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
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.

Cite this article as:
Yukihiro Hamasuna and Yasunori Endo, “On Cluster Extraction from Relational Data Using L1-Regularized Possibilistic Assignment Prototype Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.19, No.1, pp. 23-28, 2015.
Data files:
  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, Opera.

Last updated on Jan. 19, 2021