基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法研究

張勇 陳菊

摘 ?要： 典型網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法采用軟子空間聚類算法，根據(jù)目標(biāo)函數(shù)最優(yōu)解判斷聚類是否最優(yōu)，最優(yōu)解計(jì)算過程容易過度擬合陷入局部最優(yōu)，導(dǎo)致分類結(jié)果精度低。故文中提出基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法，根據(jù)信息增益選擇決策樹節(jié)點(diǎn)，在信息增益基礎(chǔ)上添加分裂信息項(xiàng)防止決策樹節(jié)點(diǎn)過度分類，獲取不同樹節(jié)點(diǎn)屬性類別劃分結(jié)果。在此基礎(chǔ)上采用后剪枝技術(shù)刪除含有噪音和干擾屬性結(jié)點(diǎn)，將包含樣本數(shù)量最多的分類結(jié)果視為網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的分類結(jié)果。仿真實(shí)驗(yàn)結(jié)果表明，所提方法聚類分析正確率隨著網(wǎng)絡(luò)高維數(shù)據(jù)集維數(shù)的增加而增加，且隨樣本數(shù)量增加的同時(shí)運(yùn)行時(shí)間增長幅度較低，用時(shí)較短，是一種應(yīng)用價(jià)值高的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法。

關(guān)鍵詞： 聚類方法; 軟子空間; 高維數(shù)據(jù); 決策樹; 信息增益; 仿真分析

中圖分類號(hào)： TN711?34; TP311 ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）20?0081?03

Research on ?network high?dimensional data soft subspace clustering

method based on decision tree

ZHANG Yong， CHEN Ju

（College of Medical Information Engineering， Chengdu University of Traditional Chinese Medicine， Chengdu 611137， China）

Abstract： The typical network high?dimensional data soft subspace clustering method is used to determine whether the clustering is optimal or not according to the optimal solution of the objective function， which adopts soft subspace clustering algorithm. The calculation process of the optimal solution is easy to fall into the local optimum by overfitting， which may result in low accuracy of classification results. A network high?dimensional data soft subspace clustering method based on decision?making tree is proposed. Decision?making tree nodes are selected according to information gain， and the split information items is added on the basis of information gain to prevent over?classification of decision?making tree nodes. The partition results of attribute classification of different decision?making tree nodes are obtained. On this basis， the post?pruning technique is used to remove the nodes containing noise and interference properties， and the classification results containing the maximum number of samples is regarded as the classification results of the network high?dimensional data soft subspace. The simulation results show that the accuracy of clustering analysis of the proposed method increases with the increase of the dimension of the high?dimensional data set in the network， and the running time amplification is still low while the sample quantity is increased. It is a kind of high?dimensional data soft subspace clustering method with high application value.

Keywords： clustering method; soft subspace; high dimensional data; decision?making tree; information gain; simulated analysis

0 ?引 ?言

聚類方法在數(shù)據(jù)挖掘中具有廣泛的應(yīng)用價(jià)值，聚類過程可將抽象對(duì)象的集合劃分為多個(gè)相似對(duì)象構(gòu)成的類別或簇。當(dāng)前的一些聚類方法在聚類網(wǎng)絡(luò)高維數(shù)據(jù)時(shí)存在聚類結(jié)果精度低和聚類運(yùn)行耗時(shí)長的問題。出現(xiàn)該結(jié)果的原因可能是高維網(wǎng)絡(luò)數(shù)據(jù)空間存在多個(gè)不相關(guān)子空間，即到定位目標(biāo)類別存在哪個(gè)子空間時(shí)，僅需獲取低維子空間的聚類，該過程為子空間聚類[1]。依照各個(gè)子空間局部特征進(jìn)行加權(quán)劃分，并對(duì)不同維度分配不同權(quán)重。因此可采用求權(quán)值的方式來獲取最優(yōu)子空間，根據(jù)加權(quán)方式的差異將子空間聚類分為硬子空間和軟子空間聚類[2]，其中軟子空間聚類時(shí)的維度權(quán)值取值在0～1之間。

