R, Python 분석과 프로그래밍의 친구 (by R Friend)

행렬의 값이 대부분 '0'인 행렬을 희소행렬(Sparse matrix) 이라고 하며, 반대로 행렬의 값이 대부분 '0이 아닌 값'을 가지는 경우 밀집행렬(Dense matrix) 혹은 조밀행렬이라고 합니다. 

가령, 자연어처리(NLP)에서 텍스트를 파싱해서 TF-IDF 행렬을 만들다보면 대부분의 값은 '0'으로 채워져 있고 '0'이 아닌 값은 듬성듬성 들어있는 희소행렬을 주로 얻게 됩니다. 

희소행렬(Sparse matrix)의 경우 대부분의 값이 '0'이므로 이를 그대로 사용할 경우 메모리 낭비가 심하고 또 연산시간도 오래 걸리는 단점이 있습니다. 이런 단점을 피하기 위해 희소행렬을 다른 형태의 자료구조로 변환해서 저장하고 사용합니다. 

희소행렬을 저장하는 자료구조 4가지에는 

(a) Dictionary of keys(DOK): key (행번호, 열번호) 대 value (데이터) 매핑

(b) List of lists (LIL): 링크드 리스트 알고리즘을 이용한 저장 기법, 내용의 추가와 삭제가 용이하지만 CSR 대비 메모리 낭비가 큼

(c) Coordinate list (COO): (행, 열, 값) 튜플 목록 저장

(d) Compressed sparse row (CSR): 가로의 순서대로 재정렬하는 방법으로 행에 관여하여 정리 압축

가 있습니다. 

* reference: https://en.wikipedia.org/wiki/Sparse_matrix

이중에서 Compressed Sparse Row(CSR) 형태(format) 자료구조의 장점과 단점을 표로 정리해보면 아래와 같습니다. 

이번 포스팅에서는 희소행렬에 대해 이들 중에서도 SciPy 모듈의 csr_matrix() 메소드를 사용하여 

(1) NumPy 희소행렬을 SciPy 압축 희소 행(CSR) 행렬로 변환하기

   (Converting a NumPy sparse matrix to a SciPy compressed sparse row matrix)

(2) SciPy 압축 희소 행(CSR) 행렬을 NumPy 희소행렬로 변환하기 

   (Converting a SciPy compressed sparse row matrix to a NumPy sparse matrix)

하는 각 2가지 방법을 소개하겠습니다. 

NumPy array 데이터형의 희소행렬을 SciPy 압축 희소 행(CSR) 행렬 (compressed sparse row matrix)로 만드는 3가지 방법을 아래의 arr 넘파이 배열을 예로 들어서 설명해보겠습니다. 

class scipy.sparse.csr_matrix(arg1, shape=None, dtype=None, copy=False)

(1-1) arr 넘파이 배열에 대해 => scipy.sparse.csr_matrix(arr)

(1-2) 값 data, '0'이 아닌 원소의 열 위치 indices, 행 위치 시작 indptr 

        => csr_matrix((data, indices, indptr), shape=(5, 4))

(1-3) 값 data, '0'이 아닌 원소의 (행, 열) 위치 => csr_matrix((data, (row, col)), shape=(5, 4))

Compressed Sparse Row matrix로 변환할 대상이 되는 NumPy array 예제 행렬인 'arr' 을 먼저 만들어보겠습니다. 

[Out]

array([[0, 1, 0, 2],
       [0, 3, 4, 5],
       [0, 0, 0, 0],
       [6, 0, 0, 7],
       [0, 8, 0, 0]])

(1-1) arr 넘파이 배열에 대해 => scipy.sparse.csr_matrix(arr)

NumPy 배열 (rank-2 ndarray), 희소행렬, 밀집행렬을 scipy.sparse.csr)matrix() 메소드 안에 넣어주면 되니 제일 쉬운 방법입니다. 

[Out] <5x4 sparse matrix of type '<class 'numpy.longlong'>'
	with 8 stored elements in Compressed Sparse Row format>

