一种改进的k均值文本聚类算法

张银明，黄廷磊，林　科，张嫱嫱

(桂林电子科技大学 计算机与信息安全学院，广西 桂林　541004)



一种改进的k均值文本聚类算法

张银明，黄廷磊，林科，张嫱嫱

(桂林电子科技大学 计算机与信息安全学院，广西 桂林541004)

针对k均值算法在文本聚类中由于初始聚类质心随机选择，使得聚类结果陷入局部最优，且孤立点和不确定的聚类个数造成k均值算法准确性低、收敛速度慢的问题，提出了一种改进的k均值文本聚类算法。该算法采用fp-growth算法挖掘文本频繁项集，过滤频繁项集得到核心频繁项集，并利用核心频繁项集指导文本初始聚类质心和聚类个数的生成，最后k均值算法利用初始聚类质心和聚类个数完成文本聚类。在新浪微博数据集上进行文本聚类实验，实验结果表明，改进的k均值算法提高了文本聚类的准确性，加快了收敛速度，具有较强的鲁棒性。

文本聚类；fp-growth；k均值

随着网络信息的爆炸式增长，在海量文本中高效、准确地提炼有价值的信息已成为研究热点。文本聚类作为文本挖掘的重要手段，将有价值的信息通过文本聚集呈现，是一个自动划分类别的过程。k均值算法简单易懂，是应用最广泛的聚类方法，但k均值算法存在2个不足：1)在聚类之前需要确定数据的聚类个数；2)初始聚类质心的随机选择导致聚类结果局部最优而非全局最优。针对上述不足，李小武等[1]提出了基于最优划分的k均值初始聚类中心选取算法，该算法通过划分样本确定初始聚类中心的分布，但文本维数较高时递归次数增多。Krishna等[2]采用k均值聚类算法和二分k均值聚类算法分别对文本进行聚类，二分k均值聚类算法不会出现聚类结果局部最优，效果优于k均值聚类算法。Liu等[3]提出了内核k均值算法，减少了非线性支持向量机的训练样本，在保持较高的测试精度的同时降低了采样时间的复杂度。然而，这些算法未考虑聚类个数，导致聚类效率低，聚类效果不理想。为此，基于fp-growth算法，提出了一种改进的k均值文本聚类算法。

1　算法的基本思想和框架

1.1k均值文本聚类算法

k均值文本聚类算法首先对文本进行分词，然后采用tf-idf、vsm算法对特征词和特征词的频度建模[4]，将文本映射为n维的特征向量，并通过特征向量测量文本之间的语义距离，最后利用k均值算法对文本进行聚类。例如，对3篇文章进行分词并提取特征，可得特征向量

(1)

其中ai、bi、ci(i=1，2，…，n)分别表示特征在3篇文章中出现的次数，n为文章的特征数。向量空间模型采用特征向量余弦测量文章的相似度。余弦值越大，则文章相似度越差，否则文章相似度越好。特征向量余弦

(2)

其中：文本特征向量A=(a1,a2,…,an)，B=(b1,b2,…,bn)。

k均值算法流程[5]为：

1)通过随机函数，创建k个起始质心。

2)计算文本项与每个质心的相似度，将文本项分配到相似度值最小的簇。

3)重新计算每个簇的质心，质心为簇中文本项特征出现次数的平均值。若质心收敛，则聚类完成，否则继续步骤2)。

k均值算法由于质心的随机性导致聚类结果局部最优，若随机选择的质心是孤立点，则孤立点将单独成为一个簇，而且影响其他簇的生成，这与聚类的目的相违背[6]。

1.2改进的k均值算法

改进的k均值算法采用fp-growth算法挖掘文本的频繁项集，过滤频繁项集得到核心频繁项集，并利用核心频繁项集指导k均值算法的初始聚类质心和簇的个数，最后结合k均值算法完成文本聚类。fp-growth算法挖掘的初始聚类质心降低了k均值算法的计算复杂度，避免了孤立点对k均值算法的影响。主要表现为：

1)核心频繁项集代表数据集中表达主题的个数，精确地描述了聚类个数。

2)通过核心频繁项集得到的初始聚类质心在文本相似度上属于每个簇，减少了聚类过程的迭代次数。

fp-growth算法将数据存储于高度压缩的数据结构fp-tree，减少了多次遍历数据库，而且fp-growth算法通过统计元素项、挖掘频繁项建立fp-tree，并采用递增的方式利用条件fp-tree挖掘频繁项集[7]。

