source: orange/Orange/classification/svm/__init__.py @ 10751:91e1dac1b42f

Revision 10751:91e1dac1b42f, 45.3 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Fixed an error when the wrapped model has no support vectors.

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                 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 normalization: Normalize the input data prior to learning
761            (default True)
762        :type normalization: bool
763       
764        Example
765       
766            >>> linear_svm = LinearSVMLearner(solver_type=LinearSVMLearner.L1R_L2LOSS,
767            ...                               C=2.0)
768            ...
769       
770        """
771        self.solver_type = solver_type
772        self.eps = eps
773        self.C = C
774        self.normalization = normalization
775
776        for name, val in kwargs.items():
777            setattr(self, name, val)
778        if self.solver_type not in [self.L2R_L2LOSS_DUAL, self.L2R_L2LOSS,
779                self.L2R_L1LOSS_DUAL, self.L1R_L2LOSS]:
780            import warnings
781            warnings.warn("""\
782Deprecated 'solver_type', use
783'Orange.classification.logreg.LibLinearLogRegLearner'
784to build a logistic regression model using LIBLINEAR.
785""",
786                DeprecationWarning)
787
788    def __call__(self, data, weight_id=None):
789        if not isinstance(data.domain.class_var, variable.Discrete):
790            raise TypeError("Can only learn a discrete class.")
791
792        if data.domain.has_discrete_attributes(False) or self.normalization:
793            dc = Orange.data.continuization.DomainContinuizer()
794            dc.multinomial_treatment = dc.NValues
795            dc.class_treatment = dc.Ignore
796            dc.continuous_treatment = \
797                    dc.NormalizeBySpan if self.normalization else dc.Leave
798            c_domain = dc(data)
799            data = data.translate(c_domain)
800
801        return super(LinearSVMLearner, self).__call__(data, weight_id)
802
803LinearLearner = LinearSVMLearner
804
805class MultiClassSVMLearner(Orange.core.LinearLearner):
806    """ Multi-class SVM (Crammer and Singer) from the `LIBLINEAR`_ library.
807   
808    """
809    __new__ = _orange__new__(base=Orange.core.LinearLearner)
810
811    def __init__(self, C=1.0, eps=0.01, normalization=True, **kwargs):
812        """\
813        :param C: Regularization parameter (default 1.0)
814        :type C: float 
815       
816        :param eps: Stopping criteria (default 0.01)
817        :type eps: float
818       
819        :param normalization: Normalize the input data prior to learning
820            (default True)
821        :type normalization: bool
822       
823        """
824        self.C = C
825        self.eps = eps
826        self.normalization = normalization
827        for name, val in kwargs.items():
828            setattr(self, name, val)
829
830        self.solver_type = self.MCSVM_CS
831
832    def __call__(self, data, weight_id=None):
833        if not isinstance(data.domain.class_var, variable.Discrete):
834            raise TypeError("Can only learn a discrete class.")
835
836        if data.domain.has_discrete_attributes(False) or self.normalization:
837            dc = Orange.data.continuization.DomainContinuizer()
838            dc.multinomial_treatment = dc.NValues
839            dc.class_treatment = dc.Ignore
840            dc.continuous_treatment = \
841                    dc.NormalizeBySpan if self.normalization else dc.Leave
842            c_domain = dc(data)
843            data = data.translate(c_domain)
844
845        return super(MultiClassSVMLearner, self).__call__(data, weight_id)
846
847#TODO: Unified way to get attr weights for linear SVMs.
848
849def get_linear_svm_weights(classifier, sum=True):
850    """Extract attribute weights from the linear SVM classifier.
851   
852    For multi class classification, the result depends on the argument
853    :obj:`sum`. If ``True`` (default) the function computes the
854    squared sum of the weights over all binary one vs. one
855    classifiers. If :obj:`sum` is ``False`` it returns a list of
856    weights for each individual binary classifier (in the order of
857    [class1 vs class2, class1 vs class3 ... class2 vs class3 ...]).
858       
859    """
860
861    def update_weights(w, key, val, mul):
862        if key in w:
863            w[key] += mul * val
864        else:
865            w[key] = mul * val
866
867    def to_float(val):
868        return float(val) if not val.isSpecial() else 0.0
869
870    SVs = classifier.support_vectors
871    class_var = SVs.domain.class_var
872
873    if classifier.svm_type in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]:
874        weights = []   
875        classes = classifier.class_var.values
876        for i in range(len(classes) - 1):
877            for j in range(i + 1, len(classes)):
878                # Get the coef and rho values from the binary sub-classifier
879                # Easier then using the full coef matrix (due to libsvm internal
880                # class  reordering)
881                bin_classifier = classifier.get_binary_classifier(i, j)
882                n_sv0 = bin_classifier.n_SV[0]
883                SVs = bin_classifier.support_vectors
884                w = {}
885
886                for coef, sv_ind in bin_classifier.coef[0]:
887                    SV = SVs[sv_ind]
888                    attributes = SVs.domain.attributes + \
889                    SV.getmetas(False, Orange.feature.Descriptor).keys()
890                    for attr in attributes:
891                        if attr.varType == Orange.feature.Type.Continuous:
892                            update_weights(w, attr, to_float(SV[attr]), coef)
893
894                weights.append(w)
895        if sum:
896            scores = defaultdict(float)
897            for w in weights:
898                for attr, w_attr in w.items():
899                    scores[attr] += w_attr ** 2
900            for key in scores:
901                scores[key] = math.sqrt(scores[key])
902            weights = dict(scores)
903    else:
904        weights = {}
905        for coef, sv_ind in classifier.coef[0]:
906            SV = SVs[sv_ind]
907            attributes = SVs.domain.attributes + \
908            SV.getmetas(False, Orange.feature.Descriptor).keys()
909            for attr in attributes:
910                if attr.varType == Orange.feature.Type.Continuous:
911                    update_weights(weights, attr, to_float(SV[attr]), coef)
912
913    return weights
914
915getLinearSVMWeights = get_linear_svm_weights
916
917def example_weighted_sum(example, weights):
918    sum = 0
919    for attr, w in weights.items():
920        sum += float(example[attr]) * w
921    return sum
922
923exampleWeightedSum = example_weighted_sum
924
925class ScoreSVMWeights(Orange.feature.scoring.Score):
926    """
927    Score a feature using squared weights of a linear SVM model.
928       
929    Example:
930   
931        >>> table = Orange.data.Table("vehicle.tab")
932        >>> score = Orange.classification.svm.ScoreSVMWeights()
933        >>> svm_scores = [(score(f, table), f) for f in table.domain.features]
934        >>> for feature_score, feature in sorted(svm_scores, reverse=True):
935        ...     print "%-35s: %.3f" % (feature.name, feature_score)
936        kurtosis about major axis          : 47.113
937        pr.axis aspect ratio               : 44.949
938        max.length rectangularity          : 39.748
939        radius ratio                       : 29.098
940        scatter ratio                      : 26.133
941        skewness about major axis          : 24.403
942        compactness                        : 20.432
943        hollows ratio                      : 20.109
944        max.length aspect ratio            : 15.757
945        scaled radius of gyration          : 15.242
946        scaled variance along minor axis   : 14.289
947        pr.axis rectangularity             : 9.882
948        circularity                        : 8.293
949        distance circularity               : 7.785
950        scaled variance along major axis   : 6.179
951        elongatedness                      : 4.038
952        skewness about minor axis          : 1.351
953        kurtosis about minor axis          : 0.760
954
955    """
956
957    handles_discrete = True
958    handles_continuous = True
959    computes_thresholds = False
960    needs = Orange.feature.scoring.Score.Generator
961
962    def __new__(cls, attr=None, data=None, weight_id=None, **kwargs):
963        self = Orange.feature.scoring.Score.__new__(cls, **kwargs)
964        if data is not None and attr is not None:
965            self.__init__(**kwargs)
966            return self.__call__(attr, data, weight_id)
967        else:
968            return self
969
970    def __reduce__(self):
971        return ScoreSVMWeights, (), dict(self.__dict__)
972
973    def __init__(self, learner=None, **kwargs):
974        """
975        :param learner: Learner used for weight estimation
976            (by default ``LinearSVMLearner(solver_type=L2R_L2LOSS_DUAL, C=1.0)``
977            will be used for classification problems and
978            ``SVMLearner(svm_type=Epsilon_SVR, kernel_type=Linear, C=1.0, p=0.25)``
979            for regression problems.
980           
981        :type learner: Orange.core.LinearLearner
982       
983        """
984        self.learner = learner
985        self._cached_data = None
986        self._cached_data_crc = None
987        self._cached_weights = None
988        self._cached_classifier = None
989
990    def __call__(self, attr, data, weight_id=None):
991        if attr not in data.domain.attributes:
992            raise ValueError("Feature %r is not from the domain." % attr)
993
994        if self.learner is not None:
995            learner = self.learner
996        elif isinstance(data.domain.class_var, variable.Discrete):
997            learner = LinearSVMLearner(solver_type=
998                                LinearSVMLearner.L2R_L2LOSS_DUAL,
999                                C=1.0)
1000        elif isinstance(data.domain.class_var, variable.Continuous):
1001            learner = SVMLearner(svm_type=SVMLearner.Epsilon_SVR,
1002                                 kernel_type=kernels.Linear,
1003                                 C=1.0, p=0.25)
1004        else:
1005            raise TypeError("Cannot handle the class variable type %r" % \
1006                                type(data.domain.class_var))
1007
1008        crc = data.checksum()
1009        if data is self._cached_data and crc == self._cached_data_crc:
1010            weights = self._cached_weights
1011        else:
1012            classifier = learner(data, weight_id)
1013            self._cached_data = data
1014            self._cached_data_crc = data.checksum()
1015            self._cached_classifier = classifier
1016            weights = self._extract_weights(classifier, data.domain.attributes)
1017            self._cached_weights = weights
1018        return weights.get(attr, 0.0)
1019
1020    def _extract_weights(self, classifier, original_features):
1021        """Extract weights from a svm classifer (``SVMClassifier`` or a
1022        ``LinearLearner`` instance).
1023       
1024        """
1025        import numpy as np
1026        if isinstance(classifier, SVMClassifier):
1027            weights = get_linear_svm_weights(classifier, sum=True)
1028            if isinstance(classifier.class_var, variable.Continuous):
1029                # The weights are in the the original non squared form
1030                weights = dict((f, w ** 2) for f, w in weights.items()) 
1031        elif isinstance(classifier, Orange.core.LinearClassifier):
1032            weights = np.array(classifier.weights)
1033            weights = np.sum(weights ** 2, axis=0)
1034            weights = dict(zip(classifier.domain.attributes, weights))
1035        else:
1036            raise TypeError("Don't know how to use classifier type %r" % \
1037                                type(classifier))
1038
1039        # collect dummy variables that were created for discrete features
1040        sources = self._collect_source(weights.keys())
1041        source_weights = dict.fromkeys(original_features, 0.0)
1042        for f in original_features:
1043            if f in weights:
1044                source_weights[f] = weights[f]
1045            elif f not in weights and f in sources:
1046                dummys = sources[f]
1047                # Use averege weight 
1048                source_weights[f] = np.average([weights[d] for d in dummys])
1049            else:
1050                raise ValueError(f)
1051
1052        return source_weights
1053
1054    def _collect_source(self, vars):
1055        """ Given a list of variables ``var``, return a mapping from source
1056        variables (``source_variable`` or ``get_value_from.variable`` members)
1057        back to the variables in ``vars``.
1058       
1059        """
1060        source = defaultdict(list)
1061        for var in vars:
1062            svar = None
1063            if var.source_variable:
1064                source[var.source_variable].append(var)
1065            elif isinstance(var.get_value_from, Orange.core.ClassifierFromVar):
1066                source[var.get_value_from.variable].append(var)
1067            elif isinstance(var.get_value_from, Orange.core.ImputeClassifier):
1068                source[var.get_value_from.classifier_from_var.variable].append(var)
1069            else:
1070                source[var].append(var)
1071        return dict(source)
1072
1073MeasureAttribute_SVMWeights = ScoreSVMWeights
1074
1075class RFE(object):
1076
1077    """Iterative feature elimination based on weights computed by
1078    linear SVM.
1079   
1080    Example::
1081   
1082        >>> table = Orange.data.Table("promoters.tab")
1083        >>> svm_l = Orange.classification.svm.SVMLearner(
1084        ...     kernel_type=Orange.classification.svm.kernels.Linear)
1085        ...
1086        >>> rfe = Orange.classification.svm.RFE(learner=svm_l)
1087        >>> data_with_subset_of_features = rfe(table, 10)
1088        >>> data_with_subset_of_features.domain
1089        [p-45, p-36, p-35, p-34, p-33, p-31, p-18, p-12, p-10, p-04, y]
1090       
1091    """
1092
1093    def __init__(self, learner=None):
1094        """
1095        :param learner: A linear svm learner for use with
1096            :class:`ScoreSVMWeights`.
1097       
1098        """
1099        self.learner = learner
1100
1101    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback", "stopAt": "stop_at" })
1102    def get_attr_scores(self, data, stop_at=0, progress_callback=None):
1103        """Return a dictionary mapping attributes to scores.
1104        A score is a step number at which the attribute
1105        was removed from the recursive evaluation.
1106       
1107        """
1108        iter = 1
1109        attrs = data.domain.attributes
1110        attr_scores = {}
1111        scorer = ScoreSVMWeights(learner=self.learner)
1112
1113        while len(attrs) > stop_at:
1114            scores = [(scorer(attr, data), attr) for attr in attrs]
1115            if progress_callback:
1116                progress_callback(100. * iter / (len(attrs) - stop_at))
1117            scores = sorted(scores)
1118            num_to_remove = max(int(len(attrs) * 1.0 / (iter + 1)), 1)
1119            for s, attr in  scores[:num_to_remove]:
1120                attr_scores[attr] = len(attr_scores)
1121            attrs = [attr for s, attr in scores[num_to_remove:]]
1122            if attrs:
1123                data = data.select(attrs + [data.domain.class_var])
1124            iter += 1
1125        return attr_scores
1126
1127    @Orange.utils.deprecated_keywords({"numSelected": "num_selected", "progressCallback": "progress_callback"})
1128    def __call__(self, data, num_selected=20, progress_callback=None):
1129        """Return a new dataset with only `num_selected` best scoring attributes
1130       
1131        :param data: Data
1132        :type data: Orange.data.Table
1133       
1134        :param num_selected: number of features to preserve
1135        :type num_selected: int
1136       
1137        """
1138        scores = self.get_attr_scores(data, progress_callback=progress_callback)
1139        scores = sorted(scores.items(), key=lambda item: item[1])
1140
1141        scores = dict(scores[-num_selected:])
1142        attrs = [attr for attr in data.domain.attributes if attr in scores]
1143        domain = Orange.data.Domain(attrs, data.domain.classVar)
1144        domain.addmetas(data.domain.getmetas())
1145        data = Orange.data.Table(domain, data)
1146        return data
1147
1148RFE = Orange.utils.deprecated_members({
1149    "getAttrScores": "get_attr_scores"},
1150    wrap_methods=["get_attr_scores", "__call__"])(RFE)
1151
1152def example_table_to_svm_format(table, file):
1153    warnings.warn("Deprecated. Use table_to_svm_format", DeprecationWarning)
1154    table_to_svm_format(table, file)
1155
1156exampleTableToSVMFormat = example_table_to_svm_format
1157
1158def table_to_svm_format(data, file):
1159    """Save :obj:`Orange.data.Table` to a format used by LibSVM.
1160   
1161    :param data: Data
1162    :type data: Orange.data.Table
1163    :param file: file pointer
1164    :type file: file
1165   
1166    """
1167
1168    attrs = data.domain.attributes + data.domain.getmetas().values()
1169    attrs = [attr for attr in attrs if attr.varType
1170             in [Orange.feature.Type.Continuous,
1171                 Orange.feature.Type.Discrete]]
1172    cv = data.domain.classVar
1173
1174    for ex in data:
1175        if cv.varType == Orange.feature.Type.Discrete:
1176            file.write(str(int(ex[cv])))
1177        else:
1178            file.write(str(float(ex[cv])))
1179
1180        for i, attr in enumerate(attrs):
1181            if not ex[attr].isSpecial():
1182                file.write(" " + str(i + 1) + ":" + str(float(ex[attr])))
1183        file.write("\n")
1184
1185tableToSVMFormat = table_to_svm_format
Note: See TracBrowser for help on using the repository browser.