一種結合時間因子聚類的群組興趣點推薦模型

陶永才,曹朝陽,石 磊,衛 琳

1(鄭州大學 信息工程學院,鄭州 450001)2(鄭州大學 軟件技術學院,鄭州 450002)

1 引 言

近年來,由于個人電腦和網絡的普及,大量用戶和用戶信息涌入互聯網.在用戶向互聯網不斷提供信息、文件、多媒體資源的同時,也在不斷的從互聯網中查詢和獲得各種需要的信息和資源.因此推薦系統伴隨各種應用快速發展.

作為數據過濾工具的一種,推薦系統通過挖掘、整理、分析用戶在網站上的行為軌跡和數據,并對這些數據進行建模,從而得到用戶隱式的需求和興趣信息.

現存經典推薦系統通常傾向于為單個用戶進行推薦.而隨著移動設備的普及和各種社交網絡的app的出現,傳統的線下集體活動開始逐漸轉變為以網絡為媒體的線上群組活動,如去餐廳就餐,度假旅游,家庭娛樂視頻等.因此,推薦系統需要以群組為單位,綜合考慮群組中用戶權重與偏好,生成群組推薦.由此組推薦系統(group recommender system)產生.

本文提出一個基于時間因子聚類的群組興趣點推薦模型(A Group POI Recommendation Model Based on Time Factor Clustering,AGRT),考慮到用戶在一天當中不同時間點的不同興趣點偏好,并結合隱語義推薦模型對群組興趣點進行推薦,較好的克服了用戶數據稀疏性問題.

2 相關工作

目前主流的組推薦系統推薦策略通常使用協同過濾推薦(collaborative filtering,簡稱CF)向組用戶產生推薦.這些策略通常可以分為兩類:基于內存的協同過濾推薦(memory-based CF)和基于模型的協同過濾推薦(model-based CF).其中,基于內存的協同過濾推薦按照融合策略的不同又分為基于個人模型的融合策略(aggregating individual model,AIM)和基于個人預測融合策略(aggregating individual prediction,AIP).基于個人模型的融合策略首先融合群組成員的偏好為組偏好然后利用傳統個人推薦算法進行推薦;而基于個人預測的融合策略首先為每個群組成員生成個人推薦,然后融合這些個人推薦列表生成組推薦[1].

Wang,Liu等人梳理了傳統個性化推薦系統的概念以及傳統推薦系統的各個模塊以及各個模塊常用的建模方法,傳統推薦算法種類以及推薦系統評價標準[12].Zhang,Du等人引入了組推薦系統的概念,詳細比較了組推薦系統與傳統推薦系統的不同,并介紹了組推薦系統的各個環節所用的技術,偏好融合策略、群組特征對偏好融合策略的影響以及組推薦系統評價標準[14].文獻[2]基于組用戶易受群組中專家成員意見影響的趨向提出了一種基于注意力機制的組推薦模型(AGR),利用該模型學習群組中專家成員對其他成員影響并能夠針對不同的領域推薦調整模型.

當前個性化推薦的研究熱點主要集中于群組、興趣點推薦[3-11].組推薦系統研究的主要問題之一是如何在現有融合策略中進行選擇以及如何對選擇后的融合策略根據用戶模型特點進行改進.偏好融合方法的選擇需要考慮群組類型、群組規模以及具體的推薦算法等因素.模型融合則不能忽視評分稀疏性的影響,評分少的群組成員在一般模型融合時對群組偏好模型的影響也較小,就產生了模型融合中所謂的不公平問題.推薦融合方法則沒有將群組成員之間的相互影響考慮在內.組內相似度也對融合方法有著不可忽略的影響,文獻[14]提出大部分的模型融合方法和推薦融合方法的準確度與組內相似度存在正相關關系.

3 結合時間因子的群組興趣點推薦模型

群組用戶對興趣點的選擇受到各種因素的影響,其中無法忽視的影響之一就是用戶一天當中所處的時間點,在不同的時間點用戶所感興趣的地點也不相同.因此本文提出的AGRT模型結合K-menas聚類算法,對用戶簽到地點以時間軌跡進行聚類,結合當前時間生成群組數據集,通過LFM隱語義算法計算出個人推薦列表,然后對結果使用加權混合融合策略,最終產生群組推薦.

AGRT模型推薦過程如圖 1所示.

①獲取數據,對用戶數據集用K-means算法進行聚類；

②根據當前時間整理出群組成員User-item矩陣,用LFM隱語義模型生成組成員個人推薦列表；

③根據群組分歧度和群組成員權重,選用合適的加權算法,生成組推薦列表,將組推薦列表的首個推薦推薦給該群組.

3.1 個人推薦列表

3.1.1 K-means算法

作為一種啟發式迭代聚類算法,K-means算法的主要思想是以距離作為度量指標,將樣本集劃分為若干個簇.K-means聚類的目標是簇內樣本點間距離盡可能小,簇間距離盡可能大.如果選取歐式距離作為相似度指標,該算法最小化公式如式(1)所示.

(1)

在本文中,對用戶數據集使用K-Means算法,步驟如下:

