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

王海艷肖亦康

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

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

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

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

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

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

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

針對(duì)以上存在問(wèn)題，本文提出了一個(gè)解決方案，主要工作如下：

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

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

1 相關(guān)工作

1.1 用戶(hù)傾向獲取

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

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

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

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

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

1.3 密度峰值聚類(lèi)算法

密度峰值聚類(lèi)算法由Rodriguez等人[13]提出，由于其良好的適應(yīng)能力和極高的運(yùn)行效率而備受關(guān)注.近年來(lái)，不少學(xué)者也將該算法應(yīng)用到了多個(gè)領(lǐng)域.

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

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

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

2.1 用戶(hù)動(dòng)態(tài)傾向提取

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

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

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

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

(1)

然后，通過(guò)以下遞推表達(dá)式獲得時(shí)間節(jié)點(diǎn)t下用戶(hù)和項(xiàng)目的相關(guān)系數(shù)：

(2)

最后，時(shí)間節(jié)點(diǎn)t下用戶(hù)n對(duì)項(xiàng)目m選擇傾向的泊松分布如下：

(3)

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

(4)

2.2 用戶(hù)傾向值分解

在計(jì)算用戶(hù)相似度時(shí)，由于本文引入了時(shí)間因素，不同時(shí)間節(jié)點(diǎn)下不同用戶(hù)間的傾向值會(huì)出現(xiàn)缺省，無(wú)法計(jì)算，因此，在計(jì)算相似度之前需要先用張量分解預(yù)測(cè)補(bǔ)全每個(gè)用戶(hù)的傾向值.

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

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

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

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

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

(5)

這個(gè)分解模型能夠通過(guò)調(diào)整參數(shù)dU，dI，dC分別控制用戶(hù)、項(xiàng)目和時(shí)間的維度.這個(gè)特性對(duì)于現(xiàn)實(shí)中大規(guī)模數(shù)據(jù)集的處理很有利，因?yàn)榫仃嘦和M的規(guī)?？赡軙?huì)增大帶來(lái)潛在存儲(chǔ)問(wèn)題.

損失函數(shù)定義為

(6)

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

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

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

(7)

其中加入了Frobenius范數(shù)Ω[U,I,C]，因?yàn)閱渭兊淖钚』鲜鰮p失函數(shù)會(huì)導(dǎo)致過(guò)擬合現(xiàn)象，Ω[S]是作用于核心張量S的范數(shù)，其目的是降低核心張量復(fù)雜度.

時(shí)間上下文張量分解的用戶(hù)傾向預(yù)測(cè)算法如下所示：

算法1. 用戶(hù)傾向張量分解預(yù)測(cè)算法.

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

輸出：用戶(hù)傾向值張量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輸入為包含原用戶(hù)傾向值的3維張量Y，以及維度d.將原張量初始化分解為U,I,C這3個(gè)矩陣，通過(guò)迭代得到近似張量F′，最小化目標(biāo)函數(shù)得到最終的包含預(yù)測(cè)傾向值得張量F.其算法復(fù)雜度為O(KdUdIdC)，與已知的傾向值數(shù)量和維度線性相關(guān).

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

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

2.3.1 密度峰值聚類(lèi)算法

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

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

2.3.2 用戶(hù)節(jié)點(diǎn)距離矩陣

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

Table 1 Users Distance Matrix表1 用戶(hù)距離矩陣

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

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

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

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

(8)

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

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

(9)

2) 畫(huà)出相應(yīng)的決策圖.將δ且ρ異常大的用戶(hù)節(jié)點(diǎn)作為群組中心.

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

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

(10)

節(jié)點(diǎn)對(duì)社區(qū)有沒(méi)有貢獻(xiàn)用節(jié)點(diǎn)適應(yīng)度函數(shù)通過(guò)下面的式子反映出來(lái)：

(11)

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

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

輸入：用戶(hù)距離矩陣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

該算法復(fù)雜度為O(u2)，主要的計(jì)算耗時(shí)集中于每個(gè)節(jié)點(diǎn)的密度與距離計(jì)算，群組的構(gòu)建操作只需對(duì)用戶(hù)進(jìn)行一次遍歷即可完成復(fù)雜度為O(u).

3 實(shí)驗(yàn)仿真及效用評(píng)估

3.1 實(shí)驗(yàn)場(chǎng)景

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

3.2 實(shí)驗(yàn)評(píng)估

3.2.1 實(shí)驗(yàn)結(jié)果評(píng)價(jià)準(zhǔn)則

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

(12)

(13)

(14)

3.2.2 推薦效果對(duì)比實(shí)驗(yàn)

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

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

(15)

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

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

在Average策略下4種群組發(fā)現(xiàn)方法精度及誤差對(duì)比結(jié)果如圖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)方法精度及誤差對(duì)比結(jié)果如圖4和圖5所示：

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

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

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

3.2.3 群組可重疊問(wèn)題檢測(cè)實(shí)驗(yàn)

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

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

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

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

4 總 結(jié)

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

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

[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)及其應(yīng)用與研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(馮國(guó)香. 基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法研究[D]. 長(zhǎng)春: 吉林大學(xué), 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)(余永紅, 高陽(yáng), 王皓. 基于Ranking的泊松矩陣分解興趣點(diǎn)推薦算法[J]. 計(jì)算機(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