# An Extension of Totohasina’s Normalization Theory of Quality Measures of Association Rules

Authors: Armand; André Totohasina; Daniel Rajaonasy Feno
Journal: International Journal of Mathematics and Mathematical Sciences
 (2019)

---

## Abstract

In the context of binary data mining, for unifying view on probabilistic quality measures of association rules, Totohasina’s theory of normalization of quality measures of association rules primarily based on affine homeomorphism presents some drawbacks. Indeed, it cannot normalize some interestingness measures which are explained below. This paper presents an extension of it, as a new normalization method based on proper homographic homeomorphism that appears most consequent.


---

## Body

## 1. Introduction

In the context of the implicative statistical analysis (ISA) [1], you can never leave aside the probabilistic notions of the measures of quality which assess the degree of implicative link between two patterns of association rule. In light of very rich number of measures in the literature of the binary database, researchers are working [2–7] parallelly to find the more general relationships allowing to classify partially or entirely these various measures of interest. Hence the creation of highly founded concept called “normalization under five constraints quality measures” in the context of data mining appeared in 2003 [2]. This definition of normalized measures is acquired. It thus turns out that all MGK normalizable measures by affine homeomorphism become comparable [2, 8]. Although this author has already well-treated this subject, the problem of normalization of probabilistic quality measures remains not fully resolved. Indeed, the tool called affine homeomorphism he used may have some weakness, because it cannot normalize a measure intended to the infinity at least one of reference situations more or less intuitive such asthe incompatibility, the statistical independence, and logical implication [1, 9–12], for example, the measuresCost Multiplying, Sebag, Conviction, Odd-Ratio, Informal Gain, and Ratio of Example counter-example. Therefore, as already announced by the author ([13] paragraph 3.2 page 65) “the problem remains open concerning the transformation allowing normalization of other measures in a way still to be specified”. We are interested in this issue. This article proposes a way to partly solve this problem and discussion. First, let us recall below our proposed definition of a normalized quality measure which is evolving with three intuitive events as incompatibility, stochastic independence, and implication.Definition 1 (cf. [6, 13–15]).
LetX andY be itemset of a context of binary data mining D=(T,I,R), P the uniform discrete probability on probabilizable space (T,P(T)) [2], T all sets of transactions, I the set of attributes called items or patterns, R the binary relation from T to I, μ a probabilistic quality measure, and X→Y an association rule, with X∩Y=∅. ∀x∈I, X′=e∈T/∀x∈X;eRx denoted the extention of the itemset X: X′ is hence an event of the discrete probability (T,P(T),P). A quality measure μ of an association rule is called to be normalized if it verifies the five conditions below: (i)
μ(X→Y)=-1, if P(Y′/X′)=0; i.e., X′ and Y′ are two incompatible events: this means the two patterns X and Y are incompatible then;(ii)
-1<μ(X→Y)<0, if 0<P(Y′/X′)<P(Y′); i.e., X′ and Y′ are two negatively dependent events, and as such both X and Y patterns are then negatively dependent;(iii)
μ(X→Y)=0, if P(Y′/X′)=P(Y′); i.e., the two events X′ and Y′ are independent and this means both X and Y are independent itemsets;(iv)
0<μ(X→Y)<1, and 0≠P(Y′/X′)>P(Y′); i.e., if X′ and Y′ are positively dependent, therefore the two itemsets X and Y are positively dependent;(v)
μ(X→Y)=1, and P(Y′/X′)=1 or if X′⊆Y′: the itemset X is then completely included in Y. X′=e∈T/∀x∈X;eRx; i.e., the set of all transactions contains the pattern X [6].Example 2.
According to the definition mentioned above, it is easy to show that theMGK measure defined by MGK(X→Y)=MGKf(X→Y)MGKd(X→Y)
whereMGKf(X→Y)=(P(Y′/X′)-P(Y′))/(1-P(Y′)), if X favors Y, and MGKd(X→Y)=(P(Y′/X′)-P(Y′))/P(Y′), if X disfavors Y, is normalized.Note that this measure was discovered independently by three authors from three continents: by S. Guillaume in France in her thesis [15], by A. Totohasina in [2] in Madagascar at his research on normalization, at that time he appointed ION “Implication Oriented Normalised”, and by X. Wu, C. Zhang, and S. Zhang in [5] in USA under the name of CPIR “Conditional Probability Incrementation Ratio”. Its rich and interesting mathematical properties are studied in [6, 15]. In addition, it is historically interesting to notice that this measure was partially discovered asCertainty Factor (CF) by Edward H. Shortliffe and Bruce G. Buchanan in USA at 1975 [12]. Fernando Berzal et al. [16] established some statistical properties ofCF and its relation with some common interestingness measures as Confidence and Conviction.Hereafter, our work is divided into five sections. Section2 recalls some properties of a homographic homeomorphism that will be the main subject of our contribution. Section 3 offers a new normalization process based on homographies, in order to solve the aforementioned problem. Section 4 recommends the raw results of each of the normalized measures. Section 5 raises a conclusion.


