劉曉慧 江 峰 杜軍威 余東瑾

（青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院 青島 266061）

1 引言

隨著互聯(lián)網(wǎng)時(shí)代的崛起和飛速發(fā)展，各種信息和數(shù)據(jù)正呈指數(shù)級(jí)增長(zhǎng)，在這種數(shù)據(jù)爆炸式擴(kuò)張的情況下，卻出現(xiàn)一種有價(jià)值信息匱乏的現(xiàn)象，從豐富復(fù)雜的數(shù)據(jù)信息中提取出具有實(shí)際意義的信息已經(jīng)成為當(dāng)代的迫切需求［1］。因此，隨著時(shí)代的發(fā)展，數(shù)據(jù)挖掘也在迅速發(fā)展，并且正在遍及于各個(gè)領(lǐng)域。由CNNIC公布的39期中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r顯示，到2017年12月為止，中國(guó)互聯(lián)網(wǎng)用戶數(shù)量為7.72億，滲透率上升為55.8%。在以人為本的web3.0平臺(tái)下，需使用更人性化的方式對(duì)互聯(lián)網(wǎng)用戶的興趣點(diǎn)［2］進(jìn)行分析，并且利用此興趣點(diǎn)來為互聯(lián)網(wǎng)瀏覽用戶實(shí)現(xiàn)有針對(duì)性的服務(wù)。

用戶的偏好分析可以由用戶的瀏覽內(nèi)容得到，以分類、聚類的方式對(duì)用戶瀏覽內(nèi)容進(jìn)行細(xì)致劃分，通過挖掘用戶搜索行為進(jìn)一步得到更為具體的搜索內(nèi)容信息，進(jìn)而得到用戶的細(xì)粒度偏好輸出。近些年來，越來越多的學(xué)者們關(guān)注于用戶的偏好方面的分析，從用戶角度出發(fā)的如協(xié)調(diào)過濾等算法［3］，或關(guān)注電子商務(wù)領(lǐng)域中的用戶的模型構(gòu)建［4］。從而分析不同用戶的偏好特點(diǎn)。然而，目前的用戶偏好分析方法仍然有很多不足［5］。首先，現(xiàn)有的大多數(shù)算法是挖掘?yàn)g覽用戶的原始屬性，因此在用戶的細(xì)粒度分析部分變得難以實(shí)現(xiàn)；另外，在挖掘細(xì)粒度偏好時(shí)，現(xiàn)有算法的精度和效率不是很理想。

在傳統(tǒng)的無向圖層次聚類［6］中，首先將無向圖所有的邊執(zhí)行排序操作，然后在所有的邊中選擇最大權(quán)重［7］的一條邊，最后算法對(duì)該邊的相鄰節(jié)點(diǎn)完成合并，并對(duì)連接到鄰居節(jié)點(diǎn)的每一條邊重新計(jì)算權(quán)重。普通聚類算法在執(zhí)行聚類時(shí)一次只能對(duì)兩個(gè)點(diǎn)合并，即便在加速算法中也會(huì)由于點(diǎn)沖突會(huì)導(dǎo)致每輪合并的節(jié)點(diǎn)的數(shù)量受到限制，以致算法效率不高，且對(duì)多邊點(diǎn)［8］的處理也存在問題。此外，傳統(tǒng)算法聚類時(shí)會(huì)使用衰減因子對(duì)合并點(diǎn)的鄰邊權(quán)重控制衰減［9］，這就會(huì)導(dǎo)致一個(gè)多邊點(diǎn)經(jīng)過衰減因子的多次衰減后，邊的權(quán)重因此嚴(yán)重降低而不再能代表其原有的含義?；谏鲜龇治觯疚囊曰ヂ?lián)網(wǎng)app為研究數(shù)據(jù)來源，介紹無向圖層次聚類算法及對(duì)其并行優(yōu)化的算法原理，并通過實(shí)驗(yàn)驗(yàn)證算法的有效性。

2 無向圖層次聚類算法

