Intégration de méthodes de data mining dans le renseignement criminel : analyse par des structures issues de la théorie des graphes dans le profilage des stupéfiants

Data mining can be defined as the extraction of previously unknown and potentially useful information from large datasets. The main principle is to devise computer programs that run through databases and automatically seek deterministic patterns. It is applied in different fields of application, e.g., remote sensing, biometry, speech recognition, but has seldom been applied to forensic case data. The intrinsic difficulty related to the use of such data lies in its heterogeneity, which comes from the many different sources of information. The aim of this study is to highlight potential uses of pattern recognition that would provide relevant results from a criminal intelligence point of view. The role of data mining within a global crime analysis methodology is to detect all types of structures in a dataset. Once filtered and interpreted, those structures can point to previously unseen criminal activities. The interpretation of patterns for intelligence purposes is the final stage of the process. It allows the researcher to validate the whole methodology and to refine each step if necessary. An application to cutting agents found in illicit drug seizures was performed. A combinatorial approach was done, using the presence and the absence of products. Methods coming from the graph theory field were used to extract patterns in data constituted by links between products and place and date of seizure. A data mining process completed using graphing techniques is called ``graph mining''. Patterns were detected that had to be interpreted and compared with preliminary knowledge to establish their relevancy. The illicit drug profiling process is actually an intelligence process that uses preliminary illicit drug classes to classify new samples. Methods proposed in this study could be used \textit{a priori} to compare structures from preliminary and post-detection patterns. This new knowledge of a repeated structure may provide valuable complementary information to profiling and become a source of intelligence.

Méthodes de visualisation en analyse criminelle: approche générale de conception des schémas relationnels et développement d'un catalogue de patterns

Le travail policier et l'enquête judiciaire nécessitent de prendre de nombreuses décisions : choisir quelle trace analyser, mettre sous surveillance ou en détention un suspect, sont autant de décisions qui sont prises quotidiennement par les acteurs du système judiciaire. Ces décisions font l'objet de pesées d'intérêts qui se fondent sur l'analyse de l'information accessible. C'est le rôle de l'analyse criminelle de mettre en perspective l'information colligée pour la rendre intelligible aux décideurs compétents. L'usage de représentations graphiques est notamment recommandé pour soutenir l'analyse et la communication de ces informations.Des techniques de visualisation relationnelle sont notamment exploitées dans les enquêtes judiciaires afin de faciliter le traitement d'affaires d'envergure. Les éléments pertinents de l'enquête sont représentés sous la forme de schémas décrivant les relations entre les événements et les entités d'intérêts (tel que des personnes, des objets et des traces). Les exploitations classiques de ces techniques qui s'apparentent à des graphes, sont par exemple : la représentation de réseaux criminels, de trafics de marchandises, de chronologies d'événements, ainsi que la visualisation de relations téléphoniques et financières. Dans ce contexte, la visualisation soutient un nombre importants d'objectifs, tels qu'analyser les traces et les informations collectées, évaluer a posteriori une investigation, aider à qualifier les infractions, faciliter l'appréhension d'un dossier, voire soutenir une argumentation lors du procès.La pratique intègre des outils logiciels simples qui produisent des graphiques élégants et souvent percutants. Leur utilisation semble néanmoins soulever des difficultés. Cette recherche tend à montrer qu'il existe des disparités étonnantes lors de l'exploitation de ces techniques. Des biais de raisonnement et de perception peuvent être induits, allant jusqu'à provoquer des décisions aux conséquences parfois désastreuses. Ce constat révèle la nécessité de consolider les méthodes pratiquées.Pour mettre en évidence ces difficultés, des évaluations ont été effectuées avec des praticiens et des étudiants. Elles ont permis d'établir une image empirique de l'étendue des variations de conception et d'interprétation des représentations, ainsi que de leurs impacts sur la prise de décision. La nature et la diversité des concepts à représenter, l'absence d'un consensus émergeant sur la manière de représenter les données, la diversité des solutions visuelles envisageables, les contraintes imposées par les outils exploités et l'absence d'une formalisation claire du langage, sont autant de causes supposées des difficultés.Au cours des vingt dernières années, plusieurs axes de développement ont été proposés pour traiter les difficultés observées, tels que l'amélioration des automatismes facilitant la conception d'une représentation, l'exploitation des techniques de réseaux sociaux, l'automatisation de l'identification et de l'extraction des entités dans du texte non-structuré et la définition de langages formels. Cette recherche propose une approche parallèle fondée sur une exploitation adaptée de structures de graphe et de propriétés visuelles pour optimiser la représentation en fonction des objectifs définis et de la nature des informations à représenter.Des solutions ont été recherchées selon plusieurs axes. Des recommandations générales, issues de diverses communautés de recherche liées à la visualisation, ont été recherchées afin de proposer une démarche générale de conception des schémas relationnels. Par ailleurs, le développement d'un catalogue de bonnes pratiques formalisées sous la forme de patterns de visualisation a été amorcé. Chaque pattern décrit une solution particulière pour un problème d'analyse récurrent, tel que l'analyse d'une série de cambriolages. Finalement, l'impact sur les outils de la méthodologie proposée est discuté en regard des limites qu'ils imposent. Un prototype de visualisation multidimensionnel a été élaboré.Cette recherche met en évidence les difficultés rencontrées lors de l'exploitation de représentations graphiques pour soutenir le processus de l'enquête judiciaire et propose des éléments de méthode et des innovations techniques utiles tant pour l'enseignement de la discipline que pour sa pratique.

