基于连通距离和连通强度的BIRCH改进算法

樊仲欣 王兴 苗春生

摘 要：为解决利用层次方法的平衡迭代规约和聚类（BIRCH）算法聚类结果依赖于数据对象的添加顺序，且对非球状的簇聚类效果不好以及受簇直径阈值的限制每个簇只能包含数量相近的数据对象的问题，提出一种改进的BIRCH算法。该算法用描述数据对象个体间连通性的连通距离和连通强度阈值替代簇直径阈值，还将簇合并的步骤加入到聚类特征树的生成过程中。在自定义及iris、wine、 pendigits数据集上的实验结果表明，该算法比多阈值BIRCH、密度改进BIRCH等现有改进算法的聚类准确率更高，尤其在大数据集上比密度改进BIRCH准确率提高6个百分点，耗时降低61%。说明该算法能够适用于在线实时增量数据，可以识别非球形簇和体积不均匀簇，具有去噪功能，且时间和空间复杂度明显降低。

关键词：层次聚类;在线算法;BIRCH;聚类特征;聚类特征树

中图分类号：TP312

文献标志码：A

文章编号：1001-9081（2019）04-1027-05

Abstract： Focusing on the issues that clustering results of Balanced Iterative Reducing and Clustering using Hierarchies （BIRCH） depend on the adding order of data objects， BIRCH has poor clustering effect on non-convex clusters， and each cluster of BIRCH can only contain a similar number of data objects because of the cluster diameter threshold， an improved BIRCH algorithm was proposed. In this algorithm， the cluster diameter threshold was replaced by connectivity distance and intensity threshold which described the connectivity between the data objects， and cluster merging step was added into the generation of cluster feature tree. Experimental result on custom and iris， wine， pendigits datasets show that the proposed algorithm has higher clustering accuracy than the existing improved algorithms such as multi-threshold BIRCH and density-improved BIRCH; especially on large datasets， the proposed algorithm has accuracy increased by 6 percentage points and running time reduced by 61% compared to density-improved BIRCH. The proposed algorithm can be applied to online real-time incremental data processing and identify non-convex clusters and clusters with uneven volume， has denoising function and significantly reduces time-complexity and space-complexity.

Key words： hierarchical clustering; on-line algorithm; Balanced Iterative Reducing and Clustering using Hierarchies （BIRCH）; Cluster Feature （CF）; Cluster Feature Tree （CF Tree）

0 引言

利用層次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering using Hierarchies， BRICH）算法[1]是具有代表性的分层聚类算法，该算法的特点在于在线实时运行，计算流程简单，算法时间空间效率高，且可识别噪声。

该算法通过构建一个聚类特征树（Cluster Feature Tree， CF Tree），树中每个节点的聚类特征向量如下：CF=（N，LS，SS）

其中：N是簇中对象数目;LS是N个对象线性和∑Ni=1xi;SS是N个对象平方和∑Ni=1xi2。

合并两个簇只需要两个聚类特征向量算术相加即可，而计算簇距离、簇直径只需要用到（N，LS，SS）这三个值就足够了。但该算法的缺点在于结果依赖于数据对象的加入顺序，

对非球状的簇和对高维数据聚类效果不好，而且受簇直径阈值T的限制，每个簇只能包含数量相近的数据对象。

在最初的BIRCH算法的基础上，后期有不少学者对其进行了改进。邵峰晶等[2-3]提出了动态阈值及多阈值T的方法，解决了各簇的数据对象数量差距大时使用统一T值导致的问题，并引入了分割因子的概念消除了簇分裂中的不确定性。仰孝富[4]提出了文本聚类算法TCBIBK（Text Clustering algorithm Based on Improved BIRCH and K-nearest neighbor），在BIRCH聚类前先做K近邻划分的数据预处理，以提高聚类精度。曾晓迪等[5-6]则采用了二次聚类的办法，在BIRCH的聚类基础上再对各簇用K中心点（K-mediods）[7]、K均值（K-means）[8]等算法进行聚类，实现了发现任意形状簇的功能目标。韦相等[9-10]为了解决非球形簇的聚类问题，直接改进了BIRCH算法，先建立起多阈值的多棵聚类特征树代表各个簇，再合并树，用具有噪声的基于密度的聚类（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）方法[11]、高斯混合模型（Gaussian Mixture Model， GMM）[12]、K-means或谱聚类（Spectral Clustering）[13-14]等方法进行全局聚类。

