熊 赟，朱揚勇

1. 復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 201203；2. 上海市數(shù)據(jù)科學(xué)重點實驗室（復(fù)旦大學(xué)） 上海 201203

特異群組挖掘：框架與應(yīng)用

熊 赟1,2，朱揚勇1,2

1. 復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 201203；2. 上海市數(shù)據(jù)科學(xué)重點實驗室（復(fù)旦大學(xué)） 上海 201203

特異群組挖掘在證券金融、醫(yī)療保險、智能交通、社會網(wǎng)絡(luò)和生命科學(xué)研究等領(lǐng)域具有重要應(yīng)用價值。特異群組挖掘與聚類、異常挖掘都屬于根據(jù)數(shù)據(jù)對象的相似性來劃分數(shù)據(jù)集的數(shù)據(jù)挖掘任務(wù)，但是，特異群組挖掘在問題定義、算法設(shè)計和應(yīng)用效果方面不同于聚類和異常等挖掘任務(wù)。為此，系統(tǒng)地闡述了特異群組挖掘任務(wù)，分析了特異群組挖掘任務(wù)與聚類、異常等任務(wù)之間的差異，給出了特異群組挖掘任務(wù)的形式化描述及其基礎(chǔ)算法，最后，列舉了特異群組挖掘的幾個重點應(yīng)用。

大數(shù)據(jù)；數(shù)據(jù)挖掘；特異群組；聚類；異常檢測；數(shù)據(jù)相似性

1 引言

數(shù)據(jù)挖掘技術(shù)是數(shù)據(jù)開發(fā)技術(shù)的核心[1]。其中，挖掘高價值、低密度的數(shù)據(jù)對象是大數(shù)據(jù)的一項重要工作，甚至高價值、低密度常常被用于描述大數(shù)據(jù)的特征[2]。存在這樣一類數(shù)據(jù)挖掘需求：將大數(shù)據(jù)集中的少部分具有相似性的對象劃分到若干個組中，而大部分數(shù)據(jù)對象不在任何組中，也不和其他對象相似（如圖1所示）。將這樣的群組稱為特異群組，實現(xiàn)這一挖掘需求的數(shù)據(jù)挖掘任務(wù)被稱為特異群組挖掘，由朱揚勇和熊赟于2009年首次提出[3]。參考文獻[3]中，特異群組的英文用peculiarity group表示，意指這些群組具有特殊性、異常性；參考文獻[4]強調(diào)這些群組中的對象具有強相似性、緊粘合性（即cohesive），因此將特異群組挖掘問題的英文進一步深化，表達為cohesive anomaly mining，意指挖掘的特異群組不僅具有特殊性、異常性，而且群組對象是強相似、緊粘合的。將這些對象形成的群組改用abnormal group[4]表示。

大數(shù)據(jù)特異群組挖掘具有廣泛應(yīng)用背景，在證券交易、智能交通、社會保險、生物醫(yī)療、銀行金融和網(wǎng)絡(luò)社區(qū)等領(lǐng)域都有應(yīng)用需求，對發(fā)揮大數(shù)據(jù)在諸多領(lǐng)域的應(yīng)用價值具有重要意義。例如，在證券市場中，特異群組常常表現(xiàn)為合謀操縱（多賬戶聯(lián)合操縱）、基金“老鼠倉”等。這些賬戶以獲取不正當利益為目的，集中資金優(yōu)勢或利用信息優(yōu)勢，操縱交易量、交易價格，擾亂市場秩序。其中，合謀操縱的行為模式主要是集中資金優(yōu)勢、持股優(yōu)勢進行市場操縱，通過使用多個賬戶進行分工交易、分倉持有來合謀操縱市場價格和成交量，以誘導(dǎo)其他投資者；基金“老鼠倉”的行為模式是通過獲悉基金即將或正在交易某投資標的，且該筆交易大幅影響投資標的價格的交易信息，以相近時刻、相同買賣方向用個人私有資產(chǎn)同步交易該投資標的，以獲取收益。

本文系統(tǒng)地闡述了特異群組挖掘任務(wù)的框架，分析了特異群組挖掘任務(wù)與聚類、異常等任務(wù)之間的差異，給出了特異群組挖掘任務(wù)的形式化描述及其基礎(chǔ)算法，最后，列舉了特異群組挖掘的幾個重點應(yīng)用。

2 特異群組挖掘與聚類和異常檢測的關(guān)系

特異群組是指由給定大數(shù)據(jù)集里面少數(shù)相似的數(shù)據(jù)對象組成的、表現(xiàn)出相異于大多數(shù)數(shù)據(jù)對象而形成異常的群組[3,4]，是一種高價值低密度的數(shù)據(jù)形態(tài)。特異群組挖掘、聚類和異常檢測都是根據(jù)數(shù)據(jù)對象間的相似程度來劃分數(shù)據(jù)對象的數(shù)據(jù)挖掘任務(wù)，但它們在問題定義、算法設(shè)計和應(yīng)用效果上存在差異[5]。

