Search

The most well-known unsupervised classification algorithms allow for the identification of hard or probabilistic partitions. However, when working with complex datasets such as those found in the healthcare domain, it is important to note that these partitions may have limitations, particularly when considering the uncertainty associated with medical data. Indeed, these algorithms do not account for modeling outliers, imprecise, or uncertain observations. In this study, we focused on analyzing time series of barometers attributes related to pain intensity in individuals with chronic pain. Our goal was to identify different typologies of care trajectories, highlighting distinct trajectories of chronic pain through clustering techniques. We propose a soft clustering approach based on feature extraction and selection from sequential data, aiming to improve interpretability and enhance the performance of the clustering procedure. Time series feature extraction and selection effectively handles complex and noisy data, improving interpretability and clustering performance. Evidential soft clustering models data uncertainty and imprecision, providing a better representation of nuances and variations in complex, raw data. The first step involves extracting features from the available time series and selecting the most important attributes. For this purpose, we use a time series feature extractor (Tsfresh) and unsupervised feature selection methods, including unsupervised Random Forest, Laplacian Score, and unsupervised Spectral Feature Selection. The second step involves using the evidential c-means (ECM) clustering algorithm on the extracted attributes. The ECM method, based on belief functions, allows for generating a credal partition that has the ability to model various forms of uncertainty. This partition can then be transformed into a hard partition to study individuals based on this uncertainty criterion. The results reveal the existence of two clusters of chronic pain related to discomfort and well-being, exhibiting excellent separability and compactness. Additionally, an uncertain cluster emerges grouping patients with intermediate characteristics. The interpretability of the determined partitions through descriptive analysis, statistical tests, and repeated measures multinomial regression on clinical and demographic data allowed us to determine the profile of patients in the identified trajectories. • Clustering care pathways for patients with chronic pain. • Patient clusters: pain related to fatigue and stress vs. pain related to sleep, physical comfort and mood. • Evidential c-means clustering models uncertainty in chronic pain time series. • Feature extraction from time series helps manage data complexity, imprecision and noisiness. • Feature selection maintains interpretability and improves clustering. [ABSTRACT FROM AUTHOR]

Due to the use of the quantile function, support vector machines with the pinball loss (PinSVMs) have good properties such as noise insensitivity and stability of re-sampling. In this paper we propose a novel model with the ε -insensitive pinball loss function for uncertain data classification. The original model we propose involves the high-dimensional integral problem. In order to make the optimization model become tractable, we transform the original model into the simplified one by using some techniques. We theoretically analyze some properties of the proposed optimization model including noise insensitivity and scatter minimization. Based on the probability of uncertain samples in the halfspaces, we make a rule to classify uncertain samples. In the proposed model a probabilistic degree of the uncertain sample that belongs to the positive or negative class can be given. In addition, we use the kernel trick to extend the proposed model to deal with nonlinear problems. The experiments on artificial data and real-world data sets are carried out to confirm the effectiveness of the proposed model in handling uncertain data. [ABSTRACT FROM AUTHOR]

The aim of this study is to design a novel machine learning model named Agglomerative Hierarchical Clustering algorithm based on Overlapped Interval Divergence distance measure (AHC-OLID), for modelling and assessing landslide susceptibility. The AHC-OLID algorithm is proposed to combat the limitations of many clustering algorithms in modelling and assessing landslide susceptibility, including: pre-defining the number of clusters; sensitivity to the clusters properties and noisy data; as well as difficulty in processing rainfall data. The proposed algorithm addresses these issues by integrating the traditional Agglomerative Hierarchical Clustering (AHC) and Overlapped Interval Divergence distance measure (OLID) methods into landslide susceptibility assessment to enhance its performance. It considers the clusters sizes as well the distances between them and tends to avoid taking into consideration small clusters which are very far from other clusters in the dataset. It is also insensitive to the variation in sizes, variances and shapes of the clusters, which makes the algorithm more advantageous. Besides, the AHC-OLID algorithm makes use of the OLID distance function to process the rainfall data, which takes two factors into consideration: distance between their centers as well as relative size of their overlapped area. Applying this new approach in Baota District, China, produced significant improvement in assessment of landslide susceptibility than previous models. Moreover, the Landslide susceptibility map constructed based on AHC-OLID algorithm can be a useful tool for landslide controlling strategies for proper land use and planning. [ABSTRACT FROM AUTHOR]

