一種結(jié)合時(shí)間因子聚類的群組興趣點(diǎn)推薦模型

陶永才,曹朝陽,石 磊,衛(wèi) 琳

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

1 引 言

近年來,由于個(gè)人電腦和網(wǎng)絡(luò)的普及,大量用戶和用戶信息涌入互聯(lián)網(wǎng).在用戶向互聯(lián)網(wǎng)不斷提供信息、文件、多媒體資源的同時(shí),也在不斷的從互聯(lián)網(wǎng)中查詢和獲得各種需要的信息和資源.因此推薦系統(tǒng)伴隨各種應(yīng)用快速發(fā)展.

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

現(xiàn)存經(jīng)典推薦系統(tǒng)通常傾向于為單個(gè)用戶進(jìn)行推薦.而隨著移動(dòng)設(shè)備的普及和各種社交網(wǎng)絡(luò)的app的出現(xiàn),傳統(tǒng)的線下集體活動(dòng)開始逐漸轉(zhuǎn)變?yōu)橐跃W(wǎng)絡(luò)為媒體的線上群組活動(dòng),如去餐廳就餐,度假旅游,家庭娛樂視頻等.因此,推薦系統(tǒng)需要以群組為單位,綜合考慮群組中用戶權(quán)重與偏好,生成群組推薦.由此組推薦系統(tǒng)(group recommender system)產(chǎn)生.

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

2 相關(guān)工作

目前主流的組推薦系統(tǒng)推薦策略通常使用協(xié)同過濾推薦(collaborative filtering,簡(jiǎn)稱CF)向組用戶產(chǎn)生推薦.這些策略通?？梢苑譃閮深?基于內(nèi)存的協(xié)同過濾推薦(memory-based CF)和基于模型的協(xié)同過濾推薦(model-based CF).其中,基于內(nèi)存的協(xié)同過濾推薦按照融合策略的不同又分為基于個(gè)人模型的融合策略(aggregating individual model,AIM)和基于個(gè)人預(yù)測(cè)融合策略(aggregating individual prediction,AIP).基于個(gè)人模型的融合策略首先融合群組成員的偏好為組偏好然后利用傳統(tǒng)個(gè)人推薦算法進(jìn)行推薦;而基于個(gè)人預(yù)測(cè)的融合策略首先為每個(gè)群組成員生成個(gè)人推薦,然后融合這些個(gè)人推薦列表生成組推薦[1].

Wang,Liu等人梳理了傳統(tǒng)個(gè)性化推薦系統(tǒng)的概念以及傳統(tǒng)推薦系統(tǒng)的各個(gè)模塊以及各個(gè)模塊常用的建模方法,傳統(tǒng)推薦算法種類以及推薦系統(tǒng)評(píng)價(jià)標(biāo)準(zhǔn)[12].Zhang,Du等人引入了組推薦系統(tǒng)的概念,詳細(xì)比較了組推薦系統(tǒng)與傳統(tǒng)推薦系統(tǒng)的不同,并介紹了組推薦系統(tǒng)的各個(gè)環(huán)節(jié)所用的技術(shù),偏好融合策略、群組特征對(duì)偏好融合策略的影響以及組推薦系統(tǒng)評(píng)價(jià)標(biāo)準(zhǔn)[14].文獻(xiàn)[2]基于組用戶易受群組中專家成員意見影響的趨向提出了一種基于注意力機(jī)制的組推薦模型(AGR),利用該模型學(xué)習(xí)群組中專家成員對(duì)其他成員影響并能夠針對(duì)不同的領(lǐng)域推薦調(diào)整模型.

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

3 結(jié)合時(shí)間因子的群組興趣點(diǎn)推薦模型

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

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

①獲取數(shù)據(jù),對(duì)用戶數(shù)據(jù)集用K-means算法進(jìn)行聚類；

②根據(jù)當(dāng)前時(shí)間整理出群組成員User-item矩陣,用LFM隱語義模型生成組成員個(gè)人推薦列表；

③根據(jù)群組分歧度和群組成員權(quán)重,選用合適的加權(quán)算法,生成組推薦列表,將組推薦列表的首個(gè)推薦推薦給該群組.

3.1 個(gè)人推薦列表

3.1.1 K-means算法

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

(1)

在本文中,對(duì)用戶數(shù)據(jù)集使用K-Means算法,步驟如下:

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

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

2)計(jì)算每個(gè)樣本點(diǎn)與簇心之間的距離,將其劃分到距離最短的簇心所在類;

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

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

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

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

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

圖2 類簇個(gè)數(shù)k=8時(shí)聚類結(jié)果圖(圖(a)(b)(c)(d)(e)(f)(g)(h)中縱坐標(biāo)為用戶簽到點(diǎn)(興趣點(diǎn)),縱坐標(biāo)為簽到頻數(shù))Fig.2 Clustering result graph with k=8

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

