Constructing Nominal X-of-N Attributes

1 Introduction

A well-known elementary limitation of selective induc­ tion algorithms is that when task-supplied attributes are not adequate for describing hypotheses, their per­ formance in terms of prediction accuracy and/or theory complexity is poor. To overcome this limitation, con­ structive induction algorithms [Michalski, 1978] trans­ form the original instance space into a more adequate space by creating new attributes. By contrast to new attributes, the task-supplied attributes are called prim­ itive attributes.

On real-world application domains, domain experts use three different types of attributes: binary, nomi­ nal, and continuous-valued attributes, 1 to describe their examples and concepts. Different types of attributes have different advantages. For example, boolean at­ tributes are very simple; nominal and continuous-valued attributes are complex but more powerful for represent­ ing concepts. Note that attributes with more than two ordered discrete values can be specified as either nominal or continuous-valued attributes.

Most selective induction algorithms can accept at­ tributes of these three kinds. However, many existing constructive induction algorithms such as FRINGE [Pa­ gallo, 1990] and CITRE [Matheus and Rendell, 1989] construct new boolean attributes only by using logical operators such as /\ , ·, and V. ID2-of-3 [Murphy and Pazzani, 1991] creates, as new attributes, M-of-N repre­ sentations stating whether at least M of N conditions are true. M-of-N representations are also boolean attributes.

1 Some more sophisticated attributes such as structured attributes may be used, but here we talk about only these three most commonly used types of attributes.

A few systems such as BACON [Langley et al., 1987] and INDUCE [Michalski, 1978] explore methods to con­ struct new continuous-valued attributes using mathe­ matical operators such as · multiplication and division. Systems such as LMDT [Brodley and Utgoff, 1992] and Swap1 [Indurkhya and Weiss, 1991] construct linear dis­ criminant functions as new attributes. To the best of the author's knowledge, few researchers have developed con­ structive induction systems that construct new nominal attributes. One exception is that INDUCE, AQ17-DCI, and AQ17-MCI construct attribute counting attributes for rule learning [Michalski, 1978; Bloedorn et al., 1993]. They have ordered discrete values, but are used more like continuous-valued attributes rather than nominal at­ tributes (see section 6 for the differences from X-of-N) . Subsetting used by C4.5 groups discrete values of a single primitive nominal attribute to form a new test [Quinlan, 1993]. It can be thought as a method of constructing new nominal attributes. The author knows of no other decision tree algorithm that constructs new nominal at­ tributes.

In this paper, we propose a new constructive induc­ tion algorithm that constructs nominal attributes in the form of X-of-N representations. Our implemented sys­ tem, called XofN, uses decision trees as its theory de­ scription language. However, the idea of constructing new nominal attributes in the form of X-of-N represen­ tations is not limited to decision tree learning. It is not difficult to extend the idea to rule learning.

The following section describes X-of-N representations. Section 3 presents the approach to constructing new nominal attributes in the form of X-of-N representations and the constructive induction algorithm XofN. Section 4 reports experimental results of XofN on several artificial and real-world domains. Section 5 further discusses the X-of-N representations and the XofN algorithm. Section 6 discusses related work, and finally, the paper concludes with future work.

2 X-of-N Representation

In short, an X-<>f-N is a set containing one or more attribute-value pairs. For a given instance, the value of an X-<>f-N representation corresponds to the number of its attribute-value pairs that are true.

Definition 1 The X-of-N representation

Let { Ai II ~ i ~ MaxAtt} be the set of attributes of a domain, and for each Ai, {Vij II ~ j ~ MaxAttVali} be its value set, 2 where MaxAtt is the number of attributes, and MaxAttVali is the number of different values of Ai· An X-<>f-N representation is a set, denoted as:

X-<>f-{ AVk I AVk is an attribute-value pair denoted as "Ai =Vii", I~ k ~ N+, N ~ N+, I~ N ~ MaxAtt }, where N+ is the number of attribute-value pairs in the X-<>f-N representation, called the size of the X-<>f-N rep­ resentation, and N is the number of different attributes that appear in the X-<>f-N representation. The value of an X-<>f-N can be any number between 0 and N.

