限制推理型之粒子群與基因演算法於產生分類規則之研究

Research of a Constraint-Based Particle Swarm Optimization and Genetic Algorithm Approach for Mining Classification Rule

詹豐澤(Feng-Tse Chan)

指導教授 ： 徐培倫

健行科技大學/電資學院/電子工程所/碩士(2009年)

https://doi.org/10.6824/UCH.2009.00035

摘要

本論文提出一個限制推理型之粒子群與基因演算法用以解決資料探勘之分類問題。由於粒子群與基因演算法主要是透過適應值函數來評估分類規則，但是當問題的複雜度提高時，除了搜尋時間會相對提高外，且有可能會陷入區域最佳解之困境。基於上述之缺點，本研究整合限制推理及粒子更新機制於粒子群演算法架構中，用來減少粒子產生的搜尋空間，使得粒子群演算法能夠更快速的找出符合限制之最佳解。此外本研究提出混合式粒子更新機制中，結合粒子群與基因演算法更新機制以補足粒子群演算法於區域搜尋能力不足的缺點，使粒子之搜尋範圍及效能得到良好的提升。根據實驗結果顯示，限制式粒子群及基因演算法較一般傳統的粒子群演算法有更快速且較符合目標之結果。

關鍵字

限制推理 ； 資料探勘 ； 粒子群演算法 ； 基因演算法

並列摘要

This paper aims to develop a constraint-based particle swarm optimization and genetic algorithm approach for mining classification rules. Existing particle swarm optimization (PSO) designed for rule induction evaluates the rules as whole via a fitness function. Major drawbacks of PSO for rule induction include computation inefficiency, accuracy and rule expressiveness. In this paper, we propose a constraint-based particle swarm optimization and genetic algorithm(CBPSOGA) approach for mining classification rules.This approach allows constraints to be specified as relationship among attributes according to predefined requirements of user’s preference in the form of a constraint network. Additionally, the new update approach based on genetic algorithm (GA) is incorporated to produce better classification rules. The proposed approach is compared with a regular PSO,constraint-based GA and constraint-based PSO algorithms using UCI repository data sets. Better classification accurate rates form CBPSOGA are demonstrated.

並列關鍵字

Constraint-Based Reasoning ； Data Mining ； Particle Swarm Optimization ； Genetic Algorithm

參考文獻

1. 徐培倫，詹豐澤，「整合限制推理粒子群演算法於資料探勘分類問題之研究」，第十三屆人工智慧與應用研討會，淡江大學宜蘭校區，民國97年十一月二十一、二十二日。

2. 王良吉，”應用PSO 演算法於分類規則之探勘”，國立高雄第一科技大學碩士論文，民國九十六年一月。

3. R. Barták, “Constraint Programming: In Pursuit of the Holy Grail,” Proceedings of Week of Doctoral Students, Prague, Czech Republic, pp.555-564, 1999.

4. C. Bessiere, “Arc-Consistency and Arc-Consistency Again,” Artificial Intelligence, Vol.65, No.1, pp.179-190, 1994.

5. C. Bessiere, E. C. Freuder and J. C. Régin, “Using Constraint Metaknowledge to Reduce Arc Consistency Computation,” Artificial Intelligence, Vol.107, No.1 pp.125-148, 1999.