圖1 大數(shù)據(jù)集里的特異群組

2.1 與聚類的比較

聚類是根據(jù)最大化簇內(nèi)相似性、最小化簇間相似性的原則，將數(shù)據(jù)對象集合劃分成若干個簇的過程[6]。相似性是定義一個簇的基礎(chǔ)，聚類過程的質(zhì)量取決于簇相似性函數(shù)的設(shè)計，不同的簇相似性定義將得到不同類別的簇[7]。例如，參考文獻[7]給出了幾種不同類別的簇：圖2（a）表示明顯分離的簇，每個對象到同一簇中對象的距離比到不同簇中任意對象的距離更近或更相似；圖2（b）表示基于原型的簇，每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近或更相似；圖2（c）是基于密度的簇，簇是對象的稠密區(qū)域；圖2（d）表示一種概念簇，簇是有某種共同性質(zhì)的對象的集合?？梢钥闯觯哂心撤N共同性質(zhì)的對象取決于挖掘目標的定義。不同的簇相似性定義得到不同的簇，甚至還有不同形狀、不同密度的簇。

但不管怎樣，傳統(tǒng)聚類算法是處理大部分數(shù)據(jù)對象具有成簇趨勢的數(shù)據(jù)集，將大部分數(shù)據(jù)對象劃分成若干個簇。然而，在一些大數(shù)據(jù)應(yīng)用中，大部分數(shù)據(jù)并不呈現(xiàn)聚類趨勢，而僅有少部分數(shù)據(jù)對象能夠形成群組。

特異群組挖掘是在大數(shù)據(jù)集中發(fā)現(xiàn)特異群組，找出的是少部分具有相似性的數(shù)據(jù)對象。與聚類的共同之處是，特異群組中的對象也具有相似性，并將相似對象劃分到若干個組中，這在一定程度上符合傳統(tǒng)簇的概念。但是，特異群組之外的對象數(shù)目一般遠大于特異群組中對象的數(shù)目，并且這些對象不屬于任何簇，這和聚類的目的是不同的。

2.2 與異常檢測的比較

少部分數(shù)據(jù)對象的挖掘通常被認為是異常檢測任務(wù)[8]。在特異群組挖掘問題中，相對于不在任何群組中的大部分數(shù)據(jù)對象而言，少部分相似對象形成的群組是一種異常。但是，現(xiàn)有的異常檢測算法難以直接用于特異群組挖掘。一是，目前大多數(shù)異常挖掘算法的目標是發(fā)現(xiàn)數(shù)據(jù)集中那些少數(shù)不屬于任何簇，也不和其他對象相似的異常點（point anomalies）[9]，這和特異群組的目標不同；二是，除異常點檢測外，存在一些算法用于發(fā)現(xiàn)異常點成簇的情況，稱為微簇（micro-cluster或clustered anomalies）挖掘[10,11]，但是該任務(wù)也對剩下的大部分數(shù)據(jù)有聚類假設(shè)，即微簇問題在一個數(shù)據(jù)集中包含點異常、微簇和簇，這不同于特異群組挖掘；三是，集體異常（collective anomalies）挖掘任務(wù)也不同于特異群組挖掘，因為集體異常只能出現(xiàn)在數(shù)據(jù)對象具有相關(guān)性的數(shù)據(jù)集中，其挖掘要求探索數(shù)據(jù)集中的結(jié)構(gòu)關(guān)系[9]。目前集體異常挖掘主要處理序列數(shù)據(jù)、圖數(shù)據(jù)和空間數(shù)據(jù)。

圖2 不同相似性定義下的各種簇[7]

2.3 三者關(guān)系

通過上述比較分析可以得到，如果一個數(shù)據(jù)集中的大部分數(shù)據(jù)對象都能夠歸屬于某些簇，那么那些不能歸屬于任何簇的數(shù)據(jù)對象就是異常對象；如果一個數(shù)據(jù)集中的大部分數(shù)據(jù)對象都不屬于任何簇，那么那些具有相似性的數(shù)據(jù)對象所形成的群組就是特異群組。因此，挖掘的需求決定了簇、特異群組、異常點：如果需要找大部分數(shù)據(jù)對象相似，則是聚類問題；需要找少部分數(shù)據(jù)對象相似，則為特異群組；如果是找少數(shù)不相似的數(shù)據(jù)對象，則為異常。

綜上，特異群組挖掘結(jié)合了聚類和異常檢測的一些特點，但又具有自身的特性。特異群組挖掘所關(guān)注的是一個大數(shù)據(jù)集中大部分數(shù)據(jù)對象不相似，而每個特異群組中的對象是相似的。即特異群組對象的群體性和普通對象的個體性不同，群組中的個體對象本身單獨而言并不一定特異，只是和群組中的相關(guān)對象一起構(gòu)成了特異群組。

3 特異群組挖掘形式化描述[4]

