论文题目：基于关联规则的领土演变解释与预测

0巴黎第8大学 - 突尼斯大学合作博士学位论文0由Asma GHARBI提交0为了获得博士学位0专业：计算机科学0一种基于关联规则的领土演变解释和预测方法0于2018年2月13日提交给以下评委会：0Hanene Azzag女士，法国巴黎第13大学副教授，HDR评委 Amel Borgi女士，突尼斯ElManar大学副教授，HDR评委 Jacqueline Signorini教授，法国巴黎第8大学教授，考官Cyril De Runz先生，法国兰斯大学副教授，HDR考官 HermanAkdag教授，法国巴黎第8大学教授，导师 Sami Faiz教授，突尼斯LaManouba大学教授，共同导师0致谢0首先，我要感谢我的评委团成员，他们同意评估这篇论文：AmelBorgi女士和Hanene Azzag女士同意担任评委，以及JacquelineSignorini教授同意审查这篇论文。我要感谢我的导师HermanAKDAG先生和SamiFAIZ先生对我研究工作的信任和指导。我还要感谢他们的可用性、倾听、尊重、鼓励和理解，这使我能够保持动力并继续前进，尽管有时会有疑虑。我要深深感谢Cyril DeRunz先生，他为我提供了长时间的指导，他的耐心、宝贵的建议和多次鼓励。我还要感谢LIASD的研究人员和工作人员，他们提供了良好的工作条件和研究研讨会，这为我扩展了科学知识。我不能忘记我的博士同事Malangua、Besma、Akram、Rabah、Saloua，他们为我提供了非常好的工作氛围，以及许多讨论对我在人际关系和科学方面都有很大的帮助。最后，我要感谢我的家人，感谢他们每天的支持、持续的鼓励，以及他们对我的信任和能力的信念。我爱你们，妈妈，爸爸，我爱你们，Zaynab，Ahmed和Hayet。最后，我要特别感谢我的丈夫，他是我生活、奋斗和成功的动力。我非常爱你，Hilel。感谢你持续的支持，感谢你的鼓励和理解。40鼓励。感谢你从这个考验开始以来给予我的爱和理解。我还要感谢你愿意为了我的抱负而牺牲你在突尼斯的日常生活、家人和朋友。我还要感谢你毫无怨言地资助我的学业。0简历0在这篇论文中，我们假设地理动态和地理对象的使用可以在一定程度上通过它们的功能变化和共同位置的历史来解释甚至预测。因此，我们提出利用频繁模式和关联规则的研究来提取这些动态的规则。这项工作还试图调整数据挖掘过程，以考虑所使用的时空数据的特殊性，特别是它们的不对称性。在这个背景下，我们的提议涉及到嵌入在数据集中的时空关系建模，适当表示学习数据，从而产生适用于我们的预测问题的规则。考虑到学习属性的频率的不对称性，我们提出了两种方法：一种方法使用多个最小支持阈值，另一种方法将属性分开处理。在第一种方法中，我们提出了两种MSApriori算法的改进，用于定义和分配这些阈值。至于第二种方法，我们提出了基于谓词语义的BERA算法，用于从结论构建到前提构建的规则生成。为了验证和评估这些不同的提议，我们提出了一个实验设备（SAFFIET）。借助这个设备，我们对来自Corine LandCover数据的不同测试集进行了实证研究。Table des mati`eresListe des tableauxvTable des figuresviListe des abr´eviationsxi1Introduction g´en´erale11.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.1Fouille de donn´ees spatio-temporelles . . . . . . . . . .11.1.2Application dans le suivi de changements d’occupa-tion/usage du sol . . . . . . . . . . . . . . . . . . . . .31.2Probl´ematiques . . . . . . . . . . . . . . . . . . . . . . . . . .51.3Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . .61.4Organisation du manuscrit . . . . . . . . . . . . . . . . . . . .82Dynamiques spatio-temporelles : d´efinitions et repr´esenta-tions112.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.2Temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.2.1D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . .112.2.2Repr´esentation de la notion du temps . . . . . . . . . .122.2.3Repr´esentation du temps dans les syst`emes d’information 172.3Espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202.3.1D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . .202.3.2Repr´esentation de l’espace dans les syst`emes d’infor-mation g´eographique . . . . . . . . . . . . . . . . . . .222.4Espace-Temps . . . . . . . . . . . . . . . . . . . . . . . . . . .25iii2.4.1Mod`eles bas´es sur une repr´esentation implicite deschangements et des ph´enom`enes spatio-temporels . . .272.4.2Mod`eles bas´es sur une repr´esentation explicite deschangements . . . . . . . . . . . . . . . . . . . . . . . .342.4.3Mod`eles bas´es sur les ´ev`enements/processus . . . . . .382.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393M´ethodes informatis´ees pour la mod´elisation des change-ments d’occupation/usage du sol413.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .413.2Classification des mod`eles. . . . . . . . . . . . . . . . . . . .423.3Classification `a base d’approches. . . . . . . . . . . . . . . .423.4Approches de mod´elisation . . . . . . . . . . . . . . . . . . . .443.4.1Mod´elisation traditionnelle statique : math´ematique etstatistique . . . . . . . . . . . . . . . . . . . . . . . . .443.4.2Mod´elisation dynamique . . . . . . . . . . . . . . . . .463.5Discussions. . . . . . . . . . . . . . . . . . . . . . . . . . . .523.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .534.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .554.3Recherche de motifs fr´equents et l’extraction de r`egles d’asso-ciation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .584.3.2Extraction de r`egles d’association fr´equentes . . . . . .615Vision m´ethodologique des contributions775.2Approche globale . . . . . . . . . . . . . . . . . . . . . . . . .785.3Mod´elisation spatio-temporelle des entit´es ´evolutives. . . . .815.3.1Donn´ees d’entr´ee . . . . . . . . . . . . . . . . . . . . .815.3.2Mod`ele des donn´ees . . . . . . . . . . . . . . . . . . . .855.4Repr´esentation des donn´ees d’apprentissage. . . . . . . . . .865.5Adaptation du processus de fouille au probl`eme de l’asym´etrie915.5.1Supports multiples pour la g´en´eration des candidatscomplets . . . . . . . . . . . . . . . . . . . . . . . . . .9304 关联规则挖掘 5504.2 数据挖掘  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5604.3.1 频繁模式挖掘问题  . . . . . . . . . . . . . . . 5904.4 结论  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7605.1 简介  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77TABLE DES MATI`ERESiii5.5.2Algorithme BERA. . . . . . . . . . . . . . . . . . . . 1065.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096Dispositif Exp´erimental, r´esultats et discussions1136.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.2Dispositif exp´erimental . . . . . . . . . . . . . . . . . . . . . . 1136.2.1Suivi de l’´evolution . . . . . . . . . . . . . . . . . . . . 1156.2.2Construction du fichier d’apprentissage . . . . . . . . . 1176.2.3G´en´eration de mod`ele d’apprentissage . . . . . . . . . . 1186.2.4Crit`eres d’´evaluation . . . . . . . . . . . . . . . . . . . 1186.3Indicateurs d’´evaluation des mod`eles d’apprentissage produits1186.3.1Indicateurs pour la gestion de l’asym´etrie . . . . . . . . 1196.3.2Indicateurs sur la richesse des r`egles g´en´er´ees . . . . . . 1196.3.3Indicateur de qualit´e interne des mod`eles . . . . . . . . 1196.4Contexte exp´erimental . . . . . . . . . . . . . . . . . . . . . . 1236.4.1Jeux de donn´ees . . . . . . . . . . . . . . . . . . . . . . 1236.5.1Gestion de l’asym´etrie des donn´ees. . . . . . . . . . . 1256.5.3´Evaluation de la richesse des mod`eles g´en´er´es. . . . . 1286.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1327.1Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1387.1.1Perspectives techniques . . . . . . . . . . . . . . . . . . 1387.1.3Perspectives en termes d’am´elioration des algorithmesd’apprentissage . . . . . . . . . . . . . . . . . . . . . . 13906.5 结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12506.5.2 MSApriori方法在生成项目集方面的性能. . . . . . . . . . . . . . . 12706.5.4 生成规则的质量. . . . . . . . . . . . . . . . 12907 结论和展望 13507.1.2 关于减轻起始假设约束的展望. . . . . . . . . . . . . . . 1380参考文献 141TABLE DES MATI`ERESiv5.1S´emantique des items . . . . . . . . . . . . . . . . . . . . . . .886.2Bilan des items du point de vue s´emantique de pr´edicats. (a)le cas d’´etude de Seine-Saint-Denis, (b) le cas d’´etude de Paris 1246.4Performances en termes de g´en´eration des items S et SPF.Comparaisons entre les mod`eles issus des diff´erents algo-rithmes propos´es : le cas de Paris. *BERA est donn´e `a titreindicatif. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.5Performances en termes de g´en´eration de motifs et r`egles per-tinents. Comparaisons entre les mod`eles issus des diff´erentsalgorithmes propos´es : le cas de Seine-Saint-Denis. . . . . . . . 1296.6Performances en termes de g´en´eration de motifs et r`egles per-tinents. Comparaisons entre les mod`eles issus des diff´erentsalgorithmes propos´es : le cas de Paris. . . . . . . . . . . . . . . 1306.7Performances en termes de classification. Comparaisons entreles mod`eles explicatifs issus de diff´erents algorithmes propo-s´es : le cas de Seine-Saint-Denis. . . . . . . . . . . . . . . . . . 1306.8Performances en termes de classification. Comparaisons entreles mod`eles explicatifs issus de diff´erents algorithmes propo-s´es : le cas de Paris. . . . . . . . . . . . . . . . . . . . . . . . . 1316.9Performances en termes de classification. Comparaisons entreles mod`eles pr´edictifs issus de diff´erents algorithmes propos´es :le cas de Seine-Saint-Denis.. . . . . . . . . . . . . . . . . . . 131v0表格列表06.1 训练集和测试集的数量。. . . . . . . . . . . 12406.3生成S和SPF项目的性能。不同算法生成的模型之间的比较：以塞纳-圣但尼省为例。* BERA仅供参考。. . . . . . . . . . . . . . . . . . . . . . 126LISTE DES TABLEAUXvi6.10 Performances en termes de classification. Comparaisons entreles mod`eles pr´edictifs issus de diff´erents algorithmes propos´es :le cas de Paris.. . . . . . . . . . . . . . . . . . . . . . . . . . 131Table des figures2.1Les diff´erentes conceptions du temps. . . . . . . . . . . . . . .132.2Illustration des relations entre les intervalles selon l’alg`ebretemporelle d’Allen [Allen, 1983]. . . . . . . . . . . . . . . . . .162.3Illustration des composantes graphiques (a) et attributaires(b) de l’information g´eographique. . . . . . . . . . . . . . . . .232.4Les modes raster et vecteur de repr´esentation de l’informationg´eographique [Caloz and Collet, 2011] . . . . . . . . . . . . . .242.5Triade spatio-temporelle simple [Peuquet, 1994], puis compl´e-t´ee [Th´eriault and Claramunt, 1999].. . . . . . . . . . . . . .272.6Illustration du mod`ele en snapshot. Ci repr´esentent les diff´e-rents snapshots, ti repr´esentent les dates. . . . . . . . . . . . .292.7Utilisation du mod`ele composites spatio-temporels pour la re-constitution d’un territoire `a une date donn´ee T3. . . . . . . .302.8Illustration de la couche historique dans le mod`ele `a base decomposites spatio-temporels adapt´es. . . . . . . . . . . . . . .312.9Structuration de l’entit´e g´eographique [Cheylan et al., 1997]. .312.10 D´ecomposition des objets espace-temps en atomes espaces-temps [Worboys, 1998]. (a) : les objets espace-temps mod´e-lisant les changements de support (U, I, A). (b) : les atomesespaces temps correspondants `a ces objets (A1, I1, I2, A2, I3,U1).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .322.11 Les neufs changements produits par la transition entre deux´etats d’un seul objet [Hornsby and Egenhofer, 2000].. . . . .352.12 Exemples de changements impliquant plusieurs objets.. . . .352.13 Mod´elisation des changements sous la forme de morphismesd’arbres [Jiang and Worboys, 2009] : (a) cas d’une s´eparation ;(b) cas d’une insertion. . . . . . . . . . . . . . . . . . . . . . .37viiTABLE DES FIGURESviii4.1Le processus d’extraction de connaissance [Fayyad et al., 1996a] 574.2Un exemple de repr´esentation d’une relation binaire sous formede table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .594.3Treillis des itemsets correspondant `a l’exemple de la figure 4.2.604.4Un exemple illustrant l’ex´ecution de l’algorithme Apriori. . . .6404.5 使用哈希结构计算项集支持的示例 6604.6 生成的时空规则结构示例 [Alouaoui et al., 2015] 7505.1 方法论贡献的综述 8005.2我们方法的方法流程：用于提取时空规则以描述和潜在预测领域演变的处理链 8105.3 数据表示：经典采集模型和时空模型中的快照模型示例 8205.4 根据Rodier和Saligny [Rodier and Saligny,2010]的时空对象（OST）概念化示例 8305.5 在土地利用变化背景下，时间的线性、有序和定量表示示例 8305.6 在Corine Land Cover数据[EEA,2009]中，1990年和2000年之间的三个不同变化示例 8505.7 对应于学习数据库的MCD 8705.8 在学习数据库中记录变化的示例 8805.9 生成事务学习实例 [Gharbi et al., 2016b] 8905.10 学习数据库的结构示例 [Gharbi et al., 2016b] 9005.11 分割和合并关系的事务表示示例 [Gharbi et al., 2016c] 9005.12 初步结果概览 9105.13 统计研究中考虑的示例元素 10105.14 根据四分位数方法生成频繁项集的示例，考虑其语义 10605.15 在处理属性时构建事务的示例 1086.7Nomenclature de la base de donn´ees CLC [EEA, 2009]. . . . . 1336.8Comparaison volum´etrique entre les algorithmes correspon-dants `a l’approche MSApriori en termes de g´en´erations dek-itemsets : le cas de paris . . . . . . . . . . . . . . . . . . . . 1346.9Comparaison volum´etrique entre les algorithmes correspon-dants `a l’approche MSApriori en termes de g´en´eration de k-itemsets : le cas de Seine-Saint-Denis . . . . . . . . . . . . . . 1340图表目录 ix05.16在数据集示例上执行BERA的示例，包括Data：初始数据库，DataS：包含频繁项集的事务数据库，DataSPF：包含频繁spf的事务数据库，DataN：包含频繁n的事务数据库 10906.1 用于提取时空规则以描述和潜在预测领域演变的处理链的实现示例 11506.2 SAFFIET图形界面示例 [Gharbi et al., 2016a] 11606.3 shp2pgsql和psql命令的语法示例 11606.4 使用shp2pgsql和psql命令导入法国93省地图的示例，日期为1990年11706.5 在时间序列研究中确定两个时间连续地图之间的空间连续性的查询示例11706.6 混淆矩阵的示例以及表示真正例、真负例、假正例和假负例的数量的示例122TABLE DES FIGURESxListe des abr´eviations— minsup : Minimum support— MBA : Mod`ele `a Base d’Agents— minconf : Minimum confiance— AC : Automate Cellulaire— ECD : Extraction de Connaissances `a partir des Donn´ees— KDD : Knowledge Discovery in Database— ADN : Acide d´esoxyribonucl´eique— conf : confiance— CVC : Chauffage, Ventilation et Climatisation— SGBD : syst`eme de gestion de base de donn´ees— BERA : Backward Extraction Rule Algorithm— SAFFIET : Spatial And Functional Frequent Itemset ExtractionTool— SIG : Syst`eme d’Information G´eographique— CLC : Corine Land Cover— RAC : R`egle d’Association Classifiante— MCD : Mod`ele Conceptuel de donn´ees— SPF : Sequence of Past Functions – S´equence des pr´ec´edentes fonc-tions— SMI : Support Minimum d’Item— SQL : Structured Query Language— OST : Objet Spatio-Temporel— OGC : Open Geospatial Consortium— EPL : Event Pattern Language— CDL : Change Description Language— LUT : Land-Use Transport Modelsrajoute la liste des abr´eviations.xiTABLE DES FIGURESxiiChapitre 1Introduction g´en´erale1.1Introduction1.1.1Fouille de donn´ees spatio-temporellesL’information digitalis´ee a rendu possible la collecte et l’archivage d’une´enorme quantit´e de donn´ees op´erationnelles et facilement accessibles. Bienque ces entrepˆots de donn´ees ne cessent de croitre principalement en raisonde la disponibilit´e des syst`emes de bases de donn´ees qui sont de plus enplus puissants et efficaces, leur richesse en connaissance incorpor´ee sembletoujours sous exploit´ee [Witten and Frank, 2005]. Pour combler ce besoin,plusieurs m´ethodes d’analyse et de traitement des donn´ees ont ´et´e propo-s´ees [Zaki and Wagner Meira, 2014]. Celles-ci visent essentiellement `a d´ecou-vrir et `a extraire les connaissances cach´ees ou non-triviales qui utilis´ees `a bonescient, serviront pour une deuxi`eme phase d’exploitation de ces donn´ees :la mod´elisation. Ce sont ces mod`eles produits qui induiront diff´erentes hypo-th`eses et postulats `a vocation explicative et/ou pr´edictive qui seront employ´espour r´epondre `a un probl`eme donn´e. En effet le terme mod`ele repr´esente, dansle domaine de la fouille de donn´ees, les relations entre les variables ou les va-leurs d´ecrivant des individus dans un jeu de donn´ees [Kantardzic, 2003]. Unmod`ele n’´emane pas d’une th´eorie mais plutˆot d’un bon ajustement aux don-n´ees. Il tend `a fournir toutes les r`egles de fonctionnement et peut mˆeme aider`a pr´edire le fonctionnement futur du syst`eme ´etudi´e. Au fil des ans, diff´erentestechniques de fouille de donn´ees `a l’instar des mod`eles statistiques lin´eaires etnon lin´eaires, des r´eseaux de neurones, des algorithmes g´en´etiques, des arbresde d´ecision, des m´ethodes de partitionnement, les r`egles d’association, etc. ont12´et´e propos´ees afin de d´efinir des mod`eles permettant d’identifier des caract´e-ristiques des donn´ees, des patrons, ou des r`egles op´erationnelles pouvant ˆetreemploy´es pour diverses applications pratiques [Bharati and Ramageri, 2010].Les te