基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類研究

張福華，劉麗，朱俊東，朱再新，余大權(quán)

（安徽明生恒卓科技有限公司，安徽 合肥 230000）

近年來，信息技術(shù)不斷發(fā)展，互聯(lián)網(wǎng)信息技術(shù)、工業(yè)信息技術(shù)、通信信息技術(shù)等行業(yè)迅速崛起，這些行業(yè)產(chǎn)生了大量的數(shù)據(jù)。在當(dāng)前階段，主要是通過自適應(yīng)聚類對(duì)數(shù)據(jù)進(jìn)行整合。數(shù)據(jù)通常以靜態(tài)的形式存放在數(shù)據(jù)庫中，以便隨時(shí)提取。但由于信息產(chǎn)生方式、性質(zhì)以及數(shù)據(jù)庫的存儲(chǔ)量是有限的，數(shù)據(jù)的存放只能是短暫性的，并不能長(zhǎng)期存放在數(shù)據(jù)庫中，而在應(yīng)對(duì)大量的數(shù)據(jù)產(chǎn)生時(shí)，數(shù)據(jù)庫無法永久保存所有數(shù)據(jù)，因此數(shù)據(jù)的自適應(yīng)聚類便成為解決該問題的方式。

為了解決上述問題，一些學(xué)者進(jìn)行了數(shù)據(jù)自適應(yīng)聚類相關(guān)研究。文獻(xiàn)[1]提出了基于信息熵加權(quán)的空間聚類算法，通過引入信息熵權(quán)重約束模式，完成對(duì)數(shù)據(jù)的自適應(yīng)聚類，但此方式只適用于少量信息的多次自適應(yīng)聚類，在應(yīng)對(duì)大量數(shù)據(jù)時(shí)仍無法很好地進(jìn)行聚類，導(dǎo)致聚類準(zhǔn)確性變差。文獻(xiàn)[2]提出了基于信息流加權(quán)的集成分類算法，通過引入集成分類算法賦予數(shù)據(jù)更高的權(quán)重，并根據(jù)每個(gè)數(shù)據(jù)類別特征構(gòu)建分類器，以此完成數(shù)據(jù)的自適應(yīng)聚類，但此方式對(duì)于大量雜亂的數(shù)據(jù)無法做到精準(zhǔn)聚類，實(shí)際應(yīng)用效果并不好。

針對(duì)目前聚類方法的漂移點(diǎn)篩選能力和抗干擾能力較弱的問題，設(shè)計(jì)了一種基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類方法，并通過實(shí)驗(yàn)對(duì)該方法的有效性進(jìn)行了驗(yàn)證。

1 基于信息熵的數(shù)據(jù)屬性加權(quán)

利用信息熵的加權(quán)對(duì)混亂數(shù)據(jù)進(jìn)行自適應(yīng)聚類，在構(gòu)建信息熵的加權(quán)機(jī)制前，設(shè)計(jì)一種混亂數(shù)據(jù)相異性度量方式[3-4]。

由于所研究的數(shù)據(jù)為混亂數(shù)據(jù)，因此采用K-P算法統(tǒng)計(jì)當(dāng)前數(shù)據(jù)集中相似數(shù)據(jù)出現(xiàn)的頻率，并設(shè)定模糊類中心，以此能夠更加直觀地度量數(shù)據(jù)之間的相異性。

根據(jù)信息熵權(quán)重建立模糊類中心，計(jì)算公式如式（1）所示：

其中，xi表示第i個(gè)數(shù)據(jù)集；C表示數(shù)據(jù)集數(shù)據(jù)的所屬類別。

而數(shù)據(jù)集中的單一對(duì)象也可表示為模糊類中心的形式，該式為模糊類中心一種特殊的表示形式[5-6]。

信息熵具有兩種形式，分別為數(shù)值型與分類型，針對(duì)數(shù)值型的數(shù)據(jù)屬性進(jìn)行加權(quán)時(shí)，需應(yīng)用到二階Renyi 熵，Renyi 熵具有良好的計(jì)算特性[7-8]。假設(shè)X是由獨(dú)立分布的N個(gè)數(shù)據(jù)對(duì)象組成的數(shù)據(jù)集合，計(jì)算熵值f(X)如式（2）所示：

