基于密度峰值聚類的動態(tài)群組發(fā)現(xiàn)方法

王海艷肖亦康

1(南京郵電大學計算機學院 南京 210023)2(江蘇省無線傳感網(wǎng)高技術研究重點實驗室 南京 210003)3(江蘇省大數(shù)據(jù)安全與智能處理重點實驗室 南京 210023)(wanghy@njupt.edu.cn)

隨著互聯(lián)網(wǎng)技術的飛速發(fā)展，網(wǎng)絡上的服務數(shù)量也隨之急劇增長.然而，這種增長遠遠超過個人或系統(tǒng)所能接受、處理和有效利用的范疇.在這種環(huán)境下，能夠針對不同用戶需求的推薦系統(tǒng)應運而生，推薦理論及其相關技術已成為學術界和工業(yè)界的一個熱門研究課題.

傳統(tǒng)的服務推薦系統(tǒng)如協(xié)同過濾技術普遍側重于向單個用戶進行推薦，但在現(xiàn)實生活的許多日常活動中，用戶是以群組形式出現(xiàn)的，例如出行旅游、網(wǎng)上團購等[1].因此，群組推薦系統(tǒng)需要同時考慮所有用戶的傾向來進行推薦.另一方面，針對某單一用戶進行推薦容易產(chǎn)生效果不理想的情況，而需要將其放入到群組中，通過群組推薦往往能獲得良好效果，并能有效緩解新用戶引起的冷啟動問題.目前面向群組的推薦系統(tǒng)研究受到越來越多的關注，2011年ACM推薦系統(tǒng)大會(RecSys2011)以“為家庭群組推薦電影”為主題，舉辦了上下文感知電影推薦挑戰(zhàn)賽(CAMRa2011)，促進了群組推薦在電影、餐飲、旅游等領域的推廣與應用[2-3].群組發(fā)現(xiàn)作為群組推薦的前提步驟，其群組劃分結果對推薦效果起重要作用.群組的內(nèi)在相似度決定了群組推薦的精確度，高相似度群組的推薦效果能夠達到甚至超過單個用戶推薦的精度，且在群組規(guī)模增大時也具有良好的穩(wěn)定性[4].

現(xiàn)有群組發(fā)現(xiàn)方法往往只考慮用戶與項目間的二元關系[5]，而較少關注時間因素的影響，這類方法在實際應用中是不合理的，因為用戶的選擇傾向會隨著時間的推移而發(fā)生變化，具有時間遷移性.時間上下文對推薦的影響主要有以下2點：1)項目的流行程度會隨著時間推移而改變；2)用戶對項目的傾向可能會隨時間變化而改變[6].例如，考慮學術研究這一應用場景，由于每年都會舉辦大量的國際、國內(nèi)學術會議，誕生大量的學術論文和在相應研究領域的突破性研究成果，隨著科技的發(fā)展，每年的研究熱點會發(fā)生變化，學者們的研究傾向也會隨之變化，這是極具時效性的.因此在進行學術熱點或相關成果推薦時把時間考慮在內(nèi)是很有必要的.

通過對現(xiàn)有相關工作進行調(diào)研與分析，已有的群組發(fā)現(xiàn)方法主要存在以下2個問題：

1) 大部分群組發(fā)現(xiàn)方法都假設用戶傾向是靜態(tài)的，忽視了時間因素帶來的傾向遷移性問題，往往導致實際計算出的用戶間相似度值精確度較低.

2) 聚類算法在群組發(fā)現(xiàn)中是一個典型應用，但大部分聚類算法將每一處理對象劃分到互斥的數(shù)據(jù)集中，即簇之間無交集，這并不符合實際情況中同一個用戶可以分屬于不同群組的事實.另外該類分配方法還會導致處在相鄰群組邊界區(qū)的用戶只能得到一個群組的推薦結果，影響這類用戶的推薦結果精度.

針對以上存在問題，本文提出了一個解決方案，主要工作如下：

1) 提出一種用戶動態(tài)傾向的計算方法.考慮到用戶傾向隨時間的遷移性，首先通過動態(tài)泊松分解得到已有觀察值的用戶傾向，再利用張量分解對高維數(shù)據(jù)的處理能力，預測出不同時間節(jié)點不同項目下用戶的傾向.

