“Dafür reichen doch schon ein paar Zeilen Javascript!”
Raimo
Bei der Betrachtung einer Technologie keimt in einem Entwickler immer wieder eine Frage auf: Wieviel Aufwand muss investiert werden um eine eigene einfache Implementierung zu erstellen? Hinter dieser Frage steht dabei nicht unbedingt das leidige Anti-Pattern Reinventing the Square Wheel, sondern die konkrete Frage nach den Fähigkeiten des eigenen Teams.
Bei meinen Zusammentreffen mit Entscheidungsbäumen in den letzten Jahrzehnten war ich regelmäßig über den Respekt meiner Kollegen gegenüber dieser Technologie erstaunt. Insbesondere da es sich nicht um die Induktion von Entscheidungsbäumen durch maschinelles Lernen handelte, sondern um deren langweilige Cousine, die manuell von einem Experten erstellt wird.
Entscheidungsbäume sind gerichtete Graphen zur Lösungsfindung, dabei repräsentiert jeder Knoten eine Frage und jedes seiner Blätter eine Antwort. Im folgenden ist eine trivialer Entscheidungsbaum dargestellt, der Personen anhand von Namen und Alter kategorisiert.
Wen die Darstellung an BPMN erinnert, liegt nicht ganz falsch. Der Einfachheit halber ist der Entscheidungsbaum mit diagrams.net gezeichnet und letzten Endes auch nichts anderes als ein sehr spezieller Workflow. Jeder Zweig eines Entscheidungsbaums endet in einem terminalen Blatt, das der gefundenen Kategorie entspricht. Hier sind es Vater, Kind, Erwachsen und Unbekannt.
Dieser Entscheidungsbaum zeigt eine weitere Besonderheit. Es ist ein binärer Entscheidungsbaum. Jede Frage besitzt nur genau zwei Antworten. Dies bedeutet aber keine Einschränkung, denn jeder Entscheidungsbaum kann auf eine binäre Darstellung zurückgeführt werden.
In diesem Beitrag geht es nicht um die Erstellung eines Entscheidungsbaums, sondern um die Kategorisierung von Eingangsdaten durch den Baum.
Der oben dargestellte Entscheidungsbaum kann durch die folgenden Zeilen erzeugt werden.
Node answerAdult = new TerminalNode("Erwachsen");
Node answerYes = new TerminalNode("Vater");
Node answerNo = new TerminalNode("Kind");
Node decision3 = new ScriptNode("Erwachsen", "age > 18", answerAdult, answerNo);
Node decision2 = new ScriptNode("Vorname Jens", "firstname === 'Jens'", answerYes, decision3);
Node info1 = new DefaultNode("Familie Kaiser", decision2);
Node decision1 = new ScriptNode("Nachname Kaiser", "lastname === 'Kaiser'", info1, answerNo);
tree = new RootNode("Example", decision1);
Die Klassen TerminalNode, RootNode, ScriptNode und InfoNode implementieren dabei die einzelnen Typen von Knoten im Baum. Der RootNode ist die Wurzel des Baumes, der ScriptNode entspricht der Frage und der TerminalNode dem Ergebnis der Qualifizierung.
Zur Auswertung des Baumes muss, beginnend mit dem RootNode, für jeden Knoten geprüft werden, welcher Knoten als nächster ausgewählt werden soll.
Für RootNode und InfoNode ist dies sehr einfach, weil beide nur einen einzigen Nachfolger haben. Für den TerminalNode ist es auch trivial, weil die Auswertung des Baumes endet, wenn er erreicht wird.
Die Auswertung ist etwas schwieriger bei dem ScriptNode, weil er einen Wert aus der aktuellen Umgebung prüft und daraufhin einen von zwei Folgeknoten auswählt. Häufig wird in diesem Zusammenhang hervorgehoben, dass ein Baum Fragen automatisiert beantworten kann und keine manuelle Eingabe benötigt. Aus der Implementierungssicht irritierend, weil die automatische Antwort die unspektakuläre ist. Da alle Fragen im Baum bekannt sind, kann zu Beginn der Verarbeitung die Vollständigkeit der Daten geprüft werden. Fehlene Daten können dann, zu gegebener Zeit, erfragt werden.
Der folgende TreeEvaluator kann einen Baum auf zwei Weisen auswerten. Mit der evaluate wird der Baum bis zu einem TerminalNode durchlaufen und mit der step Methode jeweils der nächste Knoten bestimmt.
public class TreeEvaluator {
private final Context context;
private Node current;
public TreeEvaluator(Context context, RootNode root) {
this.context = context;
this.current = root;
}
public Node evaluate() {
checkTerminal();
Node next;
do {
next = current.evaluate(context);
if (next == null) {
break;
}
current = next;
} while (!current.isTerminal());
return current;
}
public Node step() {
checkTerminal();
Node next = current.evaluate(context);
if (next == null) {
return current;
}
current = next;
return current;
}
private void checkTerminal() {
if (current.isTerminal()) {
throw new IllegalStateException("terminal already reached: " + current.getId());
}
}
}
Wird eine der beiden Methoden aufgerufen, obwohl schon ein TerminalNode erreicht wurde, dann wird eine Exception geworfen.
Der folgende JUnit Test zeigt die Verwendung mit dem weiter oben erzeugten Entscheidungsbaum.
MapContext context = new MapContext();
context.put("firstname", "Jens");
context.put("lastname", "Kaiser");
context.put("age", 52);
TreeEvaluator evaluator = new TreeEvaluator(context, tree);
Node evaluate = evaluator.evaluate();
assertNotNull(evaluate);
assertTrue(evaluate.isTerminal());
assertEquals("Vater", evaluate.getId());
Zuerst wird der Context mit allen notwendigen Daten gefüllt und dann der Evaluator initialisiert. Der Aufruf von evaluate liefert daraufhin den Knoten Vater als Ergebnis.
Die Auswertung der Daten innerhalb des ScriptNode wird über Ausdrücke realisiert, die mit Variablen arbeiten, die den Namen der Daten im Context entsprechen.
Die Ausdrücke “age > 18” und “lastname === 'Kaiser'” können mit selbstgeschriebenen Tools ausgewertet werden, aber für die Kürze des Beitrags und der Raffinesse der Lösung wird eine ScriptEngine genutzt. Seit Java 6 liefert das Java SDK Script-Unterstützung. Für die Unterstützung von Javascript wurde zuerst die Engine Rhino und später Nashorn ausgeliefert.
Die Klasse ScriptNode verwendet die ScriptEngine um die Ausdrücke auszuwerten. Die Daten werden aus dem Context als Map ausgelesen und über das Binding der Engine übergeben.
public class ScriptNode extends Node {
private static final ScriptEngine engine = new ScriptEngineManager().getEngineByName("graal.js");
private final String script;
private final Node left;
private final Node right;
public ScriptNode(String id, String script, Node left, Node right) {
super(id);
this.script = script;
this.left = left;
this.right = right;
}
@Override
public Node evaluate(Context context) {
var bindings = engine.createBindings();
context.asMap().forEach(bindings::put);
try {
boolean eval = Optional.ofNullable(engine.eval(script, bindings)).filter(Boolean.class::isInstance)
.map(Boolean.class::cast).orElse(false);
return eval ? left : right;
} catch (ScriptException e) {
throw new IllegalStateException(e.getMessage(), e);
}
}
}
Das Ergebnis der Auswertung wird als Boolean interpretiert und zur Auswahl des Folgeknotens verwendet.
Seit Java 15 ist Nashorn kein Bestandteil des Java SDK mehr und es wird eine offiziell gepflegte Alternative benötigt. Erfreulicherweise stellt das GraalVM Framework eine Engine zur Verfügung. Das Einbinden ist recht einfach, es werden nur die entsprechenden Artefakte im Classpath benötigt.
<dependency> <groupId>org.graalvm.js</groupId> <artifactId>js</artifactId> <version>21.1.0</version> </dependency> <dependency> <groupId>org.graalvm.js</groupId> <artifactId>js-scriptengine</artifactId> <version>21.1.0</version> </dependency>
Damit ist die Auswertung eines Entscheidungsbaums auch schon implementiert. Einiges kann noch ergänzt und verbessert werden, aber das ist Stoff für einen anderen Beitrag.