基于廣義線性模型的混合屬性數(shù)據(jù)聚類方法

朱永杰

(許昌學院信息化管理中心, 許昌 461099)

現(xiàn)代信息技術日新月異,社會各領域產(chǎn)生大量數(shù)據(jù)信息,可使用數(shù)據(jù)挖掘技術從海量數(shù)據(jù)中得到有效信息。數(shù)據(jù)聚類是一種使用頻率較高的數(shù)據(jù)挖掘技術,在商品營銷、圖像處理、數(shù)據(jù)分析等領域應用較廣[1]。實際應用中,可根據(jù)數(shù)據(jù)具體情況選擇聚類方法。以混合屬性數(shù)據(jù)為例,與單種屬性數(shù)據(jù)不同,混合屬性數(shù)據(jù)包含多種屬性,如數(shù)值屬性、符號屬性、時間屬性等[2]。由于屬性種類較多,算法進行聚類過程中需通過轉(zhuǎn)換方式將數(shù)據(jù)屬性統(tǒng)一,屬性轉(zhuǎn)換過程復雜,容易降低算法聚類準確度。中外不少專家學者對混合屬性數(shù)據(jù)聚類方法進行了研究,并取得了較好的研究成果。黃德才等[3]提出了混合屬性數(shù)據(jù)流的二重k近鄰聚類算法。采用二重k近鄰和改進的維度距離形成數(shù)據(jù)的微聚類,根據(jù)均值的余弦模型以及動態(tài)標準化數(shù)據(jù)方法生成初始宏聚類,通過基于均值的余弦模型和先驗聚類結(jié)果進行宏聚類優(yōu)化,以實現(xiàn)混合屬性數(shù)據(jù)的聚類,但是該方法存在聚類適應度較低的問題。Skabar[4]提出了一種基于隨機漫步的混合屬性數(shù)據(jù)聚類方法，該方法不需要任何顯式的相似性或距離度量,就能夠?qū)崿F(xiàn)混合屬性數(shù)據(jù)聚類,但是該方法存在迭代收斂速度較快的問題?，F(xiàn)針對現(xiàn)有方法存在的問題,提出一種基于廣義線性模型的混合屬性數(shù)據(jù)聚類方法。引入低階多元廣義線性模型考慮數(shù)據(jù)屬性時間特性,構(gòu)建屬性時間序列矩陣。用優(yōu)化方法計算數(shù)據(jù)相異度、樣本與聚類集間距離,當聚類結(jié)果趨于平穩(wěn)時終止運算,輸出聚類結(jié)果。通過此過程能夠有效提高聚類適應度,提高聚類算法準確度,是提升混合屬性數(shù)據(jù)聚類性能最為有效的途徑。

1 混合屬性數(shù)據(jù)聚類方法

1.1 低階多元廣義線性模型構(gòu)建

定義yq(t)為混合數(shù)據(jù)屬性的時間序列,混合數(shù)據(jù)屬性聚類過程中,構(gòu)建廣義線性模型為

yq(t)=d(t)γq+

(1)

式(1)中:

φq為a維列向量；d(t)γq為數(shù)據(jù)屬性混合導致的數(shù)據(jù)低頻漂移；s(t)表示混合屬性數(shù)據(jù)響應函數(shù)；K表示廣義線性模型特征量指數(shù)；b(t-e)表示刺激函數(shù)。

采用廣義線性模型完成混合數(shù)據(jù)聚類,可同時處理大量數(shù)據(jù),提供更多的時間信息致使數(shù)據(jù)噪聲干擾降低[5]?；旌蠈傩詳?shù)據(jù)的響應函數(shù)存在差異,因此采用B-樣條插值方法擬合混合數(shù)據(jù)的響應函數(shù)[6],過程為

(2)

式(2)中：gk(t)和zl,k(q)分別表示B樣條基函數(shù)與未知系數(shù)；sk(q)表示擬合混合數(shù)據(jù)的響應函數(shù)。

(3)

混合屬性數(shù)據(jù)的特征信息全部體現(xiàn)在系數(shù)矩陣Qk,q中,采用最小二乘法求解即可。值得注意的是,廣義線性模型參數(shù)多、混合屬性數(shù)據(jù)信噪比低的特點導致最小二乘法求解結(jié)果變異概率高,將Qk,q變換成低階矩陣相乘的方式解決該問題,具體過程如下:令Qk,q=Ek,qGk,q,Ek,q、Gk,q表示低階矩陣,維數(shù)為L×P、P×D,P取值為2,變換后的形式體現(xiàn)了混合屬性數(shù)據(jù)的時間特性[7]?；旌蠈傩詳?shù)據(jù)聚類研究的是混合屬性,所以模型的誤入項應考慮到屬性間的差異[8],據(jù)此擴展廣義線性模型為低階多元廣義線性模型,即

