社交網(wǎng)絡(luò)下非結(jié)構(gòu)化數(shù)據(jù)協(xié)同過濾推薦算法改進

王騰飛，孫 華

（1. 中車青島四方機車車輛股份有限公司，山東 青島 266100）

社交網(wǎng)絡(luò)下非結(jié)構(gòu)化數(shù)據(jù)協(xié)同過濾推薦算法改進

王騰飛，孫 華

（1. 中車青島四方機車車輛股份有限公司，山東 青島 266100）

現(xiàn)代社交網(wǎng)絡(luò)中存在著數(shù)量巨大且無序的非結(jié)構(gòu)化數(shù)據(jù)，針對非結(jié)構(gòu)化數(shù)據(jù)采取協(xié)同過濾十分必要。傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法由于其本身原理，其相似性計算的時間復(fù)雜度極高，本文通過引入粗集，高速分割用戶和用戶項目，直接計算分割后各組質(zhì)心與初始用戶的相似性來解決該問題。但數(shù)據(jù)易稀疏以及冷啟動的問題仍未解決，對此在引入粗集的基礎(chǔ)上加入信任概念，根據(jù)用戶信任度以及信任的傳遞性緩解以上問題。在增強精確度的基礎(chǔ)上還提高推薦速度。該模型還可以方便的擴展。

推薦算法；協(xié)同過濾；粗集；相似性；非結(jié)構(gòu)化數(shù)據(jù)

0 引言

在許多社交網(wǎng)絡(luò)系統(tǒng)中，存儲，發(fā)布和共享項目的便利性使得用戶在獲取有趣信息時會產(chǎn)生信息超載。越來越多有影響力的社交網(wǎng)絡(luò)為用戶提供了標記URL鏈接，電影，照片等項目的標簽。標簽提供的信息顯示用戶的興趣，更多被描繪了的項目準確地為數(shù)據(jù)分析和知識發(fā)現(xiàn)提供更多的機會和資源[1-3]。個性化推薦系統(tǒng)是用于改善用戶體驗和幫助用戶獲取適合自己興趣的信息的系統(tǒng)，是社交網(wǎng)絡(luò)中最常見的模塊之一。其中最為流行的是基于協(xié)同過濾的推薦系統(tǒng)，但由于其是通過項目和注釋操作計算所有用戶對的相似性，從而對時間復(fù)雜度提出了非常高的要求，強烈地抑制了推薦速度。本文為了克服這個缺點，利用粗集的方法，高速分割類似的用戶和相關(guān)項目，以增強基于用戶的協(xié)同過濾性能[4]，為社會標簽系統(tǒng)開發(fā)快速協(xié)作用戶模型。最重要的是沒有損失精確度。

另外隨著互聯(lián)網(wǎng)技術(shù)以及智能化手機的不斷發(fā)展，社交網(wǎng)絡(luò)用戶量增長迅速，據(jù)預(yù)測，2017年中國社交網(wǎng)絡(luò)用戶將達到6.62億，其中的主要增長來源于 50-60歲的老年群眾。而社交網(wǎng)絡(luò)是推薦系統(tǒng)的重要信息來源。一些諸如阿里巴巴，京東等電子商務(wù)網(wǎng)站也基于社交網(wǎng)絡(luò)進行了重構(gòu)，努力向社會化電商。事實證明，相比于陌生人和沒有社會影響力的人，用戶更相信身邊的人和有一定社會影響力的人士的推薦，信任作為人際關(guān)系中的重要標準，在很大程度上影響著用戶的決策，因此將信任關(guān)系作為重要維度，與協(xié)同過濾相融合，對于協(xié)同過濾本身的冷啟動和稀疏性問題都能起到較大的緩解[5-6]。

1 協(xié)同過濾

1.1 協(xié)同過濾概述

主要分為在線和離線兩種。在線協(xié)同是指通過在線數(shù)據(jù)分析得出用戶可能產(chǎn)生偏好的項目，而離線協(xié)同是將在線協(xié)同的項目集進行過濾，例如過濾到預(yù)測評分低于閾值的項目或者過濾掉預(yù)測評分在閾值之上但用戶已經(jīng)購買的項目[7]。本論文使用基于用戶的協(xié)同過濾，公式（1）進行相似性計算 公式（2）進行分數(shù)預(yù)測。

1.2 協(xié)同過濾優(yōu)缺點

協(xié)同過濾算法之所以能夠在眾多個性化算法中脫穎而出，主要有以下兩個方面：

（1）可以過濾一些機器解析相對困難的項目，例如藝術(shù)品、電影和音樂等，以及一些抽象的概念，例如思想、品味和評論等。

