'IDF'에 해당되는 글 10건

  1. 2016.02.26 [Similarity] BM25, TF/IDF 한 줄 정리.
  2. 2015.12.16 [Elasticsearch - The Definitive Guide] Theory Behind Relevance Scoring
  3. 2015.12.10 [Elasticsearch - The Definitive Guide] Relevance is Broken!
  4. 2015.12.03 [Elasticsearch - The Definitive Guide] Relevance is Broken!
  5. 2014.10.30 [ElasticSearch] _score 계산 시 IDF 연산은 어떻게 이루어 지나요?
  6. 2013.10.11 [Lucene] score 계산식 알아보기.
  7. 2013.07.12 [lucene score] 펌) score 계산식.
  8. 2013.05.15 [Algorithm] IDF(Inverse Document Frequency)
  9. 2013.05.15 [Algorithm] TF (Term Frequency)
  10. 2013.02.19 TFIDF

[Similarity] BM25, TF/IDF 한 줄 정리.

ITWeb/검색일반 2016.02.26 10:52

TF/IDF: common words can still influence the score! 

BM25: limits influence of term frequency


TF/IDF: short fields (title,...) are automatically scored higher

BM25: Scales field length with average


참 간단하죠.

그냥 둘의 가장 큰 차이점이라고 생각 하시면 될 것 같습니다.


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : bm25, IDF, Similarity, TF
Trackback 0 : Comment 0

[Elasticsearch - The Definitive Guide] Theory Behind Relevance Scoring

Elastic/TheDefinitiveGuide 2015.12.16 11:21

가장 기본이 되는  TF/IDF Scoring 에 대한 설명 입니다.

복습 차원에서 기록해 봅니다.


원문링크)


원문 Snippet)

Term frequencyedit

How often does the term appear in this document? The more often, the higher the weight. A field containing five mentions of the same term is more likely to be relevant than a field containing just one mention. The term frequency is calculated as follows:

tf(t in d) = √frequency 

The term frequency (tf) for term t in document d is the square root of
the number of times the term appears in the document.

Inverse document frequency

How often does the term appear in all documents in the collection? The more often, the lower the weight.Common terms like and or the contribute little to relevance, as they appear in most documents, while uncommon terms like elastic or hippopotamus help us zoom in on the most interesting documents. The inverse document frequency is calculated as follows:

idf(t) = 1 + log ( numDocs / (docFreq + 1)) 

The inverse document frequency (idf) of term t is the logarithm of the number
of documents in the index, divided by the number of documents that contain the term.

Field-length normedit

How long is the field? The shorter the field, the higher the weight. If a term appears in a short field, such as a title field, it is more likely that the content of that field is about the term than if the same term appears in a much bigger body field. The field length norm is calculated as follows:

norm(d) = 1 / √numTerms 

The field-length norm (norm) is the inverse square root of the number of terms in the field.

가볍게 정리 하면)

- tf는 문서 내 발생한 term 빈도수 : term 빈도수가 클 수록 weight 가 높습니다.

- idf는 전체 문서에서 발생한 term 빈도수 : term 빈도수가 작을 수록 weight 가 높습니다.

- norm은 field내 text의 길이 : 길이가 짧을 수록 weight 가 높습니다.


더불어 mapping 설정도 살짝 살펴 보면)

필요한 정보만 저장할 경우 저장소 낭비를 방지 할 수 도 있으며, score 계산시 조금이나마 성능적 효과도 볼 수 있습니다.

모든 옵션을 다 사용해야 할지 선택적으로 사용해도 문제 없을지 잘 판단 하시면 좋을 것 같습니다.


- index_options

Allows to set the indexing options, possible values are docs (only doc numbers are indexed), freqs (doc numbers and term frequencies), and positions (doc numbers, term frequencies and positions). Defaults to positions for analyzed fields, and to docs for not_analyzed fields. It is also possible to set it to offsets (doc numbers, term frequencies, positions and offsets).


- norms: {enabled: <value>}

Boolean value if norms should be enabled or not. Defaults to true for analyzed fields, and to false for not_analyzed fields. See the section about norms.


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[Elasticsearch - The Definitive Guide] Relevance is Broken!

