基于K-means的私人微博聚类算法改进

高永兵，郭文彦，周环宇，聂知秘

（内蒙古科技大学 信息工程学院，内蒙古 包头014010）

作为Web2.0时代新兴起的一类开放式互联网应用，微博是一种非正式的迷你型博客。据CNNIC（中国互联网信息中心）发布的数据显示，截至2013年6月底，我国的微博用户已达3.31亿，网民的微博用户比例达到了56.0%，用户每日发布的博文数多达1亿条。与传统社会媒体相比，微博的发展态势强劲，已成为人们生活中不可或缺的一部分[1]。针对微博的研究是目前的一大热点，微博不完全同于已有的短文本，它具有简短、实时性及社会性等特征。目前国内大量关于微博的研究都着眼于公共微博，如从公共微博中挖掘热点事件发现[2]、意见领袖识别、网络内容检测、网络舆情检测等[3]。本文针对私人微博，通过改进文本信息处理中使用到的聚类方法，对私人微博的内容进行整理和挖掘。对本人微博来说，可以对自己的微博历史内容整理归类，使得历史数据清晰可用；对他人而言，可以更清楚快速地了解他人微博的整体内容，挑选出自己感兴趣的信息；同时，也为公共微博的研究提供了支持,可以进一步应用于内容特征、用户兴趣分析和新兴话题检测等。这些功能对于数据量庞大的微博应用是很有实际意义的。聚类是一种无指导的机器学习方法，在数据挖掘领域中非常活跃，应用非常广泛。它基于“物以类聚”的原理，按照相似性把个体归为若干类别，使得同一类别差异尽可能小，不同类别差异尽可能大。其中K-means算法是目前应用最广泛的基于划分的聚类方法。本文的主要工作就是对常用的K-means算法进行改进，使之适应于私人微博文本。

1 私人微博文本特性分析及相关工作

1.1 私人微博文本特性分析

微博是一种半结构化的数据，不同于其他形式的短文本，微博文本本身就隐含了大量有价值的信息。例如采用新浪微博开放平台API，除了能够获取一条微博文本内容之外，同时还可以得到21条相关的其他信息。通过对大量个人微博纵向观察，总结出私人微博的鲜明特性：(1)文本长度短小，限定在140字内，信息量较少；(2)微博文本具有较强的时效性，内容与时间联系紧密；(3)一个人对某事件的态度和观点基本是一贯而连续的，但是兴趣点的转移却是很快的，这使得文本聚类分析变得复杂；(4)微博数据分布不平衡，符合相关研究人员提出的文本“长尾现象”；(5)微博结构中含有一些对内容非常重要的补充和提示，例如微博文本内容中两个“#”之间代表的是“微话题”，表示当前讨论的主题；微博文本内容中“@”符号后面的称谓表示了当前对话的微博账号；某条微博与其转发或者评论的微博内容上有着紧密的联系；微博转发量、评论量、点赞量这些量化了的数字提示了微博内容的流行程度及重要程度。

在文本挖掘领域中，与传统文本相比，短文本具有信息量小的缺点，这使得在数学化表示文本内容时，短文本会产生矩阵向量严重稀疏的问题。但是，微博与其他传统媒体的短文本相比隐含了大量有用的信息，为进行聚类研究提供了可以利用的条件，使得更有利于进行处理。正是在微博内容和结构上的特点的基础上，本文提出了基于K-means的改进聚类算法。

1.2 相关工作

通常进行文本聚类算法之前，需要经过几个典型步骤：文本表示、特征选择、相似度计算等。文本聚类需要建立文本模型，将文本转化成数据格式。文本模型反映了数据的关系，并在此基础上采用文本相似度的计算方法，最后采用聚类算法形成聚簇。

1.2.1文本表示和特征选择

本文在文本表示上采用了典型的向量空间模型VSM(Vector Space Model)[4]，并结合私人微博特点，采取形成伪文档的方法。微博内容往往与所评论和引用的微博紧密相关，所以把评论内容和引用内容归并到正文内容中，形成伪文档，这样部分解决了矩阵向量严重稀疏性的问题。如对某用户新浪微博2013年2月14日～2013年6月7日内共492条微博内容进行整理，如表1所示。

表1 伪文档整理对比表

可以看到，微博内容增加了一倍多，字数特别少影响到语义的文本数目大大减少。

然后进行分词预处理，本文采用中科院的汉语词法分析系统 ICTCLAS(Institute of Computing Technology，Chinese Lexical Analysis System)进行分词。特征选择上采用应用最为广泛的TFIDF(Term FreqencyInverse Document Frequency)方 法[5]。

1.2.2相似度计算

