認同度修正下的近相鄰改進推薦算法研究

李劍鋒，封林慧，于天一

大連海事大學，遼寧 大連 116026

隨著互聯網技術的飛速發展，網上購物消費已深入人們的日常生活。根據用戶的歷史信息，分析用戶的興趣愛好，為用戶提供更好的個性化服務，已成為企業的重要任務，企業所應用的推薦算法發揮著日益顯著的關鍵作用[1]。推薦算法研究起源于20世紀90年代，美國明尼蘇達大學Grouplens小組最先開始研究，他們希望制作一個為用戶個性化推薦電影的Movielens系統[2]。隨后，眾多學者也逐步深入擴展多個相關方面的研究，但電影推薦始終是一個重要研究領域。如Hwang等人[3]利用電影評分信息評測電影類型之間的關聯性，并在電影類型修正基礎上依據協同過濾方法確立目標用戶的推薦電影，結果表明此方法比原協同過濾方法具有更高的推薦準確性。何明等人[4]考慮項目的類型信息，填充分類信息下的評分矩陣，改進用戶興趣度計量方法，解決協同過濾算法的稀疏性問題，提高了推薦的準確性、多樣性和新穎性。這些學者實際上希望以電影為特定對象，用以展現推薦算法的效率，然而，由于影響因素眾多，如何有效融合多方因素，更加準確地為用戶提供個性化產品一直是關注的難點。本文則基于認同度的視角，融入大眾化認同度和個性化認同度，提出一個新的近相鄰改進算法，可以更加高效地挖掘隱藏信息，多種評價指標結果表明此算法在很大程度上提升了推薦效果。

1 推薦算法分類及認同角度

推薦算法的種類繁多，如基于內容的推薦、基于規則和知識的推薦、協同過濾推薦等等，從不同角度具有不同的劃分方法，但如果僅從涉及到的用戶數量角度，推薦算法可以大致劃分為單用戶特征推薦和多用戶融合推薦。

單用戶特征推薦算法主要是以特定用戶的歷史行為數據為基礎，通過分析用戶的個性化特征加以推薦商品。這與信息過濾技術較為相似：從特定用戶獲取信息，利用某種方法，如概率統計、語義分析、馬爾可夫預測等，分析出能夠代表此用戶偏好的特征描述，再將符合此特征的物品信息過濾出來，推薦給此目標用戶。例如，楊寶強[5]利用自然語言處理工具，通過詞頻統計方法，獲取用戶評論產品的情感色彩，以此構建用戶興趣演化模型，可以為用戶提供更好的推薦服務；江周峰等人[6]在信息熵思想基礎上提出一種社會標簽模糊化方法，形成模糊識別標簽下基于內容的推薦算法，可以提升高校圖書推薦的準確率；張丹等人[7]加入用戶駐留時間元素，改進隱馬爾可夫模型，以此分析用戶的閱讀軌跡，并尋求用戶下一步可能閱讀的新聞，其結果顯示此推薦算法較大提高了F1評價指標值。

多用戶融合推薦算法則更多強調從多用戶關系上挖掘隱含信息，利用相似多用戶的共同經驗，避免內容信息不完全所導致的推薦不準確。基于用戶和基于物品的協同過濾推薦算法實際上屬于這一分類。基于用戶協同過濾算法是把用戶按照相似度聚類成不同的組，使得同一組內的用戶行為特征相像，進而將組內用戶相似性高的信息或頻繁交互的物品視作備用的推薦。同樣，盡管基于物品的協同過濾算法是以物品聚類，但這種聚類也是以多個用戶認知的一致性為基礎，對于某兩個物品，如利用多個用戶的評分情況或參與情況來確立物品的相似度，而這如果從用戶視角，也是利用了多個用戶看法相似的融合信息。另外，一些關聯規則推薦也可以看作是利用了多個用戶的共同行為信息，在一定支持度和置信度基礎上，啤酒和尿布具有關聯關系，可以放在一起推薦給購買者，而一些網絡群組推薦也可以劃分為此類，如閔磊論述了利用社區發現技術使相似興趣的物品進行聚類，可以緩解冷啟動問題[8]。

