3.2 질의 절차

(1)

2013. 09. 08

가천대학교 IT대학 컴퓨터미디어융합학과

Information Retrieval

제3장 질의 연산

(2)

3.1 소개

3.2 질의 절차

3.3 관련성

3.4익힘 문제

(3)

3

3.1 개요

Query is a statement /program

of information request to database.

database: a set of data

statement: 편의성, 프로그램 부담 감소. DBMS program: a set of codes. IRS

Query: 사용자의 정보 요구를 수식화 한 문장.

(4)

4

3.1 개요

질의

- 질의는 데이터베이스에서 정보검색을 요구하는 문장.

- 질의는 사용자의 정보 요구를 수식화한 문장(프로그램).

연산:

- 원소들을 조작하여 다른 원소를 만드는 절차

- 어떤 집합의 원소들 사이에 일정한 조작을 적용하여 다른 원소를 이끌어내는 절차.

- 연산은 문제 해결을 위하여 명령어(instruction)를 실행 하는 것.

(5)

5

3.1 개요

질의 연산

- 검색을 위하여 문서 집합과 질의의 유사도를 계산하는 절 차

- 질의를 해석하고 문서 집합에 적용하여 관련 문서를 검색 하는 절차

(6)

6

Why Query?

Query is power of getting information from database.

질의 연산의 목적:

- 검색되는 문서의 수를 증가시키는 것.

- 관련된 문서의 수가 많아지도록 검색 프로그램을 작성하는 것.

(7)

7

3.1 개요

3.1.1 질의 종류

검색, 탐색, 브라우즈

검색 retrieval

원하는 자료를 database에서 찾아서 가져오는 것.

from what to get ex. 화석 발굴.

탐색 search

from what to where. .ex. 인공 위성 탐사

원하는 자료의 위치를 database에서 찾는 것.

(8)

8

3.1 개요

둘러보기 browse from where to what

database에 있는 모든 자료를 축적 순서대로 읽는 작업.

디렉토리(path)를 따라가면서 원하는 정보를 살펴보는 것.

ex. 백화점 eye 쇼핑

질의 결과:

검색된 문서들의 순위화.

단어 빈도수, 역문헌 빈도수

(9)

9

3.1 개요

질의 종류

구 분 둘러보기 탐 색 검 색

입 력 ^범위 ^색인어 ^색인어

자료 이동 ^no ^no ^yes

결 과 ^없음 ^위치 ^{원하는 정보}

작업량 ^{전체 읽기} ^읽기 ^{자료 전송}

속 도 ^보통 ^빠름 ^느림

특 징 from where to what

from what

to where from what to get

(10)

10

3.1 개요

질의의 문제점

검색되는 문서의 수가 적다.

- 질의 결과가 너무 적어서 문제

사용자 요구를 정확하게 표현하기 곤란

- 만족한 결과를 얻기 위해 질의 작성에 많은 시간 소요

해결책

초기 질의를 사용해서 관련 정보를 검색 검색된 문서를 사용해서 질의를 재작성 - 질의 확장:

- 용어 가중치 재부여:

(11)

11

3.1.2 개요 질의절차

질의 확장

새로운 용어를 원래 질의에 추가 질의에 포함된 용어 변경

검색되지 않은 관련 문서 검색에 도움

질의 용어 가중치 재부여

가중치를 조정하여 순위화를 조정

관련 문서에 출현되는 질의 용어의 가중치를 추가

검색되지 않은 관련 문서를 검색하는데 도움이 되지 않는다.

(12)

12

3.1 개요 질의 절차

(1) 자료 검색

사용자가 SQL 문을 DBMS에 입력

 DBMS가 구문분석, 최적화, 코드 생성, 코드실행  DBMS가 보고서를 작성하여 자용자에게 제공

(13)

13

3.1 개요 질의 절차

(2) 문서 검색

사용자가 원하는 문자를 IRS(정보검색 시스템)에 입력  IRS가 해당 문자가 있는 위치를 찾아서

 쪽번호, 줄번호 등의 정보를 사용자에게 제공 워드 프로세서의 찾기 기능과 유사한 기능

(14)

14

3.1.3 질의 형태

Pulling Process(주문형 서비스)

정보와 자료 검색: 사용자 요구를 질의하여 결과 제공.