（2）可以推薦出讓用戶出乎意料的項目。

然而傳統(tǒng)基于用戶的協(xié)同效率算法仍有以下缺陷[8]：

（1）可擴展性。由于在實際網(wǎng)站中用戶和項目達到百萬級甚至千萬級，這就會使用戶-評分矩陣的維度非常的高，并且由于用戶和項目數(shù)量仍會持續(xù)增長，其時間復(fù)雜度會增加的更加劇烈，嚴重影響推薦系統(tǒng)的效率。

（2）稀疏性。實際網(wǎng)站中一般都擁有眾多用戶和項目，且其數(shù)量是不斷增加，然而用戶只對其中非常小的一部分項目產(chǎn)生項目評分（大概只占到所有項目1%），這就導致用戶的評分矩陣非常的稀疏，從而導致搜索到的最近鄰和最近鄰的評分信息都會減少。

（3）冷啟動。冷啟動問題的根源在于“新”，一個新生成的項目是沒有人去評論的，所以該項目不會推薦給任何用戶，推薦系統(tǒng)對該項目是失效的。同樣的，一個新用戶沒有對任何項目產(chǎn)生評論，那么通過相似性計算無法產(chǎn)生任何最近鄰集，則推薦系統(tǒng)也是無效的。

在本文中，我們通過引入粗集的方式緩解第一個缺陷，利用引入信任度緩解后兩個缺陷。

2 基于粗集的快速協(xié)同過濾模型

一個社交網(wǎng)絡(luò)的標簽系統(tǒng)包含用戶的行為（例如標簽項），項目（使用的URL/視頻/圖書/商品）和注釋操作（例如，在應(yīng)用程序中標記/收集），可以表示為用戶項標記的三種形式。

其中U,R,T表示有限用戶組，項目和標簽，Eurt描述了具有特定標簽的項目。

只看用戶方面，我們可以分類出用戶-項目和用戶-標簽

因此，用戶可以通過資源使用和注釋動作的信息來表征。換句話說就是可以被表示為兩個向量：用戶項目向量和用戶標簽向量。其中用戶項目向量可以表示為：

我們可以使用相同的建模方式對項目和標簽結(jié)點進行建模。相似的用戶標簽向量表示為：

2.1 相似性指標

我們考慮共同使用項目和標簽來測量相似度。事實上，高維并稀疏的數(shù)據(jù)對歐式距離是有影響的，當數(shù)據(jù)高維并稀疏時，其歐式距離更為較為集中，而兩對數(shù)據(jù)元素的歐式距離也很相似[9]。因此我們對公式（9）進行改進從而進行相似性評估。β的值設(shè)置為 0.5是由于這兩個類型的余弦相似性遵循類似的分布。

2.2 用戶和項目的粗集

算法關(guān)鍵是用戶和項目的快速分區(qū)。我們使用k均值分割算法，它的相似性度量是基于公式（10）?；诖旨?，我們首先將用戶劃分為互不重疊組。在整個用戶-項目結(jié)構(gòu)中，這些項目還通過用戶項目關(guān)系被劃分成相關(guān)聯(lián)的重疊組。結(jié)合每個用戶組和相關(guān)聯(lián)的項目組，我們將用戶-項目劃分成用戶方面的不同子類[10-12]。雖然粗集算法的步驟與K均值方法中的步驟相似，但其目的不是獲得社會標簽系統(tǒng)的完全收斂的用戶/項目組。因此，不必使算法迭代收斂。K均值算法第一步是將節(jié)點交付給任意組。而第二步，計算每個組的質(zhì)心，并根據(jù)節(jié)點和質(zhì)心的相似度將每個節(jié)點重新分配給新的組，直到多次迭代到一個收斂的結(jié)果。本算法中，迭代數(shù)為 2。因為只要計算用戶的相似之處和每個用戶組的質(zhì)心就能反應(yīng)用戶的相似之處。兩個質(zhì)心方程分別如下：

其中UjCN 是用戶組中的用戶數(shù)，將公式（11）和（12）代入公式（10）中，得新的相似性計算公式：

3 基于信任的協(xié)同過濾

3.1 信任的定義及屬性

社會學家Lhumann指出“信任是降低社會復(fù)雜度的一種方法”[13-14]，用戶之間通過信任形成社交圈，再通過該社交圈進行社交行為，從而不斷地更新和強化信任，因此信任在社交網(wǎng)絡(luò)之中至關(guān)重要。在推薦算法的范疇里，我們使用 Golbeck對信任的定義：假設(shè)用戶B的行為為用戶A的行為帶來了有利的參考和更好的結(jié)果，有利的參考表示相關(guān)性，更好的結(jié)果表示價值性，一旦價值性和參考性同時存在，那么我們可以認為A是信任B的。信任網(wǎng)絡(luò)圖由用戶和具有權(quán)重的有向邊構(gòu)成，其中權(quán)重表示信任度。信任作為一種復(fù)雜的網(wǎng)絡(luò)關(guān)系，具有一些固有屬性[15]。

