문서 군집화

문서 군집화는 내용이 비슷한 문서끼리 묶어 줍니다. 어떤 묶음을 만들지 미리 알려 주지 않아도 됩니다. 문서끼리 얼마나 닮았는지만 보고 묶음을 스스로 찾습니다. 쌓인 글에 어떤 주제들이 들어 있는지 한눈에 보려고 씁니다.

쉽고 빠른 이해

문서 군집화는 글 더미를 비슷한 글끼리 몇 묶음으로 나눠 줍니다. 뉴스 기사를 넣으면 축구 기사끼리, 주식 기사끼리 한 묶음이 됩니다.

이게 없으면 사람이 글을 하나하나 읽고 나눠야 합니다. 어떤 주제가 들었는지 모를 때는 나눌 기준부터 세우기 어렵습니다.

1. 글마다 어떤 낱말이 얼마나 두드러지는지를 숫자 목록으로 바꿉니다
2. 숫자 목록이 닮은 글끼리 가깝다고 봅니다
3. 가까운 글끼리 묶습니다. 묶음이 더 안 바뀔 때까지 고쳐 나눕니다

대가도 있습니다. 묶음을 몇 개로 나눌지는 대개 사람이 정합니다. 묶음에 이름이 안 붙어서 사람이 읽고 지어야 합니다. 잘 나눴는지 채점할 정답도 없습니다.

주제 목록이 이미 정해져 있고 정답을 붙인 예시가 있으면 이 방법을 쓰지 않습니다. 정해 둔 목록에서 하나를 골라 붙이는 분류를 씁니다.

상세

문서 군집화(document clustering)는 문서 모음을 받아 문서마다 어느 묶음에 드는지를 돌려주는 작업입니다. 많은 방법은 묶음을 몇 개 만들지도 함께 받습니다. 묶음 하나를 군집 또는 클러스터(cluster)라고 부릅니다.

나누는 기준은 하나입니다. 같은 묶음 안의 문서끼리는 많이 닮아야 합니다. 다른 묶음의 문서와는 덜 닮아야 합니다.

기사 여섯 개가 있다고 해 봅시다. 셋은 축구 이야기입니다. 나머지 셋은 주식 이야기입니다. 문서 군집화는 이 여섯을 받아 축구 셋과 주식 셋을 두 묶음으로 돌려줍니다. 「축구」나 「주식」 같은 묶음 이름은 알려 주지 않습니다.

비슷한 것끼리 묶는 일은 글이 아니어도 합니다. 고객이나 사진을 묶는 일까지 넓게 부르는 이름이 군집화입니다. 문서 군집화는 그 대상이 글인 경우입니다. 글은 바로 비교할 수 없어서 숫자로 바꾸는 단계가 앞에 붙습니다.

한 번 돌리는 흐름

문서 군집화는 다섯 단계로 돕니다.

flowchart TD
    A["문서 모음"] --> B["낱말로 쪼갠다"]
    B --> C["문서마다 벡터를 만든다"]
    C --> D["벡터 길이를 1 로 맞춘다"]
    D --> E["가까운 벡터끼리 묶는다"]
    E --> F["묶음마다 대표 낱말을 뽑는다"]

맨 아래 단계는 사람을 돕는 단계입니다. 묶음에 이름이 없으니 대표 낱말을 보고 사람이 이름을 짓습니다.

분류와 가르는 선

문서 군집화와 가장 헷갈리는 작업은 분류입니다. 분류는 미리 정해 둔 목록에서 하나를 골라 문서에 붙입니다. 메일을 「스팸」과 「정상」 중 하나로 가르는 일이 분류입니다.

분류를 하려면 정답이 붙은 예시가 필요합니다. 사람이 「이 메일은 스팸」이라고 적어 둔 메일 수천 통으로 먼저 학습시킵니다. 정답이 붙은 예시로 배우는 방식을 지도학습이라고 부릅니다.

문서 군집화에는 정답이 없습니다. 문서들만 보고 그 안에 있는 무리를 찾습니다. 정답 없이 데이터에서 구조를 찾는 방식을 비지도학습이라고 부릅니다.

두 작업을 나란히 놓으면 아래와 같습니다.

표의 마지막 줄이 문서 군집화를 쓰는 큰 이유입니다. 무엇이 들었는지 모르는 문서 더미를 처음 열어 볼 때 쓸 수 있습니다.

정답 없이 묶는 까닭

분류에 쓸 정답을 붙이려면 사람이 문서를 읽어야 합니다. 문서가 수십만 개면 그 비용이 큽니다. 문서 군집화는 이 비용 없이 첫 나눔을 얻습니다.

