An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search TeX

@incollection{citeulike:1379636, abstract = {Clustering in data mining is a discovery process that groups similar objects into the same cluster. Various clustering algorithms have been designed to fit various requirements and constraints of application. In this paper, we study several \$k\$-medoids-based algorithms including the \$PAM\$, \$CLARA\$ and \$CLARANS\$ algorithms. A novel and efficient approach is proposed to reduce the computational complexity of such \$k\$-medoids-based algorithms by using previous medoid index, triangular inequality elimination criteria and partial distance search. Experimental results based on elliptic, curve and Gauss-Markov databases demonstrate that the proposed algorithm applied to \$CLARANS\$ may reduce the number of distance calculations by 67\% to 92\% while retaining the same average distance per object. In terms of the running time, the proposed algorithm may reduce computation time by 38\% to 65\% compared with the \$CLARANS\$ algorithm.}, author = {Chu, Shu-Chuan and Roddick, John F. and Pan, J. S.}, citeulike-article-id = {1379636}, journal = {Data Warehousing and Knowledge Discovery: 4th International Conference, DaWaK 2002, Aix-en-Provence, France, September 4-6, 2002. Proceedings}, keywords = {clustering, kmedoids}, pages = {301--311}, posted-at = {2007-06-12 04:19:28}, priority = {4}, title = {An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search}, url = {http://www.springerlink.com/content/pump5duqc23hx0gw }, year = {2002} }

TY - CHAP ID - citeulike:1379636 L3 - citeulike-article-id:1379636 N2 - Clustering in data mining is a discovery process that groups similar objects into the same cluster. Various clustering algorithms have been designed to fit various requirements and constraints of application. In this paper, we study several $k$-medoids-based algorithms including the $PAM$, $CLARA$ and $CLARANS$ algorithms. A novel and efficient approach is proposed to reduce the computational complexity of such $k$-medoids-based algorithms by using previous medoid index, triangular inequality elimination criteria and partial distance search. Experimental results based on elliptic, curve and Gauss-Markov databases demonstrate that the proposed algorithm applied to $CLARANS$ may reduce the number of distance calculations by 67% to 92% while retaining the same average distance per object. In terms of the running time, the proposed algorithm may reduce computation time by 38% to 65% compared with the $CLARANS$ algorithm. JF - Data Warehousing and Knowledge Discovery: 4th International Conference, DaWaK 2002, Aix-en-Provence, France, September 4-6, 2002. Proceedings EP - 311 TI - An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search SP - 301 KW - clustering KW - kmedoids AU - Chu, Shu-Chuan AU - Roddick, John AU - Pan, JS PY - 2002/// UR - http://www.springerlink.com/content/pump5duqc23hx0gw ER -