基于層次的孤立點(diǎn)檢測算法設(shè)計及實(shí)現(xiàn)

1、 畢業(yè)設(shè)計(論文)題 目 基于層次的孤立點(diǎn)檢測算法設(shè)計及實(shí)現(xiàn) 學(xué)院名稱 計算機(jī)科學(xué)與技術(shù)學(xué)院 指導(dǎo)教師 肖基毅 職 稱 教授 班 級 本05計算04班 學(xué) 號 20054440428 學(xué)生姓名 李敬康 2009年5月29目 錄摘要iiiAbstractiv第一章 緒論11.1研究背景及研究意義11.3論文組織結(jié)構(gòu)2第二章 相關(guān)知識32.1數(shù)據(jù)挖掘概述3數(shù)據(jù)挖掘概念3數(shù)據(jù)挖掘過程4數(shù)據(jù)挖掘算法組成52.2聚類分析5聚類算法簡介6基于層次的聚類方法8距離、相似系數(shù)及聚類分析中的數(shù)據(jù)類型142.3孤立點(diǎn)分析17基于統(tǒng)計的方法18基于距離的孤立點(diǎn)檢測算法18基于偏離的孤立點(diǎn)探測202.4本章小結(jié)20第

2、三章 算法設(shè)計與實(shí)現(xiàn)213.1算法相關(guān)定義213.2算法描述223.3算法實(shí)現(xiàn)24數(shù)據(jù)結(jié)構(gòu)定義24算法函數(shù)說明253.4算法分析30算法復(fù)雜度30算法的局限性303.5本章小結(jié)30第四章 結(jié)論31參考文獻(xiàn)32謝辭33摘要摘要：孤立點(diǎn)檢測是數(shù)據(jù)挖掘的一個重要方面，因其獨(dú)特的知識發(fā)現(xiàn)功能而得到較為深入的研究。孤立點(diǎn)檢測算法己經(jīng)在金融欺詐檢測、網(wǎng)絡(luò)入侵檢測、生態(tài)系統(tǒng)失調(diào)天氣預(yù)報等風(fēng)險控制領(lǐng)域得到了廣泛的應(yīng)用。聚類分析和孤立點(diǎn)檢測技術(shù)己經(jīng)廣泛應(yīng)用于模式識別、數(shù)據(jù)分析、圖像處理、市場研究等許多領(lǐng)域。聚類及孤立點(diǎn)檢測算法研究已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中非?；钴S的一個研究課題。本文介紹了數(shù)據(jù)挖掘理論，在深入研

3、究聚類分析和孤立點(diǎn)檢測算法的基礎(chǔ)上提出了基于層次的孤立點(diǎn)檢測算法。給出了算法較為詳細(xì)的描述，闡述了算法中各個函數(shù)的功能。該算法基于層次方法，采用歐幾里得距離進(jìn)行凝聚的層次聚類。根據(jù)聚類中含有單一數(shù)據(jù)元素的類數(shù)來確定初始孤立點(diǎn)個數(shù)，然后根據(jù)距離閥值判斷是否為孤立點(diǎn)。通過對算法的性能進(jìn)行分析，該算法的時間復(fù)雜度為，空間復(fù)雜度為，其中N是數(shù)據(jù)規(guī)模。試驗(yàn)結(jié)果表明，基于層次的孤立點(diǎn)檢測算法能基本實(shí)現(xiàn)孤立點(diǎn)的檢測，并對孤立點(diǎn)進(jìn)行精確性分析。關(guān)鍵字：數(shù)據(jù)挖掘；層次聚類；凝聚；孤立點(diǎn)檢測；距離AbstractAbstract: Outlier detection is an important aspect

4、of Data Mining，which has get more depth research because of its unique knowledge discovery functions.Today，there are lots of efficient outlier detection algorithms which are widely used in financial fraud detection，network instruction detection，ecosystem imbalance，Weather forecast and other risk con

5、trol areas.Clustering analysis and outlier detection,as important parts of data mining,are widely applied to the fields such as pattern recognition,data analysis ,image processing,and market research.Research on clustering analysis and outlier detection algorithms has become a highly active topic in

6、 the data mining research.In this thesis,the author presents the theory of data mining,and based on deeply analysis the algorithms of clustering and outlier detection,the author advances hierarchical-based outlier-detection algorithm. Elaborates the idea of the algorithm,expounds the functions of al

7、gorithm.The algorithm based on hierarchical clustering and used Euclid distance to agglomerated clustering. According to a single cluster contains several types of data elements to determine the initial number of outliers, then determine whether the outlier with the threshold distance.Through an ana

8、lysis of the performance of algorithm,the computational complexity of the algorithm is ,and the spatial complexity of the algorithm is ,where N is the number dataset objects.Keywords: Data Ming ; Hierarchical Clustering; agglomeration;outlier detection;distance第一章 緒論1.1研究背景及研究意義由于計算技術(shù)和存儲技術(shù)的飛速發(fā)展，使人們在

9、短時間里就可以從各種信息源搜集和存儲大量的人工難以管理的資料。雖然現(xiàn)代數(shù)據(jù)庫技術(shù)可以對這些資料進(jìn)行經(jīng)濟(jì)地存儲，但還是需要一種技術(shù)來幫助人們分析、理解甚至可視化這些資料。因此就產(chǎn)生了KDD(Knowledge Discovery in Database)技術(shù)。它是一個從較低級資料中抽取高級知識的總體過程，就是從數(shù)據(jù)庫中識別有效的，新穎的，潛在有用的并最終可被理解的模式的一個非平凡過程。KDD包括很多內(nèi)容，其核心部分就是數(shù)據(jù)挖掘(DataMining)。近十多年來，數(shù)據(jù)挖掘逐漸成為數(shù)據(jù)庫和人工智能等研究領(lǐng)域的一個熱點(diǎn)。聚類（Clusetring)是數(shù)據(jù)挖掘中重要組成部分，所謂聚類，就是將數(shù)據(jù)對象分

10、組成多個類或簇(Cluster)，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。聚類源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘，統(tǒng)計學(xué)，機(jī)器學(xué)習(xí)，空間數(shù)據(jù)庫，生物學(xué)和市場營銷等。目前它己經(jīng)廣泛應(yīng)用于模式識別、數(shù)據(jù)分析、圖象處理和市場分析等。由于聚類被廣泛地應(yīng)用在許多領(lǐng)域，迄今為止，研究人員己經(jīng)提出了許多聚類算法，聚類算法大體上主要可以分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。孤立點(diǎn)檢測是數(shù)據(jù)挖掘中的一項重要技術(shù)，其目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)集中行為異常的少量的數(shù)據(jù)對象。在數(shù)據(jù)挖掘領(lǐng)域，孤立點(diǎn)檢測的研究對象是數(shù)據(jù)集中偏離絕大多數(shù)對象的很小一部分。在很多KDD

