趙 健

(長(zhǎng)治學(xué)院 計(jì)算機(jī)系, 山西 長(zhǎng)治 046011)

數(shù)據(jù)的多樣性與復(fù)雜性導(dǎo)致每個(gè)記錄都是一個(gè)特征向量, 每個(gè)對(duì)象都由多個(gè)特征向量組成, 每個(gè)對(duì)象稱為矩陣對(duì)象, 這類數(shù)據(jù)廣泛應(yīng)用于銀行、 保險(xiǎn)、 電信、 零售、 醫(yī)學(xué)等領(lǐng)域[1-2]. 在大多數(shù)情況下, 矩陣對(duì)象由分類屬性和數(shù)字屬性共同描述, 而用戶行為的變化是一個(gè)隨時(shí)間變化的動(dòng)態(tài)演化過(guò)程, 因此如何實(shí)現(xiàn)有效矩陣對(duì)象數(shù)據(jù)聚類成為研究的熱點(diǎn)[3].

用傳統(tǒng)聚類算法解決上述問(wèn)題, 需對(duì)矩陣對(duì)象數(shù)據(jù)進(jìn)行變換, 主要有兩種方法： 一種是將矩陣對(duì)象壓縮成一個(gè)向量, 常用的壓縮方法是分別用分類屬性和數(shù)值屬性的模式和方法表示矩陣對(duì)象. 文獻(xiàn)[4]為克服不同初始類中心對(duì)聚類結(jié)果的影響, 針對(duì)分類型矩陣數(shù)據(jù), 提出了一種新的初始聚類中心選擇算法； 文獻(xiàn)[5]提出了三類廣義多實(shí)例假設(shè), 并在基于廣義假設(shè)條件下建立了一個(gè)層次結(jié)構(gòu)； 文獻(xiàn)[6]提出了一種基于簇間信息的分類矩陣對(duì)象數(shù)據(jù)的聚類算法, 該算法利用k-modes算法實(shí)現(xiàn)矩陣對(duì)象聚類. 但上述方法使數(shù)據(jù)大部分信息丟失, 并且只考慮平均值, 不能反映具體的數(shù)據(jù)信息.

另一種方法是將每個(gè)屬性值視為一個(gè)新的屬性進(jìn)行處理. 文獻(xiàn)[7]通過(guò)給出一種矩陣對(duì)象自身的內(nèi)聚度和該矩陣對(duì)象與其他矩陣對(duì)象之間的耦合度, 定義矩陣對(duì)象的孤立因子, 提出了一種基于信息熵的孤立點(diǎn)檢測(cè)算法; 文獻(xiàn)[8]基于信息熵定義了一種屬性權(quán)重的新度量方法, 并提出一種加權(quán)k-prototype算法實(shí)現(xiàn)矩陣對(duì)象數(shù)據(jù)聚類; 文獻(xiàn)[9]提出了一種基于密度峰值思想的加權(quán)猶豫模糊矩陣對(duì)象數(shù)據(jù)聚類算法, 該算法不僅降低了簇中心計(jì)算的復(fù)雜度, 而且提高了對(duì)不同規(guī)模以及任意形狀矩陣對(duì)象數(shù)據(jù)集的適應(yīng)性. 但上述方法會(huì)使矩陣對(duì)象數(shù)據(jù)更稀疏和高維, 從而極大降低了聚類準(zhǔn)確性.

為解決傳統(tǒng)聚類方法存在的局限性, 本文提出一種基于k多數(shù)值代表的混合矩陣對(duì)象數(shù)據(jù)聚類方法. 通過(guò)定義一種新的相異度度量計(jì)算兩個(gè)數(shù)值矩陣對(duì)象之間的差異, 提出k多數(shù)值代表聚類算法實(shí)現(xiàn)混合矩陣對(duì)象數(shù)據(jù)的聚類. 實(shí)驗(yàn)結(jié)果證明了本文方法的有效性.

1 矩陣對(duì)象數(shù)據(jù)的聚合

1.1 問(wèn)題描述

