Skip to content

13.5 计算上的考虑

原文 The Elements of Statistical Learning
翻译 szcf-weiya
发布 2017-08-29
更新 2019-01-06
状态 Done

最近邻分类规则的一个缺点通常是它的计算负荷量，无论是寻找最近邻还是存储整个训练集合．当有 $N$ 个观测和 $p$ 个变量时，对每个点最近邻分类需要 $Np$ 次操作来寻找邻域．有一些快速算法 (Friedman et al., 19751; Friedman et al., 19772) 能在某种程度上降低计算负荷．Hastie and Simard (1998)3 通过在不变度量框架下提出类似 $K$-means 聚类的方法，降低了 切向距离 (tangent distance) 的计算量．

降低存储的要求更加困难，研究者们提出了各种 编辑 (editing) 和 压缩 (condensing) 的过程．想法是单独拿出能进行最近邻预测的训练集的子集，并且把剩下的训练数据丢掉．直观上看，保留靠近判别边界处和在边界正确一侧的训练点是很重要的，而那些离边界很远的点可以舍弃．

Devijver and Kittler (1982) 4 的多重编辑算法将数据周期性地划分为训练集和测试集，计算测试集上的最近邻，并且删掉误分类的测试点．想法是保留训练观测值的同种类别．

Hart (1968)5 的 压缩 (condensing) 过程更进一步，试图仅仅保留这些类别的 外点 (exterior point)．以随机选择单个观测作为训练集开始，每次处理一个额外的数据点，仅当它被当前训练集误分类时才加入到训练集中．

这是过程在 Dasarathy (1991)6 和 Ripley (1996)7 中均有综述．它们也可以应用到除最近邻以外的学习过程．尽管这些方法有时是有用的，但是我们并没有太多的实际经验，也没有在文献中找到关于它们表现的系统性的比较．

  1. Friedman, J., Baskett, F. and Shustek, L. (1975). An algorithm for finding nearest neighbors, IEEE Transactions on Computers 24: 1000–1006. ↩

  2. Friedman, J., Bentley, J. and Finkel, R. (1977). An algorthm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software 3: 209–226. ↩

  3. Hastie, T. and Simard, P. (1998). Models and metrics for handwritten digit recognition, Statistical Science 13: 54–65. ↩

  4. Devijver, P. and Kittler, J. (1982). Pattern Recognition: A Statistical Approach, Prentice-Hall, Englewood Cliffs, N.J. ↩

  5. Hart, P. (1968). The condensed nearest-neighbor rule, IEEE Transactions on Information Theory 14: 515–516. ↩

  6. Dasarathy, B. (1991). Nearest Neighbor Pattern Classification Techniques, IEEE Computer Society Press, Los Alamitos, CA. ↩

  7. Ripley, B. D. (1996). Pattern Recognition and Neural Networks, Cambridge University Press. ↩

Comments