基于时间与数据场聚类的社交推荐模型研究

邓曦辉

摘要 向用户推荐其感兴趣的信息是推荐系统的主要目标。客观地确定用户的兴趣中心是社交网络推荐系统需要解决的首要问题，然而，用户的兴趣会随着时间而改变。本文提出加入时间因素的数据场聚类算法，根据动态变化的用户兴趣，实现主题信息的推荐。实验表明该推荐算法更具有客观性，推荐的信息更具有价值性。

【关键词】社交网络 聚类算法 数据场 推荐模型

很多传统的推荐算法都能应用到社交网络的推荐中，推荐研究大多集中在如何计算用户的影响力，把影响力大的用户作为被推荐的对象。Kwak利用关注者数量、转发数量来估计一个用户的影响力;Golder等人研究了多种用户相似度计算方法来推荐用户。Kapanipathi利用语义网的方法来过滤Twitter中的消息，从而向用户提供符合其个性化的偏好的消息。Abel等研究了如何利用twitter中的活动来为用户建模和提供个性化服务。这些推荐都不能完全适用于社交网络推荐，他们都没有讨论时间因素对模型构建的影响，因为用户的偏好并不是一成不变的，而是随着时间在改变。

本文提出了一种新的聚类算法，将数据场方法与时间相结合确定聚类中心与聚类类别个数，目的在于根据随时间动态变化的用户兴趣中心推荐主题信息，使信息更客观，更具价值性。

1 数据场介绍

2 基于数据场的聚类算法

基于数据场的聚类思想首先是优选影响因子σ产生合理的势场分布，由于势场分布的局部极大值点相当于一个“虚拟场源”，所有数据对象在各自的“虚拟场源”的吸引下呈现自组织聚集特性，因此可以将势场分布的局部极大值视为聚类中心，形成数据的初始划分，然后根据两个局部极大值点之间的正规鞍点迭代合并初始聚类，从而形成不同层次的聚类划分。

确定势场分布的局部极值点和鞍点，首先求得△P（x）=0的所有临界点，然后根据f（x）的二阶导数构成的Hesse矩阵的特征值对临界点进行分类。给定临界点x，令l1n是Hesse矩阵的d个特征值，其中d>-2是空间维数。如果ld<0，x对应势场分布的一个局部极大值点;若l1>0，x为势场分布的一个局部极小值点;若l1，12，…，l_n不为0，且特征值大于0和特征值小于0的个数都大于0，则x为势场分布的一个鞍点。算法1给出具体数据场聚类算法的步骤。

算法l数据场聚类算法

输入：空间中包含n个对象的数据集D= {x1，x2，…x_n）

步骤：

（1）从数据集D中随机抽取n_sample<

（2）搜索求得空间中势场分布的所有拓扑临界点;

（3）根据Hesse矩阵的特征值确定局部极大值和鞍点;

（4）以势函数的局部极大值点为聚类中心，形成数据的初始划分;

（5）根据正规鞍点对初始聚类进行迭代合并，得到层次聚类结果。

3 数据场聚类与时间关联构建用户兴趣模型

首先把微博消息表示为一个多维的向量，相当于数据空间中的一个数据点。利用数据场聚类算法进行聚类，把聚类中心看作用户兴趣偏好。

如果把每个数据点的质量设置为相同值，那么每个数据点在某一点势值只与这两点间的距离有关，这样得到的用户兴趣偏好模型称为数据场的静态用户偏好模型，记为Non-Time-Datafield（NonTD）模型。

如果把数据点的质量与发布时间关联，那么每个数据点的势值不仅与距离有关，还与数据点的质量有关，这样得到的用户兴趣偏好模型称为数据场的动态用户偏好模型，记为Time-Datafield（TD）模型。根据文献[5]，数据点质量随时间变化的影响力函数表示为式（3）。

其中，α、βγ都是常数，△t是时间差，即当前时间值与该条微博消息的时间值的差。数据点的时间不一样，它的质量也就不一样，因此它的势值也就不一样。

4 实验结果与分析

4.1 数据准备

以新浪微博为载体，利用新浪微博API，以ID为1894126021的用户为种子，总共爬取了6312位用户的12902816条微博信息，消息包括每条微博的发布时间、关注人的数量、被關注的数量及评论、转发数量等。利用中文分词工具对微博消息进行分词，去除消息中的停用词，并利用核密度估计算法对微博消息噪音进行处理。

4.2 实验设置

实验利用python的LDA工具包提取出每条微博消息的主题向量，设置的主题个数为50。在动态用户兴趣偏好模型的构建中，时间相关的影响力函数公式（3）的参数α=1，β=5，γ=86400/30。效用值是待推荐消息的主题向量到该主题向量所在类的类中心的距离的倒数。利用效用值表示微博消息与用户相关的程度，按效用值的从大到小推荐消息。

4.3 结果与分析

评价一个推荐结果的好坏有很多指标，该实验使用的指标是息检索领域中得到广泛认可的K位置成功率（Success at Rank K，S@K）、K位置精度（Precision at Rank K，P@K）、平均查准率均值（Mean Average Precision，MAP）。

如表1所示，在S@K指标上，TD比NonTD的值大，因此，动态用户偏好模型优于相应的静态偏好模型。

如表2所示，在P@K指标上，在K值相同时，静态偏好模型的P@K值比相应的动态的偏好模型的P@K值小。

如表3所示，在MAP指标上，在相同的聚类框架下，动态用户偏好模型比静态用户偏好模型的值大，说明加入时间因素的动态模型比静态模型在MAP上表现要好。

5 结论

通过该实验可以得出，在该实验的评估指标下，随时间变化的动态用户偏好模型比相应的静态模型更能准确地刻画用户当前的兴趣偏好。

参考文献

[1] Kwak H，Lee C，Park H，et al. What isTwitter， a social network or a newsmedia？ [A]. Proceedings of the 19thInternat ional Conference on WorldWide Web[C]， ACM， 2010： 591-600.

[2] Golder S， Yardi S， Marwick A， et al.A structural approach to contactrecommendations in online socialnetworks [A]. Workshop on Searchin Social Media at ACM SIGIR[C].2009： 412-419

[3] Kapanipathi P， Orlandi F， Sheth A，et al. Personalized Filtering of theTwitter Stream[A]. SPIM Workshop atISWC [C].2011： 6-13.

[4]李德毅，刘常昱.不确定性人工智能[J].软件学报，2004 （15）：158 3-1592

[5] Ding Y， Li X. Time weightcollaborative filtering [A].Proceedings of the 14th ACMinternat ional conference onInformation and knowledgemanagement [C]， ACM， 2005： 485-492.