設(shè)Fd為d-維特征空間，D={O1,O2,…,Oi,…,On}是對象集合，Oi∈Fd。兩個對象Oi和Oj間的相似性f由相似性函數(shù)sim(Oi，Oj)計算（0≤f≤1）。

定義1 （相似對象）給定一個相似性閾值δ，對于一個對象Oi（Oi∈D），如果數(shù)據(jù)集中至少存在另一個對象Oj，使得sim(Oi，Oj)≥δ。那么對象Oi稱為對象集合D中關(guān)于δ的相似對象。

在特異群組挖掘問題中，由于大部分數(shù)據(jù)對象都是不相似的，只有群組中的對象才是相似對象，表現(xiàn)出相異于大部分對象的特性，因此，在特異群組挖掘問題中，相似對象被稱為特異對象，特異對象的集合記為P，剩下不在P中的對象記為DP。相應(yīng)地，度量數(shù)據(jù)對象是否為相似對象的相似性函數(shù)被稱為特異度度量。特異度度量是定義一個特異群組的基礎(chǔ)。

對于一個數(shù)據(jù)集，形成特異群組集合的數(shù)據(jù)對象相對整個數(shù)據(jù)集中的數(shù)據(jù)對象是少數(shù)的。在很多情況下，指定合適的相似性閾值對用戶而言是困難的。例如，在證券市場合謀操縱賬戶挖掘中，多個賬戶在一定時間段內(nèi)的多次相同交易行為是價格操縱的基本行為。簡單直觀地，可以以相同交易行為的數(shù)量l來定義兩個賬戶的相似度，用這個數(shù)量作為相似性閾值。然而，在實際實施過程中，這個相似性閾值對用戶而言是困難的。

但是，對于特異群組挖掘需求而言，用戶更容易知道的是他們希望發(fā)現(xiàn)的特異對象的數(shù)量。例如，作為證券監(jiān)管者，希望發(fā)現(xiàn)的是涉嫌操縱股價的賬戶數(shù)量。進一步，特異群組挖掘問題是挖掘“少量”數(shù)據(jù)對象構(gòu)成的特異群組，一般觀點認為20%已經(jīng)很少了，但在許多應(yīng)用中，如證券市場合謀操縱賬戶挖掘這個例子中，10%都不是“少量”，操縱賬戶可能小于0.2%或更小，才被認為是“少量”，這個數(shù)量完全由實際問題的用戶理解所決定。例如，用戶可以根據(jù)預(yù)算的經(jīng)費和時間等指定其期望的特異對象數(shù)量。同時，這也是用戶的直接需求，用戶易于理解和指定。于是，對特異群組挖掘問題進行定義。

定義2 （τ-特異群組挖掘）特異群組挖掘是在一個數(shù)據(jù)集中發(fā)現(xiàn)特異群組的過程，這些特異群組形成的集合包含τ個數(shù)據(jù)對象，τ是一個相對小的值（τ＜＜n×50%，n是數(shù)據(jù)集中對象總個數(shù)）。

性質(zhì)1 （相似性閾值的存在性）給定一個特異對象的數(shù)量的閾值τ，存在一個潛在的相似性閾值δ，對于τ個特異對象形成的集合P中每一個對象O，都存在至少另一個對象Q與其相似，sim(O，Q)≥δ。

性質(zhì)1說明了數(shù)據(jù)集中具有相似性的數(shù)據(jù)對象（特異對象）的數(shù)量τ可以反映數(shù)據(jù)集中對象間的相似性閾值，即選擇一個特異對象數(shù)量作為代替相似性閾值的方法是合適的。

特異對象的數(shù)量τ不僅易于用戶描述其需求，而且因為τ相對較小，算法可以利用τ設(shè)計剪枝策略，以提高大數(shù)據(jù)集特異群組挖掘算法的效率。

定義3 （對象的特異度評分，特異對象）一個對象Oi的特異度評分ω是Oi和該數(shù)據(jù)集中其他對象間的最大相似性值，即ω(Oi)=maxl≤j≤n,j≠iS(Oi,Oj)，其中S(Oi,Oj)表示對象Oi和Oj的相似性度量值。

給定一個特異度評分閾值δ＞0，當一個對象O的特異度評分ω(Oi)＞δ，則該對象O是一個特異對象。表示在整個數(shù)據(jù)集中特異對象的集合。

在特異度評分定義的基礎(chǔ)上，定義特異群組。

定義4 （特異群組）一個特異對象的集合G是一個候選特異群組，當且僅當|G|≥2，并且G中的每兩個對象都是相似的，即對于Oi，Oj∈G，有S(Oi,Oj)|≥δ。如果不存在任何一個G的超集是一個候選特異群組，那么G是一個特異群組。

特異群組的緊致性度量如下。

定義5 （緊致性）一個特異群組G的緊致性ζ是該群組中所有對象的總體特異度評分之和，即

前已述及，特異度評分閾值δ在實際應(yīng)用中用戶是很難設(shè)置的。為了克服這個困難，用戶可以設(shè)置一個特異群組集合的對象總數(shù)閾值τ，這對于用戶以及特異群組挖掘問題本身而言是一個容易設(shè)置和接受的閾值。這兩個閾值（τ和δ）之間的關(guān)系如下。