Given an instance, its value is X iff X of the AVk are true. An attribute-value pair AVk (Ai = Vij) is true for an instance iff attribute Ai of the instance has value Vi}.

Now, let us see an example of the X-<>f-N representa­ tion. The target concept of the Monks2 problem [Thrun et al., I99I] is "exactly two of the six attributes have their first value". It can be represented using a tree as in Figure I. The test at the root is a nominal X-<>f-N representation. Given instances (3, 2, I, 2, I, 2; +)and (2, I, I, I, I, I;-), its values are 2 and 5 respectively.

As a nominal attribute, the X-<>f-N representation has one main advantage over conjunction, disjunction, and M-of-N representations: stronger expressive power with­ out expanding the search space.

Many constructive induction algorithms such as FRINGE, CITRE, and CI [Zheng, I992] use 1\ and -, as constructive operators. They can only indirectly rep­ resent disjunctive concepts by using the negation of a conjunction. This makes it harder to construct new at­ tributes in the form of disjunctions, especially on do­ mains with primitive nominal attributes. Some algo­ rithms also have V as a constructive operator that makes it easier to create disjunctions. However, there are still some other concepts such as parity concepts, at­ least, exactly, at-most M-of-N concepts, and their possi­ ble combinations, that cannot be effectively represented. ID2-of-3 and MoN [Ting, I994] can only create at-least M-of-N representations. From the definition, we can see that X-<>f-N can directly represent all the following types of concepts.

2 At the moment, the X-<>f-N representation is defined on binary and nominal attributes. Continuous-valued at­ tributes are transformed into binary or nominal attributes by discretization.

