Skip to main content
SpringerLink
Log in

Granular Computing: Practices, Theories, and Future Directions

  • Reference work entry
Encyclopedia of Complexity and Systems Science

Definition of the Subject

Granular Computing (GrC) is still in its inception stage, we use motivation as its statements of importance.

How Important is Granular Computing?

Granulation seems to be a natural methodology deeply rooted in human thinking. Many daily “things” are routinely granulated into sub“things”; for example, the human body has been granulated into the head, neck, and so forth. The notion is intrinsically fuzzy, vague, and imprecise. Formalization is difficult, mathematicians idealized/simplified it into the notion of partitions (= equivalence relations), and have developed it into a fundamental part of mathematics, for example, congruence in Euclidean geometry, quotient structures (groups, rings, etc) in algebra, the concept of “a. e.” (almost every where) in analysis. Nevertheless, the notion of partitions (see glossary), which absolutely does not permit any overlapping among its granules, seems to be too restrictive for real world problems. Even in natural science,...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Abbreviations

Glossary:

All terms are explained in classical sets, but implicitly, we are assuming all terms and assertions do include fuzzified versions (if fuzzifiable).

Granulation:

Granulation is an operation or a process of forming granules, with a granule being a collection of objects (points) that are drawn together by some constraints, such as indistinguishability, similarity or functionality.

Granular structure:

Granular structure is the collection of granules, in which the internal structure of each granule is visible as a sub‐structure. Informally speaking, granular structure is a collection of white box granules.

Quotient structure:

A quotient structure is the mathematical structure of the collection of granules, in which each granule is regarded as an element (point) of a set, but the interactions among granules are preserved. Informally speaking, a quotient structure is a collection of black box granules.

The collection of \( \{\ldots,-2, 0, 2,\ldots\} \) and \( \{\ldots,-3, 1, 3,\ldots\} \) is a granular structure. Let E be the first subset (even integers) and O be the second subset (the odd integers). We write the two subsets by [E] and [O], when we think of them as points. Then the collection of [E] and [O] (as points) is the quotient structure.

Neighborhood system (local granular model abb. local GrC model):

A domain of interests ( a classical set) U is called the universe. To each point p in the universe, a family of subsets is assigned. Such a family (could be empty) and each such subset is called a neighborhood system \( { \text{NS}(p) } \) at p and a neighborhood at p, respectively. The collection β of such a family at every point of the universe is called a neighborhood system \( { \text{NS}(U) } \) of the universe. Neighborhood and neighborhood system are pre-GrC language; in granular computing, they are called granule and the granular structure, respectively. The pair (\( { U, \beta } \)) is called a local granular model, since each granule is associated with some points.

Topological neighborhood system:

A neighborhood system is called a topological neighborhood system, if it satisfies the axioms of topology.

Binary neighborhood system (binary granular model; binary GrC model):

A binary neighborhood system is a neighborhood system defined by a binary relation R. A (right) neighborhood is defined as follows: \( B(p)=\{x \mid(p,x)\in R\} \). The collection B of B(p) at each p is the (right) binary neighborhood system. Similarly, we can define a left version: A left neighborhood system L is defined by the \( L(p)=\{x \mid(x, p)\in R\} \) at every point p. Note that the right and left neighborhood systems determine each other. The pair (\( { U, \beta } \)) is called a binary granular model, where β is right (left) neighborhood system or R.

pre‐Topology:

Pre‐topology is a general term referring to the neighborhood system, which includes the topological neighborhood system and binary neighborhood system as special cases. Technically, it is equivalent to the neighborhood system.

Bag:

A bag is similar to a set, but allows an element to appear more than once. For example \( { \{1, 2, 1, 2, 1\} } \) is a bag, but not a set. If a bag contains n elements, we may say it is an n‑bag. For example, the previous bag is a 5‑bag.

Relational structure (relational granular model; rela-tional GrC model):