設(shè)X={X1,X2,…,Xn}表示由m屬性{A1,A2,…,Am}描述的矩陣對(duì)象數(shù)據(jù)集, 其中Xi(1≤i≤n)表示第i個(gè)帶有ri個(gè)特征向量的矩陣對(duì)象, 表示為

(1)

1.2 算法設(shè)計(jì)

1.2.1 兩個(gè)數(shù)值矩陣對(duì)象間的相異度

本文將每個(gè)矩陣對(duì)象作為一個(gè)ri_by_m(ri≥1)型矩陣, 且矩陣對(duì)象不同, 其ri值也不同.由于由兩個(gè)特征向量與兩個(gè)矩陣對(duì)象間的歐氏距離測(cè)得的相異度不符合所有特征向量與矩陣對(duì)象觀測(cè)分類有關(guān)的特征, 所以本文提出一種測(cè)量數(shù)值矩陣對(duì)象相異度的新方法.已知每個(gè)距離需在相同特征空間內(nèi)測(cè)量, 假設(shè)屬性特征獨(dú)立, 兩個(gè)矩陣對(duì)象間的差異度可通過(guò)其特征的差別測(cè)得.由于可以將任意矩陣對(duì)象視作m型ri維向量, 因此上述問(wèn)題可轉(zhuǎn)化為測(cè)量相同特征空間內(nèi)兩個(gè)長(zhǎng)度不等的向量之間差異度問(wèn)題.由于數(shù)值屬性值具有連續(xù)性, 因此上述方法可借助其相鄰值進(jìn)行測(cè)量計(jì)算.

定義1[5]假設(shè)X為一已知的數(shù)值矩陣對(duì)象數(shù)據(jù)集,Vs為X在屬性As內(nèi)的域值集.Xis=(vi1s,vi2s,…,viris)T表示Xi(Xi∈X)的第s個(gè)ri維列向量,εs為已知參數(shù), 且?v∈Vs, 上述列向量的相鄰值在Xis內(nèi)的數(shù)量可表示為

(2)

其中

(3)

定義2[6]已知由m屬性{A1,A2,…,Am}定義的數(shù)值矩陣對(duì)象Xi和Xj, 則Xi和Xj間的相異度度量可表示為

(4)

其中

(5)

V=Xis∪Xjs, |·|表示絕對(duì)值, 并且需加入歸一化因子0.5, 使得0≤n_δ(Xis,Xjs)≤1, 當(dāng)且僅當(dāng)Xis∩Xjs=?時(shí),n_δ(Xis,Xjs)=1.

1.2.2 啟發(fā)式聚類中心更新方法

定義3已知由m屬性描述的數(shù)值矩陣對(duì)象數(shù)據(jù)集X={X1,X2,…,Xn}.設(shè)Vs為X在屬性As內(nèi)的值域集, ?v∈Vs, 其權(quán)重表示為

(6)

已知矩陣對(duì)象Xi(Xi∈X), 由式(2)可知,n_fi(v)為屬性值v在Xis內(nèi)相鄰值的個(gè)數(shù),n_fi(v)/ri為屬性值v在Xis內(nèi)的重要程度.n_fi(v)越高, 表示v在Xis中越重要.被選中的代表聚類中心屬性值應(yīng)在任一矩陣對(duì)象中都較重要.在式(6)中, 有0≤n_fi(v)/ri≤1, 且0≤n_ω(v)≤1.當(dāng)且僅當(dāng)n_fi(v)/ri=1(?i∈{1,2,…,n})時(shí), 有n_ω(v)=1.即當(dāng)且僅當(dāng)屬性值在任一矩陣對(duì)象中很重要時(shí), 該屬性值的權(quán)重較高.

算法1啟發(fā)式聚類中心更新算法.

輸入：m屬性描述的n數(shù)值矩陣對(duì)象集X, 用于計(jì)算相鄰值的參數(shù)集ε={ε1,ε2,…,εm}；

輸出：X的一個(gè)聚類中心Q；

步驟1) fors=1∶1∶mdo

步驟2) sum=0,Q=?；

步驟3) fori=1∶1∶ndo

步驟5) end for

步驟6)us=round(sum/n);

步驟7) fort=1∶1∶|Vs| do

步驟9) end for

步驟12)Q=Q∪QAs；

