聚類研究背景：

在機(jī)器學(xué)習(xí)中，一個(gè)重要的任務(wù)就是需要定量化描述數(shù)據(jù)中的集聚現(xiàn)象。聚類分析也是模式識(shí)別和數(shù)據(jù)挖掘領(lǐng)域一個(gè)極富有挑戰(zhàn)性的研究方向。

聚類分析就是在無監(jiān)督學(xué)習(xí)下數(shù)據(jù)對象的探索合適的簇的過程，在探索過程中，簇與簇之間的數(shù)據(jù)對象差異越來越明顯，簇內(nèi)的數(shù)據(jù)對象之間差異越來越小。

聚類分析是模式識(shí)別,機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要的研究課題，而聚類作為數(shù)據(jù)分析的常用工具，其重要性也在很多領(lǐng)域得到廣泛的認(rèn)同。從聚類問題的提出到現(xiàn)在，已經(jīng)有很多聚類方法：

• 基于劃分的聚類方法，如K-means
• 基于層次的聚類方法，如CURE
• 基于網(wǎng)格的聚類方法，如STING
• 基于密度的聚類方法，如DBSCAN
• 基于神經(jīng)網(wǎng)絡(luò)的聚類方法，如SOM
• 基于圖的聚類方法，如Normalized cut
• 上述的聚類方法各自有各自的優(yōu)缺點(diǎn)，大家要意識(shí)到每個(gè)聚類方法都是都是基于不同理論背景并使用不同的學(xué)科方法來進(jìn)行聚類分析的，但面對錯(cuò)綜復(fù)雜的實(shí)際問題，并沒有哪一種具體的聚類方法可以完美勝任所有數(shù)據(jù)的聚類分析的，具體問題需要具體分析。

聚類算法的相似度量

聚類的最終目標(biāo)就是在已知無標(biāo)簽的數(shù)據(jù)集上找到合適的簇，將這些無標(biāo)簽的數(shù)據(jù)合理的劃分到合適的簇中。其中簇內(nèi)的樣本的相似度很高，不同簇的樣本間相似度很低。所以聚類過程是需要計(jì)算數(shù)據(jù)間的相似性的。這里就需要有一個(gè)計(jì)算數(shù)據(jù)間相似性的標(biāo)準(zhǔn)。

一般地，每個(gè)數(shù)據(jù)點(diǎn)都可以用一個(gè)向量表示，因此可以使用距離d或者相似性s來衡量兩個(gè)用向量表示的數(shù)據(jù)間的相似程度。由于表示數(shù)據(jù)點(diǎn)的向量元素具有不同的類型，可能是連續(xù)的，也可能是離散的，也可能有二者皆有的形式。因此距離函數(shù)d和相似系數(shù)s的定義也相應(yīng)存在不同的形式。

假設(shè)有n個(gè)點(diǎn)的數(shù)據(jù)集合{x1,x2, x3,…xn},d_ij表示數(shù)據(jù)點(diǎn)x_i,x_j之間的距離，可以將n個(gè)數(shù)據(jù)點(diǎn)x_i,x_j間的距離寫成矩陣形式。

對于上述的數(shù)據(jù)集，s_ij表示數(shù)據(jù)點(diǎn)x_i與x_j間的相似度系數(shù)，也可以將n個(gè)數(shù)據(jù)對象的相似度系數(shù)寫成矩陣形式。

距離矩陣D的性質(zhì)：在聚類分析中，距離矩陣一般滿足自反性，對稱性，非負(fù)性以及三角不等式等性質(zhì)。

• 自反性，即：

• 對稱性，即：

• 非負(fù)性，即：

• 三角不等式，即：

下表涵蓋了不同的計(jì)算數(shù)據(jù)點(diǎn)xi=(x_i1,x_i2,…,x_in)與數(shù)據(jù)點(diǎn)xj=(x_j1,x_j2,…,x_jn)之間的距離或相似度的方式。

典型的聚類分析算法

基于劃分的方法