11、應(yīng)用中，發(fā)現(xiàn)孤立點(diǎn)比發(fā)現(xiàn)普通情況更有用，更重要。例如在欺詐探測中，孤立點(diǎn)可能預(yù)示著欺詐行為。在市場分析中，可用于確定極低或極高收入的消費(fèi)行為，或者在醫(yī)療分析中用于發(fā)現(xiàn)對多種治療方式的不尋常的反映。孤立點(diǎn)挖掘還可應(yīng)用于金融欺詐、網(wǎng)絡(luò)監(jiān)控、數(shù)據(jù)清洗、電子商務(wù)、職業(yè)運(yùn)動員的成績分析、故障檢測、天氣預(yù)報、醫(yī)藥研究、信貸信用等領(lǐng)域。在數(shù)據(jù)挖掘中，孤立點(diǎn)檢測算法大體上可分為:基于統(tǒng)計學(xué)的方法、基于距離的方法、基于密度的方法、基于偏離的方法等。研究孤立點(diǎn)的異常活動有助于發(fā)現(xiàn)隱藏在數(shù)據(jù)集中有價值的知識。1.2研究內(nèi)容及論文思路本文就以下內(nèi)容進(jìn)行了研究：1對數(shù)據(jù)挖掘理論、聚類分析算法、孤立點(diǎn)檢測算法、聚類與孤立

12、點(diǎn)檢測的關(guān)系等進(jìn)行了系統(tǒng)的研究學(xué)習(xí)，實(shí)現(xiàn)層次聚類的孤立點(diǎn)檢測。系統(tǒng)地研究了數(shù)據(jù)挖掘理論、聚類算法、孤立點(diǎn)檢測算法，在研究聚類算法和孤立點(diǎn)算法的基礎(chǔ)上，將聚類和孤立點(diǎn)檢測的過程相結(jié)合，實(shí)現(xiàn)了基于層次聚類的孤立點(diǎn)檢測算法。2基于層次聚類的孤立點(diǎn)檢測描述與實(shí)現(xiàn)。對基于層次的孤立點(diǎn)檢測算法進(jìn)行了系統(tǒng)描述，對算法中的數(shù)據(jù)結(jié)構(gòu)及函數(shù)進(jìn)行了說明，給出算法流程圖，并分析了該算法的時間復(fù)雜度和空間復(fù)雜度，以及改算法進(jìn)行孤立點(diǎn)檢測精確性的分析。本文用C+實(shí)現(xiàn)該算法。3結(jié)果驗(yàn)證及分析。對比傳統(tǒng)算法，對包括聚類及孤立點(diǎn)檢測正確性、精度、算法執(zhí)行時間、參數(shù)設(shè)置、數(shù)據(jù)輸入順序等，對實(shí)驗(yàn)結(jié)果進(jìn)行對比分析，對算法進(jìn)行測試、分

13、析。1.3論文組織結(jié)構(gòu)本文共分為五章。第二章系統(tǒng)研究了數(shù)據(jù)挖掘、聚類分析和孤立點(diǎn)檢測理論，給出了一些基本概念描述，重點(diǎn)分析了層次聚類算法和孤立點(diǎn)檢測算法。第三章在系統(tǒng)研究了層次聚類及孤立點(diǎn)檢測算法的基礎(chǔ)上，提出了層次聚類與孤立點(diǎn)檢測算法想結(jié)合的基于層次的孤立點(diǎn)檢測算法，對該算法進(jìn)行了詳細(xì)的描述，并進(jìn)行了算法可行性及性能等分析。第四章綜述基于算法的編程實(shí)現(xiàn)。詳細(xì)介紹了系統(tǒng)設(shè)計流程圖及功能模塊。第五章對以上所做研究及設(shè)計進(jìn)行了總結(jié)，并探討孤立點(diǎn)檢測的將來發(fā)展。第二章 相關(guān)知識2.1數(shù)據(jù)挖掘概述隨著數(shù)據(jù)庫技術(shù)的飛速發(fā)展以及人們獲取數(shù)據(jù)手段的多樣化，人類所擁有的數(shù)據(jù)急劇增加，可是能用于對這些數(shù)據(jù)進(jìn)行分

14、析處理的工具卻很少。目前數(shù)據(jù)庫系統(tǒng)所能做到的只是對數(shù)據(jù)庫中己有的數(shù)據(jù)進(jìn)行存取和簡單的操作，人們通過這些數(shù)據(jù)所獲得的信息量僅僅是整個數(shù)據(jù)庫所包含的信息量的很少一部分，隱藏在這些數(shù)據(jù)之后的更重要的信息、是關(guān)于這些數(shù)據(jù)的整體特征的描述及對其發(fā)展趨勢的預(yù)測，這些信息在決策生成的過程中具有重要的參考價值。這就引起了對強(qiáng)有力的數(shù)據(jù)分析工具的急切需求。面對這種挑戰(zhàn)，數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KDD)技術(shù)逐漸發(fā)展起來。KDD就是從大量、不完全、有噪聲的異質(zhì)模糊數(shù)據(jù)中挖掘隱含的潛在有用知識的過程，它不但能夠?qū)W習(xí)己有的知識，而且又可以發(fā)現(xiàn)未知的規(guī)律。同時，KDD也是一門新興的交叉學(xué)科，匯聚了數(shù)據(jù)庫、人工智能、統(tǒng)計、可視

15、化和并行計算等不同領(lǐng)域的研究人員。一般將KDD中進(jìn)行知識學(xué)習(xí)的階段稱為數(shù)據(jù)挖掘(DataMining)，它是整個數(shù)據(jù)庫中的知識發(fā)現(xiàn)過程中一個非常重要的處理環(huán)節(jié)，所以兩者往往混用。一般而言，在數(shù)據(jù)庫、統(tǒng)計和數(shù)據(jù)分析等工程應(yīng)用領(lǐng)域稱為數(shù)據(jù)挖掘，而在人工智能和機(jī)器學(xué)習(xí)界等研究領(lǐng)域人們則稱之為數(shù)據(jù)庫中的知識發(fā)現(xiàn)。本文將不加區(qū)分地使用兩者。數(shù)據(jù)挖掘概念數(shù)據(jù)挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在的有用信息和知識的過程。簡單的說KDD是指從大量數(shù)據(jù)中提取出可信的、新穎的、有效的、潛在有用的并能被人理解的模式的非平凡

16、處理過程。這種處理過程是一種高級的處理過程。在上述定義中，數(shù)據(jù)是指有關(guān)事實(shí)的集合，記錄和事物有關(guān)的原始信息。模式是一個用語言來表示的一個表達(dá)式，它可用來描述數(shù)據(jù)集的某個子集。我們所說的知識，是對數(shù)據(jù)包涵的信息更抽象的描述。對大量數(shù)據(jù)進(jìn)行分析的過程，包括數(shù)據(jù)準(zhǔn)備、模式搜索、知識評價，以及反復(fù)的修改求精。該過程要求是非平凡的，意思是要有一定程度的智能性、自動性(僅僅給出所有數(shù)據(jù)的總和不能算作是一個發(fā)現(xiàn)過程)。有效性是指發(fā)現(xiàn)的模式對于新的數(shù)據(jù)仍保持有一定的可信度。新穎性要求發(fā)現(xiàn)的模式應(yīng)該是新的。潛在有用性是指發(fā)現(xiàn)的知識將來有實(shí)際效用，如用于決策支持系統(tǒng)里可提高經(jīng)濟(jì)效益。最終可理解性要求發(fā)現(xiàn)的模式能被

