Analysis and evaluation of data preprocessing methods for clustering analyses

Abstract

Data is often used to extract knowledge from it and guide decisions in several areas. The knowledge extraction process is usually done with a machine-learning model like clustering. However, frequently, this data contains data imperfections such as missing values, outliers, or the data has skewed distributions. These imperfections need to be addressed to extract knowledge from the data because otherwise, machine-learning models can not be applied or achieve poor results. This process is called preprocessing. Many different preprocessing methods and corresponding hyperparameters exist. Therefore, finding a good selection of methods and hyperparameters to improve the machine-learning model result is challenging, especially if the data imperfections are unknown. In addition, more than one preprocessing method is often used, which increases the search space and brings additional challenges as the order in which they are performed and the interaction between the preprocessing methods is unclear. This may result in a lengthy trial and error process, especially for inexperienced users, where different preprocessing pipelines are evaluated until an acceptable pipeline is found. Some recent advances have been made in the area of AutoML that cover the automation of this selection as a small part of their approach. However, these are limited in the area of clustering, and most approaches propose only a single preprocessing method or consider only a limited number of methods in their configuration space. One reason for these limitations is that they focus on an end-to-end approach where, besides an appropriate preprocessing pipeline, a clustering algorithm and its parameters are suggested as well. The AutoML approaches consider preprocessing to be a small part at best and focus primarily on model building. In contrast, this work focuses mainly on addressing the challenges named in the first paragraph and improving the results with appropriate preprocessing pipelines while using a model, in this case clustering, to evaluate the pipelines. To mitigate the challenges described in the first section, the overall goal is to make accurate suggestions for preprocessing pipelines that improve the clustering result. In order to achieve this, it is important to identify data imperfections and to understand the relationship between data imperfections and preprocessing pipelines. This thesis contributes a first step in that direction with the concept of how a knowledge base can be created that accurately measures the effects of preprocessing pipelines on data with imperfections and can identify data imperfections of datasets. In order to achieve the latter, meta-features are evaluated because they are a good way to describe unseen datasets and their imperfections. Such a knowledge base needs to contain information from many different datasets to be able to generalize. Because of that, synthetic data is used and further manipulated with data imperfections to have an almost unlimited dataset available and to make a precise evaluation of what data imperfection is handled by which pipeline well. These manipulations skew the data distribution, remove parts of the data to create missing values, and add outliers to the data. Because of the named challenges of section one, it is impossible to apply all combinations of preprocessing methods and their hyperparameters to a dataset, even if the selection of preprocessing methods is small. Instead, pipelines are generated and refined during an optimization process. As optimization, Genetic optimization is used because it provides high flexibility and can be well customized to address the named challenges. The evaluation shows that for most datasets, a preprocessing pipeline is found by the optimizer, which leads to a significant improvement in the clustering results compared to the results without preprocessing. The improvement is most significant for skewed distribution data, while datasets that have not been manipulated show the slightest improvement. Additionally, the evaluation of the optimization process shows that a well-performing pipeline is found relatively quickly, while the improvement afterward exists but is comparatively small. It is shown that the missing value imputation works best with the KNN-Imputer compared to other imputation techniques. Other data imperfections do not produce a preferred method or pipeline. Concerning the order of the preprocessing methods within a pipeline, it could not be shown that there is a significant difference. Additionally, it is demonstrated that meta-features correlate with data imperfections. Therefore, it suggests that it is possible to determine the need for preprocessing and the identification of data imperfections with the thesis used meta-features.

