資料精簡 (Data Reduction).

Presentation on theme: "資料精簡 (Data Reduction)."— Presentation transcript:

1 資料精簡 (Data Reduction)

2 內容概要 簡介 資料精簡所包含之觀點 資料維度精簡(Dimension Reduction)
資料維度的評估 資料維度之組合策略 資料維度組合產生順序 資料記錄精簡(Record Reduction) 資料數值精簡(Value Reduction) 資料數值分離技術(Discretization Technique) 概念階層(Concept Hierarchy)

3 簡介(1) 資料精簡在資料探勘過程中所扮演的角色 狹義而言：主要應用在資料的前置處理階段 (pre-processing phase)
廣義而言：整個資料探勘過程都可以應用資料精簡的技術 前置處理階段(pre-processing phase) 探勘階段(mining phase) 後置處理階段(post-processing phase)

4 簡介(2) 前置處理階段之資料精簡 探勘階段之資料精簡 後置處理階段之資料精簡 從資料庫或資料倉儲中選取並建立使用者感興趣的資料集合
從資料集合中濾掉一些無關、偏差、重複的資料 探勘階段之資料精簡 探勘處理過程中去除不具代表性的中介資訊或法則，進而縮小探勘過程中所需花費的時間，減少產生重複、不重要的知識 後置處理階段之資料精簡 根據使用者的需求，由探勘結果中選取其感興趣和相關的知識，以及透過視覺化技術將知識作適當的歸納、整合，讓使用者更方便快速了解發展趨勢、市場偏向、消費者群集等等，以幫助其作決策

5 資料精簡之優點 提高知識的應用性與準確性，降低無效、錯誤資料之影響 挑選少量且具代表性的資料將大幅縮減資料探勘所需的時間
使資料探勘方法的可用性提高 助於高價值知識的取得與提升知識可讀性 降低儲存的成本

6 資料精簡之考量 如何選取代表性的資料 如何進行資料精簡

7 資料精簡所包含之觀點 資料精簡：資料維度精簡、資料記錄精簡與資料數值精簡 會員資料集合 資料維度 資料記錄 資料數值 會員編號
平均月收入 (千) 教育程度 年齡 會員等級 1 21 高中 30 低 2 24 大學 29 高 3 33 國中 28 4 20 32 5 42 31 6 38 35 7 37 36 資料記錄 資料數值

8 資料維度精簡(Dimension Reduction)
主要用來描述一件事物或事件 可利用年齡、教育程度、平均月收入和會員等級等資料維度來描述一個會員 資料維度精簡在企業決策上的應用 企業在決策支援與線上分析處理 (OLAP) 上，通常根據決策制定目標與應用目地的不同，會由日常線上交易處理(OLTP)資料集合中，挑選、轉換、乃至新增跟決策相關的資料維度來描述資料集合，並進行分析探勘

9 資料維度的評估(1) 利用一測量方法來挑選較好的資料維度
以會員資料表為例，“平均月收入” 應該比 “教育程度” 和 “年齡” 這兩個資料維度更適合做為 “會員等級” 評比的依據。(因為大部分收入低的會員，同常會員等級也會低) 讓電腦透過所設計的測量方法，自動地從資料集合中挑選較好的資料維度，幫助我們客觀解決資料維度精簡的問題

10 資料維度的評估(2) 測量方法 一致性測量法(consistency measurement)
關連性測量法(association measurement) 鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

11 資料維度的評估(3) 闡述測量方法的整合範例 其他待評估之資料維度 目標資料維度 會員編號 平均月收入 (千) 教育程度 年齡 會員等級 1
高中 2 低 大學 高 3 國中 4 5 6 7

12 測量方法 一致性測量法(consistency measurement) 關連性測量法(association measurement)
鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

13 一致性測量法(1) 概念 在使用者給定之標的資料維度下，一致性測量法的概念是利用最少的其他的資料維度，來描述資料表中每一筆記錄時，不會造成矛盾與衝突 任兩筆資料記錄可以透過所選擇的資料維度來描述，但不會產生不一致(inconsistency)的情況 範例 以”會員等級”是標的資料維度，則單以 “平均月收入” 此資料維度來描述原來的會員資料表，將使得資料記錄一與資料記錄二會產生不一致 同樣“平均月收入”等級一 但是會員一與會員二之會員等級卻不同

