一種基于小波概要的數(shù)據(jù)流量子聚類算法

米 瀅

(大連職業(yè)技術(shù)學(xué)院信息工程學(xué)院 遼寧 大連 116035)

一種基于小波概要的數(shù)據(jù)流量子聚類算法

米 瀅

(大連職業(yè)技術(shù)學(xué)院信息工程學(xué)院 遼寧 大連 116035)

針對(duì)傳統(tǒng)的聚類分析技術(shù)面對(duì)長(zhǎng)度無(wú)限且隨時(shí)變化的海量級(jí)數(shù)據(jù)流無(wú)法直接使用或使用缺陷突出等問題，從數(shù)據(jù)流自身特性出發(fā)，結(jié)合小波變換與量子理論，提出一種新的數(shù)據(jù)流量子聚類算法。該算法首先采用離散小波變換，從每個(gè)數(shù)據(jù)流中動(dòng)態(tài)分層地提取出其概要結(jié)構(gòu)作為其相應(yīng)的特征屬性，同時(shí)計(jì)算出每個(gè)數(shù)據(jù)流到聚類中心的近似距離，結(jié)合量子理論估算出較優(yōu)的核寬度調(diào)節(jié)參數(shù)進(jìn)行類調(diào)整，最終獲得一個(gè)較為理想的聚類效果。實(shí)驗(yàn)表明，該算法較好地解決了傳統(tǒng)聚類方法無(wú)法良好解決的多數(shù)據(jù)流并行聚類問題，并表現(xiàn)出較好的聚類性能。

多數(shù)據(jù)流聚類 小波變換 量子勢(shì)能

0 引 言

隨著網(wǎng)絡(luò)通信、監(jiān)控、實(shí)時(shí)股票行情等領(lǐng)域的深入發(fā)展，數(shù)據(jù)挖掘領(lǐng)域中涌現(xiàn)出了許多連續(xù)不斷且隨時(shí)間變化而演變的序列型數(shù)據(jù)，面對(duì)新的研究環(huán)境，數(shù)據(jù)挖掘的研究也迎來(lái)了新的挑戰(zhàn)。為此，研究者們紛紛提出了許多新的數(shù)據(jù)流聚類、分類、關(guān)聯(lián)挖掘等應(yīng)用算法。概括起來(lái)，可以分為兩個(gè)方面：第一，從單條數(shù)據(jù)流出發(fā)進(jìn)行挖掘，著重關(guān)注于不同時(shí)間段內(nèi)數(shù)據(jù)間的隱含信息；第二，對(duì)多條數(shù)據(jù)流的挖掘，主要關(guān)注于多條數(shù)據(jù)流之間的相關(guān)性。

針對(duì)多數(shù)據(jù)流的聚類問題，文獻(xiàn)[1]構(gòu)建SPIRIT算法來(lái)挖掘多條數(shù)據(jù)流之間的相關(guān)性，該算法利用主成分分析法，采用動(dòng)態(tài)更新的策略不斷更新代表多數(shù)據(jù)流的隱藏變量及其權(quán)重；文獻(xiàn)[2]引入滯后相關(guān)性增量公式來(lái)發(fā)掘多條數(shù)據(jù)流之間滯后相關(guān)性的Braid算法；文獻(xiàn)[3]中，Yang利用概貌偏差(snapshot deviation)計(jì)算出兩個(gè)不同數(shù)據(jù)流間的加權(quán)聚合信息，以此來(lái)判斷各數(shù)據(jù)流間的相似性。文獻(xiàn)[4]中，Beringer等人首先利用離散傅里葉變換對(duì)原數(shù)據(jù)流進(jìn)行處理，得到其低頻分量，然后利用這些低頻分量的歐氏距離來(lái)評(píng)判數(shù)據(jù)流之間的相似性；文獻(xiàn)[5]引入“按需聚類( Clustering on Demand)”的概念，提出了ADAPTIVEclustering算法，該算法將多數(shù)據(jù)流聚類劃分為兩個(gè)階段：在線信息的統(tǒng)計(jì)與維護(hù)、離線的自適應(yīng)聚類。這些算法在某種程度上解決了傳統(tǒng)挖掘算法的一定缺陷問題，但大都忽視了數(shù)據(jù)流的遺忘特性。在數(shù)據(jù)流中，人們往往會(huì)遺忘掉比較久遠(yuǎn)的數(shù)據(jù)或者僅需了解久遠(yuǎn)數(shù)據(jù)的大略概況，而更多關(guān)注于數(shù)據(jù)流中的近期數(shù)據(jù)，以及近期數(shù)據(jù)的細(xì)節(jié)信息。另外，現(xiàn)存的算法大都采用活動(dòng)窗口技術(shù)，且認(rèn)為窗口中的數(shù)據(jù)可以重復(fù)存取，于是產(chǎn)生了較大存儲(chǔ)與計(jì)算的代價(jià)需求。

