정보검색 기초

최신정보검색론
취업시즌 놀면서
매우 심플하게 요약해봄.

정보검색기초.hwp

 ------------------------------------------------------------------------------------------------------------

* 정보검색(IR:information retrieval)
 - 대규모 정보군(일반적으로 컴퓨터에 탑재되어있는 형태)으로부터 정보 요구를 충족시키는 비구조적인 속성(일반적으로 텍스트)을 지닌 자료(일반적으로 문헌)을 찾아내는 것.


* 문서(document)
 - 하나의 검색 시스템을 구축하기로 결정한 기반 단위


* 문헌의 집단(collection)
 - 검색 대상이 되는 문헌의 집단. 또는 말뭉치(corpus)


* 용어(term)
 - 색인의 기본 단위


* 용어 추출
 - 그대로 : 별도의 추출 없이 해당 필드의 내용을 그대로 사용
 - 어절 단위 추출 : 공백으로 구분되어 있는 어절 단위로 추출한다.
 - 형태소 분석 : 형태소 분석기를 이용하여 형태소 단위로 추출한다.
 - bi-gram : 두 개의 글자를 하나의 term으로 추출한다.
 - n-gram : n개의 글자를 하나의 term으로 추출한다.


* 기본 검색 방식
 - 불리언 연산(boolean) : and, or, not
 - 절단 연산 : 절단, 우절단
 - 자연어 질의 : 형태소 분석, 바이그램
 - 근접 연산 : Near, Order
 - 유사어 확장 : 동의어(상하위어), 자오류보정, 다국어 확장, 구문 확장
 - 필드 지정 : 필드의 특성에 따른 추출방법 적용 필요, 필드간 중요도 차등적용 필요
 - 질의 보관 : 질의 로그(사용자의 의도 파악)


* 색인 구축   p.67
 - 역색인(Inversed Index) : 검색어가 들어왔을 때 해당 검색어가 포함된 문서를 빠르게 찾아주기 위하여 각각의 검색어가 들어있는 문서의 리스트를 구축.
   용어 - 문헌 빈도(doc freq.) → 문서식별자(docID) 리스트
 - 정렬-기반 색인 알고리즘(blocked sort-based indexing algorithm) : O(TlogT), 너무 큰 대용량 컬렉션에서 구현하기엔 적합하지 않음
 - 단일 패스 메모리 색인(single-pass in-memory indexing alogritm)
 - 분산 색인(distributed indexing) : 방대한 웹에서는 하나의 장비에 색인을 할 수 없다. MapReduce 방식
 - 동적 색인(dynamic indexing) : 대부분의 컬렉션은 사실 자주 수정된다.


* 역색인 구축 단계
 - 색인 대상 문헌 수집
 - 각 문헌을 토큰 목록으로 변환
 - 자연어 전처리 수행, 색인어가 될 정규화 토큰 목록 생성
 - 단어 알파벳순으로 정렬된 역색인 생성


* 불용어(stop words)
 - 너무 자주 출현하여 거의 쓸모가 없어 보이는 단어들을 단어 사전에서 제외시킴.
 - 키워드 탐색(keyword search)의 경우는 유용하나 구절 탐색(phrase search)의 경우 불용어가 제거되면 유용한 결과를 얻기 힘들 수 있다.
 - 최근에는 불용어 목록을 최소화하거나 아예 사용하지 않고 용어 가중치 기법을 적용하는 방향으로 변화


* 어근추출(stemming)
 - 유명한 알고리즘 : Porter's algorithm
 - ex) am, are, is → be / car, cars, car's, cars' → car
       the boy's cars are different colors → the boy car be differ color


* 표제어복원(lemmatization)
 - ex) caresses → caress / ponies → poni / cats → cat


* 와일드카드 질의(wildcard query)
 - 질의할 때 확신이 없을 때 '*' 기호 사용. B-tree를 사용..
 - 후방 절단 질의(trailing wildcard query) :  ex) mon*
 - 전방 절단 질의(leading wildcard query) :  ex) *mon


