super关键字

子类override(覆盖)父类的函数

override时，使用super调用父类的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//超类，员工
class Employee{
    private String name;
    private double salary;//薪水
    private Date hireDay;
    public double getSalary(){
        return salary;
    }
}
//经理
class Manage extends Employee{
    private double bonus;//奖金
    public double getSalary(){//对原来的getSalary进行override
        return this.bonus + super.getSalary();//super调用父类的getSalary()方法
    }
}

super在构造器中的应用

1
2
3
4

public Manager(String n, double s, int year, int mouth, int day){
    super(n,s,year,mouth,day);//调用超类Employee中对应参数的构造器
    bonus = 0;
}

多态

一个对象变量可以指示多种实际类型的现象————多态（polymorphism） 在运行时自动选择调用那个方法的现象————动态绑定（dynamic binding）

例如：

Employee e = new Employee();
e = new Manage(); // is ok

此时，对象变量e也可以引用Manager的对象。

Manage boss = new Manage(...);
Employee[] staff = new Employee();

调用对象方法的执行过程

1. 编译器查看对象的声明类型和方法名。假设调用x.f(param)，且隐式参数x声明为C类的对象。编译器一一列举所有C类中名为f的方法和其超类中访问属性为public且名为f的方法。
2. 编译器查看调用方法时提供的参数类型。这个过程叫做重载解析（overloading resolution）
3. 如果是private方法、static方法、final方法或者构造器，那么编译器会准确地知道应该调用哪个方法（编译器可以在编译阶段就完成绑定），这种调用方式叫静态绑定(static binding)。与此对应的是，调用的方法依赖于隐式参数的实际类型（编译器在编译阶段不知道要调用哪个方法，直到运行时才能确定），并在运行时实现动态绑定。有一个很好的例子解释这两个概念——lingzhm-动态绑定
4. 程序运行时，若是动态绑定调用方法，那就先从本类中寻找，否则从超类中寻找。（每个类都有一个方法表method table）

阻止继承：final类和方法

不允许扩展（被继承）的类被称为final类。

例如下例子中的Executive类就不能有子类。

1
2
3

final class Executive extends Manager{
    ...
}

类中的方法也可以final,那么子类就不能覆盖这个方法。

1
2
3
4
5
6
7

class Employee{
    ...
    public final String getName(){
        return name;
    }
    ...
}

抽象类，abstract

用于表示某种很抽象的、上层的、更通用的类。例如图中的Person类。

• 一般来说，包含一个或多个抽象方法的类本身必须被声明为抽象的。
• 抽象类不能被实例化！

1
2
3
4
5
6
7
8

abstract class class Person{
    ...
    private String name;//人类共有的属性,是具体的属性
    public Person(String n){//具体的方法
        name=n;
    }
    public abstract String getDescription();//抽象方法
}

• 可以定义抽象类的对象变量，但只能引用非抽象子类的对象：

  Person p = new Student("Vince Vu","Economics");

照着书上写了abstract的demo

输出为：

Harry Hacker,an employee with a salary of 50000.00
Maria Morris,a student majoring in computer science

受保护访问，Protected

若超类的某个域被声明为protected,那么子类就可以直接访问这个protected域。

• private-仅本类可见
• public-所有类可见
• protected-对本包和所有子类可见
• 默认-对本包可见

之前的AdaBoostDTree的误差函数是指数型的。GBDT的误差函数是任意指定的。GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

GBDT的误差函数

• 紫色部分：之前学过的所有树的结果叠加
• 红色和蓝色部分：本轮学习的模型
• 将之前学习的树与本轮学习的模型叠加，就得到了本次的预测值

目标

1. 求函数h(x)的形式
2. 求h(x)的步长η

回归问题求解目标

对于回归（regression）问题，误差函数一般采用平方误差。即：

为了进一步求解，我们对上式进行taylor展开，即：

其中： - 左边一项\(err(S_n,y_n)\)是常量（因为\(S_n\)、\(y_n\)都已知） - 右边一项应该对s求导，并在sn这点取导数值（\(error=(s-y)^2\)求导之后得到\(2(s-y)\)）

那么，上式等于：

求h(x)

为了让上式最小化，那么貌似\(|h(x)|\)无穷大即可实现，这不科学！于是我们要对\(h(x)\)的大小进行限制（类似归一化）————加入惩罚项\((h(x_n))^2\)，即将上式变为：

而上式可变为：

其中的\((s_n-y_n)^2\)是常数，记为constant

那么新的目标就变为：用\(x_n\)和\(y_n-s_n\)做一个regression即可。即：

经过penalize一番折腾之后，h终于有个像模像样的形式了：即regression with residuals（残差）。

求步长η

需要求得一个η，使得下式最小化：

为了方便计算，我们将平方内的项取负：

上式的\(y_n-s_n\)即residuals（残差）.这是一个单变量的线性回归问题，其中输入是用gt转换后的数据，输出是残差(residual)。

GBDT算法

输出：\(\sum_t^T\alpha_t g_t(x)\)，即一堆权重\(\alpha_t\)和一堆决策树\(g_t(x)\) 步骤：

1）利用C&RT去学{x, yn-sn}，保留这一轮学出来的树gt(x)

2）再求{gt(x), residual}线性回归，最小化目标函数求出来ita

3）更新sn

学习足够多次数后，返回组合的GBDT。

添加样式支持

为了不吧原先的像是文件搞得太乱，这里，添加子集的样式文件。 首先，在样式文件的source文件夹下找到css文件夹，打开style.styl文件，在最后添加：

@import "_my/mycss";

新建自定义样式

找到样式文件夹css 新建_my文件夹，在其中新建mycss.styl文件，之后就可以按照stylus的格式自定义样式了。

设置toc浮动

给mycss.sty添加：

#toc
 line-height 1.2em
 font-size 0.8em
 backgroud-color #fff
 float right
 position fixed
 right 30em
 top 20em

存在的问题

暂不支持自相应。

参考文献

1. Hexo博客主题NexT使用自定义的CSS样式

本文主要总结了一些自己不太熟悉的概念。

对象与对象变量

Date birthday = new Date();

对象变量：birthday 对象：右边的部分

一个对象变量并没有实际包含一个对象，仅仅是引用一个对象。

可以显示地将对象变量设置为null，表明这个对象变量目前没有引用任何对象：

birthday = null;

隐式参数与显式参数

例，methodName()是类class1的方法，

