Article Search
닫기

Original Article

Split Viewer

International Journal of Fuzzy Logic and Intelligent Systems 2013; 13(4): 245-253

Published online December 30, 2013

https://doi.org/10.5391/IJFIS.2013.13.4.245

© The Korean Institute of Intelligent Systems

Associations Among Information Granules and Their Optimization in Granulation-Degranulation Mechanism of Granular Computing

Witold Pedrycz

Department of Electrical & Computer Engineering, University of Alberta, Edmonton, Canada,
Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, Jeddah, Saudi Arabia and
Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

Correspondence to :
Witold Pedrycz (wpedrycz@ualberta.ca)

Received: December 4, 2013; Revised: December 23, 2013; Accepted: December 24, 2013

Knowledge representation realized by information granules is one of the essential facets of granular computing and an area of intensive research. Fuzzy clustering and clustering are general vehicles to realize formation of information granules. Granulation – degranulation paradigm is one of the schemes determining and quantifying functionality and knowledge representation capabilities of information granules. In this study, we augment this paradigm by forming and optimizing a collection of associations among original and transformed information granules. We discuss several transformation schemes and analyze their properties. A series of numeric experiments is provided using which we quantify the improvement of the degranulation mechanisms offered by the optimized transformation of information granules.

Keywords: Information granules,Granulation-degranulation,Association among information granules,Fuzzy clustering,Granular computing

Information granules being at the center of granular computing [1, 2] are fundamental concepts using which we perceive, structure and process knowledge in a human-centric fashion. With the ongoing progress witnessed in granular computing, it has become apparent that a number of central problems still deserve our attention including a way of constructing information granules and a process of communication with the external world of data when conveying information granules. The first group of tasks directly relates to clustering and fuzzy clustering. Clustering has been a central conceptual and algorithmic vehicle supporting a realization of information granules. We have witnessed a great deal of developments in this domain [3] including numerous generalizations of clustering methods yielding a formation of higher order granular constructs, see [4] and granular fuzzy clusters [1], in general. There has been a visible role of fuzzy clustering in system modeling [5, 6]. The second problem of communication between the world of numeric data and granular entities revolves around a fundamental concept of the granulation-degranulation mechanism, assessment of its results quantified in terms of so–called degranulation criterion. The quality of information granules is captured by looking in a way how numeric data are granulated and afterwards de-granulated and to which extent a tandem of these two processing phases distorts the data. The distortions are inevitable (with several exceptions which deal with one–dimensional data and engage triangular membership functions, see [1, 7]).

The objective of this study is to further improve the granulation-degranulation abilities by introducing and optimizing transformation of information granules so that the resulting degranulation error becomes minimized. We formulate an overall task as an optimization problem, introduce several categories of transformation functions (realizing suitable interactions/associations among information granules) and discuss the underlying optimization procedures.

The study is organized as follows. We start with a concise review of information granulation realized with the aid of fuzzy clustering (Section 2). The granulation-degranulation idea along with the formal formulation of the problem is presented in Section 3. Section 4 is devoted to the design of interactions among information granules while in Section 5 we provide a number of illustrative experimental studies.

Throughout this study, we consider information granules formed in the n-dimensional space of real numbers, x ∈ ℝn.

Let us briefly recall the underlying concept and ensuing algorithmic aspects of the fuzzy C-means (FCM) algorithm [3, 8], which is one of the commonly used techniques of fuzzy clustering and a computational vehicle to build information granules.

Given is a collection of n-dimensional data (patterns) {xk|k = 1, 2,. . ., N} where xk ∈ Rn. Our objective is to determine its structure – a collection of “c” clusters (information granules). From the algorithmic perspective, the problem is posed as a minimization of the following objective function (performance index) Q

Q=i=1ck=1Nuikmxk-vi2

where v1, v2, . . ., vc are n-dimensional prototypes of the clusters and U = [uik] stands for a partition matrix expressing a way of allocation of the data to the corresponding clusters; uik is the membership degree of data xk in the i-th cluster. The distance between the data xk and prototype vi is denoted by ||.||. The fuzzification coefficient m (assuming values greater than 1) quantifies an impact of the membership grades on the individual clusters and implies a certain geometry of the ensuing information granules. Typically, the value of the fuzzification coefficient is set to 2. The partition matrix satisfies two essential and practically justifiable properties

0<k=1Nuik<N,         i=1,2,,ci=1cuik=1,         k=1,2,,N

The minimization of Q is completed with respect to U ∈ U and the prototypes vi of V = {v1, v2,...vc} of the clusters, namely

min Q with respect to UU,v1,v2,,vcn

Here U stands for a family of partition matrices, viz. the matrices satisfying conditions expressed by Eqs. (2) and (3).

From the optimization perspective, there are two individual optimization tasks to be carried out separately to determine the partition matrix and the prototypes. The results are well-documented in the literature and thoroughly discussed and the method has been intensively experimented with. The optimization process is iterative and involves successive computing of the partition matrix and the prototypes

uik=1j=1c(xk-vixk-vj)2

i = 1, 2, . . ., c; k = 1, 2, . . .,N.

vst=k=1Nuikmxktk=1Nuikm

