Search

We develop a weighted kernel k-means approach for clustering using the Sum-Over-Forests density index as node weights. Furthermore, we implement and test the developed algorithm and vary the used kernels to ascertain the algorithms functionality. The algorithm gives good results, but is strongly dependent on the kernel parameters as well as the density index parameter, both of which have to be tuned for optimal results. We achieve a reduction in algorithm runtime, albeit at the price of statistical measure scores.

[TODO] Add abstract here.

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connect- ing those elements increases and when the “length” of paths decreases. It turns out that the square root of the average commute time is a Eu- clidean distance and that the pseudoinverse of the Laplacian matrix is a kernel (its elements are inner products closely related to commute times). A procedure for computing the subspace projection of the node vectors of the graph that preserves as much variance as possible in terms of the commute-time distance – a principal component analysis (PCA) of the graph – is also introduced. This graph PCA provides a nice interpreta- tion to the “Fiedler vector”, widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where sug- gestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities (the pseudoinverse of the Laplacian matrix and the “random-forest matrix”) perform well in comparison with other methods. The model, which nicely fits into the so-called “statistical relational learning” framework, could also be usedto compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a database.

This work presents some general procedures for computing dissimilarities between nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the graph. This method is applied on the architecture of a Multi Agent System (MAS), in which each agent can be considered as a node and each interaction between two agents as a link. The model assigns transition probabilities to the links between agents, so that a random walker can jump from agent to agent. A quantity, called the average first-passage time, computes the average number of steps needed by a random walker for reaching agent k for the first time, when starting from agent i. A closely related quantity, called the average commute time, provides a distance measure between any pair of agents. Yet another quantity of interest, closely related to the average commute time, is the pseudoinverse of the Laplacian matrix of the graph, which represents a similarity measure between the nodes of the graph. These quantities, representing dissimilarities (similarities) between any two agents, have the nice property of decreasing (increasing) when the number of paths connecting two agents increases and when the "length" of any path decreases. The model is applied on a collaborative filtering task where suggestions are made about which movies people should watch based upon what they watched in the past. For the experiments, we build a MAS architecture and we instantiated the agents belief-set from a real movie database. Experimental results show that the Laplacian-pseudoinverse based similarity outperforms all the other methods.

In this short paper, we show that Kleinberg's hubs and authorities model (HITS) is simply Principal Components Analysis (PCA ­ maybe the most widely used multivariate statistical analysis method), albeit without centering, applied to the adjacency matrix of the graph of web pages. In addition to providing a new interpretation for HITS, this result suggests to rely on existing work, already published in the multivariate statistical analysis litterature (extensions of PCA), in order to design new web pages ranking procedures.

This work presents a novel procedure for computing (1) distances between nodes of a weighted, undirected, graph, called the Euclidean Commute Time Distance (ECTD), and (2) a subspace projection of the nodes of the graph that preserves as much variance as possible, in terms of the ECTD ­ a principal components analysis of the graph. It is based on a Markov-chain model of random walk through the graph. The model assigns transition probabilities to the links between nodes, so that a random walker can jump from node to node. A quantity, called the average commute time, computes the average time taken by a random walker for reaching node j for the first time when starting from node i, and coming back to node i. The square root of this quantity, the ECTD, is a distance measure between any two nodes, and has the nice property of decreasing when the number of paths connecting two nodes increases and when the "length" of any path decreases. The ECTD can be computed from the pseudoinverse of the Laplacian matrix of the graph, which is a kernel. We finally define the Principal Components Analysis (PCA) of a graph as the subspace projection that preserves as much variance as possible, in terms of the ECTD. This graph PCA has some interesting links with spectral graph theory, in particular spectral clustering.

In this paper,we present amaximumentropy (maxent) approach to the fusion of experts opinions, or classifiers outputs, problem. Themaxent approach is quite versatile and allows us to express in a clear, rigorous,way the a priori knowledge that is available on the problem. For instance, our knowledge about the reliability of the experts and the correlations between these experts can be easily integrated: Each piece of knowledge is expressed in the form of a linear constraint. An iterative scaling algorithm is used in order to compute the maxent solution of the problem. The maximum entropy method seeks the joint probability density of a set of random variables that has maximum entropy while satisfying the constraints. It is therefore the “most honest” characterization of our knowledge given the available facts (constraints). In the case of conflicting constraints, we propose to minimise the “lack of constraints satisfaction” or to relax some constraints and recompute the maximum entropy solution. The maxent fusion rule is illustrated by some simulations.

