[筆記] 機器學習 聚類 ( 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 也增加了，可能是遇上了局部最優，試試多次隨機初始化

1. 依需求選擇 K

   

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

     

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

tags: 筆記 機器學習 聚類