Skor kesamaan matriks string

Saya memiliki banyak dokumen, yang memuat banyak pasangan nilai kunci di dalamnya. Kunci mungkin tidak unik sehingga mungkin ada beberapa kunci dari jenis yang sama dengan nilai yang berbeda.

Saya ingin membandingkan kesamaan kunci antara 2 dokumen. Lebih khusus kesamaan string dari nilai-nilai ini. Saya berpikir untuk menggunakan sesuatu seperti Algoritma Smith-Waterman untuk membandingkan kesamaan.

Jadi saya telah menggambar bagaimana saya berpikir tentang merepresentasikan data -

Nilai-nilai dalam sel adalah hasil dari algoritma smith-waterman (atau beberapa metrik kesamaan string).

Gambar yang matriks ini mewakili jenis kunci "hal-hal" Saya kemudian perlu menambahkan skor kesamaan "hal" ke dalam vektor 0 atau 1. Thats ok.

Apa yang saya tidak tahu adalah bagaimana saya menentukan apakah matriksnya sama atau tidak mirip - idealnya saya ingin mengkonversi matriks ke angka antara 0 dan 1 dan kemudian saya akan menetapkan ambang batas untuk mencetaknya sebagai 0 atau 1.

Adakah ide bagaimana saya bisa membuat skor matriks? Adakah yang tahu algoritma yang melakukan hal semacam ini (jelas hal-hal seperti bagaimana smith waterman bekerja adalah sesuatu yang berlaku).

Seperti yang saya pahami, Dokumen 1 dan Dokumen 2 mungkin memiliki jumlah kunci yang berbeda. Dan Anda harus mendapatkan evaluasi kesamaan akhir antara 0 dan 1. Jika demikian, saya akan mengusulkan algoritma berikut:

1. Jumlah maks. vals sama dengan 0.
2. Pilih nilai maksimum dari matriks doc-doc dan tambahkan ke Sum of max. vals.
3. Hapus baris dan kolom dengan nilai maksimum dari matriks.
4. Ulangi langkah 2-3 hingga baris atau kolom berakhir.
5. Jumlah Denominasi maks. vals dengan rata-rata jumlah kata kunci dalam dua teks.

Estimasi akhir akan sama dengan 1, jika kedua dokumen memiliki panjang yang sama, dan setiap kata dari Doc 1 memiliki padanan dalam Doc 2.

Anda belum menyebutkan perangkat lunak, Anda menggunakan, tapi di sini adalah contoh fungsi R , menghitung kesamaan tersebut (dibutuhkan objek dari matriks kelas sebagai input):

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
}

Dengan 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

Jika tujuan Anda adalah untuk mengubah matriks Anda menjadi angka (ukuran kesamaan Anda), Anda mungkin ingin menggunakan norma matriks .

Misalnya, menggunakan norma Frobenius pada contoh Anda akan mengembalikan 1,488086.

Saya pikir tujuan Anda adalah untuk menemukan betapa miripnya dua dokumen, jika itu masalahnya saya sarankan menerapkan algoritma berikut:

Pendekatan ini memberikan seberapa mirip Doc1 dengan WR2. (Nilai Kesamaan akan berbeda untuk Doc2 wrt Doc1 jika bukan matriks kuadrat)

1. Dalam matriks Anda antara Doc1 dan Doc2, Dapatkan nilai kemiripan max baris demi baris.
   2. Ambil jumlah dan bagi dengan jumlah baris
   3. Ini akan memberi Anda indeks kesamaan. Untuk misalnya. Dalam gambar matriks Anda, saya melihat kesamaan maksimum baris demi baris adalah: 0,88, 1, 0,6 Jadi (0,88 + 1 + 0,6) / 3 = 82,67%

Ini berarti Doc2 adalah 82,67% mirip dengan Doc1 . Kesamaan tidak dapat melampaui nilai ini karena kami memilih maks item serupa di setiap baris.