机器学习——adaboost

• 一、Adaboost
• • 1. 基本原理
  • 2. 数据权重和弱分类器权重
• 二、算法步骤
• 三、具体实现

• Adaboost算法（Adaptive Boost）是一种迭代算法，其核心思想是针对同一个训练集训练不同的弱分类器，然后把这些弱分类器集合起来，构成一个强分类器。
• 弱分类器（单层决策树）
  （1）Adaboost一般使用单层决策树作为其弱分类器。单层决策树是决策树的最简化版本，只有一个决策点。也就是说，如果训练数据有多维特征，单层决策树也只能选择其中一维特征来做决策，并且还有一个关键点，决策的阈值也需要考虑。
  （2）在单层决策树计算误差时，Adaboost要求其乘上权重，即计算带权重的误差。
  （3）权重分布影响着单层决策树决策点的选择，权重大的点得到更多的关注，权重小的点得到更少的关注。

• 数据的权重
  主要用于弱分类器寻找其分类误差最小的决策点，找到之后用这个最小误差计算出该弱分类器的权重。
• 弱分类器的权重
  最终投票表决时，需要根据弱分类器的权重来进行加权投票，权重大小是根据弱分类器的分类错误率计算得出的，总的规律就是弱分类器错误率越低，其权重就越高。

输入： 训练数据集 T = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) ) T = ((x_1,y_1),(x_2,y_2),...,(x_N,y_N)) T=((x1​,y1​),(x2​,y2​),...,(xN​,yN​))，其中， x i ∈ X ⊆ R n ， y i ∈ Y = − 1 , 1 ， 迭 代 次 数 M x_i ∈X⊆R^n ，yi∈Y=−1,1，迭代次数M xi​∈X⊆Rn，yi∈Y=−1,1，迭代次数M

1. 初始化训练样本的权值分布： D 1 = ( w 11 , w 12 , … , w 1 i ) , w 1 i = 1 / N , i = 1 , 2 , … , N D1=(w_{11},w_{12},…,w_{1i}),w_{1i}=1/N,i=1,2,…,N D1=(w11​,w12​,…,w1i​),w1i​=1/N,i=1,2,…,N。
2. 对于 m = 1 , 2 , … , M m=1,2,…,M m=1,2,…,M
   2.1 使用具有权值分布 D m D_m Dm​的训练数据集进行学习，得到弱分类器 G m ( x ) G_m(x) Gm​(x)
   2.2 计算 G m ( x ) G_m(x) Gm​(x)在训练数据集上的分类误差率：
   e m = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) (1) e_m = sum_{i=1}^{N} w_{mi}I(G_m(x_i) neq y_i) tag{1} em​=i=1∑N​wmi​I(Gm​(xi​)​=yi​)(1)
   2.3 计算 G m ( x ) G_m(x) Gm​(x)在强分类器中所占的权重：
   a m = 1 2 l o g 1 − e m e m (2) a_m = frac{1}{2}logfrac{1-e_m}{e_m} tag{2} am​=21​logem​1−em​​(2)
   2.4 更新训练数据集的权值分布（这里， z m z_m zm​是归一化因子，为了使样本的概率分布和为1）：
   w ( m + 1 ) i = w m i z m e x p ( − α m y i G m ( x i ) ) , i = 1 , 2 , . . . , N (3) w_{(m+1)i} = frac{w_{mi}}{z_m}exp(-α_my_iG_m(x_i)),i = 1,2,...,N tag{3} w(m+1)i​=zm​wmi​​exp(−αm​yi​Gm​(xi​)),i=1,2,...,N(3)
   z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) (4) z_m = sum_{i=1}^{N}w_{mi}exp(-α_my_iG_m(x_i)) tag{4} zm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​))(4)
3. 得到最终分类器：
   F ( x ) = s i g n ( ∑ i = 1 N α m G m ( x ) ) (5) F(x)=sign(sum_{i=1}^{N}α_mG_m(x))tag{5} F(x)=sign(i=1∑N​αm​Gm​(x))(5)
   举例：
   比如在一维特征时，经过3次迭代，并且知道每次迭代后的弱分类器的决策点与发言权，看看如何实现加权投票表决的。
   
   如图所示，3次迭代后得到了3个决策点，