2) 提出一種基于密度峰值聚類算法的群組發(fā)現(xiàn)方法.利用用戶選擇傾向計算的結果構建高相似度用戶集合，然后對原有的密度峰值聚類算法進行修改并實現(xiàn)用戶群組劃分，新的群組劃分方法能夠滿足同一個用戶可以隸屬于多個群組的需求.

1 相關工作

1.1 用戶傾向獲取

大多數(shù)傳統(tǒng)的推薦系統(tǒng)中，系統(tǒng)根據(jù)用戶已有的評分數(shù)據(jù)或隱式信息量化用戶傾向，但是用戶傾向會隨著時間的推移而改變，因此在量化用戶間傾向時應該考慮已知的評分數(shù)據(jù)或隱式信息與時間因素的關系.

Gang等人[6]利用用戶隱式反饋信息，結合時間上下文進行推薦，指出時間上下文在項目流行程度、用戶偏好和用戶打分習慣3個方面影響著推薦結果.Victor等人[7]基于準二元組理論，利用上下文環(huán)境中用戶行為來表現(xiàn)用戶對不同項目的傾向，能夠?qū)⑾嗤挠脩魟澐诌M不同的群組，但無法保證用戶群組的內(nèi)在相似度.Yi等人[8]結合互聯(lián)網(wǎng)中項目的顯式評分和用戶點擊提取用戶偏好，構建了一個個性化推薦系統(tǒng).但該系統(tǒng)采用的歷史記錄是靜態(tài)的，無法準確表現(xiàn)用戶的動態(tài)傾向.Laurent等人[9]在泊松分解的基礎上提出了動態(tài)泊松分解，能夠同時考慮時間因素對用戶選擇傾向和項目流行度的影響，緩解了傳統(tǒng)推薦系統(tǒng)處理用戶傾向的靜態(tài)局限性.

1.2 群組發(fā)現(xiàn)

由于大多數(shù)數(shù)據(jù)集可能不包含用戶的群體信息，人們提出了不同的群組發(fā)現(xiàn)方法對群體進行劃分，目前群組推薦系統(tǒng)中的群組發(fā)現(xiàn)主要是根據(jù)用戶的傾向和人口統(tǒng)計學信息等特征對用戶進行聚類.最基本的想法是將選擇傾向相似的用戶構成群組，因為群組中用戶內(nèi)在相似度越高越容易生成高質(zhì)量的群組推薦.

Linas等人[4]對比分析了群組推薦與個人推薦，實驗結果顯示相似度高的群組推薦精度能達到甚至會超過個人推薦的精度，且在群組規(guī)模增大時依然能保持良好的穩(wěn)定性.Jing等人[10]基于用戶會受到某些潛在因素的影響的假設，提出了潛在群組模型，該方法將用戶的潛在因素偏好聚合為群體傾向從而進行群體推薦.Boratto等人[11]直接把用戶-項目評分矩陣作為K-means算法的輸入，根據(jù)用戶傾向?qū)⒂脩艟垲愋纬扇航M，但此聚類方法導致用戶只能屬于一個群組.Ntoutsi等人[2]提出一種聚類算法，初始時每個群組中只有一個用戶，然后比較每個用戶群組的內(nèi)在相似度.當偏好最相似的2個群組的相似度超過給定閾值時將2個群組合并，最終相似度超過閾值的用戶都被劃為同一個群組.Seko等人[12]提出基于內(nèi)容的群體推薦方法，該方法假設群體的選擇受物品種類影響的假設，但這種方法只能應用于預定義的群體.

1.3 密度峰值聚類算法

密度峰值聚類算法由Rodriguez等人[13]提出，由于其良好的適應能力和極高的運行效率而備受關注.近年來，不少學者也將該算法應用到了多個領域.

