001 package jcolibri.method.maintenance; 002 003 import java.util.Collection; 004 import java.util.HashMap; 005 import java.util.LinkedList; 006 import java.util.List; 007 008 import jcolibri.cbrcore.CBRCase; 009 import jcolibri.method.retrieve.KNNretrieval.KNNConfig; 010 011 /** 012 * Implements the BBNR Maintenance Algorithm to remove 013 * noise from the case base 014 * 015 * @author Lisa Cummins 016 */ 017 public class BBNRAlgorithm extends MaintenanceAlgorithm { 018 019 /** 020 * Runs the BBNR maintenance algorithm, returning the cases 021 * deleted by the algorithm 022 * @param cases The group of cases on which to perform maintenance 023 * @param simConfig The KNNConfig for these cases 024 * @return the list of cases deleted by the algorithm 025 */ 026 public LinkedList<CBRCase> runMaintenance(Collection<CBRCase> cases, KNNConfig simConfig) 027 { /* 028 * Blame-based Noise Reduction (BBNR) Algorithm 029 * T, Training Set 030 * For each c in T 031 * CSet(c) = Coverage Set of c 032 * LSet(c) = Liability Set of c 033 * End-For 034 * 035 * TSet = T sorted in descending order of LSet(c) size 036 * c = first case in TSet 037 * 038 * While |LSet(c)| >0 039 * TSet = TSet - {c} 040 * misClassifiedFlag = false 041 * For each x in CSet(c) 042 * If x cannot be correctly classified by TSet 043 * misClassifiedFlag = true 044 * break 045 * End-If 046 * End-For 047 * If misClassifiedFlag = true 048 * TSet = TSet + {c} 049 * End-If 050 * c = next case in TSet 051 * End-While 052 * 053 * Return TSet 054 */ 055 List<CBRCase> localCases = new LinkedList<CBRCase>(); 056 for(CBRCase c: cases) 057 { localCases.add(c); 058 } 059 060 SetCalculator sc = new SetCalculator(); 061 HashMap<String, HashMap<CBRCase, LinkedList<CBRCase>>> sets = sc.calculateCRRSets(cases, simConfig); 062 HashMap<CBRCase, LinkedList<CBRCase>> coverageSets = sets.get(SetCalculator.COVERAGE_SET); 063 HashMap<CBRCase, LinkedList<CBRCase>> liabilitySets = sets.get(SetCalculator.LIABILITY_SET); 064 065 LinkedList<CBRCase> tSet = new LinkedList<CBRCase>(); 066 067 LinkedList<CBRCase> sortedCases = new LinkedList<CBRCase>(); 068 LinkedList<Integer> liabilitySetSizes = new LinkedList<Integer>(); 069 for(CBRCase c:localCases) 070 { tSet.add(c); 071 LinkedList<CBRCase> currLiabilitySet = liabilitySets.get(c); 072 int liabilitySetSize = 0; 073 074 if(currLiabilitySet != null) { 075 liabilitySetSize = currLiabilitySet.size(); 076 } 077 if(sortedCases.size() == 0) 078 { sortedCases.add(c); 079 liabilitySetSizes.add(liabilitySetSize); 080 } 081 else 082 { int i; 083 for(i=0; i < liabilitySetSizes.size() && liabilitySetSizes.get(i) > liabilitySetSize; i++); 084 sortedCases.add(i, c); 085 liabilitySetSizes.add(i, liabilitySetSize); 086 } 087 } 088 089 int k = 3; 090 VotesCalculator vc = new VotesCalculator(); 091 LinkedList<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>(); 092 for(int i=0; i<sortedCases.size() && liabilitySetSizes.get(i) > 0; i++) 093 { CBRCase removed = sortedCases.get(i); 094 tSet.remove(removed); 095 LinkedList<CBRCase> covSet = coverageSets.get(removed); 096 boolean caseMisclassified = false; 097 for(CBRCase query: covSet) 098 { LinkedList<CBRCase> retrieved = 099 vc.getkRetrievedCasesForQuery(tSet, query, simConfig, k); 100 String predResult = vc.getPredictedClass(retrieved); 101 String actualResult = query.getSolution().toString(); 102 if(!predResult.equals(actualResult)) 103 { caseMisclassified = true; 104 break; 105 } 106 } 107 if(caseMisclassified) 108 { tSet.add(removed); 109 } 110 else 111 { allCasesToBeRemoved.add(removed); 112 } 113 } 114 115 return allCasesToBeRemoved; 116 } 117 }