8 min to read

Search Results clustering Engine, carrot2

Solr에서 사용할 수 있는 Search Results Clustering Engine인 carrot2 에 대해 팀내 스터디 진행하였습니다. 공부한 내용을 정리해서 작성해봤습니다. 내용은 carrot2의 소개와 carrot2에서 사용하는 clustering algorithm 중 하나인 Lingo algorithm 을 중심으로 작성하였습니다.

클러스터링이란?

먼저 carrot2를 설명하기 전에, 클러스터링(Clustering)이 무엇인지 간단하게 알아보겠습니다. 클러스터링은 비슷한 특성이 있는 데이터들의 집단을 만드는 작업입니다. Classification과 비슷해 보일 수 있으나 다른 개념입니다. 클러스터링은 사전 정보가 없는 데이터들을 유사도를 측정하여 비슷한 데이터를 찾아 그룹으로 만드는 개념이고 Classification은 분류해야 하는 특성을 미리 알고 있는 상태에서 데이터를 그룹화하는 개념입니다.

clustering

Solr란?

solr는 오픈소스 검색 라이브러리, Lucene을 기반으로 동작하는 검색플랫폼입니다. carrot2는 사용자가 검색한 결과 문서들을 클러스터링합니다. 즉 어떤 검색결과 문서들이 input으로 주어져야 합니다. 그러기 위해서 다양한 방법이 있지만, 이번 스터디에서는 solr를 사용했습니다.

solr search solr에서 검색의 과정은 위 그림처럼 이루어집니다. 검색요청이 들어오면 각 component들을 차례로 거치면서 결과를 만들어 갑니다. last component에 클러스터링을 담당하는 작업을 추가하면 검색 결과 클러스터링이 가능하게 됩니다.

solr에 대해 더 자세히 알고 싶으면 solr reference guide에서 확인하실 수 있습니다.

Carrot2

그럼 이제 클러스터링과 solr에 대해 간략하게 알아봤으니, 본격적으로 carrot2에 대해 이야기해보겠습니다.

carrot2는 검색결과를 클러스터링해서 결과를 보여주는 데, 기존의 검색결과와는 무엇이 다른지 아래 그림을 보겠습니다.

Introduction to search results clustering 기존의 검색 결과는 특정한 랭킹알고리즘을 통해 결과를 보여줍니다. 예를 들어 검색 사이트에 apache 라는 단어를 검색하면 apache 재단에 관련된 문서가 주로 상위에 보입니다. apache 헬리콥터나 인디언에 관련된 문서들도 있는데 상위에 보이지 않으므로 관련 문서를 사용자 입장에서는 찾기가 쉽지 않을 수 있습니다.
하지만 검색결과를 클러스터링해서 비슷한 문서끼리 그룹화한다면, 좀 더 검색 결과를 직관적으로 보여줄 수 있을 것입니다. 위 그림의 왼쪽은 기존의 검색 결과이고 오른쪽은 검색결과를 클러스터링한 결과입니다.

데모사이트에서 검색을 통해 직접 확인해 볼 수도 있습니다.

solr search carrot2구조는 위와 같습니다. input으로는 검색 결과가 들어오고, filter에서 클러스터링 알고리즘을 통해 비슷한 문서들끼리 클러스터를 만들게 됩니다. 생성된 클러스터들이 output이 됩니다.

Solr에서 Carrot2 이용해 간단한 검색하기

우선 solr에서 carrot2를 사용하기 위해서는 solrconfig.xml에 아래와 같이 설정을 해야 합니다.

<lib dir="${solr.install.dir:../../..}/contrib/clustering/lib/" regex=".*\.jar" />
<lib dir="${solr.install.dir:../../..}/dist/" regex="solr-clustering-\d.*\.jar" />

<searchComponent name="clustering" class="solr.clustering.ClusteringComponent">
  <lst name="engine">
    <str name="name">lingo</str>
    <str name="carrot.algorithm">org.carrot2.clustering.lingo.LingoClusteringAlgorithm</str>
  </lst>

  <lst name="engine">
    <str name="name">stc</str>
    <str name="carrot.algorithm">org.carrot2.clustering.stc.STCClusteringAlgorithm</str>
  </lst>
</searchComponent>
  • 미리 정의되어있는 알고리즘
    • LingoClusteringAlgorithm (open source)
    • STCClusteringAlgorithm (open source)
    • BisectingKMeansClusteringAlgorithm (open source)
    • Lingo3GClusteringAlgorithm (commercial)

위와 같이 미리 정의 되어있는 클러스터링 알고리즘을 carrot.algorithm 값으로 사용하면 됩니다. name은 엔진을 구별하기 위해 정의합니다.
나열된 알고리즘 중 Lingo3GClusteringAlgorithm 는 open source가 아니므로 CarrotSearch에서 구매하여 확인할 수 있습니다.

URL 파라미터로 clustering.engine=(engine name) 로 설정합니다. 엔진을 선택하여 위에 선언한 알고리즘으로 클러스터링을 진행하게 됩니다. clustering.engine 파라미터를 입력하지 않으면, 제일 먼저 선언한 엔진이 default로 설정됩니다.