上述各种BIRCH聚类改进算法均存在一些问题：动态阈值和多阈值T的方法不能突破球形簇限制;聚类预处理和二次聚类方法则都是结合多种已有算法，并未对BIRCH算法进行本质性的提升，且不适用于在线实时数据;而建立多棵聚类特征树的方法其算法比较繁琐，时间空间复杂度高，且由于需要全局聚类，部分算法还需要根据具体应用选择聚类方式。

因此，本文提出一种改进的BIRCH算法（简称连通改进BIRCH），该算法使用描述数据对象个体间连通性的连通距离和连通强度阈值替代簇直径T，同时还将簇合并的步骤加入到聚类特征树的生成过程中，以解决上述问题。

1 算法原理

本文借鉴了DBSCAN中区域半径Eps和邻域对象数阈值MinPts的概念，对BIRCH算法进行了如下几点改进：1）将簇直径阈值T改为簇的连通距离阈值D和连通强度阈值I。

2）将聚类特征向量由CF=（N，LS，SS）改为CF=（N），同时在每个数据对象中增加一个数据项M，M为数据对象的模的平方。

3）每个新增的数据对象不再是先加入最近的簇再依据簇直径阈值分裂聚类特征树节点，而是直接依据连通距离D和连通强度I，将新加入的数据对象和已有的若干簇合并，或者将新数据对象直接作为新簇加入聚类特征树，再像BIRCH算法那样分裂节点最终生成聚类特征树。简而言之，就是将原来BIRCH算法的簇分裂变为簇先合并再分裂的算法。

1.1 连通距离阈值D和连通强度阈值I

定义1 连通距离。连通距离即两个簇之间最接近的数据对象的距离，该距离用欧氏距离：dis=（x1-y1）2+…+（xn-yn）2，x1x2…xn和y1y2…yn分别为两个数据对象的向量表示。

定义2 连通距离阈值。连通距离阈值即判断两个簇是否连通的阈值，如两个簇间的连通距离小于等于连通距离阈值则为连通的簇，反之则为不连通的簇。

定义3 连通强度。连通强度即连通距离阈值范围内的数据对象个数。

定义4 连通强度阈值。连通强度阈值即判断两个簇是否为强连通的阈值，如两个簇间的连通强度大于等于连通强度阈值则为强连通簇（或称为簇核），反之则为弱连通簇（或称为干扰点）。

使用连通距离阈值D和连通强度阈值I代替簇直径阈值T，该方法具有可以发现任意形状簇和排除干扰点干扰这两大优点。首先，使用连通距离只描述簇中数据对象个体间的连通性，而不像簇直径描述的是簇中数据对象的整体范围体积，因此可以通过该连通性发现任意形状簇，且适用于簇与簇数据对象数量差距大的情况。其次，现实情况中的数据集往往因为主观的和客观的各种原因而存在干扰点，使得数据的聚类达不到理想的效果，所以为了排除干扰，需要定义连通强度将簇中数据对象最密集的部位（即簇核）给筛选出来作为强连通簇，而被筛选掉的数据对象则是弱连通簇或干扰点，干扰点并不一定就是必须去除掉的噪点，因为在很多情况下干扰点确实是客观存在的，因此应将其作为簇的非簇核部分重新合并入簇中，但在合并入簇的过程中如果干扰点与簇核的距离大于连通距离阈值D，则可以确定此干扰点为噪点。

1.2 聚类特征向量融入到数据对象中

由于连通距离和连通强度描述的是数据对象个体间连通性的参数，因此BIRCH算法原有CF聚类特征向量中的LS和SS聚类特征（用于计算簇心和簇直径）便不再需要，取而代之的是计算簇与簇之间任意两个数据对象距离的参数，该参数在计算簇与簇最近距离时需要用到。

根据三角形余弦定理，已知两边边长AL和BL及两边夹角θ求第三边边长CL：

那么现以坐标原点O和向量a、b为三角形的三个顶点，则用向量c的模表示a和b间的距离，其值为：

其中：a、b为向量的模，由此公式可知只要有数据对象的模和内积就可以求出距离，因此在每个数据对象中增加一个数据项：模平方M=（a12+a22+…+an2）。该数据项可以优化距离的计算，每次加入新的數据对象时就算好M的值存储下来，后面计算任意数据对象到该数据对象的距离就主要计算一下内积就可以求出结果。

1.3 聚类特征树的簇先合并再分裂

簇分裂的算法和BIRCH相同，在此不再敷述，而增加的簇合并的算法结合连通距离作为簇聚类的限制参数，可以避免数据加入顺序随机导致的聚类结果随机。因为簇直径随着数据加入顺序的不同，其值的变化方式也是不同的，当其变化曲线为上凸形状时就有可能会将同一个簇的数据对象分割到不同簇中，而BIRCH算法的簇只能分裂不能合并，因此无法在加入一个可以连通各簇的数据对象时进行簇的合并，所以需要采取簇先合并然后再分裂节点生成聚类特征树的算法解决这个问题。

2 算法流程及实现

算法流程步骤分为三步（如图1，其中D为连通距离阈值，I为连通强度阈值）：步骤1 数据预处理及簇的合并生成。预处理除了要读取连通距离阈值D、连通强度阈值I、叶子节点分支因子L、非叶子节点分支因子B这四个预置聚类参数以外，还要不断地读取在线聚类数据，并在每次读取时对新加数据对象追加一个数据项M，M=数据对象的模的平方。

步骤2 筛选强连通簇插入聚类特征树，该步骤和BIRCH算法分裂节点生成聚类特征树的流程一样，在此不再赘述。

步骤3 弱连通簇并入强连通簇并输出聚类特征树，该步骤需要将先前筛选出的非簇核部分重新合并入簇中，合并的方式使用最近距离的概念，依次从弱连通簇的列表中找出距离聚类特征树底层各个簇核最近的一个弱连通簇，将其加入到最近距离的那个簇核之中，直到所有弱连通簇全部加入完毕为止，但是距离大于阈值D的弱连通簇为噪点不加入。最后，输出聚类特征树底层簇的数据对象数量N及各个数据对象，还有聚类特征树其余各层的N值及各层间的父子节点隶属关系，作为当前数据的在线聚类结果。

3 时间空间复杂度

对于BIRCH算法，其在给定数据占用内存空间为MEM时的空间复杂度为O（MEM），本文算法的空间复杂度为O（MEM+MEM/d），其中d表示数据维度。

BIRCH算法加入数据对象的时间复杂度为O（dNB（1+logBMP））[1]。

本文算法时间复杂度为O（BIRCH）+O（HN+kHN）+O（sn），其中：HN為已加入的数据对象个数，k为与新加数据对象距离在阈值D内的数据个数，sn为强连通簇所有数据对象个数。增加的O（HN+kHN）和O（sn）为图1步骤一和步骤三的时间复杂度，考虑到数据密集时k值会比较大，因此本文算法主要时间复杂度为O（BIRCH）+O（kHN）。

4 聚类应用

本文算法使用Windows7 64位专业版操作系统和Eclipse Luna Service Release 2（4.4.2）编程软件基于一台CPU Inter core i5-4570 3.2GHz，内存8GB的PC上实现。

