基于通聯(lián)數(shù)據(jù)的人際關(guān)系網(wǎng)絡(luò)構(gòu)建與挖掘（網(wǎng)絡(luò)）

                        曲洋，王永劍，彭如香，姜國慶

         (公安部第三研究所信息網(wǎng)絡(luò)安全公安部重點實驗室，上海201400)

摘要：網(wǎng)絡(luò)通訊已然成為了信息時代最具代表性的產(chǎn)物，用戶之間的社交關(guān)系也變得越來越清晰、越來越重要。文章通過模擬通聯(lián)數(shù)據(jù)，利用中文分詞、自然語言處理等技術(shù)構(gòu)建反映人際關(guān)系的通聯(lián)好友網(wǎng)絡(luò)，并設(shè)計了一種適用于好友網(wǎng)絡(luò)人際關(guān)系預測的多分類算法。該算法首先利用層次聚類對原始數(shù)據(jù)進行聚類并結(jié)合人工干預，確定最終類的個數(shù)，從而有效避免通聯(lián)分組信息的多義詞性造成的類別數(shù)過多的問題，然后以通聯(lián)來往記錄等信息為基礎(chǔ)設(shè)計分類特征，最后利用在小樣本下，具有復雜決策邊界建模能力的支持向量機( Support VectorMachine，SVM)進行訓練，得到適用于人際關(guān)系預測的分類模型，并用于未知人際關(guān)系的預測。

關(guān)鍵詞：通聯(lián)日志；人際網(wǎng)絡(luò)：用戶串并；關(guān)系預測；SVM

中圖分類號：TP309 文章編號：1671-1122( 2016) 06-0068-060研究現(xiàn)狀

  在社會學、統(tǒng)計學和圖論領(lǐng)域中，針對人類社會網(wǎng)絡(luò)的研究由來已久。近年來，在網(wǎng)絡(luò)結(jié)構(gòu)、人類行為等各方面也取得了眾多的科研成果，部分學者重點就社交網(wǎng)絡(luò)節(jié)點的影響力進行了深入研究。

  韓毅等人通過分析社交網(wǎng)絡(luò)的鏈接結(jié)構(gòu)，設(shè)計了一種基于依賴關(guān)系的支撐結(jié)構(gòu)模型及計算方法并用于確定社交網(wǎng)絡(luò)中特定節(jié)點的影響力來源。此外，吳信東等人從網(wǎng)絡(luò)拓撲、用戶行為和交互信息等幾個方面總結(jié)了影響力分析的建模和度量方法。郭靜等人將社交網(wǎng)絡(luò)中用戶的歷史行為日志看作樣本，借鑒最大似然估計的思想對用戶間影響力學習問題建模；并在在線性閾值模型的框架下，提出一種影響力傳播權(quán)重的計算方法。鄧小龍等人提出了_一種新穎的基于軸節(jié)點選擇策略的大圖重要節(jié)點中介度近似計算方法和原型系統(tǒng)，并通過模擬數(shù)據(jù)和真實數(shù)據(jù)（包含一個連續(xù)六個月的真實社交網(wǎng)絡(luò)數(shù)據(jù)集）進行了驗證。在機器學習方法的應(yīng)用方面，曹玖新等人使用樸素貝葉斯NaiveBayes、邏輯回歸logisticsRregerssion等分類方法基于用戶屬性、社交關(guān)系和微博內(nèi)容三類綜合特征，對給定微博的用戶轉(zhuǎn)發(fā)行為進行預測。葉娜等人針對識別社交網(wǎng)絡(luò)用戶時存在的模式不一致問題，提出了基于分塊和二部圖的用戶識別算法。李勇軍等人以論文合作網(wǎng)絡(luò)為基礎(chǔ)，依據(jù)學生發(fā)表論文時通常與導師共同署名的現(xiàn)象，抽象出能夠反映導師一學生合作關(guān)系的特征，并提出基于最大熵模型的導師一學生關(guān)系識別算法。張玉清等人從基于行為特征、基于內(nèi)容、基于圖( Graph)、無監(jiān)督學習四個方面對近年來社交網(wǎng)絡(luò)中異常帳號檢測方案進行系統(tǒng)性的歸納總結(jié)，并對未來異常帳號檢測的研究趨勢進行了展望。

