基于網(wǎng)格的聚類分析在數(shù)據(jù)挖掘中的應(yīng)用

1、分類號 TP311 單位代碼 10642 密 級 公開 學(xué) 號2 重慶文理學(xué)院學(xué)士學(xué)位論文    基于網(wǎng)格的聚類分析在數(shù)據(jù)挖掘中的應(yīng)用    論文作者：張雷指導(dǎo)教師：申元霞學(xué)科專業(yè)：信息與計(jì)算科學(xué)研究方向：數(shù)據(jù)挖掘提交論文日期： 2008年 4 月 28 日 論文答辯日期： 2008年 5 月 10 日 學(xué)位授予單位：重慶文理學(xué)院     中 國 · 重 慶2008年4月18 / 22文檔可自由編輯打印目 錄 中文摘要IAbstractII1 引言11.1 研究的目的及意義11.2 國內(nèi)外研究現(xiàn)狀22 數(shù)據(jù)挖掘和聚類分析32

2、.1 數(shù)據(jù)挖掘概述32.1.1 數(shù)據(jù)挖掘的定義32.1.2 數(shù)據(jù)挖掘的過程32.2 聚類分析概述52.2.1 主要聚類算法分類52.2.2 基于網(wǎng)格的聚類算法62.2.3 K-means算法73 基于相似度的網(wǎng)格聚類算法93.1 網(wǎng)格與相似度的概念93.1.1 網(wǎng)格的基本概念93.1.2 相似度93.2 SGCA算法描述103.2.1 邊界點(diǎn)閾值函數(shù)103.2.2 SGCA聚類算法103.3 實(shí)驗(yàn)結(jié)果與分析124 結(jié)論15致謝16參考文獻(xiàn)17基于網(wǎng)格的聚類分析在數(shù)據(jù)挖掘中的應(yīng)用信息與計(jì)算科學(xué)專業(yè)一班 張雷 指導(dǎo)教師 申元霞摘要：數(shù)據(jù)挖掘是近些年來發(fā)展起來的新技術(shù)，通過數(shù)據(jù)挖掘，人們可以發(fā)現(xiàn)數(shù)據(jù)

3、背后隱藏的有價(jià)值的、潛在的知識，為科學(xué)地進(jìn)行各種商業(yè)決策提供強(qiáng)有力的支持。隨著數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展，作為其重要的組成部分，網(wǎng)格聚類技術(shù)己經(jīng)被廣泛的應(yīng)用于數(shù)據(jù)分析、圖象處理、市場研究等許多領(lǐng)域?；诰W(wǎng)格的聚類算法研究己經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中非?；钴S的一個(gè)研究課題。本文首先介紹了數(shù)據(jù)挖掘研究的相關(guān)背景及其理論知識，對數(shù)據(jù)挖掘中的聚類分析的相關(guān)工作做了一個(gè)簡要的概述。在研究了K-means聚類算法的基礎(chǔ)上，針對對象間的相似性度量方法，研究了基于相似度的網(wǎng)格聚類算法，根據(jù)定義的邊界點(diǎn)閾值函數(shù)提取類的邊界點(diǎn)，顯著地提高了網(wǎng)格聚類的精度。 關(guān)鍵詞：數(shù)據(jù)挖掘；網(wǎng)格；聚類；相似度；閾值函數(shù)Research

4、 on grid clustering algorithms and application in the data mining Major: Information and Science Computing Class: OneAuthor: Zhang Lei Supervisor: Shen Yuanxia Abstract：Data mining techniques is the new technique that develops in recent years, which can be used to find out potential and useful knowl

5、edge from the vast amount of data, and it provides the powerful support to carry on various business decidiondecision in science ground. With the rapid development of the data mining techniques, the technique of grid clustering, as important parts of data mining, are widely applied to the fields suc

6、h as pattern recognition, data analysis, image processing, and market research. Research on grid clustering algorithms has become a highly active topic in the data mining research.Firstly, the related background of data mining and its theories knowledge are introduced. Then the related work of clust

7、ering analysis are briefly summarized. Based on the K-means algorithms, a similarity-based grid clustering algorithm is studied. In this algorithm, the threshold function disposes of border points of clusters, which enhances remarkably the precision of grid clustering.Keywords：Data Mining；gGrid；;clu

8、steringClustering；similaritySimilarity；threshold Threshold function1 引言 1.1 研究的目的及意義隨著數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們積累的數(shù)據(jù)越來越多。如何從激增的數(shù)據(jù)背后找到有價(jià)值的信息，并從中提取出知識內(nèi)容己經(jīng)成為目前數(shù)據(jù)挖掘和知識管理等研究領(lǐng)域的重要課題。而數(shù)據(jù)挖掘技術(shù)正是解決這一課題的重要方法。權(quán)威的調(diào)查報(bào)告顯示，數(shù)據(jù)挖掘?qū)⑹墙窈髱啄耆蚍秶鷥?nèi)重點(diǎn)投資研究的十大新技術(shù)之一，它引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，是當(dāng)今數(shù)據(jù)庫系統(tǒng)研究和應(yīng)用領(lǐng)域內(nèi)的一個(gè)熱點(diǎn)問題。聚類是數(shù)據(jù)挖掘中的重要組成部分，所謂聚類