calss class1{
int a;
    public void methodName(int b){
    this.a = b ;
}

• 显式参数(explicit)：括号里面的，例如double pName
• 隐式参数(implicit)：出现在方法名前的class1类对象 -- 关键词this表示隐式参数。例如this.a

封装

不能编写返回引用可变对象的访问器方法！例如：

class class1{
    private Date a;
    public Date get(){
        return Date a; //会破坏封装性！
    }
}

以上操作破坏了a的私有性。

改正方法：克隆（clone）

class class1{
    private Date a;
    public Date get(){
        return Date a.clone(); //使用clone()
    }
}

final实例域

class class1{
    private final String name;
}

final域的特征：

1. 构造对象时，必须初始化final
2. 后面操作中，不能再改动
3. 但并不等于常量！
4. 属于对象，并不是类！

static静态

static域

1. 每个类只能有一个static域

2. 同一类的所有对象共享一个static域

3. 即使没有对象，static域也存在。它属于类，不属于任何一个对象

   class Employee{ private static int nextId = 1; private int id; }

static常量

1. 如下例，在程序中，可以使用Math.PI来获取这个常量。

   public class Math{ public static final double PI = 3.14; }

static方法

Math.pow(x,a)

1. 不使用任何对象；
2. 不能操作实例域（即类内的非static方法和变量），因为它不能操作对象；
3. 可以访问自身类的static域；
4. 对象也可以调用static方法。

在下面两种情况使用静态方法：

1. 一个方法不需要访问对象；
2. 一个方法只需要访问类的static域。

工厂方法

工厂方法是静态方法的一种常见用途。 例如，NumberFormat使用工厂方法(而不是构造器)产生不同风格的格式对象。

NumberFormat a = NumberFormat.getSytleA();
NumberFormat b = NumberFormat.getStyleB();

main方法

public class Application{
    public static void main(String[] args){
        // construct objects here
    }
}

1. 每一个类可以有一个main方法，用来单元测试；
2. 多个类被调用时，只会执行一个main方法；

初始化块

构造对象时，先运行初始化块，才运行构造器主体部分。

class Employee{
    private static int nextId;
    private int id;
    //初始化块
    {
        id=nextId;
    }
}

如果对类的静态域进行初始化的代码比较复杂，就可以使用静态的初始化块：

static{
    Random generator = new Random();
    nextId = generator.nextId(10000);
}

类（！！！不是对象）第一次加载时，将会进行static域的初始化。

初始化数据域的三种方法

1. 在构造器中设置值
2. 在声明中赋值
3. 在初始化块中赋值

类的初始化顺序

对于静态变量、静态初始化块、变量、初始化块、构造器，它们的初始化顺序依次是（静态变量、静态初始化块）>（变量、初始化块）>构造器。

例如，

public class InitialOrderTest {   
    // 静态变量   
    public static String staticField = "静态变量";   
    // 变量   
    public String field = "变量";   
    // 静态初始化块   
    static {   
        System.out.println(staticField);   
        System.out.println("静态初始化块");   
    }   
    // 初始化块   
    {   
        System.out.println(field);   
        System.out.println("初始化块");   
    }   
    // 构造器   
    public InitialOrderTest() {   
        System.out.println("构造器");   
    }   
    public static void main(String[] args) {   
        new InitialOrderTest();   
    }   
}  

运行以上代码，我们会得到如下的输出结果：

静态变量
静态初始化块
变量
初始化块
构造器

对于继承的情况：

class Parent {   
    // 静态变量   
    public static String p_StaticField = "父类--静态变量";   
    // 变量   
    public String p_Field = "父类--变量";   
  
    // 静态初始化块   
    static {   
        System.out.println(p_StaticField);   
        System.out.println("父类--静态初始化块");   
    }   
  
    // 初始化块   
    {   
        System.out.println(p_Field);   
        System.out.println("父类--初始化块");   
    }   
  
    // 构造器   
    public Parent() {   
        System.out.println("父类--构造器");   
    }   
}   
  
public class SubClass extends Parent {   
    // 静态变量   
    public static String s_StaticField = "子类--静态变量";   
    // 变量   
    public String s_Field = "子类--变量";   
    // 静态初始化块   
    static {   
        System.out.println(s_StaticField);   
        System.out.println("子类--静态初始化块");   
    }   
    // 初始化块   
    {   
        System.out.println(s_Field);   
        System.out.println("子类--初始化块");   
    }   
  
    // 构造器   
    public SubClass() {   
        System.out.println("子类--构造器");   
    }   
  
    // 程序入口   
    public static void main(String[] args) {   
        new SubClass();   
    }   
}  

运行一下上面的代码，结果马上呈现在我们的眼前：

父类--静态变量
父类--静态初始化块
子类--静态变量
子类--静态初始化块
父类--变量
父类--初始化块
父类--构造器
子类--变量
子类--初始化块
子类--构造器

总得来说，是先静态后变量，先父类后子类

其他重点

1. 基于类的访问权限：一个方法可以访问所属类的所有私有数据。
2. java的值引用（基本数据类型、对象引用）
3. 如果类中提供了至少一个有参构造器，而没有无参构造器，则在构造无参对象时会出错。

Java类库中的GregorianCalendar类 （删除本节）

纪元

时间是用距离一个固定时间点的毫秒数表示的，这个点就是纪元(epoch)。

时间与日历

为了将时间与日历分开，标准Java类库分别包含两个类：

• Date类：用来表示时间点的类；
• GregorianCalendar类：用来表示公历法的类；（通过它还有一个扩展类——Calendar类，描述了日历的一般属性）

Date类

用来表示时间的类；

只有少量的方法，例如比较两个时间点before(),after()：

doday.before(birthday)

GregorianCalendar类

常见方法：

new GregorianCalendar()，构造新的对象，用于表示对象构造时的日期和时间；

例如:

 GregorianCalendar g1 = new GregorianCalendar();

new GregorianCalendar(1999,11,31)，提供年月日构造一个表示特定日期午夜的日历对象。（月份从0开始计数，11表示12月）

new GregorianCalendar(1991,Calendar.DECEMBER,31),与上等价

new GregorianCalendar(1991,Calendar.DECEMBER,31,23,59,59),设置时间

本文主要针对天池大数据竞赛之“O2O优惠券使用预测”的冠军队伍的思路和源码分析。在此感谢无私的前辈(诗人都藏在水底)[https://github.com/wepe/O2O-Coupon-Usage-Forecast]。

本文主要对模型训练xgb.py 做一些详细的分析。

文件：O2O-Coupon-Usage-Forecast/code/wepon/season one

xgb.py 训练xgboost模型，生成特征重要性文件，生成预测结果。单模型第一赛季A榜AUC得分0.798.

import包

首先作者import xgboost,因此我们需要安装一下它。

XGBoost是数据挖掘中用到一个新型的数据分析包，相对其它Boosting模型更加高效。

安装教程xgboost install on windows

导入数据

#将数据集导入
dataset1 = pd.read_csv('data/dataset1.csv')
dataset2 = pd.read_csv('data/dataset2.csv')
dataset3 = pd.read_csv('data/dataset3.csv')

dataset1、dataset2有56个特征，图是前十个。

dataset3有57个特征

#将dataset1的label列的-1都换成0
dataset1.label.replace(-1,0,inplace=True)
dataset2.label.replace(-1,0,inplace=True)

#删除重复项
dataset1.drop_duplicates(inplace=True)
dataset2.drop_duplicates(inplace=True)
dataset3.drop_duplicates(inplace=True)

将dataset1和dataset2连起来

dataset12 = pd.concat([dataset1,dataset2],axis=0)

dataset1_y赋值为dataset1的label列

dataset1_y = dataset1.label

删除dataset1的'user_id','label','day_gap_before','day_gap_after'字段，赋值给dataset1_x

dataset1_x = dataset1.drop(['user_id','label','day_gap_before','day_gap_after'],axis=1)  # 'day_gap_before','day_gap_after' cause overfitting, 0.77


dataset2_y = dataset2.label
dataset2_x = dataset2.drop(['user_id','label','day_gap_before','day_gap_after'],axis=1)
dataset12_y = dataset12.label
dataset12_x = dataset12.drop(['user_id','label','day_gap_before','day_gap_after'],axis=1)
dataset3_preds = dataset3[['user_id','coupon_id','date_received']]
dataset3_x = dataset3.drop(['user_id','coupon_id','date_received','day_gap_before','day_gap_after'],axis=1)

用shape属性来显示数据的格式

print dataset1_x.shape,dataset2_x.shape,dataset3_x.shape

若输出：(8618,36) 表示这个表格有8618行和36列的数据，其中dimensions[0]为8618，dimensions[1]为36

加载数据到xgboost

dataset1、dateset2、dateset3 为xgb的DMatrix

dataset1 = xgb.DMatrix(dataset1_x,label=dataset1_y)
dataset2 = xgb.DMatrix(dataset2_x,label=dataset2_y)
dataset12 = xgb.DMatrix(dataset12_x,label=dataset12_y)
dataset3 = xgb.DMatrix(dataset3_x)

参考文献xgboost入门与实战（原理篇）

设置参数

params={'booster':'gbtree',
        'objective': 'rank:pairwise',
        'eval_metric':'auc',
        'gamma':0.1,
        'min_child_weight':1.1,
        'max_depth':5,
        'lambda':10,
        'subsample':0.7,
        'colsample_bytree':0.7,
        'colsample_bylevel':0.7,
        'eta': 0.01,
        'tree_method':'exact',
        'seed':0,
        'nthread':12
        }

训练模型

model = xgb.train(params,dataset12,num_boost_round=3500,evals=watchlist)    

预测测试集

dataset3_preds['label'] = model.predict(dataset3)
dataset3_preds.label = MinMaxScaler().fit_transform(dataset3_preds.label)
dataset3_preds.sort_values(by=['coupon_id','label'],inplace=True)
dataset3_preds.to_csv("xgb_preds.csv",index=None,header=None)
print dataset3_preds.describe()

保存特征评分

feature_score = model.get_fscore()
feature_score = sorted(feature_score.items(), key=lambda x:x[1],reverse=True)
fs = []
for (key,value) in feature_score:
    fs.append("{0},{1}\n".format(key,value))

with open('xgb_feature_score.csv','w') as f:
    f.writelines("feature,score\n")
    f.writelines(fs)

总结

这次算是对自己之前的各种理论知识进行了一次梳理，感觉平时过于注重算法的研究，并没有注意到宏观上的操作。以后要多加注意

感觉自己还是太渣，看了些许算法，并不知道有什么卵用。决定好好分析分析别人的思路，也许能够对我带来些许启发。

本文主要针对天池大数据竞赛之“O2O优惠券使用预测”的冠军队伍的思路和源码分析。在此感谢无私的前辈(诗人都藏在水底)[https://github.com/wepe/O2O-Coupon-Usage-Forecast]。

本文主要对数据的抽取extract_feature.py做一些详细的分析。

解决方案概述

本赛题提供了用户线下消费和优惠券领取核销行为的纪录表，用户线上点击/消费和优惠券领取核销行为的纪录表，记录的时间区间是2016.01.01至2016.06.30,需要预测的是2016年7月份用户领取优惠劵后是否核销。根据这两份数据表，我们首先对数据集进行划分，然后提取了用户相关的特征、商家相关的特征，优惠劵相关的特征，用户与商家之间的交互特征，以及利用本赛题的leakage得到的其它特征（这部分特征在实际业务中是不可能获取到的）。最后训练了XGBoost，GBDT，RandomForest进行模型融合。

源码分析

第二赛季暂时没有平台，所以本文只对第一赛季的源码进行分析。

文件：O2O-Coupon-Usage-Forecast/code/wepon/season one

这个文件夹存放第一赛季的代码 - extract_feature.py划分数据集，提取特征，生成训练集（dataset1和dataset2）和预测集（dataset3）。 - xgb.py 训练xgboost模型，生成特征重要性文件，生成预测结果。单模型第一赛季A榜AUC得分0.798.

import概述

分析对象：extract_feature.py

import包概述

1
2
3

import pandas as pd
import numpy as np
from datetime import date

pandas

Pandas 是基于 NumPy (因此还要import numpy) 的一个非常好用的库，正如名字一样，人见人爱。之所以如此，就在于不论是读取、处理数据，用它都非常简单。Pandas提供了很多处理大数据的方法。我想是因为此，原作者才采用了它。

Pandas 有两种自己独有的基本数据结构。Series 和 DataFrame，它们让数据操作更简单了。

两种结构的属性和方法不再多阐述。见两份很好的参考文档：

1. Pandas 使用
2. 十分钟搞定pandas
3. 在Python中利用Pandas库处理大数据的简单介绍
4. pandas官方文档
5. pandas常见方法，中文

大概知道了import包的内容后，我们正式开始看源码。

注意

1. 读取之前，请先把数据的表头项删除（也就是第一行的string）

读取数据集

总结：

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#1754884 record,1053282 with coupon_id,9738 coupon. date_received:20160101~20160615,date:20160101~20160630, 539438 users, 8415 merchants

off_train = pd.read_csv('data/ccf_offline_stage1_train.csv',header=None)
off_train.columns = ['user_id','merchant_id','coupon_id','discount_rate','distance','date_received','date']

#2050 coupon_id. date_received:20160701~20160731, 76309 users(76307 in trainset, 35965 in online_trainset), 1559 merchants(1558 in trainset)

off_test = pd.read_csv('data/ccf_offline_stage1_test_revised.csv',header=None,nrows=3000)
off_test.columns = ['user_id','merchant_id','coupon_id','discount_rate','distance','date_received']

#11429826 record(872357 with coupon_id),762858 user(267448 in off_train)

on_train = pd.read_csv('data/ccf_online_stage1_train.csv',header=None,nrows=47000)
on_train.columns = ['user_id','merchant_id','action','coupon_id','discount_rate','date_received','date']

读数据主要用了pandas的read_cvs方法. 为了快捷分析，我们限定只读取数据集的前7w、3k、47w行

采集特征

主要特征

总结：

这是滑窗的方法得到多份训练数据集，特征区间越小，得到的训练数据集越多。划分方式：

上面这个表格很清晰地说明了原作者划分数据的方法.

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#dataset3存放table3 的数据
dataset3 = off_test 

#feature3存放：筛出off_train中，以下四种情况：
#消费日期data在20160315-20160630的，
#或消费日期为空且领券日期在20160315-20160630的，
feature3 = off_train[
((off_train.date>='20160315')&(off_train.date<='20160630'))
|((off_train.date=='null')&(off_train.date_received>='20160315')&(off_train.date_received<='20160630'))]

#dataset2存放：从off_train筛出：领券时期在20160515-20160615之间的
dataset2 = off_train[
(off_train.date_received>='20160515')&off_train.date_received<='20160615')]

#feature2存放：从off_train筛出：
#消费日期在20160201-20160514的，
#或领券日期在20160201-20160514但没有消费的
feature2 = off_train[(off_train.date>='20160201')&(off_train.date<='20160514')|((off_train.date=='null')&(off_train.date_received>='20160201')&(off_train.date_received<='20160514'))]

#dataset1存放：从off_train筛出： 领券日期在20160414-20160514的
dataset1 = off_train[(off_train.date_received>='20160414')&(off_train.date_received<='20160514')]

#feature1存放：从off_train筛出：
#消费日期在20160101-20160413的，或
#领券日期在20160101-20160413但没有消费的
feature1 = off_train[(off_train.date>='20160101')&(off_train.date<='20160413')|((off_train.date=='null')&(off_train.date_received>='20160101')&(off_train.date_received<='20160413'))]

其他特征

other_feature3

文件名：data/other_feature3.csv

格式：user_id,coupon_id,this_month_user_receive_same_coupon_count,this_month_user_receive_all_coupon_count,date_received,this_month_user_receive_same_coupon_lastone,this_month_user_receive_same_coupon_firstone,this_day_user_receive_all_coupon_count,this_day_user_receive_same_coupon_count,day_gap_before,day_gap_after

解释：用户id,优惠券id,本月用户使用本券次数，本月用户使用所有券次数，使用时间，本月用户使用本券末次时间、首次时间，本日用户用券总数，本日用户用本券总数，上次用本券间隔，下次用本券间隔

源码分析

t:计算每个用户使用优惠券的总次数：

1
2
3
4
5
6
7

#将测试集dataset3的userid存在t中
t = dataset3[['user_id']]
#给t添加一个列，列名是this_month_user_receive_all_coupon_count，值都是1
t['this_month_user_receive_all_coupon_count'] = 1
#按照user_id分组，将user_id重复的项目的this_month_user_receive_all_coupon_count相加，然后进行reset_index
#其实就是算出每个用户使用优惠券的总次数
t = t.groupby('user_id').agg('sum').reset_index()

t1:统计每个用户，使用不同优惠券的次数：

1
2
3
4
5

t1 = dataset3[['user_id','coupon_id']]
t1['this_month_user_receive_same_coupon_count'] = 1
#按照user_id和coupon_id进行分组
#统计每个用户，使用不同优惠券的次数
t1 = t1.groupby(['user_id','coupon_id']).agg('sum').reset_index()

t2:找出每个人，消费每个券的时间，并用冒号分隔例如：

1
2
3
4
5

t2 = dataset3[['user_id','coupon_id','date_received']]
t2.date_received = t2.date_received.astype('str')
# 按照user_id','coupon_id排序后，提出来date_received，进行agg运算
# agg运算：用冒号连接起来
t2 = t2.groupby(['user_id','coupon_id'])['date_received'].agg(lambda x:':'.join(x)).reset_index()

t2:每个用户使用某张优惠券（使用次数大于1次）的首次和末次使用时间

1
2
3
4
5
6
7
8
9
10

#apply会返回每个优惠券的使用次数
t2['receive_number'] = t2.date_received.apply(lambda s:len(s.split(':')))
#筛出使用次数大于1次的数据
t2 = t2[t2.receive_number>1]
#对max_date_received赋值为最近一次的使用时间
t2['max_date_received'] = t2.date_received.apply(lambda s:max([int(d) for d in s.split(':')]))
#对min_date_received赋值为最早一次的使用时间
t2['min_date_received'] = t2.date_received.apply(lambda s:min([int(d) for d in s.split(':')]))
# 重新定义t2为以下项目
t2 = t2[['user_id','coupon_id','max_date_received','min_date_received']]

t3:每个用户使用优惠券的时间、本次优惠券与首次使用的间隔、末次使用的间隔

1
2
3
4
5
6
7
8
9
10
11
12
13

t3 = dataset3[['user_id','coupon_id','date_received']]
#merge，将两个数据集合并
#将t2和t3在['user_id','coupon_id']上进行左帧合并，即根据t3合并t2的user_id','coupon_id
#t2[['user_id','coupon_id','max_date_received','min_date_received']]
#t3[['user_id','coupon_id','date_received']]
#因此合并方式为：找到每个用户每张优惠券的消费时间和对应券的max_date_received与min_date_received
t3 = pd.merge(t3,t2,on=['user_id','coupon_id'],how='left')
#t3的this_month_user_receive_same_coupon_lastone项目设置为:此用户消费本张优惠券与最近一次消费本张优惠券的间隔

t3 = t3.apply(pd.to_numeric, args=('coerce',))
t3['this_month_user_receive_same_coupon_lastone'] = t3.max_date_received - t3.date_received
#此用户消费本张优惠券与第一次消费本张优惠券的间隔
t3['this_month_user_receive_same_coupon_firstone'] = t3.date_received - t3.min_date_received

上面跑到t3['this_month_user_receive_same_coupon_lastone'] = t3.max_date_received - t3.date_received的时候会出现TypeError: unsupported operand type(s) for -: 'float' and 'str'.

在执行这句话之前，我们看到t3.date_received的类型为

因此我们需要将数据类型先转换为float。在网上查到本方法对本代码有效（暂不知原因）。参考文献

t3 = t3.apply(pd.anumeric, args=('coerce',))

把这句话加上后，我们看到

定义函数is_firstlastone判断优惠券是否是末次使用

1
2
3
4
5
6
7

def is_firstlastone(x):
    if x==0:
        return 1
    elif x>0:
        return 0
    else:
        return -1 #those only receive once

t3:加上两个数据，...

1
2
3

t3.this_month_user_receive_same_coupon_lastone = t3.this_month_user_receive_same_coupon_lastone.apply(is_firstlastone)
t3.this_month_user_receive_same_coupon_firstone = t3.this_month_user_receive_same_coupon_firstone.apply(is_firstlastone)
t3 = t3[['user_id','coupon_id','date_received','this_month_user_receive_same_coupon_lastone','this_month_user_receive_same_coupon_firstone']]

后面套路差不多，此处不再继续分析。主要结论已经总结在上表中。 # 合并特征

生成训练集

coupon2 = pd.read_csv('data/coupon2_feature.csv')
merchant2 = pd.read_csv('data/merchant2_feature.csv')
user2 = pd.read_csv('data/user2_feature.csv')
user_merchant2 = pd.read_csv('data/user_merchant2.csv')
other_feature2 = pd.read_csv('data/other_feature2.csv')
#dataset2是根据 优惠券特征 合并商户、用户、用户-商户、其他特征
dataset2 = pd.merge(coupon2,merchant2,on='merchant_id',how='left')
dataset2 = pd.merge(dataset2,user2,on='user_id',how='left')
dataset2 = pd.merge(dataset2,user_merchant2,on=['user_id','merchant_id'],how='left')
dataset2 = pd.merge(dataset2,other_feature2,on=['user_id','coupon_id','date_received'],how='left')
dataset2.drop_duplicates(inplace=True)
print dataset2.shape
dataset2.user_merchant_buy_total = dataset2.user_merchant_buy_total.replace(np.nan,0)
dataset2.user_merchant_any = dataset2.user_merchant_any.replace(np.nan,0)
dataset2.user_merchant_received = dataset2.user_merchant_received.replace(np.nan,0)
dataset2['is_weekend'] = dataset2.day_of_week.apply(lambda x:1 if x in (6,7) else 0)
weekday_dummies = pd.get_dummies(dataset2.day_of_week)
weekday_dummies.columns = ['weekday'+str(i+1) for i in range(weekday_dummies.shape[1])]
dataset2 = pd.concat([dataset2,weekday_dummies],axis=1)
dataset2['label'] = dataset2.date.astype('str') + ':' +  dataset2.date_received.astype('str')
dataset2.label = dataset2.label.apply(get_label)
dataset2.drop(['merchant_id','day_of_week','date','date_received','coupon_id','coupon_count'],axis=1,inplace=True)
dataset2 = dataset2.replace('null',np.nan)
dataset2.to_csv('data/dataset2.csv',index=None)


coupon1 = pd.read_csv('data/coupon1_feature.csv')
merchant1 = pd.read_csv('data/merchant1_feature.csv')
user1 = pd.read_csv('data/user1_feature.csv')
user_merchant1 = pd.read_csv('data/user_merchant1.csv')
other_feature1 = pd.read_csv('data/other_feature1.csv')
dataset1 = pd.merge(coupon1,merchant1,on='merchant_id',how='left')
dataset1 = pd.merge(dataset1,user1,on='user_id',how='left')
dataset1 = pd.merge(dataset1,user_merchant1,on=['user_id','merchant_id'],how='left')
dataset1 = pd.merge(dataset1,other_feature1,on=['user_id','coupon_id','date_received'],how='left')
dataset1.drop_duplicates(inplace=True)
print dataset1.shape

dataset1.user_merchant_buy_total = dataset1.user_merchant_buy_total.replace(np.nan,0)
dataset1.user_merchant_any = dataset1.user_merchant_any.replace(np.nan,0)
dataset1.user_merchant_received = dataset1.user_merchant_received.replace(np.nan,0)
dataset1['is_weekend'] = dataset1.day_of_week.apply(lambda x:1 if x in (6,7) else 0)
weekday_dummies = pd.get_dummies(dataset1.day_of_week)
weekday_dummies.columns = ['weekday'+str(i+1) for i in range(weekday_dummies.shape[1])]
dataset1 = pd.concat([dataset1,weekday_dummies],axis=1)
dataset1['label'] = dataset1.date.astype('str') + ':' +  dataset1.date_received.astype('str')
dataset1.label = dataset1.label.apply(get_label)
dataset1.drop(['merchant_id','day_of_week','date','date_received','coupon_id','coupon_count'],axis=1,inplace=True)
dataset1 = dataset1.replace('null',np.nan)
dataset1.to_csv('data/dataset1.csv',index=None)

生成预测集

coupon3 = pd.read_csv('data/coupon3_feature.csv')
merchant3 = pd.read_csv('data/merchant3_feature.csv')
user3 = pd.read_csv('data/user3_feature.csv')
user_merchant3 = pd.read_csv('data/user_merchant3.csv')
other_feature3 = pd.read_csv('data/other_feature3.csv')
dataset3 = pd.merge(coupon3,merchant3,on='merchant_id',how='left')
dataset3 = pd.merge(dataset3,user3,on='user_id',how='left')
dataset3 = pd.merge(dataset3,user_merchant3,on=['user_id','merchant_id'],how='left')
dataset3 = pd.merge(dataset3,other_feature3,on=['user_id','coupon_id','date_received'],how='left')
dataset3.drop_duplicates(inplace=True)
print dataset3.shape

dataset3.user_merchant_buy_total = dataset3.user_merchant_buy_total.replace(np.nan,0)
dataset3.user_merchant_any = dataset3.user_merchant_any.replace(np.nan,0)
dataset3.user_merchant_received = dataset3.user_merchant_received.replace(np.nan,0)
dataset3['is_weekend'] = dataset3.day_of_week.apply(lambda x:1 if x in (6,7) else 0)
weekday_dummies = pd.get_dummies(dataset3.day_of_week)
weekday_dummies.columns = ['weekday'+str(i+1) for i in range(weekday_dummies.shape[1])]
dataset3 = pd.concat([dataset3,weekday_dummies],axis=1)
dataset3.drop(['merchant_id','day_of_week','coupon_count'],axis=1,inplace=True)
dataset3 = dataset3.replace('null',np.nan)
dataset3.to_csv('data/dataset3.csv',index=None)

附录

查看dataFrame类型的内容

见pandas 文档之 10 minutes to pandas --- viewing data

用t.values,t.columns

lambda functions

源代码中有一行t2.groupby(['user_id','coupon_id'])['date_received'].agg(lambda x:':'.join(x)).reset_index()

官方文档

lambda functions是python的一个function. 用例：

#函数f(x)
>>> def f(x):
...     return x*2
...
>>> f(3) #输入x=3     
6 #输出6

#f(x)等价于：
>>> g = lambda x: x*2  1
>>> g(3)
6
#f(x)还等价于：
>>> (lambda x: x*2)(3) 2
6

作者代码中，有一行
lambda x:':'.join(x)即将前后叠加,用:连接 t2.groupby(['user_id','coupon_id'])['date_received'].agg(lambda x:':'.join(x)).reset_index()意思是将数据集先按照user_id','coupon_id排序，然后对date_received进行用:连接一起来

例如，输入：

1
2
3
4
5
6

df = pd.DataFrame({'A' : ['foo', 'bar', 'foo', 'bar',
                            'foo', 'bar', 'foo', 'foo'],
                            'B' : ['one', 'one', 'two', 'three',
                             'two', 'two', 'one', 'three'],
                            'C' : np.random.randn(8),
                            'D' : np.random.randn(8)})

df3 = df.groupby(['A'])['B'].agg(lambda x:':'.join(x)).reset_index()

输出：

pandas的merge的how参数

原代码出现了t3 = pd.merge(t3,t2,on=['user_id','coupon_id'],how='left')

how参数主要决定了哪一个keys会被包含在结果表中。它的值有四种可能性：left,right,outer,inner。我们主要看left和right

how='left':遍历left表，找与right一样的，依次放入行。 如果没有，则设为NAN

因此t3 = pd.merge(t3,t2,on=['user_id','coupon_id'],how='left')的意思是：

根据t3合并t2的user_id','coupon_id

上一节中介绍了《随机森林算法》，该算法使用bagging的方式作出一些决策树来，同时在决策树的学习过程中加入了更多的随机因素。该模型可以自动做到验证过程同时还可以进行特征选择。

本节，我们结合AdaBoost+决策树算法。

AdaBoost决策树算法引入

在AdaBoost中每一轮迭代，都会给数据更新一个权重，利用这个权重，我们学习得到一个g，在这里我们得到一个决策树，最终利用线性组合的方式得到多个决策树组成的G。

======================================= AdaBoost-DTree(DD) 对于t=1,2,…,T，循环执行：

• 更新数据的权重\(u(t)\)；
• 通过决策树算法\(DTree(D,u(t))\)得到\(g_t\)；
• 计算\(g_t\)的投票权重\(α_t\)。

返回\(G=LinearHypo({(g_t,α_t)})\)。

========================================

问题：如何要在决策树中，加入权重ut

解决方案有两种：

• 一种是通过算法加权，在计算Ein的地方嵌入权重计算，比如AdaBoost采用的最小化加权误差；
• 另一种方法是将算法当成黑盒不变更，通过数据集加权，根据权重在bootstrap时“复制”数据，也就是加权的重采样。

AdaBoost决策树通常用后一种，即：$AdaBoost+sampling∝u^{(t)}+DTree(D_t) $

加权的决策树算法(Weighted Decision Tree Algorithm)

之前含有权重的算法中，我们在误差估计中加入了权重u：

为了对决策树中加入权重，且不改变原算法的健壮性，我们设法对输入的数据进行权重加成。而权重等效于数据的重复次数。根据这种方式得到一组新的数据，那么这组新的数据中的比例大概就是和权重的比例呈正比的，也就是说它能够表达权重对于数据的意义。

在AdaBoost-DTree中，为了简单起见，我们不去改变AdaBoost的框架，也不去修改决策树的内部细节，而只是通过基于权重的训练数据的采样来实现。

即如下图所示的：AdaBoost提升决策树=AdaBoost提升+关于权重u的数据抽样+决策树

弱决策树算法

在AdaBoost算法中，我们通过错误率εt来计算单个的g的权重αt，那么如果我们使用决策树作为g的时候，g是一个完全长成的树，该树对整个数据集进行细致的切分导致Ein=0，那么这使得εt=0，但计算得到的权重αt会变成无限大。

其意义是，如果使用一个能力很强的树作为g的话，那么该算法会赋予该树无限大的权重或票数，最终得到了一棵“独裁”的树（因为AdaBoost的哲学意义是庶民政治，就是集中多方的意见，及时有的意见可能是错误的），违背了AdaBoost的宗旨。

上面的问题出在使用了所有的数据和让树完全长成这两方面。针对这两个问题，我们要通过剪枝和部分训练数据得到一个弱一点的树。 所以实际上，AdaBoost-DTree是通过sampling的方式得到部分训练数据，通过剪枝的方式限制树的高度，得到弱一点的决策树。

下面介绍最弱的决策树。

决策桩，AdaBoost-Stump

什么样是树才是弱决策树呢？ 我们这里限制这棵树只有一层（即它仅基于单个特征来做决策），即决策桩(Decision Stump)。这样我们需要让CART树的不纯度(impurity)尽可能低，学习一个决策桩。

所以，使用决策桩作为弱分类器的AdaBoost称为AdaBoost-Stump，它是一种特殊的AdaBoost-DTree。

决策桩的实现

本节主要参考《机器学习实战》p120

实验数据adaboost.py

from numpy import *
def loadSimpData():
    dataMat = matrix([[1.,2.1],[2.,1.1],[1.3,1.],[1.,1.],[2.,1.]])
    classLabels = [1.0,1.0,-1.0,-1.0,1.0]
    return dataMat,classLabels

二分类的决策桩实现stump.py

先导入数据

import adaboost
dataMat,classLabels = adaboost.loadSimpData()

建立一个buidStump()函数，根据数据集，建立最佳单层决策树（只需要选择一个最好的特征即可）

def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr)
    labelMat = mat(classLabels).T # T是做转置

dataMatrix形式为 labelMat形式为

先令一些变量，之后解释。

    m,n = shape(dataMatrix)
    numSteps = 10.0#步长
    bestStup = {}#最佳桩
    bestClasEst = mat(zeros((m,1)))#最佳分类est
    minError = inf

接下来需要对每个特征计算出一个阈值threshVal，根据阈值二分类。

for i in range(n): # 遍历特征个数
    #为了确定threshVal，我们从本特征下的最小值到最大值分10 step进行依次测试
    rangeMin = dataMatrix[:,i].min();rangeMax = dataMatrix[:,i].max();
    stepSize = (rangeMax - rangeMin)/numSteps
    #下面对每个threshVal可能的值进行依次测试
    for j in range(-1,int(numSteps)+1):
        #然后应该开始比较大于阈值和小于阈值怎么怎么滴，为了增加代码的复用性，此处用一个循环来在大于和小于之间切换不等式
        for inequal in ['lt','gt']:#lt=小于等于，gt=大于
            threshVal = (rangeMin + float(j)*stepSize)
            # 开始测试这个特征下这个阈值的二分类器好不好用
            predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)
            #计算本次分类的err
            errArr = mat(ones((m,1)))
            errArr[predictedVals==labelMat]=0
            #基于权重向量D计算权重
            weightedError = D.T*errArr
            if weightedError < minError :
                minError = weightedError
                bestClasEst = predictedVals.copy()
                bestStump['dim'] = i
                bestStump['thresh'] = threshVal
                bestStump['ineq'] = inequal

