- 1. Chapter 8. 聚类分析什么是聚类分析?
聚类分析中的数据类型
主要聚类分析方法分类
划分方法（Partitioning Methods）
分层方法
基于密度的方法
基于表格的方法
基于模型（Model-Based）的聚类方法
异常分析
总结
- 2. 划分方法: 基本概念划分方法: 将一个包含n个数据对象的数据库组织成k个划分（k<=n），其中每个划分代表一个簇（Cluster）。
给定一个k，要构造出k个簇，并满足采用的划分准则：
全局最优:尽可能的列举所有的划分；
启发式方法: k-平均和k-中心点算法
k-平均 (MacQueen’67):由簇的中心来代表簇；
k-中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw’87): 每个簇由簇中的某个数据对象来代表。
- 3. K-平均算法给定k，算法的处理流程如下:
1.随机的把所有对象分配到k个非空的簇中；
2.计算每个簇的平均值，并用该平均值代表相应的簇；
3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；
4.回到第二步，直到不再有新的分配发生。
- 4. K-平均算法例子
- 5. K-平均算法优点
相对高效的: 算法复杂度O(tkn), 其中n 是数据对象的个数, k 是簇的个数, t是迭代的次数，通常k, t << n.
算法通常终止于局部最优解；
缺点
只有当平均值有意义的情况下才能使用，对于类别字段不适用；
必须事先给定要生成的簇的个数；
对“噪声”和异常数据敏感；
不能发现非凸面形状的数据。
- 6. K-平均算法的变种一些变种在下面几个方面有所不同：
初始k个平均值的选择；
相异度的计算；
计算簇的平均值的策略；
处理种类字段: k-模算法 (Huang’98)
用模来替代平均值；
用新的相异度计算方法来处理类别字段；
用基于频率的方法来修改簇的模；
k-原型算法：综合k-平均和k-模算法，能同时处理类别字段和数值字段。
- 7. K-中心点算法找出簇中位置最中心的对象，即中心点来代表簇
PAM (Partitioning Around Medoids, 1987)
设定一个中心点的初始集合，然后反复的用非中心点对象来替代中心点对象，以改进聚类的质量；
PAM 算法在大数据集上效率较低，没有良好的可伸缩性；
CLARA (Kaufmann & Rousseeuw, 1990)
CLARANS (Ng & Han, 1994): Randomized sampling
- 8. PAM (Partitioning Around Medoids) (1987)PAM (Kaufman and Rousseeuw, 1987）
用真实的数据对象来代表簇
随机选择k个对象作为初始的中心点；
Repeat
对每一个由非中心对象h 和中心对象 i, 计算i被h替代的总代价 Tcih
对每一个有h和I组成的对象对
If TCih < 0, i 被 h替换
然后将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点
Until不发生变化。
- 9. PAM Clustering: Total swapping cost TCih=jCjihjihttihjhitjtihj
- 10. CLARA (Clustering Large Applications) (1990)CLARA (Kaufmann and Rousseeuw in 1990)
该算法首先获得数据集的多个采样，然后在每个采样上使用PAM算法，最后返回最好的聚类结果作为输出。
优点: 能够处理大数据集。
缺点:
效率依赖于采样的大小；
如果样本发生偏斜，基于样本的一个好的聚类不一定代表得了整个数据集合的一个好的聚类；
- 11. CLARANS (“Randomized” CLARA) (1994)CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han’94)
CLARANS 在搜索的每一步动态的抽取一个样本；
聚类过程可以被描述为对一个图的搜索，图中的每个节点是一个潜在的解，即k个中心点的集合；在替换 了一个中心点后的结果被称为当前结果的邻居。
如果找到了一个局部最优，算法从随即选择的节点开始寻找新的局部最优；
比PAM 和 CLARA更有效和有更好的伸缩性；
采用聚焦技术和空间数据结构等能进一步提高性能(Ester et al.’95)
- 12. Chapter 8. Cluster Analysis什么是聚类分析?
聚类分析中的数据类型
主要聚类分析方法分类
划分方法（Partitioning Methods）
分层方法
基于密度的方法
基于表格的方法
基于模型（Model-Based）的聚类方法
异常分析
总结
- 13. 层次方法采用距离作为衡量聚类的标准。该方法不在需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative
(AGNES)divisive
(DIANA)
- 14. AGNES (Agglomerative Nesting)由 Kaufmann 和 Rousseeuw 提出；(1990)
使用单链接方法和差异度矩阵；
合并那些具有最小差异度的节点；
Go on in a non-descending fashion
最后所有的对象合并形成一个簇。
- 15. A Dendrogram Shows How the Clusters are Merged HierarchicallyDecompose data objects into a several levels of nested partitioning (tree of clusters), called a dendrogram.
A clustering of the data objects is obtained by cutting the dendrogram at the desired level, then each connected component forms a cluster.
- 16. DIANA (Divisive Analysis)由 Kaufmann 和 Rousseeuw 提出(1990)
AGNES算法的逆过程；
最终每个新的簇只包含一个对象；
- 17. More on Hierarchical Clustering Methods层次方法的主要缺点：
没有良好的伸缩性: 时间复杂度至少是 O(n2)
一旦一个合并或分裂被执行，就不能修复；
综合层次聚类和其它的聚类技术：
BIRCH (1996): uses CF-tree and incrementally adjusts the quality of sub-clusters
CURE (1998): selects well-scattered points from the cluster and then shrinks them towards the center of the cluster by a specified fraction
CHAMELEON (1999): hierarchical clustering using dynamic modeling
- 18. BIRCH (1996)Birch: Balanced Iterative Reducing and Clustering using Hierarchies, by Zhang, Ramakrishnan, Livny (SIGMOD’96)
增量的构造一个CF树
Phase 1: 扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构；
Phase 2: 采用某个聚类算法对CF树的叶子节点进行聚类；
可伸缩性: 数据集合的单边扫描产生了一个基本的聚类，额外的扫描可以进一步的改进聚类的质量。
缺点: 只能处理数值型数据；对于非球状的簇不能很好的工作。
- 19. Clustering Feature VectorClustering Feature: CF = (N, LS, SS)
N: Number of data points
LS: Ni=1=Xi
SS: Ni=1=Xi2CF = (5, (16,30),(54,190))(3,4)
(2,6)
(4,5)
(4,7)
(3,8)
- 20. CF TreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB = 7
L = 6RootNon-leaf nodeLeaf nodeLeaf node
- 21. CURE (Clustering Using REpresentatives )CURE: proposed by Guha, Rastogi & Shim, 1998
Stops the creation of a cluster hierarchy if a level consists of k clusters
Uses multiple representative points to evaluate the distance between clusters, adjusts well to arbitrary shaped clusters and avoids single-link effect
- 22. Drawbacks of Distance-Based MethodDrawbacks of square-error based clustering method
Consider only one point as representative of a cluster
Good only for convex shaped, similar size and density, and if k can be reasonably estimated
- 23. Cure: The AlgorithmDraw random sample s.
Partition sample to p partitions with size s/p
Partially cluster partitions into s/pq clusters
Eliminate outliers
By random sampling
If a cluster grows too slow, eliminate it.
Cluster partial clusters.
Label data in disk
- 24. Data Partitioning and Clusterings = 50
p = 2
s/p = 25xxxyyyyxyxs/pq = 5
- 25. Cure: Shrinking Representative PointsShrink the multiple representative points towards the gravity center by a fraction of .
Multiple representatives capture the shape of the clusterxyxy
- 26. Thank you !!!