多用戶融合推薦算法并不意味著摒棄了用戶的個性化特征，而是強調個性化特征的聚合，這個聚合表明用戶具有相似的偏好"認同感"，以此作為推薦的依據。例如，范波等采用對不同項目類型的多個評分相似度來進行預測評分，可以準確描述用戶對不同類型的偏好[9]；劉國梁[10]提出利用項目的客觀標簽（如電影的類型）描述用戶自身興趣偏好，對數量過多的“熱門項目”有獨特見解的用戶的評分準確性有一定提高；李征等人[11]利用用戶對項目類型的興趣偏好填充傳統矩陣，將用戶評分差異因素和項目質量因素融入相關系數中，再進行混合推薦，得到了更好的推薦效果；陸航等人[12]針對單一評分相似性計算不準確問題，融合用戶興趣和評分差異提出一種新的協同過濾算法，其算法具有更高的推薦精度；Cramer等人[13]強調信任增加了用戶的認同感，而這種認同感會有利于增加用戶適應推薦系統的效率；Pinata等人[14]將用戶情緒融入傳統的協同過濾推薦算法中，實證表明此情緒認知下的協同過濾算法優于傳統的協同過濾推薦算法；Jonice等人[15]提出融入物品描述、用戶興趣和社會關系網的聯接開放數據的推薦方法，此方法比一般的推薦方法具有更好的推薦準確性。

綜上所述，用戶是使用物品的主體，推薦物品建立在用戶某程度認同的基礎之上，單用戶特征推薦是尋求特定用戶的個性化認同，而多用戶融合推薦則尋求相似用戶組的共同性認同，然而，如何有效地綜合這些認同度信息、避免信息缺失并提升推薦效果，這則是一個關注難點。以基于物品的協同過濾推薦算法為例，求解近相鄰相似度是反映多用戶融合信息的基礎，大多數研究采取事先個性化特征填充矩陣的方法，這樣會增強物品之間的相異性，更好地區分物品相鄰對象，但這也意味著有可能降低受用戶歡迎物品的地位。在電影推薦中，用戶觀看了某個一般性電影，從用戶認同角度，受到相似用戶組認同的等價地位電影得到的推薦評分值靠前，然而，不可否認，多數用戶還是傾向于觀看大眾觀看較多的電影，其近相鄰算法會削弱這個特性，這可以表現為大眾化認同度影響。另外，由于用戶認同程度不一致，采取統一的相似度計算度量無法體現用戶的個性化特征，對于同一電影，不同用戶的偏好不同，其近相鄰電影也應該是不同的，這也表現為用戶個性化認同度影響。這樣，本文則采取這兩種認同度事后修正的思想，即大眾化和個性化認同度修正，提出一個新的近相鄰改進算法，力求更加高效地挖掘隱藏信息，提高推薦算法的效果。

2 基于認同度下的推薦算法

2.1 算法基本流程

此推薦算法首先求解電影項之間的皮爾遜相關系數以表現用戶的基本認同程度。對于任何兩個電影項j和i，根據N個用戶對它們的打分情況x和y，如果沒看則打分為0，其電影項相似度cor(j,i)如公式（1）所示：

隨后，分別乘以大眾化認同度和個性化認同度修正系數，這里不同用戶的修正值有所不同。最后，以修正后的電影相關項為標準，利用top-K近相鄰方法，求解出不同用戶的推薦列表。由此對基礎的算法做出補充改進，以更好地融合多方因素，減少信息損失，如圖1所示。

圖1 認同度修正下的推薦算法流程Fig.1 Algorithm process under revised approval-degree recommendation

2.2 大眾化認同度修正系數

