Programming Collective Intelligence

The biggest downside to naïve Bayesian classifiers is their inability to deal with outcomes that change based on combinations of features. Imagine the following scenario in which you are trying to distinguish spam from nonspam email: let’s say your job is building web applications, so the word “online” frequently appears in your work-related email. Your best friend works at a pharmacy and likes sending you funny stories about things that happen to him at work. Also, like most people who haven’t closely guarded their email addresses, you occasionally receive spam containing the words “online pharmacy.” You can probably see the dilemma here already—the classifier is constantly being told that “online” and “pharmacy” exist in nonspam email messages, so their proba- bilities become higher for nonspam. When you tell the classifier that a certain email message with the words “online pharmacy” is spam, those words are adjusted slightly more toward spam, creating a constant battle. Since features are all given probabilities separately, the classifier can never learn about combinations. In document classification this is usually not a big deal, since an email message with the words “online pharmacy” probably contains other spam indicators, but in other problems, understanding feature combinations can be much more important.

import random
import Route
import Map
class Genome():
    def __init__(self,genome_length=70,pop_size=140,mutation_rate=0.001,crossover_rate=0.7,mapb=None):
        self.GENOME_LENGTH=genome_length
        self.POP_SIZE=pop_size
        self.MUTATION_RATE=mutation_rate
        self.CROSSOVER_RATE=crossover_rate
        self.mapb=mapb

        self._createFirstGeneration()

    def _createFirstGeneration(self):
        self.pops=[]
        for i in range(0,self.POP_SIZE):
            self.pops.append(self._createRt())

    def _createRt(self):
        rt=Route.Route()
        rtd=[]
        for i in range(0,self.GENOME_LENGTH):
            rtd.append(random.randint(0,1)==0)

        rt.setRt(rtd)
        return rt

    def _updateFitness(self):
        bsc=0
        self.tsc=0
        for i in range(0,len(self.pops)):
            sc=self.mapb.getsc(self.pops[i].getRt())
            self.tsc+=sc
            bsc=((sc>bsc) and sc or bsc)
            self.pops[i].setsc(sc)

        return bsc

    def _mutate(self,rt):
        rd=rt.getRt()
        for i in range(0,len(rd)):
            if random.random<self.MUTATION_RATE:
                rd[i]=rd[i]==False

    def _crossover(self,fa,mo,baby1,baby2):
        fd=fa.getRt()
        md=mo.getRt()

        if random.random()>self.CROSSOVER_RATE or fa.same(mo):
            baby1.setRt(fd)
            baby2.setRt(md)
        else:
            cp=random.randint(1,self.GENOME_LENGTH-2)
            bd1=[]
            bd2=[]
            for i in range(0,cp):
                bd1.append(fd[i])
                bd2.append(md[i])

            for i in range(cp,self.GENOME_LENGTH):
                bd1.append(md[i])
                bd2.append(fd[i])
            baby1.setRt(bd1)
            baby2.setRt(bd2)

    def _select(self):
        thresc=self.tsc*random.random()

        tmpsc=0
        sel=-1
        for i in range(0,self.POP_SIZE):
            tmpsc+=self.pops[i].sc
            if tmpsc>=thresc:
                return self.pops[i]

    def _epoch(self):
        newgen=[]
        for i in range(0,self.POP_SIZE/2):
            fa=self._select()
            mo=self._select()

            baby1=Route.Route()
            baby2=Route.Route()
            self._crossover(fa, mo, baby1, baby2)

            self._mutate(baby1)
            self._mutate(baby2)

            newgen.append(baby1)
            newgen.append(baby2)

        self.pops=newgen

    def start(self):
        gene=1
        bsc=self._updateFitness()
        if bsc==1:
            print 'succ at %s gene' %gene
            return
        else:
            print 'gene %s : %.4f' %(gene,bsc)

        while gene<50:
            self._epoch()
            gene+=1
            bsc=self._updateFitness()
            if bsc==1:
                print 'succ at %s gene' %gene
                return
            else:
                print 'gene %s : %.4f' %(gene,bsc)



mapdata=[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
 [5, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
 [1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
 [1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1],
 [1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 8],
 [1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]];

mapb=Map.mapb(mapdata)
genome=Genome(mapb=mapb)
genome.start()

class Route():
    def __init__(self):
        self.sc=0

    def setRt(self,route):
        self.rt=route
    def getRt(self):
        return self.rt
    def setsc(self,score):
        self.sc=score
    def same(self,ort):
        od=ort.getRt()
        for i in range(0,len(self.rt)):
            if self.rt[i]!=od[i]:
                return False

        return True

class mapb():
    def __init__(self,mapdata):
        self.md=mapdata
        self.len_x=len(mapdata[0])
        self.len_y=len(mapdata)

        self._getEntry()

    def _getEntry(self):
        for i in range(0,len(self.md)):
            l=self.md[i]
            for j in range(0,len(l)):
                if l[j]==5:
                    self.start_x=j
                    self.start_y=i
                elif l[j]==8:
                    self.end_x=j
                    self.end_y=i
    def getsc(self,rt):
        pos_x=self.start_x
        pos_y=self.start_y

        for i in range(0,len(rt)/2):
            mv=(rt[i] and 2 or 0)+(rt[i+1] and 1 or 0)
            if mv==0:
                if self._isvalid(pos_x, pos_y-1):
                    pos_y=pos_y-1
            elif mv==1:
                if self._isvalid(pos_x, pos_y+1):
                    pos_y=pos_y+1
            elif mv==2:
                if self._isvalid(pos_x+1, pos_y):
                    pos_x=pos_x+1
            elif mv==3:
                if self._isvalid(pos_x-1, pos_y):
                    pos_x=pos_x-1
        return 1.0/(1+abs(pos_x-self.end_x)+abs(pos_y-self.end_y))


    def _isvalid(self,x,y):
        if x<0|y<0|x>self.len_x-1|y>self.len_y-1:
            return False

        return True