Speeding-up Nearest Neighbour Memories: The Template Tree Case Memory Organisation

S. Grolimund , J -G. Ganascia

IBP-Laforia 1996/13: Rapport de Recherche Laforia / Laforia research reports
16 pages - Octobre/October 1996 - French document.

Titre / Title: Speeding-up Nearest Neighbour Memories: The Template Tree Case Memory Organisation

Résumé : La mémoire de cas est un point important pour tout système de raisonnement à partir de cas. Deux grands types d'organisation de cette mémoire ont été proposés : l'un basé sur les techniques des plus proches voisins, et l'autre sur les techniques d'indexation selon attributs communs. Nous proposons une forme d'organisation basée sur les arbres de prototypes (Ramapriyan 1976), qui pour sa part cumule les avantages des deux approches précédentes. Elle permet d'une part l'intégration de fonctions complexes d'évaluation de la similarité entre deux cas, à l'exemple des méthodes des plus proches voisins, et d'autre part, elle accélère l'acquisition et la recherche de cas dans la mémoire à la manière des techniques d'indexation. L'évaluation expérimentale est conduite dans le domaine de l'apprentissage de connaissances de contrôle pour la résolution de problèmes d'optimisation à l'aide de la méthode tabou. Elle montre que l'organisation de la mémoire de cas du type arbres de prototypes accélère considérablement son fonctionnement par rapport à une technique du type plus proches voisins classique, sans pour autant altérer les performances du système

Abstract : Case retrieval is a crucial part of any CBR system as it provides the raw material for constructive solution generation by the reasoner. Case memories, as substrates for retrieval, are based on one of two main techniques: nearest neighbours classification or common feature indexing. While the former admits the incorporation of sophisticated similarity functions for accurate case retrieval, the latter provides rapid access to the stored cases. In this paper, we propose a case memory based on template trees. For this reason, we introduce the dynamic template trees, which are an adaptation of the classic template trees, originally introduced for classification in the pattern recognition field. They combine the benefits of both major approaches to case memory organisation. The hierarchical organisation of cases speeds-up case acquisition as well as case retrieval. Moreover, as they rely on the integration of an explicit similarity function, they maintain the advantages of nearest neighbour memories. Further, they can be iteratively. Results from experimental evaluation in case-based optimisation of the NP-hard capacitated facility location problem show that the proposed memory organisation exhibits a considerably better scale-up behaviour than does a conventional flat list memory. This scale-up is achieved without degrading solution quality.

Publications internes Laforia 1996 / Laforia research reports 1996