001 package jcolibri.method.maintenance.algorithms; 002 003 import java.util.Collection; 004 import java.util.LinkedList; 005 import java.util.List; 006 import java.util.ListIterator; 007 008 import jcolibri.cbrcore.CBRCase; 009 import jcolibri.exception.InitializingException; 010 import jcolibri.extensions.classification.ClassificationSolution; 011 import jcolibri.method.maintenance.AbstractCaseBaseEditMethod; 012 import jcolibri.method.maintenance.CaseResult; 013 import jcolibri.method.maintenance.CompetenceModel; 014 import jcolibri.method.maintenance.solvesFunctions.CBESolvesFunction; 015 import jcolibri.method.retrieve.RetrievalResult; 016 import jcolibri.method.retrieve.NNretrieval.NNScoringMethod; 017 import jcolibri.method.retrieve.selection.SelectCases; 018 import jcolibri.method.reuse.classification.KNNClassificationConfig; 019 import jcolibri.method.reuse.classification.KNNClassificationMethod; 020 import jcolibri.method.revise.classification.BasicClassificationOracle; 021 import jcolibri.method.revise.classification.ClassificationOracle; 022 023 /** 024 * Provides the ability to run the BBNR case base editing algorithm 025 * on a case base to eliminate noise. 026 * 027 * @author Lisa Cummins 028 * @author Derek Bridge 029 * 18/05/07 030 */ 031 public class BBNRNoiseReduction extends AbstractCaseBaseEditMethod { 032 033 /** 034 * Simulates the BBNR editing algorithm, returning the cases 035 * that would be deleted by the algorithm. 036 * @param cases The group of cases on which to perform editing. 037 * @param simConfig The similarity configuration for these cases. 038 * @return the list of cases that would be deleted by the 039 * BBNR algorithm. 040 */ 041 @SuppressWarnings("unchecked") 042 public LinkedList<CBRCase> retrieveCasesToDelete(Collection<CBRCase> cases, KNNClassificationConfig simConfig) 043 { /* 044 * Blame-based Noise Reduction (BBNR) Algorithm 045 * T, Training Set 046 * For each c in T 047 * CSet(c) = Coverage Set of c 048 * LSet(c) = Liability Set of c 049 * End-For 050 * 051 * TSet = T sorted in descending order of LSet(c) size 052 * c = first case in TSet 053 * 054 * While |LSet(c)| >0 055 * TSet = TSet - {c} 056 * misClassifiedFlag = false 057 * For each x in CSet(c) 058 * If x cannot be correctly classified by TSet 059 * misClassifiedFlag = true 060 * break 061 * End-If 062 * End-For 063 * If misClassifiedFlag = true 064 * TSet = TSet + {c} 065 * End-If 066 * c = next case in TSet 067 * End-While 068 * 069 * Return TSet 070 */ 071 072 jcolibri.util.ProgressController.init(this.getClass(), "Blame-based Noise Reduction (BBNR)", jcolibri.util.ProgressController.UNKNOWN_STEPS); 073 List<CBRCase> localCases = new LinkedList<CBRCase>(); 074 for(CBRCase c: cases) 075 { localCases.add(c); 076 } 077 078 CompetenceModel sc = new CompetenceModel(); 079 sc.computeCompetenceModel(new CBESolvesFunction(), simConfig, localCases); 080 081 List<CaseResult> caseLiabilitySetSizes = new LinkedList<CaseResult>(); 082 083 for(CBRCase c:localCases) 084 { Collection<CBRCase> currLiabilitySet = null; 085 try 086 { currLiabilitySet = sc.getLiabilitySet(c); 087 } catch (InitializingException e) 088 { e.printStackTrace(); 089 } 090 int liabilitySetSize = 0; 091 092 if(currLiabilitySet != null) 093 { liabilitySetSize = currLiabilitySet.size(); 094 } 095 096 caseLiabilitySetSizes.add(new CaseResult(c, liabilitySetSize)); 097 jcolibri.util.ProgressController.step(this.getClass()); 098 } 099 100 caseLiabilitySetSizes = CaseResult.sortResults(false, caseLiabilitySetSizes); 101 102 LinkedList<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>(); 103 104 for(ListIterator<CaseResult> liabIter = caseLiabilitySetSizes.listIterator(); liabIter.hasNext(); ) 105 { CaseResult highestLiability = liabIter.next(); 106 if(highestLiability.getResult() <= 0) 107 { break; 108 } 109 110 CBRCase removed = highestLiability.getCase(); 111 localCases.remove(removed); 112 113 Collection<CBRCase> covSet = null; 114 try 115 { covSet = sc.getCoverageSet(removed); 116 } catch (InitializingException e) 117 { e.printStackTrace(); 118 } 119 120 boolean caseMisclassified = false; 121 for(CBRCase query: covSet) 122 { Collection<RetrievalResult> knn = NNScoringMethod.evaluateSimilarity(localCases, query, simConfig); 123 knn = SelectCases.selectTopKRR(knn, simConfig.getK()); 124 try 125 { KNNClassificationMethod classifier = ((KNNClassificationConfig)simConfig).getClassificationMethod(); 126 ClassificationSolution predictedSolution = classifier.getPredictedSolution(knn); 127 ClassificationOracle oracle = new BasicClassificationOracle(); 128 129 if(!oracle.isCorrectPrediction(predictedSolution, query)) 130 { caseMisclassified = true; 131 break; 132 } 133 } catch(ClassCastException cce) 134 { org.apache.commons.logging.LogFactory.getLog(BBNRNoiseReduction.class).error(cce); 135 System.exit(0); 136 } 137 } 138 if(caseMisclassified) 139 { localCases.add(removed); 140 } 141 else 142 { allCasesToBeRemoved.add(removed); 143 } 144 jcolibri.util.ProgressController.step(this.getClass()); 145 } 146 jcolibri.util.ProgressController.finish(this.getClass()); 147 return allCasesToBeRemoved; 148 } 149 }