s = 1, 2, . . ., c, t = 1, 2, . . ., n (in the above calculations of the prototypes it has been assumed that the distance function is Euclidean). We can look at the partition matrix by considering its individual rows – denoting them by A1, A2, .., Ac we emphasize that fuzzy clustering gives rise to a collection of information granules.

More formally, we can describe this knowledge representation in terms of information granules as a way of expressing any data point x in terms of the information granules and describe the result as a vector in the c-dimensional hypercube, namely [0,1]c,

G:n[0,1]c

The degranulation step is about a reconstruction of x on a basis of the family of information granules (clusters). It can be treated as a certain mapping

G-1:[0,1]cn

The capabilities of the information granules to reflect the structure of the original data can be conveniently expressed by comparing how much the result of degranulation, say x differs from the original pattern x, that is x. More formally, where and denote the corresponding phases of information granulation and de-granulation [9].

The crux of the granulation – degranulation principle is visualized in Figure 1 [1]. Note the transformations and operate between the spaces of data and the abstract space of information granules.

Let us start with the granulation phase. More specifically, x is expressed in the form of the membership grades ui of x to the individual granules Ai, which form a solution to the following optimization problem

Mini=1cui(x)x-vi2

subject to the usual constraints imposed on the degrees of membership

i=1cui(x)=1         ui(x)[0,1]

The solution to the problem (we use here Lagrange multipliers) comes in the form,

Ai(x)=ui(x)=1j=1c(x-vix-vj)2

For the degranulation phase, given ui(x) and the prototypes vi, the vector is considered as a solution to the minimization problem in which we reconstruct (degranulate) original x when using the prototypes and the corresponding membership grades

i=1Nui(x)x^-vi2

Considering the use of the Euclidean distance in the above performance index, the subsequent calculations are straightforward yielding the result

x^=i=1cui(x)vii=1cui(x)

It is important to note that the description of x in more abstract fashion realized by means of Ai and being followed by the consecutive degranulation brings about a certain granulation error (which is inevitable given a fact that we move back and forth between different levels of abstraction). While the above formulas pertain to the granulation realized by fuzzy sets, the granulation-degranulation error is also present when dealing with sets (intervals). In this case we are faced with a quantization error, which becomes inevitable when working with A/D (granulation) and D/A (degranulation) conversion mechanisms. The problem formulated above is also associated with vector quantization, which has been widely studied in the literature, cf. [1014].

The quality of the granulation-degranulation scheme is quantified by means of the following performance index [9]

V=k=1Nxk-x^k2

This performance index articulates how much the reconstruction error is related with the representation capabilities of information granules.

Denoting information granules formed thorough the process of clustering by A1, A2, ..Ac we consider a certain framework of interaction among them where such interaction gives rise to the enhancement of the degranulation features and subsequently a reduction of the degranulation error. To highlight the essence of the approach, we can refer to Figure 2.

The essence of this enhanced mechanism dwells on a mapping (transformation) F: {A1, A2,.., Ac} → {B1, B2.,. . ., Bc} where Bi= F(A1, A2, . . ., Ac). The original membership functions are affected by their interaction with other information granules. The newly formed granules are developed in a way it furnishes them with better degranulation capabilities (viz. lower degranulation error).

In general, the transformation F: [0,1]c → [0,1]c can be implemented in numerous ways. Several interesting and practically viable alternatives are summarized in Table 1. The same table includes some comments about the nature of the mapping.

The transformation F is typically endowed with some parameters (say a matrix of weights) and those imply the flexibility of the transformation. Both the type of the mapping as well as its parameters (their numeric values) are subject to the optimization guided by the degranulation error V. More formally, we can describe the result of this optimization as follows

(Fopt,wopt)=arg minF,wV

where Fopt is an optimal transformation (coming out of a finite family of alternatives) whereas wopt is an optimized vector of its parameters. The minimization shown in Eq. (15) is realized with regard to the type of the transformation F and its parameters w.

As to the development of interactions, a certain general tendency can be observed. Consider a linear combination of original information granules shown in Table 1. Let us rewrite it in the following form

Bi(x)=Ai(x)+j=1jicwijAj(x)=Ai(x)+j=1jiwij>0cwijAj(x)+j=1jiwij<0cwijAj(x)

We note that Bi is a distorted (transformed) version of Ai in which in an attempt to minimize the degranulation error the original information granule Ai is impacted by the membership grades of the remaining Aj s. Depending upon the sign of the weights, this process is of excitatory (wij > 0) or inhibitory (wij < 0) nature. In other words, those Ajs associated with the negative weights wij form an inhibitory link while the excitatory link is realized by the Aj coming with the positive entries of W. A lack of interaction is observed when wij are close to zero for all i ≠ j or W = I where I is an identity matrix. While more sophisticated transformation may contribute to the lower degranulation error, the interpretability of the transformation itself could be more difficult because of the existence of more nonlinear and convoluted character of established interactions among information granules.

In all experiments, we consider the linear transformation of information granules (Table 1). Particle swarm optimization is used as an optimization vehicle [15]. We consider a generic version of this method where the dynamics (velocity and position) of each individual of the swarm of “M” particles is governed by the following expressions:

velocity:vij(iter+1)=wvij(iter)+c1rij(pij(iter)-xij(iter))+c2r2j(pgj(iter)-xij(iter))position:xij(iter+1)=xij(iter)+vij(iter+1)