17、用戶理解，目前它主要體現(xiàn)在簡潔性上。數(shù)據(jù)挖掘過程數(shù)據(jù)挖掘過程可粗略地分為按需選擇數(shù)據(jù)、數(shù)據(jù)集成、數(shù)據(jù)預(yù)處理、數(shù)據(jù)轉(zhuǎn)換、挖掘過程以及模式評估和知識表示等。(1)數(shù)據(jù)選擇從數(shù)據(jù)源中檢索與分析任務(wù)相關(guān)的數(shù)據(jù)。(2)數(shù)據(jù)集成建立目標(biāo)數(shù)據(jù)集。根據(jù)數(shù)據(jù)挖掘目標(biāo)，從原始數(shù)據(jù)中選擇相關(guān)數(shù)據(jù)集，并將不同數(shù)據(jù)源中的數(shù)據(jù)集成起來，以確定數(shù)據(jù)挖掘的操作對象，需要解決平臺、操作系統(tǒng)和數(shù)據(jù)類型不同產(chǎn)生的數(shù)據(jù)物理格式差異。(3)數(shù)據(jù)預(yù)處理數(shù)據(jù)集中不可避免地存在著不完整、不一致、不精確和重復(fù)的數(shù)據(jù)，這些數(shù)據(jù)統(tǒng)稱為臟數(shù)據(jù)。數(shù)據(jù)抽取之后須利用領(lǐng)域?qū)ｉT知識對臟數(shù)據(jù)進(jìn)行清洗。通常采用基于規(guī)則的方法、神經(jīng)網(wǎng)絡(luò)方法和模糊匹配技術(shù)分析多數(shù)

18、據(jù)源數(shù)據(jù)之間的聯(lián)系，然后再對它們實(shí)施相應(yīng)的處理。(4)數(shù)據(jù)轉(zhuǎn)換根據(jù)分析任務(wù)目標(biāo)，選用關(guān)鍵特征表示數(shù)據(jù)，并將數(shù)據(jù)通過匯總或聚集等操作轉(zhuǎn)換為適于數(shù)據(jù)挖掘處理的形式。(5)挖掘算法使用智能方法提取數(shù)據(jù)模式。這些方法包括概括、分類、回歸和聚類等。(6)模式評估采用有關(guān)方法對數(shù)據(jù)挖掘發(fā)現(xiàn)的模式進(jìn)行評價，根據(jù)某種興趣度度量，識別表示知識的真正興趣的模式。(7)知識表示使用可視化和知識表示技術(shù)，向用戶提供挖掘的知識，幫助用戶理解發(fā)現(xiàn)的模式。數(shù)據(jù)挖掘算法組成數(shù)據(jù)挖掘算法是對某種數(shù)據(jù)挖掘方法的具體實(shí)現(xiàn)，可以看作是一些基本技術(shù)和原理的綜合體。數(shù)據(jù)挖掘算法一般由三個部分組成模型;性能準(zhǔn)則;搜索算法。數(shù)據(jù)挖掘有許多不

19、同的算法。這些算法的區(qū)別在于它們作用的數(shù)據(jù)種類(如文件、事務(wù)數(shù)據(jù)庫、事態(tài)數(shù)據(jù)庫和空間數(shù)據(jù)庫等)和發(fā)現(xiàn)的知識類型(如分類規(guī)則、聚類規(guī)則和序列模式等)各異。按照所發(fā)現(xiàn)知識類型的不同，比較成熟且應(yīng)用廣泛的數(shù)據(jù)挖掘算法主要有:分類規(guī)則挖掘算法、聚類規(guī)則挖掘算法、關(guān)聯(lián)規(guī)則挖掘算法、序列模式挖掘算法。2.2聚類分析將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。在許多應(yīng)用中，一個簇中的數(shù)據(jù)對象可以被作為一個整體來對待。聚類技術(shù)最早在統(tǒng)計學(xué)和人工智能等領(lǐng)域得到廣泛的研究。在統(tǒng)計方法中，聚類

20、是多元數(shù)據(jù)分析的三大方法之一(其它兩種是回歸分析和判別分析)。它主要研究基于幾何距離的聚類，如歐式距離、明考斯基距離等。傳統(tǒng)的統(tǒng)計聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。這種聚類方法是一種基于全局比較的聚類，它需要考察所有的個體才能決定類的劃分。因此它要求所有的數(shù)據(jù)必須預(yù)先給定，而不能動態(tài)增加新的數(shù)據(jù)對象。聚類分析方法不具有線性的計算復(fù)雜度，難以適用于數(shù)據(jù)庫非常大的情況。在人工智能中，聚類又稱作無監(jiān)督歸納（unsupervised induction）。因?yàn)楹头诸悓W(xué)習(xí)相比，分類學(xué)習(xí)的例子或數(shù)據(jù)對象有類別標(biāo)記，而要聚類的例子則沒有標(biāo)記，需要由

21、聚類學(xué)習(xí)算法來自動確定。很多人工智能文獻(xiàn)中，聚類也稱概念聚類(concept clustering)。因?yàn)檫@里的距離不再是統(tǒng)計方法中的幾何距離，而是根據(jù)概念的描述來確定的。當(dāng)聚類對象可以動態(tài)增加時，概念聚類則稱是概念形成(concept formation)。作為一個數(shù)據(jù)挖掘的功能，聚類分析能作為一個獨(dú)立的工具來獲得數(shù)據(jù)分布的情況，觀察每個簇的特點(diǎn)，集中對特定的某些簇作進(jìn)一步的分析。此外，聚類分析可以作為其他算法（如分類等）的預(yù)處理步驟，這些算法再在生成的簇上進(jìn)行處理。數(shù)據(jù)聚類正在蓬勃發(fā)展，有貢獻(xiàn)的研究領(lǐng)域包括數(shù)據(jù)挖掘，統(tǒng)計學(xué)，機(jī)器學(xué)習(xí)，空間數(shù)據(jù)庫技術(shù)，生物學(xué)，以及市場營銷。由于數(shù)據(jù)庫中收集了

22、大量的數(shù)據(jù)，聚類分析已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中一個非常活躍的研究課題。聚類算法簡介目前在文獻(xiàn)中存在大量的聚類算法算法的選擇取決于數(shù)據(jù)的類型聚類的目的和應(yīng)用。大體上，主要的聚類算法可以劃分為如下幾類:(1)劃分方法(partitioning method)給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚類簇，并且k<=n。也就是說，它將數(shù)據(jù)劃分為k個組，同時滿足如下的要求:(i)每個組至少包含一個對象;(ii)每個對象必須屬于且只屬于一個組。注意在某些模糊劃分技術(shù)中，第二個要求可以放寬。給定要構(gòu)建的劃分的數(shù)目k，劃分方法首先創(chuàng)建一個初始劃分。然后采用一種迭

