Eine Klassifikation ordnet Eingabewerte in mindestens zwei Ergebnisklassen ein. Sie findet im Rahmen des Data Mining oder Text Mining Anwendung. Unterschiedliche Algorithmen lassen sich im Rahmen einer Klassifikation einsetzen. Je nach gewähltem Algorithmus ist die Ergebnisqualität der Klassifikation zu bestimmen.
Einordnung der Klassifikation in den KDD-Prozess
Der Begriff der Klassifikation ist ein zentraler Anwendungsbereich des Data Mining innerhalb des Knowledge Discovery in Databases (KDD). KDD bezeichnet den „… non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data …“ [Fayyad et al. 1996]. Data Mining, als eine Phase des KDD-Prozesses, bezeichnet alle Aktivitäten, „… that find a logical or mathematical description, eventually of a complex nature, of patterns and regularities in a set of data …“ [Decker/Focardi 1995]. Die Aufgaben des Data Mining sind Klassifikation, Segmentierung, Prognose, Abhängigkeitsanalyse und Abweichungsanalyse [Alpar und Niederreichholz 2000, S. 9 ff.], in denen unterschiedliche Methoden genutzt werden können.
Eine Klassifikation ordnet einzelne Objekte systematisch in zwei oder mehr zuvor definierte Klassen, die eine hierarchische Struktur aufweisen können [Ferber 2003, S. 47]. Zu dem Begriff Klassifikation kann Kategorisierung synonym verwendet werden. Jedoch ist die Klassifikation im Rahmen des Data Mining und des Text Mining klar abgegrenzt und somit wird im Folgenden der Begriff Klassifikation verwendet. Dies geschieht auf Grund von Vergleichen zwischen Klasseneigenschaften und Objektmerkmalen. Der Klassifikator übernimmt die Funktion, die Objekte den jeweiligen Klassen zuzuordnen. Klassifikationsregeln dienen zur Prüfung der Datensätze anhand der vorgegebenen Kriterien. Mögliche Kriterien sind beispielsweise die Existenz oder eine minimale Häufigkeit eines Attributwertes. Sind die Kriterien erfüllt, wird der Datensatz als korrekt klassifiziert. Komplexe Regeln können durch die Verknüpfung von Attributen unter Verwendung logischer Operatoren gebildet werden. Die einzelnen oben genannten Aufgaben lassen sich nicht immer voneinander trennen [Alpar und Niederreichholz 2000, S. 9-13].
Anwendung der Klassifikation
Grundsätzlich sind die Prüfung der Datensätze und das Aufstellen von Klassifikationskriterien zu unterscheiden. Beides kann manuell oder automatisch vorgenommen werden. Eine manuelle Prüfung des Inhalts durch qualifizierte Personen liefert die besten Klassifikationsergebnisse, da diese zusätzlich die Abgrenzung der Klassen vornehmen können. Jedoch ist eine solche Prüfung mit hohem Aufwand verbunden, wodurch diese Vorgehensweise in der Regel keine Anwendung findet. Binäre Klassen lassen sich manuell erstellen, indem Regeln für diese formuliert und im Anschluss daran automatisch angewendet werden. Alternativ bilden bereits manuell klassifizierte Beispieldatensätze die Basis, um diese von lernenden Systemen internalisieren zu lassen, die anschließend eine automatische Klassifikation vornehmen [Joachims 1998, S. 1]. Im Folgenden werden Vertreter von Klassifikationsalgorithmen kurz vorgestellt.
Künstliche Neuronale Netze
Künstliche Neuronale Netze (KNN) sind in unüberwachte und überwachte Netze zu unterteilen [Zavrel 1996]. Die überwachten KNN, dies als Unterschied zu den unüberwachten, erlernen bestimmte Sachverhalte dadurch, dass diese auf deren Fehlklassifikation hingewiesen werden und beim nächsten Durchlauf Parameter ändern, um die Fehlklassifikation zu minimieren. Die in diesem Kontext am häufigsten genutzten Multilayer Perceptrons (MLP) werden durch mehrere Schichten charakterisiert. Dies ist zunächst eine Schicht, in der die Daten aufgenommen werden (Input), mindestens eine Zwischenschicht, in denen die Transformation vollzogen wird (Hidden Units), und eine Ausgabeschicht (Output) [Fritzke 1998, S. 25]. In jeder dieser Schichten liegen eine oder mehrere Informationsverarbeitungseinheiten (Neuronen). Zur Aktivierung des versteckten Neurons erfolgt eine Transformation der linearen Summe mit der Aktivierungsfunktion. Als Aktivierungsfunktion wird üblicherweise eine sigmoide (s-förmige) Funktion angewendet werden. Hierbei handelt es sich beispielsweise um die Fermifunktion.
Ein MLP wird zunächst in einer Lernphase trainiert, um in der anschließenden Klassifikationsphase die erlernte Klassifikation anzuwenden [Lanquillon 2001, S. 24]. Für die erfolgreiche Klassifikation sind die Ausgangstopologie und Ausgangsgewichtung von entscheidender Bedeutung sowie die verwendete Aktivierungsfunktion und die Lernmethode [Chamoni und Budde 1997, S. 65]. In der Lernphase kann die Backpropagation-Regel zur (Fein-)Justierung der Gewichte eingesetzt werden, wodurch die Klassifikationsfehler in der Outputschicht minimiert werden. Die Klassifikation ergibt sich dabei aus der Kodierung der Outputneuronen als entsprechende Klassen. Neuronale Netzwerke zeichnen sich durch die Fähigkeit aus, in gewissem Maße zu abstrahieren und weisen hierdurch eine höhere Fehlertoleranz auf. Zudem kann eine internalisierte Klassifikation modifiziert werden, wodurch neue Sachverhalte erlernt werden [Chamoni und Budde 1997, S. 93]. Das Lernen ohne spezielle Instruktionen und die parallele Verarbeitung sind weitere Kennzeichen der KNN. Nachteilig ist der Sachverhalt, dass die KNN eine Blackbox darstellen, weil keine Regeln aus ihnen abgeleitet werden können. Problematisch bei den überwachten Ansätzen ist die Auswahl bezüglich Beschaffenheit und Umfang der Trainingsdatensätze. Sind diese nicht repräsentativ, kann keine zufriedenstellende Klassifikation vorgenommen werden. Zudem besteht die Möglichkeit, dass ein KNN die Fähigkeit der Generalisierung verliert, wenn die Trainingsbeispiele zu oft wiederholt werden.
Support Vector Machines
Eine Support Vector Machine (SVM) verwendet eine Hyperebene zur Klassifikation. Diese wird an der Stelle einer Datensammlung eingeführt, an der der größte Abstand zwischen den Datensätzen gemessen werden kann. Die eingefügte Ebene ist die Lösung eines formulierten Optimierungsproblems [Joachim 1998]. Die Datenpunkte eines linear separierbaren Zweiklassenproblems im n‑dimensionalen Raum seien durch eine Hyperebene ohne jeglichen Fehler optimal zu teilen. Da der Klassifikator in der Regel auf wenigen Supportvektoren basiert, wird eine gute Performance erreicht. SVMs sind robust gegenüber dem Problem des Overfitting. Dabei handelt es sich um eine starke Anpassung der durch den Algorithmus identifizierten Strukturen an den Trainingsdatenbestand, was eine Nutzung auf realen Daten oftmals unmöglich macht. Des Weiteren benötigen sie keine Attributreduktion und auch im Grundmodell kein Parametertuning als Vorverarbeitung, das gegebenenfalls eine Ergebnisverfälschung erzeugt.
Entscheidungsbaumverfahren
Bei einem Entscheidungsbaum repräsentieren die Blätter die entsprechenden Kategorien, nach denen Datensätze klassifiziert werden. Der Aufbau des Baumes resultiert aus Tests, durch welche die Gewichte für die Datensätze bestimmt werden konnten. Beispielsweise kann die Entropie als Maß beim Baumaufbau angewendet werden. Bei der konkreten Anwendung werden die Blätter des Baumes solange mit der Datensammlung abgeglichen, bis eine entsprechende Klasse gefunden ist, in die ein Datensatz eingefügt werden kann [Sebastiani 2002, S. 22 ff.]. Der Aufbau eines Baumes führt dazu, dass alle Attribute nacheinander abgearbeitet werden. So lassen sich Regeln über die Klassifikation aus den Pfaden ableiten, die bei der Anwendung durchwandert wurden. Nachteilig ist beim Entscheidungsbaum die Tendenz zum Overfitting. Um diesem Problem zu begegnen, muss eine Generalisierung, zum Beispiel durch Pruning, durchgeführt werden. Bedingt durch seine Struktur sind die generierten Regeln eines solchen Baumes vom Menschen gut nachzuvollziehen.
Naive-Bayes-Algorithmus
Bei Naive-Bayes-Verfahren wird von der Annahme ausgegangen, dass ein Datensatz mit einer bestimmten Wahrscheinlichkeit durch einen spezifizierten Vektor repräsentiert wird und dass dadurch dieser Datensatz mit einer bestimmten Wahrscheinlichkeit in eine entsprechende Klasse eingeordnet werden kann. Es gilt dabei die Unabhängigkeitsannahme für die dazu verwendeten Attribute. Als Ausprägungen bestehen für dieses Verfahren unterschiedliche Varianten, die auf der zuvor dargestellten Annahme basieren. Diese Wahrscheinlichkeiten sind jedoch unbekannt und können dementsprechend nur abgeschätzt werden [Sebastiani 2002, S. 20 ff.].
Bewertung der Klassifikationsgüte
Die Ergebnisqualität einer Klassifikation lässt sich durch eine Analyse der Ergebnismenge ermitteln. Die Qualität einer Ergebnismenge E lässt sich über Recall und Precision bestimmen. In einer Datensammlung werden bezüglich einer Abfrage die korrekten Datensätze {I} von den falschen Datensätzen {le} unterschieden. Da in der Ergebnismenge neben einem Teil der korrekten Datensätze auch falsche Dokumente aufgeführt sind, sind diese Mengen nicht disjunkt. Werden die korrekten Datensätze in der Ergebnismenge in ein Verhältnis zu allen korrekten Datensätzen beziehungsweise zu der gesamten Ergebnismenge gesetzt, werden hierdurch Precision und Recall bestimmt [Berry et al. 1995]. Die beiden Qualitätsmaße stehen in einer Wechselwirkung zueinander [Abramowicz et al. 2002, S. 80].
Um die Qualitätsmaße zu ermitteln, sind zunächst die Mengen {Ie} und {I} zu bestimmen. Dieses kann mit hohem Aufwand verbunden sein, da jeder Datensatz vom Nutzer zu bewerten ist. Als alternatives Maß lässt sich zur Bewertung der Algorithmen das Fß-Maß von van Rijsbergen heranziehen. Es handelt sich um eine Kombination der beiden Maße Recall ρ und Precision π.
Der Parameter ß steht dabei für die relative Gewichtung von Recall und Precision. Für 0 < ß < 1 wird dabei π höher gewichtet, für ß > 1 ρ. Im Falle ß=1 sind beide Werte gleichberechtigt. Dabei bezeichnet der Recall ρ das Verhältnis der als interessant eingestuften und vom System erkannten Dokumente zu allen interessant eingestuften. Die Precision π drückt das Verhältnis zu allen vom System als interessant erkannten Datensätzen aus. Die Werte von Fß liegen zwischen 0 und 1, wobei ein größerer Fß-Wert ein besseres Klassifikationsergebnis bedeutet [Sebastiani 2002].
Literatur
Abramowicz, W.; Kalczyński, P.; Weçel, K.: Filtering the Web to Feed Data Warehouses. Springer-Verlag: London et al. 2002.
Alpar, P.; Niederreichholz, J.: Data Mining im praktischen Einsatz: Verfahren und Anwendungsfälle für Marketing, Vertrieb, Controlling und Kundenunterstützung. Vieweg-Verlag: Wiesbaden 2000.
Berry, M.; Dumais, S.; Letsche, T.: Computational Methods for Intelligent Information Access. http://web.eecs.utk.edu/~mberry/sc95/sc95.html. Abgerufen am 06.10.2016
Chamoni, P.; Budde, C.: Methoden und Verfahren des Data Mining. Diskussionsbeiträge des Fachbereichs Wirtschaftswissenschaft der Gerhard-Mercator-Universität Gesamthochschule Duisburg, Nr. 232. Duisburg 1997.
Decker, K.; Focardi, S.: Technology overview: a report on data mining. Swiss Federal Institute of Technology (ETH Zurich) Technical Report CSCS TR-95-02, Zürich 1995.
Fayyad, U.; Piatetsky-Shapiro, G.; Smyth, P.: From Data Mining to Knowledge Discovery. An Overview. In: Fayyad, U.; Piatetsky-Shapiro, G.; Smyth, P.; Uthurusamy, R. (Hrsg.): Advances in Knowledge Discovery and Data Mining. The MIT Press (1996): Menlo Park et al., S. 1-34
Ferber, R.: Information Retrieval – Suchmodelle und Data-Mining-Verfahren für Textsammlungen und das Web. Dpunkt Verlag: Heidelberg 2003.
Fritzke, B.: Vektorbasierte Neuronale Netze. Habilitationsschrift. Shaker Verlag: Aachen 1998.
Joachims, T.: Text Categorization with Support Vector Machines: Learning with Many Relevant Features. http://www.cs.cornell.edu/people/tj/publications/joachims_98a.pdf. Abgerufen am 06.10.2016
Lanquillon, C.: Enhancing Text Classification to Improve Information Filtering. http://diglib.uni-magdeburg.de/Dissertationen/2001/carlanquillon.pdf. Abgerufen am 06.10.2016
Sebastiani, F.: Machine Learning in Automated Text Categorization. In: ACM Computing Surveys 34 (2002), S. 1-47
Zavrel, J.: Neural navigation interfaces for information retrieval. In: Artificial Intelligence Review archive 10 (1996), S. 477- 504