1基于通聯(lián)數(shù)據(jù)的人際關(guān)系網(wǎng)絡(luò)構(gòu)建

1.1實體抽取

    使用字典驅(qū)動方式對于結(jié)構(gòu)化的通聯(lián)數(shù)據(jù)進行實體抽取，實體抽取的原則是實體本身具有唯一性，并能夠唯一表現(xiàn)該實體的特征，實體本身不能是孤立的，要和其他實體存在關(guān)聯(lián)關(guān)系，實體屬性要依附于實體本身，可以補充實體的特征和關(guān)聯(lián)關(guān)系。通過隨機生成方式，模擬出—萬條數(shù)據(jù)樣例，并且從通聯(lián)數(shù)據(jù)本身的特點出發(fā)，選擇出需要的實體。

    1)用戶標識：模擬數(shù)據(jù)中隨機產(chǎn)生了四種可以當作實體的字段，包括手機號碼，郵箱，QQ賬號以及為模擬數(shù)據(jù)生成的用戶唯一標識。對于用戶名實體需要添加賬號類型的屬性，對帳號的類別加以區(qū)分。同時用戶標識會存在一些可串聯(lián)的關(guān)聯(lián)實體，例如，設(shè)備號、證件號、上網(wǎng)賬號、用戶名和IP地址。

    2)好友標識：通聯(lián)數(shù)據(jù)中關(guān)系好友的郵件信息用來唯一標識該好友，對于少量缺失情況標識實體需要補充記錄ID。此舉可避免同一節(jié)點對象由于采用不同標識而被視為不同的節(jié)點，進而保證人際關(guān)系網(wǎng)絡(luò)的完整性，抽取結(jié)果如表1所示。

1.2實體關(guān)系抽取

    實體間存在著緊密的連接關(guān)系，例如，證件號碼和上網(wǎng)賬號兩個實體間在規(guī)定時間區(qū)間內(nèi)是一對一的關(guān)系，一個證件號只能擁有唯一一個上網(wǎng)賬號，一個上網(wǎng)賬號只能依附于一個身份證號，同時上網(wǎng)賬號可以串聯(lián)出此賬號擁有的IP，通過IP可以關(guān)聯(lián)出此IP下所使用的設(shè)備情況，進一步完成對于用戶虛擬身份的串聯(lián)。通過用戶名這一個實體就可以很容易的構(gòu)建用戶的好友網(wǎng)絡(luò)，從而擴展出大的用戶關(guān)系網(wǎng)。對于實體間關(guān)系的描述主要從時間維度出發(fā)，而與好友的實體關(guān)系還可以通過不同的上傳工具進行分類，總體抽取結(jié)果如圖1所示。

2基于支持向量機的人際關(guān)系預測

    利用中文分詞、自然語言處理等文本挖掘技術(shù)，對通聯(lián)數(shù)據(jù)中能夠反映人與人之間人際關(guān)系的文本數(shù)據(jù)進行分析處理。首先提取諸如同事、朋友、同學、家人等反映人際關(guān)系的特定詞語，然后以此類詞語作為節(jié)點間邊的屬性來構(gòu)建人際關(guān)系網(wǎng)絡(luò)。其次以通聯(lián)記錄、短信來往記錄等信息為基礎(chǔ)設(shè)計分類特征。最后利用在小樣本下具有復雜決策邊界建模能力的支持向量機( Suppport Vector Machine,SVM)進行訓練得到適用于人際關(guān)系預測的分類模型，并用于未知關(guān)系的預測。

