提取關(guān)鍵字改進(jìn)協(xié)同過濾算法的研究與應(yīng)用

李吉祺，黃 剛

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210000)

0 引 言

推薦系統(tǒng)是一個古老的問題，也是大數(shù)據(jù)與人工智能的一個非常好的落腳點(diǎn)。傳統(tǒng)協(xié)同過濾算法至今仍然在各種場景下發(fā)揮著巨大作用，其一般基于評分矩陣的每一列或者每一行的評分值來進(jìn)行相似度計(jì)算，最終依據(jù)一定的推薦策略給出推薦列表。協(xié)同過濾算法雖然經(jīng)過前人無數(shù)次的改進(jìn)，但是在面對評價(jià)信息較少，或者沒有評價(jià)信息的時(shí)候，很難發(fā)揮其作用。因此，挖掘出物品背后更多的信息來彌補(bǔ)傳統(tǒng)協(xié)同過濾算法的不足是一個很重要的議題。

1 背景知識與問題

近年來，互聯(lián)網(wǎng)的快速發(fā)展帶來了一個很嚴(yán)重的問題：信息過載。在網(wǎng)絡(luò)中人們面臨著太多的數(shù)據(jù)，已經(jīng)無法高效率地篩選出有價(jià)值的數(shù)據(jù)了。但是從另外一方面來說，互聯(lián)網(wǎng)信息量的指數(shù)級增長，也意味著可以挖掘的數(shù)據(jù)正以驚人的速度增長。但是，很多信息并沒有做到恰當(dāng)?shù)摹坝成洹?，甚至包括很多?yīng)當(dāng)信任可以利用的數(shù)據(jù)。

解決信息過載問題一直是研究的重點(diǎn)，前人也提出了很多解決方案。自動化的推薦系統(tǒng)就是一個很好的幫用戶過濾信息的方案。

推薦系統(tǒng)在互聯(lián)網(wǎng)經(jīng)濟(jì)的很多方面扮演著至關(guān)重要的角色，例如社交網(wǎng)絡(luò)、物品推薦(電影、音樂等)。京東、天貓和豆瓣等許多互聯(lián)網(wǎng)，都已經(jīng)在推薦系統(tǒng)領(lǐng)域深耕多年，采用推薦技術(shù)來估計(jì)客戶的潛在偏好，針對性地向用戶推薦相關(guān)產(chǎn)品。由于其在用戶滿意度和商業(yè)上的出色表現(xiàn)，推薦系統(tǒng)已經(jīng)對實(shí)體經(jīng)濟(jì)產(chǎn)生了巨大影響。根據(jù)推薦系統(tǒng)計(jì)算的數(shù)據(jù)類型，以及在推薦系統(tǒng)中使用數(shù)據(jù)的方法，可以將其分成基于內(nèi)容的推薦算法(content-based，CB)，協(xié)同過濾(collaborative filtering，CF)和混合算法。例如基于內(nèi)容的推薦算法廣泛應(yīng)用于推薦系統(tǒng)設(shè)計(jì)和使用中，其使用物品的內(nèi)容創(chuàng)建特征和屬性來匹配給用戶推薦的物品。系統(tǒng)中的物品將依次與以前用戶喜歡的項(xiàng)目進(jìn)行比較，然后推薦給用戶相似度最高的項(xiàng)目[1]。所以，基于內(nèi)容的推薦算法的主要問題就是推薦系統(tǒng)需要去學(xué)習(xí)用戶的偏好，然后才能計(jì)算出其他物品與之的相關(guān)性。

協(xié)同過濾算法是目前推薦系統(tǒng)中最流行的算法，其利用過去從用戶行為中收集的大量數(shù)據(jù)來預(yù)測用戶會喜歡哪些項(xiàng)目，但并不需要去分析物品的內(nèi)容，取而代之的是計(jì)算用戶和物品之間的關(guān)系。如表1所示，這些關(guān)系依靠于一個以評分作為反饋的矩陣，每個元素代表特定用戶對特定物品的評分。矩陣縱坐標(biāo)是物品編號，橫坐標(biāo)是用戶編號，已經(jīng)有數(shù)值的即為該用戶對該物品的打分，分?jǐn)?shù)為1到5分，分?jǐn)?shù)越高表明用戶越喜愛這個物品。協(xié)同過濾算法的任務(wù)就是通過計(jì)算用戶-物品評分矩陣每一行或者每一列的相似性，來預(yù)測該矩陣中的缺失值。

