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
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.
-  A. K. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recognition Letters, Vol.31, No.8, pp. 651-666, 2010.
-  J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum Press, New York, 1981.
-  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.
-  S. Miyamoto, H. Ichihashi, and K. Honda, “Algorithms for Fuzzy Clustering,” Springer, Heidelberg, 2008.
-  R. Krishnapuram, J. M. Keller, “A possibilistic approach to clustering,” IEEE Trans. on Fuzzy Systems, Vol.1, No.2, pp. 98-110, 1993.
-  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.
-  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.
-  R. N. Davé, “Characterization and detection of noise in clustering,” Pattern Recognition Letters, Vol.12, No.11, pp. 657-664, 1991.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  M. Roubens, “Pattern classification problems and fuzzy sets,” Fuzzy Sets and Systems, Vol.1, pp. 239-253, 1978.
-  E. Ruspini, “Numerical methods for fuzzy clustering,” Information Science, Vol.2, No.3, pp. 319-350, 1970.
-  M. P. Windham, “Numerical classification of proximity data with assignment measures,” J. of Classification, Vol.2, pp. 157-172, 1985.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.