NDLI: Probabilistic characterization of nearest neighbor classifier

Content Provider	Springer Nature Link
Author	Dhurandhar, Amit Dobra, Alin
Copyright Year	2012
Abstract	The k-nearest neighbor classification algorithm (kNN) is one of the most simple yet effective classification algorithms in use. It finds major applications in text categorization, outlier detection, handwritten character recognition, fraud detection and in other related areas. Though sound theoretical results exist regarding convergence of the generalization error (GE) of this algorithm to Bayes error, these results are asymptotic in nature. The understanding of the behavior of the kNN algorithm in real world scenarios is limited. In this paper, assuming categorical attributes, we provide a principled way of studying the non-asymptotic behavior of the kNN algorithm. In particular, we derive exact closed form expressions for the moments of the GE for this algorithm. The expressions are functions of the sample, and hence can be computed given any joint probability distribution defined over the input–output space. These expressions can be used as a tool that aids in unveiling the statistical behavior of the algorithm in settings of interest viz. an acceptable value of k for a given sample size and distribution. Moreover, Monte Carlo approximations of such closed form expressions have been shown in Dhurandhar and Dobra (J Mach Learn Res 9, 2008; ACM Trans Knowl Discov Data 3, 2009) to be a superior alternative in terms of speed and accuracy when compared with computing the moments directly using Monte Carlo. This work employs the semi-analytical methodology that was proposed recently to better understand the non-asymptotic behavior of learning algorithms.
Starting Page	259
Ending Page	272
Page Count	14
File Format	PDF
ISSN	18688071
Journal	International Journal of Machine Learning and Cybernetics
Volume Number	4
Issue Number	4
e-ISSN	1868808X
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2012-04-27
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	kNN Moments Computational Intelligence Artificial Intelligence (incl. Robotics) Control, Robotics, Mechatronics Statistical Physics, Dynamical Systems and Complexity Systems Biology Pattern Recognition
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Towards enriching the quality of k-nearest neighbor rule for document classification

Hubness-based fuzzy measures for high-dimensional k-nearest neighbor classification

Optimal subspace classification method for complex data

An improved multiple fuzzy NNC system based on mutual information and fuzzy integral

Bayesian Citation-KNN with distance weighting

Multiple classifier systems for robust classifier design in adversarial environments

Large symmetric margin instance selection algorithm

Feature and instance reduction for PNN classifiers based on fuzzy rough sets

Advances in neural network based learning

Probabilistic characterization of nearest neighbor classifier

Similar Documents

Towards enriching the quality of k-nearest neighbor rule for document classification

Hubness-based fuzzy measures for high-dimensional k-nearest neighbor classification

Optimal subspace classification method for complex data

An improved multiple fuzzy NNC system based on mutual information and fuzzy integral

Bayesian Citation-KNN with distance weighting

Multiple classifier systems for robust classifier design in adversarial environments

Large symmetric margin instance selection algorithm

Feature and instance reduction for PNN classifiers based on fuzzy rough sets

Advances in neural network based learning

Probabilistic characterization of nearest neighbor classifier