4.7 Article

Iterated Watersheds, A Connected Variation of K-Means for Clustering GIS Data

Journal

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TETC.2019.2910147

Keywords

Clustering algorithms; Partitioning algorithms; Cost function; Approximation algorithms; Image segmentation; Roads; Graph clustering; K-means; E-governance; watersheds

Funding

  1. Department of Science and Technology-Science and Engineering research Board (DSTSERB)
  2. Indian Space Research Organization (ISRO) [EMR/2015/000853, ISRO/SSPO/Ch-1/2016-17]
  3. Agence Nationale de la Recherche [ANR-14-CE27-0001]
  4. Programme d'Investissements d'Avenir (LabEx BEZOUT) [ANR-10-LABX-58]
  5. Agence Nationale de la Recherche (ANR) [ANR-14-CE27-0001] Funding Source: Agence Nationale de la Recherche (ANR)

Ask authors/readers for more resources

This article introduces a modified algorithm, the iterated watersheds, based on K-Means, to address the clustering problem with connectivity constraints. Through experiments on toy examples and real-world applications, it is found that iterated watersheds outperforms traditional methods in tasks such as image segmentation and road network optimization.
In this article, we propose a novel algorithm to obtain a solution to the clustering problem with an additional constraint of connectivity. This is achieved by suitably modifying K-Means algorithm to include connectivity constraints. The modified algorithm involves repeated application of watershed transform, and hence is referred to as iterated watersheds. Detailed analysis of the algorithm is performed using toy examples. Iterated watersheds is compared with several image segmentation algorithms. It has been shown that iterated watersheds performs better than methods such as spectral clustering, isoperimetric partitioning, and K-Means on various measures. To illustrate the applicability of iterated watersheds - a simple problem of placing emergency stations and suitable cost function is considered. Using real world road networks of various cities, iterated watersheds is compared with K-Means and greedy K-center methods. It is observed that iterated watersheds result in 4 - 66 percent improvement over K-Means and in 31 - 72 percent improvement over Greedy K-Centers in experiments on road networks of various cities.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available