周燕茹

(巢湖學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽 巢湖 238000)

隨著數(shù)據(jù)庫管理系統(tǒng)的應(yīng)用范圍越來越廣，企業(yè)或其他機(jī)構(gòu)均積攢了海量數(shù)據(jù)[1].對(duì)數(shù)據(jù)實(shí)施聚類統(tǒng)計(jì)處理能夠判斷數(shù)據(jù)間的相似度，從而獲取重要的數(shù)據(jù)特征信息.然而，數(shù)據(jù)維度與稀疏度成反比，數(shù)據(jù)對(duì)象會(huì)分布于各個(gè)維度子空間內(nèi)，傳統(tǒng)的聚類方法在這方面的聚類效果較差，原因是距離函數(shù)容易無效、算法復(fù)雜度高與聚類中心選擇過于隨機(jī)等[2-3].且傳統(tǒng)的數(shù)據(jù)分析工具僅具備查詢與統(tǒng)計(jì)等作用，難以高效聚類高維稀疏數(shù)據(jù).

一直以來，高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)方法始終是數(shù)據(jù)挖掘方面的一大難題[4].邵俊健[5]等人針對(duì)高維數(shù)據(jù)聚類效果較差問題，設(shè)計(jì)了一種具有抗噪性能適用高維數(shù)據(jù)的增量式聚類統(tǒng)計(jì)方法，提升其抗噪性能與聚類效果；武森[6]等人針對(duì)數(shù)據(jù)對(duì)象易于劃分至更大類內(nèi)問題，設(shè)計(jì)了一種基于拓展差異度的高維數(shù)據(jù)聚類統(tǒng)計(jì)方法，有效縮短聚類時(shí)間.然而在實(shí)際應(yīng)用中發(fā)現(xiàn)，隨著現(xiàn)階段數(shù)據(jù)量及其復(fù)雜度的提高，上述兩種方法在聚類統(tǒng)計(jì)稀疏度較低的數(shù)據(jù)集時(shí)效果仍然較差.

模糊數(shù)學(xué)是一種分析模糊性情況的數(shù)學(xué)方法，主要用于模糊聚類分析與模糊綜合評(píng)判等.其中，最為常用的是模糊C均值算法(Fuzzy C-means，F(xiàn)CM).為此，本研究以FCM算法為基礎(chǔ)，設(shè)計(jì)了基于模糊數(shù)學(xué)的高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)方法，以期提升聚類統(tǒng)計(jì)效果.

1 高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)方法設(shè)計(jì)

1.1 FCM算法

FCM算法是模糊數(shù)學(xué)的分支，該算法以模糊思想表示對(duì)象和簇間的關(guān)系.對(duì)象y對(duì)于集合A的模糊隸屬度函數(shù)是hA(y),hA(y)∈[0,1]，在數(shù)據(jù)聚類過程中，將聚類獲取的簇當(dāng)作模糊集合，F(xiàn)CM算法目標(biāo)函數(shù)的表達(dá)公式如下：

(1)

其中，聚類中心編號(hào)為i；數(shù)據(jù)點(diǎn)編號(hào)為j；模糊組的聚類中心為ci；hij∈[0,1]；加權(quán)指數(shù)為m∈(1,∞)；i與j之間的歐幾里德距離為dij=‖yj-ci‖2.

FCM算法的具體處理步驟如下：

步驟1：獲取聚類數(shù)量c(2≤c≤n)，樣本數(shù)量為n，確定m(2≤m≤∞)的值；初始化隸屬矩陣H得到H(T)，將T作為迭代的標(biāo)記.初始化需要符合的要求如下：

(2)

(3)

(4)

其中，聚類中心編號(hào)是k.

步驟4：對(duì)比分析每次優(yōu)化后隸屬矩陣的差距，若‖H(T+1)-H(T)‖<εT，那么完成聚類統(tǒng)計(jì)，隸屬矩陣差距的標(biāo)準(zhǔn)數(shù)值是εr；若‖H(T+1)-H(T)‖>εT，設(shè)置T=T+1，返回至步驟2.

1.2 改進(jìn)的模糊聚類算法與聚類統(tǒng)計(jì)方法設(shè)計(jì)

1.2.1 優(yōu)化初始聚類中心

為避免陷入局部最優(yōu)，在FCM算法運(yùn)算過程中，需要反復(fù)初始化聚類中心，延長聚類統(tǒng)計(jì)時(shí)間.為解決這一問題，本研究利用特殊的初始聚類中心選取方法，獲取數(shù)據(jù)集凸包邊界中的初始聚類中心，確保各聚類中心距離較遠(yuǎn)，避免出現(xiàn)局部最小值的情況.具體步驟如下：

步驟1：求解數(shù)據(jù)集的平均值，將與該值距離最遠(yuǎn)的數(shù)據(jù)點(diǎn)當(dāng)成首簇聚類中心；

步驟2：計(jì)算首簇聚類中心與全部數(shù)據(jù)點(diǎn)間的距離；

