목차
※ 출처 : 그래프 머신러닝 (클라우디오 스타밀레 외, 김기성·장기식 옮김)
1. 행렬 분해(Matrix Factorization)란
1.1. 개념
$$X \approx S \times A$$
대규모 행렬 데이터를 두 개 이상의 작은 행렬들의 곱으로 나타내는 것을 말합니다. 일반적으로 원본 행렬 $X$를 원천 행렬(source matrix) $S$와 기여도 행렬(abundance matrix) $A$의 곱으로 근사합니다. 여기서 $S$는 데이터를 구성하는 기본 요소들을, $A$는 각 요소가 원본 데이터에 기여하는 정도를 의미합니다.
1.2. 활용
고차원 데이터의 잠재적인 패턴과 구조를 발견하고, 저차원 표현으로 압축하며, 노이즈를 제거하는 등의 목적으로 사용됩니다.
* 대표적인 활용 분야
- 추천 시스템의 협업 필터링
- 신호 처리
- 텍스트 마이닝과 토픽 모델링
- 생체 정보 분석
- 예시
. 영화 평점 데이터에서 사용자-영화 행렬을 분해하면 사용자 취향과 영화 장르 정보를 추출 가능
2. 행렬 분해의 수학적 배경
행렬 분해는 주어진 $m \times n$ 차원의 행렬 $X$를 원천 행렬 $S \in \mathbb{R}^{m \times d}$와 기여도 행렬 $A \in \mathbb{R}^{d \times n}$의 곱으로 나타내는 것입니다. 여기서 $d$는 잠재 차원의 개수를 가리킵니다. 목표는 $X$와 $S \times A$의 차이를 최소화하는 행렬 $S$, $A$를 찾는 것입니다. 이를 수식으로 표현하면:
$$\min \lVert X - S \times A \rVert^{2}_{F}$$
* $\lVert \rVert_F$ : 프로브니우스 노름(Frobenius norm)
※ 프로브니우스 노름(Frobenius Norm)
* 행렬의 노름(norm) 중 하나로, 행렬의 모든 원소 값에 대한 제곱 합의 제곱근
- 유클리드 노름이 벡터의 크기를 나타내듯, 프로브니우스 노름은 행렬의 크기를 나타내는 스칼라 값임
* $m \times n$ 행렬 $A = (a_{ij})$에 대해,
$$\lVert A \rVert_{F} = \sqrt{\sum_{i, j} a_{ij}^2}$$
* 연산이 간단하고 미분이 용이하여 최적화 문제에 적합
2.1. 원천 행렬(Source Matrix)와 기여도 행렬(Abundance Matrix)
* 원천 행렬(Source Matrix) $S$
- 데이터 $X$를 구성하는 기본 요소나 패턴
- 각 열 벡터는 하나의 기본 패턴을 의미
* 기여도 행렬(Abundance Matrix) $A$
- 각 기본 패턴이 원본 데이터 $X$에 기여하는 정도
- 원소 $A_{ij}$ : $j$번째 패턴이 $i$번째 데이터 포인트에 기여하는 정도
* 예시
- 텍스트 데이터 $X$가 문서-단어 행렬일 때,
. $S$ : 단어 $m$, 토픽 $d$ 행렬
. $A$ : 토픽 $d$, 문서 $n$ 행렬로, 각 문서가 토픽을 포함하는 정도
3. 대표적인 행렬 분해 기법
3.1. 비음수 행렬 분해(NMF; Non-negative Matrix Factorization)
$$X \approx W \times H$$
* 행렬 $X \in \mathbb{R}^{m \times n}$를 두 개의 비음수 행렬 기저 행렬 $W \in \mathbb{R}^{m \times d} \ge 0 $, 계수 행렬 $H \in \mathbb{R}^{d \times n} \ge 0 $의 곱으로 분해
* 비음수 제약 조건으로 인해 부분적으로 가산적인 구조를 가지므로 해석이 용이
* 텍스트 마이닝, 음성 처리, 이미지 처리에 활용
※ 비음수 제약 조건
* 분해된 행렬 $W$, $H$의 모든 원소가 0 이상의 값을 갖는 조건
- 이 제약 조건으로 인해 데이터 $X$가 $W$와 $H$의 곱으로 표현될 때, 부분적으로 합쳐지는 구조를 가짐
* 파이썬 예제
① 예제 그래프 생성
import networkx as nx
G = nx.karate_club_graph() # 예제 그래프
nx.draw(G) # 그래프 시각화
② 그래프 인접 행렬 추출
A = nx.to_numpy_array(G) # 그래프 인접 행렬
print("인접 행렬 크기:", A.shape)
print("인접 행렬:\n", A)인접 행렬 크기: (34, 34)
인접 행렬:
[[0. 4. 5. ... 2. 0. 0.]
[4. 0. 6. ... 0. 0. 0.]
[5. 6. 0. ... 0. 2. 0.]
...
[2. 0. 0. ... 0. 4. 4.]
[0. 0. 2. ... 4. 0. 5.]
[0. 0. 0. ... 4. 5. 0.]]
③ NMF 모델 학습 및 실행
from sklearn.decomposition import NMF
# NMF 모델 학습
nmf = NMF(n_components=5, # 분해할 성분 개수
init="nndsvd", # 초기화 방법
max_iter=200) # 최대 반복 횟수
W = nmf.fit_transform(A) # 기저 행렬(W)
H = nmf.components_ # 계수 행렬(H)
print("기저 행렬(W) 크기:", W.shape)
print("계수 행렬(H) 크기:", H.shape)기저 행렬(W) 크기: (34, 5)
계수 행렬(H) 크기: (5, 34)
④ NMF 결과 시각화
import matplotlib.pyplot as plt
fig, subs = plt.subplots(ncols=2, figsize=(10, 5))
# 기저 행렬(W) 시각화
subs[0].imshow(W, cmap="Reds")
subs[0].set_title("W")
# 계수 행렬(H) 시각화
subs[1].imshow(H, cmap="Reds")
subs[1].set_title("H")
plt.show()
3.2. 특이값 분해(SVD; Singular Value Decomposition)
$$X = U \Sigma V^T$$
* 행렬 $X$를 직교 행렬 $U$, $V^T$와 대각 행렬 $\Sigma$ 세 개의 행렬 곱으로 분해
* 데이터의 랭크와 고유값, 고유벡터를 계산할 수 있음
* 활용
- 차원 축소 및 데이터 압축
. $\Sigma$의 큰 특이값에 대응하는 $U$, $V$의 열 벡터만 선택하여 압축
. 데이터 차원을 축소하고 노이즈를 제거
- 노드 임베딩 및 시각화
. $U$, $V$의 열 벡터를 노드 임베딩 벡터로 활용
. 상위 k개의 열 벡터를 선택하여 k차원 공간에 노드를 임베딩하고 시각화
- 그래프 클러스터링
. $U$, $V^T$의 열 벡터를 기반으로 노드 클러스터링 수행
- 신호 분석 및 주파수 영역 변환
. $\Sigma$의 특이값은 그래프 신호의 주파수 성분을 나타냄
. 주파수 영역에서 분석하거나 필터링을 수행할 수 있음
* 파이썬 예제
① SVD 실행
import numpy as np
U, Sigma, Vt = np.linalg.svd(A, full_matrices=False) # SVD
Sigma_matrix = np.diag(Sigma)
print("U 크기:", U.shape)
print("Sigma 크기:", Sigma_matrix.shape)
print("Vt 크기:", Vt.shape)U 크기: (34, 34)
Sigma 크기: (34, 34)
Vt 크기: (34, 34)
② SVD 결과 시각화
fig, subs = plt.subplots(ncols=3, figsize=(15, 5))
# U 시각화
subs[0].imshow(U, cmap="Reds")
subs[0].set_title("U")
# Sigma 시각화
subs[1].imshow(Sigma_matrix, cmap="Reds")
subs[1].set_title("Sigma")
# V 시각화
subs[2].imshow(Vt, cmap="Reds")
subs[2].set_title("Vt")
plt.show()
3.3. 주성분 분석(PCA; Principal Component Analysis)
$$X \approx u + \sum z_i p_i$$
* 데이터 $X$를 평균 벡터 $u$와 주성분 벡터 $p_i$, 주성분 벡터에 투영된 X의 값인 $z_i$의 선형조합으로 나타냄
* 고차원 데이터의 차원을 낮추면서 가능한 많은 변동성을 보존하는 기법
* 차원 축소, 데이터 시각화, 노이즈 제거에 활용
* 파이썬 예제
① PCA 실행
from sklearn.decomposition import PCA
pca = PCA(n_components=5) # PCA 모델 생성
zi = pca.fit_transform(A) # PCA 모델 학습 및 변환
u = pca.mean_ # 평균 벡터(u)
pi = pca.components_ # 주성분 벡터(pi)
print("투영 벡터(zi) 크기:", zi.shape)
print("평균 벡터(u) 크기:", u.shape)
print("주성분 벡터(pi) 크기:", pi.shape)투영 벡터(zi) 크기: (34, 5)
평균 벡터(u) 크기: (34,)
주성분 벡터(pi) 크기: (5, 34)
② PCA 결과 시각화
fig, subs = plt.subplots(ncols=2, figsize=(10, 5))
# 투영 벡터(zi) 시각화
subs[0].imshow(zi, cmap="Reds")
subs[0].set_title("zi")
# 계수 행렬(H) 시각화
subs[1].imshow(pi, cmap="Reds")
subs[1].set_title("pi")
plt.show()
4. 행렬 분해의 활용 사례
4.1. 링크 예측(Link Prediction)
* 그래프 데이터에서 노드 간 링크 존재 여부를 예측하는 문제
- (소셜 네트워크) 친구 관계 예측
- (생물학 네트워크) 단백질 간 상호작용 예측
4.2. 노드 임베딩(Node Embedding)
* 그래프 데이터의 노드를 낮은 차원의 밀집 벡터로 변환하는 작업
- DeepWalk, Node2Vec 기법
4.3. 그래프 신호 처리(Graph Signal Processing)
* 그래프 신호(Graph Signal)
- 그래프 구조의 각 노드에 스칼라 값이 할당된 형태
- 예시
. (교통 네트워크) 각 도로 구간의 혼잡도
. (센서 네트워크) 각 센서의 측정값
. (소셜 네트워크) 각 사용자의 특성값
. (분자 구조) 각 원자의 전하량
* 그래프 신호의 필터링, 압축, 보간에 이용
- 그래프 신호를 푸리에 기저(Fourier basis)로 분해
※ 그래프 푸리에 기저(Graph Fourier Basis)
* 그래프 라플라시안 행렬(Graph Laplacian Matrix)의 고유벡터(eigenvectors)로 구성되며, 이 고유벡터들은 그래프 구조를 반영하는 기저 함수 역할을 함
- 그래프 신호를 그래프 라플라시안의 고유벡터들의 선형 조합으로 표현할 수 있음
$$f = \sum \alpha_i \phi_i$$
- $f$ : 그래프 신호, $\phi_i$ : 그래프 푸리에 기저(고유벡터), $\alpha_i$ : 계수
※ 그래프 라플라시안 행렬(Graph Laplacian Matrix)
* 그래프의 구조적 특성을 포착하는 행렬
$$L = D - A$$
- $D$ : 차수 행렬(Degree matrix)
. 대각 행렬로 $D(i, i)$는 $i$번째 노드의 차수
- $A$ : 인접 행렬(Adjacency matrix)
* 주요 특성
- 대칭 행렬
- 고유값은 0 이상
- 고유벡터들은 그래프 푸리에 기저를 형성
4.4. 그래프 클러스터링(Graph Clustering)
* 그래프의 구조적 유사성을 포착
- 커뮤니티 탐지