Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a novel algorithm for computing a training set consistent subset for the nearest neighbor decision rule. The algorithm, called FCNN rule, has some desirable properties. Indeed, it is order independent, and has subquadratic worst case time complexity, while it requires few iterations to converge, and it is likely to select points very close to the decision boundary. We compare the FCNN rule with state of the art competence preservation algorithms on large multidimensional training sets, showing that it outperforms existing methods in terms of learning speed and learning scaling behavior, and in terms of size of the model, while it guarantees a comparable prediction accuracy.

REFERENCES

• 1: Henry Brighton , Chris Mellish, Advances in Instance Selection for Instance-Based Learning Algorithms, Data Mining and Knowledge Discovery, v.6 n.2, p.153-172, April 2002 [doi>10.1023/A:1014043630878]
• 2: Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Trans. on Inform. Th., 13, 21--27.
• 3: Dasarathy, B. (1994). Minimal consistent subset (mcs) identification for optimal nearest neighbor decision systems design. IEEE Trans. on Sys. Man. Cybernet., 24, 511--517.
• 4: Devi, F., & Murty, M. (2002). An incremental prototype set building technique. Pat. Recognition, 35, 505--513.
• 5: Devroye, L. (1981). On the inequality of cover and hart. IEEE Trans. on Pat. Anal. and Mach. Intel., 3, 75--78.
• 6: Gates, W. (1972). The reduced nearest neighbor rule. IEEE Trans. on Inform. Th., 18, 431--433.
• 7: Hart, P. (1968). The condensed nearest neighbor rule. IEEE Trans. on Inform. Th., 14, 515--516.
• 8: Karaçali, B., & Krim, H. (2002). Fast minimization of structural risk by nearest neighbor rule. IEEE Trans. on Neural Networks, 14, 127--134.
• 9: Liu, C., & Nakagawa, M. (2001). Evaluation of prototype learning algorithms for nearest-neighbor classifier in application to handwritten character recognition. Pat. Recognition, 34, 601--615.
• 10: Ritter, G., Woodruff, H., Lowry, S., & Isenhour, T. (1975). An algorithm for a selective nearest neighbor decision rule. IEEE Trans. on Inform. Th., 21, 665--669.
• 11: Stone, C. (1977). Consistent nonparametric regression. Annals of Statistics, 8, 1348--1360.
• 12: Toussaint, G. (2002). Proximity graphs for nearest neighbor decision rules: Recent progress. Proc. of the Symp. on Computing and Stat., Montreal, Canada.
• 13: Wilfong, G. (1992). Nearest neighbor problems. Int. J. of Computational Geometry & Applications, 2, 383--416.
• 14: D. Randall Wilson , Tony R. Martinez, Reduction Techniques for Instance-BasedLearning Algorithms, Machine Learning, v.38 n.3, p.257-286, March 2000 [doi>10.1023/A:1007626913721]