# A Novel Method of Interestingness Measures for Association Rules Mining Based on Profit

Authors: Chunhua Ju; Fuguang Bao; Chonghuan Xu; Xiaokang Fu
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Association rules mining is an important topic in the domain of data mining and knowledge discovering. Some papers have presented several interestingness measure methods; the most typical areSupport, Confidence, Lift, Improve, and so forth. But their limitations are obvious, like no objective criterion, lack of statistical base, disability of defining negative relationship, and so forth. This paper proposes three new methods, Bi-lift, Bi-improve, and Bi-confidence, for Lift, Improve, and Confidence, respectively. Then, on the basis of utility function and the executing cost of rules, we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics of specific application object. Finally, a novel measure framework is proposed to improve the traditional one through experimental analysis. In conclusion, the new methods and measure framework are prior to the traditional ones in the aspects of objective criterion, comprehensive definition, and practical application.


---

## Body

## 1. Introduction

Along with the development and progress of data collection and storage technology in economy society, various industries and fields gradually accumulate a lot of data. In order to extract valuable information from these data, researchers have paid more and more attention to data mining technology. Association rules mining is a key technology in data mining field and is applied in many areas [1]. Association rules algorithm can generate a lot of rules, but, due to limited resources, only a part of the rules could be used by makers [2]. Therefore, the interestingness evaluation is significant for the practical application of association rules mining technology.In recent years there have been quite a few results on interestingness measure of association rules [3, 4]. Tseng et al. put forward incremental maintenance of generalized association rules under taxonomy evolution [5, 6]. Literature [7, 8] separately use two different data envelopment analysis models for the evaluation of an association rules set. To compare the evaluation results, we can find that use of different evaluation methods will get different results from the same association rules set. Interestingness measures mainly include objective measure and subjective measure [9]. The objective interestingness mainly focuses on the statistics significant research on objective data, the classic ones includeSupport,Confidence, andLift, and the new one includesValidity,Conviction, andImprove. Subjective interestingness involves the personality characteristics of subject (users) such as domain knowledge and the hobbies. There is less research on subjective interestingness and it is relatively immature. Hoque et al. and Zhang et al. presented methods to generate both frequent and rare itemsets using multiobjective genetic algorithm [10, 11]. How to mine the real and effective association rules reflecting interests of users is the common goal for researchers.The following defects of the association rules mining methods exist: (1) Many traditional association methods generate a lot of rules, and most of them are not relevant or even rules of error. (2) Do not consider users characteristics and their changes, but users characteristics and subjectivity tend to affect relevance of several events. (3) Online trading data and user evaluation data are extremely sparse (i.e., data sparseness) due to surge of current online trading. (4) The too low threshold values ofsupport andconfidence can produce the combination explosion, but, because of data sparseness, low support rules may provide some novel knowledge that users are interested in. (5) At present some literature simply combines kinds of interestingness evaluation to measure, but this does not take rationality of various interestingness evaluation methods into account.The main contribution of this paper is summarized as follows: This paper firstly summarizes the relevant research results on the objective interestingness measure of association rules. At the same time the various measurement methods of association rules are analyzed and compared, and we found that all have some defects and problems. And, then, put forward three more effective measurement methods of association rules (Bi-lift,Bi-improve, andBi-confidence) based on improvement of some methods. TheBi-lift method takes deduction of negative premise as a constraint, to form a bideduction comparing algorithm so as to improve the reliability of the mutual influence between premise and follow-up. TheBi-improve method takes the adjustment of the occurrence and nonoccurrence possibility of antecedent based on theImprove. TheBi-confidence method takes the adjustment of the nonoccurrence possibility of antecedent based on theConfidence. Through the experimental analysis, a new measure framework is proposed to improve the traditional one. Then, on the basis of utility function and the executing cost of rules, we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics of specific application object.A review of related work is given in Section2. In Section 3, three more effective measurement methods of association rules (Bi-lift,Bi-improve, andBi-confidence) are proposed. In Section 4, the paper studied subjective interestingness measures of association rules. In Section 5, through the experimental analysis, a new measure framework is proposed to improve the traditional one. Finally, we draw conclusions in Section 6.


## 2. Review on Objective Measures of Interest for Association Rules

To illustrate conveniently, firstly we suppose that formal description of association rules is as follows:(1)
A
⟶
B
.In this description, A
=
{
A
1
,
A
2
,
…
,
A
j
}
⊂
I and B
=
{
B
1
,
B
2
,
…
,
B
k
}
⊂
I. I indicate itemsets, and A
∩
B
=
ϕ. Rules should meet certainsupport threshold s andconfidence
c.Data of Table1 is produced by data extraction and transformation from a shopping mall receipts. Each line (a tuple) is a shopping list data (shopping receipts). “1” represents that the list includes this item, while “0” represents that the list does not include this item.Table 1
A data set of transaction.
Tid
E
F
G
H
I
J
K
L
M
N
R
Ttotal
1
1
1
1
1
1
1
1
0
1
0
0
8
2
1
1
0
1
1
1
1
1
1
0
0
8
3
1
1
0
1
1
0
0
0
0
1
0
5
4
1
1
1
0
0
1
0
1
1
1
1
8
5
1
1
1
0
0
1
0
0
0
1
1
6
6
1
1
1
0
0
0
0
0
1
1
1
6
7
1
1
0
0
0
0
1
0
0
1
0
4
8
1
1
1
0
1
0
0
0
0
0
1
5
9
1
0
1
1
0
0
0
0
0
1
0
4
10
1
0
1
0
0
1
0
0
0
0
1
4
Total
10
8
7
4
4
5
3
2
4
6
5
58


### 2.1.Support

Support [12] means the frequency that the data fields A and B involved in association rules occur together in the data set. Only the association rules appear frequently in the itemsets, when it gets high accuracy.Support can be used to measure the usefulness of association rules. When the frequency of A and B occurring at the same time is equal to or greater than the designated minimumsupport threshold, A and B meet frequent itemsets.Support can be expressed as(2)
s
A
⟶
B
=
P
A
B
=
N
A
B
D
,where N
(
A
B
) is the record number of A and B that appeared together, and D is the total record number of transactions in data sets.Support is classic but also has the defects of artificially controlled threshold and rare itemsets. Many infrequent itemsets in the data set may have potential value. Besides, at present in large electronic commerce system, the number of subjects (users) and the amount of projects increase exponentially. Online transaction data and user evaluation data are extremely sparse.


### 2.2.Confidence

Confidence [12] is the statistics of probability P
(
B
∣
A
) that subsequent events occur under the condition of occurrence of the precursor events in trading data sets. It is used to measure the reliability of the rules. Formula is(3)
c
A
⟶
B
=
P
B
∣
A
=
P
A
B
P
A
.It is used to combineconfidence withsupport to formSupport-confidence framework for mining association rules [13]. IfSupport is larger than the designated minimumsupport threshold andConfidence is larger than the designated minimumconfidence threshold, the rules are called strong association rules. But strong association rules are not always effective, some are not what users are interested in, and some are even misleading.


### 2.3.Lift

Because of the defects ofSupport-confidence framework, some scholars analyze the relativity of association rules mined, namely,lift [12].Lift means the ratio of rule’sConfidence to probability of occurrence of the consequent, which reflects positive or negative correlation of antecedent and consequence of rules. It refers to the ratio of the occurrence probability of B under the condition A to that without considering condition A, which reflects the relationship between “A” and “B”:(4)
l
i
f
t
A
⟶
B
=
c
A
→
B
P
B
=
P
A
B
P
A
P
B
.The range oflift values is [
0
,
+
∞
). Aslift is equal to 1, it shows that A and B appearing at the same time belong to independent random events and have no special significance; namely, A and B are independent of each other with no mutual affection. We call this rule uncorrelated rules; iflift value is less than 1, it shows that the emergence of “A” reduces the emergence of “B,” and then we call them negative correlation rules; ifLift value is larger than 1, it shows that the emergence of “A” promotes the emergence of “B,” and then we call them positive correlation rules. Problems:Lift takes events A and B in equivalence position. According to theLift, A
→
B and B
→
A are the same; that is to say, if we accept rule A
→
B, B
→
A should be also accepted, but the fact is not like this.


### 2.4.Validity

