基于HMM模型的網絡社區推薦技術

李培

（西安郵電大學計算機學院，陜西西安710121）

目前，隨著各類網絡應用的普及，在網絡環境下，具有類似興趣偏好、個人愛好等特征的人群聚集在一起，就其共同感興趣的問題進行互動，從而形成了具有歸屬感及認同感的群體即網絡社區。根據各類統計，目前各類網絡社區成為網民上網的主要關注點，而網絡社區具有主題鮮明以及互動性強等特點，可以滿足不同社區成員的信息獲取及表達，且社區成員又具有較高的凝聚力和平臺粘性。因此，個性化網絡社區推薦技術成為了各類應用平臺上滿足用戶個性化需求的核心技術[1-5]。

由于網絡社區相關數據具有海量、強噪音、實時變化性大等特點。因此，如何滿足網絡用戶高質量和實時性的社區推薦需求，使得用戶獲得準確的推薦服務成為備受關注的研究熱點。在網絡社區識別的基礎上，目前的社區推薦技術有基于群組間相似度的社區推薦算法、基于網絡拓撲結構根據個體間鏈接情況進行分析的決策樹算法以及通過對社會網絡進行群組聚類的社區推薦算法[6-8]等。

但是現有的網絡社區推薦算法普遍存在信息過載、準確度差以及擴展性差等問題，而大部分網絡社區推薦算法都是基于用戶的瀏覽及發帖等內容信息來確定用戶興趣和需求，沒有將用戶的主動行為和所在社區考慮在內[9-10]。文中則將用戶的個人行為考慮進來，并對其社區成員群體行為進行分析，再結合其瀏覽內容，更為準確地描述用戶興趣，從而有針對性的進行社區推薦。

1 基于HMM的模型建立

前期研究中已經證明了從一個較長時期上看，一個人的興趣是在不斷變化著的，但無論其興趣改變與否，一個人的興趣必定也能夠通過他的瀏覽行為表現出來，其瀏覽行為在很大程度上體現出用戶的真實興趣，并且更為精確的描述用戶興趣[11-12]。

按照相同的思路，本課題組認為在社會網絡中，具有相似興趣愛好、知識結構、思想觀念的人一般都會喜歡和希望參與同一類的社區，而具有這些內在相似點的人一般都會有類似的外在行為特征[13]。結合Web使用挖掘和內容挖掘的思想，提出了一種描述用戶訪問社區模式的挖掘模型，發現用戶訪問社區的遷移模式，反映用戶的訪問偏好。

本模型是將訪問社區的不同類型信息分為不同的興趣度來處理的，也就是建立在訪問方式不同、感興趣的社區不同的推推薦基礎上的。

圖1顯示了本課題所提出的用戶訪問社區的遷移模式挖掘模型。

圖1 用戶訪問社區遷移模式挖掘模型

該模型中的涉及到的相關概念及定義：

定義1訪問社區事件：我們將用戶訪問某個社區的事件定義為其訪問社區事件，其中包括：瀏覽信息和發表信息（包含發起新的主題討論和參與已有主題討論），但需要標記訪問類型，即瀏覽、發帖還是跟帖。

定義2：訪問社區序列：我們將采集的該用戶訪問社區事件的記錄，按發生時間的升序排列，稱為訪問社區序列。

定義3：用戶訪問社區序列：給定一個用戶訪問序列，如果將這些序列中的每個頁面替換成它所屬于的社區表示，連續相同的內容合并，那么替換后的這個序列就是用戶訪問社區序列。

定義4：用戶訪問社區序列遷移模式：該用戶頻繁出現的訪問社區序列就是用戶訪問社區序列遷移模式。

在該模型的基礎上進行分析的步驟如下：

第一步：收集Web信息，也就是將用戶訪問過的Web頁面收集起來，由于Web頁面中含有大量的無關信息，先要對其進行除雜的工作，保留其能夠反映用戶訪問社區內容的有用信息。之后，從中分析該用戶訪問社區事件中的參與類型，作為反映用戶社區興趣度的衡量指標。在收集Web信息的同時，為了序列要求的需求，要加入頁面的時間屬性，即用戶訪問社區時間。

第二步：頁面表示，這一步的工作是指將收集到的web頁面內容轉化為我們所需要的社區信息，即建立用戶訪問頁面和用戶訪問社區之間的關聯。具體實現是將具體的Web訪問頁面進行處理，即發現該頁面內容所屬的社區，進而將該頁面用用社區名稱表示。

