# Hotspots Detection in Spatial Analysis via the Extended Gustafson-Kessel Algorithm

Authors: Ferdinando Di Martino; Salvatore Sessa
Journal: Advances in Fuzzy Systems
 (2013)

---

## Abstract

We show a new approach for detecting hotspots in spatial analysis based on the extended Gustafson-Kessel clustering method encapsulated in a Geographic Information System (GIS) tool. This algorithm gives (in the bidimensional case) ellipses as cluster prototypes to be considered as hotspots on the geographic map and we study their spatiotemporal evolution. The data consist of  georeferenced patterns corresponding to positions of Taliban’s attacks against civilians and soldiers in Afghanistan that happened during the period 2004–2010. We analyze the formation through time of new hotspots, the movement of the related centroids, the variation of the surface covered, the inclination angle, and the eccentricity of each hotspot.


---

## Body

## 1. Introduction

Hotspot detection is a known spatial clustering process in which it is necessary to detect spatial areas on which specific events thicken [1]; the patterns are the events georeferenced as points on the map; the features are the geographical coordinates (latitude and longitude) of any event. Hotspot detection is used in many disciplines, as in crime analysis [2–4], for analyzing where crimes occur with a certain frequency, in fire analysis [5] for studying the phenomenon of forest fires, and in disease analysis [6–9] for studying the localization and the focuses of diseases. Generally speaking, for detecting more accurately the geometrical shapes of hotspot areas algorithms based on density [10, 11] are used and they measure the spatial distribution of patterns on the area of study, but these algorithms have a high computational complexity.In [5, 12, 13] a new hotspot detection method based on the extended fuzzy C-means algorithm (EFCM) [14, 15] was proposed, which is a variation of the famous fuzzy C-means (FCM) algorithm that detects cluster prototypes as hyperspheres. With respect to the FCM algorithm, the EFCM algorithm has the advantages of determining recursively the optimal number of clusters and being robust in the presence of noise and outliers. In [5, 12, 13] the EFCM is encapsulated in a GIS tool for detecting hotspots as circles displayed on the map. The pattern event dataset is partitioned according to the time of the event’s detection, so each subset is corresponding to a specific time interval. The authors compare the hotspots obtained in two consecutive years by studying their intersection on the map. In this way it is possible to follow the evolution of a particular phenomenon studying how its incidence is shifting and spreading through time.In this paper we present a new hotspot detection method based on the extended Gustafson-Kessel algorithm (EGK) [14, 15] for studying the spatiotemporal evolution of hotspots. Our aim is to improve the shape of the hotspots, maintaining a good computational complexity: indeed the EGK algorithm gives the cluster prototypes as hyperellipsoids and ellipses in the bidimensional case. The EGK algorithm is an extension of the Gustafson-Kessel (GK) algorithm [16] which we briefly present.LetX={x1,…,xN}⊂Rn be a dataset composed of N patterns xj=(x1j,x2j,…,xnj)T, where xkj is the kth component (feature) of the pattern xj. The GK algorithm minimizes the following objective function:
(1)J(X,U,V)=∑i=1C∑j=1Nuijmdij2,
where C is the number of clusters fixed a priori, uij is the membership degree of the pattern xj to the ith cluster (i=1,…,C), V={v1,…,vC}⊂Rn is the set of points given by the centroids of the C clusters, m is the fuzzifier parameter, and dij is the distance between vi=(v1i,v2i,…,vnj)T and xj. The general form of this distance is given by
(2)dij=(xj-vi)TAi(xj-vj),
where Ai is the norm matrix, defined to be symmetric and positive. In the FCM algorithm Ai is equal to the identity matrix I. In the GK algorithm the following Mahalanobis distance [17] is used:
(3)dij=(xj-vi)TPi-1(xj-vj),
where Pi is the covariance matrix of the ith cluster given by
(4)Pi=∑j=1Nuijm(xj-vi)(xj-vi)T∑j=1Nuijm.The covariance matrixPi provides information about the shape and orientation of the cluster. The length of the kth axis of the hyperellipsoid is given by the root square of the kth eigenvalue λik of Pi. The directions of the axes of the hyperellipsoid are given by the directions of the eigenvectors of the matrix Pi. In Figure 1 we show an example of ellipsoidal cluster prototype.Figure 1
Example of ellipses cluster prototype using the GK algorithm.Using the Lagrange multipliers for minimizing objective function (1), we obtain the following solution for the centroids of each cluster prototype:
(5)vi=∑j=1Nuijmxj∑j=1Nuijm,
where i=1,…,C and uij are given by:
(6)uij=1(∑h=1c(dij2/dhj2))2/(m-1).Initially theuij’s and the vi are assigned randomly and updated in each iteration. If U(l)=(uij(l)) is the matrix Ucalculated at the lth step, the iterative process stops when
(7)∥U(l)-U(l-1)∥=maxi,j|uij(l)-uij(l-1)|<ε,
where ε>0 is a prefixed parameter.This algorithm is sensitive to the presence of outliers and noise and the number of clusterC is fixed a priori; as in the FCM algorithm, we need to use a validity index for determining an optimal value for the number of clusters C. In order to overcome these shortcomings, in [1, 16] the EGK algorithm is proposed which is a variation of the GK algorithm: there the optimal number of clusters is obtained during the iteration process. Furthermore, the EGK algorithm is robust with respect to the presence of noise and outliers.In this paper we propose a new approach based on the EGK clustering method for detecting hotspots and studying their spatiotemporal evolution. Taking into consideration the bidimensional case, we obtain ellipses to be approximated as hotspot area better than the circular areas produced in the EFCM method.Figure2 shows an example of two intersecting elliptical hotspots, obtained as clusters detected by means of EGK method in two consecutive periods.Figure 2
Intersection of two elliptical hotspots detected for events that happened in two consecutive periods.Figure2 show three different regions:(i)
the area in which the hotspotA is not intersected by the hotspot B (corresponding to A-(A∩B)=A-B): this region can be considered as a set of geographical areas in which the prematurely detected event disappears successively;(ii)
the area of intersectionA∩B: this area can be considered a geographical area in which the event persists in the course of time;(iii)
the area in which the hotspotB is not intersected by the hotspot A (corresponding to B-(A∩B)=B-A): this region can be considered as a set of geographical areas in which the prematurely not detected event propagates successively.We can study the spatiotemporal evolution of the hotspots by analyzing the interactions between elliptical hotspots detected for consecutive periods, by verifying the presence of clusters in areas in which clusters have not yet been detected previously and the disappearance of clusters in areas previously covered by hotspots.In this research we present a method for studing the spatiotemporal evolution of hotspots areas of war in Afghanistan; we apply the EGK algorithm for comparing consecutive years’ event datasets corresponding to positions of Taliban’s attacks against civilian and soldiers. Each event corresponds to the geolocalization of the site where Taliban’s attack happened as well.We study the spatiotemporal evolution of the hotspots by analyzing the intersections of hotspots corresponding to two consecutive years, the displacement of the centroids, the increase or reduction of the hotspots areas, and the emergence of new hotspots.In Section2 we give an overview of the EGK algorithm. In Section 3 we present our method for studying the spatiotemporal evolution of hotspots in spatial analysis. In Section 4 we present the results of the spatiotemporal evolution of hotspots. Our conclusions are contained in Section 5.


