Search

This paper focuses on recovering multi-dimensional signal called tensor which is corrupted by random missing areas. The performance of the conventional tensor completion techniques deteriorate when the tensor multi-rank is large and/or large missing areas. Moreover, these techniques are weak in preserving the edges in the signals like images/videos. This paper proposes an efficient method to overcome these problems by simultaneously combining novel twist tensor total variation norm to exploit spatio-temporal correlation and tensor-Singular Value Decomposition (t-SVD) based reweighted nuclear norm to improve low multi-rank tensor recovery. The twist tensor total variation norm takes care of edges in the recovered data and aids the recovery of missing areas by utilising the similarities in the adjacent samples. The reweighted nuclear norm handles corrupted large rank tensors by sparsity enhancement via reweighting its singular values. The effectiveness of the proposed method is established by applying to video completion problem, and experimental results reveal that the algorithm outperforms its counterparts.

Several recent papers have studied the problem of attribute reduction in concept lattices by using a discernibility matrix in various extensions of formal concept analysis. We recall the clarification and reduction method by Ganter & Wille and show that it is strictly superior to the methods based on discernibility matrix. Consequently, we show how to adapt the clarification and reduction method to the extensions of formal concept analysis considered in the recent papers.

In the paper, we describe the new measure of matching fuzzy sets. The introduced measure of perturbation of one fuzzy set by another fuzzy set is considered instead of commonly used distance between two fuzzy sets. The operations known in the fuzzy set theory are used and the perturbation of one fuzzy set by another fuzzy set is understood as a measure describing changes of the first fuzzy set after adding the second one. Obviously, the opposite case can also be considered wherein the second fuzzy set is perturbed by the first one. In general, the new measure is asymmetric and can provide more information compare to a distance between fuzzy sets. The values of such measures of fuzzy sets perturbation are in range between 0 and 1. In this paper several mathematical properties of the measure of fuzzy sets perturbation are studied, and the measure of sets perturbation is compared to other selected measures.

Rough set models on two universes are valuable generalizations of classic rough set model. These models can be applied into formal concept analysis and decision-making system. This paper focuses on catoptrical approach for rough set models over two universes using granule-based definition. In this paper, we propose a new catoptrical rough set model over dual universes. The properties of the proposed model are discussed. Consequently, a variable precision extension of the model is presented. Some properties of the extended model are obtained. Finally, we investigate a further extension of the proposed model, i.e. variable precision catoptrical rough set model with two parameters.

Orthogonal moments play an important role in image analysis and other similar applications. However, existing orthogonal moments are restricted to integer order, and little investigation of non-integer order orthogonal moments has been conducted to date. In this paper, a general framework of real-order orthogonal moments, also known as fractional-order orthogonal moments, is proposed. In this general framework, fractional-order orthogonal moments can be defined in Cartesian and polar coordinate systems. Shifted Legendre polynomials are implemented in this paper to investigate the properties of fractional-order orthogonal moments. A series of experiments are performed, which demonstrate that fractional-order orthogonal moments are not only capable of region-of-interest (ROI) feature extraction but also have potential for image reconstruction and face recognition and have high noise robustness in invariant image recognition.

In MMMF, ratings matrix with multiple discrete values is treated by specially extending hinge loss function to suit multiple levels.We view this process as analogous to extending two-class classifier to a unified multi-class classifier.Alternatively, multi-class classifier can be built by arranging multiple two- class classifiers in a hierarchical manner.In this paper, we investigate this aspect for collaborative filtering and propose an efficient and novel framework of multiple bi-level MMMFs.We compare our method with nine well-known algorithms on two benchmark datasets and show that our method outperforms these methods on NMAE measure. Maximum Margin Matrix Factorization (MMMF) has been a successful learning method in collaborative filtering research. For a partially observed ordinal rating matrix, the focus is on determining low-norm latent factor matrices U (of users) and V (of items) so as to simultaneously approximate the observed entries under some loss measure and predict the unobserved entries. When the rating matrix contains only two levels (1), rows of V can be viewed as points in k-dimensional space and rows of U as decision hyperplanes in this space separating +1 entries from 1 entries. When hinge/smooth hinge loss is the loss function, the hyperplanes act as maximum-margin separator. In MMMF, rating matrix with multiple discrete values is treated by specially extending hinge loss function to suit multiple levels. We view this process as analogous to extending two-class classifier to a unified multi-class classifier. Alternatively, multi-class classifier can be built by arranging multiple two-class classifiers in a hierarchical manner. In this paper, we investigate this aspect for collaborative filtering and propose an efficient and novel framework of multiple bi-level MMMFs. There is substantial saving in computational overhead. We compare our method with nine well-known algorithms on two benchmark datasets and show that our method outperforms these methods on NMAE measure. We also show that our method yields latent factors of lower ranks and the trade-off between empirical and generalization error is low.

This paper considers parameter identification problems for multivariable Hammerstein controlled autoregressive moving average (CARMA) systems. We transform a multivariable Hammerstein CARMA system into a new identification model which contains a set of bilinear parameter vectors, i.e., two sets of parameter vectors. To solve the difficulty of estimating the two sets of parameter vectors, this paper constructs two different forms of the identification model in each of which the output is linear about one set of parameter vectors, and presents an extended stochastic gradient algorithm to interactively estimate the two sets of parameter vectors by using the hierarchical identification principle. The proposed hierarchical identification algorithm has a higher computational efficiency than the over-parametrization model based stochastic gradient algorithm. The simulation results indicate that the proposed algorithm is effective, and an example of modeling a photovoltaic array system with the multivariable Hammerstein model is given.