A family of classical sets is called a universe and denoted by \( { \mathcal{U} } \). A Cartesian product of an n‑bag of \( { \mathcal{U} } \) is called an n‑product set. A n‑ary relation is a subset of an n‑product set. A collection β of n‑ary relations (n could vary) is called a relational structure. The pair (\( { U, \beta } \)) is called a Relational GrC Model. Note that this relational structure, except the size, is similar to the relational structure (without functions) of the First Order Logic; the Relational GrC Model permits n to be any cardinal number.

Partial covering (global granular model; global GrC model):

Let U be a classical set, called the universe. Let \( { \beta =\{F^1, F^2, \ldots \} } \) be a family of subsets. Such a β is a partial covering, and (full)covering, if the union of β is the whole universe. The pair (\( { U, \beta } \)) is called a Global Granular Model (Global GrC Model).

Equivalence Relation:

A binary relation \( { \mathcal{R} } \) is called an equivalence relation, if it has the following properties: Let u, v, and w be elements of U.

reflexive::

\( { u \mathcal{R} u } \)

symmetric::

\( { u \mathcal{R} v } \) implies \( { v \mathcal{R} u } \)

transitive::

\( { u \mathcal{R} v } \) and \( { u \mathcal{R} w } \) implies \( { u \mathcal{R} w } \)

reflexive::

\( { u \mathcal{R} u } \)

symmetric::

\( { u \mathcal{R} v } \) implies \( { v \mathcal{R} u } \)

transitive::

\( { u \mathcal{R} v } \) and \( { u \mathcal{R} w } \) implies \( { u \mathcal{R} w } \)

Partition:

A partition \( { \mathcal{P} } \) of a classical set U is a collection of subsets that are mutually disjoint and their union is U. Each subset is called an equivalence class. This name is derived from the fact that partition is equivalent to the following equivalence relation: We define \( { u \mathcal{R} v } \), if and only if u and v belong to the same equivalence class. Such \( { \mathcal{R} } \) is the equivalence relation corresponding to the partition \( { \mathcal{P} } \). Note that a partition is a special type of a granular structure, so an equivalence class is a special granule.