馮國香[14]在復雜社區(qū)網(wǎng)絡的研究中應用了該算法，并對其進行改進，克服了鄰近矩陣為整數(shù)的缺點且實現(xiàn)了重疊社區(qū)網(wǎng)絡的劃分.Chen等人[15]利用密度峰值聚類算法提出了一種根據(jù)圖像估算人年齡的方法，在大規(guī)模圖像數(shù)據(jù)集試驗中取得了良好的效果.Liu等人[16]將該算法應用到了城市出租車運營領域，提出一種變體密度峰值聚類算法用于發(fā)現(xiàn)城市出租車的需求熱點，且時間與內(nèi)存消耗都很低.Mykola等人[17]針對模式識別中數(shù)據(jù)的復雜異構型問題，提出了局部密度以及流式距離測量方法，可以更精確地捕捉局部和全局流式信息.

2 群組發(fā)現(xiàn)方法

群組發(fā)現(xiàn)的核心思想是讓相似度高的用戶聚集成群組，本文圍繞這一核心思想展開工作.考慮到用戶傾向的時間遷移性，本文采用動態(tài)泊松分解的方法獲取用戶的動態(tài)傾向量化值.為計算用戶間相似系數(shù)，其中的缺省值通過張量分解預測得到，最后構造高相似度用戶集合，通過對已有的聚類算法進行改進，最終得到用戶群組.

2.1 用戶動態(tài)傾向提取

用戶對項目的選擇傾向隨著時間的變化而變化，正如引言中給出的推薦學術研究熱點問題，僅考慮用戶的歷史記錄這一全局靜態(tài)因素是不可取的.例如，學者A與B在某一時間段內(nèi)對某研究領域的論文點擊量相近，但學者A的點擊量呈逐漸增加趨勢，B則相反，也就是說學者A與B對該研究領域的關注傾向是相反的，具有較低的相似度.然而，如果靜態(tài)地考慮A與B在時間段內(nèi)的歷史數(shù)據(jù)，則會得到兩者是具有較高相似度的用戶這一截然相反的結果.

定義1. 泊松分解[18].泊松分解本質(zhì)上屬于產(chǎn)生式概率模型，它假設每個觀測元素fn m服從期望為yn m的泊松分布：fn m～Poisson(yn m).期望值矩陣Y∈N×M被分解為用戶隱藏特征矩陣U∈N×K和項目隱藏特征矩陣V∈M×K，且隱藏特征矩陣的每個元素un k和vm k服從Gamma分布，其中K?min(M,N)是隱藏特征向量的維數(shù)，并使用用戶隱藏特征矩陣U和項目隱藏特征矩陣V的內(nèi)積來近似期望值矩陣Y：Y～UVT.

為了獲取用戶的動態(tài)傾向，本文采用文獻[9]提出的動態(tài)泊松分解方法.該方法是在泊松分解這一靜態(tài)方法上的改進，優(yōu)勢在于能夠利用顯式的評分或隱式信息高效地發(fā)現(xiàn)用戶的傾向序列，并同時考慮用戶傾向和項目流行度，有效緩解了時間因素對推薦結果的影響.

首先，用狀態(tài)空間模型作為泊松分解的動態(tài)部分，狀態(tài)空間模型表示基于前一個時間節(jié)點的當前狀態(tài)的高斯分布情況，un k,t表示第n個用戶在時間節(jié)點t的第k個元素，vm k,t表示第m個項目在時間節(jié)點t的第k個元素，其分布表達式為

(1)

然后，通過以下遞推表達式獲得時間節(jié)點t下用戶和項目的相關系數(shù)：

(2)

最后，時間節(jié)點t下用戶n對項目m選擇傾向的泊松分布如下：

(3)

動態(tài)泊松分解同時考慮不同時間節(jié)點下的用戶反饋信息及項目流行度，它將兩者有機融合，本文將動態(tài)泊松分布加權平均的結果作為該時間節(jié)點下用戶對項目選擇傾向的量化值，計算方法如下：

(4)

2.2 用戶傾向值分解

在計算用戶相似度時，由于本文引入了時間因素，不同時間節(jié)點下不同用戶間的傾向值會出現(xiàn)缺省，無法計算，因此，在計算相似度之前需要先用張量分解預測補全每個用戶的傾向值.

定義2. 張量分解[19].張量分解是對矩陣分解的N維拓展，它將N階張量分解為一個核心張量和N個因子矩陣的乘積：X≈C×1U1×2U2×3…×NUN，其中Ui∈I×T，1≤i≤N，核心張量S∈T×T×…×T，因子矩陣是每一維上的主要成分.

