001/**
002 * GreedySelection.java
003 * jCOLIBRI2 framework. 
004 * @author Juan A. Recio-Garc�a.
005 * GAIA - Group for Artificial Intelligence Applications
006 * http://gaia.fdi.ucm.es
007 * 05/11/2007
008 */
009package es.ucm.fdi.gaia.jcolibri.method.retrieve.selection.diversity;
010
011import java.util.ArrayList;
012import java.util.Collection;
013import java.util.List;
014
015import es.ucm.fdi.gaia.jcolibri.cbrcore.CBRCase;
016import es.ucm.fdi.gaia.jcolibri.cbrcore.CBRQuery;
017import es.ucm.fdi.gaia.jcolibri.method.retrieve.RetrievalResult;
018import es.ucm.fdi.gaia.jcolibri.method.retrieve.NNretrieval.NNConfig;
019import es.ucm.fdi.gaia.jcolibri.method.retrieve.NNretrieval.NNScoringMethod;
020import es.ucm.fdi.gaia.jcolibri.method.retrieve.selection.SelectCases;
021
022/**
023 * This method incrementally builds a retrieval set, R. During each step the
024 * remaining cases are ordered according to their quality with the highest 
025 * quality case added to R. 
026 * <br>
027 * The quality metric combines diversity and similarity. The quality of a case c 
028 * is proportional to the similarity between c and the query, and to the diversity
029 * of c relative to those cases so far selected in R.
030 * <br>
031 * This algorithm is very expensive. It should be applied to small case bases. 
032 * <p>See:
033 * <p>
034 * B. Smyth and P. McClave. Similarity vs. diversity. In ICCBR '01: Proceedings 
035 * of the 4th International Conference on Case-Based Reasoning, pages 347-361, 
036 * London, UK, 2001. Springer-Verlag.
037 * 
038 * 
039 * @author Juan A. Recio-Garcia
040 * @author Developed at University College Cork (Ireland) in collaboration with Derek Bridge.
041 * @version 1.0
042 *
043 */
044public class GreedySelection {
045
046    /******************************************************************************/
047    /**                           STATIC METHODS                                 **/
048    /******************************************************************************/   
049    
050    
051    /**
052     * Executes the greedy selection algorithm
053     * @param cases to select from
054     * @param query to compare
055     * @param simConfig is the knn similarity configuration. Its k determines the number of returned cases 
056     * @return k cases (k is defined in simConfig). 
057     */
058    public static List<CBRCase> greedySelection(Collection<RetrievalResult> cases, CBRQuery query, NNConfig simConfig, int k)  {
059
060        Collection<CBRCase> C = SelectCases.selectAll(cases);
061                List<CBRCase> R = new ArrayList<>();
062
063                for(int i=0; i<k; i++) {
064                CBRCase best = getMoreQuality(query, C, R, simConfig);
065                R.add(best);
066                C.remove(best);
067                }
068
069                return R;
070    }
071    
072    /**
073     * Returns the case with more quality.
074     * @param query to compare
075     * @param cases to compare
076     * @param R is the set of previous selected cases
077     * @param simConfig is the knn similarity config
078     * @return the case with more quality
079     */
080    public static CBRCase getMoreQuality(CBRQuery query, Collection<CBRCase> cases, Collection<CBRCase> R, NNConfig simConfig) {
081
082        // TODO - Testearlo bien
083
084                List<RetrievalResult> nn = NNScoringMethod.evaluateSimilarity(cases, query, simConfig);
085                double maxQuality = -Double.MAX_VALUE;
086
087                CBRCase best = null;
088
089                for(RetrievalResult rr: nn)
090                {
091                        double quality = rr.getEval() * relDiversity(rr.get_case(), R, simConfig);
092                        if(quality > maxQuality)
093                        {
094                        maxQuality = quality;
095                        best = rr.get_case();
096                        }
097                }
098                return best;
099    }
100    
101    public static double relDiversity(CBRCase c, Collection<CBRCase> R, NNConfig simConfig)
102    {
103        if(R.isEmpty())
104            return 1;
105        double sum = 0;
106        for(CBRCase _case : R)
107        {
108            List<CBRCase> aux = new ArrayList<CBRCase>();
109            aux.add(_case);
110            CBRQuery query = new CBRQuery();
111            query.setDescription(c.getDescription());
112            double sim = NNScoringMethod.evaluateSimilarity(aux, query, simConfig).iterator().next().getEval();
113            sum += sim;
114        }
115        sum = sum/(double)R.size();
116        
117        return sum;
118    }
119}