UMAP metric

[mbruhns]

https://github.com/donEnno/gamma_delta/blob/8b0bae34c96adf17bd1084e38a4335d84fd32118/pipeline2.py#L107

Habe ich ein Brett vor'm Kopf, oder benutzt du für die Erstellung der UMAP gerade gar nicht deine Distanzmatrix?

[donEnno]

umap.UMAP().fit_transform(dm) benutzt die dm als Objekt, dass zu fit_transformen ist und dm ist eben die Distanzmatrix. Ich sehe keinen Fehler, aber das können wir gleich ja auch nochmal besprechen.

[donEnno]

Update NWA kann negative Similaritäten ausgeben. Es gibt Varianten wo das nicht der Fall ist, aber bei uns geht das. Es gibt sowohl in PAM70 als auch in BLOSUM45 negative Werte, wobei es nur sehr wenige sind. Wenn wir hier 1/x_i + 1 machen, dann kommt ja immer noch was negatives raus und das wäre schlecht, da wir ja in [0 1] kommen wollen.

Wenn man eine MinMaxNormalization macht a la zi = (xi – min(x)) / (max(x) – min(x)) kriegen wir alles in [0 1]. Hier sind dann aber Werte nahe Null die vorher auch klein waren und Werte nahe 1 die vorher schon hoch waren. Könnte man hier nicht einfach 1-z_i machen, um diesen Effekt umzukehren? Das ganze passiert spaltenweise, was dann besonderes hohe Similarity scores global gesehen relativieren würde. Nimmt man als min und max das global minimum und maximum, ergibt das aber auch sehr wenig Sinn.

Auch ist die Diagonale bisher 0, was für die Ähnlichkeiten weniger Sinn macht, aber das könnte man für die Distanzen ja genau so übernehmen.

Außerdem Frage ich mich, warum man die DM nicht als Feature-Matrix auffassen kann. Jeder Datenpunkt hat eben so viele Feature, wie es Datenpunkte gibt und die Einträge sind dann eben die Distanzen. Statt Genexpressionen pro Gen pro Zelle eben Distanzen pro Sequenz pro Sequenz.

In den knn_precomputed Beispielen, wird immer ein kNN Übergeben, was bei uns die DM und somit die data selber wäre. Aktuell wäre glaube ich ´metric='precomputed´ der bessere Anastz, denn auf der UMAP Seite steht

If the metric is ‘precomputed’ X must be a square distance matrix. Otherwise it contains a sample per row.

Was ja bei uns der Fall ist. Vielleicht kann man später dann die DM als Data übergeben und entsprechende kNN-Matrizen dann als precomputed_knn.

[donEnno]

Auf stackoverflow habe ich einen Post gefunden, der das Thema ein wenig behandelt:

Yes, there is a most general way to change between similarity and distance: a strictly monotone decreasing function f(x).

[...] because the relation between similarity and distance is that one decreases when the other increases.

Examples:

These are some well-known strictly monotone decreasing candidates that work for non-negative similarities or distances:

f(x) = 1 / (a + x) f(x) = exp(- x^a) f(x) = arccot(ax)

Nach vorherigem Kommentar, blieben dann nur die negativen Similarities zu klären. Fasst man aber die MinMaxNormalization als f(x) auf sollte das ja streng monoton sein, auch für negative Werte. Es bleibt also die Verhältnismäßigkeit zwischen besonders hohen Similarity-Scores zu klären.

Und jetzt, nach wahrscheinlich zu langem Überlegen, arbeite ich weiter an der kNN-Classification und der log. Regression Classification.

[mbruhns]

Jetzt kam imr ein Meeting dazwischen bevor ich antworten konnte und zack kam der nächste Post von dir 😄

Wenn man eine MinMaxNormalization macht a la zi= (xi – min(x)) / (max(x) – min(x)) kriegen wir alles in [0 1]. Hier sind dann aber Werte nahe Null die vorher auch klein waren und Werte nahe 1 die vorher schon hoch waren.

Das stimmt, ich meinte aber auch 1/(1+x) (siehe deinen Folgepost).

In den knn_precomputed Beispielen, wird immer ein kNN Übergeben, was bei uns die DM und somit die data selber wäre. Aktuell wäre glaube ich ´metric='precomputed´ der bessere Anastz, denn auf der UMAP Seite steht

Genau darauf wollte ich hinaus, hatte die Details der Dokumentation nicht im Kopf.

Außerdem Frage ich mich, warum man die DM nicht als Feature-Matrix auffassen kann.

Die Feature-Matrix würde "absolute" Werte enthalten (Beispiel Genexpression), also Koordinaten in einem (euklidischen) Raum. Die DM hingegen enthält Informationen über die relative Lage der einzelnen Samples im Raum zueinander (unter Metrik M ist das Markerprofil der Samples so verschieden). Ergibt das Sinn?

