一種自動聚類的離群點識別方法研究

黃強 葉青 聶斌 朱彥陳 郭永坤

摘? 要：針對傳統離群點識別方法對數據的分布形狀和密度有特定要求，需設定參數的問題，提出了一種自動聚類的離群點識別方法。該方法通過引入相互K近鄰數來表示數據對象的離群度，對數據的分布形狀、分布密度無要求，可以輸出全局離群點、局部離群點和離群簇；通過k次迭代來實現自動聚類，無需人為設定參數。通過合成數據以及UCI數據實驗，驗證了該方法的有效性、普適性。

關鍵詞：局部離群點；離群點識別；離群簇；自動聚類；數據挖掘

中圖分類號：TP301? ? 文獻標識碼：A? 文章編號：2096-4706（2023）07-0006-05

Abstract： Aiming at the problem that traditional outlier recognition methods have specific requirements for the distribution shape and distribution density of data and need to set parameters， an automatic clustering outlier recognition method is proposed. This method represents the outlier degree of data objects by introducing the mutual K-nearest neighbor number， with no requiring for the distribution shape and distribution density of the data， and can output global outliers， local outliers， and outlier cluster; Automatic clustering is achieved through k iterations， no need to manually set parameters. The effectiveness and universality of this method are verified through synthetic data and UCI data experiments.

Keywords： local outlier; outlier recognition; outlier cluster; automatic clustering; data mining

0? 引? 言

隨著信息技術和數據密集型科學的發展，離群點識別在很多領域得到研究和應用，比如醫療領域、污水站點監測、圖像異常檢測、網絡入侵檢測等[1-4]。

離群點是指與數據集中其他數據對象顯著偏離，像是產生于不同機制的數據對象[5]。離群點的類型有全局離群點、局部離群點和集體離群點，離群點識別方法可以大致分為基于統計的、基于距離的、基于密度的、基于聚類的四大類[6]。

基于統計的方法[7]假設數據服從某一分布，將不符合該分布特征的數據視為離群點。此類方法常用于數據分布已知的數據集[8]，但實際中的數據分布難以預知，也并非由單一分布組成。基于距離的離群點定義最早是由Knorr和Ng[9]提出的，由于算法思想簡單易懂、識別效果較好被廣泛地研究和應用?；诰嚯x的方法中的參數是基于全局的參數，沒有考慮到數據對象局部情況的不同，導致不能識別出局部離群點；且識別效果對參數敏感，不同的參數會有不同的識別效果?；诿芏鹊姆椒╗10-12]使用密度描述數據對象鄰域的疏密，能很好地識別出局部離群點，缺點是識別效果對算法參數敏感。

以上方法考慮了只存在單個離群點的情況，不適用于存在離群簇（集體離群點）的數據?；诰垲惖姆椒╗13-16]可以識別出數據中的離群簇，該類方法的思想是對數據進行聚類，不屬于任何類別的數據對象以及小類別內的所有數據對象被劃分為離群數據。如何區分大類和小類是一個問題，此外部分基于聚類的識別方法對參數敏感。

基于此，本文提出了一種自動聚類的離群點識別方法（Outlier Recognition Method Using Automatic Clustering， ORMUAC），該方法通過聚類自動的輸出離群點和離群簇，對數據對象的分布形狀和密度無要求，無需人為設定參數。ORMUAC使用相互K近鄰數衡量數據對象的離群度，數據對象的相互K近鄰數越少就越可能是離群點。相互K近鄰是一個非全局的參數，因此也可用于識別局部離群點。

1? 自動聚類的離群點識別方法

傳統離群點識別方法大都缺乏普適性，有些方法對數據的分布形狀或者密度分布有特定要求，無法識別出離群簇或者局部離群點；有些方法需要人為設定參數，增加了算法的使用難度?；诖?，本文提出了具有普適性的ORMUAC方法，該方法對數據的分布形狀和密度無要求，無需人為設定參數。在詳細介紹該算法前先闡述一些相關理論概念。

1.1? 相關概念

