基于局部偏離因子的孤立點(diǎn)檢測(cè)算法

1、第卷第期計(jì)算機(jī)工程矛文章編號(hào)：（）加文獻(xiàn)標(biāo)識(shí)碼。年月中圈分類(lèi)號(hào)軟件技術(shù)與數(shù)據(jù)庫(kù)基于局部偏離因子的孤立點(diǎn)檢測(cè)算法譚慶，張璃玲（洛陽(yáng)師范學(xué)院信息技術(shù)學(xué)院，洛陽(yáng)）奠蔓：孤立點(diǎn)檢測(cè)是知識(shí)發(fā)現(xiàn)中的一個(gè)活躍領(lǐng)域，如信用卡欺詐、入侵檢測(cè)等。研究孤立點(diǎn)的異常行為能發(fā)現(xiàn)隱藏在數(shù)據(jù)集中更有價(jià)值的知識(shí)。該文提出基于局部偏離因子（）的孤立點(diǎn)檢測(cè)算法，利用每個(gè)數(shù)據(jù)點(diǎn)的衡量該數(shù)據(jù)點(diǎn)的偏離程度。實(shí)驗(yàn)結(jié)果表明，該算法能有效檢測(cè)孤立點(diǎn)，其效率高于算法。關(guān)健詞：孤立點(diǎn)；距離鄰居；局部偏離因子，（，），（）；概述孤立點(diǎn)檢測(cè)又稱為孤立點(diǎn)分析、異常檢測(cè)、例外挖掘、小事件檢測(cè)、挖掘極小類(lèi)、偏差檢測(cè)。孤立點(diǎn)是數(shù)據(jù)集中與眾不同的數(shù)據(jù)，它們不

2、符合慣常的數(shù)據(jù)模式，其產(chǎn)生機(jī)制與一般數(shù)據(jù)不同。孤立點(diǎn)檢測(cè)是數(shù)據(jù)挖掘的重要研究?jī)?nèi)容之一，被用于發(fā)現(xiàn)數(shù)據(jù)集中比聚類(lèi)小的模式，即數(shù)據(jù)集中明顯不同于其他數(shù)據(jù)的對(duì)象。孤立點(diǎn)檢測(cè)己被應(yīng)用在電信和信用卡欺騙、貸款審批、氣象預(yù)報(bào)、金融領(lǐng)域、網(wǎng)絡(luò)入侵檢測(cè)和客戶分類(lèi)等領(lǐng)域。孤立點(diǎn)檢測(cè)在國(guó)外得到廣泛研究。，并被越來(lái)越多的國(guó)內(nèi)學(xué)者注意。機(jī)器學(xué)習(xí)領(lǐng)域的一些學(xué)者指出，異常分析將成為一個(gè)重要的研究方向。對(duì)孤立點(diǎn)的本質(zhì)性做如下定義：在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。隨后，研究者根據(jù)對(duì)異常存在的不同假設(shè)，提出了很多孤立點(diǎn)檢測(cè)算法，主要可分為基于統(tǒng)計(jì)的算法、基于距離的算法、基于密度

3、的算法、基于偏差的算法等。象，即。）（，）（）（）上述對(duì)象成為對(duì)象的距離鄰居，簡(jiǎn)記為肌仞）。定義（對(duì)象的局部偏離率）給出對(duì)象的距離鄰居，以為圓心，以距離為半徑得到一個(gè)包含所有距離鄰居的圓，計(jì)算距離鄰居的質(zhì)心，可得對(duì)象的局部偏離率，）為女（）：型旦衛(wèi)匕郴。（）（）其中，分子是對(duì)象與質(zhì)心的歐式距離；分母是對(duì)象的距離鄰居的總數(shù)。對(duì)象的局部偏離率反映了在以為圓心、距離為半徑的圓內(nèi)對(duì)象集對(duì)對(duì)象的影響。如果的值很小，說(shuō)明在對(duì)象周?chē)臄?shù)據(jù)點(diǎn)分布較均勻，則成為孤立點(diǎn)的概率很小。如果的值很大，表明在對(duì)象局部范圍內(nèi)的數(shù)據(jù)點(diǎn)對(duì)于的分布是不相關(guān)的，則成為孤立點(diǎn)的概率很大。如果值為零，說(shuō)明在對(duì)象周?chē)臄?shù)據(jù)點(diǎn)均勻分布，則

