異質網中基于張量表示的動態離群點檢測方法

劉　露　左萬利,2　彭　濤,2

1(吉林大學計算機科學與技術學院　長春　130012)2　　　(符號計算與知識工程教育部重點實驗室(吉林大學)　長春　130012)

?

異質網中基于張量表示的動態離群點檢測方法

劉露1左萬利1,2彭濤1,2

1(吉林大學計算機科學與技術學院長春130012)2(符號計算與知識工程教育部重點實驗室(吉林大學)長春130012)

(liulu12@mails.jlu.edu.cn)

挖掘隱藏在異質信息網絡中豐富的語義信息是數據挖掘的重要任務之一.離群點在值、數據分布、和產生機制上都明顯不同于正常數據對象.檢測離群點并分析其不同的產生機制，最終消除離群點具有重要的現實意義.目前，針對異質信息網絡動態離群點檢測的研究工作相對較少，還有很多問題有待解決.由于異質信息網絡的動態性，隨著時間的變化，正常數據對象也可能轉變為離群點.針對異質網絡提出一種基于張量表示的動態離群點檢測方法(TRBOutlier)，并根據張量表示的高階數據構建張量索引樹.通過搜索張量索引樹，將特征加入到直接項集和間接項集中.同時，根據基于短文本相關性的聚類方法來判斷數據集中的數據對象是否偏離其原聚簇來動態檢測網絡中的離群點.該模型能夠在充分降低時間和空間復雜度的條件下保留異質網絡中的語義信息.實驗結果表明：該方法能夠快速有效地進行異質網絡環境下的動態離群點檢測.

動態離群點檢測；異質信息網絡；張量表示；張量索引樹；聚類

異質信息網絡代表一個現實世界的抽象，專注于多種類型的對象以及對象之間的相互關系.異質網絡中經常存在許多不同于正常對象的離群點.作為數據挖掘領域的一個重要分支，離群點檢測可以預測數據對象行為和發展趨勢，具有很重要的現實意義.離群點檢測有著廣泛的應用，例如，異常天氣檢測[1]、信用卡欺詐檢測[2]、心電圖分析[3]、異常GPS追蹤[4]、文本挖掘中異常的主題檢測[5]等.

隨著時間及網絡上下文的變化，正常數據對象可能由于其不同的發展趨勢在未來某一時刻轉變成離群點.也就是說，在時刻time1不是離群點的數據不一定在時刻time2仍然不是離群點.例如，一個作者在2010—2014年發表的論文大多和數據挖掘、機器學習方向相關.然而，他在2015年發表的論文卻和分布式學習相關.此時，該作者可以被視為離群點.這種離群點可能意味著其研究方向的轉變，也可能說明該作者和某個分布式學習方向的學者有著某種合作.同樣，我們可以通過動態離群點檢測來分析演員出演電影或電視劇的類型是否發生變化，幫助導演挑選合適的演員.也可以通過分析用戶在超市購買商品的記錄來預測其職業，從而進行合理的商品推薦.不僅如此，網絡中的數據還存在多種語義關系，同質網絡中的分類或聚類方法都很難直接應用到異質網絡當中.這是因為不同類型實體的異質鏈接負載著不同的語義，而且，異質網絡通常會得到更加豐富的信息.通過投影異質網絡得到的同質網絡往往會失去很多重要的信息.例如，通過對文獻信息網絡的合作者信息投影得到1個合作者網絡，這樣的1個投影操作會丟失文獻主題等相關信息.綜上所述，如何在保留語義關系的同時進行高效數據分析是我們需要考慮的問題.所以，異質網絡中動態離群點的檢測相對于同質網絡有很大不同，會有很多新的原理、方法有待我們去探索和研究.

本文提出了一種基于張量表示的異質網絡動態離群點檢測方法.張量是矢量概念的推廣，其多用于力學分析[6-7]、人臉識別[8-9]等領域.張量在同質網絡中進行高維數據的處理已有很好的效果，張量在異質網絡中卻少有成果.本文將不同類型的數據用高階張量進行表示，按數據的類型構建張量索引樹.張量索引樹既避免了張量矢量化帶來的維數災難問題，也解決了張量分解過程中出現的稀疏性問題.在進行聚類時，通過搜索張量索引樹將特征加入到直接項集和間接項集中加以區分，聚類特征權值計算充分考慮了特征之間存在的語義關系.該方法引入了時序概念，綜合了數據集中存在的時序數據.我們通過判斷實體在不同時刻所在聚簇是否發生變化來判斷其是否為離群點.另外，我們采用了2個不同的數據集(AMiner[10]和Yahoo!Movies[11])作為標準測試數據集來展示張量表示和短文本相關性聚類方法應用于離群點檢測的出色效果.實驗結果表明，TRBOutlier可以準確識別出標記的離群數據，張量索引樹的構建也大大降低了算法的時間和空間復雜度.

