Improved K nearest neighbor classification algorithm

A novel and efficient algorithm is proposed to reduce the computational complexity for KNN classification. It uses two important features, the approximation coefficient of a fully decomposed feature vector with Haar wavelet and the variance of the corresponding untransformed vector, to produce two efficient test conditions. Since those vectors that are impossible to be the k closest vectors in the design set are kicked out quickly by these conditions, this algorithm saves largely the classification time and have the same classification performance as that of the exhaustive search classification algorithm. Experimental results based on texture image classification verify our proposed algorithm.