브라우징: 시스템이 제공하는 안내를 따라 다닌다.

Pushing Process(선지원 서비스)

사용자에게 주기적으로 유용한 정보를 추출하여 제공 정보 여과(filtering)

각 사용자의 profile에 의해 관련 정보를 추려서 제공.

ex. 이메일이나 휴대폰으로 관심 주식의 정보 제공

(15)

15

3.1.3 질의 형태

질의 문제점

검색 결과 부족, 부정확

질의 대책 - 질의 확장 - 가중치 부여

(16)

16

3.2 질의 절차

현행 기술: 내용기반 질의, 개념기반 질의

3.2.1 키워드기반 질의

Keyword: 검색어, 핵심어, 주제어

텍스트 자료의 탐색 대상 값.

문서의 내용이나 제목을 요약한 핵심적인 단어.

질의: 키워드로 구성. 질의 대상: 키워드로 구성된 문서.

키워드 탐색의 전제

1) 질의가 문서 안에 그대로 나타나 있다.

2) 질의에 있는 단어들은 순서에 관계 없이 문서에 자주 나타 난다.

(17)

17

3.2 질의 절차

대표적인 질의 표현 기법

^{질의 기법} ^{특 징}

키워드 기반 질의 문서의 주제를 나타내는 단어들로 구성된 색인을 이용하는 질의

불리언 질의 불 논리를 이용하여 연산 조건에 맞는 결과를 계산하는 질의

내용기반 질의 문서 내용의 유사성을 기반으로 원하는 결과를 계산하는 질의

순위 질의 검색 결과에 우선순위를 부여하는 질의

개념기반 질의 질의와 문서의 개념을 비교하여 결과를 계산하는 질의

(18)

18

3.2 질의 절차

3.2.1 Keyword 기반 질의

키워드 ?

1) 문서의 내용이나 제목을 요약한 핵심적인 단어

2) 정보검색 시에 텍스트 자료의 탐색 대상이 되는 값

3) 원하는 문서가 포함되어 있다고 간주하고 질의하는 대표 적인 단어

키워드 기반 질의의 전제 조건 1) 질의 내용이 문서 안에 존재.

2) 질의에 있는 단어들은 순서에 관계없이 문서에 자주 출 현.

(19)

19

3.2 질의 절차

Keyword 기반 질의의 문제점

동의어 검색 곤란

- ‘restaurant’ vs. ‘café’

- ‘ROK’ vs. ‘Korea’

비 관련 단어 검색

- ‘bat’(baseball vs. mammal) - ‘Apple’(company vs. fruit)

- ‘bit’(unit of data vs. act of eating)

(20)

20

3.2 질의 절차

단일 단어 질의

가장 간단한 질의: 한 단어.

텍스트 문서: 긴 단어 열.

검색어를 가진 가장 적합한 문서들을 우선순위로 제시.

순위화

검색 결과가 많을 때 우선 순위 필요.

워드 프로세서와 차이점.

용어 빈도수 tf, 역문헌 빈도수 idf로 측정

(21)

21

3.2 질의 절차

다 단어 질의

문서를 정확하게 검색하기 위하여 단일 단어 대신 복수 단어 또는 문맥(근접한 다른 단어)으로 검색.

구 phrase

두 개 이상의 단어를 포함하는 질의 근접도 proximity

구 질의를 완화하여 단어 사이에 허용되는 거리를 인정하는 질의.

(22)

22

3.2 질의 절차

3.2.2 불리언 질의 Boolean Query 키워드 질의의 결합 도구

구문 트리 작성

OR: query( e₁ OR e₂). e₁ 또는 e₂를 만족시키는 모든 문서 AND: query( e₁ AND e₂). e₁와 e₂ 를 모두 만족시키는 모든 문

서

BUT: query( e₁ BUT e₂). e₁을 만족시키지만 e₂를 만족시키지 않는 모든 문서

e₁, e₂: 불리언 식

(23)

23

3.2 질의 절차

3.2.2 불리언 질의 Boolean Query

불리언 질의식의 구문 트리

system

OR

AND

information retireval

model

BUT

(24)

24

3.2 질의 절차

3.2.3 내용기반 질의 Content-Base Query Def.

질의를 분석하여 얻은 특징 정보를 이용하여 유사한 정보를 검색하는 기술.

배경:

대용량 멀티미디어 사용 증가.

핵심 기술:

자료에서 효과적으로 특징을 추출하는 것.

특징 정보:

문자 문서: 단어 조합, 오디오 파일: 주파수, 영상 파일: 색상, 질감

(25)

25

3.2 질의 절차

3.2.3 내용기반 질의 검색 절차

(26)

26

3.2 질의 절차

3.2.3 내용기반 질의 Content-Base Query Query by Example

 Input an example image or better yet set of images (typically selected)

 Model the desired color, texture or shape (selected or created)

Text Associated with Images

 Metadata

 Ontologies and Classification Schemes

 Keyword search on associated texts

(27)

27

3.2 질의 절차

3.2.4 Ranking Query

- 키워드를 단순히 나열하는 형태

- 질의와 레코드 간의 유사도를 평가하여 레코드에 순위를 부 여

- 초기 인터넷 엔진은 ranking query를 많이 사용했으나 최근 에는 boolean query를 병행 지원

(28)

28

3.2 질의 절차

3.2.5 개념기반 질의 Concept-Based Query

접근 방식

각 단어마다 의미하는 개념을 결정.

한 개 이상의 온톨로지ontology를 사용.

- 개념들 사이의 관계를 표현하는 계층 구조 - e.g. ISA 관계

특정 분야의 용어를 표준화하는데 사용 가능 온톨로지는 복수 언어를 연결 가능

시맨틱 웹Semantic Web의 기반 불리언 질의 모델의 문제점.

(29)

29

3.2 질의 절차 3.2.5

^{개념 기반 질의}

키워드 검색의 문제점: 개념 파악, 동의어, 애매성.

시소러스 구성도 시소러스 실례

동의어

용어

반의어

협의어 광의어

협의 반의어

광의 반의어

노무자 피고용자

노동자

고용자 사용자

기능공 작업부 근로자

사장 경영자 책임자 관리자

3.2 질의 절차 3.2.5

개념 기반 질의 절차

순서 처리 내역 비 고

1 개념 분석 질의를 개념 집단 또는 작은 개념(용어)으로 분해

2 개념 적용 식별된 용어(개념)의 동의어, 광의어, 협의어를 고려

3 용어 변환 통제 어휘가 있으면 용어들을 통제어휘로 변환

4 연산 실행 동의어는 OR, 관련된 용어는 AND, 불필요한 용어는 NOT 연산자로 제거

(31)

31

3.2 질의 절차 3.2.5

개념 기반 질의 절차

검색 요구: ‘Smart phone’의 사회적인 ‘Issue’를 검색하되

‘information technology’에 관한 내용을 제외한다.

1) 개념 분석

개념 1 개념 2 개념 3

smart phone issue information technology

(32)

32

3.2 질의 절차 3.2.5

개념 기반 질의 절차 2) 3) 개념 적용과 변환

개념 1 개념 2 개념 3

smart phone issue information technology telephone

mobile phone PDA phone cellular phone

feature phone

controversy problem

subject

computer technology internet technology network technology

(33)

33

3.2 질의 절차 3.2.5

4) 연산 실행

1. 동일 개념 집단의 용어에는 OR 연산자를 적용한다.

2. 질의 요구에 있는 모든 개념에는 AND 연산자를 적용한다 .

3. 제거시키기 위한 개념은 NOT 연산자를 적용한다.

불리언 연산자 구성

Smart phone issue information technology OR AND OR NOT OR

other terms other terms other terms 개념1 개념2 개념3

(34)

34

3.3 관련성 Relevance

용어의 출현수

freq_i,j: 문헌 d_j에 있는 용어 t_i의 출현수 용어 정규화 빈도수

문헌 d_j에서 용어 t_i의 정규화 빈도수.

max: 문서 d_j 안에서 가장 빈도수가 큰 용어의 출현수.

n_i: 총 문서 수 N 중에서 용어 t_i가 출현한 문서의 수.

