于春艷,張育梅

(長春工業(yè)大學(xué)人文信息學(xué)院,吉林 長春130000

1 引言

聚類指將數(shù)據(jù)集合內(nèi)的數(shù)據(jù)依據(jù)固定的相似性度量準(zhǔn)則劃分為多組數(shù)據(jù)的方法。完成劃分的相同組數(shù)據(jù)具有較高的相似性[1];完成劃分后的不同組數(shù)據(jù)間存在較大差別。聚類算法是電子商務(wù)等眾多領(lǐng)域中應(yīng)用極為廣泛的算法。目前各應(yīng)用領(lǐng)域中的數(shù)據(jù)具有較高維度,樣本與樣本間的差異并不明顯[2],提升了數(shù)據(jù)聚類的難度,容易存在某數(shù)據(jù)樣本無法精準(zhǔn)確定屬于何種類別的問題,聚類算法無須先驗信息即可獲取數(shù)據(jù)中的相似信息。目前聚類算法應(yīng)用于不同領(lǐng)域中,各領(lǐng)域中的復(fù)雜數(shù)據(jù)類型以及巨大數(shù)據(jù)量,提升了數(shù)據(jù)聚類難度[3]。傳統(tǒng)聚類算法無法滿足高維度以及大數(shù)據(jù)量的數(shù)據(jù)聚類需求?？焖偎褜?shù)據(jù)聚類中心,將完成劃分的數(shù)據(jù)高效合并是大規(guī)模數(shù)據(jù)聚類的難點[4],提升聚類精度以及聚類速度已成為聚類領(lǐng)域的研究重點。相比于低維空間內(nèi)的數(shù)據(jù),高維空間內(nèi)的數(shù)據(jù)聚類難度更高,聚類過程中容易出現(xiàn)維度災(zāi)難問題。

某些領(lǐng)域中數(shù)據(jù)集內(nèi)的數(shù)據(jù)與數(shù)據(jù)間存在著固定順序關(guān)系,存在固定順序關(guān)系的變量稱之為有序變量,有序變量間的差異無法通過簡單的數(shù)值差異描述[5]。有序數(shù)據(jù)目前在市場調(diào)查、心理學(xué)等領(lǐng)域較為常見。有序數(shù)據(jù)通常為多元有序觀測數(shù)據(jù),多元有序數(shù)據(jù)的聚類精度極為重要?，F(xiàn)有研究通常采用屬性數(shù)據(jù)處理方法衡量不同有序觀測量間的距離[6],利用不同有序觀測量間存在的差異實施聚類。目前針對有序數(shù)據(jù)聚類的方法眾多,王治和等人以密度敏感距離為基礎(chǔ)[7],采用改進(jìn)模糊C均值聚類算法實現(xiàn)有序數(shù)據(jù)的聚類;何韓吉等人將趨勢性度量方法應(yīng)用于有序數(shù)據(jù)聚類中[8]。以上兩種方法均可以實現(xiàn)有序數(shù)據(jù)的聚類,但由于未考慮有序數(shù)據(jù)維度對聚類結(jié)果的影響,聚類效果并不理想。針對以上兩種方法的缺陷,研究基于有序聚類方程的數(shù)據(jù)相似性識別數(shù)學(xué)建模,數(shù)學(xué)建模是常應(yīng)用于數(shù)據(jù)統(tǒng)計分析中的重要方式,利用有序聚類方程建立識別數(shù)據(jù)相似性的數(shù)學(xué)模型,為數(shù)據(jù)相似性識別提供技術(shù)支持。通過仿真測試驗證所建立的基于有序聚類方程的數(shù)據(jù)相似性模型具有較高的數(shù)據(jù)相似性識別性能,應(yīng)用性極高。

2 數(shù)據(jù)相似性識別數(shù)學(xué)建模

設(shè)置所建立的基于有序聚類方程的數(shù)據(jù)相似性識別數(shù)學(xué)模型的輸入和輸出分別為多元有序數(shù)據(jù)樣本集X={x1,x2,…,xn}以及聚類結(jié)果,基于有序聚類方程的數(shù)據(jù)相似性識別數(shù)學(xué)建模過程如下:

1)數(shù)據(jù)預(yù)處理

