基于聚类分析的微博用户标签自动生成

1、基于聚类分析的微博用户标签自动生成（吕海燕，王丽娜，张杰）（海军航空工程学院，山东 烟台 264001）摘要：本文基于用户发表的微博内容进行标签的自动生成，主要研究的是基于聚类分析的用户标签自动生成。本文首先介绍用到的关键技术：聚类技术和TextTank ,提出了Baseline系统，接下来详细说明了基于聚类分析的标签自动生成方法，最后通过实验对该方法进行了分析和评价。实验结果表明，该方法生成的用户标签能够有效地解决同义标签的堆积问题，使得生成的标签能够在更多的维度上体现用户的兴趣。关键词: 微博用户标签;TextRank;聚类分析Automatic generation of mi

2、cro-blog user tags based on clustering analysis（LV Hai-yan,Zhang Jie ,Wang Li-na,）(Naval Aeronautical and Astronautical University，Yantai 264000，China)Abstract: The main research is the automatic generation of micro-blog user tags based on cluster analysis. Key technolo

3、gies used in this paper are introduced firstly; mainly include cluster technology and TextRank. A Baseline system is proposed in order to show the validity of the research proposed by this paper. Then the automatic generation method based on clustering analysis is illustrated detailedly. Finall

4、y analyze and evaluate the method by experiments. The experimental results show that the user tags generated by the method can solve the problem of synonymy tags stack, and the tags can reflect the users interest in more dimensions.Keywords: Tags for Micro-blog Users; TextRank;&#

5、160;Cluster Analysis引言近年来，微博已经成为了一种流行的网络信息传播平台，越来越多的人拥有自己的微博账户。微博文本短小（一般限制在140个字以内），与手机、即时信息服务软件的连接使得微博发布的门槛很低，用户可以随时随地进行更新。随着我们关注的人数越多，信息量越来越大，使我们将面临“信息过载”的问题。针对这种信息过载的问题，人们开始逐渐关注微博上的个性化。而微博用户标签作为描述用户兴趣爱好、职业领域等特征的载体，在用户组织和搜索，挖掘用户兴趣和实现用户微博个性化等方面有着重要的作用1。微博用户标签自动生成便是从可利用的资源中自动生成短文本例如词语、短语来描述用户关心的内容和兴

6、趣点2-4。其生成方法从生成标签的不同粒度出发，主要有基于关键词和基于类别两种方法5-8。本文主要研究基于关键词的微博用户标签自动生成中基于聚类分析的生成方法。1. 关键技术1.1聚类技术 聚类是一种将数据对象划分成相似的集合（簇）的过程。常见的聚类技术可以分为：划分方法例如K-Means、层次方法例如层次聚类、基于密度的方法、基于网格的方法等等9。本文选择了层次方法中的自底向上的凝聚层次聚类。首先将每一个词语都当成一个独立的簇，需要对N个词语进行聚类，那么初始的时候就有N个簇。然后，根据簇之间的距离，选择最近的两个簇逐一合并，直到N个词语都聚成了一个簇。经过这种方法，可以得到一颗具有层次的聚

7、类树，在此之上观察哪一层的聚类效果最符合用途。 层次聚类有一个主要的问题就是在逐一合并簇的过程中如何度量两个簇之间的距离。根据衡量方式的不同，可以将层次聚类细分为单连接算法、全连接算法和均值距离/平均距离算法。本文采用的是单连接算法，也称为最近邻聚类算法。算法使用两个簇中最近对象的距离作为簇间的距离，当这个距离超过一定阈值的时候聚类终止，度量公式如(1-1)所示。其中，对象o1、o2分别属于簇c1、c2。 d(c1,c2)=mino1C1,O2C2d(o1,o2) 公式（1-1）1.2 Baseline 系统 本文采用TFIDF为候选关键词排序的策略作为Baseline系统。排序公式如公式1-