針對(duì)這些問題，本文充分分析了數(shù)據(jù)流的遺忘特性，引入隨時(shí)間推薦而衰減的影響因子來(lái)標(biāo)注數(shù)據(jù)流中不同數(shù)據(jù)的影響力，采用離散小波變換DWT(discrete wavelet transform)適度地壓縮海量數(shù)據(jù)流。然后結(jié)合量子理論，利用改進(jìn)的量子聚類算法對(duì)用概要結(jié)構(gòu)表示的一組并行數(shù)據(jù)流進(jìn)行聚類分析。本文將該算法稱為W-HAS-PEQC。通過實(shí)驗(yàn)對(duì)比表明，該算法不僅解決了傳統(tǒng)聚類方法無(wú)法較好解決的多數(shù)據(jù)流并行聚類問題，而且在多數(shù)據(jù)流聚類問題上表現(xiàn)出良好的性能。

1 相關(guān)研究

1.1 數(shù)據(jù)的小波壓縮

面對(duì)海量級(jí)規(guī)模的數(shù)據(jù)流，在對(duì)其進(jìn)行分析前先進(jìn)行數(shù)據(jù)壓縮處理是很有必要的。在數(shù)據(jù)壓縮處理中，DWT[7]技術(shù)以其優(yōu)異的特性越來(lái)越受研究者們的青睞，尤其是Haar小波變換，作為DWT技術(shù)中最簡(jiǎn)單的一種，憑借著它簡(jiǎn)單、易實(shí)現(xiàn)且有效的優(yōu)異特性得到了廣泛的應(yīng)用。

利用一維Haar小波變換，可以將向量D=(x1,x2,…,xn)分解表示為n個(gè)小波系數(shù)(c1,c2,…,cn)，我們使用一個(gè)簡(jiǎn)單的實(shí)例來(lái)說明Haar小波變換。

例：假設(shè)某一數(shù)據(jù)序列D=(9,5,6,4,4,4,5,7)(n=8)，對(duì)其進(jìn)行Haar小波變換，具體過程如表1所示。

表1 序列D的Haar小波變換

本例中，小波層次由表1中的Resolution列中的l值表示，原始數(shù)據(jù)序列存儲(chǔ)在l=3這一層次的Averages列中，將原數(shù)據(jù)序列中的數(shù)據(jù)項(xiàng)兩兩組對(duì)，求其均值記為l=2中的Averages值，即：((9+5)/2,(6+4)/2,(4+4)/2,(5+7)/2)=(7,5,4,6)，經(jīng)過這一變換后，原數(shù)據(jù)序列的8個(gè)數(shù)據(jù)項(xiàng)將被壓縮成4個(gè)數(shù)據(jù)項(xiàng)，顯然丟失了原始數(shù)據(jù)序列中的某些數(shù)據(jù)信息。為了能夠重新構(gòu)造出原始數(shù)據(jù)序列集，我們?cè)诒４娼M合后的數(shù)據(jù)對(duì)均值的同時(shí)，將該均值與原組對(duì)中第2個(gè)數(shù)據(jù)項(xiàng)之差也保存起來(lái)。表1中Detailcoefficients列即為數(shù)據(jù)對(duì)均值與原組對(duì)中第2個(gè)數(shù)據(jù)項(xiàng)之間的差值。即：(7-5,5-4,4-4,6-7)=(2,1,0,-1)，迭代重復(fù)此步驟，直至層次達(dá)到l=0，最后得到的均值與Detailcoefficients列中的全部數(shù)值即組成原數(shù)據(jù)序列的小波系數(shù)(5.5,0.5,1,-1,2,1,0,-1)。