Ce document constitue la première phase de l’étude orienté objet de la cokerie de Carsid au cours de laquelle nous avons modélisé le fonctionnement de la cokerie. Pour ce faire, nous avons principalement utilisé le langage de modélisation UML. Les différentes phases du développement en UML peuvent être représentées au moyen d’une série de diagrammes permettant de comprendre de manière visuelle les concepts définis. Tous les modèles s’enchaînent en passant de l’analyse à la conception, gagnant en complexité, dans un langage commun et unique, s’affinant au fur et à mesure pour arriver à l’élaboration finale du modèle. Les diagrammes permettront de comprendre sous différents angles la globalité du cas étudié en présentant une vue statique et dynamique de celui-ci. Chaque diagramme exprimera une partie de la structure totale, tout en étant un aspect particulier du modèle.

This paper is the second part of the object-oriented study of the Carsid cokerie. The aim of this project was to redesign the data models from the Marchienne plant of CARSID and to integrate all of them in one single data model, while improving its design and showing the possibilities offered by OLAP technologies in the bettering of the data exploitation carried out in this plant.

Network (or graph) data analysis finds applications in many contexts, including biology, finance, marketing, and physics, to name a few. With the recent thriving of internet and social networks, these graph mining techniques have grown in popularity as an important tool to process, analyze, and make predictions from the quickly increasing amount of network data. This thesis mostly focuses on the randomized shortest path (RSP) framework, which defines a family of dissimilarities between nodes of a network that interpolates between the least cost path distance (optimal behavior) and the commute-cost distance (purely random behavior). This thesis therefore builds upon and extends this framework by proposing, among others, new dissimilarity measures, a design of biased random walk, as well as fast solutions to approximate the RSP for large graphs. It also explores various applications like node clustering, stochastic Markov decision processes, connectivity modeling in ecological landscapes, and collaborative filtering. (ECGE - Sciences économiques et de gestion) -- UCL, 2023

Since the rapid growth of the Internet and the advent of social networks in the 2000s, the amount of available network data is quickly increasing, leading to the development of new network analysis methods. Nowadays, these network analysis methods have spread to various fields, including, among others, marketing, supply chain, finance, and biology, as essential analysis and prediction tools. This thesis focuses on the development of one of these methods, called the bag-of-paths framework. This framework has the specificity to define a family of dissimilarity measures between nodes of the network that extrapolate between an optimal exploitation of the graph structure (optimal behavior - shortest path distance) and a random exploration of the graph (random behavior - commute time distance) via a parameter that controls the desired degree of randomness/exploration. Throughout this thesis, we propose several theoretical and practical extensions of the bag-of-paths framework. Regarding the theoretical contributions, we incorporate capacity constraints on edges, marginal constraints on input and output flows, and a Poisson distribution weighting and constraining path lengths, into the bag-of-paths framework. Furthermore, we expose the applicability of this framework through graph-based semi-supervised classification tasks and a real-life fraud detection case. (ECGE - Sciences économiques et de gestion) -- UCL, 2022

