基于Fisher線性判別分析的情景感知推薦方法

楊 茜

(鄭州大學 體育學院，河南 鄭州 450044)

0 引 言

“信息過載”導致了互聯網內容服務提供商難以為不同的用戶推薦符合其偏好的資源。而隨著搜索技術與檢索技術的逐漸發展，能夠在一定程度上緩解這些問題，由于不用的用戶對于個性化的需求各不相同，導致其并不能有效幫助用戶找到符合其興趣的偏好資源。

在此需求背景下，許多的研究工作者對能夠解決上述問題的推薦系統進行了深入的研究，并給出了有效的推薦系統實現策略[1-3]。其中應用范圍最廣、研究最深入的是協同過濾[2,3]，而多數基于其的推薦預測系統，僅僅致力于通過相似度判別方法找出用戶的k最近鄰，通過對k最近鄰行為的分析來找出當前用戶可能的偏好資源。這種方法在面對冷啟動[2]與數據稀疏性[3]問題時，對用戶的區分度較低，很難找到真正相似的最近鄰用戶，在這種情況下得出的推薦結果的可靠性相對較低，很難得出高質量的推薦結果[4]。

并且，上述推薦系統僅關注于“用戶-項目”間的二維關系模型，多以用戶間的歷史偏好數據為核心，通過度量用戶偏好行為間的交互影響關系，建立用戶的偏好預測模型。由于用戶偏好的產生受多種內在與外界因素的影響，用戶的職業、年齡、所處上下文環境等都會影響用戶的偏好決策[5]。并且對于同一用戶而言，當其所處的上下文環境發生變化，其偏好也會產生相應的波動[6]，以位置上下文的影響為例，當位置屬性為“家”時，用戶會傾向于“電視節目”，當位置屬性為“公共交通”時，則會更傾向于“音樂”、“新聞資訊”等。上述推薦系統由于無法辨別用戶的位置等上下文環境差異，也就難以取得高質量的推薦效果。

隨著“泛在計算”等新型運算模式的提出與發展，為主動發現并處理用戶狀態、所處位置等上下文信息提供支撐數學模型，那么融合各種上下文信息的情景感知推薦系統逐漸成為了新的發展方向。在這種情況下，受多視圖學習相關理論啟發，提出了一種基于線性判別分析的情景感知推薦方法，以期為相關情景感知推薦方法研究提供有益參考。

1 相關工作

情景感知推薦近年來的應用與發展越來越廣泛與深入，主要的思路為將上下文信息融入偏好獲取過程或對上下文信息進行建模分析，優化用戶的偏好模型。例如，A.Karatzoglou等[7]提出了通過引入多種神經元來融合上下文信息，以改進協同過濾算法，提高了推薦準確度；Gantner Z等[8]采用因式分解模型對電影上下文信息進行建模分析，提高了電影推薦的準確度；涂丹丹等[9]提出了一種基于聯合概率矩陣分級的情景感知廣告推送方法，提高了廣告推薦的精確度；郭晶晶等[10]基于物聯網面向虛擬社區，提出了一種社會化網絡環境下，用戶群組間信任關系的推薦方法；顧梁等[11]面向播存網絡環境采用協同過濾算法實現了UCL推薦策略，等。

這些方法多是基于上下文信息的建模來為用戶生成推薦服務，也即是從單視圖角度建立用戶的偏好模型，難以全面的涵蓋影響用戶偏好的各種信息。并且這些方法多以提高推薦準確度為度量準則，未能兼顧多種度量標準，影響了推薦質量和推薦系統的大規模推廣應用。

而多視圖學習研究起源于Yarowsky[12]，用多視圖解決圖像樣本特征分類問題，其定義比較寬泛，一般只要滿足“學習的數據可以用多視圖描述”，目前是樣本分類、模型優化與半監督學習等領域的熱門研究方向，例如，將多視圖學習用戶復雜標簽樣本分類、手寫數字識別等。在推薦領域，推薦的過程可以看作是樣本分類的過程，即是以用戶偏好為分類特征，相關的樣本數據采用多視圖來描述：可以從用戶、項目、內容提供商等視圖對相關數據進行描述，也即是推薦的產生可以轉換為多視圖優化問題。

