source: orange/Orange/classification/svm/__init__.py @ 11604:89a5fa18f2a6

Revision 11604:89a5fa18f2a6, 47.9 KB checked in by Ales Erjavec <ales.erjavec@…>, 10 months ago (diff)

Fixed a type check.

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