Search

As a whole, this thesis focuses on the quantitative and qualitative aspects of the search for association rules and proposes generalizations of classical approaches as well as innovative evaluation and extraction solutions both in the supervised case and in the unsupervised case., Le modèle des règles d’association bénéficie, de par ses nombreuses applications, d’une grande popularité en fouille de données pour la découverte de connaissances à partir de données toujours plus volumineuses. Deux défis principaux se posent, l’un algorithmique pour la génération, et l’autre qualitatif pour l’évaluation et la validation des règles d’association. Par ailleurs, le problème de décision sous-jacent est NP-complet. Les techniques classiques d’extraction procèdent généralement en deux phases. La première extrait des motifs sous une contrainte de fréquence, notamment grâce à une propriété d’antimonotonie, tandis que la seconde évalue et génère exhaustivement les règles à partir des motifs fréquents. Un grand nombre de mesure d’intérêt existent pour l’évaluation : ce travail s’appuie sur 42 d’entre elles. Dans ce contexte, nous définissons un cadre formel d’étude des règles d’association et des mesures, sur lequel nous nous appuyons pour étudier différentes propriétés qualitatives et algorithmiques des règles d’association. Dans un premier temps, nous étudions la notion de robustesse, très peu étudiée à ce jour dans le contexte des règles d’association. Nous proposons une mesure de robustesse permettant de quantifier la validité d’une règle étant donnée une mesure d’intérêt. Cette mesure exprime pour une règle donnée, de façon opérationnelle, une zone de sécurité garantissant l’intérêt de la règle. Dans un second temps, nous étudions l’extraction des règles, et plus précisément l’insertion de la phase d’évaluation au coeur des algorithmes. Nous étudions 3 propriétés algorithmiques de la littérature : bien qu’intéressantes, celles-ci sont limitées à un nombre restreint de mesures. Nous les généralisons et montrons des conditions nécessaires et/ou suffisantes d’existence pour les mesures. Finalement, dans le cadre des règles de classe, nous généralisons la notion d’antimonotonie. Nous proposons alors des propriétés algorithmiques pour un ensemble de mesures qui permettent d’inclure celles-ci dans la phase de recherche. Nous montrons que cette approche est particulièrement efficace, et énonçons une condition permettant de déterminer les mesures possédant une telle propriété. Dans son ensemble, ce travail de thèse étudie les aspects quantitatifs et qualitatifs de la recherche des règles d’association et propose des généralisations d’approches classiques ainsi que des solutions innovantes d’évaluation et d’extraction tant dans le cas supervisé que dans le cas non supervisé.

International audience; Many studies have shown the limits of the support/confidence framework used in APRIORI -like algorithms to mine association rules. There are a lot of efficient implementations based on the antimonotony property of the support, but candidate set generation (e.g., frequent item set mining) is still costly. In addition, many rules are uninteresting or redundant and one can miss interesting rules like nuggets. We are thus facing a complexity issue and a quality issue. One solution is to not use frequent itemset mining and to focus as soon as possible on interesting rules using additional interestingness measures. We present here a formal framework that allows us to make a link between analytic and algorithmic properties of interestingness measures. We introduce the notion of optimonotony in relation with the optimal rule discovery framework. We then demonstrate a necessary and sufficient condition for the existence of optimonotony. This result can thus be applied to classify the measures. We study the case of 39 classical measures and show that 31 of them are optimonotone. These optimonotone measures can thus be used with an underlying pruning strategy. Empirical evaluations show that the pruning strategy is efficient and leads tothe discovery of nuggets using an optimonotone measure and without the support constraint.

National audience; Nous proposons dans cet article une définition formelle de la robustesse pour les règles d'association, s'appuyant sur une modélisation que nous avons précédemment définie. Ce concept est à notre avis central dans l'évaluation des règles et n'a à ce jour été que très peu étudié de façon satisfaisante. Il est crucial car malgré une très bonne évaluation par une mesure de qualité, une règle peut être très fragile par rapport à des variations légères des données. La mesure de robustesse que nous proposons dépend de la mesure de qualité utilisée pour évaluer les règles et du seuil d'acceptation minimal. Il est alors possible à partir de ces deux seuls éléments et de la valeur prise par la règle sur la mesure d'évaluer sa robustesse. Nous présentons plusieurs propriétés de cette robustesse, montrons sa mise en oeuvre et illustrons celle-ci par les résultats d'expériences sur plusieurs bases de données pour quelques mesures. Nous donnons ainsi un nouveau regard sur la qualification des règles.

