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

王永程，褚衍杰

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

王永程**，褚衍杰

（盲信號(hào)處理重點(diǎn)實(shí)驗(yà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)造相似矩陣，再利用譜聚類方法對(duì)用戶進(jìn)行聚類分析，聚類結(jié)果表征了用戶的關(guān)聯(lián)關(guān)系。采用Silhouette指標(biāo)和聚類準(zhǔn)確率來衡量用戶關(guān)系挖掘質(zhì)量，同時(shí)與傳統(tǒng)的K-Means方法進(jìn)行了比較，通過真實(shí)數(shù)據(jù)集實(shí)驗(yàn)，結(jié)果表明該算法在實(shí)驗(yàn)數(shù)據(jù)集上能達(dá)到90%以上的聚類準(zhǔn)確率，證明方法有效、可行。

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

1 引 言

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

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

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

圖聚類是發(fā)現(xiàn)用戶關(guān)聯(lián)關(guān)系的重要方法之一，本文采用譜聚類方法對(duì)用戶進(jìn)行聚類分析，并利用聚類結(jié)果來表征用戶的關(guān)系網(wǎng)絡(luò)，同時(shí)用戶關(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)矩陣

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

定義1 用戶空間分布向量

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

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

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

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

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

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

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

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

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

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

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

2.2 譜聚類

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

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

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

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

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

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

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

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

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

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

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

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

4.1 數(shù)據(jù)集、聚類質(zhì)量衡量指標(biāo)及實(shí)驗(yàn)流程

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

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

（1）Silhouette值

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

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

（2）聚類準(zhǔn)確率

聚類準(zhǔn)確率定義為

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

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

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

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

本節(jié)實(shí)驗(yàn)的目的是在真實(shí)數(shù)據(jù)集上驗(yàn)證基于譜聚類的用戶關(guān)聯(lián)關(guān)系挖掘算法的性能，數(shù)據(jù)集分為兩部分，分別代表兩個(gè)時(shí)間段的樣本數(shù)據(jù)，記為Ut1和Ut2，兩個(gè)時(shí)間區(qū)間的長(zhǎng)度相同，時(shí)間跨度為兩個(gè)月。將分別考察兩個(gè)數(shù)據(jù)集在輸入不同的聚簇?cái)?shù)k（k＝4，6，8）的情況下，輸出的Silhouette值以及聚類準(zhǔn)確率ρ的差異。圖2和表1分別為Silhouette值和聚類準(zhǔn)確率實(shí)驗(yàn)結(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）為時(shí)間區(qū)間t1內(nèi)不同聚簇?cái)?shù)k對(duì)應(yīng)的Silhouette值，從圖2（a）、（b）可以看出，當(dāng)k＜8時(shí)，有部分聚簇的Silhouette值接近于1，其他聚簇的Silhouette值小于1，且輪廓線不整齊，說明聚類質(zhì)量較差。圖2（c）顯示了k＝8時(shí)的Silhouette值，可發(fā)現(xiàn)各聚簇的Silhouette值幾乎為1，且輪廓線非常整齊，聚類質(zhì)量很好，說明k＝8為最優(yōu)聚簇?cái)?shù)，這與人工標(biāo)注的“朋友圈”數(shù)相等，實(shí)驗(yàn)結(jié)果符合預(yù)期。圖2（d）～（f）為時(shí)間區(qū)間t2內(nèi)不同聚簇?cái)?shù)k對(duì)應(yīng)的Silhouette值，其中Silhouette值的變化情況與圖2（a）～（c）基本相同，且對(duì)于不同時(shí)間區(qū)間，聚簇?cái)?shù)相同的Silhouette輪廓基本相同，從而說明了用戶的關(guān)系網(wǎng)絡(luò)在觀測(cè)時(shí)間內(nèi)基本穩(wěn)定。

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

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

4.3 與K-Means算法對(duì)比分析

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

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

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

5 結(jié)束語

本文利用手機(jī)用戶地理空間分布數(shù)據(jù)來挖掘用戶關(guān)聯(lián)關(guān)系，提出的基于譜聚類的關(guān)聯(lián)關(guān)系挖掘算法在實(shí)驗(yàn)數(shù)據(jù)集上能夠取得90%以上的聚類準(zhǔn)確率，與傳統(tǒng)K-Means方法相比，用戶關(guān)系挖掘性能更優(yōu)。實(shí)驗(yàn)結(jié)果表明了利用用戶空間分布數(shù)據(jù)挖掘用戶關(guān)系的可行性，與已有文獻(xiàn)相比，本文提出的算法進(jìn)一步挖掘了由用戶關(guān)聯(lián)關(guān)系形成的用戶社團(tuán)。本文研究成果可應(yīng)用于電商用戶推薦、反恐維穩(wěn)等領(lǐng)域，具有較高的實(shí)用價(jià)值。同時(shí)，該算法針對(duì)多用戶多維數(shù)據(jù)集，在用戶聚類方面具有普適意義，特別是對(duì)于高維分布數(shù)據(jù)集，能夠在數(shù)據(jù)空間非凸分布的情況有效收斂于全局最優(yōu)。由于實(shí)驗(yàn)數(shù)據(jù)集涉及的用戶規(guī)模有限，本文未考慮用戶規(guī)模增長(zhǎng)對(duì)算法運(yùn)行效率的影響，這將是下一步研究的內(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年于盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘、網(wǎng)絡(luò)測(cè)量；

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年于盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向?yàn)樾畔⑻幚怼?/p>

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