決定木学習 - Hosei

1 ( ) 3 DNF . red circle pos red circle A blue B; red square B green C; red triangle C color red blue green shape circle square triangle neg pos pos neg neg color red blue green shape circle square triangle B C A B C 4 ( ) ( length < 3 length 3) ( ) 5 NP (1979) ID3 6 S ( , ) S p1 p0 (0 log(0)=0) (p1=p0= ), C )(log)(log)

2 (020121ppppSEntropy = = =ciiippSEntropy12)(log)(7 ( ) F Sv S v F : )()(),()(vFValuesvvSEntropySSSE ntropyFSGain = Qs: Color: Weight: Rubber: small , - medium? - large? L8-src // compute information content, // given # of pos and neg examples double computeInfo(int p, int n) { double total = p + n ; double pos = p / total ; double neg = n / total; double temp; if ((p ==0) || (n == 0)) { temp = ; } else { temp = ( * (pos * (pos) (2))) - (neg * (neg) (2)) ; } return temp ; } double computeRemainder(Variable variable, Vector examples) { int positive[] = new int[ ()]; int negative[] = new int[ ()]; int index = ; int classIndex = ; double sum = 0 ; double numValues = (); double numRecs = () ; for( int i=0 ; i < numValues ; i++) { String value = (i); Enumeration enum = (); while ( ()) { String record[] = (String[]) ().)}}}

3 // get next record if (record[index].equals(value)) { if (record[classIndex].equals("yes")) { positive[i]++; } else { negative[i]++; } } } /* endwhile */ double weight = (positive[i]+negative[i]) / numRecs; double myrem = weight * computeInfo(positive[i], negative[i]); sum = sum + myrem ; } /* endfor */ return sum ; } // return the variable with most gain Variable chooseVariable(Hashtable variables, Vector examples) { Enumeration enum = () ; double gain = , bestGain = ; Variable best = null ; int counts[] ; counts = getCounts(examples) ; int pos = counts[0] ; int neg = counts[1] ; double info = computeInfo(pos, neg); while( ()) { Variable tempVar = (Variable) () ; gain = info - computeRemainder(tempVar, examples); if (gain > bestGain) { bestGain = gain ; best = tempVar.

4 } } return best; // } C: Huang teaching AI L8 -src runtime load: basketball Algorithm-> set splitting function: gain 14 1960 CLS) 70 ID3 , ID3 CART ( ) 1980 1993 Weka Java J48 15 ( m, n ) i m-i ( n). m n F1 Fm m n )(12 == minmOni16 ( ) ID4 ID5 (1) L9-src 12/3 TA how to implement forward chaining based decision making for proving Bob runs faster then 18 Bob is a buffalo | 1.

5 Buffalo(Bob) Pat is a pig | 2. Pig(Pat) Buffaloes outrun pigs | 3. x, y Buffalo(x) Pig(y) Faster(x,y) ---------------------------------------- ---------------------------------------- -------------------- Bob outruns Pat ---------------------------------------- ---------------------------------------- ------------------- Apply (3) to 1 And 2 | 4. Buffalo(Bob) Pig(Pat) Apply (8) to 3 {x/Bob, y/Pat} | 5. Buffalo(Bob) Pig(Pat) Faster(Bob,Pat) Apply (1) to 4 And 5 | 6. Faster(Bob,Pat) Exercise next week: 1. , . 2. ( ) 19 Output.