# Fuzzy Systems Based on Multispecies PSO Method in Spatial Analysis

Authors: Ferdinando Di Martino; Vincenzo Loia; Salvatore Sessa
Journal: Advances in Fuzzy Systems
 (2012)

---

## Abstract

We present a method by using the hierarchical cluster-based Multispecies particle swarm optimization to generate a fuzzy system of Takagi-Sugeno-Kang type encapsulated in a geographical information system considered as environmental decision support for spatial analysis. We consider a spatial area partitioned in subzones: the data measured in each subzone are used to extract a fuzzy rule set of above mentioned type. We adopt a similarity index (greater than a specific threshold) for comparing fuzzy systems generated for adjacent subzones.


---

## Body

## 1. Introduction

A geographical information system (shortly, GIS) is often used by the analyst as a decision support system for problem solving in spatial analysis (e.g., cf. [1–9]). In some works,  fuzzy inference systems are encapsulated in GIS tools, where the knowledge is represented by if-then rules. In [7], the authors present  an inference model, integrated in a GIS, based on Takagi-Sugeno-Kang  (shortly, TSK) fuzzy system [10, 11]. In [4], a first-order Takagi-Sugeno fuzzy inference system is generated  for estimating and simulating the discharge and sediment concentration in river basins. Also here we integrate in a tool GIS an inference model which generates a TSK-fuzzy system, based on the hierarchical cluster-based multiSpecies particle swarm optimization (shortly, HCMSPSO) algorithm [12] The spatial area of study is divided into subzones: for each subzone the correspondent TSK-fuzzy system is extracted by starting from the subset of patterns georeferred in that subzone. In our method, we calculate a similarity index between TSK-fuzzy systems generated for adjacent subzones: if this index is greater than a specific threshold, then the corresponding subzones and the data subsets are merged, and the TSK-fuzzy system is generated again for the new subzone. The partition of the area of study in subzones derives from the fact that the impact of the geographical characteristics necessarily involves spatial changes of the parameters forming the rule set of the fuzzy system.A subzone represents a spatial subarea (of the area of study) with homogeneous characteristics with respect to the phenomenon investigated: we can consider as examples  of  subzones those areas with a specific index (pollution index, risk index, vulnerability index, traffic index, etc.). The concept of division of the area of study in homogeneous subzones has been introduced in [13–15], in which the area is partitioned in iso-reliable zones, that is, in subzones with homogeneous reliability of the spatial characteristics.  Strictly speaking, the expert has provided a set of N patterns (x1,…,xn,y), where x=(x1,…,xn) is the n-dimensional vector input, and y is the output, measured on georeferred locations in the area of study. This expert does not know a priori the optimal  partition of the area of study in homogeneous subzones with respect to the fuzzy system to be generated; he already uses partitions defined for sociological, morphological, climatic characteristics. However, he does not know whether the same fuzzy system can be applied to two adjacent subzones. In this work, we propose a based particle swarm optimization (PSO) algorithm for optimizing the partition in homogeneous zones of the area of study: indeed we generate a TSK-fuzzy system for each subzone by using the so-called HCMSPSO algorithm [12], which is a variation of PSO, and we compare the TSK-fuzzy system in adjacent subzones. A TSK-fuzzy system [16] is composed from a set of r fuzzy rules Ri represented in the following form:
(1)Ri:IF(x1isAi1)⋯(xnisAin),then(yisfi),i=1,…,r,
where the fuzzy set Aij assumes the following Gaussian membership function:
(2)Aij=exp⁡[-(xj-mijσij)2].The firing strength of theith rule on x=(x1,…,xn) is given as
(3)μi(x)=∏j=1nAij=exp⁡[-∑j=1n(xj-mijσij)2].In the TSK-fuzzy system of zero order, the fuzzy setfi  is generally represented in the consequent as a constant ai0; the TSK-fuzzy system  of one order is given by a linear combination of the input variables:
(4)fi=ai0+∑i=1naijxj,
where the coefficient aij are real numbers. The output y is calculated by the weighted average defuzzification method:
(5)y′=∑i=1rμi(x)fi∑i=1rμi(x).The HCMSPSO algorithm generates an optimal TSK-fuzzy system by determining the numberr of rules and by optimizing the coefficient values mij, σij, and aij in each rule. In our approach, the geographical area of study is initially partitioned in Z subzones; for each subzone we apply the HCMSPSO algorithm to generate the optimal TSK-fuzzy system. Here, we give an evolution process in which at each iteration we merge adjacent subzones with a fuzzy rule-set similarity index greater then a predefined threshold. The process stops when no fuzzy rule-set similarity index associated to couple of adjacent subzones is greater or equal to the threshold.  We propose a similarity index based on the fuzzy inclusion concept given as
(6)Iii′jhk=∫xj0xj1min⁡[Aijh(xj),Ai′jk(xj)]dxjmax⁡[∫xj0xj1Aijh(xj)dxj,∫xj0xj1Ai′jk(xj)dxj],
where xj0 and xj1 are the lower and upper bounds of the domain of xj. If Iijhk=1, the two fuzzy sets overlap completely.In other words, given thehth and kth TSK-fuzzy systems correspondent to adjacent subzones and with the same number of rules, we define the following similarity index for each couple of rules ri and ri′, (i,i′)∈(1,…,r)2  as
(7)Iii′hk=∑j=1n+1Iii′jhkn+1,
which is a mean of (6) on the n+1 variables (n inputs and the output variable). Then, we order the rule sets of the two fuzzy systems in accordance to the following criteria:(i)
we choose the two rulesri and ri′  with the greatest  value Iii′hk. The two rules become the first rules of the respective fuzzy systems, and the index (7) can be written as I1hk;(ii)
among the remaining rules, we consider the two new rules  with  the index (7); these rules  become the second rules of the respective fuzzy systems and the index (7) can be written as I2hk; the process is repeated up to order all the rules in the two fuzzy sets.We calculate  the similarity index of the two TSK-fuzzy systems as(8)Shk=∑i=1rIihkr.The similarity valueShk is a mean of the values Iihk obtained for all the rules. We use this index to decide if the hth and kth  adjacent subzones can be merged. Our evolution process is a hierarchical iterative approach; initially the area of study is partitioned in a fine-grained set of subzones; the analyst divides the area of study into subzones based on significant geospatial characteristics with respect to the problem studied (e.g., he divides the area into subzones corresponding to municipalities in demographic problems, or corresponding to subzones with different climatic characteristics in meteorological problems). Since each subzone must contain a significant number of data points  (otherwise the partition would be too fine with respect to the distribution of the patterns), we impose the constraint that each subzone must contain at least Nth patterns, where Nth stands for a threshold number. At each iteration, the HCMSPSO algorithm is applied to generate an optimal  fuzzy system for each subzone. In Section 2, we introduce the HCMSPSO method, in Section 3 we present our method for finding the optimal partition of the area of study, in Section 4 we present some experimental results, and Section 5 is conclusive.


