交互基函數(shù)在數(shù)據(jù)流聚類(lèi)中的應(yīng)用

朱穎雯

（三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，南京210012）

0 引言

數(shù)據(jù)流聚類(lèi)已成為一個(gè)重要研究領(lǐng)域，其目標(biāo)是在無(wú)序和潛在的無(wú)限序列中發(fā)現(xiàn)模式。故存儲(chǔ)和隨機(jī)訪問(wèn)所有數(shù)據(jù)點(diǎn)均不可行。至今許多數(shù)據(jù)流聚類(lèi)算法被提出[1-17]，其均基于傳統(tǒng)的聚類(lèi)算法。可以將其分為5類(lèi)：基于劃分的方法（STREAM[1]）；基于層次的方法（CluStream[2]、HPStream[3]、SWClustering[4]、E-Stream[5]、REPSTREAM[6])；基于密度的方法（DenStream[7]、ACSC[8]、OPTICS-Stream[9]、incPre-Decon[10]）；基于網(wǎng)格的方法(D-Stream[11]、MR-Stream[12]、CellTree[13]）；基于模型的方法（SWEM[14]、GCPSOM[15]、G-Stream[16]、RPGStream[17]）。然而，這些算法均只考慮了特征與類(lèi)別之間的相關(guān)性，并無(wú)考慮特征交互，但特征交互在各類(lèi)學(xué)習(xí)任務(wù)中普遍存在。交互特征指的是那些特征與類(lèi)別單獨(dú)計(jì)算相關(guān)性時(shí)，表現(xiàn)為無(wú)關(guān)或極弱相關(guān)，但當(dāng)與其他特征聯(lián)合時(shí)，就可能與類(lèi)別表現(xiàn)出極大的相關(guān)性[18]。

基于此本文將交互基函數(shù)（Interactive Basis Func?tions）用于數(shù)據(jù)流聚類(lèi)以提高算法的聚類(lèi)精度。首先，對(duì)到達(dá)的數(shù)據(jù)點(diǎn)根據(jù)特征之間的相關(guān)性通過(guò)預(yù)計(jì)算函數(shù)特征擴(kuò)展，再進(jìn)行聚類(lèi)。交互基函數(shù)可生成靈活的決策邊界且不需要指定軟件，預(yù)計(jì)算函數(shù)可以在任何算法中實(shí)現(xiàn)，其可用于數(shù)據(jù)流聚類(lèi)算法的任何擴(kuò)展。

1 交互基函數(shù)

我們首先討論基函數(shù)，用于訓(xùn)練的特征構(gòu)成了基向量。例如，特征數(shù)p=2時(shí)，搜索空間即為特征正交軸構(gòu)成的平面。每個(gè)特征是一個(gè)基向量。三個(gè)特征構(gòu)成了一個(gè)3D基。如果把一個(gè)特征看作一個(gè)基向量，則基函數(shù)就是一個(gè)簡(jiǎn)單變換。最簡(jiǎn)單的情況，基函數(shù)可以是恒等式：

其為多項(xiàng)式函數(shù)特例，即當(dāng)a=1時(shí)：

其他基函數(shù)也可以定義為指數(shù)形式：

基函數(shù)通常用于回歸分析，在回歸分析中基函數(shù)具有改變回歸平面特性的作用。例如，從恒等到變量的平方的轉(zhuǎn)換會(huì)使回歸線變?yōu)閽佄锞€。本文將其用于聚類(lèi)分析，考慮K個(gè)候選實(shí)基函數(shù)bi：R→R，i=1,…,K。定義{b1,b2,…,bK}為一組基函數(shù)。利用此基函數(shù)增加T個(gè)新特征來(lái)放大p個(gè)特征集：

這里，X*∈Rp+T且Xp+i=bsi(Xji)，i=1,…,T，si∈{1,…,K}，ji∈{1,…,p}。考慮p=2，即X={X1,X2}。其中T=1，K=1，b1(x)=x2，則X*={X1,X2,X3=X12}。每當(dāng)劃分算法在X3中選擇一個(gè)分割s時(shí)，其在X上的投影為，為一個(gè)常數(shù)。因此，基函數(shù)維數(shù)上的任何分割都等價(jià)于在原始的基上找到一個(gè)正交的決策邊界。

