KDD Cup 2019 AutoML Track冠军深兰科技DeepBlueAI团队技术分享 | 开源代码

作者丨罗志鹏

单位丨深兰北京AI研发中心

近日,KDD Cup 2019 AutoML Track 比赛结果出炉,本次赛题是第五次 AutoML 挑战赛,由第四范式、ChaLearn 和微软联合举办,专注于时序相关数据的自动机器学习。

这次竞赛注册队伍达到近 800 支,是近几次 AutoML 竞赛中参赛队伍最多的一次。 来自深兰科技北京 AI 研发中心的 DeepBlueAI 团队斩获冠军 ,团队成员均毕业或就读于北大。新加坡国立大学的 NUS-Xtra-Lab 团队获得第二名,阿里巴巴集团和佐治亚理工学院组成的 admin 团队则获得第三名。排名前十的队伍中还包括清华大学、南京大学、微软亚洲研究院、海康威视、美团点评等高校或机构。

本文带来该团队在竞赛中技术细节分享 ,文末附开源代码 Github 链接。

背景介绍

ACM SIGKDD 由美国计算机协会数据挖掘与知识专业委员会发起,是数据挖掘领域公认的具有最高学术地位的国际性学术会议。KDD Cup 是由 ACM 的数据挖掘及知识发现专委会(SIGKDD)主办的数据挖掘研究领域的国际顶级赛事,从 1997 年至今已有 22 年的历史。

作为目前数据挖掘领域最有影响力、最高水平的国际顶级赛事,KDD Cup 每年都会吸引来自世界各地数据挖掘领域的顶尖专家、学者和工程师参赛,因此也有“大数据奥运会”之名。今年, 第 25 届 ACM SIGKDD 会议于 2019 年 8 月 4 日至 8 日在美国阿拉斯加举行。

团队成绩

在 KDD Cup 2019 AutoML Track 当中,DeepBlueAI 团队在 Feed-back 阶段以 4 项第一 ,1 项第二 平均成绩排名第一;AutoML 阶段以 3 项第一,平均指标领先第二名 0.3 的成绩以绝对优势获得冠军,具体排名如下:

  图1. KDD Cup 2019 AutoML Track终榜及开源地址

  图2. KDD Cup 2019 AutoML Track Blind Test Phase排行榜

  图3. KDD Cup 2019 AutoML Track Feed-back Phase排行榜

团队成员获奖记录

赛题介绍

参赛者将 利用时序关系数据,设计一个能够自主(无人为干预)实现监督学习的AutoML计算机程序。 该比赛聚焦在二分类问题,且时序关系数据均来自实际业务场景。根据大多数实际应用的时间属性,数据集按时间顺序划分为训练集和测试集。训练集和测试集都由一个主表、一组相关表和一个关系图组成: 

  • 主表包含带有样本标记、部分特征和时序标签的实例,用于二分类; 

  • 相关表包含了主表中实例的重要辅助信息,可用于提高预测效果。 相关表中的字段可能含有时间标签,意味着该表中的信息与时间有关;

  • 不同表中数据之间的关系用关系图描述。需要注意的是,任何两个表(主表或相关表)都可以有一个关系,任何一对表最多只能有一个关系。主办方保证训练集和测试集的关系图是相同的。 

参赛者需要提交通过主表、相关表和关系图自动构建机器学习模型的 AutoML 方案。一旦经过训练,模型将以测试主表(不包括样本标记)、相关表和关系图作为输入,并预测测试集的样本标记。参赛者提交的方案将在受限制的计算资源和时间内进行测试。 

为了让参赛者能够更好的开发并评估方案,主办方提供了 10 个时序关系数据集,其中 5 个公共数据集,5 个私有数据集。

比赛阶段

Feedback 阶段 

即反馈阶段。在此阶段,参赛者可以在五个公共数据集上进行训练,开发 AutoML 方案。参赛者可以进行有限数量的提交,并获得作为反馈的所有五个公共数据集的测试数据的性能。参赛者可以下载有标记的训练数据集和未标记的测试数据集。因此,参赛者可以在线下准备他们的代码并提交。该阶段最后的代码提交将最终作为下一阶段进行盲测的代码。 

