论文部分内容阅读
聚类分析或称聚类,作为一种无监督数据挖掘方法,根据设定的测量方法,允许我们将类似样本划分到同一类簇中。它有助于我们识别数据元素之间的模式,揭示了数据对象之间的关联,并有助于发现隐藏的数据结构。由于聚类的诸多优点,它已经广泛地应用到多个领域如:机器学习、模式识别、图像分析、信息检索、生物信息学、数据压缩、计算机图形学等。聚类分析算法可以分为划分法(Partitioning Methods)、层次法(Hierarchical Methods)、基于密度的方法(density-based methods)、基于网格的方法(grid-based methods)以及基于模型的方法(Model-Based Methods)。但是,传统的聚类算法都是硬聚类算法即对于任意样本对象至多属于一个类簇,类与类之间没有交集,可见这样的划分标准过于苛刻。为了能更好地表示样本对象之间的数据结构,提出了软聚类算法如rough k-means(RKM)、rough-fuzzy k-means(RFKM)等。软聚类算法放宽了对聚类条件的限制,即任意的样本对象至少属于一个类簇,类簇与类簇之间允许有交集。其中三支聚类作为一种特殊的软聚类方法,融合了三支决策理论即任意类簇是由核心域和边界域组成,核心域中的样本确定属于该类簇而边界域中的样本可能属于该类簇。三支聚类方法充分考虑了那些无法确定类簇归属的样本对象,可以在一定程度上提高聚类结果的聚类精度,同时有效降低了决策风险。在现实生活中,由于数据获取困难、随机噪音、数据丢失、数据误读等原因造成了一些数据值的丢失。例如,作为机器学习领域中常用的UCI数据库中就有超过40%的数据集含有缺失数据,而重新获取这些缺失数据则需要花费较高的人力、物力、财力甚至是无法获取。统称这类含有缺失数据值的数据集为不完备数据集。目前,大多数聚类算法只能处理完备数据集而无法处理不完备数据集。因此本文不仅对如何实现不完备数据集的聚类问题进行了相关研究,同时也探讨了完备数据集的三支决策聚类问题。论文主要工作包括以下几个方面:(1)提出了一种基于k-means算法的改进的均值插补不完备数据聚类方法(KM-IMI)。首先,我们将指定的数据集按照特定的缺失率进行随机缺失得到相应的不完备数据集,将不完备数据集划分为两个互不相交的集合;然后,对于不包含缺失值的样本组成的集合使用k-means算法进行处理获得聚类结果;最后,对于包含缺失值得样本组成的集合根据聚类结果中各类簇的样本对象的属性均值进行填充,依据聚类中心的扰动分析方法寻找最优填充值,与此同时获得最终的聚类结果。通过有效性指标对UCI数据集的聚类结果进行评估,可以证明该方法的有效性。(2)借鉴KM-IMI算法,提出了一种基于投票式的不完备数据三支集成聚类方法。通过聚类集成的方法来处理数据集并获得多个基聚类结果;对多个聚类结果中的类簇做标签匹配;求取相同类簇标签的交集并将交集中的样本划分到对应类簇的核心域中;统计剩余样本对象的票数与所设定的阈值关系决定该样本属于类簇的核心域还是边界域;最后获得填充后的不完备数据集的三支聚类结果。(3)提出了基于三支决策理论的三支聚类模型(TWKM)。在TWKM模型中,使用重叠聚类获得聚类结果的上界(核心域和边缘域的并集),并使用扰动分析的方法将核心域从上界中分离出来。上界和核心域之间的差集被视为特定类簇的边界域。因此,获得了类簇的三支表示即三支聚类结果。同时,我们将谱聚类算法应用到TWKM模型上形成了三支谱聚类算法(TWSC)。通过计算TWKM模型以及TWSC算法聚类结果中核心域的Accuracy(ACC)、Davies-Bouldin Index(DBI)、Average Silhouette Coefficient(AS)等指数的值。实验结果表明,这种模型可有效改善聚类结果的结构,提高聚类精度。