一年前需要用聚類算法時塘装，自己從一些sklearn文檔和博客粗略整理了一些相關(guān)的知識急迂，記錄在電子筆記里備忘，現(xiàn)在發(fā)到網(wǎng)上蹦肴，當時就整理的就很亂僚碎，以后有空慢慢把內(nèi)容整理、完善阴幌，用作備忘勺阐。之前把電影標簽信息的聚類結(jié)果作為隱式反饋放進SVD++中去訓練，里面有兩個小例子
外部度量：
利用條件熵定義的同質(zhì)性度量：
sklearn.metrics.homogeneity_score:每一個聚出的類僅包含一個類別的程度度量矛双。
sklearn.metrics.completeness:每一個類別被指向相同聚出的類的程度度量渊抽。
sklearn.metrics.v_measure_score:上面兩者的一種折衷：
v = 2 * (homogeneity * completeness) / (homogeneity + completeness)
可以作為聚類結(jié)果的一種度量。
sklearn.metrics.adjusted_rand_score:調(diào)整的蘭德系數(shù)议忽。
ARI取值范圍為[-1,1],從廣義的角度來講懒闷，ARI衡量的是兩個數(shù)據(jù)分布的吻合程度
sklearn.metrics.adjusted_mutual_info_score:調(diào)整的互信息。
利用基于互信息的方法來衡量聚類效果需要實際類別信息徙瓶，MI與NMI取值范圍為[0,1],AMI取值范圍為[-1,1]毛雇。
在真實的分群label不知道的情況下(內(nèi)部度量)：
Calinski-Harabaz Index：
在scikit-learn中， Calinski-Harabasz Index對應的方法是metrics.calinski_harabaz_score.
CH指標通過計算類中各點與類中心的距離平方和來度量類內(nèi)的緊密度侦镇，通過計算各類中心點與數(shù)據(jù)集中心點距離平方和來度量數(shù)據(jù)集的分離度，CH指標由分離度與緊密度的比值得到织阅。從而壳繁，CH越大代表著類自身越緊密，類與類之間越分散荔棉，即更優(yōu)的聚類結(jié)果闹炉。
sklearn.metrics.silhouette_score:輪廓系數(shù)
silhouette_sample
對于一個樣本點(b - a)/max(a, b)
a平均類內(nèi)距離，b樣本點到與其最近的非此類的距離润樱。
silihouette_score返回的是所有樣本的該值,取值范圍為[-1,1]渣触。
這些度量均是越大越好
sklearn kmeans,聚類算法kmeans:
流程偽代碼：創(chuàng)建K個點作為起始質(zhì)心（通常是隨機）
當任意一個點的簇分配結(jié)果發(fā)生改變時
對數(shù)據(jù)集中的每個數(shù)據(jù)點
對每個質(zhì)心
計算質(zhì)心與數(shù)據(jù)點之間的距離
將數(shù)據(jù)點分配到最近的簇
對每個簇，計算簇中所有點的均值并將均值作為質(zhì)心
sklearn中的K-means
K-means算法應該算是最常見的聚類算法壹若，該算法的目的是選擇出質(zhì)心嗅钻，使得各個聚類內(nèi)部的inertia值最小化皂冰，計算方法如下：
inertia可以被認為是類內(nèi)聚合度的一種度量方式，這種度量方式的主要缺點是：
（1）inertia假設(shè)數(shù)據(jù)內(nèi)的聚類都是凸的并且各向同性（ convex and isotropic）养篓，
各項同性是指在數(shù)據(jù)的屬性在不同方向上是相同的秃流。數(shù)據(jù)并不是總能夠滿足這些前提假設(shè)的，
所以當數(shù)據(jù)事細長簇的聚類柳弄，或者不規(guī)則形狀的流形時舶胀，K-means算法的效果不理想。
（2）inertia不是一種歸一化度量方式碧注。一般來說嚣伐，inertia值越小，說明聚類效果越好萍丐。
但是在高維空間中轩端，歐式距離的值可能會呈現(xiàn)迅速增長的趨勢，所以在進行K-means之前首先進行降維操作碉纺，如PCA等船万，可以解決高維空間中inertia快速增長的問題，也有主意提高計算速度骨田。
K-means算法可以在足夠長的時間內(nèi)收斂耿导，但有可能收斂到一個局部最小值。
聚類的結(jié)果高度依賴質(zhì)心的初始化态贤，因此在計算過程中舱呻，采取的措施是進行不止一次的聚類，每次都初始化不同的質(zhì)心悠汽。
sklearn中可以通過設(shè)置參數(shù)init='kmeans++'來采取k-means++初始化方案箱吕，
即初始化的質(zhì)心相互之間距離很遠，這種方式相比于隨機初始質(zhì)心柿冲，能夠取得更好的效果茬高。
另外，sklearn中可以通過參數(shù)n_job假抄，使得K-means采用并行計算的方式怎栽。
##sklearn 中K-means的主要參數(shù)：
1) n_clusters: 設(shè)定的k值
2）max_iter： 最大的迭代次數(shù)，一般如果是凸數(shù)據(jù)集的話可以不管這個值宿饱，如果數(shù)據(jù)集不是凸的熏瞄，可能很難收斂，此時可以指定最大的迭代次數(shù)讓算法可以及時退出循環(huán)谬以。
3）n_init：用不同的初始化質(zhì)心運行算法的次數(shù)强饮。由于K-Means是結(jié)果受初始值影響的局部最優(yōu)的迭代算法，因此需要多跑幾次以選擇一個較好的聚類效果为黎，默認是10邮丰。如果你的k值較大行您，則可以適當增大這個值。
4）init： 即初始值選擇的方式柠座，可以為完全隨機選擇'random',優(yōu)化過的'k-means++'或者自己指定初始化的k個質(zhì)心邑雅。一般建議使用默認的'k-means++'。
5）algorithm：有“auto”, “full” or “elkan”三種選擇妈经。"full"就是我們傳統(tǒng)的K-Means算法淮野， “elkan”elkan K-Means算法。默認的"auto"則會根據(jù)數(shù)據(jù)值是否是稀疏的吹泡，來決定如何選擇"full"和“elkan”骤星。一般來說建議直接用默認的"auto"
sklearn 中K-means的主要方法
聚類的中心
print clf.cluster_centers_
每個樣本所屬的簇
print clf.labels_
用來評估簇的個數(shù)是否合適，距離越小說明簇分的越好爆哑，選取臨界點的簇個數(shù)
print clf.inertia_
Sum of distances of samples to their closest cluster center.
兩個小例子（很久以前弄的洞难，寫得比較簡略比較亂，有空再改揭朝，數(shù)據(jù)是movielen中的電影標簽信息）：
例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_#每個樣本所屬的簇
print kmeans_model.inertia_
例2队贱，在區(qū)間[2,200]上遍歷k,并生成兩個聚類內(nèi)部評價指標CH分、輪廓系數(shù)以及kmeans自帶inertia分和對應的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聚類算法）
其中兩點相似度s(i, j)的度量默認采用負歐氏距離潭袱。
sklearn.cluster.AffinityPropagation
有參數(shù)preference（設(shè)定每一個點的偏好柱嫌，將偏好于跟其他節(jié)點的相似性進行比較，選擇
高的作為exmplar,未設(shè)定則使用所有相似性的中位數(shù)）屯换、damping （阻尼系數(shù)编丘，
利用阻尼系數(shù)與1-阻尼系數(shù)對r 及 a進行有關(guān)迭代步數(shù)的凸組合，使得算法收斂
default 0.5 可以取值與[0.5, 1]）
cluster_centers_indices_:中心樣本的指標彤悔。
AP算法的主要思想是通過數(shù)據(jù)點兩兩之間傳遞的信息進行聚類嘉抓。
該算法的主要優(yōu)點是能夠自主計算聚類的數(shù)目，而不用人為制定類的數(shù)目晕窑。
其缺點是計算復雜度較大 抑片，計算時間長同時空間復雜度大，
因此該算法適合對數(shù)據(jù)量不大的問題進行聚類分析杨赤。
數(shù)據(jù)點之間傳遞的信息包括兩個蓝丙，吸引度（responsibility）r(i,k)和歸屬度（availability）a(i,k)。
吸引度r(i,k)度量的是質(zhì)心k應當作為點i的質(zhì)心的程度望拖，
歸屬度a(i,k)度量的是點i應當選擇質(zhì)心k作為其質(zhì)心的程度。
其中t是迭代的次數(shù)挫鸽，λ是阻尼因子说敏，其值介于[0,1]，在sklearn.cluster.AffinityPropagation中通過參數(shù)damping進行設(shè)置丢郊。
每次更新完矩陣后盔沫，就可以為每個數(shù)據(jù)點分配質(zhì)心医咨，分配方式?是針對數(shù)據(jù)點i，遍歷所有數(shù)據(jù)點k（包括其自身）架诞，
找到一個k使得r(i,k)+a(i,k)的值最大拟淮，則點k就是點i所屬的質(zhì)心，迭代這個過程直至收斂谴忧。
所謂收斂就是所有點所屬的質(zhì)心不再變化
Mean Shift
首先說明不引入核函數(shù)時的情況很泊。
算法大致流程為：隨機選取一個點作為球心，以一定半徑畫一個高維球（數(shù)據(jù)可能是高維的）沾谓，
在這個球范圍內(nèi)的點都是這個球心的鄰居委造。這些鄰居相對于球心都存在一個偏移向量，
將這些向量相加求和再平均均驶，就得到一個mean shift昏兆，起點在原球心，重點在球內(nèi)的其他位置妇穴。
以mean shift的重點作為新的球心爬虱，重復上述過程直至收斂。
這個計算過程中腾它，高維球內(nèi)的點跑筝，無論其距離球心距離多遠，對于mean shift的計算權(quán)重是一樣的携狭。
為了改善這種情況继蜡，在迭代計算mean shift的過程中引入了核函數(shù)
sklearn中相關(guān)實現(xiàn)是sklearn.cluster.MeanShift。
層次聚類說明
sklearn中實現(xiàn)的是自底向上的層次聚類逛腿，實現(xiàn)方法是sklearn.cluster.AgglomerativeClustering稀并。
初始時，所有點各自單獨成為一類单默，然后采取某種度量方法將相近的類進行合并碘举，并且度量方法有多種選擇。
合并的過程可以構(gòu)成一個樹結(jié)構(gòu)搁廓，其根節(jié)點就是所有數(shù)據(jù)的集合引颈，葉子節(jié)點就是各條單一數(shù)據(jù)。
sklearn.cluster.AgglomerativeClustering中可以通過參數(shù)linkage選擇不同的度量方法境蜕，用來度量兩個類之間的距離蝙场，
可選參數(shù)有ward,complete,average三個。
ward:選擇這樣的兩個類進行合并粱年，合并后的類的離差平方和最小售滤。
complete:兩個類的聚類被定義為類內(nèi)數(shù)據(jù)的最大距離，即分屬兩個類的距離最遠的兩個點的距離。
選擇兩個類進行合并時完箩，從現(xiàn)有的類中找到兩個類使得這個值最小赐俗，就合并這兩個類。
average:兩個類內(nèi)數(shù)據(jù)兩兩之間距離的平均值作為兩個類的距離弊知。
同樣的阻逮，從現(xiàn)有的類中找到兩個類使得這個值最小，就合并這兩個類秩彤。
Agglomerative cluster有一個缺點叔扼，就是rich get richer現(xiàn)象，
這可能導致聚類結(jié)果得到的類的大小不均衡呐舔。
從這個角度考慮币励，complete策略效果最差，ward得到的類的大小最為均衡珊拼。
但是在ward策略下食呻，affinity參數(shù)只能是“euclidean”，即歐式距離澎现。
如果在歐氏距離不適用的環(huán)境中仅胞，average is a good alternative。
另外還應該注意參數(shù)affinity剑辫，這個參數(shù)設(shè)置的是計算兩個點之間距離時采用的策略干旧，
注意和參數(shù)linkage區(qū)分，linkage設(shè)置的是衡量兩個類之間距離時采用的策略妹蔽，
而點之間的距離衡量是類之間距離衡量的基礎(chǔ)椎眯。
affinity的可選數(shù)值包括 “euclidean”, “l(fā)1”, “l(fā)2”, “manhattan”, “cosine”,
‘precomputed’. If linkage is “ward”, only “euclidean” is accepted.
DBSCAN
DBSCAN算法的主要思想是，認為密度稠密的區(qū)域是一個聚類胳岂，各個聚類是被密度稀疏的區(qū)域劃分開來的编整。
也就是說，密度稀疏的區(qū)域構(gòu)成了各個聚類之間的劃分界限乳丰。與K-means等算法相比掌测，該算法的主要優(yōu)點包括：可以自主計算聚類的數(shù)目，不需要認為指定产园；不要求類的形狀是凸的汞斧，可以是任意形狀的。
DBSCAN中包含的幾個關(guān)鍵概念包括core sample什燕，non-core sample粘勒，min_sample，eps屎即。
core samle是指仲义，在該數(shù)據(jù)點周圍eps范圍內(nèi)，至少包含min_sample個其他數(shù)據(jù)點，則該點是core sample埃撵，
這些數(shù)據(jù)點稱為core sample的鄰居。與之對應的虽另，non-sample是該點周圍eps范圍內(nèi)暂刘，所包含的數(shù)據(jù)點個數(shù)少于min_sample個。從定義可知接剩，core sample是位于密度稠密區(qū)域的點腌巾。
一個聚類就是一個core sample的集合撬讽，這個集合的構(gòu)建過程是一個遞歸的構(gòu)成。
首先森缠，找到任意個core sample，然后從它的鄰居中找到core sample仪缸，
接著遞歸的從這些鄰居中的core sample的鄰居中繼續(xù)找core sample贵涵。
要注意core sample的鄰居中不僅有其他core sample，也有一些non-core smaple恰画，
也正是因為這個原因宾茂，聚類集合中也包含少量的non-core sample，它們是聚類中core sample的鄰居拴还，
但自己不是core sample跨晴。這些non-core sample構(gòu)成了邊界。
在確定了如何通過單一core sample找到了一個聚類后片林，下面描述DBSCAN算法的整個流程端盆。
首先，掃描數(shù)據(jù)集找到任意一個core sample费封，以此core sample為起點焕妙，按照上一段描述的方法進行擴充，確定一個聚類孝偎。然后访敌，再次掃描數(shù)據(jù)集，找到任意一個不屬于以確定類別的core sample衣盾，重復擴充過程寺旺，再次確定一個聚類。
迭代這個過程势决，直至數(shù)據(jù)集中不再包含有core sample阻塑。
這也是為什么DBSCAN不用認為指定聚類數(shù)目的原因。
DBSCAN算法包含一定的非確定性果复。數(shù)據(jù)中的core sample總是會被分配到相同的聚類中的陈莽，哪怕在統(tǒng)一數(shù)據(jù)集上多次運行DBSCAN。其不確定性主要體現(xiàn)在non-core sample的分配上。
一個non-core sample可能同時是兩個core sample的鄰居走搁，而這兩個core sample隸屬于不同的聚類独柑。
DBSCAN中，這個non-core sample會被分配給首先生成的那個聚類私植，而哪個聚類先生成是隨機的忌栅。
sklearn中DBSCAN的實現(xiàn)中，鄰居的確定使用的ball tree和kd-tree思想曲稼，這就避免了計算距離矩陣索绪。
