大數據集合中冗余特征排除的聚類算法設計

侯莉莎

摘 要： 傳統microRNA聚類算法對數據的新特征要求較高，未全面分析大數據集內的冗余特征，使得聚類結果均衡性差。因此，提出大數據集合中冗余特征排除的聚類算法，其采用聚類集成算法，在組構造時期通過使用一致的聚類算法抽取各種子集樣本，實現大數據冗余特征的排除，獲取排除冗余特征的大數據集聚類結果。對得到的大數據聚類特征分類能力以及特征關聯性實施度量，采用基于特征聚類以及隨機子空間的miRNA識別算法，實現大數據集合冗余特征的聚類。實驗結果表明，所提算法具有較高的冗余數據排除性能，該算法下的大數據聚類效果優，具有較高的均衡性。

關鍵詞： 大數據集； 冗余特征排除； 聚類算法； 特征關聯性； 隨機子空間； miRNA識別算法

中圖分類號： TN911?34； TP311 文獻標識碼： A 文章編號： 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 引 言

隨著社會經濟的飛速發展，帶動信息技術和數據存儲技術的迅猛發展，促使數據量規模也逐漸增大，大量的高維度數據在金融領域、生物醫藥領域以及數據傳感領域應用較廣，高維度和海量的數據中可能存在大量的冗余信息，在實際應用中需要對冗余數據進行剔除，對大數據集合中冗余數據特征的聚類算法設計是提高海量高維度數據利用率的有效手段[1]。傳統microRNA聚類算法，對數據的新特征要求較高，未全面分析大數據集內的冗余特征，使得聚類結果均衡性差。本文設計大數據集合中冗余特征排除的聚類算法，提高算法的聚類效果，增強大數據聚類的均衡性。

1 大數據集合中冗余特征排除的聚類算法

1.1 聚類集成算法

通過聚類集成手段來構成組特征進而完成組構造。若歷史數據集是[D]，其中含有[n]個訓練標本，[D=X，Y=xi，yini=1]，第[i]個分子是[d]維向量在此數據集內。

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

1） 在數據集合聚類算法完全一致的情況下，可以通過對算法參數的特殊設定進而生成多種聚類結果[2]；

2） 當數據集一致時可通過其他聚類算法進行計算，獲取多種聚類結果；

3） 在初始數據集中獲取多種子集，通過一致的聚類算法針對子集實施聚類進而得到各種聚類結果；

4） 通過初始數據集獲得一定數量的特征子集，針對特征子集實施同種聚類算法，也可獲得多個聚類結果。

本文提出的聚類算法是指在組構造時期，通過使用一致的聚類算法抽取各種子集樣本，實現大數據冗余特征的排除，獲取排除冗余特征的大數據集聚類結果。詳細程序如下，選取bigging思想作為訓練集分類器的基礎，根據有反應的抽樣樣本來實現樣本子集的收集過程。若利用bigging思想獲取到多種樣本子集，此間某一個聚類器選取K?means方法。此方法在保證子集特點接近性的基礎上完成收集[3]，實現了針對大數據集中冗余特征的聚類。

此間特征中的接近性度量手段采取關聯數據。隨機變量分別由[u]，[v]代替，它們和關聯系數[ρ]的關系如下：

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

式中：[var]代表變量的方差；[cov]表示兩個變量的協方差。若[u]以及[v]具有關聯性，則二者確定為非動態關聯，[ρu，v]為1或-1；若[u]與[v]不具備關聯性，[ρu，v]為0。所以，變量[u]以及變量[v]的接近性可以借助[1-ρ（u，v）]來進行檢驗[4]。

針對[m]個樣本子集實施K?means聚類，可獲得[m]個聚類結果，單一聚類結構都具有不同特征，為[C11，…，C1l1，…，Cm1，…，Cmlm]。此間第[h]次聚類形成的第[j]個特點類型用[Chj]代表，第[m]次聚類形成的全部特征數據用[lm]表示。

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

1.2 結果表征以及評價

1.2.1 特征分類能力度量

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

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

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

1.2.2 特征關聯性度量

特征相關性度量由兩部分構成：第一部分是由Pearson積矩關聯數據、線性關聯數據組成的線性關聯；另外一部分是熵，包括信息增益性和未知性等。本文利用熵的對稱未知性對特征中的動態相關性進行分析[7]。特征[X]取第[i]個值的幾率由[P（xi）]表示，特征[Y]取值是[yi]時特征[X]取值是[xi]的幾率由[P（xiyi）]表示，[X]的數據熵計算方法如下：

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

定義對稱未知性[SUX，Y]來評價特征[X]和特征[Y]的關聯性，過程見式（3）。借此獲得特征關聯性度量[SUX，Y∈ [0，1]]，若取值是0，那么特征[X]以及特征[Y]都處于獨立狀態，若取值是1，則表示特征[X]與特征[Y]具有極強的相關性[8]。

1.3 基于特征聚類以及隨機子空間的miRNA識別算法

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

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

2 實驗分析

為了驗證本文算法在解決大數據集合中冗余特征排除結果的有效性，以模糊信息粒化算法、粗糙集近似算法、多維數據去重算法為對比算法，這些聚類算法本身可以針對不同類型的數據進行冗余特征排除。

實驗選取的大數據為某高校教學用的測試數據集，選取的樣本大數據集有Tony，R15，Flame以及Aggregation大數據集。檢測結果如圖1所示。從圖1實驗檢測結果可以看出，本文算法在樣本4個具有不同特征大數據集上均能夠得到聚類結果且用時也較短，并且本文算法聚類結果具有較高的均衡性。

為了分析本文算法的計算性能，將本文算法用于不同的大數據集上對本文算法的聚類性能以及用時情況進行測試，實驗數據集來自UCI數據庫。

實驗采用十字交叉驗證法對Isolet大數據集中的數據集評分成10分，其中訓練用數據集占[15]，其余為實驗測試用。表1為采用不同分類器下，本文算法和基于聚類的在線特征選擇算法聚類結果的準確率；表2為本文算法和基于聚類的在線特征選擇算法對不同大數據集的聚類用時。

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

3 結 論

本文提出新的用于解決大數據集合中冗余特征排除的聚類算法，其通過基于特征聚類以及隨機子空間的miRNA識別算法，實現大數據的高效率、準確聚類，并且增強了大數據聚類的均衡性。

參考文獻

[1] 古凌嵐.面向大數據集的有效聚類算法[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] 羅恩韜，王國軍.大數據中一種基于語義特征閾值的層次聚類方法[J].電子與信息學報，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] 張順龍，庫濤，周浩.針對多聚類中心大數據集的加速K?means聚類算法[J].計算機應用研究，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] 向堯，袁景凌，鐘珞，等.一種面向大數據集的粗粒度并行聚類算法研究[J].小型微型計算機系統，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] 謝川.基于混沌關聯維特征提取的大數據聚類算法[J].計算機科學，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].計算機工程與科學，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] 朱琪，張會福，楊宇波，等.基于減法聚類的合并最優路徑層次聚類算法[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] 周潤物，李智勇，陳少淼，等.面向大數據處理的并行優化抽樣聚類K?means算法[J].計算機應用，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].系統工程與電子技術，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].計算機研究與發展，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.