Check 阶段  

即校验阶段。该阶段将在五个私有数据集上对第一阶段的最后一次提交的代码进行盲测,确保提交的方案顺利运行,不会出现例如超时或者内存溢出等问题,但参赛者无法看到具体的结果,所有参赛队伍具备一次更新代码的机会,以保证在最终阶段正确的运行自己的代码。 

AutoML 阶段 

即盲试阶段。该阶段将测试方案在私有数据集上的性能。参赛者的代码将在无需人为干预情况下完成训练和预测。AUC 作为评价指标,最终将根据五个私有数据集的平均排名进行评分。若最终比分相同,则优先考虑可解释性更好的方案,可解释性将由专家团队评审。

以上三个阶段的计算及内存资源均有所限制,因此方案应兼顾效果及效率。

竞赛时间

2019 年 4 月 1 日:比赛开始,发布公共数据集。参与者可以开始提交代码并在排行榜上获得即时反馈信息。 

2019 年 6 月 27 日:Feedback 阶段结束,Feedback 阶段的代码自动迁移到 Test 阶段。 

2019 年 7 月 7 日:Check 阶段结束,主办方开始代码验证。 

2019 年 7 月 11 日:提交报告的截止日期。 

2019 年 7 月 16 日:AutoML 阶段结束,开始评审流程。 

2019 年 7 月 20 日:宣布 KDD Cup 冠军。 

2019 年 8 月 4 日:在 KDD 上举办颁奖仪式。

评测指标

本次比赛采用 AUC 作为评分指标,排名规则以官方给出的 baseline 得分 auc_base 为 0 分基准,以所有选手最高成绩 auc_max 为满分 1 分基准,按照公式得出相对分数,最后算出 5 个数据集的平均分为最终得分,得分越高代表模型性能越好。得分计算公式如下:

题目特点

在这次比赛中,主要有以下难点:

1. 挖掘有效的特征

与传统数据挖掘竞赛不同的是,AutoML 竞赛中,参赛选手只知道数据的类型(数值变量、分类变量、时间变量、多值分类变量等),而不知道数据的含义,这毫无疑问会增加特征工程的难度,如何挖掘到有效的通用特征成为一个难点。

2. 赛题数据和时序相关

时序相关数据的数据挖掘难度较大,在传统的机器学习应用中,需要经验丰富的专家才能从时序关系型数据中挖掘出有效的时序信息,并加以利用提升机器学习模型的效果。即使具备较深的知识储备,专家也需要通过不断的尝试和试错,才能构建出有价值的时序特征,并且利用好多个相关联表来提升机器学习模型的性能。

3. 赛题数据按照多表给出

赛题的数据是按照多表给出的,这就要求参赛选手能够构建一个处理多表之间多样的连接关系的自动化机器学习系统。多表数据无疑提升了对系统的稳定性的要求,稍有不慎,有可能合并出来的数据过于庞大就直接超时或者超内存而导致没有最终成绩。

4. 时间内存限制严格

比赛代码运行环境是一个 4 核 CPU,16G 内存的 docker 环境,对于未知大小的数据集,在代码执行过程中的某些操作很容易使得内存峰值超过 16G,导致程序崩溃。因此选手要严格优化某些操作,或使用采样等方式完成任务。此外,比赛方对于每个数据集严格限制了代码的执行时间,稍有不慎就会使得运行时间超时而崩溃。

解决方案

我们团队基于所给数据实现了一套支持多表的 AutoML 框架,包括自动多表合并、自动特征工程、自动特征选择、自动模型调参、自动模型融合等步骤,在时间和内存的控制上我们也做了很多优化工作。

数据预处理

我们通过对表结构及其属性的分析,针对不同类型的数据制定不同的数据预处理方案。首先,在多表间的多个连接 key 中,我们在主表中种类最多的一个 key 识别为 user。基于识别出的 user,可以尝试在主表的 category 中识别出 session。