14 一致性測量法(2) “平均月收入” 對 “會員等級” 所產生的不一致數量 “教育程度” 對 “會員等級” 所產生的不一致數量
I (平均月收入, 會員等級) = I (平均月收入(1), 會員等級) + I (平均月收入(2), 會員等級) + I (平均月收入(3), 會員等級) = = 1 “教育程度” 對 “會員等級” 所產生的不一致數量 I (教育程度, 會員等級) = I (教育程度(大學), 會員等級) + I (教育程度(高中), 會員等級) + I (教育程度(國中), 會員等級) = = 2 “年齡” 對 “會員等級” 所產生的不一致數量 I (年齡, 會員等級) = I (年齡(1), 會員等級) + I (年齡(2), 會員等級) = = 2 “平均月收入”比其他資料維度重要

15 測量方法 一致性測量法(consistency measurement) 關連性測量法(association measurement)
鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

16 關連性測量法(1) 概念 測量資料維度之間的關連度(association degree)，當兩個資料維度A、B關連度愈高，由A中的資料數值可以判斷B中的資料數值的可能性愈高 透過關連性測量法，可以得知標的資料維度與資料表中其餘資料維度之關連度 範例 以”會員等級”是標的資料維度，則“平均月收入” 與其關連度可以概略計算為2/3 * 1 * 1 = 2/3 平均月收入等級一時，有2/3的機會可以由此判斷為會員等級低 平均月收入等級二時，有百分之百的機會判斷為會員等級高 平均月收入等級三時，有百分之百的機會判斷為會員等級低

17 關連性測量法(2) “平均月收入” 與 “會員等級” 的關連度 “教育程度” 與 “會員等級”的關連度 “年齡” 與 “會員等級”的關連度
R (平均月收入, 會員等級) = R (平均月收入(1), 會員等級) * R (平均月收入(2), 會員等級) * R (平均月收入(3), 會員等級) = 2/3 * 1 * 1 = 2/3 “教育程度” 與 “會員等級”的關連度 R (教育程度, 會員等級) = R (教育程度(大學), 會員等級) * R (教育程度(高中), 會員等級) * R (教育程度(國中), 會員等級) = 1 * 2/3 * 1/2 = 1/3 “年齡” 與 “會員等級”的關連度 R (年齡, 會員等級) = R (年齡(1), 會員等級) * R (年齡(2), 會員等級) = 1 * 3/5 = 3/5 “平均月收入”比其他資料維度重要

18 測量方法 一致性測量法(consistency measurement) 關連性測量法(association measurement)
鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

19 鑑別能力測量法(1) 概念 測量資料表中的其它資料維度，對於標的資料維度中的資料數值之鑑別能力(discriminating power) 鑑別能力愈高的資料維度對於標的資料維度愈具有重要性和影響力 範例 以”會員等級”是標的資料維度，則“平均月收入” 對其鑑別能力可以概略計算Min (2/3, 3/4) = 2/3 (Min此函數為取最小值) 會員等級低的資料記錄而言，其中有2/3的部分是可以由平均月收入等級一來決定 會員等級高的資料記錄而言，其中有3/4的部分是可以由平均月收入等級二來決定

20 鑑別能力測量法(2) “平均月收入” 對 “會員等級” 的鑑別能力 “教育程度” 對 “會員等級”的鑑別能力
D (會員等級, 平均月收入) = Min (D (會員等級(低), 平均月收入), D (會員等級(高), 平均月收入)) = Min(2/3, 3/4) = 2/3 “教育程度” 對 “會員等級”的鑑別能力 R (教育程度, 會員等級) = R (教育程度(大學), 會員等級) * R D (會員等級, 教育程度) = Min (D (會員等級(低), 教育程度), D (會員等級(高), 教育程度)) = Min (2/3, 2/4) = 1/2 “年齡” 對 “會員等級”的鑑別能力 D (會員等級, 年齡) = Min (D (會員等級(低), 年齡), D (會員等級(高), 年齡)) = Min (3/3, 2/4) = Min (3/3, 2/4) = 1/2 “平均月收入”比其他資料維度重要

