Chap.II Machine Learning 機器學習

https://yourfreetemplates.com/free-machine-learning-diagram/

Part 6. Unsupervised 非監督式學習

本篇會著重在先前提過的非監督式學習上。
它是機器學習的一種方法，在沒有標記的訓練集中，讓學習器對輸入的資料進行分類。
非監督學習主要藉由：聚類分析（cluster analysis）、關聯規則（association rule）、維度縮減（dimensionality reduce）達成最終的分群。

而本篇會著重在 Cluster analysis 聚類分析上。

Cluster analysis 聚類分析

把相似的物件通過靜態分類成不同的組別或者更多的 subset，讓同子集中的物件都有相似屬性。
依照分類方式，又分為：
Hard Clustering：數據集中的樣本都被「100%」分到某一類別中。
Soft Clustering：數據集中的樣本以「一定的概率」被分到某一類別中。

6-1. K-means Clustering K-平均聚類

即是一種硬聚類。透過不停迭代求解，直至分類到指定聚類數量，又稱 EM 分析。
Expectation-step: 求得每個聚類的重心（mean）
Maximization-step: 把資料點歸屬給距離最近的聚類重心。

詳細步驟為：

1. 指定 k 值，把資料集隨機拆成 k 個聚類。
2. 以平均方式找出 k 個聚類重心（centroids），把資料點歸屬到距離最近的聚類中。
3. 以新聚類平均找出新重心，重新對資料劃分歸屬
4. 重複 2～3 直到沒有資料點改變聚類歸屬。

下圖為官網提供的阿拉伯數字範例

打個比方：假設有一資料集 (5,20,11,5,3,19,30,3,15)

至此，所有資料點不再更動，即完成。

但 k-means 的缺點如下：

1. 以初始聚類重心確立初始劃分並對其優化。初始聚類重心的選擇對聚類結果有很大影響。
2. k 值選定困難，實例中常難以估計數據集該分成多少聚類最合適。
3. 因需循環迭代，面對大數據時會耗費龐大資源。

A. K-means++

K-means++ 改善了初始重心選取不當的問題。核心思想：初始的聚類重心間距要盡可能遠。
步驟如下：

1. 從輸入的數據集中，隨機選一個點作第一個聚類中心。
2. 計算數據集的每一個點 x 與已選擇的聚類中心的距離 D(x)
3. D(x) 越大的點，被選作下一個新聚類中心的概率越大
4. 重複 2～3，直到 k 個聚類中心被選出來
5. 用這 k 個初始的聚類中心來執行 k-means 算法

以 make_blobs 創建的隨機亂數為例：

from sklearn.datasets import make_blobs

X, y_true = make_blobs(
    n_samples=300, 
    centers=4,
    cluster_std=0.6,
    random_state=0
)

from sklearn.cluster import KMeans
km = KMeans(
    n_clusters=4,
    random_state=0
)
km.fit(X)
y_pred = km.predict(X)

參數：
1. n_clusters: 即 k 值。默認 8。
2. max_iter: 執行一次 k-means 算法所進行的最大迭代數。默認 300。
3. n_init: k-means 算法會隨機運行 n 次，將最好的聚類作初始化的結果。默認 10。
4. verbose: 列出優化過程。默認 0。
5. init: 初始化方法，有 ‘k-means++’（默認）, ‘random’ 或 nd-array。
更多的超參數可參考：https://www.twblogs.net/a/5b8aaade2b71775d1ce86b48

y_true[:20], y_pred[:20]

>>  (array([1, 3, 0, 3, 1, 1, 2, 0, 3, 3, 2, 3, 0, 3, 1, 0, 0, 1, 2, 2]),
     array([0, 2, 1, 2, 0, 0, 3, 1, 2, 2, 3, 2, 1, 2, 0, 1, 1, 0, 3, 3]))

此時發現很多資料「看似」被預測錯誤，為什麼？

答：因為此為「非監督式學習」，沒有 label，自然就不會依照我們所想的方式分類。

若我們把不同類別的 index 列舉出來比較，會發現其實它們被分配到同個群：

