희소 행렬
작성 완료
-
희소 행렬(sparse matrix)
: 원소 대부분 $0$인 행렬
-
희소성(sparsity)
: 행렬의 전체 원소 중 $0$인 원소의 비율
-
희소(sparse)하다고 말할 수 있는 정확한 정의는 없지만 일반적인 기준은 $0$이 아닌 원소가 대략 행 또는 열의 수만큼 있는 것이다
-
의미있는 원소($0$이 아닌 수)가 거의 없으므로 일반적인 행렬과 같이 자료를 저장하면 메모리 측면에서 매우 비효율적이다
-
그렇기에 $0$이 아닌 원소만 저장하는 자료구조를 사용하여 메모리를 절약한다
-
대표적으로 자연어 처리에서 텍스트를 토큰화할 때 희소 행렬의 자료구조를 사용한다 (전체 글에서 사용된 유니크한 단어 개수는 매우 많지만 문장 별로 사용된 유니크한 단어 개수는 적다)
-
만약 $0$이 의미있는 원소로 사용된다면 문제가 생긴다 ($0$은 저장을 안하므로)
import numpy as np
arr = np.array([[1, 2, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 3, 0], [0, 0, 4, 0, 0], [5, 0, 0, 0, 0]])
print(arr) # 25개의 원소 중 19개가 0인 희소 행렬
-
(row, column)을 value로 매핑한 딕셔너리 구조
from scipy.sparse import dok_matrix
dok = dok_matrix((5, 5), dtype=np.float32)
for i in range(5):
for j in range(5):
dok[i, j] = i + j # 원소를 갱신, 원소가 0이라면 저장하지 않음
print(dok.toarray())
dok[0].nnz, dok[1].nnz # nnz는 0이 아닌 원소의 개수
-
각 행마다 열의 인덱스와 값을 하나의 리스트로 저장하는 구조
from scipy.sparse import lil_matrix
lil = lil_matrix(arr)
print(lil.rows) # 행마다 0이 아닌 값의 열 인덱스
print(lil.data) # 행마다 0이 아닌 값을 저장
-
(row, column, value) 튜플을 리스트에 저장한 구조
from scipy.sparse import coo_matrix
coo = coo_matrix(arr)
print(coo.row, coo.col, coo.data)
for row, col, value in zip(coo.row, coo.col, coo.data):
print(f'{row + 1}행 {col + 1}열에 저장된 값: {value}')
-
행을 기준으로 $0$이 아닌 값을 압축시킨 구조
from scipy.sparse import csr_matrix
csr = csr_matrix(arr)
print(arr)
csr.nnz # 0이 아닌 원소의 개수
csr.indptr # index pointer, 처음 값은 0, 마지막 값은 nnz, i번째 인덱스의 값은 i번째 행까지 0이 아닌 원소의 개수, 길이는 row + 1
csr.indices # 0이 아닌 원소의 열 인덱스, 길이는 nnz
csr.data # 0이 아닌 원소 목록, 길이는 nnz
-
열을 기준으로 $0$이 아닌 값을 압축시킨 구조
from scipy.sparse import csc_matrix
csc = csc_matrix(arr)
csc.indptr, csc.indices, csc.data