楊克光

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

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

中圖分類(lèi)號(hào)： TN911?34； TP311.13 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

5 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

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

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