001 package jcolibri.method.maintenance; 002 003 import java.util.Collection; 004 import java.util.HashMap; 005 import java.util.Iterator; 006 import java.util.LinkedList; 007 import java.util.List; 008 009 import jcolibri.cbrcore.CBRCase; 010 import jcolibri.method.retrieve.KNNretrieval.KNNConfig; 011 012 /** 013 * Implements the CRR Maintenance Algorithm to remove 014 * redundancy from the case base 015 * 016 * @author Lisa Cummins 017 */ 018 public class CRRAlgorithm extends MaintenanceAlgorithm { 019 020 /** 021 * Runs the CRR maintenance algorithm, returning the cases 022 * deleted by the algorithm 023 * @param cases The group of cases on which to perform maintenance 024 * @param simConfig The KNNConfig for these cases 025 * @return the list of cases deleted by the algorithm 026 */ 027 public LinkedList<CBRCase> runMaintenance(Collection<CBRCase> cases, KNNConfig simConfig) 028 { /* 029 * Conservative Redundancy Removal(CRR) Algorithm: 030 * T, Training Set 031 * 032 * Build case-base competence model 033 * For each c in T 034 * CSet(c) = Coverage Set of c 035 * End-For 036 * 037 * Remove redundant cases from case-base 038 * ESet = {}, (Edited Set) 039 * TSet = T sorted in ascending order of CSet(c) size 040 * c = first case in TSet 041 * 042 * While TSet = {} 043 * ESet = ESet + {c} 044 * TSet = TSet – CSet(c) 045 * c = next case in TSet 046 * End-While 047 * 048 * Return TSet 049 */ 050 List<CBRCase> localCases = new LinkedList<CBRCase>(); 051 for(CBRCase c: cases) 052 { localCases.add(c); 053 } 054 055 SetCalculator sc = new SetCalculator(); 056 HashMap<String, HashMap<CBRCase, LinkedList<CBRCase>>> sets = sc.calculateCRRSets(cases, simConfig); 057 HashMap<CBRCase, LinkedList<CBRCase>> coverageSets = sets.get(SetCalculator.COVERAGE_SET); 058 059 LinkedList<CBRCase> tSet = new LinkedList<CBRCase>(); 060 061 LinkedList<CBRCase> sortedCases = new LinkedList<CBRCase>(); 062 LinkedList<Integer> coverageSetSizes = new LinkedList<Integer>(); 063 for(CBRCase c: localCases) 064 { tSet.add(c); 065 066 LinkedList<CBRCase> currCoverageSet = coverageSets.get(c); 067 if(sortedCases.size() == 0) 068 { sortedCases.add(c); 069 coverageSetSizes.add(currCoverageSet.size()); 070 } 071 else 072 { int i; 073 for(i=0; i < sortedCases.size() && coverageSetSizes.get(i) < currCoverageSet.size(); i++); 074 if(i==0) 075 { sortedCases.addFirst(c); 076 coverageSetSizes.addFirst(currCoverageSet.size()); 077 } 078 else if(i==sortedCases.size()) 079 { sortedCases.addLast(c); 080 coverageSetSizes.addLast(currCoverageSet.size()); 081 } 082 else 083 { sortedCases.add(i-1, c); 084 coverageSetSizes.add(i-1, currCoverageSet.size()); 085 } 086 } 087 } 088 089 LinkedList<CBRCase> newCases = new LinkedList<CBRCase>(); 090 while(sortedCases.size() > 0) 091 { CBRCase c = sortedCases.get(0); 092 newCases.add(c); 093 sortedCases.remove(c); 094 LinkedList<CBRCase> cCoverageSet = coverageSets.get(c); 095 for(Iterator<CBRCase> cIter = cCoverageSet.iterator(); cIter.hasNext(); ) 096 { CBRCase removed = cIter.next(); 097 sortedCases.remove(removed); 098 } 099 } 100 101 LinkedList<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>(); 102 for(CBRCase c: localCases) 103 { if(!newCases.contains(c)) 104 allCasesToBeRemoved.add(c); 105 } 106 107 return allCasesToBeRemoved; 108 } 109 }