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

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

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

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