With complex properties of ergodicity, unpredictability and sensitivity to initial states, chaotic systems are widely used in cryptography. This paper proposes a two-dimensional Logistic-adjusted-Sine map (2D-LASM). Performance evaluations show that it has better ergodicity and unpredictability, and a wider chaotic range than many existing chaotic maps. Using the proposed map, this paper further designs a 2D-LASM-based image encryption scheme (LAS-IES). The principle of diffusion and confusion are strictly fulfilled, and a mechanism of adding random values to plain-image is designed to enhance the security level of cipher-image. Simulation results and security analysis show that LAS-IES can efficiently encrypt different kinds of images into random-like ones that have strong ability of resisting various security attacks.

In this paper the comparison of a proposed neural network with generalized type-2 fuzzy weights (NNGT2FW) with respect to the monolithic neural network (NN) and the neural network with interval type-2 fuzzy weights (NNIT2FW) is presented. Generalized type-2 fuzzy inference systems are used to obtain the generalized type-2 fuzzy weights and are designed by a strategy of increasing and decreasing an epsilon variable for obtaining the different sizes of the footprint of uncertainty (FOU) for the generalized membership functions. The proposed method is based on recent approaches that handle weight adaptation using type-1 and type-2 fuzzy logic. The approach is applied to the prediction of the Mackey-Glass time series, and results are shown to outperform the results produced by other neural models. Gaussian noise was applied to the test data of the Mackey-Glass time series for finding out which of the presented methods in this paper shows better performance and tolerance to noise.

In this paper a new effective and scalable differential evolution algorithm is proposed for optimizing the Satellite Broadcast's Scheduling problem (SBS). The satellite broadcast's scheduling optimization problem is known to be an NP-complete problem in which the aim is to find a valid broadcasting pattern to earth-stationed terminals which maximizes the number of timeslots utilized for broadcasting under certain constraints. The algorithm proposed SD-BDE, is a binary version of Differential Evolution hybridized with ideas extracted from Stochastic Diffusion search. On top of that a repair heuristic mechanism is added to resolve constraint violations. Preliminary analysis shows that the repair heuristic is very effective as compared to other versions which include other heuristics. Further, the performance of the proposed algorithm is tested thoroughly against published work toward solving SBS problem as well as state-of-the-art existing binary-coded population-based similar algorithms. In this paper, we used, along with instances reported in the literature for such problem, randomly generated benchmark's instances of varying sizes for the sake of creating a unified large-scale set to compare different algorithm against. Experimental results show that the proposed algorithm outperformed the existing algorithms by finding better or optimal solutions for almost all tested benchmarks.

We proposed a novel kernel-based fuzzy clustering for Geo-Demographic Analysis.It relied on Gaussian kernel function, updated elements and standardized weights.The algorithm was both theoretical and experimental validated.Its clustering quality was better than those of other relevant algorithms.Some properties of solutions were examined. Geo-Demographic Analysis (GDA) is a major concentration of various interdisciplinary researches and has been used in many decision-making processes regarding the provision and distribution of products and services in society. Machine learning methods namely Principal Component Analysis, Self-Organizing Map, K-Means, fuzzy clustering and fuzzy geographically weighted clustering were proposed to enhance the quality of GDA. Among them, the state-of-the-art method - Modified Intuitionistic Possibilistic Fuzzy Geographically Weighted Clustering (MIPFGWC) has some drawbacks such as: (i) using the Euclidean similarity measure often results in high error rate and sensitivity to noises and outliers; (ii) updating the membership matrix by the Spatial Interaction - Modification Model (SIM2) model leads to new centers not being "geographically aware". In this paper, we present a novel fuzzy clustering algorithm named as Kernel Fuzzy Geographically Clustering (KFGC) that utilizes both the kernel similarity function and the new update mechanism of the SIM2 model to remedy the disadvantages of MIPFGWC. Some supported properties and theorems of KFGC are also examined in the paper. Specifically, the differences between solutions of KFGC and those of MIPFGWC and of some variants of KFGC are theoretically validated. Lastly, experimental analysis is performed to compare the performance of KFGC with those of the relevant algorithms in terms of clustering quality.

This paper develops a new method for solving multiple attribute group decision-making (MAGDM) problems with Atanassov's interval-valued intuitionistic fuzzy values (AIVIFVs) and incomplete attribute weight information. Firstly, we investigate the asymptotic property of the Atanassov's interval-valued intuitionistic fuzzy (AIVIF) matrix. It is demonstrated that after applying weights an infinite number of times, all elements in an AIVIF matrix will approach the same AIVIFV without regard to the initial values of elements. Then, the weight of each decision maker (DM) with respect to every attribute is determined by considering the similarity degree and proximity degree simultaneously. To avoid weighting an AIVIF matrix too many times, the collective decision matrix is transformed into an interval matrix using the risk coefficient of DMs. Subsequently, to derive the attribute weights objectively, we construct a multi-objective interval-programming model that is solved by transforming it into a linear program. The ranking order of alternatives is generated by the comprehensive interval values of alternatives. Finally, an example of a research and development (R&D) project selection problem is provided to illustrate the implementation process and applicability of the method developed in this paper.

The paper subsumes and extends in a radical way a line of research aimed at automation of reasoning with inconsistent information using paraconsistent logics. We provide a new method for uniform, modular construction of analytic calculi for all major logics in the crucial class of paraconsistent logics known as C-systems. The method is based on semantic characterization of those logics via non-deterministic matrices (Nmatrices), and - unlike that developed previously - is also applicable to C-systems which can only be characterized by infinite Nmatrices. What is more, we show that the results obtained in this paper for infinite semantics imply our earlier results for finite semantics.

