source: orange/Orange/classification/svm/__init__.py @ 10774:78f837b88776

Revision 10774:78f837b88776, 45.7 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Added bias term parameter to the LinearSVMLearner and MulticlassSVMLearner.

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