Elastic/TheDefinitiveGuide 2015.12.10 12:22

예전에 어느 분이 elasticsearch에서 score 관련 문의를 주셨었는데요.

IDF 값에 대한 global value 를 사용하는지 였습니다.

Elasticsearch에서는 default 설정이 사용하지 않는다 입니다.


서비스와 문서 특징에 따라 다를수는 있지만 저 역시 반드시 global idf 값을 써야 하나 하는 생각이 듭니다.

일단 각설 하고, The Definitive Guide 에 올라온 내용 기록 합니다.


원문링크)

https://www.elastic.co/guide/en/elasticsearch/guide/current/relevance-is-broken.html


원문 Snippet)

However, for performance reasons, Elasticsearch doesn’t calculate the IDF across all documents in the index. Instead, each shard calculates a local IDF for the documents contained in that shard.

...중략...

Don’t use dfs_query_then_fetch in production. It really isn’t required. Just having enough data will ensure that your term frequencies are well distributed. There is no reason to add this extra DFS step to every query that you run.


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[Elasticsearch - The Definitive Guide] Relevance is Broken!

Elastic/TheDefinitiveGuide 2015.12.03 17:04

동의 하지 않으시는 분들도 있습니다.

하지만 저는 서비스 특성과 요건에 따라 각자 선택할 몫이라고 생각 합니다.


원문링크)


원문 Snippet)

Don’t use dfs_query_then_fetch in production. It really isn’t required. Just having enough data will ensure that your term frequencies are well distributed. There is no reason to add this extra DFS step to every query that you run.


위 글을 가볍게 정리해 보면 이렇습니다.

분산 환경에서 하나의 index를 여러개의 shard로 쪼갰을 때 idf 값에 따라 relevancy 가 달라 질 수 있다는 이야기 입니다.

즉, local idf 값을 사용할 것인지 global idf 값을 사용할 것인지 search_type 이라는 파라미터를 통해서 결정 할 수 있다는 것입니다.


원문 snippet 은 보시면 아시겠지만 dfs 를 쓰지 말라고 하고 있습니다.

이것 역시 trade off 가 있기 때문에 판단은 사용하시는 분이 판단 하시면 됩니다.

relevance 또는 rank 처리에 있어서 custom 하게 하실 경우 크게 중요하지 않을 수도 있구요.

relevance 와 rank 작업이 중요 할 경우 dfs 를 사용해야 할 필요도 있습니다.


이런 것들도 similarity 기법을 뭘 사용할 것인지에 따라 달라 질 수 있기때문에 반드시라기 보다 경우에 따라 잘 사용하시면 좋겠습니다.


저는 개인적으로 그냥 dfs 빼고 사용해도 크게 무리는 없지 않나 생각 합니다.

Elasticsearch에서도 default search_type 은 query_then_fetch 로 적용 되어 있습니다.


dfs를 사용했을 때와 사용하지 않았을 때 검색 질의에 대한 성능적 차이가 있습니다.

다만, 규모가 작은 경우 별 차이는 없습니다. ㅡ.ㅡ;;

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[ElasticSearch] _score 계산 시 IDF 연산은 어떻게 이루어 지나요?

Elastic/Elasticsearch 2014.10.30 11:53

어제 저희 회사 행사에서 "오픈소스 검색엔진 구축 사례"로 발표를 했었는데요.

저에게 질문 주셨던 것중에 나름 재밌는 질문을 주셨던 내용이 있어서 공유 드립니다.


(아마도 질문 주신 분은 elasticsearch 를 사용해 보지 않으셨거나 경험 하신지 얼마 안되신 것 같다는 느낌 이였구요. lucene 은 많이 사용해보신 분 같다는 느낌 이였습니다. ㅎㅎ 제 느낌이니 틀릴수도 있구요.)


질문은 이랬던것 같습니다. 

- elasticsearch 에서  색인 시에, IDF 값을 Global 하게 쓰기 어려울 텐데 어떻게 사용되는 지에 대한 질문이었습니다


정답은 아래 링크에 나와 있죠. ^^

(shard 별로 이루어 집니다.)

http://www.elasticsearch.org/guide/en/elasticsearch/guide/current/relevance-intro.html