This paper studies the problem of k-optimal-location-selection (kOLS) retrieval in metric spaces. Given a set D A of customers, a set D B of locations, a constrained region R, and a critical distance d c , a metric kOLS (MkOLS) query retrieves k locations in D B that are outside R but have the maximal optimality scores. Here, the optimality score of a location l ? D B located outside R is defined as the number of the customers in D A that are inside R and meanwhile have their distances to l bounded by d c according to a certain similarity metric (e.g., L 1 -norm, L 2 -norm, etc.). The existing kOLS methods are not sufficient because they are applicable only to the Euclidean space, and are not sensitive to k. In this paper, for the first time, we present an efficient algorithm for kOLS query processing in metric spaces. Our solution employs metric index structures (i.e., M-trees) on the datasets, enables several pruning rules, utilizes the advantages of reuse technique and optimality score estimation, to support a wide range of data types and similarity metrics. In addition, we extend our techniques to tackle two interesting and useful variants, namely, MkOLS queries with multiple or no constrained regions. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of the presented pruning rules and the performance of the proposed algorithms.

It is well known that one of the basic advantages of evolutionary programming is in deciding the most suitable place for breeding offspring and finding the route toward the global minimum. To reach this goal, the algorithm needs to estimate the coordinates of the global minimum and then steer the new point toward it. In this paper, the estimation of the global minimum is calculated by weighted mean coordination of individuals (WMP), and then a road is mapped between the coordinates of the parents and the WMP. In the proposed method, fuzzy logic is used for deciding on the road and the best coordination to breed offspring. The proposed algorithm is tested on 65 well-known cost functions and is compared with five algorithms inside the EP family. In the next section of the paper, the algorithm is tested on the high-dimensional problem of modeling ozone layer data, which includes almost 26,000 unknown parameters. The results demonstrate the capability of the proposed method in having acceptable speed and accuracy.

Bayesian learning provides a firm theoretical basis of the design and exploitation of algorithms in data-streams processing (preprocessing, change detection, hypothesis testing, clustering, etc.). Primarily, it relies on a recursive parameter estimation of a firmly bounded complexity. As a rule, it has to approximate the exact posterior probability density (pd), which comprises unreduced information about the estimated parameter. In the recursive treatment of the data stream, the latest approximate pd is usually updated using the treated parametric model and the newest data and then approximated. The fact that approximation errors may accumulate over time course is mostly neglected in the estimator design and, at most, checked ex post. The paper inspects the estimator design with respect to the error accumulation and concludes that a sort of forgetting (pd flattening) is an indispensable part of a reliable approximate recursive estimation. The conclusion results from a Bayesian problem formulation complemented by the minimum Kullback-Leibler divergence principle. Claims of the paper are supported by a straightforward analysis, by elaboration of the proposed estimator to widely applicable parametric models and illustrated numerically.

Rough set theory provides a very useful idea of lower and upper approximations for inconsistent data. For incomplete data these approximations are not unique. In this paper we investigate properties of three well-known generalizations of approximations: singleton, subset and concept. These approximations were recently further generalized as to include an additional parameter α , interpreted as a probability. In this paper we report novel properties of singleton, subset and concept probabilistic approximations. Additionally, we validated such approximations experimentally. Our main objective was to test which of the singleton, subset and concept probabilistic approximations are the most useful for data mining. Our conclusion is that, for a given incomplete data set, all three approaches should be applied and the best approach should be selected as a result of ten-fold cross validation. Finally, we conducted experiments on complexity of rule sets and the total number of singleton, subset and concept approximations.

Join aggregation is an important operation in database systems to return aggregate information on the join of two or several tables. Compared with exact query, it is a better choice in many cases to return approximate result satisfying a user-specified confidence interval in a much faster response time. It is found that none of previous works can efficiently process approximate join aggregation on massive data with arbitrary accuracy. This paper proposes a novel algorithm p e -AJA ( ( p , e ) -Approximate Join Aggregation) to obtain approximate join aggregate result with arbitrary confidence interval efficiently. Two data structures of low space overhead, JRS and JPIPT, are presented in this paper. p e -AJA first makes use of JRS to return a quick response. If the approximate result computed by JRS does not satisfy the given confidence interval, JPIPT is exploited to obtain enough random join tuples. This paper presents a novel sampling algorithm to acquire random JPIPT tuples of specified size and devises its correctness proof. A tuple fetching method is proposed to retrieve join tuples by the sampled JPIPT tuples in one-pass sequential scan on joined tables. The construction and maintenance algorithms of JPIPT and JRS are provided also in this paper. The experimental results show that p e -AJA obtains 3 times to 2 orders of magnitude speedup over the existing algorithms and runs 1 to 4 orders of magnitude faster than exact query.

Generating Membership Functions (MFs) from data is one of the fundamental challenges associated with the applications of fuzzy set theory. This paper proposes a new two-step algorithm, which uses discretization methods for initial partitioning, to generate MFs from data. In the first step, discretization algorithm divides domain of attributes to several partitions, and then, in the second step, an MF is defined on each partition. Four different methods are proposed to define MFs in the second step: the first method is based on partition width, the second is based on standard deviation of examples, the third is based on Coverage Rate of Neighbor Partitions (NPCR) and the last one is based on Coverage Rate of Partition (PCR). Coverage rate of partition and coverage rate of neighbor partition are two new introduced parameters, which can be used for MF generation. In addition, this paper proposes a new MF generation algorithm, called Fuzzy Entropy Based Fuzzy Partitioning (FEBFP), which is a specific version of the proposed two-step algorithm with some modifications. FEBFP uses fuzzy entropy of partition to generate MFs and involves the parameters of MFs in the process of MF generation to combine two steps of the algorithm. Non-parametric statistical tests are used to compare Fuzzy Decision Trees (FDTs) induced using the MFs generated by the proposed methods (employing different discretization algorithms as well as four MF generation methods). Experimental results show that eight methods outperform the others in terms of both accuracy and number of nodes. Among them, trapezoidal MFs that are defined by PCR on partitions generated by Zeta discretization algorithm, outperform the others when the accuracy and complexity of FDT have the same degree of importance. Moreover, the results show that the PCR and NPCR MF definition methods perform better than the other ones.

