<div id="readability-page-1" class="page"><article role="article" id="post" itemprop="articleBody">
 
 
 <svg id="date"><use xlink:href="#icon-calendar"></use></svg>
 <time itemprop="datePublished" datetime="2018-09-12T00:00:00+00:00">
 


September 12, 2018

 </time>
 
 <svg id="clock"><use xlink:href="#icon-clock"></use></svg>
 8 min to read
 
 
 <blockquote>
 Solr에서 사용할 수 있는 Search Results Clustering Engine인 carrot2 에 대해 팀내 스터디 진행하였습니다. 공부한 내용을 정리해서 작성해봤습니다. 내용은 carrot2의 소개와 carrot2에서 사용하는 clustering algorithm 중 하나인 Lingo algorithm 을 중심으로 작성하였습니다.
</blockquote>

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

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/clustering.png" alt="clustering">
<hr>

<h3 id="solr란">Solr란?</h3>
solr는 오픈소스 검색 라이브러리, <a href="http://lucene.apache.org/">Lucene</a>을 기반으로 동작하는 검색플랫폼입니다. carrot2는 사용자가 검색한 결과 문서들을 클러스터링합니다. 즉 어떤 검색결과 문서들이 input으로 주어져야 합니다. 그러기 위해서 다양한 방법이 있지만, 이번 스터디에서는 solr를 사용했습니다.

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/Solr_Search_request_handler.png" alt="solr search">
solr에서 검색의 과정은 위 그림처럼 이루어집니다. 검색요청이 들어오면 각 component들을 차례로 거치면서 결과를 만들어 갑니다. last component에 클러스터링을 담당하는 작업을 추가하면 검색 결과 클러스터링이 가능하게 됩니다. 

solr에 대해 더 자세히 알고 싶으면 <a href="https://lucene.apache.org/solr/guide/6_6/about-this-guide.html">solr reference guide</a>에서 확인하실 수 있습니다.
<hr>

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

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

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

<a href="http://search.carrot2.org/stable/search">데모사이트</a>에서 검색을 통해 직접 확인해 볼 수도 있습니다.

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/carrot_pipeline.png" alt="solr search ">
carrot2구조는 위와 같습니다. input으로는 검색 결과가 들어오고, filter에서 클러스터링 알고리즘을 통해 비슷한 문서들끼리 클러스터를 만들게 됩니다. 생성된 클러스터들이 output이 됩니다.

<hr>

<h4 id="solr에서-carrot2-이용해-간단한-검색하기">Solr에서 Carrot2 이용해 간단한 검색하기</h4>
<blockquote>
 우선 solr에서 carrot2를 사용하기 위해서는 <code>solrconfig.xml</code>에 아래와 같이 설정을 해야 합니다.
</blockquote>

<ul>
 <li>jar 포함시키기</li>
</ul>

<div><pre><code>&lt;lib dir="${solr.install.dir:../../..}/contrib/clustering/lib/" regex=".*\.jar" /&gt;
&lt;lib dir="${solr.install.dir:../../..}/dist/" regex="solr-clustering-\d.*\.jar" /&gt;
</code></pre></div>

<ul>
 <li>searchComponent 추가하기</li>
</ul>

<div><pre><code>&lt;searchComponent name="clustering" class="solr.clustering.ClusteringComponent"&gt;
 &lt;lst name="engine"&gt;
 &lt;str name="name"&gt;lingo&lt;/str&gt;
 &lt;str name="carrot.algorithm"&gt;org.carrot2.clustering.lingo.LingoClusteringAlgorithm&lt;/str&gt;
 &lt;/lst&gt;

 &lt;lst name="engine"&gt;
 &lt;str name="name"&gt;stc&lt;/str&gt;
 &lt;str name="carrot.algorithm"&gt;org.carrot2.clustering.stc.STCClusteringAlgorithm&lt;/str&gt;
 &lt;/lst&gt;
&lt;/searchComponent&gt;
</code></pre></div>

<blockquote>
 <ul>
 <li>미리 정의되어있는 알고리즘
 <ul>
 <li>LingoClusteringAlgorithm (open source)</li>
 <li>STCClusteringAlgorithm (open source)</li>
 <li>BisectingKMeansClusteringAlgorithm (open source)</li>
 <li>Lingo3GClusteringAlgorithm (commercial)</li>
 </ul>
 </li>
 </ul>
</blockquote>

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

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

<ul>
 <li>RequestHandler 만들기</li>
</ul>

<div><pre><code>&lt;requestHandler name="/clustering"
 class="solr.SearchHandler"&gt;
 &lt;lst name="defaults"&gt;
 &lt;bool name="clustering"&gt;true&lt;/bool&gt;
 &lt;bool name="clustering.results"&gt;true&lt;/bool&gt;

 &lt;str name="carrot.title"&gt;title&lt;/str&gt;
 &lt;str name="carrot.snippet"&gt;content&lt;/str&gt;

 &lt;str name="fl"&gt;*,score&lt;/str&gt;
 &lt;/lst&gt;

 &lt;arr name="last-components"&gt;
 &lt;str&gt;clustering&lt;/str&gt;
 &lt;/arr&gt;
&lt;/requestHandler&gt;
</code></pre></div>

<table>
 <thead>
 <tr>
 <th>Parameter</th>
 <th>Description</th>
 </tr>
 </thead>
 <tbody>
 <tr>
 <td><code>carrot.title</code></td>
 <td>문서의 제목에 해당하는 필드를 지정, snippet으로 지정한 필드보다 더 높은 가중치를 줌</td>
 </tr>
 <tr>
 <td><code>carrot.snippet</code></td>
 <td>문서의 내용에 해당하는 필드를 지정</td>
 </tr>
 </tbody>
</table>

더 자세한 파라미터와 설명은 <a href="https://lucene.apache.org/solr/guide/6_6/result-clustering.html">solr reference guide</a>에서 확인할 수 있습니다.

<ul>
 <li>검색결과 확인하기</li>
</ul>

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/example.png" alt="example ">

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

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/test-example.png" alt="test ">
클러스터는 <code>&lt;lst&gt;</code>로 감싸져 있습니다. 상위에서 클러스터를 색으로 구분했다면, 여기선 레이블로 구분합니다. 총 3개의 클러스터가 생성된 것을 볼 수 있습니다. <code>&lt;arr name="docs"&gt;</code> 밑에는 해당 클러스터에 속하는 문서들이 나열되어 있습니다. 

아래 그림을 통해, 결과를 직관적으로 이해할 수 있습니다. <code>&lt;str&gt;</code>태그 안에는 문서의 unique key 값이 나타납니다. 아래 그림에서는 문서의 unique key 값이 길어 축약하여 표현하였습니다.
<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/detail_result.png" alt="detail test result ">
<hr>

<h3 id="lingo-algorithm">Lingo algorithm</h3>
Lingo 알고리즘은 carrot2를 만든 <a href="https://carrotsearch.com/about-us/">Stanisław Osiński</a>가 만든 알고리즘입니다. 그는 Lingo 알고리즘이 다른 클러스터링 알고리즘과 차이점이 있다고 합니다.

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/clustering_process.png" alt="clustering process ">

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

Lingo 알고리즘은 다섯단계로 진행됩니다.
<ol>
 <li>Preprocessing</li>
 <li>Feature extraction</li>
 <li>Cluster label induction</li>
 <li>Cluster content discovery</li>
 <li>Final cluster formation</li>
</ol>

단계별로 간단하게 살펴보겠습니다.
<ul>
 <li>Preprocessing
 <ul>
 <li>문서의 언어를 판단하고, 어간 추출(stemming) 작업을 합니다.
 그리고 불용어(stop words)에 표시를 해둡니다. 한국어 불용어도 <code>stopwords.ko</code>라는 파일에 등록되어있습니다.</li>
 </ul>
 </li>
 <li>Feature extraction
 <ul>
 <li>문서내에 자주 사용되는 단어와 구문을 추출합니다. 추출한 단어들과 구문들은 레이블 후보가 됩니다. 구문을 발견하는 작업은 접미사 배열(Suffix array)을 이용합니다. 바로 전 단계에서 불용어를 삭제하지 않은 이유는 불용어가 구문을 이해하는 데 더 도움이 될 수 있기 때문입니다. 
구문 <code>Chamber Commerce</code>와 <code>Chamber of Commerce</code>를 비교해보면 <code>of</code>가 불용어지만 불용어를 제거하지 않은 후자가 더 이해하기 좋은 구문입니다. 
전 단계에서 삭제는 하지 않았지만, 불용어를 표시해둔 이유는 구문이 불용어로 시작하거나 끝나면 레이블로 사용하기에 적절하지 않기 때문입니다. 불용어로 시작하거나 끝나는 구문은 후보가 될 수 없습니다.</li>
 </ul>
 </li>
 <li>Cluster label induction
 
 </li>
 <li>Cluster content discovery
 <ul>
 <li>벡터 공간 모델을 이용해 검색결과 문서들을 클러스터에 할당합니다.</li>
 </ul>
 </li>
 <li>Final cluster formation
 <ul>
 <li>클러스터의 점수를 측정하고 병합해야될 클러스터는 병합을 합니다. 점수를 계산하는 방법은 아래와 같습니다. 
 cluster-score = label-score x member-count</li>
 </ul>
 </li>