給定一個相對小的閾值τ（τ≥2）（特異群組集合中的對象個數(shù)相對較少，因此τ的值相對較?。?，可以找到具有最高特異度評分的τ個對象。那么，第τ個對象的特異度評分就是相應(yīng)的特異度評分閾值δ，即這τ個對象具有最高的特異度評分值，并且包含τ個對象的特異群組集的緊致度最大。

在對象特異度評分定義基礎(chǔ)上，給出進一步深化的特異群組挖掘任務(wù)定義。

定義6 （τ-特異群組挖掘）特異群組挖掘問題是找到數(shù)據(jù)集中所有的特異群組，滿足特異群組集合的緊致度最大，且||=τ，其中τ（τ≥2）是一個給定閾值。

4 特異群組挖掘框架算法[4]

對于τ-特異群組挖掘問題，傳統(tǒng)的聚類算法無法直接使用。因為，聚類算法通常要求用戶指定一個相似性閾值（或相關(guān)參數(shù)），而這樣的限制不能保證結(jié)果中相似對象的數(shù)量滿足閾值τ。一種修改是通過多次調(diào)用聚類算法調(diào)整參數(shù)值，終止的條件是當簇中對象的數(shù)量滿足用戶指定的數(shù)量τ。但是，由于重復(fù)多次的聚類算法調(diào)用，造成大量冗余的計算。更壞的情況是，當多個參數(shù)之間相關(guān)時，這是相當困難的。雖然，層次聚類方法看上去能夠簡單地使用一個對象數(shù)量的閾值作為參數(shù)提前終止聚類，且易于處理任何形式的相似性。然而，對象間相似性的計算具有相當高的復(fù)雜度[12]。

還有一些聚類算法給出如何選擇參數(shù)閾值的指導(dǎo)（如DBSCAN算法中的MinPts=4[13]）或者自動調(diào)整參數(shù)閾值（如SynC算法[14]）。但是，對于一般用戶，根據(jù)參數(shù)閾值指導(dǎo)選擇參數(shù)仍然是一項困難的工作，并且算法推薦的默認值在很多情況下并不適合，因此用戶仍然必須做出許多嘗試；而自動參數(shù)調(diào)整方法在某些應(yīng)用場景中會顯示出局限性，例如當為了滿足特異群組中用戶指定數(shù)量τ對象時，自動策略如SynC中的MDL（minimum description length）原則并不適合。此外，Top-c聚類[15]是一種試圖將相似性度量閾值轉(zhuǎn)化為簇個數(shù)的聚類算法，即將數(shù)據(jù)集中的數(shù)據(jù)對象劃分到符合簇質(zhì)量定義的c個簇中，然而，簇的數(shù)量c并不能決定對象的數(shù)量，即c個簇可能包含數(shù)據(jù)集中大量的數(shù)據(jù)對象（如70%）。

因此，簡單地修改聚類算法處理τ-特異群組挖掘問題不是很好的解決方案，原因是兩者的目的不同。

值得指出的是，Gupta等提出bregman bubble clustering（BBC）算法[16]挖掘c個密集的簇，包含τ個對象，這和特異群組挖掘問題的出發(fā)點相似。然而，一方面，BBC算法需要指定c個簇的代表點，然后將對象指定到與代表點相近的對象中，直到τ個點被聚類。對于用戶而言指定這樣的代表點是困難的；另一方面，BBC試圖同時限制對象的數(shù)量和簇的數(shù)量c，因此又遇到了τ個對象必須劃分到c個簇的困境。

考慮到上述問題，下面給出一個特異群組挖掘（abnormal group mining, AGM）框架算法。該算法是一個兩階段算法[4]，如圖3所示。第一階段是找到給定數(shù)據(jù)集中的最相似的數(shù)據(jù)對象對，并采用剪枝策略將不可能包含特異對象的對象對刪除，然后從候選對象對中計算得到特異對象；第二階段將對象對劃分到特異群組中。

圖3 τ-特異群組挖掘算法框架[4]

在第一階段，采用Topk相似點對查詢策略找到Topk個相似點對，在這些相似點對中的對象被認為是候選對象。不難證明，k與τ之間的關(guān)系為k=τ×(τ-1)/2。因為τ是一個相對小的數(shù)，對于較小的k，具有剪枝策略的Topk相似點對查詢算法[17～19]有良好的運行效率。即使對于高維數(shù)據(jù)對象，相似點對查詢算法復(fù)雜度也可以降到O（（dn/B）1.5）[18]，其中d為數(shù)據(jù)對象的維度，n為數(shù)據(jù)對象集中對象數(shù)，B為數(shù)據(jù)集所在外存頁字節(jié)數(shù)。之后，在獲得的Topk個點對中找到Topτ個具有最大特異度評分的對象作為特異對象。

