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

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

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

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

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

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

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

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