BIRCH算法分析

一birch算法BIRCH算法BIRCH（BalancedIterativeReducingandClusteringUsingHierarchies）全称是：利用层次方法的平衡迭代规约和聚类，采用了一种多阶段聚类技术，师层次聚类和其他聚类算法的集成。BIRCH是一种聚类算法，它最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。BIRCH算法重要的是引入了聚类特征和聚类特征树的概念，他们用于概括簇的描述。聚类特征（CF）CF是BIRCH增量聚类算法的核心，CF树中得节点都是由CF组成，一个CF是一个三元组，这个三元组就代表了簇的所有信息。给定N个d维的数据点{x1,x2,....,xn}，CF定义如下：CF=（N，LS，SS）其中，N是子类中节点的数目，LS是N个节点的线性和，SS是N个节点的平方和。CF例子假设簇C1中有三个数据点：（2,3），（4,5），（5,6），则CF1={3，（2+4+5,3+5+6）,（2^2+4^2+5^2,3^2+5^2+6^2）}={3，（11,14），（45,70）}，同样的，簇C2的CF2={4，（40,42），（100,101）}，那么，由簇C1和簇C2合并而来的簇C3的聚类特征CF3计算如下：CF3={3+4,（11+40,14+42）,（45+100,70+101）}={7，（51,56），（145,171）}簇的质心和簇的半径假如一个簇中包含n个数据点：{Xi}，i=1,2,3...n.，则质心C和半径R计算公式如下：C=(X1+X2+...+Xn)/n，（这里X1+X2+...+Xn是向量加）R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n簇半径表示簇中所有点到簇质心的平均距离。聚类特征树（CFtree）CFtree的结构类似于一棵B-树，它有两个参数：内部节点平衡因子B，叶节点平衡因子L，簇半径阈值T。树中每个节点最多包含B个孩子节点，记为（CFi，CHILDi），1=i=B，CFi是这个节点中的第i个聚类特征，CHILDi指向节点的第i个孩子节点，对应于这个节点的第i个聚类特征。例如，一棵高度为3，B为6，L为5的一棵CF树的例子如图所示：CF树的加入一棵CF树是一个数据集的压缩表示，叶子节点的每一个输入都代表一个簇C，簇C中包含若干个数据点，并且原始数据集中越密集的区域，簇C中包含的数据点越多，越稀疏的区域，簇C中包含的数据点越少，簇C的半径小于等于T。随着数据点的加入，CF树被动态的构建，插入过程有点类似于B-树。加入算法表示如下：(1)从根节点开始，自上而下选择最近的孩子节点(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点是，更新CF值否，是否可以添加一个新的元组是，添加一个新的元组否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到rootBIRCH算法流程整个算法的实现分为四个阶段：（1）扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点对待（2）这个阶段是可选的，阶段3的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求，所以此阶段在阶段1的基础上，建立一个更小的CF树（3）补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类4）这个阶段也是可选的，把阶段3的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签BIRCH的优势节省内在。叶子节点放在磁盘分区上，非叶子节点仅仅是存储了一个CF值，外加指向父节点和孩子节点的指针。快。合并两个两簇只需要两个CF算术相加即可；计算两个簇的距离只需要用到(N,LS,SS)这三个值足矣。一遍扫描数据库即可建立B树。可识别噪声点。建立好B树后把那些包含数据点少的MinCluster当作outlier。由于B树是高度平衡的，所以在树上进行插入或查找操作很快。缺点结果依赖于数据点的插入顺序。本属于同一个簇的点可能由于插入顺序相差很远而分到不同的簇中，即使同一个点在不同的时刻被插入，也会被分到不同的簇中。对非球状的簇聚类效果不好。这取决于簇直径和簇间距离的计算方法。对高维数据聚类效果不好。由于每个节点只能包含一定数目的子节点，最后得出来的簇可能和自然簇相差很大。BIRCH适合于处理需要数十上百小时聚类的数据，但在整个过程中算法一旦中断，一切必须从头再来。局部性也导致了BIRCH的聚类效果欠佳。当一个新点要插入B树时，它只跟很少一部分簇进行了相似性（通过计算簇间距离）比较，高的efficient导致低的effective。