進階搜尋


 
系統識別號 U0026-0812200911140362
論文名稱(中文) 使用決策樹方法發掘連續數值屬性多區間分類規則
論文名稱(英文) Finding multi-interval classification rules on continuous-valued attributes, a decision tree approach.
校院名稱 成功大學
系所名稱(中) 資訊管理研究所
系所名稱(英) Institute of Information Management
學年度 92
學期 2
出版年 93
研究生(中文) 黃柏璋
研究生(英文) Po-Chang, Huang
學號 r7690109
學位類別 碩士
語文別 中文
論文頁數 88頁
口試委員 口試委員-陳正綱
口試委員-林妙聰
指導教授-黃宇翔
中文關鍵字 分類規則  連續數值屬性  決策樹 
英文關鍵字 continuous- valued  Decision tree  rule induction 
學科別分類
中文摘要   機器學習法中的決策樹歸納學習法,由於其學習速度快及易於產生明確的知識結構的特性,有很廣泛的實際應用領域。然而其應用層面卻受限於決策樹歸納學習法先天上的限制,較適用於處理名目資料(nominal)符號式的概念。對於連續數值屬性則需要一個決定分割點的演算法或量度標準,將連續數值轉為有限離散值。本研究運用決策樹歸納學習法結合階層式叢集分析,以屬性值相互間的接近程度以及分類結果的相似度作為距離函式進行叢集,來處理連續數值屬性的分割問題,藉著多區間分割方式產生更準確的分類規則,以期能突破決策樹歸納學習法處理連續數值屬性時,舊有應用上的藩籬。本研究採實證方式檢驗此屬性分割方法:實作所提出的演算法,在UCI-ML 測試資料庫上與現有的連續數值屬性分割方法加以實驗比較。以預測準確度與決策樹大小作為決策樹良莠的指標,以驗證本研究所提出的決策樹歸納學習法之有效性。
英文摘要   In realized situation, data usually are presented in datasets by both continuous and discrete-valued forms. Not inductive nor connectist learning methods can manage this kind of mixed- form datasets efficiently. While most inductive learning methods can only deal with discrete attributes value efficiently, connectist methods need more
constructing design on datasets which contain discrete-valued attributes. We purpose a new decision tree inductive learning method that uses hierarchical clustering process to construct multi- interval decision rules on continuous-valued attributes. This method occupied two advantages: 1. A decision tree inductive learning method that can deal with “mix-form datasets” efficiently, which means, the datasets that contain both discrete and continuous-valued attributes. 2. Flexibility for the trade-off between the simplification and the accuracy of decision models. The decision tree inductive method was implemented and compared experimentally with known inductive methods. Experiments use ten-fold cross-validation and block design for comparison on ten datasets.
論文目次 1 目 錄
0 誌 謝..............................................................3
1 目 錄..............................................................4
2 摘 要..............................................................9
3 Abstract...........................................................10
4 第一章 緒言....................................................... 11
第一節、研究背景.................................................... 11
第二節、研究動機.....................................................................12
第三節、研究目的.....................................................................13
第四節、論文結構.....................................................................15
5 第二章 文獻探討.....................................................................17
第一節、決策模型與知識管理.....................................................................17
第二節、決策樹歸納學習法.....................................................................19
第三節、連續數值屬性分割問題.....................................................................23
第四節、實作測試.....................................................................28
第五節、小結.....................................................................29
6 第三章 研究方法.....................................................................30
第一節、問題描述.....................................................................30
3.1.1 決策樹歸納學習法.....................................................................30
3.1.2 啟發式搜尋法.....................................................................36
3.1.3 修改後的決策樹歸納學習法.....................................................................39
3.1.4 符號定義與目標函式.....................................................................41
第二節、研究架構.....................................................................44
第三節、連續數值屬性多區間分割法.....................................................................46
5
3.3.1 距離(不相似度)函式.....................................................................47
3.3.2 叢集分析程序.....................................................................49
第四節、小結.....................................................................53
7 第四章 實證研究.....................................................................55
第一節、實務應用實驗.....................................................................55
第二節、Hide-and-seek 實驗.....................................................................66
4.2.1 控制資料集
T
S 之製備.............................................................67
4.2.2 演算法發掘預藏樣式之能力.....................................................................69
4.2.3 各演算法在資料集
T
S 上之效果...........................................................71
第三節、討論.....................................................................73
8 第五章 結論與建議.....................................................................75
第一節、結論.....................................................................75
第二節、建議.....................................................................77
9 參考資料...........................................................80
參考文獻 Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules inlarge databases. In J. Bocca, M. Jarke, & C. Zaniolo (Eds.), Proceedings
International Conference on Very Large Databases, Santiago, Chile, pp.478-499,
Morgan-Kaufmann, San Francisco.
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998). Automatic subspace
clustering of high dimensio nal data for data mining applications. Proceedings of
the 20th ACM SIGMOD International Conference on Management of Data,
Seattle, Washington, pp.94-105.
Agrawal, R., Imielinski, T., & Swami, A. (1993a). Database mining: a performance
perspective. IEEE Transactions on Knowledge and Data Engineering, Vol.5,
No.6, pp.914-925.
Agrawal, R., Imielinski, T., & Swami, A. (1993b). Mining association rules betweensets of items in large databases. In P. Buneman, & S. Jajodia (Eds.), Proceedings ACM SIGMOD International Conference on Management of Data, Washington,DC, pp.207-216, ACM, New York.
Berka, P. & Bruha, I. (1998). Empirical comparison of various discretization
procedures. International Journal of Pattern Recognition and Artificial
Intelligence, Vol.12, No.7, pp.1017-1032.
Blake, C. L. & Merz, C. J. (1998). UCI Repository of machine learning databases
[http://www.ics.uci.edu/~mlearn/MLRepository.html]. Irvine, CA: University of
California, Department of Information and Computer Science.
Bolloju, N., Khalifa, M., & Turban, E. (2002). Integrating knowledge management
into enterprise environments for the next generation decision support. Decision
Support Systems, Vol.33, No.2, pp.163-176.
Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and
Regression Trees, Wadsworth International Group, Belmont, California.
Cendrowska, J. (1987). PRISM: An Algorithm for inducing modular rules.
International Journal of Man-Machine Studies, Vol.27, No.4, pp.349-370.
Cestnik, B., Kononenko, I., & Bratko, I. (1987). ASSISTANT 86: A
Knowledge-elicitation tool for sophisticated users. In I. Bratko & N. Lavrac
(Eds.), Progress in machine learning - proceedings of the 2nd European Working
Session on Learning, Bled, Yugoslavia, pp.31-45, Sigma Press, Wilmslow.
Chmielewski, M., & Grzymala-Busse, J. W. (1996). Global discretization of
continuous attributes as preprocessing for machine learning. International
Journal of Approximate Reasoning, Vol.15, No.4, pp.319-331.
Clark, P., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning,
Vol.3, No.4, pp.261-283, Kluwer Academic Publishers, Massachusetts.
Dabija, V. G., Tsujino, K., & Nishida, S. (1992). Learning to learn decision trees.
Proceedings of 10th National Conference on Artificial Intelligence, San Jose,
California, pp.88-95, AAAI Press, Menlo Park, California.
De Jong, K. A., Spears, W. M. & Gordon, D. F. (1993). Using genetic algorithms for concept learning. Machine Learning, Vol.13, No.2-3, pp.168-182, Kluwer
Academic Publishers, Massachusetts.
De Hoog, R., Martil, R., Wielinga, B., Taylor, R., Bright, C., & van de Velde, W.
(1993). The CommonKADS model set. ESPRIT Project P5248
KADS-II/M1/DM..1b/UvA/018/5.0, University of Amsterdam, Lloyd's Register,
Touche Ross Management Consultants & Free University of Brussels.
Dougherty, J., Kohavi, R., & Sahami, M. (1995). Supervised and unsupervised
discretization of continuous features. In A. Prieditis & S. Russell (Eds.),
Proceedings of the 12th International Conference on Machine Learning, Lake
Tahoe, California, pp.194-202, Morgan-Kaufmann, San Francisco.
Drucker, P. F. (1988). The coming of the new organization. Harvard Business Review,January-February, Vol.66, No.1, pp.45-53.
Efron, B. & Tibshirani, R. (1993). An Introduction to the Bootstrap. Chapman and
Hall, New York.
Efron, B. (1979). Bootstrap methods: another look at the jackknife. Annals of Statistic,Vol.7, No.1, pp.1-26.
Fayyad, U. M., & Irani, K. B. (1991). (A) Machine learning algorithm (GID3*) for
automated knowledge acquisition: improvements and extensions. General
Motored Research Technical Report CS-634, GMR-7592(1992), GM Research
Labs, Warren, MI.
Fayyad, U. M., & Irani, K. B. (1992). On the handling of continuous- valued attributes in decision tree generation. Machine Learning, Vol.8, No.2, pp.87-102, Kluwer Academic Publishers, Massachusetts.
Fayyad, U. M., & Irani, K. B. (1993). Multi-interval discretization of
continuous-valued attributes for classification learning. In R. Bajcsy (Ed.),
Proceedings of the 13th International Joint Conference on Artificial Intelligence, Chambery, France, pp.1022-1027, Morgan-Kaufmann, San Francisco.
Fayyad, U. M., Cheng, J., Irani, K. B., & Qian, Z. (1988). Improved decision trees: a generalized version of ID3. Proceedings of the 5th International Conference on Machine Learning, Ann Arbor, MI., pp.100-108, Morgan-Kaufmann, San
Francisco.
Feelders, A., Daniels, H., & Holsheimer, M. (2000). Methodological and practical
aspects of data mining. Information and Management, Vol.37, No.5, pp.271-281.
Frawley, W. J., Piatetsky-Shapiro, G., & Matheus, C. J. (1991). Knowledge Discovery in Databases: an overview. In G. Piatetsky-Shapiro, & W. J. Frawley (Eds.), Knowledge Discovery in Databases, pp.1-27, AAAI/MIT Press, Mewlo Park,
California.
Fu, Y. (1997). Data mining: tasks, techniques, and applications. IEEE Potentials,
Vol.16, No.4, pp.18-20.
Gallion, R., Sabharwal, C. L., St. Clair, D. C., & Bond, W. E. (1993). Dynamic ID3: A Symbolic learning algorithm for many- valued attribute domains, Proceedings of the 1993 ACM/SIGAPP Symposium on Applied Computing, pp.14-20, ACM
Press, Indianapolis, Indiana.
Giordana, A., & Neri, F. (1995). Search- intensive concept induction. Evolutionary Computation, Vol.3, No.4, pp.375-416.
Gordon, J. L. (2000). Creating knowledge maps by exploiting dependent relationships. Knowledge-Based Systems, Vol.13, No.2-3, pp.71-79.
Grzymala-Busse, J. W., & Stefanowski, J. (2001). Three discretization methods for
rule induction. International Journal of Intelligent Systems, Vol.16, No.1,
pp.29-38.
Grzymala-Busse, J.W., Stefanowski, J. (1997). Discretization of numerical attributes by direct use of the LEM2 induction algorithm with interval extension.
Proceedings of 6th Symposium Intelligent Information Systems, Zakopane, Poland,
pp.159-168, IPI PAN Press, Poland.
Hettich, S. & Bay, S. D. (1999). The UCI KDD Archive [http://kdd.ics.uci.edu]. Irvine, CA: University of California, Department of Information and Computer Science.
Hinton, G. E. (1989). Connectionist learning procedures. Artificial Intelligence, Vol.40, No.1-3, pp.185-234, North Holland, Amsterdam.
Hunt, E., Marin, J., & Stone, P. (1966). Experiments in Induction, Academic Press, New York.
Hyafil, L., & Rivest, R. L. (1976). Construction optimal binary decision trees is
NP-Complete. Information Processing Letters, Vol.5, No.1, pp.15-17.
Jacobsen, C., Zscherpel, U., & Perner, P. (1999). A Comparison between neural
networks and decision trees. Proceedings of International Work. Machine
Learning and Data Mining in Pattern Recognition, MLDM, LNAI: 1715,
Springer-Verlag.
Jai, Anil K., Duin, Robert P.W., & Mao, Jian Chang. (2000). Statistical pattern
Recognition: A review. IEEE Transactions on Pattern Analysis and Machine
Intelligence, Vol.22, No.1, pp4-37.
Janikow, C. Z. (1993). A Knowledge- intensive genetic algorithm for supervised
learning. Machine Learning, Vol.13, No.2-3, pp.189-228, Kluwer Academic
Publishers, Massachusetts.
Jeng, B., Jeng, Y. M., & Liang, T. P. (1997). FILM: A Fuzzy inductive learning
method for automated knowledge acquisition. Decision Support Systems, Vol.21,
No.2, pp.61-73.
Kerber, R. (1992). ChiMerge: Discretization of numeric attributes. Proceedings of the 9th International Conference on Artificial Intelligence, pp.123-128.
Kohavi, R. (1995a). Wrappers for performance enhancement and oblivious decision
graphs. Doctoral dissertation, computer science department, Stanford University.
Kohavi, R. (1995b). A study of cross-validation and bootstrap for accuracy extimation and model selection. International Joint Conference on Artificial Intelligence IJCAI.
Kwedlo, W., & Kretowski, M. (1998). Discovery of decision rules from databases: an evolutionary approach. Principles of Data Mining and Knowledge Discovery,
2nd European Symposium PKDD'98, LNCS: 1510, pp.370-378, Springer-Verlag.
Kwedlo, W., & Kretowski, M. (1999). An Evolutionary algorithm using multivariate
discretization for decision rule induction. Principles of Data Mining and
Knowledge Discovery, 3rd European Conference PKDD'99, LNAI: 1704,
pp.392-397, Springer-Verlag.
Liu, H., & Setiono, R. (1997). Feature selection via discretization of numeric
attributes. IEEE Transactions on Knowledge and Data Engineering, Vol.9, No.4,
pp.642-649.
López de Mántaras, R. (1991). A Distance-based attribute selection measure for
decision tree induction. Machine Learning, Vol.6, No.1, pp.81-92, Kluwer
Academic Publishers, Massachusetts.
Lu, W., Wu, W., & Sakauchi M. (1995). A Drawing recognition system with rule
acquisition ability. Proceedings of the 3rd International Conference on
Document Analysis and Recognition, pp.512-515.
Macintosh, A., Filby, I., Kingston, J., & Tate, A. (1998). Knowledge asset road maps.
Proceedings of the 2nd International Conference on Practical Aspects of
Knowledge Management, Basel, Switzerland.
Mingers, J. (1989a). An Empirical comparison of pruning methods for decision tree
induction. Machine Learning, Vol.4, No.2, pp.227-243, Kluwer Academic
Publishers, Massachusetts.
Mingers, J. (1989b). An Empirical comparison of selection measures for decision-tree induction. Machine Learning, Vol.3, No.4, pp.319-342, Kluwer Academic Publishers, Massachusetts.
Mitchell T. M. (1997). Machine Learning, pp.21-26, McGraw-Hill, New York.
Murthy, S. K., Kasif, S., & Salzberg, S. (1994). A System for induction of oblique decision trees. Journal of Artificial Intelligence Research, Vol.2, pp.1-32.
Nonaka, I. & Takeuchi, H. (1995). The Knowledge-Creating Company: How
Japanese Companies Create the Dynamics of Innovation, pp.2-21, Oxford
University Press.
Nonaka, I. (1991). The knowledge-creating company. Harvard Business Review,
November-December, Vol.69, pp.96-104.
Nonaka, I. (1994). A Dynamic theory of organizational knowledge creation.
Organization Science, Vol.5, No.1, pp.14–37.
Paterson, A., & Niblett, T. (1982). ACLS User Manual. Intelligent Terminals Ltd.,
Glasgow.
Pazzani, M., & Kibler, D. (1992). The utility of knowledge in inductive learning.
Machine Learning, Vol.9, pp.57-94, Kluwer Academic Publishers, Massachusetts.
Piramuthu, S., Ragavan, H., & Shaw, M. J. (1998). Using feature construction to
improve the performance of neural network. Management Science, Vol.44, No.3,
pp.416-428.
Quinlan, J. R. (1979). Discovering rules by induction from large collections of
examples. In D. Michie (Ed.), Expert Systems in the Micro -Electronic Age,
pp.168-201, Edinburgh University Press, Edinburgh.
Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, Vol.1, No.1, pp.81-106, Kluwer Academic Publishers, Massachusetts.
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning, Morgan-Kaufmann,
San Francisco.
Quinlan, J. R. (1996). Improved use of continuous attributes in C4.5. Journal of
Artificial Intelligence Research, Vol.4, pp.77-90.
Rissanen, J. (1985). The minimum description length principle. In Kotz, S., & N. L. Johnson (Eds.), Encylopedia of Statistical Sciences, Vol.5, pp.523-527, John
Wiley, New York.
Safavian, S. R., & Landgrebe, D. (1991). A Survey of decision tree classifier
methodology. IEEE Transactions on Systems, Man and Cybernetics, Vol.21,
No.3, pp.660-674.
Sahami, M. (1995). Generating neural networks through the induction of threshold
logic unit trees. ECML-95: Proceedings of the 8th European Conference on
Machine Learning, pp.339-342.
Scheffer, T., & Herbrich, R. (1997). Unbiased assessment of learning algorithms.
Proceedings of the International Joint Conference on Artificial Intelligence,
pp.798-803.
Schlimmer, J. C. & Fisher, D. H. (1986). A Case study of incremental concept
induction. In T. Kehler, & S. Rosenschein (Eds.), Proceedings of the 5th National
Conference on Artificial Intelligence, Philadelphia, Vol.1, pp.496-501,
Morgan-Kaufmann, San Francisco.
Schreiber, G., Akkermans, H., Anjewierden, A., de Hoog, R., Shadbolt, N., Van de
Velde, W., & Wielinga, B. (2001). Knowledge Engineering and Management,
pp.14-20, MIT Press, Cambridge, Massachusetts.
Shannon, C. E., & Weaver, W. (1949). The Mathematical Theory of Communication,
University Illinois Press, Urbana.
Simon, H. A. (1983). Why should machines learn? In R. S. Michalski, J. G. Carbonell, & T. M. Mitchell (Eds.), Machine Learning: An Artificial Intelligence Approach, pp.25-37, Morgan-Kaufmann, San Francisco.
Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, Part B, Vol.36, pp.111-147.
Susmaga, R. (1997). Analyzing discretizations of continuous attributes given a
monotonic discrimination function. Intelligent Data Analysis, Vol.1, No.3,
pp.157-179.
Tay, F. E., & Shen, L. (2002). A Modified Chi2 algorithm for discretization. IEEE
Transactions on Knowledge and Data Engineering, Vol.14, No.3, pp.666-670.
Utgoff, P. E. (1989). Incremental induction of decision trees. Machine Learning, Vol.4, No.2, pp.161-186, Kluwer Academic Publishers, Massachusetts.
Utgoff, P. E. (1994). An Improved algorithm for incremental induction of decision
trees. Proceedings of the 11th International Conference on Machine Learning,
pp.318-325, Morgan-Kaufmann, San Francisco.
Utgoff, P. E., & Brodley, C. E. (1991). Linear machine decision trees, (COINS
Technical Report, pp.91-10), department of computer science, University of
Massachusetts, Amherst, Massachusetts.
Van de Velde, W. (1989). IDL: Taming the multiplexer. Proceedings: European
Working Session on Learning, Morik, Katharina, pp.211-226.
Van de Velde, W. (1990). Incremental induction of topologically minimal trees. In
Bruce W. Porter & Ray J. Mooney (Eds.), Proceedings of the 7th International
Conference on Machine Learning, Austin, Texas, pp.66-74.
Wang, X., & Hong, J. (1998). On the handling of fuzziness for continuous-valued
attributes in decision tree generation. Fuzzy Sets and Systems, Vol.99, No.3,
pp.283-290.
Wani, M. A. (2001). SAFARI: A Structured approach for automatic rule induction.
IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol.31, No.4,
pp.650-657.
Witten, I. H., & Frank, E. (1999). Data Mining: Practical Machine Learning Tools
and Techniques with Java Implementations, pp.103-104, Morgan-Kaufmann, San
Francisco.
Zeidler, J., & Schlosser, M. (1996). Continuous-valued attributes in fuzzy decision trees. Proceedings of 6th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Granada, Spain, pp.395-400. [http://www.tuchemnitz.de/~jzei/VEROEFF/ipmu.ps].
Zhang, P. (1992). On the distributional properties of model selection criteria. Journal of the American Statistical Association, Vol.87-419, pp.732-737.
王錫澤,以歸納學習法求解單元製造系統動態派工問題,國立成功大學工業管理
研究所碩士論文,民國84 年。
吳盈宜,歸納學習法中決策樹連續數值屬性分割點之選擇,國立成功大學工業管
理研究所碩士論文,民國89 年。
邱美珍,決策樹學習法中連續數值屬性之分類研究,中原大學資訊管理研究所碩
士論文,民國85 年。
童冠燁,以歸納學習法探討彈性製造系統動態排程之研究,國立成功大學工業管
理研究所博士論文,民國86 年。
蕭文峰,運用決策樹歸納學習法預測連續數值,國立中山大學資訊管理研究所碩
士論文,民國84 年。
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2005-08-04起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2005-08-04起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw