Inference in possibilistic network classifiers under uncertain observations

Possibilistic networks, which are compact representations of possibility distributions, are powerful tools for representing and reasoning with uncertain and incomplete information in the framework of possibility theory. They are like Bayesian networks but lie on possibility theory to deal with uncertainty, imprecision and incompleteness. While classification is a very useful task in many real world applications, possibilistic network-based classification issues are not well investigated in general and possibilistic-based classification inference with uncertain observations in particular. In this paper, we address on one hand the theoretical foundations of inference in possibilistic classifiers under uncertain inputs and propose on the other hand a novel efficient algorithm for the inference in possibilistic network-based classification under uncertain observations. We start by studying and analyzing the counterpart of Jeffrey’s rule in the framework of possibility theory. After that, we address the validity of Markov-blanket criterion in the context of possibilistic networks used for classification with uncertain inputs purposes. Finally, we propose a novel algorithm suitable for possibilistic classifiers with uncertain observations without assuming any independence relations between observations. This algorithm guarantees the same results as if classification were performed using the possibilistic counterpart of Jeffrey’s rule. Classification is achieved in polynomial time if the target variable is binary. The basic idea of our algorithm is to only search for totally plausible class instances through a series of equivalent and polynomial transformations applied on the possibilistic classifier taking into account the uncertain observations.     

Interventions and belief change in possibilistic graphical models

Causality and belief change play an important role in many applications. This paper focuses on the main issues of causality and interventions in possibilistic graphical models. We show that interventions, which are very useful for representing causal relations between events, can be naturally viewed as a belief change process. In particular, interventions can be handled using a possibilistic counterpart of Jeffrey's rule of conditioning under uncertain inputs. This paper also addresses new issues that are arisen in the revision of graphical models when handling interventions. We first argue that the order in which observations and interventions are introduced is very important. Then we show that in order to correctly handle sequences of observations and interventions, one needs to change the structure of possibilistic networks. Lastly, an efficient procedure for revising possibilistic causal trees is provided.     

An Approximate Algorithm for Min‐Based Possibilistic Networks

Min‐based (or qualitative) possibilistic networks are important tools to efficiently and compactly represent and analyze uncertain information. Inference is a crucial task in min‐based networks, which consists of propagating information through the network structure to answer queries. Exact inference computes posteriori possibility distributions, given some observed evidence, in a time proportional to the number of nodes of the network when it is simply connected (without loops). On multiply connected networks (with loops), exact inference is known as a hard problem. This paper proposes an approximate algorithm for inference in min‐based possibilistic networks. More precisely, we adapt the well‐known approximate algorithm Loopy Belief Propagation (LBP) on qualitative possibilistic networks. We provide different experimental results that analyze the convergence of possibilistic LBP.     

Tree-Based Credal Networks for Classification

Bayesian networks are models for uncertain reasoning which are achieving a growing importance also for the data mining task of classification. Credal networks extend Bayesian nets to sets of distributions, or credal sets. This paper extends a state-of-the-art Bayesian net for classification, called tree-augmented naive Bayes classifier, to credal sets originated from probability intervals. This extension is a basis to address the fundamental problem of prior ignorance about the distribution that generates the data, which is a commonplace in data mining applications. This issue is often neglected, but addressing it properly is a key to ultimately draw reliable conclusions from the inferred models. In this paper we formalize the new model, develop an exact linear-time classification algorithm, and evaluate the credal net-based classifier on a number of real data sets. The empirical analysis shows that the new classifier is good and reliable, and raises a problem of excessive caution that is discussed in the paper. Overall, given the favorable trade-off between expressiveness and efficient computation, the newly proposed classifier appears to be a good candidate for the wide-scale application of reliable classifiers based on credal networks, to real and complex tasks.     

Dual models for possibilistic regression analysis

Upper and lower regression models (dual possibilistic models) are proposed for data analysis with crisp inputs and interval or fuzzy outputs. Based on the given data, the dual possibilistic models can be derived from upper and lower directions, respectively, where the inclusion relationship between these two models holds. Thus, the inherent uncertainty existing in the given phenomenon can be approximated by the dual models. As a core part of possibilistic regression, firstly possibilistic regression for crisp inputs and interval outputs is considered where the basic dual linear models based on linear programming, dual nonlinear models based on linear programming and dual nonlinear models based on quadratic programming are systematically addressed, and similarities between dual possibilistic regression models and rough sets are analyzed in depth. Then, as a natural extension, dual possibilistic regression models for crisp inputs and fuzzy outputs are addressed.     

