이번 글에서는 문서 유사도를 측정하는 몇 가지 지표에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

유사도?

유사도(similarity)란 비슷한 정도를 나타내는 지표를 뜻합니다. 하지만 ‘비슷하다’는 단어의 어감에서도 알 수 있듯 굉장히 주관적인 지표입니다. 이를 정량화하는 노력이 필요한데요. 자연언어처리(Natural Language Processing) 분야에서 정의하는 유사도 지표의 속성 몇 가지를 나열해 보도록 하겠습니다.

(1) 두 객체간 유사성은 둘이 공유하는 속성이 많을 수록 증가한다.

(2) 개별 속성은 서로 독립(independent)이며, 추가가 가능하다.

(3) 각 속성이 갖는 추상화 레벨이 동일해야 한다.

(4) 유사성은 개념구조(conceptual structure)를 설명하는 데 충분해야 한다.

(1)은 직관적으로 이해가 가능할 것 같고요. (2)의 경우 예컨대 한 문서가 하나의 객체이고 이 문서가 5개 변수로 이뤄져 있다면 각 변수는 서로 무상관(uncorrelated)이라는 뜻이 됩니다. 이 문서를 벡터공간(vector space)에 표현했을 때 각 변수에 대응하는 기저(basis)는 서로 수직이라는 말로도 이해할 수 있을 것 같습니다. 아울러 변수를 6개, 7개… 이렇게 추가도 가능합니다.

(3)의 경우 각 변수가 커버하는 개념 영역이 비슷해야 한다는 취지로 받아들이면 될 것 같습니다. 예컨대 첫번째 변수가 ‘자동차’인데, 두번째 변수가 ‘아반떼’라면 해당 변수들로부터 추출한 유사도가 정확성을 갖기 어려울 것입니다. (4)는 유사도가 높은 객체들은 의미적으로도 비슷하다는 뜻으로 해석됩니다.

문서 간 유사도를 측정하는 지표는 여럿 제안되었습니다만, 대체로 단어(word, term) 수준의 방법론들입니다. 두 문서에 겹치는 단어가 많을수록 유사도가 높다는 결과를 내놓는 식입니다. 단어 수준의 유사도 측정은 (1) 문서 길이 (2) 동시 등장 단어 (3) 흔한/희귀한 단어 (4) 출현 빈도 등을 어떻게 처리하는지에 따라 다양한 방법론이 있습니다. 이번 글은 이와 관련한 여섯가지 측정 지표에 대해 살필 예정입니다.

Notation

앞으로 설명해드릴 여섯가지 지표를 계산하는 데 쓰이는 표현들에 대해 정리해보도록 하겠습니다.

1. $x_{ik}$는 $i$번째 문서에 $k$번째 단어가 몇번 등장했는지 빈도를 나타냅니다.
2. $t_{ik}$는 $x_{ik}$가 0 이상이면 1, 그렇지 않으면 0의 값을 갖습니다.
3. $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 $t$를 바탕으로 구하는데요. 각각 아래 표와 같습니다. 아래 표에서 Y는 어떤 단어가 해당 문서에 쓰인 경우를, N은 쓰이지 않은 경우를 뜻합니다. $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 각각에 해당하는 단어 수를 나타냅니다.

예시 table

아래 표는 앞으로 설명드릴 지표에 대한 이해를 돕기 위한 예시입니다.

아래 표는 등장여부를 binary로 표시한 결과입니다. 같은 말뭉치에서 도출된 표입니다.

Doc1과 Doc2에 대해 $a_{12},b_{12},c_{12},d_{12}$를 각각 구해보겠습니다. Doc1에는 등장했는데 Doc2에는 등장하지 않은 단어는 Term1 하나뿐이므로 $b_{12}$은 1입니다. Doc1에는 등장하지 않았는데 Doc2에 나온 단어는 Term4와 Term5 두 개이므로 $c_{12}$는 2입니다. 두 문서 모두 등장한 단어는 Term3 하나, 두 문서에 모두 나오지 않은 단어는 Term2 하나이므로 $a_{12}$, $d_{12}$는 각각 1입니다.

common features model