步驟3：按照貪心選擇策略選取首簇聚類中心以及平均值較遠(yuǎn)的數(shù)據(jù)點(diǎn)，將其當(dāng)成第二簇聚類中心，直到得到k簇聚類中心為止；

步驟4：以平均值為目標(biāo)，令全部聚類中心向其移動(dòng)，移動(dòng)間距為兩者距離的10%，提升聚類的收斂速度[7].

1.2.2 類間中心點(diǎn)影響

由于FCM算法并未分析各類別數(shù)據(jù)簇中心點(diǎn)間的彼此排斥影響，導(dǎo)致該算法難以對(duì)高維稀疏數(shù)據(jù)實(shí)施聚類，通過添加權(quán)重機(jī)制[8]改進(jìn)FCM算法，使其適用于高維稀疏數(shù)據(jù)的聚類統(tǒng)計(jì).將已知類與未知類均添加至FCM的目標(biāo)函數(shù)內(nèi)，變更后的目標(biāo)函數(shù)為：

(5)

其中，未知類內(nèi)第i簇聚類中心為Pi；已知類內(nèi)第k簇聚類中心為Rk；權(quán)重為wj；第j個(gè)數(shù)據(jù)點(diǎn)包含在i內(nèi)的程度為αij；j包含在k內(nèi)的程度為βkj；聚類中心數(shù)量為l.α與β需符合的條件如下：

(6)

通過拉格朗日乘子法計(jì)算：

(7)

其中，拉格朗日乘法算子為λ.

計(jì)算G(H,T,P,λ)內(nèi)變量Pi的偏導(dǎo)，過程如下：

(8)

根據(jù)公式(8)可得到：

(9)

依據(jù)同樣方法求解G(H,T,P,λ)內(nèi)變量αij與βkj的偏導(dǎo)，公式如下：

(10)

(11)

其中，簇的編號(hào)分別為a與b.

通過引入權(quán)重機(jī)制提升FCM算法中各類簇的聚類中心競(jìng)爭(zhēng)剩余數(shù)據(jù)點(diǎn)間重疊范圍內(nèi)的特征空間.通過加權(quán)指數(shù)m決定簇心間的排斥力，該值與排斥力成正比[9].

1.2.3 優(yōu)化余弦距離

雖然FCM算法具備較優(yōu)的聚類低維數(shù)據(jù)集性能，但在聚類高維稀疏數(shù)據(jù)時(shí)，其效果不佳[10].由余弦距離替換FCM算法中的歐幾里德距離，計(jì)算公式如下：

(12)

(13)

根據(jù)公式(13)可得到：

(14)

在每個(gè)數(shù)據(jù)塊很小(對(duì)象很少)的情況下，為各簇劃分的對(duì)象數(shù)量同樣較少[11]，說明χc也較小.針對(duì)各簇僅存在一個(gè)對(duì)象的現(xiàn)象，獲?。?/p>

(15)

其中，高維稀疏數(shù)據(jù)向量為yj，該向量中僅包含非常少的非零元素.這就說明yj和剩余數(shù)據(jù)間常用詞的數(shù)量明顯低于各數(shù)據(jù)內(nèi)存在的詞數(shù)量[12].通過二進(jìn)制方法加權(quán)內(nèi)yj的詞，若yj內(nèi)存在單詞，那么yji=1；若yj內(nèi)不存在單詞，那么xji=0，針對(duì)這一情況可獲取：

(16)

得到：

(17)

在高維稀疏數(shù)據(jù)內(nèi)數(shù)據(jù)塊不大的情況下，通過‖φc‖2確定d(xj,φc).同時(shí)，由于‖φc‖2的值與yj沒有關(guān)系，為避免全部對(duì)象劃分到和聚類中心存在最小歐幾里德距離的相同簇內(nèi)，在各次迭代結(jié)束時(shí)[13]，需標(biāo)準(zhǔn)化處理聚類中心，公式如下：

(18)

標(biāo)準(zhǔn)化處理聚類中心時(shí)，對(duì)象與聚類中心的距離通過公式(12)右側(cè)的最后一項(xiàng)確定，它屬于yj與φc間的內(nèi)積，確保FCM算法中的h存在意義，針對(duì)FCM算法存在：

(19)

更改上述公式獲?。?/p>

(20)

(21)

為解決模糊聚類內(nèi)yj在全部簇內(nèi)的隸屬度非常接近問題，需要?dú)w一化處理各目標(biāo)矢量[15]，使其變成單位范數(shù)‖yj‖=1.歐幾里德距離公式變更為：

(22)

在yj歸一化成單位長度的情況下，F(xiàn)CM算法的全部迭代過程中，優(yōu)化完成的聚類中心歸一化已改為基于余弦距離的FCM算法.基于此，以余弦距離替換原有的歐幾里德距離，提高高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)效果.由此，通過優(yōu)化模糊數(shù)學(xué)中的FCM算法實(shí)現(xiàn)了對(duì)高維稀疏數(shù)據(jù)的聚類統(tǒng)計(jì).

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

