111 年 國立成功大學數據科學研究所《計算機概論》

正規化（Regularization）是機器學習和深度學習中用來防止模型過度擬合（overfitting）的技術。過度擬合是指模型在訓練數據上表現極佳，但在未見過的測試數據上表現卻很差，這是因為模型過於複雜，學習到了訓練數據中的雜訊而非潛在的模式。

定義：
正規化透過在模型的損失函數（loss function）中加入一個懲罰項（penalty term）來限制模型的複雜度。這個懲罰項通常與模型權重（weights）的大小有關。透過最小化包含懲罰項的總損失函數，模型會傾向於學習到權重較小的模型，從而降低模型的複雜度，使其更好地泛化到新的數據。

數學上，原本的損失函數 $L(\theta)$，加入正規化項後會變成：
$L_{reg}(\theta) = L(\theta) + \lambda \Omega(\theta)$
其中：

• $L(\theta)$ 是原始的損失函數，$\theta$ 代表模型的參數（權重和偏差）。
• $\Omega(\theta)$ 是正規化項，它衡量模型的複雜度。
• $\lambda$ (lambda) 是一個超參數（hyperparameter），用於控制正規化項的強度。$\lambda$ 越大，正規化的效果越強，模型越簡單；$\lambda$ 越小，正規化的效果越弱，模型越接近原始模型。

常見的正規化方法：

1. L1 正規化（Lasso Regression）：
   正規化項為權重絕對值之和：$\Omega(\theta) = \sum_i |\theta_i|$。
   L1 正規化有稀疏（sparsity）的特性，它傾向於將一些不重要的權重縮減到零，從而實現特徵選擇（feature selection）。

2. L2 正規化（Ridge Regression）：
   正規化項為權重平方之和：$\Omega(\theta) = \sum_i \theta_i^2$。
   L2 正規化會將權重縮減到一個較小的值，但通常不會將其縮減到零。它能使模型更加穩定。

深度學習中的常見正規化技術：
除了 L1 和 L2 正規化，深度學習中還有其他正規化技術：

• Dropout： 在訓練過程中，隨機地「關閉」一部分神經元，使其不參與前向傳播和反向傳播。這迫使網路學習到更魯棒的特徵，避免對特定神經元的依賴。

深度優先搜尋（Depth-First Search, DFS）和廣度優先搜尋（Breadth-First Search, BFS）是圖論中兩種基本的圖遍歷（graph traversal）演算法。它們的主要區別在於遍歷的順序和所使用的輔助數據結構。

1. 遍歷順序：

• DFS： DFS 演算法會盡可能深地探索圖的分支。從起始節點開始，它會選擇一個鄰居節點，然後從該鄰居節點繼續深入探索，直到無法再深入為止。之後，它會回溯到上一個節點，並探索其下一個未訪問的鄰居。DFS 就像是沿著一條路徑一直走到盡頭，然後再返回嘗試其他路徑。
• BFS： BFS 演算法會逐層遍歷圖。它從起始節點開始，首先訪問所有與起始節點直接相連的鄰居節點。然後，再訪問這些鄰居節點的所有未訪問過的鄰居節點，依此類推。BFS 確保了所有距離起始節點為 $k$ 的節點都會在所有距離為 $k+1$ 的節點之前被訪問。BFS 就像是從一個點開始，一層一層地向外擴散。

2. 使用的數據結構：

• DFS： 通常使用**堆疊（Stack）**來實現。在遞迴實現中，堆疊是隱含的（由函數呼叫堆疊管理）；在迭代實現中，需要顯式地使用一個堆疊來儲存待訪問的節點。當訪問一個節點時，將其所有未訪問過的鄰居節點壓入堆疊。
• BFS： 通常使用**佇列（Queue）**來實現。當訪問一個節點時，將其所有未訪問過的鄰居節點加入佇列的尾部。然後，從佇列的頭部取出節點進行訪問。

3. 應用場景：

• DFS：
  • 偵測圖中的環（cycle detection）。
  • 尋找圖的連通分量（connected components）。
  • 拓撲排序（topological sorting），適用於有向無環圖（DAG）。
  • 解決迷宮問題（pathfinding）。
  • 生成樹（spanning tree）的計算。
