大數(shù)據(jù)集合中冗余特征排除的聚類算法設(shè)計(jì)

侯莉莎

摘 要： 傳統(tǒng)microRNA聚類算法對(duì)數(shù)據(jù)的新特征要求較高，未全面分析大數(shù)據(jù)集內(nèi)的冗余特征，使得聚類結(jié)果均衡性差。因此，提出大數(shù)據(jù)集合中冗余特征排除的聚類算法，其采用聚類集成算法，在組構(gòu)造時(shí)期通過使用一致的聚類算法抽取各種子集樣本，實(shí)現(xiàn)大數(shù)據(jù)冗余特征的排除，獲取排除冗余特征的大數(shù)據(jù)集聚類結(jié)果。對(duì)得到的大數(shù)據(jù)聚類特征分類能力以及特征關(guān)聯(lián)性實(shí)施度量，采用基于特征聚類以及隨機(jī)子空間的miRNA識(shí)別算法，實(shí)現(xiàn)大數(shù)據(jù)集合冗余特征的聚類。實(shí)驗(yàn)結(jié)果表明，所提算法具有較高的冗余數(shù)據(jù)排除性能，該算法下的大數(shù)據(jù)聚類效果優(yōu)，具有較高的均衡性。

關(guān)鍵詞： 大數(shù)據(jù)集； 冗余特征排除； 聚類算法； 特征關(guān)聯(lián)性； 隨機(jī)子空間； miRNA識(shí)別算法

中圖分類號(hào)： TN911?34； TP311 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）14?0048?03

Design of clustering algorithm for redundancy feature removal in big data sets

HOU Lisha1，2

（1. Tianjin University， Tianjin 300072， China； 2. Beijing Professional Business Institute， Beijing 102488， China）

Abstract： The traditional microRNA clustering algorithm has relatively high requirements for new features of data， and the redundancy feature in big data sets are not fully analyzed， resulting in poor equilibrium of clustering results. Therefore， a clustering algorithm for redundancy feature removal in big data sets is proposed， in which the integrated clustering algorithm is adopted， and samples of various subsets are extracted by using the consistent clustering algorithm during the group construction period， so as to realize the redundancy feature removal of big data， and obtain the clustering results of big data for redundancy feature removal. The classification capability and correlation of the obtained big data clustering features are measured. The miRNA recognition algorithm based on feature clustering and stochastic subspace is adopted to realize clustering of big data sets and redundancy features. The experimental results show that the proposed algorithm has high redundancy data removal performance， and the big data clustering effect under the algorithm is superior with high equilibrium.

Keywords： big data set； redundancy feature removal； clustering algorithm； feature correlation； stochastic subspace；

miRNA recognition algorithm0 引 言

隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展，帶動(dòng)信息技術(shù)和數(shù)據(jù)存儲(chǔ)技術(shù)的迅猛發(fā)展，促使數(shù)據(jù)量規(guī)模也逐漸增大，大量的高維度數(shù)據(jù)在金融領(lǐng)域、生物醫(yī)藥領(lǐng)域以及數(shù)據(jù)傳感領(lǐng)域應(yīng)用較廣，高維度和海量的數(shù)據(jù)中可能存在大量的冗余信息，在實(shí)際應(yīng)用中需要對(duì)冗余數(shù)據(jù)進(jìn)行剔除，對(duì)大數(shù)據(jù)集合中冗余數(shù)據(jù)特征的聚類算法設(shè)計(jì)是提高海量高維度數(shù)據(jù)利用率的有效手段[1]。傳統(tǒng)microRNA聚類算法，對(duì)數(shù)據(jù)的新特征要求較高，未全面分析大數(shù)據(jù)集內(nèi)的冗余特征，使得聚類結(jié)果均衡性差。本文設(shè)計(jì)大數(shù)據(jù)集合中冗余特征排除的聚類算法，提高算法的聚類效果，增強(qiáng)大數(shù)據(jù)聚類的均衡性。

1 大數(shù)據(jù)集合中冗余特征排除的聚類算法

1.1 聚類集成算法

通過聚類集成手段來構(gòu)成組特征進(jìn)而完成組構(gòu)造。若歷史數(shù)據(jù)集是[D]，其中含有[n]個(gè)訓(xùn)練標(biāo)本，[D=X，Y=xi，yini=1]，第[i]個(gè)分子是[d]維向量在此數(shù)據(jù)集內(nèi)。

本文選取的聚類集成方法，以聚類分析為基準(zhǔn)包含多種優(yōu)勢，具有良好的平均性，廣泛使用的辦法如下：

