This Website contains complementary material to the paper:

D. Martín, J. Alcalá-Fdez, A. Rosete and F.Herrera, NICGAR: a Niching Genetic Algorithm to Mine a Diverse Set of Interesting Quantitative Association Rules. Information Sciences 355-356 (2016) 208-228. DOI: 10.1016/j.ins.2016.03.039

Summary:

1. Flowchart of the algorithm
2. Experimental Framework
   1. Data-sets used in the paper
   2. Algorithms analyzed
3. Results obtained
   1. Results obtained in the comparison with other NGAs
   2. Results obtained in the comparison with mono-objective and multi-objective evolutionary approaches
   3. Comparison with classical algorithms

Flowchart of the algorithm

NICGAR can be summarized as follows:

• Input: Population size N, number of evaluations nTrials, probability of mutation P_mut, factor of amplitude for each attribute of the dataset ρ, difference threshold α, niching threshold Nich_Min, quality threshold Ev_Min.
• Output: External population (EP)

1. Initialize
   1. Generate the initial population (P_t) with N chromosomes.
   2. Evaluate the initial population.
2. Generate the offspring population (Q_t) as follows.
   1. Two parent individuals x₁ and x₂ are selected by binary tournament selection using the fitness function.
   2. Generate two offspring applying the crossover operator on the individuals x₁ and x₂. Next, the offspring are mutated and repaired using the appropriate operators.
   3. The offspring is evaluated.
   4. If the EP is not empty, the punishment mechanism is applied to each new individual if they belong to a niche from the EP and their fitness is lower than its corresponding solution of the EP.
3. Join the parents with their offspring and select the best N individuals to take part in the next population (P_t+1).
4. If the difference between the current population and the previous population is less than α%:
   1. Update the EP, based on the niches from P_t+1.
   2. Restart the population and apply the punishment mechanism to the new individuals that have been created in the restarting process.
5. If the maximum number of evaluations is not reached, go to Step 2.
6. Update the EP, based on the niches from the last population.
7. The EP is returned.

A scheme of this algorithm is shown in the Figure 1.

Figure 1. Scheme of the algorithm NICGAR.

Experimental Framework

Data-sets used in the paper

Table 1 describes the 27 real-world datasets that have been used in this experimental study, where "Attributes(R/I/N)" is the number of attributes (Real/Integer/Nominal) in the data, "Examples" is the number of examples and "Download" contains a link for downloading each data-set in the KEEL format. You may also download all data-sets by clicking here. Moreover, the datasets are available in the repository KEEL-dataset, where they can be downloaded (available at KEEL-dataset Repository).

Table 1: Summary of the datasets considered for the experimental study

Dataset	Attributes(R/I/N)	Examples	Download
Balance Scale	5 (5/0/0)	625
Basketball	5 (3/2/0)	96
Bolts	8 (2/6/0)	40
Coil2000	86 (0/86/0)	9822
Fars	29 (5/0/24)	100968
House_16H	17 (10/7/0)	22784
Ionosphere	34 (32/1/1)	351
Letter	16 (0/16/0)	20000
Magic	11(10/0/1)	19020
Movement Libras	91 (90/0/1)	360
Optdigits	65 (0/65/0)	5620
Penbased	16 (0/16/0)	10992
Pollution	16 (16/0/0)	60
Quake	4 (3/1/0)	2178
Satimage	37 (0/37/0)	6435
Segment	20 (19/1/0)	2310
Sonar	61 (60/0/1)	208
Spambase	58 (57/1/0)	4597
Spectfheart	45 (0/45/0)	267
Stock Price	10 (10/0/0)	950
Stulong	5 (5/0/0)	1419
Texture	41 (40/1/0)	5500
Thyroid	22 (6/16/0)	7200
Vehicle	19 (0/18/1)	846
Wdbc	31 (30/0/1)	569
Wine	14 (13/1/0)	178
Vowel	14 (10/4/0)	990

Algorithms analyzed

In these experiments, we compare the proposed approach with seven other algorithms, which are available from the KEEL software tool. A brief description of these algorithms follows.

