米 瀅
(大連職業(yè)技術(shù)學(xué)院信息工程學(xué)院 遼寧 大連 116035)
一種基于小波概要的數(shù)據(jù)流量子聚類算法
米 瀅
(大連職業(yè)技術(shù)學(xué)院信息工程學(xué)院 遼寧 大連 116035)
針對傳統(tǒng)的聚類分析技術(shù)面對長度無限且隨時變化的海量級數(shù)據(jù)流無法直接使用或使用缺陷突出等問題,從數(shù)據(jù)流自身特性出發(fā),結(jié)合小波變換與量子理論,提出一種新的數(shù)據(jù)流量子聚類算法。該算法首先采用離散小波變換,從每個數(shù)據(jù)流中動態(tài)分層地提取出其概要結(jié)構(gòu)作為其相應(yīng)的特征屬性,同時計算出每個數(shù)據(jù)流到聚類中心的近似距離,結(jié)合量子理論估算出較優(yōu)的核寬度調(diào)節(jié)參數(shù)進(jìn)行類調(diào)整,最終獲得一個較為理想的聚類效果。實(shí)驗(yàn)表明,該算法較好地解決了傳統(tǒng)聚類方法無法良好解決的多數(shù)據(jù)流并行聚類問題,并表現(xiàn)出較好的聚類性能。
多數(shù)據(jù)流聚類 小波變換 量子勢能
隨著網(wǎng)絡(luò)通信、監(jiān)控、實(shí)時股票行情等領(lǐng)域的深入發(fā)展,數(shù)據(jù)挖掘領(lǐng)域中涌現(xiàn)出了許多連續(xù)不斷且隨時間變化而演變的序列型數(shù)據(jù),面對新的研究環(huán)境,數(shù)據(jù)挖掘的研究也迎來了新的挑戰(zhàn)。為此,研究者們紛紛提出了許多新的數(shù)據(jù)流聚類、分類、關(guān)聯(lián)挖掘等應(yīng)用算法。概括起來,可以分為兩個方面:第一,從單條數(shù)據(jù)流出發(fā)進(jìn)行挖掘,著重關(guān)注于不同時間段內(nèi)數(shù)據(jù)間的隱含信息;第二,對多條數(shù)據(jù)流的挖掘,主要關(guān)注于多條數(shù)據(jù)流之間的相關(guān)性。
針對多數(shù)據(jù)流的聚類問題,文獻(xiàn)[1]構(gòu)建SPIRIT算法來挖掘多條數(shù)據(jù)流之間的相關(guān)性,該算法利用主成分分析法,采用動態(tài)更新的策略不斷更新代表多數(shù)據(jù)流的隱藏變量及其權(quán)重;文獻(xiàn)[2]引入滯后相關(guān)性增量公式來發(fā)掘多條數(shù)據(jù)流之間滯后相關(guān)性的Braid算法;文獻(xiàn)[3]中,Yang利用概貌偏差(snapshot deviation)計算出兩個不同數(shù)據(jù)流間的加權(quán)聚合信息,以此來判斷各數(shù)據(jù)流間的相似性。文獻(xiàn)[4]中,Beringer等人首先利用離散傅里葉變換對原數(shù)據(jù)流進(jìn)行處理,得到其低頻分量,然后利用這些低頻分量的歐氏距離來評判數(shù)據(jù)流之間的相似性;文獻(xiàn)[5]引入“按需聚類( Clustering on Demand)”的概念,提出了ADAPTIVEclustering算法,該算法將多數(shù)據(jù)流聚類劃分為兩個階段:在線信息的統(tǒng)計與維護(hù)、離線的自適應(yīng)聚類。這些算法在某種程度上解決了傳統(tǒng)挖掘算法的一定缺陷問題,但大都忽視了數(shù)據(jù)流的遺忘特性。在數(shù)據(jù)流中,人們往往會遺忘掉比較久遠(yuǎn)的數(shù)據(jù)或者僅需了解久遠(yuǎn)數(shù)據(jù)的大略概況,而更多關(guān)注于數(shù)據(jù)流中的近期數(shù)據(jù),以及近期數(shù)據(jù)的細(xì)節(jié)信息。另外,現(xiàn)存的算法大都采用活動窗口技術(shù),且認(rèn)為窗口中的數(shù)據(jù)可以重復(fù)存取,于是產(chǎn)生了較大存儲與計算的代價需求。
針對這些問題,本文充分分析了數(shù)據(jù)流的遺忘特性,引入隨時間推薦而衰減的影響因子來標(biāo)注數(shù)據(jù)流中不同數(shù)據(jù)的影響力,采用離散小波變換DWT(discrete wavelet transform)適度地壓縮海量數(shù)據(jù)流。然后結(jié)合量子理論,利用改進(jìn)的量子聚類算法對用概要結(jié)構(gòu)表示的一組并行數(shù)據(jù)流進(jìn)行聚類分析。本文將該算法稱為W-HAS-PEQC。通過實(shí)驗(yàn)對比表明,該算法不僅解決了傳統(tǒng)聚類方法無法較好解決的多數(shù)據(jù)流并行聚類問題,而且在多數(shù)據(jù)流聚類問題上表現(xiàn)出良好的性能。
1.1 數(shù)據(jù)的小波壓縮
面對海量級規(guī)模的數(shù)據(jù)流,在對其進(jìn)行分析前先進(jìn)行數(shù)據(jù)壓縮處理是很有必要的。在數(shù)據(jù)壓縮處理中,DWT[7]技術(shù)以其優(yōu)異的特性越來越受研究者們的青睞,尤其是Haar小波變換,作為DWT技術(shù)中最簡單的一種,憑借著它簡單、易實(shí)現(xiàn)且有效的優(yōu)異特性得到了廣泛的應(yīng)用。
利用一維Haar小波變換,可以將向量D=(x1,x2,…,xn)分解表示為n個小波系數(shù)(c1,c2,…,cn),我們使用一個簡單的實(shí)例來說明Haar小波變換。
例:假設(shè)某一數(shù)據(jù)序列D=(9,5,6,4,4,4,5,7)(n=8),對其進(jìn)行Haar小波變換,具體過程如表1所示。
表1 序列D的Haar小波變換
本例中,小波層次由表1中的Resolution列中的l值表示,原始數(shù)據(jù)序列存儲在l=3這一層次的Averages列中,將原數(shù)據(jù)序列中的數(shù)據(jù)項(xiàng)兩兩組對,求其均值記為l=2中的Averages值,即:((9+5)/2,(6+4)/2,(4+4)/2,(5+7)/2)=(7,5,4,6),經(jīng)過這一變換后,原數(shù)據(jù)序列的8個數(shù)據(jù)項(xiàng)將被壓縮成4個數(shù)據(jù)項(xiàng),顯然丟失了原始數(shù)據(jù)序列中的某些數(shù)據(jù)信息。為了能夠重新構(gòu)造出原始數(shù)據(jù)序列集,我們在保存組合后的數(shù)據(jù)對均值的同時,將該均值與原組對中第2個數(shù)據(jù)項(xiàng)之差也保存起來。表1中Detailcoefficients列即為數(shù)據(jù)對均值與原組對中第2個數(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)來表示該分解過程,如圖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)可劃分為左右兩個子集合:左子樹葉節(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為一符號函數(shù):
比如x2=+5.5+0.5+1-2=5,由此便可以重構(gòu)出原始數(shù)據(jù)序列集。
圖1 序列D的誤差樹
1.2 基于參數(shù)估計的量子聚類
以粒子在量子空間中的分布為主要研究對象的量子力學(xué)在數(shù)據(jù)挖掘領(lǐng)域里得到了越來越多的應(yīng)用,尤其是在聚類分析技術(shù)中,近年來,許多學(xué)者都開始著手研究量子聚類算法[6]的研究。
量子理論中,粒子的分布狀態(tài)采用概率波函數(shù)描述,對其求解常采用有勢場約束的薛定諤方程:
(1)
式中,H代表Hamilton算子,φ表示波函數(shù),V表示勢能函數(shù),E表示算子H的相應(yīng)能量特征,▽代表劈型算子,方程中包含了唯一的參數(shù)δ。由該方程可知,如果兩個分布空間具有相同的勢場,則其粒子的分布狀態(tài)相同;如果將粒子所在的分布空間變換為一維無限深勢阱的狀態(tài)時,則它們將集中分布在勢能等于零的某一寬度勢阱內(nèi),因此該勢能函數(shù)可以抽象地看成是一個源,當(dāng)勢能逐步減少至零時,將會有更多的粒子分布在勢阱內(nèi)。
反過來,由波函數(shù)φ則可以根據(jù)式(1)反推出來粒子分布的勢能函數(shù):
(2)
研究表明,高斯函數(shù)是式(1)的一個有效解,是一個能夠有效代表粒子分布狀態(tài)的波函數(shù)。一個高斯波包形式如下:
(3)
假設(shè)某觀測樣本集為X={x1,x2,…,xi,…xn}?Rd,其中xi=(xi1,xi2,…xid)T∈Rd,則利用式(3)可將其分布表示成一個寬度為δ的高斯波包。特殊的,如果n=1,即空間里僅有一個粒子x1時,利用上述式(2)、式(3)可得到此時的勢能函數(shù):
(4)
(5)
假設(shè)V值確定且非負(fù),則其最小勢能值為零,由式(2)可得:
(6)
至此既可以計算出樣本的勢能。
對樣本集的聚類就相當(dāng)于將樣本都聚集在勢能為零或者最小的樣本附近,因此,勢能最小的樣本即為類中心。采用梯度下降法來求解,其迭代公式為:
yi(t+Δt)=yi(t)-n(t)▽V(yi(t))
(7)
其中,初始化變量為yi(0)=xi,學(xué)習(xí)速率為n(t),勢能梯度為▽V。
對于算法中唯一的參數(shù)δ,我們根據(jù)高斯核寬度的參數(shù)估計法,采用式(8)來估計參數(shù)δ的值。
(8)
其中,m為樣本維數(shù),n為樣本個數(shù)。這樣,樣本集的大小、維度等信息便隱含在了參數(shù)δ的計算中,從而將樣本集潛在的結(jié)構(gòu)信息隱含在了算法模型中,提高算法性能。
W-HAS-PEQC算法首先動態(tài)地維護(hù)各個數(shù)據(jù)流的小波摘要,然后利用所得到的各數(shù)據(jù)流小波摘要,結(jié)合改進(jìn)的量子聚類算法對其進(jìn)行在線聚類分析。
2.1 數(shù)據(jù)流的小波摘要結(jié)構(gòu)
遺忘特性是流數(shù)據(jù)所特有的性質(zhì),利用這一特性,算法首先利用小波變換,采用動態(tài)的方式不斷抽取出各條數(shù)據(jù)流的摘要信息,具體提取過程[8]如下:
將原始流數(shù)據(jù)中的各數(shù)據(jù)項(xiàng)視為第0層,當(dāng)數(shù)據(jù)項(xiàng)的數(shù)目達(dá)到m時,就對所收集的m個數(shù)據(jù)項(xiàng)進(jìn)行壓縮,形成第1層中的一個新數(shù)據(jù)項(xiàng)。伴隨原始流數(shù)據(jù)中各數(shù)據(jù)項(xiàng)的不斷抵達(dá),第1層中的新數(shù)據(jù)項(xiàng)數(shù)目也逐漸增多,當(dāng)達(dá)到某一指定值后,就對最老的M個節(jié)點(diǎn)進(jìn)行歸并形成第2層上的1個新數(shù)據(jù)項(xiàng)。以此類推,便可構(gòu)造出原始數(shù)據(jù)流的一個小波誤差樹。由該誤差樹的構(gòu)造可知,層次越高的數(shù)據(jù)項(xiàng)節(jié)點(diǎn)所包含的原始數(shù)據(jù)越久遠(yuǎn),且對應(yīng)的原始數(shù)據(jù)序列就越長,因此所含原始流數(shù)據(jù)的信息就越粗糙,遺忘的程度就越大。
2.2 節(jié)點(diǎn)歸并
假設(shè)長度為n(n為2的冪次)的兩個數(shù)據(jù)序列D1、D2,其小波分解得到的各數(shù)據(jù)節(jié)點(diǎn),即小波系數(shù)為(c11,c12,…,c1n)和(c21,c22,…,c2n),則由D1與D2串聯(lián)起來的子序列D1∪D2的小波系數(shù)(c1,c2,…,c2n)滿足:
(9)
2.3 聚類距離
數(shù)據(jù)流之間的近似距離為:
(10)
其中,S1、S2為任意兩個有q個數(shù)據(jù)節(jié)點(diǎn)構(gòu)成的數(shù)據(jù)流,d(P1j,P2j)為S1中第j個數(shù)據(jù)節(jié)點(diǎn)與S2中第j個數(shù)據(jù)節(jié)點(diǎn)之間的近似距離,這里任意兩節(jié)點(diǎn)之間的近似距離計算如下:
3.1 小波摘要結(jié)構(gòu)的動態(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ù)重新編號
}
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) 動態(tài)維護(hù)小波摘要結(jié)構(gòu)。假設(shè)我們僅需考慮長度為N的原始數(shù)據(jù)流序列,則在近似重構(gòu)原始數(shù)據(jù)序列時,要選取最近的q個數(shù)據(jù)節(jié)點(diǎn),要求其包含的原始數(shù)據(jù)項(xiàng)要大于或者等于N;
(2) 規(guī)范化取出的q個數(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)行。
為驗(yàn)證算法的有效性,本文利用Matlab編程實(shí)現(xiàn)上述算法,并采用人工數(shù)據(jù)集與真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中,人工數(shù)據(jù)集是利用隨機(jī)過程分別生成的4個類別互不相同的數(shù)據(jù)集組合而成,每個類均含有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í)時匯率,共329 112個數(shù)據(jù)項(xiàng),為計算方便,選取前262 144個數(shù)據(jù)項(xiàng)構(gòu)成數(shù)據(jù)序列,另外為了驗(yàn)證并行數(shù)據(jù)流的聚類性能,我們又隨機(jī)生成4個各含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等人提出的性能評估標(biāo)準(zhǔn)——“聚類相似度”作為算法評估指標(biāo)。該指標(biāo)客觀比較了聚類的結(jié)果與數(shù)據(jù)集本身的真實(shí)類標(biāo)簽,相似度值越大,表示聚類結(jié)果越接近數(shù)據(jù)的真實(shí)類別,聚類效果越好。具體的計算公式如下:
(11)
(12)
1) 基于誤差控制小波摘要結(jié)構(gòu)的數(shù)據(jù)流重構(gòu)實(shí)驗(yàn)
實(shí)驗(yàn)設(shè)置誤差樹第一層中的每個數(shù)據(jù)項(xiàng)由第0層中的128個數(shù)據(jù)項(xiàng)濃縮而得,且每個上層中的數(shù)據(jù)項(xiàng)均由其下層中對應(yīng)的2個數(shù)據(jù)項(xiàng)濃縮而得,將一個數(shù)據(jù)節(jié)點(diǎn)距離最頂層數(shù)據(jù)節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目的倒數(shù)作為衰減函數(shù)。圖2對比了兩個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果,其中橫軸代表控制誤差ε,縱軸代表控制誤差≤ε所需要的數(shù)據(jù)節(jié)點(diǎn)數(shù)目。
圖2 小波摘要結(jié)構(gòu)的重構(gòu)
2) 不同聚類算法的對比
為驗(yàn)證文中算法,本文設(shè)置了兩個對比實(shí)驗(yàn)算法:一個是基于小波摘要的Kmeans聚類算法,記作W-HAS-Kmeans;一個是基于離散傅里葉變換的量子聚類算法,記作DFT-PEQC。圖3分別表示出了這3個算法在Tickwise數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從圖3中可以看出,相比于其他兩種方法,在數(shù)據(jù)節(jié)點(diǎn)中保留的各個不同的小波系數(shù)下,本文提出的算法取得了最好的聚類相似度值,W-HAS-Kmeans算法也取得了較好的聚類相似度,DFT-PEQC算法的聚類結(jié)果相對較差一些。
圖3 不同算法的實(shí)驗(yàn)結(jié)果
通過實(shí)驗(yàn)對比可以發(fā)現(xiàn),基于小波變換的數(shù)據(jù)壓縮算法具有更加良好的性能,能夠在最小的誤差下保留原數(shù)據(jù)流的主要特征,同時該算法能夠去除數(shù)據(jù)流中的某些噪聲,有利于改善聚類質(zhì)量。另外,相比于Kmeans聚類算法,基于量子理論的量子聚類算法能夠在一定程度上克服Kmeans算法的固有缺陷,在多數(shù)據(jù)流的聚類上具有更為優(yōu)異的效果。
本文針對多數(shù)據(jù)流的聚類問題展開探討,設(shè)計出了一種新的數(shù)據(jù)流量子聚類算法。該算法充分考慮了數(shù)據(jù)流的遺忘特性,利用動態(tài)維護(hù)的小波摘要結(jié)構(gòu)和改進(jìn)的量子聚類算法,對并行的多數(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