張量分解主要以下3點優(yōu)勢：1)不需要預過濾和后過濾.不同于許多現(xiàn)有的依靠拆分、預過濾和后過濾的算法，張量分解利用所有已知的評分將用戶和項目建模，而拆分、預過濾以及后過濾上下文會導致不同上下文設定間的信息丟失.2)簡化計算.許多現(xiàn)有的方法采用一系列代價巨大的技術，而張量分解是一個單一的簡化計算的模型.3)解決N維數(shù)據(jù)的能力.張量分解方法對于任意數(shù)量的上下文變量都具有通用的處理能力.

高階奇異值分解(high order singular value de-composition, HOSVD)屬于張量分解模型，它包含密度矩陣D，能緩解引入時間因素后造成的嚴重的數(shù)據(jù)稀疏性問題，因此本文采用該方法進行張量分解，將用戶-項目-時間3維張量分解為3個維度上的因子矩陣以及1個核心張量.

3維張量被分解為3個矩陣：U∈n×d，I∈m×d，C∈c×d，以及核心張量S∈d×d×d.針對單個用戶u，項目i和上下文c的決策函數(shù)為

Fi jk=S×UUi*×IIj*×CCk*.

(5)

這個分解模型能夠通過調(diào)整參數(shù)dU，dI，dC分別控制用戶、項目和時間的維度.這個特性對于現(xiàn)實中大規(guī)模數(shù)據(jù)集的處理很有利，因為矩陣U和M的規(guī)?？赡軙龃髱頋撛诖鎯栴}.

損失函數(shù)定義為

(6)

其中l(wèi):×y→是一個點態(tài)損失函數(shù)，懲罰估算值和真實值，F(xiàn)i jk已由式(5)給出.需要注意的是，全局損失函數(shù)L由張量Y中的真實值定義.

最終得到的目標函數(shù)如下：

R[U,I,C,S]=L(F′,Y)+Ω[Y,I,C]+Ω[S],

(7)

其中加入了Frobenius范數(shù)Ω[U,I,C]，因為單純的最小化上述損失函數(shù)會導致過擬合現(xiàn)象，Ω[S]是作用于核心張量S的范數(shù)，其目的是降低核心張量復雜度.

時間上下文張量分解的用戶傾向預測算法如下所示：

算法1. 用戶傾向張量分解預測算法.

輸入：原用戶傾向值張量Y、維度d；

輸出：用戶傾向值張量F.

初始化：U←n×d，I←m×d，C←c×d，S∈d×d×d，t=t0;

遍歷：for (i,j,k) inY

Fi jk=S×UUi*×IIj*×CCk*;

Ui*=Ui*-ηλUYi*-η?Ui*l(Fi jk,Yi jk);

Ij*=Ij*-ηλIIj*-η?Mj*l(Fi jk,Yi jk);

Ck*=Ck*-ηλCCk*-η?Ck*l(Fi jk,Yi jk);

S=S-ηλSS-η?Sl(Fi jk,Yi jk);

end for

最小化：F←R[U,I,C,S]=L(F′,Y)+Ω[U,I,C]+Ω[S].

算法1輸入為包含原用戶傾向值的3維張量Y，以及維度d.將原張量初始化分解為U,I,C這3個矩陣，通過迭代得到近似張量F′，最小化目標函數(shù)得到最終的包含預測傾向值得張量F.其算法復雜度為O(KdUdIdC)，與已知的傾向值數(shù)量和維度線性相關.

2.3 基于密度峰值聚類算法的群組發(fā)現(xiàn)

鑒于密度峰值聚類算法能夠適用于各種形狀的聚類并能自動發(fā)現(xiàn)聚類個數(shù)，且適應能力和運行效率極高，有利于解決用戶群組劃分中用戶分布情況和群組個數(shù)未知的問題，因此本節(jié)借鑒密度峰值聚類算法[13]的思想對用戶群組進行劃分，提出了一種基于密度峰值聚類的動態(tài)群組發(fā)現(xiàn)方法(dynamic group discovery method based on density peaks clustering, DGD-BDPC).

2.3.1 密度峰值聚類算法

