聚類定義

定義

聚類就是對大量未知標注 的數據集，按數據 的內在相似性將數據集劃分為多個類別，使 類別內的數據相似度較大而類別間的數據相 似度較小。是無監督的分類方式。

聚類思想

給定一個有N個對象的數據集，構造數據的k 個簇，k≤n。滿足下列條件：

• 每一個簇至少包含一個對象
• 每一個對象屬于且僅屬于一個簇
• 將滿足上述條件的k個簇稱作一個合理劃分

基本思想：對于給定的類別數目k，首先給出初始劃分，通過迭代改變樣本和簇的隸屬關系，使得每一次改進之后的劃分方案都較前一次好。

聚類與降維

有時候，聚類可以起到降維的效果。在有些領域，降維和聚類是同義詞。

例如，有以下數據樣本，m個樣本，n個特征

假定通過聚類，將上面m個樣本聚類成3類，然后經過one-hot得：

這就相當于對原始數據進行了降維。

相似度度量方式

顯然，我們對無標識 的樣本進行聚類時，必須有一種衡量樣本之間相似度的方法或者是標準，通過這種標準來判斷不同樣本之間距離的遠近，進而來進行聚類。那么有哪些方法可以判斷樣本之間相似程度或者是距離遠近呢？

歐式距離

p=1，dist(X,Y)=|x1-x2|+|y1-y2|，這時稱為曼哈頓距離。
p=2，dist(X,Y)=||X-Y||的二范式。
p=無窮大呢？這里假定樣本特征有三維x,y,z那么p次方的歐式距離為：

然后在假定

那么可推得：

在實際場景中，我們常常選用p=2來定義歐式距離。
sklearn.metrics.silhouette_score

杰卡德相似系數(Jaccard)

A,B可以看著兩個集合。
杰卡德相似系數常常用于度量推薦系統里面度量商品或者用戶的相似度。
skearn中Jaccard系數

余弦相似度(cosine similarity)

顯然對于向量a,b，夾角越小距離越近。夾角越大距離越遠。
sklearn.metrics.pairwise.cosine_similarity

Pearson相似系數

顯然當時有：

這就和余弦相似度等價了。

就是將兩個向量當做隨機變量來進行比較相似度。
scipy.stat.pearson

相對熵(K-L距離)

Hellinger距離

k-Means算法

k-Means算法，也被稱為k-平均或k-均值，是一種廣泛使用的聚類算法， 或者成為其他聚類算法的基礎。

k-Means算法步驟

假定輸入樣本為S=x1,x2,…,xm，則算法步驟為：

1. 選擇初始的k個類別中心μ1μ2…μk
2. 對于每個樣本xi，將其標記為距離類別中心最近的類別，即：
   
3. 將每個類別中心更新為隸屬該類別的所有樣本的均值
   
4. 重復最后兩步，直到類別中心的變化小于某閾值。

中止條件：迭代次數/簇中心變化率/最小平方誤差MSE(Minimum Squared Error)。

k-Means聚類過程

k-Means初值敏感性

k-Means將簇中所有點的均值作為新質心， 若簇中含有異常點，將導致均值偏離嚴重。 以一維數據為例：

1. 數組1、2、3、4、100的均值為22，顯然距離 “大多數”數據1、2、3、4比較遠
2. 改成求數組的中位數3，在該實例中更為穩妥。這種聚類方式即k-Mediods聚類(K中值距離)

初值的選擇對聚類結果有著很大的影響，那么如何避免呢？

解決方案一：選擇較好的聚類初值 ：K-Means++算法

不同與K-Means算法隨機選擇聚類中心，K-Means++算法按距離加權來初始化聚類中心。
假定我們選擇k>=2

1. 首先隨機選擇第一個聚類中心μ1。
2. 計算其他樣本到第一個聚類中心μ1的距離，分別為[d1,d2,d3,..]，d=d1+d2+d3+..。
3. 設置每一個樣本被選為第二個聚類中心μ2的概率分別為[d1/d,d2/d,/d3/d,….]。
4. 按照概率隨機選擇其中一個樣本為第二個聚類中心μ2。
5. 計算其他樣本分別到第一，第二聚類中心的距離，以其最短距離為準。重復以上步驟3，步驟4，來計算剩余的聚類中心。