21 測量方法 一致性測量法(consistency measurement) 關連性測量法(association measurement)
鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

22 資訊量測量法(1) 概念 測量資料集合中的其他資料維度對於標的資料維度的資訊獲利(information gain)，而所提供的資訊主要是用來幫助決定資料記錄中標的資料維度之資料數值 資料維度所提供的資訊量愈多者，其重要性愈高 範例 資料表中的資料記錄有3/7的機會是屬於會員等級低，有4/7的機會是屬於會員等級高 在考慮 “平均月收入” 此資料維度後，得到的資訊量為： 在平均月收入等級一的資訊提供下，有2/3的機會可以判斷為會員等級低 在平均月收入等級二和三的資訊提供下，更可以百分之百分別判斷為會員等級高和低

23 資訊量測量法(2) 未考慮其它資料維度下，標的資料維度的亂度值 在考慮資料維度組合X下，標的資料維度的亂度值
PD(ci) 表示標的資料維度中資料數值ci的機率，而d表示標的資料維度的值域 (domain) 大小 在考慮資料維度組合X下，標的資料維度的亂度值 PDj(ci) 表示當資料維度X為資料數值j時，標的資料維度中資料數值ci的機率，而d表示標的資料維度的值域大小 計算資料維度組合X對標的資料維度的資訊獲利 p表示資料維度組合X的值域大小 

24 資訊量測量法(3) 標的資料維度”會員等級”的亂度值 考慮 “平均月收入” 後 “會員等級” 的亂度值 = = 0.9852
= = PD (會員等級一) = 3/7和PD (會員等級二) = 4/7 考慮 “平均月收入” 後 “會員等級” 的亂度值 P (會員等級低|平均月收入等級一) = 2/3和P (會員等級高|平均月收入等級一) = 1/3 =  0.92 P (會員等級低|平均月收入等級二) = 0和P (會員等級高|平均月收入等級二) = 1 = = 0 P (會員等級低|平均月收入等級三) = 1和P (會員等級高|平均月收入等級三) = 0 ( )

25 資訊量測量法(4) 計算“平均月收入” 對 ”會員等級”的資訊獲利 = 0.9852 = 0.98520.394 = 0.591
當被考量的資料維度中的資料數值愈能將標的資料維度中的資料數值區分開來，則所求得之亂度值愈小；反之則愈大 考慮其它資料維度後，標的資料維度所表現出來的亂度值愈小者，所得到的資訊獲利愈大

26 測量方法 一致性測量法(consistency measurement) 關連性測量法(association measurement)
鑑別能力測量法(discrimination measurement) 資訊量測量法(information measurement) 準確性測量法 (accuracy measurement)

27 準確性測量法 概念 準確性測量法則根據所產生的知識的優劣來挑選適合的資料維度
準確性測量法將與探勘結果作緊密的結合，如果所挑選之資料維度其探勘後的結果對使用者愈有幫助，則其準確度愈高 資料維度挑選與產生 探勘過程 結果評估

28 資料維度之組合策略 資料維度組合策略的考量
利用上述的測量公式對所有可能的資料維度組合進行評估，並選擇其中最好之組合，計算時間與空間的需求將以指數的成長 因此，進行資料維度精簡時，使用者通常會設定一終止條件，例如：不一致的資料記錄數量小於2、資料維度組合之長度至多為五等等 完全列舉策略 (exhaustive strategy) 經驗法則列舉策略 (heuristic strategy) 隨機列舉策略 (random strategy)

29 資料維度之組合策略 完全列舉策略 (exhaustive strategy) 經驗法則列舉策略 (heuristic strategy)
隨機列舉策略 (random strategy)

30 完全列舉策略(1) 概念 根據選擇之測量法計算任一個維度、任兩個維度、…、依此類推至所有可能之資料維度組合，最後挑選測量值最高的資料組合 優缺點 優點：可以保證能在所有可能之挑選組合中，找到最佳 (測量值最高) 的組合 缺點：當資料維度數量多時，完全列舉策略將不切實際

