001 /**
002 * Copyright (C) 2007-2008, 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
021 package org.dllearner.algorithms.refinement2;
022
023 import java.text.DecimalFormat;
024 import java.util.Set;
025 import java.util.SortedSet;
026 import java.util.TreeSet;
027
028 import org.dllearner.core.configurators.ROLComponent2Configurator;
029 import org.dllearner.core.owl.Description;
030 import org.dllearner.core.owl.Individual;
031 import org.dllearner.utilities.owl.ConceptComparator;
032
033 /**
034 *
035 * Represents a node in the search tree. A node consists of
036 * the following parts:
037 *
038 * ... (see paper) ...
039 *
040 * @author Jens Lehmann
041 *
042 */
043 public class ExampleBasedNode {
044
045 // public static long exampleMemoryCounter = 0;
046
047 private ROLComponent2Configurator configurator;
048
049 private static DecimalFormat df = new DecimalFormat();
050
051 // example based variables
052 private Set<Individual> coveredPositives;
053 private Set<Individual> coveredNegatives;
054 // private int coveredPositiveSize;
055 // private int coveredNegativeSize;
056
057 // the method by which quality was evaluated in this node
058 public enum QualityEvaluationMethod { START, REASONER, TOO_WEAK_LIST, OVERLY_GENERAL_LIST };
059 private QualityEvaluationMethod qualityEvaluationMethod = QualityEvaluationMethod.START;
060
061 // all properties of a node in the search tree
062 private Description concept;
063 private int horizontalExpansion;
064 // specifies whether the node is too weak (exceeds the max. nr allowed
065 // misclassifications of positive examples)
066 private boolean isTooWeak;
067 private boolean isQualityEvaluated;
068 private boolean isRedundant;
069
070 private static ConceptComparator conceptComparator = new ConceptComparator();
071 private static NodeComparatorStable nodeComparator = new NodeComparatorStable();
072
073 // link to parent in search tree
074 private ExampleBasedNode parent = null;
075 private SortedSet<ExampleBasedNode> children = new TreeSet<ExampleBasedNode>(nodeComparator);
076 // apart from the child nodes, we also keep child concepts
077 private SortedSet<Description> childConcepts = new TreeSet<Description>(conceptComparator);
078
079 // a flag whether this could be a solution for a posonly learning problem
080 private boolean isPosOnlyCandidate = true;
081
082 public ExampleBasedNode(ROLComponent2Configurator configurator, Description concept) {
083 this.configurator = configurator;
084 this.concept = concept;
085 horizontalExpansion = 0;
086 isQualityEvaluated = false;
087 }
088
089 public void setHorizontalExpansion(int horizontalExpansion) {
090 this.horizontalExpansion = horizontalExpansion;
091 }
092
093 public void setRedundant(boolean isRedundant) {
094 this.isRedundant = isRedundant;
095 }
096
097 public void setTooWeak(boolean isTooWeak) {
098 if(isQualityEvaluated)
099 throw new RuntimeException("Cannot set quality of a node more than once.");
100 this.isTooWeak = isTooWeak;
101 isQualityEvaluated = true;
102 }
103
104 public boolean addChild(ExampleBasedNode child) {
105 // child.setParent(this);
106 child.parent = this;
107 childConcepts.add(child.concept);
108 return children.add(child);
109 }
110
111 public void setQualityEvaluationMethod(QualityEvaluationMethod qualityEvaluationMethod) {
112 this.qualityEvaluationMethod = qualityEvaluationMethod;
113 }
114
115 public void setCoveredExamples(Set<Individual> coveredPositives, Set<Individual> coveredNegatives) {
116 this.coveredPositives = coveredPositives;
117 this.coveredNegatives = coveredNegatives;
118 isQualityEvaluated = true;
119 // exampleMemoryCounter += coveredPositives.size() * 4;
120 // exampleMemoryCounter += coveredNegatives.size() * 4;
121 }
122
123 @Override
124 public String toString() {
125 // System.out.println(concept);
126 String ret = concept.toString() + " [q:";
127 if(isTooWeak)
128 ret += "tw";
129 else
130 ret += coveredNegatives.size();
131 ret += ", he:" + horizontalExpansion + ", children:" + children.size() + "]";
132 return ret;
133 }
134
135 // returns the refinement chain leading to this node as string
136 public String getRefinementChainString() {
137 if(parent!=null) {
138 String ret = parent.getRefinementChainString();
139 ret += " => " + concept.toString();
140 return ret;
141 } else {
142 return concept.toString();
143 }
144 }
145
146 public String getTreeString(int nrOfPositiveExamples, int nrOfNegativeExamples) {
147 return getTreeString(nrOfPositiveExamples, nrOfNegativeExamples, 0,null).toString();
148 }
149
150 public String getTreeString(int nrOfPositiveExamples, int nrOfNegativeExamples, String baseURI) {
151 return getTreeString(nrOfPositiveExamples, nrOfNegativeExamples, 0,baseURI).toString();
152 }
153
154 private StringBuilder getTreeString(int nrOfPositiveExamples, int nrOfNegativeExamples, int depth, String baseURI) {
155 StringBuilder treeString = new StringBuilder();
156 for(int i=0; i<depth-1; i++)
157 treeString.append(" ");
158 if(depth!=0)
159 // treeString.append("|-→ ");
160 treeString.append("|--> ");
161 treeString.append(getShortDescription(nrOfPositiveExamples, nrOfNegativeExamples, baseURI)+"\n");
162 for(ExampleBasedNode child : children) {
163 treeString.append(child.getTreeString(nrOfPositiveExamples, nrOfNegativeExamples, depth+1,baseURI));
164 }
165 return treeString;
166 }
167
168 public String getShortDescription(int nrOfPositiveExamples, int nrOfNegativeExamples, String baseURI) {
169 String ret = concept.toString(baseURI,null) + " [";
170
171 if(isTooWeak)
172 ret += "q:tw";
173 else {
174 double accuracy = 100 * (coveredPositives.size() + nrOfNegativeExamples - coveredNegatives.size())/(double)(nrOfPositiveExamples+nrOfNegativeExamples);
175 ret += "acc:" + df.format(accuracy) + "% ";
176
177 // comment this out to display the heuristic score with default parameters
178 double heuristicScore = MultiHeuristic.getNodeScore(this, nrOfPositiveExamples, nrOfNegativeExamples, configurator);
179 ret += "h:" +df.format(heuristicScore) + " ";
180
181 int wrongPositives = nrOfPositiveExamples - coveredPositives.size();
182 ret += "q:" + wrongPositives + "p-" + coveredNegatives.size() + "n";
183 }
184
185 ret += " ("+qualityEvaluationMethod+"), he:" + horizontalExpansion;
186 ret += " c:" + children.size() + "]";
187
188 return ret;
189 }
190
191 public String getShortDescriptionHTML(int nrOfPositiveExamples, int nrOfNegativeExamples, String baseURI) {
192 String ret = "<html><nobr> " + concept.toManchesterSyntaxString(baseURI,null) + " <i>[";
193
194 if(isTooWeak)
195 ret += "q:tw";
196 else {
197 double accuracy = 100 * (coveredPositives.size() + nrOfNegativeExamples - coveredNegatives.size())/(double)(nrOfPositiveExamples+nrOfNegativeExamples);
198 ret += "<b>acc: " + df.format(accuracy) + "% </b>";
199
200 // comment this out to display the heuristic score with default parameters
201 double heuristicScore = MultiHeuristic.getNodeScore(this, nrOfPositiveExamples, nrOfNegativeExamples, configurator);
202 ret += "h:" +df.format(heuristicScore) + " ";
203
204 int wrongPositives = nrOfPositiveExamples - coveredPositives.size();
205 ret += "q:" + wrongPositives + "p-" + coveredNegatives.size() + "n";
206 }
207
208 ret += " ("+qualityEvaluationMethod+"), he:" + horizontalExpansion;
209 ret += " c:" + children.size() + "]";
210
211 return ret + "</i></nobr></html>";
212 }
213
214 //TODO integrate this method with the one above
215 public String getStats(int nrOfPositiveExamples, int nrOfNegativeExamples) {
216 String ret = " [";
217
218 if(isTooWeak)
219 ret += "q:tw";
220 else {
221 double accuracy = 100 * (coveredPositives.size() + nrOfNegativeExamples - coveredNegatives.size())/(double)(nrOfPositiveExamples+nrOfNegativeExamples);
222 ret += "acc:" + df.format(accuracy) + "% ";
223
224 // comment this out to display the heuristic score with default parameters
225 double heuristicScore = MultiHeuristic.getNodeScore(this, nrOfPositiveExamples, nrOfNegativeExamples, configurator);
226 ret += "h:" +df.format(heuristicScore) + " ";
227
228 int wrongPositives = nrOfPositiveExamples - coveredPositives.size();
229 ret += "q:" + wrongPositives + "p-" + coveredNegatives.size() + "n";
230 }
231
232 ret += " ("+qualityEvaluationMethod+"), he:" + horizontalExpansion;
233 ret += " c:" + children.size() + "]";
234
235 return ret;
236 }
237
238 public double getAccuracy(int nrOfPositiveExamples, int nrOfNegativeExamples) {
239 return (coveredPositives.size() + nrOfNegativeExamples - coveredNegatives.size())/(double)(nrOfPositiveExamples+nrOfNegativeExamples);
240 }
241
242 /**
243 * Used to detect whether one node is more accurate than another one
244 * with calculating accuracy itself.
245 * @return Number of covered positives minus number of covered negatives.
246 */
247 public int getCovPosMinusCovNeg() {
248 return coveredPositives.size() - coveredNegatives.size();
249 }
250
251 public Set<Individual> getCoveredPositives() {
252 return coveredPositives;
253 }
254
255 public Set<Individual> getCoveredNegatives() {
256 return coveredNegatives;
257 }
258
259 public SortedSet<ExampleBasedNode> getChildren() {
260 return children;
261 }
262
263 public SortedSet<Description> getChildConcepts() {
264 return childConcepts;
265 }
266
267 public Description getConcept() {
268 return concept;
269 }
270
271 public QualityEvaluationMethod getQualityEvaluationMethod() {
272 return qualityEvaluationMethod;
273 }
274
275 public int getHorizontalExpansion() {
276 return horizontalExpansion;
277 }
278 public boolean isQualityEvaluated() {
279 return isQualityEvaluated;
280 }
281 public boolean isRedundant() {
282 return isRedundant;
283 }
284 public boolean isTooWeak() {
285 return isTooWeak;
286 }
287
288 /**
289 * @return the parent
290 */
291 public ExampleBasedNode getParent() {
292 return parent;
293 }
294
295 public boolean isPosOnlyCandidate() {
296 return isPosOnlyCandidate;
297 }
298
299 public void setPosOnlyCandidate(boolean isPosOnlyCandidate) {
300 this.isPosOnlyCandidate = isPosOnlyCandidate;
301 }
302
303 }