1/K-Means聚类
算法步骤：
(1)首先我们选择一些类/组，并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。
(2)计算每个数据点到中心点的距离，数据点距离哪个中心点最近就划分到哪一类中。
(3)计算每一类中中心点作为新的中心点。
(4)重复以上步骤，直到每一类中心在每次迭代后变化不大为止。也可以多次随机初始化中心点，然后选择运行结果最好的一个。
下图演示了K-Means进行分类的过程：
速度快，计算简便
我们必须提前知道数据有多少类/组。
K-Medians是K-Means的一种变体，是用数据集的中位数而不是均值来计算数据的中心点。
K-Medians的优势是使用中位数来计算中心点不受异常值的影响；缺点是计算中位数时需要对数据集中的数据进行排序，速度相对于K-Means较慢。
2/均值漂移聚类
均值漂移聚类是基于滑动窗口的算法，来找到数据点的密集区域。
这是一个基于质心的算法，通过将中心点的候选点更新为滑动窗口内点的均值来完成，来定位每个组/类的中心点。然后对这些候选窗口进行相似窗口进行去除，最终形成中心点集及相应的分组。
具体步骤：
1. 确定滑动窗口半径r，以随机选取的中心点C半径为r的圆形滑动窗口开始滑动。均值漂移类似一种爬山算法，在每一次迭代中向密度更高的区域移动，直到收敛。
2. 每一次滑动到新的区域，计算滑动窗口内的均值来作为中心点，滑动窗口内的点的数量为窗口内的密度。在每一次移动中，窗口会向密度更高的区域移动。
3. 移动窗口，计算窗口内的中心点以及窗口内的密度，知道没有方向在窗口内可以容纳更多的点，即一直移动到圆内密度不再增加为止。
4. 步骤一到三会产生很多个滑动窗口，当多个滑动窗口重叠时，保留包含最多点的窗口，然后根据数据点所在的滑动窗口进行聚类。
下图演示了均值漂移聚类的计算步骤：
下面显示了所有滑动窗口从头到尾的整个过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。
优点：1）不同于K-Means算法，均值漂移聚类算法不需要我们知道有多少类/组。
2）基于密度的算法相比于K-Means受均值影响较小。
缺点：1）窗口半径r的选择可能是不重要的。
3/凝聚层次聚类
层次聚类算法分为两类：自上而下和自下而上。凝聚层级聚类(HAC)是自下而上的一种聚类算法。HAC首先将每个数据点视为一个单一的簇，然后计算所有簇之间的距离来合并簇，知道所有的簇聚合成为一个簇为止。
下图为凝聚层级聚类的一个实例：
具体步骤：
1. 首先我们将每个数据点视为一个单一的簇，然后选择一个测量两个簇之间距离的度量标准。例如我们使用average linkage作为标准，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
2. 在每次迭代中，我们将两个具有最小average linkage的簇合并成为一个簇。
3. 重复步骤2知道所有的数据点合并成一个簇，然后选择我们需要多少个簇。
层次聚类优点：
（1）不需要知道有多少个簇
（2）对于距离度量标准的选择并不敏感
缺点：效率低
4/图团体检测(Graph Community Detection)，，这类似于在社交网络中的小群体的发现
当我们的数据可以被表示为网络或图，可以使用图团体检测方法完成聚类。
在这个算法中图团体（graph community）通常被定义为一种顶点(vertice)的子集，其中的顶点相对于网络的其他部分要连接的更加紧密。
下图展示了一个简单的图，展示了最近浏览过的8个网站，根据他们的维基百科页面中的链接进行了连接。
通过上述公式可以计算图的模块性，且模块性越高，该网络聚类成不同团体的程度越好，因此通过最优化方法寻找最大模块性就能发现聚类该网络的最佳方法。
组合学告诉我们对于一个仅有8个顶点的网络，就存在4140种不同的聚类方式，16个顶点的网络的聚类方式将超过100亿种。32个顶点的网络的可能聚类方式更是将超过10^21种。
因此，我们必须寻找一种启发式的方法使其不需要尝试每一种可能性。这种方法叫做Fast-Greedy Modularity-Maximization(快速贪婪模块性最大化)的算法
这种算法在一定程度上类似于上面描述的集聚层次聚类算法。
只是这种算法不根据距离来融合团体，而是根据模块性的改变来对团体进行融合。
具体步骤：
1/首先初始分配每个顶点到其自己的团体，然后计算整个网络的模块性M。
2/第1步要求每个团体对（community pair）至少被一条单边链接，如果有两个团体融合到了一起，该算法就计算由此造成的模块性改变 ΔM。
3/第2步是取 ΔM 出现了最大增长的团体对，然后融合。然后为这个聚类计算新的模块性M，并记录下来。
4/重复第1步和第2步——每一次都融合团体对，这样最后得到 ΔM 的最大增益，然后记录新的聚类模式及其相应的模块性分数M。
5/重复第1步和第2步——每一次都融合团体对，这样最后得到 ΔM 的最大增益，然后记录新的聚类模式及其相应的模块性分数M。
import_random
数据挖掘工程师 @aa
粉丝
