基于最近鄰的標簽修正推薦算法*

余利國 丁衛(wèi)平 景 煒

（南通大學信息科學技術學院 南通 226019）

1 引言

隨著信息技術和互聯(lián)網(wǎng)的快速發(fā)展，人類逐漸從信息匱乏的時代步入了信息過載（Information Overload）的時代。推薦系統(tǒng)（Recommender System）是解決信息過載問題的重要工具，近年來得到了快速的發(fā)展［1～3］。推薦系統(tǒng)的任務是關聯(lián)用戶和信息，一方面幫助用戶找到對其有價值的信息，另一方面將信息呈現(xiàn)在對其感興趣的用戶面前，從而實現(xiàn)信息生產(chǎn)者和信息消費者共贏［4］?；跇撕灥耐扑]系統(tǒng)是推薦系統(tǒng)中研究與應用的熱點［5］。豆瓣是國內(nèi)個性化推薦領域的領軍企業(yè)之一，也是標簽推薦系統(tǒng)的典型代表。豆瓣提供書籍、電影、音樂等作品的信息，其描述、評論、分類、篩選都是由用戶提供和決定，用戶對書籍和電影等打標簽，網(wǎng)站再使用用戶所標注的標簽為用戶進行個性化推薦［6］。

讓普通用戶給物品打標簽，即User Generated Content（UGC），通過用戶對一個物品打上一個標簽，這個標簽描述了用戶的興趣，也將用戶和物品聯(lián)系起來，分析這種用戶行為為用戶進行個性化推薦，即為UGC標簽推薦系統(tǒng)。

近年來，基于標簽的推薦系統(tǒng)在學術界受到了廣泛的關注，國際著名會議ECML/PKDD舉辦了多場基于標簽的推薦系統(tǒng)比賽［7～9］。在對其研究中，取得了新的進展并涌現(xiàn)了很多新的方法，比如Krestel等提出基于LDA的算法［10］；Symeonidis等構建用戶、標簽、項目的三階張量模型，提出結(jié)合聚類方法的張量分解，以減小張量進而精簡推薦運算［11］；Jiang等綜合考慮社會關系信息和時間因素，從而改進了基于標簽的推薦效果［12］。雖然目前在基于標簽的推薦系統(tǒng)上已經(jīng)有很多研究，但大部分的研究并未考慮到標簽的質(zhì)量問題。由于用戶的文化水平存在差異，用戶所打標簽可能有拼寫錯誤的單詞，因此標簽質(zhì)量的優(yōu)劣也不確定，從而影響基于標簽的推薦系統(tǒng)的推薦效果。

基于上述考慮，本文提出一種基于最近鄰算法的標簽修正算法。該標簽修正算法關鍵在于引入最近鄰算法思想，使用歐式公式計算待處理標簽與其他標簽的距離，找出最接近的單詞，即為修正后的單詞，并據(jù)此修正數(shù)據(jù)集中所有標簽，最后在處理過的標簽基礎之上為用戶進行個性化推薦。

2 基于標簽的推薦系統(tǒng)經(jīng)典算法

本文提出的算法是基于經(jīng)典推薦算法Classical Tag Based algorithm（CTB）［4］。CTB算法的核心思想為

1）統(tǒng)計每個用戶u常用的標簽user_tags；

2）對于每個標簽tag，統(tǒng)計被打此標簽次數(shù)最多的物品tag_items；

3）對于每個用戶u，首先找到其常用的標簽user_tags，然后找到具有這些標簽的最熱門物品recommend_items，并推薦給這個用戶u。

用戶u對物品i的興趣公式如下：

其中nu，b是標簽b被用戶u使用的次數(shù)，nb，i是使用標簽b標注物品i的次數(shù)。給定用戶標簽行為記錄的三元組（u，b，i）。CTB算法的示例如圖1所示，該圖包含4個用戶（A，B，C，D）、4個標簽（1，2，3，4）和5個物品（a，b，c，d，e）。

圖1 UGC經(jīng)典算法示例圖

