⑴Motivation of Aggregation

比如现在有一支股票，你不知道是跌还是涨。你有T个friends，每一个friend对应的建议分别是g1,g2,g3...gn，那么你应该怎么选择建议？

⑵Blending

1.Select the most trust-worthy friend

这其实就是对应validation，我们在所有的friend里面做kfold或者vfoldvalidation，然后比较Ein，小的将拿出来作为你的most trust-worthy friend。和我们之前学的一样，选择应该最好的模型做预测即可。

2.mix their opinion from all your friends uniformly

如果你的friends的水平都差不多，那么不如混合一下他们的想法求平均，把所有的预测结果加载一起进行平均求解。

3.mix their opinion from all your friends non-uniformly

如果你的friends水平参差不齐，那么就可以给予不同的重视程度，比如有专业搞股票的，那就给多点投票权给他，不是就减少点。

4.combine the opinion conditionally

第四种方法与第三种方法类似，但是权重不是固定的，根据不同的条件，给予不同的权重。和第三个相比，不同之处就在于它是动态的。比如如果是传统行业的股票，那么给这方面比较厉害的朋友较高的投票权重，如果是服务行业，那么就给这方面比较厉害的朋友较高的投票权重。

但是第一种方法只是从众多的模型中选择一个最好的，aggregation就是融合，我们需要的是集体的智慧。看一下为什么aggregation可以比普通的模型work better。

一条一条线就是刚刚的validation，aggregation做的就是融合，比如上部分中间的圆圈的点，叉叉一票，圈圈是两票，所以就是圈圈，所以aggregation是可以做到feature transform的。所以是起到了特征转换的效果：

再从另一个方面来看：比如我们使用perceptron learning algorithm：

而如果综合一下投票选择，平均一下是可以得到中间那条最好的直线，这和SVM的目标是一样的。所以aggregation也起到了regularization的效果。综合一下：

The advantages of aggregation model

①feature transform
②regularization

⑶Uniform Blending

对应着第三种方法。我们已经选择好了一些比较好的gt，其实就是model，我们已经从friends里面选择几个很好的朋友出来做aggregation了。uniform意味着就是平均，分类公式：

这种方法对应三种情况：第一种情况是每个候选的矩gt都完全一样，这跟选其中任意一个gt效果相同；第二种情况是每个候选的矩gt都有一些差别，这是最常遇到的，大都可以通过投票的形式使多数意见修正少数意见，从而得到很好的模型，如下图所示；第三种情况是多分类问题，选择投票数最多的那一类即可。

小的差别是可以被大的方向所correct。如果是回归问题：

第一种情况：如果gt都是一样的，那么没有任何区别
第二种情况：如果是都不一样都有差别，那么求平均其实可以减弱这些差别的影响。

对于uniform blending for regression的可行性

所以有：

所以从平均来说，求gt的平均值G比单一的gt要效果更好，可能对于左边单一gt-lost function求平均会混淆单一的gt效果，求平均只是简化计算，配合右边的而已，如果不要平均还是一样的结果，分别求lost相加求平均和先平均再求lost其实就是单一gt和平均G的lost对比。
我们已经知道G是数目为T的gt的平均值。令包含N个数据的样本D独立同分布于PN，每次从新的Dt中学习得到新的gt，在对gt求平均得到G，当做无限多次，即T趋向于无穷大的时候：


所以当T是infinite的时候，得到的g杆就是把T个训练好的朋友的结果综合起来，代替G。这T个gt是通过不同的D来训练的，把他们扔进A(Dt)进行训练，最后得到结果。
所以对应上面等式可以得到：avg(Eout(gt))就是演算法A期望的表现（expected performance of A），因为就是通过A(Dt)演算法来挑选出合适的gt来进行平均的，avg(ε(gt - G)^2)就是不同的gt和他们达成的共识相差了多少（expected deviation to consensus，called variance），Eout(G)就是达成的共识（performance of consensus），而blending在求平均的过程中就有减弱上述variance的作用，只是削弱，而不是消除。因为只有T趋于无限的时候才有可能用g杆完全替代G，因为G是所有gt的consensus，而达成共识是要求大方向把小方向给correct过来，如果大方向不够大，那么是没有能力correct的，所以平时我们使用的是近似于G，而不是真正意义上的G，所以上面的variance不能完全消除。

