在大數(shù)據(jù)時代，通過對目標人物的軌跡、通信、社交、出行、網(wǎng)絡(luò)等多模態(tài)行為進行挖掘并建立人物畫像模型，并依托人物基礎(chǔ)特征和高層特征，實例化人物畫像，支撐有關(guān)部門分析人員全方位了解目標人物的行為、活動、狀態(tài)、基本屬性等信息，同時能夠基于人物畫像指導人物活動規(guī)律分析、人物能力分析、人物動向分析等應用。

圖1 某人物組織網(wǎng)絡(luò)示例

本文將重點就人物關(guān)聯(lián)關(guān)系挖掘及其關(guān)鍵技術(shù)進行分析。人物關(guān)聯(lián)關(guān)系挖掘是網(wǎng)絡(luò)關(guān)系挖掘中的重要一步，通過人物關(guān)聯(lián)關(guān)系挖掘，可以獲得關(guān)系網(wǎng)絡(luò)中的關(guān)鍵結(jié)點和關(guān)鍵路徑，進一步獲取更多的人物關(guān)聯(lián)關(guān)系信息。人物關(guān)聯(lián)關(guān)系挖掘包括通聯(lián)關(guān)系挖掘、人物群體關(guān)系挖掘、關(guān)系網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)以及關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵路徑發(fā)現(xiàn)。

圖2 人物關(guān)聯(lián)關(guān)系挖掘技術(shù)結(jié)構(gòu)

通聯(lián)關(guān)系挖掘

通過查找選定多個人物話單人物，對多人物之間的通聯(lián)關(guān)系建立網(wǎng)絡(luò)（如圖2），構(gòu)建人物之間的關(guān)系網(wǎng)絡(luò)，并計算話單人物間的親密值權(quán)重?；跇?gòu)建的關(guān)系網(wǎng)絡(luò)可以做以下統(tǒng)計分析挖掘：

圖3 多人物關(guān)系網(wǎng)絡(luò)示意圖

01關(guān)鍵節(jié)點發(fā)現(xiàn)

在構(gòu)建的關(guān)系網(wǎng)絡(luò)中，以用戶為節(jié)點，通過PageRank算法量化不同粒度網(wǎng)絡(luò)結(jié)構(gòu)中不同主體的地位，發(fā)掘關(guān)系網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，以發(fā)現(xiàn)活躍及高價值人物。

02最短路徑查找

在構(gòu)建的關(guān)系網(wǎng)絡(luò)中，選中兩個人物，發(fā)現(xiàn)兩個人物間的最短路徑，幫助分析人員快速了解人物間的關(guān)聯(lián)性。

03團體發(fā)現(xiàn)

在構(gòu)建的關(guān)系網(wǎng)絡(luò)中，選中多個人物，發(fā)現(xiàn)多人物的親密社區(qū)。通過社區(qū)發(fā)現(xiàn)算法將整個網(wǎng)絡(luò)中的人物劃分成若干個群體。發(fā)現(xiàn)潛藏在關(guān)系網(wǎng)絡(luò)中的未知的群體關(guān)系網(wǎng)絡(luò)。在關(guān)系網(wǎng)絡(luò)的關(guān)系類型、層級、強度挖掘基礎(chǔ)之上，將利用關(guān)聯(lián)分析技術(shù)，協(xié)同發(fā)現(xiàn)未知群體關(guān)系網(wǎng)絡(luò)，實現(xiàn)關(guān)鍵人物的檢測和群體性事件的預警與速報。

04搜索共同聯(lián)系人

根據(jù)已知的多個人物人物搜索其共同聯(lián)系人，從而分析人物之間的關(guān)聯(lián)性，發(fā)現(xiàn)隱藏的關(guān)系信息。

05通聯(lián)統(tǒng)計

選中某個人物可以查看其通訊錄以及相應的統(tǒng)計特征，例如通聯(lián)頻次（分時段、收發(fā)關(guān)系）、總時長、通聯(lián)關(guān)系分布、通聯(lián)時段（出入度）。

圖4 短信語義分析示意圖

人物群體關(guān)聯(lián)關(guān)系挖掘