第三步：構造訪問頁面序列庫，這一步的構造工作是指將采集到的符合要求并按照要求表示好的頁面按其時間屬性的依照升序排列，再根據指定的時間周期將整個序列進行分割，將其變成訪問序列集。

第四步：引入隱馬爾科夫模型，這是關鍵的一步，目的是為了完成把上一步得到用戶訪問頁面序列轉換為用戶訪問的社區序列，并最終實現得到預測用戶未來感興趣社區的目的。最終實現為其他相關用戶提供網絡社區推薦的目標。

2 基于HMM模型的用戶訪問社區序列

本文的關鍵性工作就是引入隱馬爾科夫模型，最終形成用戶訪問社區序列，進行用戶訪問社區工作的預測并完成網絡社區推薦的目標。

文中最終得到的用戶訪問社區序列是用社區名稱來表示的，從而用戶訪問社區序列反映了用戶感興趣的社區轉移關系。下文中的用戶訪問社區序列會按照下面的公式（1）進行描述：

這里ei∈E，1≤i≤m，ei.community表示頁面ei所屬于的社區名稱，ei.time表示頁面ei采集到的時間，ei.interest表示頁面ei的興趣度。

根據以上定義，確定了對于一個給定的用戶訪問頁面序列，只需將該序列中的每個頁面轉換為其對應的社區名稱表示，那么轉換后得到的序列就是用戶訪問社區序列。

同時，在分析研究的過程會發現頁面文檔本身具有多主題性，也就是一個頁面可能屬于多個社區，就是平時在社區發帖中可以將一個帖子發在相關的幾個社區當中，同時，一個頁面的內容可能會在多個社區中見到，因為要想全面真實的反映該頁面文檔所屬社區，應該考慮到其多主題的歸屬特點，從而能夠更加真實準確地反映用戶訪問社區時的興趣所在以及用戶訪問社區時的轉移特性。所以，從用戶訪問頁面序列到訪問社區序列的轉換問題。適合采用隱馬爾可夫模型即HMM模型來解決[14]。

一般來說，社區個數是可數的，而本文中用社區名稱來代表社區，那么，我們可以假設有N個社區名稱，而正如我們在不同社區中所見到的，每個社區中包含1到n個頁面，同時，一個頁面可以輸入1到n個社區，那么社區和其所包含的頁面之間關系的描述可以采用一組概率分布來表示。結合隱馬爾科夫模型的特點，文中將訪問頁面序列視為可以觀察到的觀察值序列，而各個頁面所屬的社區也為已知，利用隱馬爾科夫模型就可以獲得當面觀察到的用戶訪問頁面序列對應的用戶訪問社區序列。

隱馬爾可夫模型是由兩個隨機變量序列組成的模型，其中一個隨機變量序列是觀察不到的馬爾可夫鏈，稱為馬爾可夫鏈；另一個隨機變量序列是可以觀察到的隨機序列，稱為其觀察鏈[15]。

用隱馬爾科夫模型來構造用戶訪問社區序列，構造過程如下：

首先，將用戶訪問社區的過程可以看作是一個隨機過程{Xn}，其中，若當前瀏覽的社區為i，下一個瀏覽社區即為j，它們之間的條件概率為Pi，j=P（i|j），符合一階Markov鏈的定義。也就說假定用戶當前瀏覽的社區是Ci，同時，前期已經瀏覽了社區Cin-1，…，Ci0，那么下一個瀏覽的社區j的條件概率Pij（k）就取決于社區類可以用公式（2）表示如下：

然后，可以用一個五元組=（C，P，A，B，Y）表示社區訪問序列，其中，C是用戶所有可能訪問的社區集合，P是用戶訪問的所有頁面的集合，A是社區到社區的轉移概率，B是在某一狀態下用戶訪問頁面隸屬于該社區的概率，Ψ是初始狀態的選擇概率。

基于上述定義，對于用戶訪問的某個社區節點Cj，屬于該社區節點的頁面集合P′與該節點之間的概率分布可用表示，就得到了隱馬爾科夫模型中狀態節點觀測序列中的概率值。

同時，我們可以計算得到每個社區節點Cj與該社區對應主題Mj間的相似度值，見公式（3）。

最終，只需要前面的基礎上對公式進行歸一化處理后的取值便是的值。

