流數(shù)據(jù)的聚類分類算法研究.pdf

1、近年來，隨著信息處理應(yīng)用的發(fā)展，許多應(yīng)用中的數(shù)據(jù)是以流的形式產(chǎn)生的，數(shù)據(jù)呈現(xiàn)出“連續(xù)數(shù)據(jù)流”的形式而不是傳統(tǒng)的靜態(tài)存儲結(jié)構(gòu)形式。這些應(yīng)用領(lǐng)域包括金融證券信息分析、網(wǎng)絡(luò)傳輸監(jiān)控、計算機網(wǎng)絡(luò)安全、通信數(shù)據(jù)管理、web應(yīng)用、生產(chǎn)制作、傳感器網(wǎng)絡(luò)等。這些應(yīng)用產(chǎn)生的數(shù)據(jù)形式稱為數(shù)據(jù)流。與傳統(tǒng)數(shù)據(jù)庫不同，數(shù)據(jù)流具有如下特點：(1)數(shù)據(jù)總量的無限性；(2)數(shù)據(jù)到達的快速性；(3)數(shù)據(jù)到達次序的無約束性；(4)除非可以保存，每個元素均只能被處理一次。

2、 數(shù)據(jù)流的上述特點對數(shù)據(jù)流上的挖掘提出了如下要求：首先，算法必須能夠進行實時在線挖掘，快速處理每一個元組，并實時輸出挖掘處理結(jié)果。其次，由于相對于無限規(guī)模的數(shù)據(jù)流而言，內(nèi)存通常是有限的，這就要求算法的空間復(fù)雜度要低，往往需要在數(shù)據(jù)量的對數(shù)范圍內(nèi)。再次，由于算法實時在線挖掘以及對空間復(fù)雜度的限制，算法往往只能得到近似解，且需要具有一定的精確度保證。最后，算法要具有較強的適應(yīng)性，包括對數(shù)據(jù)流不斷進化的底層模型的適應(yīng)性，處理離群點能力等

3、。 學術(shù)界己經(jīng)對數(shù)據(jù)流上的挖掘問題進行了很多研究工作，但仍存在許多問題尚待研究和解決。 本文研究了數(shù)據(jù)流上的聚類問題和分類問題，做了以下一些工作： (1)提出了基于相關(guān)系數(shù)的多數(shù)據(jù)流聚類算法。使用相關(guān)系數(shù)作為數(shù)據(jù)流間距離的度量，將有相同變化趨勢的數(shù)據(jù)流聚為一類。我們使用衰減系數(shù)來使得新數(shù)據(jù)比舊數(shù)據(jù)在聚類結(jié)構(gòu)中有更大的重要性，采用更新時間片段的機制很好地反映了聚類結(jié)構(gòu)的變化過程。我們采用動態(tài)k-means，不斷的試

4、探性地調(diào)整聚類的個數(shù)，通過比較聚類質(zhì)量，選取最優(yōu)的類的個數(shù)，提高聚類質(zhì)量。 此外，我們基于相關(guān)系數(shù)的度量，提出了另一種滿足用戶需求的聚類算法框架。算法分為前臺和后臺兩個部分：在前臺部分，我們提出了一種新穎的保存匯總信息的機制；后臺階段，根據(jù)用戶的聚類請求，讀取相應(yīng)長度的信息進行聚類。滿足了用戶對不同長度的聚類需求。 (2)提出了一種基于譜分量相似度的多數(shù)據(jù)流的聚類算法框架。使用自回歸模型對數(shù)據(jù)流序列作譜分析，把數(shù)據(jù)流表示

5、為譜參數(shù)的和。通過將相位設(shè)為零后，使用譜分量信息計算兩條數(shù)據(jù)流之間的相關(guān)性。 (3)提出了一種基于網(wǎng)格密度的數(shù)據(jù)流聚類算法GDCS算法。算法采用了在線／離線雙層框架，它在前臺在線層快速實時地將到達的數(shù)據(jù)點放入相應(yīng)的單元格，在后臺離線層不斷地更新單元格的密度并將網(wǎng)格單元聚成類。此外，算法適時檢測和剔除孤立點以改進系統(tǒng)的時間空間有效性。實驗表明，算法具有更優(yōu)的聚類效率和聚類質(zhì)量，能發(fā)現(xiàn)任意形狀的類，且能有效識別實時數(shù)據(jù)流的變化行為。