Selection Initial modes for Belief K-modes Method

Authors: Sarra Ben Hariz, Zied Elouedi, Khaled Mellouli

Abstract:

The belief K-modes method (BKM) approach is a new clustering technique handling uncertainty in the attribute values of objects in both the cluster construction task and the classification one. Like the standard version of this method, the BKM results depend on the chosen initial modes. So, one selection method of initial modes is developed, in this paper, aiming at improving the performances of the BKM approach. Experiments with several sets of real data show that by considered the developed selection initial modes method, the clustering algorithm produces more accurate results.

Keywords: Clustering, Uncertainty, Belief function theory, Belief K-modes Method, Initial modes selection.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328728

References:

[1] J.A. Barnett, Calculating Dempster-Shafer plausibility, IEEE Transactions on Pattern Analysis and Machine Intelligence, 13 (6), 1991, pp.599-602.
[2] M. Bauer, Approximation algorithms and decision making in the Dempster-Shafer theory of evidence - an empirical study, Int.J.Approx.Reason. 17 (2-3), 1997, pp.217.
[3] S. Ben Hariz, Z. Elouedi, and K. Mellouli, Clustering Approach using Belief Function Theory, Proceeding of the Twelfth International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA2006), 2006, pp.162-171.
[4] E. Bosse, D. Grenier and A.L. Jousselme, A new distance between two bodies of evidence, In Information Fusion 2, 2001, pp.91-101.
[5] P.S. Bradley, U.M. Fayyad, Refining Initial Points for K-Means Clustering, Proceedings of the 15th International Conference on Machine Learning (ICML98), San Francisco, Morgan Kaufmann, 1998.
[6] T. Denoeux, A k-nearest neighbor classification rule based on Dempster- Shafer theory, IEEE Transactions on Systems, Man and Cybernetics, 25 (5), 1995, pp.804-813.
[7] T. Denoeux and M. Skarstein-Bjanger, Induction of decision trees from partially classified data, Proceedings of SMC-2000,, Nashville, TN., 2000, pp.2923-2928.
[8] T. Denoeux and M. Masson, Clustering of proximity data using belief functions, Proceedings of IPMU-2002, Annecy, France., Vol I, 2002, pp.609-616.
[9] T. Denoeux andM. Masson, EVCLUS: Evidential Clustering of Proximity Data, IEEE Transactions on Systems, Man and Cybernetics, 34 (1), 2003, pp.95-109.
[10] T. Denoeux andM.Masson, Clustering Interval-valued Data using Belief Functions, Pattern Recognition Letters, 25 (2), 2004, pp.163-171.
[11] Z. Elouedi, K. Mellouli and P. Smets, Belief Decision trees: Theoretical foundations, International Journal of Approximat Reasoning, 28 (2-3), 2001, pp.91-124.
[12] Z. Elouedi, K. Mellouli and P. Smets, Assessing sensor reliability for multisensor data fusion within the transferable belief model, IEEE Trans.Syst.Man Cybern, 34 (1), 2004, pp.782-787.
[13] D. Fixen and R.P.S. Mahler, The modified Dempster-Shafer approach to classification, IEEE Trans.Syst.Man Cybern, 27 (1), 1997, pp.96-104.
[14] Z. Huang, Extensions to the k-means algorithm for clustering large data sets with categorical values, Data Mining Knowl.Discov., 2 (2), 1998, pp.283-304.
[15] Z. Huang and M.K. Ng, A fuzzy K-modes algorithm for clustering categorical data. IEEE Transaction on Fuzzy Systems,7(4), 1999, pp.446- 452.
[16] A.K. Jain and R.C. Dubes, Algorithms for clustering data, Prentice-Hall, Englewood cliffs, NJ, 1988, pp.197-198.
[17] D-W. Kim and K.H. Lee, Fuzzy clustering of categorical data using fuzzy centroids. Pattern Recognition Letters, 25, 2004 , pp.1263-1271.
[18] S.S. Khan, A. Ahmad, Cluster center initialization algorithm for Kmeans clustering. Pattern Recognition Letters, 25 (11), 2004, 1293-1302.
[19] S.S. Khan, Dr.S. Kant, Computation of Initial Modes for K-modes Clustering Algorithm using Evidence Accumulation. IJCAI-07, 2007, 2784-2789.
[20] MP. Murphy and D.W. Aha, Uci repository databases.http://www.ics.uci.edu/mlearn, 1996.
[21] J. MacQueen, Some methods for classification and analysis of multivariate observations, Proceeding of the Fifth Berkeley Symposium on Math, Stat and Prob., 1, 1967, pp.281-296.
[22] J. Schubert, Clustering belief functions based on attracting and conflicting metalevel evidence, Intelligent Systems for Information Processing: From Representation to Applications, 2003.
[23] G. Shafer, A mathematical theory of evidence, Princeton Univ. Press. Princeton, NJ.30, 1976.
[24] P. Smets and R. Kennes, The transferable belief model, Artificial Intelligence, 66, 1994, pp.191-234.
[25] P. Smets, The combination of evidence in the transferable belief model, IEEE-Pattern analysis and Machine Intelligence, 12, 1990, pp.447-458.
[26] P. Smets, Belief functions: The disjunctive rule of combination and the generalized bayesian theorem, International Journal of Approximate Reasoning, 9, 1993, pp.1-35.
[27] P. Smets, The transferable belief model for quantified belief representation, In D.M. Gabbay and P. Smets (Eds.), Handbook of defeasible reasoning and uncertainty management systems, 1, 1998, pp.267-301.
[28] Y. Sun, Q. Zhu, Z. Chen: An Iterative initial points refinement algorithm for categorical data clustering, Pattern Recognition Letters, 23, 875-884, 2002.
[29] B. Tessem, Approximations for efficient computation in the theory of evidence, Artif.Intell, 61 (2), 1993, pp.315-329.
[30] L.M. Zouhal and T. Doeneux, An evidence-theory k-NN rule with parameter optimization, IEEE Trans.Syst.Man Cybern. 28 (2), 1998, pp.263-271.