Unsupervised Learning - Week_8_part1

Clustering

Unsupervised Learning: Introduction

監督式學習(supervised learning)和非監督式學習(unsupervised learning)皆是機器學習的演算法的類別之一。差別在於監督式學習，其資料有標籤，非監督式學習，其資料無標籤，簡單來說以分類問題為例，若資料本身有定義分類的標籤，則適合使用監督式學習去訓練模型，若資料本身並無定義分類標籤，單純想針對資料進行結構分類，則適合使用監督式學習去訓練模型。

監督式學習

非監督式學習

K-Means Algorithm

K-mean是目前最普及的聚類算法，也算是非監督式學習算法之一，K-mean是一個迭代的演算法，透過迭代的過程找到真正的聚類中心，假設我們想亦將數據聚類分成n類，其概念如下面步驟：

1. 首先先選擇K個隨機的點，稱為聚類中心(cluster centroids)。
2. 對於數據及中的每一個數據，按照距離K個中心的距離，將其與距離最近的中心點關聯起來，與同一個中心點關聯的所有點聚成一類。
3. 計算每一組的平均值，將該組所關聯的中心點移動到平均值的位置。
4. 重複步驟2-4直到中心點不再變化。

下圖是虛擬碼(用來示意程式如何執行，非程式碼) ，大寫K代表聚類中心的總數個數，小寫k是指第k個聚類中心，𝜇₁, 𝜇₂, 𝜇₃,...,𝜇_k來表示聚類中心，用c⁽¹⁾, c⁽²⁾,...,c^(m)來儲存與第i個實例數據最近的聚類中心的索引，K-mean算法的偽代碼如下：

K-mean演算法主要分為兩步驟，第一個for迴圈是用來賦值，第二個迴圈是聚類中心的移動。K-mean也可以很便利地用於將數據分為許多不同組，即使在沒有非常明顯區分的祖群的情況下也可以。下圖所示的數據包含身高和體重兩項特徵構成，利用K-mean演算法將數據分為三類用於幫助確定要生產的T-shirt的三種尺寸。

--------------------------------------------------------------------------------------------------------------------------

Optimization Objectives

首先在這節裡面會提到，我們的優化目標，每個機器學習演算法都有他的優化目標，為了確認我們的演算法有正確的運行，我們必須先知道我們的優化目標。

價值函數就是我們的優化目標，K-mean的最小化問題就是要最小化所有數據與其所關聯的聚類中心點之間的距離和，因此K-mean的代價函數(又稱畸變函數 Distortion function)

其中𝜇_c⁽ⁱ⁾代表與x⁽ⁱ⁾最近的聚類中心點，我們的優化目標就是找出使得代價函數最小的c⁽¹⁾, c⁽²⁾, ..., c^(m)和𝜇₁, 𝜇₂,....,𝜇_k。

從上一個小節所提出K-mean的迭代算法，第一個迴圈是用於減小c⁽ⁱ⁾所造成的代價函數，所運用的公式如下，c(i)代表某個最接近某個樣本的群聚中心index，j代表第j個群聚中心，𝜇代表某個群聚中心的位置：

而第二個迴圈則適用於減小𝜇⁽ⁱ⁾所造成代價函數，簡單來說就是要更新具類中心的位置，聚類中心的位置即是用該聚類所有資料點的平均去更新位置，所運用的公式如下：

透過每次這兩個步驟地迭代過程，會慢慢更新群聚的分類與群聚中心的位置，直到後來群聚中心位置幾乎不再改變之後，即代表分類完成，迭代過程中一定每一次都會減少代價函數，若不是每一次代價函數都減小就是出現錯誤。

--------------------------------------------------------------------------------------------------------------------------

Random Initialization

這節中會提到如何在K-mean這演算法中隨機初始化聚類中心，並且討論如何避免局部最優化的問題。

若我們要隨機初始化所有聚類中心點，應該按照下面步驟進行：

1. 我們應該選擇K (聚類數目) < m (訓練樣本數)。
2. 隨機選擇K個訓練樣本
3. 令K個聚類中心分別與被挑選出來的K個訓練樣本相等。

K-mean演算法有個問題存在，就是說可能會停留在一個局部最小值處，取決於初始化的情況而定。正常來說，會如同藍色圈圈所圈起來的狀況去分類，但會因隨機初始化的狀況不同而有所不同的分類狀況，如下圖所示，：

所以為了解決這樣的問題，我們會需要多次的去運行K-mean算法，每一次都重新進行隨機初始化，最後在比較多次運行K-mean的結果。還有可能有些人會想說選擇代價函數最小的結果，但這種方式在K比較小的時候(2-10)還是可以接受，但是如果K比較大，這麼做也不會有明顯的改善。

--------------------------------------------------------------------------------------------------------------------------

Choosing the Number of Clusters

在此節中主要會討論如何去選擇聚類的數目也就是大寫K。答案是目前還沒辦法去透過自動化重此項工作，只能透過人工選擇，但是可以透過一些輔助的方式來幫助你進行選擇。

有些人可能會透過肘部方法(elbow method)來幫助選擇聚類的數目，肘部選擇的方法主要就是透過聚類數和價值函數的xy突來找尋像肘部變化的點，當成聚類數目，如同下方的圖：

不過我們不能期待肘部法則一定會出現明確的肘部變化點。大多數的人都是根據我們運用K-mean算法的動機，然後選擇能最好服務該後續目標的聚類數。

例如，在製造T-shirt的例子中，我們將用戶按照身材聚類，我們可以分成3個size和5個size，這樣的選擇是建立在回答，"聚類後我們製造的T-shirt是否能較好的適合我們的客戶"，這問題的基礎上做出決定去選擇聚類數目。