基于以上數據準備，結合隱馬爾科夫模型的定義，可以建立針對網絡用戶社區訪問的HMM模型，用O=O1，O2，…，OT來表示用戶訪問序列，用λ=（A，B，Ψ）來構造隱馬爾科夫模型，借助

在此，借鑒隱馬爾可夫模型中的解碼問題的描述，即己知用戶訪問序列O=O1，O2，…，OT和模型λ=(A，B，π)，借助Viterbi算法進行序列選擇，得到最能輔助觀察的用戶訪問社區序列。Q*=q1*，q2*，…，qT*，其中，Q*為具有訪問社區序列的最大概率。

3 基于序列模式挖掘的用戶訪問社區模式發現

采用HMM模型得到網絡用戶訪問社區序列后，需要對其生成序列進行數據挖掘額，從而得到其訪問模式。在本研究中的序列數據從組織到處理都將時間因素考慮其中，也就是在序列發掘把時間屬性加入到了關聯模型當中，那么也就是在考慮數據之間關聯特征時考慮到了時間的因素，處理事物序列時時考慮到了時間的先后次序。因此，前期得到的訪問序列都是具有時間特征的。并且可以從中觀察到數據隨時間變化的趨勢[16-19]。

因此，對該序列進行挖掘后得到的是時間序列共用模式，既反映了用戶訪問網絡社區序列中最具可能性的訪問模式，同時，也對于其他具有類似訪問模式的用戶，后續對網絡社區的訪問具有指導作用，也就是可以通過適當的處理和比較對未來出現的情況進行一定程度的預測。

針對網絡用戶社區訪問序列的特征，在引入時間屬性的序列模式挖掘算法中，考慮到在GSP算法中，引入了時間約束、滑動時間窗技術，增加了掃描的約束條件，有效地減少了需要掃描的候選序列的數量，同時還克服了基本序列模型的局限性，更切合實際，減少多余的無用模式的產生。另外，GSP利用哈希樹來存儲候選序列，減少了需要掃描的序列數量。選取了GSP算法作為序列模式挖掘算法。

具體步驟如下：

1）獲取網絡用戶訪問頁面，形成用戶訪問頁面序列。

2）標記該頁面所屬社區，將用戶訪問頁面序列轉化為用戶訪問社區序列。

3）用GSP算法處理訪問社區序列得到頻繁訪問社區序列。

①掃描用戶訪問社區序列數據庫，得到長度為1的用戶訪問社區序列模式L1，作為初始的種子集。

②根據長度為i的種子集Li，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然后掃描用戶訪問社區序列數據庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集。

注：產生候選序列模式主要分連接階段和修切階段兩步完成，可查看相關文獻，在這里就不贅述了。

③重復第二步，直到沒有新的序列模式或新的候選序列模式產生為止。

4）在上述基礎上進行分析，從而得到訪問社區隨時間推移的訪問模式。

最終，得到這些訪問模式就是研究的目的即用戶訪問社區遷移模式，也就是對相應客戶形成了網絡社區的訪問推薦。

4 分析驗證

對于上述的理論分析，我們采用對實際獲取的網絡用戶數據進行處理分析的方法來驗證其正確性。

具體采用的實驗詩句是使用抓包程序對于實驗室內部用戶3個月的網絡訪問數據進行獲取，考慮到數據量過大，同時，結合后期分析處理方便，提取其各自瀏覽校園BBS論壇的頁面信息，同時按照論壇社區劃分進行標記，結合時間因素得到頻繁訪問序列。

處理結果如表1所示。訪問ID表示用戶的標識符。

表1 用戶訪問社區序列挖掘的結果

經過基于HMM模型的數據處理，我們得到了用戶訪問網絡社區的序列，并把這些序列構成為序列庫，進一步從中挖掘中用戶訪問社區遷移序列。

具體實現時，將GSP算法運行時的最小支持度可分別設置為3、4、5時，算法執行結果如表2所示。

表2 用戶訪問社區遷移序列

挖掘出的用戶訪問社區遷移序列表示在所有用戶訪問興趣序列中，至少有4天的時間用戶在Web上都有這樣一個訪問路線：軍事→經濟→環境→計算機。該序列模式挖掘出來的結果反映了普遍的網絡用戶對訪問社區的選擇。

同時，針對該訓練結果在實驗室內部做了測試分析，評估本文中提出社區推薦算法的性能，定義算法精確度：

