import os
import numpy as np
import matplotlib.pyplot as plt

DATA_FILE = './Machine-Learning/AdaBoost_Project2/horseColicTraining2.txt'
TEST_FILE = './Machine-Learning/AdaBoost_Project2/horseColicTest2.txt'

def load_data(filename):
    '''
    从文件中读取数据和标签 
    '''
    dirpath = os.path.relpath('.')
    filepath = os.path.join(dirpath, filename)
    data = []
    labels = []

    with open(filepath) as fr:
        lines = [line.strip().split('\t') for line in fr.readlines()]
        #nftrs = len(lines[0]) - 1
        for line in lines:
            d = line[:-1]
            l = line[-1]
            data.append(d)
            labels.append(l)
    return np.array(data, dtype=np.float), np.array(labels, dtype=np.float, ndmin=2)


def stumpClassify(data, dimen, thresh_val, thresh_ineq):
    '''
    :data: 训练数据
    :dimen: 特征
    :thresh_val: 阈值
    :thresh_ineq: 符号

    :ret: 分类结果
    '''
    ret = np.ones((data.shape[0], 1))
    if thresh_ineq == 'lt':
        ret[data[:, dimen] <= thresh_val] = -1
    else:
        ret[data[:, dimen] > thresh_val] = -1
    return ret


def buildStump(data, labels, D):
    '''
    找到数据集上的最佳单层决策树

    Parameters:
        data: 训练集数据
        labels: 标签
        D: 样本权重

    Returns:
        bestStump: 最佳单层决策树信息
        minError: 最小误差
        bestClasEst: 最佳的分类结果

    ------------------------------------------------
    1. 对于训练数据集中的每一个特征：
        1.1 对于大于和小于（等于）两种情况:
            1.1.1 计算分类的阈值
            1.1.2 计算分类结果
            1.1.3 计算加权误差率
            1.1.4 计算最小误差率及对应的基本分类器
    ------------------------------------------------
    '''
    # m=5, n=2
    m, n = np.shape(data)
    numSteps = 10.0
    bestStump = {}
    # (5, 1)全零列矩阵
    bestClasEst = np.zeros((m, 1))
    # 最小误差初始化为正无穷大inf
    minError = float('inf')
    # 遍历所有特征
    for i in range(n):
        # 找到(每列)特征中的最小值和最大值
        rangeMin = data[:, i].min()
        rangeMax = data[:, i].max()
        # 计算步长
        stepSize = (rangeMax - rangeMin) / numSteps
        for j in range(-1, int(numSteps) + 1):
            # 大于和小于的情况均遍历，lt:Less than  gt:greater than
            for inequal in ['lt', 'gt']:
                # 计算阈值
                threshVal = (rangeMin + float(j) * stepSize)
                # 计算分类结果
                predictedVals = stumpClassify(data, i, threshVal, inequal)
                # 初始化误差矩阵
                errArr = np.ones((m, 1))
                # 分类正确的，赋值为0
                labels = labels.reshape(-1, 1)
                errArr[predictedVals == labels] = 0
                # 计算误差
                weightedError = D.T.dot(errArr)
                print("基本分类器 特征: %d, 阈值: %.2f, 符号: %s, 加权误差: %.3f" % (i, threshVal, inequal, weightedError))
                # 找到误差最小的分类方式
                if weightedError < minError:
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump, minError, bestClasEst


def adaClassify(datToClass, classifierArr):
    '''
    函数说明：AdaBoost分类函数
    
    Parameters:
        datToClass - 待分类样例
        classifierArr - 训练好的分类器
        
    Returns:
        分类结果
    '''
    data = datToClass
    m = np.shape(data)[0]
    aggClassEst = np.zeros((m, 1))
    for i in range(len(classifierArr)):
        # 遍历所有分类器进行分类
        classEst = stumpClassify(data, classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])
        aggClassEst += classifierArr[i]['alpha'] * classEst
        # print(aggClassEst)
    return np.sign(aggClassEst)



