AdaBoost算法和java实现

深藏阁楼爱情的钟 2022-08-03 11:38 298阅读 0赞

AdaBoost算法和java实现

算法描述

输入：训练数据集这里写图片描述,其中xi∈χ⊆Rn,yi∈{-1,+1};弱学习算法；
输出：最终分类器G(x)。

  1. 初始化训练集数据的权值分布
    D1=(w11,…,wiN), w1i=1/N, i=1,2…,N

  2. 对m=1,2,…,M

    • (a)使用具有权值分布Dm的训练数据集学习，得到基本分类器
      Gm(x):χ−−>{-1,+1}

    • (b) 计算Gm(x)在训练数据集上的分类误差率
      em=P(Gm(xi)≠yi)=∑Ni=1wmiI(Gm(xi)≠yi)

    • (c) 计算Gx的系数
      αm=12log1−emem这里的对数是自然对数。

  • (d)更新训练数据集的权值分布
    Dm+1=(wm+1,1,…wm+1,N)

    wm+1,i=wmiZmexp(−αmyiGm(xi)),i=1,2,…,N
    ,Zm是规范化因子

    Zm=∑Ni=1wmiexp(−αmyiGm(xi))
    它是Dm+1成为一个概率分布。

  1. 3. 构建基本分类器的线性组合

f(x)=∑Mm+1αmGm(x)

  1. 得到最终分类器

G(x)=sign(f(x))=sign(∑Mm=1αmGm(x))

举例说明

数据如下
这里写图片描述
当m=1时，
根据以上的公式有D1=(w1i,w2i,…,w2i),w1i=0.1,i=1,2,…,10然后在权值分布为D1的训练数据集上，阈值v取2.5时分类的误差率最低，故分类器为
注意
在训练集上的误差率e1=3*0.1(3表示有三个分类错误的数据，0.1对应权值数组D1上的值)

按照（c）中的公式据算 α1=12log1−e1e1=0.4236

更新数据的权值分布：
D2=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)()大家可以发现被错误分类的点的权值被加大了
f1(x)=α1G1(x)=0.4236G1(x)
分类器sign[f1(x)]在训练数据集上有三个错误分类点。

当m=2时，
-在权值分布为D2的训练数据集上 ，阈值v是8.5时分类误差率最低，基本分类器为

这里写图片描述
- G2(x)在训练数据集上的误差率e2=0.2143
- 计算α2=0.6496
-更新训练数据集权值分布：
D3=(0.455，0.455，0.455，0.1667，0.1667，0.1667,0.1060,0.1060,0.1060,0.0455)
f2(x)=0.4236G1(x)+0.6496G2(x)
分类器sign[f2(x)]在训练数据集上有三个错误分类点。

当m=3时，
-在权值分布为D2的训练数据集上 ，阈值v是8.5时分类误差率最低，基本分类器为

这里写图片描述
- G2(x)在训练数据集上的误差率e3=0.1820
- 计算α3=0.7514
-更新训练数据集权值分布：
D3=(0.125，0.125，0.125，0.102，0.102，0.102,0.065,0.065,0.065,0.125)
f2(x)=0.4236G1(x)+0.6496G2(x)+0.7514G3(x)
分类器sign[f2(x)]在训练数据集上有0个错误分类点。
故：G(x)=sign[f3(x)]=sign[0.4236G1(x)+0.6496G2(x)+0.7514G3(x)]

  1. import java.util.ArrayList;
  2. import java.util.Comparator;
  3. import java.util.HashMap;
  4. import java.util.Map;
  5. import java.util.TreeMap;
  7. public class Test08 {
  9.     public  ArrayList<String> list=new ArrayList<String>();
  10.     public static final double k = 0.5;
  11.     public static void main(String[] args) {
  12.         // TODO Auto-generated method stub
  13.         Test08 test=new Test08();
  14.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  15.         map.put(0, 1);
  16.         map.put(1, 1);
  17.         map.put(2, 1);
  18.         map.put(7, 1);
  19.         map.put(5, -1);
  20.         map.put(6, 1);
  21.         map.put(8, 1);
  22.         map.put(9, -1);
  23.         map.put(3, -1);
  24.         map.put(4, -1);
  25.         System.out.println(test.adaBoost(test.sortMapByKey(map)));
  26.     }
  28.     public TreeMap<Integer, Integer>  sortMapByKey(Map<Integer, Integer> oriMap) {
  29.         if (oriMap == null || oriMap.isEmpty()) {
  30.             return null;}
  31.         TreeMap<Integer, Integer> sortedMap = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
  32.             public int compare(Integer o1, Integer o2) {
  33.                 // 如果有空值，直接返回0
  34.                 if (o1 == null || o2 == null)
  35.                     return 0;
  36.                 return String.valueOf(o1).compareTo(String.valueOf(o2));
  37.             }
  38.         });
  39.         sortedMap.putAll(oriMap);
  40.         return sortedMap;
  41.     }
  43.     public Map<Double,Double> adaBoost(TreeMap<Integer, Integer> data) {
  44.         Map<Double,Double> result=new HashMap<Double,Double>();
  45.         int dataLenght=data.size();
  46.         double[] weight = new double[dataLenght];
  47.         //初始化权值数组
  48.         for (int i = 0; i < dataLenght; i++) {
  49.             weight[i]=1.0/dataLenght;
  50.         }
  52.         double grade1 = 0;
  53.         double grade2 = 0;
  54.         //double flag = 0;
  55.         String f=null;
  56.         double current=0;
  57.         double ah=0;
  58.         double low=data.firstKey();//选取最小的特征值
  59.         double high=data.lastKey();//选取最大的特征值
  60.         //迭代50次
  61.         for(int it=0;it<50;it++){
  62.             double min=1000;
  63.             double flag=low;//用来标记比较优的特征的值
  64.             while(flag<=high){
  65.                 int index = 0;// 用来索引权值数组
  66.                 grade1=0;
  67.                 grade2=0;
  68.                 for (Integer en : data.keySet()) {
  69.                     //大于某一个特征值则为一时
  70.                     if(GreatToOne(en, flag)!=data.get(en)){
  71.                         grade1+=weight[index];
  72.                     }
  73.                     //小于某一个特征值则为一时
  74.                     if(LessToOne(en, flag)!=data.get(en)){
  75.                         grade2+=weight[index];
  76.                     }   
  77.                     index++;
  78.                 }
  79.                 //选取最优的特征值
  80.                 if (grade1 < min) {
  81.                     min = grade1;
  82.                     current = flag;
  83.                     f="great";//用来标记采用的哪一个函数（GreatToOne or LessToOne）
  84.                 }
  85.                 if(grade2<min){
  86.                     min=grade2;
  87.                     current = flag;
  88.                     f="less";
  89.                 }
  90.                 flag+=k;//将用来分类的特征值增加k
  91.             }
  92.             ah=0.5*Math.log((1-min)/min);
  93.             double totle=0;
  94.             int j=0;
  95.             //
  96.             for(Integer en:data.keySet()){
  97.                 if(f.equals("great")){
  98.                     totle+=weight[j++]*Math.exp(-ah*data.get(en)*GreatToOne(en,current));
  99.                 }
  100.                 else{
  101.                     totle+=weight[j++]*Math.exp(-ah*data.get(en)*LessToOne(en,current));
  102.                 }
  104.             }
  105.             j=0;
  106.             for(Integer en:data.keySet()){
  107.                 if(f.equals("great")){
  108.                     weight[j]=weight[j]*Math.exp(-ah*data.get(en)*GreatToOne(en,current))/totle;
  109.                 }
  110.                 else{
  111.                     weight[j]=weight[j]*Math.exp(-ah*data.get(en)*LessToOne(en,current))/totle;
  112.                 }
  113.                 j++;
  114.             }
  115.         result.put(ah, current);
  116.         list.add(f);
  117.         //错误率为零，则退出
  118.         if(calc(result,data)==0) break;
  119.         }
  120.     return result;
  121.     }
  122.     private int calc(Map<Double, Double> result, TreeMap<Integer, Integer> data) {
  123.         // TODO Auto-generated method stub
  124.         int count=0;
  126.         for(Integer en:data.keySet()){
  127.             double sum=0;int index=0;
  128.             for(Double d:result.keySet()){
  129.                 if(list.get(index).equals("great")){
  130.                     sum+=d*GreatToOne(en,result.get(d));
  131.                 }
  132.                 else{
  133.                     sum+=d*LessToOne(en,result.get(d));
  134.                 }   
  135.                 index++;            
  136.             }
  137.             if(sum>0&&data.get(en)==-1) {
  138.                 count++;
  139.             }
  140.             if(sum<0&&data.get(en)==1){
  141.                 count++;
  142.             }
  144.         }
  145.         if(count==0){
  146.             return 0;
  147.             }
  148.         else{
  149.             return 1;
  150.         }
  151.     }
  153.     public int GreatToOne(int x,double flag){
  154.         if(x>flag) {
  155.             return 1;
  156.         }else{
  157.             return -1;
  158.         }
  159.     }
  160.     public int LessToOne(int x,double flag){
  161.         if(x<flag) {
  162.             return 1;
  163.         }else{
  164.             return -1;
  165.         }
  166.     }
  167. }

结果如下：
这里写图片描述

统计学习方法（李航）

发表评论

表情：
评论列表 （有 0 条评论，298人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Adaboost算法

    Adaboost算法 集成学习概述 集成学习算法定义 集成学习(Ensemble learning)就是讲若干个弱分类器通过一定策略组合后产生一个强分类

    港控/mmm°港控/mmm°/ 0 赞/ 98 阅读