동기: 용어가 문서의 내용을 얼마나 잘 표현하는가의 척도.

] [freq f max

j l, l

j i,

j

freqi,

=

(37)

37

3.3 관련성 Relevance

용어 빈도수 tf: term frequency

용어 t가 문서 d에 나오는 빈도수. …… 비율

문서 d에 나오는 용어 t의 수를 d에 있는 전체 용어의 수로 나 눈 값.

n(d,t): 문서 d에 나오는 용어 t의 출현수.

n(d): 문서 d에 있는 전체 용어의 수.

용어 빈도수 tf가 높다고 관련성이 높은 것은 아니다.

) ) (

) , 1 (

log(

) ,

( n d

t d t n

d

tf = +

(38)

38

3.3 관련성 Relevance

역문헌 빈도수 idf : inverse document frequency 용어 t를 포함하는 문서들의 수의 역수.

n(t_i): 전체 문서 N 개 중에서 용어 t_i를 포함하는 문서의 수 = n_i. idf가 높을수록 관련성이 높다.

동기 : 많은 문서에 출현한 용어는 관련성이 적다.

) ( ) 1

( t n t

idf =

(39)

39

3.3 관련성 Relevance

tf-idf : 용어 역문헌 빈도수: 용어 가중치 할당 전략 용어 빈도수와 역문헌 빈도수의 곱.

질의 Q와 문서 d의 관련성 tf-idf:

n(t_i): 문서 N 개 중에서 용어 t_i를 포함하는 문서들의 수 = n_i. idf가 높을수록 관련성이 높다.

∑

∈

=

Q t

t idf t

d tf Q

d

r( , ) ( , )* ( ) )

(

)) ( / ) , ( 1

) log(

( n t

d n t

d t n

idf

tf − = +

(40)

40

3.3 관련성 Relevance

용어 가중치 W : weight

문서 전체의 수를 용어 t를 가진 문서의 수로 나눈 값의 로그.

// 전체 문서에서 용어 t_i를 가진 문서의 비중

용어 빈도수*가중치

// 용어 빈도수 * 용어 가중치

문서 안에서 비중 * 전체 문서에서 비중

df_i: 용어 i를 가진 문서의 수

W_i,j : 문서 j 의 용어 i의 가중치

) log(

dfi

W = N

) log(

*

, ,

i j

i df

tf N

W =

(41)

41

3.3 관련성 Relevance

질의 Q 에 대한 문서 d 의 관련성(가중치 반영):

∑

∈

=

Q

t df

t N idf t

d tf Q

d

r( , ) ( , )* ( )*log( )

(42)

42

3.3 관련성 Relevance

예제 5-A: 질의 연산 연습

문서 J의 전체 용어의 수 : n(j) = 400

용어 A, B, C의 출현수 f_{req A,j} = 50, f_{req B,j} = 40, f_{req C,j} = 20 용어가 포함된 문서의 수 df_A = 100, df_B= 80, df_c= 20 전체 문서의 수 N = 1,000

1) 세 용어 A, B, C의 용어 정규화 빈도수 f_A,j , f_B,j , f_C,j ?

2) 세 용어 A, B, C의 용어 빈도수 tf_A,j = log(1+ n(d,t)/n(d)) ? 3) 세 용어 A, B, C의 역문헌 빈도수 idf(t) = 1/n(t) ?

4) 세 용어 A, B, C의 가중치 W_,j = log(N/df_i) ? 5) 용어들의 관련성 R(d,q) = tf*idf*weight ?

(43)

43

3.3 관련성 Relevance

유사도 종류 Dot product Cosine

Dice

Jaccard

∑ ∑ ∑

∑

∑ ∑

∑

∑ ∑

∑

−

= +

=

i i i

i

i i

i

i i

i

i i

b a b

a

b a Q

D Sim

b a

b a Q

D Sim

b a

b a Q

D Sim

b a Q

D Sim

)

* ( )

, (

)

* ( 2 )

, (

* )

* ( )

, (

)

* ( )