Evolutionary games on complex networks : the emergence and maintenance of cooperation

Abstract The object of game theory lies in the analysis of situations where different social actors have conflicting requirements and where their individual decisions will all influence the global outcome. In this framework, several games have been invented to capture the essence of various dilemmas encountered in many common important socio-economic situations. Even though these games often succeed in helping us understand human or animal behavior in interactive settings, some experiments have shown that people tend to cooperate with each other in situations for which classical game theory strongly recommends them to do the exact opposite. Several mechanisms have been invoked to try to explain the emergence of this unexpected cooperative attitude. Among them, repeated interaction, reputation, and belonging to a recognizable group have often been mentioned. However, the work of Nowak and May (1992) showed that the simple fact of arranging the players according to a spatial structure and only allowing them to interact with their immediate neighbors is sufficient to sustain a certain amount of cooperation even when the game is played anonymously and without repetition. Nowak and May's study and much of the following work was based on regular structures such as two-dimensional grids. Axelrod et al. (2002) showed that by randomizing the choice of neighbors, i.e. by actually giving up a strictly local geographical structure, cooperation can still emerge, provided that the interaction patterns remain stable in time. This is a first step towards a social network structure. However, following pioneering work by sociologists in the sixties such as that of Milgram (1967), in the last few years it has become apparent that many social and biological interaction networks, and even some technological networks, have particular, and partly unexpected, properties that set them apart from regular or random graphs. Among other things, they usually display broad degree distributions, and show small-world topological structure. Roughly speaking, a small-world graph is a network where any individual is relatively close, in terms of social ties, to any other individual, a property also found in random graphs but not in regular lattices. However, in contrast with random graphs, small-world networks also have a certain amount of local structure, as measured, for instance, by a quantity called the clustering coefficient. In the same vein, many real conflicting situations in economy and sociology are not well described neither by a fixed geographical position of the individuals in a regular lattice, nor by a random graph. Furthermore, it is a known fact that network structure can highly influence dynamical phenomena such as the way diseases spread across a population and ideas or information get transmitted. Therefore, in the last decade, research attention has naturally shifted from random and regular graphs towards better models of social interaction structures. The primary goal of this work is to discover whether or not the underlying graph structure of real social networks could give explanations as to why one finds higher levels of cooperation in populations of human beings or animals than what is prescribed by classical game theory. To meet this objective, I start by thoroughly studying a real scientific coauthorship network and showing how it differs from biological or technological networks using divers statistical measurements. Furthermore, I extract and describe its community structure taking into account the intensity of a collaboration. Finally, I investigate the temporal evolution of the network, from its inception to its state at the time of the study in 2006, suggesting also an effective view of it as opposed to a historical one. Thereafter, I combine evolutionary game theory with several network models along with the studied coauthorship network in order to highlight which specific network properties foster cooperation and shed some light on the various mechanisms responsible for the maintenance of this same cooperation. I point out the fact that, to resist defection, cooperators take advantage, whenever possible, of the degree-heterogeneity of social networks and their underlying community structure. Finally, I show that cooperation level and stability depend not only on the game played, but also on the evolutionary dynamic rules used and the individual payoff calculations. Synopsis Le but de la théorie des jeux réside dans l'analyse de situations dans lesquelles différents acteurs sociaux, avec des objectifs souvent conflictuels, doivent individuellement prendre des décisions qui influenceront toutes le résultat global. Dans ce cadre, plusieurs jeux ont été inventés afin de saisir l'essence de divers dilemmes rencontrés dans d'importantes situations socio-économiques. Bien que ces jeux nous permettent souvent de comprendre le comportement d'êtres humains ou d'animaux en interactions, des expériences ont montré que les individus ont parfois tendance à coopérer dans des situations pour lesquelles la théorie classique des jeux prescrit de faire le contraire. Plusieurs mécanismes ont été invoqués pour tenter d'expliquer l'émergence de ce comportement coopératif inattendu. Parmi ceux-ci, la répétition des interactions, la réputation ou encore l'appartenance à des groupes reconnaissables ont souvent été mentionnés. Toutefois, les travaux de Nowak et May (1992) ont montré que le simple fait de disposer les joueurs selon une structure spatiale en leur permettant d'interagir uniquement avec leurs voisins directs est suffisant pour maintenir un certain niveau de coopération même si le jeu est joué de manière anonyme et sans répétitions. L'étude de Nowak et May, ainsi qu'un nombre substantiel de travaux qui ont suivi, étaient basés sur des structures régulières telles que des grilles à deux dimensions. Axelrod et al. (2002) ont montré qu'en randomisant le choix des voisins, i.e. en abandonnant une localisation géographique stricte, la coopération peut malgré tout émerger, pour autant que les schémas d'interactions restent stables au cours du temps. Ceci est un premier pas en direction d'une structure de réseau social. Toutefois, suite aux travaux précurseurs de sociologues des années soixante, tels que ceux de Milgram (1967), il est devenu clair ces dernières années qu'une grande partie des réseaux d'interactions sociaux et biologiques, et même quelques réseaux technologiques, possèdent des propriétés particulières, et partiellement inattendues, qui les distinguent de graphes réguliers ou aléatoires. Entre autres, ils affichent en général une distribution du degré relativement large ainsi qu'une structure de "petit-monde". Grossièrement parlant, un graphe "petit-monde" est un réseau où tout individu se trouve relativement près de tout autre individu en termes de distance sociale, une propriété également présente dans les graphes aléatoires mais absente des grilles régulières. Par contre, les réseaux "petit-monde" ont, contrairement aux graphes aléatoires, une certaine structure de localité, mesurée par exemple par une quantité appelée le "coefficient de clustering". Dans le même esprit, plusieurs situations réelles de conflit en économie et sociologie ne sont pas bien décrites ni par des positions géographiquement fixes des individus en grilles régulières, ni par des graphes aléatoires. De plus, il est bien connu que la structure même d'un réseau peut passablement influencer des phénomènes dynamiques tels que la manière qu'a une maladie de se répandre à travers une population, ou encore la façon dont des idées ou une information s'y propagent. Ainsi, durant cette dernière décennie, l'attention de la recherche s'est tout naturellement déplacée des graphes aléatoires et réguliers vers de meilleurs modèles de structure d'interactions sociales. L'objectif principal de ce travail est de découvrir si la structure sous-jacente de graphe de vrais réseaux sociaux peut fournir des explications quant aux raisons pour lesquelles on trouve, chez certains groupes d'êtres humains ou d'animaux, des niveaux de coopération supérieurs à ce qui est prescrit par la théorie classique des jeux. Dans l'optique d'atteindre ce but, je commence par étudier un véritable réseau de collaborations scientifiques et, en utilisant diverses mesures statistiques, je mets en évidence la manière dont il diffère de réseaux biologiques ou technologiques. De plus, j'extrais et je décris sa structure de communautés en tenant compte de l'intensité d'une collaboration. Finalement, j'examine l'évolution temporelle du réseau depuis son origine jusqu'à son état en 2006, date à laquelle l'étude a été effectuée, en suggérant également une vue effective du réseau par opposition à une vue historique. Par la suite, je combine la théorie évolutionnaire des jeux avec des réseaux comprenant plusieurs modèles et le réseau de collaboration susmentionné, afin de déterminer les propriétés structurelles utiles à la promotion de la coopération et les mécanismes responsables du maintien de celle-ci. Je mets en évidence le fait que, pour ne pas succomber à la défection, les coopérateurs exploitent dans la mesure du possible l'hétérogénéité des réseaux sociaux en termes de degré ainsi que la structure de communautés sous-jacente de ces mêmes réseaux. Finalement, je montre que le niveau de coopération et sa stabilité dépendent non seulement du jeu joué, mais aussi des règles de la dynamique évolutionnaire utilisées et du calcul du bénéfice d'un individu.

