Title :
An algorithm for designing a pattern classifier by using MDL criterion
Author :
Tsuchiya, Hideaki ; Itoh, Shuichi ; Hashimo, Takeshi
Author_Institution :
Dept. of Electron. Eng., Univ. of Electro-Commun., Tokyo, Japan
Abstract :
The algorithm for designing a pattern classifier, which uses MDL criterion and a binary data structure, is proposed. The algorithm gives a partitioning of the space of the K-dimensional attribute and gives an estimated probability model for this partitioning. The volume of bins in this partitioning is asymptotically upper bounded by 𝒪((log N/N) K(K+2/)) for large N in probability, where N is the length of training sequence. The redundancy of the code length and the divergence of the estimated model are asymptotically upper bounded by 𝒪(K(log N/N)2(K+2/)). The classification error is asymptotically upper bounded by 𝒪(K1/2(log N/N) 1(K+2/))
Keywords :
binary sequences; codes; estimation theory; pattern classification; probability; tree data structures; K-dimensional attribute; MDL criterion; algorithm; binary tree data structure; classification error; code length; estimated probability model; partitioning; pattern classifier; probability; redundancy; training sequence length; upper bound; Algorithm design and analysis; Binary trees; Costs; Data engineering; Data structures; Decision trees; Design engineering; Partitioning algorithms; Probability distribution; Redundancy;
Conference_Titel :
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location :
Whistler, BC
Print_ISBN :
0-7803-2453-6
DOI :
10.1109/ISIT.1995.535746
