基于數(shù)據(jù)流的聚類分析研究及應(yīng)用.pdf

1、數(shù)據(jù)挖掘，又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)，是指從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、事先未知的、潛在有用的信息或模式。它融合了數(shù)據(jù)庫、人工智能、機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)，是數(shù)據(jù)庫研究中的一個(gè)很有應(yīng)用價(jià)值的新領(lǐng)域。而聚類分析是數(shù)據(jù)挖掘中很重要的分析手段。聚類，是按照給定的相似度定義將數(shù)據(jù)集合劃分為若干個(gè)聚類簇，使得同簇的數(shù)據(jù)之間相似度較高而不同簇的數(shù)據(jù)之間相似度較低的過程。 近年來，由于計(jì)算機(jī)及應(yīng)用技術(shù)的高速發(fā)展，人們獲取數(shù)據(jù)

2、的能力得到極大的提高，數(shù)據(jù)流(Data Streams)作為一類重要的數(shù)據(jù)來源，受到越來越多的關(guān)注，基于數(shù)據(jù)流模型的管理系統(tǒng)及其算法己成為重要的應(yīng)用前沿課題。 數(shù)據(jù)流是一組順序的、大量的、快速的、連續(xù)到達(dá)的數(shù)據(jù)序列。一般情況下，數(shù)據(jù)流可以被視為一個(gè)隨時(shí)間延續(xù)而無限增長的動(dòng)態(tài)數(shù)據(jù)集合，對流中數(shù)據(jù)的訪問代價(jià)通常比較高，因此僅一次地訪問數(shù)據(jù)成為數(shù)據(jù)流算法所追求的目標(biāo)。數(shù)據(jù)流的特性對傳統(tǒng)聚類方法提出了許多新的挑戰(zhàn)，如：僅一次地掃描數(shù)據(jù)流

3、并產(chǎn)生高質(zhì)量的聚類結(jié)果，任意時(shí)間段內(nèi)的窗口分析，等等。近些年來，數(shù)據(jù)流聚類算法逐漸開始向分層的算法框架發(fā)展。分層聚類算法通常將算法結(jié)構(gòu)分為“在線層”和“離線層”兩個(gè)部分：在線算法負(fù)責(zé)對流數(shù)據(jù)進(jìn)行快速但較為粗糙的處理，通過保存概要數(shù)據(jù)信息而避免后續(xù)過程對數(shù)據(jù)的回溯訪問；離線算法利用在線層保留下來的概要信息進(jìn)行更高層次的精確分析，并最終得到聚類結(jié)果。當(dāng)前，數(shù)據(jù)流聚類算法尚且面臨著以下一些較難解決的問題：分割數(shù)據(jù)流造成全局信息缺損從而影響聚類

4、效果、時(shí)間復(fù)雜度較高、難以實(shí)現(xiàn)有效的基于密度聚類從而發(fā)現(xiàn)數(shù)據(jù)空間中不規(guī)則分布的高密度區(qū)域，等等。 本文針對數(shù)據(jù)流聚類算法進(jìn)行了深入的研究，基于雙層數(shù)據(jù)流聚類算法框架提出了若干方法用以解決或改善上述問題，主要包括以下幾部分內(nèi)容： 1)數(shù)據(jù)流表達(dá)是在線層算法研究中的一個(gè)重要問題，直接影響到算法的處理方式及算法效率。傳統(tǒng)的模型如：界標(biāo)模型，滑動(dòng)窗口模型和快照模型都屬于基于數(shù)據(jù)壓縮的表達(dá)方式，它們針對數(shù)據(jù)本身的數(shù)值進(jìn)行計(jì)算處理，

5、得到遠(yuǎn)遠(yuǎn)小于原始數(shù)據(jù)空間的映射空間，此模式不能很好的反映空間分布。本文提出的微簇結(jié)構(gòu)能夠通過記錄數(shù)據(jù)的分布獲取更多的信息，同時(shí)可以進(jìn)一步降低算法的存儲(chǔ)需求。通過保存數(shù)據(jù)本身使其在以后的處理中可以動(dòng)態(tài)調(diào)整所屬劃分，從而更好地反映出空間分布的變化。 2)在線算法向離線算法輸出中間數(shù)據(jù)。本文初始完全劃分和算法后來非完全劃分相結(jié)合的策略，因?yàn)榫植靠臻g中的高密度區(qū)域通常也對應(yīng)著全局空間中的密集區(qū)域的原則，于是把局部空間中的高密度區(qū)域進(jìn)行輸出，而將

6、其他的稀疏數(shù)據(jù)留在內(nèi)存中與后續(xù)數(shù)據(jù)一起處理。故初始的完全劃分的簇最后密度高的話就輸出，而密度低的就分割與后續(xù)數(shù)據(jù)一起處理。這種劃分策略能夠提高在線層的輸出質(zhì)量，進(jìn)而得到更好的聚類結(jié)果。 3)提出一種改進(jìn)的雙層流數(shù)據(jù)聚類算法SCluStream，聚類結(jié)果能夠較真實(shí)的反映出數(shù)據(jù)的空間分布。在對數(shù)據(jù)流進(jìn)行初步聚類的同時(shí)，盡量保留數(shù)據(jù)的分布特征，對流數(shù)據(jù)的動(dòng)態(tài)特性表現(xiàn)出更強(qiáng)的適應(yīng)性。實(shí)驗(yàn)結(jié)果表明，算法能夠保持較低的時(shí)間開銷并得到質(zhì)量較高

7、的聚類結(jié)果。 4)本文提出了一種新算法DenCluStream用于挖掘數(shù)據(jù)流中具有任意形狀的簇．我們把密度函數(shù)以權(quán)值的形式引入數(shù)據(jù)結(jié)構(gòu)中，并利用核心微簇描述數(shù)據(jù)流中任意形狀的簇，并提出候選核心微簇和孤立微簇結(jié)構(gòu)分別用于維護(hù)并區(qū)分?jǐn)?shù)據(jù)流中潛在的核心簇和孤立點(diǎn)。在線層輸出的結(jié)果在離線層用“多維球簇”進(jìn)行保存，節(jié)省了外存空間。 另外，本文初步探討了聚類分析算法的應(yīng)用，分析目前聚類分析算法應(yīng)用的現(xiàn)狀，展望應(yīng)用前景，為以后研究做基