i = 1, 2, . . .,M and j = 1, 2, . . ., r. Here vi is the velocity of the i-th particle in a given search space of dimensionality “r” and r1 and r2 are the vectors of random numbers drawn from the uniform distribution over the unit interval. pi is the best position of the i-th particle observed so far and pg is the best particle in the entire swarm. The update of the particle is realized by adding the velocity vi(iter+1) to the current position xi(iter). The main parameters of this optimization environment is set as follows (these specific numeric values are those commonly encountered in the literature): c1 = c2 = 1.49, w = 0.6. The range of the admissible values of the weights is set to [−4, 4].

The size of the population was set to 120 individuals whereas the number of generations was equal to 100. With regard to the use of the FCM algorithm, the fuzzification coefficient is set 2 and the method was run for 60 iterations (at which point no changes to the values of the objective function were reported). The initial point of optimization was set up randomly by choosing a partition matrix with random entries. The distance function used to run FCM as well as to compute the degranulation error Eq. (14), is the weighted Euclidean distance in the form a-b2=j=1n(aj-bj)2σj2 where sj stands for a standard deviation of the j-th variable.

5.1 Synthetic Data

We start with a synthetic two-dimensional data with intent of gaining a better insight into the nature of the optimization process and the produced results. The data set exhibits three well-delineated and compact clusters (groups), Figure 3.

We formed c = 2, 3, and 4 information granules (fuzzy clusters) and determined the resulting degranulation error for all these situations, see Figure 4.

The most visible improvement is noted for c = 2. Just to observe in which way the reduced value of V translates into the character of the reconstructed data, Figure 5 contrasts the results obtained when no associations among information granules were considered. It is apparent that in this case a number of data were collapsed whereas the inclusion of the associations help retain the original data as it is visible in Figure 5(b), especially with regard to the cluster of data positioned close to the origin.

The matrix of the parameters W delivers a detailed insight into the relationships among information granules. Here we have

W=[1.00-0.05-0.091.00]W=[1.000.08-0.06-0.011.00-0.05-0.03-0.031.00]W=[1.000.37-0.140.041.011.000.22-0.080.63-0.151.00-0.03-1.10.44-0.501.00]

The relationships (associations) between information granules are more visible with the increase of the number of clusters with both inhibitory and excitatory linkages being present.

5.2 Selected Machine Learning Repository Data

A collection of three data sets coming from the Machine Learning repository http://archive.ics.uci.edu/ml/is considered, namely e-coli, auto, and housing. The snapshots of the progression of the optimization process where the fitness function (degranulation error) is reported in successive generations are presented in Figure 6.

The plots of V treated as a function of the number of clusters are displayed in a series of figures, Figure 7.

In all experiments, there is a visible improvement provided by invoking associations among information granules. This enhancement is quite steady irrespectively from the number of clusters used in the granulation process. We also witness a saturation effect meaning that the values of V tend to stabilize with the increase of the number of clusters. The plots displayed in Figure 8 deliver a certain look at the values of the weights; the diversity of the inhibitory and excitatory effects delivered by their combination is also apparent. A more global view can be formed by considering a sum of the weights reported in the individual rows of the weight matrix (not counting the entries positioned on a main diagonal) – these numbers tell us about an overall impact on the corresponding fuzzy set that arose as a result of the transformation. As illustrated in Figure 9, there is a visible diversity of excitatory and inhibitory influences among information granules.

Understanding and quantifying information granules in terms of their representation capabilities is essential to further advancements of granular computing and pursuing their role in reasoning and modeling schemes. The study covered here underlines a facet of degranulation aspects and its improvement by admitting and quantifying linkages existing among information granules. This helps gain a better insight into the nature and interaction among information granules built on a basis of numeric data. In the numeric studies reported in the paper, we stressed an important role of associations of fuzzy sets. While in this study we focused on the formalism of fuzzy sets (and fuzzy clustering), the developed framework is of general character and as such can be investigated in depth when dealing with other formalisms of information granules (sets, rough sets, shadowed sets and others).

Fig. 1.

The granulation-degranulation mechanism: a general view at the level of processing information granules. FCM, fuzzy C-mean.


Fig. 2.

Interaction–augmented degranulation mechanism; note a processing module resulting in a layer of interaction among original fuzzy sets. FCM, fuzzy C-mean.


Fig. 3.

Two-dimensional synthetic data.


Fig. 4.

Degranulation error V reported for c = 2, 3, and 4. The upper (grey) line concerns the error obtained when no associations among information granules are studied; W=I.


Fig. 5.

Results of degranulation: (a) no associations involved, and (b) optimized associations.


Fig. 6.

Fitness functions in successive generations: (a) e-coli, c=10, (b) auto, c=7, (c) housing c =9.


Fig. 7.

V versus “c”, grey lines relate to reconstruction results produced where no associations are involved: (a) e-coli, (b) auto, and (c) housing.


Fig. 8.

Entries of the association matrixW: (a) e-coli, (b) auto, and (c) housing.


Fig. 9.

Levels of interaction reported for the individual fuzzy sets: (a) e-coli, (b) auto, and (c) housing.


Table. 1.

Table 1. Selected alternatives of realization of transformation mechanisms.

