基于神經網絡和社區發現的高維數據推薦系統

唐新宇 張新政 劉保利

1(廣東工商職業技術大學計算機工程學院 廣東 肇慶 526040)2(廣東工業大學自動化學院 廣東 廣州 510090)3(空軍工程大學理學院 陜西 西安 710000)

0 引 言

隨著網絡信息的爆炸式增長，用戶從網絡獲取目標信息的效率降低，許多大型購物網站、新聞網站和視頻網站等集成了推薦系統為用戶提供感興趣的內容[1]。傳統的推薦系統大多根據用戶對項目的評分信息為用戶提供推薦列表，但用戶評分矩陣具有極大的稀疏性，且冷啟動問題和灰羊用戶問題也為推薦系統帶來了極大的挑戰[2]。隨著社交網絡的普及，各種應用場景也包含了復雜的社交關系，例如在購物網站中店鋪和用戶之間存在關注關系，買家之間也存在社交關系[3]。將推薦系統和社交網絡之類的上下文相結合，是解決推薦系統稀疏性問題、冷啟動問題和灰羊用戶問題的一種方式[4]。

文獻[5]挖掘社交網絡來發現隱藏的用戶-物品偏好關系，然后對用戶建模分析并選擇合適的推薦引擎進行個性化物品推薦，該算法展開了對用戶社交關系和隱性反饋的研究，加入了社交關系、人口統計學信息和用戶消費記錄等隱性信息。文獻[6]先基于社交網絡將用戶分組，再使用局部敏感哈希技術為分組提供推薦列表。文獻[7]設計了好友強度指標計算社交圈的緊密性，然后根據好友強度和社交圈緊密度預測用戶的偏好，提高推薦的準確率。文獻[8]將社交網絡關系引入協同過濾推薦系統中，從社交網絡提取用戶偏好和社區偏好信息并建模為質量函數，通過Dempster組合規則將多個偏好融合，由此提高協同過濾推薦系統的推薦性能。隨著社交關系日益復雜，用戶可能受到多重社交關系和上下文的影響，這些影響因素稱為“上下文維度”[9]?，F有的方案[5-8]為了提高推薦系統的性能，大多考慮了全部的“上下文維度”，導致計算復雜度提高，并且對推薦的準確率也產生了負面的影響。

為了解決“上下文維度”問題，本文設計了基于神經網絡和社區發現的推薦系統。建立多層感知神經網絡來識別最相關的上下文維度，學習上下文維度對用戶偏好的影響力；設計了社區發現算法將用戶分組，解決稀疏性問題并降低數據的維度；采用張量分解模型處理相關上下文維度，提高處理效率；最終基于上下文信息豐富的真實數據集完成了仿真實驗，實驗結果驗證了本文算法的有效性。

1 總體結構設計

圖1為本文推薦系統的總體結構設計。系統包含4個模塊：(1) 采用神經網絡識別影響力大的上下文維度；(2) 基于社交關系、地理位置、人口統計學將用戶分組；(3) 基于用戶分組的張量分解模型處理上下文維度數據；(4) 產生推薦列表。

圖1 推薦系統的總體結構

2 基于神經網絡的上下文維度分析

通過多層感知神經網絡[10]分析上下文維度，識別影響力大的上下文維度。

2.1 訓練神經網絡

多層感知神經網絡分為輸入層、隱層和輸出層。以電影推薦數據集LDOS-CoMoDa[11]為例，設數據集為D，D共有12個上下文特征，12個上下文的維度為48，輸入層節點的數量等于上下文的維度。假設上下文為c1=時間{早晨,下午,晚上,夜間}，c2=日期{工作日,周末},c3=互動{第1次觀看電影，第n次觀看電影}。神經網絡的輸入和輸出關系表示為：

OI=II

(1)

式中：OI為輸入層的輸出；II為輸入層的輸入。

輸入層節點與隱層節點連接，隱層節點與輸出層節點連接，連接的權重分別設為wij和wjk，通過訓練神經網絡確定wij和wjk。隱層節點是輸入數據的加權調和函數，根據試錯實驗的結果將隱層節點數量設為11，此時驗證實驗的精度最高。隱層的神經元向量定義為：

