Ausreißererkennung im Data Mining

Question

Ich habe ein paar Fragen zur Erkennung von Ausreißern:

1. Können wir mit k-means Ausreißer finden und ist dies ein guter Ansatz?

2. Gibt es einen Clustering-Algorithmus, der keine Eingaben des Benutzers akzeptiert?

3. Können wir eine Support-Vektor-Maschine oder einen anderen überwachten Lernalgorithmus für die Ausreißererkennung verwenden?

4. Was sind die Vor- und Nachteile der einzelnen Ansätze?

Answer 1

Ich werde mich auf das beschränken, was ich für wesentlich halte, um einige Anhaltspunkte zu all Ihren Fragen zu geben, da dieses Thema in vielen Lehrbüchern behandelt wird und sie wahrscheinlich besser in separaten Fragen behandelt werden könnten.

1. Ich würde k-means nicht zum Aufspüren von Ausreißern in einem multivariaten Datensatz verwenden, und zwar aus dem einfachen Grund, dass der k-means-Algorithmus nicht für diesen Zweck ausgelegt ist: Sie werden immer eine Lösung erhalten, die die Gesamtsumme der Quadrate innerhalb eines Clusters minimiert (und somit die Summe der Quadrate zwischen den Clustern maximiert, da die Gesamtvarianz feststeht), und der/die Ausreißer werden nicht unbedingt einen eigenen Cluster definieren. Betrachten Sie das folgende Beispiel in R:

   set.seed(123)
   sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
                                         rnorm(n, mean[2],sd[2]))
   # generate three clouds of points, well separated in the 2D plane
   xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
               sim.xy(100, c(2.5,0), c(.4,.2)),
               sim.xy(100, c(1.25,.5), c(.3,.2)))
   xy[1,] <- c(0,2)     # convert 1st obs. to an outlying value
   km3 <- kmeans(xy, 3) # ask for three clusters
   km4 <- kmeans(xy, 4) # ask for four clusters

   Wie in der nächsten Abbildung zu sehen ist, wird der abweichende Wert als solcher nie wiedergefunden: Er wird immer zu einem der anderen Cluster gehören.

   

   Eine Möglichkeit wäre jedoch die Verwendung eines zweistufigen Ansatzes, bei dem die Extrempunkte (hier definiert als Vektoren, die weit von ihren Clusterzentren entfernt sind) iterativ entfernt werden, wie im folgenden Beitrag beschrieben: Verbesserung von K-Means durch Entfernung von Ausreißern (Hautamäki, et al.).

   Dies hat eine gewisse Ähnlichkeit mit dem, was in genetischen Studien getan wird, um Individuen zu erkennen und zu entfernen, die Genotypisierungsfehler aufweisen, oder Individuen, die Geschwister/Zwillinge sind (oder wenn wir eine Populationssubstruktur identifizieren wollen), während wir nur nicht verwandte Individuen behalten wollen; in diesem Fall verwenden wir eine multidimensionale Skalierung (was einer PCA entspricht, bis zu einer Konstante für die ersten beiden Achsen) und entfernen Beobachtungen über oder unter 6 SD auf einer der oberen 10 oder 20 Achsen (siehe zum Beispiel, Populationsstruktur und Eigenwertanalyse , Patterson et al., PLoS Genetics 2006 2(12)).

   Eine gängige Alternative ist die Verwendung geordneter robuster Mahalanobis-Distanzen, die (in einem QQ-Plot) gegen die erwarteten Quantile einer Chi-Quadrat-Verteilung aufgetragen werden können, wie in der folgenden Abhandlung erörtert:

   R.G. Garrett (1989). Das Chi-Quadrat-Diagramm: ein Instrument zur Erkennung multivariater Ausreißer . Zeitschrift für geochemische Exploration 32(1/3): 319-341.

   (Sie ist erhältlich in der mvoutlier R-Paket).

