Widening mit Hashbasierter Partitionierung des Hypothesenraums

Abstract

Vielen Algorithmen im Data Mining basieren auf gierigem Verhalten, um ein ausreichend gutes Modell schnell zu finden. Bei der Verwendung solcher Greedy-Algorithmen besteht allerdings die Gefahr, dass diese in lokalen Optima stecken bleiben. Mit Hilfe von Widening, einer Technik um den Hypothesenraum breiter zu durchsuchen, kann diese Gefahr verringert werden, indem parallel mehrere, möglichst unterschiedliche, Modelle erzeugt werden. Bisherige Verfahren im Widening leiden jedoch unter zweierlei Problemen: dem Overhead durch die Kommunikation zwischen den parallelen Recheneinheiten und der Notwendigkeit, Modelle bezüglich ihrer Ähnlichkeit miteinander vergleichen zu können. In der vorliegen Arbeit wird mit dem Bucket-Selektor ein randomisiertes und Modellunabhängiges Widening-Verfahren vorgestellt, das schneller zu ähnlich guten Ergebnissen gelangt wie bisherige Verfahren.