Type of transformationFormulaComments
Linearyi=j=1cwijzjy = Wzy ∈ [0, 1]c, z ∈ [0, 1]cW = [wij] assumes values in [−a, a] where a > 0; wij =1. It is assumed that the sum is contained in [0, 1]
Nonlinearyi=φ(j=1cwijzj)φ: ℝ → [0, 1] is monotonically non-decreasing function. A typical example is a sigmoidal function, 1/(1 + exp(−u))
Higher order polynomial transformationyi=j=1cwijzj+j=1cvijzj2Generalizes a linear relationship, offers higher flexibility yet at expense of using more parameters
Logic transformationyi=Sj=1c(wijtzj)The transformation uses logic operations of t-norms (t) and t-conorms (s) [6, 9]

  1. Pedrycz, W (2013). Granular Computing: Analysis and Design of Intelligent Systems. Boca Raton, FL: Taylor & Francis
    CrossRef
  2. Pedrycz, W (2009). From fuzzy sets to shadowed sets: interpretation and computing. International Journal of Intelligent Systems. 24, 48-61. http://dx.doi.org/10.1002/int.20323
    CrossRef
  3. Pedrycz, W (2005). Knowledge-Based Clustering: From Data to Information Granules. Hoboken, NJ: Wiley
    CrossRef
  4. Hwang, C, and Rhee, FCH (2007). Uncertain fuzzy clustering: interval type-2 fuzzy approach to c-means. IEEE Transactions on Fuzzy Systems. 15, 107-120. http://dx.doi.org/10.1109/TFUZZ.2006.889763
    CrossRef
  5. Kim, SJ, and Seo, IY (2012). A clustering approach to wind power prediction based on support vector regression. International Journal of Fuzzy Logic and Intelligent Systems. 12, 108-112. http://dx.doi.org/10.5391/IJFIS.2012.12.2.108
    CrossRef
  6. Ye, XY, and Han, MM (2013). A systematic approach to improve fuzzy C-mean method based on genetic algorithm. International Journal of Fuzzy Logic and Intelligent Systems. 13, 178-185. http://dx.doi.org/10.5391/IJFIS.2013.13.3.178
    CrossRef
  7. Pedrycz, W (1994). Why triangular membership functions?. Fuzzy Sets and Systems. 64, -Array. http://dx.doi.org/10.1016/0165-0114(94)90003-5
    CrossRef
  8. Bezdek, JC (1981). Pattern Recognition With Fuzzy Objective Function Algorithms. New York, NY: Plenum Press
    CrossRef
  9. Pedrycz, W, and de Oliveira, JV (2008). A development of fuzzy encoding and decoding through fuzzy clustering. IEEE Transactions on Instrumentation and Measurement. 57, 829-837. http://dx.doi.org/10.1109/TIM.2007.913809
    CrossRef
  10. Gersho, A, and Gray, RM (1992). Vector Quantization and Signal Compression. Boston, MA: Kluwer Academic Publishers
    CrossRef
  11. Gray, RM (1984). Vector quantization. IEEE ASSP Magazine. 1, 4-29. http://dx.doi.org/10.1109/MASSP.1984.1162229
    CrossRef
  12. Lendasse, A, Francois, D, Wertz, V, and Verleysen, M (2005). Vector quantization: a weighted version for time-series forecasting. Future Generation Computer Systems. 21, 1056-1067. http://dx.doi.org/10.1016/j.future.2004.03.006
    CrossRef
  13. Linde, Y, Buzo, A, and Gray, RM (1980). An algorithm for vector quantizer design. IEEE Transactions on Communications. 28, 84-95. http://dx.doi.org/10.1109/TCOM.1980.1094577
    CrossRef
  14. Yair, E, Zeger, K, and Gersho, A (1992). Competitive learning and soft competition for vector quantizer design. IEEE Transactions on Signal Processing. 40, 294-309. http://dx.doi.org/10.1109/78.124940
    CrossRef
  15. Yuhui, S, and Eberhart, RC . Empirical study of particle swarm optimization., Proceedings of the 1999 Congress on Evolutionary Computation, July 6–9, 1999, Washington, DC, Array, pp.1945-1950. http://dx.doi.org/10.1109/CEC.1999.785511

Witold Pedrycz is a Professor and Canada Research Chair (CRC) in Computational Intelligence in the Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Canada. He is also with the Systems Research Institute of the Polish Academy of Sciences, Warsaw, Poland. He also holds an appointment of special professorship in the School of Computer Science, University of Nottingham, UK. In 2009 Dr. Pedrycz was elected a foreign member of the Polish Academy of Sciences. In 2012 he was elected a Fellow of the Royal Society of Canada. Witold Pedrycz has been a member of numerous program committees of IEEE conferences in the area of fuzzy sets and neurocomputing. In 2007 he received a prestigious Norbert Wiener award from the IEEE Systems, Man, and Cybernetics Council. He is a recipient of the IEEE Canada Computer Engineering Medal 2008. In 2009 he has received a Cajastur Prize for Soft Computing from the European Centre for Soft Computing for “pioneering and multi-faceted contributions to granular computing”. In 2013 has was awarded a Killam Prize.