## 2. About Homographic Function Processing Tool

### 2.1. Definition and Reminders

In mathematics, a homographic function is a function which can be represented as the form of quotient of two linear functions. It is bijective and its inverse function is a particular homographic function. In the commutative fieldR a homographic function f on R is a function in itself defined by f(x)=(ax+b)/(cx+d), where a,b,c, and d are real numbers such as ad-cb≠0. Prohibit ad-bc to be zero to avoid a constant function. Sometimes the condition “c not zero” is added, as the case c=0 corresponds to linear functions, but then we lose the group structure of the set of homographic functions with the composition of applications.We will retain that a homographic function is a homeomorphism of the formR∖-d/c→R:x↦(ax+b)/(cx+d), where (ad-bc≠0). This function determines a bijection from R∖-d/c to R∖a/c whose inverse bijection f-1(x)=-(dx-b)/(cx-a), which has the same determinant (ad-bc≠0). Note that f-1 is a homography of the same type as f and the graphs of homography f and f-1 are hyperbolas.It is seen that if we extendf by f-d/c=∞ and f∞=a/c, we obtain a projective application and let us denote R¯=R∪∞.Derivative and Variation. In the real homography case f, its derivative is f′(x)=abcd/cx+d2, where abdc=ac-bd is the determinant of the matrix abcd and so is called the determinant of the homography f and denoted det(f). For this reason, here are the variations in the homographic function: if det(f) is positive, then f is increasing on its two definition intervals; if det(f) is negative, then f is strictly decreasing on both definition intervals.


### 2.2. Canonical Form

Letf be a homography such that f(x)=(ax+b)/(cx+d), with (ad-bc≠0).In casec is not zero, the canonical form (also called reduced form) of a homographic function is f(x)=α/(x+β)+γ, where α=bc-ad/c2, β=d/c, and γ=a/c. By making a change in reference by taking a point S, the set projective applications, of coordinates β,γ as a new origin, the expression of the homographic function becomes f(x)=α/x which corresponds to the inverse function multiplied by the scalar α=bc-ad/c2.Morality. Any own homographic function nonzero determinant can thus be reduced to a homographic function type as x↦k/(x+m), with k≠0.From now, we are interested in all homographies of type asx↦k/(x+m), with k≠0, that limx→∞(k/x+m)=0∈R: own homography thus returns infinity to a real finite. Knowing that, this time, our main objective is to “make the infinity to be finite”, we thereafter consider the measures that have infinity value among the three conditions such aslogical implication, stochastic independence, and incompatibility; we use the homographic function mentioned above. Then, for any situation not leading to infinity, it is relevant to use the theory in [13] which is based on the use of an affine homeomorphism. Taking advantage of the fact that affine applications are part of the great family of homographies and appear as degenerate homographies returning infinity to infinity, we will enhance the whole nonconstant homographies. In the current theory we can combine the theory in [2] and the one we have just proposed. It is thus a natural extension of such approach of [14].


### 2.3. Notations

For convenience let us denote byx the value of the probabilistic quality measure μ(X→Y), by ximp the value of μ(X→Y), at logical implication, xind that of μ(X→Y) at independence, and xinc the value of μ(X→Y) at incompatibility, where (ximp,xind,xinc)∈R¯3.


## 2.1. Definition and Reminders