在第二階段，根據(jù)特異群組定義，特異群組中的每對對象之間必須相似，因此特異群組事實上是一個最大團，采用最大團挖掘算法[20，21]將所有的τ個特異對象劃分到相應(yīng)的特異群組中。最大團挖掘的最壞情況時間復(fù)雜度為O（3τ/3）[21]（τ為圖的頂點數(shù)），因為特異群組挖掘算法第一階段的輸出為Topτ個對象，而τ是一個相對較小的數(shù)，因此，對τ個數(shù)據(jù)對象集發(fā)現(xiàn)其最大團而言，特異群組挖掘算法具有較好效率。

5 特異群組挖掘應(yīng)用

行為數(shù)據(jù)反映了人類的各種行為方式，這些行為通常是個體對象主動的行為（如股票交易、看病就醫(yī)、通勤出行、購物等），一般情況下，行為對象具有個體性。因此，如果有兩個或兩個以上的對象長時間存在共同的行為，說明這些對象具有群體組織性，有別于通常大部分對象的個體性，這些群體是異?，F(xiàn)象。特異群組挖掘就是在眾多行為對象中找到那些少數(shù)對象群體，這些行為對象具有一定數(shù)量的相同或相似行為模式，表現(xiàn)出相異于大多數(shù)對象而形成異常的群組，目前已有相當?shù)膽?yīng)用。

（1）證券市場操縱行為挖掘

老鼠倉“馬樂案”中，原博時基金經(jīng)理馬樂利用任職優(yōu)勢，與他人共同操作其親友等開立的一批賬戶（關(guān)系賬戶自然人趙秋怡、疑似隱匿于銀河證券客戶信用交易擔(dān)保證券賬戶等），先于或同步于其管理的博時基金多次買入、賣出相同個股（與博時精選基金相關(guān)的“眾生藥業(yè)”、“迪威視訊”等多支股票），如圖4所示。這些賬戶隱蔽性強，在過程中沒有散發(fā)傳播虛假消息，也沒有可供披露的提升上市公司價值的經(jīng)營活動等，難以甄別，查處成本高。

然而，這批賬戶通常在多天具有共同的股票交易行為，且異于其他大多數(shù)賬戶，是一種異?，F(xiàn)象，形成特異群組。因此，特異群組挖掘技術(shù)將有助于發(fā)現(xiàn)這些可疑賬戶。

（2）醫(yī)療保險中的保費欺詐行為挖掘[3]

我國基本醫(yī)療保險中，參保人使用醫(yī)?？ň歪t(yī)發(fā)生費用時，由醫(yī)?；鹬Ц夺t(yī)保范圍內(nèi)的費用，超出醫(yī)保范圍的費用才需要個人現(xiàn)金支付。為保證醫(yī)保基金的正常安全運轉(zhuǎn)，醫(yī)保機構(gòu)對參保人醫(yī)保消費行為有一定的限制，如參保人只能消費與病情和處方相關(guān)的藥品，而不允許超范圍配藥，個人醫(yī)保費用只允許用于本人就診、購藥等。由于每張醫(yī)?？ǖ氖褂孟拗疲环N典型的用卡欺詐行為是“醫(yī)?？ㄌ赚F(xiàn)”，即嫌疑者使用多張醫(yī)?？ǐ@得盡可能多的藥品，然后賣出獲取利益。正常情況下，個人使用醫(yī)?？ň歪t(yī)是個體行為，因此嫌疑者使用一批醫(yī)?？ǎ炊鄠€醫(yī)保卡賬戶）多天在多個或同一個醫(yī)院進行刷卡購買藥品的行為是一種異?，F(xiàn)象。醫(yī)保監(jiān)督局希望能夠找到這樣的欺詐行為賬戶予以監(jiān)管。圖5是特異群組挖掘算法在上海市醫(yī)保基金風(fēng)險防控中的應(yīng)用展示。圖5（a）展示了7個特異群組，并給出了每個特異群組在多少天（“群組長度”）有一致的行為，“包含卡數(shù)”表示該群組中的特異對象；圖5（a）的右下方還給出了有特異群組出現(xiàn)的一些醫(yī)院示例。圖5（b）將第一群組中的5個特異對象展開（考慮到隱私，已隱去身份證號，并且醫(yī)?？ㄌ柡托彰沧隽艘欢ǖ拿撁籼幚恚?。圖5（b）也展示了這些特異群組所持醫(yī)?？ㄒ话闾赚F(xiàn)的藥品名稱和費用。

圖4 “老鼠倉”可疑賬戶及操縱的股票[22]

圖5 醫(yī)療保險中的保費欺詐行為挖掘

（3）智能交通監(jiān)控應(yīng)用中的駕車犯罪團伙挖掘

