# Similarity Measures for Spatial Clustering

Leila Hamdad, Karima Benatchba, Soraya Ifrez, Yasmine Mohguen

► To cite this version:

Leila Hamdad, Karima Benatchba, Soraya Ifrez, Yasmine Mohguen. Similarity Measures for Spatial Clustering. 6th IFIP International Conference on Computational Intelligence and Its Applications (CIIA), May 2018, Oran, Algeria. pp.25-36, 10.1007/978-3-319-89743-1_3 . hal-01913922

HAL Id: hal-01913922

https://inria.hal.science/hal-01913922v1

Submitted on 7 Nov 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Similarity measures for spatial clustering.

Leila Hamdad*, Karima Benatchba, Soraya Ifrez, and Yasmine Mohguen

Ecole nationale Supérieure en Informatique ESI, BP 68M,16309, Oued-Smar, Alger,
Algerie, http://www.esi.dz.

**Abstract.** The spatial data mining (SDM) is a process that extracts knowledge from large volumes of spatial data. It takes into account the spatial relationships between the data. To integrate these relations in the mining process, SDM uses two main approaches: Static approach that integrates spatial relationships in a preprocessing phase, and dynamic approach that takes into consideration the spatial relationship during the process. In this work, we are interested in this last approach. Our proposition consists on taking into consideration the spatial component in the similarity measure. We propose two similarity measures; $d_{D_{yn1}}$, $d_{D_{yn2}}$. We will use those distances on the main task of SDM, spatial clustering, particularly on K-means algorithm. Moreover, a comparaison between these two approaches and other methods of clustering will be given. The tests are conducted on Boston dataset with 590 objects.

**Keywords:** Spatial Data mining, Dynamic approach, Similarity, Pre-processing approach, clustering, K-means, DBSCAN.

# 1 Introduction

These last decades have seen an explosion in the volume of spatial data. This is due to the various technological advances and the development of automatic data acquisition tools (GPS, satellite images,...). The wide use of these data has given rise to spatial data mining (SDM). It is a process that allows extracting knowledge and useful patterns from large volumes of spatial datasets ([15], [11]). Spatial data consist of two types of components; a descriptive component containing data of usual type: integer, real, boolean,...describing some features of the data and geometric component which describes the spatial localization of the data. The SDM is more difficult than classical data mining as it handles geo-spatial data characterized by autocorrelation. In SDM, spatial component can be taken into account according to three different approaches. The first one is basic and considers all attributes in the same way (spatial and non-spatial) and uses the techniques of classical data mining. As a result, the auto-correlation between objects is not taken into consideration. In fact, several studies have shown that this process produces inconsistent results, [14], [19]. The second approach

* Please note that the LNCS Editorial assumes the western naming convention, with given names the structure of the names in the running heads and the author index.
(static), likewise, uses classical DM techniques to process geo-spatial data. How-
ever, a preliminary data preprocessing is required. It consists of extracting and
representing the geo-spatial relationship between entities, in an explicit manner
([4], [17]). This approach has many drawbacks. First of all, it is time consuming
as the preprocessing of the data takes time. Indeed, extraction may require a lot
of computation time when many relationships must be considered. Second, the
preprocessed and the original data have to be stored leading to a redundancy in
storage. Moreover, if the original data is modified, the pre-processing has to be
executed again. To overcome these drawbacks, the dynamic approach emerged.
It consists on taking into consideration the geo-spatial component during the
data-mining process. Our proposal lies in this last approach, as, in the litera-
ture, spatial dynamic processing is not explicitly defined (see [12]). Our approach
consists on taking into consideration the spatial component in the similarity mea-
sure. We will be interested, in this work, in the main task of SDM, clustering.
Formally, it consists on partitioning a set S of N objects, $S = \{O_1, O_2, ..., O_N\}$,
based on a similarity metric, into a number of clusters ($C_1, C_2, ..., C_K$), such
as: $C_i \neq \emptyset$ for $i = 1, ..., K$, $C_i \cap C_j = \emptyset$ for $1, ..., k$ and $j = 1, ..., K$, $i \neq j$,
$S = \cup_{i=1}^k C_i$. Objects of a cluster must be as similar as possible, while objects
of different clusters must be as dissimilar as possible. It is an important task as
it enables to show interesting objects grouping without a priori knowledge.