Distributed classification of acoustic targets in wireless audio-sensor networks

Target tracking is an important application for wireless sensor networks. One important aspect of tracking is target classification. Classification helps in selecting particular target(s) of interest. In this paper, we address the problem of classification of moving ground vehicles. The basis of classification are the audible signals produced by these vehicles. We present a distributed framework to classify vehicles based on features extracted from acoustic signals of vehicles. The main features used in our study are based on FFT (fast Fourier transform) and PSD (power spectral density). We propose three distributed algorithms for classification that are based on the k-nearest neighbor (k-NN) classification method. An experimental study has been conducted using real acoustic signals of different vehicles recorded in the city of Edmonton. We compare our proposed algorithms with a naive distributed implementation of the k-NN algorithm. Performance results reveal that our proposed algorithms are energy efficient, and thus suitable for sensor network deployment.     

Jeffrey’s rule of conditioning in a possibilistic framework

Conditioning, belief update and revision are important tasks for designing intelligent systems. Possibility theory is among the powerful uncertainty theories particularly suitable for representing and reasoning with uncertain and incomplete information. This paper addresses an important issue related to the possibilistic counterparts of Jeffrey’s rule of conditioning. More precisely, it addresses the existence and uniqueness of the solutions computed using the possibilistic counterparts of the so-called kinematics properties underlying Jeffrey’s rule of conditioning. We first point out that like the probabilistic framework, in the quantitative possibilistic setting, there exists a unique solution for revising a possibility distribution given the uncertainty bearing on a set of exhaustive and mutually exclusive events. However, in the qualitative possibilistic framework, the situation is different. In particular, the application of Jeffrey’s rule of conditioning does not guarantee the existence of a solution. We provide precise conditions where the uniqueness of the revised possibility distribution exists.     

Fusion and normalization of quantitative possibilistic networks

The problem of merging multiple-source uncertain information is a crucial issue in many applications. This paper proposes an analysis of possibilistic merging operators where uncertain information is encoded by means of product-based (or quantitative) possibilistic networks. We first show that the product-based merging of possibilistic networks having the same DAG structures can be easily achieved in a polynomial time. We then propose solutions to merge possibilistic networks having different structures and where the union of their graphs is free of cycles. Then we show how to deal with merged networks having cycles. Lastly, we handle the sub-normalization problem which reflects the presence of conflicts between different sources.     

A possibilistic clustering approach to novel fault detection and isolation

In this paper, a new approach for fault detection and isolation that is based on the possibilistic clustering algorithm is proposed. Fault detection and isolation (FDI) is shown here to be a pattern classification problem, which can be solved using clustering and classification techniques. A possibilistic clustering based approach is proposed here to address some of the shortcomings of the fuzzy c-means (FCM) algorithm. The probabilistic constraint imposed on the membership value in the FCM algorithm is relaxed in the possibilistic clustering algorithm. Because of this relaxation, the possibilistic approach is shown in this paper to give more consistent results in the context of the FDI tasks. The possibilistic clustering approach has also been used to detect novel fault scenarios, for which the data was not available while training. Fault signatures that change as a function of the fault intensities are represented as fault lines, which have been shown to be useful to classify faults that can manifest with different intensities. The proposed approach has been validated here through simulations involving a benchmark quadruple tank process and also through experimental case studies on the same setup. For large scale systems, it is proposed to use the possibilistic clustering based approach in the lower dimensional approximations generated by algorithms such as PCA. Towards this end, finally, we also demonstrate the key merits of the algorithm for plant wide monitoring study using a simulation of the benchmark Tennessee Eastman problem.     

Possibilistic mean-variance models and efficient frontiers for portfolio selection problem

In this paper, it is assumed that the rates of return on assets can be expressed by possibility distributions rather than probability distributions. We propose two kinds of portfolio selection models based on lower and upper possibilistic means and possibilistic variances, respectively, and introduce the notions of lower and upper possibilistic efficient portfolios. We also present an algorithm which can derive the explicit expression of the possibilistic efficient frontier for the possibilistic mean-variance portfolio selection problem dealing with lower bounds on asset holdings.     

