희소벡터와 희소행렬: 0이 대부분인 데이터를 효율적으로 다루는 법

대부분이 0인 벡터와 행렬

희소벡터(Sparse Vector)는 벡터의 대부분 요소가 0인 벡터 구조이고, 희소행렬(Sparse Matrix)은 행렬 내 대부분의 원소가 0인 행렬 구조다. 비희소(Dense) 구조와 대비되는 개념으로, 0이 아닌 값(non-zero value)이 극히 일부인 데이터 표현 방식을 가리킨다. 주로 고차원 데이터에서 발생하며, 메모리와 계산 효율성 측면에서 중요한 의미를 가진다.

어디서 이렇게 희소해지는가

자연어 처리에서는 문서-단어 행렬(Document-Term Matrix, DTM)이 문서 집합에서 각 문서를 단어 출현 빈도로 표현하고, TF-IDF(Term Frequency-Inverse Document Frequency)로 단어의 중요도를 계산한다. 영어 어휘가 100,000개인 말뭉치에서 한 문서는 보통 100~200개 단어만 사용하므로, 99.8% 이상이 0이 된다.

원-핫 인코딩(One-Hot Encoding)도 범주형 변수를 이진 벡터로 변환하는 대표적인 사례다. n개 범주가 있을 때 n차원 벡터에서 하나의 값만 1, 나머지는 0으로 표현한다. 예를 들어 [남성, 여성]은 [1,0] 또는 [0,1]로 표현된다.

추천 시스템에서는 사용자-아이템 평점 행렬에서 대부분의 사용자가 일부 아이템만 평가하는데, 넷플릭스 사용자-영화 평점 행렬은 99% 이상이 빈 값이다.

그래프·네트워크 분석에서는 인접 행렬(Adjacency Matrix)에서 노드 간 연결이 희소한 경우가 많다. 소셜 네트워크에서 한 사용자는 전체 사용자 중 극히 일부와만 연결된다.

0이 아닌 값만 기억하는 저장 방식

COO, 좌표만 남긴다

COO(Coordinate Format)는 0이 아닌 값과 해당 값의 인덱스(좌표)만 저장한다. 형식은 (row_idx, col_idx, value)이며, 간단하고 직관적이나 검색 효율성은 낮다.

CSR, 행 방향 순회에 강하다

CSR(Compressed Sparse Row)은 행 포인터, 열 인덱스, 값 배열을 사용해 행 방향 순회에 효율적이며, SciPy와 같은 과학 계산 라이브러리에서 주로 사용된다.

CSC, 열 방향으로 뒤집으면

CSC(Compressed Sparse Column)는 CSR과 유사하나 열 기준으로 압축해 열 방향 순회에 효율적이다.

딕셔너리로 좌표를 매핑하는 방법

해시맵을 사용해 (row, col) → value로 매핑하는 방식으로, 파이썬 같은 고수준 언어에서 구현이 간단하다.

sparse_dict = {(0, 1): 5, (1, 3): 7, (4, 2): 9}  # (행, 열): 값

메모리와 연산에서 얼마나 이득인가

일반 행렬은 m×n 행렬에 m×n 메모리 공간이 필요한 반면, 희소 행렬은 0이 아닌 원소 개수(nnz)에 비례한 메모리만 쓴다. 밀도가 p인 m×n 행렬을 기준으로 일반 표현은 m×n×sizeof(value) 바이트, 희소 표현은 nnz×(sizeof(value) + sizeof(index)) 바이트이며, 일반적으로 p < 0.5일 때 희소 표현이 더 효율적이다.

연산 측면에서도 덧셈/뺄셈은 O(nnz) 시간 복잡도로 밀집 표현 대비 효율적이고, 곱셈은 특수한 알고리즘을 쓰면 O(nnz) ~ O(nnz²)까지 가능하다. 전치(Transpose)는 저장 형식에 따라 효율성 차이가 있다.

SciPy·R·MATLAB에서 직접 만들어보기

Python - SciPy

from scipy import sparse

