#-*- coding: utf-8 -*-
import time
from csv import reader
from random import randint
from random import seed

import numpy as np
from numpy import mat

from group_11 import caculateAUC_1, plotTree

# 建立一棵CART樹
'''試探分枝'''
def data_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

'''計算基尼指數(shù)'''
def calc_gini(groups, class_values):
 gini = 0.0
 total_size = 0
 for group in groups:
  total_size += len(group)
 for group in groups:
  size = len(group)
  if size == 0:
   continue
  for class_value in class_values:
   proportion = [row[-1] for row in group].count(class_value) / float(size)
   gini += (size / float(total_size)) * (proportion * (1.0 - proportion))# 二分類執(zhí)行兩次，相當(dāng)于*2
 return gini

'''找最佳分叉點'''
def get_split(dataset, n_features):
 class_values = list(set(row[-1] for row in dataset))# 類別標(biāo)簽集合
 b_index, b_value, b_score, b_groups = 999, 999, 999, None

 # 隨機選取特征子集，包含n_features個特征
 features = list()
 while len(features) < n_features:
  # 隨機選取特征
  # 特征索引
  index = randint(0, len(dataset[0]) - 2) # 往features添加n_features個特征（n_feature等于特征數(shù)的根號），特征索引從dataset中隨機取
  if index not in features:
   features.append(index)
 for index in features:  # 對每一個特征
  # 計算Gini指數(shù)
  for row in dataset: # 按照每個記錄的該特征的取值劃分成兩個子集，計算對于的Gini（D，A），取最小的
   groups = data_split(index, row[index], dataset)
   gini = calc_gini(groups, class_values)
   if gini < b_score:
    b_index, b_value, b_score, b_groups = index, row[index], gini, groups
 return {'index': b_index, 'value': b_value, 'groups': b_groups} # 每個節(jié)點由字典組成

'''多數(shù)表決'''
def to_terminal(group):
 outcomes = [row[-1] for row in group]
 return max(set(outcomes), key=outcomes.count)

'''分枝'''
def split(node, max_depth, min_size, n_features, depth):
 left, right = node['groups'] # 自動分包/切片
 del (node['groups'])
 if not left or not right: # left或者right為空時
  node['left'] = node['right'] = to_terminal(left + right) # 葉節(jié)點不好理解
  return

 if depth >= max_depth:
  node['left'], node['right'] = to_terminal(left), to_terminal(right)
  return
 # 左子樹
 if len(left) <= min_size:
  node['left'] = to_terminal(left)
 else:
  node['left'] = get_split(left, n_features)
  split(node['left'], max_depth, min_size, n_features, depth + 1)
 # 右子樹
 if len(right) <= min_size: # min_size最小的的分枝樣本數(shù)
  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_one_tree(train, max_depth, min_size, n_features):
 # 尋找最佳分裂點作為根節(jié)點
 root = get_split(train, n_features)
 split(root, max_depth, min_size, n_features, 1)
 return root

'''用森林里的一棵樹來預(yù)測'''
def predict(node, row):
 if row[node['index']] < node['value']:
  if isinstance(node['left'], dict):
   return predict(node['left'], row)
  else:
   return node['left']
 else:
  if isinstance(node['right'], dict):
   return predict(node['right'], row)
  else:
   return node['right']