4、成為孤立點(diǎn)的概率很小。由于最終的孤立點(diǎn)判斷度鼉是依靠局部偏離因子，而不是，因此在計(jì)算對(duì)象的局部偏離因子時(shí)，可以對(duì)值為零的對(duì)象進(jìn)行剪枝，以節(jié)省算法的計(jì)算時(shí)間，但這將對(duì)精度造成一定影響。在考慮時(shí)間效果蘑于精度效果的條件下，還可以對(duì)值為零的對(duì)象的距離鄰居進(jìn)行剪枝，因?yàn)閺母怕噬隙?，上述?duì)象很大程度上屬于聚類(lèi)中的核心對(duì)象，其距離鄰居在很大程度：都應(yīng)該是聚類(lèi)中的點(diǎn)。定義（對(duì)象的局部偏離影響率）給定對(duì)象的距離基金項(xiàng)目：河南省科技攻關(guān)基金資助項(xiàng)目（）作者筒介：譚慶（一），男，講師、碩士，主研方向：數(shù)據(jù)挖掘，程序設(shè)計(jì)；張瑞玲，副教授收藕日期：基于局部偏離因子的孤立點(diǎn)檢測(cè)算法相關(guān)概念本文在分析基于密度的聚類(lèi)算法

5、和基于密度的孤立點(diǎn)算法的基礎(chǔ)上，提出基于局部偏離子（）的孤立點(diǎn)檢測(cè)算法。定義（對(duì)象的距離）對(duì)于任何一個(gè)正數(shù)，對(duì)象的距離，即仞），以，）在對(duì)象與對(duì)象之間必須滿足以條件（，）是與之間的歐式距離）：至少有，個(gè)對(duì)象，如，），）；至多有個(gè)對(duì)象，（）（，）。定義（對(duì)象的距離鄰居）給定一個(gè)對(duì)象的距離，的距離鄰居包括所有與的距離小于距離的對(duì)鄰居和局部偏離率，的局部偏離影響率三鞏）為（）膪仞）瓦（）兩其中，分子是對(duì)象的距離鄰居集中對(duì)象的和。對(duì)象的局部偏離影響率反映了的距離鄰居集中的對(duì)象對(duì)的偏離影響。定義（對(duì)象的局部偏離因子）給定對(duì)象的局部偏離率和局部偏離影響率，的局部偏離因子（）為刪器（）對(duì)象的局部偏離因子反映

6、了的距離鄰居內(nèi)鄰近對(duì)象分散程度。高值說(shuō)明對(duì)象周?chē)且粋€(gè)稀疏的區(qū)域，此對(duì)象很可能是一個(gè)孤立點(diǎn)，低值說(shuō)明該對(duì)象周?chē)且粋€(gè)密集區(qū)域，它不可能是孤立點(diǎn)。算法描述本算法的設(shè)計(jì)思想如下：先計(jì)算數(shù)據(jù)集中每個(gè)對(duì)象與數(shù)據(jù)集中所有其他數(shù)據(jù)之間的距離，從這些距離中選出最小的個(gè)距離，再?gòu)倪@個(gè)最小距離中選出其中的最大者作為對(duì)象的距離，得到對(duì)象的距離鄰居。然后計(jì)算對(duì)象的距離鄰居的質(zhì)心，求蹦對(duì)象與質(zhì)心的歐式距離，根據(jù)式（）計(jì)算對(duì)象的局部偏離率女）。通過(guò)剪枝過(guò)程，得到孤立點(diǎn)的候選集。再對(duì)孤立點(diǎn)的候選集，根據(jù)式（）計(jì)算對(duì)象的局部偏離影響率珊），根據(jù)式（）計(jì)算對(duì)象的局部偏離因子（）。最后的關(guān)鍵是從數(shù)據(jù)集中選出前個(gè)具有最大值的對(duì)象

7、作為孤立點(diǎn)。對(duì)基于的孤立點(diǎn)檢測(cè)算法描述如下：輸入：數(shù)據(jù)集，（是對(duì)象的最近鄰居數(shù)，是前個(gè)孤立點(diǎn)的個(gè)數(shù)）。輸出：前個(gè)對(duì)象是從數(shù)據(jù)集選出的具有最大的值。對(duì)每個(gè)對(duì)象，本文算法包含如下個(gè)步驟：（）利用定義計(jì)算的距離。（）利用定義計(jì)算的距離鄰居。（）根據(jù)定義計(jì)算的局部偏離率。（）通過(guò)剪枝過(guò)程，得到孤立點(diǎn)的候選集?？梢愿鶕?jù)不同需要采用種剪枝技術(shù)：）剪枝為零的數(shù)據(jù)對(duì)象；）剪枝為零的數(shù)據(jù)對(duì)象及其距離鄰居對(duì)象。（）對(duì)于候選集，根據(jù)定義計(jì)算的局部偏離影響率。（）對(duì)于候選集，根據(jù)定義計(jì)算的局部偏離因子。（）通過(guò)局部偏離因子，降序排列數(shù)據(jù)集，前個(gè)數(shù)據(jù)對(duì)象就是需要挖掘的孤立點(diǎn)。由于孤立點(diǎn)個(gè)數(shù)遠(yuǎn)小于數(shù)據(jù)集規(guī)模，因此可以在步

