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}