Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph
Diese Arbeit zeigt, dass die Anwendung standardmäßiger Graphalgorithmen, wie etwa PageRank, k-Core-Zerlegung und Clustering-Koeffizienten-Analyse, auf den internen k-nächsten-Nachbarn-Graphen, der durch UMAP konstruiert wurde, einen leistungsstarken, komplementären Ansatz für das Verständnis hochdimensionaler Daten darstellt, der oft spezialisierten Methoden entspricht oder diese sogar übertrifft.
Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen
Stellen Sie sich vor, Sie haben eine riesige, chaotische Kiste mit 60.000 Fotos – einige sind handgeschriebene Zahlen, andere sind Bilder von Kleidung wie Taschen, Hemden und Schuhen. Sie wollen die Muster erkennen, also benutzen Sie ein superintelligentes Werkzeug namens UMAP, um dieses 3D- (oder sogar noch höherdimensionalen) Chaos auf ein flaches 2D-Blatt Papier zu quetschen.
Normalerweise hören die Leute genau an diesem Punkt auf. Sie betrachten den hübschen 2D-Streudiagramm, kneifen die Augen zusammen, um die Punkte zu sehen, und sagen: „Okay, ich sehe hier einen Cluster von Taschen.“ Aber dieses Paper argumentiert, dass UMAP seine beste Geheimwaffe wegwirft, sobald es dieses Bild zeichnet.
Bevor UMAP die Daten auf das Papier quetscht, baut es einen verborgenen kNN-Graphen auf. Stellen Sie sich diesen Graphen als ein massives, unsichtbares Netz aus Freundschaften vor. In diesem Netz hat jedes Foto genau 15 Freunde (seine „k-nächsten Nachbarn“), von denen es glaubt, dass sie ihm am ähnlichsten sind. Aber hier ist der Clou: Während jedes Foto sich 15 Freunde auswählt, wird nicht jedes Foto auch von 15 anderen ausgewählt. Einige Fotos sind so seltsam oder einzigartig, dass fast niemand sie als Freund wählt. Andere sind so „durchschnittlich“ oder „prototypisch“, dass hunderte anderer Fotos sie als ihren besten Match nominieren.
Die Autoren sagen: „Werfen Sie dieses Netz nicht weg! Es ist eigentlich ehrlicher als das 2D-Bild.“ Sie haben drei coole Wege getestet, um mit diesem Web zu spielen, um die Daten besser zu verstehen als das 2D-Bild es je könnte.
1. Das „beliebteste Kind“ (PageRank)
Die Frage: Welche Fotos sind die wahren „Repräsentanten“ ihrer Gruppe?
Der alte Weg: Die Leute wählen normalerweise das Foto, das dem Zentrum eines Klumpens auf der 2D-Karte am nächsten liegt. Aber die 2D-Karte ist verzerrt! Ein in die Länge gezogener Klumpen könnte ein „Zentrum“ haben, das in Wirklichkeit gar kein echtes Foto darstellt.
Der neue Weg: Die Autoren verwendeten einen Algorithmus namens PageRank (derselbe, mit dem Google Webseiten rankt). In diesem Netz erhält ein Foto einen hohen Score nicht nur, weil viele Leute es ausgewählt haben, sondern weil andere populäre Fotos es ausgewählt haben.
Das Ergebnis:
- Die am höchsten bewerteten Fotos sahen aus wie die perfekten, Lehrbuch-Beispiele einer Klasse (wie eine klassische „6“ oder eine Standard-Umhängetasche).
- Die am niedrigsten bewerteten Fotos waren die seltsamen, atypischen Exemplare.
- Der Beweis: Als sie 200 Top-Fotos auswählten, um das gesamte Datenset zu repräsentieren, waren diese PageRank-Auswahlen viel besser darin, die Klassen auszubalancieren, als die alte Methode (k-Medoids). Die alte Methode wählte ständig zu viele Fotos aus den unordentlichen, weit gestreuten Gruppen aus, während PageRank eine faire Mischung lieferte.
- Wie sicher sind sie sich? Sehr. Sie führten dies an 60.000 Bildern durch und fanden heraus, dass die Ergebnisse stabil blieben, selbst wenn sie die Anzahl der Freunde von 5 auf 100 änderten. Die Rankings blieben fast identisch (Korrelation um 0,95).
2. „Kern vs. Rand“ (k-Core Dekomposition)
Die Frage: Welche Fotos sind das „Herz“ einer Gruppe und welche hängen nur am Rande herum?
Der alte Weg: Werkzeuge wie HDBSCAN geben Ihnen ein einfaches Label: „Das ist eine Tasche.“ Aber es sagt Ihnen nicht, ob dies eine klassische Tasche ist oder eine seltsame, unscharfe Tasche, die die Definition gerade so erfüllt.
Der neue Weg: Die Autoren nutzten die k-Core Dekomposition. Stellen Sie sich vor, man schält eine Zwiebel. Man entfernt immer wieder die Fotos, die die wenigsten eingehenden Nominierungen (die wenigsten populären) haben. Diejenigen, die im innersten Zentrum übrig bleiben, sind der „Kern“.
Das Ergebnis:
- Sie fanden heraus, dass die „Kern“-Fotos die am stärksten selbstähnlichen und konsistentesten waren. Im Fall der Kategorie „1“ bei handgeschriebenen Zahlen bestand der Kern beispielsweise nur aus perfekten „1er“.
- In der Kategorie „Tasche“ enthüllte der Kern deutliche Untergruppen: Umhängetaschen, Gürteltaschen und unterschiedliche Texturen. Die 2D-Karte zeigte nur einen großen, verschwommenen Klumpen von „Taschen“, aber der Graph schälte dies in Schichten auf, um Sub-Gruppen zu zeigen.
Der Beweis: Sie verglichen dies mit HDBSCAN. HDBSCAN war gut darin zu sagen: „Ist das eine Tasche?“, aber schlecht darin zu sagen: „Wie zentral ist diese Tasche?“ Die Graph-Methode lieferte eine abgestufte Skala der „Kernigkeit“, die die alten Werkzeuge übersehen hatten.
3. Der „Geheimbund“ (Clustering Coefficient)
Die Frage: Gibt es winzige, extrem eng vernetzte Gruppen von Fotos, die sich exakt gegenseitig ähneln?
Der alte Weg: Betrachtet man das 2D-Bild, sieht eine Gruppe von „6er“ wie eine einzige große, solide Masse aus.
Der neue Weg: Der Clustering Coefficient sucht nach „Dreiecken“ im Netz. Wenn Foto A Foto B als Freund betrachtet, und Foto B Foto C als Freund betrachtet, betrachtet Foto A dann auch Foto C als Freund? Wenn ja, ist das ein eng vernetztes Clique.
Das Ergebnis:
- Diese Methode fand „Mikro-Nachbarschaften“ von Fotos, die sehr spezifische Stile teilten. Für die Zahl „6“ isolierte sie Gruppen basierend auf winzigen Details: Einige hatten eine große Schlaufe, andere waren geneigt, wieder andere hatten eine spezifische Krümmung.
Der Beweis: Die obersten 5 % der Fotos mit der höchsten „Clique-ness“ hatten eine Reinheitsrate von 98 % (was bedeutet, dass fast alle ihre Nachbarn derselben Art waren). Dies ist wesentlich höher als bei einer zufälligen Auswahl.
Das Fazit
Das Paper sagt nicht, dass das 2D-Bild nutzlos ist. Es sagt nur, dass es unvollständig ist. Indem man das verborgene Netz der Freundschaften (den kNN-Graphen) behält und darauf Standard-Graph-Algorithmen anwendet, erhält man eine viel klarere, ehrlichere Sicht auf seine Daten.
Wie sicher sind sie sich?
Sie testeten dies an zwei massiven, Standard-Datensätzen (MNIST und Fashion MNIST) mit jeweils 60.000 Bildern. Die Ergebnisse waren schnell (in unter einer Sekunde auf einem Laptop berechenbar) und die Mathematik hielt den besten bestehenden Werkzeugen stand. Sie legen nahe, dass dieser Ansatz auch für andere ähnliche Tools funktioniert, haben dies jedoch nur für diese spezifischen Bildsätze bewiesen. Sie behaupten nicht, dass es jedes Datenproblem löst, aber sie sind sich ziemlich sicher, dass es ein viel besseres Maß an „Sensemaking“ ist, als nur auf die 2D-Punkte zu starren.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.