基于约束信息的微博用户划分∗

王志凯 於跃成 蔡 莹 严长春

（江苏科技大学计算机学院 镇江 212003）

1 引言

随着互联网时代的发展，人们已经步入了大数据时代，社交网络上的数据也是如此。分析微博数据和微博用户划分方法已成为网络数据挖掘的研究重点之一。而这之中涉及的主要方法有文本聚类和主题分析等。

值得注意的是，微博上的数据普遍存在着文本较短、口语化现象较为严重等问题。以新浪微博为例，它限制一篇微博的字数不超过150 字。同时，由于微博上的言论自由，个性化的语言通常伴随着大量的省略和指代。微博博文的这些特点，为通过文本方式处理信息带来很大的困难，采用普通方法分析这些数据时难以获得有效的结果。

针对以上问题，结合微博数据特点来改进聚类过程的实现成为近年来分析微博数据的主流技术之一。刘涛［1］等通过在不同的聚类过程中使用有监督的方式选择特征，大幅提高了文本聚类的性能。彭京［2］等针对文本数据维度高和数据稀疏的特点，在内积空间的基础上建立了词和文本的相似度度量方法，获得了比传统方法质量更好的分析结果。文献［3］以Hownet 的情感词典为基础，构建了一个自动机来计算短文本的情感倾向。相比于一般文本分类方法，改方法在短文本上优势明显。张猛［4］等通过获取文本的细化簇并结合了曲线的多项式拟合技术，在细化簇上进行聚类，改进了文本聚类方法。索红光［5］等采用了局部搜索优化的思想，根据目标函数值的变化对聚类的结果作再次划分，改进了K-means在文本聚类上的应用。

另一方面，从微博上的用户发布微博的行为来看，其出发点包括转发好友的博文、和好友互动、遵从个人的兴趣爱好［6～7］等情况。基于上述特点，利用微博用户行为信息成为微博数据分析的另一类主流方法。Griven［8］等在2002 年提出了社交网络中社区的概念。Gao Q［9］等结合用户之间的关系和文本信息，把用户划分成不同拓扑结构上的群体。Java A［10］等通过对twitter上用户的位置信息的研究发现，互动性强或者相关性高的用户会逐渐形成一个个群体。Liu［11］等提出的NAS算法在挖掘社区信息是考虑了节点属性的相似度。由此可见，对微博用户进行划分仅仅抓住博文信息是不够的。

受以上方法的启发，针对微博上新用户的博文内容过少、朋友圈狭窄，部分用户博文内容过短、主题单一等问题，以K-means 算法为基础，结合半监督聚类的思想，提出了一种基于用户关系和行为的弱约束K-means 聚类算法来对微博上的用户进行划分。以改善标准K-means 进行文本聚类时过于依赖词频的缺陷。

2 相关工作

传统的K-means［12～14］算法是一种无监督的聚类算法，这种方式的聚类结果很可能会与我们的理想结果有一定的差距。因此，我们希望能够附加一些条件，使得聚类算法的结果更符合预期的标准。

约束聚类是一种将指定领域的知识通过“信息约束”的方式添加到聚类过程的方法。Wagstaff等［15］提出了must link 以及cannot link 这两种形式的约束。must link 我们可以称之为样本间的正约束，cannot link 我们可以称之为样本间的负约束。在该思想中，若一对样本(xi，xj)∈ML，即(xi，xj)满足must link 约束条件，则样本xi和样本xj属于同一个簇；反之，如果一对样本(xi，xj)∈NL，即(xi，xj)满足cannot link约束条件，则样本xi和样本xj不属于同一个簇。其中集合ML则被称为正约束的样本集，集合NL被称为负约束的样本集。PCC［16］聚类 算 法（Pairwise Constrained Clustering）在 传 统K-means的基础上，在聚类的时候引入了约束性的监督信息。将约束条件添加到K-means 的目标函数中，依靠约束信息，使得算法在执行的时候有条件的进行搜索，以保证满足正约束的样本对能够属于同一个簇，满足负约束的样本对不属于同一个样本簇。由于基于划分的聚类算法不能直接处理约束条件，需要优化目标，使用惩罚约束参数，使得样本对在满足约束条件的同时，每个样本到簇中心的距离和能够最小。

因此，基于约束的K-means聚类的目标函数如下所示。

其中，Zi和Zj为样本xa和xb的簇标记；ML和NL分别表示must link 和cannot link 两种形式的约束集；Wij表示这两种约束违反的代价权重。是一个指示函数，用来表示［true］=1，否则［false］=0，表示第k个簇的质心。

