（計算機軟件與理論專業(yè)論文）基于信息熵和子空間的離群數(shù)據(jù)挖掘算法研究.pdf

中文摘要 離群數(shù)據(jù)挖掘是找出隱含在海量數(shù)據(jù)中相對稀疏而孤立的異常數(shù)據(jù)模式，它往 往可以使人們發(fā)現(xiàn)一些真實的，但又出乎意料的知識，因此通過對離群數(shù)據(jù)的研究， 發(fā)現(xiàn)異常的行為和模式，有著非常重要的意義?，F(xiàn)有的傳統(tǒng)離群數(shù)據(jù)挖掘方法存在 著受人為因素影響較大，而且不能對挖掘出來的離群點做進一步分析的問題。本文 采用信息熵作為離群數(shù)據(jù)的度量手段，對離群數(shù)據(jù)挖掘方法進行了研究，其主要研 究成果如下： 1 、給出一種基于信息熵的離群數(shù)據(jù)挖掘算法( o m b i e ) 。首先，分析和定義了基 于信息熵的離群度量因子，并通過離群度量因子來度量數(shù)據(jù)集中每個記錄的離群程 度；然后，根據(jù)每個數(shù)據(jù)點離群程度，檢測出離群數(shù)據(jù)，從而有效地消除了人為主 觀因素對離群檢測的影響，進一步反映客觀事物的本質(zhì)，并能較好地解釋離群點的 含義；最后，實驗驗證了該算法的可行性和有效性。 2 、給出一種離群數(shù)據(jù)挖掘算法( o m b c a s ) 。首先，引入屬性熵與特征屬性的概 念，并計算特征屬性子空間和屬性權(quán)重；然后，利用異常度的概念，計算子空間離 群影響因子，并檢測出離群點；最后，實驗驗證了算法具有不需要人為干預(yù)、伸縮 性強等優(yōu)點。 關(guān)鍵字：離群數(shù)據(jù)；信息熵；離群度量因子；特征屬性；子空間；恒星光譜數(shù)據(jù) a b s t r a c t t h et a s ko fo u t l i e rm i n i n gi st od i s c o v e re x c e p t i o n a l ，i n t e r e s t i n g ，s p a r s e a n di s o l a t e dp a t t e r n sc o n c e a l e di nm a s s i v ed a t as e t i tc a nf i n ds o m er e a l ，b u t u n e x p e c t e dk n o w l e d g e t h e r e f o r e ，i ti s o fs i g n i f i c a n c et om i n ea b n o r m a l b e h a v i o r sa n dp a t t e r n sb ys t u d y i n go u t l i e rm i n i n gm e t h o d s t h et r a d i t i o n a l o u t l i e rm i n i n gm e t h o d sa r es u b je c tt om a n - m a d ef a c t o r s ；i na d d i t i o n ，m i n e d o u t l i e r sc a nn o tb ea n a l y z e df u r t h e r w eh a v ea d o p t e dt h ei n f o r m a t i o n e n t r o p ya sam e a n so fm e a s u r i n go u t l i e rd a t a , a n ds t u d i e do u t l i e rm i n i n g m e t h o d sh a v eb e e ns t u d i e d m a i nr e s e a r c h e sa r ea sf o l l o w s ： 1 ) an e wd a t am i n i n ga l g o r i t h m - - - o u t l i e rm i n i n ga l g o r i t h mb a s e do n i n f o r m a t i o ne n t r o p yi sp r e s e n t e db yu s i n go u t l i e rm e a s u r ef a c t o rb a s e do n i n f o r m a t i o ne n t r o p y i nt h ea l g o r i t h m ，o u t l i e rm e a s u r ef a c t o ro f e a c hr e c o r di s c a l c u l a t e db yu s i n gi n f o r m a t i o n e n t r o p y ，a n dt h e no u t l i e r sa r ed e t e c t e db yt h e v a l u e so fo u t l i e rm e a s u r ef a c t o r ，s ot h a ti m p a c tb ym a n - m a d ef a c t o r si s e l i m i n a t e di no u t l i e rm i n i n g t h ed e f i n i t i o no fo u t l i e rb a s e do no u t l i e r m e a s u r ef a c t o rc o u l d e x p l a i n t h em e a n i n go ft h eo u t l i e r s i nt h ee n d ， e x p e r i m e n t a lr e s u l t ss h o wt h ef e a s i b i l i t ya n d ，e f f e c t i v e n e s so ft h ea l g o r i t h m b yu t i l i z i n gu c ia n dh i g h - d i m e n s i o n a ls t a rs p e c t r u md a t a 2 ) a no u t l i e rm i n i n ga l g o r i t h mb a s e do nc h a r a c t e r i s t i ca t t r i b u t e s u b s p a c e i s p r o p o s e d f i r s t l y ，t h e d e f i n i t i o n so fa t t r i b u t ee n t r o p ya n d c h a r a c t e r i s t i ca t t r i b u t ea r ei n t r o d u c e dt om a k ec o r r e s p o n d i n gc h a r a c t e r i s t i c a t t r i b u t es u b s p a c ea n da t t r i b u t ew e i g h t s e c o n d l y ，s u b s p a c eo u t l i e ri n f l u e n c e f a c t o ri s c o m p u t e db ya b n o r m a l i t yd e g r e e ，a n dt h e n o u t l i e r sa r ef o u n d f i n a l l y ，e x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mi s f e a s i b l ea n de f f e c t i v e ， b e c a u s ei ti sn o td e p e n d e n to np a r a m e t e r sw h i c hu s e ri n p u ta n dh a ss t r o n g f l e x i b i l i t y k e y w o r d s ： o u t l i e r ； i n f o r m a t i o n e n t r o p y ；o u t l i e r m e a s u r e f a c t o r ； i i i c h a r a c t e r i s t i ca t t r i b u t e ；s u b s p a c e ；s t a rs p e c t r u m i v 聲明戶明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在指導(dǎo)教師的指導(dǎo)下， 獨立進行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文 不包含其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究 做出重要貢獻的個人和集體，均已在文中以明確方式標明。本聲明的 法律責(zé)任由本人承擔(dān)。 作者簽名：主墨黧 日期： 魚! 巨塑塑旦 關(guān)于學(xué)位論文使用權(quán)的說明 本人完全了解太原科技大學(xué)有關(guān)保管、使用學(xué)位論文的規(guī)定，其 中包括：學(xué)校有權(quán)保管、并向有關(guān)部門送交學(xué)位論文的原件、復(fù)印 件與電子版；學(xué)?？梢圆捎糜坝?、縮印或其它復(fù)制手段復(fù)制并保存 學(xué)位論文；學(xué)?？稍试S學(xué)位論文被查閱或借閱；學(xué)?？梢詫W(xué)術(shù)交 流為目的，復(fù)制贈送和交換學(xué)位論文；學(xué)?？梢怨紝W(xué)位論文的全 部或部分內(nèi)容( 保密學(xué)位論文在解密后遵守此規(guī)定) 。 作者簽名：多民餾日期： 2 竺2 至羔墮竺! 導(dǎo)師簽名：! 參割主 啉 第一章緒論 第一章緒論 1 1 數(shù)據(jù)挖掘 1 1 1 引言 隨著i n t e r n e t 的日趨普及與數(shù)據(jù)庫技術(shù)的不斷發(fā)展，“數(shù)據(jù)豐富，但信息貧乏 的問題【l 】也日見突出。由于數(shù)據(jù)量急劇膨脹所生成的大量信息在給人們帶來方便的同 時，也帶來了一系列問題，例如：數(shù)據(jù)的時效性與復(fù)雜性已遠遠超出了當(dāng)前的信息 處理能力；信息量過大，超出了人們掌握、消化的能力；一些信息真?zhèn)坞y辨，給信 息的正確運用帶來困難；網(wǎng)絡(luò)上的信息安全難以保障；信息組織形式的不一致性， 增加了對信息進行有效統(tǒng)一處理的難度等【l ，2 1 。 近十幾年來，在網(wǎng)絡(luò)技術(shù)的推動下，人們生產(chǎn)和搜集數(shù)據(jù)的能力大幅度地提高， 而獲得生產(chǎn)數(shù)據(jù)的能力大大超過處理數(shù)據(jù)的能力。如今，由于數(shù)據(jù)生產(chǎn)、傳輸能力 與數(shù)據(jù)分析能力的不平衡，人們被數(shù)據(jù)淹沒，尋找隱藏在其中的有用信息無異于大 海撈針。人們希望能夠提供高層次的數(shù)據(jù)分析功能，自動和智能地在待處理的數(shù)據(jù) 中尋找和發(fā)現(xiàn)有用的信息知識。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)( d a t am i n i n ga n dk n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 技術(shù)就是在這樣的背景下應(yīng)運而生并蓬勃發(fā)展起來的。 數(shù)據(jù)挖掘與知識發(fā)現(xiàn)的目的是通過一定的算法對大量數(shù)據(jù)進行分析，從數(shù)據(jù)庫中 挖掘出事先未知且潛在有用的知識，使用所發(fā)現(xiàn)的模式幫助解釋當(dāng)前的行為或預(yù)測 未來的結(jié)果，從而做出正確的決策，并以可理解的方式展現(xiàn)給用戶。 1 1 2 數(shù)據(jù)挖掘的定義 什么是知識發(fā)現(xiàn)? 目前公認的k d d 定義是由f a y y a d 等人提出的。知識發(fā)現(xiàn) ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 是指從大量數(shù)據(jù)中提取有效的、新穎的、 潛在有用的、最終可被理解的模式的非平凡過程【2 1 。k d d 一詞首次出現(xiàn)在1 9 8 9 年8 月舉行的第1 1 屆國際聯(lián)合人工智能( a a a i ) 學(xué)術(shù)會議上。如今，k d d 的研究受到眾 多不同領(lǐng)域與行業(yè)的關(guān)注，并逐漸成為數(shù)據(jù)庫與人工智能領(lǐng)域的一個研究熱點和重 點。 k d d 是利用學(xué)習(xí)算法從數(shù)據(jù)庫中發(fā)現(xiàn)有價值的知識的一個多步驟的反復(fù)迭代的 人機交互處理過程 2 ，3 1 。此過程由九個步驟構(gòu)成，并且很多決策需要由用戶提供。從 宏觀整體上看，k d d 過程主要由三個部分組成：數(shù)據(jù)準備、數(shù)據(jù)挖掘以及結(jié)果表達 與解釋。u s a m am f a y y a d 4 1 等人給出的處理模型如圖1 - 1 所示。 基子催啟墑和于空間的離群數(shù)據(jù)挖掘算潔研互 ! ! 竺1 ! ! ：蘭! ! 竺! 竺 ! i 彳烈。j 胃： f = 魚j 一j 一一j j t 一一一一一一j 一一一一一一j 一一一一一j 一一一一一j 圖l - ik d d 過程處理模型目 f i g u r e1 一lk d dp r o c e s sm o d e ld i a g r a m l 、數(shù)據(jù)準備：了解k d d 應(yīng)用領(lǐng)域的有關(guān)情況。熟悉相關(guān)的背景知識，弄清用 戶的需求。 2 、數(shù)據(jù)選?。焊鶕?jù)用戶的要求從數(shù)據(jù)庫中提取與k d d 相關(guān)的數(shù)據(jù)，k d d 將主 要從這些數(shù)據(jù)中進行知識提取。在此過程中，將利用一些數(shù)據(jù)庫操作對數(shù)據(jù)庫進行 相關(guān)處理。 3 、數(shù)據(jù)預(yù)處琿：豐要是對步驟二中選出的數(shù)據(jù)進行再加工及處理，檢查數(shù)據(jù)的 完整性及斂性，消除噪聲，濾除與數(shù)據(jù)挖掘無關(guān)的冗余數(shù)據(jù)，對丟失的數(shù)據(jù)利用 統(tǒng)計等方法進行填補。 4 、數(shù)據(jù)變換：根據(jù)知識發(fā)現(xiàn)的千務(wù)對己預(yù)處理的數(shù)據(jù)進行再處理，主要通過投 影或數(shù)據(jù)庫的其他操作減少數(shù)據(jù)量。 5 、確定k d d 目標：根據(jù)用戶的要求，確定k d d 要發(fā)現(xiàn)何種類型的知識。因為 對k d d 的不同要求會在具體的知識發(fā)現(xiàn)過程中采用不同的知識發(fā)現(xiàn)算法。 6 、選擇算法：根據(jù)步驟五確定的任務(wù)，選擇合適的知識發(fā)現(xiàn)算法，包括選取合 適的模型和參數(shù)。 7 、數(shù)據(jù)挖掘：這是整個k d d 過程中非常重要的一個步驟。運用選定的算法， 從數(shù)據(jù)庫中提取用戶感興趣的知識，并以一定的方式表示出來，如產(chǎn)生式規(guī)則等。 8 、模式解釋：對在第七個步驟中發(fā)現(xiàn)的模式懶識進行解釋- 9 、知識評價：將拄現(xiàn)的知識以用戶能理解的方式呈現(xiàn)給用戶。此期間還包含對 知識一致性的檢查，以確信本次發(fā)現(xiàn)的知識不與前面發(fā)現(xiàn)的知識相抵觸。 會 l 吐m 一澎 互- 第一章緒論 對已挖掘出的知識進行評測后，根據(jù)得出的結(jié)果來決定是否重新進行相應(yīng)的處 理過程，在處理任意階段時都可以返回之前的階段進行再處理。在整個k d d 過程處 理中，數(shù)據(jù)挖掘占據(jù)著頗為重要的地位，它決定整個k d d 過程的效果與效率。 數(shù)據(jù)挖掘( d a t am i n i n g ) 就是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù) 據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過 程【5 1 。 數(shù)據(jù)挖掘是可以從大量數(shù)據(jù)中挖掘出隱含的、先前未知的、對決策有潛在價值的 知識和規(guī)則的高級處理過程。通過挖掘數(shù)據(jù)，有價值的知識、規(guī)則或高層次的信息 就能從數(shù)據(jù)庫的相關(guān)數(shù)據(jù)集合中抽取出來，并從不同角度顯示，從而使大型數(shù)據(jù)庫 作為一個豐富、可靠的資源為知識的提取服務(wù)。 實際上，數(shù)據(jù)挖掘是知識發(fā)現(xiàn)過程中的一個重要步驟，但有些文獻并不區(qū)分數(shù)據(jù) 挖掘與知識發(fā)現(xiàn)。一般在研究領(lǐng)域被稱作數(shù)據(jù)庫中的知識發(fā)現(xiàn)( k d d ) ，而在工程領(lǐng) 域則稱之為數(shù)據(jù)挖掘( d m ) 。 1 1 3 數(shù)據(jù)挖掘的分類 數(shù)據(jù)挖掘相關(guān)的理論與技術(shù)可以按挖掘任務(wù)、挖掘?qū)ο?、挖掘方法與發(fā)現(xiàn)知識的 種類來分類口，6 1 ： 1 、按挖掘任務(wù)分類：包括分類或預(yù)測模型知識發(fā)現(xiàn)，數(shù)據(jù)聚類，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)， 依賴關(guān)系或依賴模型發(fā)現(xiàn)，時序模式發(fā)現(xiàn)，異常與趨勢發(fā)現(xiàn)等。 2 、按挖掘?qū)ο蠓诸悾喊P(guān)系數(shù)據(jù)庫、面向?qū)ο髷?shù)據(jù)庫、空間數(shù)據(jù)庫、時態(tài)數(shù) 據(jù)庫、文本數(shù)據(jù)庫、多媒體數(shù)據(jù)庫、異構(gòu)數(shù)據(jù)庫、數(shù)據(jù)倉庫、演繹數(shù)據(jù)庫和w e b 數(shù) 據(jù)庫等。 3 、按挖掘方法分類：包括統(tǒng)計方法、機器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法和數(shù)據(jù)庫方 法。 4 、按發(fā)現(xiàn)知識的種類分類：數(shù)據(jù)挖掘主要發(fā)現(xiàn)以下知識廣義型知識、分類 知識、聚類知識、關(guān)聯(lián)型知識、預(yù)測型知識、偏差型知識【1 ，2 1 。 1 1 4 數(shù)據(jù)挖掘的任務(wù) 數(shù)據(jù)挖掘的任務(wù)可分為1 , 2 , 7 】： 1 、分類與預(yù)測：分類是指基于一個可預(yù)測屬性把事例分成多個類別。分類的目 的是提出一個分類函數(shù)或分類模型( 即分類器) ，通過分類器將數(shù)據(jù)對象映射到某一 個給定的類別中。預(yù)測是構(gòu)造和使用模型評估無標號樣本類，或評估給定樣本可能 具有的屬性值或值區(qū)間。預(yù)測與分類的不同，一般觀點認為：使用預(yù)測法來預(yù)測類 3 基于信患、熵和子空間的離群數(shù)據(jù)挖掘算法研究 標號為分類，而用預(yù)測法預(yù)測連續(xù)值( 如使用回歸法) 為預(yù)測 1 ，2 丌。 2 、聚類：聚類就是將物理或抽象的對象集合分成多個組的過程，聚類生成的組 稱為簇( c l u s t e r ) ，即簇是數(shù)據(jù)對象的集合。聚類增強了人們對客觀現(xiàn)實的認識，是 概念描述和偏差分析的先決條件。聚類技術(shù)主要包括傳統(tǒng)的模式識別方法和數(shù)學(xué)分 類學(xué)。聚類就是要讓生成的簇的內(nèi)部，任何兩個對象之間具有較高的相似度，而屬 于不同簇的兩個對象間具有較高的相異度。 3 、關(guān)聯(lián)分析：關(guān)聯(lián)規(guī)則主要用于發(fā)現(xiàn)交易數(shù)據(jù)庫數(shù)據(jù)項之間的關(guān)聯(lián)關(guān)系，所以 它也被稱為購物籃分析。數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。 關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依賴性或相互關(guān)聯(lián)性。關(guān)聯(lián)分析的目 的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)絡(luò)。有時并不知道數(shù)據(jù)庫中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使 知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。設(shè)一個數(shù)據(jù)庫中的數(shù)據(jù) 集合記為d ，d = t l ，t 2 ，垃，“) ，f k = i l ，i 2 ，f m ，f p ) ，氏( k _ 1 ，2 ，n ) 稱為事 務(wù)( t r a n s a c t i o n ) ，i m ( m = 1 ，2 ，p ) 是項目( i t e m ) 。項目的集合稱為項集，事務(wù)的集合 稱為事務(wù)集。關(guān)聯(lián)規(guī)則具有如下兩個重要的屬性支持度：p ( xu ，即x 和y 兩個項集在事務(wù)集d 中同時出現(xiàn)的概率。置信度：p ( y x ) ，即在出現(xiàn)項集x 的事務(wù) 集d 中，項集y 也同時出現(xiàn)的概率。同時滿足最小支持度閾值和最小置信度閾值的 規(guī)則稱為強規(guī)則。給定一個事務(wù)集d ，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度 分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強規(guī)則的問 題。典型的關(guān)聯(lián)規(guī)則算法有a p r i o r i 算法【8 】和f p 樹算法【引。 4 、偏差分析：偏差分析是為了找出一些特殊的事例，這些事例的行為與其他有 明顯的不同。偏差分析又被稱為孤立點( o u t l i e r ) 檢測、異常檢測或離群數(shù)據(jù)挖掘，它 用來檢測與前面觀察的行為有重大改變的行為。偏差分析現(xiàn)已有很多應(yīng)用，例如， 在地震前夕，地下水中的氡等惰性元素含量異常升高；含油區(qū)域的重力加速度g 的 值低于非含油區(qū)域等。因此，偏差分析往往可以使人們發(fā)現(xiàn)一些真實的，但又出乎 意料的知識。通過對偏差分析的研究，發(fā)現(xiàn)不正常的行為和模式，有著非常重要的 意義。但迄今，沒有一種標準的偏差分析技術(shù)，它仍然是一個熱門的研究方向。 1 1 5 數(shù)據(jù)挖掘的應(yīng)用 數(shù)據(jù)挖掘技術(shù)從產(chǎn)生開始就是面向應(yīng)用的。但是國內(nèi)較國外的數(shù)據(jù)挖掘市場有所 欠缺。迄今為止，數(shù)據(jù)挖掘技術(shù)的應(yīng)用主要集中在零售市場貿(mào)易、電信、金融、網(wǎng) 絡(luò)安全、生物醫(yī)學(xué)、天文物理等領(lǐng)域。對于零售市場貿(mào)易主要應(yīng)用有價格分析、消 費群體分析、分析庫存需求、預(yù)測銷售趨勢等；電信領(lǐng)域主要應(yīng)用有客戶欺詐、客 4 第一章緒論 戶流失等分析；金融領(lǐng)域( 如銀行、保險公司、證券公司等) 主要應(yīng)用有財務(wù)欺詐、 信用卡欺詐、客戶信譽評分、企業(yè)信用評分等；網(wǎng)絡(luò)安全主要應(yīng)用有信息安全、入 侵檢測等；生物醫(yī)學(xué)主要是d n a 分析、醫(yī)學(xué)影像數(shù)據(jù)自動分析、生理參數(shù)監(jiān)護數(shù)據(jù) 分析；而天文物理則主要集中利用異常檢測尋找稀有的未知類型天體1 0 。1 4 】。 1 1 6 目前存在的問題與發(fā)展新趨勢 盡管數(shù)據(jù)挖掘與知識發(fā)現(xiàn)在許多領(lǐng)域都得到了廣泛的應(yīng)用，但對其技術(shù)的研究 還尚不成熟，在實際應(yīng)用中仍存在一定的局限性，具體表現(xiàn)為以下幾個方面【l 副： 1 、超大規(guī)模數(shù)據(jù)庫和高維數(shù)據(jù)問題：隨著數(shù)據(jù)庫規(guī)模的迅速增長和數(shù)據(jù)的維度 不斷增高，一些傳統(tǒng)的算法已滿足不了需要。 2 、網(wǎng)絡(luò)與分布式環(huán)境下的k d d 問題：目前，大部分算法還停留在靜態(tài)數(shù)據(jù)的 處理上，網(wǎng)絡(luò)與分布式環(huán)境下要求系統(tǒng)可以處理動態(tài)變化的數(shù)據(jù)集。 3 、非標準格式的數(shù)據(jù)、多媒體數(shù)據(jù)、面向?qū)ο髷?shù)據(jù)處理問題：現(xiàn)有的數(shù)據(jù)挖掘 工具仍停留在對數(shù)值型的結(jié)構(gòu)化數(shù)據(jù)的處理上，對于半結(jié)構(gòu)化、非結(jié)構(gòu)化的數(shù)據(jù)形 式，如圖形、圖像、文本或w e b 資源，還缺乏有效與可行的方法。 4 、證實技術(shù)局限問題：目前，系統(tǒng)還無法有效地證實所發(fā)現(xiàn)的知識正確與否， 這使所發(fā)現(xiàn)的知識缺乏普遍性，從而不能成為有用的知識。 5 、模式的易懂性問題：由于用戶可以理解所發(fā)現(xiàn)的知識不僅僅局限于數(shù)字或符 號，如果數(shù)據(jù)挖掘系統(tǒng)將挖掘出的知識以用戶易懂易讀的模式如圖形、自然語言或 可視化模式輸出，用戶則能更好地評價與利用這些知識。 就目前來看，將來的幾個熱點包括文本的數(shù)據(jù)挖掘( t e x t u a lm i n i n g ) 、生物信息 或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的數(shù)據(jù)挖掘以及基于w e b 的數(shù)據(jù)挖掘( w e bs i t e d a t am i n i n g ) 【1 6 1 。 1 2 離群數(shù)據(jù)挖掘 離群數(shù)據(jù)挖掘的研究主要是對以下三個問題的研究【1 7 】：異常的數(shù)據(jù)是什么樣的， 即離群數(shù)據(jù)的定義；挖掘離群數(shù)據(jù)的有效方法；離群數(shù)據(jù)的意義，即對離群數(shù)據(jù)挖 掘結(jié)果的合理解釋。什么是離群數(shù)據(jù)( o u t l i e r ) ? 迄今為止，還沒有一個被普遍采納的 定義，統(tǒng)計學(xué)家d o u g l a sh a w k i n s 給出了離群點的本質(zhì)性定義【1 8 ，1 9 】：“離群點與其他 點如此不同，以至于讓人懷疑它們是由另外一個不同的機制產(chǎn)生的 。離群數(shù)據(jù)挖 掘具有廣泛的應(yīng)用，如電信和信用卡欺騙、貸款審批、藥物研究、醫(yī)療分析、消費 者行為分析、氣象預(yù)報、金融領(lǐng)域客戶分類、網(wǎng)絡(luò)入侵檢測等。 基于信息熵和子空間的離群數(shù)據(jù)挖掘算法研究 近年來，研究人員提出了許多離群數(shù)據(jù)挖掘算法，這些方法大致分為幾類：基 于統(tǒng)計( s t a t i s t i c a l b a s e d ) 的方法、基于深度( d e p t h - b a s e d ) 的方法、基于偏離 ( d e v i a t i o n b a s e d ) 的方法、基于距離( d i s t a n c e b a s e d ) 的方法、基于密度( d e n s i t y b a s e d ) 的方法。下面分別對各個算法進行介紹【1 7 , 2 0 , 2 1 1 。 1 2 1 基于統(tǒng)計的方法 基于統(tǒng)計的方法是出現(xiàn)最早的離群數(shù)據(jù)挖掘的方法。主要思想是【2 2 j ：假設(shè)給定的 數(shù)據(jù)集服從一個隨機分布，如正態(tài)分布等，用不一致性測試( d i s c o r d a n c et e s t ) 識別離 群點。存在問題是用戶需要事先知道數(shù)據(jù)集參數(shù)與分布；現(xiàn)實世界中的數(shù)據(jù)不符合 任何一種標準分布；即使存在一個標準分布，分布擬合的過程耗時過長；此外，基 于統(tǒng)計的方法絕大多數(shù)只適合于單變量的數(shù)值型數(shù)據(jù)。 1 2 2 基于深度的方法 該方法是由r u t s 和r o u s s e e u w 2 3 1 提出的，其基礎(chǔ)是計算幾何學(xué)和計算各層的k 維凸包。每個數(shù)據(jù)對象被映射為k 維空間的一個點，并賦予每個點特定定義的“深 度”，根據(jù)這個深度數(shù)據(jù)被劃分為不同的層次，深度“淺”的數(shù)據(jù)對象是離群數(shù)據(jù) 的可能性更大。但當(dāng)數(shù)據(jù)維數(shù) 3 時，算法的可行性則非常差。 1 2 3 基于偏離的方法 a r g r a w a l 和r a g a r a n 2 4 1 提出一種“序列異常( s e q u e n t i a le x c e p t i o n ) ”的概念。算法 給定n 個對象的集合s ，建立一個子集序列 s 1 ，s 2 ，s m ) ，這里2 m n ，滿足s j 1 s j 其中s j 薩的數(shù)據(jù)點p 不超過n 1 個，那么稱p 為薩異常。如果對數(shù)據(jù)點根據(jù)它 們的薩( p ) 距離進行排序，那么前n 個數(shù)據(jù)點就被看作離群點。此算法的不足是要計 算每個數(shù)據(jù)點的d l 【( p ) ，每計算一個數(shù)據(jù)點的d k ( p ) 瓣i 描一趟數(shù)據(jù)集，顯然在處 理大數(shù)據(jù)集時，i o 代價與算法的時間復(fù)雜度非常高。 1 2 5 基于密度的方法 基于密度的離群檢測方法是在基于距離的方法的基礎(chǔ)上改進后提出來的，于是該 方法對異常的定義比基于距離的方法更貼近h a w k i n s 的異常定義，因此能夠檢測出 基于距離的方法所不能識別的一類異常數(shù)據(jù)局部異常，即每個數(shù)據(jù)點的異常程 度只與它周圍數(shù)據(jù)點的距離有關(guān)，而與數(shù)據(jù)集中的其他數(shù)據(jù)點無關(guān)。 使用一個例子來解釋這類局部異常( 圖1 2 ) 【2 0 】。這是一個包含4 0 2 個數(shù)據(jù)點的2 維數(shù)據(jù)集，其中的3 0 0 個對象落在簇c l 中，1 0 0 個對象落在簇c 2 中，另外有兩個對 象o l 和0 2 。顯然，c l 所形成的簇的密度大于e 2 的。由h a w k i n s 的定義【1 8 ，1 9 1 可以知 道：o l 與0 2 都應(yīng)該是離群點，而c l 和c 2 中的數(shù)據(jù)點不應(yīng)該是離群點。但是根據(jù) k n o r r 與n g 【2 5 】的定義，只有0 l 是一個“合理”的d b ( p c t , 矗i r i ) 離群點。 口l 傻 榮q 圖1 - 2 局部異常示意圖 f i g u r e1 2l o c a lo u t l i e rs c h e m a t i c b r e u n i g 冪l l k r i e g e l 2 印首先提出了基于局部離群因子( l o c a lo u t l i e rf a c t o r , l o f ) 的 離群檢測算法是基于密度方法的一個經(jīng)典例子?；舅枷耄菏紫犬a(chǎn)生所有數(shù)據(jù)點的 m i n p t s 領(lǐng)域與m i n p t s 距離，并計算到其中每個數(shù)據(jù)點的距離；然后計算每個數(shù)據(jù)點 7 基丁信息、熵和子空間的離群數(shù)據(jù)挖掘算法研究 f l 勺l o f ：最后根據(jù)l o f 來檢測離群點。b r e u n i g 矛b k r i e g e l 認為離群不再是一個二值屬 性( 某一個數(shù)據(jù)點要么是離群點，要么是正常點) ，而應(yīng)該是一個度量。但是此方法 對數(shù)據(jù)的稀疏性和離群意義難以解釋，并且i o 代價通常比較高。 1 2 6 高維離群數(shù)據(jù)挖掘方法 以上幾種方法處理高維數(shù)據(jù)時，缺乏可伸縮性，效果不理想。此外，在文獻 2 8 3 l 】 中的離群數(shù)據(jù)挖掘算法僅僅作為聚類分析的一個副產(chǎn)品。然而，這些技術(shù)并未將離 群點定義為屬于聚類的點，而是作為背景噪聲嵌入到聚類中的。 傳統(tǒng)的離群檢測方法在處理高維數(shù)據(jù)時會遇到“維災(zāi)難( t h ec u r s eo f d i m e n s i o n a l i t y ) 3 2 1 ”問題，許多算法的時間復(fù)雜度隨維數(shù)的增加呈指數(shù)增長。隨著 維數(shù)的增加，高維數(shù)據(jù)越來越“稀疏( s p a r s e ) ，這使得基于距離和密度的異常定 義在高維空間中失效且變得沒有直觀意義，導(dǎo)致幾乎所有的記錄在傳統(tǒng)的定義下幾 乎都成了離群點。在處理高維數(shù)據(jù)時，一種稱作“空空間現(xiàn)象( e m p t ys p a c e p h e n o m e n o n ) p 習(xí)”在空區(qū)域中數(shù)據(jù)點的密度可能會很高的現(xiàn)象的問題也是 影響離群數(shù)據(jù)挖掘的一個方面。它是說相對于一個點的可能方向的數(shù)目，隨著維數(shù) 的增大呈指數(shù)增長，結(jié)果是，雖然與中心點之間的距離仍然服從同樣的分布，但數(shù) 據(jù)點之間的距離也會隨著維數(shù)的增加而增大，會影響離群檢測的準確率。 為了解決上述的問題，a g g a r w a l & y u 3 4 】在此領(lǐng)域做出很多貢獻。他們先提出將高 維空間投影到子空間，采用演化計算找出最優(yōu)子空間，從而降低原來空間的維數(shù)， 最后利用傳統(tǒng)的檢測方法來發(fā)現(xiàn)異常，但是算法的運行效率非常差。2 0 0 4 年他們改 進算法，利用稀疏度系數(shù)度量子空間中數(shù)據(jù)的偏移程度，并采用改進的遺傳算法搜 索稀疏度系數(shù)最小的子空間，以發(fā)現(xiàn)離群數(shù)據(jù)。但是這些算法存在著一些缺陷： 在實際應(yīng)用中，對于一些稀疏度系數(shù)并非全局最小的子空間，其包含的對象也可能 是離群數(shù)據(jù)，文獻 3 4 】采用改進的遺傳算法，在搜索稀疏度系數(shù)最小的子空間過程中， 漏掉了一些稀疏度系數(shù)并非全局最小的子空間，從而不能發(fā)現(xiàn)所有的離群數(shù)據(jù)。 不能確保最后發(fā)現(xiàn)的是稀疏度系數(shù)最小的子空間，文獻 3 4 中的實驗證明了這一點， 這使得檢測的離群數(shù)據(jù)不準確。在計算稀疏度系數(shù)過程中，必須掃描記錄集，以 求出當(dāng)前子空間中包含的對象數(shù)。而該算法需要頻繁地產(chǎn)生子空間，并計算稀疏度 系數(shù)，降低了算法的效率。僅能對數(shù)值屬性數(shù)據(jù)進行分析處理。 1 2 7 離群數(shù)據(jù)挖掘當(dāng)前研究熱點 1 、海量空間數(shù)據(jù)的離群數(shù)據(jù)檢測，關(guān)鍵是如何提高算法的效率與有效地解決內(nèi) 存容量局限性的問題。 8 第一章緒論 2 、高維空間數(shù)據(jù)的離群數(shù)據(jù)檢測，通過各種技術(shù)對數(shù)據(jù)集進行選維、降維，去 除與數(shù)據(jù)簇?zé)o關(guān)的維，然后對子空間數(shù)據(jù)進行離群點檢測。 3 、分布式環(huán)境下的離群數(shù)據(jù)檢測，需要解決不同位置的數(shù)據(jù)可能存在重疊、各 位置的參數(shù)選取等問題。 4 、動態(tài)的數(shù)據(jù)集的離群數(shù)據(jù)檢測，即對流數(shù)據(jù)在線處理的需求更為迫切，因此， 只需進行一次掃描便得到結(jié)果的數(shù)據(jù)流異常檢測算法，成為當(dāng)前的研究熱點。 1 3 論文研究內(nèi)容與組織結(jié)構(gòu) 1 3 1 研究內(nèi)容 本文的主要研究內(nèi)容是離群數(shù)據(jù)挖掘的方法研究?，F(xiàn)有的離群數(shù)據(jù)挖掘方法存 在著受人為因素影響較大，而且不能對挖掘出來的離群點做進一步分析。本論文針 對以上問題進行了研究，其主要內(nèi)容如下： 1 、將信息熵的理論引入到離群數(shù)據(jù)挖掘的領(lǐng)域，并利用信息熵與數(shù)據(jù)集自身的 特點，研究了一種新的度量離群點的方法。 2 、引入基于信息熵的離群度量因子，研究了一種新的離群數(shù)據(jù)挖掘算法 ( o m b i e ) 。 3 、分析了離群檢測算法在處理高維數(shù)據(jù)時存在的問題，研究了一種離群數(shù)據(jù)挖 掘新算法( o m b c a s ) 。 1 3 2 論文組織結(jié)構(gòu) 論文總共分為六章，具體安排如下： 第一章介紹了數(shù)據(jù)挖掘的基本概念及相關(guān)知識，以及幾類離群檢測方法，并分 析和評價了這些方法的優(yōu)點和不足。 第二章介紹了與本論文相關(guān)的理論，如信息熵，子空間。 第三章研究了一種基于信息熵的離群數(shù)據(jù)挖掘算法o m b i e 。 第四章研究了一種基于特征屬性子空間的離群數(shù)據(jù)挖掘o m b c a s 。 第五章總結(jié)己取得的研究成果并指出未來的研究方向。 9 第二章信息熵與子空間概述 2 1 信息熵 第二章信息熵與子空間概述 2 1 1 基本概念與公式 熵這個概念起源于對熱力學(xué)的研究，后來物理學(xué)家香農(nóng)將其引入到信息論中，并 用它來描述信源平均不確定性，現(xiàn)在一般將其稱為香農(nóng)熵或信息熵。信息熵度量的 意義是：當(dāng)確定一個隨機變量的值之后，就獲得了信息，獲得的信息量的大小與隨 機變量的隨機性強弱有關(guān)，隨機變量的隨機性越大獲得的信息量就越大，反之亦然 【l5 。下面引入信息熵的數(shù)學(xué)描述： 假設(shè)有一組離散的符號集 v l ，v 2 ，v n ) ，每個符號具有相應(yīng)的出現(xiàn)頻率p i 。為了 衡量用這組符號組成的特定序列的隨機性( 不確定性或不可預(yù)測性) ，定義離散分布 的熵為： , 日= 一只l o g 。只 ( 2 1 ) 其中，對數(shù)的底a 可為任何正數(shù)，一般取2 ，此時熵的單位為“比特。規(guī)定當(dāng) p i = 0 時 言加1 a = 。 億2 ) ，= 0y 這里要特別注意熵的值并不依賴于符號( 對象、數(shù)據(jù)) 本身，而只依賴于這些符號 ( 對象、數(shù)據(jù)) 的概率【3 5 】。信息熵有以下四個重要性質(zhì)3 6 , 3 7 】： 1 、非負性： h ( x ) o 2 、確定性：h ( 1 ，0 ) = h ( 1 ，0 ，0 ) = h ( 1 ，0 ，0 ，0 ) = = h ( 1 ，0 ，0 ) = 0 3 、可加性： 相對獨立的狀態(tài)，其信息熵的和等于和的信息熵。h ( x y ) = h ( ) ( ) + h ( y ) 4 、極值性： h ( p 。，p ：，p 。) h f ，三，三，三 ：l 。g 珂 刀胛n 定義2 1 ：自信息熵j & ) 3 6 , 3 7 】某事件a i 發(fā)生所含有的信息量稱為自信息熵；事 件的自信息熵定義為，其中e ( a i ) 是事件a i 發(fā)生的概率。 ，( q ) 壘一l o g p ( a , ) ( 2 3 ) 基于信息熵和子空間的離群數(shù)據(jù)挖掘算法研究 定義2 2 ：若x 是一個離散的隨機變量，s 是可能取值的集合， 概率函數(shù)，則信息熵h ( x ) j t n 公式( 2 4 ) 所定義： h ) = 一p ( x ) l o g ：( p ) ) x e s ( j 1 尸 ) 是x 的 ( 2 4 ) 對于含有多個屬性的記錄豆= x l ，以) 的信息熵如公式( 2 5 ) 計算： h 瞳) = 一ep ，氕) l o gp g l ，以) ( 2 5 ) e s ( x i )e s ( x n ) 如果記錄的屬性之間相互獨立，根據(jù)信息熵的性質(zhì)3 ，公式( 2 5 ) 可以轉(zhuǎn)化成公式 ( 2 6 ) 。換句話說，屬性值的聯(lián)合概率可以轉(zhuǎn)化成每個屬性概率的乘積，因此總的信 息熵就等于每個屬性的信息熵之和。 h 瞳) = 一ep 瓴) p 魄) ) l o gp 瓴) p 。) ) x l s ( x 1 ) x n s ( x n ) = h ) + h ) + + h 甌) ( 2 6 ) 2 1 2 信息熵的引入 無論是基于距離的離群檢測算法，還是基于密度、深度的離群檢測算法，都是 將給定系統(tǒng)看作是一個空間，而再將離群數(shù)據(jù)看作是此空間的若干稀疏數(shù)據(jù)點，所 以離群數(shù)據(jù)有時也被人們稱作離群點。本文另辟蹊徑尋求一種不同理論系統(tǒng)下的度 量離群數(shù)據(jù)的新方法。 信息熵完全建立在原始數(shù)據(jù)的基礎(chǔ)上，客觀性比較強，受人為因素影響較小。 熵的值并不依賴于符號( 對象、數(shù)據(jù)) 本身，而只依賴于這些符號( 對象、數(shù)據(jù)) 的頻 率( 概率) 3 5 】。而基于照離和偏離的離群檢測算法都需要事先確定參數(shù)，如p 訂，如i n 參數(shù)選擇不當(dāng)，會產(chǎn)生錯誤結(jié)論。 由于信息熵只依賴于記錄中每個屬性的概率，因此，屬性的取值可以是數(shù)值型， 也可以是非數(shù)值型( 如，字符型) 。也就是說，信息熵可以將數(shù)值屬性與標稱屬性整 合在一個統(tǒng)一框架中，進行處理。而基于統(tǒng)計和距離的離群檢測算法較難對非數(shù)值 屬性數(shù)據(jù)進行挖掘。 基于統(tǒng)計的方法在解釋時發(fā)生多義性，原因是：同一個離群數(shù)據(jù)點有可能是不 同的分布模型檢測出來的，即產(chǎn)生離群點的機制有可能不唯一，從而產(chǎn)生了多義性。 由于基于信息熵的方法采用的是唯一的離群數(shù)據(jù)產(chǎn)生機制，所以不會發(fā)生多義性的 情況。 2 1 3 基于信息熵的離群數(shù)據(jù)挖掘方法研究現(xiàn)狀 2 0 0 6 年，國內(nèi)的何曾友3 8 1 等人提出了基于信息熵的快速貪婪算法( g r e e d a l g ) 。 1 2 第二章信息熵與子空間概述 g r e e d a l g 算法采用了l s a 算法中的優(yōu)化模式，事先人為設(shè)定期望產(chǎn)生的離群點個數(shù) k ，同時參數(shù)k 用于發(fā)現(xiàn)一個勢為k 的離群數(shù)據(jù)集o ( 1 0 i - k ) 。但是g r e e d a l g 算法存 在以下不足：需要人為事先給出期望產(chǎn)生的離群點個數(shù)k ，這會有不能發(fā)現(xiàn)全部和 多發(fā)現(xiàn)離群點的問題；文中提到g r e e d a l g 算法需要全面掃描數(shù)據(jù)集k 次，因此i o 代價通常比較高；因為使用貪婪算法的策略，計算過程中很容易陷入局部最小， 而該算法未對此問題采取有效措施；作者在文中沒有解釋依據(jù)最大熵影響 ( m a x i m a le n t r o p yi m p a c t ) 來識別離群點的原理。 2 0 0 8 年，倪巍偉等人提出基于局部信息熵的加權(quán)子空間離群點檢測算法 ( s p o d ) 。通過對數(shù)據(jù)點在各維進行鄰域信息熵分析，生成相應(yīng)的離群子空間和屬性 權(quán)向量，進一步提出子空間加權(quán)距離等概念，采用基于l o f 的思想，計算數(shù)據(jù)點的 子空間離群影響因子來判斷數(shù)據(jù)點是否為離群點。缺點是在處理高維數(shù)據(jù)時與l o f 算法處于一個數(shù)量級0 ( n 2 ) ，而且還需要人為事先設(shè)置很多參數(shù)3 9 1 ，從而影響了檢測 的結(jié)果。 同年，于紹越等人提出基于信息熵的相對離群點的檢測方法( e n b r o d ) 。文中首 先引入去一劃分信息熵增量的概念，并在其基礎(chǔ)上給出了每個對象所對應(yīng)的相對離 群點因子( r o f ) 的定義。利用e n b r o d 算法來實現(xiàn)對r o f 的計算，但e n b r o d 算 法也需要人為事先設(shè)置參數(shù)，而這正影響了算法的運行效果【4 0 】。 2 2 子空間 由于高維數(shù)據(jù)存在稀疏與不規(guī)則的特點，因此傳統(tǒng)的離群檢測方法在處理高維 數(shù)據(jù)時往往會失效。研究人員對此給出一定的方法來解決高維數(shù)據(jù)挖掘遇到的問題。 其中，文獻 1 3 提出一種基于子空間的離群數(shù)據(jù)挖掘算法。該算法的基本思想為對于 實際應(yīng)用中，數(shù)據(jù)的偏離大部分都集中在低維子空間中，高維數(shù)據(jù)中的一些數(shù)據(jù)在 某幾維上有明顯的偏移，而其余維均沒有偏移，進而利用進化算法搜索稀疏子空間， 把稀疏子空間中的數(shù)據(jù)定義為離群數(shù)據(jù)。 所謂子空間是相對于全局空間而言的，它是指在數(shù)據(jù)集伊( 以彳) 中，從屬性集么 中選取d 維，其中i d i 3 時，算法的可行性貝t j t l z 常差；3 ) 基于偏離的方法【2 4 】：此方法 由a m i n g 等人提出，它需要首先確定相異度函數(shù)才能進行離群知識發(fā)現(xiàn)。如果相異 函數(shù)選取的不合適，則得不到滿意的結(jié)果，目前此方法主要是理論上的研究，較難 在實際問題中使用；4 ) 基于距離的方法【2 5 】：此方法是由k n o r r 和n 9 1 9 9 8 年提出的。 他們將離群點定義為與其它數(shù)據(jù)的距離大于某個閾值的數(shù)據(jù)，通常被描述為d b ( p c t ， d m i n ) ，使用該方法需要用戶通過實驗確定合適的p c t ，d m i f l 參數(shù)，如p c t , d m i n 參數(shù)選擇 不當(dāng)，會產(chǎn)生錯誤結(jié)論；5 ) 基于密度的方法【2 7 】：b r e u n i n g 和k r i e g e l 引入了局部異 常因子的概念，并認為離群點不再是一個二值屬性( 不是離群點，就是正常點) ，而 是某種度量，更加符合現(xiàn)實生活中的應(yīng)用。離群點被定義為相對于全局的局部離群 點，然后計算每個點的局部異常因子，最后根據(jù)局部異常因子判斷是否為離群數(shù)據(jù)。 其主要缺陷則是數(shù)據(jù)的稀疏性和離群意義難以解釋，i o 代價通常比較高。此外，在 1 6 第三章基于信息熵的離群數(shù)據(jù)挖掘算法 文獻：2 8 - 3 1 j 中，離群數(shù)據(jù)挖掘算法僅作為聚類分析的一個副產(chǎn)品。 傳統(tǒng)的離群檢測方法在處理高維數(shù)據(jù)時會遇到“維災(zāi)難( t h ec u r s eo f d i m e n s i o n a l i t y ) 的問題，許多算法的時間復(fù)雜度隨維數(shù)的增加呈指數(shù)增長。隨著維 數(shù)增加，高維數(shù)據(jù)越來越“稀疏( s p a r s e ) ”，這使得基于距離和密度的異常定義在高 維空間中失效且變得沒有直觀意義，導(dǎo)致幾乎所有的記錄在傳統(tǒng)的定義下幾乎都成 了離群點。 3 2 2 信息熵與離群數(shù)據(jù) 2 0 0 6 年，國內(nèi)的何曾友【3 8 】等人提出了基于信息熵的快速貪婪算法( g r e e d a l g ) 。 g r e e d a l g 算法采用了l s a 算法中的優(yōu)化模式，事先人為設(shè)定期望產(chǎn)生的離群點個數(shù) k ，同時參數(shù)k 用于發(fā)現(xiàn)一個勢為k 的離群數(shù)據(jù)集o ( 1 0 l = k ) 。但是g r e e d a l g 算法存 在以下不足：需要人為事先給出期望產(chǎn)生的離群點個數(shù)k ，這會有不能發(fā)現(xiàn)全部和 多發(fā)現(xiàn)離群點的問題；文中提到g r e e d a l g 算法需要全面掃描數(shù)據(jù)集k 次，因此i o 代價通常比較高；因為使用貪婪算法的策略，計算過程中很容易陷入局部最小， 而該算法未對此問題采取有效措施；作者在文中沒有解釋依據(jù)最大熵影響 ( m a x i m a le n t r o p yi m p a c t ) 來識別離群點的原理。 2 0 0 8 年，倪巍偉等人提出基于局部信息熵的加權(quán)子空間離群點檢測算法 ( s p o d ) 。通過對數(shù)據(jù)點在各維進行鄰域信息熵分析，生成相應(yīng)的離群子空間和屬性 權(quán)向量，進一步提出子空間加權(quán)距離等概念，采用基于l o f 的思想，計算數(shù)據(jù)點的 子空間離群影響因子來判斷數(shù)據(jù)點是否為離群點。缺點是在處理高維數(shù)據(jù)時與l o f 算法處于一個數(shù)量級o ( n 2 ) ，而且還需要人為事先設(shè)置很多參數(shù) 3 9 1 ，從而影響了檢測 的結(jié)果。 同年，于紹越等人提出基于信息熵的相對離群點的檢測方法( e n b r o d ) 。文中 首先引入去一劃分信息熵增量的概念，并在其基礎(chǔ)上給出了每個對象所對應(yīng)的相對 離群點因子( r o f ) 的定義。利用e n b r o d 算法來實現(xiàn)對r o f 的計算，但e n b r o d 算法也需要人為事先設(shè)置參數(shù)，而這正影響了算法的運行效果1 4 0 1 。 3 3 信息熵 信息熵被用來度量一個系統(tǒng)的“無序”程度和“純凈”程度。信息熵是信息有用 程度的一種表現(xiàn)形式。 為了簡化對信息熵的計算，在本章中一律假設(shè)數(shù)據(jù)集中的記錄的屬性間是相互獨 立的，可以使用第二章第二小節(jié)介紹的信息熵公式( 2 6 ) 1 7 基丁信息熵和子空間的離群數(shù)據(jù)挖掘算法研究 3 4 基于信息熵的離群數(shù)據(jù)挖掘算法 3 4 1 離群數(shù)據(jù)度量因子 信息熵可以用來度量一個系統(tǒng)無序和雜亂程度。熵值越大，說明系統(tǒng)中的數(shù)據(jù)越 無序，系統(tǒng)越雜亂；反之，熵值越小，則說明系統(tǒng)中的數(shù)據(jù)越有序，系統(tǒng)越純凈。 如果將信息熵理論應(yīng)用到離群數(shù)據(jù)挖掘中，根據(jù)h a w k i n s 1 8 】對離群點定性地描述， 離群數(shù)據(jù)是使系統(tǒng)不“純凈、“雜亂”的原因，相當(dāng)于系統(tǒng)中的“雜質(zhì)”。如果去除 系統(tǒng)中的不“純凈”因素，那么系統(tǒng)則變得相對“有序”和“純凈”，熵值比去除前 相對變小。去除后，熵值相對減小地較大，說明去除的因素相對“雜亂”；熵值相對 減小地較小，說明去