(4)

相比單一的廣義線性模型而言,低階多元廣義線性模型存在以下優(yōu)點:①可處理混合屬性數(shù)據(jù)的聚類問題,使用領域擴大[9]；②考慮了混合屬性數(shù)據(jù)的時間特性,可處理大量混合屬性信息,降低數(shù)據(jù)噪聲，同時改善了聚類算法的聚類精度[10]；③在低階多元廣義線性模型中,設置Ek,q矩陣為定值,對比Gk,q矩陣即完成混合屬性數(shù)據(jù)響應函數(shù)的對比。

混合屬性數(shù)據(jù)聚類過程中,應用到考慮時間特性屬性的時間序列矩陣,可改善聚類算法精確度,詳細聚類過程如下。

1.2 基于優(yōu)化K-prototypes的混合屬性數(shù)據(jù)聚類

由于基于K-prototypes的混合屬性數(shù)據(jù)聚類方法[11]存在迭代收斂速度快、聚類精度低的問題,因此要對該方法進行優(yōu)化。優(yōu)化的K-prototypes混合屬性數(shù)據(jù)聚類原理如下:首先,定義Xi(i=1,2,…,n)表示樣本數(shù)據(jù)集,A1,A2,…,Ak表示聚類集,數(shù)據(jù)迭代過程中計算Xi與聚類集間的距離,將距離值最小的數(shù)據(jù)樣本歸類至聚類集內(nèi)；其次,優(yōu)化聚類及數(shù)值屬性均值與分類屬性值計數(shù)器,為獲取聚類代價函數(shù)J(X,G)的最小值,迭代完成后更新分類屬性模式。優(yōu)化K-prototypes混合屬性數(shù)據(jù)聚類算法考慮了屬性的時間序列矩陣,可提高聚類精度,由此得到優(yōu)化的相異度計算方法,樣本分類屬性值和聚類集內(nèi)非未知樣本屬性值的不匹配概率和即為相異度[12],式(5)、式(6)分別為樣本與聚類集間的距離計算方法,結(jié)合式(5)、式(6)獲取分類屬性距離計算結(jié)果。

μ(Xij,Aij)=1-|Alij|/|Al|Yq;μ∈[0,1]

(5)

(6)

式中：Al表示已有樣本數(shù)量；|Alij|表示可分類樣本Xi在分類Al內(nèi)出現(xiàn)的頻率；Yq為樣本分類屬性的時間序列矩陣；d(Xi,Al)為樣本Xi與聚類集Al間的距離；Glj表示聚類集Al的數(shù)值屬性均值。

定義以下參數(shù):X={X1,X2,X3,…,X10},G={G1,G2,G3},G1=X7,G2=X2,G3=X5,A={A1,A2,A3},A1=[7,0,…,0],A2=[2,0,…,0],A3=[5,0,…,0]。K-prototypes算法聚類過程如圖1所示,優(yōu)化K-prototypes聚類算法如圖2所示。

圖1 K-prototypes聚類算法Fig.1 K-Prototypes clustering algorithm

圖2 優(yōu)化K-prototypes聚類算法Fig.2 Optimized K-Prototypes clustering algorithm

分析圖1可知,K-prototypes聚類算法迭代過程中,混合數(shù)據(jù)樣本同聚類中心距離決定了數(shù)據(jù)樣本的聚類[13]。圖2信息表明,優(yōu)化K-prototypes聚類算法在考慮樣本同聚類中心距離基礎上兼顧已知樣本信息內(nèi)容和屬性的時間序列矩陣。詳細分析圖2中的樣本X10,采用K-prototypes聚類算法得到以下形式:d(X10,G1)≥d(X10,G2)≥d(X10,G3),據(jù)此歸類X10至A3。采用優(yōu)化K-prototypes聚類算法獲取上述3個樣本到聚類中心的距離,根據(jù)距離最小原理歸納X10至A2。原因分析如下:根據(jù)圖1和圖2中樣本節(jié)點排列情況可知，X10至X2距離等于X10至X5的距離,歸納X10至A2更合理是因為樣本X3與X6存在A2內(nèi)?？偨Y(jié)優(yōu)化K-prototypes算法聚類過程如下。