9、就是將數(shù)據(jù)對象分組成為多個(gè)類或簇，在同一個(gè)簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大1。相似度是根據(jù)描述對象的屬性來計(jì)算的。距離是經(jīng)常采用的度量方式。從機(jī)器學(xué)習(xí)的角度看，聚類屬于無指導(dǎo)學(xué)習(xí)，和分類不同，它依賴預(yù)先定義的類和類標(biāo)號的訓(xùn)練實(shí)例。聚類分析具有廣泛的應(yīng)用價(jià)值，如市場分割、模式識別、生物學(xué)研究、空間數(shù)據(jù)分析、Web文檔分類。除此之外，聚類分析還可以作為獨(dú)立的數(shù)據(jù)挖掘工具，來了解數(shù)據(jù)發(fā)布，或者作為其他數(shù)據(jù)挖掘算法的預(yù)處理步驟。聚類已經(jīng)被廣泛地研究了許多年，迄今為止，研究人員已經(jīng)提出了許多聚類算法，大體上這些算法可以分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的

10、方法和基于模型的方法。網(wǎng)格技術(shù)是一項(xiàng)新興的技術(shù)，正處于不斷發(fā)展和變化當(dāng)中。基于網(wǎng)格的聚類方法利用多維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將空間劃分為有限數(shù)目的單元，以構(gòu)成一個(gè)可以進(jìn)行網(wǎng)格聚類分析的網(wǎng)格結(jié)構(gòu)。在網(wǎng)格單元中，同一單元中的點(diǎn)屬于同一類的可能性比較大，所以落入同一網(wǎng)格中的點(diǎn)可被看作一個(gè)對象進(jìn)行處理，以后所有的聚類操作都是在網(wǎng)格單元上進(jìn)行。網(wǎng)格聚類算法可以適用于比較分散、并不密集的空間多維數(shù)據(jù)的挖掘，彌補(bǔ)了基于密度的聚類算法的缺陷；不必事先假設(shè)類的個(gè)數(shù)，類的個(gè)數(shù)由算法自動(dòng)生成，彌補(bǔ)了K-平均值和K-代表點(diǎn)聚類算法的缺陷；不必事先隨機(jī)選取初始點(diǎn)，由算法自動(dòng)選取距離最遠(yuǎn)的非異點(diǎn)數(shù)據(jù)為初始點(diǎn)，從而避免了因初始點(diǎn)選擇

11、不當(dāng)而導(dǎo)致局部最優(yōu)解的錯(cuò)誤；通過網(wǎng)格合并而生成的區(qū)域表可以方便地給出聚類結(jié)果的現(xiàn)實(shí)意義描述；可以方便而有效地發(fā)現(xiàn)異常點(diǎn)；由于網(wǎng)格聚類算法采用了網(wǎng)格技術(shù)，所以算法的處理時(shí)間與數(shù)據(jù)對象的數(shù)目只呈一次線性關(guān)系，而主要由網(wǎng)格的劃分及數(shù)據(jù)的空間分布情況決定。當(dāng)對挖掘?qū)ο筮M(jìn)行網(wǎng)格劃分時(shí)每維上的劃分區(qū)間數(shù)越少，聚類效率越高。如果數(shù)據(jù)的空間分布越集中，則實(shí)際所占的網(wǎng)格數(shù)越少，則聚類效率越高。所以，對網(wǎng)格聚類算法的研究將具有廣闊的發(fā)展空間，今后將會在更多的領(lǐng)域中發(fā)揮作用。 1.2 國內(nèi)外研究現(xiàn)狀 1989年8月在美國底特律召開的第11屆國際人工智能聯(lián)合會議的專題討論會上首次出現(xiàn)KDD（Knowledge Dis

12、cover Database）這個(gè)術(shù)語15。隨后在1991年、1993年和1994年都舉行過KDD專題討論會，匯集來自各個(gè)領(lǐng)域的研究人員和應(yīng)用開發(fā)者，集中討論數(shù)據(jù)統(tǒng)計(jì)、海量數(shù)據(jù)分析算法、知識表示、知識運(yùn)用等問題。隨著參與人員的不斷增多，KDD國際會議逐漸發(fā)展成為年會1。數(shù)據(jù)庫、人工智能、信息處理、知識工程等領(lǐng)域的國際刊物也紛紛開辟了KDD專題或?qū)？?，包括IEEE知識與數(shù)據(jù)工程匯刊（TKDE），ACM數(shù)據(jù)庫系統(tǒng)匯刊（TODS），ACM雜志（JACM），信息系統(tǒng)2等，其中，IEEE16的KnowledgeandDataEngineering匯刊領(lǐng)先在1993年出版了KDD技術(shù)專刊，所發(fā)表的5篇論文

13、代表了當(dāng)時(shí)KDD研究的最新成果和動(dòng)態(tài)，較全面地論述了KDD系統(tǒng)方法論、發(fā)現(xiàn)結(jié)果的評價(jià)、KDD系統(tǒng)設(shè)計(jì)的邏輯方法，討論了鑒于數(shù)據(jù)庫的動(dòng)態(tài)性冗余、高噪聲和不確定性、KDD系統(tǒng)與其他傳統(tǒng)的機(jī)器學(xué)習(xí)、專家系統(tǒng)、人工神經(jīng)網(wǎng)絡(luò)、數(shù)理統(tǒng)計(jì)分析系統(tǒng)的聯(lián)系和區(qū)別，以及相應(yīng)的基本對策。與國外相比，國內(nèi)對DMKD（Data mining and knowledge discovery）的研究稍晚，沒有形成整體力量。許多單位也已開始進(jìn)行數(shù)據(jù)挖掘技術(shù)的研究。1993年國家自然科學(xué)基金首次支持對該領(lǐng)域的研究項(xiàng)目。目前，國內(nèi)的許多科研單位和高等院校竟相開展知識發(fā)現(xiàn)的基礎(chǔ)理論及其應(yīng)用研究。其中，北京系統(tǒng)工程研究所對模糊方法在

