資料探勘技術　申論題歷屆試題與參考架構

假設你在警檢調或司法機關，原來委外建置的關聯式資料庫有設計瑕疵：有些表格候選鍵（Candidate Key）沒有被識別、有些表格沒有達成第三正規化。請針對下列三個工作：「建立資料倉儲」、「操作 OLAP（線上分析處理）」、「進行資料探勘」 ，分別至少舉 2 例來說明會造成什麼問題？你可自行假設資料庫的表格、欄位、設計瑕疵狀況。（20 分）

（20 分）

假設某一個判斷是否為詐騙電子郵件的模型，在全部 10000 筆資料中，「True Positive 真的為詐騙、且模型判斷為詐騙」有 TP 筆、「False Negative 真的為詐騙、但模型判斷為沒有詐騙」有 FN 筆、 「False Positive不是詐騙、但模型判斷為詐騙」有 FP 筆、 「True Negative 不是詐騙、且模型也判斷不是詐騙」有 TN 筆，其數值各如下：TP=2000 FP=150 FN=2100 TN=5750

（一）判斷模型效力好壞有多個指標，請對下面五個指標，先列出公式，再計算出數值至小數 2 位：準確率（Accuracy） 、精確率（Precision）、召回率（Recall）、特異度（Specificity）、F1 分數。（15 分）

（二）請以上述五個指標綜合判定該模型的好壞，並說明理由。 （3 分）

（三）在警檢調、司法做資料探勘，不能只依賴「準確率」 、「精確率」 、「召回率」、「特異度」中單一指標，否則可能因樣本分布、探勘門檻設定等造成模型整體效力其實不佳的狀況。請假設四個情境來分別說明若只看該單一指標的問題。（12 分）

（30 分）

若你是司法人員，想找出慣竊之人格特徵與行為模式。請規劃一個完整的資料探勘專案流程，說明你會收集那些資料、希望找出的各種規則、對該規則使用那些技術，以及最後預期能達成什麼樣的施政幫助。（25 分）

（25 分）

若您是司法人員，想委外資訊廠商，找出慣竊之人格特徵與行為模式，請列出招標需求規範（RFP）應特別著重的核心規範要點。（25 分）

（25 分）

假設關聯資料庫的表格 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 分）

（25 分）

假設有個資料庫記錄了對全國某種受刑人數萬人做過的某次心理測驗，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 分）

（25 分）

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

（25 分）

歡樂暢飲公司是一間行銷全世界的茶飲料公司，它的資料庫至少記錄了2000-2018 年的 30 種產品每季在全世界各地區的銷售數量與金額。請以此為背景來說明資料倉儲的下列一些概念：

（一）何謂主題導向（Subject-Oriented）？此處的主題是什麼？（3 分）

（二）在為它建立模型時，有所謂的事實表格、維度表格，請舉例說明。（3 分）

（三） 資 料 倉 儲 操 作 上 有 「 向 上 擷 取 」（ Roll-Up ） 及 「 向 下 探 究 」（Drill-Down）功能，這與維度設計有何關係？（3 分）

（四）請依此背景，設計出星型模式（Star Schema）（8 分）

（五）請依此背景，設計出雪花模式（Snowflake Schema）（8 分）

（25 分）

一犯罪資料庫記錄前科犯所曾經犯過的不同刑案，資料如下：共 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

（25 分）

分類演算法（classification algorithm）是資料探勘中重要的分析方法。針對以下的訓練資料集：9 筆資料 x1, x2, . . . , x9，每筆資料有 4 個屬性（A1, A2, A3, Class），其中A1、A2、A3 為特徵屬性（feature），Class 為類別屬性。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 3 Y C2 x6 B 3 N C2 x7 B 2 N C2 x8 B 3 Y C2 x9 S 2 N C2現今希望用決策分類樹（decision tree）來學習該資料集的分類規則，其中分類樹內部節點（internal node）屬性以選擇最小的 Gini(A)值來決定分支，Gini(A)函數定義如下：C Gini ( A) = ∑ p (t ) ⋅ [1 − ∑ ( p (i | t )) 2 ] , t∈ A i =1 t 為屬性 A 中的某特定值，p(t)是屬性 A 中值為 t 所出現的資料比率，p(i|t)是在屬性值為 t 時，資料集隸屬於類別 i 的比率，C 為所有類別的個數。分支的停止條件則是當節點資料完全隸屬同一類別時停止，該樹葉節點（leaf node）即是分類結果。請以此訓練資料集和 Gini(A)屬性決策條件要求，產生一決策分類樹（decision tree），答案中請清楚表達該決策樹的每一內部節點的屬性、分支條件值和該決策點的Gini(A)值，以及葉節點的分類結果。（25 分）107年公務人員特種考試警察人員、一般警察人員考試及 全一張107年特 種 考 試 交 通 事 業 鐵 路 人 員 考 試 試 題 （背面）考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員犯罪分析組資料倉儲【Data Warehouse】、資料探勘【Data Mining】）

（25 分）

