一種基于圖數據庫的虛擬身份關系挖掘算法

2020-07-14 00:47:38尹玉嬌張偉

軟件導刊 2020年1期

尹玉嬌張偉

摘要：基于虛擬身份的關系挖掘是關系挖掘的重要途徑，但虛擬身份存在一定的不真實性。鑒于此，將虛擬身份一一映射到真實身份，再針對真實身份進行關系挖掘，并采用圖數據庫存儲強關聯的關系數據。該關系挖掘算法包括3部分：首先基于公共場所卡口設備和審計設備采集到的日志數據，抽取手機終端MAC、卡口設備MAC及微信構建虛擬身份庫，將虛擬身份微信反向映射到真實身份手機終端MAC：然后找出單節點手機終端MAC在某段時間內的同行人作為一個關系團體，或者直接找出虛擬身份庫中微信對應映射到的手機終端MAC最大度數節點作為核心節點;再利用同行人分析算法找出該節點在某段時間內的同行節點作為一個關系團體。研究結果表明，相比單純基于虛擬身份的關系挖掘，基于圖數據庫的虛擬身份關系挖掘算法準確率可提高至100%。

關鍵詞：社交網絡;圖數據庫;虛擬身份;關系挖掘

DOI： 10. 11907/rjdk.191322

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312

文獻標識碼：A

文章編號：1672-7800（ 2020） 001-0117-06

0 引言

自沃爾瑪公司“啤酒和尿布”的潛在關聯關系被挖掘出來后，關聯規則挖掘逐漸進入人們的視野并受到關注。關聯規則起源于購物籃的物品搭配問題，最終目的是獲得事務集中各屬性間的關聯關系，獲得可信的強關聯規則，并應用這些規則服務于人類，如商店中物品的放置位置、電子商務中用戶的購物行為。

Agrawal等[1]最先提出關聯規則的概念，同時給出了相應的挖掘算法AIS，但其性能較差;隨后建立了項目集格空間理論，并依據上述兩個定理，提出了著名的Apriori算法，之后大部分學者基于經典Apriori算法進行算法改進研究。2015年邵文爽[2]針對傳統Apriori算法執行效率低、1/0負載大、算法冗余等缺陷提出了兩種改進算法，第一種優化是基于邏輯位運算，第二種優化是基于哈希表;崔妍等[3]提出了基于散列技術、基于劃分、基于采樣、FP增長等串行算法以及并行分布式算法，其中并行是基于多處理器進行的。

隨著數據量的增長，傳統關聯規則挖掘算法已經不能滿足大數據時代的生產和生活需要，于是出現了分布式、并行的關聯規則挖掘算法。MapReduce是一種流行的分布式并行計算模型，因其使用簡單、伸縮性好、自動負載均衡和自動容錯等優點，得到了廣泛應用，由此出現了基于Ma-pReduce的并行關聯規則挖掘算法?；贛apReduce的并行關聯規則挖掘算法主要基于磁盤訪問，降低了計算性能。隨著加州大學伯克利分校AMLab實驗室研發的用于大型數據快速處理的并行計算框架被提出，基于Spark的關聯規則挖掘逐漸受到人們的廣泛關注。

不論是傳統的關聯規則挖掘算法，改進的關聯規則挖掘算法，還是分布式的基于MapReduce和Spark的關聯規則挖掘算法，都是在傳統關聯規則挖掘算法Apriori.FP-growth、Eclat基礎上提出的，其實質仍然是兩個事物之間關聯關系的挖掘。

在關聯規則分析基礎上出現了關系挖掘。關系挖掘算法更加實用，有基于機器學習的方法和統計的方法，關系挖掘的范疇包括兩個事物之間的關聯關系和多個事物之間的關聯關系。姜麗莉[4]對傳統關聯規則挖掘算法進行了優化，算法借鑒元組ID傳播思想，對關系圖進行切分，對每一部分建立全局鍵值映射哈希表，通過哈希表，將表單挖掘出的項集進行連接，從而得到多關系間的頻繁項集。

