二部图聚类的Spark实现及改进

1、算法介绍

该算法来自于文献[1]，该算法把二部图聚类问题转换为图划分问题，而图划分问题通过谱聚类算法解决。该算法的主要创新在于解决了以前算法只能根据二部图其中一部图，对另一部图的点聚类而不能同时对所有点聚类的问题。其根据二部图的二元性，同时聚类二部图中的点。

2、算法应用背景

现有消费者购买商品的购买次数数据，用下图来表示，图中蓝色点代表不同消费者、红色点代表不同商品，二者构成的图为二部图。每条边的权值为对应的消费者购买此商品的次数。现需要把有相同购买行为的消费者与他们偏爱购买的物品聚类在一起。每月数据量大约1千万条，每条数据个格式为：消费者ID，商品ID，购买次数;消费者ID集合大小为10万左右，商品ID集合大小为5万左右。

3、算法实现步骤

3.1分离出connected Components

原始数据可能由多个独立子图(Connected Components)构成，这些子图间并没有边。而谱聚类是基于连通图的算法，所以应从原始数据中提取出所有的独立子图，然后对每个子图应用二部图聚类算法。可以使用Spark自带的提取独立子图的算法(我是自己设计算法，其基于键-值数据运算提取独立子图)。

3.2 构造“消费者——商品”矩阵

对于每个独立子图数据，构造以矩阵A，Aij表示消费者i购买商品j的次数。若果为0，表示消费者i并未购买商品j.

3.3 计算矩阵An

可以看出矩阵An是由三个矩阵相乘得到的。D1、D2分别是对角矩阵;D1中的各个对角元素代表对应的消费者购买所有商品的次数之和;D2中的各个对角元素代表对应的商品被购买的次数之和。D-1/2这种形式表示对(对角矩阵)对角线元素施加求其平方根的倒数运算。

3.4 计算矩阵Z

假设聚类数目为k，现计算Z的前ℓ+1个左右奇异向量，第2到第ℓ+1个左奇异向量为u2,……uℓ+1,第2到第ℓ+1个右奇异向量为v2,……vℓ+1. 这里为何取值为何从第二个开始，请参考文献[1]的解释。

k个左奇异列向量构成矩阵U，k个右奇异列向量构成矩阵V;D1-1/2U、D2-1/2 V都表示两矩阵相乘;矩阵相乘结果上下放置，组成N*ℓ的新矩阵Z，N等于消费者人数。

3.5 聚类

Z每行与原始数据一一对应，对其KMeans聚类可得到与原始数据一一对应的聚类结果。

4、遇到的问题

4.1 svd计算不收敛

使用Spark提供的带标号的分布式矩阵的svd分解API，计算前10个奇异值时，spark报错为计算达到最大次数，最后发现是没有进行分离出connected Components步骤操作。

4.2 矩阵行与原数据对应问题

分布式矩阵Z与聚类数据如何一一对应?这里采用了Pipeline Model：Z由

IndexRowMatrix存储，Index表示消费者ID的行号;Z转换为包含Index与行数据两列的DataFrame，该DataFrame作为Pipeline Model输入数据，输出数据为Index、行数据与聚类所属类别号。

5、算法的改进

算法改进基于下面的两方面考量：

1.一个消费者A购买一个商品B，考虑这样的情形：

消费者A总的购买次数为1000次，其中购买商品B 仅仅5次;

商品B总的被购买次数是10次。

显然对于A和B，这个5的意义不同，量化衡量这种意义的一种方法就是求比率：

这5次，对于A重要度是5/1000， 对于B重要度是5/10

2.不同消费者总购买次数差异较大;不同商品的被购买的总量也是不同的，差异很大。

所以，直接用购买次数作为二部图边的权值不恰当。

基于上述分析，把二部图的边的权值(即原始数据的购买次数)变为：

max(A购买B的次数/A总的购买次数，A购买B的次数/B总的被购买次数)

之所以使用max，是指单方面相似很重要，即权值对于消费者A与商品B扇的意义是不一样的：以消费者A的角度，商品B不太重要;而以商品B的角度，消费者A很重要，那么以较大的值(也即是对一方较为重要的权值)作为边的权值是合理的。

6、改进后的算法评测

直观上，改进后簇划分的更均匀了，符合改进预期;

客观衡量指标采用图划分方法中normalized-cut方法的最小化目标函数值来评价：

根据生产数据的聚类结果，计算该目标函数的值，所得结果如下：

改进前的算法：N(V1, V2) ≈ 356.115

改进后的算法：N(V1, V2) ≈ 325.508

显然，改进后的算法所得到的目标函数值更小，表明改进后的算法对图的划分更合理。

7、总结

本文主要介绍了对二部图中的所有点同时聚类的一个谱聚类算法的Spark实现及根据生产数据的实际情况所做的改进，并对自己遇到过的问题做了描述。实际结果及评测表明，该算法及改进算法都比较符合生产要求，改进算法更优。

[1]Dhillon I S, Dhillon I S. Co-clustering documents and words using Bipartite Spectral[C]// Proc of ACM SIGKDD Intl Conf on Knowledge Discovery & Data Mining. 2001:269-274.