基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘*

王永程，褚衍杰

基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘*

王永程**，褚衍杰

（盲信號處理重點實驗室，成都610041）

為了從用戶地理空間分布數(shù)據(jù)中挖掘用戶間關(guān)聯(lián)關(guān)系，提出了一種基于譜聚類的關(guān)聯(lián)關(guān)系挖掘算法。首先定義了關(guān)聯(lián)度，用以衡量用戶之間空間分布的相似性，基于關(guān)聯(lián)度構(gòu)造相似矩陣，再利用譜聚類方法對用戶進行聚類分析，聚類結(jié)果表征了用戶的關(guān)聯(lián)關(guān)系。采用Silhouette指標和聚類準確率來衡量用戶關(guān)系挖掘質(zhì)量，同時與傳統(tǒng)的K-Means方法進行了比較，通過真實數(shù)據(jù)集實驗，結(jié)果表明該算法在實驗數(shù)據(jù)集上能達到90%以上的聚類準確率，證明方法有效、可行。

用戶行為分析；用戶關(guān)系挖掘；譜聚類；關(guān)聯(lián)度；K-Means

1 引 言

用戶行為分析是近年來數(shù)據(jù)分析領(lǐng)域的熱點問題之一。發(fā)現(xiàn)用戶行為模式，通過分析用戶間行為模式的相似性來挖掘用戶的關(guān)聯(lián)關(guān)系，是重要的研究內(nèi)容之一。本文擬針對用戶在地理空間上的分布特征，通過定義用戶空間分布的相似性將用戶相關(guān)關(guān)聯(lián)在一起，發(fā)現(xiàn)“朋友圈”，即用戶關(guān)聯(lián)關(guān)系網(wǎng)絡(luò)。

目前研究用戶行為的諸多文獻中，基于用戶行為數(shù)據(jù)流挖掘用戶行為模式是主流的研究點之一[1-2]。文獻[1]針對受噪聲污染及不完備的行為事件流，利用信息熵理論估計周期性行為模式，算法在測試數(shù)據(jù)集上表現(xiàn)出了較好的魯棒性。在發(fā)現(xiàn)用戶行為模式的基礎(chǔ)上，對用戶行為進行預(yù)測也成為該領(lǐng)域的研究熱點[3-4]。文獻[3]的研究發(fā)現(xiàn)，用戶在線上的行為活動之間具有較強的相關(guān)性，這導(dǎo)致用戶的后續(xù)行為能夠被預(yù)測，如果用戶行為發(fā)生的時間信息能夠被利用的話，預(yù)測的準確率將更高。無獨有偶，麻省理工學(xué)院一個名為“RealitY Mining”的項目組同樣發(fā)現(xiàn)，不同類型的手機用戶在地理空間上的分布熵具有較大的差異，某些用戶，如教員，他們的空間分布熵很低，意味著他們在空間上分布行為容易被預(yù)測，而另一些用戶，如學(xué)生，則具有較高的信息熵及不確定較大，他們的行為不容易被預(yù)測。同樣，這樣的行為差異被該項目組用戶區(qū)分用戶性質(zhì)，獲得了較高的準確率。

上述研究主要關(guān)注用戶個體行為，如個體行為模式挖掘和預(yù)測以及利用個體行為模式的差異來區(qū)分不同性質(zhì)的用戶，與此不同，文獻[5-6]研究了不同用戶之間行為模式的相似性以及由此反映的更深層次的用戶之間的關(guān)聯(lián)關(guān)系。文獻[5]通過用戶在時空二維空間上的分布行為，挖掘任意兩個用戶之間的社交關(guān)系，同時提供了量化用戶之間關(guān)聯(lián)程度的概率推理框架，分析了不同的時空粒度下推理的精度問題。文獻[6]同樣致力于挖掘用戶之間的關(guān)聯(lián)關(guān)系，但需要的時空粒度更小，普適性不及文獻[5]。受文獻[5-6]啟發(fā)，本文研究了手機用戶在地理空間上的分布行為，定義了用戶空間分布的相似性，與之不同的是，本文不僅給出了任意兩個用戶之間的關(guān)聯(lián)度，而且進一步挖掘了多個用戶形成的關(guān)系網(wǎng)絡(luò)，最終輸出用戶的“朋友圈”，即具有組織屬性的用戶團體。

