Search

Dynamic data in real-time application are typically updating in a multi-dimensional manner. In this paper, we introduce a novel approach based on Dominance-based Rough Set Approach (DRSA) to efficiently deal with the multi-dimensional variations of attribute set and attribute values in dynamic Ordered Information Systems (OIS). We improve the original notion of the P-generalized decision domains to make the feature value matrix be dominance symmetrical, and propose an efficient strategy based on the improved notion to obtain the dominance feature matrix. Then, we employ the dominance-feature-matrix-based incremental strategy to avoid repeated comparisons between original attributes, so that to efficiently update rough approximations of DRSA with the simultaneously increased attribute set and varied attribute values. In our approach, the steps based on these two combined strategies can work altogether or separately, not only efficiently dealing with the simultaneously increased attribute set and varied attribute values, but also efficiently dealing with the individually increased attribute set or varied attribute values in dynamic OIS. Efficient algorithm based on the updating strategies is designed and multiple groups of experiments are conducted. Experimental results on different real-world data sets show that the proposed algorithm is much faster than other algorithms for dealing with the multi-dimensional or the single-dimensional variations of attribute set and attribute values. [ABSTRACT FROM AUTHOR]

The concept of SCN offers a fast framework with universal approximation guarantee for lifelong learning of non-stationary data streams. Its adaptive scope selection property enables for proper random generation of hidden unit parameters advancing conventional randomized approaches constrained with a fixed scope of random parameters. This paper proposes deep stacked stochastic configuration network (DSSCN) for continual learning of non-stationary data streams which contributes two major aspects: 1) DSSCN features a self-constructing methodology of deep stacked network structure where hidden unit and hidden layer are extracted automatically from continuously generated data streams; 2) the concept of SCN is developed to randomly assign inverse covariance matrix of multivariate Gaussian function in the hidden node addition step bypassing its computationally prohibitive tuning phase. Numerical evaluation and comparison with prominent data stream algorithms under two procedures: periodic hold-out and prequential test-then-train processes demonstrate the advantage of proposed methodology. [ABSTRACT FROM AUTHOR]

Diversity estimation of Pareto front (PF) approximations is a critical issue in the field of evolutionary multiobjective optimization. However, the existing diversity indicators are usually inappropriate for PF approximations with more than three objectives. Many of them can be utilized only when compared with approximations obtained by multiple multiobjective optimizers, which makes them difficult to use online. In this paper, we propose a unary diversity indicator based on reference vectors (DIR) to estimate the diversity of PF approximations for many-objective optimization. In DIR, a set of uniform and widespread reference vectors are generated. The coverage of each solution in the objective space is evaluated by the number of representative reference vectors it is associated with. The diversity (both spread and uniformity) is determined by the standard deviation of the coverage for all the solutions. The smaller value of DIR, the better the diversity of a PF approximation is. DIR can be applied to a unary approximation without any compared approximations needed. Thus, DIR is easy to use as either an offline indicator to estimate the performance of an optimizer or an online indicator for the selection of solutions in a MOEA. In the experimental studies, both the artificial and the real PF approximations generated by seven different many-objective algorithms are used to verify DIR as an offline indicator. The effects of the number of reference vectors on DIR are also investigated. In addition, as an online indicator, DIR is integrated into a Pareto-dominance-based evolutionary multiobjective optimizer, NSGA-II. The experimental studies show it has the significant performance enhancements over the original NSGA-II on many-objective optimization problems. [ABSTRACT FROM AUTHOR]