# 隨機森林類
class randomForest:
 def __init__(self,trees_num, max_depth, leaf_min_size, sample_ratio, feature_ratio):
  self.trees_num = trees_num    # 森林的樹的數(shù)目
  self.max_depth = max_depth    # 樹深
  self.leaf_min_size = leaf_min_size  # 建立樹時，停止的分枝樣本最小數(shù)目
  self.samples_split_ratio = sample_ratio # 采樣，創(chuàng)建子集的比例（行采樣）
  self.feature_ratio = feature_ratio  # 特征比例（列采樣）
  self.trees = list()      # 森林

 '''有放回的采樣，創(chuàng)建數(shù)據(jù)子集'''
 def sample_split(self, dataset):
  sample = list()
  n_sample = round(len(dataset) * self.samples_split_ratio) #每棵樹的采樣數(shù)
  while len(sample) < n_sample:
   index = randint(0, len(dataset) - 2) #隨機有放回的采樣
   sample.append(dataset[index])
  return sample

 ##############***Out-of-Bag***################################
 # 進行袋外估計等相關(guān)函數(shù)的實現(xiàn),需要注意并不是每個樣本都可能出現(xiàn)在隨機森林的袋外數(shù)據(jù)中
 # 因此進行oob估計時需要注意估計樣本的數(shù)量
 def OOB(self, oobdata, train, trees):
  '''輸入為：袋外數(shù)據(jù)dict,訓(xùn)練集,tree_list
  return oob準(zhǔn)確率'''

  n_rows = []
  count = 0
  n_trees = len(trees) # 森林中樹的棵樹

  for key, item in oobdata.items():
   n_rows.append(item)

  # print(len(n_rows)) # 所有trees中的oob數(shù)據(jù)的合集

  n_rows_list = sum(n_rows, [])

  unique_list = []
  for l1 in n_rows_list: # 從oob合集中計算獨立樣本數(shù)量
   if l1 not in unique_list:
    unique_list.append(l1)

  n = len(unique_list)
  # print(n)

  # 對訓(xùn)練集中的每個數(shù)據(jù)，進行遍歷，尋找其作為oob數(shù)據(jù)時的所有trees,并進行多數(shù)投票
  for row in train:
   pre = []
   for i in range(n_trees):
    if row not in oobdata[i]:
     # print('row: ',row)
     # print('trees[i]: ', trees[i])
     pre.append(predict(trees[i], row))
   if len(pre) > 0:
    label = max(set(pre), key=pre.count)
    if label == row[-1]:
     count += 1

  return (float(count) / n) * 100

 '''建立隨機森林'''
 def build_randomforest(self, train):
  temp_flag = 0
  max_depth = self.max_depth   # 樹深
  min_size = self.leaf_min_size  # 建立樹時，停止的分枝樣本最小數(shù)目
  n_trees = self.trees_num    # 森林的樹的數(shù)目
  n_features = int(self.feature_ratio * (len(train[0])-1)) #列采樣，從M個feature中，選擇m個(m<<M)
  # print('特征值為 : ',n_features)
  oobs = {} # ----------------------
  for i in range(n_trees):   # 建立n_trees棵決策樹
   sample = self.sample_split(train)  # 有放回的采樣，創(chuàng)建數(shù)據(jù)子集
   oobs[i] = sample # ----------------
   tree = build_one_tree(sample, max_depth, min_size, n_features) # 建立決策樹
   self.trees.append(tree)
   temp_flag += 1
   # print(i,tree)
  oob_score = self.OOB(oobs, train, self.trees) # oob準(zhǔn)確率---------
  print("oob_score is ", oob_score) # 打印oob準(zhǔn)確率---------
  return self.trees

 '''隨機森林預(yù)測的多數(shù)表決'''
 def bagging_predict(self, onetestdata):
  predictions = [predict(tree, onetestdata) for tree in self.trees]
  return max(set(predictions), key=predictions.count)

 '''計算建立的森林的精確度'''
 def accuracy_metric(self, testdata):
  correct = 0
  for i in range(len(testdata)):
   predicted = self.bagging_predict(testdata[i])
   if testdata[i][-1] == predicted:
    correct += 1
  return correct / float(len(testdata)) * 100.0


# 數(shù)據(jù)處理
'''導(dǎo)入數(shù)據(jù)'''
def load_csv(filename):
 dataset = list()
 with open(filename, 'r') as file:
  csv_reader = reader(file)
  for row in csv_reader:
   if not row:
    continue
   # dataset.append(row)
   dataset.append(row[:-1])
 # return dataset
 return dataset[1:], dataset[0]

'''劃分訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)'''
def split_train_test(dataset, ratio=0.3):
 #ratio = 0.2 # 取百分之二十的數(shù)據(jù)當(dāng)做測試數(shù)據(jù)
 num = len(dataset)
 train_num = int((1-ratio) * num)
 dataset_copy = list(dataset)
 traindata = list()
 while len(traindata) < train_num:
  index = randint(0,len(dataset_copy)-1)
  traindata.append(dataset_copy.pop(index))
 testdata = dataset_copy
 return traindata, testdata

'''分析樹，將向量內(nèi)積寫入list'''
def analyListTree(node, tag, result):
 # 葉子節(jié)點的父節(jié)點
 if (isinstance(node['left'], dict)):
  # 計算node與node[tag]的內(nèi)積
  tag="left"
  re = Inner_product(node, tag)
  result.append(re)
  analyListTree(node['left'], 'left', result)
  return
 elif (isinstance(node['right'], dict)):
  # 計算node與node[tag]的內(nèi)積
  tag = "right"
  re = Inner_product(node, tag)
  result.append(re)
  analyListTree(node['right'], 'right', result)
  return
 else:
  return

'''求向量內(nèi)積'''
# 計算node與node[tag]的內(nèi)積
def Inner_product(node ,tag):
 a = mat([[float(node['index'])], [float(node['value'])]])
 b = mat([[float(node[tag]['index'])], [float(node[tag]['value'])]])
 return (a.T * b)[0,0]

