Search

International audience; Graph clustering is one of the key techniques to understand structures that are presented in networks. In addition to clusters, bridges and outliers detection is also a critical task as it plays an important role in the analysis of networks. Recently, several graph clustering methods are developed and used in multiple application domains such as biological network analysis, recommendation systems and community detection. Most of these algorithms are based on the structural clustering algorithm. Yet, this kind of algorithm is based on the structural similarity. This latter requires to parse all graph’ edges in order to compute the structural similarity. However, the height needs of similarity computing make this algorithm more adequate for small graphs, without significant support to deal with large-scale networks. In this paper, we propose a novel distributed graph clustering algorithm based on structural graph clustering. The experimental results show the efficiency in terms of running time of the proposed algorithm in large networks compared to existing structural graph clustering methods.

Knowledge discovery data (KDD) is a research theme evolving to exploit a large data set collected every day from various fields of computing applications. The underlying idea is to extract hidden knowledge from a data set. It includes several tasks that form a process, such as data mining. Classification and clustering are data mining techniques. Several approaches were proposed in classification such as induction of decision trees, Bayes net, support vector machine, and formal concept analysis (FCA). The choice of FCA could be explained by its ability to extract hidden knowledge. Recently, researchers have been interested in the ensemble methods (sequential/parallel) to combine a set of classifiers. The combination of classifiers is made by a vote technique. There has been little focus on FCA in the context of ensemble learning. This paper presents a new approach to building a single part of the lattice with best possible concepts. This approach is based on parallel ensemble learning. It improves the state-of-the-art methods based on FCA since it handles more voluminous data.

Knowledge discovery in databases (KDD) aims to exploit the large amounts of data collected every day in various fields of computing application. The idea is to extract hidden knowledge from a set of data. It gathers several tasks that constitute a process, such as: data selection, pre-processing, transformation, data mining, visualization, etc. Data mining techniques include supervised classification and unsupervised classification. Classification consists of predicting the class of new instances with a classifier built on learning data of labeled instances. Several approaches were proposed such as: the induction of decision trees, Bayes, nearest neighbor search, neural networks, support vector machines, and formal concept analysis. Learning formal concepts always refers to the mathematical structure of concept lattice. This article presents a state of the art on formal concept analysis classifier. The authors present different ways to calculate the closure operators from nominal data and also present new approach to build only a part of the lattice including the best concepts. This approach is based on Dagging (ensemble method) that generates an ensemble of classifiers, each one represents a formal concept, and combines them by a voting rule. Experimental results are given to prove the efficiency of the proposed method.

Studying protein structures is a major asset for understanding the molecular mechanisms of life. The number of publicly available protein structures has increasingly become extremely large. Yet, the classification of a protein structure remains a difficult, costly, and time-consuming task. Exploring spatial information on protein structures can provide important functional and structural insights. In this context, spatial motifs may correspond to relevant fragments, which might be very useful for a better understanding of proteins. In this article, we propose AntMot, a fast algorithm, to find spatial motifs from protein three-dimensional structures by extending the Karp-Miller-Rosenberg repetition finder, originally dedicated to sequences. The extracted motifs, termed ant-motifs, follow an ant-like shape that is composed of a backbone fragment from the primary structure, enriched with spatial refinements. We show that these motifs are biologically sound, and we used them as descriptors in the classification of several benchmark datasets. Experimental results show that our approach presents a trade-off between sequential motifs and subgraph motifs in terms of the number of extracted substructures, while providing a significant enhancement in the classification accuracy over sequential and frequent-subgraph motifs as well as alignment-based approaches.

International audience; Classification is a data mining task and which is a two-phase process: learning and classification. The learning phase consists of constructing a classifier or a model from a labeled set of objects. The classification phase consists classifying new objects by using the generated classifier. Different approaches have been proposed for supervised classification problems through Formal Concept Analysis, and which is a mathematical theory to build upon hierarchies of formal concepts. The proposed approaches in literature rely on the use of single classifier and ensemble methods. Single classifier methods vary between them according to different criteria especially the number of formal concepts generated. We distinguish overall complete lattice methods, sub-lattice methods and concept cover methods. Methods based on ensemble classifiers rely on the use of many classifiers. Among these methods, there are methods based on sequential training and methods based on parallel training. However, with the large volume of data generated from various sources, the process of knowledge extraction with traditional methods becomes difficult. That’s why new methods based on distributed classifier have recently appeared. In this paper, we present a survey of many FCA-based approaches for classification by dividing them into methods based on a mono-classifier, methods based on ensemble classifiers and methods based on distributed classifiers. Different methods are presented and compared within this paper.

The high dimension of data makes difficult to train and test many classification methods. This work aims to present a new filter Feature Selection Method, called H-Ratio, which can identify pertinent features from data. This method improves results of two previous works focusing on nominal classifiers based on Formals Concepts Analysis. The evaluation of H-Ratio shows that this method performs nominal classifiers processing. Our method has an error rate of 5% (~7% relative improvement over a supervised classification method).

Graph clustering is one of the key techniques to understand the structures present in the graph data. In addition to cluster detection, the identification of hubs and outliers is also a critical task as it plays an important role in the understanding of graph data. Recently, several graph clustering algorithms have been proposed and used in many application domains such as biological network analysis, recommendation systems and community detection. Most of these algorithms are based on structural clustering. Yet, these algorithms have been evaluated on small graph database. In this paper, we propose DSCAN, a novel distributed structural graph clustering algorithm. We present an implementation of DSCAN on top of BLADYG, a distributed graph processing framework. We experimentally show that DSCAN significantly outperforms existing clustering algorithm in terms of scalability and performance in the case of large graphs.

