2.1. Formal definitions

The mining of valuable and previously unknown association rules in a database might produce a large amount of different solutions, giving rise to a hard process of analysing each single rule. Besides, a large percentage of this set of solutions may be uninteresting and useless, being the user responsible for reducing the output by means of a process of quantifying the association rules²⁴. To solve this issue, different quality measures (see Table 1) based on the analysis of the statistical properties of data have been proposed by different authors^4,21.

The principal element in association rule mining is the pattern P, which is defined as a subset of the whole set of items I = {i₁,i₂,…,i_l} in a dataset Ω, i.e. P = {i_j,…,i_k} ⊆ I, 1 ≤ j,k ≤ l. An association rule is an implication of the form X → Y that is formed from P in such a way that the antecedent X is defined as X ⊂ P, whereas the consequent Y is denoted as Y = P \ X. Any existing quality measure in this field is based on the number of transactions in the dataset satisfied by the rule (denoted as n_xy), the antecedent (n_x), and the consequent (n_y). All these values (n_xy, n_x and n_y) can also be represented as relative frequencies, by considering the number n of transactions in data, in per unit basis:

• p_xy = n_xy/n; p_xӯ = n_xӯ/n; px¯y=nx¯y/n; pxy¯=nxy¯/n;

• px=pxy+pxy¯=1−px¯;py=pxy+px¯y=1−py¯;

• px¯=px¯y+pxy¯=1−px; and py¯=pxy¯+pxy¯=1−py.

Support² is the most well-known quality measure in association rule mining. It is defined as the relative frequency of occurrence of an association rule X → Y, i.e. Support(X → Y) ≡ p_xy. Symmetry is a major feature of this quality measure, i.e. Support(X → Y) = Support(Y → X), so it does not quantify any implication between the antecedent X and the consequent Y. Additionally, the minimum and maximum values for this quality measure are 0 and 1, respectively. However, an association rule is considered as misleading if one of these two values is obtained. Thus, in situations where p_xy = 1, then the rule is useless since it appears in any transaction so it does not provide any new knowledge about the data properties. On the contrary, if p_xy = 0, then the rule does not represent any transaction so it is considered as misleading. This last situation might be caused by the two following issues: (a) p_x = 0 or p_y = 0, so both X and Y do not have any transaction satisfied in common; (b) either the antecedent X and the consequent Y satisfy up to 50% of the transactions within the dataset, i.e. p_x ≤ 0.5 and p_y ≤ 0.5, but they do not satisfy any transaction in common. An important property of the Support quality measure is that it is always greater than 0 when p_x + p_y > 1, and its maximum value is always equal to the minimum value among p_x and p_y, i.e. p_xy ≤ Min{p_x, p_y}.

Coverage and Prevalence²¹ quality measures are defined as the Support on the basis of the antecedent X or the consequent Y, respectively. Coverage, defined as p_x, determines the percentage of transactions where the antecedent X appears. On the contrary, the Prevalence quality measure, i.e. p_y, determines the percentage of transactions where the consequent Y appears. It is noteworthy that, similarly to Support, these two quality measures operate in the range [0,1].

Confidence is a quality measure that appears in most of the problems where the mining of association between patterns is a dare²⁶. This quality quality measure is defined as the percentage of transactions in a dataset containing X and, at the same time, also Y. In a formal way, this quality measure can be expressed as Confidence(X → Y) = p_xy/p_x, or as an estimate of the conditional probability P(Y|X). It should be highlight that Confidence quality measure operates on the interval [0,1] and it is not symmetric, i.e. Confidence(X → Y) ≠ Confidence(Y → X), denoting implication between X and Y. However, it is possible to obtain that Confidence(X → Y) = Confidence(Y → X) in situations where p_x = p_y regardless the p_xy value.

Lift (also called interest)⁵ is one of the many alternative quality measures proposed by different authors. This quality measure calculates the relationship between the Confidence of the rule and its Prevalence. As shown in Table 1, Lift quality measure is described as Lift(X → Y)= p_xy/(p_x × p_y), or also as Lift(X → Y) = Confidence(X → Y)/p_y. This measure calculates a ratio between the joint probability of two observing variables (antecedent X and consequent Y) with respect to their probabilities under the independence assumption. Lift may produce invalid results when p_x or p_y is equal to 0, i.e. Lift(X → Y) = 0/0. Otherwise, Lift is defined within the range [0,n] and it is symmetric. The minimum value is obtained when p_xy = 0 and p_x ≠ 0 and/or p_y ≠ 0, whereas the maximum value is obtained when p_xy = p_x = p_y = 1/n (only one transaction is satisfied within the dataset). This measure may also be defined as a correlation measure, calculating the degree of dependence between the antecedent and consequent of a rule. Lift values lower than 1 determine a negative dependence (positive dependence for values greater than 1), whereas a value of 1 stands for independence.