The emergence of networks and network data in different forms in the near past has given rise to development of new data analysis methods with a shift in focus from vector spaces to graph topologies. While some of these methods have been designed specifically for analyzing networks, others have been transformed from more traditional methods, for instance from the machine learning and data mining literature, to function also with networks or graph-based data. The main focus in the thesis is on the recently developed randomized shortest paths (RSP) framework, from which multiple interesting graph-based measures can be derived. These measures can be used either for analyzing networks directly or as tools augmenting existing machine learning or data mining methods. Essentially, the RSP framework defines a probability distribution on the set of paths connecting two nodes on a graph. The distribution focuses mostly on shortest paths but also assigns non-zero probability to longer connections between the two nodes. The extent of this spread of the probability mass is controlled by a temperature parameter, inspired by a thermodynamical analogy. From this distribution several meaningful quantities can be derived and computed conveniently, which have interesting connections with more traditional network measures. As one highlight, the thesis presents the free energy distance, which is a novel metric that is appealing theoretically in many ways, and has been shown to provide desirable and competitive results in different network analysis tasks compared with other measures. In addition, different measures for quantifying the centrality of a node in a network or the overall functionality of a network are proposed based on the RSP framework. The theory of RSPs is also extended with model estimation methods for fitting the RSP model to a dataset of trajectories on a network. In order to demonstrate and evaluate the derived methods the thesis deals with multiple application domains, ranging from the evaluation of ecological landscapes and quantifying centrality in an urban street network to clustering of text document collections. On the other hand, the methods are developed in a general theoretical setting and also discussed from different viewpoints in order to enable their use in other possible domains. (FSA - Sciences de l'ingénieur) -- UCL, 2018

Tout au long de ce mémoire, il a été essayé de répondre à la question suivante : « Les systèmes de recommandation enferment-ils les consommateurs dans une bulle ? ». Sur base de la littérature, des hypothèses à tester ont été imaginées. Ainsi, l’interrogation se porte, premièrement, sur le degré de connaissance des clients à propos des recommandations. L’impact sur le comportement d’achat des consommateurs a aussi été vérifié. Une autre source d’interrogation concerne le manque de variété des produits proposés par les recommandations. L’hypothèse suivante vise à détecter si les recommandations empêchent les véritables découvertes. Sur base de tous les éléments précédents, un argument d’isolement des individus à l’intérieur de la société est avancé par certains spécialistes du domaine. Enfin, pour les partisans de l’existence d’une bulle, celle-ci serait confortable pour les clients et cela a aussi été examiné. Pour tester ces différentes hypothèses, on procède en deux temps. Premièrement, une approche qualitative permet d’obtenir des éléments d’information. Ainsi, les analyses qualitatives, de 10 personnes en entretiens semi-directifs, ont pointé une différence majeure entre la littérature et la réalité. Il y a une incompréhension totale des individus par rapport à la dimension d’isolement dans la société des clients. C’est pourquoi cet aspect collectif a été abandonné. Deuxièmement, une approche quantitative est mise en place pour obtenir des résultats applicables à une population. Un questionnaire complété par 150 personnes a permis de réaliser des tests statistiques appropriés pour contrôler les hypothèses. Il découle des résultats que le phénomène de recommandation du web est très majoritairement connu par les consommateurs. On remarque également qu’il existe une influence des recommandations sur le comportement d’achat des clients. Paradoxalement, la variété de ce qui est acheté n’est pas impactée par les recommandations. Par contre, une majorité des répondants est d’avis que les propositions de produits sont peu variées. Selon les clients, il y a une découverte d’importance égale en présence de systèmes de recommandation que dans une situation neutre. Cependant, ces découvertes sont définies comme proches de la consommation habituelle. Enfin, pour l’échantillon, il semble possible qu’une bulle existe et celle-ci n’est pas perçue positivement par les clients. De par les résultats de cette étude, il est impossible de dire avec certitude si une bulle filtrante existe. Cependant, nous obtenons des éléments de réponses pour orienter les conclusions. Grâce aux différentes analyses, on peut supposer qu’il y a plus de chance qu’une bulle séparatrice existe pour les consommateurs que le contraire. Master [120] en ingénieur de gestion (Mons), Université catholique de Louvain, 2017

Ce mémoire a pour objectif principal d’identifier les causes et les conséquences du stress lié au cloud dans le cadre des activités professionnelles. Au travers de nos chapitres, nous abordons la gestion du changement et celle des connaissances comme des facteurs pouvant l’influencer. Nous étudions également l’impact du stress sur les performances des individus ainsi que le niveau de confiance et l’équilibre entre vie privée et vie professionnelle. Dans la revue de la littérature, nous abordons les différents sujets précédemment cités. Nous nous focalisons sur la définition de cloud et en abordons l’utilité dans les organisations. Nous utilisons principalement les nouvelles technologies de l’information et de la communication dont le cloud fait partie afin d’en exposer les avantages et inconvénients. Nous traitons également dans cette partie les théories déjà exposées par des scientifiques liants les technologies à des concepts managériaux comme la gestion des connaissances, des performances ou du changement tout en les définissant. Cette partie est également utilisée afin de justifier les hypothèses sur lesquelles repose ce mémoire. Les hypothèses peuvent être divisées en 3 groupes dont l’un en 3 sous-groupes. Le premier groupe contient l’unique hypothèse spécifique au cloud et qui concerne le niveau de connaissance du sujet. Le second concerne la relation entre le stress et le cloud. Nous y abordons la responsabilité du cloud dans le niveau de stress des individus dans le cadre professionnel, l’équilibre entre vie privée et vie professionnelle et le niveau de confiance des individus dans le cloud. Nous utilisons un modèle afin de pouvoir décrire les relations existantes. Enfin, la dernière partie concerne les performances et les connaissances. Nous étudions l’impact du cloud sur les performances des individus en nous concentrant sur des éléments comme le niveau de stress, de soutien, la gestion des connaissances et d’autres. Nous remarquons à la suite d’un questionnaire exécuté par 290 répondants que le cloud est encore méconnu et que seuls 122 répondants utilisent le cloud dans le cadre de leurs activités professionnelles. Sur nos huit hypothèses relatives à l’explication du niveau de stress attribué au cloud, 6 sont significatives. Le niveau de support et d’éducation, l’âge et la fréquence d’utilisation font partie de notre modèle. En ce qui concerne l’explication de l’équilibre entre vie privée et vie professionnelle, nous remarquons qu’une seule de nos hypothèses est retenue. Elle met en avant que la responsabilité du cloud dans la fréquence de prestations d’heures supplémentaires non-rémunérées affecte notre variable dépendante. Aucune de nos hypothèses tâchant d’expliquer le niveau de confiance n’est vérifiée. Nous avons formulé six hypothèses relatives à l’explication de la variation de la performance due au cloud. Nous remarquons que deux d’entre elles sont significatives. Il s’agit du rôle de la responsabilité du cloud dans le niveau de stress et le désir d’acquérir de nouvelles connaissances. Nous finissons ce mémoire par les limites de nos modèles, de la revue de la littérature et des données récoltées. Master [120] en ingénieur de gestion (Mons), Université catholique de Louvain, 2017

In graph analysis, the Shortest Path problem identifies the optimal, most cost effective, path between two nodes. This problem has been the object of many studies and extensions in heterogeneous domains such as: speech recognition, social network analysis, biological sequence alignment, path planning, or zero-sum games among others. Although the shortest path focuses on the optimal cost of reaching a destination node, it does not take into account other useful information contained on the graph, such as the degree of connectivity of two nodes. On the other hand, measures taking connectivity information into account have their own drawbacks, specially when graphs become large. A new family of distances which interpolates between both extremes is introduced by the Randomized Shortest Path (RSP) framework. By spreading randomization through a graph, the RSP leads to applications where some degree of randomness would be desired. Through this work, we try to investigate whether the RSP framework can be applied to different domains in which randomization is useful, and either solve an existing problem with a new approach, or prove to outperform existing methods. (FSA - Sciences de l'ingénieur) -- UCL, 2015

In this thesis, we mainly consider two closely related classical and general problems in data mining and machine learning: (1) developing new similarity measures between graphs and between nodes of a graph, and (2) developing new density measures on nodes of a graph. In the first part of this thesis, we introduce three new graph kernels (which can be seen as similarity measures between graphs) and assess them on a graph classification task: using molecules from various origins as graphs, we try to classify them according to one of their property (mutagenicity,...). We then study the problem of quantifying the similarity between nodes of graphs. We define three new measures by assigning the forests present in the graph a probability of being sampled at random, favoring small (low-cost) forests against bigger ones. These measures are then assessed on a semi-supervised classification task, trying to infer missing node labels from the ones already present in the test datasets. From these similarity measures, we developed the Sum-over-Forests (SoF) density index presuming that, when picking forests (which are assigned a probability of sampling), if a node is present in many (preferably short) forests, it should lie in a dense region of the graph. This density index is then assessed in various ways, assessing its quality as a density estimator on graphs. At last, we developed two clustering algorithms based on the SoF density index, which are able to work directly on graphs without necessarily requiring a priori the number of clusters. Notre recherche doctorale s’intéresse principalement à deux problèmes étroitement liés, dans les domaines de l’analyse de données et de l’apprentissage automatique: (1) le développement de nouvelles mesures de similarité entre graphes et entre nœuds d’un graphe, et (2) le développement de nouvelles mesures de densité sur les nœuds d’un graphe. Dans la première partie de ce document, trois nouveaux noyaux sur graphes, pouvant être considérés comme des mesures de similarité entre graphes, sont introduits. Ces noyaux sont évalués sur une tâche de classification dont l’objectif est de classer des molécules d’origines diverses, modélisées sous forme de graphes, suivant une de leurs propriétés (mutagénicité,…). Dans notre recherche sur la quantification de la similarité entre nœuds d’un graphe, trois nouvelles mesures ont été définies en assignant aux forêts présentes dans le graphe une probabilité d’être choisies au hasard, favorisant les petites forêts (ayant un coût faible) au détriment des plus étendues. Ces mesures sont ensuite évaluées sur une tâche de classification semi-supervisée dont l’objectif est de prédire les étiquettes manquant sur certains nœuds à partir de celles attachées aux autres nœuds. De ces mesures de similarité, un indice de densité d’un nœud d’un graphe, appelé « Sum-over-Forests » (SoF), a été développé en supposant qu’un nœud présent sur beaucoup de forêts (de préférence petites – et donc avec une plus forte probabilité d’être choisies au hasard) devrait être situé dans une région dense du graphe. Cet indice de densité est ensuite testé de différentes manières, évaluant sa qualité en tant qu’estimateur de densité sur graphes. Enfin, deux méthodes de clustering de nœuds, basées sur l’indice de densité SoF, pouvant être appliquées directement sur des graphes et ne nécessitant pas a priori le nombre de clusters à obtenir, ont été mises au point. (ECGE - Sciences économiques et de gestion) -- UCL, 2014