JACIII Vol.19 No.1 pp. 23-28
doi: 10.20965/jaciii.2015.p0023


On Cluster Extraction from Relational Data Using L1-Regularized Possibilistic Assignment Prototype Algorithm

Yukihiro Hamasuna* and Yasunori Endo**

*Department of Informatics, School of Science and Engineering, Kinki University, 3-4-1 Kowakae, Higashi-osaka, Osaka 577-8502, Japan
**Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan

April 20, 2014
August 25, 2014
Online released:
January 20, 2015
January 20, 2015
assignment prototype algorithm, possibilistic clustering, L1-regularization, sequential cluster extraction, relational data

This paper proposes entropy-based L1-regularized possibilistic clustering and a method of sequential cluster extraction from relational data. Sequential cluster extraction means that the algorithm extracts cluster one by one. The assignment prototype algorithmis a typical clustering method for relational data. The membership degree of each object to each cluster is calculated directly from dissimilarities between objects. An entropy-based L1-regularized possibilistic assignment prototype algorithm is proposed first to induce belongingness for a membership grade. An algorithm of sequential cluster extraction based on the proposed method is constructed and the effectiveness of the proposed methods is shown through numerical examples.

  1. [1] A. K. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recognition Letters, Vol.31, No.8, pp. 651-666, 2010.
  2. [2] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum Press, New York, 1981.
  3. [3] S. Miyamoto and M. Mukaidono, “Fuzzy c-means as a regularization and maximum entropy approach,” Proc. of the 7th Int. Fuzzy Systems Association World Congress (IFSA’97), Vol.2, pp. 86-92, 1997.
  4. [4] S. Miyamoto, H. Ichihashi, and K. Honda, “Algorithms for Fuzzy Clustering,” Springer, Heidelberg, 2008.
  5. [5] R. Krishnapuram, J. M. Keller, “A possibilistic approach to clustering,” IEEE Trans. on Fuzzy Systems, Vol.1, No.2, pp. 98-110, 1993.
  6. [6] Y. Hamasuna, Y. Endo, and S. Miyamoto, “On Tolerant Fuzzy c-Means Clustering and Tolerant Possibilistic Clustering,” Soft Computing, Vol.14, No.5, pp. 487-494, 2010.3.
  7. [7] S. Miyamoto, Y. Kuroda, K. Arai, “Algorithms for Sequential Extraction of Clusters by Possibilistic Method and Comparison with Mountain Clustering,” J. of Advanced Computational Intelligence and Intelligent Informatics (JACIII), Vol.12, No.5, pp. 448-453, 2008.
  8. [8] R. N. Davé, “Characterization and detection of noise in clustering,” Pattern Recognition Letters, Vol.12, No.11, pp. 657-664, 1991.
  9. [9] R. N. Davé and R. Krishnapuram, “Robust clustering methods : A unified view,” IEEE Trans. on Fuzzy Systems, Vol.5, No.2, pp. 270-293, 1997.
  10. [10] R. N. Davé and S. Sen, “Robust Fuzzy Clustering of Relational Data,” IEEE Trans. on Fuzzy Systems, Vol.10, No.6, pp. 713-727, 2002.
  11. [11] R. R. Yager and D. P. Filev, “Approximate clustering via the mountain method,” IEEE Trans. on Systems, Man and Cybernetics, Vol.2, No.8, pp. 1279-1284, 1994.
  12. [12] R. Krishnapuram, A. Joshi, O. Nasraoui, and L. Yi, “Lowcomplexity fuzzy relational clustering algorithms for Web mining,” IEEE Trans. on Fuzzy Systems, Vol.9, No.4, pp. 595-607, 2001.
  13. [13] Y. Endo, “On Entropy Based Fuzzy Non Metric Model – Proposal, Kernelization and Pairwise Constraints –,” J. of Advanced Computational Intelligence and Intelligent Informatics (JACIII), Vol.16, No.1, pp. 169-173, 2012.
  14. [14] R. J. Hathaway, J.W. Davenport, J. C. Bezdek, “Relational Duals of the c-Means Clustering Algorithms,” Pattern Recognition, Vol.22, No.2, pp. 205-212, 1989.
  15. [15] R. J. Hathaway and J. C. Bezdek, “Nerf c-Means: Non-Euclidean Relational Fuzzy Clustering,” Pattern Recognition, Vol.27, No.3, pp. 429-437, 1994.
  16. [16] M. Roubens, “Pattern classification problems and fuzzy sets,” Fuzzy Sets and Systems, Vol.1, pp. 239-253, 1978.
  17. [17] E. Ruspini, “Numerical methods for fuzzy clustering,” Information Science, Vol.2, No.3, pp. 319-350, 1970.
  18. [18] M. P. Windham, “Numerical classification of proximity data with assignment measures,” J. of Classification, Vol.2, pp. 157-172, 1985.
  19. [19] E. J. Candes, M. B. Wakin, and S. Boyd, “Enhancing Sparsity by Reweighted l1 Minimization,” J. of Fourier Analysis and Applications, Vol.14, No.5, pp. 877-905, 2008.
  20. [20] K. Tsuda and T. Kudo, “Clustering graphs by weighted substructure mining,” Proc. of the 23rd Int. Conf. on Machine Learning (ICML), pp. 953-9960, 2006.
  21. [21] R. Inokuchi and S.Miyamoto, “Sparse Possibilistic Clustering with L1 Regularization,” Proc. of The 2007 IEEE Int. Conf on Granular Computing (GrC2007), pp. 442-445, 2007.
  22. [22] Y. Hamasuna and Y. Endo, “Sequential Extraction By Using Two Types of Crisp Possibilistic Clustering,” Proc. of the IEEE Int. Conf. on Systems, Man, and Cybernetics (IEEE SMC 2013), pp. 3505-3510, 2013.
  23. [23] C.-H Oh, K. Honda, and H. Ichihashi, “Fuzzy clustering for categorical multivariate data,” Proc. of Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pp. 2154-2159, 2001.
  24. [24] W. M. Rand., “Objective criteria for the evaluation of clustering methods,” J. of the American Statistical Association, Vol.66, No.336, pp. 846-850, 1971.

*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 Mar. 22, 2017