1） 在數(shù)據(jù)集合聚類算法完全一致的情況下，可以通過對(duì)算法參數(shù)的特殊設(shè)定進(jìn)而生成多種聚類結(jié)果[2]；

2） 當(dāng)數(shù)據(jù)集一致時(shí)可通過其他聚類算法進(jìn)行計(jì)算，獲取多種聚類結(jié)果；

3） 在初始數(shù)據(jù)集中獲取多種子集，通過一致的聚類算法針對(duì)子集實(shí)施聚類進(jìn)而得到各種聚類結(jié)果；

4） 通過初始數(shù)據(jù)集獲得一定數(shù)量的特征子集，針對(duì)特征子集實(shí)施同種聚類算法，也可獲得多個(gè)聚類結(jié)果。

本文提出的聚類算法是指在組構(gòu)造時(shí)期，通過使用一致的聚類算法抽取各種子集樣本，實(shí)現(xiàn)大數(shù)據(jù)冗余特征的排除，獲取排除冗余特征的大數(shù)據(jù)集聚類結(jié)果。詳細(xì)程序如下，選取bigging思想作為訓(xùn)練集分類器的基礎(chǔ)，根據(jù)有反應(yīng)的抽樣樣本來實(shí)現(xiàn)樣本子集的收集過程。若利用bigging思想獲取到多種樣本子集，此間某一個(gè)聚類器選取K?means方法。此方法在保證子集特點(diǎn)接近性的基礎(chǔ)上完成收集[3]，實(shí)現(xiàn)了針對(duì)大數(shù)據(jù)集中冗余特征的聚類。

此間特征中的接近性度量手段采取關(guān)聯(lián)數(shù)據(jù)。隨機(jī)變量分別由[u]，[v]代替，它們和關(guān)聯(lián)系數(shù)[ρ]的關(guān)系如下：

[ρu，v=covu，vvar（u）var（v）] （1）

式中：[var]代表變量的方差；[cov]表示兩個(gè)變量的協(xié)方差。若[u]以及[v]具有關(guān)聯(lián)性，則二者確定為非動(dòng)態(tài)關(guān)聯(lián)，[ρu，v]為1或-1；若[u]與[v]不具備關(guān)聯(lián)性，[ρu，v]為0。所以，變量[u]以及變量[v]的接近性可以借助[1-ρ（u，v）]來進(jìn)行檢驗(yàn)[4]。

針對(duì)[m]個(gè)樣本子集實(shí)施K?means聚類，可獲得[m]個(gè)聚類結(jié)果，單一聚類結(jié)構(gòu)都具有不同特征，為[C11，…，C1l1，…，Cm1，…，Cmlm]。此間第[h]次聚類形成的第[j]個(gè)特點(diǎn)類型用[Chj]代表，第[m]次聚類形成的全部特征數(shù)據(jù)用[lm]表示。

根據(jù)以上在特征接近性K?means方法中獲得的各種聚類結(jié)果結(jié)合為聚類集體以后，接下來應(yīng)選取相符的集成方法進(jìn)行聚類結(jié)果總結(jié)。本文以互聯(lián)矩陣為基礎(chǔ)，針對(duì)[m]個(gè)聚類結(jié)果將同組中的每一種特征實(shí)施劃分計(jì)算，再用聚類次數(shù)[m]予以平均計(jì)算[5]，得出用矩陣[Wq，r]代表特征[q]以及特征[r]的接近程度。最后根據(jù)凝聚型分層聚類，針對(duì)全部特征實(shí)施合并，以特征組中的接近性不小于[θ，θ]的特定數(shù)據(jù)為合并基礎(chǔ)，通過類平均措施統(tǒng)計(jì)特征組中的接近性，使其不受異常值變化的干預(yù)。

1.2 結(jié)果表征以及評(píng)價(jià)

1.2.1 特征分類能力度量

一般情況下特征分類能力由信息增益率來進(jìn)行檢驗(yàn)[6]。將訓(xùn)練數(shù)據(jù)集設(shè)為D，客觀pre?miRNA以及偽發(fā)夾組成序列由[Ci（i=1，-1）]來依次代表。正例標(biāo)本集合以及反例標(biāo)本集合分別由[Dp]，[Dn]表示。由此得出數(shù)據(jù)集D的信息熵計(jì)算公式：

[H（D）=-iP（Ci）lb P（Ci）] （2）

式中，[P（Ci）]表示隨機(jī)樣本歸屬類別[Ci]的可能率，設(shè)[i=1]，那么[P（Ci）=DpD]，相反[P（Ci）=DnD]。

1.2.2 特征關(guān)聯(lián)性度量

