聚類分析算法的分析與評價

文/李芝峰 張妍

1 引言

在信息時代存儲人類活動的文本、視頻、圖像和音頻數(shù)據(jù)龐大，把數(shù)據(jù)對象有效的區(qū)分開是一個熱門的研究課題。

聚類分析算法是深度學(xué)習(xí)中的一個常用的算法，它根據(jù)對象差異，把不同類的對象區(qū)分開。聚類分析算法的目標是把混雜在一起的數(shù)據(jù)盡可能的分隔開，使同一類對象的相似程度盡可能大，使不同對象的相似程度盡可能的小。聚類分析算法是一種無監(jiān)督學(xué)習(xí)的模式。目前聚類方法大體有以下類別：基于層次聚類算法、基于劃分聚類算法、基于密度聚類算法、基于網(wǎng)格聚類算法、基于模型聚類算法、基于模糊聚類算法。隨著理論研究的不斷深入，聚類分析算法已經(jīng)在語音分離、視頻人臉檢測、圖像皮膚檢測以及其他領(lǐng)域取得了不錯的研究結(jié)果。

2 聚類分析算法

聚類方法分類不是很明確，聚類方法大體可以分為：基于層次聚類算法、基于劃分聚類算法、基于密度聚類算法、基于網(wǎng)格聚類算法、基于模型聚類算法、基于模糊聚類算法。聚類方法包含著其他幾種聚類分析算法，存在的每一種聚類分析算法都有這自己長處和短處。

2.1 劃分法

劃分法保持簇內(nèi)對象相似性高，簇外對象差異高。該方法的劃分大多是基于距離的，其原理是：首先選擇K個初始聚類中心點；然后數(shù)據(jù)加入到距離中心點最近中；其次重新計算新類中心點，并作為新的中心點。

基于劃分聚類算法有K-means算法、k-modes算 法、k-prototypes算 法、k-medoids算 法、CLARA算 法、CLARANS算 法、Focused CLARAN算法、PCM算法等其他算法。這類算法的優(yōu)點是實現(xiàn)簡單、時間復(fù)雜度和空間復(fù)雜度低，缺點是容易出現(xiàn)局部最優(yōu)、對噪聲很敏感、對初始中心點選取敏感、不能解決非凸數(shù)據(jù)。

2.2 層次法

層次法是對數(shù)據(jù)對象進行分解，可以是自上而下的策略，也可以是自下而上的策略，目前自下而上的聚合策略使用較多。該方法可以是基于距離或者密度或者連通性，自下而上的原理是：首先將給定的N個對象分為N類；然后計算兩個類距離最小并進行合并；其次重新計算類之間的距離。

基于層次聚類算法有CURE算法、ROCK算法、變色龍算法CHEMALOEN算法、SBAC算法、BIRCH算法、BUBBLE算法、BUBBLE-FM算法等其他算法。這類算法的優(yōu)點時是可解釋性好、可以解決非球形簇，缺點是時間復(fù)雜度高、并且不能更正以前計算錯誤。

2.3 密度法

密度法是為了解決不規(guī)則形狀的聚類方法。該方法是將密集的滿足條件的點歸類起來，并使合并起來的高密度區(qū)域劃分為密度相連點最大集合的簇。該方法是基于密度的，其原理是：首先找到一個數(shù)據(jù)核心點；然后找到以該數(shù)據(jù)核心點為中心的密度相連的其他數(shù)據(jù)點，進行下一步的區(qū)域擴充。

基于密度聚類算法有基于密度的噪聲應(yīng)用空間聚類DBSCAN、DBLASD算法等其他算法。這類算法的優(yōu)點是對噪聲點出現(xiàn)不敏感、可以識別多種規(guī)則形狀的聚類，缺點是輸入?yún)?shù)會很大程度上影響聚類結(jié)果、對較稀的聚類和密度較大且離得較近的類區(qū)分不是很有效。

2.4 網(wǎng)格法

網(wǎng)格法是將數(shù)據(jù)對象轉(zhuǎn)化成一定數(shù)目的單元格并會形成網(wǎng)狀結(jié)構(gòu)。該方法是基于密度的，其原理是：首先采用降維措施，將N維空間降維成單維空間并分割成等長的段；然后根據(jù)網(wǎng)格單元中含有數(shù)據(jù)量的閾值，將大于閾值的視為高密度單元，否則視為低密度單元；其次將相連的高密度單元識別為同一個簇。

基于網(wǎng)格聚類算法有小波聚類算法WaveCluster、基于密度和網(wǎng)格聚類算法CLIQUE等其他算法。這類算法的優(yōu)點是時間復(fù)雜度低，缺點是算法對輸入的參數(shù)很敏感、區(qū)分不規(guī)則分布的數(shù)據(jù)很困難、維度災(zāi)難。

2.5 模型法

模型法是一個模型一個類，然后使用合適的數(shù)據(jù)集去不斷的訓(xùn)練這個認為合適的模型，這樣訓(xùn)練出來的模型可能很符合數(shù)據(jù)的密度分布函數(shù)。在使用到的數(shù)據(jù)集是由概率分布所組成的前提下，該方法才能有效進行下去。

現(xiàn)在基于模型聚類算法有統(tǒng)計方案和神經(jīng)網(wǎng)絡(luò)方案兩種方案，其中統(tǒng)計學(xué)方案算法有COBWEB算 法、CLASSIT算 法、AutoClass算法等其他算法；神經(jīng)網(wǎng)絡(luò)方案算法有SOMs算法等其他算法。這類算法的優(yōu)點是劃分類以概率形式展現(xiàn)出來，缺點是執(zhí)行效率不高。

2.6 模糊法

模糊法是采用了模糊集合的理論，是為了克服非此即彼的分類缺點，該算法假設(shè)了數(shù)據(jù)是以概率的形式屬于其中一個聚類。

基于模糊聚類算法有FCM算法。這類算法優(yōu)點是能夠得到一個參考樣本分類結(jié)果可能性的計算方法，缺點是算法性能過渡依賴初始聚類中心的選擇。

3 結(jié)束語

本文中的聚類算法能夠較好的實現(xiàn)數(shù)據(jù)的分類。存在的每一種聚類算法都是為了更好的解決現(xiàn)實中的分類問題而存在。每一種聚類算法都是有自己的適應(yīng)場景，也都有自己的優(yōu)缺點。聚類算法雖然能夠?qū)?shù)據(jù)進行分類，但是還是存在聚類數(shù)目是否自動問題，聚類算法優(yōu)點不能夠充分利用的問題，以及大規(guī)模數(shù)據(jù)和高維度數(shù)據(jù)處理能力的問題等其他問題。