001package es.ucm.fdi.gaia.jcolibri.method.maintenance.algorithms; 002 003import java.util.Collection; 004import java.util.Iterator; 005import java.util.LinkedList; 006import java.util.List; 007import java.util.ListIterator; 008 009 010import org.apache.commons.logging.LogFactory; 011 012import es.ucm.fdi.gaia.jcolibri.cbrcore.CBRCase; 013import es.ucm.fdi.gaia.jcolibri.exception.InitializingException; 014import es.ucm.fdi.gaia.jcolibri.method.maintenance.AbstractCaseBaseEditMethod; 015import es.ucm.fdi.gaia.jcolibri.method.maintenance.CaseResult; 016import es.ucm.fdi.gaia.jcolibri.method.maintenance.CompetenceModel; 017import es.ucm.fdi.gaia.jcolibri.method.maintenance.solvesFunctions.CBESolvesFunction; 018import es.ucm.fdi.gaia.jcolibri.method.reuse.classification.KNNClassificationConfig; 019import es.ucm.fdi.gaia.jcolibri.util.ProgressController; 020 021/** 022 * Provides the ability to run the CRR case base editing algorithm 023 * on a case base to eliminate redundancy. 024 * 025 * @author Lisa Cummins 026 * @author Derek Bridge 027 * 18/05/07 028 */ 029public class CRRRedundancyRemoval extends AbstractCaseBaseEditMethod { 030 031 /** 032 * Simulates the CRR case base editing algorithm, returning the cases 033 * that would be deleted by the algorithm. 034 * @param cases The group of cases on which to perform editing. 035 * @param simConfig The similarity configuration for these cases. 036 * @return the list of cases that would be deleted by the 037 * CRR algorithm. 038 */ 039 public List<CBRCase> retrieveCasesToDelete(Collection<CBRCase> cases, KNNClassificationConfig simConfig) 040 { /* 041 * Conservative Redundancy Removal(CRR) Algorithm: 042 * T, Training Set 043 * 044 * Build case-base competence model 045 * For each c in T 046 * CSet(c) = Coverage Set of c 047 * End-For 048 * 049 * Remove redundant cases from case-base 050 * ESet = {}, (Edited Set) 051 * TSet = T sorted in ascending order of CSet(c) size 052 * c = first case in TSet 053 * 054 * While TSet != {} 055 * ESet = ESet + {c} 056 * TSet = TSet � CSet(c) 057 * c = next case in TSet 058 * End-While 059 * 060 * Return TSet 061 */ 062 ProgressController.init(this.getClass(), "Conservative Redundancy Removal(CRR)", ProgressController.UNKNOWN_STEPS); 063 List<CBRCase> localCases = new LinkedList<CBRCase>(); 064 for(CBRCase c: cases) 065 { localCases.add(c); 066 } 067 068 CompetenceModel sc = new CompetenceModel(); 069 sc.computeCompetenceModel(new CBESolvesFunction(), simConfig, localCases); 070 //Map<CBRCase, Collection<CBRCase>> coverageSets = sc.getCoverageSets(); 071 072 LinkedList<CBRCase> tSet = new LinkedList<CBRCase>(); 073 074 List<CaseResult> caseCoverageSetSizes = new LinkedList<CaseResult>(); 075 for(CBRCase c: localCases) 076 { tSet.add(c); 077 Collection<CBRCase> currCoverageSet = null; 078 try 079 { currCoverageSet = sc.getCoverageSet(c); 080 caseCoverageSetSizes.add(new CaseResult(c, currCoverageSet.size())); 081 } catch (InitializingException e) 082 { LogFactory.getLog(this.getClass()).error(e); 083 } 084 ProgressController.step(this.getClass()); 085 } 086 087 caseCoverageSetSizes = CaseResult.sortResults(true, caseCoverageSetSizes); 088 List<CBRCase> newCases = new LinkedList<CBRCase>(); 089 List<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>(); 090 091 while(caseCoverageSetSizes.size() > 0) 092 { List<CBRCase> removeThese = new LinkedList<CBRCase>(); 093 CBRCase c = caseCoverageSetSizes.get(0).getCase(); 094 newCases.add(c); 095 try 096 { Collection<CBRCase> cCoverageSet = sc.getCoverageSet(c); 097 for(Iterator<CBRCase> cIter = cCoverageSet.iterator(); cIter.hasNext(); ) 098 { CBRCase removed = cIter.next(); 099 if(!removed.equals(c) && !allCasesToBeRemoved.contains(removed)) 100 { allCasesToBeRemoved.add(removed); 101 } 102 removeThese.add(removed); 103 } 104 ListIterator<CaseResult> iter = null; 105 for(iter = caseCoverageSetSizes.listIterator(); iter.hasNext() && removeThese.size() > 0; ) 106 { CaseResult cResult = iter.next(); 107 if(removeThese.contains(cResult.getCase())) 108 { iter.remove(); 109 removeThese.remove(cResult.getCase()); 110 } 111 } 112 caseCoverageSetSizes = CaseResult.sortResults(true, caseCoverageSetSizes); 113 } catch (InitializingException e) 114 { LogFactory.getLog(this.getClass()).error(e); 115 } 116 ProgressController.step(this.getClass()); 117 } 118 ProgressController.finish(this.getClass()); 119 return allCasesToBeRemoved; 120 } 121}