表1 評分矩陣示例

但是在實(shí)際應(yīng)用時(shí)，協(xié)同過濾算法存在很嚴(yán)重的稀疏性和冷啟動(cold start)的問題。例如Netflix Prize大賽，世界著名的電影推薦大賽，其數(shù)據(jù)集中大約有48萬多用戶提供的關(guān)于18 000多部電影的共1億多個評分，但是其評分?jǐn)?shù)只占用了矩陣的大約1%。使用如此稀疏的評分矩陣來計(jì)算物品或者用戶之間的相似度，一定程度上來說是非常危險(xiǎn)的，矩陣越稀疏，數(shù)據(jù)帶給結(jié)果的隨機(jī)性就越大。另外一個問題就是冷啟動問題。當(dāng)一個物品剛剛上市的時(shí)候，推薦系統(tǒng)中并沒有對應(yīng)的評分矩陣來計(jì)算其與其他物品的相似性。協(xié)同過濾算法需要大量來自用戶對物品的評分才能對物品進(jìn)行有效的推薦，如果推薦系統(tǒng)中可用的評分很少，推薦系統(tǒng)就無法為新用戶和新物品做出準(zhǔn)確的判斷。

關(guān)鍵字提取可以作為一段文字的絕佳入口，發(fā)揮很大的作用[2]。比如在豆瓣等影評網(wǎng)站，用戶通過各種電影的評價(jià)文字可以發(fā)掘出很多的信息。然而很多內(nèi)容評價(jià)網(wǎng)站的評價(jià)關(guān)鍵字，仍然是用戶自己或者依靠管理員手動添加上去的，這無疑給關(guān)鍵字本身的獲取帶來了一定的困難。TF-IDF(term frequency-inverse document frequency，詞頻與逆文本指數(shù))是一種常用的關(guān)鍵字加權(quán)提取技術(shù)，其主要計(jì)算的就是一個詞對于該文檔以及文檔集合的重要性。

為了解決推薦矩陣的稀疏性問題，文中提出了一種提取影評關(guān)鍵字來輔助改進(jìn)傳統(tǒng)協(xié)同過濾推薦系統(tǒng)的模型。

2 相關(guān)工作

2.1 協(xié)同過濾算法

2.1.1 相似度計(jì)算過程

基于前文的描述，基于物品的協(xié)同過濾算法主要分為兩大步驟[1-7]：

(1)計(jì)算系統(tǒng)內(nèi)所有物品的相似度；

(2)根據(jù)用戶歷史評分物品記錄找到高分物品，然后推薦高分物品的相似物品。

而物品間相似度的計(jì)算方法又分為以下幾種：

(1)根據(jù)基于物品的協(xié)同過濾算法的設(shè)計(jì)初衷(購買了該物品的用戶同時(shí)也購買其他物品)，定義物品相似度計(jì)算公式如下：

(1)

其中，N(i)表示喜歡物品i的用戶數(shù)；N(i)∩N(j)表示同時(shí)喜歡物品i和物品j的用戶數(shù)。

但是，式1卻面臨著推薦系統(tǒng)中“長尾問題”的困擾，即很多熱門電影是大部分人都會喜歡的，所以熱門物品間會被計(jì)算為高度相似的物品，這顯然會影響推薦系統(tǒng)的準(zhǔn)確性。所以，可以將該公式改進(jìn)為：

(2)

在該公式下，給熱門物品進(jìn)行了降權(quán)，即懲罰了物品j的權(quán)重，因此可以在一定程度上避免熱門物品對物品相似度計(jì)算的影響[8-9]。

(2)余弦相似度。

(3)

其中，Ri,n和Rj,n分別表示用戶n對物品i和物品j的評分；Nij表示對物品i和物品j的共同評分用戶集合。