8、2所示。tfidft,u=tf(t,u)×log(UUt) 公式（1-2）其中，tf(t,u)表示用户u的微博文本中词t出现的频率，U表示微博语料中用户的总数，Ut 表示微博文本中包含t的用户数1.3 TextRank TextRank算法是由Rada Mihalcea等人10于2004年提出的用于文本关键词抽取的算法，其主要思想是一个词的重要性由其它与其关联的词决定。TextRank将文档中的词语类比于互联网网页，而词与词之间的联系类比于网页之间的链接关系。即算法认为文本是一个由词语构成的网络或者说是一个由词语作为节点构成的图，词语间的语义关系构成边。在图中越重要的词越可能是关键词

9、。每个节点Vi的TextRank分数计算如公式1-3所示。对每一个节点Vi，In(Vi)代表指向它的节点集合，Out(Vi)代表它指向的节点集合。wij代表Vi和Vj之间边的权重。SVi=1-d+d*VjlnViwijvkOutVjwjkS(Vj) 公式（1-3）2生成方法2.1 生成流程基于聚类分析的方法自动生成标签，简单来说，流程大致如图2-1所示。 用户微博去噪处理：删除URL、转发词等选取名词作为候选关键词计算词语距离，进行层次聚类选取簇代表词，扩展生成用户标签预处理图2-1 基于聚类分析的标签自动生成流程2.2 生成方法1） 预处理 当得到用户发布的微博文本之后，采取“合成”策略，即

10、将用户发布的所有微博合并成一个大文档进行处理。为避免不必要引入不必要的噪声，先去除微博文本中带有的URL链接，以及文本中某某人的字样。分词后，去除预定义的停用词。预处理后我们将得到一个候选的关键词集合，词语的词性都为名词。2） 词语层次聚类 本文采用的自底向上的层次聚类对词语进行聚类，具体算法如图2-2所示。而待聚类的词语集合是TextRank权重前200的词语集合。本文认为Top200的词语集合已经体现了用户的绝大多数兴趣。Given: a set of words=w1,wnFor i=1 to n doci=wiEndc=c1,cnj=1while|c|>1(cn1,cn2)=ar

11、g min(ck,cl)c×cd(ck,cl)cj=cn1cn2c=ccn1,cn2cjj=j+1图2-2 词语层次聚类算法3） 选取簇代表词，扩展 通过层次聚类选定某个聚类效果较好的聚类层。语义相关度较高的词语将被聚成一个簇。对于聚类形成的每一个簇，需要选择合适的词来代表它。本文选用选用簇中拥有最高TextRank分数的词语作为簇代表词。选取完簇代表词后，按照TFIDF策略对词进行扩展。但与代表词合并的词语必须出现在同一个聚类簇中。4） 生成用户标签 按照一定的规则排序聚类后形成的簇，一种是按照簇内词语TextRank分数的加和，一种是按照簇内词语平均的TextRank分数。其对应

12、的聚类代表词串，便是我们自动生成标签的顺序。3.实验与结果分析 3.1实验数据 本文以随机选择的50位微博用户发布的微博内容23680余条作为本文的测试数据，他们发布的平均微博条数为512条。3.1评价方法 通过观察微博用户的标签可以看出，微博用户为自己添加的标签如：“开朗”、“活泼”、“音乐”、“任性”等这些普遍型的标签，可能并未深入地体现用户的兴趣。浏览测试用户的所有微博内容，借助于用户已经为自己添加的标签等进行评定。评定的准则有两条：一是生成的结果能否体现用户的兴趣；二是生成的结果是否适合作为用户标签。本文为用户自动生成10个标签，并按照权重计算方式进行排序。评价指标采用信息检索领域经典