圖聚類是發(fā)現(xiàn)用戶關(guān)聯(lián)關(guān)系的重要方法之一，本文采用譜聚類方法對用戶進行聚類分析，并利用聚類結(jié)果來表征用戶的關(guān)系網(wǎng)絡(luò)，同時用戶關(guān)系挖掘的質(zhì)量可以用聚類質(zhì)量來度量。譜聚類作為圖聚類方法之一，在諸多領(lǐng)域得到了成功應(yīng)用，如醫(yī)學(xué)[7]、電力[8]等，與K-Means、EM等建立在凸分布基礎(chǔ)上的傳統(tǒng)聚類算法相比，譜聚類算法能在數(shù)據(jù)空間不是凸分布的情況下收斂于全局最優(yōu)。在構(gòu)建用戶相似矩陣的基礎(chǔ)上，應(yīng)用譜聚類算法能夠成功輸出用戶的關(guān)系網(wǎng)絡(luò)。

2 基本概念

2.1 關(guān)聯(lián)度、關(guān)聯(lián)圖及關(guān)聯(lián)矩陣

本文研究在特定時間區(qū)間內(nèi)用戶的空間分布情況，這里的時間區(qū)間都是由離散的時刻構(gòu)成。

定義1 用戶空間分布向量

用戶在時間區(qū)間t＝[α，b]內(nèi)的空間分布向量表示為

式中：n表示用戶個數(shù)；i為用戶索引；m為納入考慮范圍內(nèi)的地理位置個數(shù)；如果用戶在時間區(qū)間t內(nèi)在地點k（1≤k≤m）處出現(xiàn)，則lk＝1，否則lk＝0。

定義2 關(guān)聯(lián)度

兩個用戶Ui、Uj在給定時間區(qū)間t＝[α，b]內(nèi)的關(guān)聯(lián)度定義為

如果把n個用戶看做n個節(jié)點，關(guān)聯(lián)度看做兩個節(jié)點間邊的權(quán)重，則可以得到關(guān)聯(lián)圖和關(guān)聯(lián)矩陣的概念。

定義3 關(guān)聯(lián)圖、關(guān)聯(lián)矩陣和聚類模型

設(shè)n個用戶對應(yīng)的空間分布向量集合為Ut＝，則

（1）Ut的關(guān)聯(lián)圖定義為加權(quán)圖G（V，E），其中，頂點集V＝Ut，邊集n}；邊的權(quán)重為；

（2）Ut的關(guān)聯(lián)矩陣定義為圖G在時間區(qū)間t內(nèi)的鄰接矩陣

（3）Ut的聚類模型定義為Ψ＝[C1，C2，…，Ck]，其中k為聚簇數(shù)，Ci（i＝1，2，…，k）為滿足下列條件的簇：；?i≠j，Ci∩Ci＝?。

本文擬根據(jù)關(guān)聯(lián)度對用戶Ut進行劃分，從而得到其聚類模型，即用戶的關(guān)聯(lián)關(guān)系網(wǎng)絡(luò)。

2.2 譜聚類

由2.1節(jié)可知，關(guān)聯(lián)矩陣Ω為對稱矩陣，定義每個節(jié)點的度為di＝ci1＋ci2＋???＋cin，且稱D＝diag（ d1，d2，…，dn）為度矩陣。