隨著社交媒體的不斷普及，人們更多地在虛擬網絡中進行溝通和交流，出現了大量通過社交軟件進行注冊的賬號信息?；谔摂M身份的關系挖掘為社交關系挖掘提供了新的助力，通過識別多個屬于同一個現實用戶的所有虛擬身份信息，并將其合并到一起，最終生成一個虛擬身份庫。隨著網絡技術的快速發展，用于隱藏網絡用戶身份的技術手段和方法越來越多且更新速度較快，造成用戶身份識別特別困難[5]。基于數據挖掘的虛擬身份識別方法可以解決在線網站的身份識別問題。

目前，大部分虛擬身份關系挖掘是將虛擬身份對應轉換成現實世界中的真實身份。根據涉及領域不同，對應轉換成的對象也不同，而且大部分虛擬身份關系挖掘算法仍停留在理論階段。本文從公安部門構建虛擬身份庫的實際需求出發，提出了一種基于圖數據庫的虛擬身份關系挖掘算法G VIRM（A Virtual Identity Relation Mining AlgorithmBased on Craph Database）。該關系挖掘算法利用具有強實用性的同行人分析算法挖掘虛擬身份之間的關聯關系，并針對虛擬身份的不真實性，將虛擬身份一一映射到真實身份，然后針對真實身份進行關系挖掘。

1 相關工作

在關系挖掘之前最早出現的是關聯規則挖掘，關聯規則挖掘最初研究的是單純兩個事物之間的關聯關系，由于單純的關聯規則算法存在缺陷，便出現了關聯規則算法的優化算法。隨著大數據時代的到來，傳統關聯規則計算模式已經不能滿足大規模數據處理需求，于是出現了分布式大數據平臺，如Hadoop和Spark。目前，基于MapReduce計算模型的并行關聯規則挖掘算法大多是將Apriori、FP-Crowth和Eclat 3種經典算法向MapReduce計算模型遷移，實現并行計算。基本思路是：利用hadoop作為運行平臺，利用Hadoop的分布式文件系統HDFS進行大數據集的分布式存儲，將算法的輸入和輸出改造成MapReduce計算模型要求的<鍵，值>，將算法運行改造成map和re-duce兩個階段[6]。MapReduce是一種基于磁盤的分布式并行計算模型，但存在抽象層次低、僅支持Map和Reduce兩種操作、處理效率低、不適合迭代運算等缺點，而Spark是基于內存進行計算，克服了MapReduce的諸多缺點，具有抽象層次更高、效率更高、有迭代處理和內存計算的特性。OIU H[7]等在2014年提出了一種經典的基于SparkRDD計算模型的并行Apriori算法;FANC X[8]等在2016年提出了一種基于Spark的改進FP-growth并行算法IP-FP-growth，實現了將改進的PFP-growth算法移植到Spark計算模型上進行分布式計算。Apriori算法和FP-growth算法處理的事務數據格式是水平格式，而Eclat算法不一樣，是垂直格式。馮興杰等[9]提出一種基于Spark的并行Eclat算法即SPEclat，通過改變數據存儲格式，將數據按前綴進行分組劃分到不同的計算節點，壓縮數據的搜索空間，實現并行化計算。

本文虛擬身份庫是面向公安應用而構建，如圖1所示?；诠矆鏊目谠O備和審計設備采集日志數據，抽取卡口設備MAC、手機終端MAC、虛擬賬號微信等實體，以及卡口設備MAC和手機終端MAC、手機終端MAC和微信的關聯關系，利用圖數據庫進行實體和關系的存儲。

2.2 虛擬身份到真實身份的映射

要想準確識別虛擬身份或者定位虛擬身份團體，需要將虛擬身份定位到真實身份，其難度隨著虛擬身份種類的復雜性而增加。本文虛擬身份微信與手機終端MAC直接綁定，因此直接將微信賬號定位到手機終端MAC，這種情況下的轉換是一對一的，如圖2所示。

2.3 虛擬身份關系挖掘算法設計

將微信虛擬身份映射到手機終端MAC這一真實身份后，再基于手機終端MAC進行關系挖掘。一種情況是基于特定的某個手機終端MAC進行同行人分析，得到關系團體1;另一種情況是首先挖掘出虛擬身份庫中微信虛擬身份對應映射的手機終端MAC度數最大的節點作為核心節點，然后基于已經挖掘出來的核心節點，利用同行人分析算法找出其在某段時間內的同行人作為一個關系團體，得到關系團體2。虛擬身份關系挖掘算法設計如圖3所示。

