交互基函數在數據流聚類中的應用

朱穎雯

（三江學院計算機科學與工程學院，南京210012）

0 引言

數據流聚類已成為一個重要研究領域，其目標是在無序和潛在的無限序列中發現模式。故存儲和隨機訪問所有數據點均不可行。至今許多數據流聚類算法被提出[1-17]，其均基于傳統的聚類算法?？梢詫⑵浞譃?類：基于劃分的方法（STREAM[1]）；基于層次的方法（CluStream[2]、HPStream[3]、SWClustering[4]、E-Stream[5]、REPSTREAM[6])；基于密度的方法（DenStream[7]、ACSC[8]、OPTICS-Stream[9]、incPre-Decon[10]）；基于網格的方法(D-Stream[11]、MR-Stream[12]、CellTree[13]）；基于模型的方法（SWEM[14]、GCPSOM[15]、G-Stream[16]、RPGStream[17]）。然而，這些算法均只考慮了特征與類別之間的相關性，并無考慮特征交互，但特征交互在各類學習任務中普遍存在。交互特征指的是那些特征與類別單獨計算相關性時，表現為無關或極弱相關，但當與其他特征聯合時，就可能與類別表現出極大的相關性[18]。

基于此本文將交互基函數（Interactive Basis Func?tions）用于數據流聚類以提高算法的聚類精度。首先，對到達的數據點根據特征之間的相關性通過預計算函數特征擴展，再進行聚類。交互基函數可生成靈活的決策邊界且不需要指定軟件，預計算函數可以在任何算法中實現，其可用于數據流聚類算法的任何擴展。

1 交互基函數

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

其為多項式函數特例，即當a=1時：

其他基函數也可以定義為指數形式：

基函數通常用于回歸分析，在回歸分析中基函數具有改變回歸平面特性的作用。例如，從恒等到變量的平方的轉換會使回歸線變為拋物線。本文將其用于聚類分析，考慮K個候選實基函數bi：R→R，i=1,…,K。定義{b1,b2,…,bK}為一組基函數。利用此基函數增加T個新特征來放大p個特征集：

這里，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}。每當劃分算法在X3中選擇一個分割s時，其在X上的投影為，為一個常數。因此，基函數維數上的任何分割都等價于在原始的基上找到一個正交的決策邊界。

由于基函數可在原始基中產生正交分區，我們的目標是在構造中使用交互基函數（IBFs）。這些相互作用可由一組D函數所識別，這些D函數體現了基函數的特征變換相互作用。定義交互函數為：

此設置下，定義：

因此，通過對X*應用標準的遞歸劃分方法，其在X上的投影將提供一個傾斜的劃分（也可能是非線性劃分），考慮到了特征之間的相互作用。例如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提供的框架除了傾斜分區外，還可引入非線性決策邊界，這是通過在子空間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，從而創建了一個雙曲分割。

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

2 數據流聚類

設數據流DS為一個帶有時間戳（Time Stamp）的多維數據點集合，DS={x1,x2,…,xn}（實際應用中n的取值可以為無限大），其中每個數據點xi=(xi1,xi2,…,xid)是一個d維的數據記錄，其到達時間為ti。數據流聚類將數據DS中的相似對象劃分為一個或多個組（稱為“簇”，Cluster），劃分后，同一簇中的元素彼此相似，但相異于其他簇中的元素?；诮换セ瘮迪嚓P理論，可以在使用數據流聚類算法之前，首先對d維特征進行擴充，擴充到d+T特征再進行聚類。此方法不僅對離線數據流聚類適用對在線數據流聚類也同樣適用。具體算法如下：

算法1.IBFs_DS算法.

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

輸出：節點集合C={c1,c2,c3,… 及其權值W={wc1,wc2,wc3,…,}．

①for eachxi

②使用式（6）構造xi*;

③對xi*使用各種數據流聚類算法進行聚類；

④end for

3 結語

本文將交互基函數（IBFs）用于數據流聚類以提高算法的聚類精度。首先，對到達的數據點根據特征之間的相關性通過預計算函數特征擴展，再進行聚類。交互基函數可生成靈活的決策邊界且不需要指定軟件，預計算函數可以在任何算法中實現，其可用于數據流聚類算法的任何擴展。