데이터베이스 - 정보 검색 시스템

데이터베이스를 활용하는 응용분야 중 방대한 텍스트에서 특정 키워드를 검색하는 시스템을 구축하는 방법에 대해 알아본다. 사실 데이터베이스 포스팅이라기 보다는 검색엔진에 관련된 주제이지만 뭐 데이터베이스 수업에서 나온 내용이므로 데이터베이스로 포함시켰다. 검색엔진은 원하는 키워드를 적합한 순서로 정렬해서 보여줘야하기 때문에 방대한 문서들을 정렬하는 알고리즘이 중요하다.

 

 

 

키워드를 사용하는 방법

특정 키워드를 검색할 때 문서에서 해당 단어의 가중치를 계산해서 정렬하는 방법이 있다.

 

TF-IDF

Term Frequency Invert Document Frequency의 약자로 여러 문서로 나타난 문서에서 특정 키워드가 얼마나 중요한지를 나타내는 가중치를 나타내는 수치이다. 문서의 핵심 단어를 추출하거나 검색엔진에서 결과의 우선순위를 정할 때 사용된다.

TF(Term Frequency)는 문서에서 해당 단어가 얼마나 많이 나타나는지를 뜻하는 수치로 이 값이 높을수록 문서에 많이 등장한다는 뜻이다. TF를 구하는 방법은 여러가지가 있지만 여기서는 아래와 같은 방법으로 구한다.
1을 더하는 이유는 해당 문서에 원하는 단어가 하나도 없을 수 있기 때문이다.

 

TF = log(1+n(d,t)/n(d))
n(d,t) = number of term t in document d
n(d) = number of term in document d

 

위처럼 복잡한 방법 말고 간단하게 해당 단어가 등장하면 1, 없으면 0으로 처리하는 방법도 있다.

 

IDF(Inverse Document Frequency)는 전체 문서집합에서 해당 단어가 얼마나 자주 나타나는지를 나타내는 DF(Document Frequency)의 역수로 이 값이 클 수록 보편적이지 않은 단어라는 뜻이된다. IDF 값은

 

IDF(t) = n(d)/n(d,t)
n(d) = number of documents
n(d,t) = number of documents that has term t in

 

와 같이 구할 수 있다.

 

결과적으로 TF-IDF는 TF에 IDF를 곱한 수치인데 이 값이 클수록 다른 문서에서는 많이 등장하지 않지만 해당 문서에서는 많이 등장하는 즉, 해당 키워드에 특화된 문서라는 뜻이된다.

 

추가적인 방법

TF-IDF 수치 외에도 더욱 적절한 문서를 찾을 수 있게 하기 위해서 다양한 알고리즘이 사용된다.

 

• 제목, 부제목에 등장하는 단어에 더 큰 가중치를 주는 알고리즘
• 문서에서 늦게 등장하는 단어에 더 낮은 가중치를 주는 알고리즘
• if, are, the, it 처럼 의미없는 단어는 제외하는 알고리즘
• 같은 단어가 등장하는 간격이 좁을 수록 더 큰 가중치를 주는 알고리즘

 

 

하이퍼링크를 사용하는 방법

키워드만 사용해서 문서를 검색하면 결과값도 너무 많이나오고 정렬도 잘 안되기 때문에 추가적인 방법이 요구된다. 하이퍼링크를 사용하는 방법은 사람들이 문서를 검색할 때 유명한 사이트에서 검색하는 경우가 많다는 것에서 아이디어를 얻은 것으로 웹사이트의 대중성을 먼저 정렬하고 거기에서 키워드와 매치가 많이 되는 사이트를 우선적으로 보여주는 방법을 고안해냈다.

 

 

동의어

키워드를 검색할 때 동의어를 처리해주어야 적절한 결과를 제공할 수 있다. 예를들어 motorcycle repair와 motorcycle maintenence는 둘 모두 오토바이 수리 라는 뜻을 가지고 있기 때문에 시스템은 해당 쿼리를 motorcycle and (repair or maintenece) 정도로 수정해서 처리할 수 있어야 한다.

 

 

검색 효율성

좋은 검색 효율을 가지는 엔진은 false drop (false negative) 즉, 검색 결과에서 관련이 없는 문서가 하나도 경우가 많고, false positive 즉, 검색 결과에 관련없는 문서가 발견되는 경우가 적은 엔진을 말한다.

 

정확성 (Precision)

검색된 문서들 중 실제로 쿼리와 관련된 문서의 비율. 예를들어 검색결과가 10개이며 그 중 검색하고자 했던 kiwi에 대한 문서가 5개가 있다면 정확성은 50%라고 한다.

 

재현율 (Recall)

전체 문서에서 쿼리로 검색한 결과집합에 관련된 문서가 얼마나 포함되었는지 비율. 예를들어 전체 문서에 banana와 관련된 문서가 10개가 있고, 검색 결과에 그 10개의 문서가 모두 검출되었으면 재현율은 100%라고 말한다. 결과에 banana와 관련되지 않은 문서가 포함되어 있더라도 이 수치는 변하지 않는다.

위 두 수치는 독립적으로 사용되는 것이 아니라 함수처럼 사용된다. 예를들어 재현율 50%인 결과에서 정확성이 75%이다. 또는 재현율이 75%인 결과에서 정확성이 30%이다 처럼 사용된다.