The objective of this paper is to propose two similarity distances that take
into consideration the spatial component during the clustering process. To show
the effectiveness of this proposal, we used these distances in K-means, a simple
partitioning method yet efficient and widely used. We compared the obtained
results to the first approach which we called static using K-means. Then we
compare the three versions of K-means to density based clustering method DB-
SCAN [8] and CAH an ascending hierarchical clustering method.

This paper is organized as follows: In section 2, we will introduce the static approach. Then in section 3, we will present the similarity distances to be used for dynamic clustering. In section 4, we present some clustering algorithms. Finally in section 5, tests and results on the different approaches will be presented.

## 2 Static approach

This approach allows taking advantage of traditional data mining methods to
process spatial data. There are different types of spatial relationships: metric,
topological and directional. In this paper, we deal with metric relations as the
data considered are represented by points. The data preprocessing begins by
extracting the metric relationships between the data. These relationships are
then used to modify the attributes of data. There exist in the literature several
methods to extract it. Moran (1948) [16] and Geary (1954) [9] were the first to
propose a measure for spatial interaction. Since then, several measures have been
proposed [3]. Most of them require a threshold as parameter (obtained from the
objects distance matrix) [13]. We have chosen to use the K nearest neighbors
(KNN) as it is a simple non parametric method (does not need a threshold);
moreover, it is the most used method ([13]). KNN processes as follows: For a given object $O_i$ of the dataset, KNN searches among all objects of the data set, the K-nearest neighbors of $O_i$ according to a distance such as the geometric distance. The neighbor relations obtained by applying KNN on the original dataset are used to obtain neighborhood matrix. The last step of the static approach consists on building the new dataset (smoothing matrix) from the original one. In fact, each attribute value of an object is replaced by the mean of its neighbors attribute. The algorithm is given below:

Smoothing Matrix algorithm For each object $O_i$ of S, $i = 1, N$ :

1 Compute K-nearest- neighbors of $O_i$ with KNN algorithm.

2 For each attribute of $O_i$, compute the mean of the attributes of $O_i$ and its corresponding neighbors attribute.

3 Create a new object $O'_i$ which attributes values are the one computed in (2).

4 Insert $O'_i$ in S where S is the new dataset.

## 3 Similarity distances for a dynamic approach

This approach, unlike the previous one, proposes dynamic spatial data processing. Its goal is to take into account the spatial component in the process of DM and not through a preprocessing. However, in the literature very little work is available on this approach [12]. This might be due to the fact that this research area is relatively young [17]. One of the goals of this paper is to take into consideration the spatial component, in a similarity distance. We propose two distances $d_{Dyn1}$ and $d_{Dyn2}$. Both compute the similarity between spatial objects by considering the non-spatial attributes and spatial attributes simultaneously. They are based on two distances: Euclidean distance that measures the similarity between the non-spatial attributes and geographic distance that measures the metric relationship. The first one, $d_{Dyn1}$ is formally defined as the product of the Euclidean distance between the non-spatial attributes and geographic distance between the spatial attributes:

$$d_{Dyn1}(O_i, O_k) = d_{euclidian}(O_i, O_k) * d_{geo}(O_i, O_k).$$

Where

$$d_{euclidian}(O_i, O_k) = \sqrt{\sum_{j=1}^{m} (O_i - O_k)^2}$$

and

$$d_{geo}(O_i, O_k) = 6371 * A\cos[C\cos(lat1) * C\cos(lat2) * C\cos(long2 - long1) + S\sin(lat1) * S\sin(lat2)].$$

