single-jc.php

JACIII Vol.23 No.3 pp. 577-583
doi: 10.20965/jaciii.2019.p0577
(2019)

Paper:

Cluster Validity Measures Based Agglomerative Hierarchical Clustering for Network Data

Yukihiro Hamasuna*1, Shusuke Nakano*2, Ryo Ozaki*3, and Yasunori Endo*4,†

*1Department of Informatics, School of Science and Engineering, Kindai University
3-4-1 Kowakae, Higashiosaka, Osaka 577-8502, Japan

*2Graduate School of Science and Engineering, Kindai University
3-4-1 Kowakae, Higashiosaka, Osaka 577-8502, Japan

*3ALBERT Inc.
1-26-2 Nishishinjuku, Shinjuku-ku, Tokyo 163-0515, Japan

*4Faculty of Engineering, Information and Systems, University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan

Corresponding author

Received:
December 29, 2017
Accepted:
February 7, 2019
Published:
May 20, 2019
Keywords:
cluster validity measures, hierarchical clustering, modularity, Louvain method, network clustering
Abstract

The Louvain method is a method of agglomerative hierarchical clustering (AHC) that uses modularity as the merging criterion. Modularity is an evaluation measure for network partitions. Cluster validity measures are also used to evaluate cluster partitions and to determine the optimal number of clusters. Several cluster validity measures are constructed considering the geometric features of clusters. These measures and modularity are considered to be the same concept in the viewpoint of evaluating cluster partitions. In this paper, cluster validity measures based agglomerative hierarchical clustering (CVAHC) is proposed as a novel clustering method for network data. The cluster validity measures are used as a merging criterion and an evaluation measure for network data in the proposed method. Numerical experiments show that Dunn’s and Xie-Beni’s indices for network partitions are useful for network clustering.

Cite this article as:
Y. Hamasuna, S. Nakano, R. Ozaki, and Y. Endo, “Cluster Validity Measures Based Agglomerative Hierarchical Clustering for Network Data,” J. Adv. Comput. Intell. Intell. Inform., Vol.23, No.3, pp. 577-583, 2019.
Data files:
References
  1. [1] M. Newman, “Networks: An Introduction,” Oxford University Press, New York, 2010.
  2. [2] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. of the National Academy of Sciences (PNAS), Vol.99, No.12, pp. 7821-7826, 2002.
  3. [3] S. Miyamoto, “Fuzzy Sets in Information Retrieval and Cluster Analysis,” Springer, 1990.
  4. [4] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. of Statistical Mechanics: Theory and Experiment, P10008, 2008.
  5. [5] W. Wang and Y. Zhang, “On fuzzy cluster validity indices,” Fuzzy Sets and Systems, Vol.158, No.19, pp. 2095-2117, 2007.
  6. [6] S. Miyamoto, H. Ichihashi, and K. Honda, “Algorithms for Fuzzy Clustering,” Springer, Heidelberg, 2008.
  7. [7] W. Hashimoto, T. Nakamura, and S. Miyamoto, “Comparison and evaluation of different cluster validity measures including their kernelization,” J. Adv. Comput. Intell. Intell. Inform., Vol.13, No.3, pp. 204-209, 2009.
  8. [8] N. Slonim and N. Tishby, “Agglomerative Information Bottleneck,” Proc. of Advances in Neural Information Processing Systems 12 (NIPS 1999), pp. 617-623, 1999.
  9. [9] Y. Tamura and S. Miyamoto, “Two-stage clustering using one-pass k-medoids and medoid-based agglomerative hierarchical algorithms,” Proc. of 7th Int. Conf. on Soft Computing and Intelligent Systems and 15th Int. Symp. on Advanced Intelligent Systems (SCIS&ISIS2014), pp. 484-488, 2014.
  10. [10] J. C. Dunn, “Well separated clusters and optimal fuzzy partitions,” J. of Cybernetics, Vol.4, pp. 95-104, 1974.
  11. [11] I. Gath and A. B. Geva, “Unsupervised optimal fuzzy clustering,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.11, No.7, pp. 773-780, 1989.
  12. [12] X. L. Xie and G. Beni, “A validity measure for fuzzy clustering,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.13, No.8, pp. 841-847, 1991.
  13. [13] Y. Hamasuna, D. Kobayashi, R. Ozaki, and Y. Endo, “Cluster validity measures for network data,” J. Adv. Comput. Intell. Intell. Inform., Vol.22, No.4, pp. 544-550, 2018.
  14. [14] R. Ozaki, Y. Hamasuna, and Y. Endo, “Agglomerative hierarchical clustering based on local optimization for cluster validity measures,” IEEE Int. Conf. on Systems, Man, and Cybernetics (IEEE SMC 2017), pp. 1822-1827, 2017.
  15. [15] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum Press, New York, 1981.
  16. [16] M. Lichman, UCI Machine Learning Repository, Irvine, CA: University of California, School of Information and Computer Science, 2013, http://archive.ics.uci.edu/ml [accessed December 12, 2017]
  17. [17] L. Hubert and P. Arabie, Comparing Partitions, J. of Classification, Vol.2, No.1, pp. 193-218, 1985.
  18. [18] Y. Hamasuna, R. Ozaki, and Y. Endo, “A study on cluster validity measures for clustering network data,” Joint 17th World Congress of lnt. Fuzzy Systems Association and 9th Int. Conf. on Soft Computing and Intelligent Systems (IFSA-SCIS2017), #89, 2017.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Sep. 19, 2019