⑷uniform-blending的代码实现

导包准备和读取数据文件：

import numpy as np
import pandas as pd

def read_file(filename):
  '''
  use to read file which you open
  :param filename:
  :return:dataset
  '''
  data = pd.read_csv(filename)
  return data
  pass

def load_data():
  print('Loading data......')
  train = read_file('../../Data/train.csv')
  test = read_file('../../Data/test.csv')
  y_train = train.iloc[: , 0]
  x_train = train.iloc[: , 1:]
  y_test = test.iloc[: , 0]
  x_test = test.iloc[: , 1:]
  return x_train , y_train , x_test , y_test
  pass

if __name__ == '__main__':
  x_train , y_train , x_test , y_test = load_data()
  print('x_train : ',x_train)
  print('y_train : ',y_train)

又导包：

import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
import MachineLearning.AggregationModel.Blending.load_data as load_data
from sklearn.model_selection import StratifiedKFold
from sklearn.ensemble import RandomForestClassifier , ExtraTreesClassifier
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.linear_model import LogisticRegression

主函数部分：

if __name__ == '__main__':

  np.random.seed(0)  # seed to shuffle the train set
  accuracys = []
  verbose = True
  shuffle = False

  X, y, X_test , y_test = load_data.load_data()

  if shuffle:
      idx = np.random.permutation(y.size) #random a sequence
      X = X[idx]
      y = y[idx]
  clfs = [RandomForestClassifier(n_estimators=100, n_jobs=-1, criterion='gini'),
          RandomForestClassifier(n_estimators=100, n_jobs=-1, criterion='entropy'),
          ExtraTreesClassifier(n_estimators=100, n_jobs=-1, criterion='gini'),
          ExtraTreesClassifier(n_estimators=100, n_jobs=-1, criterion='entropy'),
          GradientBoostingClassifier(learning_rate=0.05, subsample=0.5, max_depth=6, n_estimators=50)]

  print('Building the model......')
  dataset_blend_train = np.zeros((X.shape[0], len(clfs)))
  dataset_blend_test = np.zeros((X_test.shape[0], len(clfs)))
  test_matrix = np.zeros((len(y_test) , 5))




  for j, clf in enumerate(clfs):
      print (j, clf)
      clf.fit(X[j*700 : (j+1)*700] , y[j*700 : (j+1)*700])
      predict = clf.predict_proba(X_test)[: , 1]
      predict1 = []
      for i in range(len(predict)):
          if predict[i] > 0.5:
              predict1.append(1)
          else:
              predict1.append(0)
          pass
      accuracys.append(calculate_accuracy(predict1 , y_test))
      test_matrix[: , j] = predict

  predictions = []
  for i in range(len(test_matrix)):
      if test_matrix[i].mean() > 0.5:
          predictions.append(1)
      else:
          predictions.append(0)

  accuracys.append(calculate_accuracy(predictions , y_test))
  indexs_name = ['RandomForest','RandomForest','ExtraTrees_gini','ExtraTrees_entropy' , 'GradientBoosting','Average']
  draw(accuracys , indexs_name)

选择的model分别是randomforest，extraTrees和FradientBoosting，这就是选择gt的步骤，之后就是用不同的训练集去训练他们，5个model那就把数据分成5类，不同的数据训练不同模型，综合结果。
工具函数：

def calculate_accuracy(predictions , y_test):
  sum = 0
  for i in range(len(y_test)):
      if predictions[i] == y_test.tolist()[i]:
         sum += 1
  print("accuracy ：",(sum/len(y_test))*100 , '%')
  return (sum/len(y_test))*100