Where (lat1, long1) and (lat2, long2) are the spatial coordinates of respectively points $O_i$ and $O_k$. In the second proposed distance $d_{Dyn2}$, weights are assigned
to the two types of attributes (spatial and non-spatial). The formula of $d_{Dyn2}$ is given below:

$$d_{Dyn2}(O_i, O_k) = \alpha d_{euclidian}(O_i, O_k) + \beta d_{geo}(O_i, O_k).$$

where $\alpha$ and $\beta$ are respectively weights of Euclidian and geographic distance and verify that $\alpha + \beta = 1$. When $\alpha = 1(\beta = 0)$, clustering is done on descriptive attributes only. The spatial attributes are ignored. On the contrary, when $\alpha = 0(\beta = 1)$, only spatial attributes are considered and we obtain a regionalization.

# 4 Clustering algorithms

Many methods dedicated to the clustering exist in the literature. They fall into two main classes: partitioning methods and hierarchical methods. They differ in the way they build clusters. While the second gradually build those clusters, the first discover them by moving objects between clusters [11]. In addition to these two fundamental approaches, other methods exist such as density and grid based methods. They use different mechanisms for data organization and processing, and for building the clusters [1].

## 4.1 Partitioning Methods

They seek to find the best $k$ partitions for a set of $n$ objects (data), while optimizing an objective function. This function aims to maximize the similarity between objects of the same cluster and to minimize the similarity between objects of different clusters. These methods improve iteratively clusters by moving objects between clusters. There exist several partitioning methods among which K-means, the first clustering method. K-means is by far the most popular clustering algorithm and widely used in scientific and industrial applications [5]. Its popularity is due to the fact that it is simple to implement and converges rapidly. However, it has some drawbacks. It is influenced by outliers and the obtained clustering depends on the initial one.

## 4.2 Hierarchical methods

These clustering methods build hierarchical clusters gradually. They can be of two types ascending hierarchical clustering methods and descending ones. Hierarchical methods have many advantages such as flexibility regarding the level of granularity one wants to have. However they present some drawbacks such as the difficulty of setting a stopping criterion and their high execution time [6]. In what follows, we present, CAH, an ascending hierarchical clustering method. CAH builds a hierarchy of clusters assuming that initially each object is a cluster. Then the most similar clusters are aggregated. The aggregation is repeated until having a single cluster containing all objects.
## 4.3 Density based methods

These methods characterize classes as homogeneous high density regions, separated by regions of low density. Unlike partitioning methods, methods based on density are able to discover classes of concave forms and do not take into account outliers as they are removed during the process. There are two approaches for this type of methods. The first approach is based on the density connectivity. It takes two input parameters, the neighborhood radius *Eps* which represents the maximum distance between points and the density threshold *MinPts* which represents the minimum number of points in the neighborhood. The best known algorithms are DBSCAN and GDBSCA-N [2]. The second approach is based on sound mathematical principles and uses a density function in its process. The best known algorithm is DENCLUE [10].

# 5 Tests and results

In this section, we will give a summary of the different tests performed. We will start by presenting the result of k-means using the two proposed distances $d_{Dyn1}$ and $d_{Dyn2}$, respectively named $K-means_{d_{Dyn1}}$ and $K-means_{d_{Dyn2}}$. K-means with preprocessing using KNN is called $K-means_{static}$. Then we will compare those results to DBSCAN and CAH algorithms. These tests were executed on an un-supervised spatial benchmark Boston <fnref n="1" />, represented in Figure 1. Benchmark

<figure><img src="image_2.png" /><figcaption>Fig. 1. Representation of benchmark Boston.</figcaption></figure>

Boston contains 506 objects and represents Boston housing and neighborhood