为验证其有效性，使用五个数据集比较本文算法（连通改进BIRCH）与BIRCH以及多阈值BIRCH[2]、密度改进BIRCH[9]这四种在线实时运行算法的聚类结果。数据集1为自定义数据集：2维3050个数据对象，呈大小簇分布，带有噪点;数据集2为自定义数据集：2维400个数据对象，呈环形和圆形分布;数据集3为iris数据集：4维150个数据对象;数据集4为wine均一化后数据集：13维178个数据对象;数据集5为pendigits数据集：16维10992个数据对象。最后三组数据集均来源于加州大学欧文分校机器学习库（University of California Irvine Machine Learning Repository）[15]。在iris、wine和pendigits数据集中，每个数据点的类标签都是已知的，因此可以充分利用准确率来评价算法的聚类质量。

令AD表示数据集中的数据个数，CD表示AD中被正确划分的数据个数，则准确率为Correct_rate=CD/AD*100%。

从图2可看出，对于具有大小簇以及包含噪点的非球形数据集1：BIRCH算法无法分割出大小簇及噪点;多阈值BIRCH算法虽然分割出了大小簇，但由于其识别非球形簇的能力很有限，所以图中的弧形簇被分割了开来且不能识别噪点;密度改进和连通改进BIRCH算法则解决了这些问题，可以分割大小簇，识别弧形簇，以及去噪点。图3的数据集2含有更加不易识别的环形簇，但密度改进和连通改进BIRCH算法依旧表现良好，可以将环形簇分割出来，而多阈值BIRCH算法则表现一般，BIRCH算法效果最差。值得一提的是，上述BIRCH和多阈值BIRCH算法的聚类结果具有一定随机性，因为其结果依赖于数据的加入先后顺序，而密度改进和连通改进BIRCH算法则解决了这一问题。

使用UCI数据集对上述四种BIRCH聚类算法进行测试，结果如表1，其中：参数B（非叶子节点分支因子）与L（叶子节点分支因子）对所有算法及数据集的取值均为2，表中仅列出取值不一样的参数。

从表1可看出：BIRCH算法耗时最短，但在大数据集上的准确率也是最低的;多阈值BIRCH准确率有所提高;密度改进BIRCH和连通改进BIRCH则准确率提升比较明显但同时耗时也增加不少，而其中连通改进BIRCH算法则在大数据集上明显更优一些，其在pendigits数据集上的运行准确率比密度改进BIRCH提高6个百分点，且耗时减少55.2s，降低了密度改进BIRCH算法61%的耗时量。连通改进BIRCH算法在功能上和密度改进BIRCH算法接近，但是耗时明显较短。原因如下：密度改进BIRCH由于构建了多棵聚类特征树所以首先在空间复杂度上明显高于连通改进BIRCH。其次，密度改进BIRCH中用Eps和MinPts代替了聚类特征树的簇直径T，而加入数据对象时“代表点密度增加，当它变成核心点后，还要扫描所有核心点聚类特征树，归入邻近核心点”[9]，

这就相当于连通改进算法流程（见图1）的步骤一中n>I为否的情况（其耗时等于本文算法的主要增加时间复杂度O（kHN）），考虑到两种算法前后增加的计算过程，尤其是密度改进算法还有多次合并多棵聚类特征树的分裂节点、更新聚类特征值等较为复杂的操作，所以可见连通改进BIRCH算法耗时更短且实现更为简单。

5 结语

本文针对BIRCH及其现有改进算法在不能在线实时运行、只能聚类球形簇、聚类结果依赖于数据对象的添加顺序、每个簇只能包含数量相近的数据对象、算法时间空间复杂度高等方面存在的一个或若干个问题，提出了可以解决上述问题的改进算法。本文连通改进BIRCH算法融合了DBSCAN算法区域半径和邻域对象数阈值的概念，用其代替簇直径阈值T，并且采用簇先合并再分裂的方法，提高了BIRCH算法的适用范围和运行性能。时间空间复杂度及实验结果表明，该算法在损失有限的运算时间和存储空间的前提下可以有效地提高聚类准确率，并且在处理大数据集时依然具有不错的性能表现。