在相似度计算上采用的是改进的欧式距离[6]。设两个微博文本转化为两个 p纬向量 xi=(xi1，xi2，…，xip)和 xj=(xj1，xj2，…，xjp)，则它们的欧式距离为：

鉴于微博内容与时间的相关性，对式(1)进行改进，添加了时间上的考量。时间相似度的计算公式如下：

其中，ti和 tj分别表示编号为 xi和 xj的微博发布时间，该公式的计算结果在0和1之间。改进后的欧式距离既考虑了语义相似度又考虑到了时间相似度，如下：

其中，α 和 β 为相似度的可调节参数，simCom(xi，xj)为文本向量的综合相似度。

1.3 K-means聚类算法思想

聚类算法基于著名的假设：同一类别相似性大，不同类别相似性小。K-means算法属于聚类方法中一种典型的划分方法[7-8]。它的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇，然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。K-means算法的具体过程如下：

输入条件：聚类簇的个数k，以及包含n个数据对象的样本集。

输出条件：满足方差最小标准的k个聚类。

(1)选取k个对象作为初始聚类中心；(2)根据聚类中心的值，将每个对象（重新）赋给最相似的簇；(3)重新计算每个簇汇中对象的平均值，用此平均值作为新的聚类中心；(4)重复执行步骤(2)、(3)，直到评价函数收敛或聚类的中心不再发生变化为止。

K-means具有算法流程简单、复杂度低易于实现、效率高易于并行等优点，但是也存在着一些缺陷：(1)需要指定聚类数目K，K的指定往往需要大量的经验并且使得算法准确性不稳定；(2)初始的K个中心点的选取是随机的，但是中心点的选择对算法的准确性有较大影响，往往希望中心点具有一定的代表性，即具有较高的密度。

2 改进的K-means聚类算法

许多研究都证明，不像传统的普通文档（如新闻文章和学术论文），直接对微博内容进行聚类效果不好；也不像一些其他的短文本，微博本身就隐含了许多可以加以利用的信息。在此基础上，针对私人微博使用了经过改进的K-means聚类算法。主要目的在于解决微博文本信息量小导致向量矩阵稀疏和K的取值需要人工指定及K个中心随机指定的问题。

2.1 聚类初始化

伪文档经过分词和预处理形成了语料库M。鉴于之前所述的私人微博特性，在文档M中，首先选取出文本内容含"#"符号的文本，且"#"话题一致的直接归为一类，不相同的另成一类。这样充分利用了微博文本内容特点，同一个微话题下讨论的必然是相同主题的内容，不需要机器识别。选取完成后，假设从中共挑出了m1，m2，…，mn个类别，每个类别中含有 c1，c2，…，cn条文本。

此时，文档分成了两类，一类是已挑出并进行归类的文档（设为集合 u1），另一类是待处理的文档(设为集合u2)。在u1中指定中心点为每个类别m中流行度最高的微博文本,其流行度由下式确定：

pop=cRe+cCo+cAg (4)其中，pop表示流行度，cRe表示转发数，cCo表示评论数，cAg表示点赞的个数，这些参数都可以直接获得。通过流行度能够近似获得文本的重要程度，进一步获得文本密度较大的中心点。在某一聚类簇中只含一个数据的特殊情况下，它的中心点就是数据向量本身。

2.2 初始类别的选取和中心点的确定

2.2.1 K值和中心点的形成过程

u1和u2初始化完成后，通过相似度计算求得u2中每个向量与u1中所有中心点的距离。其中u2到u1中各个类中心点的所有距离中最近距离设为dmin。当dmin大于某一阈值P时，u1中添加一个新类，把此条数据向量归入该新类中，再重新计算u2中每个向量与u1中所有中心点的距离；当dmin小于该阈值P时，把此条数据向量归到u1中离中心最近的那个类，重新计算u1的中心点，此时的中心点计算采取求向量数值平均值的计算方法。u2中所有数据都添加到u1时(即u1=M时)停止。初步分类完成。

至此，得到聚类簇个数K的值，也得到每个类别的中心点。

2.2.2 相似度的计算

相似度的计算采用了改进后的欧式距离公式，该公式添加了时间相似度进行考量。微博内容的相似度与时间上的间隔有一定关系，把微博在时间上越相近、内容上相似的概率越大的因素也考虑进去。

2.2.3 阈值P的选定

阈值P的选取除了可以使用固定经验值外，也可以采用更为灵活的自适应选取的方法。计算u2中每个向量与u1中所有中心点的距离，选取其平均值为P。虽然增加了计算量，但是使得算法更稳定。实验证明，通过该方法选取的P值对结果的影响是较准确的。

2.3 采用K-means算法进行迭代

