source: orange/Orange/classification/svm/__init__.py @ 10682:289189dd68d9

Revision 10682:289189dd68d9, 44.6 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Fixed the use of 'has_discrete_attributes', ScoreSVMWeights can now be used for regression problems.

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(False) 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(False) 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        weights = {}
891        for coef, sv_ind in classifier.coef[0]:
892            SV = SVs[sv_ind]
893            attributes = SVs.domain.attributes + \
894            SV.getmetas(False, Orange.feature.Descriptor).keys()
895            for attr in attributes:
896                if attr.varType == Orange.feature.Type.Continuous:
897                    update_weights(weights, attr, to_float(SV[attr]), coef)
898
899    return weights
900
901getLinearSVMWeights = get_linear_svm_weights
902
903def example_weighted_sum(example, weights):
904    sum = 0
905    for attr, w in weights.items():
906        sum += float(example[attr]) * w
907    return sum
908
909exampleWeightedSum = example_weighted_sum
910
911class ScoreSVMWeights(Orange.feature.scoring.Score):
912    """
913    Score a feature using squares of weights of a linear SVM
914    model.
915       
916    Example:
917   
918        >>> score = Orange.classification.svm.ScoreSVMWeights()
919        >>> svm_scores = [(score(f, table), f) for f in table.domain.features]
920        >>> for feature_score, feature in sorted(svm_scores, reverse=True):
921        ...     print "%-35s: %.3f" % (feature.name, feature_score)
922        kurtosis about major axis          : 47.113
923        pr.axis aspect ratio               : 44.949
924        max.length rectangularity          : 39.748
925        radius ratio                       : 29.098
926        scatter ratio                      : 26.133
927        skewness about major axis          : 24.403
928        compactness                        : 20.432
929        hollows ratio                      : 20.109
930        max.length aspect ratio            : 15.757
931        scaled radius of gyration          : 15.242
932        scaled variance along minor axis   : 14.289
933        pr.axis rectangularity             : 9.882
934        circularity                        : 8.293
935        distance circularity               : 7.785
936        scaled variance along major axis   : 6.179
937        elongatedness                      : 4.038
938        skewness about minor axis          : 1.351
939        kurtosis about minor axis          : 0.760
940
941    """
942
943    handles_discrete = True
944    handles_continuous = True
945    computes_thresholds = False
946    needs = Orange.feature.scoring.Score.Generator
947
948    def __new__(cls, attr=None, data=None, weight_id=None, **kwargs):
949        self = Orange.feature.scoring.Score.__new__(cls, **kwargs)
950        if data is not None and attr is not None:
951            self.__init__(**kwargs)
952            return self.__call__(attr, data, weight_id)
953        else:
954            return self
955
956    def __reduce__(self):
957        return ScoreSVMWeights, (), dict(self.__dict__)
958
959    def __init__(self, learner=None, **kwargs):
960        """
961        :param learner: Learner used for weight estimation
962            (by default ``LinearSVMLearner(solver_type=L2R_L2LOSS_DUAL, C=1.0)``
963            will be used for classification problems and
964            ``SVMLearner(svm_type=Epsilon_SVR, kernel_type=Linear, C=1.0, p=0.25)``
965            for regression problems.
966           
967        :type learner: Orange.core.LinearLearner
968       
969        """
970        self.learner = learner
971        self._cached_examples = None
972
973    def __call__(self, attr, data, weight_id=None):
974        if attr not in data.domain.attributes:
975            raise ValueError("Feature %r is not from the domain." % attr)
976
977        if self.learner is not None:
978            learner = self.learner
979        elif isinstance(data.domain.class_var, variable.Discrete):
980            learner = LinearSVMLearner(solver_type=
981                                LinearSVMLearner.L2R_L2LOSS_DUAL,
982                                C=1.0)
983        elif isinstance(data.domain.class_var, variable.Continuous):
984            learner = SVMLearner(svm_type=SVMLearner.Epsilon_SVR,
985                                 kernel_type=kernels.Linear,
986                                 C=1.0, p=0.25)
987        else:
988            raise TypeError("Cannot handle the class variable type %r" % \
989                                type(data.domain.class_var))
990
991        if data is self._cached_examples:
992            weights = self._cached_weights
993        else:
994            classifier = learner(data, weight_id)
995            self._cached_examples = data
996            weights = self._extract_weights(classifier, data.domain.attributes)
997            self._cached_weights = weights
998        return weights.get(attr, 0.0)
999
1000    def _extract_weights(self, classifier, original_features):
1001        """Extract weights from a svm classifer (``SVMClassifier`` or a
1002        ``LinearLearner`` instance).
1003       
1004        """
1005        import numpy as np
1006        if isinstance(classifier, SVMClassifier):
1007            weights = get_linear_svm_weights(classifier, sum=True)
1008            if isinstance(classifier.class_var, variable.Continuous):
1009                # The weights are in the the original non squared form
1010                weights = dict((f, w ** 2) for f, w in weights.items()) 
1011        elif isinstance(classifier, Orange.core.LinearClassifier):
1012            weights = np.array(classifier.weights)
1013            weights = np.sum(weights ** 2, axis=0)
1014            weights = dict(zip(classifier.domain.attributes, weights))
1015        else:
1016            raise TypeError("Don't know how to use classifier type %r" % \
1017                                type(classifier))
1018
1019        # collect dummy variables that were created for discrete features
1020        sources = self._collect_source(weights.keys())
1021        source_weights = dict.fromkeys(original_features, 0.0)
1022        for f in original_features:
1023            if f not in weights and f in sources:
1024                dummys = sources[f]
1025                # Use averege weight 
1026                source_weights[f] = np.average([weights[d] for d in dummys])
1027            else:
1028                raise ValueError(f)
1029
1030        return source_weights
1031
1032    def _collect_source(self, vars):
1033        """ Given a list of variables ``var``, return a mapping from source
1034        variables (``source_variable`` or ``get_value_from.variable`` members)
1035        back to the variables in ``vars``.
1036       
1037        """
1038        source = defaultdict(list)
1039        for var in vars:
1040            svar = None
1041            if var.source_variable:
1042                source[var.source_variable].append(var)
1043            elif isinstance(var.get_value_from, Orange.core.ClassifierFromVar):
1044                source[var.get_value_from.variable].append(var)
1045            elif isinstance(var.get_value_from, Orange.core.ImputeClassifier):
1046                source[var.get_value_from.classifier_from_var.variable].append(var)
1047            else:
1048                source[var].append(var)
1049        return dict(source)
1050
1051MeasureAttribute_SVMWeights = ScoreSVMWeights
1052
1053class RFE(object):
1054
1055    """Iterative feature elimination based on weights computed by
1056    linear SVM.
1057   
1058    Example::
1059   
1060        import Orange
1061        table = Orange.data.Table("vehicle.tab")
1062        l = Orange.classification.svm.SVMLearner(
1063            kernel_type=Orange.classification.svm.kernels.Linear,
1064            normalization=False) # normalization=False will not change the domain
1065        rfe = Orange.classification.svm.RFE(l)
1066        data_subset_of_features = rfe(table, 5)
1067       
1068    """
1069
1070    def __init__(self, learner=None):
1071        self.learner = learner or SVMLearner(kernel_type=
1072                            kernels.Linear, normalization=False)
1073
1074    @Orange.utils.deprecated_keywords({"progressCallback": "progress_callback", "stopAt": "stop_at" })
1075    def get_attr_scores(self, data, stop_at=0, progress_callback=None):
1076        """Return a dictionary mapping attributes to scores.
1077        A score is a step number at which the attribute
1078        was removed from the recursive evaluation.
1079       
1080        """
1081        iter = 1
1082        attrs = data.domain.attributes
1083        attrScores = {}
1084
1085        while len(attrs) > stop_at:
1086            weights = get_linear_svm_weights(self.learner(data), sum=False)
1087            if progress_callback:
1088                progress_callback(100. * iter / (len(attrs) - stop_at))
1089            score = dict.fromkeys(attrs, 0)
1090            for w in weights:
1091                for attr, wAttr in w.items():
1092                    score[attr] += wAttr ** 2
1093            score = score.items()
1094            score.sort(lambda a, b:cmp(a[1], b[1]))
1095            numToRemove = max(int(len(attrs) * 1.0 / (iter + 1)), 1)
1096            for attr, s in  score[:numToRemove]:
1097                attrScores[attr] = len(attrScores)
1098            attrs = [attr for attr, s in score[numToRemove:]]
1099            if attrs:
1100                data = data.select(attrs + [data.domain.classVar])
1101            iter += 1
1102        return attrScores
1103
1104    @Orange.utils.deprecated_keywords({"numSelected": "num_selected", "progressCallback": "progress_callback"})
1105    def __call__(self, data, num_selected=20, progress_callback=None):
1106        """Return a new dataset with only `num_selected` best scoring attributes
1107       
1108        :param data: Data
1109        :type data: Orange.data.Table
1110        :param num_selected: number of features to preserve
1111        :type num_selected: int
1112       
1113        """
1114        scores = self.get_attr_scores(data, progress_callback=progress_callback)
1115        scores = sorted(scores.items(), key=lambda item: item[1])
1116
1117        scores = dict(scores[-num_selected:])
1118        attrs = [attr for attr in data.domain.attributes if attr in scores]
1119        domain = Orange.data.Domain(attrs, data.domain.classVar)
1120        domain.addmetas(data.domain.getmetas())
1121        data = Orange.data.Table(domain, data)
1122        return data
1123
1124RFE = Orange.utils.deprecated_members({
1125    "getAttrScores": "get_attr_scores"},
1126    wrap_methods=["get_attr_scores", "__call__"])(RFE)
1127
1128def example_table_to_svm_format(table, file):
1129    warnings.warn("Deprecated. Use table_to_svm_format", DeprecationWarning)
1130    table_to_svm_format(table, file)
1131
1132exampleTableToSVMFormat = example_table_to_svm_format
1133
1134def table_to_svm_format(data, file):
1135    """Save :obj:`Orange.data.Table` to a format used by LibSVM.
1136   
1137    :param data: Data
1138    :type data: Orange.data.Table
1139    :param file: file pointer
1140    :type file: file
1141   
1142    """
1143
1144    attrs = data.domain.attributes + data.domain.getmetas().values()
1145    attrs = [attr for attr in attrs if attr.varType
1146             in [Orange.feature.Type.Continuous,
1147                 Orange.feature.Type.Discrete]]
1148    cv = data.domain.classVar
1149
1150    for ex in data:
1151        if cv.varType == Orange.feature.Type.Discrete:
1152            file.write(str(int(ex[cv])))
1153        else:
1154            file.write(str(float(ex[cv])))
1155
1156        for i, attr in enumerate(attrs):
1157            if not ex[attr].isSpecial():
1158                file.write(" " + str(i + 1) + ":" + str(float(ex[attr])))
1159        file.write("\n")
1160
1161tableToSVMFormat = table_to_svm_format
1162
1163
1164def _doctest_args():
1165    """For unittest framework to test the docstrings.
1166    """
1167    import Orange
1168    table = Orange.data.Table("vehicle.tab")
1169    extraglobs = locals()
1170    return {"extraglobs": extraglobs}
Note: See TracBrowser for help on using the repository browser.