NGTSOM: A Novel Data Clustering Algorithm Based on Game Theoretic and Self- Organizing Map

Document Type : Research Article

Authors

1 Young Researchers and Elite Club, Qazvin Branch, Islamic Azad University, Qazvin, Iran

2 Dept. of Electrical Engineering, Amirkabir University of Technology, Tehran, Iran

3 Dept. of Decision Science and Knowledge Engineering, University of Economic Sciences, Tehran, Iran

Abstract

Identifying clusters is an important aspect of data analysis. This paper proposes a novel
data clustering algorithm to increase the clustering accuracy. A novel game theoretic self-organizing
map (NGTSOM ) and neural gas (NG) are used in combination with Competitive Hebbian Learning
(CHL) to improve the quality of the map and provide a better vector quantization (VQ) for clustering
data. Different strategies of Game Theory are proposed to provide a competitive game for nonwinning
neurons to participate in the learning phase and obtain more input patterns. The performance
of the proposed clustering analysis is evaluated and compared with that of the K-means, SOM and
NG methods using different types of data. The clustering results of the proposed method and existing
state-of-the-art clustering methods are also compared which demonstrates a better accuracy of the
proposed clustering method.

Highlights

[1] R. Duwairi, M. Abu-Rahmeh, A novel approach for initializing the spherical K-means clustering algorithm, Simulation Modelling Practice and Theory, 54 (2015) 49-63.

[2] H. Mashayekhi, J. Habibi, S. Voulgaris, M. van Steen, GoSCAN: Decentralized scalable data clustering, Computing, 95(9) (2013) 759-784.

[3] S.M.R. Zadegan, M. Mirzaie, F. Sadoughi, Ranked k-medoids: A fast and accurate rank-based partitioning algorithm for clustering large datasets, Knowledge-Based Systems, 39 (2013) 133-143.

[4] J. MacQueen, Some methods for classification and analysis of multivariate observations, in:  Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, Oakland, CA, USA., 1967, pp. 281-297.

[5] H.-S. Park, C.-H. Jun, A simple and fast algorithm for K-medoids clustering, Expert systems with applications, 36(2) (2009) 3336-3341.

[6] J.C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters,  (1973).

[7] S. Miyamoto, K. Umayahara, Methods in hard and fuzzy clustering, in:  Soft computing and human-centered machines, Springer, 2000, pp. 85-129.

[8] T. Johnson, S.K. Singh, Genetic algorithms based enhanced K Strange points clustering algorithm, in:  Computing and Network Communications (CoCoNet), 2015 International Conference on, IEEE, 2015, pp. 737-741.

[9] A. Likas, N. Vlassis, J.J. Verbeek, The global k-means clustering algorithm, Pattern recognition, 36(2) (2003) 451-461.

[10] D. Arthur, S. Vassilvitskii, k-means++: The advantages of careful seeding, in:  Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 1027-1035.

[11] C. Zhang, D. Ouyang, J. Ning, An artificial bee colony approach for clustering, Expert Systems with Applications, 37(7) (2010) 4761-4767.

[12] W. Kwedlo, A clustering method combining differential evolution with the K-means algorithm, Pattern Recognition Letters, 32(12) (2011) 1613-1621.

[13] T. Kohonen, The self-organizing map, Proceedings of the IEEE, 78(9) (1990) 1464-1480.

[14] S. Wu, T.W. Chow, Clustering of the self-organizing map using a clustering validity index based on inter-cluster and intra-cluster density, Pattern Recognition, 37(2) (2004) 175-188.

[15] Y. Dogan, D. Birant, A. Kut, SOM++: integration of self-organizing map and k-means++ algorithms, in:  International Workshop on Machine Learning and Data Mining in Pattern Recognition, Springer, 2013, pp. 246-259.

[16] A. Neme, S. Hernández, O. Neme, L. Hernández, Self-Organizing Maps with Non-cooperative Strategies (SOM-NC), in:  WSOM, Springer, 2009, pp. 200-208.

[17] A.P. Engelbrecht, Computational intelligence: an introduction, John Wiley & Sons, 2007.

[18] L. Pavel, Game theory for control of optical networks, Springer Science & Business Media, 2012.

[19] J. Shen, S.I. Chang, E.S. Lee, Y. Deng, S.J. Brown, Determination of cluster number in clustering microarray data, Applied Mathematics and Computation, 169(2) (2005) 1172-1185.

