From: <lor...@us...> - 2013-01-22 21:41:24
|
Revision: 3889 http://dl-learner.svn.sourceforge.net/dl-learner/?rev=3889&view=rev Author: lorenz_b Date: 2013-01-22 21:41:16 +0000 (Tue, 22 Jan 2013) Log Message: ----------- Added options to set prefixes in QTL output and to enable numeric SPARQL FILTER expression learning. Modified Paths: -------------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2013-01-22 13:22:29 UTC (rev 3888) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2013-01-22 21:41:16 UTC (rev 3889) @@ -22,9 +22,11 @@ import java.util.ArrayList; import java.util.Collection; import java.util.Collections; +import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; +import java.util.Map; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; @@ -116,6 +118,8 @@ private SortedSet<String> lggInstances; private Set<String> objectNamespacesToIgnore = new HashSet<String>(); + private Map<String, String> prefixes = new HashMap<String, String>(); + private boolean enableNumericLiteralFilters = false; public static Collection<ConfigOption<?>> createConfigOptions() { Collection<ConfigOption<?>> options = new LinkedList<ConfigOption<?>>(); @@ -125,7 +129,6 @@ } public QTL() { - } public QTL(AbstractLearningProblem learningProblem, SparqlEndpointKS endpointKS) throws LearningProblemUnsupportedException{ @@ -219,6 +222,14 @@ return maxQueryTreeDepth; } + public void setPrefixes(Map<String, String> prefixes) { + this.prefixes = prefixes; + } + + public Map<String, String> getPrefixes() { + return prefixes; + } + public String getSPARQLQuery(){ if(lgg == null){ lgg = lggGenerator.getLGG(getQueryTrees(posExamples)); @@ -256,6 +267,7 @@ if(logger.isDebugEnabled()){ logger.debug("Tree for resource " + resource); logger.debug(tree.getStringRepresentation()); + } trees.add(tree); } @@ -330,9 +342,17 @@ if(logger.isDebugEnabled()){ logger.debug("LGG: \n" + lgg.getStringRepresentation()); } - logger.info(lgg.toSPARQLQuery()); + logger.info(lgg.toSPARQLQueryString(enableNumericLiteralFilters, prefixes)); } - + + public void setEnableNumericLiteralFilters(boolean enableNumericLiteralFilters) { + this.enableNumericLiteralFilters = enableNumericLiteralFilters; + } + + public boolean isEnableNumericLiteralFilters() { + return enableNumericLiteralFilters; + } + @Override public List<String> getCurrentlyBestSPARQLQueries(int nrOfSPARQLQueries) { return Collections.singletonList(getBestSPARQLQuery()); Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2013-01-22 13:22:29 UTC (rev 3888) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2013-01-22 21:41:16 UTC (rev 3889) @@ -22,6 +22,7 @@ import java.io.PrintWriter; import java.util.Comparator; import java.util.List; +import java.util.Map; import java.util.Set; import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl; @@ -131,6 +132,8 @@ String toSPARQLQueryString(boolean filtered); + String toSPARQLQueryString(boolean filtered, Map<String, String> prefixMap); + Query toSPARQLQuery(); int getTriplePatternCount(); Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2013-01-22 13:22:29 UTC (rev 3888) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2013-01-22 21:41:16 UTC (rev 3889) @@ -31,6 +31,7 @@ import java.util.LinkedList; import java.util.List; import java.util.Map; +import java.util.Map.Entry; import java.util.Set; import java.util.TreeSet; import java.util.regex.Pattern; @@ -712,6 +713,11 @@ @Override public String toSPARQLQueryString(boolean filtered) { + return toSPARQLQueryString(filtered, Collections.<String, String>emptyMap()); + } + + @Override + public String toSPARQLQueryString(boolean filtered, Map<String, String> prefixMap) { if(children.isEmpty()){ return "SELECT ?x0 WHERE {?x0 ?y ?z.}"; } @@ -724,7 +730,16 @@ sb.append(filter).append("\n"); } sb.append("}"); - return sb.toString(); + Query query = QueryFactory.create(sb.toString(), Syntax.syntaxARQ); + query.setPrefix("rdf", "http://www.w3.org/1999/02/22-rdf-syntax-ns#"); + query.setPrefix("rdfs", "http://www.w3.org/2000/01/rdf-schema#"); + + for (Entry<String, String> entry : prefixMap.entrySet()) { + String key = entry.getKey(); + String value = entry.getValue(); + query.setPrefix(key, value); + } + return query.toString(); } private void buildSPARQLQueryString(QueryTree<N> tree, StringBuilder sb, boolean filtered, List<String> filters){ @@ -785,7 +800,7 @@ l = iter.next(); if(l.getDatatype() == XSDDatatype.XSDinteger || l.getDatatype() == XSDDatatype.XSDint){ min = (l.getInt() < min.getInt()) ? l : min; - } else if(l.getDatatype() == XSDDatatype.XSDdouble){ + } else if(l.getDatatype() == XSDDatatype.XSDdouble || l.getDatatype() == XSDDatatype.XSDdecimal){ min = (l.getDouble() < min.getDouble()) ? l : min; } else if(l.getDatatype() == XSDDatatype.XSDdate){ min = (DatatypeConverter.parseDate(l.getLexicalForm()).compareTo(DatatypeConverter.parseDate(min.getLexicalForm())) == -1) ? l : min; @@ -802,7 +817,7 @@ l = iter.next(); if(l.getDatatype() == XSDDatatype.XSDinteger || l.getDatatype() == XSDDatatype.XSDint){ max = (l.getInt() > max.getInt()) ? l : max; - } else if(l.getDatatype() == XSDDatatype.XSDdouble){ + } else if(l.getDatatype() == XSDDatatype.XSDdouble || l.getDatatype() == XSDDatatype.XSDdecimal){ max = (l.getDouble() > max.getDouble()) ? l : max; } else if(l.getDatatype() == XSDDatatype.XSDdate){ max = (DatatypeConverter.parseDate(l.getLexicalForm()).compareTo(DatatypeConverter.parseDate(max.getLexicalForm())) == 1) ? l : max; Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java 2013-01-22 13:22:29 UTC (rev 3888) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java 2013-01-22 21:41:16 UTC (rev 3889) @@ -247,7 +247,8 @@ if(lit.getDatatype() == XSDDatatype.XSDinteger || lit.getDatatype() == XSDDatatype.XSDdouble || lit.getDatatype() == XSDDatatype.XSDdate - || lit.getDatatype() == XSDDatatype.XSDint){ + || lit.getDatatype() == XSDDatatype.XSDint + || lit.getDatatype() == XSDDatatype.XSDdecimal){ subTree.addLiteral(lit); } tree.addChild(subTree, st.getPredicate().toString()); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <lor...@us...> - 2013-04-12 10:57:06
|
Revision: 3921 http://sourceforge.net/p/dl-learner/code/3921 Author: lorenz_b Date: 2013-04-12 10:57:03 +0000 (Fri, 12 Apr 2013) Log Message: ----------- Updated QTL. Modified Paths: -------------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/Filters.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/QuestionBasedQueryTreeFilter.java Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2013-04-12 10:21:20 UTC (rev 3920) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2013-04-12 10:57:03 UTC (rev 3921) @@ -20,6 +20,7 @@ package org.dllearner.algorithms.qtl; import java.util.ArrayList; +import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.HashMap; @@ -40,6 +41,7 @@ import org.dllearner.algorithms.qtl.exception.NegativeTreeCoverageExecption; import org.dllearner.algorithms.qtl.exception.TimeOutException; import org.dllearner.algorithms.qtl.filters.QueryTreeFilter; +import org.dllearner.algorithms.qtl.filters.QuestionBasedQueryTreeFilter; import org.dllearner.algorithms.qtl.operations.NBR; import org.dllearner.algorithms.qtl.operations.lgg.LGGGenerator; import org.dllearner.algorithms.qtl.operations.lgg.LGGGeneratorImpl; @@ -365,7 +367,7 @@ if(logger.isDebugEnabled()){ logger.debug("LGG: \n" + lgg.getStringRepresentation()); } - logger.info(lgg.toSPARQLQueryString(enableNumericLiteralFilters, prefixes)); + logger.info(lgg.toSPARQLQueryString(true, enableNumericLiteralFilters, prefixes)); } public void setEnableNumericLiteralFilters(boolean enableNumericLiteralFilters) { @@ -429,6 +431,7 @@ PosOnlyLP lp = new PosOnlyLP(); lp.setPositiveExamples(Helper.getIndividualSet(positiveExamples)); QTL qtl = new QTL(lp, ks); + qtl.addQueryTreeFilter(new QuestionBasedQueryTreeFilter(Arrays.asList("soccer club", "Premier League"))); qtl.init(); qtl.start(); String query = qtl.getBestSPARQLQuery(); Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2013-04-12 10:21:20 UTC (rev 3920) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2013-04-12 10:57:03 UTC (rev 3921) @@ -130,9 +130,9 @@ String toSPARQLQueryString(); - String toSPARQLQueryString(boolean filtered); + String toSPARQLQueryString(boolean filterMeaninglessProperties, boolean useNumericalFilters); - String toSPARQLQueryString(boolean filtered, Map<String, String> prefixMap); + String toSPARQLQueryString(boolean filterMeaninglessProperties, boolean useNumericalFilters, Map<String, String> prefixMap); Query toSPARQLQuery(); Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2013-04-12 10:21:20 UTC (rev 3920) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2013-04-12 10:57:03 UTC (rev 3921) @@ -703,7 +703,7 @@ StringBuilder sb = new StringBuilder(); sb.append("SELECT DISTINCT ?x0 WHERE {\n"); List<String> filters = new ArrayList<String>(); - buildSPARQLQueryString(this, sb, false, filters); + buildSPARQLQueryString(this, sb, true, false, filters); for(String filter : filters){ sb.append(filter).append("\n"); } @@ -711,13 +711,12 @@ return sb.toString(); } - @Override - public String toSPARQLQueryString(boolean filtered) { - return toSPARQLQueryString(filtered, Collections.<String, String>emptyMap()); + public String toSPARQLQueryString(boolean filterMeaninglessProperties, boolean useNumericalFilters) { + return toSPARQLQueryString(filterMeaninglessProperties, useNumericalFilters, Collections.<String, String>emptyMap()); } @Override - public String toSPARQLQueryString(boolean filtered, Map<String, String> prefixMap) { + public String toSPARQLQueryString(boolean filterMeaninglessProperties, boolean useNumericalFilters, Map<String, String> prefixMap) { if(children.isEmpty()){ return "SELECT ?x0 WHERE {?x0 ?y ?z.}"; } @@ -725,11 +724,11 @@ StringBuilder sb = new StringBuilder(); List<String> filters = new ArrayList<String>(); sb.append("SELECT DISTINCT ?x0 WHERE {\n"); - buildSPARQLQueryString(this, sb, filtered, filters); + buildSPARQLQueryString(this, sb, filterMeaninglessProperties, useNumericalFilters, filters); for(String filter : filters){ sb.append(filter).append("\n"); } - sb.append("}"); + sb.append("}");System.out.println(sb.toString()); Query query = QueryFactory.create(sb.toString(), Syntax.syntaxARQ); query.setPrefix("rdf", "http://www.w3.org/1999/02/22-rdf-syntax-ns#"); query.setPrefix("rdfs", "http://www.w3.org/2000/01/rdf-schema#"); @@ -742,12 +741,14 @@ return query.toString(); } - private void buildSPARQLQueryString(QueryTree<N> tree, StringBuilder sb, boolean filtered, List<String> filters){ + private void buildSPARQLQueryString(QueryTree<N> tree, StringBuilder sb, boolean filterMeaninglessProperties, boolean useNumericalFilters, List<String> filters){ Object subject = null; if(tree.getUserObject().equals("?")){ subject = "?x" + cnt++; - if(tree.isLiteralNode() && !tree.getLiterals().isEmpty()){ - filters.add(getFilter(subject.toString(), tree.getLiterals())); + if(useNumericalFilters){ + if(tree.isLiteralNode() && !tree.getLiterals().isEmpty()){ + filters.add(getFilter(subject.toString(), tree.getLiterals())); + } } } else { subject = "<" + tree.getUserObject() + ">"; @@ -757,7 +758,7 @@ if(!tree.isLeaf()){ for(QueryTree<N> child : tree.getChildren()){ predicate = tree.getEdge(child); - if(filtered){ + if(filterMeaninglessProperties){ if(Filters.getAllFilterProperties().contains(predicate.toString())){ continue; } @@ -771,7 +772,7 @@ } sb.append(subject).append(" <").append(predicate).append("> ").append(object).append(".\n"); if(!objectIsResource){ - buildSPARQLQueryString(child, sb, filtered, filters); + buildSPARQLQueryString(child, sb, filterMeaninglessProperties, useNumericalFilters, filters); } } } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/Filters.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/Filters.java 2013-04-12 10:21:20 UTC (rev 3920) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/Filters.java 2013-04-12 10:57:03 UTC (rev 3921) @@ -57,6 +57,7 @@ filters.add(FOAF.name.toString()); filters.add(FOAF.firstName.toString()); // filters.add(FOAF.givenname.toString()); + filters.add(FOAF.primaryTopic.toString()); return filters; } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/QuestionBasedQueryTreeFilter.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/QuestionBasedQueryTreeFilter.java 2013-04-12 10:21:20 UTC (rev 3920) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/filters/QuestionBasedQueryTreeFilter.java 2013-04-12 10:57:03 UTC (rev 3921) @@ -1,5 +1,6 @@ package org.dllearner.algorithms.qtl.filters; +import java.util.Collection; import java.util.Collections; import java.util.HashSet; import java.util.Set; @@ -15,7 +16,7 @@ public class QuestionBasedQueryTreeFilter implements QueryTreeFilter{ -private Set<String> questionWords; + private Collection<String> questionWords; private AbstractStringMetric qGramMetric; private AbstractStringMetric levensteinMetric; @@ -25,7 +26,7 @@ private int topK = 3; private double topKSumThreshold = 0.8; - public QuestionBasedQueryTreeFilter(Set<String> questionWords){ + public QuestionBasedQueryTreeFilter(Collection<String> questionWords){ this.questionWords = questionWords; qGramMetric = new QGramsDistance(); levensteinMetric = new Levenshtein(); @@ -39,7 +40,7 @@ return copy; } - public Set<String> getQuestionWords(){ + public Collection<String> getQuestionWords(){ return questionWords; } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <lor...@us...> - 2014-04-30 11:43:26
|
Revision: 4252 http://sourceforge.net/p/dl-learner/code/4252 Author: lorenz_b Date: 2014-04-30 11:43:20 +0000 (Wed, 30 Apr 2014) Log Message: ----------- Added new version of QTL. Modified Paths: -------------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/cache/QueryTreeCache.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/NBR.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/PostLGG.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java Added Paths: ----------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2014-04-23 10:47:59 UTC (rev 4251) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -19,6 +19,7 @@ */ package org.dllearner.algorithms.qtl; +import java.sql.SQLException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; @@ -31,7 +32,15 @@ import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; +import java.util.concurrent.TimeUnit; +import org.aksw.jena_sparql_api.cache.core.QueryExecutionFactoryCacheEx; +import org.aksw.jena_sparql_api.cache.extra.CacheCoreEx; +import org.aksw.jena_sparql_api.cache.extra.CacheCoreH2; +import org.aksw.jena_sparql_api.cache.extra.CacheEx; +import org.aksw.jena_sparql_api.cache.extra.CacheExImpl; +import org.aksw.jena_sparql_api.http.QueryExecutionFactoryHttp; +import org.aksw.jena_sparql_api.model.QueryExecutionFactoryModel; import org.apache.commons.collections15.ListUtils; import org.apache.log4j.Logger; import org.dllearner.algorithms.qtl.cache.QueryTreeCache; @@ -46,34 +55,36 @@ import org.dllearner.algorithms.qtl.operations.lgg.LGGGenerator; import org.dllearner.algorithms.qtl.operations.lgg.LGGGeneratorImpl; import org.dllearner.algorithms.qtl.util.SPARQLEndpointEx; -import org.dllearner.core.AbstractComponent; +import org.dllearner.core.AbstractCELA; import org.dllearner.core.AbstractLearningProblem; import org.dllearner.core.ComponentAnn; -import org.dllearner.core.ComponentManager; +import org.dllearner.core.EvaluatedDescription; import org.dllearner.core.LearningProblem; import org.dllearner.core.LearningProblemUnsupportedException; import org.dllearner.core.SparqlQueryLearningAlgorithm; import org.dllearner.core.options.CommonConfigOptions; import org.dllearner.core.options.ConfigOption; import org.dllearner.core.options.IntegerConfigOption; +import org.dllearner.core.owl.Description; import org.dllearner.core.owl.Individual; import org.dllearner.kb.LocalModelBasedSparqlEndpointKS; import org.dllearner.kb.SparqlEndpointKS; import org.dllearner.kb.sparql.CachingConciseBoundedDescriptionGenerator; import org.dllearner.kb.sparql.ConciseBoundedDescriptionGenerator; import org.dllearner.kb.sparql.ConciseBoundedDescriptionGeneratorImpl; -import org.dllearner.kb.sparql.ExtractionDBCache; import org.dllearner.kb.sparql.SparqlEndpoint; -import org.dllearner.kb.sparql.SparqlQuery; import org.dllearner.learningproblems.PosNegLP; import org.dllearner.learningproblems.PosOnlyLP; import org.dllearner.utilities.Helper; +import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; +import org.dllearner.utilities.owl.OWLAPIDescriptionConvertVisitor; +import org.semanticweb.owlapi.owllink.parser.OWLlinkDescriptionElementHandler; import org.springframework.beans.factory.annotation.Autowired; -import com.hp.hpl.jena.query.QueryExecutionFactory; +import com.google.common.collect.Sets; +import com.hp.hpl.jena.query.QueryExecution; import com.hp.hpl.jena.query.QuerySolution; import com.hp.hpl.jena.query.ResultSet; -import com.hp.hpl.jena.query.ResultSetRewindable; import com.hp.hpl.jena.rdf.model.Model; import com.hp.hpl.jena.rdf.model.Statement; import com.hp.hpl.jena.rdf.model.StmtIterator; @@ -89,7 +100,7 @@ * */ @ComponentAnn(name="query tree learner", shortName="qtl", version=0.8) -public class QTL extends AbstractComponent implements SparqlQueryLearningAlgorithm { +public class QTL extends AbstractCELA implements SparqlQueryLearningAlgorithm { private static final Logger logger = Logger.getLogger(QTL.class); @@ -99,7 +110,8 @@ private SparqlEndpoint endpoint; private Model model; - private ExtractionDBCache cache; + private org.aksw.jena_sparql_api.core.QueryExecutionFactory qef; + private String cacheDirectory; private QueryTreeCache treeCache; @@ -123,6 +135,7 @@ private SortedSet<String> lggInstances; private Set<String> objectNamespacesToIgnore = new HashSet<String>(); + private Set<String> allowedNamespaces = new HashSet<String>(); private Map<String, String> prefixes = new HashMap<String, String>(); private boolean enableNumericLiteralFilters = false; @@ -137,52 +150,44 @@ } public QTL(AbstractLearningProblem learningProblem, SparqlEndpointKS endpointKS) throws LearningProblemUnsupportedException{ - if(!(learningProblem instanceof PosOnlyLP || learningProblem instanceof PosNegLP)){ - throw new LearningProblemUnsupportedException(learningProblem.getClass(), getClass()); - } - this.learningProblem = learningProblem; - this.endpointKS = endpointKS; - -// this.configurator = new QTLConfigurator(this); + this(learningProblem, endpointKS, null); } - public QTL(AbstractLearningProblem learningProblem, SparqlEndpointKS endpointKS, ExtractionDBCache cache) throws LearningProblemUnsupportedException{ + public QTL(AbstractLearningProblem learningProblem, SparqlEndpointKS endpointKS, String cacheDirectory) throws LearningProblemUnsupportedException{ if(!(learningProblem instanceof PosOnlyLP || learningProblem instanceof PosNegLP)){ throw new LearningProblemUnsupportedException(learningProblem.getClass(), getClass()); } this.learningProblem = learningProblem; this.endpointKS = endpointKS; - this.cache = cache; - -// this.configurator = new QTLConfigurator(this); + this.cacheDirectory = cacheDirectory; } - public QTL(SPARQLEndpointEx endpoint, ExtractionDBCache cache) { + public QTL(SPARQLEndpointEx endpoint, String cacheDirectory) { this.endpoint = endpoint; - this.cache = cache; + this.cacheDirectory = cacheDirectory; treeCache = new QueryTreeCache(); - cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, cache)); + cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, cacheDirectory)); cbdGenerator.setRecursionDepth(maxQueryTreeDepth); lggGenerator = new LGGGeneratorImpl<String>(); - nbr = new NBR<String>(endpoint, cache); + nbr = new NBR<String>(endpoint, cacheDirectory); nbr.setMaxExecutionTimeInSeconds(maxExecutionTimeInSeconds); posExampleTrees = new ArrayList<QueryTree<String>>(); negExampleTrees = new ArrayList<QueryTree<String>>(); } - public QTL(SparqlEndpointKS endpointKS, ExtractionDBCache cache) { + public QTL(SparqlEndpointKS endpointKS, String cacheDirectory) { this.endpointKS = endpointKS; - this.cache = cache; + this.cacheDirectory = cacheDirectory; treeCache = new QueryTreeCache(); - cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, cache)); + cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, cacheDirectory)); cbdGenerator.setRecursionDepth(maxQueryTreeDepth); lggGenerator = new LGGGeneratorImpl<String>(); - nbr = new NBR<String>(endpoint, cache); + nbr = new NBR<String>(endpoint, cacheDirectory); nbr.setMaxExecutionTimeInSeconds(maxExecutionTimeInSeconds); posExampleTrees = new ArrayList<QueryTree<String>>(); @@ -369,20 +374,15 @@ private SortedSet<String> getResources(QueryTree<String> tree){ SortedSet<String> resources = new TreeSet<String>(); String query = getDistinctSPARQLQuery(tree); - ResultSet rs; - if(endpoint != null){ - rs = SparqlQuery.convertJSONtoResultSet(cache.executeSelectQuery(endpoint, query)); - } else { - rs = QueryExecutionFactory.create(query, model).execSelect(); - } + QueryExecution qe = qef.createQueryExecution(query); + ResultSet rs = qe.execSelect(); - String uri; QuerySolution qs; while(rs.hasNext()){ qs = rs.next(); - uri = qs.getResource("x0").getURI(); - resources.add(uri); + resources.add(qs.getResource("x0").getURI()); } + qe.close(); return resources; } @@ -392,12 +392,30 @@ return query; } +// @Override +// public void start(){ +// generatePositiveExampleTrees(); +// +// lgg = lggGenerator.getLGG(posExampleTrees); +// +// if(queryTreeFilter != null){ +// lgg = queryTreeFilter.getFilteredQueryTree(lgg); +// } +// if(logger.isDebugEnabled()){ +// logger.debug("LGG: \n" + lgg.getStringRepresentation()); +// } +// if(logger.isInfoEnabled()){ +// logger.info("Generated SPARQL query:\n" + lgg.toSPARQLQueryString(true, enableNumericLiteralFilters, prefixes)); +// } +// } + @Override public void start(){ + //build the query trees for the positive examples generatePositiveExampleTrees(); + //compute the LGG lgg = lggGenerator.getLGG(posExampleTrees); - if(queryTreeFilter != null){ lgg = queryTreeFilter.getFilteredQueryTree(lgg); } @@ -405,8 +423,36 @@ logger.debug("LGG: \n" + lgg.getStringRepresentation()); } if(logger.isInfoEnabled()){ - logger.info(lgg.toSPARQLQueryString(true, enableNumericLiteralFilters, prefixes)); + logger.info("Generated SPARQL query:\n" + lgg.toSPARQLQueryString(true, enableNumericLiteralFilters, prefixes)); } + + //build the query trees for the negative examples + if(!negExamples.isEmpty()){ + generateNegativeExampleTrees(); + + try { + //check if the LGG covers a negative example + int index = coversNegativeQueryTree(lgg); + if(index != -1){ + throw new NegativeTreeCoverageExecption(negExamples.get(index)); + } + + lggInstances = getResources(lgg); + nbr.setLGGInstances(lggInstances); + + String question; + if(negExamples.isEmpty()){ + question = nbr.getQuestion(lgg, negExampleTrees, getKnownResources()); + } else { + question = nbr.getQuestion(lgg, negExampleTrees, getKnownResources()); + } + logger.info("Question:\n" + question); + } catch (NegativeTreeCoverageExecption e) { + e.printStackTrace(); + } catch (TimeOutException e) { + e.printStackTrace(); + } + } } public void setEnableNumericLiteralFilters(boolean enableNumericLiteralFilters) { @@ -428,19 +474,43 @@ } public void init() { + if(endpointKS.isRemote()){ + SparqlEndpoint endpoint = endpointKS.getEndpoint(); + qef = new QueryExecutionFactoryHttp(endpoint.getURL().toString(), endpoint.getDefaultGraphURIs()); + if(cacheDirectory != null){ + try { + long timeToLive = TimeUnit.DAYS.toMillis(30); + CacheCoreEx cacheBackend = CacheCoreH2.create(cacheDirectory, timeToLive, true); + CacheEx cacheFrontend = new CacheExImpl(cacheBackend); + qef = new QueryExecutionFactoryCacheEx(qef, cacheFrontend); + } catch (ClassNotFoundException e) { + e.printStackTrace(); + } catch (SQLException e) { + e.printStackTrace(); + } + } +// qef = new QueryExecutionFactoryPaginated(qef, 10000); + + } else { + qef = new QueryExecutionFactoryModel(((LocalModelBasedSparqlEndpointKS)endpointKS).getModel()); + } + + if(learningProblem instanceof PosOnlyLP){ this.posExamples = convert(((PosOnlyLP)learningProblem).getPositiveExamples()); + this.negExamples = new ArrayList<String>(); } else if(learningProblem instanceof PosNegLP){ this.posExamples = convert(((PosNegLP)learningProblem).getPositiveExamples()); this.negExamples = convert(((PosNegLP)learningProblem).getNegativeExamples()); } treeCache = new QueryTreeCache(); + treeCache.addAllowedNamespaces(allowedNamespaces); if(endpointKS instanceof LocalModelBasedSparqlEndpointKS){ cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(((LocalModelBasedSparqlEndpointKS) endpointKS).getModel())); } else { endpoint = endpointKS.getEndpoint(); - cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, cache)); + cbdGenerator = new CachingConciseBoundedDescriptionGenerator(new ConciseBoundedDescriptionGeneratorImpl(endpoint, endpointKS.getCache())); } cbdGenerator.setRecursionDepth(maxQueryTreeDepth); @@ -464,6 +534,58 @@ return lgg; } + @Autowired + public void setLearningProblem(LearningProblem learningProblem) { + this.learningProblem = learningProblem; + } + + public SparqlEndpointKS getEndpointKS() { + return endpointKS; + } + + @Autowired + public void setEndpointKS(SparqlEndpointKS endpointKS) { + this.endpointKS = endpointKS; + } + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#stop() + */ + @Override + public void stop() { + } + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#isRunning() + */ + @Override + public boolean isRunning() { + return false; + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestDescription() + */ + @Override + public Description getCurrentlyBestDescription() { + return (lgg == null) ? null : DLLearnerDescriptionConvertVisitor.getDLLearnerDescription(lgg.asOWLClassExpression()); + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestEvaluatedDescription() + */ + @Override + public EvaluatedDescription getCurrentlyBestEvaluatedDescription() { + return null; + } + + /** + * @param allowedNamespaces the allowedNamespaces to set + */ + public void setAllowedNamespaces(Set<String> allowedNamespaces) { + this.allowedNamespaces = allowedNamespaces; + } + public static void main(String[] args) throws Exception { Set<String> positiveExamples = new HashSet<String>(); positiveExamples.add("http://dbpedia.org/resource/Liverpool_F.C."); @@ -473,31 +595,14 @@ ks.init(); PosOnlyLP lp = new PosOnlyLP(); lp.setPositiveExamples(Helper.getIndividualSet(positiveExamples)); - QTL qtl = new QTL(lp, ks); + QTL qtl = new QTL(lp, ks, "cache"); + qtl.setAllowedNamespaces(Sets.newHashSet("http://dbpedia.org/ontology/", "http://dbpedia.org/resource/")); qtl.addQueryTreeFilter(new QuestionBasedQueryTreeFilter(Arrays.asList("soccer club", "Premier League"))); qtl.init(); qtl.start(); String query = qtl.getBestSPARQLQuery(); System.out.println(query); + System.out.println(qtl.getCurrentlyBestDescription()); } - - public LearningProblem getLearningProblem() { - return learningProblem; - } - - @Autowired - public void setLearningProblem(LearningProblem learningProblem) { - this.learningProblem = learningProblem; - } - - public SparqlEndpointKS getEndpointKS() { - return endpointKS; - } - - @Autowired - public void setEndpointKS(SparqlEndpointKS endpointKS) { - this.endpointKS = endpointKS; - } - } Added: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java (rev 0) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -0,0 +1,368 @@ +package org.dllearner.algorithms.qtl; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.List; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.apache.log4j.Logger; +import org.dllearner.algorithms.qtl.cache.QueryTreeCache; +import org.dllearner.algorithms.qtl.datastructures.QueryTree; +import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.LiteralNodeConversionStrategy; +import org.dllearner.algorithms.qtl.operations.lgg.EvaluatedQueryTree; +import org.dllearner.algorithms.qtl.operations.lgg.LGGGenerator; +import org.dllearner.algorithms.qtl.operations.lgg.LGGGeneratorImpl; +import org.dllearner.core.AbstractCELA; +import org.dllearner.core.AbstractReasonerComponent; +import org.dllearner.core.ComponentAnn; +import org.dllearner.core.ComponentInitException; +import org.dllearner.core.EvaluatedDescription; +import org.dllearner.core.KnowledgeSource; +import org.dllearner.core.LearningProblemUnsupportedException; +import org.dllearner.core.owl.Description; +import org.dllearner.core.owl.Individual; +import org.dllearner.kb.OWLFile; +import org.dllearner.learningproblems.AxiomScore; +import org.dllearner.learningproblems.Heuristics; +import org.dllearner.learningproblems.PosNegLP; +import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; +import org.springframework.beans.factory.annotation.Autowired; + +import com.hp.hpl.jena.rdf.model.Model; +import com.hp.hpl.jena.rdf.model.ModelFactory; +import com.jamonapi.Monitor; +import com.jamonapi.MonitorFactory; + +@ComponentAnn(name="query tree learner with noise", shortName="qtl2", version=0.8) +public class QTL2 extends AbstractCELA { + + + private static final Logger logger = Logger.getLogger(QTL2.class.getName()); + + private LGGGenerator<String> lggGenerator = new LGGGeneratorImpl<String>(); + + private Queue<EvaluatedQueryTree<String>> todoList; + private SortedSet<EvaluatedQueryTree<String>> solutions; + + private double currentlyBestScore = 0d; + + private List<QueryTree<String>> posExamples; + private List<QueryTree<String>> negExamples; + + private double coverageWeight = 1; + private double specifityWeight = 0; + + private QueryTreeCache treeCache; + + private PosNegLP lp; + + private Model model; + + private AbstractReasonerComponent reasoner; + + private volatile boolean stop; + private boolean isRunning; + + public QTL2() {} + + public QTL2(PosNegLP learningProblem, AbstractReasonerComponent reasoner) throws LearningProblemUnsupportedException{ + this.lp = learningProblem; + this.reasoner = reasoner; + + } + + public QTL2(PosNegLP lp, Model model) { + this.lp = lp; + this.model = model; + } + + /* (non-Javadoc) + * @see org.dllearner.core.Component#init() + */ + @Override + public void init() throws ComponentInitException { + logger.info("Initializing..."); + treeCache = new QueryTreeCache(model); + + posExamples = new ArrayList<QueryTree<String>>(); + negExamples = new ArrayList<QueryTree<String>>(); + + //get the query trees + for (Individual ind : lp.getPositiveExamples()) { + posExamples.add(treeCache.getQueryTree(ind.getName())); + } + for (Individual ind : lp.getNegativeExamples()) { + negExamples.add(treeCache.getQueryTree(ind.getName())); + } + } + + /* (non-Javadoc) + * @see org.dllearner.core.LearningAlgorithm#start() + */ + @Override + public void start() { + logger.info("Running..."); + stop = false; + isRunning = true; + long startTime = System.currentTimeMillis(); + currentlyBestScore = 0d; + + Monitor subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); + Monitor lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + + init(posExamples, negExamples); + + EvaluatedQueryTree<String> currentElement; + do{ + logger.trace("TODO list size: " + todoList.size()); + //pick best element from todo list + currentElement = todoList.poll(); + //generate the LGG between the chosen tree and each uncovered positive example + for (QueryTree<String> example : currentElement.getFalseNegatives()) { + QueryTree<String> tree = currentElement.getTree(); + //compute the LGG + lggMon.start(); + QueryTree<String> lgg = lggGenerator.getLGG(tree, example); + lggMon.stop(); +// tree.dump();System.out.println("++++++++++++++++++++++++++++++++"); +// example.dump();System.out.println("############################"); +// lgg.dump();System.out.println("******************************"); + + + //evaluate the LGG + EvaluatedQueryTree<String> solution = evaluate(lgg); + + if(solution.getScore() >= currentlyBestScore){ + //add to todo list, if not already contained in todo list or solution list + todo(solution); + currentlyBestScore = solution.getScore(); + } + + } + solutions.add(currentElement); +// todoList.remove(currentElement); + } while(!terminationCriteriaSatisfied()); + long endTime = System.currentTimeMillis(); + logger.info("Finished in " + (endTime-startTime) + "ms."); + logger.info("Best solution:\n" + getCurrentlyBestEvaluatedDescription()); + + logger.trace("LGG time: " + lggMon.getTotal() + "ms"); + logger.trace("Avg. LGG time: " + lggMon.getAvg() + "ms"); + logger.trace("#LGG computations: " + lggMon.getHits()); + logger.trace("Subsumption test time: " + subMon.getTotal() + "ms"); + logger.trace("Avg. subsumption test time: " + subMon.getAvg() + "ms"); + logger.trace("#Subsumption tests: " + subMon.getHits()); + } + + public EvaluatedQueryTree<String> getBestSolution(){ + return solutions.first(); + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestDescription() + */ + @Override + public Description getCurrentlyBestDescription() { + return getCurrentlyBestEvaluatedDescription().getDescription(); + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestEvaluatedDescription() + */ + @Override + public EvaluatedDescription getCurrentlyBestEvaluatedDescription() { + EvaluatedQueryTree<String> bestSolution = solutions.first(); + Description description = DLLearnerDescriptionConvertVisitor.getDLLearnerDescription( + bestSolution.getTree().asOWLClassExpression(LiteralNodeConversionStrategy.FACET_RESTRICTION)); + return new EvaluatedDescription(description, new AxiomScore(bestSolution.getScore())); + } + + /** + * @return the treeCache + */ + public QueryTreeCache getTreeCache() { + return treeCache; + } + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#isRunning() + */ + @Override + public boolean isRunning() { + return isRunning; + } + + @Autowired + public void setLearningProblem(PosNegLP learningProblem) { + this.lp = learningProblem; + } + + @Autowired + public void setReasoner(AbstractReasonerComponent reasoner){ + this.reasoner = reasoner; + model = ModelFactory.createDefaultModel(); + for (KnowledgeSource ks : reasoner.getSources()) { + if(ks instanceof OWLFile){ + try { + model.read(((OWLFile) ks).getURL().openStream(), null); + } catch (IOException e) { + e.printStackTrace(); + } + } + } + } + + + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#stop() + */ + @Override + public void stop() { + stop = true; + } + + private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree){ + //1. get a score for the coverage = recall oriented + //compute positive examples which are not covered by LGG + Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(tree, posExamples); + //compute negative examples which are covered by LGG + Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(tree, negExamples); + //compute score + int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); + double recall = coveredPositiveExamples / (double)posExamples.size(); + double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + ? 0 + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + + double coverageScore = recall;//Heuristics.getFScore(recall, precision); + + //2. get a score for the specifity of the query, i.e. how many edges/nodes = precision oriented + int numberOfSpecificNodes = 0; + for (QueryTree<String> childNode : tree.getChildrenClosure()) { + if(!childNode.getUserObject().equals("?")){ + numberOfSpecificNodes++; + } + } + double specifityScore = Math.log(numberOfSpecificNodes); + + //3.compute the total score + double score = coverageWeight * coverageScore + specifityWeight * specifityScore; + + EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExamples, coveredNegativeExamples, score); + + return evaluatedTree; + } + + /** + * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. + * @param tree + * @param allTrees + * @return + */ + private Collection<QueryTree<String>> getCoveredTrees(QueryTree<String> tree, List<QueryTree<String>> trees){ + Collection<QueryTree<String>> coveredTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : trees) { + boolean subsumed = queryTree.isSubsumedBy(tree); + if(subsumed){ + coveredTrees.add(queryTree); + } + } + return coveredTrees; + } + + /** + * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. + * @param tree + * @param allTrees + * @return + */ + private Collection<QueryTree<String>> getUncoveredTrees(QueryTree<String> tree, List<QueryTree<String>> allTrees){ + Collection<QueryTree<String>> uncoveredTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : allTrees) { + boolean subsumed = queryTree.isSubsumedBy(tree); + if(!subsumed){ + uncoveredTrees.add(queryTree); + } + } + return uncoveredTrees; + } + + /** + * Initializes the todo list with all distinct trees contained in the given list {@code trees}. + * Firstly, distinct trees are computed and afterwards, for each tree a score is computed. + * @param trees + */ + private void init(List<QueryTree<String>> posExamples, List<QueryTree<String>> negExamples){ + todoList = new PriorityQueue<EvaluatedQueryTree<String>>(); + solutions = new TreeSet<EvaluatedQueryTree<String>>(); +// EvaluatedQueryTree<String> dummy = new EvaluatedQueryTree<String>(new QueryTreeImpl<String>((N)"TOP"), trees, 0d); +// todoList.add(dummy); + //compute distinct trees + Collection<QueryTree<String>> distinctTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : posExamples) { + boolean distinct = true; + for (QueryTree<String> otherTree : distinctTrees) { + if(!queryTree.equals(otherTree)){ + if(queryTree.isSameTreeAs(otherTree)){ + distinct = false; + break; + } + } + } + if(distinct){ + distinctTrees.add(queryTree); + } + } + for (QueryTree<String> queryTree : distinctTrees) {//System.out.println(queryTree.getStringRepresentation()); + //compute positive examples which are not covered by LGG + Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(queryTree, posExamples); + //compute negative examples which are covered by LGG + Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(queryTree, negExamples); + //compute score + int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); + double recall = coveredPositiveExamples / (double)posExamples.size(); + double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + ? 0 + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + + double score = Heuristics.getFScore(recall, precision); + todoList.add(new EvaluatedQueryTree<String>(queryTree, uncoveredPositiveExamples, coveredNegativeExamples, score)); + } + } + + private boolean sameTrees(QueryTree<String> tree1, QueryTree<String> tree2){ + return tree1.isSubsumedBy(tree2) && tree2.isSubsumedBy(tree1); + } + + private boolean terminationCriteriaSatisfied(){ + return stop || todoList.isEmpty(); + } + + /** + * Add tree to todo list if not already contained in that list or the solutions. + * @param solution + */ + private void todo(EvaluatedQueryTree<String> solution){ + //check if not already contained in todo list + for (EvaluatedQueryTree<String> evTree : todoList) { + if(sameTrees(solution.getTree(), evTree.getTree())){ + return; + } + } + //check if not already contained in solutions + for (EvaluatedQueryTree<String> evTree : solutions) { + if(sameTrees(solution.getTree(), evTree.getTree())){ + return; + } + } + todoList.add(solution); + } + + + +} Added: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java (rev 0) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -0,0 +1,412 @@ +package org.dllearner.algorithms.qtl; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.apache.log4j.Logger; +import org.dllearner.algorithms.qtl.cache.QueryTreeCache; +import org.dllearner.algorithms.qtl.datastructures.QueryTree; +import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.LiteralNodeConversionStrategy; +import org.dllearner.algorithms.qtl.operations.lgg.EvaluatedQueryTree; +import org.dllearner.algorithms.qtl.operations.lgg.LGGGenerator; +import org.dllearner.algorithms.qtl.operations.lgg.LGGGeneratorImpl; +import org.dllearner.core.AbstractCELA; +import org.dllearner.core.AbstractReasonerComponent; +import org.dllearner.core.ComponentAnn; +import org.dllearner.core.ComponentInitException; +import org.dllearner.core.EvaluatedDescription; +import org.dllearner.core.KnowledgeSource; +import org.dllearner.core.LearningProblemUnsupportedException; +import org.dllearner.core.owl.Description; +import org.dllearner.core.owl.Individual; +import org.dllearner.kb.OWLFile; +import org.dllearner.learningproblems.AxiomScore; +import org.dllearner.learningproblems.Heuristics; +import org.dllearner.learningproblems.PosNegLP; +import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; +import org.dllearner.utilities.owl.OWLAPIConverter; +import org.semanticweb.owlapi.io.ToStringRenderer; +import org.semanticweb.owlapi.util.SimpleShortFormProvider; +import org.springframework.beans.factory.annotation.Autowired; + +import uk.ac.manchester.cs.owl.owlapi.mansyntaxrenderer.ManchesterOWLSyntaxOWLObjectRendererImpl; + +import com.hp.hpl.jena.rdf.model.Model; +import com.hp.hpl.jena.rdf.model.ModelFactory; +import com.jamonapi.Monitor; +import com.jamonapi.MonitorFactory; + +@ComponentAnn(name="query tree learner with noise (disjunctive)", shortName="qtl2dis", version=0.8) +public class QTL2Disjunctive extends AbstractCELA { + + + private static final Logger logger = Logger.getLogger(QTL2Disjunctive.class.getName()); + + private LGGGenerator<String> lggGenerator = new LGGGeneratorImpl<String>(); + + private Queue<EvaluatedQueryTree<String>> todoList; + private SortedSet<EvaluatedQueryTree<String>> solutions; + + private double currentlyBestScore = 0d; + + private List<QueryTree<String>> posExamples; + private List<QueryTree<String>> negExamples; + + private double coverageWeight = 0.6; + private double specifityWeight = 0.4; + + private QueryTreeCache treeCache; + + private PosNegLP lp; + + private Model model; + + private AbstractReasonerComponent reasoner; + + private volatile boolean stop; + private boolean isRunning; + + private Monitor subMon; + private Monitor lggMon; + + public QTL2Disjunctive() {} + + public QTL2Disjunctive(PosNegLP learningProblem, AbstractReasonerComponent reasoner) throws LearningProblemUnsupportedException{ + this.lp = learningProblem; + this.reasoner = reasoner; + + } + + public QTL2Disjunctive(PosNegLP lp, Model model) { + this.lp = lp; + this.model = model; + } + + public EvaluatedQueryTree<String> getBestSolution(){ + return solutions.first(); + } + + /* (non-Javadoc) + * @see org.dllearner.core.Component#init() + */ + @Override + public void init() throws ComponentInitException { + logger.info("Initializing..."); + treeCache = new QueryTreeCache(model); + + posExamples = new ArrayList<QueryTree<String>>(); + negExamples = new ArrayList<QueryTree<String>>(); + + //get the query trees + for (Individual ind : lp.getPositiveExamples()) { + posExamples.add(treeCache.getQueryTree(ind.getName())); + } + for (Individual ind : lp.getNegativeExamples()) { + negExamples.add(treeCache.getQueryTree(ind.getName())); + } + } + + /* (non-Javadoc) + * @see org.dllearner.core.LearningAlgorithm#start() + */ + @Override + public void start() { + logger.info("Running..."); + stop = false; + isRunning = true; + long startTime = System.currentTimeMillis(); + currentlyBestScore = 0d; + + subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); + lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + + + //outer loop: compute LGG, pick best solution and remove all covered positive and negative examples + List<EvaluatedQueryTree<String>> unionSolutions = new ArrayList<EvaluatedQueryTree<String>>(); + do { + //compute LGG + computeLGG(); + + //pick best solution computed so far + EvaluatedQueryTree<String> bestSolution = solutions.first(); + unionSolutions.add(bestSolution); + logger.info("#Uncovered pos. examples:" + bestSolution.getFalseNegatives().size()); + + //remove all covered examples + QueryTree<String> tree; + for (Iterator<QueryTree<String>> iterator = posExamples.iterator(); iterator.hasNext();) { + tree = iterator.next(); + if(tree.isSubsumedBy(bestSolution.getTree())){ + iterator.remove(); + } + } + for (Iterator<QueryTree<String>> iterator = negExamples.iterator(); iterator.hasNext();) { + tree = iterator.next(); + if(tree.isSubsumedBy(bestSolution.getTree())){ + iterator.remove(); + } + } + } while (!(stop || posExamples.isEmpty())); + + + } + + private void computeLGG(){ + currentlyBestScore = 0d; + initTodoList(posExamples, negExamples); + + long startTime = System.currentTimeMillis(); + EvaluatedQueryTree<String> currentElement; + do{ + logger.trace("TODO list size: " + todoList.size()); + //pick best element from todo list + currentElement = todoList.poll(); + //generate the LGG between the chosen tree and each uncovered positive example + for (QueryTree<String> example : currentElement.getFalseNegatives()) { + QueryTree<String> tree = currentElement.getTree(); + + //compute the LGG + lggMon.start(); + QueryTree<String> lgg = lggGenerator.getLGG(tree, example); + lggMon.stop(); + + //evaluate the LGG + EvaluatedQueryTree<String> solution = evaluate(lgg); + + if(solution.getScore() >= currentlyBestScore){ + //add to todo list, if not already contained in todo list or solution list + todo(solution); + if(solution.getScore() > currentlyBestScore){ + logger.info("Got better solution:" + currentlyBestScore); + } + currentlyBestScore = solution.getScore(); + } + + } + solutions.add(currentElement); +// todoList.remove(currentElement); + } while(!terminationCriteriaSatisfied()); + long endTime = System.currentTimeMillis(); + logger.info("Finished in " + (endTime-startTime) + "ms."); + EvaluatedDescription bestSolution = getCurrentlyBestEvaluatedDescription(); + ToStringRenderer.getInstance().setRenderer(new ManchesterOWLSyntaxOWLObjectRendererImpl()); + ToStringRenderer.getInstance().setShortFormProvider(new SimpleShortFormProvider()); + logger.info("Best solution:\n" + OWLAPIConverter.getOWLAPIDescription(bestSolution.getDescription()) + "\n(" + bestSolution.getAccuracy() + ")"); + + logger.trace("LGG time: " + lggMon.getTotal() + "ms"); + logger.trace("Avg. LGG time: " + lggMon.getAvg() + "ms"); + logger.trace("#LGG computations: " + lggMon.getHits()); + logger.trace("Subsumption test time: " + subMon.getTotal() + "ms"); + logger.trace("Avg. subsumption test time: " + subMon.getAvg() + "ms"); + logger.trace("#Subsumption tests: " + subMon.getHits()); + } + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#stop() + */ + @Override + public void stop() { + stop = true; + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestDescription() + */ + @Override + public Description getCurrentlyBestDescription() { + return getCurrentlyBestEvaluatedDescription().getDescription(); + } + + /* (non-Javadoc) + * @see org.dllearner.core.AbstractCELA#getCurrentlyBestEvaluatedDescription() + */ + @Override + public EvaluatedDescription getCurrentlyBestEvaluatedDescription() { + EvaluatedQueryTree<String> bestSolution = solutions.first(); + Description description = DLLearnerDescriptionConvertVisitor.getDLLearnerDescription( + bestSolution.getTree().asOWLClassExpression(LiteralNodeConversionStrategy.FACET_RESTRICTION)); + return new EvaluatedDescription(description, new AxiomScore(bestSolution.getScore())); + } + + /* (non-Javadoc) + * @see org.dllearner.core.StoppableLearningAlgorithm#isRunning() + */ + @Override + public boolean isRunning() { + return isRunning; + } + + @Autowired + public void setLearningProblem(PosNegLP learningProblem) { + this.lp = learningProblem; + } + + @Autowired + public void setReasoner(AbstractReasonerComponent reasoner){ + this.reasoner = reasoner; + model = ModelFactory.createDefaultModel(); + for (KnowledgeSource ks : reasoner.getSources()) { + if(ks instanceof OWLFile){ + try { + model.read(((OWLFile) ks).getURL().openStream(), null); + } catch (IOException e) { + e.printStackTrace(); + } + } + } + } + + /** + * @return the treeCache + */ + public QueryTreeCache getTreeCache() { + return treeCache; + } + + private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree){ + //1. get a score for the coverage = recall oriented + //compute positive examples which are not covered by LGG + Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(tree, posExamples); + //compute negative examples which are covered by LGG + Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(tree, negExamples); + //compute score + int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); + double recall = coveredPositiveExamples / (double)posExamples.size(); + double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + ? 0 + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + + double coverageScore = recall;//Heuristics.getFScore(recall, precision); + + //2. get a score for the specifity of the query, i.e. how many edges/nodes = precision oriented + int numberOfSpecificNodes = 0; + for (QueryTree<String> childNode : tree.getChildrenClosure()) { + if(!childNode.getUserObject().equals("?")){ + numberOfSpecificNodes++; + } + } + double specifityScore = Math.log(numberOfSpecificNodes); + + //3.compute the total score + double score = coverageWeight * coverageScore + specifityWeight * specifityScore; + + EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExamples, coveredNegativeExamples, score); + + return evaluatedTree; + } + + /** + * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. + * @param tree + * @param allTrees + * @return + */ + private Collection<QueryTree<String>> getCoveredTrees(QueryTree<String> tree, List<QueryTree<String>> trees){ + Collection<QueryTree<String>> coveredTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : trees) { + boolean subsumed = queryTree.isSubsumedBy(tree); + if(subsumed){ + coveredTrees.add(queryTree); + } + } + return coveredTrees; + } + + /** + * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. + * @param tree + * @param allTrees + * @return + */ + private Collection<QueryTree<String>> getUncoveredTrees(QueryTree<String> tree, List<QueryTree<String>> allTrees){ + Collection<QueryTree<String>> uncoveredTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : allTrees) { + boolean subsumed = queryTree.isSubsumedBy(tree); + if(!subsumed){ + uncoveredTrees.add(queryTree); + } + } + return uncoveredTrees; + } + + /** + * Initializes the todo list with all distinct trees contained in the given list {@code trees}. + * Firstly, distinct trees are computed and afterwards, for each tree a score is computed. + * @param trees + */ + private void initTodoList(List<QueryTree<String>> posExamples, List<QueryTree<String>> negExamples){ + todoList = new PriorityQueue<EvaluatedQueryTree<String>>(); + solutions = new TreeSet<EvaluatedQueryTree<String>>(); +// EvaluatedQueryTree<String> dummy = new EvaluatedQueryTree<String>(new QueryTreeImpl<String>((N)"TOP"), trees, 0d); +// todoList.add(dummy); + //compute distinct trees + Collection<QueryTree<String>> distinctTrees = new ArrayList<QueryTree<String>>(); + for (QueryTree<String> queryTree : posExamples) { + boolean distinct = true; + for (QueryTree<String> otherTree : distinctTrees) { + if(!queryTree.equals(otherTree)){ + if(queryTree.isSameTreeAs(otherTree)){ + distinct = false; + break; + } + } + } + if(distinct){ + distinctTrees.add(queryTree); + } + } + for (QueryTree<String> queryTree : distinctTrees) {//System.out.println(queryTree.getStringRepresentation()); + //compute positive examples which are not covered by LGG + Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(queryTree, posExamples); + //compute negative examples which are covered by LGG + Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(queryTree, negExamples); + //compute score + int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); + double recall = coveredPositiveExamples / (double)posExamples.size(); + double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + ? 0 + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + + double score = Heuristics.getFScore(recall, precision); + todoList.add(new EvaluatedQueryTree<String>(queryTree, uncoveredPositiveExamples, coveredNegativeExamples, score)); + } + } + + private boolean sameTrees(QueryTree<String> tree1, QueryTree<String> tree2){ + return tree1.isSubsumedBy(tree2) && tree2.isSubsumedBy(tree1); + } + + private boolean terminationCriteriaSatisfied(){ + return stop || todoList.isEmpty() || posExamples.isEmpty(); + } + + /** + * Add tree to todo list if not already contained in that list or the solutions. + * @param solution + */ + private void todo(EvaluatedQueryTree<String> solution){ + //check if not already contained in todo list + for (EvaluatedQueryTree<String> evTree : todoList) { + if(sameTrees(solution.getTree(), evTree.getTree())){ + return; + } + } + //check if not already contained in solutions + for (EvaluatedQueryTree<String> evTree : solutions) { + if(sameTrees(solution.getTree(), evTree.getTree())){ + return; + } + } + todoList.add(solution); + } + + + +} Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/cache/QueryTreeCache.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/cache/QueryTreeCache.java 2014-04-23 10:47:59 UTC (rev 4251) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/cache/QueryTreeCache.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -2,6 +2,7 @@ import java.util.HashMap; import java.util.Map; +import java.util.Set; import org.dllearner.algorithms.qtl.QueryTreeFactory; import org.dllearner.algorithms.qtl.datastructures.QueryTree; @@ -17,12 +18,27 @@ private Map<Model, QueryTree<String>> cache; private QueryTreeFactory<String> factory; + private Model model; public QueryTreeCache(){ cache = new HashMap<Model, QueryTree<String>>(); factory = new QueryTreeFactoryImpl(); } + public QueryTreeCache(Model model){ + this.model = model; + cache = new HashMap<Model, QueryTree<String>>(); + factory = new QueryTreeFactoryImpl(); + } + + public QueryTree<String> getQueryTree(String root){ + QueryTree<String> tree = cache.get(model); + if(tree == null){ + tree = factory.getQueryTree(root, model); + } + return tree; + } + public QueryTree<String> getQueryTree(String root, Model model){ QueryTree<String> tree = cache.get(model); if(tree == null){ @@ -62,4 +78,8 @@ public void dispose(){ cache = null; } + + public void addAllowedNamespaces(Set<String> allowedNamespaces) { + factory.addAllowedNamespaces(allowedNamespaces); + } } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2014-04-23 10:47:59 UTC (rev 4251) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -26,6 +26,8 @@ import java.util.Set; import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl; +import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.LiteralNodeConversionStrategy; +import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.LiteralNodeSubsumptionStrategy; import org.semanticweb.owlapi.model.OWLClassExpression; import com.hp.hpl.jena.datatypes.RDFDatatype; @@ -148,5 +150,29 @@ RDFDatatype getDatatype(); Set<Literal> getLiterals(); + + /** + * @param edge + */ + void removeChildren(Object edge); + + /** + * @param stopIfChildIsResourceNode + * @return + */ + String getStringRepresentation(boolean stopIfChildIsResourceNode); + + /** + * @param literalNodeConversionStrategy + * @return + */ + OWLClassExpression asOWLClassExpression(LiteralNodeConversionStrategy literalNodeConversionStrategy); + + /** + * @param tree + * @param s + * @return + */ + boolean isSubsumedBy(QueryTree<N> tree, LiteralNodeSubsumptionStrategy s); } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2014-04-23 10:47:59 UTC (rev 4251) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2014-04-30 11:43:20 UTC (rev 4252) @@ -19,8 +19,12 @@ */ package org.dllearner.algorithms.qtl.datastructures.impl; +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; +import java.util.Calendar; import java.util.Collection; import java.util.Collections; import java.util.Comparator; @@ -36,20 +40,35 @@ import java.util.regex.Pattern; import javax.xml.bind.DatatypeConverter; +import javax.xml.transform.TransformerConfigurationException; import org.dllearner.algorithms.qtl.datastructures.NodeRenderer; import org.dllearner.algorithms.qtl.datastructures.QueryTree; +import org.dllearner.algorithms.qtl.datastructures.rendering.Edge; +import org.dllearner.algorithms.qtl.datastructures.rendering.Vertex; import org.dllearner.algorithms.qtl.filters.Filters; +import org.dllearner.utilities.PrefixCCMap; +import org.jgrapht.DirectedGraph; +import org.jgrapht.ext.EdgeNameProvider; +import org.jgrapht.ext.GraphMLExporter; +import org.jgrapht.ext.VertexNameProvider; +import org.jgrapht.graph.DefaultDirectedGraph; import org.semanticweb.owlapi.model.IRI; import org.semanticweb.owlapi.model.OWLClassExpression; import org.semanticweb.owlapi.model.OWLDataFactory; import org.semanticweb.owlapi.model.OWLDataProperty; +import org.semanticweb.owlapi.model.OWLDataRange; +import org.semanticweb.owlapi.model.OWLDatatype; +import org.semanticweb.owlapi.model.OWLFacetRestriction; import org.semanticweb.owlapi.model.OWLLiteral; import org.semanticweb.owlapi.model.OWLObjectProperty; import org.semanticweb.owlapi.vocab.OWL2Datatype; +import org.semanticweb.owlapi.vocab.OWLFacet; +import org.xml.sax.SAXException; import uk.ac.manchester.cs.owl.owlapi.OWLDataFactoryImpl; +import com.google.common.collect.Sets; import com.hp.hpl.jena.datatypes.BaseDatatype; import com.hp.hpl.jena.datatypes.RDFDatatype; import com.hp.hpl.jena.datatypes.xsd.XSDDatatype; @@ -59,9 +78,14 @@ import com.hp.hpl.jena.query.QueryFactory; import com.hp.hpl.jena.query.Syntax; import com.hp.hpl.jena.rdf.model.Literal; +import com.hp.hpl.jena.sparql.core.TriplePath; import com.hp.hpl.jena.sparql.syntax.ElementGroup; +import com.hp.hpl.jena.sparql.syntax.ElementPathBlock; import com.hp.hpl.jena.sparql.syntax.ElementTriplesBlock; +import com.hp.hpl.jena.sparql.syntax.ElementVisitorBase; +import com.hp.hpl.jena.vocabulary.OWL; import com.hp.hpl.jena.vocabulary.RDF; +import com.hp.hpl.jena.vocabulary.RDFS; /** * @@ -70,10 +94,32 @@ */ public class QueryTreeImpl<N> implements QueryTree<N>{ - enum NodeType{ + public enum NodeType{ RESOURCE, LITERAL, BLANK, VARIABLE; } + public enum LiteralNodeSubsumptionStrategy { + DATATYPE, + INTERVAL, + ENUMERATION, + OFF + } + + public enum LiteralNodeConversionStrategy{ + /** + * Literals in form of an enumeration, e.g. {3, 4, 10} + */ + DATA_ONE_OF, + /** + * Literals as an interval on the datatype, e.g. [>= 5 <=10] + */ + FACET_RESTRICTION, + /** + * Literals as datatype, e.g. xsd:integer + */ + SOME_VALUES_FROM + } + private N userObject; private QueryTreeImpl<N> parent; @@ -97,7 +143,6 @@ private Set<Literal> literals = new HashSet<Literal>(); - public QueryTreeImpl(N userObject) { this.userObject = userObject; children = new ArrayList<QueryTreeImpl<N>>(); @@ -116,9 +161,40 @@ label += "Values: " + object.getLiterals(); } } + label += object.isResourceNode() + "," + object.isLiteralNode(); + return label; + } + }; + + } + + public QueryTreeImpl(N userObject, NodeType nodeType) { + this.userObject = userObject; + children = new ArrayList<QueryTreeImpl<N>>(); + child2EdgeMap = new HashMap<QueryTree<N>, Object>(); + edge2ChildrenMap = new HashMap<String, List<QueryTree<N>>>(); + toStringRenderer = new NodeRenderer<N>() { + public String render(QueryTree<N> object) { + String label = object.toString() + "(" + object.getId() + ")"; + if(object.isLiteralNode()){ +// if(object.getLiterals().size() == 1){ +// label += object.getLiterals().iterator().next(); +// } else if(object.getLiterals().size() > 1){ +// label += "Values: " + object.getLiterals(); +// } + if(!object.getLiterals().isEmpty()){ + label += "Values: " + object.getLiterals(); + } + } + label += object.isResourceNode() + "," + object.isLiteralNode(); return label; } }; + if(nodeType == NodeType.RESOURCE){ + isResourceNode = true; + } else if(nodeType == NodeType.LITERAL){ + isResourceNode = true; + } } public QueryTreeImpl(QueryTree<N> tree){ @@ -130,8 +206,10 @@ subTree.setId(child.getId()); subTree.setIsLiteralNode(child.isLiteralNode()); subTree.setIsResourceNode(child.isResourceNode()); + subTree.addLiterals(child.getLiterals()); addChild(subTree, tree.getEdge(child)); } + setIsResourceNode(tree.isResourceNode()); } public boolean sameType(QueryTree<N> tree){ @@ -279,6 +357,29 @@ child.parent = null; } } + + /** + * Removes all children connected by the given edge. + */ + public void removeChildren(Object edge) { + List<QueryTree<N>> children = edge2ChildrenMap.remove(edge); + if(children != null){ + this.children.removeAll(children); + } +// List<QueryTree<N>> list = edge2ChildrenMap.get("http://dl-learner.org/carcinogenesis#hasAtom"); +// List<QueryTree<N>> newList = new ArrayList<QueryTree<N>>(); +// for (int i = 0; i < Math.min(list.size(), 11); i++) { +// QueryTreeImpl<N> keep = (QueryTreeImpl<N>) list.get(i); +// newList.add(keep); +// } +// list.clear(); +// list.addAll(newList); +// this.children.clear(); +// this.children = new ArrayList<QueryTreeImpl<N>>(); +// this.children.addAll((Collection<? extends QueryTreeImpl<N>>) list); +// edge2ChildrenMap.clear(); +// edge2ChildrenMap.put("http://dl-learner.org/carcinogenesis#hasAtom", list); + } public Object getEdge(QueryTree<N> child) { @@ -342,13 +443,15 @@ @Override public boolean isSubsumedBy(QueryTree<N> tree) { -// if(!sameType(tree)){ -// return false; -// } +// System.out.println("++++++++++++++++++++++++++++"); +// System.out.println(tree + "-" + this.userObject); +// System.out.println(tree.isResourceNode() + "," + tree.isLiteralNode() + "---" + this.isResourceNode + "," + this.isLiteralNode); +// if(tree.getParent() != null && getParent() != null) +// System.out.println(tree.getParent().getEdge(tree) + "#" + getParent().getEdge(this)); +// System.out.println(tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject)); if(!(tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject))){ return false; } - Object edge; for(QueryTree<N> child : tree.getChildren()){ boolean isSubsumed = false; @@ -364,8 +467,112 @@ } } return true; +// return isSubsumedBy(tree, LiteralNodeSubsumptionStrategy.OFF); } + public boolean isSubsumedBy(QueryTree<N> tree, LiteralNodeSubsumptionStrategy strategy) { +// System.out.println("++++++++++++++++++++++++++++"); +// System.out.println(tree + "-" + this.userObject); +// System.out.println(tree.isResourceNode() + "," + tree.isLiteralNode() + "---" + this.isResourceNode + "," + this.isLiteralNode); +// if(tree.getParent() != null && getParent() != null) +// System.out.println(tree.getParent().getEdge(tree) + "#" + getParent().getEdge(this)); +// System.out.println(tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject)); + + if(tree.isResourceNode() && this.isResourceNode){ + if(!(tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject))){ + return false; + } + } else if(tree.isLiteralNode() && this.isLiteralNode){ + if(!tree.getUserObject().equals(this.userObject)){ + if(strategy == LiteralNodeSubsumptionStrategy.OFF){ + return tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject); + } else { + return subsumes(tree.getLiterals(), this.getLiterals(), strategy); + } + } + } else if(!tree.isVarNode() && this.isVarNode()){ + return false; + } else if(tree.isResourceNode() && this.isLiteralNode || tree.isLiteralNode() && this.isResourceNode){//node type mismatch + return false; + } + Object edge; + for(QueryTree<N> child : tree.getChildren()){ + boolean isSubsumed = false; + edge = tree.getEdge(child); + for(QueryTree<N> child2 : this.getChildren(edge)){ + if(child2.isSubsumedBy(child, strategy)){ + isSubsumed = true; + break; + } + } + if(!isSubsumed){ + return false; + } + } + return true; + } + + private boolean subsumes(Set<Literal> subsumer, Set<Literal> subsumee, LiteralNodeSubsumptionStrategy strategy){ + if(strategy == LiteralNodeSubsumptionStrategy.DATATYPE){ + + } else if(strategy == LiteralNodeSubsumptionStrategy.ENUMERATION){ + return subsumer.containsAll(subsumee); + } else if(strategy == LiteralNodeSubsumptionStrategy.INTERVAL){ + //check if both datatypes are the same + RDFDatatype subsumerDatatype = getDatatype(subsumer); + RDFDatatype subsumeeDatatype = getDatatype(subsumee); + if(!subsumerDatatype.equals(subsumeeDatatype)){ + return false; + } + + //avoid boolean datatypes for interval check as there are only 2 possible values + if(subsumerDatatype.equals(XSDDatatype.XSDboolean)){ + return true; + } + + //check if subsumee interval is contained in subsumer interval + Literal subsumerMin = getMin(subsumer); + Literal subsumerMax = getMax(subsumer); + + Literal subsumeeMin = getMin(subsumee); + Literal subsumeeMax = getMax(subsumee); + + boolean leftMoreGeneral = isLessOrEqual(subsumerMin, subsumeeMin); + boolean rightMoreGeneral = isGreaterOrEqual(subsumerMax, subsumeeMax); + + if(!(leftMoreGeneral && rightMoreGeneral)){ +// System.out.println("[" + subsumeeMin + "," + subsumeeMax + "] not in interval " + "[" + subsumerMin + "," + subsumerMax + "]"); + return false; + } + } + return true; + } + + /** + * Returns the datatype of the literals. Throws exception if there are multiple datatypes. + * @param literals + */ + private RDFDatatype getDatatype(Set<Literal> literals){ + RDFDatatype datatype = literals.iterator().next().getDatatype(); + return datatype; + } + + /** + * Checks if all literals have the same datatype. + * @param literals + * @return + */ + private boolean sameDatatype(Set<Literal> literals){ + Iterator<Literal> iterator = literals.iterator(); + RDFDatatype datatype = iterator.next().getDatatype(); + while(iterator.hasNext()){ + if(!iterator.next().getDatatype().equals(datatype)){ + return false; + } + } + return true; + } + @Override public boolean isSubsumedBy(QueryTree<N> tree, boolean stopAfterError) { if(!(tree.getUserObject().equals("?") || tree.getUserObject().equals(this.userObject))){ @@ -515,6 +722,15 @@ } public String getStringRepresentation(){ + return getStringRepresentation(false); + } + + /** + * Prints the query tree and shows children of resources only if enabled. + * @param stopWhenLeafNode + * @return + */ + public String getStringRepresentation(boolean stopIfChildIsResourceNode){ int depth = getPathToRoot().size(); StringBuilder sb = new StringBuilder(); if(isRoot()){ @@ -524,17 +740,19 @@ ren = ren.replace("\n", "\n" + sb); sb.append(ren); sb.append("\n"); - for (QueryTree<N> child : getChildren()) { - for (int i = 0; i < depth; i++) { - sb.append("\t"); + if(isRoot() || !isResourceNode || (isResourceNo... [truncated message content] |
From: <lor...@us...> - 2014-05-02 19:18:37
|
Revision: 4255 http://sourceforge.net/p/dl-learner/code/4255 Author: lorenz_b Date: 2014-05-02 19:18:34 +0000 (Fri, 02 May 2014) Log Message: ----------- Continued disjunctive version of QTL. Modified Paths: -------------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGGMultithreaded.java Added Paths: ----------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Edge.java trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Vertex.java Removed Paths: ------------- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -3,9 +3,13 @@ import java.io.IOException; import java.util.ArrayList; import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; import java.util.List; +import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; +import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; @@ -27,11 +31,16 @@ import org.dllearner.core.owl.Individual; import org.dllearner.kb.OWLFile; import org.dllearner.learningproblems.AxiomScore; -import org.dllearner.learningproblems.Heuristics; import org.dllearner.learningproblems.PosNegLP; +import org.dllearner.learningproblems.QueryTreeScore; import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; +import org.semanticweb.owlapi.io.ToStringRenderer; +import org.semanticweb.owlapi.util.SimpleShortFormProvider; import org.springframework.beans.factory.annotation.Autowired; +import uk.ac.manchester.cs.owl.owlapi.mansyntaxrenderer.ManchesterOWLSyntaxOWLObjectRendererImpl; + +import com.google.common.collect.Sets; import com.hp.hpl.jena.rdf.model.Model; import com.hp.hpl.jena.rdf.model.ModelFactory; import com.jamonapi.Monitor; @@ -50,8 +59,10 @@ private double currentlyBestScore = 0d; - private List<QueryTree<String>> posExamples; - private List<QueryTree<String>> negExamples; + private List<QueryTree<String>> currentPosExampleTrees; + private List<QueryTree<String>> currentNegExampleTrees; + + private Map<QueryTree<String>, Individual> tree2Indivual; private double coverageWeight = 1; private double specifityWeight = 0; @@ -67,6 +78,9 @@ private volatile boolean stop; private boolean isRunning; + private Monitor subMon; + private Monitor lggMon; + public QTL2() {} public QTL2(PosNegLP learningProblem, AbstractReasonerComponent reasoner) throws LearningProblemUnsupportedException{ @@ -87,17 +101,31 @@ public void init() throws ComponentInitException { logger.info("Initializing..."); treeCache = new QueryTreeCache(model); + tree2Indivual = new HashMap<QueryTree<String>, Individual>(lp.getPositiveExamples().size()+lp.getNegativeExamples().size()); - posExamples = new ArrayList<QueryTree<String>>(); - negExamples = new ArrayList<QueryTree<String>>(); + currentPosExampleTrees = new ArrayList<QueryTree<String>>(lp.getPositiveExamples().size()); + currentNegExampleTrees = new ArrayList<QueryTree<String>>(lp.getNegativeExamples().size()); //get the query trees + QueryTree<String> queryTree; for (Individual ind : lp.getPositiveExamples()) { - posExamples.add(treeCache.getQueryTree(ind.getName())); + queryTree = treeCache.getQueryTree(ind.getName()); + tree2Indivual.put(queryTree, ind); + currentPosExampleTrees.add(queryTree); } for (Individual ind : lp.getNegativeExamples()) { - negExamples.add(treeCache.getQueryTree(ind.getName())); + queryTree = treeCache.getQueryTree(ind.getName()); + tree2Indivual.put(queryTree, ind); + currentNegExampleTrees.add(treeCache.getQueryTree(ind.getName())); } + + //some logging + subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); + lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + + //console rendering of class expressions + ToStringRenderer.getInstance().setRenderer(new ManchesterOWLSyntaxOWLObjectRendererImpl()); + ToStringRenderer.getInstance().setShortFormProvider(new SimpleShortFormProvider()); } /* (non-Javadoc) @@ -111,11 +139,8 @@ long startTime = System.currentTimeMillis(); currentlyBestScore = 0d; - Monitor subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); - Monitor lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + initTodoList(currentPosExampleTrees, currentNegExampleTrees); - init(posExamples, negExamples); - EvaluatedQueryTree<String> currentElement; do{ logger.trace("TODO list size: " + todoList.size()); @@ -134,7 +159,7 @@ //evaluate the LGG - EvaluatedQueryTree<String> solution = evaluate(lgg); + EvaluatedQueryTree<String> solution = evaluate(lgg, true); if(solution.getScore() >= currentlyBestScore){ //add to todo list, if not already contained in todo list or solution list @@ -226,35 +251,48 @@ stop = true; } - private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree){ + private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree, boolean useSpecifity){ //1. get a score for the coverage = recall oriented //compute positive examples which are not covered by LGG - Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(tree, posExamples); + Collection<QueryTree<String>> uncoveredPositiveExampleTrees = getUncoveredTrees(tree, currentPosExampleTrees); + Set<Individual> uncoveredPosExamples = new HashSet<Individual>(); + for (QueryTree<String> queryTree : uncoveredPositiveExampleTrees) { + uncoveredPosExamples.add(tree2Indivual.get(queryTree)); + } //compute negative examples which are covered by LGG - Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(tree, negExamples); + Collection<QueryTree<String>> coveredNegativeExampleTrees = getCoveredTrees(tree, currentNegExampleTrees); + Set<Individual> coveredNegExamples = new HashSet<Individual>(); + for (QueryTree<String> queryTree : coveredNegativeExampleTrees) { + coveredNegExamples.add(tree2Indivual.get(queryTree)); + } //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + int coveredPositiveExamples = currentPosExampleTrees.size() - uncoveredPositiveExampleTrees.size(); + double recall = coveredPositiveExamples / (double)currentPosExampleTrees.size(); + double precision = (coveredNegativeExampleTrees.size() + coveredPositiveExamples == 0) ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExampleTrees.size()); double coverageScore = recall;//Heuristics.getFScore(recall, precision); //2. get a score for the specifity of the query, i.e. how many edges/nodes = precision oriented - int numberOfSpecificNodes = 0; + int nrOfSpecificNodes = 0; for (QueryTree<String> childNode : tree.getChildrenClosure()) { if(!childNode.getUserObject().equals("?")){ - numberOfSpecificNodes++; + nrOfSpecificNodes++; } } - double specifityScore = Math.log(numberOfSpecificNodes); + double specifityScore = Math.log(nrOfSpecificNodes); //3.compute the total score double score = coverageWeight * coverageScore + specifityWeight * specifityScore; - EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExamples, coveredNegativeExamples, score); + QueryTreeScore queryTreeScore = new QueryTreeScore(score, coverageScore, + uncoveredPosExamples, Sets.difference(lp.getPositiveExamples(), uncoveredPosExamples), + coveredNegExamples, Sets.difference(lp.getNegativeExamples(), coveredNegExamples), + specifityScore, nrOfSpecificNodes); + EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExampleTrees, coveredNegativeExampleTrees, queryTreeScore); + return evaluatedTree; } @@ -297,7 +335,7 @@ * Firstly, distinct trees are computed and afterwards, for each tree a score is computed. * @param trees */ - private void init(List<QueryTree<String>> posExamples, List<QueryTree<String>> negExamples){ + private void initTodoList(List<QueryTree<String>> posExamples, List<QueryTree<String>> negExamples){ todoList = new PriorityQueue<EvaluatedQueryTree<String>>(); solutions = new TreeSet<EvaluatedQueryTree<String>>(); // EvaluatedQueryTree<String> dummy = new EvaluatedQueryTree<String>(new QueryTreeImpl<String>((N)"TOP"), trees, 0d); @@ -319,19 +357,8 @@ } } for (QueryTree<String> queryTree : distinctTrees) {//System.out.println(queryTree.getStringRepresentation()); - //compute positive examples which are not covered by LGG - Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(queryTree, posExamples); - //compute negative examples which are covered by LGG - Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(queryTree, negExamples); - //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) - ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); - - double score = Heuristics.getFScore(recall, precision); - todoList.add(new EvaluatedQueryTree<String>(queryTree, uncoveredPositiveExamples, coveredNegativeExamples, score)); + EvaluatedQueryTree<String> evaluatedQueryTree = evaluate(queryTree, false); + todoList.add(evaluatedQueryTree); } } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/QTL2Disjunctive.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -3,10 +3,15 @@ import java.io.IOException; import java.util.ArrayList; import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; +import java.util.LinkedHashSet; import java.util.List; +import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; +import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; @@ -26,10 +31,11 @@ import org.dllearner.core.LearningProblemUnsupportedException; import org.dllearner.core.owl.Description; import org.dllearner.core.owl.Individual; +import org.dllearner.core.owl.Union; import org.dllearner.kb.OWLFile; -import org.dllearner.learningproblems.AxiomScore; import org.dllearner.learningproblems.Heuristics; import org.dllearner.learningproblems.PosNegLP; +import org.dllearner.learningproblems.QueryTreeScore; import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; import org.dllearner.utilities.owl.OWLAPIConverter; import org.semanticweb.owlapi.io.ToStringRenderer; @@ -38,6 +44,7 @@ import uk.ac.manchester.cs.owl.owlapi.mansyntaxrenderer.ManchesterOWLSyntaxOWLObjectRendererImpl; +import com.google.common.collect.Sets; import com.hp.hpl.jena.rdf.model.Model; import com.hp.hpl.jena.rdf.model.ModelFactory; import com.jamonapi.Monitor; @@ -52,15 +59,19 @@ private LGGGenerator<String> lggGenerator = new LGGGeneratorImpl<String>(); private Queue<EvaluatedQueryTree<String>> todoList; - private SortedSet<EvaluatedQueryTree<String>> solutions; + private SortedSet<EvaluatedQueryTree<String>> currentPartialSolutions; private double currentlyBestScore = 0d; - private List<QueryTree<String>> posExamples; - private List<QueryTree<String>> negExamples; + private List<QueryTree<String>> currentPosExampleTrees; + private List<QueryTree<String>> currentNegExampleTrees; + private Set<Individual> currentPosExamples; + private Set<Individual> currentNegExamples; + + private Map<QueryTree<String>, Individual> tree2Individual; - private double coverageWeight = 0.6; - private double specifityWeight = 0.4; + private double coverageWeight = 0.8; + private double specifityWeight = 0.2; private QueryTreeCache treeCache; @@ -75,13 +86,14 @@ private Monitor subMon; private Monitor lggMon; + + private List<EvaluatedQueryTree<String>> partialSolutions; public QTL2Disjunctive() {} public QTL2Disjunctive(PosNegLP learningProblem, AbstractReasonerComponent reasoner) throws LearningProblemUnsupportedException{ this.lp = learningProblem; this.reasoner = reasoner; - } public QTL2Disjunctive(PosNegLP lp, Model model) { @@ -90,7 +102,7 @@ } public EvaluatedQueryTree<String> getBestSolution(){ - return solutions.first(); + return currentPartialSolutions.first(); } /* (non-Javadoc) @@ -100,17 +112,33 @@ public void init() throws ComponentInitException { logger.info("Initializing..."); treeCache = new QueryTreeCache(model); + tree2Individual = new HashMap<QueryTree<String>, Individual>(lp.getPositiveExamples().size()+lp.getNegativeExamples().size()); - posExamples = new ArrayList<QueryTree<String>>(); - negExamples = new ArrayList<QueryTree<String>>(); + currentPosExampleTrees = new ArrayList<QueryTree<String>>(lp.getPositiveExamples().size()); + currentNegExampleTrees = new ArrayList<QueryTree<String>>(lp.getNegativeExamples().size()); + currentPosExamples = new TreeSet<Individual>(lp.getPositiveExamples()); + currentNegExamples = new TreeSet<Individual>(lp.getNegativeExamples()); //get the query trees + QueryTree<String> queryTree; for (Individual ind : lp.getPositiveExamples()) { - posExamples.add(treeCache.getQueryTree(ind.getName())); + queryTree = treeCache.getQueryTree(ind.getName()); + tree2Individual.put(queryTree, ind); + currentPosExampleTrees.add(queryTree); } for (Individual ind : lp.getNegativeExamples()) { - negExamples.add(treeCache.getQueryTree(ind.getName())); + queryTree = treeCache.getQueryTree(ind.getName()); + tree2Individual.put(queryTree, ind); + currentNegExampleTrees.add(queryTree); } + + //some logging + subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); + lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + + //console rendering of class expressions + ToStringRenderer.getInstance().setRenderer(new ManchesterOWLSyntaxOWLObjectRendererImpl()); + ToStringRenderer.getInstance().setShortFormProvider(new SimpleShortFormProvider()); } /* (non-Javadoc) @@ -119,49 +147,79 @@ @Override public void start() { logger.info("Running..."); - stop = false; - isRunning = true; long startTime = System.currentTimeMillis(); - currentlyBestScore = 0d; - subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); - lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); + reset(); - - //outer loop: compute LGG, pick best solution and remove all covered positive and negative examples - List<EvaluatedQueryTree<String>> unionSolutions = new ArrayList<EvaluatedQueryTree<String>>(); + int i = 1; do { + logger.info(i++ + ". iteration..."); + logger.info("#Remaining pos. examples:" + currentPosExampleTrees.size()); + logger.info("#Remaining neg. examples:" + currentNegExampleTrees.size()); + //compute LGG computeLGG(); - //pick best solution computed so far - EvaluatedQueryTree<String> bestSolution = solutions.first(); - unionSolutions.add(bestSolution); - logger.info("#Uncovered pos. examples:" + bestSolution.getFalseNegatives().size()); + //pick best (partial) solution computed so far + EvaluatedQueryTree<String> bestPartialSolution = currentPartialSolutions.first(); + partialSolutions.add(bestPartialSolution); //remove all covered examples QueryTree<String> tree; - for (Iterator<QueryTree<String>> iterator = posExamples.iterator(); iterator.hasNext();) { + for (Iterator<QueryTree<String>> iterator = currentPosExampleTrees.iterator(); iterator.hasNext();) { tree = iterator.next(); - if(tree.isSubsumedBy(bestSolution.getTree())){ + if(tree.isSubsumedBy(bestPartialSolution.getTree())){ iterator.remove(); + currentPosExamples.remove(tree2Individual.get(tree)); } } - for (Iterator<QueryTree<String>> iterator = negExamples.iterator(); iterator.hasNext();) { + for (Iterator<QueryTree<String>> iterator = currentNegExampleTrees.iterator(); iterator.hasNext();) { tree = iterator.next(); - if(tree.isSubsumedBy(bestSolution.getTree())){ + if(tree.isSubsumedBy(bestPartialSolution.getTree())){ iterator.remove(); + currentNegExamples.remove(tree2Individual.get(tree)); } } - } while (!(stop || posExamples.isEmpty())); + } while (!(stop || currentPosExampleTrees.isEmpty())); + isRunning = false; + long endTime = System.currentTimeMillis(); + logger.info("Finished in " + (endTime-startTime) + "ms."); + + EvaluatedDescription combinedSolution = buildCombinedSolution(); + System.out.println(OWLAPIConverter.getOWLAPIDescription(combinedSolution.getDescription())); + } + private EvaluatedDescription buildCombinedSolution(){ + List<Description> disjuncts = new ArrayList<Description>(); + Description partialDescription; + for (EvaluatedQueryTree<String> partialSolution : partialSolutions) { + partialDescription = DLLearnerDescriptionConvertVisitor.getDLLearnerDescription( + partialSolution.getTree().asOWLClassExpression(LiteralNodeConversionStrategy.FACET_RESTRICTION)); + disjuncts.add(partialDescription); + } + Description unionDescription = new Union(disjuncts); + + return new EvaluatedDescription(unionDescription, null); + } + + private void reset(){ + partialSolutions = new ArrayList<EvaluatedQueryTree<String>>(); + + stop = false; + isRunning = true; + + subMon.reset(); + lggMon.reset(); + } + private void computeLGG(){ currentlyBestScore = 0d; - initTodoList(posExamples, negExamples); + initTodoList(currentPosExampleTrees, currentNegExampleTrees); + long startTime = System.currentTimeMillis(); EvaluatedQueryTree<String> currentElement; do{ @@ -178,28 +236,27 @@ lggMon.stop(); //evaluate the LGG - EvaluatedQueryTree<String> solution = evaluate(lgg); + EvaluatedQueryTree<String> solution = evaluate(lgg, true); if(solution.getScore() >= currentlyBestScore){ //add to todo list, if not already contained in todo list or solution list todo(solution); if(solution.getScore() > currentlyBestScore){ - logger.info("Got better solution:" + currentlyBestScore); + logger.info("Got better solution:" + solution.getTreeScore()); } currentlyBestScore = solution.getScore(); } } - solutions.add(currentElement); + currentPartialSolutions.add(currentElement); // todoList.remove(currentElement); } while(!terminationCriteriaSatisfied()); long endTime = System.currentTimeMillis(); logger.info("Finished in " + (endTime-startTime) + "ms."); EvaluatedDescription bestSolution = getCurrentlyBestEvaluatedDescription(); - ToStringRenderer.getInstance().setRenderer(new ManchesterOWLSyntaxOWLObjectRendererImpl()); - ToStringRenderer.getInstance().setShortFormProvider(new SimpleShortFormProvider()); - logger.info("Best solution:\n" + OWLAPIConverter.getOWLAPIDescription(bestSolution.getDescription()) + "\n(" + bestSolution.getAccuracy() + ")"); + logger.info("Best solution:\n" + OWLAPIConverter.getOWLAPIDescription(bestSolution.getDescription()) + "\n(" + bestSolution.getScore() + ")"); + logger.trace("LGG time: " + lggMon.getTotal() + "ms"); logger.trace("Avg. LGG time: " + lggMon.getAvg() + "ms"); logger.trace("#LGG computations: " + lggMon.getHits()); @@ -229,10 +286,8 @@ */ @Override public EvaluatedDescription getCurrentlyBestEvaluatedDescription() { - EvaluatedQueryTree<String> bestSolution = solutions.first(); - Description description = DLLearnerDescriptionConvertVisitor.getDLLearnerDescription( - bestSolution.getTree().asOWLClassExpression(LiteralNodeConversionStrategy.FACET_RESTRICTION)); - return new EvaluatedDescription(description, new AxiomScore(bestSolution.getScore())); + EvaluatedQueryTree<String> bestSolution = currentPartialSolutions.first(); + return bestSolution.asEvaluatedDescription(); } /* (non-Javadoc) @@ -270,35 +325,55 @@ return treeCache; } - private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree){ + private EvaluatedQueryTree<String> evaluate(QueryTree<String> tree, boolean useSpecifity){ //1. get a score for the coverage = recall oriented //compute positive examples which are not covered by LGG - Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(tree, posExamples); + Set<QueryTree<String>> uncoveredPositiveExampleTrees = getUncoveredTrees(tree, currentPosExampleTrees); + Set<Individual> uncoveredPosExamples = new HashSet<Individual>(); + for (QueryTree<String> queryTree : uncoveredPositiveExampleTrees) { + uncoveredPosExamples.add(tree2Individual.get(queryTree)); + } //compute negative examples which are covered by LGG - Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(tree, negExamples); + Collection<QueryTree<String>> coveredNegativeExampleTrees = getCoveredTrees(tree, currentNegExampleTrees); + Set<Individual> coveredNegExamples = new HashSet<Individual>(); + for (QueryTree<String> queryTree : coveredNegativeExampleTrees) { + coveredNegExamples.add(tree2Individual.get(queryTree)); + } //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) + int coveredPositiveExamples = currentPosExampleTrees.size() - uncoveredPositiveExampleTrees.size(); + double recall = coveredPositiveExamples / (double)currentPosExampleTrees.size(); + double precision = (coveredNegativeExampleTrees.size() + coveredPositiveExamples == 0) ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); + : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExampleTrees.size()); - double coverageScore = recall;//Heuristics.getFScore(recall, precision); + double coverageScore = Heuristics.getFScore(recall, precision); //2. get a score for the specifity of the query, i.e. how many edges/nodes = precision oriented - int numberOfSpecificNodes = 0; + int nrOfSpecificNodes = 0; for (QueryTree<String> childNode : tree.getChildrenClosure()) { if(!childNode.getUserObject().equals("?")){ - numberOfSpecificNodes++; + nrOfSpecificNodes++; } } - double specifityScore = Math.log(numberOfSpecificNodes); + double specifityScore = 0d; + if(useSpecifity){ + specifityScore = Math.log(nrOfSpecificNodes); + } //3.compute the total score double score = coverageWeight * coverageScore + specifityWeight * specifityScore; - EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExamples, coveredNegativeExamples, score); + QueryTreeScore queryTreeScore = new QueryTreeScore(score, coverageScore, + Sets.difference(currentPosExamples, uncoveredPosExamples), uncoveredPosExamples, + coveredNegExamples, Sets.difference(currentNegExamples, coveredNegExamples), + specifityScore, nrOfSpecificNodes); +// QueryTreeScore queryTreeScore = new QueryTreeScore(score, coverageScore, +// null,null,null,null, +// specifityScore, nrOfSpecificNodes); + + EvaluatedQueryTree<String> evaluatedTree = new EvaluatedQueryTree<String>(tree, uncoveredPositiveExampleTrees, coveredNegativeExampleTrees, queryTreeScore); + return evaluatedTree; } @@ -308,8 +383,8 @@ * @param allTrees * @return */ - private Collection<QueryTree<String>> getCoveredTrees(QueryTree<String> tree, List<QueryTree<String>> trees){ - Collection<QueryTree<String>> coveredTrees = new ArrayList<QueryTree<String>>(); + private List<QueryTree<String>> getCoveredTrees(QueryTree<String> tree, List<QueryTree<String>> trees){ + List<QueryTree<String>> coveredTrees = new ArrayList<QueryTree<String>>(); for (QueryTree<String> queryTree : trees) { boolean subsumed = queryTree.isSubsumedBy(tree); if(subsumed){ @@ -325,8 +400,8 @@ * @param allTrees * @return */ - private Collection<QueryTree<String>> getUncoveredTrees(QueryTree<String> tree, List<QueryTree<String>> allTrees){ - Collection<QueryTree<String>> uncoveredTrees = new ArrayList<QueryTree<String>>(); + private Set<QueryTree<String>> getUncoveredTrees(QueryTree<String> tree, List<QueryTree<String>> allTrees){ + Set<QueryTree<String>> uncoveredTrees = new LinkedHashSet<QueryTree<String>>(); for (QueryTree<String> queryTree : allTrees) { boolean subsumed = queryTree.isSubsumedBy(tree); if(!subsumed){ @@ -343,7 +418,7 @@ */ private void initTodoList(List<QueryTree<String>> posExamples, List<QueryTree<String>> negExamples){ todoList = new PriorityQueue<EvaluatedQueryTree<String>>(); - solutions = new TreeSet<EvaluatedQueryTree<String>>(); + currentPartialSolutions = new TreeSet<EvaluatedQueryTree<String>>(); // EvaluatedQueryTree<String> dummy = new EvaluatedQueryTree<String>(new QueryTreeImpl<String>((N)"TOP"), trees, 0d); // todoList.add(dummy); //compute distinct trees @@ -363,19 +438,8 @@ } } for (QueryTree<String> queryTree : distinctTrees) {//System.out.println(queryTree.getStringRepresentation()); - //compute positive examples which are not covered by LGG - Collection<QueryTree<String>> uncoveredPositiveExamples = getUncoveredTrees(queryTree, posExamples); - //compute negative examples which are covered by LGG - Collection<QueryTree<String>> coveredNegativeExamples = getCoveredTrees(queryTree, negExamples); - //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) - ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); - - double score = Heuristics.getFScore(recall, precision); - todoList.add(new EvaluatedQueryTree<String>(queryTree, uncoveredPositiveExamples, coveredNegativeExamples, score)); + EvaluatedQueryTree<String> evaluatedQueryTree = evaluate(queryTree, false); + todoList.add(evaluatedQueryTree); } } @@ -384,7 +448,7 @@ } private boolean terminationCriteriaSatisfied(){ - return stop || todoList.isEmpty() || posExamples.isEmpty(); + return stop || todoList.isEmpty() || currentPosExampleTrees.isEmpty(); } /** @@ -399,14 +463,11 @@ } } //check if not already contained in solutions - for (EvaluatedQueryTree<String> evTree : solutions) { + for (EvaluatedQueryTree<String> evTree : currentPartialSolutions) { if(sameTrees(solution.getTree(), evTree.getTree())){ return; } } todoList.add(solution); } - - - } Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -210,6 +210,8 @@ addChild(subTree, tree.getEdge(child)); } setIsResourceNode(tree.isResourceNode()); + setIsLiteralNode(tree.isLiteralNode()); + addLiterals(tree.getLiterals()); } public boolean sameType(QueryTree<N> tree){ Added: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Edge.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Edge.java (rev 0) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Edge.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -0,0 +1,47 @@ +package org.dllearner.algorithms.qtl.datastructures.rendering; + +public class Edge { + int id; + String label; + + public Edge(int id, String label) { + this.id = id; + this.label = label; + } + + /** + * @return the id + */ + public int getId() { + return id; + } + + /** + * @return the label + */ + public String getLabel() { + return label; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + id; + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + Edge other = (Edge) obj; + if (id != other.id) + return false; + return true; + } +} \ No newline at end of file Added: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Vertex.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Vertex.java (rev 0) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/rendering/Vertex.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -0,0 +1,47 @@ +package org.dllearner.algorithms.qtl.datastructures.rendering; + +public class Vertex { + int id; + String label; + + public Vertex(int id, String label) { + this.id = id; + this.label = label; + } + + /** + * @return the id + */ + public int getId() { + return id; + } + + /** + * @return the label + */ + public String getLabel() { + return label; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + id; + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + Vertex other = (Vertex) obj; + if (id != other.id) + return false; + return true; + } +} \ No newline at end of file Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -3,17 +3,21 @@ import java.util.Collection; import org.dllearner.algorithms.qtl.datastructures.QueryTree; -import org.dllearner.learningproblems.ScoreTwoValued; +import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.LiteralNodeConversionStrategy; +import org.dllearner.core.EvaluatedDescription; +import org.dllearner.learningproblems.QueryTreeScore; +import org.dllearner.utilities.owl.DLLearnerDescriptionConvertVisitor; public class EvaluatedQueryTree<N> implements Comparable<EvaluatedQueryTree<N>>{ private QueryTree<N> tree; private Collection<QueryTree<N>> falseNegatives; private Collection<QueryTree<N>> falsePositives; - private double score; + private QueryTreeScore score; // private ScoreTwoValued score; - public EvaluatedQueryTree(QueryTree<N> tree, Collection<QueryTree<N>> falseNegatives, Collection<QueryTree<N>> falsePositives, double score) { + public EvaluatedQueryTree(QueryTree<N> tree, Collection<QueryTree<N>> falseNegatives, + Collection<QueryTree<N>> falsePositives, QueryTreeScore score) { this.tree = tree; this.falseNegatives = falseNegatives; this.falsePositives = falsePositives; @@ -44,12 +48,16 @@ } public double getScore() { + return score.getScore(); + } + + public QueryTreeScore getTreeScore() { return score; } @Override public int compareTo(EvaluatedQueryTree<N> other) { - double diff = score - other.getScore(); + double diff = getScore() - other.getScore(); if(diff == 0){ return -1; } else if(diff > 0){ @@ -59,6 +67,11 @@ } } + public EvaluatedDescription asEvaluatedDescription(){ + return new EvaluatedDescription(DLLearnerDescriptionConvertVisitor.getDLLearnerDescription( + getTree().asOWLClassExpression(LiteralNodeConversionStrategy.FACET_RESTRICTION)), score); + } + /* (non-Javadoc) * @see java.lang.Object#toString() */ Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -168,7 +168,7 @@ // } // } // } - if(!lgg.sameType(tree2) || !lgg.getUserObject().equals(tree2.getUserObject())){ + if(!(lgg.sameType(tree2) || lgg.getUserObject().equals(tree2.getUserObject()))){ lgg.setUserObject((N)"?"); lgg.setIsLiteralNode(false); lgg.setIsResourceNode(false); @@ -178,7 +178,7 @@ RDFDatatype d1 = tree1.getDatatype(); RDFDatatype d2 = tree2.getDatatype(); // if(d1 != null && d2 != null && d1 == d2){ - if(d1 == d2){ + if(d1.equals(d2)){ ((QueryTreeImpl<N>)lgg).addLiterals(((QueryTreeImpl<N>)tree1).getLiterals()); ((QueryTreeImpl<N>)lgg).addLiterals(((QueryTreeImpl<N>)tree2).getLiterals()); } @@ -194,6 +194,10 @@ addedChildren = new HashSet<QueryTreeImpl<N>>(); for(QueryTree<N> child1 : tree1.getChildren(edge)){ for(QueryTree<N> child2 : tree2.getChildren(edge)){ +// if(edge.equals("http://dl-learner.org/carcinogenesis#amesTestPositive")){ +// System.out.println(child1); +// System.out.println(child1.isLiteralNode());System.out.println(child2.isLiteralNode() + "\n#######"); +// } lggChild = (QueryTreeImpl<N>) computeLGG(child1, child2, learnFilters); boolean add = true; for(QueryTreeImpl<N> addedChild : addedChildren){ Deleted: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -1,228 +0,0 @@ -package org.dllearner.algorithms.qtl.operations.lgg; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.List; -import java.util.PriorityQueue; -import java.util.Queue; -import java.util.SortedSet; -import java.util.TreeSet; - -import org.apache.log4j.Logger; -import org.dllearner.algorithms.qtl.datastructures.QueryTree; -import org.dllearner.learningproblems.Heuristics; - -import com.jamonapi.Monitor; -import com.jamonapi.MonitorFactory; - -public class NoiseSensitiveLGG<N> { - - - private static final Logger logger = Logger.getLogger(NoiseSensitiveLGG.class.getName()); - - private LGGGenerator<N> lggGenerator = new LGGGeneratorImpl<N>(); - - private Queue<EvaluatedQueryTree<N>> todoList; - private SortedSet<EvaluatedQueryTree<N>> solutions; - - private double currentlyBestScore = 0d; - - private List<QueryTree<N>> posExamples; - - private List<QueryTree<N>> negExamples; - - private double coverageWeight = 0.6; - private double specifityWeight = 0.4; - - public NoiseSensitiveLGG() { - } - - public List<EvaluatedQueryTree<N>> computeLGG(List<QueryTree<N>> posExampleTrees){ - return computeLGG(posExampleTrees, Collections.<QueryTree<N>>emptyList()); - } - - public List<EvaluatedQueryTree<N>> computeLGG(List<QueryTree<N>> posExamples, List<QueryTree<N>> negExamples){ - this.posExamples = posExamples; - this.negExamples = negExamples; - - currentlyBestScore = 0d; - - Monitor subMon = MonitorFactory.getTimeMonitor("subsumption-mon"); - Monitor lggMon = MonitorFactory.getTimeMonitor("lgg-mon"); - init(posExamples, negExamples); - EvaluatedQueryTree<N> currentElement; - do{ - logger.trace("TODO list size: " + todoList.size()); - //pick best element from todo list - currentElement = todoList.poll(); - //generate the LGG between the chosen tree and each uncovered positive example - for (QueryTree<N> example : currentElement.getFalseNegatives()) { - QueryTree<N> tree = currentElement.getTree(); - //compute the LGG - lggMon.start(); - QueryTree<N> lgg = lggGenerator.getLGG(tree, example); - lggMon.stop(); - - //evaluate the LGG - EvaluatedQueryTree<N> solution = evaluate(lgg); - - if(solution.getScore() >= currentlyBestScore){ - //add to todo list, if not already contained in todo list or solution list - todo(solution); - currentlyBestScore = solution.getScore(); - } - - } - solutions.add(currentElement); -// todoList.remove(currentElement); - } while(!terminationCriteriaSatisfied()); - logger.trace("LGG time: " + lggMon.getTotal() + "ms"); - logger.trace("Avg. LGG time: " + lggMon.getAvg() + "ms"); - logger.trace("#LGG computations: " + lggMon.getHits()); - logger.trace("Subsumption test time: " + subMon.getTotal() + "ms"); - logger.trace("Avg. subsumption test time: " + subMon.getAvg() + "ms"); - logger.trace("#Subsumption tests: " + subMon.getHits()); - return new ArrayList<EvaluatedQueryTree<N>>(solutions); - } - - private EvaluatedQueryTree<N> evaluate(QueryTree<N> lgg){ - //1. get a score for the coverage = recall oriented - //compute positive examples which are not covered by LGG - Collection<QueryTree<N>> uncoveredPositiveExamples = getUncoveredTrees(lgg, posExamples); - //compute negative examples which are covered by LGG - Collection<QueryTree<N>> coveredNegativeExamples = getCoveredTrees(lgg, negExamples); - //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) - ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); - - double coverageScore = recall;//Heuristics.getFScore(recall, precision); - - //2. get a score for the specifity of the query, i.e. how many edges/nodes = precision oriented - int numberOfSpecificNodes = 0; - for (QueryTree<N> childNode : lgg.getChildrenClosure()) { - if(!childNode.getUserObject().equals("?")){ - numberOfSpecificNodes++; - } - } - double specifityScore = Math.log(numberOfSpecificNodes); - - //3.compute the total score - double score = coverageWeight * coverageScore + specifityWeight * specifityScore; - - EvaluatedQueryTree<N> solution = new EvaluatedQueryTree<N>(lgg, uncoveredPositiveExamples, coveredNegativeExamples, score); - - return solution; - } - - /** - * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. - * @param tree - * @param allTrees - * @return - */ - private Collection<QueryTree<N>> getUncoveredTrees(QueryTree<N> tree, List<QueryTree<N>> allTrees){ - Collection<QueryTree<N>> uncoveredTrees = new ArrayList<QueryTree<N>>(); - for (QueryTree<N> queryTree : allTrees) { - boolean subsumed = queryTree.isSubsumedBy(tree); - if(!subsumed){ - uncoveredTrees.add(queryTree); - } - } - return uncoveredTrees; - } - - /** - * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}. - * @param tree - * @param allTrees - * @return - */ - private Collection<QueryTree<N>> getCoveredTrees(QueryTree<N> tree, List<QueryTree<N>> trees){ - Collection<QueryTree<N>> coveredTrees = new ArrayList<QueryTree<N>>(); - for (QueryTree<N> queryTree : trees) { - boolean subsumed = queryTree.isSubsumedBy(tree); - if(subsumed){ - coveredTrees.add(queryTree); - } - } - return coveredTrees; - } - - /** - * Initializes the todo list with all distinct trees contained in the given list {@code trees}. - * Firstly, distinct trees are computed and afterwards, for each tree a score is computed. - * @param trees - */ - private void init(List<QueryTree<N>> posExamples, List<QueryTree<N>> negExamples){ - todoList = new PriorityQueue<EvaluatedQueryTree<N>>(); - solutions = new TreeSet<EvaluatedQueryTree<N>>(); -// EvaluatedQueryTree<N> dummy = new EvaluatedQueryTree<N>(new QueryTreeImpl<N>((N)"TOP"), trees, 0d); -// todoList.add(dummy); - //compute distinct trees - Collection<QueryTree<N>> distinctTrees = new ArrayList<QueryTree<N>>(); - for (QueryTree<N> queryTree : posExamples) { - boolean distinct = true; - for (QueryTree<N> otherTree : distinctTrees) { - if(!queryTree.equals(otherTree)){ - if(queryTree.isSameTreeAs(otherTree)){ - distinct = false; - break; - } - } - } - if(distinct){ - distinctTrees.add(queryTree); - } - } - for (QueryTree<N> queryTree : distinctTrees) {//System.out.println(queryTree.getStringRepresentation()); - //compute positive examples which are not covered by LGG - Collection<QueryTree<N>> uncoveredPositiveExamples = getUncoveredTrees(queryTree, posExamples); - //compute negative examples which are covered by LGG - Collection<QueryTree<N>> coveredNegativeExamples = getCoveredTrees(queryTree, negExamples); - //compute score - int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size(); - double recall = coveredPositiveExamples / (double)posExamples.size(); - double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) - ? 0 - : coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size()); - - double score = Heuristics.getFScore(recall, precision); - todoList.add(new EvaluatedQueryTree<N>(queryTree, uncoveredPositiveExamples, coveredNegativeExamples, score)); - } - } - - /** - * Add tree to todo list if not already contained in that list or the solutions. - * @param solution - */ - private void todo(EvaluatedQueryTree<N> solution){ - //check if not already contained in todo list - for (EvaluatedQueryTree<N> evTree : todoList) { - if(sameTrees(solution.getTree(), evTree.getTree())){ - return; - } - } - //check if not already contained in solutions - for (EvaluatedQueryTree<N> evTree : solutions) { - if(sameTrees(solution.getTree(), evTree.getTree())){ - return; - } - } - todoList.add(solution); - } - - private boolean sameTrees(QueryTree<N> tree1, QueryTree<N> tree2){ - return tree1.isSubsumedBy(tree2) && tree2.isSubsumedBy(tree1); - } - - private boolean terminationCriteriaSatisfied(){ - return todoList.isEmpty(); - } - - - -} Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGGMultithreaded.java =================================================================== --- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGGMultithreaded.java 2014-05-02 19:17:05 UTC (rev 4254) +++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGGMultithreaded.java 2014-05-02 19:18:34 UTC (rev 4255) @@ -20,6 +20,7 @@ import com.google.common.collect.Lists; import com.hp.hpl.jena.rdf.model.Model; +@Deprecated public class NoiseSensitiveLGGMultithreaded<N> { private LGGGenerator<N> lggGenerator = new LGGGeneratorImpl<N>(); @@ -80,8 +81,8 @@ //compute score double score = Heuristics.getConfidenceInterval95WaldAverage(trees.size(), trees.size() - uncoveredExamples.size()); //add to todo list, if not already contained in todo list or solution list - EvaluatedQueryTree<N> solution = new EvaluatedQueryTree<N>(lgg, uncoveredExamples, null, score); - todo(solution); +// EvaluatedQueryTree<N> solution = new EvaluatedQueryTree<N>(lgg, uncoveredExamples, null, score); +// todo(solution); } solutions.add(evaluatedQueryTree); } @@ -110,7 +111,7 @@ Collection<QueryTree<N>> uncoveredExamples = new ArrayList<QueryTree<N>>(distinctTrees); uncoveredExamples.remove(queryTree); double score = (trees.size() - uncoveredExamples.size()) / (double)trees.size(); - todoList.add(new EvaluatedQueryTree<N>(queryTree, uncoveredExamples, null, score)); +// todoList.add(new EvaluatedQueryTree<N>(queryTree, uncoveredExamples, null, score)); } } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |