source: orange/Orange/classification/rules.py @ 10407:87f1e8bc140a

Revision 10407:87f1e8bc140a, 87.3 KB checked in by janezd <janez.demsar@…>, 2 years ago (diff)

Fixed a bug in classification.rules.rules_equal

Line 
1import random
2import math
3import operator
4import numpy
5
6import Orange
7import Orange.core
8
9RuleClassifier = Orange.core.RuleClassifier
10RuleClassifier_firstRule = Orange.core.RuleClassifier_firstRule
11RuleClassifier_logit = Orange.core.RuleClassifier_logit
12RuleLearner = Orange.core.RuleLearner
13Rule = Orange.core.Rule
14RuleList = Orange.core.RuleList
15
16BeamCandidateSelector = Orange.core.RuleBeamCandidateSelector
17BeamCandidateSelector_TakeAll = Orange.core.RuleBeamCandidateSelector_TakeAll
18BeamFilter = Orange.core.RuleBeamFilter
19BeamFilter_Width = Orange.core.RuleBeamFilter_Width
20BeamInitializer = Orange.core.RuleBeamInitializer
21BeamInitializer_Default = Orange.core.RuleBeamInitializer_Default
22BeamRefiner = Orange.core.RuleBeamRefiner
23BeamRefiner_Selector = Orange.core.RuleBeamRefiner_Selector
24ClassifierConstructor = Orange.core.RuleClassifierConstructor
25CovererAndRemover = Orange.core.RuleCovererAndRemover
26CovererAndRemover_Default = Orange.core.RuleCovererAndRemover_Default
27DataStoppingCriteria = Orange.core.RuleDataStoppingCriteria
28DataStoppingCriteria_NoPositives = Orange.core.RuleDataStoppingCriteria_NoPositives
29Evaluator = Orange.core.RuleEvaluator
30Evaluator_Entropy = Orange.core.RuleEvaluator_Entropy
31Evaluator_LRS = Orange.core.RuleEvaluator_LRS
32Evaluator_Laplace = Orange.core.RuleEvaluator_Laplace
33Evaluator_mEVC = Orange.core.RuleEvaluator_mEVC
34Finder = Orange.core.RuleFinder
35BeamFinder = Orange.core.RuleBeamFinder
36StoppingCriteria = Orange.core.RuleStoppingCriteria
37StoppingCriteria_NegativeDistribution = Orange.core.RuleStoppingCriteria_NegativeDistribution
38Validator = Orange.core.RuleValidator
39Validator_LRS = Orange.core.RuleValidator_LRS
40   
41from Orange.misc import deprecated_keywords
42from Orange.misc import deprecated_members
43
44
45class ConvertClass:
46    """ Converting class variables into dichotomous class variable. """
47    def __init__(self, classAtt, classValue, newClassAtt):
48        self.classAtt = classAtt
49        self.classValue = classValue
50        self.newClassAtt = newClassAtt
51
52    def __call__(self, example, returnWhat):
53        if example[self.classAtt] == self.classValue:
54            return Orange.data.Value(self.newClassAtt, self.classValue + "_")
55        else:
56            return Orange.data.Value(self.newClassAtt, "not " + self.classValue)
57
58
59def create_dichotomous_class(domain, att, value, negate, removeAtt=None):
60    # create new variable
61    newClass = Orange.feature.Discrete(att.name + "_", values=[str(value) + "_", "not " + str(value)])
62    positive = Orange.data.Value(newClass, str(value) + "_")
63    negative = Orange.data.Value(newClass, "not " + str(value))
64    newClass.getValueFrom = ConvertClass(att, str(value), newClass)
65
66    att = [a for a in domain.attributes]
67    newDomain = Orange.data.Domain(att + [newClass])
68    newDomain.addmetas(domain.getmetas())
69    if negate == 1:
70        return (newDomain, negative)
71    else:
72        return (newDomain, positive)
73
74
75class LaplaceEvaluator(Evaluator):
76    """
77    Laplace's rule of succession.
78    """
79    def __call__(self, rule, data, weight_id, target_class, apriori):
80        if not rule.class_distribution:
81            return 0.
82        sumDist = rule.class_distribution.cases
83        if not sumDist or (target_class > -1 and not rule.class_distribution[target_class]):
84            return 0.
85        # get distribution
86        if target_class > -1:
87            return (rule.class_distribution[target_class] + 1) / (sumDist + 2)
88        else:
89            return (max(rule.class_distribution) + 1) / (sumDist + len(data.domain.class_var.values))
90
91LaplaceEvaluator = deprecated_members({"weightID": "weight_id",
92                                       "targetClass": "target_class"})(LaplaceEvaluator)
93
94
95class WRACCEvaluator(Evaluator):
96    """
97    Weighted relative accuracy.
98    """
99    def __call__(self, rule, data, weight_id, target_class, apriori):
100        if not rule.class_distribution:
101            return 0.
102        sumDist = rule.class_distribution.cases
103        if not sumDist or (target_class > -1 and not rule.class_distribution[target_class]):
104            return 0.
105        # get distribution
106        if target_class > -1:
107            pRule = rule.class_distribution[target_class] / apriori[target_class]
108            pTruePositive = rule.class_distribution[target_class] / sumDist
109            pClass = apriori[target_class] / apriori.cases
110        else:
111            pRule = sumDist / apriori.cases
112            pTruePositive = max(rule.class_distribution) / sumDist
113            pClass = apriori[rule.class_distribution.modus()] / sum(apriori)
114        if pTruePositive > pClass:
115            return pRule * (pTruePositive - pClass)
116        else: return (pTruePositive - pClass) / max(pRule, 1e-6)
117
118WRACCEvaluator = deprecated_members({"weightID": "weight_id",
119                                     "targetClass": "target_class"})(WRACCEvaluator)
120
121
122class MEstimateEvaluator(Evaluator):
123    """
124    Rule evaluator using m-estimate of probability rule evaluation function.
125   
126    :param m: m-value for m-estimate
127    :type m: int
128   
129    """
130    def __init__(self, m=2):
131        self.m = m
132    def __call__(self, rule, data, weight_id, target_class, apriori):
133        if not rule.class_distribution:
134            return 0.
135        sumDist = rule.class_distribution.abs
136        if self.m == 0 and not sumDist:
137            return 0.
138        # get distribution
139        if target_class > -1:
140            p = rule.class_distribution[target_class] + self.m * apriori[target_class] / apriori.abs
141            p = p / (rule.class_distribution.abs + self.m)
142        else:
143            p = max(rule.class_distribution) + self.m * apriori[rule.\
144                class_distribution.modus()] / apriori.abs
145            p = p / (rule.class_distribution.abs + self.m)
146        return p
147
148MEstimateEvaluator = deprecated_members({"weightID": "weight_id",
149                                         "targetClass": "target_class"})(MEstimateEvaluator)
150
151
152class CN2Learner(RuleLearner):
153    """
154    Classical CN2 inducer (Clark and Niblett; 1988) that constructs a
155    set of ordered rules. Constructor returns either an instance of
156    :obj:`CN2Learner` or, if training data is provided, a
157    :obj:`CN2Classifier`.
158   
159    :param evaluator: an object that evaluates a rule from instances.
160        By default, entropy is used as a measure.
161    :type evaluator: :class:`~Orange.classification.rules.Evaluator`
162    :param beam_width: width of the search beam.
163    :type beam_width: int
164    :param alpha: significance level of the likelihood ratio statistics
165        to determine whether rule is better than the default rule.
166    :type alpha: float
167
168    """
169
170    def __new__(cls, instances=None, weight_id=0, **kwargs):
171        self = RuleLearner.__new__(cls, **kwargs)
172        if instances is not None:
173            self.__init__(**kwargs)
174            return self.__call__(instances, weight_id)
175        else:
176            return self
177
178    def __init__(self, evaluator=Evaluator_Entropy(), beam_width=5,
179        alpha=1.0, **kwds):
180        self.__dict__.update(kwds)
181        self.rule_finder = BeamFinder()
182        self.rule_finder.ruleFilter = BeamFilter_Width(width=beam_width)
183        self.rule_finder.evaluator = evaluator
184        self.rule_finder.validator = Validator_LRS(alpha=alpha)
185
186    def __call__(self, instances, weight=0):
187        supervisedClassCheck(instances)
188
189        cl = RuleLearner.__call__(self, instances, weight)
190        rules = cl.rules
191        return CN2Classifier(rules, instances, weight)
192
193CN2Learner = deprecated_members({"beamWidth": "beam_width",
194                     "ruleFinder": "rule_finder",
195                     "ruleStopping": "rule_stopping",
196                     "dataStopping": "data_stopping",
197                     "coverAndRemove": "cover_and_remove",
198                     "storeInstances": "store_instances",
199                     "targetClass": "target_class",
200                     "baseRules": "base_rules",
201                     "weightID": "weight_id"})(CN2Learner)
202
203
204class CN2Classifier(RuleClassifier):
205    """
206    Classical CN2 classifier (Clark and Niblett; 1988) that predicts a
207    class from an ordered list of rules. The classifier is usually
208    constructed by :class:`~Orange.classification.rules.CN2Learner`.
209   
210    :param rules: induced rules
211    :type rules: :class:`~Orange.classification.rules.List`
212   
213    :param instances: stored training data instances
214    :type instances: :class:`Orange.data.Table`
215   
216    :param weight_id: ID of the weight meta-attribute.
217    :type weight_id: int
218
219    """
220
221    @deprecated_keywords({"examples": "instances"})
222    def __init__(self, rules=None, instances=None, weight_id=0, **argkw):
223        self.rules = rules
224        self.examples = instances
225        self.weight_id = weight_id
226        self.class_var = None if instances is None else instances.domain.class_var
227        self.__dict__.update(argkw)
228        if instances is not None:
229            self.prior = Orange.statistics.distribution.Distribution(instances.domain.class_var, instances)
230
231    def __call__(self, instance, result_type=Orange.classification.Classifier.GetValue):
232        """
233        :param instance: instance to be classified.
234        :type instance: :class:`Orange.data.Instance`
235       
236        :param result_type: :class:`Orange.classification.Classifier.GetValue` or \
237              :class:`Orange.classification.Classifier.GetProbabilities` or
238              :class:`Orange.classification.Classifier.GetBoth`
239       
240        :rtype: :class:`Orange.data.Value`,
241              :class:`Orange.statistics.distribution.Distribution` or a tuple with both
242        """
243        classifier = None
244        for r in self.rules:
245         #   r.filter.domain = instance.domain
246            if r(instance) and r.classifier:
247                classifier = r.classifier
248                classifier.defaultDistribution = r.class_distribution
249                break
250        if not classifier:
251            classifier = Orange.classification.ConstantClassifier(instance.domain.class_var, \
252                self.prior.modus())
253            classifier.defaultDistribution = self.prior
254
255        classifier.defaultDistribution.normalize()
256        if result_type == Orange.classification.Classifier.GetValue:
257          return classifier(instance)
258        if result_type == Orange.classification.Classifier.GetProbabilities:
259          return classifier.default_distribution
260        return (classifier(instance), classifier.default_distribution)
261
262    def __str__(self):
263        ret_str = rule_to_string(self.rules[0]) + " " + str(self.rules[0].\
264            class_distribution) + "\n"
265        for r in self.rules[1:]:
266            ret_str += "ELSE " + rule_to_string(r) + " " + str(r.class_distribution) + "\n"
267        return ret_str
268
269CN2Classifier = deprecated_members({"resultType": "result_type",
270                                    "beamWidth": "beam_width"})(CN2Classifier)
271
272
273class CN2UnorderedLearner(RuleLearner):
274    """
275    Unordered CN2 (Clark and Boswell; 1991) induces a set of unordered
276    rules. Learning rules is quite similar to learning in classical
277    CN2, where the process of learning of rules is separated to
278    learning rules for each class.
279
280    Constructor returns either an instance of
281    :obj:`CN2UnorderedLearner` or, if training data is provided, a
282    :obj:`CN2UnorderedClassifier`.
283   
284    :param evaluator: an object that evaluates a rule from covered instances.
285        By default, Laplace's rule of succession is used as a measure.
286    :type evaluator: :class:`~Orange.classification.rules.Evaluator`
287    :param beam_width: width of the search beam.
288    :type beam_width: int
289    :param alpha: significance level of the likelihood ratio statistics to
290        determine whether rule is better than the default rule.
291    :type alpha: float
292    """
293    def __new__(cls, instances=None, weight_id=0, **kwargs):
294        self = RuleLearner.__new__(cls, **kwargs)
295        if instances is not None:
296            self.__init__(**kwargs)
297            return self.__call__(instances, weight_id)
298        else:
299            return self
300
301    def __init__(self, evaluator=Evaluator_Laplace(), beam_width=5,
302        alpha=1.0, **kwds):
303        self.__dict__.update(kwds)
304        self.rule_finder = BeamFinder()
305        self.rule_finder.ruleFilter = BeamFilter_Width(width=beam_width)
306        self.rule_finder.evaluator = evaluator
307        self.rule_finder.validator = Validator_LRS(alpha=alpha)
308        self.rule_finder.rule_stoppingValidator = Validator_LRS(alpha=1.0)
309        self.rule_stopping = Stopping_Apriori()
310        self.data_stopping = DataStoppingCriteria_NoPositives()
311
312    @deprecated_keywords({"weight": "weight_id"})
313    def __call__(self, instances, weight_id=0):
314        supervisedClassCheck(instances)
315
316        rules = RuleList()
317        self.rule_stopping.apriori = Orange.statistics.distribution.Distribution(
318            instances.domain.class_var, instances)
319        progress = getattr(self, "progressCallback", None)
320        if progress:
321            progress.start = 0.0
322            progress.end = 0.0
323            distrib = Orange.statistics.distribution.Distribution(
324                instances.domain.class_var, instances, weight_id)
325            distrib.normalize()
326        for target_class in instances.domain.class_var:
327            if progress:
328                progress.start = progress.end
329                progress.end += distrib[target_class]
330            self.target_class = target_class
331            cl = RuleLearner.__call__(self, instances, weight_id)
332            for r in cl.rules:
333                rules.append(r)
334        if progress:
335            progress(1.0, None)
336        return CN2UnorderedClassifier(rules, instances, weight_id)
337
338CN2UnorderedLearner = deprecated_members({"beamWidth": "beam_width",
339                     "ruleFinder": "rule_finder",
340                     "ruleStopping": "rule_stopping",
341                     "dataStopping": "data_stopping",
342                     "coverAndRemove": "cover_and_remove",
343                     "storeInstances": "store_instances",
344                     "targetClass": "target_class",
345                     "baseRules": "base_rules",
346                     "weightID": "weight_id"})(CN2UnorderedLearner)
347
348
349class CN2UnorderedClassifier(RuleClassifier):
350    """
351    Unordered CN2 classifier (Clark and Boswell; 1991) classifies an
352    instance using a set of unordered rules. The classifier is
353    typically constructed with
354    :class:`~Orange.classification.rules.CN2UnorderedLearner`.
355   
356    :param rules: induced rules
357    :type rules: :class:`~Orange.classification.rules.RuleList`
358   
359    :param instances: stored training data instances
360    :type instances: :class:`Orange.data.Table`
361   
362    :param weight_id: ID of the weight meta-attribute.
363    :type weight_id: int
364
365    """
366
367    @deprecated_keywords({"examples": "instances"})
368    def __init__(self, rules=None, instances=None, weight_id=0, **argkw):
369        self.rules = rules
370        self.examples = instances
371        self.weight_id = weight_id
372        self.class_var = instances.domain.class_var if instances is not None else None
373        self.__dict__.update(argkw)
374        if instances is not None:
375            self.prior = Orange.statistics.distribution.Distribution(
376                                instances.domain.class_var, instances)
377
378    @deprecated_keywords({"retRules": "ret_rules"})
379    def __call__(self, instance, result_type=Orange.classification.Classifier.GetValue, ret_rules=False):
380        """
381        The call has another optional argument that is used to tell
382        the classifier to also return the rules that cover the given
383        data instance.
384
385        :param instance: instance to be classified.
386        :type instance: :class:`Orange.data.Instance`
387       
388        :param result_type: :class:`Orange.classification.Classifier.GetValue` or \
389              :class:`Orange.classification.Classifier.GetProbabilities` or
390              :class:`Orange.classification.Classifier.GetBoth`
391       
392        :rtype: :class:`Orange.data.Value`,
393              :class:`Orange.statistics.distribution.Distribution` or a tuple with both, and a list of rules if :obj:`ret_rules` is ``True``
394        """
395        def add(disc1, disc2, sumd):
396            disc = Orange.statistics.distribution.Discrete(disc1)
397            sumdisc = sumd
398            for i, d in enumerate(disc):
399                disc[i] += disc2[i]
400                sumdisc += disc2[i]
401            return disc, sumdisc
402
403        # create empty distribution
404        retDist = Orange.statistics.distribution.Discrete(self.examples.domain.class_var)
405        covRules = RuleList()
406        # iterate through instances - add distributions
407        sumdisc = 0.
408        for r in self.rules:
409            if r(instance) and r.class_distribution:
410                retDist, sumdisc = add(retDist, r.class_distribution, sumdisc)
411                covRules.append(r)
412        if not sumdisc:
413            retDist = self.prior
414            sumdisc = self.prior.abs
415
416        if sumdisc > 0.0:
417            for c in self.examples.domain.class_var:
418                retDist[c] /= sumdisc
419        else:
420            retDist.normalize()
421
422        if ret_rules:
423            if result_type == Orange.classification.Classifier.GetValue:
424              return (retDist.modus(), covRules)
425            if result_type == Orange.classification.Classifier.GetProbabilities:
426              return (retDist, covRules)
427            return (retDist.modus(), retDist, covRules)
428        if result_type == Orange.classification.Classifier.GetValue:
429          return retDist.modus()
430        if result_type == Orange.classification.Classifier.GetProbabilities:
431          return retDist
432        return (retDist.modus(), retDist)
433
434    def __str__(self):
435        retStr = ""
436        for r in self.rules:
437            retStr += rule_to_string(r) + " " + str(r.class_distribution) + "\n"
438        return retStr
439
440
441class CN2SDUnorderedLearner(CN2UnorderedLearner):
442    """
443    CN2-SD (Lavrac et al.; 2004) induces a set of unordered rules used
444    by :class:`~Orange.classification.rules.CN2UnorderedClassifier`.
445    CN2-SD differs from unordered CN2 by the default function and
446    covering function: :class:`WRACCEvaluator` computes weighted
447    relative accuracy and :class:`CovererAndRemover_MultWeights`
448    decreases the weight of covered data instances instead of removing
449    them.
450   
451    Constructor returns either an instance of
452    :obj:`CN2SDUnorderedLearner` or, if training data is provided, a
453    :obj:`CN2UnorderedClassifier`.
454
455    :param evaluator: an object that evaluates a rule from covered instances.
456        By default, weighted relative accuracy is used.
457    :type evaluator: :class:`~Orange.classification.rules.Evaluator`
458   
459    :param beam_width: width of the search beam.
460    :type beam_width: int
461   
462    :param alpha: significance level of the likelihood ratio statistics to
463        determine whether rule is better than the default rule.
464    :type alpha: float
465   
466    :param mult: multiplicator for weights of covered instances.
467    :type mult: float
468    """
469    def __new__(cls, instances=None, weight_id=0, **kwargs):
470        self = CN2UnorderedLearner.__new__(cls, **kwargs)
471        if instances is not None:
472            self.__init__(**kwargs)
473            return self.__call__(instances, weight_id)
474        else:
475            return self
476
477    def __init__(self, evaluator=WRACCEvaluator(), beam_width=5,
478                alpha=0.05, mult=0.7, **kwds):
479        CN2UnorderedLearner.__init__(self, evaluator=evaluator,
480                                          beam_width=beam_width, alpha=alpha, **kwds)
481        self.cover_and_remove = CovererAndRemover_MultWeights(mult=mult)
482
483    def __call__(self, instances, weight=0):
484        supervisedClassCheck(instances)
485
486        oldInstances = Orange.data.Table(instances)
487        classifier = CN2UnorderedLearner.__call__(self, instances, weight)
488        for r in classifier.rules:
489            r.filterAndStore(oldInstances, weight, r.classifier.default_val)
490        return classifier
491
492
493class ABCN2(RuleLearner):
494    """
495    Argument-based CN2 that uses EVC for evaluation
496    and LRC for classification.
497   
498    :param width: beam width (default 5).
499    :type width: int
500    :param learn_for_class: class for which to learn; ``None`` (default) if all
501       classes are to be learned.
502    :param learn_one_rule: decides whether to learn only a single rule (default:
503       ``False``).
504    :type learn_one_rule: boolean
505    :param analyse_argument: index of argument to analyse; -1 to learn normally
506       (default)
507    :type analyse_argument: int
508    :param debug: sets debug mode that prints some info during execution (default: ``False``)
509    :type debug: boolean
510   
511    The following evaluator related arguments are also supported:
512   
513    :param m: m for m-estimate to be corrected with EVC (default 2).
514    :type m: int
515    :param opt_reduction: type of EVC correction: 0=no correction,
516       1=pessimistic, 2=normal (default).
517    :type opt_reduction: int
518    :param nsampling: number of samples for estimation of extreme value
519       distribution for EVC (default: 100).
520    :type nsampling: int
521    :param evd: pre-given extreme value distributions.
522    :param evd_arguments: pre-given extreme value distributions for arguments.
523   
524    The following parameters control rule validation:
525   
526    :param rule_sig: minimal rule significance (default 1.0).
527    :type rule_sig: float
528    :param att_sig: minimal attribute significance in rule (default 1.0).
529    :type att_sig: float
530    :param max_rule_complexity: maximum number of conditions in rule (default 5).
531    :type max_rule_complexity: int
532    :param min_coverage: minimal number of covered instances (default 5).
533    :type min_coverage: int
534   
535    Probabilistic covering can be controlled using:
536   
537    :param min_improved: minimal number of instances improved in probabilistic covering (default 1).
538    :type min_improved: int
539    :param min_improved_perc: minimal percentage of covered instances that need to be improved (default 0.0).
540    :type min_improved_perc: float
541   
542    Finally, LRC (classifier) related parameters are:
543   
544    :param add_sub_rules: decides whether to add sub-rules.
545    :type add_sub_rules: boolean
546    :param min_cl_sig: minimal significance of beta in classifier (default 0.5).
547    :type min_cl_sig: float
548    :param min_beta: minimal beta value (default 0.0).
549    :type min_beta: float
550    :param set_prefix_rules: decides whether ordered prefix rules should be
551       added (default False).
552    :type set_prefix_rules: boolean
553    :param alternative_learner: use rule-learner as a correction method for
554       other machine learning methods (default None).
555
556    """
557
558    def __init__(self, argument_id=0, width=5, m=2, opt_reduction=2, nsampling=100, max_rule_complexity=5,
559                 rule_sig=1.0, att_sig=1.0, postpruning=None, min_quality=0., min_coverage=1, min_improved=1, min_improved_perc=0.0,
560                 learn_for_class=None, learn_one_rule=False, evd=None, evd_arguments=None, prune_arguments=False, analyse_argument= -1,
561                 alternative_learner=None, min_cl_sig=0.5, min_beta=0.0, set_prefix_rules=False, add_sub_rules=False, debug=False,
562                 **kwds):
563
564        # argument ID which is passed to abcn2 learner
565        self.argument_id = argument_id
566        # learn for specific class only?       
567        self.learn_for_class = learn_for_class
568        # only analysing a specific argument or learning all at once
569        self.analyse_argument = analyse_argument
570        # should we learn only one rule?
571        self.learn_one_rule = learn_one_rule
572        self.postpruning = postpruning
573        # rule finder
574        self.rule_finder = BeamFinder()
575        self.ruleFilter = BeamFilter_Width(width=width)
576        self.ruleFilter_arguments = ABBeamFilter(width=width)
577        if max_rule_complexity - 1 < 0:
578            max_rule_complexity = 10
579        self.rule_finder.rule_stoppingValidator = Validator_LRS(alpha=1.0, min_quality=0., max_rule_complexity=max_rule_complexity - 1, min_coverage=min_coverage)
580        self.refiner = BeamRefiner_Selector()
581        self.refiner_arguments = SelectorAdder(discretizer=Orange.feature.discretization.Entropy(forceAttribute=1,
582                                                                                           maxNumberOfIntervals=2))
583        self.prune_arguments = prune_arguments
584        # evc evaluator
585        evdGet = Orange.core.EVDistGetter_Standard()
586        self.rule_finder.evaluator = Evaluator_mEVC(m=m, evDistGetter=evdGet, min_improved=min_improved, min_improved_perc=min_improved_perc)
587        self.rule_finder.evaluator.returnExpectedProb = True
588        self.rule_finder.evaluator.optimismReduction = opt_reduction
589        self.rule_finder.evaluator.ruleAlpha = rule_sig
590        self.rule_finder.evaluator.attributeAlpha = att_sig
591        self.rule_finder.evaluator.validator = Validator_LRS(alpha=1.0, min_quality=min_quality, min_coverage=min_coverage, max_rule_complexity=max_rule_complexity - 1)
592
593        # learn stopping criteria
594        self.rule_stopping = None
595        self.data_stopping = DataStoppingCriteria_NoPositives()
596        # evd fitting
597        self.evd_creator = EVDFitter(self, n=nsampling)
598        self.evd = evd
599        self.evd_arguments = evd_arguments
600        # classifier
601        self.add_sub_rules = add_sub_rules
602        self.classifier = PILAR(alternative_learner=alternative_learner, min_cl_sig=min_cl_sig, min_beta=min_beta, set_prefix_rules=set_prefix_rules)
603        self.debug = debug
604        # arbitrary parameters
605        self.__dict__.update(kwds)
606
607
608    def __call__(self, examples, weight_id=0):
609        # initialize progress bar
610        progress = getattr(self, "progressCallback", None)
611        if progress:
612            progress.start = 0.0
613            progress.end = 0.0
614            distrib = Orange.statistics.distribution.Distribution(
615                             examples.domain.class_var, examples, weight_id)
616            distrib.normalize()
617
618        # we begin with an empty set of rules
619        all_rules = RuleList()
620
621        # th en, iterate through all classes and learn rule for each class separately
622        for cl_i, cl in enumerate(examples.domain.class_var):
623            if progress:
624                step = distrib[cl] / 2.
625                progress.start = progress.end
626                progress.end += step
627
628            if self.learn_for_class and not self.learn_for_class in [cl, cl_i]:
629                continue
630
631            # rules for this class only
632            rules = RuleList()
633
634            # create dichotomous class
635            dich_data = self.create_dich_class(examples, cl)
636
637            # preparation of the learner (covering, evd, etc.)
638            self.prepare_settings(dich_data, weight_id, cl_i, progress)
639
640            # learn argumented rules first ...
641            self.turn_ABML_mode(dich_data, weight_id, cl_i)
642            # first specialize all unspecialized arguments
643            # dich_data = self.specialise_arguments(dich_data, weight_id)
644            # comment: specialisation of arguments is within learning of an argumented rule;
645            #          this is now different from the published algorithm
646            if progress:
647                progress.start = progress.end
648                progress.end += step
649
650            aes = self.get_argumented_examples(dich_data)
651            aes = self.sort_arguments(aes, dich_data)
652            while aes:
653                if self.analyse_argument > -1 and \
654                   (isinstance(self.analyse_argument, Orange.data.Instance) and not Orange.data.Instance(dich_data.domain, self.analyse_argument) == aes[0] or \
655                    isinstance(self.analyse_argument, int) and not dich_data[self.analyse_argument] == aes[0]):
656                    aes = aes[1:]
657                    continue
658                ae = aes[0]
659                rule = self.learn_argumented_rule(ae, dich_data, weight_id) # target class is always first class (0)
660                if self.debug and rule:
661                    print "learned arg rule", Orange.classification.rules.rule_to_string(rule)
662                elif self.debug:
663                    print "no rule came out of ", ae
664                if rule:
665                    rules.append(rule)
666                    aes = filter(lambda x: not rule(x), aes)
667                else:
668                    aes = aes[1:]
669                aes = aes[1:]
670
671            if not progress and self.debug:
672                print " arguments finished ... "
673
674            # remove all examples covered by rules
675            for rule in rules:
676                dich_data = self.remove_covered_examples(rule, dich_data, weight_id)
677            if progress:
678                progress(self.remaining_probability(dich_data), None)
679
680            # learn normal rules on remaining examples
681            if self.analyse_argument == -1:
682                self.turn_normal_mode(dich_data, weight_id, cl_i)
683                while dich_data:
684                    # learn a rule
685                    rule = self.learn_normal_rule(dich_data, weight_id, self.apriori)
686                    if not rule:
687                        break
688                    if self.debug:
689                        print "rule learned: ", Orange.classification.rules.rule_to_string(rule), rule.quality
690                    dich_data = self.remove_covered_examples(rule, dich_data, weight_id)
691                    if progress:
692                        progress(self.remaining_probability(dich_data), None)
693                    rules.append(rule)
694                    if self.learn_one_rule:
695                        break
696
697            # prune unnecessary rules
698            rules = self.prune_unnecessary_rules(rules, dich_data, weight_id)
699
700            if self.add_sub_rules:
701                rules = self.add_sub_rules_call(rules, dich_data, weight_id)
702
703            # restore domain and class in rules, add them to all_rules
704            for r in rules:
705                all_rules.append(self.change_domain(r, cl, examples, weight_id))
706
707            if progress:
708                progress(1.0, None)
709        # create a classifier from all rules       
710        return self.create_classifier(all_rules, examples, weight_id)
711
712    def learn_argumented_rule(self, ae, examples, weight_id):
713        # prepare roots of rules from arguments
714        positive_args = self.init_pos_args(ae, examples, weight_id)
715        if not positive_args: # something wrong
716            raise "There is a problem with argumented example %s" % str(ae)
717            return None
718        negative_args = self.init_neg_args(ae, examples, weight_id)
719
720        # set negative arguments in refiner
721        self.rule_finder.refiner.notAllowedSelectors = negative_args
722        self.rule_finder.refiner.example = ae
723        # set arguments to filter
724        self.rule_finder.ruleFilter.setArguments(examples.domain, positive_args)
725
726        # learn a rule
727        self.rule_finder.evaluator.bestRule = None
728        self.rule_finder(examples, weight_id, 0, positive_args)
729
730        # return best rule
731        return self.rule_finder.evaluator.bestRule
732
733    def prepare_settings(self, examples, weight_id, cl_i, progress):
734        # apriori distribution
735        self.apriori = Orange.statistics.distribution.Distribution(
736                                examples.domain.class_var, examples, weight_id)
737
738        # prepare covering mechanism
739        self.coverAndRemove = CovererAndRemover_Prob(examples, weight_id, 0, self.apriori, self.argument_id)
740        self.rule_finder.evaluator.probVar = examples.domain.getmeta(self.cover_and_remove.probAttribute)
741
742        # compute extreme distributions
743        # TODO: why evd and evd_this????
744        if self.rule_finder.evaluator.optimismReduction > 0 and not self.evd:
745            self.evd_this = self.evd_creator.computeEVD(examples, weight_id, target_class=0, progress=progress)
746        if self.evd:
747            self.evd_this = self.evd[cl_i]
748
749    def turn_ABML_mode(self, examples, weight_id, cl_i):
750        # evaluator
751        if self.rule_finder.evaluator.optimismReduction > 0 and self.argument_id:
752            if self.evd_arguments:
753                self.rule_finder.evaluator.evDistGetter.dists = self.evd_arguments[cl_i]
754            else:
755                self.rule_finder.evaluator.evDistGetter.dists = self.evd_this # self.evd_creator.computeEVD_example(examples, weight_id, target_class=0)
756        # rule refiner
757        self.rule_finder.refiner = self.refiner_arguments
758        self.rule_finder.refiner.argument_id = self.argument_id
759        self.rule_finder.ruleFilter = self.ruleFilter_arguments
760
761    def create_dich_class(self, examples, cl):
762        """
763        Create dichotomous class.
764        """
765        (newDomain, targetVal) = create_dichotomous_class(examples.domain, examples.domain.class_var, str(cl), negate=0)
766        newDomainmetas = newDomain.getmetas()
767        newDomain.addmeta(Orange.feature.Descriptor.new_meta_id(), examples.domain.class_var) # old class as meta
768        dichData = examples.select(newDomain)
769        if self.argument_id:
770            for d in dichData: # remove arguments given to other classes
771                if not d.getclass() == targetVal:
772                    d[self.argument_id] = "?"
773        return dichData
774
775    def get_argumented_examples(self, examples):
776        if not self.argument_id:
777            return None
778
779        # get argumented examples
780        return ArgumentFilter_hasSpecial()(examples, self.argument_id, target_class=0)
781
782    def sort_arguments(self, arg_examples, examples):
783        if not self.argument_id:
784            return None
785        evaluateAndSortArguments(examples, self.argument_id)
786        if len(arg_examples) > 0:
787            # sort examples by their arguments quality (using first argument as it has already been sorted)
788            sorted = arg_examples.native()
789            sorted.sort(lambda x, y:-cmp(x[self.argument_id].value.positive_arguments[0].quality,
790                                         y[self.argument_id].value.positive_arguments[0].quality))
791            return Orange.data.Table(examples.domain, sorted)
792        else:
793            return None
794
795    def turn_normal_mode(self, examples, weight_id, cl_i):
796        # evaluator
797        if self.rule_finder.evaluator.optimismReduction > 0:
798            if self.evd:
799                self.rule_finder.evaluator.evDistGetter.dists = self.evd[cl_i]
800            else:
801                self.rule_finder.evaluator.evDistGetter.dists = self.evd_this # self.evd_creator.computeEVD(examples, weight_id, target_class=0)
802        # rule refiner
803        self.rule_finder.refiner = self.refiner
804        self.rule_finder.ruleFilter = self.ruleFilter
805
806    def learn_normal_rule(self, examples, weight_id, apriori):
807        if hasattr(self.rule_finder.evaluator, "bestRule"):
808            self.rule_finder.evaluator.bestRule = None
809        rule = self.rule_finder(examples, weight_id, 0, RuleList())
810        if hasattr(self.rule_finder.evaluator, "bestRule") and self.rule_finder.evaluator.returnExpectedProb:
811            rule = self.rule_finder.evaluator.bestRule
812            self.rule_finder.evaluator.bestRule = None
813        if self.postpruning:
814            rule = self.postpruning(rule, examples, weight_id, 0, aprior)
815        return rule
816
817    def remove_covered_examples(self, rule, examples, weight_id):
818        nexamples, nweight = self.cover_and_remove(rule, examples, weight_id, 0)
819        return nexamples
820
821
822    def prune_unnecessary_rules(self, rules, examples, weight_id):
823        return self.cover_and_remove.getBestRules(rules, examples, weight_id)
824
825    def change_domain(self, rule, cl, examples, weight_id):
826        rule.filter = Orange.data.filter.Values(
827            domain=examples.domain, conditions=rule.filter.conditions)
828        rule.filterAndStore(examples, weight_id, cl)
829        if hasattr(rule, "learner") and hasattr(rule.learner, "arg_example"):
830            rule.learner.arg_example = Orange.data.Instance(examples.domain, rule.learner.arg_example)
831        return rule
832
833    def create_classifier(self, rules, examples, weight_id):
834        return self.classifier(rules, examples, weight_id)
835
836    def add_sub_rules_call(self, rules, examples, weight_id):
837        apriori = Orange.statistics.distribution.Distribution(
838                            examples.domain.class_var, examples, weight_id)
839        new_rules = RuleList()
840        for r in rules:
841            new_rules.append(r)
842
843        # loop through rules
844        for r in rules:
845            tmpList = RuleList()
846            tmpRle = r.clone()
847            tmpRle.filter.conditions = r.filter.conditions[:r.requiredConditions] # do not split argument
848            tmpRle.parentRule = None
849            tmpRle.filterAndStore(examples, weight_id, r.classifier.default_val)
850            tmpRle.complexity = 0
851            tmpList.append(tmpRle)
852            while tmpList and len(tmpList[0].filter.conditions) <= len(r.filter.conditions):
853                tmpList2 = RuleList()
854                for tmpRule in tmpList:
855                    # evaluate tmpRule
856                    oldREP = self.rule_finder.evaluator.returnExpectedProb
857                    self.rule_finder.evaluator.returnExpectedProb = False
858                    tmpRule.quality = self.rule_finder.evaluator(tmpRule, examples, weight_id, r.classifier.default_val, apriori)
859                    self.rule_finder.evaluator.returnExpectedProb = oldREP
860                tmpList.sort(lambda x, y:-cmp(x.quality, y.quality))
861                tmpList = tmpList[:self.rule_filter.width]
862
863                for tmpRule in tmpList:
864                    # if rule not in rules already, add it to the list
865                    if not True in [Orange.classification.rules.rules_equal(ri, tmpRule) for ri in new_rules] and len(tmpRule.filter.conditions) > 0 and tmpRule.quality > apriori[r.classifier.default_val] / apriori.abs:
866                        new_rules.append(tmpRule)
867                    # create new tmpRules, set parent Rule, append them to tmpList2
868                    if not True in [Orange.classification.rules.rules_equal(ri, tmpRule) for ri in new_rules]:
869                        for c in r.filter.conditions:
870                            tmpRule2 = tmpRule.clone()
871                            tmpRule2.parentRule = tmpRule
872                            tmpRule2.filter.conditions.append(c)
873                            tmpRule2.filterAndStore(examples, weight_id, r.classifier.default_val)
874                            tmpRule2.complexity += 1
875                            if tmpRule2.class_distribution.abs < tmprule.class_distribution.abs:
876                                tmpList2.append(tmpRule2)
877                tmpList = tmpList2
878        return new_rules
879
880    def init_pos_args(self, ae, examples, weight_id):
881        pos_args = RuleList()
882        # prepare arguments
883        for p in ae[self.argument_id].value.positive_arguments:
884            new_arg = Rule(filter=ArgFilter(argument_id=self.argument_id,
885                                                   filter=self.newFilter_values(p.filter),
886                                                   arg_example=ae),
887                                                   complexity=0)
888            new_arg.valuesFilter = new_arg.filter.filter
889            pos_args.append(new_arg)
890
891
892        if hasattr(self.rule_finder.evaluator, "returnExpectedProb"):
893            old_exp = self.rule_finder.evaluator.returnExpectedProb
894            self.rule_finder.evaluator.returnExpectedProb = False
895
896        # argument pruning (all or just unfinished arguments)
897        # if pruning is chosen, then prune arguments if possible
898        for p in pos_args:
899            p.filterAndStore(examples, weight_id, 0)
900            if not p.learner:
901                p.learner = DefaultLearner(default_value=ae.getclass())
902            # pruning on: we check on all conditions and take only best
903            if self.prune_arguments:
904                allowed_conditions = [c for c in p.filter.conditions]
905                pruned_conditions = self.prune_arg_conditions(ae, allowed_conditions, examples, weight_id)
906                p.baseDist = Orange.statistics.distribution.Distribution(examples.domain.classVar, examples, weight_id)
907                p.filter.conditions = pruned_conditions
908                p.learner.setattr("arg_length", 0)
909
910            else: # prune only unspecified conditions
911                spec_conditions = [c for c in p.filter.conditions if not c.unspecialized_condition]
912                unspec_conditions = [c for c in p.filter.conditions if c.unspecialized_condition]
913                # let rule cover now all examples filtered by specified conditions
914                p.filter.conditions = spec_conditions
915                p.filterAndStore(examples, weight_id, 0)
916                p.baseDist = p.classDistribution
917                p.learner.setattr("arg_length", len(p.filter.conditions))
918                pruned_conditions = self.prune_arg_conditions(ae, unspec_conditions, p.examples, p.weightID)
919                p.filter.conditions.extend(pruned_conditions)
920                p.filter.filter.conditions.extend(pruned_conditions)
921                # if argument does not contain all unspecialized reasons, add those reasons with minimum values
922                at_oper_pairs = [(c.position, c.oper) for c in p.filter.conditions if type(c) == Orange.data.filter.ValueFilterContinuous]
923                for u in unspec_conditions:
924                    if not (u.position, u.oper) in at_oper_pairs:
925                        # find minimum value
926                        if u.oper == Orange.data.filter.ValueFilter.Greater or \
927                            u.oper == Orange.data.filter.ValueFilter.GreaterEqual:
928                            u.ref = min([float(e[u.position]) - 10. for e in p.examples])
929                        else:
930                            u.ref = max([float(e[u.position]) + 10. for e in p.examples])
931                        p.filter.conditions.append(u)
932                        p.filter.filter.conditions.append(u)
933
934        # set parameters to arguments
935        for p_i, p in enumerate(pos_args):
936            p.filterAndStore(examples, weight_id, 0)
937            p.filter.domain = examples.domain
938            p.classifier = p.learner(p.examples, p.weightID)
939            p.requiredConditions = len(p.filter.conditions)
940            p.learner.setattr("arg_example", ae)
941            p.complexity = len(p.filter.conditions)
942
943        if hasattr(self.rule_finder.evaluator, "returnExpectedProb"):
944            self.rule_finder.evaluator.returnExpectedProb = old_exp
945
946        return pos_args
947
948    def newFilter_values(self, filter):
949        newFilter = Orange.data.filter.Values()
950        newFilter.conditions = filter.conditions[:]
951        newFilter.domain = filter.domain
952        newFilter.negate = filter.negate
953        newFilter.conjunction = filter.conjunction
954        return newFilter
955
956    def init_neg_args(self, ae, examples, weight_id):
957        return ae[self.argument_id].value.negative_arguments
958
959    def remaining_probability(self, examples):
960        return self.cover_and_remove.covered_percentage(examples)
961
962    def prune_arg_conditions(self, crit_example, allowed_conditions, examples, weight_id):
963        if not allowed_conditions:
964            return []
965        cn2_learner = Orange.classification.rules.CN2UnorderedLearner()
966        cn2_learner.rule_finder = BeamFinder()
967        cn2_learner.rule_finder.refiner = SelectorArgConditions(crit_example, allowed_conditions)
968        cn2_learner.rule_finder.evaluator = Orange.classification.rules.MEstimateEvaluator(self.rule_finder.evaluator.m)
969        rule = cn2_learner.rule_finder(examples, weight_id, 0, RuleList())
970        return rule.filter.conditions
971
972ABCN2 = deprecated_members({"beamWidth": "beam_width",
973                     "ruleFinder": "rule_finder",
974                     "ruleStopping": "rule_stopping",
975                     "dataStopping": "data_stopping",
976                     "coverAndRemove": "cover_and_remove",
977                     "storeInstances": "store_instances",
978                     "targetClass": "target_class",
979                     "baseRules": "base_rules",
980                     "weightID": "weight_id",
981                     "argumentID": "argument_id"})(ABCN2)
982
983class CN2EVCUnorderedLearner(ABCN2):
984    """
985    A learner similar to CN2-SD (:obj:`CN2SDUnorderedLearner`) except that
986    it uses EVC for rule evaluation.
987
988    :param evaluator: an object that evaluates a rule from covered instances.
989        By default, weighted relative accuracy is used.
990    :type evaluator: :class:`~Orange.classification.rules.Evaluator`
991   
992    :param beam_width: width of the search beam.
993    :type beam_width: int
994   
995    :param alpha: significance level of the likelihood ratio statistics to
996        determine whether rule is better than the default rule.
997    :type alpha: float
998   
999    :param mult: multiplicator for weights of covered instances.
1000    :type mult: float
1001    """
1002    def __init__(self, width=5, nsampling=100, rule_sig=1.0, att_sig=1.0, \
1003        min_coverage=1., max_rule_complexity=5.):
1004        ABCN2.__init__(self, width=width, nsampling=nsampling,
1005            rule_sig=rule_sig, att_sig=att_sig, min_coverage=int(min_coverage),
1006            max_rule_complexity=int(max_rule_complexity))
1007
1008class DefaultLearner(Orange.classification.Learner):
1009    """
1010    Default learner - returns default classifier with predefined output class.
1011    """
1012    def __init__(self, default_value=None):
1013        self.default_value = default_value
1014    def __call__(self, examples, weight_id=0):
1015        return Orange.classification.ConstantClassifier(self.default_value, defaultDistribution=Orange.statistics.Distribution(examples.domain.class_var, examples, weight_id))
1016
1017class ABCN2Ordered(ABCN2):
1018    """
1019    Rules learned by ABCN2 are ordered and used as a decision list.
1020    """
1021    def __init__(self, argument_id=0, **kwds):
1022        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1023        self.classifier.set_prefix_rules = True
1024        self.classifier.optimize_betas = False
1025
1026class ABCN2M(ABCN2):
1027    """
1028    Argument based rule learning with m-estimate as evaluation function.
1029    """
1030    def __init__(self, argument_id=0, **kwds):
1031        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1032        self.opt_reduction = 0
1033        self.rule_finder.evaluator.optimismReduction = self.opt_reduction
1034        self.classifier = CN2UnorderedClassifier
1035
1036class ABCN2MLRC(ABCN2):
1037    """
1038    Argument based rule learning with m-estimate as evaluation function. LRC is used as a classification method.
1039    """
1040    def __init__(self, argument_id=0, **kwds):
1041        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1042        self.opt_reduction = 0
1043        self.rule_finder.evaluator.optimismReduction = self.opt_reduction
1044
1045class ABCN2_StandardClassification(ABCN2):
1046    """
1047    Argument based rule learning with the original classification technique.
1048    """
1049    def __init__(self, argument_id=0, **kwds):
1050        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1051        self.classifier = CN2UnorderedClassifier
1052
1053
1054class Stopping_Apriori(StoppingCriteria):
1055    def __init__(self, apriori=None):
1056        self.apriori = None
1057
1058    def __call__(self, rules, rule, instances, data):
1059        if not self.apriori:
1060            return False
1061        if not type(rule.classifier) == Orange.classification.ConstantClassifier:
1062            return False
1063        ruleAcc = rule.class_distribution[rule.classifier.default_val] / rule.class_distribution.abs
1064        aprioriAcc = self.apriori[rule.classifier.default_val] / self.apriori.abs
1065        if ruleAcc > aprioriAcc:
1066            return False
1067        return True
1068
1069
1070class Stopping_SetRules(StoppingCriteria):
1071    def __init__(self, validator):
1072        self.rule_stopping = StoppingCriteria_NegativeDistribution()
1073        self.validator = validator
1074
1075    def __call__(self, rules, rule, instances, data):
1076        ru_st = self.rule_stopping(rules, rule, instances, data)
1077        if not ru_st:
1078            self.validator.rules.append(rule)
1079        return bool(ru_st)
1080
1081
1082class LengthValidator(Validator):
1083    """ prune rules with more conditions than self.length. """
1084    def __init__(self, length= -1):
1085        self.length = length
1086
1087    def __call__(self, rule, data, weight_id, target_class, apriori):
1088        if self.length >= 0:
1089            return len(rule.filter.conditions) <= self.length
1090        return True
1091
1092
1093class NoDuplicatesValidator(Validator):
1094    def __init__(self, alpha=.05, min_coverage=0, max_rule_length=0, rules=RuleList()):
1095        self.rules = rules
1096        self.validator = Validator_LRS(alpha=alpha, \
1097            min_coverage=min_coverage, max_rule_length=max_rule_length)
1098
1099    def __call__(self, rule, data, weight_id, target_class, apriori):
1100        if rule_in_set(rule, self.rules):
1101            return False
1102        return bool(self.validator(rule, data, weight_id, target_class, apriori))
1103
1104
1105
1106class Classifier_BestRule(RuleClassifier):
1107    def __init__(self, rules, instances, weight_id=0, **argkw):
1108        self.rules = rules
1109        self.examples = instances
1110        self.class_var = instances.domain.class_var
1111        self.__dict__.update(argkw)
1112        self.prior = Orange.statistics.distribution.Distribution(
1113                    instances.domain.class_var, instances)
1114
1115    def __call__(self, instance, result_type=Orange.classification.Classifier.GetValue):
1116        retDist = Orange.statistics.distribution.Distribution(instance.domain.class_var)
1117        bestRule = None
1118        for r in self.rules:
1119            if r(instance) and (not bestRule or r.quality > bestRule.quality):
1120                for v_i, v in enumerate(instance.domain.class_var):
1121                    retDist[v_i] = r.class_distribution[v_i]
1122                bestRule = r
1123        if not bestRule:
1124            retDist = self.prior
1125        else:
1126            bestRule.used += 1
1127        sumdist = sum(retDist)
1128        if sumdist > 0.0:
1129            for c in self.examples.domain.class_var:
1130                retDist[c] /= sumdisc
1131        else:
1132            retDist.normalize()
1133        # return classifier(instance, result_type=result_type)
1134        if result_type == Orange.classification.Classifier.GetValue:
1135          return retDist.modus()
1136        if result_type == Orange.classification.Classifier.GetProbabilities:
1137          return retDist
1138        return (retDist.modus(), retDist)
1139
1140    def __str__(self):
1141        retStr = ""
1142        for r in self.rules:
1143            retStr += rule_to_string(r) + " " + str(r.class_distribution) + "\n"
1144        return retStr
1145
1146
1147class CovererAndRemover_MultWeights(CovererAndRemover):
1148    """
1149    Covering and removing of instances using weight multiplication.
1150   
1151    :param mult: weighting multiplication factor
1152    :type mult: float   
1153    """
1154
1155    def __init__(self, mult=0.7):
1156        self.mult = mult
1157    def __call__(self, rule, instances, weights, target_class):
1158        if not weights:
1159            weights = Orange.feature.Descriptor.new_meta_id()
1160            instances.addMetaAttribute(weights, 1.)
1161            instances.domain.addmeta(weights, Orange.feature.\
1162                Continuous("weights-" + str(weights)), True)
1163        newWeightsID = Orange.feature.Descriptor.new_meta_id()
1164        instances.addMetaAttribute(newWeightsID, 1.)
1165        instances.domain.addmeta(newWeightsID, Orange.feature.\
1166            Continuous("weights-" + str(newWeightsID)), True)
1167        for instance in instances:
1168            if rule(instance) and instance.getclass() == rule.classifier(\
1169                instance, Orange.classification.Classifier.GetValue):
1170                instance[newWeightsID] = instance[weights] * self.mult
1171            else:
1172                instance[newWeightsID] = instance[weights]
1173        return (instances, newWeightsID)
1174
1175
1176class CovererAndRemover_AddWeights(CovererAndRemover):
1177    """
1178    Covering and removing of instances using weight addition.
1179   
1180    """
1181
1182    def __call__(self, rule, instances, weights, target_class):
1183        if not weights:
1184            weights = Orange.feature.Descriptor.new_meta_id()
1185            instances.addMetaAttribute(weights, 1.)
1186            instances.domain.addmeta(weights, Orange.feature.\
1187                Continuous("weights-" + str(weights)), True)
1188        try:
1189            coverage = instances.domain.getmeta("Coverage")
1190        except:
1191            coverage = Orange.feature.Continuous("Coverage")
1192            instances.domain.addmeta(Orange.feature.Descriptor.new_meta_id(), coverage, True)
1193            instances.addMetaAttribute(coverage, 0.0)
1194        newWeightsID = Orange.feature.Descriptor.new_meta_id()
1195        instances.addMetaAttribute(newWeightsID, 1.)
1196        instances.domain.addmeta(newWeightsID, Orange.feature.\
1197            Continuous("weights-" + str(newWeightsID)), True)
1198        for instance in instances:
1199            if rule(instance) and instance.getclass() == rule.classifier(instance, \
1200                    Orange.classification.Classifier.GetValue):
1201                try:
1202                    instance[coverage] += 1.0
1203                except:
1204                    instance[coverage] = 1.0
1205                instance[newWeightsID] = 1.0 / (instance[coverage] + 1)
1206            else:
1207                instance[newWeightsID] = instance[weights]
1208        return (instances, newWeightsID)
1209
1210
1211class CovererAndRemover_Prob(CovererAndRemover):
1212    """ This class impements probabilistic covering. """
1213    def __init__(self, examples, weight_id, target_class, apriori, argument_id):
1214        self.best_rule = [None] * len(examples)
1215        self.prob_attribute = Orange.feature.Descriptor.new_meta_id()
1216        self.apriori_prob = apriori[target_class] / apriori.abs
1217        examples.addMetaAttribute(self.prob_attribute, self.apriori_prob)
1218        examples.domain.addmeta(self.prob_attribute,
1219            Orange.feature.Continuous("Probs"))
1220        self.argument_id = argument_id
1221
1222    def getBestRules(self, current_rules, examples, weight_id):
1223        best_rules = RuleList()
1224        for r_i, r in enumerate(self.best_rule):
1225            if r and not rule_in_set(r, best_rules) and int(examples[r_i].getclass()) == int(r.classifier.default_value):
1226                if hasattr(r.learner, "arg_example"):
1227                    setattr(r, "best_example", r.learner.arg_example)
1228                else:
1229                    setattr(r, "best_example", examples[r_i])
1230                best_rules.append(r)
1231        return best_rules
1232
1233    def __call__(self, rule, examples, weights, target_class):
1234        """ if example has an argument, then the rule must be consistent with the argument. """
1235        example = getattr(rule.learner, "arg_example", None)
1236        for ei, e in enumerate(examples):
1237            if e == example:
1238                e[self.prob_attribute] = 1.0
1239                self.best_rule[ei] = rule
1240            elif rule(e) and rule.quality > e[self.prob_attribute]:
1241                e[self.prob_attribute] = rule.quality + 0.001 # 0.001 is added to avoid numerical errors
1242                self.best_rule[ei] = rule
1243        return (examples, weights)
1244
1245    def filter_covers_example(self, example, filter):
1246        filter_indices = CoversArguments.filterIndices(filter)
1247        if filter(example):
1248            try:
1249                if example[self.argument_id].value and len(example[self.argument_id].value.positive_arguments) > 0: # example has positive arguments
1250                    # conditions should cover at least one of the positive arguments
1251                    one_arg_covered = False
1252                    for pA in example[self.argument_id].value.positive_arguments:
1253                        arg_covered = [self.condIn(c, filter_indices) for c in pA.filter.conditions]
1254                        one_arg_covered = one_arg_covered or len(arg_covered) == sum(arg_covered) #arg_covered
1255                        if one_arg_covered:
1256                            break
1257                    if not one_arg_covered:
1258                        return False
1259                if example[self.argument_id].value and len(example[self.argument_id].value.negative_arguments) > 0: # example has negative arguments
1260                    # condition should not cover neither of negative arguments
1261                    for pN in example[self.argument_id].value.negative_arguments:
1262                        arg_covered = [self.condIn(c, filter_indices) for c in pN.filter.conditions]
1263                        if len(arg_covered) == sum(arg_covered):
1264                            return False
1265            except:
1266                return True
1267            return True
1268        return False
1269
1270    def condIn(self, cond, filter_indices): # is condition in the filter?
1271        condInd = CoversArguments.conditionIndex(cond)
1272        if operator.or_(condInd, filter_indices[cond.position]) == filter_indices[cond.position]:
1273            return True
1274        return False
1275
1276
1277    def covered_percentage(self, examples):
1278        p = 0.0
1279        for ei, e in enumerate(examples):
1280            p += (e[self.prob_attribute] - self.apriori_prob) / (1.0 - self.apriori_prob)
1281        return p / len(examples)
1282
1283
1284
1285
1286@deprecated_keywords({"showDistribution": "show_distribution"})
1287def rule_to_string(rule, show_distribution=True):
1288    """
1289    Write a string presentation of rule in human readable format.
1290   
1291    :param rule: rule to pretty-print.
1292    :type rule: :class:`~Orange.classification.rules.Rule`
1293   
1294    :param show_distribution: determines whether presentation should also
1295        contain the distribution of covered instances
1296    :type show_distribution: bool
1297   
1298    """
1299    def selectSign(oper):
1300        if oper == Orange.data.filter.ValueFilter.Less:
1301            return "<"
1302        elif oper == Orange.data.filter.ValueFilter.LessEqual:
1303            return "<="
1304        elif oper == Orange.data.filter.ValueFilter.Greater:
1305            return ">"
1306        elif oper == Orange.data.filter.ValueFilter.GreaterEqual:
1307            return ">="
1308        else: return "="
1309
1310    if not rule:
1311        return "None"
1312    conds = rule.filter.conditions
1313    domain = rule.filter.domain
1314
1315    ret = "IF "
1316    if len(conds) == 0:
1317        ret = ret + "TRUE"
1318
1319    for i, c in enumerate(conds):
1320        if i > 0:
1321            ret += " AND "
1322        if isinstance(c, Orange.data.filter.ValueFilterDiscrete):
1323            ret += domain[c.position].name + "=" + str([domain[c.position].\
1324                values[int(v)] for v in c.values])
1325        elif isinstance(c, Orange.data.filter.ValueFilterContinuous):
1326            ret += domain[c.position].name + selectSign(c.oper) + str(c.ref)
1327    if isinstance(rule.classifier, Orange.classification.ConstantClassifier) \
1328            and rule.classifier.default_val:
1329        ret = ret + " THEN " + domain.class_var.name + "=" + \
1330            str(rule.classifier.default_value)
1331        if show_distribution:
1332            ret += str(rule.class_distribution)
1333    elif isinstance(rule.classifier, Orange.classification.ConstantClassifier) \
1334            and isinstance(domain.class_var, Orange.feature.Discrete):
1335        ret = ret + " THEN " + domain.class_var.name + "=" + \
1336            str(rule.class_distribution.modus())
1337        if show_distribution:
1338            ret += str(rule.class_distribution)
1339    return ret
1340
1341def supervisedClassCheck(instances):
1342    if not instances.domain.class_var:
1343        raise Exception("Class variable is required!")
1344    if instances.domain.class_var.var_type != Orange.feature.Type.Discrete:
1345        raise Exception("CN2 requires a discrete class!")
1346
1347
1348def rule_in_set(rule, rules):
1349    for r in rules:
1350        if rules_equal(rule, r):
1351            return True
1352    return False
1353
1354def rules_equal(rule1, rule2):
1355    if len(rule1.filter.conditions) != len(rule2.filter.conditions):
1356        return False
1357    for c1 in rule1.filter.conditions:
1358        found = False # find the same condition in the other rule
1359        for c2 in rule2.filter.conditions:
1360            try:
1361                if not c1.position == c2.position: continue # same feature?
1362                if not type(c1) == type(c2): continue # same type of condition
1363                if type(c1) == Orange.core.ValueFilter_discrete:
1364                    if not type(c1.values[0]) == type(c2.values[0]): continue
1365                    if not c1.values[0] == c2.values[0]: continue # same value?
1366                if type(c1) == Orange.core.ValueFilter_continuous:
1367                    if not c1.oper == c2.oper: continue # same operator?
1368                    if not c1.ref == c2.ref: continue #same threshold?
1369                found = True
1370                break
1371            except:
1372                pass
1373        if not found:
1374            return False
1375    return True
1376
1377# Miscellaneous - utility functions
1378def avg(l):
1379    if len(l) == 0:
1380        return 0.
1381    return sum(l) / len(l)
1382
1383def var(l):
1384    if len(l) < 2:
1385        return 0.
1386    av = avg(l)
1387    vars = [math.pow(li - av, 2) for li in l]
1388    return sum(vars) / (len(l) - 1)
1389
1390def median(l):
1391    if len(l) == 0:
1392        return 0.
1393    l.sort()
1394    le = len(l)
1395    if le % 2 == 1:
1396        return l[(le - 1) / 2]
1397    else:
1398        return (l[le / 2 - 1] + l[le / 2]) / 2
1399
1400def perc(l, p):
1401    l.sort()
1402    return l[int(math.floor(p * len(l)))]
1403
1404class EVDFitter:
1405    """ Randomizes a dataset and fits an extreme value distribution onto it. """
1406
1407    def __init__(self, learner, n=200, randomseed=100):
1408        self.learner = learner
1409        self.n = n
1410        self.randomseed = randomseed
1411        # initialize random seed to make experiments repeatable
1412        random.seed(self.randomseed)
1413
1414
1415    def createRandomDataSet(self, data):
1416        newData = Orange.data.Table(data)
1417        # shuffle data
1418        cl_num = newData.toNumpy("C")
1419        random.shuffle(cl_num[0][:, 0])
1420        clData = Orange.data.Table(Orange.data.Domain([newData.domain.classVar]), cl_num[0])
1421        for d_i, d in enumerate(newData):
1422            d[newData.domain.classVar] = clData[d_i][newData.domain.classVar]
1423        return newData
1424
1425    def createEVDistList(self, evdList):
1426        l = Orange.core.EVDistList()
1427        for el in evdList:
1428            l.append(Orange.core.EVDist(mu=el[0], beta=el[1], percentiles=el[2]))
1429        return l
1430
1431
1432    # estimated fisher tippett parameters for a set of values given in vals list (+ deciles)
1433    def compParameters(self, vals, oldMi, oldBeta, oldPercs, fixedBeta=False):
1434        # compute percentiles
1435        vals.sort()
1436        N = len(vals)
1437        percs = [avg(vals[int(float(N) * i / 10):int(float(N) * (i + 1) / 10)]) for i in range(10)]
1438        if N < 10:
1439            return oldMi, oldBeta, percs
1440        if not fixedBeta:
1441            beta = min(2.0, math.sqrt(6 * var(vals) / math.pow(math.pi, 2)))#min(2.0, max(oldBeta, math.sqrt(6*var(vals)/math.pow(math.pi,2))))
1442        else:
1443            beta = oldBeta
1444        mi = max(oldMi, percs[-1] + beta * math.log(-math.log(0.95)))
1445        mi = percs[-1] + beta * math.log(-math.log(0.95))
1446        return max(oldMi, numpy.average(vals) - beta * 0.5772156649), beta, None
1447
1448    def prepare_learner(self):
1449        self.oldStopper = self.learner.ruleFinder.ruleStoppingValidator
1450        self.evaluator = self.learner.ruleFinder.evaluator
1451        self.refiner = self.learner.ruleFinder.refiner
1452        self.validator = self.learner.ruleFinder.validator
1453        self.ruleFilter = self.learner.ruleFinder.ruleFilter
1454        self.learner.ruleFinder.validator = None
1455        self.learner.ruleFinder.evaluator = Orange.core.RuleEvaluator_LRS()
1456        self.learner.ruleFinder.evaluator.storeRules = True
1457        self.learner.ruleFinder.ruleStoppingValidator = Orange.core.RuleValidator_LRS(alpha=1.0)
1458        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = 0
1459        self.learner.ruleFinder.refiner = BeamRefiner_Selector()
1460        self.learner.ruleFinder.ruleFilter = BeamFilter_Width(width=5)
1461
1462
1463    def restore_learner(self):
1464        self.learner.ruleFinder.evaluator = self.evaluator
1465        self.learner.ruleFinder.ruleStoppingValidator = self.oldStopper
1466        self.learner.ruleFinder.refiner = self.refiner
1467        self.learner.ruleFinder.validator = self.validator
1468        self.learner.ruleFinder.ruleFilter = self.ruleFilter
1469
1470    def computeEVD(self, data, weightID=0, target_class=0, progress=None):
1471        import time
1472        # prepare learned for distribution computation       
1473        self.prepare_learner()
1474
1475        # loop through N (sampling repetitions)
1476        extremeDists = [(0, 1, [])]
1477        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = self.oldStopper.max_rule_complexity
1478        maxVals = [[] for l in range(self.oldStopper.max_rule_complexity + 1)]
1479        for d_i in range(self.n):
1480            if not progress:
1481                if self.learner.debug:
1482                    print d_i,
1483            else:
1484                progress(float(d_i) / self.n, None)
1485            # create data set (remove and randomize)
1486            a = time.time()
1487            tempData = self.createRandomDataSet(data)
1488            a = time.time()
1489            self.learner.ruleFinder.evaluator.rules = RuleList()
1490            a = time.time()
1491            for l in range(self.oldStopper.max_rule_complexity + 2):
1492               self.learner.ruleFinder.evaluator.rules.append(None)
1493            a = time.time()
1494            # Next, learn a rule
1495            self.learner.ruleFinder(tempData, weightID, target_class, RuleList())
1496            a = time.time()
1497            for l in range(self.oldStopper.max_rule_complexity + 1):
1498                if self.learner.ruleFinder.evaluator.rules[l]:
1499                    maxVals[l].append(self.learner.ruleFinder.evaluator.rules[l].quality)
1500                else:
1501                    maxVals[l].append(0)
1502##                qs = [r.quality for r in self.learner.ruleFinder.evaluator.rules if r.complexity == l+1]
1503####                if qs:
1504####                    for r in self.learner.ruleFinder.evaluator.rules:
1505####                        if r.quality == max(qs) and r.classDistribution.abs == 16 and r.classDistribution[0] == 16:
1506####                            print "best rule", orngCN2.ruleToString(r), r.quality
1507##                if qs:
1508##                    maxVals[l].append(max(qs))
1509##                else:
1510##                    maxVals[l].append(0)
1511            a = time.time()
1512
1513        # longer rule should always be better than shorter rule
1514        for l in range(self.oldStopper.max_rule_complexity):
1515            for i in range(len(maxVals[l])):
1516                if maxVals[l + 1][i] < maxVals[l][i]:
1517                    maxVals[l + 1][i] = maxVals[l][i]
1518##        print
1519##        for mi, m in enumerate(maxVals):
1520##            print "mi=",mi,m
1521
1522        mu, beta, perc = 1.0, 2.0, [0.0] * 10
1523        for mi, m in enumerate(maxVals):
1524##            if mi == 0:
1525##                mu, beta, perc = self.compParameters(m, mu, beta, perc)
1526##            else:
1527            mu, beta, perc = self.compParameters(m, mu, beta, perc, fixedBeta=True)
1528            extremeDists.append((mu, beta, perc))
1529            extremeDists.extend([(0, 1, [])] * (mi))
1530            if self.learner.debug:
1531                print mi, mu, beta, perc
1532
1533        self.restore_learner()
1534        return self.createEVDistList(extremeDists)
1535
1536class ABBeamFilter(BeamFilter):
1537    """
1538    ABBeamFilter: Filters beam;
1539        - leaves first N rules (by quality)
1540        - leaves first N rules that have only of arguments in condition part
1541    """
1542    def __init__(self, width=5):
1543        self.width = width
1544        self.pArgs = None
1545
1546    def __call__(self, rulesStar, examples, weight_id):
1547        newStar = RuleList()
1548        rulesStar.sort(lambda x, y:-cmp(x.quality, y.quality))
1549        argsNum = 0
1550        for r_i, r in enumerate(rulesStar):
1551            if r_i < self.width: # either is one of best "width" rules
1552                newStar.append(r)
1553            elif self.onlyPositives(r):
1554                if argsNum < self.width:
1555                    newStar.append(r)
1556                    argsNum += 1
1557        return newStar
1558
1559    def setArguments(self, domain, positive_arguments):
1560        self.pArgs = positive_arguments
1561        self.domain = domain
1562        self.argTab = [0] * len(self.domain.attributes)
1563        for arg in self.pArgs:
1564            for cond in arg.filter.conditions:
1565                self.argTab[cond.position] = 1
1566
1567    def onlyPositives(self, rule):
1568        if not self.pArgs:
1569            return False
1570
1571        ruleTab = [0] * len(self.domain.attributes)
1572        for cond in rule.filter.conditions:
1573            ruleTab[cond.position] = 1
1574        return map(operator.or_, ruleTab, self.argTab) == self.argTab
1575
1576
1577class CoversArguments:
1578    """
1579    Class determines if rule covers one out of a set of arguments.
1580    """
1581    def __init__(self, arguments):
1582        self.arguments = arguments
1583        self.indices = []
1584        for a in self.arguments:
1585            indNA = getattr(a.filter, "indices", None)
1586            if not indNA:
1587                a.filter.setattr("indices", CoversArguments.filterIndices(a.filter))
1588            self.indices.append(a.filter.indices)
1589
1590    def __call__(self, rule):
1591        if not self.indices:
1592            return False
1593        if not getattr(rule.filter, "indices", None):
1594            rule.filter.indices = CoversArguments.filterIndices(rule.filter)
1595        for index in self.indices:
1596            if map(operator.or_, rule.filter.indices, index) == rule.filter.indices:
1597                return True
1598        return False
1599
1600    def filterIndices(filter):
1601        if not filter.domain:
1602            return []
1603        ind = [0] * len(filter.domain.attributes)
1604        for c in filter.conditions:
1605            ind[c.position] = operator.or_(ind[c.position],
1606                                         CoversArguments.conditionIndex(c))
1607        return ind
1608    filterIndices = staticmethod(filterIndices)
1609
1610    def conditionIndex(c):
1611        if isinstance(c, Orange.data.filter.ValueFilterContinuous):
1612            if (c.oper == Orange.data.filter.ValueFilter.GreaterEqual or
1613                c.oper == Orange.data.filter.ValueFilter.Greater):
1614                return 5# 0101
1615            elif (c.oper == Orange.data.filter.ValueFilter.LessEqual or
1616                  c.oper == Orange.data.filter.ValueFilter.Less):
1617                return 3 # 0011
1618            else:
1619                return c.oper
1620        else:
1621            return 1 # 0001
1622    conditionIndex = staticmethod(conditionIndex)
1623
1624    def oneSelectorToCover(ruleIndices, argIndices):
1625        at, type = -1, 0
1626        for r_i, ind in enumerate(ruleIndices):
1627            if not argIndices[r_i]:
1628                continue
1629            if at > -1 and not ind == argIndices[r_i]: # need two changes
1630                return (-1, 0)
1631            if not ind == argIndices[r_i]:
1632                if argIndices[r_i] in [1, 3, 5]:
1633                    at, type = r_i, argIndices[r_i]
1634                if argIndices[r_i] == 6:
1635                    if ind == 3:
1636                        at, type = r_i, 5
1637                    if ind == 5:
1638                        at, type = r_i, 3
1639        return at, type
1640    oneSelectorToCover = staticmethod(oneSelectorToCover)
1641
1642
1643class SelectorAdder(BeamRefiner):
1644    """
1645    Selector adder, this function is a refiner function:
1646       - refined rules are not consistent with any of negative arguments.
1647    """
1648    def __init__(self, example=None, not_allowed_selectors=[], argument_id=None,
1649                 discretizer=Orange.feature.discretization.Entropy(forceAttribute=True)):
1650        # required values - needed values of attributes
1651        self.example = example
1652        self.argument_id = argument_id
1653        self.not_allowed_selectors = not_allowed_selectors
1654        self.discretizer = discretizer
1655
1656    def __call__(self, oldRule, data, weight_id, target_class= -1):
1657        inNotAllowedSelectors = CoversArguments(self.not_allowed_selectors)
1658        new_rules = RuleList()
1659
1660        # get positive indices (selectors already in the rule)
1661        indices = getattr(oldRule.filter, "indices", None)
1662        if not indices:
1663            indices = CoversArguments.filterIndices(oldRule.filter)
1664            oldRule.filter.setattr("indices", indices)
1665
1666        # get negative indices (selectors that should not be in the rule)
1667        negative_indices = [0] * len(data.domain.attributes)
1668        for nA in self.not_allowed_selectors:
1669            #print indices, nA.filter.indices
1670            at_i, type_na = CoversArguments.oneSelectorToCover(indices, nA.filter.indices)
1671            if at_i > -1:
1672                negative_indices[at_i] = operator.or_(negative_indices[at_i], type_na)
1673
1674        #iterate through indices = attributes
1675        for i, ind in enumerate(indices):
1676            if not self.example[i] or self.example[i].isSpecial():
1677                continue
1678            if ind == 1:
1679                continue
1680            if data.domain[i].varType == Orange.feature.Type.Discrete and not negative_indices[i] == 1: # DISCRETE attribute
1681                if self.example:
1682                    values = [self.example[i]]
1683                else:
1684                    values = data.domain[i].values
1685                for v in values:
1686                    tempRule = oldRule.clone()
1687                    tempRule.filter.conditions.append(
1688                        Orange.data.filter.Discrete(
1689                            position=i,
1690                            values=[Orange.data.Value(data.domain[i], v)],
1691                            acceptSpecial=0))
1692                    tempRule.complexity += 1
1693                    tempRule.filter.indices[i] = 1 # 1 stands for discrete attribute (see CoversArguments.conditionIndex)
1694                    tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1695                    if len(tempRule.examples) < len(oldRule.examples):
1696                        new_rules.append(tempRule)
1697            elif data.domain[i].varType == Orange.feature.Type.Continuous and not negative_indices[i] == 7: # CONTINUOUS attribute
1698                try:
1699                    at = data.domain[i]
1700                    at_d = self.discretizer(at, oldRule.examples)
1701                except:
1702                    continue # discretization failed !
1703                # If discretization makes sense? then:
1704                if len(at_d.values) > 1:
1705                    for p in at_d.getValueFrom.transformer.points:
1706                        #LESS
1707                        if not negative_indices[i] == 3:
1708                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.LessEqual, p, target_class, 3)
1709                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] <= p:# and not inNotAllowedSelectors(tempRule):
1710                                new_rules.append(tempRule)
1711                        #GREATER
1712                        if not negative_indices[i] == 5:
1713                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.Greater, p, target_class, 5)
1714                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] > p:# and not inNotAllowedSelectors(tempRule):
1715                                new_rules.append(tempRule)
1716        for r in new_rules:
1717            r.parentRule = oldRule
1718            r.valuesFilter = r.filter.filter
1719        return new_rules
1720
1721    def getTempRule(self, oldRule, pos, oper, ref, target_class, atIndex):
1722        tempRule = oldRule.clone()
1723
1724        tempRule.filter.conditions.append(
1725            Orange.data.filter.ValueFilterContinuous(
1726                position=pos, oper=oper, ref=ref, acceptSpecial=0))
1727        tempRule.complexity += 1
1728        tempRule.filter.indices[pos] = operator.or_(tempRule.filter.indices[pos], atIndex) # from RuleCoversArguments.conditionIndex
1729        tempRule.filterAndStore(oldRule.examples, tempRule.weightID, target_class)
1730        return tempRule
1731
1732    def setCondition(self, oldRule, target_class, ci, condition):
1733        tempRule = oldRule.clone()
1734        tempRule.filter.conditions[ci] = condition
1735        tempRule.filter.conditions[ci].setattr("specialized", 1)
1736        tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1737        return tempRule
1738
1739SelectorAdder = deprecated_members({"notAllowedSelectors": "not_allowed_selectors",
1740                     "argumentID": "argument_id"})(SelectorAdder)
1741
1742# This filter is the ugliest code ever! Problem is with Orange, I had some problems with inheriting deepCopy
1743# I should take another look at it.
1744class ArgFilter(Orange.data.filter.Filter):
1745    """ This class implements AB-covering principle. """
1746    def __init__(self, argument_id=None, filter=Orange.data.filter.Values(), arg_example=None):
1747        self.filter = filter
1748        self.indices = getattr(filter, "indices", [])
1749        if not self.indices and len(filter.conditions) > 0:
1750            self.indices = CoversArguments.filterIndices(filter)
1751        self.argument_id = argument_id
1752        self.domain = self.filter.domain
1753        self.conditions = filter.conditions
1754        self.arg_example = arg_example
1755
1756    def condIn(self, cond): # is condition in the filter?
1757        condInd = ruleCoversArguments.conditionIndex(cond)
1758        if operator.or_(condInd, self.indices[cond.position]) == self.indices[cond.position]:
1759            return True
1760        return False
1761
1762    def __call__(self, example):
1763##        print "in", self.filter(example)#, self.filter.conditions[0](example)
1764##        print self.filter.conditions[1].values
1765        if self.filter(example) and example != self.arg_example:
1766            return True
1767        elif self.filter(example):
1768            try:
1769                if example[self.argument_id].value and len(example[self.argument_id].value.positiveArguments) > 0: # example has positive arguments
1770                    # conditions should cover at least one of the positive arguments
1771                    oneArgCovered = False
1772                    for pA in example[self.argument_id].value.positiveArguments:
1773                        argCovered = [self.condIn(c) for c in pA.filter.conditions]
1774                        oneArgCovered = oneArgCovered or len(argCovered) == sum(argCovered) #argCovered
1775                        if oneArgCovered:
1776                            break
1777                    if not oneArgCovered:
1778                        return False
1779                if example[self.argument_id].value and len(example[self.argument_id].value.negativeArguments) > 0: # example has negative arguments
1780                    # condition should not cover neither of negative arguments
1781                    for pN in example[self.argument_id].value.negativeArguments:
1782                        argCovered = [self.condIn(c) for c in pN.filter.conditions]
1783                        if len(argCovered) == sum(argCovered):
1784                            return False
1785            except:
1786                return True
1787            return True
1788        else:
1789            return False
1790
1791    def __setattr__(self, name, obj):
1792        self.__dict__[name] = obj
1793        self.filter.setattr(name, obj)
1794
1795    def deep_copy(self):
1796        newFilter = ArgFilter(argument_id=self.argument_id)
1797        newFilter.filter = Orange.data.filter.Values() #self.filter.deepCopy()
1798        newFilter.filter.conditions = self.filter.conditions[:]
1799        newFilter.domain = self.filter.domain
1800        newFilter.negate = self.filter.negate
1801        newFilter.conjunction = self.filter.conjunction
1802        newFilter.domain = self.filter.domain
1803        newFilter.conditions = newFilter.filter.conditions
1804        newFilter.indices = self.indices[:]
1805        return newFilter
1806
1807ArgFilter = deprecated_members({"argumentID": "argument_id"})(ArgFilter)
1808
1809class SelectorArgConditions(BeamRefiner):
1810    """
1811    Selector adder, this function is a refiner function:
1812      - refined rules are not consistent with any of negative arguments.
1813    """
1814    def __init__(self, example, allowed_selectors):
1815        # required values - needed values of attributes
1816        self.example = example
1817        self.allowed_selectors = allowed_selectors
1818
1819    def __call__(self, oldRule, data, weight_id, target_class= -1):
1820        if len(oldRule.filter.conditions) >= len(self.allowed_selectors):
1821            return RuleList()
1822        new_rules = RuleList()
1823        for c in self.allowed_selectors:
1824            # normal condition
1825            if not c.unspecialized_condition:
1826                tempRule = oldRule.clone()
1827                tempRule.filter.conditions.append(c)
1828                tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1829                if len(tempRule.examples) < len(oldRule.examples):
1830                    new_rules.append(tempRule)
1831            # unspecified condition
1832            else:
1833                # find all possible example values
1834                vals = {}
1835                for e in oldRule.examples:
1836                    if not e[c.position].isSpecial():
1837                        vals[str(e[c.position])] = 1
1838                values = vals.keys()
1839                # for each value make a condition
1840                for v in values:
1841                    tempRule = oldRule.clone()
1842                    tempRule.filter.conditions.append(
1843                        Orange.data.filter.ValueFilterContinuous(
1844                            position=c.position, oper=c.oper,
1845                            ref=float(v), acceptSpecial=0))
1846                    if tempRule(self.example):
1847                        tempRule.filterAndStore(
1848                            oldRule.examples, oldRule.weightID, target_class)
1849                        if len(tempRule.examples) < len(oldRule.examples):
1850                            new_rules.append(tempRule)
1851##        print " NEW RULES "
1852##        for r in new_rules:
1853##            print Orange.classification.rules.rule_to_string(r)
1854        for r in new_rules:
1855            r.parentRule = oldRule
1856##            print Orange.classification.rules.rule_to_string(r)
1857        return new_rules
1858
1859
1860class CrossValidation:
1861    def __init__(self, folds=5, random_generator=150):
1862        self.folds = folds
1863        self.random_generator = random_generator
1864
1865    def __call__(self, learner, examples, weight):
1866        res = orngTest.crossValidation([learner], (examples, weight), folds=self.folds, random_generator=self.random_generator)
1867        return self.get_prob_from_res(res, examples)
1868
1869    def get_prob_from_res(self, res, examples):
1870        prob_dist = Orange.core.DistributionList()
1871        for tex in res.results:
1872            d = Orange.statistics.Distribution(examples.domain.class_var)
1873            for di in range(len(d)):
1874                d[di] = tex.probabilities[0][di]
1875            prob_dist.append(d)
1876        return prob_dist
1877
1878
1879class PILAR:
1880    """
1881    PILAR (Probabilistic improvement of learning algorithms with rules).
1882    """
1883    def __init__(self, alternative_learner=None, min_cl_sig=0.5, min_beta=0.0, set_prefix_rules=False, optimize_betas=True):
1884        self.alternative_learner = alternative_learner
1885        self.min_cl_sig = min_cl_sig
1886        self.min_beta = min_beta
1887        self.set_prefix_rules = set_prefix_rules
1888        self.optimize_betas = optimize_betas
1889        self.selected_evaluation = CrossValidation(folds=5)
1890
1891    def __call__(self, rules, examples, weight=0):
1892        rules = self.add_null_rule(rules, examples, weight)
1893        if self.alternative_learner:
1894            prob_dist = self.selected_evaluation(self.alternative_learner, examples, weight)
1895            classifier = self.alternative_learner(examples, weight)
1896##            prob_dist = Orange.core.DistributionList()
1897##            for e in examples:
1898##                prob_dist.append(classifier(e,Orange.core.GetProbabilities))
1899            cl = RuleClassifier_logit(rules, self.min_cl_sig, self.min_beta, examples, weight, self.set_prefix_rules, self.optimize_betas, classifier, prob_dist)
1900        else:
1901            cl = RuleClassifier_logit(rules, self.min_cl_sig, self.min_beta, examples, weight, self.set_prefix_rules, self.optimize_betas)
1902
1903##        print "result"
1904        for ri, r in enumerate(cl.rules):
1905            cl.rules[ri].setattr("beta", cl.ruleBetas[ri])
1906##            if cl.ruleBetas[ri] > 0:
1907##                print Orange.classification.rules.rule_to_string(r), r.quality, cl.ruleBetas[ri]
1908        cl.all_rules = cl.rules
1909        cl.rules = self.sort_rules(cl.rules)
1910        cl.ruleBetas = [r.beta for r in cl.rules]
1911        cl.setattr("data", examples)
1912        return cl
1913
1914    def add_null_rule(self, rules, examples, weight):
1915        for cl in examples.domain.class_var:
1916            tmpRle = Rule()
1917            tmpRle.filter = Orange.data.filter.Values(domain=examples.domain)
1918            tmpRle.parentRule = None
1919            tmpRle.filterAndStore(examples, weight, int(cl))
1920            tmpRle.quality = tmpRle.class_distribution[int(cl)] / tmpRle.class_distribution.abs
1921            rules.append(tmpRle)
1922        return rules
1923
1924    def sort_rules(self, rules):
1925        new_rules = RuleList()
1926        foundRule = True
1927        while foundRule:
1928            foundRule = False
1929            bestRule = None
1930            for r in rules:
1931                if r in new_rules:
1932                    continue
1933                if r.beta < 0.01 and r.beta > -0.01:
1934                    continue
1935                if not bestRule:
1936                    bestRule = r
1937                    foundRule = True
1938                    continue
1939                if len(r.filter.conditions) < len(bestRule.filter.conditions):
1940                    bestRule = r
1941                    foundRule = True
1942                    continue
1943                if len(r.filter.conditions) == len(bestRule.filter.conditions) and r.beta > bestRule.beta:
1944                    bestRule = r
1945                    foundRule = True
1946                    continue
1947            if bestRule:
1948                new_rules.append(bestRule)
1949        return new_rules
1950
1951PILAR = deprecated_members({"sortRules": "sort_rules"})(PILAR)
1952
1953
1954class RuleClassifier_bestRule(RuleClassifier):
1955    """
1956    A very simple classifier, it takes the best rule of each class and
1957    normalizes probabilities.
1958    """
1959    def __init__(self, rules, examples, weight_id=0, **argkw):
1960        self.rules = rules
1961        self.examples = examples
1962        self.apriori = Orange.statistics.Distribution(examples.domain.class_var, examples, weight_id)
1963        self.apriori_prob = [a / self.apriori.abs for a in self.apriori]
1964        self.weight_id = weight_id
1965        self.__dict__.update(argkw)
1966        self.default_class_index = -1
1967
1968    @deprecated_keywords({"retRules": "ret_rules"})
1969    def __call__(self, example, result_type=Orange.classification.Classifier.GetValue, ret_rules=False):
1970        example = Orange.data.Instance(self.examples.domain, example)
1971        tempDist = Orange.statistics.Distribution(example.domain.class_var)
1972        best_rules = [None] * len(example.domain.class_var.values)
1973
1974        for r in self.rules:
1975            if r(example) and not self.default_class_index == int(r.classifier.default_val) and \
1976               (not best_rules[int(r.classifier.default_val)] or r.quality > tempDist[r.classifier.default_val]):
1977                tempDist[r.classifier.default_val] = r.quality
1978                best_rules[int(r.classifier.default_val)] = r
1979        for b in best_rules:
1980            if b:
1981                used = getattr(b, "used", 0.0)
1982                b.setattr("used", used + 1)
1983        nonCovPriorSum = sum([tempDist[i] == 0. and self.apriori_prob[i] or 0. for i in range(len(self.apriori_prob))])
1984        if tempDist.abs < 1.:
1985            residue = 1. - tempDist.abs
1986            for a_i, a in enumerate(self.apriori_prob):
1987                if tempDist[a_i] == 0.:
1988                    tempDist[a_i] = self.apriori_prob[a_i] * residue / nonCovPriorSum
1989            final_dist = tempDist #Orange.core.Distribution(example.domain.class_var)
1990        else:
1991            tempDist.normalize() # prior probability
1992            tmp_examples = Orange.data.Table(self.examples)
1993            for r in best_rules:
1994                if r:
1995                    tmp_examples = r.filter(tmp_examples)
1996            tmpDist = Orange.statistics.Distribution(tmp_examples.domain.class_var, tmp_examples, self.weight_id)
1997            tmpDist.normalize()
1998            probs = [0.] * len(self.examples.domain.class_var.values)
1999            for i in range(len(self.examples.domain.class_var.values)):
2000                probs[i] = tmpDist[i] + tempDist[i] * 2
2001            final_dist = Orange.statistics.Distribution(self.examples.domain.class_var)
2002            for cl_i, cl in enumerate(self.examples.domain.class_var):
2003                final_dist[cl] = probs[cl_i]
2004            final_dist.normalize()
2005
2006        if ret_rules: # Do you want to return rules with classification?
2007            if result_type == Orange.classification.Classifier.GetValue:
2008              return (final_dist.modus(), best_rules)
2009            if result_type == Orange.classification.Classifier.GetProbabilities:
2010              return (final_dist, best_rules)
2011            return (final_dist.modus(), final_dist, best_rules)
2012        if result_type == Orange.classification.Classifier.GetValue:
2013          return final_dist.modus()
2014        if result_type == Orange.classification.Classifier.GetProbabilities:
2015          return final_dist
2016        return (final_dist.modus(), final_dist)
2017
2018RuleClassifier_bestRule = deprecated_members({"defaultClassIndex": "default_class_index"})(RuleClassifier_bestRule)
Note: See TracBrowser for help on using the repository browser.