基于Haar小波变换的快速k-近邻分类算法

Fast k nearest-neighbor classification algorithm based on Haar wavelet transform

提出了一种新的快速k-近邻分类算法,通过研究Haar小波系数所包含的重要信息,确定向量经Haar小波变换得到的小波系数与向量方差间的关系,由此得出关于小波系数的不等式,并利用此不等式提高k-近邻分类中的k-近邻搜索效率。在搜索k-近邻的过程中,首先判断每个训练向量是否满足该不等式,由此排除许多不可能成为k-近邻的向量,从而可以快速找到待分类样本的k-近邻,使得在保持k-近邻法分类性能不变的情况下,分类的效率得到很大提高。最后,通过纹理分类验证了算法的有效性。

The core of the k nearest-neighbor classification method was put forward to search for the k nearest neighbors of a new sample （feature vector）. The important information hiding in the Haar wavelet coefficients was investigated. Then the relationship between the Haar wavelet coefficient and the varianee of a vector was determined, from which an inequality about the wavelet coefficient was obtained. When searching for the k nearest-neighbors this inequality condition was employed to identify and kick out quickly many vectors that are impossible to be the k closest vectors in the design set; thus the k nearest neighbors can be found quickly. The k nearest-neighbor classification method with this fast algorithm can save substantially the classification time; meanwhile achieve the same classification performance as that with the exhaust search algorithm. Experiments on texture classification are performed and the results validate the proposed algorithm.