Literature [14] introduces a new measure method of association rules, known asvalidity.Validity is defined as the difference between the probability of “A” and “B” occurring together and the occurrence probability of “B” without “A” occurring in database D. Because the value range of P
(
A
B
) and P
(
A
¯
B
) are [
0,1
], the value range ofvalidity is obviously [
-
1,1
]:(5)
V
a
l
i
d
i
t
y
A
⟶
B
=
P
A
B
-
P
A
¯
B
.In fact, our research found that thevalidity is not effective. In Table 1, for example, rule F
→
G’ssupport is 0.7 and itsvalidity is 0.5
-
0.2
=
0.3; according to the literature [14], we can judge that it is a valid association rule. But through the calculation P
(
F
G
)
-
P
(
F
)
P
(
G
)
=
0.5
-
0.8
×
0.7
=
-
0.06, it shows that F and G have certain negative correlation. And taking Table 2 for example, this case has already qualified for the basic requirements ofsupport andconfidence, and V
a
l
i
d
i
t
y
(
A
→
B
)
=
0.45
-
0.3
=
0.15. According to the measure standard ofvalidity, the rule A
→
B should be said “effective.” The occurrence of “A” will promote the occurrence of “B”. But in fact, the occurrence frequency of overall event B is 0.75, and the occurrence possibility of “B” as “A” occurs is 4500
/
6500
=
0.69, which is six percent lower.Table 2
The occurrence of “A” and “B.”
B occurring
B not occurring
Total
A occurring
4500
2000
6500
A not occurring
3000
500
3500
Total
7500
2500
10000


### 2.5.Conviction

As early as 1997, Brin introduced the concept ofconviction (Conv.) [15, 16]:(6)
C
o
n
v
i
c
t
i
o
n
A
⟶
B
=
P
A
P
B
¯
P
A
B
¯
.Its value range is[
0
,
+
∞
). When the value ofconviction is “1,” it means that “A” has no relation with “B
.” And the greater theconviction is, the higher the interest in the rule will be. But theconviction constraints are too strict; lots of valuable association rules will be removed. In Table 1, for example, C
o
n
v
i
c
t
i
o
n
(
M
→
L
)
=
0.4
×
0.8
/
0.5
=
0.64
<
1; itsconviction is low, but, in fact, the high interest of M and L may exist. And it requires that P
(
A
B
¯
)
≠
0 at the same time.


### 2.6.Improve

Literature [17] proposed a new interestingness measure method of association rules based on the description of the defects of the traditional interestingness measurement method. We will call it “Improve.” It means that the difference of the conditional probability P
(
B
∣
A
) and the probability of “B” (7)
Improve
A
⟶
B
=
P
B
∣
A
-
P
B
.But shortcomings ofImprove (Imp.) are obvious. Firstly, how much improvement of probability can be called improvement? Secondly, the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time.Take Tables3 and 4 for example and calculate theirImprove values:(8)
Improve
A
′
⟶
B
′
=
P
B
′
∣
A
′
-
P
B
′
=
0.03
,
Improve
C
⟶
D
=
P
D
∣
C
-
P
D
=
0.11
.Table 3
The occurrence of “A
′” and “B
′.”
B
′ occurring
B
′ not occurring
Total
A
′ occurring
8000
1000
9000
A
′ not occurring
500
500
1000
Total
8500
1500
10000Table 4
The occurrence of “C” and “D.”
D occurring
D not occurring
Total
C occurring
3600
700
4300
C not occurring
3700
2000
5700
Total
7300
2700
10000Only, thinking about theImprove, rule (
C
→
D
) is more valuable than rule (
A
′
→
B
′
). But the fact is also very clear that it can increase “the occurrence possibility of B” as “A” occurs by up to 39% compared to that when “A” does not occur. While it can increase “the occurrence possibility of event D” as “C” occurs by up to 19% compared to that when “C” does not occur. So rule (
A
′
→
B
′
) should be more meaningful than rule (
C
→
D
).


### 2.7.Chi-Square Analysis

Literature [18] puts forward an interestingness measure standard based on t-test. It uses t-test to analyze difference of associatedconfidence
P
(
B
∣
A
) and expectedconfidence
P
(
B
). If the difference is bigger, it indicates that the occurrence of “A” has large influence on “B,” and the rule (
A
→
B
) is interesting. Formula is as follows:(9)
C
h
i
-
S
q
u
a
r
e
A
⟶
B
=
P
B
∣
A
-
P
B
σ
,
σ
=
P
B
1
-
P
B
n
.IfC
h
i
-
S
q
u
a
r
e
(
A
→
B
)
>
t
α
(
n
), it shows that it has larger difference between associatedconfidence
P
(
B
∣
A
) and expectedconfidence
P
(
B
) and the rule (
A
→
B
) is interesting. To some extent, it improves the traditional framework of interestingness measure. But there is also a defect that is similar to that ofImprove.


### 2.8. Certainty Factor (CF)

To assess the accuracy of association rules, Berzal et al. use certainty factors [19] instead ofconfidence. Formula is as follows:(10)
C
F
A
⟶
B
=
c
A
→
B
-
s
B
1
-
s
B
=
P
A
B
/
P
A
-
P
B
1
-
P
B
=
P
A
B
-
P
A
P
B
P
A
1
-
P
B
,
i
f
c
A
⟶
B
>
s
B
,
C
F
A
⟶
B
=
c
A
→
B
-
s
B
s
B
=
P
A
B
/
P
A
-
P
B
P
B
=
P
A
B
-
P
A
P
B
P
A
P
B
,
i
f
c
A
⟶
B
<
s
B
.The certainty factor is interpreted as a measure of variation of the probability thatB is in a transaction when we consider only those transactions where there is A. More specifically, a positiveCF measures the decrease of the probability that B is not in a transaction, given that A is. A similar interpretation can be done for negativeCF.


## 2.1.Support

Support [12] means the frequency that the data fields A and B involved in association rules occur together in the data set. Only the association rules appear frequently in the itemsets, when it gets high accuracy.Support can be used to measure the usefulness of association rules. When the frequency of A and B occurring at the same time is equal to or greater than the designated minimumsupport threshold, A and B meet frequent itemsets.Support can be expressed as(2)
s
A
⟶
B
=
P
A
B
=
N
A
B
D
,where N
(
A
B
) is the record number of A and B that appeared together, and D is the total record number of transactions in data sets.Support is classic but also has the defects of artificially controlled threshold and rare itemsets. Many infrequent itemsets in the data set may have potential value. Besides, at present in large electronic commerce system, the number of subjects (users) and the amount of projects increase exponentially. Online transaction data and user evaluation data are extremely sparse.


## 2.2.Confidence

Confidence [12] is the statistics of probability P
(
B
∣
A
) that subsequent events occur under the condition of occurrence of the precursor events in trading data sets. It is used to measure the reliability of the rules. Formula is(3)
c
A
⟶
B
=
P
B
∣
A
=
P
A
B
P
A
.It is used to combineconfidence withsupport to formSupport-confidence framework for mining association rules [13]. IfSupport is larger than the designated minimumsupport threshold andConfidence is larger than the designated minimumconfidence threshold, the rules are called strong association rules. But strong association rules are not always effective, some are not what users are interested in, and some are even misleading.


## 2.3.Lift

Because of the defects ofSupport-confidence framework, some scholars analyze the relativity of association rules mined, namely,lift [12].Lift means the ratio of rule’sConfidence to probability of occurrence of the consequent, which reflects positive or negative correlation of antecedent and consequence of rules. It refers to the ratio of the occurrence probability of B under the condition A to that without considering condition A, which reflects the relationship between “A” and “B”:(4)
l
i
f
t
A
⟶
B
=
c
A
→
B
P
B
=
P
A
B
P
A
P
B
.The range oflift values is [
0
,
+
∞
). Aslift is equal to 1, it shows that A and B appearing at the same time belong to independent random events and have no special significance; namely, A and B are independent of each other with no mutual affection. We call this rule uncorrelated rules; iflift value is less than 1, it shows that the emergence of “A” reduces the emergence of “B,” and then we call them negative correlation rules; ifLift value is larger than 1, it shows that the emergence of “A” promotes the emergence of “B,” and then we call them positive correlation rules. Problems:Lift takes events A and B in equivalence position. According to theLift, A
→
B and B
→
A are the same; that is to say, if we accept rule A
→
B, B
→
A should be also accepted, but the fact is not like this.


## 2.4.Validity

Literature [14] introduces a new measure method of association rules, known asvalidity.Validity is defined as the difference between the probability of “A” and “B” occurring together and the occurrence probability of “B” without “A” occurring in database D. Because the value range of P
(
A
B
) and P
(
A
¯
B
) are [
0,1
], the value range ofvalidity is obviously [
-
1,1
]:(5)
V
a
l
i
d
i
t
y
A
⟶
B
=
P
A
B
-
P
A
¯
B
.In fact, our research found that thevalidity is not effective. In Table 1, for example, rule F
→
G’ssupport is 0.7 and itsvalidity is 0.5
-
0.2
=
0.3; according to the literature [14], we can judge that it is a valid association rule. But through the calculation P
(
F
G
)
-
P
(
F
)
P
(
G
)
=
0.5
-
0.8
×
0.7
=
-
0.06, it shows that F and G have certain negative correlation. And taking Table 2 for example, this case has already qualified for the basic requirements ofsupport andconfidence, and V
a
l
i
d
i
t
y
(
A
→
B
)
=
0.45
-
0.3
=
0.15. According to the measure standard ofvalidity, the rule A
→
B should be said “effective.” The occurrence of “A” will promote the occurrence of “B”. But in fact, the occurrence frequency of overall event B is 0.75, and the occurrence possibility of “B” as “A” occurs is 4500
/
6500
=
0.69, which is six percent lower.Table 2
The occurrence of “A” and “B.”
B occurring
B not occurring
Total
A occurring
4500
2000
6500
A not occurring
3000
500
3500
Total
7500
2500
10000