K近鄰：數據集d中，距離數據對象o最近的k個數據對象組成的集合稱為數據對象o的K近鄰，表示為：

Nk={ p|d（o， p）≤dk（o），p≠o}? ? ? ? ? ? ? ? ?（1）

其中，d（o， p）表示數據對象o和p之間的距離，dk（o）表示距離數據對象o第k近鄰的數據對象與數據對象o之間的距離。

相互K近鄰：當數據對象p屬于數據對象o的K近鄰，同時數據對象o屬于數據對象p的K近鄰時，數據對象p和數據對象o是相互K近鄰。表示為：

MN（o）={ p| p∈Nk （o），o∈Nk（ p）}? ? ? ? ? ? ? ? （2）

近鄰鏈接點：如果數據對象o的相互K近鄰個數不為零，那么數據對象o就稱作近鄰鏈接點。

基于相互K近鄰的離群點：如果數據對象o的相互K近鄰的個數為零，那么數據對象o被稱為基于相互K近鄰的離群點。

α離群簇：在數據完成聚類后，如果類內數據對象的個數小于閾值α，則組成該類的全部數據對象被稱為α離群簇。

文獻[17]中提到一個六度分離理論，該理論闡述為：任何兩個陌生人之間只要通過6個人就可以相互認識。在Facebook的一篇報告[18]中這個數字變成了4.74（數據范圍為全球），當把范圍縮小到一個國家時，人們之間的間隔度只有3度。這表明個體間存在一個間隔度值，當人能直接或間接認識到的人數小于這個值就無法認識更多的人，從而被隔離成為小眾。類比聚類，當某一數據對象的相互K近鄰個數小于閾值α時，這些數據對象就不能被劃到大類，變成離群簇。閾值α不是固定的，不同的數據環境有著不同的α值。

α值的確定：當自動聚類完成后，輸出的K值就是判別某一類是否為α離群簇的閾值α，如果類的數據對象個數小于α，將該類輸出為α離群簇。

當數據聚類的類別不再發生變化時，所有的數據對象都被正確歸類，數據聚類達到穩定狀態；這時對應的k值就是該數據集的間隔度α。

1.2? 算法原理與步驟

ORMUAC是通過近鄰鏈接點將相似的數據歸為一類，在所有數據被歸類之后，單獨成一類的數據對象被輸出為離群點，類內數據個數小于閾值α的小類則被輸出為α離群簇。ORMUAC算法流程分為兩部分，第一部分是自動聚類和輸出離群點，第二部分是輸出為α離群簇。

第一部分：從數據集D中隨機選擇一個數據對象o，判斷該數據對象是否為近鄰鏈接點。若不是，標記為離群點；否則，將數據對象o及其相互K近鄰標記為一類。接著遍歷數據對象o的相互K近鄰，如果數據對象o的相互K近鄰也為近鄰鏈接點，繼續遞歸訪問該近鄰鏈接點的相互K近

鄰；循環這一步驟，直到遍歷完所有近鄰鏈接點及其相互K近鄰，完成一次歸類。以同樣的方式繼續訪問數據集D中的下個未被訪問的數據對象，直至遍歷完數據集D中所有數據。

該如何給出合適相互K近鄰值。通過實驗發現小樣本數據集的k值一般低于25，本文采用迭代的方式找到合適的k值。k值從2到25迭代（實驗結果表明實際迭代次數平均約為12次，遠低于25次），當相鄰兩次的聚類輸出類別數相等時停止迭代，此時k值為最佳K近鄰值。迭代時會頻繁地計算數據對象的相互K近鄰，為減少開銷采用KD樹來存儲相互K近鄰。聚類前先掃描一遍數據集，建立25—近鄰KD樹，后續迭代時直接查找KD樹即可找出數據對象的任意K近鄰。自動聚類的步驟見算法1。

算法1：Auto-Clustering（D）

輸入：數據集D

輸出：聚類結果C=（C1，C2，…，Cn），k

1）初始化：I0=0，k=2，n=0。

2）掃描數據集D，將每個數據的25-近鄰數存儲到KD樹。

