大數(shù)據(jù)聚類算法研究

郭雯雯 邵全義

摘 要：隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)量不斷地增加，對大數(shù)據(jù)環(huán)境下的數(shù)據(jù)進行有效的聚類已經(jīng)成為現(xiàn)階段的一個研究熱點。文章圍繞這一課題，從介紹大數(shù)據(jù)環(huán)境下的特點以及對算法的處理要求開始，對面向大數(shù)據(jù)的聚類算法的劃分進行簡單的介紹，指出其中的問題，并對大數(shù)據(jù)下的有效聚類算法的劃分進行展望，希望能夠借此加深對于聚類算法的理解。

關(guān)鍵詞：大數(shù)據(jù)；聚類算法；劃分

1 大數(shù)據(jù)下聚類算法的含義

大數(shù)據(jù)是指以多元形式，由許多來源搜集而組成的龐大數(shù)據(jù)組。電子商務(wù)網(wǎng)站、社交網(wǎng)站以及網(wǎng)頁瀏覽記錄等都可以成為大數(shù)據(jù)的數(shù)據(jù)來源。同時，大數(shù)據(jù)又是指在現(xiàn)有的技術(shù)條件下無法在規(guī)定的時間內(nèi)對數(shù)據(jù)進行傳輸、存儲、計算和應(yīng)用等的數(shù)據(jù)集合。大數(shù)據(jù)的數(shù)據(jù)體量巨大，數(shù)據(jù)的類型繁多，價值密度較低，處理速度較快，其核心的價值在于對海量的數(shù)據(jù)進行存儲和分析，具有成本低、效率高等優(yōu)勢。隨著信息化技術(shù)的不斷發(fā)展，大數(shù)據(jù)已經(jīng)成為當(dāng)代炙手可熱的一個話題，各個行業(yè)都在對大數(shù)據(jù)下的聚類算法的應(yīng)用進行研究。大數(shù)據(jù)是信息化社會的一個產(chǎn)物，像是一塊蘊含著能量的煤礦，利用大數(shù)據(jù)的優(yōu)勢，可以為大量消費者提供產(chǎn)品或服務(wù)的企業(yè)提供進行精準(zhǔn)營銷的技術(shù)，促進企業(yè)的轉(zhuǎn)型和升級。

采用聚類算法對大數(shù)據(jù)進行處理解決抽樣數(shù)據(jù)處理上的局限性，通過聚類，可以對大數(shù)據(jù)集進行隨機分塊，每一塊又是原數(shù)據(jù)集的一個可以保證抽樣能夠獨立進行的樣本集合，在足夠小的范圍之內(nèi)保證處理結(jié)果的可靠性。

在物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展下，聚類作為數(shù)據(jù)挖掘的一個重要的手段，在無先驗知識的前提下揭示數(shù)據(jù)之間的內(nèi)在聯(lián)系，將某些具有共同屬性的數(shù)據(jù)聚成一個簇，減小簇間的相似性，擴大簇內(nèi)數(shù)據(jù)之間的相似性，是數(shù)據(jù)挖掘以及機器等學(xué)習(xí)領(lǐng)域的重要研究課題，屬于無監(jiān)督模式識別的一種。大數(shù)據(jù)環(huán)境的發(fā)展，使得在數(shù)據(jù)處理上的要求不斷增加，面對每天所存在的幾百維乃至上萬維的數(shù)據(jù)，傳統(tǒng)的聚類算法不能夠很好地與這些任務(wù)要求進行匹配，導(dǎo)致處理效率低下、效果差等情況的出現(xiàn)，迫切需要定義新的聚類算法，提高算法的穩(wěn)定性和保證聚類效果的準(zhǔn)確性。

2 大數(shù)據(jù)下的聚類算法劃分

現(xiàn)階段大數(shù)據(jù)聚類算法的具體的劃分方式如圖1所示。

2.1 單機聚類算法

單機聚類算法由傳統(tǒng)聚類算法、基于抽樣的聚類以及基于降維的聚類3個部分組成[1]。

2.1.1 傳統(tǒng)聚類算法

傳統(tǒng)聚類算法包含以下幾種算法[1]。

（1）分區(qū)聚類算法。該類型的劃分是基于點的相似性，在單個分區(qū)中根據(jù)彼此之間的分離距離來進行劃分，但是由于其需要用戶預(yù)先定義一個不具有確定性的參數(shù)K。現(xiàn)今具有代表性的分區(qū)算法主要有CLARANS，PAN和K-Means等。

（2）分層聚類算法。它就是指將數(shù)據(jù)按照不同的層次來進行劃分，劃分的依據(jù)是根據(jù)數(shù)據(jù)自底向上或自頂向下來進行的，劃分后的每種結(jié)果就代表了一種層次分類樹。現(xiàn)階段的代表性算法有ROCK，CURE和BIRCH等。

（3）基于密度的聚類算法。這種聚類劃分方法能夠有效地過濾噪音，以一種任意的方式來發(fā)現(xiàn)不同密度的區(qū)域，以此來達到處理數(shù)據(jù)的目的。

（4）基于網(wǎng)格的聚類。這種聚類算法主要由3個步驟組成：①將空間劃分為矩形方格；②將方格按照密度的高低進行篩選，選取密度低的方格；③對高密度的方格按照相鄰的結(jié)合方式進行歸類形成簇，這樣便可以降低復(fù)雜度，代表性的算法就有STING，CRIDCLUS以及CLICK等。

（5）基于模型的聚類。它可以解決測量劃分的不確定的問題，但是基于多元概率分布的規(guī)律進行處理不可避免地使得其在數(shù)據(jù)處理時的速度較慢。

2.1.2 基于抽樣的聚類算法