'''相似度優(yōu)化'''
''' same_value = 20  # 向量內(nèi)積的差（小于此值認為相似）
 same_rate = 0.63  # 樹的相似度（大于此值認為相似）
 返回新的森林（已去掉相似度高的樹）'''
def similarity_optimization(newforest, samevalue, samerate):
 res = list()    # 存儲森林的內(nèi)積
 result = list()    # 存儲某棵樹的內(nèi)積
 i = 1
 for tree in newforest:
  # 分析樹，將向量內(nèi)積寫入list
  # result 存儲tree的內(nèi)積
  analyListTree(tree, None, result)
  res.append(result)
  # print('第',i,'棵樹：',len(result),result)
  result = []
 # print('res = ',len(res),res)
 # 取一棵樹的單個向量內(nèi)積與其他樹的單個向量內(nèi)積做完全對比（相似度）
 # 遍歷列表的列
 for i in range(0, len(res) - 1):
  # 保證此列未被置空、
  if not newforest[i] == None:
   # 遍歷做對比的樹的列
   for k in range(i + 1, len(res)):
    if not newforest[k] == None:
     # time用于統(tǒng)計相似的次數(shù)，在每次更換對比樹時重置為0
     time = 0
     # 遍歷列表的當(dāng)前行
     for j in range(0, len(res[i])):
      # 當(dāng)前兩顆樹對比次數(shù)
      all_contrast = (res[ i].__len__() * res[k].__len__())
      # 遍歷做對比的樹的行
      for l in range(0, len(res[k])):
       # 如果向量的內(nèi)積相等，計數(shù)器加一
       if res[i][j] - res[k][l] < samevalue:
        time = time + 1
      # 如果相似度大于設(shè)定值
     real_same_rate = time / all_contrast
     if (real_same_rate > samerate):
      # 將對比樹置空
      newforest[k] = None
 result_forest = list()
 for i in range(0, newforest.__len__()):
  if not newforest[i] == None:
   result_forest.append(newforest[i])
 return result_forest


'''auc優(yōu)化method'''
def auc_optimization(auclist,trees_num,trees):
 # 為auc排序，獲取從大到小的與trees相對應(yīng)的索引列表
 b = sorted(enumerate(auclist), key=lambda x: x[1], reverse=True)
 index_list = [x[0] for x in b]
 auc_num = int(trees_num * 2 / 3)
 # 取auc高的前auc_num個
 print('auc: ', auc_num, index_list)
 newTempForest = list()
 for i in range(auc_num):
  # myRF.trees.append(tempForest[i])
  # newTempForest.append(myRF.trees[index_list[i]])
  newTempForest.append(trees[index_list[i]])
 return newTempForest

'''得到森林中決策樹的最佳深度'''
def getBestDepth(min_size,sample_ratio,trees_num,feature_ratio,traindata,testdata):
 max_depth = np.linspace(1, 15, 15, endpoint=True)
 # max_depth=[5,6,7,8,9,10,11,12,13,14,15]
 scores_final = []
 i=0
 for depth in max_depth:
  # 初始化隨機森林
  # print('=========>',i,'<=============')
  myRF_ = randomForest(trees_num, depth, min_size, sample_ratio, feature_ratio)
  # 生成隨機森林
  myRF_.build_randomforest(traindata)
  # 測試評估
  acc = myRF_.accuracy_metric(testdata[:-1])
  # print('模型準(zhǔn)確率：', acc, '%')
  # scores_final.append(acc.mean())
  scores_final.append(acc*0.01)
  i=i+1
 # print('scores_final: ',scores_final)
 # 找到深度小且準(zhǔn)確率高的值
 best_depth = 0
 temp_score = 0
 for i in range(len(scores_final)):
  if scores_final[i] > temp_score:
   temp_score = scores_final[i]
   best_depth = max_depth[i]
 # print('best_depth:',np.mean(scores_final),best_depth)
 # plt.plot(max_depth, scores_final, 'r-', lw=2)
 # # plt.plot(max_depth, list(range(0,max(scores_final))), 'r-', lw=2)
 # plt.xlabel('max_depth')
 # plt.ylabel('CV scores')
 # plt.ylim(bottom=0.0,top=1.0)
 # plt.grid()
 # plt.show()
 return best_depth


