基于Hadoop云平台的并行谱聚类算法的设计与实现
牛 科， 贾郭军*
【摘 要】 谱聚类(Spectral Clustering)是建立在谱图理论基础上的一种聚类算法.与传统的聚类算法相比，谱聚类能够在任意形状的样本空间上进行聚类且收敛于全局最优解.然而，实际问题中大规模数据集普遍存在，在使用谱聚类对大规模数据集进行聚类时，收敛速度变得十分缓慢，甚至无法在有效的时间内得到聚类结果.并行算法是针对大规模数据集进行处理的一种有效方法.基于Hadoop云计算平台实现大规模数据集的存储和处理是目前实现并行计算的一种高效解决方案.
【期刊名称】山西师范大学学报（自然科学版） 【年(卷),期】2014(028)001 【总页数】4
【关键词】 谱聚类； 云计算；Hadoop云平台
计算机技术和网络技术的迅猛发展以及web 2.0的逐步普及，使数据的产生和存储呈现出指数级的增长趋势.从海量数据中挖掘潜在的知识越来越受到各个应用领域的专家和学者们的青睐.对海量数据进行聚类分析也逐渐成为数据挖掘中研究的热点问题之一.谱聚类是基于谱图理论的一种聚类算法[1]，在解决实际问题时，特别是在复杂形状样本空间的聚类中表现出了传统聚类算法无法比拟的优势.然而，实际应用中随着数据集规模的增大，谱聚类的收敛速度变得十分缓慢.
云计算(Cloud Computing)是由分布式计算(Distributed Computing)、并行处理(Parallel Computing)、网格计算(Grid Computing)发展而来的，是一种
新兴的计算模型.云计算的出现对海量数据挖掘技术的发展提供了良好的契机.Hadoop是目前最流行的开源云计算平台.本文基于Hadoop[2]云计算平台设计实现了谱聚类算法的并行化.实验分析表明，并行化的谱聚类算法在大规模数据集上的聚类性能得到了明显的改善.
1 谱聚类算法
近年来，基于谱图理论的谱聚类已逐渐成为最为广泛使用的聚类算法之一[1].在计算机科学、统计学、生物学、物理学等领域越来越受到人们的关注.与传统的K-means等聚类算法相比，谱聚类在复杂形状样本聚类中表现出了良好的性能. 1.1 相似度图
谱聚类将数据集中的所有样本看作图的顶点集v={x1, x2, …, xn}，s=Rn×n是一个相似度矩阵，sij是数据点xi和xj的相似度[1].在谱聚类中通常采用高斯函数计算数据点之间的相似度： (1)
为了获得更好的计算性能，谱聚类通常对矩阵S进行稀疏化处理.稀疏化相似矩阵通常采用ξ-近邻、k-近邻、全连通三种方式[1].
谱聚类算法将稀疏化的顶点间的相似度矩阵作为相应点对的连接边的权值.这样就得到一个基于样本间相似度的无向图G=(V,E)的相应边的权重wij≥0,i,j=1,2，…,n. 因为G是一个无向图，所以可以得到顶点对(xi,xj)间的连接权值wij=wji.任意顶点vi∈V的度使用如下公式进行计算： (2)
其中，W=(wij)是n×n阶矩阵，D=(di)是1×n阶矩阵，分别称为连接矩阵和度矩阵.
1.2 拉普拉斯矩阵
由连接矩阵W和度矩阵D可以得到顶点集的拉普拉斯矩阵.拉普拉斯矩阵分为非归一化和归一化两种.非归一化的拉普拉斯矩阵计算公式如下： L=D-W (3)
归一化的拉普拉斯矩阵计算公式如下： Lsym=D-1/2LD-1/2=I-D-1/2WD-1/2 (4)
Lrw=D-1L=I-D-1W (5)
公式(4)和(5)中的L即为公式(3)中的非归一化拉普拉斯矩阵. Lsym是对称矩阵，Lrw是一个随机游走矩阵，通常是非对称的[1]. 1.3 传统谱聚类算法
传统谱聚类算法就是在构建的拉普拉斯矩阵中，根据聚类个数k,求解其前k个特征值与其对应的特征向量并构建特征向量空间.然后采用K-means算法对特征向量空间中的特征向量进行聚类. 算法步骤描述如下：
Step 1：构造基于样本间相似度的相似度图，并计算加权连接矩阵W，度矩阵D；
Step 2：计算拉普拉斯矩阵L(依据需要解决的实际应用问题采用非归一化的拉普拉斯矩阵或者归一化的拉普拉斯矩阵Lsym或者Lrw)；
Step 3：计算拉普拉斯矩阵L的前k个特征值及其对应的特征向量
基于Hadoop云平台的并行谱聚类算法的设计与实现