International audience; Association Rules Discovery is an increasing subdomain of Datamining. Many works have focused on the extraction and the evaluation of the association rules, leading to many technical improvments on the algorithms, and many different measures. But few number of them have tried to merge the both. We introduce here a formal framework for the study of association rules and interestingness measures that allows an analytic study of these objects. This framework is based on the contingency table of a rule and let us make a link between analytic properties of the measures and algorithmic properties. We give as example the case of three algorithmic properties for the extraction of association rules that were generalized and applied with the help of this framework. These properties allow a pruning of the search space based on a large number of measures and without any support constraint.

A review of literature allowed first to a state of the art of the different routes to detect the ice on theone hand and of the use of magnetostrictive materials to measure small masses. Both the feasibility andapplicability of metglasses and nanocrystalline alloys to frost resonating sensors have been clearlyestablished.The principle of magnetostrictive sensing resonator was developed and a new comprehensiveanalytical model of ribbonshaped magnetostrictive resonators was successfully achieved. The present modelincludes mechanical losses and the final expression contains the complete transfer function between the inputand output powers. Thus, the predicted frequency response of the model fairly fits to the experimental one.In addition, it clearly explains henceforth the reversals of some harmonic frequencies which occur from theresonance and antiresonance phenomena.The implementation of this new model for the characterization of amorphous ribbons showed thusthat it is now possible to well estimate the coupling coefficient from the frequency response and the Young'smodulus or damping. So we could draw developments with the bias field parameters of the resonator for2826MB and 2605SC amorphous ribbons. The evolution of these parameters allows the magnetostrictioncurves to be well established, that consists in a new characterization method.The implementation of a first prototype permits to detect frost, confirming thus the feasibility ofdetecting icing this way, but these promising preliminary tests could not bring quantitative data to model thefrost deposition on a resonating sensor. Measurements using pregnant icing controlled temperature andhumidity are a first perspective. Finally, it is important to emphasize that the present results appear as a goodsupport for the valorization of this study, especially to elaborate of a prototype sensor based onmagnetostrictive ribbons, its packaging and its implementation in in situ icing conditions.; Une recherche bibliographique a permis de faire un état de l'art, d'une part des différents principespermettant de détecter le givre et d'autre part de l'application de matériaux magnétostrictifs à la mesure defaibles masses. La faisabilité et l’applicabilité de certains alliages amorphes et nanocristallins à la réalisationde capteurs de givre ont été démontrées.Suite à cet état de l'art, le principe de détection par résonateur magnétostrictif qui a été retenu, a faitl'objet d'une étude approfondie aboutissant à l'établissement d'un nouveau modèle analytique complet desrésonateurs magnétostrictifs sous forme de ruban. L'intérêt principal de ce modèle est la prise en compte depertes mécaniques et l'expression finale contenant la fonction de transfert complète entre les entrées et sortiesélectriques. Ainsi, la réponse en fréquence du modèle est vraiment similaire aux réponses expérimentales. Deplus, il apporte une explication aux retournements observés, pour certains harmoniques entre les fréquencesde résonance et d'antirésonance, pour lesquels l’origine n’avait pu être clairement identifiée.La mise en œuvre de ce nouveau modèle pour la caractérisation de rubans amorphes a montré qu'ilest possible de déterminer le coefficient de couplage à partir de la réponse en fréquence ainsi que le moduled'Young ou l'amortissement. On a donc pu tracer pour des rubans de 2605SC et 2826MB les évolutions avecle champ de polarisation des paramètres du résonateur. De l'évolution de ces paramètres, il est possible dereconstruire les courbes de magnétostriction d'un ruban, ce qui constitue actuellement une méthode decaractérisation.La mise en œuvre d'un prototype a permis de détecter du givre et ainsi de confirmer la faisabilité dela détection de givrage par ce moyen, mais les essais préliminaires qui sont très prometteurs n’ont puapporter une réponse quantitative du capteur soumis à un dépôt de givre. Des mesures utilisant des enceintesde givrage contrôlées en température et en hygrométrie constituent une première perspective. Par ailleurs, lesrésultats présentés dans ce manuscrit s’avèrent une bonne base pour la valorisation de ces travaux,notamment pour la réalisation d’un prototype de capteur, son conditionnement et sa mise en œuvre dans devraies conditions de givrage.