His main research directions involve computational intelligence, fuzzy modeling and granular computing, knowledge discovery and data mining, fuzzy control, pattern recognition, knowledge-based neural networks, relational computing, and Software Engineering. He has published numerous papers in this area. He is also an author of 15 research monographs covering various aspects of computational intelligence, data mining, and software engineering.

Dr. Pedrycz is intensively involved in editorial activities. He is an Editor-in-Chief of Information Sciences, Editor-in-Chief of IEEE Transactions on Systems, Man, and Cybernetics Systems and Editor-in-Chief of WIREs Data Mining and Knowledge Discovery (Wiley). He currently serves as an Associate Editor of IEEE Transactions on Fuzzy Systems and is a member of a number of editorial boards of other international journals.

Article

Original Article

International Journal of Fuzzy Logic and Intelligent Systems 2013; 13(4): 245-253

Published online December 30, 2013 https://doi.org/10.5391/IJFIS.2013.13.4.245

Copyright © The Korean Institute of Intelligent Systems.

Associations Among Information Granules and Their Optimization in Granulation-Degranulation Mechanism of Granular Computing

Witold Pedrycz

Department of Electrical & Computer Engineering, University of Alberta, Edmonton, Canada,
Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, Jeddah, Saudi Arabia and
Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

Correspondence to:Witold Pedrycz (wpedrycz@ualberta.ca)

Received: December 4, 2013; Revised: December 23, 2013; Accepted: December 24, 2013

Abstract

Knowledge representation realized by information granules is one of the essential facets of granular computing and an area of intensive research. Fuzzy clustering and clustering are general vehicles to realize formation of information granules. Granulation – degranulation paradigm is one of the schemes determining and quantifying functionality and knowledge representation capabilities of information granules. In this study, we augment this paradigm by forming and optimizing a collection of associations among original and transformed information granules. We discuss several transformation schemes and analyze their properties. A series of numeric experiments is provided using which we quantify the improvement of the degranulation mechanisms offered by the optimized transformation of information granules.

Keywords: Information granules,Granulation-degranulation,Association among information granules,Fuzzy clustering,Granular computing

1. Introduction

Information granules being at the center of granular computing [1, 2] are fundamental concepts using which we perceive, structure and process knowledge in a human-centric fashion. With the ongoing progress witnessed in granular computing, it has become apparent that a number of central problems still deserve our attention including a way of constructing information granules and a process of communication with the external world of data when conveying information granules. The first group of tasks directly relates to clustering and fuzzy clustering. Clustering has been a central conceptual and algorithmic vehicle supporting a realization of information granules. We have witnessed a great deal of developments in this domain [3] including numerous generalizations of clustering methods yielding a formation of higher order granular constructs, see [4] and granular fuzzy clusters [1], in general. There has been a visible role of fuzzy clustering in system modeling [5, 6]. The second problem of communication between the world of numeric data and granular entities revolves around a fundamental concept of the granulation-degranulation mechanism, assessment of its results quantified in terms of so–called degranulation criterion. The quality of information granules is captured by looking in a way how numeric data are granulated and afterwards de-granulated and to which extent a tandem of these two processing phases distorts the data. The distortions are inevitable (with several exceptions which deal with one–dimensional data and engage triangular membership functions, see [1, 7]).

The objective of this study is to further improve the granulation-degranulation abilities by introducing and optimizing transformation of information granules so that the resulting degranulation error becomes minimized. We formulate an overall task as an optimization problem, introduce several categories of transformation functions (realizing suitable interactions/associations among information granules) and discuss the underlying optimization procedures.

The study is organized as follows. We start with a concise review of information granulation realized with the aid of fuzzy clustering (Section 2). The granulation-degranulation idea along with the formal formulation of the problem is presented in Section 3. Section 4 is devoted to the design of interactions among information granules while in Section 5 we provide a number of illustrative experimental studies.

Throughout this study, we consider information granules formed in the n-dimensional space of real numbers, x ∈ ℝn.

2. Information Granulation Through Fuzzy Clustering

Let us briefly recall the underlying concept and ensuing algorithmic aspects of the fuzzy C-means (FCM) algorithm [3, 8], which is one of the commonly used techniques of fuzzy clustering and a computational vehicle to build information granules.

Given is a collection of n-dimensional data (patterns) {xk|k = 1, 2,. . ., N} where xk ∈ Rn. Our objective is to determine its structure – a collection of “c” clusters (information granules). From the algorithmic perspective, the problem is posed as a minimization of the following objective function (performance index) Q

Q=i=1ck=1Nuikmxk-vi2

where v1, v2, . . ., vc are n-dimensional prototypes of the clusters and U = [uik] stands for a partition matrix expressing a way of allocation of the data to the corresponding clusters; uik is the membership degree of data xk in the i-th cluster. The distance between the data xk and prototype vi is denoted by ||.||. The fuzzification coefficient m (assuming values greater than 1) quantifies an impact of the membership grades on the individual clusters and implies a certain geometry of the ensuing information granules. Typically, the value of the fuzzification coefficient is set to 2. The partition matrix satisfies two essential and practically justifiable properties

0<k=1Nuik<N,         i=1,2,,ci=1cuik=1,         k=1,2,,N

The minimization of Q is completed with respect to U ∈ U and the prototypes vi of V = {v1, v2,...vc} of the clusters, namely

