机器学习实践：彭大叔为微博关注人提供联姻指南

02 Oct 2013 ###背景&相关知识点 聚类算法主要用于对一堆杂乱的事物进行自动归类，具体应用场景请自行脑补，还是挺多的。
聚类算法是一种无监督的学习算法。主要包括分级聚类和K均值聚类等，前者是逐层收敛，类似于构造一棵二叉树，最终所有item被归到根节点一个大类中，每层都向下再分小类。同一级兄弟节点的距离和子节点的差异程度成正比。算法过程是不断合并最为相似（根据欧式距离等度量）的项目，合并后项目的中点为被合并项目的平均值，直到最后合并成一个大类别;K均值聚类则是指定了类别个数，算法初始便随机指定K个点为类别基准点,然后其他所有点寻找距离自己最近的基准点投奔。算法会进行多轮迭代，每一轮的过程是：所有点寻找离自己最近的基准点投奔，等所有点都找到自己的队伍之后，调整K个聚类中的基准点位置为当前聚类里所有点的平均值，然后进入下一轮迭代，直到某一次迭代结果和上次迭代没有任何变化，算法咣当终止.
新浪微博中每个用户注册之初都会给一些tag让用户给自己做画像，表明自己的偏好，除了个别用户忽略这一步，大多数人都会给自己多少加几个标签。这些tag正好给了聚类算法用武之地,于是开搞。
首先把用户数据抓下来,新浪限制查看别人的粉丝只能查看前10页，那就不费劲了，只看自己关注人的资料就好。爬下自己关注人的tag和uid以及用户名，然后拾掇拾掇生成一个用户-tag矩阵，行为uid，列为所有用户的tag列表(当然，这是一个巨特么稀疏的矩阵)。矩阵单元格A[x][y]值为1或者0，1表示用户x给自己打了tab y，0表示没有。 然后套上聚类算法跑一跑，把结果绘制出图如下所示： 随机查看了几组，聚类结果还算靠谱，尤其是认识的那几个人，有2对还真给恰当的聚到一个分组里了,这里就不@了,真是狐朋狗友，狼狈为奸啊- -||。树两边的用户由于给自己打的tag都比较奇葩，不好归类，所以被算法归到边缘地带了。

###项目地址 https://github.com/zuojie/MichineLearningCases/tree/master/Cluster