人物群體規(guī)律采用統(tǒng)計分析和關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的方法來完成規(guī)律的挖掘。
采用Aprior算法進行關(guān)聯(lián)規(guī)則的挖掘。關(guān)聯(lián)規(guī)則反映一個事件和其它事件之間的依賴或關(guān)聯(lián)，關(guān)聯(lián)規(guī)則挖掘的目的就是找出數(shù)據(jù)中隱藏的關(guān)聯(lián)信息。關(guān)聯(lián)可分為頻繁項集關(guān)聯(lián)、因果關(guān)聯(lián)、時序關(guān)聯(lián)、數(shù)量關(guān)聯(lián)等。具體如下：

01頻繁項集

通過統(tǒng)計得到所有對象在記錄中協(xié)同出現(xiàn)的頻次得到最常出現(xiàn)的k-項集。
頻繁項集指的是在樣本數(shù)據(jù)集中頻繁出現(xiàn)的項的集合。如：在超市的交易系統(tǒng)中，記載了很多次交易，每一次交易的信息包括用戶購買的商品清單。

FP-Tree算法生成頻繁項集，步驟如下：

第一步：掃描事務(wù)數(shù)據(jù)庫，每項商品按頻數(shù)遞減排序，并刪除頻數(shù)小于最小支持度MinSup的項。

第二步：對于每一條記錄，按照第一步中的順序重新排序。

第三步：把第二步得到的各條記錄插入到FP-Tree中。

第四步：從FP-Tree中找出頻繁項。

第五步：對于每一個頻繁項從FP-Tree中找到所有的頻繁項結(jié)點，向上遍歷它的祖先結(jié)點，得到路徑；對于每一條路徑上的結(jié)點，其計數(shù)器都設(shè)置為當前遍歷頻繁項計數(shù)器的值；根據(jù)路徑上結(jié)點的計數(shù)計算支持度和置信度，將大于支持度和置信度閾值的項保留，得到前件。后件即為當前遍歷的頻繁項。

返回到第三步，遞歸迭代運行，直到遍歷完所有頻繁項。

02因果關(guān)聯(lián)

通過因果關(guān)聯(lián)分析，得到事件之間的因果關(guān)系，如威脅程度為一般是陣隊數(shù)量為1常在記錄中同時出現(xiàn)，但威脅程度為一般是陣隊數(shù)量為1的果。

03時序關(guān)聯(lián)

通過統(tǒng)計得到屬性取值之間時間先后情況。

04數(shù)量關(guān)聯(lián)

通過Aprior算法得到數(shù)值型屬性取值之間關(guān)聯(lián)情況。如陣隊數(shù)量的取值正相關(guān)于作戰(zhàn)單位總數(shù)。

Aprior算法 將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個步驟：

第一步通過迭代，篩選出所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集；

第二步利用頻繁項集構(gòu)造出滿足用戶最小置信度的規(guī)則。

關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)

關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)完成知識圖譜關(guān)系網(wǎng)絡(luò)中對網(wǎng)絡(luò)連通性和信息傳播有重要影響的結(jié)點。發(fā)現(xiàn)信息網(wǎng)絡(luò)中對網(wǎng)絡(luò)連通性和信息傳播有重要影響的結(jié)點。

01基于圖的關(guān)鍵結(jié)點發(fā)現(xiàn)

通過計算圖中結(jié)點的相關(guān)分析指標來發(fā)現(xiàn)圖中的關(guān)鍵結(jié)點。

緊密中心性：圖中某個結(jié)點到達其他結(jié)點的難易程度，也就是其他素有結(jié)點距離的平均值的倒數(shù)，即Cv=（|V|-1）/Σi≠vdvi。
介數(shù)中心性：圖中經(jīng)過某個結(jié)點的最短路徑數(shù)量占總路徑數(shù)量的比例，即Bv=Σi≠j,i≠v,j≠vgivj/gij。

02基于影響力的關(guān)鍵結(jié)點發(fā)現(xiàn)