$i$번째 문서와 $j$번째 문서에 동시에 등장한 단어수를 전체 단어수로 나누어 구합니다. 보통 전체 말뭉치에 등장하는 단어수가 10만개에 육박하기 때문에 $d_{ij}$가 매우 큽니다. 따라서 이처럼 계산하는 유사도는 대체로 0에 가까운 작은 값을 지닙니다. 계산방법과 예시는 아래와 같습니다.

[{ s }{ ij }^{ common }=\frac { { a }{ ij } }{ { a }{ ij }+{ b }{ ij }+{ c }{ ij }+{ d }{ ij } }]

ratio model

common features model에서 $d_{ij}$를 빼고 계산한 유사도입니다.

[{ s }{ ij }^{ ratio }=\frac { { a }{ ij } }{ { a }{ ij }+{ b }{ ij }+{ c }_{ ij } }]

simple matching coefficient

common features model의 식에서 분자와 분모에 $d_{ij}$를 반영해 구한 유사도입니다. common features model보다는 값이 큰 경향이 있습니다.

[{ s }{ ij }^{ smc }=\frac { { a }{ ij }+{ d }{ ij } }{ { a }{ ij }+{ b }{ ij }+{ c }{ ij }+{ d }_{ ij } }]

jaccard similarity

jaccard similarity는 아래와 같이 구합니다. ratio model과 본질적으로 유사하다고 합니다.

[{ s }{ ij }^{ jaccard }=\frac { \sum _{ k }^{ }{ min({ x }{ ik },{ x }{ jk }) } }{ \sum _{ k }^{ }{ max({ x }{ ik },{ x }_{ jk }) } }]

overlap similarity

overlap simliarity는 아래와 같이 구합니다.

[{ s }{ ij }^{ overlap }=\frac { \sum _{ k }^{ }{ min({ x }{ ik },{ x }{ jk }) } }{ min(\sum _{ k }^{ }{ { x }{ ik } } ,\sum { k }^{ }{ { x }{ jk } } ) }]

cosine similarity

cosine similarity는 아래와 같이 구합니다. 예시로 제시된 table을 행렬로, 각각의 문서에 해당하는 열을 벡터로 놓고 두 벡터를 아래와 같이 내적하게 되면 두 벡터가 이루는 각도(유사도)가 됩니다. 일반적으로 문서 유사도 계산시 가장 많이 쓰이는 방법입니다.

[{ s }{ ij }^{ cosine }=\frac { \sum _{ k }^{ }{ ({ x }{ ik }\times { x }{ jk }) } }{ \sqrt { (\sum _{ k }^{ }{ { x }{ ik }^{ 2 } } )(\sum { k }^{ }{ { x }{ jk }^{ 2 } } ) } }]

이번 글에서는 K-평균 군집화(K-means Clustering)에 대해 살펴보겠습니다. (줄여서 KC라 부르겠습니다) 이번 글은 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

알고리즘 개요

KC는 대표적인 분리형 군집화 알고리즘 가운데 하나입니다. 각 군집은 하나의 중심(centroid)을 가집니다. 각 개체는 가장 가까운 중심에 할당되며, 같은 중심에 할당된 개체들이 모여 하나의 군집을 형성합니다. 사용자가 사전에 군집 수($k$)가 정해야 알고리즘을 실행할 수 있습니다. $k$가 하이퍼파라메터(hyperparameter)라는 이야기입니다. 이를 수식으로 적으면 아래와 같습니다.

[X={ C }{ 1 }{ \cup C }{ 2 }{ …\cup C }{ K },\quad { C }{ i }\cap { C }{ j }=\phi \ \ argmin{ C }{ \sum { i=1 }^{ K }{ \sum _{ { x }{ j }\in { C }{ i } }^{ }{ { \left| { x }{ j }-{ c }_{ i } \right| }^{ 2 } } } }]

학습 과정

KC는 EM 알고리즘을 기반으로 작동합니다. EM알고리즘은 크게 Expectation 스텝과 Maximization 스텝으로 나뉘는데요. 이를 수렴할 때까지 반복하는 방식입니다. 동시에 해를 찾기 어려운 문제를 풀 때 많이 사용되는 방법론입니다. KC의 경우 (1) 각 군집 중심의 위치 (2)각 개체가 어떤 군집에 속해야 하는지 멤버십, 이 두 가지를 동시에 찾아야 하기 때문에 EM 알고리즘을 적용합니다.

