文档介绍：层次聚类算法
层次聚类方法概述
层次聚类方法将数据对象组成一棵聚类树。
根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。
Date
2
层次聚类
层次聚类方法概述
凝聚的层次聚类：一种自底 {1，2，3，4} {5，6，7，8}
5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 终止
Date
17
层次聚类
层次聚类方法的改进
层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。
改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。
下面介绍3个改进的层次聚类方法BIRTH， ROCK和Chameleon。
Date
18
层次聚类
BIRCH算法
BIRCH （Balanced Iterative Reducing and Clustering）利用层次方法的平衡迭代归约和聚类
用聚类特征（CF）和聚类特征树来概括聚类描述。
该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。
Date
19
层次聚类
聚类特征（CF）
CF(Clustering Feature)：包含簇信息的三元组(N,LS,SS)，N：簇的数据点；LS：线性和； SS：平方和
假定在簇C1中有三个点(2,5),(3,2),(4,3)
聚类特征是：
CF1=<3,(2+3+4,5+2+3),(22+32+42,52+22+32)>
=<3,(9,10),(29,38)>
Date
20
层次聚类
聚类特征树
CF树是一个具有两个参数分支因子B和阈值T的高度平衡树。
分支因子B：非叶节点可以拥有的孩子数
阈值T：叶子节点中的子聚类的最大直径
Date
21
层次聚类
阶段一：扫描数据库，建立一个初始的CF树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，CF树被动态地构造，因此，BIRTH方法对增量或动态聚类也非常有效。
阶段二：采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法。
BIRCH算法
Date
22
层次聚类
ROCK
ROCK(Robust Clustering using linKs,使用连接的鲁棒聚类
大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中。这种“局部”方法很容易导致错误。例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并。
ROCK采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。
Date
23
层次聚类
ROCK
两个概念：近邻和链接
近邻：两个点pi和pj是近邻，如果sim(pi,pj)>=θ,sim是相似度函数，θ是指定的阈值
链接：两个点pi和pj的链接数定义为这两点的共同近邻个数。
由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒。
Date
24
层次聚类
ROCK
例：购物篮数据库包含关于商品a,b,…g的事物记录。簇C1涉及商品{a,b,c,d,e},簇C2涉及商品{a,b,f,g}
假设：只考虑相似度而忽略邻域信息。
C1中{a,b,c}和{b,d,e}之间的Jaccard系数

而C1中的{a,b,c}和C2中的{a,b,f}的Jaccard系数

说明：仅根据Jaccard系数，
很容易导致错误。
Date
25
层次聚类
另一方面，如果考虑链接数，可以成功地把这些事务划分到恰当地簇中。
例如：令θ=，则C2中的事务
{a,b,f}与{a,b,g}的链接数是5
而C2中的事务 {a,b,f}与C1中的事
务{a,b,c}之间的链接数是3.
因此，ROCK能够正确地区分出两个不同
的事务簇。
Date
26
层次聚类
Chameleon
利用动态建模的层次聚类算法。采用动态建模确定簇之间的相似度。
簇之间的相似度依据簇中对象的互连度和簇的邻近度，即如果两个簇的互连性都很高且它们又靠得很近则将其合并。
Date
27
层次聚类
变色龙算法的聚类步骤
Chameleon 算法首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇；
Date
28