期刊
IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING
卷 9, 期 2, 页码 626-636出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TETC.2019.2910147
关键词
Clustering algorithms; Partitioning algorithms; Cost function; Approximation algorithms; Image segmentation; Roads; Graph clustering; K-means; E-governance; watersheds
资金
- Department of Science and Technology-Science and Engineering research Board (DSTSERB)
- Indian Space Research Organization (ISRO) [EMR/2015/000853, ISRO/SSPO/Ch-1/2016-17]
- Agence Nationale de la Recherche [ANR-14-CE27-0001]
- Programme d'Investissements d'Avenir (LabEx BEZOUT) [ANR-10-LABX-58]
- Agence Nationale de la Recherche (ANR) [ANR-14-CE27-0001] Funding Source: Agence Nationale de la Recherche (ANR)
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据