另外,我们尝试在 category 数据中识别出只有两类有效值的 binary 数据。我们对 category、user、session、key 进行重新编码,对 numerical 数据尝试将其转换为占用内存更少的类型,将 time 数据转换为容易操作的 datetime 类型。

# 识别user 与 session
def recognize_user_col(self,data,key_cols):
    user_col = None
    nunique = -1
    for col in key_cols:
        nnum = data[col].nunique()
        if nnum > nunique:
            user_col = col
            nunique = nnum
    return user_col

def recognize_session_col(self,data,cat_cols,user_col):
    if user_col is None:
        return []

    user_nunique = data[user_col].nunique()
    session_cols = []

    def func(df,user_nunique):
        cat_col = df.columns[0]
        user_col = df.columns[1]
        cat_nunique = df[cat_col].nunique()

        if (cat_nunique = df.shape[0]-10):
            return False

        if (df.groupby(cat_col)[user_col].nunique()>1).sum()>10:
            return False

        return True

    res = Parallel(n_jobs=CONSTANT.JOBS,require='sharedmem')(delayed(func)(data[[col,user_col]],user_nunique) for col in cat_cols)

    for col,is_session in zip(cat_cols,res):
        if is_session:
            session_cols.append(col)

    return session_cols

多表连接

比赛给的数据结构如上图所示,表和表之间的连接关系可以分为四种,分别是 1-1、1-M、M-1、M-M。因为时间和内存的限制,所以我们需要在尽可能保留信息的同时,让最后生成的表的数据规模不至于过大。而处理多表连接的方式,直接影响到后面的结果。我们针对不同的连接方式采用了不同的方法。

首先将四种连接方式分成了两种类型:类型 1 包含了 1-1、M-1,类型 2 包含了 1-M、M-M。对于类型 1,我们可以直接将副表的数据通过 key 合并到主表上。对于类型 2,我们首先对副表做一些聚集操作,生成聚集的结果,而这些聚集的结果可以理解为和主表是类型1的关系。

接下来,我们只要对生成聚集的结果做类型 1 的操作,直接将其合并到主表上即可。并且,对于主表和副表都有时间戳的情况下,我们为了尽可能保留信息,将副表上离主表当前数据早且最近并且为相同 key 值的数据合并到主表上。

其具体操作可以见图示,key 为 147714011 的数据项的 n_1 列的数据为 3.6,连接到 Main Table 对应的 147714011 的所有数据项之上。

该图表示了类型 2 的连接方式,这个例子为对 n_1 列做了均值聚集操作,key 为 147714011 的数据项在 n_1 列上的均值为 2.3,之后就是将该数据对应合并到主表上。

采样

因为 AutoML 比赛方给定的数据集大小未知,在对其进行操作处理之前首先要判断当前环境是否能够支持整个数据集共同参与特征工程及模型训练过程。我们在读入数据进入预处理之前做了一次判断,即要求训练集与测试集的总样本数不超过某一个可以接受的阈值。如训练集与测试集的总样本数过多,我们就考虑对其进行采样,在当前给定的 16G 内存的条件下,我们经过估算,得到 400 万条数据是一个比较好的阈值。

此外,在特征工程的组合特征模块中,同样用到了采样的思想。组合特征的特点是产生的特征数量多,特征工程的时间长,内存峰值高,起作用的特征数量少。因此,为了避免内存溢出,我们在做组合特征之前,在小数据集上进行特征工程,经过筛选后得到真正有效的特征,再在整个数据集上仅做出这些有效的特征这样不仅可以减少系统运行时间也能避免爆内存的风险。

自动特征工程

