Journal of Shandong University(Engineering Science) ›› 2019, Vol. 49 ›› Issue (2): 122-130.doi: 10.6040/j.issn.1672-3961.0.2018.211

• Machine Learning & Data Mining • Previous Articles    

A rule extraction method based on multi-objective co-evolutionarygenetic algorithm

Zhongwei ZHANG(),Hongyan MEI*(),Jun ZHOU,Huiping JIA   

  1. School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121000, Liaoning, China
  • Received:2018-05-25 Online:2019-04-20 Published:2019-04-19
  • Contact: Hongyan MEI E-mail:zzwzzwcool@126.com;liaoning_mhy@126.com
  • Supported by:
    辽宁省科学技术计划项目面上项目(2015020089);辽宁省科学技术计划项目面上项目(201602372)

RichHTML

9

PDF (PC)

316

Abstract:

Aiming to deal with the problem that continuous numerical attributes in transaction database were difficult to divide and the efficiency of rule extraction was low, a multi-objective co-evolutionary quantification association rule extraction method was proposed with the cooperative of crossover population and mutation population. The non-dominated sorting of the Pareto principle was used to optimize the individuals of population. Genotype and phenotype of individuals similarity were used to control the matching of individuals in the crossover population. The mutation population was segmented by the concept of level set, then, single point mutation and multiple point mutation were adopted according to the quality of individuals to enhance the individuals diversity. The pareto optimal solution set was obtained from the elite population which was used to preserve the excellent individuals in the crossover population and the mutation population. The simulation results on different datasets showed that the algorithm achieved a good balance of performance and quantity, and the data set was effectively covered, which verifies the effectiveness and feasibility of the algorithm.

Key words: multi-objective, co-evolutionary, non-dominated, similarity, level set

CLC Number: 

  • TP311.13

Table 1

The encoding of chromosomes"

A1 A2 Ai AN
T1 LB1 UB1 T2 LB2 UB2 Ti LBi UBi TN LBN UBN

Fig.1

The evolution model of crossover population"

Fig.2

The evolution model of mutation population"

Fig.3

The model of algorithm"

Table 2

The evolutionary parameter of genetic algorithm"

种群大小 PCx PCn Pm 迭代次数
50 0.99 0.5 0.2 200

Table 3

The description of some datasets"

数据集 记录个数 属性个数 目标属性
Basketball 96 5 Points per minute
Bodyfat 252 18 Body height
Quake 2 178 4 Richter

Table 4

Some rules extracted from the Basketball dataset"

规则序号 规则前件 规则后件 置信度 可理解度 兴趣度
1 assists_per_minute∈(0.177 4, 0.337 8) height∈(159.011 7, 193.104 2)
points_per_minute∈(0.087 3, 0.773 9)		 1 0.792 5 0.302 3
2 assists_per_minute∈(0.148 1, 0.291 6) height∈(154.136 8, 188.847 5)
time_played∈(5.578 0, 43.171 3)
age∈(22.613 6, 36.458 2)
points_per_minute∈(0.214 7, 0.691 7)		 0.641 5 0.898 2 0.352 2
3 Height∈(169.988 1, 185.075 1) assists_per_minute∈(0.154 6, 0.359 5)
age∈(22.613 6, 36.458 2)
points_per_minute∈(0.214 7, 0.691 7)		 0.931 0 0.861 4 0.354 3

Fig.4

The mean value of confidence varies with the number of iterations"

Fig.5

The mean value of comprehensibility varies with the number of iterations"

Fig.6

The mean value of interestingness varies with the number of iterations"

Table 5

The mean value of support and size of extracted rules"

数据集 支持度/% 规则大小
MODENAR RPSO GAR MOGAR REM_MOCGA MODENAR RPSO GAR MOGAR REM_MOCGA
Basketball 37.20 36.44 36.69 50.82 46.93 3.21 3.21 3.38 3.24 3.83
Bodyfat 65.22 65.22 65.26 57.22 41.17 6.87 7.06 7.45 6.96 7.90
Quake 39.86 38.74 38.65 30.12 47.69 2.03 2.22 2.33 2.38 3.12

Table 6

The number and the mean value of confidence about extracted rules"