2.1人際關(guān)系預測模型的建立

    為了預測人際網(wǎng)絡(luò)中的兩個自然人是否存在親屬、朋友或其他關(guān)系，本文通過分析現(xiàn)有具有特定人際關(guān)系的用戶之間和無關(guān)系用戶之間的行為特征差異，設(shè)計幾種具有良好分類能力的屬性作為分類特征，進而構(gòu)建訓練樣本，并將是否存在關(guān)系及存在關(guān)系類別的判定轉(zhuǎn)換成數(shù)據(jù)挖掘中的分類問題。

2.1.1特征選擇

    1)共同好友數(shù)量占好友總數(shù)的比率CFR

    KOSSINETS等人通過研究在校大學生之間的熟人關(guān)系網(wǎng)絡(luò)，發(fā)現(xiàn)他們之間的共同熟人數(shù)目在很大程度上決定兩人之間是否存在聯(lián)系，即共同熟人數(shù)越多則兩人也為熟人的可能性就越大。顯然兩個自然人之間的共同好友數(shù)量越多，他們之間存在好友關(guān)系的可能性越大，相反則越小。

    但是單純以共同好友數(shù)量來衡量兩個自然人之間關(guān)系的緊密程度存在明顯的缺陷。假設(shè)用戶A與用戶B之間的共同好友數(shù)量為5，但用戶A的好友總數(shù)為30而用戶B的好友總數(shù)為100那么用戶A存在與其剩余的其他25個好友更為緊密的可能性，同樣用戶B同樣存在與其剩余的其他5個好友關(guān)系更為緊密的可能性，但是好友總數(shù)更多的用戶A，其可能性更大。為了避免此種可能性的影響，利用好友總數(shù)為基數(shù)，利用共同好友數(shù)量占各自好友總數(shù)的比例來衡量關(guān)系緊密程度，其計算公式如下所示。

2)平均通聯(lián)次數(shù)AR

AR是指在觀測數(shù)據(jù)范圍內(nèi)，兩個用戶之間通聯(lián)次數(shù)。分別統(tǒng)計出現(xiàn)有數(shù)據(jù)中人物之間的日平均通聯(lián)次數(shù)、周平均通聯(lián)次數(shù)及月平均通聯(lián)次數(shù)，在不同人際關(guān)系之間進行對比，取三者中分類能力最強的指標來表征平均通聯(lián)次數(shù)，如圖2所示，其計算公式如下所示。

    3)平均通聯(lián)時長ATR

    僅僅從用戶之間平均通聯(lián)次數(shù)，不足以區(qū)分用戶的關(guān)系緊密程度。例如，用戶A與用戶B之間的通聯(lián)次數(shù)與用戶B與用戶C之間的通聯(lián)次數(shù)相同，但用戶B與用戶C之間的通聯(lián)時長更長，顯然后者的關(guān)系更為緊密。所以有必要引入平均通聯(lián)時長作為分類特征，該特征指在觀測數(shù)據(jù)范圍內(nèi)，兩個用戶之間通聯(lián)的平均時長，單位為秒，如圖3所示。其計算公式如下所示。

4)平均消息交互次數(shù)AM

AM是指在觀測數(shù)據(jù)范圍內(nèi)，兩個用戶之間發(fā)送消息的次數(shù)。同樣分別統(tǒng)計出現(xiàn)有數(shù)據(jù)中人物之間消息交互的日平均、周平均及月平均次數(shù)，在不同人際關(guān)系之間進行對比，取三者中分類能力最強的的指標來表征平均消息交互次數(shù)，其計算公式如下所示。

    本文設(shè)計的4大類特征依人際關(guān)系的遠近呈規(guī)律性變化，即人際關(guān)系越緊密其通聯(lián)次數(shù)及通聯(lián)時長數(shù)值越大，而人際關(guān)系越疏遠其通聯(lián)次數(shù)及通聯(lián)時長數(shù)值越小。例如“家庭關(guān)系”之間通聯(lián)時長、通聯(lián)次數(shù)均遠遠大于其他兩類關(guān)系，且不同關(guān)系之間存在著一定的差異。可見，上訴4大類特征可以在一定程度上區(qū)分不同的人際關(guān)系，從而用于人際關(guān)系預測模型的訓練。