군집 수 $k$를 2로 정했습니다. 우선 군집의 중심(빨간색 점)을 랜덤 초기화합니다.

모든 개체들(파란색 점)을 아래 그림처럼 가장 가까운 중심에 군집(녹색 박스)으로 할당합니다. 이것이 Expectation 스텝입니다.

이번엔 중심을 군집 경계에 맞게 업데이트해 줍니다. 이것이 Maximization 스텝입니다.

다시 Expectation 스텝을 적용합니다. 바꿔 말해 모든 개체들을 가장 가까운 중심에 군집(보라색 박스)으로 할당해주는 작업입니다.

Maximization 스텝을 또 적용해 중심을 업데이트합니다. Expectation과 Maximization 스텝을 반복 적용해도 결과가 바뀌지 않거나(=해가 수렴), 사용자가 정한 반복수를 채우게 되면 학습이 끝납니다.

KC의 특징과 단점

KC는 각 군집 중심의 초기값을 랜덤하게 정하는 알고리즘인데요. 아래 그림처럼 초기값 위치에 따라 원하는 결과가 나오지 않을 수도 있습니다.

군집의 크기가 다를 경우 제대로 작동하지 않을 수 있습니다.

군집의 밀도가 다를 경우에도 마찬가지입니다.

데이터 분포가 특이한 케이스도 군집이 잘 이루어지지 않습니다.

이 때문에 KC를 실제 문제에 적용할 때는 여러번 군집화를 수행해 가장 빈번히 등장하는 군집에 할당하는 majority voting 방법을 쓰는 경우가 많다고 합니다. KC의 계산복잡성은 $O(n)$으로 계층적 군집화(Hiarchical clustering)와 비교해 그리 무겁지 않은 알고리즘이기 때문입니다.

이번 글에서는 계층적 군집화(Hierarchical Clustering)를 살펴보도록 하겠습니다. (줄여서 HC라 부르겠습니다) 이번 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

알고리즘 개요

HC란 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 개체 내지 그룹과 통합하여 군집화를 수행하는 알고리즘입니다. K-평균 군집화(K-means Clustering)와 달리 군집 수를 사전에 정하지 않아도 학습을 수행할 수 있습니다. 개체들이 결합되는 순서를 나타내는 트리형태의 구조인 덴드로그램(Dendrogram) 덕분입니다. 아래 그림과 같은 덴드로그램을 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됩니다.

학습 과정

HC를 수행하려면 모든 개체들 간 거리(distance)나 유사도(similarity)가 이미 계산되어 있어야 합니다. 거리측정 방법에 대해선 이곳을, (문서)유사도 측정법에 대해선 이곳을 참고하시면 좋을 것 같습니다. 주어진 학습데이터의 개체 수가 네 개이고 아래 그림처럼 거리 행렬을 이미 구해놨다고 가정해봅시다.

거리가 가까운 관측치들끼리 차례대로 군집으로 묶어보겠습니다. 거리가 가장 짧은 것이 2이고 이에 해당하는 개체는 A와 D이므로 먼저 A와 D를 하나의 군집으로 엮으면 좋겠네요. 표 왼쪽에 덴드로그램을 그릴 건데요, 덴드로그램의 높이는 관측치간 거리(2)가 되도록 합니다.

자 여기서 A와 D를 한 군집으로 엮었으니 거리행렬을 바꿔주어야 합니다. 다시 말해 개체-개체 거리를 군집-개체 거리로 계산해야 한다는 것이죠. 예컨대 ‘AD’와 ‘B’, ‘AD’와 ‘C’ 이렇게 거리를 구해야 한다는 말입니다. 그런데 군집-개체, 혹은 군집-군집 간 거리는 어떻게 계산해야 할까요? 여기엔 아래 그림처럼 여러가지 선택지가 존재합니다.

위 네 가지 방법 가운데 하나를 택했다고 가정하고 거리행렬을 업데이트했더니 AD와 C가 가장 인접해 있군요. 이번엔 이 둘을 이어줍시다.

그 다음 과정을 수행했더니 아래처럼 되었습니다.

