Rekursive Hierarchie Ranking

Question

Ich habe keine Ahnung, ob ich das richtig geschrieben habe. Ich möchte beginnen, High-End-Data-Mining-Techniken zu lernen, und ich verwende derzeit SQL Server und Access 2016.

Ich habe ein System, ID-Karten verfolgt. Jede ID ist mit einer bestimmten Ebene einer Sicherheitshierarchie markiert, die viele Zweige aufweist.

Zum Beispiel

Root 
-Maintenance 
- Management 
    - Supervisory 
    - Manager 
    - Executive 
- Vendors 
    - Secure 
    - Per Diem 
- Inside Trades 

Es gibt viele andere Abteilungen wie Wartung, einige einfache, einige mit viel mehr gewunden, Hierarchien.

Jede ID-Karte ist im Wartungsbeispiel mit einem Tag gekennzeichnet. - Per Diem: Anbieter: Maintenance: Root. Andere können nur an Lieferanten, einige an allgemeine Wartung selbst (niemand hat Wurzel, Gott sei Dank).

Also lassen Sie uns sagen, ich habe 20 ID Cards ausgewählt, diese sind verfügbares Personal, das ich auf einen Job Aufgaben haben kann, aber da sie verschiedene Bereiche der Sicherheit haben, möchte ich Gemeinsamkeiten finden, die sie gemeinsam als 20-Personen-Gruppe arbeiten können was auch immer andere Gruppierungen ich machen kann.

So die beabsichtigte Ausgabe

CommonMatch = - Per Diem 
CardID = 1 
CardID = 3 

CommonMatch = Vendors 
CardID = 1 
CardID = 3 
CardID = 20 

So in dem obigen Beispiel würde, während ich 2 Personen auf -Per Diem Arbeit Arbeit haben könnte, denn das ist ihre kleinste gemeinsame Sicherheit Ähnlichkeit ist, gibt es auch Kartenhalter # 20 hat Rechte an der Vorgängergruppe (Vendoren), die 1 und 3 teilen, also könnte ich drei von ihnen auf dieser Ebene arbeiten lassen.

Ich suche niemanden, der die Arbeit für mich erledigt (obwohl Beispiele immer willkommen sind), mehr, um mir in die richtige Richtung zu zeigen, was ich studieren sollte, was ich versuche zu tun, etc Ich weiß, CTE's sind ein Weg zu gehen, aber das scheint nur ein Werkzeug in einem viel größeren Prozess, der getan werden muss.

Ihnen allen im Voraus danken

Answer 1

Nun ist es nicht so sehr ein Graph-Theorie oder Data-Mining-Problem, sondern eine Datenstruktur Problem und eine, die sich fast gelöst hat.

Ziel ist es, in der Lage zu sein, die Menge der Karten-IDs in disjunkte Teilmengen zu partitionieren, wenn eine Sicherheitsfreigabe gegeben ist.

Der Grundgedanke wäre also, den Hierarchiebaum zu strukturieren und dann jede Karten-ID dem Pfad zuzuweisen, der durch die Sicherheitsstufe-Clearance impliziert wird. Zu diesem Zweck wird jeder Knoten des Hierarchiebaums nun zu einem Container von Karten-IDs (zB hat jeder Knoten des Hierarchiebaums a) seinen eigenen Namen (als eindeutige Identifikation) b) Zeiger auf andere Knoten c) eine Liste der zugeordneten Karten-IDs seinen „Namen“.)

Dann ist die Menge der Karten Abrufen von mit Spiel UP TO eine bestimmte Sicherheitsstufe einfach ein Fall, den Baum von des Durchlaufens nach unten, dass bestimmte Ebene, bis die Blätter des Baumes, die ganze Zeit Sammeln der Karten-IDs von den Knotencontainern, wenn sie angetroffen werden.

Angenommen, wir Zugriff Baum haben:

A 
+-B 
+-C 
D 
+-E 

Und Karte ID Zuordnungen:

B:[1,2,3] 
C:[4,8] 
E:[10,12] 

Im Moment, B, C, E nur Sinn machen, als Tags, gibt es keine Strukturinformationen mit ihnen verbunden. Wir müssen daher zuerst den Baum "bauen". Das folgende Beispiel verwendet Networkx aber das gleiche kann mit einer Vielzahl von Wegen erreicht werden:

import networkx 
G = networkx.DiGraph() #Establish a directed graph 
G.add_edge("A","B") 
G.add_edge("A","C") 
G.add_edge("A","D") 
G.add_edge("D","E") 

nun die Karten-IDs zu den Knoten Containern zuweisen (in NetworkX, Knoten kann eine beliebige gültige Python-Objekt sein, so ich gehe mit einer sehr einfachen Liste)

G.node["B"]=[1,2,3] 
G.node["C"]=[4,8] 
G.node["E"]=[10,12] 

So, jetzt zu gehen, jeden unter „A“ zum Laufen zu bringen (die Wurzel des Baumes), können Sie den Baum von dieser Ebene nach unten entweder über Depth First Search (DFS) oder Breadth First Search (BFS) durchqueren und Sammeln Sie die Karten-IDs aus den Containern. Ich werde hier DFS verwenden, nur weil Networkx a function that returns the visited nodes je nach Besuchsauftrag direkt hat.

#dfs_preorder_nodes returns a generator, this is an efficient way of iterating very large collections in Python but I am casting it to a "list" here, so that we get the actual list of nodes back. 
vis_nodes = list(networkx.dfs_preorder_nodes(G,"A")); #Start from node "A" and DFS downwards 
cardIDs = [] 
#I could do the following with a one-line reduce but it might be clearer this way 
for aNodeID in vis_nodes: 
    if G.node[aNodeID]: 
     cardIDs.extend(G.node[aNodeID]) 

Am Ende der obigen Iteration cardIDs wird all Karten-IDs von Zweig „A“ nach unten in einer praktischen Liste enthalten.

Natürlich ist dieses Beispiel sehr einfach, aber da wir über Bäume sprechen, kann der Baum so groß sein, wie Sie möchten, und Sie durchlaufen ihn immer noch auf die gleiche Weise und benötigen nur einen einzigen Eintrittspunkt (den oberen Ebene Zweig).

Schließlich ist die Tatsache, dass Sie Access als Ihr Backend verwenden, nicht notwendigerweise ein Hindernis, sondern relationale Datenbanken do not handle graph type data with great ease. Sie könnten leicht für etwas wie einen einfachen Baum (wie das, was Sie hier zum Beispiel haben) wegkommen, aber die Mühe, dies zu unterstützen, rechtfertigt wahrscheinlich die Durchführung dieses Prozesses außerhalb der Datenbank (z. B. die Datenbank nur zum Abrufen der Daten und Ausführen verwenden Die Art der Datenverarbeitung in einer anderen Umgebung Das Ausführen eines DFS in SQL ist die Art von Aufwand, auf die ich oben Bezug nehme.)

Hoffe, das hilft.