采用樹形結(jié)構(gòu)來(lái)表示該分解過程，如圖1所示，該樹稱為誤差樹。圖中節(jié)點(diǎn)ci(i=1,2,…,8)即為分解后的小波系數(shù)，葉子節(jié)點(diǎn)xi(i=1,2,…,8)為原數(shù)據(jù)序列中的數(shù)據(jù)項(xiàng)。以ck為根節(jié)點(diǎn)的子樹葉節(jié)點(diǎn)可劃分為左右兩個(gè)子集合：左子樹葉節(jié)點(diǎn)leftleavesk、右子樹葉節(jié)點(diǎn)rightleavesk。樹中從ck(或xk)節(jié)點(diǎn)到根節(jié)點(diǎn)的所有非零系數(shù)集合記為路徑pathk。由誤差樹可知，節(jié)點(diǎn)ck=(ak-bk)/2，其中k=2,3,…,n，ak為leftleavesk中數(shù)據(jù)的均值，bk為rightleavesk中數(shù)據(jù)的均值，而c1則為全部數(shù)據(jù)的均值，故原數(shù)據(jù)序列xi=∑cj∈pathiδij·cj，這里δij為一符號(hào)函數(shù)：

比如x2=+5.5+0.5+1-2=5，由此便可以重構(gòu)出原始數(shù)據(jù)序列集。

圖1 序列D的誤差樹

1.2 基于參數(shù)估計(jì)的量子聚類

以粒子在量子空間中的分布為主要研究對(duì)象的量子力學(xué)在數(shù)據(jù)挖掘領(lǐng)域里得到了越來(lái)越多的應(yīng)用，尤其是在聚類分析技術(shù)中，近年來(lái)，許多學(xué)者都開始著手研究量子聚類算法[6]的研究。

量子理論中，粒子的分布狀態(tài)采用概率波函數(shù)描述，對(duì)其求解常采用有勢(shì)場(chǎng)約束的薛定諤方程：

(1)

式中，H代表Hamilton算子，φ表示波函數(shù)，V表示勢(shì)能函數(shù)，E表示算子H的相應(yīng)能量特征，▽代表劈型算子，方程中包含了唯一的參數(shù)δ。由該方程可知，如果兩個(gè)分布空間具有相同的勢(shì)場(chǎng)，則其粒子的分布狀態(tài)相同；如果將粒子所在的分布空間變換為一維無(wú)限深勢(shì)阱的狀態(tài)時(shí)，則它們將集中分布在勢(shì)能等于零的某一寬度勢(shì)阱內(nèi)，因此該勢(shì)能函數(shù)可以抽象地看成是一個(gè)源，當(dāng)勢(shì)能逐步減少至零時(shí)，將會(huì)有更多的粒子分布在勢(shì)阱內(nèi)。

反過來(lái)，由波函數(shù)φ則可以根據(jù)式(1)反推出來(lái)粒子分布的勢(shì)能函數(shù)：

(2)

研究表明，高斯函數(shù)是式(1)的一個(gè)有效解，是一個(gè)能夠有效代表粒子分布狀態(tài)的波函數(shù)。一個(gè)高斯波包形式如下：

(3)