這樣初始化的各個聚類中心不一定是距離最遠（因為是每次是以概率的來選聚類中心），但肯定不近。

解決方案二：多做幾回

多做幾回k-Means算法，每次隨機的選用不同的聚類中心來進行迭代，然后選擇聚類效果最好的那次。

k-Means++算法測試
下圖為做六次k-Means++，并且每次k值都為7。有六張聚類圖可知，每次聚類效果都不一樣。因為每次聚類中心的選取不一樣。多做幾次，選擇上述目標函數值最小的，或者根據實際業務選擇效果最好的效果圖。

k-Means的公式化解釋

記K個簇中心為 μ1μ2…μk，每個簇的樣本數目為N1，N2，N3，….。

使用平方誤差作為目標函數：

對關于μ1μ2…μk的函數求偏導，其駐點為：

用極大似然估計解釋目標函數：

這里假定聚類后有三個簇的樣本X1,X2,X3，假設，即均值各不同，但是有著相同的方差。

那么第一個簇的樣本概率密度函數為：

第二個簇的樣本概率密度函數為：

第三個簇的樣本概率密度函數為：

那么似然函數為：

對數似然函數為：

極大似然函數即是求：

和上面的目標函數一致。其實就是MSE。MSE均值最優。

其中μ是估計參數。
以上說明了k-Means算法對樣本的分布有要求的，我們認為樣本是由k個高斯混合（GMM）得到的，并且認為所有簇的方差是相同的。

Mini-batch k-Means算法

之前求得對關于μ1μ2…μk的函數求偏導，其駐點為：

那么需要把所有屬于第j個類的Nj個樣本求個均值嗎？其實我們可以利用SGD思想，每次從第j個類的Nj個樣本中隨機選取一部分mini-batch樣本來求均值來更新μj。

K-Means算法總結

優點：

• 是解決聚類問題的一種經典算法，簡單、快速。
• 對處理大數據集，該算法保持可伸縮性和高效率。
• 當簇近似為高斯分布時，它的效果較好。

缺點：

• 在簇的平均值可被定義的情況下才能使用，可能不適用 于某些應用
• 必須事先給出k(要生成的簇的數目)，而且對初值敏感， 對于不同的初始值，可能會導致不同結果。
• 不適合于發現非凸形狀的簇或者大小差別很大的簇。
• 對躁聲和孤立點數據敏感 。

相關代碼

cls = KMeans(n_clusters=4, init='k-means++',n_init=10)##　采樣k-means++進行聚類，做10回k-Means算法，每次隨機的選用不同的聚類中心來進行迭代，然后選擇聚類效果最好的那次。
y_hat = cls.fit_predict(data)

聚類的衡量指標

均一性

• Homogeneity

• 一個簇只包含一個類別的樣本，則滿足均一性。

H(C)：在已知樣本原始的類別標記，計算其熵值。
H(C|K)：在給定聚類結果為第K個簇時，計算其第k個簇內在真實類別標記中的熵值。

完整性

• Completeness

• 同類別樣本被歸類到相同簇中，則滿足完整性。

H(K)：第k個簇的熵值。
H(K|C)：給定某個真實的類別C，計算類別C的樣本聚類為不同的簇的熵值。

均一性和完整性類似于precision，recall，兩者一高一低或者一低一高，很難同時很好。

V-measure （均一性和完整性的加權平均）

ARI

數據集S共有N個元素， 兩次 聚類結果分別是X，Y
這里我們假定Y為樣本真實的分類標簽，X是聚類結果。

X和Y的元素個數為：

記：

則有：

ARI越小，兩次聚類結果越相似，反正越不相似。

相關代碼實現：

y = [0, 0, 0, 1, 1, 1]
y_hat = [0, 0, 1, 1, 2, 2]
h = metrics.homogeneity_score(y, y_hat)
c = metrics.completeness_score(y, y_hat)
print u'同一性(Homogeneity)：', h
print u'完整性(Completeness)：', c
v2 = 2 * c * h / (c + h)
v = metrics.v_measure_score(y, y_hat)
print u'V-Measure：', v2, vy = [0, 0, 1, 1]
y_hat = [0, 1, 0, 1]
ari = metrics.adjusted_rand_score(y, y_hat)
print ari

AMI

使用與ARI相同的記號，根據信息熵，得：
互信息/正則化互信息：

X服從超幾何分布，求互信息期望：