h(j)=f(w(j)Th(j-1)+b(j))

(2)

式中：h(j)表示j層神經元的向量；w(j)為j層的權重矩陣；b(j)為偏差項；f為激活函數。

隱層節點計算輸入量的加權調和值，計算方法為：

(3)

式中：IH為隱層節點的輸入；wij為輸入層到隱層連接的權重；OIi為輸入層第i個節點的輸出；bH為隱層的偏差；p為預測器的分級數；h為隱層的神經元數量。采用單隱層網絡減少計算復雜度，如圖2所示。

圖2 上下文維度的單層神經網絡

隱層節點支持在預測器和響應變量之間建模非線性關系，因為本文神經網絡為前饋神經網絡，所以采用雙曲正切激活函數作為輸入到輸出的映射函數。雙曲正切激活函數的輸出為OH=φ(IH)，φ(IH)定義為：

(4)

每個預測類別創建一個輸出層神經元，如果用戶滿意度范圍為1～5，那么輸出層的神經元數量為5。輸入層到輸出層的映射函數定義為：

(5)

式中：IO為輸出層的輸入；wjk為隱層到輸出層連接的權重；OHj為第j個隱層神經元的輸出；bO為輸出層的輸入偏差；j為隱層的神經元數量；t為目標類別的數量。

Softmax函數能夠預測多分類數據的輸出，所以采用Softmax函數作為輸出層的激活函數。神經網絡的最終輸出定義為：

(6)

通過最小化交叉熵誤差獲得Softmax激活函數期望的輸出。計算每個目標類別觀察值和實驗值的交叉熵誤差之和E：

(7)

式中：t為目標類別的數量(實例中為5)；y為樣本o是否被正確分類的標記值；p為觀察樣本的預測率。

然后通過反向傳播訓練神經網絡，最小化預測誤差。在反向傳播階段比較實際輸出和期望輸出，如果存在誤差，則調節權重來獲得接近期望的輸出。使用梯度下降法計算最小化誤差的權重，將誤差對每個權重向量δwij求偏導δE：

Δwij=-l[δE/δwij]

(8)

式中:l為學習率。

學習率和動量是反向傳播訓練的兩個重要參數。動量m設為0.9。采用衰減的學習率因子β，定義為：

β=(1/mK)×ln(η0/ηlow)

(9)

式中：η0為初始化學習率，設為0.4；ηlow為學習率的下限，設為0.001；K為訓練樣本的數量。

2.2 識別影響力大的上下文維度

例子中共有12個上下文特征，但每個維度的重要性不同，因此需要識別出對用戶偏好影響力大的維度。在神經網絡模型中則是選出對評分影響較大的預測器。算法1是評估上下文維度重要性的算法。

算法1上下文維度的重要性評估算法

輸入：輸入層-隱層連接權重wij，隱層-輸出層連接權重wjk。

輸出：上下文維度ci的相對重要性。

For each上下文維度cido

計算每個隱層神經元的wj=wij×wjk；

將wj除以j的輸入神經元總數量；

//j為隱層神經元

對所有輸入神經元的值求和Sum；

將Sum除以輸入神經元的數量，其結果為上下文維度的相對重要性。

3 基于社區發現的用戶分組

設計了基于社區發現的用戶分組算法，以用戶的社交關系、用戶的人口統計信息(年齡、性別等)、地理位置等信息作為社區發現的判斷依據。該模塊能夠利用用戶組的相似性，解決稀疏性問題。目前的社區發現方法存在兩個問題：(1) 采用隨機參數導致穩定性較弱；(2) 需要預設社區數量。這兩個問題導致這些方法無法適用于推薦系統，所以本文設計了基于子空間傳播的社區發現算法，包括以下3個步驟：

步驟1使用線性稀疏編碼將圖映射到低維空間。

步驟2檢測社區的代表中心。

步驟3通過標簽傳播機制構建最終的社區。

圖3為用戶分組的流程圖。

圖3 用戶分組的流程圖

3.1 子空間映射

根據子空間的自表達特性：子空間內的每個數據點可表示為其他點的線性組合[12]。借助該特性將鄰接矩陣映射到低維空間，低維空間內社區結構的分離度高于原高維空間。首先計算兩個節點的最短路徑，然后采用高斯核將網絡映射到全局的相似性空間，最終采用線性稀疏編碼將相似性空間映射到低維空間。

