文档介绍：可伸缩的聚类算法
BIRCH
BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies): 利用层次方法的平衡迭代归约和聚类
由Zhang, Ramakrishnan和Livny 提出(SIGMOD’96)
两个重要概念
聚类特征(Clustering Feature, CF)
聚类特征树(Clustering Feature Tree, CF树)
聚类特征
聚类特征(CF)是一个三元组,给出对象子类的信息的汇总描述
设某个子类中有N个d维的点或对象{oi},则该子类的CF定义如下
CF=<N,LS,SS>
其中, N是子类中的点数(0阶矩);
是N个数据点的线性和(1阶矩);
是N个数据点的平方和(2阶矩)
2017/8/28
数据挖掘导论
2
聚类特征
Clustering Feature: CF = <N, LS, SS>
N: 数据点数目
LS: Ni=1Xi
SS: Ni=1Xi2
CF = <5, (16,30),(54,190)>
(3,4)
(2,6)
(4,5)
(4,7)
(3,8)
2017/8/28
数据挖掘导论
3
BIRCH的CF树
聚类特征
从统计学的观点来看,聚类特征是对给定子类统计汇总: 子类的0阶、1阶和 2阶矩( moments )
记录了计算聚类的关键度量, 并有效地利用了存储, 因为它汇总了关于子类的信息,而不是存储所有的对象
CF 树是高度平衡的树, 它存储了层次聚类的聚类特征
树中的非叶节点有后代或“孩子”
非叶节点存储了其孩子的CF的总和, 即汇总了关于其孩子的聚类信息
CF树有两个参数----影响CF树的大小
分支因子B: 定义非树叶节点的孩子的最大个数
阈值T: 给出了存储在树的叶子节点中的子类的最大直径
2017/8/28
数据挖掘导论
4
BIRCH (续)
BIRCH增量地构造一棵 CF 树(Clustering Feature Tree) , CF树是一个层次数据结构, 用于多阶段聚类
阶段 1: 扫描 DB , 建立一棵初始的存放在内存的 CF树(数据的多层压缩, 试图保留数据内在的聚类结构)
阶段 2: 使用某种聚类算法对CF树的叶节点进行聚类.
在阶段一, 随着对象被插入, CF树被动态地构造.
一个对象被插入到最近的叶子条目(子聚类).
如果在插入后存储在叶子节点中的子类的直径大于阀值, 那么该叶子节点(可能还有其他节点)被分裂.
新对象插入后. 关于该对象的信息向着树根传递----类似于B+树构建中的插入和节点分裂
通过修改阀值, CF树的大小可以改变
2017/8/28
数据挖掘导论
5
BIRCH (续)
重建过程从旧树的叶子节点建造一个新树. 这样, 重建树的过程不需要重读所有的对象----建树只需读一次数据
在阶段二被采用任何聚类算法, 例如典型的划分方法
BIRCH的性能
支持增量聚类
线性可伸缩性: 计算复杂性O(n), 单遍扫描, 附加的扫描可以改善聚类质量
较好的聚类质量
缺点
只能处理数值数据
CF树节点不是用户所认为的自然簇, 当簇不是球形的时, BIRCH不能很好地聚类
对数据的输入次序敏感
2017/8/28
数据挖掘导论
6
CURE: 基本思想
CURE(Clustering Using REpresentative)
使用簇中的多个代表点来表示一个簇
这些点捕获了簇的几何形状
代表点相对分散: 第一个代表点选择离簇中心最远的点, 而其余的点选择离所有已经选取的点最远的点
代表点的个数是一个参数, 业已发现10或更大的值效果很好
一旦选定代表点,它们就以因子向簇中心收缩
例如, 对于= , 一个到中心的距离为10个单位的代表点将移动3个单位
使用一种凝聚层次聚类方案进行实际的聚类
两个簇之间的距离是任意两个代表点(在它们向它们代表的中心收缩之后)之间的最短距离
= 0, 等价于基于质心的层次聚类
= 1, 与单链层次聚类大致相同
2017/8/28
数据挖掘导论
7
CURE: 基本思想
在聚类过程的两个不同阶段删除离群点
第一个阶段一般出现在簇的个数是原来点数的1/3时删除增长缓慢的簇
如果一个簇增长缓慢, 则意味它主要由离群点组成
第二个离群点删除阶段出现在簇的个数达到K(期望的簇个数)的量级时. 此时, 小簇又被删除
CURE使用了两种技术来加快聚类过程
第一种技术: 取随机样本, 并在抽样的数据点上进行层次聚类, 随后是最终扫描, 将数据集中剩余的点指派到簇中
第二种技术: 划分样本数据, 然后聚类每个划分中的点
2017/8/2