5장 질의 연산 

5.1 소개

5.2 사용자 연산 피드백

5.3 자동 지역 분석

5.4 자동 전역 분석

5.5 연구 동향 및 쟁점

5.6 참고 문헌 고찰

최신정보검색론  

Chapter 12  

2  

5.1 소개 

• 질의어 확장과 가중치 재계산으로 처음 질의를 개선하는 방법들을 소개

- 사용자 피드백 정보를 이용하는 방법

- 처음 검색된 문헌 집합

- 문헌 집합 전체에서 추출된 정보를 이용하는 방법 

• 벡터 및 확률 모델에 있어서 사용자 연관 피드백 방법
• 지역 분석에 대한 두 가지 방법
• 두 가지 전역 분석 방법

최신정보검색론  

Chapter 12  

3  

5.2 사용자 연관 피드백 

• 연관  피드백 : 질의 재작성 방법

• 적합성 피드백의 장점

- 사용자는 문헌 연관성 정보만 제공

- 연관 피드백 과정의 자세한 사항은 알 필요가 없음

- 전체 검색 프로세스를 이해하기 쉬운 작은 단계로 분할함

- 용어의 강조, 다른 용어의 중요도를 감소를 위해 통제된 과정을 제공 
 

최신정보검색론  

Chapter 12  

4  

5.2.1 벡터 모델에서의 질의 확장 및  
용어 가중치 재부여 

• 연관 문헌인 경우

- 연관 문헌들의 용어-가중치 벡터와 서로 유사한 사실을 이용

• 비연관 문헌인 경우

- 연관 문헌들의 용어-가중치 벡터와는 다른 벡터라고 가정함

• 질의 q의 처리에 대한 추가적인 용어 정의

  Dr  : 검색된 문헌 중에서 사용자에 의해 연관 문헌으로 판단된  

         문헌 집합

  Dn : 검색된 비연관 문헌 집합

  Cr : 컬렉션 내 모든 문헌 중 연관 문헌 집합

|Dr|, |Dn|, |Cr| : 각 집합 Dr, Dn, Cr의 문헌 수

                  :  조절 상수

최신정보검색론  

Chapter 12  

5  

5.2.1 벡터 모델에서의 질의 확장 및  
용어 가중치 재부여 (계속) 

• 최적 질의 벡터

• 수정된 질의   을 계산하는 세가지 방법

최신정보검색론  

Chapter 12  

6  

5.2.2 확률 모델에서의 용어 가중치 재부여 

• 질의 q와 유사한 문헌들을 확률 순위화 원칙에 의해 동적으로 순위화함
• 문헌 dj와 질의 q의 유사도

• 초기 검색을 위한 가정들

- P(ki|R)값은 모든 용어 ki에 대해 상수 값(보통 0.5)

- 용어 분포 확률은 전체 컬렉션 분포로 근사함 
 
 
 
 

최신정보검색론  

Chapter 12  

7  

5.2.2 확률 모델에서의 용어  
가중치 재부여 (계속) 
 
 

• 확률P(ki|R)와 P(ki|  )의 비교 (근사함)

• |Dr|,|Dr,i|가 매우 작아지는 문제로 조정 계수(0.5)를 합함

최신정보검색론  

Chapter 12  

8  

5.2.2 확률 모델에서의 용어  
가중치 재부여 (계속) 

• 조정 계수 0.5는 불만족스러운 결과를 생성할 수 있음
• ni/N 또는 (ni-|Dr,i|)와 같은 다른 조정 계수를 제안

• 이 연관 피드백 과정의 주요 장점

- 피드백 과정이 질의 용어의 새로운 가중치 계산과 직접적 연관

- 이진 색인, 색 인어 독립성을 가정시 용어 가중치 재부여가 최적화

• 단점

- 피드백 과정에서 문헌 내 용어 가중치가 고려되지 않음

- 이전 질의에서의 용어 가중치가 무시됨

- 질의 확장이 없음

최신정보검색론  

Chapter 12  

9  

5.2.3 확률적 용어 가중치 재부여의 변형 

• 확률화 순위와 식

• Croft의 초기 검색과 피드백 검색에 다른 수식을 제안

-    는 정규화된 문헌 내의 출현 빈도

- 인수 C, K는 각 컬렉션에 맞게 조정

- 자동 색인된 컬렉션에서는 C가 초기에 0으로 지정 
 

최신정보검색론  

Chapter 12  

10  

