王騰飛，孫 華

（1. 中車(chē)青島四方機(jī)車(chē)車(chē)輛股份有限公司，山東 青島 266100）

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

王騰飛，孫 華

（1. 中車(chē)青島四方機(jī)車(chē)車(chē)輛股份有限公司，山東 青島 266100）

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

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

0 引言

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

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

1 協(xié)同過(guò)濾

1.1 協(xié)同過(guò)濾概述

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

1.2 協(xié)同過(guò)濾優(yōu)缺點(diǎn)

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

（1）可以過(guò)濾一些機(jī)器解析相對(duì)困難的項(xiàng)目，例如藝術(shù)品、電影和音樂(lè)等，以及一些抽象的概念，例如思想、品味和評(píng)論等。

（2）可以推薦出讓用戶出乎意料的項(xiàng)目。

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

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

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

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

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

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

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

其中U,R,T表示有限用戶組，項(xiàng)目和標(biāo)簽，Eurt描述了具有特定標(biāo)簽的項(xiàng)目。

只看用戶方面，我們可以分類(lèi)出用戶-項(xiàng)目和用戶-標(biāo)簽

因此，用戶可以通過(guò)資源使用和注釋動(dòng)作的信息來(lái)表征。換句話說(shuō)就是可以被表示為兩個(gè)向量：用戶項(xiàng)目向量和用戶標(biāo)簽向量。其中用戶項(xiàng)目向量可以表示為：

我們可以使用相同的建模方式對(duì)項(xiàng)目和標(biāo)簽結(jié)點(diǎn)進(jìn)行建模。相似的用戶標(biāo)簽向量表示為：

2.1 相似性指標(biāo)

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

2.2 用戶和項(xiàng)目的粗集

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

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

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

3.1 信任的定義及屬性

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

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

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

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

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

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

3.2 信任度和相似度計(jì)算

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

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

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

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

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

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

3.4 算法流程

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

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

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

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

4 總結(jié)與展望

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

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

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

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

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

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

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

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

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

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

[9] 孫冬婷, 何濤, 張福海. 推薦系統(tǒng)中的冷啟動(dòng)問(wèn)題研究綜述[J]. 計(jì)算機(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é)同過(guò)濾推薦算法改進(jìn)[J]. 軟件，2017，38（10）：169-172

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