## 2.5.Conviction

As early as 1997, Brin introduced the concept ofconviction (Conv.) [15, 16]:(6)
C
o
n
v
i
c
t
i
o
n
A
⟶
B
=
P
A
P
B
¯
P
A
B
¯
.Its value range is[
0
,
+
∞
). When the value ofconviction is “1,” it means that “A” has no relation with “B
.” And the greater theconviction is, the higher the interest in the rule will be. But theconviction constraints are too strict; lots of valuable association rules will be removed. In Table 1, for example, C
o
n
v
i
c
t
i
o
n
(
M
→
L
)
=
0.4
×
0.8
/
0.5
=
0.64
<
1; itsconviction is low, but, in fact, the high interest of M and L may exist. And it requires that P
(
A
B
¯
)
≠
0 at the same time.


## 2.6.Improve

Literature [17] proposed a new interestingness measure method of association rules based on the description of the defects of the traditional interestingness measurement method. We will call it “Improve.” It means that the difference of the conditional probability P
(
B
∣
A
) and the probability of “B” (7)
Improve
A
⟶
B
=
P
B
∣
A
-
P
B
.But shortcomings ofImprove (Imp.) are obvious. Firstly, how much improvement of probability can be called improvement? Secondly, the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time.Take Tables3 and 4 for example and calculate theirImprove values:(8)
Improve
A
′
⟶
B
′
=
P
B
′
∣
A
′
-
P
B
′
=
0.03
,
Improve
C
⟶
D
=
P
D
∣
C
-
P
D
=
0.11
.Table 3
The occurrence of “A
′” and “B
′.”
B
′ occurring
B
′ not occurring
Total
A
′ occurring
8000
1000
9000
A
′ not occurring
500
500
1000
Total
8500
1500
10000Table 4
The occurrence of “C” and “D.”
D occurring
D not occurring
Total
C occurring
3600
700
4300
C not occurring
3700
2000
5700
Total
7300
2700
10000Only, thinking about theImprove, rule (
C
→
D
) is more valuable than rule (
A
′
→
B
′
). But the fact is also very clear that it can increase “the occurrence possibility of B” as “A” occurs by up to 39% compared to that when “A” does not occur. While it can increase “the occurrence possibility of event D” as “C” occurs by up to 19% compared to that when “C” does not occur. So rule (
A
′
→
B
′
) should be more meaningful than rule (
C
→
D
).


## 2.7.Chi-Square Analysis

Literature [18] puts forward an interestingness measure standard based on t-test. It uses t-test to analyze difference of associatedconfidence
P
(
B
∣
A
) and expectedconfidence
P
(
B
). If the difference is bigger, it indicates that the occurrence of “A” has large influence on “B,” and the rule (
A
→
B
) is interesting. Formula is as follows:(9)
C
h
i
-
S
q
u
a
r
e
A
⟶
B
=
P
B
∣
A
-
P
B
σ
,
σ
=
P
B
1
-
P
B
n
.IfC
h
i
-
S
q
u
a
r
e
(
A
→
B
)
>
t
α
(
n
), it shows that it has larger difference between associatedconfidence
P
(
B
∣
A
) and expectedconfidence
P
(
B
) and the rule (
A
→
B
) is interesting. To some extent, it improves the traditional framework of interestingness measure. But there is also a defect that is similar to that ofImprove.


## 2.8. Certainty Factor (CF)

To assess the accuracy of association rules, Berzal et al. use certainty factors [19] instead ofconfidence. Formula is as follows:(10)
C
F
A
⟶
B
=
c
A
→
B
-
s
B
1
-
s
B
=
P
A
B
/
P
A
-
P
B
1
-
P
B
=
P
A
B
-
P
A
P
B
P
A
1
-
P
B
,
i
f
c
A
⟶
B
>
s
B
,
C
F
A
⟶
B
=
c
A
→
B
-
s
B
s
B
=
P
A
B
/
P
A
-
P
B
P
B
=
P
A
B
-
P
A
P
B
P
A
P
B
,
i
f
c
A
⟶
B
<
s
B
.The certainty factor is interpreted as a measure of variation of the probability thatB is in a transaction when we consider only those transactions where there is A. More specifically, a positiveCF measures the decrease of the probability that B is not in a transaction, given that A is. A similar interpretation can be done for negativeCF.


## 3. The Improvement of Objective Interestingness Measures

### 3.1.Bi-Lift

Related researches show thatlift method has good evaluation results. But obviouslylift take “A” and “B” in equivalence position, and it shows that rules A
→
B and B
→
A are the same; if we accept rule A
→
B, rule B
→
A should be also accepted. But the fact is not like this. For this problem, the paper proposes aBi-lift measure method; finding that you want to evaluate the relationship of (
A
→
B
) by l
i
f
t
(
A
→
B
), you should also study on the relationship of A
¯
→
B, so we introduce l
i
f
t
(
A
¯
→
B
) to adjust l
i
f
t
(
A
→
B
). The higher the l
i
f
t
(
A
→
B
) is, the better the rule A
→
B is, while the higher the l
i
f
t
(
A
¯
→
B
) is, the worse the rule A
→
B is. So we propose aBi-lift measure method, l
i
f
t
(
A
¯
→
B
) as denominator, and l
i
f
t
(
A
→
B
) as numerator, namely, ratio of l
i
f
t
(
A
→
B
) to l
i
f
t
(
A
¯
→
B
);Bi-lift formula is as follows:(11)
B
i
-
l
i
f
t
A
⟶
B
=
lift
A
→
B
lift
A
¯
→
B
=
P
A
B
/
P
A
P
B
P
A
¯
B
/
P
A
¯
P
B
=
P
A
B
P
A
¯
P
A
¯
B
P
A
.The premise is P
(
A
¯
B
)
≠
0, and “A” and “B” are not certain event or impossible event. Its value range is [
0
,
∞
). TheBi-lift method takes deduction of negative premise as a constraint, to form a bideduction comparing algorithm so as to improve the reliability of the mutual influence between premise and follow-up.


### 3.2.Bi-Improve

Because of the defects ofimprove, the paper put forwardBi-improve. Because the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time. In order to eliminate the influence, we make correction by multiplying the ratio of the occurrence possibility of antecedent to the no occurrence probability of antecedent.Bi-improve formula is as follows:(12)
B
i
-
i
m
p
r
o
v
e
A
⟶
B
=
P
B
∣
A
-
P
B
∗
P
A
P
A
¯
=
P
A
B
-
P
A
P
B
P
A
¯
.Taking Tables3 and 4, for examples, Improve
(
A
′
→
B
′
)
=
0.03 and Improve
(
C
→
D
)
=
0.11 only thinking about theImprove; rule (
C
→
D
) is more valuable than rule (
A
′
→
B
′
). But the fact is also very clear that it can increase “the occurrence possibility of B” as “A” occurs by up to 39% compared to that when “A” does not occur, while it can increase “the occurrence possibility of event D” as “C” occurs by up to 19% compared to that when “C” does not occur. So rule (
A
′
→
B
′
) should be more meaningful than rule (
C
→
D
). CalculateBi-Improve value through the following formula:(13)
B
i
-
i
m
p
r
o
v
e
A
⟶
B
=
P
B
∣
A
-
P
B
∗
P
A
P
A
¯
=
0.27
,
B
i
-
i
m
p
r
o
v
e
C
⟶
D
=
P
D
∣
C
-
P
D
∗
P
C
P
C
¯
=
0.225
.B
i
-
i
m
p
r
o
v
e
(
A
→
B
) is higher than B
i
-
i
m
p
r
o
v
e
(
C
→
D
), which accords with the real condition.


### 3.3.Bi-Confidence

