系列文章: 吳恩達《Machine Learning》精煉筆記 1:監督學習與非監督學習 吳恩達《Machine Learning》精煉筆記 2:梯度下降與正規方程 吳恩達《Machine Learning》精煉筆記 3:回歸問題和正則化 吳恩達《Machine Learning》精煉筆記 4:神經網絡基礎 吳恩達《Machine Learning》精煉筆記 5:神經網絡 吳恩達《Machine Learning》精煉筆記 6:關于機器學習的建議 吳恩達《Machine Learning》精煉筆記 7:支援向量機 SVM 本周的主要知識點是無監督學習中的兩個重點:聚類和降維。本文中首先介紹的是聚類中的K均值算法,包含:
- 算法思想
- 圖解K-Means
- sklearn實作
- Python實作
無監督學習unsupervised learning
無監督學習簡介
聚類和降維是無監督學習方法,在無監督學習中資料是沒有标簽的。
比如下面的資料中,橫縱軸都是xx,沒有标簽(輸出yy)。在非監督學習中,我們需要将一系列無标簽的訓練資料,輸入到一個算法中,快速這個資料的中找到其内在資料結構。
無監督學習應用
- 市場分割
- 社交網絡分析
- 組織計算機叢集
- 了解星系的形成
聚類
聚類clustering
聚類試圖将資料集中的樣本劃分成若幹個通常是不相交的子集,稱之為“簇cluster”。聚類可以作為一個單獨過程,用于尋找資料内部的分布結構,也能夠作為其他學習任務的前驅過程。聚類算法涉及到的兩個問題:性能度量和距離計算
性能度量
聚類性能度量也稱之為“有效性名額”。希望“物以類聚”。聚類的結果是“簇内相似度高”和“簇間相似度低”。
常用的外部名額是:
- Jaccard 系數
- FM 系數
- Rand 系數
上述3個系數的值都在[0,1]之間,越小越好
常用的内部名額是:
- DB指數
- Dunn指數
DBI的值越小越好,Dunn的值越大越好。
距離計算
xi,xj 的Lp的距離定義為:
規定:p≥1,常用的距離計算公式有
- 當p=2時,即為歐式距離,比較常用,即:
- 當p=1時,即曼哈頓距離,即:
- 當p趨于無窮,為切比雪夫距離,它是各個坐标距離的最大值:
餘弦相似度
餘弦相似度的公式為:
Pearson皮爾遜相關系數
皮爾遜相關系數的公式如下:
K-均值算法
K-均值,也叫做k-means算法,最常見的聚類算法,算法接受一個未标記的資料集,然後将資料聚類成不同的組。假設将資料分成n個組,方法為:
- 随機選擇K個點,稱之為“聚類中心”
- 對于資料集中的每個資料,按照距離K個中心點的距離,将其和距離最近的中心點關聯起來,與同個中心點關聯的所有點聚成一類。
- 計算上面步驟中形成的類的平均值,将該組所關聯的中心點移動到平均值的位置
- 重複上面兩個步驟,直到中心點不再變化。
圖解K-means
- 給定需要劃分的資料,随機确定兩個聚類中心點
- 計算其他資料和這兩個中心點的距離,劃入距離小的類中,假設兩個類是C1,C2
- 确定上述步驟中兩個類是C1,C2的均值,這個均值就是新的聚類中心
- 重複:計算資料和這兩個中心點的距離,劃入距離小的類中,形成新的類;再确定新的聚類中心
- 直至中心點不再變化,結束
全過程
K-means算法過程
吳恩達視訊的中的僞代碼為
repeat {
for i= to m
# 計算每個樣例屬于的類
c(i) := index (from 1 to K) of cluster centroid closest to x(i)
for k = 1 to K
# 聚類中心的移動,重新計算該類的質心
u(k) := average (mean) of points assigned to cluster K
}
西瓜書中的僞代碼
優化目标Optimization Objective
K-均值最小化問題,是要最小化所有的資料點與其所關聯的聚類中心點之間的距離之和,是以 K-均值的代價函數(畸變函數Distortion function) :
其中μ代表與xi最近的聚類中心點
優化目标就是找出使得代價函數最小的c和μ,即:
随機初始化
在運作K-均值算法的之前,首先要随機初始化所有的聚類中心點:
- 選擇K<m,即聚類中心的個數小于訓練樣本的執行個體數量
- 随機訓練K個訓練執行個體,然後令K個聚類中心分别和這K個訓練執行個體相等
關于K-means的局部最小值問題:
Scikit learn 實作K-means
make_blobs資料集
make_blobs聚類資料生成器make_blobs方法常被用來生成聚類算法的測試資料。它會根據使用者指定的特征數量、中心點數量、範圍等來生成幾類資料。
主要參數
sklearn.datasets.make_blobs(n_samples=100, n_features=2,centers=3, cluster_std=1.0, center_box=(-10.0, 10.0), shuffle=True, random_state=None)[source]
- n_samples是待生成的樣本的總數
- n_features是每個樣本的特征數
- centers表示類别數
- cluster_std表示每個類别的方差
import numpy as np
import matplotlib.pyplot as plt
# 導入 KMeans 子產品和資料集
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
# 定義畫布
plt.figure(figsize=(12,12))
# 定義樣本量和随機種子
n_samples = 1500
random_state = 170
# X是測試資料集,y是目标分類标簽0,1,2
X, y = make_blobs(n_samples=n_samples, random_state=random_state)
X
array([[-5.19811282e+00, 6.41869316e-01],
[-5.75229538e+00, 4.18627111e-01],
[-1.08448984e+01, -7.55352273e+00],
...,
[ 1.36105255e+00, -9.07491863e-01],
[-3.54141108e-01, 7.12241630e-01],
[ 1.88577252e+00, 1.41185693e-03]])
y
array([1, 1, 0, ..., 2, 2, 2])
# 預測值的簇類
y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
y_pred
array([0, 0, 1, ..., 0, 0, 0], dtype=int32)
X[:,0] # 所有行的第1列資料
array([ -5.19811282, -5.75229538, -10.84489837, ..., 1.36105255,
-0.35414111, 1.88577252])
# 子圖1的繪制
plt.subplot(221)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.title("incorrrect Number of Blods")
transformation = [[0.60834549, -0.63667341],[-0.40887718, 0.85253229]]
X_aniso = np.dot(X, transformation)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
# 子圖2的繪制
plt.subplot(222)
plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
plt.title("Anisotropicly Distributed Blobs")
X_varied, y_varied = make_blobs(n_samples=n_samples,
cluster_std=[1.0,2.5,0.5],random_state=random_state)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
plt.subplot(223)
plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
plt.title("Unequal Variance")
X_filtered = np.vstack((X[y == 0][:500],
X[y == 1][:100],
X[y == 2][:10]))
y_pred = KMeans(n_clusters=3,random_state=random_state).fit_predict(X_filtered)
plt.subplot(224)
plt.scatter(X_filtered[:, 0],
X_filtered[:, 1],
c=y_pred)
plt.title("Unevenly Sized Blobs")
plt.show()
基于 python實作K-means算法
這是在網上找到的一個基于Python找到的`K-means實驗算法,學習使用