2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological net?works》，指出復(fù)雜網(wǎng)絡(luò)中普遍存在著聚類特性［10］，此后越來越多的學(xué)者開始對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行算法探究。在基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類算法研究過程中，局部搜索算法和譜聚類算法成為最為典型的兩個(gè)算法。譜聚類算法主要是把每個(gè)樣本數(shù)據(jù)視為節(jié)點(diǎn)，根據(jù)數(shù)據(jù)之間的相似度對(duì)邊進(jìn)行賦權(quán)值從而得到無向帶權(quán)圖［11］，由此把聚類轉(zhuǎn)變成對(duì)圖的劃分。近幾年來，具有代表性的成果有GBR算法［12］，基于dominant集的點(diǎn)對(duì)聚類算法［13］和基于最大θ距離子樹的聚類算法［14］等。在無向圖層次聚類算法中，更是遵循了譜圖原理［15］，即對(duì)無向圖所有的邊排序，通過選擇權(quán)重最大的邊對(duì)其相鄰節(jié)點(diǎn)合并，并對(duì)新節(jié)點(diǎn)邊的權(quán)重重新計(jì)算，當(dāng)沒有節(jié)點(diǎn)可以合并或者滿足停止條件時(shí)輸出聚類結(jié)果的層次結(jié)構(gòu)。

在對(duì)用戶偏好分析中，用戶的搜索行為可當(dāng)作是一個(gè)有向圖，用戶搜索的關(guān)鍵詞和點(diǎn)擊的內(nèi)容看作是圖的頂點(diǎn)，每一條搜索日志可認(rèn)為是有向圖的一條邊。這樣形成一個(gè)關(guān)于關(guān)鍵詞到內(nèi)容的有向圖，由于是非連通的圖，內(nèi)容不含有指向任何節(jié)點(diǎn)的有向邊，由于存在這樣的問題導(dǎo)致不能通過有向圖對(duì)用戶行為偏好進(jìn)行分析挖掘。所以在通過用戶的搜索記錄進(jìn)行關(guān)鍵詞與內(nèi)容之間建模時(shí)，采用由無向圖的方式代替有向圖來表達(dá)二者之間的映射關(guān)系，這樣內(nèi)容也有可指向關(guān)鍵詞的邊。通過無向圖層次聚類對(duì)用戶搜索日志信息執(zhí)行聚類，最后可以通過關(guān)鍵詞和內(nèi)容之間的映射關(guān)系得到聚類結(jié)果，聚合內(nèi)容的類名可作為關(guān)鍵詞［16］，聚合內(nèi)容即為用戶搜索內(nèi)容。

3 無向圖層次聚類并行優(yōu)化算法POHCUGO

3.1 構(gòu)建無向圖

用戶的搜索行為［17］會(huì)在每天生成大量的搜索日志，所以在數(shù)據(jù)挖掘過程前需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，刪除部分沒有用處的日志以避免后續(xù)冗余的計(jì)算。數(shù)據(jù)的清理［18］主要有兩點(diǎn)：

1）用戶在輸入關(guān)鍵詞時(shí)，不可避免會(huì)出現(xiàn)單復(fù)數(shù)現(xiàn)象或拼寫錯(cuò)誤，首先需要對(duì)關(guān)鍵詞進(jìn)行歸一化操作處理。對(duì)關(guān)鍵詞設(shè)置一定的閾值，比如拼寫錯(cuò)誤為小概率發(fā)生事件，當(dāng)關(guān)鍵詞發(fā)生概率值小于設(shè)置的閾值時(shí)可以當(dāng)作是拼寫錯(cuò)誤過濾掉，另外降低搜索關(guān)鍵詞的數(shù)量級(jí)，通過將一些不易識(shí)別的特殊字符統(tǒng)一變更為空格格式，由此把關(guān)鍵詞歸一化為一種形式。除了關(guān)鍵詞之外，內(nèi)容也需要設(shè)定一個(gè)閾值對(duì)內(nèi)容也進(jìn)行篩選，過濾冷門內(nèi)容。

