基于主题文本的推断社会关系强度的熵模型

邓钟晟

(东华大学计算机科学与技术学院，上海 201600)

0 引言

近年来，随着在线社交网络服务［1］的迅速发展。许多知名网站如新浪微博、Facebook、豆瓣等吸引了巨大数量的用户，对互联网环境产生了巨大影响［2］。在线社交网络通过用户间相似的教育、地理等背景以及共同兴趣，为人与人之间的信息共享和社交开辟了新的渠道［3］。其开放性促使用户产生大量的轻量数据，如标签、评论、话题、作品。每个用户的数据都能反映出用户的特征，通过抽象这些数据，进行比较，可以评估用户之间的关系强度。

熵在生态学中可用于反映生物在地区分布中的多样性，通过熵模型，可以反映用户间在不同地点、不同时间的出现的分布情况，进而判断用户的关系强度。文献［4］通过比较用户的签到数据，推断用户在时空上的社会关系强度，在效率和效果上都有良好的表现。本文在此基础上，将用户数据在不同事物、不同关键词上的分布情况通过熵模型进行计算，从而得到用户在社交网络中关系强度。

1 数据定义

1.1 兴趣集合

当用户在网络上发布文字时，服务器上将记录以下信息:

其中用户id 为数据库标示用户的索引;主题编号为文本信息所表述的对象，在社交网络的轻量数据中，主题编号可以是微博中的某一话题、某位热点人物、某类商品;文本信息为用户在目标主题上的看法、感受等。将文本信息切分成意义明确的单词，这些数据可以表示为一个三元组＜u(user)，i(item)，t(token)＞。其中u 表示用户的id，i 为主题，t 为单词。从而元组＜u，i，t ＞可以表示用户u 在主题i 的关键词为t。例如，用户u1在世界杯主题下发表了“C 罗加油，葡萄牙加油”的评论，可以得到三元组＜u1，“世界杯”，”C罗”＞，＜u1，“世界杯”，”葡萄牙”＞，＜u1，“世界杯”，”加油”＞。显然，这些三元组的集合可以在一定程度上描述一个用户的特点和兴趣。

假设用户u1有以下三元组:

将用户u1在所有的主题中的信息整合成一个向量，则用户u1的兴趣向量可以表示为:

表示用户在主题i1上的关键词为t1，t2，在主题i2上的关键词为t3，在主题i3上的关键词为t2，t4。最后，任意用户ui在M(1，2，...，m)个主题上分别有k 个关键词，则可以得到用户的兴趣向量为Vi=(＜t1，1，t1，2，…，t1，k1＞，＜t2，1，t2，2，…，t2，k2＞，…，＜tm，1，tm，2，…，tm，km＞)

1.2 同现向量

若2 个用户在同一个主题上有相同的关键词，则可以认为2 位用户有相同的兴趣。从而可以得到用户a 和用户b 之间的相同关键词出现的向量(同现向量):

其中Cab，i表示用户a 和用户b 在主题i 上出现的相同关键词的个数。例如，假设有8 项主题，用户u1，u2在主题上的兴趣向量如下:

则用户间同现向量为C12=(1，1，1，0，0，0，0，0)，通常情况下，主题的总数是巨大的，每个用户相关的主题在主题集合之中只能占到极小的部分，因此同现向量与用户兴趣向量中的值多数为0。同现向量表示了用户之间相同兴趣在主题集合上的分布情况。

2 熵模型

熵模型通过Renyi 熵和区位熵推断2 个用户在社交网络上的关系强度。其中Renyi 熵是香农熵的推广，用于计算同现向量的多样性［5］。而区位熵是基于主题权重的计算，用于消除热门主题对社会关系强度造成的误差影响。

2.1 多样性

多样性的概念被广泛地用在物理学、经济学、生物学等领域，用于评估目标系统的丰富程度。对于本文的同现向量，可以认为相同兴趣更具有多样性(更广泛)的人之间拥有更强的社会联系，对于以下3 个同现向量:

可以注意到用户1 和用户2 之间有5 个相同兴趣，用户2 和用户3 为4 个，用户1 和用户3 为1 个，虽然拥有同样多的相同关键词，但是不难理解C12比C23更具有多样性，C23比C13更具有多样性，因此用户1 和用户2 之间具有更强的社会关系。

熵模型正是使用同现向量的多样性这一指标，度量2 个用户间同现向量所代表的有效主题的数量，得到用户同现向量多样性丰富程度的比例中项，进而评估用户间的关系强度。

2.2 香农熵

