source: orange/Orange/classification/svm/__init__.py @ 10955:8fd59ece1784

Revision 10955:8fd59ece1784, 46.1 KB checked in by Ales Erjavec <ales.erjavec@…>, 21 months ago (diff)

Code style fixup.

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