輪廓系數(Silhouette)

上面都是在已知樣本類別標簽的情況下，來對聚類結果進行衡量。那么如果不知道樣本的類別標簽如何衡量聚類效果呢？

計算樣本i到同簇其他樣本的平均距離ai。ai越小， 說明樣本i越應該被聚類到該簇。將 ai 稱為樣本i的簇內不相似度。

簇C中所有樣本的 ai 均值稱為簇C的簇不相似度。

計算樣本i到其他某簇 Cj 的所有樣本的平均距離 bij， 稱為樣本i與簇Cj的不相似度。定義為樣本i的簇間 不相似度：

bi越大，說明樣本i越不屬于其他簇。

根據樣本i的簇內不相似度ai 和簇間不相似度bi，定義樣本i的輪廓系數：

si接近1，則說明樣本i聚類合理；si 接近-1，則說明 樣本i更應該分類到另外的簇；若si近似為0，則說 明樣本i在兩個簇的邊界上。

所有樣本的si的均值稱為聚類結果的輪廓系數，是該聚類是否合理、有效的度量。

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> dataset = datasets.load_iris()
>>> X = dataset.data
>>> y = dataset.target
>>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
...                                                      
0.55...

sklearn中更詳細的說明請看sklearn.metrics.silhouette_score

層次聚類方法

層次聚類方法對給定的數據集進行層次的分解，直到某種條件滿足為止。具體又可分為：

凝聚 的層次聚類：AGNES算法

一種自底向上的策略，首先將每個對象作為一個簇，然 后合并這些原子簇為越來越大的簇，直到某個終結條件 被滿足。AGNES (AGglomerative NESting)算法最初將每個對 象作為一個簇，然后這些簇根據某些準則被一步步 地合并。兩個簇間的距離由這兩個不同簇中距離最 近的數據點對的相似度來確定；聚類的合并過程反 復進行直到所有的對象最終滿足簇數目。

分裂 的層次聚類：DIANA算法

采用自頂向下的策略，它首先將所有對象臵于一個簇中， 然后逐漸細分為越來越小的簇，直到達到了某個終結條件。DIANA (DIvisive ANAlysis)算法是上述過程的反過程，屬于分裂的層次聚類，首先將所有的對象初始化到一個簇中，然后根據一些原則(比如最大的歐式距離)，將該簇分類。直到到達用戶指定的簇數目或者兩個簇之間的距離超過了某個閾值。

上面兩種方法，凝聚 的層次聚類使用的較多。

AGNES中簇間距離的不同定義

最小距離 ：

• 兩個集合中最近的兩個樣本的距離。
• 容易形成鏈狀結構。

最大距離 ：

• 兩個集合中最遠的兩個樣本的距離complete。
• 若存在異常值則不穩定。

平均距離 ：

• 兩個集合中樣本間兩兩距離的平均值average。
• 兩個集合中樣本間兩兩距離的平方和ward。

sklearn中凝聚 的層次聚類

from sklearn.cluster import AgglomerativeClustering
ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',connectivity=connectivity, linkage=linkage)
ac.fit(data)
y = ac.labels_

密度聚類方法

密度聚類思想

密度聚類方法的指導思想是，只要樣本點的密度 大于某閾值，則將該樣本添加到最近的簇中。

這類算法能克服基于距離的算法只能發現“類圓形”(凸)的聚類的缺點，可發現任意形狀的聚類， 且對噪聲數據不敏感。但計算密度單元的計算復雜度大，需要建立空間索引來降低計算量。

• DBSCAN
• 密度最大值算法

DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

一個比較有代表性的基于密度的聚類算法。 與劃分和層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠 高密度的區域劃分為簇，并可在有“噪聲” 的數據中發現任意形狀的聚類。

對象的ε-鄰域：給定對象在半徑ε內的區域。
核心對象：對于給定的數目m，如果一個對象的ε鄰域至少包含m個對象，則稱該對象為核心對象。
直接密度可達：給定一個對象集合D，如果p是在q 的ε-鄰域內，而q是一個核心對象，我們說對象p從對象q出發是直接密度可達的。

如圖ε=1cm，m=5，q是一個核 心對象，從對象q出發到對象p是 直接密度可達的。

