Clasificare: BM25+
Scris de Denis Nuțiu
- 2 minute de citit
- 4 exemple de cod în Kotlin
- 2 imagini
Disponibil și în English
Pe această pagină
Introducere
BM25+ este un algoritm de clasificare folosit pentru a ordona documente text în funcție de un scor de relevanță.
Este folosit în motoarele de căutare pentru a determina care documente sunt cele mai relevante pentru o interogare formată din termeni.
Algoritmul implementat se bazează pe lucrarea Improvements to BM25 and Language Models Examined.
Implementare
Un index poate fi folosit pentru a indexa termenii și documentele în care apar termenii:
[term: apples] - doc1, doc2, doc3 [term: grapes] - doc2, doc4 Când un utilizator caută termenul apples, sunt returnate doc1, doc2 și doc3.
Pentru a calcula scorul de relevanță al lui doc1, doc2 și doc3, se folosește algoritmul BM25+.
BM25+ este o formulă matematică simplă, calculată după cum urmează:
Lovins, J.B., Error evaluation for stemming algorithms as clustering algorithms. JASIS, (1971), 22(1):28-40
Putem ignora suma deocamdată. Dacă un utilizator caută cu mai mulți termeni, RSV (Retrieval Status Value) este suma scorurilor fiecărui termen luat individual.
Parametrii k1, b și delta sunt parametri de ajustare. Formula finală arată astfel:
Prima parte este Inverse Term Frequency, pe care algoritmul BM25+ o modifică adunând 1 la N.
Această frecvență măsoară cât de relevant este un termen pentru document, N este numărul de documente, iar
dft este numărul de documente care conțin termenul.
În a doua parte:
tftdeste numărul de apariții ale termenului în document.Ld- este lungimea documentului.Ldavg- este lungimea medie a documentelor.
Rezultatul formulei este RSV: cu cât este mai mare, cu atât documentul este mai relevant.
Indexare
Operația de indexare stochează documentul în spațiul de stocare definit.
/** * Stocarea păstrează o corespondență: id document -> document. */private var storage: MutableMap<Int, TokenizedDocument> = HashMap()/** * Indexul de frecvență al termenilor păstrează o corespondență: termen -> lista documentelor în care apare termenul. */private var termFrequencyIndex: MutableMap<String, HashSet<Int>> = HashMap()Iar documentul index este implementat după cum urmează:
/** * Indexează un document. */fun index(document: Document) { // Tokenizăm documentul. Din motive didactice și pentru simplitate, considerăm tokeni doar // cuvintele delimitate de spații și le transformăm în litere mici. val tokenizedDocument = TokenizedDocument(document, document.text) // Documentul nu există în index if (!storage.containsKey(document.id)) { storage[document.id] = tokenizedDocument totalTokens += tokenizedDocument.getTokens().size meanDocumentLengths = (totalTokens / storage.size).toDouble() // Indexăm toți tokenii tokenizedDocument.getTokens().forEach { if (termFrequencyIndex.containsKey(it)) { termFrequencyIndex[it]?.add(document.id) } else { termFrequencyIndex[it] = HashSet() termFrequencyIndex[it]?.add(document.id) } } }}Interogarea după termeni are următoarea implementare:
fun termsQuery(vararg terms: String): List<Pair<Double, Document>> { val documentIds = terms.map { term -> Pair(term, termFrequencyIndex[term.lowercase()] ?: mutableSetOf()) }.reduce { acc, pair -> // adăugăm în mulțimea de documente toate documentele care conțin acești termeni. acc.second.addAll(pair.second) // returnăm acc }.second // Calculăm suma RSV a termenilor pentru fiecare document. return documentIds.map { val document = storage[it] ?: return@map null val documentRsv: Double = terms.sumOf { term -> computeRsv(term.lowercase(), document) } return@map documentRsv to document.document // Sortăm rezultatele după cel mai mare scor și eliminăm scorurile Infinity, care înseamnă că termenul nu există. }.filterNotNull().filter { isFinite(it.first) }.sortedByDescending { it.first }}Poți consulta codul sursă complet și suita de teste: Source Code | Unit-Tests.
