#coding=utf-8
# Random Forest Algorithm on Sonar Dataset
from random import seed
from random import randrange
from csv import reader
from math import sqrt
from math import log

# 加載數(shù)據(jù)
def load_csv(filename): #導(dǎo)入csv文件
  dataset = list()
  with open(filename, 'r') as file:
    csv_reader = reader(file)
    for row in csv_reader:
      if not row:
        continue
      dataset.append(row)
  return dataset

#除了判別列，其他列都轉(zhuǎn)換為float類(lèi)型 
def str_column_to_float(dataset, column): #將數(shù)據(jù)集的第column列轉(zhuǎn)換成float形式
  for row in dataset:
    row[column] = float(row[column].strip()) #strip()返回移除字符串頭尾指定的字符生成的新字符串。


# 將數(shù)據(jù)集隨機(jī)分成n份，方便交叉驗(yàn)證
def cross_validation_split(dataset, n_folds): #將數(shù)據(jù)集dataset分成n_flods份，每份包含len(dataset) / n_folds個(gè)值，每個(gè)值由dataset數(shù)據(jù)集的內(nèi)容隨機(jī)產(chǎn)生，每個(gè)值被使用一次
  dataset_split = list()
  dataset_copy = list(dataset) #復(fù)制一份dataset,防止dataset的內(nèi)容改變
  fold_size = len(dataset) / n_folds # 每份數(shù)據(jù)集的大小
  for i in range(n_folds):
    fold = list()  #每次循環(huán)fold清零，防止重復(fù)導(dǎo)入dataset_split
    while len(fold) < fold_size:  #這里不能用if，if只是在第一次判斷時(shí)起作用，while執(zhí)行循環(huán)，直到條件不成立
      index = randrange(len(dataset_copy))
      fold.append(dataset_copy.pop(index)) #將對(duì)應(yīng)索引index的內(nèi)容從dataset_copy中導(dǎo)出，并將該內(nèi)容從dataset_copy中刪除。pop() 函數(shù)用于移除列表中的一個(gè)元素（默認(rèn)最后一個(gè)元素），并且返回該元素的值。
    dataset_split.append(fold)
  return dataset_split  #由dataset分割出的n_folds個(gè)數(shù)據(jù)構(gòu)成的列表，為了用于交叉驗(yàn)證

#導(dǎo)入實(shí)際值和預(yù)測(cè)值，計(jì)算精確度
def accuracy_metric(actual, predicted): 
  correct = 0
  for i in range(len(actual)):
    if actual[i] == predicted[i]:
      correct += 1
  return correct / float(len(actual)) * 100.0



#根據(jù)特征和特征值分割數(shù)據(jù)集
def test_split(index, value, dataset):
  left, right = list(), list()
  for row in dataset:
    if row[index] < value:
      left.append(row)
    else:
      right.append(row)
  return left, right

# 計(jì)算基尼指數(shù)
def gini_index(groups, class_values):  #個(gè)人理解：計(jì)算代價(jià)，分類(lèi)越準(zhǔn)確，則gini越小
  gini = 0.0
  for class_value in class_values: #class_values =[0,1] 
    for group in groups:     #groups=(left,right)
      size = len(group)
      if size == 0:
        continue
      proportion = [row[-1] for row in group].count(class_value) / float(size)
      gini += (proportion * (1.0 - proportion)) #個(gè)人理解：計(jì)算代價(jià)，分類(lèi)越準(zhǔn)確，則gini越小
  return gini

#找出分割數(shù)據(jù)集的最優(yōu)特征，得到最優(yōu)的特征index，特征值row[index]，以及分割完的數(shù)據(jù)groups（left,right）
def get_split(dataset, n_features):
  class_values = list(set(row[-1] for row in dataset)) #class_values =[0,1]
  b_index, b_value, b_score, b_groups = 999, 999, 999, None
  features = list()
  #往features添加n_features個(gè)特征（n_feature等于特征數(shù)的根號(hào)），特征索引從dataset中隨機(jī)取
  while len(features) < n_features:  
    index = randrange(len(dataset[0])-1) 
    if index not in features:
      features.append(index)
  #在n_features個(gè)特征中選出最優(yōu)的特征索引，并沒(méi)有遍歷所有特征，從而保證了每課決策樹(shù)的差異性    
  for index in features:    
    for row in dataset:
  #groups=(left,right)；row[index]遍歷每一行index索引下的特征值作為分類(lèi)值value，找出最優(yōu)的分類(lèi)特征和特征值
      groups = test_split(index, row[index], dataset) 
      gini = gini_index(groups, class_values)
      if gini < b_score:
        b_index, b_value, b_score, b_groups = index, row[index], gini, groups #最后得到最優(yōu)的分類(lèi)特征b_index,分類(lèi)特征值b_value,分類(lèi)結(jié)果b_groups。b_value為分錯(cuò)的代價(jià)成本。
  #print b_score
  return {'index':b_index, 'value':b_value, 'groups':b_groups}

#輸出group中出現(xiàn)次數(shù)較多的標(biāo)簽
def to_terminal(group):
  outcomes = [row[-1] for row in group]      #max()函數(shù)中，當(dāng)key參數(shù)不為空時(shí)，就以key的函數(shù)對(duì)象為判斷的標(biāo)準(zhǔn);
  return max(set(outcomes), key=outcomes.count)  # 輸出group中出現(xiàn)次數(shù)較多的標(biāo)簽 

#創(chuàng)建子分割器，遞歸分類(lèi)，直到分類(lèi)結(jié)束
def split(node, max_depth, min_size, n_features, depth): #max_depth = 10，min_size = 1，n_features = int(sqrt(len(dataset[0])-1)) 
  left, right = node['groups']
  del(node['groups'])
  # check for a no split
  if not left or not right:
    node['left'] = node['right'] = to_terminal(left + right)
    return
  # check for max depth
  if depth >= max_depth:  #max_depth=10表示遞歸十次，若分類(lèi)還未結(jié)束，則選取數(shù)據(jù)中分類(lèi)標(biāo)簽較多的作為結(jié)果，使分類(lèi)提前結(jié)束，防止過(guò)擬合
    node['left'], node['right'] = to_terminal(left), to_terminal(right)
    return

  # process left child
  if len(left) <= min_size:
    node['left'] = to_terminal(left)
  else:
    node['left'] = get_split(left, n_features) #node['left']是一個(gè)字典，形式為{'index':b_index, 'value':b_value, 'groups':b_groups}，所以node是一個(gè)多層字典
    split(node['left'], max_depth, min_size, n_features, depth+1) #遞歸，depth+1計(jì)算遞歸層數(shù)

  # process right child
  if len(right) <= min_size:
    node['right'] = to_terminal(right)
  else:
    node['right'] = get_split(right, n_features)
    split(node['right'], max_depth, min_size, n_features, depth+1)

# 創(chuàng)建決策樹(shù)
def build_tree(train, max_depth, min_size, n_features):
  #找到最佳切分向量和最佳切分點(diǎn)進(jìn)行劃分為兩個(gè)子集
  root = get_split(train, n_features) 
  split(root, max_depth, min_size, n_features, 1)
  return root

#預(yù)測(cè)模型分類(lèi)結(jié)果
def predict(node, row):  
  if row[node['index']] < node['value']:  # index是分割的特征分量，value是特征分量的最優(yōu)切分點(diǎn)
    if isinstance(node['left'], dict):  #isinstance是Python中的一個(gè)內(nèi)建函數(shù)。是用來(lái)判斷一個(gè)對(duì)象是否是一個(gè)已知的類(lèi)型。
      return predict(node['left'], row)
    else:
      return node['left']
  else:
    if isinstance(node['right'], dict):
      return predict(node['right'], row)
    else:
      return node['right']

#使用多個(gè)決策樹(shù)trees對(duì)測(cè)試集test的第row行進(jìn)行預(yù)測(cè)，再使用簡(jiǎn)單投票法判斷出該行所屬分類(lèi)
def bagging_predict(trees, row):
  predictions = [predict(tree, row) for tree in trees] 
  return max(set(predictions), key=predictions.count)