假定一個(gè)具有n個(gè)點(diǎn)的數(shù)據(jù)的集合，我們需要把數(shù)據(jù)集劃分位k個(gè)子集，每個(gè)子集代表一個(gè)類別。常見的代表算法有kmeans，k-modes。K-means的具體思想：給定聚類個(gè)數(shù)k并隨機(jī)選定k個(gè)聚類中心c_k，計(jì)算所有數(shù)據(jù)點(diǎn)與k個(gè)聚類中心的歐式距離，再對k個(gè)距離值進(jìn)行排序，找到每個(gè)數(shù)據(jù)點(diǎn)最近的聚類中心。遍歷完所有的數(shù)據(jù)點(diǎn)后，將每個(gè)聚類中心里的所有數(shù)據(jù)求平均值，將其更新為新的聚類中心。再重新遍歷所有的數(shù)據(jù)點(diǎn)，再依次計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與k個(gè)聚類中心的距離，找到它們與之對應(yīng)的最近的聚類中心。遍歷完后更新聚類中心，以此類推，直至誤差值也就是每個(gè)簇內(nèi)部數(shù)據(jù)點(diǎn)與中心的距離之和小于一個(gè)給定值并且聚類中心無變化時(shí)，就得到了最終的聚類結(jié)果。

基于劃分的方法其實(shí)本質(zhì)是對聚類中心逐步進(jìn)行優(yōu)化，不斷將各個(gè)聚類中心進(jìn)行重新分配，直到聚類中心位置不變，即獲得最優(yōu)解。

算法的優(yōu)點(diǎn)：

• 當(dāng)類與類容易分開時(shí)，k-means算法的效果相對較好；
• 假設(shè)所有數(shù)據(jù)對象的數(shù)目，k為聚類個(gè)數(shù)，t為算法迭代的次數(shù)，則k-means時(shí)間復(fù)雜度為o(nKt)，故算法可以處理樣本量較大的數(shù)據(jù)。

算法的缺點(diǎn)：

• 初始聚類中心選擇的優(yōu)劣，對聚類結(jié)果有很大的影響；
• 只適用于凸?fàn)顢?shù)據(jù)；
• 需要人為設(shè)置聚類數(shù)目K，這對于調(diào)優(yōu)超參數(shù)K帶來一定的困擾。

基于層次的方法

基于層次的聚類方法是指對給定數(shù)據(jù)對象集合做類似于層次狀的分解，代表算法有CRUE，CHAMELEON,ROCK等?；趯哟蔚木垲愃惴ㄍǔ？梢苑譃?種，自底而上的合并聚類和自頂向下的分裂聚類。

合并聚類開始會(huì)將每個(gè)數(shù)據(jù)對象看作一個(gè)子集，也就是有n個(gè)子集，然后對這些子集逐層依次進(jìn)行聚類，直到滿足無法合并的條件。分裂聚類是在一開始將所有的數(shù)據(jù)對象看成是一個(gè)集合，然后將其不斷分解成子集直至滿足不能再分解的條件為止。

基于層次的聚類算法通常會(huì)用平均距離，最大距離，最小距離作為衡量距離的方法，算法如果使用最大距離來度量類與類的距離時(shí)，稱為最遠(yuǎn)鄰聚類算法；當(dāng)使用最小距離作為衡量類與類之間的距離時(shí)，稱為鄰聚類算法。

算法的優(yōu)點(diǎn)：

• 不需要預(yù)先設(shè)定聚類個(gè)數(shù)；
• 可以發(fā)現(xiàn)類的層次關(guān)系

算法的缺點(diǎn)：

• 計(jì)算時(shí)間復(fù)雜度高；
• 算法有可能導(dǎo)致聚類成鏈狀，而無法形成層次結(jié)構(gòu)。

基于網(wǎng)絡(luò)的方法

基于網(wǎng)格的聚類算法的目標(biāo)是將數(shù)據(jù)按照維數(shù)劃分為多層類似網(wǎng)格的結(jié)構(gòu)，常見的基于網(wǎng)格聚類的算法如：STING，WAVECLUSTER等。STING聚類算法按照維數(shù)將數(shù)據(jù)空間劃分為多個(gè)單元，子單元與原始數(shù)據(jù)的父單元構(gòu)成一個(gè)層次結(jié)構(gòu)。每個(gè)子單元存儲(chǔ)子單元的相關(guān)信息（均值，極值等）?；诰W(wǎng)格方法的時(shí)間復(fù)雜度為o(K)。其中K為最底層網(wǎng)格單元的數(shù)量。

算法的優(yōu)點(diǎn)：

• 基于網(wǎng)格計(jì)算是相互獨(dú)立的且互不干擾；
• 時(shí)間復(fù)雜度低

算法的缺點(diǎn)：

