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

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