Case-based reasoning

The project that was created for this thesis is a Case Based Reasoning application to be used in high level software design for Siemens' Telecommunications software. Currently, design engineers search for existing subtasks in the software that are similar to subtasks in their new designs by reading documentation and consulting with other engineers. The prototype for Software Design Using Case Based Reasoning (SDUCBR) stores these subtasks in a case library and enables the design engineer to locate relevant subtasks via three different indexing techniques. This thesis addresses knowledge representation and indexing mechanisms appropriate for this application. SDUCBR is domain-dependent. Cases are stored in a relational hierarchy to facilitate analyzing the existing implementation from various perspectives. The indexing mechanisms were designed to provide the software design engineer with the flexibility of describing a problem differently based on the objective, level of granularity, and special characteristics of the subtask.

In today's world, high reliability has become an essential component of almost every software system. However, since the reliability-enhancement activities entail enormous costs, software quality models, based on the metrics collected early in the development life cycle, serve as handy tools for cost-effectively guiding such activities to the software modules that are likely to be faulty. Case-Based Reasoning (CBR) is an attractive technique for software quality modeling. Software Measurement Analysis and Reliability Toolkit (SMART) is a CBR tool customized for metrics-based software quality modeling. Developed for the NASA IV&V Facility, SMART supports three types of software quality models: quantitative quality prediction, classification, and module-order models. It also supports a goal-oriented selection of classification models. An empirical case study of a military command, control, and communication system demonstrates the accuracy and usefulness of SMART, and also serves as a user-guide for the tool.

To achieve high reliability in software-based systems, software metrics-based quality classification models have been explored in the literature. However, the collection of software metrics may be a hard and long process, and some metrics may not be helpful or may be harmful to the classification models, deteriorating the models' accuracies. Hence, methodologies have been developed to select the most significant metrics in order to build accurate and efficient classification models. Case-Based Reasoning is the classification technique used in this thesis. Since it does not provide any metric selection mechanisms, some metric selection techniques were studied. In the context of CBR, this thesis presents a comparative evaluation of metric selection methodologies, for raw and discretized data. Three attribute selection techniques have been studied: Kolmogorov-Smirnov Two-Sample Test, Kruskal-Wallis Test, and Information Gain. These techniques resulted in classification models that are useful for software quality improvement.

Case-based reasoning (CBR) is a powerful reasoning paradigm for many application domains like planning, diagnosis, classification, and decision making. Recognizing solutions of past instances which are similar to the problem in hand is the central concept of CBR. Accordingly, the main research issues in CBR are efficient indexing, retrieval, and evaluation of cases. Generalization of indices has been a major concern as it directly influences the size of casebases and the ability to recognize the right candidate cases. This dissertation work presents a novel indexing scheme--using fuzzy sets to represent case indices and fuzzy aggregation operators to evaluate case matches. The proposed scheme, REFIC (REasoning from Fuzzy Indexed Cases), provides a flexible and transparent scheme to generalize case indices leading to smaller casebases. A hierarchical aggregation of different index matches is suggested for case evaluation. Also, for continuous variable domains, it is proposed to combine the solutions of a small subset of best matching cases as opposed to the conventional approach of selecting and modifying a single best one. These schemes are demonstrated by implementing a case-based navigation planner for autonomous underwater vehicles (AUVs). This navigation planner comprises of an annotated map database, a case-based path planner, and a hybrid fuzzy-CBR based reactive navigation module. The annotated map database provides a general framework for modeling the navigational environment. Annotations attached to objects and geometrical query handling are two main features of this database. Using this system as a spatial casebase, an off-line path planning system for AUV missions is designed. The obstacle avoidance module employs CBR to dynamically select promising directions of movement and to activate a subset of navigational behaviors. This reactive navigation scheme has been found to be very robust under noisy sensor data and complex obstacle distribution patterns.

The performance accuracy of software quality estimation models is influenced by several factors, including the following two important factors: performance of the prediction algorithm and the quality of data. This dissertation addresses these two factors, and consists of two components: (1) a proposed genetic algorithm (GA) based optimization of software quality models for accuracy enhancement, and (2) a proposed partitioning- and rule-based filter (PRBF) for noise detection toward improvement of data quality. We construct a generalized framework of our embedded GA-optimizer, and instantiate the GA-optimizer for three optimization problems in software quality engineering: parameter optimization for case-based reasoning (CBR) models; module rank optimization for module-order modeling (MOM); and structural optimization for our multi-strategy classification modeling approach, denoted RB2CBL. Empirical case studies using software measurement data from real-world software systems were performed for the optimization problems. The GA-optimization approaches improved software quality prediction accuracy, highlighting the practical benefits of using GA for solving optimization problems in software engineering. The proposed noise detection approach, PRBF, was empirically evaluated using data categorized into two classes. Empirical studies on artificially corrupted datasets and datasets with known (natural) noise demonstrated that PRBF can effectively detect both artificial and natural noise. The proposed filter is a stable and robust technique, and always provided optimal or near-optimal noise detection results. In addition, it is applicable on datasets with nominal and numerical attributes, as well as those with missing values. The PRBF technique supports two methods of noise detection: class noise detection and cost-sensitive noise detection. The former is an easy-to-use method and does not need parameter settings, while the latter is suited for applications where each class has a specific misclassification cost. PRBF can also be used iteratively to investigate the two general types of data noise: attribute and class noise.