• 聚類的效果依賴于矩陣單元格劃分的大小，單元格劃分的細(xì)，聚類效果好，時(shí)間復(fù)雜度高；單元格劃分的粗，聚類效果差。時(shí)間復(fù)雜度小。

基于密度的方法：

基于密度的聚類方法是將數(shù)據(jù)密度較大的區(qū)域連接，主要對有空間性的數(shù)據(jù)進(jìn)行聚類。該聚類方法將簇看作數(shù)據(jù)點(diǎn)密度相對較高的數(shù)據(jù)對象集。該方法具有較大的靈活性，能有效克服孤立點(diǎn)的干擾。常見的基于密度的聚類算法有：DBSCAN，DENCLUE,OPTICS等。

DBSCAN是基于密度的聚類方法。DBSCAN通過計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的鄰域來探尋密度可達(dá)對象集。如果一個(gè)點(diǎn)p的鄰域內(nèi)所包含密度可達(dá)對象點(diǎn)數(shù)目大于指定個(gè)數(shù)，則需要?jiǎng)?chuàng)建一個(gè)以點(diǎn)p為核心的新類。在此之后，DBSCAN算法反復(fù)從p的鄰域中找尋密度可達(dá)對象集中元素，繼續(xù)查找子集的密度可達(dá)對象集，當(dāng)沒有新的點(diǎn)構(gòu)成聚類中心點(diǎn)時(shí)，聚類過程結(jié)束。

算法的優(yōu)點(diǎn)：

• 應(yīng)用比較廣泛，收斂速度快

算法的缺點(diǎn)：

• 不適合高維數(shù)據(jù)

神經(jīng)網(wǎng)絡(luò)的方法

自組織映射(SOM)神經(jīng)網(wǎng)絡(luò)，實(shí)質(zhì)上是一種淺層神經(jīng)網(wǎng)絡(luò)，只有輸入層和隱藏層兩層結(jié)構(gòu)，隱藏層中的節(jié)點(diǎn)代表其需要聚集的類。每個(gè)輸入的樣本在隱藏層中找到一個(gè)和它匹配度最高的節(jié)點(diǎn)，稱之為激活節(jié)點(diǎn)。SOM算法的具體思路是：首先初始化一些很小的隨機(jī)數(shù)b并賦值給所有的映射節(jié)點(diǎn)，然后計(jì)算輸入向量與輸出映射節(jié)點(diǎn)的歐式距離值，排序后找出的值最小映射節(jié)點(diǎn)稱為獲勝節(jié)點(diǎn)，重新把輸入向量映射到獲勝節(jié)點(diǎn)，調(diào)節(jié)該獲勝節(jié)點(diǎn)向量的權(quán)重值，同時(shí)按比例調(diào)節(jié)獲勝節(jié)點(diǎn)鄰域內(nèi)的節(jié)點(diǎn)權(quán)重值，把所有的輸入向量計(jì)算若干次，不斷的參數(shù)優(yōu)化后，相類似的輸入向量被映射到輸出層中臨近的區(qū)域，達(dá)到算法終止條件，得到最終的輸入向量的聚類。

算法的優(yōu)點(diǎn)：

• 不需要定義聚類個(gè)數(shù)，SOM有很好的拓?fù)浣Y(jié)構(gòu)，可視性較好

算法的缺點(diǎn)：

• 需要選擇參數(shù)很多，調(diào)參數(shù)需要經(jīng)驗(yàn)

基于圖的方法：

基于圖的聚類方法根據(jù)給定的數(shù)據(jù)集，計(jì)算樣本間的相似度矩陣，度矩陣以及拉普拉斯矩陣，并計(jì)算拉普拉斯的特征值和特征向量。然后選擇合適數(shù)目的特征向量b并使用傳統(tǒng)kmeans聚類，圖聚類可以在非凸樣本空間中聚類。

算法的優(yōu)點(diǎn)：

• 比傳統(tǒng)的kmeans聚類算法普適性更強(qiáng)，不僅可以用于凸數(shù)據(jù)，對于任意形狀的數(shù)據(jù)空間也能得到很好的聚類。

算法的缺點(diǎn)：

• 在進(jìn)行聚類之前需要設(shè)置具體應(yīng)用的尺度參數(shù)，通常需要一些經(jīng)驗(yàn)。選擇初始地聚類中心對整個(gè)聚類純度影響很大。很難找到圖劃分的優(yōu)化解，聚類個(gè)數(shù)選擇對于整個(gè)聚類的結(jié)果有很大影響。