人工智能（1）爬山算法，遗传算法，决策树

在学校用的是Google的colab，体验非常棒。
但是回到国内，由于没有爬爬爬的能力，所以就没办法用colab继续啦。
不得不提colab是真的方便，线上的平台，并且提供免费的GPU,TPU加速。GPU在神经网络处理图像的时候速度明显有大的提升。CPU跑半天的，GPU不出一小时就可以搞定。
除了速度，编译环境也很友好。方便查错，会直接给Google的link。Tensorflow什么的也可以用啦。

回国之后嘛，就只可以用Jupyter Notebook查看.ipynb程序啦。
！！！之后的代码有一部分为教授上课给的样例，一部分为课后习题，总之就是不完全原创。
写这个博客只是为了我自己以后查找方便，等交完总结作业也会开成私密模式。
代码都是Python

Hill climbing

爬山算法
其想法就是随机取一点，比较它左边和右边，在两者之间选择更优的解。
这里得到的最终解法趋于一个局域最优解。在选解时加入一定概率选择差的那点有概率跳出当前局部最优解达到全局最优解。
大概就可以联想爬一座山和探索一组山脉。

下面使用N皇后问题的背景做一个爬山。
（N皇后当然有其他方法，比如进制回溯，这里仅仅是为了爬山算法而爬山算法）

import math
import random
import time

def generate_board(N=4):
    board = [i for i in range(N)]
    random.shuffle(board)
    return board


class NQueenState(object):
    def __init__(self, _board):
        self.board = _board
        self.heuristic_value = NQueenState.heuristic(self.board)

    @staticmethod
    def heuristic(board):
        # heuristic for N queen
        # no of pairs that attack each other either directly
        # or indirectly
        h = 0
        N = len(board)
        for i in range(N):
            for j in range(i+1, N):
                if board[i] == board[j]:
                    h+=1
                if ((board[i] == board[j] + (j-i))
                    or (board[i] == board[j] - (j-i))):
                    h+=1
        return h

    @staticmethod
    def successors(current_state):
        successors = []
        N = len(current_state.board)
        for i in range(N):
            for j in range(N):
                if current_state.board[i] != j:
                    L = current_state.board[:]
                    L[L.index(current_state.board[i])] = j
                    successors.append(NQueenState(L))
        return successors

    @staticmethod
    def best_successor(current):
        lowest_successor = None
        for successor in NQueenState.successors(current):
            if lowest_successor is None:
                lowest_successor = successor
            elif lowest_successor.heuristic_value > successor.heuristic_value:
                lowest_successor = successor
        return lowest_successor

    @staticmethod
    def random_successor(current):
        successors = NQueenState.successors(current)
        return random.choice(successors)

    @staticmethod
    def random_state(N):
        return NQueenState(generate_board(N))

def hill_climbing_search(problem):
    current = problem
    while True:
        successor = NQueenState.best_successor(current)
        if successor.heuristic_value <= current.heuristic_value:
            return successor
        current = successor


def hill_climbing_search_rr(problem):
    current = problem
    N = len(problem.board)
    while True:
        successor = NQueenState.best_successor(current)
        if successor.heuristic_value > current.heuristic_value:
            return current
        elif successor.heuristic_value == current.heuristic_value:
            successor = NQueenState.random_state(N)
        current = successor


# RANDOM RESTART HILL CLIMBING
def hill_climbing_search_rr2(problem):
    current = problem
    N = len(problem.board)
    while current.heuristic_value != 0:
        successor = NQueenState.best_successor(current)
        if successor.heuristic_value <= current.heuristic_value:
            successor = NQueenState.random_state(N)
        current = successor
    return current
    

主程序

N = 8 #int(raw_input('Enter value of N:\n> '), 10)
problem = NQueenState(generate_board(N))
print ("PROBLEM:", problem.board)
t1 = time.clock()
hc_rr = hill_climbing_search_rr(problem)
t2 = time.clock()
print ("HC RR: H = {}, TIME = {}s".format(hc_rr.heuristic_value, t2-t1))

这里使用爬山算法并不能保证以很短的时间找到满足要求的解。但是可以有助于理解爬山算法。
这里一个状态即一种步棋方式的好坏是由当前状态下存在攻击的皇后数来描述的。

（为了表示我没那么**，下面附上正常的回溯法解八皇后）

import numpy as np
a=np.zeros(9)
m=0
k=0
n=0
t=False
while a[0]==0:
    k+=1
    #go back to the former state
    if k>8:
        k=a[m]
        m-=1
    elif k<=8:
        t=True
        #To test if the Queen can be attacked
        i=1
        while i<=m:
            if(a[i]==k) or (i-a[i]==m+1-k) or (a[i]+i==k+m+1): 
                t=False
            else:
                pass
            i+=1
        if (t==True):
            m+=1
            a[m]=k
            k=0
        else:
            pass
        #print one solution
        if(m==8) and (t==True):
            i=1
            while i<=m:
                j=1
                while j<a[i]:
                    print('*',end='')
                    j+=1
                print('Q',end='')
                j=a[i]+1
                while j<=8:
                    print('*',end='')
                    j+=1
                print("\n")
                i+=1
            print("\n")
            n+=1
        else:
            pass