[20] S. Subramani, S. Balasubramaniam, Post mining of diversified multiple decision trees for actionable knowledge discovery, in:  International Conference on Advanced Computing, Networking and Security, Springer, 2011, pp. 179-187.

[21] T. Martinetz, K. Schulten, A" neural-gas" network learns topologies,  (1991).

[22] B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii, Scalable k-means++, Proceedings of the VLDB Endowment, 5(7) (2012) 622-633.

[23] http://cs.uef.fi/sipu/datasets.

[24] https://archive.ics.uci.edu/ml/datasets.

Keywords

References

[1] R. Duwairi, M. Abu-Rahmeh, A novel approach for initializing the spherical K-means clustering algorithm, Simulation Modelling Practice and Theory, 54 (2015) 49-63.
[2] H. Mashayekhi, J. Habibi, S. Voulgaris, M. van Steen, GoSCAN: Decentralized scalable data clustering, Computing, 95(9) (2013) 759-784.
[3] S.M.R. Zadegan, M. Mirzaie, F. Sadoughi, Ranked k-medoids: A fast and accurate rank-based partitioning algorithm for clustering large datasets, Knowledge-Based Systems, 39 (2013) 133-143.
[4] J. MacQueen, Some methods for classification and analysis of multivariate observations, in:  Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, Oakland, CA, USA., 1967, pp. 281-297.
[5] H.-S. Park, C.-H. Jun, A simple and fast algorithm for K-medoids clustering, Expert systems with applications, 36(2) (2009) 3336-3341.
[6] J.C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters,  (1973).
[7] S. Miyamoto, K. Umayahara, Methods in hard and fuzzy clustering, in:  Soft computing and human-centered machines, Springer, 2000, pp. 85-129.
[8] T. Johnson, S.K. Singh, Genetic algorithms based enhanced K Strange points clustering algorithm, in:  Computing and Network Communications (CoCoNet), 2015 International Conference on, IEEE, 2015, pp. 737-741.
[9] A. Likas, N. Vlassis, J.J. Verbeek, The global k-means clustering algorithm, Pattern recognition, 36(2) (2003) 451-461.
[10] D. Arthur, S. Vassilvitskii, k-means++: The advantages of careful seeding, in:  Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 1027-1035.
[11] C. Zhang, D. Ouyang, J. Ning, An artificial bee colony approach for clustering, Expert Systems with Applications, 37(7) (2010) 4761-4767.
[12] W. Kwedlo, A clustering method combining differential evolution with the K-means algorithm, Pattern Recognition Letters, 32(12) (2011) 1613-1621.
[13] T. Kohonen, The self-organizing map, Proceedings of the IEEE, 78(9) (1990) 1464-1480.
[14] S. Wu, T.W. Chow, Clustering of the self-organizing map using a clustering validity index based on inter-cluster and intra-cluster density, Pattern Recognition, 37(2) (2004) 175-188.
[15] Y. Dogan, D. Birant, A. Kut, SOM++: integration of self-organizing map and k-means++ algorithms, in:  International Workshop on Machine Learning and Data Mining in Pattern Recognition, Springer, 2013, pp. 246-259.
[16] A. Neme, S. Hernández, O. Neme, L. Hernández, Self-Organizing Maps with Non-cooperative Strategies (SOM-NC), in:  WSOM, Springer, 2009, pp. 200-208.
[17] A.P. Engelbrecht, Computational intelligence: an introduction, John Wiley & Sons, 2007.
[18] L. Pavel, Game theory for control of optical networks, Springer Science & Business Media, 2012.
[19] J. Shen, S.I. Chang, E.S. Lee, Y. Deng, S.J. Brown, Determination of cluster number in clustering microarray data, Applied Mathematics and Computation, 169(2) (2005) 1172-1185.
[20] S. Subramani, S. Balasubramaniam, Post mining of diversified multiple decision trees for actionable knowledge discovery, in:  International Conference on Advanced Computing, Networking and Security, Springer, 2011, pp. 179-187.
[21] T. Martinetz, K. Schulten, A" neural-gas" network learns topologies,  (1991).
[22] B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii, Scalable k-means++, Proceedings of the VLDB Endowment, 5(7) (2012) 622-633.
[23] http://cs.uef.fi/sipu/datasets.
[24] https://archive.ics.uci.edu/ml/datasets.
AUT Journal of Modeling and Simulation
Volume 49, Issue 2
December 2017
Pages 133-142

Files

Share

How to cite

Statistics