假設(shè)某觀測(cè)樣本集為X={x1,x2,…,xi,…xn}?Rd，其中xi=(xi1,xi2,…xid)T∈Rd，則利用式(3)可將其分布表示成一個(gè)寬度為δ的高斯波包。特殊的，如果n=1，即空間里僅有一個(gè)粒子x1時(shí)，利用上述式(2)、式(3)可得到此時(shí)的勢(shì)能函數(shù)：

(4)

(5)

假設(shè)V值確定且非負(fù)，則其最小勢(shì)能值為零，由式(2)可得：

(6)

至此既可以計(jì)算出樣本的勢(shì)能。

對(duì)樣本集的聚類就相當(dāng)于將樣本都聚集在勢(shì)能為零或者最小的樣本附近，因此，勢(shì)能最小的樣本即為類中心。采用梯度下降法來(lái)求解，其迭代公式為：

yi(t+Δt)=yi(t)-n(t)▽V(yi(t))

(7)

其中，初始化變量為yi(0)=xi，學(xué)習(xí)速率為n(t)，勢(shì)能梯度為▽V。

對(duì)于算法中唯一的參數(shù)δ，我們根據(jù)高斯核寬度的參數(shù)估計(jì)法，采用式(8)來(lái)估計(jì)參數(shù)δ的值。

(8)

其中，m為樣本維數(shù)，n為樣本個(gè)數(shù)。這樣，樣本集的大小、維度等信息便隱含在了參數(shù)δ的計(jì)算中，從而將樣本集潛在的結(jié)構(gòu)信息隱含在了算法模型中，提高算法性能。

2 W-HAS-PEQC算法基本思想

W-HAS-PEQC算法首先動(dòng)態(tài)地維護(hù)各個(gè)數(shù)據(jù)流的小波摘要，然后利用所得到的各數(shù)據(jù)流小波摘要，結(jié)合改進(jìn)的量子聚類算法對(duì)其進(jìn)行在線聚類分析。

2.1 數(shù)據(jù)流的小波摘要結(jié)構(gòu)

遺忘特性是流數(shù)據(jù)所特有的性質(zhì)，利用這一特性，算法首先利用小波變換，采用動(dòng)態(tài)的方式不斷抽取出各條數(shù)據(jù)流的摘要信息，具體提取過程[8]如下：

將原始流數(shù)據(jù)中的各數(shù)據(jù)項(xiàng)視為第0層，當(dāng)數(shù)據(jù)項(xiàng)的數(shù)目達(dá)到m時(shí)，就對(duì)所收集的m個(gè)數(shù)據(jù)項(xiàng)進(jìn)行壓縮，形成第1層中的一個(gè)新數(shù)據(jù)項(xiàng)。伴隨原始流數(shù)據(jù)中各數(shù)據(jù)項(xiàng)的不斷抵達(dá)，第1層中的新數(shù)據(jù)項(xiàng)數(shù)目也逐漸增多，當(dāng)達(dá)到某一指定值后，就對(duì)最老的M個(gè)節(jié)點(diǎn)進(jìn)行歸并形成第2層上的1個(gè)新數(shù)據(jù)項(xiàng)。以此類推，便可構(gòu)造出原始數(shù)據(jù)流的一個(gè)小波誤差樹。由該誤差樹的構(gòu)造可知，層次越高的數(shù)據(jù)項(xiàng)節(jié)點(diǎn)所包含的原始數(shù)據(jù)越久遠(yuǎn)，且對(duì)應(yīng)的原始數(shù)據(jù)序列就越長(zhǎng)，因此所含原始流數(shù)據(jù)的信息就越粗糙，遺忘的程度就越大。

2.2 節(jié)點(diǎn)歸并

假設(shè)長(zhǎng)度為n(n為2的冪次)的兩個(gè)數(shù)據(jù)序列D1、D2，其小波分解得到的各數(shù)據(jù)節(jié)點(diǎn)，即小波系數(shù)為(c11,c12,…,c1n)和(c21,c22,…,c2n)，則由D1與D2串聯(lián)起來(lái)的子序列D1∪D2的小波系數(shù)(c1,c2,…,c2n)滿足：

