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