最后，返回最佳的决策桩，和误差

return bestStump,minError,bestClasEst

求解AdaBoost决策树

AdaBoost的权重与投票分数的关系

回顾AdaBoost算法：

从权重ut，通过◆t对u(t+1)进行修正，而两个公式可以合成为：

如下图，接着我们将u(t+1)展开(表达为u(1)乘以一坨)，最终可以变成连加； 我们发现图中橘色部分∑αt·gt(xn)是G(x)的分数！它现在出现在Adaboost的权重表达式中； 我们称橘色∑αt·gt(xn)为投票分数(voting score)：

结论：AdaBoost里面每一个数据的权重，和exp(-yn( 投票分数 on xn))呈正比。即：

投票分数(Voting Score)和间隔(Margin)的关系

线性混合(linear blending)等价于将假设看做是特征转换的线性模型：

其中αt·gt(xn)如果换作是wT·φ(xn)可能就更清楚了，这与下面给出的在SVM中的margin表达式对比，我们可以明白投票分数∑αt·gt(xn)的物理意义，即可以看做是没有正规化的边界(margin)。

所以，yn·(voting score)是有符号的、没有正规化的边界距离，从这个角度来说，我们希望yn·(voting score)越大越好，因为这样的泛化能力越强。于是，exp(-yn·(voting score))越小越好，那么un(T+1)越小越好。

