K-nearest neighbours (Fix & Hodges 1951) is a simple but effective supervised machine learning algorithm. A multivariate data set with a group column is supplied, where one part (the training set) is assigned to groups, while the other part (the test set) has question marks in the group column. The rows in the test set are then assigned to groups (classification) according to their similarity with rows in the training set. Any distance measure can be used.
For each test row, the group is selected by a majority vote among the nearest k neighbors. The value of k is a parameter selected by the user. Small k may lead to overfitting, while large k may lead to oversmoothing. In addition, each vote among the nearest neighbors may be weighted according to distance d from the test point. Four weighting schemes are available in Past:
- No weighting. This is usually a poor choice (Gou et al. 2012) but is included for comparison.
- Inverse weighting, w = 1/d. This is the default weighting in some programs, but it is usually not optimal.
- Linear weighting (Dudani 1976) is a standard weighting that usually performs well:
Jackknifing
Past automatically performs a jackknifing (cross-validation) procedure on the training set. One row is removed from the training set at a time and classified using the remaining training data. The percentage of correctly classified rows is reported. This may be used to indicate good choices for k and weighting.
References
Dudani, S.A. 1976. The distance-weighted k-nearest-neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics 6:325-327.
Fix, E. Hodges, J.L. 1951. Discriminatory analysis, nonparametric discrimination: consistency properties. Technical Report No. 4, USAF School of Aviation Medicine, Randolf Field Texas, 238–247.
Gou, J., Du, L., Zhang, Y., Xiong, T. 2012. A new distance-weighted k-nearest neighbor classifier. Journal of Information & Computational Science 9:1429–1436.