论文部分内容阅读
伴随着信息技术和计算机网络的不断发展,每天有数亿的分布式信息被人们所共享。如何在这些海量的、异构的信息资源中快速而有效的检索出需要的信息成为人们日益关注的问题。知识发现和数据挖掘技术是解决这一问题的最新课题。文本聚类是文本发现和文本挖掘的最重要、最基本的功能之一,近年来文本聚类算法的研究取得了长足的发展和一系列的研究成果。目前常用的文本聚类算法有五类:基于划分的聚类算法,如最常用的K-means算法;基于层次的聚类算法;基于密度的聚类算法,如DBSCAN算法;基于网格的聚类算法和基于模型的聚类算法K-means算法是文本聚类算法中的最经典的基于划分的算法之一。其主要思想是随机选择K个初始中心点,将每个簇中心用该簇中数据的均值表示。这种算法具有时间复杂度低,实现简单等优点,对处理大数据集的可伸缩性较好。但是该算法也有比较明显的缺点:首先该算法的聚类效果对聚类初始中心的选择和设置过于敏感,极易导致聚类结果随之波动;其次是需要提前给定K值固定聚类个数;另外该算法在运行中容易陷入局部最优解。本文对传统的K-means算法加以改进,主要有两个方面的。首先基于距离和统计的思想对数据集中的孤立点进行了检测,先将数据点之间按最近距离升序排列,计算出所有数据点最近邻距离最大的几个数据点的最近邻距离差,以最大的距离差对应的距离值为半径对数据点的密度进行统计,将密度小于密度阈值的数据点进行统计学标准化值的检测,从而判断出数据集的强孤立点和部分弱孤立点并进行处理。其次提出一种可变步长的初始中心点选取算法。先将最近最小距离的数据点的平均距离计算出来,以此建立可变步长的半径空间,数据点的从小到大在半径空间中选取半径,对半径密度值进行计算,最终将半径密度最大最远的数据点作为初始聚类中心点进行输出。最后将基于距离和统计的孤立点检测算法和基于可变步长的初始中心选取算法结合到传统的K-Means聚类算法中,产生了基于密度的改进K-Means文本聚类算法。该算法通过对孤立点的检测和处理能避免传统K-Means算法容易陷入局部最优解的情况;又通过可变步长选取初始中心点能够提高传统算法的执行效率和聚类的质量。经过实验数据的检测证实该算法能从聚类效果和质量上都有所提高。