파이썬 scipy 희소행렬 설명 (coo, csr, dok)

파이썬 sklearn을 사용하다 보면, 희소행렬(sparse matrix)을 반환해줄 때가 있습니다.

from sklearn.feature_extraction.text import CountVectorizer

s = ['I love you', 'you love me']
count_vec = CountVectorizer()
m = count_vec.fit_transform(s)
m

 

toarray 메서드를 이용하면 흔히 사용하는 넘파이 배열로 변환할 수 있지만, 애초에 왜 희소행렬을 반환해주는가 의문이 생깁니다.

m.toarray()

 

희소행렬을 사용하는 이유

위에서는 두 개의 문장을 2 x 3 크기의 행렬로 바꾸는 작은 예시를 들었지만, 실전에서는 대규모 행렬을 다루어야 하는 경우가 흔합니다. 이 경우 메모리 문제가 생길 때 고려해볼 수 있는 것이 희소행렬입니다.

 

예를 들어 추천 시스템을 만들기 위해 어떤 고객이 어떤 영화에 별점을 몇 개 주었는지를 나타내는 행렬을 이용하고자 합니다. 그런데 고객은 100만 명이 있고 영화 10만개가 있다고 하겠습니다. 그러면 100만 x 10만 크기의 행렬을 만들어야 합니다. 원소 하나가 1바이트(int8)이라 해도 1테라바이트 크기의 메모리가 필요합니다. 

 

그런데 위 행렬은 원소가 대부분 0인 희소행렬일 것입니다. 사람 한 명이 영화를 아무리 많이 봤자 1만 개보다는 적을 것입니다. 그러면 나머지 9만 개 영화에 대해서는 행렬에 0으로 표현이 됩니다. 

 

따라서 이 경우 개념적으로는 행렬로 생각하는 게 편한 경우라도, 실제 데이터는 다르게 표현하는 것이 좋습니다. 희소행렬을 표현하는 방식에는 coo, csr 등이 있고 아래에서 살펴볼 것입니다. 간단하게 이야기하자면, 원소 값이 0이 아닌 부분에 대해서만 좌표와 값을 저장하고 나머지는 모두 0으로 간주하는 것입니다.

 

물론 커다란 행렬이더라도 대부분의 원소가 0인 행렬이 아니라면, 데이터의 부담을 온전히 져야 하기 때문에 다른 알고리즘을 찾아야 할지도 모릅니다. 이 경우에는 희소행렬과 반대되는 개념으로 밀집행렬(dense matrix)라고 부릅니다.

 

COO matrix

파이썬의 사이파이(scipy)에서 행렬의 희소 표현을 지원합니다. 예를 들어 아래와 같은 행렬이 있다고 하겠습니다. 

 

 

위 행렬은 5개 원소 빼고는 모두 값이 0인 행렬입니다. 여기서 0이 아닌 원소에만 주목해서 보면, 각각의 원소를 3개의 리스트로 간단히 표현할 수 있습니다. 즉 각 원소의 행 인덱스를 담은 리스트, 각 원소의 열 인덱스를 담은 리스트, 그리고 원소의 값을 담은 리스트로 행렬을 온전히 표현할 수 있습니다.

 

코드를 보겠습니다.

from scipy.sparse import coo_matrix

row = [0, 0, 0, 1, 2] # 행 인덱스를 담은 리스트
col = [0, 1, 2, 2, 3] # 열 인덱스를 담은 리스트
data = [2, 4, 2, 1, 5] # 원소 값을 담은 리스트

m = coo_matrix((data, (row, col)))
m

 

보시다시피 0이 아닌 원소 값 5개의 행 인덱스를 row에, 열 인덱스는 col에 담았습니다. 이를 scipy.sparse.coo_matrix에 넘겨주면 희소행렬이 만들어집니다. 원소 값이 0인 부분을 무시하고 나머지의 좌표와 값만 저장하는 것입니다.

 

빨간 색 숫자는 각 원소의 행 인덱스를 나타낸다.

 

위와 같이 희소행렬을 표현하는 방식을 coordinate format이라고 합니다. 각 원소의 좌표(coordinate)를 data와 함께 넘겨주었기 때문입니다.

 