3）從數據集D中選取一個未被訪問的數據對象O。

4）通過查找KD樹，判斷O是否為近鄰鏈接點；若是，n=n+1，Cn=Cn∪MN（O）∪O，visited（O）=true，否則，輸出為離群點。

5）如果?P∈Cn并且visited（P）≠true，Cn=Cn∪MN（P），visited（P）=true，直到遍歷完Cn中所有未被訪問數據。

6）如果數據集D還有未被訪問的數據，跳到步驟3）。

7）當數據集D中數據全部遍歷完畢，將類別個數n賦值給Ik。

8）如果Ik≠Ik-1，k=k+1，將數據集D中數據的visited值設為false，跳到步驟3），否則，結束程序。

9）End。

第二部分：聚類完成之后，數據都被全部歸類，數據對象的間隔度α隨之確定，根據最終聚類結果確定并輸出α離群簇。ORMUAC具體步驟見算法2。

算法2：ORMUAC（D）

輸入：數據集D

輸出：離群點，離群簇

1）執行Auto-Clustering（D），輸出聚類結果C=C=（C1，

C2，…，Cn）、近鄰值k、離群點。

2）令α=k，如果|Ci|≤α，（i=1，2，…，n），將Ci輸出為離群簇。

3）End。

ORMUAC識別過程如圖1所示，相互K近鄰的k從2開始迭代聚類，k=2時聚類輸出類別數為8，k=3時輸出類別數為5，與k為4時的輸出類別數一致；此時聚類數目不再隨k增加而變化，即聚類達到穩定狀態。這意味著相互K近鄰k=3時的聚類結果為最佳輸出，將此時k值（k=3）賦予α，由于A類數據樣本數小于α，簇A被輸出為α離群簇，點p單獨成一類被輸出為離群點。

1.3? 算法復雜度分析

Auto-clustering算法通過KD樹來尋找數據對象的K近鄰，時間復雜度為O（N logN），遍歷數據集的時間復雜度為O（N），Auto-clustering的時間復雜度為O（N logN）+O（N）；ORMUAC在尋找最佳k值時需要迭代Auto-clustering算法k次，因此ORMUAC的時間復雜度為O（N logN）。

KD樹的空間復雜度為O（N），用于存儲類標記的數組長度為N，存儲相互K近鄰所占的空間長度小于KN，所以ORMUAC算法的空間復雜度為O（N）。

2? 實驗與分析

實驗部分將根據合成數據、真實數據的實驗結果來評估ORMUAC算法的性能，同時將K-means[13]和DBSCAN[14]兩種經典算法作為對照算法。采用召回率（R）、精確率（P）以及精確率和召回率的調和均值（F）作為衡量指標。評價指標R、P以及F的值域為[0，1]，數值越大實驗效果越好。

2.1? K值與樣本量關系實驗

根據UCI數據的k值實驗結果，圖2繪制了相互K近鄰值與數據集樣本量的關系圖。從圖中可以看出二者關系是非線性的，相互近鄰數k值隨著數據樣本量波動增加，k在樣本量為6 000時達到最大值24，隨后再減少。

雖然ORMUAC采用迭代方式來給出最佳k值，但迭代次數k較小；實驗結果表明當樣本量較小時，實際迭代次數平均約為12次，遠低于25次，不會造成算法時間復雜度的突增。另外，實際操作時k不用從2開始迭代，可根據樣本量設置合適初始k值以減少迭代次數。

2.2? 合成數據實驗

為驗證ORMUAC可行性和有效性，采用合成數據集進行對比實驗。3個數據集均為二維數據集，D1有4個類別，共118個數據，包含9個離群數據；D2只有一個類別，共有108個數據，其中含有8個離群數據；D3共有3個類別，共有357個數據，其中包含10個離群點，數據信息如表1所示。

為模擬真實數據情況和保證實驗的科學性，三種合成數據集的密度分布有均勻和不均勻的，形狀分布有球狀和非球狀的，數據類別有單類別和多類別的；各自都包含局部離群點、全局離群點以及離群簇。數據分布情況如圖3所示，空心點為離群數據，實心點為正常數據。

