聚类算法学习笔记（五）——划分聚类

1.     划分聚类

其实从某种角度讲，划分聚类是完全不用赘述的一种聚类方法，可能也是最常见的聚类算法了。著名的k-means算法就是个中典型。这次的内容主要是通过k-means聚类算法来总体介绍一下划分聚类。

简单来讲，k均值聚类究竟做了什么事，我们可以这样来看，有N个数据点的集合D={x1,x2,…,xn}，每个xi代表一个特征向量，目标是将这N个点根据某种相似准则将其划分到K个分类中。而k均值所表达的重要在于相似准则的选取，即不断的使用类簇的均值来完成这样的划分。当然也有书把这种相似准则称之为评分函数。基于划分的聚类算法对于homogeneity的实现是通过选取适当的评分函数并使每一个数据点到它所属的聚类中心的距离最小化。而关键就是如何定义这种距离，和所谓的聚类中心。举个例子来讲，如果定义聚类间距离为欧式距离，那么可以使用协方差的概念来定义通用的评分函数。划分聚类的思想是最直观和易懂的分类思想，因此我也不在这里长篇介绍，还是以算法的实现和代码来直观表现划分聚类的性能。

2. 算法实现

       我们以k-means算法为例来实现划分聚类。该算法的复杂度为O(KnI)，其中I是迭代次数。这种算法的一个变体是依次分析每个数据点，而且一旦有数据点被重新分配就更新聚类中心，反复的在数据点中循环直到解不再变化。k-means算法的搜索过程局限于全部可能的划分空间的一个很小的部分。因此有可能因为算法收敛到评分函数的局部而非全局最小而错过更好的解。当然缓解方法可以通过选取随机起始点来改进搜索（我们例子中的KMPP算法），或者利用模拟退火等策略来改善搜索性能。因此，从这个角度来理解，聚类分析实质上是一个在庞大的解空间中优化特定评分函数的搜索问题。

不多说了，直接上代码吧！！！

k-means算法：

for k = 1, … , K 令 r(k) 为从D中随机选取的一个点；

while 在聚类Ck中有变化发生 do

       形成聚类：

       For k = 1, … , K do

              Ck = { x ∈ D | d(rk,x) <= d(rj,x) 对所有j=1, … , K, j != k}；

       End;

       计算新聚类中心：

       For k = 1, … , K do

              Rk = Ck 内点的均值向量

       End;

End;

具体实现部分因为有Apache Commons Math的现成代码，秉着Eric Raymond的TAOUP中的极大利用工具原则，我没有写k-means的实现，而是直接利用Apache Commons Math中的k-means plus plus代码来作为例子。

具体如何测试这一算法，给出了测试代码如下：

 1private static void testKMeansPP(){
 2
 3        //ori is sample as n instances with m features, here n=8,m=2
 4
 5       int ori[][] = {{2,5},{6,4},{5,3},{2,2},{1,4},{5,2},{3,3},{2,3}};
 6
 7       int n = 8;
 8
 9       Collection<EuclideanIntegerPoint> col = new ArrayList<EuclideanIntegerPoint>();
10
11       for(int i=0;i<n;i++){
12
13           EuclideanIntegerPoint ec = new EuclideanIntegerPoint(ori[i]);
14
15           col.add(ec);
16
17       }
18
19       KMeansPlusPlusClusterer<EuclideanIntegerPoint> km = new KMeansPlusPlusClusterer<EuclideanIntegerPoint>(new Random(n));
20
21       List<Cluster<EuclideanIntegerPoint>> list = new ArrayList<Cluster<EuclideanIntegerPoint>>();
22
23       list = km.cluster(col, 3, 100);
24
25       output(list);
26
27    }
28
29private static void output(List<Cluster<EuclideanIntegerPoint>> list){
30
31       int ind = 1;
32
33       Iterator<Cluster<EuclideanIntegerPoint>> it = list.iterator();
34
35       while(it.hasNext()){
36
37           Cluster<EuclideanIntegerPoint> cl = it.next();
38
39           System.out.print("Cluster"+(ind++)+" :");
40
41           List<EuclideanIntegerPoint> li = cl.getPoints();
42
43           Iterator<EuclideanIntegerPoint> ii = li.iterator();
44
45           while(ii.hasNext()){
46
47              EuclideanIntegerPoint eip = ii.next();
48
49              System.out.print(eip+" ");
50
51           }
52
53           System.out.println();
54
55       }
56
57    }
58
59    /** *//**
60
61    *@param args
62
63    */
64
65    public static void main(String[] args) {
66
67       //testHierachicalCluster();
68
69       testKMeansPP();
70
71       //testBSAS();
72
73       //testMBSAS();
74
75    }
76
77

3. 小结

       划分聚类是聚类分析中最常用的一种聚类算法了，对于其研究的论文也是多如牛毛。感兴趣的朋友们完全可以通过阅读各种相关论文来感受这一算法的美妙。当然还要再次感谢Apache Commons Math对于诸多常用数学计算的实现。对于聚类分析的总结学习暂时到此告一段落，最近要忙着写论文，等过段时间有空可以考虑继续聚类算法的研究学习。

4. 参考文献及推荐阅读

[1]PatternRecognitionThird Edition, Sergios Theodoridis, Konstantinos Koutroumbas

[2]模式识别第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王爱侠, 张广源等译

[3]数据挖掘原理, David Hand and et al, 张银奎等译

[4]http://commons.apache.org/math/

posted on 2010-05-11 21:07 changedi 阅读(7777) 评论(5)  编辑  收藏 所属分类: 聚类分析