譜聚類算法建立在圖論中的譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題，是一種點對聚類算法，利用LaPlacian矩陣的前k個最小特征值對應(yīng)的特征向量構(gòu)造新的特征向量空間Rk，在這個新的空間內(nèi)建起與原始數(shù)據(jù)的對應(yīng)關(guān)系，然后聚類成k個簇。LaPlacian矩陣有3種形式[9]，分別為未規(guī)范化LaPlacian矩陣L＝D-Ω，規(guī)范化且對稱的LaPlacian矩陣LsYm＝D-1/2L D1/2以及規(guī)范化但不對稱的LaPlacian矩陣LrW＝D-1L。實驗和統(tǒng)計分析結(jié)果表明，如果圖中各節(jié)點度分布比較均勻的話，3種類型的LaPlacian矩陣在聚類性能上無明顯區(qū)別，如果圖中節(jié)點度傾斜分布時，LrW性能最優(yōu)，故本文算法采用LrW作為LaPlacian矩陣。

3 基于譜聚類的關(guān)聯(lián)關(guān)系挖掘算法

基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘算法輸入為n個用戶對應(yīng)的空間分布向量集合為Ut＝、時間區(qū)間t＝[α，b]以及聚簇數(shù)k，輸出聚類模型Ψ＝[C1，C2，…，Ck]。主要步驟如下：

（1）根據(jù)關(guān)聯(lián)度定義，z對任意一對用戶Ui，Uj，計算關(guān)聯(lián)度；

（3）計算LaPlacian矩陣LrW＝D-1L＝I-D-1Ω，D＝diag（ d1，d2，…，dn）；

（4）計算LrW前k個最小特征值對應(yīng)的特征向量υ1，υ2，…，υk；

（5）令Y＝[υ1，υ2，…，υk]∈Rn×k，Y的行向量定義為γ1，γ2，…，γn，對應(yīng)于k維特征空間內(nèi)的n個點；

（6）利用K-Means聚類算法對（γi）i＝1，2，…，n進行聚類，得到k個簇{B1，B2，…，Bk}；

（7）返回Ψ＝[C1，C2，…，Ck]，其中Cj＝，i＝1，2，…，n，j＝1，2，…，k。

算法使用關(guān)聯(lián)度來衡量兩個用戶空間分布的相似性，并據(jù)此構(gòu)建關(guān)聯(lián)矩陣，關(guān)聯(lián)矩陣作為LaPla_ cian矩陣計算的輸入，通過選取LaPlacian矩陣的前k個最小特征值構(gòu)建特征空間。特征值及特征向量的計算為算法的主要時間消耗環(huán)節(jié)。在特征向量空間Rn×k中，這里利用K-Means聚類算法將n個數(shù)據(jù)點聚類為k個簇，Ci（i＝1，2，…，k）表示具有相同組織屬性的用戶集合，輸入相同聚簇的用戶形成用戶關(guān)系網(wǎng)絡(luò)。值得注意的是，這里的聚類算法不限于K-Means算法，其他如層次聚類或密度聚類算法都可以作為候選算法。

4 實驗分析

4.1 數(shù)據(jù)集、聚類質(zhì)量衡量指標及實驗流程

采用RealitY Mining項目組的數(shù)據(jù)收集思路，我們采集了100位手機用戶志愿者的行為數(shù)據(jù)集，該數(shù)據(jù)集主要包含用戶的ID（用戶的唯一標識）、呼叫時間、呼叫持續(xù)時間、基站位置（標識用戶地理位置）等信息，本文只抽取不同時刻用戶IP和基站位置來構(gòu)建用戶空間分布向量，作為算法的數(shù)據(jù)源。為了驗證用戶關(guān)聯(lián)關(guān)系挖掘的準確性，對所涉及用戶的組織屬性信息進行了人工標注，這里的組織屬性信息指用戶隸屬的部門，100個用戶分別為8個部門的員工，用戶之間存在關(guān)聯(lián)關(guān)系表示用戶同屬于一個部門，存在少量用戶同屬于兩個或兩個以上的部門。

下面介紹本文采用的用戶關(guān)系挖掘質(zhì)量的衡量指標：Silhouette值[10]和聚類準確率。

（1）Silhouette值

節(jié)點i的Silhouette值定義為

