社交網絡下非結構化數據協同過濾推薦算法改進

王騰飛，孫 華

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

社交網絡下非結構化數據協同過濾推薦算法改進

王騰飛，孫 華

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

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

推薦算法；協同過濾；粗集；相似性；非結構化數據

0 引言

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

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

1 協同過濾

1.1 協同過濾概述

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

1.2 協同過濾優缺點

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

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

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

然而傳統基于用戶的協同效率算法仍有以下缺陷[8]：

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

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

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

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

2 基于粗集的快速協同過濾模型

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

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

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

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

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

2.1 相似性指標

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

2.2 用戶和項目的粗集

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

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

3 基于信任的協同過濾

3.1 信任的定義及屬性

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

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

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

（3）上下文相關性：信任只表示某個領域的信任，對于其他領域可能是無效的。

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

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

3.2 信任度和相似度計算

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

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

3.3 基于信任的協同過濾框架

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

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

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

3.4 算法流程

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

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

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

（4）根據評分公式進行預測，將結果推薦給初始用戶。

4 總結與展望

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

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

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

[2] 譚學清, 黃翠翠, 羅琳. 社會化網絡中信任推薦研究綜述[J]. 現代圖書情報技術. 2014(11).

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

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

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

[6] 張富國. 基于社交網絡的個性化推薦技術[J]. 小型微型計算機系統. 2014(7).

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

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

[9] 孫冬婷, 何濤, 張福海. 推薦系統中的冷啟動問題研究綜述[J]. 計算機與現代化. 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

本文著錄格式：王騰飛，孫華. 社交網絡下非結構化數據協同過濾推薦算法改進[J]. 軟件，2017，38（10）：169-172

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