Changeset 9462:bce104c365b6 in orange


Ignore:
Timestamp:
07/27/11 19:06:49 (3 years ago)
Author:
wencanluo <wencanluo@…>
Branch:
default
Convert:
9c0d2a56c8faa3a4ca9c0ec33993c171f2712782
Message:

Update ML-kNN method for multi-label

Location:
orange
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • orange/Orange/multilabel/lp.py

    r9461 r9462  
    9898         
    9999        #build the instances 
    100         newtable = Orange.data.Table(new_domain) 
     100        new_table = Orange.data.Table(new_domain) 
    101101        for e in instances: 
    102102            new_row = Orange.data.Instance( 
    103103              new_domain,  
    104104              [v.value for v in e if v.variable.attributes.has_key('label') <> 1] + 
    105               [label.get_label_bitstream(instances,e)]) 
     105                    [label.get_label_bitstream(instances,e)]) 
    106106             
    107             newtable.append(new_row) 
     107            new_table.append(new_row) 
    108108                      
    109             #store the classifier 
    110             classifier = self.base_learner(newtable) 
    111            
     109        #store the classifier 
     110        classifier = self.base_learner(new_table) 
     111         
    112112        #Learn from the given table of data instances. 
    113113        return LabelPowersetClassifier(instances = instances, label_indices = label_indices,classifier = classifier) 
  • orange/Orange/multilabel/mlknn.py

    r9461 r9462  
    6262class MLkNNLearner(_multibase.MultiLabelLearner): 
    6363    """ 
    64     Class that implements the LabelPowerset (LP) method.  
     64    Class implementing the ML-kNN (Multi-Label k Nearest Neighbours) algorithm. The class is based on the  
     65    pseudo-code made available by the authors. 
     66     
     67    The pseudo code of ML-kNN: 
     68     
     69        :math:`[\\vec y_t,\\vec r_t] = ML-kNN(T,K,t,s)` 
     70     
     71        :math:`\%Computing \\quad the \\quad prior \\quad probabilities \\quad P(H_b^l)` 
     72     
     73        :math:`(1) for \\quad l \\in y \\quad do` 
     74 
     75        :math:`(2) \\quad  P(H_1^l) = (s+ \\sum_{i=1}^m \\vec y_{x_i}(l))/(s * 2+m); P(H_0^l)=1-P(H_1^l)` 
     76 
     77        :math:`\%Computing \\quad the \\quad posterior \\quad probabilities P(E_j^l|H_b^l)` 
     78     
     79        :math:`(3) Identify \\quad N(x_i), i \\in {1,2,...,m}` 
     80         
     81        :math:`(4) for \\quad l \\in y \\quad do` 
     82         
     83        :math:`(5) \\quad for \\quad j \\in{0,1,...,K} \\quad do` 
     84         
     85        :math:`(6) \\quad \\quad c[j]=0; c'[j]=0` 
     86         
     87        :math:`(7) \\quad for \\quad i \\in{1,...,m} \\quad do` 
     88         
     89        :math:`(8) \\quad \\quad \\delta = \\vec C_{x_i}(l)=\\sum_{a \\in N(x_i)} \\vec y_a(l)` 
     90         
     91        :math:`(9) \\quad \\quad if (\\vec y_{x_i}(l)==1) \\quad then \\quad c[\\delta]=c[\\delta]+1` 
     92         
     93        :math:`(10)\\quad \\quad \\quad \\quad else \\quad c'[\\delta]=c'[\\delta]+1` 
     94         
     95        :math:`(11)\\quad for \\quad j \\in{0,1,...,K} \\quad do` 
     96         
     97        :math:`(12)\\quad \\quad P(E_j^l|H_1^l)=(s+c[j])/(s * (K+1)+ \\sum_{p=0}^k c[p])` 
     98         
     99        :math:`(13)\\quad \\quad P(E_j^l|H_0^l)=(s+c'[j])/(s *(K+1)+ \\sum_{p=0}^k c'[p])` 
     100         
     101        :math:`\%Computing \\quad \\vec y_t \\quad and \\quad \\vec r_t`  
     102         
     103        :math:`(14) Identify \\quad N(t)` 
     104         
     105        :math:`(15) for \\quad l \\in y \\quad do` 
     106         
     107        :math:`(16)\\quad \\vec C_t(l) = \\sum_{a \\in N(t)} \\vec y_a(L)` 
     108         
     109        :math:`(17)\\quad \\vec y_t(l) = argmax_{b \\in {0,1}}P(H_b^l)P(E_{\\vec C_t(l)}^l|H_b^l)` 
     110         
     111        :math:`(18)\\quad \\vec r_t(l)=P(H_1^l|E_{\\vec C_t(l)}^l)=P(H_1^l)P(E_{\\vec C_t(l)}|H_1^l)/P(E_{\\vec C_t(l)}^l)=P(H_1^l)P(E_{\\vec C_t(l)}|H_1^l)/(\\sum_{b \\in {0,1}}P(H_b^l)P(E_{\\vec C_t(l)}^l|H_b^l))` 
     112 
     113      
     114    .. attribute:: k 
     115     
     116        Number of neighbors. If set to 0 (which is also the default value),  
     117        the square root of the number of instances is used. 
     118     
     119    .. attribute:: smooth 
     120     
     121        Smoothing parameter controlling the strength of uniform prior (Default value is set to 1 which yields the Laplace smoothing). 
     122     
     123    .. attribute:: knn 
     124         
     125        :class:`Orange.classification.knn.kNNLearner` for nearest neighbor search 
     126     
    65127    """ 
    66     def __new__(cls, instances = None, **argkw): 
     128    def __new__(cls, instances = None, k=1, smooth = 1.0, **argkw): 
     129        """ 
     130        Constructor of MLkNNLearner 
     131         
     132        :param instances: a table of instances, covered by the rule. 
     133        :type instances: :class:`Orange.data.Table` 
     134         
     135        :param k: number of nearest neighbors used in classification 
     136        :type k: int 
     137         
     138        :param smooth: Smoothing parameter controlling the strength of uniform prior (Default value is set to 1 which yields the Laplace smoothing). 
     139        :type smooth: Float 
     140         
     141        :rtype: :class:`MLkNNLearner` 
     142        """ 
     143         
    67144        self = _multibase.MultiLabelLearner.__new__(cls, **argkw) 
    68                  
     145         
     146        self.k = k 
     147        self.smooth = smooth 
     148         
    69149        if instances: 
     150            self.instances = instances 
    70151            self.__init__(**argkw) 
    71152            return self.__call__(instances) 
    72153        else: 
    73154            return self 
    74                  
     155 
    75156    def __call__(self, instances, **kwds): 
    76157        for k in kwds.keys(): 
    77158            self.__dict__[k] = kwds[k] 
    78159 
    79         num_labels = label.get_num_labels(instances) 
    80         label_indices = label.get_label_indices(instances) 
    81          
    82         #Learn from the given table of data instances. 
     160        self.num_labels = label.get_num_labels(instances) 
     161        self.label_indices = label.get_label_indices(instances) 
     162         
     163        num_labels = self.num_labels 
     164        label_indices = self.label_indices 
     165        k = self.k 
     166        print k 
     167         
     168        #A table holding the prior probability for an instance to belong in each class 
     169        self.prior_probabilities  = [0.] * num_labels 
     170         
     171        #A table holding the prior probability for an instance not to belong in each class 
     172        self.prior_nprobabilities = [0.] * num_labels 
     173         
     174        #A table holding the probability for an instance to belong in each class given that i:0..k of its neighbors belong to that class 
     175        self.CondProbabilities   = [ [0.] * (k + 1) ] * num_labels 
     176         
     177        #A table holding the probability for an instance not to belong in each class given that i:0..k of its neighbors belong to that class 
     178        self.CondNProbabilities  = [ [0.] * (k + 1) ] * num_labels 
     179         
     180        #build a kNNLearner 
     181        #remove labels 
     182        indices_remove = [var for index, var in enumerate(label_indices)] 
     183        new_domain = label.remove_indices(instances,indices_remove)  
     184         
     185        new_class = Orange.data.variable.Discrete("label") 
     186        for e in instances: 
     187            class_value = label.get_label_bitstream(instances,e) 
     188            new_class.add_value(class_value) 
     189         
     190        new_domain = Orange.data.Domain(new_domain,new_class) 
     191         
     192        new_table = Orange.data.Table(new_domain) 
     193        for e in instances: 
     194            new_row = Orange.data.Instance( 
     195              new_domain,  
     196              [v.value for v in e if v.variable.attributes.has_key('label') <> 1] + 
     197                    [label.get_label_bitstream(instances,e)]) 
     198             
     199            new_table.append(new_row) 
     200        self.knn = Orange.classification.knn.kNNLearner(new_table,k) 
     201         
     202        for e in new_table: 
     203            set = self.knn.findNearest(e,k) 
     204           
     205        #Computing the prior probabilities P(H_b^l) 
     206        self.compute_prior() 
     207         
     208        #Computing the posterior probabilities P(E_j^l|H_b^l) 
     209        self.compute_cond() 
     210         
     211        #Computing y_t and r_t 
     212         
    83213        return MLkNNClassifier(instances = instances, label_indices = label_indices) 
    84214 
     215    def compute_prior(self): 
     216        """ Computing Prior and PriorN Probabilities for each class of the training set """ 
     217        num_instances = len(self.instances) 
     218        for i in range(self.num_labels): 
     219            temp_ci = 0 
     220            for j in range(num_instances): 
     221                value = self.instances[j][self.label_indices[i]].value 
     222                if value == '1': 
     223                    temp_ci = temp_ci+1 
     224            self.prior_probabilities[i] = (self.smooth + temp_ci) / (self.smooth * 2 + num_instances) 
     225            self.prior_nprobabilities[i] = 1 - self.prior_probabilities[i] 
     226             
     227    def compute_cond(self): 
     228        """ Computing Cond and CondN Probabilities for each class of the training set """ 
     229        num_labels = self.num_labels 
     230        label_indices = self.label_indices 
     231        k = self.k 
     232        num_instances = len(self.instances) 
     233         
     234        temp_ci  = [ [0] * (k + 1) ] * num_labels 
     235        temp_NCi = [ [0] * (k + 1) ] * num_labels 
     236 
     237""" 
     238        for i  in range(num_instances): 
     239            #Instances knn = new Instances(lnn.kNearestNeighbours(train.instance(i), k)); 
     240 
     241            # now compute values of temp_ci and temp_NCi for every class label 
     242            for (int j = 0; j < numLabels; j++) { 
     243 
     244                int aces = 0; // num of aces in Knn for j 
     245                for (int k = 0; k < k; k++) { 
     246                    double value = Double.parseDouble(train.attribute(labelIndices[j]).value( 
     247                            (int) knn.instance(k).value(labelIndices[j]))); 
     248                    if (Utils.eq(value, 1.0)) { 
     249                        aces++; 
     250                    } 
     251                } 
     252                // raise the counter of temp_ci[j][aces] and temp_NCi[j][aces] by 1 
     253                if (Utils.eq(Double.parseDouble(train.attribute(labelIndices[j]).value( 
     254                        (int) train.instance(i).value(labelIndices[j]))), 1.0)) { 
     255                    temp_ci[j][aces]++; 
     256                } else { 
     257                    temp_NCi[j][aces]++; 
     258                } 
     259            } 
     260        } 
     261 
     262        // compute CondProbabilities[i][..] for labels based on temp_ci[] 
     263        for (int i = 0; i < numLabels; i++) { 
     264            int temp1 = 0; 
     265            int temp2 = 0; 
     266            for (int j = 0; j < k + 1; j++) { 
     267                temp1 += temp_ci[i][j]; 
     268                temp2 += temp_NCi[i][j]; 
     269            } 
     270            for (int j = 0; j < k + 1; j++) { 
     271                CondProbabilities[i][j] = (smooth + temp_ci[i][j]) / (smooth * (k + 1) + temp1); 
     272                CondNProbabilities[i][j] = (smooth + temp_NCi[i][j]) / (smooth * (k + 1) + temp2); 
     273            } 
     274        } 
     275    } 
     276""" 
     277  
    85278class MLkNNClassifier(_multibase.MultiLabelClassifier):       
    86279    def __call__(self, example, result_type=Orange.classification.Classifier.GetValue): 
  • orange/doc/Orange/rst/code/mlc-classify.py

    r9461 r9462  
    2222    #prints [<orange.Value 'Religion'='1'>, <orange.Value 'SCience'='1'>] <0.000, 1.000, 1.000, 0.000> 
    2323 
    24 mlknn_cliassifer = Orange.multilabel.MLkNNLearner(data) 
     24mlknn_cliassifer = Orange.multilabel.MLkNNLearner(data,k=1) 
    2525for e in data: 
    2626    c,p = mlknn_cliassifer(e,Orange.classification.Classifier.GetBoth) 
Note: See TracChangeset for help on using the changeset viewer.