基于抽樣的聚類算法只需要在數(shù)據(jù)集的一個樣本上應(yīng)用聚類算法就能夠推廣到整個數(shù)據(jù)集，重點關(guān)注較小的數(shù)據(jù)，有效減少聚類的時間和節(jié)省空間，提高數(shù)據(jù)處理的經(jīng)濟效益。主要是根據(jù)以下的公式來推測其樣本的大小。

其中，f是抽取到指定數(shù)據(jù)的比例，（0≤f≤1）；n為數(shù)據(jù)規(guī)則；ni為簇Ci的規(guī)模。

抽樣聚類主要有以下3種聚類算法。

（1）基于隨機選擇的聚類算法（Clustering Algorithm based on Randomized Search，CLARANS）。它是由CLARA演變過來的，繼承了CLARA在處理規(guī)模數(shù)據(jù)上的優(yōu)勢，有效地節(jié)約運行的時間和降低算法的復(fù)雜性，其主要目的就是通過一個整體的圖來挖掘出其局部的最優(yōu)處理方式，在動態(tài)處理上具有明顯的優(yōu)勢。

（2）利用層次方法的平衡迭代規(guī)約和聚類（Balanced Iterative Reducing and Clustering Using Hierarchies，BTRCH）。它可以利用其自身的數(shù)據(jù)結(jié)構(gòu)，對所有存在的數(shù)據(jù)點進行篩選之后存放到內(nèi)存中去，提高數(shù)據(jù)的處理效率。在這個算法中有兩個重要的步驟，首先是它需要對數(shù)據(jù)點進行掃描并在內(nèi)存中建立一棵樹；其次就是運用聚類算法對所建立好的樹的各個葉子節(jié)點進行處理。

（3）針對大型數(shù)據(jù)庫的高效的聚類算法（Clustering Using Representatives，CURE）。前述所講的算法一般都采取單個的數(shù)據(jù)點來表示一個聚類，這種模式只適用球形聚類，在實際中會出現(xiàn)各種不同類型的聚類，而CURE便能夠很好地解決這類問題，利用一組分散的數(shù)據(jù)點來表示這個聚類，把每一個數(shù)據(jù)點都看成一個獨立的聚類，并依次對相鄰的聚類進行合并，以最短的距離為基礎(chǔ)，在每個階段利用堆和K-D樹來分別記錄和表示每個聚點間的距離以及每個聚類的所有代表點。同樣的，CURE也可以使用抽樣技術(shù)來提高計算的速度，利用分區(qū)的方式，對每個分區(qū)進行局部的分層聚類直到達到預(yù)設(shè)的聚類數(shù)的臨界值或者兩個需要合并的聚類之間距離的某個閾值。如此再重復(fù)幾次，使得沒有被抽中的數(shù)據(jù)點也可以被分配到就近的聚類中，通過常數(shù)因子來縮小代表點和聚類之間的中心距離。

2.1.3 基于降維的聚類算法

變量的數(shù)量和實例的數(shù)量是測量數(shù)據(jù)大小的兩個主要的維度，由于其在分析數(shù)據(jù)時很可能由于自身數(shù)值的大小而產(chǎn)生問題，因此在應(yīng)用聚類算法時必須要對其進行一個預(yù)先的處理，以降低失誤發(fā)生的可能性。降維的目的是基于一個事先定義的標(biāo)準(zhǔn)來消除無關(guān)和冗余的信息，縮小樣本空間，避免出現(xiàn)高維度情況下較為復(fù)雜的局面。

2.2 多機聚類

多機聚類是區(qū)別于單機聚類的一種聚類模式，其又可以分為并行聚類和基于MapReduce的聚類[2]。

并行聚類是指對數(shù)據(jù)進行劃分并將其分布在不同的機器上從而提高單個機器聚類的速度，并依此來達到增加擴展性的目的，從而保證在合理的時間內(nèi)獲取合理的結(jié)果。

MapReduce是一種將任務(wù)分布在大量的服務(wù)器上執(zhí)行的任務(wù)分區(qū)機制。Map是指將一個任務(wù)分解為更小的任務(wù)到不同服務(wù)器上執(zhí)行的一個階段；Reduce則是將這些階段所得出的結(jié)果進行執(zhí)行合并的階段。MapReduce可以利用改進的K-means算法來消除其在迭代上的依賴，提高數(shù)據(jù)處理的效能；同時，借助于改進后的最大期望（Expectation Maximization，EM）算法，它可以減少計算機時間和內(nèi)存的開銷，有效提高數(shù)據(jù)處理的效能。

3 結(jié)語

目前聚類的方法有很多，其的劃分方式也多種多樣。隨著大數(shù)據(jù)時代的不斷發(fā)展，越來越多的聚類方法逐漸被提了出來。本文對現(xiàn)有的大數(shù)據(jù)環(huán)境下的聚類算法的不同處理方式進行了劃分，雖然每種聚類算法都有適用的領(lǐng)域，但是也同時存在著需要改進的地方，本文只是指出了其中的一些問題，希望能夠在接下來的研究中不斷地發(fā)展聚類算法，為未來大數(shù)據(jù)環(huán)境的發(fā)展提供更多可靠高效的聚類算法。例如，可以采用面向大數(shù)據(jù)的快速自動聚類算法，適應(yīng)大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)自動聚類，達到降低聚類維度的目的，達到平衡性和提高它的速度；采用簡單的粒子編碼方式，與FRE-PSO算法相結(jié)合的模式來自動聚類等，使得聚類的效果最大化。

[參考文獻]

[1]李斌，王勁松，黃瑋.一種大數(shù)據(jù)環(huán)境下的新聚類算法[J].計算機科學(xué)，2015（12）：247-250.

[2]周麗華，黃成泉，王林.一種自動模糊聚類的算法[J].統(tǒng)計與決策，2014（20）：16-19.