【正文】 間復雜度為，其中取決于單元的個數(shù)和維數(shù)。 Knorr和Ng通過試驗證明，當時此算法優(yōu)于NL算法。相對前兩者，基于單元的算法無論是在數(shù)據(jù)量還是在維數(shù)增加時，性能都是最好的。此算法需要將數(shù)據(jù)空間分隔成彼此獨立的單元結構，經過多次選擇來判斷離群數(shù)據(jù)。對于參數(shù)的每個變化都需要調整單元結構，因此會影響了算法的結果。后來，Rastogi和Ramaswamy提出了一個新的基于距離的異常點定義，即基于距離的第最近鄰(kth Nearest Neighbor)異常點挖掘方法。給定維空間中包含個點的數(shù)據(jù)集、參數(shù)和 (自然數(shù)),表示點和它的第最近鄰的距離。如果滿足的點q不超過n1個，即，那么稱為異常點。如果對數(shù)據(jù)對象根據(jù)它們的距離進行排序，那么前n個點就被看作異常點。他們用聚類算法首先對數(shù)據(jù)集進行聚類，然后在類中發(fā)現(xiàn)異常點。相對于異常點挖掘，異常點挖掘方法人為干預的因素要小一些。但它也有自身缺陷，就是要計算數(shù)據(jù)集中所有點的，這顯然影響到算法的效率。對低維空間的數(shù)據(jù)此方法優(yōu)于索引算法和NL算法，但對于高維數(shù)據(jù)此算法性能不高。Bay和Sc hwabacher在沿用Rastogi和Ramaswamy對于異常定義的基礎上，提出了一種基于隨機抽樣的檢測方法，它通過隨機抽樣的方法，減少了尋找k近鄰的范圍，在試驗數(shù)據(jù)上獲得了幾乎線性的計算復雜度。隨著人們對基于距離的方法的不斷研究，一些新的、較好的算法也不斷的涌現(xiàn)。代表性的算法有: 陸聲鏈等提出一個判斷異常點的新定義，并設計基于抽樣近似檢測算法。使得算法性能有所提高。另外，徐雪松等利用聚類算法與第k個最近鄰的原理提出了基于距離的再聚類的異常點算法，它克服一些基于距離算法的缺點，并取得較好的試驗結果。與基于統(tǒng)計的方法相比，它有以下幾個優(yōu)點: 則可找出數(shù)據(jù)集中的異常點。(1) 在理論上可以處理任意維任意類型的數(shù)據(jù)，這就克服了基于統(tǒng)計方法僅能檢測單個屬性的缺點。(2) 不必對數(shù)據(jù)集的相關信息(數(shù)據(jù)服從哪種統(tǒng)計分布模型，數(shù)據(jù)類型特點等)足夠了解。實際上在給出了距離的度量，并對數(shù)據(jù)進行預處理后。基于密度方法是在基于距離的方法上改進而來?；诿芏鹊漠惓Ｓ^點比基于距離的異常觀點更貼近Hawkins的異常定義，因此能夠檢測出基于距離異常算法所不能識別的局部異常。局部異常觀點摒棄了以前所有的異常定義中非此即彼的絕對異常觀念，更加符合現(xiàn)實生活的中的應用。所謂密度是基于任意一點和P點距離小于給定半徑R的鄰域空間內的數(shù)據(jù)點的個數(shù)計算得到的。一般的對密度的定義是點到其量近鄰的平均距離，平均距離小則密度小?；诿芏鹊漠惓｜c檢測，就是探測局部密度，通過不同的密度估計策略來檢測異常點。代表性算法主要有以下幾種。(1) Brito等提出相互k近鄰圖(Mutual k—Nearest Neighbor，簡稱MkNN)算法，其主要思想是對每個連通子圖進行檢測，如果包含多個結點就組成一個簇，如果僅有一個結點，那么該結點就是異常點。該算法針對數(shù)據(jù)點的分布對各種特殊形狀都有效，但算法執(zhí)行效率不高。(2)Ville Hautamaki等提出兩種基于密度的異常點檢測算法，第一種算法思路為在kNN圖中，若頂點u成為其它點的k近鄰的次數(shù)少于給定閾值T時就被認為是異常點，另一種算法則是先對所有頂點的平均k近鄰距離進行排序，然后將平均k近鄰距離大于T點頂點視為異常點。 (3)Papadimitriou定義了多粒度偏離系數(shù)(Multi—Granularity Deviation Factor，簡稱MDEF)，該算法將多粒度偏離系數(shù)是所在鄰域的標準多粒度偏離系數(shù)的3倍的點判定為異常點，然而標準多粒度偏離系數(shù)的計算量大，對算法的可行性有一定的限制。(4)Dongmei Ren等采用相對密度系數(shù)(Rela—tive Density Factor，簡稱RDF)，即P點的密度相對該點的鄰域密度的比值作為孤立程度的度量方法，其基本思路是首先基于RDF對位于簇中心的數(shù)據(jù)點進行剪枝，然后僅僅在剩下的較小的數(shù)據(jù)集中進行異常點檢測。該方法降低了數(shù)據(jù)集的大小，提高了算法效率，但是在剪枝過程中對于特殊分布的數(shù)據(jù)集就有可能將異常點剪掉，算法的準確性受到限制。(5)Breuning 提出了局部異常的概念及相應異常檢測方法（DBOM算法），即數(shù)據(jù)集中的每個對象的異常程度用局部異常因子LOF來衡量。也就是說是否是異常點不僅僅取決于它與周圍數(shù)據(jù)的距離大小，而且與鄰域內的密度情況有關。一個對象領域內的密度可以用包含固定結點個數(shù)的域半徑指定半徑領域中包含的結點數(shù)來描述。這樣就不會像DB(p，d)異常點那樣遺漏一部分異常點。LOF算法充分體現(xiàn)了“局部”的概念，每個點都給出了一個離群程度，離群程度最強的那個幾個點被標記為異常點。文獻有關發(fā)面對LOF進行推廣：一是由原來的一個鄰域的變化為兩個（計算密度領域和比較密度領域）；二是剪除非異常對象來減小計算代價；因此，使用算法比傳統(tǒng)的LOF算法有所提高。在現(xiàn)有的計算局部異常因子（LOF）算法中，把具有很高LOF值的對象作為異常點。計算LOF要耗費很大的計算量，針對此問題malik Agyemang提出了修改算法，即局部稀疏系數(shù)(LSC)算法。這種方法主要是引入局部稀疏系數(shù)(LSC)這一概念，根據(jù)每個對象的LSC值按從大到小的順序排列整個數(shù)據(jù)集并把前n個對象作為異常點。但是，此方法在實際應用中計算量亦是不小，效率有待提高。另外，岳峰等利用反向K近鄰(RKNN)這個概念提出了一個異常點檢測算法(ODRKNN)，在綜合數(shù)據(jù)集和正式數(shù)據(jù)集上的實驗結構表明，該算法能有效地檢測出異常點，且算法效率高于典型的基于密度的異常點檢測算法LOF和LSC的效率。基于偏差的異常點檢測不使用統(tǒng)計檢驗或者基于距離的度量來識別異常對象。相反，它通過檢查一組對象的主要特征來識別異常點。背離這種描述的對象認為是異常點。因此，在該方法中，屬于偏差通常用于指異常點。主要有兩種技術：第一種順序地比較集合中的對象，叫順序異常技術(sequential exception technique)；第二種采用OLAP數(shù)據(jù)立方體方法識別大型多維數(shù)據(jù)中的異常區(qū)域。(1) 序列異常技術：Aming和Argrawal 提出一種序列異常(sequential exception)的概念。這個算法復雜度與數(shù)據(jù)集大小呈線性關系，有優(yōu)異的計算性能。但是并沒有得到普遍的認同，這是因為序列異常在概念上有一定的缺陷，它對異常點存在的假設太過理想化，對現(xiàn)實復雜數(shù)據(jù)效果不太好。(2) OLAP數(shù)據(jù)立方體技術：，該單元被認為是一個異常。此方法是發(fā)現(xiàn)驅動探索的一種形式。此方法由于搜索空間很大，人工探測非常困難。第一種概念有缺陷，遺漏了不少異常點，時間復雜度與數(shù)據(jù)集大小成線性關系，適用性不高。第二種搜索空間大，人工探測困難，效率不高，只適用多維數(shù)據(jù)。在聚類算法中，異常點檢測僅僅是聚類的副產品。聚類算法發(fā)展方向是優(yōu)化聚類過程，而不是提高對異常點檢測的能力，異常點檢測和聚類是兩個相對立的過程，聚類是把屬于統(tǒng)一類的數(shù)據(jù)點聚集在一起，歸為一類，而異常點檢測是把和大多數(shù)數(shù)據(jù)點相異的點挖掘出來。Su等人首先提出基于聚類的異常點檢測算法，聚集的較小簇被認為是異常點，但這中方法忽略了小聚集簇和大聚集簇之間的距離，當一個小聚集簇和一個大聚集簇非常接近的時候，小聚集簇中的這些點更可能是大聚集簇的邊界點而不是異常點。模糊k均值聚類算法(FCM)常用于異常點檢測，該算法動態(tài)地分配權重給每一個數(shù)據(jù)點，權重表示該數(shù)據(jù)點和數(shù)據(jù)集中心之間的距離，通過各點的權重來判斷異常點。此類算法沒有先驗知識指導如何確定聚類中心，只能是隨機選取，優(yōu)化搜索空間較大，算法的復雜度較大。Hongyi Zhang等引為了提高模糊核聚類算法的運行效率，提出了新的模糊核聚類算法，該算法用先驗知識對參數(shù)初始化。取代了用聚類中心初始化，改進了聚類的目標函數(shù)，降低了算法的時間復雜度，但該算法沒有提到如何選取核函數(shù)，對于算法模糊性的控制不好撐握。2基于屬性特征在異常點檢測中的研究傳統(tǒng)算法大都是通過數(shù)據(jù)在空間地特性來判斷檢測異常點。本文的方向是從特征出發(fā)研究。傳統(tǒng)算法從整個數(shù)據(jù)集合在空間中分布地特性出發(fā)研究，比如距離的從整個數(shù)據(jù)集空間距離進行研究，同樣密度的按數(shù)據(jù)集空間密度研究，聚類也是按數(shù)據(jù)集空間特性。而本文直接從已知部分數(shù)據(jù)維度的特征著手，即是直接從每一組數(shù)據(jù)的特征來研究。對于單屬性特征的情況，根據(jù)數(shù)據(jù)重要性調整特征（即維度）權值，并根據(jù)數(shù)據(jù)重要性調整。假設數(shù)據(jù)特征表示在每個屬性上面，獨立沒有組合屬性表現(xiàn)特征地情況下，每一組數(shù)據(jù)屬性對應權值數(shù)據(jù)乘積和，表示這個數(shù)據(jù)在這組數(shù)據(jù)中全局中所占的重要性。例如檢測是否是糖尿病人的數(shù)據(jù)庫，三十歲以下這個年齡維度上病人較少，然而五十歲后這個維度病人比例就多了。映射到維度為三十歲以下這個維度地病人比較少，映射到維度為十歲以上較多。這樣我們可以添加一個權值與年齡這一項數(shù)據(jù)乘積，這個乘積必須使權值與當前數(shù)據(jù)乘積出來的數(shù)據(jù)成正比，表示年齡增長能夠體現(xiàn)在這組數(shù)據(jù)中的重要性。以便全局統(tǒng)籌決策較容易。設X為一組數(shù)據(jù)集合，可使趨向某個數(shù)值，表示這組數(shù)據(jù)某個總體特征。異?；蛘叻钱惓?，可以通過趨向某個數(shù)值表示特征異常，另一個方向數(shù)值表示非異常。有時候數(shù)據(jù)組合的重要性是體現(xiàn)在幾個數(shù)據(jù)地組合里面，既可能體現(xiàn)在幾個屬性上面,比如說一組數(shù)組(A，B，C)，可能AB組合特征不顯示異常，然而ABC組合就顯示異常，這些組合是不定地。所有在屬性權值之上需要一組對屬性不同