#coding=utf-8# Random Forest Algorithm on Sonar Datasetfrom random import seedfrom random import randrangefrom csv import readerfrom math import sqrtfrom math import log# 加載數據def load_csv(filename): #導入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#除了判別列，其他列都轉換為float類型 def str_column_to_float(dataset, column): #將數據集的第column列轉換成float形式  for row in dataset:    row[column] = float(row[column].strip()) #strip()返回移除字符串頭尾指定的字符生成的新字符串。# 將數據集隨機分成n份，方便交叉驗證def cross_validation_split(dataset, n_folds): #將數據集dataset分成n_flods份，每份包含len(dataset) / n_folds個值，每個值由dataset數據集的內容隨機產生，每個值被使用一次  dataset_split = list()  dataset_copy = list(dataset) #復制一份dataset,防止dataset的內容改變  fold_size = len(dataset) / n_folds # 每份數據集的大小  for i in range(n_folds):    fold = list()  #每次循環fold清零，防止重復導入dataset_split    while len(fold) < fold_size:  #這里不能用if，if只是在第一次判斷時起作用，while執行循環，直到條件不成立      index = randrange(len(dataset_copy))      fold.append(dataset_copy.pop(index)) #將對應索引index的內容從dataset_copy中導出，并將該內容從dataset_copy中刪除。pop() 函數用于移除列表中的一個元素（默認最后一個元素），并且返回該元素的值。    dataset_split.append(fold)  return dataset_split  #由dataset分割出的n_folds個數據構成的列表，為了用于交叉驗證#導入實際值和預測值，計算精確度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#根據特征和特征值分割數據集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# 計算基尼指數def gini_index(groups, class_values):  #個人理解：計算代價，分類越準確，則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)) #個人理解：計算代價，分類越準確，則gini越小  return gini#找出分割數據集的最優特征，得到最優的特征index，特征值row[index]，以及分割完的數據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個特征（n_feature等于特征數的根號），特征索引從dataset中隨機取  while len(features) < n_features:      index = randrange(len(dataset[0])-1)     if index not in features:      features.append(index)  #在n_features個特征中選出最優的特征索引，并沒有遍歷所有特征，從而保證了每課決策樹的差異性      for index in features:        for row in dataset:  #groups=(left,right)；row[index]遍歷每一行index索引下的特征值作為分類值value，找出最優的分類特征和特征值      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 #最后得到最優的分類特征b_index,分類特征值b_value,分類結果b_groups。b_value為分錯的代價成本。  #print b_score  return {'index':b_index, 'value':b_value, 'groups':b_groups}#輸出group中出現次數較多的標簽def to_terminal(group):  outcomes = [row[-1] for row in group]      #max()函數中，當key參數不為空時，就以key的函數對象為判斷的標準;  return max(set(outcomes), key=outcomes.count)  # 輸出group中出現次數較多的標簽 #創建子分割器，遞歸分類，直到分類結束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表示遞歸十次，若分類還未結束，則選取數據中分類標簽較多的作為結果，使分類提前結束，防止過擬合    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']是一個字典，形式為{'index':b_index, 'value':b_value, 'groups':b_groups}，所以node是一個多層字典    split(node['left'], max_depth, min_size, n_features, depth+1) #遞歸，depth+1計算遞歸層數  # 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)# 創建決策樹def build_tree(train, max_depth, min_size, n_features):  #找到最佳切分向量和最佳切分點進行劃分為兩個子集  root = get_split(train, n_features)   split(root, max_depth, min_size, n_features, 1)  return root#預測模型分類結果def predict(node, row):    if row[node['index']] < node['value']:  # index是分割的特征分量，value是特征分量的最優切分點    if isinstance(node['left'], dict):  #isinstance是Python中的一個內建函數。是用來判斷一個對象是否是一個已知的類型。      return predict(node['left'], row)    else:      return node['left']  else:    if isinstance(node['right'], dict):      return predict(node['right'], row)    else:      return node['right']#使用多個決策樹trees對測試集test的第row行進行預測，再使用簡單投票法判斷出該行所屬分類def bagging_predict(trees, row):  predictions = [predict(tree, row) for tree in trees]   return max(set(predictions), key=predictions.count)#創建數據集的隨機子樣本def subsample(dataset, ratio):    sample = list()  n_sample = round(len(dataset) * ratio)  #round() 方法返回浮點數x的四舍五入值。  while len(sample) < n_sample:    index = randrange(len(dataset)) #有放回的隨機采樣，有一些樣本被重復采樣，從而在訓練集中多次出現，有的則從未在訓練集中出現，此則自助采樣法。從而保證每棵決策樹訓練集的差異性    sample.append(dataset[index])  return sample# 隨機森林算法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表示決策樹的數量    sample = subsample(train, sample_size) #隨機采樣保證了每棵決策樹訓練集的差異性    tree = build_tree(sample, max_depth, min_size, n_features) #建立一個決策樹    trees.append(tree)  predictions = [bagging_predict(trees, row) for row in test]  return(predictions)#評估算法性能，返回模型得分 def evaluate_algorithm(dataset, algorithm, n_folds, *args):    folds = cross_validation_split(dataset, n_folds)  scores = list()  #每次循環從folds從取出一個fold作為測試集，其余作為訓練集，遍歷整個folds，實現交叉驗證  for fold in folds:      train_set = list(folds)    train_set.remove(fold)    train_set = sum(train_set, [])  #將多個fold列表組合成一個train_set列表    test_set = list()    for row in fold:  #fold表示從原始數據集dataset提取出來的測試集      row_copy = list(row)      test_set.append(row_copy)      row_copy[-1] = None    predicted = algorithm(train_set, test_set, *args) # 調用隨機森林算法，預測的分類值列表    actual = [row[-1] for row in fold]         # 真實的分類值列表    accuracy = accuracy_metric(actual, predicted)    scores.append(accuracy)  return scoresif __name__ == '__main__':    #每一次執行本文件時都能產生同一個隨機數    seed(1)    filename = 'sonar-all-data.csv'  dataset = load_csv(filename)    for i in range(0, len(dataset[0])-1): # 每一列的字符屬性轉為浮點數    str_column_to_float(dataset, i)    n_folds = 5   #分成5份數據，進行交叉驗證    max_depth = 20 #調參（自己修改）決策樹深度不能太深，不然容易導致過擬合  min_size = 1  #每個分支下最小的節點個數  sample_size = 1.0 # 每棵數所用樣本子集的大小，這里和訓練集相同    n_features =15 #調參（自己修改） #準確性與多樣性之間的權衡  for n_trees in [1,10,20]: #理論上樹的棵數是越多越好    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))))