樊仲欣 王兴 苗春生

摘 要：为解决利用层次方法的平衡迭代规约和聚类（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的限制，每个簇只能包含数量相近的数据对象。……