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

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

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

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

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

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

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

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

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