基于異構信息網絡的假幣犯罪信息分析系統①

陳貞虹, 李 慧, 許舒人, 葉 丹

1(中國科學院大學, 北京 100049)2(中國科學院軟件研究所 軟件工程技術研究開發中心, 北京 100190)

基于異構信息網絡的假幣犯罪信息分析系統①

陳貞虹1,2, 李 慧2, 許舒人2, 葉 丹2

1(中國科學院大學, 北京 100049)2(中國科學院軟件研究所 軟件工程技術研究開發中心, 北京 100190)

傳統的犯罪查詢的查詢條件是文本信息, 查詢結果是有序的文檔列表, 這種方式無法展示結果之間的關系. 基于異構信息網絡以信息網絡的形式重構假幣犯罪信息數據, 構建了假幣犯罪信息網絡, 使用人名消歧的技術建立假幣犯罪信息網絡中嫌疑人之間的關系, 并使用排序學習方法研究假幣犯罪信息網絡中的節點相關性問題, 設計并實現了假幣犯罪信息分析系統, 通過以實體對象為查詢項和網絡圖為查詢結果的方式解決假幣犯罪數據的查詢問題.

異構信息網絡; 元路徑; 犯罪數據挖掘; 人名消歧; 排序學習

1 引言

隨著犯罪行為的智能化和高科技化, 犯罪人員的組織化和職業化趨勢也越來越明顯, 假幣犯罪發案數呈現增長態勢, 犯罪規模不斷升級, 假幣犯罪有產業化和團伙化的特點. 傳統的犯罪查詢的查詢條件是一段文本, 查詢結果是有序的文檔列表. 對于假幣犯罪信息分析來說, 這種查詢方式無法展示查詢結果之間的關系, 對于具有團伙作案特性的假幣犯罪來說, 這種查詢方式并不適合. 本文采用以實體對象為查詢項,網絡圖為查詢結果的方式解決假幣犯罪分析中數據查詢問題, 幫助警員分析假幣犯罪信息, 尋找破案線索.

為了提供更加高效的假幣犯罪信息查詢, 本文對原始假幣犯罪數據進行重構, 建立假幣犯罪信息網絡,基于假幣犯罪信息網絡研究假幣犯罪信息的查詢分析與可視化. 隨著信息網絡結構和關系復雜化的發展,一個信息網絡內部的會有多種類型的節點, 節點之間的關系也會呈現出多樣化的趨勢, 為了區別單一同構的信息網絡, 韓家煒等學者提出將此種信息網絡稱為異構信息網絡[1]. 與同構信息網絡相比, 存在多種節點和關系類型的異構信息網絡模型更加適合含有三種關鍵數據類型, 即案件、嫌疑人和假幣的假幣犯罪數據. 因此本文基于異構信息網絡建立假幣犯罪信息網絡模型, 研究了嫌疑人姓名消歧和假幣犯罪信息相關性分析兩項關鍵技術, 并在此基礎上設計和實現了假幣犯罪信息分析系統.

2 相關工作

本文基于異構信息網絡以信息網絡的形式重構假幣犯罪數據, 構建了假幣犯罪信息網絡, 使用人名消歧的技術建立假幣犯罪信息網絡中嫌疑人之間的關系,并使用排序學習方法研究假幣犯罪信息網絡中的節點相關性問題. 因此, 本節從異構信息網絡、人名消歧以及排序學習三個方面介紹本文的相關工作.

2.1 異構信息網絡

網絡分析的研究已經從單一的網絡結構逐漸向異構網絡結構發展, 并成為新的研究熱點, 早期的異構信息的研究包括RankClus[1]和NetClus[2]. 但是RankClus針對的是只有兩種節點類型的異構信息網絡,而NetClus是基于星形異構信息網絡的研究, 在應用上都有一定的局限性. 隨后Yizhou Sun提出用元路徑[3]表示異構信息網絡豐富的語義信息, 同時還定義了一種新的基于元路徑的相似性測量方法PathSim[3], 研究異構信息網絡中同種對象之間的相似性. 此后有很多異構信息網絡的研究都基于元路徑展開. 文獻[4]在學術研究網絡中基于異構信息網絡的元路徑提取網絡拓撲特征預測學者之后的合作關系. 綜上, 異構信息網絡的元路徑分析方法是應用最廣泛的分析方法, 因此本文選用基于元路徑的分析方法研究基于異構信息網絡構建的假幣犯罪信息網絡.

