A study on the accuracy of frequency measures and its impact on knowledge discovery in single sequences

In knowledge discovery in single sequences, different results could be discovered from the same sequence when different frequency measures are adopted. It is natural to raise such questions as (1) do these frequency measures reflect actual frequencies accurately? (2) what impacts do frequency measures have on discovered knowledge? (3) are discovered results accurate and reliable? and (4) which measures are appropriate for reflecting frequencies accurately? In this paper, taking three major factors (anti-monotonicity, maximum-frequency and window-width restriction) into account, we identify inaccuracies inherent in seven existing frequency measures, and investigate their impacts on the soundness and completeness of two kinds of knowledge, frequent episodes and episode rules, discovered from single sequences. In order to obtain more accurate frequencies and knowledge, we provide three recommendations for defining appropriate frequency measures. Following the recommendations, we introduce a more appropriate frequency measure. Empirical evaluation reveals the inaccuracies and verifies our findings. 

Obtaining accurate frequencies of sequential patterns over a single sequence

In the mining and analysis of a single long sequence, one fundamental and important problem is obtaining accurate frequencies of sequential patterns over the sequence. However, we identify that five previous frequency measures suffer from inherent inaccuracies. To obtain more accurate frequencies, we introduce two basic principles called strict anti-monotonicity and maximum-count for frequency measures. Under the two principles, a new frequency measure is presented. An algorithm is also devised to compute it. Both theoretical analysis and empirical evaluation show that more accurate frequencies can be obtained under the new measure

A characterization theorem for t-representable n-dimensional triangular norms

n-dimensional fuzzy sets are an extension of fuzzy sets that includes interval-valued fuzzy sets and interval-valued Atanassov intuitionistic fuzzy sets. The membership values of n-dimensional fuzzy sets are n-tuples of real numbers in the unit interval [0,1], called n-dimensional intervals, ordered in increasing order. The main idea in n-dimensional fuzzy sets is to consider several uncertainty levels in the memberships degrees. Triangular norms have played an important role in fuzzy sets theory, in the narrow as in the broad sense. So it is reasonable to extend this fundamental notion for n-dimensional intervals. In interval-valued fuzzy theory, interval-valued t-norms are related with t-norms via the notion of t-representability. A characterization of t-representable interval-valued t-norms is given in term of inclusion monotonicity. In this paper we generalize the notion of t-representability for n-dimensional t-norms and provide a characterization theorem for that class of n-dimensional t-norms. © 2011 Springer-Verlag Berlin Heidelberg.

Fast mining of non-derivable episode rules in complex sequences

Researchers have been endeavoring to discover concise sets of episode rules instead of complete sets in sequences. Existing approaches, however, are not able to process complex sequences and can not guarantee the accuracy of resulting sets due to the violation of anti-monotonicity of the frequency metric. In some real applications, episode rules need to be extracted from complex sequences in which multiple items may appear in a time slot. This paper investigates the discovery of concise episode rules in complex sequences. We define a concise representation called non-derivable episode rules and formularize the mining problem. Adopting a novel anti-monotonic frequency metric, we then develop a fast approach to discover non-derivable episode rules in complex sequences. Experimental results demonstrate that the utility of the proposed approach substantially reduces the number of rules and achieves fast processing.

Enhancing fuzzy inference system based criterion-referenced assessment with an application

An important and difficult issue in designing a Fuzzy Inference System (FIS) is the specification of fuzzy sets, and fuzzy rules. The aim of this paper is to demonstrate how an additional qualitative information, i.e., monotonicity property, can be exploited and extended to be part of an FIS designing procedure (i.e., fuzzy sets and fuzzy rules design). In this paper, the FIS is employed as an alternative to the use of addition in aggregating the scores from test items/tasks in a Criterion-Referenced Assessment (CRA) model. In order to preserve the monotonicity property, the sufficient conditions of the FIS is proposed. Our proposed FIS based CRA procedure can be viewed as an enhancement for the FIS based CRA procedure, where monotonicity property is preserved. We demonstrate the applicability of the proposed approach with a case study related to a laboratory project assessment task at a university, and the results indicate the usefulness of the proposed approach in the CRA domain.

On the use of fuzzy rule interpolation techniques for monotonic multi-input fuzzy rule base models

Constructing a monotonicity relating function is important, as many engineering problems revolve around a monotonicity relationship between input(s) and output(s). In this paper, we investigate the use of fuzzy rule interpolation techniques for monotonicity relating fuzzy inference system (FIS). A mathematical derivation on the conditions of an FIS to be monotone is provided. From the derivation, two conditions are necessary. The derivation suggests that the mapped consequence fuzzy set of an FIS to be of a monotonicity order. We further evaluate the use of fuzzy rule interpolation techniques in predicting a consequent associated with an observation according to the monotonicity order. There are several findings in this article. We point out the importance of an ordering criterion in rule selection for a multi-input FIS before the interpolation process; and hence, the practice of choosing the nearest rules may not be true in this case. To fulfill the monotonicity order, we argue with an example that conventional fuzzy rule interpolation techniques that predict each consequence separately is not suitable in this case. We further suggest another class of interpolation techniques that predicts the consequence of a set of observations simultaneously, instead of separately. This can be accomplished with the use of a search algorithm, such as the brute force, genetic algorithm or etc.

On monotonic sufficient conditions of fuzzy inference systems and their applications

