本文是作者之前做多分类比赛常用的一种trick,  如果碰到多分类问题时，不妨自己试试看，该方案在之前的蚂蚁定位等多分类竞赛中都带来了不错的提升。我在很多开源的数据集上也做了实验，基本90%的数据集都可以在原始单个模型的基础上带来或多或少的提升。

1  用于多分类问题的KNN修正的随机森林

1.1  摘要

随机森林是一种高效并且可扩展性较好的算法, K最近邻算法则是一种简单并且可解释较强的非参数化算法。在本篇文章中,我们针对多分类问题提出了一种将随机森林和KNN算法相结合框架,我们先用训练数据对随机森林模型进行训练然后用训练好的随机森林模型对我们的训练集和测试集进行预测分别得到训练集和测试集的概率矩阵,然后将测试集中的可疑样本取出并在概率空间中进行KNN训练测试,我们的框架很大地提升了测试集中可疑样本的预测准确率;此外我们从预测的概率空间对训练数据进行噪音的过滤与删除,从而进一步提升了我们模型的预测准确率。在大量实验数据的测试中,我们的方法都取得了非常显著的效果。

1.2  简介

随着机器学习和数据挖掘技术的发展,机器学习和大数据处理在许多领域已经变得愈加重要,垃圾邮件的监测能够帮助用户过滤掉垃圾邮件,方便用户浏览邮件,提升用户体验;信用卡欺诈的预测,贷款用户是否逾期还款的预测能帮助银行和贷款机构识别高信用度的用户,大大降低银行和贷款方的风险;用户购物兴趣爱好的预测能帮助卖方更好的为用户推荐喜爱的产品,提高交易成功率同时方便用户购物等等。这些产品的成功主要来源于两大核心因素,一个是能够挖掘数据之间的非线性关系的模型设计,另一个则是高速的可扩展的高性能算法的设计。
在所有的机器学习算法中,随机森林在大量的数据集上都展现了较好的性能,随机森林(Random Forest)模型是由Breiman和Cutler在2001年提出的一种基于分类回归树的算法[1]。它由bagging技术和决策树组成,通过对生成的多棵决策树做bagging操作,在不改变模型偏差的情况下降低了模型的方差,从而大大提高了模型的准确率。随机森林中,每棵决策树的生成相互独立,因此可以通过并行操作来完成多棵树的同时建立，所以决策树在处理大规模数据时也拥有着较好的可扩展性,在速度上相比于其他的方法例如Boosting等都有着较明显的优势。在分类效果上,随机森林在大量数据集上的表现也战胜了SVM,LR等机器学习模型，被认为是所有分类器中效果最好的分类器之一[2]。因为随机森林的这些优点,它也被广泛的应用在文本分类,垃圾邮件监测等各个领域。
K近邻算法是一种非参数化的算法[3], 在KNN用于分类问题时，我们通常通过计算测试点与训练集中所有点的距离并找出最近的K个点(邻居),以最近K个点的投票结果作为我们模型最终的分类结果。KNN算法不存在明显的训练过程,所以KNN算法也常被称作是懒惰学习(Lazy Learning)。在数据的特征维度不是很高同时样本个数中等的时候,KNN的设计简单高效同时具有较好的可解释性,所以KNN算法被广泛使用于机器学习的诸多任务当中,常常作为很多算法的Baseline。当特征的维度较高同时训练样本较大的时候,我们为了提高K近邻搜索的效率,时常我们会采用一些特殊的算法例如KD-Tree等[4,5,6]。
本篇文章我们将随机森林模型和KNN模型相结合,先使用训练数据训练得到随机森林模型,然后用训练好的随机森林模型分别对训练数据和测试数据进行预测得到概率矩阵$N_1 * K$,$N_2 * K$, 其中$N_1$为训练样本的个数,$N_2$为测试样本的个数,$K$为类的个数,然后我们从测试数据中寻找到测试数据中的**可疑样本**(具体的定义参考后文),然后采用KNN模型对测试结果中的可疑样本进行纠正,从而提高模型在可疑样本中的预测性能.此外我们将训练数据中的可疑样本当做噪音进行删除, 发现在多个数据集中我们的模型性能都得到了进一步的提升。本文的主要贡献如下:
  • 我们提出了一种将KNN和随机森林相结合的模型预测框架；
  • 通过对训练集中的噪音样本或难以学习的样本进行删除,在非噪音部分进行KNN训练进一步提高了模型的性能；
  • 我们的算法相比于单独采用随机森林或者KNN算法进行训练预测的方法取得了更好的结果.
本文我们会按照下面的顺序讨论我们的算法,在第二部分我们会介绍随机森林和KNN的背景知识；在第三部分我们会介绍我们的算法以及它的改进版本；在第四部分我们会观察我们的实验结果并进行实验的讨论;第五部分我们给出本文的结论以及未来工作。

