[정보검색] 제8장 검색 성능 향상 전략 - 제4절 검색결과의 결합

이 글은 정영미 교수님의 정보검색연구를 바탕으로 연세대학교 문성빈 교수님의 수업을 공부한 기록입니다.

검색결과의 결합(fusion)

• 컬렉션 결합
  • 복수의 데이터베이스로부터 검색한 결과를 결합
• 데이터 결합
  • 단일데이터베이스로부터 다양한 기법에 의해 검색한 결과를 결합

컬렉션 결합

• 입력된 한 개의 질의에 대해 여러 개의 데이터베이스를 대상으로 검색을 수행한 결과 얻은 복수의 순위화된 문헌리스트를 어떻게 하나의 순위화된 리스트로 결합하여 이용자에게 제공할 것인가
• 각기 다른 복수의 데이터베이스를 검색한 결과가 이 데이터베이스들을 결합한 단일 데이터베이스를 검색한 결과와 유사하도록 만드는 것을 목적

컬렉션 결합에서 최적화시켜야 할 요인

• 각각의 데이터베이스로부터 몇개의 문헌을 검색할 것인가
• 검색된 문헌들을 결합하여 어떻게 순위화할 것인가

각각의 데이터베이스로부터 몇개의 문헌을 검색할 것인가

• 분산된 여러데이터베이스를 검색할 경우 각 데이터베이스로부터 동일한 수의 문헌을 검색하는 것은 바람직하지 X
  • 같은 검색엔진을 사용하더라도 각 데이터베이스가 질의 Q에 대해 유사한 수준의 적합성을 가지고 있다고 보기는 힘들기 때문
• 학습용 질의(training query)를 이용한 두가지 방법 제안
  • 검색된 적합문헌들의 분포를 이용한 방법
  • 질의 클러스터링을 이용한 방법
• 적합문헌 분포를 이용한 방법
  1. m개의 학습 질의와 검색용 질의 Q와의 유사도를 산출하여 검색 질의와 가장 유사한 k개의 학습 질의를 찾아낸다.
  2. k개의 학습 질의에 대한 검색결과로부터 적합문헌 분포를 산출한다
  3. 적합문헌 분포를 이용하여 각 컬렉션으로부터 검색할 문헌의 수를 산출한다.
• 질의 클러스터링을 이용한 방법
  1. 학습 질의가 공통으로 검색한 문헌수를 이용하여 학습 질의들을 클러스터링 한 후 각 질의 클러스터의 센트로이드를 산출한다.
  2. 각 학습 질의 클러스터에 속하는 질의들이 각 컬렉션으로부터 검색한 평균 적합문헌 수를 컬렉션 가중치로 부여한다.
  3. 검색용 질의가 입력디면 이 질의벡터와 학습 질의 클러스터 센트로이드를 비교하여 가장 유사한 학습 질의 클러스터를 찾아낸다.
  4. 각 질의 클러스터와 관련된 가중치를 이용하여 각 컬렉션으로부터 검색할 문헌 수를 결정한다.

검색된 문헌들을 결합하여 어떻게 순위화할 것인가

• 여러 컬렉션으로부터 검색되어 각기 다르게 순위화되어 제공되는 문헌들을 단일 순위로 통합하는 일과 관련
• 검색문헌들을 결합하여 순위화하는 방법은
  • 각 컬렉션으로부터 검색문헌의 순위만 제공되는지
  • 질의에 대한 문헌의 적합성 정도를 나타내는 문헌점수가 함께 제공되는지
• 에 따라 달라질 수 O
• 순위만 제공되는 경우
  • 여러 검색 문헌들을 순위에 따라 끼워 넣어 새로운 하나의 순위를 생성
  • 각 개별 시스템의 순위를 순위 값으로 변환하여 단일 순위화
• 순위 뿐만 아니라 문헌점수 또한 제공되는 경우
  • 컬렉션에 따라 유사도 값의 범위가 달라질 수 있으므로 유사도의 최대값과 최소값을 이용하여 각 유사도 값을 정규화 할 필요 O
  • 각 컬렉션의 크기가 다를 경우 유사도 산출에 사용되는 용어 가중치 값의 수정을 통해 문헌점수를 정규화 할 수 O

Callan, Lu, and Croft (1995)