</ul>

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

<h4 id="1결과">1.결과</h4>
결과는 label로 선정된 구문에 대한 이야기입니다. 
<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/unexpected_label.png" alt="unexpected label">
위 그림은 apache 로 검색한 결과 중 생긴 클러스터입니다. 위 그림 우측은 <code>stopwords.ko</code> 파일 일부입니다. 파일 안에 <code>할 수 있는</code>이 들어 있지 않은 것을 확인할 수 있습니다. 이렇듯 <code>stopwords.ko</code> 파일에 등록되어 있지 않은 불용어로 시작하거나 끝나는 구문이 label로 지정되는 경우가 종종 생겼습니다. <code>할 수 있는</code>이 apache 로 검색한 결과 내에서 의미 있는 구문은 아니기에 원하지 않는 결과입니다. 

<h4 id="2성능">2.성능</h4>

<table>
 <thead>
 <tr>
 <th>검색 수행 사용자</th>
 <th>테스트 진행 시간</th>
 </tr>
 </thead>
 <tbody>
 <tr>
 <td>40</td>
 <td>30min</td>
 </tr>
 </tbody>
</table>

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

<img src="https://zuminternet.github.io/images/search/post/2018-09-12-SearchResultsClustering/performance_test.png" alt="performance test">
그래프에는 총 4가지 선이 존재합니다. default는 기존 검색을 의미하고, Lingo는 carrot2를 이용한 검색을 의미합니다. row는 검색 반환 문서의 수를 의미합니다. Lingo 알고리즘에서 검색반환 수가 25인 경우가 가장 낮은 TPS를 보이는 것을 확인할 수 있습니다.

<table>
 <thead>
 <tr>
 <th>&nbsp;</th>
 <th>Lingo / row=25</th>
 <th>Lingo / row=10</th>
 <th>default / row=25</th>
 <th>default / row=10</th>
 </tr>
 </thead>
 <tbody>
 <tr>
 <td>평균 응답 시간 (ms)</td>
 <td>283.4</td>
 <td>133.1</td>
 <td>48.5</td>
 <td>40.7</td>
 </tr>
 <tr>
 <td>평균 TPS</td>
 <td>140.9</td>
 <td>299.9</td>
 <td>820.7</td>
 <td>977.3</td>
 </tr>
 </tbody>
</table>

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

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

<h3 id="참고">참고</h3>

<ul>
 <li><a href="https://en.wikipedia.org/wiki/Cluster_analysis">clustering</a></li>
 <li><a href="https://lucene.apache.org/solr/guide/6_6/result-clustering.html">solr reference guide</a></li>
 <li><a href="https://project.carrot2.org/">carrot2</a></li>
 <li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.5832&amp;rep=rep1&amp;type=pdf">AN ALGORITHM FOR CLUSTERING OF WEB SEARCH RESULTS</a></li>
</ul>

 </article></div>

ZUM 기술 블로그

Solr에서 사용할 수 있는 Search Results Clustering Engine인 carrot2 에 대해 팀내 스터디 진행하였습니다. 공부한 내용을 정리해서 작성해봤습니다. 내용은 carrot2의 소개와 carrot2에서 사용하는 clustering algorithm 중 하나인 Lingo algorithm 을 중심으로 작성하였습니다.
  
클러스터링이란?
 먼저 carrot2를 설명하기 전에, 클러스터링(Clustering)이 무엇인지 간단하게 알아보겠습니다. 클러스터링은 비슷한 특성이 있는 데이터들의 집단을 만드는 작업입니다. Classification과 비슷해 보일 수 있으나 다른 개념입니다. 클러스터링은 사전 정보가 없는 데이터들을 유사도를 측정하여 비슷한 데이터를 찾아 그룹으로 만드는 개념이고 Classification은 분류해야 하는 특성을 미리 알고 있는 상태에서 데이터를 그룹화하는 개념입니다.
 
  
Solr란?
 solr는 오픈소스 검색 라이브러리, Lucene을 기반으로 동작하는 검색플랫폼입니다....

Search Results clustering Engine, carrot<sup>2</sup>

댓글