Granular computing
Granular computing is an emerging computing paradigm of information processing that concerns the processing of complex information entities called "information granules", which arise in the process of data abstraction and derivation of knowledge from information or data. 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
As mentioned above, granular computing is not an algorithm or process; there is no particular method that is called "granular computing". It is rather an approach to looking at data that recognizes how 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 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:
Value granulation (discretization/quantization)
One type of granulation is the quantization of variables. It is very common that in data mining or machine-learning applications 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 precision. 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, there is no expectation that minute variations in temperature 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, as an artifact of overfitting. By coarsening the temperature variable into intervals the difference between which we do anticipate 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 overfitting.
- By reducing the number of intervals in the temperature variable, 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 dimensionality, which relates to the exponential 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 may exist at one level of resolution and not at another.
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 resolution wherein it takes on the four values or at a lower resolution wherein it takes on the two values Similarly, variable may be regarded at a high resolution or at a lower resolution, where it takes on the values or respectively. 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 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 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, is 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 scaling, 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.Variable aggregation
A different class of variable granulation methods derive more from data clustering 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, 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 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 into 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 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. 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 which have the highest pairwise mutual information. The product of each agglomeration is a new 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, 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.