주제 목록 자체를 모를 때도 있습니다. 고객 문의를 모아 두었습니다. 그런데 어떤 불만이 많은지 모르는 경우입니다. 먼저 묶어 보면 「배송 지연」이나 「환불 절차」 같은 무리가 드러납니다.

드러난 무리는 다음 일의 출발점이 됩니다. 사람이 무리마다 이름을 붙이면 그 이름이 분류의 목록이 됩니다. 이름 붙은 문서들은 분류기의 학습 예시가 됩니다.

문서를 벡터로 바꾸기

컴퓨터는 글 두 개를 그대로 놓고 얼마나 닮았는지 잴 수 없습니다. 그래서 글을 숫자 목록으로 바꿉니다. 순서를 정해 늘어놓은 숫자 목록을 벡터라고 부릅니다.

먼저 글을 낱말로 쪼갭니다. 이 일을 토큰화라고 부릅니다. 낱말 단위로 쪼개야 낱말마다 수를 셀 수 있습니다.

「그리고」「하지만」처럼 어느 글에나 나오는 낱말은 이때 빼기도 합니다. 이렇게 빼는 낱말을 불용어라고 합니다. 어느 글에나 나오니 주제를 가르는 데 도움이 안 됩니다.

다음으로 문서 모음에 나온 낱말마다 칸을 하나씩 둡니다. 문서 하나는 칸마다 숫자를 적은 벡터가 됩니다. 이 방식을 벡터 공간 모델이라고 부릅니다.

칸 하나를 축 하나로 놓으면 벡터는 한 점이 됩니다. 칸마다 적힌 숫자가 그 점의 좌표입니다. 칸이 둘이면 가로축과 세로축이 있는 평면 위의 점입니다. 원점에서 그 점까지 화살표를 그으면 벡터마다 가리키는 방향이 생깁니다.

벡터의 칸 수를 차원이라고 부릅니다. 칸이 둘이면 2차원 평면의 점입니다. 칸이 셋이면 3차원 공간의 점입니다. 칸이 수만 개여도 같은 셈법으로 점과 방향을 따집니다.

칸에 적는 숫자로는 TF-IDF(Term Frequency-Inverse Document Frequency, 낱말 빈도-역문서 빈도)를 많이 씁니다. 이 문서에 자주 나오고 다른 문서에는 드문 낱말일수록 값이 큽니다. 모든 문서에 흔한 낱말은 값이 0 에 가깝습니다.

TF-IDF 를 쓰는 까닭은 흔한 낱말이 닮음을 부풀리기 때문입니다. 나온 횟수만 적으면 「방법」「사용」이 많은 글끼리 닮았다고 나옵니다. 주제와 상관없는 낱말이 묶음을 정하게 됩니다.

낱말 칸 대신 임베딩을 쓰기도 합니다. 임베딩은 많은 글로 미리 학습시킨 모델이 글의 뜻을 숫자 목록으로 옮긴 것입니다. 「자동차」와 「차량」처럼 글자가 달라도 뜻이 같으면 가까운 벡터가 나옵니다.

닮음을 재는 기준

두 문서 벡터가 얼마나 닮았는지는 대개 코사인 유사도로 잽니다. 코사인 유사도는 두 화살표가 가리키는 방향이 얼마나 같은지를 잽니다. 같은 방향이면 1 입니다. 직각으로 벌어지면 0 입니다. TF-IDF 처럼 음수가 없는 벡터에서는 값이 0 에서 1 사이에 듭니다.

방향을 보는 이유는 글의 길이 때문입니다. 축구 기사를 두 번 이어 붙이면 칸마다 숫자가 두 배가 됩니다. 점은 원점에서 두 배 먼 곳으로 옮겨 갑니다.

그래도 칸끼리의 비율은 같으니 화살표의 방향은 그대로입니다. 코사인 유사도는 두 글을 같은 주제로 봅니다.

묶는 알고리즘 중에는 방향 대신 두 점 사이의 직선거리를 쓰는 것이 많습니다. 이 거리를 유클리드 거리라고 부릅니다. 직선거리로 재면 두 번 이어 붙인 기사는 원래 기사와 멀리 떨어진 점이 됩니다.

벡터의 길이는 원점에서 그 점까지의 직선거리입니다. 두 번 이어 붙인 축구 기사는 길이도 두 배입니다.

