1、相關概念
-
無監督學習：
無監督學習是機器學習的一種方法，沒有給定事先标記過的訓練示例，自動對輸入的資料進行分類或分群。無監督學習的主要運用包含：聚類分析、關系規則、次元縮減。它是監督式學習和強化學習等政策之外的一種選擇。 一個常見的無監督學習是資料聚類。在人工神經網絡中，生成對抗網絡、自組織映射和适應性共振理論則是最常用的非監督式學習。
-
聚類：
聚類是一種無監督學習。聚類是把相似的對象通過靜态分類的方法分成不同的組别或者更多的子集，這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐标系中更加短的空間距離等。
#通過簡單的例子來直接檢視K均值聚類的效果
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
#聚類前
X = np.random.rand(100,2)
plt.scatter(X[:,0],X[:,1], marker='o')
#聚類後
kmeans = KMeans(n_clusters=4).fit(X)
label_pred = kmeans.labels_
plt.scatter(X[:,0],X[:,1],c=label_pred)
plt.show()
2、性能度量
在機器學習中我們都需要對任務進行評價以便于進行下一步的優化，聚類的性能度量主要有一下兩種。
- 外部名額：是指把算法得到的劃分結果跟某個外部的“參考模型”（如專家給出的劃分結果）比較
- 内部名額：是指直接考察聚類結果，不利用任何參考模型的名額。
3、距離計算
在機器學習和資料挖掘中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類别。
- 歐式距離（2-norm距離）
- 曼哈頓距離（Manhattan distance, 1-norm距離）
- 切比雪夫距離
- 闵可夫斯基距離
- 餘弦相似性
-
馬氏距離
歐式距離:歐氏距離是最易于了解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。
d ( x , y ) = Σ k = 1 n ( x k − y k ) 2 d(x,y)=\sqrt{\Sigma_{k=1}^n (x_k-y_k)^2} d(x,y)=Σk=1n(xk−yk)2
曼哈頓距離:
曼哈頓距離也稱為街區距離，計算公式如下：
d ( x , y ) = Σ k = 1 n ∣ x k − y k ∣ d(x,y)=\Sigma_{k=1}^n \left|x_k-y_k\right| d(x,y)=Σk=1n∣xk−yk∣
切比雪夫距離： d ( x , y ) = lim n → ∞ ( Σ k = 1 n ( ∣ x k − y k ∣ ) r ) 1 r = m a x k ( ∣ x k − y k ∣ ) d(x,y) = \lim_{n\rightarrow \infty} (\Sigma_{k=1}^n (\left|x_k-y_k\right|)^r)^\dfrac{1}{r} = max_k (\left|x_k-y_k\right|) d(x,y)=n→∞lim(Σk=1n(∣xk−yk∣)r)r1=maxk(∣xk−yk∣)
闵可夫斯基距離:
d ( x , y ) = ( Σ k = 1 n ( ∣ x k − y k ∣ ) r ) 1 r d(x,y)=(\Sigma_{k=1}^n (\left|x_k-y_k\right|)^r)^\dfrac{1}{r} d(x,y)=(Σk=1n(∣xk−yk∣)r)r1
式中，r是一個可變參數，根據參數r取值的不同，闵可夫斯基距離可以表示一類距離
r = 1時，為曼哈頓距離
r = 2時，為歐式距離
r →∞時，為切比雪夫距離
闵可夫斯基距離包括歐式距離、曼哈頓距離、切比雪夫距離都假設資料各維屬性的量綱和分布（期望、方差）相同，是以适用于度量獨立同分布的資料對象。
餘弦距離:
餘弦相似度公式定義如下：
c o s ( x , y ) = x y ∣ x ∣ ∣ y ∣ = Σ k = 1 n x k y k Σ k = 1 n x k 2 Σ k = 1 n y k 2 cos(x,y)=\dfrac{xy}{\left|x\right|\left|y\right|} = \dfrac{\Sigma_{k=1}^n x_k y_k}{\sqrt{\Sigma_{k=1}^n x_k^2} \sqrt{\Sigma_{k=1}^n y_k^2}} cos(x,y)=∣x∣∣y∣xy=Σk=1nxk2
Σk=1nyk2
Σk=1nxkyk
餘弦相似度實際上是向量xx和yy夾角的餘弦度量，可用來衡量兩個向量方向的差異。如果餘弦相似度為11，則xx和yy之間夾角為0°0°，兩向量除模外可認為是相同的；如果預先相似度為00，則xx和yy之間夾角為90°90°，則認為兩向量完全不同。在計算餘弦距離時，将向量均規範化成具有長度11，是以不用考慮兩個資料對象的量值。
餘弦相似度常用來度量文本之間的相似性。文檔可以用向量表示，向量的每個屬性代表一個特定的詞或術語在文檔中出現的頻率，盡管文檔具有大量的屬性，但每個文檔向量都是稀疏的，具有相對較少的非零屬性值。
馬氏距離:
m a h a l a n o b i s ( x , y ) = ( x − y ) Σ − 1 ( x − y ) T mahalanobis(x,y)=(x-y)\Sigma^{-1}(x-y)^T mahalanobis(x,y)=(x−y)Σ−1(x−y)T
式中，Σ−1Σ−1是資料協方差矩陣的逆。
前面的距離度量方法大都假設樣本獨立同分布、資料屬性之間不相關。馬氏距離考慮了資料屬性之間的相關性，排除了屬性間相關性的幹擾，而且與量綱無關。若協方差矩陣是對角陣，則馬氏距離變成了标準歐式距離；若協方差矩陣是機關矩陣，各個樣本向量之間獨立同分布，則變成歐式距離。
4、K均值聚類
k均值聚類算法（k-means clustering algorithm）是一種疊代求解的聚類分析算法，其步驟是
建立 k 個點作為起始質心（通常是随機選擇）
當任意一個點的簇配置設定結果發生改變時（不改變時算法結束）
對資料集中的每個資料點
對每個質心
計算質心與資料點之間的距離
将資料點配置設定到距其最近的簇
對每一個簇, 計算簇中所有點的均值并将均值作為質心
聚類中心以及配置設定給它們的對象就代表一個聚類。
代碼實作
def distEclud(vecA, vecB):
'''
歐氏距離計算函數
:param vecA:
:param vecB:
:return: float
'''
dist = 0.0
# ========= show me your code ==================
dist = sqrt(sum(power(vecA-vecB,2)))
# here
# ========= show me your code ==================
return dist
def randCent(dataMat, k):
'''
為給定資料集建構一個包含K個随機質心的集合,
随機質心必須要在整個資料集的邊界之内,這可以通過找到資料集每一維的最小和最大值來完成
然後生成0到1.0之間的随機數并通過取值範圍和最小值,以便確定随機點在資料的邊界之内
:param np.dataMat:
:param k:
:return: np.dataMat
'''
# 擷取樣本數與特征值
m, n = np.shape(dataMat)
# 初始化質心,建立(k,n)個以零填充的矩陣
centroids = np.mat(np.zeros((k, n)))
print(centroids)
# ========= show me your code ==================
# 循環周遊特征值
# here
for j in range(n):#create random cluster centers, within bounds of each dimension
minJ = min(dataMat[:,j])
rangeJ = float(max(dataMat[:,j]) - minJ)
centroids[:,j] = np.mat(minJ + rangeJ * random.rand(k,1))
# ========= show me your code ==================
# 傳回質心
return centroids.A
def kMeans(dataMat, k, distMeas=distEclud):
'''
建立K個質心,然後将每個店配置設定到最近的質心,再重新計算質心。
這個過程重複數次,直到資料點的簇配置設定結果不再改變為止
:param dataMat: 資料集
:param k: 簇的數目
:param distMeans: 計算距離
:return:
'''
# 擷取樣本數和特征數
m, n = np.shape(dataMat)
# 初始化一個矩陣來存儲每個點的簇配置設定結果
# clusterAssment包含兩個列:一列記錄簇索引值,第二列存儲誤差(誤差是指目前點到簇質心的距離,後面會使用該誤差來評價聚類的效果)
clusterAssment = np.mat(np.zeros((m, 2)))
# 建立質心,随機K個質心
centroids = randCent(dataMat, k)
# 初始化标志變量,用于判斷疊代是否繼續,如果True,則繼續疊代
clusterChanged = True
while clusterChanged:
clusterChanged = False
# 周遊所有資料找到距離每個點最近的質心,
# 可以通過對每個點周遊所有質心并計算點到每個質心的距離來完成
for i in range(m):
minDist = float("inf")
minIndex = -1
for j in range(k):
# 計算資料點到質心的距離
# 計算距離是使用distMeas參數給出的距離公式,預設距離函數是distEclud
distJI = distMeas(centroids[j, :], dataMat[i, :])
# 如果距離比minDist(最小距離)還小,更新minDist(最小距離)和最小質心的index(索引)
if distJI < minDist:
minDist = distJI
minIndex = j
# 如果任一點的簇配置設定結果發生改變,則更新clusterChanged标志
# ========= show me your code ==================
# here
if clusterAssment[i, 0] != minIndex:
clusterChanged = True
# ========= show me your code ==================
# 更新簇配置設定結果為最小質心的index(索引),minDist(最小距離)的平方
clusterAssment[i, :] = minIndex, minDist ** 2
# print(centroids)
# 周遊所有質心并更新它們的取值
# ========= show me your code ==================
for cent in range(k):#recalculate centroids
ptsInClust = dataMat[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
# here
# ========= show me your code ==================
# 傳回所有的類質心與點配置設定結果
return centroids, clusterAssment
運作結果
# 運作Kmeans，假設有兩聚類中心
center,label_pred = kMeans(X, k=2)
# 将标簽轉化成易繪圖的形式
label = label_pred[:, 0].A.reshape(-1)
# 将結果可視化
plt.scatter(X[:, 0], X[:, 1], c=label)
plt.scatter(center[0, 0], center[0, 1], marker="*", s = 100)
plt.scatter(center[1, 0], center[1, 1], marker="*", s = 100)
plt.show()