참고로 m.row, m.col, m.data를 통해 0 아닌 원소의 좌표와 값에 접근할 수 있습니다.

m.data

 

CSR matrix

coo 방식에서 행 인덱스를 나타내는 리스트는 [0, 0, 0, 1, 2]이었습니다. 이는 행렬의 첫 번째 행에 0이 아닌 원소가 3개 있다는 의미입니다. 첫 번째 행에 원소가 3개 있다는 것을 알기 위해 굳이 0을 세 번 반복할 필요는 없습니다.

 

CSR(Compressed Sparse Row) 방식에서는 이러한 반복까지 줄여줍니다. 아래 코드를 보고 이어서 설명하겠습니다.

from scipy.sparse import csr_matrix

indices = [0, 1, 2, 2, 3]
indptr = [0, 3, 4, 5]
data = [2, 4, 2, 1, 5]
m = csr_matrix((data, indices, indptr))
m

 

위 코드에서 indices는 열 인덱스로서, coo 방식의 col과 같습니다. coo 방식과 다른 부분은 indptr입니다. indptr의 값은 [0, 3, 4, 5]입니다. 이를 보면 'data[0:3]가 첫 번째 행의 원소들이고, data[3:4]가 두 번째 행, data[4:5]가 세 번째 행의 원소 값이구나'라는 걸 알 수 있습니다.

 

이 같은 방식으로 indptr은 data의 구간을 나누어서 어디부터 어디까지가 몇 번째 행인지를 알려줍니다. 이 방식대로라면 indptr은 행 개수+1의 길이를 가지게 됩니다.

 

괄호가 쳐진 빨간 숫자가 indptr의 처음 세 원소들이다.

 

보시면 indptr은 coo 방식의 row보다 길이가 1 짧습니다. 0이 아닌 값이 반복적으로 등장하는 행(row)이 있을 때, coo 방식은 csr보다 효율이 떨어집니다.

 

csr은 coo 방식에서 나아가 행을 압축했지만, 열을 압축하는 방식인 csc 방식도 있고 방법은 같습니다. 

 

DOK 방식

마지막으로 dok(Dictionary of Keys)방식을 소개하겠습니다. dok는 좌표가 key이고 원소 값이 value인 딕셔너리 구조입니다. dok 방식은 희소행렬을 점진적으로 구축할 때 사용하기 좋습니다.

 

예를 들어 3 x 4 크기의 비어있는 행렬을 만든 후, 인덱싱을 통해 값을 하나씩 변경해가는 것입니다. 

from scipy.sparse import dok_matrix

m = dok_matrix((3, 4)) # 값이 0으로 채워진 (3, 4) 크기의 행렬을 만듭니다.
m[0, 1] = 4
m[2, 3] = 9
m.toarray()

 

표현 방식 간 간단한 비교

희소행렬을 나타내는 각각의 방식에는 장단점이 있습니다. 어떤 방식은 다른 방식보다 특정 동작을 수행할 때 더 빠릅니다. 

 

우선 coo는 희소행렬을 생성할 때 좀 더 직관적입니다. 그렇기 때문에 우선 coo 행렬을 만들고 나서, tocsr이나 tocsc 메서드를 통해 다른 형식의 희소행렬로 바꾸어서 작업해주면 됩니다. 또는 csr_matrix((data, (row, col))) 라고 입력해서 바로 csr 형식으로 희소행렬을 만들어줄 수도 있습니다.

 

csr 방식과 csc 방식은 산술연산과 행렬·벡터 곱 연산을 빠르게 수행합니다. 그래서 대부분 이 두 방식을 많이 쓰는 것 같습니다. 희소행렬을 이용한 연산에서는 0을 곱하는 연산을 하지 않아도 된다는 (어차피 곱해도 0이기 때문에) 장점도 있습니다.

 

반면 dok 방식은 행렬 연산이 느리다고 합니다. 그러나 특정 좌표에 있는 값에 빠르게 접근할 수 있기 때문에 희소행렬을 점진적으로 구축할 때 이용하기 좋고, coo 방식으로의 변환이 빠릅니다.