A new method for finding fuzzy information granules from multivariate data through a gravitational inspired clustering algorithm is proposed in this paper. The proposed algorithm incorporates the theory of granular computing, which adapts the cluster size with respect to the context of the given data. Via an inspiration in Newton’s law of universal gravitation, both conditions of clustering similar data and adapting to the size of each granule are achieved. This paper compares the Fuzzy Granular Gravitational Clustering Algorithm (FGGCA) against other clustering techniques on two grounds: classification accuracy, and clustering validity indices, e.g. Rand, FM, Davies–Bouldin, Dunn, Homogeneity, and Separation. The FGGCA is tested with multiple benchmark classification datasets, such as Iris, Wine, Seeds, and Glass identification.

The aim of this paper is to correct and improve some results obtained in the paper “Quantitative logic” [Information Sciences 179 (2009) 226–247].

In a (k,n) visual cryptography scheme (VCS), the dealer encodes the secret into n shadow images. Each pixel of the secret image is “expanded” into m sub-pixels in each share. In a (k,n)-VCS, the secret can be visually reconstructed when k or more shares are available. The reconstruction process employs the human visual system and no computations are required. To solve the pixel expansion problem of VCSs, probabilistic VCSs are directly converted from VCSs with no pixel expansion. Another well-known secret image sharing scheme, random grid (RG), is also provided with this novel stacking-to-see property. Compared with VCS, the most appealing benefit of RG is that there is no pixel expansion. In this paper, we use the probabilistic VCS without pixel expansion, to study the construction and performance of RG. This paper has two main results: (i) We show that each step of the share generation process in all existing (2,2)-RG, (2,n)-RG, (n, n)-RG, (k,n)-RG, incremental RG can be mapped to a corresponding step in PVCSs, and their shadow images between PVCS and RG are perfectly indistinguishable and the reconstructed images are the same, also include our (2,n) RG. (ii) From the quality of reconstructed image, pixel expansion, recognized region size, and image types to be considered for evaluating PVCSs and RGs, we point out that RG and PVCS have no difference other than the terminology. Furthermore, RGs is a subset of PVCSs.

Many methods based on the rough set theory to deal with information systems have been proposed in recent decades. In practice, some information systems are based on dominance relations and may be inconsistent because of various factors. Moreover, taking the imprecise evaluations and assignments in the description of objects into account, single-valued information systems have been generalized to interval-valued information systems. In this paper, by introducing a dominance relation to interval-valued ordered information systems, we establish a dominance-based rough set approach, which is mainly based on substitution of the indiscernibility relation by the dominance relation. To extract the minimal decision rules, approximate distribution reducts are proposed in inconsistent interval-valued ordered decision tables. This paper presents a theoretical method based on the discernibility matrix to enumerate all reducts and a practical approach on the basis of significance to find one reduct. And two equivalent definitions of approximate distribution reducts are also introduced. In addition, numerical examples are employed to examine the validity of the approaches proposed in this paper.

DNA watermarking is a technique for copyright protection and ownership authentication of DNA sequences and ensures the security of private genetic information. This paper addresses issues regarding watermarking DNA coding sequences in the frequency domain that confer mutation resistance, amino acid conservation, and security. Multimedia watermarking is designed for robustness and invisibility mainly based on frequency domain representations. However, frequency domain watermarking for a coding DNA sequence is significantly constrained because the transformation and inverse transformation must be performed while completely conserving the amino acid sequence. In this paper, we present a coding DNA watermarking method in a lifting-based discrete wavelet transform (DWT) domain that focuses on the feasibility of frequency domain watermarking for DNA sequences. Our method divides a coding DNA sequence into a number of subsequences and allocates all codons in subsequences to a numerical code using the histogram ranks of the amino acids. Our method then calculates a set of DWT coefficients for subsequences of synonymous codons and finds a subsequence among them with DWT coefficients that are optimal for embedding watermark bits. Finally, our method substitutes this sequence for a subsequence of codons. To secure the watermark, our method generates the binary watermark based on nonlinear congruential – pseudorandom number generator (NC-PRNG) and randomly selects the embeddable position in the DWT domain of the subsequence. We experimentally verified that our method ensures not only amino acid conservation and security but also resists a point mutation rate of approximately 18.5% point mutations.

Because precision and grade act as fundamental quantitative information in approximation space, they are used in relative and absolute quantifications, respectively. At present, the double quantification regarding precision and grade is a novel and valuable subject, but quantitative information fusion has become a key problem. Thus, this paper constructs the double-quantitative approximation space of precision and grade (PG-Approx-Space) and tackles the fusion problem using normal logical operations. It further conducts double-quantification studies on granular computing and rough set models. (1) First, for quantitative information organization and storage, we construct space and plane forms of PG-Approx-Space using the Cartesian product, and for quantitative information extraction and fusion, we establish semantics construction and semantics granules of PG-Approx-Space. (2) Second, by granular computing, we investigate three primary granular issues: quantitative semantics, complete system and optimal calculation. Accordingly, six types of fundamental granules are proposed based on the semantic, microscopic and macroscopic descriptions; their semantics, forms, structures, calculations and relationships are studied, and the granular hierarchical structure is achieved. (3) Finally, we investigate rough set models in PG-Approx-Space. Accordingly, model regions are proposed by developing the classical regions, model expansion is systematically analyzed, some models are constructed as their structures are obtained, and a concrete model is provided. Based on the quantitative information architecture, this paper systematically conducts and investigates double quantification and establishes a fundamental and general exploration framework.