This paper studies the complexity of query evaluation for databases whose relations are partially ordered; the problem commonly arises when combining or transforming ordered data from multiple sources. We focus on queries in a useful fragment of SQL, namely positive relational algebra with aggregates, whose bag semantics we extend to the partially ordered setting. Our semantics leads to the study of two main computational problems: the possibility and certainty of query answers. We show that these problems are respectively NP-complete and coNP-complete, but identify tractable cases depending on the query operators or input partial orders. We further introduce a duplicate elimination operator and study its effect on the complexity results. [ABSTRACT FROM AUTHOR]

Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. Using extremal combinatorics, we then characterize the families of non-redundant possibilistic keys that attain maximum cardinality. In addition, we show how to compute for any given set of possibilistic keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every key in the given set and violates every possibilistic key not implied by the given set. We also establish an algorithm for the discovery of all possibilistic keys that are satisfied by a given possibilistic relation. It is shown that the computational complexity of computing possibilistic Armstrong relations is precisely exponential in the input, and the decision variant of the discovery problem is NP-complete as well as W[2]-complete in the size of the possibilistic key. Further applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. The computation of possibilistic Armstrong relations and discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size of possibilistic Armstrong relations and the time to compute them, as well as the time it takes to compute a cover of the possibilistic keys that hold on a possibilistic relation, and the time it takes to remove any redundant possibilistic keys from this cover. [ABSTRACT FROM AUTHOR]

We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O (1) -approximation running in O (n d + 1 log ⁡ n) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O (n d) -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest. [ABSTRACT FROM AUTHOR]

Driven by the dominance of the relational model, we investigate how the requirements of applications on the certainty of functional dependencies can improve the outcomes of relational database schema design. For that purpose, we assume that tuples are assigned a degree of possibility with which they occur in a relation, and that functional dependencies are assigned a dual degree of certainty which says to which tuples they apply. A design theory is developed for functional dependencies with degrees of certainty, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples bring forward different degrees of data redundancy, caused by functional dependencies with the dual degree of certainty. Variants of the classical syntactic Boyce–Codd and Third Normal Forms are established. They are justified semantically in terms of eliminating data redundancy and update anomalies of given degrees, and minimizing data redundancy of given degrees across all dependency-preserving decompositions, respectively. As a practical outcome of our results, designers can simply fix the degree of certainty they target, and then apply classical decomposition and synthesis to the set of functional dependencies whose associated degree of certainty meets the target. Hence, by fixing the certainty degree a designer controls which integrity requirements will be enforced for the application and which data will be processed by the application. The choice of the certainty degree also balances the classical trade-off between query and update efficiency on future database instances. Our experiments confirm the effectiveness of our control parameter, and provide original insight into classical normalization strategies and their implementations. • Uncertainty in data is modeled by assigning to records a degree of possibility. • Certainty degrees of functional dependencies indicate on which records they hold. • Different degrees of data redundancy can then be defined and observed. • Refined normal forms avoid or minimize data redundancy up to a target degree. • Certainty degrees control classical trade-offs to optimize relational schema design. [ABSTRACT FROM AUTHOR]

In recent decades, frequent pattern mining has become popular in real time computing because it helps users extract meaningful business or technical trends over uncertain data streams. Generally, mainstream frequent pattern mining approaches can accurately explore frequent patterns whether the approaches are used in expected support or probabilistic frequentness mechanisms. However, whichever are implemented, they all have time issues when extracting frequent patterns if there exists a volume of data tuples in each time instance. To explore frequent patterns over uncertain data streams efficiently, we propose a predicted approach for forecasting frequent patterns with hidden Markov models. The model consists of a construction phase and a testing phase. In the former phase, the hidden Markov model is constructed by the history of past data, and in the latter phase, the results of evaluations and adjustments of transition probabilities occur. By constructing models of patterns, frequent patterns can be easily obtained. Experimental results show the proposed approach can save time cost when exploring frequent patterns and provide approximate 72% average accuracy in 50 sequential predictions; thereby, our approach can efficiently and accurately predict frequent patterns over uncertain data streams. [ABSTRACT FROM AUTHOR]