如果運(yùn)用余弦相似度計(jì)算公式，物品的所有評分?jǐn)?shù)據(jù)就會被看作是N維用戶空間上的向量，物品相似度的計(jì)算就是通過向量間的余弦夾角來衡量的，夾角越大，物品的相似度就越低。

(3)改進(jìn)的余弦相似度。

(4)

這樣改進(jìn)的目的是標(biāo)準(zhǔn)化評分，以防不同用戶的評分習(xí)慣不同，比如一些用戶打分均分偏高，可能會影響相似度的計(jì)算[10-12]。

2.1.2 推薦生成過程

計(jì)算出物品之間的相似度之后，基于物品的協(xié)同過濾推薦算法將根據(jù)用戶的高分物品，尋找其高度相似的物品，從而得到TOP-N推薦結(jié)果集[13-14]。

首先，算法需要構(gòu)建一個用戶-物品的倒排列表，即列出每個用戶高度喜歡的物品。然后根據(jù)喜愛的物品與物品列表中物品的相似度計(jì)算得到最終推薦分?jǐn)?shù)，即預(yù)測興趣度，公式如下[15]：

(5)

其中，N(u)是用戶喜歡的物品集合；S(j,K)是與物品j最相似的K個物品集合。

根本意義是與用戶的歷史喜歡物品越相似，越可能是用戶的潛在喜歡物品[15-16]。

2.2 關(guān)鍵字提取算法與文本處理

2.2.1 關(guān)鍵字提取算法

TF-IDF是一種常見的用于信息檢索和數(shù)據(jù)挖掘的加權(quán)技術(shù)，也是很好理解的關(guān)鍵字提取算法。本質(zhì)上來講，TF-IDF就是通過特定文檔中詞的相對頻率和整個文檔語料庫中該詞的反比例進(jìn)行比較，即其計(jì)算的就是某單詞在特定文檔中的相關(guān)系數(shù)。TF-IDF的公式如下：

wd=fw,d*log(|D|/fw,D)

(6)

其中，D為給定的已經(jīng)整理的文檔集合，|D|是語料庫的大小；w為特定的單詞，另外還有文檔d∈D；fw,d為w出現(xiàn)在d中的次數(shù)；fw,D為D中包含w的文檔數(shù)。

根據(jù)fw,D和fw,d權(quán)值的不同，最終wd的結(jié)果不盡相同，因此文中的不同wd的詞匯帶來不同的意義。

TF-IDF算法是建立于這樣一個假設(shè)：如果一個單詞能夠很有效地區(qū)分出這篇文章與其他文章，那么這個單詞應(yīng)該在本文中高頻率的出現(xiàn)，而在整個文檔集中的其他文檔中出現(xiàn)較少。所以TF詞頻是一個很好地衡量是否是同類文本的權(quán)值[17]。另外，一個單詞如果其出現(xiàn)的文本頻率越低，它區(qū)別不同類別文本的能力也會變得越強(qiáng)，所以該算法引入了IDF逆文本頻率的概念[18]。

但是，傳統(tǒng)的TF-IDF仍然存在各種各樣的不足。根據(jù)IDF的公式，某些特征詞的IDF值會很低，意味著該特征詞可能不具有代表性。但是在實(shí)際情況中，如果某一個詞匯在某一類文本中大規(guī)模的出現(xiàn)，則說明該詞匯能夠很好地表示出該類文本的內(nèi)容取向，像這樣的詞匯應(yīng)該給予其很高的權(quán)重值，用來計(jì)算文本之間的相似性，從來推薦相似特征的電影。所以傳統(tǒng)TD-IDF公式會出現(xiàn)兩個缺陷：部分不能代表文本內(nèi)容的低頻詞匯，其IDF值可能相對很高；一些真正能夠代表文本內(nèi)容的關(guān)鍵詞的IDF值卻非常低。所以要對傳統(tǒng)IF-IDF公式進(jìn)行一定的改進(jìn)[19-20]。