某公路交通事故資料庫系統的部分相關關聯式表格名稱、欄位屬性名稱和資料如下：ACC [事故紀錄]事故編號 發生日期 發生時間 道路編號 道路位置 事故類別 受傷人數 死亡人數ACC_ID DATE TIME R_ID R_KM ACC_C H_NUM D_NUM 2100001 02/01/2016 05：13 T9 152 A1 4 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 5 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 6 1 2100013 12/12/2016 05：58 T3 202 A1 1 3

（一）請寫出 SQL 語法查詢（query）：列出曾發生單件事故中有受傷 3 人（含）以上或有死亡人數的道路編號。（10 分）

（二）請寫出 SQL 語法查詢（query）：列出各個道路編號的受傷人數與死亡人數統計數據。（10 分）

（20 分）

承續上題，交通管理單位高層決策希望能夠從 ACC 資料庫中，建立線上分析處理（On-line analytical processing; OLAP）系統，分析各道路容易出現重大事故的路段與時間，以利掌握並研擬改善措施。為了達成目標，首先必須構建資料倉儲（data warehouse）。假設所要分析的主要目標資料項包括：事故件數（ACC_NUM）、受傷人數（H_NUM）和死亡人數（D_NUM） ；分析的維度包括有：事故日期、事故時段和道路種類、事故類別等 4 個維度（dimension） ，分述如下：

⑴ 事故日期（ACC_DATE） ：本維度中分析發生日期（DATE） ，包含有日期的概念階層（concept hierarchy）；如下：年（year）> 季（quarter）> 月（month）> 日（day）

⑵ 事故時段（ACC_TIME） ：本維度分析發生時間（TIME） ，包含上下午（Half_day）與尖、離峰時段（Rush_hour）上午：0 時至 12 時，下午：12 時至 24 時；尖峰：7 時至 9 時及 17 時至 19 時；其餘為離峰。

⑶道路種類（ROAD）：本維度分析道路編號（R_ID），並將道路類別（Road_class）分為：國道（N）、省道（T）、縣道（C）

⑷事故類別（ACC_C） ：本維度主要依事故類別（ACC_C） ，A1、A2、A3 分類，無額外分析需求。請應用資料倉儲模型（data warehouse model）為此 OLAP 系統設計資料倉儲綱要（schema），並據以回答以下問題：

（一）請您繪出所設計的資料倉儲綱要圖，並明確指出所包含的事實表格（fact table） 、維度表格（dimension table） ，以及相對的所有參考屬性（referential attribute）。（20 分）

（二）請對 ACC 資料表寫出 SQL 語法查詢（query）：計算出在分析維度（尖峰時段,事故類別）的各類事故件數。 （10 分）

（30 分）

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

（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 分）

（23 分）

假設 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年特種考試交通事業鐵路 代號：20250全一張考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員犯罪分析組儲【Data Warehouse】、資料探勘【Data Mining】）

（31 分）

假設 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 Any Undergraduate Graduate Freshman Sophomore Junior Senior M.A. M.S. Ph.D.圖 1 學籍狀態概念樹Any Science Art Computing Math Physics Chemistry Biology Statistics History Liberal-arts Music Literature圖 2 主修概念樹Any Taiwan Foreign Any北部 中部 南部 東部 離島 Japan Canada Average Good Excellent溫哥華市馬公市桃園市基隆市 高雄市 臺東市 東京市 [3.0 - 3.4] [2.0 - 2.9] [3.5 - 4.0]新北市臺北市 臺南市 花蓮市 大阪市 圖 4 平均成績概念樹圖 3 出生地概念樹

（21 分）

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

（20 分）

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

（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}

（20 分）

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

（20 分）

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

（20 分）

有關於社會網路分析（Social Network Analysis），試回答以下問題：

（一） 請 說 明 社 會 網 路 分 析 中 的 連 結 預 測 （ link prediction ） 、 具 影 響 力 節 點 探 勘（influential nodes mining）及社群探勘（community detection）的技術內涵分別為何？（15 分）

（二）請說明上述三種社會網路分析技術於犯罪偵防的可能應用為何？（10 分）

（25 分）

有關於巨量資料探勘（big data mining），試回答以下問題：

（一）請說明相較於傳統資料探勘（traditional data mining），巨量資料探勘之所以可以產生高於傳統資料探勘效益的主要理由為何？（7 分）

（二）請說明傳統資料探勘方法無法進行巨量資料探勘的主要原因為何？（8 分）

（三）請說明巨量資料探勘主要面臨的挑戰為何？（10 分）

（25 分）

有關於分群（clustering），試回答以下問題：

（一）請說明分割式分群法（partition method）、階層式分群法（hierarchical method）及密集度為導向的分群法（density-based algorithm）所採用的分群原理分別為何？（15 分）

（二）請說明採用上述三種分群法，分別適合應用於解決何種類型的分群問題？（10 分）

（25 分）

有關於關聯式規則探勘（association rule mining），試回答以下問題：

（一）請說明關聯式規則探勘中的最小支持度（minimum support）與最小信心水準（minimum confidence）的意義分別為何？（7 分）

（二）請舉例說明在何種情況下滿足最小支持度（minimum support）與最小信心水準（minimum confidence）的關聯式規則不一定保證具有意義？（8 分）

（三）請說明改採用具有分析探勘項目之間關聯度（correlation）的增益值（lift）測度，取代最小信心水準探勘關聯式規則的主要意義為何？（10 分）

（25 分）