111 年 國立成功大學電腦與通信工程研究所丁組《人工智慧概論》

這題主要在比較兩種常見的無監督式學習演算法：階層式分群 (Hierarchical Clustering) 與 K-means 分群。考驗考生對這兩種演算法的優缺點的理解。

核心觀念：

• 階層式分群 (Hierarchical Clustering)： 建立一個巢狀結構（樹狀圖，dendrogram），可以不預設群數，觀察群數與分群品質的權衡。
• K-means 分群 (K-means Clustering)： 需要預設群數 $k$，以迭代方式將資料點分配到 $k$ 個群中，目標是最小化簇內平方和 (within-cluster sum of squares, WCSS)。

解題：

• 階層式分群相較於 K-means 的優勢：
  階層式分群的優勢在於它不需要預先指定群數 $k$。

核心觀念

本題考查搜尋策略的最優性，以及博弈論中的 Nash equilibrium：

• 深度優先搜尋（Depth-First Search, DFS）
• 廣度優先搜尋（Breadth-First Search, BFS）
• 貪婪最佳優先搜尋（Greedy Best-First Search）
• A* 搜尋與可接受啟發函數（admissible heuristic）
• Nash equilibrium 的定義

判斷「最優」時，必須先確認成本函數：

• 路徑成本最優：找到的路徑總成本 $g(n)$ 最小。
• 步數最優：找到的路徑邊數最少。

除非題目特別說明，搜尋問題通常假設邊成本為非負數；BFS 的步數最優性還要求每一步成本相同。

---

解題方法

逐項對照各搜尋法的選取規則與最優性條件：

1. DFS 以「最深節點優先」為原則，不比較路徑成本或步數。
2. BFS 以「深度最小優先」為原則，因此在單位成本下可保證最少步數。
3. Greedy Best-First Search 依啟發值 $h(n)$ 選擇估計距離目標最近的節點。
4. A* 通常使用
   $f(n)=g(n)+h(n)$
   若 $h(n)$ 可接受，則不會高估從 $n$ 到目標的真實最小成本。
5. Nash equilibrium 的重點是：在其他玩家策略固定時，任何單一玩家都沒有透過單方面改變策略而改善報酬的動機。

---

選項分析

(a) Depth first search will find an optimal path with respect to the cost of the path.

錯誤。

DFS 只優先展開目前最深的節點，不會比較路徑成本。即使先找到一條路徑，也不代表其成本最低。

例如：

• 路徑 $S\to A\to G$ 的成本為 $100$
• 路徑 $S\to B\to C\to G$ 的成本為 $3$

若 DFS 先沿著 $A$ 展開，便可能先找到成本 $100$ 的解，之後才發現成本 $3$ 的路徑。因此 DFS 不保證路徑成本最優。

---

(b) Depth first search will find an optimal path with respect to the number of steps in the path.

錯誤。

DFS 不以深度最小為選擇依據，而是一路深入到底。它可能先找到一條步數較多的路徑，再找到步數較少的路徑。

例如：

• $S\to A\to G$：共有 $2$ 步
• $S\to B\to C\to D\to G$：共有 $4$ 步

若 DFS 優先探索 $B$ 分支，可能先找到 $4$ 步的解，因此無法保證步數最少。

---

(c) Breadth first search will find an optimal path with respect to the cost of the path.

錯誤。

BFS 依節點深度排序，保證的是步數最少，不是總成本最小。

若每條邊成本不同，較少步數的路徑可能反而比較昂貴。例如：

• $S\to A\to G$：$2$ 步，總成本 $100$
• $S\to B\to C\to G$：$3$ 步，總成本 $3$

BFS 會優先找到 $2$ 步的路徑，但其成本為 $100$，並非成本最優。

只有在所有邊成本相同時，最少步數才等價於最低路徑成本。

---

(d) Breadth first search will find an optimal path with respect to the number of steps in the path.

正確，但有條件。

BFS 依照深度由小到大展開節點。深度為 $d$ 的所有節點都會在深度為 $d+1$ 的節點之前被處理，因此第一次找到目標時，該路徑具有最少步數。

因此，在有限分支、可找到解的情況下，BFS 保證步數最少的解。

