Granular computing
Encyclopedia
Granular computing is an emerging computing paradigm of information processing
. It concerns the processing of complex information entities called information granules, which arise in the process of data abstraction and derivation of knowledge from information. Generally speaking, information granules are collections of entities that usually originate at the numeric level and are arranged together due to their similarity, functional or physical adjacency, indistinguishability, coherency, or the like.
At present, granular computing is more a theoretical perspective than a coherent set of methods or principles. As a theoretical perspective, it encourages an approach to data that recognizes and exploits the knowledge present in data at various levels of resolution or scales. In this sense, it encompasses all methods which provide flexibility and adaptability in the resolution at which knowledge or information is extracted and represented.
As mentioned above, granular computing is not an algorithm or process; there is not a particular method that is called "granular computing". It is rather an approach to looking at data that recognizes that different and interesting regularities in the data can appear at different levels of granularity, much as different features become salient in satellite images of greater or lesser resolution. On a low resolution satellite image, for example, one might notice interesting cloud patterns representing cyclones or other large-scale weather phenomena, while in a higher resolution image one misses these large-scale atmospheric phenomena but instead notices smaller-scale phenomena, such as the interesting pattern that is the streets of Manhattan
. The same is generally true of all data: At different resolutions or granularities, different features and relationships emerge. The aim of granular computing is ultimately simply to try to take advantage of this fact in designing more effective machine learning and reasoning systems.
There are several types of granularity that are often encountered in data mining
and machine learning
, and we review them below:
of variables. It is very common that in data mining or machine learning applications that the resolution of variables needs to be decreased in order to extract meaningful regularities. An example of this would be a variable such as "outside temperature", (
), which in a given application might be recorded to several decimal places of accuracy (depending on the sensing apparatus). However, for purposes of extracting relationships between "outside temperature" and, say, "number of health club applications", (
), it will generally be advantageous to quantize "outside temperature" into a smaller number of intervals.
For example, a simple learner or pattern recognition system may seek to extract regularities satisfying a conditional probability
threshold such as
. In the special case where 
, this recognition system is essentially detecting logical implication of the form 
or, in words, "if 
, then 
". The system's ability to recognize such implications (or, in general, conditional probabilities exceeding threshold) is partially contingent on the resolution with which the system analyzes the variables.
As an example of this last point, consider the feature space shown to the right. The variables may each be regarded at two different resolutions. Variable
may be regarded at a high (quaternary) resolution wherein it takes on the four values 
or at a lower (binary) resolution wherein it takes on the two values 
. Similarly, variable 
may be regarded at a high (quaternary) resolution or at a lower (binary) resolution, where it takes on the values 
or 
, respectively. It will be noted that at the high resolution, there are no detectable implications of the form 
, since every 
is associated with more than one 
, and thus, for all 
, 
. However, at the low (binary) variable resolution, two bilateral implications become detectable: 
and 
, since every 
occurs iff 
and 
occurs iff 
. Thus, a pattern recognition system scanning for implications of this kind would find them at the binary variable resolution, but would fail to find them at the higher quaternary variable resolution.
analysis of some kind) so that some guidance can be given as to how the discretization process should proceed. Moreover, one cannot generally achieve good results by naively analyzing and discretizing each variable independently, since this may obliterate the very interactions that we had hoped to discover.
A sample of papers that address the problem of variable discretization in general, and multiple-variable discretization in particular, are as follows: , , , , , , , , , , , , , , , ,
, , , , .
, factor analysis
, and structural equation modeling
, and their relatives, fall under the genus of "variable transformation." Also in this category are more modern areas of study such as dimensionality reduction
, projection pursuit
, and independent component analysis
. The common goal of these methods in general is to find a representation of the data in terms of new variables, which are a linear or nonlinear transformation of the original variables, and in which important statistical relationships emerge. The resulting variable sets are almost always smaller than the original variable set, and hence these methods can be loosely said to impose a granulation on the feature space. These dimensionality reduction methods are all reviewed in the standard texts, such as , , and .
methodologies than from the linear systems theory informing the above methods. It was noted fairly early that one may consider "clustering" related variables in just the same way that one considers clustering related data. In data clustering, one identifies a group of similar entities (using a measure of "similarity" suitable to the domain), and then in some sense replaces those entities with a prototype of some kind. The prototype may be the simple average of the data in the identified cluster, or some other representative measure. But the key idea is that in subsequent operations, we may be able to use the single prototype for the data cluster (along with perhaps a statistical model describing how exemplars are derived from the prototype) to stand in for the much larger set of exemplars. These prototypes are generally such as to capture most of the information of interest concerning the entities.
Similarly, it is reasonable to ask whether a large set of variables might be aggregated in to a smaller set of prototype variables that capture the most salient relationships between the variables. Although variable clustering methods based on linear correlation have been proposed , more powerful methods of variable clustering are based on the mutual information
between variables. Watanabe has shown that for any set of variables one can construct a polytomic (i.e., n-ary) tree representing a series of variable agglomerations in which the ultimate "total" correlation among the complete variable set is the sum of the "partial" correlations exhibited by each agglomerating subset (see figure). Watanabe suggests that an observer might seek to thus partition a system in such a way as to minimize the interdependence between the parts "... as if they were looking for a natural division or a hidden crack."
One practical approach to building such a tree is to successively choose for agglomeration the two variables (either atomic variables or previously agglomerated variables) which have the highest pairwise mutual information . The product of each agglomeration is a new (constructed) variable that reflects the local joint distribution
of the two agglomerating variables, and thus possesses an entropy equal to their joint entropy.
(From a procedural standpoint, this agglomeration step involves replacing two columns in the attribute-value table—representing the two agglomerating variables—with a single column that has a unique value for every unique combination of values in the replaced columns . No information is lost by such an operation; however, it should be noted that if one is exploring the data for inter-variable relationships, it would generally not be desirable to merge redundant variables in this way, since in such a context it is likely to be precisely the redundancy or dependency between variables that is of interest; and once redundant variables are merged, their relationship to one another can no longer be studied.
and Business intelligence
systems) result in transforming original data tables (often called information systems) into the tables with different semantics of rows and columns, wherein the rows correspond to the groups (granules) of original tuples and the columns express aggregated information about original values within each of the groups. Such aggregations are usually based on SQL and its extensions. The resulting granules usually correspond to the groups of original tuples with the same values (or ranges) over some pre-selected original columns.
There are also other approaches wherein the groups are defined basing on, e.g., physical adjacency of rows. For example, Infobright
implements a database engine wherein data is partitioned onto rough rows, each consisting of 64K of physically consecutive (or almost consecutive) rows. Rough rows are automatically labeled with compact information about their values on data columns, often involving multi-column and multi-table relationships. It results in a higher layer of granulated information systems where objects correspond to rough rows and attributes - to various flavors of rough information. Database operations can be efficiently supported within such a new framework, with an access to the original data pieces still available.
When the full set of attributes
is considered, we see that we have the following seven equivalence classes or primitive (simple) concepts:
Thus, the two objects within the first equivalence class,
, cannot be distinguished from one another based on the available attributes, and the three objects within the second equivalence class, 
, cannot be distinguished from one another based on the available attributes. The remaining five objects are each discernible from all other objects. Now, let us imagine a projection of the attribute value system onto attribute 
alone, which would represent, for example, the view from an observer which is only capable of detecting this single attribute. Then we obtain the following much coarser equivalence class structure.
This is in a certain regard the same structure as before, but at a lower degree of resolution (larger grain size). Just as in the case of value granulation (discretization/quantization), it is possible that relationships (dependencies) may emerge at one level of granularity that are not present at another. As an example of this, we can consider the effect of concept granulation on the measure known as attribute dependency (a simpler relative of the mutual information
).
To establish this notion of dependency (see also rough sets), let
represent a particular concept granulation, where each 
is an equivalence class from the concept structure induced by attribute set 
. For example, if the attribute set 
consists of attribute 
alone, as above, then the concept structure 
will be composed of 
, 
, and 
. The dependency of attribute set 
on another attribute set 
, 
, is given by
That is, for each equivalence class
in 
, we add up the size of its "lower approximation" (see rough sets) by the attributes in 
, i.e., 
. More simply, this approximation is the number of objects which on attribute set 
can be positively identified as belonging to target set 
. Added across all equivalence classes in 
, the numerator above represents the total number of objects which—based on attribute set 
—can be positively categorized according to the classification induced by attributes 
. The dependency ratio therefore expresses the proportion (within the entire universe) of such classifiable objects, in a sense capturing the "synchronization" of the two concept structures 
and 
. The dependency 
"can be interpreted as a proportion of such objects in the information system for which it suffices to know the values of attributes in 
to determine the values of attributes in 
" (Ziarko & Shan 1995).
Having gotten definitions now out of the way, we can make the simple observation that the choice of concept granularity (i.e., choice of attributes) will influence the detected dependencies among attributes. Consider again the attribute value table from above:
Let us consider the dependency of attribute set
on attribute set
. That is, we wish to know what proportion of objects can be correctly classified into classes of 
based on knowledge of 
. The equivalence classes of 
and of 
are shown below.
The objects that can be definitively categorized according to concept structure
based on 
are those in the set 
, and since there are six of these, the dependency of 
on 
, 
. This might be considered an interesting dependency in its own right, but perhaps in a particular data mining application only stronger dependencies are desired.
We might then consider the dependency of the smaller attribute set
on the attribute set
. The move from 
to 
induces a coarsening of the class structure 
, as will be seen shortly. We wish again to know what proportion of objects can be correctly classified into the (now larger) classes of 
based on knowledge of 
. The equivalence classes of the new 
and of 
are shown below.
Clearly,
has a coarser granularity than it did earlier. The objects that can now be definitively categorized according to the concept structure 
based on 
constitute the complete universe 
, and thus the dependency of 
on 
, 
. That is, knowledge of membership according to category set 
is adequate to determine category membership in 
with complete certainty; In this case we might say that 
. Thus, by coarsening the concept structure, we were able to find a stronger (deterministic) dependency. However, we also note that the classes induced in 
from the reduction in resolution necessary to obtain this deterministic dependency are now themselves large and few in number; as a result, the dependency we found, while strong, may be less valuable to us than the weaker dependency found earlier under the higher resolution view of 
.
In general it is not possible to test all sets of attributes to see which induced concept structures yield the strongest dependencies, and this search must be therefore be guided with some intelligence. Papers which discuss this issue, and others relating to intelligent use of granulation, are those by Y.Y. Yao and Lotfi Zadeh listed in the #References below.
learning, for example, a set of data is explained as a mixture of distinct Gaussian (or other) distributions. Thus, a large amount of data is "replaced" by a small number of distributions. The choice of the number of these distributions, and their size, can again be viewed as a problem of concept granulation. In general, a better fit to the data is obtained by a larger number of distributions or parameters, but in order to extract meaningful patterns, it is necessary to constrain the number of distributions, thus deliberately coarsening the concept resolution. Finding the "right" concept resolution is a tricky problem for which many methods have been proposed (e.g., AIC
, BIC, MDL
, etc.), and these are frequently considered under the rubric of "model regularization".
In a more philosophical sense, granular computing can describe a way of thinking that relies on the human ability to perceive the real world under various levels of granularity (i.e., abstraction) in order to abstract and consider only those things that serve a specific interest and to switch among different granularities. By focusing on different levels of granularity, one can obtain different levels of knowledge, as well as a greater understanding of the inherent knowledge structure. Granular computing is thus essential in human problem solving and hence has a very significant impact on the design and implementation of intelligent systems.
Information processing
Information processing is the change of information in any manner detectable by an observer. As such, it is a process which describes everything which happens in the universe, from the falling of a rock to the printing of a text file from a digital computer system...
. It concerns the processing of complex information entities called information granules, which arise in the process of data abstraction and derivation of knowledge from information. Generally speaking, information granules are collections of entities that usually originate at the numeric level and are arranged together due to their similarity, functional or physical adjacency, indistinguishability, coherency, or the like.
At present, granular computing is more a theoretical perspective than a coherent set of methods or principles. As a theoretical perspective, it encourages an approach to data that recognizes and exploits the knowledge present in data at various levels of resolution or scales. In this sense, it encompasses all methods which provide flexibility and adaptability in the resolution at which knowledge or information is extracted and represented.
Types of granulation
Manhattan
Manhattan is the oldest and the most densely populated of the five boroughs of New York City. Located primarily on the island of Manhattan at the mouth of the Hudson River, the boundaries of the borough are identical to those of New York County, an original county of the state of New York...
. The same is generally true of all data: At different resolutions or granularities, different features and relationships emerge. The aim of granular computing is ultimately simply to try to take advantage of this fact in designing more effective machine learning and reasoning systems.
There are several types of granularity that are often encountered in data mining
Data mining
Data mining , a relatively young and interdisciplinary field of computer science is the process of discovering new patterns from large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and database systems...
and machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
, and we review them below:
Value granulation (discretization/quantization)
One type of granulation is the quantizationQuantization (signal processing)
Quantization, in mathematics and digital signal processing, is the process of mapping a large set of input values to a smaller set – such as rounding values to some unit of precision. A device or algorithmic function that performs quantization is called a quantizer. The error introduced by...
of variables. It is very common that in data mining or machine learning applications that the resolution of variables needs to be decreased in order to extract meaningful regularities. An example of this would be a variable such as "outside temperature", (
), which in a given application might be recorded to several decimal places of accuracy (depending on the sensing apparatus). However, for purposes of extracting relationships between "outside temperature" and, say, "number of health club applications", (), it will generally be advantageous to quantize "outside temperature" into a smaller number of intervals.Motivations
There are several interrelated reasons for granulating variables in this fashion:- Based on prior domain knowledge, we do not expect that minute variations in temperature (e.g., the difference between 80°F and 80.7°F) could have an influence on behaviors driving the number of health club applications. For this reason, any "regularity" which our learning algorithms might detect at this level of resolution would have to be spurious, an artifact of overfitting. By coarsening the temperature variable into intervals the difference between which we do anticipate (based on prior domain knowledge) might influence number of health club applications, we eliminate the possibility of detecting these spurious patterns. Thus, in this case, reducing resolution is a method of controlling overfittingOverfittingIn statistics, overfitting occurs when a statistical model describes random error or noise instead of the underlying relationship. Overfitting generally occurs when a model is excessively complex, such as having too many parameters relative to the number of observations...
. - By reducing the number of intervals in the temperature variable (i.e., increasing its grain size), we increase the amount of sample data indexed by each interval designation. Thus, by coarsening the variable, we increase sample sizes and achieve better statistical estimation. In this sense, increasing granularity provides an antidote to the so-called curse of dimensionalityCurse of dimensionalityThe curse of dimensionality refers to various phenomena that arise when analyzing and organizing high-dimensional spaces that do not occur in low-dimensional settings such as the physical space commonly modeled with just three dimensions.There are multiple phenomena referred to by this name in...
, which relates to the exponentially decrease in statistical power with increase in number of dimensions or variable cardinality. - Independent of prior domain knowledge, it is often the case that meaningful regularities (i.e., which can be detected by a given learning methodology, representational language, etc.) may exist at one level of resolution and not at another.
Conditional probability
In probability theory, the "conditional probability of A given B" is the probability of A if B is known to occur. It is commonly notated P, and sometimes P_B. P can be visualised as the probability of event A when the sample space is restricted to event B...
threshold such as
. In the special case where , this recognition system is essentially detecting logical implication of the form or, in words, "if , then ". The system's ability to recognize such implications (or, in general, conditional probabilities exceeding threshold) is partially contingent on the resolution with which the system analyzes the variables.As an example of this last point, consider the feature space shown to the right. The variables may each be regarded at two different resolutions. Variable
may be regarded at a high (quaternary) resolution wherein it takes on the four values or at a lower (binary) resolution wherein it takes on the two values . Similarly, variable may be regarded at a high (quaternary) resolution or at a lower (binary) resolution, where it takes on the values or , respectively. It will be noted that at the high resolution, there are no detectable implications of the form , since every is associated with more than one , and thus, for all , . However, at the low (binary) variable resolution, two bilateral implications become detectable: and , since every occurs iff and occurs iff . Thus, a pattern recognition system scanning for implications of this kind would find them at the binary variable resolution, but would fail to find them at the higher quaternary variable resolution.Issues and methods
It is not feasible to exhaustively test all possible discretization resolutions on all variables in order to see which combination of resolutions yields interesting or significant results. Instead, the feature space must be preprocessed (often by an entropyInformation entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
analysis of some kind) so that some guidance can be given as to how the discretization process should proceed. Moreover, one cannot generally achieve good results by naively analyzing and discretizing each variable independently, since this may obliterate the very interactions that we had hoped to discover.
A sample of papers that address the problem of variable discretization in general, and multiple-variable discretization in particular, are as follows: , , , , , , , , , , , , , , , ,
, , , , .
Variable granulation (clustering/aggregation/transformation)
Variable granulation is a term that could describe a variety of techniques, most of which are aimed at reducing dimensionality, redundancy, and storage requirements. We briefly describe some of the ideas here, and present pointers to the literature.Variable transformation
A number of classical methods, such as principal component analysis, multidimensional scalingMultidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
, factor analysis
Factor analysis
Factor analysis is a statistical method used to describe variability among observed, correlated variables in terms of a potentially lower number of unobserved, uncorrelated variables called factors. In other words, it is possible, for example, that variations in three or four observed variables...
, and structural equation modeling
Structural equation modeling
Structural equation modeling is a statistical technique for testing and estimating causal relations using a combination of statistical data and qualitative causal assumptions...
, and their relatives, fall under the genus of "variable transformation." Also in this category are more modern areas of study such as dimensionality reduction
Dimensionality reduction
In machine learning, dimension reduction is the process of reducing the number of random variables under consideration, and can be divided into feature selection and feature extraction.-Feature selection:...
, projection pursuit
Projection pursuit
Projection pursuit is a type of statistical technique which involves finding the most "interesting" possible projections in multidimensional data. Often, projections which deviate more from a Normal distribution are considered to be more interesting...
, and independent component analysis
Independent component analysis
Independent component analysis is a computational method for separating a multivariate signal into additive subcomponents supposing the mutual statistical independence of the non-Gaussian source signals...
. The common goal of these methods in general is to find a representation of the data in terms of new variables, which are a linear or nonlinear transformation of the original variables, and in which important statistical relationships emerge. The resulting variable sets are almost always smaller than the original variable set, and hence these methods can be loosely said to impose a granulation on the feature space. These dimensionality reduction methods are all reviewed in the standard texts, such as , , and .
Variable aggregation
A different class of variable granulation methods derive more from data clusteringData clustering
Cluster analysis or clustering is the task of assigning a set of objects into groups so that the objects in the same cluster are more similar to each other than to those in other clusters....
methodologies than from the linear systems theory informing the above methods. It was noted fairly early that one may consider "clustering" related variables in just the same way that one considers clustering related data. In data clustering, one identifies a group of similar entities (using a measure of "similarity" suitable to the domain), and then in some sense replaces those entities with a prototype of some kind. The prototype may be the simple average of the data in the identified cluster, or some other representative measure. But the key idea is that in subsequent operations, we may be able to use the single prototype for the data cluster (along with perhaps a statistical model describing how exemplars are derived from the prototype) to stand in for the much larger set of exemplars. These prototypes are generally such as to capture most of the information of interest concerning the entities.
Mutual information
In probability theory and information theory, the mutual information of two random variables is a quantity that measures the mutual dependence of the two random variables...
between variables. Watanabe has shown that for any set of variables one can construct a polytomic (i.e., n-ary) tree representing a series of variable agglomerations in which the ultimate "total" correlation among the complete variable set is the sum of the "partial" correlations exhibited by each agglomerating subset (see figure). Watanabe suggests that an observer might seek to thus partition a system in such a way as to minimize the interdependence between the parts "... as if they were looking for a natural division or a hidden crack."
One practical approach to building such a tree is to successively choose for agglomeration the two variables (either atomic variables or previously agglomerated variables) which have the highest pairwise mutual information . The product of each agglomeration is a new (constructed) variable that reflects the local joint distribution
Joint distribution
In the study of probability, given two random variables X and Y that are defined on the same probability space, the joint distribution for X and Y defines the probability of events defined in terms of both X and Y...
of the two agglomerating variables, and thus possesses an entropy equal to their joint entropy.
(From a procedural standpoint, this agglomeration step involves replacing two columns in the attribute-value table—representing the two agglomerating variables—with a single column that has a unique value for every unique combination of values in the replaced columns . No information is lost by such an operation; however, it should be noted that if one is exploring the data for inter-variable relationships, it would generally not be desirable to merge redundant variables in this way, since in such a context it is likely to be precisely the redundancy or dependency between variables that is of interest; and once redundant variables are merged, their relationship to one another can no longer be studied.
System granulation (aggregation)
In database systems, aggregations (see e.g. OLAP aggregationOLAP
In computing, online analytical processing, or OLAP , is an approach to swiftly answer multi-dimensional analytical queries. OLAP is part of the broader category of business intelligence, which also encompasses relational reporting and data mining...
and Business intelligence
Business intelligence
Business intelligence mainly refers to computer-based techniques used in identifying, extracting, and analyzing business data, such as sales revenue by products and/or departments, or by associated costs and incomes....
systems) result in transforming original data tables (often called information systems) into the tables with different semantics of rows and columns, wherein the rows correspond to the groups (granules) of original tuples and the columns express aggregated information about original values within each of the groups. Such aggregations are usually based on SQL and its extensions. The resulting granules usually correspond to the groups of original tuples with the same values (or ranges) over some pre-selected original columns.
There are also other approaches wherein the groups are defined basing on, e.g., physical adjacency of rows. For example, Infobright
Infobright
Infobright is a commercial provider of column-oriented relational database software with a focus in machine-generated data. The company's head office is located in Toronto, Canada. Most of its research and development is based in Warsaw, Poland.-History:...
implements a database engine wherein data is partitioned onto rough rows, each consisting of 64K of physically consecutive (or almost consecutive) rows. Rough rows are automatically labeled with compact information about their values on data columns, often involving multi-column and multi-table relationships. It results in a higher layer of granulated information systems where objects correspond to rough rows and attributes - to various flavors of rough information. Database operations can be efficiently supported within such a new framework, with an access to the original data pieces still available.
Concept granulation (component analysis)
The origins of the granular computing ideology are to be found in the rough sets and fuzzy sets literatures. One of the key insights of rough set research—although by no means unique to it—is that, in general, the selection of different sets of features or variables will yield different concept granulations. Here, as in elementary rough set theory, by "concept" we mean a set of entities that are indistinguishable or indiscernible to the observer (i.e., a simple concept), or a set of entities that is composed from such simple concepts (i.e., a complex concept). To put it in other words, by projecting a data set (value-attribute system) onto different sets of variables, we recognize alternative sets of equivalence-class "concepts" in the data, and these different sets of concepts will in general be conducive to the extraction of different relationships and regularities.Equivalence class granulation
We illustrate with an example. Consider the attribute-value system below:| Object |  |  |  |  |  |
|---|---|---|---|---|---|
 |
1 | 2 | 0 | 1 | 1 |
 |
1 | 2 | 0 | 1 | 1 |
 |
2 | 0 | 0 | 1 | 0 |
 |
0 | 0 | 1 | 2 | 1 |
 |
2 | 1 | 0 | 2 | 1 |
 |
0 | 0 | 1 | 2 | 2 |
 |
2 | 0 | 0 | 1 | 0 |
 |
0 | 1 | 2 | 2 | 1 |
 |
2 | 1 | 0 | 2 | 2 |
 |
2 | 0 | 0 | 1 | 0 |
When the full set of attributes
is considered, we see that we have the following seven equivalence classes or primitive (simple) concepts:Thus, the two objects within the first equivalence class,
, cannot be distinguished from one another based on the available attributes, and the three objects within the second equivalence class, , cannot be distinguished from one another based on the available attributes. The remaining five objects are each discernible from all other objects. Now, let us imagine a projection of the attribute value system onto attribute alone, which would represent, for example, the view from an observer which is only capable of detecting this single attribute. Then we obtain the following much coarser equivalence class structure.This is in a certain regard the same structure as before, but at a lower degree of resolution (larger grain size). Just as in the case of value granulation (discretization/quantization), it is possible that relationships (dependencies) may emerge at one level of granularity that are not present at another. As an example of this, we can consider the effect of concept granulation on the measure known as attribute dependency (a simpler relative of the mutual information
Mutual information
In probability theory and information theory, the mutual information of two random variables is a quantity that measures the mutual dependence of the two random variables...
).
To establish this notion of dependency (see also rough sets), let
represent a particular concept granulation, where each is an equivalence class from the concept structure induced by attribute set . For example, if the attribute set consists of attribute alone, as above, then the concept structure will be composed of , , and . The dependency of attribute set on another attribute set , , is given byThat is, for each equivalence class
in , we add up the size of its "lower approximation" (see rough sets) by the attributes in , i.e., . More simply, this approximation is the number of objects which on attribute set can be positively identified as belonging to target set . Added across all equivalence classes in , the numerator above represents the total number of objects which—based on attribute set —can be positively categorized according to the classification induced by attributes . The dependency ratio therefore expresses the proportion (within the entire universe) of such classifiable objects, in a sense capturing the "synchronization" of the two concept structures and . The dependency "can be interpreted as a proportion of such objects in the information system for which it suffices to know the values of attributes in to determine the values of attributes in " (Ziarko & Shan 1995).Having gotten definitions now out of the way, we can make the simple observation that the choice of concept granularity (i.e., choice of attributes) will influence the detected dependencies among attributes. Consider again the attribute value table from above:
| Object |  |  |  |  |  |
|---|---|---|---|---|---|
 |
1 | 2 | 0 | 1 | 1 |
 |
1 | 2 | 0 | 1 | 1 |
 |
2 | 0 | 0 | 1 | 0 |
 |
0 | 0 | 1 | 2 | 1 |
 |
2 | 1 | 0 | 2 | 1 |
 |
0 | 0 | 1 | 2 | 2 |
 |
2 | 0 | 0 | 1 | 0 |
 |
0 | 1 | 2 | 2 | 1 |
 |
2 | 1 | 0 | 2 | 2 |
 |
2 | 0 | 0 | 1 | 0 |
Let us consider the dependency of attribute set
on attribute set
. That is, we wish to know what proportion of objects can be correctly classified into classes of based on knowledge of . The equivalence classes of and of are shown below.  |
 |
|---|---|
 |
 |
The objects that can be definitively categorized according to concept structure
based on are those in the set , and since there are six of these, the dependency of on , . This might be considered an interesting dependency in its own right, but perhaps in a particular data mining application only stronger dependencies are desired.We might then consider the dependency of the smaller attribute set
on the attribute set
. The move from to induces a coarsening of the class structure , as will be seen shortly. We wish again to know what proportion of objects can be correctly classified into the (now larger) classes of based on knowledge of . The equivalence classes of the new and of are shown below.  |
 |
|---|---|
 |
 |
Clearly,
has a coarser granularity than it did earlier. The objects that can now be definitively categorized according to the concept structure based on constitute the complete universe , and thus the dependency of on , . That is, knowledge of membership according to category set is adequate to determine category membership in with complete certainty; In this case we might say that . Thus, by coarsening the concept structure, we were able to find a stronger (deterministic) dependency. However, we also note that the classes induced in from the reduction in resolution necessary to obtain this deterministic dependency are now themselves large and few in number; as a result, the dependency we found, while strong, may be less valuable to us than the weaker dependency found earlier under the higher resolution view of .In general it is not possible to test all sets of attributes to see which induced concept structures yield the strongest dependencies, and this search must be therefore be guided with some intelligence. Papers which discuss this issue, and others relating to intelligent use of granulation, are those by Y.Y. Yao and Lotfi Zadeh listed in the #References below.
Component granulation
Another perspective on concept granulation may be obtained from work on parametric models of categories. In mixture modelMixture model
In statistics, a mixture model is a probabilistic model for representing the presence of sub-populations within an overall population, without requiring that an observed data-set should identify the sub-population to which an individual observation belongs...
learning, for example, a set of data is explained as a mixture of distinct Gaussian (or other) distributions. Thus, a large amount of data is "replaced" by a small number of distributions. The choice of the number of these distributions, and their size, can again be viewed as a problem of concept granulation. In general, a better fit to the data is obtained by a larger number of distributions or parameters, but in order to extract meaningful patterns, it is necessary to constrain the number of distributions, thus deliberately coarsening the concept resolution. Finding the "right" concept resolution is a tricky problem for which many methods have been proposed (e.g., AIC
Akaike information criterion
The Akaike information criterion is a measure of the relative goodness of fit of a statistical model. It was developed by Hirotsugu Akaike, under the name of "an information criterion" , and was first published by Akaike in 1974...
, BIC, MDL
Minimum description length
The minimum description length principle is a formalization of Occam's Razor in which the best hypothesis for a given set of data is the one that leads to the best compression of the data. MDL was introduced by Jorma Rissanen in 1978...
, etc.), and these are frequently considered under the rubric of "model regularization".
Different Interpretations of Granular Computing
Granular computing can be conceived as a framework of theories, methodologies, techniques, and tools that make use of information granules in the process of problem solving. In this sense, granular computing is used as an umbrella term to cover topics that have been studied in various fields in isolation. By examining all of these existing studies in light of the unified framework of granular computing and extracting their commonalities, it may be possible to develop a general theory for problem solving.In a more philosophical sense, granular computing can describe a way of thinking that relies on the human ability to perceive the real world under various levels of granularity (i.e., abstraction) in order to abstract and consider only those things that serve a specific interest and to switch among different granularities. By focusing on different levels of granularity, one can obtain different levels of knowledge, as well as a greater understanding of the inherent knowledge structure. Granular computing is thus essential in human problem solving and hence has a very significant impact on the design and implementation of intelligent systems.