8、驟（）中，遍歷孤立點(diǎn)的候選集數(shù)據(jù)，每次得到最大的值，然后輸出，以提高時(shí)間效率。實(shí)驗(yàn)與分析本文實(shí)驗(yàn)環(huán)境是，內(nèi)存，專(zhuān)業(yè)版操作系統(tǒng)。算法在環(huán)境下用語(yǔ)言實(shí)現(xiàn)。對(duì)本文算法和基于局部稀疏系數(shù)（，）的孤立點(diǎn)檢測(cè)算法進(jìn)行實(shí)驗(yàn)對(duì)比。提出的基于的孤立點(diǎn)檢測(cè)算法的主要思想如下：先對(duì)數(shù)據(jù)集中每個(gè)對(duì)象，計(jì)算離它最近個(gè)對(duì)象的距離，從中選出最大的距離作為該點(diǎn)的距離，對(duì)數(shù)據(jù)集中每個(gè)對(duì)象計(jì)算與其距離不大于該對(duì)象距離的鄰近對(duì)象形成一個(gè)集合。然后計(jì)算每個(gè)對(duì)象與其對(duì)應(yīng)集合中的所有對(duì)象之間平均距離的反比，即局部稀疏率。最后計(jì)算集合內(nèi)所有對(duì)象的局部稀疏率之和與該點(diǎn)的局部稀疏率比值的平均比率，即，根據(jù)每個(gè)對(duì)象的值從大到小的順序排列整個(gè)數(shù)據(jù)

9、集，并把前個(gè)對(duì)象作為孤立點(diǎn)。算法性能分析為驗(yàn)證算法的正確性，本文先用文獻(xiàn)【】中的二維數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集有個(gè)記錄，個(gè)大簇和一些分布不均勻的孤立點(diǎn)數(shù)據(jù)。此實(shí)驗(yàn)最近鄰居個(gè)數(shù)都設(shè)為，檢測(cè)的孤立點(diǎn)個(gè)數(shù)設(shè)為，實(shí)驗(yàn)部分結(jié)果如表所示。圖是算法識(shí)別的孤立點(diǎn)結(jié)果，圖是本文算法識(shí)別的孤立點(diǎn)結(jié)果，其中，檢測(cè)出的孤立點(diǎn)加粗表示。由實(shí)驗(yàn)結(jié)果可以看出，算法能識(shí)別的孤立點(diǎn)，本文算法也能識(shí)別。算法在圖左上角的大簇中識(shí)別了一些點(diǎn)作為孤立點(diǎn)，這是錯(cuò)誤的。而本文算法沒(méi)有將這個(gè)大簇中的點(diǎn)誤識(shí)為孤立點(diǎn)。因此，本文算法是有效的，可以發(fā)現(xiàn)，隨數(shù)據(jù)的值從高到低，孤立點(diǎn)的分布逐漸向大簇靠攏，體現(xiàn)了局部概念。袁本文算法和算法檢測(cè)出的孤立點(diǎn)比較

10、排列順序查蘭竺鯊！蘭望堡垂量笪星垂曼！垣譬二翠？。一，：一圈算法識(shí)捌的孤立點(diǎn)圈本文算法識(shí)刖的孤立點(diǎn)使用文獻(xiàn)【卜個(gè)較復(fù)雜的二維綜合數(shù)據(jù)集，該數(shù)據(jù)集共有個(gè)數(shù)據(jù)點(diǎn)。此實(shí)驗(yàn)最近鄰居個(gè)數(shù)都設(shè)為，檢測(cè)的孤立點(diǎn)個(gè)數(shù)設(shè)為，實(shí)驗(yàn)部分結(jié)果如表所示。圖是算法識(shí)別的孤立點(diǎn)結(jié)果，圖是本文算法識(shí)別的孤立點(diǎn)結(jié)果，算法無(wú)法發(fā)現(xiàn)該數(shù)據(jù)集的孤立點(diǎn)，本文算法在發(fā)現(xiàn)復(fù)雜分布的孤立點(diǎn)時(shí)，比算法更有效。表本文算法和算法檢測(cè)出的孤立點(diǎn)比較”一、：一，”。，：一?！保何亩?，蘆。、。：二一圈算法識(shí)別的孤立點(diǎn)圈本文算法識(shí)捌的孤立點(diǎn)基于的孤立點(diǎn)檢測(cè)算法第步的時(shí)間復(fù)雜度為其中，檢測(cè)出的孤立點(diǎn)加粗表示。由實(shí)驗(yàn)結(jié)果可以看出，算法復(fù)雜度分析），第步為

