BVA-System

Im Ausblick bei der letzten Programmaktualisierung habe ich beschrieben, das ich auf der Suche nach einer sinnvollen Datenstruktur bin, um die Zuordnungen zwischen Fotos und Fotoalben effizient erstellen zu können. Entschieden habe ich mich für einen Entscheidungsbaum. Bevor ich in 1 bis 2 Wochen die Version 2.0.0.24 veröffentliche, die eine Implementierung eines Entscheidungsbaumes enthält, möchte ich kurz erklären, was ein Entscheidungsbaum ist und worin ich die Vor- bzw. Nachteile sehe.

Was ist ein Entscheidungsbaum?

In der Informatik stellen Entscheidungsbäume eine Möglichkeit dar, mit der automatische Klassifizierungen vorgenommen werden können. Um eine Klassifizierung vornehmen zu können, wird der Entscheidungsprozess durch mehrere formale Regeln beschrieben. Diese formalen Regeln werden hierarchisch angeordnet. Ein simpler Entscheidungsbaum könnte wie folgt aussehen:

Ein einfacher Entscheidungsbaum

Zur Klassifizierung wird beim Wurzelelement begonnen, die formale Regel zu beantworten. Anschließend wird beim passenden Kindknoten des Baumes fortgefahren. Es wird wieder die formale Regel abgearbeitet und anschließend wieder der Kindknoten untersucht. Der Prozess endet, sobald der Baum keine weiteren Kindknoten enthält.

Möchte ich, nach dem obigen Beispiel, einen roten runden Ball in eines der Fächer einordnen, dann gehe ich wie folgt vor: Als erstes schaue ich, ob der Ball rot oder gelb ist. Da der Ball rot ist, muss ich auf der linken Hälfte des Baumes weitersuchen. Der rechte Teil des Baumes muss nicht weiter betrachtet werden. Anschließend schaue ich mir die Form des Balls an: Er ist rund und somit ist wieder der linke Teil des Baumes der gesuchte Teil. Da die unterste Ebene des Baumes erreicht wurde, ist nun bekannt, das der Ball in das Fach1 gehört.

Welche Vorteile hat ein Entscheidungsbaum?

Der größte Vorteil eines Entscheidungsbaumes ist, das der Anwender durch die formalen Regeln  relativ gut nachvollziehen kann, warum eine Entscheidung so getroffen wurde, wie sie getroffen wurde. Treten falsche Klassifizierungen auf, so kann der Anwender problemlos durch Anpassung der formalen Regeln, korrigierend eingreifen. Bei alternativen Ansätzen, zum Beispiel neuralen Netzen, ist es für den Anwender absolut unmöglich eine Klassifizierung nachzuvollziehen.

Auch der Aufwand, der zur Klassifikation eines Elementes benötigt wird, wird reduziert. Ohne Entscheidungsbaum würde man für jedes mögliche Klassifikationsergebnis testen, ob die Bedingungen erfüllt sind. Schauen wir wieder auf das Beispiel, so müssten für die Fächer 1 bis 4 jeweils 2 Vergleiche, insgesamt also 8, durchgeführt werden. Mit Entscheidungsbaum fallen mit jeder Hierarchiestufe eine Anzahl nicht möglicher Klassifikationsergebnisse weg. Beim Beispiel bleiben somit nur 2 Vergleiche übrig um das richige Fach zu finden. 

Welche Nachteile hat ein Entscheidungsbaum?

Ein Nachteil eines Entscheidungsbaumes ist, das er nur für abzählbare Datentypen anwendbar ist. Wählt man beispielsweise die Länge eines Objektes als Kriterium, so kann es vorkommen, das für jedes Objekt ein neuer Knoten eingefügt wird. Der Grund dafür ist, das jedes Objekt eine leicht andere Länge aufweisen kann: Eines ist 2,5cm lang, das nächste, 2,49cm und das übernächste 2,495, usw. Entgegen wirken kann man dem, indem die Länge nur gerundet in die Bewertung eingeht. Durch die Rundung kann sich allerdings das Klassifikationsergebnis leicht verschlechtern, da möglicherweise Elemente einem falschen Knoten zugeordnet werden.

Ein weiterer Nachteil ist, das der Baum sehr schnell in die Breite wachsen kann, wenn eine Eigenschaft sehr viele verschiedene Ausprägungen besitzt. Je breiter der Entscheidungsbaum wird, desto mehr büßt man von dem eingesparten Aufwand zur Entscheidungsfindung ein. Tritt so ein Fall ein, so ist es ratsam, den Baum so umzuformen, das eine weitere Ebene entsteht.

Fazit

Für mich scheinen Entscheidungsbäume genau der richtige Weg zu sein, um die Zuordnungen zwischen Foto und Fotoalbum effizient treffen zu können. Allerdings sehe ich schon noch Schwierigkeiten darin, wie er sinnvoll aufgebaut werden sollte. Bereits bei dem Metadatentyp „Aufnahmedatum“ habe ich die Befürchtung, das der Baum zu sehr in die Breite wächst. Vorteilhaft ist aber, das der Entscheidungsbaum nur temporär entstellt wird. Daher kann ich die Struktur des Baumes ohne Probleme aktualisieren, wenn die alte Struktur sich als ineffizent herrausstellen sollte.

Tags: Entscheidungsbaum, Foto, Fotoalbum, Metadaten

Kommentare als RSS 2.0-Feed | Kommentar schreiben | Trackback |