Ireguläre Darstellung von k-Means-Clustern, Ausreißerentfernung

8

Hallo, ich arbeite daran, Netzwerkdaten aus dem 1999-dpa-Datensatz zu sammeln. Leider bekomme ich nicht wirklich gruppierte Daten, nicht im Vergleich zu einigen der Literatur, mit den gleichen Techniken und Methoden.

Meine Daten kommen so heraus:

Wie Sie sehen können, ist es nicht sehr gruppiert. Dies liegt an vielen Ausreißern (Rauschen) im Dataset. Ich habe einige Ausreißer-Entfernungstechniken untersucht, aber nichts, was ich bisher versucht habe, reinigt die Daten wirklich. Eine der Methoden, die ich ausprobiert habe:

%Vor%

Im ersten Lauf wurden 48 Zeilen aus den 1000 normalisierten zufälligen Zeilen entfernt, die aus dem vollständigen Dataset ausgewählt wurden.

Dies ist das vollständige Skript, das ich für die Daten verwendet habe:

%Vor%

Dies sind zwei verschiedene Cluster aus der Ausgabe:

Wie Sie sehen, sind die Daten sauberer und gruppierter als das Original. Ich denke jedoch immer noch, dass eine bessere Methode verwendet werden kann.

Wenn ich zum Beispiel das gesamte Clustering beobachte, habe ich immer noch eine Menge Rauschen (Ausreißer) aus dem Datensatz. Wie man hier sehen kann:

Ich brauche die Ausreißerzeilen zur späteren Klassifizierung in einen separaten Datensatz (nur aus dem Cluster entfernt)

Hier ist eine Verknüpfung zum dpara-Dataset. Bitte beachten Sie, dass der 10% -Datensatz eine signifikante Reduzierung der Spalten hatte, eine Mehrheit der Spalten, die 0 oder 1 durchlaufen, wurde entfernt (42 Spalten zu 6 Spalten) :

Ссылка

BEARBEITEN

Im Datensatz gespeicherte Spalten sind:

%Vor%

RE-EDIT:

Basierend auf Diskussionen mit Anony-Mousse und seiner Antwort, könnte es eine Möglichkeit geben, das Rauschen im Clustering mit K-Medoids zu reduzieren. Ссылка . Ich hoffe, dass der Code, den ich derzeit habe, nicht stark verändert wird, aber ich weiß noch nicht, wie ich ihn implementieren soll, um zu testen, ob dadurch das Rauschen deutlich reduziert wird. Wenn jemand mir ein funktionierendes Beispiel zeigen kann, wird dies als Antwort akzeptiert.

    
Jungle Boogie 02.11.2014, 10:20
quelle

2 Antworten

9

Das Wichtigste zuerst: Sie verlangen hier viel. Zukünftige Referenz: Versuchen Sie, Ihr Problem in kleineren Brocken aufzubrechen und stellen Sie mehrere Fragen. Dies erhöht Ihre Chancen auf Antworten (und kostet Sie nicht 400 Ruf!).

Zum Glück verstehe ich Ihre missliche Lage und liebe diese Art von Frage!

Abgesehen von den möglichen Problemen dieses Datasets mit k-means, ist diese Frage immer noch generisch genug, um sie auch auf andere Datasets anzuwenden (und daher suchen Googler hier nach einer ähnlichen Sache), also lass uns voran gehen und das gelöst bekommen / p>

Mein Vorschlag ist, diese Antwort zu bearbeiten, bis Sie einigermaßen befriedigende Ergebnisse erhalten.

Anzahl der Cluster

Schritt 1 eines Clusterproblems: Wie viele Cluster sollen ausgewählt werden? Es gibt ein paar Methoden, mit denen Sie die richtige Anzahl von Clustern auswählen können. Es gibt eine nette Wiki-Seite dazu, die alle folgenden Methoden enthält (und ein paar mehr).

Sichtprüfung

Es mag albern klingen, aber wenn Sie gut getrennte Daten haben, kann Ihnen ein einfacher Plot bereits (ungefähr) sagen, wie viele Cluster Sie brauchen, nur indem Sie suchen.