fp-growth算法挖掘频繁项集的过程为：对给定的事物数据库进行2次扫描，第一次扫描数据库，得到元素项的出现次数为w，设定出现次数阈值ε1，若w>ε1，则该元素项称为频繁项。由于fp-tree是一棵有序的树，且挖掘条件模式基依赖频繁元素的出现次数，因此第二次扫描数据库，去除不频繁元素，筛选出项集中的频繁元素，并且按照频繁元素出现的次数完成元素的排序。在挖掘频繁项集的过程中，原始项集包含频繁元素和非频繁元素，而挖掘的频繁项集只包含频繁元素。元素项处理结果如表1所示，完成了元素项的筛选及排序。

表1　元素项处理结果

fp-tree是一棵根节点为空的树，除根节点外，其他节点包含元素的名字和元素出现的次数。fp-tree的构建规则为：

1)读入项集，若项集已存在，则在原来路径中修改计数值。

2)若项集不存在，则创建一条新路径，已存在的部分路径更改计数值。

为了高效地访问fp-free，增加了头指针表，头指针指向给定类型的第一个实例，相同类型彼此连接。在访问fp-tree时，通过头指针表，可以快速地访问给定类型的所有元素。为了形象地描述建树过程[8]，采用表1的数据建立fp-tree，如图1所示。

图1　fp-treeFig.1　fp-tree

在fp-tree中挖掘项集的条件模式基，利用条件模式基构建条件fp-tree。条件模式基是条件fp-tree上查找元素为叶子的路径集合，条件fp-tree属于fp-tree。挖掘频繁项集是一个递归的过程，其原理为：

元素项t的条件基为{z,x,y,s}:2,{z,x,y,r}:1,元素项s、r均满足最小支持度，但项集{t,s}、{t,r}不满足最小支持度，不是频繁项集。而项集{t,z}、{t,x}、{t,y}是频繁项集。下一步查找{t,z}的条件模式基，递归挖掘条件模式基，得到所有的频繁项集。

对频繁项集进行过滤，得到核心频繁项集。其过滤规则为：

1)创建一个核心频繁项集的集合，用于存储确定的频繁项集。

2)若频繁项集Si⊇Sj，则将频繁项集Si放入核心频繁项集。

3)若不存在包含关系，则比较Si、Sj的相似度。若其相似度大于相似度阈值ε，则合并频繁项集作为核心频繁项集，否则创建一个新的核心频繁项集。

核心频繁项集个数代表聚类的个数，每个核心频繁项集可作为k均值的初始聚类质心。算法通过调节阈值确定聚类的个数，若对聚类粒度要求较高，可增大阈值，否则减小阈值。改进的k均值算法流程为：

1)采用fp-growth算法指导初始聚类质心和聚类个数的生成。

2)利用初始聚类质心和聚类个数作为k均值的输入，完成文本聚类。

2　实验结果与分析

为了测试改进算法的性能，挖掘新浪几十个热门话题的10万条微博，内容包括体育、韩剧、手机等。其中大话题包括多个小话题，对微博聚类测试算法的性能。实验采用复旦大学的分词系统对文本分词，然后使用fp-growth算法挖掘文本的核心频繁项集，核心频繁项集的个数由相似度阈值决定，在算法中聚类个数由核心频繁项集的个数决定，根据聚类结果要求的粗略程度调节阈值。在确定聚类个数和初始聚类质心的前提下，利用k均值算法完成对文本的聚类。

实验通过改变fp-growth频繁项集相似度阈值ε，观察聚类的个数及聚类的效果，并使用准确率P、召回率R和F值评价聚类结果。

(3)

(4)

(5)

其中：T为同类文本被分到同一个簇的个数；M为不同类文本被分到不同簇的个数；N为同类文本被分到不同簇的个数。F为准确率和召回率的协同表现，综合体现聚类效果的优劣。

改变频繁项集相似度阈值ε，寻找最佳聚类结果的相似度阈值ε，不同相似度阈值的聚类结果如表2所示。

表2　不同相似度阈值的聚类结果

文本聚类结果的评判方法是文本是否正确归为本应所属的簇。簇的个数越多，文本归属到对应的簇的概率就越大。若簇的个数足够多，则每个文本单独属于一个簇，显然聚类个数不能用来衡量聚类效果[9]。由表2可知，当ε=0.75时，F值最大，文本聚类结果最佳。

为了消除参数对算法的影响，改进算法、k均值算法、二分k均值算法3种算法在相同数据集和参数下聚类。取ε=0.75，聚类个数为82个，得到3种算法的聚类结果，如图2所示。从图2可看出，改进算法的准确率、召回率、F值均高于k均值算法和二分k均值算法，二分k均值算法高于k均值算法。

图2　3种算法的聚类结果Fig.2　The clustering results of three algorithms