密度峰值聚類算法[13]的基本思想如下：假設類簇中心周圍節(jié)點的局部密度一般低于該類簇中心的局部密度，并且與具有更高密度的節(jié)點的距離都較大.首先計算每一個數(shù)據(jù)節(jié)點i局部密度ρi和該點到更高局部密度的節(jié)點的最短距離δi；然后根據(jù)這2個值畫出決策圖，在決策圖里面找到類簇中心；最后根據(jù)每一個節(jié)點的最近更高局部密度節(jié)點的類別確定其所屬類簇中心.由于該算法對于多種類型的數(shù)據(jù)顯示出了良好的適應能力和極高的運行效率，所以本文將其引入到用戶群組的劃分中.

該算法需要解決2個問題：1)需要計算不同節(jié)點之間的距離，本文將用戶傾向相似度系數(shù)作為節(jié)點間的距離；2)聚類算法只能解決標準的群組劃分結果，它將剩余的待劃分節(jié)點都劃分到最近更高局部密度節(jié)點所在的類簇中，因此無法處理包含重疊節(jié)點的群組劃分問題.本文通過定義群組貢獻的適應度函數(shù)方法來判斷剩余節(jié)點是否應該劃分進該群組.

2.3.2 用戶節(jié)點距離矩陣

密度峰值聚類算法需要用到不同節(jié)點之間的距離，即距離矩陣，由第2.2節(jié)可計算得到包含用戶傾向的張量F，然后通過皮爾遜相似度計算公式計算得到用戶間相似度并作為節(jié)點之間的距離，在此不再贅述.根據(jù)Linas等人[4]的實驗結論，相似度高于0.27的用戶即為高相似度用戶.所以本文將用戶間相似度低于0.27的系數(shù)直接設為0，表示用戶間沒有連接，這樣保證了在下一步聚類操作中得到的群體必然為具有高相似度的用戶群體.與實際距離相反，用戶間相似度值越大距離越小，反之越大.設矩陣A為已知的連接矩陣，如表1所示：

Table 1 Users Distance Matrix表1 用戶距離矩陣

其中Ai j表示節(jié)點i與j之間的距離，不同于一般的網(wǎng)絡結構，用戶間不存在間接距離，因此簡化了距離計算.

2.3.3 重疊用戶群組發(fā)現(xiàn)

得到用戶距離矩陣后，基于密度峰值聚類算法，本文修改了其處理方法以實現(xiàn)重疊用戶群組發(fā)現(xiàn).用戶群組發(fā)現(xiàn)過程具體步驟如下：

1) 計算所有節(jié)點的局部密度和與該點更高局部密度最近的距離.這2個值通過2.3.2節(jié)得到的用戶距離矩陣計算得出，修改的局部密度ρ計算公式如下：

(8)

其中，若x<0則X(x)=1，否則X(x)=0，dc是一個截斷距離，一般來說，可以選擇dc使得節(jié)點的平均鄰居數(shù)大概是數(shù)據(jù)集中節(jié)點總數(shù)的1%～2%.基本上，節(jié)點i的密度ρi等于該點的距離小于截斷距離dc的點的個數(shù).密度峰值聚類算法對于節(jié)點密度大小相對比較敏感，而對于大數(shù)據(jù)集，其對于dc的取值都具有很好的魯棒性.

用戶節(jié)點i到更高局部密度用戶的距離δi是到任何比其密度大的節(jié)點的最小值，計算公式如下：

(9)

2) 畫出相應的決策圖.將δ且ρ異常大的用戶節(jié)點作為群組中心.

圖1為決策圖的示例.圖1中圓圈代表用戶節(jié)點，不同顏色表示各個不同的群組.其中節(jié)點1和10同時具有異常大的δ和ρ，因此分別作為群組的中心節(jié)點.

3) 劃分重疊區(qū).為了得到群組間重疊的用戶節(jié)點，不能再按原算法中的方法進行劃分.找到每個群組的邊界區(qū)域，這個邊界區(qū)域的定義為：分配到某個群組中的節(jié)點，同時與其他群組的節(jié)點距離小于dc的節(jié)點集合.然后針對集合中的每個節(jié)點，本文采用LFM算法中的重疊節(jié)點判定方法[20].LFM算法在可發(fā)現(xiàn)重疊節(jié)點的社區(qū)算法中是精度和效率都非常高的算法，但該算法在處理局部密集較高的簇時效率會下降，本文只采用其重疊節(jié)點的識別方法因此并不會影響群組劃分算法的效率.定義的適應度函數(shù)表示為