特征相關(guān)性度量由兩部分構(gòu)成：第一部分是由Pearson積矩關(guān)聯(lián)數(shù)據(jù)、線性關(guān)聯(lián)數(shù)據(jù)組成的線性關(guān)聯(lián)；另外一部分是熵，包括信息增益性和未知性等。本文利用熵的對(duì)稱未知性對(duì)特征中的動(dòng)態(tài)相關(guān)性進(jìn)行分析[7]。特征[X]取第[i]個(gè)值的幾率由[P（xi）]表示，特征[Y]取值是[yi]時(shí)特征[X]取值是[xi]的幾率由[P（xiyi）]表示，[X]的數(shù)據(jù)熵計(jì)算方法如下：

[SUX，Y=2IGXYHX+HY] （3）

定義對(duì)稱未知性[SUX，Y]來評(píng)價(jià)特征[X]和特征[Y]的關(guān)聯(lián)性，過程見式（3）。借此獲得特征關(guān)聯(lián)性度量[SUX，Y∈ [0，1]]，若取值是0，那么特征[X]以及特征[Y]都處于獨(dú)立狀態(tài)，若取值是1，則表示特征[X]與特征[Y]具有極強(qiáng)的相關(guān)性[8]。

1.3 基于特征聚類以及隨機(jī)子空間的miRNA識(shí)別算法

本文基于1.1小節(jié)聚類集成算法排除大數(shù)據(jù)冗余特征后，得到的大數(shù)據(jù)集聚類特征和隨機(jī)子空間的基礎(chǔ)上，采用miRNA識(shí)別算法，根據(jù)特征取得備用特征集，按照特征關(guān)聯(lián)性對(duì)備用數(shù)據(jù)集進(jìn)行歸類[9]，在各個(gè)簇中任意抽取等量特征構(gòu)建出特征集用以形成基分類器，最終根據(jù)投票辦法對(duì)位置序列是否歸屬miRNA實(shí)施辨別。

為了使隨機(jī)兩簇中特征閾值低于最小距離，可通過凝聚最短距離層次聚類算法對(duì)備用特征集實(shí)施計(jì)算，將原始化的單獨(dú)特征進(jìn)行單獨(dú)分類，最后使用[Dist]完成合并替換矩陣[10]。根據(jù)特征集[S]從初始信息中獲得數(shù)據(jù)集訓(xùn)練分類器，通過分類器集成手段判斷抽取標(biāo)本所屬類型。

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

為了驗(yàn)證本文算法在解決大數(shù)據(jù)集合中冗余特征排除結(jié)果的有效性，以模糊信息?；惴?、粗糙集近似算法、多維數(shù)據(jù)去重算法為對(duì)比算法，這些聚類算法本身可以針對(duì)不同類型的數(shù)據(jù)進(jìn)行冗余特征排除。

實(shí)驗(yàn)選取的大數(shù)據(jù)為某高校教學(xué)用的測試數(shù)據(jù)集，選取的樣本大數(shù)據(jù)集有Tony，R15，F(xiàn)lame以及Aggregation大數(shù)據(jù)集。檢測結(jié)果如圖1所示。從圖1實(shí)驗(yàn)檢測結(jié)果可以看出，本文算法在樣本4個(gè)具有不同特征大數(shù)據(jù)集上均能夠得到聚類結(jié)果且用時(shí)也較短，并且本文算法聚類結(jié)果具有較高的均衡性。

為了分析本文算法的計(jì)算性能，將本文算法用于不同的大數(shù)據(jù)集上對(duì)本文算法的聚類性能以及用時(shí)情況進(jìn)行測試，實(shí)驗(yàn)數(shù)據(jù)集來自UCI數(shù)據(jù)庫。

實(shí)驗(yàn)采用十字交叉驗(yàn)證法對(duì)Isolet大數(shù)據(jù)集中的數(shù)據(jù)集評(píng)分成10分，其中訓(xùn)練用數(shù)據(jù)集占[15]，其余為實(shí)驗(yàn)測試用。表1為采用不同分類器下，本文算法和基于聚類的在線特征選擇算法聚類結(jié)果的準(zhǔn)確率；表2為本文算法和基于聚類的在線特征選擇算法對(duì)不同大數(shù)據(jù)集的聚類用時(shí)。