As a whole, this thesis focuses on the quantitative and qualitative aspects of the search for association rules and proposes generalizations of classical approaches as well as innovative evaluation and extraction solutions both in the supervised case and in the unsupervised case.; Le modèle des règles d’association bénéficie, de par ses nombreuses applications, d’une grande popularité en fouille de données pour la découverte de connaissances à partir de données toujours plus volumineuses. Deux défis principaux se posent, l’un algorithmique pour la génération, et l’autre qualitatif pour l’évaluation et la validation des règles d’association. Par ailleurs, le problème de décision sous-jacent est NP-complet. Les techniques classiques d’extraction procèdent généralement en deux phases. La première extrait des motifs sous une contrainte de fréquence, notamment grâce à une propriété d’antimonotonie, tandis que la seconde évalue et génère exhaustivement les règles à partir des motifs fréquents. Un grand nombre de mesure d’intérêt existent pour l’évaluation : ce travail s’appuie sur 42 d’entre elles. Dans ce contexte, nous définissons un cadre formel d’étude des règles d’association et des mesures, sur lequel nous nous appuyons pour étudier différentes propriétés qualitatives et algorithmiques des règles d’association. Dans un premier temps, nous étudions la notion de robustesse, très peu étudiée à ce jour dans le contexte des règles d’association. Nous proposons une mesure de robustesse permettant de quantifier la validité d’une règle étant donnée une mesure d’intérêt. Cette mesure exprime pour une règle donnée, de façon opérationnelle, une zone de sécurité garantissant l’intérêt de la règle. Dans un second temps, nous étudions l’extraction des règles, et plus précisément l’insertion de la phase d’évaluation au coeur des algorithmes. Nous étudions 3 propriétés algorithmiques de la littérature : bien qu’intéressantes, celles-ci sont limitées à un nombre restreint de mesures. Nous les généralisons et montrons des conditions nécessaires et/ou suffisantes d’existence pour les mesures. Finalement, dans le cadre des règles de classe, nous généralisons la notion d’antimonotonie. Nous proposons alors des propriétés algorithmiques pour un ensemble de mesures qui permettent d’inclure celles-ci dans la phase de recherche. Nous montrons que cette approche est particulièrement efficace, et énonçons une condition permettant de déterminer les mesures possédant une telle propriété. Dans son ensemble, ce travail de thèse étudie les aspects quantitatifs et qualitatifs de la recherche des règles d’association et propose des généralisations d’approches classiques ainsi que des solutions innovantes d’évaluation et d’extraction tant dans le cas supervisé que dans le cas non supervisé.

