�ݺ�ߣ

제3장.
정보검색 색인어 추출을
위한 언어학적
INFORMATION RETRIEVAL 처리

강의: 정창용 (timothy97@gmail.com)
http://www.facebook.com/hhuIR
Korea Maritime University
Navis Control Inc.

OVERVIEW

 구(Phrase)단위 색인
 단어(Word)단위 색인
 토큰(Token) 생성
 토큰의 정규화
 토큰 내 구두점 처리
 복합명사 처리
 대소문자 변형
 불용어(Stop words) 리스트
 어미통제(Stemming)

OUTLINE

 구(Phrase)단위 색인
 단어(Word)단위 색인
 토큰(Token) 생성
 토큰의 정규화
 복합명사 처리
 대소문자 변형
 불용어(Stop words) 리스트
 어미통제(Stemming)

구(PHRASE)단위 색인

 필드값을 그대로 색인어로 사용
 복수의 필드값을 갖는 필드는 분리하여 색인
 Ex) Dialog ERIC 시스템 : AU, DE, ID 필드를 세미콜론(;)으로 구분
 불용어(stop words) 제거하지 않음
 ‘et al’이나 ‘and others’로 검색 가능
 구두점이나 스페이스를 색인어로 사용
 Boolean 검색에서 사용되는 연산자를 위한 특별 처리 필요
 Ex) 스페이스, AND, OR, NOT

DIALOG 검색시스템의 명령어

DIALOG에서의 검색 예

 탐색1) S QAULITY OF LIFE
 “quality of life”를 검색
 공백문자(space)와 불용어 ‘of’를 그대로 사용
 공백문자를 포함하면 ‘구(phrase)단위’ 검색임
 탐색2) S QAULITY OF LIFE/DE,ID
 구단위 검색이 가능한 필드는 DE (Descriptor), ID (Identifier) 임
 탐색1과 같은 결과
 탐색3) S QUALITY AND OF AND LIFE
 “quality and of and life”를 검색
 and는 연산자가 아님
 탐색1, 2와는 완전히 다른 결과

공백문자의 용도에 따른 구단위 색인

디스크립터 스페이스를 문자로 사용 스페이스를 연산자로 사용
quality of life quality of life quality-of-life

Bradford’s law Bradford’s law Bradford’s-law

management by objective management by objective management-by-objective

back to work movement(LBR) back to work movement(LBR) back-to-work-movement(LBR)

bolts and nuts bolts and nuts bolts-and-nuts

 한글 검색에서는 복합명사를 띄워 쓰지 않고 색인 하기도 함
 밥 짓는 시인 퍼 주는 사랑 ▶ 밥짓는시인퍼주는사랑
 정보 검색 ▶ 정보검색

‘AND’의 용도에 따른 색인

 S “BOLTS AND NUTS”
 검색할 색인어에 따옴표를 사용
 ‘AND’는 연산자 아님
 구단위 검색으로 ‘bolts and nuts’를 검색함
 S BOLTS AND NUTS
 TI, AB, DE 필드에서 ‘bolts’와 ‘nuts’가 포함된 항목을 검색함
 ‘AND’는 연산자로 사용됨

색인을 위한 언어학적 처리

① 토큰(token) 생성
② 불용어(stop words) 처리
③ 어미 통제(stemming)
④ 용어의 출현위치 부여
⑤ 가중치 부여

* 한글 검색시스템에서는 ②, ③ 단계의 순서를 달리할 수 있음

색인 시스템

문헌 ID 부여

텍스트 토큰분할

토큰 문헌번호
불용어 제외*
필드번호

비불용어 토큰 스테밍*

어미 통제된 용어 용어출현위치부여*

위치 부여된 색인어 용어가중치부여*

가중치, 출현위치 도치색인파일
번호를 가진 색인어 시스템

탐색 시스템

피드백 적합성 판정* 질의

질의
질의 분할
질의 토큰

불용어 제외*
순위화된 문헌 질의 용어

순위화* 스테밍*
통제된 용어

검색된 문헌 질의용어 가중치*

불리언 연산* 가중치 용어

