【正文】 本科畢業(yè)設(shè)計(jì)（論文） BP神經(jīng)網(wǎng)絡(luò)的異常點(diǎn)檢測(cè)應(yīng)用可行性研究學(xué) 院 專 業(yè) 年級(jí)班別 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 2013年 5 月摘 要異常點(diǎn)數(shù)據(jù)是指數(shù)據(jù)集中與眾不同數(shù)據(jù)。這部分?jǐn)?shù)據(jù)的量小，但是對(duì)于我們的日常生產(chǎn)生活的影響極大。因此，異常點(diǎn)檢測(cè)被廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)，金融保險(xiǎn)，天氣預(yù)報(bào)以及新藥研制等領(lǐng)域。相對(duì)于大量的正常數(shù)據(jù)挖掘而言，異常點(diǎn)檢測(cè)被稱作小模式數(shù)據(jù)挖掘。BP算法是一種常用的數(shù)據(jù)挖掘算法。但是BP算法進(jìn)行實(shí)際數(shù)據(jù)的異常點(diǎn)數(shù)據(jù)挖掘過程中存在：實(shí)際數(shù)據(jù)的維數(shù)較高，存在冗余特征的干擾，以及在高維特征下，數(shù)據(jù)量不充分的問題。因此，本文分析BP神經(jīng)網(wǎng)絡(luò)處理各種數(shù)據(jù)的情況，并得到以下結(jié)果。（1）BP神經(jīng)網(wǎng)絡(luò)能夠較好的分離特征單一的仿真數(shù)據(jù)；但是（2）特征相似性較大的數(shù)據(jù)集，難以分離判斷；（3）正常數(shù)據(jù)不充分或者不具有代表性，因此正常數(shù)據(jù)類學(xué)習(xí)不充分，從而導(dǎo)致異常無(wú)法判斷。針對(duì)以上問題，本文提出了以下的改進(jìn)措施：（1）BP算法前進(jìn)行特征約簡(jiǎn)（映射）從中選取有益于異常檢測(cè)的特征（2）多神經(jīng)網(wǎng)絡(luò)融合，不同神經(jīng)網(wǎng)絡(luò)識(shí)別不同的特征，相互取長(zhǎng)補(bǔ)短，融合后得到最終的結(jié)果。關(guān)鍵字：異常，BP，異常點(diǎn)檢測(cè)，神經(jīng)網(wǎng)絡(luò)注：本設(shè)計(jì)（論文）題目來(lái)源于教師的國(guó)家級(jí)（或部級(jí)、省級(jí)、廳級(jí)、市級(jí)、校級(jí)、企業(yè)）科研項(xiàng)目，項(xiàng)目編號(hào)為： 。AbstractOutlier data is the data set different data. This part of the small amount of data, but for our daily production and life of great. Therefore, the anomaly detection is widely used in network intrusion detection, finance, insurance, weather, and new drug development and other fields. Relative to the large number of normal data mining, the anomaly detection model is called data mining small. BP algorithm is a monly used data mining algorithm. But the BP algorithm to real data outliers exist in the data mining process: the higher the dimension of the actual data, there are redundant features of the interference, and highdimensional feature, the issue of inadequate data. Therefore, this paper analyzes a variety of BP neural network processing of data, and to get the following results. (1) BP neural network can better separation characteristics of a single simulation data。 but (2) the characteristics of similar large data sets, separation is difficult to judge。 (3) normal data is not sufficient or not representative, so the normal data class learning is not sufficient, leading to abnormal can not judge. To solve the above problem, this paper proposes the following improvements: (1) BP algorithm before feature reduction (map) benefit from anomaly detection features selected (2) integration of multiple neural networks, different neural network to recognize the different characteristics of each each other, the final fusion result.Key Words：OutliersData，BP，Algorithms，Neural Networks目 錄1引言 1 1 傳統(tǒng)已有異常點(diǎn)算法介紹 1 1 2 3 5 62基于屬性特征在異常點(diǎn)檢測(cè)中的研究 73 BP神經(jīng)網(wǎng)絡(luò)介紹 9 9 9 修正權(quán)值 104 異常檢測(cè)中BP神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì) 13 13 13 145實(shí)驗(yàn)研究 17 17：把bp神經(jīng)網(wǎng)絡(luò)相似性代替距離算法相似度量 17：用單個(gè)神經(jīng)網(wǎng)絡(luò)對(duì)訓(xùn)練數(shù)據(jù)庫(kù)整體特性進(jìn)行學(xué)習(xí) 18：多神經(jīng)網(wǎng)絡(luò)各種形式訓(xùn)練及其決策 19 19 20 22 23 25 25 26 29 31 31 31 32 33 33總結(jié)與展望 35致謝 391引言異常點(diǎn)（離群點(diǎn)或者孤立點(diǎn)）檢測(cè)是數(shù)據(jù)挖掘中一個(gè)重要方面，Hawkins[1]最早給出了異常點(diǎn)的本質(zhì)定義：異常點(diǎn)是數(shù)據(jù)集中與眾不同地?cái)?shù)據(jù)，以至于使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生與完全不同的機(jī)制。異常點(diǎn)可能由于度量或執(zhí)行錯(cuò)誤產(chǎn)生，也可能是由于固有數(shù)據(jù)可變性的結(jié)果。例如，一個(gè)公司首席執(zhí)行官的工資自然遠(yuǎn)遠(yuǎn)高于公司其他雇員的工資，成為一個(gè)異常點(diǎn)。許多數(shù)據(jù)挖掘算法試圖減少異常點(diǎn)的對(duì)挖掘結(jié)果的影響，或者在挖掘過程中排除異常點(diǎn)。然而異常點(diǎn)可能隱藏著重要的信息，也許比一般的數(shù)據(jù)更有價(jià)值。因此人們開始逐漸研究異常點(diǎn)挖掘算法。目前異常點(diǎn)檢測(cè)已經(jīng)開始用于信用卡欺詐、網(wǎng)絡(luò)入侵檢測(cè)以及金融申請(qǐng)和交易欺詐等領(lǐng)域[2]，近年來(lái)異常點(diǎn)檢測(cè)已成為數(shù)據(jù)挖掘研究中的一個(gè)熱點(diǎn)問題。傳統(tǒng)數(shù)據(jù)挖掘主要有以下幾類：基于統(tǒng)計(jì)的方法，基于距離的方法，基于偏移方法，基于聚類方法，基于密度方法。本文從特征與異常檢測(cè)的關(guān)系出發(fā)進(jìn)行研究。BP神經(jīng)網(wǎng)絡(luò)適用于儲(chǔ)存和描述這種復(fù)雜的關(guān)系。但是異常檢測(cè)過程，通常數(shù)據(jù)的位數(shù)較高，在高維特征存在冗余特征干擾，以及高維特征下數(shù)據(jù)不充分的問題，因此，本文研究了BP神經(jīng)網(wǎng)絡(luò)應(yīng)用于不同情況。 傳統(tǒng)已有異常點(diǎn)算法介紹早期的異常點(diǎn)檢測(cè)算法大多數(shù)是基于統(tǒng)計(jì)學(xué)實(shí)現(xiàn)的，通常可以分為基于分布的檢測(cè)算法和基于深度的檢測(cè)算法兩類。前者一般通過先構(gòu)造一個(gè)標(biāo)準(zhǔn)概率分布來(lái)擬合數(shù)據(jù)集，然后根據(jù)概率分布來(lái)確定異常點(diǎn)，例如Rosner提出的單樣本多個(gè)異常檢測(cè)算法ESD算法，和Yamnishi等使用混合高斯模型的異常點(diǎn)檢測(cè)算法。此類算法估計(jì)多維分布的概率模型的難度較大，且準(zhǔn)確性低?；谏疃确椒ㄖ饕杂?jì)算幾何為基礎(chǔ)，通過計(jì)算不同層的KD凸包將外層的對(duì)象判定為異常點(diǎn)。但當(dāng)數(shù)據(jù)集較大，此類方法在維數(shù)上的伸縮性不好。基于統(tǒng)計(jì)的異常點(diǎn)檢測(cè)方法易于理解，實(shí)現(xiàn)方便，但此方法檢測(cè)出來(lái)的異常點(diǎn)很可能被不同的分布模型檢測(cè)出來(lái)，解釋異常點(diǎn)意義時(shí)經(jīng)常發(fā)生多義性。其次，此方法在很大程度上依賴于待挖掘的數(shù)據(jù)集是否滿足某種概率分布模型、模型的參數(shù)、異常點(diǎn)的數(shù)目等對(duì)基于統(tǒng)計(jì)的方法都有非常重要的意義，而確定這些參數(shù)通常比較困難；另外，此方法大多適合于挖掘單變量的數(shù)值型數(shù)據(jù)，然而許多數(shù)據(jù)挖掘問題要求在多維空間中發(fā)現(xiàn)異常點(diǎn)，目前幾乎沒有多元的不一致檢驗(yàn)，當(dāng)沒有特定的檢驗(yàn)時(shí)，或觀察到的分布不能恰當(dāng)?shù)赜萌魏螛?biāo)準(zhǔn)的分布建模時(shí)，此類方法不能確保所有的異常點(diǎn)被發(fā)現(xiàn)。基于距離的異常點(diǎn)檢測(cè)算法的基本思想是把數(shù)據(jù)點(diǎn)看作空間中的點(diǎn)，異常點(diǎn)被定義為與大多數(shù)數(shù)據(jù)距離較遠(yuǎn)的點(diǎn)。通常這類異常被描述為。當(dāng)且僅當(dāng)數(shù)據(jù)集中至少有個(gè)數(shù)據(jù)點(diǎn)與點(diǎn)的距離大于時(shí)，數(shù)據(jù)對(duì)象點(diǎn)稱為異常點(diǎn)。這類方法與基于密度的檢測(cè)算法有很大的相似之處，不需要事先知道數(shù)據(jù)集的分布模型，對(duì)于任意分布模型均有效。基于距離方法最早是由Knorr和Ng在1998年提出的。他們用DB(p,d)來(lái)表示數(shù)據(jù)集中的異常點(diǎn)，采用不同的參數(shù)與，可以表示所有的異常點(diǎn)。與此 定 義 相應(yīng)的算法有三種，它們是基于索引(Indexbased)的算法，嵌套循環(huán)(NestLoop，NL)算法，基于單元或劃分(cellbased)的算法等。基于索引的方法依賴多維索引結(jié)構(gòu)(Rtrees,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通過試驗(yàn)證明，當(dāng)時(shí)此算法優(yōu)于NL算法。相對(duì)前兩者，基于單元的算法無(wú)論是在數(shù)據(jù)量還是在維數(shù)增加時(shí)，性能都是最好的。此算法需要將數(shù)據(jù)空間分隔成彼此獨(dú)立的單元結(jié)構(gòu)，經(jīng)過多次選擇來(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不超過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è)方法，它通過隨機(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ù)處理后。基于密度方法是在基于距離的方法上改進(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è)局部密度，通過不同的密度估計(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ù)集的大小，提高了算法效率，但是在剪枝過程中對(duì)于特殊分布的數(shù)據(jù)集就有可能將異常點(diǎn)剪掉，算法的準(zhǔn)確性受到限制。(5)Breuning 提出了局部異常的概念及相應(yīng)異常檢測(cè)方法（DBOM算法），即數(shù)據(jù)集中的每個(gè)對(duì)象的異常程度用局部異常因子LOF來(lái)衡量。也就是說是否是異常點(diǎn)不僅僅取決于它