(9)

2.3 聚類距離

數(shù)據(jù)流之間的近似距離為：

(10)

其中，S1、S2為任意兩個(gè)有q個(gè)數(shù)據(jù)節(jié)點(diǎn)構(gòu)成的數(shù)據(jù)流，d(P1j,P2j)為S1中第j個(gè)數(shù)據(jù)節(jié)點(diǎn)與S2中第j個(gè)數(shù)據(jù)節(jié)點(diǎn)之間的近似距離，這里任意兩節(jié)點(diǎn)之間的近似距離計(jì)算如下：

3 W-HAS-PEQC算法實(shí)現(xiàn)

3.1 小波摘要結(jié)構(gòu)的動(dòng)態(tài)維護(hù)

輸入：D，α，m，M，重構(gòu)誤差ε，遺忘函數(shù)b；

輸出：小波摘要結(jié)構(gòu)。

Begini0=0，j=0；

for新到達(dá)的數(shù)據(jù)項(xiàng)x

{i0=i0+1；x0=x；

ifi0≥m

{P=node(x1,x2,…,xm)；

iferror(P,b)<ε

//error(P,b)節(jié)點(diǎn)P的重構(gòu)誤差

{ifj=0

{i1=1；j=1；}

苗種是水產(chǎn)養(yǎng)殖的基礎(chǔ)，魚苗培育工作是水產(chǎn)養(yǎng)殖的基礎(chǔ)工作。做好魚苗培育工作，為后續(xù)養(yǎng)殖提供優(yōu)良的苗種，是保證養(yǎng)殖生產(chǎn)順利進(jìn)行的關(guān)鍵因素。下面筆者就魚苗培育過程中的關(guān)鍵技術(shù)要點(diǎn)介紹如下，供養(yǎng)殖戶參考。

xm+1,xm+2,…?x1,x2,…；

//為0層上余下的數(shù)據(jù)重新編號(hào)

}

fork=1:j

{ifik≥M

iferror(P,b)<ε

{ifk=j

{ik+1=1；j=j+1}

elseik+1=ik+1+1；

}

}

}

}

end

3.2 W-HAS-PEQC聚類算法

W-HAS-PEQC算法的主要步驟如下：

(1) 動(dòng)態(tài)維護(hù)小波摘要結(jié)構(gòu)。假設(shè)我們僅需考慮長(zhǎng)度為N的原始數(shù)據(jù)流序列，則在近似重構(gòu)原始數(shù)據(jù)序列時(shí)，要選取最近的q個(gè)數(shù)據(jù)節(jié)點(diǎn)，要求其包含的原始數(shù)據(jù)項(xiàng)要大于或者等于N；

(2) 規(guī)范化取出的q個(gè)數(shù)據(jù)節(jié)點(diǎn)的小波系數(shù)，由式(3)初始化樣本的分布狀態(tài)，根據(jù)式(8)估算出參數(shù)δ，并根據(jù)式(7)進(jìn)行算法迭代，找出類中心；

