source: orange/orange/orngMultiClass.py @ 6538:a5f65d7f0b2c

Revision 6538:a5f65d7f0b2c, 8.7 KB checked in by Mitar <Mitar@…>, 4 years ago (diff)

Made XPM version of the icon 32x32.

Line 
1# ORANGE multiclass support
2#    by Alex Jakulin (jakulin@acm.org)
3#
4#       based on:
5#           Zadrozny, B.:
6#           Reducing multiclass to binary by coupling probability estimates
7#
8# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
9#
10# Version 1.7 (26/8/2002)
11#
12# - Added some intelligence to Zadrozny iterator. It now reduces tolerance
13# if the convergence is not happening.
14#
15# Version 1.6 (1/11/2001)
16#
17# Multiclass module enables the support for multiclass problems with simple
18# biclass margin classifiers.
19#
20#
21# To Do:
22#   - ECOC as MCM
23#
24
25import orange
26
27
28class MultiClassClassifier(orange.Classifier):
29    def __init__(self, cmatrix, template, domain):
30        self.cmatrix = cmatrix
31        self.template = template
32        self.domain = domain
33
34    def normalize(self, np):
35        sum = 0.0
36        for i in np:
37            sum += i
38        return [w/sum for w in np]
39
40    def getPD(self, example, ncv):
41        # initial approximate for probability distribution
42        r = 1.0/ncv
43        p = [r]*ncv
44        return p
45
46    def __call__(self, example, format = orange.GetValue):
47        ncv = len(self.domain.classVar.values)
48        p = self.getPD(example, ncv)
49       
50        # find the max probability
51        maxp = -1e200
52        for i in range(len(p)):
53            if p[i] > maxp:
54                maxp = p[i]
55                bestc = i
56        v = self.domain.classVar(bestc)
57       
58        # return
59        if format == orange.GetValue:
60            return v
61        if format == orange.GetBoth:
62            return (v,p)
63        if format == orange.GetProbabilities:
64            return p
65   
66
67class MCPEZadrozny(MultiClassClassifier):
68    def __init__(self, *args):
69        apply(MultiClassClassifier.__init__, (self,) + args )
70        self.iterations = 100
71        self.tolerance = 1e-4
72
73        # need the set definitions
74        self.I = [[] for i in self.template[0]]  # which templates cover a class with +1
75        self.J = [[] for i in self.template[0]]  # which templates cover a class with -1
76        self.iI = [[] for i in self.template]    # which templates are covered by a class with +1
77        self.iJ = [[] for i in self.template]    # which templates are covered by a class with -1
78        for i in range(len(self.template)):
79            for j in range(len(self.template[0])):
80                if self.template[i][j] == -1:
81                    self.J[j].append(i)
82                    self.iJ[i].append(j)
83                if self.template[i][j] == +1:
84                    self.I[j].append(i)
85                    self.iI[i].append(j)
86
87    def getRB(self, phat):
88        # computes the r on the basis of current probability estimate
89        rhat = []
90        for i in range(len(self.template)):
91            pt = 0.0 # top
92            for x in self.iI[i]:
93                pt += phat[x]
94            pb = 0.0 # bottom
95            for x in self.iJ[i]:
96                pb += phat[x]
97            if(pt == 0.0):
98                rhat.append(0.0)
99            else:
100                rhat.append(pt/(pb+pt))
101        return rhat
102             
103    def getPD(self, example, k):
104        # do all the experiments
105        r = []
106        n = []
107        for i in self.cmatrix:
108            r.append(i[0](example,orange.GetProbabilities)[1]) # probability the class is 1
109            n.append(i[1]+0.0)
110
111        # initial approximation
112        phat = MultiClassClassifier.getPD(self,example,k)
113
114        rt = []
115        for c in range(k):
116            tt = 1e-4  # prevent divide by 0
117            for b in self.I[c]:
118                tt += n[b]*r[b]
119            for b in self.J[c]:
120                tt += n[b]*(1.0-r[b])
121            rt.append(tt)
122
123        # do the iteration
124        iterations = self.iterations
125        tolerance = self.tolerance
126        while iterations > 0:
127            iterations -= 1
128            rhat = self.getRB(phat)
129
130            diff = 0.0 # testing for convergence
131
132            # for all classes, compute new approximation
133            for c in range(k):
134                tt = 0.0
135                for b in self.I[c]:
136                    tt += n[b]*rhat[b]
137                for b in self.J[c]:
138                    tt += n[b]*(1.0-rhat[b])
139                t = phat[c]*rt[c]/tt
140                diff += (t-phat[c])*(t-phat[c])
141                phat[c] = t
142
143            phat = self.normalize(phat)
144            if diff < tolerance:
145                break
146            if iterations == 0 and tolerance < 1.0:
147                tolerance *= 10.0
148                iterations = self.iterations
149        if iterations <= 0:
150            print "Zadrozny didn't converge. p=",phat
151        return phat
152
153#
154# Friedman's method simply counts the # of wins, and
155# weights the PD on the basis of this. Class frequencies
156# not considered.
157#
158class MCPEFriedman(MultiClassClassifier):
159    def getPD(self, example, ncv):
160        # do all the experiments
161        results = []
162        for i in self.cmatrix:
163            results.append(i[0](example))
164
165        # count the wins
166        wins = [0]*ncv
167        assert(len(self.template)==len(results))
168        assert(int(example.domain.classVar(1))==1)
169        for i in range(len(self.template)):
170            if int(results[i]) == 1:
171                # winners are the +1's
172                match = +1
173            else:
174                # winners are the -1's
175                match = -1
176            for j in range(ncv):
177                if self.template[i][j] == match:
178                    # the in class
179                    wins[j] += 1
180
181        # find the sum of winnings
182        return self.normalize(wins)
183
184
185#
186# MCM's are matrix generators for the multiclass problems.
187# Rows of the matrix indicate binary classifiers
188# Columns of the matrix indicate attributes.
189# Values mean: 0 - ignore this class, 1 - positive class, -1 - negative class
190#
191class MCMOneOne:
192    def __call__(self, nc):
193        m = []
194        for i in range(nc):
195            for j in range(nc):
196                if i < j:
197                    r = [0]*nc
198                    r[i] = 1
199                    r[j] = -1
200                    m.append(r)
201        return m
202   
203class MCMOneAll:
204    def __call__(self, nc):
205        m = []
206        for i in range(nc):
207            r = [-1]*nc
208            r[i] = 1
209            m.append(r)
210        return m
211
212class MCMOrdinal:   
213    def __call__(self, nc):
214        m = []
215        for i in range(1,nc):
216            r = [-1]*i+[1]*(nc-i)
217            m.append(r)
218        return m
219
220class MultiClassLearner(orange.Learner):
221    def __init__(self, learner, matrix = MCMOneOne, pestimator = MCPEFriedman, name='MultiClass'):
222        self.learner = learner
223        self.pestimator = pestimator
224        self.matrix = matrix()
225        self.name = name
226
227    def __call__(self, examples, weight = 0):
228        if examples.domain.classVar.varType != 1:
229            raise "MultiClassLearner only works with discrete class"
230       
231        # simple handling for simple 2-class problems
232        if len(examples.domain.classVar.values) <= 2:
233            if weight != 0:
234                return self.learner(examples, weight)
235            else:
236                return self.learner(examples)
237
238        # count the classes and generate the classifier matrix
239        nc = len(examples.domain.classVar.values)
240        nv = len(examples.domain.attributes)
241        template = self.matrix(nc)
242
243        # prepare the domain, and the new binary class
244        bin = orange.EnumVariable(name="binary",values=['0','1'])
245        b0 = bin(0)
246        b1 = bin(1)
247        nd = orange.Domain(examples.domain.attributes+[bin])
248       
249        # generate all classifiers
250        cm = []
251        for i in template:
252            exs = orange.ExampleTable(nd)
253            if weight != 0:
254                exs.addMetaAttribute(1)
255            for j in examples:
256                if i[int(j.getclass())] == 1:
257                    r = [j[x] for x in range(nv)]
258                    r.append(b1)
259                    x = orange.Example(nd,r)
260                    if weight != 0:
261                        x.setmeta(j.getMetaAttribute(weight),1)
262                    exs.append(x)
263                else:
264                    if i[int(j.getclass())] == -1:
265                        r = [j[x] for x in range(nv)]
266                        r.append(b0)
267                        x = orange.Example(nd,r)
268                        if weight != 0:
269                            x.setmeta(j.getMetaAttribute(weight),1)
270                        exs.append(x)
271            # prepare the classifier
272            if len(exs) <= 0:
273                raise "MultiClass: More than one of the declared class values do not appear in the data. Filter them out."
274            if weight!=0:
275                c = self.learner(exs,weight = 1)
276            else:
277                c = self.learner(exs)
278            cm.append((c,len(exs)))
279        return self.pestimator(cm, template, examples.domain)
280
281
Note: See TracBrowser for help on using the repository browser.