（1）主觀性：信任是一種主觀判斷，由信任方自身的情況決定，是在一定客觀因素的基礎(chǔ)上做出的自主判斷。正因如此，信任雙方的信任關(guān)系并不是等價的。

（2）非對稱性：信任關(guān)系是有方向性的，是一種單向關(guān)系。

（3）上下文相關(guān)性：信任只表示某個領(lǐng)域的信任，對于其他領(lǐng)域可能是無效的。

（4）傳遞性：在擁有共同上下文相關(guān)性的基礎(chǔ)上，信任可以傳遞并且是逐級遞減的。

（5）動態(tài)性：信任建立之后是時刻變化的，這種變化隨時可能發(fā)生而導致信任在任何情況下發(fā)生更新。

3.2 信任度和相似度計算

我們使用Golbeck等人研究的有關(guān)信任度ta,u的計算方式：

通過對信任網(wǎng)絡(luò)進行廣度優(yōu)先遍歷，我們可以搜索到初始用戶到目標用戶的所有路徑，從而篩選出與目標用戶之間存在的最大信任度的用戶集合，采用加權(quán)平均方法，迭代地更新目標用戶的初始用戶信任。相似度公式采用公式（13）。

3.3 基于信任的協(xié)同過濾框架

對于新的預(yù)測評分公式，將公式（14）帶入傳統(tǒng)的協(xié)同過濾算法項目預(yù)測公式（2）中，形成新的用戶a對項目i的預(yù)測公式：

r代表用戶對自己所有項目的平均分。用戶集合為擁有共同上下文的其他用戶。

對于傳統(tǒng)協(xié)同過濾算法的固有問題，通過引入信任，雖然無法完全解決，但我們可以很好地緩解。只要有一個信任用戶，根據(jù)信任的傳遞性就可以找到諸多其他用戶，豐富評分矩陣，從而使推薦系統(tǒng)重新生效，緩解了冷啟動問題。又例如稀疏性問題，同樣的，依賴于信任的傳遞，我們可以找到比傳統(tǒng)協(xié)同過濾更多的用戶。

3.4 算法流程

（1）去除信任網(wǎng)絡(luò)中的回路?；谛湃蔚膮f(xié)同過濾模型的最大特點是可以根據(jù)信任的傳遞獲得更好的信任度，但信任的傳遞同樣會導致信任網(wǎng)絡(luò)中出現(xiàn)較多的回路。基于現(xiàn)實中人們更加相信自己的主管判斷而不是他人判斷這一事實，我們將所有的回路去掉，只考慮從用戶A到用戶C的直接信用度。同時合并多路徑。這樣，一個雜亂無序的信用網(wǎng)絡(luò)就可以被我們整合的井然有序。

（2）簡化完信用網(wǎng)絡(luò)之后，利用信任算法，我們遞歸的搜索初始用戶的信任用戶（類似于圖論算法中的廣度優(yōu)先遍歷），直到查完所有目標。之后根據(jù)公式計算每個信用路徑的結(jié)果。

（3）根據(jù)每條信用鏈的計算結(jié)果求出初始用戶對目標用戶的信用平均值，大于系統(tǒng)規(guī)定的閾值就將其加入最近鄰用戶集之中。

（4）根據(jù)評分公式進行預(yù)測，將結(jié)果推薦給初始用戶。

4 總結(jié)與展望

傳統(tǒng)基于用戶的協(xié)同過濾模型存在著諸如相似性效率低，冷啟動以及稀疏性等問題，利用粗集的方法進行快速分割，只需計算用戶組的質(zhì)心與初始用戶的相似性，加快了推薦速度。同時將信任維度引入?yún)f(xié)同過濾算法，依賴于信任傳遞性的特點，用信用度替代原本預(yù)測公式中的推薦權(quán)重，可以找到更多的用戶和項目。