Cosine (also called IS)²¹ is a quality metric derived from Lift. Cosine is formally defined as Cosine(X→Y)=Lift×Support=pxy/px×py. It is similar to Lift measure with the difference of the square root which is taken on the product of the probabilities p_x and p_y (denominator of the equation). This square root means that Cosine is possible only influenced by p_x, p_y and p_xy, but not by the total number of transactions |Ω|. This quality measure ranges the values in [0,1], since it is defined as the geometric mean of Confidence, which also ranges in the same space of values. Finally, it should be highlight that Cosine quality measure includes the following properties: (a) it takes into account both the interestingness and the significance of an association rule since it contains two important quality measures in this sense, i.e. Support and Lift; (b) it is equivalent to the geometric mean of Confidence, i.e. Cosine=Lift×Support=pxy2/(px×py), which can also be described as Cosine(X→Y)=Confidence(X→Y)×Confidence(Y→X); (c) similarly to Lift, Cosine does not quantify any implication between the antecedent X and consequent Y, i.e. Cosine(X → Y) = Cosine(Y → X).

Leverage was proposed by Piatetsky-Shapiro¹⁹ as a quality measure quite similar to Lift. Leverage determines how different is the co-occurrence of the antecedent X and the consequent Y of a rule from independence¹⁰. This quality measure, also known as novelty³, is formally defined as Leverage(X → Y)=p_xy − (p_x × p_y), and it takes values in the range [−0.25,0.25], denoting a zero value in those cases where the antecedent X and consequent Y are statistically independent. Finally, similarly to Support, Lift and Cosine quality measures, Leverage also includes symmetry as an important property, i.e. Leverage(X → Y) = Leverage(Y → X).

Conviction⁵ was proposed as a way of representing the degree of implication of a rule, and values far from the unity indicate interesting rules. This quality measure (see Table 1) is formally defined as Conviction(X → Y)=(p_x × p_ӯ)/p_xӯ, which can also be defined as Conviction(X → Y)=(p_x − (p_x × p_y))/(p_x − p_xy). Conviction takes values in the range [1/n,n/4]. Whereas lower bound is reached when p_x = p_ӯ = p_xӯ since p_x = 0 produces an indetermination, the upper bound is reached when p_x = p_ӯ = 0.5 and p_xӯ = 1/n.

Centered Confidence (CC)¹⁰, also called relative accuracy or gain is formally defined as gain(X → Y) = Confidence(X → Y) − p_y). As shown in Table 1, the centered Confidence measure produces values in the range [−1,1 − 1/n], being impossible to produce a value equal to unity. Note that the maximum feasible value is achieve when p_y is minimum and Confidence(X → Y) is maximum. The minimum feasible value of p_y is p_y = 1/n since 0 values does not produce maximum Confidence values, i.e. p_y = 0 = p_xy so Confidence(X → Y) = 0. Hence, the maximum value for the centered Confidence or gain is equal to gain(X → Y) = 1 − 1/n, when p_xy = p_x and p_y = 1/n.

Other quality measures have been proposed by many authors as interesting quality measures to be considered. Even when almost all the existing works in the association rule mining field include, at least, one of the aforementioned quality measures, there are many other additional measures that might be used in different scenarios (see Table 1) including the following: certainty factor (CF)⁴ is defined as the gain normalized into the interval [−1,1], i.e. CF(X → Y) = gain(X → Y)/p_ӯ if gain(X → Y) ≥ 0), and CF(X → Y) = gain(X → Y)/p_y if gain(X → Y) < 0); Recall⁸ (Recall(X → Y) = p_xy/p_y) is denoted as the percentage of transactions in a database containing Y and, at the same time, also X; Laplace measure⁸ is formally stated as Laplace(X → Y) = (n_xy + 1)/(n_x + 2) and it can be transformed to (p_xy × n + 1)/(p_x × n + 2); pearson’s correlation coefficient¹¹, which is defined as (pxy−(px×py))/px×py×px¯×py¯; information gain (IG)¹¹, denoted as log(p_xy/(p_x × p_y)) and taking values in the range [log(1/n), log(n)]; Sebag and Schoenauer¹¹ proposed a quality measure defined as p_xy/p_xӯ=p_xy/(p_x − p_xy); least contradiction (LC)⁸, which is formulated as (p_xy − p_xӯ)/p_y; example and counterexample rate (ECR)⁸, defined as 1 − (p_xӯ/p_y); the metric proposed by Zhang et al.²⁶ and denoted as (pxy−(px×py))/Max{pxy×px¯,pxy×pxy¯}; netconf²² described as a measure to estimate the strength of an association rule, and defined as (p_xy −(p_x × p_y))/(p_x × (1 − p_x)); yule’sQ²² as (pxy×pxy¯−pxy¯×px¯y)/(pxy×pxy¯+pxy¯×px¯y).

2.2. Properties of quality measures