Daten werden häufig dazu verwendet, um Wissen aus ihnen zu extrahieren und Entscheidungen in verschiedenen Bereichen zu treffen. Der Prozess der Wissensextraktion erfolgt in der Regel mit einem maschinellen Lernmodell wie Clustering. Häufig enthalten diese Daten jedoch Fehler wie fehlende Werte, Ausreißer oder eine schiefe Verteilung der Daten. Diese Fehler müssen beseitigt werden, um Wissen aus den Daten zu extrahieren, da sonst die Modelle des maschinellen Lernens nicht angewandt werden können oder schlechten Ergebnisse erzielen. Dieser Prozess wird als Vorverarbeitung bezeichnet. Es gibt viele verschiedene Vorverarbeitungsmethoden und entsprechende Hyperparameter. Daher ist es eine Herausforderung, eine gute Auswahl an Methoden und Hyperparametern zu finden, um das Ergebnis des maschinellen Lernens zu verbessern, insbesondere wenn die Fehler der Daten unbekannt sind. Darüber hinaus wird häufig mehr als eine Vorverarbeitungsmethode verwendet, was den Suchraum vergrößert und zusätzliche Herausforderungen mit sich bringt, da die Reihenfolge, in der sie durchgeführt werden, und die Interaktion zwischen den Vorverarbeitungsmethoden unklar sind. Dies kann zu einem langwierigen Versuch und Irrtum Prozess führen, bei dem verschiedene Vorverarbeitungspipelines bewertet werden, bis eine akzeptable Pipeline gefunden ist. Das ist insbesondere für unerfahrene Benutzer häufig der Fall. In letzter Zeit wurden einige Fortschritte auf dem Gebiet AutoML erzielt, die die Automatisierung dieser Auswahl als einen kleinen Teil ihres Ansatzes abdecken. Diese sind jedoch auf den Bereich des Clustering begrenzt vorhanden, und die meisten Ansätze schlagen nur eine einzige Vorverarbeitungsmethode vor oder berücksichtigen nur eine begrenzte Anzahl von Methoden in ihrem Konfigurationsraum. Ein Grund für diese Einschränkungen ist, dass sie sich auf einen Ende zu Ende Ansatz konzentrieren, bei dem neben einer geeigneten Vorverarbeitungspipeline auch ein Clustering-Algorithmus und dessen Parameter vorgeschlagen werden. Die AutoML-Ansätze betrachten die Vorverarbeitung bestenfalls als einen kleinen Teil und konzentrieren sich hauptsächlich auf die Modellerstellung. Im Gegensatz dazu konzentriert sich diese Arbeit hauptsächlich auf die Bewältigung der im ersten Absatz genannten Herausforderungen und die Verbesserung der Ergebnisse durch geeignete Vorverarbeitungspipelines, wobei ein Modell, in diesem Fall Clustering, zur Bewertung der Pipelines verwendet wird. Um die im ersten Abschnitt beschriebenen Herausforderungen zu entschärfen, besteht das allgemeine Ziel darin, genaue Vorschläge für Vorverarbeitungspipelines zu machen, die das Clustering Ergebnis verbessern. Um dies zu erreichen, ist es wichtig, Fehler in den Daten zu identifizieren und die Beziehung von deisen Fehlern zu Vorverarbeitungspipelines zu verstehen. Diese Arbeit leistet einen ersten Schritt in diese Richtung mit einem Konzept, wie eine Wissensbasis geschaffen werden kann, die die Auswirkungen von Vorverarbeitungspipelines auf Daten mit Fehlern genau untersucht und Fehler von Datensätzen identifizieren kann. Um Letzteres zu erreichen, werden Meta-Merkmale evaluiert, da sie eine gute Möglichkeit darstellen, ungesehene Datensätze und deren Fehler zu beschreiben. Eine solche Wissensbasis muss Informationen aus vielen verschiedenen Datensätzen enthalten, um verallgemeinern zu können. Aus diesem Grund werden synthetische Daten verwendet und mit Fehlern versehen, um einen nahezu unbegrenzten Datensatz zur Verfügung zu haben und eine genaue Bewertung vornehmen zu können, welche Fehler von welcher Pipeline gut verarbeitet werden. Durch diese Manipulationen werden die Daten verzerrt, Teile der Daten entfernt, um fehlende Werte zu erzeugen, und Ausreißer zu den Daten hinzugefügt. Aufgrund der im ersten Abschnitt genannten Herausforderungen ist es unmöglich, alle Kombinationen von Vorverarbeitungsmethoden und ihren Hyperparametern auf einen Datensatz anzuwenden, selbst wenn die Auswahl an Vorverarbeitungsmethoden klein ist. Stattdessen werden Pipelines generiert und während eines Optimierungsprozesses verbessert. Als Optimierung wird eine genetische Optimierung wird verwendet, weil sie eine hohe Flexibilität bietet und gut an die genannten Herausforderungen angepasst werden kann. Die Auswertung zeigt, dass der Optimierer für die meisten Datensätze eine Vorverarbeitungspipeline findet, die zu einer deutlichen Verbesserung der Clustering Ergebnisse im Vergleich zu den Ergebnissen ohne Vorverarbeitung führt. Die Verbesserung ist am signifikantesten für Daten mit schiefer Verteilung, während Datensätze, die nicht manipuliert wurden, die geringste Verbesserung aufweisen. Darüber hinaus zeigt die Auswertung des Optimierungsprozesses, dass eine gut funktionierende Pipeline relativ schnell gefunden wird, während die anschließende Verbesserung zwar vorhanden, aber vergleichsweise gering ist. Es wird gezeigt, dass das Ersetzen von fehlenden Werten mit dem KNN-Imputer am besten funktioniert. Andere Fehler in den Daten führen nicht zu einer bevorzugten Methode oder Pipeline. Was die Reihenfolge der Vorverarbeitungsmethoden innerhalb einer Pipeline betrifft, konnte kein signifikanter Unterschied nachgewiesen werden. Darüber hinaus wird gezeigt, dass Meta-Merkmale mit den Fehlern in den Daten korrelieren. Dies legt den Schluss nahe, dass es möglich ist, die Notwendigkeit einer Vorverarbeitung und die Identifizierung von Datenmängeln anhand der in dieser Arbeit verwendeten Meta-Merkmale zu bestimmen.