[Recommendation] Data Sparsity

■ 데이터 희소도 란?

• 추천 시스템에서는 사용자×아이템 간 평점·행동 기록을 행렬 형태로 표현함
• 이 행렬에서 실제 기록이 있는 셀(유저가 아이템에 평점을 남긴 경우 등)은 매우 적고, 대부분의 셀은 빈 값(interaction이 없음)입니다.
• 데이터 희소도는
  $$ sparsity = 1 -  \frac {실제 행동 수} {(사용자 수) \times (아이템 수)} $$
  계산하며, 값이 클수록 “비어 있는” 비율이 높다는 의미입니다.
• 희소도가 높으면 전통적 유사도 기반 협업 필터링(“이웃 사용자 찾기”)이 어려워지고, 잠재 요인(latent factor) 모델이나 딥러닝 기반 모델이 더 유리해질 수 있습니다.

1) 개념 정의

• 희소행렬(Sparse Matrix)
  • 대부분의 원소가 0인 행렬을 뜻함
  • 예를 들어, 1,000명의 사용자와 10,000개의 상품이 있는 전자상거래 사이트에서 ‘사용자×상품’ 클릭 로그를 행렬로 만들면, 한 사용자가 클릭하는 상품은 극히 일부이므로 1,000×10,000=1,000만 칸 중 실제 값이 있는 칸은 수만 개에 불과합니다.
  • 이처럼 0이 압도적으로 많은 데이터를 효율적으로 저장·연산하기 위해 희소행렬 포맷을 사용합니다.
• CSR 포맷(Compressed Sparse Row)
  0이 아닌 원소들만 차례로 저장하고, 각 행(row) 이 시작되는 인덱스를 별도로 관리합니다.
  • data 배열: 0이 아닌 (non-zero) 값들의 순서 리스트
  • indices 배열: 각 값이 속한 열(column) 번호 리스트
  • indptr 배열: 각 행(row) 이 data에서 시작하는 위치를 가리키는 포인터 리스트
    이렇게 구성하면, 특정 행의 모든 비제로 값을 빠르게 찾을 수 있어 메모리와 연산 속도를 크게 절감합니다.
• COO 포맷(Coordinate List)
  비제로 원소 각각의 (행, 열, 값) 튜플을 나열한 형태입니다.
  • (row, col, value) 목록을 순차 저장
  • 추가·삭제가 잦은 초기 생성 단계나, 간단한 변환 시 편리합니다.
    다만, 대규모 연산 단계에서는 CSR처럼 행 또는 열 단위 접근이 최적화된 포맷으로 변환해 사용하는 것이 일반적입니다.
• Math(Sparse Matrix) x Computing(CSR Format/COO Format) 인듯함

2) 수학적 배경

• 행렬 곱셈(Matrix Multiplication) 
  • 두 행렬 $A$ 와 $B$ 를 곱할 때, 결과 행렬 $C$ 의 원소 $C_{ij}$ 는 다음과 같이 계산됨
  • 0이 아닌 원소끼리만 연산하므로, 희소행렬에서는  $A_{ik}\neq0$ 또는  $B_{kj}\neq0$ 인 경우만 고려합니다.
    $$ C = A \times B, \quad
    C_{ij} = \sum_k A_{ik} \, B_{kj}
    $$
• 공간 복잡도(메모리 사용량) 비교
  • 밀집 행렬(Dense) : 모든 $ m \times n$ 칸을 저장
  • 희소 행렬(Sparse) : 실제 값이 있는 칸(nnz; non-zero)만 저장
    $$ \text{Dense storage} = O(mn), 
    \quad
    \text{Sparse storage} = O(\mathrm{nnz})
    $$
• CSR 주요 구조
  1. data (nnz 길이)
  2. indices (nnz 길이)
  3. indptr (m+1 길이, 각 행의 시작·끝 인덱스)

import numpy as np
from scipy.sparse import coo_matrix, csr_matrix

# 1) 예제 밀집 행렬 생성
dense = np.array([
    [0, 0, 3, 0, 0],
    [5, 0, 0, 0, 7],
    [0, 2, 0, 4, 0],
])

# 2) COO 포맷 변환
coo = coo_matrix(dense)
print("COO data:", coo.data)
print("COO row indices:", coo.row)
print("COO col indices:", coo.col)

# 3) CSR 포맷 변환
csr = csr_matrix(dense)
print("CSR data:", csr.data)
print("CSR indices (cols):", csr.indices)
print("CSR indptr (row pointers):", csr.indptr)

# 4) 희소행렬 연산 예시: 행 단위 합 계산
row_sums = csr.sum(axis=1)
print("Row sums:\n", row_sums)

 

• coo.data: 0이 아닌 값을 나열한 배열
• coo.row, coo.col: 각각 값의 행(row) 번호, 열(col) 번호
• csr.data: 비제로 값들의 순서 목록 (COO와 동일 순서)
• csr.indices: 각 data 값이 놓인 열 번호
• csr.indptr: data 배열에서 각 행이 시작·끝나는 지점을 가리키는 포인터.
  • 길이가 행 개수 + 1 이며,
  • 예컨대 indptr = [0, 2, 4, 5] 이면
    • 0행의 비제로 원소는 data[0:2],
    • 1행은 data[2:4],
    • 2행은 data[4:5] 에 저장됨을 뜻합니다.

 해석 예시

COO data: [3 5 7 2 4]
COO row indices: [0 1 1 2 2]
COO col indices: [2 0 4 1 3]

CSR data: [3 5 7 2 4]
CSR indices (cols): [2 0 4 1 3]
CSR indptr (row pointers): [0 1 3 5]

Row sums:
 [[3]
  [12]
  [6]]

 

 

 

• COO 해석
  • (0,2)=3, (1,0)=5, (1,4)=7, (2,1)=2, (2,3)=4 임을 의미합니다.
• CSR 해석
  • indptr=[0,1,3,5] 이므로
    • 0행: data[0:1]=[3] → (0,2)=3
    • 1행: data[1:3]=[5,7] → (1,0)=5, (1,4)=7
    • 2행: data[3:5]=[2,4] → (2,1)=2, (2,3)=4
• 행 합 계산
  • row_sums 결과는 각 행에 있는 비제로 값들의 합입니다.
    • 0행 합 = 3
    • 1행 합 = 5+7 = 12
    • 2행 합 = 2+4 = 6