聚类

1.产生背景

    聚类的目的也是把数据分类，但是事先我是不知道如何去分的，完全是算法自己来判断各条数据之间的相似性，相似的就放在一起。在聚类的结论出来之前，我完全不知道每一类有什么特点，一定要根据聚类的结果通过人的经验来分析，看看聚成的这一类大概有什么特点。在现实世界中，“人以类聚，物以群分”，“近朱者赤近墨者黑”，“根据时间线，借用佛洛依德的话来说，人们爱上的，往往都是与他们相似的人，或是他们曾经的那种人，或是他们想要成为的那种人“。人们常常说的”圈子“不同，不必强融，大概说的就是不是同一类人，没必要非要融入那个认知等均不在同一个范围内的人。在很多场景中我们需要对人做人物画像，需要对人的兴趣爱好做挖掘，来达到商业目的。这时候聚类算法作为一种比较直观易懂的算法就应运而生。

2.特点

    1.算法变种多，如kmeans聚类、dbScan聚类、层次聚类、图分裂聚类、关联规则聚类、半监督标签传播算法聚类等；

    2.”距离“

3.网络结构

    不同的聚类算法网络结构略有不同

    3.1. kmeans聚类：

     3.2.dbScan聚类

    3.3. 层次聚类

3.4.图分裂聚类

    3.5.关联规则聚类

    3.6.半监督标签传播算法

    以上均为盗图

4.算法思想

    4.1 kmeans聚类：

            1）初始化随机选取k个中心点；

            2）分别计算其他节点到这k个中心点的距离；选择距离最小的中心点加入；

            3）重新计算此节点新加入的”群“的质心，并选择质心点作为此”群“新的中心点；

            4）其他节点不断重复1）-3）的过程，直到原中心点和新的质心点的距离小于某一设定阈值，计算结束；

    4.2 dbScan聚类

            1）选择在指定的阈值L范围内，某个节点A周围节点个数最多的那个点作为一个”中心点“；

            2）如果A这个阈值L的圈内有其他的“中心点”B，则其他中心点B的所属L范围内的“节点X”也间接成为A节点的所属节点；这里X节点如果是“中心节点”，则可继续延伸；如果X节点是“非中心节点”，则X节点后面不可延伸；

            3）其他节点也进行1）-2）过程的计算；

            4）上述所有节点计算完成后，可能会出现某些个别节点不属于阈值L范围内的任何节点；那么这个节点就自成一个“圈”；

     4.3. 层次聚类

            1）将每个对象看作一类，计算两两之间的最小距离；

            2）将距离最小的两个类合并成一个新类；

            3）重新计算新类和所有类之间的距离；

            4）重复2）-3），直到所有类合并成一类；

    4.4.    图分裂聚类

    4.5.   关联规则聚类

            1）关联规则根据对象两两的支持度，将支持度高的聚类在一起；

    4.6. 半监督标签传播算法

          1)  把没有标注的样本和有标注的样本进行比较，相似度高的标为同标注，会优先标注离有标注近的无标注样本，然后再进行传播。

5. 算法优缺点对比

6.参考