對待聚類的有序數(shù)據(jù)集實施歸一化處理,將數(shù)據(jù)集內(nèi)的數(shù)據(jù)歸一化處理至[0,1]區(qū)間內(nèi),獲取歸一化后的數(shù)據(jù)集Data={x1,x2,…,xN};

2)依據(jù)網(wǎng)格?；惴▽⑼瓿蓺w一化后的有序數(shù)據(jù)空間劃分為多個均勻的網(wǎng)格空間;

3)掃描完成網(wǎng)格空間劃分后的數(shù)據(jù)集X={x1,x2,…,xn},將數(shù)據(jù)集內(nèi)的數(shù)據(jù)劃分至相應(yīng)網(wǎng)格單元中,計算各網(wǎng)格單元內(nèi)數(shù)據(jù)的密度信息;

4)依據(jù)網(wǎng)格單元內(nèi)數(shù)據(jù)密度信息計算結(jié)果識別各網(wǎng)格單元的中心點;

5)以網(wǎng)格單元中心點為基礎(chǔ),利用有序聚類方程計算各網(wǎng)格單元內(nèi)有序數(shù)據(jù)的相似性[9],利用相似性計算結(jié)果將數(shù)據(jù)劃分至不同類簇中,直至完成全部數(shù)據(jù)空間的網(wǎng)格掃描,將有序數(shù)據(jù)集內(nèi)的數(shù)據(jù)點標(biāo)記為相應(yīng)類別,相同類別內(nèi)的有序數(shù)據(jù)即為具有較高相似性的有序數(shù)據(jù)。通過以上過程完成基于有序聚類方程的數(shù)據(jù)相似性識別數(shù)學(xué)模型建立。

2.1 多元有序數(shù)據(jù)空間的網(wǎng)格?；惴?/h3>

選取STING網(wǎng)格劃分方法作為多元有序數(shù)據(jù)空間的網(wǎng)格?；惴?。采用STING網(wǎng)格劃分方法對多元有序數(shù)據(jù)空間內(nèi)的有序數(shù)據(jù)實施粒化,將多元有序數(shù)據(jù)空間內(nèi)的原始有序數(shù)據(jù)點利用網(wǎng)格單元數(shù)據(jù)替代[10],降低多元有序數(shù)據(jù)維度,實現(xiàn)多元有效數(shù)據(jù)的有效壓縮。

設(shè)置STING網(wǎng)格劃分算法的輸入有序數(shù)據(jù)樣本集以及輸出網(wǎng)格單元集分別用X={x1,x2,…,xn}與G={g1,g2,…,gn}表示。STING網(wǎng)格劃分方法的多元有序數(shù)據(jù)空間的網(wǎng)格粒化過程如下:

1)將多元有序數(shù)據(jù)空間集內(nèi)全部數(shù)據(jù)歸一化至維度為D={d1,d2,…,dn}的數(shù)據(jù)空間內(nèi),令[0,1]d?D。

2)多元有序空間內(nèi)數(shù)據(jù)的聚類效果受劃分網(wǎng)格粒度影響,選取最合適的網(wǎng)格劃分粒度,可以獲取最優(yōu)聚類效果。劃分網(wǎng)格數(shù)量過多時,網(wǎng)格單元內(nèi)數(shù)據(jù)容易丟失,影響聚類精度[11];劃分網(wǎng)格數(shù)量過少時,網(wǎng)格內(nèi)數(shù)據(jù)與原數(shù)據(jù)空間內(nèi)數(shù)據(jù)存在較高相似性,無法實現(xiàn)數(shù)據(jù)快速處理。網(wǎng)格劃分的尺度參數(shù)需依據(jù)多元有序空間內(nèi)的數(shù)據(jù)數(shù)量決定。通過尺度參數(shù)ξ劃分多元有序數(shù)據(jù)空間網(wǎng)格,尺度參數(shù)表達(dá)式如下

ξ=N/k

(1)

式(1)中,N與k分別表示樣本數(shù)量以及聚類數(shù)量。

劃分多元有序數(shù)據(jù)空間網(wǎng)格維度的表達(dá)式如下

(2)