14、知識發(fā)現(xiàn)中的應(yīng)用進(jìn)行了較深入的研究，北京大學(xué)也在開展對數(shù)據(jù)立方體代數(shù)的研究，四川大學(xué)和上海交通大學(xué)等單位探討、研究了非結(jié)構(gòu)化數(shù)據(jù)的知識發(fā)現(xiàn)以及Web數(shù)據(jù)挖掘。國內(nèi)也開始有關(guān)于蟻群算法的公開報(bào)道和研究成果。基于網(wǎng)格的聚類算法是一種重要的聚類算法。與其他算法相比，基于網(wǎng)格的聚類算法可以高效處理低維的海量數(shù)據(jù)?；诰W(wǎng)格的方法對數(shù)據(jù)集所分布的空間進(jìn)行劃分，生成一系列單元的集合，即一個(gè)網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)格上進(jìn)行。該類聚類算法的處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目，僅與單元的數(shù)目及網(wǎng)格結(jié)構(gòu)有關(guān)5。然而，由于網(wǎng)格的劃分使得一些數(shù)據(jù)對象成為類的邊界點(diǎn)，傳統(tǒng)的網(wǎng)格聚類算法將其視為孤立點(diǎn)或者噪聲數(shù)據(jù)將其丟棄，

15、這樣做顯然降低了聚類的質(zhì)量。因此在這方面還有很大的研究空間。2 數(shù)據(jù)挖掘和聚類分析2.1 數(shù)據(jù)挖掘概述隨著數(shù)據(jù)庫技術(shù)的飛速發(fā)展以及人們獲取數(shù)據(jù)手段的多樣化，人類所擁有的數(shù)據(jù)急劇增加，可是用于對這些數(shù)據(jù)進(jìn)行分析處理的工具卻很少。目前數(shù)據(jù)庫系統(tǒng)所能做到的只是對數(shù)據(jù)庫中己有的數(shù)據(jù)進(jìn)行存取和簡單的操作，人們通過這些數(shù)據(jù)所獲得的信息量僅僅是整個(gè)數(shù)據(jù)庫所包含的信息量的很少的一部分，隱藏在這些數(shù)據(jù)之后的更重要的信息是關(guān)于這些數(shù)據(jù)的整體特征的描述及對其發(fā)展趨勢的預(yù)測，這些信息在決策生成的過程中具有重要的參考價(jià)值。這就引起了對強(qiáng)有力的數(shù)據(jù)分析工具的急切需求。快速增長的海量數(shù)據(jù)收集、存放在大型和大量數(shù)據(jù)庫中，沒有

16、強(qiáng)有力的工具，理解它們己經(jīng)遠(yuǎn)遠(yuǎn)超出了人的能力。面對這種挑戰(zhàn)，數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discover Database,KDD）技術(shù)逐漸發(fā)展起來。KDD就是從大量、不完全、有噪聲的異質(zhì)模糊數(shù)據(jù)中挖掘隱含的潛在有用知識的過程，它不但能夠?qū)W習(xí)已有的知識，而且又可以發(fā)現(xiàn)未知的規(guī)律3。同時(shí)，KDD也是一門新興的交叉學(xué)科，匯聚了數(shù)據(jù)庫、人工智能、統(tǒng)計(jì)、可視化和并行計(jì)算等不同領(lǐng)域的研究人員。一般將KDD中進(jìn)行知識學(xué)習(xí)的階段稱為數(shù)據(jù)挖掘，它是整個(gè)數(shù)據(jù)庫中的知識發(fā)現(xiàn)過程中一個(gè)非常重要的處理環(huán)節(jié)，所以兩者往往混用。一般而言，在數(shù)據(jù)庫、統(tǒng)計(jì)和數(shù)據(jù)分析等工程應(yīng)用領(lǐng)域稱為數(shù)據(jù)挖掘，而在人工智能和機(jī)器學(xué)

17、習(xí)界等研究領(lǐng)域人們則稱之為數(shù)據(jù)庫中的知識發(fā)現(xiàn)。2.1.1 數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是指從大量無序的數(shù)據(jù)中提取隱含的、有效的、可理解的、對決策有潛在價(jià)值的知識和規(guī)則，為用戶提供問題求解層次的決策支持能力3。這個(gè)定義包括以下四個(gè)層次的含義：(1)數(shù)據(jù)源必須是真實(shí)的、大量的、含噪聲的；(2)發(fā)現(xiàn)的是用戶感興趣的知識；(3)發(fā)現(xiàn)的知識要可接受、可理解、可運(yùn)用，最好能用自然語言表達(dá)發(fā)現(xiàn)結(jié)果；(4)并不是要求發(fā)現(xiàn)放之四海皆準(zhǔn)的知識，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機(jī)器定理證明，所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件、面向特定領(lǐng)域的。2.1.2 數(shù)據(jù)挖掘的過程數(shù)據(jù)挖掘是一個(gè)完

