On the well-behavedness of important attribute evaluation functions
Tapio Elomaa, Juho Rousu · 1998
Abstract. The class of well-behaved evaluation functions simplifies and makes efficient the handling of numerical attributes; for them it suffices to concentrate on the boundary points in searching for the optimal partition. This holds always for binary partitions and also for multisplits if only the function is cumulative in addition to being well-behaved. The class of well-behaved eval-uation functions is a proper superclass of convex evaluation functions. Thus, a large proportion of the most important attribute evaluation functions are well-behaved. This paper explores the extent and boundaries of well-behaved func-tions. In particular, we examine C4.5’s default attribute evaluation function gain ratio, which has been known to have problems with numerical attributes. We show that gain ratio is not convex, but is still well-behaved with respect to binary partitioning. However, it cannot handle higher arity partitioning well. Our empirical experiments show that a very simple cumulative rectification to the poor bias of information gain significantly outperforms gain ratio. 1