Abstract
Acquisition of case adaptation knowledge is a classic challenge for case-based reasoning. A promising response is learning adaptation rules from cases in the case base, using the case difference heuristic (CDH). In previous research we presented Ensembles of Adaptations for Regression (EAR), an approach that uses a CDH-based method to generate adaptation rules and then exploits the availability of multiple learned rules to apply ensemble-based adaptation. We extended EAR to classification tasks, with Ensembles of Adaptations for Classification (EAC), which showed promising accuracy results. EAR and EAC are practical for standard case bases, but become computationally expensive for large case bases and large ensembles, primarily due to retrieval cost. This paper presents research on scaling up EAC by integrating it with EACH, a new method for efficient approximate retrieval that extends locality-sensitive hashing retrieval to categorical features. Experimental results support the ability of the EAC with EACH (Ensemble of Adaptations for Classifications Hashing) to maintain accuracy while increasing efficiency. In addition, EACH could be applied as a standalone method to provide scalable approximate nearest neighbor retrieval in other CBR retrieval contexts.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Badra, F., Cordier, A., Lieber, J.: Opportunistic adaptation knowledge discovery. In: McGinty, L., Wilson, D.C. (eds.) ICCBR 2009. LNCS (LNAI), vol. 5650, pp. 60–74. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02998-1_6
Bogaerts, S., Leake, D.: Facilitating CBR for incompletely-described cases: distance metrics for partial problem descriptions. In: Funk, P., González Calero, P.A. (eds.) ECCBR 2004. LNCS, vol. 3155, pp. 62–76. Springer, Heidelberg (2004). doi:10.1007/978-3-540-28631-8_6
Broder, A.: On the resemblance and containment of documents. In: Proceedings of the Compression and Complexity of Sequences 1997, SEQUENCES 1997, pp. 21–29. IEEE Computer Society, Washington, DC (1997)
Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 327–336. ACM (1998)
Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC 2002, NY, USA, pp. 380–388. ACM, New York (2002)
Daengdej, J., Lukose, D., Tsui, E., Beinat, P., Prophet, L.: Dynamically creating indices for two million cases: a real world problem. In: Smith, I., Faltings, B. (eds.) EWCBR 1996. LNCS, vol. 1168, pp. 105–119. Springer, Heidelberg (1996). doi:10.1007/BFb0020605
Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG 2004, NY, USA, pp. 253–262. ACM, New York (2004)
Gilks, W.R., Richardson, S., Spiegelhalter, D.J.: Introducing markov chain monte carlo. Markov Chain Monte Carlo Pract. 1, 19 (1996)
Hanney, K., Keane, M.T.: Learning adaptation rules from a case-base. In: Smith, I., Faltings, B. (eds.) EWCBR 1996. LNCS, vol. 1168, pp. 179–192. Springer, Heidelberg (1996). doi:10.1007/BFb0020610
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC 1998, NY, USA, pp. 604–613. ACM, New York (1998)
Jalali, V., Leake, D.: CBR meets big data: a case study of large-scale adaptation rule generation. In: Hüllermeier, E., Minor, M. (eds.) ICCBR 2015. LNCS (LNAI), vol. 9343, pp. 181–196. Springer, Cham (2015). doi:10.1007/978-3-319-24586-7_13
Jalali, V., Leake, D., Forouzandehmehr, N.: Ensemble of adaptations for classification: learning adaptation rules for categorical features. In: Goel, A., Díaz-Agudo, M.B., Roth-Berghofer, T. (eds.) ICCBR 2016. LNCS (LNAI), vol. 9969, pp. 186–202. Springer, Cham (2016). doi:10.1007/978-3-319-47096-2_13
Jalali, V., Leake, D.: Extending case adaptation with automatically-generated ensembles of adaptation rules. In: Delany, S.J., Ontañón, S. (eds.) ICCBR 2013. LNCS (LNAI), vol. 7969, pp. 188–202. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39056-2_14
Lee, K.M.: Locality-sensitive hashing for data with categorical and numerical attributes using dual hashing. Int. J. Fuzzy Log. Intell. Syst. 2(2), 98–104 (2014)
Lichman, M.: UCI machine learning repository (2013). http://archive.ics.uci.edu/ml
McDonnell, N., Cunningham, P.: A knowledge-light approach to regression using case-based reasoning. In: Roth-Berghofer, T.R., Göker, M.H., Güvenir, H.A. (eds.) ECCBR 2006. LNCS (LNAI), vol. 4106, pp. 91–105. Springer, Heidelberg (2006). doi:10.1007/11805816_9
McSherry, D.: An adaptation heuristic for case-based estimation. In: Smyth, B., Cunningham, P. (eds.) EWCBR 1998. LNCS, vol. 1488, pp. 184–195. Springer, Heidelberg (1998). doi:10.1007/BFb0056332
Meng, X., Bradley, J.K., Yavuz, B., Sparks, E.R., Venkataraman, S., Liu, D., Freeman, J., Tsai, D.B., Amde, M., Owen, S., Xin, D., Xin, R., Franklin, M.J., Zadeh, R., Zaharia, M., Talwalkar, A.: MLlib: machine learning in apache spark. CoRR abs/1505.06807 (2015). http://arxiv.org/abs/1505.06807
Müller, G., Bergmann, R.: Learning and applying adaptation operators in process-oriented case-based reasoning. In: Hüllermeier, E., Minor, M. (eds.) ICCBR 2015. LNCS (LNAI), vol. 9343, pp. 259–274. Springer, Cham (2015). doi:10.1007/978-3-319-24586-7_18
Smyth, B., Cunningham, P.: The utility problem analysed. In: Smith, I., Faltings, B. (eds.) EWCBR 1996. LNCS, vol. 1168, pp. 392–399. Springer, Heidelberg (1996). doi:10.1007/BFb0020625
Smyth, B., Keane, M.: Remembering to forget: a competence-preserving case deletion policy for case-based reasoning systems. In: Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, pp. 377–382. Morgan Kaufmann, San Mateo (1995)
Smyth, B., McKenna, E.: Building compact competent case-bases. In: Althoff, K.-D., Bergmann, R., Branting, L.K. (eds.) ICCBR 1999. LNCS, vol. 1650, pp. 329–342. Springer, Heidelberg (1999). doi:10.1007/3-540-48508-2_24
Stanfill, C., Waltz, D.L.: Toward memory-based reasoning. Commun. ACM 29(12), 1213–1228 (1986)
Wilson, D.R., Martinez, T.R.: Improved heterogeneous distance functions. J. Artif. Int. Res. 6(1), 1–34 (1997)
Wilson, D., Martinez, T.: Reduction techniques for instance-based learning algorithms. Mach. Learn. 38(3), 257–286 (2000)
Wiratunga, N., Craw, S., Rowe, R.: Learning adaptation knowledge to improve case-based reasoning. Artif. Intell. 170, 1175–1192 (2006)
Zhu, J., Yang, Q.: Remembering to add: competence-preserving case-addition policies for case base maintenance. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, pp. 234–241. Morgan Kaufmann (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jalali, V., Leake, D. (2017). Scaling Up Ensemble of Adaptations for Classification by Approximate Nearest Neighbor Retrieval. In: Aha, D., Lieber, J. (eds) Case-Based Reasoning Research and Development. ICCBR 2017. Lecture Notes in Computer Science(), vol 10339. Springer, Cham. https://doi.org/10.1007/978-3-319-61030-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-61030-6_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61029-0
Online ISBN: 978-3-319-61030-6
eBook Packages: Computer ScienceComputer Science (R0)