本文的主要貢獻如下:

1) 提出了一種基于張量表示的異質網絡動態離群點檢測方法TRBOutlier，通過分析網絡中數據變化趨勢判斷其是否為離群點;

2) 張量表示方法被應用到異質網絡中來處理不同類型的數據，張量索引樹的構建解決了數據稀疏性問題，同時保留了數據的語義關系;

3) 在張量索引樹的基礎上對網絡中出現的短文本進行相關性分析，并依據短文本的相關性對異質網絡中的實體進行聚類;

4) 應用不同數據集的實驗驗證我們提出的離群點檢測算法可以有效發現異質網絡中存在的動態離群點.

1　相關工作

離群點檢測不論在同質網絡中還是在異質網絡中都發揮著重要的作用.靜態離群點和動態離群點檢測在不同的背景下也都有著廣泛的應用和重要的研究意義.接下來，我們概述已有的部分離群點檢測工作以及在不同條件下的應用.

關于離群點檢測的研究有很多，但大多數都是針對同質信息網絡的研究[12-13].文獻[14]提出了一種基于密度的局部離群點檢測算法.該方法通過引入信息熵來發現網絡中存在的局部離群點.文獻[15]提出了一種使用后綴樹的離群點檢測方法.該方法認為離群點稀少，出現的次數也相對較少，比一些周期性出現且出現次數頻繁的正常點更加重要.其主要用于處理數值或者字符，因此被應用于同質信息網絡.

如今，異質網絡無處不在，網絡中實體的類型不同，實體之間的鏈接關系也多種多樣，使得原本適用于同質信息網絡的離群點檢測方法不能完全勝任.因此，異質網絡中的離群點檢測方法應運而生.Gupta等人在文獻[16]中提出了一種應用于異質網絡的基于社區分布的離群點檢測方法(CDOutlier).該方法利用非負矩陣分解來判斷所在社區的分布是否跟大部分社區分布變化模式相似來檢測離群點，他們還在文獻[17]中對關于時序數據的離群點檢測方法進行了綜述.

不論異質網絡還是同質網絡中的數據都不是一成不變的.我們將離群點檢測也分為靜態離群點檢測方法和動態離群點檢測方法.在靜態網絡中，Liu等人在文獻[18]中提出了一種基于支持向量數據描述的離群點檢測方法.該方法對網絡中的不確定數據進行了分析和處理.在進行離群點檢測的同時降低了不確定數據對整個分類器的影響，從而提高了離群點檢測的準確度.Perrozi等人在文獻[19]中提出了在大規模的屬性圖中面向用戶興趣偏好的離群點檢測方法.該方法使用主題聚類方法體現了在大規模社交網絡中推測用戶興趣偏好的成果，并檢測出其中的離群點.在動態網絡中，張凈等人在文獻[20]中提出了一種增量式的離群點檢測方法.該方法利用網格七元組對數據進行降維，通過分析數據的變化部分來達到減少計算量和降低時間復雜度的目的.但該方法也僅應用于同質信息網絡，并不能對多類型節點進行處理.文獻[21]描述了一個虛擬機在云端動態遷移時的離群點檢測方法.該方法通過定義維數推理規則，擴展了使用傳統局部離群因子來進行離群點檢測，從而彌補了不能檢測出虛擬機移動到新主機過程中出現離群點的缺陷.胡云等人在文獻[22]中提出了一種演化離群點檢測方法.該方法采用穩健回歸M-估計方法檢測重要成員的異常演化行為，它是一種在同質網絡下的動態離群點檢測方法.

國內外的研究人員針對離群點檢測做了許多探索和嘗試，也取得了一些研究成果，但其中很少有針對異質網絡的動態離群點檢測方法.本文提出的基于張量表示的動態離群點檢測方法，將網絡中的異質數據進行動態分析.不僅解決了數據的稀疏性問題，也很大程度上保留了數據之間的語義關系.該方法可以根據異質數據所在聚簇是否發生變化來判斷網絡中的數據是否為離群數據，也可以根據離群數據來分析其產生機制并進行相應的處理.