同行人分析算法如圖4所示。其中，圓圈節點是核心節點，圖中總共出現了5個軌跡點，然后在每個軌跡點找出某段時間同出現的其它節點，如圖4中的菱形和長方形，其中長方形節點是在5個軌跡點都出現過的節點，即核心節點的關系團體。

2.4 算法描述及偽代碼實現

2.4.1 虛擬身份庫構建

輸入：從卡口設備和審計設備采集到的日志數據中抽取出卡口設備MAC、手機終端MAC、微信賬號實體，卡口設備MAC和手機終端MAC的關聯次數，手機終端MAC和微信賬號的關聯次數。

輸出：基于卡口設備MAC、手機終端MAC、微信賬號及其之間的關聯次數形成的虛擬身份庫。

算法：

Stepl：首先從數據庫中抽取出實體節點;

Step2：導入實體節點到圖數據庫;

Step3：導入實體節點之間的邊到圖數據庫;

Step4：判斷實體節點之間的邊是否出現過，如果出現過累積邊的權值加1。

其中創建節點和邊的偽代碼如下：

Node（“label"， name， real_name， stype）

Relationship（ nodel，“label”.node2， name， stype）

2.4.2 核心節點挖掘

輸入：由卡口設備MAC、手機終端MAC、微信及其之間的關聯次數形成的虛擬身份庫。

輸出：虛擬身份庫中微信對應映射的手機終端MAC度數最大的節點。

算法：

Stepl：設置初始微信對應映射的手機終端MAC度數最大節點的度為0;

Step2：搜索出虛擬身份庫中的所有節點;

Step3：判斷節點是否是手機終端MAC節點，如果是則記錄下該節點的度數，并搜索出該節點的所有孩子節點。判斷孩子節點是否是微信賬號，如果是則節點的度數減1，并與初始微信對應映射的度數最大的手機終端MAC節點相比較，取兩者中最大的作為當前手機終端MAC度數最大的節點;

Step4：不斷循環判斷其余所有手機終端MAC節點，保留最終手機終端MAC節點度數最大的作為核心節點。

核心節點挖掘偽代碼如下：

max_degree=0

real_name=null

flag=0

for nodel in nodes：

if nodel.label==mac：

flag=0

degree=graph.degree（ nodel）

for node2 in nodel.child：

if node2.label==wechat：

degree=degree-l

flag=l

if（ flag==l°ree>max_degree）：

max_degree=degree

real_name=nodel

2.4.3 關系團體挖掘

輸入：虛擬身份庫中的核心節點或者特定的虛擬身份映射后的手機終端MAC節點，統稱為節點A，以及特定的某段時間內卡口設備采集到的日志數據。

輸出：特定某段時間內節點A的關系團體。

算法：

Step1：搜索出特定某段時間內卡口設備采集到的日志數據;

Step2：按時間順序將日志數據進行排序;

Step3：找出節點A在該段時間內的軌跡，也即出現過的場所;

Step4：在每個軌跡點找出與節點A同出現的其它節點;

Step5：所有軌跡點做交集得出核心節點的關系團體。

按照時間先后順序搜索出節點A的軌跡，其中status是場所狀態，為1表示該場所在線，偽代碼如下：

track={}

for line in lines：

if（ status==l）：

track[ netbar]={}

track[netbar][‘equipment_longitude] =longitude

track[ netbar][‘equipment_latitude] =latitude

搜索每個軌跡點同出現的其它節點偽代碼如下：

for netbar in netbars：

select distinct （mobile_mac） from table where net-bar_wacode=netbar

所有軌跡點做交集得出核心節點的關系團體偽代碼如下所示，其中count是軌跡點的總數：

for i in range（ count）：

if（i_=0）：

continue

listl=colle[i]

list2=colle[i-l]

ans=list（ set（ listl） .intersection（ list2））

3 實驗與分析

3.1 實驗平臺及數據

本實驗平臺CPU 4核，內存8G，操作系統采用CentosMinial版，數據庫采用單機版Greenplum和圖數據庫Ne04j。實驗數據采用某市150 000條卡口設備日志數據和5 000條審計日志數據。

3.2 實驗結果

基于卡口設備MAC、手機終端MAC、微信及其關聯次數構建的虛擬身份庫如圖5所示。