式中：α（i）表示節(jié)點到同簇中其他節(jié)點的平均距離；b（i）表示節(jié)點到其他簇中節(jié)點的平均距離。Silhouette值的取值范圍為[-1，1]，s（i）越接近1，表示聚類效果越好，從而用戶關(guān)系挖掘質(zhì)量越高，反之，挖掘質(zhì)量越差。Silhouette值從聚類結(jié)果本身出發(fā)，衡量聚類質(zhì)量，不依賴于人工標注信息，具備一定的參考價值。同時考慮到樣本中的人工標注信息，我們定義了聚類準確率。

（2）聚類準確率

聚類準確率定義為

式中：Nc表示正確聚類的樣本數(shù)量；Nα表示所有的樣本數(shù)量。Nc的計算方法為針對聚類結(jié)果中的每一個聚簇i（1≤i≤k），根據(jù)標注信息，統(tǒng)計聚簇i中真實的聚簇數(shù)以及各聚簇對應(yīng)的樣本數(shù)量，樣本數(shù)量最多的簇所對應(yīng)的樣本為正確聚類的樣本?？紤]到某些用戶可能擁有多個部門身份，即同屬于不同的聚簇，當(dāng)這些用戶被分類到真實所屬的聚簇中時，都將其視為被正確聚類。聚類準確率越高，表示用戶關(guān)系挖掘質(zhì)量越高，反之，挖掘質(zhì)量越差。

圖1顯示了實驗分析流程，本實驗分別在不同聚簇數(shù)k（k＝4，6，8）的情況下對實驗結(jié)果性能進行考察。仿真條件為因特爾酷睿雙核3.16 GHz處理器及4 GB內(nèi)存。

圖1 基于譜聚類的用戶關(guān)聯(lián)關(guān)系實驗分析流程Fig.1 ExPeriment floW of user association mining based on sPecial clustering

4.2 基于真實數(shù)據(jù)集的聚類質(zhì)量分析

本節(jié)實驗的目的是在真實數(shù)據(jù)集上驗證基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘算法的性能，數(shù)據(jù)集分為兩部分，分別代表兩個時間段的樣本數(shù)據(jù)，記為Ut1和Ut2，兩個時間區(qū)間的長度相同，時間跨度為兩個月。將分別考察兩個數(shù)據(jù)集在輸入不同的聚簇數(shù)k（k＝4，6，8）的情況下，輸出的Silhouette值以及聚類準確率ρ的差異。圖2和表1分別為Silhouette值和聚類準確率實驗結(jié)果。

圖2 基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘算法性能（Silhouette值）Fig.2 Performance of user association mining based on sPecial clustering（Silhouette value）

圖2 （a）～（c）為時間區(qū)間t1內(nèi)不同聚簇數(shù)k對應(yīng)的Silhouette值，從圖2（a）、（b）可以看出，當(dāng)k＜8時，有部分聚簇的Silhouette值接近于1，其他聚簇的Silhouette值小于1，且輪廓線不整齊，說明聚類質(zhì)量較差。圖2（c）顯示了k＝8時的Silhouette值，可發(fā)現(xiàn)各聚簇的Silhouette值幾乎為1，且輪廓線非常整齊，聚類質(zhì)量很好，說明k＝8為最優(yōu)聚簇數(shù)，這與人工標注的“朋友圈”數(shù)相等，實驗結(jié)果符合預(yù)期。圖2（d）～（f）為時間區(qū)間t2內(nèi)不同聚簇數(shù)k對應(yīng)的Silhouette值，其中Silhouette值的變化情況與圖2（a）～（c）基本相同，且對于不同時間區(qū)間，聚簇數(shù)相同的Silhouette輪廓基本相同，從而說明了用戶的關(guān)系網(wǎng)絡(luò)在觀測時間內(nèi)基本穩(wěn)定。

表1 本文算法與K-Means算法聚類準確率性能比較Tab.1 ComParison of Performance on clustering accuracY betWeen the ProPosed algorithm and K-Means method %