(10)

節(jié)點對社區(qū)有沒有貢獻用節(jié)點適應度函數(shù)通過下面的式子反映出來：

(11)

本文修改的基于密度峰值聚類的可重疊的動態(tài)群組發(fā)現(xiàn)算法(DGD-BDPC)如下：

算法2. 基于密度峰值聚類的動態(tài)群組發(fā)現(xiàn)算法.

輸入：用戶距離矩陣U；

輸出：群組集合G.

Step1. for eachuinU

end for

Step2. for eachuinU

end for

for eachucenter

Gi←ucenter;

end for

Step3. for eachuinGi

Uedge←u;

end if

end for

Step4. for eachuinU

G←u;

end if

end for

該算法復雜度為O(u2)，主要的計算耗時集中于每個節(jié)點的密度與距離計算，群組的構建操作只需對用戶進行一次遍歷即可完成復雜度為O(u).

3 實驗仿真及效用評估

3.1 實驗場景

為了檢測本文提出的基于密度峰值聚類算法的群組發(fā)現(xiàn)的效果，采用的測試樣本使用了為提供科學研究成果的交流與共享而建立的arXiv.org真實論文數(shù)據(jù)集，它包含2003—2013年75 000篇學術論文以及5 000個用戶，每篇學術論文至少有20次點擊量.實驗硬件環(huán)境:CPU為酷睿i5處理器2.3 GHz，內(nèi)存8 GB，系統(tǒng)為Ubuntu 14.04 LTS.

3.2 實驗評估

3.2.1 實驗結果評價準則

本文采用nDCG和RMSE這2個參數(shù)來對比衡量不同群組劃分方法得到的群組推薦效果.

(12)

(13)

(14)

3.2.2 推薦效果對比實驗

本實驗以文獻[22]提出的采用K-means群組發(fā)現(xiàn)方法的潛在群體模型(latent group model, LGM)、文獻[7]提出的基于用戶行為的群組發(fā)現(xiàn)方法(online role mining, ORM)、以及隨機用戶群組(Random)作為參照對象與本文所提出的DGD-BDPC方法進行對比.實驗選取了Average，LM(least misery)兩種傳統(tǒng)的融合策略獲得推薦結果.

實驗1. 對比引入時間因素后動態(tài)群組的推薦效果，在保持推薦生成策略相同的條件下對比4種群組發(fā)現(xiàn)方法的推薦效果.本實驗中用Value來表示推薦精度改善百分比，計算方法如下：

(15)

對比無任何優(yōu)化處理的Random方法，表2給出了在不同群組規(guī)模下，LGM，ORM，DGD-BDPC三種群組發(fā)現(xiàn)方法在Average和LM策略下的推薦精度改善百分比．由于Random對比自身的改善值均為0，因此不在表2中顯式列出.從表2中可以看出本文提出的DGD-BDPC方法改善效果始終高于另外2個靜態(tài)方法，且在群組規(guī)模增大時依然具有較好的改善效果.對比Average和LM兩種策略可以發(fā)現(xiàn)，在本文的數(shù)據(jù)集應用場景下，Average策略具有更好的改善效果.

Table 2 Improvement Comparison of Recommendation Effects表2 推薦效果改善對比 %

在Average策略下4種群組發(fā)現(xiàn)方法精度及誤差對比結果如圖2和圖3所示：

Fig. 2 Mean nDCG in Average strategy圖2 Average策略的nDCG

Fig. 3 RMSE in Average strategy圖3 Average策略的RMSE

在LM策略下4種群組發(fā)現(xiàn)方法精度及誤差對比結果如圖4和圖5所示：

Fig. 4 Mean nDCG in LM strategy圖4 LM策略的nDCG

