Concept Formation From Very Large Training Sets
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Learning and Knowledge Acquisition. Pages 479-480.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
This paper proposes an alternative to Ouinlan' s al&o rit hn for forr.ting classification trees fron large sets of exatlples. tty algorithn is gua ranteed to terninate. Qui nlan's a l gor ithm is usually faster.
- Everitt, ll S. _C_l_t~s-~e_r_ !~n_a_lxs_i_s_. : 1\einenann 1974.
- Kenc!all, r1. J•lultivariate -~n_a_lx~i_s_. Griffin &•c-o T9)T:-- Charles Quinlan, J.R. Discovering Rules hy Induction fron Large Collecti•o,;s--o-{ -r:~•.;-.,;p-ie-8; -pa-ges--16•3--"z"M: Ed-in-bu_r_r,"!l-lfn-rv•e-rsity rr-ess;-i979.
- Sturt, E. Computerized Construction in Fortran of a Discriminant Function for Categorical Data.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
CONCEPT FORI1ATION FROM VERY LARGE TRAINING SETS
Richard A. 0' l:~efe*
Departnent of Artificial Intelligence IJniversity of Edinburgh, I:dinhurgh
The input to a concept fornation algoritlm, then, i s
a set of attributes A , j = 1 ·· :1 j attribute j has values 1 ·. 1 A I j a set of exatlpl es E , i = 1 ·· tl i for each exanple , its classification C and its attributes C i!1 { 1. .1 A I} ij j in { 1, 2} i()
The training set can thus be repr esented by an N x (t!+l) int ege r natrix.
II. The Fonn of a Rule.
(Quinlan, 1979, Sturt, 198la) and this paper represent a discrimi:1ant function as a decision tree. The description here is slightly different t o make the algorithn clearer.
Each node of a decision t r ee has three labels: ~-Set(Node) is a set of exa~ples Class( Node) is enpty , 1, 2, or nixed Attrb(Node) is undefined, 1, ··· , or H and sone sons Son(Node,i) fori= l ·· IA Attrh(Node)
We use a decision tree to hy applying the following classify algorithm examples to its
a ttribute rneasurenents:
set Node = the root of the tree. while Class(Node) is mixed do set k = the value of attribute Attrb(tlode). set Node= Son(Node, k). od. if Class(Node) is enpty, fail. report Class(Node) as the c lassification .
(Quinlan, 1979) suggests returning an arbitrary classification when Class(Node) is empty. \./hether guessing is a good idea or not depends on what you want to do 11ith the rul e . Note that Class(Node) is redundant; it is empty, 1, 2, or nixed according as E-Set(Node) is empty, all class 1, all class 2 , or sone of each.
Abstract
This paper proposes an alternative to Ouinlan' s al&orit hn for forr.ting classification trees fron large sets of exatlples. tty algorithn is gua ranteed to terninate. Quinlan's a l gor ithm is usually faster .
I. The Nature of the Problem.
He have a popula tion of objects t~hich ·~e want to classify into two** gr oups . \./e have a set of attributes, each with a snall finite nunher of distinct values, and a set of examples t~hose attributes have been neasured and which have already been classifi ed . Our ~oal is to find a rul P. , based on these examples, which 1~e can use to classify other rnenhers of the population.
In general this will lead us to statistical nethods such as cluster analysis (Everitt, 1974, Kendall, 1975, Sturt, 198la, Sturt, 19!l lb). The large r our collection of e~anples, the nore likely it is that sone of ther:1 are r.lisclassified. ( Stur t, 198la) provides an excellent illustration of how inproving the fit of a rule to the training set (beyond a certain point) can nake it perform worse on the rest of the population.
Even so, there are interesting tasks ~~he re the donain is fonnal, and we can be sure that we have all the information we need and that our classif ications are correct. There are, however, interesting problems where the donain is formal r athe r than real, and we can be sure that all the relevant information is ava ilable and our classifications are correct. Chess positions and algebraic equations are two such donains.
*This work was supported Scholarship. Conputing was Dec-lO under grant GR/C/20826 by a done Cornrnom~ealth on the SERC
- **IDJ and my algorithm are both presented in t enns of two categories. The information heuristic generalises to any fixed nunber of categories, and so do the algorithms.
III. Building a Rule.
The algorithn for buildinr, a decision tree is the usual one:
create a tree with one i!ode . set E-Set(rlo<le) = the en tire training set. set Class( Node ) according to E-Set(Node) . set Attrb(:lode) = undefi necl,
while there is a ~lode with Class( tlode) and Attrb(~lode) = undef ined do mixed od. select an at tribute A not tested by any Gncestor of this Node . set Attrb(SubNode) = j . for k = l ·· I A I do od . c reG te a ne1-1 SubNode. add SuhNode as Son(Note, k). set F. -Se t(Suhllode) = the exa10ples in E- Se t(Node ) wltose A value is k . .i set Class(Suh:lode) fron E-Set(SubNode), set Attrh(SubNode) = undefined.
It is clear that thi s algorithn nust t e rmina te, that each nixed Node will finally be expanded, a nd that the order of expansion doesn't matter. The only roon for choice in this algorithm is thf' selection of an attribute . (Quinlan, [q79) sugr,ests using the infornation heuristic to c hoose an attribute. The entropy of a set of examples is defined as
where p1 (p2 ) is the proportion of exanples in class 1 (class 2)*. This is, roughly speaking, the nunber of bi'1ary t es ts needed to discriminate between the two classes . If we test attribute A ,
the ave rag e entropy of the subtrees is
The information heuristic is to select the attribute with ni nirnun II It is a heuristic
because we are assuning that the training set is typica l of the population . For 2 classes, H'
*this is where the generalisation to more than two categories is made.
candirlate att ributes , and I~' exanples , the 11 can he conputed in .i
The same space can he used for all attribute selections, since K' can never exceed its initial value.
IV. Quinlan's Iterative Dichotomiser
The algorithr.t rlescrihed above is normally r egarded as suitable only when all the exar,1ples (and the rule) can he fitted into main r.wnorv. Real problems sometimes don't fit . (Quinlan, 1979) userl chess end-games. His algori thn nakes concept fonnation practical for such problems. In outline , it ls
select a sanple of the training set · do od. infer a rule f ron the · sample . check the rul e against the whole traininr, set . exit when there are no nistakes. select a new sample from the old sample anrl the exceptions 1-1hich 1-1ere just discovererl.
In practice , IDJ works very well. Eac h iteration requires only one pass over the trainine set, and only changes data in main mer.wry. If Ill] terninates, it has indeed found a rule. 1\oi.Jeve r, Ill] needs _S.::n.!:. of the examples to be in nenory. A rul e which will fit in nenory nay be mi ssed because the exanples it is inferrahle fron will not fit. It woulrl be better if none of the examples had to be kept in netaory. The resampling me thod as describe in (Quinlan, 1979) may fail to r ealise that no possible sanple will work, anrl loop forver.
It would be acceptable if IDJ spotted that it couldn't cope and stopped. In practice a linit on the size of the tree or the n1rr1her of iterations is enough . l101~ever, there is no guarantee that a problem whi ch exceeds these limits rloesn't have a simple rule.
V. Rule Building is like Radix Sort.
Quinlan narle two contributions to concept forma tion: the infonnation heuristic, and his iterative sampling nethod. We can retain the fonner, and look for another way of handline large training sets,
The only difference between Formation algorithm and radix sort the Concept is that the sons of a node nay test different attributes, while in a left-to-right rac!ix sort they must test the same attribute. We ac!apt the data structure of rac!ix sort (a pair of randomly accessed files) to the abstract algorithn of Section 3. This is the only new ic!ea in this paper. As it keeps no examples in nenory, if it fails to find a rule, that is a r,uarantee that the information heuristic will never generate a rule that fits in nemory. As it adds no extra cho-fc-es to the abstract al gorithm, it must terminate.
\le hold the examples in two files, which are always pernutations of each other. An exanple set is represented hy a triple
(\.JhichFile, First, Next)
where the I.JhichFile field says which of the two files the set may be found in, First is the index of the first exat~ple in this set, and Next is the index of the first exataple following this set. An enpty set is represented by a triple with First = Nex t.
Selecting an Attrb for a Node pass over E-Set(Node), where we requires one calculate the counts from which the p are derived. He jkc
initialise the E-Sets for the sons as folloiJs: set (file1,First,Next) = E-Set(Node). set file2 = other file(file1). set first = First: fork= 1 ·· 1Attrb(Node)l do set E-Set(Son(Node,k)) (file2,first,first). set first = first+Nk. od.
where Hk, t.he nunber of examples with attribute value k, was determined in the first pass. We then make one more pass over the data, doing
for place First ·· Next-1 do read an example from file1(place). set k = the attribute value. set (file2,first,last) = E-Set(Son(Node,k)). write the example to file2(last). set E-Set(Son(Node,k)) = (file2,first,last+1). od.
As we permute the examples into the same range of r ecords, the E-Set labels of all existing nodes r emain valid.
11ain memory is needed to hold the counts for attribute selection (less than 500 cells for Quinlan's examples) anc! to hole! the rule. If the rule will not fit in nain memory, this algorithM will stop. I.Je are assured that the algorithm could not find any simpler rule.
7his algorithm nay take as many passes over the training set as there are levels in the decision tree, so the total cost of finc!ing a rule is proportional to the product
(depd1 of decision tree) x (total nunher of attribute values) x (nunbe r of exaMples in training set)
A pass of my algorithm reads a file twice and writes another once. A pass of ID3 reac!s the data file once. I.Jhen ID3 discovers a simple rule, it usually takes fewer passes than the nodified radix sort. Hut the point of the nodified r ac!ix sort is to cope with any sort of data. I doubt that it can he done nore_c_h.eaply.
@inproceedings{ijcai1983p118,
title = {Concept Formation From Very Large Training Sets},
author = {O'Keefe, Richard A.},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {479--480},
year = {1983},
note = {Learning and Knowledge Acquisition},
url = {https://ijcai.org/proceedings/1983/118},
}
TY - CPAPER TI - Concept Formation From Very Large Training Sets AU - O'Keefe, Richard A. T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 479 EP - 480 UR - https://ijcai.org/proceedings/1983/118 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards