001 /**
002 * Copyright (C) 2007-2011, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019
020 package org.dllearner.learningproblems;
021
022 import java.util.Map;
023 import java.util.SortedSet;
024 import java.util.TreeMap;
025
026 import org.dllearner.core.owl.Description;
027 import org.dllearner.core.owl.Individual;
028 import org.dllearner.core.owl.Intersection;
029 import org.dllearner.core.owl.Union;
030 import org.dllearner.utilities.Helper;
031 import org.dllearner.utilities.datastructures.SortedSetTuple;
032 import org.dllearner.utilities.owl.ConceptComparator;
033
034 /**
035 * Caches results of previous concept evaluation to speed up
036 * further evaluations. Implements a fast evaluation approach,
037 * which tries to infer the covered examples of a given concept
038 * from previous results.
039 *
040 * TODO Under construction.
041 * @author Jens Lehmann
042 *
043 */
044 public class EvaluationCache {
045
046 // maps a concept to a list of individuals it covers
047 private Map<Description,SortedSet<Individual>> cache;
048 private boolean checkForEqualConcepts = false;
049
050 // concept comparator for concept indexing
051 // (so only logarithmic time complexity is needed to access a cached object)
052 private ConceptComparator conceptComparator;
053
054 private SortedSet<Individual> examples;
055
056 public EvaluationCache(SortedSet<Individual> examples) {
057 this.examples = examples;
058 conceptComparator = new ConceptComparator();
059 cache = new TreeMap<Description,SortedSet<Individual>>(conceptComparator);
060 }
061
062 public void put(Description concept, SortedSet<Individual> individuals) {
063 cache.put(concept, individuals);
064 }
065
066 /**
067 * Determines which examples are instances of a concept.
068 * @param concept
069 * @return A tuple of two sets, where the first element is the
070 * set of individuals belonging to the class and the second element
071 * is the set of individuals not belonging to the class. For all
072 * elements, which are in neither of the sets, the cache cannot
073 * safely determine whether they are concept instances or not.
074 */
075 public SortedSetTuple<Individual> infer(Description concept) {
076 if(checkForEqualConcepts) {
077 SortedSet<Individual> pos = cache.get(concept);
078 SortedSet<Individual> neg = Helper.difference(examples, pos);
079 return new SortedSetTuple<Individual>(pos,neg);
080 } else {
081 // for a negation NOT C we can only say which concepts are not in it
082 // (those in C), but we cannot say which ones are in NOT C
083
084 // for a conjunction we know that the intersection of instances
085 // of all children belongs to the concept
086 if(concept instanceof Intersection) {
087 handleMultiConjunction((Intersection)concept);
088 // disjunctions are similar to conjunctions but we use union here;
089 // note that there can be instances which are neither in a concept
090 // C nor in a concept D, but in (C OR D)
091 } else if(concept instanceof Union) {
092 SortedSet<Individual> ret = cache.get(concept.getChild(0));
093 for(int i=1; i<concept.getChildren().size(); i++) {
094 ret = Helper.union(ret, cache.get(concept.getChild(i)));
095 }
096 // in all other cases we cannot infer anything, so we return an
097 // empty tuple
098 } else {
099 return new SortedSetTuple<Individual>();
100 }
101 }
102
103 return null;
104 }
105
106 private SortedSetTuple<Individual> handleMultiConjunction(Intersection mc) {
107 SortedSet<Individual> pos = cache.get(mc.getChild(0));
108 for(int i=1; i<mc.getChildren().size(); i++) {
109 pos = Helper.intersection(pos, cache.get(mc.getChild(i)));
110 }
111 // TODO: handle the case that some children may not be in cache
112 return null;
113 }
114 }