密度可達：如果存在一個對象鏈 p1p2…pn，，對 ，(1≤i ≤n)，是從pi關于ε和m直接密度可達 的，則對象p是從對象q關于 ε 和m密度可達的。

密度相連：如果對象集合D中存在一個對象o，使得對象p和q 是從o關于ε和m 密度可達 的（即o點可密度可達p點，o點也可密度可達q點），那么對象p和q是關于ε和m密度 相連的。

簇：一個基于密度的簇是最大的密度相連對象的集合。
噪聲：不包含在任何簇中的對象稱為噪聲。 （不是核心對象，且不能被其他對象密度可達）

DBSCAN算法流程：

1. 如果一個點p的ε-鄰域包含多于m個對象，則創建一個p作為核心對象的新簇；
2. 尋找并合并核心對象直接密度可達的對象；（判斷與p直接密度可達的對象是否是核心對象，如果是，那么合并該核心對象，并繼續尋找與該核心對象直接密度可達的對象，不斷的重復以上操作。）
3. 沒有新點可以更新簇時，算法結束。

有上述算法可知：

• 每個簇至少包含一個核心對象；
• 非核心對象可以是簇的一部分，構成了簇的邊緣(edge)；
• 包含過少對象的簇被認為是噪聲。
• 不同于K-Means，DBSCAN不需要事先確定簇的個數。

DBSCAN 代碼舉例

import numpy as np
import matplotlib.pyplot as plt
import sklearn.datasets as ds
import matplotlib.colors
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScalerdef expand(a, b):d = (b - a) * 0.1return a-d, b+dif __name__ == "__main__":N = 1000centers = [[1, 2], [-1, -1], [1, -1], [-1, 1]]data, y = ds.make_blobs(N, n_features=2, centers=centers, cluster_std=[0.5, 0.25, 0.7, 0.5], random_state=0)data = StandardScaler().fit_transform(data)# 數據1的參數：(epsilon, min_sample)params = ((0.2, 5), (0.2, 10), (0.2, 15), (0.3, 5), (0.3, 10), (0.3, 15))# 數據2# t = np.arange(0, 2*np.pi, 0.1)# data1 = np.vstack((np.cos(t), np.sin(t))).T# data2 = np.vstack((2*np.cos(t), 2*np.sin(t))).T# data3 = np.vstack((3*np.cos(t), 3*np.sin(t))).T# data = np.vstack((data1, data2, data3))# # # 數據2的參數：(epsilon, min_sample)# params = ((0.5, 3), (0.5, 5), (0.5, 10), (1., 3), (1., 10), (1., 20))matplotlib.rcParams['font.sans-serif'] = [u'Droid Sans Fallback']matplotlib.rcParams['axes.unicode_minus'] = Falseplt.figure(figsize=(12, 8), facecolor='w')plt.suptitle(u'DBSCAN聚類', fontsize=20)for i in range(6):eps, min_samples = params[i]model = DBSCAN(eps=eps, min_samples=min_samples)model.fit(data)y_hat = model.labels_core_indices = np.zeros_like(y_hat, dtype=bool)core_indices[model.core_sample_indices_] = Truey_unique = np.unique(y_hat)n_clusters = y_unique.size - (1 if -1 in y_hat else 0)## y_hat=-1為聚類后的噪聲類print y_unique, '聚類簇的個數為：', n_clustersplt.subplot(2, 3, i+1)clrs = plt.cm.Spectral(np.linspace(0, 0.8, y_unique.size))##指定聚類后每類的顏色print clrsfor k, clr in zip(y_unique, clrs):cur = (y_hat == k)if k == -1:plt.scatter(data[cur, 0], data[cur, 1], s=20, c='k')continueplt.scatter(data[cur, 0], data[cur, 1], s=30, c=clr, edgecolors='k')#plt.scatter(data[cur & core_indices][:, 0], data[cur & core_indices][:, 1], s=60, c=clr, marker='o', edgecolors='k')x1_min, x2_min = np.min(data, axis=0) ## 兩列的最小值x1_max, x2_max = np.max(data, axis=0)## 兩列的最大值x1_min, x1_max = expand(x1_min, x1_max)x2_min, x2_max = expand(x2_min, x2_max)plt.xlim((x1_min, x1_max))plt.ylim((x2_min, x2_max))plt.grid(True)plt.title(ur'$\epsilon$ = %.1f  m = %d，聚類數目：%d' % (eps, min_samples, n_clusters), fontsize=16)plt.tight_layout()plt.subplots_adjust(top=0.9)plt.show()
1
密度最大值聚類
密度最大值聚類是一種簡潔優美的聚類算法, 可以 識別各種形狀的類簇, 并且參數很容易確定。 
局部密度ρi： 