结论：AdaBoost在迭代过程中，是让∑un(t)越来越小的过程，在这个过程中，逐渐达到SVM中最大分类间隔的效果。

AdaBoost误差函数

上面解释到了，AdaBoost在迭代学习的过程，就是希望让∑un(t)越来越小的过程，那么我们新的目标就是最佳化权重和∑un(T+1)：

我们可以画出0/1错误和AdaBoost误差函数err(s,y) = exp(-ys)的函数曲线，我们发现AdaBoost的误差函数（称为exponential error measure）实际上也是0/1错误函数的上限函数，于是，我们可以通过最小化该函数来起到最佳化的效果。

AdaBoost误差函数的梯度下降求解

本节目的————最小化AdaBoost的误差函数Ein：

这个任务比较麻烦，因为是Σ套着exp再套着Σ，因此需要一些前人的智慧了。

我们可以将Ein函数在所在点的附近做泰勒展开，我们就可以发现在该点的附近可以被梯度所描述，我们希望求一个最好的方向（最大梯度相反的方向），然后在该方向上走一小步，这样我们就可以做到比现在的函数效果好一点点，依次进行梯度下降，最终达到最小化误差函数的效果。

原始的梯度下降法：

为了模仿梯度下降的方法，假设前面已经AdaBoost完t-1轮了，现在要求的是一个函数gt(x)（或者称为h(x)）。