## 2. The HCMSPSO Algorithm: An Overview

The HCMSPSO algorithm [12] is a method based on the PSO algorithm for determining the optimal TSK-fuzzy system by using a set of patterns. The HCMSPSO determines the number r of rules and the optimal values of the parameters mij, σij, and aij of the membership functions in each rule.  In [12, 17–27], variations of the PSO algorithm are proposed.The HCMSPSO method originates from the cluster-based particle swarm optimization method (shortly, CPSO) [28], in which each swarm is used independently for optimizing a set of parameters. In HCMSPSO, each swarm forms a species and the number of species is set to the number of fuzzy rules r. each species is formed from Ps particles, and each particle in a species represents a single fuzzy rule. The ith species is used for optimizing the parameters in the ith fuzzy rule. The position siq of the qth particle in the ith species is given from the (2n+1)-dimensional vector:
(9)siq=(mi1q,…,minq,σi1q,…,σinq,ai0q)∈R2n+1
and from the (3n+1)-dimensional  vector:
(10)siq=(mi1q,…,minq,σi1q,…,σinq,ai0q,ai1q,…,ainq)∈R3n+1.
for a TSK-fuzzy system of first order. A TSK-fuzzy system of zero order is built by choosing one for each species of the Ps particles. To determine the final number of rules and generate the Ps particles in each species, the following iterative process is used:(1) initially we setr=1; we consider the first input pattern x(0), forming the first particle in the first species setting m1j1=xj(0) and  σ1j1=σInit, where σInit is a predefined value by determining the initial width of each fuzzy set;(2) we generate all the particles in the first species, associated to the fuzzy ruleR1; the qth particle is given by the formula (for TSK-fuzzy system of first order):
(11)s1q=(m11+Δm11q,…,min+Δm1nq,σ11+Δσ11q,…,σ1n+Δσ1nq,a10q,a11q,…,a1nq),
where q=1,…,Ps, Δm1jq and Δσ1jq represent small variations to m1j and σ1j, respectively, generated from the interval [-0.1,0.1];  the values a10q,a11q,…,a1nq are obtained randomly in the output y range;(3) for each successive patternx(k),k=2,…,N, we consider the rule with maximum firing strength given by
(12)I(k)=argmax⁡1≤i≤r[μi(x(k))].
If results μI(k)(x(k))≤μth, where μth is a predefined threshold,  then a new rule is generated by setting
(13)m(r+1)j(k)=xj(k),j=1,…,n,σ(r+1)j(k)=α∑j=1n(xj(k)-mIkjσIkj)2,j=1,…,n,
where α>0 determines the degree of overlapping between two clusters;(4) we generate all the particles in the (r+1)-species, associated to the fuzzy rule R(r+1); the qth particle is given by the formula (for TSK-fuzzy system of first order):
(14)s(r+1)q(k)=(m(r+1)1(k)+Δm(r+1)1q(k),…,m(r+1)n(k)+Δm(r+1)nq(k),σ(r+1)1(k)+Δσ(r+1)1q(k),…,σ(r+1)n(k)+Δσ(r+1)nq(k),a(r+1)0q,a(r+1)1q,…,a(r+1)nq),
where q=1,…,Ps, k=2,…,N, Δm(r+1)jq(k) and Δσ(r+1)jq(k) represent small variations to m(r+1)j(k) and σ(r+1)j(k), respectively, from the interval [-0.1,0.1]; the related values a(r+1)0q,a(r+1)1q,…,a(r+1)nq are obtained randomly  from an interval identical to the output y range;(5) we setr=r+1 and iterate the steps (3) and (4) for all the patterns. At the end of the process, we have generated r rules and r species with Ps particles.For each species, a partition of its particles is created in subspecies. A subspecies is a cluster of particles of a species. To create a subspecies partition of the particle of a species, we need to sort the particle of the species. The index used for sorting the particles of a species is the root means square error (RMSE) defined as(15)RMSE=∑k=1N[y′(k)-y(k)]2N,
where y′(k) is the output calculated using the defuzzification formula (5), and y(k) is the output value of the kth pattern. The successive steps are used for sorting the particles in each species based on the increasing value of the RMSE  and partitioning each species into subspecies:(1) for each combination of particles of  each species, we determine the set of particles(s1g,…,srg) with minimum RMSE.  For each species, we set si1=sig;(2) for sorting the particles in theith species, we calculate the RMSE produced by the combination (s1g,…,si-1g,siq,si+1g,…,srg) with q=2,…,Ps; then sorting the particles based on the increasing value of the corresponding RMSE. This step is repeated for all r species.After sorting each species, we can do a partition of them into subspecies; the first particle of a subspecies, that is, the particle of the subspecies with least RMSE, is called leader of the subspecies. The next steps are used for partitioning each ordered species in subspecies:(1) for theith species,  we set the number of subspecies  ni=1 and create the first subspecies by setting the leader of this subspecies as the first particles of the species,  pileader(ni)=sig;(2) then we consider the successive particles of the speciessiq with q=2,…,Ps and calculate the index distance between the particle siq and the leader of the first subspecies:
(16)ψ(pileader(ni),siq)=‖pileader(ni)-siq‖L,
where L=2n (resp., L=3n) for a TSK-fuzzy system of zero (resp., first) order. If we have ψ(pileader(ni),siq)<ψth, where ψth is a threshold value, then we assign  the particle siq to this subspecies; otherwise we create a new subspecies by setting ni=ni+1;(3) we iterate the steps (8) and (9) for all ther species.In the last steps, the PSO algorithm is applied; we define the particles in the same subspecies as neighbours of a particle. The best global position of the neighbours of a particlesiq, enclosed in the kth subspecies of the ith species at the iteration time (t-1), is given from the best position of the leader of the subspecies  pileader(k) until the iteration time (t-1). The best local position of the particle siq enclosed in the kth subspecies of the ith species at the iteration time (t-1) is given by the best position  piq of the particle until the iteration time (t-1).


