Many approaches to case based reasoning (CBR) exploit feature weight setting algorithms to reduce the sensitivity to distance functions. In this paper, we demonstrate that optimal feature weight setting in a special kind of CBR problems can be formalised as linear programming problems. Therefore, the optimal weight settings can be calculated in polynomial time instead of searching in exponential weight space using heuristics to get sub-optimal settings. We also demonstrate that our approach can be used to solve classification problems.
Case based reasoning (CBR) is a multi-disciplinary subject that focuses on the reuse of experiences [2]. Typically, a CBR approach retains a fairly large number of previous experiences (which are usually called cases) in a database (which is usually called the case base). When a new problem occurs, it will be represented as a new case and compared to the cases in the case base. Thus, the cases similar to the new cases will be used to suggest to users a solution for the new problem. Usually, the solved new case will also be added into the case base. The underlying assumption for CBR is that similar cases will have similar solutions. Many CBR approaches have been reported for solving problems in various domains, such as planning [11], design [14], software engineering [4] and [42], image processing [21] and [40], and diagnosis [8], [31] and [49].
Cases can be represented in various forms. In this paper, we focus on the well-structured form. Other forms of case representation include directed acyclic graphs [30] and examplars [9] and [41]. A well-structured case is defined as a vector of features: x={x1,x2,…xq}, where q is the number of features. Therefore, an algorithm such as k-nearest neighbour (k-NN) [18] and [22] can be exploited through calculating the distance between case x={x1,x2,…xq} and case y={y1,y2,…yq} using a distance function. However, a universal distance function may not be suitable for solving problems in different domains. One solution is to investigate multiple distance functions [55] and [56]. The other is to parameterise the distance function with feature weights [3] and [53]. For a feature weighting approach, a main research topic is to determine feature weight settings (see e.g. [16], [32], [34], [48] and [54]).
In particular, CBR approaches can also be applied to diagnosis problems. In a diagnosis problem, the solution to a case is a set of faults, which is usually easy to be compared with the set of faults of another case. For two cases whose solutions have been found, the similarity in each feature, the calculated overall similarity, and the real similarity between the two sets of faults can be obtained. However, when diagnosing a new case, only the similarity in each feature and the calculated overall similarity between the new case and an existing case can be obtained. The calculated overall similarity is used to predict the fault similarity.
Linear programming (LP) [17] has been a rapidly developing mathematical discipline since it started in 1947. Theoretically, LP problems have been proved to be polynomial time solvable [26] and [27]. Practically, the simplex algorithm [17] and its derivatives and the interior point algorithm [26] and its derivatives are fast enough to be used in real world applications. Therefore, many realistic problems that have been expressed as LP problems have been well solved, and there is also a lot of commercial or free software for LP problems available from vendors and/or on the Internet.
In this paper, we demonstrate that optimal feature weight setting in a general form of case based diagnosis can be formalised as LP problems. Therefore, available LP software can be used to solve case based diagnosis problems.
The organisation of the remainder of the paper is as follows. Section 2 gives a brief overview of LP problems, and presents a general form of case based diagnosis. Section 3 demonstrates that calculation of optimal initial weights can be formalised as an LP problem. Section 4 demonstrates that calculation of new case weights can also be formalised as an LP problem. Section 5 provides some preliminary empirical results. Section 6 further discusses some related works of our approach. Section 7 concludes this paper.
In this paper, we have proved that the two kinds of optimal weight setting in a general form of case based diagnosis can be formalised as LP problems. As LP problems are polynomial time solvable, optimal weight settings can be calculated in polynomial time rather than searching the exponential weight space using heuristics to get sub-optimal settings. Optimal weight settings calculated in our method are in the sense of minimising predictive errors, which is quite in accordance with common sense. Our preliminary empirical results also show that our approach can not only calculate the theoretically optimal feature setting, but also be used to solve real world problems quite accurately.
We demonstrate that we have solved the optimal feature weight setting problem in a general form of case based diagnosis, and therefore, some alternative approaches focusing on various distance functions and case weight setting can actually be represented by our approach. On the basis of our approach, the global weighting can be treated as a simplification of the local weighting, and therefore, the two approaches can be directly compared with each other on the same ground. We also demonstrate that classification problems can be viewed as a subset of case based diagnosis problems, and therefore, our approach is also applicable to classification.
Future works include further testing the performance of our approach using more real world data and investigating LP algorithms that are particularly efficient for weight setting in case based diagnosis.
