Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1057] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-08-07 11:06:58
|
Revision: 1057
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1057&view=rev
Author: jenslehmann
Date: 2008-08-07 11:06:52 +0000 (Thu, 07 Aug 2008)
Log Message:
-----------
implemented selection of candidate class in label extension in EL downward refinement operator
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/refinementoperators/ELDown.java
trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-08-06 17:54:29 UTC (rev 1056)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-08-07 11:06:52 UTC (rev 1057)
@@ -30,7 +30,6 @@
import org.dllearner.core.owl.ObjectProperty;
import org.dllearner.core.owl.ObjectSomeRestriction;
import org.dllearner.core.owl.Thing;
-import org.dllearner.core.owl.UnsupportedLanguageException;
/**
* Represents an EL description tree, which corresponds to a
@@ -110,16 +109,6 @@
// }
/**
- * Constructs an EL description tree from an EL description.
- * @param description A description
- */
- public ELDescriptionNode(Description description) {
- // TODO not implemented
- // throw an exception if the description is not in EL
- throw new UnsupportedLanguageException(description.toString(), "EL");
- }
-
- /**
* Checks whether this node has a parent. If the parent link
* is null, the node is considered to be a root node.
* @return True of this is the root node and false otherwise.
@@ -188,6 +177,15 @@
}
/**
+ * Each node is assigned a number within the tree.
+ * TODO add explanation how this is done
+ * @return The position number of this node within the tree as described above.
+ */
+ public int getCurrentPositionNumber() {
+ return 0;
+ }
+
+ /**
* Replaces an entry in the node label.
* @param oldClass Class to remove from label.
* @param newClass Class to add to label.
@@ -220,24 +218,4 @@
return level;
}
- @Override
- public ELDescriptionNode clone() {
- ELDescriptionNode node = null;
- try {
- node = (ELDescriptionNode) super.clone();
- } catch (CloneNotSupportedException e) {
- // should never happen
- throw new InternalError(e.toString());
- }
-/*
- // create a deep copy
- node.children = new LinkedList<Description>();
- for(Description child : children) {
- Description clonedChild = (Description) child.clone();
- node.addChild(clonedChild);
- }
-*/
- return node;
- }
-
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-08-06 17:54:29 UTC (rev 1056)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-08-07 11:06:52 UTC (rev 1057)
@@ -25,7 +25,9 @@
import java.util.Set;
import java.util.TreeSet;
+import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.UnsupportedLanguageException;
/**
* Represents an EL description tree. Unlike {@link ELDescriptionNode},
@@ -50,6 +52,16 @@
public ELDescriptionTree() {
}
+
+ /**
+ * Constructs an EL description tree from an EL description.
+ * @param description A description
+ */
+ public ELDescriptionTree(Description description) {
+ // TODO not implemented
+ // throw an exception if the description is not in EL
+ throw new UnsupportedLanguageException(description.toString(), "EL");
+ }
/**
* Gets the nodes on a specific level of the tree.
@@ -63,6 +75,10 @@
return levelNodeMapping.get(level);
}
+ public Description transformToDescription() {
+ return rootNode.transformToDescription();
+ }
+
/**
* Internal method for updating the level node mapping.
* It is called when a new node is added to the tree.
@@ -96,6 +112,39 @@
return rootNode;
}
+ /**
+ * Selects a sub tree.
+ * @param positionNumber A position in the tree. Positions are iteratively given to nodes
+ * by leftmost depth-first search. This allows efficient selection of subtrees.
+ * (TODO: Implementation does not work if any node has more than two children
+ * like conjunction and disjunction.)
+ * @return The selected subtree.
+ */
+ public Description getNode(int positionNumber) {
+// if (children.size() == 0)
+// return this;
+// else if (children.size() == 1) {
+// if (positionNumber == 0)
+// return this;
+// else
+// return children.get(0).getSubtree(positionNumber - 1);
+// }
+// // arity 2
+// else {
+// // we have found it
+// if (positionNumber == 0)
+// return this;
+// // left subtree
+// int leftTreeNodes = children.get(0).getNumberOfNodes();
+// if (positionNumber <= leftTreeNodes)
+// return children.get(0).getSubtree(positionNumber - 1);
+// // right subtree
+// else
+// return children.get(1).getSubtree(positionNumber - leftTreeNodes - 1);
+// }
+ return null;
+ }
+
@Override
public ELDescriptionTree clone() {
// create a new reference tree
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-06 17:54:29 UTC (rev 1056)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-07 11:06:52 UTC (rev 1057)
@@ -25,6 +25,7 @@
import java.util.TreeMap;
import org.dllearner.algorithms.el.ELDescriptionNode;
+import org.dllearner.algorithms.el.ELDescriptionTree;
import org.dllearner.core.ReasoningService;
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.NamedClass;
@@ -95,10 +96,10 @@
public Set<Description> refine(Description concept) {
// TODO according to the specification, we need to minimise
// the tree (not yet implemented)
- ELDescriptionNode tree = new ELDescriptionNode(concept);
- Set<ELDescriptionNode> refinementTrees = refine(tree);
+ ELDescriptionTree tree = new ELDescriptionTree(concept);
+ Set<ELDescriptionTree> refinementTrees = refine(tree);
Set<Description> refinements = new HashSet<Description>();
- for(ELDescriptionNode refinementTree : refinementTrees) {
+ for(ELDescriptionTree refinementTree : refinementTrees) {
refinements.add(refinementTree.transformToDescription());
}
return refinements;
@@ -112,23 +113,28 @@
* @param tree Input EL description tree.
* @return Set of refined EL description trees.
*/
- public Set<ELDescriptionNode> refine(ELDescriptionNode tree) {
- return refine(tree, new Thing());
+ public Set<ELDescriptionTree> refine(ELDescriptionTree tree) {
+ return refine(tree, tree.getRootNode(), new Thing());
}
- private Set<ELDescriptionNode> refine(ELDescriptionNode tree, Description index) {
- Set<ELDescriptionNode> refinements = new HashSet<ELDescriptionNode>();
+ private Set<ELDescriptionTree> refine(ELDescriptionTree tree, ELDescriptionNode node, Description index) {
+ Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
// option 1: label extension
-
+ Set<NamedClass> candidates = utility.getClassCandidates(index, node.getLabel());
+ for(NamedClass nc : candidates) {
+
+ }
// option 2: label refinement
// loop through all classes in label
- for(NamedClass nc : tree.getLabel()) {
+ for(NamedClass nc : node.getLabel()) {
// find all more special classes for the given label
for(Description moreSpecial : rs.getMoreSpecialConcepts(nc)) {
if(moreSpecial instanceof NamedClass) {
// create refinements by replacing class
- ELDescriptionNode tmp = tree.clone();
- tmp.replaceInLabel(nc, (NamedClass) moreSpecial);
+ ELDescriptionTree tmp = tree.clone();
+ // TODO we need to find a way to get this node in
+ // the cloned tree
+// tmp.replaceInLabel(nc, (NamedClass) moreSpecial);
refinements.add(tmp);
}
}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java 2008-08-06 17:54:29 UTC (rev 1056)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java 2008-08-07 11:06:52 UTC (rev 1057)
@@ -47,6 +47,7 @@
public final class Utility {
private ReasoningService rs;
+ SubsumptionHierarchy sh;
// concept comparator
private ConceptComparator conceptComparator = new ConceptComparator();
@@ -61,6 +62,7 @@
public Utility(ReasoningService rs) {
this.rs = rs;
+ sh = rs.getSubsumptionHierarchy();
}
/**
@@ -107,21 +109,58 @@
private Set<NamedClass> getClassCandidatesRecursive(Description index, Set<NamedClass> existingClasses, Description upperClass) {
Set<NamedClass> candidates = new TreeSet<NamedClass>();
- SubsumptionHierarchy sh = rs.getSubsumptionHierarchy();
+
+ // we descend the subsumption hierarchy to ensure that we get
+ // the most general concepts satisfying the criteria
+ // there are 4 checks a class has to satisfy to get into the set;
+ // for 2 of them we can stop further traversal in the subsumption
+ // hierarchy
for(Description d : sh.getMoreSpecialConcepts(upperClass)) {
- // check disjointness with index
- if(isDisjoint(d,index)) {
- // check whether the class is meaningful, i.e. adds something to the index
- // to do this, we need to make sure that the class is not a superclass of the
- // index (otherwise we get nothing new)
- if(isDisjoint(new Negation(d),index)) {
- // TODO further checks
+ // owl:Nothing is never a candidate (not in EL)
+ if(!(d instanceof Nothing)) {
+ NamedClass candidate = (NamedClass) d;
+ // we first do those checks where we know that we do not
+ // need to traverse the subsumption hierarchy if they are
+ // not satisfied
+ // check1: disjointness with index
+ // check3: no superclass exists already
+ if(!isDisjoint(candidate,index) || !checkSubClasses(existingClasses,candidate)) {
+ // check whether the class is meaningful, i.e. adds something to the index
+ // to do this, we need to make sure that the class is not a superclass of the
+ // index (otherwise we get nothing new)
+ if(!isDisjoint(new Negation(candidate),index) || !checkSuperClasses(existingClasses,candidate)) {
+ // candidate went successfully through all checks
+ candidates.add(candidate);
+ } else {
+ // descend subsumption hierarchy to find candidates
+ candidates.addAll(getClassCandidatesRecursive(index, existingClasses, candidate));
+ }
}
}
}
return candidates;
}
+ // returns true of the candidate is not subclass of an existing class,
+ // false otherwise (check 3)
+ private boolean checkSubClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
+ for(NamedClass nc : existingClasses) {
+ if(sh.isSubclassOf(candidate, nc))
+ return false;
+ }
+ return true;
+ }
+
+ // returns true of the candidate is not superclass of an existing class,
+ // false otherwise (check 4)
+ private boolean checkSuperClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
+ for(NamedClass nc : existingClasses) {
+ if(sh.isSubclassOf(nc, candidate))
+ return false;
+ }
+ return true;
+ }
+
private boolean isDisjoint(Description d1, Description d2) {
// check whether we have cached this query
Map<Description,Boolean> tmp = cachedDisjoints.get(d1);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