認同度修正系數是算法關鍵，在實際應用中，電影已觀看的用戶數量會對潛在用戶產生一定的影響，這是因為羊群效應，人們很容易受到大眾認同度的影響，所以，從大眾角度加入大眾認同度修正系數，計算公式（2）和（3）如下：

其中，N j表示為某個電影j的用戶觀看數量；P j表示為電影j的用戶觀看數量對所有電影的平均用戶觀看數量的比值；b表示為偏移值，通常取0.5；R j則表示為觀看某個電影j的大眾化認度修正系數。這實際上是以電影觀看的平均值為度量標準，利用Sigmoid函數進行幅度歸一化處理并進行偏移，對比分析大眾對于電影的喜好程度。如果某電影觀看數量恰好是電影觀看用戶數平均值，則其相對比值減去1之后為0，其Sigmoid函數值為0.5，再加上偏移值0.5等于1，而其他的電影觀看用戶數值則經過上述公式計算圍繞著1變動，體現為放大或縮小效果。另外，對于沒人觀看新電影的最初大眾化認同度修正系數也設為1，之后則根據其用戶觀看情況動態地加以調整。

2.3 個性化認同度修正系數

上述從大眾化角度對算法進行了修正，但用戶還存在著自身的個性化偏好特點，例如，雖然冒險類電影很受大眾歡迎，但有的用戶就是不喜歡這種緊張刺激的類型，寧愿看一些輕松歡快的喜劇類型，這樣就需要在改進算法中加入個性化認同度因素，本文利用用戶個體觀看電影的類型因素來求解個性化認同度修正系數，計算公式（4）如下：

其中，N ug表示為用戶u看過的g類型電影數量，t表示為電影類型總數。這里采用了近似求相對比值方法，因為存著一些看電影數較少的用戶，如果他只看了一次某類型電影，很難說此用戶就完全不喜歡其他類型電影，所以增加了修正常數1，模糊這種數量少時類型偏好劃分，而當用戶觀看的電影數量逐漸增大，這種修正常數的模糊效果會逐漸減少，用戶喜歡電影類型會更加明確，并且，這也可以避免求解沒看過任何電影冷用戶時分母數值為0的情況。

之后，仍然利用sigmoid函數歸一化處理，防止數據的幅度偏大而導致傳遞時效果不好的問題，并且，引入了偏移值b=0.5，使得平均值通過計算定位于1，如公式（5）所示：

然而，電影的類型并不一定唯一，可能存在著多種類型，可能是冒險類型，同時又是動作和羅曼蒂克類型，所以對于某個電影，用戶的個性化度量值需要進行平均化處理，計算公式（6）如下：

其中，h表示某個電影j所具有的類型數(h≥1)，這樣，對于不同的用戶u而言，喜歡的電影類型不有所同，所面對的電影j的修正系數也是不同的，從而體現個性化認同度的修正效果。

2.4 認同修正后top-k近相鄰算法

求解大眾化認同度系數和個性化認同度系數之后，就可以借此將大眾趨勢和個性偏好融入傳統的近相鄰算法中，如公式（7）所示：

其中，u表示為某個用戶，i表示為用戶u看過的電影，j表示用戶u還可能選擇看的電影，cor(j,i)，R j和R uj分別為前文公式的中相關系數、大眾化認同度系數和個性化認同度系數，R uji則是用戶u在電影i相鄰的可供選擇電影j集合的綜合排序值，這樣，選擇不同的k相鄰值，就可以限定閾值范圍為用戶推薦不同的電影，如圖2所示。

圖2 認同度修正下k相鄰改進過程Fig.2 Improving process of k-nearest neighbors under revised approval-degree recommendation

3 實驗及結果分析

3.1 實驗數據

本文采用明尼蘇達大學Grouplens小組的兩個推薦算法的經典數據集，分別是ml-latest-small和ml-100k數據集，兩者都去除了非類型標記的記錄（no genres listed和unkown），包括10萬條左右的評價記錄數，對兩個數據集都進行隨機八二劃分，形成訓練集和驗證集合，之后求證上文所提出的認同度修正下的近相鄰改進算法的效果。