決策樹法是數(shù)據(jù)挖掘領(lǐng)域應(yīng)用最廣泛的方法之一，尤其在網(wǎng)絡(luò)高維數(shù)據(jù)分類方面應(yīng)用較廣。該方法在不同的決策樹節(jié)點(diǎn)上選擇分類精度最佳的屬性[3?5]，重復(fù)進(jìn)行節(jié)點(diǎn)選擇，直至決策樹分類樣本的精確最高。通常采用決策樹進(jìn)行分類需要對(duì)決策樹進(jìn)行剪枝處理，以提升網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的聚類精度。因此，本文提出基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法，提升聚類結(jié)果正確率和效率。

1 ?典型網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法

軟子空間聚類時(shí)，將特征權(quán)值矩陣用W表示，第j個(gè)聚類中的第r個(gè)維度比重為[wjr]，該值滿足條件如下：

獲取目標(biāo)函數(shù)后，需采取一定優(yōu)化求解方式計(jì)算目標(biāo)函數(shù)最優(yōu)解，目標(biāo)函數(shù)最優(yōu)值即可判斷網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的分類結(jié)果是否最優(yōu)。

典型網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法通過定義目標(biāo)函數(shù)，根據(jù)目標(biāo)函數(shù)的最優(yōu)解判斷是否最優(yōu)聚類，聚類過程容易陷入局部過于擬合[6?7]，陷入局部最優(yōu)，未能有效地對(duì)網(wǎng)絡(luò)高維數(shù)數(shù)據(jù)進(jìn)行精確類別劃分。因此本文對(duì)典型網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法進(jìn)行改進(jìn)，提出基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法。

2 ?基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類

基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法，在決策樹生成過程時(shí)，樹節(jié)點(diǎn)的選擇是網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類分類的核心，決策樹中樹節(jié)點(diǎn)的選擇以信息增益為標(biāo)準(zhǔn)[8]，網(wǎng)絡(luò)高維數(shù)據(jù)樣本集D，具有n個(gè)不同目標(biāo)屬性，定義集合D分類熵為：

式中：[V（O）]表示屬性O(shè)的取值集合，其中的取值結(jié)果用v表示;[D]為網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間樣本總數(shù);[Dv]表示取值為v屬性O(shè)的樣本數(shù)。

由于信息增益標(biāo)準(zhǔn)具有偏好細(xì)劃分特征，因此無論樹節(jié)點(diǎn)屬性選擇是否對(duì)網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類最有意義，只要其劃分網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間類別多，在信息增益標(biāo)準(zhǔn)下該決策樹節(jié)點(diǎn)就是所選節(jié)點(diǎn)。本文通過在信息增益基礎(chǔ)上添加一個(gè)分裂信息項(xiàng)（SI），來懲罰分類過細(xì)的屬性。

由于網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間中包括大量噪聲和干擾屬性，因此生成的決策樹節(jié)點(diǎn)包含大量錯(cuò)誤信息，其雖然能夠?qū)崿F(xiàn)對(duì)網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的準(zhǔn)確分類，但分類結(jié)果精度較低，且生成的決策樹節(jié)點(diǎn)規(guī)模較大，該現(xiàn)象即為過擬合現(xiàn)象，剪枝技術(shù)可降低決策樹的過擬合現(xiàn)象[9]，提升決策樹的分類精度。剪枝技術(shù)包括前剪枝和后剪枝兩種。

前剪枝技術(shù)是在決策樹生成前根據(jù)某標(biāo)準(zhǔn)降低樹節(jié)點(diǎn)增長，前剪枝技術(shù)降低決策樹擬合時(shí)雖然降低樹節(jié)點(diǎn)，提升分類精度，但降低聚類方法的搜索范圍，分類精度提升效果較差。

后剪枝技術(shù)是在生成決策樹后對(duì)決策樹以某標(biāo)準(zhǔn)進(jìn)行節(jié)點(diǎn)刪除[10]，如刪除含有噪聲和干擾屬性節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹，將其從根節(jié)點(diǎn)轉(zhuǎn)變?yōu)槿~子節(jié)點(diǎn)，葉子節(jié)點(diǎn)將樣本分為n個(gè)類別[S1，S2，…，Sn]，若分類中包含樣本數(shù)量最多，可把該分類結(jié)果定義為網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的分類結(jié)果。重復(fù)進(jìn)行決策樹節(jié)點(diǎn)刪除，且節(jié)點(diǎn)應(yīng)為刪除后可提升分類精度的節(jié)點(diǎn)，一直修剪直至分類結(jié)果最佳為止。后剪枝相較前剪枝的分類精度高且范圍廣，反復(fù)進(jìn)行節(jié)點(diǎn)刪除得到網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法分類精度高。