以汽車為作案工具的犯罪案件中，一種常見的情況是多輛汽車共同參與作案。作案車輛為熟悉作案地點和行程，通常會提前準備，在多天內(nèi)共同出現(xiàn)在多個地點，隨著智能交通技術(shù)的發(fā)展，這些信息都將由高清攝像頭識別記錄。由于城市道路上的車輛行駛以個體行為為主，因此這種有一批車輛在多天共同出現(xiàn)在多個監(jiān)控點的行為是一種異?，F(xiàn)象。警察機關(guān)希望能夠從監(jiān)控數(shù)據(jù)庫中挖掘到這些車輛，為案件偵破提供線索[3]。圖6是特異群組挖掘算法在上海市寶山公安分局關(guān)于跟車行為檢測中的應(yīng)用展示，通過挖掘可以得到在多天共同出現(xiàn)在多個監(jiān)控點的異常車輛群組（考慮到隱私，圖6中的車牌數(shù)據(jù)也進行了一定的脫敏處理）。

（4）電子商務(wù)交易中的信譽欺詐挖掘

大多數(shù)在線交易平臺（如eBay.com和Taobao.com）都已建立交易雙方的信用評分系統(tǒng)。對賣家而言，更高的信用等級將帶來更多買家，然而，從低等級到高等級需要經(jīng)過較長時間積累大量的交易。于是，一些賣家采用“刷信用”方式賺取高等級的信用評分。提供“刷信用”服務(wù)的嫌疑者（甚至是專門的“刷信用”公司）通常申請一批賬號與所服務(wù)賣家事先商定，在不進行實際交易的方式下給出好的信用評分。同時，這批賬號又為其他多個賣家“刷信用”。相比所有在線客戶，“刷信用”賬號數(shù)量是相對較少的。因此，如果一組賬戶總是給大量相同的賣家好的信用評分，那么這組賬戶是可疑的。發(fā)現(xiàn)這些可疑賬戶將為交易平臺信譽欺詐檢測提供幫助。

（5）社會網(wǎng)絡(luò)中的小群體發(fā)現(xiàn)

Leskovec等人發(fā)現(xiàn)社會網(wǎng)絡(luò)中，社區(qū)變得越大，社區(qū)成員的交流卻開始變得更少[23]。因此，在這樣龐大的社會網(wǎng)絡(luò)中識別交流更加密集的小社區(qū)變得更有意義，雖然他們僅僅包含非常少的節(jié)點，即真正具有成為社區(qū)趨勢的對象數(shù)量相對整個社會網(wǎng)絡(luò)的節(jié)點而言是少部分。在大規(guī)模的社會網(wǎng)絡(luò)中挖掘小社區(qū)群體屬于特異群組挖掘問題。

圖6 公安系統(tǒng)跟車行為檢測

（6）論文抄襲檢測

大多數(shù)論文都是不相同的，但是仍然存在一些抄襲的論文。例如，幾篇論文抄襲同一篇，或者A抄襲B，B抄襲C，甚至出現(xiàn)專門的論文代寫公司，這些抄襲的論文事實上構(gòu)成一系列的特異群組。然而，現(xiàn)有的Similarity Join方法[24]目的只是發(fā)現(xiàn)抄襲論文的對象對，而不能發(fā)現(xiàn)多篇抄襲論文形成的特異群組。

除了在社會行為科學(xué)研究中特異群組挖掘具有廣泛的應(yīng)用背景，科學(xué)研究領(lǐng)域（如生命科學(xué)研究）產(chǎn)生的科學(xué)數(shù)據(jù)也有著重要的價值。

（7）在生命科學(xué)研究中的特異群組挖掘

生物學(xué)家總是希望對實驗收集的基因或蛋白質(zhì)序列進一步分析，如識別蛋白質(zhì)序列所屬的家族。聚類是常用的方法，然而這些方法總是有大量的假陽性。這是因為，在一些實驗收集的序列數(shù)據(jù)集中，僅僅少部分序列可能是相似的。盡管如此，傳統(tǒng)的聚類方法將大部分序列劃分到簇中。例如，Zheng等人指出許多人類轉(zhuǎn)錄因子（transcription factor，TF）僅僅能調(diào)控幾個甚至一個下游基因[24]（如TF adenosine deaminase domain-containing protein2（ADAD2）僅僅調(diào)控下游基因MUC5AC，而actin filament-associated protein 1-like 1（AFAP1L1）僅僅調(diào)控基因CAV1）。因此，如果一個生物學(xué)家收集一個基因表達數(shù)據(jù)集，大多數(shù)下游基因被不同的TF調(diào)節(jié)，而僅僅少部分由相同的TF調(diào)節(jié)。當研究調(diào)控機制時，發(fā)現(xiàn)少部分被相同TF調(diào)控的基因形成的簇更為合理，而不是聚類所有的數(shù)據(jù)對象。參考文獻[4]對特異群組挖掘算法進行了性能評估實驗，對比的算法主要是經(jīng)典的聚類算法DBSCAN、BBC、SynC以及基于無剪枝的數(shù)據(jù)對象兩兩比對的NavAllPairs算法，如圖7所示。重疊分數(shù)（overlapping score，OS）是被預(yù)測出的群組中的數(shù)據(jù)對象與已知類中的數(shù)據(jù)對象匹配的數(shù)量比例。ARI（adjusted rand index）是Hubert等提出的一種常用的有效性度量指標[26]，評估預(yù)測群組與已知類的一致程度。實驗結(jié)果表明，從效率上看，特異群組挖掘算法的運行時間隨著數(shù)據(jù)對象數(shù)量的增長變化不大，具有較高的可伸縮性，而其他算法的運行時間增長較快；在有效性方面，在相似對象密集的情況（即τ的值越小的情況）下，有效性越高，這進一步說明，特異群組挖掘算法對于高價值、低密度的數(shù)據(jù)集具有更好的性能。