其中，Wi為parzen 窗口函數(shù)，通常為高斯核函數(shù)。通過parzen 窗口估計(jì)法得到的熵通常為正數(shù)，上述定義給出的類內(nèi)熵值反映了在聚類分化結(jié)果中某一類的值在不同屬性數(shù)據(jù)情況下的分布狀態(tài)，即一個(gè)類的類內(nèi)熵越小，聚類過程的數(shù)據(jù)屬性權(quán)重越大[9-10]。

互補(bǔ)信息熵計(jì)算公式如式（3）所示：

根據(jù)以上分析可知，通過信息匹配得到數(shù)據(jù)熵，在完成數(shù)據(jù)聚類之后確定信息的不同屬性，根據(jù)不同屬性實(shí)現(xiàn)數(shù)據(jù)分離，從而實(shí)現(xiàn)數(shù)據(jù)屬性加權(quán)。

2 基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類

在完成基于信息熵的數(shù)據(jù)屬性加權(quán)后，對(duì)數(shù)據(jù)進(jìn)行自適應(yīng)聚類，聚類流程如圖1 所示。

圖1 基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類流程

根據(jù)圖1 可知，聚類過程首先構(gòu)建一個(gè)數(shù)據(jù)自適應(yīng)聚類器，然后完成聚類模型更新，同時(shí)進(jìn)行基礎(chǔ)聚類器更新和權(quán)重更新實(shí)現(xiàn)數(shù)據(jù)自適應(yīng)聚類。

構(gòu)造一個(gè)數(shù)據(jù)自適應(yīng)聚類器流程，假設(shè)E為一個(gè)由k個(gè)基礎(chǔ)聚類器y組成的自適應(yīng)聚類器，設(shè)S表示數(shù)據(jù)總量，將S平均分成大小相等的數(shù)據(jù)塊B，此時(shí)自適應(yīng)聚類器開始初始化，當(dāng)一個(gè)新的數(shù)據(jù)塊到達(dá)時(shí)。若數(shù)據(jù)塊中的所有數(shù)據(jù)都能夠被識(shí)別，則可將該數(shù)據(jù)塊轉(zhuǎn)變?yōu)橐粋€(gè)基礎(chǔ)聚類器，當(dāng)基礎(chǔ)聚類器的個(gè)數(shù)未達(dá)到閾值k時(shí)，將不斷轉(zhuǎn)化可識(shí)別的數(shù)據(jù)塊為基礎(chǔ)聚類器，直到基礎(chǔ)聚類器的數(shù)量達(dá)到k個(gè)[11-12]。自適應(yīng)聚類器由多個(gè)基礎(chǔ)聚類器組成，若要建立一個(gè)性能完好的自適應(yīng)聚類器，則需要保證基礎(chǔ)聚類器具有多樣性與準(zhǔn)確性。滿足基礎(chǔ)聚類器的多樣性條件是數(shù)據(jù)塊都建立在不同維度的子空間中，因此每個(gè)數(shù)據(jù)塊的維度與空間特征都是隨機(jī)的。

為了解決數(shù)據(jù)不穩(wěn)定的問題，需要使用IEWU算法對(duì)自適應(yīng)聚類器進(jìn)行更新，更新分為基礎(chǔ)聚類器的更新以及基礎(chǔ)聚類器權(quán)重的更新兩部分。

由于IEWU 算法的中心思想與自適應(yīng)聚類器的構(gòu)建過程相似，因此在相似數(shù)據(jù)的數(shù)量達(dá)到一定程度時(shí)便可組建一個(gè)數(shù)據(jù)塊，通過數(shù)據(jù)塊得到一個(gè)基礎(chǔ)聚類器。基礎(chǔ)聚類器的權(quán)重隨著數(shù)據(jù)塊屬性與性能的變化而變化，以此解決數(shù)據(jù)不穩(wěn)定問題。數(shù)據(jù)塊的大小決定了基礎(chǔ)聚類器的性能。較大的數(shù)據(jù)塊可以組建成性能更好的基礎(chǔ)聚類器，分類性能更佳。因此在基礎(chǔ)聚類器更新過程中，需要篩選出較大的數(shù)據(jù)塊來提升基礎(chǔ)聚類器的性能[13-14]。