#print the number of solutions
print(n)

GA

遗传算法
类似于基因遗传，每次由父辈中优秀的基因产生下一代人。

以下用寻求路径，即基本的图论问题来解释这种算法。
理解的话也可以倒推来理解，最后的最短路肯定是由前面的最短路加后一段最短路构成的。所以从一开始每一段开始不断优化。

这里也一样，因为有随机函数的存在，并不能保证一定能找到最好的解。
在程序段中随机种子可以设为任意值，但是不要为0，而且一定要设一个，用来保证每次运行得到的结果是一样的。不然结果会很混乱。

这边用了热图来展现结果。

import pandas as pd
import numpy as np
import random
import copy
import matplotlib.pyplot as plt
import seaborn as sns

def print_pop(population):
    for i in population:
        print(i)

def initialize_map(p_zero, N):
    # first thing is to create the map that you're trying to navigate.  We will do this randomly.
    # This will be of the form of a adjacency matrix...
    # In other words, an NxN matrix where each row and column correspond to an intersection on a map
    # X_ij, then is equal to the amount of time that it takes to get from position i to position j
    # could also be considered a distance measure... but whatever is easier to think about.
    # practically, then we need a matrix that has numeric values in it... 
    # there should be some paths that don't exist.  I will assign these a 0.  
    # For instance, if you can't get directly from i to j, then X_ij = 0
    
    # The initialization needs some tuning parameters.  One is the proportion of 0's in the final result
    
    the_map = np.zeros((N,N))
    
    for i in range(0, N):
        for j in range(0, i):
            if random.random() > p_zero:
                the_map[i][j] = random.random()
                the_map[j][i] = the_map[i][j]
                
    return the_map

# We can make a more complicated map that has at least 10 stops that have to be made and see what happens.

def initialize_complex_map(p_zero, N, groups):

    the_map = np.zeros((N,N))
    
    for i in range(0, N):
        for j in range(0, i):
            group_i = int(i/(N/groups))
            group_j = int(j/(N/groups))
            
            if random.random() > p_zero and abs(group_i - group_j) <= 1:
                the_map[i][j] = random.random()
                the_map[j][i] = the_map[i][j]
          
        
    ax = sns.heatmap(the_map)

    plt.show()
        
    return the_map

def create_starting_population(size, the_map):
    
    # This just creates a population of different routes of a fixed size.  
    # Pretty straightforward.
    
    population = []
    
    for i in range(0,size):
        population.append(create_new_member(the_map))
        
    return population

def fitness(route, the_map):
    
    score = 0
    
    for i in range(1, len(route)):
        if (the_map[route[i-1]][route[i]] == 0) and i != len(the_map)-1:
            print("WARNING: INVALID ROUTE")
            print(route)
            print(the_map)
        score = score + the_map[route[i-1]][route[i]]

    return score

def crossover(a, b):
        
    # ERROR PROME AREA: You can make an error here by allowing routes to crossover at any point, which obviously won't work
    # you have to insure that when the two routes cross over that the resulting routes produce a valid route
    # which means that crossover points have to be at the same position value on the map
    
    common_elements = set(a) & set(b)
    
    if len(common_elements) == 2:
        return (a, b)
    else:
        common_elements.remove(0)
        common_elements.remove(max(a)) 
        value = random.sample(common_elements, 1)        
    
    cut_a = np.random.choice(np.where(np.isin(a, value))[0])
    cut_b = np.random.choice(np.where(np.isin(b, value))[0])
    
    new_a1 = copy.deepcopy(a[0:cut_a])
    new_a2 = copy.deepcopy(b[cut_b:])
    
    new_b1 = copy.deepcopy(b[0:cut_b])
    new_b2 = copy.deepcopy(a[cut_a:])
    
    new_a = np.append(new_a1, new_a2)
    new_b = np.append(new_b1, new_b2)
       
    return (new_a, new_b)

def mutate(route, probability, the_map):
    
    new_route = copy.deepcopy(route)
    
    for i in range(1, len(new_route)):
        if random.random() < probability:
            
            go = True

            while go:

                possible_values = np.nonzero(the_map[new_route[i-1]])
                proposed_value = random.randint(0,len(possible_values[0])-1)
                route = np.append(new_route, possible_values[0][proposed_value])

                if new_route[i] == len(the_map)-1:
                    go = False
                else:
                    i += 1
    
    return new_route

