검색 엔진2 - 검색 기법

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.




드디어.. 5개월만에 새로운 글을 쓰게 되었습니다.
회사 이직과 맞물려 너무 정신이 없었습니다.바쁘다는 핑계로.. 이렇게 소홀하게 되다니...
==============================================================================
검색 기법
다음은 BELKIN, NICHOLAS J.and CROFT, W. BRUCE,"Retrival Techniques," ARIST, 22(1987), PP. 109-145 에서 발취한 내용들이다.
BELKIN, NICHOLAS J.and CROFT, W. BRUCE등에 의해 제안된 검색기법의 분류방법
+-- Exact match
+-- Partial match --+-- Individual --+--- Structure-based
+-- Network +--- Feature-based

1. Exact match techniques(완전일치 기법)
검색된 도큐먼트들의 표현(representation)이 질문의 표현과 완전하게 일치된 것만 검색하는 방식이다. 초창기 대규모 검색시스템들에서 대부분 사용하던 방식이다. 이런 방법의 적용 예로는 불리언 검색, 전문검색, 스트링검색등이 있다.
단점으로는 다음과 같은 것들이 지적되어 왔다.
1) 이용자의 질의에 부분적으로 일치되는 경우의 텍스트들이 그 유용성에도 불구하고 검색에서 누락되는 예가 많다.
2) 검색된 텍스트들에 대한 적절성의 순위를 정하지 못한다.
3) 질문 및 텍스트 내에 존재하는 상호관련성이 있는 중요개념들을 전혀 고려하지 않는다.
4) 질문의 논리적 형성과정이 까다롭다.
5) 이용자의 질의 표현과 텍스트의 표현 비교가 오직 동일어휘로만 한정되어 있다.

이러한 단점에도 불구하고 초창기 많이 쓰이게 된 이유는 다음과 같다.
1) 검색기법을 변경하는데 드는 비용이 너무 많기 때문에 비경제적이다.
2) "exact match"기법이외의 대체기법들을 아직까지 대규모 시스템 환경에서 운영(테스트)해 본적이 없다.
3) 그러한 대체 기법들 조차도 실험적인 시스템 환경에서 테스트해 본 결과 그다지 만족스러운 것이 아니었다.
4) 이용자의 정보요구나 질의를 표현하는데 있어서 블리안 기법이 비교적 우수하다고 볼 수 있다.
그러나 현재 진보된 검색시스템들을 보게되면 위의 3,4번에 대한 이유가 무색해 진다. 현재 사용되고 있는 대부분의 상용 검색엔진들은 경험적으로나 이론적으로나 위의 3,4번에 대한 경우가 잘못된 생각임을 증명하고 있다.


2. Partial match techniques(부분일치 기법)
검색된 도큐먼트들의 표현이 질문의 표현과 부분적으로 일치된 경우의 것들로 함께 검색하는 방식이다. 여기서 Individual 방법은 이용자 질의를 각각의 개별 도큐먼트들과 비교 하는 방식을 말하며 Network 방법은 이용자 질의를 개별 도큐먼트들의 표현과 비교하는 것이 아니라 개별 도큐먼트들 및 이와 관련된 다른 도큐먼트들과의 관계성 에 중점을 두어 작성되는 표현들과 비교한 검색기법이다. 이러한 네트웍 검색기법 에서는 개별 도큐먼트들의 내용에만 전적으로 의존하여 검색이 이루어지기 보 다는 이들과 관련을 맺고 있는 네트웍 기법으로는 cluster에 근거한 검색기법 과 Browsing기법 및 Spreading activation기법이 있다.

