A dynamic adaptive framework for improving case-based reasoning system performance

A Dynamic Adaptive Framework for improving Case-Based Reasoning System Performance Fernando Orduña Cabrera Computer Science Department Universitat Politècnica de Catalunya · BarcelonaTech Ph.D. Programme in Artificial Intelligence Ph.D. Thesis presented for obtaining the degree of Doctor Advisor: Dr. Miquel Sànchez-Marrè 2015 2 3 Preface This thesis document is the document which presents the student Fernando Orduña Cabrera for obtaining the degree of doctor by the Universitat Politècnica de Catalunya · BarcelonaTech, in the Doctoral Programme of Artificial Intelligence. 4 5 Acknowledgments First, I want to thank my supervisor for the support needed to realize this project, the large amount of overtime that he addressed to me. Thanks for your patience and support, and by the enthusiasm and dedication. I also want to thank CONACYT for the support with grant number 205684, also wish to thank the "Faculty Development Program, PRODEP" for their support to the thesis writing scholarship "DSA / 103.5 / 15/6635". And all those who were directly and indirectly involved in this project. Thanks. 6 7 Abstract An optimal performance of a Case-Based Reasoning (CBR) system means, the CBR system must be efficient both in time and in size, and must be optimally competent. Efficiency in time requires that CBR tasks must be carried out in a fast way: retrieval time, adaptation/reuse time, evaluation/revise time and learning/retain time should be as low as possible. From these tasks, usually the retrieval task is taking longer than the other ones. Therefore, the efficiency in time is closely related to an efficient and optimal retrieval process over the Case Base/Case Library of the CBR system. Efficiency in size means that the Case Library (CL) size should be minimal. Thus, a minimum number of cases must be stored in the CL. Therefore, the efficiency in size is closely related to optimal case learning policies, optimal meta-case learning policies, optimal case forgetting policies, etc. On the other hand, the optimal competence of a CBR system means that the number of problems that the CBR system can satisfactorily solve must be maximum. To improve or optimize all three dimensions in a CBR system at the same time is a difficult challenge because they are interrelated, and it becomes even more difficult when the CBR system is applied to a dynamic domain or continuous domain (data stream). In this thesis work, a dynamic adaptive framework is proposed to improve the CBR system performance coping especially with reducing the retrieval time, increasing the CBR system competence, and maintaining and adapting the CL to be efficient in size, especially in continuous domains. One of the main contributions of the work is the proposal of a Dynamic Adaptive Case Library (DACL) framework. A DACL is composed of a set of dynamically built case libraries to cope with the heterogeneity and complexity of real domains. It learns cases and organizes them into dynamic cluster structures. The DACL is able to adapt itself to a dynamic environment, where new clusters, meta-cases or prototype of cases, and associated indexing structures (discriminant trees, k-d trees, etc.) can be formed, updated, or even removed. DACL offers a possible solution to the management of the large amount of data generated in an unsupervised continuous domain (data stream). In addition, we propose the use of a Multiple Case Library (MCL), which is a static version of a DACL, with the same structure but being defined statically to be used 8 in supervised domains. The core of the retrieval process in both MCL and DACL is the matching of the current/query case against a set of prototype cases called meta-cases, to select the case library to search in. In a MCL, the number of meta-cases and its corresponding case libraries is fixed a priori according to the different class labels, rather than dynamically like in a DACL. The structure of a DACL/MCL is organized hierarchically at different levels: the meta-case, the prototype of a concrete cluster of cases and the indexing hierarchical structures (discriminant trees, k-d trees, etc.) that represent the way that all the cases in a given cluster are organized. The framework proposed is flexible enough to allow the implementation of many different retrieval techniques, because of the facilities that the Multiple Case Library (MCL) and the Dynamic Adaptive Case Library (DACL) offers for indexing. The thesis work proposes some techniques for improving the indexation and the retrieval task. The most important indexing method is the NIAR k-d tree algorithm, which improves the retrieval time and competence, compared against the baseline approach (a flat CL) and against the well-known techniques based on using standard k-d tree strategies. In addition, a partial matching exploration technique is proposed. NIAR k-d tree algorithm performs quite similar to the standard k-d tree selecting by discrimination the attributes through cycling the list of major attributes, but differs of standard k-d tree approach in the technique of selecting the split value. The Partial Matching Exploration (PME) technique explores a hierarchical case library with a tree indexingstructure aiming at not losing the most similar cases to a query case. This technique allows not only exploring the best matching path, but also several alternative partial matching paths to be explored. Both techniques: NIAR k-d tree indexing structure and Partial Matching Exploration (PME) technique have been evaluated. The results show an improvement in competence and time of retrieving of similar cases. Through the experimentation tests done, with a set of well-known benchmark supervised databases, it has been shown that the use of a Multiple Case Library (MCL) embedding a NIAR k-d tree, and using the additional strategy of PME to explore the indexing structure provides a very good approach both to improve the time efficiency and the competence in CBR systems. 9 The dynamic building of prototypes in DACL has been tested in an unsupervised domain (environmental domain) where the air pollution is evaluated. Here, the prototypes are incrementally generated and managed by the DACL. The core task of building prototypes in a DACL is the implementation of a stochastic method for the learning of new cases and management of prototypes. Therefore, it allows creating and managing a DACL. The stochastic method works with two main moments, the first moment guides the learning of new cases and decides where to store the cases. The second moment evaluates the prototypes selecting or building a new prototype. The proposed method for building prototypes has been conducted using the database acquired in an air pollution environmental domain. The experimental results shown, that using DACL in the environmental domain performs well and helps the experts to identify critical moments where the pollution is dangerous for people. Finally, the whole dynamic framework, integrating all the main proposed approaches of the research work, has been tested in simulated unsupervised domains. Several databases from the UCI Machine Learning repository were tested in an incremental way, as data streams are processed in real life. The conclusions outlined that from the experimental results, it can be stated that the dynamic adaptive framework proposed (DACL/MCL), jointly with the contributed indexing strategies and exploration techniques, and with the proposed stochastic case learning policies, and meta-case learning policies, improves the performance of standard CBR systems both in supervised domains (MCL) and in unsupervised continuous domains (DACL). 16 17 List of Tables Table 1. Contributions to CBM field part 1 ........................................................... 61 Table 2. Contributions to CBM field part 2. .......................................................... 62 Table 3. Contributions to CBM field part 3. .......................................................... 63 Table 4. Description of databases used in the experimentation. #Inst is to the total number of instances in the database, #Cont means the total number of continuous/numerical attributes in the database, #CatOrd mens the total number of categorical ordered attributes, #CatNOrd means the total number of categorical non ordered attributes and #Classes refers to the total number of different class labels in the database. .............................................................................................................. 118 Table 5. Average CPU Time for case retrieval .................................................... 119 Table 6. Depth of trees generated using in approaches ....................................... 121 Table 7. Distribution of expanded nodes by level in the approaches and compared with the most compact possible binary tree, for the Car database ............................ 122 Table 8. Average CPU Time for case retrieval .................................................... 124 Table 9. Depth of trees generated using both approaches ................................... 125 Table 10. Distribution of expanded nodes by level in both approaches and compared with the most compact possible binary tree, for the Abalone database .... 126 Table 11. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases.......... 130 Table 12. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases (continued from table 11). ........................................................................................ 131 Table 13. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases (continued from table 12). ........................................................................................ 131 Table 14. Statistics of tables 11, 12 and 13. ........................................................ 132 Table 15. Time performance. .............................................................................. 135 Table 16. Increase of the accuracy. ..................................................................... 136 Table 17. Accuracy of MCL ................................................................................ 138 Table 18. Number of Prototypes and the γ policy evaluation values. For each γ policy value there is the number of cases of each prototype. .................................... 143 Table 19. Distance measures between the Mc’s obtained for γ=0.1 .................... 145 Table 20. Results of the different formulas assessment ....................................... 145 Table 21. Standard Deviation of Prototypes ........................................................ 146 Table 22. List of tested databases along with experimentation details ................ 149 Table 23. Mean precision values for Iris and Balance databases ......................... 150 18 19 1 Introduction Since the introduction of Case-Based Reasoning (CBR) principles by Schank in (Schank 1974; Schank 1982) in late 70s, CBR has been consolidating as a reliable reasoning paradigm in the Artificial Intelligence field (Richter & Weber, 2013; López, 2013; López de Mántaras, 2005; Aamodt & Plaza, 2004; Kolodner, 1993). Several research works (Orduña and Sànchez-Marrè, 2008a, 2008b) have been proposing techniques/methods to use CBR as a solution for learning of experiences, and as a method to make an interpretation of the expert knowledge, translating the knowledge to CBR systems. In the CBR literature (see for instance (Fornells et al. 2008)), for methodological purposes it is distinguished between Data-Intensive CBR systems (DI-CBR) and Knowledge-Intensive CBR systems (KI-CBR). DICBR systems share characteristic features like extensive use of learning from examples, spare use of domain knowledge and simpler case and solution representations. They are different from the main features shared by KI-CBR systems, like intensive use of domain knowledge, complex case and solution structures and current developments being now based on ontologies and description logics. Our approach falls within the Data-Intensive CBR systems (DI-CBR) class, because in continuous/dynamical domains usually the huge amount of data is slightly more important than the domain knowledge. In our approach, both the case problem description and the case solution are implemented with a list of attribute-value pairs. In this thesis work, a dynamic adaptive framework is proposed to improve the CBR system performance coping especially with reducing the retrieval time, increasing the CBR system competence, and maintaining and adapting the case library to be efficient in size, especially in continuous domains. The framework proposed works for reasoning and learning both in supervised domains and unsupervised domains. The proposal is entitled as a Dynamic Adaptive Case Library Framework (DACL). A DACL is composed of a set of dynamically built case libraries. It learns cases and organizes them into dynamic cluster and tree-indexing structures. The DACL is able to adapt itself to a dynamic environment. 20 The proposal offers a solution to the management of the large amount of data incrementally generated in unsupervised domains. In addition, it is proposed the use of a Multi-Case Library (MCL) for supervised domains. Both DACL and MCL aim to retrieve cases by matching the current/query case against a set of prototype cases called meta-cases. The structure of DACL/MCL is organized hierarchically at different levels: the meta-case and the use of hierarchical indexing structures. Both structures improve the proposed framework. One improvement is showing flexibility enough to allow the implementation of many different retrieval techniques. One of the main techniques proposed is a NIAR k-d tree algorithm, which improves the retrieval time and competence. Another technique is the Partial Matching Exploration (PME) technique. Those techniques have been evaluated. The results show an improvement in competence and time of retrieving of similar cases. Both techniques combined provide a very good approach to improve the time efficiency and competence in CBR systems. Other contribution included in the framework is the dynamic building of prototypes in DACL. These prototypes are incrementally generated and managed by DACL. The technique aims to implement a stochastic method for the learning of new cases and management of prototypes. Others techniques are included in the proposal; those techniques implement methods for building representative prototypes. All the techniques proposed have been tested and the results indicates an improvement of the performance of the standard CBR system both in supervised domains with MCL and in unsupervised continuous domains with DACL. 1.1 Motivation Case-Based Reasoning (CBR) systems solve new problems by retrieving and adapting the solutions to previously solved problems that have been stored in a case library (Richter &Weber, 2013; López 2013; López de Mántaras et. al., 2005, Aamodt and Plaza, 1994, Kolodner, 1993). Systems until now have been used in different fields as it is mentioned in (Orduña and Sànchez- Marrè, 2008b). CBR systems are a good tool for the experts interested in management of knowledge in an automatic way. The work of Orduña and Sànchez-Marrè in (Orduña and Sànchez-Marrè, 2008b) refers to several 21 fields where CBR systems have been used successfully, but there are domains where CBR systems need to be more efficient. Continuous domains are domains where is necessary to continuously work to improve the CBR systems. Continuous domains are complex because they generate large amount of information in a short time period. Case Based Maintenance (CBM) is a Case-Based Reasoning subarea where the community of CBR has been working with the aim of finding better methods that improve the performance of the CBR cycle. In the last years, several research works have proposed different methods to handle the information in a CBR system. Some of these contributions are detailed in (Jalali, 2014; Salamó, 2011; Orduña and Sànchez-Marrè, 2008c; Perner, 2006; Iglezakis et al., 2004; Portinale and Torasso, 2001; Smyth and Mckenna, 2001; Leake and Wilson, 2000; Yang and Wu, 2000). The performance of a CBR system is usually measured along two dimensions: efficiency and competence. Efficiency of a CBR system means that the CBR system requires the minimal resources needed to solve any case in the domain of application. The resources are twofold: the time required for solving a case, and the size of the case library needed to solve a case. Therefore, efficiency is related both to the case solving time and to the size of the case library. The competence of a CBR system refers to the range of problems that can be satisfactorily solved, for instance see (Salamó & López-Sánchez, 2011). All these performance dimensions are interrelated. For instance, if the case library size is getting smaller by decreasing the number of cases learnt, then the time efficiency could be decreased but the competence of the CBR system could be reduced. On the contrary, if the case library size is larger by increasing the number of learnt cases, then the time efficiency could be worsened, but the competence of the CBR system could be increased. The retrieval is one of the important steps in Case-Based Reasoning systems. Several algorithms have been proposed for the indexing of cases, since the original indexing approach of k-d trees appeared in the literature. Main approaches propose to use a pre-computed binary search tree to get an average logarithmic time effort in searching. The basic idea of the proposal is to implement a Dynamic Adaptive Case Library for Continuous domains strengthen its structure by the imple- 22 mentation on its second level of indexing algorithms based on the principle of binary search trees for efficient retrieval according to a given similarity measure sim. Even more, a proposed NIAR k-d tree algorithm is based on the computation of the average value of the corresponding attribute among the sub-tree cases. An evaluation of algorithms such as the k-d trees and NIAR k-d trees has been done in (Orduña and Sànchez-Marrè, 2013); to make a comparative of efficiency and performance evaluation. In some research works, an effort to give an approximation to reduce the complexity of learning in continuous domains is observed (Salamó & López-Sánchez, 2011; Segata, 2010). One of them is the research work (Sànchez- Marrè et. al., 2000), where their proposal consists in a Meta-reasoning by means of a set of meta-cases approach. This research differs from our research proposal given that in their proposal a static structure is presented, consisting in a given number of meta-cases. In their proposal (Orduña and Sànchez-Marrè, 2009), (Orduña and Sànchez-Marrè, 2014a), (Orduña and Sànchez-Marrè, 2014b) the structure is dynamic and the library is able to deal with a variable number of meta-cases, clusters and discriminant trees. In his research presents one rule to know whether a case is similar to one of the given meta-cases. This rule is considered in (Orduña and Sànchez- Marrè, 2009). The Meta-case is the top level of the indexing method proposed where its attributes are used in the learning process. In that proposal, the values of its attributes were considered as previously established by experts. The DACL proposed in (Orduña and Sànchez-Marrè, 2009) is illustrated in figure 13. DACL learns cases and organizes them into the dynamic cluster structures. The library is able to adapt itself to a dynamic environment, where new clusters, meta-cases, and associated indexing structures (discriminant trees, k-d trees, etc.) can be formed, updated, or even removed (Orduña and Sànchez-Marrè, 2015a). DACL offers a possible solution to the management of the large amount of data generated in a continuous domain. With the stochastic learning process of new cases and metacases introduced in (Orduña and Sànchez-Marrè, 2013) is feasible to improve the retrieval time and size of the case library. Even more, a fusion of all proposed techniques with DACL proposed in (Orduña and Sànchez-Marrè, 2009) is feasible to improve CBR system performance, especially when facing unsupervised continuous domains with large case bases. 23 1.2 Issues of the work In this thesis work, we aim at improving the general CBR system performance, by jointly coping with the time efficiency, size efficiency and competence dimensions, especially when coping with unsupervised continuous domains. We aim at improving the case library structure with some new proposals for dynamically structuring the case library in such a way that the performance of the system increases. These new structures should be able to handle a data stream of cases within the unsupervised domains. In addition, the work has the aim to find indexing strategies, which improve the performance of CBR systems. The aim is to search for variations in the building of k-d trees, to make them more balanced structures and faster accessing methods. Moreover, the research work will aim at proposing new exploration techniques of k-d trees, and in general of hierarchical structures, different from usual ones (like hyberball techniques, etc.) so that the retrieval time could be reduced, even though the accuracy of the system could be slightly worsened. Another issue is to propose new case learning strategies based on reliable facts like, for instance, the relevance concept. A very important aspect related to unsupervised continuous domains is the incrementality problem. General CBR systems assume that the set of cases available for building the case library is fixed. Then they build the memory indexing structures, like for instance, a k-d tree, etc. However, when a CBR system is facing an unsupervised continuous domain, the system should build and update the case library structure/s in an incremental way. The proposal of some new introspective tasks and strategies are also another sub goal of our work, in order to update and maintain the CBR system in optimal conditions. In our thesis proposal, the structure of the Dynamic Adaptive Case Library (DACL) can be built-up in an incremental way, and some introspective reasoning tasks can be scheduled to regularly update the indexing structures (NIAR k-d trees, etc.). 24 1.3 Contributions The main contribution of this thesis is a general Dynamic Adaptive Framework for improving Case-Based Reasoning System Performance. This framework is general enough for coping with supervised domains, where DACL is named as Multi-Case Library (MCL), because here the structure is not dynamic, and for coping with unsupervised, usually continuous, domains, where a stream of cases are needed to be processed and solved. The global contribution of this research framework can be split in the following research contributions: 1. The DACL: a Dynamic Adaptive Case Library technique to be able to store a big amount of cases and to manage them for unsupervised domains, and especially, for continuous domains. The cases will be stored according to different policies/methods. The cases will be stored in the best-matching sub-library. This will be accomplished by means of the use of prototypes of the cases indexed through dynamic tree structures. The prototype will be called Meta-case. The Metacases will have associated indexing schemes (discriminant trees, k-d trees, etc.). The DACL structure was introduced in (Orduña and Sànchez- Marrè, 2009) (see section 3.1). 2. The MCL: a Multi Case Library will be a similar structure of DACL, but in that situation, the building of the structure will follow a special procedure for static supervised domains. The main use of Meta-cases is the same than in a DACL (see section 3.2) 3. New proposed variants of a k-d tree structure to improve the efficiency of the CBR system performance. Both AvKd-tree (Average k-d tree) and NIAR k-d tree (Nearest Instance to the Average Root) algorithms will be proposed to improve the competence in retrieval time and quality of retrieval in CBR. AvKd-Tree and NIAR k-d tree will differ of standard k-d tree in the technique of selecting the split value for each attribute at the internal nodes. The idea of the algorithms was introduced in (Orduña and Sànchez-Marrè, 2013) (see sections 4.1 and 4. 4.2). 25 4. The proposal of a new exploration technique for traversing a k-d tree, and obtaining the most similar cases of the k-d tree exploring alternative paths to the main path. This technique will be named as Partial Matching Exploration technique (PME) (see section 4.3) 5. The proposal of a SMcLM Stochastic Meta-case Learning Method, which will consider two relevant moments to guide the learning of the new case (Nc): building a new Meta-case (Mc) or storing it in the existing Meta-cases. The aim of this policy will be to learn those cases that accomplish the two moments of the stochastic process. This method has been implemented in the study of the air pollution domain (Orduña and Sànchez-Marrè, 2015a), where the results obtained shows the efficiency of the method. This method is a second method of building representative prototypes, because a first DACL method was described in (Orduña and Sànchez-Marrè, 2009) (see sections 5.1 and 5.2) 6. Other techniques for selecting the Meta-cases and building representative prototypes (see section 5.3). 7. The proposal and inclusion of some introspective tasks for global maintenance of the DACL (see section 5.4). 1.4 Thesis Organization This thesis document is organized as follows: Chapter 2: Describes and details the topics strongly related and inherent to the DACL Framework: Case-Based Reasoning, Case representation and Case Library organization, Case Base Maintenance and related concepts, Introspective reasoning, stochastic learning and Continuous domains. Chapter 3: In this chapter, the DACL is detailed. The three-layer structure of a DACL is described: the Meta-cases, the cluster of cases and the corresponding sub-library for each meta-case. Two basic algo- 32 values of the new case and the most similar one are used to appropriately guide the modification of the parameters in the solution. The transformation methods use either some common sense transformation rules, such as deleting a component, adding a component or adjusting values of a component, as in the JULIA system (Shinn, 1988), or some modelguided repair transformation techniques based on a causal model(s). The special-purpose adaptation techniques or critic-based adaptation methods are based on some specific rules of repairing, called critics (Sacerdoti, 1997), such as those used in PERSUADER (Sycara, 1987). Other systems such as CHEFF (Hammond, 1989) and JULIA (Shinn, 1988) use some domain specific adaptation heuristic and some structure modification heuristic. Finally Derivational adaptation methods do not operate on the original solutions, but on the method used to derive that solution. The goal is rerunning the same methods applied to derive the previous solution, to re-compute the solution for the new case. This methodology was implemented in the ARIES system, and was named as derivational replay (Carbonell, 1986). Revise the proposed solution (Case Revision). This step gives to CBR systems a way to evaluate its decisions in the real world, allowing feedback that enables the learning from success or failure. The experts decide if the proposed solution is the most appropriate, generally evaluate the solution applied to the real world. If there is not an expert available, then a simulation of the application of this solution can be performed, or a direct experimentation in the real world. The results will determine the quality of the solution and it will be observed. Retain the parts of this experience likely to be useful for future problem solving (Case Retention). The information given to the system about the quality of the proposed solution in the revision step is an important part in the learning process of the CBR system. Learning in a CBR environment could be in two different methods such us the learning by observation and learning by experience. Learning by observation is done when the system starts with a representative set of initial cases. These cases result from the direct observation of the domain or when an expert provides the knowledge. This kind of learning can also be given in the course of the use of the system, when new cases are observed, and are considered as representative or essential situations to describe the real environment of the problem. The expert can also add new cas- 33 es, if it is possible to describe them even when they have not been observed, and if they are not already in the case base. And the Learning by experience: is done after each cycle of the CBR system. After the revision step, it is determined if the solution was successful or not. In the first case, the CBR system memorizes the success, with the system being given the opportunity of storing the new case together with its solution in the case base, and marking it as a correct answer. If the answer was not appropriate, the system must be able to prevent itself from making the same mistake in the future, learning from failure. If the evaluation process concludes that the proposed solution is not the appropriate one, it is important to know what caused the error. It could be due to a bad adaptation of the proposed solution from the most similar case to the new one, or it is possible that within the case base there is not a very similar case. Even so, the system will recover this. Although it seems to be similar enough, it exist a difference. In this case, it is important to inform to the expert if there exists one, and try to generate a representative case of the current situation and to provide an appropriate solution. Another circumstance directly related to the purpose of this work can happen if exists a case in the case base, being more similar to the one recovered. If this is the situation, the similarity measure, the attribute weights, the normalization process, the discretization process, and the way to handle missing values must be revised. 2.1.1 Knowledge Organization Cases in a CBR system must be represented and organized in such a way that the case representation methodology allows the comparison between cases, and the overall case organization permits the case retrieved in an optimal way. 2.1.1.1 Case Representation A case is a piece of knowledge about a context, which represents an experience that teaches a fundamental lesson to the reasoner in view to get its goal (Kolodner, 1993). A case should represent a specific knowledge linked to a context, to store a different experience. It should be useful to the reasoner, and it is necessary to be able to compare it with other cases to determine its similarity. 34 A CBR system is highly dependent on the elected formalism to represent the cases in its case base. Since the core of the system consists of finding a similar previous case to the current one, the methodology used to make the search in the case base will depend on the structure used to represent each case and its solution. The first task when building a CBR application is to decide how the cases will be represented. This decision will have a direct impact on the strategies to continue in the following design phases of the application such as case base organization, similarity evaluation, recovery of the most similar case to the current one, solution adaptation and system learning. The most common case representation formalisms are the following: • Attribute-Value Vectors is one of the most common case representations and organization mechanisms. For their simplicity and easy handling, the attribute-value vectors are a broadly used formalism. This formalism assumes that each case (𝐶𝐶𝑖𝑖) is defined by a set of 𝑚𝑚 attributes that can be continuous or discrete; 𝐶𝐶𝑐𝑐 𝑖𝑖 is an optional class label for the case 𝐶𝐶𝑖𝑖 in a supervised domain. 𝐶𝐶𝑖𝑖=�𝐶𝐶1 𝑖𝑖,𝐶𝐶2 𝑖𝑖,⋯,𝐶𝐶𝑚𝑚 𝑖𝑖;𝐶𝐶𝑐𝑐 𝑖𝑖� As an example, consider an automobile buyer who consults a CBR system to find out their best option. The corresponding vectors to the attribute description and value vectors are: Attributes: < Type, brand, cylinders, power, fuel, color, price, year, seats > Cases: < sport, BMW, 8, 275, gasoline, blue, 35000, 2000, 4 > < sport, AstonM, 12, 450, gasoline, red, 120000, 2002, 2 > < sport, Maserati, 12, 380, gasoline, green, 80000,2002,2 > < tourism, Citroen, 4, 95, diesel, red, 20000, 2002, 5 > < tourism, Renault, 4,65, gasoline, white, 12000, 2002, 5 > < tourism, Renault, 6, 85, gasoline, white, 17000,2002,5 > < tourism, Renault, 4, 60,gasoline,white,8000,2000,5 > 35 • Free Text. In some applications such as judicial cases (Weber-Lee et al., 1998), text categorization, electronic trade, answers to frequent questions systems (FAQ’s) (Lenz and Burkhard, 1997) and medical and technicians reports, attributevalue vectors are not an appropriate option. In these domains, free text using natural language is a good way of representing cases. The case is described by means of sentences trying to include words that are good enough for the case discrimination and representing the problem domain in a faith-full way. In the automobiles context a formalism to case representation could be: ”A red sports car with 300 horse power and 12 cylinders, with a price less than 250000 and must be BMW” The system operation is exposed in (Lenz and Burkhard, 1997). The case base consists of a set of texts containing possible answers to the questions made by the user. The described system takes the user’s question expressed in natural language, and retrieves the text that better matches as an answer to the formulated question. The retrieval is carried out evaluating the similarity between the question and the cases in the case base, recovering those that are more similar. For each case, a set of Information Entities (IE) produced by the key words in the text are identified. • Conversational CBR. In recent years, due to Internet expansion, many web-based consultation applications have emerged. In them, the user introduces a brief text explaining his problem. With this text, the system finds the most similar case in its case base. Then, the system presents a set of questions associated to the recovered case. The user can answer to these questions in a quick and direct way. These systems are known as CCBR (Conversational CBR). The system should automatically infer the details that describe the problem starting from the text introduced by the user. During the conversation, the system evaluates and shows the most similar cases and their solutions, progressively until finding the most appropriate solution according to the user’s opin- 36 ion. In these systems (Aha et al., 1999), a case x is represented as follows: 1. Problem 𝑋𝑋𝑝𝑝=𝑋𝑋𝑑𝑑+𝑋𝑋𝑞𝑞𝑞𝑞 encodes the problem solved by 𝑋𝑋𝑠𝑠. Where: description 𝑋𝑋𝑑𝑑 is a portion of free text that partially describes X’s problem. Specification 𝑋𝑋𝑞𝑞𝑞𝑞 is a set of <question, answer> pairs. 2. Solution 𝑋𝑋𝑠𝑠=𝑋𝑋𝑞𝑞1,𝑋𝑋𝑞𝑞2⋯,𝑋𝑋𝑞𝑞𝑎𝑎 is a sequence of actions 𝑋𝑋𝑞𝑞𝑖𝑖 for responding to 𝑋𝑋𝑝𝑝. Actions can be free text, hyperlinks or other objects. A case’s problem description and specification serve as its index. Questions in case specification can be internally disjunctive (i.e. have multiple answers). Cases are “positive” examples: applying 𝑋𝑋𝑠𝑠 to 𝑋𝑋𝑝𝑝 is assumed to be successful. 𝑋𝑋 serves as a prototype for solving queries whose problem specification is similar to X’s. In figure 2, the generic process of problem resolution in a CCBR system is presented. Fig. 2. Conversational CBR Problem Solution Generic Process 37 • Graphs. In previous sections, it was shown how the case representation formalism in a CBR system is linked to the domain. Some domains exist where the objects representing the problem are highly related to each other. This relationship cannot be efficiently represented in any of the previously described models. In those domains, graphs could be used as a case representation formalism. Fig. 3. A graph representation A graph is defined as a structure 𝐺𝐺= < 𝑉𝑉𝐺𝐺,𝐴𝐴𝐺𝐺 > where 𝑉𝑉𝐺𝐺 is a finite set of vertices and 𝐴𝐴𝐺𝐺 ⊆𝑉𝑉𝐺𝐺∗𝑉𝑉𝐺𝐺 is a set of edges. In general, vertices are used to represent the objects of the domain, and edges express the relationships and restrictions among them, as was used in the planning of timetabling of a school course (Burke et al., 2001). In some domains, edges can represent binary predicates as in CHIRON and CAPER (Sanders and Hendler, 1997). An example of this kind of representation is shown in the figure 3. 38 By means of this formalism, one could represent elements of the domain that are unlikely to appear in another representation: hard and soft constraints that are indicated by solid or dotted edges respectively. In the notation 𝑋𝑋:𝑌𝑌, 𝑋𝑋 is the label and y represents the value of the attribute; Physics, Lab and MathA are labelled by 1, indicating that they are multiple courses. Values 2, 3, 2 give the times they should be held per week respectively. Other courses labelled 0 (ordinary courses) should be held just once a week. The courses adjacent to edges labelled 7 cannot be held simultaneously. Database should be consecutive to Lab if possible (the edge between them is labelled 5), and MathA should not be consecutive to MathB if possible (the edge between them is labelled 6). The direct edge between ComputerA and ComputerB is labelled 4, denoting that ComputerA should be held before ComputerB. One of the main disadvantages of using this formalism is that when recovery is done, it is evident that this is an isomorphism graph problem (a graph representing a current case compared with graphs representing previous cases), and it is broadly well known that this is a NP-complete problem. 2.1.1.2 Case base Organization Several methods to organize the Case base can be implemented; the aim of the organization of the cases is that the implementation of method improves the search and retrieving of cases. Hierarchical and flat organizations are main used formalisms, but any other combination of structures is possible. 2.1.1.2.1 Flat Memory This is the most intuitive organization scheme, since involves storing all the available cases sequentially, in a simple list, array, or file. In a flat memory, the new case is matched against each case in the memory, and the best matches are returned. An algorithm to guide this search is presented in algorithm 1. This algorithm is very simple, and it is the similarity evaluation heuristic which carries out all the work. The main advantage is that, the entire 39 library is used to search, and the accuracy will only depend on how good the similarity measure is computed. There are some disadvantages that should be evaluated. The main one is that this scheme tends to be time-consuming in the retrieval step. As the case library gets large, so does the time needed for retrieval. A scheme like this works well in applications where the case base is not very large. However, it is necessary to closely watch over the case base growth, incorporating maintenance schemas, evaluating the relevance of incorporating a new case avoiding redundancy, but being flexible enough to accept a new case that represents a new domain situation that was not present among the existent cases in the case base. Algorithm 1: linear search in a flat memory Input: Set of cases of the Case Library (S), 1 The New Case (Nc) 2 Output: Index of nearest case (r) 3 Begin linear search(S, Nc) 4 Let N = the number of cases of the Case Library; 5 Let BestDissimilarity = the best dissimilarity value be-6 tween Nc and all the cases until the current case 7 Let CurrentDissimilarity = the dissimilarity value be-8 tween Nc and the current case (Ci) 9 Let d() = the distance computation function among two 10 cases 11 N = |S| 12 BestDissimilarity = + ∞ 13 i = 1 14 while i ≤ N do 15 CurrentDissimilarity = d(Ci,Nc) 16 if CurrentDissimilarity < BestDissimilarity then 17 r = i 18 BestDissimilarity = CurrentDissimilarity 19 endif 20 i = i + 1 21 enwhile 22 return r 23 end linear search 24 40 2.1.1.2.2 Hierarchical Organization Through time, a CBR system increases its data by means of the inherent learning in the learning phase. Thus, the number of cases in the case base will increase. In this situation, a flat structure and sequential search is impractical. As the case base grows, there is a need to organize cases hierarchically so that only a small subset needs to be considered during retrieval. This subset, however, must be likely to have the best-matching or most useful cases in its organization (Kolodner, 1993). Next some alternatives are presented to solve the hierarchical organization problem. Shared Feature Networks. The main idea is as follows; if you can cluster together cases that are similar to one another and figure out which cluster best matches the new situation, then only items in that cluster need to be considered in finding a best-matching case. Hierarchies are formed when clusters are broken into sub-clusters and so on (Kolodner, 1993). Shared-feature networks provide a means of clustering cases so that cases that share many features are clustered together. Each internal node of a shared-feature network holds features shared by the cases below it. Leaf nodes hold cases themselves. The retrieval process in a shared-feature network performs a sort of breadth first search. The new case is matched against the contents of each node at the highest level in the graph. The best-matching node is chosen. If this is a case, the case is returned. Otherwise, if it is an internal node, the same thing is repeated among its descendants. This continues until a case is returned. View the Kolodner approach in (Kolodner, 1993). Discrimination Networks. In a discrimination network, each internal node is a question that subdivides the set of cases stored underneath it. Each child node represents a different answer to the question posed by its parent, and each child organizes the cases that have its answer. A main difference with shared-feature networks is that discrimination networks put more emphasis on the discrimination than on clustering, exactly the opposite happens in shared-feature networks. To perform better in the recovery, it is important to include the most relevant questions in high levels of the hierarchy, leaving the less important questions for the low levels. A discrimination network algorithm is presented by Kolodner in (Kolodner, 1993). 41 2.1.1.2.3 k-d Trees The retrieving of similar cases is one of the key steps in the case-based reasoning paradigm (Richter & Weber, 2013; Kolodner et al., 1985). The case base must be analyzed to detect a set of potentially useful cases for adaptation purposes. Commonly, there is the distinction between surface and structural similarity (Holyoak and Koh, 1986). Structural similarity computation is normally very expensive, because it means to consider all available knowledge of the domain. On the contrary, the retrieval step should manage the similarity computation of all cases in the case base as fast as possible. Thus, this task can only rely on the comparison of syntactical features, i.e., surface similarity (Gentner and Forbus, 1991). In addition, in the case-based reasoning literature there can be distinguished two different approaches to similarity assessment (Althoff and Wess, 1992); the representational approach (Kolodner, 1980) and the computational approach (Aha, 1991). The former is based on using a structured memory of cases, and the latter is based on the computation of an explicit similarity measure sim. This work is based on the computational approach. When facing a relatively small case base, the similarity computation of all cases could be done in a sequential process, comparing each case in the case base against the current problem (see algorithm 1). This strategy is reasonable for small case bases, as the computational time effort is linear (O(n), being n the number of cases) but it is not feasible for larger case bases. Several strategies have been proposed to improve the retrieval step for large case bases. Some approaches use massively parallel computer hardware to speed up the similarity assessment process. Others are based in the pre-computation of efficient indexation schemes which improve the efficiency of the retrieval step. We will propose a new strategy following these later approaches, but we will propose in chapter 5, some incremental indexing methods to tackle the data stream problem. Also, some indexation schemes were designed to find the m most similar cases (m nearest neighbors, or m-NN) such as (Wess et al. 1993; Friedmann et al. 1977), while others focused on the one most similar case (nearest neighbor or 1-NN) (Arya et al. 1993; Bentley 1975). In our work, we took the second option, and the aim of the retrieval process is the most similar case. However, having in mind that the value m normally is low, be- 48 is on the actual node’s bounding box on the edge facing the query case 𝑋𝑋𝑞𝑞. If there is no overlapping in any of the k dimensions between the node’s bounding box and the k-dimensional ball around 𝑋𝑋𝑞𝑞, then 𝑋𝑋𝑚𝑚𝑖𝑖𝑎𝑎 is a corner of the bounding box. If 𝑋𝑋𝑞𝑞 is within the bounding box then 𝑋𝑋𝑞𝑞=𝑋𝑋𝑚𝑚𝑖𝑖𝑎𝑎 (see figure 6). Before the recursive search procedure ends, the BWB test is applied. This test is true if the k-dimensional ball round 𝑋𝑋𝑞𝑞 is completely within the bounding box the actual tree node (Fig. 6). 𝐵𝐵𝐵𝐵𝐵𝐵 ⇔ 𝑃𝑃𝑠𝑠𝑚𝑚�𝑋𝑋1 𝑗𝑗,𝑋𝑋𝑞𝑞�<𝑃𝑃𝑃𝑃𝑃𝑃[𝑚𝑚] ∧ 𝑃𝑃𝑠𝑠𝑚𝑚�𝑋𝑋2 𝑗𝑗,𝑋𝑋𝑞𝑞�<𝑃𝑃𝑃𝑃𝑃𝑃[𝑚𝑚] ∀𝑗𝑗= 1, ⋯,𝑘𝑘 In this case, no overlapping with other bounding boxes is possible. Thus, the search is finished, and the 𝑚𝑚 most similar cases for the current query case according the similarity measure 𝑠𝑠𝑠𝑠𝑚𝑚 are found. Wess et al. (Wess et al., 1993) also proposed an improvement of the hyperball with BOB and BWB bounds by using information about the known cases. The basic idea is to describe the subspaces that really include cases more precisely. Therefore, all occurring maximal and minimal values for each attribute are stored. These ideas led them to define the concept of Minimal Virtual Bounds (see figure 6). Fig. 6. BOB Tests and Minimal Virtual Bounds, extracted from (Wess et al., 1993). In the right part of the figure 6, the intuitive idea of how much from the description space need not to be considered during search by looking at the white areas is depicted. A BOB test using minimal virtual bounds recognizes that the bucket II does not include any better cases. 49 The Minimal Virtual Bounds of a tree node for the dimension 𝑘𝑘 are defined as follows: 𝑚𝑚𝑠𝑠𝑛𝑛𝐵𝐵𝑙𝑙𝑚𝑚𝑛𝑛𝑚𝑚𝑠𝑠[𝑘𝑘].𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈 = 𝑚𝑚𝑚𝑚𝑚𝑚(𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑖𝑖[𝑘𝑘]) 𝑚𝑚𝑚𝑚𝑚𝑚𝐵𝐵𝑙𝑙𝑚𝑚𝑛𝑛𝑚𝑚𝑠𝑠[𝑘𝑘].𝐿𝐿𝑙𝑙𝐿𝐿𝑈𝑈𝑈𝑈 = 𝑚𝑚𝑠𝑠𝑛𝑛(𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑖𝑖[𝑘𝑘]) {𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑖𝑖[𝑘𝑘]} Denotes the set of all values of attribute 𝑘𝑘 for the cases 𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑖𝑖 that it is being represented by the tree node. While minimal virtual bounds lead to an improvement of the 𝐵𝐵𝑂𝑂𝐵𝐵 tests, an analogous idea, of Maximal Virtual Bounds, can be used to improve the 𝐵𝐵𝐵𝐵𝐵𝐵 tests. For the latter, it is reasonable to describe the searched subspace as precise as possible such that the 𝑘𝑘-dimensional hyperball around the query case has the maximal chance to be completely within that ball. Therefore, the Maximal Virtual Bounds were introduced, as described in figure 8. Fig. 7. BWB tests and Maximal Virtual Bounds, extracted from (Wess et al., 1993). Within such maximal virtual bounds it is guaranteed that no more similar cases can be found within those borders. The computation of the maximal virtual bounds requires more effort because it is not based on the analysis of the cases, but on the analysis of all neighboring subspaces. The virtual bounds can be computed during tree generation. Within the maximal virtual bounds, it is guaranteed that only cases of the respective subspace itself belong to it. There are no more similar cases outside these boundaries. Thus, the search process is finished. 50 2.2 Case Base Maintenance Case Base Maintenance (CBM) is defined by David Leake such as the process of refining a CBR system’s case base to improve the system’s performance: “Case base maintenance implements policies for revising the organization or contents (representation, domain content, accounting information, or implementation) of the case base in order to facilitate future reasoning for a particular set of performance objectives”. Maintenance in CBR can mean a number of different things: out-of- date, redundant, or inconsistent cases may be deleted; groups of cases may be merged to eliminate redundancy and improve reasoning power; cases may be re-described to repair inconsistencies. Thus case-base maintenance may involve revising indexing information, links between cases, or other organizational structures and their implementations. Maintaining Case-Base contents may affect a single case or multiple cases. It may revise: • The case representations used • Either domain information in the case-base or accounting "information" • How case representations are implemented • The case-base at the implementation level, representation level, or the knowledge level The Leake and Wilson framework of CBM shown in (Leake and Wilson, 1998; Wilson and Leake, 2001) is used in this section to describe the concepts and to understand the state of the art in Case Base maintenance (see figure 8). Those research works presents a first attempt at identifying the dimensions of the Case Base maintenance. They show that characterizations along such dimensions can suggest avenues for future Case Base maintenance research and presents initial steps exploring one of those avenues: identifying patterns of problems that require generalized revisions and addressing them with lazy updating. 51 Fig. 8. Case Base Maintenance from Leake’s and Wilson Framework (Leake & Wilson, 1998, 1999) and (Wilson & Leake, 2001) As CBR systems are deployed in real-world situations, the issue of case maintenance becomes more and more critical. Uncontrolled Case Base growth can cause serious performance problems as retrieval efficiency degrades and incorrect or inconsistent cases become increasingly difficult to detect. 52 Case Base Maintenance has become an active CBR research area, producing results with important ramifications for both the theory and practice of CBR, some research works are the proposals; (Perner, 2006; Iglezakis et al., 2004; Portinale and Torasso, 2001; Smyth and Mckenna, 2001; Leake and Wilson, 2000; Yang and Wu, 2000). Much significant work in this area focuses on developing methods for reducing the size of the Case Base while maintaining Case Base competence (Barry and Paul, 2001; Smyth and Mckenna, 2001, 1999; Wilson and Leake, 2001; Leake and Wilson, 1998; Smyth, 1998; Smyth and Cunningham, 1996; Smyth and Keane, 1995). The goal of achieving compact competent Case Bases addresses important performance objectives for CBR systems. As an added benefit, compact Case Bases decrease communications costs when Case Bases are used as vehicles for knowledge sharing or are transferred in distributed CBR systems. However, Case Base compactness is only an opinion to a proxy for performance in a CBR system, rather than an end in itself. Experience with the growing number of large-scale CBR systems has led to increasing recognition of the importance of Case Base maintenance. Many researchers have addressed pieces of the Case Base maintenance problem, considering such issues as maintaining consistency and controlling Case Base growth. CBM methods aim to improve Competence and Efficiency of the CBR systems. Where Performance objectives provide criteria for evaluating the internal behavior and task performance of a particular CBR system for a given initial case-base and sequence of problems solved. The performance objectives may be quantitative or qualitative. 2.2.1 Concepts about efficiency and competence Performance objectives may change over time to reflect varying external circumstances, which may necessitate changing (maintaining) maintenance policies as well. Performance models which combine competence and efficiency can be used to guide the deletion of redundant cases from a case-base in order to optimize system performance. Effective maintenance Case Base reasoning depends on the ability to measure and manage case competence as well as case efficiency. 53 Maintenance policies are described in terms of how they gather data relevant to maintenance, how they decide when to trigger maintenance, whether they react to problems or proactively forestall them, the types of maintenance operations available and how selected maintenance operations are executed. 2.2.1.1 Efficiency Efficiency means that a CBR system is the most efficient one, it if requires the minimal resources needed to solve any case in the domain. The resources are twofold: the time required solving a case, and the size of the Case Base needed to solve a case. Thus, efficiency has to do both with case solving time and the size of the case base. Utility problem: The utility problem highlights the link between knowledge base (Case Base) size and the retrieval time needed to select an item of knowledge to use in a particular problem solving situation. Addition of more knowledge results in potentially severe efficiency degradation. Utility metric is used to take into account the cost of maintaining. 2.2.1.2 Competence Competence means the range of problems that can be satisfactorily solved. During future problem solving, as cases are learned and deleted from the Case Base, the case categories must be updated by recomputing the coverage and reachability of affected cases to adjust the categories accordingly. Competence-Directed Maintenance Individual knowledge items only contribute to problem solving efficiency. An underlying first principles problem solver is always used to encode basic problem solving competence. Cases contribute to both competence and efficiency. 2.2.1.3 The Foundations of Competence The following definitions were formulated in the research works (Barry and Paul, 2001; Smyth and McKenna, 2001; Smyth, 1998; Smyth and Cunningham, 1996; 54 Smyth and Keane, 1995), and are used to give a characterization and overview of the CBM framework. The local competence contributions of individual cases can be characterized by two sets. The coverage set of a case is the set of all target problems that this case can be used to solve. It is not the responsibility of the competence model to explicitly define the ”solves” predicate other than to assume that it exists for any target CBR system. The reachability set of a target problem is the set of all cases that can be used to solve it. It is not possible to enumerate all possible future target problems (𝑇𝑇), but by using the case base (𝐶𝐶) itself as a representative of the target-problem space, we can efficiently estimate these sets, as shown in the definitions of coverage and reachability. Coverage of a case: the set of target problems that a given case can successfully solve. Cases with large coverage sets seem likely to be making large competence contributions. In contrast, cases that are members of large reachability sets seem likely to be less important, as many other cases exist which can solve similar problems. The ability to measure coverage and reachability is the key to understanding competence in CBR. Of course it should be clear that the coverage and reachability sets depend on the characteristics of particular retrieval and adaptation methods. Definition 1: Case Coverage Given a Case Base: 𝐶𝐶= {𝑐𝑐1 . . . 𝑐𝑐𝑎𝑎}, and a case 𝑐𝑐𝑖𝑖 ∈ 𝐶𝐶, i ∈ {1, …, n} 𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈(𝑐𝑐𝑖𝑖) = {𝑐𝑐’∈ 𝐶𝐶∶ 𝐴𝐴𝑚𝑚𝑚𝑚𝑈𝑈𝑛𝑛𝑚𝑚𝐴𝐴𝑙𝑙𝑈𝑈(𝑐𝑐𝑖𝑖,𝑐𝑐’)} Reachability of a target problem: the set of cases that can be used to solve a given target problem. Definition 2: Case Reachability Given a Case Base: 𝐶𝐶= {𝑐𝑐1 . . . 𝑐𝑐𝑎𝑎}, and a case 𝑐𝑐𝑖𝑖 ∈ 𝐶𝐶, i ∈ {1, …, n} 𝑅𝑅𝑈𝑈𝑚𝑚𝑐𝑐ℎ𝑚𝑚𝐴𝐴𝑠𝑠𝑙𝑙𝑠𝑠𝑛𝑛𝑎𝑎(𝑐𝑐𝑖𝑖) = {𝑐𝑐’ ∈ 𝐶𝐶∶ 𝐴𝐴𝑚𝑚𝑚𝑚𝑈𝑈𝑛𝑛𝑚𝑚𝐴𝐴𝑙𝑙𝑈𝑈(𝑐𝑐’, 𝑐𝑐𝑖𝑖)} 55 Competence Groups. Coverage and Reachability sets provide a measure of local competence only. In order to estimate the true competence contributions of cases, it is necessary to model the interactions between related cases, specifically in terms of how their coverage and reachability sets overlap. 𝑅𝑅𝑈𝑈𝑙𝑙𝑚𝑚𝑛𝑛𝑈𝑈𝑚𝑚𝑃𝑃𝑈𝑈𝑛𝑛(𝑐𝑐𝑖𝑖) = 𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈𝑃𝑃𝑈𝑈𝑛𝑛(𝑐𝑐𝑖𝑖) ∪ 𝑅𝑅𝑈𝑈𝑚𝑚𝑐𝑐ℎ𝑚𝑚𝐴𝐴𝑠𝑠𝑙𝑙𝑠𝑠𝑛𝑛𝑎𝑎𝑃𝑃𝑈𝑈𝑛𝑛(𝑐𝑐𝑖𝑖) For 𝑐𝑐1,𝑐𝑐2 ∈ 𝐶𝐶, 𝑃𝑃ℎ𝑚𝑚𝑈𝑈𝑈𝑈𝑚𝑚𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈(𝑐𝑐1,𝑐𝑐2) ⇔ [𝑅𝑅𝑈𝑈𝑙𝑙𝑚𝑚𝑛𝑛𝑈𝑈𝑚𝑚𝑃𝑃𝑈𝑈𝑛𝑛(𝑐𝑐1)∩𝑅𝑅𝑈𝑈𝑙𝑙𝑚𝑚𝑛𝑛𝑈𝑈𝑚𝑚𝑃𝑃𝑈𝑈𝑛𝑛(𝑐𝑐2)] ≠ ∅ 𝐹𝐹𝑙𝑙𝑈𝑈 𝐺𝐺 = {𝑐𝑐1 . . . 𝑐𝑐𝑎𝑎} ⊆ 𝐶𝐶, 𝐶𝐶𝑙𝑙𝑚𝑚𝑈𝑈𝑈𝑈𝑛𝑛𝑈𝑈𝑛𝑛𝑐𝑐𝑈𝑈𝐺𝐺𝑈𝑈𝑙𝑙𝑚𝑚𝑈𝑈(𝐺𝐺) ⇔ ∀𝑐𝑐𝑖𝑖∈ 𝐺𝐺,∃𝑐𝑐𝑗𝑗 ∈ 𝐺𝐺−𝑐𝑐𝑖𝑖∶ 𝑃𝑃ℎ𝑚𝑚𝑈𝑈𝑈𝑈𝑚𝑚𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈(𝑐𝑐𝑖𝑖,𝑐𝑐𝑗𝑗) ∧ ∀𝑐𝑐𝑘𝑘 ∈ 𝐶𝐶−𝐺𝐺,∄𝑐𝑐𝑙𝑙 ∈ 𝐺𝐺∶ 𝑃𝑃ℎ𝑚𝑚𝑈𝑈𝑈𝑈𝑚𝑚𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈(𝑐𝑐𝑘𝑘 , 𝑐𝑐𝑙𝑙 ) First, the related set of a case to be the union of its coverage and reachability sets. When the related sets of two cases overlap, we say that they exhibit shared coverage, and cases can be grouped together into socalled competence groups that are maximal sets of cases exhibiting shared coverage. In fact, every case base can be organized into a unique set of competence groups which, by definition, do not interact from a competence viewpoint i.e., while each case within a given competence group must share coverage with at least one other case in that group, no case from one group can share coverage with any case from another group. The importance of the competence group concept is that each group makes a unique contribution to competence. Thus, competence groups allow us to partition the case space into non-interacting groups of cases. Each group can be treated independently of all other groups in the case base from a competence viewpoint, and this means that the competence of a case base as a whole can be computed as the sum of the competence contributions of each competence group. 56 While each competence group makes a unique contribution to overall competence, not every case in a group makes the same (or even a positive) contribution. The final stage of the model involves identifying the so-called footprint cases and measuring their relative competence contributions. By definition, footprint cases are those cases, which make a positive competence contribution to competence, and the set of footprint cases of a group covers the entire group. In contrast, non-footprint cases make redundant competence contributions because they are fully covered by nearby footprint cases. We will revisit the concept of footprint cases in a later section, where we will provide algorithms for identifying the footprint of a group. The relative competence contribution of an individual case is estimated by the relative coverage (RC) measure, which estimates the competence contribution of an individual case c as a function of the size of the case’s coverage set (see next Equation). RC weights the contribution of each covered case by the degree to which these cases are themselves covered. It is based on the idea that if a case c’ is covered by n other cases, then each of the n cases will receive a contribution of 1/𝑛𝑛 from c’ to their relative coverage measures. 𝑅𝑅𝑈𝑈𝑙𝑙𝑚𝑚𝑛𝑛𝑠𝑠𝐶𝐶𝑈𝑈 𝐶𝐶𝑙𝑙𝐶𝐶𝑈𝑈𝑈𝑈𝑚𝑚𝑙𝑙𝑈𝑈(𝑐𝑐)=∑1 |𝑅𝑅𝑅𝑅𝑞𝑞𝑐𝑐ℎ𝑞𝑞𝑎𝑎𝑖𝑖𝑙𝑙𝑖𝑖𝑎𝑎𝑎𝑎𝑎𝑎𝑅𝑅𝑎𝑎(𝑐𝑐′)| 𝑐𝑐′∈𝐶𝐶𝐶𝐶𝐶𝐶𝑅𝑅𝐶𝐶𝑞𝑞𝐶𝐶𝑅𝑅𝑎𝑎𝑅𝑅𝑎𝑎(𝑐𝑐) 2.2.2 Maintenance Data Collection Maintenance Data Collection gathers, synthesizes, and distills the data about the case base and about system processing. This information will be used to determine whether maintenance operation should be performed or not. It gathers information about: • Individual cases: it might record the number of times a case has been successfully used or the number of times it has failed. • The case base: the case base as a whole could involve, for example, monitoring the size of the case base. • Processing: it might involve noting clusters in input problems or input problems that the system is unable to solve successfully. 57 There are three approaches to collecting and analyzing data to decide when CBM is needed: None, Synchronic, or Diachronic. The simplest is to do no collection at all: • A policy with no data collection makes maintenance decisions independently of the present or past state of the case base. As such, this type of policy is referred to as nonintrospective. For example, a CBR system that updates its case base by unconditionally adding a case each time it adapts a prior case would need no data collection. This is the approach of most CBR systems. Similarly, a system may drive maintenance according to external information sources. This is valuable for proactive maintenance, for example, to add cases to a help-desk case base in anticipation of future queries. • Synchronic (Policies that consider snapshot information). More sophisticated reasoning is enabled by considering a snapshot of the current case base in part or as a whole. Examination of this information can determine, for example, whether a case is worth adding to a case base because it increases the competence of the CBR system or whether a solution can be discarded without affecting competence (Smyth and Keane 1995). As another example see Reinartz et al. contributions in (Reinartz et al,. 2000) where they propose a set of measures that can be computed to assess the overall quality of a case base in order to trigger maintenance. • Diachronic (Policies that consider changes in the case base over time). The most informative approach is to collect data over time, over a sequence of snapshots, in order to identify trends in how Case Base contents and usage are changing. For example, a policy that gathered information about trends in retrieval times to identify the onset of utility problems would be diachronic. Because synchronic and diachronic collection examines the internal state of the case base, both are referred to as introspective. Regarding the time when the data collection is needed it Timing could be: periodic, conditional, or ad hoc. A maintenance policy must specify when data collection is performed. Periodic timing happens at an estab- 64 2.3 Introspective Reasoning The tenets of metacognition are monitoring, modeling, evaluating and controlling of the cognition (Anderson and Oates, 2007). Metacognition means to have the knowledge and how to use this knowledge to improve performance and reduce as low as possible deficiencies. The main challenge of meta-reasoning is to find answers to most predictable future needs. Introspective reasoning is an invaluable part in metareasoning. John McCarty in (McCarthy, 1979) defines introspection as a machine with beliefs of its internal state. Leake and Wilson in (Leake and Wilson, 2008) defines that an introspective strategy must be characterized by properties defining the When, What and How the learning step is done. Research on meta-reasoning and introspective reasoning has been reviewed and analyzed especially in fields such as physiology, social science and especially in artificial intelligence. In this later, some scientific contributions define this process to be successfully implemented in computer science, such intelligence algorithms. Cox in (Cox, 2005) does an extensive review of those topics where discuses cognition about Meta-cognition and establish a relationship between psychology and computer science fields. Anderson in (Anderson and Oates, 2007) extends the definition of metacognition in computer science illustrating terms such as learning, meta-learning and meta-cognition. Afterwards Cox in his Manifesto (Cox and Raja, 2008) explains in detailed fundamental terms such as Ground Level, Object Level and Meta-level. Thus, Meta-reasoning has been extensively studied and characterized such as been demonstrated in literature. The meta-reasoning has been implemented effectively in the Case- Based Reasoning (CBR) (Arcos et al, 2008; Leake, 2001; Fox and Leake, 2001; Leake et al, 1995; Fox and Leake, 1994). In (Leake et al, 1995) the objective is to improve the adaptation step by introspective reasoning considering the requirements and built a library with adapted cases. The introspective reasoning process implements memory search as form of planning and use operators such as sensors to detect internal states. Their results show a successful adaptation of knowledge. In Arcos et al, 2008 the performance of the CBR cycle through an internal reasoning process that guides the use of its cases is considerable improved. Arcos et al. implements the method such as an introspective reasoner monitor, pursuing the goal to determinate the causes of failures, and then adjusts retrieval and reuse strategies to improve solution quality. 65 Fox and Leake in (Fox and Leake, 2001; 1994) have proposed some improvements to the CBR scenario, where meta-reasoning is embedded in the cycle. In (Fox and Leake, 1994) proposed to refine the indexing criteria by the implementation of an introspective reasoning framework with the aim of refining reasoning processes, this frame-work is extended and detailed in (Fox and Leake, 2001). Sànchez-Marrè in (Sànchez-Marrè et al., 2000) introduced the idea of retrieval cases in hierarchical case libraries, where a radius is defined by the implementation of a metric measure, where if the distance from the library to the case exceeds the threshold, then the case will not store there. Our proposal shares a similitude to this, but exists some differences between them. In our case the proposal aims to build the required prototypes and make a decision of where going to store the new cases. The core of our proposal is the implementation of a stochastic method working with two moments. That will be detailed in the thesis. The meta-learning and meta-reasoning have been widely studied; even more, those topics are one of the goals to achieve by the Artificial Intelligence community. In CBR community interesting and efficient methods have been proposed in this sense. Several proposals that have been published have had the aim of implementing meta-reasoning. Some proposals use introspective reasoning as our method to detect some expected behavior or to evaluate the behavior to guarantee the good performance of the CBR system. Our proposal uses an introspective reasoning strategy to evaluate the performance of a set of algorithms in learning phase. This done autonomously by the system, the introspective reasoning strategy involves the implementation of a set of rules to evaluate whether the algorithms gives the best performance to the system. With the strategy implemented we answer the questions formulated in Leake and Wilson, 2008 that consist in ¿When? ¿What? And ¿How the system learns? ¿When? When there exists a strategy that improves the performance. ¿What? The new algorithm. And finally ¿How the system learns? the system learns by the implementation of the new indexing strategy proposed. This is done when the reasoning gathers sufficient information and its results improve the other algorithms, when an algorithm over perform others, then it is considered as the best candidate to be used. All these answers and our proposal are 66 defined according to introspective reasoning as reflected in (Cox and Raja, 2008; Anderson and Oates, 2007; Cox, 2005). 2.4 Stochastic Learning The Stochastic method has been widely used in several applications where learning is required. Here data plays the main role in the learning. One field in artificial intelligence where stochastic learning has been used is in the clustering field. Contribution in this field proposes improved methods to get better results in finding clusters. For instance see (Swee et al., 2011), where authors examine a practical stochastic clustering method that has the ability to find clusters in datasets without requiring users to specify the centroids or the number of clusters. Other application is in the field of robotics and learning, with the proposal of (Zhang et al., 2013). They propose an efficient Stochastic Clustering Auctions for centralized auctioning and homogeneous robot teams. For others contributions see (Rebagliati et al., 2013), (Wang et al., 2012). For the application in Trees see (Akbari and Reza, 2011). There are many other contributions in the application of stochastic methods. One of the main contribution in the CBR field is the proposal of (Finestrali and Muñoz-Avila, 2013) where they studied the problem of explaining events in stochastic environments. They claimed that a system using stochastic explanations reacts faster to abrupt changes in the environment than a system using deterministic explanations. They demonstrated this claim in a CBR system, while playing a real-time strategy game. In chapter 5 some differences between our proposal and their proposal will be discussed. Chuan in (Tan et al., 2010), implements a stochastic method where building and classification of clusters are the issue. This is done without human interaction. Then, they use the time variable to evaluate the probability of belonging to some cluster. In our method, we use a time variable to indicate the time when the acquired data was taken. Both methods learn cases and store it, but we differ from Chuan in the method of learning the cases. In our case, we talk about representative prototypes. The learning of cases in our proposal is conditioned to accomplish with the maximal acceptable dissimilarity or dispersion. 67 The following is a revision of the stochastic method according with Taylor and Karlin in (Taylor and Karlin, 1998). The word "stochastic" derives from the Greek and means "random" or "chance". The antonym is "sure," deterministic," or "certain". A deterministic model predicts a single outcome form a given set of circumstances. A stochastic model predicts a set of possible outcomes weighted by their likelihoods, or possibilities. A coin flipped into the air will surely return to earth somewhere. Whether it lands heads or tails is random. For a "fair" coin, we consider these alternatives equally likely and assign to each the probability 1/2. However, phenomena are not in themselves inherently stochastic or deterministic. Rather is the choice of the observer to model a phenomenon as stochastic or deterministic. The choice depends on the observer's purpose. Most often, the proper choice is quite clear, but controversial situations do arise. If once fallen the coin is quickly covered by a book, so that the outcome "heads" or "tails" remains unknown, two participants may still usefully employ probability concepts to evaluate what is a fair bet between them. That is, they may usefully view the coin as random, even though most people would consider the outcome now to be fixed or deterministic. As a less mundane example of the converse situation, changes in the level of a large population are often usefully modeled deterministically, in spite of the general agreement among observers that many chance events contribute to their fluctuations. Scientific modeling has three components: (i) a natural phenomenon under study, (ii) a logical system for deducing implications about the phenomenon, and (iii) a connection linking the elements of the natural system under study to the logical system used to model it. If we think of these three components in terms of the great-circle air route problem, the natural system is the earth with airports at Los Angeles and New York; the logical system is the mathematical subject of spherical geometry; and the two are connected by viewing the airports in the physical system as points in the logical system. The modern approach to stochastic modeling is in a similar spirit. Nature does not dictate a unique definition of "probability," in the same way that there is no natureimposed definition of "point" in geometry. "Probability" and "point" are terms in pure mathematics, defined only through the properties invested in them by their respective sets of axioms. 68 In many real life situations, observations are made over a period and they are influenced by random effects, not just at a single instant but throughout the entire interval of time or sequence of times (Athanasios, 1984). In a “rough” sense, a random process is a phenomenon that varies to some degree unpredictably as time goes on. If we observed an entire time-sequence of the process on several different occasions, under presumably “identical” conditions, the resulting observation sequences, in general, would be different. A random variable (RV) is a rule that assigns a real number to every outcome of a random experiment, while a random process is a rule that assigns a time function to every outcome of a random experiment. A random experiment may lead not only to a single random variable, but to an entire sequence of random variables. {𝑋𝑋𝑖𝑖:𝑠𝑠= 1, 2, 3 ⋯}= {𝑋𝑋1,𝑋𝑋2,𝑋𝑋3 ⋯} Consider the random experiment of tossing a dice at 𝑛𝑛= 0 and observing the number on the top face. The sample space of this experiment consists of the outcomes {1, 2, 3, ⋯, 6}. For each outcome of the experiment, let us arbitrarily assign a function of time 𝑛𝑛 {0≤𝑛𝑛 < ∞} in the following manner; considering the list of last outcomes, where its function time is as follows: 𝑋𝑋1(𝑛𝑛)= −2, 𝑋𝑋2(𝑛𝑛)= −4, 𝑋𝑋3(𝑛𝑛)= 2, 𝑋𝑋4(𝑛𝑛)= 4, 𝑋𝑋5(𝑛𝑛)= −𝑛𝑛/2, 𝑋𝑋6(𝑛𝑛)= 𝑛𝑛/2 The set of functions {𝑋𝑋1(𝑛𝑛),𝑋𝑋2(𝑛𝑛), ⋯,𝑋𝑋6(𝑛𝑛)} represents a random process. A random process is a collection of RVs {𝑋𝑋(𝑠𝑠,𝑛𝑛)} that are func- 69 tions of real variable, namely time t where 𝑠𝑠 ∈ 𝑃𝑃 (sample space) and 𝑛𝑛 ∈ 𝑇𝑇 (parameter set of index set). The set of possible values of any individual member of the random process is called state space. Any individual member itself is called a sample function or a realization of the process. Classification of random processes Depending on the continuous or discrete nature of the state space 𝑃𝑃 and parameter set 𝑇𝑇, a random process can be classified into four types: 1. If both 𝑇𝑇 and S are discrete, the random process is called a discrete random process. For example, if 𝑋𝑋𝑎𝑎 represents the outcome of the nth toss of a fair dice, then {𝑋𝑋𝑎𝑎,𝑛𝑛 ≥1} is a discrete random sequence, since 𝑇𝑇= {1, 2, 3, ⋯} and 𝑃𝑃= {1, 2, 3, 4, 5, 6}. 2. If 𝑇𝑇 is discrete and S is continuous, the random process is called a continuous random sequence. For example, if 𝑋𝑋𝑎𝑎 represents the temperature at the end of the 𝑛𝑛𝑛𝑛ℎ hour of a day, then {𝑋𝑋𝑎𝑎, 1 ≤𝑛𝑛 ≤24} is a continuous random sequence, since temperature can take any value in an interval and hence continuous. 3. If 𝑇𝑇 is continuous and 𝑃𝑃 is discrete, the random process is called a discrete random process. For example, if 𝑋𝑋(𝑛𝑛) represents the number of telephone calls received in the interval (0, 𝑛𝑛) then {𝑋𝑋(𝑛𝑛)} is discrete random process, since 𝑃𝑃= {0,1,2,3, ⋯}. 4. If both 𝑇𝑇 and 𝑃𝑃 are continuous, the random process is called a continuous random process. For example, if 𝑋𝑋(𝑛𝑛) represents the maximum temperature at a place in the interval (0, 𝑛𝑛), {𝑋𝑋(𝑛𝑛)} is a continuous random process. In the names given above, the word ‘discrete’ or ‘continuous’ is used to refer to the nature of 𝑇𝑇. Specifying a random process. Let 𝑋𝑋1,𝑋𝑋2,⋯𝑋𝑋𝑘𝑘 be the 𝑘𝑘 random variables obtained by sampling the random process 𝑋𝑋(𝑛𝑛,𝜁𝜁) at times 𝑛𝑛1,𝑛𝑛2,⋯𝑛𝑛𝑘𝑘: 70 𝑋𝑋1=𝑋𝑋(𝑛𝑛1,𝜁𝜁),𝑋𝑋2=𝑋𝑋(𝑛𝑛2,𝜁𝜁),⋯,𝑋𝑋𝑘𝑘=𝑋𝑋(𝑛𝑛𝑘𝑘2,𝜁𝜁). The joint behavior of the random process at these 𝑘𝑘 time instants is specified by the joint cumulative distribution for the vector random variable (𝑋𝑋1,𝑋𝑋2,⋯,𝑋𝑋𝑘𝑘). A stochastic process is specified by the collection of the 𝑘𝑘𝑛𝑛ℎ-order joint cumulative distribution functions: 𝐹𝐹𝑋𝑋1⋯𝑋𝑋𝑘𝑘(𝑚𝑚1,𝑚𝑚2,⋯,𝑚𝑚𝑘𝑘)=𝑃𝑃[𝑋𝑋1≤𝑚𝑚1,𝑋𝑋2≤𝑚𝑚2,⋯,𝑋𝑋𝑘𝑘≤𝑚𝑚𝑘𝑘] For any 𝑘𝑘 and any choice at sampling instants 𝑛𝑛1,⋯,𝑛𝑛𝑘𝑘. If the stochastic process is discrete-valued, then a collection of probability mass functions can be used to specify the stochastic process: 𝑃𝑃𝑋𝑋1⋯𝑋𝑋𝑘𝑘(𝑚𝑚1,𝑚𝑚2,⋯,𝑚𝑚𝑘𝑘)=𝑃𝑃[𝑋𝑋1=𝑚𝑚1,𝑋𝑋2=𝑚𝑚2,⋯,𝑋𝑋𝑘𝑘=𝑚𝑚𝑘𝑘] The Mean 𝑚𝑚𝑋𝑋(𝑛𝑛) of a random process 𝑋𝑋(𝑛𝑛) is 𝑚𝑚𝑋𝑋(𝑛𝑛)=𝐸𝐸 [𝑋𝑋(𝑛𝑛)=� 𝑚𝑚𝑓𝑓𝑥𝑥(𝑎𝑎)𝑚𝑚 𝑚𝑚𝑚𝑚. ∞ −∞ In general, 𝑚𝑚𝑋𝑋(𝑛𝑛) is a function of time. Suppose we write 𝑚𝑚𝑋𝑋(𝑛𝑛)+𝑌𝑌(𝑛𝑛) then 𝑌𝑌(𝑛𝑛) has zero mean. Trends in the behavior of 𝑚𝑚𝑋𝑋(𝑛𝑛) are reflected in the variation of the 𝑚𝑚𝑋𝑋(𝑛𝑛) with time. The Autocorrelation 𝑅𝑅𝑥𝑥(𝑛𝑛1,𝑛𝑛2) of a random process 𝑋𝑋(𝑛𝑛) are reflected in the variation of 𝑚𝑚𝑋𝑋(𝑛𝑛) with time. The autocorrelation 𝑅𝑅𝑥𝑥(𝑛𝑛1,𝑛𝑛2) of a random process 𝑋𝑋(𝑛𝑛) is the joint moment of 𝑋𝑋(𝑛𝑛1) and 𝑋𝑋(𝑛𝑛2) 𝑅𝑅𝑋𝑋(𝑛𝑛1,𝑛𝑛2)=𝐸𝐸 [𝑋𝑋(𝑛𝑛1)𝑋𝑋(𝑛𝑛2)] = � � 𝑚𝑚𝑎𝑎𝑓𝑓𝑥𝑥(𝑎𝑎1),𝑥𝑥(𝑎𝑎2)𝑚𝑚𝑚𝑚 𝑚𝑚𝑎𝑎. ∞ −∞ ∞ −∞ Note that 𝑓𝑓𝑥𝑥(𝑎𝑎1),𝑥𝑥(𝑎𝑎2) is the second order pdf or 𝑋𝑋(𝑛𝑛) and 𝑅𝑅𝑋𝑋(𝑛𝑛1,𝑛𝑛2) is a function of 𝑛𝑛1 and 𝑛𝑛2. 71 The Autocovariance 𝐶𝐶𝑥𝑥(𝑛𝑛1,𝑛𝑛2) of a random proces 𝑋𝑋(𝑛𝑛)s is defined as the covariance of 𝑋𝑋(𝑛𝑛1) and 𝑋𝑋(𝑛𝑛2): 𝐶𝐶𝑋𝑋(𝑛𝑛1,𝑛𝑛2)=𝐸𝐸[{𝑋𝑋(𝑛𝑛1)−𝑚𝑚𝑋𝑋(𝑛𝑛1)}{𝑋𝑋(𝑛𝑛2)−𝑚𝑚𝑋𝑋(𝑛𝑛2)}] = 𝑅𝑅𝑋𝑋(𝑛𝑛1,𝑛𝑛2)−𝑚𝑚𝑋𝑋(𝑛𝑛1)𝑚𝑚𝑋𝑋(𝑛𝑛2) In particular, when 𝑛𝑛1= 𝑛𝑛2=𝑛𝑛 we have 𝑉𝑉𝐴𝐴𝑅𝑅[𝑋𝑋(𝑛𝑛)]=𝐸𝐸[(𝑋𝑋(𝑛𝑛)− 𝑚𝑚𝑋𝑋(𝑛𝑛))2]= 𝐶𝐶𝑋𝑋(𝑛𝑛,𝑛𝑛). Correlation coefficient of 𝑋𝑋(𝑛𝑛) is defined as 𝜌𝜌𝑚𝑚(𝑛𝑛1,𝑛𝑛2)=𝐶𝐶𝑋𝑋(𝑛𝑛1,𝑛𝑛2) �𝐶𝐶𝑋𝑋(𝑛𝑛1,𝑛𝑛1)�𝐶𝐶𝑋𝑋(𝑛𝑛2,𝑛𝑛2); |𝜌𝜌𝑚𝑚(𝑛𝑛1,𝑛𝑛2)| ≤1 The mean, autocorrelation and autocovariance functions provide only partial description of a random process. 2.5 Continuous Domains In recent years, advances in hardware technology have facilitated new ways of continuously collecting data. In many applications such as network monitoring, the volume of such data is so large that it may be impossible to store the data on disk. Furthermore, even when the data can be stored, the volume of the incoming data may be so large that it may be impossible to process any particular record more than once. Therefore, many data mining and database operations such as classification, clustering, frequent pattern mining and indexing become significantly more challenging in this context (Aggarwal, 2007). The monitoring of many events in real time produces much information. In recent years data stream field has grown rapidly. This field provides of techniques to deal with large information, but the lead of big amount of data there are some challenges to consider such as the following: • With increasing volume of the data, it is no longer possible to process the data efficiently by using multiple passes. Rather, one can process a data item at most once. This leads to constraints on the implementation of the underlying algorithms. 72 Therefore, stream mining algorithms typically need to be designed so that the algorithms work with one pass of the data. • In most cases, there is an inherent temporal component to the stream mining process. This is because the data may evolve over time. This behaviour of data streams is referred to as temporal locality. Therefore, a straight-forward adaptation of one-pass mining algorithms may not be carefully designed with a clear focus on the evolution of the underlying data. Continuous problem domains require different underlying representations and place additional constraints on the problem solving process (Ram and Santamaría, 1997). Ram and Santamaria define three characteristics where the problem domain is continuous, and those are: First, they require continuous representations, For example, a robotic navigation task requires representations of continuous perceptual and motor control information. Second, they require continuous performance. For example, driving a car requires continuous action. Often, problemsolving performance is incremental of necessity because of limited knowledge available to the reasoning system and (or) because of the unpredictability of the environment; the system can at best execute the “best” short term actions available to it and then re-evaluate its progress. A robot, for example, may not know where obstacles lie until it actually encounters them. Third, these problem domains require continuous adaptation and learning. As the problems encountered become more varied and difficult, it becomes necessary to use fine-grained, detailed knowledge in an incremental manner to act, and to rely on continuous feedback from the environment to adapt actions and learn from experiences. Reasoning about continuous domains is not an easy task. Moreover, this is a domain where CBR can rapidly extend its benefits because data is systematically collected for its analysis. A CBR system that continuously interacts with an environment must be able to create autonomously new situation cases (new concepts or clusters) based on its perception of the local environment in order to select the appropriate steps to achieve the current mission goal (Harris and Slobodan, 2005), but a general framework is still missing. Some systems that use case-based methods in continuous environment are described in (Urdiales et al., 2006, Kruusmaa, 2003, Ram et al., 1997). 73 There are two other central problems derived from the continuous nature of some domains. First of all, the size of the case library could grow very fast as the CBR system is learning new cases without an extensive improvement in the competence of the system, as pointed out in (Miyashita and Sycara, 1995). Two natural human cognitive tasks appear as the solution to these problems: forgetting (Keane and Smyth, 1995) and sustained relevant learning (Sànchez-Marrè et al., 1999). On the other hand, learning many cases could provoke an overhead in the case library organization. As new cases are stored in the case library, it will be necessary to update the case library organization (Meléndez, 2001). 80 age and reachability formulated by Keane and Smyth (Keane and Smyth, 1995): Case#_X: The identifier assigned to the new case. List of Attributes (att1 ... attm ): The list of the attributes witch characterize both the problem description and the corresponding solution. Problem: A situation detected by the system it is described by a list of attribute-value pairs. Solution: It is the solution for the problem. The solution is a list of attribute-value pairs showing the solution to the problem. Distance to Meta-case: It is the distance of the case to its Meta-case model. Taking the Case as an object, it could incorporates some others values that help to have a better representation of the current new case (𝑁𝑁𝑐𝑐). 3.1.2 The Meta-case The idea of using a Meta-case as a representative case of several similar cases was introduced by Sànchez-Marrè in (Sànchez-Marrè et al., 2000). The aim is to show a formal proposal of how to a Meta-case (𝑀𝑀𝑐𝑐) can be built. For our goal, a Meta-case is the prototype of a set of related cases. The centroid value is generated taking into account the whole cases stored in the indexing structure. With the following formula: 𝑀𝑀𝑐𝑐𝑗𝑗𝑖𝑖=1 𝑎𝑎𝑖𝑖∑𝐶𝐶𝑗𝑗𝑘𝑘 𝐿𝐿ℎ𝑈𝑈𝑈𝑈𝑈𝑈 j = 1, … , m 𝑎𝑎𝑖𝑖 𝑘𝑘=1 . The average distance (centroid) of the set of cases in that cluster is computed. A case (𝐶𝐶𝑖𝑖) and a Metacase (𝑀𝑀𝑐𝑐) are described by m attribute values. That is the first proposal that was introduced in (Orduña and Sànchez-Marrè, 2009). Our proposal of constructing Meta-cases (Orduña and Sànchez-Marrè et. al., 2015a) is where the stochastic methods is introduced and prove it. DACL have as representative case a 𝑀𝑀𝑐𝑐, this 𝑀𝑀𝑐𝑐 works like a clustering filter where the decision to learn a new incoming case (𝑀𝑀𝑐𝑐) is made, this decision concerns to a method to evaluate the 𝑀𝑀𝑐𝑐′𝑠𝑠 and find the most appropriate 𝑀𝑀𝑐𝑐 where to learn the 𝑁𝑁𝑐𝑐. 81 Fig. 13. Learning new cases through the DACL framework The figure 13 depicts the general way of learning a new case, first the case arrives, and next the method finds the most representative Mc. Once the Mc has been identified, the DACL proceed to store the Nc in the corresponding indexing structure (k-d tree, discrimination tree, etc.). Here follows the formalization of this process: 𝐶𝐶𝑖𝑖=�𝐶𝐶1 𝑖𝑖,𝐶𝐶2 𝑖𝑖,⋯,𝐶𝐶𝑚𝑚 𝑖𝑖� 𝑀𝑀𝑐𝑐𝑖𝑖=�𝑀𝑀𝑐𝑐1 𝑖𝑖,𝑀𝑀𝑐𝑐2 𝑖𝑖,⋯,𝑀𝑀𝑐𝑐𝑚𝑚 𝑖𝑖� Where 𝑛𝑛𝑖𝑖 = #𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑠𝑠 𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑠𝑠𝑈𝑈𝑛𝑛𝑛𝑛𝑈𝑈𝑚𝑚 𝐴𝐴𝑎𝑎 𝑛𝑛ℎ𝑈𝑈 𝑀𝑀𝑈𝑈𝑛𝑛𝑚𝑚−𝑐𝑐𝑚𝑚𝑠𝑠𝑈𝑈(𝑀𝑀𝑐𝑐𝑖𝑖) 𝑀𝑀𝑐𝑐𝑗𝑗𝑖𝑖=1 𝑎𝑎𝑖𝑖∑𝐶𝐶𝑗𝑗𝑘𝑘 j = 1, … , 𝑚𝑚 𝑎𝑎𝑖𝑖 𝑘𝑘=1 (1a) 82 If 𝑗𝑗 is a qualitative attribute, and 𝑀𝑀𝑐𝑐𝑗𝑗𝑖𝑖=𝑚𝑚𝑙𝑙𝑚𝑚𝑈𝑈�𝐶𝐶𝑗𝑗𝑘𝑘� 𝑘𝑘= 1, … , 𝑛𝑛𝑖𝑖 𝑗𝑗= 1, … , 𝑚𝑚 (1b) If 𝑗𝑗 is a quantitative attribute The Meta-case structure improves the performance of the retrieval time according to the proposals of Orduña and Sànchez-Marrè in (Orduña and Sànchez-Marrè et. al., 2015a; Orduña and Sànchez-Marrè, 2009). The Meta-case is related to the clustering and learning processes. A Meta-case structure is considered as follows: Meta-case-id: It is the identification of the Meta-case. Meta-case centroid: It is computed, for each component, as the average value or mode value of corresponding values of all cases existing in the corresponding cluster. This average or mode is generated by using the formulas 1a or 1b. IndStr link: The link to the root of the Indexing structure. McBrother: The link to the nearest Meta-case brother. Considering the Mc as an object, it could incorporate some other values to help having a better representative prototype. A CBR system executes the following 4 phases to learn a new experience; retrieve, reuse, revise and retain. In the DACL approach, the retrieve and retain phases need to be addressed and reformulated. Retrieving similar cases regarding to a new case is a process that needs to be done accurately. A new algorithm (DACL Retrieval algorithm) to retrieve the most similar case or cases in the DACL is shown. 83 Algorithm 3: DACL retrieval algorithm Input: The Case (C) 1 Output: the retrieved set of cases (Retrieved) 2 Begin Discriminant_tree(Node Nc) 3 Let C = the arriving case; 4 Let Mc = a Meta-case; 5 Let dMC = the most similar Meta-case; 6 Let i = total number of Meta-cases; 7 Let K = total number of attributes of the C; 8 Let a = an attribute of C where a= {1… K}; 9 Let CL = the cluster that's represents a Meta-case where 10 CL={1…i} 11 Let ListMc = a {list to store temporally the distances 12 estimated}; 13 Let N = The root of the tree; 14 Let Node C = the representation of the C; 15 Let atta = an specific attribute of C, where a = {1… K}; 16 Let Dadnode = a {node that's represents a discriminant 17 section} 18 Estimate the distance between the C and the entire Meta-19 case using the formula 2; 20 dMC = Min(ListMc) 21 Similar = Method_search(C, N) 22 Begin Method_search(Node C, Node DadNode) 23 Path = Compare dMC.attx with C.attx 24 if(Path.leaf == Relevance) 25 If Path.leaf == DadNode then 26 Method_search(C, Path.leaf) 27 Else 28 If Path.leaf == CaseNode then 29 If CaseNode.ListCases == true then 30 while ListCases != null 31 Apply the formula 3. 32 Endwhile 33 Retrieved = Max(ListSimil) 34 Else 35 Retrieved = Path.leaf 36 Endif 37 Endif 38 Endif 39 Endif 40 Return Retrieved 41 End Method_search42 𝐿𝐿𝑠𝑠𝑠𝑠𝑛𝑛𝑀𝑀𝑐𝑐[𝑐𝑐𝑙𝑙]=∑�1 𝑞𝑞𝑎𝑎𝑎𝑎𝑘𝑘 𝐶𝐶𝑙𝑙𝑖𝑖 𝐶𝐶𝑙𝑙=1 �∑�𝐶𝐶𝑞𝑞𝑎𝑎𝑎𝑎 −𝑀𝑀𝑐𝑐𝐶𝐶𝑙𝑙𝑎𝑎𝑎𝑎𝑎𝑎� 𝑞𝑞𝑘𝑘 𝑞𝑞𝑎𝑎𝑎𝑎=1 �� (2) 𝐿𝐿𝑠𝑠𝑠𝑠𝑛𝑛𝑀𝑀𝑐𝑐[𝑖𝑖]=∑�1−�∑𝑅𝑅𝑤𝑤𝑞𝑞𝑎𝑎𝑎𝑎 𝑑𝑑�𝐶𝐶𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎−𝐶𝐶𝑞𝑞𝑠𝑠𝑅𝑅𝑠𝑠𝐶𝐶𝑖𝑖𝑠𝑠𝑎𝑎𝑖𝑖𝑎𝑎𝑎𝑎𝑎𝑎� 𝑛𝑛 𝑎𝑎𝑎𝑎𝑎𝑎=1 ∑𝑅𝑅𝑤𝑤𝑞𝑞𝑎𝑎𝑎𝑎 𝑛𝑛 𝑎𝑎𝑎𝑎𝑎𝑎=1 �� 𝐶𝐶𝑞𝑞𝑠𝑠𝑅𝑅𝑠𝑠𝐶𝐶𝑖𝑖𝑠𝑠𝑎𝑎!=𝑎𝑎𝑛𝑛𝑙𝑙𝑙𝑙 𝑖𝑖=1 (3) Where: 𝑚𝑚�𝐶𝐶𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎 − 𝐶𝐶𝑚𝑚𝑠𝑠𝑈𝑈𝑠𝑠𝐿𝐿𝑠𝑠𝑠𝑠𝑛𝑛𝑖𝑖𝑎𝑎𝑎𝑎𝑎𝑎�= �𝑞𝑞𝑛𝑛𝑞𝑞𝑎𝑎𝑎𝑎𝐶𝐶𝑞𝑞𝑙𝑙(𝐶𝐶𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎 )− 𝑞𝑞𝑛𝑛𝑞𝑞𝑎𝑎𝑎𝑎𝐶𝐶𝑞𝑞𝑙𝑙(𝐶𝐶𝑞𝑞𝑠𝑠𝑅𝑅𝑠𝑠𝐶𝐶𝑖𝑖𝑠𝑠𝑎𝑎𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎 )� 𝑈𝑈𝑝𝑝𝑝𝑝𝑅𝑅𝐶𝐶𝑈𝑈𝑞𝑞𝑙𝑙(𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎) − 𝐶𝐶𝐶𝐶𝐿𝐿𝑅𝑅𝐶𝐶𝑈𝑈𝑞𝑞𝑙𝑙(𝐴𝐴𝑎𝑎𝑎𝑎𝑎𝑎) (4) Retain task aims to maintain (Basic retaining/learning algorithm) a competent Case Library with a high coverage. The Retain process decides whether the new case needs to be stored in the case library, by updating an existing sub-library, building a new sub-library or simply ignoring the case. The process to make a decision is guided by the learning algorithm. The algorithm basic retaining/learning algorithm works as follows: it receives a solved new case (Nc) and then computes the distance to all the Meta-cases, with the aim to find the closest Meta-cases. Once the best Meta-case is found, it proceeds to compare whether the distance found falls within the α threshold (previously defined by the experts or tuned by trial and error experimentation). Then, it proceeds to store the new case into the current library. Otherwise, if the distance is higher than the α threshold value, a new sub-library must be created containing the new solved case. The last consideration in the algorithm is when the distance of the solved case falls within the ratio of two or more meta-cases. If so, the competence of the most similar Meta-case (MsMc) and the second most similar Meta-case (2MsMc) is computed taking into account the solved case. Moreover, the solved case is stored into the sub-library that better improves its competence with the case. Algorithm 4: basic retaining/learning algorithm (VirtualMcSel-1) Input: the new case solved (Nc) 1 The DACL 2 Output: The updated DACL 3 Begin VirtualMcSel-1 4 Let MsMc = the most similar Meta-case; 5 Let 2MsMc = the second most similar; 6 The distance is computed between the new case and the 7 whole set of Mc 8 if d(Nc, MsMc) < α and (d(Nc, 2MsMc) < α then 9 /* α is the threshold value, predefined by the experts 10 or tuned by trial and error experimentation */ 11 Evaluate the competence of the MsMc and 2MsMc; 12 Select the sub-library that get a better competence 13 with the new case; 14 The selected Meta-case is updated with the new case; 15 elseif d(Nc, MsMc) < α then 16 Update the corresponding sub-library with the new case 17 elseif d(Nc, MsMc) > α then 18 Build a new sub-library, and store the new case 19 endif 20 end VirtualMcSel-1 21 3.2 Multiple Case Library (MCL) In our research, we propose to use a static version of a DACL: a Multiple Case Library (MCL) with the same structure but being defined statically at the building stage of the Multiple Case Library. MCL approach is intended for supervised domains. Main rationale for a MCL is the same than for a DACL: the main problem in hierarchical Case Libraries retrieval task is that sometimes is impossible to reach most similar cases due to an exploration in a wrong area of the hierarchy. This problem could be because the hierarchy of nodes does not correspond to the relevance of the attributes, as for example a bad –unique– discrimination ordering of the attributes. Our proposal to overcome this problem is to split the case library in a set of different smaller case libraries. These smaller case libraries can provide a faster search because they have a smaller number of tree levels, and in addition, they can provide more accurate similar-case search because each Case Library corresponds to a different prototype (Meta-case) of cases in the whole domain. 86 The retrieval process in a MCL starts matching the current/query case against a set of prototype cases, called meta-cases, to select one (or more) case libraries to search in. This approach tries to build several hierarchical structures for suiting different kind of cases, making the CBR system more flexible, accurate and reliable. In a MCL, the number of meta-cases and its corresponding Case Libraries has been fixed a priori, rather than dynamically like in a DACL structure. One common situation is when the domain or database is supervised, and there is a class label for each case. Then, all the cases sharing the same class label form the corresponding cluster, and its prototype is the Meta-case. In other unsupervised situations, a previous clustering process or a general dynamic incremental process can give, as a result, the set of Meta-cases to be used for splitting all the cases in the corresponding set of case libraries. For each Meta-case (cluster of cases), a hierarchical structure (k-d tree) is constructed to discriminate among all the cases belonging to the same cluster. Each sub-library is organized hierarchically with the same layers than a DACL: • The Meta-case: The Meta-case is the prototype of a concrete cluster of cases. • The clusters: The set of cases belonging to the same cluster, and that are being represented by the Meta-case • The indexing structures (discriminant trees, k-d trees, etc.): Represents the way that all the cases in a given cluster are organized in the corresponding sub-library. In the top level of a MCL could exist several Meta-cases, where each one describes a subtype of cases in the general domain (class type) stored in MCL. In next level, the hierarchical structures/trees are employed as an indexing strategy which aim is to improve both the time retrieval and the accuracy of retrieved case/s. MCL is a very flexible structure because in the second level, any hierarchical strategy could be used. Furthermore, a MCL has the flexibility to mix different strategies. For instance: the second level of any Meta-case, i.e., the hierarchical/tree level, could have a special method implemented within: a standard k-d tree, a NIAR k-d tree, a binary tree, etc., where this method improves the retrieval especially in this kind of cases (subdomain). 87 This characteristic endows MCLs to deal with an introspective reasoning method and allows the selection of the best indexing technique for each meta-case. The implementation of possible different methods at indexing levels avoids the implementation of the same retrieval algorithm for all data in the whole MCL, always aiming to improve the performance and quality of the system. This third level of a MCL is where several approaches will be tested in chapter 6: standard k-d trees, NIAR k-d trees, the same approaches with a Partial Matching Exploration strategy (PME) and the same approaches with the hyperball with bounds strategy. Therefore, an experimental testing will be undertaken to show whether the use and combination of the new approaches proposed against previous well-known used techniques improves the efficiency and competence of CBR systems. 88 89 4 Improving the retrieval task Case retrieval is one important step in the case-based reasoning cycle, especially related to the time efficiency of a CBR system. Several algorithms have been proposed for the hierarchical indexing of cases, since the original indexing approach of k-d trees appeared in the literature. Main approaches propose to use a pre-computed binary search tree to get an average logarithmic time effort in searching. The basic ideas of the proposal are indexing algorithms based on the principle of binary search trees for efficient case retrieval according to a given similarity measure sim. In next sections, the AvKd-Tree, the NIAR k-d tree and the Partial Matching Exploration (PME) technique will be proposed and explained. 4.1 AvKd-Tree An algorithm called AvKd-Tree is introduced. AvKd-Tree is a proposal with better performance in retrieving time than a standard k-d tree, but no better than a NIAR k-d tree. AvKd-Tree spends least retrieval time than standard k-d tree in databases with large amount of data. However, in databases with a considerable amount of data the behavior is similar to a standard k-d tree. In the next section, the algorithm will be explained. The rationale behind AvKd-Tree approach is to try to get the sub-trees of each internal node as much balanced as possible, in order to reduce the number of tree levels, and consequently increase the retrieval speed. The approach is to deal the incremental problem in the building of k-d trees, especially when facing continuous domains, where a lot of new cases are generated and must be stored progressively in the case base. The indexing strategies should be analyzed and modified to show reasonable time in the updating of the case base indexation. The use of k-d trees, NIAR, AvKd-Tree embedded in DACL gives facilities to build an indexing structure framework with the aim to select the best algorithm for indexing cases that belongs to its representative Meta-case. The selection of the best method is according of the framework proposed. Its behavior is learned following a set of evaluation rules 96 Fig. 14. Splitting step in the generation of a NIAR k-d tree The average computational time for generating a NIAR k-d tree is 𝑂𝑂(𝑛𝑛∗ 𝑙𝑙𝑙𝑙𝑙𝑙2𝑛𝑛), being 𝑛𝑛 the number of cases, and 𝑂𝑂(𝑛𝑛2) for the worst case, improving the effort for generating the k-d tree of some of the standard k-d trees. 4.3 Partial Matching Exploration (PME) Technique In this section, a partial matching exploration technique (PME) for a tree indexing structure is proposed (figure 15). It is a technique to explore a hierarchical case library, with a tree indexing structure aiming to not to lose the most similar cases to a query case. The basic idea underlying the process is to prevent from the fact that some potentially good (similar) cases could not be reached in the retrieval process. Such an unsuccessful search in the case library will lead to a bad retrieving strategy. Among the causes originating these failures there is a wrong choice at a high node in case library as an effect of the discretization process of the node attribute values or, if the hierarchy of nodes does not correspond to the importance of the attributes, as for example a bad discrimination order of the attributes, etc. The partial matching exploration technique means that not only the best matching path will be traversed, but also several alternative partial matching paths will be explored. The exploration task searches the case library with two exploration techniques: best matching exploration and partial matching exploration. The best matching exploration means that 97 only the best1 child (best matching node) will be explored. It is the common search of the case library following the main path through the hierarchical case library. The partial matching exploration means that the two best children (best and second-best matching nodes) of the current node will be explored. At root node of the tree, the partial matching exploration is used. That means the two best children of the root node will be explored. The best child is explored again with partial matching exploration, and the second-best child is explored with best matching exploration, if possible. Summarizing, the nodes on the best matching path (main path) are always searched with partial matching exploration, and the nodes on the alternative matching paths are searched with best matching exploration. Being 𝑘𝑘 the maximum number of attributes used in the tree, then at most 𝑘𝑘 paths from the root are explored, and at most 𝑘𝑘2 nodes are explored. So, the searching time 𝑇𝑇(𝑘𝑘), is upper bounded by a function of the number of attributes used in the tree, usually smaller than the number of cases (𝑛𝑛) stored in the Case Library, and does not depend on it, which is usually bigger as the system grows: 𝑇𝑇(𝑛𝑛,𝑘𝑘) ∈ 𝑂𝑂(𝑘𝑘2). Fig. 15. Partial-matching exploration 1The most similar value to the query case value for the attribute of the corresponding node. 98 Thus, the cases retrieved are all the cases stored in the Case Library differing at most in one attribute's value from the query case (see figure 15). Therefore, this partial matching technique allows recognizing partial matching cases as possible similar cases to the query case. Below, the Partial Matching Exploration algorithm is described. The algorithm has a main class called PME. This class has two methods named last and second. Algorithm 7: Partial Matching Exploration (PME) Input: root of the tree 1 Case node 2 Output: the most similar cases collectes through the ex-3 ploration of the tree 4 Begin PME(case_node, root) 5 if(case_node != root){ 6 different = true; 7 break; 8 } 9 if(case_node[root.Attdisc] <= root.Dato[root.Attdisc]){ 10 if(!different){ 11 root.left = true; 12 root.MainPath = true; 13 nearest[dist_count] = root.ID; 14 Distance[dist_count] = this.Euclidean(case_node, 15 root.Dato); 16 dist_count++; 17 } 18 else{ 19 if (root.left != null){ 20 root.left = true; 21 root.MainPath = true; 22 nearest[dist_count] = root.ID; 23 Distance[dist_count] = this.Euclidean(case_node, 24 root.Dato); 25 dist_count++; 26 PME(case_node, root.left); 27 } 28 else{ 29 root.MainPath = true; 30 main = root; 31 nearest[dist_count] = root.ID; 32 99 Distance[dist_count] = this.Euclidean(case_node, 33 root.Dato); 34 dist_count++; 35 second(nearest, dist_count, root, case_node); 36 } 37 } 38 } 39 else{ 40 if (root.right != null){ 41 root.Mainright = true; 42 root.MainPath = true; 43 nearest[dist_count] = root.ID; 44 Distance[dist_count] = this.Euclidean(case_node, 45 root.Dato); 46 dist_count++; 47 PME(case_node, root.right); 48 } 49 else{ 50 root.MainPath = true; 51 main = root; 52 nearest[dist_count] = root.ID; 53 Distance[dist_count] = this.Euclidean(case_node, 54 root.Dato); 55 dist_count++; 56 second(nearest, dist_count, root, case_node); 57 } 58 } 59 endPM 60 61 Method: second 62 Begin second(nearest,ser,root,case_node){ 63 if (root.dad != null){ 64 root = root.dad; 65 if (root.Mainright == true) { 66 if (root.left != null) { 67 nearest[ser] = last(root.left, case_node); 68 Distances[ser] = this.Euclidean(case_node, 69 root.Dato); ser++; 70 second(nearest, ser, root,case_node); 71 } 72 else 73 second(nearest, ser, root, case_node); 74 } 75 else{ 76 if (root.right != null) { 77 100 nearest[ser] = last(root.right, case_node); 78 Distances[ser] = this.Euclidean(case_node, 79 root.Dato); ser++; 80 second(nearest, ser, root, case_node); 81 } 82 else 83 second(nearest, ser, root, case_node); 84 }}} 85 Method: last 86 Begin last(root, case_node) { 87 if (case_node[root.Attdisc] <= root.Dato[root.Attdisc]) { 88 if (root.left != null) { 89 last(root.left, case_node); 90 } 91 else 92 Aux = root; 93 } 94 else{ 95 if (root.right != null) { 96 last(root.right, case_node); 97 } 98 else 99 if(root.left != null) 100 last(root.left, case_node); 101 else 102 Aux = root; 103 } 104 return Aux.ID; 105 }106 The PME algorithm requires the 𝑁𝑁𝑐𝑐 (case_node) and the root node of the tree to start its process. The first task (lines 2-5) checks if the 𝑁𝑁𝑐𝑐 matches with the root node. If the node does not match, then checks the relevance of the attributes between root and case_node. If the value of attribute in case_node is lower than root (line6),then checks if it has a left son (line 16) and if it has one, then the nearest node going to be root (line 19). Then the Euclidean distance is computed (line 20) and stored in the node. Then PME algorithm is called sending the case_node and the left son (line 23). Else root its labeled as main path and the euclidean distances between case_node and root is estimated (lines 26-31), then the second best match is going to be search calling the method second (line 32). 101 If the value of attribute in case_node is higher than root (line6) then the right side is checked searching for a right son. And the same dynamic is computed (lines 36-54). The method called second requires beginning the nearest case, the case_node and the root node. The first question is whether the root has any son, on right side (line 62). If it has a son, then the last method is called with the aim of finding the nearest case (line 64), the Euclidean distance is computed, after this task second method is called with new values (line 67). Then, once computed the procedure in the right side then it is the left sides turn, following a similar criteria (lines 72-81). The task of the method last has the main task of finding the last node in the path. To start it job it requires the root node and the case_node. The criterion to find the last node is to compare the values of the attributes in the case_node and the root node (line 84). Then the recursive search in left and right sides begins (lines 86, 93, 97). The computing is successful when the last node is returned. 102 5 Improving the maintenance and learning of the Case Library The improving of the CBR cycle it is one of the challenges for case base maintenance policies, especially in domains with large amount of cases, and even more, if data are changing. In this chapter, some maintenance policies and methods aiming to improve the maintenance and learning of the CBR cycle are introduced. The first method introduced is related to the improvement of the learning of the DACL proposing a stochastic method to build the representative prototypes (Mc) in a dynamic environment. The proposed method considers two moments for the learning of prototypes. The moments will be detailed. For the supervised domains with DACL, the proposal is to use Multiple Case Library (DACL/MCL). The chapter introduces one additional policy for building the representative prototype. 5.1 The Stochastic Learning Strategy In previous chapter 3, the details of the DACL framework have been introduced and a method to build Meta-cases has been proposed. The method has the characteristic of building a Meta-case following the strategy of computing a centroid as a Meta-case. This second method of computing a Meta-case considers a Stochastic Method. It has two core moments used in the learning algorithm. One of the open problems in clustering field is to select the number of clusters; this is relevant in a DACL too. When there are several sublibraries in the DACL and a dispersion of the cases is generated, then the quality is coming down. On the contrary way, when there exists a few number of sub-libraries and these are compact, the quality its better and the retrieval time is faster. With the following learning policy, DACL is able to learn and classify continuous data precisely, according to the expert’s evaluation, as we will explain in the evaluation chapter 6. The proposed method has the ability to learn Meta-cases (𝑀𝑀𝑐𝑐) as is depicted in figure 12. In this work, a Mc is described as follows: 104 The 𝑀𝑀𝑐𝑐’𝑠𝑠 are designed as the top level of the DACL strategy; this has two aims. The first is when a New Case (𝑁𝑁𝑐𝑐) is being considered by the DACL. It has to learn it and store it in the best optimal way or decide not to store it; and second, when the best case has to be retrieved, this strategy should improve time and quality of the process avoiding an exploration in a wrong sub-library. A 𝑀𝑀𝑐𝑐 is a prototype of the entire cases belonging to the sub-library. The Mc in DACL helps to find the most optimal sub-library where the cases have to be learnt. The Mc is a generalization of the cases stored in the sub-library. The 𝑀𝑀𝑐𝑐 is built following the next Mc building process: 1) A case 𝐶𝐶𝑖𝑖 is defined as 𝐶𝐶𝑖𝑖=�𝐶𝐶1 𝑠𝑠,𝐶𝐶2 𝑠𝑠,⋯,𝐶𝐶𝑚𝑚 𝑠𝑠� where𝐶𝐶𝑗𝑗=1,…𝑚𝑚 𝑖𝑖, are the attribute values describing the case 𝐶𝐶𝑖𝑖 and where 𝑠𝑠 is the current case of the total of 𝑛𝑛 cases belonging to the corresponding Mc. 2) A 𝑀𝑀𝑐𝑐𝑙𝑙 is defined as 𝑀𝑀𝑐𝑐𝑙𝑙= < 𝑀𝑀𝑐𝑐1 𝑙𝑙… 𝑀𝑀𝑐𝑐𝑚𝑚 𝑙𝑙> where 𝑀𝑀𝑐𝑐𝑗𝑗=1,…,𝑚𝑚 𝑙𝑙, are the computed attribute values of the Meta-case as the average prototype values for continuous/numerical attributes or the most frequent values (mode) of discrete categorical values, according to the following formulas: If 𝑚𝑚𝑛𝑛𝑛𝑛𝑗𝑗 is numerical: 𝑀𝑀𝑐𝑐𝑗𝑗𝑙𝑙=1 𝑎𝑎𝑙𝑙∑𝐶𝐶𝑗𝑗𝑘𝑘 𝑎𝑎𝑙𝑙 𝑘𝑘=1 and #𝑐𝑐𝑚𝑚𝑠𝑠𝑈𝑈𝑠𝑠(𝑀𝑀𝑐𝑐𝑙𝑙) = 𝑛𝑛𝑙𝑙 If 𝑚𝑚𝑛𝑛𝑛𝑛𝑗𝑗 is categorical: 𝑀𝑀𝑐𝑐𝑗𝑗𝑙𝑙=𝑚𝑚𝑙𝑙𝑚𝑚𝑈𝑈(𝐶𝐶𝑗𝑗𝑘𝑘) 𝑘𝑘 = 1, . . . , 𝑛𝑛𝑙𝑙 The proposed strategy modifies the total number of attributes of the case, where a case 𝐶𝐶𝑗𝑗 is defined by its attributes <𝐶𝐶1 𝑗𝑗… 𝐶𝐶𝑚𝑚 𝑗𝑗>. The strategy adds a new attribute 𝐶𝐶𝑎𝑎𝑠𝑠 𝑗𝑗, and then, a case 𝐶𝐶𝑗𝑗 is described as <𝐶𝐶𝑎𝑎𝑠𝑠 𝑗𝑗,𝐶𝐶1 𝑗𝑗…𝐶𝐶𝑚𝑚 𝑗𝑗>. This new attribute is a time stamp ordering identifier (ts). The new attribute is initialized at 𝑛𝑛𝑠𝑠= 1 and increases one by one. The increase occurs when a new case is stored in the sub-library. This 𝐶𝐶𝑎𝑎𝑠𝑠 𝑗𝑗 value is considered like an attribute in the algorithm. The attribute is used in both first and second moment of the stochastic method proposed. It is named as 𝜏𝜏. 𝜏𝜏 plays the role of time, an ordered attribute, 105 like in the statically normal stochastic method. The value of 𝜏𝜏 helps to increase the differences of cases adding an increase value between them. The value is taken into account when first moment is computed (see formula 9). The method can be summarized as follows: when a new case arrives, and the algorithm is working to find the Mc most similar to the case, the 𝜏𝜏 value gives a direct difference and make that Mc’s be filtered more effectively, because a low 𝜏𝜏 value indicates “most similar” while a higher 𝜏𝜏 value indicates a higher separation of the cases. Other relevant use of the 𝜏𝜏 value is when the prototype is built; this is depicted in step 2 of the Mc building process, previously introduced. Here, the value of the first attribute of the Mc is 1. When the Mc is updated, the second value is 1.5. At the third step the value is 2, and continues increasing following a constant increase of 0.5 for update iteration. These values are generated computing the step 2 in formula of Mc building process. The learning of new cases and the building of its representative prototype it is one of the aims to achieve in a DACL. To get a successful learning of cases and a good quality of learning Mc’s is introduced a Stochastic Learning 𝑀𝑀𝑐𝑐’𝑠𝑠 Method “SLMcM”. SLMcM considers two relevant moments to guide the learning. The first moment is described as: 𝜌𝜌=min 𝑗𝑗𝑚𝑚𝑈𝑈𝑙𝑙𝐷𝐷�𝑁𝑁𝑐𝑐,𝑀𝑀𝑐𝑐𝑗𝑗� (8) Formula 8 is computed to find the most similar 𝑀𝑀𝑐𝑐 in DACL to the new case 𝑁𝑁𝑐𝑐. 𝐷𝐷 is the distance function that evaluates the dissimilarity value. And 𝜌𝜌 will represent the most similar prototype selected. The similarity of a new case will be assessed against all 𝑀𝑀𝑐𝑐’𝑠𝑠 by means of the same dissimilarity measure used in the normal assessment of similarity between two cases. In this case, the proposed measure is the Euclidean distance when all attributes are numerical, but other heterogeneous measures can be used when both numerical and categorical attributes exist. The method for finding the most similar 𝑀𝑀𝑐𝑐 can be summarized in following Search similar Mc algorithm. 112 each cluster of cases will be created. In addition, the cases will be stored in their corresponding tree node, according to the splitting criteria of the indexing structure. Regarding the NIAR k-d tree, the splitting value at each node is the nearest value of the cases to the average value of the attribute. Therefore, at the beginning all the average values for all the attributes are computed and the nearest value present in the corresponding cases for those attributes are selected as the splitting values at each node. The problem is that when the system is continuously learning new cases, it can happen that the splitting value of a node, which should be the nearest value to the average value of the attribute, is not anymore the nearest value. This will be caused by the fact that the average value of the attributes is changing continuously. This situation could provoke that the indexing k-d tree could start to be not well balanced in all its subtrees, worsening the retrieval time. This will be a hard problem if the new values of the attribute, which are arriving at the DACL, are very disturbing. For our proposal, we will consider that a value of an attribute 𝑚𝑚𝑎𝑎+1 is a disturbance value ⇔ |𝐴𝐴𝐶𝐶(𝑚𝑚𝑎𝑎)−𝑚𝑚𝑎𝑎+1|≥𝑠𝑠𝑛𝑛𝑚𝑚𝑈𝑈𝐶𝐶(𝑚𝑚𝑎𝑎) That means the values with high dispersion will be those that are far from the mean value of the attribute. Av() is the mean value and stdev() is the standard deviation of the distribution of values. Fortunately, the DACL framework can easily and incrementally compute the new average values for all the attributes, according to the following formula: 𝐴𝐴𝐶𝐶(𝑚𝑚𝑎𝑎+1) = 𝑛𝑛 𝐴𝐴𝐶𝐶(𝑚𝑚𝑎𝑎) + 𝑚𝑚𝑎𝑎+1 𝑛𝑛+ 1 Where Av(xk) is the average mean value of the attribute x according to its first k values (x1, ..., xk). Also the standard deviation can be computed in an incremental way through this formula due to Welford (Welford, 1962): 113 𝑠𝑠𝑛𝑛𝑚𝑚𝑈𝑈𝐶𝐶(𝑚𝑚𝑎𝑎+1)=𝑠𝑠𝑛𝑛𝑚𝑚𝑈𝑈𝐶𝐶(𝑚𝑚𝑎𝑎)+(𝑚𝑚𝑎𝑎+1 −𝐴𝐴𝐶𝐶(𝑚𝑚𝑎𝑎))∗(𝑚𝑚𝑎𝑎+1 −𝐴𝐴𝐶𝐶(𝑚𝑚𝑎𝑎+1)) Our proposal is that the DACL system will trigger a maintenance task to rebuild a concrete indexing NIAR k-d tree, at asynchronous time periods, when the following condition would be satisfied, since the last time the task was fired: #Disturbance values ≥ δ * N where δ is a specified percentage, we propose as initial trial that δ= 0.2 and N is the size of the corresponding sub-library. This criterion mean that when the number of disturbance values is higher than a specified percentage (for instance the 20%) of the number of cases of the sub-library, the task of rebuilding the indexing NIAR kd tree corresponding to the sub-library will be started. A new NIAR k-d tree will be generated with the possible new splitting values at each node of the tree. 5.4.2 Introspective task to improve the learning of new cases As it was detailed in section 5.3.1, there is the possibility to work with real Meta-cases instead of the virtual Meta-cases. The difference relies in the fact that now the prototypes of each cluster (virtual meta-cases) are replaced for real cases. This means that the prototype of a cluster of classes is a case existing within the set of cases of the cluster. Concretely, the real Meta-case will be the nearest real case to the virtual meta-case. The idea is that the real meta-cases perhaps could be a good solution for impasse situations. Impasse situations happen when a new case which must be stored in the DACL is equally similar to more than one virtual meta-case (prototype). Even though a case could be at the same distance to several virtual Meta-cases, perhaps the distance to the corresponding real Meta-cases will not be than same, and the impasse situation could be solved using the following algorithm. 114 Algorithm 12: retaining/learning algorithm avoiding impasses with real 𝑀𝑀𝑐𝑐 Input: the new case solved (Nc) 1 Let MsMC = the virtual Meta-case most similar to the 2 case; 3 Let 2MsMC = the second most similar virtual Meta-case to 4 the case; 5 begin 6 The distance is computed between the new case and the 7 whole set of virtual Meta-cases using the formula 1; 8 if d(NC, MsMC) < α and d(NC, 2MsMC) ≥ α then 9 /* α is the threshold value, predefined by the 10 experts*/ 11 Update the corresponding sub-library with the new case 12 elseif d(NC, MsMC) > α then 13 Build a new sub-library 14 elseif d(NC, MsMC) < α and d(NC, 2MsMC) < α then 15 Use the real Meta-cases instead of the virtual Meta- 16 cases; 17 Select the sub-library with the minimum distance 18 between the case and the corresponding real 19 Meta-cases; 20 The corresponding cluster, the virtual Meta-case, the 21 real Meta-case are updated with the new case; 22 endif 23 end retaining/learning algorithm avoiding impasses with 24 real Mc25 115 6 Experimental Evaluation and Results In the previous chapters, the methods proposed in the thesis have been detailed. In this chapter, the evaluation of the methods is explained, and the results are discussed. The evaluation of DACL/MCL and the policies to improve the CBR reasoning cycle are deeply detailed. In first place, the evaluation of several indexing strategies in supervised domains is detailed. In this evaluation, the algorithms NIAR kd tree and AvKd-tree are compared versus the standard k-d tree for exact-case search such depicted in figure 18, in order to get a feedback from the database field scenario, where k-d trees approach was originated. In the evaluation of proposed strategies, it is considered the evaluation of the quality in the retrieval process and the retrieving time. In this scenario, the depth of tree is evaluated too such depicted in figure 18. After this, the evaluation of a MCL in supervised domains, but using a similar-case search as a guiding searching experimentation, it is detailed and 12 strategies including a flat case library and both standard kd tree and NIAR k-d tree methods for indexing cases are described. In addition, the Partial Matching Exploration (PME) technique is evaluated against the commonly used technique based on the hyperball with bounds technique. To evaluate the case retrieval step, the algorithms for retrieving such as NIAR k-d tree, standard k-d tree, hyperball with bounds and partial matching are analyzed in detail, see figure 17. Then, the promising results are discussed. Next, the Dynamic Adaptive Case library (DACL) is analyzed (see figure 17). An environmental domain has been selected to test the evaluation. To achieve the objective of building representative prototypes in DACL, a stochastic strategy/method has been proposed. In this section, the building of representative meta-cases with the proposed stochastic method is evaluated. Finally, a discussion of the results is presented. The final step in the evaluation scheme has been the testing of the whole Dynamic Adaptive Case Library framework, where the DACL, the NIAR k-d trees, the PME technique have been used to cope with some simulated unsupervised domains in an incremental way. Therefore, this way, the hierarchical structures (NIAR k-d trees) are incre- 116 mentally constructed and all the cases in the databases used are processed in a step by step mode. The figure 17 graphically summarizes the experimentation process. showing the different strategies used to evaluate the different proposals in different domains (supervised and unsupervised). In the figure, the indexing methods implemented are detailed, theexploration ntechnique used, the kind o serach pursued, etc. For the evaluation of the dynamic proposal, the following figure 17 shows sections that are combined when a set of tests is performed. The first section shows the option of not use or to use the structure MCL. Other part indicates the algorithm that could be used as an option for indexing the data and storing in the MCL or NonMCL. Those indexing strategies are evaluated considering the time used in retrieval the information and the quality in retrieval. The four retrieval algorithms are indicated in the figure 17, but the 12 combinations of index method vs retrieval method used to evaluate the proposal are detailed in the sections of this chapter. In the figure 17, the unsupervised domains section, shows the evaluations done with the environmental data base and the strategies that have been used, here the DACL + Stochastic learning method was implemented successfully. The second part is under construction, the strategies that going to be used are DACL + NIAR + PME and the others 12 policies used in the supervised domains. In this occasion the 10 data bases form UCI used in the supervised evaluation going to be used, but in unsupervised point of view that means that the data going to be handled as an unsupervised data arriving as a data stream. Domain Search Library Type Indexing Method Exploration Strategy Fig. 17. Experimentation flowchart 6.1 Avkd-tree evaluation in exact-case search For the experimental evaluation, ten databases from UCI Machine Learning repository (Frank and Asuncion, 2010) were selected. The databases selected are depicted in table 4. All the databases have numerical attributes or categorical ordered attributes, which can be transformed to a numerical ordered attribute. In one database (AB) one attribute which was categorical Not ordered was transformed to a numerical one, to test some future usage in the k-d trees and AvKd-Tree. In table 4 there is the description of all databases used in the experimental evaluation. Table 4. Description of databases used in the experimentation. #Inst is to the total number of instances in the database, #Cont means the total number of continuous/numerical attributes in the database, #CatOrd mens the total number of categorical ordered attributes, #CatNOrd means the total number of categorical non ordered attributes and #Classes refers to the total number of different class labels in the database. Database #Inst #Cont #Cat Ord #Cat NOrd #Classes Abalone 4177 7 0 1 29 Car Eval. 1728 0 6 0 4 Ecoli 336 7 0 0 8 Glass 214 9 0 0 7 Ionosphere 351 34 0 0 2 Pima 768 8 0 0 2 Iris 150 3 0 0 3 Waveform 5000 3 0 0 3 Letter 20000 16 0 0 26 Balance 625 21 0 0 3 We have conducted a test to evaluate the performance of algorithms. The aim of the test was to assess both the retrieval CPU time effort and the depth of the k-d Tree and AvKd-Tree (the distribution of cases at the tree levels). The testing was done for an exact-case search. In the experimentation for each scenario, the same cases are tested (test set) in all trees, and the retrieval time is computed. The experimental validation was done randomly sampling the test set with a number of cases equal to the 15% of data in each database. 119 Each experimental validation in one database was conducted in the following way: • The cases to be retrieved were randomly sampled from the database. • Case retrieval for each query test case was executed for all tree approaches and the retrieval time was computed. • The mean time of all query cases retrieval in test set was computed for each k-d tree approach. • Searching for accurate results, a multiple validation process was undertaken. Each experiment was repeated twelve times in both trees. Once computed the 12 runs for each database with both approaches, the maximal and minimal time consumed were excluded to get more stable results. Thus, finally only 10 runs were considered. • With the ten time mean values obtained before, a final time average over all runs was calculated and this value was the best estimation of a general case retrieval time consumed by the CPU. The whole experimentation was repeated for each one of the databases. The experiments were done in a computer with an Intel Core i7 processor, and 10 GB of RAM. Table 5. Average CPU Time for case retrieval Database k-d Tree Avk-d Tree Glass 16.08 17.43 Ecoli 19.42 19.77 Ionosphere 6.62 7.31 Pima 17.84 23.12 Car 44.47 37.1 Abalone 17.25 16.36 Iris 14.72 9.25 Balance 7.45 5.41 Waveform 15.37 16.01 Letter 13.05 10.12 Mean 17.227 16.18 The table 5 depicts the average CPU processing time for a case retrieval using the two new approaches compared with the standard k-d tree ap- 120 proach, and for all the databases tested. The time computed is expressed in nanoseconds (ns). In figure 18 there is a chart with the respective retrieval time in the approaches for all databases. Fig. 18. Comparison of retrieval time in the approaches The results shown in table 5 and figure 19 depict a difference in time consuming when a search is implemented. It seems that the proposed AvKd-Tree strategy is more efficient in retrieving information than standard k-d tree in some occasion, but it is clear that Avk-d tree strategy is generally more efficient than Kd-Tree strategy. The comparison between AvKd-Tree strategy and standard k-d tree approach gave as a result that AvKd-Tree strategy is on average 1% better. The data sets Abalone, Letter, Waveform and Car databases are the databases show a higher reduction in the depth of the tree (32, 21 ad 21 levels reduction) despite that they are the largest databases (4177, 20000, 5000 and 1728 respectively). The second dimension that was used to evaluate the AvKd-Tree strategy and k-d tree proposal was the evaluation of the tree depth and the distribution of cases at the different levels of the trees. The table 6 shows 0 5 10 15 20 25 30 35 40 45 50 k-d Tree AvKd-Tree 121 significant differences in the number of tree levels in the trees, for all the databases. Table 6 shows the depth level of the AvKd-Tree strategy and the standard k-d tree approach. In all databases, AvKd-Tree strategy build the trees with a significant reduction of levels, and the standard kd tree builds the trees with more levels causing a more expensive time in the retrieval. Abalone, Pima and Iris databases are the databases showing a higher reduction in the depth of the tree (46, 37 and 28 levels were reduced to 14, 16 and 13 levels respectively) despite some are the largest databases. Not surprisingly, most of these databases are the ones were the time retrieval reduction was higher. This fact means that the reduction in time retrieval is directly correlated with the decrease in the number of levels in the trees. Table 6. Depth of trees generated using in approaches Data Base k-d Tree AvKd-Tree Abalone 28 15 Car 14 13 Ecoli 21 14 Glass 26 16 Ionosphere 19 62 Pima 46 17 Iris 37 12 Balance 15 11 Thus, it is very interesting to try to find out to which factor is due the reduction of levels. A reasonable answer is that the trees would be more balanced, i.e. the number of nodes in the tree will be more uniformly distributed along the different levels of the tree. In order to check this hypothesis a third dimension was investigated: the nodes expanded at each level. This means that the tree should be expanded uniformly in breadth, and not to generate extra levels in the tree increasing the depth of the tree. 128 In the previous section, it was shown that the NIAR k-d tree was a promising technique for improving the time efficiency, but it should be tested for similar-case retrieval, which is the usual search done in CBR systems, different from common exact-case search in databases. In addition, it should be tested regarding to competence of the CBR system and the new proposed partial matching exploration technique should be tested too. The commonly used approaches in the literature are the use of just one case library, the standard k-d tree approach (Broder 1990; Friedman et al. 1977; Bentley, 1975), the hyperball with bounds exploring strategy (Friedman et al., 1977) improved with the virtual bounds technique (Wess et al., 1993). See section 2.1.2. Through the experimentation tests, it will be showed that the use of a Multiple Case Library (MCL) embedding a NIAR k-d tree, and using the additional strategy of partial matching to explore the indexing structure (the tree) provides a very good approach both to improve the time efficiency and the competence accuracy for case retrieval task in CBR systems. 6.3.1 Experimental Settings Eight databases from UCI Machine Learning repository (Frank and Asuncion, 2010) were selected in order to test the different combination of approaches and strategies. All databases have numerical attributes or ordered categorical attributes, which can be transformed to an ordered numerical attribute, because all k-d trees can only cope with numerical or categorical ordered attributes, where an order relation exists. In table 4, Abalone database has one categorical attribute, which was not ordered. It was transformed into a numerical one aiming to be possible to use the standard k-d tree and NIAR k-d tree approaches to compute the partition value (median value, nearest value to mean value). The complete properties of each database are compiled in table 4. The experimental setting was done under the following characteristics: • The above eight databases were tested 129 • As a baseline, the Flat Case Library was considered which gives the upper bound of the accuracy. • Twelve different strategies (plus the baseline strategy) were considered combined the different possibilities for the structure of the Case Library (Non MCL/MCL), The Case Library Indexing structure (Standard k-d Tree/NIAR k-d tree) and the additional exploring strategies (none/Partial Matching/Hyperball with bounds): o S0: Flat Case Library o S1: Standard k-d tree o S2: Standard k-d tree + Partial matching exploration o S3: Standard k-d tree + Hyperball with bounds exploration o S4: NIAR k-d tree o S5: NIAR k-d tree + Partial matching exploration o S6: NIAR k-d tree + Hyperball with bounds exploration o S7: MCL + Standard k-d tree o S8: MCL + Standard k-d tree + Partial matching exploration o S9: MCL + Standard k-d tree + Hyperball with bounds exploration o S10: MCL + NIAR k-d tree o S11: MCL + NIAR k-d tree + Partial matching exploration o S12: MCL + NIAR k-d tree + Hyperball with bounds exploration • For each database and for each strategy, a 10-fold cross validation was performed, taking sequentially (10 runs), each fold as a test set and the other nine folds as the training set. • The average time retrieval of one case (in µs) and the average success on label classification of the cases (in percentage), as an estimation of the competence accuracy, was computed for each database and for each strategy, as an average quantity among the 10 runs of the cross validation. 6.3.2 Experimental Results The tables 11, 12, 13 and 14 show both the average CPU processing time, and the average percentage of success in predicting the 130 correct class label of the cases, for a case retrieval using the different strategies for all the databases tested. In addition, two new columns labelled as “Average” show the average values across all the databases to give an estimation of each strategy (see table 14). Finally, the last two columns added give the “Average Reduction of each strategy regarding the baseline strategy” (S0, Flat Case Library) across all the databases (see table 14). Table 11. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases. 131 Table 12. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases (continued from table 11). Table 13. Average CPU Time (in µs) for case retrieval and average Success (in %) in class label prediction for all the strategies, and for all the tested databases (continued from table 12). 132 Table 14. Statistics of tables 11, 12 and 13. Fig. 20. Comparison of averaged success (%) across all databases for the class label prediction in all the strategies 133 Figure 21 shows the average CPU retrieval time for one case across all the databases depicted in tables 11, 12 and 13, for each strategy minus the baseline Flat Case Library, in a graphic. The baseline is not depicted in order not to distortion the graphic, because its value is much higher than the other ones, and then, the differences among the other strategies could not be appreciated. Fig. 21. Comparison of averaged CPU retrieval time (µs) across all databases for the class label prediction in all the strategies minus S0 (baseline Flat Case Library) 6.3.3 Discussion of the results 6.3.3.1 Non-MCL strategies Regarding the strategies which use only one case library (non- MCL strategies, i.e., S1 to S6), the use of an additional exploration technique (partial matching or hyperball with bounds) leads to an increase between 8-14% in the accuracy regarding not using them, as it is shown in figure 22. Therefore, they seem useful for increasing the accuracy. 134 Fig. 22. Increase of accuracy The NIAR k-d tree approach without any additional exploration strategy (S1) compared with the standard k-d tree without any additional strategy (S4) is slightly better in accuracy on average, but slightly worse in time. Anyway, these differences are not significant. Fig. 23. Reduction of accuracy Comparing the same additional exploration technique with a standard k-d tree (S2 or S3) and with a NIAR k-d tree (S5 or S6) there is a 5% approx., reduction in accuracy (see figure 23). This means that for a Iris Glass Balance Pima Ionosphere Abalone Car Ecoli Kd-tree 65,03 43,4 35,3 47,83 64,2 32,23 60,97 55,2 NIAR 71,47 43,6 35 50,57 62,97 32,17 61,33 55,3 0 10 20 30 40 50 60 70 80 Increase of accuracy Iris Glass Balanc ePima Ionosp here Abalon eCar Ecoli Kd-tree 79,7 50,8 46,2 51,9 63,8 30,7 56,1 62,1 NIAR 81 45,7 48,2 53,4 65,6 30,3 51 23,1 0 20 40 60 80 100 Reduction in accuracy 135 single Case Library approach, it seems to be a better option to use the standard k-d tree than a NIAR k-d tree. Regarding the time performance, all these non-MCL strategies (S1 to S6) make an important reduction in time (more than 97%) regarding the baseline strategy (S0), which is a linear sequential search over the Case Library, see following table 15. Table 15. Time performance. 51.84 470.84 Average S0,S6 %Succ Time 76.83 17759.6 Average Reduction regarding baseline S6 %Succ Time 24.99 97.34882 Anyway, what can be observed is that the partial matching exploration strategies (S2, S5) have significative better results in time than the corresponding hyperball with bounds strategies (S3, S6), independently if they use a standard k-d tree or a NIAR k-d tree. That means the partial matching exploration technique is a very good option to reduce the time retrieval. Therefore, among all strategies using only one Case Library (S1 to S6), and taking into account both the accuracy and time features, probably the best strategy would be the standard k-d tree with partial matching exploration (S2, with an average of 55.16% of accuracy and with an average of 188 µs for case retrieval). In addition, the NIAR k-d tree with partial matching exploration could be also a good option (S5, with an average of 49.79% of accuracy and with an average of 27 µs for case retrieval). 6.3.3.2 MCL Strategies Regarding the strategies which use a Multiple Case Library (MCL strategies, i.e., S7 to S12), the use of an additional exploration 136 technique (partial matching or hyperball with bounds), as in the non- MCL strategies, leads to an increase between 9-17% in the accuracy regarding not using them as it is depicted in table 16. Therefore, it can be confirmed that these techniques increases the accuracy. Table 16. Increase of the accuracy. Moreover, all MCL strategies (S7 to S12) improve the accuracy of its corresponding non-MCL strategies (S1 to S6) by 8-19%. The k-d tree approach without any additional exploration technique (S7) compared with the standard NIAR k-d tree without any additional exploration technique (S10) is slightly worse (2%) in accuracy on average, and slightly worse in time. Comparing the same additional exploration technique with a standard k-d tree (S8 or S9) and with a NIAR k-d tree (S11 or S12) there is a different behavior. With the partial matching exploration, there is a 4% approx. increase in accuracy using the NIAR k-d tree. On the contrary, with the hyperball with bounds technique, there is a 4% approx. reduction in accuracy using the NIAR k-d tree. This means that for a Multiple Case Library approach, it seems to be a better option to use the NIAR k-d tree with partial matching exploration. This strategy reaches a 68.41% of accuracy see following figure 25, the best among all alternatives to the baseline, just only 8.4% lower than the 76.8% of accuracy of the baseline strategy (S0), which is the maximum possible accuracy. Average S7,S11 %Succ Time 76.83 17759.6 57.44 1.12 68.41 57.76 Average Reduction regarding baseline S7,S11 %Succ Time 19.39 99.99369 8.42 99.67477 137 Fig. 24. Increase of accuracy in NIAR Regarding the time performance with the MCL strategies, the same situation as with the non-MCL strategies can be observed. All MCL strategies (S7 to S12) make an important reduction in time (more than 97%) regarding the baseline strategy (S0). Notwithstanding, the time employed is lower in strategies using an additional exploration technique (S8, S9, S11, S12) than its corresponding non MCL strategies (S2, S3, S5, S6). S7 and S10 have slightly higher time retrieval, but it is almost the same value. Again, it can be observed that the partial matching exploration techniques (S8, S11) have significate better results in time than the corresponding hyperball with bounds techniques (S9, S12), independently if they use a standard k-d tree or a NIAR k-d tree. Thus, it confirms that the partial matching exploration technique is a very good option to reduce the time retrieval. Therefore, among all strategies using a Multiple Case Library (S7 to S12, depicted in table 17), and taking into account both the accuracy and time features, probably the best strategy is clearly the NIAR k-d tree with partial matching exploration technique (S11, with an average of 68.41% of accuracy and with an average of 57 µs for case retrieval). Iris Glass Balan ce Pima Ionos phere Abalo ne Car Ecoli MCL-Kd-tree 82,3 39,6 66,8 60,5 67,9 46,7 70,4 77,7 MCL-NIAR 91,8 45,7 74,9 63,1 72,8 48,2 71,3 79,5 0 20 40 60 80 100 increase in accuracy using the NIAR k-d tree. 144 When γ=0.2 the algorithm generates three prototypes. In this situation, the prototypes represent the behavior of the environment in three phases. First is between 0-12 hours; this behavior covers the human activities of the first and second period, according the prototype when the γ=0.1. Between the 12-22 hours covers the behavior when people takes a break to lunch and goes to pick up children to school, and finally when people ends the working day. In the 22-24 hours, the people travel to home or maybe going to other places. Having in consideration this arguing, the second γ policy evaluation value could be acceptable, but is more interesting and realistic the first one according the argumentation of the environmental experts. Anyway, when γ experiments the other values of 0.3, 0.4 and 0.5, the obtained results are out of a reasonable behavior. One explanation of this fact is that the evaluation threshold is extended too much, and the relaxation learning policy is higher, mixing different prototypes in only one mixed prototype, which does not represent a clear different environmental situation, but a merge of several conditions. While in first evaluation of γ=0.1, the relaxation is more demanding, and only cases that accomplish the stochastic moments are learned. A normal behavior of nature could be described as follows. At the end of the day, when the human activity is reduced and considering all the night and the first minutes (00:01) of the new day, the nature have a break, and at this time, the nature activity is more effective. Then, the improving of the air quality is higher. When the human activity begins, the air quality starts to going down. At late hours, the concentration of contamination increases and is reduced until the human activity is reduced. Therefore, the cycle ends and begins again. Once the prototypes have been built, the following task is to evaluate the first policy. The policy aims to measure the separation between Mc’s. The following table shows the results in the evaluation of the prototypes when γ=0.1. The prototypes evaluated have been selected having in mind the evaluation of γ, and the comments of the environmental experts. 145 Table 19. Distance measures between the Mc’s obtained for γ=0.1 Mc 1 Mc 2 Mc 3 Mc 4 Mc 1 030.967 30.666 53.225 Mc 2 30.967 021.120 26.185 Mc 3 30.666 21.120 037.394 Mc 4 53.225 26.185 37.394 0 The normalization of the data between 0 and 1 is an usual procedure in data mining. However, in this special case, data are computed and represented on its natural values, with the aim of following the International and Mexican norms, as it is depicted in table 19. Table 19 shows the distance evaluation between prototypes. The table shows blocks of different colors. For the evaluation, we concentrate in the cases situated in the white blocks. According to the results depicted in table, all prototypes are separated for a good distance between them. This is an indication that the prototypes are well structured, and the use of the stochastic steps works fine. The prototypes never overlap. The second evaluation is the implementation of the second policy. This is done through the implementation of the formulas 11, 12, 13 and 14 for the prototypes. Previously, it has been introduced the aim and meaning of the formulas, which is to evaluate the quality of the learning (or the building of new prototypes), starting with an empty casebase. The table 20 depicts the results of the implementation of each formula for the prototypes. Table 20. Results of the different formulas assessment Mc '1 Mc '2 Mc '3 Mc '4 Mc '5 Formula 11 41,93658 24,88025 21,41534 61,14482 11,46441 Formula 12 840,1143 1320,691 1802,095 2336,38 2860,231 Formula 13 19794,06 7588,476 6317,526 21645,27 149,0373 Formula 14 23,56115 5,745838 3,505657 9,264447 0,052107 Formula 11 computes an average while formula 13 computes the sum of distances between the cases and the prototype. These two formulas help to view the compactness of the sub-library. Especially in formula 13, it is possible to assess how far the cases to its prototype are. Here, a 146 reduced value is desired, because it will be an indicator of a good compact sub-library (hard sub-library). A high value indicates that the cases are far from its prototype. Then, the class/cluster is not too compact. Thus, it is soft. Taking into account results, the prototypes one and four are the prototypes that could be soft, because both have the higher values, and where prototype 1 has more than Mc 4. Prototype 4 has the higher separation of its cases. These prototypes represents the first and last hours of the day, where the human activity it is reduced. Prototypes two and three are the harder prototypes, and are the prototypes which represents when the human activity is high. The harder prototypes are the cases more nearest to its prototype. The evaluation of the magnitude of each prototype is computed, and the results are depicted in table 20 as results of formula 12. According to the experts, in the morning the air quality is good, but with the human activity, the air quality is going worst. This behavior is expected in data. In the evaluation of the prototype, could be seen how the values for each prototype increases. The increase of magnitude shows us that the pollution has been increased. Finally, in formula 14, a similarity of the prototype and the evaluation of distances are computed. This similarity gives an idea of how representative is the prototype of all the cases that are stored/summarized on it. To have a full evaluation of the results the following table 21 shows the evaluation of the dispersion of the data in the prototypes. Table 21. Standard Deviation of Prototypes Mc'1 93.83733 Mc'2 34.00873 Mc'3 29.97352 Mc'4 107.1802 Mc'5 158.8435 Table 20 in formula 11, 13 and 14 shows a pattern as result of the iplementation of the stochastic method. Table 21 shows the standard deviation evaluation, which depicts the hard prototypes and soft prototypes. In hard prototypes, the cases tend to be very close to the Mc, which is the situation of Mc’2 and Mc’3. Others prototypes are spread out over a large range of values. This behavior is depicted in both tables. 147 Table 20 and 21 complements the evaluation of the prototypes, but especially in the evaluation of prototype 5 the result is low, the magnitude is high, and the distance is low, but the number of cases is reduced. In this case, is essential the evaluation of the dispersion results that is the higher value and magnitude is higher too. It is positively surprising that the pattern of air quality in the city matches with the citizen daily behavior. 6.5 Testing incrementally the whole DACL Framework An exhaustive experimentation combining all the main contributions of this thesis work: Dynamic Adaptive Case Library (DACL), Incremental NIAR k-d Tree building, PME technique, Stochastic Learning and Relevant Case learning policies, have been carried out. This experiments provided the confirmation that the proposed DACL framework is especially suitable to cope with incremental data streams. It is not easy to cope with an unsupervised database, where in an incremental way, a lot of cases are being generated, and must be processed by the CBR system. This way, the system has not so much cases in its Case Library like in a non-incremental processing scenario. This means that it is pretty more difficult to achieve good accuracy percentages, because at the beginning of the processing, normally the precision will be lower than when working in a non-incremental scenario. Fortunately, the experimentation done has outlined that the DACL approach is able to satisfactorily cope with unsupervised and incremental scenario. As showed later the DACL approach has been able to detect and construct the same number of meta-cases (prototypes) 6.5.1 Experimental Settings The same 10 databases (Abalone, Balance, Car evaluation, Ecoli, Glass, Ionosphere, Iris, Letter, Pima and Waveform), from the UCI repository, used in section 6.3 were also used here. In table 4 there is the description of main features of all these databases. The experimental setting was done under the following characteristics: • The above ten databases were tested 148 • As a baseline, the Flat Case Library was considered which gives the upper bound of the accuracy. • Twelve different strategies were tested. These combinations are the result of the crossing of 3 Meta-case Selection strategies (VirtualMcSelection, RealMcSelection and VirtualRmaxMcSelection) , two incremental maintenance strategies for the NIAR k-d Tree (IncMaintTree and IncMaintPercTree) and 2 strategies for the Learning of cases (AllCaseLearning and RelCaseLearning): o S1: VirtualMcSelection + IncMaintTree + AllCaseLearning o S2: VirtualMcSelection + IncMaintTree + RelCaseLearning o S3: VirtualMcSelection + IncMaintPercTree + AllCaseLearning o S4: VirtualMcSelection + IncMaintPercTree + RelCaseLearning o S5: RealMcSelection + IncMaintTree + AllCaseLearning o S6: RealMcSelection + IncMaintTree + RelCaseLearning o S7: RealMcSelection + IncMaintPercTree + AllCaseLearning o S8: RealMcSelection + IncMaintPercTree + RelCaseLearning o S9: VirtualRmaxMcSelection + IncMaintTree + AllCaseLearning o S10: VirtualRmaxMcSelection + IncMaintTree + RelCaseLearning o S11: VirtualRmaxMcSelection + IncMaintPercTree + AllCaseLearning o S12: VirtualRmaxMcSelection + IncMaintPercTree + RelCaseLearning • For each database and for each strategy, 10 execution runs were done sampling randomly the cases to get different ordering of the cases. In addition, one more run was done with the original ordering of each database. • For each execution and for each database several statistics were computed: the average accuracy (in percentage); the incremental evolution of the accuracy (accumulated percentage), the average time retrieval (time in µs), the evolution of the incremental time retrieval (accumulated time in µs); The detection of meta-cases-prototypes; the incremental evolution of the number of cases of the whole Case Library; the incremental evolution of the number of cases of each discovered Meta-case/prototype. 149 6.5.2 Experimental Results Regarding the discovering of Meta-cases and protoypes, all the databases have been processed and the different meta-cases (prototypes) were found to correspond accurately with the real hidden class labels. In the table 22, the list of the used databases is shown along with some experimentation details, like the number of classes and instances of each database and the number of meta-cases built (discovered when using different values of the β parameter (ranging from 0.74 to 5.9). Table 22. List of tested databases with details on the discovered Meta-cases DB #Classes #Inst β=4.55 β=0.9 β=3.45 β=0.425 β=5.8 β=5.9 β=5 β=0.74 Pima 2768 Mc1=753 Mc2=15 Ionosphere 2351 Mc1=37 Mc2=314 Iris 3150 Mc1=50 Mc2=68 Mc3=32 Waveform 35000 Mc1=1411 Mc2=686 Mc3=1675 Mc4=1228 Balance 3625 Mc1=298 Mc2=304 Mc3=23 Car 41728 Mc1=616 Mc2=598 Mc3=285 Mc4=229 Glass 7214 Mc1=152 Mc2=17 Mc3=1 Mc4=2 Mc5=11 Mc6=30 Ecoli 8336 Mc1=144 Mc2=10 Mc3=102 Mc4=1 Mc5=21 Mc6=46 Mc7=2 Mc8=10 Abalone 29 4177 Mc1=132 Mc2=38 Mc3=4 Mc4=63 Mc5=173 Mc6=16 Mc7=9 Mc8=26 Mc9=31 Mc10=100 Mc11=101 Mc12=33 Mc13=73 Mc14=85 Mc15=8 Mc16=78 Mc17=72 Mc18=24 Mc19=72 Mc20=228 Mc21=64 Mc22=42 Mc23=43 Mc24=20 Mc25=91 Mc26=82 Mc27=55 Mc28=1 Mc29=139 Mc30=151 Mc31=1 Mc32=136 1 Mc33=761 β=1.1 Number of Metacases built in the dynamic learning of prototypes (DACL) 150 In the following two sections more details about the performance of the proposed methodology when tested on the Iris and Balance database correspondingly, can be found. These databases were selected in order not put all resulting tables for all databases. Anyway, the results on all databases were very equivalent. 6.5.2.1 Evaluating the Accuracy in Iris and Balance databases After running 10 different tests on each database the average precisions values found are reported in the following table (table 23). It is important to mention that the algorithm’s learning process updates its learning base each time a new meta-case appears, which has as a result that the initial precision value is lower and grows as more metacases are identified. Table 23. Mean precision values for Iris and Balance databases #CL #MCs #NCL Precision β iris #CL1=50 3 3 87% 0.425 #CL2=68 #CL3=32 Balance #CL1=298 3 3 68% 5.9 #CL2=304 #CL3=23 151 6.5.2.2 Analyzing the Iris database In figures 25 and 26, the results of the experiments run on the Iris database are presented graphically, with the setting of β = 0.425. These figures show the evolution of the detection of the Meta-Cases, for several random executions. Fig. 25. Iris meta-cases for sequential and random (1, 2, 7, 8, 20) arrival 152 Fig. 26. Iris meta-cases for sequential and random (3, 4, 5, 6, 9) arrival 6.5.2.3 Analyzing the Balance Database In figure 27, 28 and 29, the results of the experiments run on the Balance database are presented graphically, with the setting of β = 0.61. These figures show the evolution of the detection of the Meta-Cases, for several random executions. Fig. 27. Balance meta-cases for sequential and random (1-5) arrival 153 Fig. 28. Balance meta-cases for sequential and random (6, 7, 8) arrival Fig. 29. Balance meta-cases for sequential and random (9, 10) arrival