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

黃馨玉　陳曉東

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

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

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

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

1.1算法思想

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

1.2相關(guān)定義

定義1鄰域（neighborhood）。點(diǎn)p的鄰域表示距離點(diǎn)p最近的k個(gè)點(diǎn)的集合，用6：（p）表示，即：

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

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

其中（...q.）是點(diǎn)q在d維空間中的坐標(biāo)。

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

其中點(diǎn)q代表第k個(gè)鄰域中除p以外的任意一點(diǎn)，xq=（x**"，xx）是點(diǎn)q在d維空間中的坐標(biāo)

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

定義5無關(guān)質(zhì)心距離（distanceofunrelatedcentermass）。無關(guān)質(zhì)心距離表示兩個(gè)相鄰的無關(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)各點(diǎn)均勻分布;值大于1，說明p的加入使得鄰域質(zhì)心的變化加劇，從而說明p的不穩(wěn)性較強(qiáng);值小于1，說明p的加入使得鄰域質(zhì)心的變化減緩，從而說明p的穩(wěn)定性較強(qiáng)。比值越大，p離群可能性越高。

2實(shí)例分析

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

3結(jié)束語

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

參考文獻(xiàn)

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