步驟1已知聚類數(shù)量為k,聚類集A的原始聚類中心樣本是隨機選擇的原始節(jié)點G={G1,G2,…,Gk},那么A1={G1},…,Ak={Gk},同時定義η表示分類屬性的權(quán)重值。

步驟2存在Xi(1≤i≤n,Xi≠Gj,j=1,2,…,k),與聚類集的距離表示為d(Xi,Al)。p表示聚類集元素計數(shù)器,設定p的初始值為1,歸納Xi至聚類集Amin中,Amin為距離最小的聚類集,若計數(shù)器值增加1,說明聚類運算了1次,用參數(shù)表示為Amin·p=i,p=p+1,新樣本加入后,需再次計算聚類集Amin的數(shù)據(jù)屬性均值,據(jù)此調(diào)整分類屬性值計數(shù)器內(nèi)容。

步驟3根據(jù)數(shù)據(jù)的混合屬性差異獲取聚類集原始聚類中心樣本[14],原則為:數(shù)值型屬性取聚類元素均值,分類型屬性取聚類樣本的分類屬性中頻繁出現(xiàn)的值。

步驟4各迭代目標函數(shù)值可依據(jù)目標函數(shù)公式(7)計算，即

(7)

式(7)中：若eil為1,說明Al包含樣本Xi；若eil為0,說明Al不包含樣本Xi。

步驟5循環(huán)操作步驟2～步驟4,采用固定的迭代目標函數(shù)值,當聚類結(jié)果趨于平穩(wěn)時終止運算[15],輸出聚類結(jié)果。

采用廣義線性模型與優(yōu)化K-prototypes聚類算法結(jié)合的方法完成混合屬性數(shù)據(jù)聚類[16],有效提升聚類算法處理混合屬性數(shù)據(jù)的準確度。

2 實驗分析

為驗證本文方法對于混合屬性數(shù)據(jù)的聚類優(yōu)勢,將文本數(shù)據(jù)作為混合屬性聚類的樣本數(shù)據(jù),展開混合屬性數(shù)據(jù)聚類分析測試。實驗環(huán)境如下。①硬件環(huán)境:Inter(R) Corel(TM) Duo 2.00GHz CPU,內(nèi)存為8 GB,使用Windows 10操作系統(tǒng)；②實驗對比方法:K-prototypes數(shù)據(jù)聚類方法、二重K近鄰聚類方法；③實驗數(shù)據(jù)使用權(quán)威數(shù)據(jù)平臺提供的語言詞匯表,分為測試集A(包含5×102個混合屬性數(shù)據(jù))、測試集B(包含2×103個混合屬性數(shù)據(jù))與測試集C(包含5×103個混合屬性數(shù)據(jù)),部分混合屬性數(shù)據(jù)如表1所示。表1中,數(shù)據(jù)的混合屬性包括分類屬性與數(shù)值屬性,分類屬性為“渠道”“范疇”,數(shù)值屬性為“時間”。

2.1 聚類方法性能對比

本次測試在數(shù)據(jù)量不同的測試集A、B、C中進行,不同方法混合屬性數(shù)據(jù)聚類性能如表2所示。

表1 語言詞匯

表2數(shù)據(jù)顯示:在不同數(shù)據(jù)量的數(shù)據(jù)集聚類測試中,本文方法迭代時間在1 s左右、迭代次數(shù)約為21次,上下波動小,均優(yōu)于其他兩種聚類方法；本文方法進行混合屬性數(shù)據(jù)聚類準確度均高于99.6%,不隨數(shù)據(jù)量增加而降低,K-prototypes數(shù)據(jù)聚類方法、二重K近鄰聚類方法聚類準確度隨數(shù)據(jù)量增加而降低的趨勢較明顯；另外,3種方法最優(yōu)解原始樣本組數(shù)量均隨測試集數(shù)據(jù)量的增加而增長,本文方法聚類后,得到最優(yōu)解的原始樣本組數(shù)量均高于其他兩種方法。綜上所述，本文方法進行混合屬性數(shù)據(jù)聚類性能優(yōu)于同類方法,之后詳細分析本文聚類方法的具體優(yōu)勢。

2.2 平均目標函數(shù)值分析

采用本文方法在內(nèi)的3種聚類方法進行混合屬性數(shù)據(jù)聚類測試,3種方法聚類平均目標函數(shù)值與迭代次數(shù)關系如圖3所示。

