張勇 陳菊

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

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

中圖分類號： TN711?34; TP311 ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 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ù)據挖掘中具有廣泛的應用價值，聚類過程可將抽象對象的集合劃分為多個相似對象構成的類別或簇。當前的一些聚類方法在聚類網絡高維數(shù)據時存在聚類結果精度低和聚類運行耗時長的問題。出現(xiàn)該結果的原因可能是高維網絡數(shù)據空間存在多個不相關子空間，即到定位目標類別存在哪個子空間時，僅需獲取低維子空間的聚類，該過程為子空間聚類[1]。依照各個子空間局部特征進行加權劃分，并對不同維度分配不同權重。因此可采用求權值的方式來獲取最優(yōu)子空間，根據加權方式的差異將子空間聚類分為硬子空間和軟子空間聚類[2]，其中軟子空間聚類時的維度權值取值在0～1之間。

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

1 ?典型網絡高維數(shù)據軟子空間聚類方法

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

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

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

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

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

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

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

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

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

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

3 ?實驗分析

3.1 ?實驗環(huán)境

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

3.2 ?數(shù)據集選擇

實驗選擇Iris為實驗待聚類網絡高維數(shù)據集，網絡高維數(shù)據集如表1所示。

表1 ?實驗所需網絡高維數(shù)據集

3.3 ?測試結果

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

表2 ?不同聚類方法對不同網絡高維數(shù)據軟子空間的聚類準確率

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

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

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

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

4 ?結 ?論

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

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

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

經實驗測試結果可知，本文方法聚類分析網絡高維數(shù)據集軟子空間結果正確率高，運行時間隨樣本數(shù)據增長變化較小，具有較強的實用性和應用性。

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

參考文獻

[1] 牛志華，屈景怡，吳仁彪.基于Spark的分層子空間權重樹隨機森林算法[J].信號處理，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)仿真學報，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] 支曉斌，許朝暉.魯棒的特征權重自調節(jié)軟子空間聚類算法[J].計算機應用，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] 亢紅領，李明楚，焦棟，等.一種基于屬性相關度的子空間聚類算法[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].計算機科學與探索，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] 肖紅光，陳穎慧，巫小蓉.基于結構樹的高維數(shù)據流子空間自適應聚類算法[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] 費賢舉，李虹，田國忠.基于特征加權理論的數(shù)據聚類算法[J].沈陽工業(yè)大學學報，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].數(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] 邱云飛，費博雯，劉大千.基于概率模型的重疊子空間聚類算法[J].模式識別與人工智能，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] 李小玲.關于網絡數(shù)據庫傳輸中異常數(shù)據檢測仿真研究[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.