2.1 Individual, Feature-based
이용자의 질의 및 도큐먼트들의 표현방식을 "색인어"와 같은 일련의 특징들로 표현하는 방식
->이러한 일련의 Features(특징)들은 각각 가중치로 표현될 수 있으며, text내에서 나오는 보다 복잡한 현상들을 표현하기에 적합하다. 이러한 feature-based기법에는 다시 Formal mode(여기에 해당되는 기법으로, Vector space model, 확률모델, fuzzy set model 등이 있다)과 Ad-hoc model이 있다. 이러한 범주의 기법들은 이용자의 질의를, 일련의 특징들 혹은 색인어들로 나타내는 도큐먼트 표현과 비교하는 방식을 취하고 있다. 이때의 도큐먼트 표현물들은 수작업이나 자동색인의 방식으로 도큐먼트의 텍스트 상으로 부터 추출되어지며, 마찬가지로 이용자 질의용어 역시 자연어로 표현된 질문으로 부터 직접 추출되거나, 색인어휘상의 용어를 사용하기도 한다. 여기에서 "feature"로 채택되는 요소들은, 단어나 어근, 구 혹은 개념들로서 이들과 관련된 가중치(weighte)값을 지니게 된다. 이러한 가중치들은, 그러한 각 요소들이 한 도큐먼트에 출현하는 빈도수나 혹은 이의 역 빈도수에 의하여 측정될 수 있다. 이러한 가중치의 표현방법이나 사용방법 및 계산방법 등은 각 시스템이 채택하고 있는 검색기법에 따라 다를 수가 있다.
(Formal) ==> Vector space model, probabilistic model, fuzzy set model.

2.1.1 Vector space model(벡터 공간 모델)
벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간속의 벡터들로 취급되며, 이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(tf)와 이의 역빈도수를 조합하여 계 산한다.
2) "낮은 식별치"(poor discriminatin value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며 구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 "코사인"상관도(cosine correlation)에 의해 계산된다(벡터 공간내에서 이 용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해 낸다)

2.1.2 Probabilistic model(확률모델)
확률모델은 지금까지의 검색기술에 새로운 방법론을 제시한 것으로서, 그 기술적 기반은 위의 벡터공간 모델로 부터 나온 것이다. 이 모델의 기본적인 목적은 이용자의 질의에 대한 적절성의 고확률순으로 도큐먼트의 순위를 정하여 검색하는 것이다. 즉, 각각의 도큐먼트를 구성하는 용어의 가중치가 "1"혹은 "0"의 값을 가질 수 있고 또한 이러한 각각의 용어들은 다른 용어들에 대해서 독립성을 지녔다고 가정하여 각 도큐먼트들의 순위를 정하는 방법이다.

2.1.3 Fuzzy set(퍼지 집합 이론)
이것은 검색기법 상으로 볼 때 블리언 질문기법과 도큐먼트 순위 매김기법을 통합한 기법이나 벡터공간 모델에 기초한 확장된 블리언 검색기법과 비교해 볼 때, 이러한 통합에는 한계가 있음이 드러났다.

2.1.4 Ad hoc(애드 혹 모델)
이 모델의 기본은 질의 용어군과 도큐먼트 용어군과의 겹침(over-lap)의 정도를 측정하여 그 유사성의 정도에 의하여 문헌을 검색하는 기법이다.


2.2 Individual, Structure-Based Techniques(개별적, 구조기반 기술)
이러한 범주에 드는 검색모델의 특징은 이용자 질의나 도큐먼트의 내용을, 색인어 등의 방식이 아닌 좀 더 복잡한 구조적 형태(structure)로 표현하여 이를 비교하는 방식이다. 이러한 검색기술은 특히, 특정한 전문주제분야에 적용되는 것이 적절하다.

2.2.1 Logic(논리모델)
도큐먼트의 텍스트가 담고있는 핵심적인 정보는 몇개의 짧은 문장으로 표현될 수 있으며, 이러한 문장들은 일정한 논리식으로 표현이 가능하다. 이와 마찬가지로 이용자의 질의도 논리식에 의한 표현이 가능하며, 이러한 질의는 논리식과 연계된 추론법칙에 의해서 그 해답이 가능하다.
예) 도큐먼트의 주제내용. "If a company sells computer, it is financially viable".
==> 논리식으로 표현 ==> (for all(x) (if (sells x computer) (viable x)))
이때 이용자의 질문(viable?)의 경우 "forward chaming"으로 해답이 가능하다. 이러한 모델의 가장 커다란 어려움은 각 텍스트들을 논리식으로 전환하는 작업인데, 현재는 수작업으로 하고 있다.

