随机森林

一、 集成学习：

选择训练多个分类模型，并将各自的预测结果组合起来，可以提高分类问题的预测准确性。分为两类：bagging算法和boosting算法

Bagging算法通过对样本的有放回抽样，产生多个训练子集，并在每一个子集上训练一个分类器，最终的分类结果由多个分类器的分类结果投票而得。Boosting算法通过顺序的给训练集中的数据重新加权创造不同的基学习器。核心思想是重复利用一个基学习器来对数据集进行修饰，在每次学习过程中，通过计算错误率来对坏的、好的数据进行重新加权，再次计算错误率，最后对每一个分类器的结果进行线性加权得到最终预测效果。

图1 bagging算法流程图

图2 boosting算法流程图

随机森林

随机森林是Bagging算法的一种，算法流程如下：

1. 通过有放回的对m个样本进行m次抽样，有些样本会重复出现，而有些样本会抽不到。

2. 对样本的n维特征进行随机选择出k维特征，k=log2（n），然后从这k维特征，根据基尼指数，选择最优属性对二叉树进行训练。

3. 重复训练所有的树，直到该节点的所有训练样本都属于同一类别。

二、 决策树

决策树是基于树结构来进行决策的方法或模型。决策树的关键是如何选择划分属性来对数据进行分类。一般而言，我们希望随着树的划分，决策树的节点所包含的样本尽可能的都属于同一类别，即节点的“纯度”越来越高。

2.1 信息增益

ID3决策树学习算法就是以信息增益来划分的。“信息熵”的值越小，则样本集D的纯度越高。

离散属性有V个可能的取值，若使用属性a对样本进行划分，则会有V个节点，对第v个节点所包含的样本数为，于是属性a对样本即的信息增益为：信息增益越大，意味着属性a划分D所得样本纯度“提升”越高。

2.2 增益率

信息增益会对节点个数较多的属性有偏好，增益率会对节点个数较少的属性有偏好，C4.5决策树算法就是采用增益率来对属性划分的。

2.3 基尼指数

CART决策树使用基尼指数来选择属性划分，数据集D的基尼值为：

属性a的基尼指数为：基尼指数代表了从数据集D中随机抽取两个样本，其类别标记不一致的概率，所以Gini越小，D的纯度越高，所以要选择的属性是使得基尼指数最小的属性来对数据进行划分。

三 、 连续值处理

连续属性的可取值数目无限，因此不可再用上述可取值来直接对接点划分，采用二分法对连续属性属性处理，C4.5决策树中采用的机制。

给定样本集D，属性a，嘉定属性a在D中有n个不同的取值，将这些取值从小到大排序，找到一个划分点t，

即把中间点作为划分点，然后根据离散值来计算，找到一个最优的划分点。与离散属性不同的是，若当前节点划分为连续属性，它还可作为其后代节点的划分属性。

三、 训练过程详解

数据是400*2的样本集，类别用-1和1来代表。

step1：利用boostrap采样法，对原始数据进行k=2的抽样

step2：利用Gini指数选择最优划分属性和切分点，将数据分为左右子树

step3：重复step2，直至叶子节点

step4：重复step1-step3，生成50棵CART树

step5：将50棵树的结果进行加和，若超过半数以上和原始数据的标签一致，则认为分类正确

# -*- coding: utf-8 -*-
"""
Created on Mon May 21 10:26:09 2018

@author: Administrator
"""
import numpy as np
from math import log
from tree import build_tree,predict
import random as rd
import pickle as pickle
import pdb
    
def random_forest_training(data_train,trees_num):
    '''
    input: data_training(list) 训练数据
           trees_num(int) 分类树的个数  50
    output: trees_result(list) 每一棵树的最好划分
            trees_feature(list) 每一棵树中队员是特征的选择
    '''
    
    trees_result = []
    trees_feature = []
    n = np.shape(data_train)[1]
    if n > 2:
        k = int(log(n - 1,2)) + 1
    else:
        k = 1
        
    #开始构建每一棵树
    for i in range(trees_num):
        #1.随机选择m个样本，k个特征
        data_samples, feature = choose_samples(data_train,k)
        #2.构建每一课分类树
        tree = build_tree(data_samples)
        #3. 保存训练好的分类树
        trees_result.append(tree)
        #4.保存好该分类数使用的特征
        trees_feature.append(feature)
    return trees_result,trees_feature

