희소행렬(sparse_matrix)과 CSR, COO

 추천 알고리즘은 크게 협업 필터링, 컨텐츠 필터링이 있다. 이 중 협업 필터링을 구현하려면 사용자 간의 유사도를 분석해야 한다. 이 때 각 사용자별 제품, 서비스 등에 대한 선호도를 알아야할 경우가 있다. 제품, 서비스 등의 수가 많아진다면, 0으로 나타내지는 항이 많을 것이다. 사용자가 모든 제품, 서비스를 이용했을 가능성은 매우 낮기 때문이다.

희소 행렬(Sparse Matrix)

 희소 행렬(Sparse Matrix)란 그림1과 같이 대부분의 값이 0인 행렬을 말한다. 그림1과 같은 행렬을 다룰 때는 문제가 되지 않겠지만, 크기가 매우 큰 희소 행렬을 생각하면 메모리 낭비를 예상할 수 있다. 이를 좀 더 효율적으로 표현 및 저장할 수 있는 방법이 바로 COO(Coordinate Format), CSR(Compressed Sparse Row Format)이다.

그림1. 희소 행렬(Sparse Matrix)

COO(Coordinate Format)

 0을 제외한 값만을 (행 번호, 열 번호, 값) 형태로 저장하는 형식을 말한다. 파이썬의 라이브러리 scipy를 사용하면 쉽게 구현할 수 있다. 아래의 코드는 그림1의 행렬을 COO(Coordinate Format)으로 나타내는 코드이다.

 

from scipy import sparse

mat = [[1, 0, 2, 0, 0, 0], 
       [0, 9, 0, 0, 0, 0], 
       [1, 7, 0, 0, 0, 0], 
       [0, 0, 3, 0, 0, 0], 
       [0, 1, 4, 0, 0, 0], 
       [0, 0, 0, 5, 0, 0]]
print("희소 행렬 mat:\n")
for row in mat:
    print(row)

coo = sparse.coo_matrix(mat)
print("\nCoo 표현방식:\n", coo)

그림2와 같은 출력을 확인할 수 있다.

 

그림2. 희소 행렬의 COO 표현

0을 제외한 항이 (행 번호, 열 번호), 값 순으로 출력되는 것을 확인할 수 있다.

 

CSR(Compressed Sparse Raw)

 COO 방식에서 좀 더 발전한 형태라고 할 수 있다. 그림2의 COO 행렬의 행 번호를 보면 비내림차순임을 확인할 수 있다. 여기서 반복되는 행 번호를 압축하여 표현할 수 있다. 각 행번호가 시작되는 인덱스만을 표시한다면 반복되는 값을 줄여 메모리 낭비를 최소화시킬 수 있는 것이다. 만약 그림2의 행 번호가 시작되는 인덱스를 표현한다면 [0, 2, 3, 5, 6, 8, 9]로 표현할 수 있을 것이다. 마지막 값은 누적 개수이다. 아래의 코드는 그림1 행렬을 CSR 행렬로 표현하는 코드이다.

from scipy import sparse

mat = [[1, 0, 2, 0, 0, 0], 
       [0, 9, 0, 0, 0, 0], 
       [1, 7, 0, 0, 0, 0], 
       [0, 0, 3, 0, 0, 0], 
       [0, 1, 4, 0, 0, 0], 
       [0, 0, 0, 5, 0, 0]]
print("희소 행렬 mat:\n")
for row in mat:
    print(row)

csr = sparse.csr_matrix(mat)
print("\nCSR 표현방식:\n", csr)

그림3과 같은 출력을 확인할 수 있다.

그림3. 희소행렬의 CSR 표현

여기서 이상한점을 하나 발견할 수 있는데, COO와 CSR의 출력값이 동일하다는 점이다. 이는 python 내부적으로 저장방식만 차이가 있고, 출력을 할 때는 각 값에 관한 정보를 그대로 출력하기 때문이다.