步驟13) end for

步驟14) 返回Q.

1.2.3k-Mnv-Rep算法

已知公式聚類k(?n)內(nèi)的數(shù)值矩陣對(duì)象集X={X1,X2,…,Xn}, 使用k-Mnv-Rep算法對(duì)下列目標(biāo)函數(shù)最小化：

(7)

其中W=(ωli)為k_by_n{0,1}矩陣, 當(dāng)ωli=1時(shí), 將目標(biāo)Xi分配入聚類l；Q={Q1,Q2,…,Qk},Ql∈Q表示聚類l中的多數(shù)值表示.

對(duì)目標(biāo)函數(shù)的最小化為NP難問(wèn)題, 一般情況下, 可通過(guò)不斷迭代直到完成聚合, 從而解決兩個(gè)子問(wèn)題, 進(jìn)一步解決F(W,Q)問(wèn)題: 1) 在迭代t中, 始終令Q=Qt, 利用式(3), 解決F(W,Qt)減小問(wèn)題, 并找出F(W,Qt)取得最小值時(shí)的Wt; 2) 通過(guò)運(yùn)行算法1, 用上述得到的Wt值解決F(Wt,Q)減小問(wèn)題, 并找出F(Wt,Q)取得最小值時(shí)的Qt+1.

算法2k-Mnv-Rep算法.

輸入：m屬性描述的n數(shù)值矩陣對(duì)象集X, 需聚合的聚類個(gè)數(shù)k, 閾值o;

輸出： 聚合后所有目標(biāo)的標(biāo)簽cid;

步驟1) 生成隨機(jī)數(shù)k, 通過(guò)指數(shù)取得初始中心k；

步驟2) 設(shè)Q={Ql,Q2,…,Qk}為初始中心, 且value=0, num=0;

步驟3) while num≤100 do

步驟4) value1=0;

步驟5) fori=1∶1∶ndo

步驟8) end for

步驟9) if |value1-value|≤o, break； else value=value1, 且num=num+1；

步驟10) forl=1∶1∶kdo

步驟11) 運(yùn)行算法1, 更新聚類中心Ql；

步驟12) end for

步驟13) end while.

對(duì)k-Mnv-Rep算法計(jì)算復(fù)雜性的分析如下.

