A Nonlinear Integral Defined On Partition Of Set And Its Application To Decision Tree Algorithm

Information fusion means to extract useful information from many different information sources, which can help us to make better decision. As a tool of information fusion, the integral plays an important role in many fields such as data mining, pattern recognition, and machine learning. Aggregation with different backgrounds in information fusion requires different integrals. Linear integral (Lebesgue-like integral) is valid for many linear models, but it fails to nonlinear models, while nonlinear integral can compensate for the deficiency of the linear integral, which can efficiently deal with many nonlinear models. By now, there have already been developed many kinds of non-linear integrals, but the existing integrals are all defined on a set (or a subset), there has not been integral defined on a partition of a set yet. Motivated ID3 algorithm generating decision trees, this paper proposes a nonlinear integral of a function with respect to a non-negative set function on a partition, presents its basic properties, and gives its computing in special case. Using the new integral in decision tree, the paper provides the conclusion that the sum of the weighted entropy of the union of several subsets is not less than the sum of the weighted entropy of a single subset. So, this paper provides a mathematically theoretic basis for the ID3 algorithm.