技术概览
首先回归和分类最要得区别就是:回归的目标数据是连续的,分类的目标数据是离散的。
最近邻回归的原理是从训练样本中找到与新点在距离上最近的预定数量的几个点,并从这些点中预测标签。 这些点的数量可以是用户自定义的常量(K-最近邻学习),也可以根据不同的点的局部密度(基于半径的最近邻学习)。距离通常可以通过任何方式来度量: standard Euclidean distance(标准欧式距离)是最常见的选择。Neighbors-based(基于邻居的)方法被称为非泛化 机器学习方法, 因为它们只是简单地”记住”了其所有的训练数据(可能转换为一个快速索引结构,如 Ball Tree或 KD Tree)
尽管它很简单,但最近邻算法已经成功地适用于很多的回归问题,例如手写数字或卫星图像的场景。 作为一个 non-parametric(非参数化)方法,它经常成功地应用于决策边界非常不规则的情景下。k-NN regression和Fixed-radius near neighbors是比较经典最近邻回归算法。
K近邻算法也适用于连续变量估计,KNN回归的一个简单的实现是计算最近邻K的数值目标的平均值。另一种方法是使用K近邻的逆距离加权平均值。KNN回归使用与KNN分类相同的距离函数。比如适用反距离加权平均多个K近邻点确定测试点的值。KNN回归的实例如下:
以下是一个预测房价的例子,目标是预测房价(HPI House Price Index),年龄和贷款是预测参数。
现在可以使用Euclidean距离对一个未知的案例(年龄=48和贷款=$142,000)进行预测。一下是计算距离的方程:
D = \sqrt{(x_1 - y_1)^{2} + (x_2 - y_2)^{2}}
如果K=1,计算目前所有点对此点的距离(所有距离显示在表中),发现最近的距离最小的邻居是(年龄=33和贷款=$150,000),其距离为8000.01。所以我们就认为(年龄=48和贷款=$142,000)这个案例与(年龄=33和贷款=$150,000)最相似,所以案例(年龄=48和贷款=$142,000)的房价预测结果也就认为是案例(年龄=33和贷款=$150,000)的房价264.
D = \sqrt{(48 - 33)^{2} + (142000 - 150000)^{2}} = 8000.01 \gg HPI = 264
当K=3, HPI的预测等于HPI对前三个邻居的平均值。(我们就选取距离最近的3个案例:(年龄=33和贷款=$150,000)案例(年龄=35和贷款=$120,000)案例(年龄=60和贷款=$100,000)),所以,此时我们预测(年龄=48和贷款=$142,000)的房价如下:
HPI = (264+139+139)/3 = 180.7
[描述来源:wikipedia,URL: https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm#k-NN_regression]
发展历史
描述
最早的回归形式是最小二乘法,由Legendre在1805年和高斯在1809年提出。Legendre和Gauss都将这个方法应用于从天文观测到天体绕太阳运行的轨道(大部分是彗星,但后来也发现了新发现的小行星)的问题。Gauss在1821年出版了《最小二乘理论》的进一步讨论,其中包括Gauss–Markov theorem。
“回归”一词是由Francis Galton在19世纪创造的,用来描述一种生物现象。这种现象是,高个祖先的后代的身高趋向于平均水平(这一现象也被称为趋均数回归)。对于高尔顿来说,回归只有生物学上的意义,但是他的研究后来被Udny Yule 和 Karl Pearson推广到一个更一般的统计环境中。在Yule和Pearson的研究中,响应和解释变量的联合分布被假设为高斯分布。在1922年和1925年的作品中,R.A. Fisher削弱了这种假设。Fisher假设响应变量的条件分布是高斯分布,但联合分布不需要。在这方面,费雪的假设更接近于高斯1821的公式。在20世纪50年代和60年代,经济学家们使用机电计算器计算回归。在1970年以前,有时需要24小时才能收到一种回归的结果。所以回归在20世纪70年代再次兴起。
回归方法目前仍然是一个活跃的研究领域。近几十年来,回归方法已经到robust很健壮的程度,回归问题包含了:相关的反应,如时间序列和增长曲线,回归的预测变量(自变量)或响应曲线,图像、图形、或其他复杂的数据对象,适应各种类型的缺失的数据回归方法,非参数回归,贝叶斯方法回归,回归预测变量的测量误差,回归比观察,预测变量和因果推论与回归。
回归方法也分为参数化回归和非参数化回归,当然也分为线性回归和非线性回归。非参数化的回归算法再次兴起于1970s, 首先Nadaraya 1964; Priestley and Chao 1972; Watson 1964提出了局部的位置估计local location estimators,比如 kernel regression,和邻近回归估计 (Benedetti 1977; Stone 1977; Tukey 1977 )。
非参数回归是一种回归分析的范畴,在这种回归分析中,预测者不采取预先确定的形式,而是根据来自数据的信息构造。非参数回归比基于参数模型的回归需要更大的样本量,因为数据必须提供模型结构和模型估计。非参数回归目前主要有:Gaussian process regression or Kriging;Kernel regression;Nonparametric multiplicative regression;Regression trees等。最近邻回归就属于非参数化的回归。随着NNS(Nearest Neighbor)问题的不断演化,Nearest Neighbor regression也有很多方法:最经典的是K-nearest neighbor(KNN-regression);Fixed-radius near neighbors regression,对临近搜索问题的各种情况也考虑的比较完整。但是KNN-regression计算量大;样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);需要大量的内存等缺点,使得决策树回归进一步发展。最近决策树回归因为高效率,如GBDT (Gradient BoostDecision Tree) Leo Breiman,XGboost都被广泛得使用。
主要事件
年份 | 事件 | 相关论文 |
1977 | Benedetti对非参数回归方式进行了讨论 | Benedetti, J. K. (1977). On the nonparametric estimation of regression functions. Journal of the Royal Statistical Society. Series B (Methodological), 248-253. |
1977 | Stone非参数回归如kernel方式和临近估量进行分析 | Stone, C. J. (1977). Consistent nonparametric regression. The annals of statistics, 595-620. |
1999 | Freund对Gradient boosting进行观察 | Freund, Y., Schapire, R., & Abe, N. (1999). A short introduction to boosting. Journal-Japanese Society For Artificial Intelligence, 14(771-780), 1612. |
2001 | Friedman提出回归梯度增强算法 | Friedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189-1232. |
2009 | Hastie T提出多class adaboost | Hastie, T., Rosset, S., Zhu, J., & Zou, H. (2009). Multi-class adaboost. Statistics and its Interface, 2(3), 349-360. |
2015 | 陈天奇等人提出xgboost算法 | Chen, T., He, T., & Benesty, M. (2015). Xgboost: extreme gradient boosting. R package version 0.4-2, 1-4. |
2016 | 陈天奇等人提出xgboost系统 | Chen, T., & Guestrin, C. (2016, August). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd international conference on knowledge discovery and data mining (pp. 785-794). ACM. |
发展分析
瓶颈
- 计算量大,需要大量的内存;
- 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);
- 有时候在回归分析中,选用何种因子和该因子采用何种表达式只是一种推测,这影响了用电因子的多样性和某些因子的不可测性,使得回归分析在某些情况下受到限制
未来发展方向
最近邻算法是「基于实例的」,这就意味着其需要保留每一个训练样本观察值。最近邻算法通过搜寻最相似的训练样本来预测新观察样本的值。
而这种算法是内存密集型,对高维数据的处理效果并不是很好,并且还需要高效的距离函数来度量和计算相似度。在实践中,基本上使用正则化的回归或树型集成方法是最好的选择。
Contributor: Ruiying Cai