由圖1可得，用戶標簽行為記錄有（A，1，a）（A，2，c）（A，3，c），（B，1，a）（B，3，b）（B，3，e）（B，4，e），（C，1，a）（C，2，b）（C，4，d），（D，3，b）（D，2，c）（D，3，c）。具體推薦過程如下：首先分別計算出nu，b：nA，1=1，nA，2=1，nA，3=1；nB，1=1，nB，3=2，nB，4=1；nC，1=1，nC，2=1，nC，4=1；nD，2=1，nD，3=2。接著分別計算出nb，i：n1，a=3，n2，b=1，n3，b=2，n2，c=2，n3，c=2，n4，d=1，n3，e=1，n4，e=1。其余未列出的nb，i和nu，b值為0。再次統(tǒng)計出nb，i和nu，b后，根據(jù)興趣公式，可以得出對于用戶u興趣度最高的TopN，作為給用戶u個性化推薦的物品。圖1示例中，選擇用戶A，為其個性化推薦物品。據(jù)興趣公式，分別求得位列前兩位，所以為用戶A個性化推薦的物品列表為（b，e）。

算法1給出了CTB算法為目標用戶u產(chǎn)生推薦列表的偽代碼。

算法1Recommend

輸入：u-目標用戶，n-推薦列表中物品的個數(shù)

輸出：recommend_items-為目標用戶u推薦的物品列表

步驟：

1：InitStat（）

2：tagged_item=user_items［u］

3：for tag，wut in user_tags［usr］.items（）do

4：for item，wit in tag_items［tag］.items（）do

5：if item_not in tagged_item then

6：if item not in recommend_list then

7：recommend_list［item］=wut*wit

8：else

9：recommend_list［item］+=wut*wit

10：end if

11：end if

12：end for

13：end for

14：return Sorted（recommend_list）.top（n）

算法1中InitStat（）是推薦算法對數(shù)據(jù)集的初始化方法，該方法進行各項數(shù)據(jù)的統(tǒng)計，包括每個用戶u常用的標簽user_tags及對于每個標簽tag，被打這個標簽次數(shù)最多的物品tag_items，用戶u打過標簽的物品user_items等。

由于要處理海量數(shù)據(jù)，InitStat（）在實驗中使用了Spark的RDD離線計算，算法2為其偽代碼。

算法2 InitStat

輸入：f-數(shù)據(jù)集user_tagged.dat文件地址字符串

輸出：（user_tags，tag_items，user_items）-各項統(tǒng)計數(shù)據(jù)的集合

步驟：

1：data_file=open（f）

2：line=data_file.readline（）

3：while line do

4：terms=line.split（“ ”）

5：user=terms［0］，item=terms［1］，tag=terms［2］6：addValueToMat（user_tags，user，tag，1）

7：addValueToMat（tag_items，tag，item，1）

8：addValueToMat（user_items，user，item，1）

9：line=data_file.readline（）；

10：end while

11：return（user_tags，tag_items，user_items）

3 基于最近鄰的標簽修正推薦算法

3.1 引入最近鄰算法

K近鄰算法，即K-nearestneighbor（KNN）最早在1967年被Cover和Hart提出，用以處理文本的分類問題［13］。相較于其他分類算法，KNN算法簡單且易于實現(xiàn)，分類精準率也較高，適合用于多分類問題，是實際分類應用比較常用的算法［14～15］。KNN算法基本思想是假設一個樣本在特征空間中的k個最相鄰樣本中的大部分屬于某個類別，則該樣本也屬于這個類別，并擁有該類別中樣本的特征。

算法3給出了KNN算法的描述。

算法3 KNN

輸出：實例x所屬的類y

步驟：

1：依據(jù)選定的距離度量，在訓練集T中找出與x最近的k個點，涵蓋這k個點的鄰域，記為Nk(x)

2：在Nk(x)中根據(jù)分類決策規(guī)則（如多數(shù)表決），決定x的類別y：

在上式中，I為指數(shù)函數(shù)，即當yi=cj時，I為1，否則I為0。

KNN算法特殊情況是k=1的情形，稱為最近鄰算法，對于輸入的實例點（特征向量）x最近鄰算法將訓練數(shù)據(jù)集中與x最近鄰的類作為x的類。本文采取的就是KNN算法的這種特殊情況，即最近鄰算法。

在KNN算法中，有很多距離的計算方法，本文采用歐式距離（Euclidean distance）計算待修正單詞與其他單詞的距離［13］，具體計算方式如下：

3.2 TCNNB算法核心思想

本文針對用戶所打標簽可能出現(xiàn)拼寫錯誤的問題，提出基于最近鄰的標簽修正推薦算法（tag correction recommendation algorithm based on nearestneighbor，TCNNB）。在給用戶個性化推薦之前，對用戶所打的標簽進行修正。其核心思想為：1）分別統(tǒng)計出所有標簽單詞的字母頻次；2）使用歐式距離計算出待處理標簽單詞與所有其他標簽單詞的頻次之差，即該單詞與其他單詞的距離；3）根據(jù)距離找出最接近的單詞，即該單詞與其他單詞的頻次之差的平方和，再求開平方，結(jié)果最小的單詞。