2　異質信息網絡中的張量表示方法

在本節中，我們主要介紹張量表示方法在異質信息網絡中的應用，并且將類型的概念引入張量中.

2.1基本定義

對同質網絡進行離群點檢測時， 通常用數值或向量來表示網絡中的實體.例如，在異常天氣檢測中，氣溫用數值進行記錄，1周或1個月的氣溫值可以存儲在1個向量之中.在對文本主題異常檢測時，文本中的特征權值通常用向量表示.不論氣溫還是文本，數值中和向量中存儲的都是同一類別的實體，即數值和向量的定義域是相同的.然而，在異質信息網絡中存在著不同類型的實體和鏈接，將所有實體各自表示成向量進行相似或離群的計算往往不能得到滿意的結果.因此，在本節中，我們提出了一種張量表示方法來處理異質網絡中的實體.將張量矢量化處理很可能引起維數災難并破壞了原本高維數據之間的結構關系.為了解決張量矢量化帶來的問題，研究者提出了一些張量分解模型.典型的張量分解方法，如PARAFAC分解和TUCKER分解[23]，雖然能一定程度上解決維數災難問題，但卻不能有效分析張量內在的模式和結構特點.張量是矢量的推廣，1階張量是向量，2階張量是矩陣，3階張量是矩體，3階或3階以上的張量被稱為高階張量.將張量表示用于異質離群點檢測是一種新的嘗試.在詳細描述離群點檢測算法之前，我們先給出一些基本的符號解釋和定義.

定義1. 異質信息網絡[24].給定一個有向圖G=(V，E;τ,φ;A，R).V代表節點集，E代表邊集.τ表示對象類型映射函數.φ表示關系類型映射函數.τ(v)∈A表示每個對象v∈V都屬于一個特定的對象類.φ(e)∈R表示每個關系e∈E都屬于一種特定的關系類.當節點類型數量|A|>1或邊的類型數量|R|>1時，這樣的信息網絡被稱為異質信息網絡.反之為同質信息網絡.

Fig. 1　The tensor index tree constructed by a third order tensor in bibliographic network.圖1　文獻網絡中由3階張量所構建的張量索引樹

定義3. 張量索引樹.張量索引樹是包含n(n≥1)個節點且滿足5個條件的有限集合:

1) 張量索引樹中的每一個節點都由1個 N(N≥1)維向量組成.

2) 存在唯一一個向量節點X0，它是由一系列時序數據組成的向量，稱為張量索引樹的根節點.

3) 張量索引樹同一層的節點可以包含不同類型的數據.但同一類型的數據都處于張量索引樹的同一層中.

4) 除根節點的后繼節點為向量本身外，其余非葉子節點向量中的數據均可獨立作為后繼節點并放置在所在類型的向量之中.

5) 若1個向量節點中的數據均無后繼節點，則稱該向量節點為張量索引樹的葉子節點.

2.2張量索引樹的構建

第1節已敘述張量矢量化可能破壞各階中數據之間的關系.在大數據環境下，不可避免地會引起維數災難.而對于異質網絡中的數據，如何進行高階統計也是我們需要考慮的問題.應用張量分解方法，例如構建鄰接矩陣，處理數據集中的樣本會出現嚴重的數據稀疏性問題.在本節中，我們提出了一種構建張量索引樹的方法來處理異質信息網絡中用張量表示的數據，進而動態發現網絡中存在的離群點.

我們首先描述張量索引樹的構建過程.由于本文主要解決動態離群點發現的問題，因此，張量索引樹的根節點為時序數據組成的向量X=(X1，X2，…，Xn) ，如圖1中Layer1所示.在本節中，我們使用文獻網絡中的3階張量模型來說明構建過程.在時間點X1中，順序遍歷N(N=3)階張量中的第1階張量.將屬于type1類型的實體(作者名)加入Layer2向量節點中.同時，將該作者發表的論文依次加入Layer3向量節點中.Layer3向量節點中的論文題目作為Layer2向量節點中作者名的后繼節點.大部分情況下，1篇論文是由若干作者合作完成的.因此，形成Layer3向量節點之后需進行去重.同樣，第2階張量和第3階張量之間也被加入索引.第3階張量中的實體(關鍵詞)作為第4層節點被加入到張量索引樹當中.在圖1張量索引樹中的Layer2，Layer3向量節點都只有1個后繼向量節點.但在實際應用中，一個類型的實體可能擁有不同類型的后繼節點.例如，在文獻網絡中，論文不僅有關鍵詞一個屬性，而且論文發表的期刊名或會議名也應該在數據分析的范圍之內.圖1中的Layer4也應加入期刊名或會議名所構成的向量節點.同樣，在電影網絡分析過程中，我們也需要考慮電影所屬的類型、配音使用的語種等屬性.本文將用3階張量構成單后繼節點的4層張量索引樹來進行構建過程說明.