(3) 如果有新數(shù)據(jù)項(xiàng)到達(dá)，或者是有老數(shù)據(jù)項(xiàng)從數(shù)據(jù)流中刪除，則更新小波系數(shù)。每次聚類的初始化均采用前一次的聚類結(jié)果進(jìn)行。

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證算法的有效性，本文利用Matlab編程實(shí)現(xiàn)上述算法，并采用人工數(shù)據(jù)集與真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，人工數(shù)據(jù)集是利用隨機(jī)過程分別生成的4個(gè)類別互不相同的數(shù)據(jù)集組合而成，每個(gè)類均含有100條不同的數(shù)據(jù)流序列，該數(shù)據(jù)集在實(shí)驗(yàn)中，誤差樹所含的節(jié)點(diǎn)數(shù)目取q=4，小波系數(shù)的保留值取r=4。真實(shí)數(shù)據(jù)集采用Tickwise[10]，該數(shù)據(jù)集包含了1985年5月20日到1991年4月12日美元兌瑞士法郎的實(shí)時(shí)匯率，共329 112個(gè)數(shù)據(jù)項(xiàng)，為計(jì)算方便，選取前262 144個(gè)數(shù)據(jù)項(xiàng)構(gòu)成數(shù)據(jù)序列，另外為了驗(yàn)證并行數(shù)據(jù)流的聚類性能，我們又隨機(jī)生成4個(gè)各含100條不同數(shù)據(jù)流序列的并行數(shù)據(jù)流類：

p(t)=T(t)+p′(t)

p′(t+Δt)=p′(t)+u(t)

其中，T(t)為Tickwise數(shù)據(jù)序列，p(·)代表產(chǎn)生每一類數(shù)據(jù)流的隨機(jī)過程，u(t)為區(qū)間[-0.01,0.01]上服從均勻分布的獨(dú)立隨機(jī)變量。

為比較不同算法的聚類質(zhì)量，本文采用文獻(xiàn)[9]中Gavrilov等人提出的性能評(píng)估標(biāo)準(zhǔn)——“聚類相似度”作為算法評(píng)估指標(biāo)。該指標(biāo)客觀比較了聚類的結(jié)果與數(shù)據(jù)集本身的真實(shí)類標(biāo)簽，相似度值越大，表示聚類結(jié)果越接近數(shù)據(jù)的真實(shí)類別，聚類效果越好。具體的計(jì)算公式如下：

(11)

(12)

1) 基于誤差控制小波摘要結(jié)構(gòu)的數(shù)據(jù)流重構(gòu)實(shí)驗(yàn)

實(shí)驗(yàn)設(shè)置誤差樹第一層中的每個(gè)數(shù)據(jù)項(xiàng)由第0層中的128個(gè)數(shù)據(jù)項(xiàng)濃縮而得，且每個(gè)上層中的數(shù)據(jù)項(xiàng)均由其下層中對(duì)應(yīng)的2個(gè)數(shù)據(jù)項(xiàng)濃縮而得，將一個(gè)數(shù)據(jù)節(jié)點(diǎn)距離最頂層數(shù)據(jù)節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目的倒數(shù)作為衰減函數(shù)。圖2對(duì)比了兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，其中橫軸代表控制誤差ε，縱軸代表控制誤差≤ε所需要的數(shù)據(jù)節(jié)點(diǎn)數(shù)目。

圖2 小波摘要結(jié)構(gòu)的重構(gòu)

2) 不同聚類算法的對(duì)比

為驗(yàn)證文中算法，本文設(shè)置了兩個(gè)對(duì)比實(shí)驗(yàn)算法：一個(gè)是基于小波摘要的Kmeans聚類算法，記作W-HAS-Kmeans；一個(gè)是基于離散傅里葉變換的量子聚類算法，記作DFT-PEQC。圖3分別表示出了這3個(gè)算法在Tickwise數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從圖3中可以看出，相比于其他兩種方法，在數(shù)據(jù)節(jié)點(diǎn)中保留的各個(gè)不同的小波系數(shù)下，本文提出的算法取得了最好的聚類相似度值，W-HAS-Kmeans算法也取得了較好的聚類相似度，DFT-PEQC算法的聚類結(jié)果相對(duì)較差一些。

圖3 不同算法的實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)對(duì)比可以發(fā)現(xiàn)，基于小波變換的數(shù)據(jù)壓縮算法具有更加良好的性能，能夠在最小的誤差下保留原數(shù)據(jù)流的主要特征，同時(shí)該算法能夠去除數(shù)據(jù)流中的某些噪聲，有利于改善聚類質(zhì)量。另外，相比于Kmeans聚類算法，基于量子理論的量子聚類算法能夠在一定程度上克服Kmeans算法的固有缺陷，在多數(shù)據(jù)流的聚類上具有更為優(yōu)異的效果。