由于使用IEWU 算法構(gòu)建了一個(gè)混合類型的自適應(yīng)聚類器，因此在IEWU 算法應(yīng)用過程中，需要不利用新的基礎(chǔ)聚類器來替換舊的基礎(chǔ)聚類器，并需要對(duì)已有的基礎(chǔ)聚類器進(jìn)行學(xué)習(xí)，結(jié)合信息熵對(duì)每個(gè)基礎(chǔ)聚類器的權(quán)重進(jìn)行更新。通過此方式可以篩選出性能更好的基礎(chǔ)聚類器，提高整個(gè)自適應(yīng)聚類器在面對(duì)不穩(wěn)定數(shù)據(jù)時(shí)的處理能力[15]。信息熵為此次研究的重要參數(shù)，利用IEWU 算法計(jì)算信息熵的計(jì)算公式如下：

式中，H表示信息熵；P表示聚類器參數(shù)。采用IEWU 算法可求得當(dāng)前數(shù)據(jù)屬性的信息熵值，由于信息熵能夠表示聚類結(jié)果的不確定性，因此信息熵越大，聚類結(jié)果的不確定性越強(qiáng)。當(dāng)利用IEWU算法所求得的信息熵足夠小時(shí)，即可判定當(dāng)前聚類結(jié)果準(zhǔn)確。由于不同數(shù)據(jù)的信息熵都不相同，因此采用動(dòng)態(tài)自適應(yīng)的方式對(duì)信息熵進(jìn)行更新，信息熵更新閾值計(jì)算公式如下：

式中，em為信息熵更新閾值；et為信息熵的平均值；en為信息熵的最小值，et與en的值會(huì)隨著數(shù)據(jù)屬性的不斷變化而發(fā)生改變。當(dāng)IEWU 算法所求得的信息熵值小于em時(shí)，則信息熵更新停止。

通?；A(chǔ)聚類器剛建立時(shí)會(huì)被賦予最高的權(quán)重值，隨著更多數(shù)據(jù)塊的到來，每個(gè)基礎(chǔ)聚類器會(huì)根據(jù)信息熵的閾值判斷自身是否處于性能較好的基礎(chǔ)聚類器，并實(shí)時(shí)調(diào)整自身權(quán)重，使得性能較好的基礎(chǔ)聚類器能夠被識(shí)別出，不斷淘汰性能較差的基礎(chǔ)聚類器[16]。

自適應(yīng)聚類器的聚類結(jié)果由所有列舉出的聚類器進(jìn)行加權(quán)投票，其中IEWU 算法還使用了拋棄策略，由于基礎(chǔ)聚類器的性能有好壞之分，性能較差的基礎(chǔ)聚類器由于其不穩(wěn)定性，參與投票后更容易導(dǎo)致聚類結(jié)果更加不準(zhǔn)確，因此參與投票的基礎(chǔ)聚類器都是性能較優(yōu)的。給予一個(gè)固定的權(quán)重閾值，該算法只將性能在權(quán)重閾值以上的基礎(chǔ)聚類器加入投票的排列之中，以此實(shí)現(xiàn)數(shù)據(jù)的自適應(yīng)聚類[17]。

3 實(shí)驗(yàn)研究

為了驗(yàn)證所提出的基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類方法的實(shí)際應(yīng)用效果，進(jìn)行了相關(guān)實(shí)驗(yàn)測(cè)試。在實(shí)驗(yàn)過程中，選用此次研究的自適應(yīng)聚類方法和傳統(tǒng)的基于人工合成的自適應(yīng)聚類方法、基于數(shù)據(jù)分析的數(shù)據(jù)自適應(yīng)聚類方法進(jìn)行實(shí)驗(yàn)對(duì)比。

為了更好地保證實(shí)驗(yàn)效果，同時(shí)選用RanTree、SEAg、poker 三個(gè)不同的數(shù)據(jù)塊進(jìn)行實(shí)驗(yàn)對(duì)比，探究不同數(shù)據(jù)塊下的聚類準(zhǔn)確性。得到的實(shí)驗(yàn)結(jié)果如圖2-圖4 所示。

圖2 RanTree數(shù)據(jù)塊下聚類準(zhǔn)確率