張量索引樹的構建不僅可以加快離群點檢測的速度，而且可以有效解決在使用鄰接矩陣進行計算時出現的數據稀疏性問題.

3　基于張量表示的聚類過程

在本節中，我們詳細介紹如何根據給定的入口entry(source，target)搜索張量索引樹，進而使用聚類方法發現異質網絡中存在的離群點(即源節點相對于目標類別是否離群).張量索引樹可以根據給定入口快速定位相關的異質信息.例如，給定作者a1，只需通過遍歷其所有前驅結點和后繼節點就可以找出與之相關的論文、期刊、會議、研究方向等相關信息.我們把作者名、期刊名、研究方向和其他異質信息網絡中出現的例如電影名、電影類別、語種等都稱為短文本.然而，我們知道1個作者發表的1篇論文中只有4～5個關鍵詞，1個演員出演的1部電影可能也只有1～3個類別.不論是論文的關鍵詞還是電影所屬的類別都不是完全無關的.假設我們要進行作者相對于“textmining”這個研究方向離群程度的計算.僅定位與“textmining”在同一路徑上的作者類型節點是不夠準確的、不全面的.短文本之間的相似性也應被充分考慮.與“textmining”在語義上相似的短文本如“webmining”，“textclassification”等，也應被加入到特征權值分析中.在進行基于張量的短文本聚類之前，我們先描述短文本特征權值計算過程和如何處理數據分布的不一致性.

首先，提取索引樹中源節點至目標類別路徑上直接關聯的數據，將其放入直接項集(directitemset, DIS)中，如圖2表格中的Paper1～Paper3.根據頻繁項集的思想，將包含直接項集中目標類型節點2項以上的前驅節點及其相應路徑上的直接關聯信息加入到間接項集(indirectitemset, IIS)中，如圖2表格中的Paper4～Paper10.從表格中可以看到，Paper4中的關鍵詞outlierdetection和heterogeneousnetwork在Paper1～Paper3中出現過，因此，Paper4被加入間接項集中.得到直接項集和間接項集后，項集中目標類別的特征被加入到1維向量詞典中，記為Dic1=(st1:stw1,st2:stw2,…,stN:stwN).其中，st表示短文本特征，stw表示短文本特征權值.式(1)中給出了短文本權值的定義.

(1)

其中，NDIS和NIIS分別為直接項集和間接項集中項的數量(1條路徑中的數據集合稱為1條項集，也稱記錄).tk i表示特征i在直接項集記錄k中出現的次數. tl i表示特征i在間接項集記錄l中出現的次數.α為調節因子.本文中，設α=0.5.由于直接項集中的記錄和源節點的相關程度將高于間接項集中的記錄與源節點的相關程度，因此，調節因子起到調節特征在直接項集和間接項集中重要程度的作用.

Fig. 2　Direct item set and indirect item set.圖2　直接項集與間接項集

根據上述特征權值計算過程，我們可以得到源節點相對于目標類別的特征表示，根據特征相似度判斷對象是否屬于一個聚簇當中.但是，不同的源節點對應的目標類別節點大不相同，需在聚類之前解決數據分布不一致的問題.首先構建一個包含目標類別所有特征的詞典DIC，每個源節點關于目標節點的特征表示為Dici，1≤i≤Nsum其中，Nsum為目標類別特征總數.每個Dici中的特征均為DIC的一部分.計算短文本特征權值的算法在算法1中給出.由于之前已經得到源節點相對于目標類別節點的特征表示，對于所有DIC中的特征，如果未在Dici出現過，則該特征的權值設為0.該方法可以解決聚類過程中出現的數據分布不一致問題.

異質網絡中的節點及鏈接關系存在異質性、多樣性，采用單一對象類別標注方法會失去很多語義信息.因此，我們提出一種基于張量表示的短文本聚類的方法來進行離群點的檢測.式(2)給出了2個特征向量進行相似度計算的方法[25].

(2)

Fig. 3　A model that illustrates how the outliers change based on clustering from time1to time2.圖3　時刻time1到時刻time2基于聚類方法的離群點變化模型