Confidence indicates that the appearance of some itemsets will lead to appearance of other itemsets. But we see that theconfidence of association rules only thinks about the occurrence possibility of “B” when “A” occurs, but not consider the relationship between “A” and “B” when “A” does not occur. So it makes a lot of association rules mining invalid. For the above problems of association rules, we found that the description ofconfidence is not perfect and not enough to show the degree of correlation between itemsets. We put forward the concept ofBi-confidence, and its definition is as follows:(14)
B
i
-
c
o
n
f
i
d
e
n
c
e
A
⟶
B
=
P
A
B
P
A
-
P
A
¯
B
P
A
¯
=
P
A
B
-
P
A
P
B
P
A
×
1
-
P
A
.The value range ofBi-confidence is [
-
1,1
]. If theBi-confidence value is greater than 0, then P
(
A
B
)
>
P
(
A
)
P
(
B
), which shows that “A” and “B” have the positive correlation. If theBi-confidence is equal to 1, then P
(
A
B
)
=
P
(
A
)
=
P
(
B
), and it shows that “A” and “B” in record set appear together or not. If theBi-confidence is equal to 0, and P
(
A
B
)
=
P
(
A
)
P
(
B
), which shows that “A” has no relation with “B
.” If theBi-confidence is less than 0, then P
(
A
B
)
<
P
(
A
)
P
(
B
); it shows that “A” and “B” have the negative correlation, and negative rules also have research value.Bi-confidence’s definition not only contains the correlation factors, but also contains P
(
B
) factor. Therefore,Bi-confidence can fully embody the effectiveness of the rules. If we useSupport-Bi-confidence framework to replaceSupport-confidence framework, it not only can mine association rules effectively, but also can reduce the occurrence of the weak correlation rules.


## 3.1.Bi-Lift

Related researches show thatlift method has good evaluation results. But obviouslylift take “A” and “B” in equivalence position, and it shows that rules A
→
B and B
→
A are the same; if we accept rule A
→
B, rule B
→
A should be also accepted. But the fact is not like this. For this problem, the paper proposes aBi-lift measure method; finding that you want to evaluate the relationship of (
A
→
B
) by l
i
f
t
(
A
→
B
), you should also study on the relationship of A
¯
→
B, so we introduce l
i
f
t
(
A
¯
→
B
) to adjust l
i
f
t
(
A
→
B
). The higher the l
i
f
t
(
A
→
B
) is, the better the rule A
→
B is, while the higher the l
i
f
t
(
A
¯
→
B
) is, the worse the rule A
→
B is. So we propose aBi-lift measure method, l
i
f
t
(
A
¯
→
B
) as denominator, and l
i
f
t
(
A
→
B
) as numerator, namely, ratio of l
i
f
t
(
A
→
B
) to l
i
f
t
(
A
¯
→
B
);Bi-lift formula is as follows:(11)
B
i
-
l
i
f
t
A
⟶
B
=
lift
A
→
B
lift
A
¯
→
B
=
P
A
B
/
P
A
P
B
P
A
¯
B
/
P
A
¯
P
B
=
P
A
B
P
A
¯
P
A
¯
B
P
A
.The premise is P
(
A
¯
B
)
≠
0, and “A” and “B” are not certain event or impossible event. Its value range is [
0
,
∞
). TheBi-lift method takes deduction of negative premise as a constraint, to form a bideduction comparing algorithm so as to improve the reliability of the mutual influence between premise and follow-up.


## 3.2.Bi-Improve

Because of the defects ofimprove, the paper put forwardBi-improve. Because the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time. In order to eliminate the influence, we make correction by multiplying the ratio of the occurrence possibility of antecedent to the no occurrence probability of antecedent.Bi-improve formula is as follows:(12)
B
i
-
i
m
p
r
o
v
e
A
⟶
B
=
P
B
∣
A
-
P
B
∗
P
A
P
A
¯
=
P
A
B
-
P
A
P
B
P
A
¯
.Taking Tables3 and 4, for examples, Improve
(
A
′
→
B
′
)
=
0.03 and Improve
(
C
→
D
)
=
0.11 only thinking about theImprove; rule (
C
→
D
) is more valuable than rule (
A
′
→
B
′
). But the fact is also very clear that it can increase “the occurrence possibility of B” as “A” occurs by up to 39% compared to that when “A” does not occur, while it can increase “the occurrence possibility of event D” as “C” occurs by up to 19% compared to that when “C” does not occur. So rule (
A
′
→
B
′
) should be more meaningful than rule (
C
→
D
). CalculateBi-Improve value through the following formula:(13)
B
i
-
i
m
p
r
o
v
e
A
⟶
B
=
P
B
∣
A
-
P
B
∗
P
A
P
A
¯
=
0.27
,
B
i
-
i
m
p
r
o
v
e
C
⟶
D
=
P
D
∣
C
-
P
D
∗
P
C
P
C
¯
=
0.225
.B
i
-
i
m
p
r
o
v
e
(
A
→
B
) is higher than B
i
-
i
m
p
r
o
v
e
(
C
→
D
), which accords with the real condition.


## 3.3.Bi-Confidence

Confidence indicates that the appearance of some itemsets will lead to appearance of other itemsets. But we see that theconfidence of association rules only thinks about the occurrence possibility of “B” when “A” occurs, but not consider the relationship between “A” and “B” when “A” does not occur. So it makes a lot of association rules mining invalid. For the above problems of association rules, we found that the description ofconfidence is not perfect and not enough to show the degree of correlation between itemsets. We put forward the concept ofBi-confidence, and its definition is as follows:(14)
B
i
-
c
o
n
f
i
d
e
n
c
e
A
⟶
B
=
P
A
B
P
A
-
P
A
¯
B
P
A
¯
=
P
A
B
-
P
A
P
B
P
A
×
1
-
P
A
.The value range ofBi-confidence is [
-
1,1
]. If theBi-confidence value is greater than 0, then P
(
A
B
)
>
P
(
A
)
P
(
B
), which shows that “A” and “B” have the positive correlation. If theBi-confidence is equal to 1, then P
(
A
B
)
=
P
(
A
)
=
P
(
B
), and it shows that “A” and “B” in record set appear together or not. If theBi-confidence is equal to 0, and P
(
A
B
)
=
P
(
A
)
P
(
B
), which shows that “A” has no relation with “B
.” If theBi-confidence is less than 0, then P
(
A
B
)
<
P
(
A
)
P
(
B
); it shows that “A” and “B” have the negative correlation, and negative rules also have research value.Bi-confidence’s definition not only contains the correlation factors, but also contains P
(
B
) factor. Therefore,Bi-confidence can fully embody the effectiveness of the rules. If we useSupport-Bi-confidence framework to replaceSupport-confidence framework, it not only can mine association rules effectively, but also can reduce the occurrence of the weak correlation rules.


## 4. Subjective Interestingness Measures of Association Rules

Generally, the purpose of association rule mining is to obtain certain utility or benefit through the use of some appropriate association rules. So taking the user’s subjective preference or specific application object into consideration, profit targets (or revenue function) are the real key for the users. Thus, two critical problems emerge: firstly, it can bring what kind of utility to the users by the adopted association rules; secondly, the cost or the cost of labor must be taken into consideration when performing the association rules.


### 4.1. Utility Function: Incremental Monetary Value

The purpose of association rule mining is to translate it into real value and to obtain certain utility. Generally utility function is the concern point of users. Specifically, utility of rules can be incremental monetary value generated by association rule [20]. Incremental monetary value (IMV) is the expected profit (EP) under the guidance of rules minus the profit you would expect to receive without the guidance of rules or due to the natural course. Incremental monetary value is defined as follows in that study:(15)
I
M
V
A
⟶
B
=
P
B
∣
A
-
P
B
×
∑
P
r
i
c
e
B
i
,where P
r
i
c
e
(
B
i
) is the unit price of goods B
i and ∑
P
r
i
c
e
(
B
i
) is the sum price of all the “B” sets.Incremental monetary value (IMV) has some defects, the probability of former pieces’ occurrence will seriously affectImprove evaluation (Imp
.
(
A
→
B
)
=
P
(
B
∣
A
)
-
P
(
B
)), and, in order to eliminate the influence, we make correction by multiplying by the ratio of the occurrence possibility of antecedent to the no occurrence probability of antecedent. In addition, utility or value should be price minus cost. So we put forward antecedent incremental monetary value (AIMV):(16)
A
I
M
V
A
⟶
B
=
P
B
∣
A
-
P
B
×
P
A
P
A
¯
·
∑
P
r
i
c
e
B
i
-
C
o
s
t
B
i
,where P
r
i
c
e
(
B
i
) is the unit price of goods B
i and C
o
s
t
(
B
i
) is the cost per unit of goods B
i.


### 4.2. Cost Function

The cost or the cost of labor should be concerned when executing the association rules. LetC
o
s
t
(
A
→
B
) represent the executing cost of rules of (
A
→
B
), such as the unit cost of handling commodity “A” from place A to place B. But the calculation of the so-called executing cost is complicated sometimes. In order to make the study under the maneuverability, the executing cost of rules of (
A
→
B
) can be divided into several levels.


### 4.3. Interestingness Function Based on Profit (IFBP)

On the basis of utility function and the executing cost of rulesC
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) with subjective preferences and specific application object. Formula is as follows:(17)
I
F
B
P
A
⟶
B
=
P
B
∣
A
-
P
B
×
P
A
P
A
¯
·
∑
P
r
i
c
e
B
i
-
C
o
s
t
B
i
-
C
o
s
t
A
⟶
B
.