與圖2對應(yīng)，從表1可看出，本文算法的聚類準確率同樣在k＝8時達到最高，為90%以上，顯示了基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘算法在實驗數(shù)據(jù)集上優(yōu)異的性能。

4.3 與K-Means算法對比分析

本節(jié)的實驗?zāi)康氖窃谡鎸崝?shù)據(jù)集上與傳統(tǒng)聚類方法K-Means算法進行性能比較，與4.2節(jié)相同，數(shù)據(jù)集同樣采用兩個時間區(qū)間的樣本數(shù)據(jù)，且在不同的聚簇數(shù)k（k＝4，6，8）的情況下，比較Silhouette值以及聚類準確率ρ。圖3為K-Means算法的Sil_ houette值實驗結(jié)果，K-Means算法的聚類準確率實驗結(jié)果見表1。

圖3 K-Means算法性能（Silhouette值）Fig.3 Performance of K-Means（Silhouette value）

圖3 （a）～（c）和圖3（d）～（f）分別為K-Means算法在時間區(qū)間t1和t2內(nèi)不同聚簇數(shù)k對應(yīng)的Silhouette值。隨著k值的變化，Silhouette值的變化趨勢與本文算法的變化趨勢基本相同。不同在于，與本文算法的實驗結(jié)果相比，對于相同數(shù)據(jù)集和相同k值，K-Means算法的Silhouette值輪廓線整齊度下降不少。結(jié)合表1兩種算法的聚類準確率性能結(jié)果來看，本文算法的聚類性能要優(yōu)于K-Means算法，提升幅度在10個百分點左右。上述實驗結(jié)果的原因在于當(dāng)樣本數(shù)據(jù)的維數(shù)升高時（本文數(shù)據(jù)集的維數(shù)為20），K-Means算法難以適應(yīng)數(shù)據(jù)空間非凸分布的情況，而譜聚類仍然能在此種情況下獲得全局最優(yōu)的效果。

5 結(jié)束語

本文利用手機用戶地理空間分布數(shù)據(jù)來挖掘用戶關(guān)聯(lián)關(guān)系，提出的基于譜聚類的關(guān)聯(lián)關(guān)系挖掘算法在實驗數(shù)據(jù)集上能夠取得90%以上的聚類準確率，與傳統(tǒng)K-Means方法相比，用戶關(guān)系挖掘性能更優(yōu)。實驗結(jié)果表明了利用用戶空間分布數(shù)據(jù)挖掘用戶關(guān)系的可行性，與已有文獻相比，本文提出的算法進一步挖掘了由用戶關(guān)聯(lián)關(guān)系形成的用戶社團。本文研究成果可應(yīng)用于電商用戶推薦、反恐維穩(wěn)等領(lǐng)域，具有較高的實用價值。同時，該算法針對多用戶多維數(shù)據(jù)集，在用戶聚類方面具有普適意義，特別是對于高維分布數(shù)據(jù)集，能夠在數(shù)據(jù)空間非凸分布的情況有效收斂于全局最優(yōu)。由于實驗數(shù)據(jù)集涉及的用戶規(guī)模有限，本文未考慮用戶規(guī)模增長對算法運行效率的影響，這將是下一步研究的內(nèi)容。

[1] GUAN T，WANG K R，ZHANG S P.A robust PeriodicitY mining method from incomPlete and noisY observations based on relative entroPY[J].International Journal of Ma_ chine Learning and CYbernetics，2015，6（2）：1-11.

[2] GOEL A，MALLICK B.Customer Purchasing behavior using sequential Pattern mining technique[J].International Jour_ nal of ComPuter APPlications，2015，119（1）：1-5.

[3] SINATRA R，SZELL M.EntroPY and the PredictabilitY of online life[J].EntroPY，2014，16（1）：543-556.

[4] PHITHAKKITNUKOON S，HUSNA H，DANTU R.Be_ havioral entroPY of a cellular Phone user[M]//Social ComPuting，Behavioral Modeling，and Prediction.NeW York：SPringer，2008：160-167.

