Algoritmo per dedurre la gerarchia dei tag

Questo è quello che ho trovato. Per i miei dati, è abbastanza veloce e i risultati sono ciò che cercavo.

1. Per prima cosa, costruisci un albero in cui i nodi non sono necessariamente univoci, tutti i nodi devono condividere un tag "root" (in questo caso 'a') quindi partition restituisce solo un albero, 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 = []
   

   Questo risulta nell'albero:

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

2. I nodi di questo albero devono essere riordinati affinché si trasformino in un grafo aciclico, quindi scambia le relazioni genitore-figlio in cui il bambino si presenta più frequentemente del genitore (qualsiasi metrica lo farà comunque). Quando hanno la stessa frequenza, assicurati che il genitore abbia il tag inferiore (in ordine alfabetico).
   Questo è un po 'complicato in quanto il nodo genitore potrebbe dover essere diviso se conta > rispetto al numero dei bambini.

   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
   

   Il nuovo albero ora appare come:

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

Una volta completato, l'albero può essere attraversato per creare un elenco di bordi del grafico (potrebbero esserci alcuni duplicati) o una matrice di ricorrenza.

Per risolvere questo problema è importante considerare come si vuole rappresentare il grafico. Nel tuo schizzo hai assegnato un peso sia ai nodi che ai bordi, ma sembra che il peso del bordo sia irrilevante. Una buona rappresentazione potrebbe essere una coppia di peso e una serie di vicini:

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

Durante la creazione del grafico iniziale non orientato, si mantiene un dizionario di nodi con il loro nome.

Per ogni percorso nell'input, si cerca o si creano tutti i nodi nel dizionario. Quindi incrementare il peso di tutti i nodi e collegare i nodi su ciascuna coppia del grafico tra loro:

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  ]):
}

Ora abbiamo un grafo non diretto, non connesso con nodi ponderati:

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

Ora vorrai rimuovere i cicli. Il tuo esempio contiene il sottografo

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

Come puoi vedere, ci sono tre possibilità per eliminare questo ciclo partendo da a . La terza possibilità è la più semplice da implementare.

Se vuoi uno degli altri ordini, dovrai fare test di raggiungibilità più costosi: per ogni due nodi figlio, salta (ma non segna come visto) uno di quei nodi figli se è raggiungibile dall'altro senza utilizzando un percorso che utilizza il nodo corrente.

Successivamente, vogliamo ottenere il nodo con il peso più alto. Questo è un ordinamento semplice.

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

Ora attraversiamo tutto il grafico a partire da quel nodo e costruiamo il DAG. Possiamo costruire un grafico completamente nuovo (preferibile) o rimuovere il nodo corrente dal set vicino. Se questo insieme contiene dei nodi che erano già stati visitati durante l'assemblaggio dei DAG, è stato rilevato un ciclo (che interrompiamo saltando quel nodo). I sottografi non raggiungibili saranno dimenticati, questo eliminerebbe la parte d-e . Possiamo ovviare a questo eliminando eventuali nodi dal dizionario e creando DAG finché il dtt non è vuoto. Questo creerebbe una foresta.

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);
}

Questo dovrebbe creare la foresta

  _a_    d
 / | \   |
b  c  e  f

Esiste una famiglia di algoritmi di data mining denominati analisi dell'albero decisionale o tree learning delle decisioni. La pagina di Wikipedia spiega come viene utilizzato per creare un grafico che rappresenta un dato set di dati. Una volta che l'algoritmo crea il modello, può essere utilizzato per prevedere le caratteristiche mancanti dei nuovi punti di dati.