5.2.3 확률적 용어 가중치 재부여의 변형 
(계속) 

• Croft가 제안한 피드백 검색에서 Fi,j,q 식

• 확률적 용어 가중치 재부여 변형 방법의 장점

- 문헌 내 출현 빈도를 고려

- 정규화된 출현 빈도를 사용

- C, K상수를 도입하는데 매우 큰 융통성을 제공

• 단점

- 더 복잡한 수식을 사용

- 질의 확장이 없음

최신정보검색론  

Chapter 12  

11  

5.2.4 연관 피드백 방법들의 평가 

• Rocchio식을 이용한 검색 성능 향상 평가

- 피드백 과정에서 연관된 집합 R내의 문헌들에게 높은 순위를 줌 

- 이 문헌들은 검사하였기 때문에 이러한 평가는 비현실적임 

• 현실적인 방법

- 잔여 컬렉션만을 고려하는 것 

    잔여 컬렉션을 대상으로 재현율-검색률 측정이 일반적

최신정보검색론  

Chapter 12  

12  

5.3 자동 지역 분석 

• 전역적 방법

- 컬렉션 내 전체 문헌을 사용

- 용어 연관성을 나타내는 전역적 유사 소서러스 구조를 작성

- 사용자는 자신에게 제시된 이 구조를 이용

- 질의 확장을 위한 용어를 선택 

• 지역적 방법

- 질의 q에 의해 검색된 문헌들을 이용

- 질의 시간에 질의 확장을 위한 용어를 선택

- 사용자의 도움이 필요 없음

- 지역 클러스터링, 지역 문맥 분석 방법

최신정보검색론  

Chapter 12  

13  

5.3.1 지역 클러스터링을 통한 질의 확장 

• 정의

• 이 전략의 지역적 성질

• 현재 질의에 의해 검색된 문헌만을 대상으로 작업
• 검색된 문헌의 내용에 접근해야 할 필요성이 빈번하게 발생
• 이 지역 전략을 웹 환경에 적용하는 것은 비현식적

V(s)는 공집합이 아니며, 전체 단어의 부분 집합으로 서로 문법적 이형태 (variants) 단어들을 모은 집합이라고 하자. V(s)의 정규 형태 s를 스템(stem)이라고 한다. 예를 들어 V(s)={polish, polishing, polished}이라면 s=polish가 된다. 

주어진 질의 q에 대해, 검색된 문헌 집합 Dl을 지역 문헌 집합이라고 하고 이 지역 문헌 집합에 나타나는 서로 다른 모든 집합 Vl을 지역 어휘라고 부른다. Vl집합으로부터 추출된 서로 다른 모든 스템의 집합을 Sl로 표시한다.

최신정보검색론  

Chapter 12  

14  

5.3.1 지역 클러스터링을 통한 질의 확장 (계속) 

• 연관(association)클러스터

• 연관 계수를 정규화

문헌                내에서의 어떤 스템 si의 빈도를 f si,j로 표시한다.

               는 |Sl|행과 |Dl|열로 구성된 연관 행렬이며, mij= f si,j

    은     의 도치(transpose) 행렬이며, 행렬              은 지역 스템간 연관 행렬이 된다.    의 각 요소        는 스템     와     의 연관도 c u,v를 나내며 다음과 같이 구할 수 있다. 
 
 

최신정보검색론  

Chapter 12  

15  

5.3.1 지역 클러스터링을 통한 질의 확장 (계속) 

• 지역 연관 클러스터

• 질의 시간에 효과적으로 계산될 수 있다는 것을 의미함

연관 행렬     의 u번째 행(즉, 스템    의 모든 용어를 표시하는 행)을 고려해보자

U번째 열을 받아 모든         (v는 지역 스템을 정의역으로 하며,         이다) 값들 중 가장 큰 n개의 값을 반환하는 함수를     (n)이라고 하자. 그러면     (n)은 스템     의 지역 연관 클러스터를 정의하게 된다. 만약         가 식 5.6을 이용하여 계산되면 연관 클러스터는 정규화되지 않았다고 하며, 식 5.7을 이용하여 계산되면 연관 클러스터는 정규화되었다고 한다.

최신정보검색론  

Chapter 12  

16  

5.3.1 지역 클러스터링을 통한 질의 확장 (계속) 

• 메트릭(Metric)클러스터

• 다르게 연관 계수를 정규화 (5.9)

