×

Locally linear reconstruction for instance-based learning. (English) Zbl 1167.68424

Summary: Instance-Based Learning (IBL), so called memory-based reasoning, is a commonly used non-parametric learning algorithm. \(k\)-Nearest Neighbor (\(k\)-NN) learning is the most popular realization of IBL. Due to its usability and adaptability, \(k\)-NN has been successfully applied to a wide range of applications. However, in practice, one has to set important model parameters only empirically: the number of neighbors \((k)\) and weights to those neighbors. In this paper, we propose structured ways to set these parameters, based on Locally Linear Reconstruction (LLR). We then employed sequential minimal optimization for solving quadratic programming step involved in LLR for classification to reduce the computational complexity. Experimental results from 11 classification and eight regression tasks were promising enough to merit further investigation: not only did LLR outperform the conventional weight allocation methods without much additional computational cost, but also LLR was found to be robust to the change of \(k\).

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition

Software:

kknn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Loftsgaarden, D. O.; Quesenberry, C. P., A nonparametric estimate of a multivariate density function, Ann. Math. Statist., 36, 3, 1049-1051 (1965) · Zbl 0132.38905
[2] Cover, T. M.; Hart, P. E., Nearest neighbor pattern classification, IEEE Trans. Inform. Theory, 13, 1, 21-27 (1967) · Zbl 0154.44505
[3] Hardle, W., Applied Nonparametric Regression (1990), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0714.62030
[4] Mitchell, T. M., Machine Learning (1997), McGraw-Hill: McGraw-Hill Singapore · Zbl 0913.68167
[5] O’mahony, M.; Hurley, N.; Kushmerick, N.; Silvestre, G., Collaborative recommendationa robustness analysis, ACM Trans. Internet Technol., 4, 4, 344-377 (2003)
[6] Sarwar, B.; Karypis, G.; Konstan, J.; Riedl, J., Analysis of recommendation algorithms for e-commerce, (Proceedings of ACM Conference on Electronic Commerce (EC’00). Proceedings of ACM Conference on Electronic Commerce (EC’00), Minneapolis, Minnesota, USA (2000)), 158-167
[7] Ding, Y.; Li, X.; Orlowska, M. E., Recency-based collaborative filtering, (Proceedings of the 17th Australasian Database Conference. Proceedings of the 17th Australasian Database Conference, Hobart, Australia (2006)), 99-107
[8] Mohan, B. K.; Keller, B. J.; Ramakrishnan, N., Scouts, promotors, and connectorsthe roles of ratings in nearest neighbor collaborative filtering, (Proceedings of the ACM Conference on Electronic Commerce (EC’06). Proceedings of the ACM Conference on Electronic Commerce (EC’06), Ann Arbor, MI, USA (2006)), 250-259
[9] Xue, G.-R.; Lin, C.; Yang, Q.; Xi, W.; Zeng, H.-J.; Yu, Y.; Chen, Z., Scalable collaborative filtering using cluster-based smoothing, (Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’05). Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’05), Salvador, Brazil (2005)), 114-121
[10] D. Ruprecht, H. Müller, A framework for generalized scattered data interpolation, Technical Report no. 539, Universität Dortmund, Fachbereich Informatik, D-44221 Dortmund, Germany, \(1994 \langle;\) http://ls7-ftp.cs.uni-dortmund.de/pub/reports/ls7/1994/rr-517.ps.gz \(\rangle;\); D. Ruprecht, H. Müller, A framework for generalized scattered data interpolation, Technical Report no. 539, Universität Dortmund, Fachbereich Informatik, D-44221 Dortmund, Germany, \(1994 \langle;\) http://ls7-ftp.cs.uni-dortmund.de/pub/reports/ls7/1994/rr-517.ps.gz \(\rangle;\)
[11] Vijayakumar, S.; D’Souza, A.; Schaal, S., Approximate nearest neighbor regression in very high dimension, (Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (2006), MIT Press: MIT Press Cambridge, MA, USA), 103-142
[12] Wolberg, G., Digital Image Warping (1990), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA
[13] Jing, X.-Y.; Wong, H.-S.; Zhang, D., Face recognition based on discriminant fractional Fourier feature extraction, Pattern Recognition Lett., 27, 13, 1465-1471 (2006)
[14] Zhang, X.; Jia, Y., Face recognition with local steerable phase feature, Pattern Recognition Lett., 27, 16, 1927-1933 (2006)
[15] Jiang, S.; Song, X.; Wang, H.; Han, J.-J.; Li, Q.-H., A clustering-based method for unsupervised intrusion detections, Pattern Recognition Lett., 27, 7, 802-810 (2006)
[16] Aha, D. W.; Goldstone, R. L., Concept learning and flexible weighting, (Proceedings of 14th Annual Conference of the Cognitive Science Society. Proceedings of 14th Annual Conference of the Cognitive Science Society, Mahwaj, NJ, USA (1992)), 534-539
[17] Wand, M. P.; Schucany, W. R., Gaussian-based kernels, Canad. J. Statist., 18, 3, 197-204 (1990)
[18] Atkeson, C. G.; Moore, A. W.; Schaal, S., Locally weighted learning, Artif. Intell. Rev., 11, 5, 11-73 (1997)
[19] Fedorov, V. V.; Hackl, P.; Müller, W. G., Moving local regressionthe weight function, Nonparametric Statist., 2, 4, 355-368 (1993) · Zbl 1360.62120
[20] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[21] Roweis, S. T.; Saul, L. K., Think globally, fit locallyunsupervised learning of nonlinear manifolds, J. Mach. Learn. Res., 4, June, 119-155 (2003) · Zbl 1093.68089
[22] Domeniconi, C.; Peng, J.; Gunopulos, D., Locally adaptive metric nearest neighbor classification, IEEE Trans. Pattern Anal. Mach. Intell., 24, 9, 1281-1285 (2002)
[23] Han, E.-H.; Karypis, G.; Kumar, V., Text categorization using weight adjusted \(k\)-nearest neighbor classification, (Proceedings of 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2001). Proceedings of 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2001), Hong Kong, China (2001)), 53-65 · Zbl 0978.68700
[24] Howe, N.; Cardie, C., Examining locally varying weights for nearest neighbor algorithms, (Proceedings of International Conference on Case-Based Reasoning (ICCBR 1997). Proceedings of International Conference on Case-Based Reasoning (ICCBR 1997), Providence, RI, USA (1997)), 455-466
[25] Tan, S., Neighbor-weighted k-nearest neighbor for unbalanced text corpus, Expert Systems Appl., 28, 4, 667-671 (2005)
[26] Hattori, K.; Takahashi, M., A new nearest neighbor rule in the pattern classification problem, Pattern Recognition, 32, 3, 425-432 (1999)
[27] Cost, S.; Salzberg, S., A weighted nearest neighbor algorithm for learning with symbolic features, Mach. Learn., 10, 1, 57-78 (1993)
[28] K. Hechenbichler, K. Schliep, Weighted \(k\langle;\) http://epub.ub.uni-muenchen.de/archive/00001769/01/paper_399.pdf \(\rangle;\); K. Hechenbichler, K. Schliep, Weighted \(k\langle;\) http://epub.ub.uni-muenchen.de/archive/00001769/01/paper_399.pdf \(\rangle;\)
[29] Paredes, R.; Vidal, E., Learning weighted metrics to minimize nearest-neighbor classification error, IEEE Trans. Pattern Anal. Mach. Intell., 28, 7, 1100-1110 (2006)
[30] Fan, J.; Hall, P., One curve estimation by minimizing mean absolute deviation and its implication, Ann. Statist., 22, 2, 867-885 (1994) · Zbl 0806.62030
[31] Wang, Z.; Isaksson, T.; Kowalski, B. R., New approach for distance measurement in locally weighted regression, Anal. Chem., 66, 2, 249-260 (1994)
[32] Ichino, M.; Yaguchi, H., Generalized minkowski metrics for mixed feature-type data analysis, IEEE Trans. Systems, Man, Cybernet., 24, 4, 698-708 (1994) · Zbl 1371.68235
[33] Gowda, K. C.; Diday, E., Symbolic clustering using a new dissimilarity measure, Pattern Recognition, 24, 6, 567-578 (1991)
[34] Gowda, K. C.; Diday, E., Unsupervised learning through symbol clustering, Pattern Recognition Lett., 12, 5, 259-264 (1991)
[35] Vapnik, V., Estimation on Dependences Based on Empirical Data (1982), Springer: Springer New York, NY, USA · Zbl 0499.62005
[36] Osuna, E.; Freund, R.; Girosi, F., An improved training algorithm for support vector machines, (Proceedings of IEEE Neural Networks for Signal Processing (NNSP’97). Proceedings of IEEE Neural Networks for Signal Processing (NNSP’97), Amelia Island, FL, USA (1997)), 276-285
[37] Platt, J. C., Fast training of support vector machines using sequential minimal optimization, (Advances in Kernel Methods—Support Vector Learning (1998), MIT Press: MIT Press Cambridge, MA, USA), 41-65
[38] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9, 251-280 (1990) · Zbl 0702.65046
[39] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning (2001), Springer: Springer New York, NY, USA
[40] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification (2001), Wiley: Wiley New York, NY, USA · Zbl 0968.68140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.