根據(jù)圖2 可知，由于RanTree 數(shù)據(jù)塊的信息環(huán)境極其不穩(wěn)定，因此三種聚類方法的聚類準(zhǔn)確率存在明顯差異。對(duì)于RanTree 數(shù)據(jù)塊，與實(shí)驗(yàn)對(duì)比方法相比較，所提出的聚類方法始終保持著較高的聚類準(zhǔn)確性。此次提出的聚類方法通過引入信息熵進(jìn)行數(shù)據(jù)聚類，在不平穩(wěn)的環(huán)境下也能夠很好地適應(yīng)外界變化，而傳統(tǒng)的聚類方法在聚類過程中，容易受到外界因素影響，在不穩(wěn)定的環(huán)境下可能出現(xiàn)準(zhǔn)確率上升或下降的問題，難以完成快速適應(yīng)，甚至?xí)霈F(xiàn)數(shù)據(jù)漂移，導(dǎo)致聚類準(zhǔn)確率下降。

與RanTree 數(shù)據(jù)塊相比，SEAg 數(shù)據(jù)塊更加穩(wěn)定，通過分析圖3 可以發(fā)現(xiàn)，三種聚類方法的準(zhǔn)確率都相對(duì)較高，但是在遇見漂移點(diǎn)時(shí)，三種聚類方法的準(zhǔn)確率都有所下降，此次提出的聚類方法聚類準(zhǔn)確率僅有2%～5%的下降，而傳統(tǒng)的基于人工合成的自適應(yīng)聚類方法準(zhǔn)確率下降超過20%，基于數(shù)據(jù)分析的數(shù)據(jù)自適應(yīng)聚類方法準(zhǔn)確率下降超過50%，由此可見，所提出的聚類方法抗干擾能力更強(qiáng)。

圖3 SEAg數(shù)據(jù)塊下聚類準(zhǔn)確率

根據(jù)圖4 可知，poker 數(shù)據(jù)塊存在的漂移點(diǎn)極少，但是聚類過程容易受到外界干擾因素影響，因此三種聚類方法在前期的聚類準(zhǔn)確率都相對(duì)較低，但是隨著聚類時(shí)間的增加，此次所提出的聚類方法通過信息熵更新權(quán)重消除外界干擾，聚類準(zhǔn)確率大大增加，而傳統(tǒng)方法依舊難以滿足精準(zhǔn)聚類要求，導(dǎo)致聚類質(zhì)量下降。

圖4 poker數(shù)據(jù)塊下聚類準(zhǔn)確率

在上述基礎(chǔ)上，為了進(jìn)一步驗(yàn)證三種方法的聚類性能，比較了三種方法的數(shù)據(jù)聚類時(shí)間，比較結(jié)果如表1 所示。

表1 數(shù)據(jù)聚類時(shí)間比較

分析表1 中的數(shù)據(jù)可知，隨著實(shí)驗(yàn)數(shù)據(jù)量的增加，不同方法的數(shù)據(jù)聚類耗時(shí)均呈現(xiàn)上升趨勢(shì)，當(dāng)實(shí)驗(yàn)數(shù)據(jù)量達(dá)到100 GB 的情況下，三種方法的聚類時(shí)間均達(dá)到最大值。其中信息熵更新權(quán)重聚類法的聚類時(shí)間最大值為1.25 s，平均值為0.71 s；人工合成聚類法的聚類時(shí)間最大值為1.91 s，平均值為1.29 s；數(shù)據(jù)分析聚類法的聚類時(shí)間最大值為2.56 s，平均值為1.58 s；基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類方法的聚類時(shí)間更短，效率更高。

4 結(jié)束語

該文以解決當(dāng)前聚類方法的漂移點(diǎn)篩選能力和抗干擾能力較弱的問題作為研究目標(biāo)，設(shè)計(jì)了一種基于信息熵更新權(quán)重的數(shù)據(jù)自適應(yīng)聚類方法。通過混亂數(shù)據(jù)相異性度量完成數(shù)據(jù)屬性加權(quán)，構(gòu)建基礎(chǔ)聚類器，利用多個(gè)基礎(chǔ)聚類器構(gòu)建自適應(yīng)聚類器，以此達(dá)到自適應(yīng)聚類數(shù)據(jù)的最終目標(biāo)。實(shí)驗(yàn)表明，此次提出的基于信息熵更新權(quán)重的自適應(yīng)聚類方法解決了當(dāng)前方法中存在的問題，能夠在數(shù)據(jù)自適應(yīng)聚類領(lǐng)域得到廣泛應(yīng)用，以此提升數(shù)據(jù)的聚類質(zhì)量。