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

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

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

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

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

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