def choose_samples(data,k):
    '''
    input:data(list) 原始数据集
          k(int) 选择的特征个数
    output:data_samples(list) 被选择出来的样本
           feature(list) 被选择出来的特征的index
    '''
    m,n = np.shape(data)  #400*3,最后一列是标签
    #1. 选择出k个特征的index
    feature = []
    for j in range(k):
        feature.append(rd.randint(0,n - 2))
    #2. 选择出m个样本的index
    index = []
    for i in range(m):
        index.append(rd.randint(0,m - 1))
    #3. 从data中选择出m个样本的k特征，组成数据集data_samples
    data_samples = []
    for i in range(m):
        data_tmp = []
        for fea in feature:
            data_tmp.append(data[index[i]][fea])
        data_tmp.append(data[index[i]][-1])
        data_samples.append(data_tmp)
    return data_samples,feature
        
def load_data(file_name):
    data_train = []
    f = open(file_name)
    for line in f.readlines():
        lines = line.strip().split("\t")
        data_tmp = []
        for x in lines:
            data_tmp.append(float(x))
        data_train.append(data_tmp)
    f.close()
    return data_train

def get_predict(trees_result,trees_feature,data_train):
    '''
    input:
        tree_result(list) 训练好的RF模型
        tree_Feature(list) 每一课分类树特征的选择
        data_train(list) 
    output:
        final_predict(list) 对样本预测的结果
    '''
    m_tree = len(trees_result)
    m = np.shape(data_train)[0]
    
    result = []
    for i in range(m_tree):
        clf = trees_result[i]
#        print(clf.results)
        feature = trees_feature[i]
        data = split_data(data_train,feature)
        result_i = []
        for i in range(m):
            result_i.append(list(predict(data[i][0:-1],clf).keys())[0])
        result.append(result_i)
#    pdb.set_trace()
    final_predict = np.sum(result,axis = 0)
    return final_predict
          
def split_data(data_train, feature):
    '''选择特征
    input:  data_train(list):训练数据集
            feature(list):要选择的特征
    output: data(list):选择出来的数据集
    '''
    m = np.shape(data_train)[0]
    data = []
    
    for i in range(m):
        data_x_tmp = []
        for x in feature:
            data_x_tmp.append(data_train[i][x])
        data_x_tmp.append(data_train[i][-1])
        data.append(data_x_tmp)
    return data      
        
def cal_correct_rate(data_train, final_predict):
    m = len(final_predict)
    corr = 0.0
    for i in range(m):
        if data_train[i][-1] * final_predict[i] > 0:
            corr += 1
    return corr / m        
        
        
def save_model(trees_result, trees_feature, result_file, feature_file):
    # 1、保存选择的特征
    m = len(trees_feature)
    f_fea = open(feature_file, "w")
    for i in range(m):
        fea_tmp = []
        for x in trees_feature[i]:
            fea_tmp.append(str(x))
        f_fea.writelines("\t".join(fea_tmp) + "\n")
    f_fea.close()
    
    # 2、保存最终的随机森林模型
    with open(result_file, 'wb') as f:
        pickle.dump(trees_result, f)       
        
        
        
if __name__ == "__main__":
    #1.导入数据
    print("---1.load data---")
    data_train = load_data("..\data.txt")
    
    #2. 训练RF模型
    print("---2.RF_training---")
    
    trees,trees_feature = random_forest_training(data_train,50)
    
    #3. 得到训练的准确性
    pdb.set_trace()
    print("---3. get prediction correct rate---")
    result = get_predict(trees,trees_feature,data_train)
    corr_rate = cal_correct_rate(data_train,result)
   
    print("---4. save model ---")
    save_model(trees,trees_feature,"result_file","feature_file")