Abstract: 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 β, we consider β-decision rules that localize rows in subtables of T with uncertainty at most β. Our algorithm constructs a directed acyclic graph Δ β (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 β. The graph Δ β (T) allows us to describe the whole set of so-called irredundant β-decision rules. We can describe all irredundant β-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. [Copyright &y& Elsevier]

Random Vector Functional-link (RVFL) networks, a class of learner models, can be regarded as feed-forward neural networks built with a specific randomized algorithm, i.e., the input weights and biases are randomly assigned and fixed during the training phase, and the output weights are analytically evaluated by the least square method. In this paper, we provide some insights into RVFL networks and highlight some practical issues and common pitfalls associated with RVFL-based modelling techniques. Inspired by the folklore that “all high-dimensional random vectors are almost always nearly orthogonal to each other”, we establish a theoretical result on the infeasibility of RVFL networks for universal approximation, if a RVFL network is built incrementally with random selection of the input weights and biases from a fixed scope, and constructive evaluation of its output weights. This work also addresses the significance of the scope setting of random weights and biases in respect to modelling performance. Two numerical examples are employed to illustrate our findings, which theoretically and empirically reveal some facts and limits of such class of randomized learning algorithms. [ABSTRACT FROM AUTHOR]

Ordered data widely exists in practical problems. Dominance-based Rough Set Approach (DRSA) is an effective mathematical tool to obtain approximations of concepts and discovery knowledge from ordered data. In this paper, we focus on the dynamic DRSA for the multi-dimensional variation of an ordered information system, and propose a novel incremental simplified algorithm which can efficiently update approximations of DRSA when objects and attributes increase simultaneously. Most of existing algorithms can efficiently deal with the single-dimensional variation of an information system. However, multi-dimensional variations often occur in real dynamic data. That is, the object set, the attribute set or attribute values of an information system often vary simultaneously. Although we can directly use the definitions of approximations, or integrate some single-dimensional incremental algorithms to cope with multi-dimensional variations, this always results in complex algorithm architectures and a large amount of inefficient computation. In our works, by simplifying traditional definitions of DRSA and employing the incremental learning strategy, we develop an algorithm to neglect unnecessary parameters and avoid much redundant computation. Then, we present two different storage schemes for our proposed algorithm to solve the problem of memory consumption. Finally, a series of experiments are conducted to evaluate its efficiency. Experimental results clearly show that for the two-dimensional variation of objects and attributes in an ordered information system, our proposed algorithm is much faster not only than the non-incremental algorithm based on traditional definitions, but also than the integration of two single-dimensional incremental algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Reflexive boundary conditions (BCs) assume that the array values outside the viewable region are given by a symmetry of the array values inside. The reflection guarantees the continuity of the image. In fact, there are usually two choices for the symmetry: symmetry around the meshpoint and symmetry around the midpoint. The first is called whole-sample symmetry in signal and image processing, the second is half-sample. Many researchers have developed some fast algorithms for the problems of image restoration with the half-sample symmetric BCs over the years. However, little attention has been given to the whole-sample symmetric BCs. In this paper, we consider the use of the whole-sample symmetric boundary conditions in image restoration. The blurring matrices constructed from the point spread functions (PSFs) for the BCs have block Toeplitz-plus-PseudoHankel with Toeplitz-plus-PseudoHankel blocks structures. Recently, regardless of symmetric properties of the PSFs, a technique of Kronecker product approximations was successfully applied to restore images with the zero BCs, half-sample symmetric BCs and anti-reflexive BCs, respectively. All these results extend quite naturally to the whole-sample symmetric BCs, since the resulting matrices have similar structures. It is interesting to note that when the size of the true PSF is small, the computational complexity of the algorithm obtained for the Kronecker product approximation of the resulting matrix in this paper is very small. It is clear that in this case all calculations in the algorithm are implemented only at the upper left corner submatrices of the big matrices. Finally, detailed experimental results reporting the performance of the proposed algorithm are presented. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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 (rough description logic based on approximate concepts) is proposed based on approximate concepts. The syntax, semantics and properties of the 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 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. [Copyright &y& Elsevier]

This paper attempts to provide a new solution to the model approximation problem for dynamic systems with time-varying delays under the fuzzy framework. For a given high-order system, our focus is on the construction of a reduced-order model, which approximates the original one in a prescribed error performance level and guarantees the asymptotic stability of the corresponding error system. Based on the reciprocally convex technique, a less conservative stability condition is established for the dynamic error system with a given error performance index. Furthermore, the reduced-order model is eventually obtained by applying the projection approach, which converts the model approximation into a sequential minimization problem subject to linear matrix inequality constraints by employing the cone complementary linearization algorithm. Finally, two numerical examples are provided to illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper is concerned with the approximate solution of Hamilton–Jacobi–Isaacs (HJI) equation for constrained-input nonlinear continuous-time systems with unknown dynamics. We develop a novel online adaptive dynamic programming-based algorithm to learn the solution of the HJI equation. The present algorithm is implemented via an identifier-critic architecture, which consists of two neural networks (NNs): an identifier NN is applied to estimate the unknown system dynamics and a critic NN is constructed to obtain the approximate solution of the HJI equation. An advantage of the proposed architecture is that the identifier NN and the critic NN are tuned simultaneously. With introducing two additional terms, namely, the stabilizing term and the robustifying term to update the critic NN, the initial stabilizing control is no longer required. Meanwhile, the developed critic tuning rule not only ensures convergence of the critic to the optimal saddle point but also guarantees stability of the closed-loop system. Moreover, the uniform ultimate boundedness of the weights of the identifier NN and the critic NN are proved by using Lyapunov’s direct method. Finally, to illustrate the effectiveness and applicability of the developed approach, two simulation examples are provided. [ABSTRACT FROM AUTHOR]

Covering rough sets generalize classical rough sets by relaxing partitions of the universe to coverings. The existing research of covering rough sets mainly concentrates on comparing of different kinds of approximation operators and designing algorithms for attribute reductions of decision systems. Less efforts have been made in measurements of covering rough sets. To enrich this field, in this paper we investigate the measurements of covering rough sets based on granules and evidence theory, which can be used to solve more complex practical problems. Firstly, it is shown that the most common sixteen pairs of covering approximation operators can be grouped into five pairs of dual covering approximation operators and six pairs of non-dual covering approximation operators according to definitions based on element, granule, and subsystem. Secondly, we define the rough degree and precision for the purpose of characterizing the uncertainty of these summarized covering approximation operators under a unified framework. The underlying uncertainty of covering rough sets results from the roughness of granulation of coverings. Finally, we investigate the relationships between the covering approximation operators and evidence theory. It shows that some kinds of covering approximation operators can be characterized by belief and plausibility functions, while others do not share this property. The sufficient conditions under which covering approximation operators can be measured by belief and plausibility functions are further explored, and the corresponding counterexamples are given to illustrate those that cannot be measured. Based on above discussions, we develop a basic framework of numerical characterization on measurements of covering rough sets with granules and evidence theory. [ABSTRACT FROM AUTHOR]

Abstract: Swapped Networks (SNs) are a family of two-level interconnection networks, suitable for constructing large parallel and distributed systems. In this paper, the Minimum Dominating Set (MDS) problem and the Minimum Connected Dominating Set (MCDS) problem in SNs are investigated based on the connectivity rule of SNs. We prove the two problems in SNs are -hard, and present two efficient algorithms for building dominating sets and connected dominating sets in SNs. The proposed algorithms use as input a given (connected) dominating set of the factor network, and yield a good approximation of an MDS or MCDS for the SN provided that the input is a good approximation of an MDS or MCDS for the factor network. We also derive several non-trivial bounds on the (connected) domination parameters of SNs. We believe this work is of theoretical interest in graph theory since SNs form a family of graphs. It may also motivate further research on dominating problems in SNs with their potential applications. [Copyright &y& Elsevier]

Abstract: Establishing consistent correspondences between two sets of features is a fundamental problem in computer vision. This problem can be well formulated as graph matching in which nodes and edges represent feature points and pairwise relationships between feature points, respectively. Spectral matching [19] is the state-of-the-art eigenvector-based method for graph matching. The spectral matching algorithm has been used successfully for small data, but its heavy memory requirement limited the maximum data sizes and contexts it can be used. In this paper, we propose FaSM, a fast and scalable approximate spectral matching algorithm. The main ideas are twofold. First, we exploit the redundancy in the data generation process to approximate the affinity matrix with the linear combination of Kronecker products between bases and index matrices. The bases and index matrices are highly compressed representation of the approximated affinity matrix, requiring much smaller memory than in previous works which store the whole affinity matrix. Second, we compute the eigenvector of the approximated affinity matrix using the small bases and index matrices without explicitly materializing the approximated matrix. Experimental results show that our proposed method is up to 33× faster, requiring up to 645× smaller memory than the exact algorithm, with little or no loss of accuracy. [Copyright &y& Elsevier]

Abstract: Massive data mining and knowledge discovery present a tremendous challenge with the data volume growing at an unprecedented rate. Rough set theory has been successfully applied in data mining. The lower and upper approximations are basic concepts in rough set theory. The effective computation of approximations is vital for improving the performance of data mining or other related tasks. The recently introduced MapReduce technique has gained a lot of attention from the scientific community for its applicability in massive data analysis. This paper proposes a parallel method for computing rough set approximations. Consequently, algorithms corresponding to the parallel method based on the MapReduce technique are put forward to deal with the massive data. An extensive experimental evaluation on different large data sets shows that the proposed parallel method is effective for data mining. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new bare-bones multi-objective particle swarm optimization algorithm to solve the environmental/economic dispatch problems. The algorithm has three distinctive features: a particle updating strategy which does not require tuning up control parameters; a mutation operator with action range varying over time to expand the search capability; and an approach based on particle diversity to update the global particle leaders. Several trials have been carried out on the IEEE 30-bus test system. By comparing with seven existing multi-objective optimization algorithms and three well-known multi-objective particle swarm optimization techniques, it is found that our algorithm is capable of generating excellent approximation of the true Pareto front and can be used to solve other types of multi-objective optimization problems. [Copyright &y& Elsevier]

Abstract: In this paper, the problems of fuzzy binary relations on fuzzy n-cell number space and their applications are investigated. Firstly, we have defined some fuzzy approximation relations on fuzzy n-cell number space, and studied their properties. Secondly, as application, we have developed an algorithmic version of classification in an imprecise or uncertain environment by using the fuzzy approximation relations. Practical examples are provided to show the application and rationality of the proposed techniques. [Copyright &y& Elsevier]

Abstract: In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions and analyses of convergence in multi-objective evolutionary algorithms (MOEAs), convergence with probability is easily obtained because diversity is not considered. However, diversity cannot be guaranteed. By combining the convergence with diversity, this paper presents a new definition for the finite representation of a Pareto set, the B-Pareto set, and a convergence metric for MOEAs. Based on a new archive-updating strategy, the convergence of one such MOEA to the B-Pareto sets of MOPs is proved. Numerical results show that the obtained B-Pareto front is uniformly distributed along the Pareto front when, according to the new definition of convergence, the algorithm is convergent. [Copyright &y& Elsevier]

Abstract: Identifying the most frequent elements in a data stream is a well known and difficult problem. Identifying the most frequent elements for each individual, especially in very large populations, is even harder. The use of fast and small memory footprint algorithms is paramount when the number of individuals is very large. In many situations such analysis needs to be performed and kept up to date in near real time. Fortunately, approximate answers are usually adequate when dealing with this problem. This paper presents a new and innovative algorithm that addresses this problem by merging the commonly used counter-based and sketch-based techniques for top-k identification. The algorithm provides the top-k list of elements, their frequency and an error estimate for each frequency value. It also provides strong guarantees on the error estimate, order of elements and inclusion of elements in the list depending on their real frequency. Additionally the algorithm provides stochastic bounds on the error and expected error estimates. Telecommunications customer’s behavior and voice call data is used to present concrete results obtained with this algorithm and to illustrate improvements over previously existing algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Artificial immune systems are a kind of new computational intelligence methods which draw inspiration from the human immune system. Most immune system inspired optimization algorithms are based on the applications of clonal selection and hypermutation, and known as clonal selection algorithms. These clonal selection algorithms simulate the immune response process based on principles of Darwinian evolution by using various forms of hypermutation as variation operators. The generation of new individuals is a form of the trial and error process. It seems very wasteful not to make use of the Baldwin effect in immune system to direct the genotypic changes. In this paper, based on the Baldwin effect, an improved clonal selection algorithm, Baldwinian Clonal Selection Algorithm, termed as BCSA, is proposed to deal with optimization problems. BCSA evolves and improves antibody population by four operators, clonal proliferation, Baldwinian learning, hypermutation, and clonal selection. It is the first time to introduce the Baldwinian learning into artificial immune systems. The Baldwinian learning operator simulates the learning mechanism in immune system by employing information from within the antibody population to alter the search space. It makes use of the exploration performed by the phenotype to facilitate the evolutionary search for good genotypes. In order to validate the effectiveness of BCSA, eight benchmark functions, six rotated functions, six composition functions and a real-world problem, optimal approximation of linear systems are solved by BCSA, successively. Experimental results indicate that BCSA performs very well in solving most of the test problems and is an effective and robust algorithm for optimization. [Copyright &y& Elsevier]

Abstract: The original rough set model was developed by Pawlak, which is mainly concerned with the approximation of sets described by a single binary relation on the universe. In the view of granular computing, the classical rough set theory is established through a single granulation. This paper extends Pawlak’s rough set model to a multi-granulation rough set model (MGRS), where the set approximations are defined by using multi equivalence relations on the universe. A number of important properties of MGRS are obtained. It is shown that some of the properties of Pawlak’s rough set theory are special instances of those of MGRS. Moreover, several important measures, such as accuracy measure , quality of approximation and precision of approximation , are presented, which are re-interpreted in terms of a classic measure based on sets, the Marczewski–Steinhaus metric and the inclusion degree measure. A concept of approximation reduct is introduced to describe the smallest attribute subset that preserves the lower approximation and upper approximation of all decision classes in MGRS as well. Finally, we discuss how to extract decision rules using MGRS. Unlike the decision rules (“AND” rules) from Pawlak’s rough set model, the form of decision rules in MGRS is “OR”. Several pivotal algorithms are also designed, which are helpful for applying this theory to practical issues. The multi-granulation rough set model provides an effective approach for problem solving in the context of multi granulations. [Copyright &y& Elsevier]

Abstract: This paper describes a new algorithm for the generation of pseudo random numbers with approximate self-similar structure. The Simple Self-Similar Sequences Generator (4SG) elaborates on an intuitive approach to obtain a fast and accurate procedure, capable of reproducing series of points exhibiting the property of persistence and anti-persistence. 4SG has a computational complexity of and memory requirements of the order of , where is the number of points to be generated. The accuracy of the algorithm is evaluated by means of computer-based simulations, recurring to several Hurst parameter estimators, namely Variance Time (VT) and the Wavelets-based estimator. The Hosking and the Wavelets-based methods for the generation of self-similar series were submitted to the same tests the 4SG was analysed with, providing for a basis for comparison of several performance aspects of the algorithm. Results show that the proposal embodies a good candidate not only for on-demand emulation of arbitrarily long self-similar sequences, but also for fast and efficient online simulations. [Copyright &y& Elsevier]

Abstract: This paper presents an approach based on an adaptive bio-inspired method to make state of the art clustering algorithms scalable and to provide them with an any-time behavior. The method is based on the biology-inspired paradigm of a flock of birds, i.e. a population of simple agents interacting locally with each other and with the environment. The flocking algorithm provides a model of decentralized adaptive organization useful to solve complex optimization, classification and distributed control problems. This approach avoids the sequential search of canonical clustering algorithms and permits a scalable implementation. The method is applied to design two novel clustering algorithms based on the main principles of two popular clustering algorithms: DBSCAN and SNN. This apporach can identify clusters of widely varying shapes and densities and is able to extract an approximate view of the clusters whenever it is required. Both the algorithms have been evaluated on synthetic and real world data sets and the impact of the flocking strategy on performance has been evaluated. [Copyright &y& Elsevier]

Abstract: In various generalized rough set models, definable concepts are used to approximate other concepts. Based on a unified abstract rough set theory, this paper investigates the mathematical structure of the set of definable concepts in several generalized rough set models such as relation based models, covering based models, and fuzzy based models. It is shown that there exist two kinds of interesting structures for the set of definable concepts, which are often used in rough set models: the complementary structure and the equational structure. In addition, relations between different rough set models are discussed. [Copyright &y& Elsevier]

This paper is focused on determining the parameters of radial basis function neural networks (number of neurons, and their respective centers and radii) automatically. While this task is often done by hand, or based in hillclimbing methods which are highly dependent on initial values, in this work, evolutionary algorithms are used to automatically build a radial basis function neural networks (RBF NN) that solves a specified problem, in this case related to currency exchange rates forecasting. The evolutionary algorithm EvRBF has been implemented using the evolutionary computation framework evolving object, which allows direct evolution of problem solutions. Thus no internal representation is needed, and specific solution domain knowledge can be used to construct specific evolutionary operators, as well as cost or fitness functions. Results obtained are compared with existent bibliography, showing an improvement over the published methods. [ABSTRACT FROM AUTHOR]