'''對比不同樹個數(shù)時的模型正確率'''
def getMyRFAcclist(treenum_list):
 seed(1) # 每一次執(zhí)行本文件時都能產(chǎn)生同一個隨機數(shù)
 filename = 'DataSet3.csv'   #SMOTE處理過的數(shù)據(jù)
 min_size = 1
 sample_ratio = 1
 feature_ratio = 0.3 # 盡可能小，但是要保證 int(self.feature_ratio * (len(train[0])-1)) 大于1
 same_value = 20 # 向量內(nèi)積的差（小于此值認為相似）
 same_rate = 0.63 # 樹的相似度（大于此值認為相似）

 # 加載數(shù)據(jù)
 dataset, features = load_csv(filename)
 traindata, testdata = split_train_test(dataset, feature_ratio)
 # 森林中不同樹個數(shù)的對比
 # treenum_list = [20, 30, 40, 50, 60]
 acc_num_list = list()
 acc_list=list()
 for trees_num in treenum_list:
  # 優(yōu)化1-獲取最優(yōu)深度
  max_depth = getBestDepth(min_size, sample_ratio, trees_num, feature_ratio, traindata, testdata)
  print('max_depth is ', max_depth)

  # 初始化隨機森林
  myRF = randomForest(trees_num, max_depth, min_size, sample_ratio, feature_ratio)
  # 生成隨機森林
  myRF.build_randomforest(traindata)

  print('Tree_number: ', myRF.trees.__len__())
  # 計算森林中每棵樹的AUC
  auc_list = caculateAUC_1.caculateRFAUC(testdata, myRF.trees)
  # 選取AUC高的決策數(shù)形成新的森林(auc優(yōu)化)
  newTempForest = auc_optimization(auc_list,trees_num,myRF.trees)
  # 相似度優(yōu)化
  myRF.trees = similarity_optimization(newTempForest, same_value, same_rate)
  # 測試評估
  acc = myRF.accuracy_metric(testdata[:-1])
  print('myRF1_模型準(zhǔn)確率：', acc, '%')
  acc_num_list.append([myRF.trees.__len__(), acc])
  acc_list.append(acc)
 print('trees_num from 20 to 60: ', acc_num_list)
 return acc_list


if __name__ == '__main__':
 start = time.clock()
 seed(1) # 每一次執(zhí)行本文件時都能產(chǎn)生同一個隨機數(shù)
 filename = 'DataSet3.csv'  # 這里是已經(jīng)利用SMOTE進行過預(yù)處理的數(shù)據(jù)集
 max_depth = 15 # 調(diào)參（自己修改） #決策樹深度不能太深，不然容易導(dǎo)致過擬合
 min_size = 1
 sample_ratio = 1
 trees_num = 20

 feature_ratio = 0.3  # 盡可能小，但是要保證 int(self.feature_ratio * (len(train[0])-1)) 大于1
 same_value = 20  # 向量內(nèi)積的差（小于此值認為相似）
 same_rate = 0.82  # 樹的相似度（大于此值認為相似）
 # 加載數(shù)據(jù)
 dataset,features = load_csv(filename)
 traindata,testdata = split_train_test(dataset, feature_ratio)

 # 優(yōu)化1-獲取最優(yōu)深度
 # max_depth = getBestDepth(min_size, sample_ratio, trees_num, feature_ratio, traindata, testdata)
 # print('max_depth is ',max_depth)

 # 初始化隨機森林
 myRF = randomForest(trees_num, max_depth, min_size, sample_ratio, feature_ratio)
 # 生成隨機森林
 myRF.build_randomforest(traindata)

 print('Tree_number: ', myRF.trees.__len__())
 acc = myRF.accuracy_metric(testdata[:-1])
 print('傳統(tǒng)RF模型準(zhǔn)確率：',acc,'%')

 # 畫出某棵樹用以可視化觀察（這里是第一棵樹）
 # plotTree.creatPlot(myRF.trees[0], features)
 # 計算森林中每棵樹的AUC
 auc_list = caculateAUC_1.caculateRFAUC(testdata,myRF.trees)
 # 畫出每棵樹的auc——柱狀圖
 # plotTree.plotAUCbar(auc_list.__len__(),auc_list)

 # 選取AUC高的決策數(shù)形成新的森林(auc優(yōu)化)
 newTempForest = auc_optimization(auc_list,trees_num,myRF.trees)
 # 相似度優(yōu)化
 myRF.trees=similarity_optimization(newTempForest, same_value, same_rate)

 print('優(yōu)化后Tree_number: ', myRF.trees.__len__())
 # 測試評估
 acc = myRF.accuracy_metric(testdata[:-1])
 # print('優(yōu)化后模型準(zhǔn)確率：', acc, '%')
 print('myRF1_模型準(zhǔn)確率：', acc, '%')
 # 畫出某棵樹用以可視化觀察（這里是第一棵樹）
 # plotTree.creatPlot(myRF.trees[0], features)
 # 計算森林中每棵樹的AUC
 auc_list = caculateAUC_1.caculateRFAUC(testdata, myRF.trees)
 # 畫出每棵樹的auc——柱狀圖
 plotTree.plotAUCbar(auc_list.__len__(), auc_list)
 end = time.clock()
 print('The end!')
 print(end-start)