31 完全列舉策略(2) 所有可能資料維度組合都需考慮

32 資料維度之組合策略 完全列舉策略 (exhaustive strategy) 經驗法則列舉策略 (heuristic strategy)
隨機列舉策略 (random strategy)

33 經驗法則列舉策略(1) 概念 優缺點 經驗法則列舉策略是一種貪婪式方法 (greedy approach)，只關注於眼前最好的選擇
在運作上，根據選擇之測量法，從單一資料維度中挑選出最好的維度出來；依此維度為基礎，從其餘未挑選之任一資料維度，產生可能之兩個資料維度之組合；以此類推，直到滿足使用者設定之終止條件為止 優缺點 優點：執行上較有效率 缺點：最後所挑選之資料維度組合並不保證是最佳的

34 經驗法則列舉策略(2) 以 “平均月收入” 為基礎之資料維度組合

35 資料維度之組合策略 完全列舉策略 (exhaustive strategy) 經驗法則列舉策略 (heuristic strategy)
隨機列舉策略 (random strategy)

36 隨機列舉策略 概念 優缺點 隨機列舉策略則以單一資料維度為種子 (seed)，隨機產生可能之資料維度組合
或以目前所產生之資料維度為基礎，隨機進行加入其他資料維度或去除舊有的資料維度，而加入或去除之維度數量也可以是隨機決定的 優缺點 優點：執行上有效率，可能可以跳脫區域最佳解(local optimal) 缺點：無法保證挑選結果的品質

37 資料維度組合產生順序(1) 資料維度組合產生的考量 漸進式挑選法(sequential forward generation)
在尋找符合終止條件或最佳之資料維度組合時，應由較短的資料維度組合進行評核，還是由較長的資料維度組合進行評核 漸進式挑選法(sequential forward generation) 漸進式刪減法(sequential backward generation) 混合法(bidirectional generation) 隨機選取法(randomized generation)

38 資料維度組合產生順序(2) 假設{“平均月收入”, “年齡”}為測量值最高、最佳之資料維度組合，配合完全列舉策略，以下將探討四種資料維度組合產生順序

39 資料維度組合產生順序 漸進式挑選法(sequential forward generation)
漸進式刪減法(sequential backward generation) 混合法(bidirectional generation) 隨機選取法(randomized generation)

40 漸進式挑選法 概念 由晶格下方 { } 往晶格上方，每次多考慮一個資料維度
根據選擇之測量法計算晶格第一層之單一資料維度 {“平均月收入”}、{“教育程度”} 與 {“年齡”}，並挑選其中最好的資料維度，假設為 {“平均月收入”} 針對晶格第二層之成對的資料維度 {“平均月收入”, “教育程度”}、{“平均月收入”, “年齡”} 與 {“教育程度”, “年齡”} 分別計算其測量值，並挑選其中最好的 {“平均月收入”, “年齡”} 測量值 假設 {“平均月收入”, “年齡”} 的測量值優於 {“平均月收入”}，因此{“平均月收入”, “年齡”} 取代 {“平均月收入”} 成為最佳之資料維度組合 以此類推，進行晶格第三層的處理

41 資料維度組合產生順序 漸進式挑選法(sequential forward generation)
漸進式刪減法(sequential backward generation) 混合法(bidirectional generation) 隨機選取法(randomized generation)

42 漸進式刪減法 概念 由晶格上方 {“平均月收入”, “教育程度”, “年齡”} 往晶格下方，每次少考慮一個資料維度
計算精簡任一資料維度後的可能組合 {“平均月收入”, “教育程度”}、{“平均月收入”, “年齡”} 和 {“教育程度”, “年齡”}，並挑選其中最好的資料維度 {“平均月收入”, “年齡”} 針對晶格單一資料維度 {“平均月收入”}、{“教育程度”} 與 {“年齡”} 分別計算其測量值，並挑選其中最好的資料維度 {“平均月收入”} 因為 {“平均月收入”} 的測量值低於 {“平均月收入”, “年齡”} ，因此{“平均月收入”, “年齡”} 仍為最佳之資料維度組合