In mathematics, a homographic function is a function which can be represented as the form of quotient of two linear functions. It is bijective and its inverse function is a particular homographic function. In the commutative fieldR a homographic function f on R is a function in itself defined by f(x)=(ax+b)/(cx+d), where a,b,c, and d are real numbers such as ad-cb≠0. Prohibit ad-bc to be zero to avoid a constant function. Sometimes the condition “c not zero” is added, as the case c=0 corresponds to linear functions, but then we lose the group structure of the set of homographic functions with the composition of applications.We will retain that a homographic function is a homeomorphism of the formR∖-d/c→R:x↦(ax+b)/(cx+d), where (ad-bc≠0). This function determines a bijection from R∖-d/c to R∖a/c whose inverse bijection f-1(x)=-(dx-b)/(cx-a), which has the same determinant (ad-bc≠0). Note that f-1 is a homography of the same type as f and the graphs of homography f and f-1 are hyperbolas.It is seen that if we extendf by f-d/c=∞ and f∞=a/c, we obtain a projective application and let us denote R¯=R∪∞.Derivative and Variation. In the real homography case f, its derivative is f′(x)=abcd/cx+d2, where abdc=ac-bd is the determinant of the matrix abcd and so is called the determinant of the homography f and denoted det(f). For this reason, here are the variations in the homographic function: if det(f) is positive, then f is increasing on its two definition intervals; if det(f) is negative, then f is strictly decreasing on both definition intervals.


## 2.2. Canonical Form

Letf be a homography such that f(x)=(ax+b)/(cx+d), with (ad-bc≠0).In casec is not zero, the canonical form (also called reduced form) of a homographic function is f(x)=α/(x+β)+γ, where α=bc-ad/c2, β=d/c, and γ=a/c. By making a change in reference by taking a point S, the set projective applications, of coordinates β,γ as a new origin, the expression of the homographic function becomes f(x)=α/x which corresponds to the inverse function multiplied by the scalar α=bc-ad/c2.Morality. Any own homographic function nonzero determinant can thus be reduced to a homographic function type as x↦k/(x+m), with k≠0.From now, we are interested in all homographies of type asx↦k/(x+m), with k≠0, that limx→∞(k/x+m)=0∈R: own homography thus returns infinity to a real finite. Knowing that, this time, our main objective is to “make the infinity to be finite”, we thereafter consider the measures that have infinity value among the three conditions such aslogical implication, stochastic independence, and incompatibility; we use the homographic function mentioned above. Then, for any situation not leading to infinity, it is relevant to use the theory in [13] which is based on the use of an affine homeomorphism. Taking advantage of the fact that affine applications are part of the great family of homographies and appear as degenerate homographies returning infinity to infinity, we will enhance the whole nonconstant homographies. In the current theory we can combine the theory in [2] and the one we have just proposed. It is thus a natural extension of such approach of [14].


## 2.3. Notations

For convenience let us denote byx the value of the probabilistic quality measure μ(X→Y), by ximp the value of μ(X→Y), at logical implication, xind that of μ(X→Y) at independence, and xinc the value of μ(X→Y) at incompatibility, where (ximp,xind,xinc)∈R¯3.


## 3. Normalization Process by Homography