此外，在公共安全方面發(fā)現(xiàn)突發(fā)群體事件，在社交網(wǎng)絡(luò)大數(shù)據(jù)中發(fā)現(xiàn)影響安全、和諧網(wǎng)絡(luò)環(huán)境的特異群體等都是大數(shù)據(jù)特異群組挖掘的應(yīng)用需求。通過對特異群組挖掘與利用，減少欺詐行為，提高監(jiān)管力度，提升公共安全管理和應(yīng)急響應(yīng)能力，幫助政府節(jié)省開支。

6 結(jié)束語

特異群組挖掘是大數(shù)據(jù)的一個重要任務(wù)。本文討論了特異群組挖掘任務(wù)在問題定義、算法實現(xiàn)和應(yīng)用等方面與聚類、異常檢測之間的差異，指出挖掘的需求決定了簇、特異群組、異常點的本質(zhì)，表明了相似性理論是大數(shù)據(jù)挖掘技術(shù)研究的基礎(chǔ)和關(guān)鍵；給出了一個易于理解和應(yīng)用的特異群組挖掘任務(wù)的形式化描述及其實現(xiàn)算法；描述了特異群組挖掘的一些應(yīng)用領(lǐng)域，實現(xiàn)大數(shù)據(jù)價值。

值得指出的是，聚類、特異群組挖掘、異常檢測都是基于數(shù)據(jù)對象的相似性來挖掘數(shù)據(jù)對象的。對于給定的數(shù)據(jù)集和相似性定義，如果相似點的數(shù)量遠大于孤立點的數(shù)量，對應(yīng)的相似點集是聚類的結(jié)果簇，而孤立點是異常檢測需要找出的數(shù)據(jù)對象；如果相似點的數(shù)量遠小于孤立點的數(shù)量，相似點構(gòu)成的組就是特異群組。相似點集挖掘是未來的一個重要研究方向。

圖7 在生物數(shù)據(jù)集上特異群組挖掘算法性能[4]

[1] 朱揚勇, 熊赟. 大數(shù)據(jù)是數(shù)據(jù)、技術(shù)，還是應(yīng)用. 大數(shù)據(jù), 2015007 Zhu Y Y, Xiong Y. Defining big data. Big Data Research, 2015007

[2] Mark B. Gartner says solving ‘big data’ challenge involves more than just managing volumes of data. http://www. gartner.com/newsroom/id/1731916, 2011

[3] Xiong Y, Zhu Y Y. Mining peculiarity groups in day-by-day behavioral datasets. Proceedings of IEEE International Conference on Data Mining (ICDM’09), Miami, Florida, USA, 2009: 578～587

[4] Xiong Y, Zhu Y Y, Yu Philip S,et al. Towards cohesive anomaly mining. Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI-13), Bellevue, Washington, USA, 2013

[5] 朱揚勇, 熊赟. 數(shù)據(jù)挖掘新任務(wù): 特異群組挖掘.中國科技論文在線, http://www.paper. edu.cn/releasepaper/content/201111-463, 2011 Zhu Y Y, Xiong Y. Peculiarity group mining: a new task in data mining. Science Paper Online, http://www.paper.edu.cn/ releasepaper/content/201111-463, 2011

[6] Jain A K. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 2010, 31(8): 651～666

[7] Tan P N, Steinbach M, Kumar V. Introduction to Data Mining. Boston: Addison-Wesley, 2006

[8] Hawkins D. Identification of Outliers. London: Chapman and Hall, 1980: 2～26

[9] Chandola V, Banerjee A, Kumar V. Anomaly detection: a survey. ACM Computing Surveys, 2009, 41(3): 1～58

[10] Papadimitriou S, Kitagawa H, Gibbons P B. Loci: fast outlier detection using the local correlation integral. Proceedings of the 19th International Conference on Data Engineering, Bangalore, India, 2003, 315～327

[11] Liu F T, Ting K M, Zhou Z H. On detecting clustered anomalies using SCiForest. Proceedings of ECML/PKDD, Barcelona, Spain, 2010: 274～290

[12] Dettling M, Buhlmann P. Supervised clustering of genes. Genome Biology, 2002, 3(12): 129～137

[13] Ester M, Kriegel H P, Sander J. A densitybased algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, Portland, USA, 1996: 226～231