香农熵是一种评估样本多样性的模型，定义了用于描述样本不确定性程度大小的度量熵(简称为香农熵)。当概率分布P 的不确定性程度越大时，其对应的熵值越大;反之，其熵值越小。在主题文本的应用环境下表示用户a 和b 在主题i存在相同关键词表示用户a 和b 在主题i 上的相同关键词的合集，是用户a 和b所有相同兴趣关键词的合集，则用户在主题i 上相同关键词的概率为。用户a 和b 的同现向量的香农熵为:

香农熵的多样性指数［6］为:

以上文中的3 个同现向量为例，香农熵的多样性指数如下:C12=5.0，C23=3.789，C13=1.0。正确地反映了3 个同现向量的多样性。

2.3 Renyi 熵

对于香农熵的多样性而言，兴趣向量在一个主题上的高频次会使计算结果产生和实际情况不相符的误差［7］。将香农熵推广到Renyi 熵［8］后，可以通过q的取值控制多次重复对计算结果的影响。Renyi 熵的定义如下:

Renyi 熵的多样性:

其中fab=∑iCab，i表示用户a 和b 的相同兴趣关键词的总数。Cab，i表示用户a 和b 在主题i 上的相同兴趣关键词个数。

公式(4)表示了由Renyi 熵给出的相同兴趣向量的多样性，其中q 为多样性级数，文献［9］阐述了多样性级数对Renyi 熵计算结果的影响，证明过程本文不再赘述，其q 值的变化反映了局部频率的权重:

1)q ＞1，局部频率Cab，i越大，其权重越大，对多样性的影响力越大。

2)q ＜1，局部频率Cab，i越小，其权重越大。

3)q=0，多样性与Cab，i无关，为相同兴趣的个数。

4)q=1，Renyi 熵及其多样性分别转化为香农熵及其多样性。

例如对于相同兴趣向量Cab=(10，1，0，0，9)与Ccd=(2，3，2，2，3)，香农熵多样性为Dab=2.35，Dcd=4.90。而Renyi 熵的多样性(q=0.5)分别为Dab=24.60，Dcd=279.67。可以看出用户c 和d 之间同现向量的多样性评分显著高于用户a 和b，且Renyi 熵提高了均匀分布样本的多样性指数。

3 权重频率

对于热门主题，参与的用户数量与冷门主题的用户数量相差较大。因此，在热门主题中更有可能出现相同的关键词。显然，这些相同关键词与冷门主题中的相同关键词相比更有可能是巧合，或是较为普遍的关键词。因而这些关键词在社会关系强度的评分上应当进行适当的权重修正。本文将区位熵引入模型，从而对热门主题中的关键词评分进行修正。

区位熵可以用于衡量一个区域的热门程度［10］。计算结果区位熵越大，表示该地方越受欢迎。在本文中，将区位熵用于衡量一个主题的热门程度。通过访问主题的用户数量计算主题的热门程度。其表达式如下:

其中Pu，i=|Vi，u|/|Vi|表示用户u 访问主题i 的概率，Vi，u={＜u，i，t ＞:∀t}表示用户u 访问主题i 的集合，Vi={＜u，i，t ＞:∀t，∀u}表示所有用户访问主题i 的集合。

则加权频率为:

同样以相同兴趣向量Cab=(10，1，0，0，9)、Ccd=(2，3，2，2，3)为例，假设主题1 与主题5 为热门主题，另有其他20 名用户访问，且每人访问10 次，可以得到加权频率Fab=1.10，Fcd=3.07。可以发现使用加权频率提高了在冷门主题中的关键词的权重。

4 社会关系强度

上文阐述了用相同兴趣向量评估用户关系强度的2 种相互独立的方法，多样性分析的是用户在主题维度上的分布，加权频率则关注的是主题本身的热门程度。因此用户间在社交网络上的关系强度与这2个独立变量线性相关，从而得到用户a 和b 间社会关系强度的表达式:

其中参数α，β，γ 需通过对已知好友关系的数据集学习获得。文献［4］比较了3 种评估关系强度的技术，分别为杰卡德距离、亚当/亚达相似性［11］、卡茨评分。其中卡茨评分在熵模型的召回率与准确率上变化较为平滑，训练效果较好。

卡茨评分通过计算用户与用户在社交网络上的关系距离，从而评估用户间的关系强度，用户a 与用户b 之间的卡茨评分定义如下:

其中Pab，l表示从用户a 到用户b 好友路径长度为l 的集合，ε 是一个正常数，随着l 的增长，ε 能减少其对卡茨评分的影响，最优值应在10-3数量级上［12］。在实际应用中，考虑六度分割理论［13］，长度大于4 的路径对卡茨评分的影响较小，可以忽略不计。

5 实 验

5.1 实验数据