2）對(duì)用戶的搜索日志信息按照某種規(guī)則進(jìn)行清理篩選，一般而言瀏覽歷史記錄分為顯示、點(diǎn)擊和下載等多種形式，為提高準(zhǔn)確性應(yīng)保證關(guān)鍵詞和內(nèi)容之間的關(guān)聯(lián)性，對(duì)添加到無向圖中的關(guān)鍵詞與內(nèi)容要求二者之間能夠進(jìn)行高度匹配，故只有點(diǎn)擊以上的強(qiáng)行為才能加入無向圖中完成聚類。

根據(jù)以上提出的方法對(duì)數(shù)據(jù)進(jìn)行處理得到關(guān)鍵詞與內(nèi)容的對(duì)應(yīng)關(guān)系，并且以此對(duì)應(yīng)關(guān)系為基礎(chǔ)生成搜索日志無向圖，為防止數(shù)據(jù)膨脹采用關(guān)鍵詞到內(nèi)容的操作次數(shù)的對(duì)數(shù)值作為對(duì)應(yīng)邊的權(quán)重，如圖1所示。

圖1 搜索無向圖

3.2 節(jié)點(diǎn)合并

在傳統(tǒng)層次聚類中，從下而上合并類簇，每次找到距離最短的兩個(gè)節(jié)點(diǎn)合并，但這種合并的效率非常低。通常首先對(duì)所有的邊按權(quán)重值進(jìn)行排序，合并權(quán)重值最大也即最近的節(jié)點(diǎn)對(duì)，此時(shí)應(yīng)注意在合并時(shí)主要多對(duì)節(jié)點(diǎn)之間避免有相連的邊，防止在合并時(shí)產(chǎn)生沖突問題。如圖2所示，假使圖中進(jìn)行聚類的距離最近的節(jié)點(diǎn)分別是AB、CD、EC，我們不能對(duì)EC進(jìn)行合并，只能對(duì)AB和CD進(jìn)行合并，由于合并后的AB需再次計(jì)算與A、B全部相鄰節(jié)點(diǎn)的邊權(quán)重，并且E與A相鄰，如果EC節(jié)點(diǎn)進(jìn)行合并則可能導(dǎo)致計(jì)算沖突。

圖2 無向節(jié)點(diǎn)合并

在合并之后會(huì)得到一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)相鄰的邊權(quán)重需要進(jìn)行重新計(jì)算，此時(shí)通常需要對(duì)邊的權(quán)重按照一定值進(jìn)行衰減，例如AB進(jìn)行合并時(shí)，新AB節(jié)點(diǎn)為位于A、B之間的點(diǎn)，這意味著AB會(huì)包括A和B的相關(guān)數(shù)據(jù)信息，也使得E與AB的權(quán)重值要小于E與A的權(quán)重值，因此算法需采用一個(gè)衰減因子將合并后的節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的邊權(quán)重執(zhí)行衰減。

3.3 并行化加速

一般來說熱門關(guān)鍵詞會(huì)對(duì)應(yīng)較多的熱門內(nèi)容，如圖3所示。經(jīng)常會(huì)出現(xiàn)很熱的內(nèi)容與關(guān)鍵詞進(jìn)行多次合并［19］，由于衰減因子［20］的影響，在若干輪迭代后，關(guān)鍵詞長(zhǎng)尾的邊權(quán)重值會(huì)因?yàn)樗p而變得很小，從而失去可比性。

圖3 高熱關(guān)鍵詞節(jié)點(diǎn)

對(duì)于這種情況，提出一種并行［21］合并［22］的解決方案。如圖4所示，把含信息量很大的關(guān)鍵詞節(jié)點(diǎn)劃分成為多個(gè)對(duì)應(yīng)的關(guān)鍵詞子節(jié)點(diǎn)，并且把原來相連的邊按照一定的權(quán)重分別賦值于這多個(gè)子節(jié)點(diǎn)，此處的拆分并非邏輯上的，如圖4中所示的K2節(jié)點(diǎn)依舊是之前唯一節(jié)點(diǎn)，只是將一個(gè)K2節(jié)點(diǎn)在物理層面上分為多個(gè)子節(jié)點(diǎn)，K2通過各個(gè)子節(jié)點(diǎn)連接到C1、C2、C3、C4，由此其中一個(gè) K2與 C1、C2點(diǎn)連接，另外一個(gè)K2與C3、C4連接，將節(jié)點(diǎn)拆分不僅能夠并行的方式合并這些點(diǎn)，而且還能夠優(yōu)化邊權(quán)重的衰減，K2可以在一輪聚合中同時(shí)與C1和C3進(jìn)行合并，因此算法的收斂速度得到快速提升。