우선 TF의 경우 뭐 그냥 term frequency 니까 이건 별 문제 없을 거구요.

(기본 per field similarity 입니다.)

IDF의 경우는 그럼 어떻게 할까요 인데요????

IDF는 쉽게말해 index 내 전체 문서에서의 term이 포함된 document frequency 가 되는 건데요.

루씬에서는 뭐 당연히 문제가 안되겠지만 es 에서는 shard 라는 개념이 있죠. 즉 하나의 index를 여러개의 shard 로 나눠서 서로 다른 노드에 가지고 있으니 IDF 를 어떻게 계산 할 수 있을지.... 


제가 보는 관점은 단순 합니다.

- shard 별 document 의 idf 값만 보면 document 의 relevance가 문제일수 있지만, document 의 score 의 경우 tf + idf + field length norm 등 다양한 요소와 함께 계산되기 떄문에 normalized 되었다고 봅니다. 즉 score 값을 신뢰 할 수 있다 입니다.


ㅎㅎ 간만에 검색 질문을 주셔서 재밌었습니다.

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[Lucene] score 계산식 알아보기.

Elastic/Elasticsearch 2013.10.11 11:25
필요해서 어제 공부 좀 했습니다.

제가 elasticsearch 로 프로젝트를 진행 하고 있습니다.

랭킹과 문서 스코어링 관련해서 문의가 있어서 정확하게 설명을 해줘야 튜닝에 도움이 될 것 같아 글 좀 남겨 봅니다.


검색해 보시면 많은 문서들이 나오는데요.

아래 문서 참고 하시면 좋을 것 같내요.


[참고링크]

http://www.lucenetutorial.com/advanced-topics/scoring.html

http://devyongsik.tistory.com/364 (여긴 울 회사 재화님도 알고 계신 DEV용식님 사이트인데요. 작성 된지 좀 되었지만 이해 하기에는 좋습니다.)

https://lucene.apache.org/core/3_6_2/scoring.html

http://lucene.apache.org/core/4_5_0/core/org/apache/lucene/search/package-summary.html#package_description

http://lucene.apache.org/core/4_5_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html  


[참고용 소스코드]

Similarity.java

DefaultSimilarity.java

TFIDFSimilarity.java


lucene 이나 elasticsearch 나 기본은 바로 위에 있는 넘들 가지고 similarity 계산을 하게 됩니다.

소스를 보시면 아시겠지만 아래 요소를 가지고 score 를 계산 합니다.


tf

idf

lengthNorm

queryNorm

coord


소스코드에서 식을 뽑아 보면 이렇습니다.


 TF

 (float)Math.sqrt(freq)

 IDF

 (float)(Math.log(numDocs/(double)(docFreq+1)) + 1.0)^2

 lengthNorm

 state.getBoost() * ((float) (1.0 / Math.sqrt(numTerms)))

 queryNorm

 (float)(1.0 / Math.sqrt(sumOfSquaredWeights))

 coord

 overlap / (float)maxOverlap


이런건 그냥 위에 나온거 보면 다 나오구요.

검색 질의 시 스코어 계산 유형을 살펴 보겠습니다.

(계산 할 때 위에 식에 넣어서 계산 하기 번거로우니 explain 떠서 나온 값들을 사용해서 계산 하도록 하세요.)


1. 검색어 하나 질의

쉽게는 explain 에서 나온 queryWeight * fieldWeight 를 곱하시면 score 가 나옵니다.

score = (queryWeight * fieldWeight)^2


TFIDFSimilarity.html 에 잘 나와 있죠.

score(q,d)   =   coord(q,d)  ·  queryNorm(q)  · ( tf(t in d)  ·  idf(t)2  ·  t.getBoost() ·  norm(t,d) )
t in q
Lucene Practical Scoring Function

이걸 엑셀 같은 데 식을 넣어서 계산 해 보면 값이 나오게 됩니다.

아래 2번에서 풀어 놓은 식을 참고하세요.


2. 검색어 여러개 질의

score = (queryNorm * SUM( tf * idf^2 * fieldBoost * fieldNorm) )^2


3. 필드 부스팅을 포함한 검색어 질의

쉽게는 아래 처럼 풀어서 이해 하시면 됩니다.