A review of literature allowed first to a state of the art of the different routes to detect the ice on theone hand and of the use of magnetostrictive materials to measure small masses. Both the feasibility andapplicability of metglasses and nanocrystalline alloys to frost resonating sensors have been clearlyestablished.The principle of magnetostrictive sensing resonator was developed and a new comprehensiveanalytical model of ribbonshaped magnetostrictive resonators was successfully achieved. The present modelincludes mechanical losses and the final expression contains the complete transfer function between the inputand output powers. Thus, the predicted frequency response of the model fairly fits to the experimental one.In addition, it clearly explains henceforth the reversals of some harmonic frequencies which occur from theresonance and antiresonance phenomena.The implementation of this new model for the characterization of amorphous ribbons showed thusthat it is now possible to well estimate the coupling coefficient from the frequency response and the Young'smodulus or damping. So we could draw developments with the bias field parameters of the resonator for2826MB and 2605SC amorphous ribbons. The evolution of these parameters allows the magnetostrictioncurves to be well established, that consists in a new characterization method.The implementation of a first prototype permits to detect frost, confirming thus the feasibility ofdetecting icing this way, but these promising preliminary tests could not bring quantitative data to model thefrost deposition on a resonating sensor. Measurements using pregnant icing controlled temperature andhumidity are a first perspective. Finally, it is important to emphasize that the present results appear as a goodsupport for the valorization of this study, especially to elaborate of a prototype sensor based onmagnetostrictive ribbons, its packaging and its implementation in in situ icing conditions., Une recherche bibliographique a permis de faire un état de l'art, d'une part des différents principespermettant de détecter le givre et d'autre part de l'application de matériaux magnétostrictifs à la mesure defaibles masses. La faisabilité et l’applicabilité de certains alliages amorphes et nanocristallins à la réalisationde capteurs de givre ont été démontrées.Suite à cet état de l'art, le principe de détection par résonateur magnétostrictif qui a été retenu, a faitl'objet d'une étude approfondie aboutissant à l'établissement d'un nouveau modèle analytique complet desrésonateurs magnétostrictifs sous forme de ruban. L'intérêt principal de ce modèle est la prise en compte depertes mécaniques et l'expression finale contenant la fonction de transfert complète entre les entrées et sortiesélectriques. Ainsi, la réponse en fréquence du modèle est vraiment similaire aux réponses expérimentales. Deplus, il apporte une explication aux retournements observés, pour certains harmoniques entre les fréquencesde résonance et d'antirésonance, pour lesquels l’origine n’avait pu être clairement identifiée.La mise en œuvre de ce nouveau modèle pour la caractérisation de rubans amorphes a montré qu'ilest possible de déterminer le coefficient de couplage à partir de la réponse en fréquence ainsi que le moduled'Young ou l'amortissement. On a donc pu tracer pour des rubans de 2605SC et 2826MB les évolutions avecle champ de polarisation des paramètres du résonateur. De l'évolution de ces paramètres, il est possible dereconstruire les courbes de magnétostriction d'un ruban, ce qui constitue actuellement une méthode decaractérisation.La mise en œuvre d'un prototype a permis de détecter du givre et ainsi de confirmer la faisabilité dela détection de givrage par ce moyen, mais les essais préliminaires qui sont très prometteurs n’ont puapporter une réponse quantitative du capteur soumis à un dépôt de givre. Des mesures utilisant des enceintesde givrage contrôlées en température et en hygrométrie constituent une première perspective. Par ailleurs, lesrésultats présentés dans ce manuscrit s’avèrent une bonne base pour la valorisation de ces travaux,notamment pour la réalisation d’un prototype de capteur, son conditionnement et sa mise en œuvre dans devraies conditions de givrage.

International audience

International audience; Many studies have shown the limits of support/confidence framework used in Apriori-like algorithms to mine association rules. There are a lot of efficient implementations based on the antimonotony property of the support but candidate set generation is still costly. In addition many rules are uninteresting or redundant and one can miss interesting rules like nuggets. One solution is to get rid of frequent itemset mining and to focus as soon as possible on interesting rules. For that purpose algorithmic properties were first studied, especially for the confidence. They allow all confidence rules to be found without a preliminary support pruning. More recently, in the case of class association rules, the concept of optimal rules gave a pruning strategy compatible with more measures. However, all these properties have been demonstrated for a limited number of interestingness measures. We present a new formal framework which allows us to make the link between analytic and algorithmic properties of the measures. We apply this framework to optimal rules, and we demonstrate a necessary and sufficient condition of existence for this pruning strategy, which can be applied to any measure.

National audience; Différentes études ont montré les limites du couple support/confiance dans les algorithmes de type Apriori, tant du point de vue quantitatif (quantité des règles), que qualitatif (redondance, intérêt, pépites de connaissance). Une solution consiste à concentrer au plus tôt la recherche sur les règles intéressantes en utilisant des mesures d'intérêt possédant des propriétés algorithmiques, mais aussi des capacités à mettre en évidence des règles d'un intérêt certain. Celles-ci permettent alors de trouver les règles d'intérêt élevé, sans utiliser un élagage préalable par la condition de support. Elles rendent également possible la recherche efficace de pépites de connaissance. C'est le cas de la all-confidence (ou h-confidence), transformation antimonotone de la confiance. Nous nous intéressons ici à la possibilité d'appliquer une transformation semblable à d'autres mesures, au travers d'une condition nécessaire s'appuyant sur un cadre formel que nous définissons. Nous montrons cependant que parmi les 27 mesures étudiées ici, seules 5 d'entre elles peuvent être transformées en une mesure antimonotone. Ainsi bien que très prometteuse, cette propriété d'antimonotonie n'est à l'heure actuelle applicable qu'à peu de mesures.