算法4給出了上述修正過程的偽代碼。

算法4Check_Modify

輸入：word-待檢測標簽的單詞，words-所有標簽中的單詞集合

輸出：modifiedWord-檢測并糾正后的單詞

步驟：

1：L=len（words），minDist=0，similarWord=word

2：for i from 1 to L do

3：fre=Counter（word）

4：distance=distance（word，words［i］）

5：if distance

6：similarWord=words［i］

7：minDist=distance

8：end if

9：end for

10：return similarWord

算法4在實驗中同樣使用了Spark的RDD離線計算對數(shù)據(jù)集進行處理。在算法4中，第3行Counter（）方法用來統(tǒng)計待處理word里字符出現(xiàn)的次數(shù)，distance（）方法使用定義2）中的歐式距離，計算兩個單詞的距離。

3.3 基于TCNNB算法的推薦流程

在CTB算法基礎上，本文引入TCNNB算法對數(shù)據(jù)集中用戶所打標簽進行了修正，整個推薦算法的流程如圖2所示。

圖2 TCNNB算法流程

該算法首先使用算法4 Check_Modify對數(shù)據(jù)集中用戶所打標簽進行修正，然后將修正后的的數(shù)據(jù)進行統(tǒng)計，統(tǒng)計出user_tags，tag_items和user_items等集合，最后使用算法1為用戶進行個性化推薦，輸出為該用戶推薦的物品列表recommend_items。

4 實驗結(jié)果與分析

本文采用的實驗平臺為PC（Intel（R），CPU i5-7300HQ，RAM 16GB），Windows10家庭中文版操作系統(tǒng)，開發(fā)工具為IntelliJ IDEA、JetBrains PyCharm，代碼使用Scala語言編寫Spark程序處理數(shù)據(jù)集，Python語言編寫推薦算法。

本節(jié)首先進行實驗數(shù)據(jù)集介紹和相關實驗設計，接著介紹實驗中采用的度量標準，最后展示了TCNNB算法與CTB算法的實驗結(jié)果，并對實驗結(jié)果進行分析。

4.1 數(shù)據(jù)集

本文采用Delicious數(shù)據(jù)集，Delicious是UGC標簽推薦系統(tǒng)的開創(chuàng)者，是目前網(wǎng)絡上最大的書簽類站點。Delicious數(shù)據(jù)集中包含用戶對網(wǎng)頁URL的標簽記錄，其每一行由一個四元組表示，該四元組包括用戶ID（userID）、網(wǎng)頁URL（bookmark ID）、標簽ID（tagID）和時間（包括年、月、日、分、秒）。Delicious數(shù)據(jù)集的統(tǒng)計信息如表1所示，實驗中使用大數(shù)據(jù)處理框架Spark中wordcount案例的方法對數(shù)據(jù)集進行處理，統(tǒng)計出最熱門的10個標簽如表2所示。

表1 Delicious數(shù)據(jù)集的基本信息

表2 Delicious數(shù)據(jù)集中最熱門的10個標簽

4.2 實驗設計

為了全面測評本文提出的TCNNB算法在推薦中性能，本文采用交叉驗證方法進行相關實驗［4］。實驗中將數(shù)據(jù)集隨機分為K份，以鍵值用戶和物品進行劃分，不包含標簽。其中，用戶對物品的多個標簽記錄被分入訓練集或測試集，不含分入訓練集和測試集交叉情況。隨機挑選1份數(shù)據(jù)集作為測試集，剩下的K-1份作為訓練集，總共進行K次測試。通過學習訓練集中用戶所打標簽的數(shù)據(jù)，預測測試集中用戶將會給什么物品打標簽。所有測試后，計算K次測試所得的度量指標的平均值，以確保算法驗證的可靠性。

本文還將設置不同的K值（K=5，10，20，40，80，160）進行實驗，考察K值不同情況下，本文算法在度量指標上的性能，實驗步驟設計如圖3所示。

圖3 實驗設計流程圖

4.3 度量標準

