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