## 2. The EGK Algorithm

In the EGK algorithm we consider clustering prototypes given by hyperellipsoids in then-dimensional feature’s space. The ith hyperellipsoidal cluster prototype Vi is characterized by a centroid vi=(v1i,…,vni) and a mean radius ri and we say that xj belongs to Vi if dij≤ri.The radiusri is obtained considering the covariance matrix Pi of the ith cluster, defined by (4), whose determinant gives the volume of the ith cluster. Since Pi is symmetric and positive, it can be decomposed in the form
(8)Pi=QiΛiQiT,
where Qi is an orthonormal matrix and λi=(λij) is a diagonal matrix. The mean radius ri is given as [15]
(9)ri=1n∏k=1nλik1/n=(det(Pi))1/n.In the EGK algorithm the objective function to be minimized is(10)J(X,U,V)=∑i=1C∑j=1Nuijm(dij2-ri2),
where dij is given by the Mahalanobis distance (3). The solutions obtained for the centroids vi are given by formula (5) and the functions uij are obtained by
(11)uij=1∑h=1C(dij2wij/dhj2whj)1/(m-1),
where wkj=max(0,1-(rk2/dkj2)) for k=1,…,C. By setting dkj2wkj=max(0,dkj2-rk2) and φj=card{k∈{1,…,C}:dkj2≤rk2} for any j=1,…,N, we have that formula (11) holds if φj=0, while if φj>0, one defines uij in the following way:
(12)uij={0ifdij2wij>01φjifdij2wij=0.Formula (12) produces the negative effect of diminishing the objective function (10) when a meaningful number of features are placed in a cluster; this effect can prevent the separation of the clusters. In order to solve this problem in [15], one starts with a small value ri and by setting gradually ri:=ri+β(i)/C(i), where C(i) is the number of clusters at the ith iteration and β(i) is defined recursively as β(0)=1,β(i)=min(C(i-1),β(i-1)) (C(0) is the initial number of clusters). By setting
(13)Iik=∑j=1Nmin(uij,ukj)∑j=1Nuij,
one defines the symmetric matrix S=(Sik), where Sik=max{Iik,Iki}. If S(l) is the matrix S at the lth iteration (l>1) and the threshold α(l)=1/(C(l)-1) is introduced, two indexes i* and k* are determined such that Si*k*(l)=max{Sik(l):i=1,…,N;k=1,…,C}≥α(l). Then these indices are merged by setting, for any j=1,…,N,
(14)ui*j(l)≔ui*j(l)+uk*j(l),C(l):=C(l-1)+1;
thus, the k*th row can be removed from the matrix U(l). In conclusion the following steps hold for the EGK algorithm.(1)
The user assigns initiallyC(0), m>0 (usually m=2), ε>0, Sik(0)=0, and β(0)=1.(2)
uij(0)are fixed randomly.(3)
vi and ri are calculated with formulae (5) and (9), respectively.(4)
uij are calculated with formulae (11) and (12).(5)
Determinei* and k* such that Si*k*(l)=max{Sik(l):i=1,…,N;k=1,…,C}.(6)
IfSi*k*(l)>α(l), then the i*th and k*th clusters are merged via formula (14) and the k*th row is deleted from U(l).(7)
If formula (7) is satisfied, then the process stops otherwise go to (3) for the (l+1)th iteration.


## 3. Hotspots Detection and Evolution in Military War

Each pattern is given by the event corresponding to a place in which an attack has occurred. The two features of the pattern are the geographic coordinates of this place.We divide the event dataset into subsets corresponding to the events that occurred in a specific year or set of years. For each subset of events we apply the EGK algorithm to detect the final cluster prototypes.The dataset is extracted from the URLhttp://www.acleddata.com/data/asia/; the data are the geolocalizations of Taliban’s attacks in Afghanistan during the period 2004–2010. The EGK algorithm is encapsulated in the ESRI/ArcGIS tool. Figure 3 shows the mask used for setting the parameters and running the EGK algorithm.Figure 3
Mask created in the ESRI/ArcGIS tool for managing the EGK process.We can set other numerical fields for adding other features to the geographical coordinates. Initially we set the initial number of clusters, the fuzzifierm (equal to 2 by default), and the error threshold for stopping the iterations (equal to 0.01 by default). At the end of the process we displayed on the form of the number of iterations, the final number of clusters, and the error calculated at the last iteration. The resultant clusters are shown as ellipses on the geographical map and can be saved in a new geographical layer.In Figure4 we show the mask used for displaying the information of each elliptical prototype detected: centroid’s coordinates, length of each semiaxis, and orientation of the ellipses with respect to the horizontal plane on the geographical map.Figure 4
Mask created in the ESRI/ArcGIS tool for displaying the information of the detected cluster prototypes.The final process concerns the comparative analysis of the hotspots obtained by the final clusters resulting for each subset of events. Figure5 shows an example of the display of hotspots obtained as final clusters corresponding to three consecutive years.Figure 5
Spatiotemporal evolution of hotspots detected in three consecutive years.In order to assess the expansion and the displacement of any hotspot, we measure the area covered by each hotspot, the distance between the centroids of two intersecting hotspots detected in consecutive periods, the variation of the inclination angle, the eccentricity, and the length of both semiaxis.


## 4. Test Results

After partitioning the dataset in the five periods 2004–2006, 2007, 2008, 2009, and 2010, respectively, we apply the EGK algorithm for detecting the sequences of elliptical cluster prototypes. We fixm=2, C(0)=15, and ε=1×10-2. Table 1 shows the results obtained for each period.Table 1
Results of the EGK applied to the event’s subsets.
Year
Initial number of clusters
Final number of clusters
|
U
(
l
)
-
U
(
l
-
1
)
|
ε
2004–2006
15
7
0.79
×
10
-
2
1
×
10
-
2
2007
15
7
0.65
×
10
-
2
1
×
10
-
2
2008
15
7
0.68
×
10
-
2
1
×
10
-
2
2009
15
8
0.74
×
10
-
2
1
×
10
-
2
2010
15
8
0.81
×
10
-
2
1
×
10
-
2We present the details relating to the comparison of the hotspots by considering the event data that occurred in the five periods. In Figures6, 7, 8, 9, and 10 we show the hotspots detected.Figure 6
Taliban’s attack events: years 2004–2006.Figure 7
Taliban’s attack events: year 2007.Figure 8
Taliban’s attack events: year 2008.Figure 9
Taliban’s attack events: year 2009.Figure 10
Taliban’s attack events: year 2010.By analyzing Figures6–8 we can deduce that in the period 2004–2008 seven hotspot areas approximated as ellipses are present; in these periods each hotspot modified only slightly its angle, width, and position of the centroid. In the years 2009 and 2010 a new hotspot is detected in a region neighboring with Turkmenistan. In Figure 10 the hotspots obtained for two consecutive years 2009 and 2010 are overlapped as well. In blue (resp., red) we enumerate the hotspots corresponding to the year 2009 (resp., 2010); see Figure 11. The hotspots are labeled, and the hotspot number 8 is the new hotspot detected and coming from overlap of the related hotspots.Figure 11
Hotspots detected for two consecutive periods: 2009 (blue) and 2010 (red).In Table2 the first column shows the labels of each hotspot; the second and third columns show the area, in km2, of the hotspot detected in 2009 and 2010, respectively. The fourth column (resp., fifth) shows the intersection area of the two hotspots (resp., the percentage of area of the hotspot detected in 2009 covered by the corresponding hotspot detected in 2010, that is, the ratio “intersection area/area hotspot detected in 2009”).Table 2
Areas of hotspots detected in 2009 and 2010.
Hotspot ID
Areahotspot 2009
Areahotspot 2010
Intersection area
% of Intersection area
1
18804.11
18856.72
14936.25
79.43%
2
13580.19
13583.15
10632.51
78.29%
3
1516.89
1538.23
1011.87
66.71%
4
7889.86
6665.24
5174.83
65.59%
5
4987.08
6086.51
3706.52
74.32%
6
6361.20
5691.76
4490.73
70.60%
7
5761.71
7866.39
5175.92
89.83%
8
18460.84
23471.45
16255.32
88.05%The results in Table2 show that over 65% of the area of each hotspot detected in 2009 is also covered by the corresponding hotspot detected in 2010. Another significant result is the increase of the area of the hotspot 8, which exceeds 2 × 104 km2 in 2010. In Table 3 we show the eccentricity of each hotspot and the distance between the centroids of each hotspot detected in 2009 and the corresponding one detected in 2010.Table 3
Eccentricity and centroid’s distance between the hotspots detected in 2009 and 2010.
Hotspot ID
Eccentricity hotspot 2009
Eccentricity hotspot 2010
Centroids distance (km)
1
0.796
0.786
16.52
2
0.947
0.949
17.86
3
0.897
0.906
23.30
4
0.672
0.899
42.08
5
0.564
0.381
21.55
6
0.591
0.701
23.60
7
0.536
0.699
25.66
8
0.669
0.693
33.87The results show that the eccentricity increases significantly in 2010 for hotspots 4 and 6, whereas it decreases for hotspot 3; the eccentricity remains almost unchanged for the remaining hotspots in 2010. Another significant result is the distance exceeding 40 km between the centroid of hotspot 4 detected in 2009 and the centroid of the corresponding hotspot detected in 2010.


## 5. Conclusions

We present a new approach for detecting hotspots in spatial analysis using the EGK clustering method encapsulated in a GIS tool. Similar to the EFCM algorithm, the EGK method is robust with respect to noise and outliers and we obtain the optimal number of the clusters iteratively during the process; furthermore, it has the advantage to detect hotspots of elongated shape. In our experiments we consider the site of Taliban’s attacks in Afghanistan during the period 2004–2010. The spatial dataset is partitioned into subsets in order to study the evolution of the hotspots through time. We study the evolution of each hotspot in terms of movement of the centroids, surface covered, inclination, and eccentricity. The results show the formation, starting from 2009, of a new hotspot in the north-western zone neighboring with Turkmenistan. The results of the comparison of the hotspots detected in 2009 and 2010 show that this hotspot is increased with an extension of (about) 2 × 104 km2.



---

*Source: 876073-2013-12-09.xml*