1.构造亲和矩阵W
2.构造度矩阵D
3.拉普拉斯矩阵L
4.计算L矩阵的第二小特征值(谱)对应的特征向量Fiedler 向量
5.以Fiedler向量作为kmean聚类的初始中心,用kmeans聚类
亲和矩阵 :W_ij=exp(-(d(s_i,s_j)/2o^2)) d(s_i,s_j) = ||s_i,s_j||. o 为事先设定的参数。
度矩阵:D_ii =sum(w_i)
规范相似矩阵:D^(-1/2)*W*D^(1/2) ,即:W(i,j)/(D(i,i))^1/2*(D(j,j))^1/2
计算(D-W)*x=lamd*D*x 的第二小特征值
Mahout 流程:
亲和矩阵格式
i,j,value
AffinityMatrixInputJob 输出格式
i vector
构造度矩阵(亲和矩阵,i行元素求和作为返回向量i列的值)
MatrixDiagonalizeJob
VectorCache 将向量存储在HDFS中
VectorMatrixMultiplicationJob 向量矩阵相乘
求矩阵的特征值:SSVDSolver (分布式SVD),默认是DistributedLanczosSolver(兰索斯分解器)
将U矩阵归一化
UnitVectorizerJob.runJob(data, unitVectors);
UnitVectorizerJob 归一化矩阵
输入矩阵V,输入矩阵U
v_ij = u_ij / sqrt(sum_j(u_ij * u_ij)
归一化后的U矩阵中i行的最大值作为特征向量的i列的值,以该向量作为种子生成初始中心。
Kmeans 聚类,生成最终的簇。