Was ist eigentlich Ähnlichkeit ?

Sowohl bei der Dublettensuche als auch bei den Pulsierenden Neuronen-Netzwerken (Spiking Neural Networks, SNNs) spielt der Ähnlichkeitsbegriff eine große Rolle.

Ähnlichkeit ist mathematisch schwer auszudrücken.

Die heute bekannten Ansätze gehen in zwei Richtungen:

  1. Distanz (metrische Verfahren)
  2. Anzahl übereinstimmender Elemente im Verhältnis zur Gesamtmenge (stochastische Verfahren)

Distanzen

Gemeint ist hier vorwiegend die Entfernung in Form von Rechenschritten oder grundlegenden Operationen wie Einfügen, Löschen und Ersetzen von Elementen, um das Eine in das Andere zu überführen.

Das bekannteste dieser Verfahren ist die Levenshtein-Distanz, die genau wie eben erläutert funktioniert. Die Berechnung ist nicht ganz einfach, denn wir suchen dabei eine optimale Lösung innerhalb eines Suchbaumes.

Selbst wenn diese Verfahren "metrisch" genannt werden, sind sie eigentlich weit entfernt von dem Begriff der Metrik, selbst wenn dieser auf faszinierende Weise sehr weit interpretiert werden kann, ganz abhängig von der Metrik, die man dabei verwendet, wenn Sie verstehen, was ich meine 😉

Pearson ist dabei klar statistisch, Manhattan ist dagegen rein geometrisch, zwischen diesen liegen Welten mit kaum für mich erkennbaren Berührungspunkten.

Jaccard-Koeffizient

Ganz anders und denkbar einfach das Verfahren des Schweizer Botanikers Paul Jaccard:

Um den Jaccard-Koeffizient zweier Mengen zu berechnen, teilt man die Anzahl der gemeinsamen Elemente durch die Größe der Vereinigungsmenge.

Wikipedia

Man könnte es sogar deutlich weniger umständlich ausdrücken, liebe Mathematikfreunde 😉
Wenn man wollte, sogar ganz ohne dabei auch noch die Mengenlehre zu bemühen, aber sei's drum.

Permutationen

Wichtig in diesem Zusammenhang ist der Begriff der Permutation. Denn es geht darum, wie gut die oben genannten Verfahren sämtliche Permutationen berücksichtigen können, und dabei versagen sie alle auf die eine oder andere Weise.*

*) bitte korrigieren Sie mich, wenn Sie anderer Ansicht sind.

Ein gutes Ähnlichkeitsmass wäre in der Lage, sämtliche Permutationen gleichmässig zu berücksichtigen.

Detlef Kroll

Beispiel:

"Detlef Kroll"
"Kroll, Detlef"

Ein Mensch erkennt sofort, dass es sich um denselben Namen handelt und würde dies sogar als identisch bezeichnen, nur eben anders herum geschrieben.

Die Levenshtein-Distanz müsste nun "Kroll, ", also 7 Zeichen löschen, dann ein Leerzeichen und 5 Zeichen "Kroll" am Ende einfügen. Und kommt damit auf eine Ähnlichkeit von exakt 0.5 (13 Operationen bei n=13). Das ist alles in allem keine besonders smarte Lösung. Um besser zu sein müssten Blockoperationen zugelassen werden, aber das könnte die Suche nach der Lösung bereits NP-Hart machen, jedenfalls bei größeren Sequenzen wie einem ganzen Genom mit einigen Millionen Elementen (z.B. bei einer Maus).

Bedeutung für die Mathematik

Wie oben erwähnt soll sich dieser Artikel nicht allein auf die Dublettensuche beziehen.

Der Begriff der Ähnlichkeit hat eine grundlegende Bedeutung wenn es um Unterscheidung geht oder wenn wir etwas klassifizieren wollen. Beides wird überhaupt erst möglich, wenn wir die Ähnlichkeit zwischen zwei Entitäten zuverlässig und übereinkommend ausdrücken können!

  Lesen Sie dazu auch den Abschnitt "Was ist eigentlich Intelligenz ?" auf dieser Seite.

Was es allgemein mit der Kategorisierung und der Clusteranalyse auf sich hat, und welche Verfahren dazu auch noch geeignet wären, und wie dies im Zusammenhang mit anderen Problemen steht, dazu in einem späteren Artikel.

Selbstähnlichkeit

Selbstähnlichkeit ist eine Eigenschaft von fraktalen Mustern, wie sie in Kochkurven, im Apfelmännchen oder in der Natur bei Schneeflocken auftritt. Mandelbrot versuchte dem mit gebrochenen Dimensionen beizukommen, ein Ansatz der mir wenig gefällt, denn Dimensionen sind mir heilig, müssen meiner Ansicht nach ganzzahlig sein und rechtwinklig aufeinander stehen, sonst sind es keine. Und man sollte nicht zu viele von Ihnen für eine Erklärung bemühen, sagen wir: Nicht mehr als 5. Dann bin ich zufrieden.

Nein, die Fraktale ergeben sich allein aus dem Umstand, dass hier zwei Kräfte gegeneinander wirken und sich dabei gegenseitig durchdringen. Dazu braucht es soweit überhaupt keine Dimensionen. Der Begriff der Transzendenz (gegenseitige Durchschreitung) beschreibt dieses Phänomen für mich bereits vollständig. Ein gutes Beispiel aus der Physik ist das Gekoppelte Pendel, wo zwei Pendel* durch eine Spiralfeder miteinander verbunden sind.

*) Der Wikipedia Artikel hinterlässt den Anschein, dass gekoppelte Pendel gut berechenbar wären und beschreibt auch schön die verschiedenen Schwingungszustände, ignoriert dabei aber, dass die Übergänge zwischen diesen Zuständen nicht vorhersagbar sind, wenn die Pendel in mehreren Versuchen von verschiedenen Punkten losgelassen werden. Einen guten Einstieg zum Verständniss von solch chaotischem Verhalten liefert die leicht nachvollziehbare Bifurkation