From c9f45698e9a535650b20a516d197dca86ed70d90 Mon Sep 17 00:00:00 2001 From: couturie Date: Tue, 16 Apr 2019 16:48:49 +0200 Subject: [PATCH] new --- chapter2.tex | 218 ++++++++++++++++++++++++++++++++++++++++++++++--- references.tex | 24 ++++++ 2 files changed, 230 insertions(+), 12 deletions(-) diff --git a/chapter2.tex b/chapter2.tex index d5f45e3..ed3ec5b 100644 --- a/chapter2.tex +++ b/chapter2.tex @@ -29,7 +29,7 @@ gradually being supplemented by the processing of modal, frequency and, recently, interval and fuzzy variables. } -\section{Preamble} +\section*{Preamble} Human operative knowledge is mainly composed of two components: that of facts and that of rules between facts or between rules themselves. @@ -298,7 +298,11 @@ It estimates a gap between the contingency $(card(A\cap \overline{B}))$ and the value it would have taken if there had been independence between $a$ and $b$. -\definition $$q(a,\overline{b}) = \frac{n_{a \wedge \overline{b}}- \frac{n_a.n_{\overline{b}}}{n}}{\sqrt{\frac{n_a.n_{\overline{b}}}{n}}}$$ +\definition +\begin{equation} q(a,\overline{b}) = \frac{n_{a \wedge \overline{b}}- + \frac{n_a.n_{\overline{b}}}{n}}{\sqrt{\frac{n_a.n_{\overline{b}}}{n}}} + \label{eq2.1} +\end{equation} is called the implication index, the number used as an indicator of the non-implication of $a$ to $b$. In cases where the approximation is properly legitimized (for example @@ -504,7 +508,7 @@ close to the Lagrange index, but better adapted to the rank variable situation. -\section{Cases of on-interval and on-interval variables} +\section{Cases of variables-on-intervals and interval-variables} \subsection{Variables-on-intervals} \subsubsection{Founding situation} @@ -589,8 +593,8 @@ admits the partition corresponding to the first maximum and that the optimal reciprocal involvement is satisfied for the partition of $[b1,~ b2]$ corresponding to the second maximum. -\section{Interval-variables} -\subsection{Founding situation} +\subsection{Interval-variables} +\subsubsection{Founding situation} Data are available from a population of $n$ individuals (who may be each or some of the sets of individuals, e.g. a class of students) according to variables (e.g. grades over a year in French, math, @@ -621,7 +625,7 @@ Similarly, we will say that $[14.25, 17.80]$ in physics most often implies $[16.40, 18]$ in mathematics. -\subsection{Algorithm} +\subsubsection{Algorithm} By following the problem of E. Diday and his collaborators, if the values taken according to the subjects by the variables $a$ and $b$ @@ -685,9 +689,15 @@ topology\footnote{Fréchet's topology allows $\mathbb{N}$ sections, as they are with the usual topology.}, is expressed as follows by the scalar product: -$$dq = \frac{\partial q}{\partial n}dn + \frac{\partial q}{\partial +\begin{equation} +dq = \frac{\partial q}{\partial n}dn + \frac{\partial q}{\partial n_a}dn_a + \frac{\partial q}{\partial n_b}dn_b + \frac{\partial - q}{\partial n_{a \wedge \overline{b}}}dn_{a \wedge \overline{b}} = grad~q.dM\footnote{By a mechanistic metaphor, we will say that $dq$ is the elementary work of $q$ for a movement $dM$ (see chapter 14 of this book).}$$ + q}{\partial n_{a \wedge \overline{b}}}dn_{a \wedge \overline{b}} = +grad~q.dM\footnote{By a mechanistic metaphor, we will say that $dq$ is + the elementary work of $q$ for a movement $dM$ (see chapter 14 of + this book).} +\label{eq2.2} +\end{equation} where $M$ is the coordinate point $(n,~ n_a,~ n_b,~ n_{a \wedge \overline{b}})$ of the vector scalar field $C$, $dM$ is the @@ -724,16 +734,24 @@ where $o(\Delta q)$ is an infinitely small first order. Let us examine the partial derivatives of $n_b$ and $n_{a \wedge \overline{b}}$ the number of counter-examples. We get: -$$ \frac{\partial +\begin{equation} + \frac{\partial q}{\partial n_b} = \frac{1}{2} n_{a \wedge \overline{b}} (\frac{n_a}{n})^{-\frac{1}{2}} (n-n_b)^{-\frac{3}{2}} -+ \frac{1}{2} (\frac{n_a}{n})^{\frac{1}{2}} (n-n_b)^{-\frac{1}{2}} > 0 $$ + + \frac{1}{2} (\frac{n_a}{n})^{\frac{1}{2}} (n-n_b)^{-\frac{1}{2}} > + 0 + \label{eq2.3} +\end{equation} -$$ \frac{\partial +\begin{equation} + \frac{\partial q}{\partial n_{a \wedge \overline{b}}} = \frac{1}{\sqrt{\frac{n_a n_{\overline{b}}}{n}}} -= \frac{1}{\sqrt{\frac{n_a (n-n_b)}{n}}} > 0 $$ + = \frac{1}{\sqrt{\frac{n_a (n-n_b)}{n}}} > 0 + \label{eq2.4} +\end{equation} + Thus, if the increases $\Delta nb$ and $\Delta n_{a \wedge \overline{b}}$ are positive, the increase of $q(a,\overline{b})$ is @@ -745,3 +763,179 @@ observed values $n_b$ and $ n_{a \wedge \overline{b}}$ and minimum at values $n_b+\Delta n_b$ and $n_{a \wedge \overline{b}}+ n_{a \wedge \overline{b}}$. + +If we examine the case where $n_a$ varies, we obtain the partial +derivative of $q$ with respect to $n_a$ which is: + +\begin{equation} + C = \frac{ n_{a \wedge \overline{b}}}{2 + \sqrt{\frac{n_{\overline{b}}}{n}}} + \left(\frac{n}{n_a}\right)^{\frac{3}{2}} + -\frac{1}{2}\sqrt{\frac{n_{\overline{b}}}{n_a}}<0 + \label{eq2.5} + \end{equation} + +Thus, for variations of $n_a$ on $[0,~ nb]$, the implication index function is always decreasing (and concave) with respect to $n_a$ and is therefore minimum for $n_a= n_b$. As a result, the intensity of implication is increasing and maximum for $n_a= n_b$. + +Note the partial derivative of $q$ with respect to $n$: + +$$\frac{\partial q}{\partial n} = \frac{1}{2\sqrt{n}} \left( n_{a + \wedge \overline{b}}+\frac{n_a n_{\overline{b}}}{n} \right)$$ + +Consequently, if the other 3 parameters are constant, the implication +index decreases by $\sqrt{n}$. +The quality of implication is therefore all the better, a specific +property of the SIA compared to other indicators used in the +literature~\cite{Grasab}. +This property is in accordance with statistical and semantic +expectations regarding the credit given to the frequency of +observations. +Since the partial derivatives of $q$ (at least one of them) are +non-linear according to the variable parameters involved, we are +dealing with a non-linear dynamic system\footnote{"Non-linear systems + are systems that are known to be deterministic but for which, in + general, nothing can be predicted because calculations cannot be + made"~\cite{Ekeland} p. 265.} with all the epistemological +consequences that we will consider elsewhere. + + + +\subsection{Numerical example} +In a first experiment, we observe the occurrences: $n = 100$, $n_a = +20$, $n_b = 40$ (hence $n_b=60$, $ n_{a \wedge \overline{b}} = 4$). +The application of formula (\ref{eq2.1}) gives = -2.309. +In a 2nd experiment, $n$ and $n_a$ are unchanged but the occurrences +of $b$ and counter-examples $n_{a \wedge \overline{b}}$ increase by one unit. + +At the initial point of the space of the 4 variables, the partial +derivatives that only interest us (according to $n_b$ and $n_{a + \wedge \overline{b}}$) have respectively the following values when +applying formulas (\ref{eq2.3}) and (\ref{eq2.4}): $\frac{\partial + q}{\partial n_b} = 0.0385$ and $\frac{\partial q}{\partial n_{a + \wedge \overline{b}}} = 0.2887$. + +As $\Delta n_b$, $\Delta n_{\overline{b}}$ and $\Delta n_{a + \wedge \overline{b}} $ are equal to 1, -1 and 1, then $\Delta q$ is +equal to: $0.0385 + 0.2887 + o(\Delta q) = 0.3272 + o(\Delta q)$ and +the approximate value of $q$ in the second experiment is $-2.309 + +0.2887 + o(\Delta q)= -1.982 +o(\Delta q)$ using the first order +development of $q$ (formula (\ref{eq2.2})). +However, the calculation of the new implication index $q$ at the point +of the 2nd experiment is, by the use of (\ref{eq2.1}): $-1.9795$, a +value well approximated by the development of $q$. + + + +\subsection{A first differential relationship of $\varphi$ as a function of function $q$} +Let us consider the intensity of implication $\varphi$ as a function +of $q(a,\overline{b})$: +$$\varphi(q)=\frac{1}{\sqrt{2\pi}}\int_q^{\infty}e^{-\frac{t^2}{2}}$$ +We can then examine how $\varphi(q)$ varies when $q$ varies in the neighberhood of a given value $(a,b)$, knowing how $q$ itself varies according to the 4 parameters that determine it. By derivation of the integration bound, we obtain: +\begin{equation} + \frac{d\varphi}{dq}=-\frac{1}{\sqrt{2\pi}}e^{-\frac{q^2}{2}} < 0 + \label{eq2.6} +\end{equation} +This confirms that the intensity increases when $q$ decreases, but the growth rate is specified by the formula, which allows us to study more precisely the variations of $\varphi$. Since the derivative of $\varphi$ from $q$ is always negative, the function $\varphi$ is decreasing. + +{\bf Numerical example}\\ +Taking the values of the occurrences observed in the 2 experiments +mentioned above, we find for $q = -2.309$, the value of the intensity +of implication $\varphi(q)$ is equal to 0.992. Applying formula +(\ref{eq2.6}), the derivative of $\varphi$ with respect to $q$ is: +-0.02775 and the negative increase in intensity is then: -0.02775, +$\Delta q$ = 0.3272. The approximate first-order intensity is +therefore: $0.992-\Delta q$ or 0.983. However, the actual calculation +of this intensity is, for $q= -1.9795$, $\varphi(q) = 0.976$. + + + +\subsection{Examination of other indices} +Unlike the core index $q$ and the intensity of implication, which +measures quality through probability (see definition 2.3), the other +most common indices are intended to be direct measures of quality. +We will examine their respective sensitivities to changes in the +parameters used to define these indices. +We keep the ratings adopted in paragraph 2.2 and select indices that +are recalled in~\cite{Grasm},~\cite{Lencaa} and~\cite{Grast2}. + +\subsubsection{The Loevinger Index} + +It is an "ancestor" of the indices of +implication~\cite{Loevinger}. This index, rated $H(a,b)$, varies from +1 to $-\infty$. It is defined by: $H(a,b) =1-\frac{n n_{a \wedge + b}}{n_a n_b}$. Its partial derivative with respect to the variable number of counter-examples is therefore: +$$\frac{\partial H}{\partial n_{a \wedge \overline{b}}}=-\frac{n}{n_a n_b}$$ +Thus the implication index is always decreasing with $n_{a \wedge + \overline{b}}$. If it is "close" to 1, implication is "almost" +satisfied. But this index has the disadvantage, not referring to a +probability scale, of not providing a probability threshold and being +invariant in any dilation of $E$, $A$, $B$ and $A \cap \overline{B}$. + + +\subsubsection{The Lift Index} + +It is expressed by: $l =\frac{n n_{a \wedge b}}{n_a n_b}$. +This expression, linear with respect to the examples, can still be +written to highlight the number of counter-examples: +$$l =\frac{n (n_a - n_{a \wedge \overline{b}})}{n_a n_b}$$ +To study the sensitivity of the $l$ to parameter variations, we use: +$$\frac{\partial l}{\partial n_{a \wedge \overline{b}} } = +-\frac{1}{n_a n_b}$$ +Thus, the variation of the Lift index is independent of the variation +of the number of counter-examples. +It is a constant that depends only on variations in the occurrences of $a$ and $b$. Therefore, $l$ decreases when the number of counter-examples increases, which semantically is acceptable, but the rate of decrease does not depend on the rate of growth of $n_{a \wedge \overline{b}}$. + +\subsubsection{Confidence} + +This index is the best known and most widely used thanks to the sound +box available in an Anglo-Saxon publication~\cite{Agrawal}. +It is at the origin of several other commonly used indices which are only variants satisfying this or that semantic requirement... Moreover, it is simple and can be interpreted easily and immediately. +$$c=\frac{n_{a \wedge b}}{n_a} = 1-\frac{n_{a \wedge \overline{b}}}{n_a}$$ + +The first form, linear with respect to the examples, independent of +$n_b$, is interpreted as a conditional frequency of the examples of +$b$ when $a$ is known. +The sensitivity of this index to variations in the occurrence of +counter-examples is read through the partial derivative: +$$\frac{\partial c}{\partial n_{a \wedge \overline{b}} } = +-\frac{1}{n_a }$$ + + +Consequently, confidence increases when $n_{a \wedge \overline{b}}$ +decreases, which is semantically acceptable, but the rate of variation +is constant, independent of the rate of decrease of this number, of +the variations of $n$ and $n_b$. +This property seems not to satisfy intuition. +The gradient of $c$ is expressed only in relation to $n_{a \wedge + \overline{b}}$ and $n_a$:(). {\bf CHECK FORMULA} +This may also appear to be a restriction on the role of parameters in +expressing the sensitivity of the index. + +\section{Gradient field, implicative field} +We highlight here the existence of fields generated by the variables +of the corpus. + +\subsection{Existence of a gradient field} +Like our Newtonian physical space, where a gravitational field emitted +by each material object acts, we can consider that it is the same +around each variable. +For example, the variable $a$ generates a scalar field whose value in +$b$ is maximum and equal to the intensity of implication or the +implicition index $q(a,\overline{b})$. +Its action spreads in V according to differential laws as J.M. Leblond +says, in~\cite{Leblond} p.242. + +Let us consider the space $E$ of dimension 4 where the coordinates of +the points $M$ are the parameters relative to the binary variables $a$ +and $b$, i.e. ($n$, $n_a$, $n_b$, $n_{a\wedge \overline{b}}$). $q(a,\overline{b})$ is the realization of a scalar field, as an application of $\mathbb{R}^4$ in $\mathbb{R}$ (immersion of $\mathbb{N}^4$ in $\mathbb{R}^4$). +For the grad vector $q$ of components the partial derivatives of $q$ +with respect to variables $n$, $n_a$, $n_b$, $n_{a\wedge + \overline{b}}$ to define a gradient field - a particular vector +field that we will also call implicit field - it must respect the +Schwartz criterion of an exact total differential, i.e.: + +$$\frac{\partial}{\partial n_{a\wedge \overline{b}}}\left( +\frac{\partial q}{\partial n_b} \right) =\frac{\partial}{\partial n_b}\left( +\frac{\partial q}{\partial n_{a\wedge \overline{b}}} \right) $$ +and the same for the other variables taken in pairs. However, we have, +through the formulas (\ref{eq2.3}) and (\ref{eq2.4}) diff --git a/references.tex b/references.tex index 7989cb0..62d3b12 100644 --- a/references.tex +++ b/references.tex @@ -90,6 +90,9 @@ \bibitem{Ehrenberg} Ehrenberg A. (2008) Sciences Humaines, n° 198, nov. 2008. + + +\bibitem{Ekeland} Ekeland I. (2002) La complexité, vertiges et promesses, Le Pommier. \bibitem{Espagnat} d’Espagnat B. (1981) A la recherche du réel, Le @@ -158,6 +161,11 @@ données, Mathématiques et Sciences Humaines, n° 154-155, p 9-29, ISSN \bibitem{Grast} Gras R., Régnier J.C. (2009) Qualité d’un graphe implicatif: variance implicative, Analyse Statistique Implicative, Une méthode d'analyse de données pour la recherche de causalités, sous la direction de Régis Gras, réd, invités Régis Gras, Jean-Claude Régnier, Fabrice Guillet, Cépaduès Ed. Toulouse, ISBN : 978.2.85428.8971, p.151-163. +\bibitem{Grast2} Gras R., Couturier R. (2010) Spécificités de + l'Analyse Statistique Implicative (A.S.I.) par rapport à d'autres + mesures de qualité de règles d'association, Conference: 5ème colloque international ASI (ASI 5). + + \bibitem{Grasu} Gras R., Couturier R. (2012) Implication entropique et causalité, L’Analyse Statistique Implicative : de l’exploratoire au confirmatoire, Eds J.C.Régnier, M.Bailleul, R.Gras, Université de Caen, ISBN 978-2-7466-5256-9, p.39-50. \bibitem{Grasv} Gras R., Lahanier-Reuter D. (2012) Dualité entre espace des variables et espace des sujets, L’Analyse Statistique Implicative: de l’exploratoire au confirmatoire, Eds J.C.Régnier, M.Bailleul R.Gras, Université de Caen, ISBN 978-2-7466-5256-9, p. 19-38. @@ -204,6 +212,22 @@ Cépaduès Ed. Toulouse, p. 195-208, ISBN: 978.2.36493.577.8. \bibitem{Lebart} Lebart L., Morineau A. and Piron M., Statistique exploratoire multidimensionnelle, Dunod. +\bibitem{Leblond} Leblond J.M. (1996) Aux contraires, nrf essais, Paris, Gallimard. + + +\bibitem{Lencaa} Lenca P., Meyer P., Vaillant P., Picouet P. and + Lallich S., (2004), Evaluation et analyse multi-critères de qualité + des règles d’association, Mesures de qualité pour la fouille de + données, RNTI-E-1,Cépaduès, p. 219-246. + +\bibitem{Lencab} Lenca P., Vaillant B., Meyer P., and Lallich + S. (2007), Association Rule Interestingness Measures: Experimental + and Theorical Studies, Guillet F. and Hamilton H.J. eds, Studies in + Computational Intelligence 43, Springer, p. 51-76. + +\bibitem{Lent} Lent B., A.N. Swami A.N., et J. Widow J. (1997), Clustering association rules. Proc. of the 13th Int. Conf. on Data Engineering, p. 220-231. + + \bibitem{Lerman} Lerman, I. C. (1970) Sur l'analyse des données préalable à une classification automatique (proposition d'une nouvelle mesure de similarité). Mathématiques et sciences humaines, 32, 5-15. \bibitem{Lermana} Lerman I.-C., Gras R. and Rostam H. (1981) Elaboration et évaluation d'un indice d'implication pour des données binaires, I et II, Mathématiques et Sciences Humaines, n°74,, 5-35 and n° 75, 5-47 -- 2.39.5