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

熊 赟^1,2，朱揚(yáng)勇^1,2

1. 復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203；

2. 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室（復(fù)旦大學(xué)） 上海 201203

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

關(guān)鍵詞：大數(shù)據(jù)；數(shù)據(jù)挖掘；特異群組；聚類；異常檢測(cè)；數(shù)據(jù)相似性

doi:10.11959/j.issn.2096-0271.2015020

Abnormal Group Mining: Framework and Applications

Xiong Yun^1,2,Zhu Yangyong^1,2

1. School of Computer Science, FudanUniversity, Shanghai 201203, China;

2. Shanghai KeyLaboratory of Data Science, Fudan University, Shanghai 201203,

China

Abstract: Abnormalgroups can be found in a wide range of areas. Together with clustering andoutlier detection, their goals are all to partition a data set according todata similarity. However, abnormal group mining (AGM) is different in problemdefinition, algorithm design and applications. To the best of our knowledge,the abnormal group mining problem was investigated systematically. Thedifferences among AGM, clustering and outlier detection were analyzed. Theformalized definitions on AGM and a framework algorithm were presented, andseveral interesting applications were particularized.

Key words: big data, data mining, abnormal group, clustering, outlier detection,data similarity

1引言

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

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

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

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

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

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

2.1 與聚類的比較

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

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

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

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

2.2 與異常檢測(cè)的比較

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

2.3 三者關(guān)系

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

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

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

設(shè)F^d為d-維特征空間，D={O₁, O₂,…, O_i,…,O_n}是對(duì)象集合，O_i∈F^d。兩個(gè)對(duì)象O_i和O_j間的相似性f由相似性函數(shù)sim(O_i，O_j) 計(jì)算（0≤f≤1）。

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

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

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

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

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

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

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

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

定義3 （對(duì)象的特異度評(píng)分，特異對(duì)象）一個(gè)對(duì)象Oi的特異度評(píng)分ω是Oi和該數(shù)據(jù)集中其他對(duì)象間的最大相似性值，即ω(O_i)=max_l≤j≤n,_j≠iS(O_i,O_j)，其中S(O_i,O_j)表示對(duì)象O_i和O_j的相似性度量值。

給定一個(gè)特異度評(píng)分閾值δ>0，當(dāng)一個(gè)對(duì)象O的特異度評(píng)分ω(O_i)>δ，則該對(duì)象O是一個(gè)特異對(duì)象。表示在整個(gè)數(shù)據(jù)集中特異對(duì)象的集合。

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

定義4 （特異群組）一個(gè)特異對(duì)象的集合G是一個(gè)候選特異群組，當(dāng)且僅當(dāng)|G |≥2，并且G中的每?jī)蓚€(gè)對(duì)象都是相似的，即對(duì)于O_i，O_j∈G，有S(O_i,O_j)|≥δ。如果不存在任何一個(gè)G的超集是一個(gè)候選特異群組，那么G是一個(gè)特異群組。

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

定義5 （緊致性）一個(gè)特異群組G的緊致性ζ是該群組中所有對(duì)象的總體特異度評(píng)分之和，即ζ=Σ_i=1^|G|ω(O_i)( O_i∈G)。

設(shè)是特異群組集，的緊致度是中所有特異群組緊致度之和。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）證券市場(chǎng)操縱行為挖掘

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

圖4 “老鼠倉(cāng)”可疑賬戶及操縱的股票^[22]

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

（2）醫(yī)療保險(xiǎn)中的保費(fèi)欺詐行為挖掘^[3]