An important and difficult issue in designing a Fuzzy Inference System (FIS) is the specification of fuzzy sets and fuzzy rules. In this paper, two useful qualitative properties of the FIS model, i.e., the monotonicity and sub-additivity properties, are studied. The monotonic sufficient conditions of the FIS model with Gaussian membership functions are further analyzed. The aim is to incorporate the sufficient conditions into the FIS modeling process, which serves as a simple (which can be easily understood by domain users), easy-to-use (which can be easily applied to or can be a part of the FIS model), and yet reliable (which has a sound mathematical foundation) method to preserve the monotonicity property of the FIS model. Another aim of this paper is to demonstrate how these additional qualitative information can be exploited and extended to be part of the FIS designing procedure (i.e., for fuzzy sets and fuzzy rules design) via the sufficient conditions (which act as a set of useful governing equations for designing the FIS model). The proposed approach is able to avoid the "trial and error" procedure in obtaining a monotonic FIS model. To assess the applicability of the proposed approach, two practical problems are examined. The first is an FIS-based model for water level control, while the second is an FIS-based Risk Priority Number (RPN) model in Failure Mode and Effect Analysis (FMEA). To further illustrate the importance of the sufficient conditions as the governing equations, an analysis on the consequences of violating the sufficient conditions of the FIS-based RPN model is presented.

An evolutionary-based similarity reasoning scheme for monotonic multi-input fuzzy inference systems

In this paper, an Evolutionary-based Similarity Reasoning (ESR) scheme for preserving the monotonicity property of the multi-input Fuzzy Inference System (FIS) is proposed. Similarity reasoning (SR) is a useful solution for undertaking the incomplete rule base problem in FIS modeling. However, SR may not be a direct solution to designing monotonic multi-input FIS models, owing to the difficulty in getting a set of monotonically-ordered conclusions. The proposed ESR scheme, which is a synthesis of evolutionary computing, sufficient conditions, and SR, provides a useful solution to modeling and preserving the monotonicity property of multi-input FIS models. A case study on Failure Mode and Effect Analysis (FMEA) is used to demonstrate the effectiveness of the proposed ESR scheme in undertaking real world problems that require the monotonicity property of FIS models.

A new framework with similarity reasoning and monotone fuzzy rule relabeling for fuzzy inference systems

A complete and monotonically-ordered fuzzy rule base is necessary to maintain the monotonicity property of a Fuzzy Inference System (FIS). In this paper, a new monotone fuzzy rule relabeling technique to relabel a non-monotone fuzzy rule base provided by domain experts is proposed. Even though the Genetic Algorithm (GA)-based monotone fuzzy rule relabeling technique has been investigated in our previous work [7], the optimality of the approach could not be guaranteed. The new fuzzy rule relabeling technique adopts a simple brute force search, and it can produce an optimal result. We also formulate a new two-stage framework that encompasses a GA-based rule selection scheme, the optimization based-Similarity Reasoning (SR) scheme, and the proposed monotone fuzzy rule relabeling technique for preserving the monotonicity property of the FIS model. Applicability of the two-stage framework to a real world problem, i.e., failure mode and effect analysis, is further demonstrated. The results clearly demonstrate the usefulness of the proposed framework.

Parallel monotone spline interpolation and approximation on GPUs

Monotonicity preserving interpolation and approximation have received substantial attention in the last thirty years because of their numerous applications in computer aided-design, statistics, and machine learning [9, 10, 19]. Constrained splines are particularly popular because of their flexibility in modeling different geometrical shapes, sound theoretical properties, and availability of numerically stable algorithms [9,10,26]. In this work we examine parallelization and adaptation for GPUs of a few algorithms of monotone spline interpolation and data smoothing, which arose in the context of estimating probability distributions.

On some properties of weighted averaging with variable weights

Density-based means have been recently proposed as a method for dealing with outliers in the stream processing of data. Derived from a weighted arithmetic mean with variable weights that depend on the location of all data samples, these functions are not monotonic and hence cannot be classified as aggregation functions. In this article we establish the weak monotonicity of this class of averaging functions and use this to establish robust generalisations of these means. Specifically, we find that as proposed, the density based means are only robust to isolated outliers. However, by using penalty based formalisms of averaging functions and applying more sophisticated and robust density estimators, we are able to define a broader family of density based means that are more effective at filtering both isolated and clustered outliers. © 2014 Elsevier Inc. All rights reserved.

Weakly monotone averaging functions

Averaging behaviour of aggregation functions depends on the fundamental property of monotonicity with respect to all arguments. Unfortunately this is a limiting property that ensures that many important averaging functions are excluded from the theoretical framework. We propose a definition for weakly monotone averaging functions to encompass the averaging aggregation functions in a framework with many commonly used non-monotonic means. Weakly monotonic averages are robust to outliers and noise, making them extremely important in practical applications. We show that several robust estimators of location are actually weakly monotone and we provide sufficient conditions for weak monotonicity of the Lehmer and Gini means and some mixture functions. In particular we show that mixture functions with Gaussian kernels, which arise frequently in image and signal processing applications, are actually weakly monotonic averages. Our concept of weak monotonicity provides a sound theoretical and practical basis for understanding both monotone and non-monotone averaging functions within the same framework. This allows us to effectively relate these previously disparate areas of research and gain a deeper understanding of averaging aggregation methods. © Springer International Publishing Switzerland 2014.

Fuzzy measures of pixel cluster compactness

Pixel-scale fine details are often lost during image processing tasks such as image reduction and filtering. Block or region based algorithms typically rely on averaging functions to implement the required operation and traditional function choices struggle to preserve small, spatially cohesive clusters of pixels which may be corrupted by noise. This article proposes the construction of fuzzy measures of cluster compactness to account for the spatial organisation of pixels. We present two construction methods (minimum spannning trees and fuzzy measure decomposition) to generate measures with specific properties: monotonicity with respect to cluster size; invariance with respect to translation, reflection and rotation; and, discrimination between pixel sets of fixed cardinality with different spatial arrangements. We apply these measures within a non-monotonic mode-like averaging function used for image reduction and we show that this new function preserves pixel-scale structures better than existing monotonie averages.