2.2.2 Graph(그래프 모델) 이 모델은 그래프 형태의 표현방법을 이용한 검색기법이다. 즉, 그래프 형태의 표현방법은 노드들과 이러한 노드들간의 edges(links)들로 이루어져 있는데, 이러한 노드들과 edges들은 주로 자연어 처리과정을 통해서 얻어지는 의미망(semantic nets), 혹은 의미프레임(semantic frames)으로 표현된다. 검색기법은 질의어의 그래프 구조와 도큐먼트의 그래프 구조를 서로 비교하여 그 유사성에 의거하여 문헌을 검색하거나 그 순위를 정하는 방식이다.


2.3 Network(네트웍 모델)

2.3.1 Cluster(클러스터 모델)
클러스터란, 내용이 유사한 일련의 도큐먼트군을 의미한다. 이것은 SMART프로젝트에 채택된 검색기법으로서, 클러스터 계층구조(CLUSTER HIERACHY)에 의한 것이었다.
* 클러스터 계층구조
--> 전체의 도큐먼트들을 몇개의 클러스터들로 나눈후에 각각의 클러스트들을 또다시 작은 클러스터들로 나누는 반복된 작업구조.
검색방법은 이용자의 질의내용을 최상위의 클러스터로 부터 최하위의 클러스터들 까지 하향식으로 비교하여 그 유사성의 큰 것부터 차례대로 검색해 내는 방식.

2.3.2 Browsing(브라우징 기법)
각각의 도큐먼트, 색인용어, 서지적 정보들을 시스템상에서 노드와 컨넥터들로 표현된 네트웍 구조로 만들 수 있다면, 이 때, 이용자는 이러한 네트웍을 훌터나가면서(Browsing) 필요한 도큐먼트들을 검색하는 기법. 이러한 Browsing기법에서 주목할 사항은 검색기법상 이용자 질문식의 형성(query formulation)에는 중점을 덜 두는 반면에, 이용자로 하여금 Browsing과정 중에서, 즉각적인 피드백을 강조하는 시스템이다.
I R 시스템의 예
노드(node) --> 도큐먼트, 색인어, 주제영역지식, 저자, 저널명.
링크(links) --> 색인정보, 시소러스 정보, 인접노드정보, 인용, 저자사항.

2.3.3 Spreding activation(스프래딩 액티베이션 모델)
위의 Browsing기법과 유사한 모델
네트웍 상에서 이용자의 질문에 해당되는, 어느 한 부분의 노드(색인어 혹은 도큐먼트) 및 이와 관련된 또 다른 노드들만 활성화(activate)시켜 가면서 최종 도큐먼트를 검색해 내는 방식.
예를들어 이용자의 질문에 의해서 어느 한 색인어가 선택되어 졌을 때, 이 색인어와 연결된 도큐먼트들 및 관련 색인들 역시 함께 활성화시키게 되는 방식.

2.4 Feedback Methods(피드백 기법)
이 기법은, 원래 "Feature-based"기법에서 발전되어 온 것으로서 현재는 모든 검색기법에서 응용되고 있다. 이 기법의 핵심은, 질의 용어에 대한 기준치를 검색도중에 수정해 가면서 최적의 도큐먼트들을 검색해 내는 방식이다. 이러한 가중치의 수정은, 적합한 것으로 판단된 도큐먼트들 속에 포함된 색인어들의 빈도수에 의해서 결정된다. 10-20%.



Relative Performance of Retrieval! Techniques(검색기법의 상호성능 비교)
(Comparation Performance Studies)
1) 전반적으로 완전일치(exact match)기법보다는 부분일치(paricial-match)기법에 의 한 검색 결과가 더우수한 것으로 나타났다.
2) Feature-based기법 중에서는 특히 색인어에 대한 가중치 부여 기법을 사용한 확률 모델 기법이 가장 우수한 것으로 조사되었으며, 이때 용어의 가중치를 주는 방식 에 따라 그 검색성능이 크게 달라졌음이 밝혀졌다.
3) 클러스터 검색기법의 경우 "individual feature-based"검색에 버금가는 성능을 지녔으며, 특히 다른 검색기법들에 비해서, 높은 정확율을 가져온 것으로 나타났다. 따라서 클러스터 기법은 "individual feature-based"모델을 대체할 수 있는 좋은 기법이다.
==============================================================================
오늘도 하나 배워가는 하루가 되시길...