數(shù)據(jù)挖掘 特異群組挖掘的框架與應(yīng)用

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

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)合操縱）、基金“老鼠倉”等。這些賬戶以獲取不正當(dāng)利益為目的，集中資金優(yōu)勢(shì)或利用信息優(yōu)勢(shì)，操縱交易量、交易價(jià)格，擾亂市場(chǎng)秩序。其中，合謀操縱的行為模式主要是集中資金優(yōu)勢(shì)、持股優(yōu)勢(shì)進(jìn)行市場(chǎng)操縱，通過使用多個(gè)賬戶進(jìn)行分工交易、分倉持有來合謀操縱市場(chǎng)價(jià)格和成交量，以誘導(dǎo)其他投資者；基金“老鼠倉”的行為模式是通過獲悉基金即將或正在交易某投資標(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ì)象間的相似程度來劃分?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ì)象的集合?？梢钥闯觯哂心撤N共同性質(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è)Fd為d-維特征空間，D={O1, O2,…, Oi,…,On}是對(duì)象集合，Oi∈Fd。兩個(gè)對(duì)象Oi和Oj間的相似性f由相似性函數(shù)sim(Oi，Oj) 計(jì)算（0≤f≤1）。

定義1 （相似對(duì)象）給定一個(gè)相似性閾值δ，對(duì)于一個(gè)對(duì)象Oi（Oi∈D），如果數(shù)據(jù)集中至少存在另一個(gè)對(duì)象Oj，使得sim(Oi，Oj)≥δ。那么對(duì)象Oi稱為對(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à)格操縱的基本行為。簡單直觀地，可以以相同交易行為的數(shù)量l來定義兩個(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ì)小的值（τ

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

性質(zhì)1說明了數(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ì)象間的最大相似性值，即ω(Oi)=maxl≤j≤n, j≠iS(Oi,Oj)，其中S(Oi,Oj)表示對(duì)象Oi和Oj的相似性度量值。

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

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

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

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

定義5 （緊致性）一個(gè)特異群組G的緊致性ζ是該群組中所有對(duì)象的總體特異度評(píng)分之和，即ζ=Σi=1Gω(Oi)( Oi∈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)的聚類算法無法直接使用。因?yàn)?，聚類算法通常要求用戶指定一個(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)困難的。雖然，層次聚類方法看上去能夠簡單地使用一個(gè)對(duì)象數(shù)量的閾值作為參數(shù)提前終止聚類，且易于處理任何形式的相似性。然而，對(duì)象間相似性的計(jì)算具有相當(dāng)高的復(fù)雜度[12]。

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

值得指出的是，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ù)集所在外存頁字節(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ī)、通勤出行、購物等），一般情況下，行為對(duì)象具有個(gè)體性。因此，如果有兩個(gè)或兩個(gè)以上的對(duì)象長時(shí)間存在共同的行為，說明這些對(duì)象具有群體組織性，有別于通常大部分對(duì)象的個(gè)體性，這些群體是異?，F(xiàn)象。特異群組挖掘就是在眾多行為對(duì)象中找到那些少數(shù)對(duì)象群體，這些行為對(duì)象具有一定數(shù)量的相同或相似行為模式，表現(xiàn)出相異于大多數(shù)對(duì)象而形成異常的群組，目前已有相當(dāng)?shù)膽?yīng)用。

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

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

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

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

我國基本醫(yī)療保險(xiǎn)中，參保人使用醫(yī)?？ň歪t(yī)發(fā)生費(fèi)用時(shí)，由醫(yī)?；鹬Ц夺t(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)用只允許用于本人就診、購藥等。由于每張醫(yī)?？ǖ氖褂孟拗疲环N典型的用卡欺詐行為是“醫(yī)?？ㄌ赚F(xiàn)”，即嫌疑者使用多張醫(yī)?？ǐ@得盡可能多的藥品，然后賣出獲取利益。正常情況下，個(gè)人使用醫(yī)?？ň歪t(yī)是個(gè)體行為，因此嫌疑者使用一批醫(yī)?？ǎ炊鄠€(gè)醫(yī)?？ㄙ~戶）多天在多個(gè)或同一個(gè)醫(yī)院進(jìn)行刷卡購買藥品的行為是一種異常現(xiàn)象。醫(yī)保監(jiān)督局希望能夠找到這樣的欺詐行為賬戶予以監(jiān)管。圖5是特異群組挖掘算法在上海市醫(yī)?；痫L(fēng)險(xiǎn)防控中的應(yīng)用展示。圖5（a）展示了7個(gè)特異群組，并給出了每個(gè)特異群組在多少天（“群組長度”）有一致的行為，“包含卡數(shù)”表示該群組中的特異對(duì)象；圖5（a）的右下方還給出了有特異群組出現(xiàn)的一些醫(yī)院示例。圖5（b）將第一群組中的5個(gè)特異對(duì)象展開（考慮到隱私，已隱去身份證號(hào)，并且醫(yī)?？ㄌ?hào)和姓名也做了一定的脫敏處理）。圖5（b）也展示了這些特異群組所持醫(yī)?？ㄒ话闾赚F(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ù)庫中挖掘到這些車輛，為案件偵破提供線索[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í)將帶來更多買家，然而，從低等級(jí)到高等級(jí)需要經(jī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àn)椋谝恍?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以及基于無剪枝的數(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ù)量的增長變化不大，具有較高的可伸縮性，而其他算法的運(yùn)行時(shí)間增長較快；在有效性方面，在相似對(duì)象密集的情況（即τ的值越小的情況）下，有效性越高，這進(jìn)一步說明，特異群組挖掘算法對(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é)束語

特異群組挖掘是大數(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ì)象的相似性來挖掘數(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)集挖掘是未來的一個(gè)重要研究方向。