Bzgl. des generellen Problems: schau bitte noch einmal genau in die entsprechenden Implementierungen, was die jeweils erwarten. Revant meinte gerade, dass einige Louvain-Implementierungen auch genau eine Affinitätsmatrix erwarten, das kommt aber immer auf die Bibliothek an. Also schauen was Networkit für die Erstellung eines Graphen und das finden der Cluster erwartet.

Bzgl. der Umwandlung der Ähnlichkeitsmatrix in eine Distanzmatrix: eventuell bietet sich auch die Levenshtein-Distanz an, die müsste man jedoch komplett neu berechnen. Hier noch mehr Informationen dazu: https://math.mit.edu/classes/18.417/Slides/alignment.pdf

[donEnno]

Update zu den UMAPs: In der Tat kommt UMAP nicht so wirklich auf die Ähnlichkeiten als Distanzen klar.. trotzdem sehr interessant, dass es zumindest so scheint, als würde er in der DM als Feature-Matrix etwas finden.

[donEnno]

Das stimmt, ich meinte aber auch 1/(1+x) (siehe deinen Folgepost).

Wenn hier x < -1 ist, dann kommen wir ja aber mit negativen "Distanzen" raus, oder nicht?

Ergibt das Sinn?

Ja, danke für die Erklärung 😄

[...] was Networkit für die Erstellung eines Graphen und das finden der Cluster erwartet.

Aus der Doku zu Louvain (und auch Leiden): Hier steht nichts über Distanzen/Affinitätsmatrizen ...

Parameters G (networkit.Graph) – A graph.

Aus der Doku zu Graph:

Bases: object An undirected graph (with optional weights) and parallel iterator methods. Graph(n=0, weighted=False, directed=False)

Create a graph of n nodes. The graph has assignable edge weights if weighted is set to True. If weighted is set to False each edge has edge weight 1.0 and any other weight assignment will be ignored.

[...] Levenshtein [...]

Ist mir bekannt. Es gibt sogar ein python package, dass das kann und über C läuft. Was hier natürlich schön wäre, ist die Tatsache, dass dadurch der Parameter der gewählten Substitutions Matrix und der gap penalties komplett entfällt.

Nur noch ein Gedanke am Rande: Wenn wir über eine Neuberechnung der DMs sprechen bzw. reichen eigentlich auch nur die heute aufgetretenen Probleme, sehe ich das Schreiben eines Abstracts bis zum 4. März sehr kritisch und würde das Kilian im Zweifel frühzeitig sagen, damit er weiß wie der Hase läuft. Vielleicht sehe ich das ganze aber auch zu eng.

[mbruhns]

[...] trotzdem sehr interessant, dass es zumindest so scheint, als würde er in der DM als Feature-Matrix etwas finden.

Mit genügend Annahmen findet man immer etwas 😄 Sieht aber schonmal deutlich interessanter aus. Was war da jetzt der Input bei "precomputed", die Ähnlichkeiten oder eine Form der Distanzen?

Wenn hier x < -1 ist, dann kommen wir ja aber mit negativen "Distanzen" raus, oder nicht?

Stimmt, das mit den negative Ähnlichkeiten ist wirklich sehr nervig 🤦🏼‍♂️ Muss nochmal lesen, wie sowas zu interpretieren ist, oder ob man das eher als Artefakt auffassen muss.

Wenn wir über eine Neuberechnung der DMs sprechen bzw. reichen eigentlich auch nur die heute aufgetretenen Probleme, sehe ich das Schreiben eines Abstracts bis zum 4. März sehr kritisch und würde das Kilian im Zweifel frühzeitig sagen, damit er weiß wie der Hase läuft.

Könnte in der Tat ein Problem werden. Können wir eventuell morgen nochmal besprechen. Die Konferenz wäre ja eh nur ein netter Bonus gewesen, am Ende soll das ja eh primär in einem Journal landen.

Mach dir auf jeden Fall keinen Stress, sollte das mit der DM wirklich falsch gewesen sein. Fehler passieren, auch (bzw. gerade) in der Wissenschaft. Jetzt weißt du, dass man auf sowas achten muss und gut ist ✌🏻

[donEnno]

Was war da jetzt der Input bei "precomputed", die Ähnlichkeiten oder eine Form der Distanzen?

Das war jetzt ´fit_transform´ auf die DM angewendet, nur dass ich ´metric=precomputed´ angegeben habe.

wirklich sehr nervig

Ja, du sagst es. Deshalb war ich schnell bei MinMax. Ich habe aber auch noch gelesen, dass es beispielsweise in R ein package gibt, dass aus similarities dissimilarites machen kann, was Distanzen ja schon deutlich näher kommt.

Die Konferenz wäre ja eh nur ein netter Bonus gewesen, am Ende soll das ja eh primär in einem Journal landen.

