Search

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]

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: 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]