決策樹、降維與分群Trees, Dimensionality Reduction & Clustering

前兩章的模型都假設某種線性結構。這一章介紹三類形式完全不同的方法：決策樹以一連串「是或否」的問題切分特徵空間，能自然地捕捉非線性與交互作用；主成分分析與它的核函數版本在沒有標籤的情況下，找出資料變化最大的方向，用來降維與視覺化；K-means 則把資料分成幾個彼此相似的群組。

後兩者屬於非監督式學習（unsupervised learning）：沒有 $y$ 可以對照，也就沒有「測試誤差」這樣明確的評估標準。因此理解每個方法的目標函數到底在最佳化什麼，比在監督式學習中更加重要。

4.1決策樹Decision Trees

決策樹把特徵空間切成許多互不重疊的矩形區域 $R_1, \ldots, R_J$，在每個區域內給出一個固定的預測值：迴歸樹用區域內 $y$ 的平均，分類樹用區域內的多數類別。

找出全域最佳的切分方式在計算上不可行，所以實務上採用由上而下的貪婪遞迴二元分割（greedy recursive binary splitting）：在目前的節點，嘗試每一個特徵 $j$ 與每一個切分點 $s$，選出讓兩個子節點總成本最小的那一組，然後在兩個子節點上重複同樣的步驟。每一步只看眼前最好的切法，不考慮之後的影響，這就是「貪婪」的意思。

迴歸樹

迴歸樹以 RSS 作為成本。以特徵 $j$、切分點 $s$ 把節點分為 $R_1(j, s) = \{\mathbf{x} \mid x_j < s\}$ 與 $R_2(j, s) = \{\mathbf{x} \mid x_j \ge s\}$，選擇

其中 $\bar y_{R_m}$ 是區域 $R_m$ 內反應變數的平均。

分類樹與不純度

分類樹以不純度（impurity）衡量一個節點的類別有多混雜。令 $\hat p_{mk}$ 為節點 $m$ 中屬於第 $k$ 類的比例：

三者都在節點只含單一類別時等於 0，在各類別平均混雜時最大。分割時選擇讓子節點加權平均不純度最小的切法，權重是各子節點的樣本比例。

舉例來說，一個節點有 10 筆資料，兩類各 5 筆，吉尼不純度為 0.5。若某個切分得到左邊 4 比 1、右邊 1 比 4，兩個子節點的吉尼不純度都是 $2 \times 0.8 \times 0.2 = 0.32$，加權平均為 0.32，不純度下降 0.18。

吉尼不純度與熵是可微分的平滑函數，對節點純度的變化比錯誤分類率敏感，因此適合用來長樹；錯誤分類率則常用在剪枝時評估整棵樹的表現。

停止條件與剪枝

如果一直分割下去，每個葉節點最後只剩一筆資料，訓練誤差為 0，但完全過擬合。常見的停止條件有：

• 節點的樣本數少於門檻 $a$ 時不再分割，或要求分割後每個子節點至少有 $a$ 筆資料。
• 樹的深度達到上限 $c$。
• 分割帶來的不純度下降小於門檻。

但提早停止有一個盲點：一個本身看似無用的分割，可能讓下一層出現非常好的分割（典型例子是 XOR 型態的資料）。因此更好的策略是先長出一棵很大的樹，再進行成本複雜度剪枝（cost-complexity pruning）：對每個 $\alpha \ge 0$，找出最小化

的子樹 $T$，其中 $|T|$ 是葉節點個數。$\alpha$ 的角色與正則化參數相同，用交叉驗證選擇（見第 5 章）。

高變異與集成方法

決策樹容易解讀、不需要標準化特徵、能處理混合型態的變數，但最大的缺點是變異很高：訓練資料稍有變動，長出來的樹可能截然不同。改善的方法不是把單一棵樹變簡單，而是結合許多棵樹：

• 袋裝法（bagging）與隨機森林（random forest）：以自助抽樣（bootstrap）訓練多棵深樹再取平均，主要降低變異。隨機森林在每次分割時只從隨機抽出的部分特徵（例如 $\sqrt{p}$ 個）中挑選，讓各棵樹之間的相關性降低，平均的效果更好。
• 提升法（boosting）：依序訓練許多棵淺樹，每一棵修正前面模型的殘差或錯誤，主要降低偏誤。

兩者的細節見第 5 章。

4.2主成分分析Principal Component Analysis