23、代的重定位技術(shù)，嘗試通過對象在劃分間移動來改進(jìn)劃分。一個好的劃分的一般準(zhǔn)則是:在同一個類中的對象之間盡可能“接近”或相關(guān)，而不同類中的對象之間盡可能“遠(yuǎn)離”或不同。還有許多其他劃分質(zhì)量的評判標(biāo)準(zhǔn)。為了達(dá)到全局最優(yōu)，基于劃分的聚類會要求窮舉所有可能的劃分。實(shí)際上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方法:(i)k-平均算法，在該算法中，每個簇用該簇中對象的平均值來表示。(ii)k-中心點(diǎn)算法，在該算法中，每個簇用接近聚類中心的一個對象來表示。這些啟發(fā)式聚類方法，對在中小規(guī)模的數(shù)據(jù)庫中，發(fā)現(xiàn)球狀簇很適用。為了對大規(guī)模的數(shù)據(jù)集進(jìn)行聚類，以及處理復(fù)雜形狀的聚類，基于劃分的方法需要進(jìn)一步的改進(jìn)。(

24、2)層次的方法(hierarchical method)層次的方法對給定的數(shù)據(jù)對象集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。凝聚的方法，也稱為自底向上的方法，一開始將每個對象作為單獨(dú)的一個組，然后相繼合并相近的對象或組，直到所有的組合并為一個(層次的最上層)，或者達(dá)到一個終止條件。分裂的方法，也稱為自頂向下的方法，一開始將所有的對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨(dú)的一個簇中，或者達(dá)到一個終止條件。層次的方法的缺陷在于，一旦一個步驟(合并或分裂)完成，它就不能被撤銷。這個嚴(yán)格規(guī)定是有用的，由于不用擔(dān)心組合數(shù)目的不同

25、選擇，計算代價會較小。但是，該技術(shù)的一個主要問題是它不能更正錯誤的決定。有兩種方法可以改進(jìn)層次聚類的結(jié)果:（i）在每層劃分中，仔細(xì)分析對象間的“聯(lián)接”，例如CURE和Chamelocn中的做法。(ii)綜合層次聚類和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進(jìn)結(jié)果。例如在BIRCH中的方法。(3)基于密度的方法(density一basedmethod)絕大多數(shù)劃分方法基于對象之間的距離進(jìn)行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的另一類聚類方法，其主要思想是:只要臨近區(qū)域的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超出某個閩值，就繼續(xù)聚類。

26、也就是說、對給定類中的每個數(shù)據(jù)點(diǎn)，在一個給定范圍的區(qū)域中必須包含一定數(shù)目的點(diǎn)。這樣的方法可以用來過慮“噪音”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。DBSCAN是一個有代表性的基于密度的方法，它根據(jù)一個密度閉值來控制簇的增長。OTPICS是另一個基于密度的方法，它為自動的和交互的聚類分析提供一個聚類順序。(4) 基于網(wǎng)格的方法(grid-basedmethod)基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)(即量化的空間)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快，其處理時間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。STNIG是基于網(wǎng)格

27、方法的一個典型例子。CLIQUE和waveCluster這兩種算法既是基于網(wǎng)格的，又是基于密度的。(5) 基于模型的方法(model-basedmethod)基于模型的方法為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來定位聚類。它也基于標(biāo)準(zhǔn)的統(tǒng)計數(shù)字自動決定聚類的數(shù)目，考慮“噪音”數(shù)據(jù)或孤立點(diǎn)，從而產(chǎn)生健壯的聚類方法。一些聚類算法集成了多種聚類方法的思想，所以有時將某個給定的算法劃分為屬于某類聚類方法是很困難的。此外，某些應(yīng)用可能有特定的聚類標(biāo)準(zhǔn)，要求綜合多個聚類技術(shù)。下一節(jié)針對本文研究的方向，將詳細(xì)討論上述的基于層次的聚類算

28、法?；趯哟蔚木垲惙椒ɑ趯哟蔚姆椒▽o定的數(shù)據(jù)集進(jìn)行層次分解。根據(jù)層次分解的方式，層次的方法可以分力凝聚的和分裂的兩種類型。凝聚的層次聚類法(也稱為自底向上的方法)，一開始將每個對象作為單獨(dú)的一個簇，然后相繼地合并最相似或相近的對象或簇，得到更大的簇，直到達(dá)到一個終止條件或者所有的對象都在一個簇中(層次的最上層)。這種方法需要對簇的相似性或簇間距離進(jìn)行定義。絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間的相似度或距離的定義上有所不同。分裂的層次聚類法(也稱為自頂向下的方法)，一開始將所有的對象置于一個簇中，在迭代的每一步中，每個簇逐漸被細(xì)分為越來越小的簇，直到最終每個對象在單獨(dú)的一個簇中，或

29、者達(dá)到一個終止條件。用戶可以指定希望得到的簇的數(shù)目作為一個結(jié)束條件，也可以指定一個閏值，當(dāng)兩個最近的簇之間的距離超過了這個閩值時，結(jié)束分裂過程。這種方法要求預(yù)先設(shè)定每一步待分裂簇的選擇依據(jù)以及如何實(shí)施這個分裂。待分裂簇的選擇依據(jù)有很多，例如在每一步的分裂過程中可以選擇最大的簇，可以選擇總體相似性(Overall Similarity)最小的簇，或者使用一種同時基于大小和總體相似性的度量規(guī)則。大量的實(shí)驗(yàn)結(jié)果表明，這些選擇所帶來的效果差異不大，所以通常選擇分裂現(xiàn)存的最大的簇。層次聚類方法使用距離來反映相似度。四個廣泛使用的簇間距離度量方法是：最小距離： 最大距離： 平均值距離：平均距離： 這里是兩

30、個對象之間的距離， 是簇的平均值，是簇中對象的個數(shù)。表2.1四種簇間距離度量方法的比較方法空間性質(zhì)單調(diào)性距離選擇結(jié)果類型適用性備注最短距離法壓縮是條形 S型唯一太壓縮，不夠靈敏最長距離法擴(kuò)張是適用于橢球型距離表中有形同元素時可能出現(xiàn)不唯一的結(jié)果太壓擴(kuò)張，樣本大時易失真平均值距離法守恒否歐氏距離的平方平均距離法守恒否同上不太壓縮也不太擴(kuò)張，效果較好，較常用以上四種方法是主要針對樣品聚類并采用“距離”來衡量樣品間的“靠近”程度的方法。在對變量進(jìn)行聚類時，一般先求出變量間的相似系數(shù)。按照相似系數(shù)越大，兩個變量越相近的原則，根據(jù)分層聚類的思想，聚類過程是完全相似的，也可以先將相似系數(shù)轉(zhuǎn)化為距離，然后再

