5장 질의 연산 5.1 소개 5.2 사용자 연산 피드백 5.3 자동 지역 분석 5.4 자동 전역 분석 5.5 연구 동향 및 쟁점 5.6 참고 문헌 고찰 최신정보검색론 Chapter 12.

Presentation on theme: "5장 질의 연산 5.1 소개 5.2 사용자 연산 피드백 5.3 자동 지역 분석 5.4 자동 전역 분석 5.5 연구 동향 및 쟁점 5.6 참고 문헌 고찰 최신정보검색론 Chapter 12."— Presentation transcript:

1 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 벡터 모델에서의 질의 확장 및 용어 가중치 재부여
5.2.1 벡터 모델에서의 질의 확장 및 용어 가중치 재부여 연관 문헌인 경우 - 연관 문헌들의 용어-가중치 벡터와 서로 유사한 사실을 이용 비연관 문헌인 경우 - 연관 문헌들의 용어-가중치 벡터와는 다른 벡터라고 가정함 질의 q의 처리에 대한 추가적인 용어 정의 Dr : 검색된 문헌 중에서 사용자에 의해 연관 문헌으로 판단된 문헌 집합 Dn : 검색된 비연관 문헌 집합 Cr : 컬렉션 내 모든 문헌 중 연관 문헌 집합 |Dr|, |Dn|, |Cr| : 각 집합 Dr, Dn, Cr의 문헌 수 : 조절 상수 최신정보검색론 Chapter 12

5 5.2.1 벡터 모델에서의 질의 확장 및 용어 가중치 재부여 (계속)
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| )의 비교 (근사함)
5.2.2 확률 모델에서의 용어 가중치 재부여 (계속) 확률P(ki|R)와 P(ki| )의 비교 (근사함) |Dr|,|Dr,i|가 매우 작아지는 문제로 조정 계수(0.5)를 합함 최신정보검색론 Chapter 12

8 5.2.2 확률 모델에서의 용어 가중치 재부여 (계속) 조정 계수 0.5는 불만족스러운 결과를 생성할 수 있음
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식을 이용한 검색 성능 향상 평가
- 이 문헌들은 검사하였기 때문에 이러한 평가는 비현실적임 현실적인 방법 - 잔여 컬렉션만을 고려하는 것 잔여 컬렉션을 대상으로 재현율-검색률 측정이 일반적 최신정보검색론 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 유사도 시소러스를 이용한 질의 확장 (계속) 최신정보검색론 Chapter 12
[그림 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]: 전역 통계 시소러스를 통한 질의 확장 최신정보검색론 Chapter 12