一种Web用户访问路径的可能性模糊聚类算法

结合Web用户访问特点,针对Web用户访问路径聚类分析中普遍存在的对象类别不确定性现象进行了研究.结合模糊聚类和可能性聚类的特点,提出来一种新的用户访问路径的可能性模糊聚类算法.新方法通过定义相关的截集,自动地将对象分配到若干簇中,避免了人工干预,实现了交叉聚类的目的.新方法建立在leader聚类算法的框架上,只需要扫描数据集一遍使得算法效率大大提高.在标准数据集上的对比试验表明新算法不仅是有效的,而且效率较高.     

Learning Bayesian classifiers from positive and unlabeled examples

The positive unlabeled learning term refers to the binary classification problem in the absence of negative examples. When only positive and unlabeled instances are available, semi-supervised classification algorithms cannot be directly applied, and thus new algorithms are required. One of these positive unlabeled learning algorithms is the positive naive Bayes (PNB), which is an adaptation of the naive Bayes induction algorithm that does not require negative instances. In this work we propose two ways of enhancing this algorithm. On one hand, we have taken the concept behind PNB one step further, proposing a procedure to build more complex Bayesian classifiers in the absence of negative instances. We present a new algorithm (named positive tree augmented naive Bayes, PTAN) to obtain tree augmented naive Bayes models in the positive unlabeled domain. On the other hand, we propose a new Bayesian approach to deal with the a priori probability of the positive class that models the uncertainty over this parameter by means of a Beta distribution. This approach is applied to both PNB and PTAN, resulting in two new algorithms. The four algorithms are empirically compared in positive unlabeled learning problems based on real and synthetic databases. The results obtained in these comparisons suggest that, when the predicting variables are not conditionally independent given the class, the extension of PNB to more complex networks increases the classification performance. They also show that our Bayesian approach to the a priori probability of the positive class can improve the results obtained by PNB and PTAN.     

Kernel approach to possibilistic C‐means clustering

Kernel approaches can improve the performance of conventional clustering or classification algorithms for complex distributed data. This is achieved by using a kernel function, which is defined as the inner product of two values obtained by a transformation function. In doing so, this allows algorithms to operate in a higher dimensional space (i.e., more degrees of freedom for data to be meaningfully partitioned) without having to compute the transformation. As a result, the fuzzy kernel C‐means (FKCM) algorithm, which uses a distance measure between patterns and cluster prototypes based on a kernel function, can obtain more desirable clustering results than fuzzy C‐means (FCM) for not only spherical data but also nonspherical data. However, it can still be sensitive to noise as in the FCM algorithm. In this paper, to improve the drawback of FKCM, we propose a kernel possibilistic C‐means (KPCM) algorithm that applies the kernel approach to the possibilistic C‐means (PCM) algorithm. The method includes a variance updating method for Gaussian kernels for each clustering iteration. Several experimental results show that the proposed algorithm can outperform other algorithms for general data with additive noise. © 2009 Wiley Periodicals, Inc.     

Learning naive Bayes classifiers from positive and unlabelled examples with uncertainty

Traditional classification algorithms require a large number of labelled examples from all the predefined classes, which is generally difficult and time-consuming to obtain. Furthermore, data uncertainty is prevalent in many real-world applications, such as sensor network, market analysis and medical diagnosis. In this article, we explore the issue of classification on uncertain data when only positive and unlabelled examples are available. We propose an algorithm to build naive Bayes classifier from positive and unlabelled examples with uncertainty. However, the algorithm requires the prior probability of positive class, and it is generally difficult for the user to provide this parameter in practice. Two approaches are proposed to avoid this user-specified parameter. One approach is to use a validation set to search for an appropriate value for this parameter, and the other is to estimate it directly. Our extensive experiments show that the two approaches can basically achieve satisfactory classification performance on uncertain data. In addition, our algorithm exploiting uncertainty in the dataset can potentially achieve better classification performance comparing to traditional naive Bayes which ignores uncertainty when handling uncertain data.     

模糊支持张量机图像分类算法及其应用