(2)

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

(3)

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

圖3 簽到頻數(shù)對(duì)比圖a(隨機(jī)選取20個(gè)興趣點(diǎn))Fig.3 Check-in frequency contrast graph a (Random selection of 20 check-in point)

(4)

(5)

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

(6)

圖4 簽到頻數(shù)對(duì)比圖b(簽到頻數(shù)最高的14個(gè)點(diǎn))Fig.4 Check-in frequency contrast graph b (14 points with the highest check-in frequency)

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

(7)

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

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

(8)

(9)

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

(10)

(11)

3.1.3 評(píng)分預(yù)測(cè)

綜合3.1.1,3.1.2節(jié)提出的步驟,得到組內(nèi)成員評(píng)分預(yù)測(cè)算法流程如算法1所示.

算法1.個(gè)人推薦算法

輸入:matrix,用戶-興趣點(diǎn)簽到矩陣;

G,待推薦用戶集合;

N,計(jì)劃推薦項(xiàng)目數(shù);

Tcur,當(dāng)前時(shí)間；

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

1.foreach user uiin G

2.利用k-means算法聚類出用戶在各個(gè)時(shí)間點(diǎn)簽到類簇集合{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}為當(dāng)前推薦集合

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

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

8.對(duì)Ui進(jìn)行升序排序,選取得分最高的前N個(gè)項(xiàng)目推薦給用戶

3.2 偏好融合策略

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

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

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

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

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

(12)

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

(13)

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

算法2.組推薦算法

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

G,組用戶集合;

輸出:組推薦結(jié)果.

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)計(jì)算見公式(3)

7.endfor

8.endfor

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

10.make the GR[0] as recommendation result

11.end

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

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

本文采用的數(shù)據(jù)集采集于斯坦福大學(xué)Gowalla網(wǎng)站,Gowalla網(wǎng)站是近年來非常熱門的一個(gè)check-in簽到網(wǎng)站,大量有關(guān)geo-tag和location-based的應(yīng)用研究都可以在該數(shù)據(jù)集上開展.該數(shù)據(jù)集包含6442890個(gè)簽到記錄,數(shù)據(jù)集樣本包含了興趣點(diǎn)推薦所需要的全部信息.本文在實(shí)驗(yàn)前對(duì)數(shù)據(jù)進(jìn)行整理,過濾掉了簽到頻數(shù)過低的用戶.

4.2 算法評(píng)價(jià)標(biāo)準(zhǔn)

本文采用F值(準(zhǔn)確率和召回率調(diào)和平均)為指標(biāo)評(píng)價(jià)個(gè)人推薦列表.對(duì)任意用戶u,Ru為算法推薦地點(diǎn)集合,Tu為測(cè)試集中用戶u簽到點(diǎn)集合,推薦準(zhǔn)確率P、召回率R、以及F值公式分別如式(14),式(15),式(16)所示.

(14)

(15)

(16)

RMSE(平方根誤差)把預(yù)測(cè)評(píng)分與真實(shí)評(píng)分之間的誤差作為評(píng)價(jià)推薦系統(tǒng)的標(biāo)準(zhǔn).本文對(duì)RMSE進(jìn)行改進(jìn),使用改進(jìn)后的公式對(duì)組推薦結(jié)果進(jìn)行評(píng)價(jià),如式(17)所示.

(17)

r(ui,pa)為用戶ui對(duì)點(diǎn)pa的打分,r(G,pa)為組G對(duì)點(diǎn)pa的打分,|G|為組成員個(gè)數(shù).

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

4.3.1 隱語義模型K值比較

隱語義模型的分類數(shù)K的值代表對(duì)興趣點(diǎn)的分類粒度,分類數(shù)越大則粒度越細(xì),而分類數(shù)越小則粒度越粗.本文實(shí)驗(yàn)通過設(shè)置不同的K值對(duì)推薦結(jié)果進(jìn)行評(píng)價(jià),實(shí)驗(yàn)結(jié)果如圖 5 所示.從圖中可以看出當(dāng)K=15,選取前20個(gè)推薦結(jié)果作為最終推薦結(jié)果時(shí),獲得了最高的F值,推薦效果較好.

圖5 不同K值對(duì)個(gè)人推薦準(zhǔn)確率的影響Fig.5 Precision of different values of K

4.3.2 加權(quán)混合融合策略和其他融合策略的比較

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

圖6 不同融合策略實(shí)驗(yàn)數(shù)據(jù)對(duì)比Fig.6 Results comparison on aggregation strategies

5 總結(jié)與展望

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