實驗過程中，K-means需要給定類別個數k、距離閾值d兩個參數，DBSCAN算法中需要給定距離閾值d和最少數據個數P兩個參數。實驗中設定的參數值均為使得兩種對比算法識別效果達到最佳時的參數值。

表2、表3和表4記錄了三種算法的合成數據實驗的實驗結果，從合成數據實驗結果可以知道：

1）D1數據集實驗中，DBSCAN識別效果較好，F值為0.941略低于ORMUAC；D1數據集中多數離群數據分布在中心位置導致K-means的識別結果最差，雖然p值為1，但F值卻低至0.5；ORMUAC表現最好，各項指標均為最高。

2）在單類別、多密度和包含環內離群點的D2數據集實驗中，因環形數據和分布中間數據的密度不同，導致DBSCAN的F值稍有降低為0.941。K-means根據數據對象距離質心的遠近來判斷數據是否為離群點，因而其在環形分布的D2中效果很不理想，F值僅為0.667；ORMUAC表現依舊最好。

3）對于分布非球狀、密度不均勻的D3數據集，DBSCAN的識別效果不佳，調和均值F僅為0.886；K-means雖然p值很高但調和均值僅為0.181，召回率R值低至0.1，意味其遺漏了大部分的離群點。RORMUAC則依然識別出了數據集中全部離群數據。

合成數據實驗表明：相較于對比算法ORMUAC能有效應用于分布多樣、密度不均的數據集，具有更好的普適性。

2.3? 真實數據實驗

為進一步驗證ORMUAC的有效性，選取來自UCI數據庫[19]的三組真實數據集，Iris、banknote authentication和Breast Cancer Wisconsin數據集的wdbc數據進行進一步對比實驗，數據信息詳如表5所示。

為更好地完成實驗，參照文獻[20，21]對數據集做了以下處理：Iris有三個類別，每類50個數據樣本；將其中一類全部50個數據對象作為正常點，從剩下兩類中各取5個數據對象作為離群點，構成第一組實驗數據（Iris）。banknote authentication有兩個類別，各自包含762和610個樣本；大類作為正常類別，再從小類中隨機取20個數據對象作為離群點，組成第二組實驗數據（Banknote）。wdbc有B和M兩個類別，各自包含357和212個數據樣本；將B類當作正常類別，再從M類中隨機取10個數據對象作為離群點，以此作為第三組實驗數據（wdbc）。

實驗結果如表6、7、8和圖4所示，實驗分析具體為：

1）Iris數據集實驗中，三種算法識別效果都還不錯，ORMUAC和DBSCAN表現一致，二者綜合指標F值均為0.953，K-means表現其次，綜合指標F值為0.909。

2）ORMUAC在Banknote數據實驗表現要優于另外兩種算法，其中P和R兩者指標值都要高于另外兩種算法，并且F值相對最高為0.869。

3）高維數據wdbc對比實驗中，K-means和DBSCAN的識別效果一致，指標P、R、F值分別為0.700、0.636和0.667，ORMUAC的表現依舊最好，P值、R值和F值為0.800、0.667、0.761均高于兩種對比算法。

真實數據實驗證明：相較對比算法ORMUAC識別準確率高有更好的識別效果，能夠更有效地應用于真實數據集。

為驗證ORMUAC的普適性和有效性，采用合成數據集和真實數據集做了驗證實驗。合成數據實驗中，ORMUAC能夠很好地適應分布形狀不規則、密度分布不均勻的數據，驗證了ORMUAC的普適性。真實數據實驗中ORMUAC的表現最佳，P、R和F值均為三種算法之中最高，進一步證明了ORMUAC的普適性和有效性。

圖4? 真實數據實驗結果

3? 結? 論

本文提出了一種自動聚類的離群點識別方法，該方法可自動識別出數據集中的全局離群點、局部離群點以及離群簇，且對數據的分布形狀、密度無要求，有著較強的普適性。理論分析與對比實驗證明了新方法能更有效應用于分布復雜且離群類型多樣的數據集。