## 4.1. Utility Function: Incremental Monetary Value

The purpose of association rule mining is to translate it into real value and to obtain certain utility. Generally utility function is the concern point of users. Specifically, utility of rules can be incremental monetary value generated by association rule [20]. Incremental monetary value (IMV) is the expected profit (EP) under the guidance of rules minus the profit you would expect to receive without the guidance of rules or due to the natural course. Incremental monetary value is defined as follows in that study:(15)
I
M
V
A
⟶
B
=
P
B
∣
A
-
P
B
×
∑
P
r
i
c
e
B
i
,where P
r
i
c
e
(
B
i
) is the unit price of goods B
i and ∑
P
r
i
c
e
(
B
i
) is the sum price of all the “B” sets.Incremental monetary value (IMV) has some defects, the probability of former pieces’ occurrence will seriously affectImprove evaluation (Imp
.
(
A
→
B
)
=
P
(
B
∣
A
)
-
P
(
B
)), and, in order to eliminate the influence, we make correction by multiplying by the ratio of the occurrence possibility of antecedent to the no occurrence probability of antecedent. In addition, utility or value should be price minus cost. So we put forward antecedent incremental monetary value (AIMV):(16)
A
I
M
V
A
⟶
B
=
P
B
∣
A
-
P
B
×
P
A
P
A
¯
·
∑
P
r
i
c
e
B
i
-
C
o
s
t
B
i
,where P
r
i
c
e
(
B
i
) is the unit price of goods B
i and C
o
s
t
(
B
i
) is the cost per unit of goods B
i.


## 4.2. Cost Function

The cost or the cost of labor should be concerned when executing the association rules. LetC
o
s
t
(
A
→
B
) represent the executing cost of rules of (
A
→
B
), such as the unit cost of handling commodity “A” from place A to place B. But the calculation of the so-called executing cost is complicated sometimes. In order to make the study under the maneuverability, the executing cost of rules of (
A
→
B
) can be divided into several levels.


## 4.3. Interestingness Function Based on Profit (IFBP)

On the basis of utility function and the executing cost of rulesC
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) with subjective preferences and specific application object. Formula is as follows:(17)
I
F
B
P
A
⟶
B
=
P
B
∣
A
-
P
B
×
P
A
P
A
¯
·
∑
P
r
i
c
e
B
i
-
C
o
s
t
B
i
-
C
o
s
t
A
⟶
B
.


## 5. The Measure Framework of Association Rules and Experimental Analysis

### 5.1. Example Analysis of Objective Interestingness Measures

According to a set of business data in Table1, take verification of kinds of measure methods and design measure framework. Because item E appears in all affairs, take it as a kind of certain event and do not think of association rules about E. Set minimumsupport for 20% and minimumconfidence for 50%. Frequent 2 itemsets calculated through the a priori algorithm are shown in Table 5.Table 5
Various measure evaluation results of various rules.
(a)
Rules
Sup.
Con.
Lift
Bi-lift
Val.
Conv.
Imp.
Bi-imp.
Csa.
CF
Bi-con.
M
→
J
0.3
0.75
1.5
2.25
0.1
2
0.25
0.16
1.58
0.50
0.42
M
→
G
0.3
0.75
1.08
1.13
0.1
1.2
0.05
0.03
0.35
0.17
0.08
J
→
G
0.4
0.8
1.14
1.33
0.1
0.75
0.1
0.1
0.69
0.33
0.2
I
→
H
0.3
0.75
1.88
4.5
0.2
2.4
0.35
0.23
2.26
0.58
0.58
I
→
F
0.4
1
1.25
1.5
0
/
0.2
0.13
1.58
1.00
0.33
H
→
F
0.3
0.75
0.95
0.9
−0.2
0.8
−0.05
−0.03
−0.4
−0.06
−0.08
R
→
G
0.5
1
1.42
2.5
0.3
/
0.3
0.3
2.1
1.00
0.6
N
→
G
0.4
0.67
0.95
0.89
0.1
0.9
−0.03
−0.05
−0.21
−0.04
−0.08
R
→
F
0.4
0.8
1
1
0
1
0
0
0
0.00
0
N
→
F
0.5
0.83
1.04
1.11
0.2
1.2
0.03
0.05
0.24
0.15
0.08
M
→
F
0.4
1
1.25
1.5
0
/
0.2
0.13
1.58
1.00
0.33
J
→
F
0.4
0.8
1
1
0
1
0
0
0
0.00
0
G
→
F
0.5
0.71
0.89
0.71
0.2
0.7
−0.09
−0.21
−0.71
−0.11
−0.28
J
→
M
0.3
0.6
1.5
3
0.2
1.5
0.2
0.2
1.29
0.33
0.4
G
→
J
0.4
0.57
1.14
1.71
0.3
1.17
0.07
0.18
0.44
0.14
0.24
H
→
I
0.3
0.75
1.88
4.5
0.2
2.4
0.35
0.23
2.26
0.58
0.58
F
→
I
0.4
0.5
1.25
/
0.4
1.2
0.1
0.4
0.65
0.17
0.5
G
→
R
0.5
0.71
1.42
/
0.5
1.75
0.21
0.49
1.33
0.42
0.71
G
→
N
0.4
0.57
0.95
0.86
0.2
0.93
−0.03
−0.07
−0.19
−0.05
−0.1
F
→
R
0.4
0.5
1
1
0.3
1
0
0
0
0.00
0
F
→
N
0.5
0.63
1.04
1.25
0.4
1.07
0.03
0.12
0.19
0.08
0.13
F
→
M
0.4
0.5
1.25
/
0.4
1.2
0.1
0.4
0.65
0.17
0.5
F
→
J
0.4
0.5
1
1
0.3
1
0
0
0
0.00
0
F
→
G
0.5
0.63
0.89
0.63
0.3
0.8
−0.07
−0.28
−0.48
−0.10
−0.38
M
→
L
0.2
0.5
2.5
/
0.2
0.64
0.3
0.2
2.37
0.38
0.5
(b)
Rules
Lift rank
Bi-lift rank
Val. rank
Conv. rank
Imp. rank
Bi-imp. rank
Csa. rank
CF rank
Bi-con. rank
M
→
J
5
9
17
6
5
10
5
6
8
M
→
G
14
15
19
12
14
16
14
11
15
J
→
G
13
13
18
23
12
14
10
9
13
I
→
H
3
6
12
5
2
6
3
5
4
I
→
F
11
12
22
3
8
12
7
3
11
H
→
F
23
21
25
22
23
21
23
23
22
R
→
G
7
8
5
1
3
4
4
2
2
N
→
G
22
22
20
20
22
22
22
21
21
R
→
F
20
20
24
18
20
20
20
20
20
N
→
F
16
16
14
11
15
15
15
14
16
M
→
F
10
11
21
2
7
11
6
1
10
J
→
F
19
19
23
17
19
19
19
19
19
G
→
F
25
24
16
24
25
24
25
25
24
J
→
M
4
7
13
8
9
8
9
10
9
G
→
J
12
10
6
13
13
9
13
15
12
H
→
I
2
5
11
4
1
5
2
4
3
F
→
I
9
3
3
10
11
3
12
13
7
G
→
R
6
1
1
7
6
1
8
7
1
G
→
N
21
23
15
19
21
23
21
22
23
F
→
R
18
18
8
16
18
18
18
18
18
F
→
N
15
14
4
14
16
13
16
16
14
F
→
M
8
2
2
9
10
2
11
12
6
F
→
J
17
17
7
15
17
17
17
17
17
F
→
G
24
25
9
21
24
25
24
24
25
M
→
L
1
4
10
25
4
7
1
8
5
Note: keep two digits after the decimal point.From Table5, we can see thatsupport andconfidence mainly have the function of basicsupport as classic association rules measure methods, but they can neither distinguish positive and negative correlation nor find the value of various rules. The differences of different measure methods exist, and one single objective interestingness measure method cannot decide which rules are really valuable. That means one must depend on the measure framework which combines multiple indexes.(1)
Thevalidity (Val) is not effective and has huge difference form other measure methods. Each rule in the Measure table ofvalidity is valid, but, in fact, many rules have no significance; for example, F
→
J, F
→
R are uncorrelated; F
→
G, G
→
N have negative inhibitory effect.
(2)
The traditionalsupport-confidence framework can eliminate most uncorrelated association rules; but, as low constraints, it can also produce a lot of uncorrelated frequent itemsets and even some negative correlated rules or rules of error.
(3)
Lift has a good evaluation result. But obviouslylift takes events A and B in equivalent position; l
i
f
t
(
A
→
B
) and l
i
f
t
(
B
→
A
) are the same; that is to say, if we accept rule A
→
B, B
→
A should be also accepted; under such situation, we proposeBi-lift to solve it.
(4)
ButBi-lift also has a small defect. Its premise is P
(
A
¯
B
)
≠
0, and A and B are not certain event or impossible event. Its value range is [
0
,
∞
).
(5)
Conviction’s value range is [
0
,
∞
). When the value ofconviction is “1,” it means that “A” does not have relation with “B.” And the greater theconviction is, the higher the interest of the rule will be. But theconviction constraints are too strict, and lots of valuable association rules will be removed. In Table 1, for example, C
o
n
v
i
c
t
i
o
n
(
M
→
L
)
=
0.4
×
0.8
/
0.5
=
0.64
<
1; itsconviction is low, but, in fact, the high interest of M and L may exist. The result of Certainty factor (CF) is very similar to that ofConviction.
(6)
Shortcomings ofImprove (Imp.) are obvious. Firstly, how much improvement of probability can be called improvement? Secondly, the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time. Thus, it is difficult to distinguish valuable rules and even tends to make inaccurate value evaluation. Therefore, this paper puts forwardBi-Improve aimed at evaluating rules value more accurately.
(7)
The evaluating results of the author’s “Bi-improve,” which is adjusted by the occurrence and nonoccurrence probability of the antecedent, will increase distinction and accuracy.
(8)
Chi-square analysis (Csa.) is proposed based on theImprove (Imp.). But the evaluations results indicate that the effects still have not been able to solve the problem ofimprove finally, and its evaluation performance is worse than that ofBi-improve.According to the evaluation results and the performance analysis for measure method, thevalidity (Val.) is not effective and sometimes it even appears as essential mistake. For instance, it is sometimes counterproductive, while its evaluation is a promotion.ThoughImprove (Imp.) andChi-square analysis (Csa.) do not have the essential mistakes, the stability of their evaluation is not good. Sometimes, they maybe are prone to computation error. However, evaluation results ofBi-lift,Bi-improve, andBi-confidence are almost the same, and their stabilities of evaluations are high. In conclusion, we can eliminate thevalidity (Val.),improve (Imp.),Chi-square analysis (Csa.), and other measure indicators. Among theSupport,Confidence,Lift,Bi-lift,Bi-improve, andBi-confidence, seek and build a reasonable measure framework. Procedures are as follow: firstly, useSupport andConfidence threshold to filter out frequent set; secondly, calculateBi-lift,Bi-improve, andBi-confidence value; then, according to theBi-lift,Bi-improve and theBi-confidence value evaluate association rules comprehensively. Actually the final evaluation results of these three kinds of measure methods are very close and they are perfect, which are shown in Tables 6 and 7. Evaluation results and comparisons ofBi-lift,Bi-improve, andBi-confidence are shown as Figure 1.Table 6
The sort of positive association rules.
Rules
Bi-lift
Bi-imp.
Bi-con.
Rank
G
→
R
7
0.49
0.71
1
F
→
M
6
0.4
0.5
2
F
→
I
6
0.4
0.5
3
R
→
G
2.5
0.3
0.6
4
H
→
I
4.5
0.23
0.58
5
I
→
H
4.5
0.23
0.58
6
M
→
L
5
0.2
0.5
7
J
→
M
3
0.2
0.4
8
G
→
J
1.71
0.18
0.24
9
M
→
J
2.25
0.16
0.42
10
M
→
F
1.5
0.13
0.33
11
I
→
F
1.5
0.13
0.33
12
F
→
N
1.25
0.12
0.13
13
J
→
G
1.33
0.1
0.2
14
N
→
F
1.11
0.045
0.08
15
M
→
G
1.13
0.03
0.08
16Table 7
The sort of negative association rules and meaningless rules.
Rules
Bi-lift
Bi-imp.
Bi-con.
Rank
H
→
F
0.9
−0.03
−0.08
17
N
→
G
0.89
−0.045
−0.08
18
G
→
N
0.86
−0.07
−0.1
19
G
→
F
0.71
−0.21
−0.28
20
F
→
G
0.63
−0.28
−0.38
21
F
→
J
1
0
0
22
F
→
R
1
0
0
23
J
→
F
1
0
0
24
R
→
F
1
0
0
25Figure 1
The radar map of evaluation results of measure methods.


