一种面向增量数据的重叠聚类算法研究

Study on an Overlapping Clustering Algorithm for Incremental Data

摘要: 数据的在线聚类问题分为完全在线聚类和半在线聚类两种。而增量数据的聚类属于半在线聚类，是在已有数据聚类的基础上进行聚类。另外，由于大多数的聚类算法只会把一个数据点分配给唯一聚类，但很多现实环境的数据集都包含交叉重复信息，而重叠聚类允许一个数据点属于多个聚类。传统的重叠聚类方法overlapping k-means (OKM)作为对k-means的扩展，存在聚类效率低和对聚类中心初始化敏感的问题。为解决以上问题，本文提出一种面向增量数据的重叠k-means混合模型，其主要思想是利用KHM的输出对OKM方法的聚类中心进行初始化。该模型首先应用k调和均值算法与重叠k均值算法来对已有数据进行重叠聚类；然后迭代使用OKM算法对增量数据进行聚类，即k-harmonic means & iterative overlapping k-means混合算法(KHM-IOKM)，算法时间复杂度为$O\left(kn\right)$ 。实验结果显示：在仿真数据集和UCI真实数据集上与传统的OKM和KHM算法进行比较，该方法能够有效降低聚类中心初始化敏感的问题，并且相比于传统的聚类方法能获得更好的聚类效果。

Abstract: The online clustering problem of data is divided into two types: full online clustering and semi-online clustering. The clustering of incremental data belongs to semi-online clustering, which is based on existing data clustering. In addition, most clustering algorithms produce exclusive clusters, meaning that each data point can just belong to one cluster. In fact, a great many real-world datasets have inherently overlapping information, while the overlapping clustering methods allow one data point to belong to more than one cluster. The traditional overlapping clustering method is overlapping k-means (OKM). As an extension of the k-means algorithm, it has the problems of low clustering efficiency and sensitivity to the selection of the initial clustering center. In order to solve the above problems, in this study, we propose an overlapping k-means hybrid model for incremental data, whose main idea is to use the output of KHM to initialize the clustering center of the OKM method. The model first uses k-harmonic mean algorithm and overlapping k-means algorithm to overlap clustering existing data; then iteratively uses OKM algorithm to cluster incremental data, that is k-harmonic means & iterative overlapping k-means hybrid algorithm (KHM-IOKM), the time complexity is $O\left(kn\right)$ . By comparing with the traditional OKM and KHM algorithms on synthetic dataset and UCI real dataset, the experimental results demonstrate that the proposed method can effectively reduce the sensitivity of clustering center initialization and obtain better clustering than traditional clustering methods.