建构整合决策树与关连规则之资料挖矿架构及实证研究

建構整合決策樹與關連規則之資料挖礦架構及實證研究期末報告組別：三資四BH24932128謝殿臣資四BH24932089黃孝慈資四BH24932437顏姿青作者：楊景晴2一、緒論_研究背景及重要性隨著資訊科技的進步，企業所記錄或儲存的大量資料，對於不同階層的使用者來，資料代表著不同的意義與價值。當大量的資料被企業儲存起來，如何發揮與創造出資料價值變成為將資料由負債轉換資產的成功關鍵。3一、緒論_研究背景及重要性決策結果解釋(視覺化技術)資料挖礦(資訊探索)資料探索(OLAP、統計分析、查詢報表)資料倉儲、資料超市資料來源(資料庫系統、OLTP、檔案)資訊量價值性決策者企業主管資料分析者資料庫管理者圖1.1企業中的資料階層4一、緒論_研究目的目的：事故排除方法：建構整合決策樹與關連規則之資料挖礦架構及實證研究。實驗對象：以台灣電力公司與某半導體廠兩個不同產業之案例做為實證，已檢驗此資料挖礦架構之效度。5一、緒論_論文結構與研究流程1.2圖研究流程問題定義與架構問題定義理論架構結果分析與討論結論專家訪談實證研究一台灣電力公司實證研究二某半導體大廠6二、文獻探討_知識發現與資料挖礦表2.2資料挖礦的定義2.2圖資料挖礦的四個循環確認問題類型評估挖礦結果採用適當工具進行挖礦工作7二、文獻探討_知識發現與資料挖礦2.3圖資料挖礦過程的主要步驟問題定義獲取相關領域知識選取資料資料前置處理分析與解釋報告與使用資訊8二、文獻探討_知識發現與資料挖礦2.4圖資料挖礦專案流程步驟2.5圖適用各產業之資料挖礦架構9二、文獻探討_資料挖礦模式與工具資料挖礦模式(Model)的六種形式資料挖礦模式(Model)分類迴歸時間序列分群關聯分析順序挖掘監督式學習非監督式學習10二、文獻探討_資料挖礦模式與工具2.6圖資料挖礦的技術資料挖礦(DataMining)資料庫技術(DatabaseTechnology)統計學(Statistics)資訊科學(InformationScience)機器學習(MachineLearning)視覺化技術(Visualization)其他領域研究11二、文獻探討_資料挖礦挖掘結果類型資料挖礦所處理的問題類型由上而下:利用現有的模型來建立資料，藉此來描述某一特定變數。由下而上:不需要特別標註在某一變數或某一種値，而是試著尋找所有變數中是否有隱藏某種關係。分類(Classification)預測(Prediction)分群(Clustering)關聯規則分析(AssociationRule)資料挖礦所處理的問題類型由上而下由下而上12二、文獻探討_資料挖礦工具資料挖礦屬於探索導向，不需事先假設以求驗證。挖礦者需在一開始就釐清處理的工作目的為何？資料挖礦工具依照解決的問題類型與挖礦的目的而異。通常不會只使用單一工具來進行挖掘工作。13二、文獻探討_資料挖礦工具表2.3挖礦問題類型及可使用的工具(附註:ˇ表工具可使用之挖掘問題類型)問題類型工具分類Classification預測Prediction關聯分組AffinityGrouping聚集分析Clustering基本統計ˇˇˇˇ關聯規則/購物籃分析ˇˇˇ記憶基礎法ˇˇˇˇ遺傳演算法ˇˇ聚類偵測法ˇˇ鍊結分析法ˇˇˇ決策樹ˇˇˇ類神經網路ˇˇˇ14二、文獻探討_資料挖礦工具表2.4資料挖掘工具的基本特性介紹的演算法如下:遺傳演算法類神經網路FuzzyLogic記憶基礎理解決策樹。使用14種特性作介紹。15二、文獻探討_資料挖礦工具表2.5資料挖礦工具間的比較(附註:ˇ表資料挖礦工具能表現的能力)工具表現能力Regression/ANOVA類神經網路決策樹關聯規則模式使用上(Modelfree)ˇˇˇ對離群値的穩定性(RobusttoOutliers)ˇ具體解釋能力(Physicalintertation)ˇˇ連續變數處理能力(Continuousoutputs)ˇˇ類別變數處理能力(Discreteoutputs)ˇˇˇˇ16二、文獻探討_關聯規則是最常被應用的模式之一關聯規則分析（associationRuleAnalysis）從資料庫龐大的資料中，探索資料間欄位有趣的關係或相關性。購物籃分析如何從日積月累的交易資料中，以有效的方法找出商品間的關聯性，進而推斷消費者購買行為，創造無限商機。17二、文獻探討_關聯規則定義與說明進行關聯規則挖礦時，作業流程的兩大步驟找出所有的高頻項目組(FrequentItemsets)高頻項目組所出現的次數必須大於等於事先定義的最小支持度數目。此步驟決定了整體作業的效能從找到高頻項目組產生關聯規則所產生的規則必須滿足決策者所給定支持度與信賴度的最低門檻値，規則才成立。18二、文獻探討_關聯規則定義與說明定義描述YXIYXitemset)t(ConsequenYitemset)t(AntecedenXYXY)thenX(IfYXTDITon)(TransactiT(Item)},...,,{I21的子集合且皆為和為結果項目組為前提項目組則規則表示形式為有很大機會會發生情況下，生若產生的關聯規則為發的集合。是有交易紀錄。內物品項的集合，則是指一筆交易的集合。是所有相異物品項目miii19二、文獻探討_關聯規則定義與說明關聯規則的成立必須滿足決策者所訂定之最小支持度（MinmumSupportThreshold），和最小信賴度(MinmumConfidenceThreshold)。有意義的關聯規則其支持度與信賴度必須大於或等於所訂定之最小門檻値。增益指標加入後，若增益大於1，則表示規則的預測結果比單純的亂數還要好，反之，則較差。20二、文獻探討_關聯規則定義與說明若規則表示為X=Y，則1.支持度（Support）在規則(Rule)中，項目(Items)一起出現的交易暨路佔全部交易紀錄的百分比。最小支持度控制了一個關聯規則必須涵蓋的最少資料數目，以篩選掉不顯著的規則，在實務上才有應用價値。支持度代表的意義為X與Y一起出現的機率。2.1)()()(式YXPYXSupport21二、文獻探討_關聯規則定義與說明若規則表示為X=Y，則2.信賴度(Confidence)代表此條規則的預測強度。X發生之下發生Y結果的機率足以使得此關聯規則得以成立。計算在前提項目X發生的情況下，發生結果Y的機率。2.2)()(Y)P(X)()(式XPXYPYXConfidence22二、文獻探討_關聯規則定義與說明若規則表示為X=Y，則3.增益(LiftorImprovement)比較信賴度與結果項目Y單獨發生時之機率兩者間的大小。關聯規則的條件機率比母體中原本發生的機率大才具有意義。2.3)()()()()()()(式YPXYPYPXPYXPYXLift23二、文獻探討_關聯規則類型關聯規則類型1.以屬性質的形態為基礎若挖礦規則焦點放在項目(Item)是否出現，則稱為布林値的關聯規則(BooleanAssociationRule)。2.以規則中涵蓋資料維度為基礎若要挖礦的規則的項目或屬性著眼在單一維度時，稱之為單一維度關聯規則(SingleDimensionalAssociationRule)。3.以規則集合中所涵蓋的抽象層級(LevelofAbstraction)為基礎規則屬性或是項目全為同一層級，則稱為單一層級關聯規則(Single-LevelAssociationRule)。24二、文獻探討_關聯規則類型2.7圖概念層級樹25二、文獻探討_關聯規則演算法與特性表2.6關聯規則演算法與特性演算法作者/年代主要特色缺點AprioriAgrawal(1994)反覆產生候選項目組，找出所有高頻項目組，進而推導規則。需反覆搜尋資料庫，花費I/O時間。PartitionSavasere(1995)將資料庫分區段，找出個區段之高頻項目組並集合之，再次搜尋資料庫找出真正高頻項目組。在各區段中會產生較多非相關項目組。DHPJong等人(1997)利用雜湊表(hashtable)刪減不必要的候選項目組。一開始會花時間建立hashtableBSMWur等人(1999)使用表格運算方式產生高頻項目組，改善Apriori多次掃描資料庫的缺點。需事先轉換運算表格。26二、文獻探討_關聯規則的應用1.商業應用藉由關聯規則方法了解顧客購買行為的資訊，協助零售業在進行商品擺放位置規畫。2.工業應用利用關聯規則發展一彈性且有項的巢式製造系統(CellularManufacturingSystem)，找出機台間的最佳組合，形成群組技術(GroupTechnology)。3.醫學應用利用關聯規則做藥品櫥位管理，或以過去看診暨路檢式藥品使用量與方法是否正確，並可分析個病例特徵間關聯程度。27二、文獻探討_決策樹決策樹監督式的特徵萃取演算法，廣泛應用來解決分類(Classification)形態問題的工具，亦可做為探索與預測之用。能夠將輸入變數依據某種規則或資料進行分類，並以樹枝狀方式表現類別之間由輸入變數所造成的區別，因此決策樹可對資料進行架構的分類。28二、文獻探討_決策樹決策樹演算法的四大步驟1.決策樹的切割(Splitting)決策樹須將輸入的預測變數作分類，用以解釋目標變數變異的原因。2.停止長樹(Stopping)當無法找出任何分隔預測變數可以顯著降低下一節點的分散度，表示樹以生長完整(Complete)。29二、文獻探討_決策樹決策樹演算法的四大步驟3.評估(Assessment)評估整個決策樹的錯分率(Misclassification)或是評估每個節點的錯誤率(ErrorRate)。公式如下：2.5)()()()(:)Re()()()(:)(2式錯分率迴歸樹錯分率分類樹tptsTRTreegressiontptrTRTreetionClassifica30二、文獻探討_決策樹決策樹演算法的四大步驟4.決策樹的修剪當決策樹所生長的層級越深時，子節點的資料比數就會越來越少，資料的代表性就越低，所產生的法則可能會造成過度學習(OverFitting)而產生偏差，此時演算法中就應加修剪的步驟。找出錯誤的分支給予修剪，如:CART、C4.5。以測試資料(TestingData)驗證、抽樣方法來減少決策樹過度學習現象的發生。31二、文獻探討_決策樹2.11圖修剪對錯誤率的影響32二、文獻探討_決策樹演算法表2.7常用決策樹演算法之比較演算法比較準則常見幾種決策樹的演算法CARTID3C4.5CHAID作者(年代)Briemen(1984)Quinlan(1986)Quinlin(1993)Hartigan(1975)處理資料形態離散、連續離散、連續離散、連續離散分裂樹二元樹不受限制不受限制不受限制連續形資料處理方式分2枝不受限制不受限制無法處理分枝準則Gini値InformationGainGain_Ratio統計檢定(卡方分配)33二、文獻探討_決策樹於事故診斷的相關研究表2.8應用決策樹於事故排出之相關研究研究者實證對象使用的演算法Braha&Shmilovici(2003)半導體黃光區C4.5鄭人傑(2003)晶圓過站記綠與CP測試値Kruskal-Wallis、卡方交互影響檢測、變異降低分枝法則劉中光(2002)印刷電路板(PCB)決策樹結合SOM方法Raghavan(2002)良率、ICE-TTestparameter利用決策樹(CART、CHAID)Fan(2001)WAT、InLineManufacturingdata決策樹蔡智政(2001)晶圓批量製程管制(LPC)資料以CART決策樹分析LPC李培瑞(2001)半導體WAT資料、CP資料結合人工類神經網路與決策樹林鼎浩(2000)半導體WAT與製造相關資料無母數Kruskal-Wal