110 經濟部聯招(台電、中油、台水、台糖)新進職員 統計資訊 國營事業聯招 (資料庫及資料探勘、程式設計)B 考古題詳解

核心觀念

本題考查 BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）的四項核心設計：

1. 適用的資料型態。
2. CF Tree（Clustering Feature Tree）節點所儲存的摘要資訊。
3. 透過資料壓縮與增量式處理降低記憶體需求。
4. 使用 $k$-means 後，以 Elbow Curve Method 決定群組數 $k$。

BIRCH 的重點不是直接保存所有原始資料，而是將相近資料點彙整成少量的群集特徵（Clustering Feature, CF），藉此建立階層式摘要結構。

---

（一）此方法適用何種資料型態？

解題方法

BIRCH 主要適用於：

• 數值型資料（numeric data）。
• 多維度數值資料。
• 可計算距離，尤其是採用歐幾里得距離的資料。

BIRCH 透過資料點的線性總和與平方和計算群集的質心、半徑與直徑，因此必須能進行數值運算。

對於一個群集 $C$，BIRCH 以：

$$CF=(N,LS,SS)$$

表示其特徵，其中：

• $N$：資料點數量。
• $LS$（Linear Sum）：各資料點向量的總和。
• $SS$（Squared Sum）：各資料點各維度平方和的總和。

若資料點為 $d$ 維向量，則：

$$LS=\sum_{i=1}^{N}x_i$$ $$SS=\sum_{i=1}^{N}x_i^2$$

因此，BIRCH 最適合可使用距離或相似度衡量的數值型資料。

作答重點

BIRCH 主要適用於大量的數值型、多維度資料，且資料點之間必須能計算距離；典型情況是使用歐幾里得距離的資料。

對純類別型資料，不能直接套用上述 CF 的數值摘要方式，必須先進行適當的數值化或改用適合類別資料的分群方法。

---

（二）Internal 節點除 pointer 之外儲存何種資料？

解題方法

BIRCH 使用 CF Tree。每一個 CF 代表一個子群集的摘要資料：

$$CF=(N,LS,SS)$$

其中：

• $N$：該子群集包含的資料點數量。
• $LS$：所有資料點的向量總和。
• $SS$：所有資料點平方後的總和。

在 internal node 中，每個 entry 通常包含：

1. 一個 CF 值，用來描述該子樹所涵蓋資料的群集特徵。
2. 一個指向子節點的 pointer。

題目已說明 pointer 不計，因此應回答 internal node 儲存該子樹的 CF 摘要資訊，即 $N$、$LS$、$SS$。

CF 可推導的資訊

由 CF 可計算該群集的質心：

$$\mu=\frac{LS}{N}$$

也可計算半徑或直徑等群集緊密程度資訊。例如，群集半徑可由群內資料點到質心的平均平方距離推導：

$$R=\sqrt{\frac{SS}{N}-\left(\frac{LS}{N}\right)^2}$$

因此，BIRCH 不必保留每一個原始資料點，只要保留 CF，即可進行後續的距離與群集判斷。

作答重點

Internal 節點除了子節點 pointer 外，儲存其子樹所代表群集的 CF（Clustering Feature），包括：

$$CF=(N,LS,SS)$$

即資料筆數、線性總和與平方和。

---

（三）如何處理大量資料，降低記憶體限制？

解題方法

BIRCH 採用「增量式掃描」與「資料壓縮摘要」機制。

資料點逐筆讀入時，先依據距離尋找 CF Tree 中最接近的子群集。若加入後仍符合指定的 Threshold，便將該資料點合併至既有 CF；若超過 Threshold，則建立新的 CF entry。

CF 合併具有可加性：

$$CF_1+CF_2=(N_1+N_2,\ LS_1+LS_2,\ SS_1+SS_2)$$

因此，許多原始資料點可以被壓縮成少數 CF entry，而不需要全部保存在記憶體中。

主要機制

1. 逐筆或分批讀取資料 不必一次將整個資料集載入記憶體。