1) 計(jì)算相異度： 屬性As內(nèi)兩個(gè)數(shù)值矩陣對(duì)象間相異度的復(fù)雜性可表示為O(|Vs|), 屬性m內(nèi)兩個(gè)數(shù)值矩陣對(duì)象間相異度的計(jì)算復(fù)雜性可表示為O(m|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.

2) 更新聚類中心： 屬性As屬性值權(quán)重的計(jì)算復(fù)雜性可表示為O(n|Vs|), 屬性m內(nèi)k型聚類中心的計(jì)算復(fù)雜性可表示為O(kmn|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.

3) 通過(guò)t型迭代進(jìn)行聚合時(shí),k-Mnv-Rep算法的總計(jì)算復(fù)雜性可表示為O(tmnk|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.因此, 該算法的時(shí)間復(fù)雜性與矩陣對(duì)象數(shù)量、 屬性數(shù)量、 聚類數(shù)量和屬性值數(shù)量呈線性正相關(guān).

1.3 用于處理混合矩陣對(duì)象數(shù)據(jù)的算法

1.3.1 兩個(gè)混合矩陣對(duì)象間的相異度

(8)

其中γ為權(quán)重, 可使兩種數(shù)據(jù)得到相同處理.As內(nèi)范疇型矩陣對(duì)象的距離可表示為

(9)

其中V=Xis∪Xjs, 當(dāng)兩個(gè)參數(shù)相等時(shí),c_g(·,·)=1, 其余情況下,c_g(·,·)=0.需加入歸一化因子0.5, 使得0≤c_δ(Xis,Xjs)≤1.當(dāng)且僅當(dāng)Xis∩Xjs=?時(shí),c_δ(Xis,Xjs)=1.

(10)

其中

(11)

定義6設(shè)X為由屬性m描述的混合矩陣對(duì)象數(shù)據(jù)集.?Xi,Xj∈X,Xi和Xj間的相異度可表示為

(12)

其中

(13)

1.3.2 屬性值的權(quán)重更新方法

分別通過(guò)數(shù)值屬性和范疇屬性更新聚類中心.在任一屬性中, 更新方法應(yīng)以較高權(quán)重得到若干數(shù)值.權(quán)重的定義是更新算法的關(guān)鍵.根據(jù)式(10)可知, 當(dāng)v值已知時(shí), 公式在數(shù)值屬性和范疇屬性內(nèi)一致.因此, 在已知混合數(shù)據(jù)集內(nèi), 屬性值的權(quán)重可定義如下.

定義7設(shè)X為屬性m描述的含有n個(gè)混合矩陣對(duì)象的數(shù)據(jù)集,Vs為X在屬性As內(nèi)的域值集, ?v∈Vs, 其權(quán)重定義為

(14)

1.3.3k-Mv-Rep算法

設(shè)X={X1,X2,…,Xn}為混合矩陣對(duì)象數(shù)據(jù)集.k-Mv-Rep算法可以將X聚合入k(≤n)聚類內(nèi), 從而實(shí)現(xiàn)下列目標(biāo)函數(shù)的最小化：

(15)

與k-Mnv-Rep算法相似, 通過(guò)使用一種新的啟發(fā)式聚類中心更新方法處理混合矩陣對(duì)象數(shù)據(jù)取得F′(W′,Q′)的局部最小值, 取得局部最小的過(guò)程與k-Mnv-Rep算法相同.

算法3k-Mv-Rep算法.

輸入： 屬性m描述的n混合矩陣對(duì)象數(shù)據(jù)集X, 需聚合的聚類個(gè)數(shù)k, 域值o；

輸出： 聚合后所有目標(biāo)的標(biāo)簽cid；

步驟1) 生成k個(gè)隨機(jī)數(shù), 通過(guò)指數(shù)取得k個(gè)初始中心；

步驟2) 設(shè)Q={Q1,Q2,…,Qk}為初始中心, 且value=0, num=0；

步驟3) while num≤100 do

步驟4) value1=0;

步驟5) fori=i∶1∶ndo

步驟8) end for

步驟9) if |value1-value|≤o, break； else, value=value1且num=num+1；

步驟10) forl∶1∶kdo

步驟11) 利用式(14)更新聚類中心Ql；

步驟12) end for

步驟13) end while.

k-Mnv-Rep算法的總計(jì)算復(fù)雜性可表示為O(tmnk|V′|), 這里t表示迭代, 且|V′|=max{|Vs|, 1≤s≤m}. 因此, 該算法的計(jì)算時(shí)間復(fù)雜性與矩陣對(duì)象數(shù)量、 屬性數(shù)量、 聚類數(shù)量和屬性值數(shù)量呈線性正相關(guān).

2 實(shí)驗(yàn)與分析

2.1 評(píng)估指標(biāo)

采用5個(gè)外部指標(biāo)評(píng)估上述兩種算法, 分別為精確度(AC)、 準(zhǔn)確度(PE)、 召回率(RE)、 調(diào)整蘭德系數(shù)(ARI)和歸一化互信息(NMI)[10].

設(shè)X為一矩陣對(duì)象數(shù)據(jù)集,C={C1,C2,…,Ck′}為X的聚合結(jié)果,P={P1,P2,…,Pk}為X的實(shí)分區(qū).nij為Pi和Cj中相同的矩陣對(duì)象數(shù)量, 即nij=|Pi∩Cj|,pi和cj分別為Pi和Cj中的矩陣對(duì)象數(shù)量.5個(gè)評(píng)估指標(biāo)分別定義如下：

2.2 數(shù)值矩陣對(duì)象數(shù)據(jù)實(shí)驗(yàn)

2.2.1 真實(shí)數(shù)據(jù)集

由于缺少公開(kāi)數(shù)值矩陣對(duì)象, 因此本文實(shí)驗(yàn)使用多示例數(shù)據(jù)集評(píng)估k-Mnv-Rep算法, 另一部分實(shí)驗(yàn)圍繞9組真實(shí)數(shù)據(jù)集展開(kāi), 數(shù)據(jù)集信息列于表1.