dc是一個截斷距離, ρi即到對象i的距離小于dc的對象的個 數。由于該算法只對ρi的相對值敏感, 所以對dc的選擇是 穩健的，一種推薦做法是選擇dc，使得平均每個點的鄰 居數為所有點的1%-2%。
局部密度的其他定義：
截斷值： 

高斯核相似度：距離越近，權值越大 

K近鄰均值： 

高局部密度點距離
定義：假定求得第i個樣本的局部密度為，第1個樣本，第二個樣本直到第n個樣本的局部密度分別為：，找出其局部密度大于的所有樣本 j，然后再求出第i個樣本到第j個樣本的距離，選出最小的那個作為樣本i的高局部密度點距離。
即是：在密度高于對象i的所有對象中，到對象i最近的距離，即高局部密度點距離。 
對于密度最大的對象，設置δi=max(dij)(即：該問題中的無窮大)。 

只有那些密度是局部或者全局最大的點才會有遠 大于正常值的高局部密度點距離。 
簇中心的識別
由上面可以分析得：
比較大，也比較大，那么第i的樣本對象可能是一個簇的中心。
比較小，比較大，那么第i的樣本對象可能是噪聲。
比較大，比較小，那么第i的樣本是一個簇里面很普通的樣本。
那些有著比較大的局部密度ρi和很大的高密 距離δi的點被認為是簇的中心；  

高密距離δi較大但局部密度ρi較小的點是異 常點；  

確定簇中心之后，其他點按照距離已知簇的中心最近進行分類 。
譜和譜聚類
定義
方陣作為線性算子，它的所有特征值 的全體，統稱方陣的譜。
方陣 的譜半徑為最大的特征值。
矩陣 A的譜半徑：(ATA)的最大特征值。
譜聚類是一種基于圖論的聚類方法，通過對樣本數據的拉普拉斯矩陣的特征向量 進行聚類，從而達到對樣本數據聚類的目的。
譜分析的整體過程
給定一組數據x1,x2,…xn，記任意兩個點之間 的相似度 (―距離”的減函數，如高斯相似度度量方式 )為sij= < xi,xj >，形成相似度圖(similarity graph)：G=(V,E) 。這里把sii（即對角線上）全部設為0。這樣就得出了鄰接矩陣。
無向圖G=(V,E)
鄰接矩陣 
 

高斯相似度： 

 

其中是超參數，事先給定的。
頂點的度di–>度矩陣D (對角陣)。（鄰接矩陣中第i行數據求和即為第i個樣本的度di，形成的矩陣D對角線上每個元素即為d1,d2,…,dn，其余位置全為0） 

未正則的拉普拉斯矩陣：
L = D – W 
L是對稱半正定矩陣，最小特征值是0，相應的特征向量是全1向量。
算法步驟：
輸入：n個點{pi}，簇的數目k
計算n×n的相似度矩陣W和度矩陣D；
計算拉普拉斯矩陣L=D-W；
計算L的前k個特征向量u1,u2,…,uk，對應的特征值分別為 ，如果定義的L=D-W，特征值是從小到大排序的；
將k個列向量u1,u2,…,uk組成矩陣U，U∈Rn×k；
對于i=1,2,…,n,令yi∈Rk是U的第i行的向量；
使用k-means算法將點(yi)i=1,2,…,n聚類成簇 C1,C2,…Ck； 
輸出簇A1,A2,…Ak，其中，Ai={j|yj∈Ci} 
個人感覺就是對拉普拉斯矩陣L做主成分分析，然后做K-Means。
正則拉普拉斯矩陣
對稱拉普拉斯矩陣： 