• Clearing: This Niching Genetic Algorithm is one of the most popular niching techniques used in conjunction with the evolutionary computation community. This method is based on limited the resources within subpopulations of similar individuals, where only the best individuals of each niche will survive since the fitness of the rest of them will be reset to zero. This process is applied after evaluation process and before the selection.
• Adaptive Species Conservation Genetic Algorithm (ASCGA): This algorithm is based on the species conservation approach (SCGA) proposed by Li, it divides the population into several species according to their similarity and each of these species is built around a dominating individual, commonly referred to as a species seed. This method automatically adjust species parameters and allow the species to adapt to an optimization problem.
• Evolutionary Association Rules Mining with Genetic Algorithm (EARMGA): This algorithm uses a GA to identify QARs. Each chromosome encodes a generalized k-rule, where k indicates the desired length. The most interesting rules are returned according to the interestingness measure defined by the fitness function, which is based on the support of the rule and its antecedent and consequent support. The proposed GA performs a dataset-independent approach that does not rely upon the minSup threshold.
• GENetic Association Rules(GENAR): This algorithm uses a GA to mine association rules in numeric datasets. Each chromosome encodes an association rule, containing maximum and minimum intervals of each numeric attribute. The length of the rules is always fixed to the number of attributes, only the last attribute forms the consequent. The objective function considers the number of records covered by the rule and penalizes those which have already covered the same records in the dataset.
• Genetic Association Rules (GAR): This algorithm is an extension of GENAR, which searches for frequent itemsets in numeric datasets without needing to discretize the attributes. Each chromosome is a k-itemset, in which each gene represents the maximum and minimum values of the attributes that belong to the k-itemset. This algorithm finds frequent itemsets, and it is therefore necessary to run another procedure afterwards in order to generate association rules.
• Genetic algorithm for automated mining of both positive and negative quantitative association rules (Alatasetal): This algorithm designs a GA, which does not require a user-specified the minSup and minConf thresholds, to simultaneously search for intervals of quantitative attributes and to discover PNQARs that these intervals conform to in a single run. The chromosomes represent rules, in which each gene has four parts.
• QAR-CIP-NSGA-II: This method mines a set of QARs with a good trade-off between interpretability and accuracy, which maximizes three objectives: comprehensibility, interestingness and performance, understanding by performance the product of Certainty Factor (CF) and support. This algorithm extends the well-known MOEA NSGA-II to perform an evolutionary learning of the intervals of the attributes and a condition selection for each rule.
• MOPNAR: This algorithm extends the MOEA based on decomposition MOEA/D-DE to obtain a reduced set of PNQARs with a good trade-off between the number of rules, support and coverage of the dataset. It performs a condition selection and an evolutionary learning of the intervals of the attributes for each rule, maximizing three objectives: comprehensibility; interestingness and performance.
• Apriori: Apriori follows a breadth-first strategy. It generates candidate itemsets for the current iteration by means of itemsets considered to be frequent in the previous iteration. It then enumerates all the subsets for each transaction and increments the support of candidates matching them. Then, those that have the user-specified minSup are marked as frequent for the next iteration. This process is repeated until all frequent itemsets have been found. Finally, Apriori uses the frequent itemsets to generate positive rules with confidence greater than minimum confidence.
• Eclat: Eclat employs a depth-first strategy. It generates candidates by extending the prefixes of an itemset until an infrequent one is found. In such cases, it simply backtracks to the previous prefix and then recursively applies the above procedure. Unlike Apriori, for all the items in a dataset, it first constructs a list of all the transaction identifiers (tid-list) containing that item. Then it counts the support by merely intersecting two or more tid-lists to check whether they have items in common. If so, the support is equal to the size of the resulting set. The process for generating the positive rules is the same as Apriori.

Results obtained

This section is divided into three parts: the first part provides the results of the comparison with two NGAs extended to extract PNQARs. Next, the second part shows the results of the comparison with other mono-objective and multi-objective evolutionary approaches. Finally, in the third part, the performance results of our algorithm again two classical algorithms can be found.

Results obtained in the comparison with other NGAs

In this section, we present the performance results obtained of our algorithm against Clearing and ASCGA. Table 2 shows the average results obtained of 5 runs for each dataset.

Moreover, this performance results are available for download in xls, pdf and tex files by clicking the links , and , respectively.

Results obtained in the comparison with mono-objective and multi-objective evolutionary approaches

In this section, we present the results obtained by our algorithm against four mono-objective evolutionary algorithms (EARMGA, GAR, GENAR and Alatasetal) and two multi-objective evolutionary algorithms (QAR-CIP-NSGA-II and MOPNAR). Table 3 and Table 4 show the average results obtained by the mono-objectives and the multi-objectives evolutionary approaches of 5 runs for each dataset, respectively.

Moreover, this performance results are available for download in xls, pdf and tex files. To download the results obtained by the mono-objective evolutionary algoritmhs, click the links by clicking the links , and and for the ones obtained by the multi-objective evolutionary algorithms, click the links , and .

Results obtained in the comparison with classical algorithms

In this section, we present the results obtained by our algorithm against two classical algorithms (Apriori and Eclat). Table 5 shows the average results obtained of 5 runs for each dataset. Notice that we only show the results obtained by the Apriori and Eclat algorithms over 15 datasets due to the fact that they present scalability problems and cannot run in all datasets.

Finally, this performance results are available for download in xls, pdf and tex files by clicking the links , and , respectively.

Page Maintained by D.Martín and J. Alcalá-Fdez