def adaBoostTrainDS(dataArr, classLabels, numIt=60):
    '''
    函数说明：使用AdaBoost进行优化
    
    Parameters:
        dataArr - 数据矩阵
        classLabels - 数据标签
        numIt - 最大迭代次数
        
    Returns:
        weakClassArr - 存储单层决策树的list
        aggClassEsc - 训练的label
    '''
    weakClassArr = []
    # 获取数据集的行数
    m = np.shape(dataArr)[0]
    # 样本权重，每个样本权重相等，即1/n
    D = np.ones((m, 1)) / m
    # 初始化为全零列
    aggClassEst = np.zeros((m, 1))
    # 迭代
    for i in range(numIt):
        # 构建单层决策树
        bestStump, error, classEst = buildStump(dataArr, classLabels, D)
        # print("D:", D.T)
        # 计算弱学习算法权重alpha，使error不等于0，因为分母不能为0
        alpha = float(0.5 * np.log((1.0 - error) / max(error, 1e-16)))
        # 存储弱学习算法权重
        bestStump['alpha'] = alpha
        # 存储单层决策树
        weakClassArr.append(bestStump)
        # 打印最佳分类结果
        # print("classEst: ", classEst.T)
        # 计算e的指数项
        expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)
        # 计算递推公式的分子
        D = np.multiply(D, np.exp(expon))
        # 根据样本权重公式，更新样本权重
        D = D / D.sum()
        # 计算AdaBoost误差，当误差为0的时候，退出循环
        # 以下为错误率累计计算
        aggClassEst += alpha * classEst
        # print("aggClassEst: ", aggClassEst.T)
        # 计算误差
        aggErrors = np.multiply(np.sign(aggClassEst) != (classLabels).T, np.ones((m, 1)))
        errorRate = aggErrors.sum() / m
        # print("total error:", errorRate)
        if errorRate == 0.0:
            # 误差为0退出循环
            break
    return weakClassArr, aggClassEst


if __name__ == '__main__':
    dataArr, LabelArr = load_data(DATA_FILE)
    weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, LabelArr)
    testArr, testLabelArr = load_data(TEST_FILE)
    print(weakClassArr)
    predictions = adaClassify(dataArr, weakClassArr)
    errArr = np.mat(np.ones((len(dataArr), 1)))
    print('训练集的错误率:%.3f%%' % float(errArr[predictions != np.mat(LabelArr).T].sum() / len(dataArr) * 100))
    predictions = adaClassify(testArr, weakClassArr)
    errArr = np.mat(np.ones((len(testArr), 1)))
    print('测试集的错误率:%.3f%%' % float(errArr[predictions != np.mat(testLabelArr).T].sum() / len(testArr) * 100))

import numpy as np

class AdaBoost:

    def __init__(self, features, labels, iter_times=3):
        self.ftrs = features
        self.labels = labels
        self.iter_times = iter_times
        wights = [1 / len(features)] * len(features)
        self.weights = np.array(wights)
        self.values_list = []

    def base_classifier(self, value, ftrs, less):
        classes = 2 * (ftrs < value) - 1
        return classes if less else -classes

    def error_ratio(self, ftrs, value, less):
        classes = self.base_classifier(value, ftrs, less)
        err_ratio = sum(self.weights * (classes != self.labels))
        return err_ratio

    def get_coff(self, ftrs, value, less):
        err_ratio = self.error_ratio(ftrs, value, less)
        coff = np.log((1 - err_ratio) / err_ratio) / 2
        return coff

    def get_best_v(self, ftrs):
        ftrs = ftrs * self.weights
        ftrs = np.sort(ftrs)
        values = [(ftrs[i]+ftrs[i+1])/2
                        for i in range(len(ftrs))
                            if i != len(ftrs)-1]
        values.append(ftrs[-1]+0.1)
        err_ratios = [self.error_ratio(ftrs, v, less)
                        for less in [True, False] for v in values]
        min_index = err_ratios.index(min(err_ratios))
        less = min_index < 10
        min_index = min_index % 10
        return self.ftrs[min_index] + 0.5, less

    def renew_weights(self, alpha, value, ftrs, less):
        G = self.base_classifier(value, ftrs, less)
        expon = -alpha * self.labels * self.base_classifier(value, ftrs, less)
        normal_coff = sum(self.weights * np.exp(expon))
        self.weights = self.weights * np.exp(expon) / normal_coff

    def train(self):
        for i in range(self.iter_times):
            value, less = self.get_best_v(self.ftrs)
            alpha = self.get_coff(self.ftrs, value, less)
            self.renew_weights(alpha, value, self.ftrs, less)
            print("[", i, "]", "\n分类点:", value, "\n系数:",
                    alpha, "\n权重:", self.weights)
            self.values_list.append((value, less))

    def sign(self, features):
        return 1 if features > 0 else -1

    def predict(self, features):
        func_list = [self.base_classifier(value, features, less)
                     for value, less in self.values_list]
        result = sum(func_list)
        return self.sign(result)

if __name__ == "__main__":
    np.set_printoptions(precision=3)
    features = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    labels = np.array([1, 1, 1, -1, -1, -1, 1, 1, 1, -1])
    adaboost = AdaBoost(features, labels)
    adaboost.train()