TWOSTEP两步法聚类详解分析.doc

TWOSTEP两步法聚类详解分析 系统平台部 经营分析组 2012-10-10 第一步完成简单数据处理，以便将原始输入数据压缩为可管理的子聚类集合。第二步使用层级聚类方法将子聚类一步一步合并为更大的聚类。TwoStep 具有一个优点，就是能够为训练数据自动估计最佳聚类数。 第一步用到的算法-BIRCH：Balanced Iterative Reducing and Clustering using Hierarchies 优点：适合大的数据集，最小化运行时间和数据扫描 在一个类中，给定N个d维的数据点：{}，其中i=1,2,3….,N,则 CF={N,LS,SS} CF（Clustering Feature）：包含簇信息的三元组，其中N是类中数据点的数量，LS是N个数据点的线性求和，SS是N个数据点的平方和，一个CF向量有足够的信息去计算相似度。 可以直接求和：CF1 + CF2 = (N1+N2, LS1+LS2, SS1+SS2) 相似度量：给定一个实例{}，我们定义如下 图心 半径（每个实例跟图心的平均距离） 直径（在一个类中，成对实例的平均距离）  每个中间节点至多有B个子节点 每个叶节点至多有L个CF簇，每个簇都满足阈值T 节点大小由数据空间维度和输入参数P决定 一个CF树有三个参数： B=分支系数，中间节点的最大子节点数量 T=叶节点中的类的半径或直径的阈值 L=叶节点的最大CF簇数量 CF树的插入算法： 1、从根节点开始，在根节点中查找最靠近数据点的CF簇，移动到子节点并重复该处理直到发现一个最靠近的叶节点CF簇。 2、在叶节点中： A、如果这一点能被安置在类中，则更新簇； B、如果本次添加超过阈值T，分裂该簇； C、如果分裂导致簇超过阈值L，则分裂叶节点； D、如果它的父节点对应的子节点超过阈值B，则分裂父节点。 3、从根节点到叶节点更新CF簇信息以适应这个数据点。 图表说明： 一、如果本次添加数据点超过了簇的阈值T，独立为新类 二、如果一个叶节点的分支系数不能超过3，则中间节点LN1分裂。 三、如果一个中间节点的分支系数不能超过3，则根节点将分裂，CF树的高度增加1. 阶段1： 选择初始阈值，依照插入算法，开始一个一个的插入数据点 如果上面的插入过程中，CF树的大小超出了可用内存的大小，则增大阈值 依照变换算法，将部分建立的树数转换为新的树 重复上面的步骤直到整个数据集都被扫描过并已创建了一个完整的树。 阶段2： 第一阶段和第三阶段的桥梁 通过增大阈值构建一个更小的CF树 阶段3： 应用全局聚类算法，对叶节点提供的子类进行聚类 提高聚类质量 阶段4： 扫描整个数据集，给每个数据点打上标签 例子： 图中一个BTNode最多包含4个CFNode，每个CFNode就相当于一个簇，而每个BTNode里面的所有CFNode相当于一个大簇。当插入一个新纪录时，是从底往上修改的，所以叶子节点是等深的，用BLeafNode将所有叶子节点窜连起来，方便挖掘这颗B-树。还是用例子说明吧。先插入第一条记录，用该纪录创建一个CFNode，再用该CFNode创建一个BTNode作为根节点。图如下： 从第二条记录起就具有一般性了，插入第二条记录时，用该条记录创建一个临时CFNode（记cft）,然后从根节点开始，看cft和根节点的哪个CFNode距离最近（当然目前只有一个CFNode),根据这个CFNode找到它的子BTNode（当然这里没有），一直这样下去，直到叶子节点（当然这里根节点也就是叶子节点）。假如cft和找到的最近的BTNode（记bt）,的最近的那个CFNode（记cfp）的距离是d,如果d小于给定的阈值minDis，则将cft和cfp合并，然后从该叶子节点向上更新各个BTNode的信息直到根节点，更新的方法是将cft的信息合并到父节点的各个CFNode中。如果d大于给定的阈值，但是bt的CFNode小于给定的阈值M，则将cft作为bt的一个新CFNode，然后依然从该叶子节点向上更新各个BTNode的信息直到根节点。如果bt的cfp大于给定的阈值M，则只能将bt分裂成两个BTNode,然后将原BTNode（也就是bt）所对应的父节点（记r）对应的CFNode分裂成两个CFNode,如果那时r中的CFNode数目也大于M则继续向上分裂，否则向上更新。 第一阶段： 扫描所有数据，建立初始化的CF树 把稠密数据分成簇，稀疏数据作为孤立点对待 第二阶段： 可选的 阶段3的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求 在阶段1的基础上，建立一个更小的CF树 第三阶段： 补救由于输入顺序和页面大小带来的分裂 使用全局/半全局算法对全部叶节点进行聚类 现有的聚类算法可以被改进，用于簇与簇之间的聚类 把中心点作为