從表1分類結(jié)果的準(zhǔn)確率結(jié)果可以看出，本文算法無論采用哪一種分類器分類結(jié)果的準(zhǔn)確率都要優(yōu)于基于聚類的在線特征選擇算法。在數(shù)據(jù)維度較高的Urban數(shù)據(jù)集上，基于聚類的在線特征選擇算法不能對(duì)其數(shù)據(jù)操作，可以得出本文算法能夠提高大數(shù)據(jù)的分類正確率，以及對(duì)高維度的大數(shù)據(jù)也能進(jìn)行正確分類。從表2算法的計(jì)算用時(shí)可以看出，本文算法和基于聚類的在線特征選擇算法在對(duì)相同的大數(shù)據(jù)進(jìn)行冗余特征排除法聚類中，本文算法的運(yùn)算用時(shí)均低于基于聚類的在線特征選擇算法，說明本文算法的時(shí)間效率較好，可以節(jié)省時(shí)間成本。

3 結(jié) 論

本文提出新的用于解決大數(shù)據(jù)集合中冗余特征排除的聚類算法，其通過基于特征聚類以及隨機(jī)子空間的miRNA識(shí)別算法，實(shí)現(xiàn)大數(shù)據(jù)的高效率、準(zhǔn)確聚類，并且增強(qiáng)了大數(shù)據(jù)聚類的均衡性。

參考文獻(xiàn)

[1] 古凌嵐.面向大數(shù)據(jù)集的有效聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（6）：2183?2187.

GU linglan. Efficient clustering algorithm for large data sets [J]. Computer engineering and design， 2014， 35（6）： 2183?2187.

[2] 羅恩韜，王國軍.大數(shù)據(jù)中一種基于語義特征閾值的層次聚類方法[J].電子與信息學(xué)報(bào)，2015，37（12）：2795?2801.

LUO Entao， WANG Guojun. A hierarchical clustering method based on the threshold of semantic feature in big data [J]. Journal of electronics & information technology， 2015， 37（12）： 2795?2801.

[3] 張順龍，庫濤，周浩.針對(duì)多聚類中心大數(shù)據(jù)集的加速K?means聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（2）：413?416.

ZHANG Shunlong， KU Tao， ZHOU Hao. Accelerate K?means for multi?center clustering of big datasets [J]. Application research of computers， 2016， 33（2）： 413?416.

[4] 向堯，袁景凌，鐘珞，等.一種面向大數(shù)據(jù)集的粗粒度并行聚類算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，35（10）：2370?2374.

XIANG Yao， YUAN Jingling， ZHONG Luo， et al. A coarse?grained clustering unit based parallel algorithm for big data set [J]. Journal of Chinese computer systems， 2014， 35（10）： 2370?2374.

[5] 謝川.基于混沌關(guān)聯(lián)維特征提取的大數(shù)據(jù)聚類算法[J].計(jì)算機(jī)科學(xué)，2016，43（6）：229?232.

XIE Chuan. Big data clustering algorithm based on chaotic correlation dimensions feature extraction [J]. Computer science， 2016， 43（6）： 229?232.

[6] 張曉，王紅.一種改進(jìn)的基于大數(shù)據(jù)集的混合聚類算法[J].計(jì)算機(jī)工程與科學(xué)，2015，37（9）：1621?1626.

ZHANG Xiao， WANG Hong. An improved hybrid clustering algorithm based on large data sets [J]. Computer engineering and science， 2015， 37（9）： 1621?1626.

[7] 朱琪，張會(huì)福，楊宇波，等.基于減法聚類的合并最優(yōu)路徑層次聚類算法[J].計(jì)算機(jī)工程，2015，41（6）：178?182.

ZHU Qi， ZHANG Huifu， YANG Yubo， et al. Combined optimal path hierarchical clustering algorithm based on subtractive clustering [J]. Computer engineering， 2015， 41（6）： 178?182.

[8] 周潤物，李智勇，陳少淼，等.面向大數(shù)據(jù)處理的并行優(yōu)化抽樣聚類K?means算法[J].計(jì)算機(jī)應(yīng)用，2016，36（2）：311?315.

ZHOU Runwu， LI Zhiyong， CHEN Shaomiao， et al. Parallel optimization sampling clustering K?means algorithm for big data processing [J]. Journal of computer applications， 2016， 36（2）： 311?315.

[9] 盧志茂，馮進(jìn)玫，范冬梅，等.面向大數(shù)據(jù)處理的劃分聚類新方法[J].系統(tǒng)工程與電子技術(shù)，2014，36（5）：1010?1015.

LU Zhimao， FENG Jinmei， FAN Dongmei， et al. Novel partitional clustering algorithm for large data processing [J]. Systems engineering and electronics， 2014， 36（5）： 1010?1015.

[10] 鞏樹鳳，張巖峰.EDDPC：一種高效的分布式密度中心聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2016，53（6）：1400?1409.

GONG Shufeng， ZHANG Yanfeng. EDDPC： an efficient distributed density peaks clustering algorithm [J]. Journal of computer research and development， 2016， 53（6）： 1400?1409.