제12장 정보 검색 - Information Retrieval -

(1)

제12장 정보 검색 - Information Retrieval -

2009. 08. 10

경원대학교 IT대학 전자거래학과

(2)

12.1 개요

12.2 연관성 순위 12.3 시맨틱 웹 12.4 검색 모델 12.5 성능 평가 12.6 웹 검색 엔진

12.7 익힘 문제

(3)

3 12.1 개요

Why 정보 검색 ?

비구조적 텍스트에 대한 질의.

비구조적 자료: Multimedia text, audio, image, video,,,

자료의 양이 기하급수적으로 증가  검색 곤란 문서: 도서관, 뉴스 기사, 재판 자료.

키워드 검색.  키워드 색인화 Web:

정보는 많으나 검색 도구가 ?

(4)

4 1.1 개요

[표 12.1) ] 검색 시스템의 종류

세대 검색 시스템 지원 체제 검색 대상 검색 수단

1 도서 카드 시스템 종이 카드 서적, 논문, 제목, 저자, 출판사, 2 키워드 검색 시스템 컴퓨터 문서 색인 미리 선정된 키워드 3 전문 검색 시스템 컴퓨터 문서 전체 문서의 모든 용어 4 웹 검색 시스템 인터넷 문서 전체 웹 서버 전체 용어

(5)

5 12.1 개요

기존 Database

복잡한 자료, 조직화된 자료, 정형화한 자료,,,….DBMS 정보 검색

간단한 자료, 비구조적, and, or, not,,, 전문검색full-text search:

문서의 모든 단어들이 keyword  색인 결과가 많으면 순위화 필요

용어 term

문서 내의 자료

(6)

6 12.1 개요

데이터 검색 Data Retrieval

- 구조적 자료 기반: 명확한 정의와 조건 - exact match: key search

- DBMS: 갱신, 병행제어, 트랜잭션,, 정보 검색 Information Retrieval

- 비구조적 텍스트의 키워드기반  내용기반 - 유사도 검색: no exact match  우선순위 검색 - 문서의 분석 및 분류

공통점

- 디스크에 자료 저장 및 검색

(7)

7 1.1 개요

[표 12.2) ] 자료 검색과 정보 검색의 비교

구 분 자료 검색 정보 검색

대상 자료 구조적 자료(속성 자료) 비구조적 자료(텍스 트)

목적 시스

템 데이터베이스 시스템 정보 검색 시스템 검색 형태 정확한 일치 유사도 검색

검색 목표 키워드가 있는 문서 검 색

주제와 관련된 문서 검색

주요 비중 갱신, 병행제어, 무결

성,, 키워드, 유사도

(8)

8

12.2 연관성 순위 전문검색의 문제점

원하는 문서를 검색해야,, 문서가 너무 많아서 대책: 용어와 연관성이 많은 문서를 검색해야 용어 빈도수 tf(d,t) : term frequency

용어 t가 문서 d에 나오는 빈도수

연관성이란? 빈도수가 높다고 연관성이 많은가?

tf(d,t) = log(1 + n(d,t)/n(d))

n(d,t): 문서 d에서 용어 t의 빈도수, n(d) : 문서 d내의 전체 용어의 수.

(9)

9 12.2 연관성 순위

idf Inverse document frequency : 역문서 빈도수

여러 용어로 검색 시 중요도를 적용해야

idf(t) = 1/n(t)

n(t) : 용어 t를 포함하는 문서의 수

tf-idf : 질의 Q에 대한 문서 d의 연관성

용어 빈도수 tf(d,t)와 역문서 빈도수 idf(t)의 함수 tf-idf(d,t) = tf(d,t) * idf(t)

=

log(1 + n(d,t)/n(d)) * 1/n(t) tf-idf(d,t) : 용어 t의 문서 d에 대한 연관성

(10)

10

12.2 연관성 순위

r(d,Q) : 용어 집합 Q에 대한 문서 d의 연관성

r(d,Q) =

r: 질의 Q에 대한 문서 d의 연관성

사용자 지정 가중치 User Weight : tf * w(d, t)

