基于密度的數(shù)據(jù)流聚類方法研究.pdf

1、近年來，隨著信息技術(shù)的飛速發(fā)展和廣泛應(yīng)用，數(shù)據(jù)流作為一種普遍存在的數(shù)據(jù)形式，吸引了越來越多數(shù)據(jù)挖掘研究者的關(guān)注。與存儲(chǔ)于可多次隨機(jī)訪問介質(zhì)中的靜態(tài)數(shù)據(jù)不同，數(shù)據(jù)流具有連續(xù)性、實(shí)時(shí)性、次序性等特征，使傳統(tǒng)的聚類分析技術(shù)不適用于數(shù)據(jù)流環(huán)境。學(xué)術(shù)界已經(jīng)對(duì)數(shù)據(jù)流上的聚類分析問題進(jìn)行了不少研究工作，開發(fā)出很多快速有效地針對(duì)數(shù)據(jù)流的聚類算法，給人們提供了有價(jià)值的信息幫助決策。由于數(shù)據(jù)流本身的復(fù)雜性和多樣性，現(xiàn)有算法仍然有待于進(jìn)一步提高以適應(yīng)新的條件

2、和要求，在諸如提高聚類結(jié)果的精度，發(fā)現(xiàn)不同密度的聚簇和離群點(diǎn)，在分布式數(shù)據(jù)流和不確定數(shù)據(jù)流中發(fā)現(xiàn)不同形狀的聚簇等方面仍然有很多迫切需要解決的問題等待進(jìn)一步研究。本文針對(duì)數(shù)據(jù)流分析中的聚類分析任務(wù)，利用基于密度的聚類技術(shù)，從以下四個(gè)方面進(jìn)行了更加細(xì)致有效的研究：
　　首先，針對(duì)不確定數(shù)據(jù)流聚類算法大多應(yīng)用基于距離劃分的聚類思想，難于發(fā)現(xiàn)不確定數(shù)據(jù)流中的非球狀簇，而現(xiàn)有的基于密度的不確定數(shù)據(jù)流聚類算法不能解決屬性級(jí)不確定性聚類問題。提

3、出衡量網(wǎng)格不確定性的期望距離標(biāo)準(zhǔn)，通過分析屬性級(jí)不確定性對(duì)聚類問題的影響定義網(wǎng)格概率密度，使網(wǎng)格密度能夠兼顧網(wǎng)格中數(shù)據(jù)量與不確定性雙重因素；同時(shí)，定義了新的密度閾值標(biāo)準(zhǔn)和網(wǎng)格衰減標(biāo)準(zhǔn)，并據(jù)此分類網(wǎng)格及設(shè)計(jì)聚類算法，保證了及時(shí)捕捉到簇的變化；在此基礎(chǔ)上，結(jié)合衰減窗口技術(shù)，提出一種基于網(wǎng)格密度的不確定數(shù)據(jù)流聚類算法(DBUSC)，查找密度大于動(dòng)態(tài)密度閾值的相鄰網(wǎng)格單元得到最終聚類結(jié)果；最后，通過實(shí)驗(yàn)表明：與傳統(tǒng)的基于距離劃分方法相比， DB

4、USC算法具有能夠發(fā)現(xiàn)非球形狀聚簇和無需指定簇?cái)?shù)的優(yōu)點(diǎn)，在聚類不確定數(shù)據(jù)流時(shí)不僅所產(chǎn)生的時(shí)間代價(jià)更小，而且能夠取得更好的聚類質(zhì)量。
　　其次，針對(duì)基于微聚類的數(shù)據(jù)流聚類方法中的微聚類結(jié)構(gòu)不保留數(shù)據(jù)流自身信息，影響了聚類準(zhǔn)確度，同時(shí)采用的兩階段聚類的思想降低了算法效率問題。提出用代表點(diǎn)結(jié)構(gòu)作為數(shù)據(jù)流的概要結(jié)構(gòu)，用以保存數(shù)據(jù)流的密度信息，在代表點(diǎn)的基礎(chǔ)上定義環(huán)點(diǎn)，設(shè)計(jì)迭代算法通過查找環(huán)點(diǎn)得到密度相連的代表點(diǎn)形成簇；另外，定義了代表點(diǎn)時(shí)

5、態(tài)權(quán)重，提出一種基于代表點(diǎn)性質(zhì)的數(shù)據(jù)流聚類算法(RB-Stream)，采用測試-更新策略及時(shí)發(fā)現(xiàn)低于權(quán)重閾值的代表點(diǎn)，和權(quán)重不斷增加的新的代表點(diǎn)，能夠在最大程度上發(fā)現(xiàn)數(shù)據(jù)流中舊簇消亡和新簇出現(xiàn)的同時(shí)，進(jìn)一步提高RB-Stream算法的運(yùn)行效率；最后，通過分析和實(shí)驗(yàn)表明：RB-Stream算法相對(duì)于二次聚類微簇得到聚類結(jié)果的算法，具有更好的聚類準(zhǔn)確性，節(jié)省了聚類所需的運(yùn)行時(shí)間。
　　再次，針對(duì)現(xiàn)有的數(shù)據(jù)流聚類多數(shù)只能適用于密度一致的

6、流數(shù)據(jù)，不能發(fā)現(xiàn)數(shù)據(jù)流中密度不同的簇，并且數(shù)據(jù)流中數(shù)據(jù)不斷流入，使發(fā)現(xiàn)密度不同且動(dòng)態(tài)改變的簇和離群點(diǎn)尤為困難的問題。在共享最近鄰圖的基礎(chǔ)上，定義了共享最近鄰密度，結(jié)合數(shù)據(jù)對(duì)象被類似的最近鄰對(duì)象包圍的程度和被其周圍對(duì)象需要的程度這兩個(gè)環(huán)境因素，使聚類結(jié)果不受密度變化的影響；另外，定義了數(shù)據(jù)對(duì)象的平均距離和簇密度，以識(shí)別離群點(diǎn)和簇間的橋接；在此基礎(chǔ)上，結(jié)合滑動(dòng)窗口技術(shù)，維護(hù)共享最近鄰圖實(shí)現(xiàn)簇的不斷更新，提出了一種基于共享最近鄰密度的演化數(shù)據(jù)

7、流聚類算法(SNDStream)，查找密度大于指定閾值的連通分支得到聚類結(jié)果；最后，通過分析和實(shí)驗(yàn)表明：SNDStream算法能夠發(fā)現(xiàn)任意形狀和不同密度的簇，正確識(shí)別離群點(diǎn)和聚簇之間的連接，具有良好的聚類質(zhì)量，能夠在不指定簇?cái)?shù)的條件下有效適應(yīng)聚簇不斷變化的數(shù)據(jù)流場景。
　　最后，在分布式數(shù)據(jù)流環(huán)境中發(fā)現(xiàn)任意形狀的簇具有非常重要的意義，針對(duì)現(xiàn)有的分布式數(shù)據(jù)流聚類算法采用基于距離劃分的或者基于模型的聚類思想，難于很好的處理數(shù)據(jù)流中的非