1)從數據集中選取k個樣本,以其為初始簇心(以簽到時間點為選擇依據,采用隨機選取方式):{μ1,μ2,…,μk}；

圖1 AGRT推薦流程Fig.1 Recommended flow

2)計算每個樣本點與簇心之間的距離,將其劃分到距離最短的簇心所在類;

3)更新簇心:對每簇中的所有樣本簽到時間求平均,以該平均作為該類的簇心;計算最小化公式的值;

4)看簇心和最小化函數值是否變化;若不變,則輸出聚類結果;若改變則返回2).

圖 2 展示了當聚簇個數k=8本文數據集的聚類結果,圖 3和圖 4展示了不同簇在相同簽到興趣點的頻數差異,圖2(a)～圖2(h)中橫坐標為簽到興趣點(隨機選取和簽到頻數最高前14個),縱坐標為用戶在該地點的簽到頻數.從圖2中可以看出在不同時間點為簇中心點的用戶簽到數據有明顯差異,也證實了時間因子對用戶選擇興趣點確實存在影響.

3.1.2 基于隱語義推薦(LFM)的推薦算法

推薦系統使用用戶的已有行為數據預測用戶可能行為或偏好行為,但現存推薦系統往往面臨數據稀疏性和冷啟動問題.使用隱語義模型能夠某種程度的緩解協同過濾面臨的問題,同時也為解決數據稀疏性和冷啟動問題提供了一種新的思路[13].隱語義模型LFM和LSI,LDA,TopicModel都屬于隱語義分析技術,他們的本質是找出待評價項目中潛在的主題或分類,這些主題或分類被理解為用戶的興趣屬性.隱語義技術首先在文本挖掘領域提出,近年來被不斷應用到其他領域,取得了顯著的效果.

圖2 類簇個數k=8時聚類結果圖(圖(a)(b)(c)(d)(e)(f)(g)(h)中縱坐標為用戶簽到點(興趣點),縱坐標為簽到頻數)Fig.2 Clustering result graph with k=8

本文首先對用戶簽到數據進行建模,如公式(2)所示.

(2)

R矩陣就是user-item矩陣,矩陣值i∈(1,m)、j∈(1,n)表示的是第i個用戶對第j個項目的興趣度,通常可以通過顯式獲取和隱式獲取兩種方式得到用戶偏好數據,顯式獲取需要用戶對所有項目評分,隱式獲取則使用用戶的已存在行為數據來分析用戶偏好.隱式獲取不會用戶產生干擾,并且能夠尊重用戶隱私.基于用戶的簽到信息只能獲得用戶的興趣點和簽到次數,顯然本文只能采取隱式獲取的方法,以用戶在對應興趣點的簽到次數作為用戶對該點的評分,如公式(3)所示.

(3)

其中sum(ui,pj)代表用戶ui在點pj處的簽到次數,若用戶ui在點pj處無簽到記錄,則設評分為0.得到評分矩陣以后,LFM隱語義模型需要將Rmxn矩陣表示為兩個矩陣P和Q的乘積,如公式(4)、公式(5)所示.

圖3 簽到頻數對比圖a(隨機選取20個興趣點)Fig.3 Check-in frequency contrast graph a (Random selection of 20 check-in point)

(4)

(5)

其中P矩陣為user-class矩陣,矩陣值pi,j為user i對class j的興趣度;Q矩陣為class-item矩陣,矩陣值qi,j為item i在class j中的權重;因此LFM根據式(6)計算用戶U對物品I的興趣度.

(6)

圖4 簽到頻數對比圖b(簽到頻數最高的14個點)Fig.4 Check-in frequency contrast graph b (14 points with the highest check-in frequency)

首先隨機給定P矩陣和Q矩陣的初始值,然后通過隨機梯度下降算法最小化損失函數使P·Q的值逼近R,損失函數如公式(7)所示.

(7)

損失函數右邊部分的λ(‖Pi‖2+‖Qj‖2)項是L2正則化項,可以降低過擬合問題導致分解后的矩陣元素太大.

對上式通過求參數Pi和Qj的偏導確定最快的下降方向,如公式(8)、公式(9)所示.

(8)

(9)

通過迭代計算不斷優化參數,直到參數收斂.迭代公式如公式(10)、公式(11)所示.

(10)

(11)

3.1.3 評分預測

綜合3.1.1,3.1.2節提出的步驟,得到組內成員評分預測算法流程如算法1所示.

算法1.個人推薦算法

輸入:matrix,用戶-興趣點簽到矩陣;

G,待推薦用戶集合;

N,計劃推薦項目數;

Tcur,當前時間；

輸出:每個組用戶的個人推薦列表L={l1,l2,…,lm}.

1.foreach user uiin G

2.利用k-means算法聚類出用戶在各個時間點簽到類簇集合{u1t1,u1t2,…,u1tn},{u2t1,u2t2,…,u2tn},…,{umt1,umt2,…,umtn}

3.得到ti,其中ti∈(t1,t2,…,tn)且有|ti-Tcur| = min{|tj-Tcur|,tj∈(t1,t2,…,tn)};令類簇集合{u1ti,u2ti,…,umti}為當前推薦集合