圖4 高熱節(jié)點(diǎn)并行優(yōu)化

我們一般會(huì)采用迭代次數(shù)作為聚類的停止條件，為對(duì)合并層數(shù)進(jìn)行有效控制我們?cè)黾恿硗鈨蓚€(gè)停止條件：首先限制邊的衰減次數(shù)，刪除被衰減n次的邊；其次設(shè)置閾值，當(dāng)一條邊的權(quán)重小于該閾值則看作是無意義的，去除小于該閾值的邊。通過整理后會(huì)得到同時(shí)包含內(nèi)容和關(guān)鍵詞的集群聚類，選擇出現(xiàn)頻率最大的關(guān)鍵詞作為類名。

3.4 POHCUGO算法

POHCUGO算法如下：

4 POHCUGO在用戶偏好分析中的應(yīng)用

POHCUGO算法以互聯(lián)網(wǎng)用戶的搜索行為［23］為出發(fā)點(diǎn)，通過對(duì)用戶的搜索行為進(jìn)行挖掘，使用搜索關(guān)鍵詞作為類名，將用戶感覺是一致的信息聚合到一個(gè)類中。本文后續(xù)的實(shí)驗(yàn)將以某網(wǎng)站的真實(shí)app作為實(shí)例，把a(bǔ)pp的分類標(biāo)簽轉(zhuǎn)換為用戶關(guān)于標(biāo)簽的偏好。用戶對(duì)于app的行為分為三種：瀏覽、搜索和下載。用戶搜索的關(guān)鍵詞能夠詳細(xì)地代表其搜索目的，即可以認(rèn)為是用戶關(guān)于搜索關(guān)鍵詞的偏好，這種偏好可以由用戶對(duì)app的操作行為轉(zhuǎn)換得到。即互聯(lián)網(wǎng)用戶對(duì)于關(guān)鍵詞的偏好分可由以下公式所得：

由公式可以清楚地看出偏好分?jǐn)?shù)通過用戶的搜索、瀏覽和下載行為獲得，因?yàn)橛脩魧?duì)app的偏好與這三種操作行為密切相關(guān)，并且我們可以得到下載行為影響最強(qiáng)、其次是搜索、瀏覽最弱。用戶的主動(dòng)意圖可以由搜索關(guān)鍵詞很好的表示，這種比標(biāo)簽更為細(xì)致地搜索關(guān)鍵詞特征使得內(nèi)容展現(xiàn)出更細(xì)化的表示［24］，也因此更利于對(duì)用戶行為的偏好進(jìn)行分析挖掘，進(jìn)而能夠更好地針對(duì)每位用戶的需求提供符合個(gè)人偏好的服務(wù)。并且，根據(jù)挖掘用戶的行為可以為其展示內(nèi)容的聚類，此外同時(shí)融合用戶歷史的搜索行為進(jìn)行分析，不僅能夠得到用戶對(duì)內(nèi)容的偏好，還可轉(zhuǎn)換成對(duì)于搜索關(guān)鍵詞以及用戶對(duì)于關(guān)鍵詞下其他搜索內(nèi)容的偏好。

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

5.1 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文提出的POHCUGO算法的有效性，本文針對(duì)互聯(lián)網(wǎng)app聚類進(jìn)行了多次實(shí)驗(yàn)。本文的實(shí)驗(yàn)數(shù)據(jù)來自于某網(wǎng)站的真實(shí)app瀏覽日志數(shù)據(jù)信息，主要包含app的搜索、瀏覽、點(diǎn)擊和下載等相關(guān)數(shù)據(jù)，對(duì)于本文算法，有效的試驗(yàn)數(shù)據(jù)是app的搜索、點(diǎn)擊、下載相關(guān)信息，試驗(yàn)數(shù)據(jù)的具體如表1所列。