La conception de schémas relationnels en analyse criminelle: au-delà de la maîtrise des outils

Des techniques de visualisation sont exploitées dans les enquêtes judiciaires afin de faciliter le traitement d'affaires d'envergure. Les éléments pertinents de l'enquête sont représentés par des schémas décrivant les relations entre les évènements et les entités d'intérêt. Les exploitations classiques de ces techniques qui s'apparentent à la construction de graphes sont par exemple : la représentation de réseaux criminels, de trafics de marchandises, de chronologies d'évènements, ainsi que la visualisation de relations téléphoniques et financières. Dans ce contexte, la visualisation soutient un nombre important d'objectifs, tels qu'analyser les traces et les informations collectées, évaluer à posteriori une investigation, aider à qualifier les infractions, faciliter l'appréhension d'un dossier et la prise de décisions au cours d'une enquête, voire soutenir une argumentation lors du procès. La pratique intègre des outils logiciels simples qui produisent des graphiques élégants et souvent percutants. Cette recherche tend à montrer qu'il existe des disparités étonnantes lors de l'exploitation de ces techniques. Des biais de raisonnement et de perception peuvent être induits, allant jusqu'à provoquer des décisions aux conséquences parfois désastreuses. Pour mettre en évidence ces difficultés, des évaluations ont été effectuées avec des praticiens et des étudiants. Elles ont permis d'établir une image empirique de l'étendue des variations de conception et d'interprétation des représentations, ainsi que de leurs impacts sur la prise de décision. La nature et la diversité des concepts à représenter, l'absence de consensus sur la manière de représenter les données, la diversité des solutions visuelles envisageables, les contraintes imposées par les outils exploités et l'absence d'une formalisation claire du langage, sont autant de causes supposées des difficultés. Ce constat révèle la nécessiter de consolider les méthodes pratiquées.