min Q with respect to UU,v1,v2,,vcn

Here U stands for a family of partition matrices, viz. the matrices satisfying conditions expressed by Eqs. (2) and (3).

From the optimization perspective, there are two individual optimization tasks to be carried out separately to determine the partition matrix and the prototypes. The results are well-documented in the literature and thoroughly discussed and the method has been intensively experimented with. The optimization process is iterative and involves successive computing of the partition matrix and the prototypes

uik=1j=1c(xk-vixk-vj)2

i = 1, 2, . . ., c; k = 1, 2, . . .,N.

vst=k=1Nuikmxktk=1Nuikm

s = 1, 2, . . ., c, t = 1, 2, . . ., n (in the above calculations of the prototypes it has been assumed that the distance function is Euclidean). We can look at the partition matrix by considering its individual rows – denoting them by A1, A2, .., Ac we emphasize that fuzzy clustering gives rise to a collection of information granules.

3. Granulation and Degranulation Principle

More formally, we can describe this knowledge representation in terms of information granules as a way of expressing any data point x in terms of the information granules and describe the result as a vector in the c-dimensional hypercube, namely [0,1]c,

G:n[0,1]c

The degranulation step is about a reconstruction of x on a basis of the family of information granules (clusters). It can be treated as a certain mapping

G-1:[0,1]cn

The capabilities of the information granules to reflect the structure of the original data can be conveniently expressed by comparing how much the result of degranulation, say x differs from the original pattern x, that is x. More formally, where and denote the corresponding phases of information granulation and de-granulation [9].

The crux of the granulation – degranulation principle is visualized in Figure 1 [1]. Note the transformations and operate between the spaces of data and the abstract space of information granules.

Let us start with the granulation phase. More specifically, x is expressed in the form of the membership grades ui of x to the individual granules Ai, which form a solution to the following optimization problem

Mini=1cui(x)x-vi2

subject to the usual constraints imposed on the degrees of membership

i=1cui(x)=1         ui(x)[0,1]

The solution to the problem (we use here Lagrange multipliers) comes in the form,

Ai(x)=ui(x)=1j=1c(x-vix-vj)2

For the degranulation phase, given ui(x) and the prototypes vi, the vector is considered as a solution to the minimization problem in which we reconstruct (degranulate) original x when using the prototypes and the corresponding membership grades

i=1Nui(x)x^-vi2

Considering the use of the Euclidean distance in the above performance index, the subsequent calculations are straightforward yielding the result

x^=i=1cui(x)vii=1cui(x)

It is important to note that the description of x in more abstract fashion realized by means of Ai and being followed by the consecutive degranulation brings about a certain granulation error (which is inevitable given a fact that we move back and forth between different levels of abstraction). While the above formulas pertain to the granulation realized by fuzzy sets, the granulation-degranulation error is also present when dealing with sets (intervals). In this case we are faced with a quantization error, which becomes inevitable when working with A/D (granulation) and D/A (degranulation) conversion mechanisms. The problem formulated above is also associated with vector quantization, which has been widely studied in the literature, cf. [1014].

The quality of the granulation-degranulation scheme is quantified by means of the following performance index [9]

V=k=1Nxk-x^k2

This performance index articulates how much the reconstruction error is related with the representation capabilities of information granules.

4. Building Interactions Among Information Granules

Denoting information granules formed thorough the process of clustering by A1, A2, ..Ac we consider a certain framework of interaction among them where such interaction gives rise to the enhancement of the degranulation features and subsequently a reduction of the degranulation error. To highlight the essence of the approach, we can refer to Figure 2.

The essence of this enhanced mechanism dwells on a mapping (transformation) F: {A1, A2,.., Ac} → {B1, B2.,. . ., Bc} where Bi= F(A1, A2, . . ., Ac). The original membership functions are affected by their interaction with other information granules. The newly formed granules are developed in a way it furnishes them with better degranulation capabilities (viz. lower degranulation error).

In general, the transformation F: [0,1]c → [0,1]c can be implemented in numerous ways. Several interesting and practically viable alternatives are summarized in Table 1. The same table includes some comments about the nature of the mapping.

The transformation F is typically endowed with some parameters (say a matrix of weights) and those imply the flexibility of the transformation. Both the type of the mapping as well as its parameters (their numeric values) are subject to the optimization guided by the degranulation error V. More formally, we can describe the result of this optimization as follows

(Fopt,wopt)=arg minF,wV

where Fopt is an optimal transformation (coming out of a finite family of alternatives) whereas wopt is an optimized vector of its parameters. The minimization shown in Eq. (15) is realized with regard to the type of the transformation F and its parameters w.

As to the development of interactions, a certain general tendency can be observed. Consider a linear combination of original information granules shown in Table 1. Let us rewrite it in the following form

Bi(x)=Ai(x)+j=1jicwijAj(x)=Ai(x)+j=1jiwij>0cwijAj(x)+j=1jiwij<0cwijAj(x)

