聚类分析基本概念和方法

无论使用凝聚方法还是只用分类方法，一个核心问题是 度量两个簇之间的距离，其中每个簇一般是一个对象集。 4个广泛采用的簇间距离，也称链接度量(linkage measure)： dist min(Ci, Cj ) min {| p p ' |} 最小距离： pCi , p 'Cj
最大距离：
10.3：层次方法
层次聚类方法(hierarchical clustering method): 将数据对象组成层次结构或簇的“树”。 对组织在层次结构中的数据进行汇总或特征化。 层次划分可以递归继续，直到达到期望的粒度。 层次结构对于数据可视化特别有用。 一种提高层次方法聚类质量的有希望的方向是集成层 次聚类与其他聚类技术，形成多阶段聚类。
10.3.4：Chameleon：使用动态的建模的多阶段层次聚类
Chameleon(变色龙)是一种层次聚类算法，它采用动态建 模来确定一对簇之间的相似度。在Chameleon中，簇的相似 度依据如下两点评估： 簇中对象的连接情况 簇的邻近性 图10.10解释Chameleon如何运作。
10.3.4：Chameleon：使用动态的建模的多阶段层次聚类 Chameleon根据两个簇Ci和Cj的相对互连度RI(Ci,Cj)和 相对接近度RC(Ci,Cj)来决定它们的相似度： 两个簇Ci和Cj的相对互连度RI(Ci,Cj)定义为Ci和Cj之间 的绝对互连度关于两个簇Ci和Cj的内部互连度的规范化 | EC | C , C || ，即 RI (Ci, Cj )
i j

两个簇Ci和Cj的相对接近度RC(Ci,Cj)定义为Ci和Cj之间 的绝对接近度关于两个簇Ci和Cj的内部互连度的规范化 S EC{Ci , Cj} ，定义如下： RC (Ci, Cj )
| Ci | | Ci | S ECCi S ECCj | Ci | | Cj | | Ci | | Cj |
考虑一个n个d维的数据对象或点的簇。聚的聚类特征 (Clustering Feature, CF)是一个3维向量，汇总了对 象簇的信息，定义如下：
CF n, LS , SS
其中，LS是n个点的线性和(即 方和(即 x )。
n i 1 2 i
x )，而SS是数据点的平
i i 1
n
10.3.1：凝聚的与分裂的层次聚类
层次聚类方法可以是凝聚的或分裂的，取决于层 次分解是自底向上（合并）还是以自顶向下（分裂） 方式形成。
凝聚的层次聚类方法使用自底向上的策略。 分裂的层次聚类方法使用自顶向下的策略。
在凝聚或分裂聚类中，用户都可以指定期望的簇 个数作为终止条件。
10.3.1：凝聚的与分裂的层次聚类
最近邻聚类算法(nearest-neighbor clustering algorithm) 单链接算法(single-linkage algorithm) 最小生成树算法(minimal spanning tree algorithm) 最远邻聚类算法(farthest-neighbor clustering algorithm) 全连接算法(complete-linkage algorithm) 例10.4
1 (| ECCi | | ECCj |) 2
10.3.5：概率层次聚类
算法的层次聚类方法使用连接度量，往往使得聚 类容易理解并且有效。它们广泛用在许多聚类分析应 用中。然而，算法的层次聚类方法也有一些缺点。 为层次聚类选择一种好的距离度量常常是困难的 为了使用算法的方法，数据对象不能有缺失的 属性值 大部分算法的层次聚类方法都是启发式的，在 每一步局部地搜索好的合并/划分。 因此，结果聚类层次结构的优化目标可能不清晰。
10.3.3 BIRCH：使用聚类特征树的多阶段聚类
BIRCH 使用聚类特征来概括一个簇 使用聚类特征树(CF-树)来表示聚类的层次结构 这些结构帮助聚类方法在大型数据库甚至在流数据库中 取得好的速度和伸缩性 这些结构使得BIRCH方法对新对象增量或动态聚类也非 常有效
10.3.3 BIRCH：使用聚类特征树的多阶段聚类
10.3.3 BIRCH：使用聚类特征树的多阶段聚类
平衡迭代归约和聚类(Balanced Iterative Reducing and Clustering using Hierarchies, BIRCH): 是为大量数值数据聚类设计的 将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的 其他聚类算法(在其后的宏聚类阶段)集成在一起 克服了凝聚聚类方法所面临的两个困难 可伸缩性 不能撤销先前步骤所做的工作
凝聚的层次聚类算法AGNES(Agglomerative NESting)； 分裂的层次聚类算法DIANA(Divisive ANAlysis)； 单链接(single-linkoge)方法； 树状图的树形结构来表示层次聚类的过程。 详情见例10.3
10.3.2：算法方法的距离度量
wenku.baidu.com
聚类特征本质上是给定簇的统计汇总。使用聚类特征 ，我们可以很容易地推导出簇的许多有用的统计量。例如 ，簇的型心X0、半径R和直径D。
例10.5
10.3.3 BIRCH：使用聚类特征树的多阶段聚类
BIRCH采用了一种多阶段聚类技术：数据集的单编扫描 产生一个基本的好聚类，而一或多遍的额外扫描可以进一 步地改进聚类质量。它主要包括两个阶段: 阶段一：BIRCH扫描数据库，建立一棵存放于内存的初始 CF-树，它可以被看做数据的多层压缩，试图保留数据的 内在聚类结构。 阶段二：BIRCH采用某个(选定的)聚类算法对CF树的叶节 点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇 合并为更大的簇。
均值距离： 平均距离：
dist max(Ci, Cj ) max {| p p ' |}
pCi , p 'Cj
distmean(Ci, Cj ) | mi mj |
1 distavg (Ci, Cj ) | p p'| nn i j pCi , p 'Cj
10.3.2：算法方法的距离度量