score = ((queryWeight * fieldWeight) + (queryWeight * fieldWeight))^2

-> 필드 부스팅 된 필드의 queryWeight 값은 기본 계산이 되어서 나오지만 같은 필드에 같은 term 으로 했을 경우 기본 queryWeight 에 곱하기 boostScore 만큼 해준다고 보면 됩니다.


여기서 필드 부스팅을 한개가 아닌 여러개를 했다면 (queryWeight * fieldWeight) 이넘을 여러번 계산 해서 더하시면 됩니다.


근데 여기서 궁금한거 하나.... 

- fieldNorm 과 sumOfSquaredWeights 는 어떻게 구하나요???

소스 코드를 보시면 됩니다.


[fieldNorm]

computeNorm(), encodeNormValue(), decodeNormValue(), NORM_TABLE 을 참고하세요.

풀면 결국 아래와 같이 됩니다.


fieldNorm = NORM_TABLE[(floatToByte315(1/SQRT(fieldTotalTermsNum)) & 0xFF)];


[sumOfSquaredWeights]

말 처럼 이건 각각의 term 에 대해서 더하셔야 합니다.

1번에서 처럼  sigma 가 붙어 있는 걸 잊으시면 안됩니다.

이해를 돕고자 풀면 아래와 같이 됩니다.

queryBoost^2 * SUM( (idf * fieldBoost)^2 )


가볍게 이해 하는 수준으로만 사용하시고 깊이 있게 이해를 하고 싶으신 분들은 소스 코드를 꼭 드려야 보세요. :)


신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 : Comment 0

[lucene score] 펌) score 계산식.

Elastic/Elasticsearch 2013.07.12 17:29

Original URL : http://www.lucenetutorial.com/advanced-topics/scoring.html


Lucene Scoring

The authoritative document for scoring is found on the Lucene site here. Read that first.

Lucene implements a variant of the TfIdf scoring model. That is documented here.

The factors involved in Lucene's scoring algorithm are as follows:

  1. tf = term frequency in document = measure of how often a term appears in the document
  2. idf = inverse document frequency = measure of how often the term appears across the index
  3. coord = number of terms in the query that were found in the document
  4. lengthNorm = measure of the importance of a term according to the total number of terms in the field
  5. queryNorm = normalization factor so that queries can be compared
  6. boost (index) = boost of the field at index-time
  7. boost (query) = boost of the field at query-time

The implementation, implication and rationales of factors 1,2, 3 and 4 in DefaultSimilarity.java, which is what you get if you don't explicitly specify a similarity, are: 

note: the implication of these factors should be read as, "Everything else being equal, ... [implication]"

1. tf 
Implementation: sqrt(freq) 
Implication: the more frequent a term occurs in a document, the greater its score
Rationale: documents which contains more of a term are generally more relevant

2. idf
Implementation: log(numDocs/(docFreq+1)) + 1
Implication: the greater the occurrence of a term in different documents, the lower its score 
Rationale: common terms are less important than uncommon ones

3. coord
Implementation: overlap / maxOverlap
Implication: of the terms in the query, a document that contains more terms will have a higher score
Rationale: self-explanatory

4. lengthNorm
Implementation: 1/sqrt(numTerms)
Implication: a term matched in fields with less terms have a higher score
Rationale: a term in a field with less terms is more important than one with more

queryNorm is not related to the relevance of the document, but rather tries to make scores between different queries comparable. It is implemented as1/sqrt(sumOfSquaredWeights)

So, in summary (quoting Mark Harwood from the mailing list),

* Documents containing *all* the search terms are good
* Matches on rare words are better than for common words
* Long documents are not as good as short ones
* Documents which mention the search terms many times are good

The mathematical definition of the scoring can be found athttp://lucene.apache.org/core/4_0_0/core/org/apache/lucene/search/similarities/Similarity.html

Hint: look at NutchSimilarity in Nutch to see an example of how web pages can be scored for relevance

Customizing scoring

Its easy to customize the scoring algorithm. Subclass DefaultSimilarity and override the method you want to customize.

For example, if you want to ignore how common a term appears across the index,