#創(chuàng)建數(shù)據(jù)集的隨機(jī)子樣本
def subsample(dataset, ratio):  
  sample = list()
  n_sample = round(len(dataset) * ratio)  #round() 方法返回浮點(diǎn)數(shù)x的四舍五入值。
  while len(sample) < n_sample:
    index = randrange(len(dataset)) #有放回的隨機(jī)采樣，有一些樣本被重復(fù)采樣，從而在訓(xùn)練集中多次出現(xiàn)，有的則從未在訓(xùn)練集中出現(xiàn)，此則自助采樣法。從而保證每棵決策樹(shù)訓(xùn)練集的差異性
    sample.append(dataset[index])
  return sample

# 隨機(jī)森林算法
def random_forest(train, test, max_depth, min_size, sample_size, n_trees, n_features):
  trees = list()
  for i in range(n_trees):  #n_trees表示決策樹(shù)的數(shù)量
    sample = subsample(train, sample_size) #隨機(jī)采樣保證了每棵決策樹(shù)訓(xùn)練集的差異性
    tree = build_tree(sample, max_depth, min_size, n_features) #建立一個(gè)決策樹(shù)
    trees.append(tree)
  predictions = [bagging_predict(trees, row) for row in test]
  return(predictions)

#評(píng)估算法性能，返回模型得分 
def evaluate_algorithm(dataset, algorithm, n_folds, *args):  
  folds = cross_validation_split(dataset, n_folds)
  scores = list()
  #每次循環(huán)從folds從取出一個(gè)fold作為測(cè)試集，其余作為訓(xùn)練集，遍歷整個(gè)folds，實(shí)現(xiàn)交叉驗(yàn)證
  for fold in folds:  
    train_set = list(folds)
    train_set.remove(fold)
    train_set = sum(train_set, [])  #將多個(gè)fold列表組合成一個(gè)train_set列表
    test_set = list()
    for row in fold:  #fold表示從原始數(shù)據(jù)集dataset提取出來(lái)的測(cè)試集
      row_copy = list(row)
      test_set.append(row_copy)
      row_copy[-1] = None
    predicted = algorithm(train_set, test_set, *args) # 調(diào)用隨機(jī)森林算法，預(yù)測(cè)的分類(lèi)值列表
    actual = [row[-1] for row in fold]         # 真實(shí)的分類(lèi)值列表
    accuracy = accuracy_metric(actual, predicted)
    scores.append(accuracy)
  return scores

if __name__ == '__main__':  
  #每一次執(zhí)行本文件時(shí)都能產(chǎn)生同一個(gè)隨機(jī)數(shù)  
  seed(1)  
  filename = 'sonar-all-data.csv'
  dataset = load_csv(filename)  
  for i in range(0, len(dataset[0])-1): # 每一列的字符屬性轉(zhuǎn)為浮點(diǎn)數(shù)
    str_column_to_float(dataset, i)  
  n_folds = 5   #分成5份數(shù)據(jù)，進(jìn)行交叉驗(yàn)證  
  max_depth = 20 #調(diào)參（自己修改）決策樹(shù)深度不能太深，不然容易導(dǎo)致過(guò)擬合
  min_size = 1  #每個(gè)分支下最小的節(jié)點(diǎn)個(gè)數(shù)
  sample_size = 1.0 # 每棵數(shù)所用樣本子集的大小，這里和訓(xùn)練集相同  
  n_features =15 #調(diào)參（自己修改） #準(zhǔn)確性與多樣性之間的權(quán)衡
  for n_trees in [1,10,20]: #理論上樹(shù)的棵數(shù)是越多越好
    scores = evaluate_algorithm(dataset[0:50], random_forest, n_folds, max_depth, min_size, sample_size, n_trees, n_features)
    print('Trees: %d' % n_trees)
    print('Scores: %s' % scores)
    print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))