在文本聚类中应用改进后的K-Means算法

摘刁石3七 随着Intemet的大规模普及和企业信息化程度的提高，无结构(如HTML和纯文本文 件)或半结构(如XML数据)化的文本数据正在以惊人的速度增长，文本数据的管理和分 析就变得空前重要。聚类技术作为文本信息挖掘技术中的核心技术之一，其目标是将文 档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能的大，而不同簇之间的相 似度尽可能的小。 自20世纪50年代以来，人们提出了多种聚类算法，大致可分为基于划分和基于层 次的两种。在基于划分的聚类算法中，最著名的是K一MeanS算法。自 1967年由MacQueen 首次发表后，目前已经成为数理统计、模式识别、机器学习和数据挖掘等领域应用最普 遍的聚类算法之一，并衍生出多种变形算法，组成了K一MeanS算法家族。这些K一Means 类型的算法聚类速度快、易于实现，而且适用于文本、图像特征等多种数据的聚类分析。 然而，由于聚类初始中心点选择的随机性，传统K一Means算法以及其变种的聚类结 果会产生较大的波动。本文基于密度的概念，对每个点(文本)按密度大小排序，通过自 适应选择最佳密度半径来确定最大的点密度，选择密度较大且合理的点作为聚类的初始 中心点，从而优化中心点的选择，使K·Means算法有个好的起点。同时针对文本特征矩 阵的高维性、稀疏性等特点，文本的每一个类别聚类时限定于所选关键词的一个子集， 因此本文在每一个聚类簇上根据变量对聚类结果贡献的重要程度赋予其不同的权值，重 要的变量赋予较大的权值，可以有效地解决文本数据的稀疏性、高维性等问题，显著地 提高K一Means算法聚类的准确性，快速发现好的聚类簇，得到一种适合文本数据聚类分 析的改进算法。本文对K一Means算法做了两点重要改进，实验表明改进后的算法能够生 成质量较高而且波动性较小的聚类结果。同时，为了使聚类结果易于理解和表达，对聚 类簇进行合适的标引，以便正确理解聚类簇内容，提高信息处理的性能和效率