3

I'm looking for an algorithm to infer a hierarchy from a set of tagged items.

E.g. if the following items have the tags:

1 a
2 a,b
3 a,c
4 a,c,e
5 a,b
6 a,c
7 d
8 d,f

Then I can construct an undirected graph (or graphs) by tallying the node weights and edge weights:

 node weights  edge weights

 a 6           a-b 2
 b 2           a-c 3
 c 3           c-e 1
 d 2           a-e 1  <-- this edge is parallel to a-c and c-e and not wanted
 e 1           d-f 1
 f 1

The first problem is how to drop any redundant edges to get to the simplified graph? Note that it's only appropriate to remove that redundant a-e edge in this case because something is tagged as a-c-e, if that wasn't the case and the tag was a-e, that edge would have to remain. I suspect that means the removal of edges can only happen during the construction of the graph, not after everything has been tallied up.

What I'd then like to do is identify the direction of the edges to create a directed graph (or graphs) and pick out root nodes to hopefully create a tree (or trees):

 trees         

    a        d 
  // \\      | 
 b     c     f 
        \      
         e     

It seems like it could be a string algorithm - longest common subsequences/prefixes - or a tree/graph algorithm, but I am a little stuck since I don't know the correct terminology to search for it.

  • Huh? Parsing that input and constructing a graph from it isn't difficult… Just keep a table around to look up nodes by their name. What exact information do you want to obtain from the tree once it is built? Something like “all root nodes” → a, d or “contains no cycles” → true or “longest path in the graph” → e, c, a? – amon Oct 8 '13 at 23:01
  • @amon I've expanded the question a bit to hopefully clarify it a bit, I think it boils down to turning an undirected graph into a directed graph (with no cycles). In general, I think the edges should go from nodes with a higher weight to a lower weight, but since it's a graph, that won't always be the case. – Tom Oct 9 '13 at 0:53
  • this looks like it might be the way to go: stackoverflow.com/questions/8127932/… 'directed acyclic graph' was the terminology I couldn't recall! – Tom Oct 9 '13 at 0:58
  • This might be able to be simplified by adding a null root node that all tags would be children of. That way there's only one tree/graph... – Tom Oct 9 '13 at 2:41
  • If your graph is undirected, how do you handle the d-f ambiguity when making it directed? In which direction does the edge go? Otherwise, for each connected subgraph, you can choose the node with the highest weight and build the DAG so that all edges point there, producing a tree. You could also orient all edges so that they point to the node with higher weight, but that won't always produce a tree. When considering these decision, assume the additional rules g, e,g. – amon Oct 9 '13 at 7:46
3

This is what I've come up with. For my data, it's fast enough and the results are what I was after.

  1. First, construct a tree where nodes are not necessarily unique, all nodes must share a "root" tag (in this case 'a') so partition returns just one tree, in pseudo-python:

    nodes = [[a,b], [a,c], [a,b,d], [a,b,d,e], [a,c,e], [a,c,d,e]]
    
    tree = partition(nodes)[0]
    
    def partition(self, nodes, parent=None):
        children = []
        while nodes:
            pivot, count = most_frequent_tag(nodes)
            if not pivot:
                break
    
            left = [node for node in nodes if pivot in node]
            right = [node for node in nodes if pivot not in node]
            child = Node(pivot, count, parent=parent)
            child.children = partition([[tag for tag in node if tag != pivot]
                                        for node in left],
                                       parent=child)
            children.append(child)
            nodes = right
        return children
    
    def most_frequent_tag(nodes):
        ...
        return tag, count
    
    class Node(object):
        def __init__(self, tag, count, parent=None):
            self.tag = tag
            self.count = count
            self.parent = parent
            self.children = []
    

    This results in the tree:

       a (6)
      /    \
    b (3)  c (3)
     |      |
    d (2)  e (2)
     |      |
    e (1)  d (1)
    
  2. The nodes in this tree have to be reordered for it to turn into an acyclic graph, so swap any parent-child relationships where the child occurs more frequently than the parent (any metric will do though). When they have the same frequency, ensure the parent has the lower tag (alphabetically).
    This is a little tricky as the parent node may have to be split if it's count > than the child count.

    tree.check_order()
    
    def Node.check_order(self):
        new_children = []
        for child in self.children:
            swaps.extend(child.check_order())
            if not self.in_order(child):
                # add child to parent, self to child
                new_child = Node(child.tag, child.count, self.parent)
                new_self = Node(self.tag, child.count, new_child)
                self.count -= child.count
                new_self.children = child.children
                new_child.children.append(new_self)
                self.parent.children.append(new_child)
            else:
                new_children.append(child)
        self.children = new_children
    

    The new tree now looks like:

          a (6)
         /    \
       b (3)   c (3)
      /    \     \
    d (2)  e (1)  e (2)
            |      |
           d (1)  d (1)
    

Once that's complete, the tree can be traversed to create a list of graph edges (there may be some duplicates) or a co-occurrence matrix.

  • You can self accept if you want. – World Engineer Oct 22 '13 at 12:34
  • I have and was going to, I had a vague recollection that you had to wait a day or two before that was enabled. Maybe that's just after the question was asked. – Tom Oct 22 '13 at 22:15
2

To solve this problem it is important to consider how you want to represent the Graph. In your sketch you have assigned a weight both to nodes and to edges, but it seems that the edge weight is irrelevant. A good representation might be a pair of the weight and an array of neighbours:

Node(weight: Int, name: String, neighbours: Set of Node)

During the building of the initial undirected graph, you maintain a dictionary of nodes by their name.

For each path in the input, you look up or create all nodes in the dictionary. You then increment the weight of all nodes, and connect the nodes on each pair of the graph to each other:

var nodes = path.split("-").map(s => dict.lookupOrCreate(s));
// increment the weight
for var node <- nodes { node.weight++ }
// add the connections
for var i <- (1 upto nodes.length) {
  nodes[i  ].neighbours.add(nodes[i-1]);
  nodes[i-1].neighbours.add(nodes[i  ]):
}

We now have an undirected, unconnected graph with weighted nodes:

2   6   3   1   2   1
b ↔ a ↔ c ↔ e   d ↔ f
     ↖_____↗

It is now that you will want to remove cycles. Your example contains the subgraph

  e 1        I.  a6 → e1 → c3     ↗ e1
 / \    ==>                     a6     III.
a 6 |        II. a6 → c3 → e1     ↘ c3
 `- c 3

As you can see, there are three possibilites to eliminate this cycle while starting from a. The 3rd possibility is the easiest to implement.

If you want one of the other orders, you'll have to do more expensive reachability tests: For each two child nodes, skip (but not mark as seen) one of those child nodes if it is reachable by the other without using a path that uses the current node.

Next, we want to get the node with the highest weight. This is a simple sort.

var [..., highest] = dict.values.sortBy(n => n.weight);

Now, we traverse the whole graph starting from that node and build the DAG. We can either build a completely new graph (preferable) or remove the current node from the neighbour set. If this set then contains any nodes that were already visited during DAG buidling, a cycle was detected (which we break by skipping that node). Subgraphs that are not reachable will be forgotten, this would eliminate the d-e part. We can work around of this by deleting any nodes from the dictionary, and creating DAGs until the dict is empty. This would create a forest.

var forest = collect until dict.isEmpty {
  var [..., highest] = dict.values.sortBy(n => n.weight);

  def recurse(node: Node): DagNode {
    // remove current node from dict
    dict.delete(node.name);

    // remove seen childs – eliminates cycles
    var childs = node.neighbours.filter(c => dict.contains(c.name));
    // mark all new childs as seen
    for var child <- childs { dict.delete(child.name) }

    // return the DAG subgraph (here: tree) and recurse into each child
    return DagNode(weight: node.weight,
                   name:   node.name,
                   childs: childs.map(c => recurse(c)));
  }

  yield recurse(highest);
}

This should create the forest

  _a_    d
 / | \   |
b  c  e  f
  • Edge weights are important because it's not a tree but a graph, so I need to know how often c is a child of a, not just how often c occurs. – Tom Oct 9 '13 at 22:09
  • Also, I would prefer the algorithm to detect that e only ever appears together with c, so is a child of c, not a... – Tom Oct 9 '13 at 22:13
-2

There's a family of data mining algorithms called decision tree analysis or decision tree learning. The Wikipedia page explains how it is used to create a graph that represents a given data set. Once the algorithm creates the model, it can be used to predict missing characteristics of new data points.

  • 4
    I don't think decision trees are appropriate here. The purpose of decision tree analysis is to do categorization or prediction through learning from a set of observations. The tree structure is learned based on the relationships between a set of input variables and dependent variable that one is seeking to predict. The structure of decision trees is effectively determined based on the variables influence in determining the target variable. Tom is asking for guidance on determining a tree structure based on a specific set of hierarchical tags that have been captured in the data. – DemetriKots Oct 9 '13 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.