용어 빈도수 tf(d,t)와 역문서 빈도수 idf(t)의 함수 uw(d,t) = tf(d,t) * w(d,t)

w(d,t) : log(N/df(t)) 문서 d의 용어 t의 가중치

N: 모든 문서의 수, df(t) : 용어 t를 가진 문서의 수.

∑

t

∈Q

t idf t

d

tf ( , ) * ( )

(11)

11 12.2 연관성 순위

불용어 stop word.

a, the, if, then, and, or, 약 100 개 정도

용어 근접도 proximity

용어들이 가까운 위치에 있어야 의미,,,

연관성 피드백 relevance feedback 결과 내 재 검색

(12)

12 12.2 연관성 순위

문서 전처리 작업.

순

서 전처리 작업 내 역 비 고

1 어휘 분석 특수 문자 식별 !, &, *, +, -, / 외 2 불용어 제거 의미 없는 단어 제거 a, the, this, which 외 3 어간 추출 접두사, 접미사 제거 encapsulated

4 (용어)색인어

선정 용어 정리 및 선별 capsule

5 시소러스 동의어, 동음이의어, 반

대어 외 재규어?, 테이블?

(13)

13 12.3.1 시맨틱 웹 개요

키워드

검색 시 동의어, 동음이의어 활용 차량 정비: 자동차 수리?

테이블: 가구? 자료?, 재규어: 짐승? 자동차?

단어의 의미를 명확히 하기 위해 문서들을 분석하고, 개념을 정리

문맥에 따라 결정  개념기반 질의 장점:

개념이 있으면, 다른 언어로도 질의 가능

계층 구조화: 내포와 외연으로 범위 축소 및 확장

(14)

14 12.3.2 온톨로지

Ontology

어원: 존재의 본질과 유형에 관한 이론 일종의 사전.

단어의 개념들 간의 관계를 반영하는 계층 구조.

ex. 사자? 호랑이?  고양이  포유류  동물

IS-A 관계, PART-OF 관계, Member-of 관계, Instance-of 관계 구조:

단어 계층, 추론 규칙, 시맨틱 웹의 중심 개념

(15)

15

12.3.2

온톨로지

정의: 공유된 개념과 이들의 관계를 명확하게 정형화한 명 세.

목적: 정보를 기반으로 지식 생성. 추론 기반 제공

용어 내 역 비 고

공유 정보의 의미를 합의하여 공통적으로 사

용 공용성

개념화 사물의 공통점을 집합으로 묶고 분류 분류 명확성 개념들의 종류, 관계, 제약조건을 정의 정확성 정형화 기계가 정보를 읽을 수 있는 형식 정의 형식화 명세화 개념의 내용을 상세하게 기술 상세한 기술

(16)

16 12.3.3 RDF

RDF resource description framework 온톨로지를 만드는 수단.

정의:정보 자원의 특성과 값을 명세함으로써 자원 간의 상호 관계성을 기술하는 모델

: 자원을 (주체, 술어, 개체)의 3요소로 정의

Http://www.kwu.ac.kr/computer/database.xml

홍길동

Author

구조(자료)/주체

특성/술어

값/객체

(17)

17 12.3.3 RDF

RDF 구조

구성 요

소 내 역

실 례 1 일반 온톨로지

실 례 2 - 웹 온톨로지 -

구조 structure

주체 subject

데이터베이

스 www.kwu.ac.kr/computer/database.xml 특성

property

술어

predicate 저자 dblab.kyungwon.ac.kr/1.2/author 값

value

객체

object 홍길동 dblab.org/cs/professor/58603 * Hong, kil-dong

RDF는 정보 자원의 특성과 값을 명세함으로써 자원 간의 상호 관계를 기술하는 모델이다.

(18)

18 12.3.3 RDF와 온톨로지

RDF schema:

정보자원의 특성과 다른 자원과의 관계 정의

* RDF는 기존 meta-data에 대한 정보만 표현하기 때문

온톨로지 구축과정

순서 단계별 작업 내 역

1 설계 온톨로지 구축 목적을 명세 2 개념화 주제 영역의 핵심 개념 정리 3 범주화 주제 영역의 단어들을 분류

4 정의 생성 주제 영역에서 기본적인 단어들을 정 의

5 기호화 온톨로지 표현 언어로 기호 생성

(19)

19

12.3.3 온톨로지

관계성

IS-A 관계: 일반화, 특수화

PART-OF 관계: 부품이 모두 모여야,,,

Member-of 관계: 객체를 이루고 있는 여러 객체 중의 하나 Instance-of 관계: 객체를 이루고 있는 여러 사례 중의 하나

Publication

Title Author

Publication

Journal Book Paper

콘크리트물

콘도로 콘하수도 콘댐

동물

사자 원숭이 호랑이

Text

(20)

20 12.3.4 시맨틱 웹

Semantic Web

단어의 개념, 유사성, 상관관계 등의 의미를 파악하여 결과물 을 생성하여 제공하는 웹.

자료의 개념, 유사성, 상관관계 등의 의미를 파악하여 결과물 을 생성하여 제공하는 웹.

접근 방식

1. RDF record description framework기반의 온톨로지 기술 자원을 기술하는 언어인 메타-자료에 정보를 이해하고 처

리

2. ISO의 Topic Map기술: XML 기반의 XTM 언어 지식층과 정보층의 2중 구조

(21)

21 12.3.4 시맨틱 웹

Semantic Web의 구조 주요 요소

1) 자원 서술 XML, RDF 2) 지식 서술 온톨로지 3) 통합 운용

agent: 정보자원을 수집, 검색, 추론하고 온톨로지를 이용 하여 다른 agent와 교환하는 지능형 프로그램.

(22)

22 12.3.4 시맨틱 웹

기존 웹과 Semantic Web

(23)

23 12.3.4 시맨틱 웹

기존 웹과 Semantic Web

^{구 분} ^{시맨틱 웹} ^{월드 와이드 웹}

제 안 1999, Tim Berners-Lee 1989, Tim Berners-Lee

2004 Dale Dougherty (web 2.0)

검색 주체 기계(프로그램) 인간

자료 연결 의미적, 형식적 비형식적

검색 기능 의미적 연결 관계와 추론 검

색 단어 수준의 검색

키워드 오류

시 의미적 추론으로 검색 검색 불가 연관정보 키워드의 의미와 연관 정보

부재 관계에 의한 연관 정보 브라우징

주요 기술 온톨로지, RDF Folksonomy, Wiki, Ajax, RSS 주요 기능 기술 중심(지능형 에이전트) 사용자 중심(개방, 공개, 참여)

(24)

24 12.3.4 시맨틱 웹

Semantic Web의 미래

고급 웹: 다양한 도메인의 지식 처리  종합적 의사결정 지 원.

(25)

25 12.3.4 시맨틱 웹

Semantic Web의 미래 Semantic web의 현재 발전 속도: slow

복잡도: too complex 표준화: not easy

해결할 문제점

1) 기반 기술: RDF, OIL, DAML,,, 부족 2) 언어 관계: not easy

3) 표준화: not easy

(26)

26 12.3.4 시맨틱 웹

지식 검색

정보를 수집하고 분석하여 사용자가 원하는 형태의 지식으 로 가공하여 제공하는 작업.

전제:

사용자가 원하는 정보와 지식을 기계가 인식할 수 있는 객관 적인 표현방법 필요.

핵심 기술

1) 지능형 검색: 검색 모델 개발

2) 지식 브로커: 일관된 접근 방식과 통일된 관리 방식 3) 자동분류: 의미적으로 유사한 결과를 범주화

(27)

27

검색 모델은 용어를 매개로 질의와 문서가 얼마나 관련되는 지를 결정하는 도구.

12.4.1 불리언 모델 1) OR 연산자:

2) AND 연산자:

3) NOT 연산자:

(curve and query) = 12, 125

(curve or query) = 11, 12, 25, 34, 36, 56, 76, 77, 125, 334 (curve and not query) = 25, 36, 77, 334

