JavaScript 전체 텍스트 검색 관련성 점수 샘플 코드에 대한 자세한 소개
- 黄舟원래의
- 2017-03-13 16:50:18944검색
전체 텍스트 검색은 기계 학습 분야의 다른 대부분의 문제와 달리 웹 프로그래머가 일상 업무에서 자주 직면하는 문제입니다. 고객이 어딘가에 검색 상자를 제공하도록 요청할 수 있으며 WHERE title LIKE %:query%와 같은 SQL 문을 작성하여 검색 기능을 구현합니다. 처음에는 별 문제가 없었는데, 어느 날 고객님께서 "검색에 오류가 있었습니다!"라고 하셨습니다.
당연히 검색에 "오류"가 없었습니다. 단지 검색 결과가 고객이 원하는 것이 아니었을 뿐입니다. 일반 사용자는 정확한 일치를 수행하는 방법을 모르기 때문에 얻는 검색 결과의 품질이 좋지 않습니다. 문제를 해결하기 위해 전체 텍스트 검색을 사용하기로 결정했습니다. 지루한 학습 기간을 보낸 후 MySQL의 FULLTEXT index를 활성화하고 "MATCH() ... AGAINST("와 같은 고급 query 구문을 사용했습니다. ) ".
자, 문제가 해결되고 꽃이 완성되었습니다! 데이터베이스 크기가 작은 경우에는 문제가 되지 않습니다.
그러나 데이터가 점점 더 많아지면 데이터베이스가 점점 느려지는 것을 알게 될 것입니다. MySQL은 사용하기 매우 쉬운 전체 텍스트 검색도구가 아닙니다. 그래서 ElasticSearch를 사용하고, 코드를 리팩터링하고, Lucene 기반의 전체 텍스트 검색 클러스터를 배포하기로 결정했습니다. 당신은 그것이 매우 잘 작동하고 빠르고 정확하게 작동한다는 것을 알게 될 것입니다.
이 시점에서 궁금하지 않을 수 없습니다. Lucene이 왜 그렇게 멋진가요? 이 글(주로 TF-IDF, Okapi BM-25 및 일반 관련성 점수 소개)과 다음 글(주로 인덱싱 소개)에서는 전체 텍스트 검색에 대해 설명합니다. 🎜>기본 컨셉 그 뒤에. 관련성
각 검색어에 대해 각 문서에 대한 "관련성 점수"를 쉽게 정의할 수 있습니다. 사용자가 검색할 때 문서 출현 시간 대신 관련성 점수를 사용하여 정렬할 수 있습니다. 이렇게 하면 생성된 지 얼마나 되었는지에 관계없이 가장 관련성이 높은 문서가 첫 번째 순위가 됩니다(물론 문서 생성 시간과도 관련이 있는 경우도 있습니다).
텍스트 간의 상관관계를 계산하는 방법은 매우 많지만 가장 간단한 통계 기반 방법부터 시작하겠습니다. 이 방법은 언어 자체에 대한 이해가 필요하지 않고, 문서 내 고유 단어의 출현율을 기준으로 단어 사용, 일치, 가중치를 계산하여 "관련성 점수"를 결정합니다.
이 알고리즘은 단어가 명사인지 동사인지 상관하지 않으며 단어의 의미에도 신경 쓰지 않습니다. 그것이 관심을 갖는 유일한 것은 어떤 단어가 흔한지, 어떤 단어가 희귀한지입니다. 검색어에 일반적인 단어와 희귀한 단어가 모두 포함된 경우 일반적인 단어의 가중치를 낮추면서 희귀한 단어가 포함된 문서에 더 높은 점수를 부여하는 것이 좋습니다.
이 알고리즘의 이름은 Okapi BM25입니다. 여기에는 두 가지 기본 개념이 포함되어 있습니다. 단어 빈도(
용어 빈도), 약어로 용어 빈도(“TF”)및 역 문서 빈도(역 문서 빈도), 약어로 다음과 같습니다. (“IDF”) 이들을 하나로 묶은 것을 "TF-IDF"라고 하는데, 이는 문서에서 용어가 얼마나 중요한지 나타내는 데 사용되는 통계적 척도입니다. TF-IDF
용어 빈도(
용어 빈도)는“TF”라고도 하며 매우 간단한 측정 기준입니다. 특정 단어가 검색어에 나타나는 횟수입니다. 문서 . 이 값을 문서의 총 단어 수로 나누어 점수를 얻을 수 있습니다. 예를 들어, 문서에 100개의 단어가 있고 'the'라는 단어가 8번 나타나면 'the'의 TF는 8, 8/100 또는 8%(표현하려는 방식에 따라 다름)입니다. 역 문서 빈도
(역 문서 빈도)는 "IDF"라고 하며 조금 더 복잡합니다. 단어가 희귀할수록 이 값이 높아집니다. 전체 문서 수를 해당 용어가 포함된 문서 수로 나눈 다음 몫에 로그를 취하여 구합니다. 단어가 희귀할수록 생성되는 "IDF"가 높아집니다. 이 두 숫자를 곱하면(TF*IDF) 문서에서 단어의 무게를 얻게 됩니다. "무게"는 다음과 같이 정의됩니다. 해당 단어가 얼마나 드물고 문서에 얼마나 자주 나타나는가?
문서에 대한 검색어에 이 개념을 사용할 수 있습니다. 쿼리의 각 키워드에 대해 TF-IDF 점수를 계산하고 이를 합산합니다. 점수가 가장 높은 문서가 쿼리문과 가장 잘 일치하는 문서입니다.
멋지네요!
Okapi BM25
위 알고리즘은 사용 가능한 알고리즘이지만 완벽하지는 않습니다. 이는 통계 기반의 상관 점수 알고리즘을 제공하며 이를 더욱 개선할 수 있습니다.
Okapi BM25는 지금까지 가장 발전된 순위 알고리즘 중 하나로 간주됩니다(그래서 ElasticSearch라고 합니다). Okapi BM25는 TF-IDF를 기반으로 각각 "용어 주파수 포화도"와 "필드 길이 사양"을 나타내는 두 개의 조정 가능한 매개변수 k1과 b를 추가합니다. 이게 대체 뭐야?
'단어 빈도 포화도'를 직관적으로 이해하려면 야구를 다룬 비슷한 길이의 두 기사를 상상해 보세요. 또한 이 두 문서를 제외한 모든 문서에 야구 관련 콘텐츠가 많지 않다고 가정하면 '야구'라는 단어의 IDF는 매우 드물고 중요합니다. 두 기사 모두 야구에 대해 다루고 있으며 둘 다 상당한 공간을 할애하고 있지만 한 기사는 다른 기사보다 "야구"라는 단어를 더 많이 사용합니다. 그렇다면 이 경우 실제로 한 기사가 다른 기사와 점수가 많이 다른가요? 두 문서 모두 야구를 전반적으로 다루고 있기 때문에 '야구'라는 단어가 40번 나오든, 80번 나오든 상관없습니다. 사실, 30번이 상한선이어야 합니다!
이것이 "단어 빈도 포화"입니다. 기본 TF-IDF 알고리즘에는 포화 개념이 없으므로 "야구"가 80번 나타나는 문서는 40번 나타나는 문서보다 2배 높은 점수를 갖습니다. 때로는 이때 우리가 원하지만 때로는 원하지 않는 경우도 있습니다. 또한 Okapi BM25에는 채도 변화율을 조정하는 데 사용되는 k1 매개변수 값이 일반적으로 1.2 사이입니다. 2.0. 값이 낮을수록 포화 프로세스가 더 빨라집니다. (위의 두 문서 모두 "야구"라는 단어가 많이 포함되어 있기 때문에 동일한 점수를 가짐을 의미합니다.)
필드 길이 감소( 필드 -length 정규화는 문서의 길이를 모든 문서의 평균 길이로 줄입니다. 이는 단일 필드 컬렉션(예: 우리의 컬렉션)에서 서로 다른 길이의 문서를 동일한 비교 기준으로 통합하는 데 유용합니다. 컬렉션(예: "제목" 및 "본문")에도 제목과 본문 필드를 동일한 비교 조건으로 통합할 수 있습니다. 필드 길이 감소는 b로 표시되며 해당 값은 0입니다. 공식은 확실히 이해하기 쉽기 때문에 공식을 언급하지 않고 바로 코드로 이동하겠습니다.
BM25.Tokenize = function(text) {
text = text
.toLowerCase()
.replace(/\W/g, ' ')
.replace(/\s+/g, ' ')
.trim()
.split(' ')
.map(function(a) { return stemmer(a); });
// Filter out stopStems
var out = [];
for (var i = 0, len = text.length; i < len; i++) {
if (stopStems.indexOf(text[i]) === -1) {
out.push(text[i]);
}
}
return out;
};간단한
정적 메소드를 정의합니다. )은문자열
을 토큰의배열
으로 구문 분석하는 것입니다. 이러한 방식으로 엔트로피를 줄이고 매칭을 향상시키기 위해 모든 토큰을 소문자로 만듭니다. 정도("걷기"와 "걷기" 일치는 동일함) 그리고 엔트로피 값을 더 줄이기 위해 중지 단어(매우 일반적인 단어)도 필터링합니다. 개념에 너무 깊이 들어가기 전에 양해해 주시기 바랍니다.BM25.prototype.addDocument = function(doc) {
if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); };
if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); };
// Raw tokenized list of words
var tokens = BM25.Tokenize(doc.body);
// Will hold unique terms and their counts and frequencies
var _terms = {};
// docObj will eventually be added to the documents database
var docObj = {id: doc.id, tokens: tokens, body: doc.body};
// Count number of terms
docObj.termCount = tokens.length;
// Increment totalDocuments
this.totalDocuments++;
// Readjust averageDocumentLength
this.totalDocumentTermLength += docObj.termCount;
this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;
// Calculate term frequency
// First get terms count
for (var i = 0, len = tokens.length; i < len; i++) {
var term = tokens[i];
if (!_terms[term]) {
_terms[term] = {
count: 0,
freq: 0
};
};
_terms[term].count++;
}
// Then re-loop to calculate term frequency.
// We'll also update inverse document frequencies here.
var keys = Object.keys(_terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
// Term Frequency for this document.
_terms[term].freq = _terms[term].count / docObj.termCount;
// Inverse Document Frequency initialization
if (!this.terms[term]) {
this.terms[term] = {
n: 0, // Number of docs this term appears in, uniquely
idf: 0
};
}
this.terms[term].n++;
};
// Calculate inverse document frequencies
// This is SLOWish so if you want to index a big batch of documents,
// comment this out and run it once at the end of your addDocuments run
// If you're only indexing a document or two at a time you can leave this in.
// this.updateIdf();
// Add docObj to docs db
docObj.terms = _terms;
this.documents[docObj.id] = docObj;
};여기서 addDocument() 메소드가 사용되며 기본적으로 this.documents와 this.terms라는 두 가지 유사한 메소드를 생성하고 유지합니다. documentis는 모든 문서의 원본 텍스트와 문서의 길이 정보를 저장하고, 목록에 저장된 모든 단어와 단어의 수를 저장하는 데이터베이스입니다. 이 데이터 구조를 사용하면 쉽고 빠르게 할 수 있습니다. (예, 매우 빠르며 O(1) 시간 복잡도의 해시 테이블 쿼리 시간만 필요합니다.) 다음 질문에 답하십시오. 문서 #3에 'walk'라는 단어가 몇 번이나 나타납니까? 또 다른 데이터 구조인 this.terms도 사용합니다. 말뭉치의 모든 단어를 나타냅니다. 이 데이터 구조를 통해 O(1) 시간 내에 다음 질문에 답할 수 있습니다. 'walk'라는 단어가 몇 개의 문서에 나타납니까? 그 사람의 아이디는 무엇인가요? 마지막으로 각 문서의 길이를 기록하고, 전체 말뭉치에 걸쳐 문서의 평균 길이를 기록합니다. 위 코드에서 idf는 0으로 초기화되고 updateidf() 메서드는 주석 처리
되어 있습니다. 이는 이 방법이 매우 느리게 실행되고 인덱싱 후 한 번만 실행하면 되기 때문입니다. 한 번 실행하면 요구 사항을 충족할 수 있으므로 5,000번 실행할 필요가 없습니다. 먼저 주석 처리하고 대규모 인덱싱 작업 후에 실행하면 많은 시간을 절약할 수 있습니다. 이함수
에 대한 코드는 다음과 같습니다.BM25.prototype.updateIdf = function() {
var keys = Object.keys(this.terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
var num = (this.totalDocuments - this.terms[term].n + 0.5);
var denom = (this.terms[term].n + 0.5);
this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
}
};
这是一个非常简单的函数，但是由于它需要遍历整个语料库中的所有词语，并更新所有词语的值，这就导致它工作的就有点慢。这个方法的实现采用了逆向文档频率 (inverse document frequency) 的标准公式（你可以在 Wikipedia 上找到这个公式）— 由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。我做了一些修改，让返回值一直大于0。
BM25.prototype.search = function(query) {
var queryTerms = BM25.Tokenize(query);
var results = [];
// Look at each document in turn. There are better ways to do this with inverted indices.
var keys = Object.keys(this.documents);
for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
var id = keys[j];
// The relevance score for a document is the sum of a tf-idf-like
// calculation for each query term.
this.documents[id]._score = 0;
// Calculate the score for each query term
for (var i = 0, len = queryTerms.length; i < len; i++) {
var queryTerm = queryTerms[i];
// We've never seen this term before so IDF will be 0.
// Means we can skip the whole term, it adds nothing to the score
// and isn't in any document.
if (typeof this.terms[queryTerm] === 'undefined') {
continue;
}
// This term isn't in the document, so the TF portion is 0 and this
// term contributes nothing to the search score.
if (typeof this.documents[id].terms[queryTerm] === 'undefined') {
continue;
}
// The term is in the document, let's go.
// The whole term is :
// IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
// IDF is pre-calculated for the whole docset.
var idf = this.terms[queryTerm].idf;
// Numerator of the TF portion.
var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
// Denomerator of the TF portion.
var denom = this.documents[id].terms[queryTerm].count
+ (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));
// Add this query term to the score
this.documents[id]._score += idf * num / denom;
}
if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
results.push(this.documents[id]);
}
}
results.sort(function(a, b) { return b._score - a._score; });
return results.slice(0, 10);
};最后，search() 方法遍历所有的文档，并给出每个文档的 BM25 分数，然后按照由大到小的顺序进行排序。当然了，在搜索过程中遍历语料库中的每个文档实是不明智。这个问题在 Part Two （反向索引和性能）中得到解决。
上面的代码已经做了很好的注释，其要点如下：为每个文档和每个词语计算 BM25 分数。词语的 idf 分数已经预先计算好了，使用的时候只需要查询即可。词语频率作为文档属性的一部分也已经预先计算好了。之后只需要简单的四则运算即可。最后给每个文档增加一个临时变量 _score，然后根据 score 做降序排列并返回前 10 个结果。
示例，源代码，注意事项和下一步计划
上面的示例有很多方法进行优化，我们将在 “全文搜索”的第二部分中介绍它们，欢迎继续收看。我希望我能在几个星期之后完成它。下面列了下次将要提到的内容：
反向索引和快速搜索
快速索引
更好的搜索结果
为了这个演示，我编了一个小的维基百科爬虫，爬到相当多（85000）维基百科文章的第一段。由于索引到所有85K文件需要90秒左右，在我的电脑我已经削减了一半。不想让你们仅仅为了一个简单的全文本演示浪费你的笔记本电脑电量。
因为索引是一个繁重的、模块化的CPU操作，我把它当成一个网络工作者。索引运行在一个后台线程上–在这里你可以找到完整的源代码。你也会发现到词干算法和我的停用词列表中的源代码参考。至于代码许可，还是一如既往为教育目的而免费，而不用于任何商业目的。
最后是演示。一旦索引完成，尝试寻找随机的东西和短语，维基百科会知道的。注意，只有40000段的索引，所以你可能要尝试一些新的话题。
위 내용은 JavaScript 전체 텍스트 검색 관련성 점수 샘플 코드에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!