La conception de schémas relationnels en analyse criminelle: au-delà de la maîtrise des outils

Des techniques de visualisation sont exploitées dans les enquêtes judiciaires afin de facili- ter le traitement d'affaires d'envergure. Les éléments pertinents de l'enquête sont repré- sentés par des schémas décrivant les relations entre les événements et les entités d'inté- rêt. Les exploitations classiques de ces techniques qui s'apparentent à la construction de graphes, sont par exemple: la représentation de réseaux criminels, de trafics de marchan- dises, de chronologies d'événements, ainsi que la visualisation de relations téléphoniques et financières. Dans ce contexte, la visualisation soutient un nombre importants d'objectifs, tels qu'analyser les traces et les informations collectées, évaluer a posteriori une investiga- tion, aider à qualifier les infractions, faciliter l'appréhension d'un dossier et la prise de déci- sions au cours d'une enquête, voire soutenir une argumentation lors du procès. La pratique intègre des outils logiciels simples qui produisent des graphiques élégants et souvent per- cutants. Cette recherche tend à montrer qu'il existe des disparités étonnantes lors de l'ex- ploitation de ces techniques. Des biais de raisonnement et de perception peuvent être induits, allant jusqu'à provoquer des décisions aux conséquences parfois désastreuses. Pour mettre en évidence ces difficultés, des évaluations ont été effectuées avec des prati- ciens et des étudiants. Elles ont permis d'établir une image empirique de l'étendue des variations de conception et d'interprétation des représentations, ainsi que de leurs impacts sur la prise de décision. La nature et la diversité des concepts à représenter, l'absence de consensus sur la manière de représenter les données, la diversité des solutions visuelles envisageables, les contraintes imposées par les outils exploités et l'absence d'une forma- lisation claire du langage, sont autant de causes supposées des difficultés. Ce constat révèle la nécessité de consolider les méthodes pratiquées.

Analyse de réseau piéton et gestion scolaire: sinuosité, centricité et transport optimal régularisé