We note that Bi is a distorted (transformed) version of Ai in which in an attempt to minimize the degranulation error the original information granule Ai is impacted by the membership grades of the remaining Aj s. Depending upon the sign of the weights, this process is of excitatory (wij > 0) or inhibitory (wij < 0) nature. In other words, those Ajs associated with the negative weights wij form an inhibitory link while the excitatory link is realized by the Aj coming with the positive entries of W. A lack of interaction is observed when wij are close to zero for all i ≠ j or W = I where I is an identity matrix. While more sophisticated transformation may contribute to the lower degranulation error, the interpretability of the transformation itself could be more difficult because of the existence of more nonlinear and convoluted character of established interactions among information granules.

5. Experimental Studies

In all experiments, we consider the linear transformation of information granules (Table 1). Particle swarm optimization is used as an optimization vehicle [15]. We consider a generic version of this method where the dynamics (velocity and position) of each individual of the swarm of “M” particles is governed by the following expressions:

velocity:vij(iter+1)=wvij(iter)+c1rij(pij(iter)-xij(iter))+c2r2j(pgj(iter)-xij(iter))position:xij(iter+1)=xij(iter)+vij(iter+1)

i = 1, 2, . . .,M and j = 1, 2, . . ., r. Here vi is the velocity of the i-th particle in a given search space of dimensionality “r” and r1 and r2 are the vectors of random numbers drawn from the uniform distribution over the unit interval. pi is the best position of the i-th particle observed so far and pg is the best particle in the entire swarm. The update of the particle is realized by adding the velocity vi(iter+1) to the current position xi(iter). The main parameters of this optimization environment is set as follows (these specific numeric values are those commonly encountered in the literature): c1 = c2 = 1.49, w = 0.6. The range of the admissible values of the weights is set to [−4, 4].

The size of the population was set to 120 individuals whereas the number of generations was equal to 100. With regard to the use of the FCM algorithm, the fuzzification coefficient is set 2 and the method was run for 60 iterations (at which point no changes to the values of the objective function were reported). The initial point of optimization was set up randomly by choosing a partition matrix with random entries. The distance function used to run FCM as well as to compute the degranulation error Eq. (14), is the weighted Euclidean distance in the form a-b2=j=1n(aj-bj)2σj2 where sj stands for a standard deviation of the j-th variable.

5.1 Synthetic Data

We start with a synthetic two-dimensional data with intent of gaining a better insight into the nature of the optimization process and the produced results. The data set exhibits three well-delineated and compact clusters (groups), Figure 3.

We formed c = 2, 3, and 4 information granules (fuzzy clusters) and determined the resulting degranulation error for all these situations, see Figure 4.

The most visible improvement is noted for c = 2. Just to observe in which way the reduced value of V translates into the character of the reconstructed data, Figure 5 contrasts the results obtained when no associations among information granules were considered. It is apparent that in this case a number of data were collapsed whereas the inclusion of the associations help retain the original data as it is visible in Figure 5(b), especially with regard to the cluster of data positioned close to the origin.

The matrix of the parameters W delivers a detailed insight into the relationships among information granules. Here we have

W=[1.00-0.05-0.091.00]W=[1.000.08-0.06-0.011.00-0.05-0.03-0.031.00]W=[1.000.37-0.140.041.011.000.22-0.080.63-0.151.00-0.03-1.10.44-0.501.00]

The relationships (associations) between information granules are more visible with the increase of the number of clusters with both inhibitory and excitatory linkages being present.

5.2 Selected Machine Learning Repository Data

A collection of three data sets coming from the Machine Learning repository http://archive.ics.uci.edu/ml/is considered, namely e-coli, auto, and housing. The snapshots of the progression of the optimization process where the fitness function (degranulation error) is reported in successive generations are presented in Figure 6.

The plots of V treated as a function of the number of clusters are displayed in a series of figures, Figure 7.

In all experiments, there is a visible improvement provided by invoking associations among information granules. This enhancement is quite steady irrespectively from the number of clusters used in the granulation process. We also witness a saturation effect meaning that the values of V tend to stabilize with the increase of the number of clusters. The plots displayed in Figure 8 deliver a certain look at the values of the weights; the diversity of the inhibitory and excitatory effects delivered by their combination is also apparent. A more global view can be formed by considering a sum of the weights reported in the individual rows of the weight matrix (not counting the entries positioned on a main diagonal) – these numbers tell us about an overall impact on the corresponding fuzzy set that arose as a result of the transformation. As illustrated in Figure 9, there is a visible diversity of excitatory and inhibitory influences among information granules.

6. Conclusion

Understanding and quantifying information granules in terms of their representation capabilities is essential to further advancements of granular computing and pursuing their role in reasoning and modeling schemes. The study covered here underlines a facet of degranulation aspects and its improvement by admitting and quantifying linkages existing among information granules. This helps gain a better insight into the nature and interaction among information granules built on a basis of numeric data. In the numeric studies reported in the paper, we stressed an important role of associations of fuzzy sets. While in this study we focused on the formalism of fuzzy sets (and fuzzy clustering), the developed framework is of general character and as such can be investigated in depth when dealing with other formalisms of information granules (sets, rough sets, shadowed sets and others).

Fig 1.

Figure 1.

The granulation-degranulation mechanism: a general view at the level of processing information granules. FCM, fuzzy C-mean.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 2.

Figure 2.

Interaction–augmented degranulation mechanism; note a processing module resulting in a layer of interaction among original fuzzy sets. FCM, fuzzy C-mean.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 3.

Figure 3.

Two-dimensional synthetic data.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 4.