在第t轮，我们沿着函数h(x)的方向走\(η\)的步长，可以使得目标函数迅速往min的方向走。如下：现在我们把函数gt当做向量，希望去找到这个gt（这里函数方向gt和上面介绍的最大梯度的方向向量没有什么差别，只是表示方式有所不同而已）。

我们解释一下上面的公式：

• (1、2行)由于前面已经执行完了t-1轮，因此可以把式子化简一下，把一些项目合并成ut的函数形式
• (3行左) 将exp(-y·η·h(xn))在原点xn=0点的泰勒展开，进一步化简得到得到(1-yn·η·h(xn))；（这里为什么要用0这个位置的taylor展开呢，可以理解成h(x)只是沿着原来的Σ1,t-1(alphat*g'(xn)这个函数，挪动的了一小步；这一小步，就意味着变化很小，变化很小甚至接近0，因此就可以在0点taylor展开。不晓得这种理解是否正确，意会吧）
• (3行右) 然后拆成两部分∑un(t)和η·∑un(t)·yn·h(xn)，第一部分是Ein，第二部分就是要最小化的目标。

到此，我们利用前人的智慧已经把目标函数给大大简化了，下面需要要求的东西有俩：

1）h(x)是啥？

2）$η$是啥？

求h(x)

我们对∑un(t)·yn·h(xn)整理一下，对于二元分类情形，我们把yn和h(xn)是否同号进行分别讨论：

上面的公式中，我们特意将∑un(t)·yn·h(xn)拆成-∑un(t)和Ein(h)的形式，这里最小化Ein对应于AdaBoost中的A（弱学习算法），好的弱学习算法就是对应于梯度下降的函数方向。

结论：在AdaBoost的过程中，算法A就是good gt了！

求最佳化步长\(η\)

我们要最小化Eada，需要找到好的函数方向gt，但是得打这个gt的代价有些大，梯度下降的过程中，每走一小步，就需要计算得到一个gt。如果转换一下思路，我们现在已经确定了好的gt，我们希望快速找到梯度下降的最低点，那么我们需要找到一个合适的最大步长η。

我们这里使用贪心算法来得到最大步长η，称为steepest decent for optimization。

让Eada对η求偏微分，得到最陡时候的ηt，我们发现这时ηt等于AdaBoost的αt。所以在AdaBoost中αt是在偷偷地做最佳化的工作。

核心在于EADA是怎么变成可对\(η\)求导的形式的：

EADA = u1texp(-\(η\)) + u2texp(\(η\))...

EADA1 = u1texp(-\(η\)) + ut2t0 ... （EADA1只考虑exp(-\(η\))的项，其余的补上0）

EADA2 = u1t0 + u2t exp(\(η\)) ...（EADA2只考虑exp(+\(η\))的项，其余的补上0）

则，EADA = EADA1 + EADA1 = (Σunt) * ( (1-epson)exp(-\(η\)) + epson*exp(\(η\)) )

随后的求导步骤就是很自然的了，因此就验证了之前的结论，\(η\)t = sqrt( (1-epsont)/epsont) )就是最优的。前一次课直接给出了这个结论，并没有说为什么，这次算是给出了一个相对理论些的推导。