2.2 人名消歧

人名消歧的研究中應用較為廣泛的是基于聚類的人名消歧. 基于聚類的人名消歧主要使用人物的屬性信息進行聚類, 有效的人物屬性可以提高聚類的結果的準確性. 基于聚類的人名消歧中的重要問題是如何確定類的個數, 文獻[5,6]采用交叉驗證、排列檢測、重采樣以及懲罰似然等方法來確定類的個數. 此外, 文獻[7,8]采用了自底向上的凝聚式層次聚類方法, 能夠不事先確定簇的個數. 本文采用自底向上的凝聚式層次聚類方法解決嫌疑人姓名消歧問題.

2.3 排序學習

排序學習方法是在信息檢索問題中, 利用機器學習的方法, 基于特征集合, 自動學習得到用于檢索的最終的排序函數. 已有的排序學習算法可以根據訓練樣例的不同分為三類: Pointwise、Pairwise 和Listwise方法. Pointwise 方法, 如Pranking with ranking 算法[9],采用一個查詢對應的單一文檔作為訓練樣例; Pairwise方法, 如Ranking SVM算法[10,11], 采用查詢對應的文檔對作為訓練樣例; 而Listwise 方法, 如ListNet 算法[12], 采用查詢對應的文檔序列作為訓練樣例. 已有研究表明, 一般來說Pairwise 和Listwise 方法優于Pointwise 方法[13,14]. 由于Listwise 方法的算法復雜度太高, 本文選用應用更為成熟的Pairwise方法中的Ranking SVM算法.

3 假幣犯罪信息網絡模型

為了給假幣犯罪數據提供網絡化的查詢方式, 本文基于異構信息網絡建立假幣犯罪信息網絡模型.

3.1 相關定義

定義1. 信息網絡[3](Information network): 信息網絡被定義為有向圖G = 〈 V, E 〉的形式, 有一個對象類型映射函數φ∶V→A和一個鏈接類型映射函數φ∶E→R, 即每個對象v∈V屬于一個特定的對象類型φ(v)∈A, 每一個關系e∈E屬于特定的關系類型φ(e)∈R. 當對象類型|A|〉1或關系類型|R|〉1時, 該信息網絡稱為異構信息網絡, 否則為同構信息網絡.

為了明確異構信息網絡中的對象類型和關系類型,使用網絡模式來描述異構信息網絡的元結構.

定義2. 網絡模式[3](Network schema): 在異構信息網絡G = (V, E)中, 有對象類型映射φ:V→A和鏈接類型映射φ:E→R, 網絡模式是在對象類型 A上定義的有向圖, 邊為來自R的關系, 表示為TG=(A,R).

定義 3. 元路徑[3](Meta-path): 元路徑P是一條定義在網絡模式圖TG=(A,R) 上的路徑, 表示為它定義了對象類型Al和Al+1之間的復合關系其中o表示關系的復合操作.

元路徑描述了網絡模式中兩類對象之間的連接路徑, 表示兩類節點在元層次上存在的關系, 不同的元路徑代表了對象類型之間可以通過不同的節點類型和關系建立不同的關系.

3.2 假幣犯罪信息網絡

定義4. 假幣犯罪信息網絡: 假幣犯罪信息網絡是異構信息網絡的實例, 被定義為有向圖G = 〈 V, E 〉的形式, 有一個對象類型映射函數φ:V→A和一個關系類型映射函數φ:E→R, 其中節點類型A={Case, Person, Money}, 即案件(Case, C), 嫌疑人(Person, P)和假幣(Money, M)三種對象, 關系類型R={ involve, involved in, related by, identical, similar},六種關系類型描述如下:

