聚类算法简介
聚类是数据挖掘的一个基本问题。人们把相似的事物分成一类，同样对待，这样就大大降低了处理的复杂度。
应用举例：
市场销售: 帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；
土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区；
保险: 对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；
城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅；
地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类；
传统的聚类由人利用统计方法进行。这在现代，数据量快速积累的情况下过于昂贵且太慢。聚类算法则提供了低廉、快速的解决办法。
聚类问题的数学抽象：
给定被聚类的一群对象，对每个对象我们可以提取其d个特征，每个特征有若干种取值（有限/离散的或无限/连续的）。如果两个对象的同一特征相同或相近，则这两个对象在这个特征上是相似的。根据这d个特征，我们定义两个对象之间的距离，再根据距离远近，把离得近的点尽量分到一簇里，而离得远的点尽量分到不同的两簇里。每一簇成为一个结果类。
这样，每个对象O[sub]i[/sub]对应于d维空间里的1个点p[sub]i. [/sub]问题转化成给定d维空间里的一群点p[sub]1[/sub],p[sub]2[/sub],…,p[sub]N[/sub], p[sub]i[/sub]=(a[sub]i1[/sub],...,a[sub]id[/sub]). 根据它们彼此的距离把它们分到若干类（K类）里。
对聚类结果的衡量，一般结合簇内距离和簇间距离。即，簇内距离越小，簇间距离越大，这样的结果越好。
求聚类的最优解似乎需要穷举所有组合，因此在计算上是不可行的。常用的算法都是近似算法。
常见的聚类算法有：
1. K-Means
2. Hierarchical clustering，常见的有Agglomerative clustering（凝聚法）
3. CLARA(NS)
4. BIRCH
……
1. K-Means
其中心思想是每一类用一个代表点表示，并按照这个点对所有点分类。用迭代逐步求精。
一开始，随机选K个点作为种子，按与这K个点的远近把所有点分成K类，然后对每一类，计算其“质心”（即求每一维坐标的平均值，得到的点），用它作为新的代表点，再对所有点分类。这样迭代，直至最后收敛（即上一次得到的那组K个点和这一次的K个点之间的差别低于某个很小的数），或超过指定步数。
可以证明，每次迭代后所有点的平方误差和总是下降的。因此算法总会收敛。
时间复杂度：O(NKd)
缺点：
1. 需要尝试K值。可以取一个较大的值，然后减小。
2. 最终效果跟初试点选取关系很大。如果不凑巧，可能聚类效果很差。
优点：
简单、时间复杂度低
2. Hierarchical clustering
生成一棵树，每个非叶节点是一个大簇，它的子节点是包含的小簇。叶节点是单独的点。
有从叶节点向上生长（凝聚）和从根节点向下生长（劈分）两大类。
凝聚法：
一开始，每个点是一个小簇。每次循环，把两个距离最近的簇合并成一个新簇。直至所有点属于同一簇（到达根节点）。
聚类结束后，为获取聚类结果，可按需要从分簇树某个高度“拦腰截断”，这一层的非叶节点就代表了各个簇。
为提高效率，一般预先计算所有点两两间的距离。这样其时间和空间复杂度均为O(N[sup]2[/sup]).
缺点：
1. 时间复杂度较大。大规模数据集上会比较慢。
2. 空间复杂度较大。在大规模数据集上，可能会超过物理允许的限度。但当当的数据量级似乎还能承受。
优点：
效果比K-Means好
注：Michael Steinbach等人提出一种二分K-Means算法，他们声称这种算法优于凝聚算法。
3. CLARA(NS)
这两个都是PAM（Partitioning Around Medoids）的衍生算法。PAM与K-Means有些类似，它把每个簇用一个点代表，某个点O属于簇C<=>与p最近的代表点为O[sub]C[/sub]。与K-Means不同的是，它的代表点必须是数据点集合里的某点。而K-Means中的“质点”很可能并不对应某个存在的点。PAM的代表点调整方案也不同。代表点的每一步调整里，它首先计算所有可能的调整方案（所有的代表点和非代表点的两两组合），找出最能提高聚类质量的那个组合并执行。
容易看到，PAM的时间复杂度非常高。CLARA和CLARANS都是为了解决这一问题提出的近似算法。其中，CLARA是从所有点中选若干抽样点，对其进行PAM算法。而CLARANS把聚类的不断求精过程抽象成在一棵聚类方案树上随机游走的过程（这棵树上，每个节点都对应一种聚类方案），每次游走都朝着更好的方向（否则换一种调整方案）。
优点：
1. 对outlier（数据里的噪声）抵抗力比较强
2. 聚类结果与数据的输入顺序无关
3. 能处理很大规模的数据（空间复杂度较低）
缺点：
1. 实现比较复杂
2. 时间复杂度仍比较高
4. BIRCH
它的中心思想是用代表点代替临近的点，这样可以大规模降低问题规模。但直觉上，被某个点所代表的点数多少应该成为衡量该点重要性的指标。BIRCH把被代表的点的属性浓缩在几个量里：点的数目、所有点的线性和（每个坐标之和得到的向量）、所有点对应的向量长度的平方和。
BIRCH通过4遍pass逐渐构造一棵分簇的树。第一遍先建立一棵粗略分簇的树，后面的3次pass再慢慢调整求精。
时间和空间复杂度：均为O(N)
缺点：
难理解，实现起来非常复杂
优点：
1. 时间、空间复杂度都很低。适合很大规模的数据集。
2. 对outlier抵抗力很强
3. 聚类结果与数据的输入顺序无关
综合比较：
| 时间复杂度
| 空间复杂度
| 效果
| 实现难度
| K-Means
| O(NKd)
| O(N+K)
| 不稳定
| 简单
| 凝聚法
| O(N[sup]2[/sup])
| O(N[sup]2[/sup])
| 尚可
| 简单
| CLARANS
| O(NP(N))[sup]*
[/sup] | O(N)
| 未知（没有与K-means比较的数据）
| 较复杂
| BIRCH
| O(N)
| O(N)
| 好
| 复杂
|
* P(N): 程序每次局部搜索里，所有交换的次数。对交换的尝试会在连续尝试了若干次（如100次）仍找不到更好交换的时候终止。所以这个次数是个随机值。如果假设大致P(N)～N，则时间复杂度为O(N[sup]2[/sup]).
参考文献：
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1427769
http://www.cs.uiuc.edu/homes/hanj/refs/papers/zhang96.pdf
http://citeseer.ist.psu.edu/steinbach00comparison.html | 
发表于 2007-4-20 15:36:45
发表于 2007-4-20 15:44:26