2. 以 CF 摘要取代原始資料點 每一群相近資料只保留 $N$、$LS$、$SS$ 等統計資訊。

核心觀念

本題考查資料探勘中的「資料正規化（Normalization）」：將不同欄位的數值轉換到可比較的尺度，使歐幾里得距離不會被數值範圍較大的欄位主導。

對兩筆資料 $X=(x_1,x_2,\ldots,x_p)$ 與 $Y=(y_1,y_2,\ldots,y_p)$，歐幾里得距離為

$$d(X,Y)=\sqrt{\sum_{j=1}^{p}(x_j-y_j)^2}$$

若某欄位的數值範圍遠大於其他欄位，該欄位的差異經平方後會占據距離的大部分，使其他欄位的資訊被忽略。

---

（一）正規化之目的

正規化的主要目的，是將不同欄位的數值轉換至相近的尺度，使各欄位在距離計算、分群、分類及相似度分析中具有合理且公平的影響力。

正規化可避免下列問題：

1. 消除不同欄位間的量綱差異，例如年齡以「歲」表示、收入以「元」表示。
2. 避免數值範圍較大的欄位支配歐幾里得距離。
3. 提升分群、最近鄰分類及其他距離型演算法的分析效果。
4. 使資料更容易進行比較與後續模型訓練。

---

（二）常用的 3 種正規化方法

1. 最小值—最大值正規化（Min-Max Normalization）

將原始資料線性轉換至指定區間，最常見的是 $[0,1]$。

若原始資料為 $x$，該欄位的最小值與最大值分別為 $\min_A$ 與 $\max_A$，欲轉換至 $[L,U]$，公式為

$$x' = L+\frac{x-\min_A}{\max_A-\min_A}(U-L)$$

當指定區間為 $[0,1]$ 時，公式簡化為

$$x'=\frac{x-\min_A}{\max_A-\min_A}$$

其中：

• 原始最小值會轉換為 $0$；
• 原始最大值會轉換為 $1$；
• 其他數值依比例落在 $[0,1]$ 之間。

例如某欄位最小值為 $10$、最大值為 $50$，資料值為 $30$，則

$$x'=\frac{30-10}{50-10}=\frac{20}{40}=0.5$$

此方法保留原始資料的相對順序與比例關係，但容易受到極端值影響。若日後出現超過原最大值或低於原最小值的新資料，轉換結果可能超出原設定區間。

---

2. $z$ 分數正規化（Z-Score Normalization）

利用欄位的平均數與標準差進行轉換，使資料以平均數為中心，並以標準差作為尺度。

公式為

$$x'=\frac{x-\mu_A}{\sigma_A}$$

其中：

• $\mu_A$ 為欄位 $A$ 的平均數；
• $\sigma_A$ 為欄位 $A$ 的標準差。

若使用樣本資料計算標準差，也可寫成

核心觀念

本題考查關聯規則分析中的兩項指標：

1. 支持度（Support）

對規則 $X \rightarrow Y$ 而言：

$$\text{supp}(X \rightarrow Y) = \text{supp}(X \cup Y) = \frac{\text{同時包含 }X\cup Y\text{ 的交易筆數}}{\text{交易總筆數}}$$

本題共有 $6$ 筆交易，最小支持度為 $30\%$，因此規則至少須出現：

$$6\times 30\%=1.8$$

交易筆數必須為整數，故至少出現 $2$ 次。

2. 信心度（Confidence）

$$\text{conf}(X\rightarrow Y) = \frac{\text{supp}(X\cup Y)}{\text{supp}(X)} = \frac{\text{包含 }X\cup Y\text{ 的交易筆數}}{\text{包含 }X\text{ 的交易筆數}}$$

本題最小信心度為 $80\%$。

題目限定規則形式為「兩項商品 $\rightarrow$ 一項商品」，因此需檢查所有三項商品組合，再將其中兩項作為前件、另一項作為後件。

---

解題方法

先統計各商品組合的出現次數。三項商品組合至少須出現 $2$ 次，才能符合最小支持度。

符合支持度門檻的三項商品組合如下：

三項商品組合	出現交易	次數	支持度
$ABE$	T1、T5	2	$2/6=33.33\%$
$BDE$	T2、T5	2	$2/6=33.33\%$
$ADE$	T4、T5	2	$2/6=33.33\%$

其餘三項商品組合皆未達 $2$ 次，不符合最小支持度。

---

一、由 $ABE$ 產生的規則

相關交易為 T1、T5，因此：

• $AB$ 出現於 T1、T5，共 $2$ 次
• $AE$ 出現於 T1、T4、T5，共 $3$ 次
• $BE$ 出現於 T1、T2、T5，共 $3$ 次

$AB\rightarrow E$

$$\text{supp}(AB\rightarrow E)=\frac{2}{6}=33.33\%$$ $$\text{conf}(AB\rightarrow E)=\frac{2}{2}=100\%$$

支持度與信心度皆達門檻，成立。

$AE\rightarrow B$

$$\text{conf}(AE\rightarrow B)=\frac{2}{3}=66.67\%$$

未達 $80\%$，不成立。

$BE\rightarrow A$

$$\text{conf}(BE\rightarrow A)=\frac{2}{3}=66.67\%$$

未達 $80\%$，不成立。

---

二、由 $BDE$ 產生的規則

相關交易為 T2、T5，因此：

核心觀念

本題考查遞迴函式的設計，重點包括：

1. 設定適當的基底條件（Base Case）。
2. 找出目前問題與較小規模問題之間的遞迴關係。
3. 確保每次遞迴呼叫都使問題規模縮小，最後能回到基底條件。
4. 最大公因數使用歐幾里得演算法（Euclidean Algorithm）。

---

（一）細胞總數函式 CellNumber

解題方法

假設第 $0$ 個月開始時有 $1$ 個成年細胞，且沒有幼年細胞。

設：

• $A_n$：第 $n$ 個月的成年細胞數
• $Y_n$：第 $n$ 個月的幼年細胞數
• $C_n=A_n+Y_n$：第 $n$ 個月的細胞總數

每個月的變化如下：

• 成年細胞仍然存在，並且每個成年細胞產生 $2$ 個幼年細胞。
• 幼年細胞經過 $1$ 個月後變為成年細胞。

因此：

$$A_{n+1}=A_n+Y_n$$ $$Y_{n+1}=2A_n$$

細胞總數為：

$$C_{n+1}=A_{n+1}+Y_{n+1}$$

代入上式：

$$C_{n+1}=A_n+Y_n+2A_n$$ $$C_{n+1}=C_n+2A_n$$

又因為第 $n-1$ 個月的成年細胞，於第 $n$ 個月會變成幼年細胞；可整理得到：

$$C_n=C_{n-1}+2C_{n-2}$$

基底條件

第 $0$ 個月：

$$C_0=1$$

第 $1$ 個月：

• 原本的成年細胞仍為成年細胞 $1$ 個
• 產生幼年細胞 $2$ 個

所以：

$$C_1=3$$

遞迴程式

Function CellNumber(N)
 If N = 0 Then
 Return 1
 Else If N = 1 Then
 Return 3
 Else
 Return CellNumber(N - 1) + 2 * CellNumber(N - 2)
 End If
End Function

範例驗算

$$C_0=1$$ $$C_1=3$$ $$C_2=C_1+2C_0=3+2(1)=5$$ $$C_3=C_2+2C_1=5+2(3)=11$$

因此細胞總數依序為：

$$1,\ 3,\ 5,\ 11,\ 21,\ldots$$

解題技巧與常見陷阱

• 必須先明確設定第 $0$ 個月的初始細胞狀態。本解採「開始時有 $1$ 個成年細胞」的標準假設。
• 成年細胞不會消失，幼年細胞才會在下一個月轉為成年細胞。

核心觀念

本題考查「互斥鎖（mutex）」與「臨界區（critical section）」的使用。

