source: orange/Orange/classification/svm/__init__.py @ 11377:1f01a3c46101

Revision 11377:1f01a3c46101, 46.7 KB checked in by Ales Erjavec <ales.erjavec@…>, 14 months ago (diff)

Added notes to svm learner documentation about discrete feature translation.

Line 
1import math
2
3from collections import defaultdict
4from operator import add
5
6import Orange.core
7import Orange.data
8import Orange.misc
9import Orange.feature
10
11import kernels
12import warnings
13
14from Orange.core import SVMLearner as _SVMLearner
15from Orange.core import SVMLearnerSparse as _SVMLearnerSparse
16from Orange.core import LinearClassifier, \
17                        LinearLearner, \
18                        SVMClassifier as _SVMClassifier, \
19                        SVMClassifierSparse as _SVMClassifierSparse
20
21from Orange.data import preprocess
22
23from Orange import feature as variable
24
25from Orange.utils import _orange__new__
26
27
28def max_nu(data):
29    """
30    Return the maximum nu parameter for the given data table for
31    Nu_SVC learning.
32
33    :param data: Data with discrete class variable
34    :type data: Orange.data.Table
35
36    """
37    nu = 1.0
38    dist = list(Orange.core.Distribution(data.domain.classVar, data))
39
40    def pairs(seq):
41        for i, n1 in enumerate(seq):
42            for n2 in seq[i + 1:]:
43                yield n1, n2
44    return min([2.0 * min(n1, n2) / (n1 + n2) for n1, n2 in pairs(dist) \
45                if n1 != 0 and n2 != 0] + [nu])
46
47maxNu = max_nu
48
49
50def is_discrete(feature):
51    return isinstance(feature, Orange.feature.Discrete)
52
53
54def is_continuous(feature):
55    return isinstance(feature, Orange.feature.Continuous)
56
57
58class SVMLearner(_SVMLearner):
59    """
60    :param svm_type: the SVM type
61    :type svm_type: SVMLearner.SVMType
62    :param kernel_type: the kernel type
63    :type kernel_type: SVMLearner.Kernel
64    :param degree: kernel parameter (only for ``Polynomial``)
65    :type degree: int
66    :param gamma: kernel parameter; if 0, it is set to 1.0/#features
67        (for ``Polynomial``, ``RBF`` and ``Sigmoid``)
68    :type gamma: float
69    :param coef0: kernel parameter (for ``Polynomial`` and ``Sigmoid``)
70    :type coef0: int
71    :param kernel_func: kernel function if ``kernel_type`` is
72        ``kernels.Custom``
73    :type kernel_func: callable object
74    :param C: C parameter (for ``C_SVC``, ``Epsilon_SVR`` and ``Nu_SVR``)
75    :type C: float
76    :param nu: Nu parameter (for ``Nu_SVC``, ``Nu_SVR`` and ``OneClass``)
77    :type nu: float
78    :param p: epsilon parameter (for ``Epsilon_SVR``)
79    :type p: float
80    :param cache_size: cache memory size in MB
81    :type cache_size: int
82    :param eps: tolerance of termination criterion
83    :type eps: float
84    :param probability: build a probability model
85    :type probability: bool
86    :param shrinking: use shrinking heuristics
87    :type shrinking: bool
88    :param normalization: normalize the input data prior to learning into
89        range [0..1] and replace discrete features with indicator columns
90        one for each value of the feature using
91        :class:`~Orange.data.continuization.DomainContinuizer` class
92        (default ``True``)
93    :type normalization: bool
94    :param weight: a list of class weights
95    :type weight: list
96    :param verbose: If `True` show training progress (default is `False`).
97    :type verbose: bool
98
99    Example:
100
101        >>> import Orange
102        >>> from Orange.classification import svm
103        >>> from Orange.evaluation import testing, scoring
104        >>> data = Orange.data.Table("vehicle.tab")
105        >>> learner = svm.SVMLearner()
106        >>> results = testing.cross_validation([learner], data, folds=5)
107        >>> print "CA:  %.4f" % scoring.CA(results)[0]
108        CA:  0.7908
109        >>> print "AUC: %.4f" % scoring.AUC(results)[0]
110        AUC: 0.9565
111
112    """
113    __new__ = _orange__new__(_SVMLearner)
114
115    C_SVC = _SVMLearner.C_SVC
116    Nu_SVC = _SVMLearner.Nu_SVC
117    OneClass = _SVMLearner.OneClass
118    Nu_SVR = _SVMLearner.Nu_SVR
119    Epsilon_SVR = _SVMLearner.Epsilon_SVR
120
121    @Orange.utils.deprecated_keywords({"kernelFunc": "kernel_func"})
122    def __init__(self, svm_type=Nu_SVC, kernel_type=kernels.RBF,
123                 kernel_func=None, C=1.0, nu=0.5, p=0.1, gamma=0.0, degree=3,
124                 coef0=0, shrinking=True, probability=True, verbose=False,
125                 cache_size=200, eps=0.001, normalization=True,
126                 weight=[], **kwargs):
127        self.svm_type = svm_type
128        self.kernel_type = kernel_type
129        self.kernel_func = kernel_func
130        self.C = C
131        self.nu = nu
132        self.p = p
133        self.gamma = gamma
134        self.degree = degree
135        self.coef0 = coef0
136        self.shrinking = shrinking
137        self.probability = probability
138        self.verbose = verbose
139        self.cache_size = cache_size
140        self.eps = eps
141        self.normalization = normalization
142        for key, val in kwargs.items():
143            setattr(self, key, val)
144        self.learner = Orange.core.SVMLearner(**kwargs)
145        self.weight = weight
146
147    max_nu = staticmethod(max_nu)
148
149    def __call__(self, data, weight=0):
150        """Construct a SVM classifier
151
152        :param table: data with continuous features
153        :type table: Orange.data.Table
154
155        :param weight: ignored (required due to base class signature);
156        """
157
158        examples = Orange.core.Preprocessor_dropMissingClasses(data)
159        class_var = examples.domain.class_var
160        if len(examples) == 0:
161            raise ValueError("Example table is without any defined classes")
162
163        # Fix the svm_type parameter if we have a class_var/svm_type mismatch
164        if self.svm_type in [0, 1] and \
165            isinstance(class_var, Orange.feature.Continuous):
166            self.svm_type += 3
167
168        if self.svm_type in [3, 4] and \
169            isinstance(class_var, Orange.feature.Discrete):
170            self.svm_type -= 3
171
172        if self.kernel_type == kernels.Custom and not self.kernel_func:
173            raise ValueError("Custom kernel function not supplied")
174
175        nu = self.nu
176        if self.svm_type == SVMLearner.Nu_SVC:
177            # Check if nu is feasible
178            max_nu = self.max_nu(examples)
179            if self.nu > max_nu:
180                if getattr(self, "verbose", 0):
181                    warnings.warn("Specified nu %.3f is infeasible. \
182                    Setting nu to %.3f" % (self.nu, max_nu))
183                nu = max(max_nu - 1e-7, 0.0)
184
185        for name in ["svm_type", "kernel_type", "kernel_func", "C", "nu", "p",
186                     "gamma", "degree", "coef0", "shrinking", "probability",
187                     "verbose", "cache_size", "eps"]:
188            setattr(self.learner, name, getattr(self, name))
189
190        self.learner.nu = nu
191        self.learner.set_weights(self.weight)
192
193        if self.svm_type == SVMLearner.OneClass and self.probability:
194            self.learner.probability = False
195            warnings.warn("One-class SVM probability output not supported.")
196        return self.learn_classifier(examples)
197
198    def learn_classifier(self, data):
199        if self.normalization:
200            data = self._normalize(data)
201        svm = self.learner(data)
202        return SVMClassifier(svm)
203
204    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback"})
205    def tune_parameters(self, data, parameters=None, folds=5, verbose=0,
206                       progress_callback=None):
207        """Tune the ``parameters`` on the given ``data`` using
208        internal cross validation.
209
210        :param data: data for parameter tuning
211        :type data: Orange.data.Table
212        :param parameters: names of parameters to tune
213            (default: ["nu", "C", "gamma"])
214        :type parameters: list of strings
215        :param folds: number of folds for internal cross validation
216        :type folds: int
217        :param verbose: set verbose output
218        :type verbose: bool
219        :param progress_callback: callback function for reporting progress
220        :type progress_callback: callback function
221
222        Here is example of tuning the `gamma` parameter using
223        3-fold cross validation. ::
224
225            svm = Orange.classification.svm.SVMLearner()
226            svm.tune_parameters(table, parameters=["gamma"], folds=3)
227
228        """
229
230        import orngWrap
231
232        if parameters is None:
233            parameters = ["nu", "C", "gamma"]
234
235        searchParams = []
236        normalization = self.normalization
237        if normalization:
238            data = self._normalize(data)
239            self.normalization = False
240        if self.svm_type in [SVMLearner.Nu_SVC, SVMLearner.Nu_SVR] \
241                    and "nu" in parameters:
242            if isinstance(data.domain.class_var, variable.Discrete):
243                max_nu = max(self.max_nu(data) - 1e-7, 0.0)
244            else:
245                max_nu = 1.0
246            searchParams.append(("nu", [i / 10.0 for i in range(1, 9) if \
247                                        i / 10.0 < max_nu] + [max_nu]))
248        elif "C" in parameters:
249            searchParams.append(("C", [2 ** a for a in  range(-5, 15, 2)]))
250
251        if self.kernel_type == 2 and "gamma" in parameters:
252            searchParams.append(("gamma",
253                                 [2 ** a for a in range(-5, 5, 2)] + [0])
254                                )
255        tunedLearner = orngWrap.TuneMParameters(object=self,
256                            parameters=searchParams,
257                            folds=folds,
258                            returnWhat=orngWrap.TuneMParameters.returnLearner,
259                            progressCallback=progress_callback
260                            if progress_callback else lambda i: None)
261        tunedLearner(data, verbose=verbose)
262        if normalization:
263            self.normalization = normalization
264
265    def _normalize(self, data):
266        dc = preprocess.DomainContinuizer()
267        dc.class_treatment = preprocess.DomainContinuizer.Ignore
268        dc.continuous_treatment = preprocess.DomainContinuizer.NormalizeBySpan
269        dc.multinomial_treatment = preprocess.DomainContinuizer.NValues
270        newdomain = dc(data)
271        return data.translate(newdomain)
272
273
274SVMLearner = Orange.utils.deprecated_members({
275    "learnClassifier": "learn_classifier",
276    "tuneParameters": "tune_parameters",
277    "kernelFunc": "kernel_func",
278    },
279    wrap_methods=["__init__", "tune_parameters"])(SVMLearner)
280
281
282class SVMClassifier(_SVMClassifier):
283    def __new__(cls, *args, **kwargs):
284        if args and isinstance(args[0], _SVMClassifier):
285            # Will wrap a C++ object
286            return _SVMClassifier.__new__(cls, name=args[0].name)
287        elif args and isinstance(args[0], variable.Descriptor):
288            # The constructor call for the C++ object.
289            # This is a hack to support loading of old pickled classifiers
290            return _SVMClassifier.__new__(_SVMClassifier, *args, **kwargs)
291        else:
292            raise ValueError
293
294    def __init__(self, wrapped):
295        self.class_var = wrapped.class_var
296        self.domain = wrapped.domain
297        self.computes_probabilities = wrapped.computes_probabilities
298        self.examples = wrapped.examples
299        self.svm_type = wrapped.svm_type
300        self.kernel_func = wrapped.kernel_func
301        self.kernel_type = wrapped.kernel_type
302        self.__wrapped = wrapped
303
304        assert(type(wrapped) in [_SVMClassifier, _SVMClassifierSparse])
305
306        if self.svm_type in [SVMLearner.C_SVC, SVMLearner.Nu_SVC] \
307                and len(wrapped.support_vectors) > 0:
308            # Reorder the support vectors of the binary classifiers
309            label_map = self._get_libsvm_labels_map()
310            start = 0
311            support_vectors = []
312            for n in wrapped.n_SV:
313                support_vectors.append(
314                    wrapped.support_vectors[start: start + n]
315                )
316                start += n
317            support_vectors = [support_vectors[i] for i in label_map \
318                               if i is not None]
319            support_vectors = reduce(add, support_vectors)
320            self.support_vectors = Orange.data.Table(support_vectors)
321        else:
322            self.support_vectors = wrapped.support_vectors
323
324    @property
325    def coef(self):
326        """Coefficients of the underlying svm model.
327
328        If this is a classification model then this is a list of
329        coefficients for each binary 1vs1 classifiers, i.e.
330        #Classes * (#Classses - 1) list of lists where
331        each sublist contains tuples of (coef, support_vector_index)
332
333        For regression models it is still a list of lists (for consistency)
334        but of length 1 e.g. [[(coef, support_vector_index), ... ]]
335
336        """
337        if is_discrete(self.class_var):
338            # We need to reorder the coef values
339            # see http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f804
340            # for more information on how the coefs are stored by libsvm
341            # internally.
342            import numpy as np
343            c_map = self._get_libsvm_bin_classifier_map()
344            label_map = self._get_libsvm_labels_map()
345            coef = []
346            n_class = len(label_map)
347            n_SV = self.__wrapped.n_SV
348            coef_array = np.array(self.__wrapped.coef)
349            p = 0
350            libsvm_class_indices = np.cumsum([0] + list(n_SV), dtype=int)
351            class_indices = np.cumsum([0] + list(self.n_SV), dtype=int)
352            for i in range(n_class - 1):
353                for j in range(i + 1, n_class):
354                    ni = label_map[i]
355                    nj = label_map[j]
356
357                    if ni is None or nj is None:
358                        # One of the classes is missing from the model.
359                        continue
360
361                    bc_index, mult = c_map[p]
362
363                    if ni > nj:
364                        # The order in libsvm model is switched.
365                        ni, nj = nj, ni
366
367                    # Original class indices
368                    c1_range = range(libsvm_class_indices[ni],
369                                     libsvm_class_indices[ni + 1])
370                    c2_range = range(libsvm_class_indices[nj],
371                                     libsvm_class_indices[nj + 1])
372
373                    coef1 = mult * coef_array[nj - 1, c1_range]
374                    coef2 = mult * coef_array[ni, c2_range]
375
376                    # Mapped class indices
377                    c1_range = range(class_indices[i],
378                                     class_indices[i + 1])
379                    c2_range = range(class_indices[j],
380                                     class_indices[j + 1])
381                    if mult == -1.0:
382                        c1_range, c2_range = c2_range, c1_range
383
384                    nonzero1 = np.abs(coef1) > 0.0
385                    nonzero2 = np.abs(coef2) > 0.0
386
387                    coef1 = coef1[nonzero1]
388                    coef2 = coef2[nonzero2]
389
390                    c1_range = [sv_i for sv_i, nz in zip(c1_range, nonzero1)
391                                if nz]
392                    c2_range = [sv_i for sv_i, nz in zip(c2_range, nonzero2)
393                                if nz]
394
395                    coef.append(list(zip(coef1, c1_range)) + \
396                                list(zip(coef2, c2_range)))
397
398                    p += 1
399        else:
400            coef = [zip(self.__wrapped.coef[0],
401                        range(len(self.support_vectors)))]
402
403        return coef
404
405    @property
406    def rho(self):
407        """Constant (bias) terms of the svm model.
408
409        For classification models this is a list of bias terms
410        for each binary 1vs1 classifier.
411
412        For regression models it is a list with a single value.
413
414        """
415        rho = self.__wrapped.rho
416        if is_discrete(self.class_var):
417            c_map = self._get_libsvm_bin_classifier_map()
418            return [rho[i] * m for i, m in c_map]
419        else:
420            return list(rho)
421
422    @property
423    def n_SV(self):
424        """Number of support vectors for each class.
425        For regression models this is `None`.
426
427        """
428        n_SV = self.__wrapped.n_SV
429        if n_SV is not None:
430            labels_map = self._get_libsvm_labels_map()
431            return [n_SV[i] if i is not None else 0 for i in labels_map]
432        else:
433            return None
434
435    # Pairwise probability is expresed as:
436    #   1.0 / (1.0 + exp(dec_val[i] * prob_a[i] + prob_b[i]))
437    # Since dec_val already changes signs if we switch the
438    # classifier direction only prob_b must change signs
439    @property
440    def prob_a(self):
441        if self.__wrapped.prob_a is not None:
442            if isinstance(self.class_var, variable.Discrete):
443                c_map = self._get_libsvm_bin_classifier_map()
444                prob_a = self.__wrapped.prob_a
445                return [prob_a[i] for i, _ in c_map]
446            else:
447                # A single value for regression
448                return list(self.__wrapped.prob_a)
449        else:
450            return None
451
452    @property
453    def prob_b(self):
454        if self.__wrapped.prob_b is not None:
455            c_map = self._get_libsvm_bin_classifier_map()
456            prob_b = self.__wrapped.prob_b
457            # Change sign when changing the classifier direction
458            return [prob_b[i] * m for i, m in c_map]
459        else:
460            return None
461
462    def __call__(self, instance, what=Orange.core.GetValue):
463        """Classify a new ``instance``
464        """
465        instance = Orange.data.Instance(self.domain, instance)
466        return self.__wrapped(instance, what)
467
468    def class_distribution(self, instance):
469        """Return a class distribution for the ``instance``
470        """
471        instance = Orange.data.Instance(self.domain, instance)
472        return self.__wrapped.class_distribution(instance)
473
474    def get_decision_values(self, instance):
475        """Return the decision values of the binary 1vs1
476        classifiers for the ``instance`` (:class:`~Orange.data.Instance`).
477
478        """
479        instance = Orange.data.Instance(self.domain, instance)
480        dec_values = self.__wrapped.get_decision_values(instance)
481        if isinstance(self.class_var, variable.Discrete):
482            # decision values are ordered by libsvm internal class values
483            # i.e. the order of labels in the data
484            c_map = self._get_libsvm_bin_classifier_map()
485            return [dec_values[i] * m for i, m in c_map]
486        else:
487            return list(dec_values)
488
489    def get_model(self):
490        """Return a string representing the model in the libsvm model format.
491        """
492        return self.__wrapped.get_model()
493
494    def _get_libsvm_labels_map(self):
495        """Get the mapping from indices in `class_var.values` to
496        internal libsvm labels. If a class value is missing from the libsvm
497        model the returned corresponding entry is `None`)
498
499        """
500        if is_discrete(self.class_var):
501            n_classes = len(self.class_var.values)
502        else:
503            # OneClass/Regression models
504            n_classes = 1
505        model_string = self.__wrapped.get_model()
506        # Get the labels definition line from the model string
507        # (the labels, if present, are always integer strings
508        # indexing self.class_var.values)
509        labels = [line for line in model_string.splitlines() \
510                  if line.startswith("label")]
511        labels = labels[0].split(" ")[1:] if labels else ["0"]
512        labels = [int(label) for label in labels]
513        labels_map = dict((cls_index, i) for i, cls_index in enumerate(labels))
514        return [labels_map.get(i) for i in range(n_classes)]
515
516    def _get_libsvm_bin_classifier_map(self):
517        """Return the libsvm binary classifier mapping (due to label ordering).
518        """
519        if not is_discrete(self.class_var):
520            raise TypeError("SVM classification model expected")
521
522        label_map = self._get_libsvm_labels_map()
523        bin_c_map = []
524        n_class_values = len(self.class_var.values)
525        nr_class = len([i for i in label_map if i is not None])
526        for i in range(n_class_values - 1):
527            for j in range(i + 1, n_class_values):
528                ni = label_map[i]
529                nj = label_map[j]
530                mult = 1
531
532                if ni is None or nj is None:
533                    # One or both classes are missing from the libsvm model.
534                    continue
535
536                if ni > nj:
537                    # The order in libsvm is switched
538                    ni, nj = nj, ni
539                    mult = -1
540
541                # classifier index
542                cls_index = nr_class * (nr_class - 1) / 2 - \
543                            (nr_class - ni - 1) * (nr_class - ni - 2) / 2 - \
544                            (nr_class - nj)
545                bin_c_map.append((cls_index, mult))
546        return bin_c_map
547
548    def __reduce__(self):
549        return SVMClassifier, (self.__wrapped,), dict(self.__dict__)
550
551    def get_binary_classifier(self, c1, c2):
552        """Return a binary classifier for classes `c1` and `c2`.
553        """
554        import numpy as np
555        if self.svm_type not in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]:
556            raise TypeError("SVM classification model expected.")
557
558        c1 = int(self.class_var(c1))
559        c2 = int(self.class_var(c2))
560
561        n_class = len(self.class_var.values)
562
563        if c1 == c2:
564            raise ValueError("Different classes expected.")
565
566        bin_class_var = Orange.feature.Discrete("%s vs %s" % \
567                        (self.class_var.values[c1], self.class_var.values[c2]),
568                        values=["0", "1"])
569
570        mult = 1.0
571        if c1 > c2:
572            c1, c2 = c2, c1
573            mult = -1.0
574
575        classifier_i = n_class * (n_class - 1) / 2 - \
576                       (n_class - c1 - 1) * (n_class - c1 - 2) / 2 - \
577                       (n_class - c2)
578
579        coef = self.coef[classifier_i]
580
581        coef1 = [(mult * alpha, sv_i) for alpha, sv_i in coef \
582                 if int(self.support_vectors[sv_i].get_class()) == c1]
583        coef2 = [(mult * alpha, sv_i) for alpha, sv_i in coef \
584                 if int(self.support_vectors[sv_i].get_class()) == c2]
585
586        rho = mult * self.rho[classifier_i]
587
588        model = self._binary_libsvm_model_string(bin_class_var,
589                                                 [coef1, coef2],
590                                                 [rho])
591
592        all_sv = [self.support_vectors[sv_i] \
593                  for c, sv_i in coef1 + coef2]
594
595        all_sv = Orange.data.Table(all_sv)
596
597        svm_classifier_type = type(self.__wrapped)
598
599        # Build args for svm_classifier_type constructor
600        args = (bin_class_var, self.examples, all_sv, model)
601
602        if isinstance(svm_classifier_type, _SVMClassifierSparse):
603            args = args + (int(self.__wrapped.use_non_meta),)
604
605        if self.kernel_type == kernels.Custom:
606            args = args + (self.kernel_func,)
607
608        native_classifier = svm_classifier_type(*args)
609        return SVMClassifier(native_classifier)
610
611    def _binary_libsvm_model_string(self, class_var, coef, rho):
612        """Return a libsvm formated model string for binary classifier
613        """
614        import itertools
615
616        if not isinstance(self.class_var, variable.Discrete):
617            raise TypeError("SVM classification model expected")
618
619        model = []
620
621        # Take the model up to nr_classes
622        libsvm_model = self.__wrapped.get_model()
623        for line in libsvm_model.splitlines():
624            if line.startswith("nr_class"):
625                break
626            else:
627                model.append(line.rstrip())
628        nr_class = len(class_var.values)
629        model.append("nr_class %i" % nr_class)
630        model.append("total_sv %i" % reduce(add, [len(c) for c in coef]))
631        model.append("rho " + " ".join(str(r) for r in rho))
632        model.append("label " + " ".join(str(i) for i in range(nr_class)))
633        # No probA and probB
634
635        model.append("nr_sv " + " ".join(str(len(c)) for c in coef))
636        model.append("SV")
637
638        def instance_to_svm(inst):
639            values = [(i, float(inst[v])) \
640                      for i, v in enumerate(inst.domain.attributes) \
641                      if not inst[v].is_special() and float(inst[v]) != 0.0]
642            return " ".join("%i:%f" % (i + 1, v) for i, v in values)
643
644        def sparse_instance_to_svm(inst):
645            non_meta = []
646            base = 1
647            if self.__wrapped.use_non_meta:
648                non_meta = [instance_to_svm(inst)]
649                base += len(inst.domain)
650            metas = []
651            for m_id, value in sorted(inst.get_metas().items(), reverse=True):
652                if not value.isSpecial() and float(value) != 0:
653                    metas.append("%i:%f" % (base - m_id, float(value)))
654            return " ".join(non_meta + metas)
655
656        if isinstance(self.__wrapped, _SVMClassifierSparse):
657            converter = sparse_instance_to_svm
658        else:
659            converter = instance_to_svm
660
661        if self.kernel_type == kernels.Custom:
662            SV = libsvm_model.split("SV\n", 1)[1]
663            # Get the sv indices (the last entry in the SV lines)
664            indices = [int(s.split(":")[-1]) for s in SV.splitlines() \
665                       if s.strip()]
666
667            # Reorder the indices
668            label_map = self._get_libsvm_labels_map()
669            start = 0
670            reordered_indices = []
671            for n in self.__wrapped.n_SV:
672                reordered_indices.append(indices[start: start + n])
673                start += n
674            reordered_indices = [reordered_indices[i] for i in label_map]
675            indices = reduce(add, reordered_indices)
676
677            for (c, sv_i) in itertools.chain(*coef):
678                model.append("%f 0:%i" % (c, indices[sv_i]))
679        else:
680            for (c, sv_i) in itertools.chain(*coef):
681                model.append(
682                    "%f %s" % (c, converter(self.support_vectors[sv_i]))
683                )
684
685        model.append("")
686        return "\n".join(model)
687
688
689SVMClassifier = Orange.utils.deprecated_members({
690    "classDistribution": "class_distribution",
691    "getDecisionValues": "get_decision_values",
692    "getModel" : "get_model",
693    }, wrap_methods=[])(SVMClassifier)
694
695
696# Backwards compatibility (pickling)
697SVMClassifierWrapper = SVMClassifier
698
699
700class SVMLearnerSparse(SVMLearner):
701
702    """
703    A :class:`SVMLearner` that learns from data stored in meta
704    attributes. Meta attributes do not need to be registered with the
705    data set domain, or present in all data instances.
706    """
707
708    @Orange.utils.deprecated_keywords({"useNonMeta": "use_non_meta"})
709    def __init__(self, **kwds):
710        SVMLearner.__init__(self, **kwds)
711        self.use_non_meta = kwds.get("use_non_meta", False)
712        self.learner = Orange.core.SVMLearnerSparse(**kwds)
713
714    def _normalize(self, data):
715        if self.use_non_meta:
716            dc = preprocess.DomainContinuizer()
717            dc.class_treatment = dc.Ignore
718            dc.continuous_treatment = dc.NormalizeBySpan
719            dc.multinomial_treatment = dc.NValues
720            newdomain = dc(data)
721            data = data.translate(newdomain)
722        return data
723
724
725class SVMLearnerEasy(SVMLearner):
726    """A class derived from :obj:`SVMLearner` that automatically
727    scales the data and performs parameter optimization using
728    :func:`SVMLearner.tune_parameters`. The procedure is similar to
729    that implemented in easy.py script from the LibSVM package.
730
731    """
732
733    def __init__(self, folds=4, verbose=0, **kwargs):
734        """
735        :param folds: the number of folds to use in cross validation
736        :type folds:  int
737
738        :param verbose: verbosity of the tuning procedure.
739        :type verbose: int
740
741        ``kwargs`` is passed to :class:`SVMLearner`
742
743        """
744        SVMLearner.__init__(self, **kwargs)
745        self.folds = folds
746        self.verbose = verbose
747
748        self.learner = SVMLearner(**kwargs)
749
750    def learn_classifier(self, data):
751        transformer = preprocess.DomainContinuizer()
752        transformer.multinomialTreatment = preprocess.DomainContinuizer.NValues
753        transformer.continuousTreatment = \
754            preprocess.DomainContinuizer.NormalizeBySpan
755        transformer.classTreatment = preprocess.DomainContinuizer.Ignore
756        newdomain = transformer(data)
757        newexamples = data.translate(newdomain)
758
759        parameters = []
760        self.learner.normalization = False  # Normalization already done
761
762        if self.svm_type in [1, 4]:
763            if self.svm_type == SVMLearner.Nu_SVC:
764                max_nu = max(self.max_nu(newexamples) - 1e-7, 0.0)
765            else:
766                max_nu = 1.0
767            parameters.append(("nu", [i / 10.0 for i in range(1, 9) \
768                                      if i / 10.0 < max_nu] + [max_nu]))
769        else:
770            parameters.append(("C", [2 ** a for a in  range(-5, 15, 2)]))
771        if self.kernel_type == 2:
772            parameters.append(
773                ("gamma", [2 ** a for a in range(-5, 5, 2)] + [0])
774            )
775
776        import orngWrap
777        tunedLearner = orngWrap.TuneMParameters(learner=self.learner,
778                                                parameters=parameters,
779                                                folds=self.folds)
780
781        return tunedLearner(newexamples, verbose=self.verbose)
782
783
784class SVMLearnerSparseEasy(SVMLearnerEasy):
785    def __init__(self, folds=4, verbose=0, **kwargs):
786        SVMLearnerEasy.__init__(self, folds=folds, verbose=verbose,
787                                **kwargs)
788        self.learner = SVMLearnerSparse(**kwargs)
789
790
791"""
792LIBLINEAR learners interface
793"""
794
795
796class LinearSVMLearner(Orange.core.LinearLearner):
797    """Train a linear SVM model."""
798
799    L2R_L2LOSS_DUAL = Orange.core.LinearLearner.L2R_L2Loss_SVC_Dual
800    L2R_L2LOSS = Orange.core.LinearLearner.L2R_L2Loss_SVC
801    L2R_L1LOSS_DUAL = Orange.core.LinearLearner.L2R_L1Loss_SVC_Dual
802    L1R_L2LOSS = Orange.core.LinearLearner.L1R_L2Loss_SVC
803
804    __new__ = _orange__new__(base=Orange.core.LinearLearner)
805
806    def __init__(self, solver_type=L2R_L2LOSS_DUAL, C=1.0, eps=0.01,
807                 bias=1.0, normalization=True, **kwargs):
808        """
809        :param solver_type: One of the following class constants:
810            ``L2R_L2LOSS_DUAL``, ``L2R_L2LOSS``,
811            ``L2R_L1LOSS_DUAL``, ``L1R_L2LOSS``
812
813            The first part (``L2R`` or ``L1R``) is the regularization term
814            on the weight vector (squared or absolute norm respectively),
815            the ``L1LOSS`` or ``L2LOSS`` indicate absolute or squared
816            loss function ``DUAL`` means the optimization problem is
817            solved in the dual space (for more information see the
818            documentation on `LIBLINEAR`_).
819
820        :param C: Regularization parameter (default 1.0)
821        :type C: float
822
823        :param eps: Stopping criteria (default 0.01)
824        :type eps: float
825
826        :param bias: If non negative then each instance is appended a constant
827            bias term (default 1.0).
828
829        :type bias: float
830
831        :param normalization: Normalize the input data into range [0..1] prior
832            to learning (default ``True``)
833        :type normalization: bool
834
835        .. note:: If the training data contains discrete features they are
836            replaced by indicator columns one for each value of the feature
837            regardless of the value of `normalization`. This is different
838            then in :class:`SVMLearner` where this is done only if
839            `normalization` is ``True``.
840
841        Example
842
843            >>> linear_svm = LinearSVMLearner(
844            ...     solver_type=LinearSVMLearner.L1R_L2LOSS,
845            ...     C=2.0)
846            ...
847
848        """
849        self.solver_type = solver_type
850        self.eps = eps
851        self.C = C
852        self.bias = bias
853        self.normalization = normalization
854
855        for name, val in kwargs.items():
856            setattr(self, name, val)
857        if self.solver_type not in [self.L2R_L2LOSS_DUAL, self.L2R_L2LOSS,
858                self.L2R_L1LOSS_DUAL, self.L1R_L2LOSS]:
859            warnings.warn("""\
860Deprecated 'solver_type', use
861'Orange.classification.logreg.LibLinearLogRegLearner'
862to build a logistic regression model using LIBLINEAR.
863""",
864                DeprecationWarning)
865
866    def __call__(self, data, weight_id=None):
867        if not isinstance(data.domain.class_var, variable.Discrete):
868            raise TypeError("Can only learn a discrete class.")
869
870        if data.domain.has_discrete_attributes(False) or self.normalization:
871            dc = Orange.data.continuization.DomainContinuizer()
872            dc.multinomial_treatment = dc.NValues
873            dc.class_treatment = dc.Ignore
874            dc.continuous_treatment = \
875                    dc.NormalizeBySpan if self.normalization else dc.Leave
876            c_domain = dc(data)
877            data = data.translate(c_domain)
878
879        return super(LinearSVMLearner, self).__call__(data, weight_id)
880
881LinearLearner = LinearSVMLearner
882
883
884class MultiClassSVMLearner(Orange.core.LinearLearner):
885    """ Multi-class SVM (Crammer and Singer) from the `LIBLINEAR`_ library.
886    """
887    __new__ = _orange__new__(base=Orange.core.LinearLearner)
888
889    def __init__(self, C=1.0, eps=0.01, bias=1.0,
890                 normalization=True, **kwargs):
891        """\
892        :param C: Regularization parameter (default 1.0)
893        :type C: float
894
895        :param eps: Stopping criteria (default 0.01)
896        :type eps: float
897
898        :param bias: If non negative then each instance is appended a constant
899            bias term (default 1.0).
900
901        :type bias: float
902
903        :param normalization: Normalize the input data prior to learning
904            (default True)
905        :type normalization: bool
906
907        """
908        self.C = C
909        self.eps = eps
910        self.bias = bias
911        self.normalization = normalization
912        for name, val in kwargs.items():
913            setattr(self, name, val)
914
915        self.solver_type = self.MCSVM_CS
916
917    def __call__(self, data, weight_id=None):
918        if not isinstance(data.domain.class_var, variable.Discrete):
919            raise TypeError("Can only learn a discrete class.")
920
921        if data.domain.has_discrete_attributes(False) or self.normalization:
922            dc = Orange.data.continuization.DomainContinuizer()
923            dc.multinomial_treatment = dc.NValues
924            dc.class_treatment = dc.Ignore
925            dc.continuous_treatment = \
926                    dc.NormalizeBySpan if self.normalization else dc.Leave
927            c_domain = dc(data)
928            data = data.translate(c_domain)
929
930        return super(MultiClassSVMLearner, self).__call__(data, weight_id)
931
932#TODO: Unified way to get attr weights for linear SVMs.
933
934
935def get_linear_svm_weights(classifier, sum=True):
936    """Extract attribute weights from the linear SVM classifier.
937
938    For multi class classification, the result depends on the argument
939    :obj:`sum`. If ``True`` (default) the function computes the
940    squared sum of the weights over all binary one vs. one
941    classifiers. If :obj:`sum` is ``False`` it returns a list of
942    weights for each individual binary classifier (in the order of
943    [class1 vs class2, class1 vs class3 ... class2 vs class3 ...]).
944
945    """
946
947    def update_weights(w, key, val, mul):
948        if key in w:
949            w[key] += mul * val
950        else:
951            w[key] = mul * val
952
953    def to_float(val):
954        return float(val) if not val.isSpecial() else 0.0
955
956    SVs = classifier.support_vectors
957    class_var = SVs.domain.class_var
958
959    if classifier.svm_type in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]:
960        weights = []
961        classes = classifier.class_var.values
962        for i in range(len(classes) - 1):
963            for j in range(i + 1, len(classes)):
964                # Get the coef and rho values from the binary sub-classifier
965                # Easier then using the full coef matrix (due to libsvm
966                # internal class  reordering)
967                bin_classifier = classifier.get_binary_classifier(i, j)
968                n_sv0 = bin_classifier.n_SV[0]
969                SVs = bin_classifier.support_vectors
970                w = {}
971
972                for coef, sv_ind in bin_classifier.coef[0]:
973                    SV = SVs[sv_ind]
974                    attributes = SVs.domain.attributes + \
975                    SV.getmetas(False, Orange.feature.Descriptor).keys()
976                    for attr in attributes:
977                        if attr.varType == Orange.feature.Type.Continuous:
978                            update_weights(w, attr, to_float(SV[attr]), coef)
979
980                weights.append(w)
981        if sum:
982            scores = defaultdict(float)
983            for w in weights:
984                for attr, w_attr in w.items():
985                    scores[attr] += w_attr ** 2
986            for key in scores:
987                scores[key] = math.sqrt(scores[key])
988            weights = dict(scores)
989    else:
990        weights = {}
991        for coef, sv_ind in classifier.coef[0]:
992            SV = SVs[sv_ind]
993            attributes = SVs.domain.attributes + \
994            SV.getmetas(False, Orange.feature.Descriptor).keys()
995            for attr in attributes:
996                if attr.varType == Orange.feature.Type.Continuous:
997                    update_weights(weights, attr, to_float(SV[attr]), coef)
998
999    return weights
1000
1001getLinearSVMWeights = get_linear_svm_weights
1002
1003
1004def example_weighted_sum(example, weights):
1005    sum = 0
1006    for attr, w in weights.items():
1007        sum += float(example[attr]) * w
1008    return sum
1009
1010exampleWeightedSum = example_weighted_sum
1011
1012
1013class ScoreSVMWeights(Orange.feature.scoring.Score):
1014    """
1015    Score a feature using squared weights of a linear SVM model.
1016
1017    Example:
1018
1019        >>> table = Orange.data.Table("vehicle.tab")
1020        >>> score = Orange.classification.svm.ScoreSVMWeights()
1021        >>> svm_scores = [(score(f, table), f) for f in table.domain.features]
1022        >>> for feature_score, feature in sorted(svm_scores, reverse=True):
1023        ...     print "%-35s: %.3f" % (feature.name, feature_score)
1024        pr.axis aspect ratio               : 44.263
1025        kurtosis about major axis          : 42.593
1026        max.length rectangularity          : 39.377
1027        radius ratio                       : 28.741
1028        skewness about major axis          : 26.682
1029        hollows ratio                      : 20.993
1030        compactness                        : 20.085
1031        elongatedness                      : 17.410
1032        distance circularity               : 14.542
1033        scaled radius of gyration          : 12.584
1034        max.length aspect ratio            : 10.686
1035        scatter ratio                      : 10.574
1036        scaled variance along minor axis   : 10.049
1037        circularity                        : 8.360
1038        pr.axis rectangularity             : 7.473
1039        scaled variance along major axis   : 5.731
1040        skewness about minor axis          : 1.368
1041        kurtosis about minor axis          : 0.690
1042
1043
1044    """
1045
1046    handles_discrete = True
1047    handles_continuous = True
1048    computes_thresholds = False
1049    needs = Orange.feature.scoring.Score.Generator
1050
1051    def __new__(cls, attr=None, data=None, weight_id=None, **kwargs):
1052        self = Orange.feature.scoring.Score.__new__(cls, **kwargs)
1053        if data is not None and attr is not None:
1054            self.__init__(**kwargs)
1055            return self.__call__(attr, data, weight_id)
1056        else:
1057            return self
1058
1059    def __reduce__(self):
1060        return ScoreSVMWeights, (), dict(self.__dict__)
1061
1062    def __init__(self, learner=None, **kwargs):
1063        """
1064        :param learner: Learner used for weight estimation
1065            (by default
1066            ``LinearSVMLearner(solver_type=L2R_L2LOSS_DUAL, C=1.0)``
1067            will be used for classification problems and
1068            ``SVMLearner(svm_type=Epsilon_SVR, kernel_type=Linear, C=1.0, p=0.25)``
1069            for regression problems).
1070
1071        :type learner: Orange.core.LinearLearner
1072
1073        """
1074        self.learner = learner
1075        self._cached_data = None
1076        self._cached_data_crc = None
1077        self._cached_weights = None
1078        self._cached_classifier = None
1079
1080    def __call__(self, attr, data, weight_id=None):
1081        if attr not in data.domain.attributes:
1082            raise ValueError("Feature %r is not from the domain." % attr)
1083
1084        if self.learner is not None:
1085            learner = self.learner
1086        elif isinstance(data.domain.class_var, variable.Discrete):
1087            learner = LinearSVMLearner(
1088                            solver_type=LinearSVMLearner.L2R_L2LOSS_DUAL,
1089                            C=1.0)
1090
1091        elif isinstance(data.domain.class_var, variable.Continuous):
1092            learner = SVMLearner(svm_type=SVMLearner.Epsilon_SVR,
1093                                 kernel_type=kernels.Linear,
1094                                 C=1.0, p=0.25)
1095        else:
1096            raise TypeError("Cannot handle the class variable type %r" % \
1097                                type(data.domain.class_var))
1098
1099        crc = data.checksum()
1100        if data is self._cached_data and crc == self._cached_data_crc:
1101            weights = self._cached_weights
1102        else:
1103            classifier = learner(data, weight_id)
1104            self._cached_data = data
1105            self._cached_data_crc = data.checksum()
1106            self._cached_classifier = classifier
1107            weights = self._extract_weights(classifier, data.domain.attributes)
1108            self._cached_weights = weights
1109        return weights.get(attr, 0.0)
1110
1111    def _extract_weights(self, classifier, original_features):
1112        """Extract weights from a svm classifer (``SVMClassifier`` or a
1113        ``LinearLearner`` instance).
1114
1115        """
1116        import numpy as np
1117        if isinstance(classifier, SVMClassifier):
1118            weights = get_linear_svm_weights(classifier, sum=True)
1119            if isinstance(classifier.class_var, variable.Continuous):
1120                # The weights are in the the original non squared form
1121                weights = dict((f, w ** 2) for f, w in weights.items())
1122        elif isinstance(classifier, Orange.core.LinearClassifier):
1123            weights = np.array(classifier.weights)
1124            weights = np.sum(weights ** 2, axis=0)
1125            weights = dict(zip(classifier.domain.attributes, weights))
1126        else:
1127            raise TypeError("Don't know how to use classifier type %r" % \
1128                                type(classifier))
1129
1130        # collect dummy variables that were created for discrete features
1131        sources = self._collect_source(weights.keys())
1132        source_weights = dict.fromkeys(original_features, 0.0)
1133        for f in original_features:
1134            if f in weights:
1135                source_weights[f] = weights[f]
1136            elif f not in weights and f in sources:
1137                dummys = sources[f]
1138                # Use averege weight
1139                source_weights[f] = np.average([weights[d] for d in dummys])
1140            else:
1141                raise ValueError(f)
1142
1143        return source_weights
1144
1145    def _collect_source(self, vars):
1146        """ Given a list of variables ``var``, return a mapping from source
1147        variables (``source_variable`` or ``get_value_from.variable`` members)
1148        back to the variables in ``vars``.
1149
1150        """
1151        source = defaultdict(list)
1152        for var in vars:
1153            if var.source_variable:
1154                source[var.source_variable].append(var)
1155            elif isinstance(var.get_value_from, Orange.core.ClassifierFromVar):
1156                source[var.get_value_from.variable].append(var)
1157            elif isinstance(var.get_value_from, Orange.core.ImputeClassifier):
1158                imputer = var.get_value_from.classifier_from_var
1159                source[imputer.variable].append(var)
1160            else:
1161                source[var].append(var)
1162        return dict(source)
1163
1164MeasureAttribute_SVMWeights = ScoreSVMWeights
1165
1166
1167class RFE(object):
1168
1169    """Iterative feature elimination based on weights computed by
1170    linear SVM.
1171
1172    Example::
1173
1174        >>> table = Orange.data.Table("promoters.tab")
1175        >>> svm_l = Orange.classification.svm.SVMLearner(
1176        ...     kernel_type=Orange.classification.svm.kernels.Linear)
1177        ...
1178        >>> rfe = Orange.classification.svm.RFE(learner=svm_l)
1179        >>> data_with_subset_of_features = rfe(table, 10)
1180        >>> data_with_subset_of_features.domain
1181        [p-45, p-36, p-35, p-34, p-33, p-31, p-18, p-12, p-10, p-04, y]
1182
1183    """
1184
1185    def __init__(self, learner=None):
1186        """
1187        :param learner: A linear svm learner for use with
1188            :class:`ScoreSVMWeights`.
1189
1190        """
1191        self.learner = learner
1192
1193    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback",
1194                                       "stopAt": "stop_at"})
1195    def get_attr_scores(self, data, stop_at=0, progress_callback=None):
1196        """Return a dictionary mapping attributes to scores.
1197        A score is a step number at which the attribute
1198        was removed from the recursive evaluation.
1199
1200        """
1201        iter = 1
1202        attrs = data.domain.attributes
1203        attr_scores = {}
1204        scorer = ScoreSVMWeights(learner=self.learner)
1205
1206        while len(attrs) > stop_at:
1207            scores = [(scorer(attr, data), attr) for attr in attrs]
1208            if progress_callback:
1209                progress_callback(100. * iter / (len(attrs) - stop_at))
1210            scores = sorted(scores)
1211            num_to_remove = max(int(len(attrs) * 1.0 / (iter + 1)), 1)
1212            for s, attr in  scores[:num_to_remove]:
1213                attr_scores[attr] = len(attr_scores)
1214            attrs = [attr for s, attr in scores[num_to_remove:]]
1215            if attrs:
1216                data = data.select(attrs + [data.domain.class_var])
1217            iter += 1
1218        return attr_scores
1219
1220    @Orange.utils.deprecated_keywords(
1221        {"numSelected": "num_selected",
1222         "progressCallback": "progress_callback"})
1223    def __call__(self, data, num_selected=20, progress_callback=None):
1224        """Return a new dataset with only `num_selected` best scoring
1225        attributes.
1226
1227        :param data: Data
1228        :type data: Orange.data.Table
1229
1230        :param num_selected: number of features to preserve
1231        :type num_selected: int
1232
1233        """
1234        scores = self.get_attr_scores(data, progress_callback=progress_callback)
1235        scores = sorted(scores.items(), key=lambda item: item[1])
1236
1237        scores = dict(scores[-num_selected:])
1238        attrs = [attr for attr in data.domain.attributes if attr in scores]
1239        domain = Orange.data.Domain(attrs, data.domain.classVar)
1240        domain.addmetas(data.domain.getmetas())
1241        data = Orange.data.Table(domain, data)
1242        return data
1243
1244
1245RFE = Orange.utils.deprecated_members({
1246    "getAttrScores": "get_attr_scores"},
1247    wrap_methods=["get_attr_scores", "__call__"])(RFE)
1248
1249
1250def example_table_to_svm_format(table, file):
1251    warnings.warn("Deprecated. Use table_to_svm_format", DeprecationWarning)
1252    table_to_svm_format(table, file)
1253
1254exampleTableToSVMFormat = example_table_to_svm_format
1255
1256
1257def table_to_svm_format(data, file):
1258    """Save :obj:`Orange.data.Table` to a format used by LibSVM.
1259
1260    :param data: Data
1261    :type data: Orange.data.Table
1262    :param file: file pointer
1263    :type file: file
1264
1265    """
1266
1267    attrs = data.domain.attributes + data.domain.getmetas().values()
1268    attrs = [attr for attr in attrs if attr.varType
1269             in [Orange.feature.Type.Continuous,
1270                 Orange.feature.Type.Discrete]]
1271    cv = data.domain.classVar
1272
1273    for ex in data:
1274        if cv.varType == Orange.feature.Type.Discrete:
1275            file.write(str(int(ex[cv])))
1276        else:
1277            file.write(str(float(ex[cv])))
1278
1279        for i, attr in enumerate(attrs):
1280            if not ex[attr].isSpecial():
1281                file.write(" " + str(i + 1) + ":" + str(float(ex[attr])))
1282        file.write("\n")
1283
1284tableToSVMFormat = table_to_svm_format
Note: See TracBrowser for help on using the repository browser.