由于基函數(shù)可在原始基中產(chǎn)生正交分區(qū)，我們的目標(biāo)是在構(gòu)造中使用交互基函數(shù)（IBFs）。這些相互作用可由一組D函數(shù)所識(shí)別，這些D函數(shù)體現(xiàn)了基函數(shù)的特征變換相互作用。定義交互函數(shù)為：

此設(shè)置下，定義：

因此，通過(guò)對(duì)X*應(yīng)用標(biāo)準(zhǔn)的遞歸劃分方法，其在X上的投影將提供一個(gè)傾斜的劃分（也可能是非線性劃分），考慮到了特征之間的相互作用。例如p=2，即X={X1,X2}，T=1，K=1，b1(x)=x，D=1，h1(b1(X1),b1(X2))=b1(X1)+b1(X2)=X1+X2，且X*={X1,X2,X3}我們得到X3=s被投影到原基的平面上，即X2=s-X1，從而在該平面上給出傾斜劃分。IBFs提供的框架除了傾斜分區(qū)外，還可引入非線性決策邊界，這是通過(guò)在子空間X=(X1,…,Xp)中投影hi(b1(X1),b1(X2),…,bK(Xp))=a生成。例如，h1(b1(X1),b1(X2))=b1(X1)b1(X2)，由b1(x)=x得到X1X2。固定了X1X2=s，因此X2=s/X1，從而創(chuàng)建了一個(gè)雙曲分割。

最后一個(gè)例子，h1(b1(X1),b1(X2))=b1(X1)+b1(X2)，b1(x)=x2導(dǎo) 致X12+X22。固定X12+X22=s，得到，從而形成一個(gè)徑向劃區(qū)。

2 數(shù)據(jù)流聚類(lèi)

設(shè)數(shù)據(jù)流DS為一個(gè)帶有時(shí)間戳（Time Stamp）的多維數(shù)據(jù)點(diǎn)集合，DS={x1,x2,…,xn}（實(shí)際應(yīng)用中n的取值可以為無(wú)限大），其中每個(gè)數(shù)據(jù)點(diǎn)xi=(xi1,xi2,…,xid)是一個(gè)d維的數(shù)據(jù)記錄，其到達(dá)時(shí)間為ti。數(shù)據(jù)流聚類(lèi)將數(shù)據(jù)DS中的相似對(duì)象劃分為一個(gè)或多個(gè)組（稱(chēng)為“簇”，Cluster），劃分后，同一簇中的元素彼此相似，但相異于其他簇中的元素。基于交互基函數(shù)相關(guān)理論，可以在使用數(shù)據(jù)流聚類(lèi)算法之前，首先對(duì)d維特征進(jìn)行擴(kuò)充，擴(kuò)充到d+T特征再進(jìn)行聚類(lèi)。此方法不僅對(duì)離線數(shù)據(jù)流聚類(lèi)適用對(duì)在線數(shù)據(jù)流聚類(lèi)也同樣適用。具體算法如下：

算法1.IBFs_DS算法.

輸入：DS={x1,x2,x3,…}；

輸出：節(jié)點(diǎn)集合C={c1,c2,c3,… 及其權(quán)值W={wc1,wc2,wc3,…,}．

①for eachxi

②使用式（6）構(gòu)造xi*;

③對(duì)xi*使用各種數(shù)據(jù)流聚類(lèi)算法進(jìn)行聚類(lèi)；

④end for

3 結(jié)語(yǔ)

本文將交互基函數(shù)（IBFs）用于數(shù)據(jù)流聚類(lèi)以提高算法的聚類(lèi)精度。首先，對(duì)到達(dá)的數(shù)據(jù)點(diǎn)根據(jù)特征之間的相關(guān)性通過(guò)預(yù)計(jì)算函數(shù)特征擴(kuò)展，再進(jìn)行聚類(lèi)。交互基函數(shù)可生成靈活的決策邊界且不需要指定軟件，預(yù)計(jì)算函數(shù)可以在任何算法中實(shí)現(xiàn)，其可用于數(shù)據(jù)流聚類(lèi)算法的任何擴(kuò)展。