Preface1. Granular Computing
Granular computing (GrC) has emerged as one of the fastest growing information processing paradigms in computational intelligence and human-centric systems.
In recent years, the research on granular computing has attracted many researchers and practitioners. The concept of granular computing was initially called information granularity or information granulation related to the research of fuzzy sets (Zadeh 1979). The term granular computing first appeared within literature in 1997 in Zadeh’s paper where it was defined as “a subset of computing with words” (Zadeh, 1997). It is a generally accepted that 1997 is considered as the year of the birth of granular computing (Yao, 2007). We have experienced the emergence and growth of granular computing research in the past decade (Bargiela, A. & Pedrycz, W., 2006; Yao, 2005; Yao & Yao, 2002; Yao YY, 2005; Zadeh, 2006). Although the term granular computing is new (just over ten years mark), the basic notions and principles of granular computing occurred under various forms in many disciplines and fields (Yao, 2004, Zadeh, 1997). Similar views are shared by research in belief functions, artificial intelligence, cluster analysis, chunking, data compression, databases, decision trees, divide and conquer, fuzzy logic, interval computing, machine learning, structured programming, quantization, quotient space theory, and rough set theory.
Granular computing is often loosely defined as an umbrella term to cover any theories, methodologies, techniques, and tools that make use of granules in complex problem solving (Yao YY, 2005). Zadeh considers granular computing as basis for computing with words, i.e., computation with information described in natural language (Zadeh, 1997; Zadeh, 2006). Yao views granular computing as a complementary and dependant triangle: structured thinking in philosophical perspective, structured problem solving in methodological perspective and structured information processing in computational perspective (Yao, 2005; Yao, 2007).
An important fuzzy aspect in granular computing is to view granular computing as human-centric intelligent systems. Human-centered information processing was initiated with the introduction of fuzzy sets. The insights have led to the development of the granular computing paradigm (Bargiela and Pedrycz 2008, Zadeh 1997). Shifting from machine-centered approaches to human-centered approaches is considered one of the trends in GrC research.
The basic ingredients of granular computing are granules such as subsets, classes, objects, clusters, and elements of a universe. These granules are composed of finer granules that are drawn together by distinguishability, similarity and functionality (Zadeh, 1997). Based on complexity, abstraction level and size, granules can be measured in different levels. The problem domain, i.e., the universe, exists at the highest and coarsest granule. Granules at the lowest level are composed of elements or basic particles of the particular model that is used (Yao 2007).
Granulation is one of the key issues in granular computing for problem solving. The original meaning of granulation from dictionaries, such as the Merriam-Webster’s Dictionary, is the act or process of forming something into granules. It is a process of making a larger object into smaller ones. Zadeh (1996) adopted this idea to decompose a universe to granules and pointed out “granulation involves a decomposition of whole into parts. Conversely, organization involves an integration of parts into whole.” Based on this definition, there will be two operations in granular computing, i.e., granulation and organization. It is suggested that a broad view of granulation in granular computing is easy to understand and manageable for granular computing research and applications (Yao 2005). Granulation involves the process of two directions in problem solving: construction and decomposition. The construction involves the process of forming a larger and higher level granule with smaller and lower level sub-granules. The decomposition involves the process of dividing a larger granule into smaller and lower level granules. The former is a bottom-up process and the latter a top-down process. The reason for a more general and broad view of granulation is that construction and decomposition are tightly related. When one chooses a particular granulation in an application, the benefits and efficiency of one direction is correlated to its opposite direction. If we consider a decomposition operation without the consideration of construction we may end up with a very efficient decomposition operation and a very inefficient construction..
In order to conduct granulation, it is crucial to understand relationships amongst granules. We may classify granular relationships into two groups: interrelationship and intrarelationship (Yao 2005). Decomposition concerns breaking down a larger granule into smaller granules from which a larger granule can still be formed with construction. Construction concerns grouping smaller granules that share similarity, indistinguishability, and functionality to a larger granule. The relationship involved in the former granulation is considered as interrelationship, the latter intrarelationship. In other words, interrelationship is the basis of grouping small objects together while intrarelationship is the foundation of dividing a granule into smaller ones. Refinement and coarsening are additional types of relationships (Yao & Yao, 2002). A granule o1 is defined as a refinement of another granule o2, or equivalently, o2 is a coarsening of o1, if every sub-granule or object of o1 is contained in some sub-granules of o2. Partitions and coverings are two simple and commonly used granulations of a universe. A partition of a universe is a collection of its non-empty and pairwise disjoint subsets whose union is the universe. It forms a covering if it is not disjoint. The subsets are called covering granules in a covering, and partition granules in a partition.
2. Recent Developments in Granular Computing
Representative and influential research in granular computing were identified recently (Yao, 2006; Yao, 2007). We will briefly summarize the findings here.
2.1 Philosophic and fundamental views of granular computing
The triarchic theory is a representative research on the foundations of granular computing (Yao YY, 2008). Defining granular computing is one of the important research tasks for this community. Instead of simply defining what granular computing research is, Y.Y. Yao views the scope of granular computing from three perspectives, namely, the philosophical perspective, methodological perspective and computational perspective. It is argued that with each perspective focusing on different aspects of granular structures, the three perspectives working together will provide a more general and complementary view of granular computing. The philosophical perspective concerns structured thinking. The methodological perspective concerns structured problem solving. The computational perspective concerns structured information processing. Granular computing also focuses on the application of its theory to knowledge-intensive systems. The representation and processes of a system are two things to consider. Representation of a system describes the granules and granular structures within the application domain.
2.2 Human-centered and fuzzy information processing
Human-centered information processing was initiated with the introduction of fuzzy sets. The insights have led to the development of the granular computing paradigm (Bargiela & Pedrycz, 2008; Zadeh, 1997). Shifting from machine-centered approaches to human-centered approaches is considered one of trends in granular computing research (Yao YY, 2008). Bargiela and Pedrycz’s (2008) research adopt granular computing into a structured combination of algorithmic and non-algorithmic information processing that mimics human, intelligent synthesis of knowledge from information. By integrating various different agents in which each pursues its own agenda, exploits its environment, develops its own problem solving strategy and establishes required communication strategies, one may form a more effective human-centered information system (Pedrycz, 2008). In fact, each agent may encounter a diversity of problem-solving approaches and realize their processing at the level of information granules that is the most suitable from their local points of view. To this level, the hybrid model raises a fundamental issue of forming effective interaction linkages between the agents so that they fully broadcast their findings and benefit from interacting with others.
2.3 Rough-Granular Computing
Rough set theory plays an important role in granular computing. A recent work by Skowron studies the formation of granules with different criteria from a rough computing point of view (Skowron & Stepaniuk, 2007). When searching for optimal solutions satisfying some constraints, one of the challenges is that these constraints are often vague and imprecise. In addition, specifications of concepts and dependencies between these involving in the constraints are often incomplete. Granules are constructed in computations aiming at solving such optimization tasks. General optimization criterion based on the minimal length principle was used. In searching for (sub-)optimal solutions, it is necessary to construct many compound granules using some specific operations such as generalization, specification or fusion. It is suggested that these criteria can be based on the minimal length principle, can express acceptable risk degrees of granules, or can use some utility functions (Skowron & Stepaniuk, 2007).
2.4 Dominance-based Rough Set Approach
The dominance-based rough set approach is another representation of rough set-based granular computing methodology. It extends the classical rough set approach by utilizing background knowledge about ordinal evaluations of objects and about monotonic relationships between these evaluations (Slowinski, Greco & Matarazzo, 2007) The indiscernibility or tolerance relation among objects, which is used in the classical rough set approach, has been replaced by the dominance relation: the only relation uncontested in multiattribute pair-wise comparisons when attribute scales are ordered. In addition, the fuzzy-rough approximations taking into account monotonic relationships between memberships to different sets may be applied to case-based reasoning.
2.5 Other Important Research Directions
Topological views of granular computing are also attracting some researchers. For instance, Zhu (2007) studies covering-based rough sets from the topological view.
Yager (2007) adopted granular computing on information fusion applications. In particular, fuzzy sets are used to provide a granular representation of uncertain information about a variable of interest.
Zhang & Zhang (2004) proposed a theoretical framework of a fuzzy reasoning model under quotient space structure. The quotient space structure is introduced into fuzzy sets to construct fuzzy set representations of different grain-size spaces and their relationships.
Liu et al. studied granular computing from a rough logic aspect (Liu, Sun & Wang, 2007). The granulation is based on the meaning of a rough logical formula in a given information system. It is suggested that the practicability of the granulations will offer a new idea for studying the meaning of classical logic and the meaning of other nonstandard logic.
3. The Most Cited Granular Computing Papers and Call for Chapters
In (Yao, 2007) and (Yao, 2008), the most influential research papers on the topic of granular computing were identified. We defined a granular computing paper as a paper that contains granular computing related terms, for instance, “granular computing”, “information granularity”, “information granulation” or “granular computation”. We used the Web of Science of ISI to locate granular computing papers that are indexed by ISI. We searched by Topic which is defined as the words or phrases within article titles, keywords, or abstracts in Web of Science. Top highly cited granular computing papers retrieved from Web of Science on Oct 1, 2007 are listed below.
1. Zadeh LA, Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets And Systems 90 (2): 111-127, 1997
2. Greco S, Matarazzo B, Slowinski R, Rough sets theory for multicriteria decision analysis, European Journal of Operational Research 129 (1): 1-47, 2001
3. Skowron A, Stepaniuk J, Information granules: Towards foundations of granular computing, International Journal of Intelligent Systems 16 (1): 57-85, 2001
4. Pedrycz W, Vasilakos AV, Linguistic models and linguistic modeling, IEEE Transactions on Systems Man, and Cybernetics Part B-Cybernetics 29 (6): 745-757, 1999
5. Pedrycz W, Fuzzy equalization in the construction of fuzzy sets, Fuzzy Sets and Systems 119 (2): 329-335, 2001
6. Yao YY, Information granulation and rough set approximation, International Journal of Intelligent Systems 16 (1): 87-104, 2001
7. Hirota K, Pedrycz W, Fuzzy computing for data mining, Proceedings of the IEEE 87 (9): 1575-1600, 1999
8. Peters JF, Skowron A, Synak P, et al., Rough sets and information granulation, Lecture Notes in Artificial Intelligence 2715: 370-377, 2003
9. Al-Khatib W, Day YF, Ghafoor A, et al., Semantic modeling and knowledge representation in multimedia databases, IEEE Transactions on Knowledge and Data Engineering 11 (1): 64-80, 1999
10. Hirota K, Pedrycz W, Fuzzy relational compression, IEEE Transactions on Systems, Man and Cybernetics Part B-Cybernetics 29 (3): 407-415, 1999
11. Greco S, Matarazzo B, Slowinski R, Extension of the rough set approach to multicriteria decision support, INFOR 38 (3): 161-195, 2000 v
12. Slowinski R, Greco S, Matarazzo B, Rough set analysis of preference-ordered data, Lecture Notes In Artificial Intelligence 2475: 44-59, 2002
14. Hata Y, Kobashi S, Hirano S, et al., Automated segmentation of human brain MR images aided by fuzzy information granulation and fuzzy inference, IEEE Transactions on Systems, Man and Cybernetics Part C-Applications And Reviews 30 (3): 381-395, 2000
15. Pal SK, Mitra P, Case generation using rough sets with fuzzy representation, IEEE Transactions on Knowledge and Data Engineering 16 (3): 292-300, 2004
16. Yao YY, Probabilistic approaches to rough sets, Expert Systems 20 (5): 287-297, 2003
17. Pal SK, Mitra P, Multispectral image segmentation using the rough-set-initialized EM algorithm, IEEE Transactions on Geoscience and Remote Sensing 40 (11): 2495-2501, 2002
18. Pedrycz W, Gudwin RR, Gomide FAC, Nonlinear context adaptation in the calibration of fuzzy sets, Fuzzy Sets and Systems 88 (1): 91-97, 1997
As stated in Wohlin’s article (Wohlin, 2008),
“Citations are a common way of judging the most influential work in different fields. The most cited articles often provide new insights, open a new avenue of research, or provide a significant summary of the state-of-the-art in an area. Citations are a way to show how researchers build their work on existing research to evolve research further. Basically, they are the backbone of research and hence articles and authors being cited frequently deserve acknowledgment for their contribution.”
One of the goals of this book is to seek for research papers from authors of the most influential papers in order to see recent development of granular computing research. We invited these most influential authors to contribute a chapter together with a public call for papers. Eight chapters in the book are authored by the most influential authors in granular computing. We underline the authors who contributed to this book.
4. Chapter Summary
In the chapter “Human-Inspired Granular Computing” authored by Yiyu Yao, a view of granular computing as a paradigm of human-inspired problem solving and information processing, covering human-oriented studies and machine-oriented studies is explored. The triarchic theory, namely, a philosophy of structured thinking, a methodology of structured problem solving, and a computation paradigm of structured information processing is detailed. The stress on multilevel, hierarchical structures makes granular computing a human-inspired and structured approach to problem solving.
The chapter entitled “Discovery of Process Models from Data and Domain Knowledge: A Rough-Granular Approach” by Hung Son Nguyen, Andrzej Jankowski, James F. Peters, Andrzej Skowron, Jarosław Stepaniuk, and Marcin Szczuka outlines some issues of process mining from data and domain knowledge as well as approximate reasoning about changes along trajectories of approximated processes. A rough-granular approach is proposed for modeling the discovery process. The need for developing rough granular computing based on interactions among granules as well as learning strategies for approximation of functions characterizing changes, and approximation of trajectories of complex dynamical systems are also emphasized in this chapter.
The third chapter entitled “Supervised and Unsupervised Information Granulation: A Study in Hyperbox Design” authored by Andrzej Bargiela and Witold Pedrycz explores the technology of hyperboxes and fuzzy sets as a fundamental conceptual vehicle of information granulation. In particular, a new algorithm for pattern classification based on novel representation of class sets as a difference of two types of fuzzy sets is presented, i.e., the union of hyperboxes belonging to the given class and the union of hyperboxes belonging to different classes. It has been shown that, compared to the standard hyperbox paving approaches, the proposed algorithm results in a more efficient generation of complex topologies that are necessary to describe the pattern classes.
The next chapter “On Characterization of Relation Based Rough Set Algebras” authored by Wei-Zhi Wu and Wen-Xiu Zhang focuses mainly on rough set algebras characterized by a dual pair of lower and upper approximation operators in both of crisp and fuzzy environments. It reviews the definitions of generalized crisp rough sets, rough fuzzy sets and fuzzy rough sets, and then presents the essential properties of the corresponding lower and upper approximation operators. The approximation operators are characterized by axioms, and as an example, the connection between fuzzy rough set algebras and fuzzy topological spaces are established.
The chapter entitled “A Top-Level Categorization Of Types Of Granularity“ authored by C. Maria Keet proposes a taxonomy of types of granularity and discusses for each leaf type how the entities or instances relate within its granular level and between levels. It gives guidelines to a modeler to better distinguish between the types of granularity in the design phase and the software developer to improve on implementations of granularity.
The chapter entitled “From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval, p-Box, and Fuzzy Uncertainty” by Martine Ceberio, Vladik Kreinovich, Andrzej Pownuk, and Barnabás Bede presents a study of granular computing from an interval computing perspective. It is shown that extended interval computation enables us to find estimates in feasible time.
The chapter entitled “Granular Computing Based Data Mining in the Views of Rough Set and Fuzzy Set” authored by Guoyin Wang, Jun Hu, Qinghua Zhang, Xianquan Liu, and Jiaqing Zhou proposes a new understanding for data mining, namely, domain-oriented data-driven data mining (3DM), and analyses its relationship with granular computing. It also discusses the granular computing based data mining in the views of rough set and fuzzy set, and introduces some applications of granular computing in data mining.
The chapter entitled “Near Sets in Assessing Conflict Dynamics within a
Perceptual System Framework” by Sheela Ramanna and James F. Peters introduces a new framework to represent socio-technical conflicts during negotiation. It is argued that conflict situations result from different sets of view points (perceptions) about issues under negotiation, therefore, reasoning about conflict dynamics is made possible with nearness relations and tolerance perceptual near sets used in defining measures of nearness. This approach provides a new way of representing and reasoning about conflicts in the context of requirements engineering using near set theory.
The chapter entitled “Rule Extraction and Rule Evaluation Based on Granular Computing” authored by Jiye Liang, Yuhua Qian, and Deyu Li presents a dynamic approximation method of target concepts based on a granulation order, which consists of the positive approximation and converse approximation. Two algorithms for rule extracting called MABPA and REBCA are designed and applied to hierarchically generate decision rules from a decision table. It also proposes measures to evaluate the certainty, consistency and support of a decision-rule set extracted from a decision table. These three measures may be helpful in determining which rule extraction technique should be chosen in a practical decision problem.
The chapter entitled “Granular Models: Design Insights and Development Practices” authored by Witold Pedrycz and Athanasios Vasilakos presents a study on design and implementation of granular models with clearly defined semantics, i.e., linguistic models. It shows that fuzzy sets of context plays an important role in shaping up modeling activities and help handle dimensionality issues decomposing the original problem into a series of sub-problems guided by specific contexts.
It presents a context-based clustering approach that forms a viable vehicle to build information granules when considering their further usage in some input-output mapping. By bringing the concept of conditional clustering along with the granular neuron as some aggregation mechanism, it shows that granular models are easily assembled into a web of connections between information granules and these architectural considerations.
The chapter entitled “Semantic Analysis of Rough Logic” by Qing Liu presents a study on the semantics of rough logic. It also discusses related operations and related properties of semantics based on rough logic as well as related reasoning of the semantics.
The chapter entitled “Rough Entropy Clustering Algorithm in Image Segmentation” authored by Dariusz Małyszko and Jarosław Stepaniuk proposes and investigates a granular rough entropy method in the area of image clustering. The proposed rough entropy clustering algorithm results in a robust new approach into rough entropy computation.
The chapter entitled “Modeling Classification by Granular Computing” by Yan Zhao discusses the basic components of a granular structure, the modeling of classification in terms of these components as well as the top-down, bottom-up strategies for searching classification solutions within different granule networks.
The chapter entitled “Discovering Perceptually Near Information Granules” authored by James F. Peters presents a research to discover perceptual information granules that are in some sense near each other with near set theory. It argues that the near set theory can provide a basis for observation, comparison and classification of perceptual granules. It further suggests that every family of perceptual granules is a dual chopped lattice.
The chapter entitled “Granular Computing in Object-oriented Software Development Process” by Jianchao Han focuses on the applications of granular computing in various aspects and phases of the object-oriented software development process, including user requirement specification and analysis, software system analysis and design, algorithm design, structured programming, software testing, and system deployment design. The importance and usefulness of granular computing as a human-centered problem solving strategy in object-oriented software development process are highlighted.
The chapter entitled “Granular Computing in Formal Concept Analysis” authored by Yuan Ma, Zhangang Liu, and Xuedong Zhang tries to systematically connect granular computing with formal concepts. Granular spaces generated by ideal-filter, congruence relations and tolerance relations and their properties are studied.
The chapter entitled “Granular Synthesis of Rule-Based Models and Function Approximation using Rough Sets”, authored by Carlos Pinheiro, Fernando Gomide, Otávio Carpinteiro, and Isaías Lima shows how concepts of rough sets can be used to model static and dynamic nonlinear systems. The granular modeling methodology introduced here gives rule-based models associated with a functional representation that can uniformly approximate continuous functions with a certain degree of accuracy. Experiments and examples testify that granular models with function approximation and estimation capabilities can model continuous linear and nonlinear systems.
The chapter entitled “A Genetic Fuzzy Semantic Web Search Agent Using Granular Semantic Trees for Ambiguous Queries”, authored by Yan Chen and Yan-Qing Zhang introduces a model named Granular Semantic Tree (GST) for Web search. The model more conveniently represents associations among concepts than the traditional Word Sense Disambiguation methods. Fuzzy logic is used to determine the most appropriate concepts related to queries based on contexts and users’ preferences.
Last but not least the chapter entitled “Dominance-based Rough Set Approach to Granular Computing “authored by Salvatore Greco, Benedetto Matarazzo, and Roman Słowiński provides arguments for the claim that the Dominance-based Rough Set Approach (DRSA) is a proper way of handling monotonically ordered data in granular computing. DRSA in the context of ordinal classification, its fuzzy extension, and a rough probabilistic model of DRSA have been presented.