적합문헌
도치색인파일
시스템

토큰 생성 (TOKENIZATION)

 토큰 생성 정책 필요
 단어의 시작과 끝을 결정하는 규칙 (space, 구두점)
 토큰 내 특수문자 처리
 색인 제외 문자열 : 한(one) 문자 단어, 숫자

토큰 생성 예

Are all citations equal? or, did we op. cit. your item?

Ex1) Tokenize

are all citations equal or did we op cit your item

‘ad hoc’ 검색은 비교적 정적인(static) 정보원/문헌집단을 대상으로

Ex2) Tokenize

ad hoc 검색은 비교적 정적인(static) 정보원/문헌집단을 대상으로

토큰 생성 예 – C O N T .

knn 분류기, svm 분류기, 신경망 분류기 등을 사용하여,

Tokenize

knn 분류기 svm 분류기 신경망 분류기 등을 사용하여

Ex3) Remove stop words

knn 분류기 svm 신경망 등을 사용하여

Stemming

knn 분류기 svm 신경망 사용

토큰의 정규화(normalization)

 토큰의 정규화
 약간의 차이가 있는 토큰들을 동일한 토큰으로 만드는 과정
 동일 어간을 가진 변형된 단어를 동일한 단어로 만드는 과정
 Ex) car, cars, Cars, automobile ▶ “car“
 정규화 방법
 동등수준의 토큰 중 하나의 동치류(equivalence calss)로 매핑
 full-text, fulltext, full-texts ▶ “fulltext “로 매핑
 효율적이지만 매핑 조건 선택이 어려움
 U.S.A.=usa, C.A.T.≠cat
 비정규화된 토큰 간의 관례를 유지 (시소러스 * 용어관계사전 이용)
 automobile ▶ “car“
 검색 시 정규화 vs. 색인 시 정규화

참고) 시소러스(thesaurus)

토큰 내 구두점 처리

 구두점을 처리하는 방법
 분리자(seperator)로 사용
 무시(제거)
 그대로 남겨 둠

구두점 처리 – C O N T .

 어퍼스트로피(‘)
boy’s → boys’, boys, boy s
O’Neill → O’Neill, ONeill, O Neill
aren’t → aren’t, arent, aren t, are n’t
‘ad hoc’ → ad hoc

 하이픈(-)
on-line → online [무시(제거)]
state-of-the-art → state of the art [분리자로 사용]
Knuth-Morris-Pratt Algorithm → Knuth-Morris-Pratt Algorithm

 슬래쉬(/)
TCP/IP → TCP/IP, TCP IP
정보원/문헌집단 → 정보원/문헌집단, 정보원 문헌집단

구두점 처리 – C O N T .

 온점(마침표, dot)
 ‘Z39.50’, ‘wordlist.txt’, ‘3.15’, ‘6.25 동란’
 남겨 두는 것이 좋음
 반점(쉼표, comma)
 천 단위 구분자 사용
 무시하는 것이 효과적
 기타 특수 부호(special character)
 C++, C# : 특정 의미를 가짐
 Google : ! ? , . ; [ ] @ / # < > 제외시킴
 숫자(digits)
 일반적으로 색인어에서 제외 (수치 검색시스템 예외)
 고유명사에 포함된 숫자는 색인 포함 : i5 CPU, 386세대

시스템별 구두점 처리

토큰 처리 LC Dialog Google

어퍼스트로피 제거 분리자 그대로

온점(마침표) 분리자 분리자 제거

하이픈 분리자 분리자 그대로

슬래쉬 분리자 분리자 제거

#,+,$ 등 특수기호 그대로 #:제거, 나머지: 그대로

복합명사 처리

 인접한 명사를 하나로 합치거나 둘 이상으로 분리하는 것
 고유명사
 둘 이상의 인접 토큰이 대문자로 시작되면 하나로 합침
 Ex) Los Angeles, New York, San Francisco
▶ LosAngeles, NewYork, SanFrancisco
 단어 n-그램 (word n-gram)
 인접한 토큰을 n개씩 묶는 방법
 Ex) “Quality of life in Korea”
