Comprehensible and Robust Knowledge Discovery from Small Datasets

Die Wissensentdeckung in Datenbanken (“Knowledge Discovery in Databases”, KDD) zielt darauf ab, nützliches Wissen aus Daten zu extrahieren. Daten können eine Reihe
von Messungen aus einem realen Prozess repräsentieren oder eine Reihe von Eingabe-
Ausgabe-Werten eines Simulationsmodells. Zwei häufig widersprüchliche Anforderungen
an das erworbene Wissen sind, dass es (1) die Daten möglichst exakt zusammenfasst und
(2) in einer gut verständlichen Form vorliegt. Entscheidungsbäume (“Decision Trees”) und
Methoden zur Entdeckung von Untergruppen (“Subgroup Discovery”) liefern Wissenszusammenfassungen in Form von Hyperrechtecken; diese gelten als gut verständlich.
... mehr

Um die Bedeutung einer verständlichen Datenzusammenfassung zu demonstrieren,
erforschen wir Dezentrale intelligente Netzsteuerung — ein neues System, das die Bedarfsreaktion in Stromnetzen ohne wesentliche Änderungen in der Infrastruktur implementiert.
Die bisher durchgeführte konventionelle Analyse dieses Systems beschränkte sich auf
die Berücksichtigung identischer Teilnehmer und spiegelte daher die Realität nicht ausreichend gut wider. Wir führen viele Simulationen mit unterschiedlichen Eingabewerten durch und wenden Entscheidungsbäume auf die resultierenden Daten an. Mit den daraus resultierenden verständlichen Datenzusammenfassung konnten wir neue Erkenntnisse zum Verhalten der Dezentrale intelligente Netzsteuerung gewinnen.

Entscheidungsbäume ermöglichen die Beschreibung des Systemverhaltens für alle Eingabekombinationen.
Manchmal ist man aber nicht daran interessiert, den gesamten Eingaberaum
zu partitionieren, sondern Bereiche zu finden, die zu bestimmten Ausgabe führen
(sog. Untergruppen). Die vorhandenen Algorithmen zum Erkennen von Untergruppen
erfordern normalerweise große Datenmengen, um eine stabile und genaue Ausgabe zu erzielen.
Der Datenerfassungsprozess ist jedoch häufig kostspielig. Unser Hauptbeitrag ist die
Verbesserung der Untergruppenerkennung aus Datensätzen mit wenigen Beobachtungen.

Die Entdeckung von Untergruppen in simulierten Daten wird als Szenarioerkennung
bezeichnet. Ein häufig verwendeter Algorithmus für die Szenarioerkennung ist PRIM
(Patient Rule Induction Method). Wir schlagen REDS (Rule Extraction for Discovering
Scenarios) vor, ein neues Verfahren für die Szenarioerkennung. Für REDS, trainieren wir
zuerst ein statistisches Zwischenmodell und verwenden dieses, um eine große Menge
neuer Daten für PRIM zu erstellen. Die grundlegende statistische Intuition beschrieben wir
ebenfalls. Experimente zeigen, dass REDS viel besser funktioniert als PRIM für sich alleine:
Es reduziert die Anzahl der erforderlichen Simulationsläufe um 75% im Durchschnitt.

Mit simulierten Daten hat man perfekte Kenntnisse über die Eingangsverteilung — eine
Voraussetzung von REDS. Um REDS auf realen Messdaten anwendbar zu machen, haben
wir es mit Stichproben aus einer geschätzten multivariate Verteilung der Daten kombiniert.
Wir haben die resultierende Methode in Kombination mit verschiedenen Methoden zur Generierung von Daten experimentell evaluiert. Wir haben dies für PRIM und BestInterval — eine weitere repräsentative Methode zur Erkennung von Untergruppen — gemacht. In den meisten Fällen hat unsere Methodik die Qualität der entdeckten Untergruppen erhöht.

Knowledge Discovery in Databases (KDD) targets extracting useful knowledge from data. Data can represent a set of measurements from a real-world process or be a set of input-output values of a simulation model. Two often conflicting requirements to the knowledge acquired are: (1) summarize the data accurately and (2) be in a comprehensible form for a human. Decision trees or subgroup discovery methods, the topic of this study, yield data summaries in the form of hyper-rectangles, which are human-comprehensible.

To demonstrate the importance of comprehensible data models, we study Decentral Smart Grid Control (DSGC) — a new system that implements demand response in electrical grids without significant changes in the infrastructure. ... mehrThe conventional analysis of this system performed so far was limited to considering identical participants and thus did not reflect the reality sufficiently well. We run many simulations, with diverse input values, apply decision trees to the resulting data, and provide new insights.

Decision trees allow describing the system behavior for all combinations of inputs. Sometimes, one is interested not in partitioning the whole input space, but in isolating large regions which lead to particular output — subgroups. The existing algorithms to discover subgroups usually require big datasets to produce stable and accurate hyperrectangles.
However, the data collection process is often costly. Our main contribution is
improving subgroup discovery from small datasets — with few observations.

Subgroup discovery in simulated data is called scenario discovery. A commonly used algorithm for scenario discovery is PRIM (Patient Rule Induction Method). In this work, we propose a new procedure, REDS (Rule Extraction for Discovering Scenarios). We train an intermediate statistical model which generalizes fast and use it to create more data for PRIM. We provide the statistical intuition behind this idea. Experiments show that this method is much better than PRIM on its own. It reduces the number of simulation runs necessary by 75% on average.

With simulated data, one has perfect knowledge on the input distribution — an assumption of REDS. To make REDS applicable to measured data, we combined it with sampling from an estimated joint probability distribution of attributes. We have evaluated the resulting method in combination with various methods to generate data experimentally on a broad range of datasets. We did so for PRIM and BestInterval — another representative subgroup discovery method. In the majority of cases, our methodology enhanced the quality of discovered subgroups.