def create_new_member(the_map):
    # here we are going to create a new route
    # the new route can have any number of steps, so we'll select that randomly
    # the structure of the route will be a vector of integers where each value is the next step in the route
    # Everyone starts at 0, so the first value in the vector will indicate where to attempt to go next.
    # That is, if v_i = 4, then that would correspond to X_0,4 in the map that was created at initialization
    
    # N is the size of the map, so we need to make sure that 
    # we don't generate any values that exceed the size of the map

    N = len(the_map)
    
    route = np.zeros(1, dtype=int)

    go = True
    
    i = 1
    
    while go:
        
        possible_values = np.nonzero(the_map[route[i-1]])
        proposed_value = random.randint(0,len(possible_values[0])-1)
        route = np.append(route, possible_values[0][proposed_value])
                
        if route[i] == N-1:
            go = False
        else:
            i += 1
    
    return route

def score_population(population, the_map):
    
    scores = []
    
    for i in range(0, len(population)):
        scores += [fitness(population[i], the_map)]
        
    return scores

def pick_mate(scores):

    array = np.array(scores)
    temp = array.argsort()
    ranks = np.empty_like(temp)
    ranks[temp] = np.arange(len(array))

    fitness = [len(ranks) - x for x in ranks]
    
    cum_scores = copy.deepcopy(fitness)
    
    for i in range(1,len(cum_scores)):
        cum_scores[i] = fitness[i] + cum_scores[i-1]
        
    probs = [x / cum_scores[-1] for x in cum_scores]
    
    rand = random.random()
    
    for i in range(0, len(probs)):
        if rand < probs[i]:
            
            return i

def main():
    
    # parameters
    sparseness_of_map = 0.95
    size_of_map = 1000
    population_size = 30
    number_of_iterations = 1000
    number_of_couples = 9
    number_of_winners_to_keep = 2
    mutation_probability = 0.05
    number_of_groups = 1
    
    # initialize the map and save it
    the_map = initialize_complex_map(sparseness_of_map, size_of_map, number_of_groups)

    # create the starting population
    population = create_starting_population(population_size, the_map)

    last_distance = 1000000000
    # for a large number of iterations do:
        
    for i in range(0,number_of_iterations):
        new_population = []
        
        # evaluate the fitness of the current population
        scores = score_population(population, the_map)

        best = population[np.argmin(scores)]
        number_of_moves = len(best)
        distance = fitness(best, the_map)
        
        if distance != last_distance:
            print('Iteration %i: Best so far is %i steps for a distance of %f' % (i, number_of_moves, distance))
            plot_best(the_map, best, i)

        
        # allow members of the population to breed based on their relative score; 
            # i.e., if their score is higher they're more likely to breed
        for j in range(0, number_of_couples):  
            new_1, new_2 = crossover(population[pick_mate(scores)], population[pick_mate(scores)])
            new_population = new_population + [new_1, new_2]
  
        # mutate
        for j in range(0, len(new_population)):
            new_population[j] = np.copy(mutate(new_population[j], 0.05, the_map))
            
        # keep members of previous generation
        new_population += [population[np.argmin(scores)]]
        for j in range(1, number_of_winners_to_keep):
            keeper = pick_mate(scores)            
            new_population += [population[keeper]]
            
        # add new random members
        while len(new_population) < population_size:
            new_population += [create_new_member(the_map)]
            
        #replace the old population with a real copy
        population = copy.deepcopy(new_population)
                
        last_distance = distance
        
    # plot the results

def plot_best(the_map, route, iteration_number):
    ax = sns.heatmap(the_map)

    x=[0.5] + [x + 0.5 for x in route[0:len(route)-1]] + [len(the_map) - 0.5]
    y=[0.5] + [x + 0.5 for x in route[1:len(route)]] + [len(the_map) - 0.5]
    
    plt.plot(x, y, marker = 'o', linewidth=4, markersize=12, linestyle = "-", color='white')
    #plt.savefig('images/new1000plot_%i.png' %(iteration_number), dpi=300)
    plt.show()

main()

（还是一样的话，图论那些算法应付这种问题肯定更优，这里只是为了遗传而遗传）

决策树训练数据集

assignment1的内容，课上给的例子是经典的那个花的数据集，给三种花分类。课后作业就是给疾病分类预测一个病。

这边放截图吧。



这边需要说一下，有个one hot编码，还是十分有用的，可以把数据储存为一个稀疏的0,1矩阵。矩阵在AI里面还是十分重要的。当然种类过于多的时候，这样做可能会占用过多的空间。

在对数据做处理前，先要完善数据。对数据做预处理。这一点很重要。库里提供了一些现成的函数即填充方式。也可以自己重新编写。
常见操作有，把错误数据显示出来自己一条条手改，直接去掉错误数据那一整条记录，用平均数什么的填充。各有利弊，得结合场合选择。

分割数据集，一般都是9:1,8:2,7:3这样。将数据集分为训练集和测试集。

训练训练集（EMMMM相信大家都懂动词＋名词）

输出准确度。
我锻炼的不是很好啦，其实全部输出没病都比这个好，笑，主要是数据量很小啦。

这个问题上其实最好做一个矩阵（上一篇里有提到）

输出决策树
用以下函数可以输出各个因素的重要度：

importances=tree_clf.feature_importances_
print(importances)