首先為每個節點vi生成一個距離向量Gi。距離向量包括：用戶的社交關系、用戶的人口統計信息(年齡、性別等)、地理位置。該向量是從vi到其他所有節點的最短路徑集合，所有向量的集合表示為G∈Rn×n，G=[G1,G2,…,Gn]，n為節點數量。然后通過以下的高斯核函數將距離向量轉化為相似性評分：

(10)

式中：σs為衰減率計算為(2×G)的平均總標準偏差；⊙為點積運算。社區內連接較為密集，社區間連接較為稀疏，因此同一個社區內節點的最短路徑數量應該小于社區之間。每個節點vi的相似性為其他節點的線性組合：

(11)

式中：αi=[αi(1),αi(2),…,αi(n)]為相似性系數的向量，αi(j)為節點vi到vj的相似性系數；sj是節點vj相似性向量。vi到vj的相似性系數可能不同于vj到vi的相似性，即αi(j)≠αj(i)。

根據文獻[12]一個類內的每個數據點可表示為同一個類內其他數據點的線性組合。因此采用l1-正則化的稀疏線性分解法計算最優相似性系數向量，其目標函數定義為：

(12)

(13)

式中：D為對稱線性稀疏矩陣。

3.2 檢測社區的代表中心

首先使用節點排序策略計算每個節點的全局影響值，然后根據影響值檢測社區的代表中心。該策略的核心思想是社交網絡中的社區一般圍繞有影響力的節點。采用影響力和重要性度量節點在其子空間內的影響值，節點vi的影響值定義為：

(14)

式中：di為D的第i行。該式采用節點密度和距離向量計算節點的影響值。子空間的節點越多或者子空間內節點間相似性更高，該子空間組成社區的概率越大。

子空間內影響值最大的節點被選為社區中心的候選節點，節點vi的子空間定義為：

sSpace(vi)={vj|?j=1,2,…,n,j≠i,D(i,j)>β}

(15)

式中：β定義了每個節點的影響范圍。算法2為社區中心的檢測算法。

算法2社區中心檢測算法。

輸入：β,D,S

輸出：社區中心CC

計算節點重要性Pt；

//使用式(14)計算

CC=NULL；

for eachifrom 1 toN

計算子空間sSpace(vi)；

//使用式(15)計算

for each 節點vjinsSpace(vi)

Tag=TRUE；

ifPt(vj)>Pt(vi) then

Tag=FALSE；

end if

end for

if(Tag==TRUE) then

CC=CC∪{vi}；

end if

end for

3.3 標簽傳播

標簽傳播為每個節點分配社區，包括搜索微社區和構建最終的社區兩個過程。

(1) 搜索微社區。微社區定義為成員間相似性最大的一組節點。初始化將每個社區中心作為一個微社區，然后將其子空間內能夠增強其質量的節點加入該微社區。根據式(16)選擇加入第i個微社區的節點：

CM(Ci)={vj|?j=1,2,…,n,j≠i,JD(Ci,vj)>0}

(16)

式中：Ci為算法1初始化的第i個社區。設JD為局部關系和子空間關系的組合,用于度量節點和微社區的相似性，計算為：

JD(vi,vj)=D(vi,vj)×JS(vi,vj)

(17)

式中：JS為Jaccard相似性矩陣，D為式(13)的結果。JS度量了每對節點的局部密度：

(18)

式中：Γ(vi)為節點vi的相鄰節點集。

采用以下的適應度函數計算節點vj加入社區Ci的質量增益：

ef(Ci,vj)=fCi∪vj-fCi

(19)

f定義為：

(20)

(21)

(22)

淘汰每個微社區的無效節點。該步驟計算每對節點的全局相似性，定義為Jaccard相似性和高斯相似性的乘積：

sim(vi,vj)=S(vi,vj)×JS(vi,vj)

(23)

算法3為建立微社區的程序。

算法3建立微社區的算法。

輸入：D,S,JS,CC

輸出：微社區集合MCS

JD=D⊙JS；

Foreachifrom 1 toCC