對比圖2和圖4可以看出，在群組規(guī)模較小的情況下4種方法差別不大.隨著群組規(guī)模的增大，隨機群組的精度急劇下降.LGM和ORM方法在群組規(guī)模增大時仍然保持良好的推薦精度，但是ORM由于不能保證群組相似度的缺點，推薦精度在群組規(guī)模相對較大時逐漸劣于LGM方法.本文提出的DGD-BDPC群組發(fā)現(xiàn)方法較LGM和ORM方法具有更好的精確度和誤差率，且在群組規(guī)模增大時也具有良好的穩(wěn)定性.

對比分析圖3和圖5，可以看到隨機化的群組始終存在較高的誤差率.ORM和LGM方法在群組相對較小時誤差率都很低且很接近，但同樣由于無法保證用戶相似度的問題，ORM方法的誤差率逐漸超過了LGM方法.本文提出的群組發(fā)現(xiàn)方法始終保持相對較低的誤差率，且當群組規(guī)模增大時，與其他3種方法對比，DGD-BDPC方法增長趨勢逐漸平穩(wěn).

3.2.3 群組可重疊問題檢測實驗

以現(xiàn)實應用為例，某學者主要研究機器學習算法，但近幾年對服務推薦領域產(chǎn)生興趣，由于該學者往年的學術關注記錄絕大多與機器學習相關，因此傳統(tǒng)的聚類算法在群組劃分時很可能會將其劃分到關注機器學習的學者群組中，因此也無法得到服務推薦領域的學術推薦，該部分用戶即是所謂的群組重疊區(qū)域用戶.

實驗2. 檢測本文提出的群組發(fā)現(xiàn)DGD-BDPC方法對邊界區(qū)用戶的重疊處理的效果.將各個群組間重疊區(qū)域內(nèi)的用戶作為實驗對象，該部分用戶通過3.3.3節(jié)的步驟3獲得，分別對其采用非重疊處理(non-overlapping)和重疊處理(overlapping)兩種方式進行對比最終推薦結果.對于非重疊處理的用戶只采用所在群組的推薦結果直接進行推薦，對于重疊處理的用戶則采用多個群組的推薦結果進行推薦.這2種處理方法的推薦精度結果如圖6所示：

Fig. 6 Comparison between overlapping and non-overlapping圖6 重疊處理對比圖

從圖6可以看出，無論群組規(guī)模大小，處在重疊區(qū)的用戶接受多個群組的推薦結果其nDCG明顯高于只接受單個群組推薦的用戶，充分顯現(xiàn)了本文對用戶群組重疊性問題的處理方法有效改善了推薦效果，更符合現(xiàn)實中用戶可以隸屬多個群組的情況，避免了用戶只能獲得單個群組推薦結果的局限性.

4 總 結

群體推薦在推薦系統(tǒng)中越來越流行，而群組發(fā)現(xiàn)作為群組推薦首要的環(huán)節(jié)起到了至關重要的作用.本文提出了一種考慮用戶傾向動態(tài)性的基于密度峰值聚類的群組發(fā)現(xiàn)方法，通過引入時間因素根據(jù)用戶的歷史數(shù)據(jù)精確量化用戶的傾向，解決了用戶傾向的時間遷移性問題導致的用戶相似度計算誤差.進而采用修改的基于密度峰值聚類的算法劃分得到可互相重疊群組，保證了重疊區(qū)用戶不會只接受單一的群組推薦，提高了該部分用戶的推薦結果精度.

在后續(xù)的研究中，我們將進一步研究群組推薦階段需要進一步考慮的問題，比如：如何解決個人用戶對群組推薦結果的影響、如何緩解群組推薦中的冷啟動問題等，不斷提高群組推薦的效果.

[1]Zhang Yujie, Du Yulu, Meng Xiangwu. Research on group recommendation systems and their applications[J]. Chinese Journal of Computers, 2016, 39(4): 745-764 (in Chinese)(張玉潔, 杜雨露, 孟祥武. 組推薦系統(tǒng)及其應用與研究[J]. 計算機學報, 2016, 39(4): 745-764)

[2]Ntoutsi E, Stefanidis K. Fast group recommendations by applying user clustering[C] //Proc of the 31st Int Conf ER(ICER 2012). Berlin: Springer, 2012: 126-140