두 키워드 ki와 kj 사이의 거리 r(ki, kj)를 한 문헌 내에서 두 키워드 사이에 출현하는 단어의 수로 정의한다. 만약 두 키워드 ki, kj가 같은 문헌에 출현하지 않으면                      이다. 지역 스템간 메트릭 연관 행렬     는 다음과 같이 되는데 s의 각 요소          는 스템     와      사이의 연관도 c u,v를 나타낸다. 즉, 

최신정보검색론  

Chapter 12  

17  

5.3.1 지역 클러스터링을 통한 질의 확장 (계속)  

• 지역 메트릭 클러스터의 정의

메트릭 연관 행렬    의  u번째 행렬(즉, 스템     에 대한 모든 연관을 나타내는 행)을 입력으로 하여, 모든         (v는 지역 스템을 정의역으로 하며,           이다) 값들 중 가장 큰 n개의 값을 반환하는 함수를      (n)이라고 하자. 그러면

     (n)은 스템     의 지역 메트릭 클러스터를 정의하게 된다. 만약          가 식 5.8을 이용하여 계산되면 메트릭 클럴스터는 정규화되지 않았다고 말하며, 식 5.9를 이용하여 계산되면 메트릭 클러스터는 정규화되었다고 한다.

최신정보검색론  

Chapter 12  

18  

5.3.1 지역 클러스터링을 통한 질의 확장 (계속) 

• 스칼라(Scalar)클러스터

                                            을 스템      와      의 연관 계

수벡터라고 하자.     =  (          )를 스칼라 연관 행렬이라고 하면, 각           는 다음과 같이 정의 된다. 
 
 
 

                                                                                              (5.10) 

   (n)을 식 5.10에서 정의 된 모든         (       )값 중 가장 큰 n개의 값을 반환하는 함수라고 하면 Su(n)은 스템     의 스칼라 클러스터를 정의하게 된다.

최신정보검색론  

Chapter 12  

19  

5.3.1 지역 클러스터링을 통한 질의 확장(계속) 

• 대화적 탐색 명시

최신정보검색론  

Chapter 12  

20  

5.3.2 지역 문맥 분석을 통한 질의 확장 

• 지역 문맥 분석 방법 : 전역 분석의 아이디어를 검색된 지역 문헌에만 적용한 예
• 전역분석과 지역 분석을 결합한 것

- 전역 분석 방법 : 전체 컬렉션을 이용하여 용어 연관 관계를 탐색하는 것

• 지역 문맥 분석 과정

- 현재 질의를 사용하여 상위 n개의 단락을 검색

- 해당 개념과 전체 질의와의 유사도 sim(q,c)를 계산

- m개의 상위 순위 개념이 원래 질의에 추가

- 각 개념에 1-0.9*i/m의 가중치가 부여

- 원래 질의 q에 있던 용어들은 가중치를 2로 부여함 (강조)

최신정보검색론  

Chapter 12  

21  

5.3.2 지역 문맥 분석을 통한 질의 확장 (계속) 

• 각 연관 개념 c와 원래 질의 q사이의 유사도 sim(q,c)
• N: 상위 순위 단락의 수

최신정보검색론  

Chapter 12  

22  

5.4 자동 전역 분석 

• 컬렉션 전체 문헌으로부터 추출된 정보를 이용하여 질의를 확장

• 이 절에서 소개하는 방법은 컬렉션 전체 문헌을 이용하여 작성된 유사 시소러스 구조를 사용

• 시소러스를 작성하는 방법과 질의 확장을 위한 용어 선택 방법은 매우 상이함

최신정보검색론  

Chapter 12  

23  

5.4.1 유사도 시소러스를 이용한 질의 확장 

• 정의

앞에서와 같이, t는 전체 컬렉션의 용어 수, N은 컬렉션 내의 총 문헌 수, fi,j 를 문헌 dj에서의 용어 ki의 빈도, tj를 문헌di의 색인어 수라고 하자. 또, itfi 를 문헌 di의 역 용어 빈도라고 하면 itfi는 역문헌 빈도 정의와 비슷하게 다음과 같이 정의된다. 

(5.11) 

(5.12)

최신정보검색론  

Chapter 12  

24  

5.4.1 유사도 시소러스를 이용한 질의 확장 (계속) 

• 전역 유사 시소러스 질의 확장의 3단계
• 색인 용어를 표현하기 위해 사용된 개념 공간상에 질의표시
• 각 용어 kv에 대한 전체 질의에 대한 유사도 sim(q,kv)계산
• sim(q,kv)에 따라 정렬한 상위 r개의 용어를 사용/질의 확장
• 색인 용어 벡터의 개념 공간상에 표시

