source: orange/Orange/classification/rules.py @ 10379:6bf831b779d4

Revision 10379:6bf831b779d4, 87.2 KB checked in by janezd <janez.demsar@…>, 2 years ago (diff)

Yet more fixes due to classification.rules refactoring

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 c1.position == c2.position and type(c1) == type(c2):
1362                    continue # same feature and type?
1363                if isinstance(c1, Orange.data.filter.ValueFilterDiscrete):
1364                    if type(c1.values[0]) != type(c2.values[0]) or \
1365                            c1.values[0] != c2.values[0]:
1366                        continue # same value?
1367                if isinstance(c1, Orange.data.filter.ValueFilterContinuous):
1368                    if c1.oper != c2.oper or c1.ref != c2.ref:
1369                        continue # same operator?
1370                found = True
1371                break
1372            except:
1373                pass
1374        if not found:
1375            return False
1376    return True
1377
1378# Miscellaneous - utility functions
1379def avg(l):
1380    if len(l) == 0:
1381        return 0.
1382    return sum(l) / len(l)
1383
1384def var(l):
1385    if len(l) < 2:
1386        return 0.
1387    av = avg(l)
1388    vars = [math.pow(li - av, 2) for li in l]
1389    return sum(vars) / (len(l) - 1)
1390
1391def median(l):
1392    if len(l) == 0:
1393        return 0.
1394    l.sort()
1395    le = len(l)
1396    if le % 2 == 1:
1397        return l[(le - 1) / 2]
1398    else:
1399        return (l[le / 2 - 1] + l[le / 2]) / 2
1400
1401def perc(l, p):
1402    l.sort()
1403    return l[int(math.floor(p * len(l)))]
1404
1405class EVDFitter:
1406    """ Randomizes a dataset and fits an extreme value distribution onto it. """
1407
1408    def __init__(self, learner, n=200, randomseed=100):
1409        self.learner = learner
1410        self.n = n
1411        self.randomseed = randomseed
1412        # initialize random seed to make experiments repeatable
1413        random.seed(self.randomseed)
1414
1415
1416    def createRandomDataSet(self, data):
1417        newData = Orange.data.Table(data)
1418        # shuffle data
1419        cl_num = newData.toNumpy("C")
1420        random.shuffle(cl_num[0][:, 0])
1421        clData = Orange.data.Table(Orange.data.Domain([newData.domain.classVar]), cl_num[0])
1422        for d_i, d in enumerate(newData):
1423            d[newData.domain.classVar] = clData[d_i][newData.domain.classVar]
1424        return newData
1425
1426    def createEVDistList(self, evdList):
1427        l = Orange.core.EVDistList()
1428        for el in evdList:
1429            l.append(Orange.core.EVDist(mu=el[0], beta=el[1], percentiles=el[2]))
1430        return l
1431
1432
1433    # estimated fisher tippett parameters for a set of values given in vals list (+ deciles)
1434    def compParameters(self, vals, oldMi, oldBeta, oldPercs, fixedBeta=False):
1435        # compute percentiles
1436        vals.sort()
1437        N = len(vals)
1438        percs = [avg(vals[int(float(N) * i / 10):int(float(N) * (i + 1) / 10)]) for i in range(10)]
1439        if N < 10:
1440            return oldMi, oldBeta, percs
1441        if not fixedBeta:
1442            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))))
1443        else:
1444            beta = oldBeta
1445        mi = max(oldMi, percs[-1] + beta * math.log(-math.log(0.95)))
1446        mi = percs[-1] + beta * math.log(-math.log(0.95))
1447        return max(oldMi, numpy.average(vals) - beta * 0.5772156649), beta, None
1448
1449    def prepare_learner(self):
1450        self.oldStopper = self.learner.ruleFinder.ruleStoppingValidator
1451        self.evaluator = self.learner.ruleFinder.evaluator
1452        self.refiner = self.learner.ruleFinder.refiner
1453        self.validator = self.learner.ruleFinder.validator
1454        self.ruleFilter = self.learner.ruleFinder.ruleFilter
1455        self.learner.ruleFinder.validator = None
1456        self.learner.ruleFinder.evaluator = Orange.core.RuleEvaluator_LRS()
1457        self.learner.ruleFinder.evaluator.storeRules = True
1458        self.learner.ruleFinder.ruleStoppingValidator = Orange.core.RuleValidator_LRS(alpha=1.0)
1459        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = 0
1460        self.learner.ruleFinder.refiner = BeamRefiner_Selector()
1461        self.learner.ruleFinder.ruleFilter = BeamFilter_Width(width=5)
1462
1463
1464    def restore_learner(self):
1465        self.learner.ruleFinder.evaluator = self.evaluator
1466        self.learner.ruleFinder.ruleStoppingValidator = self.oldStopper
1467        self.learner.ruleFinder.refiner = self.refiner
1468        self.learner.ruleFinder.validator = self.validator
1469        self.learner.ruleFinder.ruleFilter = self.ruleFilter
1470
1471    def computeEVD(self, data, weightID=0, target_class=0, progress=None):
1472        import time
1473        # prepare learned for distribution computation       
1474        self.prepare_learner()
1475
1476        # loop through N (sampling repetitions)
1477        extremeDists = [(0, 1, [])]
1478        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = self.oldStopper.max_rule_complexity
1479        maxVals = [[] for l in range(self.oldStopper.max_rule_complexity + 1)]
1480        for d_i in range(self.n):
1481            if not progress:
1482                if self.learner.debug:
1483                    print d_i,
1484            else:
1485                progress(float(d_i) / self.n, None)
1486            # create data set (remove and randomize)
1487            a = time.time()
1488            tempData = self.createRandomDataSet(data)
1489            a = time.time()
1490            self.learner.ruleFinder.evaluator.rules = RuleList()
1491            a = time.time()
1492            for l in range(self.oldStopper.max_rule_complexity + 2):
1493               self.learner.ruleFinder.evaluator.rules.append(None)
1494            a = time.time()
1495            # Next, learn a rule
1496            self.learner.ruleFinder(tempData, weightID, target_class, RuleList())
1497            a = time.time()
1498            for l in range(self.oldStopper.max_rule_complexity + 1):
1499                if self.learner.ruleFinder.evaluator.rules[l]:
1500                    maxVals[l].append(self.learner.ruleFinder.evaluator.rules[l].quality)
1501                else:
1502                    maxVals[l].append(0)
1503##                qs = [r.quality for r in self.learner.ruleFinder.evaluator.rules if r.complexity == l+1]
1504####                if qs:
1505####                    for r in self.learner.ruleFinder.evaluator.rules:
1506####                        if r.quality == max(qs) and r.classDistribution.abs == 16 and r.classDistribution[0] == 16:
1507####                            print "best rule", orngCN2.ruleToString(r), r.quality
1508##                if qs:
1509##                    maxVals[l].append(max(qs))
1510##                else:
1511##                    maxVals[l].append(0)
1512            a = time.time()
1513
1514        # longer rule should always be better than shorter rule
1515        for l in range(self.oldStopper.max_rule_complexity):
1516            for i in range(len(maxVals[l])):
1517                if maxVals[l + 1][i] < maxVals[l][i]:
1518                    maxVals[l + 1][i] = maxVals[l][i]
1519##        print
1520##        for mi, m in enumerate(maxVals):
1521##            print "mi=",mi,m
1522
1523        mu, beta, perc = 1.0, 2.0, [0.0] * 10
1524        for mi, m in enumerate(maxVals):
1525##            if mi == 0:
1526##                mu, beta, perc = self.compParameters(m, mu, beta, perc)
1527##            else:
1528            mu, beta, perc = self.compParameters(m, mu, beta, perc, fixedBeta=True)
1529            extremeDists.append((mu, beta, perc))
1530            extremeDists.extend([(0, 1, [])] * (mi))
1531            if self.learner.debug:
1532                print mi, mu, beta, perc
1533
1534        self.restore_learner()
1535        return self.createEVDistList(extremeDists)
1536
1537class ABBeamFilter(BeamFilter):
1538    """
1539    ABBeamFilter: Filters beam;
1540        - leaves first N rules (by quality)
1541        - leaves first N rules that have only of arguments in condition part
1542    """
1543    def __init__(self, width=5):
1544        self.width = width
1545        self.pArgs = None
1546
1547    def __call__(self, rulesStar, examples, weight_id):
1548        newStar = RuleList()
1549        rulesStar.sort(lambda x, y:-cmp(x.quality, y.quality))
1550        argsNum = 0
1551        for r_i, r in enumerate(rulesStar):
1552            if r_i < self.width: # either is one of best "width" rules
1553                newStar.append(r)
1554            elif self.onlyPositives(r):
1555                if argsNum < self.width:
1556                    newStar.append(r)
1557                    argsNum += 1
1558        return newStar
1559
1560    def setArguments(self, domain, positive_arguments):
1561        self.pArgs = positive_arguments
1562        self.domain = domain
1563        self.argTab = [0] * len(self.domain.attributes)
1564        for arg in self.pArgs:
1565            for cond in arg.filter.conditions:
1566                self.argTab[cond.position] = 1
1567
1568    def onlyPositives(self, rule):
1569        if not self.pArgs:
1570            return False
1571
1572        ruleTab = [0] * len(self.domain.attributes)
1573        for cond in rule.filter.conditions:
1574            ruleTab[cond.position] = 1
1575        return map(operator.or_, ruleTab, self.argTab) == self.argTab
1576
1577
1578class CoversArguments:
1579    """
1580    Class determines if rule covers one out of a set of arguments.
1581    """
1582    def __init__(self, arguments):
1583        self.arguments = arguments
1584        self.indices = []
1585        for a in self.arguments:
1586            indNA = getattr(a.filter, "indices", None)
1587            if not indNA:
1588                a.filter.setattr("indices", CoversArguments.filterIndices(a.filter))
1589            self.indices.append(a.filter.indices)
1590
1591    def __call__(self, rule):
1592        if not self.indices:
1593            return False
1594        if not getattr(rule.filter, "indices", None):
1595            rule.filter.indices = CoversArguments.filterIndices(rule.filter)
1596        for index in self.indices:
1597            if map(operator.or_, rule.filter.indices, index) == rule.filter.indices:
1598                return True
1599        return False
1600
1601    def filterIndices(filter):
1602        if not filter.domain:
1603            return []
1604        ind = [0] * len(filter.domain.attributes)
1605        for c in filter.conditions:
1606            ind[c.position] = operator.or_(ind[c.position],
1607                                         CoversArguments.conditionIndex(c))
1608        return ind
1609    filterIndices = staticmethod(filterIndices)
1610
1611    def conditionIndex(c):
1612        if isinstance(c, Orange.data.filter.ValueFilterContinuous):
1613            if (c.oper == Orange.data.filter.ValueFilter.GreaterEqual or
1614                c.oper == Orange.data.filter.ValueFilter.Greater):
1615                return 5# 0101
1616            elif (c.oper == Orange.data.filter.ValueFilter.LessEqual or
1617                  c.oper == Orange.data.filter.ValueFilter.Less):
1618                return 3 # 0011
1619            else:
1620                return c.oper
1621        else:
1622            return 1 # 0001
1623    conditionIndex = staticmethod(conditionIndex)
1624
1625    def oneSelectorToCover(ruleIndices, argIndices):
1626        at, type = -1, 0
1627        for r_i, ind in enumerate(ruleIndices):
1628            if not argIndices[r_i]:
1629                continue
1630            if at > -1 and not ind == argIndices[r_i]: # need two changes
1631                return (-1, 0)
1632            if not ind == argIndices[r_i]:
1633                if argIndices[r_i] in [1, 3, 5]:
1634                    at, type = r_i, argIndices[r_i]
1635                if argIndices[r_i] == 6:
1636                    if ind == 3:
1637                        at, type = r_i, 5
1638                    if ind == 5:
1639                        at, type = r_i, 3
1640        return at, type
1641    oneSelectorToCover = staticmethod(oneSelectorToCover)
1642
1643
1644class SelectorAdder(BeamRefiner):
1645    """
1646    Selector adder, this function is a refiner function:
1647       - refined rules are not consistent with any of negative arguments.
1648    """
1649    def __init__(self, example=None, not_allowed_selectors=[], argument_id=None,
1650                 discretizer=Orange.feature.discretization.Entropy(forceAttribute=True)):
1651        # required values - needed values of attributes
1652        self.example = example
1653        self.argument_id = argument_id
1654        self.not_allowed_selectors = not_allowed_selectors
1655        self.discretizer = discretizer
1656
1657    def __call__(self, oldRule, data, weight_id, target_class= -1):
1658        inNotAllowedSelectors = CoversArguments(self.not_allowed_selectors)
1659        new_rules = RuleList()
1660
1661        # get positive indices (selectors already in the rule)
1662        indices = getattr(oldRule.filter, "indices", None)
1663        if not indices:
1664            indices = CoversArguments.filterIndices(oldRule.filter)
1665            oldRule.filter.setattr("indices", indices)
1666
1667        # get negative indices (selectors that should not be in the rule)
1668        negative_indices = [0] * len(data.domain.attributes)
1669        for nA in self.not_allowed_selectors:
1670            #print indices, nA.filter.indices
1671            at_i, type_na = CoversArguments.oneSelectorToCover(indices, nA.filter.indices)
1672            if at_i > -1:
1673                negative_indices[at_i] = operator.or_(negative_indices[at_i], type_na)
1674
1675        #iterate through indices = attributes
1676        for i, ind in enumerate(indices):
1677            if not self.example[i] or self.example[i].isSpecial():
1678                continue
1679            if ind == 1:
1680                continue
1681            if data.domain[i].varType == Orange.feature.Type.Discrete and not negative_indices[i] == 1: # DISCRETE attribute
1682                if self.example:
1683                    values = [self.example[i]]
1684                else:
1685                    values = data.domain[i].values
1686                for v in values:
1687                    tempRule = oldRule.clone()
1688                    tempRule.filter.conditions.append(
1689                        Orange.data.filter.Discrete(
1690                            position=i,
1691                            values=[Orange.data.Value(data.domain[i], v)],
1692                            acceptSpecial=0))
1693                    tempRule.complexity += 1
1694                    tempRule.filter.indices[i] = 1 # 1 stands for discrete attribute (see CoversArguments.conditionIndex)
1695                    tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1696                    if len(tempRule.examples) < len(oldRule.examples):
1697                        new_rules.append(tempRule)
1698            elif data.domain[i].varType == Orange.feature.Type.Continuous and not negative_indices[i] == 7: # CONTINUOUS attribute
1699                try:
1700                    at = data.domain[i]
1701                    at_d = self.discretizer(at, oldRule.examples)
1702                except:
1703                    continue # discretization failed !
1704                # If discretization makes sense? then:
1705                if len(at_d.values) > 1:
1706                    for p in at_d.getValueFrom.transformer.points:
1707                        #LESS
1708                        if not negative_indices[i] == 3:
1709                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.LessEqual, p, target_class, 3)
1710                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] <= p:# and not inNotAllowedSelectors(tempRule):
1711                                new_rules.append(tempRule)
1712                        #GREATER
1713                        if not negative_indices[i] == 5:
1714                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.Greater, p, target_class, 5)
1715                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] > p:# and not inNotAllowedSelectors(tempRule):
1716                                new_rules.append(tempRule)
1717        for r in new_rules:
1718            r.parentRule = oldRule
1719            r.valuesFilter = r.filter.filter
1720        return new_rules
1721
1722    def getTempRule(self, oldRule, pos, oper, ref, target_class, atIndex):
1723        tempRule = oldRule.clone()
1724
1725        tempRule.filter.conditions.append(
1726            Orange.data.filter.ValueFilterContinuous(
1727                position=pos, oper=oper, ref=ref, acceptSpecial=0))
1728        tempRule.complexity += 1
1729        tempRule.filter.indices[pos] = operator.or_(tempRule.filter.indices[pos], atIndex) # from RuleCoversArguments.conditionIndex
1730        tempRule.filterAndStore(oldRule.examples, tempRule.weightID, target_class)
1731        return tempRule
1732
1733    def setCondition(self, oldRule, target_class, ci, condition):
1734        tempRule = oldRule.clone()
1735        tempRule.filter.conditions[ci] = condition
1736        tempRule.filter.conditions[ci].setattr("specialized", 1)
1737        tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1738        return tempRule
1739
1740SelectorAdder = deprecated_members({"notAllowedSelectors": "not_allowed_selectors",
1741                     "argumentID": "argument_id"})(SelectorAdder)
1742
1743# This filter is the ugliest code ever! Problem is with Orange, I had some problems with inheriting deepCopy
1744# I should take another look at it.
1745class ArgFilter(Orange.data.filter.Filter):
1746    """ This class implements AB-covering principle. """
1747    def __init__(self, argument_id=None, filter=Orange.data.filter.Values(), arg_example=None):
1748        self.filter = filter
1749        self.indices = getattr(filter, "indices", [])
1750        if not self.indices and len(filter.conditions) > 0:
1751            self.indices = CoversArguments.filterIndices(filter)
1752        self.argument_id = argument_id
1753        self.domain = self.filter.domain
1754        self.conditions = filter.conditions
1755        self.arg_example = arg_example
1756
1757    def condIn(self, cond): # is condition in the filter?
1758        condInd = ruleCoversArguments.conditionIndex(cond)
1759        if operator.or_(condInd, self.indices[cond.position]) == self.indices[cond.position]:
1760            return True
1761        return False
1762
1763    def __call__(self, example):
1764##        print "in", self.filter(example)#, self.filter.conditions[0](example)
1765##        print self.filter.conditions[1].values
1766        if self.filter(example) and example != self.arg_example:
1767            return True
1768        elif self.filter(example):
1769            try:
1770                if example[self.argument_id].value and len(example[self.argument_id].value.positiveArguments) > 0: # example has positive arguments
1771                    # conditions should cover at least one of the positive arguments
1772                    oneArgCovered = False
1773                    for pA in example[self.argument_id].value.positiveArguments:
1774                        argCovered = [self.condIn(c) for c in pA.filter.conditions]
1775                        oneArgCovered = oneArgCovered or len(argCovered) == sum(argCovered) #argCovered
1776                        if oneArgCovered:
1777                            break
1778                    if not oneArgCovered:
1779                        return False
1780                if example[self.argument_id].value and len(example[self.argument_id].value.negativeArguments) > 0: # example has negative arguments
1781                    # condition should not cover neither of negative arguments
1782                    for pN in example[self.argument_id].value.negativeArguments:
1783                        argCovered = [self.condIn(c) for c in pN.filter.conditions]
1784                        if len(argCovered) == sum(argCovered):
1785                            return False
1786            except:
1787                return True
1788            return True
1789        else:
1790            return False
1791
1792    def __setattr__(self, name, obj):
1793        self.__dict__[name] = obj
1794        self.filter.setattr(name, obj)
1795
1796    def deep_copy(self):
1797        newFilter = ArgFilter(argument_id=self.argument_id)
1798        newFilter.filter = Orange.data.filter.Values() #self.filter.deepCopy()
1799        newFilter.filter.conditions = self.filter.conditions[:]
1800        newFilter.domain = self.filter.domain
1801        newFilter.negate = self.filter.negate
1802        newFilter.conjunction = self.filter.conjunction
1803        newFilter.domain = self.filter.domain
1804        newFilter.conditions = newFilter.filter.conditions
1805        newFilter.indices = self.indices[:]
1806        return newFilter
1807
1808ArgFilter = deprecated_members({"argumentID": "argument_id"})(ArgFilter)
1809
1810class SelectorArgConditions(BeamRefiner):
1811    """
1812    Selector adder, this function is a refiner function:
1813      - refined rules are not consistent with any of negative arguments.
1814    """
1815    def __init__(self, example, allowed_selectors):
1816        # required values - needed values of attributes
1817        self.example = example
1818        self.allowed_selectors = allowed_selectors
1819
1820    def __call__(self, oldRule, data, weight_id, target_class= -1):
1821        if len(oldRule.filter.conditions) >= len(self.allowed_selectors):
1822            return RuleList()
1823        new_rules = RuleList()
1824        for c in self.allowed_selectors:
1825            # normal condition
1826            if not c.unspecialized_condition:
1827                tempRule = oldRule.clone()
1828                tempRule.filter.conditions.append(c)
1829                tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1830                if len(tempRule.examples) < len(oldRule.examples):
1831                    new_rules.append(tempRule)
1832            # unspecified condition
1833            else:
1834                # find all possible example values
1835                vals = {}
1836                for e in oldRule.examples:
1837                    if not e[c.position].isSpecial():
1838                        vals[str(e[c.position])] = 1
1839                values = vals.keys()
1840                # for each value make a condition
1841                for v in values:
1842                    tempRule = oldRule.clone()
1843                    tempRule.filter.conditions.append(
1844                        Orange.data.filter.ValueFilterContinuous(
1845                            position=c.position, oper=c.oper,
1846                            ref=float(v), acceptSpecial=0))
1847                    if tempRule(self.example):
1848                        tempRule.filterAndStore(
1849                            oldRule.examples, oldRule.weightID, target_class)
1850                        if len(tempRule.examples) < len(oldRule.examples):
1851                            new_rules.append(tempRule)
1852##        print " NEW RULES "
1853##        for r in new_rules:
1854##            print Orange.classification.rules.rule_to_string(r)
1855        for r in new_rules:
1856            r.parentRule = oldRule
1857##            print Orange.classification.rules.rule_to_string(r)
1858        return new_rules
1859
1860
1861class CrossValidation:
1862    def __init__(self, folds=5, random_generator=150):
1863        self.folds = folds
1864        self.random_generator = random_generator
1865
1866    def __call__(self, learner, examples, weight):
1867        res = orngTest.crossValidation([learner], (examples, weight), folds=self.folds, random_generator=self.random_generator)
1868        return self.get_prob_from_res(res, examples)
1869
1870    def get_prob_from_res(self, res, examples):
1871        prob_dist = Orange.core.DistributionList()
1872        for tex in res.results:
1873            d = Orange.statistics.Distribution(examples.domain.class_var)
1874            for di in range(len(d)):
1875                d[di] = tex.probabilities[0][di]
1876            prob_dist.append(d)
1877        return prob_dist
1878
1879
1880class PILAR:
1881    """
1882    PILAR (Probabilistic improvement of learning algorithms with rules).
1883    """
1884    def __init__(self, alternative_learner=None, min_cl_sig=0.5, min_beta=0.0, set_prefix_rules=False, optimize_betas=True):
1885        self.alternative_learner = alternative_learner
1886        self.min_cl_sig = min_cl_sig
1887        self.min_beta = min_beta
1888        self.set_prefix_rules = set_prefix_rules
1889        self.optimize_betas = optimize_betas
1890        self.selected_evaluation = CrossValidation(folds=5)
1891
1892    def __call__(self, rules, examples, weight=0):
1893        rules = self.add_null_rule(rules, examples, weight)
1894        if self.alternative_learner:
1895            prob_dist = self.selected_evaluation(self.alternative_learner, examples, weight)
1896            classifier = self.alternative_learner(examples, weight)
1897##            prob_dist = Orange.core.DistributionList()
1898##            for e in examples:
1899##                prob_dist.append(classifier(e,Orange.core.GetProbabilities))
1900            cl = RuleClassifier_logit(rules, self.min_cl_sig, self.min_beta, examples, weight, self.set_prefix_rules, self.optimize_betas, classifier, prob_dist)
1901        else:
1902            cl = RuleClassifier_logit(rules, self.min_cl_sig, self.min_beta, examples, weight, self.set_prefix_rules, self.optimize_betas)
1903
1904##        print "result"
1905        for ri, r in enumerate(cl.rules):
1906            cl.rules[ri].setattr("beta", cl.ruleBetas[ri])
1907##            if cl.ruleBetas[ri] > 0:
1908##                print Orange.classification.rules.rule_to_string(r), r.quality, cl.ruleBetas[ri]
1909        cl.all_rules = cl.rules
1910        cl.rules = self.sort_rules(cl.rules)
1911        cl.ruleBetas = [r.beta for r in cl.rules]
1912        cl.setattr("data", examples)
1913        return cl
1914
1915    def add_null_rule(self, rules, examples, weight):
1916        for cl in examples.domain.class_var:
1917            tmpRle = Rule()
1918            tmpRle.filter = Orange.data.filter.Values(domain=examples.domain)
1919            tmpRle.parentRule = None
1920            tmpRle.filterAndStore(examples, weight, int(cl))
1921            tmpRle.quality = tmpRle.class_distribution[int(cl)] / tmpRle.class_distribution.abs
1922            rules.append(tmpRle)
1923        return rules
1924
1925    def sort_rules(self, rules):
1926        new_rules = RuleList()
1927        foundRule = True
1928        while foundRule:
1929            foundRule = False
1930            bestRule = None
1931            for r in rules:
1932                if r in new_rules:
1933                    continue
1934                if r.beta < 0.01 and r.beta > -0.01:
1935                    continue
1936                if not bestRule:
1937                    bestRule = r
1938                    foundRule = True
1939                    continue
1940                if len(r.filter.conditions) < len(bestRule.filter.conditions):
1941                    bestRule = r
1942                    foundRule = True
1943                    continue
1944                if len(r.filter.conditions) == len(bestRule.filter.conditions) and r.beta > bestRule.beta:
1945                    bestRule = r
1946                    foundRule = True
1947                    continue
1948            if bestRule:
1949                new_rules.append(bestRule)
1950        return new_rules
1951
1952PILAR = deprecated_members({"sortRules": "sort_rules"})(PILAR)
1953
1954
1955class RuleClassifier_bestRule(RuleClassifier):
1956    """
1957    A very simple classifier, it takes the best rule of each class and
1958    normalizes probabilities.
1959    """
1960    def __init__(self, rules, examples, weight_id=0, **argkw):
1961        self.rules = rules
1962        self.examples = examples
1963        self.apriori = Orange.statistics.Distribution(examples.domain.class_var, examples, weight_id)
1964        self.apriori_prob = [a / self.apriori.abs for a in self.apriori]
1965        self.weight_id = weight_id
1966        self.__dict__.update(argkw)
1967        self.default_class_index = -1
1968
1969    @deprecated_keywords({"retRules": "ret_rules"})
1970    def __call__(self, example, result_type=Orange.classification.Classifier.GetValue, ret_rules=False):
1971        example = Orange.data.Instance(self.examples.domain, example)
1972        tempDist = Orange.statistics.Distribution(example.domain.class_var)
1973        best_rules = [None] * len(example.domain.class_var.values)
1974
1975        for r in self.rules:
1976            if r(example) and not self.default_class_index == int(r.classifier.default_val) and \
1977               (not best_rules[int(r.classifier.default_val)] or r.quality > tempDist[r.classifier.default_val]):
1978                tempDist[r.classifier.default_val] = r.quality
1979                best_rules[int(r.classifier.default_val)] = r
1980        for b in best_rules:
1981            if b:
1982                used = getattr(b, "used", 0.0)
1983                b.setattr("used", used + 1)
1984        nonCovPriorSum = sum([tempDist[i] == 0. and self.apriori_prob[i] or 0. for i in range(len(self.apriori_prob))])
1985        if tempDist.abs < 1.:
1986            residue = 1. - tempDist.abs
1987            for a_i, a in enumerate(self.apriori_prob):
1988                if tempDist[a_i] == 0.:
1989                    tempDist[a_i] = self.apriori_prob[a_i] * residue / nonCovPriorSum
1990            final_dist = tempDist #Orange.core.Distribution(example.domain.class_var)
1991        else:
1992            tempDist.normalize() # prior probability
1993            tmp_examples = Orange.data.Table(self.examples)
1994            for r in best_rules:
1995                if r:
1996                    tmp_examples = r.filter(tmp_examples)
1997            tmpDist = Orange.statistics.Distribution(tmp_examples.domain.class_var, tmp_examples, self.weight_id)
1998            tmpDist.normalize()
1999            probs = [0.] * len(self.examples.domain.class_var.values)
2000            for i in range(len(self.examples.domain.class_var.values)):
2001                probs[i] = tmpDist[i] + tempDist[i] * 2
2002            final_dist = Orange.statistics.Distribution(self.examples.domain.class_var)
2003            for cl_i, cl in enumerate(self.examples.domain.class_var):
2004                final_dist[cl] = probs[cl_i]
2005            final_dist.normalize()
2006
2007        if ret_rules: # Do you want to return rules with classification?
2008            if result_type == Orange.classification.Classifier.GetValue:
2009              return (final_dist.modus(), best_rules)
2010            if result_type == Orange.classification.Classifier.GetProbabilities:
2011              return (final_dist, best_rules)
2012            return (final_dist.modus(), final_dist, best_rules)
2013        if result_type == Orange.classification.Classifier.GetValue:
2014          return final_dist.modus()
2015        if result_type == Orange.classification.Classifier.GetProbabilities:
2016          return final_dist
2017        return (final_dist.modus(), final_dist)
2018
2019RuleClassifier_bestRule = deprecated_members({"defaultClassIndex": "default_class_index"})(RuleClassifier_bestRule)
Note: See TracBrowser for help on using the repository browser.