1.3  背景

1.3.1  随机森林

随机森林(Random Forest)是由 Leo Breiman和Adele Cutler在2001年共同提出的一种集成算法[1],它通过对训练数据进行Boostrap采样[9]同时对特征进行列采样从而构建大量的去相关性的树,然后对这些树的预测结果求均值作为最终的结果。随机森林算法不仅设计简单,而且有着很多非常好的性质,我们可以利用随机森林中的OOB误差近似N折交叉验证的结果从而可以节省N折交叉验证的时间,随机森林关于特征重要性的构建可以很好地帮助我们进行数据特征选择与降维，随机森林中每棵树的构建相互独立,可以并行完成,因而大大降低模型构建的速度,增加模型的可扩展性。不仅如此,在大量的实验中,我们发现随机森林模型在很少会出现严重的拟合现象。在Manuel Fern{\'{a}}ndez Delgado进行的大量对比实验中[3],我们发现在大量的数据集上相较于SVM,LR,ANN等模型随机森林都取得了更好的结果,被认为是性能最好的模型之一。

1.3.2  KNN

K近邻算法是一种非参数化的算法,因为它的简单高效以及较好的可解释性,所以KNN算法被广泛应用于机器学习的诸多任务当中,同时也被认为是数据挖掘领域的10大机器学习算法之一[7]。KNN算法常常被用来处理分类和回归问题，当KNN算法用于分类问题时，我们经常通过计算测试点与训练集中所有点的距离，然后找出最近的K个点(邻居),并以最近K个点的投票结果作为我们模型最终的分类结果,但这样往往会忽略距离的影响,所以一些算法会选择对最近的K个点的距离进行加权并以加权后的结果作为模型的预测结果[8]。虽然KNN算法有着诸多的优点,但是KNN算法也存在较大的问题,当数据维度较高样本较多时,KNN常常会受到存储空间和计算复杂度的困扰,同时KNN将所有的训练样本当做是相关实例,所以KNN算法在存在噪音的数据集上往往受到较大的影响。

1.3.3  可疑样本定义

此处我们给出可疑样本的定义。
假设我们存在$N$个样本$(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$,$x_i$为第$i$个样本的特征,$y_i$为第$i$个样本对应的标签,$y_i \in \{1,2,3...,K\}$,$K \ge 3$为类的个数,我们采用已经训练好的模型$Model$对$N$个样本进行预测,得到一个$N*K$的概率矩阵,我们用$p_{ij}$表示为$Model$把第$i$个样本预测为第$j$类的概率,并且将每一个样本中概率最大的值对应的类作为我们最终的预测结果.即$argmax_j ~ p_{ij}, j \in K$为第$i$个样本的预测结果.   
可疑样本定义: 对于每一个样本$x_i $, 令$ q_i = max ~ p_{ij},~ j \in \{1,2,...,K\}, i \in \{1,2,...,N\}$,我们将所有 $q_i \le threshold,i \in \{1,2,...,N\} $的样本定义为可疑样本,表示模型对该类样本的预测没有较强把握.
而实践中我们也发现模型对于可疑样本的预测准确率往往远小于对于其他样本的预测准确率. 详细的比较可以我们放在后续的实验中。

1.4  算法设计

这一模块我们给出我们的算法的动机以及新的算法的伪代码。

1.4.1  算法动机

算法动机: 很多数据分析问题直接采用一些传统的模型例如感知机模型,线性支持向量机,逻辑回归,KNN等模型时所取得的效果较差,而采用基于树的模型,例如随机森林等往往可以取得较好的结果. 大多时候我们会选择直接将预测的结果作为最终的结果或者通过集成的方法来对模型进行进一步的提高,但是这样的计算代价往往较大,因为我们需要训练大量的模型来增加模型之间的差异性。本文从另外一个角度出发,通过修正不确定样本来提高模型的分类准确率。
我们在实践中发现, 在树模型的预测结果中存在较多的可疑样本,这些样本的预测准确率往往较低, 但是我们认为在同一个模型的预测概率空间中,测试集中不确定样本的预测概率分布与训练集中的不确定样本概率分布会拥有较为相似的分布, 所以我们考虑在预测概率空间中对不确定样本进行KNN操作来提高对不确定样本的分类准确率,实验中我们发现通过该方法确实可以较大提升我们对于不确定样本的预测准确率。

1.4.2  算法1

1.4.2.1  算法步骤

1.输入: 训练数据$Train$,$\{(x_1,y_1),(x_2,y_2),...,(x_{N_1},y_{N_1}) \}, x_i \in R^d, y_i \in \{1,2,..., M\}$, 测试集$Test$,$\{(x_1,y_1),(x_2,y_2),...,(x_{N_2},y_{N_2}) \}$.可疑样本的$Threshold$. $KNN$的$K$以及采用的距离函数。
2.模型训练: 对数据集Train进行训练获得模型$Model$。
3.模型预测:使用模型$Model$分别对训练集和测试集进行预测得到训练集的预测概率矩阵$Matrix\_Tr \in R^{N_1 * M}$以及测试集的概率矩阵$Matrix\_Te \in R^{N_2 * M}$。
4.KNN纠正: 将测试集中预测结果概率低于$Threshold$的样本的预测数据提取出来形成新的测试集$Test'$,将训练集的预测矩阵作为新的训练集的特征并使用$KNN$进行训练获得KNN模型,使用$KNN$对$Test'$进行预测,并将新的预测结果替代原先的预测结果。
5.输出:将纠正后的预测结果作为最终结果进行输出。

1.4.2.2  算法示意图

1.4.3  算法2

1.4.3.1  算法步骤

1.输入: 训练数据$Train$,$\{(x_1,y_1),(x_2,y_2),...,(x_{N_1},y_{N_1}) \}, x_i \in R^d, y_i \in \{1,2,..., K\}$, 测试集$Test$,$\{(x_1,y_1),(x_2,y_2),...,(x_{N_2},y_{N_2}) \}$.训练集可疑样本的$Threshold\_Tr$.测试集可疑样本的$Threshold\_Te$.$KNN$的$K$以及采用的距离函数。
2.模型训练: 对数据集$Train$进行训练获得模型$Model$。
3.模型预测:**使用模型$Model$分别对训练集和测试集进行预测得到训练集的预测概率矩阵$Matrix\_Tr \in R^{N_1 * K}$以及测试集的概率矩阵$Matrix\_Te \in R^{N_2 * K}$。

4.KNN纠正: 将测试集中预测结果概率低于$Threshold\_Te$的样本的预测数据提取出来形成新的测试集$Test'$,将训练集的预测矩阵高于$Threshold\_Tr$作为过滤之后的训练集的特征并使用$KNN$进行训练获得$KNN$模型,使用$KNN$对$Test'$进行预测,并将新的预测结果替代原先的预测结果。

5.输出:将纠正后的预测结果作为最终结果进行输出。

1.4.3.2  算法示意图

1.5  实验

1.5.1  数据集

  • Abalone Data Set
  • Poker Hand Data Set
  • CAR
  • HAR
  • Letter Recognition
  • Nursery
  • JsBach Chorals Harmony
  • Page Block
  • Magic

1.5.2  实验设计

1.5.2.1  训练集测试集划分

我们的实验数据全部来自UCI,如果数据集存在已经划分好的训练集和测试集,我们在训练集上进行3折交叉验证选取最优的参数,然后在训练数据上重新训练得到我们的最终模型,再在测试集上进行测试。
如果数据集上不存在已经划分好的训练集和测试集,则我们将数据按照7:3的比例划分为训练集和测试集,同样的,在训练数据上我们采用3折交叉验证获取最佳参数,然后使用最优参数在训练数据上重新进行模型训练,然后再在测试集上进行测试。
此外关于Poker Hand Data Set,我们随机采样200000个样本作为我们的训练测试数据。

1.5.2.2  参数设置

下面是我们实验中关于随机森林做交叉验证时的参数,训练集和测试集置信区间的参数设置以及在第二层KNN参数设置.
随机森林的参数:树的个数(n_estimators)为[100,200,500,1000],树的深度(max_depth)为[3,5,8,10,20],树最小分割样本(min_smaples_split)为[2,5,8],树叶子(min_smaples_leaf)的最小样本数为[2,5,8]；
训练样本的置信阈值$Threshold_{Tr}为[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]；
测试样本的置信阈值$Threshold_{Te}为[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]；
KNN的参数,K为[1,3,5,7,9],距离函数为[Cityblock,Euclidean,Chebyshev]。

1.5.3  实验结果

实验部分我们主要希望验证如下几个结论：
  • 随机森林相比于KNN能更好的挖掘数据之间的非线性关系,从而获得更高的准确率
  • 随机森林在预测的高概率空间中能获得更高的准确率,在低概率空间则往往只能得到较低的准确率
  • 通过KNN对随机森林预测中的可疑样本进行纠正可以很好地提高预测的准确率
  • 对训练集中的数据进行噪音删除可以进一步提高模型的准确率

1.5.3.1  随机森林相较于KNN能更好的挖掘数据之间的非线性关系

为了验证随‍‍‍机森林相比于KNN算法能更好地发掘数据之间的非线性关系,这边我们对8个数据集分别进行KNN和随机森林的训练以及测试,随机森林的训练测试步骤按照参数设置部分中的随机森林进行处理;KNN的训练测试,我们将KK设置为[1,3,5,7,9],距离函数设置为[Cityblock,Euclidean,Chebyshev]分别进行训练测试并将所有结果中最好的结果作为KNN的最终结果。‍‍‍
从上面的结果中我们发现随机森林算法在所有的8个数据集上相较于KNN都取得了更好的效果,这也验证了我们的猜想,随机森林相较于KNN能更好的挖掘数据之间的非线性关系同时取得更好的实验效果。

1.5.3.2  随机森林模型中高概率和低概率测试集的分布

为了方便,我们默认将0.5作为测试集的置信阈值,最终的结果参见下表:
从上表中我们发现模型中预测概率较高的往往也具有较高的准确率,而模型中预测分类概率较低的往往也具有较低的准确率。符合我们的认知。

1.5.3.3  验证KNN纠正可以提升随机森林预测结果的准确率（算法1）

我们此处仍然以0.5作为测试集的置信阈值,我们对测试集预测结果低于0.5的结果进行KNN处理,最终的结果参见下表:
通过观察上表我们发现,采用KNN对随机森林模型预测结果中不确定的部分进行KNN纠正可以很好的提升模型的准确率.

1.5.3.4  验证对训练数据进行噪音过滤可以进一步的提升模型的准确率（算法2）

同样的,我们将0.5作为测试集的置信阈值,与上面实验的不同之处在于我们对训练集的预测结果设置阈值[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65],将随机森林对于训练集预测结果小于某一阈值的结果作为噪音删去. 然后在剩余的训练集中进行KNN纠正.最终的结果如下:
通过观察上表我们发现,除了数据集JsBach Chorals Harmony,模型的效果下降了一点,其他数据集都表现出了较好的性能,这也从侧面说明训练数据中的这些预测结果较低的数据往往就是噪音,删除这些噪音能对KNN的预测带来较好的帮助。

1.5.3.5  算法探索

上述的实验我们将0.5作为测试集的置信阈值,这边我们在[0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65]间调整测试集的置信阈值,并比较当前结果与之前默认阈值的结果. 实验的结果可以参考下表.
通过观察上表我们发现,通过调整置测试集信阈值的大小,我们的模型的性能还可以得到进一步的提升。

1.6  结论

本文我们提出了一种将随机森林和KNN算法相结合的框架,我们的框架在多分类问题中进一步提升了测试集中可疑样本的预测准确率,之后我们又在此框架的基础上对训练样本进行噪音数据的处理,从而进一步提升了我们模型的性能,在大量实验数据的测试中,我们的方法都取得了非常显著的效果。目前该框架仍然还存在诸多可以改进和研究的地方,在未来的工作中,我们一方面会考虑将此框架扩展到其他模型中,例如神经网络模型等;另一方面,我们会进一步研究可疑样本的预测分布规律并考虑对预测较差的样本进行再学习等。

1.7  参考文献

  • L. Breiman. Random forests. Machine Learning, 45(1):5–32, 2001
  • Manuel Fern{\'{a}}ndez Delgado, Eva Cernadas,Sen{\'{e}}n Barro, Dinani Gomes Amorim. Do we need hundreds of classifiers to solve real world classification problems? JMLR,2014.
  • Altman, N. S.. "An introduction to kernel and nearest-neighbor nonparametric regression". The American Statistician. 46 (3): 175–185. 1992
  • Andrew Glassner. An Introduction to Ray Tracing. Morgan Kaufmann,1989. ISBN 0-12286-160-4.
  • Vlastimil Havran. Heuristic Ray Shooting Algorithms. PhD thesis,Czech Technical University in Prague, 2001.
  • Wald I, Havran V. "On building fast kd-trees for ray tracing, and on doing that in O(N log N)". In: Proceedings of the 2006 IEEE
  • Wu X, Kumar V, Ross Quinlan J, Ghosh J, Yang Q, Motoda H,McLachlan GJ, Ng A, Liu B, Yu PS, Zhou ZH, Steinbach M,Hand DJ, Steinberg D (2007) Top 10 algorithms in data mining.Knowl Inf Syst 14(1):1–37. 2007
  • Samworth R. J. "Optimal weighted nearest neighbour classifiers". Annals of Statistics. 40 (5): 2733–2763. 2012
  • Ann. Statist. Bootstrap Methods: Another Look at the Jackknife. Volume 7, Number 1 (1979), 1-26.
本文转自Kaggle竞赛宝典
作者个人微信，欢迎交流讨论机器学习，数据挖掘
继续阅读
阅读原文