在機器學(xué)習(xí)中，一個重要的任務(wù)就是需要定量化描述數(shù)據(jù)中的集聚現(xiàn)象。聚類分析也是模式識別和數(shù)據(jù)挖掘領(lǐng)域一個極富有挑戰(zhàn)性的研究方向。
聚類分析就是在無監(jiān)督學(xué)習(xí)下數(shù)據(jù)對象的探索合適的簇的過程，在探索過程中，簇與簇之間的數(shù)據(jù)對象差異越來越明顯，簇內(nèi)的數(shù)據(jù)對象之間差異越來越小。
聚類分析是模式識別,機器學(xué)習(xí)領(lǐng)域中的一個重要的研究課題，而聚類作為數(shù)據(jù)分析的常用工具，其重要性也在很多領(lǐng)域得到廣泛的認同。從聚類問題的提出到現(xiàn)在，已經(jīng)有很多聚類方法：
聚類的最終目標就是在已知無標簽的數(shù)據(jù)集上找到合適的簇，將這些無標簽的數(shù)據(jù)合理的劃分到合適的簇中。其中簇內(nèi)的樣本的相似度很高，不同簇的樣本間相似度很低。所以聚類過程是需要計算數(shù)據(jù)間的相似性的。這里就需要有一個計算數(shù)據(jù)間相似性的標準。
一般地，每個數(shù)據(jù)點都可以用一個向量表示，因此可以使用距離d或者相似性s來衡量兩個用向量表示的數(shù)據(jù)間的相似程度。由于表示數(shù)據(jù)點的向量元素具有不同的類型，可能是連續(xù)的，也可能是離散的，也可能有二者皆有的形式。因此距離函數(shù)d和相似系數(shù)s的定義也相應(yīng)存在不同的形式。
假設(shè)有n個點的數(shù)據(jù)集合{x1,x2, x3,…xn},d_ij表示數(shù)據(jù)點x_i,x_j之間的距離，可以將n個數(shù)據(jù)點x_i,x_j間的距離寫成矩陣形式。
對于上述的數(shù)據(jù)集，s_ij表示數(shù)據(jù)點x_i與x_j間的相似度系數(shù)，也可以將n個數(shù)據(jù)對象的相似度系數(shù)寫成矩陣形式。
距離矩陣D的性質(zhì)：在聚類分析中，距離矩陣一般滿足自反性，對稱性，非負性以及三角不等式等性質(zhì)。
自反性
對稱性
非負性
三角不等式
下表涵蓋了不同的計算數(shù)據(jù)點xi=(x_i1,x_i2,…,x_in)與數(shù)據(jù)點xj=(x_j1,x_j2,…,x_jn)之間的距離或相似度的方式。
表1
基于劃分的方法
假定一個具有n個點的數(shù)據(jù)的集合，我們需要把數(shù)據(jù)集劃分位k個子集，每個子集代表一個類別。常見的代表算法有kmeans，k-modes。K-means的具體思想：給定聚類個數(shù)k并隨機選定k個聚類中心c_k，計算所有數(shù)據(jù)點與k個聚類中心的歐式距離，再對k個距離值進行排序，找到每個數(shù)據(jù)點最近的聚類中心。遍歷完所有的數(shù)據(jù)點后，將每個聚類中心里的所有數(shù)據(jù)求平均值，將其更新為新的聚類中心。再重新遍歷所有的數(shù)據(jù)點，再依次計算每個數(shù)據(jù)點與k個聚類中心的距離，找到它們與之對應(yīng)的最近的聚類中心。遍歷完后更新聚類中心，以此類推，直至誤差值也就是每個簇內(nèi)部數(shù)據(jù)點與中心的距離之和小于一個給定值并且聚類中心無變化時，就得到了最終的聚類結(jié)果。
基于劃分的方法其實本質(zhì)是對聚類中心逐步進行優(yōu)化，不斷將各個聚類中心進行重新分配，直到聚類中心位置不變，即獲得最優(yōu)解。
算法的優(yōu)點：
算法的缺點：
基于層次的方法
基于層次的聚類方法是指對給定數(shù)據(jù)對象集合做類似于層次狀的分解，代表算法有CRUE，CHAMELEON,ROCK等。基于層次的聚類算法通?？梢苑譃?種，自底而上的合并聚類和自頂向下的分裂聚類。
合并聚類開始會將每個數(shù)據(jù)對象看作一個子集，也就是有n個子集，然后對這些子集逐層依次進行聚類，直到滿足無法合并的條件。分裂聚類是在一開始將所有的數(shù)據(jù)對象看成是一個集合，然后將其不斷分解成子集直至滿足不能再分解的條件為止。
基于層次的聚類算法通常會用平均距離，最大距離，最小距離作為衡量距離的方法，算法如果使用最大距離來度量類與類的距離時，稱為最遠鄰聚類算法；當(dāng)使用最小距離作為衡量類與類之間的距離時，稱為鄰聚類算法。
算法的優(yōu)點：
算法的缺點：
基于網(wǎng)絡(luò)的方法
基于網(wǎng)格的聚類算法的目標是將數(shù)據(jù)按照維數(shù)劃分為多層類似網(wǎng)格的結(jié)構(gòu)，常見的基于網(wǎng)格聚類的算法如：STING，WAVECLUSTER等。STING聚類算法按照維數(shù)將數(shù)據(jù)空間劃分為多個單元，子單元與原始數(shù)據(jù)的父單元構(gòu)成一個層次結(jié)構(gòu)。每個子單元存儲子單元的相關(guān)信息（均值，極值等）?；诰W(wǎng)格方法的時間復(fù)雜度為o(K)。其中K為最底層網(wǎng)格單元的數(shù)量。
算法的優(yōu)點：
算法的缺點：
基于密度的方法：
基于密度的聚類方法是將數(shù)據(jù)密度較大的區(qū)域連接，主要對有空間性的數(shù)據(jù)進行聚類。該聚類方法將簇看作數(shù)據(jù)點密度相對較高的數(shù)據(jù)對象集。該方法具有較大的靈活性，能有效克服孤立點的干擾。常見的基于密度的聚類算法有：DBSCAN，DENCLUE,OPTICS等。
DBSCAN是基于密度的聚類方法。DBSCAN通過計算每個數(shù)據(jù)點的鄰域來探尋密度可達對象集。如果一個點p的鄰域內(nèi)所包含密度可達對象點數(shù)目大于指定個數(shù)，則需要創(chuàng)建一個以點p為核心的新類。在此之后，DBSCAN算法反復(fù)從p的鄰域中找尋密度可達對象集中元素，繼續(xù)查找子集的密度可達對象集，當(dāng)沒有新的點構(gòu)成聚類中心點時，聚類過程結(jié)束。
算法的優(yōu)點：
算法的缺點：
神經(jīng)網(wǎng)絡(luò)的方法
自組織映射(SOM)神經(jīng)網(wǎng)絡(luò)，實質(zhì)上是一種淺層神經(jīng)網(wǎng)絡(luò)，只有輸入層和隱藏層兩層結(jié)構(gòu)，隱藏層中的節(jié)點代表其需要聚集的類。每個輸入的樣本在隱藏層中找到一個和它匹配度最高的節(jié)點，稱之為激活節(jié)點。SOM算法的具體思路是：首先初始化一些很小的隨機數(shù)b并賦值給所有的映射節(jié)點，然后計算輸入向量與輸出映射節(jié)點的歐式距離值，排序后找出的值最小映射節(jié)點稱為獲勝節(jié)點，重新把輸入向量映射到獲勝節(jié)點，調(diào)節(jié)該獲勝節(jié)點向量的權(quán)重值，同時按比例調(diào)節(jié)獲勝節(jié)點鄰域內(nèi)的節(jié)點權(quán)重值，把所有的輸入向量計算若干次，不斷的參數(shù)優(yōu)化后，相類似的輸入向量被映射到輸出層中臨近的區(qū)域，達到算法終止條件，得到最終的輸入向量的聚類。
算法的優(yōu)點：
算法的缺點：
基于圖的方法：
基于圖的聚類方法根據(jù)給定的數(shù)據(jù)集，計算樣本間的相似度矩陣，度矩陣以及拉普拉斯矩陣，并計算拉普拉斯的特征值和特征向量。然后選擇合適數(shù)目的特征向量b并使用傳統(tǒng)kmeans聚類，圖聚類可以在非凸樣本空間中聚類。
算法的優(yōu)點：
算法的缺點：
