面向大數(shù)據(jù)集的遞增聚類方法研究

楊克光

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

關(guān)鍵詞： 大數(shù)據(jù)集； 遞增聚類方法； 高斯概率密度函數(shù)； 證據(jù)理論

中圖分類號： TN911?34； TP311.13 文獻標(biāo)識碼： 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 引 言

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

綜上所述，以往提出的面向大數(shù)據(jù)集的遞增聚類方法常受限于類似度衡量技術(shù)的穩(wěn)定性，并沒有取得優(yōu)越的聚類成果和聚類效率[4]。解決這一問題的主要方式就是構(gòu)建出能夠有效平衡大數(shù)據(jù)維度的大數(shù)據(jù)處理集合，在此基礎(chǔ)上分層次地獲取到遞增聚類結(jié)果，再對各層次的遞增聚類結(jié)果進行匯總，使用合理的處理手段給出統(tǒng)一的遞增聚類結(jié)果?；谏鲜龇治?，提出一種面向大數(shù)據(jù)集的遞增聚類新方法。

1 大數(shù)據(jù)處理集合的構(gòu)建

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

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

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

2 大數(shù)據(jù)集局部遞增聚類方法

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

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

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

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

當(dāng)某一大數(shù)據(jù)的小于或證明局部遞增聚類成功。

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

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

3 大數(shù)據(jù)整體遞增聚類方法

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

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

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

Step1： 輸入原始大數(shù)據(jù)集，無需變更數(shù)據(jù)維度；

Step2： 使用式（1）～式（3）構(gòu)建大數(shù)據(jù)處理集合，使用式（4），式（5）修正集合；

Step3： 選取標(biāo)志樣本，計算標(biāo)志坐標(biāo)，進行局部遞增聚類，匯總局部遞增聚類結(jié)果；

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

Step5： 使用式（7）檢測錯誤坐標(biāo)并修改；

Step6： 使用式（8）增強方法類似度衡量技術(shù)穩(wěn)定性；

Step7： 使用式（9）計算信任函數(shù)，推導(dǎo)出方法目標(biāo)函數(shù)，給出最終的遞增聚類結(jié)果。

4 仿真實驗

4.1 實驗設(shè)置

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

4.2 實驗結(jié)果與分析

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

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

5 結(jié) 論

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

參考文獻

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

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

[3] 涂新莉，劉波，林偉偉.大數(shù)據(jù)研究綜述[J].計算機應(yīng)用研究，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] 羅恩韜，王國軍.大數(shù)據(jù)中一種基于語義特征閾值的層次聚類方法[J].電子與信息學(xué)報，2015，37（12）：2795?2801.

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

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

[8] 孫大為，張廣艷，鄭緯民.大數(shù)據(jù)流式計算：關(guān)鍵技術(shù)及系統(tǒng)實例[J].軟件學(xué)報，2014，25（4）：839?862.

[9] 潘章明，陳尹立.面向大數(shù)據(jù)集的共享近鄰聚類研究[J].小型微型計算機系統(tǒng)，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.