Patent ID: 6101275
Filing Date: 2000-08-08
Classification: G06K

Abstract:
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for finding a best test for a nominal attribute for generating a binary decision tree to classify a plurality of values of nominal attribute, the machine receiving a plurality of values of said nominal attribute, the method comprising:(1) reducing a number of distinct values of said plurality of said values based on whether there are identical class probabilities among the values of the nominal attribute;(2) ordering the values of the nominal attribute by one of an ascending value and a descending value of a principal component score computed from a weighted variance matrix; and(3) evaluating only subset tests of consecutively larger subsets of values in said order for impurity computations to classify said values of nominal attribute, and establishing a variant in which said impurity computations are compared using subset tests both for the consecutively larger subsets of values and for subsets obtained by exchanging adjacent elements between each subset and its complement.