<requestHandler name="/clustering"
                class="solr.SearchHandler">
  <lst name="defaults">
    <bool name="clustering">true</bool>
    <bool name="clustering.results">true</bool>

    <str name="carrot.title">title</str>
    <str name="carrot.snippet">content</str>

    <str name="fl">*,score</str>
  </lst>

  <arr name="last-components">
    <str>clustering</str>
  </arr>
</requestHandler>
Parameter Description
carrot.title 문서의 제목에 해당하는 필드를 지정, snippet으로 지정한 필드보다 더 높은 가중치를 줌
carrot.snippet 문서의 내용에 해당하는 필드를 지정

더 자세한 파라미터와 설명은 solr reference guide에서 확인할 수 있습니다.

example

아래 그림은 테스트 데이터에 위와 같이 검색한 결과의 일부입니다. 결과를 통해 클러스터가 생성된 것을 확인할 수 있습니다.

test 클러스터는 <lst>로 감싸져 있습니다. 상위에서 클러스터를 색으로 구분했다면, 여기선 레이블로 구분합니다. 총 3개의 클러스터가 생성된 것을 볼 수 있습니다. <arr name="docs"> 밑에는 해당 클러스터에 속하는 문서들이 나열되어 있습니다.

아래 그림을 통해, 결과를 직관적으로 이해할 수 있습니다. <str>태그 안에는 문서의 unique key 값이 나타납니다. 아래 그림에서는 문서의 unique key 값이 길어 축약하여 표현하였습니다. detail test result

Lingo algorithm

Lingo 알고리즘은 carrot2를 만든 Stanisław Osiński가 만든 알고리즘입니다. 그는 Lingo 알고리즘이 다른 클러스터링 알고리즘과 차이점이 있다고 합니다.

clustering process

다른 대다수의 클러스터링 알고리즘은 위 그림 좌측에 있는 구조처럼 먼저 문서들간의 유사도를 비교하여 클러스터를 우선 만듭니다. 그 후 클러스터 대표할 단어를 찾아 결과를 반환합니다.
Lingo 알고리즘은 위 그림 우측에 해당하는 방법을 사용합니다. 클러스터를 만드는 일보다 먼저 문서들을 비교하여 레이블을 찾습니다. 레이블은 사용될 클러스터를 대표하는 단어및 구문이 됩니다. 즉, 클러스터를 단어 및 구문을 우선 찾는 방법입니다. 그 후, 문서들을 찾은 레이블들과 비교하여 어울리는 레이블에 문서를 넣습니다.

Lingo 알고리즘은 다섯단계로 진행됩니다.

  1. Preprocessing
  2. Feature extraction
  3. Cluster label induction
  4. Cluster content discovery
  5. Final cluster formation

단계별로 간단하게 살펴보겠습니다.

마무리

지금까지 carrot2에 대해 알아보았습니다. carrot2는 사용하기도 용이하고 꽤 괜찮은 결과를 보여주는 것 같아 보였습니다. 하지만 결과와 성능 측면에서 개선해야 할 점이 보였습니다.

1.결과

결과는 label로 선정된 구문에 대한 이야기입니다.
unexpected label 위 그림은 apache 로 검색한 결과 중 생긴 클러스터입니다. 위 그림 우측은 stopwords.ko 파일 일부입니다. 파일 안에 할 수 있는이 들어 있지 않은 것을 확인할 수 있습니다. 이렇듯 stopwords.ko 파일에 등록되어 있지 않은 불용어로 시작하거나 끝나는 구문이 label로 지정되는 경우가 종종 생겼습니다. 할 수 있는이 apache 로 검색한 결과 내에서 의미 있는 구문은 아니기에 원하지 않는 결과입니다.

2.성능

검색 수행 사용자 테스트 진행 시간
40 30min

위와 같은 조건에서 기존 검색 과 carrot2의 Lingo 알고리즘을 이용한 검색 , 총 두 가지 검색을 검색반환 문서 수(10, 20) 에 따라 진행하였습니다.
아래 그래프는 테스트에 관한 결과를 TPS(transaction per second) 그래프 입니다. x축은 경과 시간(초)을 나타내고 y축은 TPS를 나타냅니다. TPS는 초당 transaction을 처리한 수를 나타내는 데, 이 테스트에서 transaction은 검색하고 결과를 반환받는 과정을 말합니다. 즉 TPS가 높을수록 성능이 좋다고 말할 수 있습니다.

performance test 그래프에는 총 4가지 선이 존재합니다. default는 기존 검색을 의미하고, Lingo는 carrot2를 이용한 검색을 의미합니다. row는 검색 반환 문서의 수를 의미합니다. Lingo 알고리즘에서 검색반환 수가 25인 경우가 가장 낮은 TPS를 보이는 것을 확인할 수 있습니다.

  Lingo / row=25 Lingo / row=10 default / row=25 default / row=10
평균 응답 시간 (ms) 283.4 133.1 48.5 40.7
평균 TPS 140.9 299.9 820.7 977.3

테스트를 통해 carrot2를 이용한 검색이 기존의 검색보다 성능이 낮은 것을 확인했습니다.

검색에서 실시간 클러스터링을 사용하기 위해서는 정확도와 응답속도 개선이 필요해 carrot2의 대대적인 커스터마이징이 필요할 것으로 판단됩니다.

참고