在推薦系統(tǒng)中，通常給用戶一個個性化的推薦列表，這個推薦列表是推薦對象根據(jù)推薦算法排序的前N個推薦對象，這種推薦即Top N推薦，本文將使用此方法。本文采用召回率（Recall）和準確率（Precision）評測推薦系統(tǒng)推薦算法的精度［4］。

召回率的計算公式定義為

準確率的計算公式定義為

其中，R（u）表示為用戶u推薦的長度為N的物品列表，R（u）包括了推薦算法預測用戶會打標簽的物品。T（u）表示測試集中用戶u實際打過標簽的物品集合。

本文還采用覆蓋率（Coverage）全面測評UGC標簽推薦系統(tǒng)的性能。覆蓋率是測評推薦系統(tǒng)發(fā)覺物品長尾的能力［4］。覆蓋率有不同的定義方法，本文采用最常用的方法，即推薦系統(tǒng)能夠推薦出來的網(wǎng)頁URL集合占總網(wǎng)頁URL集合的比例。其中，U表示用戶集合，R（u）表示推薦系統(tǒng)為用戶u推薦長度為N的網(wǎng)頁URL列表，覆蓋率計算公式定義為

4.4 實驗結(jié)果與分析

本節(jié)主要展示了在Delicious數(shù)據(jù)集上分別使用TCNNB和CTB算法基于標簽的推薦系統(tǒng)的實驗結(jié)果，對度量標準的各項指標結(jié)果進行比較。表3和表4分給出了兩種算法在Delicious數(shù)據(jù)集上實驗的各項度量標準的測評結(jié)果。

表3 CTB算法的實驗結(jié)果

表4 TCNNB算法的實驗結(jié)果

根據(jù)表3和表4，我們可得出如下實驗結(jié)論：1）推薦結(jié)果的精準度（召回率和準確率）和K不成正相關或者負相關，K取較小值時，精準率隨著K增大而增大，精準率會達到一個峰值，隨后，隨K值增大，精準率會隨之減?。?）K增加會降低覆蓋率。

推薦算法的精準率（召回率和準確率）在不同K值下，兩種算法的實驗結(jié)果對比分別如圖4和圖5所示。

圖4 兩種算法下的召回率

圖5 兩種算法下的準確率

從圖4和圖5可以看出，在不同K值下，本文提出的TCNNB算法在召回率和準確率上都明顯高于原有的CTB算法，其原因在于TCNNB算法修正了用戶可能拼寫錯誤的標簽，去除掉隨意性的標簽，修改為與其最相似的標簽，進而提高了個性化推薦的召回率和準確率。從圖4和圖5中發(fā)現(xiàn)，召回率和準確率的變化趨勢相似。TCNNB相對于CTB算法，召回率和準確率改進的增幅隨著K值增加而隨之增大，這是因為K值越大，訓練集占數(shù)據(jù)集比例越高，經(jīng)過TCNNB算法修正的標簽比例也越高，測試集的推薦結(jié)果也更加精準。

推薦算法的覆蓋率在不同K值下，兩種算法的實驗結(jié)果對比如圖6所示。

圖6 兩種算法下的覆蓋率

從圖6可以看出，在不同K值下TCNNB算法的推薦結(jié)果的覆蓋率都比原有的CTB算法要差。這是因為對數(shù)據(jù)集中用戶所打標簽進行修正，去除了一些生僻詞匯的標簽，改用了一些出現(xiàn)次數(shù)較多且相似的標簽，這些標簽很大一部分是為那些不流行的網(wǎng)頁URL所打。因此，提出的TCNNB算法在覆蓋率這一指標上會略微有所降低。

5 結(jié)語

在基于標簽的推薦系統(tǒng)中，為了更加精確地為用戶個性化推薦物品，必須提高用戶所打標簽的質(zhì)量，本文提出了一種基于最近鄰的標簽修正推薦算法，對用戶所打標簽的拼寫錯誤，進行了有效的修正，提高了推薦結(jié)果的精確率（召回率和準確率）這個關鍵指標，達到了提高個性化推薦性能的效果。在Delicious數(shù)據(jù)集上的實驗表明，本文算法能夠在一定程度上達到提高標簽質(zhì)量的目的，推薦系統(tǒng)的推薦效果明顯提高。

本文重點考慮了拼寫錯誤的標簽對推薦結(jié)果的影響，其他問題，如：修正海量的用戶標簽，需要搭建Spark等大數(shù)據(jù)框架進行處理，以及因詞根不同，但意思相同的同義詞對推薦結(jié)果的影響，將在今后的工作中進一步開展研究。