表1 數(shù)據(jù)集信息

2.2.2 比較結(jié)果

通過(guò)表1中9種數(shù)值型數(shù)據(jù)集實(shí)驗(yàn), 將k-Mnv-Rep算法與使用3種距離表示方式的包級(jí)多實(shí)例聚類算法(BAMIC)[11]、 自適應(yīng)鄰域聚類算法(CAN)[12]、 表示自適應(yīng)鄰域聚類算法(PCAN)[13]、L1范數(shù)垃圾回收算法(CLR-L1)[14]、L2范數(shù)垃圾回收算法(CLR-L2)[15]得出的結(jié)果進(jìn)行比較. 上述后4種算法的輸入數(shù)據(jù)集中, 每個(gè)矩陣對(duì)象都由一個(gè)向量描述. 因此, 以每個(gè)矩陣對(duì)象的中值作為每個(gè)屬性的屬性值.

在實(shí)驗(yàn)過(guò)程中, 將8種算法各運(yùn)行30次, 取最終結(jié)果的中值. 設(shè)參數(shù)εs大小為第s屬性內(nèi)X標(biāo)準(zhǔn)差的1/2, 在k-Mnv-Rep算法中, 設(shè)該參數(shù)為0.2. 不同算法9個(gè)數(shù)據(jù)集的對(duì)比結(jié)果列于表2, 其中符號(hào)“±”左側(cè)為中值, 右側(cè)為標(biāo)準(zhǔn)差. 在每個(gè)數(shù)據(jù)集中, 對(duì)評(píng)估指數(shù)值進(jìn)行排序, 最高值排序?yàn)?, 次高值排序?yàn)?, 依此類推, 如表2中括號(hào)內(nèi)所示. AvgR表示所有算法在9個(gè)數(shù)據(jù)集中的平均排序.

由表2可見(jiàn),k-Mnv-Rep算法的AvgR值在所有評(píng)估指數(shù)中排序最高, 即k-Mnv-Rep算法在總體上優(yōu)于上述其他算法. 在8個(gè)數(shù)據(jù)集中,k-Mnv-Rep算法的每個(gè)評(píng)估指標(biāo)都優(yōu)于其他算法； 在數(shù)據(jù)集Function中, 只有PCAN算法的性能優(yōu)于k-Mnv-Rep算法, 但由于PCAN算法無(wú)法處理逆矩陣, 因此該算法不能處理所有數(shù)據(jù)聚類. 并且在數(shù)據(jù)集Messidor,Muta2,Process中, BAMIC-avgH算法優(yōu)于BAMIC-minH算法和BAMIC-maxH算法的AC值; 在數(shù)據(jù)集Muta1,Compon中, BAMIC-maxH算法優(yōu)于BAMIC-minH算法和BAMIC-avgH算法的AC指標(biāo); 在數(shù)據(jù)集Elephant,Web2,Musk1,Function中, BAMIC-minH算法的性能最優(yōu). BAMIC算法的其他指標(biāo)也出現(xiàn)了相同結(jié)果. 因此, BAMIC算法很難從3種距離中得出最佳距離.

表2 不同算法9個(gè)數(shù)值型數(shù)據(jù)集的比較結(jié)果

續(xù)表2

續(xù)表2

續(xù)表2

表3 5類實(shí)驗(yàn)中上述算法的平均排序值

(21)

圖1為8種算法對(duì)5個(gè)評(píng)估指標(biāo)進(jìn)行Bonferroni-Dunn實(shí)驗(yàn)的結(jié)果, 其中圓圈表示算法的平均排序, 線段表示臨界差CD.由圖1可見(jiàn),k-Mnv-Rep算法與CAN,PCAN,CLR-L1,CLR-L2四種算法的所有指標(biāo)均差異較大, 與BAMIC-minH,BAMIC-maxH,BAMIC-avgH三種算法則差異較小. 而B(niǎo)AMIC-minH,BAMIC-maxH,BAMIC-avgH三種算法的指標(biāo)幾乎無(wú)差異, CAN,PCAN,CLR-L1,CLR-L2四種算法的指標(biāo)幾乎無(wú)差異. 從平均排序結(jié)果可見(jiàn),k-Mnv-Rep算法性能最佳. 綜上, 因?yàn)閗-Mnv-Rep算法的排序較高、 差異值較大, 所以k-Mnv-Rep算法優(yōu)于其他對(duì)比算法.