Abstract Uncertainty of data is inherent in many applications, and query processing over uncertain data has gained widespread attention. The probabilistic skyline query is a powerful tool for managing uncertain data. However, the famous probabilistic skyline query, called p -skyline query, is likely to return unattractive objects which have no advantage in either their attributes or skyline probabilities with comparing to other query results. Moreover, it may return too many objects to offer any meaningful insight for customers. In this paper, we first propose a modified p -skyline (MPS) query based on a strong dominance operator to identify truly attractive results. Then we formulate a top k MPS (T k MPS) query on the basis of a new ranking criterion. We present effective approaches for processing the MPS query, and extend these approaches to process the T k MPS query. To improve the query performance, the reuse technique is adopted. Extensive experiments verify that the proposed algorithms for the MPS and T k MPS queries are efficient and effective, our MPS query can filter out 34.44% unattractive objects from the p -skyline query results at most, and although in some cases the results of the MPS and the p -skyline queries are just the same, our MPS query needs much less CPU, I/O, and memory costs. [ABSTRACT FROM AUTHOR]

Abstract In this work, a classification learning algorithm is designed within the framework of support vector machines through modeling uncertain data with additive kernels, which are introduced to calculate the similarity between uncertain samples characterized by probability density functions (PDFs). The PDFs are used as features of the uncertain samples, where the value of a feature is not a single value, but a set of values that represent the probability distribution of the noise. This is different with the existing methods which represent an uncertain sample by a set of new samples around it, but use the farthest or nearest value in the distribution to construct the optimal hyperplane. With the properties of kernel functions, we can easily extend additive kernels to compute the similarity between samples described with multiple uncertain features. Furthermore, we introduce an efficient algorithm to compute the kernel functions, and solve the additive kernel SVMs. The experimental results show the efficiency of additive-kernel SVMs in uncertain data classification. [ABSTRACT FROM AUTHOR]

Uncertain data in K means clustering, namely UK means, have been discussed in decade years. UK means clustering, however, has some difficulties of time performance and effectiveness because of the uncertainty of objects. In this study, we propose some modified UK means clustering mechanisms to improve the time performance and effectiveness, and to enable the clustering to be more complete. The main issues include (1) reducing the consideration of time performance in clustering, (2) increasing the effectiveness of clustering, and (3) considering the determination of the number of clusters. In time performance, we use simplified object expressions to reduce the time spent in comparing similarities. Regarding the effectiveness of clustering, we propose compounded factors including the distance, the overlapping of clusters and objects, and the cluster density as the clustering standard to determine similarity. In addition, to increase the effectiveness of clustering, we also propose the concept of a cluster boundary, which affects the belongingness of an object by the overlapping factor. Finally, we use the evaluating approach of the number of uncertain clusters to determine the appropriate the number of clusters. In the experiment, clustering results generated using strategies commonly used in processing uncertain data clustering in UK means clusters are compared. Our proposed model shows more favorable performance, higher effectiveness of clustering, and a more appropriate number of clusters compared to other models. [ABSTRACT FROM AUTHOR]

Possible world has shown to be effective for handling various types of data uncertainty in uncertain data management. However, few uncertain data clustering and classification algorithms are proposed based on possible world. Moreover, existing possible world based algorithms suffer from the following issues: (1) they deal with each possible world independently and ignore the consistency principle across different possible worlds; (2) they require the extra post-processing procedure to obtain the final result, which causes that the effectiveness highly relies on the post-processing method and the efficiency is also not very good. In this paper, we propose a novel possible world based consistency learning model for uncertain data, which can be extended both for clustering and classifying uncertain data. This model utilizes the consistency principle to learn a consensus affinity matrix for uncertain data, which can make full use of the information across different possible worlds and then improve the clustering and classification performance. Meanwhile, this model imposes a new rank constraint on the Laplacian matrix of the consensus affinity matrix, thereby ensuring that the number of connected components in the consensus affinity matrix is exactly equal to the number of classes. This also means that the clustering and classification results can be directly obtained without any post-processing procedure. Furthermore, for the clustering and classification tasks, we respectively derive the efficient optimization methods to solve the proposed model. Experimental results on real benchmark datasets and real world uncertain datasets show that the proposed model outperforms the state-of-the-art uncertain data clustering and classification algorithms in effectiveness and performs competitively in efficiency. [ABSTRACT FROM AUTHOR]

