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.refinementoperators;
021
022 import java.util.HashSet;
023 import java.util.Iterator;
024 import java.util.LinkedList;
025 import java.util.List;
026 import java.util.Set;
027 import java.util.TreeSet;
028
029 import org.dllearner.core.AbstractReasonerComponent;
030 import org.dllearner.core.owl.ObjectAllRestriction;
031 import org.dllearner.core.owl.NamedClass;
032 import org.dllearner.core.owl.Nothing;
033 import org.dllearner.core.owl.Description;
034 import org.dllearner.core.owl.ObjectSomeRestriction;
035 import org.dllearner.core.owl.Intersection;
036 import org.dllearner.core.owl.Union;
037 import org.dllearner.core.owl.Negation;
038 import org.dllearner.core.owl.ObjectProperty;
039 import org.dllearner.core.owl.ObjectQuantorRestriction;
040 import org.dllearner.core.owl.Thing;
041 import org.dllearner.learningproblems.PosNegLP;
042 import org.dllearner.utilities.owl.ConceptComparator;
043
044 /**
045 * Operatoren Psi-Down und Psi-Up müssen noch so umgeschrieben werden, dass sie
046 * nur konsistente Konzepte (mit korrekten parent-Links) enthalten. Dazu müssen
047 * alle verwendeten atomaren Konzepte geklont werden.
048 *
049 * AuÃerdem erscheint es ratsam weitere konzeptverkürzende MaÃnahmen einzuführen,
050 * z.B. EXISTS r.A => BOTTOM für down bzw. TOP für up
051 * => Konzepte erreichen etwa eine Länge von 20
052 *
053 * @author jl
054 *
055 */
056 public class PsiDown extends RefinementOperatorAdapter {
057
058 ConceptComparator conceptComparator = new ConceptComparator();
059
060 PosNegLP learningProblem;
061 AbstractReasonerComponent reasoningService;
062
063 private TreeSet<Description> topSet;
064
065 public PsiDown(PosNegLP learningProblem, AbstractReasonerComponent reasoningService) {
066 this.learningProblem = learningProblem;
067 this.reasoningService = reasoningService;
068
069 // Top-Menge erstellen
070 createTopSet();
071 }
072
073 private void createTopSet() {
074 topSet = new TreeSet<Description>(conceptComparator);
075
076 // TOP OR TOP => Was soll mit Refinements passieren, die immer improper sind?
077 Union md = new Union();
078 md.addChild(new Thing());
079 md.addChild(new Thing());
080 topSet.add(md);
081
082 // allgemeinste Konzepte
083 topSet.addAll(reasoningService.getSubClasses(new Thing()));
084
085 // negierte speziellste Konzepte
086 Set<Description> tmp = reasoningService.getSuperClasses(new Nothing());
087 for(Description c : tmp)
088 topSet.add(new Negation(c));
089
090 // EXISTS r.TOP und ALL r.TOP für alle r
091 for(ObjectProperty r : reasoningService.getObjectProperties()) {
092 topSet.add(new ObjectAllRestriction(r, new Thing()));
093 topSet.add(new ObjectSomeRestriction(r, new Thing()));
094 }
095 }
096
097 @Override
098 @SuppressWarnings("unchecked")
099 public Set<Description> refine(Description concept) {
100
101 Set<Description> refinements = new HashSet<Description>();
102 Set<Description> tmp = new HashSet<Description>();
103
104 if (concept instanceof Thing) {
105 return (Set<Description>) topSet.clone();
106 } else if (concept instanceof Nothing) {
107 // return new TreeSet<Concept>(conceptComparator);
108 return new HashSet<Description>();
109 } else if (concept instanceof NamedClass) {
110 // beachte: die Funktion gibt bereits nur nicht-äquivalente Konzepte zurück
111 // beachte weiter: die zurückgegebenen Instanzen dürfen nicht verändert werden,
112 // da beim Caching der Subsumptionhierarchie (momentan) keine Kopien gemacht werden
113 // Bottom wird hier ggf. automatisch mit zurückgegeben
114 refinements.addAll(reasoningService.getSubClasses(concept));
115 // negiertes atomares Konzept
116 } else if (concept instanceof Negation && concept.getChild(0) instanceof NamedClass) {
117 tmp.addAll(reasoningService.getSuperClasses(concept.getChild(0)));
118
119 // Top rausschmeissen
120 boolean containsTop = false;
121 Iterator<Description> it = tmp.iterator();
122 while(it.hasNext()) {
123 Description c = it.next();
124 if(c instanceof Thing) {
125 it.remove();
126 containsTop = true;
127 }
128 }
129 if(containsTop)
130 refinements.add(new Nothing());
131
132 for(Description c : tmp) {
133 refinements.add(new Negation(c));
134 }
135 } else if (concept instanceof Intersection) {
136 // eines der Elemente kann verfeinert werden
137 for(Description child : concept.getChildren()) {
138
139 // Refinement für das Kind ausführen
140 tmp = refine(child);
141
142 // neue MultiConjunction konstruieren
143 for(Description c : tmp) {
144 // TODO: müssen auch alle Konzepte geklont werden??
145 // hier wird nur eine neue Liste erstellt
146 // => eigentlich muss nicht geklont werden (d.h. deep copy) da
147 // die Konzepte nicht verändert werden während des Algorithmus
148 List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
149 // es muss genau die vorherige Reihenfolge erhalten bleiben
150 // (zumindest bis die Normalform definiert ist)
151 int index = newChildren.indexOf(child);
152 newChildren.add(index, c);
153 newChildren.remove(child);
154 Intersection mc = new Intersection(newChildren);
155 refinements.add(mc);
156 }
157 }
158 } else if (concept instanceof Union) {
159 // eines der Elemente kann verfeinert werden
160 for(Description child : concept.getChildren()) {
161
162 // Refinement für das Kind ausführen
163 // tmp = refine(child);
164 tmp = refine(child);
165 // neue MultiConjunction konstruieren
166 for(Description c : tmp) {
167 List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
168 // es muss genau die vorherige Reihenfolge erhalten bleiben
169 // (zumindest bis die Normalform definiert ist)
170 int index = newChildren.indexOf(child);
171 newChildren.add(index, c);
172 newChildren.remove(child);
173 Union md = new Union(newChildren);
174 refinements.add(md);
175 }
176 }
177
178 // ein Element der Disjunktion kann weggelassen werden
179 for(Description child : concept.getChildren()) {
180 List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
181 newChildren.remove(child);
182 // wenn nur ein Kind da ist, dann wird Disjunktion gleich weggelassen
183 if(newChildren.size()==1)
184 refinements.add(newChildren.get(0));
185 else {
186 Union md = new Union(newChildren);
187 refinements.add(md);
188 }
189 }
190
191 } else if (concept instanceof ObjectSomeRestriction) {
192 tmp = refine(concept.getChild(0));
193 for(Description c : tmp) {
194 refinements.add(new ObjectSomeRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
195 }
196
197 // falls Kind Bottom ist, dann kann exists weggelassen werden
198 if(concept.getChild(0) instanceof Nothing)
199 refinements.add(new Nothing());
200
201 } else if (concept instanceof ObjectAllRestriction) {
202 tmp = refine(concept.getChild(0));
203 for(Description c : tmp) {
204 refinements.add(new ObjectAllRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
205 }
206
207 if(concept.getChild(0) instanceof Nothing)
208 refinements.add(new Nothing());
209
210 // falls es keine spezielleren atomaren Konzepte gibt, dann wird
211 // bottom angehangen => nur wenn es ein atomares Konzept (insbesondere != bottom)
212 // ist
213 // if(tmp.size()==0) {
214 // if(concept.getChild(0) instanceof AtomicConcept && tmp.size()==0) {
215 // refinements.add(new All(((Quantification)concept).getRole(),new Bottom()));
216 //}
217 } else
218 throw new RuntimeException(concept.toString());
219
220 // falls Konzept ungleich Bottom oder Top, dann kann ein Refinement von Top
221 // angehangen werden
222 if(concept instanceof Union || concept instanceof NamedClass ||
223 concept instanceof Negation || concept instanceof ObjectSomeRestriction || concept instanceof ObjectAllRestriction) {
224
225 // es wird AND TOP angehangen
226 Intersection mc = new Intersection();
227 mc.addChild(concept);
228 mc.addChild(new Thing());
229 refinements.add(mc);
230 }
231
232 // Refinements werden jetzt noch bereinigt, d.h. Verschachtelungen von Konjunktionen
233 // werden entfernt; es wird eine neue Menge erzeugt, da die Transformationen die
234 // Ordnung des Konzepts ändern könnten
235 // TODO: eventuell geht das noch effizienter, da die meisten Refinement-Regeln Refinements
236 // von Child-Konzepten sind, die bereits geordnet sind, d.h. man könnte dort eventuell
237 // gleich absichern, dass alle neu hinzugefügten Refinements in geordneter Negationsnormalform
238 // sind
239 // SortedSet<Concept> returnSet = new TreeSet<Concept>(conceptComparator);
240 /*
241
242 Set<Concept> returnSet = new HashSet<Concept>();
243 for(Concept c : refinements) {
244 ConceptTransformation.cleanConcept(c);
245 // ConceptTransformation.transformToOrderedNegationNormalForm(c, conceptComparator);
246 returnSet.add(c);
247 }
248
249 return returnSet;
250 */
251
252 // Zwischenschritt wird weggelassen - man muss nicht alle Konzepte cleanen,
253 // um dann nur eins davon auszuwählen
254
255 return refinements;
256
257 }
258
259 @Override
260 public Set<Description> refine(Description concept, int maxLength,
261 List<Description> knownRefinements) {
262 throw new RuntimeException();
263 }
264
265 }