정보검색론: 정보검색 모형1

검색 모형의 종류

*불리언 검색 모형

*벡터공간 검색 모형

*확률 검색 모형

*퍼지집합 검색 모형

*확장 불리언 검색 모형

ad hoc 검색과 라우팅/필터링

*TREC-4 이전

- ad hoc 검색 : 정적인 정보원을 대상으로 동적인 질의를 처리

- 라우팅

*TREC-7 이후

- ad hoc 검색

- 필터링

-- 적응적 필터링: 적합성 피드백 시스템이 도입된 필터링

-- 배치 필터링: 대량의 학습문헌(적합문헌+부적합문헌)으로 프로파일을 구축하여 필터링 시행

-- 라우팅: 순위화하여 문헌을 출력함

불리언 검색: 불 대수를 이용하여 질의를 만족시키는 문헌을 검색하는 기법

1.각 검색어를 색인어로 가지는 문헌집합들을 생성함.

2.생성된 집합을 AND, OR, NOT 논리관계에 맞추어 교집합, 합집합, 차집합 연산을 수행함.

*도치색인/역색인

- 사전파일과 문헌번호파일을 이용해 시스템을 구성하는 것. (벡터공간 검색이나 확률 검색에서도 사용됨)

- 먼저 사전파일에서 해당하는 색인어를 찾아서, 그 포인터가 가리키는 곳으로 가면 문헌번호 파일들이 있다.

- 위의 예에서는 ABILITY에 해당하는 문헌번호로 5, 27, 42가 있고, 각각의 문헌에 따라 TF와 단어가 등장하는 위치를 알 수 있다.

- 문헌번호파일은 링크드 리스트 형식으로 구성되어 있어서, 차례로 다음 문헌으로 순회할 수 있게 되어있다.

- 단어번호를 이용해 인접검색을 수행할 수도 있다.

불리언 검색의 장점

*구현하기가 쉬움

*질의처리가 매우 효율적임

*상용 시스템에서 보편적으로 사용됨

불리언 검색의 한계

*검색어의 상대적인 중요도를 나타낼수 없음

*적합성 정도에 따라 순위화가 불가능함

*완전일치 문헌만 검색이 가능, 부분일치 문헌은 검색되지 않음

퍼지집합 검색: 전통적인 불리언 검색이 완전히 속하거나(1), 전혀 속하지 않거나(0)의 binary 시스템이었다면, 퍼지 모델은 속하는 정도에 따라 0~1 사이의 실수값을 부여할 수 있는 시스템

*퍼지집합의 정의: 멤버쉽 함수 f를 다음과 같이 정의함

= X가 집합 A에 속하는 정도 (0~1사이의 실수값)

합집합

교집합

차집합

D1 = {디지털: 0.5, 도서관: 0.6}

D2 = {디지털: 0.7, 도서관: 0.2}

D3 = {디지털: 0.9, 도서관: 0.4} 일때, "디지털 AND 도서관"이라는 질의는 다음과 같이 평가된다.

fA(D1) = 0.5, fB(D1) = 0.6 => fAnB(D1) = 0.5

fA(D2) = 0.7, fB(D2) = 0.1 => fAnB(D2) = 0.1

fA(D3) = 0.9, fB(D3) = 0.4 => fAnB(D3) = 0.4

따라서 D1, D3, D2의 순으로 순위매겨진다.

퍼지집합 검색의 장점

* 개념의 중요도를 표현할 수 있어 불리언 검색보다 융통성이 있음

* 검색된 문헌을 적합성에 따라 순위매길 수 있음

퍼지집합 검색의 한계

* 색인어에 가중치를 부여해야만 부분 멤버쉽함수를 적용할 수 있음

* 순위부여 능력은 모든 검색어에 대해 민감하지 못함 : 위의 예에서 D2 평가값은 0.1로 제일 낮게 나왔지만, 이용자가 '디지털'이라는 검색어를 더 중요시여겼을 경우에는 D2가 더 적합할 수 있다.

확장 불리언: MMM(Mixed Min and Max)모형

- 퍼지집합 검색 모형에서는 AND, OR 연산 시에 최대값과 최소값 중 하나만을 반영한 반면, MMM에서는 두 값을 모두 반영한다.

* MMM 연산의 정의

검색어 A, B, C와 문헌 D사이의 유사도는 다음과 같이 계산한다. (dA, dB, dC는 문헌 D가 가지는 A, B, C에 대한 색인어 가중치이다)

SIM(A and B and C, D) = a * min(dA, dB, dC) + (1-a) * max(dA, dB, dC)

SIM(A or B or C, D) = b * max(dA, dB, dC) + (1-b) * min(dA, dB, dC)

a와 b는 연성계수로써 a=1, b=1인 경우는 퍼지집합 검색과 동일해진다. 보통 0.5 <= a <= 0.8일때, b > 0.2 일때 좋은 성능을 보이는 것으로 보고되었음.

확장 불리언: P-norm 모형

- P-norm 모형은 색인어뿐만 아니라 검색어에도 가중치를 부여할 수 있음

* P-norm 연산의 정의

검색어 A_n에 대해 a_n의 가중치가 부여되어있다고 가정하자. 이때 검색어와 문헌 D 사이의 유사도는 다음과 같이 계산한다. (dA_n은 문헌 D가 가지는 A_n에 대한 색인어 가중치이다)

p는 파라미터로써, p=1인 경우는 and 연산과 or연산의 결과가 같아지며, 벡터공간 모형과 일치하게 된다. p=∞인 경우는 전통적인 불리언 모형과 같아진다. p=2일때 아주 좋은 성능을 보이는 것으로 보고되었다.

벡터공간 검색: 문헌과 질의를 용어벡터로 표현하여, 벡터 간의 유사도를 이용해 검색문헌을 순위화하는 모형

유사도 계수로는 주로 코사인 유사계수 공식을 사용한다.

*유사도 계산 예시: D는 문헌, Q는 검색어라고 하면, 나타나는 용어를 바탕으로 다음과 같이 표현할 수 있다

D = (온라인:3, 정보:2, 검색:3, 파일:1, 조직:1)

Q = (온라인:1, 문헌:1, 검색:1)

이를 벡터로 변환하면

D = (3, 2, 0, 3, 1, 1)

Q = (1, 0, 1, 1, 0, 0)

코사인 유사계수는 다음과 같이 계산된다.

SIM(D, Q) = (3*1 + 3*1) / sqrt((9+4+9+1+1) * (1+1+1)) = 0.7071