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