분석 대상 관측치가 하나도 없으면 학습이 종료됩니다.

HC의 특징

이미 설명해 드린 것처럼 HC는 K-평균 군집화와 달리 사전에 군집수 $k$를 설정할 필요가 없습니다. 그도 그럴 것이 앞선 예에서 덴드로그램의 최상층을 끊어주면 $A, D, C$와 $B$로 두 개 군집이 도출됩니다. 위에서 두번째 층을 끊으면 $A, D$와 $C$, $B$ 이렇게 세 개 군집이 나옵니다. HC의 학습결과물인 덴드로그램을 적절한 수준에서 잘라주면 된다는 얘기입니다. 반면 HC의 계산복잡성은 $O(n^3)$로 K-평균 군집화보다는 무거운 편입니다.

이번 글에서는 K-최근접이웃(K-Nearest Neighbor, KNN) 알고리즘을 살펴보도록 하겠습니다. 이번 글은 고려대 강필성 교수님, 김성범 교수님 강의를 참고했습니다. 그럼 시작하겠습니다.

모델 개요

KNN은 새로운 데이터가 주어졌을 때 기존 데이터 가운데 가장 가까운 $k$개 이웃의 정보로 새로운 데이터를 예측하는 방법론입니다. 아래 그림처럼 검은색 점의 범주 정보는 주변 이웃들을 가지고 추론해낼 수 있습니다. 만약 $k$가 1이라면 오렌지색, $k$가 3이라면 녹색으로 분류(classification)하는 것이지요. 만약 회귀(regression) 문제라면 이웃들 종속변수($y$)의 평균이 예측값이 됩니다.

사실 KNN은 학습이라고 할 만한 절차가 없습니다. 그도 그럴 것이 새로운 데이터가 들어왔을 때, 그제야 기존 데이터 사이의 거리를 재서 이웃들을 뽑기 때문입니다. 그래서 KNN을 모델을 별도로 구축하지 않는다는 뜻으로 게으른 모델(Lazy model)이라고 부르는 사람도 있습니다. 조금 점잖게 Instance-based Learning이라고 불리기도 합니다. 데이터로부터 모델을 생성해 과업을 수행하는 Model-based learning과 대비되는 개념으로, 별도 모델 생성과정 없이 각각의 관측치(instance)만을 이용하여 분류/회귀 등 과업을 수행한다는 취지입니다.

KNN의 하이퍼파라메터(Hyper parameter)는 탐색할 이웃 수($k$), 거리 측정 방법 두 가지입니다. $k$가 작을 경우 데이터의 지역적 특성을 지나치게 반영하게 됩니다(overfitting). 반대로 매우 클 경우 모델이 과하게 정규화되는 경향이 있습니다(underfitting). 아래 그림은 범주가 두 개인 데이터의 분류 경계면을 나타낸 것입니다. $k$의 크기에 따라 분류 경계면에 단순해지는 걸 확인할 수 있습니다.

다만 KNN 알고리즘이 이러한 경계면을 직접 만드는 것은 절대 아니고, 새로운 데이터가 주어졌을 때 어느 범주로 분류되는지를 보기 좋게 시각화했다는 점에 주의하셔야 합니다.

거리 지표

KNN은 거리 측정 방법에 따라 그 결과가 크게 달라지는 알고리즘입니다. 몇 가지 살펴보겠습니다.

Euclidean Distance

가장 흔히 사용하는 거리 척도입니다. 두 관측치 사이의 직선 최단거리를 의미합니다. \(\begin{align*} X&=({ x }_{ 1 },{ x }_{ 2 },...,{ x }_{ n })\\ Y&=({y }_{ 1 },{ y }_{ 2 },...,{ y }_{ n })\\ { d }_{ (X,Y) }&=\sqrt { { ({ x }_{ 1 }-{y }_{ 1 }) }^{ 2 }+...+{ ({ x }_{ n }-{ y }_{ n }) }^{ 2 } } \\ &=\sqrt { \sum _{ i=1 }^{ n }{ { ({ x }_{ i }-{ y }_{ i }) }^{ 2 } } } \end{align*}\)

예시는 아래와 같습니다.