表1 app搜索日志

原始數(shù)據(jù)由用戶最近三個(gè)月的點(diǎn)擊信息、下載日志組成，且以日志的操作類型為標(biāo)準(zhǔn)對(duì)數(shù)據(jù)進(jìn)行篩選清理，只采用用戶關(guān)于app的點(diǎn)擊、下載日志的數(shù)據(jù)信息。通過以下幾點(diǎn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證：

1）測(cè)評(píng)聚合到一起的app在hot中的覆蓋率。2）判斷聚類所得到的搜索關(guān)鍵詞與類內(nèi)app是不是為同一app為原則計(jì)算算法的準(zhǔn)確率。

3）在準(zhǔn)確率和效率方面對(duì)傳統(tǒng)方法、普通多點(diǎn)合并加速（HCUGO）算法以及本文研究的POHCU?GO算法進(jìn)行比較，對(duì)本文算法的有效性進(jìn)行證明。

由于沒有很好的方式來評(píng)估標(biāo)記的精準(zhǔn)程度，故在本文通過人工盲評(píng)的形式評(píng)估該標(biāo)簽標(biāo)記算法的準(zhǔn)確程度。本文進(jìn)行了三次實(shí)驗(yàn)，均采用同一環(huán)境，通過對(duì)每輪算法的平均迭代時(shí)間和算法的迭代收斂輪數(shù)比較以完成POHCUGO算法的證明，其中實(shí)驗(yàn)數(shù)據(jù)量、環(huán)境及參數(shù)配置如下：

1）整理實(shí)驗(yàn)數(shù)據(jù)，最終計(jì)算是無向圖的節(jié)點(diǎn)數(shù)量是10w，其中關(guān)鍵詞節(jié)點(diǎn)數(shù)量是6w，app節(jié)點(diǎn)數(shù)量是4w，邊數(shù)量是240w。

2）算法是通過Graph分布式框架完成驗(yàn)證的，因此本文進(jìn)行實(shí)驗(yàn)的3種算法的提交參數(shù)均如下所示：worker數(shù)量30、每個(gè)worker內(nèi)存10G。本文對(duì)系統(tǒng)資源進(jìn)行限制進(jìn)而實(shí)現(xiàn)算法環(huán)境的統(tǒng)一。

3）把衰減因子的值均設(shè)置為0.96，將最小合并邊的權(quán)重設(shè)置為8。（參數(shù)信息由數(shù)據(jù)分析得到，取決于數(shù)據(jù)）

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

根據(jù)三次實(shí)驗(yàn)結(jié)果進(jìn)行分析，總結(jié)之后得到如圖5所示的算法的hot覆蓋率對(duì)比信息。

圖5 算法覆蓋率

對(duì)圖5進(jìn)行分析可得出傳統(tǒng)算法與HCUGO算法在覆蓋率上相差無幾，由于多變點(diǎn)問題使得二者對(duì)hot覆蓋率相對(duì)比較低。舉例說明，對(duì)于每日下載次數(shù)很多的twitter來說，它是特別火熱的社交app，由此也會(huì)帶動(dòng)其相關(guān)的twitter tools的app的下載次數(shù)，然而與twitter相比，這類tools下載熱度相對(duì)較低。即是在多邊點(diǎn)無向圖中權(quán)重中長(zhǎng)尾的邊在全部邊中屬于權(quán)重比較大的，但是這樣的邊會(huì)因?yàn)轭l繁衰減不斷降低其所附帶的數(shù)據(jù)信息，當(dāng)其不再有意義時(shí)不能被聚類。因此導(dǎo)致傳統(tǒng)算法和HCUGO算法在hot的覆蓋率相對(duì)比較低。而PO?HCUGO在分裂節(jié)點(diǎn)中避免了由于多邊點(diǎn)所帶來的消極影響。由實(shí)驗(yàn)結(jié)果可以很容易看出，POHCU?GO通過節(jié)點(diǎn)分裂使其在hot的覆蓋率方面比其他兩種算法高。