def draw(accuracys , indexs_name):
  fig, ax = plt.subplots()
  colors = ['#B0C4DE','#6495ED','#0000FF','#0000CD','#000080','#191970']
  ax.bar(range(len(accuracys)), accuracys, color=colors, tick_label=indexs_name)
  plt.xlabel('ModelName')
  plt.ylabel('Accuracy')
  ax.set_xticklabels(indexs_name,rotation=30)
  plt.show()
  pass

最后画柱形图：

平均下来的还是很高的，符合上面的avg(Eout(gt)) > E(avg(gt))的结果。

⑸Linear Blending and Any Blending

之前讲的是平均的思想，先要提的是linear Blending，对应的就是 non-uniformly：

那么主要是怎么找到最好的α，可以应用之前的误差最小化的思想：

和之前的线性模型差不多，可以用梯度下降或者牛顿法求解，但是区别就是α有存在限制。所以linear blending = 线性模型 + feature transform + 限制
事实上对于α这个值的正反其实可以不理会：

当α ＜ 0，有|α|(-g(x))，意思就是让我们反着用，对的当错的，错的当对的。α ＞ 0就一切照常使用。
对于Any Blending，其实就是stacking，堆叠模型，一层一层用不同的模型进行训练。

⑹Bagging（Boostrap Aggregation）

对于Blending，无论是Uniform的还是Non-Uniform或者是conditional，都是先得到gt，也就是先用不同的数据训练好gt之后在进行的aggregate，那么我们能否一边做aggregation一边做getting gt呢？

问题来了，如何得到不同的g。在blending中是使用不同的model来得到不同的g，这是一种方法。①使用不同的model。②同一model不同参数。③algorithm本身就带有随机性，比如kmean，EM这种对于初值很敏感的算法，PLA本身这种比较随机的。④数据随机，不同的数据训练模型，可以相同模型也可以不同模型。

回顾一下上一节讲到的一个演算法可以有两部分构成：

那如何利用已有的一份数据集来构造出不同的gt呢？首先，我们回顾一下之前介绍的bias-variance，即一个演算法的平均表现可以被拆成两项，一个是所有gt的共识（bias），一个是不同gt之间的差距是多少（variance）。其中每个gt都是需要新的数据集的。只有一份数据集的情况下，如何构造新的数据集？
其中g杆是在T趋于infinite的时候不同gt计算得到的平均值，为了得到g杆，我们需要构造两个近似条件：
①有限的T
②由已有数据集D构造出Dt PN，独立同分布

第一个条件是可以完成的，第二个条件使用boostrap做法。假设我们有N笔资料，选出一个样本，记录下，再放回去，再选择一个样本，再放回去，重复N次。这样我们就得到了新的一笔资料，这笔资料里面有可能有重复的也有可能没有原数据里面的某些样本。而抽取放回操作不一定是要N次。

有一个实际的例子：
下面举个实际中Bagging Pocket算法的例子。如下图所示，先通过bootstrapping得到25个不同样本集，再使用pocket算法得到25个不同的gt，每个pocket算法迭代1000次。最后，再利用blending，将所有的gt融合起来，得到最终的分类线，如图中黑线所示。可以看出，虽然bootstrapping会得到差别很大的分类线（灰线），但是经过blending后，得到的分类线效果是不错的，则bagging通常能得到最佳的分类模型。

⑺Bagging的代码实现

实现主要的Bagging包：
就是一个类：

class Bagging(object):

所有有关于Bagging的方法都会在这里。
首先是初始化方法：

  def __init__(self ,n_estimators , estimator , rate = 1.0):
      self.n_estimators = n_estimators
      self.estimator = estimator
      self.rate = rate
      pass

有多少个基础模型，模型是哪几个，如果是下采样那么采样率是多少。然后就是投票函数了，因为得到的结果是横着的，横坐标是model纵坐标是prediction，所有要transpose一下，取出每一行看看是1多还是0多，然后取最多的返回即可。

  def Voting(self , data):
      term = np.transpose(data)
      result = list()
      def Vote(df):
          store = defaultdict()
          for kw in df:
              store.setdefault(kw , 0)
              store[kw] += 1
          return max(store , key=store.get)
      result = map(Vote , term)
      return result