主成分分析（Principal Component Analysis, PCA）尋找一組新的正交座標軸，使資料投影到前幾個軸上時保留最多的變異。它可以從兩個等價的角度理解：最大化投影變異，或最小化重建誤差；實際計算則通常透過奇異值分解。

以下設資料矩陣 $\mathbf{X}$ 為 $N \times p$，每一欄都已減去平均（中心化），樣本共變異數矩陣為 $\mathbf{S} = \mathbf{X}^\top \mathbf{X} / (N - 1)$。

最大變異數的觀點

第一主成分方向 $\mathbf{v}_1$ 是讓投影變異最大的單位向量：

以拉格朗日乘數法可得 $\mathbf{S}\mathbf{v}_1 = \lambda_1 \mathbf{v}_1$：$\mathbf{v}_1$ 是 $\mathbf{S}$ 最大特徵值對應的特徵向量，投影後的變異數恰好就是 $\lambda_1$。第二主成分在與 $\mathbf{v}_1$ 正交的條件下最大化變異，依此類推。整體而言就是共變異數矩陣的特徵分解（eigendecomposition）$\mathbf{S} = \mathbf{V} \boldsymbol\Lambda \mathbf{V}^\top$：

• 特徵值 $\lambda_j$ 是第 $j$ 個主成分的變異數。
• 特徵向量 $\mathbf{v}_j$ 稱為負荷量（loadings），代表每個原始變數在這個主成分中的權重。
• 第 $i$ 筆資料在第 $j$ 個主成分上的分數（score）為 $z_{ij} = \mathbf{x}_i^\top \mathbf{v}_j$。

重建誤差的觀點

另一個角度是：用 $q$ 維（$q < p$）的仿射子空間近似資料，讓重建誤差最小：

其中 $\mathbf{V}_q$ 是 $p \times q$ 矩陣，各欄為彼此正交的單位向量（$\mathbf{V}_q^\top \mathbf{V}_q = \mathbf{I}_q$）；$\boldsymbol\mu \in \mathbb{R}^p$ 是位置向量；$\boldsymbol\lambda_i \in \mathbb{R}^q$ 是第 $i$ 筆資料在子空間中的座標。注意這裡粗體的 $\boldsymbol\lambda_i$ 是座標向量，與前面的特徵值 $\lambda_j$ 不同。

固定 $\mathbf{V}_q$ 時，最佳解為

也就是先中心化、再投影到子空間。最佳的 $\mathbf{V}_q$ 則由前 $q$ 個特徵向量組成。兩種觀點等價的原因是畢氏定理：每筆資料到平均的距離平方，等於「投影在子空間內的部分」加上「垂直於子空間的部分」。總和固定，保留的變異越大，重建誤差就越小。最小的重建誤差為 $(N-1)\sum_{j > q} \lambda_j$，也就是被捨棄的那些主成分的變異總和。

以 SVD 計算

實務上不直接計算 $\mathbf{X}^\top \mathbf{X}$，而是對中心化後的 $\mathbf{X}$ 做奇異值分解（Singular Value Decomposition, SVD），數值上更穩定。設 $N \ge p$，精簡形式的 SVD 為

代入可得 $\mathbf{X}^\top \mathbf{X} = \mathbf{V} \mathbf{D}^2 \mathbf{V}^\top$，因此：

• $\mathbf{V}$ 的各欄就是 $\mathbf{X}^\top \mathbf{X}$（也是 $\mathbf{S}$）的特徵向量，即主成分的負荷量。
• 奇異值 $d_j$ 是 $\mathbf{X}^\top \mathbf{X}$ 特徵值的平方根；共變異數矩陣的特徵值為 $\lambda_j = d_j^2 / (N - 1)$。
• 主成分分數為 $\mathbf{Z} = \mathbf{X}\mathbf{V} = \mathbf{U}\mathbf{D}$，大小 $N \times p$。

從幾何上看，$\mathbf{x}_i$ 在第 $k$ 個主成分方向上的投影是 $u_{ik} d_k \mathbf{v}_k$：$\mathbf{v}_k$ 決定方向，$u_{ik} d_k$ 則是沿著這個方向的座標，也就是帶正負號的距離。

要保留幾個主成分

第 $j$ 個主成分的解釋變異比例（proportion of variance explained, PVE）為 $\lambda_j / \sum_{l} \lambda_l$。常見的選擇方式有：