## 3. Subzones in the Generation Process

Our method is an iterative process that determines the optimal partition in subzones of the area of study; each subzone represents a zone of the area of study, homogeneous with respect to a specific TSK-fuzzy system composed fromr fuzzy rules in the form (1). The expert creates an initial finer partition of the area of study according to specific local features (of type sociological, climatic, orographic, hydrological, etc.); the pattern data set is divided into subsets such that a subset is spatially included in the corresponding subzone. The successive step is performed to verify that the data distribution is consistent with the partition into subzones of the area of study; we verify that the number of patterns inside each subzone is greater or equal to a specific threshold value which can be set by the user. Clearly, the higher this value is, more the low resultant RMSE is expected; therefore, the greater the accuracy of the resulting TSK-fuzzy system will be. If Nh is the dimension of the subset of patterns inside the hth subzone and Nth is the threshold value, we impose the following constraint for each subzone:
(17)Nh≥Nth,h=1,…,Z,
where Z is the  cardinality of the partition such that N=∑h=1ZNh. We consider consistently the pattern dataset with the partition into subzones of the area of study if (17) is true; otherwise, the expert creates a more coarse-grained partition; this control is iterated until each subset of patterns is consistent with respect to the corresponding subzone. For each subzone, the  HCMSPSO method is applied for generating an optimal TSK-fuzzy system; we associate to each subzone the TSK-fuzzy system determined and its RMSE.We compare the TSK-fuzzy systems of adjacent subzones, calculating the similarity indexShk as in (8).  If Shk is greater or equal to a threshold value Sthreshold, the hth and kth subzones are merged. When two or more subzones are merged in a new subzone, we group the corresponding pattern subsets together into a single subset, and we restart the HCMSPSO algorithm for the new subzone. This process is iterated until we have that Shk<Sthreshold for all hth and kth adjacent subzones. As final result a thematic map is produced in which the area of study is divided into the final subzones classified according to the RMSE of the TSK-fuzzy system generated. To compare homogeneous errors, we calculate two normalized errors used in the literature:(i)
the normalized root mean square Error index (shortly, NRMSE) which is the rapport between the RMSE and the range (this last is given from the difference between maximal and the minimal values of the output variabley, in absolute value).  We define the NRMSE with the following percentage:
(18)NRMSE=RMSE|ymax⁡-ymin⁡|×100;(ii)
the coefficient of variation of the RMSE error (shortly, CVRMSE) which is the rapport between the RMSE and the mean valuey- of the output variable y. We define the CVRMSE with the following percentage:
(19)CVRMSE=RMSEy-×100.The NRMSE and CVRMSE are used in the creation of thematic maps of the TSK-fuzzy systems. The expert can fix a reliability threshold for the TSK-fuzzy system; in subzones with index greater than this threshold, it is necessary to use additional data and/or eliminate data with noise and outliers.  The process described above can be schematized  in the following steps:(1) the expert divides initially the area of study into Z subzones, partitioning the area in homogeneous zones; this partition represents the finer partition desired by the expert;(2) the pattern dataset is partitioned in subsets of data; each subset contains measured data georeferred into a specific subzone; if the dimension of each pattern subsets is less than a prefixed thresholdNth, the partition is too fine with respect to the pattern dataset and  the process return to step (1); in this case the expert must create a more coarse grained subzone partition of the area of study;(3) for each subzone, we use the HCMSPSO method to determine the number of rules and generate the correspondent species;(4) we use the HCMSPSO method to generate the subspecies  and optimize the parameters in each rule;(5) we compare the TSK-fuzzy system calculated to two adjacent subzoneszh and zk, by calculating the similarity index  Shk;  if Shk≥Sthreshold, where Sthreshold  is a predefined threshold, the two subzones, are merged in one subzone and the number of subzones is Z-1;(6) if there are two or more subzones merged, we iterate steps  (3), (4), and (5) for each new subzone;(7) two thematic maps are created by showing for each final subzone the reliability class correspondent to the final NRMSE and CVRMSE.In Figure1, we have schematized the above process. If we are interested to analyze whether the final distribution of the final subzones is or not approximately uniform, we can calculate the coefficient of variation of this distribution; this index is extracted by calculating the mean and standard deviation of the distribution of the Nh’s as
(20)mN=∑h=1ZNhZ,σN=∑h=1Z(Nh-mN)2Z-1.
The coefficient of variation, expressed in percentage, is given by
(21)CVN=σNmN×100.Figure 1
Schema of the subzones  generation process.We can consider the pattern data distribution approximately uniform ifCVN≤50%; this control can be used at the end of the process by the expert if he intends to verify if the final pattern dataset is approximately uniform with respect to the final partition of the area of study. This analysis is useful to see that significant differences in the RMSE on the area of study can be due to substantial changes in the cardinality of the final subsets of patterns inside each final subzone.  In Section 4, we present some results of our tests applied on spatial datasets. The HCMSPSO algorithm has been implemented and encapsulated in the tool GIS ESRI/ArcGIS, release 10. A first experiment is made on test spatial data firstly by comparing the results obtained with the HCMSPSO method and the ones obtained using other PSO-based methods, secondly for  verifying the accuracy of our method in the subzones merging process. Then, we present the results obtained by applying our method on a problematic related to the valuation of the costs for building maintenance in the city of Pompeii (Italy).


