鄧曦輝

摘要 向用戶推薦其感興趣的信息是推薦系統(tǒng)的主要目標。客觀地確定用戶的興趣中心是社交網絡推薦系統(tǒng)需要解決的首要問題，然而，用戶的興趣會隨著時間而改變。本文提出加入時間因素的數據場聚類算法，根據動態(tài)變化的用戶興趣，實現主題信息的推薦。實驗表明該推薦算法更具有客觀性，推薦的信息更具有價值性。

【關鍵詞】社交網絡 聚類算法 數據場 推薦模型

很多傳統(tǒng)的推薦算法都能應用到社交網絡的推薦中，推薦研究大多集中在如何計算用戶的影響力，把影響力大的用戶作為被推薦的對象。Kwak利用關注者數量、轉發(fā)數量來估計一個用戶的影響力;Golder等人研究了多種用戶相似度計算方法來推薦用戶。Kapanipathi利用語義網的方法來過濾Twitter中的消息，從而向用戶提供符合其個性化的偏好的消息。Abel等研究了如何利用twitter中的活動來為用戶建模和提供個性化服務。這些推薦都不能完全適用于社交網絡推薦，他們都沒有討論時間因素對模型構建的影響，因為用戶的偏好并不是一成不變的，而是隨著時間在改變。

本文提出了一種新的聚類算法，將數據場方法與時間相結合確定聚類中心與聚類類別個數，目的在于根據隨時間動態(tài)變化的用戶興趣中心推薦主題信息，使信息更客觀，更具價值性。

1 數據場介紹

2 基于數據場的聚類算法

基于數據場的聚類思想首先是優(yōu)選影響因子σ產生合理的勢場分布，由于勢場分布的局部極大值點相當于一個“虛擬場源”，所有數據對象在各自的“虛擬場源”的吸引下呈現自組織聚集特性，因此可以將勢場分布的局部極大值視為聚類中心，形成數據的初始劃分，然后根據兩個局部極大值點之間的正規(guī)鞍點迭代合并初始聚類，從而形成不同層次的聚類劃分。

確定勢場分布的局部極值點和鞍點，首先求得△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）根據正規(guī)鞍點對初始聚類進行迭代合并，得到層次聚類結果。

3 數據場聚類與時間關聯構建用戶興趣模型

首先把微博消息表示為一個多維的向量，相當于數據空間中的一個數據點。利用數據場聚類算法進行聚類，把聚類中心看作用戶興趣偏好。

如果把每個數據點的質量設置為相同值，那么每個數據點在某一點勢值只與這兩點間的距離有關，這樣得到的用戶興趣偏好模型稱為數據場的靜態(tài)用戶偏好模型，記為Non-Time-Datafield（NonTD）模型。

如果把數據點的質量與發(fā)布時間關聯，那么每個數據點的勢值不僅與距離有關，還與數據點的質量有關，這樣得到的用戶興趣偏好模型稱為數據場的動態(tài)用戶偏好模型，記為Time-Datafield（TD）模型。根據文獻[5]，數據點質量隨時間變化的影響力函數表示為式（3）。

其中，α、βγ都是常數，△t是時間差，即當前時間值與該條微博消息的時間值的差。數據點的時間不一樣，它的質量也就不一樣，因此它的勢值也就不一樣。

4 實驗結果與分析

4.1 數據準備

以新浪微博為載體，利用新浪微博API，以ID為1894126021的用戶為種子，總共爬取了6312位用戶的12902816條微博信息，消息包括每條微博的發(fā)布時間、關注人的數量、被關注的數量及評論、轉發(fā)數量等。利用中文分詞工具對微博消息進行分詞，去除消息中的停用詞，并利用核密度估計算法對微博消息噪音進行處理。

4.2 實驗設置

實驗利用python的LDA工具包提取出每條微博消息的主題向量，設置的主題個數為50。在動態(tài)用戶興趣偏好模型的構建中，時間相關的影響力函數公式（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的值大，因此，動態(tài)用戶偏好模型優(yōu)于相應的靜態(tài)偏好模型。

如表2所示，在P@K指標上，在K值相同時，靜態(tài)偏好模型的P@K值比相應的動態(tài)的偏好模型的P@K值小。

如表3所示，在MAP指標上，在相同的聚類框架下，動態(tài)用戶偏好模型比靜態(tài)用戶偏好模型的值大，說明加入時間因素的動態(tài)模型比靜態(tài)模型在MAP上表現要好。

5 結論

通過該實驗可以得出，在該實驗的評估指標下，隨時間變化的動態(tài)用戶偏好模型比相應的靜態(tài)模型更能準確地刻畫用戶當前的興趣偏好。

參考文獻

[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.