As previously described, many objective quality measures have been proposed in the literature to quantify the interest of the knowledge extracted. The analysis of these measures is not trivial and many different and opposed properties have been considered by different researchers, denoting that these properties can be divided into two main different sets, i.e. the one proposed by Piatetsky-Shapiro¹⁹ and the one of Tan et al.²².

Piatetsky-Shapiro¹⁹ suggested that any quality measure ℳ defined to quantify the interest of an association rule should verify three specific properties in order to separate strong and weak rules so high and low values can be assigned, respectively. These properties are described below and Table 2 summarizes which quality measure satisfies each of the three properties. The first property (P1) states that an association rule which occurs by chance has zero interest value, that is, it is not interesting. P1 claims that any quality measure ℳ should test whether X and Y are statistically independent, denoting that ℳ (X → Y) should be 0 when p_xy = p_x × p_y. Property number two (P2) states that the greater the Support, the greater the interestingness value when the Support for X and Y is fixed, that is, the more positive correlation X and Y have, the more interesting the rule. Here, ℳ (X → Y) monotonically increases with p_xy when p_x and p_y remain the same. The third property (P3) states that if the Supports for the rule and Y (or X) are fixed, the smaller the Support for X (or Y), the more interesting the pattern. Considering P3, ℳ (X → Y) monotonically decreases with p_x or with p_y when other parameters remain the same, i.e. p_xy and p_x or p_y remain unchanged.

Tan et al.²² proposed a different set of properties based on operations for 2x2 contingency tables. The five proposed properties are described below and all the aforementioned quality measures have been tested regarding these five properties (see Table 2). The first property (O1) is related to the symmetry under variable permutation. In this sense, a measure ℳ satisfies this property if and only if ℳ (X → Y) = ℳ (Y → X). The second property (O2) determines invariance when we scale any row or column by a positive factor. Property number three (O3) describes the antisymmetry under row/column permutation. A normalized measure ℳ is antisymmetric under the row permutation operation if ℳ (T^R)=-ℳ (T), considering T as the table of frequencies and T^R as the table of frequencies with a permutation on the rows; whereas the measure ℳ is antisymmetric under the column permutation operation if ℳ (T^C)=-ℳ (T), considering T^C as the table of frequencies with a permutation on the columns. According to the authors²² measures that are symmetric under the row and column permutation operations do not distinguish well between positive and negative correlations so it should be careful when using them to evaluate the interestingness of a pattern. Analysing the O3 property, it is stated that ℳ (X → Y) = −ℳ (X → ¬Y) = −ℳ (¬X → Y), so it means that the measure can identify both positive and negative correlations. Property O4 states that ℳ (X → Y) = ℳ (¬X → ¬Y), so property O3 is in fact a special case of this one, i.e. O4. Note that when permuting the rows (columns) causes the sign to change once and permuting the columns (rows) causes it to change again, so the overall result of permuting both rows and columns will be to leave the sign unchanged. The fifth property (O5) states that the measure ℳ should only take into account the number of records containing X, Y, or both. O5 is a null invariance property, denoting that if we change just the values of pxy¯, the measure remains the same.

As a summary, Table 2 shows that there are six quality measures (Leverage, centered Confidence, certainty factor, pearson, information gain and yule’sQ) that satisfy the three properties proposed by Piatetsky-Shapiro¹⁹. According to the set of properties provided by Tan et al.²² there are three measures (Leverage, pearson and yule’sQ) that satisfy a higher number of properties. However, it is noteworthy that not all the properties are required to be satisfied. For instance, in association rule mining, it is of high interest to determine the implication, not the co-occurrence, so property O1 is not desirable. Note that a measure ℳ satisfies O1 if and only if ℳ (X → Y) = ℳ (Y → X). Hence, even when Leverage quality measure seems to be a really good metric (it satisfies almost all the properties), it does not provide implication (Leverage(X → Y) = Leverage(Y → X)) so it should be used together with other quality measure¹⁸ that provide implication (O1 property should not be satisfied), e.g. Confidence.

2.3. Relationships between the most well-known quality measures

The analysis of existing quality measures, which score the interest of any association rule, is cornerstone to ease the process of choosing the right metric. In this regard, many different quality measures have been proposed along the years, but the simultaneous optimization of all measures is complex and might lead to poor results. The selection of which quality measure should be optimized is of high importance, determining which kind of rules will be extracted. Additionally, to analyse the existing relationships among measures is essential since the maximization of a specific measure could imply the optimization of many more in the best case scenario. With this aim, and considering Support and Confidence as the basic pillars of any good quality measure², it is of high interest to mathematically describe the relationship between different metrics and Support/Confidence. Here, the most widespread quality measures (Support, Confidence, Lift, Cosine, Leverage and Conviction) in the association rule mining field²⁴ are considered.

Support/Confidence.

