001/** 002 * Copyright (C) 2007 - 2016, 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 */ 019package org.dllearner.algorithms.celoe; 020 021import com.google.common.collect.Sets; 022import com.jamonapi.Monitor; 023import com.jamonapi.MonitorFactory; 024import org.dllearner.core.*; 025import org.dllearner.core.config.ConfigOption; 026import org.dllearner.core.owl.ClassHierarchy; 027import org.dllearner.core.owl.DatatypePropertyHierarchy; 028import org.dllearner.core.owl.ObjectPropertyHierarchy; 029import org.dllearner.kb.OWLAPIOntology; 030import org.dllearner.learningproblems.ClassAsInstanceLearningProblem; 031import org.dllearner.learningproblems.ClassLearningProblem; 032import org.dllearner.learningproblems.PosNegLP; 033import org.dllearner.learningproblems.PosOnlyLP; 034import org.dllearner.reasoning.ClosedWorldReasoner; 035import org.dllearner.reasoning.OWLAPIReasoner; 036import org.dllearner.reasoning.ReasonerImplementation; 037import org.dllearner.reasoning.SPARQLReasoner; 038import org.dllearner.refinementoperators.*; 039import org.dllearner.utilities.*; 040import org.dllearner.utilities.datastructures.SearchTree; 041import org.dllearner.utilities.owl.*; 042import org.semanticweb.owlapi.apibinding.OWLManager; 043import org.semanticweb.owlapi.model.*; 044import org.slf4j.Logger; 045import org.slf4j.LoggerFactory; 046import org.slf4j.Marker; 047import org.slf4j.MarkerFactory; 048import org.springframework.beans.factory.annotation.Autowired; 049import uk.ac.manchester.cs.owl.owlapi.OWLClassImpl; 050import uk.ac.manchester.cs.owl.owlapi.OWLDataFactoryImpl; 051 052import java.io.File; 053import java.util.*; 054import java.util.concurrent.TimeUnit; 055 056/** 057 * The CELOE (Class Expression Learner for Ontology Engineering) algorithm. 058 * It adapts and extends the standard supervised learning algorithm for the 059 * ontology engineering use case. 060 * 061 * @author Jens Lehmann 062 * 063 */ 064@SuppressWarnings("CloneDoesntCallSuperClone") 065@ComponentAnn(name="CELOE", shortName="celoe", version=1.0, description="CELOE is an adapted and extended version of the OCEL algorithm applied for the ontology engineering use case. See http://jens-lehmann.org/files/2011/celoe.pdf for reference.") 066public class CELOE extends AbstractCELA implements Cloneable{ 067 068 private static final Logger logger = LoggerFactory.getLogger(CELOE.class); 069 private static final Marker sparql_debug = MarkerFactory.getMarker("SD"); 070 071 private boolean isRunning = false; 072 private boolean stop = false; 073 074// private OEHeuristicStable heuristicStable = new OEHeuristicStable(); 075// private OEHeuristicRuntime heuristicRuntime = new OEHeuristicRuntime(); 076 077 @ConfigOption(description = "the refinement operator instance to use") 078 private LengthLimitedRefinementOperator operator; 079 080 private SearchTree<OENode> searchTree; 081 @ConfigOption(defaultValue="celoe_heuristic") 082 private AbstractHeuristic heuristic; // = new OEHeuristicRuntime(); 083 // the class with which we start the refinement process 084 @ConfigOption(defaultValue = "owl:Thing", 085 description = "You can specify a start class for the algorithm. To do this, you have to use Manchester OWL syntax either with full IRIs or prefixed IRIs.", 086 exampleValue = "ex:Male or http://example.org/ontology/Female") 087 private OWLClassExpression startClass; 088 089 // all descriptions in the search tree plus those which were too weak (for fast redundancy check) 090 private TreeSet<OWLClassExpression> descriptions; 091 092 093 // if true, then each solution is evaluated exactly instead of approximately 094 // private boolean exactBestDescriptionEvaluation = false; 095 @ConfigOption(defaultValue="false", description="Use this if you are interested in only one suggestion and your learning problem has many (more than 1000) examples.") 096 private boolean singleSuggestionMode; 097 private OWLClassExpression bestDescription; 098 private double bestAccuracy = Double.MIN_VALUE; 099 100 private OWLClass classToDescribe; 101 // examples are either 1.) instances of the class to describe 2.) positive examples 102 // 3.) union of pos.+neg. examples depending on the learning problem at hand 103 private Set<OWLIndividual> examples; 104 105 // CELOE was originally created for learning classes in ontologies, but also 106 // works for other learning problem types 107 private boolean isClassLearningProblem; 108 private boolean isEquivalenceProblem; 109 110 // important parameters (non-config options but internal) 111 private double noise; 112 113 private boolean filterFollowsFromKB = false; 114 115 // less important parameters 116 // forces that one solution cannot be subexpression of another expression; this option is useful to get diversity 117 // but it can also suppress quite useful expressions 118 private boolean forceMutualDifference = false; 119 120 // utility variables 121 122 // statistical variables 123 private int expressionTests = 0; 124 private int minHorizExp = 1; 125 private int maxHorizExp = 0; 126 private long totalRuntimeNs = 0; 127 128 // TODO: turn those into config options 129 130 131 // important: do not initialise those with empty sets 132 // null = no settings for allowance / ignorance 133 // empty set = allow / ignore nothing (it is often not desired to allow no class!) 134 @ConfigOption(defaultValue="false", description="specifies whether to write a search tree") 135 private boolean writeSearchTree = false; 136 137 @ConfigOption(defaultValue="log/searchTree.txt", description="file to use for the search tree") 138 private String searchTreeFile = "log/searchTree.txt"; 139 140 @ConfigOption(defaultValue="false", description="specifies whether to replace the search tree in the log file after each run or append the new search tree") 141 private boolean replaceSearchTree = false; 142 143 @ConfigOption(defaultValue="10", description="Sets the maximum number of results one is interested in. (Setting this to a lower value may increase performance as the learning algorithm has to store/evaluate/beautify less descriptions).") 144 private int maxNrOfResults = 10; 145 146 @ConfigOption(defaultValue="0.0", description="the (approximated) percentage of noise within the examples") 147 private double noisePercentage = 0.0; 148 149 @ConfigOption(defaultValue="false", description="If true, then the results will not contain suggestions, which already follow logically from the knowledge base. Be careful, since this requires a potentially expensive consistency check for candidate solutions.") 150 private boolean filterDescriptionsFollowingFromKB = false; 151 152 @ConfigOption(defaultValue="false", description="If true, the algorithm tries to find a good starting point close to an existing definition/super class of the given class in the knowledge base.") 153 private boolean reuseExistingDescription = false; 154 155 @ConfigOption(defaultValue="0", description="The maximum number of candidate hypothesis the algorithm is allowed to test (0 = no limit). The algorithm will stop afterwards. (The real number of tests can be slightly higher, because this criterion usually won't be checked after each single test.)") 156 private int maxClassExpressionTests = 0; 157 158 @ConfigOption(defaultValue="0", description = "The maximum number of candidate hypothesis the algorithm is allowed after an improvement in accuracy (0 = no limit). The algorithm will stop afterwards. (The real number of tests can be slightly higher, because this criterion usually won't be checked after each single test.)") 159 private int maxClassExpressionTestsAfterImprovement = 0; 160 161 @ConfigOption(defaultValue = "0", description = "maximum execution of the algorithm in seconds after last improvement") 162 private int maxExecutionTimeInSecondsAfterImprovement = 0; 163 164 @ConfigOption(defaultValue="false", description="specifies whether to terminate when noise criterion is met") 165 private boolean terminateOnNoiseReached = false; 166 167 @ConfigOption(defaultValue="7", description="maximum depth of description") 168 private double maxDepth = 7; 169 170 @ConfigOption(defaultValue="false", description="algorithm will terminate immediately when a correct definition is found") 171 private boolean stopOnFirstDefinition = false; 172 173 private int expressionTestCountLastImprovement; 174 175 176 @SuppressWarnings("unused") 177 private long timeLastImprovement = 0; 178 @ConfigOption(defaultValue = "false", description = "whether to try and refine solutions which already have accuracy value of 1") 179 private boolean expandAccuracy100Nodes = false; 180 private double currentHighestAccuracy; 181 182 // option to keep track of best score during algorithm run 183 private boolean keepTrackOfBestScore = false; 184 private SortedMap<Long, Double> runtimeVsBestScore = new TreeMap<>(); 185 186 187 public CELOE() {} 188 189 public CELOE(CELOE celoe){ 190 setReasoner(celoe.reasoner); 191 setLearningProblem(celoe.learningProblem); 192 193 setAllowedConcepts(celoe.getAllowedConcepts()); 194 setAllowedObjectProperties(celoe.getAllowedObjectProperties()); 195 setAllowedDataProperties(celoe.getAllowedDataProperties()); 196 197 setIgnoredConcepts(celoe.ignoredConcepts); 198 setIgnoredObjectProperties(celoe.getIgnoredObjectProperties()); 199 setIgnoredDataProperties(celoe.getIgnoredDataProperties()); 200 201 setExpandAccuracy100Nodes(celoe.expandAccuracy100Nodes); 202 setFilterDescriptionsFollowingFromKB(celoe.filterDescriptionsFollowingFromKB); 203 setHeuristic(celoe.heuristic); 204 205 setMaxClassExpressionTests(celoe.maxClassExpressionTests); 206 setMaxClassExpressionTestsAfterImprovement(celoe.maxClassExpressionTestsAfterImprovement); 207 setMaxDepth(celoe.maxDepth); 208 setMaxExecutionTimeInSeconds(celoe.getMaxExecutionTimeInSeconds()); 209 setMaxExecutionTimeInSecondsAfterImprovement(celoe.maxExecutionTimeInSecondsAfterImprovement); 210 setMaxNrOfResults(celoe.maxNrOfResults); 211 setNoisePercentage(celoe.noisePercentage); 212 213 LengthLimitedRefinementOperator op = new RhoDRDown((RhoDRDown)celoe.operator); 214 try { 215 op.init(); 216 } catch (ComponentInitException e) { 217 e.printStackTrace(); 218 } 219 setOperator(op); 220 221 222 setReuseExistingDescription(celoe.reuseExistingDescription); 223 setSingleSuggestionMode(celoe.singleSuggestionMode); 224 setStartClass(celoe.startClass); 225 setStopOnFirstDefinition(celoe.stopOnFirstDefinition); 226 setTerminateOnNoiseReached(celoe.terminateOnNoiseReached); 227 setUseMinimizer(celoe.isUseMinimizer()); 228 229 setWriteSearchTree(celoe.writeSearchTree); 230 setReplaceSearchTree(celoe.replaceSearchTree); 231 } 232 233 public CELOE(AbstractClassExpressionLearningProblem problem, AbstractReasonerComponent reasoner) { 234 super(problem, reasoner); 235 } 236 237 public static Collection<Class<? extends AbstractClassExpressionLearningProblem>> supportedLearningProblems() { 238 Collection<Class<? extends AbstractClassExpressionLearningProblem>> problems = new LinkedList<>(); 239 problems.add(AbstractClassExpressionLearningProblem.class); 240 return problems; 241 } 242 243 @Override 244 public void init() throws ComponentInitException { 245 baseURI = reasoner.getBaseURI(); 246 prefixes = reasoner.getPrefixes(); 247 248 if(maxExecutionTimeInSeconds != 0 && maxExecutionTimeInSecondsAfterImprovement != 0) { 249 maxExecutionTimeInSeconds = Math.min(maxExecutionTimeInSeconds, maxExecutionTimeInSecondsAfterImprovement); 250 } 251 252 // TODO add comment 253 ClassHierarchy classHierarchy = initClassHierarchy(); 254 ObjectPropertyHierarchy objectPropertyHierarchy = initObjectPropertyHierarchy(); 255 DatatypePropertyHierarchy datatypePropertyHierarchy = initDataPropertyHierarchy(); 256 257 // if no one injected a heuristic, we use a default one 258 if(heuristic == null) { 259 heuristic = new OEHeuristicRuntime(); 260 heuristic.init(); 261 } 262 263 minimizer = new OWLClassExpressionMinimizer(dataFactory, reasoner); 264 265 if (writeSearchTree) { 266 File f = new File(searchTreeFile); 267 if (f.getParentFile() != null) { 268 f.getParentFile().mkdirs(); 269 } 270 Files.clearFile(f); 271 } 272 273 // start at owl:Thing by default 274 startClass = OWLAPIUtils.classExpressionPropertyExpanderChecked(this.startClass, reasoner, dataFactory, this::computeStartClass, logger); 275 276 bestEvaluatedDescriptions = new EvaluatedDescriptionSet(maxNrOfResults); 277 278 isClassLearningProblem = (learningProblem instanceof ClassLearningProblem); 279 280 // we put important parameters in class variables 281 noise = noisePercentage/100d; 282 283 // (filterFollowsFromKB is automatically set to false if the problem 284 // is not a class learning problem 285 filterFollowsFromKB = filterDescriptionsFollowingFromKB && isClassLearningProblem; 286 287 // actions specific to ontology engineering 288 if(isClassLearningProblem) { 289 ClassLearningProblem problem = (ClassLearningProblem) learningProblem; 290 classToDescribe = problem.getClassToDescribe(); 291 isEquivalenceProblem = problem.isEquivalenceProblem(); 292 293 examples = reasoner.getIndividuals(classToDescribe); 294 } else if(learningProblem instanceof PosOnlyLP) { 295 examples = ((PosOnlyLP)learningProblem).getPositiveExamples(); 296 } else if(learningProblem instanceof PosNegLP) { 297 examples = Sets.union(((PosNegLP)learningProblem).getPositiveExamples(),((PosNegLP)learningProblem).getNegativeExamples()); 298 } 299 300 // create a refinement operator and pass all configuration 301 // variables to it 302 if (operator == null) { 303 // we use a default operator and inject the class hierarchy for now 304 operator = new RhoDRDown(); 305 ((CustomStartRefinementOperator) operator).setStartClass(startClass); 306 ((ReasoningBasedRefinementOperator) operator).setReasoner(reasoner); 307 } 308 if (operator instanceof CustomHierarchyRefinementOperator) { 309 ((CustomHierarchyRefinementOperator) operator).setClassHierarchy(classHierarchy); 310 ((CustomHierarchyRefinementOperator) operator).setObjectPropertyHierarchy(objectPropertyHierarchy); 311 ((CustomHierarchyRefinementOperator) operator).setDataPropertyHierarchy(datatypePropertyHierarchy); 312 } 313 314 if (!((AbstractRefinementOperator) operator).isInitialized()) 315 operator.init(); 316 317 initialized = true; 318 } 319 320 @Override 321 public void start() { 322 stop = false; 323 isRunning = true; 324 reset(); 325 nanoStartTime = System.nanoTime(); 326 327 currentHighestAccuracy = 0.0; 328 OENode nextNode; 329 330 logger.info("start class:" + startClass); 331 addNode(startClass, null); 332 333 while (!terminationCriteriaSatisfied()) { 334 showIfBetterSolutionsFound(); 335 336 // chose best node according to heuristics 337 nextNode = getNextNodeToExpand(); 338 int horizExp = nextNode.getHorizontalExpansion(); 339 340 // apply refinement operator 341 TreeSet<OWLClassExpression> refinements = refineNode(nextNode); 342 343 while(!refinements.isEmpty() && !terminationCriteriaSatisfied()) { 344 // pick element from set 345 OWLClassExpression refinement = refinements.pollFirst(); 346 347 // get length of class expression 348 int length = OWLClassExpressionUtils.getLength(refinement); 349 350 // we ignore all refinements with lower length and too high depth 351 // (this also avoids duplicate node children) 352 if(length >= horizExp && OWLClassExpressionUtils.getDepth(refinement) <= maxDepth) { 353 // add node to search tree 354 addNode(refinement, nextNode); 355 } 356 } 357 358 showIfBetterSolutionsFound(); 359 360 // update the global min and max horizontal expansion values 361 updateMinMaxHorizExp(nextNode); 362 363 // write the search tree (if configured) 364 if (writeSearchTree) { 365 writeSearchTree(refinements); 366 } 367 } 368 369 if(singleSuggestionMode) { 370 bestEvaluatedDescriptions.add(bestDescription, bestAccuracy, learningProblem); 371 } 372 373 // print some stats 374 printAlgorithmRunStats(); 375 376 // print solution(s) 377 logger.info("solutions:\n" + getSolutionString()); 378 379 isRunning = false; 380 } 381 382 /* 383 * Compute the start class in the search space from which the refinement will start. 384 * We use the intersection of super classes for definitions (since it needs to 385 * capture all instances), but owl:Thing for learning subclasses (since it is 386 * superfluous to add super classes in this case) 387 */ 388 private OWLClassExpression computeStartClass() { 389 OWLClassExpression startClass = dataFactory.getOWLThing(); 390 391 if(isClassLearningProblem) { 392 if(isEquivalenceProblem) { 393 Set<OWLClassExpression> existingDefinitions = reasoner.getAssertedDefinitions(classToDescribe); 394 if(reuseExistingDescription && (existingDefinitions.size() > 0)) { 395 // the existing definition is reused, which in the simplest case means to 396 // use it as a start class or, if it is already too specific, generalise it 397 398 // pick the longest existing definition as candidate 399 OWLClassExpression existingDefinition = null; 400 int highestLength = 0; 401 for(OWLClassExpression exDef : existingDefinitions) { 402 if(OWLClassExpressionUtils.getLength(exDef) > highestLength) { 403 existingDefinition = exDef; 404 highestLength = OWLClassExpressionUtils.getLength(exDef); 405 } 406 } 407 408 LinkedList<OWLClassExpression> startClassCandidates = new LinkedList<>(); 409 startClassCandidates.add(existingDefinition); 410 // hack for RhoDRDown 411 if(operator instanceof RhoDRDown) { 412 ((RhoDRDown)operator).setDropDisjuncts(true); 413 } 414 LengthLimitedRefinementOperator upwardOperator = new OperatorInverter(operator); 415 416 // use upward refinement until we find an appropriate start class 417 boolean startClassFound = false; 418 OWLClassExpression candidate; 419 do { 420 candidate = startClassCandidates.pollFirst(); 421 if(((ClassLearningProblem)learningProblem).getRecall(candidate)<1.0) { 422 // add upward refinements to list 423 Set<OWLClassExpression> refinements = upwardOperator.refine(candidate, OWLClassExpressionUtils.getLength(candidate)); 424// System.out.println("ref: " + refinements); 425 LinkedList<OWLClassExpression> refinementList = new LinkedList<>(refinements); 426// Collections.reverse(refinementList); 427// System.out.println("list: " + refinementList); 428 startClassCandidates.addAll(refinementList); 429// System.out.println("candidates: " + startClassCandidates); 430 } else { 431 startClassFound = true; 432 } 433 } while(!startClassFound); 434 startClass = candidate; 435 436 if(startClass.equals(existingDefinition)) { 437 logger.info("Reusing existing class expression " + OWLAPIRenderers.toManchesterOWLSyntax(startClass) + " as start class for learning algorithm."); 438 } else { 439 logger.info("Generalised existing class expression " + OWLAPIRenderers.toManchesterOWLSyntax(existingDefinition) + " to " + OWLAPIRenderers.toManchesterOWLSyntax(startClass) + ", which is used as start class for the learning algorithm."); 440 } 441 442 if(operator instanceof RhoDRDown) { 443 ((RhoDRDown)operator).setDropDisjuncts(false); 444 } 445 446 } else { 447 Set<OWLClassExpression> superClasses = reasoner.getClassHierarchy().getSuperClasses(classToDescribe, true); 448 if(superClasses.size() > 1) { 449 startClass = dataFactory.getOWLObjectIntersectionOf(superClasses); 450 } else if(superClasses.size() == 1){ 451 startClass = (OWLClassExpression) superClasses.toArray()[0]; 452 } else { 453 startClass = dataFactory.getOWLThing(); 454 logger.warn(classToDescribe + " is equivalent to owl:Thing. Usually, it is not " + 455 "sensible to learn a class expression in this case."); 456 } 457 } 458 } 459 } 460 return startClass; 461 } 462 463 private OENode getNextNodeToExpand() { 464 // we expand the best node of those, which have not achieved 100% accuracy 465 // already and have a horizontal expansion equal to their length 466 // (rationale: further extension is likely to add irrelevant syntactical constructs) 467 Iterator<OENode> it = searchTree.descendingIterator(); 468 if (logger.isTraceEnabled()) { 469 for (OENode N:searchTree.getNodeSet()) { 470 logger.trace(sparql_debug,"`getnext:"+N); 471 } 472 } 473 474 while(it.hasNext()) { 475 OENode node = it.next(); 476 logger.trace(sparql_debug,"``"+node+node.getAccuracy()); 477 if (isExpandAccuracy100Nodes() && node.getHorizontalExpansion() < OWLClassExpressionUtils.getLength(node.getDescription())) { 478 return node; 479 } else { 480 if(node.getAccuracy() < 1.0 || node.getHorizontalExpansion() < OWLClassExpressionUtils.getLength(node.getDescription())) { 481 return node; 482 } 483 } 484 } 485 486 // this should practically never be called, since for any reasonable learning 487 // task, we will always have at least one node with less than 100% accuracy 488 throw new RuntimeException("CELOE could not find any node with lesser accuracy."); 489 } 490 491 // expand node horizontically 492 private TreeSet<OWLClassExpression> refineNode(OENode node) { 493 logger.trace(sparql_debug,"REFINE NODE " + node); 494 MonitorFactory.getTimeMonitor("refineNode").start(); 495 // we have to remove and add the node since its heuristic evaluation changes through the expansion 496 // (you *must not* include any criteria in the heuristic which are modified outside of this method, 497 // otherwise you may see rarely occurring but critical false ordering in the nodes set) 498 searchTree.updatePrepare(node); 499 int horizExp = node.getHorizontalExpansion(); 500 TreeSet<OWLClassExpression> refinements = (TreeSet<OWLClassExpression>) operator.refine(node.getDescription(), horizExp); 501// System.out.println("refinements: " + refinements); 502 node.incHorizontalExpansion(); 503 node.setRefinementCount(refinements.size()); 504// System.out.println("refined node: " + node); 505 searchTree.updateDone(node); 506 MonitorFactory.getTimeMonitor("refineNode").stop(); 507 return refinements; 508 } 509 510 /** 511 * Add node to search tree if it is not too weak. 512 * @return TRUE if node was added and FALSE otherwise 513 */ 514 private boolean addNode(OWLClassExpression description, OENode parentNode) { 515 String sparql_debug_out = ""; 516 if (logger.isTraceEnabled()) sparql_debug_out = "DESC: " + description; 517 MonitorFactory.getTimeMonitor("addNode").start(); 518 519 // redundancy check (return if redundant) 520 boolean nonRedundant = descriptions.add(description); 521 if(!nonRedundant) { 522 logger.trace(sparql_debug, sparql_debug_out + "REDUNDANT"); 523 return false; 524 } 525 526 // check whether the class expression is allowed 527 if(!isDescriptionAllowed(description, parentNode)) { 528 logger.trace(sparql_debug, sparql_debug_out + "NOT ALLOWED"); 529 return false; 530 } 531 532 // quality of class expression (return if too weak) 533 Monitor mon = MonitorFactory.start("lp"); 534 logger.trace(sparql_debug, sparql_debug_out); 535 double accuracy = learningProblem.getAccuracyOrTooWeak(description, noise); 536 logger.trace(sparql_debug, "`acc:"+accuracy); 537 mon.stop(); 538 539 // issue a warning if accuracy is not between 0 and 1 or -1 (too weak) 540 if(accuracy > 1.0 || (accuracy < 0.0 && accuracy != -1)) { 541 throw new RuntimeException("Invalid accuracy value " + accuracy + " for class expression " + description + 542 ". This could be caused by a bug in the heuristic measure and should be reported to the DL-Learner bug tracker."); 543 } 544 545 expressionTests++; 546 547 // return FALSE if 'too weak' 548 if(accuracy == -1) { 549 return false; 550 } 551 552 OENode node = new OENode(description, accuracy); 553 searchTree.addNode(parentNode, node); 554 555 // in some cases (e.g. mutation) fully evaluating even a single class expression is too expensive 556 // due to the high number of examples -- so we just stick to the approximate accuracy 557 if(singleSuggestionMode) { 558 if(accuracy > bestAccuracy) { 559 bestAccuracy = accuracy; 560 bestDescription = description; 561 logger.info("more accurate (" + dfPercent.format(bestAccuracy) + ") class expression found: " + descriptionToString(bestDescription)); // + getTemporaryString(bestDescription)); 562 } 563 return true; 564 } 565 566 // maybe add to best descriptions (method keeps set size fixed); 567 // we need to make sure that this does not get called more often than 568 // necessary since rewriting is expensive 569 boolean isCandidate = !bestEvaluatedDescriptions.isFull(); 570 if(!isCandidate) { 571 EvaluatedDescription<? extends Score> worst = bestEvaluatedDescriptions.getWorst(); 572 double accThreshold = worst.getAccuracy(); 573 isCandidate = 574 (accuracy > accThreshold || 575 (accuracy >= accThreshold && OWLClassExpressionUtils.getLength(description) < worst.getDescriptionLength())); 576 } 577 578 if(isCandidate) { 579 OWLClassExpression niceDescription = rewrite(node.getExpression()); 580 581 if(niceDescription.equals(classToDescribe)) { 582 return false; 583 } 584 585 if(!isDescriptionAllowed(niceDescription, node)) { 586 return false; 587 } 588 589 // another test: none of the other suggested descriptions should be 590 // a subdescription of this one unless accuracy is different 591 // => comment: on the one hand, this appears to be too strict, because once A is a solution then everything containing 592 // A is not a candidate; on the other hand this suppresses many meaningless extensions of A 593 boolean shorterDescriptionExists = false; 594 if(forceMutualDifference) { 595 for(EvaluatedDescription<? extends Score> ed : bestEvaluatedDescriptions.getSet()) { 596 if(Math.abs(ed.getAccuracy()-accuracy) <= 0.00001 && ConceptTransformation.isSubdescription(niceDescription, ed.getDescription())) { 597// System.out.println("shorter: " + ed.getDescription()); 598 shorterDescriptionExists = true; 599 break; 600 } 601 } 602 } 603 604// System.out.println("shorter description? " + shorterDescriptionExists + " nice: " + niceDescription); 605 606 if(!shorterDescriptionExists) { 607 if(!filterFollowsFromKB || !((ClassLearningProblem)learningProblem).followsFromKB(niceDescription)) { 608// System.out.println(node + "->" + niceDescription); 609 bestEvaluatedDescriptions.add(niceDescription, accuracy, learningProblem); 610// System.out.println("acc: " + accuracy); 611// System.out.println(bestEvaluatedDescriptions); 612 } 613 } 614 615// bestEvaluatedDescriptions.add(node.getDescription(), accuracy, learningProblem); 616 617// System.out.println(bestEvaluatedDescriptions.getSet().size()); 618 } 619 620 return true; 621 } 622 623 // checks whether the class expression is allowed 624 private boolean isDescriptionAllowed(OWLClassExpression description, OENode parentNode) { 625 if(isClassLearningProblem) { 626 if(isEquivalenceProblem) { 627 // the class to learn must not appear on the outermost property level 628 if(occursOnFirstLevel(description, classToDescribe)) { 629 return false; 630 } 631 if(occursOnSecondLevel(description, classToDescribe)) { 632 return false; 633 } 634 } else { 635 // none of the superclasses of the class to learn must appear on the 636 // outermost property level 637 TreeSet<OWLClassExpression> toTest = new TreeSet<>(); 638 toTest.add(classToDescribe); 639 while(!toTest.isEmpty()) { 640 OWLClassExpression d = toTest.pollFirst(); 641 if(occursOnFirstLevel(description, d)) { 642 return false; 643 } 644 toTest.addAll(reasoner.getClassHierarchy().getSuperClasses(d)); 645 } 646 } 647 } else if (learningProblem instanceof ClassAsInstanceLearningProblem) { 648 return true; 649 } 650 651 // perform forall sanity tests 652 if (parentNode != null && 653 (ConceptTransformation.getForallOccurences(description) > ConceptTransformation.getForallOccurences(parentNode.getDescription()))) { 654 // we have an additional \forall construct, so we now fetch the contexts 655 // in which it occurs 656 SortedSet<PropertyContext> contexts = ConceptTransformation.getForallContexts(description); 657 SortedSet<PropertyContext> parentContexts = ConceptTransformation.getForallContexts(parentNode.getDescription()); 658 contexts.removeAll(parentContexts); 659// System.out.println("parent description: " + parentNode.getDescription()); 660// System.out.println("description: " + description); 661// System.out.println("contexts: " + contexts); 662 // we now have to perform sanity checks: if \forall is used, then there 663 // should be at least on class instance which has a filler at the given context 664 for(PropertyContext context : contexts) { 665 // transform [r,s] to \exists r.\exists s.\top 666 OWLClassExpression existentialContext = context.toExistentialContext(); 667 boolean fillerFound = false; 668 if(reasoner instanceof SPARQLReasoner) { 669 SortedSet<OWLIndividual> individuals = reasoner.getIndividuals(existentialContext); 670 fillerFound = !Sets.intersection(individuals, examples).isEmpty(); 671 } else { 672 for(OWLIndividual instance : examples) { 673 if(reasoner.hasType(existentialContext, instance)) { 674 fillerFound = true; 675 break; 676 } 677 } 678 } 679 680 // if we do not find a filler, this means that putting \forall at 681 // that position is not meaningful 682 if(!fillerFound) { 683 return false; 684 } 685 } 686 } 687 688 // we do not want to have negations of sibling classes on the outermost level 689 // (they are expressed more naturally by saying that the siblings are disjoint, 690 // so it is reasonable not to include them in solutions) 691// Set<OWLClassExpression> siblingClasses = reasoner.getClassHierarchy().getSiblingClasses(classToDescribe); 692// for now, we just disable negation 693 694 return true; 695 } 696 697 // determine whether a named class occurs on the outermost level, i.e. property depth 0 698 // (it can still be at higher depth, e.g. if intersections are nested in unions) 699 private boolean occursOnFirstLevel(OWLClassExpression description, OWLClassExpression cls) { 700 return !cls.isOWLThing() && (description instanceof OWLNaryBooleanClassExpression && ((OWLNaryBooleanClassExpression) description).getOperands().contains(cls)); 701// return description.containsConjunct(cls) || 702// (description instanceof OWLObjectUnionOf && ((OWLObjectUnionOf) description).getOperands().contains(cls)); 703 } 704 705 // determine whether a named class occurs on the outermost level, i.e. property depth 0 706 // (it can still be at higher depth, e.g. if intersections are nested in unions) 707 private boolean occursOnSecondLevel(OWLClassExpression description, OWLClassExpression cls) { 708// SortedSet<OWLClassExpression> superClasses = reasoner.getSuperClasses(cls); 709// if(description instanceof OWLObjectIntersectionOf) { 710// List<OWLClassExpression> operands = ((OWLObjectIntersectionOf) description).getOperandsAsList(); 711// 712// for (OWLClassExpression op : operands) { 713// if(superClasses.contains(op) || 714// (op instanceof OWLObjectUnionOf && !Sets.intersection(((OWLObjectUnionOf)op).getOperands(),superClasses).isEmpty())) { 715// for (OWLClassExpression op2 : operands) { 716// if((op2 instanceof OWLObjectUnionOf && ((OWLObjectUnionOf)op2).getOperands().contains(cls))) { 717// return true; 718// } 719// } 720// } 721// } 722// 723// for (OWLClassExpression op1 : operands) { 724// for (OWLClassExpression op2 : operands) { 725// if(!op1.isAnonymous() && op2 instanceof OWLObjectUnionOf) { 726// for (OWLClassExpression op3 : ((OWLObjectUnionOf)op2).getOperands()) { 727// if(!op3.isAnonymous()) {// A AND B with Disj(A,B) 728// if(reasoner.isDisjoint(op1.asOWLClass(), op3.asOWLClass())) { 729// return true; 730// } 731// } else {// A AND NOT A 732// if(op3 instanceof OWLObjectComplementOf && ((OWLObjectComplementOf)op3).getOperand().equals(op1)) { 733// return true; 734// } 735// } 736// } 737// } 738// } 739// } 740// } 741 742 return false; 743 } 744 745 private boolean terminationCriteriaSatisfied() { 746 return 747 stop || 748 (maxClassExpressionTestsAfterImprovement != 0 && (expressionTests - expressionTestCountLastImprovement >= maxClassExpressionTestsAfterImprovement)) || 749 (maxClassExpressionTests != 0 && (expressionTests >= maxClassExpressionTests)) || 750 (maxExecutionTimeInSecondsAfterImprovement != 0 && ((System.nanoTime() - nanoStartTime) >= (maxExecutionTimeInSecondsAfterImprovement* 1000000000L))) || 751 (maxExecutionTimeInSeconds != 0 && ((System.nanoTime() - nanoStartTime) >= (maxExecutionTimeInSeconds* 1000000000L))) || 752 (terminateOnNoiseReached && (100*getCurrentlyBestAccuracy()>=100-noisePercentage)) || 753 (stopOnFirstDefinition && (getCurrentlyBestAccuracy() >= 1)); 754 } 755 756 private void reset() { 757 // set all values back to their default values (used for running 758 // the algorithm more than once) 759 searchTree = new SearchTree<>(heuristic); 760 descriptions = new TreeSet<>(); 761 bestEvaluatedDescriptions.getSet().clear(); 762 expressionTests = 0; 763 runtimeVsBestScore.clear(); 764 } 765 766 private void printAlgorithmRunStats() { 767 if (stop) { 768 logger.info("Algorithm stopped ("+expressionTests+" descriptions tested). " + searchTree.size() + " nodes in the search tree.\n"); 769 } else { 770 totalRuntimeNs = System.nanoTime()-nanoStartTime; 771 logger.info("Algorithm terminated successfully (time: " + Helper.prettyPrintNanoSeconds(totalRuntimeNs) + ", "+expressionTests+" descriptions tested, " + searchTree.size() + " nodes in the search tree).\n"); 772 logger.info(reasoner.toString()); 773 } 774 } 775 776 private void showIfBetterSolutionsFound() { 777 if(!singleSuggestionMode && bestEvaluatedDescriptions.getBestAccuracy() > currentHighestAccuracy) { 778 currentHighestAccuracy = bestEvaluatedDescriptions.getBestAccuracy(); 779 expressionTestCountLastImprovement = expressionTests; 780 timeLastImprovement = System.nanoTime(); 781 long durationInMillis = getCurrentRuntimeInMilliSeconds(); 782 String durationStr = getDurationAsString(durationInMillis); 783 784 // track new best accuracy if enabled 785 if(keepTrackOfBestScore) { 786 runtimeVsBestScore.put(getCurrentRuntimeInMilliSeconds(), currentHighestAccuracy); 787 } 788 logger.info("more accurate (" + dfPercent.format(currentHighestAccuracy) + ") class expression found after " + durationStr + ": " + descriptionToString(bestEvaluatedDescriptions.getBest().getDescription())); 789 } 790 } 791 792 private void writeSearchTree(TreeSet<OWLClassExpression> refinements) { 793 StringBuilder treeString = new StringBuilder("best node: ").append(bestEvaluatedDescriptions.getBest()).append("\n"); 794 if (refinements.size() > 1) { 795 treeString.append("all expanded nodes:\n"); 796 for (OWLClassExpression ref : refinements) { 797 treeString.append(" ").append(ref).append("\n"); 798 } 799 } 800 treeString.append(TreeUtils.toTreeString(searchTree)).append("\n"); 801 802 // replace or append 803 if (replaceSearchTree) { 804 Files.createFile(new File(searchTreeFile), treeString.toString()); 805 } else { 806 Files.appendToFile(new File(searchTreeFile), treeString.toString()); 807 } 808 } 809 810 private void updateMinMaxHorizExp(OENode node) { 811 int newHorizExp = node.getHorizontalExpansion(); 812 813 // update maximum value 814 maxHorizExp = Math.max(maxHorizExp, newHorizExp); 815 816 // we just expanded a node with minimum horizontal expansion; 817 // we need to check whether it was the last one 818 if(minHorizExp == newHorizExp - 1) { 819 820 // the best accuracy that a node can achieve 821 double scoreThreshold = heuristic.getNodeScore(node) + 1 - node.getAccuracy(); 822 823 for(OENode n : searchTree.descendingSet()) { 824 if(n != node) { 825 if(n.getHorizontalExpansion() == minHorizExp) { 826 // we can stop instantly when another node with min. 827 return; 828 } 829 if(heuristic.getNodeScore(n) < scoreThreshold) { 830 // we can stop traversing nodes when their score is too low 831 break; 832 } 833 } 834 } 835 836 // inc. minimum since we found no other node which also has min. horiz. exp. 837 minHorizExp++; 838 839// System.out.println("minimum horizontal expansion is now " + minHorizExp); 840 } 841 } 842 843 @Override 844 public OWLClassExpression getCurrentlyBestDescription() { 845 EvaluatedDescription<? extends Score> ed = getCurrentlyBestEvaluatedDescription(); 846 return ed == null ? null : ed.getDescription(); 847 } 848 849 @Override 850 public List<OWLClassExpression> getCurrentlyBestDescriptions() { 851 return bestEvaluatedDescriptions.toDescriptionList(); 852 } 853 854 @Override 855 public EvaluatedDescription<? extends Score> getCurrentlyBestEvaluatedDescription() { 856 return bestEvaluatedDescriptions.getBest(); 857 } 858 859 @Override 860 public NavigableSet<? extends EvaluatedDescription<? extends Score>> getCurrentlyBestEvaluatedDescriptions() { 861 return bestEvaluatedDescriptions.getSet(); 862 } 863 864 public double getCurrentlyBestAccuracy() { 865 return bestEvaluatedDescriptions.getBest().getAccuracy(); 866 } 867 868 @Override 869 public boolean isRunning() { 870 return isRunning; 871 } 872 873 @Override 874 public void stop() { 875 stop = true; 876 } 877 878 public int getMaximumHorizontalExpansion() { 879 return maxHorizExp; 880 } 881 882 public int getMinimumHorizontalExpansion() { 883 return minHorizExp; 884 } 885 886 /** 887 * @return the expressionTests 888 */ 889 public int getClassExpressionTests() { 890 return expressionTests; 891 } 892 893 public LengthLimitedRefinementOperator getOperator() { 894 return operator; 895 } 896 897 @Autowired(required=false) 898 public void setOperator(LengthLimitedRefinementOperator operator) { 899 this.operator = operator; 900 } 901 902 public OWLClassExpression getStartClass() { 903 return startClass; 904 } 905 906 public void setStartClass(OWLClassExpression startClass) { 907 this.startClass = startClass; 908 } 909 910 public boolean isWriteSearchTree() { 911 return writeSearchTree; 912 } 913 914 public void setWriteSearchTree(boolean writeSearchTree) { 915 this.writeSearchTree = writeSearchTree; 916 } 917 918 public String getSearchTreeFile() { 919 return searchTreeFile; 920 } 921 922 public void setSearchTreeFile(String searchTreeFile) { 923 this.searchTreeFile = searchTreeFile; 924 } 925 926 public int getMaxNrOfResults() { 927 return maxNrOfResults; 928 } 929 930 public void setMaxNrOfResults(int maxNrOfResults) { 931 this.maxNrOfResults = maxNrOfResults; 932 } 933 934 public double getNoisePercentage() { 935 return noisePercentage; 936 } 937 938 public void setNoisePercentage(double noisePercentage) { 939 this.noisePercentage = noisePercentage; 940 } 941 942 public boolean isFilterDescriptionsFollowingFromKB() { 943 return filterDescriptionsFollowingFromKB; 944 } 945 946 public void setFilterDescriptionsFollowingFromKB(boolean filterDescriptionsFollowingFromKB) { 947 this.filterDescriptionsFollowingFromKB = filterDescriptionsFollowingFromKB; 948 } 949 950 public boolean isReplaceSearchTree() { 951 return replaceSearchTree; 952 } 953 954 public void setReplaceSearchTree(boolean replaceSearchTree) { 955 this.replaceSearchTree = replaceSearchTree; 956 } 957 958 public boolean isTerminateOnNoiseReached() { 959 return terminateOnNoiseReached; 960 } 961 962 public void setTerminateOnNoiseReached(boolean terminateOnNoiseReached) { 963 this.terminateOnNoiseReached = terminateOnNoiseReached; 964 } 965 966 public boolean isReuseExistingDescription() { 967 return reuseExistingDescription; 968 } 969 970 public void setReuseExistingDescription(boolean reuseExistingDescription) { 971 this.reuseExistingDescription = reuseExistingDescription; 972 } 973 974 public AbstractHeuristic getHeuristic() { 975 return heuristic; 976 } 977 978 @Autowired(required=false) 979 public void setHeuristic(AbstractHeuristic heuristic) { 980 this.heuristic = heuristic; 981 } 982 983 public int getMaxExecutionTimeInSecondsAfterImprovement() { 984 return maxExecutionTimeInSecondsAfterImprovement; 985 } 986 987 public void setMaxExecutionTimeInSecondsAfterImprovement( 988 int maxExecutionTimeInSecondsAfterImprovement) { 989 this.maxExecutionTimeInSecondsAfterImprovement = maxExecutionTimeInSecondsAfterImprovement; 990 } 991 992 public boolean isSingleSuggestionMode() { 993 return singleSuggestionMode; 994 } 995 996 public void setSingleSuggestionMode(boolean singleSuggestionMode) { 997 this.singleSuggestionMode = singleSuggestionMode; 998 } 999 1000 public int getMaxClassExpressionTests() { 1001 return maxClassExpressionTests; 1002 } 1003 1004 public void setMaxClassExpressionTests(int maxClassExpressionTests) { 1005 this.maxClassExpressionTests = maxClassExpressionTests; 1006 } 1007 1008 public int getMaxClassExpressionTestsAfterImprovement() { 1009 return maxClassExpressionTestsAfterImprovement; 1010 } 1011 1012 public void setMaxClassExpressionTestsAfterImprovement( 1013 int maxClassExpressionTestsAfterImprovement) { 1014 this.maxClassExpressionTestsAfterImprovement = maxClassExpressionTestsAfterImprovement; 1015 } 1016 1017 public double getMaxDepth() { 1018 return maxDepth; 1019 } 1020 1021 public void setMaxDepth(double maxDepth) { 1022 this.maxDepth = maxDepth; 1023 } 1024 1025 public boolean isStopOnFirstDefinition() { 1026 return stopOnFirstDefinition; 1027 } 1028 1029 public void setStopOnFirstDefinition(boolean stopOnFirstDefinition) { 1030 this.stopOnFirstDefinition = stopOnFirstDefinition; 1031 } 1032 1033 public long getTotalRuntimeNs() { 1034 return totalRuntimeNs; 1035 } 1036 1037 /** 1038 * @return the expandAccuracy100Nodes 1039 */ 1040 public boolean isExpandAccuracy100Nodes() { 1041 return expandAccuracy100Nodes; 1042 } 1043 1044 /** 1045 * @param expandAccuracy100Nodes the expandAccuracy100Nodes to set 1046 */ 1047 public void setExpandAccuracy100Nodes(boolean expandAccuracy100Nodes) { 1048 this.expandAccuracy100Nodes = expandAccuracy100Nodes; 1049 } 1050 1051 /** 1052 * Whether to keep track of the best score during the algorithm run. 1053 * 1054 * @param keepTrackOfBestScore 1055 */ 1056 public void setKeepTrackOfBestScore(boolean keepTrackOfBestScore) { 1057 this.keepTrackOfBestScore = keepTrackOfBestScore; 1058 } 1059 1060 /** 1061 * @return a map containing time points at which a hypothesis with a better score than before has been found 1062 */ 1063 public SortedMap<Long, Double> getRuntimeVsBestScore() { 1064 return runtimeVsBestScore; 1065 } 1066 1067 /** 1068 * Return a map that contains 1069 * <ol> 1070 * <li>entries with time points at which a hypothesis with a better score than before has been found</li> 1071 * <li>entries with the current best score for each defined interval time point</li> 1072 * </ol> 1073 * 1074 * @param ticksIntervalTimeValue at which time point the current best score is tracked periodically 1075 * @param ticksIntervalTimeUnit the time unit of the periodic time point values 1076 * 1077 * @return the map 1078 * 1079 */ 1080 public SortedMap<Long, Double> getRuntimeVsBestScore(long ticksIntervalTimeValue, TimeUnit ticksIntervalTimeUnit) { 1081 SortedMap<Long, Double> map = new TreeMap<>(runtimeVsBestScore); 1082 1083 // add entries for fixed time points if enabled 1084 if(ticksIntervalTimeValue > 0) { 1085 long ticksIntervalInMs = TimeUnit.MILLISECONDS.convert(ticksIntervalTimeValue, ticksIntervalTimeUnit); 1086 1087 // add t = 0 -> 0 1088 map.put(0L, 0d); 1089 1090 for(long t = ticksIntervalInMs; t <= TimeUnit.SECONDS.toMillis(maxExecutionTimeInSeconds); t += ticksIntervalInMs) { 1091 // add value of last entry before this time point 1092 map.put(t, map.get(runtimeVsBestScore.headMap(t).lastKey())); 1093 } 1094 1095 // add entry for t = totalRuntime 1096 long totalRuntimeMs = Math.min(TimeUnit.SECONDS.toMillis(maxExecutionTimeInSeconds), TimeUnit.NANOSECONDS.toMillis(totalRuntimeNs)); 1097 map.put(totalRuntimeMs, map.get(map.lastKey())); 1098 } 1099 1100 return map; 1101 } 1102 1103 /* (non-Javadoc) 1104 * @see java.lang.Object#clone() 1105 */ 1106 @Override 1107 public Object clone() throws CloneNotSupportedException { 1108 return new CELOE(this); 1109 } 1110 1111 public static void main(String[] args) throws Exception{ 1112// File file = new File("../examples/swore/swore.rdf"); 1113// OWLClass classToDescribe = new OWLClassImpl(IRI.create("http://ns.softwiki.de/req/CustomerRequirement")); 1114 File file = new File("../examples/father.owl"); 1115 OWLClass classToDescribe = new OWLClassImpl(IRI.create("http://example.com/father#male")); 1116 1117 OWLOntology ontology = OWLManager.createOWLOntologyManager().loadOntologyFromOntologyDocument(file); 1118 1119 AbstractKnowledgeSource ks = new OWLAPIOntology(ontology); 1120 ks.init(); 1121 1122 OWLAPIReasoner baseReasoner = new OWLAPIReasoner(ks); 1123 baseReasoner.setReasonerImplementation(ReasonerImplementation.HERMIT); 1124 baseReasoner.init(); 1125 ClosedWorldReasoner rc = new ClosedWorldReasoner(ks); 1126 rc.setReasonerComponent(baseReasoner); 1127 rc.init(); 1128 1129 ClassLearningProblem lp = new ClassLearningProblem(rc); 1130// lp.setEquivalence(false); 1131 lp.setClassToDescribe(classToDescribe); 1132 lp.init(); 1133 1134 RhoDRDown op = new RhoDRDown(); 1135 op.setReasoner(rc); 1136 op.setUseNegation(false); 1137 op.setUseHasValueConstructor(false); 1138 op.setUseCardinalityRestrictions(true); 1139 op.setUseExistsConstructor(true); 1140 op.setUseAllConstructor(true); 1141 op.init(); 1142 1143 1144 1145 //(male â (â hasChild.â¤)) â (â hasChild.(â hasChild.male)) 1146 OWLDataFactory df = new OWLDataFactoryImpl(); 1147 OWLClass male = df.getOWLClass(IRI.create("http://example.com/father#male")); 1148 OWLClassExpression ce = df.getOWLObjectIntersectionOf( 1149 df.getOWLObjectUnionOf( 1150 male, 1151 df.getOWLObjectIntersectionOf( 1152 male, male), 1153 df.getOWLObjectSomeValuesFrom( 1154 df.getOWLObjectProperty(IRI.create("http://example.com/father#hasChild")), 1155 df.getOWLThing()) 1156 ), 1157 df.getOWLObjectAllValuesFrom( 1158 df.getOWLObjectProperty(IRI.create("http://example.com/father#hasChild")), 1159 df.getOWLThing() 1160 ) 1161 ); 1162 System.out.println(ce); 1163 OWLClassExpressionMinimizer min = new OWLClassExpressionMinimizer(df, rc); 1164 ce = min.minimizeClone(ce); 1165 System.out.println(ce); 1166 1167 CELOE alg = new CELOE(lp, rc); 1168 alg.setMaxExecutionTimeInSeconds(10); 1169 alg.setOperator(op); 1170 alg.setWriteSearchTree(true); 1171 alg.setSearchTreeFile("log/search-tree.log"); 1172 alg.setReplaceSearchTree(true); 1173 alg.init(); 1174 alg.setKeepTrackOfBestScore(true); 1175 1176 alg.start(); 1177 1178 SortedMap<Long, Double> map = alg.getRuntimeVsBestScore(1, TimeUnit.SECONDS); 1179 System.out.println(MapUtils.asTSV(map, "runtime", "best_score")); 1180 1181 } 1182 1183}