Geostatistical simulation methods have been used to quantify spatial variability of reservoir models since the 80s. In the last two decades, state of the art simulation methods have changed from being based on covariance-based 2-point statistics to multiple-point statistics (MPS), that allow simulation of more realistic Earth-structures. In addition, increasing amounts of geo-information (geophysical, geological, etc.) from multiple sources are being collected. This pose the problem of integration of these different sources of information, such that decisions related to reservoir models can be taken on an as informed base as possible. In principle, though difficult in practice, this can be achieved using computationally expensive Monte Carlo methods. Here we investigate the use of sequential simulation based MPS simulation methods conditional to uncertain (soft) data, as a computational efficient alternative. First, it is demonstrated that current implementations of sequential simulation based on MPS (e.g. SNESIM, ENESIM and Direct Sampling) do not account properly for uncertain conditional information, due to a combination of using only co-located information, and a random simulation path. Then, we suggest two approaches that better account for the available uncertain information. The first make use of a preferential simulation path, where more informed model parameters are visited preferentially to less informed ones. The second approach involves using non co-located uncertain information. For different types of available data, these approaches are demonstrated to produce simulation results similar to those obtained by the general Monte Carlo based approach. These methods allow MPS simulation to condition properly to uncertain (soft) data, and hence provides a computationally attractive approach for integration of information about a reservoir model. [ABSTRACT FROM AUTHOR]

The probabilistic group nearest neighbor(PGNN) query , which returns all the uncertain objects whose probabilities of being the group nearest neighbor (GNN) results exceed a user-specified threshold, is widely used in uncertain database. Most existing work for answering PGNN queries adopted a general framework which consist of three phases: spatial pruning, probabilistic pruning, refinement . In the probabilistic pruning phase, dividing the uncertain regions into many partitions to derive a tighter probabilities bounds is a common method. However, there is a tradeoff between the computational cost of probabilistic pruning phase and refinement phase controlled by the granularity of the partitions. In this paper, we study the problem of setting the optimal granularity of the partitions for uncertain objects, and propose a new framework for PGNN queries based on granularity classification using ELM such that the overall cost is minimized. In addition, to improve the accuracy of classification and make the classifier applicable to the dynamic environment, a plurality voting method and a dynamic classification strategy are proposed respectively. Extensive experiments shows that compared with the default granularities of the partitions, the granularities chosen by ELM classifiers are more proper, which further improves the performance of PGNN query algorithm. In addition, ELM outperforms SVM with regard to both the response time and classification accuracy. [ABSTRACT FROM AUTHOR]

Let N be the line-set and M be the column-set of a matrix { a i j } , such that a i j = 1 if line i ∈ N is covered by column j ∈ M , or a i j = 0 otherwise. Besides, let b j ≥ 0 be the benefit associated with a column j ∈ M . Given a constant T < | M | , the NP-Hard Maximal Covering Location Problem (MCLP) consists in finding a subset X ⊆ M with the maximum sum of benefits, such that | X | ≤ T and every line in N is covered by at least one column in X . In this study, we investigate the min-max regret Maximal Covering Location Problem, a robust counterpart of MCLP, where the benefit of each column is uncertain and modeled as an interval data. The objective is to find a robust solution that minimizes the maximal regret over all possible combinations of values for the columns benefit. This problem has applications in disaster relief. We propose a MILP formulation, an exact and 2-approximation algorithms, and test them using classical instances from the literature. [ABSTRACT FROM AUTHOR]

High volumes of wide varieties of valuable data of different veracity (e.g., imprecise and uncertain data) can be easily generated or collected at a high velocity for various knowledge-based and intelligent information & engineering systems in many real-life situations. Embedded in these big data is valuable knowledge and useful information, which can be discovered by data science solutions. As a popular data science task, frequent pattern mining aims to discover implicit, previously unknown and potentially useful information and valuable knowledge in terms of sets of frequently co-occurring items. Many of the existing frequent pattern mining algorithms use a transaction-centric mining approach to find frequent patterns from precise data. However, there are situations in which an item-centric mining approach is more appropriate, and there are also situations in which data are imprecise and uncertain. In this article, we present an item-centric algorithm for mining frequent patterns from big uncertain data. Evaluation results show the effectiveness of our algorithm in item-centric mining of frequent patterns from big uncertain data. [ABSTRACT FROM AUTHOR]

Quantitative demonstrating of organic frameworks has turned into an essential computational methodology in the configuration of novel and investigation of existing natural frameworks. Be that as it may, active information that portrays the framework's elements should be known keeping in mind the end goal to get pertinent results with the routine displaying strategies. This information is frequently robust or even difficult to get. Here, we exhibit a model of quantitative fuzzy rational demonstrating approach that can adapt to obscure motor information and hence deliver applicable results despite the fact that dynamic information is fragmented or just dubiously characterized. Besides, the methodology can be utilized as a part of the blend with the current cutting edge quantitative demonstrating strategies just in specific parts of the framework, i.e., where the data are absent. The contextual analysis of the methodology suggested in this paper is performed on the model of nine-quality genes. We propose a kind of FPN model in light of fuzzy sets to manage the quantitative modeling of biological systems. The tests of our model appear that the model is practical and entirely powerful for information impersonation and thinking of fuzzy expert frameworks. [ABSTRACT FROM AUTHOR]

