[[alternative]]Using association classification to represent a decision tree

博士[[abstract]]分類（Classification）是資料探勘（Data Mining）常用策略之一，而關聯演算法（Association Classification）與決策樹（Decision tree）更是分類上經常使用的方法。雖然關聯演算法的主要優點在提供全域決策規則（Global Decision Rules），但關聯演算法無法直接處理連續型數值資料，先行對連續型數值進行離散化處理，而要找最佳數值切點是一個NP-hard問題；且關聯演算法雖可以找出所有決策規則，但由於規則數量過多，較難建構一個完整知識解釋結構。另一方面，雖然決策樹能夠直接處理連續型數值與非連續型數值欄位及易於產生明確的知識結構，但決策樹因樹狀結構與演算法的限制，因此在由決策樹轉換後的決策規則是屬於區域決策規則（Local Decision Rules）且決策規則當中可能存在不相關決策條件（Irrelevant Classification Condition）。因此，本論文將針對此問題，提出解決方法。本研究首先利用決策樹在連續數值屬性以及快速處理的特性，找出隱藏在資料集內的知識與決策規則，同時藉由決策樹演算法的區域性（local）特性快速度出所有可能連續數值屬性的離散化切點集。而後再將決策樹轉換後決策規則與離散化切點集重新利用關聯演算法整理，將決策樹決策規則重新轉換成為以全域性、移除不相關決策條件及條件更簡單的關聯決策規則。最後，在本研究中利用卵巢子宮內膜異位症臨床資料集進行實驗，實驗结果表明，對比CART決策樹生成的決策規則在原始決策規則之下，提出分類精度較高、條件更簡單且可理解性強的關聯決策規則。[[abstract]]Since the derived rules of decision trees are local, the association classifier has higher accuracy than decision tree classifier and many useful rules are left undiscovered by the decision tree techniques.However, goal of the classification rule mining is to discover a small set of rules in the database, the association rule technique will capture all possible rules in the database and generate too many rules; one the other hand, many useful rules are left undiscovered by the decision tree techniques. Medical data always contains numeric (continuous values) attributes; however, the association rule technique can not deal with numeric data directly and it is not an easy task to find out the appropriate way to discrete numeric attributes. Moreover, in order to neutralize drawbacks of these two mining techniques and use current commercial mining tools to analyze postoperative status of ovarian endometriosis patients to discover rules, we propose a concept to take the advantages of decision tree and association rule techniques to mine the data. In this paper, our goal is to investigate the efficacy of transvaginal aspiration and sclerotherapy with 95% ethanol retained in situ for the treatment of recurrent ovarian endometriomas. Moreover, although several researchers have performed statistical method to prove that aspiration followed by injection 95% ethanol left in situ (retention) is an effective treatment of ovarian endometriomas, very few of them discuss about the conditions that could generate better recovery rate for the patients. Therefore, this study adopts the statistical method and data mining techniques together to analyze postoperative status of ovarian endometriosis patients to discover such conditions.[[tableofcontents]]目錄 第一章緒論 1 1-1 研究背景與動機 1 1-2 研究目的 4 1-3 研究方法 8 1-4 論文架構 9 第二章背景知識 11 2-1 決策樹 11 2-2 數量關聯分類演算法 15 2-2-1 關聯分類演算法 15 2-2-2 數量關聯規則 18 2-2-3 數量關聯演算法 19 2-2-4 數量關聯演算法合併 23 2-3 決策樹用於分類建構上的問題 28 2-3-1 連續數值屬性離散化 29 2-3-2 全域分類與區域分類 30 2-3-3 不相關決策條件問題 34 2-3-4 決策樹單一分支問題 38 第三章研究方法 40 3-1 使用CART演算法取得規則集與連續數值屬性切點集 42 3-2 全域規則演算法 45 第四章實驗結果 59 4-1 研究資料集來源 59 4-2 實驗結果 60 4-3 實驗討論 67 4-3-1 各別規則實驗結果討論 67 4-3-2 整體性實驗結果分析與討論 69 第五章結論 72 參考文獻 77 圖目錄 圖 2-1決策樹樹狀圖 12 圖 2-2 Cyst_size離散化結果 30 圖 2-3原始決策樹 32 圖 2-4裁減後決策樹 32 圖 2-5決策規則與資料分佈圖 33 圖 3-1 IRDTAC演算法 41 圖 3-2根據表3-1建構高血壓控制決策樹(未執行分支裁剪設定) 44 圖 3-3根據表3-1建構高血壓控制決策樹(已執行分支剪裁設定) 44 圖 3-4區域性之決策圖 46 圖 3-5全域性之決策圖 47 圖 3-6規則選擇有用切點演算法 51 圖 3-7選擇最佳規則演算法 58 圖 4-1臨床資料集CART原始決策樹 61 圖 4-2手動裁剪後臨床資料集決策樹結果 63 表目錄 表 2-1決策樹轉換後決策規則 13 表 2-2移除不相關決策條件的全域決策規則 35 表 2-3轉換後決策規則 39 表 2-4簡化後決策規則 39 表 3-1高血壓控制狀況表 43 表 3-2屬性離散化切點表 45 表 3-3 x屬性切點集 49 表 3-4 x屬性切點集 52 表 3-5表3-4可用切點之關聯規則組合 53 表 3-6候選關聯規則集 56 表 4-1屬性描述 61 表 4-2 Cyst_size切點集 62 表 4-3 CA_125切點集 62 表 4-4 BMI切點集 62 表 4-5離散化切點數比較 63 表 4-6臨床資料集決策樹轉換後關聯規則 64 表 4-7以信賴度、支持度，規則長度與規則條件涵蓋度篩選後臨床資料集關聯規則 66 表 4-8卵巢子宮內膜異位症臨床資料集分類成果比較表 70[[note]]學號: 894190049, 學年度: 10