结论：通过求解 ，我们得到最佳的

小结

在第二小节中，我们从另外一个角度介绍了AdaBoost算法，它其实是steepest gradient decent。

上面的式子很清楚了，我们将AdaBoost的误差函数看做是指数误差函数，AdaBoost就是在这个函数上一步一步做最佳化，每一步求得一个h，并将该h当做是gt，决定这个gt上面要走多长的距离ηt，最终得到这个gt的票数αt。

AdaBoost决策树总结

1. AdaBoost本次的u(t+1)与exp(-yn( 投票分数 on xn))成正比
2. AdaBoost在迭代过程中，是让∑un(t)越来越小的过程，在这个过程中，逐渐达到SVM中最大分类间隔的效果
3. 上目标与最小化误差函数err(s,y) = exp(-ys)等价
4. 要使得err(s,y)最小，就需要求得h(x)和η

参考文献

1. 梯度提升决策树
2. 【Gradient Boosted Decision Tree】林轩田机器学习技术
3. 《机器学习实战》

Boosting

提升（boosting）：从弱学习算法（正确率低）出发，反复学习，得到一系列弱分类器（基本分类器），然后组合这些弱分类器，构成一个强分类器。（三个臭皮匠顶个诸葛亮）

提升（boosting）方法需要解决的问题： - 如何获得更多的弱分类器————如何改变训练数据的权值或概率分布————提高被前一轮错误分类样本的权值，降低被正确分类样本的权值。 - 如何将弱分类器合成一个强分类器————加权多数表决：加大误差小的分类器的权值，减小误差大的分类器的权值。

提升方法有很多，最具代表性的就是AdaBoost算法。

AdaBoost算法

假设给定一个二分类训练数据集\(T=\\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\\}\)

其中，每个样本点由【特征+标签】组成

特征：$x_iX R^n $

标签：\(y_i \in Y={-1,+1}\)

AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成一个强分类器

输入:

• 数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}\)
• 弱学习算法

输出：最终分类器\(G(x)\)

步骤： 1. 初始化训练数据的权值(每个都设为1/N)： \[D_1=(w_{11},w_{1i},...,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,...,N\] 其中\(w_{ki}\) 代表迭代第k次时，第i个样本被抽到的概率！！！ 2. 对\(m=1,2,...,M\): 使用带权值\(D_m\)的训练集学习，得到基本分类器\(G_m(x):X\rightarrow \\{-1,+1\\}\) 计算\(G_m(x)\)在训练集上的分类误差率：\[e_m=P(G_m(x_i)\neq y_i)=\sum_{n=1}^N w_{mi}I(G_m(x_i)\neq y_i)\] 3. 计算\(G_m(x)\)的系数：\[\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}\] 4. 更新训练集权值： 5. 将上面迭代k次后，得到M个基本分类器。构建基本分类器的线性组合：

AdaBoost详解

Boot strapping

Boot strapping，拔靴法：利用有限的样本资料经由多次重复抽样，重新建立起足以代表母体样本分布之新样本。

多次之后，得到一个非线性的结果（黑色线）

基本算法引入权重

已知：一笔数据\(D={(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)}\)。根据D算出来的输入误差Ein为：

通过Boot strapping，得到新的一笔数据\(D_t={(x_1,y_1),(x_1,y_1),(x_2,y_2),(x_4,y_4)}\)。对应地，根据Dt算出来的Ein为：（增加一个权重u即可）

\(u1=2,u2=1,u3=0,u4=1\)

结论：每一个bootstrapping得到了一个权重u

优化权重u

优化原理

• 每一个bootstrapping得到了一个权重u。
• 为了综合得到更好的g,则需要抽取的数据集得到的g尽量地不同。
• 改变u，使得g差异更大，才会更好地改进最终结果

得到g差异很大的方法：

• 第一轮\(u_n^t\)时，得到\(g_t\)
• 第二轮，选择一个 在\(g_t\) 表现不好的 \(u_n^{t+1}\) ，得到 \(g_{t+1}\) -- 表现不好的定义： --- 将\(u_n^{t+1}\)作用在\(g_t\)上，得到一个归一化的错误率 --- 为了简便，定义橙色方块为所有犯错误的\(u_n^{t+1}\)的累加，绿色圆形为所有正确的\(u_n^{t+1}\)累加 --- 即： -- 表现不好的选择方法： --- 将本次正确的\(u_n^t\)，除以一个错误的比例（缩小正确），赋给\(u_n^{t+1}\) --- 将本次错误的\(u_n^t\)，乘以一个正确的比例（放大错误），赋给\(u_n^{t+1}\) --- 这样得到的\(u_n^{t+1}\)的比率就会为2/1 --- 即：

优化权重u的方法————放缩因子

放缩因子-Adaptive Boosting Algorithm - ◆t有更清晰的物理意义，通常情况下εt < 1/2（因为是学习之后的结果，错误率应该小于0.5）， - ◆t将大于1； - 那么，犯错的数据将乘上大于1的数，正确数据将除以大于1的数 - 使得提升了犯错数据的权重(scale up incorrect)， - 降低做对数据的权重(scale down correct) - 这样使得更加专注在犯了错的地方，来得到不一样的假设(diverse hypotheses)。

Linear Aggregation（聚集） - 合成最终的g

目标：合成最终的的\(G(x)=sign(\sum_{t=1}^T\alpha_t g_t(x)\) - 其中 \(\alpha_t\)是系数 - 要求好的\(g_t\)（错误率低），\(\alpha_t\)应该大一些 - 坏的\(g_t\)（错误率高），\(\alpha_t\)应该小一些 - 而◆t与错误率成反比 - 则可令\(\alpha_t=ln(\text{◆t})\)

算法流程：

这里之所以认为αt = ln(◆t)，处于下面的考虑： 如果εt = 1/2， 那么◆t = 1，则αt = 0，意思是随机乱猜的情况下（二元分类错误率为0.5），认为是坏的g，则一票不给个，不使用该g 如果εt = 0， 那么◆t = ∞，则αt = ∞，意思是正确率为0的情况，给它无限多票数

AdaBoost 自适应优化算法总结

自适应优化算法 = 简单的学习A + 放缩权重 + 合成得到g 即：

AdaBoost算法完整流程

AdaBoost理论特性

通过之前的VC Bound，来约束测试误差，其中蓝色的部分是模型的复杂度，O(dvc(H))为g的模型复杂度，而O(dvc(H))·T·logT是模型G的复杂度。原作者证明说，可以用O(logN)次迭代可以将Ein(G)做到很小，并且当数据量N足够多的情况下，又可以使得模型复杂度变得很小，从而使得模型复杂度得到控制。最终预测效果Eout也会很好。 AdaBoost的保证是让一个很弱的算法不断变强，最终得到一个很强是算法（Ein=0，Eout is small）。 # Adaptive Boosting的实际应用表现 上面的AdaBoost只需要一个很弱的算法就可以使用。 一般情况下，可以使用决策桩(Decision Stump)，该模型相当于在某一个维度上的Perceptron模型。

聚合（aggregation）模型总结

aggregation 模型主要应用在将得到的多个预测函数\(g_t\)聚合在一起，得到更好的\(g_t\)（即更好的分类器）的方式

聚合方式主要面向两种情况：

• blending:已经有了一堆\(g_t\)在手上（可能是已知的，可能是求得的）。
• learning：不已知\(g_t\)，需要通过一定方式求得很多\(g_t\)

learning的分为三种情况

• 把g看做是同等地位，通过投票或者平均的方式将它们合起来，称为Bagging
• g是不平等的，有好有坏，一个可行的做法是把g当成是特征的转换，然后丢进线性模型训练就可以了，这称为AdaBoost
• 如果是不同的条件下，使用不同的g，那么我们仍然可以将g当做是特征转换，接下来使用一个非线性模型来得到最终的模型参数，这就是下文要介绍的决策树算法

AdaBoost思路总结

• 一般，数据量过少时，我们无法得到更好的g.
• 因此我们采取BootStrapping方法，生成多个数据集，得到多个g
• 最后合成最好的g

AdaBoost伪代码

对每次迭代：
    用buildStump()函数找到最佳单层决策树
    将最佳单层决策树加入到单层决策树数组
    计算alpha
    计算新的权重向量D
    更新累积类别估计值
    如果错误率等于0，则退出循环

参考文献 1. 《机器学习技法》，林轩田 2. Jason Ding，【机器学习基础】自适应提升 3. Jason Ding，【机器学习基础】决策树算法

备注：本节是《机器学习技法》第8章+《统计学习方法》第8章笔记

引言

回顾之前学习过的两个算法：

• Bagging -- 简要：通过bootstrapping得到不一样的数据，得到不同的g，对g取平均得到G -- 特点：通过投票和平均的方式来降低对不同数据的敏感性（variance的效果）
• 决策树 -- 简要：通过递归方式建立子树，最终得到完整的树 -- 特点：对不同数据较敏感（算法的variance很大）
• 随机森林 -- 两者的结合

随机森林算法

概述：利用随机的方式将许多决策树组合成一个森林,每个决策树\(g_t(t)\)在分类的时候投票决定测试样本的最终类别。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

详细算法：

• 左边的总算法是Bagging思想--体现随机性

• 其中为每个\(g_t(t)\)建树时，是决策树的思想--体现森林

• 并行计算的可能性：随机森林算法从Bagging过程中可以分配到不同的计算机中进行计算，每台计算机可以独立学习一棵树，不同的树之间没有任何依赖关系。这使得Bagging过程很容易实现并行化。

特征投影（Feature Project)