圖1 8種算法在Bonferroni-Dunn實(shí)驗(yàn)中的5個(gè)指標(biāo)Fig.1 Five indexes of eight algorithms in Bonferroni-Dunn experiment

2.3 混合矩陣對(duì)象數(shù)據(jù)實(shí)驗(yàn)

下面進(jìn)行混合數(shù)值矩陣對(duì)象實(shí)驗(yàn), 評(píng)估k-Mv-Rep算法的有效性. 已知有真實(shí)混合矩陣對(duì)象數(shù)據(jù)集, 并已知k-Mv-Rep算法和k型算法的比較結(jié)果.

2.3.1 真實(shí)混合數(shù)據(jù)集

由于缺少公開(kāi)混合矩陣對(duì)象, 因此本文實(shí)驗(yàn)中使用真實(shí)混合數(shù)據(jù)集評(píng)估k-Mnv-Rep算法的有效性. 為評(píng)估上述算法, 應(yīng)對(duì)上述數(shù)據(jù)集進(jìn)行結(jié)構(gòu)預(yù)處理. 本文用多維尺度法對(duì)數(shù)據(jù)進(jìn)行可視化處理. 由式(12)可得出n_by_n型距離矩陣, 用多維尺度法主要是為了將該矩陣轉(zhuǎn)移到MATLAB生成的mdscale方程中, 從而獲得P維度中n個(gè)點(diǎn)的構(gòu)型.n點(diǎn)間的歐氏距離與n_by_n型距離矩陣中相應(yīng)相異點(diǎn)的單調(diào)變換大致相同, 因此, 可通過(guò)將n點(diǎn)可視化顯示數(shù)據(jù)的分布情況.設(shè)P=2, 對(duì)數(shù)據(jù)進(jìn)行可視化.在大多數(shù)實(shí)驗(yàn)案例中, 真實(shí)數(shù)據(jù)集的分布通常是無(wú)序的.利用可視化, 可通過(guò)刪除部分點(diǎn)獲得相對(duì)清晰的數(shù)據(jù)結(jié)構(gòu).

首先從數(shù)據(jù)集Author中選出相應(yīng)系統(tǒng)內(nèi)符合范圍x<0.55且y>0.16或x<0.55且y<-0.16的目標(biāo), 進(jìn)行可視化后成為一個(gè)新數(shù)據(jù)集, 然后對(duì)如圖2所示的新數(shù)據(jù)集進(jìn)行可視化. 利用可視化可推斷出聚類的數(shù)量和每個(gè)矩陣對(duì)象的標(biāo)簽信息, 數(shù)據(jù)集Author信息列于表4.

圖2 數(shù)據(jù)集Author的分布Fig.2 Distribution of data set Author

表4 數(shù)據(jù)集Author信息

2.3.2 對(duì)比結(jié)果分析

已知部分聚類算法無(wú)法直接處理混合矩陣目標(biāo), 所以應(yīng)在該子部分內(nèi)應(yīng)用k型算法. 由于矩陣對(duì)象本質(zhì)上是矩陣而非向量, 因此需要將矩陣對(duì)象轉(zhuǎn)換為能使用k型算法的形式. 混合矩陣對(duì)象范疇屬性的屬性值由模式表示, 數(shù)值屬性的屬性值由中值表示. 這樣即可將混合矩陣對(duì)象變形為向量, 從而可以使用k型算法處理矩陣對(duì)象數(shù)據(jù)集.

分別運(yùn)行k型算法和k-Mv-Rep算法50次, 取實(shí)驗(yàn)結(jié)果的中值作為最終結(jié)果. 設(shè)k-Mv-Rep算法的參數(shù)ε=0.2,k型算法γ的參數(shù)值為文獻(xiàn)[16]中所有數(shù)值屬性的標(biāo)準(zhǔn)差, 表5列出了數(shù)據(jù)集Author中k型算法和k-Mv-Rep兩種算法的比較結(jié)果. 由表5可見(jiàn),k-Mv-Rep算法的5個(gè)評(píng)估指標(biāo)值均優(yōu)于k型算法, 并且k-Mv-Rep算法比k型算法的精確度約高13%. 因此,k-Mv-Rep算法優(yōu)于k型算法.