首先，需要引入歸一化的思想。因?yàn)楦鶕?jù)原公式，文本的長短會對TF-IDF的最終結(jié)果產(chǎn)生影響，所以要對其權(quán)值進(jìn)行歸一化處理，使得最終結(jié)果大于等于0且小于等于1，公式如下：

(7)

其次，一個詞在全文的跨度也可以在一定意義上表現(xiàn)出該詞的重要性?？绲木渥釉蕉?，在全文的代表性就越高。傳統(tǒng)TF-IDF的權(quán)值計(jì)算過程中，局部關(guān)鍵詞很有可能因?yàn)樵诰植康母哳l率出現(xiàn)而降低了提取關(guān)鍵詞的準(zhǔn)確性，所以可以進(jìn)一步改進(jìn)TF-IDF公式：

Wd=

(8)

其中，li表示句子出現(xiàn)的句子數(shù)；L表示句子總數(shù)。

2.2.2 文本處理

(1)停止詞。

停止詞(stop words)就是一些在某種語言中大范圍使用的詞，但是對分析文本并沒有太大意義，比如說“我們”“可能”“所以”等。所以要對這些停止詞進(jìn)行一些處理，但面對不同類型的需求的時(shí)候，對停止詞的處理方法是不盡相同的。比如聚類算法中就可能要減少停止詞的權(quán)值，信息檢索的時(shí)候就不會檢索停止詞，而文中需要直接刪除停止詞，以防某些停止詞的出現(xiàn)干擾文本TF-IDF算法的計(jì)算結(jié)果。同時(shí)停止詞的過濾可以降低系統(tǒng)處理語句的量，減少非內(nèi)容信息詞的干擾。當(dāng)然停止詞的使用必須謹(jǐn)慎，以免丟失關(guān)鍵的文本信息。

(2)同義詞。

英文和中文一樣，會包含大量的同義詞，而推薦系統(tǒng)計(jì)算相似性時(shí)，不同的單詞可能會被理解成不同的意義，從而增加了維度，但是因?yàn)槭峭x詞，它們應(yīng)當(dāng)代表的是同一維度。因?yàn)槠浔旧砗械囊饬x應(yīng)該是相同的或者相近的，所以為了提高推薦系統(tǒng)的精確性和計(jì)算效率，必須將同義詞進(jìn)行精確的替換，替換為某一個指定的詞。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用著名的MovieLens電影數(shù)據(jù)集。該數(shù)據(jù)集是由明尼蘇達(dá)大學(xué)GroupLens項(xiàng)目組創(chuàng)辦的一個開源的站點(diǎn)，包含了很多開源數(shù)據(jù)集，文中使用其中的MovieLens 1M Dataset，包含了“評分”、“用戶”和“電影”四張表(英文)。評分表包括用戶ID，電影ID，對應(yīng)評分以及時(shí)間戳。用戶表包括用戶ID，性別，年齡段，職業(yè)以及郵編。電影表是電影ID，電影名與年代，以及電影分類(例如喜劇，浪漫等)。

為突出該實(shí)驗(yàn)方案解決稀疏矩陣相似性計(jì)算問題的能力，進(jìn)行了人工預(yù)處理，去除掉了部分評分，使得評分矩陣的某些維度更加稀疏。預(yù)處理后共有3 883部電影，80萬個評分?jǐn)?shù)據(jù)以及6 040個用戶。

另外實(shí)驗(yàn)采用的影評數(shù)據(jù)集采集自著名影評網(wǎng)站IMDB(Internet movie database，互聯(lián)網(wǎng)電影資料庫)，其創(chuàng)建于1990年，是一個專業(yè)且嚴(yán)肅的影評網(wǎng)站。根據(jù)MovieLens的電影名從各自的頁面中爬取影評作為TF-IDF的數(shù)據(jù)集。

3.2 實(shí)驗(yàn)?zāi)Ｐ驮O(shè)計(jì)