• 原来在Bagging中，我们对数据进行抽取，得到不同的数据集，从而产生不同的\(g_t\)

• 在随机森林算法中，除了对数据抽取，也可以在特征这一角度抽取

• 例，如果事先我们有100个特征，现在我们可以抽取10个特征

• 得到数据集

• 来训练一棵树，这样的方式我们也可以得到很不一样的树，其对于分类的标准显然也很不一样

• 这等效于一个特征转换，这个过程中，从100维度到10个维度的转换中，相当于作了低维度的投影(Projection)

• 一般来说，

• 得到的特征实际上是原始特征的随机子集，这使得生成模型过程中的效率也大大提高了

特征扩展（feature Expansion）

每次随机抽取子空间 等效于 对原来的特征向量左乘一个投影矩阵\(P\),使得\(\Phi(X)=P\cdot x\)

更加有能力的特征投影就是不再单一选取单一维度的特征，而是将多个维度的特征进行组合(随机的方向)，得到新的一维的特征，这称为特征扩展。

• 将多个方向的特征随机合起来(combination)，即对于投影矩阵\(P\)的每一个方向\(p_i\)，不再固定方向（row）。即变为\(\Phi_i(X)=P_i^T\cdot x\) -- 一般情况下，会考虑low-dimensional，即投影过去时，一般每次选取少量维度进行投影。即只有\(d''\)的非零项被投影过去
• 这样的方式，包含了随机抽取（random subspace）的思想
• 一般来说，每次投影都采用新的不一样的投影

随机森林的采样过程

在建立森林的每颗决策树\(g_t\)的过程中，首先需要随机采样数据点。

不是所有数据点都能被采到。以下介绍OOB点

Out-of-bag（OOB）点

OOB点：在bootstrapping过程中，有些数据可能没有被选择，这些数据被称为OOB点。例如下表，对于训练每一个决策树\(g_t\)，其中用*号标注的就是\(g_t\)的OOB

OOB点个数

假设bootstrapping抽了\(N'\)次数据，探讨会有多少数据不会被抽到： - 若\(N'=N\)，某个数据\((x_n,y_n)\)从未被抽到的概率是\((1-\frac{1}{N})^N\) \[(1-\frac{1}{N})^N=\frac{1}{\frac{N}{N-1}^N}\approx \frac{1}{e}\] - 那么每个决策树\(g_t\)OOB集合的大小就约为\(\frac{1}{e}N\approx 0.3N\)

OOB用途-验证随机森林的G

可以用来做测试集-问题在于————验证g还是G？ 以数据集\((x_N,y_N)为例\)

• 验证\(g\)的必要性不大
• 验证\(G\)不方便
• 可以用来验证除了g1之外的G = \(G_N^-(x)=average(g_2,g_3,g_T)\)
• 总之，用来验证\(G\)表现是否好的方式： \[E_{oob}(G)=\frac{1}{N}\sum_1^N error(y_n,G_n^-(x_n))\]

特征选择（feature selection）

目的：自动选择需要的特征，去除冗余、不相关的特征 优点：降维，减少复杂度；减少噪声，提高模型泛化能力；物理意义； 缺点：计算量大；可能导致过拟合；

下面介绍特征选择的方法。

根据重要性选择（线性的）

• 给每个特征算一个权重（分数）
• 问题：特征选择是线性的，不符合随机森林的非线性特点

置换检验（非线性的，Permutation Test）

问题：每个特征是有噪音的，由于噪音的存在，导致某些原本很优秀的特征的分数被降低

解决方法：将第i个维度特征的所有数据重新的随机调整位置，然后比较一下原始数据和调整之后的数据表现的差距，来评价这个维度的特征是有多么重要。

• 调整方法1：高斯什么的，但会改变数据原始分布
• 调整方法2：随机重排，即置换检验。将某一维度的数据随机重排，可以看出来这个维度有多重要。

在Out-Of-Bag Estimate过程中做Permutation Test

在随机森林中可以用OOB代替验证的过程，为了简化Permutation Test带来的重新进行训练的代价，我们在使用OOB Example（bootstrap过程中没有选取的数据）进行验证的过程中做一些修改，即在验证的时候去进行Permutation Test，而非训练时进行。 在求Eoob(G)时，我们通过G-(xn)来计算，我们在这里将x(n)修改成x(n,i)，就可以不用对G进行修改了。 在实际应用中，面对非线性的问题时，可以通过随机森林的方法来进行初步的特征选择。

参考资料： 1. 机器学习的算法(1):决策树之随机森林 2. 机器学习技法

决策树简介

模仿人类决策的过程

• 优点：好理解；简单
• 缺点：缺少很强的理论支持；树结构不唯一；

决策树的表达方式

如上图所示的决策树，我们用\(G(x)\)来表达决策树：

\[G(x)=\sum_{t=1}^T q_t(x)\cdot g_t(x) \]

tips:

• \(g(x)\)是最终的决策（Y or N），叶子节点
• \(q_t(x)\)是条件，condition。就是橘色箭头的判断过程
• 内部的决策过程，例如deadline?，内部节点

那么决策树的表达就有两种方式：

• 路径角度。将每个从根到叶子的路径作为一个假设g，通过不同的条件组合得到最后的G(X)。

• 递归角度。父树是由子树递归定义的tree=(root,sub-trees)

基本流程

1. 如何分支（branching criteria），即如何得到\(b(x)\)
2. 根据分支，数据如何分块
3. 根据数据，如何学习子树
4. 得到最终的决策树

CART算法

• Classification And Regression Tree，分类回归树
• 二叉树（只有是、否）
• 输入：随机变量\(X\)
• 输出：随机变量\(Y\)的条件概率分布
• \(g_t(x)\)返回一个常数（根据不同的条件，对数据进行切分，到达叶子节点时，根据剩下的数据进行预测，输出一个常数）

纯度

纯度的定义

• CART算法中每个节点（看做是一个决策桩decision stump）对数据进行切分，如果分出来的数据的y都很接近（回归问题）或者都一样（分类问题），那么我们说这样的数据是“纯的”，这样用标量对数据进行预测可以得到比较小的误差。

CART分支\(b(x)\)为：

• 我们通过上面的公式，来计算对于每一个节点的决策桩来说，分出来的两份数据的纯度是怎样的。
• 该公式通过计算数据集Di（i=1 or 2）的纯度并根据数据集的数量对其进行加权
• 其加权的意义是如果数据集的数量比较大的话，那个纯度对其比较重要
• 反之，就不那么重要。
• CART通过分出的两部分数据综合起来的纯度对决策桩进行选择，选择“最纯”的分割方式作为当前的分支。

纯度的计算函数

我们可以将分割出来的数据和回传的常数的误差作为评价纯度的方法，利用数据的y和回传的y_ba的均方误差来评价回归问题的纯度；利用0/1误差函数来评价分类问题的纯度。

如果是分类问题，我们还可以使用一个别的方法。通过基尼不纯度来度量分类问题的纯度问题。

终止条件

CART中有两种被迫终止的情况，分别是：

• yn都一样，这时不纯度为0，于是可以得到gt(x)=yn；
• xn都一样，就没有继续分割的可能了。
• CART树长到被迫停下来的情况，称为完全长成的树（fully-grown tree）。

下面是CART算法完整流程：

CART剪枝

预防过拟合

上图告诉我们使用叶子的数目作为正则项（regularizer），最终得到一个正则化的决策树。 关于剪枝的具体做法时：

• 首先得到完全长成的树作为G(0)；
• 然后试图摘掉一片叶子，将所有摘掉一片叶子后的树计算Ein，将最小的那棵摘掉一片叶子的数作为G(1)；
• 如此这般，得到摘掉两片叶子的最优树G(2)，这样不断剪枝，直到根结点，形成一个子树序列；
• 最终对这个子树序列使用argmin Ein(G)+λΩ(G)来得到最后的输出。

参考资料

1. Jason Ding，决策树算法
2. 机器学习技法课程，林轩田，台湾大学