import pandas as pd
true = pd.Series(y_true)
pred = pd.Series(y_pred)

print(true[true==1].index)
print(pred[pred==0].index)

# 在圖上標示重心
plt.scatter(X[:, 0], X[:, 1], c=y_pred, s=50, cmap='viridis')

centers = km.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.5)

B. 決定聚類數目

解決了初始聚類重心的難題後，接著我們來解決 k 值選定。

使用 make_blobs 產生的資料作以下兩種範例：

# 圖片美化用
import seaborn as sns; sns.set()

from sklearn.datasets import make_blobs
X, y_true = make_blobs(
    n_samples=150,
    n_features=2,
    centers=3,
    cluster_std=0.5,
    shuffle=True,
    random_state=0
)
plt.scatter(X[:, 0], X[:, 1], c=y_true, s=50)

B1. Elbow 轉折判斷法：

以迭代集群數去執行 k-means，用誤差平方和（MSE）作為失真（Distortion）準度。

from sklearn.cluster import KMeans
distortions = []

# 用迭代將 1~10 都試一次
for i in range(1, 11):
    km = KMeans(
        n_clusters=i,
        n_init=10,
        max_iter=300,
        random_state=0
    )
    km.fit(X)
    
    # 樣本到它們最近的聚類中心的距離平方和（越小越好）
    distortions.append(km.inertia_)

# 作圖
import matplotlib.pyplot as plt
plt.plot(range(1, 11), distortions, marker='o')
plt.xlabel('Number of clusters')
plt.ylabel('Distortion')
plt.tight_layout()
plt.show()

B2. Silhouette 輪廓係數法：

首先定義 Silhouette 輪廓如下：

使用 sklearn 內建計算輪廓係數：

for i in range(2, 11):
    km = KMeans(
        n_clusters=i,
        n_init=10,
        max_iter=300,
        random_state=0
    )
    km.fit(X)
    y_pred = km.fit_predict(X)
    print(f'{i:<2}, silhouette score: {silhouette_score(X, y_pred):.2f}')

>>  2 , silhouette score: 0.58
    3 , silhouette score: 0.71
    4 , silhouette score: 0.58
    5 , silhouette score: 0.45
    6 , silhouette score: 0.32
    7 , silhouette score: 0.32
    8 , silhouette score: 0.34
    9 , silhouette score: 0.35
    10, silhouette score: 0.35

可以發現當分群 3 時，輪廓係數最高。我們可以把它視覺化：

# k=3
from sklearn.cluster import KMeans
km = KMeans(n_clusters=3, n_init=10, max_iter=300, random_state=0)
y_pred = km.fit_predict(X)

import numpy as np
cluster_labels = np.unique(y_pred)
n_clusters = cluster_labels.shape[0]

from sklearn.metrics import silhouette_samples
sil = silhouette_samples(X, y_pred, metric='euclidean')

from matplotlib import cm
y_low, y_upp = 0, 0
yticks = []

# i: 1~3, c: 0~2
for i, c in enumerate(cluster_labels):
    c_sil = sil[y_pred == c]
    c_sil.sort()
    y_upp += len(c_sil)
    color = cm.jet(float(i) / n_clusters)
    plt.barh(
        range(y_low, y_upp),
        c_sil,
        height=1.0,
        edgecolor='none',
        color=color
    )
    yticks.append((y_low + y_upp) / 2.)
    y_low += len(c_sil)

sil_avg = np.mean(sil)
plt.axvline(sil_avg, color="r", linestyle="--")

plt.yticks(yticks, cluster_labels + 1)
plt.ylabel('Cluster')
plt.xlabel('Silhouette coefficient')

plt.tight_layout()
plt.show()

圖片指標：

1. 盡量讓每個聚類樣本數量相近
2. 每個聚類基本上要大於輪廓係數（平均值）

我們同時也可以比較 k=2，會發現其不符合上述指標。

6-2. Hierarchical Clustering 層次聚類

同為硬聚類的一種。將資料集逐次「合併或分裂」，直到要求的聚類數為止。
依照原理，層次聚類分成兩種方法：