為了驗(yàn)證TF-IDF在改進(jìn)協(xié)同過濾算法的可行性，進(jìn)行了幾組對比實(shí)驗(yàn)，首先是傳統(tǒng)的協(xié)同過濾算法實(shí)驗(yàn)。首先計(jì)算物品之間的相似度，然后根據(jù)物品之間的相似度和用戶的歷史打分物品給出最終的推薦列表。其次就是使用TF-IDF的改進(jìn)公式來改進(jìn)傳統(tǒng)協(xié)同過濾算法(CF)中“稀疏矩陣”的相似性計(jì)算(簡稱TI-CF算法)。該實(shí)驗(yàn)先使用TF-IDF算法抽取權(quán)值前10的關(guān)鍵詞來計(jì)算物品相似度，然后取出TOP-N的物品，和傳統(tǒng)相似度計(jì)算方法的TOP-N物品根據(jù)相似度大小(已經(jīng)歸一化)排名取合集TOP-N，作為最后的推薦物品集合。

3.3 實(shí)驗(yàn)評價(jià)體系

文中使用準(zhǔn)確率、召回率以及覆蓋率評價(jià)該模型的推薦性能。設(shè)給用戶u推薦N個物品的集合為R(u)，令用戶u在測試集上評分的物品集合為T(u)，則準(zhǔn)確率和召回率的公式為：

(9)

(10)

準(zhǔn)確率反映了正確被評分的項(xiàng)目占推薦項(xiàng)目的比例，召回率反映了正確被評分的物品占用戶實(shí)際喜歡的物品的比例。兩者取值在0和1之間，數(shù)值越接近1，準(zhǔn)確率和覆蓋率就越高。

覆蓋率反映了推薦算法挖掘長尾的能力。長尾效應(yīng)指的是這樣一種現(xiàn)象：數(shù)量占少數(shù)的熱門商品，往往貢獻(xiàn)了網(wǎng)站的大部分流量。其最初由“連線”的總編輯克里斯·安德森(Chris Anderson)于2004年發(fā)表，主要表達(dá)諸如Amazon和Netflix此類的商業(yè)網(wǎng)站的盈利途徑。其強(qiáng)調(diào)那些銷量小而且及其龐大的商品能夠給公司帶來的收益，往往大大超過那些所謂的熱門商品。如果推薦系統(tǒng)片面地推薦了熱門商品，那么這個系統(tǒng)并沒有分析出有意義的價(jià)值，真正的價(jià)值應(yīng)該是發(fā)現(xiàn)冷門的但是很有商業(yè)潛力的商品。

(11)

3.4 實(shí)驗(yàn)結(jié)果

如圖1～3所示，物品的相似性計(jì)算過程經(jīng)過關(guān)鍵詞提取技術(shù)的改進(jìn)后，最終推薦結(jié)果在各種TOP-N取值下，其準(zhǔn)確率、召回率和覆蓋率均有一定的提升。

圖1 準(zhǔn)確率

圖2 召回率

圖3 覆蓋率

證明通過文本提取關(guān)鍵字的路徑，可以成功挖掘到文本相關(guān)電影的內(nèi)容特征，進(jìn)而輔助相似度計(jì)算的過程，最終在一定程度上解決矩陣稀疏的問題，提升推薦系統(tǒng)用戶體驗(yàn)，從而給電影推薦網(wǎng)站帶來盈利。

4 結(jié)束語

傳統(tǒng)協(xié)同過濾算法發(fā)展至今，已經(jīng)有了很大的成就。但是面對冷啟動以及數(shù)據(jù)稀疏問題時(shí)，精確率等評價(jià)標(biāo)準(zhǔn)會顯著下降，這時(shí)就需要去挖掘其他信息來完善物品相似度的計(jì)算，各種電影的影評就是來源之一。如果是一個創(chuàng)業(yè)期電影網(wǎng)站，面對冷啟動以及矩陣稀疏問題時(shí)，就可以從其電影的影評等文字?jǐn)?shù)據(jù)中獲得有效的信息，從而準(zhǔn)確計(jì)算電影相似度，推薦相似類型電影。

TF-IDF算法仍然有很多挖掘的潛力，深度學(xué)習(xí)在推薦系統(tǒng)領(lǐng)域的作用也正在逐漸展現(xiàn)[19]，值得進(jìn)一步去研究。