<footnote n="1">¹ https://geodacenter.asu.edu</footnote>
data. Each object is represented by 18 non spatial features and longitude and latitude (spatial attributes). The different features describe the type of area of the different housing such as: hot district characterized by high criminality level, rich district, poor one... One can notice that this benchmark is very dense.

## 5.1 Dynamic vs Static K-means

To compare the dynamic versions of K-means (K-means$_{d_{Dyn1}}$ and K-means$_{d_{Dyn2}}$) to the static one we conducted several tests. For all the tested version of K-means, the number of iterations was set to 100. As this benchmark is unsupervised one, and to compare the results of the three versions of k-means, we executed classical k-means ($k = 3$) on the non spatial attributes of the benchmark to better visualize the objects distribution and their meaning. Moreover, we executed K-means$_{d_{Dyn2}}$ on spatial attributes($\alpha = 0$), obtaining a regionalization. The results of both executions are given in the following Figures. In Figure 2, the blue color

<figure><img src="image_3.png" /><figcaption>Fig. 2. Regionalization.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Classical K-means.</figcaption></figure>

represents north districts, the yellow one the center, and the red one south districts. In Figure 3, the blue color represents the wealthy neighborhood, the yellow one the middle class neighborhood and the red color the poor neighborhood.

## 5.2 Comparison of $K-means_{static}$, $K-means_{d_{Dyn1}}$ and $K-means_{d_{Dyn2}}$

Figures 4, 5, 6 and 7 show the results of visualization of K-means$_{static}$ (with the number of neighbors for KNN being to 2 and 4), K-means$_{d_{Dyn1}}$ and K-means$_{d_{Dyn2}}$.
means<sub>dD<sub>yn2</sub></sub> (α = β = 0.5). For these tests, the number of classes for K-means was set to 3.

If we take a closer look at Figures 4 and 5, we can see the influence of the KNN parameter on the clustering. For a *number of neighbors* = 2, a certain number of objects (the ones between the red class and the yellow one) are considered belonging to the cluster poor neighborhood. While when more neighbors are taken into consideration when building the smoothing matrix, this number decreases. One notes that some objects classified in the blue cluster in Figure 4 are classified in the red cluster in Figure 5.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Static K-means with number of neighbors=2.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Static K-means with number of neighbors=4.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** K-means Dyn1.</figcaption></figure>

If we compare the results of classical K-means and those of K-means<sub>static</sub>
(Figure 5), we notice that the two classifications can be considered as close. We
do not see a clear impact of the spatial attributes on the clustering. One no-
tices that the boundaries between classes are clearly defined for K-means<sub>dD<sub>yn1</sub></sub>
<figure><img src="image_8.png" /><figcaption>**Fig. 7.** K-means Dyn2 ($\alpha = \beta = 0.5$).</figcaption></figure>

(Figure 6) when compared to K-means<sub>static</sub> (Figures 4 and 7). Classes do not overlap as for K-means<sub>static</sub>. This may be due to the distance used which gives the same importance to both types of attributes. K-means<sub>d<sub>Dyn2</sub></sub> gives a different partitioning of the objects. A close look at Figure 7 shows that two classes of K-means<sub>d<sub>Dyn1</sub></sub> (the poor neighborhood in red and the middle class neighborhood in yellow, Figure 6) are merged to form the poor neighborhood (in red). While the rich neighborhood of Figure 6 is split into two clusters: yellow one for middle class neighborhood and blue one for rich neighborhood. To try to explain this, we executed the K-means<sub>static</sub> with 4 neighbors for KNN, setting the number of classes to 5. We obtained the following results (Figure 8): The obtained

<figure><img src="image_9.png" /><figcaption>**Fig. 8.** Results visualization of K-means static (with 4 neighbors and K=5).</figcaption></figure>