针对在小样本图像分类应用中,以向量空间作为输入的传统分类算法的不足,提出以张量理论为基础,结合模糊支持向量机思想的基于张量图像样本的模糊支持张量机分类器,利用张量表示图像样本,求解最优张量面。通过手写体数字图像样本实验仿真,验证该算法的性能,随后将其应用到羽绒菱节图像识别中进行对比,该算法较传统算法平均高出6.3%以上的识别率。实验证明该算法更适合应用于图像样本分类识别。     

Modeling uncertainty reasoning with possibilistic Petri nets

Manipulation of perceptions is a remarkable human capability in a wide variety of physical and mental tasks under fuzzy or uncertain surroundings. Possibilistic reasoning can be treated as a mechanism that mimics human inference mechanisms with uncertain information. Petri nets are a graphical and mathematical modeling tool with powerful modeling and analytical ability. The focus of this paper is on the integration of Petri nets with possibilistic reasoning to reap the benefits of both formalisms. This integration leads to a possibilistic Petri nets model (PPN) with the following features. A possibilistic token carries information to describe an object and its corresponding possibility and necessity measures. Possibilistic transitions are classified into four types: inference transitions, duplication transitions, aggregation transitions, and aggregation-duplication transitions. A reasoning algorithm, based on possibilistic Petri nets, is also presented to improve the efficiency of possibilistic reasoning and an example related to diagnosis of cracks in reinforced concrete structures is used to illustrate the proposed approach.     

结合类内和类间距离的可能聚类分割算法

目的 为了进一步提高噪声图像分割的抗噪性和准确性,提出一种结合类内距离和类间距离的改进可能聚类算法并将其应用于图像分割。方法 该算法避免了传统可能性聚类分割算法中仅仅考虑以样本点到聚类中心的距离作为算法的测度,将类内距离与类间距离相结合作为算法的新测度,即考虑了类内紧密程度又考虑了类间离散程度,以便对不同的聚类结构有较强的稳定性和更好的抗噪能力,并且将直方图融入可能模糊聚类分割算法中提出快速可能模糊聚类分割算法,使其对各种较复杂图像的分割具有即时性。结果 通过人工合成图像和实际遥感图像分割测试结果表明,本文改进可能聚类算法是有效的,其分割轮廓清晰,分类准确且噪声较小,其误分率相比其他算法至少降低了2个百分点,同时能获得更满意的分割效果。结论 针对模糊C-均值聚类分割算法和可能性聚类分割算法对于背景和目标颜色相近的图像分类不准确的缺陷,将类内距离与类间距离相结合作为算法的测度有效的解决了图像分割归类问题,并且结合直方图提出快速可能模糊聚类分割算法使其对于大篇幅复杂图像也具有适用性。     

传感器网络中节点个数约束查询处理算法

对传感器网络中一类新查询--节点个数约束查询,提出能量有效的查询处理算法.算法主要由查询下发和结果回收两部分构成.查询下发算法首先根据节点个数约束查询的特点提出相关节点选择以及基于Steiner树的查询下发算法.然后对该下发算法以及一种基于洪泛的能量有效查询下发算法的能量消耗进行分析,并对比两种算法的能量消耗从中选择适当的下发算法.结果回收算法提出直接和间接两种结果回收方式,并给出两种方式在进行结果回收时能够节省能量的条件.仿真实验表明,提出的能量有效节点个数约束查询处理算法能够在满足用户查询精度的同时,使其能量消耗低于其他查询处理算法.     

基于并行支持向量机的多变量非线性模型预测控制

提出一种基于并行支持向量机的多变量系统非线性模型预测控制算法．首先,通过考虑输入、输出间的耦合,建立基于并行支持向量机的多步预测模型;然后,将该模型用于非线性预测控制,提出新的适用于并行预测模型的反馈校正策略,得到最优控制律．连续搅拌槽式反应器（CSTR）的控制仿真结果表明,该算法的性能优于基于并行神经网络的非线性模型预测控制和基于集成模型的非线性模型预测控制．     

基于用户兴趣的服务资源分类算法

在自治网络中对其所拥有的服务资源,依靠改进朴素贝叶斯分类算法,并且结合中国图书馆分类法进行分类,从而有效地提高基于不同用户兴趣的分类准确率。实验结果表明,与传统的朴素贝叶斯算法相比,该方法具有更好的性能。