2014 | OriginalPaper | Buchkapitel
Efficient kNN Algorithm Based on Graph Sparse Reconstruction
verfasst von : Shichao Zhang, Ming Zong, Ke Sun, Yue Liu, Debo Cheng
Erschienen in: Advanced Data Mining and Applications
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper proposes an efficient k Nearest Neighbors (kNN) method based on a graph sparse reconstruction framework, called Graph Sparse kNN (GS-kNN for short) algorithm. We first design a reconstruction process between training and test samples to obtain the k value of kNN algorithm for each test sample. We then apply the varied kNN algorithm (
i.e.,
GS-kNN) for the learning tasks, such as classification, regression, and missing value imputation. In the reconstruction process, we employ a least square loss function for achieving the minimal reconstruction error, use an ℓ
1
-norm to generate different k values of kNN algorithm for different test samples, design an ℓ
21
-norm to generate the row sparsity for the removal of the impact of noisy training samples, and utilize Locality Preserving Projection (LPP) to preserve the local structures of data. With such an objective function, the GS-kNN obtains the correlation between each test sample and training samples, which then is used to design new classification/regression/missing value imputation rules for real applications. Finally, the proposed GS-kNN method is evaluated with extensive experiments, including classification, regression and missing value imputation, on real datasets, and the experimental results show that the proposed GS-kNN algorithm outperforms the previous kNN algorithms in terms of classification accuracy, correlation coefficient and root mean square error (RMSE).