基于局部孤立系數(shù)的孤立點(diǎn)挖掘

提出了一種基于局部孤立系數(shù)（LOC）的孤立點(diǎn)挖掘算法。該算法是對(duì)基于局部稀疏系數(shù)（LSC）孤立點(diǎn)挖掘論文中局部稀疏率和局部稀疏系數(shù)計(jì)算的一種改進(jìn)。實(shí)驗(yàn)表明，LOC 算法在發(fā)現(xiàn)孤立點(diǎn)方面比LSC 算法更高效。
孤立點(diǎn)檢測(cè)在數(shù)據(jù)挖掘領(lǐng)域是一項(xiàng)重要的挖掘技術(shù)。孤立點(diǎn)檢測(cè)的研究對(duì)象是數(shù)據(jù)集中
偏離絕大多數(shù)對(duì)象的很小一部分?jǐn)?shù)據(jù)。在許多KDD 應(yīng)用中，研究孤立點(diǎn)比研究聚類更有用、更重要。因?yàn)椋谀承?yīng)用領(lǐng)域中研究孤立點(diǎn)的異常行為能發(fā)現(xiàn)隱藏在數(shù)據(jù)集中更有價(jià)值的知識(shí)。諸如，在欺詐探測(cè)中，孤立點(diǎn)可能預(yù)示著欺詐行為；在市場(chǎng)分析中，可用于確定極低或極高的收入的消費(fèi)行為；在醫(yī)療分析中，用于發(fā)現(xiàn)對(duì)多種治療方式的不尋常的反映；因此，孤立點(diǎn)檢測(cè)是一個(gè)重要的數(shù)據(jù)挖掘任務(wù)，稱為孤立點(diǎn)挖掘或異常挖掘。孤立點(diǎn)挖掘可以描述如下：給定一個(gè)n 個(gè)數(shù)據(jù)點(diǎn)或?qū)ο蟮募?，及預(yù)期的孤立點(diǎn)的數(shù)目k，發(fā)現(xiàn)與剩余的數(shù)據(jù)相比是顯著相異的、異常的或不一致的頭k 個(gè)對(duì)象[1]。
在數(shù)據(jù)挖掘中，孤立點(diǎn)檢測(cè)算法大體上可分為以下幾類：統(tǒng)計(jì)學(xué)方法，基于距離的方法，基于偏離的方法和基于密度的方法。
基于密度的方法能夠挖掘出比基于距離異常算法所不能識(shí)別的一類異常數(shù)據(jù)—局部異
常。局部異常觀點(diǎn)擯棄了以前所有的異常定義中非此即彼的絕對(duì)異常觀念，這更加符合現(xiàn)實(shí)生活中的應(yīng)用。近年來(lái)，一些研究人員提出局部孤立點(diǎn)探測(cè)[2，3，4，5],就是對(duì)每個(gè)對(duì)象賦予某個(gè)度，這個(gè)度決定了這個(gè)對(duì)象成為孤立點(diǎn)的程度。每個(gè)點(diǎn)的孤立程度只與它和周圍點(diǎn)的距離有關(guān)，而與數(shù)據(jù)集中其他的點(diǎn)沒(méi)有任何關(guān)系，這就體現(xiàn)了“局部”的特性。局部稀疏系數(shù)（LSC）就是其中一種，Malik Agyemang 提出的基于局部稀疏系數(shù) (LSC)孤立點(diǎn)挖掘[4]算法的主要思想是對(duì)數(shù)據(jù)集中每個(gè)對(duì)象，計(jì)算出離它最近K 個(gè)對(duì)象的距離，并從中選出最大的距離作為該點(diǎn)的K-距離，對(duì)數(shù)據(jù)集中每個(gè)對(duì)象計(jì)算出與它的距離不大于該對(duì)象K-距離的鄰近對(duì)象形成一個(gè)集合，然后計(jì)算每個(gè)對(duì)象與其對(duì)應(yīng)集合的所有對(duì)象之間平均距離的反比，即局部稀疏率，最后計(jì)算集合內(nèi)所有對(duì)象的局部稀疏率之和與該點(diǎn)的局部稀疏率比值的平均比率，即局部稀疏系數(shù)（LSC）；根據(jù)每個(gè)對(duì)象的LSC 值從大到小的順序排列整個(gè)數(shù)據(jù)集，并把前n 個(gè)對(duì)象作為孤立點(diǎn)。
在局部稀疏系數(shù)（LSC）算法中，需要計(jì)算數(shù)據(jù)集中每個(gè)對(duì)象的局部稀疏率和局部稀疏
系數(shù)，當(dāng)數(shù)據(jù)集很大時(shí)，計(jì)算每個(gè)對(duì)象的局部稀疏率和局部稀疏系數(shù)耗費(fèi)很大的計(jì)算量。本文提出了基于局部孤立系數(shù)（LOC）孤立點(diǎn)算法，它是對(duì)LSC 算法的改進(jìn)，LOC 算法的主要思想是:對(duì)于數(shù)據(jù)集中每個(gè)點(diǎn)，計(jì)算出離它最近K 個(gè)對(duì)象的距離并選出其中最大距離作為該點(diǎn)的K-距離，并把最近K 個(gè)距離的和作為該點(diǎn)的局部距離之和；然后計(jì)算每個(gè)點(diǎn)的局部距離之和與它K-距離內(nèi)每個(gè)對(duì)象的局部距離之和的總和平均值的比率（LOC）作為該點(diǎn)的孤立因子，按LOC 值從大到小的順序選出前n 個(gè)作為孤立點(diǎn)。本文給出了LSC 算法和LOC 算法的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果表明LOC 算法在發(fā)現(xiàn)孤立點(diǎn)方面比LSC 算法效率高。