International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 3, No. 1, 8 Feb. 2011
Cover page and Table of Contents: PDF (size: 221KB)
Clustering Belief Functions using Extended Agglomerative Algorithm
Full Text (PDF, 221KB), PP.31-37
Views: 0 Downloads: 0
Author(s)
Ying Peng
1,*
Huairong Shen
2
Zenghui Hu
3
Yongyi Ma
1
Index Terms
Belief functions, clustering, belief distance, agglomerative algorithm
Abstract
Clustering belief functions is not easy because of uncertainty and the unknown number of clusters. To overcome this problem, we extend agglomerative algorithm for clustering belief functions. By this extended algorithm, belief distance is taken as dissimilarity measure between two belief functions, and the complete-link algorithm is selected to calculate the dissimilarity between two clusters. Before every merging of two clusters, consistency test is executed. Only when the two clusters are consistent, they can merge, otherwise, dissimilarity between them is set to the largest value, which prevents them from merging and assists to determine the number of final clusters. Typical illustration shows same promising results. Firstly, the extended algorithm itself can determine the number of clusters instead of needing to set it in advance. Secondly, the extended algorithm can deal with belief functions with hidden conflict. At last, the algorithm extended is robust.
Cite This Paper
Ying Peng,Huairong Shen,Zenghui Hu,Yongyi Ma, "Clustering Belief Functions using Extended Agglomerative Algorithm", IJIGSP, vol.3, no.1, pp.31-37, 2011. DOI: 10.5815/ijigsp.2011.01.05
Reference
[1]A. P. Dempster, “Upper and lower probabilities induced by a multi-valued mapping,” Annals of Mathematical Statistics, vol. 38, pp. 325-339, 1967.
[2]G. Shafer, “A Mathematical Theory of Evidence,” Princeton: Princeton University Press, 1976.
[3]J. MacQueen, “Some methods for classification and analysis of multivariate observations,” In: Proc. of the Fifth Berkeley Symposium on Math, Stat. and Prob. vol. 1, 281-296, 1967.
[4]Guha,S., R. Rastogi, K. Shim, “CURE: An Efficient Clustering Algorithm for Large Databases,” In Proc. Of ACM SIGMOD Intl. Conf. on Management of Data, pp. 73-82, 1998.
[5]Karypis, G., E. Han, and V. Kumar, “Chameleon: A hierarchical clustering algorithm using dynamic modeling,” IEEE Computer, vol. 32, no. 8, pp. 68-75, 1999.
[6]J. Schubert, “Clustering decomposed belief functions using generalized weights of conflict,” International Journal of Approximate Reasoning, vol. 48, no. 2, pp. 466-480, 2008.
[7]S. B. Hariz, Z. Elouedi, K. Mellouli, “Clustering approach using belief function theory,” Lecture Notes in Computer Science, vol. 4183, no. 1, pp. 162-171, 2006.
[8]Ye Qing, Wu Xiaoping, Chen Zemao, “An approach for evidence clustering using generalized distance,” Journal of electronics (china), 2009, 26(1): 18-23.
[9]Z. Huang, “Extensions to the k_means algorithm for clustering large data sets with categorical values,” Data Mining Knowledge Discovery, vol. 2, no. 2, pp. 283-304, 1998.
[10]M. Daniel, “Associatively in combination of belief functions: a derivation of minC combination,” Soft Computing, vol. 7, no. 5, pp. 288-296, 2003.
[11]Ph. Smets, R. Kennes, “The transferable belief model,” Artificial Intelligence, vol. 66, no. 3, pp. 191-234, 1994.
[12]J. Dezert, F. Smarandache, “A new probabilistic transformation of belief mass assignment,” 11th International Conference on Information Fusion, pp. 1-8, 2008.
[13]A. L. Jousselme, Dominic G, Bosse E, “A new distance between two bodies of evidence,” Information Fusion, vol. 2, no. 2, pp. 91-111, 2001.
[14]R. Sibson, “SLINK: An optimally efficient algorithm for the single link cluster method,” The Computer Journal, vol. 16, no. 1, pp. 30-34, 1973.
[15]D. Defays, “An efficient algorithm for a complete link method,” The Computer Journal, vol. 20, no. 4, pp. 364-366, 1977.
[16]E. M. Voorhees, “Implementing agglomerative hierarchical clustering algorithms for use in document retrieval,” Information Process Manage, vol. 22, no. 6, pp. 465-476, 1986.