검색과 클러스터링

클러스터링에 대한 공부는 예전에 k-means 알고리즘을 이용한 음성데이터 클러스터링을 마지막으로 손을 가져가지 않았다가, 이번에 이런저런 책을 보면서 클러스터링에 대한 공부를 해봤다.

검색엔진이 왜 클러스터링과 관련이 있는지 알아보자!

컬렉션이 잘 클러스터링 되어 있다면, 그 해당 클러스터만을 검색해서 문서를 찾아내는것이 더 효과적이다.

이런 효과적인 성능에 비해 크러스터링은 일반적인 검색엔진에 쓰이기 힘든 factor가 있다.

1. 문서 집합에 대해서 클러스터링을 했을경우 그 클러스터가 어떤 쿼리에 관계가 있는지 모호하다.
2. 클러스터링 복잡도가 매우높다. (N * N의 유사도 매트릭스를 사용할 경우 매 클러스터링을 수행할 경우 O(n^2)). 요즘 문서셋이 굉장히 크다는걸 감안할때 상당할 것이다.

이런 한계 때문에 일반적으로 결과셋의 클러스터링에 클러스터링 알고리즘들이 사용된다.

그럼 이런 클러스터링은 어떤 방식으로 수행이 될까?

1. 결과셋의 문서들을 파싱해서 구(단어들의 집합)를 뽑아낸다.
2. 학습 알고리즘으로 학습된 모델에 이 문서 단위의 구를 입력해서 Key가 되는 구를 찾아낸다.(linear regression, logistic regression, support vector regression 등등)
3. 그 키를 이용해 포함된 문서를 초기 클러스터링 한다.
3.1 예를 들어 키 구로 “수도 서울”이 포함된 문서는 같은 클러스터로 분류되서 초기화 된다.
4. 초기 클러스터를 기반으로 문서 대 문서간의 유사도를 이용해 merge 작업을 한다.

그러니까 위의 merge작업을 클러스터 집합에 대한 트리로 만들어서 그 트리를 검색 결과에 보여주면 되는 것이다.

몇몇 클러스터링 알고리즘이 존재한다.

1. Hierarchical Agglomerative Clustring 알고리즘
2. Partitioning(Iterative) 기반의 알고리즘 (one-pass, BuckShot, K-means)

위의 두가지 알고리즘 셋의 차이점은 기 계산된 문서-문서 쌍의 유사도 matrix를 가지고 있느냐 아니느냐의 것이다.

Hierarchical Agglomerative Clustring 알고리즘

1. 유사도가 가장 높은 클러스터 2개를 선택한다.
2. 두 클러스터를 merge하고 유사도 matrix를 재계산 한다.(n번의 계산 필요)

위의 1,2번 과정을 오직 하나의 클러스터가 될때까지 계속 한다.
여기서 merge된 cluster의 유사도를 정하는것은 통상 3가지의 식이 사용된다.

1. Single Link
2. Complete Linkage
3. Group Average

Single Link : 두 클러스터 사이의 문서쌍중에 가장 큰 값을 취하는 방법
Complete Linkage : 두 클러스터 사이의 문서쌍중에 가장 작은 값을 취하는 방법
Group Average : 두 클러스터내의 문서쌍 유사도의 평균값

이런 방식으로 유사도 매트릭스를 업데이트 해가면서 클러스터링을 수행하고 그 클러스터링 결과를 트리 형식의 Bottum-Up 방식으로 구성해서 검색엔진 쿼리 프로세싱에 사용을 하게 된다.

그러나 이 방법은 검색 결과를 보기까지 너무 많은 복잡도를 요구한다.
이 알고리즘은 O(n^2)의 복잡도를 가지는 것으로 알려져 있다. (이것은 유사도 계산의 1회 계산에 포커싱이 맞춰진 복잡도 이다. 만일 유사도 계산의 세부 연산에 대한 복잡도를 계산하자면 이것은 정확한 것이 아닐 수 있다.)

그렇다고 매드릭스를 구성하지 않는 클러스터링 방법을 한다고 해서 복잡도 상으로 그렇게 효과적이지는 않다.

그래서 미리 클러스터링을 해놓은 문서집합을 사용해서 검색 결과를 보여주기도 한다.(몇몇의 국내 제품이 이런 방식을 사용하는것으로 알고 있다. 중요 키워드에 대해 말이다.)

검색결과 랭킹을 이런 방식으로 했었던 전의 첫눈이라는 검색엔진이 있었다. 상당히 유저에게 어필을 하는 구조였는데 지금은 그 모습을 보기 쉽지 않으니 좀 아쉽기도 하다.

실시간으로 검색 결과 클러스터링을 효율적으로 하는 구조는 있을까?  한번 찾아봄직 할거 같다.