在《聚類的幾個重要問題（理論篇）》中，我們主要講解了聚類的現實意義、無序屬性的距離度量方法、以及幾種聚類算法的優劣程度，但我沒有對聚類算法做出詳細講解，一方面是因爲聚類算法一般都比較簡單，另一方面則是聚類算法數量和種類都很多，我不得不以更爲宏觀講解其中的重要問題。在本文中，我們會利用幾種分佈不同的數據來對不同的聚類算法做對比，以及同一聚類算法中，不同參數對聚類算法的影響。

首先，因爲聚類的性能標準並不統一，通過數值比較也並不直觀，所以我們可以自然的想到，如果我們處理一個分類數據，如果此類數據利用聚類的結果與類別一致，那麼就可以說聚類達到了好的效果，通過特徵空間的直觀對比，我們就可以大致比較不同聚類算法的優劣。在這裏，我們的假設是，相似的樣本具有相同的類別。

我們構建樣例數據：

from sklearn import cluster,datasets

import matplotlib.pyplot as plt

import seaborn as sns

n_samples=1000

X,y=datasets.make_blobs(n_samples=n_samples, random_state=42,centers=5，cluster_std=3)

sns.set(style='darkgrid')

for i,v,l in [[0,'r','class_0'],[1,'b','class_1'],[2,'g','class_2']]:

plt.scatter(X[y==i][:,0],X[y==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.legend()

plt.show()

如圖，樣本分佈爲三個明顯的類，但某些藍色點摻雜到了紅色點裏面，我們需要特別注意這些點。

我們利用K均值算法需要設置初始的均值向量，也要預先指定好類別數，然後迭代更新這些均值向量，我們指定類別數爲3，隨機選擇均值向量：

from sklearn import datasets

import matplotlib.pyplot as plt

import seaborn as sns

from sklearn.cluster import KMeans

n_samples=1000

X,y=datasets.make_blobs(n_samples=n_samples,centers=3,random_state=42,cluster_std=3)

kmean=KMeans(n_clusters=3,init='random')

y_pre=kmean.fit_predict(X)

sns.set(style='darkgrid')

for i,v,l in [[0,'r','cluster_0'],[1,'b','cluster_1'],[2,'g','cluster_2']]:

plt.scatter(X[y_pre==i][:,0],X[y_pre==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.legend()

plt.title('Kmeans for Bolbs')

plt.show()

如圖，聚類的結果大致上只是對於這三個類重新標記了顏色，但在特徵空間的同樣位置，我們發現原本發生‘’摻雜‘’的點，在利用Kmeans算法之後變得嚴格分離，這是非常簡單就可以預料到的。

如果我們增加指定的類別數會發生什麼呢？

.......

kmean=KMeans(n_clusters=4,init='random')

.......

如圖，指定類別數4的Kmeans又強行把某一類拆分出兩個類，從kmeans的角度來看，初始的均值向量個數有幾個，我們就會分成幾類，這也是kmeans算法的缺點之一。

那麼初始均值向量該如何選擇，因爲初始化會對我們最後的結果造成一定的影響，因爲初始的均值向量完全隨機可能會將兩個靠得很近的樣本當作均值向量，那麼這兩個均值向量爲中心的簇就可能會把本來屬於同一類的樣本強行劃分爲兩個類。在實際應用中，我們會kmeans中插入一種叫做k-means++的技術，它改變了選擇初始均值向量的方法，距離越大的點會有更大的概率被選擇爲進入最終kmeans的算法。

但我們目前使用的數據是凸形結構的，如果我們選用不是凸形結構的數據會如何呢？我們使用在《核技巧》中提到過的一種環形數據：

.......

X,y=datasets.make_circles(n_samples=n_samples, factor=.5,noise=.05)

......

我們利用kmeans算法適應這樣的數據會產生什麼效果呢？

......

kmean=KMeans(n_clusters=2,init='k-means++')

y_pre=kmean.fit_predict(X)

sns.set(style='darkgrid')

for i,v,l in [[0,'r','cluster_0'],[1,'b','cluster_1']]:

plt.scatter(X[y_pre==i][:,0],X[y_pre==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.legend()

plt.title('Kmeans for Circles')

plt.show()

如圖，我們可以看到原本特徵空間的環形並沒有得到保持，而是分裂爲上下兩個類別，因爲kmeans算法會把所有的數據都當作凸形結構來處理。

我們轉用密度聚類來處理這個問題，以DBSCAN爲例，我們不需要設置類別數，在這方面比kmeans更加靈活，但我們主要需要另外兩個參數，一個叫maximum distance，它衡量的是樣本要離的多近才能算作鄰域，另一個叫做minimum samples，它衡量的是要包含多少個core point才能算作一個簇。此外，傳統的kmeans還有一個缺點，只要我們制定了類別數，樣本一定會被劃分到一個類，如果我們的數據包含噪聲的話，kmeans的效果就會受到很大影響。

表面上來看噪聲項是離羣點，但在DBSCAN中，可以被定義爲無法由core point通過密度可達關係包含的點，這些點不會屬於任何一個簇，我們構建DBSCAN，來觀察其在circles數據上的表現：

from sklearn import datasets

import matplotlib.pyplot as plt

import seaborn as sns

from sklearn.cluster import KMeans

from sklearn.cluster import DBSCAN

n_samples=1000

X,y=datasets.make_circles(n_samples=n_samples, factor=.5,noise=.05)

dbscan=DBSCAN(eps=0.08)

y_pre=dbscan.fit_predict(X)

sns.set(style='darkgrid')

for i,v,l in [[0,'r','cluster_0'],[1,'b','cluster_1'],[-1,'y','Noisy Samples']]:

plt.scatter(X[y_pre==i][:,0],X[y_pre==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.legend()

plt.title('DBSCAN for Circles')

plt.show()

如圖，DBSCAN可以良好的適應circles數據，並且將一些可能的噪聲項（黃色點）做了標記。

但是，DBSCAN對參數非常敏感，我們在這裏將鄰域參數設置爲了0.08，是希望足夠小的鄰域可以對類別有很好區分，但是太小的話，可能會將同一類的樣本劃到不同類，太大的話，可能會將不同的類當作一個類。如果對他進行微小調節，我們將會看到聚類結果發生很大的變化：

......

gammas=[0.01,0.08,0.2,5]

sns.set(style='darkgrid')

for k,j in enumerate(gammas):

dbscan=DBSCAN(eps=j)

y_pre=dbscan.fit_predict(X)

plt.subplot(len(gammas)/2,len(gammas)/2,k+1)

for i,v,l in [[0,'r','cluster_0'],[1,'b','cluster_1'],[-1,'y','Noisy Samples']]:

plt.scatter(X[y_pre==i][:,0],X[y_pre==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.title('$\gamma=$%s'%j)

plt.show()

如圖，我們可以看到，當鄰域太小的時候，以至於每個類都沒有足夠的密度可達對象，造成全部的樣本都被認爲是噪聲；當鄰域爲合適的大小時，大體形狀相似，但對噪聲的識別會不太一樣；而當鄰域太大時，所有的點都被當作core points，所以所有的樣本都會被當作一個類。

此外我們還可以利用層次聚類、網格聚類和概率模型聚類，但爲了更好的理解降維與聚類的關係，我們主要嘗試譜聚類的，譜聚類會對數據做降維，然後再利用kmeans的基本框架完成聚類，那麼降維之後真的可以處理非凸結構類型的數據嗎？

......

spectral=SpectralClustering(n_clusters=2,affinity='nearest_neighbors',eigen_solver='arpack')

y_pre=spectral.fit_predict(X)

sns.set(style='darkgrid')

for i,v,l in [[0,'r','cluster_0'],[1,'b','cluster_1']]:

plt.scatter(X[y_pre==i][:,0],X[y_pre==i][:,1],c=v,label=l,s=15,edgecolor='k')

plt.legend()

plt.title('Spectral Clusteringfor Circles')

plt.show()

如圖，spectral clustering 也可以處理非凸結構的數據，我們得到了與DBSCAN類似的結果。

之所以我特意展示spectral clustering的威力，並不是它是最好的，因爲根本不存在“最好”的算法，而是這裏面反映出我們在前面的文章《核技巧（kernel trick）》中提到的將一個線性不可分（非凸）變爲線性可分（凸），繼續再做降維，spectral clustering正是利用了這一思想，我們將會在後面的文章中反覆的利用前面的知識。

讀芯君開扒

課堂TIPS

• 譜聚類利用的是一種叫做拉普拉斯特徵映射的降維方法，本質上也是非線性的，所以纔會有處理非凸結構的能力。

• 高斯混合模型這裏並沒有提到，但進行極大似然估計時，會有隱變量需要估計，我們會使用經典的EM算法處理。

• 很多聚類算法都有不同的變種，以k-means爲例，爲了解決其需要指定類別數的問題，我們可以把類別數目K當作超參數來處理，然後根據不同K下的silhouette Coefficient來確定K；爲了解決初始化聚類中心的問題，除了k-means++，我們還會使用intelligent k-means；爲了解決噪聲點的影響，我們還有k-medians。

作者：唐僧不用海飛絲

如需轉載，請後臺留言，遵守轉載規範