5 結(jié) 語(yǔ)

本文針對(duì)多數(shù)據(jù)流的聚類問題展開探討，設(shè)計(jì)出了一種新的數(shù)據(jù)流量子聚類算法。該算法充分考慮了數(shù)據(jù)流的遺忘特性，利用動(dòng)態(tài)維護(hù)的小波摘要結(jié)構(gòu)和改進(jìn)的量子聚類算法，對(duì)并行的多數(shù)據(jù)流進(jìn)行聚類分析。實(shí)驗(yàn)表明，所提方法在并行的多數(shù)據(jù)流聚類問題上表現(xiàn)出了更好的聚類性能。

[1]PapadimitriouS,SunJ,FaloutsosC.Streamingpatterndiscoveryinmultipletime-series[C]//Proceedingsofthe31stInternationalConferenceonVeryLargeDataBases,Trondheim,Norway,2005:697-708.

[2]DaiBR,HuangJW,YehMY,etal.Adaptiveclusteringformultipleevolvingstreams[J].IEEETransactionsonKnowledgeandDataEngineering,2006,18(9):1166-1180.

[3]YangJ.Dynamicclusteringofevolvingstreamswithasinglepass[C]//Proceedingsofthe19thInternationalConferenceonDataEngineering,Bangalore,India,2003:695-697.

[4]BeringerJ,HüllermeierE.Onlineclusteringofparalleldatastreams[J].DataandKnowledgeEngineering,2006,58(2):180-204.

[5]KeoghE,KasettyS.Ontheneedfortimeseriesdataminingbenchmarks:asurveyandempiricaldemonstration[J].DataMiningandKnowledgeDiscovery,2003,7(4):349-371.

[6] Abdulsalam H,Skillicorn D B,Martin P.Classification using streaming random forests[J].IEEE Transactions on Knowledge and Data Engineering,2011,23(1):22-36.

[7] Gilbert A C,Kotidis Y,Muthukrishnan S,et al.One-pass wavelet decompositions of data streams[J].IEEE Transactions on Knowledge and Data Engineering,2003,15(3):541-554.

[8] Chen H,Shi B,Qian J,et al.Wavelet synopsis based clustering of parallel data streams[J].Journal of Software,2010,21(4):644-658.

[9] Gavrilov M,Anguelov D,Indyk P,et al.Mining the stock market: which measure is best?[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.New York,NY,USA:ACM Press,2000:487-496.

[10] Tickwise數(shù)據(jù)集[DS/OL].http://www-psych.stanford.edu/～andreas/Time-Series/Data/.

A DATA STREAM QUANTUM CLUSTERING ALGORITHM BASED ON WAVELET SYNOPSIS

Mi Ying

(CollegeofInformationEngineering,DalianVocationalandTechnicalCollege,Dalian116035,Liaoning,China)

In view of the traditional clustering analysis technology, faced with the problem unlimited length and always changing mass data stream can’t be directly used or the use of defects, a new data stream quantum clustering algorithm is proposed based on the characteristics of data stream, combined with the wavelet transform and quantum theory. Firstly, the discrete wavelet transform is used to extract the profile structure from each data stream as its corresponding characteristic property, and calculate the approximate distance of each data stream to the clustering center. The optimal kernel width adjustment parameters are estimated by quantum theory, and an ideal clustering effect is obtained finally. Experiments show that the proposed algorithm can solve the problem of multiple data stream parallel clustering which can’t be solved by traditional clustering method, and show good clustering performance.

Multiple data stream clustering Wavelet transform Quantum potential energy

2016-04-10。米瀅，講師，主研領(lǐng)域：數(shù)據(jù)挖掘。

TP391.41

A

10.3969/j.issn.1000-386x.2017.05.050