基于近鄰穩定性的離群點檢測算法

黃馨玉　陳曉東

摘要：本文提出了基于近鄰穩定性的離群點檢測算法。實驗證明本文提出的算法具有較高的精確度。

[關鍵詞]離群點鄰域質心不穩定因子

離群點是指那些明顯偏離其它數據、不滿足數據的一般模式或行為，與存在的其它數據不一致的數據。物理學中質心與穩定性間存在聯系，離質心越近的點，穩定性越強，反之穩定性越弱。JihyunHa等人受這一性質的啟發提出了使用不穩定因子的健壯離群點檢測算法（INS算法）。該算法容易將處于稀疏區域與稠密區域的交界處的正常點誤判為離群點。為解決該問題本文提出了基于近鄰穩定性的離群點檢測算法（NSINS算法）。

1基于近鄰穩定性的離群點檢測算法

1.1算法思想

本文提出了基于近鄰穩定性的離群點檢測算法。該算法的主要思想是：數據集中任意一"點p的k個最近鄰組成p的k個鄰域，其中第i個鄰域包含了p和距離p最近的前i個點。每個鄰域計算兩個質心。一個質心與p相關，即鄰域中包括點p時的質心;另一個質心與p無關，即鄰域中不包括點p時的質心。最后會得到兩類質心，每類都有k個。比較這兩類質心的位置變化，最終確定p的不穩定程度。定義與p無關的質心考慮到了近鄰的穩定性對p不穩定因子的影響。

1.2相關定義

定義1鄰域（neighborhood）。點p的鄰域表示距離點p最近的k個點的集合，用6：（p）表示，即：

其中d（p，q）表示p，q之間的距離，Pr是p的第k個最近鄰。當P點計入6r（p）中時，6.（p）的基數是k+1;當p點不計入6r（p）中時，6，（p）的基數是k。

定義2相關鄰域質心（relatedcentreofmass）。點p的相關鄰域質心表示p的鄰域包括點p時的質心，用rm，（p）表示：

其中（...q.）是點q在d維空間中的坐標。

定義3無關鄰域質心（unrelatedcentreofmass）。點p的無關鄰域質心表示p的鄰域不含p時的質心，用urmx（p）表示：

其中點q代表第k個鄰域中除p以外的任意一點，xq=（x**"，xx）是點q在d維空間中的坐標

定義4相關質心距離（distance of unrelated center mass）。相關質心距離表示兩個相鄰的相關質心之間的距離。用rm_d（p）表示：

定義5無關質心距離（distanceofunrelatedcentermass）。無關質心距離表示兩個相鄰的無關質心之間的距離。用urm_d：（p）表示：

定義6不穩定因子（instabilityfactor）不穩定因子定義為相關質心距離之和與無關質心距離之和的比，用INSF表示：

INSF（P）值為1，說明p與鄰域內各點均勻分布;值大于1，說明p的加入使得鄰域質心的變化加劇，從而說明p的不穩性較強;值小于1，說明p的加入使得鄰域質心的變化減緩，從而說明p的穩定性較強。比值越大，p離群可能性越高。

2實例分析

數據集采用INS算法中的葡萄酒質量數據集。該數據集包括1599個紅葡萄酒樣本數據和4898個白葡萄酒樣本數據。品質差的葡萄酒和品質高的葡萄酒數據量很少，是離群點檢測的目標。紅葡萄酒數據集中K取值50時，INS準確率88.9%，NSINS準確率94.4%;K取值100時，INS準確率88.9%，NSINS準確率100%。白葡萄酒數據集中K取值50時，INS準確率65%，NSINS準確率85%;K取值100時，INS準確率70%，NSINS準確率80%。

3結束語

本文提出的算法改進了使用不穩定因子的健壯離群點檢測算法，考慮到了近鄰的穩定性對被檢測點的影響，該算法綜合兩類質心的變化情況來決定不穩定因子大小。在數據集分布不規則的情況下優勢明顯。

參考文獻

[1]Xia Huo-Song. Data warehouse anddata mining technolo [M]. Beijing： Science Press， 2004： 229-231.

[2]Jihyun Ha， Seulgi Seok， Jong-SeokLee. Robust outlier detection us ingthe instability factor [J]. Knowledge-Based Systems. 2014（63）： 15-23.