對于未來的工作，本人將考慮主要研究基于模型的協(xié)同過濾算法，這是目前學者著重研究的，其可以概括為解決一個問題：即有n個產(chǎn)品和n個消費者數(shù)據(jù)，其中只有部分用戶和部分項目之間有評分，其余評分都是空的，通過已知評分來填補空白評分。關(guān)于該問題，大都使用機器學習算法建模解決，例如關(guān)聯(lián)算法、聚類算法、分類算法、回歸算法、矩陣分解算法和神經(jīng)網(wǎng)絡(luò)等。其中用深度學習做協(xié)同過濾應(yīng)當是今后的一個主流，現(xiàn)在比較流行的是兩層神經(jīng)網(wǎng)絡(luò)的限制玻爾茲曼機，在今后，基于CNN和RNN的協(xié)同過濾應(yīng)當會有更好的效果。本人計劃在改進限制玻爾茲曼機的基礎(chǔ)上，重點研究通過深度學習來填補推薦模型的空白，分析用戶特征和項目特征。

[1] 張振華, 劉瑞芳. 微博社交網(wǎng)絡(luò)中面向機構(gòu)的用戶挖掘[J].軟件, 2013, 34(1): 121-124.

[2] 譚學清, 黃翠翠, 羅琳. 社會化網(wǎng)絡(luò)中信任推薦研究綜述[J]. 現(xiàn)代圖書情報技術(shù). 2014(11).

[3] 李善濤, 肖波. 基于社交網(wǎng)絡(luò)的信息推薦系統(tǒng)[J]. 軟件,2013, 34(12): 41-45.

[4] 顏龍杰. 基于近鄰評分預(yù)測的協(xié)同過濾推薦算法[J]. 軟件,2013, 34(8): 63-66.

[5] 徐妍妍, 王宏志, 高宏, 等. 基于高維稀疏數(shù)據(jù)的k- 分桶高效skyline 查詢算法[J]. 新型工業(yè)化, 2012, 2(8): 41-55.

[6] 張富國. 基于社交網(wǎng)絡(luò)的個性化推薦技術(shù)[J]. 小型微型計算機系統(tǒng). 2014(7).

[7] 郭磊, 馬軍, 陳竹敏. 一種信任關(guān)系強度敏感的社會化推薦算法[J]. 計算機研究與發(fā)展. 2013(9).

[8] 曹一鳴. 協(xié)同過濾推薦瓶頸問題綜述[J]. 軟件. 2012(12).

[9] 孫冬婷, 何濤, 張福海. 推薦系統(tǒng)中的冷啟動問題研究綜述[J]. 計算機與現(xiàn)代化. 2012(5).

[10] Recommender systems survey[J]. J. Bobadilla, F. Ortega, A.Hernando, A. Gutiérrez. Knowledge-Based Systems. 2013.

[11] Jesús Bobadilla, Fernando Ortega, Antonio Hernando, Jesús Bernal. A collaborative filtering approach to mitigate the new user cold start problem[J]. Knowledge-Based Systems. 2011

[12] Yehuda Koren. Factor in the neighbors[J]. ACM Transactions on Knowledge Discovery from Data (TKDD). 2010 (1).

[13] X. Zhu, H. Tian, S. Cai, J. Stat. Mech. Theory Exp[J]. 2014(2014) P07004.

[14] G. Adomavicius, A. Tuzhilin, IEEE Trans. Knowl. Data Eng[J]. 17 (2005) 734-749.

[15] L. Lü, M. Medo, C.H. Yeung, Y.-C. Zhang, Z.-K. Zha g, T.Zhou, Phys. Rep[J]. 519 (2012): 1–49.

Improvement of Unstructured Data Collaborative Filtering Recommendation Algorithm in Social Network

WANG Teng-fei1, SUN Hua2
(CRRC QINGDAO SIFANG CO., LTD.Qingdao Shandong, 266100)

There is a large amount of unstructured data in the modern social network, and it is necessary to adopt collaborative filtering for unstructured data. The traditional user-based collaborative filtering recommendation algorithm has a very high time complexity in its similarity calculation due to its own principle. By introducing the coarse cluster, high-speed segmentation user and user project, this paper calculates the similarity between the groups and the initial users To solve the problem. But the data is easy to sparse and cold start problem remains unresolved,which in the introduction of coarse clusters based on the concept of trust, according to the user trust and trust to ease the above problems. On the basis of enhanced accuracy to improve the recommended speed. The model can also be easily extended.

: Recommended algorithm; Collaborative filtering; Coarse cluster; Similarity; Unstructured data

TP301.6

A

10.3969/j.issn.1003-6970.2017.10.033

本文著錄格式：王騰飛，孫華. 社交網(wǎng)絡(luò)下非結(jié)構(gòu)化數(shù)據(jù)協(xié)同過濾推薦算法改進[J]. 軟件，2017，38（10）：169-172

王騰飛(1987-)，男，工程師，信息技術(shù)應(yīng)用；孫華(1972-)，男，高級工程師，信息技術(shù)應(yīng)用。