论文部分内容阅读
聚类分析是将一组数据集按照一定规律或者需求进行分组,是数据挖掘的核心问题之一。聚类算法的研究与发展主要依托两方面:度量学习和算法设计。谱聚类算法和层次聚类算法是聚类算法发展过程中两类较为经典的算法,这两类算法虽然能够对数据做出较好的划分,然而本文在实际研究中发现,这两类算法依然存在一些问题:谱聚类算法受到度量方法中尺度因子的困扰,同时在聚类过程中做特征分解时计算量过大;层次聚类算法无法处理离群点数据及形状复杂的样本数据。因此本文基于传递距离、传递核映射和K-means二元属性的原理,针对以上存在的问题进行了深入研究。本文的主要工作包括:1.基于传递距离的谱聚类算法谱聚类算法的聚类结果常常需要受到度量中尺度因子的影响,同时通过欧式距离度量出的样本间相似性也不准确。针对上述情况,本文提出一种基于传递距离的谱聚类算法用于数据样本聚类。该算法主要通过改进传统谱聚类中的度量方式,用基于传递距离的度量方式代替原先谱聚类算法中度量样本间距离的度量方式,接着通过最小生成树算法构建传递矩阵,利用该传递矩阵做指数变换得到相似度矩阵。最后用得到的相似度矩阵构建拉普拉斯矩阵,求特征值特征向量完成对数据样本的聚类。在人工数据集以及UCI数据集上的实验结果表明,基于传递距离的谱聚类算法具有较好的鲁棒性和有效性。2.基于传递核映射的K-means二元属性算法谱聚类算法在处理多尺度以及形状复杂类型的数据时,都能够得到较好的聚类结果。然而谱聚类算法却有着计算量大,在执行过程中需要做特征分解导致时间复杂度高达到0(nh)等缺陷。针对上述情况,本文利用了传递核映射原理,将样本数据映射至一个新的空间中,并利用K-means二元属性,在新空间中对映射后的样本直接进行聚类。在人工数据集以及UCI数据集上的实验结果表明,基于传递核映射的K-means二元属性算法具有较好的有效性和实用性。3.基于传递距离的层次聚类算法层次聚类中的合并法最能够体现聚类算法的基本原则,然而当样本数据集中样本数据形状复杂,或者样本数据集中存在大量离群点数据时,层次聚类算法不能获得正确的聚类结果。针对这个问题,本文将传递距离的原理运用进层次聚类算法中,通过对样本数据建立一个传递矩阵,接着在该传递矩阵中一一合并相同的类别,最终完成对样本数据的聚类。在带有离群点数据及形状复杂的样本数据实验中,基于传递距离的层次聚类算法有着较好的有效性和鲁棒性。