source: orange/Orange/classification/svm/__init__.py @ 10639:b80b09cd23e3

Revision 10639:b80b09cd23e3, 39.5 KB checked in by Ales Erjavec <ales.erjavec@…>, 2 years ago (diff)

Fixed an error in get_linear_svm_weights.

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