2.1.2訓練樣本的構(gòu)建

    獲取兩兩自然人之間的通聯(lián)記錄數(shù)據(jù)、消息信息及其他信息數(shù)據(jù)，分別依據(jù)2 .1.1節(jié)確立的計算方法進行計算得到共同好友數(shù)量、平均通聯(lián)次數(shù)、平均通聯(lián)時長、平均消息交互次數(shù)4個分類特征，得到初步的訓練樣本，數(shù)據(jù)形態(tài)如圖4所示。

    由于通聯(lián)日志對于關(guān)系表述不一致。例如，朋友、客人這兩類完全可以合并為同一類處理，將其命名為“朋友”類（合并前的類稱為原始類，合并后的大類稱為最終類）。這樣避免出現(xiàn)大量相近的類別，大大提高訓練樣本的質(zhì)量。

    本文對上述初步的訓練樣本運用層次聚類進行類的合并。處理原則如下：1）利用層次聚類的類別可控特點，人工干預類的合并，進一步提高類的質(zhì)量；2）合并后的最終類各樣本的特征值由合并類中所有原始類中各特征值的平均值計算得到。其處理結(jié)果如圖5所示，“朋友”、“客人，’被合并為同一類“朋友”類，“同事”、“員工”被合并為同一類“同事”類，其樣本值為各自原始類中樣本值的平均值。

2.2算法的正確率驗證

    本文中的人際關(guān)系預測只針對在通聯(lián)中已建立好友關(guān)系但是具體存在何種關(guān)系類型未知的情況作為預測，這是一種分類問題。在預測過程中，為保證預測算法的有效性，本文將采用K折交叉驗證評估方法。K折交叉驗證：將初始樣本分割成K個集合，其中一個單獨的子樣本作為驗證模型的數(shù)據(jù)，其他K-1個樣本作為訓練集。為交叉驗證需重復K次，每次針對一個子樣本驗證一次，并將平均K次的結(jié)果作為本算法的預測準確率。

    本文采用多種評價方法對本預測算法進行評價，包括精確率、召回率、及F-Measure。下面以二元分類問題的混淆矩陣來說明以上幾個評價指標的含義。

假設(shè)人際關(guān)系只有兩種：“朋友”，“親人’。

    從表2可知，在實際的預測中，任何一個類的預測可能有兩種結(jié)果，1）正確的預測；2）錯誤的預測。從而形成上訴：真正例( True Positive)，真負例(True Negative)，假負例( False Negative)及假正例(False Positive)的情況。同時，當真正例( True Positive)、真負例(True Negative)的比率較高時，就意味著模型整體的預測正確率就高，在混淆矩陣中表現(xiàn)為數(shù)值集中在矩陣的主對角線上。正確率、精確率、召回率和AUC的計算方法如下所示。

    1)正確率：反映所有類的預測正確率，即整體識別率。

    2)精確率：標記為正類的元組實際為正類的所占的百分比，在上例中表示為所有“朋友關(guān)系”被預測的比例，即

  4) 一個分類結(jié)果的好壞的特征在于其是否同時具有高敏感性和高特異性，而AUC恰好結(jié)合了兩者的特性。AUC是ROC曲線和兩坐標軸圍成的區(qū)域面積，該面積越大則表示預測準確率越高。AUC的基準值為0.5，即隨機猜測。

3實例分析

