Changeset 10640:dec28e0a76fa in orange


Ignore:
Timestamp:
03/26/12 15:17:57 (2 years ago)
Author:
Ales Erjavec <ales.erjavec@…>
Branch:
default
Parents:
10639:b80b09cd23e3 (diff), 10636:52d5b2c31190 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Orange/classification/svm/__init__.py

    r10634 r10640  
    275275        self.kernel_type = wrapped.kernel_type 
    276276        self.__wrapped = wrapped 
    277  
     277         
    278278        assert(type(wrapped) in [_SVMClassifier, _SVMClassifierSparse]) 
    279  
     279         
    280280        if self.svm_type in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]: 
    281281            # Reorder the support vectors 
     
    290290        else: 
    291291            self.support_vectors = wrapped.support_vectors 
    292  
     292     
    293293    @property 
    294294    def coef(self): 
    295         """Coefficients of the underlying binary 1vs1 classifiers. 
    296          
    297         This is a #Classes * (#Classses - 1) list of lists where 
    298         each sublist contains tuples of (alpha, support_vector_index) 
     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), ... ]]  
    299304            
    300305        """ 
    301         # We need to reorder the coef values 
    302         # see http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f804 
    303         # for more information on how the coefs are stored by libsvm 
    304         # internally. 
    305  
    306         import numpy as np 
    307         c_map = self._get_libsvm_bin_classifier_map() 
    308         label_map = self._get_libsvm_labels_map() 
    309         libsvm_coef = self.__wrapped.coef 
    310         coef = [] #[None] * len(c_map) 
    311         n_class = len(label_map) 
    312         n_SV = self.__wrapped.n_SV 
    313         coef_array = np.array(self.__wrapped.coef) 
    314         p = 0 
    315         libsvm_class_indices = np.cumsum([0] + list(n_SV), dtype=int) 
    316         class_indices = np.cumsum([0] + list(self.n_SV), dtype=int) 
    317         for i in range(n_class - 1): 
    318             for j in range(i + 1, n_class): 
    319                 ni = label_map[i] 
    320                 nj = label_map[j] 
    321                 bc_index, mult = c_map[p] 
    322  
    323                 if ni > nj: 
    324                     ni, nj = nj, ni 
    325  
    326                 # Original class indices 
    327                 c1_range = range(libsvm_class_indices[ni], 
    328                                  libsvm_class_indices[ni + 1]) 
    329                 c2_range = range(libsvm_class_indices[nj], 
    330                                  libsvm_class_indices[nj + 1]) 
    331  
    332                 coef1 = mult * coef_array[nj - 1, c1_range] 
    333                 coef2 = mult * coef_array[ni, c2_range] 
    334  
    335                 # Mapped class indices 
    336                 c1_range = range(class_indices[i], 
    337                                  class_indices[i + 1]) 
    338                 c2_range = range(class_indices[j], 
    339                                  class_indices[j + 1]) 
    340                 if mult == -1.0: 
    341                     c1_range, c2_range = c2_range, c1_range 
    342  
    343                 nonzero1 = np.abs(coef1) > 0.0 
    344                 nonzero2 = np.abs(coef2) > 0.0 
    345  
    346                 coef1 = coef1[nonzero1] 
    347                 coef2 = coef2[nonzero2] 
    348  
    349                 c1_range = [sv_i for sv_i, nz in zip(c1_range, nonzero1) if nz] 
    350                 c2_range = [sv_i for sv_i, nz in zip(c2_range, nonzero2) if nz] 
    351  
    352                 coef.append(list(zip(coef1, c1_range)) + list(zip(coef2, c2_range))) 
    353  
    354                 p += 1 
     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             
    355363        return coef 
    356  
     364     
    357365    @property 
    358366    def rho(self): 
    359         """Constant (bias) terms in each underlying binary 1vs1 classifier. 
    360         """ 
    361         c_map = self._get_libsvm_bin_classifier_map() 
     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        """ 
    362375        rho = self.__wrapped.rho 
    363         return [rho[i] * m for i, m in c_map] 
    364  
     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     
    365382    @property 
    366383    def n_SV(self): 
    367384        """Number of support vectors for each class. 
     385        For regression models this is `None`. 
     386         
    368387        """ 
    369388        if self.__wrapped.n_SV is not None: 
    370389            c_map = self._get_libsvm_labels_map() 
    371             n_SV = self.__wrapped.n_SV 
     390            n_SV= self.__wrapped.n_SV 
    372391            return [n_SV[i] for i in c_map] 
    373392        else: 
    374393            return None 
    375  
     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 
    376399    @property 
    377400    def prob_a(self): 
    378401        if self.__wrapped.prob_a is not None: 
    379             c_map = self._get_libsvm_bin_classifier_map() 
    380             prob_a = self.__wrapped.prob_a 
    381             # TODO: What about order switch? 
    382             return [prob_a[i] for i, _ in c_map] 
     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) 
    383409        else: 
    384410            return None 
    385  
     411     
    386412    @property 
    387413    def prob_b(self): 
     
    389415            c_map = self._get_libsvm_bin_classifier_map() 
    390416            prob_b = self.__wrapped.prob_b 
    391             # TODO: What about order switch? 
    392             return [prob_b[i] for i, _ in c_map] 
     417            # Change sign when changing the classifier direction 
     418            return [prob_b[i] * m for i, m in c_map] 
    393419        else: 
    394420            return None 
    395  
     421     
    396422    def __call__(self, instance, what=Orange.core.GetValue): 
    397423        """Classify a new ``instance`` 
     
    413439        instance = Orange.data.Instance(self.domain, instance) 
    414440        dec_values = self.__wrapped.get_decision_values(instance) 
    415         # decision values are ordered by libsvm internal class values 
    416         # i.e. the order of labels in the data 
    417         c_map = self._get_libsvm_bin_classifier_map() 
    418         return [dec_values[i] * m for i, m in c_map] 
    419  
     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         
    420449    def get_model(self): 
    421450        """Return a string representing the model in the libsvm model format. 
    422451        """ 
    423452        return self.__wrapped.get_model() 
    424  
     453     
    425454    def _get_libsvm_labels_map(self): 
    426455        """Get the internal libsvm label mapping.  
     
    433462 
    434463    def _get_libsvm_bin_classifier_map(self): 
    435         """Return the libsvm binary classifier mapping (due to label ordering) 
    436         """ 
     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") 
    437468        label_map = self._get_libsvm_labels_map() 
    438469        bin_c_map = [] 
     
    451482                bin_c_map.append((cls_index, mult)) 
    452483        return bin_c_map 
    453  
     484                 
    454485    def __reduce__(self): 
    455486        return SVMClassifier, (self.__wrapped,), dict(self.__dict__) 
    456  
     487     
    457488    def get_binary_classifier(self, c1, c2): 
    458489        """Return a binary classifier for classes `c1` and `c2`. 
     
    461492        if self.svm_type not in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]: 
    462493            raise TypeError("SVM classification model expected.") 
    463  
     494         
    464495        c1 = int(self.class_var(c1)) 
    465496        c2 = int(self.class_var(c2)) 
    466  
     497                 
    467498        n_class = len(self.class_var.values) 
    468  
     499         
    469500        if c1 == c2: 
    470501            raise ValueError("Different classes expected.") 
    471  
     502         
    472503        bin_class_var = Orange.feature.Discrete("%s vs %s" % \ 
    473504                        (self.class_var.values[c1], self.class_var.values[c2]), 
    474505                        values=["0", "1"]) 
    475  
     506         
    476507        mult = 1.0 
    477508        if c1 > c2: 
    478509            c1, c2 = c2, c1 
    479510            mult = -1.0 
    480  
     511             
    481512        classifier_i = n_class * (n_class - 1) / 2 - (n_class - c1 - 1) * (n_class - c1 - 2) / 2 - (n_class - c2) 
    482  
     513         
    483514        coef = self.coef[classifier_i] 
    484  
     515         
    485516        coef1 = [(mult * alpha, sv_i) for alpha, sv_i in coef \ 
    486517                 if int(self.support_vectors[sv_i].get_class()) == c1] 
    487518        coef2 = [(mult * alpha, sv_i) for alpha, sv_i in coef \ 
    488                  if int(self.support_vectors[sv_i].get_class()) == c2] 
    489  
     519                 if int(self.support_vectors[sv_i].get_class()) == c2]  
     520         
    490521        rho = mult * self.rho[classifier_i] 
    491  
    492         model = self._binary_libsvm_model_string(bin_class_var, 
     522         
     523        model = self._binary_libsvm_model_string(bin_class_var,  
    493524                                                 [coef1, coef2], 
    494525                                                 [rho]) 
    495  
     526         
    496527        all_sv = [self.support_vectors[sv_i] \ 
    497                   for c, sv_i in coef1 + coef2] 
    498  
     528                  for c, sv_i in coef1 + coef2]  
     529                   
    499530        all_sv = Orange.data.Table(all_sv) 
    500  
     531         
    501532        svm_classifier_type = type(self.__wrapped) 
    502  
     533         
    503534        # Build args for svm_classifier_type constructor 
    504535        args = (bin_class_var, self.examples, all_sv, model) 
    505  
     536         
    506537        if isinstance(svm_classifier_type, _SVMClassifierSparse): 
    507538            args = args + (int(self.__wrapped.use_non_meta),) 
    508  
     539         
    509540        if self.kernel_type == kernels.Custom: 
    510541            args = args + (self.kernel_func,) 
    511  
     542             
    512543        native_classifier = svm_classifier_type(*args) 
    513544        return SVMClassifier(native_classifier) 
    514  
     545     
    515546    def _binary_libsvm_model_string(self, class_var, coef, rho): 
    516547        """Return a libsvm formated model string for binary classifier 
    517548        """ 
    518549        import itertools 
    519  
     550         
     551        if not isinstance(self.class_var, variable.Discrete): 
     552            raise TypeError("SVM classification model expected") 
     553         
    520554        model = [] 
    521  
     555         
    522556        # Take the model up to nr_classes 
    523557        libsvm_model = self.__wrapped.get_model() 
     
    527561            else: 
    528562                model.append(line.rstrip()) 
    529  
     563         
    530564        model.append("nr_class %i" % len(class_var.values)) 
    531565        model.append("total_sv %i" % reduce(add, [len(c) for c in coef])) 
     
    533567        model.append("label " + " ".join(str(i) for i in range(len(class_var.values)))) 
    534568        # No probA and probB 
    535  
     569         
    536570        model.append("nr_sv " + " ".join(str(len(c)) for c in coef)) 
    537571        model.append("SV") 
    538  
     572         
    539573        def instance_to_svm(inst): 
    540574            values = [(i, float(inst[v])) \ 
     
    542576                      if not inst[v].is_special() and float(inst[v]) != 0.0] 
    543577            return " ".join("%i:%f" % (i + 1, v) for i, v in values) 
    544  
     578         
    545579        def sparse_instance_to_svm(inst): 
    546580            non_meta = [] 
     
    554588                    metas.append("%i:%f" % (base - m_id, float(value))) 
    555589            return " ".join(non_meta + metas) 
    556  
     590                 
    557591        if isinstance(self.__wrapped, _SVMClassifierSparse): 
    558592            converter = sparse_instance_to_svm 
    559593        else: 
    560594            converter = instance_to_svm 
    561  
     595         
    562596        if self.kernel_type == kernels.Custom: 
    563597            SV = libsvm_model.split("SV\n", 1)[1] 
    564598            # Get the sv indices (the last entry in the SV lines) 
    565599            indices = [int(s.split(":")[-1]) for s in SV.splitlines() if s.strip()] 
    566  
     600             
    567601            # Reorder the indices  
    568602            label_map = self._get_libsvm_labels_map() 
     
    574608            reordered_indices = [reordered_indices[i] for i in label_map] 
    575609            indices = reduce(add, reordered_indices) 
    576  
     610             
    577611            for (c, sv_i) in itertools.chain(*coef): 
    578612                model.append("%f 0:%i" % (c, indices[sv_i])) 
     
    580614            for (c, sv_i) in itertools.chain(*coef): 
    581615                model.append("%f %s" % (c, converter(self.support_vectors[sv_i]))) 
    582  
     616                 
    583617        model.append("") 
    584618        return "\n".join(model) 
    585  
     619         
    586620 
    587621SVMClassifier = Orange.utils.deprecated_members({ 
     
    590624    "getModel" : "get_model", 
    591625    }, wrap_methods=[])(SVMClassifier) 
    592  
     626     
    593627# Backwards compatibility (pickling) 
    594628SVMClassifierWrapper = SVMClassifier 
     
    659693            parameters.append(("gamma", [2 ** a for a in range(-5, 5, 2)] + [0])) 
    660694        import orngWrap 
    661         tunedLearner = orngWrap.TuneMParameters(learner=self.learner, 
     695        tunedLearner = orngWrap.TuneMParameters(object=self.learner, 
    662696                                                parameters=parameters, 
    663697                                                folds=self.folds) 
    664698 
    665         return tunedLearner(newexamples, verbose=self.verbose) 
     699        return tunedLearner(newexamples,verbose=self.verbose) 
    666700 
    667701class SVMLearnerSparseEasy(SVMLearnerEasy): 
     
    772806 
    773807    SVs = classifier.support_vectors 
    774     weights = [] 
    775  
    776808    class_var = SVs.domain.class_var 
    777     if classifier.svm_type not in [SVMLearner.C_SVC, SVMLearner.Nu_SVC]: 
    778         raise TypeError("SVM classification model expected.") 
    779  
    780     classes = classifier.class_var.values 
    781  
    782     for i in range(len(classes) - 1): 
    783         for j in range(i + 1, len(classes)): 
    784             # Get the coef and rho values from the binary sub-classifier 
    785             # Easier then using the full coef matrix (due to libsvm internal 
    786             # class  reordering) 
    787             bin_classifier = classifier.get_binary_classifier(i, j) 
    788             n_sv0 = bin_classifier.n_SV[0] 
    789             SVs = bin_classifier.support_vectors 
    790             w = {} 
    791  
    792             for alpha, sv_ind in bin_classifier.coef[0]: 
    793                 SV = SVs[sv_ind] 
    794                 attributes = SVs.domain.attributes + \ 
    795                 SV.getmetas(False, Orange.feature.Descriptor).keys() 
    796                 for attr in attributes: 
    797                     if attr.varType == Orange.feature.Type.Continuous: 
    798                         update_weights(w, attr, to_float(SV[attr]), alpha) 
    799  
    800             weights.append(w) 
    801  
    802     if sum: 
    803         scores = defaultdict(float) 
    804  
    805         for w in weights: 
    806             for attr, w_attr in w.items(): 
    807                 scores[attr] += w_attr ** 2 
    808         for key in scores: 
    809             scores[key] = math.sqrt(scores[key]) 
    810         return dict(scores) 
     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) 
    811840    else: 
    812         return weights 
    813  
     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     
    814853getLinearSVMWeights = get_linear_svm_weights 
    815854 
Note: See TracChangeset for help on using the changeset viewer.