def main_init(self):
    self.order1s = [
                PreMcToNumpy,McCatRank,
                OriginSession,
                ApartCatRecognize,\
                KeysCountDIY,UserKeyCntDIY,SessionKeyCntDIY,\
                KeysTimeDiffAndFuture,
                KeysNuniqueDIY, KeysCntDivNuniqueDIY,
                KeysCumCntRateAndReverse,UserKeyCumCntRateAndReverse,
                KeyTimeDate,KeyTimeBin,KeysBinCntDIY,
                CatCountDIY,
                LGBFeatureSelection,
            ]
    self.keys_order2s = [
                KeysNumMeanOrder2MinusSelfNew,
                KeysNumMaxMinOrder2MinusSelfNew,
                KeysNumStd,
                KeysCatCntOrder2New,
                LGBFeatureSelectionWait,
            ]
        self.all_order2s = [
                BinsCatCntOrder2DIYNew,
                BinsNumMeanOrder2DIYNew,
                CatNumMeanOrder2DIYNew,
                CatCntOrder2DIYNew,
                LGBFeatureSelectionWait
            ]

        self.post_order1s = [
                TimeNum,
            ]

        self.merge_order1s = [
                CatSegCtrOrigin,
                CatMeanEncoding,
                LGBFeatureSelectionLast,
            ]

特征工程部分往往是数据挖掘竞赛的关键核心内容,也是我们团队在竞赛中取得显著优势的重要因素。我们通过 LightGBM 模型来验证特征效果。我们将特征工程分成几个模块。

第一个模块是基础特征部分,这一部分主要是针对 user、key、session 的统计特征,产生新特征的数目较少却有很好的效果,因此放在最先。

第二模块是一阶组合特征部分,我们尝试将主表中较为重要的 user、key、session 与其余的 numerical 或 categorical 挑选出的数据进行组合,对某些数据集有非常好的效果。

第三个是大量组合特征部分,我们对时间分桶,尝试使用时间桶对 categorical 和 numerical 数据进行组合,此外我们还根据不同数据集的数据量大小,筛选出适量的 categorical 或 numerical 数据两两组合形成新的特征,在希望挖掘到有用的特征的同时,尽量减小内存溢出的风险。

最后的部分是有监督学习的 CTR 和均值编码特征,将其放在最后的原因是一方面在这一阶段会产生很多特征,容易造成生成过多的特征而导致爆内存;另一方面是我们认为这些特征和其他特征组合没有什么实际意义,因此将其放在最后不参与组合。

同时,因为本次竞赛的时间和内存的控制比较严格,在面对百万级的数据量上,每个特征生成几乎都要控制在几秒内生成,为了满足这一要求,我们的代码加入了许多优化。比如对于类别数据在多类别数据中的位置这一特征,如果用传统的 Pandas 实现,时间会达到几个小时,而加入多线程之后,情况会有所改善,但是仍旧要消耗大量的时间。

我们退而求其次,使用 numpy 来实现该特征,特征的生成时间直接到达了几十秒的级别,但是这仍旧不能满足我们的要求。最后我们对这块代码使用 cython 去优化,并且对 cython 代码进行精雕细琢,最后该特征的生成只需要几秒。

  图4. 经过筛选后较为重要的特征

自动特征选择

在自动特征工程阶段,我们将特征工程分为多个阶段。在每一个模块结束后,我们都会做一次特征选择来筛掉那些在这一阶段做出的无效的特征,来避免内存溢出并且加速最终的模型训练。

我们通过结合特征重要性及序列后向选择算法,设置一个阈值,将在参与模型训练中,筛出重要性较低的特征而尽可能小地损失模型精度。我们还尝试了基于特征的信息增益来对特征进行筛选,亦或是对两种筛选方法进行结合,但因为没能找到更好的切分点,最终还是使用了基于特征重要性的方法。

  图5. 特征选择机制

类别不平衡问题处理

我们对类别不平衡的数据在训练时做了处理。正负样本比例超过 1:3 时,我们采用欠采样的方式,缓和正负样本不平衡。此外,我们还尝试通过增加正样本的权重等方式来优化类别不平衡带来的问题。在模型融合的部分,我们在保留原始较少的正样本的同时,换一批负样本来进行训练,这样能够尽可能保留更多的原始数据的信息,同时缓解类别不平衡的问题。

模型融合

由于比赛环境对时间和内存做了严格的限制,我们在模型融合方面考虑了 bagging、blending、stacking 等方案,最终选用了使用 bagging 的方法。我们通过计算一个 demo 模拟真实数据集训练和预测来预估真实数据集所需要的时间,如时间不足则选择在训练时 early-stop,允许精度上的损失来保证代码能够在规定时间内运行完毕。