직선거리와 방향의 차이는 벡터의 길이를 모두 1 로 맞추면 사라집니다. 이 일을 길이 정규화라고 합니다. 길이를 1 로 맞추면 두 번 이어 붙인 기사도 원래 기사와 같은 점에 놓입니다.

길이가 1 인 벡터끼리는 두 잣대가 같은 순서를 냅니다. 직선거리가 가까운 쌍일수록 코사인 유사도가 큽니다. 덕분에 길이를 맞춘 뒤에는 직선거리를 쓰는 알고리즘으로도 방향을 비교한 결과가 나옵니다.

k-평균 군집화로 묶는 절차

문서를 묶는 가장 기본적인 알고리즘은 k-평균 군집화입니다. k 는 만들 묶음의 수입니다. 사람이 미리 정합니다.

묶음마다 중심점을 하나 둡니다. 중심점은 묶음의 한가운데 점입니다. 그 묶음에 든 문서 벡터들의 평균입니다. 칸마다 값을 더해 문서 수로 나눕니다.

문서는 가장 가까운 중심점의 묶음에 붙습니다. 절차는 아래 네 단계입니다.

1. 중심점 k 개를 고릅니다. 문서 k 개를 무작위로 뽑아 그 벡터를 첫 중심점으로 쓰는 방법이 기본입니다
2. 문서마다 가장 가까운 중심점을 찾아 그 묶음에 넣습니다
3. 묶음마다 문서 벡터의 평균을 구해 새 중심점으로 삼습니다
4. 2 와 3 을 되풀이합니다. 묶음을 옮긴 문서가 하나도 없으면 멈춥니다

flowchart TD
    S["중심점 k 개를 고른다"] --> A["문서마다 가장 가까운 중심점의 묶음에 넣는다"]
    A --> M["묶음마다 평균을 내어 새 중심점으로 삼는다"]
    M --> Q{"묶음을 옮긴 문서가 있나"}
    Q -- "있다" --> A
    Q -- "없다" --> E["멈춘다"]

여섯 문서로 따라가 보기

앞의 기사 여섯 개로 절차를 돌려 봅니다. 칸은 「축구」와 「주식」 둘만 둡니다. 계산을 쉽게 하려고 길이 맞추기는 건너뜁니다. 나온 횟수를 그대로 점의 좌표로 씁니다.

k 는 2 입니다. 첫 중심점으로 A 와 B 를 뽑았다고 합시다. 둘 다 축구 기사라서 시작이 한쪽으로 쏠렸습니다.

아래 표는 한 줄이 한 번의 되풀이입니다. 왼쪽 중심점으로 문서를 나눕니다. 나눈 묶음의 평균이 오른쪽 새 중심점입니다.

1회에서는 C 부터 F 까지가 전부 B 쪽에 붙습니다. A 보다 B 가 조금이라도 가깝기 때문입니다. 그 결과 묶음 2 의 중심점이 주식 쪽인 (1.6, 2.6) 으로 끌려갑니다.

2회에서는 끌려간 중심점 덕분에 B 와 C 가 A 쪽으로 넘어옵니다. 축구 셋과 주식 셋이 갈립니다. 3회에서는 옮긴 문서가 없어서 멈춥니다.

시작이 결과를 바꾸는 문제

위 예에서는 쏠린 시작이 되풀이 중에 바로잡혔습니다. 늘 그렇지는 않습니다. 첫 중심점에 따라 다른 나눔에서 멈추기도 합니다.

k-평균은 매 단계 조금씩 나아지는 쪽으로만 움직입니다. 그러다 더 나아질 수 없는 나눔을 만나면 멈춥니다. 그 나눔이 가능한 나눔 중 가장 나은 것이라는 보장은 없습니다. 이런 나눔을 국소 최적해라고 부릅니다.

많이 쓰는 대처는 둘입니다. 첫째는 첫 중심점을 바꿔 여러 번 돌리고 가장 잘 모인 결과를 고르는 것입니다. 둘째는 첫 중심점을 서로 멀리 떨어지게 뽑는 것입니다. 둘째 방법을 k-평균++라고 부릅니다.

묶음 수 고르기

k-평균은 k 를 받아야 돌기 시작합니다. 문서 더미를 처음 열 때는 주제가 몇 개인지 모릅니다. 그래서 k 를 여러 값으로 바꿔 돌립니다. 그 결과들을 비교합니다.

비교할 때 자주 보는 값이 클러스터 내 제곱합입니다. 문서마다 자기 중심점까지 거리를 제곱해 모두 더한 값입니다. 문서가 중심점에 촘촘히 모일수록 작아집니다.

이 값은 k 를 늘리면 계속 줄어듭니다. 묶음을 문서 수만큼 만들면 0 이 됩니다. 그래서 값이 가장 작은 k 를 고르지 않습니다.

대신 k 를 늘려도 값이 별로 안 줄기 시작하는 지점을 고릅니다. 이 방법을 엘보 방법이라고 부릅니다.

실루엣 계수를 보기도 합니다. 문서마다 자기 묶음과 얼마나 가까운지 잽니다. 가장 가까운 남의 묶음과 얼마나 먼지도 잽니다. 이 둘을 -1 에서 1 사이 값 하나로 냅니다.

1 에 가까울수록 제 묶음에 잘 들어간 문서입니다. 0 근처면 두 묶음 사이 경계에 걸친 문서입니다. 음수면 남의 묶음에 더 가깝다는 뜻입니다.

다른 묶는 방식

k-평균 말고도 문서를 묶는 알고리즘이 여럿 있습니다. 그중 셋을 봅니다.

계층적 군집화는 문서 하나하나를 묶음 하나로 놓고 출발합니다. 가장 가까운 두 묶음을 합치는 일을 묶음이 하나 남을 때까지 되풀이합니다. 합친 순서가 나무 모양으로 남습니다.

이 나무를 덴드로그램이라고 부릅니다. 합친 차례가 늦을수록 나무 위쪽에 그려집니다. 어느 높이에서 가로로 자르면 그 아래 남은 가지 수가 묶음 수가 됩니다.

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 문서가 빽빽하게 모인 영역을 묶음으로 봅니다. 반경과 그 안에 들어야 할 최소 이웃 수를 받습니다. 어디에도 빽빽하게 끼지 못한 문서는 외톨이로 남깁니다.

토픽 모델링은 문서 하나가 여러 주제에 걸친다고 봅니다. 결과는 「축구 70, 주식 30」처럼 주제마다 비율로 나옵니다.

토픽 모델링의 대표 방법이 잠재 디리클레 할당(Latent Dirichlet Allocation, LDA)입니다. 주제마다 잘 나오는 낱말이 따로 있다고 봅니다. 문서에 든 낱말을 보고 그 문서의 주제 비율을 거꾸로 추정합니다.

셋을 k-평균과 함께 놓으면 아래와 같습니다.

계산에 드는 비용

k-평균의 한 번 되풀이는 모든 문서를 모든 중심점과 비교합니다. 비교할 때마다 칸을 전부 봅니다.

일의 양은 O(…) 표기로 적습니다. 괄호 안에 일의 양이 무엇에 비례하는지를 씁니다.

문서 수를 n, 묶음 수를 k, 칸 수를 d 라고 하면 한 번에 O(n·k·d) 만큼 일합니다. 셋 중 하나가 두 배가 되면 일도 두 배가 됩니다.

되풀이 횟수를 t 라고 하면 전체는 O(n·k·d·t) 입니다. t 가 얼마가 될지는 문서마다 달라서 미리 정해지지 않습니다. 되풀이 횟수에 상한을 두기도 합니다. 그 횟수에 닿으면 멈춥니다.

가장 잘 모인 나눔을 반드시 찾는 문제는 훨씬 어렵습니다. 문서가 늘면 따져 볼 나눔의 수가 폭발적으로 늘어납니다. 이 문제를 빠르게 푸는 방법은 알려져 있지 않습니다. k-평균이 국소 최적해에서 멈추는 것을 받아들이는 까닭입니다.

계층적 군집화는 모든 문서 쌍의 거리를 알아야 합니다. 쌍의 수는 문서 수의 제곱에 비례합니다. 그래서 그 거리를 담아 두는 데 O(n²) 만큼 메모리를 씁니다. 문서가 10만 개면 쌍이 약 50억 개입니다. 시간은 그보다 더 듭니다.

차원이 높아서 생기는 문제

낱말마다 칸을 두면 차원이 수만 개가 됩니다. 문서 하나에 든 낱말은 수백 개라서 칸 대부분이 0 입니다. 이렇게 거의 0 으로 찬 벡터를 희소 벡터라고 합니다. 0 인 칸은 곱해도 0 이라 계산에서 건너뛸 수 있습니다.

중심점은 이야기가 다릅니다. 여러 문서의 평균이라 문서마다 다른 낱말 칸이 한꺼번에 찹니다. 중심점은 칸 대부분에 값이 있는 벡터가 됩니다. 건너뛸 0 이 적으니 문서와 비교하는 계산이 늘어납니다.