• BFS：
  • 尋找兩個節點之間的最短路徑（在無權圖中）。
  • 尋找節點之間的最短距離（在無權圖中）。
  • 在網路上搜尋（例如網頁爬蟲）。
  • 垃圾回收（Garbage Collection）中的標記-清除階段。

4. 時間與空間複雜度：
對於一個具有 $V$ 個頂點（vertices）和 $E$ 條邊（edges）的圖：

此題考驗對 Python 裝飾器（decorator）的理解。裝飾器是一種在不修改原函數的基礎上，為函數添加額外功能的語法糖。

3.1. 操作名稱解釋：

題目中描述的「一個函數 dentro 另一個函數」，並在函數定義前使用 @ 符號，這種操作在 Python 中稱為裝飾器（Decorator）。

• 裝飾器（Decorator）： 裝飾器是一種設計模式，它允許你以聲明的方式修改或增強函數或方法。在 Python 中，裝飾器本質上是一個函數，它接收另一個函數作為參數，並返回一個新的函數（通常是包裝函數）。
• 包裝函數（Wrapper Function）： 在這個例子中，wrap() 函數就是一個包裝函數。它接收了原函數 func（即 add 或 sub），並在調用 func() 的前後執行額外的操作（打印函數名）。
• @ 語法糖： @print_func_name 語法是 Python 為簡化裝飾器使用而提供的「語法糖」。它等同於：

  def add():
      print("Note")
  add = print_func_name(add) # 這行等同於 @print_func_name
  
  def sub():
      print("Stop")
  sub = print_func_name(sub) # 這行等同於 @print_func_name
  

  當 add() 和 sub() 被定義時，它們實際上已經被 print_func_name 裝飾了。所以，當我們調用 add() 時，實際上調用的是 print_func_name 返回的 wrap() 函數，這個 wrap() 函數知道原函數的名字 (func.__name__) 並先打印它，然後再調用原函數 func()（即 add 函數本身）。

3.2. 兩個函數調用的輸出：

當程式執行到 if __name__ == "__main__": 區塊時：

此題要求使用 Dijkstra 演算法找出從起始節點 (a) 出發到圖中其他節點的最短路徑。Dijkstra 演算法是一種用於尋找圖中單源最短路徑的貪婪演算法。

Dijkstra 演算法步驟：

1. 初始化：

   • 為所有節點設定一個初始距離。起始節點 (a) 的距離設為 0，其他所有節點的距離設為無限大（$\infty$）。
   • 建立一個集合 S，用來存放已找到最短路徑的節點，初始為空。
   • 建立一個集合 Q，用來存放所有節點，初始時包含所有節點。

2. 迭代： 當 Q 不為空時，重複以下步驟：

   • 從 Q 中選取距離值最小的節點 u。
   • 將 u 從 Q 中移除，並加入 S。
   • 對於 u 的每一個鄰居節點 v（即存在邊 (u, v)）：
     • 計算從起始節點經由 u 到達 v 的距離：alt = dist[u] + weight(u, v)。
     • 如果 alt < dist[v]，則更新 dist[v] = alt，並記錄 v 的前驅節點為 u。

圖示與節點：
根據圖 1，我們有節點 {a, b, c, d, e, f, i}。邊的權重如下（假設圖中的數字即為權重）：

• a -> b: 10
• a -> c: 20
• b -> c: 10
• b -> d: 21
• c -> d: 20
• c -> e: 3
• d -> e: 5
• d -> f: 20
• e -> f: 2
• e -> i: 10
• f -> i: 20

執行 Dijkstra 演算法：

初始化：

• dist: {a: 0, b: $\infty$, c: $\infty$, d: $\infty$, e: $\infty$, f: $\infty$, i: $\infty$}
• S: {}
• Q: {a, b, c, d, e, f, i}

第一次迭代：

• 選取 u = a (dist[a] = 0)。
• 將 a 加入 S。S = {a}。
• 更新 a 的鄰居：
  • b: alt = dist[a] + weight(a, b) = 0 + 10 = 10。由於 10 < dist[b] ($\infty$)，更新 dist[b] = 10，前驅為 a。
  • c: alt = dist[a] + weight(a, c) = 0 + 20 = 20。由於 20 < dist[c] ($\infty$)，更新 dist[c] = 20，前驅為 a。