Bibliography

  1. Baliga P, Lin TY (2005) Kolmogorov complexity based automata modeling forintrusion detection. In: 2005 IEEE international conference on granular computing, Beijing, 25–27 July 2005. pp 387–392

    Google Scholar 

  2. Chiang IJ, Lin TY, Liu Y (2005) Table representations of granulationsrevisited. In: Proc 10th international conference, RSFDGrC 2005, Regina, Canada, 31 Aug–3 Sept 2005, part I. Lecture notes in computerscience, vol 3641. Springer, Berlin, pp 728–737

    Google Scholar 

  3. Dubois D, Prade H (1992) Putting rough sets and fuzzy sets together. In:Slowinski R (ed) Intelligent decision support: Handbook of applications and advances of the rough sets theory. Kluwer, Dordrecht, pp 203–232

    Google Scholar 

  4. Ginsburg S, Hull R (1981) Ordered attribute domains in the relational model. In:XP2 workshop on relational database theory, June 22–24, Pennsylvania State University, USA

    Google Scholar 

  5. Ginsburg S, Hull R (1983) Order dependency in the relational model. Theor ComputSci 26:149–195

    MathSciNet  MATH  Google Scholar 

  6. Hsiao D, Harary F (1970) A formal system for information retrieval fromfiles. Commun ACM 13(2):67–73 (Corrigenda 13(4))

    MATH  Google Scholar 

  7. Lin TY (1988) Neighborhood systems and relational database. In: Proc of the 16thACM annual conference on computer science, Atlanta, 23–25 Feb 1988. p 725

    Google Scholar 

  8. Lin TY (1989) Chinese wall security policy – An aggressive model. In:Proc of the 5th aerospace computer security application conference, Tuscon, 4–8 December, pp 286–293

    Google Scholar 

  9. Lin TY (1989) Neighborhood systems and approximation in database and knowledgebase systems. In: Proc of the 4th international symposium on methodologies of intelligent systems (poster session), Charlotte, 12 Oct 1989. pp75–86. (Available to the public from the National Technical Information Services, U. S. Departmetnof Commerce, 5285 Port Royal Rd., Springfield, VA22161. NTIS price codes rited copy: A11 Micorfiche A01. Available to DOE and DOE contractors from the office od scientific and technical informationP. O. Box 62, Oak Ridge, TN 37831; prices available from (615) 576-8401)

    Google Scholar 

  10. Lin TY (1990) Relational data models and category theory (abstract). In:CSC'90, Proc of the ACM 18th annual computer science conference on cooperation, Sheraton Washington Hotel, Washington DC, 20–22 Feb 1990. p424

    Google Scholar 

  11. Lin TY (1992) Topological and fuzzy rough sets. In: Slowinski R (ed) Decisionsupport by experience – Application of the rough sets theory. Kluwer, Dordrecht, pp287–304

    Google Scholar 

  12. Lin TY (1996) A set theory for soft computing. In: Proceedings of 1996IEEE international conference on fuzzy systems, New Orleans, 8–11 Sept 1996, pp 1140–1146

    Google Scholar 

  13. Lin TY (1997) Neighborhood systems – A qualitative theory forfuzzy and rough sets. In: Wang P (ed) Advances in machine intelligence and soft computing, vol IV. Duke University, Durham, North Carolina, USA, pp132–155

    Google Scholar 

  14. Lin TY (1998) Granular computing on binary relations I: Data mining andneighborhood systems. In: Skoworn A Polkowski L (eds) Rough sets in knowledge discovery. Physica, Heidelberg, pp107–121

    Google Scholar 

  15. Lin TY (1998) Granular computing on binary relations II: Rough setrepresentations and belief functions. In: Skoworn A, Polkowski L (eds) Rough sets in knowledge discovery. Physica, Heidelberg, pp121–140

    Google Scholar 

  16. Lin TY (1999) Granular computing: Fuzzy logic and rough sets. In: Zadeh L,Kacprzyk J (eds) Computing with words in information/intelligent systems. Physica, Heidelberg, pp 183–200

    Google Scholar 

  17. Lin TY (2003) Chinese wall security policy models: Information flows andconfining trojan horses. In: De Capitani di Vimercati S, Ray I, Ray I (eds) Data and applications security XVII: Status and prospects, IFIP TC-11 WG 11.317th annual working conference on data and application security, Estes Park, 4–6 Aug 2003. Kluwer, Boston, pp275–287

    Google Scholar 

  18. Lin TY (2005) Divide and conquer in granular computing: Topologicalpartition. In: Proc of the 2005 North American fuzzy information processing society annual conference: Computing for real world applications, Ann Arbor,22–25 June 2005

    Google Scholar 

  19. Lin TY (2006) A roadmap from rough set theory to granular computing. In:Proc of the 1st international conference rough sets and knowledge technology, RSKT 2006, Chongquing, 24–26 July 2006. Lecture notes in computerscience, vol 4062. Springer, Berlin, pp 33–41

    Google Scholar 

  20. Lin TY (2006) Granular computing on partitions, coverings, and neighborhoodsystems. J Nanchang Inst Technol 25(2):1–7 (Special issue as the Proc of the international forum on theory of GrC from rough setprospective.)

    Google Scholar 

  21. Lin TY, Chiang IJ (2005) A simplicial complex, a hypergraph,structure in the latent semantic space of document clustering. Int J Approx Reason 40(1–2):55–80

    MathSciNet  MATH  Google Scholar 

  22. Lin TY, Liau CJ (2005) Granular Computing and Rough Sets. In: Maimon O, RokachL (eds) The data mining and knowledge discovery handbook. Springer, New York, pp 535–561

    Google Scholar 

  23. Lin TY, Huang KJ, Liu Q, Chen W (1990) Rough sets, neighborhood systems andapproximation. In: Proc of the 5th international symposium on methodologies of intelligent systems, selected papers, Knoxville, 25–27 Oct 1990,pp 130–141. Library of Congress Catalog Card Number:90-84690

    Google Scholar 

  24. Lin TY, Sutojo A, Hsu JD (2006) Concept analysis and web clustering usingcombinatorial topology. In: Workshops Proc of the 6th IEEE international conference on data mining (ICDM 2006), Hong Kong, 18–22 Dec 2006. pp412–416

    Google Scholar 

  25. Liu Y, Lin TY, Xu C, Zhang Q, Huang L, He P (2008) Modeling complexarchitectures based on granular computing on ontology. Submitted to IEEE Trans Fuzzy Syst

    Google Scholar 

  26. Maclane S (1995) Homology. Classics in mathematics, reprint of the 1975edn. Springer, Berlin, x+422 pp

    Google Scholar 

  27. Mumford D (1988) Introduction ot algebriac geometry. In: The red book ofvarieties and schemes, mimeographed notes from the Harvard mathematics department 1967. Lecture Notes in Mathematics, vol 1348. Springer,Berlin

    Google Scholar 

  28. Munkres J (2000) Topology, 2nd edn. Prentice‐Hall

    Google Scholar 

  29. Park JW, Sandberg IW (1991) Universal approximation usingradial‐basis‐function networks. Neural Comput 3:246–257

    Google Scholar 

  30. Pawlak Z (1991) Rough sets. Theoretical Aspects Of Reasoning AboutData. Kluwer, Dordrecht

    MATH  Google Scholar 

  31. Polya G (1957) How to solve it, 2nd edn. Princeton University Press,Princeton

    Google Scholar 

  32. Robinson A (1966) Non‐standard analysis. North‐Holland,Amsterdam

    MATH  Google Scholar 

  33. Sierpenski W (trans by Krieger C) (1952) General Topology. Mathematicalexposition, no 7. University of Toronto Press, Toronto

    Google Scholar 

  34. Spanier EH (1966) Algebraic topology. Springer, NewYork

    MATH  Google Scholar 

  35. Stanat D, McAllister D (1977) Discrete mathematics in computerscience. Prentice‐Hall, Englewood Cliffs

    Google Scholar 

  36. Wong E, Chiang TC (1971) Canonical structure in attribute based fileorganization. Commun ACM 14(9):593–597

    MATH  Google Scholar 

  37. Zadeh LA (1979) Fuzzy sets and information granularity. In: Gupta M, Ragade R,Yager R (eds) Advances in fuzzy set theory and applications. North‐Holland, Amsterdam, pp 3–18

    Google Scholar 

  38. Zadeh LA (1996) The key roles of information granulation and fuzzy logic inhuman reasoning. In: 1996 IEEE international conference on fuzzy systems, New Orleans, 8–11 Sept, p 1

    Google Scholar 

  39. Zadeh LA (1997) Toward a theory of fuzzy information granulation and itscentrality in human reasoning and fuzzy logic. Fuzzy Sets Syst 90:111–127

    MathSciNet  MATH  Google Scholar 

  40. Zadeh LA (1998) Some reflections on soft computing, granular computing andtheir roles in the conception, design and utilization of information/intelligent systems. Soft Comput 2:23–25

    Google Scholar 

  41. Zimmerman H (1991) Fuzzy set theory – and its applications. Kluwer, Dordrecht

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, San Jose State University, San Jose, USA

    Tsau Young Lin

Authors
  1. Tsau Young Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. RAMTECH LIMITED, 122 Escalle Lane, Larkspur, CA, 94939, USA

    Robert A. Meyers Ph. D. (Editor-in-Chief) (Editor-in-Chief)

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag

About this entry

Cite this entry

Lin, T. (2009). Granular Computing: Practices, Theories, and Future Directions. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY. https://doi.org/10.1007/978-0-387-30440-3_256

Download citation

Publish with us

Policies and ethics

Search

Navigation