算法步驟：
輸入：n個點{pi}，簇的數目k
計算n×n的相似度矩陣W和度矩陣D；
計算正則拉普拉斯矩陣 ；
計算Lsym的前k個特征向量u1,u2,…,uk；
將k個列向量u1,u2,…,uk組成矩陣U，U∈Rn×k，對應的特征值分別為 ，特征值是從小到大排序的；
對于i=1,2,…,n,令yi∈Rk是U的第i行的向量；
對于i=1,2,…,n,將yi∈Rk依次單位化，使得|yi|=1；（單位化）
使用k-means算法將點(yi)i=1,2,…,n聚類成簇C1,C2,…Ck；
輸出簇A1,A2,…Ak，其中，Ai={j|yj∈Ci} 。
隨機游走拉普拉斯矩陣：
圖論中的隨機游走是一個隨機過程，它從一 個頂點跳轉到另外一個頂點。譜聚類即找到 圖的一個劃分，使得隨機游走在相同的簇中 停留而幾乎不會游走到其他簇。 
算法步驟：
輸入：n個點{pi}，簇的數目k
計算n×n的相似度矩陣W和度矩陣D；
計算正則拉普拉斯矩陣；
計算Lrw的前k個特征向量u1,u2,…,uk，對應的特征值分別為 ，特征值是從小到大排序的；；
將k個列向量u1,u2,…,uk組成矩陣U，U∈ Rn×k ；
對于i=1,2,…,n,令yi∈Rk是U的第i行的向量；
使用k-means算法將點(yi)i=1,2,…,n聚類成簇 C1,C2,…Ck ； 
輸出簇A1,A2,…Ak，其中，Ai={j|yj∈Ci} 
上面三個拉普拉斯矩陣，在沒有先驗知識情況下，優先選擇隨機游走拉普拉斯矩陣。
譜聚類中的K如何確定？ 將拉普拉斯矩陣的特征值從小到大排序，選擇相鄰特征值差值最大的索引。 

譜聚類代碼舉例
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.colors
from sklearn.cluster import spectral_clustering
from sklearn.metrics import euclidean_distancesdef expand(a, b):d = (b - a) * 0.1return a-d, b+dif __name__ == "__main__":matplotlib.rcParams['font.sans-serif'] = [u'Droid Sans Fallback']matplotlib.rcParams['axes.unicode_minus'] = Falset = np.arange(0, 2*np.pi, 0.1)data1 = np.vstack((np.cos(t), np.sin(t))).T ##在行上做連接堆積，相當與np.concatenate(tup,axis=0)data2 = np.vstack((2*np.cos(t), 2*np.sin(t))).Tdata3 = np.vstack((3*np.cos(t), 3*np.sin(t))).Tdata = np.vstack((data1, data2, data3))n_clusters = 3m = euclidean_distances(data, squared=True) ##計算兩兩樣本之間的歐式距離print "m",m.shapeplt.figure(figsize=(12, 8), facecolor='w')plt.suptitle(u'譜聚類', fontsize=20)clrs = plt.cm.Spectral(np.linspace(0, 0.8, n_clusters))##指定聚類后每類的顏色for i, s in enumerate(np.logspace(-2, 0, 6)):print saf = np.exp(-m ** 2 / (s ** 2)) + 1e-6 ##利用data中兩兩樣本距離，計算兩兩樣本的高斯相似度，其中s為超參數sigmay_hat = spectral_clustering(af, n_clusters=n_clusters, assign_labels='kmeans', random_state=1)#譜聚類以后每個樣本所屬的簇plt.subplot(2, 3, i+1)for k, clr in enumerate(clrs):cur = (y_hat == k)plt.scatter(data[cur, 0], data[cur, 1], s=40, c=clr, edgecolors='k')x1_min, x2_min = np.min(data, axis=0)x1_max, x2_max = np.max(data, axis=0)x1_min, x1_max = expand(x1_min, x1_max)x2_min, x2_max = expand(x2_min, x2_max)plt.xlim((x1_min, x1_max))plt.ylim((x2_min, x2_max))plt.grid(True)plt.title(ur'$\sigma$ = %.2f' % s, fontsize=16)plt.tight_layout()plt.subplots_adjust(top=0.9)plt.show()
標簽傳遞算法
對于部分樣本的標記給定，而大多數樣本的 標記未知的情形，是半監督學習問題。 
標簽傳遞算法(Label Propagation Algorithm,LPA)，將標記樣本的標記通過一定的概率傳遞給未標記樣本，直到最終收斂。
即在一批無標記的樣本中隨機選取一部分樣本進行標記，然后根據樣本之間的相似度，進行概率化的傳遞，給其他無標記的樣本自動打上標記。