source: orange/Orange/classification/rules.py @ 10570:77b10f404f3b

Revision 10570:77b10f404f3b, 85.4 KB checked in by Martin Mozina <martin.mozina@…>, 2 years ago (diff)

Removed some bugs related to 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            aes = self.get_argumented_examples(dich_data)
625            aes = self.sort_arguments(aes, dich_data)
626            while aes:
627                if self.analyse_argument > -1 and \
628                   (isinstance(self.analyse_argument, Orange.core.Example) and not Orange.core.Example(dich_data.domain, self.analyse_argument) == aes[0] or \
629                    isinstance(self.analyse_argument, int) and not dich_data[self.analyse_argument] == aes[0]):
630                    aes = aes[1:]
631                    continue
632                ae = aes[0]
633                rule = self.learn_argumented_rule(ae, dich_data, weight_id) # target class is always first class (0)
634                if self.debug and rule:
635                    print "learned arg rule", Orange.classification.rules.rule_to_string(rule)
636                elif self.debug:
637                    print "no rule came out of ", ae
638                if rule:
639                    rules.append(rule)
640                    aes = filter(lambda x: not rule(x), aes)
641                else:
642                    aes = aes[1:]
643
644            if not progress and self.debug:
645                print " arguments finished ... "
646
647            # remove all examples covered by rules
648            for rule in rules:
649                dich_data = self.remove_covered_examples(rule, dich_data, weight_id, True)
650            if progress:
651                progress(self.remaining_probability(dich_data), None)
652
653            # learn normal rules on remaining examples
654            if self.analyse_argument == -1:
655                self.turn_normal_mode(dich_data, weight_id, cl_i)
656                while dich_data:
657                    # learn a rule
658                    rule, good_rule = self.learn_normal_rule(dich_data, weight_id, self.apriori)
659                    if not rule:
660                        break
661                    if self.debug:
662                        if good_rule:
663                            print "rule learned: ", rule_to_string(rule), rule.quality
664                        else:
665                            print "rule only to influence learning: ", rule_to_string(rule), rule.quality
666                           
667                    dich_data = self.remove_covered_examples(rule, dich_data, weight_id, good_rule)
668
669                    if progress:
670                        progress(self.remaining_probability(dich_data), None)
671                    if good_rule:
672                        rules.append(rule)
673                    if self.learn_one_rule:
674                        break
675
676            # prune unnecessary rules
677            rules = self.prune_unnecessary_rules(rules, dich_data, weight_id)
678
679            if self.add_sub_rules:
680                rules = self.add_sub_rules_call(rules, dich_data, weight_id)
681
682            # restore domain and class in rules, add them to all_rules
683            for r in rules:
684                all_rules.append(self.change_domain(r, cl, examples, weight_id))
685
686            if progress:
687                progress(1.0, None)
688        # create a classifier from all rules       
689        return self.create_classifier(all_rules, examples, weight_id)
690
691    def learn_argumented_rule(self, ae, examples, weight_id):
692        # prepare roots of rules from arguments
693        positive_args = self.init_pos_args(ae, examples, weight_id)
694        if not positive_args: # something wrong
695            raise "There is a problem with argumented example %s" % str(ae)
696            return None
697        if False in [p(ae) for p in positive_args]: # a positive argument is not covering this example
698            raise "One argument does not cover critical example: %s!"%str(ae)
699            return None
700        negative_args = self.init_neg_args(ae, examples, weight_id)
701
702        # set negative arguments in refiner
703        self.rule_finder.refiner.notAllowedSelectors = negative_args
704        self.rule_finder.refiner.example = ae
705        # set arguments to filter
706        self.rule_finder.ruleFilter.setArguments(examples.domain, positive_args)
707
708        # learn a rule
709        self.rule_finder.evaluator.bestRule = None
710        self.rule_finder(examples, weight_id, 0, positive_args)
711
712        # return best rule
713        return self.rule_finder.evaluator.bestRule
714
715    def prepare_settings(self, examples, weight_id, cl_i, progress):
716        # apriori distribution
717        self.apriori = Orange.statistics.distribution.Distribution(
718                                examples.domain.class_var, examples, weight_id)
719
720        # prepare covering mechanism
721        self.coverAndRemove = CovererAndRemover_Prob(examples, weight_id, 0, self.apriori, self.argument_id)
722        self.rule_finder.evaluator.probVar = examples.domain.getmeta(self.cover_and_remove.probAttribute)
723
724        # compute extreme distributions
725        # TODO: why evd and evd_this????
726        if self.rule_finder.evaluator.optimismReduction > 0 and not self.evd:
727            self.evd_this = self.evd_creator.computeEVD(examples, weight_id, target_class=0, progress=progress)
728        if self.evd:
729            self.evd_this = self.evd[cl_i]
730
731    def turn_ABML_mode(self, examples, weight_id, cl_i):
732        # evaluator
733        if self.rule_finder.evaluator.optimismReduction > 0 and self.argument_id:
734            if self.evd_arguments:
735                self.rule_finder.evaluator.evDistGetter.dists = self.evd_arguments[cl_i]
736            else:
737                self.rule_finder.evaluator.evDistGetter.dists = self.evd_this # self.evd_creator.computeEVD_example(examples, weight_id, target_class=0)
738        # rule refiner
739        self.rule_finder.refiner = self.refiner_arguments
740        self.rule_finder.refiner.argument_id = self.argument_id
741        self.rule_finder.ruleFilter = self.ruleFilter_arguments
742
743    def create_dich_class(self, examples, cl):
744        """
745        Create dichotomous class.
746        """
747        (newDomain, targetVal) = create_dichotomous_class(examples.domain, examples.domain.class_var, str(cl), negate=0)
748        newDomainmetas = newDomain.getmetas()
749        newDomain.addmeta(Orange.feature.Descriptor.new_meta_id(), examples.domain.class_var) # old class as meta
750        dichData = examples.select(newDomain)
751        if self.argument_id:
752            for d in dichData: # remove arguments given to other classes
753                if not d.getclass() == targetVal:
754                    d[self.argument_id] = "?"
755        return dichData
756
757    def get_argumented_examples(self, examples):
758        if not self.argument_id:
759            return None
760
761        # get argumented examples
762        return ArgumentFilter_hasSpecial()(examples, self.argument_id, target_class=0)
763
764    def sort_arguments(self, arg_examples, examples):
765        if not self.argument_id:
766            return None
767        evaluateAndSortArguments(examples, self.argument_id)
768        if len(arg_examples) > 0:
769            # sort examples by their arguments quality (using first argument as it has already been sorted)
770            sorted = arg_examples.native()
771            sorted.sort(lambda x, y:-cmp(x[self.argument_id].value.positive_arguments[0].quality,
772                                         y[self.argument_id].value.positive_arguments[0].quality))
773            return Orange.data.Table(examples.domain, sorted)
774        else:
775            return None
776
777    def turn_normal_mode(self, examples, weight_id, cl_i):
778        # evaluator
779        if self.rule_finder.evaluator.optimismReduction > 0:
780            if self.evd:
781                self.rule_finder.evaluator.evDistGetter.dists = self.evd[cl_i]
782            else:
783                self.rule_finder.evaluator.evDistGetter.dists = self.evd_this # self.evd_creator.computeEVD(examples, weight_id, target_class=0)
784        # rule refiner
785        self.rule_finder.refiner = self.refiner
786        self.rule_finder.ruleFilter = self.ruleFilter
787
788    def learn_normal_rule(self, examples, weight_id, apriori):
789        if hasattr(self.rule_finder.evaluator, "bestRule"):
790            self.rule_finder.evaluator.bestRule = None
791        rule = self.rule_finder(examples,weight_id,0,RuleList())
792        if hasattr(self.rule_finder.evaluator, "bestRule") and self.rule_finder.evaluator.returnExpectedProb:
793            if not self.rule_finder.evaluator.bestRule and rule.quality > 0:
794                return (rule, False)
795            rule = self.rule_finder.evaluator.bestRule
796            self.rule_finder.evaluator.bestRule = None
797        if self.postpruning:
798            rule = self.postpruning(rule,examples,weight_id,0, aprior)
799        return (rule, True)
800   
801
802    def remove_covered_examples(self, rule, examples, weight_id, good_rule):
803        if good_rule:
804            nexamples, nweight = self.cover_and_remove(rule, examples, weight_id, 0)
805        else:
806            nexamples, nweight = self.cover_and_remove.mark_examples_solved(rule,examples,weight_id,0)
807        return nexamples
808
809
810    def prune_unnecessary_rules(self, rules, examples, weight_id):
811        return self.cover_and_remove.getBestRules(rules, examples, weight_id)
812
813    def change_domain(self, rule, cl, examples, weight_id):
814        rule.filter = Orange.data.filter.Values(
815            domain=examples.domain, conditions=rule.filter.conditions)
816        rule.filterAndStore(examples, weight_id, cl)
817        if hasattr(rule, "learner") and hasattr(rule.learner, "arg_example"):
818            rule.learner.arg_example = Orange.data.Instance(examples.domain, rule.learner.arg_example)
819        return rule
820
821    def create_classifier(self, rules, examples, weight_id):
822        return self.classifier(rules, examples, weight_id)
823
824    def add_sub_rules_call(self, rules, examples, weight_id):
825        apriori = Orange.statistics.distribution.Distribution(
826                            examples.domain.class_var, examples, weight_id)
827        new_rules = RuleList()
828        for r in rules:
829            new_rules.append(r)
830
831        # loop through rules
832        for r in rules:
833            tmpList = RuleList()
834            tmpRle = r.clone()
835            tmpRle.filter.conditions = r.filter.conditions[:r.requiredConditions] # do not split argument
836            tmpRle.parentRule = None
837            tmpRle.filterAndStore(examples, weight_id, r.classifier.default_val)
838            tmpRle.complexity = 0
839            tmpList.append(tmpRle)
840            while tmpList and len(tmpList[0].filter.conditions) <= len(r.filter.conditions):
841                tmpList2 = RuleList()
842                for tmpRule in tmpList:
843                    # evaluate tmpRule
844                    oldREP = self.rule_finder.evaluator.returnExpectedProb
845                    self.rule_finder.evaluator.returnExpectedProb = False
846                    tmpRule.quality = self.rule_finder.evaluator(tmpRule, examples, weight_id, r.classifier.default_val, apriori)
847                    self.rule_finder.evaluator.returnExpectedProb = oldREP
848                tmpList.sort(lambda x, y:-cmp(x.quality, y.quality))
849                tmpList = tmpList[:self.ruleFilter.width]
850
851                for tmpRule in tmpList:
852                    # if rule not in rules already, add it to the list
853                    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:
854                        new_rules.append(tmpRule)
855                    # create new tmpRules, set parent Rule, append them to tmpList2
856                    if not True in [Orange.classification.rules.rules_equal(ri, tmpRule) for ri in new_rules]:
857                        for c in r.filter.conditions:
858                            tmpRule2 = tmpRule.clone()
859                            tmpRule2.parentRule = tmpRule
860                            tmpRule2.filter.conditions.append(c)
861                            tmpRule2.filterAndStore(examples, weight_id, r.classifier.default_val)
862                            tmpRule2.complexity += 1
863                            if tmpRule2.class_distribution.abs < tmpRule.class_distribution.abs:
864                                tmpList2.append(tmpRule2)
865                tmpList = tmpList2
866        return new_rules
867
868    def init_pos_args(self, ae, examples, weight_id):
869        pos_args = RuleList()
870        # prepare arguments
871        for p in ae[self.argument_id].value.positive_arguments:
872            new_arg = Rule(filter=ArgFilter(argument_id=self.argument_id,
873                                                   filter=self.newFilter_values(p.filter),
874                                                   arg_example=ae),
875                                                   complexity=0)
876            new_arg.valuesFilter = new_arg.filter.filter
877            pos_args.append(new_arg)
878
879
880        if hasattr(self.rule_finder.evaluator, "returnExpectedProb"):
881            old_exp = self.rule_finder.evaluator.returnExpectedProb
882            self.rule_finder.evaluator.returnExpectedProb = False
883
884        # argument pruning (all or just unfinished arguments)
885        # if pruning is chosen, then prune arguments if possible
886        for p in pos_args:
887            p.filterAndStore(examples, weight_id, 0)
888            if not p.learner:
889                p.learner = DefaultLearner(default_value=ae.getclass())
890            # pruning on: we check on all conditions and take only best
891            if self.prune_arguments:
892                allowed_conditions = [c for c in p.filter.conditions]
893                pruned_conditions = self.prune_arg_conditions(ae, allowed_conditions, examples, weight_id)
894                p.baseDist = Orange.statistics.distribution.Distribution(examples.domain.classVar, examples, weight_id)
895                p.filter.conditions = pruned_conditions
896                p.learner.setattr("arg_length", 0)
897
898            else: # prune only unspecified conditions
899                spec_conditions = [c for c in p.filter.conditions if not c.unspecialized_condition]
900                unspec_conditions = [c for c in p.filter.conditions if c.unspecialized_condition]
901                # let rule cover now all examples filtered by specified conditions
902                p.filter.conditions = spec_conditions
903                p.filterAndStore(examples, weight_id, 0)
904                p.baseDist = p.classDistribution
905                p.learner.setattr("arg_length", len(p.filter.conditions))
906                pruned_conditions = self.prune_arg_conditions(ae, unspec_conditions, p.examples, p.weightID)
907                p.filter.conditions.extend(pruned_conditions)
908                p.filter.filter.conditions.extend(pruned_conditions)
909                # if argument does not contain all unspecialized reasons, add those reasons with minimum values
910                at_oper_pairs = [(c.position, c.oper) for c in p.filter.conditions if type(c) == Orange.data.filter.ValueFilterContinuous]
911                for u in unspec_conditions:
912                    if not (u.position, u.oper) in at_oper_pairs:
913                        # find minimum value
914                        if u.oper == Orange.data.filter.ValueFilter.Greater or \
915                            u.oper == Orange.data.filter.ValueFilter.GreaterEqual:
916                            u.ref = min([float(e[u.position]) - 10. for e in p.examples])
917                        else:
918                            u.ref = max([float(e[u.position]) + 10. for e in p.examples])
919                        p.filter.conditions.append(u)
920                        p.filter.filter.conditions.append(u)
921
922        # set parameters to arguments
923        for p_i, p in enumerate(pos_args):
924            p.filterAndStore(examples, weight_id, 0)
925            p.filter.domain = examples.domain
926            p.classifier = p.learner(p.examples, p.weightID)
927            p.requiredConditions = len(p.filter.conditions)
928            p.learner.setattr("arg_example", ae)
929            p.complexity = len(p.filter.conditions)
930
931        if hasattr(self.rule_finder.evaluator, "returnExpectedProb"):
932            self.rule_finder.evaluator.returnExpectedProb = old_exp
933
934        return pos_args
935
936    def newFilter_values(self, filter):
937        newFilter = Orange.data.filter.Values()
938        newFilter.conditions = filter.conditions[:]
939        newFilter.domain = filter.domain
940        newFilter.negate = filter.negate
941        newFilter.conjunction = filter.conjunction
942        return newFilter
943
944    def init_neg_args(self, ae, examples, weight_id):
945        return ae[self.argument_id].value.negative_arguments
946
947    def remaining_probability(self, examples):
948        return self.cover_and_remove.covered_percentage(examples)
949
950    def prune_arg_conditions(self, crit_example, allowed_conditions, examples, weight_id):
951        if not allowed_conditions:
952            return []
953        cn2_learner = Orange.classification.rules.CN2UnorderedLearner()
954        cn2_learner.rule_finder = BeamFinder()
955        cn2_learner.rule_finder.refiner = SelectorArgConditions(crit_example, allowed_conditions)
956        cn2_learner.rule_finder.evaluator = Orange.classification.rules.MEstimateEvaluator(self.rule_finder.evaluator.m)
957        rule = cn2_learner.rule_finder(examples, weight_id, 0, RuleList())
958        return rule.filter.conditions
959
960ABCN2 = deprecated_members({"beamWidth": "beam_width",
961                     "ruleFinder": "rule_finder",
962                     "ruleStopping": "rule_stopping",
963                     "dataStopping": "data_stopping",
964                     "coverAndRemove": "cover_and_remove",
965                     "storeInstances": "store_instances",
966                     "targetClass": "target_class",
967                     "baseRules": "base_rules",
968                     "weightID": "weight_id",
969                     "argumentID": "argument_id"})(ABCN2)
970
971class CN2EVCUnorderedLearner(ABCN2):
972    """
973    A learner similar to CN2-SD (:obj:`CN2SDUnorderedLearner`) except that
974    it uses EVC for rule evaluation.
975
976    :param evaluator: an object that evaluates a rule from covered instances.
977        By default, weighted relative accuracy is used.
978    :type evaluator: :class:`~Orange.classification.rules.Evaluator`
979   
980    :param beam_width: width of the search beam.
981    :type beam_width: int
982   
983    :param alpha: significance level of the likelihood ratio statistics to
984        determine whether rule is better than the default rule.
985    :type alpha: float
986   
987    :param mult: multiplicator for weights of covered instances.
988    :type mult: float
989    """
990    def __init__(self, width=5, nsampling=100, rule_sig=1.0, att_sig=1.0, \
991        min_coverage=1., max_rule_complexity=5.):
992        ABCN2.__init__(self, width=width, nsampling=nsampling,
993            rule_sig=rule_sig, att_sig=att_sig, min_coverage=int(min_coverage),
994            max_rule_complexity=int(max_rule_complexity))
995
996class DefaultLearner(Orange.classification.Learner):
997    """
998    Default learner - returns default classifier with predefined output class.
999    """
1000    def __init__(self, default_value=None):
1001        self.default_value = default_value
1002    def __call__(self, examples, weight_id=0):
1003        return Orange.classification.ConstantClassifier(self.default_value, defaultDistribution=Orange.statistics.distribution.Distribution(examples.domain.class_var, examples, weight_id))
1004
1005class ABCN2Ordered(ABCN2):
1006    """
1007    Rules learned by ABCN2 are ordered and used as a decision list.
1008    """
1009    def __init__(self, argument_id=0, **kwds):
1010        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1011        self.classifier.set_prefix_rules = True
1012        self.classifier.optimize_betas = False
1013
1014class ABCN2M(ABCN2):
1015    """
1016    Argument based rule learning with m-estimate as evaluation function.
1017    """
1018    def __init__(self, argument_id=0, **kwds):
1019        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1020        self.opt_reduction = 0
1021        self.rule_finder.evaluator.optimismReduction = self.opt_reduction
1022        self.classifier = CN2UnorderedClassifier
1023
1024class ABCN2MLRC(ABCN2):
1025    """
1026    Argument based rule learning with m-estimate as evaluation function. LRC is used as a classification method.
1027    """
1028    def __init__(self, argument_id=0, **kwds):
1029        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1030        self.opt_reduction = 0
1031        self.rule_finder.evaluator.optimismReduction = self.opt_reduction
1032
1033class ABCN2_StandardClassification(ABCN2):
1034    """
1035    Argument based rule learning with the original classification technique.
1036    """
1037    def __init__(self, argument_id=0, **kwds):
1038        ABCN2.__init__(self, argument_id=argument_id, **kwds)
1039        self.classifier = CN2UnorderedClassifier
1040
1041
1042class Stopping_Apriori(StoppingCriteria):
1043    def __init__(self, apriori=None):
1044        self.apriori = None
1045
1046    def __call__(self, rules, rule, instances, data):
1047        if not self.apriori:
1048            return False
1049        if not type(rule.classifier) == Orange.classification.ConstantClassifier:
1050            return False
1051        ruleAcc = rule.class_distribution[rule.classifier.default_val] / rule.class_distribution.abs
1052        aprioriAcc = self.apriori[rule.classifier.default_val] / self.apriori.abs
1053        if ruleAcc > aprioriAcc:
1054            return False
1055        return True
1056
1057
1058class Stopping_SetRules(StoppingCriteria):
1059    def __init__(self, validator):
1060        self.rule_stopping = StoppingCriteria_NegativeDistribution()
1061        self.validator = validator
1062
1063    def __call__(self, rules, rule, instances, data):
1064        ru_st = self.rule_stopping(rules, rule, instances, data)
1065        if not ru_st:
1066            self.validator.rules.append(rule)
1067        return bool(ru_st)
1068
1069
1070class LengthValidator(Validator):
1071    """ prune rules with more conditions than self.length. """
1072    def __init__(self, length= -1):
1073        self.length = length
1074
1075    def __call__(self, rule, data, weight_id, target_class, apriori):
1076        if self.length >= 0:
1077            return len(rule.filter.conditions) <= self.length
1078        return True
1079
1080
1081class NoDuplicatesValidator(Validator):
1082    def __init__(self, alpha=.05, min_coverage=0, max_rule_length=0, rules=RuleList()):
1083        self.rules = rules
1084        self.validator = Validator_LRS(alpha=alpha, \
1085            min_coverage=min_coverage, max_rule_length=max_rule_length)
1086
1087    def __call__(self, rule, data, weight_id, target_class, apriori):
1088        if rule_in_set(rule, self.rules):
1089            return False
1090        return bool(self.validator(rule, data, weight_id, target_class, apriori))
1091
1092
1093
1094class Classifier_BestRule(RuleClassifier):
1095    def __init__(self, rules, instances, weight_id=0, **argkw):
1096        self.rules = rules
1097        self.examples = instances
1098        self.class_var = instances.domain.class_var
1099        self.__dict__.update(argkw)
1100        self.prior = Orange.statistics.distribution.Distribution(
1101                    instances.domain.class_var, instances)
1102
1103    def __call__(self, instance, result_type=Orange.classification.Classifier.GetValue):
1104        retDist = Orange.statistics.distribution.Distribution(instance.domain.class_var)
1105        bestRule = None
1106        for r in self.rules:
1107            if r(instance) and (not bestRule or r.quality > bestRule.quality):
1108                for v_i, v in enumerate(instance.domain.class_var):
1109                    retDist[v_i] = r.class_distribution[v_i]
1110                bestRule = r
1111        if not bestRule:
1112            retDist = self.prior
1113        else:
1114            bestRule.used += 1
1115        sumdist = sum(retDist)
1116        if sumdist > 0.0:
1117            for c in self.examples.domain.class_var:
1118                retDist[c] /= sumdisc
1119        else:
1120            retDist.normalize()
1121        # return classifier(instance, result_type=result_type)
1122        if result_type == Orange.classification.Classifier.GetValue:
1123          return retDist.modus()
1124        if result_type == Orange.classification.Classifier.GetProbabilities:
1125          return retDist
1126        return (retDist.modus(), retDist)
1127
1128    def __str__(self):
1129        retStr = ""
1130        for r in self.rules:
1131            retStr += rule_to_string(r) + " " + str(r.class_distribution) + "\n"
1132        return retStr
1133
1134
1135class CovererAndRemover_MultWeights(CovererAndRemover):
1136    """
1137    Covering and removing of instances using weight multiplication.
1138   
1139    :param mult: weighting multiplication factor
1140    :type mult: float   
1141    """
1142
1143    def __init__(self, mult=0.7):
1144        self.mult = mult
1145    def __call__(self, rule, instances, weights, target_class):
1146        if not weights:
1147            weights = Orange.feature.Descriptor.new_meta_id()
1148            instances.addMetaAttribute(weights, 1.)
1149            instances.domain.addmeta(weights, Orange.feature.\
1150                Continuous("weights-" + str(weights)), True)
1151        newWeightsID = Orange.feature.Descriptor.new_meta_id()
1152        instances.addMetaAttribute(newWeightsID, 1.)
1153        instances.domain.addmeta(newWeightsID, Orange.feature.\
1154            Continuous("weights-" + str(newWeightsID)), True)
1155        for instance in instances:
1156            if rule(instance) and instance.getclass() == rule.classifier(\
1157                instance, Orange.classification.Classifier.GetValue):
1158                instance[newWeightsID] = instance[weights] * self.mult
1159            else:
1160                instance[newWeightsID] = instance[weights]
1161        return (instances, newWeightsID)
1162
1163
1164class CovererAndRemover_AddWeights(CovererAndRemover):
1165    """
1166    Covering and removing of instances using weight addition.
1167   
1168    """
1169
1170    def __call__(self, rule, instances, weights, target_class):
1171        if not weights:
1172            weights = Orange.feature.Descriptor.new_meta_id()
1173            instances.addMetaAttribute(weights, 1.)
1174            instances.domain.addmeta(weights, Orange.feature.\
1175                Continuous("weights-" + str(weights)), True)
1176        try:
1177            coverage = instances.domain.getmeta("Coverage")
1178        except:
1179            coverage = Orange.feature.Continuous("Coverage")
1180            instances.domain.addmeta(Orange.feature.Descriptor.new_meta_id(), coverage, True)
1181            instances.addMetaAttribute(coverage, 0.0)
1182        newWeightsID = Orange.feature.Descriptor.new_meta_id()
1183        instances.addMetaAttribute(newWeightsID, 1.)
1184        instances.domain.addmeta(newWeightsID, Orange.feature.\
1185            Continuous("weights-" + str(newWeightsID)), True)
1186        for instance in instances:
1187            if rule(instance) and instance.getclass() == rule.classifier(instance, \
1188                    Orange.classification.Classifier.GetValue):
1189                try:
1190                    instance[coverage] += 1.0
1191                except:
1192                    instance[coverage] = 1.0
1193                instance[newWeightsID] = 1.0 / (instance[coverage] + 1)
1194            else:
1195                instance[newWeightsID] = instance[weights]
1196        return (instances, newWeightsID)
1197
1198
1199class CovererAndRemover_Prob(CovererAndRemover):
1200    """ This class impements probabilistic covering. """
1201    def __init__(self, examples, weight_id, target_class, apriori, argument_id):
1202        self.best_rule = [None] * len(examples)
1203        self.prob_attribute = Orange.feature.Descriptor.new_meta_id()
1204        self.apriori_prob = apriori[target_class] / apriori.abs
1205        examples.addMetaAttribute(self.prob_attribute, self.apriori_prob)
1206        examples.domain.addmeta(self.prob_attribute,
1207            Orange.feature.Continuous("Probs"))
1208        self.argument_id = argument_id
1209
1210    def getBestRules(self, current_rules, examples, weight_id):
1211        best_rules = RuleList()
1212        for r_i, r in enumerate(self.best_rule):
1213            if r and not rule_in_set(r, best_rules) and int(examples[r_i].getclass()) == int(r.classifier.default_value):
1214                if hasattr(r.learner, "arg_example"):
1215                    r.setattr("best_example", r.learner.arg_example)
1216                else:
1217                    r.setattr("best_example", examples[r_i])
1218                best_rules.append(r)
1219        return best_rules
1220
1221    def __call__(self, rule, examples, weights, target_class):
1222        """ if example has an argument, then the rule must be consistent with the argument. """
1223        example = getattr(rule.learner, "arg_example", None)
1224        if example:
1225            for ei, e in enumerate(examples):
1226                if e == example:
1227                    e[self.prob_attribute] = rule.quality+0.001 # 0.001 is added to avoid numerical errors
1228                    self.best_rule[ei]=rule
1229        else:       
1230            for ei, e in enumerate(examples):
1231                if rule(e) and rule.quality>e[self.prob_attribute]:
1232                    e[self.prob_attribute] = rule.quality+0.001 # 0.001 is added to avoid numerical errors
1233                    self.best_rule[ei]=rule
1234        return (examples, weights)
1235
1236    def mark_examples_solved(self, rule, examples, weights, target_class):
1237        for ei, e in enumerate(examples):
1238            if rule(e):
1239                e[self.prob_attribute] = 1.0
1240        return (examples, weights)
1241
1242    def covered_percentage(self, examples):
1243        p = 0.0
1244        for ei, e in enumerate(examples):
1245            p += (e[self.prob_attribute] - self.apriori_prob) / (1.0 - self.apriori_prob)
1246        return p / len(examples)
1247
1248
1249
1250
1251@deprecated_keywords({"showDistribution": "show_distribution"})
1252def rule_to_string(rule, show_distribution=True):
1253    """
1254    Write a string presentation of rule in human readable format.
1255   
1256    :param rule: rule to pretty-print.
1257    :type rule: :class:`~Orange.classification.rules.Rule`
1258   
1259    :param show_distribution: determines whether presentation should also
1260        contain the distribution of covered instances
1261    :type show_distribution: bool
1262   
1263    """
1264    def selectSign(oper):
1265        if oper == Orange.data.filter.ValueFilter.Less:
1266            return "<"
1267        elif oper == Orange.data.filter.ValueFilter.LessEqual:
1268            return "<="
1269        elif oper == Orange.data.filter.ValueFilter.Greater:
1270            return ">"
1271        elif oper == Orange.data.filter.ValueFilter.GreaterEqual:
1272            return ">="
1273        else: return "="
1274
1275    if not rule:
1276        return "None"
1277    conds = rule.filter.conditions
1278    domain = rule.filter.domain
1279
1280    ret = "IF "
1281    if len(conds) == 0:
1282        ret = ret + "TRUE"
1283
1284    for i, c in enumerate(conds):
1285        if i > 0:
1286            ret += " AND "
1287        if isinstance(c, Orange.data.filter.ValueFilterDiscrete):
1288            ret += domain[c.position].name + "=" + str([domain[c.position].\
1289                values[int(v)] for v in c.values])
1290        elif isinstance(c, Orange.data.filter.ValueFilterContinuous):
1291            ret += domain[c.position].name + selectSign(c.oper) + str(c.ref)
1292    if isinstance(rule.classifier, Orange.classification.ConstantClassifier) \
1293            and rule.classifier.default_val:
1294        ret = ret + " THEN " + domain.class_var.name + "=" + \
1295            str(rule.classifier.default_value)
1296        if show_distribution:
1297            ret += str(rule.class_distribution)
1298    elif isinstance(rule.classifier, Orange.classification.ConstantClassifier) \
1299            and isinstance(domain.class_var, Orange.feature.Discrete):
1300        ret = ret + " THEN " + domain.class_var.name + "=" + \
1301            str(rule.class_distribution.modus())
1302        if show_distribution:
1303            ret += str(rule.class_distribution)
1304    return ret
1305
1306def supervisedClassCheck(instances):
1307    if not instances.domain.class_var:
1308        raise Exception("Class variable is required!")
1309    if instances.domain.class_var.var_type != Orange.feature.Type.Discrete:
1310        raise Exception("CN2 requires a discrete class!")
1311
1312
1313def rule_in_set(rule, rules):
1314    for r in rules:
1315        if rules_equal(rule, r):
1316            return True
1317    return False
1318
1319def rules_equal(rule1, rule2):
1320    if len(rule1.filter.conditions) != len(rule2.filter.conditions):
1321        return False
1322    for c1 in rule1.filter.conditions:
1323        found = False # find the same condition in the other rule
1324        for c2 in rule2.filter.conditions:
1325            try:
1326                if not c1.position == c2.position: continue # same feature?
1327                if not type(c1) == type(c2): continue # same type of condition
1328                if type(c1) == Orange.core.ValueFilter_discrete:
1329                    if not type(c1.values[0]) == type(c2.values[0]): continue
1330                    if not c1.values[0] == c2.values[0]: continue # same value?
1331                if type(c1) == Orange.core.ValueFilter_continuous:
1332                    if not c1.oper == c2.oper: continue # same operator?
1333                    if not c1.ref == c2.ref: continue #same threshold?
1334                found = True
1335                break
1336            except:
1337                pass
1338        if not found:
1339            return False
1340    return True
1341
1342# Miscellaneous - utility functions
1343def avg(l):
1344    if len(l) == 0:
1345        return 0.
1346    return sum(l) / len(l)
1347
1348def var(l):
1349    if len(l) < 2:
1350        return 0.
1351    av = avg(l)
1352    vars = [math.pow(li - av, 2) for li in l]
1353    return sum(vars) / (len(l) - 1)
1354
1355def median(l):
1356    if len(l) == 0:
1357        return 0.
1358    l.sort()
1359    le = len(l)
1360    if le % 2 == 1:
1361        return l[(le - 1) / 2]
1362    else:
1363        return (l[le / 2 - 1] + l[le / 2]) / 2
1364
1365def perc(l, p):
1366    l.sort()
1367    return l[int(math.floor(p * len(l)))]
1368
1369class EVDFitter:
1370    """ Randomizes a dataset and fits an extreme value distribution onto it. """
1371
1372    def __init__(self, learner, n=200, randomseed=100):
1373        self.learner = learner
1374        self.n = n
1375        self.randomseed = randomseed
1376        # initialize random seed to make experiments repeatable
1377        random.seed(self.randomseed)
1378
1379
1380    def createRandomDataSet(self, data):
1381        newData = Orange.data.Table(data)
1382        # shuffle data
1383        cl_num = newData.toNumpy("C")
1384        random.shuffle(cl_num[0][:, 0])
1385        clData = Orange.data.Table(Orange.data.Domain([newData.domain.classVar]), cl_num[0])
1386        for d_i, d in enumerate(newData):
1387            d[newData.domain.classVar] = clData[d_i][newData.domain.classVar]
1388        return newData
1389
1390    def createEVDistList(self, evdList):
1391        l = Orange.core.EVDistList()
1392        for el in evdList:
1393            l.append(Orange.core.EVDist(mu=el[0], beta=el[1], percentiles=el[2]))
1394        return l
1395
1396
1397    # estimated fisher tippett parameters for a set of values given in vals list (+ deciles)
1398    def compParameters(self, vals, oldMi, oldBeta, oldPercs, fixedBeta=False):
1399        # compute percentiles
1400        vals.sort()
1401        N = len(vals)
1402        percs = [avg(vals[int(float(N) * i / 10):int(float(N) * (i + 1) / 10)]) for i in range(10)]
1403        if N < 10:
1404            return oldMi, oldBeta, percs
1405        if not fixedBeta:
1406            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))))
1407        else:
1408            beta = oldBeta
1409        mi = max(oldMi, percs[-1] + beta * math.log(-math.log(0.95)))
1410        mi = percs[-1] + beta * math.log(-math.log(0.95))
1411        return max(oldMi, numpy.average(vals) - beta * 0.5772156649), beta, None
1412
1413    def prepare_learner(self):
1414        self.oldStopper = self.learner.ruleFinder.ruleStoppingValidator
1415        self.evaluator = self.learner.ruleFinder.evaluator
1416        self.refiner = self.learner.ruleFinder.refiner
1417        self.validator = self.learner.ruleFinder.validator
1418        self.ruleFilter = self.learner.ruleFinder.ruleFilter
1419        self.learner.ruleFinder.validator = None
1420        self.learner.ruleFinder.evaluator = Orange.core.RuleEvaluator_LRS()
1421        self.learner.ruleFinder.evaluator.storeRules = True
1422        self.learner.ruleFinder.ruleStoppingValidator = Orange.core.RuleValidator_LRS(alpha=1.0)
1423        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = 0
1424        self.learner.ruleFinder.refiner = BeamRefiner_Selector()
1425        self.learner.ruleFinder.ruleFilter = BeamFilter_Width(width=5)
1426
1427
1428    def restore_learner(self):
1429        self.learner.ruleFinder.evaluator = self.evaluator
1430        self.learner.ruleFinder.ruleStoppingValidator = self.oldStopper
1431        self.learner.ruleFinder.refiner = self.refiner
1432        self.learner.ruleFinder.validator = self.validator
1433        self.learner.ruleFinder.ruleFilter = self.ruleFilter
1434
1435    def computeEVD(self, data, weightID=0, target_class=0, progress=None):
1436        import time
1437        # prepare learned for distribution computation       
1438        self.prepare_learner()
1439
1440        # loop through N (sampling repetitions)
1441        extremeDists = [(0, 1, [])]
1442        self.learner.ruleFinder.ruleStoppingValidator.max_rule_complexity = self.oldStopper.max_rule_complexity
1443        maxVals = [[] for l in range(self.oldStopper.max_rule_complexity + 1)]
1444        for d_i in range(self.n):
1445            if not progress:
1446                if self.learner.debug:
1447                    print d_i,
1448            else:
1449                progress(float(d_i) / self.n, None)
1450            # create data set (remove and randomize)
1451            a = time.time()
1452            tempData = self.createRandomDataSet(data)
1453            a = time.time()
1454            self.learner.ruleFinder.evaluator.rules = RuleList()
1455            a = time.time()
1456            for l in range(self.oldStopper.max_rule_complexity + 2):
1457               self.learner.ruleFinder.evaluator.rules.append(None)
1458            a = time.time()
1459            # Next, learn a rule
1460            self.learner.ruleFinder(tempData, weightID, target_class, RuleList())
1461            a = time.time()
1462            for l in range(self.oldStopper.max_rule_complexity + 1):
1463                if self.learner.ruleFinder.evaluator.rules[l]:
1464                    maxVals[l].append(self.learner.ruleFinder.evaluator.rules[l].quality)
1465                else:
1466                    maxVals[l].append(0)
1467##                qs = [r.quality for r in self.learner.ruleFinder.evaluator.rules if r.complexity == l+1]
1468####                if qs:
1469####                    for r in self.learner.ruleFinder.evaluator.rules:
1470####                        if r.quality == max(qs) and r.classDistribution.abs == 16 and r.classDistribution[0] == 16:
1471####                            print "best rule", orngCN2.ruleToString(r), r.quality
1472##                if qs:
1473##                    maxVals[l].append(max(qs))
1474##                else:
1475##                    maxVals[l].append(0)
1476            a = time.time()
1477
1478        # longer rule should always be better than shorter rule
1479        for l in range(self.oldStopper.max_rule_complexity):
1480            for i in range(len(maxVals[l])):
1481                if maxVals[l + 1][i] < maxVals[l][i]:
1482                    maxVals[l + 1][i] = maxVals[l][i]
1483##        print
1484##        for mi, m in enumerate(maxVals):
1485##            print "mi=",mi,m
1486
1487        mu, beta, perc = 1.0, 2.0, [0.0] * 10
1488        for mi, m in enumerate(maxVals):
1489##            if mi == 0:
1490##                mu, beta, perc = self.compParameters(m, mu, beta, perc)
1491##            else:
1492            mu, beta, perc = self.compParameters(m, mu, beta, perc, fixedBeta=True)
1493            extremeDists.append((mu, beta, perc))
1494            extremeDists.extend([(0, 1, [])] * (mi))
1495            if self.learner.debug:
1496                print mi, mu, beta, perc
1497
1498        self.restore_learner()
1499        return self.createEVDistList(extremeDists)
1500
1501class ABBeamFilter(BeamFilter):
1502    """
1503    ABBeamFilter: Filters beam;
1504        - leaves first N rules (by quality)
1505        - leaves first N rules that have only of arguments in condition part
1506    """
1507    def __init__(self, width=5):
1508        self.width = width
1509        self.pArgs = None
1510
1511    def __call__(self, rulesStar, examples, weight_id):
1512        newStar = RuleList()
1513        rulesStar.sort(lambda x, y:-cmp(x.quality, y.quality))
1514        argsNum = 0
1515        for r_i, r in enumerate(rulesStar):
1516            if r_i < self.width: # either is one of best "width" rules
1517                newStar.append(r)
1518            elif self.onlyPositives(r):
1519                if argsNum < self.width:
1520                    newStar.append(r)
1521                    argsNum += 1
1522        return newStar
1523
1524    def setArguments(self, domain, positive_arguments):
1525        self.pArgs = positive_arguments
1526        self.domain = domain
1527        self.argTab = [0] * len(self.domain.attributes)
1528        for arg in self.pArgs:
1529            for cond in arg.filter.conditions:
1530                self.argTab[cond.position] = 1
1531
1532    def onlyPositives(self, rule):
1533        if not self.pArgs:
1534            return False
1535
1536        ruleTab = [0] * len(self.domain.attributes)
1537        for cond in rule.filter.conditions:
1538            ruleTab[cond.position] = 1
1539        return map(operator.or_, ruleTab, self.argTab) == self.argTab
1540
1541
1542class CoversArguments:
1543    """
1544    Class determines if rule covers one out of a set of arguments.
1545    """
1546    def __init__(self, arguments):
1547        self.arguments = arguments
1548        self.indices = []
1549        for a in self.arguments:
1550            indNA = getattr(a.filter, "indices", None)
1551            if not indNA:
1552                a.filter.setattr("indices", CoversArguments.filterIndices(a.filter))
1553            self.indices.append(a.filter.indices)
1554
1555    def __call__(self, rule):
1556        if not self.indices:
1557            return False
1558        if not getattr(rule.filter, "indices", None):
1559            rule.filter.indices = CoversArguments.filterIndices(rule.filter)
1560        for index in self.indices:
1561            if map(operator.or_, rule.filter.indices, index) == rule.filter.indices:
1562                return True
1563        return False
1564
1565    def filterIndices(filter):
1566        if not filter.domain:
1567            return []
1568        ind = [0] * len(filter.domain.attributes)
1569        for c in filter.conditions:
1570            ind[c.position] = operator.or_(ind[c.position],
1571                                         CoversArguments.conditionIndex(c))
1572        return ind
1573    filterIndices = staticmethod(filterIndices)
1574
1575    def conditionIndex(c):
1576        if isinstance(c, Orange.data.filter.ValueFilterContinuous):
1577            if (c.oper == Orange.data.filter.ValueFilter.GreaterEqual or
1578                c.oper == Orange.data.filter.ValueFilter.Greater):
1579                return 5# 0101
1580            elif (c.oper == Orange.data.filter.ValueFilter.LessEqual or
1581                  c.oper == Orange.data.filter.ValueFilter.Less):
1582                return 3 # 0011
1583            else:
1584                return c.oper
1585        else:
1586            return 1 # 0001
1587    conditionIndex = staticmethod(conditionIndex)
1588
1589    def oneSelectorToCover(ruleIndices, argIndices):
1590        at, type = -1, 0
1591        for r_i, ind in enumerate(ruleIndices):
1592            if not argIndices[r_i]:
1593                continue
1594            if at > -1 and not ind == argIndices[r_i]: # need two changes
1595                return (-1, 0)
1596            if not ind == argIndices[r_i]:
1597                if argIndices[r_i] in [1, 3, 5]:
1598                    at, type = r_i, argIndices[r_i]
1599                if argIndices[r_i] == 6:
1600                    if ind == 3:
1601                        at, type = r_i, 5
1602                    if ind == 5:
1603                        at, type = r_i, 3
1604        return at, type
1605    oneSelectorToCover = staticmethod(oneSelectorToCover)
1606
1607
1608class SelectorAdder(BeamRefiner):
1609    """
1610    Selector adder, this function is a refiner function:
1611       - refined rules are not consistent with any of negative arguments.
1612    """
1613    def __init__(self, example=None, not_allowed_selectors=[], argument_id=None,
1614                 discretizer=Orange.feature.discretization.Entropy(forceAttribute=True)):
1615        # required values - needed values of attributes
1616        self.example = example
1617        self.argument_id = argument_id
1618        self.not_allowed_selectors = not_allowed_selectors
1619        self.discretizer = discretizer
1620
1621    def __call__(self, oldRule, data, weight_id, target_class= -1):
1622        inNotAllowedSelectors = CoversArguments(self.not_allowed_selectors)
1623        new_rules = RuleList()
1624
1625        # get positive indices (selectors already in the rule)
1626        indices = getattr(oldRule.filter, "indices", None)
1627        if not indices:
1628            indices = CoversArguments.filterIndices(oldRule.filter)
1629            oldRule.filter.setattr("indices", indices)
1630
1631        # get negative indices (selectors that should not be in the rule)
1632        negative_indices = [0] * len(data.domain.attributes)
1633        for nA in self.not_allowed_selectors:
1634            #print indices, nA.filter.indices
1635            at_i, type_na = CoversArguments.oneSelectorToCover(indices, nA.filter.indices)
1636            if at_i > -1:
1637                negative_indices[at_i] = operator.or_(negative_indices[at_i], type_na)
1638
1639        #iterate through indices = attributes
1640        for i, ind in enumerate(indices):
1641            if not self.example[i] or self.example[i].isSpecial():
1642                continue
1643            if ind == 1:
1644                continue
1645            if data.domain[i].varType == Orange.feature.Type.Discrete and not negative_indices[i] == 1: # DISCRETE attribute
1646                if self.example:
1647                    values = [self.example[i]]
1648                else:
1649                    values = data.domain[i].values
1650                for v in values:
1651                    tempRule = oldRule.clone()
1652                    tempRule.filter.conditions.append(
1653                        Orange.data.filter.ValueFilterDiscrete(
1654                            position=i,
1655                            values=[Orange.data.Value(data.domain[i], v)],
1656                            acceptSpecial=0))
1657                    tempRule.complexity += 1
1658                    tempRule.filter.indices[i] = 1 # 1 stands for discrete attribute (see CoversArguments.conditionIndex)
1659                    tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1660                    if len(tempRule.examples) < len(oldRule.examples):
1661                        new_rules.append(tempRule)
1662            elif data.domain[i].varType == Orange.feature.Type.Continuous and not negative_indices[i] == 7: # CONTINUOUS attribute
1663                try:
1664                    at = data.domain[i]
1665                    at_d = self.discretizer(at, oldRule.examples)
1666                except:
1667                    continue # discretization failed !
1668                # If discretization makes sense? then:
1669                if len(at_d.values) > 1:
1670                    for p in at_d.getValueFrom.transformer.points:
1671                        #LESS
1672                        if not negative_indices[i] == 3:
1673                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.LessEqual, p, target_class, 3)
1674                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] <= p:# and not inNotAllowedSelectors(tempRule):
1675                                new_rules.append(tempRule)
1676                        #GREATER
1677                        if not negative_indices[i] == 5:
1678                            tempRule = self.getTempRule(oldRule, i, Orange.data.filter.ValueFilter.Greater, p, target_class, 5)
1679                            if len(tempRule.examples) < len(oldRule.examples) and self.example[i] > p:# and not inNotAllowedSelectors(tempRule):
1680                                new_rules.append(tempRule)
1681        for r in new_rules:
1682            r.parentRule = oldRule
1683            r.valuesFilter = r.filter.filter
1684        return new_rules
1685
1686    def getTempRule(self, oldRule, pos, oper, ref, target_class, atIndex):
1687        tempRule = oldRule.clone()
1688        tempRule.filter.conditions.append(
1689            Orange.data.filter.ValueFilterContinuous(
1690                position=pos, oper=oper, ref=ref, acceptSpecial=0))
1691        tempRule.complexity += 1
1692        tempRule.filter.indices[pos] = operator.or_(tempRule.filter.indices[pos], atIndex) # from RuleCoversArguments.conditionIndex
1693        tempRule.filterAndStore(oldRule.examples, tempRule.weightID, target_class)
1694        return tempRule
1695
1696    def setCondition(self, oldRule, target_class, ci, condition):
1697        tempRule = oldRule.clone()
1698        tempRule.filter.conditions[ci] = condition
1699        tempRule.filter.conditions[ci].setattr("specialized", 1)
1700        tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1701        return tempRule
1702
1703SelectorAdder = deprecated_members({"notAllowedSelectors": "not_allowed_selectors",
1704                     "argumentID": "argument_id"})(SelectorAdder)
1705
1706# This filter is the ugliest code ever! Problem is with Orange, I had some problems with inheriting deepCopy
1707# I should take another look at it.
1708class ArgFilter(Orange.core.Filter):
1709    """ This class implements AB-covering principle. """
1710    def __init__(self, argument_id=None, filter = Orange.core.Filter_values(), arg_example = None):
1711        self.filter = filter
1712        self.indices = getattr(filter,"indices",[])
1713        if not self.indices and len(filter.conditions)>0:
1714            self.indices = CoversArguments.filterIndices(filter)
1715        self.argument_id = argument_id
1716        self.domain = self.filter.domain
1717        self.conditions = filter.conditions
1718        self.arg_example = arg_example
1719        self.only_arg_example = True
1720       
1721    def condIn(self,cond): # is condition in the filter?
1722        condInd = CoversArguments.conditionIndex(cond)
1723        if operator.or_(condInd,self.indices[cond.position]) == self.indices[cond.position]:
1724            return True
1725        return False
1726   
1727    def __call__(self,example):
1728        if not self.filter(example):
1729            return False
1730        elif (not self.only_arg_example or example == self.arg_example):
1731            if example[self.argument_id].value and len(example[self.argument_id].value.positive_arguments)>0: # example has positive arguments
1732                # conditions should cover at least one of the positive arguments
1733                oneArgCovered = False
1734                for pA in example[self.argument_id].value.positive_arguments:
1735                    argCovered = [self.condIn(c) for c in pA.filter.conditions]
1736                    oneArgCovered = oneArgCovered or len(argCovered) == sum(argCovered) #argCovered
1737                    if oneArgCovered:
1738                        break
1739                if not oneArgCovered:
1740                    return False
1741            if example[self.argument_id].value and len(example[self.argument_id].value.negative_arguments)>0: # example has negative arguments
1742                # condition should not cover neither of negative arguments
1743                for pN in example[self.argument_id].value.negative_arguments:
1744                    argCovered = [self.condIn(c) for c in pN.filter.conditions]
1745                    if len(argCovered)==sum(argCovered):
1746                        return False
1747        return True
1748
1749    def __setattr__(self,name,obj):
1750        self.__dict__[name]=obj
1751        self.filter.setattr(name,obj)
1752
1753    def deep_copy(self):
1754        newFilter = ArgFilter(argument_id=self.argument_id)
1755        newFilter.filter = Orange.core.Filter_values() #self.filter.deepCopy()
1756        newFilter.filter.conditions = self.filter.conditions[:]
1757        newFilter.domain = self.filter.domain
1758        newFilter.negate = self.filter.negate
1759        newFilter.conjunction = self.filter.conjunction
1760        newFilter.domain = self.filter.domain
1761        newFilter.conditions = newFilter.filter.conditions
1762        newFilter.indices = self.indices[:]
1763        newFilter.arg_example = self.arg_example
1764        return newFilter
1765ArgFilter = deprecated_members({"argumentID": "argument_id"})(ArgFilter)
1766
1767class SelectorArgConditions(BeamRefiner):
1768    """
1769    Selector adder, this function is a refiner function:
1770      - refined rules are not consistent with any of negative arguments.
1771    """
1772    def __init__(self, example, allowed_selectors):
1773        # required values - needed values of attributes
1774        self.example = example
1775        self.allowed_selectors = allowed_selectors
1776
1777    def __call__(self, oldRule, data, weight_id, target_class= -1):
1778        if len(oldRule.filter.conditions) >= len(self.allowed_selectors):
1779            return RuleList()
1780        new_rules = RuleList()
1781        for c in self.allowed_selectors:
1782            # normal condition
1783            if not c.unspecialized_condition:
1784                tempRule = oldRule.clone()
1785                tempRule.filter.conditions.append(c)
1786                tempRule.filterAndStore(oldRule.examples, oldRule.weightID, target_class)
1787                if len(tempRule.examples) < len(oldRule.examples):
1788                    new_rules.append(tempRule)
1789            # unspecified condition
1790            else:
1791                # find all possible example values
1792                vals = {}
1793                for e in oldRule.examples:
1794                    if not e[c.position].isSpecial():
1795                        vals[str(e[c.position])] = 1
1796                values = vals.keys()
1797                # for each value make a condition
1798                for v in values:
1799                    tempRule = oldRule.clone()
1800                    tempRule.filter.conditions.append(
1801                        Orange.data.filter.ValueFilterContinuous(
1802                            position=c.position, oper=c.oper,
1803                            ref=float(v), acceptSpecial=0))
1804                    if tempRule(self.example):
1805                        tempRule.filterAndStore(
1806                            oldRule.examples, oldRule.weightID, target_class)
1807                        if len(tempRule.examples) < len(oldRule.examples):
1808                            new_rules.append(tempRule)
1809##        print " NEW RULES "
1810##        for r in new_rules:
1811##            print Orange.classification.rules.rule_to_string(r)
1812        for r in new_rules:
1813            r.parentRule = oldRule
1814##            print Orange.classification.rules.rule_to_string(r)
1815        return new_rules
1816
1817
1818class CrossValidation:
1819    def __init__(self, folds=5, random_generator=150):
1820        self.folds = folds
1821        self.random_generator = random_generator
1822
1823    def __call__(self, learner, examples, weight):
1824        res = orngTest.crossValidation([learner], (examples, weight), folds=self.folds, random_generator=self.random_generator)
1825        return self.get_prob_from_res(res, examples)
1826
1827    def get_prob_from_res(self, res, examples):
1828        prob_dist = Orange.core.DistributionList()
1829        for tex in res.results:
1830            d = Orange.statistics.distribution.Distribution(examples.domain.class_var)
1831            for di in range(len(d)):
1832                d[di] = tex.probabilities[0][di]
1833            prob_dist.append(d)
1834        return prob_dist
1835
1836
1837class PILAR:
1838    """
1839    PILAR (Probabilistic improvement of learning algorithms with rules).
1840    """
1841    def __init__(self, alternative_learner=None, min_cl_sig=0.5, min_beta=0.0, penalty=0.01, set_prefix_rules=False, optimize_betas=True):
1842        self.alternative_learner = alternative_learner
1843        self.min_cl_sig = min_cl_sig
1844        self.min_beta = min_beta
1845        self.set_prefix_rules = set_prefix_rules
1846        self.optimize_betas = optimize_betas
1847        self.selected_evaluation = CrossValidation(folds=5)
1848        self.penalty = penalty
1849
1850    def __call__(self, rules, examples, weight=0):
1851        rules = self.add_null_rule(rules, examples, weight)
1852        if self.alternative_learner:
1853            prob_dist = self.selected_evaluation(self.alternative_learner, examples, weight)
1854            classifier = self.alternative_learner(examples, weight)
1855##            prob_dist = Orange.core.DistributionList()
1856##            for e in examples:
1857##                prob_dist.append(classifier(e,Orange.core.GetProbabilities))
1858            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)
1859        else:
1860            cl = Orange.core.RuleClassifier_logit(rules, self.min_cl_sig, self.min_beta, self.penalty, examples, weight, self.set_prefix_rules, self.optimize_betas)
1861
1862        for ri, r in enumerate(cl.rules):
1863            cl.rules[ri].setattr("beta", cl.ruleBetas[ri])
1864        cl.setattr("all_rules", cl.rules)
1865        cl.rules = self.sort_rules(cl.rules)
1866        cl.ruleBetas = [r.beta for r in cl.rules]
1867        cl.setattr("data", examples)
1868        return cl
1869
1870    def add_null_rule(self, rules, examples, weight):
1871        for cl in examples.domain.class_var:
1872            tmpRle = Rule()
1873            tmpRle.filter = Orange.data.filter.Values(domain=examples.domain)
1874            tmpRle.parentRule = None
1875            tmpRle.filterAndStore(examples, weight, int(cl))
1876            tmpRle.quality = tmpRle.class_distribution[int(cl)] / tmpRle.class_distribution.abs
1877            rules.append(tmpRle)
1878        return rules
1879
1880    def sort_rules(self, rules):
1881        new_rules = RuleList()
1882        foundRule = True
1883        while foundRule:
1884            foundRule = False
1885            bestRule = None
1886            for r in rules:
1887                if r in new_rules:
1888                    continue
1889                if r.beta < 0.01 and r.beta > -0.01:
1890                    continue
1891                if not bestRule:
1892                    bestRule = r
1893                    foundRule = True
1894                    continue
1895                if len(r.filter.conditions) < len(bestRule.filter.conditions):
1896                    bestRule = r
1897                    foundRule = True
1898                    continue
1899                if len(r.filter.conditions) == len(bestRule.filter.conditions) and r.beta > bestRule.beta:
1900                    bestRule = r
1901                    foundRule = True
1902                    continue
1903            if bestRule:
1904                new_rules.append(bestRule)
1905        return new_rules
1906
1907PILAR = deprecated_members({"sortRules": "sort_rules"})(PILAR)
1908
1909
1910class RuleClassifier_bestRule(RuleClassifier):
1911    """
1912    A very simple classifier, it takes the best rule of each class and
1913    normalizes probabilities.
1914    """
1915    def __init__(self, rules, examples, weight_id=0, **argkw):
1916        self.rules = rules
1917        self.examples = examples
1918        self.apriori = Orange.statistics.distribution.Distribution(examples.domain.class_var, examples, weight_id)
1919        self.apriori_prob = [a / self.apriori.abs for a in self.apriori]
1920        self.weight_id = weight_id
1921        self.__dict__.update(argkw)
1922        self.default_class_index = -1
1923
1924    @deprecated_keywords({"retRules": "ret_rules"})
1925    def __call__(self, example, result_type=Orange.classification.Classifier.GetValue, ret_rules=False):
1926        example = Orange.data.Instance(self.examples.domain, example)
1927        tempDist = Orange.statistics.distribution.Distribution(example.domain.class_var)
1928        best_rules = [None] * len(example.domain.class_var.values)
1929
1930        for r in self.rules:
1931            if r(example) and not self.default_class_index == int(r.classifier.default_val) and \
1932               (not best_rules[int(r.classifier.default_val)] or r.quality > tempDist[r.classifier.default_val]):
1933                tempDist[r.classifier.default_val] = r.quality
1934                best_rules[int(r.classifier.default_val)] = r
1935        for b in best_rules:
1936            if b:
1937                used = getattr(b, "used", 0.0)
1938                b.setattr("used", used + 1)
1939        nonCovPriorSum = sum([tempDist[i] == 0. and self.apriori_prob[i] or 0. for i in range(len(self.apriori_prob))])
1940        if tempDist.abs < 1.:
1941            residue = 1. - tempDist.abs
1942            for a_i, a in enumerate(self.apriori_prob):
1943                if tempDist[a_i] == 0.:
1944                    tempDist[a_i] = self.apriori_prob[a_i] * residue / nonCovPriorSum
1945            final_dist = tempDist #Orange.core.Distribution(example.domain.class_var)
1946        else:
1947            tempDist.normalize() # prior probability
1948            tmp_examples = Orange.data.Table(self.examples)
1949            for r in best_rules:
1950                if r:
1951                    tmp_examples = r.filter(tmp_examples)
1952            tmpDist = Orange.statistics.distribution.Distribution(tmp_examples.domain.class_var, tmp_examples, self.weight_id)
1953            tmpDist.normalize()
1954            probs = [0.] * len(self.examples.domain.class_var.values)
1955            for i in range(len(self.examples.domain.class_var.values)):
1956                probs[i] = tmpDist[i] + tempDist[i] * 2
1957            final_dist = Orange.statistics.distribution.Distribution(self.examples.domain.class_var)
1958            for cl_i, cl in enumerate(self.examples.domain.class_var):
1959                final_dist[cl] = probs[cl_i]
1960            final_dist.normalize()
1961
1962        if ret_rules: # Do you want to return rules with classification?
1963            if result_type == Orange.classification.Classifier.GetValue:
1964              return (final_dist.modus(), best_rules)
1965            if result_type == Orange.classification.Classifier.GetProbabilities:
1966              return (final_dist, best_rules)
1967            return (final_dist.modus(), final_dist, best_rules)
1968        if result_type == Orange.classification.Classifier.GetValue:
1969          return final_dist.modus()
1970        if result_type == Orange.classification.Classifier.GetProbabilities:
1971          return final_dist
1972        return (final_dist.modus(), final_dist)
1973
1974RuleClassifier_bestRule = deprecated_members({"defaultClassIndex": "default_class_index"})(RuleClassifier_bestRule)
Note: See TracBrowser for help on using the repository browser.