[{ d }_{ (A,B) }=\sqrt { { (0-2) }^{ 2 }+{ (3-0) }^{ 2 }+{ (2-0) }^{ 2 } } =\sqrt { 17 }]

Manhattan Distance

A에서 B로 이동할 때 각 좌표축 방향으로만 이동할 경우에 계산되는 거리입니다. 뉴욕 맨해튼의 한 빌딩에서 다른 빌딩으로 이동하려면 격자 모양의 길을 따라가야 하는데요, 이를 떠올려보면 쉽습니다. Taxi cab Distance라고도 불립니다.

아래 그림(출처)의 세 경로는 맨해튼 거리 기준으로는 같은 거리입니다.

Mahalanobis Distance

변수 내 분산, 변수 간 공분산을 모두 반영하여 거리를 계산하는 방식입니다. 변수 간 상관관계를 고려한 거리 지표입니다.

[{ d }_{ Mahalanobis(X,Y) }=\sqrt { { (\overrightarrow { X } -\overrightarrow { Y } ) }^{ T }{ \Sigma }^{ -1 }(\overrightarrow { X } -\overrightarrow { Y } ) } \ { \Sigma }^{ -1 }=inverse\quad of\quad covariance\quad matrix]

$X, Y$ 사이의 마할라노비스 거리를 $c$, $X$를 $(x_1, x_2)$, $Y$를 $(0,0)$로 두고 위 식을 풀면 아래와 같이 쓸 수 있습니다. 타원의 방정식 꼴입니다.

[{ x }{ 1 }^{ 2 }{ s }{ 1 }+2{ x}{ 1 }{ x }{ 2 }{ s }{ 2 }+{ x }{ 2 }^{ 2 }{ s }{ 4 }={ c }^{ 2 }\ { \Sigma }^{ -1 }=\begin{bmatrix} { s }{ 1 } & { s }{ 2 } \ { s }{ 3 } & { s }_{ 4 } \end{bmatrix}]

위 식에서 $c$를 1로 고정시켜 놓고, 공분산행렬을 바꾸면 마할라노비스 거리가 어떻게 달라지는지 살펴보겠습니다. 아래 그림들에 나오는 타원 위의 점들은 마할라노비스 거리 기준으로는 모두 같은 거리입니다. 공분산행렬이 항등행렬(identity matrix)일 때 마할라노비스 거리는 유클리디언 거리와 동일합니다.

[\Sigma ={ \Sigma }^{ -1 }=\begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}]

[\Sigma =\begin{bmatrix} 4 & 0 \ 0 & 1 \end{bmatrix},\quad { \Sigma }^{ -1 }=\begin{bmatrix} 1/4 & 0 \ 0 & 1 \end{bmatrix}]

[\Sigma =\begin{bmatrix} 4 & \sqrt { 2 } \ \sqrt { 2 } & 1 \end{bmatrix},\quad { \Sigma }^{ -1 }=\begin{bmatrix} 1/2 & -\sqrt { 2 } \ -\sqrt { 2 } & 2 \end{bmatrix}]

바로 위 그림의 공분산은 그대로 두고, 이제는 $c$를 바꿔보겠습니다. $c$의 값에 따른 변화는 아래 그림과 같습니다.

마지막으로 유클리디언 거리와 비교해 보겠습니다. 아래와 같은 데이터가 주어졌을 때 유클리디언 거리 측정 기준으로는 데이터의 중심과 $A$와의 거리는 $B$와의 거리보다 멉니다. 하지만 마할라노비스 거리 기준으로는 $A$가 가깝습니다. 변수 간 양의 상관관계가 강해서 그 방향과 동떨어진 $B$가 마할라노비스상 거리가 꽤 멀게 계산되기 때문입니다. 이렇듯 마할라노비스 거리는 거리 측정시 변수 내 분산, 변수 간 공분산/상관관계를 모두 고려합니다.

Correlation Distance

데이터의 pearson correlation을 거리 척도로 직접 사용합니다. 개별 관측치 하나하나가 아니라 데이터 전체의 경향성을 비교하기 위한 척도입니다. 다시 말해 두 개 데이터 패턴의 유사도를 반영할 수 있습니다. 상관계수는 -1에서 1 사이의 범위를 가지므로, Correlation Distance의 범위는 0에서 2 사이입니다. 0이면 두 데이터의 패턴이 매우 유사한 것이고 2이면 그렇지 않다고 해석할 수 있습니다.