First, it is appealing to determine the existing relationship between Support and Confidence quality measures (see Figure 1). Note that the shaded region illustrates the feasible area in which any association rule can obtain the values. In order to understand the aforementioned relationship, it should be noted that p_xy ≤ Min{p_x, p_y}, and p_xy ≤ p_x. Thus, given a value p_xy, then p_x will have a value in the range p_x ∈ [p_xy, 1].

Fig. 1.

Relationship between Support and Confidence.

According to the previous information, p_xy/p_x ≥ p_xy so it is possible to assert that Confidence(X → Y) is always greater or equal to Support(X → Y). As shown in Figure 1, it is not possible to obtain a high Support value and a low Confidence value at the same time, and this information is essential to be known beforehand. Hence, this analysis reveals that a high co-occurrence (high values of p_xy) implies a high implication (high values of p_xy/p_x), whereas a high implication does not imply a high co-occurrence.

Lift vs Support/Confidence.

As it is illustrated in Figure 2, for any Support value p_xy and considering Lift values lower than unity, then Lift increases when Support also does. On the contrary, when considering Lift values greater than unity, then Lift increases when Support decreases. In fact, high Support values tend to produce Lift values around unity, implying an independence between antecedent and consequent of the rule. Finally, it should be noted that Support values equal to unity implies Lift values close to unity, but the opposite is not necessarily true. This information is essential to be known in advance, so any user or expert knows that it is not possible to optimize both Support and Lift (high values) at time.

Fig. 2.

Relationship between Lift and Support.

Analysing the existing relationship between Confidence (p_xy/p_x) and Lift (p_xy/(p_x × p_y)), it is possible to define Lift on the basis of Confidence as Lift(X → Y)= Confidence(X → Y)/p_y. Lift quality measure produces maximum values when p_y is minimum, i.e. p_y = 1/n, so the maximum values for this quality measure is obtained as Lift_max(X → Y)= Confidence(X → Y) × n. On the contrary, Lift produces minimum values when p_y is maximum, i.e. p_y = 1, so the minimum values for Lift quality measure is obtained as Lift_max(X → Y)= Confidence(X → Y). This relationship is shown in Figure 3. As it is illustrated, for maximum Confidence values, i.e. Confidence(X → Y) = 1, then the Lift value will be in the range [1,n]. This analysis reveals that low Confidence values produce low Lift values (lower than unity), denoting a negative correlation. On the contrary, it is easy to obtain a positive correlation (positive Lift values) when Confidence produces high values (close to unity).

Fig. 3.

Relationship between Lift and Confidence.

Cosine vs Cupport/Confidence.

Comparing Support and Cosine values (see Figure 4) according to their definitions (see Table 1), it is obtained that any Support value (p_xy) may produce maximum Cosine values, and these maximum values are obtained in situations where p_xy = p_x = p_y.

Fig. 4.

Relationship between Support and Cosine.

On the contrary, minimum Cosine values are obtained when p_xy = p_x (or p_xy = p_y) and p_y = 1 (or p_x = 1). Both Support and Cosine behave almost equal to Support and Confidence. In this sense, it is not possible to obtain a high Support value and a low Cosine value at the same time (see Figure 4). This analysis reveals that high Support values imply high Cosine values, but the opposite is not true. Finally, comparing Cosine with Confidence (the feasible area is shown in Figure 5), it is obtained that almost any Confidence value may produce any Cosine value. Hence, both measures can be minimized/maximized at once.

Fig. 5.

Relationship between Confidence and Cosine.

Leverage vs Support/Confidence.

Leverage, defined as Leverage(X → Y) = p_xy − (p_x × p_y), determines how different is the co-occurrence of the antecedent X and the consequent Y of a rule from independence¹⁰. Similarly to the previous analyses, Figure 6 graphically shows how Support and Leverage are related, denoting that any association rule will obtain a Leverage value in the range [−0.25,0.25] and high Support values tend to produce Leverage values close to 0. The upper boundary of the feasible area is obtained when p_xy = p_x = p_y, so considering Support(X → Y) = p_xy the upper boundary is defined as Leverage(X → Y) = Support(X → Y) − Support²(X → Y). Continuing the analysis, it is obtained that low Support values tend to produce Leverage values lower than 0.

Fig. 6.

Relationship between Support and Leverage.

Finally, considering how Confidence is related to Leverage (see Figure 7), it is shown that high Confidence values tend to produce positive values for the Leverage quality measure. On the other hand, low Confidence values tend to produce negative values for Leverage. It is interesting to know beforehand that extremely high Confidence values cannot produce negative Leverage values, whereas extremely low Confidence values cannot produce positive Leverage values.

Fig. 7.

Relationship between Confidence and Leverage.

Conviction vs Support/Confidence.