• at-least M-of-N (as X-<>f-N in {M, M+I, ... , NP),
• exactly M-of-N (as X-<>f-N = M),
• at-most M-of-N (as X-<>f-N in {0, I, ... , M} ),
• parity (for even parity, as X-<>f-N in {0, 2, 4, ... } ),
• conjunction with internal disjunction (as X-<>f-N = N),
• disjunction with internal disjunction (as X-<>f-N in {I, 2, ... , N} ), and
• possible combinations of the above six types of con­ cepts.

Compared with M-of-N representations, the search space of X-<>f-N representations is smaller. This is be­ cause to create an M-of-N representation, we must first search for N+ attribute-value pairs and then search for a value M. When the number N is large, searching for a good value M can be expensive. However, to cre­ ate an X-<>f-N representation, we need only search for N+ attribute-value pairs. X-<>f-N representations have as large a search space as conjunction and disjunction representations.

One disadvantage of X-<>f-N representations is a "frag­ mentation" problem. When X-<>f-N representations with large Ns are used as tests for decision trees, they quickly split training sets into a large number of small subsets. This makes it harder to find good tests for the subtrees. However, this situation occurs only when training sets are relatively small and target concepts are very com­ plex in the sense that a few X-<>f-N representations are not enough. If target concepts are not complex or huge data sets are available, it is not a problem.

3 Constructing New Nominal Attributes for Decision Trees

Now, let us describe how to create and use X-<>f-N repre­ sentations in constructive induction. XofN uses the well­ known decision tree learning algorithm C4.5 [Quinlan, I993] as its selective induction component. It consists of a single process. As shown in Table I, XofN builds a decision tree by constructing, at each decision node, one new attribute based on primitive attributes using the lo­ cal training set. If the new attribute constructed at a node is better than all primitive attributes and previ­ ously created new attributes, XofN uses it as the test for the node; otherwise discards it and uses the best of the primitive attributes and previously constructed new at­ tributes. After growing a tree, XofN applies the pruning mechanism used by C4.5 [Quinlan, I993] .

Decision trees built by conventional tree learning al­ gorithms such as C4.5 use a test based on one attribute at each decision node. They are called univariate trees [Brodley and Utgoff, I992]. By contrast, XofN creates multivariate trees in which tests can refer to multiple attributes. We call them X-<>f-N trees as X-<>f-N repre­ sentations are used as multivariate tests. At each de­ cision node, besides creating one new X-<>f-N attribute, XofN considers reusing X-<>f-N attributes constructed pre­ viously for other decision nodes.

Function "Construct-X-<>f-N( )" in XofN constructs the best X-<>f-N representation using the local training set

3 This means that X-<>f-N equals M, or M+l, ... , or N.

XotN-Tree(Aprimitive> Aactive> Dtraining> C) Input: Aprimitive= a set of primitive attributes, A active= a set of primitive and X-<>f-N attributes for creating a test for the current decision node, initialized as Aprimitive> Dtraining= a set of training examples represented using Aactive> C: majority class at the parent node of the current node, initialized as the majority class in the whole training set. Output: a decision tree, Aactive= modified by adding one new X-<>f-N attribute constructed at this point. IF (Dtraining is empty) THEN RETURN a leaf node labeled with C ELSE { C := the majority class in Dtraining } IF (all examples in Dtraining have the same class C) THEN RETURN a leaf node labeled with C ELSE { Abest := Best-Attribute(Aactive> Dtraining) } Anew := Construct-X-of-N(Aprimitive> Dtraining) IF (Anew is better than Abest) THEN { Aactive := Aactive U {Anew} Abest := Anew } Rewrite Dtraining using Aactive ELSE Dispose of Anew Use Abest to partition Dtraining into n subsets DJ> D2, ... , Dn, one for each outcome of the test formed using A best RETURN the tree formed by a decision node with test Abest and subtrees XotN-Tree(Aprimitive> Aactive> DJ, C), XotN-Tree(Aprimitive> Aactive> D2, C), ... ' XotN-Tree(Aprimitive> Aactive> Dn, C)

at a decision node. It performs a simple greedy search in the instance space defined by primitive attributes. The starting point of the search is an empty X-of-N attribute. At each search step, it applies one of two operators: adding one possible attribute-value pair or deleting one possible attribute-value pair. To make the search efficient, if possible, 4 the deleting operator is ap­ plied first. During the search, XofN creates and keeps the best X-of-N representation for each possible size. Fi­ nally, function "Construct-X-of-N( )" returns the best of the X-of-N representations retained.

The information gain ratio 5 is used as the evaluation function for comparing and selecting new attributes. To avoid creating very complex new attributes that might over-fit the training data, another criterion is added, based on the coding cost of new attributes. By complex, we mean that an X-of-N representation has a large num­ ber of attribute-value pairs. 6 This kind of new attribute splits the training set into many subsets, so over-fitting is likely to occur. We use a similar coding method de­ scribed in [Quinlan and Rivest, 1989]. The coding cost of a new attribute includes two parts. One is for coding the new attribute itself. The other is for coding the ex­ ceptions when applying the new attribute as a classifier to the local training data at the current decision node. There is no weight added to either part. The newly con­ structed X-of-N representation (new-X-of-N) will replace the current best X-of-N (best-X-of-N) to become the best one only if the following condition is true.

4 1£ the size of an X-<>f-N representation is less than or equal to two, the deleting operator cannot be applied, because the best X-<>f-N of size one has already been found.

5 As used by C4.5.

(Gain-ratio(new-X-<>f-N) > Gain-ratio(best-X-<>f-N) 1\ Coding-cost(new-X-<>f-N) :::; Coding-cost(best-X-<>f-N)) V (Gain-ratio(new-X-<>f-N) = Gain-ratio(best-X-<>f-N) 1\ Coding-cost(new-X-<>f-N) < Coding-cost(best-X-<>f-N))

With this condition, the algorithm accepts a new at­ tribute with a higher gain ratio if its coding cost is not higher. The algorithm also accepts a new attribute with the same gain ratio but with a lower coding cost.

The stopping criterion for searching X-of-N represen­ tations is that the maximum possible size of X-of-N rep­ resentations is reached. To reduce the search time, an­ other restriction is applied: if no better new attribute has been found in five consecutive search steps/ the al­ gorithm terminates.

From the definition of X-of-N representations, it may seem that X-of-N representations can only be directly constructed from binary and nominal attributes. To deal with continuous-valued attributes, the XofN algorithm has a preprocessor that discretizes primitive continuous­ valued attributes. In the current implementation, we use a very simple method, although some better, but more complex, methods could be used. When there are some primitive continuous-valued attributes, XofN runs C4.5 on primitive attributes once and gets cut points for continuous-valued attributes. Then it discretizes the continuous-valued attributes using the cut points. The new attribute construction is carried out on the dis­ cretized attributes, binary attributes, and nominal at­ tributes.

4 Experiments

The most commonly used measures of the behavior of learning systems are prediction accuracy of learned the­ ories on test examples, theory complexity, and time com­ plexity. Theory complexity (abbreviated to complexity later in this paper) is the size of a learned theory. For a rule set, it is the number of all conditions in the rule set. For a tree, it is the sum of sizes of all nodes of the tree. The size of a leaf is 1. The size of a decision node is 1 for a univariate tree, and is the number of attribute-value pairs in the test of the node for a multivariate tree such as a tree built by XofN, ID2-of-3, or CI. Time complexity is the execution time needed by a learning algorithm. We focus here on the first two measures, accuracy and the­ ory complexity, because time results of other algorithms are not available or different computers and/or program­ ming languages are used. As far as the time complexity is concerned, XofN is much slower than the selective tree learning algorithm C4.5, but is still acceptable. For ex­ ample, on a DEC AXP 3000/500 workstation, the cpu time for XofN on the Cleveland Heart Disease domain (13 continuous-valued attributes, 2 classes, 303 cases) is 14.8 seconds, while it is 0.2 seconds for C4.5. On the Nettalk (Phoneme) domain (7 nominal attributes with 27 different values, 52 classes, 5438 cases), it is 9256.5 seconds for XofN and 4.3 seconds for C4.5.

6 We talk about the situation that most primitive at­ tributes in the X-<>f-N representation are different.

7 This default setting is arbitrary, but it can be changed. There is no special reason for selecting "five" .

To evaluate experimentally the effects of construct­ ing new nominal attributes in the form of X-of-N repre­ sentations, the results of XofN on a set of artificial and real-world domains are given. For comparison, we also give the results of some other constructive induction al­ gorithms: AQ17-HCI, AQ17-DCI, AQ17-MCI, ID2-of-3, and our algorithm CI [Zheng, 1992]. CI creates new attributes for decision trees by using conjunctions of conditions from production rules generated by C4.5rules [Quinlan, 1993]. The default option setting of CI is used here. To create a new attribute, CI chooses two con­ ditions, which are near the root of a tree, from a rule. With this setting, CI constructs new attributes based on two primitive attributes, and identifies relevant at­ tributes [Zheng, 1992]. The results of C4.5 are given for reference.

4.1 Experimental domains and methods

Three Monks domains [Thrun et al., 1991] are chosen because they are well-studied. There are published re­ sults for more than 25 different learning algorithms on them. They represent three different types of learning tasks with two binary and four nominal attributes. To make the Monks2 problem harder, especially for simple M-of-N learning methods, [Bloedorn et al., 1993] creates the "Noisy and Irrelevant Monks2" problem by adding 5% random classification noise (by inverting the classes) in the training set, and adding seven random five-value irrelevant attributes in both the training and test sets. There is no classification noise in the test set. On all these four domains, the fixed training set (a subset of the whole universe) and test set (the whole universe) are given by the problem designers. In our experiments, we follow this methodology and run experiments once on the given training set and test set for each domain.

8 There are fifty four English phonemes, but phonemes for "Word Boundary" and "Period" do not appear in the dataset.

9 There are six English stresses, but one for "Word Bound­ ary" does not appear in the dataset.

10 The number of all possible phoneme-stress pairs that ap­ pear in the dictionary of 20008 words is 163.

In addition, ten real-world domains are used, on which M-of-N like concepts are expected to be found [Spack­ man, 1988]. They are five medical domains (Cleve­ land Heart Disease, Hepatitis, Liver Disorders, Pima Indians Diabetes, and Wisconsin Breast Cancer), one molecular biology domain (Promoters), three linguis­ tics domains (Nettalk(Phoneme), Nettalk(Stress), and N ettalk(Letter)), and one game domain (Tic-Tac-Toe). All are from the UCI repository of machine learning databases [Murphy and Aha, 1994]. Table 2 gives a brief summary of the domains, including the data set size, the number of binary (B), nominal (N), continuous-valued (C), total (T) attributes, and the number of classes.

Phoneme and Stress are two basic subproblems of the Nettalk domain. Letter is a combination of them. Their tasks are mapping a letter in an English word into a phoneme, a stress, and a phoneme-stress pair respec­ tively. Following the method used in [Dietterich et al., 1990] we generate data sets by using a window of length 7, but use the 1000 most common English words.

On each real-world domain, a 10-fold cross-validation [Breiman et al., 1984] is conducted. In all the experi­ ments reported here, C4.5, CI, ID2-of-3, and XofN are run with their default option settings, and are run on the same partitions for all the domains. No parameter­ tuning is done here. Pruned trees are used for all the four algorithms.

4.2 Experimental results

This subsection compares the performance of the XofN algorithm with AQ17-HCI, AQ17-DCI, AQ17-MCI, CI, ID2-of-3, and C4.5.

The Monks domains

Table 3 summarizes the accuracy (Ace) and complexity (Com) of C4.5, AQ17-DCI, AQ17-HCI, CI, ID2-of-3, and XofN on three monks problems. The results of AQ17DCI and AQ17-HCI are from [Thrun et al., 1991]. The Table shows that only XofN solves all three problems with correct representations. As we expected, XofN finds a perfect representation of the target concept on Monks2.

To explore how noise and irrelevant attributes affect the performance of learning algorithms on the Monks2 domain, we give our results of C4.5, CI, ID2-of-3, and XofN, and the results of AQ17-DCI, AQ17-HCI, and AQ17-MCI from [Bloedorn et al., 1993] in Table 4. Only XofN learns the correct concept. Because of noise, the learned concept is not the perfect representation. In­ stead, XofN finds two new attributes X-of-{ A4 = 1} and X-of-{A1 = 1,A2 = 1,A3 = 1,As = 1, A6 = 1}. How­ ever, it is still the most concise representation among those learned by these algorithms except for C4.5 and Cl which return a tree having only one leaf. This illus­ trates that XofN can, to some extent, tolerate irrelevant attributes under conditions of noise, but this matter re­ mains to be explored further.

The real-world domains

To demonstrate that the XofN algorithm can work well on real-world domains as well as artificial domains, Tables 5 and 6 give the performance of XofN on ten real-world domains. It uses only C4.5, Cl, and ID2-of-3 as references, since very few directly comparable results of other constructive induction algorithms are available from publications. Each value given is the average of a ten-fold cross-validation. It is worth mentioning that LFC [Ragavan and Rendell, 1993] achieves higher pre­ diction accuracy (78.8%) than XofN on Pima Indians Diabetes domain (see section 6).

To compare accuracies of XofN, ID2-of-3, Cl, and C4.5, a two-tailed pairwise t-test is used. In Table 5, boldface indicates that Cl, ID2-of-3, or XofN is better than C4.5 with the significance level of above 95%, while * and # denote that XofN is better than ID2-of-3 and Cl respectively at the 95% significance level.

On seven out of ten domains, XofN achieves a signifi­ cant improvement on prediction accuracy over C4.5. On the other three domains, the differences are not signifi­ cant. The reason why XofN does not work well on these domains might be that there are no X.of-N representa­ tions in them, or there are some but XofN cannot find them due to the simple search strategy of the current implementation. Table 5 also shows that ID2-of-3 is sig­ nificantly better than C4.5 on four domains, and there is no significant difference on the other six domains. Cl is significantly better than C4.5 on six domains, signif­ icantly worse on the Nettalk(Letter) domain, and there is no significant difference on the other three domains. Compared to ID2-of-3, XofN is significantly better on four domains and there is no significant difference on the other six domains. Compared to Cl, XofN is signif­ icantly better on six domains. The differences on the other domains are not significant. 11 On seven out of ten domains, XofN achieves the highest accuracy among the four algorithms. As far as the complexity is con­ cerned, on most domains, XofN can learn a more concise tree than C4.5, especially on those domains where XofN achieves a higher accuracy. Compared to ID2-of-3, XofN learns smaller trees on seven out of ten domains.

5 Discussion

It has been found that XofN works quite well on a set of artificial and real-world domains. We expect that XofN can be applied to domains containing M-of-N concepts, such as biomedical domains [Spackman, 1988], linguistic domains, and domains containing parity concepts found for example in digital logic circuit design. To apply XofN to domains containing complex DNF concepts with long terms, some mechanisms are necessary to overcome the "fragmentation" problem. One approach is using subset­ ting of C4.5 [Quinlan, 1993]. Two other possible solu­ tions are using subranging and building decision graphs [Oliver et al., 1992] instead of decision trees. Subrang­ ing is similar to subsetting but also considers the order of the values of Xof-N representations. Subranging reduces the number of outcomes of an X-of-N test by combining some adjacent values of the X-of-N representation which are identical in terms of splitting data sets.

At the moment , XofN uses the cut points found by C4.5 to discretize primitive continuous-valued attributes.

11 0n the Diabetes domain, the significance level of the dif­ ference between CI and XofN is less than 95%, although the significance level of the difference between CI and C4.5 is above 95% and the average accuracy of C4.5 is higher than that of XofN. The reason is that the accuracy of XofN is higher than that of CI in some folds .

Other discretization methods that can be used are multi­ interval discretization methods [Catlett, 1991; Fayyad and Irani , 1993], supervised/unsupervised methods [Van de Merckt, 1993], and an entropy method [Ragavan and Rendell, 1993]. The current XofN discretizes continuous­ valued attributes statically in the sense that discretiza­ tion occurs before new attribute construction. An alter­ native is dynamic discretization, i.e. doing discretization while constructing new attributes. This method might be able to create good discretizations but with an in­ creased computational complexity.

Up to now, we have concentrated only on treat­ ing X-of-N representations as nominal attributes. Be­ cause their values are ordered, however, they can also be treated as continuous-valued attributes. Since the standard decision tree based learning algorithms trans­ form continuous-valued attributes into binary tests, the continuous-valued X-of-N should work well when the tar­ get concept requires X-of-N representations with only one cut point (M-of-N concepts) . However, on domains re­ quiring X-of-N representations with more than one cut point, the continuous-valued X-of-N has weaker expres­ sive power than the nominal X-of-N. For details on this issue, please see [Zheng, 1995].

6 Related Work

The closest related work is ID2-of-3 [Murphy and Paz­ zani, 1991]. It constructs new binary attributes in the form of M-of-N representations, while XofN constructs X-of-N representations. When building a decision tree, both ID2-of-3 and XofN construct one new attribute for each decision node using the local training set. Instead of building trees, MoN [Ting, 1994] creates M-of-N rules.

The production rule learning algorithms INDUCE [Michalski, 1978], AQ17-DCI, and AQ17-MCI [Bloedorn et al., 1993] use the counting operator 12 #VarEQ(x) to construct new attributes that count the number of at­ tributes in an instance which take the value x. For primitive boolean attributes, a boolean counting oper­ ator takes a vector of n boolean attributes (n ;::: 2) and counts the number of true values for an instance. Like X-of-Ns, new attributes constructed by these two opera­ tors have ordered discrete values. However, when used to generate production rules, they are treated more like continuous-valued attributes than nominal attributes. 13 The boolean counting attribute is a special case of the #VarEQ(x) attribute, while the #VarEQ(x) attribute is a special case of the X-of-N representation.

Most hypothesis-driven constructive induction al­ ~orithms such as FRINGE [Pagallo, 1990], CITRE lMatheus and Rendell, 1989], CI [Zheng, 1992], and AQ17-HCI [Wnek and Michalski, 1994] construct and select a set of new attributes based on the entire train­ ing set. This strategy has a shortcoming: new attributes that have high values of the evaluation function for the entire training set might have lower values than other unselected new attributes for a training subset after a part of a decision tree or a rule set has been created [Matheus and Rendell, 1989]. To overcome this, XofN constructs one new attribute using the local training set for each decision node. Therefore, the new attribute con­ structed by XofN at each decision node is the best one in XofN's search space in terms of the evaluation function. Another difference between XofN and these algorithms is that the latter interleave the theory learning phase and the process of building new attributes, and generate new attributes by analyzing the theory learned previ­ ously, while XofN has only one iteration and constructs new attributes by analyzing data.

