資源描述：
《基于網(wǎng)格方法的聚類算法研究》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、華中科技大學博士學位論文基于網(wǎng)格方法的聚類算法研究姓名：孫玉芬申請學位級別：博士專業(yè)：計算機軟件與理論指導教師：盧炎生20061107摘要隨著信息技術在各個領域的普及，各種應用每天產(chǎn)生的數(shù)據(jù)量呈指數(shù)級增長。如何有效處理這些數(shù)據(jù)，從中提取有用的知識，是迫切需要解決的問題。數(shù)據(jù)挖掘的任務是從大型數(shù)據(jù)集中提取知識。聚類分析是數(shù)據(jù)挖掘中的一項主要技術，它將物理對象或抽象對象的集合分組成為由類似的對象組成的多個簇。網(wǎng)格方法在空間數(shù)據(jù)分析、索引，和聚類中都有應用。使用網(wǎng)格方法的數(shù)據(jù)分析方法將空間劃分為由（超）矩形網(wǎng)格單元組成的網(wǎng)格，然后在網(wǎng)格單元上進行各種分析。數(shù)據(jù)空間
2、可以以多種方式劃分成網(wǎng)格，其中以簡單的樹形網(wǎng)格劃分和p×p網(wǎng)格劃分用得最多。通過將同一網(wǎng)格單元內的數(shù)據(jù)的信息用它們的統(tǒng)計信息替代，網(wǎng)格可以直觀地將數(shù)據(jù)壓縮。網(wǎng)格單元的壓縮功能與微簇和抗體對數(shù)據(jù)的壓縮有很多相似之處，但是它們也具有很多不同的性質。使用網(wǎng)格單元、微簇，和抗體的聚類算法對壓縮單元的生成和管理采用了不同的策略。利用網(wǎng)格的空間劃分特征和網(wǎng)格內信息的可加性，基于網(wǎng)格方法的算法可以以多種方式進行并行化?，F(xiàn)有的基于網(wǎng)格方法的聚類算法都假設落入同一個網(wǎng)格單元的數(shù)據(jù)點屬于同一個簇，這個假設并不總是成立。設計了一個新的基于網(wǎng)格的數(shù)據(jù)壓縮方法，這個壓縮方法只有在能確認
3、一組數(shù)據(jù)都屬于同一個簇時，才對這組數(shù)據(jù)進行壓縮。在網(wǎng)格數(shù)據(jù)結構中，完全位于一個簇內部的網(wǎng)格單元內的數(shù)據(jù)可以肯定都屬于這個簇?；趯臻g中網(wǎng)格單元與簇的關系的觀察，新的數(shù)據(jù)壓縮方法采用不均勻的網(wǎng)格劃分方法，對簇內部的網(wǎng)格單元采用較大的粒度，進行安全的數(shù)據(jù)壓縮。對簇邊緣的網(wǎng)格單元采用較小的粒度，提高簇的描述精度。基于新的數(shù)據(jù)壓縮方法，設計了一個聚類算法SGRIDS。此算法基于網(wǎng)格單元內數(shù)據(jù)的密度，判斷網(wǎng)格單元的位置。算法SGRIDS能通過對數(shù)據(jù)集的一次掃描，I以較高精度快速找到大型空間數(shù)據(jù)集中的簇。由于網(wǎng)格單元的大小不再影響數(shù)據(jù)壓縮質量，此算法的聚類質量受網(wǎng)格單元
4、粒度影響較小。而通過保存記錄簇的形狀的邊緣點，算法能以較高精度描述簇的形狀。SGRIDS的計算復雜度為O(N)，它對超大型空間數(shù)據(jù)集具有好的可伸縮性，能發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的簇，并且不受數(shù)據(jù)輸入順序的影響。實驗表明，SGRIDS的聚類質量比經(jīng)典算法WaveCluster好，算法對網(wǎng)格劃分參數(shù)的敏感度比WaveCluster低。流數(shù)據(jù)挖掘是當前數(shù)據(jù)挖掘領域研究的熱點。流數(shù)據(jù)在線流入的特征對聚類算法提出了多個新的要求，其中最基本的是只能對數(shù)據(jù)作一次線性掃描。為滿足這些要求，流數(shù)據(jù)聚類算法通常使用概要數(shù)據(jù)結構對數(shù)據(jù)進行在線壓縮。提出一個使用網(wǎng)格數(shù)據(jù)結構作為概要數(shù)據(jù)結
5、構的算法GCHDS處理高維數(shù)據(jù)流。算法采用一個簡單的啟發(fā)式方法，通過分析數(shù)據(jù)在每維投影的分布，選擇對聚類分析有用的維來降低數(shù)據(jù)空間的維度。在真實數(shù)據(jù)集上的實驗分析驗證了算法的正確度與運行效率。實驗表明，GCHDS的聚類性能比VLDB文章中的算法HPStream好。GSCDS是一個聚類高維數(shù)據(jù)流的子空間聚類算法。此算法結合由底向上的網(wǎng)格劃分方法和自頂向下的網(wǎng)格劃分方法，能快速、有效地處理高維數(shù)據(jù)流。GSCDS使用均勻劃分的網(wǎng)格在線壓縮數(shù)據(jù)流數(shù)據(jù)。在此網(wǎng)格數(shù)據(jù)結構上，使用自頂向下的網(wǎng)格劃分方法將數(shù)據(jù)中的簇分隔開，并將每個簇與相應的子空間及區(qū)域相關聯(lián)。然后，算法將各
6、子空間中相連的網(wǎng)格單元識別為簇，得到精確的簇的描述。最后，算法檢查是否有簇需要被合并，從而消除自頂向下網(wǎng)格劃分方法所引入的錯誤。對算法的復雜度分析以及在多個數(shù)據(jù)集上所做的性能分析實驗都驗證了此算法的計算效率和有效性。關鍵詞：聚類;網(wǎng)格方法;數(shù)據(jù)壓縮;數(shù)據(jù)流;子空間聚類IIAbstractAstheinformationtechnologieshavebeenusedwidelyinmanyfieldsofhumanlife,thedatagainedfromthesefieldsgrowsexponentiallyeveryday.Howtoextractkn
7、owledgefromthesedataisaproblemthatshouldbesolved.Theaimofdataminingistoextractknowledgefromlargedatasets.Clusteringanalysisisamaintechniqueofdatamining.Itpartitionsdataobjectsintoclustersthatarecomposedbysimilarobjects.Gridhasbeenusedinspatialdataanalysis,index,andclustering.Grid-ba
8、seddataanalysismeth