Pros:

  • schnell
  • einfach
  • funktioniert gut in gut getrennten Clustern in relativ kleinen Datensätzen

Nachteile:

  • und dreckig
  • erfordert Benutzerinteraktion
  • es ist leicht, kleinere Cluster zu übersehen
  • Daten mit weniger gut getrennten Clustern, oder sehr viele von ihnen, sind mit dieser Methode schwer zu erreichen
  • es ist alles eher subjektiv - die nächste Person könnte einen anderen Betrag wählen als Sie.

Silhouettenplot

Wie in einer Ihrer anderen Fragen angegeben, machen Sie eine silhouettes Plot hilft Ihnen, eine bessere Entscheidung über die richtige Anzahl von Clustern in Ihren Daten zu treffen.

Pros:

  • relativ einfach
  • reduziert die Subjektivität durch Verwendung statistischer Kennzahlen
  • intuitive Art, die Qualität der Wahl darzustellen

Nachteile:

  • erfordert Benutzerinteraktion
  • Im Extremfall, wenn Sie so viele Cluster aufnehmen, wie es Datenpunkte gibt, wird Ihnen ein Silhouettenplot zeigen, dass das die beste Wahl ist
  • es ist immer noch eher subjektiv, nicht auf statistischen Mitteln basiert
  • kann rechenintensiv sein

Ellenbogenmethode

Wie bei der Methode "Silhouettenplot" führen Sie kmeans wiederholt mit jeweils einer größeren Anzahl von Clustern aus und Sie sehen, wie viel der Gesamtvarianz in den Daten durch die von diesem kmeans run ausgewählten Cluster erklärt wird . Es wird eine Reihe von Clustern geben, bei denen die Menge der erklärten Varianz plötzlich viel weniger zunehmen wird als bei irgendeiner der vorherigen Auswahl der Cluster (der "Ellbogen"). Der Ellenbogen ist dann statistisch gesehen die beste Wahl für die Anzahl der Cluster.

Pros:

  • keine Benutzerinteraktion erforderlich - der Ellbogen kann automatisch ausgewählt werden
  • statistisch mehr Klang als jede der oben genannten Methoden

Nachteile:

  • etwas kompliziert
  • immer noch subjektiv, da die Definition des "Ellbogens" von subjektiv gewählten Parametern abhängt
  • kann rechenintensiv sein

Ausreißer

Sobald Sie die Anzahl der Cluster mit einer der oben genannten Methoden ausgewählt haben, ist es an der Zeit, Ausreißer zu erkennen, um zu sehen, ob sich die Qualität Ihrer Cluster verbessert.

Ich würde mit einem zweistufigen iterativen Ansatz beginnen, indem ich die Ellbogenmethode verwende. Im Pseudo-Matlab:

%Vor%

Der schwierige Teil bestimmt offensichtlich, ob you are satisfied . Dies ist der Schlüssel zur Effektivität des Algorithmus. Die grobe Struktur von dieser Teil

%Vor%

wäre so etwas

%Vor%

situation has improved , wenn weniger Ausreißer vorhanden sind, oder die Varianz für alle Optionen von N erklärt ist besser als während der vorherigen Schleife in while . Daran ist auch etwas dran.

Wie auch immer, viel mehr als ein erster Versuch würde ich das nicht nennen. Wenn jemand hier Unvollständigkeiten, Fehler oder Schlupflöcher sieht, bitte kommentieren oder bearbeiten

    
Rody Oldenhuis 23.05.2017, 10:32
quelle
10

Beachten Sie, dass die Verwendung dieses Datasets entmutigt ist:

Dieser Datensatz enthält Fehler: Datensatz KDD Cup '99 (Network Intrusion) als schädlich

Überdenken Sie die Verwendung eines anderen Algorithmus. k-means ist nicht wirklich geeignet für gemischte Daten, bei denen viele Attribute diskret sind und sehr unterschiedliche Skalen haben. K-means muss vernünftige Mittel berechnen können. Und für einen binären Vektor ist "0.5" kein sinnvoller Mittelwert, er sollte entweder 0 oder 1 sein.

Außerdem mag k-means Ausreißer nicht zu sehr.