31、聚類，轉(zhuǎn)化公式為：或者其中c表示兩個變量之間的某種相似系數(shù)。d為它們之間的某種距離。盡管層次的方法比較簡單，但是沒有良好的伸縮性，而且一旦一個合并或分裂被執(zhí)行，就不能被撤消。為了改進(jìn)層次方法的聚類效果，人們嘗試著將層次聚類與其他聚類技術(shù)相結(jié)合，形成多階段的聚類方法，代表性的算法有:BIRCH算法、CURE算法、ROCK算法和CHAMELEON算法。一 BIRCH算法BIRCH是一個綜合的層次聚類方法，它的中文含義是利用層次方法的平衡迭代歸約和聚類。它引人入聚類特征(Clustering feather)和聚類特征樹(CF樹)兩個概念。引入CF樹，可以使大型數(shù)據(jù)庫中的聚類能取得高速度和可伸縮性，

32、可以有效地進(jìn)行增量聚類或動態(tài)聚類。一個聚類特征(CF)是一個三元組，給出對象子聚類的信息的匯總描述。假設(shè)某個子聚類中有N個d維的點(diǎn)或?qū)ο螅瑒t該子聚類的CF定義如下：其中，N是子類中點(diǎn)的數(shù)目，是N個點(diǎn)的線性和，即，SS是數(shù)據(jù)點(diǎn)的平方和即。CF樹不是存儲所有的對象，而是匯總了關(guān)于子聚類的信息，這些信息是計算聚類和有效利用存儲的關(guān)鍵度量。每個葉節(jié)點(diǎn)包含一個或多個子聚類，每個子聚類中包含一個或多個對象。一個CF樹有兩個參數(shù)，即分支因子B和閉值T，這兩個參數(shù)影響了結(jié)果樹的大小。分支因子定義了每個非葉節(jié)點(diǎn)的后代的最大數(shù)目，閉值參數(shù)給出了存儲在葉節(jié)點(diǎn)中的子聚類的最大直徑。BIRCH法的分兩個段：階段一：BI

33、RCH 掃描數(shù)據(jù)庫，建立一個初始存放于內(nèi)存的CF 樹，它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。在這個階段，當(dāng)一個對象被插入到最近的葉節(jié)點(diǎn)(子聚類)中時，如果在插入對象后，存儲在葉節(jié)點(diǎn)中子聚類的直徑大于閡值，那么該葉節(jié)點(diǎn)被分裂，也可能有其他節(jié)點(diǎn)被分裂。新對象插入后，關(guān)于該對象的信息向根節(jié)點(diǎn)傳遞。通過修改閑值，CF樹的大小可以改變;階段二：BIRCH 采用某個聚類算法對CF 樹的葉節(jié)點(diǎn)進(jìn)行聚類。BIRCH算法具有可伸縮性，數(shù)據(jù)集的單遍掃描產(chǎn)生了一個基本的聚類，二次掃描可以進(jìn)一步改進(jìn)聚類質(zhì)量和處理孤立點(diǎn)。同時，該算法的速度快，計算復(fù)雜性只為O(n)。n是數(shù)據(jù)集中對象的個數(shù)。BIRCH

34、的缺點(diǎn)是，對于非球狀的簇不能很好地工作。二 CURE算法絕大多數(shù)聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點(diǎn)時變得比較脆弱。CURE 解決了偏好球形和相似大小的問題，在處理孤立點(diǎn)上也更加健壯。CURE(clustering using representative) 采用了一種新的層次聚類算法，該算法選擇了位于基于質(zhì)心和基于代表對象方法之間的中間策略。它不用單個質(zhì)心或?qū)ο髞泶硪粋€簇，而是選擇了數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)。一個簇的代表點(diǎn)通過如下方式產(chǎn)生：首先選擇簇中分散的對象，然后根據(jù)一個特定的分?jǐn)?shù)或收縮因子向簇中心“收縮”或移動它們。在算法的每一步，有最近距離的代表點(diǎn)對

35、（每個點(diǎn)來自于一個不同的簇）的兩個簇被合并。每個簇有多于一個的代表點(diǎn)使得 CURE 可以適應(yīng)非球形的幾何形狀。簇的收縮或凝聚可以有助于控制孤立點(diǎn)的影響。因此，CURE 對孤立點(diǎn)的處理更加健壯，而且能夠識別非球形和大小變化較大的簇。對于大規(guī)模數(shù)據(jù)庫，它也具有良好的伸縮性，而且沒有犧牲聚類質(zhì)量。針對大數(shù)據(jù)庫，CURE 采用了隨機(jī)取樣和劃分兩種方法的組合：一個隨機(jī)樣本首先被劃分，每個劃分被部分聚類。這些結(jié)果簇然后被聚類產(chǎn)生希望的結(jié)果。下面的步驟描述了 CURE 算法的核心：1從源數(shù)據(jù)對象中抽取一個隨機(jī)樣本S。2將樣本S 劃分為一組分塊。3對每個劃分局部地聚類。4通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個簇增長

36、得太慢，就去掉它。5對局部的簇進(jìn)行聚類。落在每個新形成的簇中的代表點(diǎn)根據(jù)用戶定義的一個收縮因子a 收縮或向簇中心移動。這些點(diǎn)描述和捕捉到了簇的形狀。CURE算法的缺陷是不處理分類屬性。三 ROCKROCK(Robust Clustering Of Links)是一個可選的凝聚層次聚類算法，適用于分類屬性。它引入了一個新穎的概念，即交叉鏈(link)，利用交叉鏈來度量一對數(shù)據(jù)點(diǎn)之間的相似性，并根據(jù)交叉鏈而不是距離來進(jìn)行簇的合并。在ROCK方法中，一個點(diǎn)的近鄰是那些與它很相似的點(diǎn)。記是計量點(diǎn)對和之間接近程度的相似性函數(shù)。該函數(shù)可以是常用的距離公式，也可以是其他形式。相似性函數(shù)可以由領(lǐng)域?qū)＜抑付?。給

37、定一個介于0到1之間的常數(shù)作為閥值，如果，那么就認(rèn)為和是近鄰。是兩個點(diǎn)和共同近鄰的個數(shù)。如果的值比較大，則點(diǎn)和更可能屬于同一個簇。ROCK首先根據(jù)相似度閾值和共同鄰居的概念從給定的數(shù)據(jù)相似度矩陣構(gòu)建一個稀疏的圖，然后在這個稀疏圖上運(yùn)行一個層次聚類算法。四 ChameleonChameleon 是一個在層次聚類中采用動態(tài)模型的聚類算法。在它的聚類過程中，如果兩個簇間的互連性和近似度與簇內(nèi)部對象間的互連性和近似度高度相關(guān)，則合并這兩個簇?；趧討B(tài)模型的合并過程有利于自然的和相似的聚類的發(fā)現(xiàn)，而且只要定義了相似度函數(shù)就可應(yīng)用于所有類型的數(shù)據(jù)。Chameleon 的產(chǎn)生是基于對兩個層次聚類算法CURE