同一服務的號碼變數會被多台取號機共同存取，因此「讀取目前號碼、更新下一個號碼」必須在鎖定狀態下完成，避免兩台取號機同時讀到相同號碼，造成重複發號。

臨界區的正確操作順序為：

1. 嘗試鎖定服務號碼變數。
2. 鎖定成功後取得目前號碼。
3. 將號碼加一並寫回。
4. 解鎖。
5. 回傳原本取得的號碼。

若鎖定失敗，累計失敗次數；當失敗次數超過輸入的上限時，回傳 $0$。

---

解題方法

設目前服務的號碼變數為 $n$。因為最小號碼為 $1$，第一次成功取號時應回傳 $1$，並將號碼變數更新為 $2$：

$$\text{回傳值}=n$$ $$\text{更新後的號碼變數}=n+1$$

鎖定成功後，get 與 set 必須連續執行，且在 unlock 前完成，這段程式就是臨界區。

int GetNumber(int serviceid, int maxFail)
{
 int failCount = 0;

 while (1)
 {
 if (lock(serviceid) == 1)
 {
 int number = get(serviceid);

 set(serviceid, number + 1);

 unlock(serviceid);

 return number;
 }

 failCount++;

 if (failCount > maxFail)
 {
 return 0;
 }

 sleep;
 }
}

流程說明如下：

• lock(serviceid) == 1：表示成功取得該服務號碼變數的鎖。
• get(serviceid)：讀出目前應發出的號碼。
• set(serviceid, number + 1)：將下一次應發出的號碼寫回。
• unlock(serviceid)：完成更新後立即解鎖，讓其他取號機可以使用。
• 每次鎖定失敗，failCount 加一。

核心觀念

本題考查「Queue 取資料」、「逐一搜尋」及「最小值選擇」：

1. 使用 getqueue 取得等待乘客的目標樓層。
2. 若 Queue 無資料，getqueue 回傳 999，此時不選擇任何電梯，回傳 0。
3. 電梯編號為 $1$ 到 $N$，逐一使用 getcurfloor(elevid) 取得目前樓層。
4. getcurfloor 回傳 999 表示該電梯不提供服務，必須跳過。
5. 可服務電梯與目標樓層的距離為：

$$\text{distance}=\left|\text{目前樓層}-\text{目標樓層}\right|$$

距離最小者即為應選擇的電梯。

由於樓層可能包含負值，例如地下 1 樓為 $0$、地下 2 樓為 $-1$，因此必須使用絕對值計算樓層距離。

---

解題方法

設：

• target：Queue 取出的目標樓層
• bestElev：目前找到的最佳電梯號碼
• bestDist：目前最小距離

處理步驟如下：

1. 呼叫 getqueue 取得目標樓層。
2. 若 target == 999，表示沒有等待資料，直接回傳 0。
3. 將 bestElev 設為 0，表示目前尚未找到可服務電梯。
4. 將 bestDist 設為最大整數。
5. 以迴圈檢查電梯 $1$ 到 $N$：

• 呼叫 getcurfloor(i)。
• 若回傳 999，跳過該電梯。
• 計算該電梯與目標樓層的距離。
• 若距離小於目前最小距離，更新最佳電梯。

6. 迴圈結束後回傳 bestElev。
7. 若所有電梯均不提供服務，bestElev 仍為 0，符合題目要求。

---

參考程式碼

#include <stdlib.h>
#include <limits.h>

int SelElev(int N)
{
 int target;
 int bestElev = 0;
 int bestDist = INT_MAX;
 int i;

 target = getqueue;

 /* Queue 無資料 */
 if (target == 999 || N <= 0)
 return 0;

 for (i = 1; i <= N; i++)
 {
 int curfloor;
 int distance;

 curfloor = getcurfloor(i);

 /* 電梯不提供服務 */
 if (curfloor == 999)
 continue;

 distance = abs(curfloor - target);

 if (distance < bestDist)
 {
 bestDist = distance;
 bestElev = i;
 }
 }

 return bestElev;
}

---

程式正確性說明

Queue 無資料