3)掃描全部多元有序數(shù)據(jù)空間內(nèi)數(shù)據(jù)集,將數(shù)據(jù)集內(nèi)全部數(shù)據(jù)放入完成劃分后的數(shù)據(jù)空間網(wǎng)格中[12],網(wǎng)格單元數(shù)量為n。用N與k分別表示數(shù)據(jù)空間內(nèi)數(shù)據(jù)維度以及數(shù)據(jù)點數(shù)量,D={d1,d2,…,dn}與X={x1,x2,…,xn}分別表示數(shù)據(jù)維度以及數(shù)據(jù)集,依據(jù)尺度參數(shù)ξ將多元有序空間內(nèi)數(shù)據(jù)的每個維度劃分為ε等分,可得不同維度的有序數(shù)據(jù)劃分結(jié)果為di={c1,c2,…,cε}。

2.2 有序數(shù)據(jù)的網(wǎng)格中心點識別

用i表示完成劃分后的多元有序網(wǎng)格空間內(nèi)隨機數(shù)據(jù),隨機數(shù)據(jù)i的密度計算公式如下

ρi=?i+ηi

(3)

式(3)中,ηi與?i分別表示多元有序網(wǎng)格空間內(nèi)數(shù)據(jù)度數(shù)以及該數(shù)據(jù)全部鄰域數(shù)據(jù)度數(shù)之和。通過式(3)獲取多元有序空間內(nèi)其中一個網(wǎng)格全部數(shù)據(jù)的密度值后,將所獲取的數(shù)據(jù)密度值作為基礎(chǔ)[13],可得全部數(shù)據(jù)間的距離σ。數(shù)據(jù)i的距離值σi計算表達(dá)式如下

(4)

式(4)中,dij表示有序數(shù)據(jù)i與有序數(shù)據(jù)j的圖論距離,有序數(shù)據(jù)i的密度值低于有序數(shù)據(jù)j的密度值。

將數(shù)據(jù)i的密度值與距離值利用Z-score方法標(biāo)準(zhǔn)化處理。數(shù)據(jù)i的密度值標(biāo)準(zhǔn)化處理表達(dá)式如下

(5)

(6)

式中,μρ與μσ分別表示多元有序網(wǎng)格空間內(nèi)全部數(shù)據(jù)的密度均值與距離均值;φp與φσ分別表示多元有序網(wǎng)格空間內(nèi)全部數(shù)據(jù)的密度標(biāo)準(zhǔn)差與距離標(biāo)準(zhǔn)差。

(7)

2.3 有序聚類方程的數(shù)據(jù)相似性計算

識別有序數(shù)據(jù)相似性前,需要將全部有序數(shù)據(jù)依據(jù)固定的排序準(zhǔn)則排列,令相鄰有序數(shù)據(jù)間的相似性最高。以上文獲取的網(wǎng)格單元中心點為基礎(chǔ),用C(F)表示有序數(shù)據(jù)的性質(zhì)特征,有序數(shù)據(jù)的性質(zhì)特征相似度到達(dá)固定數(shù)值時,即可劃分為相同類別中。F表示數(shù)據(jù)的秩,該值越高時,表示數(shù)據(jù)重要性越高。有序聚類的實質(zhì)是令完成聚類后,相同類別的有序數(shù)據(jù)差異盡可能小,不同類別的數(shù)據(jù)差異盡可能大[14]。采用有序聚類方程作為識別不同有序數(shù)據(jù)相似性的聚類算法,有序數(shù)據(jù)聚類過程如下:

1)對有序數(shù)據(jù)的相似性實施排秩處理。

以網(wǎng)格單元中心點為基礎(chǔ),依據(jù)從小到大原則對數(shù)據(jù)相似性指標(biāo)向量內(nèi)的全部相似性計算結(jié)果排秩。完成排秩后建立相似性指標(biāo)的秩向量R=(r1,2,r2,3,…,rn-1,n)。

分析以上過程可知,相鄰數(shù)據(jù)間的秩越小時,表示數(shù)據(jù)間相似性較小;相鄰數(shù)據(jù)間的秩越大時,表示數(shù)據(jù)間相似性越大。

2)確定有序秩聚類的聚類數(shù)量k。

數(shù)據(jù)待聚類數(shù)量為k時,數(shù)據(jù)聚類的斷開位置為rij=1,2,…,k-1,相鄰斷點內(nèi)的數(shù)據(jù)即可劃分為相同類別。

