Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


6979.pdf (1.2 MB)

ETD Abstract Container

Abstract Header

K-Centers Dynamic Clustering Algorithms and Applications

Xie, Qing Yan
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1384427644

Abstract Details

2013, PhD, University of Cincinnati, Engineering and Applied Science: Computer Science and Engineering.
Every day large and increasing amounts of unstructured information are created, putting ever more demands on retrieval methods, classification, automatic data analysis and management. Clustering is an important and efficient way for organizing and analyzing information and data. One of the most widely used dynamic clustering algorithms is K-Means clustering. This dissertation presents our K-Centers Min-Max dynamic clustering algorithm (KCMM) and K-Centers Mean-shift Reverse Mean-shift dynamic clustering algorithm (KCMRM). These algorithms are designed to modify K-Means in order to achieve improved performance and help with specific goals in certain domains. These two algorithms can be applied to many fields such as wireless sensor networks, server or facility location optimization, and molecular networks. Their application in wireless sensor networks are described in this dissertation. The K-Centers Min-Max clustering algorithm uses a smallest enclosing disk/sphere algorithm to attain a minimum of the maximum distance between a cluster node and data nodes. Our approach results in fewer iterations, and shorter maximum intra-cluster distances than the standard K-Means clustering algorithm with either uniform distribution or normal distribution. Most notably, it can achieve much better performance when the size of clusters is large, or when the clusters includes large numbers of member nodes in normal distribution. The K-Centers Mean-shift Reverse Mean-shift clustering algorithm is proposed to solve the "empty cluster" problem which is caused by random deployment. It employs a Gaussian function as a kernel function, discovers the relationship between mean shift and gradient ascent on the estimated density surface, and iteratively moves cluster nodes away from their weighted means. This results in cluster nodes which better accommodate the distribution of data nodes. The K-Centers Mean-shift Reverse Mean-shift algorithm can not only reduce the number of empty clusters, but can also make the sizes of clusters are more evenly balanced compared to K-Means and K-Centers Min-Max clustering algorithms. In wireless sensor networks, addressing energy dissipation is a key issue. For heterogeneous wireless sensor networks, energy consumption to transmit data is proportional to the distance between sensor nodes and cluster heads or to a base station. Clustering is one of the best methods to reduce energy dissipation and extend network lifetimes. The K-Centers Min-Max and K-Centers Mean-shift Reverse Mean-shift clustering algorithms are applied to two proposed protocols, KCMM and KCMRM, for wireless sensor networks. Desirable features of the proposed clustering protocols KCMM and KCMRM include: energy efficiency; distributed and localized data aggregation; adaptation to changes in sensor distribution; robustness to partial damage; and self-recovery. Besides the above features, KCMRM protocol can make use of cluster heads efficiently and can reduce empty clusters.
Yizong Cheng, Ph.D. (Committee Chair)
Kenneth Berman, Ph.D. (Committee Member)
Wen Ben Jone, Ph.D. (Committee Member)
Anca Ralescu, Ph.D. (Committee Member)
Xuefu Zhou, Ph.D. (Committee Member)
107 p.
Computer Science
Clustering algorithm; K-Means; K-Centers Min-Max clustering algorithm; mean-shift; K-Centers Mean-shift Reverse Mean-shift; wireless sensor networks

Recommended Citations

Citations

  • Xie, Q. Y. (2013). K-Centers Dynamic Clustering Algorithms and Applications [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1384427644

    APA Style (7th edition)

  • Xie, Qing Yan. K-Centers Dynamic Clustering Algorithms and Applications. 2013. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1384427644.

    MLA Style (8th edition)

  • Xie, Qing Yan. "K-Centers Dynamic Clustering Algorithms and Applications." Doctoral dissertation, University of Cincinnati, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1384427644

    Chicago Manual of Style (17th edition)

ucin1384427644
495
© 2013, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.