数据集 提取规则数量 置信度/%
MODENAR RPSO MOGAR REM_MOCGA MODENAR RPSO MOGAR REM_MOCGA
Basketball 48.0 34.2 50 152.3 61±2.1 60±2.8 83 88±2.9
Bodyfat 52.4 46.4 84 311.4 62±3.2 61±1.8 85 85±2.3
Quake 55.4 46.4 44.87 332.6 63±2.8 63±2.8 82 92±3.4

Table 7

The mean value of coverage about extracted rules"

%
数据集 MODENAR RPSO GAR MOGAR REM_MOCGA
Basketball 100.00 100.00 100.00 100.00 100.00
Bodyfat 86.11 86.11 86.00 93.52 97.22
Quake 88.9 87.92 87.5 91.07 99.68
1 SRIKANT R , AGRAWAL R . Mining quantitative association rules in large relational tables[J]. ACM SIGMOD Record, 1996, 25 (2): 1- 12.
doi: 10.1145/235968
2 HAN Jiawei , PEI Jian , YIN Yiwen , et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8 (1): 53- 87.
3 HU Yichung , CHEN Rueyshun , TZENG Gwohshiung . Discovering fuzzy association rules using fuzzy partition methods[J]. Knowledge-Based Systems, 2003, 16 (3): 137- 147.
doi: 10.1016/S0950-7051(02)00079-5
4 CAO Hui, SI Gangquan, ZHANG Yanbin, et al. A density-based quantitative attribute partition algorithm for association rule mining on industrial database[C]//2008 American Control Conference. Seattle, USA: IEEE, 2008: 75-80.
5 KAYAA M , ALHAJJB R . Genetic algorithm based framework for mining fuzzy aAssociation rules[J]. Fuzzy Sets & Systems, 2005, 152 (3): 587- 601.
6 周丽娟, 石倩, 葛学彬, 等. 基于聚类的模糊遗传挖掘算法的研究[J]. 计算机工程与应用, 2010, 46 (13): 118- 121.
doi: 10.3778/j.issn.1002-8331.2010.13.035
ZHOU Lijuan , SHI Qian , GE Xuebin , et al. Cluster-based evaluation in fuzzy-genetic data mining[J]. Computer Engineering & Applications, 2010, 46 (13): 118- 121.
doi: 10.3778/j.issn.1002-8331.2010.13.035
7 HONG Tzungpei , CHEN Chunhao , WU Yulung , et al. A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions[J]. Soft Computing, 2006, 10 (11): 1091- 1101.
doi: 10.1007/s00500-006-0046-x
8 ALCALÁ-FDEZ J , ALCALÁ R , GACTO M J , et al. Learning the membership function contexts for mining fuzzy association rules by using genetic algorithms[J]. Fuzzy Sets & Systems, 2009, 160 (7): 905- 921.
9 PALACIOS A M , PALACIOS J , LU IS , et al. Genetic learning of the membership functions for mining fuzzy association rules from low quality data[J]. Information Sciences, 2015, 295 (C): 358- 378.
10 JESUS M J D , GÁMEZ J A , GONZÁLEZ P , et al. On the discovery of association rules by means of evolutionary algorithms[J]. Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, 2011, 1 (5): 397- 415.
11 ASHISH Ghosh , BHABESH Nath . Multi-objective rule mining using genetic algorithms[J]. Information Sciences, 2004, 163 (1/2/3): 123- 133.
12 ALATAS B , AKIN E . Rough particle swarm optimization and its applications in data mining[J]. Soft Computing, 2008, 12 (12): 1205- 1218.
doi: 10.1007/s00500-008-0284-1
13 ALATAS B , AKIN E , KARCI A . MODENAR: Multi-objective differential evolution algorithm for mining numeric association rules[J]. Applied Soft Computing, 2008, 8 (1): 646- 656.
14 MINAEI-BIDGOLI B , BARMAKI R , NASIRI M . Mining numerical association rules via multi-objective genetic algorithms[J]. Information Sciences, 2013, 233 (2): 15- 24.
15 DEB K , PRATAP A , AGARWAL S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions Evolutionary Computation, 2002, 6 (2): 182- 197.
16 吴琼, 曾庆鹏. 基于多目标烟花算法的关联规则挖掘[J]. 模式识别与人工智能, 2017, 30 (4): 365- 376.
WU Qiong , ZENG Qingpeng . Association rules mining based on multi-objective fireworks optimization algorithm[J]. Pattern Recognition and Artificial Intelligence, 2017, 30 (4): 365- 376.
17 SHANG Ronghua , WANG Yuying , WANG Jia , et al. A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem[J]. Information Sciences, 2014, 277 (2): 609- 642.
18 MEHTA S B , CHAUDHURY S , BHATTACHARYYA A , et al. Tissue classification in magnetic resonance images through the hybrid approach of michigan and pittsburg genetic algorithm[J]. Applied Soft Computing, 2011, 11 (4): 3476- 3484.
doi: 10.1016/j.asoc.2011.01.021
19 NASIRI M , TAGHAVI L S , MINAEE B . Numeric multi-objective rule mining using simulated annealing algorithm[J]. Journal of Convergence Information Technology, 2011, 5 (1): 60- 68.
20 MATA J, ALVAREZ J, RIQUELME J. Discovering numeric association rules via evolutionary algorithm[C]// Advances in Knowledge Discovery and Data Mining. Berlin, Germany: Springer, 2002: 40-51.
[1] LIN Jianghao, ZHOU Yongmei, YANG Aimin, CHEN Jin. Building of domain sentiment lexicon based on word2vec [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 40-47.
[2] CUI Xiaosong, WANG Ying, MENG Jia, ZOU Li. Online business self-evaluation system based on linguistic-valued similarity reasoning [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(1): 1-7.
[3] WANG Fei, XU Jian, LI Wei, WANG Xinhao, SHI Xiaohan. Rolling optimal dispatch method of wind power based on distributed energy storage system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(6): 89-94.
[4] SONG Yang, ZHONG Maiying. Fault isolability analysis based on improved distance similarity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 103-109.
[5] PANG Renming, WANG Bo, YE Hao, ZHANG Haifeng, LI Mingliang. Clustering of blast furnace historical data based on PCA similarity factor and spectral clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 143-149.
[6] LI Zhenwei, CUI Guozhong, GUO Congzhou, YU Changhao. Blind image restoration using alternating direction method of multipliers [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 14-18.
[7] PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, CHEN Menghui. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 25-30.
[8] HAO Chongqing, WANG Zhihong. Classification and analysis of epileptic EEG based on complex networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 8-15.
[9] REN Yongfeng, DONG Xueyu. An image saliency object detection algorithm based on adaptive manifold similarity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 56-62.
[10] ZHANG Li, XIA Peipei, LI Fanzhang. A method based on cosine similarity in supplier selection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 1-6.
[11] WANG Zhiqiang, WEN Yimin, LI Fang. Collaborative recommendation for scenic spots based on multi-aspect ratings [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 54-61.
[12] DENG Guanlong, YANG Hongyong, ZHANG Shuning, GU Xingsheng. Multi-objective scheduling in no-wait flow shop using a hybridized differential evolution algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 21-28.
[13] LIN Yaojin, ZHANG Jia, LIN Menglei, WANG Juan. A method of collaborative filtering recommendation based on fuzzy information entropy [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 13-20.
[14] ZHONG Zhiyan, WEN Zhiqiang, ZHANG Xiaoyun, YE Degang. Neighborhood similarity descriptor used in halftone image [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 58-64.
[15] LIU Chen, CAI Ting. A localization algorithm based on RSSI vector for wireless sensor networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 23-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Su-yu,<\sup>,AI Xing<\sup>,ZHAO Jun<\sup>,LI Zuo-li<\sup>,LIU Zeng-wen<\sup> . Milling force prediction model for highspeed end milling 3Cr2Mo steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 1 -5 .
[2] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[3] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[4] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[5] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[6] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
[7] SUN Dianzhu, ZHU Changzhi, LI Yanrui. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 84 -86 .
[8] LI Fangjia, GAO Shangce, TANG Zheng*, Ishii Masahiro, Yamashita Kazuya. 3D similar pattern generation of snow crystals with cellular automata[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 102 -105 .
[9] BO De-Yun, ZHANG Dao-Jiang. Adaptive spectral clustering algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 22 -26 .
[10] LI Shan-ping,ZHAO Yu-xiao,QIAO Peng,FENG Zheng-zhi . Cultivation of aerobic granular sludge and the kinetics of substrate degradation and biomass growth[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 95 -98 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd