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    }