2.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證上述設(shè)計(jì)的基于模糊數(shù)學(xué)的高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)方法的實(shí)際應(yīng)用性能，設(shè)計(jì)如下實(shí)驗(yàn).將文獻(xiàn)[5]中的具有抗噪性能適用高維數(shù)據(jù)的增量式聚類統(tǒng)計(jì)方法(方法1)和文獻(xiàn)[6]中的基于拓展差異度的高維數(shù)據(jù)聚類統(tǒng)計(jì)方法(方法2)作為對(duì)比，要個(gè)具體點(diǎn)的方向本文方法共同完成性能驗(yàn)證.

將HR(Hit-rate，命中率)與ARI(Adjusted Rand Index，調(diào)整蘭德指數(shù))作為衡量3種方法聚類統(tǒng)計(jì)性能的指標(biāo)，HR的取值范圍是[0,0.3]，ARI的取值范圍是[0,1]，兩者的取值均與聚類效果成正比.其中，HR的取值高于0.2則代表該方法具備較優(yōu)的聚類效果，ARI的取值高于0.5則代表該方法具備較優(yōu)的聚類效果.

在某網(wǎng)絡(luò)中隨機(jī)選取6個(gè)真實(shí)數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象，數(shù)據(jù)集的具體信息如表1所示.

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

2.2 性能分析

為確保3種方法具備可比性，在隨機(jī)分塊完成時(shí)，每次使用3種方法過程中所利用的隨機(jī)分塊需要具備一致性.利用3種方法聚類統(tǒng)計(jì)上述數(shù)據(jù)集，測(cè)試3種方法在數(shù)據(jù)總量不同分塊時(shí)的ARI值，測(cè)試結(jié)果如表2所示.

表2 3種方法在不同分塊時(shí)的ARI值

當(dāng)數(shù)據(jù)集維度較小時(shí)，3種方法分塊數(shù)量越大，ARI值越大，聚類統(tǒng)計(jì)效果越好；當(dāng)數(shù)據(jù)集維度較大時(shí)，3種方法的分塊數(shù)量越小，ARI值越大，聚類統(tǒng)計(jì)效果越好.合理劃分分塊大小，可提升3種方法的聚類效果.根據(jù)表2可知，當(dāng)數(shù)據(jù)集維度以及分塊比例不同時(shí)，本文方法的ARI值明顯高于另外兩種方法，本文方法的ARI值波動(dòng)范圍是0.50至0.81，方法1的ARI值波動(dòng)范圍是0.06至0.54，方法2的ARI值波動(dòng)范圍是0.13至0.58.上述實(shí)驗(yàn)證明：本文方法在不同數(shù)據(jù)集維度及分塊比例時(shí)的ARI值最高，且最低ARI值也高于標(biāo)準(zhǔn)值0.5，聚類統(tǒng)計(jì)效果較優(yōu).

測(cè)試3種方法在聚類統(tǒng)計(jì)不同稀疏度等級(jí)的數(shù)據(jù)集時(shí)的HR值及執(zhí)行時(shí)間，測(cè)試結(jié)果如圖1與表3所示.

稀疏度等級(jí)圖1 HR值測(cè)試結(jié)果

數(shù)據(jù)集稀疏度等級(jí)越低代表其越稀疏.由圖1可知，隨著稀疏度等級(jí)的逐漸提升，3種方法的HR值均有所增長，在不同稀疏度等級(jí)時(shí)本文方法的HR值均最高、變化幅度最小，且最低HR值也在0.2之上，其余兩種方法僅有在稀疏度等級(jí)為0.6時(shí)其HR值才超過0.2.上述實(shí)驗(yàn)證明：在聚類統(tǒng)計(jì)不同稀疏度等級(jí)的數(shù)據(jù)集時(shí)，本文方法的HR值最高，且受稀疏度影響較小.

表3 聚類統(tǒng)計(jì)執(zhí)行時(shí)間(μs)

根據(jù)表3可知，在數(shù)據(jù)集稀疏度等級(jí)較低時(shí)，方法1與方法2無法完成聚類統(tǒng)計(jì).隨著稀疏度等級(jí)逐漸提升，3種方法的聚類統(tǒng)計(jì)執(zhí)行時(shí)間逐漸縮短，本文方法的執(zhí)行時(shí)間最少.上述實(shí)驗(yàn)證明：本文方法適用于稀疏度較低的數(shù)據(jù)聚類統(tǒng)計(jì)，且聚類統(tǒng)計(jì)效率較高.

3 結(jié) 論

設(shè)計(jì)了基于模糊數(shù)學(xué)的高維稀疏數(shù)據(jù)聚類統(tǒng)計(jì)方法，以FCM算法為基礎(chǔ)，在此基礎(chǔ)上加以改進(jìn)，解決局部最優(yōu)問題，合理劃分?jǐn)?shù)據(jù)集的分塊比例，從而提升了聚類統(tǒng)計(jì)效果，也降低了數(shù)據(jù)集稀疏度等級(jí)對(duì)聚類統(tǒng)計(jì)效果的影響，提升了聚類統(tǒng)計(jì)效率.