Letμhn be the homography normalization of quality measure μ, μshn the semihomographic normalized of μ, μshnd at right semihomographic normalized of μ, and μshng at left semihomographic normalized of μ.As announced in [2], the main objective of normalization of quality measure μ is to bring its values in [-1; 1] under the three conditions that μn takes the value - 1 at incompatibility, 0 at independence, and 1 at logical implication in order to compare two normalizable measures. Remember always that if these three values are finite and pairwise different, so the research carried out by [14] has already taken the approach to solve this kind of problem (problem of normalization of probabilistic quality measure), i.e., the use of the expression of the normalized μn of μ:(1)μnX→Y=xfx+yf,ifXfavorsY;xdx+yd,ifXdisfavorsY.where these four coefficients, called normalization coefficient, are determined by passing unilateral limits in reference situations (incompatibility, independence, and logical implication) due to the continuity of evolution in both zones: attraction (positive dependence) and repulsion ( negative dependence ) [2, 6, 17].If one or two of the three valuesximp, xind, and xinc are infinite and in case we have two infinite values, it is necessary that xind is excluded, which leads us to use one of the three following expressions to find the four real coefficients, xf, yf, xd, and yd: (2)μshndX→Y=xfx+m+yf,ifXfavorsY;xdx+yd,ifXdisfavorsY.μshngX→Y=xfx+yf,ifXfavorsY;xdx+m+yd,ifXdisfavorsY.μhnX→Y=xfx+m+yf,ifXfavorsY;xdx+m+yd,ifXdisfavorsY.These four coefficients are still determined by passing unilateral limits in situations of reference (incompatibility, independence, and logic implication) by taking into account the continuity evolution in both zones: attraction (positive dependence) and repulsion (negative dependence). In case where X favors Y, ximp can be infinite, xind≠xinc, (xind,xinc)∈R2 and xind∈R∗; then we obtain the following system of equations:(3)xfximp+yf=1,logicalimplicationxfxind+yf=0,independenceatrightAs (xind,xinc)∈R2 and xind∈R∗, so you only use the theories in [2] for the left normalization. We can write the system of four nonlinear equations, with the following four unknowns:(4)xfximp+yf=1xfxind+yf=0xdxind+yd=0xdxind+yd=-1We are just here to take m=0 and we have four equations with four unknowns, with this particularity that the coefficient ximp can be infinite. Hence we have the following proposition.Proposition 3.
(i) If (ximp,xind)∈(R∗)2 with ximp, xind, and xinc pairwise distinct, then the system of equations (4) admits four real solutions; (ii) if ximp = ∞ and xind∈R∗, then the system of equations (4) has four real solutions such that yf = 1, xf = -xind, xd=1/(xind-xinc), and yd = -xdxind; (iii) otherwise, the system of equations has no solution.Proof.
( i ) The system of equations (4) is equivalent to the system of equations (5):(5)ximpyf+xf=ximpxindyf+xf=0xdxind+yd=0xdxinc+yd=-1It became a system of linear equations. The matrix writing system of equations (5) is given by the vector equation (6):(6)ximp100xind10000xind100xinc1yfxfxdyd=ximp00-1Let us call M1 = ximp100xind10000xind100xind1. So we must have detM1 = (ximp-xind)(xind-xinc)≠0; so (i); for (ii), just take limximp→∞(xf/ximp)=0; for (iii), if xind=∞, the last two equations do not make sense.The following system of equations presents the common features of equation (5) with the only difference that xinc can be infinite, ximp≠xind and xind∈R∗. This gives the system of equations (7).(7)xfximp+yf=1xfxind+yf=0xdxind+yd=0xdxinc+yd=-1Hence we obtain the following proposition.Proposition 4.
(i) If (xind,xinc)∈(R∗)2, with ximp, xind, and xinc pairwise distinct, then the system of equations (7) admits four real solutions; (ii) if xinc = ∞ and xind∈R∗, then the system of equations (7) has four real solutions such that yd = -1, xd=xind and xf=1/(ximp-xind), yf=-xfxind; (iii) otherwise, the system of equations has no solution.Proof.
( i ) The system of equations (7) is equivalent to the system of equations (8):(8)xfximp+yf=1xfxind+yf=0ydxind+xd=0ydxinc+xd=-xincIt became a system of linear equations. The matrix writing the system of equations (8) is given by the vector equation (9):(9)ximp100xind10000xind100xinc1xfyfydxd=100-xincLet us call M2 = ximp100xind10000xind100xinc1. So we must have detM2 = (ximp-xind)(xind-xinc)≠0; so (i); for (ii), just take lim limxinc→∞(xd/xinc)=0; for (iii), if xind=∞, then the last two equations do not make sense.The following system is similar to the previous equation (7), this time with xind∈R and m∈R∗, including case where xind=0; then in this case, m must be nonzero. Take, for example, m = 1.(10)xfximp+yf=1xfxind+yf=0xdxind+1+yd=0xdxinc+1+yd=-1Then we obtain the following proposition.Proposition 5.
(i) If (xind,xinc)∈R2, with ximp≠0, ximp, xind, and xinc pairwise distinct, then the system of equations (10) has four real solutions;(ii) if xinc=∞, xind∈R, and ximp∈R∗, then the system of equations (10) has four real solutions such that yd=-1, xd=xind+1 and xf=1/(ximp-xind), yf=-xfxind;(iii) then, the system of equations has no solution.Proof.
( i ) The system of equations (10) is equivalent to the system of equations (11):(11)xfximp+yf=1xfxind+yf=0ydxind+1+xd=0ydxinc+1+xd=-xinc-1It is reduced to a system of linear equations. The matrix writing of the system of equations (11) is given by the vector equation (12):(12)ximp100xind10000xind+1100xinc+11xfyfydxd=100-xinc-1.Let us call M3 = ximp+1100xind+110000xind+1100xinc+11. Thus we must have detM3 = (ximp-xind)(xind-xinc)≠0; so (i); for (ii), just take limxinc→∞(xd/xinc+1)=0; for (iii), if xind=∞, then the last two equations do not make sense.The current form of the studied system was the appearance of the system of equations (13):(13)xfximp+m+yf=1xfxind+m+yf=0xdxind+m+yd=0xdxinc+m+yd=-1In (13) ximp and xinc can be infinite, xind is real, and (xind+m)∈R∗.Proposition 6.
(i) If (ximp,xind,xinc)∈R3, with ximp, xind, and xinc pairwise distinct, then the system of equations (13) has four real solutions; (ii) if xinc=∞, xind∈R and if ximp=∞, then the system of equations (13) has four solutions actual such that yd=-1, xd=(xind+m) and xf=1, yf=-(xind+m); (iii) alternatively, the system of equations has no solution.Proof.
(i) The system of equations (13) is equivalent to the system of equations (14):(14)yfximp+m+xf=ximp+myfxind+m+xf=0ydxind+m+xd=0ydxinc+m+xd=-xinc+mIt therefore comes to a system of linear equations. The matrix writing system of equations (14) is given by the vector equation (15): (15)ximp+m100xind+m10000xind+m100xinc+m1yfxfydxd=ximp+m00-xinc+mLet us call M4 = ximp+m100xind+m10000xind+m100xinc+m1. Thus, we must always have detM4=(ximp-xind)(xind-xinc)≠0; for (ii), just take limxinc→∞(xd/xinc)=0 and limximp→∞(xf/ximp)=0; for (iii), if xind=∞, then all the equations do not make sense.Note 7.
Note that the different matrices for the four above-mentioned propositions asM1, M2, M3, M4 have the same determinant; this means that all the measures have the following conditions ximp≠xind≠xinc and (ximp,xind,xinc)∈R3 have the same condition of normalizability.


