Clustering Algorithm/聚类算法[二]

Comments: 1 Comment
Published on: 2012 年 10 月 10 日

四、Canopy 聚类算法

Canopy 聚类算法的基本原则是:首先应用成本低的近似的距离计算方法高效的将数据分为多个组,这里称为一个Canopy。Canopy 之间可以有重叠的部分。

然后采用严格的距离计算方式准确的计算在同一 Canopy 中的点,将他们分配与最合适的簇中。Canopy 聚类算法经常用于 K 均值聚类算法的预处理,用来找合适的 k 值和簇中心。

下面详细介绍一下创建 Canopy 的过程:

初始,假设我们有一组点集 S,并且预设了两个距离阈值,T1,T2(T1>T2);然后选择一个点,计算它与 S 中其他点的距离(这里采用成本很低的计算方法),将距离在 T1 以内的放入一个 Canopy 中,同时从 S 中去掉那些与此点距离在 T2 以内的点(这里是为了保证和中心距离在 T2 以内的点不能再作为其他 Canopy 的中心),重复整个过程直到 S 为空为止。

这里可以发现Canopy聚类算法就是使用画圈的方法在数据集里进行简单的分类,并且每个中心点(canopy)不至于靠的太近(距离:T1-T2)。这能使我们优化K-Means聚类算法的一个缺陷,就是上篇提到过的选取初值K集的问题,借用pluskid的几个matlab图来说明一下:

上图是比较好的选取初值,得到理想结果。


上图是就因为初值的选取问题而到得了一个比较差的聚类结果。

一个避免这种情况出现的方法就是类似爬山算法,多进行几次程序的运算。另外一个就是使用这里说Canopy算法了,可以用来优化K-Means聚类算法的初始值K的选取的部分。

五、二分K-Means聚类算法

二分K-Means算法是基本的K-Means算法的扩充,它基于一个简单的想法:为了得到K个类,将原始数据集通过多次试验分裂成两个类,然后递归的在各个子类里进行二分算法即可。

这里二分类的时候不同的分发会导致不同的结果,并在递归过程中持续扩大这种二分偏向。其中多次二分试验,选择最优的二分选择进行二分。

六、模糊K-Means聚类算法

模糊 K 均值聚类算法是 K 均值聚类的扩展,它的基本原理和 K 均值一样,只是它的聚类结果允许存在对象属于多个簇,也就是说:它属于我们前面介绍过的可重叠聚类算法。为了深入理解模糊 K 均值和 K 均值的区别,这里我们得花些时间了解一个概念:模糊参数(Fuzziness Factor)。
与 K 均值聚类原理类似,模糊 K 均值也是在待聚类对象向量集合上循环,但是它并不是将向量分配给距离最近的簇,而是计算向量与各个簇的相关性(Association)。假设有一个向量 v,有 k 个簇,v 到 k 个簇中心的距离分别是 d1,d2… dk,那么 V 到第一个簇的相关性 u1可以通过下面的算式计算:

计算 v 到其他簇的相关性只需将 d1替换为对应的距离。
从上面的算式,我们看出,当 m 近似 2 时,相关性近似 1;当 m 近似 1 时,相关性近似于到该簇的距离,所以 m 的取值在(1,2)区间内,当 m 越大,模糊程度越大,m 就是我们刚刚提到的模糊参数。

七、最后的K-Means类型聚类算法的优缺点、优化总结

缺点:

1、每种数学模型都有自己的偏向,也不会有全能的模型适合所有的情况。对于发现不同的类别,K-Means和它的各种变种都具有一些局限性。具体说当原始数据具有非球形状、具有不同尺寸、不同密度时,K-Means都很难检测聚合出合理的类别。另外如果K足够大,或者分的类别足够多,这种缺陷也是能够避免的,就看是否愿意把数据集分的足够细。
2、K-Means算法对离群点的数据进行聚类时,离群点对聚类影响较大,应该提前使用一些方法删除离群点、噪点等不合理数据。
3、就是上一篇说到的,K-Means算法仅仅可以计算具有中心(质心)概念的数据集,不能对无中心数据进行聚类。如果针对这种情况改进,时间复杂度和空间复杂度都增加很多,开销很大。

优点:
时间复杂度空间复杂度相对其他聚类算法来讲有不少提升。

优化:
初始点选取可以使用Canopy算法。也可以在计算过程中使用随机搜索的办法得到最优解,即设计一个成本函数,计算每次的解成本。选择合适的K-Means的改进扩展算法等。

至此K-Means聚类算法告一段落。

个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

1 Comment - Leave a comment
  1. ml说道:

    canopy clustering解决了kmeans选取K值的问题,却又留下了选取t1和t2的问题。这个问题你怎么看?

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期一, 2017 年 11 月 20 日