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

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

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

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

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

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

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