面向大數據集的遞增聚類方法研究

楊克光

摘 要： 以往提出的面向大數據集的遞增聚類方法直接將多維度的大數據集轉換成一維大數據集，導致聚類成果不佳，故提出面向大數據集的遞增聚類新方法。為取得高聚類效率，在高度保留原始數據維度的情況下，簡化了大數據集遞增聚類步驟，構建出大數據處理集合，對集合中的標志樣本進行局部遞增聚類，將未能成功聚類的大數據平均分配到局部遞增聚類結果中，使用高斯概率密度函數和證據理論檢測其中的錯誤坐標并進行改正，獲取最終的遞增聚類結果。實驗結果證明該方法具有優越的聚類成果和聚類效率。

關鍵詞： 大數據集； 遞增聚類方法； 高斯概率密度函數； 證據理論

中圖分類號： TN911?34； TP311.13 文獻標識碼： A 文章編號： 1004?373X（2017）09?0176?03

Abstract： Since the clustering effect is poor because the previously?proposed incremental clustering method converts the multi?dimensional large dataset into the one?dimensional large dataset directly， a new incremental clustering method for large dataset is put forward. In order to obtain the high clustering efficiency， the incremental clustering step of the large dataset was simplified while highly maintaining the original data dimensions to construct a large data processing set. The local incremental clustering is performed for the logo samples in the set. The large data with failed clustering is distributed into the local incremental clustering results equally， and its fault coordinate is detected with Gaussian probability density function and coordinate evidence theory and modified. The final incremental clustering results are obtained. The experiment results prove that the proposed method has superior clustering effect and clustering efficiency.

Keywords： large dataset； incremental clustering method； Gaussian probability density function； evidence theory

0 引 言

聚類的實質就是把大數據分層，同層中的大數據特征擁有共通性，而不同層中的大數據特征存在明顯差異，并且大數據特征是可以被提取和描述的[1]。遞增聚類是其中一種無監督式的分析手段，在語音識別、色彩分類和紋理提取等搜索層面中均有涉及，受到了廣泛的關注。遞增聚類的基本原理類似于度衡量技術和最優函數，它依據特定標準在未經處理過的大數據集中挖掘隱晦的遞增聚類架構[2]。在實際應用中，類似度衡量技術的穩定性不佳，經常受到大數據遞增結構、聚類密度、大數據維度等方面的約束，致使遞增聚類達不到目標聚類的成果[3]。增強遞增聚類中類似度衡量技術的穩定性一直是科研人員的研究基礎，一些優秀的類似度衡量技術的穩定性解決方法，如相鄰大數據共享策略、密度敏感性度量等均是在大數據維度不高的情況下被提出的，在高維度應用中上述方法的迭代次數過多，大幅度降低了聚類效率。

綜上所述，以往提出的面向大數據集的遞增聚類方法常受限于類似度衡量技術的穩定性，并沒有取得優越的聚類成果和聚類效率[4]。解決這一問題的主要方式就是構建出能夠有效平衡大數據維度的大數據處理集合，在此基礎上分層次地獲取到遞增聚類結果，再對各層次的遞增聚類結果進行匯總，使用合理的處理手段給出統一的遞增聚類結果。基于上述分析，提出一種面向大數據集的遞增聚類新方法。

1 大數據處理集合的構建

以往提出的面向大數據集的遞增聚類方法為了提高聚類效率，直接將多維度的大數據集轉換成一維大數據集，導致聚類成果不佳，在實際應用中具有局限性[5]。為此，提出面向大數據集的遞增聚類新方法在對運算量高的大數據進行維度簡化的同時，補充了遞增聚類步驟，保留了大數據集的多維度特性，取得了高聚類效率。

在多維坐標系中選擇一個含有個數據的大數據集，用表示，提取出其中的目標大數據，用表示。如果的維度為則可將轉換為一個矩陣[6]。遞增聚類大數據集的實質就是獲取集合矩陣中各層大數據特征的類似度，依據類似度的具體數值為目標大數據定義出一個識別碼是遞增聚類總數量。一般來講，在遞增聚類中大數據集中的所有大數據都是目標大數據，則可組建出目標大數據識別碼集合，用表示[7]。遞增聚類的最終目的是無限增大相同層次中大數據特征的類似度。

本文提出的面向大數據集的遞增聚類新方法以多維坐標系中的中心坐標點為圓心、離差平方和為半徑構建大數據處理集合。假設大數據處理集合中擁有個大數據層次，那么的圓心和半徑可表示成：

2 大數據集局部遞增聚類方法

由于大數據集同層中的大數據特征擁有共通性，為了提高聚類效率，所提面向大數據集的遞增聚類新方法先在大數據集中選擇出各層大數據特征的標志樣本，將樣本的大數據特征平均值標記為標志坐標，對以標志坐標為圓心的大數據處理集合進行遞增聚類[9]。每取得一次遞增聚類結果，需要將聚類成功后的大數據刪除，避免大數據特征的不斷累計增加運算量，其聚類流程如圖1所示。

大數據集局部遞增聚類方法的思想是在大數據集中任意提取一個樣本，如果中涵蓋了本層中所有大數據特征，則將其定義為標志樣本，并從中提取一個坐標點定義成初值，令初值的半徑為初值與本層中大數據特征的密度閾值為MI，要求經由初值構建出的大數據處理集合中，所有大數據的特征密度均大于MI。標志樣本的標志坐標使用公式進行計算，表示擁有標志坐標的標志大數據。