Safety is of the utmost importance in the air traffic system. In recent years, data-driven algorithms have emerged to identify anomalous and potentially unsafe operations based on machine learning techniques. Although many algorithms have shown notable progress in anomaly detection, they have hardly considered the fact that data can be corrupted by noise and uncertainty (e.g., navigation system error) can lead to frequent misdetection and false alarms, which could disturb air traffic controllers and result in system performance degradation. Therefore, an accurate and reliable assessment of emerging safety risks that accounts for and alleviates the effect of uncertainty in data is required for safe and efficient airspace operations. To achieve this goal, this paper proposes a conformal prediction-based framework that explicitly examines uncertainty for reliable anomaly detection and learns online from new streaming data. In addition to supporting the monitoring task of air traffic controllers, the proposed method takes one step forward and provides support for the control task, by offering a resolution strategy when anomaly probability violates the predefined threshold. The proposed method is demonstrated with real air traffic data, called automatic dependent surveillance-broadcast data. [ABSTRACT FROM AUTHOR]

Uncertain data has posed a great challenge to traditional clustering algorithms. Recently, several algorithms have been proposed for clustering uncertain data, and among them density-based techniques seem promising for handling data uncertainty. However, some issues like losing uncertain information, high time complexity and nonadaptive threshold have not been addressed well in the previous density-based algorithm FDBSCAN and hierarchical density-based algorithm FOPTICS. In this paper, we firstly propose a novel density-based algorithm PDBSCAN, which improves the previous FDBSCAN from the following aspects: (1) it employs a more accurate method to compute the probability that the distance between two uncertain objects is less than or equal to a boundary value, instead of the sampling-based method in FDBSCAN; (2) it introduces new definitions of probability neighborhood, support degree, core object probability, direct reachability probability, thus reducing the complexity and solving the issue of nonadaptive threshold (for core object judgement) in FDBSCAN. Then, we modify the algorithm PDBSCAN to an improved version (PDBSCANi), by using a better cluster assignment strategy to ensure that every object will be assigned to the most appropriate cluster, thus solving the issue of nonadaptive threshold (for direct density reachability judgement) in FDBSCAN. Furthermore, as PDBSCAN and PDBSCANi have difficulties for clustering uncertain data with non-uniform cluster density, we propose a novel hierarchical density-based algorithm POPTICS by extending the definitions of PDBSCAN, adding new definitions of fuzzy core distance and fuzzy reachability distance, and employing a new clustering framework. POPTICS can reveal the cluster structures of the datasets with different local densities in different regions better than PDBSCAN and PDBSCANi, and it addresses the issues in FOPTICS. Experimental results demonstrate the superiority of our proposed algorithms over the existing algorithms in accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Distance measure plays an important role in clustering uncertain data. However, existing distance measures for clustering uncertain data suffer from some issues. Geometric distance measure can not identify the difference between uncertain objects with different distributions heavily overlapping in locations. Probability distribution distance measure can not distinguish the difference between different pairs of completely separated uncertain objects. In this paper, we propose a self-adapted mixture distance measure for clustering uncertain data which considers the geometric distance and the probability distribution distance simultaneously, thus overcoming the issues in previous distance measures. The proposed distance measure consists of three parts: (1) The induced kernel distance: it can be used to measure the geometric distance between uncertain objects. (2) The Jensen–Shannon divergence: it can be used to measure the probability distribution distance between uncertain objects. (3) The self-adapted weight parameter: it can be used to adjust the importance degree of the induced kernel distance and the Jensen–Shannon divergence according to the location overlapping information of the dataset. The proposed distance measure is symmetric, finite and parameter adaptive. Furthermore, we integrate the self-adapted mixture distance measure into the partition-based and density-based algorithms for clustering uncertain data. Extensive experimental results on synthetic datasets, real benchmark datasets and real world uncertain datasets show that our proposed distance measure outperforms the existing distance measures for clustering uncertain data. [ABSTRACT FROM AUTHOR]