如圖5所示，在異構(gòu)信息網(wǎng)絡(luò)中，關(guān)鍵結(jié)點可能是屬于某一角色。比如，在信息傳播的過程中，某些結(jié)點是信息傳播的起始結(jié)點，某些結(jié)點對信息傳播起到推波助瀾的作用，某些結(jié)點對信息傳播沒有任何實質(zhì)性影響，對于這種情況，可以將這三類結(jié)點分別對應三種不同的角色（A、B以及C）。因此，將關(guān)鍵結(jié)點發(fā)現(xiàn)的問題轉(zhuǎn)化為角色發(fā)現(xiàn)的問題，通過網(wǎng)絡(luò)中結(jié)點的角色發(fā)現(xiàn)進而找到關(guān)鍵結(jié)點。給定一個網(wǎng)絡(luò)，具有相似結(jié)構(gòu)的結(jié)點屬于同一角色。非監(jiān)督的學習方法RolX，自動地從網(wǎng)絡(luò)數(shù)據(jù)集中提取結(jié)構(gòu)化的角色。ReFeX的優(yōu)勢在于，它能夠處理大規(guī)模網(wǎng)絡(luò)并且能夠有效地捕捉到結(jié)點的區(qū)域性的特征。RolX大致由三個部分組成：特征提取、特征分組以及模型選擇。

