Association rules are essential data mining tool and as such has been well researched. Many new types of association rules based on both categorial or quantitative data have been founded ([8], [7], [2], [4]). Our work is directed to the theoretical features of association rules; especially, we study a specific class of association rules called δ -cosymmetric rules. We present here some interesting properties of such rules and provide a definition of rules expressing the significant difference in position, as an example. We show here that even the usual implicational rules are special cases of δ -cosymmetric rules.
This paper is intended to motivate the rise of a new class of association rules called δ -cosymmetric rules. First of all, we describe here brieyfl the notions of the Logic of typed relations used to write the association rules down (for more information see [6]). After that, we provide some motivating examples of the representative cosymmetric rule types. We also study several features of the δ cosymmetric rules and define the δ -cosymmetric rule of significant difference in position. The end of this paper is dedicated to some notes on how to mine the δ -cosymmetric rules.
In [6], we have developed the Probabilistic Logic of Typed Relations (PLTR) suitable for the formal association rules representation. In this section we brieyfl and informally describe main notions of that logic to understand the meaning of its formulae.
The main notion of PLTR is typed relation. Typed relation can be simply viewed as a data table with nfiite number of columns and rows. Each column represents one attribute and a set of such attributes is a type of the relation.
A typed relation is similar to classical concept of mathematical relation. We can perform usual set operations as union (∪), intersection (∩) or difference (− ). Furthermore, there exist two crucial relational operations: selection and projection. Selection is an unary operation of the form
R(c1 ∧ c2 ∧ ¬c3)
R(age > 25)
R[A1, A2, . . . , An]. where R is typed relation and c1 ∧ c2 ∧ ¬c3 is a formula called selection condition. Selection is used to select only the rows satisfying the given condition. For example, when R is a data table (typed relation) of university students, the selection picks only the students older than 25. The projection on relation R is an unary operation of the form The projection is used to take out only several columns (attributes) of the relation R. The choosed attributes are simply written in the comma-separated list in the brackets. The projection
results simply in the two-column data table with student’s basic personal information. Obviously, we can combine selection and projection together to pick up an arbitrary sub-relation of the original typed relation, e.g.
which results in a relation of basic personal information of students older than 25. (See also figure 1.) The rules written in PLTR use the relational operations described above to explicitly express a knowledge. For example,
R(age > 65)[blood pressure] >?mean R(age < 21)[blood pressure]
tells that the blood pressure of people older than 65 is in average significantly
higher than for people younger than 21. In the above rule we use a mapping
>?mean to express the strong difference in the mean value between two “data
columns”. (See also figure 2.) The mapping >?mean is simply a function, which
computes a truth value of the strong difference in mean from the given two typed
relations.
(
sex = “female” ⇒ wage: mean = $7.90/hr (overall mean wage = $9.02). (
R(sex = “female”)[wage] <?mean R(sex 6= “female”)[wage] and
R(non-smoker ∧ wine-drinker)[life-expectancy] >?mean
R(¬(non-smoker ∧ wine-drinker))[life-expectancy].
Our research shows that many types of the associational rules can be transformed to the fashion of comparing “something” against “something else” (later in this paper, we mention some of them). Thus, it is natural to expect that such rules will have some equal properties and that it will behave similarly in alike situations. Therefore it is reasonable to identify the common features and use them in general definition of a new class of association rules. Later in this paper we try to do so and name the class of such association rules the δ -cosymmetric rules.
Moreover, it is obvious to contemplate rules of type (
The following subsections try to highlight some properties that are common in the class of association rules we want to name δ -cosymmetric. After that, we provide the first prototype definition of what δ -cosymmetric rule is.
We start with the domain of the δ -cosymmetric predicate <?. We can see,
the rules of type (
Let R is a set of all typed relations. We may expect that each δ -cosymmetric predicate’s domain D equals to the carthesian product of some set of typed relations: ∃K ⊆ R : D = K ×
K.
This property tells us that for each typed relations A, B ∈ K, hA, Ai, hA, Bi and hB, Ai are comparable by the δ -cosymmetric predicate. That is, one can ask the truth value of the formulae <? (A, A), <? (A, B), <? (B, A) for each A, B ∈ K. 3.2
When mining the rules of type (
The same concept can be used when comparing variances, probability or anything else. – The next thing common to each cosymmetric rule is the possibility to employ the minimum difference δ to it.
In the following, we will write the rule of the minimum difference δ the subsequent way:
R(C1)[A] >δ? R(C2)[A]
(
R(sex = “female”)[wage] <?mean;$5 R(sex 6= “female”)[wage]. 3.3
In the following, we will need to denfie the negation of formula F . Suppose F is
formula of PLTR (e.g. (
The third common feature of rules similar to (
More generally, the truth value of a statement “objects of relation B are minimally over δ less than objects of relation A” equals to a negation of the statement “objects of relation A are minimally over (− δ ) less than objects of the relation B”. Formally written: When δ = 0 is omitted, it leads to <δ? (B, A) ⇔ ¬
<−? δ (A, B) . <? (B, A) ⇔ ¬ <? (A, B) . or prexfiually:
>δ? R(C1)[A], R(C2)[A] .
E.g. see the rule of the difference in wage of at least $5: 3.4
Let >δ?1 A, B = hl1, h1i and >δ?2 A, B = hl2, h2i where >? is a predicate similar to the previously discussed. One can observe that the following holds all the time:
δ 1 < δ 2 ⇒ (l1 ≥ l2) ∧ (h1 ≥ h2) . (
We name probable the rule, which truth value i = hl, hi satisfies the condition
0, 5 < l. Let <δ? (A, B) = hl1, h1i, <δ? (B, C) = hl2, h2i and <δ? (A, C) = hl3, h3i.
The last property of rules similar to (
(0, 5 < l1) ∧ (0, 5 < l2) ⇒ 0, 5 ≤ l3 . (12) Informally, when some sub-table A is probably lower than B and B is probably lower than C, it implies that A is probably not higher than C.
Please note, we can’t say that the probability of A <? C is higher or equals to
the maximum or minimum of the probabilities of A <? B and B <? C, because
such condition holds in fact very seldom.
(
Actually, we are still working on the precise denfiition of the δ -cosymmetric
relationship predicate. We try to unhide the important properties of the rules
similar to (
Definition 1. Let R be the set of all typed relations, V the set of all truth values, K ⊆ R and D = K × K. We name <? the cosymmetric predicate schema if <? is a set of relationship predicates <δ?: D → V (defined for each δ ∈ R) and if the following holds: 1. For each typed relations A, B ∈ K and δ ∈ R holds: <δ? (A, B) = ¬
<−? δ (B, A) , δ 1 < δ 2 ⇒ (l1 ≥ l2) ∧ (h1 ≥ h2), 2. For each typed relations A, B ∈ K and δ 1, δ 2 ∈ R and i1 = hl1, h1i, i2 = hl2, h2i such that <δ?1 (A, B) = i1, <δ?2 (A, B) = i2 holds: 3. For each typed relations A, B, C ∈ K and δ ∈ R and i1 = hl1, h1i, i2 = hl2, h2i, i3 = hl3, h3i, such that <δ? (A, B) = i1, <δ? (B, C) = i2, <δ? (A, C) = i3, holds:
(0, 5 < l1) ∧ (0, 5 < l2) ⇒ 0, 5 ≤ l3 .
The elements <δ? of the set <? are called δ -cosymmetric relationship predicates. The set D is also called the domain of the cosymmetric predicate schema. 4
In the above section we have discussed several properties of a so-called cosymmetric rules. In this section, we provide an exemplary denfiitions of such rule type. 4.1
The idea for cosymmetric rules of significant difference in position is subsequent.
One may have data which are quantitative and may ask, for which subsets of
data the focused quantitative attribute is rather higher or lower in contrast
to the rest (c.f. rule (
For such purpose we use the Aspin–Welch statistical test (see [3]), which is two-sample test on means. The test is similar to the common Student’s t test. It assumes the two random samples X and Y to be normally distributed (there is no need of equal variances) and it tests the zero hypothesis H0 : EX − EY = δ against the two-sided alternative hypothesis HA : EX − EY 6= δ . The test statistic is f =
S4 m2(SmX4− 1) + n2(nY− 1)
S4 .
T = X¯ − Y¯ − δ ,
S where
S = r SX2 + m
S2
Y ; n The hypothesis H0 is rejected if |T | ≥ tf (1 − α2 ), where tf is a distribution function of Student’s distribution with f degrees of freedom.
Pursuant to the one-sided Aspin–Welch statistics, we can define the relationship predicate <?AW ;δ as follows.
Definition 2. Predicate <?AW ;δ is a function where an interval of probability i = hp, pi is mapped the following way to each pair of typed relations hX, Y i, which both are non-empty and both contain just one column.
<?AW ;δ (X, Y ) = hp, pi for such p where T = tf (p) for T , f and tf as above.
The usage example comes after. Suppose we have a data table D about patients suffering certain disease. Let such table contains categorial column sex and quantitative column pressure. One may be interested whether D(sex = “male”)[pressure] gives higher values than D(sex = “female”)[pressure]. That is, one enquires the validity of the following rule:
D(sex = “male”)[pressure] >AW ;0 D(sex = “female”)[pressure].
Now we can take a closer look at the Aspin–Welch predicate <?AW ;δ to see, whether it has all the properties enumerated in section 3.6.
Theorem 1. The set of all Aspin–Welch relationship predicates <?AW ;δ (∀δ ) is cosymmetric predicate schema.
Proof. (a) Non-symmetricity. We should check the equivalence (
T1 =
X¯ − Y¯ − δ
S = tf (p1) and
T2 =
Y¯ − X¯ − (− δ )
S = tf (p2).
We see that T1 = − T2, so tf (p1) = − tf (p2). It is commonly known that tf (p) = − tf (1 − p), so p1 = 1 − p2.
(b) Monotony. It is commonly known that tf (p) is monotone, so when we increase δ , the value of characteristics T gets lower and so does the value of the resultant probability p.
(c) Quasi-transitivity. the validity of quasi-transitivity condition is evident
from the fact that ∀f ∈ N : tf (
We can go on and define various other δ -cosymmetric predicates similar to the denfiition of Aspin–Welch predicate. We don’t have enough space for such definitions, so let us leastwise mention some possibilities.
We can denfie many other predicates for determining the significant difference in position. Such definitions could be based on various existing statistical tests – it is possible e.g. to employ the rank tests to achieve robust cosymmetric predicates etc. Similarly to the signicfiant difference in position, we can denfie predicates deciding of the difference in variance (dispersion). For example, we can mine rules telling us whether the presence of some attribute puts there significant increase of dispersion of some other attribute etc.
We can employ the two-sample tests on binomial distribution to generate rules about discrete attributes. Generally said, almost every two-sample statistical test may be considered to be used in a denfiition of appropriate cosymmetric predicate.
Let’s have a look on the implicational rules of type (
The GUHA method ([8], [7]) works with the so-called generalized quantifiers . These quantiefirs form the base for the association rule creation. The rules are of the form ϕ ∼ ψ , where ϕ and ψ are formulae and ∼ the generalized quantifier. The truth of the rule is determined from a 4-field table (see table 1), which summarizes the amount of objects satisfying ceratin congfiurations.
More on such rules can be read from [8], [7] or [10]. The example of the rule
based on the funded implication is (
Now, we provide a definition of a predicate that is similar to the quantiefir of funded implication. After that, we show that it is δ -cosymmetric. Definition 3. Let A and B be the typed relations, each containing exactly one column with values from the set {0, 1} and let δ ∈ [− 1, 1]. Let us denote sum(A) the number of A’s rows possessing “1”. We define the Funded relationship predicate <f?nd;δ as follows:
>f?nd;δ (A, B) = h1, 1i >f?nd;δ (A, B) = h0, 5, 0, 5i >f?nd;δ (A, B) = h0, 0i iff iff iff
sum(A) sum(A) + sum(B)
sum(A) sum(A) + sum(B)
sum(A) sum(A) + sum(B) > = < , , .
Theorem 2. The set of all funded relationship predicates <f?nd;δ (∀δ ) is cosymmetric predicate schema.
Proof. (a) Non-symmetricity. We must prove that a+ab > 1+δ iff 2 a+b < 1− 2 δ .
b ⇔ ⇔ (b) Monotony and (c) Quasi-transitivity are obvious.
a+b > 1+δ a 2 ⇔ 2a a+b − 1 > δ 1 − a2+bb > δ ⇔ 2a+a2+bb− 2b − 1 > δ a+b < 1− 2 δ .
b ⇔
If we omit the minimum support constraint in the denfiition of the funded implication, we get the same rules as with the funded δ -cosymmetric predicate. In the other words, the rule
ϕ ⇒p,0 ψ is true on data table R iff the following rule has truth value equal to h1, 1i:
R(ψ )[ϕ] >f?nd;(2p− 1) R(¬ψ )[ϕ].
As a result we can say that implicational GUHA rules are just special cases of δ -cosymmetric rules. This surprising result convinced us of the importance of the δ -cosymmetric rules research. 5
Consider the general pattern of a δ -cosymmetric rule:
R(C1)[A] >? R(C2)[A]. (13) When mining such rules, we can generate and test virtually every combination of C1, C2, A, but doing so makes not much sense. It is because the association rule mining process results often in a wide range of association rules and it is sometimes hard to be acquainted with it. Moreover, only several combinations of conditions C1 and C2 are easy to interpret. Consider the following rule – although it may be true, the analyst has probably no usage for it.
R(eyes = “blue” ∧ sex = “male”)[fat] >? R(age > 30 ∧ wage < $200)[fat] (14)
In the following, we try to recognize the patterns of δ -cosymmetric rules of better interest than general pattern (13).
The easiest pattern of interesting δ -cosymmetric rules is
R(C)[A] >? R(¬C)[A].
We take one condition C and compare values of some quantitative attribute A for two sub-tables where the rfist satisfies the given condition C and the second doesn’t. Such rules express the condition at which the values of attribute A are “somehow” signicfiantly higher (or lower) than the rest of the data table. This basic pattern we name one-against-the-rest.
A pattern similar to (15) is conditional one-against-the-rest :
R(C1 ∧ C2)[A] >? R(¬C1 ∧ C2)[A]. (15) (16) This pattern stands for “when considering only values fullfiling the condition C2, the additional condition C1 indicates the signicfiant increase of value A (in the sense of >?).” That is, we fisrt restrict ourselves on data rows satisfying C2 only and then we search simply the one-against-the-rest rules on them. 5.2
The pattern one-on-one is a little more tricky. It is good in situations, when we want to compare groups created accordingly to one categorial attribute. Suppose attribute B be categorial with domain {b1, b2, . . . , bn}. Let moreover attribute A be quantitative. The pattern one-on-one is as follows:
R(B = bi)[A] >? R(B = bj )[A] (for i 6= j).
(17) The rule of such type means: “The objects with value bi in attribute B involve significantly higher values of attribute A than objects with value bj in attribute B.” Generally, we can generate and test n2 different hypotheses for a categorial attribute with n various values.
We can add an additional condition C to form conditional one-on-one pattern, too:
R(B = bi ∧ C)[A] >? R(B = bj ∧ C)[A] (for i 6= j).
(18) 6
The large size of the association rule mining results is the common problem. Analyst hardly orientates himself or herself in a big list of mined rules. Therefore, we enumerate here some hints of how to prune the result from less-interesting rules and so to restrict the resultant δ -cosymmetric formulae to the reasonable amount. 1. The significance level – the basic restriction on eventual rules is stating the minimum probability of its validity – in the other words, one may set a number pmin and throw away every rule, which truth value is below that threshold. Signicfiance level can be pre-set to any of the usual values as 0,95 or 0,99. 2. Contradictory conditions – the conditions appearing in the rule should be contradictory. That is, when considering the rule
R(C1)[A] >? R(C2)[A] then the formula C1 ∧ C2 should be contradiction. Rules satisfying that criterion are more easily interpretable and we avoid the uncorrect statistical comparing of non-disjunctive samples. (Compare with rule (14). Note also that the rules based on one-against-the-rest or one-on-one are all of contradictory conditions.) 3. Minimum support – minimum support is the best-known instrument for pruning away the non-interesting conditions from which the association rules are going to be formed. The minimum support criterion simply says that there must exist minimally minsup objects satisfying condition that appears in the rule. If not, such condition isn’t used in the association rule generating process. The definition of the minsup value greatly improves the efficience of association rule mining algorithms (see [1], [9], [11] for more information).
Minimum support should be set by expert only. 4. Minimum difference – setting the minimum difference δ is analogous to the stating of minimum rule probability. Doing so we express that we are interested in the rules, which confirm the dissimilarity to be at least of size δ .
Minimum difference should be set by expert only. 5. Easy-to-interpret rules only – in section 5 we have shown that generating all possible rules makes no sense. One may to generate only the rules, which are easy to interpret. That is, we should generate rules conforming to the patterns discussed in section 5. A similar criterion on that topic is to use conditions in conjunctive form only. 7
In this paper, we have introduced the new class of association rules – the δ cosymmetric rules. We are the first who has shown, how to use the Probability logic of typed relations (PLTR, see [6]) to express rules of such type. This paper also shows the benetfi of using PLTR as a language for writing the association rules in, too.
We have identiefid the basic properties of δ -cosymmetric rules and provided the definition of rules of signicfiant difference in position, as an example. The second part of this paper was dedidacted to some notes on how to generate the δ -cosymmetric rules to obtain the interesting rules only.
This paper also presents two basic examples of concrete δ -cosymmetric rules: the Aspin–Welch predicate and the Funded predicate. The second is surprise for us, since it shows that GUHA’s implicational rules are just the special cases of more general δ -cosymmetric rules.
Our future work will address the deeper research of δ -cosymmetric rules. We will try to unhide more interesting features of that rule class. For example, our actual research shows that the cosymmetric rules can be used in the denfiition of a function that is metric. An interesting task will be undisputably the clustering using such metrics, etc.
We are also focused on nfiding the fast and efficient algorithm to mine the δ -cosymmetric rules. A lot of work was done in [4] by Aumann and Lindell. (However, they didn’t know that they are mining cosymmetric rules – their algorithm should be slightly modiefid to comply the wide range of possible rule types.)
We are also interested in the methods of visualisation of δ -cosymmetric rules. The properties of δ -cosymmetric rules make rational to use the slightly modified Hasse’s diagrams to visualize the rules mined according to the pattern “oneon-one” discussed above. We also work on employing the conceptual lattices to represent mined δ -cosymmetric rules.