3 ?實(shí)驗(yàn)分析

3.1 ?實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)選取網(wǎng)絡(luò)高維數(shù)據(jù)數(shù)據(jù)集用于測(cè)試分析，實(shí)驗(yàn)數(shù)據(jù)集中需先完成特征歸一化處理，使數(shù)據(jù)集中特征在[0，1]之間。為提升實(shí)驗(yàn)結(jié)果的公平性，實(shí)驗(yàn)對(duì)所有聚類方法均進(jìn)行多次重復(fù)實(shí)驗(yàn)，將各個(gè)方法測(cè)試結(jié)果的方差和均值均利用Matlab軟件進(jìn)行仿真。聚類方法評(píng)價(jià)指標(biāo)包括聚類準(zhǔn)確率（聚類方法正確劃分樣本所占比率）和Rand指數(shù)RI（數(shù)據(jù)集聚類后和實(shí)際劃分后，兩種結(jié)果的一致性）。聚類準(zhǔn)確率值越高表明聚類方法聚類結(jié)果越優(yōu);當(dāng)RI值為1時(shí)，表明聚類方法聚類結(jié)果與實(shí)際類表相同。

3.2 ?數(shù)據(jù)集選擇

實(shí)驗(yàn)選擇Iris為實(shí)驗(yàn)待聚類網(wǎng)絡(luò)高維數(shù)據(jù)集，網(wǎng)絡(luò)高維數(shù)據(jù)集如表1所示。

表1 ?實(shí)驗(yàn)所需網(wǎng)絡(luò)高維數(shù)據(jù)集

3.3 ?測(cè)試結(jié)果

為突出本文方法聚類結(jié)果的高準(zhǔn)確度，將基于差分演化的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法和基于閔氏距離的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法與本文方法進(jìn)行比較。三種方法對(duì)不同網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的聚類準(zhǔn)確率如表2所示。

表2 ?不同聚類方法對(duì)不同網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的聚類準(zhǔn)確率

從表2可知，本文方法在聚類不同數(shù)據(jù)集軟子空間時(shí)聚類正確率均高于差分演化和閔氏距離法。詳細(xì)分析不同數(shù)據(jù)維數(shù)時(shí)的聚類正確率可知，隨著數(shù)據(jù)集維數(shù)的增加，本文方法的聚類正確率呈現(xiàn)增長的變化趨勢(shì)，而另外兩種方法聚類正確率與數(shù)據(jù)維數(shù)間無明顯關(guān)系，因此說明，本文方法對(duì)不同網(wǎng)絡(luò)高維數(shù)據(jù)集軟子空間的聚類結(jié)果正確率高，且隨著數(shù)據(jù)維數(shù)的不斷增加聚類正確率也不斷提高。

采用三種方法聚類Iris數(shù)據(jù)集進(jìn)行運(yùn)行效率與樣本數(shù)量分析，結(jié)果如圖1所示。

分析圖1可知，三種方法聚類分析Iris數(shù)據(jù)集時(shí)，均存在運(yùn)行時(shí)間隨樣本數(shù)增加而增長的趨勢(shì)且增長幅度均較低。詳細(xì)分析圖1可知，本文方法運(yùn)行時(shí)間初始值較小，而另外兩種方法的運(yùn)行初始值較大，隨著樣本數(shù)增加三種方法的運(yùn)行用時(shí)差值顯著，說明本文方法是一種運(yùn)行效率高的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類方法。

圖1 ?三種方法聚類分析Iris數(shù)據(jù)集樣本數(shù)與運(yùn)行時(shí)間關(guān)系

4 ?結(jié) ?論

本文探討基于決策樹的網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間聚類算法，該方法在聚類分析時(shí)具有以下幾點(diǎn)優(yōu)勢(shì)：

1） 決策樹法在信息增益基礎(chǔ)上添加分裂信息項(xiàng)，防止網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的過度擬合分類，提升分類結(jié)果的價(jià)值意義;

2） 后剪枝技術(shù)在降低決策樹多度擬合的同時(shí)還提升聚類方法的搜索范圍，擴(kuò)大網(wǎng)絡(luò)高維數(shù)據(jù)軟子空間的數(shù)據(jù)類別。

