郭雯雯 邵全義

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

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

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

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

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

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

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

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

2.1 單機(jī)聚類算法

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

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

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

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

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

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

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

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

2.1.2 基于抽樣的聚類算法

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

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

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

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

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

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

2.1.3 基于降維的聚類算法

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

2.2 多機(jī)聚類

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

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

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

3 結(jié)語

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

[參考文獻(xiàn)]

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

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