Sparse Matrix
Sparse Matrix(희소 행렬)는 행렬의 요소 대부분이 0인 행렬을 의미한다. 의미있는 값이 희소하다고 생각하면 이해가 편한데, 대부분의 값이 0이므로 일반적인 행렬과 같이 저장할 경우 연산의 낭비가 심하다. 이를 극복하기 위해 고안된 여러 효율적인 표현법이 있다. 대표적인 방법으로는 Coordinate List(COO)와 Compressed Sparse Row(CSR)가 있다.
Sparse Matrix Format
위와 같은 Sparse Matrix가 있을 때. 0이 아닌 원소들의 좌표는 다음과 같다.
•
Coordinate List(COO)
COO는 이름에서 알 수 있듯, 0이 아닌 원소들의 좌표를 이용해 기록하는 방식이다. 형식의 Tuple을 List로 묶어 표현하는 방식이 일반적이다. 위의 행렬의 경우 다음과 같은 형식과 같이 표현(저장)된다.
Sparse Matrix를 구성하기 위한 빠른 Format이며, 벡터연산을 통해 다른 Format과의 상호 변환이 빠르지만 슬라이싱과 산술 연산이 어렵다는 단점이 있다. Python에선 Scipy를 이용하면 쉽게 구현할 수 있다.
import numpy as np
from scipy.sparse import coo_matrix
row = np.array([0, 1, 2, 2, 3, 3, 4])
col = np.array([0, 1, 2, 3, 1, 3, 4])
data = np.array([1, 2, 5, 1, 1, 1, 1])
coo_matrix((data, (row, col)), shape=(5, 5)).toarray()
Python
복사
Compressed Sparse Row(CSR)
CSR는 행(Row)을 압축시켜, COO보다 더 짧은 벡터를 이용해 Sparse Matrix를 표현하는 방식이다. 압축은 좌표값을 생략하고, 대신 각 행이 시작되는 지점을 기록하는 방식으로 이루어진다.
•
2, 3번 행에 0이 아닌 원소가 2개이므로, 행 벡터에 2, 3이 두 번 씩 나오는것을 볼 수 있다. 이 처럼 COO는 좌표를 표현하기 위해 중복적으로 값을 사용해야하는데, 행렬이 커지면 커질수록 이런 중복이 많아진다. 이 중복을 과감히 제거하고, 행이 시작하는 지점을 표시해주는 방식으로 벡터의 길이를 줄일 수 있다. 이처럼 행 좌표의 중복을 제거해서 압축시킨 행렬을 Compressed Sparse Row(CSR), 열 좌표의 중복을 제거해서 압축시키면 Compressed Sparse Column (CSC)라고 부른다. (이 글에선 CSR만 설명한다)
그럼 실제 CSR 형태로 Sparse Matrix를 한번 표현해 보자.
COO Format을 이용해 행, 열, 값 벡터를 표현하면 다음과 같다.
•
Row :
•
Column :
•
Value :
CSR Format은 Row 좌표 대신, 각 행이 시작하는 Value의 좌표를 이용해 Row를 표현한다. 각 행이 시작되는 Value의 좌표(Index)라는 개념이 직관적으로 이해하기 어려운데, 그림으로 표현하면 다음과 같다.
(Row에 마지막 값에는 행 변환이 끝났음을 표시하기 위해 Value의 갯수를 넣어준다)
•
Row :
•
Column :
•
Value :
CSR은 일때 메모리를 절약할 수 있다.(NNZ는 원소갯수, m,n은 행렬 길이) 또한 효율적인 산술 연산, 벡터곱을 지원한다. CSR 역시 Python에선 Scipy를 이용하면 쉽게 구현할 수 있다.
import numpy as np
from scipy.sparse import coo_matrix
row = np.array([0, 1, 2, 4, 6, 7])
col = np.array([0, 1, 2, 3, 1, 3, 4])
data = np.array([1, 2, 5, 1, 1, 1, 1])
csr_matrix((data, col, row), shape=(5,5)).toarray()
Python
복사