如时间充裕,则通过当前剩余时间计算允许多少个模型进行融合。为了保证代码通过,我们采用了保守估计的方式,即在计算出模型融合数量的基础上,选择少融合一个模型。

start_time = time.time()
temp = X.iloc[:100000]

temp = temp.astype(np.float32)
gc.collect()
temp = temp.values
gc.collect()

model.predict(temp)
end_time = time.time()
model_test_use_time = (end_time-start_time)
# 估算预测10万条数据所需的时间
model_test_use_time = len_test/temp.shape[0] * model_test_use_time
# 得到预测测试集数据所需的时间
model_use_time = model_use_time + model_test_use_time
# 总时间 = 训练时间 + 测试时间
del temp,model

rest_time = config.budget/10*9-(end_time-config.start_time)
# 使用给定时间的90%做保守估计,计算剩余可用时间
if rest_time = 50:
    rest_model_num = 50 

if rest_model_num >= 1:
    rest_model_num -= 1
# 根据剩余时间计算出可融合模型的数量,在此基础上少融合一个模型

运行时间优化

我们的时间控制在各个过程中都有体现。 

在自动化数据处理和自动化特征工程的过程中,我们使用 Cython 对编码以及一些生成效率较慢的特征进行加速。这里举一个特征为例,对于两列数据,一列为 category 类型的数据,一列为 multi-category 类型的数据,我们提前判断了两列数据的数据项集具有交集,我们要计算这一 category 列中的数据项在 multi-category 列对应的数据项集中的位置信息。

比如说有有一条数据。data : [ 2137 , (134,2137,576,816) ] ,前者 2137 在后者的第 2 个位置上。所以这条数据该特征为 2。如果没有出现的话,规定为 0。对于这一特征,如果我们使用 pandas 提供的 apply 接口来实现,在本次竞赛的环境下,该类特征的生成需要大约几个小时的时间。

考虑到 DataFrame 不适合做遍历,以及接口泛化性带来的性能上的损失。我们使用 Numpy,做遍历来实现该特征,能够让特征的生成达到分钟级。而本次竞赛的时间和内存有严格的控制,像那些需要超过 10 秒才能生成的一类特征就算非常耗时的了。

之后我们采用 Cython,应用 Cython 提前编译,静态类型等机制我们将该特征的生成时间控制在了 10 秒内。其中生成该特征的过程中有一些细节。比如如果在 Cython 中继续使用 Python 原生类型,那么遍历的效率还是比较缓慢。但是 multi-category 类型的数据存储又不好离开 Python 原生类型的支持。

考虑我们在生成特征的过程中,主要是对 multi-category 类型做遍历操作,所以可以使用一个数组去存储 multi-category 的每个数据项。并且用额外一个数组去保存每个 multi-category 的数据项集的长度。这样根据其长度数组和数据数组,我们就能做一个高效的遍历。

在测试这段优化的过程中,纯粹的 Python 代码经过 Cython 优化,效率大概能到 60 秒。而经过这段优化,很轻松就能到达 10 秒内(测试环境就是以我们的本次计算机为主,线上环境会多一些时间)。 

在模型集成部分,我们会做提前计算,记录到当前用时,通过训练模型几个轮次来计算出模型启动的时间以及模型训练每一轮数据所消耗的时间,通过这两个时间,我们能够预估出后续的参数调优,模型训练的时间。从而决定最后模型融合的数量。

  时间优化前后对比

运行内存优化

在内存控制方面,我们首先实现了一个内存的监听器。我们首先完整运行一轮我们的系统,记录下内存情况,对不同数据集的内存峰值进行分析。可以发现的是,内存峰值往往就出现在几个典型的地方。比如:数据合成时、在模型开始训练时、某些特征生成时。

经过分析,可以概括为几个点,其中比较典型的是数据合成时,如果使用 pandas 的接口 pandas.concat 进行数据合并,其合并过程中,会生成大约两倍当前数据内存的量。这个是显然的,因为其合并返回的结果不是就地的,而是创建出第三块内存。因此,我们将合成的过程改为按列赋值,这样合并时就几乎不存在内存峰值了。但是这么做,同时会带来较差的时间效率。所以在系统的早期,内存比较宽松的情况下,我们仍旧采用 pandas 的接口来进行对数据的合并。