下采样，如果是用下采样的话就可以调用这个函数：

  def UnderSampling(self,data):
      data = np.array(data)
      np.random.shuffle(data)
      newdata = data[0:int(data.shape[0]*self.rate),:]
      return newdata
      pass

刚刚采样的rate就有用了。
训练预测，这些别人已经写好了，不用多写：
重心是在于Bagging模型本身，这些算法在后面讲到的时候会详细说到。

  def TrainPredict(self , train , test):
      clf = self.estimator.fit(train[: , 0:-1] , train[: , -1])
      result = clf.predict(test[: , 0:-1])
      return result
      pass

然后就是boostrap采样了：

  def RepetitionRandomSampling(self , data , number):
      samples = []
      for i in range(int(self.rate * number)):
          samples.append(data[random.randint(0, len(data) - 1)])
          pass
      return samples
      pass

这个就是一直随机基于好了。

  def Metrics(self, predict_data , test):
      score = predict_data
      pre = np.matrix(test[: , -1])
      score = list(score)
      score = np.matrix(score)
      recall = recall_score(pre.T , score.T, average=None)
      precision = accuracy_score(pre.T, score.T)
      return recall , precision
      pass

估计模型效果，recall，metric，F1，accuracy，precision这些以后会有详细的篇章会讲到。

  def MutModel_clf(self , train , test , sample_type = 'RepetitionRandomSampling'):
      result = list()
      sample_function = self.RepetitionRandomSampling
      num_estimators = len(self.estimator)
      if sample_type == "RepetitionRandomSampling":
          print('Sample type : ' , sample_type)
      elif sample_type == "UnderSampling":
          print('Sample type : ' , sample_type)
          sample_function = self.UnderSampling
          print ("sampling frequency : ",self.rate)
      for estimator in self.estimator:
          print (estimator)
          for i in range(int(self.n_estimators/num_estimators)):
              sample=np.array(sample_function(train,len(train)))
              clf = estimator.fit(sample[:,0:-1],sample[:,-1])
              result.append(clf.predict(test[:,0:-1]))

      score = self.Voting(result)
      recall,precosoion = self.Metrics(score,test)
      return recall,precosoion

只会就是主函数了。

之后就到了数据处理了，因为使用的数据还是上一次blending使用的数据，所以要把label放到最后，做一下数据处理：

import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
import numpy as np

def MoveActivity(fileName , location , saveName):
  dataframe = pd.read_csv(location + fileName)
  activity = dataframe['Activity']
  dataframe.drop(labels=['Activity'], axis=1,inplace = True)
  dataframe.insert(len(dataframe.columns.values) , 'Activity', activity)
  dataframe.to_csv(location + saveName,index=False)
  pass