經(jīng)實(shí)驗(yàn)測(cè)試結(jié)果可知，本文方法聚類分析網(wǎng)絡(luò)高維數(shù)據(jù)集軟子空間結(jié)果正確率高，運(yùn)行時(shí)間隨樣本數(shù)據(jù)增長變化較小，具有較強(qiáng)的實(shí)用性和應(yīng)用性。

注：本文通訊作者為陳菊。

參考文獻(xiàn)

[1] 牛志華，屈景怡，吳仁彪.基于Spark的分層子空間權(quán)重樹隨機(jī)森林算法[J].信號(hào)處理，2017，33（10）：27?33.

NIU Zhihua， QU Jingyi， WU Renbiao. Random forest algorithm using stratified subspaces and weighted trees based on spark [J]. Journal of signal processing， 2017， 33（10）： 27?33.

[2] 寇廣，湯光明，何嘉婧，等.一種基于變異蝙蝠算法的高維聚類方法[J].系統(tǒng)仿真學(xué)報(bào)，2018，30（4）：49?55.

KOU Guang， TANG Guangming， HE Jiajing， et al. High?dimensional clustering method based on variant bat algorithm [J]. Journal of system simulation， 2018， 30（4）： 49?55.

[3] 支曉斌，許朝暉.魯棒的特征權(quán)重自調(diào)節(jié)軟子空間聚類算法[J].計(jì)算機(jī)應(yīng)用，2015，35（3）：770?774.

ZHI Xiaobin， XU Zhaohui. Robust soft subspace clustering algorithm with feature weight self?adjustment mechanism [J]. Journal of computer applications， 2015， 35（3）： 770?774.

[4] 亢紅領(lǐng)，李明楚，焦棟，等.一種基于屬性相關(guān)度的子空間聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（2）：211?214.

KANG Hongling， LI Mingchu， JIAO Dong， et al. Attribute relevancy?based subspace clustering algorithm [J]. Journal of Chinese computer systems， 2015， 36（2）： 211?214.

[5] 董琪，王士同.隱子空間聚類算法的改進(jìn)及其增量式算法[J].計(jì)算機(jī)科學(xué)與探索，2017，11（5）：802?813.

DONG Qi，WANG Shitong.Improved latent subspace clustering algorithm and its incremental version [J]. Journal of frontiers of computer science & technology， 2017， 11（5）： 802?813.

[6] 肖紅光，陳穎慧，巫小蓉.基于結(jié)構(gòu)樹的高維數(shù)據(jù)流子空間自適應(yīng)聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37（10）：2206?2211.

XIAO Hongguang， CHEN Yinghui， WU Xiaorong. Adaptive clustering algorithm for high dimensional data stream based on structure tree [J]. Journal of Chinese computer systems， 2016， 37（10）： 2206?2211.

[7] 費(fèi)賢舉，李虹，田國忠.基于特征加權(quán)理論的數(shù)據(jù)聚類算法[J].沈陽工業(yè)大學(xué)學(xué)報(bào)，2018，40（1）：77?81.

FEI Xianju， LI Hong， TIAN Guozhong. Data clustering algorithm based on feature weighting theory [J]. Journal of Shenyang University of Technology， 2018， 40（1）： 77?81.

[8] 王躍，肖人杰，褚芯閱，等.基于數(shù)據(jù)流形結(jié)構(gòu)的聚類方法及其應(yīng)用研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（14）：180?188.

WANG Yue， XIAO Renjie， CHU Xinyue， et al. Clustering method based on the data manifold structure and its application research [J]. Mathematics in practice and theory， 2016， 46（14）： 180?188.

[9] 邱云飛，費(fèi)博雯，劉大千.基于概率模型的重疊子空間聚類算法[J].模式識(shí)別與人工智能，2017，30（7）：609?621.

QIU Yunfei， FEI Bowen， LIU Daqian. Overlapping subspace clustering based on probabilistic model [J]. Pattern recognition and artificial intelligence， 2017， 30（7）： 609?621.

[10] 李小玲.關(guān)于網(wǎng)絡(luò)數(shù)據(jù)庫傳輸中異常數(shù)據(jù)檢測(cè)仿真研究[J].計(jì)算機(jī)仿真，2018，35（1）：420?423.

LI Xiaoling. Simulation research on abnormal data detection in network database transmission [J]. Computer simulation， 2018， 35（1）： 420?423.