• dist: {a: 0, b: 10, c: 20, d: $\infty$, e: $\infty$, f: $\infty$, i: $\infty$}
• Q: {b, c, d, e, f, i}

第二次迭代：

• 從 Q 中選取 dist 最小的節點 u = b (dist[b] = 10)。
• 將 b 加入 S。S = {a, b}。
• 更新 b 的鄰居：
  • c: alt = dist[b] + weight(b, c) = 10 + 10 = 20。由於 20 不小於 dist[c] (20)，不更新。
  • d: alt = dist[b] + weight(b, d) = 10 + 21 = 31。由於 31 < dist[d] ($\infty$)，更新 dist[d] = 31，前驅為 b。
• dist: {a: 0, b: 10, c: 20, d: 31, e: $\infty$, f: $\infty$, i: $\infty$}
• Q: {c, d, e, f, i}

第三次迭代：

• 從 Q 中選取 dist 最小的節點 u = c (dist[c] = 20)。
• 將 c 加入 S。S = {a, b, c}。
• 更新 c 的鄰居：
  • d: alt = dist[c] + weight(c, d) = 20 + 20 = 40。由於 40 不小於 dist[d] (31)，不更新。
  • e: alt = dist[c] + weight(c, e) = 20 + 3 = 23。由於 23 < dist[e] ($\infty$)，更新 dist[e] = 23，前驅為 c。
• dist: {a: 0, b: 10, c: 20, d: 31, e: 23, f: $\infty$, i: $\infty$}
• Q: {d, e, f, i}

第四次迭代：

• 從 Q 中選取 dist 最小的節點 u = e (dist[e] = 23)。
• 將 e 加入 S。S = {a, b, c, e}。
• 更新 e 的鄰居：
  • f: alt = dist[e] + weight(e, f) = 23 + 2 = 25。

此題要求找出圖中任意兩節點之間最長的「簡單路徑」（simple path），其中路徑長度僅計算邊的數量，不考慮權重。簡單路徑是指不包含重複節點的路徑。

問題分析：
在一個無權圖中尋找最長的簡單路徑是一個 NP-hard 問題。對於任意圖，沒有已知的多項式時間演算法可以解決它。然而，對於問題中給出的特定圖（Figure 1），我們可以透過窮舉或仔細分析來找到答案。

圖的結構分析 (Figure 1)：
圖中有節點 {a, b, c, d, e, f, i}。
邊（無權）：

• a - b
• a - c
• b - c
• b - d
• c - d
• c - e
• d - e
• d - f
• e - f
• e - i
• f - i

尋找最長簡單路徑的策略：
由於圖的節點數量不多（7 個），我們可以嘗試從不同的節點開始，進行深度優先搜尋 (DFS)，並記錄遇到的最長路徑。最長簡單路徑的終點可能是圖中的任何兩個節點。

嘗試窮舉或分析：

一個簡單路徑最多可以包含圖中所有的節點，即長度為 $V-1$（邊的數量）。在這個圖中有 7 個節點，所以最長簡單路徑的長度最多為 $7-1=6$。

我們需要檢查是否存在長度為 6 的簡單路徑。這意味著路徑需要經過所有 7 個節點，且不重複。

讓我們試著構建一個可能的長路徑：
從某個節點出發，盡量選擇分支較多的節點。

• 從 'a' 開始：

  • a -> b -> c -> d -> e -> f -> i (長度 6) - 這是個簡單路徑，經過所有節點。
  • a -> c -> e -> i (長度 3)
  • a -> c -> d -> f -> i (長度 4)

• 從 'i' 開始：

  • i -> e -> c -> a -> b -> d (長度 5)
  • i -> f -> d -> b -> a -> c (長度 5)
  • i -> e -> f -> d -> b -> a (長度 5)

讓我們仔細檢查 a -> b -> c -> d -> e -> f -> i 這條路徑：