[5] CRANDALL D J，BACKSTROM L，COSLEY D，et al.In_ ferring social ties from geograPhic coincidences[J].Pro_ ceedings of the National AcademY of Sciences，2010，107（52）：22436-22441.

[6] EAGLE N，PENTLAND A S，LAZER D.Inferring friend_ shiP netWork structure bY using mobile Phone data[J]. Proceedings of the National AcademY of Sciences，2009，106（36）：15274-15278.

[7] TARTARE G，HAMAD D，AZAHAF M，et al.SPectral clustering aPPlied for dYnamic contrast-enhanced MR a_ nalYsis of time-intensitY curves[J].ComPuterized Medi_ cal Imaging and GraPhics，2014，38（8）：702-713.

[8] SáNCHEZ-GARCíA R J，F(xiàn)ENNELLY M，NORRIS S，et al. Hierarchical sPectral clustering of PoWer grids[J].IEEE Transactions on PoWer SYstems，2014，29（5）：2229-2237.

[9] LUXBURG U.A tutorial on sPectral clustering[J].Sta_ tistics and ComPuting，2007，17（4）：395-416.

[10] AMORIM R C，HENNIG C.Recovering the number of clusters in data sets With noise features using feature res_ caling factors[J].Information Sciences，2015，324（12）：126-145.

王永程（1987—），男，山西介休人，2009年于清華大學(xué)獲學(xué)士學(xué)位，2012年于盲信號處理重點實驗室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向為數(shù)據(jù)挖掘、網(wǎng)絡(luò)測量；

WANG Yongcheng Was born in Jiexiu，Shanxi Province，in 1987.He received the B.S. degree from Tsinghua UniversitY and the M.S. degree from KeY LaboratorY of Science and TechnologY on Blind Signal Processing in 2009 and 2012，resPectivelY.He is current_ lY Working toWard the Ph.D.degree.His research concerns data minning and netWork measurement.

Email：407541127@qq.com

褚衍杰（1982—），男，山東棗莊人，2005年于清華大學(xué)獲學(xué)士學(xué)位，2008年于盲信號處理重點實驗室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向為信息處理。

CHU Yanjie Was born in Zaozhuang，Shandong Province，in 1982.He received the B.S.degree from Tsinghua UniversitY and the M.S.degree from KeY LaboratorY of Science and Tech_ nologY on Blind Signal Processing in 2005 and 2008，resPective_ lY.He is currentlY Working toWard the Ph.D.degree.His re_ search concerns information Processing.

User Association Mining Based on Spectral Clustering

WANG Yongcheng，CHU Yanjie
（National KeY LaboratorY of Science and TechnologY on Blind Signal Processing，Chengdu 610041，China）

For mining association relationshiP from user's geograPhical sPatial distribution data，a neW meth_ od based on sPectral clustering is ProPosed.FirstlY，the correlation degree is defined，Which is used to measure the similaritY of sPatial distribution of users，and then the similaritY matrix is constructed.Cluste_ ring analYsis is conducted bY using sPectral clustering method，and the relationshiP betWeen users is charac_ terized bY clustering results.The Silhouette index and clustering accuracY are used to measure the qualitY of user relationshiP mining，meanWhile the traditional K-Means method is comPared With the ProPosed algo_ rithm.ExPeriments on real data set shoW that the algorithm can achieve more than 90%of the clustering accuracY，indicating that the method is effective and feasible.

user behavior analYsis；user association mining；sPectral clustering；correlation degree；K-Means

TP393

A

1001-893X（2016）01-0032-06

10.3969/j.issn.1001-893x.2016.01.006

王永程，褚衍杰.基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘[J].電訊技術(shù)，2016，56（1）：32-37.[WANG Yongcheng，CHU Yanjie.User associa_ tion mining based on sPectral clustering[J].Telecommunication Engineering，2016，56（1）：32-37.]

2015-10-22；

2015-12-29 Received date：2015-10-22；Revised date：2015-12-29

**通信作者：407541127@qq.com Corresponding author：407541127@qq.com