改进算法、k均值算法、二分k均值算法的迭代次数如图3所示。从图3可看出，改进算法的迭代次数在不同数据条数下高于k均值算法和二分k均值算法。由于二分k均值算法将整个数据集作为一个簇，然后将该簇一分为二，并选择最大程度降低聚类代价函数(误差平方和)的簇划分为2个簇，误差平方和是簇中每个元素与聚类质心距离的平方和。相比k均值算法，二分k均值算法避免了聚类结果的局部最优。但是二分k均值算法的初始聚类质心依然是随机的，并未避免质心的移动，且误差平方和增加了算法的计算复杂度，效率没有显著提高。改进算法采用核心频繁项集指导初始聚类质心，聚类质心在文本相似度上与该簇的主题相似，聚类过程中减少了聚类质心的移动，降低了计算复杂度，提高了算法的收敛速度，且获得了最佳的聚类个数。

图3　3种算法的迭代次数Fig.3　The iteration number of three algorithms

3　结束语

基于fp-growth算法，提出了一种改进的k均值文本聚类算法。该算法采用fp-growth算法挖掘频繁项集，利用频繁项集过滤核心频繁项集，通过核心频繁项集指导聚类个数以及初始聚类质心的生成，最后将其作为k均值算法的输入，完成了文本聚类。该算法克服了k均值算法容易陷入局部最优的缺陷，提升了算法的收敛速度。

[1]李小武,邵剑飞,廖秀玲.一种基于K-means的分布式聚类算法[J].桂林电子科技大学学报,2011,31(6):460-463.

[2]KRISHNABSV,SATHEESHP,SUNEELKUMARR.Comparativestudyofk-meansandbisectingk-meanstechniquesinwordnetbaseddocumentclustering[J].InternationalJournalofEngineeringandAdvancedTechnology,2012,2249:8958.

[3]LIUXiaozhang,FENGGuocan.Kernelbisectingk-meansclusteringforSVMtrainingsamplereduction[C]//19thIEEEInternationalConferenceonPatternRecognition,2008:1-4.

[4]彭敏,黄佳佳,朱佳晖,等.基于频繁项集的海量短文本聚类与主题抽取[J].计算机研究与发展,2015,52(9):1941-1953.

[5]XUJiaming,XUBo,TIANGuanhua,etal.Shorttexthashingimprovedbyintegratingmulti-granularitytopicsandtags[J].LectureNotesinComputerScience,2015,9041:444-455.

[6]TIANYun,LIHaisheng,CAIQiang,etal.Measuringthesimilarityofshorttextsbywordsimilarityandtreekernels[C]//IEEEYouthConferenceonInformationComputingandTelecommunications,2010:363-366.

[7]HUXia,SUNNan,ZHANGChao,etal.Exploitinginternalandexternalsemanticsfortheclusteringofshorttextsusingworldknowledge[C]//ACMConferenceonInformationandKnowledgeManagement,2009:919-928.

[8]BHARTIKK,SINGHPK.Hybriddimensionreductionbyintegratingfeatureselectionwithfeatureextractionmethodfortextclustering[J].ExpertSystemswithApplications,2015,42(6):3105-3114.

[9]张建沛，杨悦，杨静，等.基于最优划分的k-means初始聚类中心选取算法[J].系统仿真学报，2009，21(9):2586-2589.

编辑：曹寿平

An improved k-means algorithm for text clustering

ZHANG Yinming, HUANG Tinglei, LIN Ke, ZHANG Qiangqiang

(School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China)

Random selection of initial cluster centroid ink-means algorithm for text clustering resulted in local optimization of clustering results, and isolated points and indeterminate cluster number led to low accuracy and slow convergence speed ofk-means algorithm. So an improvedk-means algorithm for text clustering was proposed. In the proposed algorithm, fp-growth algorithm was used for mining frequent item sets of text, and frequent item sets of text were filtered to obtain the core frequent item sets, and then the core frequent item sets were adopted to generate initial cluster centroid and the number of clustering. Finallyk-means algorithm was applied for text clustering with the generated initial cluster centroid and the number of clustering. The results of text clustering experiment on Sina microblog dataset show that the improvedk-means algorithm can effectively improve the accuracy of text clustering and accelerate the convergence speed, and has strong robustness.

text clustering; fp-growth;k-means

2016-04-07

国家863计划(2012AA011005)

黄廷磊(1971-)，男，安徽肥东人，教授，博士，研究方向为数据挖掘、无线Mesh网络等。E-mail：tlhuang@guet.edu.cn

TP311

A

1673-808X(2016)04-0311-04

引文格式：张银明，黄廷磊，林科，等.一种改进的k均值文本聚类算法[J].桂林电子科技大学学报，2016,36(4):311-314.