▶quality, quality of, quality of life, of life in,
life in Korea, in Korea, Korea
 한국어: 복합명사를 분리하는 경향 있음
 중국어, 일본어: 문자 N-그램 방식이 효과적

대소문자 변형

 대문자 혹은 소문자로 일괄 변환
 Dialog, Google
 약어가 일반 단어와 구분되지 않는 문제 발생
 U.S. ▷ US ▷ us
 C.A.T ▷ CAT ▷ cat
 고유명사가 일반명사와 구분되지 않는 문제 발생
 General Motors ▷ general motors
 Windows ▷ windows
 일본어
 히라가나+가타가나+한자 ▷ 히라가나

불용어(STOP WORDS) 리스트

 불용어(stop words) : 어휘분석 시 제거되는 의미 없는 기능어
 영어: 관사, 전치사, 접속사
 한글: 조사, 접속사
 출현 빈도가 높은 단어를 불용어로 선택
 Ex) an, and, by, for, from, of, the, to, with
 출현 빈도가 높지만 특정 의미를 지니는 단어는 불용어 제외
 a ◀ “Vitamin A”, in ◀ “in-vitro”, on ◀ “on-line”
 색인 저장장소를 절약
 다량의 불용어는 검색 성능을 낮춤
 “To be or not to be”
 “gone with the wind”
 “as we may think”

언어처리에 의한 파일 크기 감소율

포스팅에 위치정보까지
단어 포스팅
포함할 경우

감 누 감 누 감 누
개수 소 적 개수 소 적 개수 소 적
율 % 율 % 율 %

토큰 수 484,494 109,971,179 197,879,290

숫자 제외 473,723 -2 -2 100,680,242 -8 -8 179,158,204 -9 -9

대소문자통일 391,523 -17 -19 96,969,056 -3 -12 179,158,204 -0 -9

30개 불용어 391,493 -0 -19 83.390,443 -14 -24 121,857,825 -31 -38

150개 불용어 391,373 -0 -19 67,001,847 -30 -39 94,516,599 -47 -52

스테밍 322,383 -17 -33 63,812,300 -4 -42 94,516,599 -0 -52

스테밍 (STEMMING)

 같은 어간(stem)을 가진 용어들을 하나의 색인어로 매핑
 접미사(접두사)를 제거하고 남은 형태소를 하나로 정리하는 처리
engineer, engineered, engineering ▶ engineer
use, user, users, used, using ▶ use
read, reads, reading, readable ▶ read
connect, connected, connecting, connection, connections ▶ connect

 cf. 원형복원(lemmatization)
saw, seen
▶ see
am, are, is ▶ be

접미사 제거 (by Porter)

 Notation
 V - 모음 : a, e, i, o, u와 자음 다음에 오는 y
 C - 자음
 단어의 형태
 [C](VC){m}[V]
 (VC){m} ⇒ (VC) 형태가 m번 반복
 CCC… ⇒ C, VVV… ⇒ V
m=0 TR, EE, TREE, Y, BY.
m=1 TROUBLE, OATS, TREES, IVY.
m=2 TROUBLES, PRIVATE, OATEN,
ORRERY.

PORTER STEMMER

 Notation
 *S : S로 끝나는 어간(stem)
 *v* : 모음을 담고 있는 stem
 *d : 쌍자음으로 끝나는 stem
 Ex) -TT, -SS)
 *o : CVC로 끝나지만 두 번째C가 w, x, y가 아닌 stem
 Ex) -WIL, -HOP

PORTER STEMMER – 1 ST STEP

 Step 1a
조건 접미사 → 치환 예
SSES → SS caresses → caress
IES → I ponies → poni
ties → ti
SS → SS caress → caress
S → {null} cats → cat

 Step 1b
(m>0) EED → EE feed → feed
agreed → agree
(*v*) ED → {null} plastered → plaster
bled → bled
(*v*) ING → {null} motoring → motor
sing → sing

PORTER STEMMER – 1 ST STEP

 Step 1b에서 규칙 2 혹은 3으로 스테밍된 단어에 한하여
