Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1580] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2009-01-24 20:02:36
|
Revision: 1580
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1580&view=rev
Author: jenslehmann
Date: 2009-01-24 20:02:30 +0000 (Sat, 24 Jan 2009)
Log Message:
-----------
new as method for EL operator 2
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTreeComparator.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
trunk/src/dl-learner/org/dllearner/scripts/evaluation/ELOperatorBenchmark.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSet.java
trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSetComparator.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -112,6 +112,7 @@
// this is the root node of the overall tree
tree.rootNode = this;
tree.addNodeToLevel(this, level);
+ tree.size += label.size();
}
// convenience constructor
@@ -194,6 +195,8 @@
extendLabel(nc);
}
+ // 1 for the edge (labels are already taken care of by extendLabel)
+ tree.size += 1;
}
/**
@@ -339,6 +342,9 @@
public void extendLabel(NamedClass newClass) {
label.add(newClass);
labelSimulationUpdate();
+ tree.size += 1;
+// System.out.println(tree);
+// System.out.println(tree.size);
}
// simulation update when extending or refining label
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -65,6 +65,8 @@
// max level = 0 means that there is no tree at all
// (max level = 1 means the root node exists)
private int maxLevel = 0;
+
+ protected int size = 1;
protected ELDescriptionNode rootNode;
@@ -533,6 +535,7 @@
// update global tree
treeClone.rootNode = newRoot;
treeClone.maxLevel = maxLevel;
+ treeClone.size = size;
// nodes
treeClone.nodes = new LinkedList<ELDescriptionNode>();
@@ -604,10 +607,10 @@
* @return The tree size.
*/
public int getSize() {
- int size = nodes.size();
- for(ELDescriptionNode node : nodes) {
- size += node.getLabel().size();
- }
+// int size = nodes.size();
+// for(ELDescriptionNode node : nodes) {
+// size += node.getLabel().size();
+// }
return size;
}
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTreeComparator.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTreeComparator.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTreeComparator.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -41,9 +41,15 @@
*/
@Override
public int compare(ELDescriptionTree tree1, ELDescriptionTree tree2) {
- ELDescriptionNode node1 = tree1.getRootNode();
- ELDescriptionNode node2 = tree2.getRootNode();
- return nodeComp.compare(node1, node2);
+ // we use the size as first criterion to avoid many comparisons
+ int sizeDiff = tree1.size - tree2.size;
+ if(sizeDiff == 0) {
+ ELDescriptionNode node1 = tree1.getRootNode();
+ ELDescriptionNode node2 = tree2.getRootNode();
+ return nodeComp.compare(node1, node2);
+ } else {
+ return sizeDiff;
+ }
}
}
Added: trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSet.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSet.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSet.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -0,0 +1,61 @@
+/**
+ * Copyright (C) 2007-2009, 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.algorithms.el;
+
+import java.util.Set;
+
+import org.dllearner.core.owl.ObjectProperty;
+
+/**
+ * Convenience class representing an EL description tree and a set of roles.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class TreeAndRoleSet {
+
+ private ELDescriptionTree tree;
+ private Set<ObjectProperty> roles;
+
+ public TreeAndRoleSet(ELDescriptionTree tree, Set<ObjectProperty> roles) {
+ this.tree = tree;
+ this.roles = roles;
+ }
+
+ /**
+ * @return the tree
+ */
+ public ELDescriptionTree getTree() {
+ return tree;
+ }
+
+ /**
+ * @return the roles
+ */
+ public Set<ObjectProperty> getRoles() {
+ return roles;
+ }
+
+ @Override
+ public String toString() {
+ return "("+tree.toDescriptionString() + "," + roles.toString()+")";
+ }
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSetComparator.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSetComparator.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/TreeAndRoleSetComparator.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -0,0 +1,66 @@
+/**
+ * Copyright (C) 2007-2009, 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.algorithms.el;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.dllearner.core.owl.ObjectProperty;
+
+/**
+ * A comparator implementation for the tree and role set convenience structure.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class TreeAndRoleSetComparator implements Comparator<TreeAndRoleSet> {
+
+ private ELDescriptionTreeComparator treeComp = new ELDescriptionTreeComparator();
+
+ /* (non-Javadoc)
+ * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
+ */
+ @Override
+ public int compare(TreeAndRoleSet o1, TreeAndRoleSet o2) {
+ int comp = treeComp.compare(o1.getTree(), o2.getTree());
+ if(comp == 0) {
+ Set<ObjectProperty> op1 = o1.getRoles();
+ Set<ObjectProperty> op2 = o2.getRoles();
+ int sizeDiff = op1.size() - op2.size();
+ if(sizeDiff == 0) {
+ Iterator<ObjectProperty> it1 = op1.iterator();
+ Iterator<ObjectProperty> it2 = op2.iterator();
+ while(it1.hasNext()) {
+ int stringComp = it1.next().compareTo(it2.next());
+ if(stringComp != 0) {
+ return stringComp;
+ }
+ }
+ return 0;
+ } else {
+ return sizeDiff;
+ }
+ } else {
+ return comp;
+ }
+ }
+
+}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -38,6 +38,9 @@
import org.dllearner.algorithms.el.ELDescriptionEdgeComparator;
import org.dllearner.algorithms.el.ELDescriptionNode;
import org.dllearner.algorithms.el.ELDescriptionTree;
+import org.dllearner.algorithms.el.ELDescriptionTreeComparator;
+import org.dllearner.algorithms.el.TreeAndRoleSet;
+import org.dllearner.algorithms.el.TreeAndRoleSetComparator;
import org.dllearner.core.ReasonerComponent;
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.Intersection;
@@ -95,7 +98,9 @@
private Utility utility;
// comparators
- ELDescriptionEdgeComparator edgeComp = new ELDescriptionEdgeComparator();
+ private ELDescriptionTreeComparator treeComp = new ELDescriptionTreeComparator();
+ private ELDescriptionEdgeComparator edgeComp = new ELDescriptionEdgeComparator();
+ private TreeAndRoleSetComparator mComp = new TreeAndRoleSetComparator();
public ELDown2(ReasonerComponent rs) {
this.rs = rs;
@@ -155,7 +160,7 @@
refinements.addAll(extendLabel(tree, v, position));
refinements.addAll(refineLabel(tree, v, position));
refinements.addAll(refineEdge(tree, v, position));
- refinements.addAll(attachSubtree(tree, v, position));
+ refinements.addAll(attachSubtree2(tree, v, position));
}
return refinements;
@@ -251,7 +256,7 @@
}
// operation 4: attach tree
- private List<ELDescriptionTree> attachSubtree(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
+ private Collection<ELDescriptionTree> attachSubtree(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
Monitor mon = MonitorFactory.start("attach tree");
List<ELDescriptionTree> refinements = new LinkedList<ELDescriptionTree>();
@@ -343,6 +348,103 @@
return refinements;
}
+ // new version of as
+ private Collection<ELDescriptionTree> attachSubtree2(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
+ Monitor mon = MonitorFactory.start("attach tree");
+ Set<ELDescriptionTree> refinements = new TreeSet<ELDescriptionTree>(treeComp);
+
+ // create and initialise M
+ TreeSet<TreeAndRoleSet> m = new TreeSet<TreeAndRoleSet>(mComp);
+ ELDescriptionTree topTree = new ELDescriptionTree(rs, Thing.instance);
+ Description index = getIndex(v);
+ SortedSet<ObjectProperty> appOPs = utility.computeApplicableObjectProperties(index);
+ m.add(new TreeAndRoleSet(topTree, appOPs));
+
+// logger.trace("M initialised: " + m);
+
+ while(!m.isEmpty()) {
+
+ // pick first element of M
+ TreeAndRoleSet tars = m.pollFirst();
+ ELDescriptionTree tp = tars.getTree();
+ Set<ObjectProperty> rSet = tars.getRoles();
+// logger.trace("selected first element of M: " + tars);
+
+
+ // init sets R' and R''
+ // more efficient
+ SortedSet<ObjectProperty> rpSet = utility.computeMgr(appOPs);
+ rpSet.retainAll(rSet);
+// SortedSet<ObjectProperty> rpSet = new TreeSet<ObjectProperty>();
+// for(ObjectProperty rEl : rSet) {
+// if(!containsSuperProperty(rEl, rSet)) {
+// rpSet.add(rEl);
+// }
+// }
+
+// logger.trace("R': " + rpSet);
+ Set<ObjectProperty> rppSet = new TreeSet<ObjectProperty>();
+
+ while(!rpSet.isEmpty()) {
+ // pick an element r from R'
+ Iterator<ObjectProperty> it = rpSet.iterator();
+ ObjectProperty r = it.next();
+ it.remove();
+// logger.trace("picked role r: " + r);
+
+ ELDescriptionTree tpp = mergeTrees(tree, v, position, r, tp);
+// logger.trace("merged tree:\n" + tpp);
+ // the position of w is the position of v + #edges outgoing from v
+ int[] wPosition = new int[position.length+1];
+ System.arraycopy(position, 0, wPosition, 0, position.length);
+ wPosition[position.length] = v.getEdges().size();
+ ELDescriptionNode w = tpp.getNode(wPosition);
+
+ if(tpp.isMinimal()) {
+ refinements.add(tpp);
+// logger.trace("tree is minimal; added to T");
+ } else {
+ boolean check = asCheck(w);
+// logger.trace("tree is not minimal; result of complex check: " + check);
+
+ if(check) {
+
+// Monitor mon2 = MonitorFactory.start("as.tmp");
+ // add role to R' if it is in R (allowed)
+ for(ObjectProperty subRole : rs.getSubProperties(r)) {
+ if(rSet.contains(subRole)) {
+ rpSet.add(subRole);
+ }
+ }
+ rppSet.add(r);
+// logger.trace("updated R' to: " + rpSet);
+// logger.trace("updated R'' to: " + rppSet);
+// mon2.stop();
+ }
+ }
+ }
+
+ if(rppSet.size() != 0) {
+ // recursive call
+ mon.stop();
+// logger.trace("recursive call start");
+ List<ELDescriptionTree> recRefs = refine(tp);
+// logger.trace("recursive call end");
+ mon.start();
+
+ for(ELDescriptionTree tStar : recRefs) {
+ m.add(new TreeAndRoleSet(tStar, rppSet));
+ }
+// logger.trace("M after recursion: " + m);
+ }
+
+ }
+
+ mon.stop();
+ return refinements;
+ }
+
+
// create a new tree which is obtained by attaching the new tree at the given node in the tree via role r
private ELDescriptionTree mergeTrees(ELDescriptionTree tree, ELDescriptionNode node, int[] position, ObjectProperty r, ELDescriptionTree newTree) {
Monitor mon = MonitorFactory.start("as.merge trees");
@@ -472,4 +574,23 @@
return i;
}
+ private Description getIndex(ELDescriptionNode v) {
+ if(v.isRoot()) {
+ return Thing.instance;
+ } else {
+ return opRanges.get(v.getParentEdge().getLabel());
+ }
+ }
+
+ private boolean containsSuperProperty(ObjectProperty prop, Set<ObjectProperty> props) {
+ for(ObjectProperty p : props) {
+ if(!p.equals(prop)) {
+ if(opHierarchy.isSubpropertyOf(prop, p)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
}
Modified: trunk/src/dl-learner/org/dllearner/scripts/evaluation/ELOperatorBenchmark.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/scripts/evaluation/ELOperatorBenchmark.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/scripts/evaluation/ELOperatorBenchmark.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -71,9 +71,10 @@
new File(dir).mkdir();
String example = "/home/jl/promotion/ontologien/galen2.owl";
+// example = "/home/jl/downloads/uni-leipzig/OTAGen-v1/generated/generatedOnt.owl";
for(int i=10; i<17; i++) {
- rand = new Random(2);
+ rand = new Random(1);
testOntology(dir, example, 100, i);
}
@@ -217,7 +218,7 @@
statString += getMonitorData(MonitorFactory.getMonitor("attach tree", "ms."));
statString += getMonitorData(MonitorFactory.getMonitor("as.merge trees", "ms."));
statString += getMonitorData(MonitorFactory.getMonitor("as.complex check", "ms."));
-// statString += getMonitorData(MonitorFactory.getMonitor("as.tmp", "ms."));
+ statString += getMonitorData(MonitorFactory.getMonitor("as.tmp", "ms."));
// statString += getMonitorData(MonitorFactory.getMonitor("el.tmp", "ms."));
statString += getMonitorDataBoolean(MonitorFactory.getMonitor("as.minimal", "boolean"));
statString += getMonitorDataBoolean(MonitorFactory.getMonitor("as.check", "boolean"));
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2009-01-18 16:41:36 UTC (rev 1579)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2009-01-24 20:02:30 UTC (rev 1580)
@@ -82,6 +82,17 @@
System.out.println("TEST 1");
ReasonerComponent rs = TestOntologies.getTestOntology(TestOntology.SIMPLE);
+// ELDescriptionTree t = new ELDescriptionTree(rs);
+// ObjectProperty p1 = new ObjectProperty("p1");
+// ObjectProperty p2 = new ObjectProperty("p2");
+// NamedClass a1 = new NamedClass("a1");
+// ELDescriptionNode n1 = new ELDescriptionNode(t, a1);
+// ELDescriptionNode n2 = new ELDescriptionNode(n1, p1, a1);
+//
+// System.out.println(t);
+// System.out.println(t.getSize());
+// System.exit(0);
+
// input description
Description input = KBParser.parseConcept("(human AND EXISTS has.animal)");
System.out.println("refining: " + input.toString(KBParser.internalNamespace, null));
@@ -179,6 +190,7 @@
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS has.human))");
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS has.cat))");
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS has.EXISTS has.TOP))");
+ desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS has.(cat AND bird)))");
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS hasPet.cat))");
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS hasPet.EXISTS has.TOP))");
desiredString.add("(human AND (EXISTS hasPet.bird AND EXISTS hasChild.TOP))");
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