, (

2 2

t1

t2 D

Q

(44)

44

3.3 관련성 Relevance

유사도 관련 용어의 정리

용 어 내 역

용어 출현수 문서에서 특정 용어가 나타난 횟수

용어 정규화 빈도수 문서에서 특정 용어의 수와 문서의 최대 용어 수의 비율

용어 빈도수 문서에서 특정 용어의 수와 문서의 전체 용어 수의 비율

역 문헌 빈도수 특정 용어가 나타난 문서 수의 역수 용어-역 문헌 빈도수 용어 빈도수와 역 문헌빈도수를 곱한 값

역 문헌 빈도수 질의 유사도 역 문헌 빈도수를 이용한 질의와 문서와의 유사도

용어 가중치 전체 문서 수와 특정 용어를 가진 문서 수의 비율 용어 빈도수 가중치 용어 빈도수와 가중치를 곱한 값

가중치 질의 유사도 역 문헌 빈도수와 가중치를 이용한 문서와의 유사도

(45)

45

3.3 관련성 Relevance

3.3.2 연관 환류 Relevance Feedback

질의 결과로 얻어진 문서들을 대상으로 질의를 재작성하여 더 관련성이 많은 문서들을 얻는 검색 방식.

연관 환류를 반복함으로써 검색 결과를 개선.

1) 사용자 관련 환류

사용자가 선택적으로 환류 시행 2) 지역 환류

검색 결과 안에서 환류 3) 전역 환류

모든 문서 집합을 대상으로 환류

(46)

46

3.3 관련성 Relevance

질의 재작성 기술 - 질의 확장

- 질의 용어 가중치 부여

장 점

- 질의 재작성 과정의 세부 내용이 사용자에게 숨겨진다.

- 전체 검색 과정을 작은 단계로 나누어 처리한다.

- 관련 용어는 강조하고 비관련 용어는 강조하지 않는다.

(47)

47

3.3 관련성 Relevance

사용자 관련 환류 절차

(48)

48

3.4 요점 정리

질의: DB에서 원하는 정보를 요구하는 문장(들).

연산: 원소들을 조작하여 새로운 원소를 만드는 절차.

질의 연산: 질의와 문서 집합의 유사도를 비교하여 검색하는 절 차.

질의의 목적: 관련된 문서의 검색 결과를 증대하는 것.

질의의 종류: 검색, 탐색, 둘러보기

질의의 문제점: 검색 결과 관련 문서 수가 적다. 질의 작성 시간 소요.

질의 문제점 대책: 초기 질의 활용. 질의 재 작성(질의 확장,가중 치 활용)

질의 절차: 문서 검색 자료 검색

(49)

49

3.4 요점 정리

질의 형태: Pulling, Pushing

질의 절차: 키워드 질의, 내용기반 질의, 불리언 질의, 랭킹 질 의, 개념기반 질의

키워드 질의: 문서의 핵심 단어를 색인으로 이용하는 질의

내용기반 질의: 문서 내용의 유사성(특징)을 기반으로 하는 질 의

불리언 질의: 질의 조건으로 불리언 식을 이용하는 질의

랭킹 질의: 정확도를 기준으로 검색 결과에 순위를 부여하는 질의.

개념기반 질의: 질의의 개념에 맞는 문서를 검색하는 질의.

개념기반 질의 절차: 개념분석 개념 적용 용어 변환 연산 실

(50)

50

3.4 요점 정리

관련성: 질의와 문서의 유사도를 나타내는 기준

유사도: 질의와 문서가 키워드를 기준으로 비슷한 정도를 나 타내는 수치.

용어 출현수: 문서에서 어떤 용어가 나타난 횟수

용어 정규화 빈도수: 문서에서 어떤 용어 수와 최대 용어 수의 비율

용어 빈도수: 문서에서 어떤 용어의 수와 전체 용어 수의 비 율

역문헌 빈도수: 특정 용어가 나타난 문서 수의 역수

용어-역문헌 빈도수: 용어 빈도수와 역문헌 빈도수의 곱

용어 가중치: 전체 문서의 수와 특정 용어를 가진 문서 수의

(51)

51

3.4 요점 정리

관련 환류 relevance feedback: 검색 결과를 대상으로 재 질의하 여 더 관련성이 많은 결과를 얻으려는 검색 기술

환류의 종류: 사용자 환류, 지역 환류, 전역 환류

(52)

52

기타

1.

2.

∑ ∑

∑

=

i i

i

i i

b a

Q D Sim

b a

Q D Sim

2 2 *

)

* ( )

, (

)

* ( )

, (

∑ ∑ ∑

∑

∑ ∑

∑

−

= +

i i i

i

i i

i

i i

b a b

a

b a Q

D Sim

b a

b a Q

D Sim

)

* ( )

, (

)

* ( 2 )

, (

2 2