Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner: [659] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-02-27 19:04:38
|
Revision: 659
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=659&view=rev
Author: jenslehmann
Date: 2008-02-27 11:03:22 -0800 (Wed, 27 Feb 2008)
Log Message:
-----------
extracted math operations in downward refinement operator to separate class such that they can be used by all operators
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java
trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDown.java
trunk/src/dl-learner/org/dllearner/test/OWLAPIBugDemo.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/refinementoperators/MathOperations.java
Added: trunk/src/dl-learner/org/dllearner/refinementoperators/MathOperations.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/MathOperations.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/MathOperations.java 2008-02-27 19:03:22 UTC (rev 659)
@@ -0,0 +1,151 @@
+/**
+ * Copyright (C) 2007-2008, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.refinementoperators;
+
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.Union;
+
+/**
+ * Math operations related to refinement operators.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class MathOperations {
+
+ /**
+ * This function implements the getCombos method. Through the
+ * use of the upper limit, it is guaranteed that it
+ * will never return doublettes, so no special handling for
+ * them is necessary.
+ *
+ * @see #getCombos(int)
+ * @param number Number to decompose.
+ * @param upperLimit Maximum number allowed in sum.
+ * @param bisher Numbers created so far.
+ * @param combosTmp Temporary list of combinations (filled during run).
+ */
+ private static void decompose(int number, int upperLimit, LinkedList<Integer> bisher, List<List<Integer>> combosTmp) {
+
+ for (int i = Math.min(number, upperLimit); i >= 1; i--)
+ {
+
+ LinkedList<Integer> newBisher = null;
+ // für i==0 wird aus Effizienzgründen die bisherige Liste genommen
+ if(i==0) {
+ newBisher = bisher;
+ newBisher.add(i);
+ // für zahl - i == 1 muss gar keine Liste erstellt werden, da dann keine
+ // Zerlegung mehr möglich ist
+ } else if(number - i != 1) {
+ newBisher = cloneList(bisher);
+ newBisher.add(i);
+ }
+
+
+ if (number - i > 1)
+ {
+ // i wird hinzugefügt, d.h.
+ // - es muss nur noch zahl - i - 1 zerlegt werden (-1 wegen OR-Symbol)
+ // - es darf keine größere Zahl als i mehr vorkommen
+ // (dadurch gehen keine Kombinationen verloren)
+ decompose(number - i - 1, i, newBisher,combosTmp);
+ }
+ // Fall zahl == i, d.h. es muss nicht weiter zerlegt werden
+ else if(number - i == 0){
+ combosTmp.add(newBisher);
+ }
+
+
+ }
+
+ // numbers.add(bisher);
+ }
+
+ /**
+ * Given <code>number</code>, the functions returns all
+ * combinations of natural numbers plus the number count
+ * (which can be thought of as the number of interconnecting
+ * symbols between those numbers) adds up to <code>number</code>.
+ *
+ * It uses an efficient algorithm to achieve this, which can
+ * handle number=50 in less than a second and number=30 in
+ * about 10 milliseconds on an average PC.
+ *
+ * For illustrating the function, the return values of the first numbers
+ * are given:
+ * number = 1: [[1]]
+ * number = 2: [[2]]
+ * number = 3: [[3], [1, 1]]
+ * number = 4: [[4], [2, 1]]
+ * number = 5: [[5], [3, 1], [2, 2], [1, 1, 1]]
+ * number = 6: [[6], [4, 1], [3, 2], [2, 1, 1]]
+ * number = 7: [[7], [5, 1], [4, 2], [3, 3], [3, 1, 1], [2, 2, 1], [1, 1, 1, 1]]
+ *
+ * @param length
+ * @return
+ */
+ public static List<List<Integer>> getCombos(int length) {
+ // on Notebook: length 70 in 17 seconds, length 50 in 800ms, length 30 in 15ms
+ LinkedList<List<Integer>> combosTmp = new LinkedList<List<Integer>>();
+ decompose(length, length, new LinkedList<Integer>(), combosTmp);
+ return combosTmp;
+ }
+
+ @SuppressWarnings("unchecked")
+ private static LinkedList<Integer> cloneList(LinkedList<Integer> list) {
+ return (LinkedList<Integer>) list.clone();
+ }
+
+ public static void main(String args[]) {
+ System.out.println(getCombos(7));
+ }
+
+ // neue Implementierung, die nicht mehr zur incompleteness führen soll,
+ // da die Konzepte in einer MultiDisjunction als Liste gespeichert werden
+ public static Set<Union> incCrossProduct(Set<Union> baseSet, Set<Description> newSet) {
+ Set<Union> retSet = new HashSet<Union>();
+
+ if(baseSet.isEmpty()) {
+ for(Description c : newSet) {
+ Union md = new Union();
+ md.addChild(c);
+ retSet.add(md);
+ }
+ return retSet;
+ }
+
+ for(Union md : baseSet) {
+ for(Description c : newSet) {
+ Union mdNew = new Union(md.getChildren());
+ mdNew.addChild(c);
+ retSet.add(mdNew);
+ }
+ }
+
+ return retSet;
+ }
+
+}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java 2008-02-27 15:59:18 UTC (rev 658)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java 2008-02-27 19:03:22 UTC (rev 659)
@@ -19,21 +19,31 @@
*/
package org.dllearner.refinementoperators;
+import java.util.HashMap;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
+import java.util.TreeSet;
import org.dllearner.algorithms.refinement.RefinementOperator;
import org.dllearner.core.ReasoningService;
+import org.dllearner.core.owl.BooleanValueRestriction;
import org.dllearner.core.owl.DatatypeProperty;
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.Negation;
import org.dllearner.core.owl.Nothing;
+import org.dllearner.core.owl.ObjectAllRestriction;
import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.ObjectSomeRestriction;
import org.dllearner.core.owl.SubsumptionHierarchy;
import org.dllearner.core.owl.Thing;
+import org.dllearner.core.owl.Union;
+import org.dllearner.utilities.ConceptComparator;
+import org.dllearner.utilities.ConceptTransformation;
/**
* A downward refinement operator, which makes use of domains
@@ -58,6 +68,37 @@
private Map<DatatypeProperty,Description> dpDomains = new TreeMap<DatatypeProperty,Description>();
private Map<ObjectProperty,Description> opRanges = new TreeMap<ObjectProperty,Description>();
+ // gibt die Gr��e an bis zu der die Refinements des Top-Konzepts
+ // bereits berechnet worden => entspricht der max. L�nge der Menge M
+ private int topRefinementsLength = 0;
+
+ // die Menge M im Refinement-Operator indiziert nach ihrer L�nge
+ private Map<Integer,Set<Description>> m = new HashMap<Integer,Set<Description>>();
+
+ // Zerlegungen der Zahl n in Mengen
+ // Map<Integer,Set<IntegerCombo>> combos = new HashMap<Integer,Set<IntegerCombo>>();
+ private Map<Integer, List<List<Integer>>> combos = new HashMap<Integer, List<List<Integer>>>();
+ // abspeichern von Kombinationen während diese rekursiv berechnet werden
+ // private List<List<Integer>> combosTmp;
+
+ // Refinements des Top-Konzept indiziert nach Länge
+ private Map<Integer, TreeSet<Description>> topRefinements = new HashMap<Integer, TreeSet<Description>>();
+ private Map<Integer, TreeSet<Description>> topRefinementsCumulative = new HashMap<Integer, TreeSet<Description>>();
+
+ // comparator für Konzepte
+ private ConceptComparator conceptComparator = new ConceptComparator();
+
+ // Statistik
+ private long mComputationTimeNs = 0;
+ private long topComputationTimeNs = 0;
+
+// private boolean applyAllFilter = true;
+ private boolean applyExistsFilter = true;
+ private boolean useAllConstructor = true;
+ private boolean useExistsConstructor = true;
+ private boolean useNegation = true;
+ private boolean useBooleanDatatypes = true;
+
public RhoDRDown(ReasoningService rs) {
this.rs = rs;
subHierarchy = rs.getSubsumptionHierarchy();
@@ -110,4 +151,176 @@
return refinements;
}
+ // TODO: später private
+ public void computeTopRefinements(int maxLength) {
+ long topComputationTimeStartNs = System.nanoTime();
+
+ // M erweiteren
+ computeM(maxLength);
+
+ // berechnen aller möglichen Kombinationen für Disjunktion,
+ for(int i = topRefinementsLength+1; i <= maxLength; i++) {
+ combos.put(i,MathOperations.getCombos(i));
+ topRefinements.put(i, new TreeSet<Description>(conceptComparator));
+ // topRefinements.put(i, new HashSet<Concept>());
+
+ for(List<Integer> combo : combos.get(i)) {
+
+ // Kombination besteht aus nur einer Zahl => einfach M benutzen
+ // if(combo.getNumbers().size()==1) {
+ if(combo.size()==1) {
+ topRefinements.get(i).addAll(m.get(i));
+ // Kombination besteht aus mehreren Zahlen => Disjunktion erzeugen
+ } else {
+ Set<Union> baseSet = new HashSet<Union>();
+ for(Integer j : combo) { // combo.getNumbers()) {
+ baseSet = MathOperations.incCrossProduct(baseSet, m.get(j));
+ }
+
+ // Umwandlung aller Konzepte in Negationsnormalform
+ for(Description concept : baseSet) {
+ ConceptTransformation.transformToOrderedNegationNormalForm(concept, conceptComparator);
+ }
+
+ if(applyExistsFilter) {
+ Iterator<Union> it = baseSet.iterator();
+ while(it.hasNext()) {
+ Union md = it.next();
+ boolean remove = false;
+ // falls Exists r für gleiche Rolle zweimal vorkommt,
+ // dann rausschmeißen
+ // Map<AtomicRole,Boolean> roleOccured = new HashMap<AtomicRole,Boolean>();
+ Set<String> roles = new TreeSet<String>();
+ for(Description c : md.getChildren()) {
+ if(c instanceof ObjectSomeRestriction) {
+ String role = ((ObjectSomeRestriction)c).getRole().getName();
+ boolean roleExists = !roles.add(role);
+ // falls Rolle schon vorkommt, dann kann ganzes
+ // Refinement ignoriert werden (man könnte dann auch
+ // gleich abbrechen, aber das hat nur minimalste
+ // Auswirkungen auf Effizienz)
+ if(roleExists)
+ remove = true;
+ }
+ }
+ if(remove)
+ it.remove();
+
+ }
+ }
+
+ topRefinements.get(i).addAll(baseSet);
+ }
+ }
+
+ // neu berechnete Refinements kumulieren, damit sie schneller abgefragt werden können
+ // computeCumulativeTopRefinements(i);
+ TreeSet<Description> cumulativeRefinements = new TreeSet<Description>(conceptComparator);
+ // Set<Concept> cumulativeRefinements = new HashSet<Concept>();
+ for(int j=1; j<=i; j++) {
+ cumulativeRefinements.addAll(topRefinements.get(j));
+ }
+ topRefinementsCumulative.put(i, cumulativeRefinements);
+ }
+
+ // neue Maximallänge eintragen
+ topRefinementsLength = maxLength;
+
+ topComputationTimeNs += System.nanoTime() - topComputationTimeStartNs;
+ }
+
+ // computation of the set M
+ private void computeM(int maxLength) {
+ long mComputationTimeStartNs = System.nanoTime();
+ // System.out.println("compute M from " + (topRefinementsLength+1) + " up to " + maxLength);
+
+ // initialise all not yet initialised lengths
+ // (avoids null pointers in some cases)
+ for(int i=topRefinementsLength+1; i<=maxLength; i++) {
+ m.put(i, new TreeSet<Description>(conceptComparator));
+ }
+
+ // Berechnung der Basiskonzepte in M
+ // TODO: Spezialfälle, dass zwischen Top und Bottom nichts liegt behandeln
+ if(topRefinementsLength==0 && maxLength>0) {
+ // Konzepte der Länge 1 = alle Konzepte, die in der Subsumptionhierarchie unter Top liegen
+ Set<Description> m1 = rs.getMoreSpecialConcepts(new Thing());
+ m.put(1,m1);
+ }
+
+ if(topRefinementsLength<2 && maxLength>1) {
+ // Konzepte der Länge 2 = Negation aller Konzepte, die über Bottom liegen
+ if(useNegation) {
+ Set<Description> m2tmp = rs.getMoreGeneralConcepts(new Nothing());
+ Set<Description> m2 = new TreeSet<Description>(conceptComparator);
+ for(Description c : m2tmp) {
+ m2.add(new Negation(c));
+ }
+ m.put(2,m2);
+ }
+ }
+
+ if(topRefinementsLength<3 && maxLength>2) {
+ // Konzepte der Länge 3: EXISTS r.TOP
+ Set<Description> m3 = new TreeSet<Description>(conceptComparator);
+ if(useExistsConstructor) {
+ // previous operator: uses all roles
+ // for(AtomicRole r : Config.Refinement.allowedRoles) {
+ // m3.add(new Exists(r, new Top()));
+ //}
+ // new operator: only uses most general roles
+ for(ObjectProperty r : rs.getMostGeneralRoles()) {
+ m3.add(new ObjectSomeRestriction(r, new Thing()));
+ }
+
+ }
+
+ // boolean datatypes, e.g. testPositive = true
+ if(useBooleanDatatypes) {
+ Set<DatatypeProperty> booleanDPs = rs.getBooleanDatatypeProperties();
+ for(DatatypeProperty dp : booleanDPs) {
+ m3.add(new BooleanValueRestriction(dp,true));
+ m3.add(new BooleanValueRestriction(dp,false));
+ }
+ }
+
+ m.put(3,m3);
+ }
+
+ if(maxLength>2) {
+ if(useAllConstructor) {
+ // Konzepte, die mit ALL r starten
+ // alle existierenden Konzepte durchgehen, die maximal 2 k�rzer als
+ // die maximale L�nge sind
+ // topRefinementsLength - 1, damit Konzepte der Länge mindestens
+ // topRefinementsLength + 1 erzeugt werden (ALL r)
+ for(int i=topRefinementsLength-1; i<=maxLength-2; i++) {
+ // i muss natürlich mindestens 1 sein
+ if(i>=1) {
+
+ // alle Konzepte durchgehen
+ for(Description c : m.get(i)) {
+ // Fall wird jetzt weiter oben schon abgehandelt
+ // if(!m.containsKey(i+2))
+ // m.put(i+2, new TreeSet<Concept>(conceptComparator));
+
+ // previous operator: uses all roles
+ // for(AtomicRole r : Config.Refinement.allowedRoles) {
+ // Mehrfacheinf�gen ist bei einer Menge kein Problem
+ // m.get(i+2).add(new All(r,c));
+ // }
+
+ for(ObjectProperty r : rs.getMostGeneralRoles()) {
+ m.get(i+2).add(new ObjectAllRestriction(r,c));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ mComputationTimeNs += System.nanoTime() - mComputationTimeStartNs;
+ }
+
+
}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDown.java 2008-02-27 15:59:18 UTC (rev 658)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDown.java 2008-02-27 19:03:22 UTC (rev 659)
@@ -414,7 +414,7 @@
// berechnen aller möglichen Kombinationen für Disjunktion,
for(int i = topRefinementsLength+1; i <= maxLength; i++) {
- combos.put(i,getCombos(i));
+ combos.put(i,MathOperations.getCombos(i));
topRefinements.put(i, new TreeSet<Description>(conceptComparator));
// topRefinements.put(i, new HashSet<Concept>());
@@ -454,7 +454,7 @@
} else {
Set<Union> baseSet = new HashSet<Union>();
for(Integer j : combo) { // combo.getNumbers()) {
- baseSet = incCrossProduct2(baseSet, m.get(j));
+ baseSet = MathOperations.incCrossProduct(baseSet, m.get(j));
}
// Umwandlung aller Konzepte in Negationsnormalform
@@ -603,6 +603,7 @@
}
+ // wird nicht mehr verwendet
public static void summen(int zahl, int max, String bisher, int recDepth)
{
for(int j=0; j<recDepth; j++)
@@ -635,99 +636,14 @@
}
}
- @SuppressWarnings("unchecked")
- private LinkedList<Integer> cloneList(LinkedList<Integer> list) {
- return (LinkedList<Integer>) list.clone();
- }
+
- /**
- *
- * Dadurch das max das Maximum der vorkommenden Zahl regelt, kommen
- * keine doppelten Kombinationen vor.
- *
- * TODO: Implementierung mit Speicherung in Datenstruktur statt
- * direkter Ausgabe; IntegerCombo wird hier gar nicht benötigt, da
- * alle Elemente bereits in richtiger Reihenfolge vorliegen und
- * es keine doppelten Nennungen gibt
- *
- * @param zahl Zu zerlegende Zahl.
- * @param max Maximal in Summenzerlegung vorkommende Zahl.
- * @param bisher
- */
- private void zerlege(int zahl, int max, LinkedList<Integer> bisher, List<List<Integer>> combosTmp) {
-
- for (int i = Math.min(zahl, max); i >= 1; i--)
- {
-
- LinkedList<Integer> newBisher = null;
- // für i==0 wird aus Effizienzgründen die bisherige Liste genommen
- if(i==0) {
- newBisher = bisher;
- newBisher.add(i);
- // für zahl - i == 1 muss gar keine Liste erstellt werden, da dann keine
- // Zerlegung mehr möglich ist
- } else if(zahl - i != 1) {
- newBisher = cloneList(bisher);
- newBisher.add(i);
- }
-
-
- if (zahl - i > 1)
- {
- // i wird hinzugefügt, d.h.
- // - es muss nur noch zahl - i - 1 zerlegt werden (-1 wegen OR-Symbol)
- // - es darf keine größere Zahl als i mehr vorkommen
- // (dadurch gehen keine Kombinationen verloren)
- zerlege(zahl - i - 1, i, newBisher,combosTmp);
- }
- // Fall zahl == i, d.h. es muss nicht weiter zerlegt werden
- else if(zahl - i == 0){
- combosTmp.add(newBisher);
- }
-
- }
-
- // numbers.add(bisher);
- }
- // auf Notebook: Länge 70 in 17 Sekunden, Länge 50 in 800ms, Länge 30 in 15ms
- // http://88.198.173.90/tud/forum/messages?topic=304392
- public List<List<Integer>> getCombos(int length) {
- LinkedList<List<Integer>> combosTmp = new LinkedList<List<Integer>>();
- zerlege(length, length, new LinkedList<Integer>(), combosTmp);
- return combosTmp;
- }
-
- // neue Implementierung, die nicht mehr zur incompleteness führen soll,
- // da die Konzepte in einer MultiDisjunction als Liste gespeichert werden
- private Set<Union> incCrossProduct2(Set<Union> baseSet, Set<Description> newSet) {
- Set<Union> retSet = new HashSet<Union>();
-
- if(baseSet.isEmpty()) {
- for(Description c : newSet) {
- Union md = new Union();
- md.addChild(c);
- retSet.add(md);
- }
- return retSet;
- }
-
- for(Union md : baseSet) {
- for(Description c : newSet) {
- Union mdNew = new Union(md.getChildren());
- mdNew.addChild(c);
- retSet.add(mdNew);
- }
- }
-
- return retSet;
- }
-
// incremental cross product
// es müssen Listen statt Sets verwendet werden
@SuppressWarnings({"unused"})
- private Set<Set<Description>> incCrossProduct(Set<Set<Description>> baseSet, Set<Description> newSet) {
+ private Set<Set<Description>> incCrossProductOld(Set<Set<Description>> baseSet, Set<Description> newSet) {
Set<Set<Description>> retSet = new HashSet<Set<Description>>();
// falls erste Menge leer ist, dann wird Menge mit jeweils Singletons aus der
Modified: trunk/src/dl-learner/org/dllearner/test/OWLAPIBugDemo.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/OWLAPIBugDemo.java 2008-02-27 15:59:18 UTC (rev 658)
+++ trunk/src/dl-learner/org/dllearner/test/OWLAPIBugDemo.java 2008-02-27 19:03:22 UTC (rev 659)
@@ -63,11 +63,11 @@
// class cast exception
Set<Set<OWLDescription>> test = reasoner.getDomains(p);
- OWLClass oc = (OWLClass) test.iterator().next();
- System.out.println(oc);
-// for(Set<OWLDescription> test2 : test) {
-// System.out.println(test2);
-// }
+// OWLClass oc = (OWLClass) test.iterator().next();
+// System.out.println(oc);
+ for(Set<OWLDescription> test2 : test) {
+ System.out.println(test2);
+ }
// save ontology
manager.saveOntology(ontology);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