질의 q에 대해 다음과 같은 용어-개념 공간상의 벡터    가 부여된다. 
 
 
 

여기서 wi,q 색인어-질의 쌍 [ki,q]에 부여된 가중치이며, 식5.11의 색인어-문헌 가중치와 비슷하게 계산된다. 

최신정보검색론  

Chapter 12  

25  

5.4.1 유사도 시소러스를 이용한 질의 확장 (계속) 

• 각 용어 kv와 사용자 질의와의 유사도 sim(q,kv)

[그림 5.2] 질의 중심 Qc로부터

주어진 용어 Kv까지의 거리는

각각의 질의 용어로부터 Kv까지

의 거리와 매우 다를 수 있다

최신정보검색론  

Chapter 12  

26  

5.4.1 유사도 시소러스를 이용한 질의 확장 (계속)

최신정보검색론  

Chapter 12  

27  

5.4.1 유사도 시소러스를 이용한 질의 확장 (계속) 

[그림 5.3] 완전 링크 알고리즘을 이용해 작성된 세 클러스터 계층(클러스터간 유사도는 타원 내 숫자로 표시)

최신정보검색론  

Chapter 12  

28  

5.4.2 통계 시소러스를 이용한 질의 확장 

• 완전 링크(complete link) 알고리즘

- 각 문헌을 다른 클러스터에 둠

- 모든 클러스터 쌍 사이의 유사도를 계산

- 클러스터간 유사도가 가장 큰 클러스터 쌍 [Cu,Cv]를 결정

- 두 클러스터 Cu, Cv를 통합

- 정지 조건을 검사

- 클러스터 계층을 반환

최신정보검색론  

Chapter 12  

29  

5.4.2 통계 시소러스를 이용한 질의 확장 (계속) 

• 전역 시소러스의 클래스를 구성하는 용어의 선택

- 클래스 임계값, 클래스 문헌 수, 역 문헌 빈도 최소값 인수를 얻음

- Cu와 Cv 가 한 시소러스 클래스를 생성하려면 sim(Cu,Cv)가 임계값 보다 커야 함

- NDC 인수를 사용하여 대상 클러스터의 크기를 제한함

- 한 클러스트 내중 오직 저빈도 문헌에서만 시소러스 클래스 용어가 선택

최신정보검색론  

Chapter 12  

30  

5.4.2 통계 시소러스를 이용한 질의 확장 (계속) 

• 각 시소러스 클래스 C에 대한 평균 용어 가중치

• 시소러스 클래스 가중치

최신정보검색론  

Chapter 12  

31  

5.5 연구 동향 및 쟁점 

• 최신 정보 시스템의 그래픽 인터페이스에 바로 적용
• 그러나 대화성이 중요하므로 피드백 정보를 얻는 새로운 기술이 요구됨
• 전역 분석 기술은 질의에 제공된 지역 문맥을 활용함
• 중요한 연구 과제

- 지역 분석, 전역 분석, 시각 표시 장치와 대화적 인터페이스를 조합하는 문제

• 중요한 쟁점

- 사용자로 하여금 문헌 공간을 시각적으로 항해하는 문제

- 질의 작성을 돕는 단서를 제공하는 문제

최신정보검색론  

Chapter 12  

32  

5.6 참고 문헌 고찰 

• 1960년 Maron, Kuhn[547]: 사용자 질의를 확장의 초기 연구
• 1965년 Rocchio[678]: 질의 확장과 가중치 재계산 연구
• 1976년 Robertson, Sparch Jones[677]: 초기 확률 모델
• 1978년 Harper, van Rijabergen: 확률적 질의 확장을 위해 클러스터링 기술을 이용
• 1983년 Croft[198]: 문헌 내 용어 빈도를 위해 확률식에 C, K 인수를 도입
• Voorhees[793], Crouch, Yang[200], Qui, Frei[655]의 실험 :

     전역 분석을 이용한 질의 확장이 일관성 있게 검색 성능을 개선

• 1977년 Attar, Fraenkel[35]: 지역 분석을 통한 질의 확장 논의
• 1996년 Xu, Croft[838]: 지역 문맥 분석
• Qui, Frei[655]: 전역 유사 시소러스를 통한 질의 확장
• Crouch, Yang[200]: 전역 통계 시소러스를 통한 질의 확장