Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner: [688] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-03-05 12:07:36
|
Revision: 688
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=688&view=rev
Author: jenslehmann
Date: 2008-03-05 04:07:28 -0800 (Wed, 05 Mar 2008)
Log Message:
-----------
implemented a new heuristic
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java
trunk/src/dl-learner/org/dllearner/core/owl/Nothing.java
trunk/src/dl-learner/org/dllearner/core/owl/Thing.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/MultiHeuristic.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java 2008-03-04 19:10:55 UTC (rev 687)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java 2008-03-05 12:07:28 UTC (rev 688)
@@ -39,16 +39,15 @@
*/
public class ExampleBasedNode {
- // example based variables here
+ // example based variables
private Set<Individual> coveredPositives;
private Set<Individual> coveredNegatives;
- // TOP ist einfach das TOP-Konzept, also das einzige welches nicht evaluiert wird
+ // the method by which quality was evaluated in this node
public enum QualityEvaluationMethod { TOP, REASONER, TOO_WEAK_LIST, OVERLY_GENERAL_LIST };
-
private QualityEvaluationMethod qualityEvaluationMethod = QualityEvaluationMethod.TOP;
- // alle Eigenschaften eines Knotens im Suchbaum
+ // all properties of a node in the search tree
private Description concept;
private int horizontalExpansion;
private int coveredNegativeExamples;
@@ -59,28 +58,17 @@
private static ConceptComparator conceptComparator = new ConceptComparator();
private static NodeComparatorStable nodeComparator = new NodeComparatorStable();
- // Einbettung in Suchbaum
+ // link to parent in search tree
private ExampleBasedNode parent = null;
- // private Set<Node> children = new HashSet<Node>();
private Set<ExampleBasedNode> children = new TreeSet<ExampleBasedNode>(nodeComparator);
- // es wird auch eine Liste von Kindern gehalten
+ // apart from the child nodes, we also keep child concepts
private Set<Description> childConcepts = new TreeSet<Description>(conceptComparator);
- // verwendeter Operator für Expansion des Knotens
- // private RefinementOperator operator;
-
public ExampleBasedNode(Description concept) {
this.concept = concept;
horizontalExpansion = 0;
isQualityEvaluated = false;
}
-
- public void setCoveredNegativeExamples(int coveredNegativeExamples) {
- if(isQualityEvaluated)
- throw new RuntimeException("Cannot set quality of a node more than once.");
- this.coveredNegativeExamples = coveredNegativeExamples;
- isQualityEvaluated = true;
- }
public void setHorizontalExpansion(int horizontalExpansion) {
this.horizontalExpansion = horizontalExpansion;
@@ -104,25 +92,16 @@
return children.add(child);
}
- public Description getConcept() {
- return concept;
+ public void setQualityEvaluationMethod(QualityEvaluationMethod qualityEvaluationMethod) {
+ this.qualityEvaluationMethod = qualityEvaluationMethod;
}
- public int getCoveredNegativeExamples() {
- return coveredNegativeExamples;
+
+ public void setCoveredExamples(Set<Individual> coveredPositives, Set<Individual> coveredNegatives) {
+ this.coveredPositives = coveredPositives;
+ this.coveredNegatives = coveredNegatives;
+ isQualityEvaluated = true;
}
- public int getHorizontalExpansion() {
- return horizontalExpansion;
- }
- public boolean isQualityEvaluated() {
- return isQualityEvaluated;
- }
- public boolean isRedundant() {
- return isRedundant;
- }
- public boolean isTooWeak() {
- return isTooWeak;
- }
-
+
@Override
public String toString() {
String ret = concept.toString() + " [q:";
@@ -134,7 +113,7 @@
return ret;
}
- // gibt die Refinement-Chain zurück, die zu dem Knoten geführt hat
+ // returns the refinement chain leading to this node as string
public String getRefinementChainString() {
if(parent!=null) {
String ret = parent.getRefinementChainString();
@@ -143,8 +122,8 @@
} else {
return concept.toString();
}
- }
-
+ }
+
public String getTreeString() {
return getTreeString(0).toString();
}
@@ -173,6 +152,14 @@
ret += " ("+qualityEvaluationMethod+"), he:" + horizontalExpansion + "]";
return ret;
+ }
+
+ public Set<Individual> getCoveredPositives() {
+ return coveredPositives;
+ }
+
+ public Set<Individual> getCoveredNegatives() {
+ return coveredNegatives;
}
public Set<ExampleBasedNode> getChildren() {
@@ -183,28 +170,35 @@
return childConcepts;
}
+ public Description getConcept() {
+ return concept;
+ }
+
public QualityEvaluationMethod getQualityEvaluationMethod() {
return qualityEvaluationMethod;
+ }
+
+ public int getCoveredNegativeExamples() {
+ return coveredNegativeExamples;
}
-
- public void setQualityEvaluationMethod(QualityEvaluationMethod qualityEvaluationMethod) {
- this.qualityEvaluationMethod = qualityEvaluationMethod;
+ public int getHorizontalExpansion() {
+ return horizontalExpansion;
}
-
- public Set<Individual> getCoveredPositives() {
- return coveredPositives;
+ public boolean isQualityEvaluated() {
+ return isQualityEvaluated;
}
-
- public void setCoveredPositives(Set<Individual> coveredPositives) {
- this.coveredPositives = coveredPositives;
+ public boolean isRedundant() {
+ return isRedundant;
}
-
- public Set<Individual> getCoveredNegatives() {
- return coveredNegatives;
+ public boolean isTooWeak() {
+ return isTooWeak;
}
- public void setCoveredNegatives(Set<Individual> coveredNegatives) {
- this.coveredNegatives = coveredNegatives;
- }
-
-}
+ /**
+ * @return the parent
+ */
+ public ExampleBasedNode getParent() {
+ return parent;
+ }
+
+}
\ No newline at end of file
Modified: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java 2008-03-04 19:10:55 UTC (rev 687)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java 2008-03-05 12:07:28 UTC (rev 688)
@@ -217,37 +217,25 @@
}
public void start() {
-
-
// calculate quality threshold required for a solution
allowedMisclassifications = (int) Math.round(noise * nrOfExamples);
// start search with start class
if(startDescription == null) {
- Thing top = new Thing();
- startNode = new ExampleBasedNode(top);
- // top covers all negatives
- int coveredNegativeExamples = getNumberOfNegatives();
- startNode.setCoveredNegativeExamples(coveredNegativeExamples);
- startNode.setCoveredPositives(learningProblem.getPositiveExamples());
- startNode.setCoveredNegatives(learningProblem.getNegativeExamples());
+ startNode = new ExampleBasedNode(Thing.instance);
+ startNode.setCoveredExamples(learningProblem.getPositiveExamples(), learningProblem.getNegativeExamples());
} else {
startNode = new ExampleBasedNode(startDescription);
Set<Individual> coveredNegatives = rs.instanceCheck(startDescription, learningProblem.getNegativeExamples());
- startNode.setCoveredPositives(rs.instanceCheck(startDescription, learningProblem.getPositiveExamples()));
- startNode.setCoveredNegatives(coveredNegatives);
- startNode.setCoveredNegativeExamples(coveredNegatives.size());
+ Set<Individual> coveredPositives = rs.instanceCheck(startDescription, learningProblem.getPositiveExamples());
+ startNode.setCoveredExamples(coveredPositives, coveredNegatives);
}
candidates.add(startNode);
candidatesStable.add(startNode);
- // note that TOP may already be a solution
+
ExampleBasedNode bestNode = startNode;
-// solutionFound = (coveredNegativeExamples == 0);
-// solutions = new LinkedList<Concept>();
-// if(solutionFound)
-// solutions.add(top);
-
+
int loop = 0;
algorithmStartTime = System.nanoTime();
@@ -571,8 +559,7 @@
// quality is the number of misclassifications (if it is not too weak)
quality = (nrOfPositiveExamples - newlyCoveredPositives.size())
+ newlyCoveredNegatives.size();
- newNode.setCoveredNegatives(newlyCoveredNegatives);
- newNode.setCoveredPositives(newlyCoveredPositives);
+ newNode.setCoveredExamples(newlyCoveredPositives, newlyCoveredNegatives);
}
}
@@ -588,7 +575,7 @@
solutions.add(refinement);
}
- newNode.setCoveredNegativeExamples(quality);
+// newNode.setCoveredNegativeExamples(quality);
newCandidates.add(newNode);
// candidates.add(newNode);
// candidatesStable.add(newNode);
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/MultiHeuristic.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/MultiHeuristic.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/MultiHeuristic.java 2008-03-05 12:07:28 UTC (rev 688)
@@ -0,0 +1,114 @@
+/**
+ * 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.algorithms.refexamples;
+
+import org.dllearner.utilities.ConceptComparator;
+
+/**
+ * This heuristic combines the following criteria to assign a
+ * double score value to a node:
+ * <ul>
+ * <li>quality/accuracy of a concept (based on the full training set, not
+ * the negative example coverage as the flexible heuristic)</li>
+ * <li>horizontal expansion</li>
+ * <li>accuracy gain: The heuristic takes into account the accuracy
+ * difference between a node and its parent. If there is no gain (even
+ * though we know that the refinement is proper) it is unlikely (although
+ * not excluded) that the refinement is a necessary path to take towards a
+ * solution.</li>
+ * </ul>
+ *
+ * The heuristic has two parameters:
+ * <ul>
+ * <li>expansion penalty factor: describes how much accuracy gain is worth
+ * an increase of horizontal expansion by one (typical value: 0.01)</li>
+ * <li>gain bonus factor: describes how accuracy gain should be weighted
+ * versus accuracy itself (typical value: 1.00)</li>
+ * </ul>
+ *
+ * The value of a node is calculated as follows:
+ *
+ * <p><code>value = accuracy + gain bonus factor * accuracy gain - expansion penalty
+ * factor * horizontal expansion</code></p>
+ *
+ * <p><code>accuracy = (TP + TN)/(P + N)</code></p>
+ *
+ * <p><code>
+ * TP = number of true positives (= covered positives)<br />
+ * TN = number of true negatives (= nr of negatives examples - covered negatives)<br />
+ * P = number of positive examples<br />
+ * N = number of negative examples<br />
+ * </code></p>
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class MultiHeuristic implements ExampleBasedHeuristic {
+
+ private ConceptComparator conceptComparator = new ConceptComparator();
+
+ // heuristic parameters
+ private double expansionPenaltyFactor = 0.01;
+ private double gainBonusFactor = 1.00;
+
+ // examples
+ private int nrOfNegativeExamples;
+ private int nrOfExamples;
+
+ public MultiHeuristic(int nrOfPositiveExamples, int nrOfNegativeExamples, double expansionPenaltyFactor, double gainBonusFactor) {
+ this.nrOfNegativeExamples = nrOfNegativeExamples;
+ nrOfExamples = nrOfPositiveExamples + nrOfNegativeExamples;
+ this.expansionPenaltyFactor = expansionPenaltyFactor;
+ this.gainBonusFactor = gainBonusFactor;
+ }
+
+ /* (non-Javadoc)
+ * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
+ */
+ public int compare(ExampleBasedNode node1, ExampleBasedNode node2) {
+ double score1 = getNodeScore(node1);
+ double score2 = getNodeScore(node2);
+ double diff = score1 - score2;
+ if(diff>0)
+ return 1;
+ else if(diff<0)
+ return -1;
+ else
+ // TODO: would it be OK to simply return 0 here (?)
+ // could improve performance a bit
+ return conceptComparator.compare(node1.getConcept(), node2.getConcept());
+ }
+
+ public double getNodeScore(ExampleBasedNode node) {
+ double accuracy = getAccuracy(node.getCoveredPositives().size(),node.getCoveredNegatives().size());
+ ExampleBasedNode parent = node.getParent();
+ double gain = 0;
+ if(parent != null) {
+ double parentAccuracy = getAccuracy(parent.getCoveredPositives().size(),parent.getCoveredNegatives().size());
+ gain = accuracy - parentAccuracy;
+ }
+ return accuracy + gainBonusFactor * gain - expansionPenaltyFactor * node.getHorizontalExpansion();
+ }
+
+ private double getAccuracy(int coveredPositives, int coveredNegatives) {
+ return (coveredPositives + nrOfNegativeExamples - coveredNegatives)/(double)nrOfExamples;
+
+ }
+}
Modified: trunk/src/dl-learner/org/dllearner/core/owl/Nothing.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/owl/Nothing.java 2008-03-04 19:10:55 UTC (rev 687)
+++ trunk/src/dl-learner/org/dllearner/core/owl/Nothing.java 2008-03-05 12:07:28 UTC (rev 688)
@@ -1,3 +1,22 @@
+/**
+ * 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.core.owl;
import java.util.Map;
@@ -2,13 +21,11 @@
-
-
+/**
+ * Implementation of owl:nothing/BOTTOM.
+ *
+ * @author Jens Lehmann
+ *
+ */
public class Nothing extends Description {
- /*
- @Override
- protected void calculateSets(FlatABox abox, SortedSet<String> adcPosSet, SortedSet<String> adcNegSet) {
- posSet = abox.bottom;
- negSet = abox.top;
- }
- */
+ public static final Nothing instance = new Nothing();
@@ -48,5 +65,4 @@
visitor.visit(this);
}
-
}
Modified: trunk/src/dl-learner/org/dllearner/core/owl/Thing.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/owl/Thing.java 2008-03-04 19:10:55 UTC (rev 687)
+++ trunk/src/dl-learner/org/dllearner/core/owl/Thing.java 2008-03-05 12:07:28 UTC (rev 688)
@@ -1,3 +1,22 @@
+/**
+ * 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.core.owl;
import java.util.Map;
@@ -2,12 +21,19 @@
+/**
+ * Implementation of owl:thing/TOP.
+ *
+ * TODO: According to the OWL 1.1 spec, owl:thing is special instance of
+ * class, so it might be better to put a method there for retrieving
+ * a/the instance of owl:thing. However, some algorithms require parent
+ * links e.g. in EXISTS r.TOP we may need to know where TOP belongs
+ * (especially for genetic operators). This is instance dependant, i.e.
+ * two different instances of TOP can have different parent links.
+ *
+ * @author Jens Lehmann
+ *
+ */
public class Thing extends Description {
- /*
- @Override
- protected void calculateSets(FlatABox abox, SortedSet<String> adcPosSet, SortedSet<String> adcNegSet) {
- posSet = abox.top;
- negSet = abox.bottom;
- }
- */
-
+ public static final Thing instance = new Thing();
+
public String toString(String baseURI, Map<String,String> prefixes) {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
