zbMATH — the first resource for mathematics

Choice of neighbor order in nearest-neighbor classification. (English) Zbl 1274.62421
Summary: The \(k\)th-nearest neighbor rule is arguably the simplest and most intuitively appealing nonparametric classification procedure. However, application of this method is inhibited by lack of knowledge about its properties, in particular, about the manner in which it is influenced by the value of \(k\); and by the absence of techniques for empirical choice of \(k\). In the present paper we detail the way in which the value of \(k\) determines the misclassification error. We consider two models, Poisson and binomial, for the training samples. Under the first model, data are recorded in a Poisson stream and are “assigned” to one or other of the two populations in accordance with the prior probabilities. In particular, the total number of data in both training samples is a Poisson-distributed random variable. Under the binomial model, however, the total number of data in the training samples is fixed, although again each data value is assigned in a random way. Although the values of risk and regret associated with the Poisson and binomial models are different, they are asymptotically equivalent to first order, and also to the risks associated with kernel-based classifiers that are tailored to the case of two derivatives. These properties motivate new methods for choosing the value of \(k\).

62H30 Classification and discrimination; cluster analysis (statistical aspects)
62G20 Asymptotic properties of nonparametric inference
Full Text: DOI arXiv
[1] Audibert, J.-Y. and Tsybakov, A. B. (2007). Fast learning rates for plug-in classifiers under the margin condition. Ann. Statist. 35 608-633. · Zbl 1118.62041 · doi:10.1214/009053606000001217
[2] Bax, E. (2000). Validation of nearest neighbor classifiers. IEEE Trans. Inform. Theory 46 2746-2752. · Zbl 1019.68099 · doi:10.1109/18.887892
[3] Cover, T. M. (1968). Rates of convergence for nearest neighbor procedures. In Proceedings of the Hawaii International Conference on System Sciences (B. K. Kinariwala and F. F. Kuo, eds.) 413-415. Univ. Hawaii Press, Honolulu.
[4] Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13 21-27. · Zbl 0154.44505 · doi:10.1109/TIT.1967.1053964
[5] Devroye, L. (1981). On the asymptotic probability of error in nonparametric discrimination. Ann. Statist. 9 1320-1327. · Zbl 0481.62051 · doi:10.1214/aos/1176345648
[6] Devroye, L., Györfi, L., Krzyżak, A. and Lugosi, G. (1994). On the strong universal consistency of nearest neighbor regression function estimates. Ann. Statist. 22 1371-1385. · Zbl 0805.62039 · doi:10.1214/aos/1176325500
[7] Devroye, L., Györfi, L. and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition . Springer, New York. · Zbl 0853.68150
[8] Devroye, L. and Wagner, T. J. (1977). The strong uniform consistency of nearest neighbor density estimates. Ann. Statist. 5 536-540. · Zbl 0367.62061 · doi:10.1214/aos/1176343851
[9] Devroye, L. and Wagner, T. J. (1982). Nearest neighbor methods in discrimination. In Classification , Pattern Recognition and Reduction of Dimensionality. Handbook of Statistics 2 (P. R. Krishnaiah and L. N. Kanal, eds.) 193-197. North-Holland, Amsterdam. · Zbl 0511.62069
[10] Györfi, L. and Györfi, Z. (1978). An upper bound on the asymptotic error probability of the k -nearest neighbor rule for multiple classes. IEEE Trans. Inform. Theory 24 512-514. · Zbl 0477.62042 · doi:10.1109/TIT.1978.1055900
[11] Györfi, L., Kohler, M., Krzyżak, A. and Walk, H. (2002). A Distribution-Free Theory of Nonparametric Regression . Springer, New York. · Zbl 1021.62024
[12] Fix, E. and Hodges, J. L., Jr. (1951). Discriminatory analysis, nonparametric discrimination, consistency properties. Randolph Field, Texas, Project 21-49-004, Report No. 4.
[13] Fritz, J. (1975). Distribution-free exponential error bound for nearest neighbor pattern classification. IEEE Trans. Inform. Theory 21 552-557. · Zbl 0313.62030 · doi:10.1109/TIT.1975.1055443
[14] Györfi, L. (1978). On the rate of convergence of nearest neighbor rules. IEEE Trans. Inform. Theory 24 509-512. · Zbl 0433.62027 · doi:10.1109/TIT.1978.1055898
[15] Györfi, L. (1981). The rate of convergence of k - NN regression estimates and classification rules. IEEE Trans. Inform. Theory 27 362-364. · Zbl 0467.62053 · doi:10.1109/TIT.1981.1056344
[16] Hall, P. and Kang, K.-H. (2005). Bandwidth choice for nonparametric classification. Ann. Statist. 33 284-306. · Zbl 1064.62075 · doi:10.1214/009053604000000959
[17] Hall, P., Park, B. U. and Samworth, R. J. (2007). Choice of neighbour order for nearest-neighbour classification rule. Available at http://stat.snu.ac.kr/theostat/papers/hps.pdf.
[18] Holst, M. and Irle, A. (2001). Nearest neighbor classification with dependent training sequences. Ann. Statist. 29 1424-1442. · Zbl 1043.62057 · doi:10.1214/aos/1013203460
[19] Kharin, Yu. S. (1982). Asymptotic expansions for the risk of parametric and nonparametric decision functions. In Transactions of the Ninth Prague Conference on Information Theory , Statistical Decision Functions , Random Processes B 11-16. Reidel, Dordrecht. · Zbl 0554.62052
[20] Kharin, Yu. S. and Ducinskas, K. (1979). The asymptotic expansion of the risk for classifiers using maximum likelihood estimates. Statist. Problemy Upravleniya-Trudy Sem. Protsessy Optimal. Upravleniya V Sektsiya 38 77-93. (In Russian.) · Zbl 0435.62058
[21] Kohler, M. and Kryżak, A. (2006). On the rate of convergence of local averaging plug-in classification rules under a margin condition. Manuscript.
[22] Kulkarni, S. R. and Posner, S. E. (1995). Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Trans. Inform. Theory 41 1028-1039. · Zbl 0839.93070 · doi:10.1109/18.391248
[23] Mammen, E. and Tsybakov, A. B. (1999). Smooth discrimination analysis. Ann. Statist. 27 1808-1829. · Zbl 0961.62058 · doi:10.1214/aos/1017939240
[24] Marron, J. S. (1983). Optimal rates on convergence to Bayes risk in nonparametric discrimination. Ann. Statist. 11 1142-1155. · Zbl 0554.62053
[25] Psaltis, D., Snapp, R. R. and Venkatesh, S. S. (1994). On the finite sample performance of the nearest neighbor classifier. IEEE Trans. Inform. Theory 40 820-837. · Zbl 0820.62060 · doi:10.1109/18.335893
[26] Raudys, Š. and Young, D. (2004). Results in statistical discriminant analysis: A review of the former Soviet Union literature. J. Multivariate Anal. 89 1-35. · Zbl 1036.62053 · doi:10.1016/S0047-259X(02)00021-0
[27] Snapp, R. R. and Venkatesh, S. S. (1998). Asymptotic expansion of the k nearest neighbor risk. Ann. Statist. 26 850-878. · Zbl 0929.62070 · doi:10.1214/aos/1024691080
[28] Wagner, T. J. (1971). Convergence of the nearest neighbor rule. IEEE Trans. Inform. Theory 17 566-571. · Zbl 0225.62040 · doi:10.1109/TIT.1971.1054698
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.