38、 和ROCK 的缺點(diǎn)的觀察。CURE 及其相關(guān)的方案忽略了關(guān)于兩個不同簇中的對象的互連性的信息，而ROCK 及其相關(guān)的方案強(qiáng)調(diào)對象間互連性，卻忽略了關(guān)于對象間近似度的信息。Chameleon 的主要思想是：首先通過一個圖劃分算法將數(shù)據(jù)對象聚類為大量相對較小的子類，然后用一個凝聚的層次聚類算法通過反復(fù)地合并子類來找到真正的結(jié)果簇。它既考慮了互連性，又考慮了簇間的近似度，特別是簇內(nèi)部的特征，來確定最相似的子類。因此它不依賴于一個靜態(tài)的，用戶提供的模型，能夠自動地適應(yīng)被合并的簇的內(nèi)部特征。Chameleon 基于通常采用的k 個最近的鄰居圖方法來描述它的對象。K 個最近的鄰居圖中的每個點(diǎn)代表一個數(shù)據(jù)

39、對象，如果一個對象是另一個對象的k 個最類似的對象之一，在這兩個點(diǎn)（對象）之間存在一條邊。K 個最近鄰居圖動態(tài)地捕捉鄰域的概念：一個對象的領(lǐng)域半徑被對象所在區(qū)域的密度所決定。在一個密集區(qū)域，鄰域的定義范圍相對狹窄；在一個稀疏區(qū)域，它的定義范圍相對較寬。與采用基于密度的全局鄰域方法相比，該方法能產(chǎn)生更自然的聚類結(jié)果。而且，區(qū)域的密度作為邊的權(quán)重被記錄下來。就是說，一個密集區(qū)域的邊趨向于比稀疏區(qū)域的邊有更大的權(quán)重。Chameleon 通過兩個簇的相對互連性RI 和相對近似性RC來決定簇間的相似度：其中是包含的簇分裂為截斷邊，（或）是（或）的最小截斷等分線的大小(即將圖劃分為大致相等的部分需要切斷的

40、邊的加權(quán)和)。其中是連接的頂點(diǎn)的邊的平均權(quán)重。（或）是（或）的最小截斷等分線的邊的平均權(quán)重?？梢钥闯?，Chameleon跟CURE和DBSCAN相比，在發(fā)現(xiàn)高質(zhì)量的任意形狀的聚類方面有高強(qiáng)的能力。但是，在最壞的情況下，高維數(shù)據(jù)的處理代價可能對n個對象需要O（）的時間。2.2.3距離、相似系數(shù)及聚類分析中的數(shù)據(jù)類型我們研究在聚類分析中經(jīng)常出現(xiàn)的數(shù)據(jù)類型，以及如何對其進(jìn)行預(yù)處理。假設(shè)要聚類的數(shù)據(jù)集合包含n 個數(shù)據(jù)對象，這些數(shù)據(jù)對象可能表示人，房子，文檔，國家等。許多基于內(nèi)存的聚類算法選擇如下兩種有代表性的數(shù)據(jù)結(jié)構(gòu)：(1)數(shù)據(jù)矩陣（Data matrix，或稱為對象屬性結(jié)構(gòu)）它用p 個變量（也稱為屬

41、性）來表現(xiàn)n 個對象，例如用年齡，身高，性別，種族等屬性來表現(xiàn)對象“人”。這種數(shù)據(jù)結(jié)構(gòu)是關(guān)系表的形式，或者看為n*p 維（n 個對象*p 個屬性）的矩陣。(2)相異度矩陣（dissimilarity matrix，或稱為對象-對象結(jié)構(gòu)）：存儲n 個對象兩兩之間的近似性，表現(xiàn)形式是一個n*n 維的矩陣。在這里d(i,j)是對象i 和對象j 之間相異性的量化表示，通常它是一個非負(fù)的數(shù)值，當(dāng)對象i 和j 越相似，其值越接近0；兩個對象越不同，其值越大。數(shù)據(jù)矩陣經(jīng)常被稱為二模（two-mode）矩陣，而相異度矩陣被稱為單模（one-mode）矩陣。這是因?yàn)榍罢叩男泻土写聿煌膶?shí)體，而后者的行和列代表

42、相同的實(shí)體。許多聚類算法以相異度矩陣為基礎(chǔ)。如果數(shù)據(jù)是用數(shù)據(jù)矩陣的形式表現(xiàn)的，在使用該類算法之前要將其轉(zhuǎn)化為相異度矩陣。許多聚類算法是以相異度矩陣為基礎(chǔ)的。如果數(shù)據(jù)是以數(shù)據(jù)矩陣的形式給出，可以將數(shù)據(jù)矩陣轉(zhuǎn)化為相異度矩陣。有的聚類算法以相似度矩陣為基礎(chǔ)，而不是相異度矩陣。相似度矩陣通常用距離公式計算得到。一 距離與相似系數(shù)選用的度量單位將直接影響聚類分析的結(jié)果。一般而言，選用的單位越小，變量可能的值域就越大，這樣對聚類結(jié)果的影響就越大。因此為了避免聚類結(jié)果對單位選擇的依賴，數(shù)據(jù)應(yīng)當(dāng)標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化處理后，對象間的相異度是基于距離來計算的。最常用的距離度量方法是歐幾里得距離，它的定義為:其中和是兩個

43、p維的數(shù)據(jù)對象。在使用歐幾里得距離時，要特別注意樣本諸測量值的選取，應(yīng)是有效地反映類別屬性的特征。還有一個就是曼哈頓距離：如果對每個變量根據(jù)其重要性賦予一個權(quán)重，加權(quán)的歐幾里得距離可以計算如下：相似系數(shù)的表示形式常見有以下兩種：1.夾角余弦2相關(guān)系數(shù)三 聚類分析中的數(shù)據(jù)類型(1) 區(qū)間標(biāo)度（Interval-Scaled）變量是一個粗略線性標(biāo)度的連續(xù)變量。典型的例子包括重量和高度，經(jīng)度和緯度坐標(biāo)以及大氣溫度。(2)二元變量（binary variable）一個二元變量只有兩個狀態(tài):O或者1，0表示該變量為空，1表示該變量存在。例如，給出一個描述病人的變量Smoker，l表示病人抽煙，而O表示病

44、人不抽煙。如果二元變量有相同的權(quán)重，則可以得到一個兩行兩列的可能性表2-l，這個表反映了兩個對象的變量取值可能性情況。在表中，q是對象i和對象j值都為1的變量的數(shù)目，r是對象i值為1而對象j為0的變量的數(shù)目，s是對象i值為0而對于對象j為1的變量的數(shù)目，t是對象i和j值都為0的變量的數(shù)目。變量的總數(shù)是， 。如果二元變量的兩個狀態(tài)是同等價值的，并有相同的權(quán)重，則二元變量是對稱的:基于對稱二元變量的相似度稱為恒定的相似度，對恒定的相似度來說，評價兩個對象i和j的相異度的最著名的系數(shù)是簡單匹配系數(shù)，其定義如下:如果二元變量的兩個狀態(tài)的輸出不是同樣重要，那么該二元變量是不對稱的。例如一個疾病檢查的肯定