# 희소행렬 생성
row = [0, 1, 2, 0]
col = [0, 1, 2, 2]
data = [1, 2, 3, 4]
sparse_matrix = sparse.csr_matrix((data, (row, col)), shape=(3, 3))

# 희소행렬 연산
result = sparse_matrix.dot(sparse_matrix.T)

R - Matrix 패키지

library(Matrix)
# 희소행렬 생성
sparse_matrix <- sparseMatrix(i = c(1,2,3), j = c(1,2,3), x = c(1,2,3))

MATLAB의 희소행렬

% 희소행렬 생성
i = [1, 2, 3]; j = [1, 2, 3]; s = [1, 2, 3];
sparse_matrix = sparse(i, j, s, 100, 100);

검색 엔진과 추천 알고리즘이 희소행렬을 다루는 법

검색 엔진의 역색인(Inverted Index)은 문서-단어 매핑을 희소행렬로 구현하고, 문서 클러스터링에서도 유사 문서 그룹화에 희소 표현을 활용한다. 구글 검색 엔진은 수조 개의 웹페이지에서 수백만 단어를 희소행렬로 처리한다.

추천 시스템에서는 협업 필터링(Collaborative Filtering)이 사용자-아이템 희소행렬을 기반으로 하고, 행렬 분해(Matrix Factorization)로 희소행렬을 저차원 밀집행렬로 분해한다. 넷플릭스 추천 알고리즘은 수억 명 사용자 × 수만 개 콘텐츠의 희소행렬을 처리한다.

⤢✕

빅데이터 분석에서는 고차원 희소 특징 벡터를 생성하는 특징 추출(Feature Extraction)과 희소 데이터의 효율적 표현을 위한 차원 축소가 함께 쓰인다. 소셜 미디어 데이터에서 해시태그 분석이 대표적으로, 수백만 해시태그 중 소수만 사용되는 구조를 보인다.

희소성이 지나치면 생기는 문제와 대응

데이터가 너무 희소하면 패턴 학습이 어려워지는 희소성의 저주(Curse of Sparsity)와, 고차원에서의 데이터 희소성 문제인 차원의 저주(Curse of Dimensionality)가 있다. 일부 행렬 연산에서는 희소 표현이 오히려 비효율적일 수 있다는 연산 복잡성 문제도 있다.

대응 방안으로는 SVD(Singular Value Decomposition)로 희소행렬을 저차원 밀집행렬로 근사하거나, PCA(Principal Component Analysis)로 주성분 기반 차원 축소를 하거나, t-SNE로 비선형 차원 축소 후 시각화하는 차원 축소 기법이 있다. 과적합 방지와 일반화 성능 향상을 위한 정규화(Regularization), 고차원 희소 벡터를 저차원 밀집 벡터로 바꾸는 임베딩(Embedding)도 함께 쓰인다.

⤢✕

딥러닝은 희소 데이터를 어떻게 다루는가

Word2Vec, GloVe, FastText는 희소한 원-핫 벡터를 밀집 임베딩으로 변환한다. 예컨대 "apple"의 원-핫 벡터(10만 차원)는 밀집 임베딩(300차원)으로 바뀐다.

Dropout은 무작위로 뉴런을 0으로 만들어 희소성을 유도하고, ReLU 활성화 함수는 음수 입력을 0으로 만들어 희소 활성화를 만든다. Attention 메커니즘은 관련 요소에만 집중해 희소 가중치를 생성한다.

그래프 신경망(GNN)은 희소 그래프 구조에서 노드 표현을 학습하며, 메시지 전달(Message Passing) 알고리즘으로 희소 연결을 활용한다.

고차원 시대에 더 중요해지는 표현법

희소벡터와 희소행렬은 고차원 데이터의 효율적 처리를 위한 핵심 개념으로, 메모리 사용량 감소와 연산 속도 향상에 크게 기여한다. 자연어 처리, 추천 시스템, 그래프 분석 등 다양한 분야에서 활용되며, 희소성의 장점을 최대화하고 단점을 보완하는 알고리즘 발전이 지속적으로 이루어지는 중이다.