### 5.2. Example Analysis Subjective Interestingness Measures

On the basis of utility function and the executing cost of rulesC
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics of specific application object. It plays an important role in the association rules evaluation and selection. According to a set of business data in Table 1, take verification of kinds of measure methods and design measure framework. Because item E appears in all affairs, take it as a kind of certain event and do not think of association rules about E. Set minimumsupport for 30% and minimumconfidence for 35%. Frequent 2 itemsets calculated through the a priori algorithm are shown in Table 8.Table 8
Various measure evaluation results of various rules.
(a)
Rules
Cost
Profit
Sup.
Con.
Lift
Imp.
Csa.
Bi-imp.
IFBP
H
→
I
1
2
0.3
0.75
1.88
0.35
2.26
0.23
0.23
I
→
H
5
6
0.3
0.75
1.88
0.35
2.26
0.23
0.23
R
→
G
5
4
0.5
1
1.42
0.3
2.1
0.3
−0.3
M
→
J
7
5
0.3
0.75
1.5
0.25
1.58
0.16
−0.32
G
→
R
3
3
0.5
0.71
1.42
0.21
1.33
0.49
0
I
→
F
1
5
0.4
1
1.25
0.2
1.58
0.13
0.52
M
→
F
5
5
0.4
1
1.25
0.2
1.58
0.13
0
J
→
M
6
3
0.3
0.6
1.5
0.2
1.29
0.2
−0.6
J
→
G
2
7
0.4
0.8
1.14
0.1
0.69
0.1
0.5
F
→
M
1
3
0.4
0.5
1.25
0.1
0.65
0.4
0.8
F
→
I
2
2
0.4
0.5
1.25
0.1
0.65
0.4
0
G
→
J
3
5
0.4
0.57
1.14
0.07
0.44
0.18
0.36
M
→
G
4
7
0.3
0.75
1.08
0.05
0.35
0.03
0.09
N
→
F
1
5
0.5
0.83
1.04
0.03
0.24
0.045
0.18
F
→
N
2
4
0.5
0.63
1.04
0.03
0.19
0.12
0.24
G
→
M
5
3
0.3
0.43
1.08
0.03
0.19
0.07
−0.14
F
→
J
3
5
0.4
0.5
1
0
0
0
0
F
→
R
1
3
0.4
0.5
1
0
0
0
0
J
→
F
2
5
0.4
0.8
1
0
0
0
0
R
→
F
2
5
0.4
0.8
1
0
0
0
0
F
→
H
5
7
0.3
0.38
0.95
−0.02
−0.13
−0.08
−0.16
G
→
N
3
4
0.4
0.57
0.95
−0.03
−0.19
−0.07
−0.07
N
→
G
2
4
0.4
0.67
0.95
−0.03
−0.21
−0.045
−0.09
H
→
F
3
5
0.3
0.75
0.95
−0.05
−0.4
−0.03
−0.06
F
→
G
1
4
0.5
0.63
0.89
−0.07
−0.48
−0.28
−0.84
G
→
F
4
5
0.5
0.71
0.89
−0.09
−0.71
−0.21
−0.21
(b)
Rules
Cost
Profit
Lift Rank
Imp. Rank
Csa. Rank
Bi-imp. Rank
IFBP Rank
H
→
I
1
2
1
1
1
5
6
I
→
H
5
6
2
2
2
6
7
R
→
G
5
4
6
3
3
4
23
M
→
J
7
5
3
4
4
9
24
G
→
R
3
3
5
5
7
1
12
I
→
F
1
5
8
6
5
10
2
M
→
F
5
5
10
7
6
11
15
J
→
M
6
3
4
8
8
7
25
J
→
G
2
7
11
9
9
13
3
F
→
M
1
3
7
10
10
2
1
F
→
I
2
2
9
11
11
3
13
G
→
J
3
5
12
12
12
8
4
M
→
G
4
7
13
13
13
16
9
N
→
F
1
5
16
14
14
15
8
F
→
N
2
4
15
15
15
12
5
G
→
M
5
3
14
16
16
14
20
F
→
J
3
5
17
17
17
17
10
F
→
R
1
3
18
18
18
18
11
J
→
F
2
5
19
19
19
19
14
R
→
F
2
5
20
20
20
20
16
F
→
H
5
7
24
21
21
24
21
G
→
N
3
4
22
22
22
23
18
N
→
G
2
4
23
23
23
22
19
H
→
F
3
5
21
24
24
21
17
F
→
G
1
4
26
25
25
26
26
G
→
F
4
5
25
26
26
25
22
Note: keep two digits after the decimal point.Evaluation results of these five kinds of measure methods are shown in Figure2. According to the result of evaluation and measure performance analysis, the evaluation results ofImprove (Imp.) andChi-square analysis (Csa.) are almost the same, their curves are almost coincidence. And their defects exist obviously.Lift andBi-improve have good performance of evaluation and similar tendency. Yetlift takes events A and B in equivalence position; if we accept rule A
→
B, B
→
A should be also accepted. For this situation,Bi-improve is the best choice. On the basis of utility function and the executing cost of rules C
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics specific application object. It plays an important role in the association rules evaluation and selection.Figure 2
Evaluation results of these five kinds of measure methods (Lift,Imp.,Csa., andN-Imp.,IFBP).


