基于用戶屬性聚類與矩陣填充的景點推薦算法

劉榮權，袁仕芳，趙錦珍，楊偉杰

(五邑大學 數學與計算科學學院，廣東 江門 529020)

0 引 言

在當今數據化時代，人們出行需要從海量景點信息中選取自己喜歡的景點，導致旅游用戶出行前有選擇困難。為了解決這個問題，許多旅游推薦系統會根據用戶的行為特征，給用戶推薦一些可能喜歡的景點，幫助用戶做出選擇。近幾年來，基于用戶的協同過濾算法和基于項目的協同過濾算法[1]在這方面起到了重要的作用。目前有很多學者不斷改進傳統的協同過濾算法，以提高旅游推薦的質量[2-4]。

傳統協同過濾算法主要是根據評分矩陣計算推薦結果，評分矩陣的好壞直接影響推薦的質量。評分矩陣最大的不足是數據稀疏[5]，因為大部分用戶去過的旅游景點數較少，只會對海量景點中的少數景點做出評分，從而做出的評分數量很少，使得評分矩陣出現大量的缺失值。

針對上述問題，該文嘗試基于用戶的屬性對用戶進行聚類，計算目標用戶與同一類中的其他用戶的相似度，這樣不僅減少了計算量，而且使所得近鄰用戶集更準確。然后用奇異值分解算法填充評分矩陣，從而在計算預測評分時減少數據稀疏帶來的影響，提高預測評分的準確性。

1 用戶屬性聚類

目前傳統k-means算法[6]和二分k-means聚類算法[7]在用戶屬性聚類算法中有重要應用。傳統k-means算法：隨機選取初始簇心、無法確定類別個數造成聚類誤差較大，文獻[8]證明了二分k-means聚類減小初始隨機選取簇心的影響,降低聚類誤差。傳統的推薦算法是在單一的評分矩陣中給目標用戶推薦項目，如果數據過于稀疏，將導致目標用戶的近鄰用戶集不準確。本節主要討論將二分k-means聚類算法應用到用戶屬性聚類中，因為同一類用戶的特征越相似，則它們的相似度越高，這使得目標用戶的相近鄰用戶集越準確。

1.1 旅游用戶屬性預處理

用戶屬性是指用戶的一些基本特征。在文獻[9]中提到，影響用戶出行的因素主要有職業、性別、年齡、出行時段、出游陪同、人均消費和出發天數。以文獻[9]為基礎，該文選取用戶性別、注冊年份、天數、出發時間、陪同、人均消費和玩法作為用戶屬性，構成數據集。對數據集進行量化，玩法量化主要計算每個用戶的玩法的詞頻和與總玩法的詞頻和之比。量化如表1所示。

表1 用戶屬性量化

續表1

1.2 二分k-means聚類

定義用戶集{xi|i=1,2,…,n}和用戶屬性集{aij|j=1,2,…,7}(例如用ai1可表示用戶i的性別屬性值，后面的以此類推)，對每一個用戶屬性集進行歸一化處理，消除指標之間的量綱的影響，處理方法如下：

其中， max(aj)、min(aj)是用戶屬性j的最大值、最小值。

k-means聚類算法描述如下：

輸入：用戶屬性集合，聚類數K。

輸出：K個聚類結果。

(1)初始化K個聚類中心。在每個屬性的范圍內選擇K個隨機值，生成K個聚類中心，以保證每個聚類中心仍處于原數據集內。定義第i個聚類中心為：

ci={ci1,ci2,…,ci7},i∈{i|1≤i≤K,i∈N}

cij=[max(aj)-min(aj)]·rand+min(aj)

{j|1≤j≤7}

其中，rand是(0,1)之間的隨機數，cij是聚類中心ci第j個用戶屬性的隨機值。

(2)計算所有樣本點到K個聚類中心的歐氏距離，并把樣本點歸類到距離最小的類中。計算公式如下：

d(xi,cj)=

其中，xi是第i個用戶的用戶屬性向量，cj是第j類的聚類中心。

當聚類數K=2時，k-means算法變為二分k-means算法，它的主要聚類過程是k-means算法。算法一般采用誤差平方和作為目標函數，不斷迭代優化聚類結果，當目標函數收斂，迭代結束。目標函數如下：

其中，error為所有用戶與對應聚類中心的誤差平方和，ci為第i類的聚類中心，x為第i類的樣本點。

二分k-means聚類算法描述如下：

輸入：用戶屬性集合，聚類數K。

輸出：K個聚類結果。

(1)初始時，建立類表(用于存儲二分聚類結果)，將所有用戶視為同一類c并存入類表。

(2)當類表中只有一類c時，將此類c中所有用戶屬性代入上述k-means聚類算法(K=2)，得到兩個新類c1,c2，存入類表并取代c。

當類表中有兩類及以上時，以聚類后所得誤差平方和最小為目標，遍歷當前類表中的所有類，執行上述k-means聚類算法；當遍歷完畢時，若某類滿足上述目標，使其成為目標類并執行二分聚類，將所得兩個新類取代目標類。

(3)當K達到輸入要求時，算法停止，否則繼續執行步驟(2)。