(28)

28

12.4.2 벡터 공간 모델:

가정: 문서와 질의를 표현하는 색인 용어들의 집합은 고정.

문서 D

_i

와 질의 Q

_j

의 표현

D

_i

= [T

_i1

, T

_i2

,…,T

_ik

,…, T

_im

] Q

_j

= [Q

_j1

, Q

_j2

,…,Q

_jk

,…, Q

_jn

]

T

_ik

: 문서 i의 용어 k,

Q

_jk

: 질의 j에서 용어 k의 가중치,

N: 문서와 질의에서 사용된 용어들의 전체 수.

용어 가중치 T

_ik

와 Q

_jk

는 이진수이거나 tf.idf이거나 다른 의미에서 얻어진 가중치.

(29)

29

문서 D

_i

와 Q

_j

의 유사도:

S(D

_i

, Q

_j

) = Σ

_k=1,N

T

_ik

· Q

_jk

D

₁

= [0.2, 0.1, 0.4, 0.5]

D

₂

= [0.5, 0.6, 0.3, 0] Q = [0.5, 0.5, 0, 0]

D

₃

= [0.4, 0.5, 0.8, 0.3]

D

₄

= [0.1, 0, 0.7, 0.8]

S(D

₁

,Q) = 0.1+0.05 = 0.15 S(D

₂

,Q) = 0.55

S(D

₃

,Q) = 0.45 S(D

₄

,Q) = 0.05

시스템은 D

₂

, D

₃

, D

₁

, D

₄

, 순서로 반환

(30)

30 12.4 검색 모델

문서의 유사성 기준 cosine similarity

t

₁

, t

₂

, … , t

_n

: 두 문서에 나타난 용어들.

r(d, Q) = tf(d,t) * idf(t)

두 문서 간의 유사도 S

S =

- Algebra 모델

- 문헌과 질의가 1차원 공간의 벡터로 표시 - 선형대수 연산자로 구성

∑ ∑

∑

= =

= n

i

n

i

i i

n

i

i i

t e r t

d r

t e r t d r

1 1

2 2

1

) , ( )

, (

)

,

(

)

,

(

(31)

31 Vector Space Model

방법

- 가중치를 실수로 - 유사도로 순위화 ex. Cosine 유사도

Q

d _j

θ

system

retrieval 4

10 10 5

<4,10>

<10,10>

θ

<7,10>

Θ’

(32)

32 Vector Space Model

실례

T

₁

: retrieval T

₂

: information T

₃

2

= 3T

1

+ 7T

2

+ T

3

1

2

(33)

33 12.4.3 내용기반 검색

[표 12.4) ] 내용기반 검색의 비교

구 분 키 기반 검색 내용기반 검색 비 고

함수 관

계 y = f(x) x = f^-1(y) x: key, y: content 파일 형

식 file inverted file

색 인 키를 저장하는 색인 내용을 저장하는 색인

목표: 상세한 내용(레코드, 문서)

응용 분

야 데이터베이스 분야 멀티미디어 검색 키로 검색, 내용으로 검색 실 례

key(학번) --> 성명 key(곡명) --> 노래 제목

성명 --> 학번 곡조 --> 음악

기본 키(키 필드 기반), 보조 키(내용기반)

(34)

34 12.4.3 내용기반 검색

Inverted File

내용  key  자세한 내용 기존 파일: key  내용 Inverted file의 실례

용어1: 레코드1, 레코드3 용어2: 레코드1, 레코드2

용어3: 레코드2, 레코드3, 레코드4

용어4: 레코드1, 레코드2, 레코드3, 레코드4

용어i: 색인 용어i의 ID 번호, 레코드i: 레코드i나 문서i의 ID 번호.

Query: (용어1 AND 용어3), (용어1 OR 용어3)

(용어4 AND NOT 용어1), (용어1 AND NOT 용어4)

(35)

35

12.4.2 내용기반 검색

Inverted File

y = f(x) : x = key

x = f

^-1

(y) : y = content

ANSI {D1, D22}

CASE {D4, D7, D55}

Media {D1, D7}

Oracle {D14}

Term Documents

Sybase {D2, D10}

Informix {D3, D22}

Sun {D10, D55}

HP {D14}

D1 D2 D3

D7 D10 D14 D22

D55 D4

Inverted Index

Prime data file

(36)

36

Inverted file 연산의 확장

- 단어/용어의 근접성, ‘object’ WHITIN(or BEFORE or AFTER) 1 - 단어/용어가 N 문장 내, “database’ WHTHIN 1 SENTENCE

ex. (용어i within sentence 용어j) 용어i와 j가 같은 문장에 있슴.

(용어i adjacent 용어j)

(‘database’ within sentence ‘media’)

이를 위해 다음의 정보가 요구된다.

용어i: 레코드 번호, 문단번호, 문장번호, 단어번호.

ex. database: R99,10,8,3;R155,15,3,6;R166,2,3,1 media: R77,9,7,2;R99,10,8,4;R166,10,2,5

R99의 10번 문단 8번 문장에 두 단어가 같이 있음을 알 수 있다.

(37)

37 12.4.2 내용기반 검색

역 파일 inverted file, inverted index

신속한 검색을 위해 내용으로 자료를 찾는 색인 y = f(x). x = f

^-1

(y)

구 조



Data 레코드가 하나의 텍스트 필드로 구성되었다고 가정.



구성 요소

1.

Index file: dictionary or collection

2.

Posting file

3.

이순신 장군은 정보 검색과 엔진에 관한 관심이 많았다.

을지문덕 장군도 검색에 관한 관심이 많았다.

Doc#3 :

징기스칸은 정보에 관한 관심이

누구보다도 많았다.

DF: document frequency Doc#: document number

Wgt: documents weight Doc#6 :

Doc#7 :

DF LINK

(39)

39 12.5 검색 성능 평가

성능 평가

조회율 Recall: 검색된 관련문서의 수/전체 관련 문서의 수 정확도 Precision: 검색된 관련 문서의 수/검색된 문서의 수 모두 좋으면 좋으나, 반비례 관계

Collection

연관정보 .

|R|

결과집합

|R _a |

|R| : 연관정보

|R _a | : 결과집합의 연관정보

|A|: 결과집합

Recall = |A|/|R|

Precision = |A|/|R _a |

|A|

(40)

40 12.5 검색 성능 평가

Index:

공간 절약을 위한 간결한 구조  정확도 저 하

False drop, false negative: 곤란 False positive: 일부 허용

precision

recall 1

1 (0,0)

(41)

41 12.5 검색 성능 평가

조회율과 정확도의 비교 ^검색된

문서의 수

조회율 정확도 비 고

1 1/6 0.17

1/1

1.0 조회율: 낮음, 정확도: 높음 2 2/6 0.33

2/2

1.0

3 2/6 0.33

2/3

0.67 4 2/6 0.33

2/4

0.5 5 3/6 0.5

3/5

0.6

6 4/6 0.67

4/6

0.67 조회율 = 보통 = 정확도 7 4/6 0.67

4/7

0.57

8 4/6 0.67

4/8

0.5 9 5/6 0.83

5/9

0.55

10 5/6 0.83

5/10

0.5 조회율: 높음, 정확도: 낮음

(42)

42 12.6 웹 검색 엔진

검색 엔진의 구조

(43)

43 12.6 웹 검색 엔진

검색 엔진의 주요 기능 _순

서 기 능 주요 처리 내역 프로그

램

1 자료 수집 웹 사이트에서 정보를 수집하여 검색 사이트로

전송 crawler

2 용어 추출 웹 로봇이 보내주는 정보에서 용어를 추출하고

정리 indexer

3 용어 저장 추출된 용어를 색인 데이터베이스에 저장

4 사용자 검색 사용자 질의를 데이터베이스 질의로 변환하고

실행 searcher

5 순위 알고리

즘 원하는 정보와 가장 유사한 순서대로 정렬

(44)

44 12.6 웹 검색 엔진

검색 엔진의 3요소

검색기, 색인기, crawler(로봇)

Crawler: 웹 상의 정보를 찾아 수집하는 프로그램 검색 결과를 Depository에 저장

Indexer: 간략한 정보와 주소를 색인 DB에 저장.

정보를 추출하는 기능 + 정보를 색인화하는 기능 Searcher:

사용자의 질의를 받아서 색인 DB를 검색.

검색 결과에 순위를 부여하여 제시.

(45)

45

Typical Web Search Engine Structure

(46)

46

Web Search Engine

Core program - transfers keywords into database query - ranks the results into a list

정보검색처리

Internet

질의 인터페이스 응답 인터페이스

Internet

검색 사이트 Web Search Engine

Query Generator

키워드, 단어, 주제 결과 Storage

DB Query

Web Page Title Ranking

HTML Generator Data Level

Process Level

UI Level

Client Server 정보수집

처리

Index

(47)

47 12.6 웹 검색 엔진

Web search engine

초기: tf-idf 기반의 유사도 측정  방대한 웹에서 한계

현재: 키워드 포함 문서에서 인기 있는 문서들을 높게 순위 부 여.

ex. Google의 Pagerank

reference feedback: 검색된 자료 중에서 재 검색 엔진 형태

- directory 서비스: 주제별 검색, 분류 중심, Yahoo - keyword 검색: 단어별 검색, Altavista

- 메타 검색 엔진: Savvy - 지식검색: Google, Naver

(48)

48 12.6 웹 검색 엔진

Web search engine의 역사

검색 엔진 세대 엔진 특징 대표적 실례

1 세대 엔진 디렉토리 검색 Yahoo,Lycos, ,Einet Galaxy

2 세대 엔진 키워드 + 로봇 검색 Altavista, HotBot, Excite 2.5 세대 엔진 디렉토리 + 로봇 검색 네이버, 다음, 엠파스, 파란

3 세대 엔진 Page Ranking 기법 Google

4 세대 엔진 지식 검색(시맨틱 웹) Hakia, searchme, Qrobo

50

(50)

50 12.7 익힘 문제

1. 전문검색을 수행하는 방식을 설명하시오.

2. 자료검색과 정보검색의 차이를 설명하시오.

3. 정보검색과 지식검색의 차이를 설명하시오.

4. 멀티미디어검색과 정보검색의 차이를 설명하시오.

5. 검색 모델이란?

6. 검색 모델에서 연관성은 어떻게 계산하는가?

7. 용어 빈도수의 역할을 설명하시오.

8. 역문헌 빈도수의 역할을 설명하시오.

9. tf-idf의 역할을 설명하시오.

10. 사용자 가중치의 역할을 설명하시오.

(51)

51 12.7 익힘 문제

11. tf-idf를 설명하시오.

12. 개념기반 질의는 왜 필요한가?

13. 벡터공간모델은 어느 검색에 유용한가?

14. 웹 서치 엔진의 형태와 발전과정을 기술하시오.

15. 웹 서치 엔진의 구조를 설명하시오.

16. 개념기반 질의는 왜 필요한가?

17. XML과 온톨로지의 관계를 설명하시오.

18. XML과 RDF의 관계를 설명하시오.

19. 시맨틱 웹이란?

20. 시맨틱 웹을 구현하는 수단은?

(52)

52 12.8 익힘 문제

21. 다음은 문서들과 질의의 행렬식이다. 유사성을 계산하시오.

D1 = [1, 2, 3, 1]

D2 = [0, 2, 1, 0]

D3 = [1, 1, 1, 0]

D4 = [1, 1, 0, 2]

Q = [1, 2, 1, 0]

22. 키 기반 검색과 내용기반 검색의 차이를 설명하시오.

23. 역 파일을 사용하는 이유는 무엇인가? 용도는?

24. 조회율과 정확도의 관계를 설명하시오.

25. 벡터공간모델은 어느 검색에 유용한가?

26. 웹 서치 엔진의 형태와 발전과정을 기술하시오.

27. 웹 서치 엔진의 구조를 설명하시오.