This paper focuses on three types of attribute reducts in inconsistent decision tables: assignment reduct, distribution reduct, and maximum distribution reduct. It is quite inconvenient to judge these three types of reduct directly according to their definitions. This paper proposes judgment theorems for the assignment reduct, the distribution reduct and the maximum distribution reduct, which are expected to greatly simplify the judging of these three types of reducts. On this basis, we derive three new types of attribute significance measures and construct the Q-ARA (Quick Assignment Reduction Algorithm), the Q-DRA (Quick Distribution Reduction Algorithm), and the Q-MDRA (Quick Maximum Distribution Reduction Algorithm). These three algorithms correspond to the three types of reducts. We conduct a series of comparative experiments with twelve UCI (machine learning data repository, University of California at Irvine) data sets (including consistent and inconsistent decision tables) to evaluate the performance of the three reduction algorithms proposed with the relevant algorithm QuickReduct [9,34]. The experimental results show that QuickReduct possesses weak robustness because it cannot find the reduct even for consistent data sets, whereas our proposed three algorithms show strong robustness because they can find the reduct for each data set. In addition, we compare the Q-DRA (Quick Distribution Reduction Algorithm) with the CEBARKNC (conditional entropy-based algorithm for reduction of knowledge without a computing core) [43] because both find the distribution reduct by using a heuristic search. The experimental results demonstrate that Q-DRA runs faster than CEBARKNC does because the distribution function of Q-DRA has a lower calculation cost. Instructive conclusions for these reduction algorithms are drawn from the perspective of classification performance for the C4.5 and RBF-SVM classifiers. Last, we make a comparison between discernibility matrix-based methods and our algorithms. The experimental results indicate that our algorithms are efficient and feasible.

Rank correlation measures are intended to measure to which extent there is a monotonic association between two observables. While they are mainly designed for ordinal data, they are not ideally suited for noisy numerical data. In order to better account for noisy data, a family of rank correlation measures has previously been introduced that replaces classical ordering relations by fuzzy relations with smooth transitions-thereby ensuring that the correlation measure is continuous with respect to the data. The given paper briefly repeats the basic concepts behind this family of rank correlation measures and investigates it from the viewpoint of robust statistics. Then, on this basis, we introduce a framework of novel rank correlation tests. An extensive experimental evaluation using a large number of simulated data sets is presented which demonstrates that the new tests indeed outperform the classical variants in terms of type II error rates without sacrificing good performance in terms of type I error rates. This is mainly due to the fact that the new tests are more robust to noise for small samples. The Gaussian rank correlation estimator turned out to be the best choice in situations where no prior knowledge is available about the data, whereas the new family of robust gamma test provides an advantage in situations where information about the noise distribution is available. An implementation of all robust rank correlation tests used in this paper is available as an R package from the CRAN repository.

CCI - Centre for Computational Intelligence NOTICE: this is the author’s version of a work that was accepted for publication in Information Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version can be found by following the DOI The work reported in this paper addresses the challenge of the efficient and accurate defuzzification of discretised generalised type-2 fuzzy sets as created by the inference stage of a Mamdani Fuzzy Inferencing System. The exhaustive method of defuzzification for type-2 fuzzy sets is extremely slow, owing to its enormous computational complexity. Several approximate methods have been devised in response to this defuzzification bottleneck. In this paper we begin by surveying the main alternative strategies for defuzzifying a generalised type-2 fuzzy set: (1) Vertical Slice Centroid Type-Reduction; (2) the sampling method; (3) the elite sampling method; and (4) the $\alpha$-planes method. We then evaluate the different methods experimentally for accuracy and efficiency. For accuracy the exhaustive method is used as the standard. The test results are analysed statistically by means of the Wilcoxon Nonparametric Test and the elite sampling method shown to be the most accurate. In regards to efficiency, Vertical Slice Centroid Type-Reduction is demonstrated to be the fastest technique.

Estimation of distribution algorithms (EDAs) identify linkages among genes and build models which decompose a given problem. EDAs have been successfully applied to many real-world problems; however, whether their models indicate the optimal way to decompose the given problem is rarely studied. This paper proposes using the number of function evaluations (N"f"e) as the performance measure of EDA models. As a result, the optimal model can be defined as the one that consumes the fewest N"f"e on average for EDAs to solve a specific problem. Based on this concept, correct building blocks (BBs) can be defined as groups of genes that construct the optimal model. Similarly, linkages within a BB are defined as the correct linkages of which the specific problem consists. The capabilities of four commonly used linkage-learning metrics, nonlinearity, entropy, simultaneity and differential mutual complement, are investigated based on the above definitions. For certain partially separable problems, none of the above metrics yields difference that is statistically significant between linear and nonlinear gene pairs. Although an optimal threshold still exists to separate linear and nonlinear gene pairs, most existing EDA designs today have not yet characterize such threshold. Based on the idea of N"f"e estimation, this paper also proposes a metric enhancer, named eNFE, to enhance existing linkage-learning techniques. Empirical results show that eNFE improves BB identification by eliminating spurious linkages which occur often in most existing EDAs.

In many applications, top-k join is an important operation to return the k most important join tuples among the potentially huge answer space according to a given ranking function. PBRJ is an algorithm template that generalizes previous top-k join algorithms. In this paper, our analysis shows that PBRJ needs to maintain a large quantity of candidate tuples on massive data. Based on the analysis, this paper proposes a novel top-k join algorithm TJJE which is suitable for handling massive data. By some pre-computed information, TJJE first estimates an upper-bound on scan depth of each joined table. Then it determines the file that contains the join positional index pairs of the top-k join results. A novel algorithm is proposed to retrieve the required join tuples by a single sequential and selective scan on the joined tables. Finally, the top-k join results are obtained by a single scan on the retrieved join tuples. The correctness proof and cost analysis of TJJE are presented in this paper. Extensive experiments show that TJJE maintains up to three orders of magnitude fewer candidate tuples and obtains up to one order of magnitude speedup compared to PBRJ.