Similarity sim = new DefaultSimilarity() {
  public float idf(int i, int i1) {
    return 1;
  }
}

and if you think for the title field, more terms is better

Similarity sim = new DefaultSimilarity() {
  public float lengthNorm(String field, int numTerms) {
    if(field.equals("title")) return (float) (0.1 *Math.log(numTerms));
    else return super.lengthNorm(field, numTerms);
  }
}


신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : Coord, IDF, lucene, Score, td
Trackback 0 : Comment 0

[Algorithm] IDF(Inverse Document Frequency)

Elastic/Elasticsearch 2013.05.15 14:32

참고 URL : http://kaistwebst.blog.me/130166255835


위 문서에 쉽게 설명이 나와 있습니다.

정리 하면, 하나의 문서 묶음(|S|)에서 어떤 단어(Wj) 가 한번 이라도 발생한 문서 수(Å)의 역수를 구하는 것입니다.


idfj  =            |S|

        log2


Term Wj 에 대한 idf 는 위와 같습니다.

그래서 TF-IDF 공식은 아래와 같습니다.



log2(1+fij) * idfj



즉, idf 값이 작게 되면 문서의 중요도가 낮다고 볼 수 있습니다.

TF-IDF 값이 클 수록 검색어에 대한 찾는 문서에 가깝다고 이해 하면 되겠습니다.

신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : IDF
Trackback 0 : Comment 0

[Algorithm] TF (Term Frequency)

Elastic/Elasticsearch 2013.05.15 14:12

참고 URL : http://kaistwebst.blog.me/130165776517


위 문서에 있는 것 처럼 하나의 문서에서 출현한 하나의 단어 출현 빈도수 입니다.

수식으로 표현 하면

Di : 문서

Wj : 단어(Term)

fij : 출현 단어 빈도 수

log2(1+fij)



예) 

Di : "안녕하세요 검색 관련 색인 빈도 중 Term 빈도, Document 빈도"

Wj : "빈도"

fij : 2

log2(1+2)


DF 설명 : 색인어당 문서의 빈도 수 (색인어 A 가 들어 있는 문서 들 이라고 보면 됨)

신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : df, IDF, TF
Trackback 0 : Comment 0

TFIDF

ITWeb/개발일반 2013.02.19 18:48

Reference URLs :

http://en.wikipedia.org/wiki/Tf%E2%80%93idf

http://ko.wikipedia.org/wiki/TF-IDF

http://nlp.stanford.edu/IR-book/html/htmledition/index-1.html



TF-IDF(Term Frequency - Inverse Document Frequency)는 정보 검색과 텍스트 마이닝에서 이용하는 가중치로, 여러 문서로 이루어진 문서군이 있을 때 어떤 단어가 특정 문서 내에서 얼마나 중요한 것인지를 나타내는 통계적 수치이다. 문서의 핵심어를 추출하거나, 검색 엔진에서 검색 결과의 순위를 결정하거나, 문서들 사이의 비슷한 정도를 구하는 등의 용도로 사용할 수 있다.


TF(단어 빈도수, term frequency)는 특정한 단어가 문서 내에 얼마나 자주 등장하는지를 나타내는 값으로, 이 값이 높을수록 문서에서 중요하다고 생각할 수 있다. 하지만 단어 자체가 문서군 내에서 자주 사용되는 경우, 이것은 그 단어가 흔하게 등장한다는 것을 의미한다. 이것을 DF(문서 빈도수, document frequency)라고 하며, 이 값의 역수를 IDF(inverse document frequence)라고 한다. TF-IDF는 TF와 IDF를 곱한 값이다.


IDF 값은 문서군의 성격에 따라 결정된다. 예를 들어 '원자'라는 낱말은 일반적인 문서들 사이에서는 잘 나오지 않기 때문에 IDF 값이 높아지고 문서의 핵심어가 될 수 있지만, 원자에 대한 문서를 모아놓은 문서군의 경우 이 낱말은 상투어가 되어 각 문서들을 세분화하여 구분할 수 있는 다른 낱말들이 높은 가중치를 얻게 된다.


신고
크리에이티브 커먼즈 라이선스
Creative Commons License
tags : IDF, td
Trackback 0 : Comment 0

티스토리 툴바