Clustering Algorithm

聚类，是根据样本间的数据相似性进行聚类

聚类算法分类：

1.基于划分

给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。
特点：计算量大。很适合发现中小规模的数据库中小规模的数据库中的球状簇。
算法：K-MEANS算法、K-MEDOIDS算法、CLARANS算法

2.基于层次

对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
特点：较小的计算开销。然而这种技术不能更正错误的决定。
算法：BIRCH算法、CURE算法、CHAMELEON算法

3.基于密度

只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
特点：能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
算法：DBSCAN算法、OPTICS算法、DENCLUE算法

4.基于网格

将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。
特点：处理速度很快，通常这是与目标数据库中记录的个数无关的，只与把数据空间分为多少个单元有关。
算法：STING算法、CLIQUE算法、WAVE-CLUSTER算法

K-means聚类

最原始的K-means

最简单而经典的聚类算法，具体如下：

算法的原理以及流程：

1.初始化数据集，随机初始化K个中心点

2.针对数据集中所有的样本n，计算每个样本到每个中心点之间的距离，选取距离最短的中心点为其所属的类

3.在各个类内部，重新寻找合适的中心点：计算出类内部所有样本的m维中心点，作为全新的中心点

4.重新进行聚类操作2、3，直至中心点不再变换或者迭代达到固定次数t

时间复杂度：O(tnm*k)

空间复杂度：O(nm+km)

其中m为每个元素字段个数，n为数据量，t为迭代数。一般I,k,m均可认为是常量，所以时间和空间复杂度可以简化为O(n)，即线性的。

K值选取

在实际应用中，由于Kmean一般作为数据预处理，或者用于辅助分类贴标签。所以k一般不会设置很大。可以通过枚举，令k从2到一个固定值如10，在每个k值上重复运行数次kmeans(避免局部最优解)，并计算当前k的平均轮廓系数，最后选取轮廓系数最大的值对应的k作为最终的集群数目。

半监督的K-means：

在K-means的过程中，如果初始化条件较差，即没给定合适的K和初始点位置，一方面计算上的损耗十分巨大，另一方面也可能导致聚类的结果不准确，所以半监督的K-means其实就提供一部分带label的数据，作为初始化条件的依据，由这个小数据集得到聚类的目标数量以及通过类别内部先行计算，确定其中心点，从而使得聚类效果更好、计算效率更高

K-medoids:

由于K-means聚类过程中，会根据当前类内全部样本的值进行平均，而其准则函数通常为平方误差，那当数据集内部存在一个明显的离群值时，可能会对中心点的计算带来比较大的误差，为了防止这一点，K-medoids就通过中心点为类内样本点的方式来削弱异常值的影响

具体的算法流程：

　　1.在总体n个样本点中任意选取k个点作为medoids

　　2.按照与medoids最近的原则，将剩余的n-k个点分配到当前最佳的medoids代表的类中

　　3.对于第i个类中除对应medoids点外的所有其他点，按顺序计算当其为新的medoids时，准则函数的值，遍历所有可能，选取准则函数最小时对应的点作为新的medoids

　　4.重复2-3的过程，直到所有的medoids点不再发生变化或已达到设定的最大迭代次数

　　5.产出最终确定的k个类

与K-means的区别：

K-Means	K-Medoids
初始据点随机选取	初始随机据点限定在样本点中
使用Means（均值）作为聚点，对outliers（极值）很敏感	使用Medoids(中位数)作为聚点
对数据要求高，要求数据点处于欧式空间中	可适用类别（categorical）类型的特征——（4）
时间复杂度：O(nkt)，t为迭代次数	时间复杂度：O(n^2 kt)，t为迭代次数——（4）
K-Means 算法对小规模数据集较高效（efficient for smaller data sets）	K-Medoids算法对大规模数据性能更好，但伸缩性较差——（3）
都有可能陷入局部最优解的困境之中
K的含义相同,都需要开始人为设定簇数目
都是无监督算法

题外话——KNN：

说来很神奇，有人会把K-means与KNN搞混，但事实上，二者的区别十分巨大，简单而言，前者是无监督或者半监督的聚类，通过计算打上label，而后者是有监督的分类，通过已有label的数据集推测出新的数据属于的类别。

详细区别如下表：

KNN	K-Means
1.KNN是分类算法 2.监督学习 3.喂给它的数据集是带label的数据，已经是完全正确的数据	1.K-Means是聚类算法 2.非监督学习 3.喂给它的数据集是无label的数据，是杂乱无章的，经过聚类后才变得有点顺序，先无序，后有序
没有明显的前期训练过程，属于memory-based learning	有明显的前期训练过程
K的含义：来了一个样本x，要给它分类，即求出它的y，就从数据集中，在x附近找离它最近的K个数据点，这K个数据点，类别c占的个数最多，就把x的label设为c	K的含义：K是人工固定好的数字，假设数据集合可以分为K个簇，由于是依靠人工定好，需要一点先验知识
相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。**

Mean-shift：

均值漂移聚类，是基于滑动窗口的算法，试图找到数据点的密集区域。目标的定位就是每一类的中心点，通过将中心的候选点向滑动窗口内的均值点移动来实现向密度更大的方向滑动，直至发现密度不再增加；而后由于多个窗口存在重叠交叉，则进行合并——保留点多密度大的集合；

具体操作：

1.我们从一个以 C 点（随机选择）为中心，以半径 r 为核心的圆形滑动窗口开始。均值漂移是一种爬山算法，它包括在每一步中迭代地向更高密度区域移动，直到收敛。

2.在每次迭代中，滑动窗口通过将中心点移向窗口内点的均值（因此而得名）来移向更高密度区域。滑动窗口内的密度与其内部点的数量成正比。自然地，通过向窗口内点的均值移动，它会逐渐移向点密度更高的区域。

均值漂移聚类算法动图0

3.我们继续按照均值移动滑动窗口直到没有方向在核内可以容纳更多的点。请看上面的图；我们一直移动这个圆直到密度不再增加（即窗口中的点数）。

4.步骤 1 到 3 的过程是通过许多滑动窗口完成的，直到所有的点位于一个窗口内。当多个滑动窗口重叠时，保留包含最多点的窗口。然后根据数据点所在的滑动窗口进行聚类。

下面显示了所有滑动窗口从头到尾的整个过程。每个黑点代表滑动窗口的质心，每个灰点代表一个数据点。

均值漂移聚类算法动图1

与K-means相比，首先我们不需要提前确定K的数量，将会在滑动和合并的过程中自然发现；且聚类中心向着密度最大的点聚类的情况也是令人满意的，因为理解和适应自然数据驱动的意义s是非常直观的；但是缺点在于，窗口的半径R的选择也是十分重要的。

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise），是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

算法流程：

DBSCAN聚类算法

我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N