The practice of using divide and conquer techniques to solve complex, time-consuming problems has been in use for a very long time. Here we evaluate the performance of centroid-based clustering techniques, specifically k-means and its two approximation algorithms, the k-means++ and k-means (also known as Scalable k-means++), as divide and conquer paradigms applied for the creation of minimum spanning trees. The algorithms will be run on different datasets to get a good evaluation of their respective performances. This is a continuation of our previous work carried out in developing the KMST+ algorithm in the context of fast minimum spanning tree (FMST) frameworks. © 2017 IEEE.

Balakrushna Tripathy

Department of Analytics

School of Computer Science and Engineering

Vellore Campus

Sabhijiit S. Sandhu

Ashwin R. Jadhav

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

2017 Third International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN)

In this paper, we have implemented a unique form of clustering that takes a non-numeric data set and clusters it with the help of the word embedding provided by the GloVe dataset. The related word embedding are generated for each of the items in the dataset we want to cluster using the GloVe vector representation of those words. We then perform dimensionality reduction on the data set to obtain the accurate number of dimensions to be taken for appropriate cluster formation. The data is then clustered using k-means++. This paper provides one of the ways to overcome the limitation of k-means clustering in terms of initialising the cluster centres and hence gives better quality clusters. With the synthetic examples, the k-means method does not perform well, because the random seeding inevitably merges clusters together, and the algorithm is unable to then split them apart. Careful seeding method used by k-means++ prevents this problem and hence usually gives optimal results even when datasets are synthetic. © 2017 IEEE.

2017 International Conference on Intelligent Sustainable Systems (ICISS)

Implementing GloVe for context based k-means++ clustering

There are a number of algorithms that have been proposed in the graph theory literature to compute the minimum spanning tree of a given graph. These include the famous Prim’s and Kruskal’s algorithm, among others. The main drawback of these algorithms is their greedy nature, which means they cannot be applied to large datasets. In 2015, Zhong et al. proposed a fast MST (FMST) algorithm framework that uses K-means to find the MST with a reduced complexity of O(N1.5). In this paper, we have introduced an improved version of the FMST algorithm by using K-means++ to further increase the efficiency of the FMST algorithm. The use of K-means++ instead of K-means results in lesser complexity, faster convergence, and more accurate results during the clustering step which improves the accuracy of the MST formed. © Springer Nature Singapore Pte Ltd. 2019.

Smart Innovations in Communication and Computational Sciences Advances in Intelligent Systems and Computing

KMST+: A K-Means++-Based Minimum Spanning Tree Algorithm

Information Sciences

A fast minimum spanning tree algorithm based on K-means

Proceedings of the VLDB Endowment

Scalable k-means++

Proceedings of the twenty-second annual symposium on Computational geometry - SCG '06

How slow is the k-means method?

Computer

Chameleon: hierarchical clustering using dynamic modeling

Comparison of centroid-based clustering algorithms in the context of divide and conquer paradigm based FMST framework

Journal	Data powered by Typeset2017 Third International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN)
Publisher	Data powered by TypesetIEEE
Open Access	0