A. Divisive Hierarchical Clustering 分裂層次聚類

將所有樣本視為一個聚類，將其逐步分割，直到達成指定聚類數為止。

B. Agglomerative Hierarchical Clustering 凝聚層次聚類

反之，以每個樣本為聚類，不停將相近的聚類合併，直到達成指定聚類數為止。
凝聚層次聚類又根據對「聚類間距離」定義不同，分以下四種算法：

Single Linkage 單一聯動

聚類間距定義：不同群聚中最近兩點間的距離。
特點：群聚的過程中產生「大者恆大」的效果，對離群很敏感。

Complete Linkage 完整聯動

聚類間距定義：不同群聚中最遠兩點間的距離。
特點：比較容易產生「齊頭並進」的效果，對離群很敏感。

Average Linkage 平均聯動

聚類間距定義：不同聚類間點與點間的距離總和，取平均。
特點：比較容易產生「齊頭並進」的效果，較不受離群影響。

Ward's method 沃德法

聚類間距定義：兩群合併後，聚類中各點到聚類重心的距離平方和。

覺得抽象的化，用 sklearn 內建的圖片來看就很易懂了：

我們用固定亂數 np.random.seed 產生作範例：

import pandas as pd
import numpy as np

np.random.seed(123)
variables = ['X', 'Y', 'Z']
labels = ['ID_0', 'ID_1', 'ID_2', 'ID_3', 'ID_4']

X = np.random.random_sample([5, 3])*10
df = pd.DataFrame(X, columns=variables, index=labels)
df

使用 pdist 計算點到點距離：

from scipy.spatial.distance import pdist, squareform

# pdist(X, metric=)
# X: nd-array，為 m*n 矩陣。
# metric: 距離求解法。默認 'euclidean'。
# 求解距離的函數。返回 Y 為 Cm取2 個觀察值之間的成對距離。
dis_vec = pdist(df, metric='euclidean')
dis_vec

>>  array([4.973534  , 5.51665266, 5.89988504, 3.83539555, 4.34707339,
           5.10431109, 6.69823298, 7.24426159, 8.31659367, 4.382864  ])

把每個點到點的間距用矩陣表示：

# squareform: 將向量形式的距離表示轉換成矩陣形式，或把矩陣形式轉為向量形式。
matrix = squareform(dis_vec)

row_dis = pd.DataFrame(
    matrix,
    columns=labels,
    index=labels
)
row_dis

Likage（此處使用'complete'算法）

from scipy.cluster.hierarchy import linkage

row_clusters = linkage(df.values, method='complete', metric='euclidean')
pd.DataFrame(
    row_clusters,
    columns=['row label 1', 'row label 2', 'distance', 'no. of items in clust.'],
    index=['cluster %d' % (i + 1) for i in range(row_clusters.shape[0])]
)

# 作圖
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram

row_dendr = dendrogram(
    row_clusters,
    labels=labels,
)
plt.tight_layout()
plt.ylabel('Euclidean distance')

plt.show()

如果只想要得知分群結果，可用 sklearn 內建函數：

from sklearn.cluster import AgglomerativeClustering

ac = AgglomerativeClustering(
    n_clusters=3,
    affinity='euclidean',
    linkage='complete'
)
labels = ac.fit_predict(X)
print(f'Cluster labels: {labels}')

>>  Cluster labels: [1 0 0 2 1]

超參數：
1. n_clusters: 將要分成幾群。默認 2。
2. affinity: 用於計算鏈接的度量。默認 'euclidean'。
3. linkage: 使用哪個鏈接標準，'ward'（默認）, 'complete', 'average', 'single'。

6-3. DBSCAN 基於密度的雜訊應用空間聚類

全名 Density-Based Spatial Clustering of Applications w/ Noise。
不同於 K-means 與 Hierarchical 藉距離定義聚類，DBSCAN 是以「密度」定義聚類。