## 5.1. Example Analysis of Objective Interestingness Measures

According to a set of business data in Table1, take verification of kinds of measure methods and design measure framework. Because item E appears in all affairs, take it as a kind of certain event and do not think of association rules about E. Set minimumsupport for 20% and minimumconfidence for 50%. Frequent 2 itemsets calculated through the a priori algorithm are shown in Table 5.Table 5
Various measure evaluation results of various rules.
(a)
Rules
Sup.
Con.
Lift
Bi-lift
Val.
Conv.
Imp.
Bi-imp.
Csa.
CF
Bi-con.
M
→
J
0.3
0.75
1.5
2.25
0.1
2
0.25
0.16
1.58
0.50
0.42
M
→
G
0.3
0.75
1.08
1.13
0.1
1.2
0.05
0.03
0.35
0.17
0.08
J
→
G
0.4
0.8
1.14
1.33
0.1
0.75
0.1
0.1
0.69
0.33
0.2
I
→
H
0.3
0.75
1.88
4.5
0.2
2.4
0.35
0.23
2.26
0.58
0.58
I
→
F
0.4
1
1.25
1.5
0
/
0.2
0.13
1.58
1.00
0.33
H
→
F
0.3
0.75
0.95
0.9
−0.2
0.8
−0.05
−0.03
−0.4
−0.06
−0.08
R
→
G
0.5
1
1.42
2.5
0.3
/
0.3
0.3
2.1
1.00
0.6
N
→
G
0.4
0.67
0.95
0.89
0.1
0.9
−0.03
−0.05
−0.21
−0.04
−0.08
R
→
F
0.4
0.8
1
1
0
1
0
0
0
0.00
0
N
→
F
0.5
0.83
1.04
1.11
0.2
1.2
0.03
0.05
0.24
0.15
0.08
M
→
F
0.4
1
1.25
1.5
0
/
0.2
0.13
1.58
1.00
0.33
J
→
F
0.4
0.8
1
1
0
1
0
0
0
0.00
0
G
→
F
0.5
0.71
0.89
0.71
0.2
0.7
−0.09
−0.21
−0.71
−0.11
−0.28
J
→
M
0.3
0.6
1.5
3
0.2
1.5
0.2
0.2
1.29
0.33
0.4
G
→
J
0.4
0.57
1.14
1.71
0.3
1.17
0.07
0.18
0.44
0.14
0.24
H
→
I
0.3
0.75
1.88
4.5
0.2
2.4
0.35
0.23
2.26
0.58
0.58
F
→
I
0.4
0.5
1.25
/
0.4
1.2
0.1
0.4
0.65
0.17
0.5
G
→
R
0.5
0.71
1.42
/
0.5
1.75
0.21
0.49
1.33
0.42
0.71
G
→
N
0.4
0.57
0.95
0.86
0.2
0.93
−0.03
−0.07
−0.19
−0.05
−0.1
F
→
R
0.4
0.5
1
1
0.3
1
0
0
0
0.00
0
F
→
N
0.5
0.63
1.04
1.25
0.4
1.07
0.03
0.12
0.19
0.08
0.13
F
→
M
0.4
0.5
1.25
/
0.4
1.2
0.1
0.4
0.65
0.17
0.5
F
→
J
0.4
0.5
1
1
0.3
1
0
0
0
0.00
0
F
→
G
0.5
0.63
0.89
0.63
0.3
0.8
−0.07
−0.28
−0.48
−0.10
−0.38
M
→
L
0.2
0.5
2.5
/
0.2
0.64
0.3
0.2
2.37
0.38
0.5
(b)
Rules
Lift rank
Bi-lift rank
Val. rank
Conv. rank
Imp. rank
Bi-imp. rank
Csa. rank
CF rank
Bi-con. rank
M
→
J
5
9
17
6
5
10
5
6
8
M
→
G
14
15
19
12
14
16
14
11
15
J
→
G
13
13
18
23
12
14
10
9
13
I
→
H
3
6
12
5
2
6
3
5
4
I
→
F
11
12
22
3
8
12
7
3
11
H
→
F
23
21
25
22
23
21
23
23
22
R
→
G
7
8
5
1
3
4
4
2
2
N
→
G
22
22
20
20
22
22
22
21
21
R
→
F
20
20
24
18
20
20
20
20
20
N
→
F
16
16
14
11
15
15
15
14
16
M
→
F
10
11
21
2
7
11
6
1
10
J
→
F
19
19
23
17
19
19
19
19
19
G
→
F
25
24
16
24
25
24
25
25
24
J
→
M
4
7
13
8
9
8
9
10
9
G
→
J
12
10
6
13
13
9
13
15
12
H
→
I
2
5
11
4
1
5
2
4
3
F
→
I
9
3
3
10
11
3
12
13
7
G
→
R
6
1
1
7
6
1
8
7
1
G
→
N
21
23
15
19
21
23
21
22
23
F
→
R
18
18
8
16
18
18
18
18
18
F
→
N
15
14
4
14
16
13
16
16
14
F
→
M
8
2
2
9
10
2
11
12
6
F
→
J
17
17
7
15
17
17
17
17
17
F
→
G
24
25
9
21
24
25
24
24
25
M
→
L
1
4
10
25
4
7
1
8
5
Note: keep two digits after the decimal point.From Table5, we can see thatsupport andconfidence mainly have the function of basicsupport as classic association rules measure methods, but they can neither distinguish positive and negative correlation nor find the value of various rules. The differences of different measure methods exist, and one single objective interestingness measure method cannot decide which rules are really valuable. That means one must depend on the measure framework which combines multiple indexes.(1)
Thevalidity (Val) is not effective and has huge difference form other measure methods. Each rule in the Measure table ofvalidity is valid, but, in fact, many rules have no significance; for example, F
→
J, F
→
R are uncorrelated; F
→
G, G
→
N have negative inhibitory effect.
(2)
The traditionalsupport-confidence framework can eliminate most uncorrelated association rules; but, as low constraints, it can also produce a lot of uncorrelated frequent itemsets and even some negative correlated rules or rules of error.
(3)
Lift has a good evaluation result. But obviouslylift takes events A and B in equivalent position; l
i
f
t
(
A
→
B
) and l
i
f
t
(
B
→
A
) are the same; that is to say, if we accept rule A
→
B, B
→
A should be also accepted; under such situation, we proposeBi-lift to solve it.
(4)
ButBi-lift also has a small defect. Its premise is P
(
A
¯
B
)
≠
0, and A and B are not certain event or impossible event. Its value range is [
0
,
∞
).
(5)
Conviction’s value range is [
0
,
∞
). When the value ofconviction is “1,” it means that “A” does not have relation with “B.” And the greater theconviction is, the higher the interest of the rule will be. But theconviction constraints are too strict, and lots of valuable association rules will be removed. In Table 1, for example, C
o
n
v
i
c
t
i
o
n
(
M
→
L
)
=
0.4
×
0.8
/
0.5
=
0.64
<
1; itsconviction is low, but, in fact, the high interest of M and L may exist. The result of Certainty factor (CF) is very similar to that ofConviction.
(6)
Shortcomings ofImprove (Imp.) are obvious. Firstly, how much improvement of probability can be called improvement? Secondly, the probability of former pieces’ occurrence will seriously affectImprove evaluation in such a way that when it is high, theimprove value will be very small all the time. Thus, it is difficult to distinguish valuable rules and even tends to make inaccurate value evaluation. Therefore, this paper puts forwardBi-Improve aimed at evaluating rules value more accurately.
(7)
The evaluating results of the author’s “Bi-improve,” which is adjusted by the occurrence and nonoccurrence probability of the antecedent, will increase distinction and accuracy.
(8)
Chi-square analysis (Csa.) is proposed based on theImprove (Imp.). But the evaluations results indicate that the effects still have not been able to solve the problem ofimprove finally, and its evaluation performance is worse than that ofBi-improve.According to the evaluation results and the performance analysis for measure method, thevalidity (Val.) is not effective and sometimes it even appears as essential mistake. For instance, it is sometimes counterproductive, while its evaluation is a promotion.ThoughImprove (Imp.) andChi-square analysis (Csa.) do not have the essential mistakes, the stability of their evaluation is not good. Sometimes, they maybe are prone to computation error. However, evaluation results ofBi-lift,Bi-improve, andBi-confidence are almost the same, and their stabilities of evaluations are high. In conclusion, we can eliminate thevalidity (Val.),improve (Imp.),Chi-square analysis (Csa.), and other measure indicators. Among theSupport,Confidence,Lift,Bi-lift,Bi-improve, andBi-confidence, seek and build a reasonable measure framework. Procedures are as follow: firstly, useSupport andConfidence threshold to filter out frequent set; secondly, calculateBi-lift,Bi-improve, andBi-confidence value; then, according to theBi-lift,Bi-improve and theBi-confidence value evaluate association rules comprehensively. Actually the final evaluation results of these three kinds of measure methods are very close and they are perfect, which are shown in Tables 6 and 7. Evaluation results and comparisons ofBi-lift,Bi-improve, andBi-confidence are shown as Figure 1.Table 6
The sort of positive association rules.
Rules
Bi-lift
Bi-imp.
Bi-con.
Rank
G
→
R
7
0.49
0.71
1
F
→
M
6
0.4
0.5
2
F
→
I
6
0.4
0.5
3
R
→
G
2.5
0.3
0.6
4
H
→
I
4.5
0.23
0.58
5
I
→
H
4.5
0.23
0.58
6
M
→
L
5
0.2
0.5
7
J
→
M
3
0.2
0.4
8
G
→
J
1.71
0.18
0.24
9
M
→
J
2.25
0.16
0.42
10
M
→
F
1.5
0.13
0.33
11
I
→
F
1.5
0.13
0.33
12
F
→
N
1.25
0.12
0.13
13
J
→
G
1.33
0.1
0.2
14
N
→
F
1.11
0.045
0.08
15
M
→
G
1.13
0.03
0.08
16Table 7
The sort of negative association rules and meaningless rules.
Rules
Bi-lift
Bi-imp.
Bi-con.
Rank
H
→
F
0.9
−0.03
−0.08
17
N
→
G
0.89
−0.045
−0.08
18
G
→
N
0.86
−0.07
−0.1
19
G
→
F
0.71
−0.21
−0.28
20
F
→
G
0.63
−0.28
−0.38
21
F
→
J
1
0
0
22
F
→
R
1
0
0
23
J
→
F
1
0
0
24
R
→
F
1
0
0
25Figure 1
The radar map of evaluation results of measure methods.


