Score Matrix String Ähnlichkeit

Question

Ich habe eine Ladung von Dokumenten, die eine Ladung von Schlüsselwertpaaren enthalten. Der Schlüssel ist möglicherweise nicht eindeutig, sodass es möglicherweise mehrere Schlüssel des gleichen Typs mit unterschiedlichen Werten gibt.

Ich möchte die Ähnlichkeit der Schlüssel zwischen 2 Dokumenten vergleichen. Insbesondere die String -Ähnlichkeit dieser Werte. Ich denke daran, so etwas wie das zu verwenden Smith-Waterman-Algorithmus um die Ähnlichkeit zu vergleichen.

Also habe ich ein Bild davon gezeichnet, wie ich über die Darstellung der Daten nachdenke -

Die Werte in den Zellen sind das Ergebnis des Smith-Waterman-Algorithmus (oder einer anderen String-Ähnlichkeitsmetrik).

Bild, dass diese Matrix einen Schlüsseltyp "Dinge" darstellt. Ich muss dann die Ähnlichkeitsbewertung "Dinge" in einen Vektor von 0 oder 1 hinzufügen. Das ist in Ordnung.

Was ich nicht herausfinden kann, ist, wie ich feststelle, ob die Matrix ähnlich oder nicht ähnlich ist - idealerweise möchte ich die Matrix in eine Zahl zwischen 0 und 1 konvertieren, und dann setze ich nur einen Schwellenwert, um sie als entweder 0 oder als 0 oder als 0 zu bewerten oder 1.

Irgendwelche Ideen, wie ich eine Punktzahl der Matrix erstellen kann? Kennt jemand irgendwelche Algorithmen, die diese Art von Dingen tun (Offensichtlich ist, wie Smith Waterman arbeitet).

Answer 1

Wie ich verstanden habe, haben Dokument 1 und Dokument 2 möglicherweise eine unterschiedliche Anzahl von Schlüssel. Und Sie streifen, um die endgültige Ähnlichkeitsbewertung zwischen 0 und 1 zu erhalten. Wenn ja, würde ich nach dem Algorithmus vorschlagen:

1. Summe von max. Vals entspricht 0.
2. Wählen Sie den Maximalwert aus der Doc-Doc-Matrix aus und fügen Sie ihn zur Summe von max hinzu. Vals.
3. Entfernen Sie die Zeile und die Spalte mit maximalem Wert aus der Matrix.
4. Wiederholen Sie die Schritte 2-3, bis die Zeilen oder Spalten beendet sind.
5. Beengungssumme von max. VALS nach durchschnittlicher Anzahl von Schlüsselwörtern in zwei Texten.

Die endgültige Schätzung wäre gleich 1, wenn beide Dokumente eine identische Länge haben und jedes Wort aus DOC 1 in DOC 2 gleichwertig ist.

Sie haben keine Software erwähnt, die Sie verwenden, aber hier ist R Beispiel für die Funktion, Berechnung einer solchen Ähnlichkeit (das Objekt der Klassenmatrix als Eingabe):

eval.sim <- function(sim.matrix){
  similarity <- 0
  denominator <- sum(dim(sim.matrix)) / 2
  for(i in 1:(min(c(nrow(sim.matrix), ncol(sim.matrix))) - 1)){
    extract <- which(sim.matrix == max(sim.matrix), arr.ind=T)[1, ]
    similarity <- similarity + sim.matrix[extract[1], extract[2]]
    sim.matrix <- sim.matrix[-extract[1], -extract[2]]
  }
  similarity <- similarity + max(sm.copy)
  similarity <- similarity / denominator
}

In Python -

import numpy as np

def score_matrix(sim_matrix):
    similarity = 0
    denominator = sum(sim_matrix.shape) / 2
    for i in range(min(sim_matrix.shape)):
        x, y = np.where(sim_matrix == np.max(sim_matrix))[0][0], np.where(sim_matrix == np.max(sim_matrix))[1][0]
        similarity += sim_matrix[x, y]
        sim_matrix = np.delete(sim_matrix,(x),axis=0)
        sim_matrix = np.delete(sim_matrix,(y),axis=1)
    return similarity / denominator

Answer 2

Wenn Ihr Ziel darin besteht, Ihre Matrix in eine Zahl (Ihre Ähnlichkeitsmaßnahme) zu verwandeln, möchten Sie möglicherweise a verwenden Matrix -Norm.

Zum Beispiel die Verwendung der FROBENIUS NORM In Ihrem Beispiel würde 1.488086 zurückgeben.

Answer 3

Ich denke, Ihr Ziel ist es, herauszufinden, wie ähnlich zwei Dokumente sind. Wenn dies der Fall ist, schlage ich vor, nach dem Algorithmus zu bewerben:

Dieser Ansatz gibt an, wie viel ähnliches DOC1 WRT DOC2 ist. (Die Ähnlichkeitswerte sind für doc2 WRT DOC1 unterschiedlich, wenn es keine quadratische Matrix ist)

1. Holen Sie sich in Ihrer Matrix zwischen DOC1 und DOC2 die MAX -Ähnlichkeitswert Zeile nach Zeile.
   2. Nehmen Sie die Summe und teilen Sie die Anzahl der Reihen
   3. Dies gibt Ihnen den Ähnlichkeitsindex. Für zB. In Ihrem Matrixbild sehe ich die maximale Ähnlichkeitszeile für Reihen: 0,88, 1, 0,6 SO (0,88 + 1 + 0,6)/3 = 82,67%

Das heisst DOC2 ist 82,67% ähnlich wie DOC1. Die Ähnlichkeit kann diesen Wert nicht überschreiten, da wir in jeder Zeile maximale ähnliche Elemente ausgewählt haben.