• 컬렉션들이 넓게 분산되어 있고 동적일 경우 적용할 수 있는 결합 기법을 제안
• 일반적인 문헌 검색 시스템에서 구축하는 문헌 수준의 색인 이외에 컬렉션 수준의 색인을 구축하는 것이 핵심
  • 각 컬렉션을 하나의 가상 문헌으로 취급
  • 컬렉션 색인어의 가중치는 문헌 색인어의 TF-IDF 가중치 개념을 적용하여 산출
  • 문헌 내 단어빈도(TF)는 특정한 컬렉션에서 색인어가 출현한 문헌 수를 나타내는 문헌빈도(DF)로 대체
  • 문헌빈도는 색인어를 포함하는 컬렉션 수를 의미하는 장서빈도(CF)로 대체
  • 역문헌빈도(IDF)는 역장서빈도(ICF)로 대체
• 질의 Q에 대한 검색
  1. 컬렉션 색인을 이용하여 질의 Q에 대해 유사한 순서로 컬렉션을 순위화하고,
  2. 상위 k개의 컬렉션을 대상으로 문헌 색인을 이용하여 문헌을 검색한다.
• 실험 결과 문헌의 유사도 값과 컬렉션 가중치를 결합한 값으로 문헌을 순위화하는 방식이 효과적

데이터 결합 (Data Fusion)

• 동일한 컬렉션에 대해 여러 다른 검색 관련 기법들을 적용하여 검색한 결과들을 통합하는 전략
• 데이터 결합의 필요성
  • 상이한 검색 관련 기법을 사용하여 검색한 문헌들은 상호중복성이 매우 낮다는 실험 결과 존재
  • 따라서 다른 기법들을 사용하여 검색한 결과를 통합하면 단일 기법을 사용하는 것보다 질의에 적합한 문헌을 더 많이 제공할 수 있을 것
• 데이터 결합에서 결합 대상이 되는 검색 관련 기법들
  1. 다른 문헌 표현 방법
  2. 다른 질의 형식
  3. 다른 용어 가중치
  4. 다른 검색 알고리즘
  5. 다른 검색 순위

1. 문헌 표현 방법의 결합

• 다른 유형의 색인어 또는 문헌 표현 방법을 결합하는 것
  • 다른 유형의 색인어: 자동색인 결과 생성된 키워드, 수작업으로 부여된 디스크립터
• 다른 단위의 문헌 텍스트를 결합하는 것
  • 다른 단위의 문헌 텍스트: 색인어 추출 대상이 되는 텍스트 부분: 표제, 초록, 단락, 전문

2. 질의 형식의 결합

• 동일한 정보요구를 표현한 키워드 질의, 불리언 질의, 확장 불리언 질의 등을 결합하는 것

4. 검색 알고리즘의 결합

• 불리언 검색, p-norm 검색, 확률검색 등 다른 검색 모형을 사용하여 검색한 결과를 결합하는 것

5. 검색 순위의 결합

• 여러 검색 결과를 하나의 리스트로 순위화하여 제공
• 데이터 결합에서 복수의 검색 기법이나 복수의 용어 가중치를 사용할 경우 각 검색 결과를 통합하여 제공하게 되므로 먼저 검색문헌의 유사도 값을 정규화할 필요 O
  • 왜냐하면 각기 다른 검색 방법은 다른 범위의 유사도 값을 산출할 수 있기 때문
• 문헌점수를 정규화하는 방법
  • 최대값 정규화 (max_normalization)
  • 최소-최대값 정규화 (min_max_normalization)
• 문헌점수가 정규화되면 특정 문헌이 새로 생성되는 통합 리스트에서 부여받게 될 순위를 결정하기 위해 각 문헌점수를 결합하여 단일 문헌점수를 산출
• 결합함수
  • CombMAX = MAX(개별 유사도 값들) : 최대값
  • CombMIN = MIN(개별 유사도 값들) : 최소값
  • CombSUM = SUM(개별 유사도 값들) : 합계
  • CombANZ = CombSUM / 0이 아닌 유사도 값의 수 : 평균값
  • CombMNZ = CombSUM * 0이 아닌 유사도 값의 수 : 보정 합계
  • CombMED = MED(개별 유사도 값들) : 중간값