3.2 評價指標

經過多個評價指標分析，都表明此算法在很大程度提升了推薦效果，評價指標包括：查準率（precision）、查全率（recall）、假正率（FPR）、F1值(F1)、深度（depth）和提升度（lift）。

依據預測值與實際值相互對映，實驗樣本可以分為真正例（TP）、假正例（FP）、真反例（TN）和假反例（FN）。查準率又稱之為精確率，表示為預測中真的正例數占所有預測為正的例數比值，反映預測正例的可信性；查全率又被稱為召回率、靈敏度和真正率，表示為預測中真的正例數占實際為正的例數比值，反映推薦正例的覆蓋性；假正率表示為被錯誤地預測為正的例數占所有實際為負的例數比值，反映多少負樣本被錯誤地預測為正樣本；F1值表示為2倍查準率和查全率的乘積占兩者之和的比值，反映查準率和查全率的調和程度；深度表示為預測為正的例數占全部樣本數C的比值，反映推薦正樣本的進度；提升度表示為預測正例的可信性與實際正比例的比值，也等于真正率（TPR）與深度（depth）的比值，反映推薦的提升效果。如公式（8）～（13）所示：

在算法求解過程中，主要將近相鄰的k值設為從1到100的10等分數值，依次求解推薦算法的評價指標值，這樣可以在不同狀況下，分析基于認同度修正下的改進算法與傳統近相鄰算法的對比效果，具體如表1和表2所示。

表1 數據集ml-latest-small的評價指標變動比率Table 1 Change ration of evaluation indicators through ml-latest-small dataset

表2 數據集ml-100k的評價指標變動比率Table 2 Change ration of evaluation indicators through ml-100k dataset

從表1可以看到，在ml-latest-small數據集中，相對于傳統的近相鄰算法，認同度修正下的推薦算法各方面評價值都得到了提高。表1中數為修正算法值減去傳統算法值再除以傳統算法值，表示為變動比率。近相鄰的k值從1到100過程中，各用戶平均假正率變動都是負值，說明修正算法比傳統算法的認錯性得以降低，不同k值下的平均假正率減少了29.3個百分點。深度變動也都是負值，說明改進算法的推薦數量比例比傳統算法有所減少，不同k值下平均減少了28.7個百分點，但這種推薦數量減少仍實現了查準率、查全率、F1值和提升度各個評價指標的提高：查準率變動都是正值，說明修正算法比傳統算法的預測可信性得以增加，平均提高39.5個百分點；查全率變動都大于等于0，說明修正算法比傳統算法的預測覆蓋性也有所增大，平均提高1.1個百分點；F1值變動也都是正值，盡管查準率和查全率存在沖突，說明修正算法比傳統算法對于兩者的調和程度也有所變好，平均提高37.1個百分點；提升度變動也都是正值，說明修正算法比傳統算法的提升效果也有所增長，平均提高37.3個百分點。由此可見，通過mllatest-small數據集測試，無論是越小越好的負向指標（假正率和深度），還是越大越好的正向指標（查準率、查全率、F1值和提升度），修正算法推薦效果都優于傳統算法，并且具有較為明顯的提高比例。

同樣，從表2可以看到，在ml-100k數據集中，相對于傳統的近相鄰算法，認同度修正下算法也具有較好的推薦效果。對于不同的近相鄰k值，各用戶平均假正率變動也都是負值，修正算法的認錯性得以降低，不同k值下的平均假正率減低了26.4個百分點。深度變動也都是負值，不同k值下修正算法的推薦數量比例平均減少了25.5個百分點。然而，查全率指標卻有所減弱，不同k值下的平均查全率降低了3.5個百分點，但查準率、F1值和提升度這些指標都得到大幅度提高：查準率變動皆為正值，說明修正算法所提供的正例比值增加，其預測可信性得以加強，平均提高29.1個百分點；F1值變動皆為正值，說明盡管查全率變弱，但查準率和查全率的綜合評價調合指標F1值仍然得到較大提高，平均提高26.5個百分點；提升度變動皆為正值，修正算法的提升效果也有所增長，平均提高29.4個百分點。由上所述，雖然ml-l00數據集的測試結果不如ml-latest-small數據集，且查全率指標有所減弱，但波動幅度較小，而其他評價指標（假正率、深度、查準率、F1值和提升度）都得到大副度提升，這些負向指標和正向指標的變好程度都達到20%～30%，因此，通過ml-l00k數據集測試，同樣表明修正算法具有顯著的推薦效果。

