Paper:

# On Cluster Extraction from Relational Data Using *L*_{1}-Regularized Possibilistic Assignment Prototype Algorithm

_{1}

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

*L*-regularization, sequential cluster extraction, relational data

_{1}This paper proposes entropy-based *L _{1}*-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

*L*-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] J. C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms,” Plenum Press, New York, 1981.
- [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] S. Miyamoto, H. Ichihashi, and K. Honda, “Algorithms for Fuzzy Clustering,” Springer, Heidelberg, 2008.
- [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] 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] 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] R. N. Davé, “Characterization and detection of noise in clustering,” Pattern Recognition Letters, Vol.12, No.11, pp. 657-664, 1991.
- [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] 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] 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] 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] 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] 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] 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] M. Roubens, “Pattern classification problems and fuzzy sets,” Fuzzy Sets and Systems, Vol.1, pp. 239-253, 1978.
- [17] E. Ruspini, “Numerical methods for fuzzy clustering,” Information Science, Vol.2, No.3, pp. 319-350, 1970.
- [18] M. P. Windham, “Numerical classification of proximity data with assignment measures,” J. of Classification, Vol.2, pp. 157-172, 1985.
- [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] 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] 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] 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] 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] 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.

*L*-Regularized Possibilistic Assignment Prototype Algorithm,”

_{1}*J. Adv. Comput. Intell. Intell. Inform.*, Vol.19, No.1, pp. 23-28, 2015

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.19, No.1, pp. 23-28, 2015