開始前，我們需要定義兩個參數，分別是：
ε (eps)：由這個參數值為半徑劃出的圓型區域稱為 ε-鄰域。
minPts：構成高密度區域需要最少有幾個點。

詳細步驟：

1. 隨機抽一資料點，探索其 ε-鄰域，若有足夠點則建立一新聚類，稱它為 Core Point。
2. 若無發現足夠的點，則標籤它為 Noise Point。
3. 即使點被標籤為雜訊，若往後標籤過程中被視為聚類的一員，則標籤為 Border Point。

如下圖，即使單看點 C 會將其標籤為雜訊，但它同時也是點 A 聚類的一員。

我們使用 make_moons 做範例：

from sklearn.datasets import make_moons
import matplotlib.pyplot as plt

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)
plt.scatter(X[:, 0], X[:, 1], c='grey')
plt.tight_layout()

plt.show()

聚類方法：

# 用 K-means 做
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
km = KMeans( n_clusters=2, random_state=0)
y_km = km.fit_predict(X)

# 用聚類分析做
ac = AgglomerativeClustering(n_clusters=2, affinity='euclidean', linkage='complete')
y_ac = ac.fit_predict(X)

# 用 DBSCAN 做
db = DBSCAN(eps=0.2, min_samples=5, metric='euclidean')
y_db = db.fit_predict(X)

超參數：
1. eps: 兩個樣本之間的最大距離，即 ε 。默認 0.5。
2. min_samples: 包括自身，將一個點視為核心點的鄰近樣本數（或總權重）。默認 5。

作圖：

f, (ax1, ax2, ax3) = plt.subplots(1, 3, figsize=(12, 3))

axis = [ax1, ax2, ax3]
y_ = [y_km, y_ac, y_db]
titles = ['K-means clustering', 'Agglomerative clustering', 'DBSCAN']

for a, y, t in zip(axis, y_, titles):
    a.scatter(
        X[y == 0, 0], X[y == 0, 1],
        c='lightblue', marker='o', s=40, label='cluster 1'
    )
    a.scatter(
        X[y == 1, 0], X[y == 1, 1],
        c='red', marker='o', s=40, label='cluster 2'
    )

    a.set_title(t)

plt.legend()
plt.tight_layout()

plt.show()

在聚類非線性資料集時，DBSCAN 表現通常比 K-means、Hierarchical 好。

最後，DBSCAN 也可以用來找尋資料集中的離群，請看 wine 範例：

from sklearn.datasets import load_wine
ds = load_wine()
X = pd.DataFrame(ds.data, columns=ds.feature_names)[['flavanoids', 'color_intensity']]
y = pd.DataFrame(ds.target, columns=['Wine'])

# 作圖
plt.scatter(X.iloc[:, 0], X.iloc[:, 1], c='b', marker='o')
plt.xlabel('Concentration of flavanoids', fontsize=16)
plt.ylabel('Color intensity', fontsize=16)
plt.title('Concentration of flavanoids vs Color intensity', fontsize=20)

plt.show()

要注意的是這邊只把影響最大的因子 'flavanoids' 丟進 DBSCAN

X_data = X.iloc[:, 0:1].values

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=0.2, min_samples=19).fit(X_data)

import numpy as np
y_pred = db.labels_

# 作圖
import matplotlib.pyplot as plt
plt.scatter(X.iloc[:, 0], X.iloc[:, 1], c=y_pred, marker='o')
plt.xlabel('Concentration of flavanoids', fontsize=16)
plt.ylabel('Color intensity', fontsize=16)

plt.show()

尋找 Outlier：

df[y_pred == -1]

至此，大致上說完 Cluster analysis 較常用的三種方法了。

結論：

1. K-means 較有效率，但遇到大資料與非線性資料效果較差。
2. Hierarchical 步驟為慢慢整併各類，在視覺化上較直觀。
3. DBSCAN 在尋找離群值 & 非線性資料時效果好，但在密度相近的異群間效果差。
   .
   .
   .
   .
   .

補充資料

若有需求，可到以下網站習得更多：

1. Kaggle
2. Susan Li's Blog
3. ML mastery
4. Medium