聚类分析基本概念和方法.pptx

《

聚类分析基本概念和方法

10、3、1:凝聚得与分裂得层次聚类

层次聚类方法可以就是凝聚得或分裂得，取决于层次分解就是自底向上(合并)还就是以自顶向下(分裂)方式形成。

●凝聚得层次聚类方法使用自底向上得策略。

●分裂得层次聚类方法使用自顶向下得策略。

在凝聚或分裂聚类中，用户都可以指定期望得簇

个数作为终止条件。

10、3、1:凝聚得与分裂得层次聚类

凝聚得层次聚类算法AGNES(AgglomerativeNESting);

分裂得层次聚类算法DIANA(DivisiveANAlysis);

单链接(single-linkoge)方法；

树状图得树形结构来表示层次聚类得过程。详情见例10、3

10、3、2:算法方法得距离度量

无论使用凝聚方法还就是只用分类方法，一个核心问题就是度量两个簇之间得距离，其中每个簇一般就是一个对象集。

4个广泛采用得簇间距离，也称链接度量(linkagemeasure):

最小距离：

最大距离：

均值距离：distmean(Ci,Cj)=|mi-mj|

10、3、2:算法方法得距离度量

最近邻聚类算法(nearest-neighborclustering

algorithm)

单链接算法(single-linkagealgorithm)

最小生成树算法(minimalspanningtreealgorithm)

最远邻聚类算法(farthest-neighborclustering

algorithm)

全连接算法(plete-linkagealgorithm)

例104

10、3、3BIRCH:使用聚类特征树得多阶段聚类

平衡迭代归约和聚类(BalancedIterativeReducingandClusteringusingHierarchies,BIRCH):

就是为大量数值数据聚类设计得

将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样得其她聚类算法(在其后得宏聚类阶段)集成在一起

克服了凝聚聚类方法所面临得两个困难

√可伸缩性

√不能撤销先前步骤所做得工作

家

10、3、3BIRCH:使用聚类特征树得多阶段聚类

BIRCH使用聚类特征来概括一个簇

今使用聚类特征树(CF-树)来表示聚类得层次结构

→这些结构帮助聚类方法在大型数据库甚至在流数据库中取得好得速度和伸缩性

这些结构使得BIRCH方法对新对象增量或动态聚类也非常有效

10、3、3BIRCH:使用聚类特征树得多阶段聚类

考虑一个n个d维得数据对象或点得簇。聚得聚类特征(ClusteringFeature,CF)就是一个3维向量，汇总了对象簇得信息，定义如下：

CF=n,LS,SS

其中，LS就是n个点得线性和(即,而SS就是数据点得

平方和(

聚类特征本质上就是给定簇得统计汇总。使用聚类特征，我们可以很容易地推导出簇得许多有用得统计量。例如，簇得型心X。、半径R和直径D。

例I0:5

10、3、3BIRCH:使用聚类特征树得多阶段聚类

BIRCH采用了一种多阶段聚类技术：数据集得单编扫描位生一个基本得好聚类，而一或多遍得额外扫描可以进一步地改进聚类质量。她主要包括两个阶段：

●阶段一：BIRCH扫描数据库，建立一棵存放于内存得初始CF-树，她可以被看做数据得多层压缩，试图保留数据得内在聚类结构。

●阶段二：BIRCH采用某个(选定得)聚类算法对CF树得叶节点进行聚类，把稀疏得簇当做离群点删除，而把稠密得簇合并为更大得簇。

10、3、4:Chameleon:使用动态得建模得多阶段层次聚类

Chameleon(变色龙)就是一种层次聚类算法，她采用动态

建模来确定一对簇之间得相似度。在Chameleon中，簇得相似度依据如下两点评估：

●簇中对象得连接情况

●簇得邻近性

●图10、10解释Chameleon如何运作。

大家有疑问的，可以询问和交流

可以互相讨论下，但要小声点

候

10、3、4:Chameleon:使用动态得建模得多阶段层次聚类

Chameleon根据两个簇C:和Cj得相对互连度RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定她们得相似度：

口两个簇Ci和Cj得相对互连度RI(Ci,Cj)定义为Ci和Cj之间得绝对互连度关于两个簇Ci和Cj得内部互连度得规范化，即

●两个簇Ci和Cj得相对接近度RC(Ci,Cj)定义为Ci和Cj之间得绝对接近度关于两个簇Ci和Cj得内部互连度得规范化，定义如下：