source: orange/Orange/classification/rules.py @ 10518:9127eb1fe9a5

Revision 10518:9127eb1fe9a5, 85.2 KB checked in by martin@…, 2 years ago (diff)

Improved learning of rules with ABCN2.

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