12 In INDUCE, it is called #v_COND.

13 Generated rules have the form like (#VarEQ(1) >= 3) [Thrun et al., 1991, p11] .

Like ID2-of-3 and XofN, LFC [Raga van and Rendell, 1993] is also a data-driven constructive induction algo­ rithm that builds multivariate trees, but it uses negation and conjunction as constructive operators. LFC creates one conjunction for each decision node by using a di­ rected lookahead search. It achieved quite high predic­ tion accuracy on a couple of real-world domains such as Pima Indians Diabetes, but the problem is that it has a sensitive parameter "Lookahead Depth" which needs to be set when applied to a domain. Another multivariate tree learning algorithm is LMDT [Brodley and Utgoff, 1992] that generates a linear machine at each decision node when building a tree.

7 Conclusions and Future Work

Selective induction algorithms build their theories by selecting primitive attributes and are thus limited for hard tasks whose primitive attributes are not sufficient for, or directly relevant to, representing the theories. To overcome this problem, constructive induction algo­ rithms use various methods to generate powerful new attributes. However, most algorithms construct only bi­ nary attributes, while domain experts use binary, nom­ inal, and continuous-valued attributes to describe their tasks. From this point, we first proposed a rich knowl­ edge representation means, namely X-of-N representa­ tions, and then gave a new constructive induction algo­ rithm XofN. It generates X-of-N representations as new nominal attributes for decision trees using a data-driven constructive strategy.

The experiments illustrate the learning power of the XofN algorithm on some artificial and real-world do­ mains in terms of both higher prediction accuracy and lower theory complexity. In addition, it has been shown that XofN can achieve higher accuracy on some domains than other constructive induction algorithms that con­ struct, as new attributes, conjunctions or M-of-N repre­ sentations.

However, the current XofN is a preliminary imple­ mentation. A lot of research is worth doing and some is in progress. Examples are exploring more appro­ priate evaluation functions for comparing and selecting X-of-Ns, other search methods, other discretization meth­ ods for continuous-valued attributes, and implement­ ing subranging and decision graph algorithms. In addi­ tion, examining XofN's ability to tolerate missing values, noise, and irrelevant attributes should be interesting.

Acknowledgments

This research was partially supported by an ARC grant (to J.R. Quinlan) and by a research agreement with Digi­ tal Equipment Corporation. The author is supported by EMSS scholarship. The author appreciates the advice and suggestions J .R. Quinlan has given. Many thanks to J.R. Quinlan for providing C4.5, P.M. Murphy for sup­ plying the code ofiD2-of-3, also to K.M. Ting, A. Varsek, N. Indurkhya, P. Brazdil, P. Langley, M. Cameron-Jones, and three anonymous reviewers for comments that im­ prove the ideas and earlier drafts. Finally, P.M. Murphy and D. Aha are gratefully acknowledged for creating and managing the UCI Repository of ML databases.