基于近鄰穩(wěn)定性的離群點檢測算法

黃馨玉　陳曉東

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

[關鍵詞]離群點鄰域質心不穩(wěn)定因子

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

1基于近鄰穩(wěn)定性的離群點檢測算法

1.1算法思想

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

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不穩(wěn)定因子（instabilityfactor）不穩(wěn)定因子定義為相關質心距離之和與無關質心距離之和的比，用INSF表示：

INSF（P）值為1，說明p與鄰域內各點均勻分布;值大于1，說明p的加入使得鄰域質心的變化加劇，從而說明p的不穩(wěn)性較強;值小于1，說明p的加入使得鄰域質心的變化減緩，從而說明p的穩(wěn)定性較強。比值越大，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結束語

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

參考文獻

[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.