• a -> b (✅)
• b -> c (✅)
• c -> d (✅)
• d -> e (✅)
• e -> f (✅)
• f -> i (✅)
  這是一條有效的簡單路徑，長度為 6。

是否存在更長的簡單路徑？
由於圖中只有 7 個節點，最長的簡單路徑最多只能經過這 7 個節點各一次，所以邊的數量最多是 $7-1=6$。我們已經找到一條長度為 6 的簡單路徑。因此，這就是最長的簡單路徑。

函數實現思路 (Pseudo-code)：
雖然題目要求寫函數，但實際上對於一個給定的圖，找到最長簡單路徑的函數實現是複雜的。一個基本思路是：

這是一道涵蓋了數據科學多個重要概念的題目，包含模型、數據結構、處理數據問題以及時間序列數據劃分。

6.1. 什麼是邏輯迴歸 (Logistic Regression)？

邏輯迴歸是一種廣泛用於分類問題的統計模型。儘管名稱中包含「迴歸」，但它主要用於預測一個二元結果（例如，是/否、成功/失敗、患病/未患病）。

• 核心思想： 邏輯迴歸透過一個邏輯函數（通常是 sigmoid 函數）將線性模型的輸出轉換為概率。
  假設一個線性模型為：$z = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n$
  邏輯迴歸模型預測目標變數為 1 的概率為：
  $P(Y=1|X) = \sigma(z) = \frac{1}{1 + e^{-z}} = \frac{1}{1 + e^{-(\beta_0 + \beta_1 x_1 + ... + \beta_n x_n)}}$
  其中 $Y$ 是目標變數，$X$ 是特徵向量，$\beta$ 是模型的係數。
• 決策邊界： 透過設定一個閾值（通常是 0.5），我們可以將預測概率劃分為兩個類別。例如，如果 $P(Y=1|X) > 0.5$，則預測為類別 1；否則預測為類別 0。
• 應用： 常用於二元分類問題，也可以擴展到多元分類（如 Softmax Regression）。
• 優點： 模型簡單、計算效率高、易於解釋，並且能提供預測的概率。

【答案】
邏輯迴歸是一種用於分類問題的統計模型，它使用 sigmoid 函數將線性模型的輸出轉換為預測某事件發生的概率，常用於二元分類。

6.2. 如何在數據結構中儲存圖的結構？請給出至少兩種解決方案。

圖是一種表示對象之間關係的數據結構。常見的儲存方法有：

1. 鄰接矩陣 (Adjacency Matrix)：

   • 描述： 使用一個 $V \times V$ 的二維矩陣（其中 $V$ 是圖中的頂點數量）來表示圖。矩陣的元素 $M[i][j]$ 表示頂點 $i$ 和頂點 $j$ 之間是否存在邊。
   • 表示方式：
     • 無權圖：如果存在邊，則 $M[i][j] = 1$，否則為 0。
     • 有權圖：如果存在邊，則 $M[i][j]$ 為該邊的權重，否則為 0 或 $\infty$（表示無邊）。
   • 優點： 檢查兩個節點之間是否存在邊非常快速，時間複雜度為 $O(1)$。
   • 缺點： 佔用空間較大，對於稀疏圖（邊數遠小於 $V^2$）來說，空間複雜度為 $O(V^2)$，效率不高。插入和刪除節點也比較麻煩。
   • 適用場景： 稠密圖。

2. 鄰接列表 (Adjacency List)：

   • 描述： 使用一個數組或列表，其中每個索引對應圖中的一個頂點。該索引處儲存一個列表，包含所有與該頂點相鄰的頂點。
   • 表示方式：
     • 無權圖：adj_list[i] 儲存與頂點 $i$ 相鄰的所有頂點的列表。
     • 有權圖：adj_list[i] 儲存一個包含 (neighbor, weight) 對的列表。
   • 優點： 對於稀疏圖非常高效，空間複雜度為 $O(V + E)$，其中 $E$ 是邊的數量。添加邊的操作相對簡單。
   • 缺點： 檢查兩個節點之間是否存在邊的時間複雜度為 $O(\text{degree}(v))$，其中 $\text{degree}(v)$ 是節點 $v$ 的度。
   • 適用場景： 稀疏圖，這是圖結構最常用的表示方法。