① Involve: 指的是該案件所抓獲的犯罪嫌疑人;

② Involved in: 指的是該犯罪嫌疑人所涉及的案件;

③ Relate: 指的是在一個案件中所繳獲的假幣;

④ Related by: 指的是該假幣是在哪一個案件當中被繳獲的;

⑤ Identical: 兩條同名嫌疑人記錄指向同一嫌疑人;

⑥ Similar: 通過已有假幣相似度分析程序計算相似度, 并建立關聯關系.

圖1 假幣犯罪信息網絡的網絡模式

根據定義4, 假幣犯罪信息網絡的網絡模式如圖1所示. 基于假幣犯罪信息網絡的網絡模式, 假幣犯罪信息網絡的兩條元路徑實例如圖2所示, 其中元路徑嫌疑人—案件—嫌疑人(PCP)表示人和人之間通過參與了相同的案件建立了一條路徑, 路徑中包括人和案件之間的“involved in”關系以及案件和人之間“involve”關系. 另一條元路徑案件—假幣—假幣—案件(CMMC)表示兩個案件之間通過關聯了非常相似的的假幣建立了一條路徑, 路徑中包括案件和假幣之間的“relate”關系, 假幣和假幣之間的“similar”關系以及假幣和案件之間“related by”關系. 因此, 不同的元路徑具有不同的語義來描述節點之間的相關度.

圖2 假幣犯罪信息網絡的元路徑實例

4 關鍵技術研究

本節介紹假幣犯罪信息分析系統中使用的兩個關鍵技術, 嫌疑人姓名消歧和假幣犯罪相關性分析. 嫌疑人姓名消歧用于構建假幣犯罪信息網絡的嫌疑之間的關系, 應用于假幣犯罪分析系統的構建假幣犯罪信息網絡模塊. 假幣犯罪信息相關性分析是基于假幣犯罪信息網絡提取節點網絡拓撲結構特征, 同時使用排序學習的方法融合節點的屬性信息和拓撲特征分析假幣犯罪信息相關性, 應用于假幣犯罪分析系統的數據分析模塊.

4.1 嫌疑人姓名消歧

為了解決假幣犯罪中嫌疑人記錄重復錄入導致的同一嫌疑人所犯的案件無法建立關聯關系的問題, 本文使用人名消歧技術判斷同名嫌疑人是否指向同一人.對于被認定為同一嫌疑人的記錄不進行合并, 而是建立關聯關系, 即假幣犯罪信息網絡中的嫌疑人之間的“identical”關系記為同一嫌疑人關系.

4.1.1 嫌疑人屬性

經過業務分析, 選擇了28個屬性作為嫌疑人消歧中使用的屬性, 并將這28個屬性分為四類:

1) 同一性判定屬性: 此類屬性具有較強的同一性判定功能, 如手機號、QQ號、銀行賬戶號等.

2) 重要屬性: 若該類屬性相同, 則兩條同名嫌疑人記錄有較大可能性指向同一嫌疑人, 如現住地址、戶籍地址、綽號等.

3) 一般屬性: 一般的常規屬性, 如性別、民族和血型等.

4) 模糊屬性: 警員在錄入過程存在主觀性誤差的屬性, 如體型、臉型、身高和口音等屬性.

4.1.2 兩階段聚類模型

本文采用自底向上的凝聚式層次聚類方法, 并分為兩個階段:

① 階段一: 該階段僅使用同一性判定屬性. 初始狀態下每一個同名的嫌疑人各為一個簇, 發現具有任一相同的同一性判定屬性則合并成一個簇, 并輸出若干個簇作為該階段的聚類結果.

② 階段二: 該階段使用重要屬性、一般屬性和模糊屬性三類屬性計算兩個嫌疑人之間的相似度, 對于不同類別的屬性賦予不同的權重. 使用公式(1)計算嫌疑人px和嫌疑人py的屬性k的相似度.

