层次聚类方法的改进--BIRCH
BIRCH(利用层次方法的平衡迭代归约和聚类)是一个综合的层次聚类方法,它用聚类特征和聚类特征树(CF)来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树,存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目,而阈值给出了存储在树的叶子节点中的子聚类的最大直径。
BIRCH算法的工作过程包括两个阶段:
阶段一:BIRCH扫描数据库,建立一个初始存放于内存的CF树,它可以被看作数据的多层压缩,试图保留数据内在的聚类结构。随着对象的插入,CF树被动态地构造,不要求所有的数据读入内存,而可在外存上逐个读入数据项。因此,BIRTH方法对增量或动态聚类也非常有效。
阶段二:BIRCH采用某个聚类算法对CF树的叶结点进行聚类。在这个阶段可以执行任何聚类算法,例如典型的划分方法。
BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行较好的聚类,故该算法的计算复杂度是O(n),n是对象的数目。
1