13、的评价指标PN（如公式3-1所示），表示生成的前N个用户标签结果的准确率。由于评价过程比较主观,因此本文采用两位评价者分别对生成的标签进行评定。PN=前N个标签结果中生成正确的数目N 公式3-13.2聚类终止的条件 聚类终止条件，即聚类过程达到什么条件，实际就可以停止了。假定，当簇间的距离小于某值时停止迭代。因此，需要寻找到这一阈值。将40位测试用户产生的词对的互信息分数由高到低进行排序，发现当互信息得分不超过7时，词对的语义关联已经较为微弱。因此，本文将阈值K粗略地设置为7、6、5、4、3、2、1（它们为互信息分数）进行人工比较。通过观察发现，当阈值设置为6时，效果普遍较好。将K值设为6，聚

14、类效果如表3-1所示。表3-1 词语聚类示例聚类簇序号 聚类簇内词簇1 企业 商店 员工 团队 管理者 高层 市场价值 人力 财力 社会资源簇2 领导 负责人 首长 长官 主管 主任 官员 领导者簇3 毕业生 学校 本科 研究生 学历 博士 课程 人才簇4 需求 客户 市场 产品 领域 行业 簇5 福利 奖金 工资 薪酬3.3 标签自动生成效果 选取每个簇内TextRank分数最高的词语作为该簇的代表词，进行扩展。抽取的关键词，若按照簇内TextRank分数加和排序，称之为cluster-sum；若按照簇内TextRank平均值排序，称之为cluster-avg。同时，选取baseline系统

15、与其对照。标签自动生成效果如表3-2所示。表3-2 基于聚类分析的标签自动生成效果（）评价者1的评价结果TFIDFcluster-sumcluster-avgP157.3069.558.36P249.2557.5453.22P342.8749.6547.13P441.0248.9246.20P538.9746.8540.50P636.4545.9638.84P732.24 43.10 35.98P829.8744.2833.62P929.0239.2733.36P1028.7939.0532.58评价者2的评价结果TFIDFcluster-sumcluster-avgP153.2071.006

16、8.16P247.8360.2459.12P343.2756.0452.43P441.6552.8848.29P539.6550.8549.75P637.7148.6845.94P734.3445.1043.62P832.4844.7941.12P930.3341.8739.50P1029.8740.2038.68 对每一种生成标签的方式，计算两位评价者评价结果的一致性，用Cohens kappa系数衡量。Kappa值在-1到1之间，值越大则一致性越好。当kappa值超过0.75时，则说明评定的结果的一致性是非常好的；kappa值在0.40与0.75之间时，则说明一致性一般；kappa值低于0

17、.40时，则说明一致性很差。两位评价者评价的一致性如表3-3所示。表3-3 评价者1、2对标签生成结果评定的一致性TFIDFcluster-sumcluster-avgcohens kappa0.58200.58010.5779小 结微博用户被允许使用自造的、长度不限的词语或者短语来描述、标识自己。这就是所谓的标签功能。本文从微博内容分析的角度出发，研究了基于聚类分析的微博用户标签自动生成技术，旨在生成能够体现用户兴趣的标签。实验结果表明，该方法解决了同义标签的堆积问题，使得生成的标签能够在更多的维度上体现用户的兴趣。参考文献1 Klaas Dellshaft， Steffen Staab.

18、An Epistemic Dynamic Model for Tagging SystemsC. In HT08: Proceedings of the nineteenth ACM conference on Hypertext and hypermedia. 2008: 71-78.2 Simo Overell, Borkur Sigurbjornsson, Roelof van Zwol. Classifying Tags Using Open Content ResourcesC. WSDM. 2009:64-73.3 Manish Gupta，Rui Li，Zhijun Yin,et

19、 al.Survey on Social Tagging TechniquesC.Sigkdd Explorations.2010，12(1):58-72.4 Heymann P, Garcia Molinay H. Collaborative Creation of Communal Hierarchical Taxonomies in Social Tagging SystemsR. Technical Report InfoLab. Department of Computer Science, StanfordUniversity, Stanford, CA, USA. April 2006: 1-5.5 Jilin Chen,