实验使用了last.fm 网站提供的用户数据，last.fm 网站提供了用户各类音乐专辑、曲目的数据，允许用户对这些音乐条目打上自定义的标签，并且提供了好友关注的社交功能［14］。数据分为3 部分:1)用户数据，用户的数字编号标示的用户数据，总计99 405条。2)好友关系信息，以2 个用户编号为一组的好友关系对，总计3 151 283 对。3)标签信息，以用户编号、条目编号、标签编号组成的三元组，条目编号1 393 559条，标签编号281 818 条。用户的相关参数统计如表1 所示。

表1 数据集中用户相关参数的统计信息

5.2 实验方法

本实验使用数据集中一半的数据进行训练，用剩下的数据对实验结果进行评估。

实验分为4 个部分:1)计算同现向量;2)计算向量的Renyi 熵多样性及区位熵;3)通过卡茨评分学习模型参数;4)将模型参数代入剩余数据集检验。

首先，为了提高数据的处理效率，采用Hadoop［15］分布式平台下MapReduce 框架［16］计算同现向量。

处理过程分为2 步:1)Map 将标签信息以条目编号分组，Reduce 得到每个条目下各个用户的所有标签。2)Map 计算各个条目中出现局部同现向量，并以用户关系对进行分组，Reduce 将局部同现向量合并，从而获得完整的同现向量。在第一步中同时计算各个条目的区位熵，而在第二步的Reduce 过程上，可以计算同现向量的Renyi 熵的多样性。在得到数据集的用户同现向量之后，通过卡茨评分计算关系强度的估计值。使用最小二乘法［17］进行线性回归，则α，β，γ 的最优值可由公式(9)获得:

最后，将得到的参数＜α，β，γ ＞代入公式(7)中，用剩余的数据集求得关系强度Sab。

5.3 实验结果

在剩余的数据集中，对计算结果使用召回率与准确率进行评估。召回率和准确率与关系强度阈值的关系如图1 所示。图中横坐标为关系强度阈值，纵坐标为百分比。随着关系强度阈值的提高，召回率逐渐下降，准确率逐渐提高。

图1 模型的召回率与准确率

6 结束语

本文提出了一种基于社交网络主题文本推断关系强度的熵模型。首先介绍了香农熵和Renyi 熵用于分析在用户间同现向量多样性的计算方法，然后介绍了区位熵对热门主题权重的修正方法，最后使用卡茨评分对用户在社交网络上的关系强度进行估计，并用于模型学习。获得的参数结果在召回率和准确率上都有良好的表现。

［1］王亮.SNS 社交网络发展现状及趋势［J］.现代电信科技，2009，39(6):9-13.

［2］周鹏飞.国内有关SNS 网站的研究综述［J］.现代情报，2010，30(7):174-177.

［3］刘耀庭.社交网络结构研究［D］.杭州:浙江大学，2008.

［4］Pham H，Shahabi C，Liu Yan.Ebm:An entropy-based model to infer social strength from spatiotemporal data［C］// ACM SIGMOD Conference.2013:265-276.

［5］李冠国.多样性指数的应用［J］.海洋科学，1981(2):4-8.

［6］Jost L.Entropy and diversity［J］.Oikos，2006，113(2):363-375.

［7］Maszczyk T，Duch W.Comparison of Shannon，Renyi and Tsallis entropy used in decision trees［C］// Proceedings of the 9th Internation Conference on Artificial Intelligence and Soft Computing-ICAISC 2008.Springer Berlin Heidelberg，2008:643-651.

［8］˙Zyczkowski K.Rényi extrapolation of Shannon entropy［J］.Open Systems ＆ Information Dynamics，2003，10(3):297-310.

［9］Renyi A.On measures of entropy and information［C］//Fourth Berkeley Symposium on Mathematical Statistics and Probability.1961:547-561.

［10］Cranshaw J，Toch E，Hong J，et al.Bridging the gap between physical location and online social networks［C］//Proceedings of the 12th ACM International Conference on Ubiquitous Computing.2010:119-128.

［11］Adamic L A，Adar E.Friends and neighbors on the web［J］.Social Networks，2003，25(3):211-230.

［12］Liben Nowell D，Kleinberg J.The link-prediction problem for social networks［J］.Journal of the American Society for Information Science and Technology，2007，58(7):1019-1031.

［13］余学军.六度分割理论成就SNS［J］.信息网络，2009(11):37-37.

［14］Wu H，Sorathia V，Prasanna V K.When diversity meets speciality:Friend recommendation in online social networks［J］.Human，2013，1(1):52-60.

［15］Lam C.Hadoop in Action［M］.Manning Publications Co.，2010.

［16］Miner D，Shook A.MapReduce Design Patterns:Building Effective Algorithms and Analytics for Hadoop and Other Systems［M］.O’Reilly Media，Inc.，2012.

［17］Bishop C M.Pattern Recognition and Machine Learning［M］.New York:Springer，2006.