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

劉榮權(quán)，袁仕芳，趙錦珍，楊偉杰

(五邑大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣東 江門 529020)

0 引 言

在當(dāng)今數(shù)據(jù)化時(shí)代，人們出行需要從海量景點(diǎn)信息中選取自己喜歡的景點(diǎn)，導(dǎo)致旅游用戶出行前有選擇困難。為了解決這個(gè)問(wèn)題，許多旅游推薦系統(tǒng)會(huì)根據(jù)用戶的行為特征，給用戶推薦一些可能喜歡的景點(diǎn)，幫助用戶做出選擇。近幾年來(lái)，基于用戶的協(xié)同過(guò)濾算法和基于項(xiàng)目的協(xié)同過(guò)濾算法[1]在這方面起到了重要的作用。目前有很多學(xué)者不斷改進(jìn)傳統(tǒng)的協(xié)同過(guò)濾算法，以提高旅游推薦的質(zhì)量[2-4]。

傳統(tǒng)協(xié)同過(guò)濾算法主要是根據(jù)評(píng)分矩陣計(jì)算推薦結(jié)果，評(píng)分矩陣的好壞直接影響推薦的質(zhì)量。評(píng)分矩陣最大的不足是數(shù)據(jù)稀疏[5]，因?yàn)榇蟛糠钟脩羧ミ^(guò)的旅游景點(diǎn)數(shù)較少，只會(huì)對(duì)海量景點(diǎn)中的少數(shù)景點(diǎn)做出評(píng)分，從而做出的評(píng)分?jǐn)?shù)量很少，使得評(píng)分矩陣出現(xiàn)大量的缺失值。

針對(duì)上述問(wèn)題，該文嘗試基于用戶的屬性對(duì)用戶進(jìn)行聚類，計(jì)算目標(biāo)用戶與同一類中的其他用戶的相似度，這樣不僅減少了計(jì)算量，而且使所得近鄰用戶集更準(zhǔn)確。然后用奇異值分解算法填充評(píng)分矩陣，從而在計(jì)算預(yù)測(cè)評(píng)分時(shí)減少數(shù)據(jù)稀疏帶來(lái)的影響，提高預(yù)測(cè)評(píng)分的準(zhǔn)確性。

1 用戶屬性聚類

目前傳統(tǒng)k-means算法[6]和二分k-means聚類算法[7]在用戶屬性聚類算法中有重要應(yīng)用。傳統(tǒng)k-means算法：隨機(jī)選取初始簇心、無(wú)法確定類別個(gè)數(shù)造成聚類誤差較大，文獻(xiàn)[8]證明了二分k-means聚類減小初始隨機(jī)選取簇心的影響,降低聚類誤差。傳統(tǒng)的推薦算法是在單一的評(píng)分矩陣中給目標(biāo)用戶推薦項(xiàng)目，如果數(shù)據(jù)過(guò)于稀疏，將導(dǎo)致目標(biāo)用戶的近鄰用戶集不準(zhǔn)確。本節(jié)主要討論將二分k-means聚類算法應(yīng)用到用戶屬性聚類中，因?yàn)橥活愑脩舻奶卣髟较嗨疲瑒t它們的相似度越高，這使得目標(biāo)用戶的相近鄰用戶集越準(zhǔn)確。

1.1 旅游用戶屬性預(yù)處理

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

表1 用戶屬性量化

續(xù)表1

1.2 二分k-means聚類

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

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

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

輸入：用戶屬性集合，聚類數(shù)K。

輸出：K個(gè)聚類結(jié)果。

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

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)之間的隨機(jī)數(shù)，cij是聚類中心ci第j個(gè)用戶屬性的隨機(jī)值。

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

d(xi,cj)=

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

當(dāng)聚類數(shù)K=2時(shí)，k-means算法變?yōu)槎謐-means算法，它的主要聚類過(guò)程是k-means算法。算法一般采用誤差平方和作為目標(biāo)函數(shù)，不斷迭代優(yōu)化聚類結(jié)果，當(dāng)目標(biāo)函數(shù)收斂，迭代結(jié)束。目標(biāo)函數(shù)如下：

其中，error為所有用戶與對(duì)應(yīng)聚類中心的誤差平方和，ci為第i類的聚類中心，x為第i類的樣本點(diǎn)。

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