18、整的過程，該過程從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中挖掘先前未知的、有效的、可實(shí)用的信息，并使用這些信息做出決策或豐富知識。在實(shí)施數(shù)據(jù)挖掘之前，先決定采取什么樣的步驟，每一步都做什么，達(dá)到什么樣的目標(biāo)是必要的，有了好的計(jì)劃才能保證數(shù)據(jù)挖掘有條不紊的實(shí)施并取得成功。一般地，數(shù)據(jù)挖掘在任何一個(gè)問題上的應(yīng)用，都可以大致分為三個(gè)階段：第一階段 數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備是數(shù)據(jù)挖掘中的一個(gè)重要步驟，數(shù)據(jù)準(zhǔn)備是否作好將直接影響到數(shù)據(jù)挖掘的效率、準(zhǔn)確率以及最終模式的有效性。這個(gè)階段又可以進(jìn)一步分成三個(gè)子步驟：數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)預(yù)處理。(1)數(shù)據(jù)集成7數(shù)據(jù)集成是將多文件或者多數(shù)據(jù)庫運(yùn)行環(huán)境中的數(shù)據(jù)進(jìn)行合并處理，解決語意模糊性

19、、處理數(shù)據(jù)中的遺漏和清洗臟數(shù)據(jù)等。(2)數(shù)據(jù)選擇 數(shù)據(jù)選擇的目的是辨別出需要分析的數(shù)據(jù)集合，縮小處理范圍，提高數(shù)據(jù)采掘的質(zhì)量。(3)數(shù)據(jù)預(yù)處理 該階段的目的是將數(shù)據(jù)轉(zhuǎn)換成適合于數(shù)據(jù)挖掘的形式，并進(jìn)行一些必要的數(shù)據(jù)約簡。如果數(shù)據(jù)挖掘?qū)ο笫菙?shù)據(jù)倉庫，那么上述這些工作往往在生成數(shù)據(jù)倉庫時(shí)準(zhǔn)備妥當(dāng)。第二階段 數(shù)據(jù)挖掘借助各種數(shù)據(jù)挖掘工具，從數(shù)據(jù)庫中找出有可能解決問題的知識。包括：(1)確定挖掘的任務(wù)或目的，是屬于數(shù)據(jù)總結(jié)、分類、聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)或序列模式發(fā)現(xiàn)中的哪一種。(2)選擇合適的挖掘技術(shù)。在確定挖掘任務(wù)的基礎(chǔ)上，選擇適當(dāng)?shù)臄?shù)據(jù)挖掘技術(shù)。如分類模型常由有指導(dǎo)的神經(jīng)元網(wǎng)絡(luò)或歸納技術(shù)如決策樹來實(shí)現(xiàn)；

20、聚類常用聚類分析技術(shù)；關(guān)聯(lián)分析使用關(guān)聯(lián)發(fā)現(xiàn)和序列發(fā)現(xiàn)技術(shù)等。(3)選擇挖掘算法。挖掘算法的選擇是一個(gè)核心的步驟，一般不會存在一個(gè)普遍適用的數(shù)據(jù)挖掘算法，一個(gè)算法在一個(gè)領(lǐng)域非常有效，但在另一個(gè)領(lǐng)域卻可能不太適合所以，在面對一個(gè)實(shí)際的領(lǐng)域，如何從眾多的數(shù)據(jù)挖掘算法中精選有效的算法就自然成為研究與開發(fā)任務(wù)首先要解決的一個(gè)核心問題。選擇挖掘算法主要考慮兩個(gè)因素：一是不同的數(shù)據(jù)有不同的特點(diǎn)，因此需要用與之相關(guān)的算法來挖掘；二是用戶或?qū)嶋H運(yùn)行系統(tǒng)的要求，有的用戶可能希望獲取描述型的、容易理解的知識，而有的用戶或系統(tǒng)的目的是獲取預(yù)測準(zhǔn)確度盡可能高的預(yù)測型知識。(4)挖掘數(shù)據(jù)。用選定的算法或算法組合在模式空間

21、中進(jìn)行反復(fù)迭代的搜索，從數(shù)據(jù)集合中抽取出隱藏的、新穎的模式。第三階段 結(jié)果表述和解釋根據(jù)最終用戶的決策目的對提取的信息進(jìn)行分析，把最有價(jià)值的信息區(qū)分出來，并且通過決策支持工具提交給決策者。因此，這一步驟的任務(wù)不僅是把結(jié)果表達(dá)出來，還要對信息進(jìn)行過濾處理。如果不能令決策者滿意，需要重復(fù)以上數(shù)據(jù)挖掘過程。2.2 聚類分析概述聚類分析是數(shù)據(jù)挖掘中一種非常重要的技術(shù)和方法，是數(shù)據(jù)挖掘的主要任務(wù)之一。聚類是把一組個(gè)體按照相似性劃分成若干個(gè)類別，跟平常說的“物以類聚”相似。聚類分析就是使用聚類算法來發(fā)現(xiàn)有意義的類，主要依據(jù)是把相似的樣本劃分為一類，而把差異大的樣本區(qū)分開來，這樣所生成的簇是一組數(shù)據(jù)對象的集

22、合，這些對象與同一簇中的對象彼此相似，而與其他簇的對象彼此相異。在應(yīng)用中經(jīng)常把一個(gè)簇中的數(shù)據(jù)對象當(dāng)成一個(gè)整體來對待。定義2.1 簇：一個(gè)數(shù)據(jù)對象的集合。任何一簇內(nèi)，對象具有相似性，不同簇中，對象是相異的3。定義2.2 聚類分析：把一個(gè)給定的數(shù)據(jù)對象集合分成不同的組，并使組與組之間的相似性最小，而組內(nèi)的相似性盡可能的大8。2.2.1 主要聚類算法分類作為統(tǒng)計(jì)學(xué)的重要研究內(nèi)容，人們構(gòu)造了一系列聚類分析算法，通常聚類分析算法可以劃分為以下幾大類：(1)劃分的方法給定一個(gè)n個(gè)對象或元組的數(shù)據(jù)庫，一個(gè)劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)聚類簇，并且kn9。也就是說，它將數(shù)據(jù)劃分為k個(gè)組，同時(shí)滿足

