數(shù)據(jù)流聚類分析算法.pdf

1、近年來，許多應(yīng)用中的數(shù)據(jù)是以流的形式產(chǎn)生的，例如網(wǎng)絡(luò)流，傳感器數(shù)據(jù)，以及網(wǎng)頁點擊流等。分析和挖掘這類數(shù)據(jù)日益成為一個熱點問題。作為一種基礎(chǔ)的數(shù)據(jù)挖掘手段，聚類分析在數(shù)據(jù)流環(huán)境下得到了學術(shù)界和工業(yè)界的廣泛關(guān)注。與傳統(tǒng)數(shù)據(jù)庫不同，數(shù)據(jù)流具有如下特點：(1)數(shù)據(jù)總量的無限性；(2)數(shù)據(jù)到達的快速性；(3)數(shù)據(jù)到達次序的無約束性；(4)除非可以保存，每個元素均只能被處理一次。 數(shù)據(jù)流的上述特點對數(shù)據(jù)流上的聚類挖掘提出了如下要求：首先，算

2、法必須能夠進行實時在線挖掘，快速處理每一個元組，并實時輸出挖掘處理結(jié)果。其次，相對于無限規(guī)模的數(shù)據(jù)流內(nèi)存通常是有限的，算法的空間復雜度要低，往往需要在數(shù)據(jù)量的對數(shù)范圍內(nèi)。再次，由于算法實時在線挖掘以及對空間復雜度的限制，算法往往只能得到近似解，且需要具有一定的精確度保證。最后，算法要具有較強的適應(yīng)性，包括對數(shù)據(jù)流不斷進化的底層模型的適應(yīng)性，處理離群點的能力，以及挖掘任意形狀簇的能力等。 學術(shù)界已經(jīng)對數(shù)據(jù)流上的聚類分析問題進行了不

3、少研究工作，但仍存在許多問題尚待研究和解決。本文研究了滑動窗口內(nèi)的數(shù)據(jù)流聚類分析問題，數(shù)據(jù)流中具有任意形狀簇的挖掘問題，利用圖形處理器加速數(shù)據(jù)流聚類問題以及分布式數(shù)據(jù)流的數(shù)據(jù)聚類問題，旨在為現(xiàn)有的數(shù)據(jù)流系統(tǒng)提供更為多樣的聚類分析功能。本文的主要貢獻有如下四個方面： 1．本文提出了一種新算法CluWin來解決滑動窗口內(nèi)數(shù)據(jù)流聚類分析問題。我們設(shè)計了一種新的概要結(jié)構(gòu)一聚類特征指數(shù)直方圖一來保持滑動窗口中簇的統(tǒng)計信息。CluWin算法

4、僅需要維護O(κ/εlog(ε[N/κ]))個時間聚類特征結(jié)構(gòu)，就能夠估算長度為Ⅳ的滑動窗口中所有記錄的聚類結(jié)果，且窗口最大相對誤差不超過c。此外，它還被擴展用于解決N-n窗口(滑動窗口擴展模型)數(shù)據(jù)聚類問題。 2．本文提出了一種新算法DenStream用于挖掘進化數(shù)據(jù)流中具有任意形狀的簇。我們引入一種“密”微簇稱為核心微簇(core-micro-cluster)用于描述數(shù)據(jù)流中任意形狀的簇，并提出潛在核心微簇(potentia

5、lcore-micro-cluster)和離群微簇(outliermicro-cluster)結(jié)構(gòu)分別用于維護并區(qū)分數(shù)據(jù)流中潛在的簇和離群點。DenStream基于這些概念包含了一種新穎的淘汰策略，該策略可利用次線性空間的內(nèi)存維護并保證各微簇權(quán)值的精度。 3．本文利用性能強大、日趨廉價且在數(shù)據(jù)流領(lǐng)域尚未引起足夠重視的圖形處理器(GPU)處理數(shù)據(jù)流聚類挖掘問題。我們提出一類基于GPU的快速聚類方法，包括基于k-means的基本聚類

6、方法，基于GPU的數(shù)據(jù)流聚類以及數(shù)據(jù)流簇進化分析方法。這些方法的共同特點就是充分利用GPU強大的處理能力和流水線特性。與以往具有獨立框架的數(shù)據(jù)流聚類算法不同，基于GPU的聚類算法具有同一框架和多種聚類分析功能，為數(shù)據(jù)流聚類分析提供了統(tǒng)一平臺。 4．本文提出了一個分布式聚類處理框架CluDistream。該框架可高效地實時處理分布式數(shù)據(jù)流中海量數(shù)據(jù)，有噪聲、有損或不完整數(shù)據(jù)記錄，以及有交疊的數(shù)據(jù)集。在CluDistream基于期望

7、最大化(ExpectationMaximization)的算法中，每個數(shù)據(jù)記錄可以以不同的隸屬度屬于不同的簇。這種軟聚類方式能較好地反映簇的交疊性。對有噪聲、損壞的或不完整的數(shù)據(jù)記錄，算法可通過最大化數(shù)據(jù)簇的似然度來學習數(shù)據(jù)流的底層分布。此外，CluDistream算法中測試后聚類的策略可有效地減少算法的平均處理代價，這對分布式數(shù)據(jù)流的在線實時聚類挖掘非常有效。 總之，本文研究了數(shù)據(jù)流聚類分析的四個基本問題并分別提出了新的解決方

8、案?；瑒哟翱谑翘幚頂?shù)據(jù)流的基本模型之一，如何在滑動窗口內(nèi)對數(shù)據(jù)流進行聚類分析是一個基本問題；具有任意形狀簇相對于球形簇是更為一般的數(shù)據(jù)簇模型，如何挖掘任意形狀的簇也是一個基本問題；如何提高數(shù)據(jù)流聚類算法的處理速度是一個基本問題，這是由數(shù)據(jù)流聚類算法實時在線挖掘的特點所決定的：分布式數(shù)據(jù)流的數(shù)據(jù)聚類問題，其基礎(chǔ)性在于現(xiàn)實應(yīng)用中數(shù)據(jù)流往往是在分布式環(huán)境中產(chǎn)生的。本文算法是對現(xiàn)有數(shù)據(jù)流上的聚類分析技術(shù)的有益補充和改進。理論分析和實驗結(jié)果表明本