輸入：用戶屬性集合，聚類數(shù)K。

輸出：K個(gè)聚類結(jié)果。

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

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

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

(3)當(dāng)K達(dá)到輸入要求時(shí)，算法停止，否則繼續(xù)執(zhí)行步驟(2)。

2 景點(diǎn)推薦算法

上一節(jié)對(duì)用戶屬性進(jìn)行二分k-means聚類，使同一類中的用戶具有更高的相似度；在計(jì)算目標(biāo)用戶與同一類其他用戶的相似度時(shí)，不僅減少了計(jì)算量，而且使所得近鄰用戶集更準(zhǔn)確。但在實(shí)際中，用戶之間共同評(píng)分的景點(diǎn)數(shù)較少，使評(píng)分矩陣稀疏程度偏大。本節(jié)采用文獻(xiàn)[10]中的矩陣奇異值分解(SVD)對(duì)用戶景點(diǎn)評(píng)分矩陣進(jìn)行填補(bǔ)，并基于用戶的協(xié)同過(guò)濾算法，預(yù)測(cè)目標(biāo)用戶景點(diǎn)評(píng)分。

2.1 傳統(tǒng)的協(xié)同過(guò)濾算法

傳統(tǒng)的協(xié)同過(guò)濾算法包括基于用戶的協(xié)同過(guò)濾算法和基于項(xiàng)目的協(xié)同過(guò)濾算法[11]。由于大部分景點(diǎn)缺失描述信息，也沒(méi)有相應(yīng)描述標(biāo)簽，使景點(diǎn)之間的相似度不易計(jì)算。若采用基于項(xiàng)目的協(xié)同過(guò)濾算法進(jìn)行推薦，則難以實(shí)施。因此該文采用基于用戶的協(xié)同過(guò)濾算法。

它的主要內(nèi)容如下：

(1)構(gòu)建用戶景點(diǎn)評(píng)分矩陣。

收集m個(gè)用戶對(duì)n個(gè)景點(diǎn)的評(píng)分?jǐn)?shù)據(jù)，定義用戶集{x|x1,x2,…,xm}，景點(diǎn)集{y|y1,y2,…,yn}，構(gòu)成大小m×n的評(píng)分矩陣，如圖1所示。

圖1 用戶-景點(diǎn)評(píng)分矩陣

其中，S(xi,yj)為用戶xi對(duì)景點(diǎn)yj的評(píng)分；規(guī)定用戶未評(píng)價(jià)景點(diǎn)的評(píng)分為-1，依據(jù)用戶對(duì)景點(diǎn)的喜愛(ài)程度，將評(píng)分設(shè)為五分制。

(2)用戶相似度。

在推薦系統(tǒng)中，計(jì)算相似度的方法有Jaccard相關(guān)系數(shù)[12]、余弦相似度和Pearson相關(guān)系數(shù)等等[13]，其中Pearson相關(guān)系數(shù)應(yīng)用較為廣泛。該文使用Pearson相關(guān)系數(shù)計(jì)算用戶相似度，公式如下：

(3)景點(diǎn)評(píng)分預(yù)測(cè)。

2.2 SVD算法填充矩陣

在推薦系統(tǒng)中，用戶景點(diǎn)評(píng)分矩陣的數(shù)據(jù)稀疏性嚴(yán)重影響推薦算法的預(yù)測(cè)準(zhǔn)確度。對(duì)于數(shù)據(jù)稀疏，文獻(xiàn)[15]的解決辦法有：簡(jiǎn)單的數(shù)據(jù)填補(bǔ)、對(duì)用戶進(jìn)行聚類和數(shù)據(jù)降維。

本節(jié)采用SVD算法[16]對(duì)原數(shù)據(jù)進(jìn)行降維分解，最大程度地保留原數(shù)據(jù)的信息，填充原數(shù)據(jù)的缺失值，得到完整的評(píng)分矩陣。填充過(guò)程描述如下：

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

(2)規(guī)定閾值為95%。當(dāng)前k個(gè)奇異值的累計(jì)貢獻(xiàn)率達(dá)到95%，可認(rèn)為這前k個(gè)奇異值保存足夠的特征。

