DIC-DOC- K -means: Dissimilarity-based Initial Centroid selection for DOCument clustering using K -means for improving the effectiveness of text document clustering
Restricted accessResearch articleFirst published online December, 2019
DIC-DOC- K -means: Dissimilarity-based Initial Centroid selection for DOCument clustering using K -means for improving the effectiveness of text document clustering
In this article, a new initial centroid selection for a K-means document clustering algorithm, namely, Dissimilarity-based Initial Centroid selection for DOCument clustering using K-means (DIC-DOC-K-means), to improve the performance of text document clustering is proposed. The first centroid is the document having the minimum standard deviation of its term frequency. Each of the other subsequent centroids is selected based on the dissimilarities of the previously selected centroids. For comparing the performance of the proposed DIC-DOC-K-means algorithm, the results of the K-means, K-means++ and weighted average of terms-based initial centroid selection + K-means (Weight_Avg_Initials + K-means) clustering algorithms are considered. The results show that the proposed DIC-DOC-K-means algorithm performs significantly better than the K-means, K-means++ and Weight_Avg_Initials+ K-means clustering algorithms for Reuters-21578 and WebKB with respect to purity, entropy and F-measure for most of the cluster sizes. The cluster sizes used for Reuters-8 are 8, 16, 24 and 32 and those for WebKB are 4, 8, 12 and 16. The results of the proposed DIC-DOC-K-means give a better performance for the number of clusters that are equal to the number of classes in the data set.
HanJKamberM.Data mining: concepts and techniques. 2nd ed. San Francisco, CA: Morgan Kaufmann, 2006.
2.
Al-MubaidHUmairSA.A new text categorization technique using distributional clustering and learning logic. IEEE Trans Knowl Data Eng2006; 18(9): 1156–1165.
ShetkarAAFernandesS.Text categorization of documents using K-means and K-means++ clustering algorithm. Int J Recent Innov Tren Comput Commun2016; 4(6): 485–489.
5.
PenaJMLozanoJALarranagaP.An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognit Lett1999; 20(10): 1027–1040.
6.
SteinleyDBruscoMJ.Initializing K-means batch clustering: a critical evaluation of several techniques. J Classif2007; 24: 99–121.
7.
ArthurDVassilvitskiiS. K-means++: the advantages of careful seeding. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, New Orleans, Louisiana, 7–9 January 2007, pp. 1027–1035.
8.
KangPChoS. K-means clustering seeds initialization based on centrality, sparsity and isotropy. In: International conference on intelligent data engineering and automated learning, Burgos, 23–26 September 2009, pp. 109–117. Berlin: Springer.
9.
KhanF.An initial seed selection algorithm for K-means clustering of georeferenced data to improve replicability of cluster assignment for mapping application. Appl Soft Comput2012; 12: 3698–3700.
10.
Karteeka PavanKRaoAARaoAVD, et al. Single pass seed selection algorithm for K-means. J Comput Sci2010; 6(1): 60–66.
11.
AghaMEAshourWM.Efficient and fast initialization algorithm for k-means clustering. Int J Intell Syst Appl2010; 1: 21–31.
12.
OnanABulutHKorukogluS.An improved ant algorithm with LDA-based representation for text document clustering. J Inf Sci2017; 43(2): 275–292.
13.
Jaya Mabel RaniMLathaP. Clustering analysis by improved particle swarm optimization and K-means algorithm. In: International conference on sustainable energy and intelligent systems, Tiruchengode, India, 27–29 December 2012.
14.
Sampath PremkumarMHari GaneshS. A median based external initial centroid selection method for K-means clustering. In: World congress on computing and communication technologies, Tiruchirappalli, India, 2–4 February 2017.
15.
Sohrab MahmudMMostafizer RahmanMNasim AkhtarM. Improvement of K-means clustering algorithm with better initial centroids based on weighted average. In: International conference on 2012 7th international conference on electrical and computer engineering, Dhaka, Bangladesh, 20–22 December 2012.
16.
Mahesh KumarKRama Mohan ReddyA. A fast K-means clustering using prototypes for initial cluster center selection. In: International conference on intelligent systems and control, Coimbatore, India, 9–10 January 2015.
17.
XinwuL. Research on text clustering algorithm based on improved K-means. In: International conference on computer design and applications, Qinhuangdao, China, 25–27 June 2010.
18.
JaganathanPJaiganeshS. An improved K-means algorithm combined with particle swarm optimization approach for efficient web document clustering. In: International conference on green computing, communication and conservation of energy (ICGCE), Chennai, India, 12–14 December 2014.
19.
YuanFMengZHZhangHX, et al. A new algorithm to get the initial centroids. In: Proceedings of international conference on machine learning and cybernetics, Shanghai, China, 26–29 August 2004.
20.
WangZLiuZChenD, et al. A new partitioning based algorithm for document clustering. In: International conference on fuzzy systems and knowledge discovery, Shanghai, China, 26–28 July 2011.
21.
KataraJChoudharyN.A modified version of the K-means clustering algorithm. Global J Comput Sci Technol2015; 15(7): 1–7.
22.
de AmorimRCMirkinB. Minkowski metric, feature weighting and anomalous cluster initializing in K-means clustering. Pattern Recognit2012; 45(3): 1061–1075.
23.
KumarYSahooG.A new initialization method to originate initial clusters for K-means algorithm. Int J Adv Sci Technol2014; 62: 43–54.
24.
CelebiMEKingraviHAVelaPA.A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Syst Appl2013; 40(1): 200–210.
25.
KhanSSAhmadA.Cluster center initialization algorithm for k-means clustering. Pattern Recognit Lett2004; 25(11): 1293–1302.
26.
ZhangHYangZOjaE.Improving cluster analysis by co-initializations. Pattern Recognit Lett2014; 45: 71–77.
27.
KanungoTMountDMNetanyahuNS, et al. An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans Pattern Anal Mach Intell2002; 24(7): 881–892.
28.
AliguliyevRM.Clustering of document collection – a weighting approach. Expert Syst Appl2009; 36: 7904–7916.
29.
ChenY-LChiuY-T.Vector space model for patent documents with hierarchical class labels. J Inf Sci2012; 38(3): 212–233.
30.
RochaRCoboA.Feature selection strategies for automated classification of digital media content. J Inf Sci2011; 37(4): 418–428.
31.
BidePShedgeR.Improved document clustering using k-means algorithm. In: 2015 IEEE international conference on electrical, computer and communication technologies (ICECCT), Coimbatore, India, 5–7 March 2015.
32.
ChenC-H.Improved TFIDF in big news retrieval: an empirical study. Pattern Recognit Lett2017; 93: 113–122.
33.
LinYSJiangJYLeeSJ.A similarity measure for text classification and clustering. IEEE Trans Knowl Data Eng2014; 26(7): 1575–1590.
34.
BasuTMurthyCA.A similarity assessment technique for effective grouping of documents. Inf Sci2015; 311: 149–162.
35.
DhillonISModhaDS.Concept decompositions for large sparse test data using clustering. Mach Learn2001; 42(1): 143–175.
36.
ZhangXShenQGaoH, et al. A density-based method for initializing the k-means clustering algorithm. In: Proceedings of 2012 international conference on network and computational intelligence, Homg Kong, China, 3–4 August 2012, pp. 46–53.
37.
AubaidanBMohdMAlbaredM.Comparative study of k-means and k-means++ clustering algorithms on crime domain. J Comput Sci2014; 10(7): 1197–1206.
38.
AgarwalMJaiswalRPalA.k-means++ under approximation stability. In: International conference on theory and applications of models of computation, Hong Kong, China, 20–22 May 2013, pp. 84–95. Berlin: Springer.