根据聚类中心的值，将每个对象（重新）赋给最相似的簇；重新计算每个聚类簇中所有对象的平均值，用此平均值作为新的聚类中心；比较每个数据向量离它最近的聚类中心是否就是其所属的聚类的中心；迭代，直到评价函数收敛或聚类的中心不再发生变化为止。最终得出聚类结果。

2.4 聚类结果的整理

私人微博上有许多信息都是属于个人的信息，如个人的想法、遇到的事情、心情等。这些信息一般都是孤立出现，缺乏聚类的意义。有关研究人员提出了短文本的“长尾现象”[9]。根据“长尾现象”的理论，最后得出的类别数目有很大部分会是小的类别，把这些小类别视作孤立点，将不太具有聚类效果和意义的进行舍弃。实验得出当某类文档个数只含有1或2个文档时进行舍弃效果较好。

2.5 改进后的K-means算法流程图

改进后的K-means算法流程如图1所示。

图1 算法流程图

3 实验及结果分析

运行环境为Windows 7操作系统，3.20 GHz CPU，8.0 GB内存，编程工具是Microsoft Visual Studio 2012。数据通过新浪开放平台API获取，从名人影响力榜上随机抽取了50位认证用户的微博进行实验，其中每位用户的微博数量不少于100条，时间跨度不小于一个月。以下采用某名人用户新浪微博2013年2月14日～2013年3月11日内共100条微博内容做举例进行说明，分词采用中科院的汉语词法分析系统（ICTCLAS）。

鉴于微博内容聚类结果评价标准难度较大，本文对聚类质量的评价标准参考了一种常用的基于人工标注的评价指标F-measure[10]的思想并进行了简化，主要以人工判别为主，对聚类产生的结果直接进行人工判别。当结果簇中超过半数的文档可以被看做一类时，认为该聚类是正确的。通过结果簇的正确率的比较，衡量算法的准确性。

实验过程中，首先使用改进的算法进行实验(其中相似度计算时，α和β都取为 0.5)，然后再使用传统的K-means算法进行对照实验。传统K-means算法的K值根据改进算法的聚类簇个数给出。部分实验结果如图2所示。

图2 部分实验结果图

统计算法执行过程中的聚类个数，结果如表2所示。

由表2可知，对应于传统聚类算法的聚类簇数目K值为17。采用传统K-means算法再次处理，进行对比实验，实验结果如表3所示。

统计所有50人的微博文本聚类实验的正确率，结果如表4所示。

由实验结果可知，改进后的算法克服了K-means算法K和中心点需要指定的缺点，充分利用了微博内容和结构上的特点，且准确率较原算法也有提高，基本实现了设想的目标。

表2 聚类簇数目

表3 对照实验比较

表4 平均正确率比较

国内关于微博的研究主要都着眼于公共微博，本文从私人微博入手，以用户为单位对微博内容进行处理挖掘。由于微博文本不同于其他形式的短文本，其本身就隐含了大量有价值的信息，这些微博文本结构上和内容上的特点为研究提供了思路。针对私人微博的特殊性和传统K-means聚类算法的不足，本文提出了一种聚类簇数目和初始中心点自适应生成的改进算法，有效克服了传统算法准确性不稳定的缺陷。其应用在私人微博的聚类过程中，具有一定的使用价值。

由于只对文本内容进行了研究，而微博现在使用了大量的富媒体技术，下一步的工作需要针对如何结合富媒体对微博内容整体有一个更全面的研究。

[1]王连喜，蒋盛益，庞观松，等.微博用户关系挖掘研究综述[J].情报杂志，2012，31(12)：91－97.

[2]童薇，陈威，孟小峰.EDM：高效的微博事件检测算法[J].计算机科学与探索，2012，6(12)：1076-1086.

[3]蒋盛益，麦智凯，庞观松，等.微博信息挖掘技术研究综述[J].图书情报工作，2012，56(17)：136－142.

[4]BUGIS S P，YOUNG J E M，ARCHIBALD S D，et al.Diagnostic accuracy of fine-needle aspiration biopsy versus frozen section in solitary thyroid nodules[J].The American Journal of Surgery，1986，152(4)：411-416.

[5]AIZAWA A.An information-theoretic perspective of tf-idf measures[J].Information Processing&Management，2003，39(1)：45-65.

[6]张忠林，曹志字，李元韬.基于加权欧式距离的K-means算法研究[J].郑州大学学报(工学版)，2010，31(1)：89-92.

[7]MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability，1967(1)：281-297.

[8]万小军，杨建武，陈晓鸥.文档聚类中K-means算法的一种改进算法[J].计算机工程，2003，29(2)：102-157.

[9]彭泽映，俞晓明，许洪波，等.大规模短文本的不完全聚类[J].中文信息学报，2011，25(1)：54-59.

[10]LARSEN B，AONE C.Fast and effective text mining using linear-time document clustering[C].Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，1999：16-22.