## 4. Application of These Four Propositions

We recall in Table1 the respective definitions of the various measures that lead to the results below.Table 1
The probabilistic quality measures.
No Measuresμ μ ( X → Y ) 1 Cost multiplying P ( X ′ ∩ Y ′ ) P ( Y ¯ ′ ) P ( X ′ ∩ Y ¯ ′ ) P ( Y ′ ) 2 Example counter-example P(X′∩Y′)-P(X′∩Y¯′)P(X′∩Y′) 3 Informal Gain logP(X′∩Y′)P(X′)P(Y′) 4 Odd-Ratio P ( X ′ ∩ Y ′ ) P ( X ¯ ′ ∩ Y ¯ ′ ) P ( X ¯ ′ ∩ Y ′ ) P ( X ′ ∩ Y ¯ ′ ) 5 Conviction P(X′)P(Y¯′)P(X′∩Y¯′) 6 Sebag P ( X ′ ∩ Y ′ ) P ( X ′ ) P ( Y ¯ ′ )( 1 ) The normalized measure of “Cost Multiplying” is (16)Cost-MultshndX→Y=PY′/X′-PY′PY′/X′1-PY′ifXfavorsY;PY′/X′-PY′PY′1-PY′/X′ifXdisfavorsY.SoitCost-MultshndX→Y=MGKX→YPY′/X′ifXfavorrsY;MGKX→Y1-PY′/X′,ifXdisfavorsY.( 2 ) The normalized measure of “Sebag” is (17)SebagshndX→Y=PY′/X′-PY′PY′/X′1-PY′ifXfavorsY;PY′/X′-PY′PY′1-PY′/X′ifXdisfavorsY.SoitSebagshndX→Y=MGKX→YPY′/X′ifXfavorsY;MGKX→Y1-PY′/X′,ifXdisfavorsY.( 3 ) The normalized measure of “Example counter-example” is (18)Ex-ContshndX→Y=PY′/X′-PY′PY′/X′1-PY′ifXfavorsY;PY′/X′-PY′PY′1-2PY′/X′ifXdisfavorsY.SoitEx-ContshngX→Y=MGKX→YPY′/X′ifXfavorsY;MGKX→Y1-PY′/X′,ifXdisfavorsY.( 4 ) The normalized measure of “Odd-Ratio” is (19)OddRshndX→Y=PY′/X′-PY′PY′/X′1-PX′-PY′+PY′/X′PX′ifXfavorsY;PY′/X′-PY′1-PY′/X′PY′-PY′/X′PX′ifXdisfavorsY.Odd-RatioshndX→Y=1-PX′MGKX→YPY′/X′1-PX′-PY′+PY′/X′PX′,ifXfavorsY;PY′MGKX→Y1-PY′/X′PY′-PY′/X′PX′,ifXdisfavorsY.( 5 ) The normalized measure of “Conviction” is (20)ConvhnX→Y=PY′/X′-PY′1-PX′,ifXfavorsY;PY′/X′-PY′PY′,ifXdisfavorsY.SoitConvhnX→Y=MGKX→Y.( 6 ) The normalized measure of “Informal Gain” is(21)Gain-Infshng=log⁡PY′-log⁡PY′/X′log⁡PY′,ifXfavorsY;-log⁡PY′/X′-log⁡PY′log⁡PY′/X′-log⁡PY′+1,ifXdisfavorsY.Note that the normalized of Gain-Informal measure has no relationship with MGK, but it is continuing.  Table 1 calls the respective definitions of the various measures.The following theorem supplements in its part (i) the statement in [17] (paragraph 3.2, page 62).Theorem 8.
A probabilistic quality measureμ is normalizing if and only if, for any association rule X→Y, the following conditions are met:(i) the following inequalities are satisfied ximp≠xind≠xinc, if (ximp,xind,xinc)∈R3;(ii) if (ximp,xind,xinc)∈R¯3, then it is necessary that any of the three values (ximp,xind,xinc) must be infinite; or in the case where two values are infinite, xind must always be finite, and x2+m∈R∗.Proof.
(i) ximp≠xind≠xinc and if (ximp,xind,xinc)∈R3, then the determinant of the matrix Mi (i = 1, 2, 3, 4) associated with all the equations (6), (9), (12), and (15) is equal to (ximp-xind)(xind-xinc) and is, thus, nonzero; for (ii), if (ximp,xind,xinc)∈R¯3, and one or two of them are infinite, then it is necessary to use Propositions 3, 4, 5, and 6 (ii) above. Hence the theorem is stated.