if __name__ == '__main__':
  MoveActivity(fileName='train.csv' , location='../../Data/' , saveName='newtrain.csv')
  MoveActivity(file

生成一个新的表格CSV。

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns
import MachineLearning.AggregationModel.Bagging.bagging as bagging
from sklearn.model_selection import StratifiedKFold
from sklearn.ensemble import RandomForestClassifier , ExtraTreesClassifier
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.linear_model import LogisticRegression
def loadData():
  train = pd.read_csv('../../Data/newtrain.csv')
  test = pd.read_csv('../../Data/newtest.csv')
  train = train.as_matrix()
  test = test.as_matrix()
  return train , test
  pass

def Running():
  train , test = loadData()
  clfs = [RandomForestClassifier(n_estimators=100, n_jobs=-1, criterion='gini'),
          RandomForestClassifier(n_estimators=100, n_jobs=-1, criterion='entropy'),
          ExtraTreesClassifier(n_estimators=100, n_jobs=-1, criterion='gini'),
          ExtraTreesClassifier(n_estimators=100, n_jobs=-1, criterion='entropy'),
          GradientBoostingClassifier(learning_rate=0.05, subsample=0.5, max_depth=6, n_estimators=50)]
  bag = bagging.Bagging(n_estimators=5 , estimator=clfs)
  recall , precision = bag.MutModel_clf(train , test)
  print(recall , precision)
  pass

if __name__ == '__main__':
  Running()

使用的模型和上一个blending的是一样的，便于对比。最后做了一下对比：

if __name__ == '__main__':
  pres1 = []
  pres2 = []

  for i in range(10):
      pre = Running(sample='UnderSampling')
      pres2.append(pre)

  for i in range(10):
      pre = Running()
      pres1.append(pre)


  plt.plot([x for x in range(10)] , pres1 , c = 'r')
  plt.plot([x for x in range(10)] , pres2 , c = 'b')
  plt.show()

效果对比：

红色的线是boostrap采样，蓝色的线是下采样，其实也不是下采样，因为刚刚忘记设置rate了，所以默认是1.......。总体效果还是比blending要好的。
GitHub上代码：

https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/AggregationModel/Bagging

⑻Adaptive Boosting

继续Aggregation Model，最后一个集成算法——Adaptive Boosting，和前面一样都是监督式的学习。举一个简单的例子：老师要求学生来识别一些苹果，上面的是苹果下面的是其他东西。一个学生说，圆形的是苹果，于是成功的识别了一些，但是也有错误的。于是有了下图：

既然有正确分类的了，那么应该要把注意力放在错误的地方上，其他算法也是这样，logistics linear SVM都是minimize lost function。于是另一个学生又提出来了，红色的才是苹果，于是有：

但是错误的几个里面，绿色的也可以是苹果，于是另一个学生又说绿色的是苹果，然后又有：

还是有错，于是另一个同学又说有梗的才是苹果，然后：

这下就正确了，经过这几个同学的推论，苹果就是园的，红色或者绿色，有梗，虽然可能不是非常准确，但是要比单一的条件要好得多。也就是说把所有学生对苹果的定义融合起来，最终得到一个比较好的对苹果的总体定义。这个过程就是boosting，一开始的单个分类器，也就是一个同学是弱分类器，然后boosting主要就是集中多个弱分类器把它变成强的分类器。
在上面的例子里面，老师就像是演算法，学生就像hypothesis 的g，苹果的总定义就是G，老师的作用有两个，一个是选择学生，第二个就是指导方向，使得它们的注意力集中在错误上面。

①Diversity by Re-weighting

介绍这个algorithm之前先来看一下之前的bagging，bagging的抽样方法是boostrap抽样得到一个和原始数据类似的数据D1，然后训练gt，之后进行aggregation操作。假设我们现在有D个样本，进行了一次boostrap抽样操作：

那么对于一个新的抽样得到的数据D1，把他交给一个算法，让他计算：

可以看到抽样出来x1有两个，既然是两个的x1的，那就说明x1只要犯了错误那么就相当于是两个x1犯了错误，说明它做错的程度要更深一些，于是改进一下，增加一个权值：

所以当D1里面出现次数越多的样本，他对应的u就是越大，也就是说他的惩罚会越厉害，其实就是通过bootstrap的方式，来得到这些ui值，作为犯错样本的权重因子，再用 algorithn最小化包含ui的error function，得到不同的gt。这个error function被称为bootstrap-weighted error。

这种算法形式就和之前的SVM差不多，在最后的soft margin里面，我们转换过ξ，他其实就是犯错误的多少，所以：

和之前的SVM不一样的是，这里的u相当于每个犯错的样本的惩罚因子，并会反映到α的范围限定上。
同样在logistics中也是一样的：

所以，知道了u的概念之后，我们是可以通过u来选择不同的gt的，意味我们是可以在相同的模型中通过参数不同来选择不同的gt。结果是要使得gt互相之间都很不相同，因为之前讲过越不同的gt想要找到他们的consensus就越难，不同的gt也会涉及不同的分类方式，所以效果也会越好，相当于是regularization和feature transform了。

问题来了，如何得到不同的g(t)和g(t+1)？按照上面的讲述：

g(t)是u(t+1)产生的，而g(t+1)是u(t+1)产生的，所以如果当g(t)用u(t+1)的时候效果很差时，就表明g(t)和g(t+1)是很差的了。于是我们利用随机效果，比如一枚硬币，随机的时候两面都是0.5，如果有：

那么就表明相差很大，因为gt对于预测分类是没有什么影响的了，已经是随机了，所以这个时候差异是最大的。
对于上面那个式子不太好求解，变换一下：

犯错误的点和没有犯错误的点用橙色和绿色表示，要让这个fraction是0.5，错误和正确的一样就可以了，所以，错误的都乘上正确的数量，正确的都乘上错误的数量，600张是对的，200张错的，那么错的都乘600对的都乘200就可以了。或者我们可以乘上分数，3/4和1/4。所以计算u(t+1)就可以乘上1-ε和ε了。

②Adaptive Boosting Algorithm

现在进入了真正的Adaboost。对于1-ε和ε这些还是有点麻烦，引入一个新的尺度：

对于正确的类别将会除以◇t，对于错误的将会乘上◇t。效果是一样的，之所以这样做是因为它代表了更多的physical significance；当ε ＜ 1/2，◇t ＞ 1，所以正确的除去◇t，就是在削弱正确类别的重要性，错误类别乘上就是增加它的权值，增加它的重要性，对于minimize影响这么大algorithm肯定会重视，于是就会花更多的力气来处理权值大的，这就是像刚刚的例子里面，老师指导方向的效果了。

从这里开始，我们就可以得到一个初步的演算法了：

初始值暂时不知道，①通过u(t)得到gt②利用gt更新u(t)到u(t+1)。
对于u的初始值，一开始可以都是平均的，或者可以用刚刚的boostrap抽样来决定。G(x)可以使用之前的linear blending算法，设置一个参数α作为gt的权重：

对于α，构造一个和上面◇t 相关的一个式子：

于是算法完整了：

α这样取值是有物理意义的，例如当ϵ=1/2时，error很大，跟掷骰子这样的随机过程没什么两样，此时对应的⋄t=1，α=0，即此gt对G没有什么贡献，权重应该设为零。而当ϵt=0时，没有error，表示该gt预测非常准，此时对应的⋄t=∞，α=∞，即此gt对G贡献非常大，权重应该设为无穷大。

由三部分构成：base learning algorithm A，re-weighting factor ⋄t和linear aggregation αt。这三部分分别对应于我们在本节课开始介绍的例子中的Student，Teacher和Class。

base algorithm：对应基础算法模型，比如决策树，SVM，logistics这些。
re-weighting factor ：对应的就是u的更新了。
linear aggregation：就是最后的G，综合gt的意见。
完整的算法流程：

---

③对于AdaBoost可行性的理解：

对这个VC bound中的第一项Ein(G)来说，有一个很好的性质：如果满足ϵt ≤ ϵ < 12，则经过T=O(log N)次迭代之后，Ein(G)能减小到 = 0的程度。而当N很大的时候，其中第二项也能变得很小。因为这两项都能变得很小，那么整个Eout(G)就能被限定在一个有限的上界中。dvc(H)这部分是base algorithm的复杂度，自然是不会太大了，基础算法就是弱分类器就行了，boost要做正是把弱分类器变强。T(logT)是迭代次数，这个是实践的时候得到的结论。logN/N就是样本数目了。迭代次数通常不会太久，数据大小也可以控制，所以综上来看，AdaBoost可以做到很好的效果缺不会太过拟合，这也就印证了之前regularization和feature transform的理解。

所以只要每一次ϵ ∈（ϵt , 1/2），也就是每一次都可以比随机好一点点，那么多次迭代就可以得到很好的结果了。Ein很小，Eout也不会差到哪里去。

⑼Adaptive Boosting in Action

看一下实际上的效果，待会会有代码的实现。
首先拿一些样本做切割：

迭代多几次之后就可以分开了。

⑽AdaBoost代码实现

⒈实现弱分类器decision-stump

实现Adaboost需要用到弱分类器，这个弱分类器使用的是decision-stump。这是一个单分类器，也叫单决策树，它会遍历所有数据的维度，然后找到最小的Ein在哪个维度上，那么哪个维度的那个线就是最好的分类。和上面的几个图是一样的，只能是垂直或者是竖直分，是一直弱分类器。它主要的过程就是遍历所有的数据维度，然后寻找一个合适的thresh作为分割，再看看是左边的作为positive好还是右边的作为positive好。从实际意义来看，decision stump 根据一个属性的一个判断就决定了最终的分类结果，比如根据水果是否是圆形判断水果是否为苹果，这体现的是单一简单的规则（或叫特征）在起作用。显然 decision stump 仅可作为一个 weak base learning algorithm（它会比瞎猜 1/2 稍好一点点，但好的程度十分有限），常用作集成学习中的 base algorithm，而不会单独作为分类器。
所以要优化的function：

所以要先实现一个decision-stump：

def decision_stump(dataMat , Labels , u):
  dataMat = np.mat(dataMat)
  Labels = np.mat(Labels).T
  n , d = dataMat.shape
  numSteps = 10.0
  bestSump = {}
  bestClasEst = np.mat(np.zeros((n , 1)))
  minError = np.inf
  for i in range(d):
      rangeMin = dataMat[: , i].min()
      rangeMax = dataMat[: , i].max()
      stepSize = (rangeMax - rangeMin) / numSteps
      for j in range(-1 , int(numSteps) + 1):
          for inequal in ['lt' , 'gt']:
              threshVal = (rangeMin + np.float32(j) * stepSize)
              predictedVals = stumpClassify(dataMat , i , threshVal , inequal)
              errArr = np.mat(np.ones((n , 1)))
              errArr[predictedVals == Labels] = 0
              weightedError = u.T * errArr

              if weightedError < minError:
                  minError = weightedError
                  bestClasEst = predictedVals.copy()
                  bestSump['dim'] = i
                  bestSump['thresh'] = threshVal
                  bestSump['inseq'] = inequal
  return bestSump, minError, bestClasEst

传入u参数是为了后面的兼容Adaboost的weightError，错误需要增加权重。按照上面的function解释一下功能：

①确定thresh，也就是确定阈值的范围，这里设置的是10个阈值，也就是每一个维度我按照10个来划分，迭代12次，找到最好的一个阈值。12次是因为最左和最右边各有一次。
②迭代dimension，开始寻找每一个维度是否是最小的Ein。
③迭代thresh，实际上就是迭代每一个维度上的12个thresh值，看看哪一个达到最小。
④如果thresh的positive和negative是反过来的也有可能造成很大的错误，所以看看哪边是positive或者是negative可以达到最好的效果，所以迭代lt和gt。
⑤最后得到是所有分类的1，-1标签，乘上每一个样本的权值u，就得到最终的error了。

thresh的decision-stump分类function：

def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):  # just classify the data
  retArray = np.ones((np.shape(dataMatrix)[0], 1))
  if threshIneq == 'lt':
      retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
  else:
      retArray[dataMatrix[:, dimen] > threshVal] = -1.0
  return retArray