若把每一步視為成本相同，例如每條邊成本皆為 $1$，則 BFS 同時也保證路徑成本最小。

---

(e) The greedy search algorithm works by always computing the successors of the unexpanded search space node that a he

核心觀念

本題考查對抗式搜尋中的 Minimax 演算法：

• Max 節點代表第一位玩家，選擇子節點中數值最大的結果。
• Min 節點代表對手，選擇子節點中數值最小的結果。
• 從葉節點開始，由下往上逐層回傳數值。

公式為：

$$V(\text{Max})=\max_i V_i,\qquad V(\text{Min})=\min_i V_i$$

解題方法

依照圖中由左至右的葉節點：

$$6,\ 5,\ 2,\ 6,\ 4,\ 7,\ 2,\ 2,\ 5,\ 6,\ 1,\ 5,\ 3,\ 9,\ 2,\ 6$$

1. 最底層 Min 節點

每個 Min 節點取其兩個葉節點的較小值：

$$\begin{aligned} m_1&=\min(6,5)=5\\ m_2&=\min(2,6)=2\\ m_3&=\min(4,7)=4\\ m_4&=\min(2,2)=2\\ m_5&=\min(5,6)=5\\ m_6&=\min(1,5)=1\\ m_7&=\min(3,9)=3\\ m_8&=\min(2,6)=2 \end{aligned}$$

因此最底層方框由左至右為：

$$\boxed{5,\ 2,\ 4,\ 2,\ 5,\ 1,\ 3,\ 2}$$

2. 中間 Max 節點

每個 Max 節點取下方兩個 Min 節點的較大值：

這題考驗對隨機森林 (Random Forest) 相較於單一決策樹 (Decision Tree) 的優勢的理解。

核心觀念：

• 決策樹 (Decision Tree)： 一種監督式學習模型，通過一系列規則將資料分割成越來越小的子集，最終在葉節點做出預測。優點是易於理解和解釋，但容易過度擬合。
• 隨機森林 (Random Forest)： 一種集成學習方法，通過構建多個決策樹並對它們的預測進行平均（迴歸）或投票（分類）來提高預測準確性和穩定性。它引入了隨機性，以減少決策樹之間的相關性。

解題：

隨機森林相較於單一決策樹有以下三個潛在的優勢：

1. 降低過度擬合 (Reduced Overfitting)： 單一決策樹，尤其是生長到足夠深的決策樹，很容易學習到訓練資料中的雜訊，導致在未見過的資料上表現不佳（過度擬合）。

這題考驗對決策樹過度擬合 (Overfitting) 現象的理解，以及如何通過一些策略來緩解這個問題。

核心觀念：

• 過度擬合 (Overfitting)： 模型在訓練資料上表現極好，但在新的、未見過的測試資料上表現較差。這通常發生在模型過於複雜，學習到了訓練資料中的雜訊或個別案例，而不是底層的數據模式。
• 決策樹的過度擬合： 當決策樹生長得過於「深」或「複雜」時，容易發生過度擬合。樹的每個節點都試圖找到最佳分割，導致樹的結構非常精細，能夠完美匹配訓練資料，但也容易捕捉雜訊。

解題：

有幾種常見的策略可以幫助減少決策樹的過度擬合：

1. 預剪枝 (Pre-pruning)： 在決策樹生長過程中，設置一些停止條件來限制樹的生長。常見的預剪枝策略包括：

   • 限制樹的最大深度 (Maximum Depth)： 設定一個最大層數，一旦達到就停止生長。
   • 設置節點所需的最小樣本數 (Minimum Samples per Node)： 要求一個節點必須包含至少一定數量的樣本才能繼續分割。
   • 設置葉節點所需的最小樣本數 (Minimum Samples per Leaf)： 要求一個葉節點（終端節點）至少要包含一定數量的樣本。
   • 設置節點熵或基尼不純度閾值 (Impurity Threshold)： 如果分割帶來的純度提升（例如，資訊增益或 Gini 增益）低於某個閾值，則停止分割。

2. 後剪枝 (Post-pruning)： 先讓決策樹生長到足夠大（可能過度擬合），然後再移除樹的某些分支或節點，以簡化模型。常見的後剪枝策略包括：