Information Retrieval

2 Introduction Information Retrieval –automatic indexing + document retrieval Web Information Retrieval – 전통적인 IR 과 유사한 방법 / 방식 –, but 대상 문서의 환경 변화에 따른 특징 비정형화되고 비구조화된 문서 문서 내용의 변화 빈도가 높음 문서의 양이 매우 많음 도메인 ( 영역 ) 의 한계가 없음

3 Web IR 흐름도 Web Connection Web Page Load HTML Tag Remove Lexical Analysis Stopping Stemming Term Retrieval Term Weighting DB Indexing Keyword/URL

4 Web Connection CHttpFile –provides the functionality to request and read files on an HTTP server. –CFile>CStdioFile> CInternetFile>CHttpFile CHttpConnection –manages your connection to an HTTP server. –CInternetConnection CInternetSession –to create and initialize a single or several simultaneous Internet sessions To communicate with an HTTP server, you must first create an instance of CInternetSession, and then create a CHttpConnection object.

5 Web Page 수집 Web Robot & Web Agent – 초기 URL 을 시작으로 연속적인 탐색 검색엔진의 결과 (meta-search) 이용 – 관련 keyword 에 의해 시작 –altavista 를 이용한 질의식 작성 " bin/query?pg=q&kl=en&q=snake&stq=0&c9k” –altavista 결과에 대한 내용 추출 관련 문서의 패턴을 조사 패턴에 따라 원하는 부분의 내용 추출 -> URL 수집 / 저장

6 HTML Tag Remove 문서의 내용과 관계없는 HTML 의 해석기호 제거 Tag –Web Page(HTML) 의 형식 결정자 – 문서의 인덱스로 부적합, but 문서 내용의 중요 정보 –“ ” 로 싸여진 태크의 제거 –script 언어로 쓰여진 부분 특수 기호 –HTML 에서 사용되는 기호를 표시 –ex) < > " & etc.

7 Lexical Analysis the stage of automatic indexing and query processing a word or token 의 분리 ( 생성 ) Consideration –Digits, Hyphens, Punctuation, Case Implementing –Using a finite automata (ex : Figure 7.2, 7.3, 7.4 ) Tip –lexical analysis 의 부분으로 제거 과정 (tag 제거, stopping, stemming) 을 처리

8 Stopping Index term 으로 가치가 없는 단어 제거 Stoplist 의 구축 – 색인 대상이나 사용자에 의존 –negative dictionary 도 일부 포함 Implementing –Lexical analysis 에 의해 token 생성 후 –stop list 와 비교 / 처리

9 Stemming Provide with ways of finding morphological variant of search terms for improving IR performance example – 단 / 복수, 파생어, 형 변환 등 education educational educator educators launch launched launches launching mail mailed mailer mailers mailing mailings

10 웹 문서 처리 - 예제

11 HTML source California Gray Whale Tutorial T he G ray W hale The gray whale is a mammal. Like all mammals, it bears live young, breathes air, is warm blooded, and nurses its young. The gray whale is in the scientific order Cetacea (from the Latin "cetus"), and in the sub-order Mysticeti (from Latin for mustache). All Mysticeti whales have baleen fringes inside their mouths rather than teeth, and they have two blowholes. Next | Contents | What is | Migration | Feeding | Whaling | Behavior | Calving | Home Page ] Definitions Warm blooded - maintains a constant internal temperature Mysticeti (\mis-ta- cets\) - The baleen whale Cetacean (\si-ta-shan\) - marine mammals that include whales, dolphins, and porpoises. Go to Top of Page Last Modified

12 HTML Tag 제거 California Gray Whale Tutorial The Gray Whale The gray whale is a mammal. Like all mammals, it bears live young, breathes air, is warm blooded, and nurses its young. The gray whale is in the scientific order Cetacea(from the Latin "cetus"), and in the sub-order Mysticeti (from Latin for mustache). All Mysticeti whales have baleen fringes inside their mouths rather than teeth, and they have two blowholes. Next Contents What is Migration Feeding Whaling Behavior Calving Home Page Definitions Warm blooded - maintains a constant internal temperature Mysticeti (\mis-ta-cets\) - The baleen whale Cetacean (\si-ta-shan\) - marine mammals that includewhales, dolphins, and porpoises. Go to Top of Page Last Modified

13 california gray whale tutorial the gray whale the gray whale is a mammal like all mammals it bears live young breathes air is warm blooded and nurses its young the gray whale is in the scientific order cetacea from the latin cetus and in the sub-order mysticeti from latin for mustache all mysticeti whales have baleen fringes inside their mouths rather than teeth and they have two blowholes next contents what is migration feeding whaling behavior calving home page definitions warm blooded maintains a constant internal temperature mysticeti the baleen whale cetacean marine mammals that include whales dolphins and porpoises go to top of page last modified Lexical Analysis

14 california gray whale tutorial gray whale gray whale mammal mammal bear young breathe air warm blood nurse young gray whale scientific order cetacea latin cetus sub-order mysticeti latin mustache mysticeti whale baleen fringe mouth teeth blowhole next content migration feed whal behavior calve definition warm blood maintain constant internal temperature mysticeti baleen whale cetacean marine mammal whale dolphin porpoise california gray whale tutorial gray whale gray whale mammal mammals bears young breathes air warm blooded nurses young gray whale scientific order cetacea latin cetus sub-order mysticeti latin mustache mysticeti whales baleen fringes mouths teeth blowholes next contents migration feeding whaling behavior calving definitions warm blooded maintains constant internal temperature mysticeti baleen whale cetacean marine mammals whales dolphins porpoises Stopping Stemming

15 whale(1.0), gray whale(0.887), mammal(0.833), blood(0.764), cetacea(0.667), bear(0.667), california gray(0.667), etc... whale(7), gray whale(4), mammal(3), young(2), blood(2), Cetacea(1), california gray(1), tutorial(1), bear(1), etc... TF Term Weighting whale(1.0), gray whale(0.887), mammal(0.833), blood(0.764), cetacea(0.667), bear(0.667), california gray(0.667) Tip.

16 Term Weighting 문서에 나타난 각 단어 ( 색인어 ) 의 중요도를 책정 Term Weighting of Term Frequency –TF & IDF –length of Document –maximum frequency of a index word SMART Weighting Schemes [salton] –Term weighting factor : TF, IDF, Normalization –Term-weighting component Term Frequency Component(TF) : Collection Frequency Component(DF) : Normalization Component :

17 DB indexing 웹 정보 검색 시스템 – 웹을 통해 모아진 정보를 색인 및 관리와 검색을 처리 웹 정보 검색 시스템의 주요 기능 –URL 수집, 색인 기능, 감시 기능, 검색 기능 웹 문서에서 특정 정보만을 추출하여 구축한 DB 정보의 검색과 제공에 사용, 역 색인 (inverted index) 구 조 사용 WebDB 구성 Table – 총 7 개로 Going Table, Gone Table, Page-list Table, Page- modification Table, Link Table, Keyword-list Table, Inverted- index Table 로 구성

18 DB - keyword-list table 지식베이스의 객체 정보 URL 로봇에 의해 접근 기존 검색엔진에 질의로 사용 Domain 의 결정에 따라

19 DB - going table 수집된 URL 저장 로 구성 URL 수집 방법에 따라 priority 부여

20 DB - gone table 이미 방문한 URL 저장 URL 방문의 효율성 – 방문 개시 전 – 새로운 URL 의 저장 Going/Gone table 의 필요 성

21 DB - page-list table 저장할 문서의 특징을 추출하여 저장 저장할 문서 정보 –URL, title, content, description

22 DB - page-modification table 웹 문서의 최종 수정 일 저장 -> 문서 변화 감지를 위해 변화 감지의 유연성 – 검사 횟수 – 문서 변화 횟수

23 DB - link table 웹 문서에 나타난 URL 링 크 저장 순위 결정의 한 방법 than 방문 목적의 링크 저장 문서 검색에서 – 링크 정보에 의한 문서 순 위 재조정 – 유사도 계산

24 DB - inverted-index table 문서에 나타난 단어 저장 검색에서 단어가 출연한 문서의 정합에서 사용 TF 식

25 DB’s 각 Table 설명 Going Table – 방문의 대상이 되는 URL 들을 의 쌍으로 저장 – 각 URL 마다 자신이 수집된 경위에 따라 순위를 가짐 ※ priority 에 의해 방문할 URL 의 순서를 정함 –URL 수집 방법 기존의 검색 엔진을 이용한 URL 수집 (priority=2) 방문한 문서에 나타난 URL 을 수집 (priority=3) 정보 변화에 의해 재 방문이 결정된 URL 수집 (priority=1) Gone Table – 한번 방문한 문서에 대해 한번 이상 같은 문서를 방문하지 않 기 위해 이미 방문한 URL 들을 저장

26 Cont’d(2) Page-list Table – 문서에 대한 정보로 문서의 여러 가지 특징을 추출하여 저장 – 저장되는 정보로는 문서의 URL 주소, 문서의 타이틀, 이 문서 의 대표하는 핵심어들, 이 문서의 요약문 Page-modification Table – 문서의 내용 변화를 감지하고 유연한 감시 기간을 제공 – 구성 문서의 최종 수정일 변화 여부를 검사하기 위해 남은 시간 변화가 되지 않은 횟수

27 Cont’d(3) Link table – 각 문서에 대해 문서가 참조하기 위해 링크하고 정보 – 문서의 URL 들과 그 앵커 이름 (anchor name) 을 저장 – 링크 정보는 웹 문서의 구조적인 특징으로 검색시 유용 정보 Keyword-list table – 특정 도메인에 나타나는 지식 정보의 저장 –URL 을 수집하기 위한 키워드로 사용 Inverted index table – 각각의 키워드에 문서 번호를 연계하고 그 단어의 문서상의 위치 정보와 Term weight 값을 함께 저장

28 웹 정보 검색 시스템 구조 Client Web 검색처리기색인처리기감시처리기 DB URL 수집기 문서정보 해당 URL URL 색인어 ( 들 ) 추출문서 질의관련문서 URL Web 문서 URL Header 정보 Search Engine

29 검색처리기 색인처리기 감시처리기 WebDB URL 수집기 Client User Interface Web URL Page information Retrieval Page query ranked page 웹 정보 검색 시스템

30 방문 모듈가공 모듈 평가 모듈 색인 모듈 Web 색인처리기 웹 정보검색 시스템 - 색인 처리기 Posting file & header 정보 WebDB URLWeb Page Posting file 적합성 평가값 특징 추출과 저장 Web Page

31 색인 처리기 - 가공 모듈 문서에 대해 정보의 가공을 담당 문서의 처리과정 형태소 분석과 Tagging 작업 Stopping Stemming Term Weighting posting file 의 구축 tf i = log w i + 1.0

32 감시 처리기 문서 내용 변화를 감지하여 최신의 정보를 제공 변화를 검사하는 기간의 유연성 제공 감시처리기의 처리과정 ① In Page-modification Table, 문서의 remainder-time 검사 ② remainder-time 값이 0 이 되는 문서의 변화 여부를 검사 ③해당 웹 문서의 헤더 정보로부터 수정 일을 가져온 후 WebDB 에 저장된 최종 수정일과 비교 ④만약 변화가 있다면 해당 웹 문서를 재 방문하기 위해 Going Table 에 등록하고 해당 문서 삭제 ⑤변화가 없다면 no-change-check-time 을 update(1 증가 ) ⑥변화된 no-change-check-time 이 5 이면, remainder-time 의 값 을 Default value 에 배수로 update( 검사기간의 유연성 제공 ) ⑦ remainder-time 에 Default value(3 일 ) 로 update

33 검색 처리기 User Retrieval Module WebDB Quer y - Query 와 matching 된 문 서 - and, or 처리 - 순위 처리된 결과 - P-norm model 이용 최종 결과 User Interface

34 문서 검색 인덱스 DB 를 이용한 웹 문서 제공 주어진 질의에 대해 정합과 순위 결정 순위 결정 – 관련 문서의 순위를 개선하여 향상된 정보의 제공 – 처리 과정 질의와 문서의 정합과정을 통해 관련 문서의 추출 추출된 문서들은 질의와의 유사도 계산 관련 문서들간의 링크 정보를 이용한 순위 재조정

35 예제

36 Extended Boolean Model Pure Boolean Model – 구현이 쉽고, 효율적 – 단순 불리언만 으로는 사용자 의도와 다른 결과 초래 – 문헌의 우선순위나 질의의 가중치 ( 중요도 ) 부여가 어려움 Fuzzy Set Model – 단일 피연산자의 의존이 심화 Extended Boolean Model – 불리언에 대한 엄격한 해석을 피함 – 우선 순위 부여 가능 – 불확실성을 중요하게 다룸

37 E.B.M II 특징 – 색인 용어에 대한 가중치와 질의 용어에 대한 가중 치 (P-norm) – 범위가 0 ~ 1 종류 –MMM model –Paice Model –P-norm Model

38 MMM Model Zadeh 의 Fuzzy set 개념을 기반 유사도 계산시 최대, 최소 가중치만을 사용 C 는 질의 연산자에 대한 융통성 계수 –C AND1 : [0.5, 0.8] –C OR1 > 0,2 검색 효율이 높음 than boolean model

39 Paice Model Fuzzy set 개념을 기반 유사도 계산시 모든 문헌 가중치를 사용 r 의 값 AND : 1.0, OR : 0.7 일때, 검색효율이 높음 [Fox] MMM 보다 계산 비용이 많이 듬

40 P-norm Model 색인용어의 가중치 + 질의용어의 가중치 OR Query – 모든 문헌의 색인용어 가중치가 0 인 경우 검색에서 제외 – 문헌 가중치는 (0,0,…,0) 인 좌표에서 떨어진 거리를 내림차순 으로 정렬 AND Query – 모든 문헌의 색인용어 가중치가 1 인 경우 가장 적합 – 문헌 가중치는 (1,1,…,1) 인 좌표에서 떨어진 거리를 오름차순 으로 정렬 P-norm Model 이 가장 효율적 [Fox]

41 P-norm Model