接下來的研究可從優化新算法在高維、大數據集中的效率方面著手。

參考文獻：

[1] BRZEZI?SKA A N，HORY? C. Outliers in Covid 19 data based on Rule representation-the analysis of LOF algorithm [J].Procedia Computer Science，2021，192：3010-3019.

[2] 呂承侃，沈飛，張正濤，等.圖像異常檢測研究現狀綜述 [J].自動化學報，2022，48（6）：1402-1428.

[3] MOHAMMADPOUR L，LING T C，LIEW C S，et al. A Survey of CNN-Based Network Intrusion Detection [J].Applied Sciences，2022，12（16）：8162-8162.

[4] 黃彥斌，駱德漢，蔡高琰.基于電力數據分析的污水站點監測方法研究 [J].現代信息科技，2021，5（21）：121-125.

[5] HAWKINS D. Identification of outliers [M].London：Chapman and Hall，1980.

[6] 周玉，朱文豪，房倩，等.基于聚類的離群點檢測方法研究綜述 [J].計算機工程與應用，2021，57（12）：37-45.

[7] 黃旺華，王欽若.基于距離統計的有序紋理點云離群點檢測 [J].計算技術與自動化，2019，38（1）：139-144.

[8] 梅林，張鳳荔，高強.離群點檢測技術綜述 [J].計算機應用研究，2020，37（12）：3521-3527.

[9] KNORR E M，NG R T. Algorithms for Mining Distance-Based Outliers in Large Datasets [C]//Proceedings of the 24rd International Conference on Very Large Data Bases.San Francisco：Morgan Kaufmann Publishers Inc，1998：392-403.

[10] BREUNIG M M，KRIEGEL H P，NG R T，et al. LOF：Identifying Density-Based Local Outliers [EB/OL].[2022-10-28].https：//www.docin.com/p-291134797.html.

[11] HA J，SEOK S，LEE J S. Robust outlier detection using the instability factor [J].Knowledge-Based Systems，2014，63：15-23.

[12] SHAO M L，QI D Y，XUE H L. Big data outlier detection model based on improved density peak algorithm [J].Journal of Intelligent & Fuzzy Systems，2021，40（4）：6185-6194.

[13] 楊俊闖，趙超.K-Means聚類算法研究綜述 [J].計算機工程與應用，2019，55（23）：7-14+63.

[14] ESTER M，KRIEGEL H P，SANDER J，et al. A density-based algorithm for discovering clusters in large spatial data bases with noise [C]//Proceedings of the 2nd International Conference on Knowledge Discovering in Databases and Data Mining （KDD-96）.Massachusetts：AAAI Press，1996，226-232.

[15] GAN G J，NG M K P. K-means clustering with outlier removal [J].Pattern Recognition Letters，2017，90：8-14.

[16] HUANG J L，ZHU Q S，YANG L J，et al. A Novel Outlier Cluster Detection Algorithm without Top-n Parameter [J].Knowledge-Based Systems，2017，121：32-40.

[17] KERBY M，KERBY M. Six degrees of separation [J].AOPA pilot，2012，55（2），68-68.

[18] BACKSTROM L，BOLDI P，ROSA M，et al. Four Degrees of Separation [EB/OL].[2022-10-28].http：//snap.stanford.edu/class/cs224w-readings/backstrom12four.pdf.

[19] DUA D，GRAFF C. UCI Machine Learning Repository [EB/OL].[2022-10-28].http：//archive.ics.uci.edu/ml.

[20] HAWKIN S，HE H X，WILLIAMS G J，et al．Outlier Detection Using Replicator Neural NetworKs [C]//2000：Data Warehousing and Knowledge Discovery.France：Springer，2002：4-6.

[21] ZHU Q S，FAN X G，FENG J. Outlier detection based on K_Neighborhood MST [C]//2014 IEEE 15th International Conferenceon Information Reuse and Integration.Redwood City：IEEE，2014，718-724.

作者簡介：黃強（1993—），男，漢族，江西上饒人，助教，碩士，主要研究方向：數據挖掘、中醫信息學研究。