Brevet FR3066289A1 — publié le 20181116

PROCEDE, MIS EN OEUVRE PAR ORDINATEUR, DE RECHERCHE DE REGLES D'ASSOCIATION DANS UNE BASE DE DONNEES DOMAINE TECHNIQUE DE L'INVENTION La présente invention se rapporte au domaine général du traitement de structures de données dans des bases de données, et en particulier aux procédés, mis en oeuvre par ordinateur, de recherche de règles d'associations dans des bases de données volumineuses. La présente invention concerne plus particulièrement un procédé, mis en oeuvre par une unité de traitement d'un ordinateur et/ou par un circuit logique programmable ou reprogrammable, de recherche de règles d'association dans une base de données. La présente invention concerne également un produit programme d'ordinateur comportant des instructions pour l'exécution d'un tel procédé de recherche, ainsi qu'un support d'enregistrement sur lequel est enregistré un programme d'ordinateur comprenant des instructions de code de programme pour mettre en oeuvre tout ou partie des étapes de ce procédé. De nombreuses applications industrielles de la présente invention ont été identifiées, incluant, sans que cette liste ne soit exhaustive, des dispositifs d'analyse de pannes dans des systèmes industriels, des dispositifs de détection de vigilance du conducteur dans un véhicule, ou encore des dispositifs de recherche de relations de cause à effet dans des données médicales ou pharmaceutiques. 3066289 2 ETAT DE LA TECHNIQUE ANTERIEURE Généralement, les techniques d'exploration de données dans une base de données peuvent être séparées en deux grandes catégories qui caractérisent deux niveaux 5 d'exploration : l'exploitation de données transactionnelles et les requêtes ; l'exploration de données pour l'informatique décisionnelle. 10 La technique d'exploitation de données transactionnelles et de requêtes porte sur des données dont l'objet initial est l'archivage, et permet d'extraire de l'information que l'on sait détenir. La technique d'exploration de données pour l'informatique décisionnelle, quant à elle, permet 15 d'une part de produire de l'information nouvelle à partir des données, et d'autre part de bénéficier d'améliorations stratégiques visant à un avantage concurrentiel ou à une meilleure gestion des risques et des coûts, à travers la production de réponses à des questions non triviales et non 20 accessibles via les requêtes traditionnelles. Dans le cas des techniques d'exploration de données pour l'informatique décisionnelle, le but est de modéliser un comportement sur les données pour en extraire de l'information qu'on n'est pas sûr a priori de pouvoir 25 comprendre, et dont la structure va dépendre du type de problème auquel on est confronté. La matière première est l'exploration de données traitées et propres, organisées en base sous forme de tableaux dont les colonnes représentent des variables et les lignes des instances (par exemple des individus, ou encore des instants pour des séries 3066289 3 temporelles). En fonction de l'objectif poursuivi (description ou prédiction), du type de données (numériques ou textuelles, quantitatives ou qualitatives, discrètes ou continues) et du problème posé, il s'agit de modéliser et 5 estimer les relations entre les données (régressions linéaire, logistique ou autre), de classer les individus (via des arbres de décisions, des réseaux de neurones ou autre), de créer des scores de risque et d'appétence pour des clients et prospects, de produire des prévisions de 10 variables économiques et financières, et bien d'autres applications touchant une grande variété de domaines. Deux grandes familles d'approches se présentent alors pour faire de l'exploration de données : - la modélisation : dans certaines activités et pour 15 certaines situations données, des modèles sont capables de décrire le fonctionnement d'un système complexe. Ces modèles introduisent des variables et des paramètres associés, ainsi que leurs relations. Les données sont alors utilisées pour estimer les paramètres et valider 20 la pertinence des variables, puis pour confirmer ou infirmer la théorie. - Les techniques de classification ou de recherche de règles d'association :beaucoup des nouvelles activités industrielles ou de services de ces dernières années 25 ont fait naître de nouvelles données qui échappent à la modélisation. Un problème qui se pose alors est celui de l'utilisation de la masse considérable des données recueillies pour améliorer l'efficacité des entreprises auprès de leurs clients lorsqu'elles touchent à des 30 activités pour lesquelles les relations entre les variables ne sont pas bien connues. 3066289 4 Dans ces dernières situations, qui échappent à la modélisation (par exemple du fait d'un manque de théorie préétablie, de difficultés à déterminer des variables pertinentes au regard de la profusion des données, ou encore 5 de l'explosion combinatoire liée à la nécessité d'utiliser un maximum de variables pour comprendre des systèmes complexes), il est commun d'utiliser la puissance de calcul des ordinateurs pour produire des solutions, soit exactes, soit approchées, soit locales. 10 La plupart du temps, il n'existe pas d'algorithme permettant de résoudre le problème en un temps raisonnable. On parle de problème NP-difficile en mathématiques. Un cas classique est celui du voyageur de commerce : celui-ci doit minimiser la distance nécessaire à parcourir pour relier au 15 cours de son voyage d'affaires un certain nombre de villes dont on connait les distances deux à deux. Une première méthode visant à résoudre ce problème, simple conceptuellement, consiste à énumérer tous les itinéraires possibles traversant toutes les villes une et une seule fois, 20 à en calculer la longueur totale, et à choisir l'itinéraire le plus court. A ce jour, aucune solution mathématique ne permet de trouver l'optimum global de ce problème en temps polynomial, c'est-à-dire en un temps qui ne croisse pas exceptionnellement vite à mesure qu'on ajoute des instances 25 (ici, des villes). La combinatoire nous indique que la solution naïve de l'énumération devient très vite impraticable même pour des ordinateurs puissants en un temps raisonnable, au-delà de quelques dizaines de villes. Ainsi, on peut essayer de trouver des optimums locaux. 30 Dans les situations qui échappent à la modélisation, et qui sont représentées par une base de données, il est connu 3066289 5 d'autres techniques visant à identifier, dans cette base, des données pertinentes constituant autant de solutions à un problème NP-difficile donné. Il est ainsi connu des procédés, mis en oeuvre par 5 ordinateur, de recherche de règles d'associations dans une base de données. Parmi ces derniers, il est connu en particulier un procédé, mis en oeuvre par ordinateur, et connu sous l'acronyme PRIM (de l'anglais « Patient Rule Induction Method »). Dans ce procédé de recherche de règles 10 d'associations, une base de données est stockée dans des moyens de mémorisation de l'ordinateur et comporte un ensemble de données. L'ensemble de données est organisé sous la forme d'une liste d'instances, chaque instance étant définie par un ensemble de valeurs numériques réelles prises 15 par un nombre prédéterminé de variables. Le procédé comprend une étape de sélection d'un ensemble de Ni variables parmi les variables de la liste d'instances ; cet ensemble formant un ensemble de variables d'entrée et définissant un espace de dimension Ni ; et une étape de sélection d'une variable 20 parmi les variables restantes de la liste d'instances, cette variable formant une variable de sortie. Chaque instance est représentée par un point dans l'espace de dimension Ni. Le procédé comprend en outre une étape de définition d'au moins une modalité pour la variable de sortie sélectionnée, 25 autrement dit d'un critère à vérifier par la valeur de cette variable de sortie ; et une étape de définition d'une taille minimale de régions à explorer dans l'espace de dimension Ni. Le procédé comprend en outre une étape de génération, dans l'espace de dimension Ni, de régions contenant plusieurs 30 points vérifiant la modalité précédemment définie. Le procédé PRIM génère séquentiellement les régions en supprimant à chaque étape les observations déjà couvertes. 3066289 6 Le procédé comprend enfin une étape de détermination de régions d'intérêt parmi ces régions générées. Chaque région d'intérêt ainsi déterminée vérifie le critère de taille minimale précédemment défini, et contient un nombre de points 5 vérifiant la modalité précédemment définie tel que la densité de ces points dans la région est supérieure à une densité-seuil prédéterminée. Les valeurs limites des variables d'entrée qui délimitent chaque région d'intérêt ainsi déterminée définissent une règle d'association dans la base 10 de données. Toutefois, un inconvénient de ce procédé PRIM est qu'il implique des calculs complexes et chronophages de la part de l'unité de traitement de l'ordinateur. En outre, la base de données n'est pas explorée de manière exhaustive, ce qui 15 nuit à la précision des résultats obtenus. Enfin, la mise en oeuvre de ce procédé PRIM nécessite de prévoir une gestion de variables redondantes, mais sans pouvoir effectuer celle-ci en amont. Cette gestion des variables redondantes, et notamment la suppression de ces dernières, est ainsi 20 effectuée ex post, ce qui est préjudiciable là encore à la précision des résultats obtenus. RESUME DE L'INVENTION Un but de la présente invention est de pallier au moins partiellement les inconvénients précités. 25 En particulier, un but de la présente invention est de proposer un procédé, mis en oeuvre par ordinateur, de recherche de règles d'association dans une base de données permettant de réduire la complexité et la durée des calculs dans l'ordinateur, tout en améliorant la précision des 30 résultats obtenus. 3066289 7 A cette fin, la présente invention propose un procédé, mis en oeuvre par une unité de traitement d'un ordinateur et/ou par un circuit logique programmable ou reprogrammable, de recherche de règles d'association dans une base de 5 données, la base de données étant stockée dans des moyens de mémorisation de l'unité de traitement ou dans le circuit logique programmable ou reprogrammable et comportant un ensemble de données, l'ensemble de données étant organisé sous la forme d'une liste d'instances, chaque instance étant 10 définie par un ensemble de valeurs numériques réelles prises par un nombre prédéterminé de variables ; le procédé comprenant les étapes suivantes: - la sélection d'un ensemble de Ni variables parmi lesdites variables de la liste d'instances, ledit ensemble de Ni 15 variables formant un ensemble de variables d'entrée et définissant un espace de dimension Ni ; et la sélection d'une variable parmi les variables restantes de la liste d'instances, ladite variable formant une variable de sortie ; 20 - l'ordonnancement, pour chaque variable d'entrée de la liste d'instances sélectionnée, des valeurs numériques des instances pour cette variable, de sorte à passer d'une topologie de valeurs réelles à une topologie de valeurs ordinales pour les variables d'entrée sélectionnées, chaque 25 instance étant alors définie par un ensemble de rangs associés à chacune des valeurs des variables d'entrée de cette instance, chaque instance étant représentée par un point dans ledit espace de dimension Ni ; - la définition d'au moins une modalité pour la variable de 30 sortie sélectionnée, ladite modalité étant définie comme un 3066289 8 critère à vérifier par la valeur de ladite variable de sortie ; - l'exploration, dans des sous-espaces de l'espace de dimension Ni, de régions convexes droites, chaque région 5 convexe droite explorée étant un hyperrectangle présentant, sur deux sommets diagonalement opposés selon une grande diagonale dudit hyperrectangle, deux points représentatifs de deux instances dont la valeur de la variable de sortie vérifie ladite modalité, chaque région convexe droite 10 explorée étant en outre l'hyperrectangle qui, dans le sous-espace dont la dimension correspond à la dimension dudit hyperrectangle, peut être défini de manière univoque uniquement par ces deux points ; - la sélection, parmi lesdites régions convexes droites 15 explorées, de régions d'intérêt, chaque région d'intérêt sélectionnée contenant un nombre de points vérifiant ladite modalité tel que la densité de ces points est supérieure à une densité-seuil prédéterminée, les valeurs limites des variables d'entrée qui délimitent une région d'intérêt 20 donnée définissant une règle d'association dans la base de données. Via un remodelage particulier de la structure des données de la base de données initiale, ainsi que de la structure des solutions retenues (remodelage représenté 25 notamment par les étapes d'ordonnancement et d'exploration), le procédé selon l'invention permet avantageusement de réduire substantiellement la complexité combinatoire des calculs, sans nuire à la précision des résultats obtenus. Les calculs à effectuer par l'unité de traitement passent 30 ainsi d'une complexité exponentielle (calculs tels qu'effectués dans les procédés d'induction de règles de l'art 3066289 9 antérieur), à une complexité polynomiale, comme cela est démontré à l'avant-dernière section du présent document. Le temps de traitement global devient donc polynomial lui aussi. Un gain substantiel d'espace mémoire et une réduction des 5 ressources matérielles utilisées pour les calculs sont ainsi obtenus. Ces différents avantages et effets techniques, qui seront illustrés à la fin du présent document, sont indifférents à la sémantique des données utilisées. Grâce à ce passage d'une complexité exponentielle à une 10 complexité polynomiale pour les calculs à effectuer par l'unité de traitement, le procédé selon l'invention peut être avantageusement appliqué pour des applications industrielles mettant en oeuvre un grand nombre d'instances et de variables. De telles applications industrielles 15 incluent par exemple, sans que cette liste ne soit exhaustive, des dispositifs d'analyse de pannes dans des systèmes industriels, des dispositifs de détection de vigilance du conducteur dans un véhicule, ou encore des dispositifs de recherches de relations de cause à effet dans 20 des données médicales ou pharmaceutiques. Le procédé de recherche de règles d'association selon l'invention permet en outre d'effectuer une exploration plus exhaustive de la base de données, permettant d'améliorer la précision des résultats obtenus. Une telle exploration plus 25 exhaustive permet en particulier de construire des règles d'association qui ne soient ni fondées sur la couverture globale, ni sur le partitionnement. Un aspect clé faisant du procédé selon l'invention une recherche plus exhaustive est l'approche non-séquentielle. En particulier, l'étape 30 d'exploration de régions convexes droites est effectuée de manière non-séquentielle. Cette approche non-séquentielle 3066289 10 est fortement différenciante en comparaison des procédés d'induction de règles de l'art antérieur, notamment en comparaison du procédé PRIM. L'exploration de régions convexes droites et la 5 sélection, parmi ces régions convexes droites explorées, de régions d'intérêt, sont effectuées indépendamment pour chaque sous-espace de l'espace de dimension Ni, et donc pour chaque combinaison de variables d'entrée correspondantes. Ainsi, le procédé de recherche de règles d'association selon 10 l'invention est décentralisé. Cette décentralisation conduit avantageusement à du calcul parallélisé, au contraire du procédé PRIM de l'art antérieur dans lequel les calculs sont difficilement parallélisables. Cette parallélisation des calculs est cruciale et avantageuse du point de vue de la 15 réduction du temps de traitement, du fait de la complexité combinatoire de ces calculs. Avantageusement, chaque région d'intérêt sélectionnée contient en outre un nombre de points représentatifs d'instances, appelé taille, tel que ce nombre est supérieur 20 à une taille-seuil minimale prédéterminée. Cette caractéristique permet d'améliorer encore la précision des résultats obtenus. Avantageusement, le procédé comprend en outre une étape de détermination, dans chaque sous-espace de l'espace de 25 dimension Ni, d'un majorant de la taille des régions convexes droites de ce sous-espace, et une étape de comparaison, pour chaque sous-espace de l'espace de dimension Ni , entre ce majorant et ladite taille-seuil minimale. Ces étapes permettent de déterminer le majorant de la 30 taille d'une région convexe droite sans avoir à parcourir 3066289 11 toutes les instances représentées par les points vérifiant la modalité contenus dans cette région, ainsi que de savoir si un sous-espace contient une forte densité de points vérifiant la modalité, sans avoir à explorer ce sous-espace. 5 Ces étapes permettent d'obtenir une réduction avantageuse de la complexité et du temps de calcul. Avantageusement, lors de l'étape d'exploration, dans des sous-espaces de l'espace de dimension Ni, de régions convexes droites, seuls les sous-espaces pour lesquels le 10 majorant déterminé est supérieur à la taille-seuil minimale sont explorés. Cette caractéristique permet notamment de ne pas explorer certains chemins de sous-espaces qui seraient inutiles à explorer. Ainsi, cette caractéristique permet de 15 réduire la complexité combinatoire liée au nombre de variables et au nombre d'espaces liés à ces variables, et d'ainsi permettre une réduction avantageuse de la complexité et du temps de calcul. Avantageusement, le procédé comprend en outre une étape 20 de raffinement des régions d'intérêt sélectionnées, l'étape de raffinement comprenant, pour chaque région d'intérêt sélectionnée, une première phase d'agrandissement, respectivement de réduction, de la taille de cette région par augmentation, selon chaque dimension du sous-espace 25 associé à ladite région d'intérêt, de la valeur du rang maximum et/ou par diminution, selon chaque dimension du sous-espace associé à ladite région d'intérêt, de la valeur du rang minimum entre les deux instances définissant ladite région d'intérêt, pour la variable associée à cette 30 dimension; respectivement par diminution, selon chaque dimension du sous-espace associé à ladite région d'intérêt, 3066289 12 de la valeur du rang maximum et/ou par augmentation, selon chaque dimension du sous-espace associé à ladite région d'intérêt, de la valeur du rang minimum entre les deux instances définissant ladite région d'intérêt, pour la 5 variable associée à cette dimension; et une deuxième phase au cours de laquelle la région d'intérêt ainsi agrandie, respectivement rétrécie, est ajoutée à l'ensemble des régions d'intérêt sélectionnées si la densité des points de cette région vérifiant ladite modalité est supérieure à 10 ladite densité-seuil prédéterminée et si la taille de cette région est supérieure à ladite taille-seuil minimale prédéterminée. Ces caractéristiques permettent d'optimiser la taille et la dimension de chaque région d'intérêt sélectionnée, et 15 d'ainsi améliorer l'exhaustivité et la précision des résultats obtenus. Cette optimisation de la taille et de la dimension de chaque région d'intérêt sélectionnée est effectuée à pleine visibilité. Avantageusement, chaque région d'intérêt sélectionnée 20 définit un sous-ensemble de l'ensemble de données organisé sous la forme de la liste d'instances, et une valeur-p est calculée pour le sous-ensemble de données formé par chaque région d'intérêt sélectionnée, pour ladite modalité de la variable de sortie considérée. 25 Avantageusement, le procédé comprend en outre une étape de comparaison, pour chaque région d'intérêt sélectionnée, entre la valeur-p calculée pour cette région et une valeur-seuil maximale prédéterminée, et une étape de sélection finale des régions d'intérêt pour lesquelles la valeur-p 30 calculée est inférieure à ladite valeur-seuil maximale. 3066289 13 Ces caractéristiques permettent de minimiser la probabilité de sélectionner de manière erronée des régions d'intérêt, et donc des règles d'association correspondantes, purement aléatoires. 5 L'invention se rapporte également à un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par une unité de traitement d'un ordinateur ou par un circuit logique programmable ou 10 reprogrammable, comprenant des instructions de programme, lesdites instructions de programme étant adaptées pour mettre en oeuvre les étapes du procédé de recherche de règles d'association dans une base de données tel que décrit ci-dessus lorsque le produit programme est exécuté sur une unité 15 de traitement d'un ordinateur ou sur un circuit logique programmable ou reprogrammable. L'invention se rapporte également à un support d'enregistrement, de type circuit logique programmable ou reprogrammable, sur lequel est enregistré un programme 20 d'ordinateur comprenant des instructions de code de programme pour mettre en oeuvre tout ou partie des étapes du procédé de recherche de règles d'association dans une base de données tel que décrit ci-dessus. Définitions : 25 Ordinateur : tout dispositif électronique structuré selon une architecture de type « von Neumann », et muni d'une unité de traitement de données, ainsi que de moyens de stockage de données, tel que par exemple un ordinateur de bureau, un ordinateur portable, un appareil de communication sans fil 3066289 14 tel qu'un smartphone, ou encore une tablette numérique, sans que cette liste ne soit exhaustive. Circuit logique programmable ou reprogrammable : tout circuit intégré logique apte à être reconfiguré après sa 5 fabrication, tel que par exemple un circuit FPGA (de l'anglais « Field-Programmable Gate Array »), un circuit PLD (de l'anglais « Programmable Logic Device »), un circuit EPLD (de l'anglais « Erasable Programmable Logic Device »), un circuit CPLD (de l'anglais « Complex Programmable Logic 10 Device »), un circuit PAL (de l'anglais « Programmable Array Logic »), ou encore un circuit PLA (de l'anglais « Programmable Logic Array »), sans que cette liste ne soit exhaustive. Instance ou individu : ensemble de valeurs numériques réelles 15 prises par un nombre prédéterminé de variables. Classe d'une instance ou d'un individu : valeur numérique prise par une variable de sortie pour cette instance ou cet individu. Attributs d'une instance ou d'un individu : ensemble des 20 valeurs numériques prises par plusieurs variables d'entrée pour cette instance ou cet individu. Modalité : critère à vérifier par la valeur d'une variable de sortie. Liste d'instances ou d'individus : ensemble de plusieurs 25 instances ou individus sélectionné(e)s parmi une population donnée. Espace ou sous-espace : ensemble de n dimensions parmi les N dimensions (n N). 3066289 15 Région d'un espace : sous partie fermée d'un espace. Hyperrectangle : analogue n-dimensionnel d'un rectangle en dimension deux, et d'un parallélépipède rectangle en dimension trois. 5 Sommets d'un hyperrectangle diagonalement opposés selon une grande diagonale de cet hyperrectangle : deux sommets d'un hyperrectangle qui sont opposés selon une grande diagonale, au sens géométrique du terme, de cet hyperrectangle, c'est-à-dire selon une diagonale telle que le plus court chemin 10 (sur les arêtes de l'hyperrectangle) reliant les deux sommets opposés selon cette diagonale emprunte exactement un nombre d'arêtes égal au nombre de dimensions de cet hyperrectangle. BREVE DESCRIPTION DES FIGURES 15 D'autres caractéristiques et avantages de l'invention ressortiront à la lecture de la description qui suit, en référence aux figures annexées, dans lesquelles : la figure 1 est une représentation schématique d'un ordinateur, comprenant une unité de traitement et 20 des moyens mémoire stockant une application apte à mettre en oeuvre le procédé de recherche de règles d'association selon un mode de réalisation de l'invention ; la figure 2 est une représentation schématique d'un 25 exemple de base de données au sein de laquelle le procédé de recherche de règles d'association selon un mode de réalisation de l'invention peut être appliqué ; 3066289 16 la figure 3 est un organigramme représentant le procédé de recherche de règles d'association dans une base de données selon un mode de réalisation de l'invention ; 5 la figure 4 est une représentation schématique d'une étape particulière du procédé de la figure 2, illustrant la représentation d'une région convexe droite particulière, dans un espace à trois dimensions ; 10 la figure 5 est une représentation schématique d'un ensemble ordinateur - circuit logique programmable ou reprogrammable, le circuit logique stockant une application apte à mettre en oeuvre le procédé selon un mode de réalisation de l'invention ; 15 la Figure 6 représente le temps d'exploration dans un espace en fonction du nombre d'entités ; la Figure 7 représente le nombre de régions en fonction du nombre d'entités ; la Figure 8 représente la vitesse d'exploration en 20 fonction du nombre d'entités ; la Figure 9 représente le temps d'exploration dans un espace en fonction du nombre de dimensions ; la Figure 10 représente le nombre de régions en fonction du nombre de dimensions ; et 25 la Figure 11 représente la vitesse d'exploration en fonction du nombre de dimensions. 3066289 17 Pour plus de clarté, les éléments identiques ou similaires sont repérés par des signes de référence identiques sur l'ensemble des figures. MODES DE REALISATION 5 Dans la suite, il est divulgué en particulier un procédé de recherche de règles d'association dans une base de données 2. Un ordinateur 4 est représenté schématiquement sur la figure 1. L'ordinateur 4 est muni d'une unité de traitement 10 6. L'unité de traitement 6 comprend par exemple un processeur 7 et des moyens de mémorisation 8 reliés au processeur 7. Les moyens de mémorisation 8 stockent la base de données 2, ainsi qu'une application 10. La base de données 2 comporte un ensemble de données. 15 L'ensemble de données est organisé sous la forme d'une liste 14 d'instances Il,..Ip, comme illustré sur la figure 2. Chaque instance Il,..Ipest définie par un ensemble de valeurs numériques réelles prises par un nombre prédéterminé de variables V1, ..VN,Vs. Les variables V1 f - - VN f Vs peuvent par 20 exemple être des variables représentées par des valeurs numériques réelles. L'application 10 est apte à être exécutée par le processeur 7 de l'unité de traitement 6, et comporte des instructions pour l'exécution d'un procédé de recherche de 25 règles d'association selon l'invention, comme cela sera détaillé par la suite. L'application 10 est par exemple une application téléchargeable, via une plateforme de téléchargement non représentée sur les figures. 3066289 18 Le procédé de recherche de règles d'association dans la base de données 2, mis en oeuvre par l'unité de traitement 6 de l'ordinateur 4, va maintenant être décrit en détail, en référence à la figure 3. On suppose qu'initialement 5 l'application 10 est exécutée par le processeur 7 de l'unité de traitement 6. Le procédé comporte une étape initiale 20 au cours de laquelle un ensemble de Ni variables V2,..VN sont sélectionnées parmi les variables V1,..VN, Vs de la liste 14 10 d'instances. L'ensemble de Ni variables V2,..VN forme un ensemble de variables d'entrée et définit un espace de dimension Ni. Au cours d'une étape parallèle ou suivante 22, une variable Vs est sélectionnée parmi les variables restantes 15 Vi,Vs de la liste 14 d'instances. La variable Vs forme une variable de sortie. La variable Vs peut par exemple être une variable catégorielle pouvant prendre un nombre prédéterminé de valeurs catégorielles. Au cours d'une étape suivante 24, pour chaque variable 20 d'entrée sélectionnée V2,..VN, les valeurs numériques des instances Il,..Ip sont ordonnancées pour cette variable, de sorte à passer d'une topologie de valeurs réelles à une topologie de valeurs ordinales pour les variables d'entrée sélectionnées V2,..VN. Chaque instance Il,..Ip est alors 25 définie par un ensemble de rangs associés à chacune des valeurs des variables d'entrée V2,..VN de cette instance. Chaque instance Il,..Ip est alors représentée par un point dans l'espace de dimension Ni formé par l'ensemble des Ni variables d'entrée V2,..VN, comme représenté dans l'exemple 30 illustré sur la figure 4, exemple pour lequel Ni est égal à 3066289 19 trois (trois variables d'entrée sélectionnées V2,V3,V4), et P est égal à vingt-cinq (vingt-cinq instances Il,..I2s).Cette étape d'ordonnancement 24 en rangs permet de discrétiser les valeurs numériques des instances Il,..Ip pour les variables 5 d'entrée V2,..VN, et d'ainsi pouvoir rendre le problème dénombrable. En effet, une telle étape d'ordonnancement en rangs permet de s'affranchir d'un grand nombre de calculs, tout en conservant la même topologie de résultats. Ceci permet de simplifier l'analyse combinatoire sans perdre de 10 généralité des résultats, comme cela sera décrit par la suite en lien avec l'étape 32 d'exploration. Avantageusement, lors de cette étape d'ordonnancement 24, un traitement des éventuels doublons de valeurs des variables d'entrée est effectué, afin qu'il ne subsiste aucun doublon de rangs pour 15 une même variable d'entrée à l'issue de cette étape. Un tel traitement peut par exemple consister, si deux valeurs d'une même variable d'entrée sont identiques pour deux instances, à leur affecter un rang différent consécutif. Une alternative d'un tel traitement peut consister à utiliser une autre 20 variable, indicative du nombre d'instances ayant un même rang pour la variable d'entrée considérée. Au cours d'une étape suivante ou parallèle 26, au moins une modalité est définie pour la variable de sortie Vs sélectionnée. Une modalité est définie comme un critère à 25 vérifier par la valeur de la variable de sortie V. Dans l'exemple de réalisation illustré sur la figure 4, la variable de sortie Vs est une variable binaire apte à prendre deux valeurs distinctes : une première valeur représentée par une étoile dans l'espace de dimension Ni, et une deuxième 30 valeur représentée par un cercle dans ce même espace. Selon cet exemple de réalisation particulier, la modalité définie pour cette variable de sortie Vsest la première valeur. 3066289 20 En variante non représentée, les étapes d'ordonnancement 24 et de définition d'au moins une modalité 26 peuvent être inversées. De préférence, le procédé comprend une étape suivante 5 28 de détermination, dans chaque sous-espace de l'espace de dimension Ni, d'un majorant de la taille des régions convexes droites de ce sous-espace ; ainsi qu'une étape 30 de comparaison, pour chaque sous-espace de l'espace de dimension Ni, entre ce majorant et une taille-seuil minimale 10 prédéterminée. La taille d'une région convexe droite donnée est définie comme étant le nombre de points représentatifs d'instances Il,..Ip qui sont contenus, au sens géométrique du terme, dans le fermé formé par cette région convexe droite. 15 Au cours d'une étape suivante 32, des régions convexes droites sont explorées dans des sous-espaces de l'espace de dimension Ni. Chaque région convexe droite explorée est un hyperrectangle présentant, sur deux sommets diagonalement opposés selon une grande diagonale de cet hyperrectangle, 20 deux points représentatifs de deux instances Il,..Ip dont la valeur de la variable de sortie Vs vérifie la modalité précédemment définie pour cette variable Vs à l'étape 26. Plus précisément, chaque région convexe droite explorée est l'hyperrectangle qui, dans le sous-espace dont la dimension 25 correspond à la dimension de cet hyperrectangle, peut être défini de manière univoque uniquement par ces deux points. Par exemple, dans l'exemple de réalisation particulier illustré sur la figure 4, une région convexe droite explorée 33 est représentée. Cette région convexe droite 33 est 30 l'hyperrectangle de dimension trois (autrement dit un parallélépipède rectangle) qui présente, sur deux sommets 3066289 21 diagonalement opposés selon une grande diagonale du parallélépipède, deux points représentatifs de deux instances 114, 118 dont la valeur de la variable de sortie Vs vérifie la modalité (première valeur représentée par une 5 étoile), et qui peut être défini de manière univoque uniquement par ces deux points 114, I. De préférence, lorsque le procédé comprend l'étape 28 de détermination et l'étape 30 de comparaison, seuls les sous-espaces pour lesquels le majorant déterminé est 10 supérieur à la taille-seuil minimale prédéterminée sont explorés au cours de l'étape 32 d'exploration. Ceci permet de ne pas explorer certains chemins de sous-espaces qui seraient inutiles à explorer. Ainsi, cette caractéristique permet de réduire la complexité combinatoire liée au nombre 15 de variables et au nombre d'espaces liés à ces variables, et d'ainsi permettre une réduction avantageuse de la complexité et du temps de calcul. Au cours d'une étape suivante 34, certaines régions d'intérêt sont sélectionnées parmi les régions convexes 20 droites explorées. Chaque région d'intérêt sélectionnée contient un nombre de points Il,..Ip vérifiant la modalité précédemment définie à l'étape 26 tel que la densité de ces points est supérieure à une densité-seuil prédéterminée. Avantageusement, chaque région d'intérêt sélectionnée 25 contient en outre un nombre de points Il,..Ip, appelé taille, tel que ce nombre est supérieur à la taille-seuil minimale prédéterminée. Par exemple, dans l'exemple de réalisation particulier illustré sur la figure 4, la région convexe droite explorée 33 a été sélectionnée en tant que région 30 d'intérêt pour la modalité de la variable Vs considérée. En effet, en considérant que la taille-seuil minimale était de 3066289 22 cinq points et que la densité-seuil était de quatre points, la région convexe droite 33 contient six points 18,19,114,117,118 représentatifs d'instances, et contient, parmi ces six points, cinq points 19,114,117,118 dont la valeur 5 de la variable de sortie Vs vérifie la modalité (première valeur représentée par une étoile). Chaque région d'intérêt sélectionnée définit un sous-ensemble de l'ensemble de données organisé sous la forme de la liste 14 d'instances. Les valeurs limites des variables 10 d'entrée V2,..VN qui délimitent une région d'intérêt donnée définissent une règle d'association dans la base de données 2. Lorsqu'une nouvelle instance dont seules les valeurs des variables d'entrée sont connues est ensuite ajoutée à la liste 14 d'instance de la base de données 2, une telle règle 15 d'association permet ensuite de prédire éventuellement l'état de la variable de sortie Vs pour cette nouvelle instance. En effet, si le point représentatif de cette nouvelle instance est contenu, au sens géométrique du terme, dans le fermé formé par la région convexe droite d'intérêt 20 définissant la règle d'association, il est possible de prédire que l'état de la variable de sortie Vs pour cette nouvelle instance correspondra à la modalité précédemment définie pour cette variable de sortie V. De préférence, à l'issue de l'étape 34 de sélection, 25 une valeur-p est calculée pour le sous-ensemble de données formé par chaque région d'intérêt sélectionnée, pour la modalité précédemment définie pour la variable de sortie Vs à l'étape 26. Par « valeur-p » on entend la probabilité, dans un test statistique, d'obtenir la même valeur du test 30 si l'hypothèse nulle était vraie. Dans le cas présent le test consiste, pour une région convexe droite explorée, à 3066289 23 vérifier si cette région contient un nombre de points Il,..Ip vérifiant la modalité précédemment définie à l'étape 26 tel que la densité de ces points soit supérieure à la densité-seuil prédéterminée. Cette valeur-p permet ainsi dans le cas 5 présent de déterminer à quel point la sélection d'une région d'intérêt donnée, et donc de la règle d'association correspondante, est statistiquement significative. De préférence encore, lorsqu'une valeur-p est calculée pour le sous-ensemble de données formé par chaque région 10 d'intérêt sélectionnée, le procédé comprend une étape suivante 36 de comparaison, pour chaque région d'intérêt sélectionnée, entre la valeur-p calculée pour cette région et une valeur-seuil maximale prédéterminée, et une étape 38 de sélection finale des régions d'intérêt pour lesquelles la 15 valeur-p calculée est inférieure à cette valeur-seuil maximale. Ces étapes de comparaison 36 et de sélection finale 38 permettent de minimiser la probabilité de sélectionner de manière erronée des régions d'intérêt, et donc des règles 20 d'association correspondantes, purement aléatoires. De préférence, le procédé comprend en outre une étape suivante 40 de raffinement des régions d'intérêt sélectionnées. L'étape de raffinement 40 comprend, pour chaque région d'intérêt sélectionnée, une première phase 42 25 d'agrandissement ou de réduction de la taille de cette région, et une deuxième phase 44 au cours de laquelle la région d'intérêt ainsi agrandie ou rétrécie est ajoutée à l'ensemble des régions d'intérêt sélectionnées si la densité des points Il,..Ip de cette région qui vérifient la modalité 30 précédemment définie est supérieure à la densité-seuil 3066289 24 prédéterminée, et si la taille de cette région est supérieure à la taille-seuil minimale prédéterminée. Lorsqu'il s'agit d'un agrandissement de la taille de la région d'intérêt, la première phase 42 consiste en 5 l'augmentation, selon chaque dimension du sous-espace associé à cette région d'intérêt, de la valeur du rang maximum entre les deux instances dont les deux points représentatifs définissent cette région d'intérêt, pour la variable associée à cette dimension. En variante ou en 10 complément, cette première phase 42 peut aussi consister dans ce cas en la diminution, selon chaque dimension du sous-espace associé à cette région d'intérêt, de la valeur du rang minimum entre les deux instances dont les deux points représentatifs définissent cette région d'intérêt, pour la 15 variable associée à cette dimension. Lorsqu'il s'agit d'une réduction de la taille de la région d'intérêt, la première phase 42 consiste en la diminution, selon chaque dimension du sous-espace associé à cette région d'intérêt, de la valeur du rang maximum entre 20 les deux instances dont les deux points représentatifs définissent cette région d'intérêt, pour la variable associée à cette dimension. En variante ou en complément, cette première phase 42 peut aussi consister dans ce cas en l'augmentation, selon chaque dimension du sous-espace 25 associé à cette région d'intérêt, de la valeur du rang minimum entre les deux instances dont les deux points représentatifs définissent cette région d'intérêt, pour la variable associée à cette dimension. Cette étape de raffinement 40 permet d'affiner les 30 solutions retenues, en optimisant localement ainsi qu'en terme de dimensionnalité les régions d'intérêt sélectionnées 3066289 25 lors de l'étape de sélection 34 ou 38, ceci afin d'identifier des régions d'intérêt encore meilleures. Cette étape de raffinement 40 permet ainsi d'optimiser la taille et la dimension de chaque région d'intérêt sélectionnée, et 5 d'améliorer l'exhaustivité et la précision des résultats obtenus. Un ensemble 50 comprenant un ordinateur 51 et un circuit logique programmable ou reprogrammable 54 est représenté schématiquement sur la figure 5. 10 L'ordinateur 51 est muni d'une unité de traitement 52. L'unité de traitement 52 comprend par exemple un processeur 53A et des moyens de mémorisation 53B reliés au processeur 53A. Les moyens de mémorisation 53B stockent la base de données 2. 15 Le circuit logique programmable ou reprogrammable 54 stocke une application 58. Le circuit logique programmable ou reprogrammable 54 forme ainsi un support d'enregistrement sur lequel est enregistrée l'application 58. L'application 58 est apte à être exécutée par le circuit 20 logique programmable ou reprogrammable 54, sur instruction de l'ordinateur 51, et comporte des instructions pour l'exécution du procédé de recherche de règles d'association selon l'invention. Cette exécution du procédé s'effectue de manière analogue à ce qui a été décrit précédemment en lien 25 avec la mise en oeuvre de l'application 10, et ne sera donc pas décrit ici plus en détail. Ce portage de l'application 58 sur le circuit logique programmable ou reprogrammable 54 permet avantageusement de multiplier la vitesse de calcul tout en diminuant fortement 3066289 26 le coût logistique et environnemental de l'utilisation d'un ordinateur unique. En variante, l'application 58 est stockée dans les moyens de mémorisation 53B de l'ordinateur 51 ou dans le circuit 5 logique programmable ou reprogrammable 54, et est exécutable en partie par le processeur 53A de l'unité de traitement 52, et en partie par le circuit logique programmable ou reprogrammable 54. L'invention a été illustrée et décrite en détail dans 10 les dessins et la description précédente. Celle-ci doit être considérée comme illustrative et donnée à titre d'exemple et non comme limitant l'invention à cette seule description. De nombreuses variantes de réalisation sont possibles. 15 COMPLEXITE ALGORITHMIQUE DU PROCEDE Formulation mathématique du problème à résoudre Soient Met N le nombre d'instances et le nombre de variables d'entrée de la base de données. Soit C la classe de la 20 variable de sortie. Le support (respectivement la taille) d'une région convexe droite R quelconque est défini comme suit : 1 PR = 1(m E R) (respectivement TR = M PR) rnER Sa moyenne (respectivement sa pureté) est définie comme suit 25 1 1YR = MR E 0 (respectivement SR = MYR) P rnER 3066289 27 Nous cherchons l' ensemble des régions (Rn'ien)ii n N, (i, j) E [1,M]2 dont la pureté sur une modalité spécifiée de la variable de sortie est supérieure à un certain seuil, et dont la taille est, de préférence, raisonnablement 5 importante. Complexité du problème - approche « naïve » par énumération exhaustive des solutions Nous avons besoin de discrétiser l'espace pour pouvoir 10 dénombrer les solutions possibles. En effet, dans le cas général où les dimensions du problème sont représentées par des variables numériques réelles, il existe une infinité de points de coordonnées permettant de servir de base à la construction d'une région convexe droite. 15 Une méthode naturelle pour effectuer la discrétisation de l'espace - et donc de rendre le problème dénombrable - consiste à limiter la précision des coordonnées des points composant l'espace des instances. On choisit alors une précision à p chiffres après la virgule pour une plage de 20 valeurs s'étalant dans un intervalle [ri;11/1]. Dans ce cas, la discrétisation naturelle se fait en 10P X (M - valeurs distinctes. En effectuant deux hypothèses, nous pouvons simplifier l'analyse combinatoire sans perte de généralité des 25 résultats : a. Discrétisation identique sur toutes les dimensions b. Pas de prise en compte des doublons 3066289 28 Dénombrement des solutions possibles dans un espace à D dimensions Pour un discrétisation à n= 10P x (M-m) valeurs distinctes, il existe 0-uplets de coordonnées, dont nous pouvons choisir 5 2 éléments distincts, nécessaires et suffisants pour caractériser une région convexe droite. En utilisant la notation classique de la combinatoire mathématique, il nr)! existe C2D - - (D2)2 façons de choisir 2 éléments parmi un n! ensemble contenant np éléments. Nous devons diviser ce 10 nombre par le nombre de diagonales que possède une région convexe droite en D dimensions, soit 2D-1, puisque tous les couples de points diagonaux correspondant définissent tous la même région. L'ordre de la complexité combinatoire liée à l'exploration 15 d'un espace de dimension D est donc : (n2)D Dénombrement des sous-espaces de dimension d réduction de la complexité du problème d'un facteur pouvant aller de 10 à 10 000 voire beaucoup 3066289 32 plus (facteur croissant en fonction du nombre de variables) Cl l'étape d'exploration, dans des sous-espaces de 5 l'espace de dimension Ni, de régions convexes droites, chaque région convexe droite explorée étant un hyperrectangle présentant, sur deux sommets diagonalement opposés selon une grande diagonale dudit hyperrectangle, deux points représentatifs de deux 10 instances dont la valeur de la variable de sortie vérifie la modalité, chaque région convexe droite explorée étant en outre l'hyperrectangle qui, dans le sous-espace dont la dimension correspond à la dimension dudit hyperrectangle, peut être défini de manière 15 univoque uniquement par ces deux points. H> réduction de la complexité du problème d'un facteur pouvant aller de 10 à 100 (facteur croissant en fonction du nombre d'instances) 20 Numériquement, pour D dimensions et M instances, le nombre de régions à explorer via la mise en oeuvre d'une telle étape d'exploration est : M. (M - 1) 2 25 La complexité du problème devient polynomiale, puisque la dépendance globale est selon le carré du nombre d'instances (M2), et ne dépend plus du nombre de dimensions. Le temps de traitement global est donc polynomial lui aussi. 3066289 33 On obtient ainsi, en fonction de la dimension initiale du problème, une réduction globale de la complexité de ce problème d'un facteur pouvant aller de 100 à 1 000 000, voire beaucoup plus dans des espaces de données à forte 5 dimensionnalité. Cette réduction est obtenue uniquement en travaillant de manière ingénieuse sur la structure des données de la base de données initiale, ainsi que sur la structure des solutions retenues. 10 EXEMPLES NUMERIQUES (TEMPS DE TRAITEMENT COMPARES) Les exemples ci-après ont été exécutés sur une machine Dell Optiplex 380 (marques déposées) ayant comme unité centrale un Intel Core 3 Duo E8400 fonctionnant à 3GHz et avec une mémoire centrale de 4Go. Le système d'exploitation de cette 15 machine est Windows 7 Professionnel 64bits. Les données utilisées ont variées de 100 à 500 entités et de 5 à 10 dimensions. Résultats 20 Impact du nombre d'attributs Le nombre d'attributs (les variables attachées aux dimensions) entraine un faible impact sur les performances. Un univers de 100 entités comportant de 5 à 10 attributs (donc 465 régions quel que soit le nombre de dimensions) est 25 testé en approximativement en 20 ms. 3066289 34 Temps d'exécution (en ms) Impact du nombre d'entités Exploration d'un seul espace 5 Lorsque l'univers (ici en 5 dimensions) passe de 100 à 500 entités, le temps d'exécution passe de 16 à 1.636 ms avec un total des régions explorées passant de 465 à 12.850 (NB : on n'explore ici qu'un seul espace à 5 dimensions et non tous ses sous-espaces). 10 Le temps d'exploration augmente bien avec le nombre d'entités, mais on constate surtout une décélération : la vitesse d'exploration (exprimée régions/s) décroit avec le nombre d'entités. Dimensions : 5 16 135 417 1 082 1 636 465 2 345 5 043 8 761 12 850 29 063 17 370 12 094 8 097 7 855 15 3066289 Ainsi, la Figure 6 représente le temps d'exploration dans un espace en fonction du nombre d'entités, la Figure 7 représente le nombre de régions en fonction du nombre d'entités et la Figure 8 représente la vitesse d'exploration 5 en fonction du nombre d'entités. Exploration de tous les sous-espaces (1 à 5 dimensions) Lorsqu'on explore tous les sous-espaces de 1 à 5 dimensions avec un univers contenant de 100 à 500 entités, le temps d'exécution passe de 251 à 36.257 ms avec un total 10 des régions explorées passant de 14.415 à 398.576. Impact du nombre de dimensions On explore ici un univers de 100 entités dans des espaces comportant de 1 à 10 dimensions. 251 14 415 2 558 72 702 9 162 156 390 22 152 271 726 36 257 398 576 200 300 400 500 251 490 931 1 964 3 469 7 324 14 415 29 295 59 055 118 575 237 359 475 183 3066289 36 Ainsi, la Figure 9 représente le temps d'exploration dans un espace en fonction du nombre de dimensions, la Figure 10 représente le nombre de régions en fonction du nombre de 5 dimensions et la Figure 11 représente la vitesse d'exploration en fonction du nombre de dimensions. Ainsi on constate que la vitesse d'exploration est à peu près constante à 62 000 régions/s (ici pour un univers de 100 entités), mais le nombre de régions croît 10 exponentiellement avec le nombre de dimensions. Par ailleurs, le test atomique d'appartenance d'une entité à une région ne dépend que faiblement du nombre d'attributs, la vitesse d'exploration décroit avec le nombre d'entités, et le temps total d'exploration varie 15 linéairement avec le nombre de régions à explorer, mais ce nombre croît beaucoup plus vite avec le nombre de dimensions qu'avec le nombre d'entités. REVENDICATIONS1. Procédé, mis en oeuvre par une unité de traitement (6 ; 52) d'un ordinateur (4 ; 51) et/ou par un circuit logique 5 programmable ou reprogrammable (54), de recherche de règles d'association dans une base de données (2), la base de données (2) étant stockée dans des moyens de mémorisation (8 ; 53B) de l'unité de traitement (6 ; 52) ou dans le circuit logique programmable ou reprogrammable (54) et 10 comportant un ensemble de données, l'ensemble de données étant organisé sous la forme d'une liste (14) d'instances, chaque instance étant définie par un ensemble de valeurs numériques réelles prises par un nombre prédéterminé de variables ; le procédé comprenant les étapes suivantes: 15 - la sélection (20) d'un ensemble de Ni variables parmi lesdites variables de la liste (14) d'instances, ledit ensemble de Ni variables formant un ensemble de variables d'entrée et définissant un espace de dimension Ni ; et la sélection (22) d'une variable parmi les variables restantes 20 de la liste (14) d'instances, ladite variable formant une variable de sortie ; - l'ordonnancement (24), pour chaque variable d'entrée de la liste (14) d'instances sélectionnée, des valeurs numériques des instances pour cette variable, de sorte à passer d'une 25 topologie de valeurs réelles à une topologie de valeurs ordinales pour les variables d'entrée sélectionnées, chaque instance étant alors définie par un ensemble de rangs associés à chacune des valeurs des variables d'entrée de cette instance, chaque instance étant représentée par un 30 point dans ledit espace de dimension Ni ; 3066289 38 - la définition (26) d'au moins une modalité pour la variable de sortie sélectionnée, ladite modalité étant définie comme un critère à vérifier par la valeur de ladite variable de sortie ; - l'exploration (32), dans des sous-espaces de l'espace de dimension Ni, de régions convexes droites (33), chaque région convexe droite explorée (33) étant un hyperrectangle présentant, sur deux sommets diagonalement opposés selon une grande diagonale dudit hyperrectangle, deux points représentatifs de deux instances dont la valeur de la variable de sortie vérifie ladite modalité, chaque région convexe droite explorée (33) étant en outre l'hyperrectangle qui, dans le sous-espace dont la dimension correspond à la dimension dudit hyperrectangle, peut être défini de manière univoque uniquement par ces deux points ; - la sélection (34), parmi lesdites régions convexes droites explorées, de régions d'intérêt, chaque région d'intérêt sélectionnée contenant un nombre de points vérifiant ladite modalité tel que la densité de ces points est supérieure à une densité-seuil prédéterminée, les valeurs limites des variables d'entrée qui délimitent une région d'intérêt donnée définissant une règle d'association dans la base de données (2). 2. Procédé selon la revendication 1, dans lequel chaque région d'intérêt sélectionnée contient en outre un nombre de points représentatifs d'instances, appelé taille, tel que ce nombre est supérieur à une taille-seuil minimale prédéterminée. 3066289 39 3. Procédé selon la revendication 2, dans lequel le procédé comprend en outre une étape (28) de détermination, dans chaque sous-espace de l'espace de dimension Ni, d'un majorant de la taille des régions convexes droites de ce 5 sous-espace, et une étape (30) de comparaison, pour chaque sous-espace de l'espace de dimension Ni , entre ce majorant et ladite taille-seuil minimale. 4. Procédé selon la revendication 3, dans lequel, lors de 10 l'étape (32) d'exploration, dans des sous-espaces de l'espace de dimension Ni, de régions convexes droites, seuls les sous-espaces pour lesquels le majorant déterminé est supérieur à la taille-seuil minimale sont explorés. 15 5. Procédé selon l'une quelconque des revendications 2 à 4, dans lequel le procédé comprend en outre une étape (40) de raffinement des régions d'intérêt sélectionnées, l'étape de raffinement (40) comprenant, pour chaque région d'intérêt sélectionnée, une première phase (42) d'agrandissement, 20 respectivement de réduction, de la taille de cette région par augmentation, selon chaque dimension du sous-espace associé à ladite région d'intérêt, de la valeur du rang maximum et/ou par diminution, selon chaque dimension du sous-espace associé à ladite région d'intérêt, de la valeur du 25 rang minimum entre les deux instances définissant ladite région d'intérêt, pour la variable associée à cette dimension; respectivement par diminution, selon chaque dimension du sous-espace associé à ladite région d'intérêt, de la valeur du rang maximum et/ou par augmentation, selon 30 chaque dimension du sous-espace associé à ladite région 3066289 40 d'intérêt, de la valeur du rang minimum entre les deux instances définissant ladite région d'intérêt, pour la variable associée à cette dimension; et une deuxième phase (44) au cours de laquelle la région d'intérêt ainsi agrandie, 5 respectivement rétrécie, est ajoutée à l'ensemble des régions d'intérêt sélectionnées si la densité des points de cette région vérifiant ladite modalité est supérieure à ladite densité-seuil prédéterminée et si la taille de cette région est supérieure à ladite taille-seuil minimale 10 prédéterminée. 6. Procédé selon l'une quelconque des revendications précédentes, dans lequel chaque région d'intérêt sélectionnée définit un sous-ensemble de l'ensemble de 15 données organisé sous la forme de la liste (14) d'instances, et dans lequel une valeur-p est calculée pour le sous-ensemble de données formé par chaque région d'intérêt sélectionnée, pour ladite modalité de la variable de sortie considérée. 20 7. Procédé selon la revendication 6, dans lequel le procédé comprend en outre une étape (36) de comparaison, pour chaque région d'intérêt sélectionnée, entre la valeur-p calculée pour cette région et une valeur-seuil maximale 25 prédéterminée, et une étape (38) de sélection finale des régions d'intérêt pour lesquelles la valeur-p calculée est inférieure à ladite valeur-seuil maximale. 3066289 41 8. Produit programme d'ordinateur (10 ; 58) téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par une unité de traitement (6 ; 52) d'un ordinateur (4 ; 51) ou par un 5 circuit logique programmable ou reprogrammable (54), caractérisé en ce qu'il comprend des instructions de programme, lesdites instructions de programme étant adaptées pour mettre en oeuvre les étapes du procédé de recherche de règles d'association dans une base de données (2) selon l'une 10 quelconque des revendications précédentes lorsque le produit programme est exécuté sur une unité de traitement (6 ; 52) d'un ordinateur (4 ; 51) ou sur un circuit logique programmable ou reprogrammable (54). 15 9. Support d'enregistrement (54), de type circuit logique programmable ou reprogrammable, sur lequel est enregistré un programme d'ordinateur (58) comprenant des instructions de code de programme pour mettre en oeuvre tout ou partie des étapes du procédé de recherche de règles d'association dans 20 une base de données (2) selon l'une quelconque des revendications 1 à 7.