特征提?。篟eFeX(Recursive Feature eXtraction）遞歸結(jié)合結(jié)點以及結(jié)點鄰居的特征，然后得到結(jié)點的區(qū)域性特征。
特征分組：將具有相似結(jié)構(gòu)化特征的結(jié)點分為一組。于是，我們采用軟聚類方法（每個結(jié)點均具有角色分布）對結(jié)點進行聚合。對結(jié)點特征矩陣采用SVD或者非負矩陣分解近似得到矩陣，滿足argminG,F?‖V-GF‖fro，s.t.G≥0，F(xiàn)≥0
模型選擇：通過最小化ε=∑i,j(Vi,jlogVi,j/(GF)i,j-Vi,j+(GF)i,j)，自動識別網(wǎng)絡(luò)中的角色數(shù)量。

圖5 結(jié)點角色結(jié)構(gòu)圖

03基于角色的關(guān)鍵結(jié)點發(fā)現(xiàn)

從信息傳播的角度看，網(wǎng)絡(luò)中結(jié)點的影響力越大，信息傳播的速度就會越快而且范圍越廣。因此，可從網(wǎng)絡(luò)重構(gòu)的角度審視影響力最大化問題，將網(wǎng)絡(luò)中關(guān)鍵結(jié)點發(fā)現(xiàn)的問題轉(zhuǎn)化為最小化重構(gòu)誤差的問題。

DRIM（Data Reconstruction for Influence Maximization）通過影響力最大化發(fā)現(xiàn)網(wǎng)絡(luò)中的關(guān)鍵結(jié)點。
基本定義如下：G=（V,E,T）表示當前網(wǎng)絡(luò)，?V表示頂點集合，?E表示邊集合，?T=[ti,j]n*n表示影響力傳播矩陣，其中ti,j表示影響力由結(jié)點i傳播到結(jié)點j的概率，即weight(i,j)/indegree(j)。

步驟如下：

第一步：構(gòu)建影響力矩陣X∈R^(N×N)，其中Xi∈R^(1×N)表示結(jié)點i ?對其它結(jié)點的影響力向量。結(jié)點i對結(jié)點j的影響力定義為：

其中，Nj={j1,j2,…jm}表示結(jié)點j的鄰居結(jié)點集合，?αj和?λj??分別是模型的參數(shù)。由此我們可以得到結(jié)點i的影響力向量fi=[f(i→1),f(i→2),…f(i→n)]，即為Xi。

第二步：從矩陣X中選擇K行所代表的結(jié)點作為影響力結(jié)點。問題轉(zhuǎn)化為最小化?J(A,β):

04基于節(jié)點收縮的關(guān)鍵節(jié)點確定

采用節(jié)點收縮方法，其原理（如圖4）如下：假設(shè)Vi是網(wǎng)絡(luò)G(V,E)中的一個節(jié)點，所謂節(jié)點收縮是指將節(jié)點Vi與其相鄰節(jié)點進行融合，即用一個新節(jié)點V’i來代替融合后的節(jié)點，且與節(jié)點V’i及其鄰節(jié)點相連的邊轉(zhuǎn)而與新節(jié)點V’i相連接，加權(quán)網(wǎng)絡(luò)中節(jié)點收縮后如果外圍節(jié)點與節(jié)點V’i及其鄰節(jié)點有多條路徑到達，新的連接以最短路徑形式收縮。

圖6節(jié)點收縮原理示意圖

05關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵路徑發(fā)現(xiàn)

關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵路徑發(fā)現(xiàn)完成支撐網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵路徑的挖掘。

在前文角色發(fā)現(xiàn)的基礎(chǔ)上，可以通過關(guān)鍵結(jié)點找到圖中的關(guān)鍵路徑?，F(xiàn)假設(shè)時態(tài)網(wǎng)絡(luò)中存在三類角色（A、B以及C），我們認為關(guān)鍵路徑是以角色為A的結(jié)點為關(guān)鍵路徑的初始結(jié)點，以B或者C為關(guān)鍵路徑的終止結(jié)點的一條路徑?；谏厦娴囊阎獥l件和假設(shè)，提出一種新的算法。已知一個時態(tài)網(wǎng)絡(luò)圖G(V,E)?，給定候選起始結(jié)點集合C和終止結(jié)點R集合，那么就可以完成斯坦納森林的構(gòu)建。通過斯坦納森林可知，葉子結(jié)點到根結(jié)點的路徑就是該圖的一條關(guān)鍵路徑。
關(guān)鍵路徑定義：時態(tài)網(wǎng)絡(luò)G(V,E)，V是頂點集合，邊集合E={(u,v,t)│u,v∈V,t∈R}?。在給定初始結(jié)點、終止結(jié)點集合的情況下，關(guān)鍵路徑就是使得總的時間代價cost(P│R)=∑e∈Pw(e)??最小時初始結(jié)點到終止結(jié)點的路徑。其中P表示時態(tài)路徑集合，w(e)表示權(quán)值函數(shù)。
基于隨機游走的關(guān)鍵路徑發(fā)現(xiàn)：擬采用隨機游走在網(wǎng)絡(luò)中進行隨機采樣，研究如何設(shè)計特定的模型對樣本進行統(tǒng)計處理與分析，并研究如何從處理后的樣本中發(fā)現(xiàn)網(wǎng)絡(luò)的關(guān)鍵路徑。
基于關(guān)鍵結(jié)點的關(guān)鍵路徑發(fā)現(xiàn)：關(guān)鍵結(jié)點出現(xiàn)在關(guān)鍵路徑中的可能性要高于出現(xiàn)在非關(guān)鍵路徑中的可能性。因此，擬借鑒上一部分對關(guān)鍵節(jié)點發(fā)現(xiàn)的探索，研究如何對某些包含關(guān)鍵結(jié)點的路徑進行分析，并研究如何使用特定模型判斷是否為關(guān)鍵路徑。

本文小結(jié)?

本文闡述的人物關(guān)聯(lián)關(guān)系挖掘的技術(shù)結(jié)構(gòu)主要涉及通聯(lián)關(guān)系挖掘、人物群體關(guān)系挖掘、關(guān)系網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)以及關(guān)聯(lián)網(wǎng)絡(luò)關(guān)鍵路徑發(fā)現(xiàn)，可應用于相關(guān)領(lǐng)域大規(guī)模知識圖譜自動化構(gòu)建與典型應用分析，相關(guān)技術(shù)成果已經(jīng)在達觀淵海知識圖譜平臺及相關(guān)項目中陸續(xù)轉(zhuǎn)化落地。

作者簡介

桂洪冠，達觀數(shù)據(jù)技術(shù)副總裁、聯(lián)合創(chuàng)始人、高級工程師，中國科學技術(shù)大學計算機碩士學位，中國計算機學會CCF會員，自然語言處理技術(shù)專家，首席數(shù)據(jù)官聯(lián)盟成員，蘇州相城市企業(yè)家智庫成員。在參與創(chuàng)辦達觀數(shù)據(jù)前，曾在騰訊文學、阿里巴巴、新浪微博等知名企業(yè)擔任數(shù)據(jù)挖掘高級技術(shù)管理工作。桂洪冠在數(shù)據(jù)技術(shù)領(lǐng)域擁有6項國家發(fā)明專利，在大數(shù)據(jù)架構(gòu)與核心算法以及文本智能處理等領(lǐng)域有深厚的積累和豐富的實戰(zhàn)經(jīng)驗。領(lǐng)導構(gòu)建了達觀基于知識和事件分析的認知智能平臺，完成了中電科集團研究所、中船重工集團研究所、深交所、華為等多個大型機構(gòu)的課題項目研究和工程化落地實踐。