圖3數(shù)據(jù)表明:3種聚類方法處理混合屬性數(shù)據(jù)過程中,平均目標函數(shù)值均與迭代次數(shù)呈反比例關系；迭代次數(shù)一定時,本文方法的平均目標函數(shù)值最低,另外兩種方法均高于本文方法,由于平均目標函數(shù)值越低，聚類精度越高,所以本文方法的聚類精度優(yōu)于K-prototypes數(shù)據(jù)聚類方法、二重K近鄰聚類方法；另外,由測試過程可知,迭代次數(shù)為20～30時,本文方法優(yōu)化劃分聚類集,迭代次數(shù)為30～42時,K-prototypes數(shù)據(jù)聚類方法優(yōu)化劃分聚類集,迭代次數(shù)為38～48時,二重K近鄰聚類方法優(yōu)化劃分聚類集,相比之下,本文方法僅使用較少的迭代次數(shù)即可優(yōu)化劃分混合屬性數(shù)據(jù)的聚類集,說明本文方法效率較高。

圖3 平均目標函數(shù)值與迭代次數(shù)關系Fig.3 Relationship between average objective function value and iteration times

由于本文方法對混合屬性數(shù)據(jù)進行聚類過程中,考慮到聚類集中的已有樣本數(shù)據(jù),所以減少了迭代分析次數(shù),提高數(shù)據(jù)聚類效率,這也是本文方法相對同類型K-prototypes數(shù)據(jù)聚類方法的優(yōu)化與改進之處。

2.3 原始樣本數(shù)量與迭代次數(shù)關系分析

迭代次數(shù)影響混合屬性數(shù)據(jù)聚類效果,2.2節(jié)實驗對迭代次數(shù)與聚類方法的平均目標函數(shù)值關系進行分析,為全面掌握迭代次數(shù)對聚類效果的影響與干擾,本次實驗測試聚類方法迭代次數(shù)與最優(yōu)解原始樣本組數(shù)量的關系,測試結(jié)果如圖4所示。

分析圖4可知,迭代次數(shù)一定時,本文方法得到最優(yōu)解樣本數(shù)量大于K-prototypes數(shù)據(jù)聚類方法、二重K近鄰聚類方法,以迭代次數(shù)20次為例,本文方法有55個原始樣本組達到最優(yōu)解,K-prototypes數(shù)據(jù)聚類方法有33個原始樣本組達到最優(yōu)解,二重K近鄰聚類方法有23個原始樣本組達到最優(yōu)解；另外,本文方法聚類迭代30～50次時最優(yōu)解樣本數(shù)量趨于穩(wěn)定,另外兩種方法沒有趨于穩(wěn)定的跡象,證明本文方法可靠性較強。上述數(shù)據(jù)表明，本文方法進行混合屬性數(shù)據(jù)聚類過程中,聚類性能優(yōu)于另外兩種方法,且迭代穩(wěn)定性、可靠性強。

表2 不同方法聚類性能對比結(jié)果

圖4 迭代次數(shù)與初始樣本組數(shù)量的關系Fig.4 The relationship between the number of iterations and the number of initial sample groups

2.4 適應度分析

聚類適應度影響聚類方法性能,因此,對3種混合屬性數(shù)據(jù)聚類方法的適應度進行測試,測試結(jié)果如圖5所示。

從圖5能夠看出，3種聚類方法適應度隨時間的進化過程,本文方法適應度值在0.88～0.94,處于穩(wěn)定發(fā)展狀態(tài),K-prototypes數(shù)據(jù)聚類方法適應度先增加再降低,最高適應度值為0.68,二重K近鄰聚類方法呈由高至低的狀態(tài),實驗結(jié)束時適應度值僅為0.3。

圖5 適應度變化曲線Fig.5 Fitness curve

總體看來,本文方法適應度值最高,適應度最強,增強了混合屬性數(shù)據(jù)聚類的性能。

3 結(jié)論

提出一種基于廣義線性模型的混合屬性數(shù)據(jù)聚類方法,實驗證明本文方法解決混合屬性數(shù)據(jù)聚類問題性能較優(yōu),相比同類方法具有優(yōu)勢。

總結(jié)本文提出的基于廣義線性模型的混合屬性數(shù)據(jù)聚類方法優(yōu)點如下:①構(gòu)建低階多元廣義線性模型,考慮了混合屬性樣本數(shù)據(jù)的時間特性,得到混合屬性時間序列矩陣,提升聚類算法準確度；②迭代聚類過程中,參考混合屬性數(shù)據(jù)樣本同原型的差異,樣本與聚類集間的距離計算采用更新的相異度公式與距離公式,得到的距離結(jié)果更加精準,有效提高聚類準確度。