4.整理集合,生成user-item矩陣

5.利用隱語義模型生成P,Q矩陣

8.對Ui進行升序排序,選取得分最高的前N個項目推薦給用戶

3.2 偏好融合策略

在生成群組個人推薦列表后,接下來需要選取合適的融合策略.為了盡可能的滿足群組用戶的滿意度,以及對各個組員的公平性,推薦結果的可解釋性,在實際中對于不同的組推薦系統需要根據實際情況選擇融合策略.

融合策略多種多樣,每種融合策略都盡可能的想要實現融合的平衡和滿意.但現有融合策略均存在一定的優缺點和適用局限性,例如均值策略可能會引起部分群組成員的痛苦問題,最小痛苦策略可能會受到惡意評分的影響.表1對幾種組推薦融合策略進行了說明.

表1 常用融合策略
Table 1 Aggregation strategy in common use

名 稱解 釋公平策略每次推薦輪流選取群組成員的評分作為群組評分均值策略計算所有群組成員評分的算術平均值作為群組評分痛苦避免策略選擇痛苦閾值α,以高于痛苦閾值成員評分平均值作為群組評分最受尊敬者策略從群組成員中選擇某個用戶,將其評分作為群組評分最小痛苦策略選擇所有群組成員中最低評分作為群組評分

考慮到群組中不同組成員簽到次數的非均衡性或者用戶的活躍度問題,也即少量用戶擁有大量簽到記錄,而大量用戶只有少量簽到記錄.顯然簽到次數越多的用戶對群組偏好影響越大,因此本文采用加權混合融合策略對群組偏好進行融合,并采用以下模型計算用戶權重,如式(12)所示.

(12)

其中G代表群組,I代表所有群組簽到興趣點集合,其中s(ui,pj)計算方法如式(13)所示.

(13)

采用加權混合融合策略,組推薦流程如算法(2)所示.

算法2.組推薦算法

輸入:L={l1,l2,…,lm},群組成員個人推薦列表

G,組用戶集合;

輸出:組推薦結果.

1.foreach user uiin G

2. calculate weight w(ui)

3.endfor

4.foreach pain L

5.for(i in G)

6. GR[j] +=w(ui)·rat(ui,pa) //rat(ui,pa)計算見公式(3)

7.endfor

8.endfor

9.sort the GR[j] in descending order;

10.make the GR[0] as recommendation result

11.end

4 實 驗

4.1 數據集

本文采用的數據集采集于斯坦福大學Gowalla網站,Gowalla網站是近年來非常熱門的一個check-in簽到網站,大量有關geo-tag和location-based的應用研究都可以在該數據集上開展.該數據集包含6442890個簽到記錄,數據集樣本包含了興趣點推薦所需要的全部信息.本文在實驗前對數據進行整理,過濾掉了簽到頻數過低的用戶.

4.2 算法評價標準

本文采用F值(準確率和召回率調和平均)為指標評價個人推薦列表.對任意用戶u,Ru為算法推薦地點集合,Tu為測試集中用戶u簽到點集合,推薦準確率P、召回率R、以及F值公式分別如式(14),式(15),式(16)所示.

(14)

(15)

(16)

RMSE(平方根誤差)把預測評分與真實評分之間的誤差作為評價推薦系統的標準.本文對RMSE進行改進,使用改進后的公式對組推薦結果進行評價,如式(17)所示.

(17)

r(ui,pa)為用戶ui對點pa的打分,r(G,pa)為組G對點pa的打分,|G|為組成員個數.

4.3 實驗結果

4.3.1 隱語義模型K值比較

隱語義模型的分類數K的值代表對興趣點的分類粒度,分類數越大則粒度越細,而分類數越小則粒度越粗.本文實驗通過設置不同的K值對推薦結果進行評價,實驗結果如圖 5 所示.從圖中可以看出當K=15,選取前20個推薦結果作為最終推薦結果時,獲得了最高的F值,推薦效果較好.

圖5 不同K值對個人推薦準確率的影響Fig.5 Precision of different values of K

4.3.2 加權混合融合策略和其他融合策略的比較

為了驗證AGRT算法的有效性,本文通過實驗,將本文提出的算法與幾種現存算法就融合策略進行了比較,實驗結果如圖 6 所示.從實驗中可以看出,AGRT算法較其他目前常用的幾種算法有較明顯的改進,并且AGRT在低相似度群組中的表現優于高相似度的改進.其中,該系統在低相似度(隨機)群組和高相似度群組評測條件下下較HAaB提高了5.19%和2.06%.

圖6 不同融合策略實驗數據對比Fig.6 Results comparison on aggregation strategies

5 總結與展望

本文提出了一種K-means時間因子聚類和隱語義模型相結合的群組興趣點推薦算法,在實驗數據集上取得了較傳統協同過濾推薦策略和融合方法相結合的組推薦系統較為理想的推薦效果.但由于本文所采用的數據集的局限性,不能保證算法的普適性.本文下一步的工作是在更為廣泛的數據集上進行實驗和改善算法,希望能夠取得更為完善和普適的算法.