• 畫出各主成分 PVE 的陡坡圖（scree plot），在曲線明顯轉平的「手肘」處截斷。
• 保留累積 PVE 達到某個門檻（例如 80% 或 90%）所需的主成分數，這只是經驗法則。
• 若 PCA 是後續監督式模型的前處理，則把 $q$ 當成超參數，以交叉驗證選擇。

import numpy as np

Xc = X - X.mean(axis=0)                       # 先中心化
U, d, Vt = np.linalg.svd(Xc, full_matrices=False)
eigvals = d**2 / (len(Xc) - 1)                # 各主成分的變異數
pve = eigvals / eigvals.sum()                 # 解釋變異比例
Z = U[:, :q] * d[:q]                          # 前 q 個主成分分數，等於 Xc @ Vt[:q].T

4.3核主成分分析Kernel PCA

PCA 只能找出線性的結構。核主成分分析（kernel PCA）先用一個非線性映射把資料送到高維的特徵空間，再在那裡做 PCA：

特徵空間可能非常高維甚至無限維，無法直接計算 $\phi(\mathbf{x})$。關鍵在於 PCA 需要的只是資料之間的內積，而內積可以用核函數（kernel function）直接算出：$k(\mathbf{x}, \mathbf{y}) = \langle \phi(\mathbf{x}), \phi(\mathbf{y}) \rangle$。這就是核技巧（kernel trick），它也是支援向量機的核心（見第 6 章）。常用的核函數包括高斯（RBF）核 $k(\mathbf{x}, \mathbf{y}) = \exp(-\lVert \mathbf{x} - \mathbf{y} \rVert^2 / 2\sigma^2)$ 與多項式核 $(\mathbf{x}^\top \mathbf{y} + c)^d$；取線性核 $\mathbf{x}^\top \mathbf{y}$ 時，就回到一般的 PCA。

演算法

1. 計算 $n \times n$ 的核矩陣 $\mathbf{K}$，$K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$。
2. 中心化。PCA 要求資料平均為 0，但我們無法直接在特徵空間中減去平均，改為對核矩陣做等價的轉換（見下式）。

其中 $\mathbf{1}$ 是長度 $n$ 的全 1 向量，$\mathbf{1}\mathbf{1}^\top$ 是 $n \times n$ 的全 1 矩陣，而 $\mathbf{1}^\top \mathbf{1} = n$。

3. 對 $\tilde{\mathbf{K}}$ 做特徵分解，得到特徵對 $(\lambda_i, \boldsymbol\alpha_i)$，即第 $i$ 大的特徵值 $\lambda_i$ 與對應的特徵向量 $\boldsymbol\alpha_i$。
4. 正規化。特徵空間中的主成分方向是 $\sum_j \alpha_{ij} \tilde\phi(\mathbf{x}_j)$，要讓它長度為 1，需縮放 $\boldsymbol\alpha_i$ 使 $\lambda_i \, \boldsymbol\alpha_i^\top \boldsymbol\alpha_i = 1$。
5. 投影。第 $j$ 筆訓練資料在第 $i$ 個主成分上的分數為 $(\tilde{\mathbf{K}} \boldsymbol\alpha_i)_j = \lambda_i \alpha_{ij}$；新資料 $\mathbf{x}$ 的分數則為 $\sum_j \alpha_{ij} \tilde k(\mathbf{x}, \mathbf{x}_j)$，其中 $\tilde k$ 以訓練資料的平均做同樣的中心化。

在這樣的正規化下，第 $i$ 個主成分分數的平方和恰為 $\lambda_i$，所以 $\lambda_i / n$ 就是該主成分在特徵空間中的變異數，選擇保留幾個主成分的方式與一般 PCA 相同。

代價是核矩陣的大小為 $n \times n$：記憶體需求 $O(n^2)$，完整特徵分解 $O(n^3)$，樣本數大時需要近似方法。此外，核函數與其參數（如 RBF 的 $\sigma$）的選擇對結果影響很大，而且特徵空間中的點通常無法直接映射回原始空間。

正規化核函數

若對所有 $\mathbf{x}$ 都有 $k(\mathbf{x}, \mathbf{x}) = 1$，稱為正規化核函數（normalized kernel）。這表示每個 $\phi(\mathbf{x})$ 在特徵空間中的長度都是 1，全部落在單位球面上。RBF 核就具有這個性質。

由於核函數是內積，它滿足柯西－施瓦茲不等式（Cauchy–Schwarz inequality）：

因此任何核函數都可以正規化為