其次，對(duì)傳統(tǒng)算法、HCUGO算法和POHCUGO算法的準(zhǔn)確率方面進(jìn)行分析比較。在實(shí)驗(yàn)結(jié)果中分別隨機(jī)選取100個(gè)分類，并通過人工盲評(píng)方法評(píng)估算法的準(zhǔn)確性。評(píng)估結(jié)果如圖6所示，通過比較發(fā)現(xiàn)傳統(tǒng)算法［25］的精度與HCUGO算法［26］的準(zhǔn)確率分別為83%和82%，本文所提的POHCUGO算法以91%的準(zhǔn)確率顯然高于另外兩種算法。對(duì)此結(jié)果進(jìn)行研究，由于節(jié)點(diǎn)的分裂并行降低了邊權(quán)重的衰減輪數(shù)，也因此減低了邊的信息耗損率。通過對(duì)本次的實(shí)驗(yàn)結(jié)果進(jìn)行分析可得出本文研究的PO?HCUGO算法在準(zhǔn)確率上要優(yōu)于HCUGO算法和傳統(tǒng)算法。

圖6 算法準(zhǔn)確率

最后，根據(jù)比較3次實(shí)驗(yàn)結(jié)果的平均迭代時(shí)間、算法時(shí)間和迭代收斂輪數(shù)，分析算法的效率，三種算法消耗時(shí)間如表2所列。

表2 算法效率

對(duì)表2進(jìn)行分析可得出，算法的平均迭代時(shí)間大致一樣，由表格得到大部分時(shí)間花費(fèi)于算法迭代收斂輪數(shù)上，對(duì)于傳統(tǒng)算法而言，在每輪迭代時(shí)只對(duì)兩個(gè)節(jié)點(diǎn)進(jìn)行合并；HCUGO算法在每輪迭代時(shí)只能對(duì)多對(duì)不相鄰的節(jié)點(diǎn)進(jìn)行合并；而POHCUGO算法由于并行可以在每次合并多個(gè)節(jié)點(diǎn)，因此PO?HCUGO算法與其他兩種算法相比所用時(shí)間更少。通過實(shí)驗(yàn)結(jié)果可得到在算法效率上POHCUGO算法遠(yuǎn)高于HCUGO算法。

通過對(duì)傳統(tǒng)算法、HCUGO算法和本文提出的POHCUGO算法在準(zhǔn)確率、覆蓋率、效率上進(jìn)行了實(shí)驗(yàn)并對(duì)試驗(yàn)結(jié)果進(jìn)行分析比較，可以明顯得到本文所提出的POHCUGO算法更優(yōu)于傳統(tǒng)方法和HCUGO算法，從而也證明了POHCUGO算法的有效性。

6 結(jié)語(yǔ)

聚類是當(dāng)前數(shù)據(jù)挖掘范疇中不可分割的重要組成成分，并且已經(jīng)在多個(gè)領(lǐng)域［27］有實(shí)際成效。本文首先講述了無向圖層次聚類并進(jìn)而介紹其優(yōu)化算法POHCUGO算法。POHCUGO算法對(duì)高熱節(jié)執(zhí)行分裂，降低了由于衰減因子引起的消極作用，并且，算法通過節(jié)點(diǎn)并行的方法實(shí)現(xiàn)加速并優(yōu)化圖聚類的效果。最后通過用戶對(duì)于關(guān)鍵詞的偏好進(jìn)行聚類來表達(dá)其對(duì)搜索內(nèi)容的偏好，進(jìn)而完成用戶關(guān)于內(nèi)容的偏好分析。通過將傳統(tǒng)算法、HCUGO算法和本文研究的POHCUGO算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較，驗(yàn)證了本文算法的有效性。

然而，在對(duì)用戶搜索歷史進(jìn)行聚類時(shí)只是通過用戶的歷史搜索信息作為原始數(shù)據(jù)進(jìn)行挖掘用戶偏好，并未考慮時(shí)間維度所帶來的影響，因此在下一步研究時(shí)考慮加入時(shí)間維度的影響，通過在時(shí)間維度上研究用戶搜索行為的偏好進(jìn)行挖掘探索在時(shí)序上關(guān)于用戶搜索內(nèi)容的規(guī)律。