資料探勘技術考古題｜歷屆國考試題彙整

假設關聯資料庫的表格R（A,B,C,D,E,F）有六個屬性A,B,C,D,E,F，各 屬性均無多值（Multi-Value）現象，其功能相依（Functional Dependency） 有下列兩條： FD1：{A,B} → {C,D,E,F} FD2：C → B 請以屬性封閉性（Closure）的概念，找出R 的所有候選鍵（Candidate Key）（6 分） 請證明R 不滿足Boyce-Codd 正規化（BCNF）。（3 分） 請試圖將R 分割，並先找出你分割出來每一表格的所有候選鍵，再證 明分割出來的每一表格均滿足BCNF，且同時證明你的分割滿足 lossless（無損）join 特性。（12 分） 你是否會建議你上述的分割？為什麼？（4 分）

假設有個資料庫記錄了對全國某種受刑人數萬人做過的某次心理測驗， B、C、D、E、F 分別代表其具有某種行為傾向。以下P{α}代表受刑人有 α 行為傾向的機率，P{α,β}代表受刑人同時有α 與β 行為傾向的機率。 P{B}= 0.08, P{C}= 0.06, P{D}= 0.04, P{E}= 0.07, P{F}= 0.02, P{B,C}= 0.04, P{ B,D}= 0.04, P{B,E}= 0.06, P{B,F}= 0.02, P{C,D}= 0.04, P{C,E}= 0.04, P{C,F}= 0, P{D,E}= 0.02, P{D,F}= 0, P{E,F}= 0.2 我們欲進行關聯規則（Association Rule）的資料探勘： 請先解釋何謂支持度（Support）、信心度（Confidence）的概念。（6 分） 假設支持度最低門檻是0.05、信心度最低門檻是0.7，請指出上述那 些是Large-1、Large-2 的項目集合（Item-set）；並找出所有只包含2 個項目集合的強（Strong）關聯規則。（14 分） 在尋找關聯規則時，有個重要的反單調（Anti-monotonicity）特性可減 低運算成本，請先說明何謂此特性？再請以上述例子來說明應如何運 用此特性。（5 分）

假設我們對某種犯罪資料要進行研究，資料庫收集了4,000 筆個人的心 理、行為、參與社群等詳細資料，其中1,900 人實際有過該犯罪事實， 2,100 人則無該犯罪事實。使用兩種方法來做集群（Cluster）分析。α 方 法可分出1,400 位犯罪人，但其中100 位未有犯罪事實，但被錯誤歸為 此犯罪群；此外有600 位實際有過犯罪事實，卻未被歸為此群。β 方法 可分出1,600 位犯罪人，但其中200 位未有犯罪事實，但被錯誤歸為此 犯罪群；此外有500 位實際有過犯罪事實，卻未被歸為此群。請問應如 何評估此兩方法的優劣？你會建議選擇那個方法？為什麼？（25 分）

歡樂暢飲公司是一間行銷全世界的茶飲料公司，它的資料庫至少記錄了 2000-2018 年的30 種產品每季在全世界各地區的銷售數量與金額。請以 此為背景來說明資料倉儲的下列一些概念： 何謂主題導向（Subject-Oriented）？此處的主題是什麼？（3 分） 在為它建立模型時，有所謂的事實表格、維度表格，請舉例說明。 （3 分） 資料倉儲操作上有「向上擷取」（Roll-Up ）及「向下探究」 （Drill-Down）功能，這與維度設計有何關係？（3 分） 請依此背景，設計出星型模式（Star Schema）（8 分） 請依此背景，設計出雪花模式（Snowflake Schema）（8 分）

一犯罪資料庫記錄前科犯所曾經犯過的不同刑案，資料如下：共5 個欄位A、B、C、 D、E，有標1 者分別代表該前科犯曾經犯過該刑案。試使用關聯規則探勘（association rule mining）方法，找出此五種犯罪刑案任二種間具最高支持度（support）與信心度 （confidence）的前三條規則，並列出各規則的支持度和信心度的值。（25 分） （注意：1.支持度高者優先列出，相同支持度時，請依信心度排列；2.必須寫出探勘過程。） 前科犯 A（偷竊） B（恐嚇） C（搶劫） D（傷害） E（販毒） 001 1 1 1 002 1 1 003 1 1 1 004 1 1 1 1 005 1 006 1 1 1 007 1 1 008 1 1 1 009 1 010 1 1