Figure 4.

Degranulation error V reported for c = 2, 3, and 4. The upper (grey) line concerns the error obtained when no associations among information granules are studied; W=I.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 5.

Figure 5.

Results of degranulation: (a) no associations involved, and (b) optimized associations.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 6.

Figure 6.

Fitness functions in successive generations: (a) e-coli, c=10, (b) auto, c=7, (c) housing c =9.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 7.

Figure 7.

V versus “c”, grey lines relate to reconstruction results produced where no associations are involved: (a) e-coli, (b) auto, and (c) housing.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 8.

Figure 8.

Entries of the association matrixW: (a) e-coli, (b) auto, and (c) housing.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Fig 9.

Figure 9.

Levels of interaction reported for the individual fuzzy sets: (a) e-coli, (b) auto, and (c) housing.

The International Journal of Fuzzy Logic and Intelligent Systems 2013; 13: 245-253https://doi.org/10.5391/IJFIS.2013.13.4.245

Table 1 . Selected alternatives of realization of transformation mechanisms.

Type of transformationFormulaComments
Linearyi=j=1cwijzjy = Wzy ∈ [0, 1]c, z ∈ [0, 1]cW = [wij] assumes values in [−a, a] where a > 0; wij =1. It is assumed that the sum is contained in [0, 1]
Nonlinearyi=φ(j=1cwijzj)φ: ℝ → [0, 1] is monotonically non-decreasing function. A typical example is a sigmoidal function, 1/(1 + exp(−u))
Higher order polynomial transformationyi=j=1cwijzj+j=1cvijzj2Generalizes a linear relationship, offers higher flexibility yet at expense of using more parameters
Logic transformationyi=Sj=1c(wijtzj)The transformation uses logic operations of t-norms (t) and t-conorms (s) [6, 9]

References

  1. Pedrycz, W (2013). Granular Computing: Analysis and Design of Intelligent Systems. Boca Raton, FL: Taylor & Francis
    CrossRef
  2. Pedrycz, W (2009). From fuzzy sets to shadowed sets: interpretation and computing. International Journal of Intelligent Systems. 24, 48-61. http://dx.doi.org/10.1002/int.20323
    CrossRef
  3. Pedrycz, W (2005). Knowledge-Based Clustering: From Data to Information Granules. Hoboken, NJ: Wiley
    CrossRef
  4. Hwang, C, and Rhee, FCH (2007). Uncertain fuzzy clustering: interval type-2 fuzzy approach to c-means. IEEE Transactions on Fuzzy Systems. 15, 107-120. http://dx.doi.org/10.1109/TFUZZ.2006.889763
    CrossRef
  5. Kim, SJ, and Seo, IY (2012). A clustering approach to wind power prediction based on support vector regression. International Journal of Fuzzy Logic and Intelligent Systems. 12, 108-112. http://dx.doi.org/10.5391/IJFIS.2012.12.2.108
    CrossRef
  6. Ye, XY, and Han, MM (2013). A systematic approach to improve fuzzy C-mean method based on genetic algorithm. International Journal of Fuzzy Logic and Intelligent Systems. 13, 178-185. http://dx.doi.org/10.5391/IJFIS.2013.13.3.178
    CrossRef
  7. Pedrycz, W (1994). Why triangular membership functions?. Fuzzy Sets and Systems. 64, -Array. http://dx.doi.org/10.1016/0165-0114(94)90003-5
    CrossRef
  8. Bezdek, JC (1981). Pattern Recognition With Fuzzy Objective Function Algorithms. New York, NY: Plenum Press
    CrossRef
  9. Pedrycz, W, and de Oliveira, JV (2008). A development of fuzzy encoding and decoding through fuzzy clustering. IEEE Transactions on Instrumentation and Measurement. 57, 829-837. http://dx.doi.org/10.1109/TIM.2007.913809
    CrossRef
  10. Gersho, A, and Gray, RM (1992). Vector Quantization and Signal Compression. Boston, MA: Kluwer Academic Publishers
    CrossRef
  11. Gray, RM (1984). Vector quantization. IEEE ASSP Magazine. 1, 4-29. http://dx.doi.org/10.1109/MASSP.1984.1162229
    CrossRef
  12. Lendasse, A, Francois, D, Wertz, V, and Verleysen, M (2005). Vector quantization: a weighted version for time-series forecasting. Future Generation Computer Systems. 21, 1056-1067. http://dx.doi.org/10.1016/j.future.2004.03.006
    CrossRef
  13. Linde, Y, Buzo, A, and Gray, RM (1980). An algorithm for vector quantizer design. IEEE Transactions on Communications. 28, 84-95. http://dx.doi.org/10.1109/TCOM.1980.1094577
    CrossRef
  14. Yair, E, Zeger, K, and Gersho, A (1992). Competitive learning and soft competition for vector quantizer design. IEEE Transactions on Signal Processing. 40, 294-309. http://dx.doi.org/10.1109/78.124940
    CrossRef
  15. Yuhui, S, and Eberhart, RC . Empirical study of particle swarm optimization., Proceedings of the 1999 Congress on Evolutionary Computation, July 6–9, 1999, Washington, DC, Array, pp.1945-1950. http://dx.doi.org/10.1109/CEC.1999.785511