聚类算法比较

聚类算法:

1. 划分法：K-MEANS算法、K-M EDOIDS算法、CLARANS算法；

1）K-means 算法：

基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。

K-Means聚类算法主要分为三个步骤：

(1)第一步是为待聚类的点寻找聚类中心

(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去

(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心

反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止

下图展示了对n个样本点进行K-means聚类的效果，这里k取2：

(a)未聚类的初始点集

(b)随机选取两个点作为聚类中心

(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去

(d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心

(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去

(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心

优点：

1.算法快速、简单;

2.对大数据集有较高的效率并且是可伸缩性的;

3.时间复杂度近于线性，而且适合挖掘大规模数据集。

缺点：

1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。

2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。

3. 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。

4. 产生类的大小相差不会很大，对于脏数据很敏感。

2）K-M EDOIDS（k-medoids）算法

与k-means很像，不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值，在 K-medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。

选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-MEDODIS的具体流程如下：

1）任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。

2）将余下的对象分到各个类中去（根据与medoid最相近的原则）；

3）对于每个类，顺序选取一个对象，计算用这个对象代替原中心点的方差。选择方差最小的那个对象来代替原中心点。这样K个medoids就改变了。

4）重复2、3步直到K个medoids固定下来。

优点：

不容易受到那些由于误差之类的原因产生的脏数据的影响

缺点：

计算量显然要比K-means要大，一般只适合小数据量

3）CLARANS (A Clustering Algorithm based on Randomized Search，基于随机选择的聚类算法)：

将采样技术（CLARA[Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1,O2…Oi…Ok），然后在这当中选取E 最小的一个作为最终的结果]）和PAM（找出中心点）结合起来。CLARA的主要思想是：不考虑整个数据集合，而是选择实际数据的一小部分作为数据的代表。然后用PAM方法从样本中选择中心点。如果样本是以非常随机的方式选取的，那么它应当接近代表原来的数据集。从中选出代表对象（中心点）很可能和从整个数据集合中选出的代表对象相似。CLARA抽取数据集合的多个样本，对每个样本应用PAM算法，并返回最好的聚类结果作为输出。

CLARA的有效性主要取决于样本的大小。如果任何一个最佳抽样中心点不在最佳的K 个中心之中，则CLARA将永远不能找到数据集合的最佳聚类。同时这也是为了聚类效率做付出的代价。

CLARANS聚类则是将CLARA和PAM有效的结合起来，CLARANS在任何时候都不把自身局限于任何样本，CLARANS在搜素的每一步都以某种随机性选取样本。算法步骤如下（算法步骤摘自百度文库）：

1、输入参数numlocal和maxneighbor。numlocal 表示抽样的次数，maxneighbor 表示一个节点可以与任意特定邻居进行比较的数目令：i=1，i用来表示已经选样的次数mincost 为最小代价，初始时设为大数。

2、设置当前节点current为Gn中的任意一个节点。

3、令j =1。（j用来表示已经与current进行比较的邻居的个数）

4、考虑当前点的一个随机的邻居S，并计算两个节点的代价差。

5、如果S的代价较低，则current:=S，转到步骤3。

6、否则，令j=j+1。如果j<=maxneighbor,则转到步骤4。

7、否则，当j>maxneighbor，当前节点为本次选样最小代价节点. 如果其代价小于mincost,令mincost为当前节点的代价，bestnode为当前的节点。

8、令i= i+1，如果i〉numlocal,输出bestnode，运算中止.否则，转到步骤2。对上面出现一些概念进行说明：

（1）代价值，主要描述一个对象被分到一个类别中的代价值，该代价值由每个对象与其簇中心点间的相异度（距离或者相似度）的总和来定义。代价差则是两次随机领域的代价差值。

（2）更新邻接点，CLARANS不会把搜索限制在局部区域，如果发现一个更好的近邻，CLARANS就移到该近邻节点，处理过程从新开始；否则，当前的聚类则产生了一个局部最小。如果找到一个局部最小，CLARANS从随机选择的新节点开始，搜索新的局部最小。当搜索的局部最小解达到用户指定的数目时，最好的局部最小作为算法的输出。从上面的算法步骤也可以看出这一思想。在第5步中更新节点current。

2. 层次法：自顶向下，自底向上。BIRCH算法、CURE算法、CHAMELEON算法等；

BIRCH算法(最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。如果簇不是球形的，BIRCH不能很好的工作，因为它用了半径或直径的概念来控制聚类的边界。):

算法的核心：通过扫描数据库，建立一个初始存放于内存中的聚类特征树，然后对聚类特征树的叶结点进行聚类。它的核心是聚类特征（CF）和聚类特征树（CF Tree）