表5 兩種算法在數(shù)據(jù)集Author中的實(shí)驗(yàn)結(jié)果對(duì)比

2.4 參數(shù)ε對(duì)算法的影響

k型算法和k-Mv-Rep算法的參數(shù)ε已知, 并作為終止程序的控制條件. 當(dāng)目標(biāo)方程的變換小于ε時(shí), 程序終止. 因此, 不同參數(shù)大小可能會(huì)產(chǎn)生不同的聚類結(jié)果, 如何確定該參數(shù)十分重要. 分別在相應(yīng)數(shù)據(jù)集內(nèi)按照不同公式運(yùn)行k型算法和k-Mv-Rep算法各30次, 公式大小變化以0.05為梯度, 由0.05增加至0.35, 并記錄AC的中值和迭代次數(shù), 結(jié)果分別如圖3和圖4所示.

圖3 不同ε在10個(gè)數(shù)據(jù)集內(nèi)的準(zhǔn)確率Fig.3 Accuracy of differnt ε in ten data sets

圖4 不同ε在10個(gè)數(shù)據(jù)集內(nèi)的迭代次數(shù)Fig.4 Iterations of differnt ε in ten data sets

由圖3可見(jiàn), 隨著ε增大, AC在10個(gè)數(shù)據(jù)集內(nèi)均有輕微浮動(dòng), 但總體穩(wěn)定. 由圖4可見(jiàn), 隨著ε增大, 迭代次數(shù)在10個(gè)數(shù)據(jù)集內(nèi)呈總體下降趨勢(shì), 一般當(dāng)ε>0.2時(shí), 迭代次數(shù)下降趨勢(shì)較緩. 在上述兩種算法中, 綜合AC結(jié)果和迭代結(jié)果, 令ε=0.2.

2.5 聚合性檢驗(yàn)

因?yàn)楸疚奶岢龅挠糜诟戮垲愔行牡膋-Mv-Rep算法和k-Mnv-Rep算法均屬于啟發(fā)式算法, 所以要對(duì)這兩種算法進(jìn)行聚合性檢驗(yàn), 以保證其合理性. 在所有實(shí)驗(yàn)中, 記錄目標(biāo)方程值和所有迭代次數(shù). 圖5為目標(biāo)方程值變化與k-Mv-Rep算法迭代的比值. 由圖5可見(jiàn), 隨著迭代次數(shù)增加, 目標(biāo)方程值呈下降趨勢(shì). 在10個(gè)數(shù)據(jù)集內(nèi)的聚合性檢驗(yàn)結(jié)果也同樣證明了該結(jié)論.

圖5 目標(biāo)方程值變化與k-Mv-Rep算法迭代的比值Fig.5 Ratio of value change of objective equation to iteration of k-Mv-Rep algorithm

綜上所述, 為解決數(shù)據(jù)的稀疏性和高維問(wèn)題, 并有效反映聚類中心與聚類內(nèi)矩陣對(duì)象的分布, 本文提出了一種基于k多數(shù)值表示的混合矩陣對(duì)象數(shù)據(jù)聚類方法. 由真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可得如下結(jié)論：

1) 本文聚類算法對(duì)于稀疏數(shù)據(jù)集和高維數(shù)據(jù)集均能保證良好的聚類效果, 證明該方法能解決數(shù)據(jù)集的稀疏和高維問(wèn)題；

2) 本文算法對(duì)于不同的數(shù)據(jù)集均實(shí)現(xiàn)了精度較高的聚類, 證明該算法的泛化能力較強(qiáng), 能有效反映聚類中心與聚類內(nèi)矩陣對(duì)象的分布；

3) 本文算法的聚類準(zhǔn)確度對(duì)于參數(shù)具有良好的魯棒性, 并且聚合性檢驗(yàn)證明了算法的合理性.