Ci={CC(i)}；

CMi={vj|?j=1,2,…,n,JD(Ci,vj)>0}

Nextmax:Max_Fit=0；

Foreachkfrom 1 to |CMi|

ef=fCi∪CMik-fCMik；

//式(17)計算相似性

ifef>max_fitthen

max_fit=ef；

candi_node=CMik；

end if

end for

end for

if max_fit>0 then

Ci=Ci∪candi_node；

CMi=CMicandi_node；

Goto Nextmax；

Endif

Nextmin：min_fit=0；

forkfrom 1 to |Ci|

ef=fCi-fCivk；

//式(23)計算相似性

if min_fit=ef；

min_fit=ef；

candi_node=vk；

end if

end for

if min_fit<0 then

Ci=Cicandi_node；

Goto Nextmin；

end if

end for

(2) 組建最終社區的結構。使用式(23)計算每個無標記節點的適應度，選擇其中適應度最高的社區分配方案。通過一個簡單實例解釋用戶分組的每個步驟，對LDOS-CoMoDa數據集進行了訓練實驗，神經網絡的參數σs和β最優值分別為1.199 3和0.01。圖3中：(a)是17個節點和3個社區的網絡；(b)將網絡映射到低維相似性空間，節點上的數值為式(23)計算的全局重要性；(c)是算法2選擇的社區中心，分別為節點1、10、15。(d)是微社區候選節點；(e)是刪除無效節點后的微社區；(f)是標簽傳播建立的最終社區結構，具體方法是使用式(23)計算每個無標記節點的適應度，選擇其中適應度最高的社區分配方案。

(a) 3個社區的網絡 (b) 網絡映射到低維空間

(c) 社區的代表中心 (d) 搜索候選節點

(e) 構建微社區 (f) 標簽傳播建立社區圖4 社區分簇的實例

4 基于簇的張量分解模型

4.1 奇異值分解

用戶評分矩陣A的元素(i,j)表示為aij，元素(i,j,k)的三階張量表示為Aijk。采用奇異值分解模型(Higher Order Singular Value Decomposition Model,HOSVD)處理用戶-評分矩陣。首先建立3階張量<用戶,電影,上下文信息>，再根據張量建立新矩陣，對每個矩陣進行SVD，最終重建張量。

(1) 初始化張量。將不同的上下文維度建模為張量，三個模式的張量記為TM∈RIu×Im×Ci。張量TM的元素表示了在上下文環境下的興趣，例如：一個28歲的女性用戶在和孩子觀看電影的情況下，評分為4。

(2) 展開張量。展開張量將張量轉化為矩陣形式。例如：在“用戶-電影-上下文”的維度，假設張量為TM∈RIu×Im×Ci，TM表示用戶u在上下文i對電影m評分r。在“評分-好友”的維度，此時基于社交關系預測用戶的評分。

(3) 應用SVD處理矩陣。應用SVD處理每個展開的矩陣，具體方法為：

TM1=U(1)·S1·V1TM2=U(2)·S2·V2,

TM3=U(3)·S3·V3

(24)

式中：U(1)、U(2)、U(3)為SVD的左矩陣。SVD計算張量SM的所有維度。

(4) 建立核心張量SM。核心張量SM能夠發現用戶和項目之間的多維度關系。其計算方法為：

(25)

(26)

4.2 生成推薦列表

5 實 驗

5.1 實驗方法和環境

采用真實的電影評分數據集LDOS-CoMoDa。LDOS-CoMoDa數據集通過問卷調查形式統計了用戶在不同上下文的情況下對電影的評分，該數據集包括了用戶的人口統計學信息、用戶觀看電影的上下文信息以及用戶間的好友關系。LDOS-CoMoDa數據集共有113位用戶對于1 186部電影共2 094條評分記錄，該數據集共有12種上下文因素，評分范圍為1～5，稀疏度為1.6%，如表1所示。

表1 員工基本信息

為了驗證本文提出的方法的有效性，引入了4種不同類型的推薦算法：ESVD[13]、HRMARM[14]、PCAP[15]和HACAR[16]，并比較它們的推薦效果。ESVD是一種基于增強奇異值分解的推薦算法，因為本文算法采用了張量分解技術，所以選擇該算法作為對比方法。HRMARM是一種基于關聯規則挖掘和社交關系的推薦算法，本算法也考慮了社交關系和社區劃分處理，所以選擇該算法作為對比方法。PCAP和HACAR均通過分析用戶上下文信息增強推薦系統的性能，這兩個算法未考慮上下文維度的影響力，而本文算法考慮了上下文維度的影響力，所以選擇這兩個算法作為對比方法。

基于MATLAB 2017b實現本算法。采用5折交叉檢驗方法進行推薦實驗，將每組實驗結果的平均值統計為最終的性能結果。

采用平均絕對誤差MAE、均方根誤差RMSE和精度評估推薦系統的推薦性能。

(27)

(28)

式中:pu,i為用戶u對電影i的預測評分；ru,i為用戶u對電影i的實際評分；N為數據集內的評分總數量。MAE值越低表示推薦的準確率越高。

精度Pr定義為：

(29)

5.2 上下文影響力實驗

本文的核心思想是利用多層感知神經網絡選出影響力大的上下文維度，以期提高推薦系統的性能。采用文獻[17]的連接權重方法測試預測器的重要性，該方法計算輸入層-隱層和隱層-輸出層的預測器重要性之和，將結果作為上下文維度的相對重要性。圖5是神經網絡所計算的不同上下文維度的影響力結果，圖中結果顯示endEmo和dominantEmo是兩個影響力較大的上下文維度，Decision和interaction的影響力較低。

5.3 推薦系統的總體性能

將本文算法與4個對比方案進行比較，圖6、圖7分別為5個推薦算法對于LDOS-CoMoDa數據集的平均MAE結果和RMSE結果?？梢钥闯?，PCAP、HACAR和本文算法均明顯優于ESVD和HRMARM算法，所以考慮推薦系統的上下文環境對于LDOS-CoMoDa數據集的推薦性能較好。PCAP和HACAR算法的性能極為接近，而本文算法的性能略優于PCAP和HACAR算法，所以本文算法通過多層感知神經網絡為分析上下文維度的重要性，有效地提高了推薦的準確率。

圖6 推薦系統對于LDOS-CoMoDa數據集的MAE結果

圖7 推薦系統對于LDOS-CoMoDa數據集的RMSE結果

5.4 上下文維度對推薦精度的影響

根據圖5可看出上下文維度endEmo、dominantEmo和season是影響力最大的維度。實現多層感知神經網絡來分析顯著預測器，最大化用戶在不同上下文情況下評分的方差。圖8是12個上下文維度的神經網絡預測精度結果，結果表明endEmo、dominantEmo和season的預測精度明顯高于其他的上下文維度。此外，5.2節中social維度的影響力較為普通，但其預測精度高于平均值，其原因是本算法的用戶分組策略中考慮了社交關系和人口統計學信息，使得社交關系對推薦的精度產生了有利的影響。

圖8 上下文維度的神經網絡預測精度結果

5.5 不相關上下文維度對推薦性能的影響

圖8表明endEmo、dominantEmo、season和social上下文維度對預測精度的貢獻較為突出，說明推薦系統引入不相關的上下文維度則會導致推薦性能降低。將不相關上下文維度建立為張量，然后為用戶產生推薦列表，圖9為引入不相關上下文維度后的推薦系統MSE值?？梢钥闯?，引入不相關維度導致總體的推薦性能大約衰減了15%，因此本系統通過對上下文維度的篩選有效地排除了不相關維度帶來的負面影響。

圖9 引入不相關上下文維度后的推薦系統MSE值

6 結 語

本文推薦系統通過神經網絡識別影響力大的上下文維度，基于社交關系、地理位置、人口統計學將用戶分組，基于用戶分組的張量分解模型處理上下文維度數據，最終產生推薦列表?；贚DOS-CoMoDa數據集的實驗結果表明，本系統通過上下文維度的分析有效地提高了推薦的性能。

本文基于LDOS-CoMoDa數據集進行了實驗驗證，但該數據集僅有2 094條記錄，數據規模較小。目前研究領域中沒有符合上下文維度要求的大規模數據集，未來將考慮構建大規模的相關數據集，測試本算法處理大數據的效果。