* 빈도/가중치   p.114
 - tf(term frequency) : 문헌 d에서 용어 t의 빈도
 - cf(collection frequency) : 컬렉션 안에 있는 용어의 전체 빈도
 - df(document frequency) : 용어 t를 포함하는 문헌들의 수
 - idf(inverse document frequency) : idf = log(N/df)
   → 드문 용어의 idf는 높고, 흔한 용어의 idf는 낮다.
 - tf-idf : tf * idf
   → 적은 수의 문헌에 용어 t가 많이 있으면 가장 높은 값을 가짐(문헌들에게 높은 식별력을 줌)
   → 한 문헌이나 많은 문헌들에 그 용어가 적게 있으면 더 적은 값을 가짐(적합성이 뚜렷하지 않음)
   → 모든 문헌 안에 그 용어들이 있을 경우 가장 낮은 값을 가진다.


* 벡터 공간 모델(vector space model)
 - 벡터 공간 안에서 문헌들의 집합을 표시. 질의를 벡터 공간에서의 벡터로 본다는 것!   p.117


* 유사성 계수(similarity coeffiecient) : 문헌 간에 유사성을 나타내는 척도
 - 자카드 계수(Jaccard coefficient) : 이진 데이터에 대한 유사도 척도
 - 코사인 유사도(Cosine similarity) : 벡터 공간 내의 두 문헌의 유사도 측정(문헌길이 상쇄)   p.117
   → sim(d1,d2) = V(d1)*V(d2) / |V(d1)||V(d2)|
   → 분모의 의미는 단위 벡터 v(d1) = V(d1)/|V(d1)|, v(d2) = V(d2)/|V(d2)| 로 길이 정규화하는 것임.
   → 따라서 다음과 같이 정규화된 두 문헌 벡터들의 내적으로 바꿀 수 있음
      => sim(d1,d2) = v(d1)*v(d2) = cosΘ
   → 문서 컬렉션 안에서 코사인 유사도 구하는 것은 엄청난 연산이 필요함. 이를 개선하기 위해 역색인 사용
 - 타니모토 계수(확장 자카드 계수), 다이스 계수(Dice's coefficient), 중복도 계수(Overlap coefficient) 등등 더있음.


* 유사도를 이용한 단순 알고리즘
 - 유클리디안 거리점수를 활용한 유사도 측정
 - 피어슨 상관점수
 - 맨하튼 거리
 - 유사성 계수 이용


* Heap 법칙(Heap’s law)   p.87

 - 용어의 수 추정.
 - X 축은 코퍼스 사이즈고, Y 축은 코퍼스 내에 출현한 단어의 종류
 - 코퍼스 사이즈가 10배 는다고 출현한 단어의 종류가 10배 느는게 아니라 로그 함수로 조금씩 는다는 것.
 - 90%를 커버하기는 쉽지만 100%를 커버하기 위해서는 엄청난 양의 코퍼스를 모아야 할 듯.


* Zipf 법칙(Zipf's law)   p.89

 - 용어 분포 모델링.
 - 점점 감소하는 그래프 모양.
 - 특정한 크기의 코퍼스에서 워드의 빈도수를 조사해 순위를 매긴 후, 순위*빈도 하면 특정한 상수가 됨.
 - 50위의 순위의 단어의 빈도수가 150위 순위의 단어보다 약 3배 정도 더 많이 사용되고,   1위 단어는 10000위 단어에 비해 약 만 배 정도 더 많이 출현한다는 소리


* 엔트로피(entropy)   p.98
 - 무질서도. 물리·열역학에서 나오는 엔트로피와 그닥 다르지 않음.
 - 정보엔트로피(정보량)가 높을수록 불확실성은 커진다.
 - 맑을 확률(50%), 비올 확률(50%) → 엔트로피 큼
 - 맑을 확률(90%), 비올 확률(10%) → 엔트로피 낮음


* 검색 집합의 평가   p.148

 - 정확률(precision) : 검색된 문헌의 적합한 일부분. (검색된 적합 문헌/검색 문헌). P = tp/(tp+fp)
 - 재현율(recall) : 적합한 문헌의 검색된 일부분. (검색된 적합 문헌/적합문헌). R = tp/(tp+fn)
 - 정밀도(accuracy) : 맞는 분류의 일부분. accuracy = (tp+tn)/(tp+fp+fn+tn)
 - F 척도(F measure) : 정확률과 재현율을 대체하는 또 다른 척도(정확률과 재현율의 가중치 조화 평균임)
 - 균형 F 척도(balanced F measure) : 알파값 = 1/2 또는 베타값 = 1 로 하는 F1 척도


* 검색 적합성 평가   p.157
 - kappa 통계치(kappa statistic)


* 검색에 사용되는 기본 확률들   p.212
 - 연쇄 법칙(chain rule)
 - 분할 법칙(partition rule)
 - Bayes’ rule
 - Odds
 - 확률 순위화 원리(PRP : probability ranking principle)


* 학습
 - 지도 학습(supervised learning)
 - 비 지도 학습(unsupervised learning)
 - 준 지도 학습(Semi-Supervised Learning)


* 지도 학습을 사용한 알고리즘
 - 서포트 벡터 머신(support vector machine)
 - 은닉 마르코프 모델(Hidden Markov model)
 - 나이브 베이즈 분류(Naive Bayes Classification)
 - 신경망(Neural network)
 - 회귀 분석(Regression)


* Naive Bayes Classification   p.256
 - 조건부확률
 - 임의의 data가 특정 분류에 속할 확률을 계산하여 계산된 확률 중 가장 확률이 높은 분류를 선택
 →  P(B|A) = P(A^B)/P(A)
     P(A^B) = P(B|A)P(A)
     P(A|B) = P(A^B)/P(B) = P(B|A)P(A)/P(B)
    ∴ P(A|B) = P(B|A)P(A)/P(B)


* 자질 선택(feature selection)   p.262
 - 상호 정보(MI : mutual information)
 - X2
 - 빈도 기반 자질 선택(frequency-based feature selection)


* 벡터 공간 분류
 - Rocchio classification
 - kNN classification


* SVM(support vector machine)
 - margin
 - support vectors


* 군집화 평가
 - 순도(purity)
 - 정규화된 상호 정보(NMI : normalized mutual information)
 - Rand 지수(rand index)
 - F-measure


* K-means
 - 중요한 평면 군집화 알고리즘


* PageRank

(100%맞는 그림은 아니지만 이해가 쉬운 그림.. 어디선가 퍼옴)
 - A의 페이지 랭크는 그 페이지를 인용하고 있는 다른 페이지 T1, T2, T3, ..가 가진 페이지 랭크를 정규화 시킨 값의 합
 - 세상의 모든 페이지를 PageRank 등수에 따라서 미리 정렬을 해 두고,   어떤 검색어를 입력하는 순간, 그 검색어가 포함된 페이지들을 순위별로 나열하기만 하면 끝
 - 영향력 있는 페이지가 인용할수록 페이지랭크가 올라간다.
 - ‘불펌’이 만연하는 곳에서는 이 알고리즘은 바보가 됨.
 - 원문 링크도 걸지 않고, 아무리 많은 사람들이 퍼가도 웹사이트의 순위는 올라가지 않는다.
 - 구글의 검색 베이스 알고리즘


* 해밍 거리(Hamming distance)
 - 같은 길이의 문자열 2개. 한 문자열을 다른 문자열로 바꾸기 위해 몇 글자를 바꿔야 하는지 나타낸 것.
 - 리처드 해밍이 제안. 통신에서 문자열 전송 도중 몇 글자에서 오류가 났나를 측정하는 방법


* Lucene
 - 정보 검색 오픈 소스 라이브러리. JAVA로 시작해 perl, python, C++ 등으로 포팅 되어 있음.
 - 소프트웨어 프로그램에 색인과 검색 기능을 간단하게 추가할 수 있도록 지원


* 책에 나오는 한 번씩 생각해 볼 것들.
 - Markov chain
 - 감마코드
 - 정보 이득(information gain)
 - 군집 가지치기(Cluster Pruning)
 - B tree, B* tree, B- tree
 - 웹 수집(web crawling)
 - 문서 요약(text summarization)
 - 동의어(synonymy), 시소러스
 - 기계학습