43 資料維度組合產生順序 漸進式挑選法(sequential forward generation)
漸進式刪減法(sequential backward generation) 混合法(bidirectional generation) 隨機選取法(randomized generation)

44 混合法 概念 混合法結合漸進式挑選法與漸進式刪減法，同時由晶格下方的{ }往晶格上方和由晶格上方的 {“平均月收入”, “教育程度”, “年齡”} 往晶格下方出發

45 資料維度組合產生順序 漸進式挑選法(sequential forward generation)
漸進式刪減法(sequential backward generation) 混合法(bidirectional generation) 隨機選取法(randomized generation)

46 隨機選取法 概念 隨機選取法主要為配合隨機列舉策略所衍生出來。首先，隨機決定由晶格下方或晶格上方出發，配合隨機列舉策略產生任一可能的資料維度組合，並進行評核

47 列舉策略 v.s 組合產生順序 資料維度組合產生策略與資料維度組合產生順序的搭配可行性 完全列舉策略 經驗法則列舉策略 隨機列舉策略
漸進式挑選法 適合 不適合 漸進式刪減法 混合法 隨機選取法

48 資料記錄精簡(Record Reduction)
資料記錄精簡的需求 隨著資料表中的資料記錄愈來愈多，整個資料探勘所需的時間將跟著拉長 在資料維度精簡上也扮演著重要的角色，可以利用少量具代表性的資料記錄，將可以加速資料維度精簡上的處理 資料記錄精簡對所獲得的知識影響 求得之知識可能多少有些誤差 然而當資料集合中存在無關、偏差的資料記錄時，將資料記錄作適當的精簡，將能獲得更準確有效的知識

49 資料記錄精簡的方法 統計方法中抽樣(sampling)的作法 資料集合中抽取部分的資料記錄樣本來代表整個資料集合母體
隨機抽樣(random sampling) 分層抽樣(stratified sampling) 群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

50 資料記錄精簡的方法 隨機抽樣(random sampling) 分層抽樣(stratified sampling)
群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

51 隨機抽樣(random sampling)
假設資料集合中的資料記錄數量為N，則每一筆被選擇的機率為1/N 取回式隨機抽樣 每一筆被挑選的資料記錄，仍可以重覆再被挑選 不取回式隨機抽樣 每一資料記錄僅能被挑選一次，不可重覆被挑選 資料集合(N=6) 取回式隨機抽樣(n=4) 不取回式隨機抽樣(n=4)

52 資料記錄精簡的方法 隨機抽樣(random sampling) 分層抽樣(stratified sampling)
群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

53 分層抽樣(stratified sampling)
概念 步驟一：針對資料集合中同質性高且互不重疊的分層，各自進行隨機抽樣 步驟二：將各分層的抽樣結果結合成一個樣本 資料集合(N=6) 分層抽樣 樣本(n=3) 分層一 分層二 分層三

54 資料記錄精簡的方法 隨機抽樣(random sampling) 分層抽樣(stratified sampling)
群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

55 群集抽樣(cluster sampling)
概念 步驟一：利用群集分析技術，將整個資料集合區分成數個群集，使得每個群集中的資料記錄相似度很高，不同群集間的資料記錄相似度很低 步驟二：隨機由這些群集中選取數個群集形成一個樣本 群集抽樣 資料集合(N=6) 樣本(n=3) 群集一 群集二 群集一 群集二 群集三

56 資料記錄精簡的方法 隨機抽樣(random sampling) 分層抽樣(stratified sampling)
群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

57 系統抽樣(systematic sampling)
概念 步驟一：假設資料集合中的資料記錄筆數為N，而所需之樣本資料記錄筆數為n，則系統抽樣的方式首先隨機由1~N/n之間選取一個數字；假設所選取的數字為k 步驟二：以k開始，每N/n個間隔 (interval)，將相對應的資料記錄選取進樣本之中 系統抽樣 k=2 資料集合(N=6) 樣本(n=3)

