Granulate and Conquer

Or so goes the fancy tagline for a particular problem-solving methodology, which predominantly comprises applied mathematics and IT (soft computing) [1], and addresses to a lesser extent the philosophical and ontological aspects [2][3]. More comprehensively, the field of Granular Computing combines efforts from philosophy, Artificial Intelligence, machine learning, database theory and data mining, (applied) mathematics with fuzzy logic and rough sets, among others. Themes addressed for computational problem solving tend to emphasise quantitative aspects of granularity, whereas the others put a higher emphasis on the qualitative component of granularity.

The “granulate and conquer” then amounts to a nice methodology to manage your data, information and knowledge. Applications can be as diverse as:

  • Using clustering techniques to make sense of mRNA expression patterns in microarray data [4], in this case applied to gene expression data of the malarial parasite Plasmodium falciparum;
  • Access control models in computer security, where, as Lin summarizes in [1], for each object p Î V there is a granule B(p) Í U of objects that are in conflict; put differently: eventually, after taking into account the various access rights for the resources (like documents, folders etc.), the resulting granule contains the list of enemies. For the interested reader: details about all this goes under the term Chinese Wall Security Policy Model;
  • Individual student-tailored study feedback. A slightly outdated description of such a systems is given by McCalla and Greer [5], but anyone familiar with Computer-based Training and its ‘test exam’ facility makes use of this approach: after doing the test, for the wrong answers given, it tells you in which paragraph(s) of the study material you can find the explanation so that you don’t have to go through all the material again and re-do only those few sections that you didn’t understand sufficiently.

Although the applications are very diverse, there are some commonalities in the approaches and (oftentimes one-off) models created for a particular purpose. More specifically, the underlying semantics of how the granulation is done and the relation between the entities within a granular level (/granule/grain) is consistent – but there is not one single type of granule. A first attempt to categorise those types of granularity is made by [3], where a taxonomy is presented with seven leaf categories. The main distinctions made are between scale-dependent granularity and, for the lack of a better term, non-scale-dependent granularity. Further divisions include, among others, granulating according to some mathematical formula (e.g. seconds, minutes, hours, etc.), sorting by means of one type of (primitive) relation (e.g. [structural-]partOf, [spatially-]containedIn), and aggregation of the same collection of instances of one type that subsequently can be partitioned in various ways at lower levels of detail using semantic criteria where the entity at a lower level is a subtype of the type at the coarser-grained level (e.g. a collection of phone points and finer-grained land-line and mobile phone points). The distinctions described in the article can guide a conceptual modeller to better distinguish between the types of granularity when representing domain knowledge and can be of use to the software developer to improve applications that use granularity in one way or another.

Coincidentally, a conference on Granular Computing will take place within a few weeks, which will be held in Atlanta, USA, from 10 to 12 May 2006. There is little time left to register here.

References

[1] Lin, T.Y. Toward a Theory of Granular Computing. IEEE International Conference on Granular Computing (GrC06). 10-12 May 2006, Atlanta, USA. Draft online available

[2] Yao, Y.Y. Perspectives of Granular Computing. IEEE Conference on Granular Computing (GrC05), 1:85-90.

[3] Keet, C.M. A taxonomy of types of granularity. IEEE Conference in Granular Computing (GrC06). 10-12 May 2006, Atlanta, USA.

[4] Zhou, Y., Young, J.A., Santrosyan, A., Chen, K., Yan, S.F., Winzeler, E.A. In silico gene function prediction using ontology-based pattern identification. Bioinformatics, 2005 21(7):1237-1245.
Online information available at: http://carrier.gnf.org/publications/OPI

[5] McCalla, G.I., Greer, J.E. Granularity Hierarchies. Computers and Mathematics with Applications: Special Issue on Semantic Networks, 1992, 23:363-376.

Advertisements

Comments are closed.