Lineage is important in uncertain data management since it can be used for finding out which part of data contributes to a result and computing the probability of the result. Nonetheless, the existing works consider an uncertain tuple as a set of tuples that can be stored in a relational table. Lineage can derive each tuple in the table, with which one can only find out the tuples rather than specific attributes that contribute to the result. If uncertain tuples have multiple uncertain attributes, for a result tuple with low probability, users cannot know which attribute is the main cause of it. In this paper, we propose an approach to model uncertain data. Compared with the alternative way based on the relational model, our model achieves a low maintenance cost and avoids a large number of redundant storage and join operations. Based on our model, some operations are defined for querying data, generating lineage, computing probability and derivation of results. Further, we discuss how to correctly compute probability with lineage and an algorithm is proposed to transform lineage for correct probability computation. We also discuss how to realize result derivation with the lineage. Experiments show the advantages of the proposed model on uncertain data management. [ABSTRACT FROM AUTHOR]

Weighted Frequent Itemset Mining (WFIM) has been proposed as an extension of frequent itemset mining that considers not only the frequency of items but also their relative importance. However, using WFIM algorithms in real applications raises some problems. First, they do not consider how recent the patterns are. Second, traditional WFIM algorithms cannot handle uncertain data, although this type of data is common in real-life. To address these limitations, this paper introduces the concept of Recent High Expected Weighted Itemset (RHEWI), which considers the recency, weight and uncertainty of patterns. By considering these three factors, more up-to-date and relevant results are found. A projection-based algorithm named RHEWI-P is presented to mine RHEWIs using a novel upper - bound downward closure ( UBDC ) property. An improved version of this algorithm called RHEWI-PS is further proposed based on a novel sorted upper-bound downward closure ( SUBDC ) property for pruning unpromising candidate itemsets early. An experimental evaluation against the state-of-the-art HEWI-Uapriori algorithm was carried out on both real-world and synthetic datasets. Results show that the proposed algorithms are highly efficient and are acceptable for mining the desired patterns. [ABSTRACT FROM AUTHOR]

The current state-of-art for tackling the problem of classification of static uncertain data under PU learning (Positive Unlabeled Learning) scenario, is UPNB. It is based on the Bayesian assumption, which does not hold for real-life applications, and hence it may depress the classification performance of UPNB. In this paper, we propose UPTAN (Uncertain Positive Tree Augmented Naive Bayes), a Bayesian network algorithm, so as to utilize the dependence information among uncertain attributes for classification. We propose uncertain conditional mutual information (UCMI) for measuring the mutual information between uncertain attributes, and then use it to learn the tree structure of Bayesian network. Furthermore, we give our approach for estimating the parameters of the Bayesian network for uncertain data without negative training examples. Our experiments on 20 UCI datasets show that UPTAN has excellent classification performance, with average F 1 being 0.8257, which outperforms UPNB by 3.73%. [ABSTRACT FROM AUTHOR]

Uncertain objects, where each feature is represented by multiple observations or a given or fitted probability density function, arise in applications such as sensor networks, moving object databases and medical and biological databases. We propose a methodology to classify uncertain objects based on a new probabilistic distance measure between an uncertain object and a group of uncertain objects. This object-to-group probabilistic distance measure is unique in that it accounts separately for the correlations among the features within each class and within each object. We compare the proposed object-to-group classifier to two existing classifiers, namely, the K-Nearest Neighbor classifier on object means (certain-KNN) and the uncertain-naïve Bayes classifier. In addition, we compare the object-to-group classifier to an uncertain K-Nearest Neighbor classifier (uncertain-KNN), also proposed here, that uses existing probabilistic distance measures for object-to-object distances. We illustrate the advantages of the proposed classifiers with both simulated and real data. [ABSTRACT FROM AUTHOR]