其他可能方案（簡述）：

• 邊列表 (Edge List)： 儲存所有邊的列表，每條邊包含起點、終點和權重（如果適用）。空間複雜度為 $O(E)$。適用於某些圖演算法，如 Kruskal's 演算法。

【答案】
圖結構可透過鄰接矩陣（$V \times V$ 矩陣，表示節點間連通性）或鄰接列表（陣列/列表，每個元素儲存與該節點相鄰節點的列表）來儲存。

6.3. 對於類別不平衡問題（例如，某些類別的樣本相對較少），請給出解決該問題的方案。

類別不平衡（Class Imbalance）是監督學習中常見的問題，當數據集中某些類別的樣本數量遠少於其他類別時，模型可能會偏向於預測樣本數較多的類別，而忽略樣本數較少的類別，導致在少數類別上的預測性能較差。

解決方案：

1. 重採樣技術 (Resampling Techniques)：
   • 過採樣 (Oversampling)： 增加少數類別的樣本數量。
     • 隨機過採樣： 簡單地複製少數類別的樣本。
     • SMOTE (Synthetic Minority Over-sampling Technique)： 透過插值的方法，為少數類別生成新的合成樣本。
   • 欠採樣 (Undersampling)： 減少多數類別的樣本數量。
     • 隨機欠採樣： 隨機刪除多數類別的樣本。
     • Tomek Links： 移除多數類別和少數類別之間相鄰的樣本對，以清晰化決策邊界。

這題涵蓋了數據處理、機器學習模型、演算法和數據科學基礎概念的多個方面。

7.1. 缺失數據的填補方法只有刪除。 (True/False)

• 答案： False
• 解釋： 刪除（Deletion）只是處理缺失數據的一種方法，稱為「刪失法」（Listwise Deletion 或 Pairwise Deletion）。然而，這會導致數據損失，可能引入偏差。更常見且有效的處理缺失數據的方法包括：
  • 平均值/中位數/眾數填補 (Mean/Median/Mode Imputation)： 用該特徵的平均值、中位數或眾數來填補缺失值。
  • 回歸填補 (Regression Imputation)： 使用其他特徵來預測缺失值。
  • 多重填補 (Multiple Imputation)： 生成多個填補值，並在每個數據集上建立模型，最後綜合結果。
  • 模型預測填補： 使用更複雜的模型（如 KNN、決策樹）來預測缺失值。
  • 專門的插值方法： 如時間序列中的線性插值、多項式插值等。

【正確答案】
False。除了刪除，還有平均值/中位數/眾數填補、回歸填補、多重填補等方法。

7.2. 離群值檢測通常用於移除缺失值。 (True/False)

• 答案： False
• 解釋： 離群值（Outlier）是指數據集中與其他數據點顯著不同的數據點。缺失值（Missing Value）是指數據點的某些屬性值是空的。
  • 離群值檢測 的目的是識別和處理那些可能影響模型訓練的極端值。處理方式可能是移除、轉換或保留。
  • 缺失值處理 的目的是填補或移除數據中缺失的部分。
    這兩者是不同的問題，雖然有時離群值可能會被誤認為是缺失值（反之亦然），但它們的處理方法和目的不同。離群值檢測的目的是處理「異常但存在」的值，而缺失值處理的目的是處理「不存在」的值。

【正確答案】
False。離群值檢測用於識別和處理極端值，而缺失值處理用於填補或移除數據中的空白。

7.3. 過擬合問題會導致訓練階段的性能下降，這是眾所周知的。 (True/False)

• 答案： False
• 解釋： 過擬合（Overfitting）是指模型在訓練數據上表現得非常好，但對未見過的測試數據表現較差。
  • 在訓練階段，過擬合的模型通常會表現極佳，其訓練誤差非常低，甚至接近於零，因為模型過度學習了訓練數據中的雜訊和細節。
  • 性能下降（Performance Degradation）發生在測試階段或驗證階段，因為模型無法泛化到新的、未見過的數據。

【正確答案】
False。過擬合會導致模型在測試階段的性能下降，但在訓練階段的性能通常會非常好。

7.4. 決策樹可以被視為一個可解釋的分類器/迴歸器。 (True/False)

