基于密度單元覆蓋的聚類(lèi)數(shù)據(jù)流算法研究.pdf

1、隨著計(jì)算機(jī)應(yīng)用的普及，信息系統(tǒng)產(chǎn)生的數(shù)據(jù)量日益增大，如何有效的利用巨量的原始數(shù)據(jù)分析現(xiàn)狀和預(yù)測(cè)未來(lái)，已經(jīng)成為人類(lèi)面臨的一大挑戰(zhàn)。近年來(lái)，越來(lái)越多的應(yīng)用促使了數(shù)據(jù)流的產(chǎn)生，它是連續(xù)的、有序的、快速變化的、海量的數(shù)據(jù)，如網(wǎng)絡(luò)連接數(shù)據(jù)、傳感器數(shù)據(jù)和Web點(diǎn)擊流數(shù)據(jù)，分析和挖掘這種類(lèi)型的數(shù)據(jù)已經(jīng)成為一個(gè)熱點(diǎn)。 聚類(lèi)是挖掘數(shù)據(jù)流的一種重要工具。聚類(lèi)就是把沒(méi)有類(lèi)別標(biāo)記的樣本按照某種準(zhǔn)則劃分為若干類(lèi)，使類(lèi)內(nèi)樣本的相似性盡可能大，而類(lèi)間樣本的相

2、似性盡可能小，是一種無(wú)監(jiān)督的學(xué)習(xí)方法。流聚類(lèi)分析較傳統(tǒng)的聚類(lèi)分析具有更大的挑戰(zhàn)性，這是由數(shù)據(jù)流的特性決定的。數(shù)據(jù)流分析的基本要求有：有限的使用內(nèi)存及存儲(chǔ)空間；對(duì)數(shù)據(jù)的訪(fǎng)問(wèn)最多一次；能夠有較短的響應(yīng)時(shí)間。 除了內(nèi)存限制和單遍掃描限制，數(shù)據(jù)流環(huán)境對(duì)聚類(lèi)還有如下要求：不預(yù)先設(shè)定聚類(lèi)個(gè)數(shù)，能處理具有任意形狀的聚簇并且能夠處理孤立點(diǎn)。目前已經(jīng)提出了許多數(shù)據(jù)流聚類(lèi)算法，但是都尚未解決以上數(shù)據(jù)流環(huán)境下的要求。傳統(tǒng)的基于密度的聚類(lèi)算法，如DBS

3、CAN，可以發(fā)現(xiàn)具有任意形狀的聚類(lèi)，但這些算法的高復(fù)雜度以及多次掃描數(shù)據(jù)集的需求不適合對(duì)流數(shù)據(jù)進(jìn)行聚類(lèi)。 在數(shù)據(jù)流滑動(dòng)窗口模型下，本文提出了基于密度單元覆蓋的數(shù)據(jù)流聚類(lèi)算法DucStream。該算法能發(fā)現(xiàn)具有任意形狀的數(shù)據(jù)流聚類(lèi)，解決了由于數(shù)據(jù)流滑動(dòng)窗口模型下不能精確記錄每個(gè)數(shù)據(jù)，歷史數(shù)據(jù)對(duì)聚類(lèi)結(jié)果的影響問(wèn)題。DucStream使用核心密度單元和候選密度單元刻畫(huà)數(shù)據(jù)分布形式，作為在線(xiàn)數(shù)據(jù)摘要信息；根據(jù)每個(gè)單元中的最近數(shù)據(jù)到達(dá)時(shí)間