其实就是调换一下positive和negative的表示方式。

⒉实现Adaboost

接下来就是主要的running function，Adaboost了：

def Running(Number , numIt):
  dataX , dataY = getData.get_Data(Number)
  weakClassArr = []
  n = dataX.shape[0]
  u = np.mat(np.ones((n , 1)) / n)
  aggClassEst = np.mat(np.zeros((n , 1)))
  getData.draw(dataX , dataY , Number , [])
  for i in range(numIt):
      bestSump, error, classEst = decision_stump(dataX, dataY, u)
      alpha = float(0.5 * np.log((1.0 - error) / max(error, 1e-16)))
      bestSump['alpha'] = alpha
      weakClassArr.append(bestSump)
      expon = np.multiply(-1 * alpha * np.mat(dataY).T, classEst)
      u = np.multiply(u , np.exp(expon)) / np.sum(u) #if miss the normalization,the u will be bigger than bigger , and the thresh is unusable.
      aggClassEst += alpha * classEst
      aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(dataY).T, np.ones((n, 1)))
      errorRate = aggErrors.sum() / n
      precision = np.multiply(np.sign(aggClassEst) == np.mat(dataY).T, np.ones((n, 1)))
      precision = (sum(precision) / n) * 100

      if i % 10 == 0:
          if precision == 100.0:
              break
          print('precision : ',precision)
          getData.draw(dataX , np.sign(aggClassEst) ,200, weakClassArr)
  return weakClassArr, aggClassEst