由不等式可知 $|\hat k(\mathbf{x}, \mathbf{y})| \le 1$，它正是 $\phi(\mathbf{x})$ 與 $\phi(\mathbf{y})$ 夾角的餘弦值，可以直接解讀為相似度。

4.4K-means 與 K-mediansK-means and K-medians

目標函數

給定群數 $K$，K-means 要把資料分成 $K$ 群，並找出各群中心 $\mathbf{m}_1, \ldots, \mathbf{m}_K$，使每個點到其所屬群中心的距離平方總和（群內平方和）最小：

其中 $C(i)$ 表示第 $i$ 個點被分配到的群。

Lloyd 演算法

同時最佳化分群與中心是 NP-hard 問題，標準做法是交替固定其中一個、最佳化另一個：

1. 更新中心：給定分群 $C$，每一群的中心取該群所有點的平均，$\mathbf{m}_k = \operatorname{mean}\{\mathbf{x}_i : C(i) = k\}$。
2. 重新分配：給定中心，把每個點分到最近的中心，$C(i) = \arg\min_{k} \lVert \mathbf{x}_i - \mathbf{m}_k \rVert^2$。
3. 重複步驟 1、2，直到分群不再改變。

每一步都不會讓 $W$ 增加，而可能的分群方式是有限的，因此演算法一定會在有限步內收斂，但收斂到的只是局部最佳解。

初始化與多次啟動

結果取決於初始中心的位置，不同的起點可能收斂到很不一樣的局部最佳解。常見的對策有兩個：

• 多次隨機啟動：用不同的初始中心執行多次，保留 $W$ 最小的結果。
• k-means++ 初始化：第一個中心隨機選一個資料點；之後每個新中心，以「與目前最近中心的距離平方」成正比的機率從資料點中抽出。這讓初始中心彼此分散，在期望值上保證得到的 $W$ 不超過最佳值的 $O(\log K)$ 倍。

選擇 $K$

最佳的 $W$ 隨 $K$ 增加只會持平或下降（$K = n$ 時 $W = 0$），所以不能直接選 $W$ 最小的 $K$。常見的方法有：

• 手肘法（elbow method）：畫出 $W$ 對 $K$ 的曲線，選在下降幅度明顯趨緩的轉折處。
• 輪廓係數（silhouette coefficient）：對每個點計算 $s(i) = \dfrac{b(i) - a(i)}{\max\{a(i), b(i)\}}$，其中 $a(i)$ 是它到同群其他點的平均距離，$b(i)$ 是它到最近的其他群所有點的平均距離。$s(i)$ 介於 $-1$ 與 1 之間，越接近 1 表示分得越好；選擇平均輪廓係數最大的 $K$。

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

for k in range(2, 9):
    km = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=0).fit(X)
    print(k, km.inertia_, silhouette_score(X, km.labels_))   # inertia_ 即 W

K-means 以歐氏距離衡量相似度，隱含假設各群大致呈球狀、大小相近，因此也需要先標準化特徵，否則單位大的變數會主導距離。

K-medians 與 K-medoids

K-means 的中心是平均值，容易被離群值拉走。K-medians 把距離改為 L1（曼哈頓）距離 $\sum_j |x_{ij} - m_{kj}|$，在這個距離下最佳的中心是逐座標的中位數。中位數不受極端值影響，因此 K-medians 對離群值較穩健。K-medoids 更進一步，要求中心必須是實際的資料點，可以搭配任意的相異度量。

4.5參考資料References

• James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning（ISLR），Springer, 2013，第 8、10 章。
• Hastie, Tibshirani & Friedman, The Elements of Statistical Learning（ESL），2nd ed., Springer, 2009，第 9.2、14.3、14.5 節。
• Breiman, Friedman, Olshen & Stone, Classification and Regression Trees, Wadsworth, 1984。
• Breiman, "Random Forests", Machine Learning, 2001。
• Jolliffe, Principal Component Analysis, 2nd ed., Springer, 2002。
• Schölkopf, Smola & Müller, "Nonlinear Component Analysis as a Kernel Eigenvalue Problem", Neural Computation, 1998。
• Lloyd, "Least Squares Quantization in PCM", IEEE Transactions on Information Theory, 1982。
• Arthur & Vassilvitskii, "k-means++: The Advantages of Careful Seeding", SODA, 2007。
• Rousseeuw, "Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis", Journal of Computational and Applied Mathematics, 1987。