• The first method for interactive mining of Top-K uncertain frequent patterns. • Introducing a new list-based data structure to deal with interactive environments. • Introducing techniques to avoid unnecessary processing of lists. • The proposed ITUFP dramatically improves runtime and scalability. Top- K Uncertain Frequent Pattern (UFP) mining is an interesting topic in data mining. The existing TUFP algorithm supports static mining of Top- K UFPs; however, in the real world, users need to repeatedly change the K threshold to extract the information according to the requirements of their application. In interactive environments, the TUFP algorithm needs to re-scan the database and create the UP-Lists and CUP-Lists from scratch which is very time-consuming. In this paper, a fast method called ITUFP is proposed for interactive mining of Top- K UFPs. The proposed method uses a new data structure called IMCUP-List to store information of patterns efficiently. It creates the UP-Lists with a single database scan, extracts the patterns by generating IMCUP-Lists, and stores all the lists. When K changes, the proposed algorithm only updates the IMCUP-Lists without having to create the lists from scratch. Accordingly, ITUFP conforms to the "build once, mine many" principle, where the UP-Lists and IMCUP-Lists are created only once and used in mining with different K values. This is the first study on interactive mining of Top- K UFPs. Extensive experimental results with sparse and dense uncertain data prove that the proposed method is very efficient for interactive mining of Top- K UFPs. [ABSTRACT FROM AUTHOR]

In geostatistics, available conditional information is typically categorized as either hard (with no uncertainty) or soft (associated with an uncertainty) data. 2-point based Gaussian (kriging) simulation methods have since their inception been able to account for hard and soft data. In contrast, multiple-point statistical (MPS) simulation methods, that allow quantifying more complex phenomena than Gaussian methods, have focused mostly on conditioning to hard data. The most widely used method for accounting for soft data is to consider only co-located soft data. Here we define conditional information data through a probability distribution and show how a general probabilistic solution, in the form of a posterior probability distribution, can be obtained, combining conditional categorical information with information from a categorical training image. We demonstrate how to compute the conditional distribution, as needed by most MPS-based sequential simulation algorithms, that allows accounting for both co- and non-co-located hard and soft data. Examples are provided comparing the direct computation of conditional statistics to using more computational demanding rejection sampling. In order to reduce the significant computational demands, a distance-based measure is proposed to increase the entropy of conditional data, based on the distance to the point being estimated and simulated. • Ignoring non-co-located soft data leads to artefacts and loss of information. • Using a preferential path with co-locations soft data conditioning increases the accuracy of MPS. • All non-co-locational conditioning data can in principle be accounted for using MPS sequential simulation. • Accounting for correlated co-locational data with MPS is still an unsolved problem. [ABSTRACT FROM AUTHOR]

Learning from uncertain data has attracted increasing attention in recent years. In this paper, we propose a decision tree learning method that can not only handle uncertain data, but also reduce epistemic uncertainty by querying the most valuable uncertain instances within the learning procedure. Specifically, we use entropy intervals extracted from the evidential likelihood to query uncertain training instances when needed, with the goal to improve the selection of the splitting attribute. Experimental results under various conditions confirm the interest of the proposed approach. [ABSTRACT FROM AUTHOR]

In recent years, along with the generation of uncertain data, more and more attention is paid to the mining of uncertain data. In this paper, we study the problem of classifying uncertain data using Extreme Learning Machine (ELM). We first propose the UU-ELM algorithm for classification of uncertain data which is uniformly distributed. Furthermore, the NU-ELM algorithm is proposed for classifying uncertain data which are non-uniformly distributed. By calculating bounds of the probability, the efficiency of the algorithm can be improved. Finally, the performances of our methods are verified through a large number of simulated experiments. The experimental results show that our methods are effective ways to solve the problem of uncertain data classification, reduce the execution time and improve the efficiency. [ABSTRACT FROM AUTHOR]

Driven by the emerging network data exchange and storage, XML documents classification has become increasingly important. Most existing representation model and conventional learning algorithm are defined on certain XML documents. However, in many real-world applications, XML datasets contain inherent uncertainty, which brings greater challenges to classification problem. In this paper, we propose a novel solution to classify uncertain XML documents, including uncertain XML documents representation and two uncertain learning algorithms based on Extreme Learning Machine. Experimental results show that our approaches exhibit prominent performance for uncertain XML documents classification problem. [ABSTRACT FROM AUTHOR]

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query interval I : (1) top-1 query: find a point in P that lies in I with the highest probability, (2) top- k query: given any integer k ≤ n as part of the query, return the k points in P that lie in I with the highest probabilities, and (3) threshold query: given any threshold τ as part of the query, return all points of P that lie in I with probabilities at least τ . We present data structures for these range queries with linear or nearly linear space and efficient query time. [ABSTRACT FROM AUTHOR]

