數據挖掘 特異群組挖掘的框架與應用

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

1引言

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

圖1 大數據集里的特異群組

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

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

2 特異群組挖掘與聚類和異常檢測的關系

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

2.1 與聚類的比較

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

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

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

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

2.2 與異常檢測的比較

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

2.3 三者關系

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

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

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

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

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

在特異群組挖掘問題中，由于大部分數據對象都是不相似的，只有群組中的對象才是相似對象，表現出相異于大部分對象的特性，因此，在特異群組挖掘問題中，相似對象被稱為特異對象，特異對象的集合記為P，剩下不在P中的對象記為D\P。相應地，度量數據對象是否為相似對象的相似性函數被稱為特異度度量。特異度度量是定義一個特異群組的基礎。

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

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

定義2 （τ-特異群組挖掘）特異群組挖掘是在一個數據集中發現特異群組的過程，這些特異群組形成的集合包含τ個數據對象，τ是一個相對小的值（τ

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

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

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

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

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

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

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

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

定義5 （緊致性）一個特異群組G的緊致性ζ是該群組中所有對象的總體特異度評分之和，即ζ=Σi=1Gω(Oi)( Oi∈G)。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 特異群組挖掘應用

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

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

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

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

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

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

圖5 醫療保險中的保費欺詐行為挖掘

（3）智能交通監控應用中的駕車犯罪團伙挖掘

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

圖6 公安系統跟車行為檢測

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

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

（5）社會網絡中的小群體發現

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

（6）論文抄襲檢測

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

除了在社會行為科學研究中特異群組挖掘具有廣泛的應用背景，科學研究領域（如生命科學研究）產生的科學數據也有著重要的價值。

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

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

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

此外，在公共安全方面發現突發群體事件，在社交網絡大數據中發現影響安全、和諧網絡環境的特異群體等都是大數據特異群組挖掘的應用需求。通過對特異群組挖掘與利用，減少欺詐行為，提高監管力度，提升公共安全管理和應急響應能力，幫助政府節省開支。

6 結束語

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

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