classes of this execution are described as follows: The pink cluster represents the rich neighborhood, the green one the middle class one, the yellow one the residential area, the blue the economical one and the red one the poor neighborhood. Given this type of information, we can conclude that the clustering of K-means<sub>d<sub>Dyn2</sub></sub> is interesting as it merged the economical and poor neighborhood, found by K-means<sub>static</sub> and K-means<sub>d<sub>Dyn1</sub></sub>, into one class (Red one in Figure 7). It also, separated the rich class found by K-means<sub>static</sub> and K-means<sub>d<sub>Dyn1</sub></sub> into two classes: Middle class and rich neighborhood. Now, if we compare the different approaches according to the intra cluster inertia and execution time (Figures
9 and 10), we note that as the number of classes increases, the inertia decreases. This is due to the fact that as the size of clusters decreases, clusters will have more similar objects. For 3 clusters, the best inertia is given by $K-means_{static}$ with 2 neighbors, followed by $K-means_{D_{Dyn2}}$. However, the dynamic version of $K-means$ is faster than the preprocessing $k-means$ ($K-means_{static}$). That was the goal of using dynamic $K-means$.

<figure><img src="image_10.png" /><figcaption>Fig. 9. Intra cluster inertia of the different $k$-means versions when varying $k$.</figcaption></figure>

## 5.3 Dynamic K-means VS DBSCAN and CAH

In this section, we will compare $K-means_{D_{Dyn1}}$ and $K-means_{D_{Dyn1}}$ to DBSCAN and CAH. Figures 11, 12, 13 and 14 display the results of respectively $K-means_{D_{Dyn1}}$, $K-means_{D_{Dyn2}}$, DBSCAN and CAH.

We can notice from these Figures, that the four methods give different clustering. DBSCAN (Figure 13) give more compact classes. One cluster (rich neighborhood in blue) is bigger, in terms of size than the other two. $K-means_{D_{Dyn2}}$ divide this class into two (rich and middle class neighborhood). CAH (Figure 14) does the same; however, its rich neighborhood is smaller and is located south. Both $K-means_{D_{Dyn2}}$ and CAH define the same poor neighborhood.

If we compare the intra cluster inertia of DBSCAN, CAH and $K-means_{D_{Dyn2}}$ (see Figure 15), we notice that, DBSCAN has the best followed by $K-means_{D_{Dyn2}}$ and CAH. However, for this method, objects that are distant or isolated are considered noises and are not assigned to clusters. In Figure 13, these points are in black and represent 3.4% of the size of the benchmark. While the execution
<figure><img src="image_11.png" /><figcaption>**Fig. 10.** Execution time of the different versions of K-means when varying K.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>**Fig. 11.** K-means$_{d_{Dy,n1}}$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>**Fig. 12.** K-means$_{d_{Dy,n2}}$ ($\alpha = \beta = 0.5$).</figcaption></figure>

time of DBSCAN and K-means$_{d_{Dy,n2}}$ somehow similar, CAH takes much more
time (Figure 15).

# 6 CONCLUSIONS

We focused, in our work, on the main descriptive task of SDM, spatial clustering.
The main goal of our study was to compare two spatial clustering approaches
namely: the spatial data preprocessing approach (static) and dynamic approach.
<figure><img src="image_14.png" /><figcaption>Fig. 13. DBSCAN ($Eps = 100$ et $MinPts = 5$).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 14. CAH ($\alpha = \beta = 0.5$).</figcaption></figure>

For the second approach, we proposed to take into consideration the spatial component in the similarity measure. We proposed two distances, $d_{Dyn1}$ and $d_{Dyn2}$. The various tests performed on the benchmark Boston, showed that the approach proposed ($K-means_{d_{Dyn1}}$, $K-means_{d_{Dyn2}}$) gives better results than the preprocessing approach in terms of execution time. This was the main goal as the preprocessing approach takes too much time. The results obtained with $K-means_{d_{Dyn1}}$ seems similar to those of the preprocessing approach but with more precise boundaries. This is due to the fact that $K-means_{d_{Dyn1}}$ takes into consideration both spatial and non spatial attributes. $K-means_{d_{Dyn2}}$ is more efficient in terms of intra-class inertia, it makes a good description in terms of regionalization and characterization of these obtained regions.

