Introduction
-
Efficiency: Time to solve a problem.
-
Competence: Problem count that can be solved.
-
Quality: Accuracy of the proposed solution.
-
Continuous timing.
-
Conditional timing.
-
Ad hoc timing.
-
Case addition strategy.
-
Case deletion strategy.
-
In case addition methodologies with continuous or ad-hoc timing, cases can be added only in the case-base. There is no criteria for deleting cases from the case-base as this could lead to retrieval time bottlenecks with the ongoing increase in the case-base cardinality.
-
In addition and deletion policies with conditional timing, the whole process of maintenance tends to recur quite often due to the blind addition of completely resolved case. This results in performance bottlenecks.
-
The proposed approach is capable to control the case-base cardinality at a user preferred threshold.
-
It acquires knowledge and preserves the case-base competence using online and offline case maintenance mechanisms.
-
The resultant case-base from the proposed approach is more compact and equally competent as compared to the the existing benchmarks. Its average problem solving time offers up to 65% reduction as compared to that of the standard CBR cycle without compromising on its performance.
-
Over time, it strengthens the existing stronger cases through updating their utility and periodically removes the weaker cases.
Case based reasoning (CBR)
CBR cycle
Retrieve phase
Distance function | Formula |
---|---|
Euclidian distance |
\(dis(i,j) = \sqrt{\sum \limits _{k=1}^{m}(w_k(p_{ik} - p_{jk}))^2}\)
|
Manhattan distance |
\(dis(i,j) = \sum \limits _{k=1}^{m}w_k|p_{ik} - p_{jk}|\)
|
Canberra distance |
\(dis(i,j)= \sum \limits _{k=1}^{m} w_k \frac{|p_{ik} - p_{jk}|}{|p_{ik}|+|p_{jk}|}\)
|
Squared chord distance |
\(dis(i,j) = \sum \limits _{k=1}^{m}w_k\left(\sqrt{p_{ik}} - \sqrt{p_{jk}}\right)^2\)
|
Minkowski distance |
\(dis(i,j)= \left[\sum \limits _{k=1}^{m}w_k |p_{ik} - p_{jk}|^q\right] ^{\frac{1}{q}}\)
|
Reuse and revise phases
Retain phase
Case-base maintenance (CBM)
Quality
Competence
Efficiency
Related work
-
The existing approaches either focus on case addition or case deletion.
-
In case addition policies, only new completely resolved case is added which looks important according to the existing case-base. However, the importance of that new case may degrade with the addition of new cases.
-
These addition policies are unable to delete cases amplifying the gradual increase in the case-base cardinality which will eventually degrade the performance of a CBR system.
-
On the other hand, the case deletion techniques encourage blind addition of new cases and after reaching a swamping limit, unimportant cases are deleted from the case-base.
-
Due to the blind retention of new cases in deletion approaches, the case-base cardinality grows swiftly resulting in frequent need for complex maintenance. It results in degradation of the CBR process.
Proposed hybrid CBM approach
-
Auxiliary cases By the removal of auxiliary cases, the competence does not get effected. If the coverage provided by a case is absorbed by one of its reachable cases then that case is an auxiliary case. For instance in Fig. 5, cases a, b and c are auxiliary cases, since the coverage they provide is subsumed by their reachable cases such as case y.
-
Pivotal cases If a case is only reachable by itself, then that case is a pivotal case. The competence of a system degrades by the deletion of a pivotal case. In Fig. 5, case x is a pivotal case since it is reachable by only itself.
-
Spanning cases The cases with an overlapping coverage space with other cases within the problem space are categorised as spanning cases. In Fig. 5, case y is a spanning case as it links together the problem space between case x and cases a, b and c.
-
Support cases The cases which exist in the form of groups and act as spanning cases within the group are known as support cases. In Fig. 5, cases 1, 2 and 3 are support cases and as a whole they represent a support group. The removal of a member of the support category does not harm competence at all. However, deletion of a whole category is as deletion of a pivotal case.
Case study, experimental settings and initial results
Case study: Simulated model of autonomic forest fire application
Distributions | Case-base | Problem space |
---|---|---|
Distribution 1 | 3000 | 7000 |
Distribution 2 | 5000 | 5000 |
Distribution 3 | 7000 | 3000 |
Optimal nearest neighbors
Optimal value of NN’s for simple CBR cycle
Optimal value of NN’s for RC-CNN
Training | Testing | Optimal NN size | Accuracy (%) | Precision (%) | Recall (%) |
---|---|---|---|---|---|
3000 | 7000 | 11 | 95.9 | 97.8 | 87.7 |
5000 | 5000 | 13 | 96.2 | 98.2 | 87.8 |
7000 | 3000 | 12 | 96.3 | 98 | 88.5 |
Training | Testing | Optimal NN | Accuracy (%) | Precision (%) | Recall (%) |
---|---|---|---|---|---|
3000 | 7000 | 8 | 95.2 | 97.3 | 85 |
5000 | 5000 | 13 | 95.8 | 97.6 | 86 |
7000 | 3000 | 8 | 95.6 | 97 | 86.3 |
Optimal value of NN’s for footprint deletion
Training | Testing | Optimal NN’s | Accuracy (%) | Precision (%) | Recall (%) |
---|---|---|---|---|---|
3000 | 7000 | 10 | 95.4 | 97.9 | 85.9 |
5000 | 5000 | 10 | 96.1 | 98.5 | 87.5 |
7000 | 3000 | 12 | 96.2 | 97.8 | 88.3 |
Optimal value of NN’s for the proposed hybrid approach
Training | Testing | Optimal NN’s | Accuracy (%) | Precision (%) | Recall (%) |
---|---|---|---|---|---|
3000 | 7000 | 7 | 95.6 | 97.2 | 87.2 |
5000 | 5000 | 11 | 95.8 | 97.8 | 86.7 |
7000 | 3000 | 9 | 96 | 97.5 | 88.1 |
Benchmarking with state-of-the-art approaches
Experiment 1: Comparison of theoretical complexities
Technique | Activating time | Online complexity | Offline complexity |
---|---|---|---|
CBR cycle | Continuous | O(n) | N/A |
RC-CNN | Conditional | N/A |
\(O(n^2)\)
|
FPD | Conditional | N/A |
\(O(n^2)\)
|
Hybrid | Continuous + conditional |
\(O(n^2)\)
|
\(O(n^2)\)
|