参考文献（References）

[1] ZHANG T， RAMAKRISHNAN R， LINVY M. BIRCH： an efficient data clustering method for very large databases[C]// SIGMOD 1996： Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1996： 103-114.

[2] 邵峰晶， 张斌， 于忠清.多阈值BIRCH聚类算法及其应用[J]. 计算机工程与应用， 2004， 41（12）： 174-176. （SHAO F J， ZHANG B， YU Z Q. BIRCH clustering algorithm with mult_threshold[J]. Computer Engineering and Applications， 2004， 41（12）： 174-176.）

[3] 蒋盛益， 李霞. 一种改进的BIRCH聚类算法[J]. 计算机应用， 2009， 29（1）： 293-296. （JIANG S Y， LI X. Improved BIRCH clustering algorithm[J]. Journal of Computer Applications， 2009， 29（1）： 293-296.）

[4] 仰孝富.基于BIRCH改进算法的文本聚类研究[D]. 北京： 北京林业大学， 2013： 22-29. （YANG X F. Research of text clustering based on improved BIRCH[D]. Beijing： Beijing Forestry University， 2013： 22-29.）

[5] 曾晓迪.一种基于K-mediods改进BIRCH的大数据聚类方法[D]. 昆明： 云南财经大学， 2014： 27-31. （ZENG X D. A big data clustering method based on K-mediods improved BIRCH[D]. Kunming： Yunnan University of Finance and Economics， 2014： 27-31.）

[6] 邹杰涛， 赵方霞， 汪海燕.基于加权相似性的聚类算法[J]. 数学的实践与认知， 2011， 47（16）： 118-124. （ZOU J T， ZHAO F X， WANG H Y. Clustering algorithm based on weighted similarity[J]. Mathematics in Practice and Theory， 2011， 47（16）： 118-124.）

[7] HUANG Z X. A fast clustering algorithm to cluster very large categorical data sets in data mining[EB/OL]. [2018-05-10]. http：//www.vladestivill-castro.net/teaching/kdd.d/readings.d/huang97 fast.pdf.

[8] MACQUEEN J. Some methods for classification and analysis of mul-tivariate observations[C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley： University of California Press， 1967， 1： 281-297.

[9] 韋相.基于密度的改进BIRCH聚类算法[J]. 计算机工程与应用， 2013， 49（10）： 201-205. （WEI X. Improved BIRCH clustering algorithm based on density[J]. Computer Engineering and Applications， 2013， 49（10）： 201-205.）

[10] MADAN S， DANA K J. Modified Balanced Iterative Reducing and Clustering using Hierarchies （m-BIRCH） for visual clustering[J]. Pattern Analysis and Applications， 2016， 19（4）： 1023-1040.

[11] ESTER M， KRIEGEL H， SANDER J， et a1. A density-based algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park， CA： AAAI Press， 1996： 226-231.

[12] AWWAD B， HASAN S， GAN J Q. Sequential EM for unsupervised adaptive Gaussian mixture model based classifier[C]// MLDM 2009： Proceedings of the 6th International Conference on Machine Learning and Data Mining in Pattern Recognition， LNAI 5632. Berlin： Springer， 2009： 96-106.

[13] LAUER F， SCHNORR C. Spectral clustering of linear subspaces for motion segmentation[C]// Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway， NJ： IEEE， 2009： 678-685.

[14] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： analysis and an algorithm[EB/OL]. [2018-05-10]. http：//papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.pdf.

[15] MERZC J， MERPHY P. UCI repository of machine learning data-bases[DB/OL]. [2018-03-19]. http：//archive.ics.uci.edu/ml/index.php.