As shown in Figure 8, Support and Conviction are related in such a way that the highest Conviction values are obtained for intermediate values of Support. Zero Support values (p_xy = 0) imply Conviction values defined as Conviction(X → Y)=(p_x − (p_x × p_y))/p_x=1 − p_y. Hence, p_xy = 0 implies a Conviction value in the range [0,1]. For p_y = 1 then Conviction(X → Y) = 0, whereas for p_y = 0 then Conviction(X → Y) = 1. On the contrary, maximum Support values, i.e. p_xy = 1, produces invalid Conviction results, since p_xy = p_x = p_y = 1 and Conviction(X → Y) = 0/0. Hence, it is required to know that no algorithm is able to obtain rules with huge Support values and huge Conviction values regardless the dataset used or the application field.

Fig. 8.

Relationship between Support and Conviction.

Considering now the relationship between Confidence and Conviction (see Figure 9), maximum Confidence values (p_xy/p_x = 1) produce invalid results since p_xy = p_x so Conviction(X → Y) = (1 − p_xy)/0. Finally, it should be noted that minimum Confidence values (p_xy/p_x = 0, p_xy = 0 and p_x ≠ 1) implies a Conviction value in the range [0,1]. From this analysis, it is revealed that no association rule can produce a low Confidence value and a high Conviction value at time.

Fig. 9.

Relationship between Confidence and Conviction.

3.1. Datasets

The experimental analysis has been carried out by considering a set of 30 varied and well-known datasets (see Table 3), which are publicly available at http://keel.es, as well as twenty quality measures widely used in the association rule mining field. Datasets were selected to be as varied as possible, including either continuous and discrete attributes, and comprising a diverse number of transactions. This diversity is a keystone since each quality measure may differently behave from dataset to dataset, so the higher the number of datasets, the more close to the reality are the results.

As shown in Table 3, the selected datasets comprise a number of attributes that varies from 5 to 64, whereas the number of transactions ranges from 14 to 12,960. Additionally, the datasets considered in this experimental analysis comprise either discrete and continuous attributes, and the proportion of discrete/continuous attributes varies from dataset to dataset.

3.2. Methodology

The huge number of existing objective quality measures prompts users to carry out an arduous process of choosing the most suitable metrics to be maximized by any algorithm, either exhaustive search or evolutionary methods. In order to get an idea of the role played by each quality measure in this optimization process, a deep analysis is required to determine how each measure behaves when others are optimized. In this regard, the experimental study requires to know beforehand the maximum feasible value for each dataset and quality measure. The previous knowledge of these maximum values eases the process of testing whether a specific quality measure is being optimized or not. It is noteworthy that the maximum value may be completely different from dataset to dataset depending on the data distribution and, therefore, sub-ranges of the ranges analysed in Table 1 should be considered.

Table 4 contains the maximum values for each dataset and quality measure, and it will serve as baseline for the experimental study performed in this work. Any value shown in Table 4 was obtained after running different association rule mining algorithms on each dataset, and keeping the maximum value obtained for each quality measure. In those datasets that only include discrete attributes, then a brute force algorithm⁹ was applied, which extracts any existing association rule, so the maximum value for each dataset can be surely obtained. However, this kind of algorithms cannot be applied to datasets comprising continuous attributes due to the huge search space. For these specific datasets, the extraction of the maximum value for each quality measure is not a trivial issue since each continuous attribute can be split into an undetermined number of bins. Hence, the same brute force algorithm⁹ was applied by transforming continuous attributes into a varied number of bins (equal-width and equal-frequency binning methods were applied, considering 5, 10, 15, 20, 25 and 30 bins). Additionally, different evolutionary algorithms (NICGAR¹⁵, EARMGA-A²⁵, ARMMGA²⁰, QuantG3P¹² and G3PARM¹³) that work with continuous attributes without a previous transformation were also considered. These algorithms, which were taken from KEEL²³ software tool, were specifically designed to work with continuous attributes and they have achieved a really good performance²⁴. As a result, the values shown in Table 4 are the maximum values obtained after applying all the aforementioned algorithms.

The methodology followed in this work is based on checking whether each quality measure is being optimized or not. We determine that a specific quality measure is being optimized if the results for this measure is close to the maximum value described in Table 4. For instance, let us consider the ankara weather dataset and a sample rule having the values for Support and Confidence equal to 0.90 and 0.92, respectively. In such a situation, it is possible to assert that both quality measures are optimized at time since the maximum values for both Support and Confidence measures are 1.00. Let us also consider now a sample rule on dataset nursery having the values for Support and Confidence equal to 0.32 and 0.98, respectively. In this situation, it is also possible to assert that the rule optimizes both quality measures at time since the maximum Support value is 0.33, and 1.00 for the Confidence metric for this specific dataset. Therefore, it demonstrates that the optimization testing should be carried out by considering the maximum values for each specific dataset and not only the maximum feasible values mathematically described in Table 2.

