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 }