# [筆記] 機器學習 聚類 ( Clustering )

* 屬於非監督式學習

* 使用的是未標記的資料，{x⁽¹⁾, x⁽²⁾, x⁽³⁾, ..., x^(m)}
* 

### K 均值算法 ( K-Means )

1. 隨機選擇 i 個點叫做聚類中心 ( cluster centroids )，因為要分成 i 類


2. 進行聚類分配，所有資料點依照對聚類中心的遠近做分配


3. 移動聚類中心，依照分配到的點，移動聚類中心到這些點的均值處


4. 重複上面 2、3 點，直到聚類中心不變


#### 算法

* 輸入

* K ( 分成 K 類 )
* 訓練集 {x⁽¹⁾, x⁽²⁾, x⁽³⁾, ..., x^(m)} ( 不使用 x₀ = 1 )

* 計算

* 隨機初始化 K 個聚類中心 μ₁，μ₂，...，μ_K
* 重複操作 :

* for i = 1 to m

* c⁽ⁱ⁾ := x⁽ⁱ⁾ 靠近哪個聚類中心 ( 1 到 K )
* c⁽ⁱ⁾ = $min||x^{(i)} - μ_k||^2$

            function idx = findClosestCentroids(X, centroids)

            K = size(centroids, 1);
            idx = zeros(size(X,1), 1);
            xtokvalue = zeros(K, 1);

            for i = 1:size(X, 1)

              for j = 1:K

                % 算出 X 與每個 K 的距離
                xtokvalue(j) = sum((X(i, :) - centroids(j, :)) .^ 2);

              endfor

              % 找出最小距離的 K，索引放入 idx
              [val, ind] = min(xtokvalue);
              idx(i) = ind;

            endfor

            end

* 在 Octave 上找出與類聚中心最小距離的函式

* for k = 1 to K

* μ_k := 分配給聚類中心 k 的資料平均
* μ_k = $\dfrac{1}{分配給聚類中心 k 的資料量}(x^{(k'sdata1)} + x^{(k'sdata2)} + x^{(k'sdata3)} + ...)$

            function centroids = computeCentroids(X, idx, K)

            [m n] = size(X);
            centroids = zeros(K, n);

            for i = 1:K

              % 抓出靠近聚類中心的資料
              temp = find(idx == i);

              % 計算出要移動到的點
              centroids(i, :) = sum(X(temp, :)) / size(X(temp, :), 1);

            endfor

            end

* 在 Octave 上移動類聚中心的函式

* 如果有個聚類中心沒有分配到資料點，我們通常會把他刪除，變成 K - 1 個聚類中心

#### 優化目標函數

* $c^{(i)}$ 表示當前 x⁽ⁱ⁾ 歸屬哪個聚類中心 ( 1 到 K )
* $μ_k$ 表示聚類中心 k
* $x_{c^{(i)}}$ 表示 x⁽ⁱ⁾ 所屬的聚類中心


* 又稱失真代價函數 ( distortion cost function )
* 先使 c 為變量，求 J 最小值 ( 進行聚類分配 )
* 後使 μ 為變量，求 J 最小值 ( 移動聚類中心 )

#### 隨機初始化聚類中心

* K 一定是小於 m，選定 K
* 隨機挑選 K 個訓練資料
* 設定 μ₁，μ₂，...，μ_K 等於這些訓練資料
* 避免局部最優 : 多次隨機初始化，找出最優 ( 對於 K = 2 ~ 10 會很有效果，如果 K 較大，剛開始可能就會是較好的結果，多次隨機初始化並不會有太大效果 )

* for i = 1 to 100 ( 有時是 50 ~ 1000 )

* 隨機初始化 K-Means
* 執行 K-Means，取得 c⁽¹⁾，...，c^(m)，μ₁，...，μ_K
* 計算代價函數 J(c⁽¹⁾, ..., c^(m), μ₁, ..., μ_K)

* 選出能算出最小 J(c⁽¹⁾, ..., c^(m), μ₁, ..., μ_K) 的聚類

function centroids = kMeansInitCentroids(X, K)

centroids = zeros(K, size(X, 2));

randidx = randperm(size(X, 1));
centroids = X(randidx(1:K), :);

end

* 在 Octave 上隨機初始化聚類中心的函式

#### 選擇聚類數 K

1. 肘部法則 ( Elbow method )


* 發現在 K = 3 之後下降緩慢，這裡就選擇 K = 3


* 沒有清楚的肘點就不太適用此方法

P.S. 假如 K 增加，代價函數 J 也增加了，可能是遇上了局部最優，試試多次隨機初始化

2. 依需求選擇 K


* 需要分類 S，M，L 三個衣服尺寸


* 需要分類 XS，S，M，L，XL 三個衣服尺寸

###### tags: `筆記` `機器學習` `聚類`