With the advent of modern techniques for scientific data collection, large quantities of data are getting accumulated at various databases. Systematic data analysis methods are necessary to extract useful information from rapidly growing data banks. Cluster analysis is one of the major data mining methods and the k-means clustering algorithm is widely used for many practical applications. But the original k-means algorithm is computationally expensive and the quality of the resulting clusters substantially relies on the choice of initial centroids. Several methods have been proposed in the literature for improving the performance of the k-means algorithm. This paper proposes an improvement on the classic k-means algorithm to produce more accurate clusters. The proposed algorithm comprises of a O(n logn) heuristic method, based on sorting and partitioning the input data, for finding the initial centroids in accordance with the data distribution. Experimental results show that the proposed algorithm produces better clusters in less computation time.
The creation of stable, scalable and adaptive clusters with good performance, faster convergence rate and with minimal overhead is a challenging task in mobile ad hoc networks (MANETs). This study proposes two clustering techniques for MANETs, which are (k, r)-dominating set-based, weighted and adaptive to changes in the network topology. The set of dominating nodes functions as the clusterheads. The scenario-based clustering algorithm for MANETs (SCAM) is a greedy approximation algorithm, whereas the distributed-SCAM (DSCAM) selects the (k, r)-dominating set through a distributed election mechanism. These algorithms achieve variable degree of clusterhead redundancy through the parameter k which contributes to reliability. Similarly, flexibility in creating variable diameter clusters is achieved with the parameter r. To improve the stability of the created clusters, the affiliation of other nodes with the clusterhead is decided based on the quality of the clusterhead, which is a function of connectivity, stability, residual battery power and transmission range. Mechanisms are available for accounting the group mobility and load balancing. The performance of these algorithms are evaluated through simulation and the results show that these algorithms create stable, scalable and load-balanced clusters with relatively less control overhead in comparison with the existing popular algorithms.