Latent Semantic Indexing (LSI) with Singular Value Decomposition (SVD) is an effective dimension reduction method for document classification and other information analysis tasks. The computational overhead of SVD is known to be a bottleneck in dealing with large data sets, and faster dimension reduction with competitive accuracy is desired in such a setting. This paper presents Imprecise Spectrum Analysis (ISA) to carry out fast dimension reduction for document classification. ISA follows the one-sided Jacobi method for computing SVD and simplifies its intensive orthogonality computation. It uses a representative matrix composed of top-k column vectors derived from the original feature vector space and reduces the dimension of a feature vector by computing its product with this representative matrix. The paper provides an analysis to show the approximation error and the rationale behind such a dimension reduction method. To further improve classification accuracy, this paper also presents a feature selection method in building the initial feature matrix and augments the representative matrix by including centroid vectors. Our extensive experimental results show that ISA is fast in handling large term-document feature matrices while delivering better or competitive classification accuracy for the tested benchmarks compared to LSI with SVD.

This paper is devoted to the study of an extension of dynamic programming approach which allows sequential optimization of approximate decision rules relative to the length and coverage. We introduce an uncertainty measure R(T) which is the number of unordered pairs of rows with different decisions in the decision table T. For a nonnegative real number @b, we consider @b-decision rules that localize rows in subtables of T with uncertainty at most @b. Our algorithm constructs a directed acyclic graph @D"@b(T) which nodes are subtables of the decision table T given by systems of equations of the kind ''attribute=value''. This algorithm finishes the partitioning of a subtable when its uncertainty is at most @b. The graph @D"@b(T) allows us to describe the whole set of so-called irredundant @b-decision rules. We can describe all irredundant @b-decision rules with minimum length, and after that among these rules describe all rules with maximum coverage. We can also change the order of optimization. The consideration of irredundant rules only does not change the results of optimization. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository.

This paper presents an invariant image watermarking scheme by introducing the Polar Harmonic Transform (PHT), which is a recently developed orthogonal moment method. Similar to Zernike moment (ZM) and pseudo-Zernike moment (PZM) approaches, PHT is defined on a circular domain. The magnitudes of PHTs are invariant to image rotation and scaling. Furthermore, the PHTs are free of numerical instability, so they are more suitable for watermarking. In this paper, the invariant properties of PHTs are investigated. During embedding, a subset of the accurate PHTs are modified according to the binary watermark sequence. Then a compensation image is formatted by reconstructing the modified PHT vector. The final watermarked image is obtained by adding the compensation image to the original image. In the decoder, the watermark can be retrieved from the magnitudes of the PHTs directly. Experimental results illustrate that the proposed scheme outperforms ZM/PZM based schemes in terms of embedding capacity and watermark robustness and is also robust to both geometric and signal processing based attacks.

Temporal coherence principle is an attractive biologically inspired learning rule to extract slowly varying features from quickly varying input data. In this paper we develop a new Nonlinear Neighborhood Preserving (NNP) technique, by utilizing the temporal coherence principle to find an optimal low dimensional representation from the original high dimensional data. NNP is based on a nonlinear expansion of the original input data, such as polynomials of a given degree. It can be solved by the eigenvalue problem without using gradient descent and is guaranteed to find the global optimum. NNP can be viewed as a nonlinear dimensionality reduction framework which takes into consideration both time series and data sets without an obvious temporal structure. According to different situations, we introduce three algorithms of NNP, named NNP-1, NNP-2, and NNP-3. The objective function of NNP-1 is equal to Slow Feature Analysis (SFA), and it works well for time series such as image sequences. NNP-2 artificially constructs time series consisting of neighboring points for data sets without a clear temporal structure such as image data. NNP-3 is proposed for classification tasks, which can minimize the distances of neighboring points in the embedding space and ensure that the remaining points are as far apart as possible simultaneously. Furthermore, the kernel extension of NNP is also discussed in this paper. The proposed algorithms work very well on some image sequences and image data sets compared to other methods. Meanwhile, we perform the classification task on the MNIST handwritten digit database using the supervised NNP algorithms. The experimental results demonstrate that NNP is an effective technique for nonlinear dimensionality reduction tasks.

Methods of fuzzy rule extraction based on rough set theory are rarely reported in incomplete interval-valued fuzzy information systems. Thus, this paper deals with such systems. Instead of obtaining rules by attribute reduction, which may have a negative effect on inducting good rules, the objective of this paper is to extract rules without computing attribute reducts. The data completeness of missing attribute values is first presented. Positive and converse approximations in interval-valued fuzzy rough sets are then defined, and their important properties are discussed. Two algorithms based on positive and converse approximations, namely, mine rules based on the positive approximation (MRBPA) and mine rules based on the converse approximation (MRBCA), are proposed for rule extraction. The two algorithms are evaluated by several data sets from the UC Irvine Machine Learning Repository. The experimental results show that MRBPA and MRBCA achieve better classification performances than the method based on attribute reduction.

