2003-5-19
BIRCH:
An Ecient Data Clustering Method for Very
Large Databases
主讲人：左子叶
2003-5-19
问题：
大数据集
I/O 开销
BIRCH
一次扫描
处理噪音
评估时间 / 空间效率
BIRCH/CLARANS 性能比较
2003-5-19
Introduction
聚类：识别稀疏 / 密集数据；发现数据及
的全局分布模式；可视化
两种数据： metric ， non-metric
给定 k 、 N ，距离度量函数，要寻找一
个数据集的分区，使函数最小化
2003-5-19
相关工作（ 1 ）
数据集太大，内存无法存放
基于概率的方法：
各个属性值的分布相互独立
簇的更新和存储开销很大：属性值的数目和属性的数目
非平衡树：性能与数据输入相关
基于距离的方法
所有数据点事先给定，反复扫描，同等对待
全局的度量方法，扫描所有的簇或数据点
全枚举
迭代最优：
从一个初始分区开始，计算所有可能使度量函数更小的点的移动
局部最优，初始敏感
2003-5-19
相关工作（ 2 ）
层次聚类 O(N
2
)
CLARANS
图的搜索
节点： K- 分区， K 个中心点；两个簇是邻居：只有一个中
心点不同
对当前节点，随机检查 maxneighbor 个邻居
如果有更好的邻居，移动到那个节点，继续
否则纪录当前节点为局部最优，重新选择一个新的节点
找到 numlocal 个局部最优为止，返回最佳的
与迭代最优方法相似
质量换时间： R* 树采样；相关数据点
- 1
- 2
前往页