其中，向量(stwi1,stwi2,…,stwi Nsum)和向量(stwj1,stwj2,…,stwj Nsum)分別是源節點i和源節點j的Nsum維特征表示，代表Dici和Dicj.Sim(Dici，Dicj) 的取值范圍為[0,1].式(3)定義了一個0，1變量CV(comparisonvariation)[25]來判斷2個聚類能否合并或分裂.

(3)

算法1. 短文本特征權值計算算法.

輸入：張量索引樹TI-tree、 源節點s、目標類型t、直接項集DIS、間接項集IIS；

輸出：源節點相對于目標類型的特征表示Dics.

① BreadthFirstSearch(TI-tree,s)；

②foreach包含s的路徑

④endfor

⑥if任意結點p是集合C中至少兩個結點的父結點

⑦ 將路徑p中所有結點加入集合IIS中;

⑨endif

⑩ 用式(1)計算每個源結點s的特征表示Dics.

4　基于張量表示的離群點檢測方法

離群點和正常數據對象的產生機制不同，以致于出現了不同于正常點的數值或數據分布等現象.而且，正常數據對象也可能在未來某時刻成為離群點.也就是說，某些數據在正常對象和離群點之間是動態變化的.基于這個思想，在本節中我們提出了一種基于張量表示的動態離群點檢測方法.

首先，我們將帶有時序特征的數據按張量表示法添加到張量索引樹當中.樹中的根節點即為時序數據.再通過對每個時間點下的子節點進行聚類，分析每個對象所在的聚簇是否變化和變化的程度，即可判斷節點所對應的對象是否為離群點.如圖3所示，時刻time1網絡中存在5個聚簇，其中3個標記的對象分別在 C1，C2，C5中.然而，時刻time2三個標記的對象分別變化到了C5，C3，C4中.由于3個標記對象的變化趨勢與其所在聚簇內節點的變化趨勢不同.因此，我們將這3個標記對象視為網絡中的離群點.

在真實的網絡環境中，我們可以將數據分為N個時刻進行數據分析.不僅可以判斷對象所在的聚簇是否發生變化，而且可以統計變化的次數以達到數據分析的目的.圖4給出了基于張量表示的動態離群點檢測方法的整體框架.

Fig. 4　The overall framework of tensor representation based dynamic outlier detection method.圖4　基于張量表示的動態離群點檢測方法的整體框架

5　實驗與結果

在本節中，我們使用本文提出的技術構建了一個面向異質網絡的動態離群點檢測模型，并且在2個數據集(AMiner[10]和Yahoo!Movies[11])上測試了我們的方法.

5.1度量標準

離群點的判斷標準一般分為2種：1)用二進制數0，1來判斷數據是否為離群點.若為1則是離群點，反之則不是離群點;2)用離群分數來度量數據的離群程度，若離群分數達到規定的閾值，則認為其是離群點，反之則不是離群點.本文選用第1種方法來進行離群點的判斷.由于已有數據集中很少存在標記的離群數據，異質網絡中也幾乎沒有辦法統一標記實體的類別.因此，我們在數據集中手動加入離群數據.若數據對象所屬的聚簇發生了變化，則該對象被識別為離群點.我們用精確率和召回率來反映離群點檢測系統的性能.離群點檢測系統中的精確率是被正確識別為離群點的數據占被識別為離群點數據的比例.召回率，也稱查全率，是被正確檢測出的離群點數據占實際離群點數據的比例.這2個度量標準分別反映了模型找對和找全離群點的能力.我們定義精確率和召回率公式如下.

(4)

(5)

其中，ChS表示聚類過程中所在聚簇發生變化的數據集.OutS表示聚類前被標記為離群點的數據集.

隨著召回率的增加，精確率很可能呈下降趨勢.通過調節精確率和召回率的重要程度，我們采用精確率和召回率的調和平均值F-Measure[26]來作為評估離群點檢測模型的1個標準.F-Measure的計算公式定義如下:

(6)

β作為調節精確率和召回率的權值，在實驗中被設置為1.然而，僅用精確率和召回率評價系統的性能是不夠的.本文還使用準確度Accuracy作為度量標準來衡量所有數據是否和真實類別一致，即衡量模型作出正確決定的能力.我們將數據集中的數據分成四大類:1)被判斷為離群點的離群數據，記作TP(true positive);2)被判斷為離群點的正常數據，記作FP(false positive);3)被判斷為正常點的正常數據，記作TN(true negative);4)被判斷為正常點的離群數據，記作FN(false negative).AllN表示數據集中所有記錄的總數.Accuracy的公式定義如下:

(7)

5.2數據集

本文將在AMiner和Yahoo!Movies兩個數據集上測試我們提出的方法.下面我們從數據集大小和數據特點等方面分別介紹這2個數據集.

1) AMiner數據集是一個異質的文獻信息網絡.它由3個部分構成，分別是AMiner-Author， AMiner-Paper， AMiner-Coauthor.這3部分共包括1 712 433個作者和2 092 356篇論文的信息，這些節點和節點之間的關系構成了涵蓋計算機不同領域的異質信息網絡.我們提取其中20 000個作者及其相關信息構成本文實驗數據集，并手動添加200個記錄作為離群點進行檢測.

2) Yahoo!Movies數據集作為Yahoo!數據集評分和分類數據的一部分，可以被應用到各種數據挖掘算法當中.這個數據集包含6個文件，共23 MB，描述了電影網絡中各個節點的信息和節點之間的關系.我們從中選取5 000個演員和其相應的電影信息，包括電影名、電影類型的相關信息進行實驗.并手動添加100個記錄作為離群點進行識別.在AMiner和Yahoo!Movies兩個數據集中均構建3階張量進行實驗.

5.3實驗和結果

本節用4個實驗來驗證我們提出的離群點檢測模型的可行性和高效性.實驗1是通過變化λ的取值判斷其取何值時精確率率和召回率可以達到最大值.從表1可以看出，λ越小，聚類的標準越高，數據點特征稍有變化就可能被視為離群點.反之，λ越大，聚類的標準越低，此時可以盡量找全離群點，但精確率會有所降低.同時，λ過高或過低也會影響著準確度的大小.在AMiner數據集中，λ=3時F-Measure和Accuracy的取值達到峰值.在Yahoo!Movies數據集中，λ=2時F-Measure和Accuracy的取值達到峰值.在之后的3個實驗中，λ在AMiner和Yahoo!Movies數據集中分別取3和2.

Table 1　The Performance of TRBOutlier on AMiner and Yahoo!Movies with Different λ表1　TRBOutlier方法在AMiner和Yahoo!Movies數據集中λ變化時的性能

在實驗2中，我們將提出的基于張量表示的動態離群點檢測算法和2個基線算法進行F-Measure和Accuracy的比較.由于目前還沒有基于張量表示的離群點檢測方法，我們在實驗部分使用基于實體的社團離群點檢測方法(entity based clique outlier detection, EBC[27])和基于社區分布的離群點檢測方法(community distribution based outlier detection, CDOutlier[16]). EBC將每個實體的屬性單獨聚類，當實體的屬性變化異常時，該實體就被識別為離群點.將實體的屬性單獨聚類很可能忽略了異質網絡之間的結構關系.CDOutlier使用非負矩陣分解的方法判斷社區分布的變化情況.非負矩陣雖然可以很好地保留對象之間的結構關系，但不能很好地解決數據稀疏性的問題，很大程度上造成了時間和空間的浪費.從實驗結果可以看出，TRBOutlier的離群點檢測性能要高于EBC和CDOutlier(如圖5所示).

在實驗3中，我們驗證離群點檢測方法的可擴展性，即隨著節點數量的增長，運行時間成線性還是指數型增長.從圖6可以看出，在同一數據集中，當數據量增加時，運行時間也呈線性增長趨勢.當處理器數量增加時，運行時間也穩步下降.

Fig. 5　Performance comparison of three outlier detection methods on AMiner and Yahoo!Movies datasets.圖5　3種離群點檢測方法在AMiner和Yahoo!Movies數據集中的性能比較

Fig. 6　Execution time comparison of TRBOutlier over AMiner and Yahoo!Movies datasets.圖6　TRBOutlier在AMiner和Yahoo!Movies數據集中運行時間比較

在實驗4中，我們將提出的TRBOutlier與其他基線算法進行效率的比較.從運行的時間上可以看出，TRBOutlier的效率明顯高于2個基線算法.張量索引樹的構建可以起到降低時間復雜度的效果,如圖7所示:

Fig. 7　Running time comparison of three outlier detection methods.圖7　3種離群點檢測方法的運行時間比較

6　總　　結

