source: orange/Orange/classification/svm/__init__.py @ 10679:3eefc11fe7c0

Revision 10679:3eefc11fe7c0, 41.6 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Added normalization parameter to MultiClassSVMLearner. Changed how and when DomainContinuizer is used.

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"""
728class LinearSVMLearner(Orange.core.LinearLearner):
729    """Train a linear SVM model."""
730
731    L2R_L2LOSS_DUAL = Orange.core.LinearLearner.L2R_L2Loss_SVC_Dual
732    L2R_L2LOSS = Orange.core.LinearLearner.L2R_L2Loss_SVC
733    L2R_L1LOSS_DUAL = Orange.core.LinearLearner.L2R_L1Loss_SVC_Dual
734    L2R_L1LOSS_DUAL = Orange.core.LinearLearner.L2R_L2Loss_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            ``LR2_L2LOSS_DUAL``, ``L2R_L2LOSS``,
744            ``LR2_L1LOSS_DUAL``, ``L2R_L1LOSS`` or
745            ``L1R_L2LOSS``
746       
747        :param C: Regularization parameter (default 1.0)
748        :type C: float 
749       
750        :param eps: Stopping criteria (default 0.01)
751        :type eps: float
752       
753        :param normalization: Normalize the input data prior to learning
754            (default True)
755        :type normalization: bool
756       
757        """
758        self.solver_type = solver_type
759        self.eps = eps
760        self.C = C
761        self.normalization = normalization
762
763        for name, val in kwargs.items():
764            setattr(self, name, val)
765        if self.solver_type not in [self.L2R_L2LOSS_DUAL, self.L2R_L2LOSS,
766                self.L2R_L1LOSS_DUAL, self.L2R_L1LOSS_DUAL, self.L1R_L2LOSS]:
767            import warnings
768            warnings.warn("""\
769Deprecated 'solver_type', use
770'Orange.classification.logreg.LibLinearLogRegLearner'
771to build a logistic regression model using LIBLINEAR.
772""",
773                DeprecationWarning)
774
775    def __call__(self, data, weight_id=None):
776        if not isinstance(data.domain.class_var, variable.Discrete):
777            raise TypeError("Can only learn a discrete class.")
778
779        if data.domain.has_discrete_attributes() or self.normalization:
780            dc = Orange.data.continuization.DomainContinuizer()
781            dc.multinomial_treatment = dc.NValues
782            dc.class_treatment = dc.Ignore
783            dc.continuous_treatment = \
784                    dc.NormalizeBySpan if self.normalization else dc.Leave
785            c_domain = dc(data)
786            data = data.translate(c_domain)
787
788        return super(LinearSVMLearner, self).__call__(data, weight_id)
789
790LinearLearner = LinearSVMLearner
791
792class MultiClassSVMLearner(Orange.core.LinearLearner):
793    """ Multi-class SVM (Crammer and Singer) from the `LIBLINEAR`_ library.
794    """
795    __new__ = _orange__new__(base=Orange.core.LinearLearner)
796
797    def __init__(self, C=1.0, eps=0.01, normalization=True, **kwargs):
798        """\
799        :param C: Regularization parameter (default 1.0)
800        :type C: float 
801       
802        :param eps: Stopping criteria (default 0.01)
803        :type eps: float
804       
805        :param normalization: Normalize the input data prior to learning
806            (default True)
807        :type normalization: bool
808       
809        """
810        self.C = C
811        self.eps = eps
812        self.normalization = normalization
813        for name, val in kwargs.items():
814            setattr(self, name, val)
815
816        self.solver_type = self.MCSVM_CS
817
818    def __call__(self, data, weight_id=None):
819        if not isinstance(data.domain.class_var, variable.Discrete):
820            raise TypeError("Can only learn a discrete class.")
821
822        if data.domain.has_discrete_attributes() or self.normalization:
823            dc = Orange.data.continuization.DomainContinuizer()
824            dc.multinomial_treatment = dc.NValues
825            dc.class_treatment = dc.Ignore
826            dc.continuous_treatment = \
827                    dc.NormalizeBySpan if self.normalization else dc.Leave
828            c_domain = dc(data)
829            data = data.translate(c_domain)
830
831        return super(MultiClassSVMLearner, self).__call__(data, weight_id)
832
833#TODO: Unified way to get attr weights for linear SVMs.
834
835def get_linear_svm_weights(classifier, sum=True):
836    """Extract attribute weights from the linear SVM classifier.
837   
838    For multi class classification, the result depends on the argument
839    :obj:`sum`. If ``True`` (default) the function computes the
840    squared sum of the weights over all binary one vs. one
841    classifiers. If :obj:`sum` is ``False`` it returns a list of
842    weights for each individual binary classifier (in the order of
843    [class1 vs class2, class1 vs class3 ... class2 vs class3 ...]).
844       
845    """
846
847    def update_weights(w, key, val, mul):
848        if key in w:
849            w[key] += mul * val
850        else:
851            w[key] = mul * val
852
853    def to_float(val):
854        return float(val) if not val.isSpecial() else 0.0
855
856    SVs = classifier.support_vectors
857    class_var = SVs.domain.class_var
858   
859    if classifier.svm_type in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]:
860        weights = []   
861        classes = classifier.class_var.values
862        for i in range(len(classes) - 1):
863            for j in range(i + 1, len(classes)):
864                # Get the coef and rho values from the binary sub-classifier
865                # Easier then using the full coef matrix (due to libsvm internal
866                # class  reordering)
867                bin_classifier = classifier.get_binary_classifier(i, j)
868                n_sv0 = bin_classifier.n_SV[0]
869                SVs = bin_classifier.support_vectors
870                w = {}
871               
872                for coef, sv_ind in bin_classifier.coef[0]:
873                    SV = SVs[sv_ind]
874                    attributes = SVs.domain.attributes + \
875                    SV.getmetas(False, Orange.feature.Descriptor).keys()
876                    for attr in attributes:
877                        if attr.varType == Orange.feature.Type.Continuous:
878                            update_weights(w, attr, to_float(SV[attr]), coef)
879                   
880                weights.append(w)
881        if sum:
882            scores = defaultdict(float)
883            for w in weights:
884                for attr, w_attr in w.items():
885                    scores[attr] += w_attr ** 2
886            for key in scores:
887                scores[key] = math.sqrt(scores[key])
888            weights = dict(scores)
889    else:
890#        raise TypeError("SVM classification model expected.")
891        weights = {}
892        for coef, sv_ind in classifier.coef[0]:
893            SV = SVs[sv_ind]
894            attributes = SVs.domain.attributes + \
895            SV.getmetas(False, Orange.feature.Descriptor).keys()
896            for attr in attributes:
897                if attr.varType == Orange.feature.Type.Continuous:
898                    update_weights(weights, attr, to_float(SV[attr]), coef)
899           
900    return weights
901   
902getLinearSVMWeights = get_linear_svm_weights
903
904def example_weighted_sum(example, weights):
905    sum = 0
906    for attr, w in weights.items():
907        sum += float(example[attr]) * w
908    return sum
909
910exampleWeightedSum = example_weighted_sum
911
912class ScoreSVMWeights(Orange.feature.scoring.Score):
913    """
914    Score a feature by the squared sum of weights using a linear SVM
915    classifier.
916       
917    Example:
918   
919        >>> score = Orange.classification.svm.ScoreSVMWeights()
920        >>> for feature in table.domain.features:
921        ...     print "%-35s: %.3f" % (feature.name, score(feature, table))
922        compactness                        : 0.019
923        circularity                        : 0.025
924        distance circularity               : 0.007
925        radius ratio                       : 0.010
926        pr.axis aspect ratio               : 0.076
927        max.length aspect ratio            : 0.010
928        scatter ratio                      : 0.046
929        elongatedness                      : 0.095
930        pr.axis rectangularity             : 0.006
931        max.length rectangularity          : 0.030
932        scaled variance along major axis   : 0.001
933        scaled variance along minor axis   : 0.001
934        scaled radius of gyration          : 0.002
935        skewness about major axis          : 0.004
936        skewness about minor axis          : 0.003
937        kurtosis about minor axis          : 0.001
938        kurtosis about major axis          : 0.060
939        hollows ratio                      : 0.029
940       
941             
942    """
943
944    def __new__(cls, attr=None, data=None, weight_id=None, **kwargs):
945        self = Orange.feature.scoring.Score.__new__(cls, **kwargs)
946        if data is not None and attr is not None:
947            self.__init__(**kwargs)
948            return self.__call__(attr, data, weight_id)
949        else:
950            return self
951
952    def __reduce__(self):
953        return ScoreSVMWeights, (), dict(self.__dict__)
954
955    def __init__(self, learner=None, **kwargs):
956        """
957        :param learner: Learner used for weight estimation
958            (default LinearSVMLearner(solver_type=L2Loss_SVM_Dual))
959        :type learner: Orange.core.LinearLearner
960       
961        """
962        if learner:
963            self.learner = learner
964        else:
965            self.learner = LinearSVMLearner(solver_type=
966                                    LinearSVMLearner.L2R_L2LOSS_DUAL)
967
968        self._cached_examples = None
969
970    def __call__(self, attr, data, weight_id=None):
971        if data is self._cached_examples:
972            weights = self._cached_weights
973        else:
974            classifier = self.learner(data, weight_id)
975            self._cached_examples = data
976            import numpy
977            weights = numpy.array(classifier.weights)
978            weights = numpy.sum(weights ** 2, axis=0)
979            weights = dict(zip(data.domain.attributes, weights))
980            self._cached_weights = weights
981        return weights.get(attr, 0.0)
982
983MeasureAttribute_SVMWeights = ScoreSVMWeights
984
985class RFE(object):
986
987    """Iterative feature elimination based on weights computed by
988    linear SVM.
989   
990    Example::
991   
992        import Orange
993        table = Orange.data.Table("vehicle.tab")
994        l = Orange.classification.svm.SVMLearner(
995            kernel_type=Orange.classification.svm.kernels.Linear,
996            normalization=False) # normalization=False will not change the domain
997        rfe = Orange.classification.svm.RFE(l)
998        data_subset_of_features = rfe(table, 5)
999       
1000    """
1001
1002    def __init__(self, learner=None):
1003        self.learner = learner or SVMLearner(kernel_type=
1004                            kernels.Linear, normalization=False)
1005
1006    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback", "stopAt": "stop_at" })
1007    def get_attr_scores(self, data, stop_at=0, progress_callback=None):
1008        """Return a dictionary mapping attributes to scores.
1009        A score is a step number at which the attribute
1010        was removed from the recursive evaluation.
1011       
1012        """
1013        iter = 1
1014        attrs = data.domain.attributes
1015        attrScores = {}
1016
1017        while len(attrs) > stop_at:
1018            weights = get_linear_svm_weights(self.learner(data), sum=False)
1019            if progress_callback:
1020                progress_callback(100. * iter / (len(attrs) - stop_at))
1021            score = dict.fromkeys(attrs, 0)
1022            for w in weights:
1023                for attr, wAttr in w.items():
1024                    score[attr] += wAttr ** 2
1025            score = score.items()
1026            score.sort(lambda a, b:cmp(a[1], b[1]))
1027            numToRemove = max(int(len(attrs) * 1.0 / (iter + 1)), 1)
1028            for attr, s in  score[:numToRemove]:
1029                attrScores[attr] = len(attrScores)
1030            attrs = [attr for attr, s in score[numToRemove:]]
1031            if attrs:
1032                data = data.select(attrs + [data.domain.classVar])
1033            iter += 1
1034        return attrScores
1035
1036    @Orange.utils.deprecated_keywords({"numSelected": "num_selected", "progressCallback": "progress_callback"})
1037    def __call__(self, data, num_selected=20, progress_callback=None):
1038        """Return a new dataset with only `num_selected` best scoring attributes
1039       
1040        :param data: Data
1041        :type data: Orange.data.Table
1042        :param num_selected: number of features to preserve
1043        :type num_selected: int
1044       
1045        """
1046        scores = self.get_attr_scores(data, progress_callback=progress_callback)
1047        scores = sorted(scores.items(), key=lambda item: item[1])
1048
1049        scores = dict(scores[-num_selected:])
1050        attrs = [attr for attr in data.domain.attributes if attr in scores]
1051        domain = Orange.data.Domain(attrs, data.domain.classVar)
1052        domain.addmetas(data.domain.getmetas())
1053        data = Orange.data.Table(domain, data)
1054        return data
1055
1056RFE = Orange.utils.deprecated_members({
1057    "getAttrScores": "get_attr_scores"},
1058    wrap_methods=["get_attr_scores", "__call__"])(RFE)
1059
1060def example_table_to_svm_format(table, file):
1061    warnings.warn("Deprecated. Use table_to_svm_format", DeprecationWarning)
1062    table_to_svm_format(table, file)
1063
1064exampleTableToSVMFormat = example_table_to_svm_format
1065
1066def table_to_svm_format(data, file):
1067    """Save :obj:`Orange.data.Table` to a format used by LibSVM.
1068   
1069    :param data: Data
1070    :type data: Orange.data.Table
1071    :param file: file pointer
1072    :type file: file
1073   
1074    """
1075
1076    attrs = data.domain.attributes + data.domain.getmetas().values()
1077    attrs = [attr for attr in attrs if attr.varType
1078             in [Orange.feature.Type.Continuous,
1079                 Orange.feature.Type.Discrete]]
1080    cv = data.domain.classVar
1081
1082    for ex in data:
1083        if cv.varType == Orange.feature.Type.Discrete:
1084            file.write(str(int(ex[cv])))
1085        else:
1086            file.write(str(float(ex[cv])))
1087
1088        for i, attr in enumerate(attrs):
1089            if not ex[attr].isSpecial():
1090                file.write(" " + str(i + 1) + ":" + str(float(ex[attr])))
1091        file.write("\n")
1092
1093tableToSVMFormat = table_to_svm_format
1094
1095
1096def _doctest_args():
1097    """For unittest framework to test the docstrings.
1098    """
1099    import Orange
1100    table = Orange.data.Table("vehicle.tab")
1101    extraglobs = locals()
1102    return {"extraglobs": extraglobs}
Note: See TracBrowser for help on using the repository browser.