An Appraisal of a Decision Tree Approach to Image Classification

An Appr ai sal of a Dec i sion Tree approach t o Image Classification .*

B. A. Shepherd.

Machine Intell igence Research Uni t, Un iver sity of Edi nbu rgh , U. K.

to produce solutions wi th a high degree of human intelligibility and has been extended at MIRU (Blake . 82> to handle both numerical and non­ numerical attributes . This extended form is ca lled ACLS ( Analogue Concept Learn ing System>. The work described here seeks to evaluate the use of ACLS-generated decision trees in image classification problems . An industrial vision problem was selected as test domain . Th is problem has no obvious ' best ' solution and much effort has been devoted to performing a realistic appraisal of the ACLS solution by making a comprehens ive set of comparisons with the performances of alternative classifiers .

~ The vision problem domain .

A sufficiently demanding vision problem has been posed by Rowntree of York concerning the identification of Black Mag ic chocolates at thei r factory . In th is problem the 12 different types of chocolate have on ly one stable posi t ion but can take any orientation in the horizontal plane . Classification is to be done from a plan view image of individual chocolates d igitised to an accuracy of 96X96 pixels . The problem is further defined by making the classification based on shape information < ie . silhouettes> on ly .

L ~ ~ algorithm .

ACLS inputs examples of the pattern classes . Each example consists of an attribute vec tor paired with a class value . A decision tree is generated from a collection of examples <train ing set> by recursively sub- dividing th is collection into smaller subsets according to the values of the attributes . The 103 entropy-based cost measure is applied to each subset to determine which attribute wi ll create the 'best' further sub-d ivision and a node representing the attribute used is added to the tree . The form of the node will depend on whether the attribute is numerical <called integer> or non-numerical <called log ical> . Nodes for integer attributes are binary and test the attribute against a single threshold value . In contrast nodes testing logical attributes have an output branch associated with each value the attribute may take . Sub-dividing the training set conti nues until each subset contains examples of one c lass only . and the corresponding terminal node < leafl is labeled with that class value . If the tree generated is binary then all leaves wi ll be labeled but only wi th class values for which train ing examples exist and hence It will discriminate only between these particular classes . The multi - branch ing trees produced using logical attributes may contain many unlabeled leaves <called null > . These leaves may

ABSTRACT

This paper investigates the applicability to a shape-recognition problem of a concept learning algorithm which generates decision rules from examples. A comprehensive analysis of this a lgorithm applied to an industrial vision problem is described . This problem has no obvious ·best' solution and much effort has been devoted to performing a realistic appraisal of the algorithm by making a detailed set of comparisons with the performances of appropriate alternative classifiers . Results presented show the algorithm to be comparable in performance with the alternative classifiers but superior in terms of both the cost of making a class ification and also the intelligibility of

the solution .

L Introduction .

A non parametric <or "distribution-free"> solution to a pattern recognition problem is one designed only from information contained In representative examples of the pattern classes . This approach is popular in practical problems where detailed statistical information is rarely available . A promising nonparametrlc solution to classification problems is to produce decision rules which can be expressed in the form of decision trees . Some algorithms for generating s·uch decision trees from examples have been suggested < eg Henrichon & Fu 69 . Seithi & Sarvaraydu 82> but have concentrated on classification using only numerical measurements of the patterns . A similar limitation ar ises with 'statistical ' classifiers . these are well suited to patterns contain ing noise (random variation> but poor at dealing with structural information . The algorithm described here has the ability to use both numerical and non-numerical variables . Its origins can be summarised .

An investigation by Hunt < 66> Into Inductive reasoning produced an algorithm called CLS <Concept Learning System> for generating decision trees from examples defined in terms of non­ numeric attributes. Each attribute has a predefined set of outcomes which need not represent values along a physical dimension or have any ordering . 103 <Iterative Dlchotomiser 3. Quinlan 79) an algorithm based on CLS has been extensively tested on the problem of classifying positions as won or lost In chess endgames <Shapiro & Niblett. 82> . 103 has displayed many advantages over alternative solutions . It can often be used In such a way as correspond to attribute vectors not belonging to any of the pattern classes or they may have arisen only because of the absence of an appropriate training example .

·This research is supported by a grant from the SERC for co-operative research with GEC Hirst Research Centre. Wembley . Principal Investigator: Professor Donald Michie.

.1.,_ Objectives of the Investigation.

The advantages of a decision rule in tree form can be summarised :

(a) Generating the tree performs an ·attribute selection' function allowing each class to be described by the most appropriate subset of attributes. Thus the set of attributes supplied to the learning phase can be selected without regard to minimising its size : reduction of size can be left to the algorithm itself.

• ( bl . When making a classification only attributes occurring on the decision path need be computed .
• (c) Decision trees lend themselves to humanly understandable solutions .
• (d) ACLS trees in particular can handle both integer and logical attributes <see note 1) .

In order to measure these advantages a detailed experimental comparison was made with two alternative classifiers: the K Nearest Neighbour decision rule < K-NN> <Fix & Hodges. 1951. 52) and the minimum distance classifier <MDC> <see for eg . Devijver & Kittler. 82) . A third alternative means of classification was also undertaken and consisted of showing the chocolate images to a series of human subjects. It was hoped that these latter results would provide a useful measurement to help judge the machine performances .

Note 1: A full investigation into the advantages and scope of logical attributes is unrealistic with this domain . However a c lass of logical attributes which can be investigated is that generated by discretising the integer attributes . If these discrete values can be given conceptual names eg . small. large then the intelligibility of the tree may benefit.

.2.,_ Experimental procedure .

