source: orange/Orange/classification/svm/__init__.py @ 10664:1c41c9dd6c8f

Revision 10664:1c41c9dd6c8f, 40.0 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Added doctests to the svm test suite.

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