## 5.2. Example Analysis Subjective Interestingness Measures

On the basis of utility function and the executing cost of rulesC
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics of specific application object. It plays an important role in the association rules evaluation and selection. According to a set of business data in Table 1, take verification of kinds of measure methods and design measure framework. Because item E appears in all affairs, take it as a kind of certain event and do not think of association rules about E. Set minimumsupport for 30% and minimumconfidence for 35%. Frequent 2 itemsets calculated through the a priori algorithm are shown in Table 8.Table 8
Various measure evaluation results of various rules.
(a)
Rules
Cost
Profit
Sup.
Con.
Lift
Imp.
Csa.
Bi-imp.
IFBP
H
→
I
1
2
0.3
0.75
1.88
0.35
2.26
0.23
0.23
I
→
H
5
6
0.3
0.75
1.88
0.35
2.26
0.23
0.23
R
→
G
5
4
0.5
1
1.42
0.3
2.1
0.3
−0.3
M
→
J
7
5
0.3
0.75
1.5
0.25
1.58
0.16
−0.32
G
→
R
3
3
0.5
0.71
1.42
0.21
1.33
0.49
0
I
→
F
1
5
0.4
1
1.25
0.2
1.58
0.13
0.52
M
→
F
5
5
0.4
1
1.25
0.2
1.58
0.13
0
J
→
M
6
3
0.3
0.6
1.5
0.2
1.29
0.2
−0.6
J
→
G
2
7
0.4
0.8
1.14
0.1
0.69
0.1
0.5
F
→
M
1
3
0.4
0.5
1.25
0.1
0.65
0.4
0.8
F
→
I
2
2
0.4
0.5
1.25
0.1
0.65
0.4
0
G
→
J
3
5
0.4
0.57
1.14
0.07
0.44
0.18
0.36
M
→
G
4
7
0.3
0.75
1.08
0.05
0.35
0.03
0.09
N
→
F
1
5
0.5
0.83
1.04
0.03
0.24
0.045
0.18
F
→
N
2
4
0.5
0.63
1.04
0.03
0.19
0.12
0.24
G
→
M
5
3
0.3
0.43
1.08
0.03
0.19
0.07
−0.14
F
→
J
3
5
0.4
0.5
1
0
0
0
0
F
→
R
1
3
0.4
0.5
1
0
0
0
0
J
→
F
2
5
0.4
0.8
1
0
0
0
0
R
→
F
2
5
0.4
0.8
1
0
0
0
0
F
→
H
5
7
0.3
0.38
0.95
−0.02
−0.13
−0.08
−0.16
G
→
N
3
4
0.4
0.57
0.95
−0.03
−0.19
−0.07
−0.07
N
→
G
2
4
0.4
0.67
0.95
−0.03
−0.21
−0.045
−0.09
H
→
F
3
5
0.3
0.75
0.95
−0.05
−0.4
−0.03
−0.06
F
→
G
1
4
0.5
0.63
0.89
−0.07
−0.48
−0.28
−0.84
G
→
F
4
5
0.5
0.71
0.89
−0.09
−0.71
−0.21
−0.21
(b)
Rules
Cost
Profit
Lift Rank
Imp. Rank
Csa. Rank
Bi-imp. Rank
IFBP Rank
H
→
I
1
2
1
1
1
5
6
I
→
H
5
6
2
2
2
6
7
R
→
G
5
4
6
3
3
4
23
M
→
J
7
5
3
4
4
9
24
G
→
R
3
3
5
5
7
1
12
I
→
F
1
5
8
6
5
10
2
M
→
F
5
5
10
7
6
11
15
J
→
M
6
3
4
8
8
7
25
J
→
G
2
7
11
9
9
13
3
F
→
M
1
3
7
10
10
2
1
F
→
I
2
2
9
11
11
3
13
G
→
J
3
5
12
12
12
8
4
M
→
G
4
7
13
13
13
16
9
N
→
F
1
5
16
14
14
15
8
F
→
N
2
4
15
15
15
12
5
G
→
M
5
3
14
16
16
14
20
F
→
J
3
5
17
17
17
17
10
F
→
R
1
3
18
18
18
18
11
J
→
F
2
5
19
19
19
19
14
R
→
F
2
5
20
20
20
20
16
F
→
H
5
7
24
21
21
24
21
G
→
N
3
4
22
22
22
23
18
N
→
G
2
4
23
23
23
22
19
H
→
F
3
5
21
24
24
21
17
F
→
G
1
4
26
25
25
26
26
G
→
F
4
5
25
26
26
25
22
Note: keep two digits after the decimal point.Evaluation results of these five kinds of measure methods are shown in Figure2. According to the result of evaluation and measure performance analysis, the evaluation results ofImprove (Imp.) andChi-square analysis (Csa.) are almost the same, their curves are almost coincidence. And their defects exist obviously.Lift andBi-improve have good performance of evaluation and similar tendency. Yetlift takes events A and B in equivalence position; if we accept rule A
→
B, B
→
A should be also accepted. For this situation,Bi-improve is the best choice. On the basis of utility function and the executing cost of rules C
o
s
t
(
A
→
B
), we propose interestingness function based on profit (IFBP) considering subjective preferences and characteristics specific application object. It plays an important role in the association rules evaluation and selection.Figure 2
Evaluation results of these five kinds of measure methods (Lift,Imp.,Csa., andN-Imp.,IFBP).


## 6. Conclusion

As a statistics based method, association rule mining has certain limitations. First of all, the generation of the association rules is totally based on the fact data without considering the relationship between the rules. Secondly, affected by data quality and selection of threshold, the generator may produce useless rules or even lose some useful rules. Thirdly, the expression ability of association rules is limited. Thus, evaluating the reliability of the obtained association rules becomes one of the hot spots for researchers. Study on traditional association rules mining is based onsupport-confidence framework, and the rules are called strong association rules only when they satisfy both thresholds ofsupport andconfidence. However, sometimes strong association rules are not what users are interested in and are even misleading. Thus, to further analyze and evaluate the mined rules in order to find the most valuable association.Generally, since most rules with highsupport are obvious or are already known by users, lowsupport rules that provide users with some interesting new knowledge may be more novel than highsupport rules. However, with too lowsupport threshold, it can also produce the combination explosion problem. So the best way to resolve this dilemma is to first set a lowsupport threshold or use dynamicsupport threshold to complete a series of mining and then employ the new association rules measure framework to screen mining results and extract the most valuable and interesting association rules at the same time.



---

*Source: 868634-2015-07-09.xml*