2 景點推薦算法

上一節對用戶屬性進行二分k-means聚類，使同一類中的用戶具有更高的相似度；在計算目標用戶與同一類其他用戶的相似度時，不僅減少了計算量，而且使所得近鄰用戶集更準確。但在實際中，用戶之間共同評分的景點數較少，使評分矩陣稀疏程度偏大。本節采用文獻[10]中的矩陣奇異值分解(SVD)對用戶景點評分矩陣進行填補，并基于用戶的協同過濾算法，預測目標用戶景點評分。

2.1 傳統的協同過濾算法

傳統的協同過濾算法包括基于用戶的協同過濾算法和基于項目的協同過濾算法[11]。由于大部分景點缺失描述信息，也沒有相應描述標簽，使景點之間的相似度不易計算。若采用基于項目的協同過濾算法進行推薦，則難以實施。因此該文采用基于用戶的協同過濾算法。

它的主要內容如下：

(1)構建用戶景點評分矩陣。

收集m個用戶對n個景點的評分數據，定義用戶集{x|x1,x2,…,xm}，景點集{y|y1,y2,…,yn}，構成大小m×n的評分矩陣，如圖1所示。

圖1 用戶-景點評分矩陣

其中，S(xi,yj)為用戶xi對景點yj的評分；規定用戶未評價景點的評分為-1，依據用戶對景點的喜愛程度，將評分設為五分制。

(2)用戶相似度。

在推薦系統中，計算相似度的方法有Jaccard相關系數[12]、余弦相似度和Pearson相關系數等等[13]，其中Pearson相關系數應用較為廣泛。該文使用Pearson相關系數計算用戶相似度，公式如下：

(3)景點評分預測。

2.2 SVD算法填充矩陣

在推薦系統中，用戶景點評分矩陣的數據稀疏性嚴重影響推薦算法的預測準確度。對于數據稀疏，文獻[15]的解決辦法有：簡單的數據填補、對用戶進行聚類和數據降維。

本節采用SVD算法[16]對原數據進行降維分解，最大程度地保留原數據的信息，填充原數據的缺失值，得到完整的評分矩陣。填充過程描述如下：

在Σm×n中，對角元素稱為奇異值，它包含著R'中重要的信息，這也是數據降維的關鍵。

(2)規定閾值為95%。當前k個奇異值的累計貢獻率達到95%，可認為這前k個奇異值保存足夠的特征。

(5) 對缺失值進行預測。計算用戶x在景點i缺失值的預測評分，可以通過下式求解：

2.3 總體的算法流程

算法實現流程如圖2所示。

圖2 算法實現流程

3 數據實驗與分析

3.1 實驗環境

實驗環境為Windows7、64位操作系統，所用編程語言為Python。

3.2 實驗數據

該研究在攜程網站(www.ctrip.com)，以“深圳”為關鍵字，收集用戶和評分數據。共獲得1 551個用戶數據以及用戶對49個景點的評分數據。分析可知，評分矩陣的稀疏度為92.5%。隨機選取80%的實驗數據作為訓練集，20%作為測試集。

3.3 評測指標

MAE的定義如下：

其中，|N|是未評分的景點數量。

3.4 實驗結果與分析

初始時，二分k-means聚類數K是一個不確定值。以二分聚類結果的誤差平方和最小為目標，循環運算二分k-means聚類算法得到最優的K值。從圖3中可見，當聚類數為5時，誤差平方和最小。綜上該文選取聚類K=5。

圖3 最佳K聚類數

對于多維聚類，利用Python的TSNE進行數據可視化，將五維數據的聚類結果展示到二維空間，如圖4所示。可見原數據聚類成五類，同一類中聚攏程度高，不同類間分界明顯，聚類效果符合預期目標。

為了評測該算法的推薦質量，將基于用戶的協同過濾算法、經聚類優化后的協同過濾算法與文中算法進行比較。三個算法在不同的近鄰用戶數量下，計算MAE并比較，結果如圖5所示。

圖4 聚類結果可視化

圖5 不同算法比較

由圖5可知，在不同的近鄰用戶數量下，文中算法所得MAE值均比基于用戶的協同過濾算法、聚類后的協同過濾算法的小，說明文中算法的景點預測評分與真實評分之間誤差最小，推薦質量最優。基于用戶的協同過濾算法使用較稀疏的評分矩陣計算相似度，所得MAE值最大；對用戶屬性進行聚類的協同過濾算法在一定程度上使所得目標用戶的近鄰用戶集更準確，所得MAE值較小；而該文對用戶進行屬性聚類并填充稀疏的評分矩陣，減小數據的稀疏度，所得MAE值在三者中最小。

4 結束語

針對旅游數據稀疏性偏大的問題，對用戶屬性進行二分k-means聚類，對評分矩陣進行填充，得到完整的用戶評分矩陣；在目標用戶所在的類別中，對目標用戶計算Pearson相似度，找到目標用戶的近鄰用戶集；計算目標用戶對未游覽景點的預測評分，構成Top-N推薦列表，向目標用戶展示。實驗表明，該算法的推薦質量優于傳統推薦算法。