차원이 높으면 거리 자체도 믿기 어려워집니다. 차원이 커질수록 어느 두 점을 골라도 거리가 비슷비슷해지는 경향이 있습니다. 가까운 것과 먼 것의 차이가 흐려지는 이 현상을 차원의 저주라고 부릅니다.

이를 피하려고 묶기 전에 차원을 줄이기도 합니다. 잠재 의미 분석(Latent Semantic Analysis, LSA)은 문서와 낱말의 표를 압축해 차원을 수백 개로 줄입니다. 자주 함께 나오는 낱말이 같은 칸으로 모입니다. 임베딩을 쓰면 처음부터 수백 차원짜리 벡터를 얻습니다.

묶음에 이름 붙이기와 결과 판단

문서 군집화가 돌려주는 것은 묶음 번호뿐입니다. 번호 3 이 무슨 주제인지는 사람이 알아내야 합니다. 자주 쓰는 방법은 중심점에서 값이 가장 큰 낱말 몇 개를 뽑아 보는 것입니다.

중심점의 큰 값은 그 묶음 문서들에 공통으로 많이 나온 낱말입니다. 「골 · 감독 · 경기」가 뽑히면 사람이 그 묶음에 「축구」라는 이름을 붙입니다. 이렇게 낱말을 뽑는 일을 키워드 추출이라고 합니다.

결과가 맞았는지 채점할 정답은 없습니다. 실루엣 계수처럼 묶음 모양만 보고 재는 값이 있습니다. 결국 묶음마다 문서 몇 개를 사람이 읽어 보고 판단하는 일이 따라붙습니다.

같은 문서 더미라도 k 나 첫 중심점, 벡터를 만드는 방식을 바꾸면 결과가 달라집니다. 정답이 하나인 작업이 아니라서 어느 결과도 틀렸다고 말하기 어렵습니다. 쓰려는 목적에 맞게 나뉘었는지가 기준이 됩니다.

쓸 때와 안 쓸 때

문서 군집화는 무엇이 들었는지 모르는 더미를 처음 훑을 때 씁니다. 고객 문의나 설문 응답을 주제별로 나눠 보는 일이 그렇습니다. 같은 사건을 다룬 뉴스 기사를 한데 모으는 데도 씁니다.

검색 결과를 묶어 보여 주는 데도 씁니다. 「자바」로 찾았을 때 프로그래밍 언어 이야기와 섬 이야기를 따로 묶으면 사용자가 원하는 쪽을 고르기 쉽습니다.

주제 목록이 이미 정해져 있고 정답 붙은 예시가 있으면 분류를 씁니다. 문서 군집화는 묶음 이름을 모릅니다. 결과도 돌릴 때마다 달라질 수 있습니다. 목록이 정해진 일에는 분류가 결과를 더 일정하게 냅니다.

똑같은 문서를 찾는 일에는 군집화가 필요 없습니다. 내용 전체를 해시값으로 바꿔 비교하면 됩니다. 몇 글자만 다른 문서를 찾는 일은 근접 중복 탐지라는 이름으로 따로 다룹니다.

관련 항목

문서 군집화가 속하는 상위 분류

군집화 · 군집 분석 · 비지도학습 · 머신러닝 · 자연어 처리 · 텍스트 마이닝 · 정보 검색

문서를 벡터로 바꾸는 앞 단계

토큰화 · 불용어 · 어간 추출 · 형태소 분석 · 벡터 공간 모델 · TF-IDF · 단어 가방 모델 · 문서-용어 행렬 · 임베딩

문서 사이의 닮음을 재는 척도

코사인 유사도 · 유클리드 거리 · 내적 · 길이 정규화 · 자카드 유사도

문서를 묶는 알고리즘

k-평균 군집화 · k-평균++ · 계층적 군집화 · 단일 연결 군집 · DBSCAN · 토픽 모델링 · 잠재 디리클레 할당

묶음 수를 고르고 묶음 모양을 재는 지표

클러스터 내 제곱합 · 엘보 방법 · 실루엣 계수 · 중심점 · 덴드로그램

벡터 칸이 많아서 생기는 문제와 칸을 줄이는 방법

희소 벡터 · 밀집 벡터 · 차원의 저주 · 차원 축소 · 잠재 의미 분석

정답 붙은 예시로 문서를 나누는 대립 작업

분류 · 텍스트 분류 · 지도학습 · 스팸 필터 · 라벨

문서 군집화를 쓰는 텍스트 작업

검색 · 검색 결과 군집화 · 근접 중복 탐지 · 유사 문서 검색 · 추천 시스템 · 키워드 추출