3.1基于層次聚類的訓練樣本的構(gòu)建

  模擬出通聯(lián)數(shù)據(jù)后，首先利用中文分詞、自然語言處理等技術(shù)提取通聯(lián)中的好友分組信息，然后以兩兩通聯(lián)好友為計算對象，分別計算兩個好友的共同好友數(shù)量占好友總數(shù)的比率CFR、平均通聯(lián)次數(shù)AR、平均通聯(lián)時長ATR及平均消息交互次數(shù)AM,得到‘初始訓練樣本”的4個分類特征。

    由于不同的通聯(lián)工具，其分組標識各不相同，并且用戶可自定義分組信息，這必將導致出現(xiàn)大量的分組，即出現(xiàn)大量的分類類別。如：“同學”，“同事”，“好友”，“員工”，“同事”等。顯然，“員工”和“同事”這兩個子類在一定程度上是可以合并處理的，從而避免在使用分類算法時，出現(xiàn)大量冗余、信息重疊的類別。本文采用層次聚類結(jié)合人工干預對“初始訓練樣本”進行聚類，合并冗余信息類，得到較為精準的“最終訓練樣本”。圖6顯示了對10個子類進行系統(tǒng)聚類的結(jié)果。

    由圖6可知，當聚類為3時，子類System Group：Friend。、同事、所有聯(lián)系人一號店在籍2號店員工、客人、員工及Favorite_8656150共6個子類被合并為l類，陌生人、ageha小惡魔被合并為1類，所有聯(lián)系人TIARA、所有聯(lián)系人家庭被合并為1類。

    聚類的結(jié)果較為合理，分類特征值較為相近的子類被合并為一個大類，所有聯(lián)系人TIARA、所有聯(lián)系人家庭是2個溝通交流較為頻繁的子類，而陌生人、ageha小惡魔為2個溝通頻較低2個子類。鑒于本文的研究對象，本文將系統(tǒng)聚類的結(jié)果進一步進行調(diào)整，合并為4大類，其結(jié)果如下：

3.2基于SVM的人際關(guān)系預測模型構(gòu)建

3.2.1人際關(guān)系預測模型訓練

    依據(jù)3.1節(jié)系統(tǒng)聚類的結(jié)果，對訓練樣本進行調(diào)整，合并子類，將合并類作為訓練樣本的類標號，選取70%的樣本作為訓練樣本，利用支持向量機SVM進行模型訓練，剩余30%的樣本用于模型的正確率檢驗。人際產(chǎn)關(guān)系預測模型的訓練過程如圖7所示。

如表4所示，基于本文現(xiàn)有的訓練數(shù)據(jù)，利用基于徑向基核函數(shù)的支持向量機進行人際關(guān)于預測模型的預測，在現(xiàn)有數(shù)據(jù)中，共出現(xiàn)4中人際關(guān)系類型，分別是“家庭關(guān)系”，“陌生關(guān)系”，“朋友關(guān)系”，“同事關(guān)系”，模型的整體識別率為62.5%。同時，“家庭關(guān)系”及“同事關(guān)系”的預測較為精準，尤其是“家庭關(guān)系”其精度為100%，而“陌生關(guān)系”及“朋友關(guān)系”的預測準確率較低，“陌生關(guān)系”的精度僅為25%。如圖8所示，混淆矩陣顯示了本文提出的人際關(guān)系預測模型各個類的情況。

4結(jié)束語

    本文以通聯(lián)數(shù)據(jù)為研究對象，首先基于郵箱等虛擬身份信息對疑似同一對象的用戶實體進行識別，并處理。其次采用中文分詞、自然語言處理等方法提取通聯(lián)數(shù)據(jù)中的分組信息，建立初步的人際關(guān)系網(wǎng)絡(luò)，并設(shè)計共同好友數(shù)量占好友總數(shù)的比率CFR、平均通聯(lián)次數(shù)AR等4個方面的特征，利用系統(tǒng)聚類，對訓練數(shù)據(jù)進行聚類并結(jié)合人工干預合確定最終類及訓練樣本，從而消除通聯(lián)分組信息的冗余，避免大量類的出現(xiàn)。然后在以上分析的基礎(chǔ)上，利用適合小樣本的支持向量機算法，進行模型訓練，得到適合通聯(lián)數(shù)據(jù)人際關(guān)系預測的分類模型。實驗結(jié)果表明，本算法能夠識別出網(wǎng)絡(luò)中的全部比例“家庭關(guān)系”，并能從整體上保證相對較高的準確率，具有一定的應(yīng)用價值。