23、如下的要求:每個(gè)組至少包含一個(gè)對象；每個(gè)對象必須屬于且只屬于一個(gè)組。注意在某些模糊劃分技術(shù)中，第二個(gè)要求可以放寬。給定要構(gòu)建的劃分的數(shù)目k，劃分方法首先創(chuàng)建一個(gè)初始劃分。然后采用一種迭代的重定位技術(shù)，嘗試通過對象在劃分間移動(dòng)來改進(jìn)劃分。一個(gè)好的劃分的一般準(zhǔn)則是：在同一個(gè)類中的對象之間盡可能“接近”或相關(guān)，而不同類中的對象之間盡可能“遠(yuǎn)離”或不同。還有許多其他劃分質(zhì)量的評判標(biāo)準(zhǔn)。(2)層次的方法 層次的方法對給定的數(shù)據(jù)對象集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。凝聚的方法10，也稱為自底向上的方法，一開始將每個(gè)對象作為單獨(dú)的一個(gè)組，然后相繼合并相近的對象或組

24、，直到所有的組合并為一個(gè)(層次的最上層)，或者達(dá)到一個(gè)終止條件。分裂的方法，也稱為自頂向下的方法，一開始將所有的對象置于一個(gè)簇中。在迭代的每一步中，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對象在單獨(dú)的一個(gè)簇中，或者達(dá)到一個(gè)終止條件。層次方法的缺陷在于，一旦一個(gè)步驟合并或分裂完成，它就不能被撤銷。這個(gè)嚴(yán)格規(guī)定是有用的，由于不用擔(dān)心組合數(shù)目的不同選擇，計(jì)算代價(jià)會較小。但是，該技術(shù)的一個(gè)主要問題是它不能更正錯(cuò)誤的決定。(3)基于密度的方法絕大多數(shù)劃分方法基于對象之間的距離進(jìn)行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的另一類聚類方法，其主要思想是：只要臨近區(qū)域

25、的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超出某個(gè)閾值，就繼續(xù)聚類。也就是說，對給定類中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須包含一定數(shù)目的點(diǎn)。這樣的方法可以用來過慮“噪音”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。(4)基于網(wǎng)格的方法基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個(gè)網(wǎng)格結(jié)構(gòu)(即量化的空間)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。(5)基于模型的方法基于模型的方法為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對給定模型的最佳擬合。一個(gè)基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來定位聚類。它也

26、基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)字自動(dòng)決定聚類的數(shù)目，考慮“噪音”數(shù)據(jù)或孤立點(diǎn)，從而產(chǎn)生健壯的聚類方法。一些聚類算法集成了多種聚類方法的思想，所以有時(shí)將某個(gè)給定的算法劃分為屬于某類聚類方法是很困難的。此外，某些應(yīng)用可能有特定的聚類標(biāo)準(zhǔn)，要求綜合多個(gè)聚類技術(shù)?，F(xiàn)有的許多基于網(wǎng)格的聚類算法都綜合了基于密度和基于網(wǎng)格的方法。下面我們就來詳細(xì)的介紹基于網(wǎng)格的具有代表性的聚類算法。2.2.2 基于網(wǎng)格的聚類算法基于網(wǎng)格的聚類方法是利用多維網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將空間劃分為有限數(shù)目單元，這些單元格構(gòu)成了一個(gè)可以進(jìn)行聚類分析的網(wǎng)格結(jié)構(gòu)14。這種方法的主要優(yōu)點(diǎn)是其處理時(shí)間獨(dú)立與數(shù)據(jù)對象的數(shù)目，僅依賴于量化空間中每一維上的單元數(shù)，從而

27、可以確保該類算法有較短的處理時(shí)間。常用的基于網(wǎng)格的聚類方法包括：STING11、WaveCluster12和CLIQUE13。(1)STING方法STING是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個(gè)級別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息(例如平均值、最大值和最小值)被預(yù)先計(jì)算和存儲，可以更有效的進(jìn)行查詢操作。(2)WaveCluster方法WaveCluster是一種多分辨率的聚類算法，它首先通過在數(shù)據(jù)空間上強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后采用一種小波變換來變換

28、原特征空間，在變換后的空間中找到密集區(qū)域。在該方法中，每個(gè)網(wǎng)格單元匯總了一組映射到該單元中的點(diǎn)的信息。這種匯總信息適合于在內(nèi)存中進(jìn)行多分辨率小波變換使用，以及隨后的聚類分析。小波變換是一種信號處理技術(shù)，它將一個(gè)信號分解為不同頻率的子波段。通過應(yīng)用一維小波變換n次，小波模型可以應(yīng)用于n維信號。在進(jìn)行小波變換時(shí)，數(shù)據(jù)被變換以便在不同的分辨率層次保留對象間的相對距離。這使得數(shù)據(jù)的自然聚類變得更加容易區(qū)別。通過在新的空間中尋找高密度區(qū)域，可以確定聚類。(3)CLIQUE方法CLIQUE聚類算法綜合了基于密度和基于網(wǎng)格的聚類方法。它對大規(guī)模數(shù)據(jù)庫中的高維數(shù)據(jù)的聚類非常有效。CLIQUE的中心思想如下：給