AT → ATE conflat(ed) → conflate
BL → BLE troubl(ed) → trouble
IZ → IZE siz(ed) → size
*d and not (*L → single letter hopp(ing) → hop
or *S or *Z) tann(ed) → tan
fall(ing) → fall
hiss(ing) → hiss
fizz(ed) → fizz
(m=1 and *o) → E fail(ing) → fail
fil(ing)→ file

 Step 1C
(*v*) Y → I happy → happi
sky → sky

PORTER STEMMER – 2 ND STEP

(m>0) ATIONAL → ATE relational → relate
(m>0) TIONAL → TION conditional → condition
rational → rational
(m>0) ENCI → ENCE valenci → valence
(m>0) ANCI → ANCE hesitanci → hesitance
(m>0) IZER → IZE digitizer→ digitize
(m>0) ABLI → ABLE conformabli → conformable
(m>0) ALLI → AL radicalli → radical
(m>0) ENTLI → ENT differentli → different
(m>0) ELI → E vileli → vile
(m>0) OUSLI → OUS analogousli → analogous
(m>0) IZATION → IZE vietnamization → vietnamize
(m>0) ATION → ATE predication → predicate
(m>0) ATOR → ATE operator → operate
(m>0) ALISM → AL feudalism → feudal
(m>0) IVENESS → IVE decisiveness → decisive
(m>0) FULNESS → FUL hopefulness → hopeful
(m>0) OUSNESS → OUS callousness → callous
(m>0) ALITI → AL formaliti→ formal
(m>0) IVITI → IVE sensitiviti → sensitive
(m>0) BILITI → BLE sensibiliti → sensible

PORTER STEMMER – 3 RD STEP

(m>0) ICATE → IC triplicate → triplic
(m>0) ATIVE → {null} formative → form
(m>0) ALIZE → AL formalize → formal
(m>0) ICITI → IC electriciti → electric
(m>0) ICAL → IC electrical → electric
(m>0) FUL → {null} hopeful → hope
(m>0) NESS → {null} goodness → good

PORTER STEMMER – 4 TH STEP

(m>1) AL → {null} revival → reviv
(m>1) ANCE → {null} allowance → allow
(m>1) ENCE → {null} inference → infer
(m>1) ER → {null} airliner → airlin
(m>1) IC → {null} gyroscopic → gyroscop
(m>1) ABLE → {null} adjustable → adjust
(m>1) IBLE → {null} defensible → defens
(m>1) ANT → {null} irritant → irrit
(m>1) EMENT → {null} replacement → replac
(m>1) MENT → {null} adjustment → adjust
(m>1) ENT → {null} dependent → depend
(m>1) and (*S or *T) ION → {null} adoption → adopt
(m>1) OU → {null} homologou → homolog
(m>1) ISM → {null} communism → commun
(m>1) ATE → {null} activate → activ
(m>1) ITI → {null} angulariti → angular
(m>1) OUS → {null} homologous → homolog
(m>1) IVE → {null} effective → effect
(m>1) IZE → {null} bowdlerize → bowdler

PORTER STEMMER – 5 TH STEP

 Step 5a
(m>1) E → {null} probate → probat
rate → rate
(m=1 and not *o E → {null} cease → ceas

 Step 5b
(m>1 and *d and *L → single letter controll → control
roll → roll

PORTER STEMMER - Example

 GENERALIZATIONS
 Step1 ▶ GENERALIZATION
 Step2 ▶ GENERALIZE
 Step3 ▶ GENERAL
 Step4 ▶ GENER

 CONNECTIONS
 Step1 ▶
 Step2 ▶
 Step3 ▶
 Step4 ▶

사전크기 변화

 10,000개의 단어사전을 스테밍한 결과(by Porter)
1단계 3597
2단계 766
줄어든 단어 수 3단계 327
4단계 2424
5단계 1373
남은 최종 단어 수 3650

�ݺ�ߣ

제3장 색인어 추출을 위한 언어학적 처리

More Related Content

제3장 색인어 추출을 위한 언어학적 처리