3 基于约束K-means 的微博用户群体划分

在微博中，一个用户发布的博文，往往是转发的好友博文、与好友的互动或者是自身兴趣爱好的体现。每个微博文本都包含着评论、转发、点赞等用户行为，任何一篇博文都不是独立存在的。在传统的对微博用户进行划分的过程中，只重视了文本的信息，而忽视了用户的行为信息。因此，本节提出了一种基于用户行为的改进K-means 弱约束聚类，以通过引入用户行为信息来改善仅仅使用文本信息来划分微博用户时所面临的问题。

3.1 用户间的亲密度

根据微博博文中反映出来的用户关系和用户行为，我们使用聚类算法对微博用户进行划分的时候，给予每个样本一个约束信息，同时保留博文之间的文本关系。为了防止数据信息偏差过大，我们在选取用户约束关系时使用了三层关系网的数据。如图1 所示，在描述目标用户的约束信息时，选择目标用户自身关注的用户。直觉上，目标用户关注的用户与目标用户存在共同兴趣的概率要高于随机选择的用户，因此，为了改善新用户直接关系用户过少，约束信息太弱的现象，选择目标用户关注的用户所关注的用户作为当前目标用户的弱约束信息，以进一步改善新用户易被忽略的问题。

通常，我们判断一个用户对一篇微博博文是否感兴趣的标准是通过转发、评价和点赞来计算的。但是由于在数据获取上不便于得知一个用户是否对于另一篇博文有点赞行为。因此，我们利用一个用户对其他用户的转发和评价行为来控制约束项，通过微博博文来对用户进行约束聚类。

图1 样本选取图示

假设一个用户有评价行为Com 和转发行为For，用Act 来表示两个用户之间关系的亲密程度。由于一个用户可能有多个关注的对象，因此用户xi与另一个用户xj之间关系的亲密度可以量化为Actij，可用式（2）表示。

其中，Comij表示用户xi对用户xj的博文的评价次数，Forij表示用户xi对用户xj的转发次数。Com表示用户i对所有好友的评论总数，For 表示用户i对所有关注的好友的转发总数。本文用用户xi对用户xj的博文的评价次数与转发次数的和与用户xi对于博文总共的评价次数和转发次数的和的比值，来比较用户xj相较于用户的xi的亲密程度。

3.2 微博用户划分

如式（3）所示的聚类目标函数，本文提出的用户划分方法只是建议有关注关系并且用户关系相对亲密的用户，在根据文本内容进行聚类的时候能够划分到一个用户群体中去，并没有强制规定两个有关注关系的用户必须要划分到同一个用户群体中去。因此，相比于经典的约束K-means 聚类，本文提出的方法是一种弱约束的K-means 聚类方法。算法流程如图2所示。

图2 结合用户行为的约束聚类算法

其中，Ck表示第k个簇的样本集。

4 实验结果与分析

4.1 实验数据获取与预处理

由于考虑到实验的数据是要来自于微博平台，并且很多信息来自于博文和用户的信息，因此我们采用以下三种方式相结合的方式：1）通过网络爬虫，将爬出的网页解析，运用正则表达式、人工观察相结合的方式，获取所需的数据。这个方式目的性明确，只是获取数据的方式最为复杂且速度相对比较慢；2）通过申请新浪微博的公开的API的方式获取数据，通过提供的指定接口，请求需求的数据；3）通过网上已经公开的一些微博数据。最经常使用的公开数据源的网站是中国爬盟。

为了保证获取的数据源的质量，需要我们排除一些无用的数据，合适的数据有利于我们有效地分析数据，因此，在获取数据之后，必须采取有效的方法对数据进行预处理。在数据预处理阶段，首先删除一些关注用户过少的用户（僵尸用户不利于我们后续的推荐），同时对于一定的时间段内，发布微博过少（不活跃用户）的用户，也以予删除。同时，对于予以采用数据的用户，记录下博文的评论数、转发数、点赞数和用户标签信息（如果有的话）。本节实验的数据筛选标准如下：

1）每条博文去除停用词、分词后，词语的数量大于3；

2）最近三个月内有过发布微博或者转发微博的行为；

3）关注的用户量至少有10人；

4）发表的总微博数大于等于10。

对于从用户获取的微博文本信息，使用Jieba分词算法进行分词、去除停用词并且去除一些过短的文本、文本中的表情、颜文字等。

4.2 实验评价标准

