희소 데이터
IT 위키
희소 데이터(稀疏-, 영어: Sparse data)는 데이터의 대부분이 0 또는 비어 있는 값으로 이루어진 데이터를 말한다. 반대로, 대부분의 값이 유효한 값을 가지는 데이터는 조밀 데이터(密-, Dense data)라고 한다. 희소 데이터는 수학, 통계학, 데이터 과학, 인공지능 등 다양한 분야에서 다루어지며, 저장 및 연산 효율성을 위해 특별한 표현 방식과 알고리즘이 사용된다.
개요
- 희소 데이터는 전체 크기에 비해 실제로 유의미한 값이 차지하는 비율이 매우 낮다.
- 예를 들어, 1000차원 벡터에서 990개의 값이 0이고 10개만이 유효한 경우, 이는 희소 벡터라고 한다.
- 희소성(sparsity)의 정도는 데이터에서 0이 차지하는 비율로 정의되며, 보통 70% 이상이 0일 경우 희소 데이터로 간주한다.
표현 방식
희소 데이터를 효율적으로 저장하기 위해 다양한 압축 및 표현 기법이 사용된다.
표현 방식
희소 데이터를 효율적으로 저장하기 위해 다양한 압축 및 표현 기법이 사용된다.
- 비트맵 인코딩(Bitmap encoding) : 값의 위치를 비트 벡터로 표시
- 0이 아닌 원소의 위치를 1로, 나머지를 0으로 표현한다.
- 실제 값은 별도의 값 배열(value array)에 저장하여 (비트맵, 값) 쌍으로 관리한다.
- 예시: [0, 5, 0, 0, 3, 0, 8] → 비트맵 [0,1,0,0,1,0,1], 값 [5,3,8]
- 런렝스 인코딩(Run-Length Encoding, RLE) : 동일 값이 연속적으로 반복되는 구간을 값과 길이 쌍으로 기록
- 동일한 값이 반복될 때마다 (값, 반복 길이) 형태로 압축 저장한다.
- 0이 긴 구간으로 반복될 경우 압축 효율이 매우 높다.
- 예시: [0, 0, 0, 1, 1, 0, 0] → (0,3), (1,2), (0,2)
- COO(Coordinate List) 형식 : 0이 아닌 원소의 좌표와 값을 각각 리스트로 저장
- 행 인덱스(row), 열 인덱스(col), 값(value)을 병렬 배열로 구성한다.
- 구조가 단순하고 직관적이지만, 중복 좌표 처리나 정렬에 추가 비용이 든다.
- 예시: (행, 열, 값) = [(0,2,5), (1,0,3), (2,1,7), (2,3,2)]
- CSR(Compressed Sparse Row) 형식 : 희소 행렬을 행 단위로 압축하여 저장
- 0이 아닌 값(value), 열 인덱스(col_idx), 행 포인터(row_ptr) 배열로 구성한다.
- 행별 데이터 경계를 명확히 관리할 수 있어 행렬-벡터 곱 연산이 빠르다.
- 예시: value=[5,3,7,2], col_idx=[2,0,1,3], row_ptr=[0,1,2,4]
- CSC(Compressed Sparse Column) 형식 : CSR과 유사하나 열 단위로 압축
- 값(value), 행 인덱스(row_idx), 열 포인터(col_ptr) 배열로 구성된다.
- 전치(transpose)나 열 단위 연산에서 효율적이다.
- 예시: value=[3,7,5,2], row_idx=[1,2,0,2], col_ptr=[0,1,2,3,4]
활용
- 머신러닝 : 자연어 처리에서 원-핫 인코딩(One-hot encoding) 벡터, 추천 시스템의 사용자-아이템 행렬
- 통계학 : 대규모 설문조사나 로그 데이터에서 결측치나 0이 많은 데이터셋
- 컴퓨터 그래픽스 : 이미지나 영상 데이터의 압축 표현
- 정보 검색 : 문서-단어 행렬(TF-IDF)에서 대부분의 단어가 등장하지 않는 희소 벡터
장점
- 데이터 저장 공간 절약
- 불필요한 연산을 줄여 계산 효율 향상
- 대규모 데이터 처리 가능
단점
- 일반적인 선형대수 연산을 그대로 적용하기 어려움
- 특수한 자료구조 및 알고리즘이 필요
- 압축률은 데이터 분포에 따라 달라짐
같이 보기
참고 문헌
- Gilbert, J. R., Moler, C., & Schreiber, R. (1992). Sparse Matrices in MATLAB: Design and Implementation. SIAM Journal on Matrix Analysis and Applications.
- Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning. MIT Press, 2016.
