Abstract: Clustering is a common technique for data analysis, and has been widely used in many practical areas. However, in many practical applications, there are some reasons to cause the missing values in real data sets such as difficulties and limitations of data acquisition and random noises. Most of clustering methods can’t be used to deal with incomplete data sets for clustering analysis directly. For this reason, this paper proposes a three-way decision clustering algorithm for incomplete data based on q-nearest neighbors. Firstly, the algorithm finds the q-nearest neighbors for an object with missing values, and the missing value is filled by the average value of q-nearest neighbors. Secondly, it uses the clustering method based on density peaks for the complete data set to obtain the clustering result. For the data object with uncertainty in each cluster, it is designed to the boundary region of a cluster using the three-way decision theory. The three-way decision with interval sets naturally partitions a cluster into three regions as the positive region, boundary region and negative region, which has the advantage of dealing with soft clustering. The experimental results on some UCI data sets and synthetic data sets show preliminarily the effectiveness of the proposed algorithm.

Key words: incomplete data, three-way decision clustering, q-nearest neighbors

摘要： 聚类是数据挖掘的重要技术之一，在许多实际应用领域，由于数据获取限制，数据误读，随机噪音等原因会造成大量的缺失数据，形成数据集的不完备性，而传统的聚类方法无法直接对这类数据集进行聚类分析。针对数值型数据，提出了一个基于三支决策的不完备数据聚类方法。首先找到不完备数据对象的q个近邻，使用q个近邻的平均值填充缺失的数据；然后在“完备的”数据集上使用基于密度峰值的聚类方法得到簇划分，对每个簇中含有不确定性的数据对象，使用三支决策的思想将其划分到边界域中。三支决策聚类结果采用区间集形式表示，通常一个簇被划分成正域、负域和边界域部分，可以更好地描述软聚类结果。在UCI数据集和人工数据集上的实验结果展示了算法的有效性。

关键词: 不完备数据, 三支决策聚类, q近邻