NDLI: Reducing the Time Requirement of k-Means Algorithm

Content Provider	PubMed Central
Author	Osamor, Victor Chukwudi Adebiyi, Ezekiel Femi Oyelade, Jelilli Olarenwaju Doumbia, Seydou
Editor	Bourdon, Jérémie
Copyright Year	2012
Abstract	Traditional k-means and most k-means variants are still computationally expensive for large datasets, such as microarray data, which have large datasets with large dimension size d. In k-means clustering, we are given a set of n data points in d-dimensional space R d and an integer k. The problem is to determine a set of k points in R d , called centers, so as to minimize the mean squared distance from each data point to its nearest center. In this work, we develop a novel k-means algorithm, which is simple but more efficient than the traditional k-means and the recent enhanced k-means. Our new algorithm is based on the recently established relationship between principal component analysis and the k-means clustering. We provided the correctness proof for this algorithm. Results obtained from testing the algorithm on three biological data and six non-biological data (three of these data are real, while the other three are simulated) also indicate that our algorithm is empirically faster than other known k-means algorithms. We assessed the quality of our algorithm clusters against the clusters of a known structure using the Hubert-Arabie Adjusted Rand index (ARIHA). We found that when k is close to d, the quality is good (ARIHA>0.8) and when k is not close to d, the quality of our new k-means algorithm is excellent (ARIHA>0.9). In this paper, emphases are on the reduction of the time requirement of the k-means algorithm and its application to microarray data due to the desire to create a tool for clustering and malaria research. However, the new clustering algorithm can be used for other clustering needs as long as an appropriate measure of distance between the centroids and the members is used. This has been demonstrated in this work on six non-biological data.
Related Links	http://dx.doi.org/10.1371/journal.pone.0049946
Starting Page	49946
File Format	PDF
ISSN	19326203
e-ISSN	19326203
Journal	PLoS ONE
Issue Number	12
Volume Number	7
Language	English
Publisher	Public Library of Science
Publisher Date	2012-12-01
Access Restriction	Open
Rights Holder	Public Library of Science
Subject Keyword	Biochemistry, Genetics and Molecular Biology(all) Agricultural and Biological Sciences(all) Medicine(all) Research in Higher Education
Content Type	Text
Resource Type	Article
Subject	Multidisciplinary

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Comparison of K-Means and Fuzzy c-Means Algorithm Performance for Automated Determination of the Arterial Input Function

ARK: Aggregation of Reads by K-Means for Estimation of Bacterial Community Composition

A Simple Algorithm for Finding All k-Edge-Connected Components

Requirement of SLD5 for Early Embryogenesis

Cofactor Requirement of HpyAV Restriction Endonuclease

Detection of the Elite Structure in a Virtual Multiplex Social System by Means of a Generalised K-Core

Predicting the Electron Requirement for Carbon Fixation in Seas and Oceans

Algorithm for the Time-Propagation of the Radial Diffusion Equation Based on a Gaussian Quadrature

Accelerating Bayesian Hierarchical Clustering of Time Series Data with a Randomised Algorithm

Reducing the Time Requirement of k-Means Algorithm

Similar Documents

Comparison of K-Means and Fuzzy c-Means Algorithm Performance for Automated Determination of the Arterial Input Function

ARK: Aggregation of Reads by K-Means for Estimation of Bacterial Community Composition

A Simple Algorithm for Finding All k-Edge-Connected Components

Requirement of SLD5 for Early Embryogenesis

Cofactor Requirement of HpyAV Restriction Endonuclease

Detection of the Elite Structure in a Virtual Multiplex Social System by Means of a Generalised K-Core

Predicting the Electron Requirement for Carbon Fixation in Seas and Oceans

Algorithm for the Time-Propagation of the Radial Diffusion Equation Based on a Gaussian Quadrature

Accelerating Bayesian Hierarchical Clustering of Time Series Data with a Randomised Algorithm

Reducing the Time Requirement of k-Means Algorithm