[3]Yu Zhiwen, Zhou Xingshe, Hao Yanbin. TV program recommendation for multiple viewers based on user profile[J]. User Modeling and User-adapted Interaction, 2006, 16(1): 63-82

[4]Linas B, Francesco R. Group recommendations with rank aggregation and collaborative filtering[C] //Proc of the 8th ACM Conf on Recommender Systems (RecSys 2010). New York: ACM, 2010: 26-30

[5]Ricci F, Rokach L. Recommender Systems Handbook[M]. Berlin: Springer, 2010: 40-62

[6]Gang Tian, Wang Jian. Time-aware Web service recommendations using implicit feedback[C] //Proc of the 21st IEEE Int Conf on Web Services (ICWS 2014). Piscataway, NJ: IEEE, 2014: 273-280

[7]Victor W, Chi Huangchi. Online role mining without over-fitting for service recommendation[C] //Proc of the 20th IEEE Int Conf on Web Services (ICWS 2013). Piscataway, NJ: IEEE, 2013: 58-65

[8]Yi Xing, Hong Liangjie, Zhong Erheng. Beyond clicks: Dwell time for personalization[C] //Proc of the 8th ACM Conf on Recommender Systems (RecSys 2014). New York: ACM, 2014: 113-120

[9]Laurent C. Dynamic poisson factorization[C] //Proc of the 9th ACM Conf on Recommender Systems (RecSys 2015). New York: ACM, 2015: 155-162

[10]Jing Shi, Wu Bin. A latent group model for group recommendation[C] //Proc of the 4th IEEE Int Conf on Mobile Service (MS 2015). Piscataway, NJ: IEEE, 2015: 233-238

[11]Boratto L, Carta S. Group identification and individual recommendations in group recommendation algorithms[C] //Proc of the 4th ACM Conf on Recommender Systems (RecSys 2010). New York: ACM, 2010: 27-34

[12]Seko S, Yagi T. Group recommendation using feature space representing behavioral tendency and power balance among members[C] //Proc of the 5th ACM Conf on Recommender Systems (RecSys 2011). New York: ACM, 2011: 101-108

[13]Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496

[14]Feng Guoxiang. Research on overlapping community detection method based on density peaks[D]. Changchun: Jilin University, 2015 (in Chinese)(馮國香. 基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法研究[D]. 長春: 吉林大學, 2015)

[15]Chen Yewang, Lai Dehe. A new method to estimate ages of facial image for large database[J]. Multimedia Tools & Application, 2015, 75(5): 1-19

[16]Liu Dongchang, Cheng Shifen. Density peaks clustering approach for discovering demand hot spots in city-scale taxi fleet dataset[C] //Proc of the 18th IEEE Int Conf on Intelligent Transportation System (ICITS 2015). Piscataway, NJ: IEEE, 2015: 1831-1836

[17]Mykola P, Jian Z. A robust density-based clustering algorithm for multi-manifold structure[C] //Proc of the 31st Annual ACM Symp on Applied Computing (SAC 2016). New York: ACM, 2016: 832-838

[18]Yu Yonghong, Gao Yang, Wang Hao. A ranking based poisson matrix factorization model for point-of-interest recommendation[J]. Journal of Computer Research and Development, 2016, 53(8): 1651-1663 (in Chinese)(余永紅, 高陽, 王皓. 基于Ranking的泊松矩陣分解興趣點推薦算法[J]. 計算機研究與發(fā)展, 2016, 53(8): 1651-1663)

[19]Wang Licai. Understanding and using contextual information in recommender system[C] //Proc of the 34th Annual ACM SIGIR Conf on Information Retrieval (SIGIR 2011). New York: ACM, 2011: 1329-1330

[20]Lancichinetti A, Fortunato S. Detecting the overlapping and hierarchical community structure in complex network[J]. New Journal of Physics, 2009, 11: 2-20

[21]Toon D, Simon D. Comparison of group recommendation algorithms[J]. Multimedia Tools & Application, 2014, 72(3): 2497-2541

[22]Gopalan P, Hofman J. Scalable recommendation with hierarchical poisson factorization[C] //Proc of the 31st Conf on Uncertainty in Artificial Intelligence (CUAI 2015). Arlington, VA: AUAI, 2015: 235-242