In Multiple Instance Learning (MIL) problem for sequence data, the instances inside the bags are sequences. In some real world applications such as bioinformatics, comparing a random couple of sequences makes no sense. In fact, each instance may have structural and/or functional relations with instances of other bags. Thus, the classification task should take into account this across bag relation. In this work, we present two novel MIL approaches for sequence data classification named ABClass and ABSim. ABClass extracts motifs from related instances and use them to encode sequences. A discriminative classifier is then applied to compute a partial classification result for each set of related sequences. ABSim uses a similarity measure to discriminate the related instances and to compute a scores matrix. For both approaches, an aggregation method is applied in order to generate the final classification result. We applied both approaches to solve the problem of bacterial Ionizing Radiation Resistance prediction. The experimental results of the presented approaches are satisfactory.

Recently, increasingly large amounts of data are generated from a variety of sources.Existing data processing technologies are not suitable to cope with the huge amounts of generated data. Yet, many research works focus on Big Data, a buzzword referring to the processing of massive volumes of (unstructured) data. Recently proposed frameworks for Big Data applications help to store, analyze and process the data. In this paper, we discuss the challenges of Big Data and we survey existing Big Data frameworks. We also present an experimental evaluation and a comparative study of the most popular Big Data frameworks with several representative batch and iterative workloads. This survey is concluded with a presentation of best practices related to the use of studied frameworks in several application domains such as machine learning, graph processing and real-world applications.

Recently, graph mining approaches have become very popular, especially in certain domains such as bioinformatics, chemoinformatics and social networks. One of the most challenging tasks is frequent subgraph discovery. This task has been highly motivated by the tremendously increasing size of existing graph databases. Due to this fact, there is an urgent need of efficient and scaling approaches for frequent subgraph discovery. In this paper, we propose a novel approach for large-scale subgraph mining by means of a density-based partitioning technique, using the MapReduce framework. Our partitioning aims to balance computational load on a collection of machines. We experimentally show that our approach decreases significantly the execution time and scales the subgraph discovery process to large graph databases.

Supervised classification is a spot/task of data mining which consist on building a classifier from a set of instances labeled with their class (learning step) and then predicting the class of new instances with a classifier (classification step). In supervised classification, several approaches were proposed such as: Induction of Decision Tree and Formal Concept Analysis. The learning of formal concepts is generally based on the mathematical structure of Galois lattice (or concept lattice). The complexity of Galois lattice generation limits the application fields of these systems. In this paper, we discuss about supervised classification based on Formal Concept Analysis and we present methods based on concept lattice or sub lattice. We propose a new approach that builds only a part of the lattice, including the best concepts (i.e pertinent concepts). These concepts are used as classifiers in parallel combination using voting rule. The proposed method is based on Dagging of Nominal Classifier. Experimental results are given to prove the interest of the proposed method.

Biological macromolecules, i.e. DNA, RNA and proteins, are coded by strings, called primary structures. During the last decades, the number and the complexity of primary structures are growing exponentially. Analyzing this huge volume of data to extract pertinent knowledge is a challenging task. Data mining approaches can be helpful to reach this goal. In this paper, we present a new data mining approach, called Disclass, based on vote strategies to do classification of primary structures: Let f1,f2,...,fn be families that represent, respectively, n samples of n sets S1,S2,...,Sn of primary structures. Let us consider now a new primary structure w that is assumed to belong to one of the n sets S1,S2,...,Sn. By using our data mining approach Disclass, the decision to assign the new primary structure w to one of the sets S1,S2,...,Sn is taken as follows: (i) During the first step, for each family fi, 1≤i≤n, we construct the ambiguously discriminant and minimal substrings (ADMS) associated with this family. Because the family fi, 1≤i≤n, is a sample of the set Si, the obtained ADMS are considered also to be associated with the whole set Si. During the classification process, the ADMS associated with the set Si, that are approximate substrings of the new primary structure w, will vote with weighted voices for the set Si. (ii) During the second step, we compute according to a vote strategy, the voice weights of the different ADMS, constructed during the first step. (iii) Finally, during the last step, the set that has the maximum weight of voices is the set to which we assign the new primary structure w.

In many real-world learning problems the data flows continuously and learning algorithms should be able to respond to this circumstance: the induced concept description should gradually change over time. In this paper, we outline some existing incremental learners based on the theory of Formal Concept Analysis: FCA. Then, we introduce a new learning approach that improves incremental concept formation. This approach has the advantage of handling both the problem of data addition, data deletion, data update, attribute addition and attribute deletion. Finally, we apply the proposed approach to the problem of cancer diagnosis. We measure the effect of incrementality on the quality of the discovered rules using cross-validation.

An encoding method has a direct effect on the quality and the representation of the discovered knowledge in data mining systems. Biological macromolecules are encoded by strings of characters, called primary structures. Knowing that data mining systems usually use relational tables to encode data, we have then to reencode these strings and transform them into relational tables. In this paper, we do a comparative study of the existing static encoding methods, that are based on the Biologist know-how, and our new dynamic encoding one, that is based on the construction of Discriminant and Minimal Substrings(DMS). Different classification methods are used to do this study. The experimental results show that our dynamic encoding method is more efficient than the static ones, to encode biological macromolecules within a data mining perspective.