위에서 만든 'csr_mat' 이름의 5x4 sparse matrix (CSR format) 에서 특성값(attributes)으로서 

  - (a) csr_mat.indptr : 행렬의 '0'이 아닌 원소의 행의 시작 위치

  - (b) csr_mat.indices : 행렬의 '0'이 아닌 원소의 열의 위치

  - (c) csr_mat.data : 행렬의 '0'이 아닌 원소 값

-- Compressed Sparse Row matrix --
indptr: [0 2 5 5 7 8]
indices: [1 3 1 2 3 0 3 1]
data: [1 2 3 4 5 6 7 8]

이를 그림으로 좀더 알기 쉽게 표현을 해보면 아래와 같습니다. 헷갈리지 않고 좀더 알아보기에 편리하도록 NumPy array 행렬의 값(data)을 숫자가 아니라 영어 알파벳으로 바꾸어서 표시하였습니다. 

SciPy Compressed Sparse Row matrix 에서 

  - data 는 행렬의 '0'이 아닌 원소 값이므로 이해하기 어려운게 없습니다. 

  - indices 도 행렬의 '0'이 아닌 원소의 위치 (row, column) 에서 열(column) 위치(index) 배열 [1, 3, 1, 2, 3, 0, 3, 1 ] 이므로 어려울게 없습니다. 

  - indptr 은 저는 처음에 봤을 때는 이게 뭔가하고 유심히 보면서 좀 고민을 했습니다. ^^;  indptr은 행을 기준으로 했을 때 행별로 '0'이 아닌 원소가 처음 시작하는 위치의 배열입니다. 말로 설명하기 좀 어려운데요, 가령 위의 NumPy 배열 'arr'의 '0'이 아닌 원소의 위치 (행 row, 열 col) 배열(위 그림의 중간에 표시되어 있음)을 보면, 

'arr' 배열의 첫번째 행 [0, a, 0, b] 는 '0'이 아닌 원소의 (row, col) 배열의 0 위치에서 시작, 

               두번째 행 [0, c, d, e] 는 '0'이 아닌 원소의 (row, col) 배열의 2 위치에서 시작, 

               세번째 행 [0, 0, 0, 0] 는 '0'이 아닌 원소의 (row, col) 배열의 5 위치에서 시작, (비어있음) 

               네번째 행 [f, 0, 0, g] 는 '0'이 아닌 원소의 (row, col) 배열의 5 위치에서 시작, 

                        (--> 왜냐하면, 세번째 행의 모든 값이 '0' 이므로 같은 위치인 5에서 시작함)

               다섯번째 행 [0, h, 0, 0] 는 '0'이 아닌 원소의 (row, col) 배열의 7 위치에서 시작, 

               마지막으로, 'arr' 의 원소의 개수 8 에서 끝남.  

이렇게 indptr을 이용하는 이유는 행 기준의 '0'이 아닌 원소의 (row, col) 을 사용하는 것보다 데이터를 좀더 압축할 수 (즉, 줄일 수) 있기 때문입니다. 위의 예의 경우 row 기준으로 '0'이 아닌 원소의 (row, col)에서 row만 보면 [0, 0, 1, 1, 1, 3, 3, 4] 로서 [0, 0], [1, 1, 1], [3, 3] 처럼 같은 행에 두 개 이상의 '0'이 아닌 원소가 있으면 같은 행 숫자가 반복됩니다. 이럴 때 indptr 을 사용하면 [0, 2, 5, 5, 7, 8] 처럼 행 기준으로 '0'이 아닌 원소가 시작되는 row 위치만 가져오면 되므로 저장해야하는 정보량을 줄일 수 (압축) 있게 됩니다.   

(1-2) 값 data, '0'이 아닌 원소의 열 위치 indices, 행 위치 시작 indptr 

        => csr_matrix((data, indices, indptr), shape=(5, 4))

NumPy array 행렬이 없더라도, data, indices, indptr 입력값과 output 행렬의 형상(shape) 을 알고 있다면 SciPy Compressed Sparse Row matrix를 아래처럼 만들 수 있습니다.

(다만, indptr, indices 를 사람이 직접 입력하기에는 좀 어려운 면이 있어서 위의 (1-1) 방법보다는 좀 어려워보이네요.)