• 答案： True
• 解釋： 決策樹（Decision Tree）是一種非常直觀且易於理解的機器學習模型。
  • 結構： 它由一系列的決策節點、分支和葉節點組成。每個決策節點代表一個特徵的測試，每個分支代表測試的結果，而葉節點則代表最終的預測類別或數值。
  • 可解釋性： 決策路徑可以被清晰地描述為一系列的「如果...那麼...」規則，這使得決策樹的預測過程非常容易被人類理解。例如，「如果特徵 A > 5 且特徵 B = 'X'，則預測為類別 1」。

【正確答案】
True。決策樹的結構（節點、分支、葉節點）和決策路徑可以清晰地展示預測邏輯，使其成為一個可解釋的模型。

7.5. 所有類別數據都應該轉換為 one-hot 編碼形式，以便用於決策樹。 (True/False)

• 答案： False
• 解釋： 雖然 One-Hot Encoding 是處理類別特徵的一種常用方法，但對於決策樹來說，並非總是必需的，也可能不是最佳方法。
  • 決策樹的處理能力： 決策樹可以自然地處理類別特徵。在決策節點，決策樹可以透過尋找最佳的類別分裂點來進行分裂，而不需要將其轉換為數值。
  • One-Hot Encoding 的缺點：
    • 增加維度： 對於具有很多類別的特徵（高基數特徵），One-Hot Encoding 會導致維度爆炸，這會增加計算複雜度和記憶體消耗，並可能導致稀疏數據問題，有時反而會降低決策樹的性能。
    • 引入假定： One-Hot Encoding 會引入模型對這些新數值特徵的順序假定（儘管決策樹通常不會受到這種順序假定的嚴重影響）。
  • 決策樹的替代處理方式： 許多決策樹實現（如 scikit-learn 的 DecisionTreeClassifier）可以直接接受類別特徵（通常需要將其轉換為整數編碼，或直接傳遞 Pandas 的 CategoricalDtype）。它們會自動尋找最佳的分裂方式，例如基於資訊增益或基尼係數。

這題考驗對 Python 閉包（Closure）概念的理解。

什麼是閉包 (Closure)？

在 Python 中，閉包是指一個內部函數，它記住了它被創建時所在的**外部函數的作用域（scope）**中的變數，即使外部函數已經執行完畢並返回，內部函數仍然可以訪問和操作這些變數。

閉包的構成條件：

1. 嵌套函數： 必須有一個外部函數和一個在其內部定義的函數。
2. 變數引用： 內部函數必須引用外部函數作用域中的變數。
3. 外部函數返回內部函數： 外部函數必須返回這個內部函數。

關鍵點：

• 「記憶」外部變數： 閉包的核心在於它「記住」了外部函數的變數。這些變數並非全局變數，也不是通過參數傳遞給內部函數的，而是「捕獲」自外部函數的作用域。
• 延遲綁定 (Late Binding)： 閉包中的變數綁定是延遲的。這意味著，當你調用閉包時，它才會去查找變數的當前值。這與在外部函數執行時就確定變數值不同。
• 實現數據隱藏和狀態保持： 閉包常被用來實現數據隱藏（類似於私有變數）和狀態保持。

範例：

考慮一個創建計數器的例子：

def make_counter():
    count = 0  # 這是外部函數作用域中的變數

    def increment():
        nonlocal count  # 聲明我們要修改外部函數的 count 變數
        count += 1
        return count
    
    return increment # 返回內部函數

# 創建一個計數器實例
counter1 = make_counter() 

# 調用計數器
print(counter1()) # 輸出: 1
print(counter1()) # 輸出: 2

# 創建另一個獨立的計數器實例
counter2 = make_counter()
print(counter2()) # 輸出: 1 (與 counter1 無關)

在這個例子中：

• make_counter 是外部函數。
• increment 是內部函數。
• count 是外部函數作用域中的變數，被 increment 引用。
• make_counter 返回 increment 函數。

當我們調用 counter1 = make_counter() 時，make_counter 執行並返回 increment 函數。此時，counter1 就持有了一個閉包，它「記住」了 count 的值（初始為 0）。