分別使用公式(2)(3)(4)計算嫌疑人px和嫌疑人py之間的重要屬性, 一般屬性以及模糊屬性的相似性.

其中Aimp,Anor,Afuz分別表示重要屬性集合, 一般屬性集合以及模糊屬性集合. 使用公式(5)計算嫌疑人px和嫌疑人py之間的相似度.

其中ɑimp,ɑnor,ɑfuz分別表示重要屬性, 一般屬性和模糊屬性的權重. 將階段一的輸出的若干個簇作為該階段的輸入, 并使用公式(6)計算簇Ci和簇Cj之間的相似度.

迭代過程中具有最大相似度的兩個簇合并成一個簇, 當任意兩個簇之間最大相似度小于一個給定的閾值t時停止聚類.

4.2 假幣犯罪信息相關性分析

假幣犯罪信息在本文中以假幣犯罪信息網絡的形式組織, 因此假幣犯罪信息的相關性分析即為假幣犯罪信息網絡中節點的相關性分析.

4.2.1 節點相關度排序關鍵信息

傳統的排序模型常常只關注節點的屬性特征, 或者只關注節點的拓撲特征, 但是只關注其中一種特征,往往會造成結果的置信度不夠, 本文將融合以上兩類特征來決定排序結果.

1) 節點之間的拓撲特征

節點的拓撲特征使用異構信息網絡的元路徑分析方法提取, 使用文獻[4]的四個基于元路徑的網絡度量方法, 分別是路徑數(path count)、歸一化路徑數(normalized path count)、隨機游走(random walk)以及對稱隨機游走(symmetric random walk)作為拓撲特征的度量方法. 根據文獻[3], 較短的元路徑能夠較好的度量相關度, 一條長的元路徑甚至會造成干擾. 因此本文將選用長度不大于4的元路徑, 使用傳統的廣度優先搜索算法, 在網絡模式圖上搜索出所有符合條件的元路徑. 對于每一個類型的節點拓撲特征數為元路徑的個數乘以度量方法個數.

2) 節點的屬性特征

節點的屬性特征直接從節點的屬性中通過業務分析選取, 部分屬性特征列舉如下:

① 案件: 案發時間, 案發地點, 簡要案情等.

② 嫌疑: 居住地, 戶籍地址, 是否慣犯等.

③ 假幣: 冠字號, 年版, 幣種, 厚度等.

4.2.2 節點相關性排序框架

圖3是節點相關性排序的框架圖, 訓練數據為已經標注好的節點相關性數據, 選用Ranking SVM算法訓練排序模型, 使用訓練集的數據訓練排序模型. 測試數據的結構和訓練數據相同, 對測試集中的每一條記錄, 使用排序模型計算待分析節點的得分獲得相關性結果, 其得分是一個在0到1之間的小數, 得分越高說明兩個節點越相關.

圖3 節點相關度排序框架示意圖

5 假幣犯罪信息分析系統的設計與實現

為了解決假幣犯罪信息的查詢問題, 基于第三節介紹的假幣犯罪信息網絡模型構建了假幣犯罪信息分析系統. 假幣犯罪信息分析系統提供假幣犯罪數據的查詢分析與可視化服務, 幫助警員分析假幣犯罪數據.假幣犯罪信息分析系統的系統結構圖如圖4所示. 構建假幣犯罪信息網絡模塊從原始的假幣犯罪數據存儲的關系型數據庫以及一些文本文件中抽取假幣、案件和嫌疑人的屬性信息和關系信息, 同時使用4.1節介紹的嫌疑人姓名消歧算法解決原始嫌疑人建立嫌疑人關系, 構建假幣犯罪信息網絡; 數據存儲模塊持久化假幣犯罪信息網絡; 數據分析模塊是假幣犯罪分析系統中的核心模塊, 負責處理用戶查詢, 從數據存儲模塊存儲的假幣犯罪信息網絡中查詢出和查詢節點相關聯并且符合用戶定義的查詢反胃的所有節點和關系,組成查詢結果網絡, 使用4.2節介紹的假幣犯罪信息相關性分析技術分析查詢項與查詢結果之間的相關性,返回結合相關性分析結果的查詢結果網絡; 數據展示模塊是假幣犯罪分析系統與用戶直接交互的模塊, 收集用戶查詢條件和查詢結果網絡的可視化展示.

