一年前需要用聚類算法時(shí)，自己從一些sklearn文檔和博客粗略整理了一些相關(guān)的知識(shí)，記錄在電子筆記里備忘，現(xiàn)在發(fā)到網(wǎng)上，當(dāng)時(shí)就整理的就很亂，以后有空慢慢把內(nèi)容整理、完善，用作備忘。之前把電影標(biāo)簽信息的聚類結(jié)果作為隱式反饋放進(jìn)SVD++中去訓(xùn)練，里面有兩個(gè)小例子
外部度量：
利用條件熵定義的同質(zhì)性度量：
sklearn.metrics.homogeneity_score:每一個(gè)聚出的類僅包含一個(gè)類別的程度度量。
sklearn.metrics.completeness:每一個(gè)類別被指向相同聚出的類的程度度量。
sklearn.metrics.v_measure_score:上面兩者的一種折衷：
v = 2 * (homogeneity * completeness) / (homogeneity + completeness)
可以作為聚類結(jié)果的一種度量。
sklearn.metrics.adjusted_rand_score:調(diào)整的蘭德系數(shù)。
ARI取值范圍為[-1,1],從廣義的角度來講，ARI衡量的是兩個(gè)數(shù)據(jù)分布的吻合程度
sklearn.metrics.adjusted_mutual_info_score:調(diào)整的互信息。
利用基于互信息的方法來衡量聚類效果需要實(shí)際類別信息，MI與NMI取值范圍為[0,1],AMI取值范圍為[-1,1]。
在真實(shí)的分群label不知道的情況下(內(nèi)部度量)：
Calinski-Harabaz Index：
在scikit-learn中， Calinski-Harabasz Index對(duì)應(yīng)的方法是metrics.calinski_harabaz_score.
CH指標(biāo)通過計(jì)算類中各點(diǎn)與類中心的距離平方和來度量類內(nèi)的緊密度，通過計(jì)算各類中心點(diǎn)與數(shù)據(jù)集中心點(diǎn)距離平方和來度量數(shù)據(jù)集的分離度，CH指標(biāo)由分離度與緊密度的比值得到。從而，CH越大代表著類自身越緊密，類與類之間越分散，即更優(yōu)的聚類結(jié)果。
sklearn.metrics.silhouette_score:輪廓系數(shù)
silhouette_sample
對(duì)于一個(gè)樣本點(diǎn)(b - a)/max(a, b)
a平均類內(nèi)距離，b樣本點(diǎn)到與其最近的非此類的距離。
silihouette_score返回的是所有樣本的該值,取值范圍為[-1,1]。
這些度量均是越大越好
sklearn kmeans,聚類算法kmeans:
流程偽代碼：創(chuàng)建K個(gè)點(diǎn)作為起始質(zhì)心（通常是隨機(jī)）
當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)
對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)
對(duì)每個(gè)質(zhì)心
計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到最近的簇
對(duì)每個(gè)簇，計(jì)算簇中所有點(diǎn)的均值并將均值作為質(zhì)心
sklearn中的K-means
K-means算法應(yīng)該算是最常見的聚類算法，該算法的目的是選擇出質(zhì)心，使得各個(gè)聚類內(nèi)部的inertia值最小化，計(jì)算方法如下：
inertia可以被認(rèn)為是類內(nèi)聚合度的一種度量方式，這種度量方式的主要缺點(diǎn)是：
（1）inertia假設(shè)數(shù)據(jù)內(nèi)的聚類都是凸的并且各向同性（ convex and isotropic），
各項(xiàng)同性是指在數(shù)據(jù)的屬性在不同方向上是相同的。數(shù)據(jù)并不是總能夠滿足這些前提假設(shè)的，
所以當(dāng)數(shù)據(jù)事細(xì)長(zhǎng)簇的聚類，或者不規(guī)則形狀的流形時(shí)，K-means算法的效果不理想。
（2）inertia不是一種歸一化度量方式。一般來說，inertia值越小，說明聚類效果越好。
但是在高維空間中，歐式距離的值可能會(huì)呈現(xiàn)迅速增長(zhǎng)的趨勢(shì)，所以在進(jìn)行K-means之前首先進(jìn)行降維操作，如PCA等，可以解決高維空間中inertia快速增長(zhǎng)的問題，也有主意提高計(jì)算速度。
K-means算法可以在足夠長(zhǎng)的時(shí)間內(nèi)收斂，但有可能收斂到一個(gè)局部最小值。
聚類的結(jié)果高度依賴質(zhì)心的初始化，因此在計(jì)算過程中，采取的措施是進(jìn)行不止一次的聚類，每次都初始化不同的質(zhì)心。
sklearn中可以通過設(shè)置參數(shù)init='kmeans++'來采取k-means++初始化方案，
即初始化的質(zhì)心相互之間距離很遠(yuǎn)，這種方式相比于隨機(jī)初始質(zhì)心，能夠取得更好的效果。
另外，sklearn中可以通過參數(shù)n_job，使得K-means采用并行計(jì)算的方式。
##sklearn 中K-means的主要參數(shù)：
1) n_clusters: 設(shè)定的k值
2）max_iter： 最大的迭代次數(shù)，一般如果是凸數(shù)據(jù)集的話可以不管這個(gè)值，如果數(shù)據(jù)集不是凸的，可能很難收斂，此時(shí)可以指定最大的迭代次數(shù)讓算法可以及時(shí)退出循環(huán)。
3）n_init：用不同的初始化質(zhì)心運(yùn)行算法的次數(shù)。由于K-Means是結(jié)果受初始值影響的局部最優(yōu)的迭代算法，因此需要多跑幾次以選擇一個(gè)較好的聚類效果，默認(rèn)是10。如果你的k值較大，則可以適當(dāng)增大這個(gè)值。
4）init： 即初始值選擇的方式，可以為完全隨機(jī)選擇'random',優(yōu)化過的'k-means++'或者自己指定初始化的k個(gè)質(zhì)心。一般建議使用默認(rèn)的'k-means++'。
5）algorithm：有“auto”, “full” or “elkan”三種選擇。"full"就是我們傳統(tǒng)的K-Means算法， “elkan”elkan K-Means算法。默認(rèn)的"auto"則會(huì)根據(jù)數(shù)據(jù)值是否是稀疏的，來決定如何選擇"full"和“elkan”。一般來說建議直接用默認(rèn)的"auto"
sklearn 中K-means的主要方法
聚類的中心
print clf.cluster_centers_
每個(gè)樣本所屬的簇
print clf.labels_
用來評(píng)估簇的個(gè)數(shù)是否合適，距離越小說明簇分的越好，選取臨界點(diǎn)的簇個(gè)數(shù)
print clf.inertia_
Sum of distances of samples to their closest cluster center.
兩個(gè)小例子（很久以前弄的，寫得比較簡(jiǎn)略比較亂，有空再改，數(shù)據(jù)是movielen中的電影標(biāo)簽信息）：
例1：
kmeans_model = KMeans(n_clusters = 10, random_state = 1,init='k-means++')
pred = kmeans_model.fit_predict(matrix)
print pred
print kmeans_model.cluster_centers_ #聚類的中心
print kmeans_model.labels_#每個(gè)樣本所屬的簇
print kmeans_model.inertia_
例2，在區(qū)間[2,200]上遍歷k,并生成兩個(gè)聚類內(nèi)部評(píng)價(jià)指標(biāo)CH分、輪廓系數(shù)以及kmeans自帶inertia分和對(duì)應(yīng)的k值的圖片來選擇k：
i = []
y_silhouette_score = []
inertia_score = []
calinskiharabaz_score = []
for k in range(2,201):
kmeans_model = KMeans(n_clusters = k, random_state = 1,init='k-means++')
pred = kmeans_model.fit_predict(matrix)
silhouettescore = silhouette_score(matrix, pred)
print "silhouette_score for cluster '{}'".format(k)
print silhouettescore
calinskiharabazscore = calinski_harabaz_score(matrix, pred)
print "calinski_harabaz_score '{}'".format(k)
print calinskiharabazscore
i.append( k )
y_silhouette_score.append( silhouettescore )
inertia_score.append(kmeans_model.inertia_)
calinskiharabaz_score.append( calinskiharabazscore )
print "kmeans_model.inertia_score for cluster '{}'".format(k)
print kmeans_model.inertia_
#轉(zhuǎn)成字典方便查找
#dict_silhouette = dict(zip( i,y_silhouette_score))
#dict_inertia_score = dict(zip( i,inertia_score))
#dict_calinskiharabaz_score = dict(zip( i, calinskiharabaz_score))
plt.figure()
plt.plot(i,y_silhouette_score)
plt.xlabel("kmeans-k")
plt.ylabel("silhouette_score")
plt.title("matrix")
plt.figure()
plt.plot(i,inertia_score)
plt.xlabel("kmeans-k")
plt.ylabel("inertia_score(sum of squared)")
plt.title("matrix")
plt.figure()
plt.plot(i,calinskiharabaz_score)
plt.xlabel("kmeans-k")
plt.ylabel("calinski_harabaz_score")
plt.title("matrix")
Affinity Propagation（AP聚類算法）
其中兩點(diǎn)相似度s(i, j)的度量默認(rèn)采用負(fù)歐氏距離。
sklearn.cluster.AffinityPropagation
有參數(shù)preference（設(shè)定每一個(gè)點(diǎn)的偏好，將偏好于跟其他節(jié)點(diǎn)的相似性進(jìn)行比較，選擇
高的作為exmplar,未設(shè)定則使用所有相似性的中位數(shù)）、damping （阻尼系數(shù)，
利用阻尼系數(shù)與1-阻尼系數(shù)對(duì)r 及 a進(jìn)行有關(guān)迭代步數(shù)的凸組合，使得算法收斂
default 0.5 可以取值與[0.5, 1]）
cluster_centers_indices_:中心樣本的指標(biāo)。
AP算法的主要思想是通過數(shù)據(jù)點(diǎn)兩兩之間傳遞的信息進(jìn)行聚類。
該算法的主要優(yōu)點(diǎn)是能夠自主計(jì)算聚類的數(shù)目，而不用人為制定類的數(shù)目。
其缺點(diǎn)是計(jì)算復(fù)雜度較大 ，計(jì)算時(shí)間長(zhǎng)同時(shí)空間復(fù)雜度大，
因此該算法適合對(duì)數(shù)據(jù)量不大的問題進(jìn)行聚類分析。
數(shù)據(jù)點(diǎn)之間傳遞的信息包括兩個(gè)，吸引度（responsibility）r(i,k)和歸屬度（availability）a(i,k)。
吸引度r(i,k)度量的是質(zhì)心k應(yīng)當(dāng)作為點(diǎn)i的質(zhì)心的程度，
歸屬度a(i,k)度量的是點(diǎn)i應(yīng)當(dāng)選擇質(zhì)心k作為其質(zhì)心的程度。
其中t是迭代的次數(shù)，λ是阻尼因子，其值介于[0,1]，在sklearn.cluster.AffinityPropagation中通過參數(shù)damping進(jìn)行設(shè)置。
每次更新完矩陣后，就可以為每個(gè)數(shù)據(jù)點(diǎn)分配質(zhì)心，分配方式?是針對(duì)數(shù)據(jù)點(diǎn)i，遍歷所有數(shù)據(jù)點(diǎn)k（包括其自身），
找到一個(gè)k使得r(i,k)+a(i,k)的值最大，則點(diǎn)k就是點(diǎn)i所屬的質(zhì)心，迭代這個(gè)過程直至收斂。
所謂收斂就是所有點(diǎn)所屬的質(zhì)心不再變化
Mean Shift
首先說明不引入核函數(shù)時(shí)的情況。
算法大致流程為：隨機(jī)選取一個(gè)點(diǎn)作為球心，以一定半徑畫一個(gè)高維球（數(shù)據(jù)可能是高維的），
在這個(gè)球范圍內(nèi)的點(diǎn)都是這個(gè)球心的鄰居。這些鄰居相對(duì)于球心都存在一個(gè)偏移向量，
將這些向量相加求和再平均，就得到一個(gè)mean shift，起點(diǎn)在原球心，重點(diǎn)在球內(nèi)的其他位置。
以mean shift的重點(diǎn)作為新的球心，重復(fù)上述過程直至收斂。
這個(gè)計(jì)算過程中，高維球內(nèi)的點(diǎn)，無論其距離球心距離多遠(yuǎn)，對(duì)于mean shift的計(jì)算權(quán)重是一樣的。
為了改善這種情況，在迭代計(jì)算mean shift的過程中引入了核函數(shù)
sklearn中相關(guān)實(shí)現(xiàn)是sklearn.cluster.MeanShift。
層次聚類說明
sklearn中實(shí)現(xiàn)的是自底向上的層次聚類，實(shí)現(xiàn)方法是sklearn.cluster.AgglomerativeClustering。
初始時(shí)，所有點(diǎn)各自單獨(dú)成為一類，然后采取某種度量方法將相近的類進(jìn)行合并，并且度量方法有多種選擇。
合并的過程可以構(gòu)成一個(gè)樹結(jié)構(gòu)，其根節(jié)點(diǎn)就是所有數(shù)據(jù)的集合，葉子節(jié)點(diǎn)就是各條單一數(shù)據(jù)。
sklearn.cluster.AgglomerativeClustering中可以通過參數(shù)linkage選擇不同的度量方法，用來度量?jī)蓚€(gè)類之間的距離，
可選參數(shù)有ward,complete,average三個(gè)。
ward:選擇這樣的兩個(gè)類進(jìn)行合并，合并后的類的離差平方和最小。
complete:兩個(gè)類的聚類被定義為類內(nèi)數(shù)據(jù)的最大距離，即分屬兩個(gè)類的距離最遠(yuǎn)的兩個(gè)點(diǎn)的距離。
選擇兩個(gè)類進(jìn)行合并時(shí)，從現(xiàn)有的類中找到兩個(gè)類使得這個(gè)值最小，就合并這兩個(gè)類。
average:兩個(gè)類內(nèi)數(shù)據(jù)兩兩之間距離的平均值作為兩個(gè)類的距離。
同樣的，從現(xiàn)有的類中找到兩個(gè)類使得這個(gè)值最小，就合并這兩個(gè)類。
Agglomerative cluster有一個(gè)缺點(diǎn)，就是rich get richer現(xiàn)象，
這可能導(dǎo)致聚類結(jié)果得到的類的大小不均衡。
從這個(gè)角度考慮，complete策略效果最差，ward得到的類的大小最為均衡。
但是在ward策略下，affinity參數(shù)只能是“euclidean”，即歐式距離。
如果在歐氏距離不適用的環(huán)境中，average is a good alternative。
另外還應(yīng)該注意參數(shù)affinity，這個(gè)參數(shù)設(shè)置的是計(jì)算兩個(gè)點(diǎn)之間距離時(shí)采用的策略，
注意和參數(shù)linkage區(qū)分，linkage設(shè)置的是衡量?jī)蓚€(gè)類之間距離時(shí)采用的策略，
而點(diǎn)之間的距離衡量是類之間距離衡量的基礎(chǔ)。
affinity的可選數(shù)值包括 “euclidean”, “l(fā)1”, “l(fā)2”, “manhattan”, “cosine”,
‘precomputed’. If linkage is “ward”, only “euclidean” is accepted.
DBSCAN
DBSCAN算法的主要思想是，認(rèn)為密度稠密的區(qū)域是一個(gè)聚類，各個(gè)聚類是被密度稀疏的區(qū)域劃分開來的。
也就是說，密度稀疏的區(qū)域構(gòu)成了各個(gè)聚類之間的劃分界限。與K-means等算法相比，該算法的主要優(yōu)點(diǎn)包括：可以自主計(jì)算聚類的數(shù)目，不需要認(rèn)為指定；不要求類的形狀是凸的，可以是任意形狀的。
DBSCAN中包含的幾個(gè)關(guān)鍵概念包括core sample，non-core sample，min_sample，eps。
core samle是指，在該數(shù)據(jù)點(diǎn)周圍eps范圍內(nèi)，至少包含min_sample個(gè)其他數(shù)據(jù)點(diǎn)，則該點(diǎn)是core sample，
這些數(shù)據(jù)點(diǎn)稱為core sample的鄰居。與之對(duì)應(yīng)的，non-sample是該點(diǎn)周圍eps范圍內(nèi)，所包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)少于min_sample個(gè)。從定義可知，core sample是位于密度稠密區(qū)域的點(diǎn)。
一個(gè)聚類就是一個(gè)core sample的集合，這個(gè)集合的構(gòu)建過程是一個(gè)遞歸的構(gòu)成。
首先，找到任意個(gè)core sample，然后從它的鄰居中找到core sample，
接著遞歸的從這些鄰居中的core sample的鄰居中繼續(xù)找core sample。
要注意core sample的鄰居中不僅有其他core sample，也有一些non-core smaple，
也正是因?yàn)檫@個(gè)原因，聚類集合中也包含少量的non-core sample，它們是聚類中core sample的鄰居，
但自己不是core sample。這些non-core sample構(gòu)成了邊界。
在確定了如何通過單一core sample找到了一個(gè)聚類后，下面描述DBSCAN算法的整個(gè)流程。
首先，掃描數(shù)據(jù)集找到任意一個(gè)core sample，以此core sample為起點(diǎn)，按照上一段描述的方法進(jìn)行擴(kuò)充，確定一個(gè)聚類。然后，再次掃描數(shù)據(jù)集，找到任意一個(gè)不屬于以確定類別的core sample，重復(fù)擴(kuò)充過程，再次確定一個(gè)聚類。
迭代這個(gè)過程，直至數(shù)據(jù)集中不再包含有core sample。
這也是為什么DBSCAN不用認(rèn)為指定聚類數(shù)目的原因。
DBSCAN算法包含一定的非確定性。數(shù)據(jù)中的core sample總是會(huì)被分配到相同的聚類中的，哪怕在統(tǒng)一數(shù)據(jù)集上多次運(yùn)行DBSCAN。其不確定性主要體現(xiàn)在non-core sample的分配上。
一個(gè)non-core sample可能同時(shí)是兩個(gè)core sample的鄰居，而這兩個(gè)core sample隸屬于不同的聚類。
DBSCAN中，這個(gè)non-core sample會(huì)被分配給首先生成的那個(gè)聚類，而哪個(gè)聚類先生成是隨機(jī)的。
sklearn中DBSCAN的實(shí)現(xiàn)中，鄰居的確定使用的ball tree和kd-tree思想，這就避免了計(jì)算距離矩陣。