分類演算法（classification algorithm）是資料探勘中重要的分析方法。針對以下的訓 練資料集：9 筆資料x1, x2, . . . , x9，每筆資料有4 個屬性（A1, A2, A3, Class），其中 A1、A2、A3 為特徵屬性（feature），Class 為類別屬性。 現今希望用決策分類樹（decision tree）來學習該資料集的分類規則，其中分類樹內部 節點（internal node）屬性以選擇最小的Gini(A)值來決定分支，Gini(A)函數定義如下： ID A1 A2 A3 Class x1 S 2 Y C1 x2 B 2 Y C1 x3 B 1 Y C1 x4 S 1 Y C1 x5 S

Y C2 x6 B 3 N C2 x7 B 2 N C2 x8 B 3 Y C2 x9 S 2 N C2 ,] )) | ( ( 1[ ) ( ) ( 2 1 t i p t p A Gini C i A t = ∈ ∑ − ⋅ ∑ = t 為屬性A 中的某特定值，p(t)是屬性A 中值為t 所出現的資料比率，p(i|t)是在屬性值 為t 時，資料集隸屬於類別i 的比率，C 為所有類別的個數。分支的停止條件則是當 節點資料完全隸屬同一類別時停止，該樹葉節點（leaf node）即是分類結果。 請以此訓練資料集和Gini(A)屬性決策條件要求，產生一決策分類樹（decision tree）， 答案中請清楚表達該決策樹的每一內部節點的屬性、分支條件值和該決策點的 Gini(A)值，以及葉節點的分類結果。（25 分） 107年公務人員特種考試警察人員、一般警察人員考試及 107年特種考試交通事業鐵路人員考試試題 全一張 （背面） 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員犯罪分析組 科 目： 資料探勘技術（包括資料庫管理與運用、線上交易處理【OLTP】、 資料倉儲【Data Warehouse】、資料探勘【Data Mining】）  的道路編號。（10 分） 故日期（AC 故時段（ACC_TIME）：本維度分析 ush_hour） 至24 時； 峰。 ） ⑷ 別（ACC_C），A1、A2、A3 分類，無 請應用資料倉儲模型（data warehouse model）為此OLAP 系統設計資料倉儲綱要 並明確指出所包含的事實表格（fact table）、維  三、某公路交通事故資料庫系統的部分相關關聯式表格名稱、欄位屬性名稱和資料如下： ACC [事故紀錄] 事故編號 發生日期 發生時間 道路編號 道路位置 事故類別 受傷人數 死亡人數 ACC_ID DATE TIME R_ID R_KM ACC_C H_NUM D_NUM 2100001 02/01/2016 05：13 T9 152 A1

1 2100002 02/12/2016 08：30 N1 178 A2 1 2 2100003 02/07/2016 18：01 N3 352 A3 0 0 2100004 05/16/2016 04：58 T9 152 A1

1 2100006 09/02/2016 05：32 N1 175 A3 0 0 2100007 09/12/2016 07：21 T3 202 A2 4 0 2100009 09/15/2016 07：55 N1 58 A2 2 0 2100010 10/01/2016 17：30 T1 312 A3 0 0 2100011 10/02/2016 01：32 C118 13 A2

1 2100013 12/12/2016 05：58 T3 202 A1 1 3 請寫出SQL 語法查詢（query）：列出曾發生單件事故中有受傷3 人（含）以上或 有死亡人數 請寫出SQL 語法查詢（query）：列出各個道路編號的受傷人數與死亡人數統計數據。 （10 分） 四、 承續上題，交通管理單位高層決策希望能夠從ACC 資料庫中，建立線上分析處理 （On-line analytical processing; OLAP）系統，分析各道路容易出現重大事故的路段與 時間，以利掌握並研擬改善措施。為了達成目標，首先必須構建資料倉儲（data warehouse）。假設所要分析的主要目標資料項包括：事故件數（ACC_NUM）、受傷 人數（H_NUM）和死亡人數（D_NUM）；分析的維度包括有：事故日期、事故時段 和道路種類、事故類別等4 個維度（dimension），分述如下： ⑴ 事 C_DATE）：本維度中分析發生日期（DATE），包含有日期的概念階 層（concept hierarchy）；如下： 年（year）> 季（quarter）> 月（month）> 日（day） ⑵ 事 發生時間（TIME），包含上下午（Half_day） 與尖、離峰時段（R 上午：0 時至12 時，下午：12 時 尖峰：7 時至9 時及17 時至19 時；其餘為離 ⑶道路種類（ROAD）：本維度分析道路編號（R_ID），並將道路類別（Road_class 分為：國道（N）、省道（T）、縣道（C） 事故類別（ACC_C）：本維度主要依事故類 額外分析需求。 （schema），並據以回答以下問題： 請您繪出所設計的資料倉儲綱要圖， 度表格（dimension table），以及相對的所有參考屬性（referential attribute）。（20 分） 請對ACC 資料表寫出SQL 語法查詢（query）：計算出在分析維度（尖峰時段,事 故類別）的各類事故件數。（10 分）

全球3C 公司是一間行銷全世界的歷史悠久的電腦、通訊與消費電子產品公司，它的 資料庫記錄了1950-2017 年的每個月200 種產品、在全世界各城市的銷售數量與金 額。請針對下列每一項的資料倉儲操作先給定義，再以上述背景為例來說明清楚該 操作內涵：⑴向下探究(drill-down)、⑵向上擷取(roll-up)、⑶切片(slice)、⑷切塊 （dice）、⑸轉軸（pivot）。（25 分）

假設關聯資料庫的表格R(A,B,C,D)有四個屬性A,B,C,D，其功能相依（Functional Dependency）為{A,B,D}€C 與{C,D}€B 請以屬性封閉性（Closure）的概念，找出R 的所有候選鍵（Candidate Key），請說 明清楚你使用功能相依的每一個推演步驟。（6 分） 請證明R 滿足第二正規化（2NF）或反證R 不滿足2NF。（3 分） 請證明R 滿足第三正規化（3NF）或反證R 不滿足3NF。（4 分） 請證明R 滿足Boyce-Codd 正規化（BCNF）或反證R 不滿足BCNF。（4 分） 若R 不滿足上述任一正規化，請將其切割，以求滿足之，你必須說明切割後的各 表格為何滿足你所聲稱的正規化。（6 分）

假設XYZ 公司的商品包含A、B、C、D、E、F、G 等多種，由其交易資料庫記錄， 我們得知表一的資料，假設我們要求的最小支持度（Support）為0.2、最小信心水準 （Confidence Level）為0.7。請找出所有包含一個商品的高頻項目集合（Frequent Item-sets），及其個別的支持度（7 分）、找出所有包含兩個商品的高頻項目集合， 及其個別的支持度（12 分）、找出所有包含三個商品的高頻項目集合，及其個別的 支持度（4 分）、列出至少兩條包含三個商品的強（Strong）關聯規則（Association Rules）及其個別規則的信心水準（8 分）。 表一 交易編號 銷售商品 A10001 A、B、C A10002 A、D A10003 D、E A10004 A、B、C A10005 C、F A10006 F A10007 D、F A10008 A、B、C、G A10009 E、G A10010 A、B 106年公務人員特種考試警察人員、一般警察 人員考試及106年特種考試交通事業鐵路 人員、退除役軍人轉任公務人員考試試題 全一張 （背面） 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員犯罪分析組 科 目： 資料探勘技術（包括資料庫管理與運用、線上交易處理【OLTP】、資料倉 儲【Data Warehouse】、資料探勘【Data Mining】）

假設U 大學之學生資料庫有下列表二的12 筆資料，其Status（學籍狀態）、Major （主修）、Birth_Place（出生地）、GPA（平均成績）四個屬性值之部分的概念樹個 別如圖1,2,3,4（註：圖4 的[2.0-2.9]表示其數值介於2.0 至2.9 間，也可為2.9 或2.0。 其餘[3.0-3.4] 等概念類推）。請利用這些資料，以概念樹導向方式，找出研究生 （Graduate）與大學生（Undergraduate）的區別規則（Discrimination Rule），注意： 請列出你的推導過程，且最後的規則應為最抽象、精簡，並加上機率。（21 分） 表二 Student_ID Status Major Birth_Place GPA 1001 M.A. History 臺北市 3.5 1002 Junior Math 新北市 3.7 1011 Junior Liberal_arts 桃園市 2.6 1012 M.S. Physics 臺南市 3.9 1021 Ph.D. Math 溫哥華市 3.3 1022 Sophomore Chemistry 高雄市 2.7 1031 Senior Computing 基隆市 3.5 1032 Ph.D. Biology 大阪市 3.4 1041 Sophomore Music 臺東市 3.0 1042 Ph.D. Computing 基隆市 3.8 1051 M.S. Statistics 東京市 3.2 1052 Freshman Literature 花蓮市 3.9 圖1 學籍狀態概念樹 Any Undergraduate Graduate Freshman Sophomore Junior Senior M.A. M.S. Ph.D. 圖4 平均成績概念樹 Any Average Good Excellent [2.0 - 2.9] [3.0 - 3.4] [3.5 - 4.0] Any 圖3 出生地概念樹 大 阪 市 Taiwan Foreign 北部 中部 南部 東部 離島 Japan Canada 臺 北 市 新 北 市 基 隆 市 桃 園 市 臺 南 市 高 雄 市 花 蓮 市 臺 東 市 馬 公 市 東 京 市 溫 哥 華 市 Any 圖2 主修概念樹 Art Science Computing Math Physics Chemistry Liberal-arts Biology Statistics History Music Literature

下列關聯表SJT 限制如下⑴每一門科目的每位學生只能被一位老師教，⑵每位老師 只能教一門科目（但一門科目可由多位老師教）。請問關聯表SJT 是否是廣義第三 正規化型式（BCNF）？並說明理由。假如不是，該如何切割（decompose）關聯表 SJT？切割後有何功能相依性（functional dependency）會遺失？（20 分） 學生（S） 科目（J） 老師（T） 張三 數學 陳老師 張三 物理 黃老師 李四 數學 陳老師 李四 物理 林老師

針對資料探勘（data mining），請描述其資料前置作業（data preprocessing）的主要 步驟。（20 分）

下列資料庫有四筆交易，如果最小支持度（minimum support）為60%、最小信心水 準（minimum confidence）為80%。請找出所有的頻繁項目集（frequent itemsets）和所 有符合下列型態的關聯法則（association rule），同時也要列出其支持度（support）和 信心水準（confidence）。（20 分） {項目1, 項目2} ⇒ 項目3 [支持度（support）, 信心水準（confidence）] TID 項目 T100 {K,A,D,B} T200 {D,A,C,E,B} T300 {C,A,B,E} T400 {B,A,D}

用下列分類資料呈現混淆矩陣表（confusion matrix），並算出精確率（precision）、 回想率（recall）及正確率（accuracy）。（20 分） 真實結果： 分類結果： 癌症樣本數目 200 預測真實癌症數目 150 非癌症樣本數目 800 預測真實非癌症數目 700

線上分析處理（OLAP）在高維度下會發生什麼問題？該如何解決？（20 分）

有關於社會網路分析（Social Network Analysis），試回答以下問題： 請說明社會網路分析中的連結預測（link prediction）、具影響力節點探勘 （influential nodes mining）及社群探勘（community detection）的技術內涵分別為 何？（15 分） 請說明上述三種社會網路分析技術於犯罪偵防的可能應用為何？（10 分）

有關於巨量資料探勘（big data mining），試回答以下問題： 請說明相較於傳統資料探勘（traditional data mining），巨量資料探勘之所以可以 產生高於傳統資料探勘效益的主要理由為何？（7 分） 請說明傳統資料探勘方法無法進行巨量資料探勘的主要原因為何？（8 分） 請說明巨量資料探勘主要面臨的挑戰為何？（10 分）

有關於分群（clustering），試回答以下問題： 請說明分割式分群法（partition method）、階層式分群法（hierarchical method） 及密集度為導向的分群法（density-based algorithm）所採用的分群原理分別為何？ （15 分） 請說明採用上述三種分群法，分別適合應用於解決何種類型的分群問題？（10 分）

有關於關聯式規則探勘（association rule mining），試回答以下問題： 請說明關聯式規則探勘中的最小支持度（minimum support）與最小信心水準 （minimum confidence）的意義分別為何？（7 分） 請舉例說明在何種情況下滿足最小支持度（minimum support）與最小信心水準 （minimum confidence）的關聯式規則不一定保證具有意義？（8 分） 請說明改採用具有分析探勘項目之間關聯度（correlation）的增益值（lift）測度， 取代最小信心水準探勘關聯式規則的主要意義為何？（10 分）

請就資料模型，查詢方式，查詢複雜度，資料變動頻率四方面比較資料倉 儲與傳統資料庫之差異。（20 分）

請回答以下有關關聯法則（Association Rule）分析之問題： 請舉例說明如何運用關聯法則於犯罪分析上。（10 分） 對於一資料集，我們進行關聯法則探勘後可能會產生非常多的關聯法則，有些關 聯法則雖內容不同但彼此之間可能具有潛在之高度重複性（redundancy）。請說 明如何分析找出具有潛在高度重複性之關聯法則。（15 分）

分群（Clustering）是資料探勘中常用到的一種技術，請回答下列問題： 請說明k-means 分群方法之運作方式。（15 分） 請說明如何評估一個分群結果之好壞。（10 分）

請回答以下有關分類（Classification）之問題： 決策樹（decision tree）與支持向量機（support vector machine,簡稱SVM）為分類 中常用之技術，請比較其優缺點。（15 分） 請說明如何利用K-fold 交叉驗證（K-fold cross validation）來驗證分類模型之有效 性。（15 分）

內政部警政署委託某一大學舉辦高階資料探勘研習班，研習過程中學員必須完成指 定作業並參加模擬測驗。研習通過與否以期末考成績為唯一標準。該班學員資料如 下表所列： 學號 （ID） 電話 （Phone） 語言 （Language） 完成所有作業 （Assignments） 模擬考成績 （Test） 通過期末考 （Exam） 0001 3231-5483 Java No 31 Yes 0002 3231-5482 Java No 20 No 0003 3231-4283 C++ Yes 35 Yes 0004 3231-4729 Python Yes 25 Yes 0005 3231-4214 Java Yes 39 No 0006 3231-4782 C++ No 29 No 0007 3231-4824 Java No 19 No 0008 3231-3845 Python Yes 32 Yes 請利用上表資料，設計並描述一個合理的K-NN classifier（K-Nearest Neighbor 分 類器）來預測學員是否會通過最終的期末考。（20 分） 若學員0009 的研習記錄如下所示，請用你所設計的K-NN classifier 預測該學員是 否有可能通過最後的期末考。請寫出相關計算與分析。（10 分） 學號 （ID） 電話 （Phone） 語言 （Language） 完成所有作業 （Assignments） 模擬考成績 （Test） 通過期末考 （Exam） 0009 3231-5423 C++ Yes 30 ?

下圖與圖分別是用K-means 分群（clustering）的結果。請分別分析為什麼分群 結果會不甚理想，並提出改進之道（但必須保有K-means 之精神）。 （10 分） （10 分） 圖 圖 99年公務人員特種考試警察人員考試及 99年特種考試交通事業鐵路人員考試試題 類 科： 刑事警察人員犯罪分析組 資料倉儲【Data Warehouse】、資料探勘【Data Mining】） 全一張 （背面）

請比較Naïve Bayesian, Support Vector machine, K-nearest neighbor 這三種常見的資料 分群方法（classification methods）。 那一種方法最容易修改成可以處理動態資料流（Dynamically changing data streams）？ 請敘明理由以及改變方法。（15 分） 那一種方法最不容易修改成可以處理動態資料流？請敘明理由。（10 分）

請說明一個兩群組的二維資料集（2-dimensional dataset）如何可以用一個線性SVM 完全正確的分群，但是卻無法用3-NN classifier 完全正確的分群。請舉例並以圖示 輔助說明。（25 分）

請定義relational database 裡的equi-join 及natural join 運算並舉例說明之。另請說明 hash-join algorithm 如何運作，以及為甚麼hash-join algorithm 只能用在處理equi-join 及 natural join 而不能處理一般join？（25 分）

請考慮frequent itemset 探勘。何謂Apriori principle？請描述Apriori algorithm 並指 出Apriori principle 如何用在Apriori algorithm 上。（25 分）

請舉例說明以下資料探勘技術：clustering，sequential pattern discovery， anomaly detection。（25 分）

請就以下frequent 3-sequences：<{1,2,3}>,<{1,2}{3}>,<{1}{2,3}>,<{1,2}{4}>,<{1,3}{4}>, <{1,2,4}>,<{2,3}{3}>,<{2,3}{4}>,<{2}{3}{3}>,<{2}{3}{4}>, （25 分） 列出使用GSP algorithm 在candidate generation 步驟後所產生的所有candidate 4-sequences。 列出使用GSP algorithm 在candidate pruning 步驟後所有被去除的candidate 4-sequences。

解釋名詞：(每子題5 分，共計30 分） 資料正規化（Data Normalization） 功能相依（Functional Dependency, FD） 解釋資料（Metadata） 實體關係圖（Entity-Relationship Diagram, ERD） 關聯法則支持度（Support） 下鑽（Drill-down）

試寫出類神經網路在資料探勘處理上的優缺點。（20 分）

一般資料探勘策略分為監督式與非監督式兩種，請回答下列各問題： 試簡要描述這兩種策略的主要特點。（10 分） 分類（Classification）是屬於何種策略？試指出它的相依變數資料型態與其屬性？ （10 分） 分群（Cluster）是屬於何種策略？試說明之。（10 分）

甲警察局在某一重要路口裝設一部彩色高解析度攝影機，專拍來往車輛的車牌，經 由影像擷取和車牌自動辨識系統、刑事警察局涉案車輛資料庫比對後，再利用資料 探勘技術──Model X（由類神經網路導得）與Model Y（由決策樹導得）兩種方 法，獲得如下的混淆矩陣表。 Model X 混淆矩陣表 Model Y 混淆矩陣表 Model X 計算 有涉案 計算 未涉案 Model Y 計算 有涉案 計算 未涉案 有涉案 10

有涉案

9 未涉案 25 60 未涉案 15 70 資料探勘建構模型用資料集範例總共多少部車輛？請寫出計算過程。（4 分） 那一個Model 被分類為未涉案車輛數較多？試說明之。（4 分） 試計算出Model X 的增益值（Lift）和支持度？（8 分） 那一種探勘方法（類神經網路或決策樹）所導得的模型較佳？試說明其理由？ （4 分）

請比較資料庫管理系統和資料倉儲的異同，並說明兩者間的關係。（20 分）

請說明網際網路資料探勘的類型及使用技術，並舉例說明不同類型網際網路資料探 勘相關的應用。（30 分）

請比較資料探勘技術和線上分析處理技術（On-Line Analysis Processing）的異同， 並說明兩者間的關係。（20 分）

請說明decision tree 與naïve Bayesian algorithm 兩種分類（classification）技術，並 比較其異同及適合處理的資料型態。（30 分）

在資料的管理中，索引是一個很重要的技術，為什麼？請列出一個你熟悉的索引結 構，並說明其用法。（20 分）

在資料探勘領域裏，有一種法則叫association rule，常是探勘的目標。請詳細說明 一種方法來探勘這種法則。另外，探勘這種法則需要兩個參數叫support 及 confidence，請解釋其涵義。（20 分）

請比較線上交易處理與線上分析處理之不同點。（20 分）

假設有一個資料倉儲包含time, doctor 及patient（病人）三個dimensions 及count 與 charge 兩個measures，其中charge 代表一個doctor 對一個patient 一次看病的收費。 （40 分） 請畫出一個schema 圖來表示這個資料倉儲。 從一個base cuboid [day, doctor, patient]，要執行什麼運算才能得到每個doctor 在 西元2000 年的年度總收費？