圖4 假幣犯罪信息分析系統結構圖

5.1 構建假幣犯罪信息網絡模塊

構建假幣犯罪信息網絡模塊負責從數據源, 即關系型數據庫中抽取關系和屬性, 構建假幣犯罪信息網絡并將結果傳入數據存儲模塊. 根據假幣犯罪信息網絡關系的生成方式的不同分為以下三類:

① 原關系型數據庫的關系和屬性: 嫌疑人和案件以及案件和假幣之間的四種關系類型可以從原關系型數據庫中直接抽取, 同時對象的屬性信息也從原數據庫中一同抽取, 用于數據分析.

② 假幣和假幣的identical關系: 通過已有假幣相似度分析程序計算相似度建立關聯關系.

③ 嫌疑人和嫌疑人的similar關系: 根據嫌疑人姓名消歧算法建立聯系.

5.2 數據存儲模塊

假幣犯罪分析系統需要持久化的數據是假幣犯罪信息網絡, Neo4J是圖數據庫, 適合存儲網絡形式的數據, 在社交網絡領域已經有了成熟的應用, 同時Neo4J能處理具有高達數十億規模頂點和邊的圖數據,同時兼容完全ACID 事務屬性[15]. 本文選用NoSQL數據庫中的圖數據庫Neo4J作為假幣犯罪分析系統的數據庫. 假幣犯罪信息網絡的數據庫模式圖如圖5所示,和假幣犯罪信息網絡的結構完全一致, 同時還存儲了節點的屬性信息, 因此使用Neo4J圖數據庫存儲假幣犯罪信息網絡, 降低模型轉換的代價, 提高查詢效率.

圖5 假幣犯罪信息網絡的數據庫模式圖

5.3 數據分析模塊

數據分析模塊的主要功能是處理用戶的查詢請求,返回查詢結果網絡, 分為用戶查詢處理, 相關性分析,屬性特征計算和拓撲特征計算四個小模塊.

圖6是數據分析的流程圖, 展示了數據分析模塊中的四個小模塊是如何協作完成數據分析的工作. 首先用戶查詢處理模塊接收用戶的查詢條件, 根據用戶指定的查詢節點以及限定的查詢犯罪從數據存儲模塊存儲的獲取所有符合查詢條件的節點, 并生成查詢結果網絡, 然后將生成的查詢結果網絡傳送給相關性分析模塊. 相關性分析模塊將查詢結果網絡分解為查詢和待分析的相關性節點的二元組＜Q, R＞, 同時調用拓撲特征計算模塊計算該二元組的拓撲特征和屬性特征計算模塊計算屬性特征, 這兩個模塊將計算結果返回給相關性分析模塊, 由相關性分析模塊匯總二元組的拓撲特征和屬性特征, 調用4.2節介紹的節點相關性排序模型計算相關性, 然后將結果返回給用戶查詢處理模塊, 最后由用戶查詢處理模塊將相關性信息加入查詢結果網絡, 最后返回查詢結果網絡.

圖6 數據分析流程圖

5.4 數據展示模塊

數據展示模塊負責用戶交互, 包括收集用戶查詢條件以及查詢結果網絡的可視化. 用戶查詢條件包括指定查詢實體, 以及搜索的路徑長度.

圖7 查詢結果網絡示例

圖7 是查詢結果網絡的示例, 使用不同的圖片表示不同類型的節點, 用邊的顏色和形狀來區分不同的關系, 同時使用懸浮窗口顯示節點的屬性信息, 并根據結果節點和查詢節點之間的相關性分析結果決定該節點顯示的尺寸.

6 結語