我國(guó)基本醫(yī)療保險(xiǎn)中，參保人使用醫(yī)保卡就醫(yī)發(fā)生費(fèi)用時(shí)，由醫(yī)保基金支付醫(yī)保范圍內(nèi)的費(fèi)用，超出醫(yī)保范圍的費(fèi)用才需要個(gè)人現(xiàn)金支付。為保證醫(yī)保基金的正常安全運(yùn)轉(zhuǎn)，醫(yī)保機(jī)構(gòu)對(duì)參保人醫(yī)保消費(fèi)行為有一定的限制，如參保人只能消費(fèi)與病情和處方相關(guān)的藥品，而不允許超范圍配藥，個(gè)人醫(yī)保費(fèi)用只允許用于本人就診、購(gòu)藥等。由于每張醫(yī)保卡的使用限制，一種典型的用卡欺詐行為是“醫(yī)保卡套現(xiàn)”，即嫌疑者使用多張醫(yī)保卡獲得盡可能多的藥品，然后賣出獲取利益。正常情況下，個(gè)人使用醫(yī)保卡就醫(yī)是個(gè)體行為，因此嫌疑者使用一批醫(yī)保卡（即多個(gè)醫(yī)保卡賬戶）多天在多個(gè)或同一個(gè)醫(yī)院進(jìn)行刷卡購(gòu)買藥品的行為是一種異常現(xiàn)象。醫(yī)保監(jiān)督局希望能夠找到這樣的欺詐行為賬戶予以監(jiān)管。圖5是特異群組挖掘算法在上海市醫(yī)保基金風(fēng)險(xiǎn)防控中的應(yīng)用展示。圖5（a）展示了7個(gè)特異群組，并給出了每個(gè)特異群組在多少天（“群組長(zhǎng)度”）有一致的行為，“包含卡數(shù)”表示該群組中的特異對(duì)象；圖5（a）的右下方還給出了有特異群組出現(xiàn)的一些醫(yī)院示例。圖5（b）將第一群組中的5個(gè)特異對(duì)象展開（考慮到隱私，已隱去身份證號(hào)，并且醫(yī)保卡號(hào)和姓名也做了一定的脫敏處理）。圖5（b）也展示了這些特異群組所持醫(yī)保卡一般套現(xiàn)的藥品名稱和費(fèi)用。

圖5 醫(yī)療保險(xiǎn)中的保費(fèi)欺詐行為挖掘

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

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

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

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

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

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

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

（6）論文抄襲檢測(cè)

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)

[1] 朱揚(yáng)勇, 熊赟. 大數(shù)據(jù)是數(shù)據(jù)、技術(shù)，還是應(yīng)用. 大數(shù)據(jù), 2015007

Zhu Y Y, Xiong Y. Defining big data. Big DataResearch, 2015007

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

[3] Xion g Y, Z hu Y Y. Mining peculiarity groups inday-by-day behavioral datasets. Proceedings of IEEE International Conference onData 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 (A A A I-13), Bellevue, Washington, USA, 2013

[5] 朱揚(yáng)勇, 熊赟. 數(shù)據(jù)挖掘新任務(wù): 特異群組挖掘.中國(guó)科技論文在線, http://www.paper.edu.cn/releasepaper/content/201111-463, 2011

Zhu Y Y, Xiong Y. Peculiarity group mining: a newtask 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 toData 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: fastoutlier detection using the local correlation integral. Proceedings of the 19thInternational Conference on Data Engineering, Ba ngalore, 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 density-based algorithm for discoveringclusters in large spatial databases with noise. Proceedings of the 4th InternationalConference on Knowledge Discovery and Data Mining, Portland, USA, 1996: 226~231

[14]Bohm C, Plant C, Shao J. Clustering by synchronization. Proceedings of the 16thACM 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 pattern-basedclusters from microarray data . Proceedings of DASFAA, Beijing, China, 2005:188~200

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

[17]Corral A, Manolopoulos Y, Theodoridis Y. Algorithms for processingk-closest-pair 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 inhigh-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 heterogeneousinformation 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 . ACMTransactions on Database Systems, 2011, 36(4): 1~34

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

[22]趙迪. 原博時(shí)基金經(jīng)理馬樂“老鼠倉(cāng)”深度調(diào)查. 股市動(dòng)態(tài)分析, 2013

ZhaoD. The in-depth investigation of Ma Le “rat trading” at bosera select equity investmentfund. Journal of Dynamic Analysis in Stock Market, 2013

[23]Leskovec J, Lang K J, Mahoney M W. Empirical comparison of algorithms for networkcommunity detection. Proceeding s of the 19th International World Wide WebConference, Raleigh, North Carolina, USA, 2010: 631~640

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

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

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

---

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

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

---

總結(jié)

以上是生活随笔為你收集整理的《大数据》2015年第2期“研究”——特异群组挖掘：框架与应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。