本文提出了一種基于張量表示的動態離群點檢測方法.靜態離群點檢測方法可以發現1個時間點內的異常數據，然而網絡中的數據是不斷變化的.本文提出的離群點檢測方法可以發現不斷變化的異常點.將張量表示引入到離群點檢測中是一個新的嘗試，基于張量表示的異質網絡數據可以在解決數據稀疏性的同時保留網絡結構中的語義關系.通過構建張量索引樹，將數據的特征表示分成直接項集和間接項集2種，并根據基于短文本相似度的聚類方法進行聚類.直接項集和間接項集考慮了和對象直接相關屬性和間接相關屬性之間的區別.根據對象所在聚簇是否發生了變換來對其進行動態離群判斷.實驗結果表明，本文提出的動態離群點檢測方法在準確度和效率方面優于許多已有的離群點檢測方法.因此，本文的方法是可行且高效的.

[1]Shepherd J M, Burian S J. Detection of urban-induced rainfall anomalies in a major coastal city[J]. Earth Interactions, 2003, 7(4): 1-17

[2]Beutel A, Faloutsos C. User behavior modeling and fraud detection[J]. IEEE Intelligent Systems, 2016, 31(2):84-86

[3]Jiang B C, Yang W H, Yang C Y. An SPC-based forward-backward algorithm for arrhythmic beat detection and classification[J]. Industrial Engineeering & Management Systems, 2013, 12(4): 380-388

[4]Chen C, Zhang D, Castro P S, et al. Real-time detection of anomalous taxi trajectories from GPS traces[M] //Mobile and Ubiquitous Systems: Computing, Networking, and Services. Berlin: Springer, 2011: 63-74

[5]Srivastava A, Zane-Ulman B. Discovering recurring anomalies in text reports regarding complex space systems[C] //Proc of IEEE Aerospace Conf. Piscataway, NJ: IEEE, 2005: 55-63

[6]Lebedev L P, Cloud M J, Eremeyev V A. Tensor Analysis with Applications in Mechanics[M]. Hackensack, NJ: World Scientific, 2010

[7]Schobeiri M T. Vector and tensor analysis, applications to fluid mechanics[G] //Fluid Mechanics for Engineers. Berlin: Springer, 2010: 11-29

[8]Hao N, Kilmer M E, Braman K, et al. Facial recognition using tensor-tensor decompositions[J]. SIAM Journal on Imaging Sciences, 2013, 6(1): 437-463

[9]Litaˇ L, Pelican E. A low-rank tensor-based algorithm for face recognition[J]. Applied Mathematical Modelling, 2015, 39(3): 1266-1274