其实就是按照上面所讲的不找来写的。
实现步骤：

①首先是得到数据了，初始化一些参数等等，比如u，n还有多个弱分类器分类结果相加得到的aggClassEst。
②迭代，每一个迭代就会产生一个弱分类器，首先先用刚刚写的decision-stump得到一个弱分类器，α的更新公式：

把1/2提出来也是一样的。
③这个分类器算是完成了，把它加入到集合里面。
④对于u的更新：

整合一下，其实就是ue^(-αf(x)h(x))，上面的公式是可以化简成这样的。最后还有进行一个u的归一化，林轩宇老师上面的是没有进行归一化的，如果不进行归一化也可以，但是可能错误的权值会增加的很快，正确的权值就会增加的很慢，因为后面的分类结果是要multiple u然后相加的，这样就是会导致，可能你这个点在上一次分类是正确的，u有点小，但是这一次错了，一乘上结果u就很大了，一加起来就很大，会导致有些个别的点波动幅度会很大，最后不一定用-1 / 1这些阈值可以分开了，分类效果很受影响。归一化的一个好处就是可以把错误都限制在-1 / 1之间，最后还是可以用1.-1区分。
⑤最后就是一些错误的相加了，计算准确率和错误率。

⒊最后一个就是数据的准备了

生成一个sin的数据，就是要生成这种百分之80都是对的，看看剩下那20能不能分对，做到feature transform的效果。

