聚类算法: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）CURE算法：CURE（Clustering Using Representatives）是一种针对大型数据库的高效的聚类算法。

基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。

CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。

并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。

基本目标聚类算法CURE的算法实现。

对图形进行聚类，在时间，结果方面对其性能进行评估。

算法流程CURE的算法在开始时，每个点都是一个簇，然后将距离最近的簇结合，一直到簇的个数为要求的K。

它是一种分裂的层次聚类。

算法分为以下6步： 1）从源数据对象中抽取一个随机样本S。

2）将样本S分割为一组划分。

3）对划分局部的聚类。

4）通过随机取样提出孤立点。

如果一个簇增长得太慢，就去掉它。

5）对局部的簇进行聚类。

6）用相应的簇标签标记数据。

算法设计(1)基本聚类算法procedure cluster(S, k) /*将数据集S聚类成为k个簇*/ begin1. T := build_kd_tree(S) /*对应数据集S建立一个K-DTree T*/2. Q := build_heap(S) /*对应数据集S建立一个堆 Q*/3. while size(Q) > k do { /*聚类直至簇的个数为k */4. u := extract_min(Q) /*找到最近的两个簇u，v */5. v := u.cloest6. delete(Q, v)7. w := merge(u, v) /*将u，v合并为簇w */ 8. delete_rep(T, u);delete_rep(T, v);insert_rep(T, w)9. w.cloest := x /* x is an arbitrary cluster in Q*/ 10. for each x∈Q do{ /*调节因合并带来的T和Q的变化*/ 11. if (dist(w,x) < dist(w,w.cloest)) 12. w.cloest := x13. if x.cloest is either u or v {14. if dist(x, x.cloest) < dist(x.w)15. x.cloest := cloest_cluster(T, x, dist(x,w)) 16. else 17. x.cloest := w 18. relocate(Q, x) 19. } 20. else if dist(x, x.cloest) > dist(x, w) { 21. x.cloest := w 22. relocate(Q, x) 23. } 24. }25. insert(Q, w) 26. } end此程序段用到的数据结构有Heap，和K-DTree。

为了合并距离最短的两个聚类，需要构建一个K-DTree来找到空间中的一聚类最近的一个聚类，之后把K-DTree 中的聚类按照其与最近的聚类的距离进行排序（用的是堆排序），找到最近的两个的聚类，将它们合并（对应函数merge（））。

CHAMELEON是一种两阶段聚类法。

第一阶段把点分成很多小的簇；第二阶段根据相近程度合并这些小的簇。

第一阶段采用K最邻近法，即把一个点和它最邻近的K个点连接起来。

第二阶段计算任意两个簇的互连性RI和紧密性RC，当两个指标都比较大时才合并这两个簇。

下图是第一阶段后形成的几个小的子簇：把子簇合并后形成的最终簇划分：3. 密度算法：DBSCAN算法、OPTICS算法、DENCLUE算法等DBSCAN算法：DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。