精確度=用戶采納推薦數/系統推薦社區總數。

考慮到用戶的喜好是主觀的，不能提供精確的定量分析，內部測試該算法的精確度為0.8左右，供大家參考。

事實證明，按照按社區訪問序列進行社區推薦，得到大家的普遍認可。進一步證明該方法在進行網絡社區推薦方面是能起到一定效果的。

5 結束語

網絡上的資源如此眾多，在進行上網瀏覽時能夠得到有效的推薦是非常必須的一項服務。我們的研究把目前熱門的網絡社區作為研究的對象，同時結合HMM模型進行序列模式的挖掘，最終得到了對網絡社區推薦方案。該方法引入了具有時間屬性的序列模式數據挖掘，與現有的網絡社區推薦相比可以說是一個嘗試，更是一個探索，也是一個創新。目前采用的GSP算法在實驗階段序列模式長度較短的應用時效率不錯，但該算法在序列模式長度較長時就不易處理，還需要對該算法進行改進。總之，我們還會繼續研究下去，在網絡用戶進行網絡訪問時提供更有針對性，更加符合需求的社區推薦，減少上網的垃圾時間，提高學習生活及工作的效率，更多更好的享受網絡資源的豐富。

參考文獻：

[1]王國霞，劉賀平.個性化推薦系統綜述[J].計算機工程與應用，2012，48（7）:66-76.

[2]Linyuan Lü，Matú? Medo，et al.Recommender systems[J].Physics Reports，2012，519（1）:1-49.

[3]李慧，胡云，施珺.社會網絡環境下的協同推薦方法[J].計算機應用，2013，33（11）:3067-3070.

[4]趙宇翔，范哲，朱慶華.用戶生成內容（UGC）概念解析及研究進展[J].中國圖書館學報，2012，38（5）:68-81.

[5]王洪福，李懷龍，張家年.博客資源數據挖掘研究現狀 [J].電腦知識與技術，2013，9（12）:2771-2773.

[6]趙亞楠，董晶，董佳梁.基于社會化標注的博客標簽推薦方法[J].計算機工程與設計，2012，33（12）:4609-4613.

[7]熊正理，姜文君，王國軍.基于用戶緊密度的在線社會網絡社區發現算法[J].計算機工程，2013，39（8）:50-54.

[8]林友芳，王天宇，唐銳，等.一種有效的社會網絡社區發現模型和算法[J].計算機研究與發展.2012，49（2）:337-345.

[9]黃發良，肖南峰.網絡社區發現的粒子群優化算法[J].控制理論與應用，2011，28（9）:1135-1140.

[10]金弟，劉杰，楊博，等.局部搜索與遺傳算法結合的大規模復雜網絡社區探測[J].自動化學報，2011，37（7）:873-882.

[11]錢付蘭，李啟龍.結合全局與雙重局部信息的社交推薦[J].計算機科學，2016，43（2）:57-59.

[12]蔣勝，王忠群，修宇，等.基于動態社會行為和用戶背景的協同推薦方法[J].計算機科學，2015，42（3）:252-255.

[13]王玙，高琳.基于社交圈的在線社交網絡朋友推薦算法[J].計算機學報，2014，37（4）:801-808.

[14]Ahmad A.Kardan，Mahnaz Ebrahimi.A novel approach to hybrid recommendation systems based on association rules mining for content recommendation in asynchronous discussion groups[J].Information Sciences，2013，219（219）:93-110.

[15]Alejandro Bellogín，Iván Cantador，Pablo Castells.A comparative study of heterogeneous item recommendations in social systems[J].Information Sciences，2013（221）:142-169.

[16]Walter Carrer-Neto，María Luisa Hernández-Al?caraz，Rafael Valencia-García，Francisco García-Sánchez.Social knowledge-based recommender system.Application to the movies domain[J].Ex?pert Systems With Applications，2012，39（12）:10 990-11 000.

[17]穆靜，陳芳，王長元.人臉面部表情圖像的隱馬爾科夫建模及情感識別[J].西安工業大學學報，2015（9）:705-709.

[18]馬恒，杜慶偉.社區模型機會網絡路由研究[J].電子科技，2013（5）:117-121.

[19]劉明偉，張曉濱，楊東山.移動環境下多情景源用戶情景序列的提取[J].西安工程大學學報，2015（6）:746-750.