29、定一個(gè)多維數(shù)據(jù)點(diǎn)的大集合，數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和“擁擠的”區(qū)域或單元，以發(fā)現(xiàn)數(shù)據(jù)集合的全局分布模式。如果一個(gè)單元中的數(shù)據(jù)點(diǎn)的數(shù)目超過了某個(gè)輸入模型參數(shù)，則該單元是密集的。在CLIQUE中，簇定義為相連的密集單元的最大集合。2.2.3 K-means算法K-means是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似性就越大。該類算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。K-means算法的處理流程為：首先從n個(gè)數(shù)據(jù)對象中隨機(jī)選擇k個(gè)數(shù)據(jù)對象作為初始聚類的中心,而對于余下的每個(gè)

30、對象,根據(jù)其與各個(gè)聚類中心的距離或相似度,分別將它們分配給與其最相似的聚類；然后重新計(jì)算每個(gè)聚類的平均值。這個(gè)過程不斷重復(fù),直到標(biāo)準(zhǔn)測度函數(shù)開始收斂。標(biāo)準(zhǔn)測度函數(shù)通常采用平均誤差E: (2.1)其中,E表示所有聚類對象的平均誤差的總和,p表示給定的數(shù)據(jù)對象, 是聚類C內(nèi)各聚類對象的平均值,即： (2.2)表示聚類中聚類對象的數(shù)目。K-means算法的計(jì)算復(fù)雜度為，這里n為對象個(gè)數(shù)，k為聚類個(gè)數(shù)，t為循環(huán)次數(shù)。通常有k<<n和t<<n。K-means算法描述：輸入：聚類的數(shù)目k和包含n個(gè)數(shù)據(jù)對象的數(shù)據(jù)庫；最小誤差。輸出：k個(gè)聚類。方法：(1)隨機(jī)選擇k個(gè)對象作為初始的聚類

31、中心；(2)將每個(gè)對象分給初始的聚類中心；(3)Repeat(4)根據(jù)聚類中數(shù)據(jù)對象的平均值，將每個(gè)數(shù)據(jù)對象重新賦給最相似的聚類；(5)計(jì)算每個(gè)聚類中數(shù)據(jù)對象的平均值，更新聚類的平均值；(6)Until平均誤差或者每個(gè)聚類不再發(fā)生變化。假設(shè)有個(gè)分布在看見中的對象集合，如圖2.1所示。給定k=4，即用戶要求將這些對象聚類為四類。根據(jù)上述算法，最終我們可以得到圖2.2。圖2.2 K-means算法聚類結(jié)果圖2.1 原數(shù)據(jù)集 K-means算法是解決聚類問題的一種經(jīng)典算法，它是一種爬山式的搜索算法。這種算法簡單、快速。然而，K-means算法仍存在如下不足：(1)該算法只有在聚類的平均值被定義的情況

32、下才能使用，對某些應(yīng)用來講，這很難做到，如涉及有分類屬性的數(shù)據(jù)；(2)該算法對初值比較敏感，對于不同的初始值，可能會導(dǎo)致不同的聚類結(jié)果；(3)該算法要求用戶事先給定要生成的聚類個(gè)數(shù)k，k的選擇是一個(gè)比較困難的問題，一般情況下，這與具體問題有關(guān)，用戶需要選擇若干個(gè)k值進(jìn)行實(shí)驗(yàn)。3 基于相似度的網(wǎng)格聚類算法聚類分析是數(shù)據(jù)挖掘領(lǐng)域中一項(xiàng)重要的研究課題。在聚類算法中所使用的數(shù)據(jù)對象，通常是根據(jù)描述對象的屬性值來計(jì)算它們的相異度或相似度。度量它們之間的相異性或相似性有很多種方法，最常用的距離度量方法是歐幾里得距離，利用它可度量對象間的相異度；另一個(gè)著名的度量方法是曼哈坦距離；明考斯基距離是歐幾里得和曼哈

33、坦距離的概化。文獻(xiàn)11以曼哈坦距離為基礎(chǔ)定義了數(shù)據(jù)對象間的相異度，并將相異度轉(zhuǎn)化為對象間的相似度，最終使用接受率的概念用于螞蟻在圖表上的聚類算法，這使得該算法顯示出了精確、高效的聚類結(jié)果。本章是受文獻(xiàn)11的啟發(fā)，將其定義的相似度度量方法應(yīng)用于網(wǎng)格聚類，根據(jù)邊界點(diǎn)閾值函數(shù)提取類的邊界點(diǎn)，顯著地提高了網(wǎng)格聚類的精度。3.1 網(wǎng)格與相似度的概念3.1.1 網(wǎng)格的基本概念設(shè)是數(shù)據(jù)集中數(shù)據(jù)對象的r個(gè)屬性的有界定義域，那么就是一個(gè)r維空間，我們將看成是W的維(屬性、字段)，則對于一個(gè)包含n個(gè)數(shù)據(jù)點(diǎn)的r維空間中的數(shù)據(jù)集，其中，的第j個(gè)分量。將W的每一維M等分，即把W分割成M個(gè)網(wǎng)格單元。一個(gè)網(wǎng)格單元的鄰居是指

