Case-base maintenance by conceptual clustering of graphs

Case-base maintenance typically involves the addition, removal or revision of cases, but can also include changes to the retrieval knowledge. In this paper, we consider the learning of the retrieval knowledge (organization) as well as the prototypes and the cases as case-based maintenance. We address this problem based on cases that have a structural case representation. Such representations are common in computer vision and image interpretation, building design, timetabling or gene-nets. In this paper we propose a similarity measure for an attributed structural representation and an algorithm that incrementally learns the organizational structure of a case base. This organization schema is based on a hierarchy and can be updated incrementally as soon as new cases are available. The tentative underlying conceptual structure of the case base is visually presented to the user. We describe two approaches for organizing the case base. Both are based on approximate graph subsumption. The first approach is based on a divide-and-conquer strategy whereas the second one is based on a split-and-merge strategy which better allows to fit the hierarchy to the actual structure of the application but takes more complex operations.