source: orange/Orange/classification/rules.py @ 10580:c4cbae8dcf8b

Revision 10580:c4cbae8dcf8b, 85.4 KB checked in by markotoplak, 2 years ago (diff)

Moved deprecation functions, progress bar support and environ into Orange.utils. Orange imports cleanly, although it is not tested yet.

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