受此啟發，本文提出了一種基于線性判別分析的情景感知推薦方法。該方法不僅降低了時間開銷，而且能夠同時提高推薦準確度與多樣性，即是說明了所提出方法能夠兼顧多種度量準則。該方法的具體描述見下文。

2 基于多視圖數據融合的情景感知推薦方法

2.1 多視圖數據的獲取

本文所采用的多視圖數據主要包括用戶視圖下的偏好項目特征數據與項目視圖下的項目吸引程度。其中，用戶視圖下的偏好項目特征數據表示基于用戶的歷史偏好行為，所建立起的描述其偏好項目特征的數據集合。其中用戶的歷史偏好信息多由評分矩陣表述(見表1)，Pij指代用戶Ui對于任意項目Ij的歷史偏好值，偏好程度與Pij的值為正相關關系。

表1 用戶歷史偏好矩陣

度量用戶間偏好相似程度的主流方法包括以下3種：余弦相似度[2]、修正的余弦相似度[3]、泊松相似度[7]，3種度量策略的實現思路均為度量歷史偏好行為偏差程度，并對其差異程度采用歸一化的度量值表示。本文使用修正的余弦相似度方法作為偏好行為近似程度的度量策略，具體如下

(1)

在通過上述方法獲取偏好近鄰的基礎上，基于偏好近鄰的歷史偏好信息，建立用戶偏好項目的屬性特征描述，具體如下

(2)

(3)

其中，CUip指代用戶Ui對于任意屬性p的偏好特征，KNN(Ui)表示獲取的用戶Ui的最近鄰用戶集合，cUjp指代Ui的任一近鄰用戶Uj對于p的平均偏好度量值，Ip為Uj的歷史偏好項目中，包含屬性p的項目集合，PUjm表示Uj對于項目m(m∈Ip)的歷史偏好值。

基于項目視圖下的項目吸引力，指的是從項目視圖下度量項目對于用戶的吸引程度，能夠反映出項目被推薦的概率。其值越大表明項目被推薦的概率也就越大，推薦系統整體的項目吸引力能夠反映出用戶推薦列表對于項目整體的覆蓋程度。度量此值的目的在于減弱長尾效應[7]，使每個項目能夠推薦至偏好它的用戶群組，而不是只推薦熱門資源，避免冷門資源越來越冷門。項目吸引力采用A(m,Ui) 表示，具體度量方法如下

(4)

2.2 多視圖數據融合

(5)

根據類間離散度與類內離散度定義，各類中的類內離散度矩陣可表示為

(6)

根據上述定義，總的類內離散度矩陣可由如下方式獲取

Sk=Sk1+Sk2

(7)

類間離散度矩陣如下

St=(A1-A2)(A1-A2)T

(8)

其中，矩陣(A1-A2)(A1-A2)T是一種協方差矩陣，度量了所獲取的偏好特征與總體樣本數據間的約束程度，其對角線中的特征數據為偏好特征與樣本總體間的樣本方差，非對角線數據為樣本總體的協方差。也即是Aj指代樣本總體中各類特征數據間的離散冗余程度，St指代各類特征數據間的離散冗余程度。

根據分類準則，需通過降低分類后類間特征數據的近似程度，提高類內特征數據的近似程度。那么，推薦結果的產生也就轉換成了找到使得Aj取得整體最小值，St取得整體最大值的分類準則。具體方法為將原兩類樣本數據轉換為相應維度的特征向量，并以任一向量C為方向進行投影變換，如下

(9)

變換后的兩類類樣本均值為

(10)

變換后的類內離散度為