Que ce soit d'un point de vue, urbanistique, social, ou encore de la gouvernance, l'évolution des villes est un défi majeur de nos sociétés contemporaines. En offrant la possibilité d'analyser des configurations spatiales et sociales existantes ou en tentant de simuler celles à venir, les systèmes d'information géographique sont devenus incontournables dans la gestion et dans la planification urbaine. En cinq ans la population de la ville de Lausanne est passée de 134'700 à 140'570 habitants, alors que les effectifs de l'école publique ont crû de 12'200 à 13'500 élèves. Cet accroissement démographique associé à un vaste processus d'harmonisation de la scolarité obligatoire en Suisse ont amené le Service des écoles à mettre en place et à développer en collaboration avec l'université de Lausanne des solutions SIG à même de répondre à différentes problématiques spatiales. Établies en 1989, les limites des établissements scolaires (bassins de recrutement) ont dû être redéfinies afin de les réadapter aux réalités d'un paysage urbain et politique en pleine mutation. Dans un contexte de mobilité et de durabilité, un système d'attribution de subventions pour les transports publics basé sur la distance domicile-école et sur l'âge des écoliers, a été conçu. La réalisation de ces projets a nécessité la construction de bases de données géographiques ainsi que l'élaboration de nouvelles méthodes d'analyses exposées dans ce travail. Cette thèse s'est ainsi faite selon une dialectique permanente entre recherches théoriques et nécessités pratiques. La première partie de ce travail porte sur l'analyse du réseau piéton de la ville. La morphologie du réseau est investiguée au travers d'approches multi-échelles du concept de centralité. La première conception, nommée sinuo-centralité ("straightness centrality"), stipule qu'être central c'est être relié aux autres en ligne droite. La deuxième, sans doute plus intuitive, est intitulée centricité ("closeness centrality") et exprime le fait qu'être central c'est être proche des autres (fig. 1, II). Les méthodes développées ont pour but d'évaluer la connectivité et la marchabilité du réseau, tout en suggérant de possibles améliorations (création de raccourcis piétons). Le troisième et dernier volet théorique expose et développe un algorithme de transport optimal régularisé. En minimisant la distance domicile-école et en respectant la taille des écoles, l'algorithme permet de réaliser des scénarios d'enclassement. L'implémentation des multiplicateurs de Lagrange offre une visualisation du "coût spatial" des infrastructures scolaires et des lieux de résidence des écoliers. La deuxième partie de cette thèse retrace les aspects principaux de trois projets réalisés dans le cadre de la gestion scolaire. À savoir : la conception d'un système d'attribution de subventions pour les transports publics, la redéfinition de la carte scolaire, ou encore la simulation des flux d'élèves se rendant à l'école à pied. *** May it be from an urbanistic, a social or from a governance point of view, the evolution of cities is a major challenge in our contemporary societies. By giving the opportunity to analyse spatial and social configurations or attempting to simulate future ones, geographic information systems cannot be overlooked in urban planning and management. In five years, the population of the city of Lausanne has grown from 134'700 to 140'570 inhabitants while the numbers in public schools have increased from 12'200 to 13'500 students. Associated to a considerable harmonisation process of compulsory schooling in Switzerland, this demographic rise has driven schooling services, in collaboration with the University of Lausanne, to set up and develop GIS capable of tackling various spatial issues. Established in 1989, the school districts had to be altered so that they might fit the reality of a continuously changing urban and political landscape. In a context of mobility and durability, an attribution system for public transport subventions based on the distance between residence and school and on the age of the students was designed. The implementation of these projects required the built of geographical databases as well as the elaboration of new analysis methods exposed in this thesis. The first part of this work focuses on the analysis of the city's pedestrian network. Its morphology is investigated through multi-scale approaches of the concept of centrality. The first conception, named the straightness centrality, stipulates that being central is being connected to the others in a straight line. The second, undoubtedly more intuitive, is called closeness centrality and expresses the fact that being central is being close to the others. The goal of the methods developed is to evaluate the connectivity and walkability of the network along with suggesting possible improvements (creation of pedestrian shortcuts).The third and final theoretical section exposes and develops an algorithm of regularised optimal transport. By minimising home to school distances and by respecting school capacity, the algorithm enables the production of student allocation scheme. The implementation of the Lagrange multipliers offers a visualisation of the spatial cost associated to the schooling infrastructures and to the student home locations. The second part of this thesis recounts the principal aspects of three projects fulfilled in the context of school management. It focuses namely on the built of an attribution system for public transport subventions, a school redistricting process and on simulating student pedestrian flows.