11、（），第步為（，第步為（），第步為（），第步為（加，第步為（），其中，是每個(gè)數(shù)據(jù)對(duì)象的最近鄰居數(shù)；是所求的前，個(gè)孤立點(diǎn)的個(gè)數(shù)；是數(shù)據(jù)集的規(guī)模；是候選集的規(guī)模。完成剪枝過(guò)程后，通常遠(yuǎn)小于，因此，本文算法總的時(shí)間復(fù)雜度為鯽枷（女）。算法的時(shí)間復(fù)雜度與每個(gè)對(duì)象的最近鄰居個(gè)數(shù)成線瑚性關(guān)系，與數(shù)據(jù)集的規(guī)模呈平方關(guān)系。算法的總的時(shí)間咖復(fù)雜度也為（）?？褂梦墨I(xiàn)【】的二維綜合數(shù)據(jù)集，進(jìn)行如下個(gè)實(shí)驗(yàn)：鯽（）值的執(zhí)行時(shí)間。使用條記錄，實(shí)驗(yàn)需要用戶提供值和要求的前，個(gè)孤立點(diǎn)數(shù)。此實(shí)驗(yàn)使用了個(gè)不同伽瑚的值，即，。前個(gè)孤立點(diǎn)數(shù)都設(shè)定為，個(gè)算法在不同最近鄰居個(gè)數(shù)下的執(zhí)行時(shí)間如圖所示，可數(shù)據(jù)規(guī)模，個(gè)以看出，對(duì)于不同值，本

12、文算法的效率都高于算法。隨著的增長(zhǎng)，本文算法的執(zhí)行時(shí)間增長(zhǎng)緩慢，而算法不同數(shù)據(jù)規(guī)模情況下本文算法和算法的執(zhí)行時(shí)阿的執(zhí)行時(shí)間增長(zhǎng)較快。個(gè)算法的執(zhí)行時(shí)間近似線性增長(zhǎng)，結(jié)束語(yǔ)驗(yàn)證了上述關(guān)于時(shí)間復(fù)雜度的分析。本文提出基于的孤立點(diǎn)檢測(cè)算法，此算法能很好地咖檢測(cè)出數(shù)據(jù)集中的孤立點(diǎn)。實(shí)驗(yàn)結(jié)果表明，它對(duì)孤立點(diǎn)的識(shí)姍別效果優(yōu)于傳統(tǒng)算法。筆者的下一步工作是研究高維空咖間中孤立點(diǎn)的識(shí)別方法。跏力參考文獻(xiàn)一姍，：一【】（）咖湖：一【】，：，最近鄰居個(gè)數(shù)】，圈不同量近鄰居個(gè)數(shù)情況下本文算法和算法的執(zhí)行時(shí)問(wèn)（）不同數(shù)據(jù)規(guī)模的執(zhí)行時(shí)間。此實(shí)驗(yàn)使用條記錄，中的條。數(shù)據(jù)量大小為條條記錄，每次遞：】，增條。前個(gè)孤立點(diǎn)個(gè)數(shù)設(shè)為，每個(gè)對(duì)象的最近鄰居，：數(shù)設(shè)為。采用剪枝方法僅剪去為零的數(shù)據(jù)對(duì)象。實(shí)驗(yàn)結(jié)果如圖所示，可以看出，個(gè)算法的執(zhí)行時(shí)間近似【】：為拋物線，驗(yàn)證了上述關(guān)于個(gè)算法的時(shí)間復(fù)雜度與數(shù)據(jù)規(guī)模呈平方關(guān)系的分析。由圖可以看出，本文算法運(yùn)行時(shí)間【】山低于算法的運(yùn)行時(shí)間，符合上述時(shí)間復(fù)雜度分析。當(dāng)在【】（）：剪枝過(guò)程中也剪去為零的數(shù)據(jù)對(duì)象的鄰居時(shí)，運(yùn)行時(shí)間必然比算法更低。隨著數(shù)據(jù)集規(guī)模的增大，在發(fā)現(xiàn)孤【】（）立點(diǎn)的正確率和執(zhí)行時(shí)間方面，本文算法比算法更高效。：（上接第頁(yè)）器綜上所述，基于兩個(gè)矩陣的算法在執(zhí)行效率上有獨(dú)特優(yōu)勢(shì)，其所需存儲(chǔ)空間極大減少，可一次調(diào)入內(nèi)存進(jìn)行執(zhí)行，囂且具有支持并行計(jì)算的特點(diǎn)。結(jié)束語(yǔ)；