2. Das hängt davon ab, was Sie als Benutzereingabe bezeichnen. Ich interpretiere Ihre Frage dahingehend, ob ein Algorithmus automatisch eine Abstandsmatrix oder Rohdaten verarbeiten und bei einer optimalen Anzahl von Clustern anhalten kann. Wenn dies der Fall ist, können Sie für jeden distanzbasierten Partitionierungsalgorithmus jeden der verfügbaren Gültigkeitsindizes für die Clusteranalyse verwenden; einen guten Überblick finden Sie in

   Handl, J., Knowles, J., und Kell, D.B. (2005). Computergestützte Clustervalidierung in der postgenomischen Datenanalyse . Bioinformatik 21(15): 3201-3212.

   die ich am Kreuzvalidiert . Sie können z. B. mehrere Instanzen des Algorithmus auf verschiedenen Zufallsstichproben (unter Verwendung von Bootstrap) der Daten für einen Bereich von Clusterzahlen (z. B. k=1 bis 20) laufen lassen und k nach den optimierten Kriterien auswählen, die berücksichtigt wurden (durchschnittliche Silhouettenbreite, kophenetische Korrelation usw.); dies kann vollständig automatisiert werden, ohne dass Benutzereingaben erforderlich sind.

   Es gibt auch andere Formen des Clustering, die auf der Dichte (Cluster werden als Regionen betrachtet, in denen Objekte ungewöhnlich häufig vorkommen) oder der Verteilung (Cluster sind Gruppen von Objekten, die einer bestimmten Wahrscheinlichkeitsverteilung folgen) basieren. Das modellbasierte Clustering, wie es in Mclust ermöglicht beispielsweise die Identifizierung von Clustern in einem multivariaten Datensatz durch Aufspannen eines Formbereichs für die Varianz-Kovarianz-Matrix für eine unterschiedliche Anzahl von Clustern und die Auswahl des besten Modells entsprechend der BIC Kriterium.

3. Dies ist ein heißes Thema in der Klassifizierung, und einige Studien konzentrierten sich auf SVM, um Ausreißer zu erkennen, insbesondere wenn sie falsch klassifiziert werden. Eine einfache Google-Abfrage liefert eine Menge Treffer, z. B. Support Vector Machine zur Erkennung von Ausreißern bei der Vorhersage der Überlebenswahrscheinlichkeit von Brustkrebs von Thongkam et al. ( Vorlesungsnotizen in Computerwissenschaften 2008 4977/2008 99-109; dieser Artikel enthält einen Vergleich mit Ensemble-Methoden). Die Grundidee besteht darin, eine Einklassen-SVM zu verwenden, um die Hauptstruktur der Daten zu erfassen, indem eine multivariate (z. B. Gauß-) Verteilung an sie angepasst wird; Objekte, die auf oder knapp außerhalb der Grenze liegen, können als potenzielle Ausreißer betrachtet werden. (In gewissem Sinne würde ein dichtebasiertes Clustering ebenso gut funktionieren, da die Definition, was ein Ausreißer wirklich ist, angesichts einer erwarteten Verteilung einfacher ist).

   Andere Ansätze für unüberwachtes, halbüberwachtes oder überwachtes Lernen lassen sich leicht über Google finden, z. B.

   • Hodge, V.J. und Austin, J. A Übersicht über Methoden zur Erkennung von Ausreißern .
   • Vinueza, A. und Grudic, G.Z. Unüberwachte Ausreißererkennung und halb-überwachtes Lernen .
   • Escalante, H.J. A Vergleich von Algorithmen zur Erkennung von Ausreißern beim maschinellen Lernen .

   Ein verwandtes Thema ist Erkennung von Anomalien über die Sie eine Vielzahl von Dokumenten finden werden.

4. Das verdient wirklich eine neue (und wahrscheinlich gezieltere) Frage :-)

Answer 2

1) Können wir Ausreißer mit k-means finden, ist das ein guter Ansatz?

Clusterbasierte Ansätze sind optimal, um Cluster zu finden, und können verwendet werden, um Ausreißer zu erkennen, wie Nebenprodukte. Bei der Clusterbildung können sich Ausreißer auf die Lage der Clusterzentren auswirken und sogar zu einem Mikrocluster aggregieren. Diese Eigenschaften machen die clusterbasierten Ansätze für komplizierte Datenbanken unbrauchbar.

2) Gibt es einen Clustering-Algorithmus, der keine Eingaben des Benutzers akzeptiert?

Vielleicht können Sie einige wertvolle Erkenntnisse zu diesem Thema gewinnen: Dirichlet-Prozess-Clustering