Gut, so sehe ich das nämlich auch.

Wie in der Pandemie so oft so schön gesagt wurde: "Wissenschaft ist der neuste Stand des Irrtums." Und damit eine gute Nacht und bis morgen ✌🏼

[donEnno]

Noch ein kleiner Nachtrag zu den NetworKit Methoden, aus deren Paper:

As the central data structure, the Graph class implements a directed or undirected, optionally weighted graph using an adjacency array data structure with O(n+m) memory requirement for a graph with n nodes and m edges.

[mbruhns]

Ich habe gerade auch nochmal geschaut, im Louvain Paper liest es sich auch so, als würden Ähnlichkeiten genutzt. Sieht also so aus, als wäre das alles in Ordnung 😄

[mbruhns]

Das hier zeigt auch in die Richtung

[donEnno]

Das ist ja schonmal gut, insofern dass das Problem dann "nur" UMAP betrifft. Da finde ich aber interessant, dass Louvain oft die Cluster, die durch UMAP suggeriert werden, findet.

[donEnno]

Ich habe jetzt die die Affinitymatrix (AM) zu einer Distanzmatrix umgewandelt mit dem ´1/(1+x)´ Ansatz, mit dem vorherigen zero-shiften der Ähnlichkeiten. Unten ist die entsprechende UMAP.

Hier noch eine Formfrage: Die AM habe ich so berechnet, dass auf der Diagonalen nur Nullen stehen. Tatsächlich müsste hier ja aber das Maximum für jede Sequenz stehen. Durch ´np.fill_diagnoal(sm, 0)´ habe ich das behoben. Jetzt gibt es aber identische Sequenzen, d.h. hier sollte in der DM (die transformierte SM, to be clear) dann jeweils auch eine 0 stehen. Das ist jetzt aber nur auf der Diagonalen der Fall, also dem tatsächlichen Selbstvergleich. Für Sequenzen die identisch sind, steht hier dann "nur" ein Wert, der 0 sehr nahe kommt.

Das könnte man beheben in dem man die Diagonale neu berechnet via NWA und dann eben wie oben beschrieben transformiert. Was hältst du davon?

[mbruhns]

UMAP

Wieso sieht die UMAP jetzt wieder so beschissen aus 😭😄 Habe sicherheitshalber nochmal gecheckt, welche Einträge eine kNN-Matrix enthalten soll, sklearn als Referenz gibt uns Recht:

---

Transformation

Wir haben das gerade nochmal im Lab diskutiert, negative Werte sollten einfach zu null konvertiert werden. Durch den Shift würde man ja über Eck implizieren, dass Sequenzen mit Ähnlichkeit 0 doch eigentlich Ähnlich sind.

---

Identische Sequenzen

Wie viele Sequenzen kommen nochmal mehrfach vor? Für die UMAP ist es vermutlich sinnvoll die zu entfernen.

[donEnno]

Ich verstehe nicht ganz, warum du findest, dass das schlecht aussieht? Ist doch schön, wenn es blob-like Strukturen gibt und wenn die sich dann obendrein mit den Clustern decken, umso besser? Oder nicht?

@Transformation: Aber Ähnlichkeit = 0 bedeutet nicht "ähnlich" oder "nicht ähnlich", sondern ist ja ein quantitaives Maß für die Ähnlichkeit. Durch das Konvertieren von negativen scores, verwässert man doch im Endeffekt die Distanz 1.

@Identische Sequenzen_ Müsste ich nochmal genau nachschauen, aber es waren >5k. Klar, kann ich rausnehmen.

[mbruhns]

Ging mir primär um die ganzen Sequenzen, die sich nicht in die großen Blobs einfügen, aber man kann ja nicht immer alles haben 😅

Transformation: Sehr guter Punkt! Werde mir dazu nochmal Gedanken machen, bzw. Manfred befragen wie er das sieht. Würde vorschlagen, dass wir beim bisherigen Ansatz bleiben.

[donEnno]

Achsoo. Es wäre so nice, wenn man im Plot einfach die Punkte gaten kann, so wie beim FACS oÄ. In den 3d Darstellungen sieht man aber sehr gut, dass diese "Punkte" am Rand oft 10-20 Sequenzen sind, die dort Minicluster bilden.

Alright, dann bin gespannt auf das Feedback.

[donEnno]

Fazit

Louvain/Leiden erwarten die Affinity-Matrix.

Durch die 1/(x+1)-Transformation haben wir die Affinitäten zu Distanzen gemacht und mit umap.UMAP(metric='precomputed').fit_transform(data) können diese Distanzen direkt durch UMAP verarbeitet werden.

Zwar funktioniert UMAP auch auf der Affinity-Matrix, das ist so aber nicht ganz gedacht.

[donEnno]

PS: Ich habe den Code für die UMAP angepasst.