基于時(shí)間與數(shù)據(jù)場(chǎng)聚類的社交推薦模型研究

鄧曦輝

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

【關(guān)鍵詞】社交網(wǎng)絡(luò) 聚類算法 數(shù)據(jù)場(chǎng) 推薦模型

很多傳統(tǒng)的推薦算法都能應(yīng)用到社交網(wǎng)絡(luò)的推薦中，推薦研究大多集中在如何計(jì)算用戶的影響力，把影響力大的用戶作為被推薦的對(duì)象。Kwak利用關(guān)注者數(shù)量、轉(zhuǎn)發(fā)數(shù)量來(lái)估計(jì)一個(gè)用戶的影響力;Golder等人研究了多種用戶相似度計(jì)算方法來(lái)推薦用戶。Kapanipathi利用語(yǔ)義網(wǎng)的方法來(lái)過(guò)濾Twitter中的消息，從而向用戶提供符合其個(gè)性化的偏好的消息。Abel等研究了如何利用twitter中的活動(dòng)來(lái)為用戶建模和提供個(gè)性化服務(wù)。這些推薦都不能完全適用于社交網(wǎng)絡(luò)推薦，他們都沒(méi)有討論時(shí)間因素對(duì)模型構(gòu)建的影響，因?yàn)橛脩舻钠貌⒉皇且怀刹蛔兊模请S著時(shí)間在改變。

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

1 數(shù)據(jù)場(chǎng)介紹

2 基于數(shù)據(jù)場(chǎng)的聚類算法

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

確定勢(shì)場(chǎng)分布的局部極值點(diǎn)和鞍點(diǎn)，首先求得△P（x）=0的所有臨界點(diǎn)，然后根據(jù)f（x）的二階導(dǎo)數(shù)構(gòu)成的Hesse矩陣的特征值對(duì)臨界點(diǎn)進(jìn)行分類。給定臨界點(diǎn)x，令l1n是Hesse矩陣的d個(gè)特征值，其中d>-2是空間維數(shù)。如果ld<0，x對(duì)應(yīng)勢(shì)場(chǎng)分布的一個(gè)局部極大值點(diǎn);若l1>0，x為勢(shì)場(chǎng)分布的一個(gè)局部極小值點(diǎn);若l1，12，…，l_n不為0，且特征值大于0和特征值小于0的個(gè)數(shù)都大于0，則x為勢(shì)場(chǎng)分布的一個(gè)鞍點(diǎn)。算法1給出具體數(shù)據(jù)場(chǎng)聚類算法的步驟。

算法l數(shù)據(jù)場(chǎng)聚類算法

輸入：空間中包含n個(gè)對(duì)象的數(shù)據(jù)集D= {x1，x2，…x_n）

步驟：

（1）從數(shù)據(jù)集D中隨機(jī)抽取n_sample<

（2）搜索求得空間中勢(shì)場(chǎng)分布的所有拓?fù)渑R界點(diǎn);

（3）根據(jù)Hesse矩陣的特征值確定局部極大值和鞍點(diǎn);

（4）以勢(shì)函數(shù)的局部極大值點(diǎn)為聚類中心，形成數(shù)據(jù)的初始劃分;

（5）根據(jù)正規(guī)鞍點(diǎn)對(duì)初始聚類進(jìn)行迭代合并，得到層次聚類結(jié)果。

3 數(shù)據(jù)場(chǎng)聚類與時(shí)間關(guān)聯(lián)構(gòu)建用戶興趣模型

首先把微博消息表示為一個(gè)多維的向量，相當(dāng)于數(shù)據(jù)空間中的一個(gè)數(shù)據(jù)點(diǎn)。利用數(shù)據(jù)場(chǎng)聚類算法進(jìn)行聚類，把聚類中心看作用戶興趣偏好。

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

如果把數(shù)據(jù)點(diǎn)的質(zhì)量與發(fā)布時(shí)間關(guān)聯(lián)，那么每個(gè)數(shù)據(jù)點(diǎn)的勢(shì)值不僅與距離有關(guān)，還與數(shù)據(jù)點(diǎn)的質(zhì)量有關(guān)，這樣得到的用戶興趣偏好模型稱為數(shù)據(jù)場(chǎng)的動(dòng)態(tài)用戶偏好模型，記為T(mén)ime-Datafield（TD）模型。根據(jù)文獻(xiàn)[5]，數(shù)據(jù)點(diǎn)質(zhì)量隨時(shí)間變化的影響力函數(shù)表示為式（3）。

其中，α、βγ都是常數(shù)，△t是時(shí)間差，即當(dāng)前時(shí)間值與該條微博消息的時(shí)間值的差。數(shù)據(jù)點(diǎn)的時(shí)間不一樣，它的質(zhì)量也就不一樣，因此它的勢(shì)值也就不一樣。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)準(zhǔn)備

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

4.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)利用python的LDA工具包提取出每條微博消息的主題向量，設(shè)置的主題個(gè)數(shù)為50。在動(dòng)態(tài)用戶興趣偏好模型的構(gòu)建中，時(shí)間相關(guān)的影響力函數(shù)公式（3）的參數(shù)α=1，β=5，γ=86400/30。效用值是待推薦消息的主題向量到該主題向量所在類的類中心的距離的倒數(shù)。利用效用值表示微博消息與用戶相關(guān)的程度，按效用值的從大到小推薦消息。

4.3 結(jié)果與分析

評(píng)價(jià)一個(gè)推薦結(jié)果的好壞有很多指標(biāo)，該實(shí)驗(yàn)使用的指標(biāo)是息檢索領(lǐng)域中得到廣泛認(rèn)可的K位置成功率（Success at Rank K，S@K）、K位置精度（Precision at Rank K，P@K）、平均查準(zhǔn)率均值（Mean Average Precision，MAP）。

如表1所示，在S@K指標(biāo)上，TD比NonTD的值大，因此，動(dòng)態(tài)用戶偏好模型優(yōu)于相應(yīng)的靜態(tài)偏好模型。

如表2所示，在P@K指標(biāo)上，在K值相同時(shí)，靜態(tài)偏好模型的P@K值比相應(yīng)的動(dòng)態(tài)的偏好模型的P@K值小。

如表3所示，在MAP指標(biāo)上，在相同的聚類框架下，動(dòng)態(tài)用戶偏好模型比靜態(tài)用戶偏好模型的值大，說(shuō)明加入時(shí)間因素的動(dòng)態(tài)模型比靜態(tài)模型在MAP上表現(xiàn)要好。

5 結(jié)論

通過(guò)該實(shí)驗(yàn)可以得出，在該實(shí)驗(yàn)的評(píng)估指標(biāo)下，隨時(shí)間變化的動(dòng)態(tài)用戶偏好模型比相應(yīng)的靜態(tài)模型更能準(zhǔn)確地刻畫(huà)用戶當(dāng)前的興趣偏好。

參考文獻(xiàn)

[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].軟件學(xué)報(bào)，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.