-
ranking (순위부여)의 필요성
-
-
natural language query에 의한 결과를 평가하기 위하여, ranking이 필요하다.
-
일반사용자는 boolean query 보다 natural language query를 선호한다.
- boolean system 은 훈련이 없는 일반 사용자에 복잡한 boolean query를 요구한다.
-
natural language query는 데이타에 없는 용어나 잘못된 철자에도 임의의 결과를 얻을 수 있다.
- 검색어의 일부분만 일치하여도 일부의 문서는 검색할 수 있으므로
-
-
-
순위부여 모델의 특징
-
근접(인접)연산, 필드제한이 필요없다.
- 추가적인 위치정보(필드위치, 단어위치)를 저장할 필요가 없다.
-
불용어목록을 줄일 수 있다.
- 컴퓨터분야에 대한 문헌에서 "컴퓨터"를 불용어로 지정할 필요가 없다.
-
-
순위부여 기본 개념
-
-
term vector
- 전체 문서집합안에 n개의 색인어(term)가 존재할 때, (t1, t2, ..... tn)처럼 vector로 표현할 수 있다.
- 각 색인어가 문서 또는 질의에 존재 여부에 따라 이 vector에서 1,0 으로 표시할 수 있다.
- query vector : query에 대한 term vector
- document vector: document에 대한 term vector
-
ranking
- rankinig은 query vector * document vector 의 값을 내림차순으로 정렬하는 것.
-
단, query vector, document vector 에 아래 요소를 이용하여, 가중치를 부여할 수 있다.
- TF, IDF가 높을 수록 가중치가 높다.
-
TF= term frequency (문헌내 빈도수)
- TF의 예:
- 많이 출현한 용어일 수록 TF가 높다.
- TF는 그 문헌에서 가장많이 출현한 용어의 출현 빈도수가 작을수록 높다. (정규화를 위한 옵션)
- TF는 용어 KIi의 빈도수가 높을수록 높다.
- TF의 예:
-
IDF= inverted document frequency (역 문헌 빈도수)
- IDF의 예:
-
흔하지 않은 용어일 수록 IDF가 높다.
- IDF는 전체문헌의 수가 많을 수록 높다. (정규화를 위한 옵션)
- IDF는 용어의 출현 빈도수가 작을 수록 높다.
- IDF의 예:
-
user-specified term weight
- 사용자가 임의로 정한 가중치
-
ranking 의 예
-
-
순위부여 모델
-
순위부여에서 유사도에 평가의 필요성에 대해 주장한 Luhn, 1957
-
"두 개 이상의 정보표현(문헌과 질의)이 주어진 원소(색인어)와 분포(색인어의 분포)면에서 서로 일치한다면, 그것들은(문헌과 질의) 유사한 정보를 표현할 확률이 더욱 높다."
-
-
벡터와 가중치를 이용한 유사도계산 방법
-
- 모델에 따라 가중치 계산을 다르게 함.
-
-
순위부여 모델의 종류
-
각 문헌에 대한 질의에 순위 부여
- vector space model (벡터공간 모델)
- probabilistic model (확률 모델)
-
관련있는 문헌 집합 전체에 대한 질의에 순위부여
- 클러스터링 모델
- 퍼지 모델
-
직접 비교
- Spark Jones: 수작업으로 색인어 추출
- McGill: 제어색인(수작업), 비제어색인(자동)을 모두 이용
-
Harman: "잡음" 측정법이용하여 용어집중도 파악
- 잡음: 검색에 사용할 만한 용어가 아닌 중요하지 않은 단어
-
문헌구조에 따라 순위부여
- Bernstein: 용어가 있는 구조적 위치에 따라 가중치 부여
-
문헌내부구조에 따라 순위부여
- 잠재 의미색인(semantic indexing) 이용
- 성능은 우수하지만, 속도의 문제가 있음
-
-
-
순위부여 기법 선정 가이드
-
IDF, 잡음, 엔트로피를 이용하면 성능이 향상된다.
-
즉, 장서내의 용어 분포를 바탕으로 하는 용어 가중치를 이용하면, 성능이 향상된다.
-
-
TF를 이용하여도 항상 성능이 향상되는 것은 아니다.
-
TF 에 대한 정규화 필요성 (TF 이용시 위험성)
-
높은 문헌내 빈도수의 영향 완화
- 같은 문헌에서 20번 나타나는 용어가 1번 나타나는 용어보다 20배 중요한 것은 아니다.
-
문헌 길이에 대한 효과 고려
- 매우 짧은 문헌에게 불리한 환경
-
장서의 종류에 따른 특성 고려
- 문헌내 빈도수의 효과가 작은 장서도 있다.
-
-
-
TF와 IDF를 조합하여 여러가지 방법을 사용할 수 있다.
-
정규화의 2가지 방식
- 코사인(cosine) 정규화: 출현빈도를 정규화하는데 사용
- 최대(max) 정규화: 다중 주제에 대한 검색시 유용
-
-
문헌구조에 따라 추가적인 가중치를 부여하는 것은 유용하다.
- 제목, 요약문에 나오는 용어에 높은 가중치를 부여한다.
- 초기 검색 이후에 연관 가중치를 사용하는 것은 효과적이다.
-
-
순위부여 모델의 역파일
-
-
사전(렉시콘)에 가중치 정보를 저장하는 경우
- 용어가중치 계산을 탐색루틴에서 해야하므로 오버헤드 발생 (???)
- 가중치 관련정보 = 역문헌 빈도수
-
-
포스팅 파일에 가중치 정보를 저장하는 경우 (저장하는 정보에 따른 분류)
-
저장하지 않음
- 모든 처리를 탐색 루틴에서 한다.
-
-
원빈도수 저장
- 탐색은 느리다.
-
가장 유연한다.
- 색인을 바꾸지 않고 용어 가중치 알고리즘을 변경할 수 있다.
-
정규화된 빈도수 저장
- 갱신시 포스팅파일을 바꿀 필요가 없다.
- 원빈도수 저장보다 탐색이 빠르다.
-
완전한 용어가중치 저장
-
갱신할 때마다 포스팅파일을 바꿔야 한다.
- 역문헌빈도수가 레코드가 추가될 때마다 바뀌기 때문이다.
- 탐색시간이 가장 빠르다.
-
연관피드백에서 이용하기 어렵다.
- 탐색시 각 가중치를 더하기만 한다.
-
-
-
-
순위부여 모델의 탐색 방법
- 불리언 시스템의 역파일 탐색 과정과 비슷하나, 포스팅에서 가중치 획득하는 부분이 추가된다.
-
문헌 식별번호를 키로 하여 레코드 가중치를 값으로 하는 해싱테이블 이용
- 해싱테이블은 저장장치의 한 블록을 사용
-
스템과 비스템 질의용어 조작
-
스템,비스템을 하나의 사전에 정렬하여 저장한다.
- 저장장치를 절약하므로, 대용량 데이타 집합에 유리
-
스템,비스템을 2개의 사전에 정렬하여 저장한다.
- 소용량 데이타 집합에 유리
-
-
가지치기(전지,pruning)
- 검색 성능에 큰 영향을 미치지 않는 선에서, 적합성(가중치)이 낮은 문서를 순위부여과정에서 제외시키는 것
-
가지치기 방법
- 불용어를 제거
-
역문헌빈도수가 낮은 용어와 관련된 문서 제거
- 가중치를 합산하는 과정에서, 역문헌빈도수가 작고 가중치가 0인 누산기에는 가중치를 추가하지 않는다.
-
순위부여 관련 주제
-
연관(적합성) 피드백
- 연관피드백을 이용하여 검색성능 향상 가능
-
클러스터링
- 같은 문헌을 클러스터링하여, 순위 부여하는 회수를 줄임
-
불리언 모델(시스템)
- 불리언 모델과 순위부여 모델의 통합 시도
-
요약파일
- 역파일 대신 요약파일을 사용하여 처리속도 향상
-
제약에 대한 처리
- 특정 문구 포함, 불리언 연산자, 인접 연산자
- 2단계로 처리됨 (제약을 처리하는 단계가 추가됨)
-
'검색 엔진' 카테고리의 다른 글
| [박혜웅] 벡터 공간 모델(vector space model) (0) | 2010.03.27 |
|---|---|
| [박혜웅] 확률 모델(probabilistic model) (0) | 2010.03.27 |
| [박혜웅] 확장 불리언 모델(extended boolean model) (0) | 2010.03.27 |
| [박혜웅] 적합성 피드백(relevance feedback) (0) | 2010.03.27 |
| [박혜웅] 불리언 모델 (boolean model) (0) | 2010.03.27 |