# -*- coding: utf-8 -*-
"""
Created on Mon May 21 09:56:21 2018

@author: Administrator
"""
import pdb

class node:
    '''
    树的节点类
    '''
    def __init__(self,fea=-1,value=None,results=None,right=None,left=None):
        self.fea = fea  #用于切分数据集的属性索引
        self.value = value  #设置划分的值
        self.results = results  #存储类节点所属的类别
        self.right = right  #右子树
        self.left = left  #左子树
def cal_gini_index(data):
    '''
    input:
        data(list) 数据集
    output:
        gini(float) Gini指数
    '''
    total_sample = len(data)
    if len(data) == 0:
        return 0
    label_counts = label_uniq_cnt(data)  #统计数据集中不同标签的个数
    
    gini = 0
    for label in label_counts:
        gini = gini + pow(label_counts[label],2)
    
    gini = 1 - float(gini) / pow(total_sample,2)
    return gini

def label_uniq_cnt(data):
    '''
    input:data(list) 原始数据集
    output:label_uniq_cnt(int) 样本中标签个数
    '''
    label_uniq_cnt = {}
    for x in data:
        label = x[len(x) - 1] #获取每一类的类标签
        if label not in label_uniq_cnt:
            label_uniq_cnt[label] = 0
        label_uniq_cnt[label] = label_uniq_cnt[label] + 1
    return label_uniq_cnt

        
def build_tree(data):
    '''
    input:data(list) 训练样本  400*2
    output:node 树的节点
    '''
    if len(data) == 0:
        return node()
    
    #1.计算当前的Gini指数
    currentGini = cal_gini_index(data)
    
    bestGain = 0.0
    bestCriteria = None  #存储最佳切分属性以及最佳切分点
    bestSets = None  #存储切分后的两个数据集
    
    feature_num = len(data[0]) -1  #样本中特征的个数
    
    #2.找到最好的划分
    for fea in range(0,feature_num):
        #2.1 获取fea特征处所有可能取值
        feature_values = {}
        for sample in data:
            feature_values[sample[fea]] = 1  #获取样本的每一维属性的值
            
        #2.2 针对所有这一维属性，尝试将数据集划分，并计算Gini指数
        for value in feature_values.keys():
            #2.2.1 根据属性中的keys将数据集划分为左右子树
            (set_1,set_2) = split_tree(data,fea,value)
            #2.2.2 计算当前Gini指数
            nowGini = float(len(set_1) * cal_gini_index(set_1) + len(set_2) * cal_gini_index(set_2)) / len(data)
            #2.2.3 计算Gini指数的增加量
            gain = currentGini - nowGini
            #2.2.4 判断此划分是否比当前的划分更好
            if gain >bestGain and len(set_1) > 0 and len(set_2) > 0:
                bestGain = gain
                bestCriteria = (fea,value)
                bestSets = (set_1,set_2)
     
    #3. 判断是否结束
#    pdb.set_trace()
    if bestGain > 0 :
        right = build_tree(bestSets[0])
        left = build_tree(bestSets[1])
        return node(fea=bestCriteria[0],value=bestCriteria[1],right=right,left=left)
    else:
        return node(results=label_uniq_cnt(data))
    
def split_tree(data,fea,value):
    '''
    根据fea中的值value将数据集data划分成左右子树
    input:data(list) 数据集
          fea(int) 待分割属性的索引
          value(float) 待分割的属性的索引
    output:
        (set1,set2)(tuple)
    '''
    set_1 = []
    set_2 = []
    for x in data:
        if x[fea] >= value:
            set_1.append(x)
        else:
            set_2.append(x)
    return (set_1,set_2)
        
def predict(sample,tree):
    '''
    input:sample(list)  样本
          tres(类) 构建好的分类树
    output: tree.results 所属的类别
    '''
    #1. 只有树根
    if tree.results != None:
        return tree.results
    else:
        #2. 只有左右子树
        val_sample = sample[tree.fea]
        branch = None
        if val_sample  >= tree.value:
            branch = tree.right
        else:
            branch = tree.left
        return predict(sample,branch)