黃馨玉　陳曉東

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

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

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

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

1.1算法思想

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

1.2相關(guān)定義

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

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

定義2相關(guān)鄰域質(zhì)心（relatedcentreofmass）。點p的相關(guān)鄰域質(zhì)心表示p的鄰域包括點p時的質(zhì)心，用rm，（p）表示：

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

定義3無關(guān)鄰域質(zhì)心（unrelatedcentreofmass）。點p的無關(guān)鄰域質(zhì)心表示p的鄰域不含p時的質(zhì)心，用urmx（p）表示：

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

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

定義5無關(guān)質(zhì)心距離（distanceofunrelatedcentermass）。無關(guān)質(zhì)心距離表示兩個相鄰的無關(guān)質(zhì)心之間的距離。用urm_d：（p）表示：

定義6不穩(wěn)定因子（instabilityfactor）不穩(wěn)定因子定義為相關(guān)質(zhì)心距離之和與無關(guān)質(zhì)心距離之和的比，用INSF表示：

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

2實例分析

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

3結(jié)束語

本文提出的算法改進了使用不穩(wěn)定因子的健壯離群點檢測算法，考慮到了近鄰的穩(wěn)定性對被檢測點的影響，該算法綜合兩類質(zhì)心的變化情況來決定不穩(wěn)定因子大小。在數(shù)據(jù)集分布不規(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.