采用有序聚類方程對有序數(shù)據(jù)聚類時,需要確定的聚類數(shù)量需令不同類別有序數(shù)據(jù)的誤差函數(shù)之和為最小。聚類過程中存在相同秩情況時,需要搜尋令誤差函數(shù)最小的位置,從誤差最小位置斷開[15],獲取最佳聚類結(jié)果。

定義有序數(shù)據(jù)的排序準(zhǔn)則如下:

設(shè)多元有序空間內(nèi)包含數(shù)據(jù)數(shù)量為n,Ck(Fk)表示有序數(shù)據(jù)k的分布特征,依據(jù)Fk將全部有序數(shù)據(jù)從小到大順序排列。依據(jù)以上排序準(zhǔn)則實現(xiàn)多元有序數(shù)據(jù)的同質(zhì)數(shù)據(jù)集中化,異質(zhì)數(shù)據(jù)分散化。通過有序數(shù)據(jù)的初步排序為有序數(shù)據(jù)相似性識別提供基礎(chǔ)。

有序數(shù)據(jù)相似性識別過程如下:

計算多元有序空間內(nèi)數(shù)據(jù)特征Ck(Fk),依據(jù)上文確定的數(shù)據(jù)排序準(zhǔn)則,重新排序全部數(shù)據(jù)的Ck(Fk),完成排序后的數(shù)據(jù)用向量C=(C1,C2,…,Cn)表示。相鄰數(shù)據(jù)相似性識別的有序聚類方程如下

(8)

利用向量S=(S1,2,S2,3,…,Sn-1,n)表示全部有序數(shù)據(jù)的相似性識別結(jié)果。

3 仿真測試

為了驗證所建立數(shù)學(xué)模型采用有序聚類方程識別數(shù)據(jù)相似性有效性,采用Bochs仿真平臺進(jìn)行本文模型的仿真測試。選取應(yīng)用于市場調(diào)查中的人工數(shù)據(jù)集作為本文模型的測試對象,數(shù)據(jù)集中包含子數(shù)據(jù)集3個。人工數(shù)據(jù)集中的有序樣本為4維數(shù)據(jù),包含樣本數(shù)量共11889個。

統(tǒng)計本文模型采用有序聚類方程識別數(shù)據(jù)相似性,差異類別數(shù)量以及差異尺度參數(shù)時的下近似中類內(nèi)間距,統(tǒng)計結(jié)果如圖1所示。

圖1 聚類收斂曲線

圖1實驗結(jié)果可以看出,有序聚類方程設(shè)置類別數(shù)量為12個時,采用本文模型可以在20次迭代次數(shù)之內(nèi)實現(xiàn)快速收斂,且獲取聚類結(jié)果的下近似中類內(nèi)距離較高,說明此時本文模型具有良好的聚類收斂效果。采用本文模型識別數(shù)據(jù)相似性時,設(shè)置有序聚類方程的聚類類別數(shù)量為12。下近似中類內(nèi)距離越大時,表示聚類算法準(zhǔn)確率越高,此時劃分至該類別中的有序樣本越多。本文模型在聚類類別數(shù)量為12時,具有良好的聚類性能。

設(shè)置聚類類別數(shù)量為12,采用本文模型對測試數(shù)據(jù)集中的有序數(shù)據(jù)實施聚類處理,聚類結(jié)果如表1所示。

表1 本文模型聚類結(jié)果

表1實驗結(jié)果可以看出,采用本文模型將測試數(shù)據(jù)集中的樣本,劃分為12類,此時相同類別內(nèi)的有序數(shù)據(jù)具有較高相似性,驗證本文模型可以有效識別有序數(shù)據(jù)集內(nèi)的有序數(shù)據(jù)。本文模型可以利用有序聚類方程實現(xiàn)有序數(shù)據(jù)的有效識別,具有較高的應(yīng)用性。

Kappa系數(shù)是常見的應(yīng)用于評價聚類性能的指標(biāo),Kappa系數(shù)計算公式如下:

(9)

式(9)中,nk+與n+k分別表示類真實的樣本數(shù)量以及類被分類的樣本總數(shù);nk與N分別表示劃分至k簇中的樣本數(shù)量。

設(shè)置聚類類別數(shù)量為12,統(tǒng)計不同鄰居節(jié)點數(shù)量時,采用本文模型對不同類別有序數(shù)據(jù)相似性進(jìn)行識別。不同鄰居節(jié)點數(shù)量時,本文模型的Kappa系數(shù)統(tǒng)計結(jié)果如圖2所示。