3.3 評價曲線

由于評價指標存在關聯性，也可以利用指標之間關聯評價曲線來形象反映推薦算法的效果，常用推薦評價曲線有受試者特征曲線（receiver operating characteristic curve，ROC）和提升曲線（depth-lift）。

ROC曲線最早于二戰時雷達探測中評判信號偵察模型的好壞，后用于分析推薦算法效果的優劣。該曲線中橫坐標為假正率（FPR），縱坐標為真正率（TPR），或稱查全率、召回率和靈敏度，曲線上各點表示為針對不同閾值信號刺激下的假正率和真正率的共同感受性。通過該曲線進行度量所考慮的目的是：盡可能保持少負樣本被錯誤地預測為正樣本（假正率），同時檢驗出更多的正類個體（真正率）。

圖3和圖4分別顯示根據ml-latest-small和ml-100k數據集所計算的認同度修正算法和傳統近相鄰算法的ROC曲線，修正算法符號為“■”，傳統算法符號為“○”，圖中點表示近相鄰k值從1到100的10等分數值所對應于假正率和真正率。可以明顯看出，相同k點情況下，兩個數據集的實驗結果都表明修正算法比傳統算法具有更小假正率和更大真正率，并且，修正算法點更加聚集于二維圖左側，說明修正算法可以在較小錯誤情況下推薦更多地覆蓋用戶所看的電影，其推薦算法效果更加顯著。

圖3 數據集ml-latest-small的受試者特征曲線ROCFig.3 Receiver operating characteristic curve through ml-latest-small dataset

圖4 數據集ml-100k的受試者特征曲線ROCFig.4 Receiver operating characteristic curve through ml-100k dataset

除了ROC曲線，提升曲線也是常用的推薦算法效果的評價曲線，提升曲線的橫軸表示為深度（depth），縱軸表示為提升度（lift），該曲線反映算法隨著不同挖掘深度所對應的不同提升效率。

圖5和圖6則分別顯示兩個數據集下所計算的認同度修正算法和傳統近相鄰算法的提升曲線。圖中樣本點表示近相鄰k值從1到100的10等分數值所對應于兩者指標，修正算法符號為“■”，傳統近相鄰算法符號為“○”。很明顯可以看出，相同k點情況下，兩個數據集下修正算法比傳統算法都具有更小深度和更大提升度，說明修正算法可以在較小推薦數量條件下（深度）得到較大的提升效果（提升度），即更大的預測正例的可信性與實際正比例的比值，也可以說明深度隨之的正樣本覆蓋比例也有所增加。

圖5 數據集ml-latest-small的提升曲線Fig.5 Lifting curve through ml-latest-small dataset

圖6 數據集ml-100k的提升曲線Fig.6 Lifting curve through ml-100k dataset

4 結論

本文提出了一種認同度修正下的推薦算法，將大眾化認同度和個性化認同度系數融入近相鄰算法中，可以更加高效地挖掘隱藏信息。通過在兩個數據集mllatest-small和ml-100k數據集進行對比實驗，結果表明：盡管查全率小幅度上下波度，但其他多個評價指標都得到極大提升，假正率和深度有所減少，查準率、F1值和提升度得以增加，并且，受試者特征曲線和提升曲線也都說明此修正算法具有更為顯著的推薦效果。