=CTSkjC,j=1,2

(11)

變換后的類間離散度為

=CT(A1-A2)(A1-A2)TC

=CTStC

(12)

對于轉換之后的偏好項目集合的特征數據需求仍然是，降低分類后類間特征數據的近似程度，提高類內特征數據的近似程度。為此，采用Fisher判別準則進行樣本數據優化，具體如下

(13)

具體方法為以其判別準則為優化目標，獲得能夠使JFisher最大的投影方向，具體如下

(14)

使用Lagrange乘子法作為求解方法，設CTSkC為非零常數b，則

L(C,δ)=CTStC-δ(CTSkC-b)

(15)

對C求偏導數可以得出

(16)

令偏導數為0，即是

StC′=δSkC′

(17)

(18)

3 實驗與結果分析

3.1 數據集

實驗選取擴充后的BookCrossing數據集(數據集下載地址如下：http://www2.informatik.uni-freiburg.de/～cziegler/BX)，并以此為基礎加入一定的上下文生成規則，構建一個模擬真實數據集BookCrossing-MN。其中，核心數據集是從Book-Crossing圖書社區上采集的真實數據。其中共包含278 858名讀者對于271 379圖書的借閱、評價等行為信息記錄。BookCrossing-MN共包括如下幾部分：

BC-MN-Users，讀者的ID、位置、年齡；

BC-MN-Books，圖書的標題、編號、所屬領域、出版社、作者、頁碼；

BC-MN-Ratings，讀者對相應圖書的偏好值；

BC-MN-Contexts，包括時間、位置、狀態信息等上下文信息。

3.2 算法度量準則

準確度是衡量推薦系統質量最直觀與最常用的度量準則，能夠直接反映出推薦結果是否符合其偏好模型。其中P@R依據推薦列表中的Top-R個相關項目，并將其與測試集中訪問頻次最高的Top-R個項目進行對比，其值與準確度為正相關關系

(19)

多樣性是另一個度量推薦效果的度量準則，S(i,j)指代項目間的相似關系，|R|指代推薦列表的長度，那么多樣性定義如下

(20)

3.3 實驗及分析

實驗一：參數最優取值實驗

參數α為歷史偏好行為次數與歷史偏好值對于項目吸引力影響的修正參數，項目吸引力是從項目視圖下度量項目價值。其中，歷史偏好次數能夠反映出項目的熱門程度，歷史偏好值反映的是相應項目符合用戶偏好的程度。本次實驗將項目吸引度最大的項目作為相應用戶的推薦列表，并采用覆蓋率作為度量準則。具體如下

(21)

其中，|I|指代推薦系統中所有的項目數量，R(Ui)指代Ui的推薦列表，分子指代系統中所有用戶推薦列表的并集。

在本次實驗中，數據集的處理采用ABO方法[14]，本文在每個參數實驗節點運算10次，并把其均值作為相應度量結果值。并將本文數據集劃分為不同比例的訓練集與測試集，經過反復對比實驗，選取出有代表性的訓練集比例，以及α取值(表2)，對比結果如圖1～圖4所示。

表2 參數α代表性取值

由圖1～圖4可知：α取不同值的時候，訓練集比例從小到大，算法的覆蓋率并無統一規律，說明訓練集比例對于覆蓋率顯著影響。另外，隨著推薦列表長度的增加，覆蓋率隨之增加，說明提高推薦列表長度有助于獲得更高的覆蓋率。而其長度應依具體應用環境控制在合適的范圍內。原因在于：一方面減少算法時間開銷，另一方面由于數據集的稀疏性，增加推薦列表長度會導致算法涵蓋不相關的偏好信息，影響推薦準確度。綜合對比4個實驗結果圖，隨著α的增加，本文方法的覆蓋率呈現出先增后減的趨勢，并在α=1.21時取得最優結果，因此在接下來的實驗中，取α=1.21。

圖1 20%數據為訓練集的實驗結果

圖2 40%數據為訓練集實驗結果

圖3 60%數據為訓練集實驗結果

圖4 70%數據為訓練集實驗結果

實驗二：算法對比實驗

在獲取最優參數的基礎上，將本文算法與現有的算法進行實驗分析對比。本文選取兩個有代表性的方法RNCF[13]和GBCR[14]。其中RNCF是不考慮上下文信息的推薦方法，主要思路為通過建立歸一化的評分體系，削弱用戶評分尺度的影響，并在此基礎上改進協同過濾算法。而協同過濾算法是最具代表性并且應用最廣泛的推薦方法。GBCR是通過圖模型對上下文信息建模，通過度量模型節點間相關關系生成偏好模型。GBCR是推薦系統最新的研究方向的代表性方法。由于RNCF不考慮上下文信息，所以只采用BC-MN-Ratings部分。

(1)準確性對比

準確度是目前度量推薦效果最常用的度量準則，它能夠直觀的反映出所推薦項目是否符合用戶的偏好模型，其值越大表明推薦質量越高，本文選取具有代表意義的實驗結果如圖5和圖6所示。

圖5 40%數據為訓練集實驗結果

圖6 60%數據為訓練集實驗結果

由圖5，圖6所示，在兩組對比實驗結果上，本文算法與GBCR能夠相比于RNCF能夠取得更好的推薦準確度，說明在建立用戶偏好模型時，考慮相關的上下文信息能夠提高推薦算法的推薦質量。而本文算法相比于GBCR與RNCF，準確度平均提升了13.54%、24.28%，說明采用多視圖學習融合用戶偏好的多視圖數據能夠取得更好的推薦準確度。

(2)多樣性對比

多樣性描述了推薦算法能否挖掘用戶潛在偏好的重要度量標準。在幾種不同比例訓練集上進行實驗測試，選取出有代表性的40%與60%的訓練集比例進行對比實驗，見表3。

表3 多樣性對比實驗結果

從表3可以看出，本文算法的多樣性優于兩種對比算法，相比于GBCR與RNCF多樣性分別提升了26.42%與39.15%，也即是本文算法有更大的概率覆蓋用戶的潛在偏好。原因在于本文算法相比于兩個對比算法，采用了多視圖學習的方法融合了用戶偏好的多維特征，某種程度上降低了用戶歷史偏好的影響，豐富了推薦列表的多樣性。

(3)時間復雜度對比

環境為Intel(R)Core(TM)i3，主頻2.1G隨機HZ。選取50個用戶為一組，計算3種算法的平均時間開銷。實驗結果見表4(時間單位為s)。

在表4中，第一列指代推薦列表長度，由表中數據可知，隨著推薦列表的增加，3種算法的時間開銷對隨之增加，并且初始推薦的時間開銷(推薦列表長度為10)較多，隨著推薦列表長度的持續增加，時間開銷的增加幅度逐漸減少。這是由于算法初次運行時會計算出相關的中間變量，所需的時間開銷較多。3個算法中，RNCF的時間開銷最少，這是由于它只采用了評分數據，沒有采用上下文數據，減少了時間開銷。而本文算法的時間開銷比GBCR減少約7.74%，說明相比于現有的情景感知推薦方法，本文能夠降低算法的時間開銷。

表4 時間開銷對比

4 結束語

情景感知推薦方法研究是目前人工智能研究熱點之一，國內外各個研究機構、大學和互聯網巨頭公司等都投入了大量的人力和物力進行探索和研究。現有的情景感知推薦方法，多采用單視圖數據建立用戶的偏好模型，導致了推薦結果無法兼顧多種度量準則，影響了推薦質量。受多視圖學習相關理論啟發，提出了一種基于線性判別分析的情景感知推薦方法，與現有的方法比較，本文方法不僅降低了時間開銷，而且準確度平均提高18.91%，多樣性平均提高32.79%，即是說明了所提出方法能夠兼顧多種度量準則，提高了推薦質量。

[1]SUN Guangfu,WU Le,LIU Qi,et al.Recommendations based on collaborative filtering by exploiting sequential beha-viors[J].Journal of Software,2013,24(11):2711-2733(in Chinese).[孫光福,吳樂,劉淇,等.基于時序行為的協同過濾推薦算法[J].軟件學報,2013,24(11):2711-2733.]

[2]WANG Xingmao,ZHANG Xingming.Collaborative recommendation algorithm based on contributor factor[J].Application Research of Computer,2015,32(12):132-136(in Chinese).[王興茂,張興明.基于貢獻因子的協同過濾推薦算法[J].計算機應用研究,2015,32(12):132-136.]

[3]WU Yueping,DU Yi.Collaboration filtering recommendation algorithm based on artificial fish swarm algorithm[J].Computer Engineering & Design,2012,33(5):1852-1856(in Chinese).[吳月萍,杜奕.基于人工魚群算法的協同過濾推薦算法[J].計算機工程與設計,2012,33(5):1852-1856.]

[4]GAO Ming,JIN Cheqing,QIAN Weining,et al.Real-time and personalized recommendation on microblogging systems[J].Chinese Journal of Computers,2014,37(4):963-975(in Chinese).[高明,金澈清,錢衛寧,等.面向微博系統的實時個性化推薦[J].計算機學報,2014,37(4):963-975.]

[5]Wu H,Yue K,Liu X,et al.Context-aware recommendation via graph-based contextual modeling and postfiltering[J].International Journal of Distributed Sensor Networks,2015(3):1-10.

[6]Kim J,Lee D,Chung K Y.Item recommendation based on context-aware model for personalized u-healthcare service[J].Multimedia Tools and Applications,2013,71(2):855-872.

[7]Karatzoglou A,Amatriain X,Baltrunas L,et al.Multiverse recommendation:N-dimensional tensor factorization for context-aware collaborative filtering[C]//Proceedings of the Fourth ACM Conference on Recommender Systems.New York:ACM,2013:79-86.

[8]Gantner Z,Rendle S,ST L.Factorization models for context-/time-aware movie recommendations[C]//Processing of the Recsys Workshop on CAMRa.New York:ACM press,2014:14-19.

[9]TU Dandan,SHU Chengchun.Using unified probabilistic matrix factorization for contexual advertisement recommendation[J].Journal of Software,2013,24(3):454-464(in Chinese).[涂丹丹,舒承椿.基于聯合概率矩陣分級的上下文廣告推薦算法[J].軟件學報,2013,24(3):454-464.]

[10]GUO Jingjing,MA Jianfeng.Trust recommendation algorithm for virtual community based interest of things[J].Journal of XiDian University,2015,42(2):52-57(in Chinese).[郭晶晶,馬建峰.面向虛擬社區物聯網的信任推薦算法[J].計算機研究與發展,2015,42(2):52-57.]

[11]GU Liang,YANG Peng,LUO Junzhou.A collaborative filtering recommedation method for UCL in broadcast-storage network[J].Journal of Computer Research and Development,2015,52(2):475-486(in Chinese).[顧梁,楊鵬,羅軍舟.一種播存網絡環境下的UCL協同過濾推薦方法[J].計算機研究與發展,2015,52(2):475-486.]

[12]Baltrunas L,Ricci F.Experimental evaluation of context-dependent collaborative filtering using item splitting[J].User Modeling and User-Adapted Interaction,2014,24(1):7-34.

[13]Kim S C,Sung K J,Park C S,et al.Improvement of colla-borative filtering using rating normalization[J].Multimedia Tools and Applications,2013,6(2):1-12.

[14]Wu H,Yue K,Liu X,et al.Context-aware recommendation via graph-based contextual modeling and postfiltering[J].International Journal of Distributed Sensor Networks,2015,21(3):1-10.