45、和否定的結(jié)果。根據(jù)慣例我們將比較重要的輸出結(jié)果，通常也是出現(xiàn)幾率比較小的結(jié)果編碼為l，而將另一種結(jié)果編碼為0。給定兩個不對稱的二元變量，兩個都取l的情況被認(rèn)為比兩個都取0的情況更有意義.基于這樣變量的相似度被稱為非恒定的相似度。對非恒定的相似度，最著名的評價系數(shù)是Jaccard系數(shù)，其定義為:(3)標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個的狀態(tài)值。例如color是一個標(biāo)稱變量，它可能有五個狀態(tài):紅色，黃色，綠色，粉紅色和色。假設(shè)一個標(biāo)稱變量的狀態(tài)數(shù)目是M。每一個狀態(tài)值可以用字母、符號或者一整數(shù)來表示，則兩個對象i和j之間的相異度可以用簡單匹配方法來計算：這里m

46、是匹配數(shù)，即i和j之間的相異度可以用簡單匹配方法來計算:這里m是匹配數(shù)，即i和j取值相同的變量的數(shù)目，而p是全部變量的數(shù)目。序數(shù)型變量序數(shù)型變量可以是離散的，也可以是連續(xù)的。在連續(xù)型的序變量中，值的相對順序是必要的，而其實(shí)際的大小則不重要。在相異度的計算需要把每個變量的值域映射到0.0，1.0上，以便每個變量都有相同的權(quán)重。然后可以采用距離的計算方法進(jìn)行相異度的計算。比例標(biāo)度型變量比例標(biāo)度型變量是非線性的標(biāo)度取正的度量值計算時可以采用與處理區(qū)間標(biāo)度變量相同的方法:也可以先進(jìn)行對數(shù)變換，再進(jìn)行計算；也可以借用序數(shù)性變量，采用秩作為區(qū)間標(biāo)度的值來對待。(4)混合類型的變量在許多真實(shí)的數(shù)據(jù)庫中，對象

47、是由混合類型的變量描述的。一般來說，一個數(shù)據(jù)庫可能包含上面列出的全部類型。2.3孤立點(diǎn)分析Hawkins給出了孤立點(diǎn)的本質(zhì)定義:孤立點(diǎn)是在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。聚類算法對孤立點(diǎn)的定義:孤立點(diǎn)是聚類嵌于其中的背景噪聲。孤立點(diǎn)檢測算法則認(rèn)為孤立點(diǎn)是既不屬于聚類也不屬于背景噪聲的點(diǎn)，它們的行為與正常的行為有很大不同。孤立點(diǎn)檢測需要在多維數(shù)據(jù)集中發(fā)現(xiàn)與其它個體不同的對象。孤立點(diǎn)檢測是數(shù)據(jù)挖掘中一個重要方面，在很多應(yīng)用里，例外事件常常比普通的事件更有意義。孤立點(diǎn)檢測大多用于電信和信用卡詐騙檢測、貸款審批、醫(yī)藥研究、天氣預(yù)報、電子貿(mào)易中的犯罪活動檢

48、測，在NBA比賽和NHL（Natial Hockey Legaue)數(shù)據(jù)中，孤立點(diǎn)檢測也有應(yīng)用。在數(shù)據(jù)倉庫領(lǐng)域，孤立點(diǎn)檢測被用來發(fā)現(xiàn)不一致的數(shù)據(jù)，以提高數(shù)據(jù)質(zhì)量。從20世紀(jì)80年代起，孤立點(diǎn)檢測問題就在統(tǒng)計學(xué)領(lǐng)域里得到廣泛研究，通常用戶用某個統(tǒng)計分布對數(shù)據(jù)點(diǎn)進(jìn)行建模，再以假定的模型，根據(jù)點(diǎn)的分布來確定是否為孤立點(diǎn)。這些方法的最大缺陷是:在許多情況下，用戶并不知道數(shù)據(jù)集的分布。而且現(xiàn)實(shí)數(shù)據(jù)也往往不符合任何一種理想狀態(tài)的數(shù)學(xué)分布。Aggrawal和Ragaran在1996年提出過“序列孤立點(diǎn)”的概念。他們采用這樣一個機(jī)制:掃描數(shù)據(jù)集并觀測一系列相似數(shù)據(jù)，當(dāng)發(fā)現(xiàn)一個數(shù)據(jù)點(diǎn)明顯不同于前面的序列，這樣的

49、點(diǎn)就被認(rèn)為是孤立點(diǎn)。這個算法復(fù)雜度與數(shù)據(jù)集大小呈線性關(guān)系，有優(yōu)異的計算性能。但是序列孤立點(diǎn)對孤立點(diǎn)存在的情況的假設(shè)太理想化，對現(xiàn)實(shí)復(fù)雜數(shù)據(jù)效果不太好。Knorr和Ng在1998年提出了基于距離的孤立點(diǎn)檢測算法。Rastogi和Ramaswamy改進(jìn)了他們的孤立點(diǎn)定義。在聚類算法研究中，如DBSCAN，BRICH都具有一定的噪聲處理能力。但是聚類中的噪聲和孤立點(diǎn)在概念上還是有些偏差的。噪聲是定義在聚類基礎(chǔ)之上，即噪聲是不隸屬于任何聚類的數(shù)據(jù);而孤立點(diǎn)的定義不依賴于是否存在聚類。而且上面的算法的最終目標(biāo)是優(yōu)化聚類查找，而不是孤立點(diǎn)檢測。當(dāng)然一般而言，假設(shè)聚類存在的話(低維數(shù)據(jù)集往往更容易定義聚類)

50、，噪聲和孤立點(diǎn)在概念上還是有很多重疊處的。Breunig和Kriegel作了將基于密度的聚類算法OPTICS與孤立點(diǎn)檢測合并到一起的研究。在此基礎(chǔ)上，Bruenig和Kriegel提出了局部孤立因子的概念。Aggaarwal和Yu提出了一個針對高維數(shù)據(jù)集進(jìn)行降維的孤立點(diǎn)檢測的新思路，利用遺傳算法優(yōu)化其性能。本節(jié)著重介紹基于距離的孤立點(diǎn)檢測算法孤立點(diǎn)檢測算法。基于統(tǒng)計的方法基于統(tǒng)計的方法使用著名的標(biāo)準(zhǔn)統(tǒng)計分布(即正態(tài)分布，帕松等)來擬合數(shù)據(jù)點(diǎn)。孤立點(diǎn)是在數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)的偏離并非由隨機(jī)因數(shù)產(chǎn)生，而是產(chǎn)生于完全不同的統(tǒng)計分布。不一致檢驗(yàn)是為了在不同條件下挖掘孤立點(diǎn)而設(shè)

