001    /**
002     * BoundedGreedySelection.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     */
009    package jcolibri.method.retrieve.selection.diversity;
010    
011    import java.util.ArrayList;
012    import java.util.Collection;
013    
014    import jcolibri.cbrcore.CBRCase;
015    import jcolibri.cbrcore.CBRQuery;
016    import jcolibri.method.retrieve.RetrievalResult;
017    import jcolibri.method.retrieve.NNretrieval.NNConfig;
018    import jcolibri.method.retrieve.selection.SelectCases;
019    
020    /**
021     * Tries to reduce the complexity of the greedy selection algorithm first selecting
022     * the best b·k cases according to their similarity to the query and then applies
023     * the greedy selection method to these cases.
024     * <p>See:
025     * <p>
026     * B. Smyth and P. McClave. Similarity vs. diversity. In ICCBR '01: Proceedings 
027     * of the 4th International Conference on Case-Based Reasoning, pages 347-361, 
028     * London, UK, 2001. Springer-Verlag.
029     * @author Juan A. Recio-Garcia
030     * @author Developed at University College Cork (Ireland) in collaboration with Derek Bridge.
031     * @version 1.0
032     *
033     */
034    public class BoundedGreedySelection
035    {   
036        
037        /**
038         * Executes the algorithm
039         * @param cases to retrieve from
040         * @param query to compare
041         * @param simConfig is the knn config that defines the k returned cases
042         * @param bound to create the bounded retrieval set
043         * @param k is the number of cases to select
044         * @return k cases
045         */
046        public static Collection<CBRCase> boundedGreddySelection(Collection<RetrievalResult> cases, CBRQuery query, NNConfig simConfig, int k, int bound)
047        {
048    
049            Collection<CBRCase> C = SelectCases.selectTopK(cases, bound*k);
050            
051            Collection<CBRCase> R = new ArrayList<CBRCase>();
052            for(int i=0; (i<k)&& (!C.isEmpty()); i++)
053            {
054                CBRCase best = GreedySelection.getMoreQuality(query, C, R, simConfig);
055                R.add(best);
056                C.remove(best);
057            }
058            return R;
059        }
060    }