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}