정보 검색 개요


 

정보 검색 개요

정보 검색 시스템

정의

사용자가 필요로 하는 정보를 수집-저장

효율적인 검색을 위한 색인

검색 요구에 적합한 정보 검색 및 제공

인터넷 상의 문서의 수가 폭발적인 증가로 인해 검색 대상의 수가 방대해짐.

사용자 질의에 대한 빠른 응답 시간 요구

구성도

색인

정의

개개의 정보 자료(문서)의 특성을 표현하는 데이터 요소(색인어)를 뽑아

각 정보자료의 내용을 대표하도록 한 것

* 검색어 : Retrival term

정보 데이터베이스의 탐색 시간을 최소화하여 이용자에게 빠른 속도로 정보를 제공하기 위함

순서

1. 입력 문서들로부터 색인어를 추출

2. 역파일 구조로 색인 정보 저장

3. 일괄처리 방식으로 수행 (전체 문서를 색인)

색인 과정

1. 각 문서에서 색인어 추출

1-1 forward indexing

stopword(불용어) 제거 : 조사 (한국어: 은,는,이,가 / 영어 : a, the , is) 현재는 불용어 제거 X

1-2 stemming

1-3 색인어의 출현 빈도(TF :  Term Frequency)

2-2 Inverted File(역 파일) 생성

<문서, 색인어 list> 대응 관계를

<색인어, 문서 list> 형태로 재구성하고(Backword Indexing)

색인어 순으로 sorting 한다.

색인어별 문서 빈도(DF : Document Frequency) 계산

TF-IDF를 고려하여 각 문서의 색인어 가중치 계산

(weight = TF*IDF)

* IDF = 1/DF (DF 문서 빈도가 높다는 것은 중요하지 않다 / IDF가 높다는 것은 중요하다.

(a, the …) 빈도가 높다고 중요한 것은 아니다 -> 가중치를 달리 해야 한다.

차이가 배수로 커지므로 log 함수를 이용해 줄인다.

Inverted File 저장 구조

위의 역파일 구조로 저장한다면 가변적인 길이로 처리하기 힘들다.

이에 따라 고정적인 크기의 문서 list에 인덱싱 처리를 한다.

색인어 / 시작 위치(Index) / 문서 개수를 통해 접근한다.

색인 과정 요약

1. 각 문서들에 대한 순서대로 docID 할당 및 색인어 추출

중복 색인어 제거 및 TF 계산

(docID, <색인어, TF>)

2. 추출된 색인어들을 (색인어, docID, TF) 형태로 변환 및 색인어 순으로 sort & merge

(색인어, <docID, TF>)

3. 각 색인어들에 대한 DF 계산 및 Term Table 작성

Term Table : TermID, Index, DF

Posting File : <docID, TF>

4. 실제 검색 엔진에서는 TF와 더불어 ‘위치 정보' 색인어의 출현 위치를 함께 저장

검색

정의

사용자 질의를 분석하여 질의 내용에 적합한 문서를 찾는 과정

사용자 질의를 분석 -> 시스템 질의 형성

시스템 질의와 각 문서들과의 유사도 계산

유사도 순으로 각 문서를 정렬

검색 모델로는 벡터 공간 모델과 불린 모델이 있다.

질의 분석

사용자 질의를 분석하여 시스템 질의를 형성한다.

stemming, 가중치를 계산한다. <keyward, weight>

불린 모델(boolean  model)

집합 이론에 기반하여 있다 없다를 검색한다.

불린식으로 질의를 표현한다. 각 term들을 and, or, not의 연산자로 연결

모든 색인어들에 0(있으면) 또는 1(없으면)의 가중치를 할당

정확한 match를 통한 검색을 수행

- 불린식 전체를 만족하는 문서만을 검색

- 문서의 유사도는 1 또는 0

- 검색된 문서를 ranking 하지 못한다

q = a Λ ( b Ⅴ c )

q = (a Λ b) Ⅴ (a Λ c)

* dnf  합집합으로만 표현, Λ 교집합, Ⅴ 합집합

벡터 공간 모델(Vector space model)

불린 모델의 0과 1로는 랭킹을 측정할 수가 없다.

가중치를 0 ~ 1 사이의 값으로 측정한다.

질의와 문서를 모두 n 차원의 벡터로 표현

n : 전체 문서 집합 내에 존재하는 서로 다른 색인어의 수

각 벡터의 원소에 wi 만큼의 가중치를 할당

각각의 차원은 개별 단어에 대응된다. 어떤 단어가 문서에 포함되면, 해당 단어는 0이 아닌 벡터값을 갖는다.

단어 가중치라고도 불리는 이 값을 산출하는 방법에는 여러 가지가 있다.

wi = tf * idf

질의 벡터와 각 문서 벡터의 cos 유사도 계산

유사도 순으로 검색된 문서를 정렬

d2 * q 는 문서 벡터(오른쪽 그림의 d2)와 질의 벡터(그림의 q)의 교차점(스칼라곱)에 해당한다.

* 스칼라곱은 내적 공간이라고 불린다.

||d2|| 는  벡터 공간의 원소들에 일종의 ‘길이’ 또는 ‘크기’를 부여하는 함수이다.

적합성 피드백

정의

적합 또는 부적합 하다고 판단된 문서들 중에서 중요한 단어들을 추출하고,

이를 이용하여 질의를 재구성하여 다시 검색하는 방법

사용자의 정보 요구를 정확한 질의로 표현하기 어려움

질의어와 동일 개념의 용어라도 다른 유사 용어로 색인된 문서를 검색할 수 없다.

ex) 질의어 : 선생님 - 색인어 : 교사

검색된 문서의 정확도를 높이기 위해 사용

질의 재구성

질의 확장

가중치 재부여

벡터 공간 피드백

검색된 문서에서 문서 벡터, 용어 가중치가 높은 것이 중요하다.