Programming Collective Intelligence

总结书中提到的各种分类算法： 朴素贝叶斯（naïve Bayesian）： 优点：速度快，支持增量训练，易于理解 缺点：无法解决特征组合的情况

决策树（Decision Tree）： 优点：速度快，易于理解，接受数值型数据，可以回归，能够处理特征之间的相互影响 缺点：不支持增量训练 神经网络（Neural Network）： 优点：支持增量训练，接受数值型数据，能够处理特征之间的相互影响，能够处理复杂的非线性函数 缺点：不易理解，训练数据比例难以控制 支持向量机（Support-Vector Machines）： 优点：分类速度快，接受数值型数据 缺点：不易理解，参数需要不断尝试 K-最近邻（k-Nearest Neighbors）： 优点：能够利用复杂函数预测，易于理解，知道各个样本的重要程度，添加样本不需要重新训练 缺点：低效，需要缩放特征值

同样的思路，java写的，走到死走不出去，python一半的概率能走出去，只能怀疑是随机函数的关系了。 Genome.py

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()

Route.py

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

Map.py

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     

本章中提及knn算法中选取k个邻值很重要，k的多少可以使用优化方法来获取。 下面是我的思路： 其cost方法，使用300个酒中的每一个，经knn算法后得到的预测值与真实值得差异的总和作为返回值。 KNN算法中最核心的是各变量的权重 本章中提到的最重要的几个概念是： 1.交叉验证 将数据集分为训练集和测试集(往往5%)，可进行多次划分，并交叉验证，取平均。 2.变量权重 可以通过优化方法优化 3.结果的概率分布 考虑到很多未知因素，可以将最后得到的邻居，按低到高，分为k组，获取每个分段中点的权重和，分别除以总权重，可获得在各段的分布

根据人和人“趣味”的相似性将人聚类，然后给“趣味”相似的人们推荐电影·音乐等等。 Collaborative Filtering 目标：找到那些趣味和我相似的人们 Collecting Preference 取得人们对某样东西的喜好，将喜好的程度量化。 Finding Similar Users 目标：确定人和人之间“趣味”的相似性，并给这种相似性打分(similarity score)。 Euclidean distance 算人在preference space的欧几里德距离，距离小的相似度高。Preference space的每一维代表一种物品。 参考维基百科：相关。 皮尔森相关系数 两个变量的关系可以直观地用散点图表示，当其紧密地群聚于一条直线的周围时，变量间存在强相关。定义为两个变量协方差除以两个变量的标准差。 Recommending Items 生成推荐作品的过程中要解决好两个问题： 1. 那些和你趣味最相似的人们并未都看过都看过同一部电影，这样的一部电影可能是部好电影，也要被公平的打分。 2. 有部电影的分数被某个人打的很高，但是大家的意见和他相反。这种“例外”的影响要被削弱。