本文將大量的犯罪數據以網絡的形式組織起來,建立了假幣犯罪信息網絡, 使用排序學習的方法融合屬性信息和拓撲信息解決假幣犯罪信息網絡中的節點相關度排序問題, 并在此基礎上設計了假幣犯罪信息分析系統, 提供查詢分析與可視化服務幫助警員進行假幣犯罪分析和并案分析. 在下一步工作中, 我們將會基于假幣犯罪信息網絡上挖掘假幣犯罪團伙信息.

1 Sun Y, Han J, Zhao P, et al. Rankclus: Integrating clustering with ranking for heterogeneous information network analysis. Proc. of the 12th International Conference on Extending Database Technology: Advances in Database Technology. ACM. 2009. 565–576.

2 Sun Y, Yu Y, Han J. Ranking-based clustering of heterogeneous information networks with star network schema. Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM. 2009. 797–806.

3 Sun Y, Han J, Yan X, et al. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. VLDB’11. 2011.

4 Sun Y, Barber R, Gupta M, et al. Co-author relationship prediction in heterogeneous bibliographic networks. 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE. 2011. 121–128.

5 Chen Y, Martin J. Cu-comsem: Exploring rich features for unsupervised web personal name disambiguation. Proc. of the 4th International Workshop on Semantic Evaluations. Association for Computational Linguistics. 2007. 125–128.

6 Elmacioglu E, Tan YF, Yan S, et al. Psnus: Web people name disambiguation by simple clustering with rich features. Proc. of the 4th International Workshop on Semantic Evaluations. Association for Computational Linguistics. 2007.268–271.

7 Chen Y, Lee SYM, Huang CR. Polyuhk: A robust information extraction system for web personal names. 2nd Web People Search Evaluation Workshop (WePS 2009), 18th WWW Conference. 2009.

8 Gong J, Oard D. Determine the entity number in hierarchical clustering for web personal name disambiguation. 2nd Web People Search Evaluation Workshop (WePS 2009), 18th WWW Conference. 2009.

9 Crammer K, Singer Y. Pranking with Ranking. Advances in Neural Information Processing Systems, 2002, 14: 641–647.

10 Herbrich R, Graepel T, Obermayer K. Large margin rank boundaries for ordinal regression. Advances in Neural Information Processing Systems, 1999: 115–132.

11 Joachims T. Optimizing search engines using clickthrough data. Proc. of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM. 2002. 133–142.

12 Cao Z, Qin T, Liu TY, et al. Learning to rank: from pairwise approach to listwise approach. Proc. of the 24th International Conference on Machine Learning. ACM. 2007. 129–136.

13 Zhang M, Kuang D, Hua G, et al. Is learning to rank effective for Web search? SIGIR 2009 Workshop: Learning to Rank for Information Retrieval. 2009. 641–647.

14 Liu TY. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 2009, 3(3): 225–331.

15 Eifrem E. Neo4J-the benefits of graph databases. 2009. http://www.oscon.com/oscon2009/public/schedule/detail/8364.

Counterfeit Money Crimes Information Analysis System Based on Heterogeneous Information Networks

CHEN Zhen-Hong1,2, LI Hui2, XU Shu-Ren2, YE Dan212
(University of Chinese Academy of Sciences, Beijing 100049, China) (Technology Center of Software Engineering, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

The query condition of traditional criminal query is a text, and query results are ordered documents lists. However, the way is not conducive to present the relationship of the results and help the police find clues of cases. Therefore, this paper reconstructs counterfeit crime data in the form of information network based on heterogeneous information network information, and constructs a counterfeit money crimes information network. We apply name disambiguation to build relationships of the suspects in counterfeit crime information network, and study relevancy problem of counterfeit money crimes information network using learning to rank methods. In this paper we design and implement the counterfeit money crimes information analysis system. To resolve the query problem of the criminal data, we use the entity as a query term and the network graph as the query results.

heterogeneous information network; meta-path; crime data mining; name disambiguation; learning to rank

國家自然科學基金(61379044);國家科技支撐課題(2015BAH18F02)

2016-03-19;收到修改稿時間:2016-04-18

10.15888/j.cnki.csa.005457