基于有序聚類方程的數(shù)據(jù)相似性識(shí)別數(shù)學(xué)建模

于春艷,張育梅

(長(zhǎng)春工業(yè)大學(xué)人文信息學(xué)院,吉林 長(zhǎng)春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ù)樣本無(wú)法精準(zhǔn)確定屬于何種類別的問題,聚類算法無(wú)須先驗(yàn)信息即可獲取數(shù)據(jù)中的相似信息。目前聚類算法應(yīng)用于不同領(lǐng)域中,各領(lǐng)域中的復(fù)雜數(shù)據(jù)類型以及巨大數(shù)據(jù)量,提升了數(shù)據(jù)聚類難度[3]。傳統(tǒng)聚類算法無(wú)法滿足高維度以及大數(shù)據(jù)量的數(shù)據(jù)聚類需求?？焖偎褜?shù)據(jù)聚類中心,將完成劃分的數(shù)據(jù)高效合并是大規(guī)模數(shù)據(jù)聚類的難點(diǎn)[4],提升聚類精度以及聚類速度已成為聚類領(lǐng)域的研究重點(diǎn)。相比于低維空間內(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)系的變量稱之為有序變量,有序變量間的差異無(wú)法通過簡(jiǎn)單的數(shù)值差異描述[5]。有序數(shù)據(jù)目前在市場(chǎng)調(diào)查、心理學(xué)等領(lǐng)域較為常見。有序數(shù)據(jù)通常為多元有序觀測(cè)數(shù)據(jù),多元有序數(shù)據(jù)的聚類精度極為重要?，F(xiàn)有研究通常采用屬性數(shù)據(jù)處理方法衡量不同有序觀測(cè)量間的距離[6],利用不同有序觀測(cè)量間存在的差異實(shí)施聚類。目前針對(duì)有序數(shù)據(jù)聚類的方法眾多,王治和等人以密度敏感距離為基礎(chǔ)[7],采用改進(jìn)模糊C均值聚類算法實(shí)現(xiàn)有序數(shù)據(jù)的聚類;何韓吉等人將趨勢(shì)性度量方法應(yīng)用于有序數(shù)據(jù)聚類中[8]。以上兩種方法均可以實(shí)現(xiàn)有序數(shù)據(jù)的聚類,但由于未考慮有序數(shù)據(jù)維度對(duì)聚類結(jié)果的影響,聚類效果并不理想。針對(duì)以上兩種方法的缺陷,研究基于有序聚類方程的數(shù)據(jù)相似性識(shí)別數(shù)學(xué)建模,數(shù)學(xué)建模是常應(yīng)用于數(shù)據(jù)統(tǒng)計(jì)分析中的重要方式,利用有序聚類方程建立識(shí)別數(shù)據(jù)相似性的數(shù)學(xué)模型,為數(shù)據(jù)相似性識(shí)別提供技術(shù)支持。通過仿真測(cè)試驗(yàn)證所建立的基于有序聚類方程的數(shù)據(jù)相似性模型具有較高的數(shù)據(jù)相似性識(shí)別性能,應(yīng)用性極高。

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

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

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

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

2)依據(jù)網(wǎng)格粒化算法將完成歸一化后的有序數(shù)據(jù)空間劃分為多個(gè)均勻的網(wǎng)格空間;

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

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

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

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

選取STING網(wǎng)格劃分方法作為多元有序數(shù)據(jù)空間的網(wǎng)格粒化算法。采用STING網(wǎng)格劃分方法對(duì)多元有序數(shù)據(jù)空間內(nèi)的有序數(shù)據(jù)實(shí)施粒化,將多元有序數(shù)據(jù)空間內(nèi)的原始有序數(shù)據(jù)點(diǎn)利用網(wǎng)格單元數(shù)據(jù)替代[10],降低多元有序數(shù)據(jù)維度,實(shí)現(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ù)量過多時(shí),網(wǎng)格單元內(nèi)數(shù)據(jù)容易丟失,影響聚類精度[11];劃分網(wǎng)格數(shù)量過少時(shí),網(wǎng)格內(nèi)數(shù)據(jù)與原數(shù)據(jù)空間內(nèi)數(shù)據(jù)存在較高相似性,無(wú)法實(shí)現(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ù)點(diǎn)數(shù)量,D={d1,d2,…,dn}與X={x1,x2,…,xn}分別表示數(shù)據(jù)維度以及數(shù)據(jù)集,依據(jù)尺度參數(shù)ξ將多元有序空間內(nèi)數(shù)據(jù)的每個(gè)維度劃分為ε等分,可得不同維度的有序數(shù)據(jù)劃分結(jié)果為di={c1,c2,…,cε}。

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

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

ρi=?i+ηi

(3)

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

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

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

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

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

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

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

采用有序聚類方程對(duì)有序數(shù)據(jù)聚類時(shí),需要確定的聚類數(shù)量需令不同類別有序數(shù)據(jù)的誤差函數(shù)之和為最小。聚類過程中存在相同秩情況時(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)則實(shí)現(xiàn)多元有序數(shù)據(jù)的同質(zhì)數(shù)據(jù)集中化,異質(zhì)數(shù)據(jù)分散化。通過有序數(shù)據(jù)的初步排序?yàn)橛行驍?shù)據(jù)相似性識(shí)別提供基礎(chǔ)。

有序數(shù)據(jù)相似性識(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ù)相似性識(shí)別的有序聚類方程如下

(8)

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

3 仿真測(cè)試

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

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

圖1 聚類收斂曲線

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

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

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

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

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

(9)

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

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

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

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

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

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

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

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

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

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

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

圖5 平均絕對(duì)誤差

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

4 結(jié)論

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