## 4. Results of Tests

Now, we apply our method to geospatial data. The test concerns the buildings of the  municipality of Pompeii, which is a famous touristic city for the presence of  an important Sanctuary and of a large famous archeological heritage. The municipal area is partitioned into four classes: rural area, urban center, inhabited nucleus, and industrial area.  An expert's goal is to plan the cost of maintenance of  buildings, based to the building maintenance data. The data are extracted from the related dataset, and they are the following:x1:year of construction, x2:year of last maintenance, x3:extent of the damage with respect to the volume of the building (0:null extension and 1:complete extension), x4:gravity of the damage (0:null gravity and 1:maximum gravity), y:cost of the maintenance (calculated in thousands of Euro). Each pattern corresponds to a building  georeferred to a specific census microzone. The initial subzones are formed by union of adjacent microzones with a same city planning  class, and we obtain Z=7 subzones. The thematic map in Figure 2 shows the seven subzones obtained by the subdivision of the area of Pompeii based on the four classes.Figure 2
Initial subzones of Pompeii based on the city planning class.The dataset is formed byN=3445 buildings (cf. Table 1); we set Nth=50. We have that Nh is greater than Nth=50 for every h=1,…,Z, we can assume that the set of data is suitable for the partition. Then we use this subdivision in 7 subzones of Pompeii for generating the relative TSK-fuzzy system of zero order. In the HCMSPSO  method, we set the threshold values μth and ψth to 0.03 and 2, respectively; the number of iterations is 200.000. The graph in Figure 3 shows the RMSE trend with respect to the iteration number obtained for the seven subzones. For all the seven TSK-fuzzy systems generated, the RMSE trend reaches a plateau after about 1.5×105 iterations. Table 2 shows the results, and we report the final number of rules, the RMSE, NRMSE, CVRMSE, and the index tp. The results show that the TSK-fuzzy systems related to the subzones 3 and 7 have RMSE and tp greater values with respect to the ones related to the other subzones. Then, we calculated the similarity indexes between adjacent subzones; we set Sthreshold=0.7.Table 1
Dimension of the pattern subsets included in each subzone.
Subzone
Class
Number of buildings
1
Industrial area
64
2
Industrial area
75
3
Rural area
1306
4
Inhabited nucleus
586
5
Inhabited nucleus
126
6
Urban center
192
7
Rural area
1160Table 2
Final number of rules and RMSE obtained for each TSK-fuzzy system.
Subzone
Number of rules
RMSE
NRMSE
CVRMSE
t
p
1
7
15.281
2.942%
5.736%
1.2 × 105
2
7
22.214
4.738%
8.175%
1.3 × 105
3
9
239.023
45.020%
83.677%
1.5 × 105
4
7
87.727
18.465%
32.460%
1.3 × 105
5
7
38.369
9.820%
14.518%
1.4 × 105
6
7
53.223
10.467%
18.835%
1.4 × 105
7
8
162.931
30.688%
57.169%
1.5 × 105Figure 3
RMSE trend obtained for the seven subzones.The similarity values between two TSK-fuzzy systems with same number of rules, associated with adjacent subzones are given in Table3. Table 4 contains breaks of the three thematic classes of NRMSE and CVRMSE: we consider not sufficiently reliable the results obtained in subzones belonging to the class “high,” that is, subzones with  NMRSE greater then 30% or CVRMSE  greater than 50%. The results in Figures 4 and 5 show that the resultant TSK-fuzzy system obtained for  the rural areas 1 and 7 are not sufficiently reliable. These subzones contain the greatest number of patterns; the results confirm that  the costs of maintenance of a building in rural areas are probably not significantly related to parameters like the last year of construction and maintenance.Table 3
Similarity index between adjacent subzones.
Subzone 1
Subzone 2
S
h
k
4
6
0.388
5
6
0.326
1
4
0.078
2
5
0.073Table 4
Breaks of the three thematic classes of NRMSE and CVRMSE.
Class
NRMSE class breaks
CVRMSE class breaks
Low
0%–10%
0%–20%
Mean
10,001%–30%
20,001%–50%
High
Over 30%
Over 50%Figure 4
Thematic map of NRMSE.Figure 5
Thematic map of CVRMSE.


## 5. Conclusions

In this paper, we present a method based on the HCMSPSO algorithm for extracting a TSK-fuzzy system from a dataset of georeferred measured data for spatial analysis. The area of study is partitioned initially into subzones by the expert; for each subzone is extracted the TSK-fuzzy system by using the subset of patterns georeferred into the subzone. We merge subzones with similar TSK-fuzzy system and by recreating the TSK-fuzzy system for the new subzone. For each TSK-fuzzy system, the reliability is evaluated using indexes based on the final RMSE. The algorithm has been implemented in the tool ESRI/ArcGIS, release 10; the results of our tests show that this method can be well used in a GIS platform and encapsulated as decision support system for optimizing fuzzy systems related to subzones of the area of study.



---

*Source: 808361-2012-08-15.xml*