[14] Bohm C, Plant C, Shao J. Clustering by synchronization. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2010: 583～592

[15] Jiang D X, Pei J, Zhang A D. A general approach to mining quality patternbased clusters from microarray data. Proceedings of DASFAA, Beijing, China, 2005: 188～200

[16] Gupta G, Ghosh J. Bregman bubble clustering: a robust, scalable framework for locating multiple, dense regions in data. Proceedings of the 6th International Conference on Data Mining, Hong Kong, China, 2008: 232～243

[17] Corral A, Manolopoulos Y, Theodoridis Y. Algorithms for processing k-closestpair queries in spatial databases. Data & Knowledge Engineering Journal, 2004(49): 67～104

[18] Tao Y F, Yi K, Sheng C,et al. Efficient and accurate nearest neighbor and closest pair search in high-dimensional spase. ACM Transactions on Database Systems, 2010, 35(3):1～46

[19] Xiong Y, Zhu Y Y, Yu Philip S. Top-k similarity join in heterogeneous information networks. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(6): 1710～1723

[20] Cheng J, Ke Y P, Fu A W. Finding maximal cliques in massive networks. ACM Transactions on Database Systems, 2011, 36(4): 1～34

[21] Tomita E, Tanaka A, Takahashi H. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 2006, 363(1):28～42

[22] 趙迪. 原博時基金經(jīng)理馬樂“老鼠倉”深度調(diào)查. 股市動態(tài)分析, 2013 Zhao D. The in-depth investigation of Ma Le “rat trading” at bosera select equity investment fund. Journal of Dynamic Analysis in Stock Market, 2013

[23] Leskovec J, Lang K J, Mahoney M W. Empirical comparison of algorithms for network community detection. Proceedings of the 19th International World Wide Web Conference, Raleigh, North Carolina, USA, 2010: 631～640

[24] Feng J, Wang J, Li G. Trie-join: a trie-based method for efficient string similarity joins. The VLDB Journal, 2012, 21(4): 437～461

[25] Zheng G Y, Tu K, Yang Q. ITFP: an integrated platform of mammalian transcription factors. Bioinformatics, 2008, 24(20): 2416～2417

[26] Hubert L, Arabie P. Comparing partitions. Journal of Classification, 1985, 2(1):193～218

熊赟，女，博士，復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院副教授。2004年起從事數(shù)據(jù)領(lǐng)域方面的研究工作，作為項目負責(zé)人主持國家自然科學(xué)基金、上海市科委發(fā)展基金以及企業(yè)合作項目。相關(guān)研究成果在本領(lǐng)域國際權(quán)威期刊或會議發(fā)表論文30 余篇，出版專著2 本。目前研究方向為數(shù)據(jù)科學(xué)、大數(shù)據(jù)。

朱揚勇，男，博士，復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院教授、學(xué)術(shù)委員會主任，上海市數(shù)據(jù)科學(xué)重點實驗室主任。1989年起從事數(shù)據(jù)領(lǐng)域研究，2008年提出數(shù)據(jù)資源保護和利用，2009年發(fā)表了數(shù)據(jù)科學(xué)論文“Data explosion, data nature and dataology”，并出版專著《數(shù)據(jù)學(xué)》，對數(shù)據(jù)科學(xué)進行了系統(tǒng)探討和描述。2010年創(chuàng)辦了“International workshop on dataology and data science”，2014年和石勇、張成奇共同創(chuàng)辦了“International conference on data science”。第462次香山科學(xué)會議“數(shù)據(jù)科學(xué)與大數(shù)據(jù)的理論問題探索”的執(zhí)行主席?！洞髷?shù)據(jù)技術(shù)與應(yīng)用叢書》主編。目前研究方向為數(shù)據(jù)科學(xué)、大數(shù)據(jù)。

Xiong Y, Zhu Y Y. Abnormal group mining: framework and applications. Big Data Research, 2015020

Abnormal Group Mining: Framework and Applications

Xiong Yun1,2, Zhu Yangyong1,2

1. School of Computer Science, Fudan University, Shanghai 201203, China;

2. Shanghai Key Laboratory of Data Science, Fudan University, Shanghai 201203, China

Abnormal groups can be found in a wide range of areas. Together with clustering and outlier detection, their goals are all to partition a data set according to data similarity. However, abnormal group mining (AGM) is different in problem definition, algorithm design and applications. To the best of our knowledge, the abnormal group mining problem was investigated systematically. The differences among AGM, clustering and outlier detection were analyzed. The formalized definitions on AGM and a framework algorithm were presented, and several interesting applications were particularized.

big data, data mining, abnormal group, clustering, outlier detection, data similarity

10.11959/j.issn.2096-0271.2015020

2015-06-24

國家自然科學(xué)基金資助項目（No.61170096，No.71331005）

Foundation Items:The National Natural Science Foundation of China Projects (No.61170096, No.71331005)

熊赟，朱揚勇. 特異群組挖掘：框架與應(yīng)用. 大數(shù)據(jù), 2015020