• 最左边的决策点是小于（等于）7的分为+1类，大于7的分为-1类，且分类器的权重为0.5；它的投票表示，小于（等于）7的区域得0.5，大于7得-0.5。
• 中间的决策点是大于（等于）13的分为+1类，小于13分为-1类，权重0.3；它的投票表示大于（等于）13的区域得0.3，小于13分区域得-0.3。
• 最右边的决策点是小于（等于19）的分为+1类，大于19分为-1类，权重0.4。它的投票表示小于（等于19）的区域得0.4，大于19分区域得-0.4。
  如下图：
  
  求和可得：
  
  最后进行符号函数转化即可得到最终分类结果：
  

1. 带权数据集

package machinelearning.adaboostig;

import java.io.FileReader;
import java.util.Arrays;

import weka.core.Instances;



public class WeightedInstances extends Instances {

	
	private static final long serialVersionUID = 11087456L;

	
	private double[] weights;

	
	public WeightedInstances(FileReader paraFileReader) throws Exception {
		super(paraFileReader);
		setClassIndex(numAttributes() - 1);

		// Initialize weights
		weights = new double[numInstances()];
		double tempAverage = 1.0 / numInstances();
		for (int i = 0; i < weights.length; i++) {
			weights[i] = tempAverage;
		} // Of for i
		System.out.println("Instances weights are: " + Arrays.toString(weights));
	} // Of the first constructor

	
	public WeightedInstances(Instances paraInstances) {
		super(paraInstances);
		setClassIndex(numAttributes() - 1);

		// Initialize weights
		weights = new double[numInstances()];
		double tempAverage = 1.0 / numInstances();
		for (int i = 0; i < weights.length; i++) {
			weights[i] = tempAverage;
		} // Of for i
		System.out.println("Instances weights are: " + Arrays.toString(weights));
	} // Of the second constructor

	
	public double getWeight(int paraIndex) {
		return weights[paraIndex];
	} // Of getWeight

	
	public void adjustWeights(boolean[] paraCorrectArray, double paraAlpha) {
		// Step 1. Calculate alpha.
		double tempIncrease = Math.exp(paraAlpha);

		// Step 2. Adjust.
		double tempWeightsSum = 0; // For normalization.
		for (int i = 0; i < weights.length; i++) {
			if (paraCorrectArray[i]) {
				weights[i] /= tempIncrease;
			} else {
				weights[i] *= tempIncrease;
			} // Of if
			tempWeightsSum += weights[i];
		} // Of for i

		// Step 3. Normalize.
		for (int i = 0; i < weights.length; i++) {
			weights[i] /= tempWeightsSum;
		} // Of for i

		System.out.println("After adjusting, instances weights are: " + Arrays.toString(weights));
	} // Of adjustWeights

	
	public void adjustWeightsTest() {
		boolean[] tempCorrectArray = new boolean[numInstances()];
		for (int i = 0; i < tempCorrectArray.length / 2; i++) {
			tempCorrectArray[i] = true;
		} // Of for i

		double tempWeightedError = 0.3;

		adjustWeights(tempCorrectArray, tempWeightedError);

		System.out.println("After adjusting");

		System.out.println(toString());
	} // Of adjustWeightsTest

	
	@Override
	public String toString() {
		String resultString = "I am a weighted Instances object.rn" + "I have " + numInstances() + " instances and "
				+ (numAttributes() - 1) + " conditional attributes.rn" + "My weights are: " + Arrays.toString(weights)
				+ "rn" + "My data are: rn" + super.toString();

		return resultString;
	} // Of toString

	
	public static void main(String args[]) {
		WeightedInstances tempWeightedInstances = null;
		String tempFilename = "D:/00/data/iris.arff";
		try {
			FileReader tempFileReader = new FileReader(tempFilename);
			tempWeightedInstances = new WeightedInstances(tempFileReader);
			tempFileReader.close();
		} catch (Exception exception1) {
			System.out.println("Cannot read the file: " + tempFilename + "rn" + exception1);
			System.exit(0);
		} // Of try

		System.out.println(tempWeightedInstances.toString());

		tempWeightedInstances.adjustWeightsTest();
	} // Of main

} // Of class WeightedInstances