Over 300 boolean Images were created. with approximately equal numbers from each chocolate class . For each Image the nine numeric shape descriptors summarised in fig . 1 were computed . These attributes were chosen mainly because of their ease to compute . They were not tailored to the problem neither were they expected to totally solve it. The resulting attribute vectors were paired with the correct class values and used as examples . Testing the classifiers was achieved by dividing the total set of examples into various subsets and using each in turn as training and test sets . In order to pursue the use of logical attributes the integer attributes were divided into labeled subranges . and the experiments using the ACLS classifier repeated.

Compactness Circularity Rectangularity1 Rectangularity2 Aspect ratio 1 Aspect rat io 2 Elongatedness norm. area norm . perim.

area+circle area with same perim area+circle area with same diam area+area of best-fit rectangle area+area of computed rectangle length+width max . length+min . length length+'stralghtened out ' width area+normalising area

per lm . + normalising perim .

.El9..:...l Numerical ~ attributes.

.§..,_ ~ .£JJQ discussion .

.§.....1 Classification success ~

The results obtained using the integer attributes are summarised in fig . 2. In order to both train and test the classifiers the maximum training set size was limited to 216 examples (leaving 108 test examples) . All performances improve as the training set size increases to this value. It seems likely that these performances will improve further <to some steady value> given larger training sets . No major differences among the best performances of the three algorithms are evident from these results which are substantially better than those obtained from human subjects trained on similar material <see later) . Results for the smaller training set sizes show the K-NN algorithm to have a higher performance . Note that the K-NN method < K equal to one) and the MDC method are algorithmically identical when the training set contains only one example of each class .

~ Average success ~

<Note: Each figure is the average of 3 individual successful to total classifications made for a given

· estimators . Each of these consists of the ratio of training-test example set combination>

Logical attributes were investigated in two ways :

<a> Expressing each integer attribute as a multivalued logical attribute:

This gave inferior results which worsened as N the number of values in each attribute was increased . A larger value of N produced an increase in the number of valid combinations of the attributes which consequently required a gteater number of training examples in order to be labeled correctly . This Is an illustration of a problem often encountered in pattern recognition whenever the dimensionality of the 'measurement' space Is Increased . In this problem . increasing N caused the fixed size training sets to become less representative resulting in an Increasing number of unlabelled <null> leaves appearing In the trees generated. The actual decrease in success rate arose because many of these null decisions occurred during the testing phase. The potential advantage of the multi-branching trees to distinguish non-classes from classes is not exercised here since all test classifications were made using only class examples. Hence all the

null classifications which occurred were erroneous .

< bl Expressing each integer attribute as a series of boolean logical attributes:

The Idea here was to use logical attributes and also generate binary trees . Each outcome of the multi-valued logical attributes was used as a separate boolean attribute taking the values true or false. For example if the attribute 'area' was given the outcomes 'small' and 'large' then the boolean attributes derived in this way would be : ' is-area­ small?' and 'is-area-large?'. Trees generated in this way were were found to perform nearly as well

as those using integer attributes .

~ ~ of classification .

A comparison of costs is shown in fig 3 . The memory requirements of both the MDC and ACLS seem very economical. With regard to minimising the computation required ACLS seems far superior to the two alternatives . Only half of the total attribute set Is computed for any particular classification and the extra processi.ng required after this is insignificant.

~ Intelligibility .9.f !!:!§ solutions .

Two factors which effect the intelligibility of a decison tree are its size and the intelligibility of the attributes used . The smallest binary tree which can solve this problem must have 11 branch nodes + 12 leaves = 23 nodes. but this would require ideal attributes. Those used in this investigation possess a high degree of variation <see next section> and so the measured average tree size <best performance> of 54 nodes is not excessive. However inspection of the trees shows them to be too large and scattered to be easily comprehended . Replacing each Integer attribute by one many-valued logical attribute can help to conceptually simplify the tree . At each node all possible outcomes of the tested attribute are explained and each attribute only occurs once on any decision path . This compares favourably with the binary trees where the same attribute can be scattered intermittently along any path . This option has its limitations : an excessive number of outcomes in each logical attribute may also result in large and complicated trees . The lower observed performance of the multi-branching trees would seem to suggest a ' trade-off' between performance and any gain in intelligibility they may provide . However the size of the training set must also be taken Into account here since a larger training set may well raise the performance to an acceptable level <see 6 . 1 . q) .

~ Success with !!:!§ chocolate domain.

The major cause of classification error arose from a large within-class variation in the images which can be split Into manufacturing and Image capture variations An analysis of the attribute values shows a large component of the latter arises from lens distortion effects. Experiments were performed < Mowforth. 82> · to test human subjects on the same images as used in the above experiments . The average success rate measured was only 62% but increased to 90% when using images created using a planar lens <no lens distortion> . This confirms the lens as a source of error and also reflects well on the machine success rates . A performance of 100% is probably unattainable using silhouette images alone. The experimental confusion matrices show a strong confusion between two of the shapes <both squares> and this Is confirmed by inspection of the chocolates themselves . A grey level measurement may be necessary to discriminate these particular chocolates .

L... Conclusions and further work.

In this domain the decision trees generated by ACLS have performed comparably with those of practical alternative classifiers and all compare favourably with the performance of humans. In addition ACLS trees have displayed advantages regarding both the cost of making a classification and the intelligibility of the solution . Comparisons amongst the various trees have indicated that binary trees may perform better than the logical multi-branching trees. although the latter may have a certain advantage regard ing intelligibility. Current work Includes increasing the conceptual power of the trees . One approach <Shapiro & Niblett 82> makes large trees more understandable by structuring them into a hierarchy of sub-trees each representing an identifiable sub-problem . The experiments are also being re-run using images with no lens distortion and this together with a small extension to the attribute set is expected to achieve a practically acceptable success rate in this problem domain .

Future work will apply this algorithm to a more structurally complex problem domain .