Der Dirichlet-basierte Clustering-Algorithmus kann die Anzahl der Cluster entsprechend der Verteilung der Beobachtungsdaten adaptiv bestimmen.

3) Können wir eine Support-Vektor-Maschine oder einen anderen überwachten Lernalgorithmus für die Ausreißererkennung verwenden?

Jeder überwachte Lernalgorithmus benötigt eine ausreichende Anzahl von beschrifteten Trainingsdaten, um Klassifikatoren zu erstellen. Ein ausgewogener Trainingsdatensatz ist jedoch für reale Probleme wie die Erkennung von Eindringlingen oder die medizinische Diagnostik nicht immer verfügbar. Nach der Definition von Hawkins Ausreißer ("Identification of Outliers". Chapman and Hall, London, 1980) ist die Zahl der normalen Daten viel größer als die der Ausreißer. Die meisten Algorithmen des überwachten Lernens sind nicht in der Lage, einen effizienten Klassifikator für den oben genannten unausgewogenen Datensatz zu erstellen.

4) Was sind die Vor- und Nachteile der einzelnen Ansätze?

In den letzten Jahrzehnten reichen die Forschungsarbeiten zur Ausreißererkennung von der globalen Berechnung bis zur lokalen Analyse, und die Beschreibungen von Ausreißern variieren von binären Interpretationen bis zu probabilistischen Darstellungen. Je nach den Hypothesen der Ausreißererkennungsmodelle können die Algorithmen zur Ausreißererkennung in vier Arten unterteilt werden: Statistische Algorithmen, Cluster-basierte Algorithmen, Nearest Neighborhood-basierte Algorithmen und Klassifikator-basierte Algorithmen. Es gibt mehrere wertvolle Untersuchungen zur Ausreißererkennung:

• Hodge, V. und Austin, J. "A survey of outlier detection methodologies", Journal of Artificial Intelligence Review, 2004.

• Chandola, V. und Banerjee, A. und Kumar, V. "Outlier detection: A survey", ACM Computing Surveys, 2007.

Answer 3

1. k-means ist ziemlich empfindlich gegenüber Rauschen im Datensatz. Es funktioniert am besten, wenn Sie die Ausreißer vorher entfernen.

2. Nein. Jeder Clusteranalyse-Algorithmus, der behauptet, parameterfrei zu sein, ist in der Regel stark eingeschränkt und hat oft versteckte Parameter - ein gängiger Parameter ist beispielsweise die Distanzfunktion. Jeder flexible Clusteranalyse-Algorithmus akzeptiert zumindest eine benutzerdefinierte Abstandsfunktion.

3. Einklassen-Klassifikatoren sind ein beliebter Ansatz des maschinellen Lernens zur Erkennung von Ausreißern. Allerdings sind überwachte Ansätze nicht immer geeignet, um _zuvor_ ungesehene Objekte zu erkennen. Außerdem können sie zu stark angepasst werden, wenn die Daten bereits Ausreißer enthalten.

4. Jeder Ansatz hat seine Vor- und Nachteile, deshalb gibt es sie ja auch. In einer realen Umgebung müssen Sie die meisten von ihnen ausprobieren, um zu sehen, was für Ihre Daten und Ihre Umgebung funktioniert. Deshalb heißt die Ausreißererkennung auch Wissensentdeckung - müssen Sie erforschen, wenn Sie entdecken etwas neu ...

Answer 4

Vielleicht möchten Sie einen Blick auf die ELKI-Data-Mining-Rahmen . Es ist angeblich die größte Sammlung von Data-Mining-Algorithmen zur Ausreißererkennung. Es handelt sich um Open-Source-Software, die in Java implementiert ist und mehr als 20 Algorithmen zur Ausreißererkennung enthält. Siehe die Liste der verfügbaren Algorithmen .

Beachten Sie, dass die meisten dieser Algorithmen nicht auf Clustering basierend . Viele Clustering-Algorithmen (insbesondere k-means) versuchen, Instanzen "auf jeden Fall" zu clustern. Nur wenige Clustering-Algorithmen (z.B. DBSCAN) berücksichtigen tatsächlich den Fall, dass vielleicht nicht alle Instanzen in Cluster gehören! Bei einigen Algorithmen werden Ausreißer also tatsächlich verhindern. eine gute Clustering!