Source code

001/**
002 * Copyright (C) 2007 - 2016, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
018 */
019package org.dllearner.algorithms.qtl.operations.nbr.strategy;
020
021import java.util.ArrayList;
022import java.util.Collections;
023import java.util.HashMap;
024import java.util.List;
025import java.util.Map;
026import java.util.Map.Entry;
027import java.util.Random;
028
029import org.apache.log4j.Logger;
030import org.dllearner.algorithms.qtl.QueryTreeUtils;
031import org.dllearner.algorithms.qtl.datastructures.impl.RDFResourceTree;
032
033import org.apache.jena.graph.Node;
034import com.jamonapi.Monitor;
035import com.jamonapi.MonitorFactory;
036
037/**
038 * 
039 * @author Lorenz BÃ¼hmann
040 *
041 */
042public class GreedyNBRStrategy implements NBRStrategy{
043        
044        private static final Logger logger = Logger.getLogger(GreedyNBRStrategy.class);
045        
046        private int maxEqualEdgesFromRoot = 3;
047        
048        private Random random;
049        
050        private boolean useWeakGeneralisation = true;
051        
052        public GreedyNBRStrategy(){
053                random = new Random();
054        }
055
056        @Override
057        public RDFResourceTree computeNBR(RDFResourceTree posExampleTree,
058                        List<RDFResourceTree> negExampleTrees) {
059                if(logger.isInfoEnabled()){
060                        logger.info("Making NBR...");
061                }
062                logger.info("LGG:\n" + QueryTreeUtils.toSPARQLQueryString(posExampleTree));
063                Monitor mon = MonitorFactory.getTimeMonitor("NBR");
064                mon.start();
065                
066                RDFResourceTree nbr = new RDFResourceTree(posExampleTree);
067                Map<RDFResourceTree, List<Integer>> matrix = new HashMap<>();
068                
069                for(int i = 0; i < negExampleTrees.size(); i++){
070                        checkTree(matrix, nbr, negExampleTrees.get(i), i);
071                }
072                
073                
074                int negTreeSize = negExampleTrees.size();
075                Map<RDFResourceTree, Double> rowValues = new HashMap<>();
076                double value;
077                for(Entry<RDFResourceTree, List<Integer>> entry : matrix.entrySet()){
078                        value = (sum(entry.getValue())+1.0)/(negTreeSize+2.0);
079                        rowValues.put(entry.getKey(), value);
080                }
081
082                
083                List<RDFResourceTree> candidates2Remove = new ArrayList<>();
084                if(useWeakGeneralisation){
085                        for(Entry<RDFResourceTree, Double> entry : rowValues.entrySet()){
086                                if(random.nextDouble() < entry.getValue()){
087                                        candidates2Remove.add(entry.getKey());
088                                }
089                        }
090                        useWeakGeneralisation = false;
091                } else {
092                        for(Entry<RDFResourceTree, Double> entry : rowValues.entrySet()){
093                                if(random.nextDouble() < (1 - entry.getValue())){
094                                        candidates2Remove.add(entry.getKey());
095                                }
096                        }
097                }
098                
099//              RDFResourceTree parent;
100//              for(RDFResourceTree leaf : new ArrayList<RDFResourceTree>(nbr.getLeafs())){
101//                      parent = leaf.getParent();
102//                      if(candidates2Remove.contains(leaf)){
103//                              if(logger.isInfoEnabled()){
104//                                      logger.info("Removing edge [" + 
105//                                                      leaf.getParent().getUserObject() + "--" + leaf.getParent().getEdge(leaf) + "-->" + leaf.getUserObject() + "]");
106//                              }
107//                              leaf.getParent().removeChild((QueryTreeImpl<N>) leaf);
108//                              if(logger.isInfoEnabled()){
109//                                      logger.info("Checking if removal leads to cover a negative tree...");
110//                              }
111//                              if(coversNegativeTree(nbr, negExampleTrees)){
112//                                      parent.addChild((QueryTreeImpl<N>) leaf);
113//                                      if(logger.isInfoEnabled()){
114//                                              logger.info("Removal of the edge leads to cover a negative tree. Undoing removal.");
115//                                      }
116//                              }
117//                      }
118//              }
119                RDFResourceTree parent;
120                for(RDFResourceTree candidate : candidates2Remove){
121                        if(candidate.isRoot())continue;
122                        parent = candidate.getParent();
123                        parent.removeChild(candidate);
124                        if(logger.isInfoEnabled()){
125                                logger.info("Checking if removal leads to coverage of a negative tree...");
126                        }
127                        if(coversNegativeTree(nbr, negExampleTrees)){
128                                parent.addChild(candidate);
129                                if(logger.isInfoEnabled()){
130                                        logger.info("Removal of the edge leads to coverage of a negative tree. Undoing removal.");
131                                }
132                        }
133                }
134                
135//              removeLeafs(nbr, candidates2Remove);
136                removeEqualEdgesFromRoot(nbr);
137                
138                mon.stop();
139                
140                return nbr;
141        }
142        
143        private void generaliseWeak(){
144                
145        }
146        
147        private void generaliseStrong(){
148                
149        }
150        
151        private boolean coversNegativeTree(RDFResourceTree posTree, List<RDFResourceTree> negTrees){
152                for(RDFResourceTree negTree : negTrees){
153                        if(QueryTreeUtils.isSubsumedBy(negTree, posTree)){
154                                return true;
155                        }
156                }
157                return false;
158        }
159        
160        private void removeLeafs(RDFResourceTree nbr, List<RDFResourceTree> candidates2Remove){
161                for(RDFResourceTree leaf : new ArrayList<>(nbr.getLeafs())){
162                        if(candidates2Remove.contains(leaf)){
163                                logger.info("REMOVE " + leaf);
164                                leaf.getParent().removeChild(leaf);
165                        }
166                }
167        }
168        
169        private void removeEqualEdgesFromRoot(RDFResourceTree tree){
170                List<RDFResourceTree> children;
171                int childCount = 1;
172                for(Node edge : tree.getEdges()){
173                        children = tree.getChildren(edge);
174                        childCount = children.size();
175                        while(childCount > maxEqualEdgesFromRoot){
176                                tree.removeChild(children.get(childCount-1));
177                                childCount--;
178                        }
179                }
180                
181        }
182        
183        
184        private String printTreeWithValues(RDFResourceTree tree, Map<RDFResourceTree, List<Integer>> matrix){
185                int depth = QueryTreeUtils.getDepth(tree);
186        StringBuilder sb = new StringBuilder();
187        if(tree.isRoot()){
188                sb.append("TREE\n\n");
189        }
190//        ren = ren.replace("\n", "\n" + sb);
191        sb.append(tree.getData()).append("(").append(matrix.get(tree)).append(")");
192        sb.append("\n");
193        for (RDFResourceTree child : tree.getChildren()) {
194            for (int i = 0; i < depth; i++) {
195                sb.append("\t");
196            }
197            Node edge = tree.getEdgeToChild(child);
198            if (edge != null) {
199                sb.append("  ");
200                sb.append(edge);
201                sb.append(" ---> ");
202            }
203            sb.append(printTreeWithValues(child, matrix));
204        }
205        return sb.toString();
206        }
207        
208        private int sum(List<Integer> list){
209                int sum = 0;
210                for(Integer i : list){
211                        sum += i;
212                }
213                return sum;
214        }
215
216        @Override
217        public List<RDFResourceTree> computeNBRs(RDFResourceTree posExampleTree,
218                        List<RDFResourceTree> negExampleTrees) {
219                return Collections.singletonList(computeNBR(posExampleTree, negExampleTrees));
220        }
221        
222//      private void checkTree(Map<RDFResourceTree, List<Integer>> matrix, RDFResourceTree posTree, RDFResourceTree negTree, int index){
223//              int entry;
224//              if(!posTree.getUserObject().equals("?") && !posTree.getUserObject().equals(negTree.getUserObject())){
225//                      entry = 1;
226//              } else {
227//                      entry = 1;
228//                      for(Object edge : posTree.getEdges()){
229//                              for(RDFResourceTree child1 : posTree.getChildren(edge)){
230//                                      for(RDFResourceTree child2 : negTree.getChildren(edge)){
231//                                              if(!posTree.getUserObject().equals("?") && child1.getUserObject().equals(child2.getUserObject())){
232//                                                      entry = 0;break;
233//                                              }
234//                                              if(posTree.getUserObject().equals("?")){
235//                                                      checkTree(matrix, child1, child2, index);
236//                                              }
237//                                      }
238//                              }
239//                      }
240//                      Object edge;
241//                      for(RDFResourceTree child1 : posTree.getChildren()){
242//                      edge = posTree.getEdge(child1);
243//                      for(RDFResourceTree child2 : negTree.getChildren(edge)){
244//                              
245//                      }
246//                      
247//              }
248//              }
249//              setMatrixEntry(matrix, posTree, index, entry);
250//              if(entry == 1){
251//                      for(RDFResourceTree child : posTree.getChildrenClosure()){
252//                              setMatrixEntry(matrix, child, index, 0);
253//                      }
254//              }
255//      }
256        
257        private void checkTree(Map<RDFResourceTree, List<Integer>> matrix, RDFResourceTree posTree, RDFResourceTree negTree, int index){
258                int entry = 1;
259                for(RDFResourceTree child1 : posTree.getChildren()){
260                        entry = 1;
261                Node edge = posTree.getEdgeToChild(child1);
262                for(RDFResourceTree child2 : negTree.getChildren(edge)){
263                        if(!child1.isVarNode() && child1.getData().equals(child2.getData())){
264                                entry = 0;
265                                checkTree(matrix, child1, child2, index);
266                        } else if(child1.isVarNode()){
267                                entry = 0;
268                                checkTree(matrix, child1, child2, index);
269                        }
270                }
271                setMatrixEntry(matrix, child1, index, entry);
272                if(entry == 1){
273                        for(RDFResourceTree child : QueryTreeUtils.getNodes(posTree)) {
274                                setMatrixEntry(matrix, child, index, 0);
275                        }
276                }
277                }
278                
279        }
280        
281        private void setMatrixEntry(Map<RDFResourceTree, List<Integer>> matrix, RDFResourceTree row, int column, int entry){
282                List<Integer> list = matrix.get(row);
283                if(list == null){
284                        list = new ArrayList<>();
285                        matrix.put(row, list);
286                }
287                try {
288                        list.set(column, entry);
289                } catch (IndexOutOfBoundsException e) {
290                        list.add(entry);
291                }
292        }
293
294//      @Override
295//      public RDFResourceTree computeNBR(RDFResourceTree posExampleTree,
296//                      List<RDFResourceTree> negExampleTrees) {
297//              Map<RDFResourceTree, Integer> map = new HashMap<RDFResourceTree, Integer>();
298//              for(RDFResourceTree negExampleTree : negExampleTrees){
299//                      checkSubsumptionBreadthFirst(posExampleTree, negExampleTree, map);
300//              }
301//              
302//              Map<RDFResourceTree, Integer> sortedMap = sortByValues(map);
303//              System.out.println(sortedMap);
304//              return null;
305//      }
306//
307//      @Override
308//      public List<RDFResourceTree> computeNBRs(RDFResourceTree posExampleTree,
309//                      List<RDFResourceTree> negExampleTrees) {
310//              // TODO Auto-generated method stub
311//              return null;
312//      }
313//      
314//      private void checkSubsumptionBreadthFirst(RDFResourceTree tree1, RDFResourceTree tree2, Map<RDFResourceTree, Integer> map){
315//              Object edge;
316//              for(RDFResourceTree child1 : tree1.getChildren()){
317//                      edge = tree1.getEdge(child1);
318//                      for(RDFResourceTree child2 : tree2.getChildren(edge)){
319//                              if(child1.getUserObject().equals("?") || child2.getUserObject().equals(child1.getUserObject())){
320//                                      Integer i = map.get(child1);
321//                                      if(i == null){
322//                                              i = Integer.valueOf(0);
323//                                      }
324//                                      map.put(child1, Integer.valueOf(i.intValue() +1));
325//                                      checkSubsumptionBreadthFirst(child1, child2, map);
326//                              } else {
327//                                      Integer i = map.get(child1);
328//                                      if(i == null){
329//                                              map.put(child1, Integer.valueOf(0));
330//                                      }
331//                                      
332//                              }
333//                      }
334//              }
335//      }
336//      
337//      private <K, V extends Comparable<V>> Map<K, V> sortByValues(final Map<K, V> map) {
338//              Comparator<K> valueComparator =  new Comparator<K>() {
339//                  public int compare(K k1, K k2) {
340//                      int compare = map.get(k2).compareTo(map.get(k1));
341//                      if (compare == 0) return 1;
342//                      else return compare;
343//                  }
344//              };
345//              Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
346//              sortedByValues.putAll(map);
347//              return sortedByValues;
348//      }
349//      
350//      public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(
351//                      Map<K, V> map) {
352//              List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(
353//                              map.entrySet());
354//              Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
355//                      public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
356//                              return (o1.getValue()).compareTo(o2.getValue());
357//                      }
358//              });
359//
360//              Map<K, V> result = new LinkedHashMap<K, V>();
361//              for (Map.Entry<K, V> entry : list) {
362//                      result.put(entry.getKey(), entry.getValue());
363//              }
364//              return result;
365//      }
366        
367        
368
369}