TWOSTEP两步法聚类详解分析

1、TWOSTEP两步法聚类详解分析 系统平台部 经营分析组 2012-10-10 第一步完成简单数据处理，以便将原始输入数据压缩为可管理的子聚类集合。 第二步使用层 级聚类方法将子聚类一步一步合并为更大的聚类。TwoStep具有一个优点，就是能够为训练 数据自动估计最佳聚类数。 第一步用到的算法 -BIRCH： Bala need Iterative Reduci ng and Clusteri ng using Hierarchies 优点：适合大的数据集，最小化运行时间和数据扫描 在一个类中，给定 N个d维的数据点：，其中i=1,2,3 .,N,则 CF= N,L S,SS CF ( Clu

2、stering Feature):包含簇信息的三元组，其中N是类中数据点的数量，LS是N个数 据点的线性求和，SS是 N个数据点的平方和，一个CF向量有足够的信息去计算相似度。 可以直接求和：CF1 + CF2 = (N1+N2, LS1+LS2, SS1+SS2) .) .). .). 2 3 4 5 ? ? ? CF = (5:(16?30)?(54/190) XI/ V)/ 4 6 5 7 8 ? ? 5 ? 5 3 2 4 4 3 x(x fv /V zt cri = (4, (10,14), 84) CF3 = CF1 十 CF2 卜ig- 2. CF Example 相似度量：给定

3、一个实例 图心 ,我们定义如下 X0 = 半径（每个实例跟图心的平均距离） 直径（在一个类中，成对实例的平均距离） Rcral: nods Luf node CZ) CSD CD 每个中间节点至多有 B个子节点 每个叶节点至多有 L个CF簇，每个簇都满足阈值 T 节点大小由数据空间维度和输入参数P决定 一个CF树有三个参数： B=分支系数，中间节点的最大子节点数量 T=叶节点中的类的半径或直径的阈值 L=叶节点的最大CF簇数量 CF树的插入算法： 1、 从根节点开始，在根节点中查找最靠近数据点的CF簇，移动到子节点并重复该处理直到 发现一个最靠近的叶节点 CF簇。 2、在叶节点中： A、如果这

4、一点能被安置在类中，则更新簇； B、如果本次添加超过阈值 T,分裂该簇； C、如果分裂导致簇超过阈值 L,则分裂叶节点； D、 如果它的父节点对应的子节点超过阈值B,则分裂父节点。 3、从根节点到叶节点更新 CF簇信息以适应这个数据点。 图表说明： 、如果一个叶节点的分支系数不能超过3，则中间节点LN1分裂。 三、如果一个中间节点的分支系数不能超过3，则根节点将分裂，CF树的高度增加1. 阶段1: 选择初始阈值，依照插入算法，开始一个一个的插入数据点 如果上面的插入过程中，CF树的大小超出了可用内存的大小，则增大阈值 依照变换算法，将部分建立的树数转换为新的树 重复上面的步骤直到整个数据集都被

5、扫描过并已创建了一个完整的树。 阶段2 : 第一阶段和第三阶段的桥梁 通过增大阈值构建一个更小的CF树 阶段3: 应用全局聚类算法，对叶节点提供的子类进行聚类 提高聚类质量 阶段4: 扫描整个数据集，给每个数据点打上标签 Data . rJbdMl. 1 n#d illtii TriTTmi|iv Iniildinx 门 Iwi lihiiiitl CF irw1 Plid- (irpiioiiuL): CorKkitM iiiin iltvirahlr |制厲 by bulldJiiR a nioUa C F trev iiutllpf CK ini1、 Phase J: (npilonil

6、 and off line) : Chisler Roftning 例子: 明1血 * CFNodr tie 肚弭 !: BTN-jde 1 * :c x n k x X 1: BTXode ” B H X J 图中一个BTNode最多包含4个CFNode每个CFNode就相当于一个簇，而每个 BTNode里 面的所有CFNode相当于一个大簇。当插入一个新纪录时，是从底往上修改的，所以叶子节 点是等深的，用BLeafNode将所有叶子节点窜连起来，方便挖掘这颗B揺。还是用例子说明 吧。先插入第一条记录，用该纪录创建一个CFNode,再用该CFNode创建一个BTNode作为 根节点。图如下：

7、 CFNode rt BTOel 皿科I 从第二条记录起就具有一般性了，插入第二条记录时，用该条记录创建一个临时CFNode（记 eft），然后从根节点开始，看eft和根节点的哪个 CFNode距离最近（当然目前只有一个 CFNode）, 根据这个CFNode找到它的子BTNode （当然这里没有），一直这样下去，直到叶子节点（当 然这里根节点也就是叶子节点）。假如eft和找到的最近的 BTNode （记bt）,的最近的那个 CFNode（记cfp）的距离是d,如果d小于给定的阈值 minDis，则将eft和efp合并，然后从 该叶子节点向上更新各个BTNode的信息直到根节点，更新的方法是将

8、eft的信息合并到父 节点的各个 CFNode中。如果d大于给定的阈值，但是 bt的CFNode小于给定的阈值 M，则 将eft作为bt的一个新CFNode，然后依然从该叶子节点向上更新各个BTNode的信息直到 根节点。如果bt的efp大于给定的阈值 M，则只能将bt分裂成两个BTNode,然后将原BTNode （也就是bt）所对应的父节点（记r）对应的CFNode分裂成两个 CFNode如果那时r中的 CFNode数目也大于 M则继续向上分裂，否则向上更新。 第一阶段： 扫描所有数据，建立初始化的 CF树 序把稠密数据分成簇，稀疏数据作为孤立点对待 第二阶段： 可选的 阶段3的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求 必在阶段1的基础上，建立一个更小的 CF树 第三阶段： 补救由于输入顺序和页面大小带来的分裂 使用全局/半全局算法对全部叶节点进行聚类 希现有的聚类算法可