[10]Tang J, Zhang J, Yao L, et al. Arnetminer: Extraction and mining of academic social networks[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 990-998

[11]Yahoo! Webscope Program. Yahoo! Movies user ratings and descriptive content information, v1.0[OL]. [2016-01-28] http://webscope.sandbox. yahoo.com

[12]Wu S, Wang S. Information-theoretic outlier detection for large-scale categorical data[J]. IEEE Trans on Knowledge and Data Engineering, 2013, 25(3): 589-602

[13]Akoglu L, Tong H, Koutra D. Graph based anomaly detection and description: A survey[J]. Data Mining and Knowledge Discovery, 2015, 29(3): 626-688

[14]Hu Caiping, Qin Xiaolin. A density-based local outlier detection algorithm[J]. Journal of Computer Research and Development, 2010, 47(12): 2110-2116 (in Chinese)

(胡彩平, 秦小麟. 一種基于密度的局部離群點檢測算法DLOF[J]. 計算機研究與發展, 2010, 47(12): 2110-2116)

[15]Rasheed F, Alhajj R. A framework for periodic outlier pattern detection in time-series sequences[J]. IEEE Trans on Cybernetics, 2014, 44(5): 569-582

[16]Gupta M, Gao J, Han J. Community distribution outlier detection in heterogeneous information networks[G] //Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2010: 11-29

[17]Gupta M, Gao J, Aggarwal C C. Outlier detection for temporal data: A survey[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(9): 2250-2267

[18]Liu B, Xiao Y, Cao L, et al. SVDD-based outlier detection on uncertain data[J]. Knowledge and Information Systems, 2013, 34(3): 597-618

[19]Perozzi B, Akoglu L, Sánchez P I, et al. Focused clustering and outlier detection in large attributed graphs[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 1346-1355

[20]Zhang Jing, Sun Zhihui, Yang Ming, et al. Fast incremental outlier mining algorithm based on grid and capacity[J]. Journal of Computer Research and Development, 2011, 48(5): 823-830 (in Chinese)

(張凈, 孫志揮, 楊明, 等. 基于網格和密度的海量數據增量式離群點挖掘算法[J]. 計算機研究與發展, 2011, 48(5): 823-830)

[21]Huang T, Zhu Y, Wu Y, et al. Anomaly detection and identification scheme for VM live migration in cloud infrastructure[J]. Future Generation Computer Systems, 2016, 56: 736-745

[22]Hu Yun, Wang Chongjun, Xie Junyuan, et al. Robust transition estimation for community evolution and evolutionary outlier detection[J]. Journal of Software, 2013, 24(11), 2710-2720 (in Chinese)

(胡云, 王崇駿, 謝俊元, 等. 社群演化的穩健遷移估計及演化離群點檢測[J]. 軟件學報, 2013, 24(11), 2710-2720)

[23]Kolda T G, Bader B W. Tensor decompositions and applications[J]. SIAM Review, 2009, 51(3): 455-500

[24]Sun Y, Han J, Yan X, et al. Pathsim: Meta path-based top-ksimilarity search in heterogeneous information networks[C] //Proc of VLDB’2011. Trondheim,Norway: VLDB Endowment, 2011:992-1003

[25]Peng T, Liu L. A novel incremental conceptual hierarchical text clustering method using CFu-tree[J]. Applied Soft Computing, 2015, 27: 269-278

[26]Croft W B, Metzler D, Strohman T. Search engines: Information retrieval in practice[M]. Reading: Addison-Wesley, 2010

[27]Gupta M, Gao J, Yan X, et al. On detecting association-based clique outliers in heterogeneous information networks[C] //Proc of IEEE//ACM Int Conf on Advances in Social Networks Analysis and Mining (ASONAM). Piscataway, NJ: IEEE, 2013: 108-115

Liu Lu, born in 1989. PhD. Her research interests include Web mining, information retrieval, machine learning.

Zuo Wanli, born in 1957. PhD, professor, PhD supervisor. Senior member of China Computer Federation. His research interests include database theory, data mining, Web mining, machine learning, and Web search engine.

Peng Tao, born in 1977. PhD, professor. Member of China Computer Federation. His research interests include Web mining, information retrieval, and machine learning.

TensorRepresentationBasedDynamicOutlierDetectionMethodinHeterogeneousNetwork

LiuLu1,ZuoWanli1,2,andPengTao1,2

1(College of Computer Science and Technology, Jilin University, Changchun 130012)2(Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)

Miningrichsemanticinformationhiddeninheterogeneousinformationnetworkisanimportanttaskindatamining.Thevalue,datadistributionandgenerationmechanismofoutliersarealldifferentfromthatofnormaldata.Itisofgreatsignificanceofanalyzingitsgenerationmechanismoreveneliminatingoutliers.Outlierdetectioninhomogeneousinformationnetworkhasbeenstudiedandexploredforalongtime.However,fewofthemareaimingatdynamicoutlierdetectioninheterogeneousnetworks.Manyissuesneedtobesettled.Duetothedynamicsoftheheterogeneousinformationnetwork,normaldatamaybecomeoutliersovertime.Thispaperproposesadynamictensorrepresentationbasedoutlierdetectionmethod,calledTRBOutlier.Itconstructstensorindextreeaccordingtothehighorderdatarepresentedbytensor.Thefeaturesareaddedtodirectitemsetandindirectitemsetrespectivelywhensearchingthetensorindextree.Meanwhile,wedescribeaclusteringmethodbasedonthecorrelationofshorttextstojudgewhethertheobjectsindatasetschangetheiroriginalclustersandthendetectoutliersdynamically.Thismodelcankeepthesemanticrelationshipinheterogeneousnetworksasmuchaspossibleinthecaseoffullyreducingthetimeandspacecomplexity.Theexperimentalresultsshowthatourproposedmethodcandetectoutliersdynamicallyinheterogeneousinformationnetworkeffectivelyandefficiently.

dynamicoutlierdetection;heterogeneousinformationnetwork;tensorrepresentation;tensorindextree;clustering

2016-03-17；

2016-05-24

國家自然科學基金項目(60903098)；吉林省工業技術研究和開發項目(JF2012c016-2)；吉林大學研究生創新基金項目(2015040)

彭濤(tpeng@jlu.edu.cn)

TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(60903098),theProjectofJilinProvincialIndustrialTechnologyResearchandDevelopment(JF2012c016-2),andtheGraduateInnovationFundofJilinUniversity(2015040).