Markov clustering은 데이터 분류 기법의 일종인데, Markov Chain 을 기반으로 하고 있어서 이것에 대한 이해가 먼저 필요해요. 둘 다 설명해 보겠습니다. 일단 하고 많은 소개글들과 다르게 쓰려고 하는 것은, 가능한 한 쉽게 그리고 코드를 곁들여서 설명하려고 하는 점입니다.
데이터 간의 관계
Markov Clustering의 목적은 데이터를 분류하는 겁니다. 어떤 데이터냐? 다른 데이터와 관계를 가지고 있는 데이터들을 분류하는 겁니다. 데이터의 관계라고 하면 여러 가지가 있겠지만 일단 아래 그림을 먼저 보겠습니다.
위 그림에서 "데이터" 라고 부를 만한 게 8개가 있습니다. 딱 봐도 네개씩 묶으면 (=클러스터링하면) 되겠죠? 어떻게? 서로 가까운 것들끼리요. 즉, 여기서 우리가 직관적으로 우리 머리로 클러스터링한 결과의 근거는,
- 데이터 상호 간의 "거리" 를 데이터 간의 관계로 규정을 하고,
- 관계성이 높은 (거리가 가까운) 애들끼리 알아서 묶었다는 겁니다.
인간은 머리가 좋은 거 같아요. 그냥 눈으로 딱 봐도 하잖아요? 이런 방식을 기계가 하게 했던 것이, 아래 여러가지 방식의 클러스터링입니다.
Markov Clustering 에서 관계의 정의
위의 내용을 가만히 살펴 봤을 때, 결국 어떤 방식으로든 데이터 간의 관계가 정의되어 있을 때, 그 관계가 높은 애들끼리 묶어주는 게 클러스터링이다... 라고 얘기할 수 있을 거 같아요. 그러면 Markov Clustering에서의 관계는 뭐냐? 다음의 그림을 보시죠
Markov Clustering은 데이터 간의 관계를 "상태의 변화" 로 생각합니다. 보통 데이터 라고 하면, 뭐 예를 들면 2차원 데이터면 (1, 2) 라는 식으로 딱 떨어지고 다른 데이터와의 관계는 예를 들면 "거리" 를 별도로 구하잖아요? 근데 이건 이렇게 얽힌 상태들 자체가 데이터가 됩니다. 뭔 소린가 싶을 텐데 예를 들어 한번 보겠습니다.
위의 그림을 이렇게 바꿔볼께요. "비가 온다" 는 상태입니다. 이때 내일도 비가 올 확률과 내일은 비가 안올 확률이 있겠죠? 근데 이거만으로는 완전한 데이터가 안됩니다. "비가 안온다" 라는 상태도 있어야겠죠.
한번 차근차근히 볼께요. 위에 글자가 일단 너무 많아서 헷갈리니까, 글자를 실제 확률로 한번 바꿔보겠습니다.
아예 색깔로 나눠봤는데, 위에서 보는 것처럼 "비가 온다" 라는 상태에 대해서 다른 상태 또는 자기 자신의 상태로 갈 확률 그 자체가 하나의 데이터가 됩니다. 반대도 마찬가지입니다. 그리고 위에 쓰인 각각의 확률 값 자체가 관계가 되구요. 즉, "비가 온다" 라는 상태는, 자기 자신보다 "비가 안온다" 라는 상태와 관계를 더 강하게 맺고 있고, "비가 안온다" 라는 상태는 그렇지 않습니다.
관계를 데이터로 만들기
뭔가 숫자가 써 있으니까, 이걸 그냥 흔히 데이터를 표현하는 벡터로 바꿔주면 되겠죠? 이렇게 합니다.
| 상태 | 비가 오는 상태로 갈 확률 | 비가 안오는 상태로 갈 확률 |
| 비가 온다 | 0.4 | 0.6 |
| 비가 안온다 | 0.2 | 0.8 |
이렇게 현재 상태를 놓고, 다음 상태로 갈 때의 확률이 어떻게 되는지를 쭉 써주면 그게 데이터가 돼요. 결과적으로 아래와 같습니다.
- 데이터 1 = [0.4, 0.6]
- 데이터 2 = [0.2, 0.8]
Markov Chain (마르코프 연쇄)
사실은 지금 설명한 것이 Markov Chain 입니다. Markov Clustering 전에 반드시 알아야 할 내용이기 때문에 짚고 넘어가겠습니다. 한글로는 마르코프 연쇄라고 하는데, 위키에 찾아보면 무슨 이산확률상태가 어쩌고 저쩌고 하는데 똑같은 내용입니다. 위의 그림으로 돌아가보시죠.
이 그림을 보면, 지금 상태에서 바로 다음 상태로 갈 확률이 쭉 정의되어 있습니다. 이렇게 현재에서 "바로 다음" 상태로 간다고 해서 이걸 1차 마르코프 연쇄 (Markov Chain) 이라고 합니다. 그럼 2차 마르코프 연쇄는 뭐냐?
위의 예제에서는, 오늘 비가 올때 모레 비가 안 올 확률은? 이게 2차 마르코프 연쇄입니다. 그림으로 표현해보면 아래와 같습니다.
N차 마르코프 연쇄 구하기
위에서 데이터 1, 데이터 2를 아래와 같이 정의했습니다.
- 데이터 1 = [0.4, 0.6]
- 데이터 2 = [0.2, 0.8]
각 데이터를 벡터로 생각하고, 아래처럼 이를 행렬로 나타내 보겠습니다.
이걸 전이 확률 행렬 (Transition Probability Matrix) 이라고 합니다. 이제 행렬이 나왔고, 그냥 이걸 두번 곱하면 2차 마르코프 연쇄가, n번 곱하면 n차 마르코프 연쇄가 됩니다. 그러면 오늘 비가 올 때 내일 모레 비가 안 올 확률을 구해볼게요.
행렬을 읽는 방법은 똑같습니다. 비가 오는 상태는 1열이고 비가 안오는 상태로 갈 확률은 2행이니까, 오늘 비가 왔는데 모레 비가 안올 확률은 이 모델에서 0.72, 즉 72%가 됩니다.
N차 마르코프 연쇄의 특징
이제 거의 다 왔습니다!! 힘을 내세요!! 특징을 딱 하나만 알아볼께요. 다음의 물음에 대한 답이 될 겁니다.
마르코프 행렬을 계속 곱하면 어떻게 될까?
이게 그 답입니다. 계속 곱하다 보면, 어느 순간 아무리 곱해도 값이 변하지 않게 수렴합니다.
이건 사견이지만, Markov Chain은 기본적으로 시간의 흐름에 따른 상태의 변화를 정의하는 모델이고, 그렇다고 하면 n차로 계속 곱한다는 것은 먼 미래에 대한 예측을 의미하는 것으로 보입니다. 그 상태가 뭔 짓을 해도 변하지 않는다는 건, 예를 들면 주식 시장은 미래에는 상승한다! 물가는 미래에 상승한다! 뭐 이런 게 아닐까 싶어요. 미래에 물가가 오른다는 건 나도 알지... 같은
근데 이게 만약에, 그런 의미라고 한다면 사실 이 모델 자체가 현실을 잘 반영하는 게 아닌가 하고 생각합니다. 가까운 미래는 어느 정도 예측 가능하다, 하지만 먼 미래는 대충 추세만 안다 라는 결과로 말이예요.
Markov Clustering 예시
이제 진짜 거의 다 왔습니다.
이건 사실 위에 Markov Chain이 뭔지, 어떻게 동작하는지만 알면 그냥 순서대로 따라가면 됩니다. 위에서 계속 "확률"로 얘기를 했는데, 음... 이제는 그냥 "횟수"로 얘기를 할께요. 예를 들면... 머 지난 1년을 봤더니, 비가 온 다음날 비가 온 날이 100일 이더라, 비가 온 다음날 비가 안 온 날이 265일 이더라... 이런 식으로요.
1. 각 상태의 전이를 확인해서 전이 행렬을 만듭니다. 이때, 자기 자신의 상태로 가는 건 뺍니다. 즉, 비가 온 다음날 비가 온 날은 아예 0으로 빼버립니다. 비를 예시로 하면, 다음과 같습니다.
2. [해도 되고 안해도 되는 과정] 자기 상태로 가는 걸 1로 바꿔요. 이게 알고리즘 순서 상에서 그냥 Optional로 되어 있는데, 일단 따라가 보겠습니다.
3. 행렬을 열별로 표준화합니다. 확률로 바꾸는 과정이겠죠?
이제부터 나올 과정을 계속 반복해 주면 됩니다.
4. [반복 스텝 1] 마르코프 연쇄의 차수를 높입니다. 즉, 전이 행렬을 몇 차례 곱해줍니다. 몇 번을 곱해줄 지는 튜닝 인자로 정해주면 돼요. 보통 2를 쓰는 거 같아요. 그러니까... 위에서 결과로 나온 행렬을 2번 곱해줍니다. 그림으로 보면 아래와 같아요.
이 과정은 마르코프 연쇄에서 차수가 높아지면, 연결이 강한 쪽으로 흐르기가 쉽고 연결이 약한 쪽으로는 흐르기가 어려운 특성 때문이라고 합니다. 차수가 너무 높아지면 이런 특성이 사라진다고 하네요.
5. [반복 스텝 2] 행렬을 강조해 줍니다. 그러니까... 이건 행렬의 요소끼리 그냥 곱해줘요. 곱하는 횟수도 마찬가지로 튜닝 인자입니다. 여기도 2를 써보죠. 그러니까 요소별로 제곱을 해 줍니다. 이러면 큰 숫자는 더 커지고, 작은 숫자는 더 작아지므로, 기존에 강한 연결을 더 강하게 만들어줍니다. 이것을 인플레이션 과정이라 합니다. 그런데 0보다 작은 걸 더 곱해버리면 숫자가 몽땅 다 작아지니까, 이걸 다시 열 별로 표준화를 해 줍니다. (다 합쳤을 때 1이 되게끔)
4번과 5번 스텝을 계속 반복하다 보면, 어느 순간 변하지 않는 행렬이 나와요. 그러면 끝입니다. 위의 예시에서는 아래와 같은 행렬입니다.
이걸 해석해 보면, 비가 온다와 비가 안온다 상태가 하나로 묶였다는 뜻입니다. 데이터가 두개밖에 없어서 이해가 잘 안되니, 이제는 코드를 보면서 예시를 살펴보겠습니다.
코드로 살펴보기
#-*- coding:utf-8 -*-
import numpy as np
from matplotlib import pyplot as plt
# 임의로 격자 데이터 생성
grid_size = 10
num_data = grid_size**2
pos = [[i+np.random.rand()*0.4, j+np.random.rand()*0.4] \
for i in range(grid_size) for j in range(grid_size)] # 사각형 그리드
pos = np.array(pos)
# 전이 행렬 생성
A = (np.random.rand(num_data**2)*100).round().reshape((num_data, num_data))
# 자기랑 일정한 거리 이하에 있는 연결만 남겨두고 나머지는 0으로 만듬
for i in range(num_data):
A[i] = A[i]*(np.sum((pos - pos[i])**2, axis=1) < grid_size/4)
# 자기 자신에게 가는 노드를 1로 변경
A = A*(-1*(np.eye(num_data)-1)) + np.eye(num_data)
# Normalize
A = A/A.sum(axis=0)
# 처음 연결 시각화
fig = plt.figure(figsize=(8,8))
for i in range(num_data):
for j in range(num_data):
if A[j][i] != 0:
plt.plot([pos[i][0],pos[j][0]], [pos[i][1],pos[j][1]], \
linewidth=A[j][i]/np.max(A)*5, c='#003366', alpha=0.3)
plt.scatter(pos.T[0],pos.T[1], s=100)
plt.show()
# 마르코프 연쇄
A = np.matmul(A,A)
A = A*A
A = A/A.sum(axis=0)
# 재시각화
fig = plt.figure(figsize=(8,8))
for i in range(num_data):
for j in range(num_data):
if A[j][i] != 0:
plt.plot([pos[i][0],pos[j][0]], [pos[i][1],pos[j][1]], \
linewidth=A[j][i]/np.max(A)*5, c='#003366', alpha=0.3)
plt.scatter(pos.T[0],pos.T[1], s=100)
plt.show()
코드는 위와 같고, 이 코드의 실행 결과를 가지고 한번 이야기해 보겠습니다.
데이터와 연결 만들기
데이터의 위치는 중요한 게 아닙니다. 그냥 임의로 여기에 있다 치고 보기 좋게 뿌린 것 뿐이구요, 단지 저 연결의 굵기를 연결의 강도로 생각해 주시면 됩니다. 이렇게 데이터 간의 관계(연결)에 따라 시각화를 했구요, 이제 위에서 설명한 것처럼 4번, 5번 스텝을 계속 반복해 주면서 강한 연결은 더 강하게, 약한 연결은 약하게 만들어 보겠습니다.
클러스터링 과정
과정은 11번인가를 반복했는데, 애니메이션으로 보면 아래와 같습니다.
보시면 강한 연결은 점점 강조되어서 점점 강하게 되고, 그렇지 못한 건 점점 지워지면서 결국 몇 개의 그룹으로 나눠지는 게 보이시죠? 제가 뭘 한 게 아닙니다. 그냥 위 스텝에서 4, 5번 스텝만 반복하면 저렇게 알아서 됩니다.
최종적으로는 이렇게 10개의 클러스터로 분류됩니다.
오늘은 Markov Clustering에 필요한 사전 지식과 함께 내용도 알아봤습니다. 코드도 있으니 함께 보시면 될 거 같구요, 이제까지 봤던 다른 클러스터링과는 다르게, 데이터 간의 관계 자체가 데이터가 되는 것이고, 이걸 보통 "네트워크"라고 하는데, 이렇게 네트워크를 분류하는 것이 Markov Clustering 입니다.
댓글