(5) 對(duì)缺失值進(jìn)行預(yù)測(cè)。計(jì)算用戶x在景點(diǎn)i缺失值的預(yù)測(cè)評(píng)分，可以通過(guò)下式求解：

2.3 總體的算法流程

算法實(shí)現(xiàn)流程如圖2所示。

圖2 算法實(shí)現(xiàn)流程

3 數(shù)據(jù)實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為Windows7、64位操作系統(tǒng)，所用編程語(yǔ)言為Python。

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

該研究在攜程網(wǎng)站(www.ctrip.com)，以“深圳”為關(guān)鍵字，收集用戶和評(píng)分?jǐn)?shù)據(jù)。共獲得1 551個(gè)用戶數(shù)據(jù)以及用戶對(duì)49個(gè)景點(diǎn)的評(píng)分?jǐn)?shù)據(jù)。分析可知，評(píng)分矩陣的稀疏度為92.5%。隨機(jī)選取80%的實(shí)驗(yàn)數(shù)據(jù)作為訓(xùn)練集，20%作為測(cè)試集。

3.3 評(píng)測(cè)指標(biāo)

MAE的定義如下：

其中，|N|是未評(píng)分的景點(diǎn)數(shù)量。

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

初始時(shí)，二分k-means聚類數(shù)K是一個(gè)不確定值。以二分聚類結(jié)果的誤差平方和最小為目標(biāo)，循環(huán)運(yùn)算二分k-means聚類算法得到最優(yōu)的K值。從圖3中可見(jiàn)，當(dāng)聚類數(shù)為5時(shí)，誤差平方和最小。綜上該文選取聚類K=5。

圖3 最佳K聚類數(shù)

對(duì)于多維聚類，利用Python的TSNE進(jìn)行數(shù)據(jù)可視化，將五維數(shù)據(jù)的聚類結(jié)果展示到二維空間，如圖4所示?？梢?jiàn)原數(shù)據(jù)聚類成五類，同一類中聚攏程度高，不同類間分界明顯，聚類效果符合預(yù)期目標(biāo)。

為了評(píng)測(cè)該算法的推薦質(zhì)量，將基于用戶的協(xié)同過(guò)濾算法、經(jīng)聚類優(yōu)化后的協(xié)同過(guò)濾算法與文中算法進(jìn)行比較。三個(gè)算法在不同的近鄰用戶數(shù)量下，計(jì)算MAE并比較，結(jié)果如圖5所示。

圖4 聚類結(jié)果可視化

圖5 不同算法比較

由圖5可知，在不同的近鄰用戶數(shù)量下，文中算法所得MAE值均比基于用戶的協(xié)同過(guò)濾算法、聚類后的協(xié)同過(guò)濾算法的小，說(shuō)明文中算法的景點(diǎn)預(yù)測(cè)評(píng)分與真實(shí)評(píng)分之間誤差最小，推薦質(zhì)量最優(yōu)?；谟脩舻膮f(xié)同過(guò)濾算法使用較稀疏的評(píng)分矩陣計(jì)算相似度，所得MAE值最大；對(duì)用戶屬性進(jìn)行聚類的協(xié)同過(guò)濾算法在一定程度上使所得目標(biāo)用戶的近鄰用戶集更準(zhǔn)確，所得MAE值較?。欢撐膶?duì)用戶進(jìn)行屬性聚類并填充稀疏的評(píng)分矩陣，減小數(shù)據(jù)的稀疏度，所得MAE值在三者中最小。

4 結(jié)束語(yǔ)

針對(duì)旅游數(shù)據(jù)稀疏性偏大的問(wèn)題，對(duì)用戶屬性進(jìn)行二分k-means聚類，對(duì)評(píng)分矩陣進(jìn)行填充，得到完整的用戶評(píng)分矩陣；在目標(biāo)用戶所在的類別中，對(duì)目標(biāo)用戶計(jì)算Pearson相似度，找到目標(biāo)用戶的近鄰用戶集；計(jì)算目標(biāo)用戶對(duì)未游覽景點(diǎn)的預(yù)測(cè)評(píng)分，構(gòu)成Top-N推薦列表，向目標(biāo)用戶展示。實(shí)驗(yàn)表明，該算法的推薦質(zhì)量?jī)?yōu)于傳統(tǒng)推薦算法。