In this paper, a new algorithm is developed to reduce the computational complexity of Ward's method. The proposed approach uses a dynamic k-nearest-neighbor list to avoid the determination of a cluster's nearest neighbor at some steps of the cluster merge. Double linked algorithm (DLA) can significantly reduce the computing time of the fast pairwise nearest neighbor (FPNN) algorithm by obtaining an approximate solution of hierarchical agglomerative clustering. In this paper, we propose a method to resolve the problem of a non-optimal solution for DLA while keeping the corresponding advantage of low computational complexity. The computational complexity of the proposed method DKNNA+FS (dynamic k-nearest-neighbor algorithm with a fast search) in terms of the number of distance calculations is O(N^2), where N is the number of data points. Compared to FPNN with a fast search (FPNN+FS), the proposed method using the same fast search algorithm (DKNNA+FS) can reduce the computing time by a factor of 1.90-2.18 for the data set from a real image. In comparison with FPNN+FS, DKNNA+FS can reduce the computing time by a factor of 1.92-2.02 using the data set generated from three images. Compared to DLA with a fast search (DLA+FS), DKNNA+FS can decrease the average mean square error by 1.26% for the same data set.

It is considered to be the most suitable solution for large scale elections to design an electronic voting scheme using blind signatures and anonymous channels. Based on this framework, Okamoto first proposed a receipt-free voting scheme [30] for large scale elections. However, in the following paper, Okamoto [31] proved that the scheme [30] was not receipt-free and presented two improved schemes. One scheme requires the help of the parameter registration committee and the other needs a stronger physical assumption of the voting booth. In this paper, we utilize the double-trapdoor commitment to propose a new receipt-free voting scheme based on blind signatures for large scale elections. Neither the parameter registration committee nor the voting booth is required in our scheme. We also present a more efficient zero-knowledge proof for secret permutation. Therefore, our scheme is much more efficient than Okamoto's schemes [30,31] with the weaker physical assumptions. Moreover, we prove that our scheme can achieve the desired security properties.

This paper presents an efficient algorithm, called pattern reduction (PR), for reducing the computation time of k-means and k-means-based clustering algorithms. The proposed algorithm works by compressing and removing at each iteration patterns that are unlikely to change their membership thereafter. Not only is the proposed algorithm simple and easy to implement, but it can also be applied to many other iterative clustering algorithms such as kernel-based and population-based clustering algorithms. Our experiments-from 2 to 1000 dimensions and 150 to 10,000,000 patterns-indicate that with a small loss of quality, the proposed algorithm can significantly reduce the computation time of all state-of-the-art clustering algorithms evaluated in this paper, especially for large and high-dimensional data sets.

In this paper an age-structured population growth model, based on a fuzzy cellular structure, is proposed. An age-structured population growth model enables a better description of population dynamics. In this paper, the dynamics of a particular bird species is considered. The dynamics is governed by the variation of natality, mortality and emigration rates, which in this work are evaluated using an interval type-2 fuzzy logic system. The use of type-2 fuzzy logic enables handling the effects caused by environment heterogeneity on the population. A set of fuzzy rules, about population growth, are derived from the interpretation of the ecological laws and the bird life cycle. The proposed model is formulated using discrete mathematics within the framework of a fuzzy cellular structure. The fuzzy cellular structure allows us to visualize the evolution of the population's spatial dynamics. The spatial distribution of the population has a deep effect on its dynamics. Moreover, the model enables not only to estimate the percentage of occupation on the cellular space when the species reaches its stable equilibrium level, but also to observe the occupation patterns.

In this paper we study logical properties of the operation chance discovery (CD) via structures based on special Kripke/Hintikka models. These models use as bases partially ordered sets of indexes (indexes of steps in a computation, or ones indicating time points in a time flow), and clusters of states associated to each index. The language chosen to build the logical formulas includes modal/temporal operations, operations for the agents' knowledge, local and global operations for CD, operation of local common knowledge, and an operation for chance of discovery via agents' interactions. We introduce and study a logic (of knowledge and discovery via interaction of agents), LDK"a, which is defined by semantics, as the set of all formulas that are valid in all suggested models. The paper provides an algorithm to recognize logical laws (and satisfiable formulas) of LDK"a. The algorithm replaces a formula with a rule in a special, so-called reduced normal form, and, then it verifies the validity of this rule in specific models of exponential size in the size of the rule. We show that the problem of computing the true logical laws of LDK"a is decidable.

The current research progress and the existing problems of uncertain or imprecise knowledge representation and reasoning in description logics are analyzed in this paper. Approximate concepts are introduced to description logics based on rough set theory, and a kind of new rough description logic RDL AC (rough description logic based on approximate concepts) is proposed based on approximate concepts. The syntax, semantics and properties of the RDL AC are given. It is proved that the approximate concept satisfiability (definitely satisfiability and possibly satisfiability) reasoning problem and approximate concepts rough subsumption reasoning problem w.r.t. rough TBox in RDL AC may be reduced to the concept satisfiability reasoning problem in (almost) standard ALC (the description logic that provides the Boolean concept constructors plus the existential and universal restriction constructors). The works of this paper provide logic foundations for approximate ontologies and theoretical foundations for reasoning algorithms of more expressive rough description logics including approximate concepts, number restrictions, nominals, inverse roles and role hierarchies.

This paper discusses the full implication inference of fuzzy reasoning. For all residuated implications induced by left continuous t-norms, unified @a-triple I algorithms are constructed to generalize the known results. As the corollaries of the main results of this paper, some special algorithms can be easily derived based on four important residuated implications. These algorithms would be beneficial to applications of fuzzy reasoning. Based on properties of residuated implications, the proofs of the many conclusions are greatly simplified.

