使用基因演算法結合涵蓋演算法

Applying Genetic Algorithms to Covering Algorithms

邱南星(Nanhsing Chiu)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2001年)

摘要

涵蓋演算法是屬於眾多規則推理中的一種方式，它可以從眾多的分類資料來源當中，推理出一組規則出來。但是對於連續性的資料而言，涵蓋演算法則很難在這些資料當中，產生出呈現資料特性的規則。因此，對於連續性的資料，必須經過量化處理或者是其它的處理方式後，才能夠加以應用。在眾多的最佳化的理論當中，基因演算法是常被使用的方法之一。因此在資料量化的方法，採用基因演算法來進行量化。針對自變數的資料，是使用全域性監督資料量化的方式，來進行資料的量化。針對依變數的資料，是使用全域性非監督資料量化的方式。直至目前為止，很少人提出結合基因演算法與涵蓋理論來進行規則推理。使用此一方式來進行規則推理是一項創新的實驗研究。我們使用基因演算法不僅能用於輔助資料量化來決定最佳的切割點，並結合了涵蓋演算法，以其作為規則推理中的資料量化的準則。在本研究中，我們針對五種具代表性的分類資料進行實驗，將提出的作法與其他樹狀結構的規則推理與非樹狀結構的規則推理做比較。實驗結果顯示，本研究所提出之混合基因涵蓋演算法能夠有效的量化連續性的資料，動態的切割連續性資料，並能建構推理出規則。此外，本研究亦開發了一套雛形系統，用以輔助非樹狀規則推理的建構並自動產生一些規則以支援決策者制定決策。

關鍵字

基因演算法 ； 涵蓋演算法 ； 規則推理 ； 監督式資料量化 ； 非監督式資料量化 ； 全域性資料量化 ； 局部性資料量化

並列摘要

Covering Algorithms is a rule induction method. It usually performs well in categorical variables domains but poorly in continuous variables domains for rule induction. Disretization of continuous variables is important in data analysis, especially for covering algorithms that uses continuous variables. Therefore, the continuous variables have to be discretization before rule induction. The proposed methods of data discretization are adopted global with supervised discretization for input variables, and global with unsupervised discretization for output variable. Because genetic algorithm is a popular topic for solving optimization problems, discretization of continuous variables is adopted genetic algorithms as a preprocessing procedure for data discretization. However, rare work has been done in treating continuous variables and categorical in a coherent manner in the framework of covering algorithms. This paper presents a new structure that applies genetic algorithms to covering algorithms (GA+CA) for rule induction, and compares its learning performance with those results from some tree rule induction methods and non-tree rule induction methods. The experiment results show that the GA+CA method is effective in solving continuous variables for rule induction methods.

並列關鍵字

Genetic Algorithms ； Covering Algorithms ； Rule Induction Methods ； Supervised Discretization ； Unsupervised Discretization ； Global Discretization ； Local Discretization

參考文獻

[40]Ngan, P. S., Wong, M. L., Lam, W., Leung, K. S. and Cheng, C.Y., “Medical Data Mining Using Evolutionary Compution”, Artifical Intelligence in Medicine, Vol. 16, pp.73-96, 1999.

[34]Leech, W. J., "A Rule Based Process Control Method with Feedback", In Proceedings of the ISA/86, Research Triangle Park, NC 27709, The Instrumentation Society of America, pp.169-175, 1986.

[1]Abdullah, M. K., “CAN: Chain of Nodes Approach to Direct Rule Induction”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 29, No. 6, December, pp.758-770, 1999.

[2]Adeli, H. and Cheng, N. T., “Integrated Genetic Algorithm for Optimization of Space Structures”, J. Aerosp. Engrg., ASCE, Vol. 6(4), pp.315-328, 1993.

[5]Catlett, J., “On Changing Continuous Attributes into Ordered Discrete Attributes”, In Machine Learning—EWSL-91, Volume 482, Springer, pp.164-178, March 1991.