The empirical analysis is twofold: single and multiple objective optimization. As for single-objective optimization, the aim is to determine a single measure as objective to be optimized, and to test how the rest of measures behave. The process is repeated by each single quality measure. An exhaustive search algorithm⁹ and a set of evolutionary algorithms (NICGAR¹⁵, EARMGA-A²⁵, ARMMGA²⁰, QuantG3P¹² and G3PARM¹³) freely available in the KEEL²³ software tool was performed, and each algorithm was run 6,000 times — evolutionary algorithms are stochastic models so 10 different runs per dataset and per quality measure are required. Results are the average results obtained for the different runs and taking the top rules discovered, i.e. those having the highest value for the objective quality measure. We have taken a resulting set of 20 rules since this is the number most widely used by most of the evolutionary algorithms for discovering the top association rules²⁴. As for multi-objective optimization, two of the most well-known multi-objective optimization algorithms were used (NSGA2⁶ and SPEA2²⁷), and each one was run 57,000 times — they are stochastic algorithms so 10 different runs per dataset and per pair of quality measures (190 combinations of quality measures). Results are the average results obtained for the different runs and taking the resulting set of rules (the ones that achieve a good trade-off between two conflicting metrics) of each algorithm.

3.3. Single-objective optimization

In this first analysis, a single-objective optimization is performed by taking each sole quality measure as objective function each time. The aim is three-fold: first, to check which quality measure is maximized by a higher number of other quality measures; second, to determine which quality measure (used as a single objective function) allows a higher number of quality measures to be optimized (maximized) at time; finally, to analyse which set of quality measures should be used to maximize all the metrics. A specific quality measure is marked as optimized if it is close to the maximum value according to a specific percentile. As a matter of example, the Support quality measure whose values range in the interval [0.0,1.0] will be marked as optimized in the 90th percentile if a value is in the range [0.9,1.0].

First analysis.

Taking the aforementioned guidelines, the first goal is to check which quality measures is optimized by a higher number of objectives (single quality measures). As previously demonstrated, the percentile used to mark whether a quality measure has been optimized or not plays a really important role since minimum/maximum values changed from dataset to dataset. Hence, for the sake of doing a complete analysis, different percentiles (70th, 80th and 90th percentile) were considered. Results are summarized in Figure 10, which shows the percentage of objective functions that optimize each single quality. As it is illustrated, Confidence and ECR are optimized by almost 80% of the objective functions. Additionally, Zhang and CF (Certainty Factor) are also really general quality measures, since they are optimized by close to 70% of the objectives (single metrics). On the contrary, Support, Lift, Leverage, Conviction, IG, Sebag and Yule’sQ are high indepedent quality measures since they are hardly optimized by any other single metric.

Fig. 10.

Percentage of objective functions that optimize each quality measure by considering different percentiles (70th, 80th and 90th percentile).

Taking those quality measures (Confidence, CF, Laplace, ECR and Zhang) that are optimized by a higher number of fitness functions (single quality measures) according to the previous analysis summarized in Figure 10, the aim is to check the behaviour on each single dataset. In this sense, Table 5 shows the results for this analysis, stating that Confidence and ECR are optimized by around 80% of the quality measures regardless the dataset used and with a low dispersion. As for the Confidence quality measure, it is optimized by more than 70% of the quality measures for any dataset except for Treasury and Weather. The latter is, according to the results, the dataset in which the Confidence quality measure worst behaves since this measure is maximized by only 40% of the metrics.

Dataset	Confidence	CF	Laplace	ECR	Zhang
Ankara weather	0.85	0.55	0.65	0.85	0.55
Automobile	0.85	0.75	0.65	0.85	0.75
Bolts	0.85	0.70	0.75	0.85	0.70
Car	0.85	0.50	0.65	0.75	0.50
Chess	0.85	0.50	0.60	0.85	0.55
Cmc	0.80	0.70	0.65	0.80	0.70
Flare	0.70	0.65	0.75	0.70	0.70
German	0.75	0.80	0.75	0.75	0.90
Izmir weather	0.85	0.85	0.70	0.85	0.85
Marketing	0.80	0.80	0.65	0.80	0.85
Mushrooms	0.80	0.60	0.60	0.80	0.65
Nursery	0.80	0.70	0.50	0.80	0.70
Optdigits	0.85	0.70	0.70	0.85	0.70
Pollution	0.80	0.60	0.70	0.75	0.60
Ring	0.80	0.75	0.65	0.80	0.75
Satimage	0.70	0.75	0.70	0.65	0.85
Soybean	0.80	0.80	0.50	0.80	0.85
Stock	0.80	0.80	0.60	0.80	0.80
Stulong	0.80	0.65	0.50	0.75	0.65
Texture	0.85	0.70	0.65	0.80	0.70
Thyroid	0.85	0.75	0.60	0.75	0.75
Tic-tac-toe	0.80	0.75	0.65	0.80	0.75
Treasury	0.65	0.65	0.40	0.60	0.85
Twonorm	0.80	0.50	0.65	0.70	0.50
Vote	0.85	0.40	0.65	0.80	0.40
Vowel	0.80	0.85	0.60	0.80	0.90
WDatabaseBC	0.85	0.40	0.70	0.85	0.45
Weather	0.40	0.85	0.40	0.90	0.85
WPBC	0.80	0.60	0.60	0.75	0.60
Zoo	0.80	0.65	0.50	0.80	0.75

Table 5.

Average percentage (in per unit basis) of objective functions that achieves to optimize the measures analysed for each dataset. The 70th percentile was considered.

Focusing now on the ECR quality measure, it is optimized by more than 70% of the quality measures for any dataset except for Satimage and Treasury. This is a normal behaviour since data distribution from dataset to dataset may vary so much. Thus, it is important to analyse the results from a general perspective, taking as many datasets as possible. Finally, it is noteworthy that the analysis performed provides the user with a really interesting knowledge, denoting that Confidence and ECR may be optimized without fixing them implicitly into the function to be optimized. At the same time, other quality measures such as Lift or Leverage cannot be optimized unless they are included into the function to be optimized (see Figure 10).

Second analysis.

The next analysis of this experimental stage is to determine those single-objectives that enable a higher number of different metrics to be maximized. In this regard, and similarly to the previous analysis, three different percentiles (70th, 80th and 90th percentile) has been considered. The results obtained for all the datasets under study have been summarized in Figure 11, which shows the percentage of measures that are maximized by each single-objective. As it is illustrated, Coverage, Prevalence, Recall and Yule’sQ optimize an extremely low number of quality measures. Hence, it is possible to assert that these metrics should be avoided as single-objective functions in those situations were values close to the maximum are required in other quality measures. Continuing the analysis, there is no specific objective function that enables a high number of metrics to be optimized. As shown in Figure 11, the optimization of any single measure produces a maximization in less than 60% of the metrics. From all the analysed single-objective functions, Lift, CC, Pearson, IG and Netconf are the most promising ones, achieving to optimize more than 50% of the quality measures at time.

Fig. 11.

Average percentage of quality measures that were optimized by each single-objective and considering different percentiles (70th, 80th and 90th percentile).

3.4. Multi-objective optimization

In this second analysis, a multi-objective optimization is performed by taking any pair of metrics (each quality measure is a different objective) from the set of 20 quality measures analysed in this work. Hence, from a total of 190 existing pairs (number of combinations of pairs of quality measures), the goal is to test which specific group of quality measures is optimized when others are used as multi-objective functions. Similarly to the previous analysis, the final aim is three-fold: first, to check which quality measure is maximized by a higher number of pairs of measures; second, to determine which pair of quality measures (used as multi-objective function) allow a higher number of quality measures to be optimized (maximized) at time; and, finally, to analyse which set of multi-objective functions should be used to maximize all the metrics.

First analysis.

Taking the aforementioned guidelines, the goal of this first analysis is to check which quality measures are optimized by a higher number of objectives (pairs of quality measures). Similarly to the previous experimental study for single-objective optimization, the percentile used to mark a quality measure as optimized is a keystone, so different percentiles (70th, 80th and 90th percentile) were considered to carry out a complete analysis. Figure 12 illustrates the average results obtained for all the runs and considering all the datasets and two well-known multi-objective optimization models (NSGA2 and SPEA2). In this figure, the percentage of objectives (from a total of 190 pairs of quality measures) that optimizes each quality measure by considering different percentiles (70th, 80th and 90th percentile) is shown. As it is illustrated, Coverage, Laplace and zhang are optimized by more than 80% of the 190 pairs of multi-objective functions available in this study. Additionally, CF and ECR are also really general quality measures, since they are optimized by close to 70% of the multi-objectives. On the contrary, Lift, Conviction, IG and Netconf are high independent quality measures since they are hardly optimized by any multi-objective function.

Fig. 12.

Percentage of pairs of objectives, from a total of 190 pairs, that maximizes each quality measure by considering different percentiles (70th, 80th and 90th percentile).

Second analysis.

The next analysis of this experimental stage is to determine which multi-objectives (pairs of metrics) enable a higher number of metrics to be maximized. In this regard, and similarly to the previous analysis, three different percentiles (70th, 80th and 90th percentile) have been considered. The results obtained for all the datasets under study and considering the 70th percentile have been summarized in Figure 13, which shows the percentage of measures that were maximized by each multi-objective functions (only the 20 multi-objective functions that maximize a higher percentage of quality measures are shown in this analysis). As it is illustrated, there is no specific multi-objective function that enables a high number of metrics to be optimized, and the optimization of any multi-objective function produces a maximization in less than 60% of the metrics. As a remarkable result, it is obtained that more than 56% of the metrics were optimized by the following multi-objective metrics: Support-Leverage, Leverage-LC, CF-LC, and Cosine-Leverage. Finally, the same analysis has been carried out for different percentiles (80th and 90th) and as it is summarized in Figures 14 and 15.

Fig. 13.

Average percentage of quality measures that was optimized by the best multi-objective functions (those 20 that obtain a best average) and considering the 70th percentile.

Fig. 14.

Average percentage of quality measures that was optimized by the best multi-objective functions (those 20 that obtain a best average) and considering the 80th percentile.

Fig. 15.

Average percentage of quality measures that was optimized by the best multi-objective functions (those 20 that obtain a best average) and considering the 90th percentile.

Analysing all the results for the three aforementioned percentiles, it is obtained that 14 multi-objective functions appear within the 20 best multi-objective functions for each percentile. These multi-objective functions are the following: Cosine-LC, LC-yule’sQ, Support-LC, Prevalence-LC, Support-Cosine, Cosine-Laplace, Laplace-LC, LC-ECR, CFLC, Sebag-LC, Support-CF, Cosine-ECR, Cosine-CF, and Confidence-LC. When analysing each single quality measure (from the set of multi-objective functions), it is obtained that LC appears in 9 of these 14 multi-objective functions; Cosine in 5 of the 14 multi-objective functions; CF and Support in 3; Laplace and ECR in 2 of the multi-objective functions; and, finally, Prevalence, Confidence, Sebag and yule’sQ in 1 of the aforementioned functions.

3.5. Lesson learned

The results obtained in this experimental analysis are quite useful for any researcher in the association rule mining field, specially those focused on evolutionary computation. The analysis has described which quality measures are related (or unrelated) so they should (or should not) be used at time. Considering Support and Confidence as the basic pillars of any good quality measure², and knowing that these are the two most widely used metrics in this field, it is essential to use them together with other quality measures that provide any additional information. In this regard, when any existing algorithm for mining association rules considers Support/Confidence as measures to be maximized, the following metrics should be avoided since they are also maximized at time: Coverage, Prevalence, CF, Laplace, ECR and Zhang. Hence, there is no sense to choose any of the aforementioned metrics when Support/Confidence are being maximized.

When an expert (or a random user) needs to maximize a specific metric without using it as objective to be maximized but a different metrics, it is good to know that Confidence, ECR, Zhang, CF and Laplace are those more easily maximized. In fact, more than 60% of the metrics enable these measures to be maximized at time. On the contrary, Support, Lift, Leverage, Conviction, IG, Sebag and Yule’sQ are high independent quality measures since they are hardly maximized by any other single metric. This is a really interesting knowledge since anyone who needs to maximize any of that metrics requires to use them explicitly in the algorithm.

Additionally, the experimental results have revealed that Support and Lift appear as the most promising quality measures to be used as metrics to be maximized in any association rule mining problem. Any algorithm designed to maximize these two quality measures will produce a resulting set of rules where 16 over the 20 quality measures are also maximized. Hence, these two quality measures can be defined as general metrics to be considered by any algorithm in this field. In fact, even when it was tought that Confidence is also a good quality measure in this field, this specific metric is maximized together with Support so the use of both at time might be meaningless for some problems. Finally, it is of high interest for any expert user in the association rule mining field to know that Leverage, Conviction, Sebag and Yule’sQ are not desirable to be used as metrics to be maximized since they only maximize a unique quality measure at time. Thus, these four quality measures should be used only in those cases were they are required to be maximized (no additional maximization is required).

As for the multi-objective optimization problem, the results obtained in this analysis have revealed that Coverage, Laplace and Zhang are maximized by a high number of multi-objective functions so they should not be used by any multi-objective algorithm as metrics to be maximized. Taking a 70th percentile, these quality measures are maximized by more than 80% of the results of the 190 pairs of multi-objective functions available in this study. On the contrary, if user need to know which quality measures are high independent to be included as functions in a multi-objective algorithm, the experimental analysis has revealed that Lift, Conviction, IG and Netconf should not be used if the user needs to maximize a higher number of metrics at time.

Focusing on which pair of metrics are better to be chosen if we want the algorithm to maximize a higher number of metric (among the 20 studied metrics), it is obtained that either Support-Prevalence or Confidence-CC maximize 65% of the metrics analysed in this work. For example, considering Support-Prevalence as a multi-objective function, it is obtained that the following measures are maximized: Support, Coverage, Prevalence, Confidence, Recall, Laplace, LC and ECR. The same set of metrics are also maximized if we consider Support-Cosine for a multi-objective algorithm.

Finally, it is interesting to note that, some quality measures (Lift, Leverage, Conviction, Pearson and Sebag) do not produce a self-maximization when they are optimized together with other metics in a multi-objective optimization algorithm. It is quite interesting knowledge for the expert and it is somehow related to the knowledge previously described since some of these measures were defined as hardly maximized metrics in single-objective optimization. Hence, these metrics should be considered as autonomous metrics (either in single-objective or multi-objective algorithms) and should be studied in isolation for any expert.