[{ d }_{ Corr(X,Y) }=1-\rho _{ XY }]

예컨대 아래 그림의 경우 좌측은 Correlation Distance가 가깝게(패턴이 유사), 우측은 멀게 나타날 것입니다.

Rank Correlation Distance

데이터의 Spearman Rank Correlation을 거리 척도로 직접 사용합니다. 나머지 특징은 correlation distance와 같습니다.

[{ d }{ RankCorr(X,Y) }=1-\rho _{ XY }\ \rho _{ XY }=1-\frac { 6 }{ n({ n }^{ 2 }-1) } \sum _{ i=1 }^{ n }{ { (rank({ x }{ i })-rank({ y }_{ i })) }^{ 2 } }]

예컨대 지역별 계절 기온 순위(rank)가 아래처럼 주어졌다고 가정해 봅시다.

그렇다면 서울-뉴욕 간 Rank correlation distance는 아래와 같습니다.

[{ d }_{ RankCorr(Seoul,NewYork) }=1-\rho =1-1=0\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left{ { (3-3) }^{ 2 }+{ (1-1) }^{ 2 }+{ (2-2) }^{ 2 }+{ { (4-4 }) }^{ 2 } \right} =1]

서울-시드니 간 Rank correlation distance는 아래와 같습니다.

[{ d }_{ RankCorr(Seoul,Sydney) }=1-\rho =1-(-1)=2\ \rho =1-\frac { 6 }{ 4({ 4 }^{ 2 }-1) } \left{ { (3-2) }^{ 2 }+{ (1-4) }^{ 2 }+{ (2-3) }^{ 2 }+{ { (4-1 }) }^{ 2 } \right} =-1]

best K 찾기

R 내장 데이터인 iris에 대해 KNN을 수행하였습니다. best K는 데이터마다 다르기 때문에 탐욕적인 방식으로 찾아야 합니다. 아래 그림을 볼까요?

$k$를 1부터 10까지 1씩 증가시키면서 오분류율을 점검했습니다. 그 결과 best K는 7로 확인이 되네요. 그런데 iris 말고 다른 데이터에서 $k$가 증가할 수록 오분류율이 계속 낮아진다면 $k$ 범위를 더 넓혀서 탐색할 필요가 있습니다.

아울러 best K를 찾기 위해서는 학습데이터와 검증데이터를 나누고, $k$값에 변화를 주면서 실험을 해야 하는데요. 이런 모든 과정을 대신 해주는 패키지가 R에 있어서 편리하게 사용할 수 있습니다. 분류 문제에 best K를 찾기 위한 코드는 아래와 같습니다.

# find best k (classification)
library(kknn)
knntr <- train.kknn(Target ~ ., data, kmax=10, distance=2, kernel="rectangular")
knntr$MISCLASS
knntr$best.parameters

combining rule

1-NN을 제외한 KNN은 주변 이웃의 분포에 따라 예측 결과가 충분히 달라질 수 있습니다. 가장 단순한 결정 방식은 다수결(Majority voting)입니다. 이웃들 범주 가운데 빈도 기준 제일 많은 범주로 새 데이터의 범주를 예측하는 것입니다.

가중합(weighted voting) 방식도 있습니다. 거리($d$)가 가까운(=유사도가 높은) 이웃의 정보에 좀 더 가중치를 줍니다. $1/(1+d)$, $1/(1+d^2)$, $exp(-d)$ 등 단조감소함수이기만 하면 무엇이든 가중치 산출 함수로 쓸 수 있다고 합니다.

cut-off 기준 설정

이진분류 문제를 푼다고 할 때 우리가 예측해야 할 관측치 주변 이웃의 범주 비율 정보가 ‘A : 0.7, B : 0.3’이라고 가정해 봅시다. 별 다른 처리를 하지 않는다면 우리는 이 관측치를 A로 분류하게 됩니다. 두 범주가 절반씩 있을 거라는 상식에서 비롯된 생각입니다.

그런데 범주 간 비율이 불균형한 데이터일 땐 여기에 주의를 해야 합니다. 예컨대 제조업 정상/불량 데이터를 분류하는 문제의 경우 학습데이터에선 정상 관측치가 대다수일 겁니다. 여기에서 새 관측치 주변 이웃의 범주 비율 정보가 ‘정상 : 0.8, 불량 : 0.2’이라면 불량으로 판정하는 게 합리적일 것입니다.

요컨대 컷오프 기준을 설정할 때 학습데이터 범주의 사전확률(prior probability)을 고려해야 한다는 것입니다.

KNN 수행시 주의점

KNN 수행 전 반드시 변수를 정규화(Normalization)해 주어야 합니다. 가상의 아래 표를 보시죠.

도시별 정보를 모아서 유사한 환경을 지닌 도시를 뽑는 문제를 풀어봅시다. 위 표 기준으로는 거리/유사성 측정시 미세먼지농도 정보는 전혀 반영이 되지 않을 겁니다. 인구 변수에 해당하는 숫자가 훨씬 크기 때문입니다. 따라서 변수별로 평균과 분산을 일치시키는 정규화 작업을 반드시 KNN 적용 전 수행해 주어야 합니다.

KNN의 장단점

KNN은 학습데이터 내에 끼어있는 노이즈의 영향을 크게 받지 않으며 학습데이터 수가 많다면 꽤 효과적인 알고리즘이라고 합니다. 특히 마할라노비스 거리와 같이 데이터의 분산을 고려할 경우 매우 강건(robust)한 방법론으로 알려져 있습니다. 네이버, 카카오 등 현업에서도 KNN을 두루 사용하고 있는 것으로 전해집니다.

아울러 $k$가 1인 1-NN의 오차 범위는 다음과 같다는 사실이 증명되어 있습니다. (Idealerr=주어진 데이터에 적합 가능한 가장 이상적인 모형의 오차) 바꿔 말해 1-NN에 한해서는 모델 성능을 어느 정도 보장할 수 있다는 이야기입니다.

[Err(1-NN)\le 2\times IdealErr]

그러나 최적 이웃의 수(k)와 어떤 거리척도가 분석에 적합한지 불분명해 데이터 각각의 특성에 맞게 연구자가 임의로 선정해야 하는 단점이 있습니다.

또 새로운 관측치와 각각의 학습 데이터 사이의 거리를 전부 측정해야 하므로 계산 시간이 오래 걸리는 한계점이 존재합니다.

이 때문에 Locality Sensitive Hashing, Network based Indexer, Optimized product quantization 등 KNN의 계산복잡성을 줄이려는 시도들이 여럿 제안되었습니다. 인스턴스 간 거리를 모두 계산하지 않고도 마치 그렇게 한 것처럼 결과를 내는 방법론들입니다. 이에 대해서는 추후에 다시 정리할 계획입니다.

여기까지 읽어주셔서 감사합니다.

이번 글에서는 클러스터링(Clustering;군집화)의 전반적 내용에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. 이 글은 클러스터링의 개괄적 내용을 설명하는 데 방점을 두었으니 K-means 군집화, 계층적 군집화 등 구체적 알고리즘을 살펴보시려면 링크를 클릭하시기 바랍니다. 그럼 시작하겠습니다.

클러스터링의 목적

클러스터링의 목적은 간단합니다. 비슷한 개체끼리 한 그룹으로, 다른 개체는 다른 그룹으로 묶어보자는 겁니다. 이를 좀 있어보이게 표현하면 아래와 같습니다.

(1) 군집 간 분산(inter-cluster variance) 최대화
(2) 군집 내 분산(inner-cluster variance) 최소화

다만 여기서 주의해야 할 것은 클러스터링은 분류(Classification)와 구별해야 한다는 점입니다. 클러스터링은 정답이 없는 비지도학습(unsupervised learning)입니다. 다시 말해 각 개체의 그룹 정보 없이 비슷한 개체끼리 묶어보는 거죠. 반면 분류는 정답이 있는 지도학습(supervised learining)입니다. 분류 과제를 수행할 때는 데이터의 독립변수($X$)로 종속변수($Y$)를 예측하도록 학습을 진행하게 됩니다.

군집 타당성 평가

클러스터링 과업은 정답이 없기 때문에 일반적인 머신러닝 알고리즘처럼 단순정확도(Accuracy) 등 지표로 평가할 수 없습니다. 아래 예에서 볼 수 있듯 최적의 군집 개수를 정답 없이 알아내기란 쉽지 않습니다.

그렇다고 해서 군집이 제대로 만들어졌는지 평가할 수 있는 방법이 아주 없지는 않습니다. 군집을 만든 결과가 얼마나 유용한지 따지는 군집타당성지표(Clustering Validity Index)가 있기 때문입니다. 군집타당성지표는 아래 그림처럼 (1) 군집 간 거리 (2) 군집의 지름 (3) 군집의 분산 등을 고려합니다. 다시 말해 군집 간 분산과 군집 내 분산을 따진다는 겁니다. 이번 글에서는 Dunn Index와 Silhouette 두 가지 지표를 살펴보겠습니다.

Dunn Index

Dunn Index는 군집 간 거리의 최소값(하단 좌측)을 분자, 군집 내 요소 간 거리의 최대값(하단 우측)을 분모로 하는 지표입니다.

[I(C)=\cfrac { \min { i\neq j }{ { { d }{ c }({ C }{ i },{ C }{ j })} } }{ \max { 1\le l\le k }{ { \triangle ({ C }{ l })} } }]

군집 간 거리는 멀수록, 군집 내 분산은 작을 수록 좋은 군집화 결과라 말할 수 있는데요. 이 경우에 Dunn Index는 커지게 됩니다.

Silhouette

실루엣 지표를 계산하는 식은 아래와 같습니다.

[s(i)=\frac { b(i)-a(i) }{ \max { { a(i),b(i)} } }]

여기에서 $a(i)$는 $i$번째 개체와 같은 군집에 속한 요소들 간 거리들의 평균입니다. $b(i)$는 $i$번째 개체와 다른 군집에 속한 요소들 간 거리들의 평균을 군집마다 각각 구한 뒤, 이 가운데 가장 작은 값을 취한 것입니다. 다시 말해 $b(i)$는 $i$번째 개체가 속한 군집과 가장 가까운 이웃군집을 택해서 계산한 값이라고 보시면 됩니다.

예컨대 아래처럼 파란색 군집 안에 있는 네모 박스에 해당하는 개체를 중심으로 실루엣 지표를 구할 수 있습니다. 이 경우 $a(i)$는 네모 개체와 파란색 군집 내 개체들 사이의 거리들의 평균이고요. $b(i)$는 네모 개체와 오렌지색 군집 내 개체들 사이의 거리들의 평균을 의미합니다.

가장 이상적인 경우라면 $a(i)$가 0일 겁니다. 한 군집의 모든 개체가 한치도 떨어져 있지 않고 붙어있는 경우가 여기에 해당합니다. 그러면 실루엣 지표는 1이 됩니다. 최악의 경우에는 $b(i)$가 0입니다. 서로 다른 군집이 전혀 구분되지 않는 경우입니다. 이 때 실루엣 지표는 -1이 됩니다. 보통 실루엣 지표가 0.5보다 크면 군집 결과가 타당한 것으로 평가하게 된다고 합니다.

클러스터링의 종류

클러스터링에는 몇 가지 종류가 있는데 다음과 같습니다.

hard clustering : 한 개체가 여러 군집에 속하는 경우를 허용하지 않는 군집화 방법입니다

soft clustering : 한 개체가 여러 군집에 속할 수 있습니다.

pational clustering : 전체 데이터의 영역을 특정 기준에 의해 동시에 구분하는 군집화 방법입니다. 각 개체들은 사전에 정의된 개수의 군집 가운데 하나에 속하게 됩니다. K-mean 군집화가 대표적입니다.

hierarchical clustering : 개체들을 가까운 집단부터 차근차근 묶어나가는 방식입니다. 군집화 결과뿐 아니라 유사한 개체들이 결합되는 덴드로그램(dendrogram)을 생성합니다.

Self-Organizing Map : 뉴럴넷 기반의 군집화 알고리즘입니다.

Spectual clustering : 그래프 기반의 군집화 방법론입니다