<figure><img src="image_16.png" /><figcaption>Fig. 15. Comparison between DBSCAN, CAH and $K-means_{d_{Dyn2}}$.</figcaption></figure>
References

1. P. Andritsos. Data Clustering Techniques, Tech. Report CSRG-443, University of Toronto, 2002.

2. M. Ankerst, M. Breunig, H. Kriegel et J. Sander. "OPTICS: Ordering Points to Identify the Clustering Structure", *ACM SIGMOD, international conference on Management of data*, 1999.

3. L. Anselin, "Spatial Econometrics: Methods and Models", Springer, 1988.

4. V. Bogorny, E. Martins, and L.O. Alvares. A Reuse-based Spatial Data Preparation Framework for Data Mining, *In Proceedings of the 17th International Conference on Software Engineering and Knowledge Engineering*. pp. 649-652, 2005

5. M. Boubou. "Contribution aux méthodes de classification non supervisée via des approches prtopologiques et d'aggrégation d'opinions", *Thèse de doctorat, Université Claude Bernard - Lyon I*. 2007.

6. G. Cleuziou. "Une méthode de classification non-supervisée pour l'apprentissage dergles et la recherche d'information", *Thèse de doctorat, Université d'Orlans, 2004*.

7. M. Ester, H.P. Kriegel, and J.Sande r. Spatial data mining: A database approach. *A. School and A. Voisard, eds., Advances in Spatial Databases, 5th Int. Symp., SDD-97, 4766, Berlin, Germany, 1997.*

8. M. Ester, H. P. Kriegel, J. Sander. "Knowledge Discovery in Spatial Databases", Institute for Computer Science, University of Munich, Invited Paper at 23rd German Conf. on Artificial Intelligence (KI 99), Bonn, Germany, 1999.

9. R.C. Geary. "The contiguity ratio and statistical mapping". *The Incorporated Statistician*, **5** (3), P 115-145, 1954.

10. J. Han et M.Kamber. "Data mining : Concepts and techniques", Elsevier Inc, 2006.

11. A. K. Jain, M. N. Murty, P. J. Flynn. "Data Clustering: A Review", *ACM Computing Surveys*, Vol. 31, No.3, September 1999.

12. W. Klosgen, J. M. Zytkow. "Knowledge discovery in Databases: The purpose, necessity, and challenges". *Handbook of Data Mining and Knowledge Discovery*. Oxford University Press, Inc. L. Y, 2002.

13. L. Lebart, "Contiguity Analysis and Classification", *Data Analysis Studies in Classification, Data Analysis, and Knowledge Organization 2000*, pp 233-243.

14. D. J. Maguire, An overview and definition of GIS, in *Geographic Information Systems: Principles and Applications, 1st ed.*, vol. 1, 2 vols., pp. 920, 1991.

15. J. Mennis, D. Guo. Spatial data mining and geographic knowledge discoveryAn introduction, *Computers, Environment and Urban Systems, vol. 33, no. 6, pp. 403408, 2009*.

16. P. A. P. Moran. "The interpretation of statistical maps", *Biometrika* 35, 255260, 1948.

17. Rinzivillo, S. Turini, F. Bogorny, V. Korner, C. Kuijpers, B. and May, B." Knowledge discovery from geographical data". *Mobility, Data Mining and Privacy, vol. pp. 243-265, Springer, 2008.*

18. W. R., Tobler. "Cellular geography", In *Gale S. Olsson G.* (eds) *Phylosophy in Geography, Dortrecht, Reidel*, p.379-86, 1979.

19. K. Zeitouni, L. Yeh. "Le data mining spatial et les bases de données spatiales", *Revue internationale de géomatique, Numro spécial sur le Data mining spatial, Vol 9, N 4, 2000*.