source: orange/Orange/classification/svm/__init__.py @ 10695:f89944e24e5e

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

Using ScoreSVMWeights in RFE.

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