BIRCH算法解析.ppt

BIRCHAn Efficient Data Clustering Method for Very Large Databases一种对大型数据库有效的聚类方法 主讲人:常贺 * 基本概念 聚类分析 是一个把数据对象（或观测)划分成子集的过程 簇 每个子集就是一个簇 聚类 由聚类分析产生的簇的集合称作一个聚类 层次聚类方法 将数据对象组成层次结构或簇的“树” 聚类特征 CF-树 * 聚类特征 聚类特征（Clusting Feature）是一个3维向量。对一个聚类中的所有d维数据对象 聚类的聚类特征的向量值定义为一个三元组的形式： CF=(n，LS,SS) 其中n为聚类中数据对象的数目。 LS为n个数据对象的线性和。 SS为n个数据对象的平方和。 * CF树 * * CF累加性定理 假设 和 为个不相交的聚类的CF向量。 合并这两个聚类为一个聚类是，那么新聚类的CF向量值为： * CF-树的创建过程 CF树的构造过程实际是一个数据对象的插入过程， 步骤： （1）找到恰当的叶子节点：从根结点开始递归往下，计算当前节点实体与要插入的数据对象之间的距离 ，寻找距离最小的那个路径，直到找到与该数据对象最接近的叶节点中的实体。 （2）比较计算出的距离是否小于阈值T，如果小于则当前节点实体吸收改数据对象；如果距离大于过等于阈值T,则转第三步。 * （3）判断当前实体所在的叶节点的实体个数是否小于L，如果是则直接将数据对象插入为该节点的新实体，否则需要分裂该叶节点。分裂的原则是寻找该叶节点中距离最远的两个实体并以这两个实体作为分裂后新的两个叶节点的起始实体，其他剩下的实体根据距离最小原则分配到这两个新的叶节点中，删除原叶节点并更新整个CF树。 当数据对象无法插入时，这个是很好需要提升阈值T并重新建树来吸收更多的叶节点实体，直到把所有数据点全部插入完毕。 * BIRCH Balanced Iterative Reducing and Clustering using Hierarchies (利用层次结构的平衡迭代归约和聚类) BIRCH算法：是使用聚类特征来概括一个簇，使用聚类特征树来表示聚类的层次结构，并基于距离的层次聚类算法。 考虑对于一个n个d维的数据对象集{ }。其中i=1,2.....n，该聚类簇的中心C和半径R定义为 其中 R为一个聚类簇中所有数据对象到聚类中心对象的平均距离。 * BIRCH算法描述 BIRCH算法试图利用有限可用的计算资源来生成最好的簇，给定有限的主存，一个重要的考虑是最小化I/O所需时间。BIRCH算法采用了一种多阶段聚类技术;数据集合的单遍扫描产生一个基本的好聚类，一遍或多遍的额外扫描可以用来进一步优化聚类质量。它主要包括两个阶段： 阶段一：扫描数据库，建立一颗存放于内存的初始CF树，它可以被看做数据的多层压缩，试图保留数据的内在聚类结构 阶段二：采用某个（选定的）聚类算法对CF树的叶节点进行聚类，把稀疏的簇当做离群点删除，而把稠密的簇合并为更大簇。 算法说明 在阶段一中，随着对象的插入，CF树被动态的构造。这样，该方法就支持增量聚类。一个对象被插入到最近的也叶条目（子簇）。如果在插入后，存储在叶子节点的子簇的直径大于阈值，则该叶节点和可能的其他节点被分裂。新对象插入后，关于该对象的信息向树根结点传递。通过修改阈值，CF树的大小可以改变。如果存储CF树需要的内存大于主存的大小，可以定义较大的阈值，并重新建立CF树。 重建过程从旧树的叶节点构建一颗新树。这样，重建术的过程不需要重读所有的对象或点。这类似于B+树构建中的插入和节点分裂。因此，为了建树只读一次数据。 *