This paper investigates a novel multi-objective model for a no-wait flow shop scheduling problem that minimizes both the weighted mean completion time (C¯w) and weighted mean tardiness (T¯w). Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new hybrid multi-objective algorithm based on the features of a biological immune system (IS) and bacterial optimization (BO) to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective immune algorithm (HMOIA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various metrics, is compared against five prominent multi-objective evolutionary algorithms: PS-NC GA, NSGA-II, SPEA-II, MOIA, and MISA. Our computational results suggest that our proposed HMOIA outperforms the five foregoing algorithms, especially for large-sized problems.

This paper addresses the problem of timestamped event sequence matching, a new type of similar sequence matching that retrieves the occurrences of interesting patterns from timestamped sequence databases. The sequential-scan-based method, the trie-based method, and the method based on the iso-depth index are well-known approaches to this problem. In this paper, we point out their shortcomings, and propose a new method that effectively overcomes these shortcomings. The proposed method employs an R ∗ -tree, a widely accepted multi-dimensional index structure that efficiently supports timestamped event sequence matching. To build the R ∗ -tree, this method extracts time windows from every item in a timestamped event sequence and represents them as rectangles in n -dimensional space by considering the first and last occurring times of each event type. Here, n is the total number of disparate event types that may occur in a target application. To resolve the dimensionality curse in the case when n is large, we suggest an algorithm for reducing the dimensionality by grouping the event types. Our sequence matching method based on the R ∗ -tree performs with two steps. First, it efficiently identifies a small number of candidates by searching the R ∗ -tree. Second, it picks out true answers from the set of candidates. We prove its robustness formally, and also show its effectiveness via extensive experiments.

Previous algorithms for unrestricted constraint satisfaction use reduction search, which inferentially removes values from domains in order to prune the backtrack search tree. This paper introduces partition search, which uses an efficient join mechanism instead of removing values from domains. Analytical prediction of quantitative performance of partition search appears to be intractable and evaluation therefore has to be by experimental comparison with reduction search algorithms that represent the state of the art. Instead of working only with available reduction search algorithms, this paper introduces enhancements such as semijoin reduction preprocessing using Bloom filtering.

A Modified Direct Method for the computation of the Zernike moments is presented in this paper. The presence of many factorial terms, in the direct method for computing the Zernike moments, makes their computation process a very time consuming task. Although the computational power of the modern computers is impressively increasing, the calculation of the factorial of a big number is still an inaccurate numerical procedure. The main concept of the present paper is that, by using Stirling's Approximation formula for the factorial and by applying some suitable mathematical properties, a novel, factorial-free direct method can be developed. The resulted moments are not equal to those computed by the original direct method, but they are a sufficiently accurate approximation of them. Besides, their variability does not affect their ability to describe uniquely and distinguish the objects they represent. This is verified by pattern recognition simulation examples.

This paper deals with the design and implementation of a novel image sharpness metric based on the statistical approach. This sharpness metric is derived by modelling the image sharpness problem as a generalized eigenvalues problem. This problem is solved using Rayleigh quotient optimization where relevant statistical information of an image is extracted and then represented through a series of eigenvalues. The novelty of this paper comes from the application of eigenvalues in image sharpness metric formulation to provide robust assessment with the presence of various blur and noisy conditions. Firstly, the input image is normalized by its energy to minimize the effects caused by image contrast. Secondly, the covariance matrix is computed from this normalized image before it is diagonalized using Singular Values Decomposition (SVD) to obtain a series of eigenvalues. Finally, the image sharpness of the normalized image is determined by the trace of the first several eigenvalues. The performance of the proposed metric is gauged by comparing with several objective image sharpness metrics. Experimental results using synthetic and real images with known and unknown distortion conditions show the robustness and feasibility of the proposed metric in providing relative image sharpness. In particular, the proposed metric provides wider working range and more precise prediction consistency under all tested deformation conditions although it is slightly expensive in terms of computation than other metrics.

In this paper, we introduce an extended ring signature scheme in which the actual signer has the ability to admit to having signed a document at his will. Generally speaking, this scheme can be considered as an extension and improvement of the ring signature suggested by Rivest et al. in 2001. The proposed scheme is called signer-admission ring signature which combines the idea of the designated confirmer signatures proposed by Chaum in 1994 and the designated verifier proofs proposed by Jakobsson et al. in 1996. This paper presents a scenario explaining why the signer-admission property is valuable in real-life applications. An actual signer may possibly want to expose himself if, in doing so, he will acquire an enormous benefit. Here, we propose a generic construction of the signer-admission ring signature as well as a demonstration modified from Rivest et al.'s scheme to achieve signer-admission.

The centroid of an interval type-2 fuzzy set (IT2 FS) provides a measure of the uncertainty of such a FS. Its calculation is very widely used in interval type-2 fuzzy logic systems. In this paper, we present properties about the centroid of an IT2 FS. We also illustrate many of the general results for a T2 fuzzy granule (FG) in order to develop some understanding about the uncertainty of the FG in terms of its vertical and horizontal dimensions. At present, the T2 FG is the only IT2 FS for which it is possible to obtain closed-form formulas for the centroid, and those formulas are in this paper.

An approach to solving optimization problems with fuzzy coefficients in objective functions and constraints is described. It consists in formulating and solving one and the same problem within the framework of mutually related models with constructing equivalent analogs with fuzzy coefficients in objective functions alone. It enables one to maximally cut off dominated alternatives ''from below'' as well as ''from above''. Since the approach is applied within the context of fuzzy discrete optimization problems, several modified algorithms of discrete optimization are discussed. These algorithms are associated with the method of normalized functions, are based on a combination of formal and heuristic procedures, and allow one to obtain quasi-optimal solutions after a small number of steps, thus overcoming the computational complexity posed the NP-completeness of discrete optimization problems. The subsequent contraction of the decision uncertainty regions is associated with reduction of the problem to multiobjective decision making in a fuzzy environment with using techniques based on fuzzy preference relations. The techniques are also directly applicable to situations in which the decision maker is required to choose alternatives from a set of explicitly available alternatives. The results of the paper are of a universal character and can be applied to the design and control of systems and processes of different purposes as well as the enhancement of corresponding CAD/CAM systems and intelligent decision making systems. The results of the paper are already being used to solve problems of power engineering.