A Hybrid Clustering Algorithm Based on Rough Set and Shared Nearest Neighbors

Abstract:

In this paper, a hybrid method combining rough set and shared nearest neighbor algorithms is proposed for data clustering with non-globular shapes. The rough k-means algorithm is based on the distances between data and cluster centers. It partitions a data set with globular shapes well, but when the data are non-globular shapes, the results obtained by a rough k-means algorithm are not very satisfactory. In order to resolve this problem, a combined rough set and shared nearest neighbor algorithm is proposed. The proposed algorithm first adopts a shared nearest neighbor algorithm to evaluate the similarity among data, then the lower and upper approximations of a rough set algorithm are used to partition the data set into clusters.

• Periodical: Applied Mechanics and Materials (Volume 145)
• Pages: 189-193
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.145.189
• Online since: December 2011
• Authors: Horng Lin Shieh
• Keywords: Data Clustering, k-Means Algorithm, Rough Set (RS), Shared Nearest Neighbor

References

[1] J. Han, and M. Kamber, Data mining: Concepts and Techniques. Second Edition, Morgan Kaufmann Publisher, San Francisco. (2003).

[2] P. Frānti, O. Virmajoki, and V. Hautamāki, "Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph, IEEE Trans. on Pattern analysis and Machine Intelligent, vol. 28, no. 11, pp.1875-1881. (2006).

DOI: 10.1109/tpami.2006.227

[3] B. Walter, K. Bala, M. Kulkarni, and K. Pingali, Fast Agglomerative Clustering for Rendering, IEEE/EG Symposium on Interactive Ray Tracing, , Los Angeles, California, USA, pp.81-86. ( 2008).

DOI: 10.1109/rt.2008.4634626

[4] J. -T. Chien, Decision Tree State Tying Using Cluster Validity Criteria, IEEE Trans. on audio, speech, and Language processing, vol. 13, no. 3, pp.182-193. ( 2005).

DOI: 10.1109/tsa.2004.840941

[5] L. A. Zadeh, Fuzzy sets, Information Control, 8, p.338~353. (1965).

[6] J.C. Bezdek, A convergence theorem for the fuzzy ISODATA clustering algorithms, IEEE Trans. on Pattern Analysis and Machine Intelligence, pp.1-8. (1980).

DOI: 10.1109/tpami.1980.4766964

[7] Z. Pawlak, Rough sets, International Journal of Computer and Information Sciences, 11, 5 , . p.341–356. (1982).

[8] P. Maji and S. K. Pal, Rough Set Based Generalized Fuzzy C-Means Algorithm and Quantitative Indices, IEEE Trans. on Systems, Man and Cybernetics, Part B, vol. 37, no. 6, pp.1529-1540. (2007).

DOI: 10.1109/tsmcb.2007.906578

[9] G. Peters, Some refinements of rough k-means clustering, Pattern Recognition, 39, pp.1481-1491. (2006).

DOI: 10.1016/j.patcog.2006.02.002

[10] H. HAN and M. Mao, Fuzzy-Rough k-Nearest Neighbor Algorithm for Imbalanced Data Sets Learning, International Conference on Fuzzy Systems and Knowledge Discovery, pp.1286-1290. (2010).

DOI: 10.1109/fskd.2010.5569116

[11] S. Mitra, W. Pedrycz and B. Barman, Shadowed c-means: Integrating fuzzy and rough clustering, Pattern Recognition, 43, p.431282–1291. (2010).

DOI: 10.1016/j.patcog.2009.09.029

[12] R. A. Jarvis and E. A. Patrick, Clustering Using a Similarity Measure Based on Shared Near Neighbors, IEEE Trans. on Computers, vol. C-22, no. 11, pp.1025-1034. (1974).

DOI: 10.1109/t-c.1973.223640

[13] Y.Y. Yao, Semantics of Fuzzy Sets in Rough Set Theory, on http: /www2. cs. uregina. ca/~yyao/PAPERS/fuzzy_semantics. pdf.

[14] P. Lingras, M. Chen, and D. Miao, Rough Cluster Quality Index Based on Decision Theory, IEEE Trans. on Knowledge and Data Engineering, vol. 21, no. 7, pp.1014-1025. (2009).

DOI: 10.1109/tkde.2008.236

[15] P. Lingras, R. Yan, Interval Clustering using Fuzzy and Rough Set Theory, IEEE Annual Meeting of the North American Fuzzy Information, Processing, Society, Banff Alberta, Canada. (2004).

DOI: 10.1109/nafips.2004.1337401

[16] J. Komorowski ,L. Polkowski, and A. Skowron, Rough Sets: A Tutorial, on http: /folli. loria. fr/cds/1999/library/pdf/skowron. pdf.