Stellen Sie beim Plotten sicher, dass sie gleichmäßig skaliert werden, oder das Ergebnis wird falsch aussehen. Ihre X-Achse hat eine Länge von etwa 0,9, Ihre Y-Achse nur 0,2 - kein Wunder, dass sie gequetscht aussehen.

Alles in allem, hat der Datensatz vielleicht keine k-means-artigen Cluster? Sie sollten auf jeden Fall dichtebasierte Methoden ausprobieren (weil diese mit umgehen können ) Ausreißer) wie DBSCAN. Aber nach den Visualisierungen, die Sie hinzugefügt haben, würde ich sagen, dass es höchstens 4-5 Cluster hat, und sie sind nicht wirklich interessant. Sie können wahrscheinlich mit einer Anzahl von Schwellen in einigen Dimensionen erfasst werden.

Hier ist eine Visualisierung des Datensatzes nach der Z-Normalisierung, visualisiert in parallelen Koordinaten, mit 5000 Samples. Hellgrün ist normal.

Sie können deutlich bestimmte Eigenschaften des Datensatzes sehen. Alle Angriffe unterscheiden sich deutlich in den Attributen 3 und 4 (count und srv_count) und auch sehr konzentriert in dst_host_count und dst_host_srv_count.

Ich habe auch OPTICS auf diesem Datensatz ausgeführt. Es fand eine Reihe von Clustern, die meisten davon im weinfarbenen Angriffsmuster. Aber sie sind nicht wirklich interessant. Wenn Sie 10 verschiedene Hosts ping-flooding haben, werden sie 10 Cluster bilden.

Sie können sehr gut sehen, dass es OPTICS gelungen ist, eine Reihe dieser Angriffe zu clustern. Es hat den ganzen orangefarbenen Kram verfehlt (vielleicht, wenn ich die Mint niedriger gesetzt hätte, ist es ziemlich weit ausgebreitet), aber es hat sogar * eine Struktur innerhalb des weinfarbenen Angriffs entdeckt und es in eine Anzahl von verschiedenen Ereignissen aufgeteilt.

Um wirklich für diesen Datensatz sinnvoll zu sein, sollten Sie mit der Feature-Extraktion beginnen, indem Sie beispielsweise solche Ping-Flood-Verbindungsversuche in ein Aggregatereignis .

Beachten Sie auch, dass dies ein unrealistisches Szenario ist .

  1. Es gibt bekannte Muster bei Angriffen, insbesondere Port-Scans . Diese werden am besten mit einem speziellen Port-Scan-Detektor erkannt, nicht mit lernen .
  2. Die simulierten Daten haben viele völlig sinnlose "Angriffe" simuliert. Zum Beispiel Schlumpfangriff aus den 90ern, ist & gt; 50% des Datensatzes und Syn flood ist ein weiterer 20%; während normaler Verkehr ist & lt; 20%!
  3. Für diese Art von Angriffen gibt es wohlbekannte Signaturen.
  4. Viele moderne Angriffe (zum Beispiel SQL-Injection) fließen mit normalem HTTP-Verkehr und werden im rohen Verkehrsmuster nicht anormal angezeigt.

Nur verwenden Sie diese Daten nicht zur Klassifizierung oder Ausreißererkennung . Tu es einfach nicht.

Zitieren Sie den obigen KDNuggets-Link:

  

Daher empfehlen wir dringend

     

(1) alle Forscher hören auf, den Datensatz KDD Cup '99 zu verwenden,

     

(2) Die KDD-Cup- und UCI-Websites enthalten eine Warnung auf der KDD-Cup '99-Datensatz-Webseite, die Forscher darüber informiert, dass es bekannte Probleme mit dem Datensatz gibt, und

     

(3) Peer-Reviewer für Konferenzen und Fachzeitschriften (wie sie in der Netzwerksicherheitsgemeinde üblich sind) (oder sogar direkt ablehnen ), wobei die Ergebnisse ausschließlich aus dem Datensatz KDD Cup '99 stammen.

Dies sind weder echte noch realistische Daten. Holen Sie sich etwas anderes.

    
Anony-Mousse 07.07.2012 23:18
quelle