import numpy as np
import random
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
def get_Data(Number):
  x = np.zeros((2*Number , 2),dtype = np.float32)
  y = np.zeros(2*Number , dtype = np.float32)
  t = np.linspace(0 , np.pi * 2 , Number)
  for i in range(Number):
      x[i] = np.c_[t[i] , np.sin(t[i]) - np.random.random() * 3]
      y[i] = 1
      pass
  for i in range(Number):
      x[Number+i] = np.c_[t[i] , np.sin(t[i]) + np.random.random() * 3]
      y[Number+i] = -1
  return x , y
  pass

def draw(X, Y, Number , line):
  for i in range(2*Number):
      if Y[i] == 1:
          plt.scatter(X[i,0], X[i, 1], color='r', marker='x')
      else:
          plt.scatter(X[i, 0], X[i, 1], color='b', marker='<')

      pass

  for l in line:
      if l['dim'] == 0:
          plt.plot(8*[l['thresh']] , np.linspace(0, 8, 8) , color = 'gray' , alpha = 0.5)
      else:
          plt.plot(np.linspace(0, 6.5, 6), 6 * [l['thresh']], color = 'gray', alpha=0.5)
      pass
  plt.title('DataSet')
  plt.xlabel('First Dimension')
  plt.ylabel('Second Dimension')
  plt.show()
  pass

if __name__ == '__main__':
  x , y = get_Data(200)
  draw(x, y, 200 , [])

效果200个点：

4.效果对比

讲道理，这东西应该是可以做到正确率百分之100的。但是：

看看效果：
一个弱分类器的时候
10个的时候
20个的时候
30个的时候
我后面又迭代了几次，讲道理，这我就有点虚了。
后来我又找了一下原因，numSize = 10，是不是这个decision stump分类能力太弱了，Adaboost虽然点名要弱的，但是这个散打比赛太弱了。于是改到40，然后就行了......
起最后的效果图（事实上改到40还是不行，到99.75%就停了，改到60之后就OK了）：


这样效果就有100%了，当然实际上这样会过拟合，但是这只是测试而已。
aggregation model完结！

所有代码在GitHub上：
https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/AggregationModel/Adaboost