58 資料記錄精簡的方法 隨機抽樣(random sampling) 分層抽樣(stratified sampling)
群集抽樣(cluster sampling) 系統抽樣(systematic sampling) 兩階段式抽樣(two-phase sampling)

59 兩階段式抽樣(two-phase sampling)
概念 進行兩個階段的抽樣選取過程以決定樣本 第一階段首先由資料集合中隨機抽樣出一個較大的樣本，接著將第一階段中所得到的樣本當成資料集合 兩階段式抽樣可以延伸成多階段式抽樣(multi-phase sampling)

60 抽樣方法設計考量 一般抽樣或特定領域抽樣 機率抽樣或非機率抽樣 一次處理抽樣或多次處理抽樣 取回式抽樣或不取回式抽樣 動態抽樣或非動態抽樣

61 資料數值精簡(Value Reduction)
資料記錄精簡的需求 原始資料中存在太細、過於底層的資料數值，對於許多資料探勘方法而言，將無法從中找出層次較高、趨勢導向的知識 連續性資料數值精簡 資料數值分離技術(discretization technique) 類別性資料數值精簡 概念階層(concept hierarchy)

62 資料數值分離技術(1) 利用分離技術(discretization)，切割出數個區間來取代值域上眾多的資料數值 人工分離法
依據特定連續性資料維度的認知、專家的建議、普遍存在的現象，將資料數值的值域分離出數個區間 “年齡”此資料維度可以分離出下列三個區間，(0, 30]、(30,60]、(60,120]，並分別對應到 ‘青年’、‘中年’ 和 ‘老年’ 等三個資料數值

63 資料數值分離技術(2) 裝箱法(binning method)
相等寬度 (equal-width-interval)裝箱法 相等深度 (equal-frequency-interval)裝箱法

64 等寬裝箱法 在使用者所給定之箱子個數n下，依據排序過後資料數值之最大值與最小值切割成n個等寬箱子
以 “年齡” 此資料維度而言，在使用者所給定之箱子個數為3下，每一個箱子的寬度為 (36-28) /3 = 2.67，經四捨五入後為3 箱子一：28, 29, 30 箱子二：31, 32 箱子三：35, 36

65 等深裝箱法 此做法為在使用者所給定之箱子個數n下，依據資料數值的數量切割成n個數量相等箱子
會員資料表中總共有7筆資料記錄，在使用者所給定之箱子個數為3下，每一個箱子可裝載之資料筆數為為7/3 = 2.33，經四捨五入後為2 箱子一：28, 29 箱子二：30, 31 箱子三：32, 35, 36

66 概念階層(1) 概念階層的概念 對於某一領域中各個概念(concept) 給定適當之階層關係，透過這些階層關係，了解此領域的範圍和組成元素，幫助釐清與了解領域 愈往上層的概念所涵蓋的範圍愈廣泛，愈往底層之概念所涵蓋範圍愈特定而狹隘

67 概念階層(2) 會員編號 平均月收入 (千) 教育程度 年齡 會員等級 1 21 高中 30 低 2 24 大學 29 高 3 33 國中
28 4 20 32 5 42 31 6 38 35 7 37 36 會員編號 平均月收入 (千) 教育程度 年齡 會員等級 1 21 高等教育 30 低 2 24 29 高 3 33 基礎教育 28 4 20 32 5 42 31 6 38 35 7 37 36

68 總結(1) 前置處理階段適當的資料精簡 資料維度的精簡 資料記錄的精簡 減少整個探勘過程中所花費的時間和成本
提高所獲取知識的準確性、利用性和可讀性 資料維度的精簡 給定標的資料維度，利用測量法、組合產生策略與組合產生順序，選出具有代表性的資料維度，縮短每一資料記錄的長度 資料記錄的精簡 利用統計抽樣的方法，挑選出部分具代表性的資料記錄，減少資料記錄的數量

69 總結(2) 資料數值的精簡 資料維度、資料記錄與資料數值在進行精簡上，彼此互相關連和影響
利用資料數值分離技術與概念階層，將分別縮小連續性資料數值與類別性資料數值的值域範圍 資料維度、資料記錄與資料數值在進行精簡上，彼此互相關連和影響