[Out] <5x4 sparse matrix of type '<class 'numpy.int64'>'

	with 8 stored elements in Compressed Sparse Row format>

-- Compressed Sparse Row matrix 2 --
indptr: [0 2 5 5 7 8]
indices: [1 3 1 2 3 0 3 1]
data: [1 2 3 4 5 6 7 8]

(1-3) 값 data, '0'이 아닌 원소의 (행, 열) => csr_matrix((data, (row, col)), shape=(5, 4))

세번째는 행렬에서 '0' 이 아닌 원소의 값(data)과 (행, 열) 위치 (row_ind, col_ind), 그리고 행렬의 형상(shape) 을 입력해주는 방식입니다. (사람 입장에서는 이 (1-3) 방식이 위의 (1-2) 방식보다는 직관적으로 이해하기가 더 쉽기는 합니다.)

[Out] <5x4 sparse matrix of type '<class 'numpy.longlong'>'

	with 8 stored elements in Compressed Sparse Row format>

-- Compressed Sparse Row matrix 2 --
indptr: [0 2 4 4 6 7]
indices: [1 3 1 2 0 3 1]
data: [1 2 3 4 5 6 7]

-- Compressed Sparse Row matrix 3 --
indptr: [0 2 5 5 7 8]
indices: [1 3 1 2 3 0 3 1]
data: [1 2 3 4 5 6 7 8]

SciPy 압축 희소 행 행렬을 NumPy 행렬로 변환하기는 아래 2가지 메소드를 이용하면 매우 쉽습니다. 

(2-1) scipy.sparse.csr_matrix.toarray() 메소드

(2-2) scipy.sparse.csr_matrix.todense() 메소드

위에서 만든 'csr_mat', 'csr_mat2', 'csr_mat3' 세 개의 압축 희소 행(CSR) 행렬을 아래에서 원래의 NumPy array 배열로 변환해보니 모두 동일하게 제대로 변환이 되었네요. 

(2-1) scipy.sparse.csr_matrix.toarray() 메소드

[Out]

array([[0, 1, 0, 2],
       [0, 3, 4, 5],
       [0, 0, 0, 0],
       [6, 0, 0, 7],
       [0, 8, 0, 0]], dtype=int64)

[Out]

array([[0, 1, 0, 2],
       [0, 3, 4, 5],
       [0, 0, 0, 0],
       [6, 0, 0, 7],
       [0, 8, 0, 0]], dtype=int64)

[Out]

array([[0, 1, 0, 2],
       [0, 3, 4, 5],
       [0, 0, 0, 0],
       [6, 0, 0, 7],
       [0, 8, 0, 0]], dtype=int64)

(2-2) scipy.sparse.csr_matrix.todense() 메소드

SciPy Compressed Sparse Row matrix를 원래의 행렬로 변환할 때 그게 희소행렬(Sparse matrix) 일 수도 있고 아니면 밀집행렬(Dense matrix) 일 수도 있기 때문에 메소드 이름을 csr_matrix.todense() 라고 하면 좀 오해의 소지도 있어서 썩 잘 지은 메소드 이름은 아니라고 생각하는데요, 어쨌든 반환된 후의 결과는 위의 csr_matrix.toarray() 와 동일합니다. 

[Out]

array([[0, 1, 0, 2],
       [0, 3, 4, 5],
       [0, 0, 0, 0],
       [6, 0, 0, 7],
       [0, 8, 0, 0]], dtype=int64)

아래의 행렬처럼 (row, column) 이 (0, 0)인 위치에 5, 3 의 값이 중복되어 있고, (1, 1)인 위치에 2, 4 의 값이 중복되어 있는 Compressed Sparse Row matrix 데이터는 중복된 위치의 값을 더해주게 됩니다. 

[Out]

array([[8, 0, 0],
       [0, 6, 0],
       [0, 0, 0]], dtype=int64)

[ Reference ]

* SciPy 모듈 sparse.csr_matrix() 메소드

  : https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html

* Sparse matrix: https://en.wikipedia.org/wiki/Sparse_matrix

많은 도움이 되었기를 바랍니다. 

이번 포스팅이 도움이 되었다면 아래의 '공감~'를 꾹 눌러주세요.