source: orange/Orange/doc/reference/RuleLearner.htm @ 9671:a7b056375472

Revision 9671:a7b056375472, 15.7 KB checked in by anze <anze.staric@…>, 2 years ago (diff)

Moved orange to Orange (part 2)

Line 
1<!-- saved from url=(0022)http://internet.e-mail -->
2<!-- saved from url=(0022)http://internet.e-mail -->
3<html>
4<HEAD>
5<LINK REL=StyleSheet HREF="style.css" TYPE="text/css">
6<LINK REL=StyleSheet HREF="style-print.css" TYPE="text/css" MEDIA=print>
7</HEAD>
8
9<BODY>
10<h1>Learning Rules</h1>
11<index name="classifiers+rule learning">
12<index name="classifiers+CN2">
13
14<p> This document describes main classes used for supervised learning of if-then rules. First two classes, <A href=#rulelearner">RuleLearner</A>  and <A href="#rulebeamfinder">RuleBeamFinder</A> , implement learning of rules by following separate-and-conquer strategy. This strategy consists of several replaceable functions, which are, in our classes, presented as components. As usual for all Orange classes, these components can be easily rewritten (in Python) and can replace the default ones. As there are many components here and to make the presentation of components a bit easier, the description of classes will start with the pseudo code of implemented algorithm to show where functions (components) do actually take place. After the algorithm, the actual description of individual components is given. The third class, class <A href="#rule">Rule</A>, is a class used to represent a single rule. <A href="#examples">Examples</A> at the end are used to illustrate how these three classes can be used to implement different ways of learning rules. </p>
15
16<hr>
17
18<A name="rulelearner"></A>
19<H2>RuleLearner class</H2>
20
21<p><INDEX name="classes/RuleLearner">RuleLearner is a class for inductive learning rules from data. The algorithm follows separate-and-conquer strategy, which has its origins in the AQ family of algorithms (Fuernkranz J.; Separate-and-Conquer Rule Learning, Artificial Intelligence Review 13, 3-54, 1999). Basically, such algorithms search for the "best" possible rule in learning examples, remove covered data from learning examples (separate) and repeat the process (conquers) on the remaining examples. Follows the algorithm of separate-and-conquer rule learning:
22
23<br><br>
24<u>RuleLearner's call function</u>:<br>
25<PRE class="code">
26def __call__(self,examples,weightID=0):
27    ruleList = orange.RuleList()
28    allExamples = orange.ExampleTable(examples)
29    while not self.<b>dataStopping</b>(examples,weightID,self.targetClass):
30        newRule = self.<b>ruleFinder</b>(examples,weightID,self.targetClass,self.baseRules)
31        if self.<b>ruleStopping</b>(ruleList,newRule,examples,weightID):
32            break
33        examples,weightID = self.<b>coverAndRemove</b>(newRule,examples,weightID,self.targetClass)
34        ruleList.append(newRule)
35    return orange.RuleClassifier_firstRule(rules=ruleList,examples=allExamples)
36</PRE>
37<br>
38
39Main functions of this algorithm are <b>dataStopping</b>, <b>ruleFinder</b>, <b>coverAndRemove</b>, and <b>ruleStopping</b>. Each of those functions corresponds to an callable attribute in the class and a component (callable class or function) needs to be set in order that method can work. By default, components that simulate CN2 algorithm will be used, but user can change it to any arbitrary function (component) that accepts and returns appropriate parameters. The instructions and requirements for writting such components is given at the description of attributes.
40
41</p>
42<P class=section>Methods</P>
43<DL class=attributes>
44As ruleLearner is derived from orange Learner class, it has the classical call method that accepts examples and, if available, id number of weight attribute.
45</DL>
46<P class=section>Attributes</P>
47<DL class=attributes>
48
49<DT>dataStopping</DT>
50<DD>This callable attribute accepts a component that checks from the examples whether there will be benefit from further learning, so basically checks if there is enough data to continue learning. The default component returns true if the set of examples is empty or, if targetClass is given, returns true if number of instances with given class is zero.
51<br><br>
52<table border="0">
53  <tr>
54    <td> Default component: </td>
55    <td> orange.RuleDataStoppingCriteria_NoPositives</td>
56  </tr>
57  <tr>
58    <td> Derived from: </td>
59    <td> orange.RuleDataStoppingCriteria </td>
60  </tr>
61  <tr>
62    <td> Format: </td>
63    <td> condition = dataStopping(examples,weightID,targetclass) </td>
64  </tr>
65</table>
66
67</DD>
68
69<DT>ruleStopping </DT>
70<DD>ruleStopping is a component that decides from the last rule learned, if it is worthwhile to use this rule and learn more rules. By default, this attribute is set to None - meaning that all rules are accepted.
71
72<br><br>
73<table border="0">
74  <tr>
75    <td> Default component: </td>
76    <td> None</td>
77  </tr>
78  <tr>
79    <td> Derived from: </td>
80    <td> orange.RuleStoppingCriteria </td>
81  </tr>
82  <tr>
83    <td> Format: </td>
84    <td> condition = ruleStopping(ruleList,rule,examples,weight) </td>
85  </tr>
86</table>
87
88
89</DD>
90
91<DT>coverAndRemove </DT>
92<DD>This component removes examples covered by the rule and returns remaining examples. If the targetClass is not given (targetClass = -1), default component does exactly this, and, if target class is given, removes only covered examples that are in the target class.
93
94<br><br>
95<table border="0">
96  <tr>
97    <td> Default component: </td>
98    <td> orange.RuleCovererAndRemover_Default</td>
99  </tr>
100  <tr>
101    <td> Derived from: </td>
102    <td> orange.RuleCovererAndRemover </td>
103  </tr>
104  <tr>
105    <td> Format: </td>
106    <td> (newExamples,newWeightID) = coverAndRemove(rule,examples,weightID,targetClass) </td>
107  </tr>
108</table>
109
110</DD>
111
112<DT>ruleFinder</DT>
113<DD>RuleFinder learns a single rule from examples. By default, RuleBeamFinder class is used, which is explained later on.
114<br><br>
115<table border="0">
116  <tr>
117    <td> Default component: </td>
118    <td> orange.RuleBeamFinder</td>
119  </tr>
120  <tr>
121    <td> Derived from: </td>
122    <td> orange.RuleFinder </td>
123  </tr>
124  <tr>
125    <td> Format: </td>
126    <td> rule = ruleFinder(examples,weightID,targetClass,baseRules) </td>
127  </tr>
128</table>
129</DD>
130
131<DT>storeExamples</DT>
132<DD>Set this to 1 if you want the rules to have stored examples.
133</DD>
134
135<DT>targetClass</DT>
136<DD>Learn rules with a specific target class
137</DD>
138
139<DT>baseRules</DT>
140<DD>Base rules are rules that we would like to use in ruleFinder to constrain the learning space. You can see it in the ruleFinder format specification that it takes also a set of base rules as a parameter. If attribute baseRules is not set, it will be set to a set containing only empty rule.
141</DD>
142</DL>
143
144<A name="rulebeamfinder"></A>
145<H2>RuleBeamFinder class</H2>
146
147<p><INDEX name="classes/RuleBeamFinder">RuleBeamFinder class performs beam search for the best rule. This is the default class used in RuleLearner to find the best rule. Pseudo code of the algorithm is shown here:
148<br><br>
149<u>RuleBeamFinder's call function</u>:<br>
150<PRE class = "code">
151    def __call__(self,examples,weightID,targetClass,baseRules):
152        prior = orange.Distribution(examples.domain.classVar,examples,weightID)
153        rulesStar,bestRule = self.<b>initializer</b>(examples,weightID,targetClass,baseRules,self.evaluator,prior)
154        # compute quality of rules in RuleStar and bestRule
155        ...
156        while len(rulesStar)>0:
157            candidates, rulesStar = self.<b>candidateSelector</b>(rulesStar,examples,weightID)
158            for cand in candidates:
159                newRules = self.<b>refiner</b>(cand,examples,weightID,targetClass)
160                for newRule in newRules:
161                    if self.<b>ruleStoppingValidator</b>(newRule,examples,weightID,targetClass,cand.classDistribution)                              newRule.quality = self.<b>evaluator</b>(newRule,examples,weightID,targetClass,prior)
162                        rulesStar.append(newRule)
163                            if self.<b>validator</b>(newRule,examples,weightID,targetClass,prior) and   newRule.quality>bestRule.quality:
164                                bestRule = newRule
165            rulesStar = self.<b>ruleFilter</b>(rulesStar,examples,weightID)
166        return bestRule
167</PRE>
168<br>
169As you can see, there are several exchangeable components. Each of those is explained in the attributes section.
170
171 </p>
172
173<P class=section>Attributes</P>
174<DL class=attributes>
175
176<DT>initializer</DT>
177<DD>This component is used to initialize rulesStar and for selecting the initial best rule. By default, baseRules are returned as starting rulesSet and the best from baseRules is set as bestRule.
178If baseRules are not set, this class will return rulesStar with rule that covers all examples (has no selectors) and this rule will be also used as bestRule.
179<br><br>
180<table border="0">
181  <tr>
182    <td> Default class: </td>
183    <td> orange.RuleBeamInitializer_Default </td>
184  </tr>
185  <tr>
186    <td> Derived from: </td>
187    <td> orange.RuleBeamInitializer </td>
188  </tr>
189  <tr>
190    <td> Format: </td>
191    <td> (ruleList,bestRule) = initializer(examples,weigthID,targetClass,baseRules,evaluator,prior) </td>
192  </tr>
193</table>
194</DD>
195
196
197<DT>candidateSelector</DT>
198<DD>Separates a subset from the current rulesStar and returns it. These rules will be used in the next specification step. Default component takes all rules in rulesStar.
199<br><br>
200<table border="0">
201  <tr>
202    <td> Default class: </td>
203    <td> orange.RuleBeamCandidateSelector_TakeAll</td>
204  </tr>
205  <tr>
206    <td> Derived from: </td>
207    <td> orange.RuleBeamCandidateSelector </td>
208  </tr>
209  <tr>
210    <td> Format: </td>
211    <td> (candidates,ruleList) = candidateSelector(ruleList,examples,weigthID) </td>
212  </tr>
213</table>
214
215</DD>
216
217<DT>refiner</DT>
218<DD>Refines given rule. New rule should cover a strict subset of examples covered by given rule. Default component adds a a conjunctive selector (attribute = att_value) to selectors present in the rule.
219<br><br>
220<table border="0">
221  <tr>
222    <td> Default class: </td>
223    <td> orange.RuleBeamRefiner_Selector</td>
224  </tr>
225  <tr>
226    <td> Derived from: </td>
227    <td> orange.RuleBeamRefiner </td>
228  </tr>
229  <tr>
230    <td> Format: </td>
231    <td> newRule = candidateSelector(rule,examples,weigthID,targetClass) </td>
232  </tr>
233</table>
234</DD>
235
236<DT>ruleFilter</DT>
237<DD>Filters rules to keep beam relatively small to constrain search complexity. By default, it takes five best rules.
238<br><br>
239<table border="0">
240  <tr>
241    <td> Default class: </td>
242    <td> orange.RuleBeamFilter_Width(m=5)</td>
243  </tr>
244  <tr>
245    <td> Derived from: </td>
246    <td> orange.RuleBeamFilter </td>
247  </tr>
248  <tr>
249    <td> Format: </td>
250    <td> rules = ruleFilter(rules,examples,weigthID) </td>
251  </tr>
252</table>
253</DD>
254
255 <DT>evaluator</DT>
256<DD>Evaluates rule from covered examples. By default, entropy is used as a measure.
257<br><br>
258<table border="0">
259  <tr>
260    <td> Default class: </td>
261    <td> orange.RuleEvaluator_Entropy</td>
262  </tr>
263  <tr>
264    <td> Derived from: </td>
265    <td> orange.RuleEvaluator </td>
266  </tr>
267  <tr>
268    <td> Format: </td>
269    <td> quality = evaluator(rule,examples,weigthID,targetClass,prior) </td>
270  </tr>
271</table>
272</DD>
273
274 <DT>ruleStoppingValidator</DT>
275<DD>Validates whether the rule is specialized enough comparing it to its parent. The parent of a rule is a rule from which this rule was specialized.
276<br><br>
277<table border="0">
278  <tr>
279    <td> Default class: </td>
280    <td> None</td>
281  </tr>
282  <tr>
283    <td> Derived from: </td>
284    <td> orange.RuleValidator </td>
285  </tr>
286  <tr>
287    <td> Format: </td>
288    <td> ruleStoppingValidator(rule,examples,weigthID,targetClass,priorOfParentRule) </td>
289  </tr>
290</table>
291
292</DD>
293 <DT>validator</DT>
294<DD>Validates, whether the rule is good enough to be considered as the best rule, i.e. the rule is good enough to be returned by rulefinder. By default, likelihood ratio statistics is used that gives an estimate if rule is statistically better than the default rule.
295<br><br>
296<table border="0">
297  <tr>
298    <td> Default class: </td>
299    <td> orange.RuleValidator_LRS(alpha=1.0)</td>
300  </tr>
301  <tr>
302    <td> Derived from: </td>
303    <td> orange.RuleValidator </td>
304  </tr>
305  <tr>
306    <td> Format: </td>
307    <td> ruleGoodEnough = validator(rule,examples,weigthID,targetClass,prior) </td>
308  </tr>
309</table>
310
311</DD>
312
313</DL>
314
315
316<P class=section>Methods</P>
317<DL class=attributes>
318
319<DT>call operator(examples, weight, targetClass, baseRules);</DT>
320<DD>Learns a rule from examples</DD>
321
322</DL>
323
324<A name="rule"></A>
325<H2>Rule class</H2>
326
327<p><INDEX name="classes/Rule">Rule class is the base class for presentation of a single rule.</p>
328
329<P class=section>Attributes</P>
330<DL class=attributes>
331
332<DT>filter</DT>
333<DD>This attribute specifies the contents of the rule; it is the basis of the Rule class. Class Filter_values is set as a default, which can, together with default methods, be replaced with any class inherited from Filter.
334</DD>
335
336<DT>classifier</DT>
337<DD>Each rule can be used as a classical Orange like classificator. By default, Default classifier is used.</DD>
338
339<DT>learner</DT>
340<DD>Learner to be used for making a classifier. By default, MajorityLearner is used.</DD>
341
342<DT>classDistribution</DT>
343<DD>Distribution of class in examples covered by this rule.</DD>
344
345<DT>examples</DT>
346<DD>Covered examples by this rule.</DD>
347
348<DT>weightID</DT>
349<DD>Weight for the stored examples.</DD>
350
351<DT>quality</DT>
352<DD>Quality of the rule. Rules with higher quality are better.</DD>
353
354<DT>complexity</DT>
355<DD>Complexity of the rule. Complexity is used for selecting between rules with equal quality, where rules with lower complexity are preferred. Currently, complexity corresponds to the number of selectors in rule (actually to number of conditions in filter), but, obviously, any other measure can be applied.
356</DD>
357
358</DL>
359
360
361<P class=section>Methods</P>
362<DL class=attributes>
363
364<DT>__init__(self)</DT>
365<DD>Creates and empty rule. </DD>
366
367
368<DT>operator (example)</DT>
369<DD>Returns True if Example if covered by rule and 0 otherwise. </DD>
370
371<DT>operator (examples, ref=True, negate=False)</DT>
372<DD>Filters examples using filter object. Returns examples that are covered by the rule. </DD>
373
374<DT>filterAndStore(examples, weightID=0, targetClass=-1)</DT>
375<DD>This method filters passed examples and stores them in the attribute examples. It also computes classDistribution, sets weight of stored examples and creates a new classifier using learner attribute. </DD>
376</DL>
377
378<A name="examples"></A>
379<H2>Examples</H2>
380
381<p> This last section is used to give some examples how we can replace the default components. All examples are from <a href="testRulelearner.py">testRuleLearner.py</a> (uses <a href="titanic.tab">titanic.tab</a>). </p>
382
383<xmp type="code">learner = orange.RuleLearner()
384cl = learner(data)
385
386# print rules
387for r in cl.rules:
388    print orngCN2.ruleToString(r)
389</xmp>
390In the first row we initialize the learner, in the second run learner on data that returns a rule classifier, and in the last two lines, the induced rules are printed on screen (uses orngCN2 module). This learner uses only default components, but we wish to change that now. The following two lines, for instance,
391<xmp type="code">learner.ruleFinder = orange.RuleBeamFinder()
392learner.ruleFinder.evaluator = orngCN2.mEstimate(m=50)
393
394# print rules
395cl = learner(data)
396for r in cl.rules:
397    print orngCN2.ruleToString(r)
398</xmp>
399would change the evaluation function of learner to m-estimate of probability with m set to 50. This evaluation function is implemented in orngCN2 module (orngCN2.py). Notice that we first need to set the ruleFinder component, because the default components are not constructed when the learner is constructed, but only when we run it on data. At that time, the algorithm checks which components are necessary and sets defaults. Similarly, when the learner finishes, it destructs all default components.
400
401Continuing with our example, assume that we wish to set a different validation function and a different bean width. This is simply written as:
402<xmp type="code">learner.ruleFinder.ruleStoppingValidator = orange.RuleValidator_LRS(alpha=0.01,min_coverage=10,max_rule_complexity = 2)
403learner.ruleFinder.ruleFilter = orange.RuleBeamFilter_Width(width = 50)
404
405# print rules
406cl = learner(data)
407for r in cl.rules:
408    print orngCN2.ruleToString(r)
409</xmp>
410
411
Note: See TracBrowser for help on using the repository browser.