34、與其有共同邊界或共同點(diǎn)的那些網(wǎng)格單元。若一個(gè)網(wǎng)格單元中數(shù)據(jù)對象的個(gè)數(shù)大于給定的密度閾值MinPts，則認(rèn)為其是高密度單元；否則視其為低密度單元。我們只對高密度單元中的數(shù)據(jù)對象進(jìn)行聚類，通常視低密度單元中的數(shù)據(jù)對象為孤立點(diǎn)或噪聲數(shù)據(jù)將其丟棄。3.1.2 相似度數(shù)據(jù)對象間的相似性是基于對象間的距離來計(jì)算的。對象間的相似度越大，它們就越相似。也即是說，當(dāng)我們對這些數(shù)據(jù)對象聚類時(shí)，它們屬于同一個(gè)類的可能性就越大。定義 1數(shù)據(jù)記錄集：設(shè)S=(O,A)，我們用S表示n條記錄的集合。其中代表數(shù)據(jù)對象集，代表數(shù)據(jù)對象的屬性，,代表對象的第k個(gè)屬性，因此，用代表一個(gè)r維的向量。定義 2相異度：任意兩個(gè)數(shù)據(jù)對象與

35、之間的相異度定義如下：dif(i,j)=,i,j=1,2,n (3.1)定義 3相似度:任意兩個(gè)數(shù)據(jù)對象與之間的相似度定義如下: Sim(i,j)=maxdif-dif(i,j) (3.2)其中，代表數(shù)據(jù)集中數(shù)據(jù)對象間的最大相異度。3.2 SGCA算法描述3.2.1 邊界點(diǎn)閾值函數(shù)如果一個(gè)聚類的邊界點(diǎn)落入與高密度單元相鄰的低密度單元中，傳統(tǒng)的網(wǎng)格聚類算法在聚類過程中將它們看作孤立點(diǎn)或噪聲而丟棄。為了提高聚類的精度，在SGCA算法中引入邊界點(diǎn)閾值函數(shù)其定義如下： (3.3)其中，=maxj|Sim(i,j),1jn, (3.4) 邊界點(diǎn)函數(shù)Borderf(i),其定義如下： (3.5) 其中,H

36、D表示高密度單元中數(shù)據(jù)對象的個(gè)數(shù)。邊界點(diǎn)提取的主要思想是：對每一個(gè)高密度的網(wǎng)格單元，若其鄰居單元中存在低密度單元，則考查每個(gè)低密度單元中的數(shù)據(jù)對象i，如果Borderf(i)滿足給定的邊界點(diǎn)函數(shù)閾值Minf(i)，則數(shù)據(jù)對象i是此高密度單元的邊界點(diǎn)，即i與此高密度單元中的數(shù)據(jù)對象屬于一類。這樣做的好處是可以提高聚類的質(zhì)量，減少類中數(shù)據(jù)的丟失。3.2.2 SGCA聚類算法SGCA聚類算法的基本思想：首先將數(shù)據(jù)空間W劃分為網(wǎng)格單元，并將數(shù)據(jù)對象集O映射到網(wǎng)格單元中。根據(jù)用戶輸入的密度閾值MinPts判斷每個(gè)網(wǎng)格單元是否為高密度單元，對與高密度單元相鄰的低密度單元中的數(shù)據(jù)對象，利用邊界點(diǎn)閾值函數(shù)判斷

37、其是否為該高密度單元的邊界點(diǎn)，若是就提取邊界點(diǎn)，否則就作為孤立點(diǎn)或噪聲數(shù)據(jù)處理。然后根據(jù)用戶輸入的相似度閾值MinSim，對所有高密度單元中的數(shù)據(jù)對象及其提取出的邊界點(diǎn)，使用相似度方法進(jìn)行聚類，即如果任意兩個(gè)數(shù)據(jù)對象的相似度Sim(i,j)滿足給定的閾值MinSim條件，則這兩個(gè)數(shù)據(jù)對象被聚為同一類。SGCA算法流程如下：圖-不要空出,把下面的內(nèi)容提前開始劃分網(wǎng)格將數(shù)據(jù)集映射到網(wǎng)格單元中統(tǒng)計(jì)網(wǎng)格單元中的數(shù)據(jù)個(gè)數(shù)判斷是否為高密度單元低密度單元NY邊界點(diǎn)的處理對數(shù)據(jù)進(jìn)行聚類結(jié)束圖 3.1 流程圖由上圖可以看到SGCA算法可以分6個(gè)步驟進(jìn)行:步驟1將r維數(shù)據(jù)空間的每一維劃分為M個(gè)大小相等的區(qū)間，形成

38、M個(gè)網(wǎng)格單元。步驟2是通過對數(shù)據(jù)對象集O的一遍掃描，將O中的對象映射到數(shù)據(jù)空間中。步驟3是記下每一個(gè)網(wǎng)格單元中數(shù)據(jù)對象的個(gè)數(shù)。步驟4是根據(jù)用戶輸入的密度閾值MinPts判定網(wǎng)格單元的類型。如果一個(gè)網(wǎng)格單元中數(shù)據(jù)對象的個(gè)數(shù)大于MinPts，則該單元被標(biāo)記為高密度單元，否則被標(biāo)記為低密度單元。步驟5考查每個(gè)高密度單元的相鄰低密度單元中的數(shù)據(jù)對象i，如果這個(gè)數(shù)據(jù)對象的邊界點(diǎn)函數(shù)滿足用戶要求的邊界點(diǎn)閾值函數(shù)Minf(i)，則數(shù)據(jù)對象i是此高密度單元的邊界點(diǎn)，即i與此高密度單元中的數(shù)據(jù)對象同屬于一個(gè)類。經(jīng)過這一步對聚類邊界的處理，能準(zhǔn)確地將聚類的邊界點(diǎn)從噪聲數(shù)據(jù)中分離出來，從而提高了聚類的精度。步驟6是

39、對高密度單元及其邊界點(diǎn)中的所有數(shù)據(jù)點(diǎn)，如果任意兩個(gè)數(shù)據(jù)點(diǎn)的相似度函數(shù)滿足用戶設(shè)定的最小相似度閾值MinSim，那么這兩個(gè)數(shù)據(jù)對象就屬于同一個(gè)類。重復(fù)操作，直至所有的數(shù)據(jù)對象都被聚類。3.3 實(shí)驗(yàn)結(jié)果與分析本實(shí)驗(yàn)算法是用MATLAB進(jìn)行編程設(shè)計(jì)的。實(shí)驗(yàn)中用到的100個(gè)數(shù)據(jù)是隨機(jī)取的，在實(shí)驗(yàn)中，首先對SGCA算法在不同參數(shù)下的聚類結(jié)果進(jìn)行了分析對比，并且對SGCA算法和K-means算法進(jìn)行了對比。首先，我們先分析SGCA算法在不同參數(shù)下的聚類結(jié)果, 實(shí)驗(yàn)中所需要的參數(shù)如下表3.1。 原始數(shù)據(jù)的為高斯分布N(2,2)的100個(gè)隨機(jī)數(shù),如圖3.2所示。圖 3.2 原始數(shù)據(jù) 表 3.1 實(shí)驗(yàn)中數(shù)據(jù)集所

40、需參數(shù)劃分參數(shù)M密度閾值MinPts聚類結(jié)果類的個(gè)數(shù)32圖3.3652圖3.4455圖3.53310圖3.64在不同參數(shù)下，SGCA算法的聚類結(jié)果示意圖如下：圖-所示 圖3.4 SGCA算法聚類結(jié)果圖3.3 SGCA算法聚類結(jié)果 圖3.6 SGCA算法聚類結(jié)果圖3.5 SGCA算法聚類結(jié)果 從上面的各圖和表中我們可以看出，在參數(shù)M一定的情況下，參數(shù)MinPts取相對大的值，導(dǎo)致高密度單元變少,低密度單元變多,同時(shí)聚類結(jié)果變少；相反，參數(shù)MinPts取相對小的值，導(dǎo)致高密度單元變多，低密度單元變少，同時(shí)聚類結(jié)果變多。在參數(shù)MinPts一定的情況下，參數(shù)M取相對大的值，劃分的網(wǎng)格單元變少，導(dǎo)致聚類

41、結(jié)果變少；相反，參數(shù)M取相對小的值，劃分的網(wǎng)格單元變多，導(dǎo)致聚類結(jié)果變多。這些都說明，在不同的參數(shù)下使用SGCA算法得到聚類結(jié)果是不同的，這些參數(shù)直接影響了SGCA算法的聚類結(jié)果。(網(wǎng)格劃分過小，閾值取的不合適，會形成很多低密度單元，計(jì)算量變大。)從100個(gè)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果我們可以清楚看到：基于相似度的網(wǎng)格聚類算法SGCA的聚類結(jié)果明顯好于傳統(tǒng)的聚類算法K-means算法的聚類結(jié)果，具體的聚類結(jié)果圖如下： 圖3.8 SGCA算法聚類結(jié)果圖3.7 SGCA算法聚類結(jié)果圖3.7是算法K-means的聚類結(jié)果，從該圖中我們可以看到聚類結(jié)果是4個(gè)類，但由于沒有邊界處理而導(dǎo)致精度不是很高。圖3.6是算法S

42、GCA的聚類結(jié)果，從該圖我們可以看到聚類結(jié)果也是4個(gè)類，同時(shí)孤立點(diǎn)和噪聲也被有效識別出來，使聚類結(jié)果的精度有一個(gè)較大的提高。 圖3.9 SGCA算法聚類結(jié)果圖3.10 K-means算法聚類結(jié)果 圖3.9是算法K-means的聚類結(jié)果，從該圖中我們可以看到聚類結(jié)果是3個(gè)類，但由于沒有邊界處理而導(dǎo)致精度不是很高。圖3.8是算法SGCA的聚類結(jié)果，從該圖我們可以看到聚類結(jié)果也是3個(gè)類，同時(shí)孤立點(diǎn)和噪聲也被有效識別出來，使聚類結(jié)果的精度有一個(gè)較大的提高。4 結(jié)論數(shù)據(jù)挖掘技術(shù)可以從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的、有價(jià)值的知識，它給人們在信息時(shí)代所積累的海量數(shù)據(jù)賦予了新的意義。隨著數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展，作為其重

43、要組成部分，網(wǎng)格聚類技術(shù)已經(jīng)被廣泛應(yīng)用于模式識別、數(shù)據(jù)分析、圖像處理、市場研究等許多領(lǐng)域。網(wǎng)格聚類算法的研究已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中非常活躍的一個(gè)研究課題。本文介紹了數(shù)據(jù)挖掘理論，對聚類分析進(jìn)行了深入地分析研究。在研究了傳統(tǒng)網(wǎng)格聚類算法的基礎(chǔ)上，研究了基于相似度的網(wǎng)格聚類算法，將其應(yīng)用于網(wǎng)格聚類，根據(jù)定義的邊界點(diǎn)閾值函數(shù)提取類的邊界點(diǎn)，顯著地提高了網(wǎng)格聚類的精度。在本文工作的基礎(chǔ)上，今后將在以下方面做進(jìn)一步的研究：(1)基于相似度的網(wǎng)格聚類算法在聚類的精度和效率上都優(yōu)于一些傳統(tǒng)的聚類算法，但比起其他的一些聚類算法它仍需要做進(jìn)一步的改善。下一步要進(jìn)一步提高該算法的精度，盡可能的縮短聚類的運(yùn)行時(shí)間。(2)基于相似度的網(wǎng)