圖2 Kappa系數(shù)對比結(jié)果

通過圖2實驗結(jié)果可以看出,鄰居數(shù)越少時,數(shù)據(jù)相似性識別的Kappa系數(shù)越高,鄰居節(jié)點數(shù)量越多時,影響了有序聚類方程的聚類效果,鄰居節(jié)點數(shù)量為9時,采用本文模型識別有序數(shù)據(jù)相似性,設(shè)置鄰居節(jié)點數(shù)量為9,此時可以獲取最佳的有序數(shù)據(jù)識別結(jié)果。

統(tǒng)計采用本文模型識別有序數(shù)據(jù)相似性的標(biāo)準(zhǔn)互信息結(jié)果,統(tǒng)計結(jié)果如圖3所示。

圖3 標(biāo)準(zhǔn)互信息統(tǒng)計結(jié)果

通過圖3實驗結(jié)果可以看出,采用本文模型識別有序數(shù)據(jù)相似性,對不同子數(shù)據(jù)集內(nèi)的有序數(shù)據(jù)樣本進(jìn)行相似性識別,識別結(jié)果的標(biāo)準(zhǔn)互信息結(jié)果均高于0.9。統(tǒng)計結(jié)果驗證本文模型具有較高的有序數(shù)據(jù)相似性識別性能,本文模型可將具有較高相似性的有序數(shù)據(jù)精準(zhǔn)聚類,聚類結(jié)果較優(yōu)。

調(diào)節(jié)蘭德指數(shù)是應(yīng)用于聚類算法評價中的另一重要評價指標(biāo)。調(diào)節(jié)蘭德指數(shù)的取值區(qū)間為[-1,1],該指標(biāo)可以體現(xiàn)聚類算法劃分不同類別時的重疊情況。統(tǒng)計采用本文模型識別有序數(shù)據(jù)相似性的調(diào)節(jié)蘭德指數(shù),統(tǒng)計結(jié)果如圖4所示。

圖4 調(diào)節(jié)蘭德指數(shù)

圖4實驗結(jié)果可以看出,采用本文模型識別有序數(shù)據(jù)相似性的調(diào)節(jié)蘭德指數(shù)均高于0.8。圖4實驗結(jié)果驗證本文模型具有較高的聚類性能,本文模型可將具有較高相似性的有序數(shù)據(jù)精準(zhǔn)聚類,聚類性能優(yōu)越,提升了模型的應(yīng)用性。

采用本文模型識別測試數(shù)據(jù)集內(nèi)的有序數(shù)據(jù)相似性,有序數(shù)據(jù)相似性識別的平均絕對誤差結(jié)果如圖5所示。

圖5 平均絕對誤差

圖5實驗結(jié)果可以看出,伴隨樣本數(shù)量的增加,本文模型識別有序數(shù)據(jù)相似性的平均絕對誤差有所降低。實驗結(jié)果說明本文模型在樣本數(shù)據(jù)量較大時,仍具有較高的聚類性能,可以提升有序數(shù)據(jù)相似性的識別性能。有序數(shù)據(jù)具有較高的聚類難度,本文模型可以實現(xiàn)有序數(shù)據(jù)的精準(zhǔn)聚類,獲取理想的有序數(shù)據(jù)相似性識別結(jié)果,具有較高的有序數(shù)據(jù)相似性識別性能。

4 結(jié)論

有序數(shù)據(jù)由于結(jié)構(gòu)過于復(fù)雜,增加了數(shù)據(jù)聚類的難度。多元有序數(shù)據(jù)的相似性識別已成為目前眾多領(lǐng)域研究學(xué)者極為重視的重要內(nèi)容?；谟行蚓垲惙匠探?shù)據(jù)相似性識別的數(shù)學(xué)模型,通過仿真測試驗證所建立的數(shù)學(xué)模型可以實現(xiàn)有效數(shù)據(jù)相似性的高效識別,避免有序數(shù)據(jù)維度過多時,受噪聲數(shù)據(jù)影響造成不良影響。所建立的數(shù)學(xué)模型具有較高的有效性,適用于眾多領(lǐng)域中的數(shù)據(jù)相似性識別中。