Most of the real-world data is gathered locally, organized regionally leading to distributed environment. The analysis of such data will assist decision makers for promoting their business. Most of the data mining strategies are multi-pass techniques employed for mining and discovering the knowledge. Hence, the paper focuses on developing two pass data mining constructs to handle uncertain data. One of the simplest and feasible item-pattern representations is transactional tree. The developed methodology for constructing transactional trees is studied in detail and apt technological solutions is proposed. It is proposed to construct transactional tree from uncertain data which is usually associated with existential probabilities and to establish distributed computing environment for developing transactional trees. This paper aims at bringing out the knowledge valid for a given location through which it is expected to derive global knowledge. [ABSTRACT FROM AUTHOR]

With the evolution of technology, the ways to acquire data and the applications of data are more diverse. As data volume con- tinuously grows, the data quality may not be high as usual. The data can be defected, imprecise or inaccurate due to the process of data acquiring. Recently, the skyline query is widely used in data analysis to derive the results that meets more than one spe- cific condition simultaneously. For example, the forest monitoring system, which collects the temperature and humidity of the surrounding environment with sensors, to monitor the disasters. Using the skyline query, the zones of potential fire hazards can be found in time, where the temperature is high and the humidity is low. In the mentioned application, the derived data change with time. We refer to such data as data streams. The constant change and uncertainty of data make the query process difficult and need more computations. Thus, how to have an effective skyline query process in terms of time and space over uncertain data streams becomes crucial. In this paper, we discuss this problem and propose an effective approach, Efficient Probabilistic Skyline Update (EPSU), using a new data structure by augmenting the R-tree structure. The relevant algorithms are analyzed and discussed. Last, we perform the simulated experiments extensively with synthetic data to validate the EPSU approach. The results show that EPSU can effectively compute the probabilistic skyline query in terms of the time and space and outperforms the existing ones. [ABSTRACT FROM AUTHOR]

Processing lineages (also called provenances) over uncertain data consists in tracing the origin of uncertainty based on the process of data production and evolution. In this paper, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian network (BN), one of the popular and important probabilistic graphical models (PGMs), as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for SPJ (Selection–Projection–Join) queries over uncertain data, we propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, can be constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN's exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN's approximate inferences. Experimental results show the efficiency and effectiveness of our methods. [ABSTRACT FROM AUTHOR]

Knowledge discovery and data mining generally discovers implicit, previously unknown, and useful knowledge from data. As one of the popular knowledge discovery and data mining tasks, frequent itemset mining, in particular, discovers knowledge in the form of sets of frequently co-occurring items, events, or objects. On the one hand, in many real-life applications, users mine frequent patterns from traditional databases of precise data, in which users know certainly the presence of items in transactions. On the other hand, in many other real-life applications, users mine frequent itemsets from probabilistic sets of uncertain data, in which users are uncertain about the likelihood of the presence of items in transactions. Each item in these probabilistic sets of uncertain data is often associated with an existential probability expressing the likelihood of its presence in that transaction. To mine frequent itemsets from these probabilistic datasets, many existing algorithms capture lots of information to compute expected support. To reduce the amount of space required, algorithms capture some but not all information in computing or approximating expected support. The tradeoff is that the upper bounds to expected support may not be tight. In this paper, we examine several upper bounds and recommend to the user which ones consume less space while providing good approximation to expected support of frequent itemsets in mining probabilistic sets of uncertain data. [ABSTRACT FROM AUTHOR]

In this study, we propose two algorithms to discover time - interval univariate uncertain ( U2 ) - sequential patterns from a set of univariate uncertain ( U2 )- sequences . A U2-sequence is a sequence that contains transactions of univariate uncertain data , where each attribute in a transaction is associated with a quantitative interval and a probability density function indicating the possibility that each value exists in the interval. Many sources record U2-sequences, such as atmospheric pollution sensors and network monitoring systems. Mining sequential patterns from these U2-sequences is important for understanding the intrinsic characteristics of the U2-sequences. The proposed two algorithms are based on the candidate generate-and-test methodology and pattern growth methodology, respectively. We performed a series of experiments to evaluate them in terms of runtime and memory consumption. The experimental results show that different algorithms excel when applied to different conditions. In general, the algorithm based on the pattern growth methodology is the better choice. [ABSTRACT FROM AUTHOR]

Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k -center problem on one-dimensional uncertain data. The input is a set P of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (i.e., a histogram). The goal is to find a set Q of k points on the line to minimize the maximum expected distance from the uncertain points of P to their expected closest points in Q . We present efficient algorithms for this uncertain k -center problem and their running times almost match those for the “deterministic” k -center problem. [ABSTRACT FROM AUTHOR]