CEVCLUS: evidential clustering with instance-level constraints for relational data

Recent advances in clustering consider incorporating background knowledge in the partitioning algorithm, using, e.g., pairwise constraints between objects. As a matter of fact, prior information, when available, often makes it possible to better retrieve meaningful clusters in data. Here, this approach is investigated in the framework of belief functions, which allows us to handle the imprecision and the uncertainty of the clustering process. In this context, the EVCLUS algorithm was proposed for partitioning objects described by a dissimilarity matrix. It is extended here so as to take pairwise constraints into account, by adding a term to its objective function. This term corresponds to a penalty term that expresses pairwise constraints in the belief function framework. Various synthetic and real datasets are considered to demonstrate the interest of the proposed method, called CEVCLUS, and two applications are presented. The performances of CEVCLUS are also compared to those of other constrained clustering algorithms.     

Modelling and predicting partial orders from pairwise belief functions

In this paper, we introduce a generic way to represent and manipulate pairwise information about partial orders (representing rankings, preferences, ...) with belief functions. We provide generic and practical tools to make inferences from this pairwise information and illustrate their use on the machine learning problems that are label ranking and multi-label prediction. Our approach differs from most other quantitative approaches handling complete or partial orders, in the sense that partial orders are here considered as primary objects and not as incomplete specifications of ideal but unknown complete orders.     

Classification using belief functions: relationship between case-based and model-based approaches.

The transferable belief model (TBM) is a model to represent quantified uncertainties based on belief functions, unrelated to any underlying probability model. In this framework, two main approaches to pattern classification have been developed: the TBM model-based classifier, relying on the general Bayesian theorem (GBT), and the TBM case-based classifier, built on the concept of similarity of a pattern to be classified with training patterns. Until now, these two methods seemed unrelated, and their connection with standard classification methods was unclear. This paper shows that both methods actually proceed from the same underlying principle, i.e., the GBT, and that they essentially differ by the nature of the assumed available information. This paper also shows that both methods collapse to a kernel rule in the case of precise and categorical learning data and for certain initial assumptions, and a simple relationship between basic belief assignments produced by the two methods is exhibited in a special case. These results shed new light on the issues of classification and supervised learning in the TBM. They also suggest new research directions and may help users in selecting the most appropriate method for each particular application, depending on the nature of the information at hand.     

An evidence-theoretic k-NN rule with parameter optimization

The paper presents a learning procedure for optimizing the parameters in the evidence-theoretic k-nearest neighbor rule, a pattern classification method based on the Dempster-Shafer theory of belief functions. In this approach, each neighbor of a pattern to be classified is considered as an item of evidence supporting certain hypotheses concerning the class membership of that pattern. Based on this evidence, basic belief masses are assigned to each subset of the set of classes. Such masses are obtained for each of the k-nearest neighbors of the pattern under consideration and aggregated using Dempster's rule of combination. In many situations, this method was found experimentally to yield lower error rates than other methods using the same information. However, the problem of tuning the parameters of the classification rule was so far unresolved. The authors determine optimal or near-optimal parameter values from the data by minimizing an error function. This refinement of the original method is shown experimentally to result in substantial improvement of classification accuracy     

Risk assessment based on weak information using belief functions: a case study in water treatment

Whereas probability theory has been very successful as a conceptual framework for risk analysis in many areas where a lot of experimental data and expert knowledge are available, it presents certain limitations in applications where only weak information can be obtained. One such application investigated in this paper is water treatment, a domain in which key information such as input water characteristics and failure rates of various chemical processes is often lacking. An approach to handle such problems is proposed, based on the Dempster-Shafer theory of belief functions. Belief functions are used to describe expert knowledge of treatment process efficiency, failure rates, and latency times, as well as statistical data regarding input water quality. Evidential reasoning provides mechanisms to combine this information and assess the plausibility of various noncompliance scenarios. This methodology is shown to boil down to the probabilistic one where data of sufficient quality are available. This case study shows that belief function theory may be considered as a valuable framework for risk analysis studies in ill-structured or poorly informed application domains.     

Energy-Efficient Operation of Water Systems through Optimization of Load Power Reduction in Electricity Markets

Demand response (DR) is gaining more and more importance in the architecture of power systems in a context of flexible loads and high share of intermittent generation. Changes in electricity markets regulation in several countries have recently enabled an effective integration of DR mechanisms in power systems. Through its flexible components (pumps, tanks), drinking water systems are suitable candidates for energy-efficient DR mechanisms. However, these systems are often managed independently of power system operation for both economic and operational reasons. Indeed, a sufficient level of economic viability and water demands risk management are necessary for water utilities to integrate their flexibilities to power system operation. In this paper, we proposed a mathematical model for optimizing pump schedules in water systems while trading DR blocs in a spot power market during peak times. Uncertainties about water demands were considered in the mathematical model allowing to propose power reductions covering the potential risk of real-time water demand forecasting inaccuracy. Numerical results were discussed on a real water system in France, demonstrating both economic and ecological benefits.     

Principal component analysis of fuzzy data using autoassociative neural networks

This paper describes an extension of principal component analysis (PCA) allowing the extraction of a limited number of relevant features from high-dimensional fuzzy data. Our approach exploits the ability of linear autoassociative neural networks to perform information compression in just the same way as PCA, without explicit matrix diagonalization. Fuzzy input values are propagated through the network using fuzzy arithmetics, and the weights are adjusted to minimize a suitable error criterion, the inputs being taken as target outputs. The concept of correlation coefficient is extended to fuzzy numbers, allowing the interpretation of the new features in terms of the original variables. Experiments with artificial and real sensory evaluation data demonstrate the ability of our method to provide concise representations of complex fuzzy data.     

EVCLUS: evidential clustering of proximity data

A new relational clustering method is introduced, based on the Dempster-Shafer theory of belief functions (or evidence theory). Given a matrix of dissimilarities between n objects, this method, referred to as evidential clustering (EVCLUS), assigns a basic belief assignment (or mass function) to each object in such a way that the degree of conflict between the masses given to any two objects reflects their dissimilarity. A notion of credal partition is introduced, which subsumes those of hard, fuzzy, and possibilistic partitions, allowing to gain deeper insight into the structure of the data. Experiments with several sets of real data demonstrate the good performances of the proposed method as compared with several state-of-the-art relational clustering techniques.