聚类算法简介 [原创]
聚类算法简介聚类是数据挖掘的一个基本问题。人们把相似的事物分成一类，同样对待，这样就大大降低了处理的复杂度。
应用举例：
市场销售: 帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；
土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区；
保险: 对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；
城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅；
地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类；
传统的聚类由人利用统计方法进行。这在现代，数据量快速积累的情况下过于昂贵且太慢。聚类算法则提供了低廉、快速的解决办法。
聚类问题的数学抽象：
给定被聚类的一群对象，对每个对象我们可以提取其d个特征，每个特征有若干种取值（有限/离散的或无限/连续的）。如果两个对象的同一特征相同或相近，则这两个对象在这个特征上是相似的。根据这d个特征，我们定义两个对象之间的距离，再根据距离远近，把离得近的点尽量分到一簇里，而离得远的点尽量分到不同的两簇里。每一簇成为一个结果类。
这样，每个对象Oi对应于d维空间里的1个点pi. 问题转化成给定d维空间里的一群点p1,p2,…,pN, pi=(ai1,...,aid). 根据它们彼此的距离把它们分到若干类（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(N2).
缺点：
1. 时间复杂度较大。大规模数据集上会比较慢。
2. 空间复杂度较大。在大规模数据集上，可能会超过物理允许的限度。但当当的数据量级似乎还能承受。
优点：
效果比K-Means好
注：Michael Steinbach等人提出一种二分K-Means算法，他们声称这种算法优于凝聚算法。
3. CLARA(NS)
这两个都是PAM（Partitioning Around Medoids）的衍生算法。PAM与K-Means有些类似，它把每个簇用一个点代表，某个点O属于簇C<=>与p最近的代表点为OC。与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(N2)
O(N2)
尚可
简单
CLARANS
O(NP(N))*
O(N)
未知（没有与K-means比较的数据）
较复杂
BIRCH
O(N)
O(N)
好
复杂
* P(N): 程序每次局部搜索里，所有交换的次数。对交换的尝试会在连续尝试了若干次（如100次）仍找不到更好交换的时候终止。所以这个次数是个随机值。如果假设大致P(N)～N，则时间复杂度为O(N2).
参考文献：
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 看不懂哦。
为我等菜鸟提供点背景资料吧。 如果这贴子是楼主原创, 请在标题加入[原创]或[原创首发].
**** Hidden Message ***** 引用第1楼醉乡常客于2007-04-20 15:44发表的 :
看不懂哦。
为我等菜鸟提供点背景资料吧。
增加了一点应用介绍和参考资料。
学习聚类算法需要线性代数和计算机算法的基础。 当年线代、数据结构、软件工程等课程学得都还行。
为了表达对老师的感激之情，全部还回去了。 hehe 正常
我概率也忘得差不多了
现在经常是边用边复习 确实有点深奥，我从网上找了一个比较通俗一点的关于数据挖掘之聚类算法的帖子（http://www.blogjava.net/mlh123caoer/articles/51836.html）：
一， 什么是聚类？
聚类： - 将一个对象的集合分割成几个类，每个类内的对象之间是相似的，但与其他类的对象是不相似的。
......
二， 聚类所基于的数据类型。
聚类算法通常基于“数据矩阵”和“ Dissimilarity 矩阵”。
怎么样计算不同对象之间的距离？
1 ，数值连续的变量（体重，身高等）：度量单位的选取对于聚类的结果的很重要的。例如将身高的单位从米变为尺，将体重的单位从公斤变为磅将对聚类的结果产生很大的影响。为了避免出现这种情况，我们必须将数据标准化：将数据中的单位“去掉”。
A, 计算绝对背离度。 B, 计算标准量度。
下面我们考虑怎样来计算两个对象之间的差异。 1 ，欧几里得距离。 2 ，曼哈顿距离。这两种算法有共同之处： d(i,j)>=0,d(i,i)=0, d(i,j)=d(j,i),d(i,j)=<d(i,h)+d(h,j) 。 3 ， Minkowski 距离。这是上述两种算法的通式。并且对于不同的变量，我们可以给它赋于不同的 weight.
2 ，二元数据变量：如果还是用上面的方法来计算的话，肯定会出现错误。这儿分两种情况，对称的与非对称的。
3 ， Nominal 变量： ( 例如红，黄，绿，蓝 ….)
4 ， ordinal 变量（例如科长，处长，局长 …. ）
5 ， ratio-scaled 变量：
6, 以上几种混合的变量（多数情况是这样的）：
......
我想请教aaa兄，何谓“ Dissimilarity 矩阵”？另外2～5的数据类型怎么理解？
Dissimilarity 指不相似性 即差异性
如果把每个对象看成对象空间里的一点 那么这种差异性就可以看成点跟点的距离
Nominal 变量指类型变量 这种变量的特点是取值离散 而且不同值之间没有大小关系 只有相同或不同的关系
ordinal 变量指序数变量 离散值 有大小关系
ratio-scaled变量我不清楚 google出来似乎是某种按指数变化的变量 BIRCH 为啥能有那么好的性能，又有那么好的效果？聚类方法还有很多啊，比如谱聚类就有很大一类。能提供点BIRCH的细节资料吗？比如对什么样的数据比较有优势，对于什么样的数据错误率较大？ 现在变为字典学习了 引用第9楼hakodate于2014-02-16 22:35发表的 :
现在变为字典学习了
这是什么技术，没听说过？
页:
[1]