## 5. Conclusion and Perspectives

This study makes a significant number of quality measures that remain nonaffine normalizable (e.g.,Sebag, Odd-Ratio, Example counter-example, Informal Gain, Cost Multiplying, and Conviction), through the use of homographic functions. However, we have shown that each measure has its own position in relation to the three intuitive references such as incompatibility, independency, and logical implication. In this case, we have shown that we can use a homographic homeomorphism or even combine a homographic homeomorphism with an affine homeomorphism, when the infinity appears as reference coefficient. Only, we must be able to play with the homographic homeomorphism in accordance with its property and according to the need. It is explained in our work only that any situation is infinite; moreover, it is not yet risen to the position of stochastic independence: only homographic functions of the type x↦b/(x+m), where m=0 and b∈R∗, are sufficient to solve the problem of normalization. A small exception will be noticed on the measurementInformal Gain, because it is infinite at incompatibility and equal to zero at the stochastic independence. Therefore, it appears necessary to introduce the two functions xinc↦b/(xinc+m) and xind↦b/(xind+m) and m≠0, for example, m = 1. Finally, this study is based on normalization by homography complementarily to those by affine application; this remains around the quality measure MGK with its two components MGKf and MGKd multiplying by closely factors. This reinforces the unifying property of MGK relative to all measures existing in literature. Although we have these homographic homeomorphisms and affine homeomorphisms to normalize interestingness measures, the route to be taken is even longer. Indeed, there is a group of measures that resist to the use of these new tools, namely,Klosgen, Pondered dependency, One way support, Bilateral Support, Coverage, and Prevalence, because they do not meet the conditions for normalization. So, the problem remains still open with respect to the transformation that allows normalization of those quality measures in a sense still to be specified.



---

*Source: 7829805-2019-01-29.xml*