虛擬身份到真實身份映射后，虛擬身份庫中核心節點和特定某個微信映射的手機終端MAC節點MAC值、度數、某段時間內的軌跡、關系團體總數如表1所示。

3.3 結果分析

實驗結果表明，由卡口設備MAC、手機終端MAC，微信等形成的網絡具有群聚現象，大部分節點會聚集在一個地方，不松散，這種現象由人類居住特點和人口密度決定。通過將虛擬身份映射到真實身份，增加了虛擬身份關系挖掘的準確性。隨著數據量的累積，核心節點的度數維持在66左右。在數據量達不到一定規模時，核心節點出現的場所過少，同行人節點過多。微信等虛擬身份對應映射到真實身份手機終端MAC節點后，特定的某個手機終端MAC節點或者核心節點軌跡非空，同行節點非空。本文同行人分析算法充分利用了時間和空間屬性，具有較強實用性。

4 結語

本文基于圖數據庫的虛擬身份關系挖掘算法通過將微信等虛擬身份映射為手機終端MAC等真實身份，進而將虛擬身份的關系挖掘問題轉換為真實身份的關系挖掘問題，提高了虛擬身份關系挖掘的準確性。并且，本文關系挖掘算法充分利用了時間和空間屬性，具有較強的實用性，能夠解決基于微信等虛擬身份的關系團體挖掘問題。后續研究可針對更為復雜的虛擬身份關系網絡進行身份識別和關系挖掘。

參考文獻：

[1] 周英，卓金武，卞月青.大數據挖掘系統方法與實例分析[M].北京：機械工業出版社，2016.

[2] 邵文爽.基于關聯規則挖掘Apriori算法的改進[D].沈陽：東北大學，2015.

[3] 崔妍，包志強.關聯規則挖掘綜述[J].計算機應用研究，2016，33 （2）.330-334.

[4]姜麗莉，黃承寧.多關系關聯規則挖掘在考勤數據分析中的應用[J].電腦知識與技術，2018，14（ 36）：3-4.

[5] 陳莎.基于大數據的互聯網虛擬身份關鍵技術研究與實現[D].北京：北京郵電大學，2015.

[6] 肖文，胡娟，周曉峰.基于MapReduce計算模型的并行關聯規則挖掘算法研究綜述[J].計算機應用研究，2018，35（1）：13-23.

[7]QIU H，CU R， YUAN C， et aI.YAFIM：a parallel frequent itemset min-ing algorithmWith Spark[C].Parallel&Distributed Processing Sym-posium Workshops.IEEE， 2014.

[8]FANG X. ZHANG G X. Optimization of parallel FP-growth algorithmhased on Spark [Jl. Modern Electronics Technique， 2016， 39 （8）： 9-13.

[9] 馮興杰，潘軒.基于Spark的并行Eclat算法[J].計算機應用研究，2019（1）：18-21.

[10] 邵健.基于數據挖掘的及物性和單賓語句典型性關系挖掘[J].漢語學習，2019（1），31-41.

[11]王敏，李萬春，扶彩霞，等.基于Apriori算法的戰術數據鏈層次關系挖掘[J].航天電子對抗，2018（6）：29-33.

[12] 江慶華，王亞民，湯在祥.基于生存分析模型挖掘HSPB1基因表達與放療敏感性關系研究[J].安徽醫科大學學報，2019，54（2）：261-266.

[13] 李嬌，曹暉，李倩.基于共現和關聯挖掘的人物關系圖構建過程[J].無線互聯科技，2019，16（1）：110-112.

[14]李有增，周全，蔣鴻玲.基于時空關聯的高校社會網絡關系挖掘方法研究[J].微電子學與計算機，2018，35（ 12）：137-140.

[15]唐佳麗.面向科技評審中專家回避的人物社會關系分析方法研究[D].南昌：華東交通大學，2016.

[16]邱文龍.網絡虛擬身份分析系統的研究與實現[D].北京：北京郵電大學，2015.

[17] 藍邵武.網絡虛擬身份關系的提取和分析[D]北京：北京郵電大學，2017.

[18] 閆洲.基于深度學習的多社交網絡中虛擬身份關聯技術研究[D].長沙：國防科技大學，2017.

[19] 韓浩明.圖數據庫系統研究綜述[J].計算機光盤軟件與應用，2014.