從標志坐標開始依次向外進行遞增聚類，計算出大數據處理集合中其他大數據坐標與之間的距離：

式中：分別表示到和的軸位移。

當某一大數據的小于或證明局部遞增聚類成功。

大數據處理集合的每個層次都需要進行多次遞增聚類才能取得聚類結果，聚類結果中的大數據是按照遞增聚類成功的先后次序排列的[10]。本文方法將事先給出每個層次的聚類結果文件，初始文件均為空集，每取得一個小于或的大數據，聚類結果文件便會自動將大數據引入并為其賦予編號。產生了第一個聚類結果并將聚類成功大數據刪除后，方法才會開始進行第二個聚類結果的提取工作，以防止聚類結果文件對大數據的錯誤引入，增強了方法的聚類成果。

分層次將大數據處理集合中的所有大數據聚類成功后，可得到個聚類結果，將結果匯總，用集合表示。對于大于、等于或的大數據，大數據集局部遞增聚類方法會把這些為數不多的大數據平均分到集合中，得到，并利用大數據整體遞增聚類方法進行統一處理。

3 大數據整體遞增聚類方法

考慮到局部聚類結果中仍存在遞增聚類不成功的大數據，若面向大數據集的遞增聚類新方法使用單一的高斯概率密度函數進行整體遞增聚類將得不到優越的聚類成果，所以需要在高斯概率密度函數中融合證據理論。

給定一個集合作為大數據集局部遞增聚類結果集合的冪數集合，冪數集合中的數據可表示的聚類證據，是證據數量，。證據是指遞增聚類中數據點的歸屬度，在一定程度上代表了聚類成果，是衡量大數據特征類似度的標準。冪數集合的高斯概率密度函數被定義為：

面向大數據集的遞增聚類新方法的使用步驟整理如下：

Step1： 輸入原始大數據集，無需變更數據維度；

Step2： 使用式（1）～式（3）構建大數據處理集合，使用式（4），式（5）修正集合；

Step3： 選取標志樣本，計算標志坐標，進行局部遞增聚類，匯總局部遞增聚類結果；

Step4： 平均分配未成功進行遞增聚類的大數據；

Step5： 使用式（7）檢測錯誤坐標并修改；

Step6： 使用式（8）增強方法類似度衡量技術穩定性；

Step7： 使用式（9）計算信任函數，推導出方法目標函數，給出最終的遞增聚類結果。

4 仿真實驗

4.1 實驗設置

為了精準驗證本文提出的面向大數據集的遞增聚類新方法的聚類成果和聚類效率，需要在不同維度的大數據集中進行實驗，并盡可能采取對比策略，給出具有說服力的驗證結果。為此，實驗利用計算機模擬出了Tris和KDD64Bio兩種大數據集，第一種是二維坐標點大數據集，第二種是多維圖像大數據集。與本文方法相對應的對比方法在文獻[5]和文獻[9]中進行了詳細介紹，這兩種方法的市場需求和用戶反饋均是比較優越的。

4.2 實驗結果與分析

由于Tris大數據集擁有精確的數據坐標點信息，因此可從遞增聚類準確度中看出三種方法的聚類成果，如圖2所示。KDD64Bio大數據集由于數據維度復雜，故需要從聚類結果的數據間隔入手分析聚類成果，數據間隔越短，聚類成果越好，如表1所示。數據間隔包括同層間隔和異層間隔。實驗設置三種方法的聚類時間結果將與聚類成果共同輸出，如表2所示。

從表1，表2中能夠非常明顯地看出，實驗中對比方法的聚類成果均要遠低于本文方法的聚類成果，同時，本文方法還取得了優越的聚類效率。

5 結 論

本文提出一種面向大數據集的遞增聚類新方法，其在合理簡化大數據集維度、獲取高效遞增聚類的同時，對重要的遞增聚類步驟進行了補充，又依據從局部到整體的遞增聚類方式，對類似度衡量技術穩定性進行了加強處理，給出了遞增聚類目標函數。實驗將本文方法與文獻[5]、文獻[9]中的方法進行對比，從實驗結果中可明顯看出本文方法的聚類成果和聚類效率均要高于其他方法。

參考文獻

[1] 趙鳳嬌，賀月姣.基于改進的K?means聚類算法水下圖像邊緣檢測[J].現代電子技術，2015，38（18）：89?91.

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

[3] 涂新莉，劉波，林偉偉.大數據研究綜述[J].計算機應用研究，2014，31（6）：1612?1616.

[4] LIANG C， LENG Y. Collaborative filtering based on information?theoretic co?clustering [J]. International journal of systems science， 2014， 45（3）： 589?597.

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

[6] 張帆，毋濤.基于云計算的服裝物料管理系統[J].西安工程大學學報，2015，29（6）：740?745.

[7] 孟凡軍，李天偉，徐冠雷，等.基于K均值聚類算法的霧天識別方法研究[J].現代電子技術，2015，38（22）：80?83.

[8] 孫大為，張廣艷，鄭緯民.大數據流式計算：關鍵技術及系統實例[J].軟件學報，2014，25（4）：839?862.

[9] 潘章明，陳尹立.面向大數據集的共享近鄰聚類研究[J].小型微型計算機系統，2014，35（1）：50?54.

[10] KHAN S S， AHMAD A. Cluster center initialization algorithm for K?modes clustering [J]. Expert systems with applications， 2014， 40（18）： 7444?7456.