本节提出的用户划分方法不同于传统的k-means 算法，由于在通过聚类划分用户的时候考虑到了用户的关注关系，因此，实验采用模块度Q值来作为评价用户划分的标准。

模块度度值可以用来描述社交网络中社区结构好坏。模块度Q 值可用用户关系中实际的边数减去随机情况下用户间的边数。如式（4）所示。

其中，eii表示社区i 中，有关注关系的用户间边的个数，ai表示社区i中，任意用户相连边的个数。

4.3 弱约束聚类划分效果

由于本文提出的约束信息是基于用户关系和用户的行为的聚类。因此，在对用户进行划分后，首先分析每个用户群体中，满足约束条件的用户的个数，分析弱约束聚类的效果。

在下图实验结果中，以选定的目标用户为中心，选取周围200 名，且在三个月内发布微博数超过30 条的用户，总计7645 条微博文本。将周围的用户划分为5、6、7、8、9、10 个用户群体后，分析每个群体中有交互关系的用户却不在在一个群体中的个数、没有关注交互却仍在一个群体中的个数以及模块度值。

图3 反映了在不同的用户群体数下，具有交互关系却在不一个群体中的个数。

如图3 所示，当只使用K-means 方法，通过文本分析划分微博用户的时候，在所有用户群体中，具有交互关系但是不在一个群体中的用户数量随着用户群体的增加，呈现了逐渐增长的态势，当分为10 个用户群体的时候，已经有超过50%的用户在被划分的时候忽视了用户间的交互信息。相比之下，使用约束K-means的方法划分用户群体的时候，随着用户群体的数量的增加，一直保持着将近80%的用户能和与自己有交互关系的用户位于同一个用户群体中。

图3 有交互关系但不在同个群体中的用户数

综上所述，由于微博中的任何博文都不是孤立存在的，当只使用传统的文本聚类的方法划分用户时，已经把每个用户的博文看作是孤立存在的。通过这种方式划分出来的用户群体只有词之间的联系，没有交互性。相反，使用本文的方法划分用户时，能较好地区分用户的关系，相比于传统的方法，具有较大的提升，更适合与微博用户划分。

根据本文的方法，分析了图3 的数据后，还需要分析没有交互关系却被分到同一个群体中的数量。图4 反映了用户群体中没有交互关系的用户却在同一个群体中的用户数目。

图4 无约束关系但却在同个群体中的用户数

通过比较两种方法可以看出，传统的聚类相比本文提出的方法，同一个用户群体中存在着更多的没有交互关系的用户。随着用户群体的增多，传统的方法保持着较高的非关系用户，平均每200 个用户就有80 个左右这样的用户。而本文提出的算法则较好地减少了这种用户，并且随着用户群体的增加这类用户对维持在55 左右。同时这也能证明本文的方法是一种弱约束的聚类算法，它并没有强制规定每个用户群体中只能存在有交互关系的用户，只是建议将亲密度比较高的用户划分在一个群体中。

4.4 用户群体划分效果比较

由于微博用户的划分不能仅仅通过比较每个用户群体的文本聚类准确度来判断，因此为了评价本文的算法和传统的K-means 算法在划分用户时的差异，实验使用模块度值来评价两种方法。结果如表1所示。

表1 两种算法的模块度值的比较

从表1 的实验结果可以看出，本文提出的方法在划分微博用户群体的时候，比传统的只通过文本聚类的方法更加的合理。在用户群体个数从5 增长的过程中，传统的方法由于只关心了文本信息，因此在将用户划分后，模块度值一直处在很低的水平，这也说明传统划分方法结果虽然能使得每个群体中的用户有相似的兴趣，但是用户之间却都是陌生的，在处理微博上的新用户或朋友少的用户时，效果不佳。

而本文的方法在划分用户群体时，在微博用户真实数据集下，当用户被划分为7 个群体时效果达到了峰值，最佳结果是0.343966，这时构成的用户群体是最为稳定的，同时也反映用户在交友的过程中，兴趣相似固然很重要，但是人与人之间能否沟通是不可忽略的。

5 结语

本文主要针对网络社交平台下，划分用户群体时仅仅依赖用户的微博文本，忽略了用户间的内在联系等问题，采用聚类思想，改进了用户划分的方式。提出了基于用户关系和用户紧密度的约束聚类，将单独的用户划分成有内部关联的用户群体，针对微博平台，进行了适应性的改进并且通过实验数据的比较证明了结合了用户间关注信息的约束聚类能够更好地划分用户，适应微博平台。未来的工作中，将针对微博中朋友少的用户、微博文本少的用户，改进划分用户的方法。