source: orange/Orange/classification/svm/__init__.py @ 11612:aa911724fb25

Revision 11612:aa911724fb25, 47.2 KB checked in by Ales Erjavec <ales.erjavec@…>, 10 months ago (diff)

Fixed changed SVM doctest output.

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:  %.2f" % scoring.CA(results)[0]
109        CA:  0.79
110        >>> print "AUC: %.2f" % scoring.AUC(results)[0]
111        AUC: 0.95
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: %.1f" % (feature.name, feature_score)
1051        pr.axis aspect ratio               : 44.3
1052        kurtosis about major axis          : 42.6
1053        max.length rectangularity          : 39.4
1054        radius ratio                       : 28.7
1055        ...
1056
1057
1058    """
1059
1060    handles_discrete = True
1061    handles_continuous = True
1062    computes_thresholds = False
1063    needs = Orange.feature.scoring.Score.Generator
1064
1065    def __new__(cls, attr=None, data=None, weight_id=None, **kwargs):
1066        self = Orange.feature.scoring.Score.__new__(cls, **kwargs)
1067        if data is not None and attr is not None:
1068            self.__init__(**kwargs)
1069            return self.__call__(attr, data, weight_id)
1070        else:
1071            return self
1072
1073    def __reduce__(self):
1074        return ScoreSVMWeights, (), dict(self.__dict__)
1075
1076    def __init__(self, learner=None, **kwargs):
1077        """
1078        :param learner: Learner used for weight estimation
1079            (by default
1080            ``LinearSVMLearner(solver_type=L2R_L2LOSS_DUAL, C=1.0)``
1081            will be used for classification problems and
1082            ``SVMLearner(svm_type=Epsilon_SVR, kernel_type=Linear, C=1.0, p=0.25)``
1083            for regression problems).
1084
1085        :type learner: Orange.core.LinearLearner
1086
1087        """
1088        self.learner = learner
1089        self._cached_data = None
1090        self._cached_data_crc = None
1091        self._cached_weights = None
1092        self._cached_classifier = None
1093
1094    def __call__(self, attr, data, weight_id=None):
1095        if attr not in data.domain.attributes:
1096            raise ValueError("Feature %r is not from the domain." % attr)
1097
1098        if self.learner is not None:
1099            learner = self.learner
1100        elif isinstance(data.domain.class_var, variable.Discrete):
1101            learner = LinearSVMLearner(
1102                            solver_type=LinearSVMLearner.L2R_L2LOSS_DUAL,
1103                            C=1.0)
1104
1105        elif isinstance(data.domain.class_var, variable.Continuous):
1106            learner = SVMLearner(svm_type=SVMLearner.Epsilon_SVR,
1107                                 kernel_type=kernels.Linear,
1108                                 C=1.0, p=0.25)
1109        else:
1110            raise TypeError("Cannot handle the class variable type %r" % \
1111                                type(data.domain.class_var))
1112
1113        crc = data.checksum()
1114        if data is self._cached_data and crc == self._cached_data_crc:
1115            weights = self._cached_weights
1116        else:
1117            classifier = learner(data, weight_id)
1118            self._cached_data = data
1119            self._cached_data_crc = data.checksum()
1120            self._cached_classifier = classifier
1121            weights = self._extract_weights(classifier, data.domain.attributes)
1122            self._cached_weights = weights
1123        return weights.get(attr, 0.0)
1124
1125    def _extract_weights(self, classifier, original_features):
1126        """Extract weights from a svm classifer (``SVMClassifier`` or a
1127        ``LinearLearner`` instance).
1128
1129        """
1130        import numpy as np
1131        if isinstance(classifier, SVMClassifier):
1132            weights = get_linear_svm_weights(classifier, sum=True)
1133            if isinstance(classifier.class_var, variable.Continuous):
1134                # The weights are in the the original non squared form
1135                weights = dict((f, w ** 2) for f, w in weights.items())
1136        elif isinstance(classifier, Orange.core.LinearClassifier):
1137            weights = np.array(classifier.weights)
1138            weights = np.sum(weights ** 2, axis=0)
1139            weights = dict(zip(classifier.domain.attributes, weights))
1140        else:
1141            raise TypeError("Don't know how to use classifier type %r" % \
1142                                type(classifier))
1143
1144        # collect dummy variables that were created for discrete features
1145        sources = self._collect_source(weights.keys())
1146        source_weights = dict.fromkeys(original_features, 0.0)
1147        for f in original_features:
1148            if f in weights:
1149                source_weights[f] = weights[f]
1150            elif f not in weights and f in sources:
1151                dummys = sources[f]
1152                # Use averege weight
1153                source_weights[f] = np.average([weights[d] for d in dummys])
1154            else:
1155                raise ValueError(f)
1156
1157        return source_weights
1158
1159    def _collect_source(self, vars):
1160        """ Given a list of variables ``var``, return a mapping from source
1161        variables (``source_variable`` or ``get_value_from.variable`` members)
1162        back to the variables in ``vars``.
1163
1164        """
1165        source = defaultdict(list)
1166        for var in vars:
1167            if var.source_variable:
1168                source[var.source_variable].append(var)
1169            elif isinstance(var.get_value_from, Orange.core.ClassifierFromVar):
1170                source[var.get_value_from.variable].append(var)
1171            elif isinstance(var.get_value_from, Orange.core.ImputeClassifier):
1172                imputer = var.get_value_from.classifier_from_var
1173                source[imputer.variable].append(var)
1174            else:
1175                source[var].append(var)
1176        return dict(source)
1177
1178MeasureAttribute_SVMWeights = ScoreSVMWeights
1179
1180
1181class RFE(object):
1182    """
1183    Iterative feature elimination based on weights computed by a
1184    linear SVM.
1185
1186    Example:
1187
1188        >>> table = Orange.data.Table("promoters.tab")
1189        >>> svm_l = Orange.classification.svm.SVMLearner(
1190        ...     kernel_type=Orange.classification.svm.kernels.Linear)
1191        ...
1192        >>> rfe = Orange.classification.svm.RFE(learner=svm_l)
1193        >>> data_with_subset_of_features = rfe(table, 10)
1194        >>> data_with_subset_of_features.domain
1195        [p-45, p-36, p-35, p-34, p-33, p-31, p-18, p-12, p-10, p-04, y]
1196
1197    """
1198
1199    def __init__(self, learner=None):
1200        """
1201        :param learner: A linear svm learner for use for scoring (this
1202            learner is passed to :class:`ScoreSVMWeights`)
1203
1204        :type learner: :class:`LinearSVMLearner` or :class:`SVMLearner` with
1205            linear kernel
1206
1207        .. seealso:: :class:`ScoreSVMWeights`
1208
1209        """
1210        self.learner = learner
1211
1212    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback",
1213                                       "stopAt": "stop_at"})
1214    def get_attr_scores(self, data, stop_at=0, progress_callback=None):
1215        """Return a dictionary mapping attributes to scores.
1216        A score is a step number at which the attribute
1217        was removed from the recursive evaluation.
1218
1219        """
1220        iter = 1
1221        attrs = data.domain.attributes
1222        attr_scores = {}
1223        scorer = ScoreSVMWeights(learner=self.learner)
1224
1225        while len(attrs) > stop_at:
1226            scores = [(scorer(attr, data), attr) for attr in attrs]
1227            if progress_callback:
1228                progress_callback(100. * iter / (len(attrs) - stop_at))
1229            scores = sorted(scores)
1230            num_to_remove = max(int(len(attrs) * 1.0 / (iter + 1)), 1)
1231            for s, attr in  scores[:num_to_remove]:
1232                attr_scores[attr] = len(attr_scores)
1233            attrs = [attr for s, attr in scores[num_to_remove:]]
1234            if attrs:
1235                data = data.select(attrs + [data.domain.class_var])
1236            iter += 1
1237        return attr_scores
1238
1239    @Orange.utils.deprecated_keywords(
1240        {"numSelected": "num_selected",
1241         "progressCallback": "progress_callback"})
1242    def __call__(self, data, num_selected=20, progress_callback=None):
1243        """Return a new dataset with only `num_selected` best scoring
1244        attributes.
1245
1246        :param data: Data
1247        :type data: Orange.data.Table
1248
1249        :param num_selected: number of features to preserve
1250        :type num_selected: int
1251
1252        """
1253        scores = self.get_attr_scores(data, progress_callback=progress_callback)
1254        scores = sorted(scores.items(), key=lambda item: item[1])
1255
1256        scores = dict(scores[-num_selected:])
1257        attrs = [attr for attr in data.domain.attributes if attr in scores]
1258        domain = Orange.data.Domain(attrs, data.domain.classVar)
1259        domain.addmetas(data.domain.getmetas())
1260        data = Orange.data.Table(domain, data)
1261        return data
1262
1263
1264RFE = Orange.utils.deprecated_members({
1265    "getAttrScores": "get_attr_scores"},
1266    wrap_methods=["get_attr_scores", "__call__"])(RFE)
1267
1268
1269def example_table_to_svm_format(table, file):
1270    warnings.warn("Deprecated. Use table_to_svm_format", DeprecationWarning)
1271    table_to_svm_format(table, file)
1272
1273exampleTableToSVMFormat = example_table_to_svm_format
1274
1275
1276def table_to_svm_format(data, file):
1277    """Save :obj:`Orange.data.Table` to a format used by LibSVM.
1278
1279    :param data: Data
1280    :type data: Orange.data.Table
1281    :param file: file pointer
1282    :type file: file
1283
1284    """
1285
1286    attrs = data.domain.attributes + data.domain.getmetas().values()
1287    attrs = [attr for attr in attrs if attr.varType
1288             in [Orange.feature.Type.Continuous,
1289                 Orange.feature.Type.Discrete]]
1290    cv = data.domain.classVar
1291
1292    for ex in data:
1293        if cv.varType == Orange.feature.Type.Discrete:
1294            file.write(str(int(ex[cv])))
1295        else:
1296            file.write(str(float(ex[cv])))
1297
1298        for i, attr in enumerate(attrs):
1299            if not ex[attr].isSpecial():
1300                file.write(" " + str(i + 1) + ":" + str(float(ex[attr])))
1301        file.write("\n")
1302
1303tableToSVMFormat = table_to_svm_format
Note: See TracBrowser for help on using the repository browser.