另外,我们同样对训练预测时内存的情况进行了提前计算,在最后的特征筛选的过程中,我们会计算模拟出在生成多大的数据量下,能够完整进行系统后续的过程。从而来控制最后筛选出来的数据量。并且在最后一次特征筛选前,生成特征时,我们也会先时候小数据集进行一个模拟过程,来计算出整个过程中的内存情况,来对生成期生成的特征数量进行一个控制。

最后,我们会做一些比较精细的内存管理,在变量生命周期结束的时候,我们都会对其进行内存回收。以下是我们内存优化前后的一个对比。里面包含了比赛中给的 5 个数据集的运行过程中的内存情况。

  图6. 内存优化前后对比

系统测试

对于系统的测试,我们分为了两个方面进行。第一个方面是测试系统的扩展性,第二个方面是测试系统的性能。 

对于系统的扩展性,我们测试过如下: 

  • 对于不同的数据类型缺失的情况;

  • 对于不同数据类型数值全为空的情况; 

  • 对于表的结构为单表、复杂多表的情况。 

以及其他一系列的极限状态。

而对于系统的性能方面,我们测试过如下: 

  • 扩大数据的条目,就本次竞赛的 5 个数据集而言,我们扩展每个数据集数据条目 2 倍,3 倍,6 倍都能够在规定的时间和内存下顺利运行。 

  • 扩大数据的字段数量,同样,我们扩展 5 个数据集的字段数量 2 倍也能够顺利运行。 

  • 构造特定的数据集,观察是否会因为某些组合特征而系统崩溃。最后测试了大约数十个构造的极端数据集都能够运行成功。 

  • 限制数据集允许运行时间,我们通过调整数据集允许运行时间,观察我们的系统是否能够自适应调整自身的运行时间。我们调整本次竞赛中原本时间就比较紧张的 A 数据集以及数据量较大的 B 数据集,将其允许的运行时间变为原来的 1/2,1/3,甚至是 1/4。我们的系统都能够顺利运行。

总结

本次 KDD Cup AutoML 竞赛在赛制上得到进一步完善。相对于 NeurIPS 2018 AutoML 竞赛增加了一次 AutoML 阶段的提交次数,这样能够尽量保障参赛选手顺利跑通 B 榜数据。相对于 PAKDD 2019 AutoML 竞赛改进评分机制,最终得分只受各任务最高分的影响。完善后的竞赛机制让参赛选手得到更好的竞赛体验和技术发挥,感谢主办方的辛勤付出。 

在这次竞赛中我们的工作围绕着竞赛的挑战而进行,主要有几个比较重要的过程:自动化多表数据处理、自动多表连接、自动化特征工程、自动化模型构建、选择和融合。同时为了满足竞赛的时间和内存的需求,我们在代码上做了相当多的优化,比如使用了多线程、Cython、预处理、提前估算等方法。最后我们的成绩相当不错,A,B 榜单上均在多个任务集上有比较大的优势。 

时序关系型数据在在线广告、推荐系统、金融市场分析等应用场景中十分常见。本次 AutoML 聚焦时序关系型数据,为参赛者提出了挑战,同时也为 AutoML 的发展提供了新的思路。近年来 AutoML 因为其高适应性、高效性、可扩展性、高可用性,在工业应用中可以大大降低应用门槛,在不同的场景中均可以发挥出用武之地,大大缩短项目开发周期。最后祝贺所有的 Top 队伍,愿大家在未来都能取得自己满意的成绩!

作者介绍

罗志鹏,深兰北京 AI 研发中心负责人,深兰科技机器学习科学家。

硕士毕业于北大,获得过 PAKDD,KDD,NeurIPS,CIKM,CVPR,SIGIR 等顶级会议竞赛冠军,以一作发表 KDD Oral 一篇,共同一作 WWW 一篇,多年机器学习实战经验。

开源链接

https://github.com/DeepBlueAI/AutoSmart