51、計的統(tǒng)計檢驗(yàn)?；诰嚯x的孤立點(diǎn)檢測算法基于距離的方法是通過數(shù)據(jù)點(diǎn)或?qū)ο笾g的距離來檢測孤立點(diǎn)的。如果數(shù)據(jù)集合X中對象至少有p部分與對象O的距離大于d，則對象O是一個帶參數(shù)p和d的基于距離的孤立點(diǎn)，即DB（p,d）-Outlier。對于每個實(shí)體O，O的d鄰域是一個包含所有在O的d距離以內(nèi)的實(shí)體的集合。例如。分?jǐn)?shù)p是一個孤立點(diǎn)的d鄰域之外的實(shí)體的最小比例。為了討論簡單，假設(shè)M為一個孤立點(diǎn)的d鄰域中實(shí)體的最大個數(shù)(顯然，M=N（1-p）)。根據(jù)上面的公式，對于給定的p和d，找出孤立點(diǎn)的關(guān)鍵在于解決對每個以O(shè)為中心的d鄰域的搜索，只要在O的d鄰域中發(fā)現(xiàn)了（M+1）個實(shí)體，就可以停止搜索并且宣布O不是孤

52、立點(diǎn)。否則，就認(rèn)為O是一個孤立點(diǎn)?；诰嚯x的孤立點(diǎn)檢測算法設(shè)計了三種算法:基于索引的算法、嵌套循環(huán)算法及基于單元的算法，1.基于索引的距離算法該算法的主要思想是將數(shù)據(jù)實(shí)體存儲在索引樹中，判斷一個對象是否是一個孤立點(diǎn)只需查詢d-鄰域內(nèi)是否包含M個對象，如果是則該對象不是孤立點(diǎn)，否則該對象是孤立點(diǎn)。對于多維索引模式的分析說明，對于R*樹的變種，k-d樹，X樹，一個范圍查詢的復(fù)雜度下限是。當(dāng)維數(shù)(或?qū)傩? k增加時，范圍查詢迅速變?yōu)?。N是數(shù)據(jù)實(shí)體的個數(shù)。然而使用上面的方法查詢DB（p,d）-Outlier的過程最壞的復(fù)雜度情況是。2.嵌套循環(huán)算法(NL算法)為了避免查詢DB（p,d）-Outlier

53、中建立索引的花費(fèi)，NL算法使用了一種基于塊和循環(huán)的設(shè)計。假設(shè)有一個b%數(shù)據(jù)集大小的緩存，算法就將緩存劃分為相等兩個部分，稱為第一和第二數(shù)組。它把數(shù)據(jù)集讀入數(shù)組，直接計算每個實(shí)體對的距離。對于每個在第一個數(shù)組內(nèi)的實(shí)體，它的d鄰域被記錄下來，當(dāng)實(shí)體的d鄰域中點(diǎn)的個數(shù)超過M時，則證明該點(diǎn)不是孤立點(diǎn)，這時停止計數(shù)，跳出現(xiàn)在的循環(huán)，比較下一個點(diǎn)。假設(shè)NL算法有50%的緩存，并用A，B，C，D來代表4個邏輯塊，每個塊記錄了數(shù)據(jù)集1/4的實(shí)體。以下面的順序來填充每個數(shù)組，并比較:(1)A和A，然后和B，C，D-總共有四個塊被讀；(2)D和D(不需要讀)，然后和A(不用讀)，B,C有兩塊被讀；(3)C和C(不

54、需要讀)，然后和D(不用讀)，A，B總共有兩塊被讀；(4)B和B(不需要讀)，然后和C(不用讀)，A，D總共有兩塊被讀。共有十塊被讀，相當(dāng)于10/4次掃描數(shù)據(jù)集。和索引算法相比，NL算法避免了建立索引結(jié)構(gòu)的花費(fèi)。很容易看出它的復(fù)雜度是，k是數(shù)據(jù)維數(shù)(或?qū)傩詡€數(shù))。與不考慮1/0效率的一個實(shí)體對一個實(shí)體的強(qiáng)制算法相比，NL算法有優(yōu)勢，因?yàn)樗鼫p少了讀的次數(shù)。3.基于單元的算法:與前兩種方法相比，基于單元的算法的計算復(fù)雜度較小。該方注把k維數(shù)據(jù)空間劃分為邊長為的單元，每個單元有兩層圍繞著，第一層的厚度為一個單元，第二層的厚度為。該方法統(tǒng)計單元中對象的數(shù)目、單元與第一層中對象的數(shù)目之和、單元與兩個層次

55、中對象的數(shù)目之和等三個統(tǒng)計數(shù)據(jù)。我們把他們分別記為c_count、c_1_count、c_2_count.設(shè)M是一個孤立點(diǎn)的d-鄰域內(nèi)允許包含的點(diǎn)最大數(shù)目。某個單元中的對象。被認(rèn)為孤立點(diǎn)的充要條件是c_count小于等于M。如果某個單元中c_1_count大于M，那么，該單元中的所有點(diǎn)都不是孤立點(diǎn)。如果某個單元中c_2_count小于等于M，那么，該單元中的所有點(diǎn)都是孤立點(diǎn)。如果某個單元中c_2_count大于M，那么，該單元中可能存在孤立點(diǎn)，為了尋找這些孤立點(diǎn)，需要對每個對象逐個進(jìn)行處理?；诰嚯x的孤立點(diǎn)探測要求用戶設(shè)置參數(shù)p和d，而尋找這些參數(shù)的合適設(shè)置可能會涉及多次試探和錯誤?；谄x的

56、孤立點(diǎn)探測通過檢查一組對象的主要特征來確定孤立點(diǎn)，如果一個對象與給出的描述發(fā)生“偏離”，則認(rèn)為對象是孤立點(diǎn)。序列異常技術(shù)和OALP數(shù)據(jù)立方體方法是兩種基于偏離的孤立點(diǎn)檢測方法。序列異常技術(shù)模仿了人類從一系列推測類似的對象中識別異常對象的方式，OALP數(shù)據(jù)立方體方法在大型多維數(shù)據(jù)中使用數(shù)據(jù)立方體來確定反常區(qū)域。2.4本章小結(jié)本章對數(shù)據(jù)挖掘技術(shù)，聚類以及孤立點(diǎn)檢測算法進(jìn)行了系統(tǒng)的闡述。首先，介紹了數(shù)據(jù)挖掘的發(fā)展，數(shù)據(jù)挖掘的嚴(yán)格定義，數(shù)據(jù)挖掘的過程。然后，對聚類分析中的數(shù)據(jù)類型、聚類算法、孤立點(diǎn)檢測算法進(jìn)行了詳細(xì)闡述，并對己有算法進(jìn)行了分析。在此基礎(chǔ)上，下一章將提出基于層次聚類的孤立點(diǎn)檢測算法。第三章 算法設(shè)計與實(shí)現(xiàn)本章在分析了聚類算法和孤立點(diǎn)檢測方法的基礎(chǔ)上，將聚類過程與孤立點(diǎn)檢測結(jié)合起來，提出了基于層次的孤立點(diǎn)檢測算法。3.1算法相關(guān)定義設(shè)待檢測數(shù)據(jù)集數(shù)據(jù)元素的模式