for textmining

단순 결합 질의(simple conjunctive query)

|

이번 포스팅에선 불린 검색 모델(Boolean Retrieval Model)의 기본인 단순 결합 질의(simple conjunctive query)를 파이썬으로 구현하는 걸 살펴보도록 하겠습니다. 이 글의 알고리즘은 Introduction to Information Retrieval(Manning, C. D. et al., 안동언 외 옮김)을 바탕으로 하되 코드는 제가 직접 작성했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

풀려는 문제

풀려는 문제는 다음과 같습니다. 예컨대 영화 리뷰 말뭉치에서 ‘영화’, ‘재미’, ‘깨알’ 세 단어가 동시에 사용된 문서를 찾고 싶은 겁니다. 이 때 세 단어들은 질의(query)가 됩니다. 우선 왓챠에서 72만2813건의 문서를 수집했고, 리뷰 하나가 하나의 행이 되도록 csv파일로 저장해뒀습니다. 이를 파이썬으로 읽어들이는 코드는 다음과 같습니다.

import pandas as pd
corpus = pd.read_table('review.csv', sep=',')

단어-문서 색인

영화 리뷰 말뭉치에 있는 단어와 문서를 다음과 같이 색인합니다. 우리가 필요한 정보는 특정 단어가 전체 문서집합 가운데 몇 건의 문서에 등장했는지(document frequency), 그리고 등장한 문서의 ID 집합(postings list)입니다.

위와 같이 색인하는 코드는 다음과 같습니다.

def make_index(corpus):
    # corpus 형태 : document로 이뤄진 list
    from collections import defaultdict

    # split docs and words
    docs = [doc.split() for doc in corpus 
            if isinstance(doc, str)]
    words = sorted(list(set(flatten(docs))))

    # indexing
    term_doc = defaultdict(list)
    for doc_idx, words in enumerate(docs):
        for word in words:
            term_doc[word].append(doc_idx)
    term_docfreq = {}
    term_post = {}
    for word, value in zip(term_doc.keys(),
                           term_doc.values()):
        term_docfreq[word] = len(value)
        term_post[word] = list(set(value))
    return term_docfreq, term_post

def flatten(x):
    result = []
    for el in x:
        if isinstance(el, list):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

포스팅 목록 비교 함수

‘영화’라는 단어가 등장한 문서의 ID는 다음과 같다고 칩시다. 이 아이디는 term_post로부터 구할 수 있습니다.

2, 4, 7, 8, 11

‘재미’는 다음과 같다고 합니다.

7, 368, 383, 434, 1049

우선 ‘영화’ 목록의 첫번째 포인터가 가리키는 2와 ‘재미’의 7을 비교합니다. 다르니까 패스합니다. 2는 7보다 작으므로 ‘영화’의 포인터를 하나 옮깁니다.

이번엔 4와 7을 비교합니다. 다르니까 또 패스합니다. 4는 7보다 작으므로 ‘영화’의 포인터를 하나 옮깁니다.

‘영화’의 7과 ‘재미’의 7이 이번엔 일치하네요. 이를 정답 리스트에 저장해놓습니다. 이런 식으로 검색해야 할 포스팅 목록이 사라질 때까지 같은 작업을 반복하는 겁니다.

코드는 다음과 같습니다.

def intersection(p1, p2):
    # 포스팅 목록 두개를 단순 비교
    # 계산복잡성은 p1 길이 + p2 길이
    p1 = sorted(p1)
    p2 = sorted(p2)
    answer = []
    while len(p1) > 0 and len(p2) > 0:
        if p1[0] is p2[0]:
            answer.append(p1[0])
            p1 = p1[1:]
            p2 = p2[1:]
        else:
            if p1[0] < p2[0]:
                p1 = p1[1:]
            else:
                p2 = p2[1:]
    return answer

단순결합질의

이번엔 두 개 이상의 단어로 이뤄진 쿼리에 대해 단순결합질의를 하는 함수를 만들어 보겠습니다. 그런데 하나 생각할 것이 있습니다. 예컨대 ‘영화’, ‘재미’, ‘깨알’이 동시에 들어있는 문서를 검색해야 한다면 Document Frequency가 가장 낮은 용어부터 처리해야 검색에 필요한 연산량을 줄일 수 있을 겁니다.

이와 관련해 단어들의 리스트로 이뤄진 쿼리와 DF 정보가 주어졌을 때 쿼리 단어를 DF 순으로 정렬해주는 함수를 만들었습니다. 다음과 같습니다.

def sort_freq(query, docfreq):
    result = sorted([[term,docfreq[term]] for term in query],
                 key=lambda x: x[1], reverse=False)
    return [term for term, _ in result]

마지막으로 단순결합질의를 위한 함수를 만들어보겠습니다. 쿼리를 DF가 낮은 순으로 정리한 뒤 순서대로 겹치는 목록(문서)을 찾아가는 방식입니다. 코드는 다음과 같습니다.

def search(query, posting, docfreq):
    terms = sort_freq(query, docfreq=docfreq)
    result = posting[terms[0]]
    terms = terms[1:]
    while len(result) > 0 and len(terms) > 0:
        result = intersection(result, posting[terms[0]])
        terms = terms[1:]
    return result

함수 실행

자, 필요한 함수를 모두 정의했으니 이번엔 실행을 해보도록 하겠습니다. 실행 코드는 다음과 같습니다.

import time

# indexing
docfreq, posting = make_index(corpus)

# processing start
start_time = time.time()

# processing
result = search(query=['영화','재미','깨알'],
                docfreq=docfreq,
                posting=posting)

# processing end
end_time = time.time()

# print processing time
print(end_time - start_time)
print(result)

실행 결과는 다음과 같습니다. 간단한 검색어, 검색 대상이 72여만 건에 불과한데도 제 맥북(2015-early 13인치)에서 무려 125초 넘게 걸리네요ㅠㅠ 다음 글에서 이를 개선해보도록 하겠습니다.

125.26901292800903 [430144, 541361, 708930]

그럼 결과가 잘 나왔는지 해당 문서 내용을 살펴보겠습니다. 다음과 같습니다.

Doc 430144 : 깨알 같은 재미 어느 하나 허투인 것이 없는 웨스 앤더슨 식 영화 Doc 541361 : 깨알 대사 재미 남자임에도 여주인공에게 몰입할 수 있도록 도와주는 연기 생각할 수 있게 하는 영화 또 볼래요 Doc 708930 : 간만에 내 취향의 영화 발견 순수하고 귀여운 캐릭터와 적절한 감동 깨알 재미 배려깊은 결말까지 모두 맘에 들었다 홍영신님과 함께

Comments