'압축 희소 행 행렬을 희소행렬로 변환하기'에 해당되는 글 1건

  1. 2020.08.09 [Python] Numpy 희소행렬을 SciPy 압축 희소 열 행렬 (Compressed sparse row matrix)로 변환하기

행렬의 값이 대부분 '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) 자료구조의 장점과 단점을 표로 정리해보면 아래와 같습니다. 


 CSR 자료구조의 장점

(Advantages of the CSR format)

CSR 자료구조의 단점

(Disadvantages of the CSR format)

  •  효율적인 산술 연산
     (예: CSR + CSR, CSR * CSR 등)
  • 효율적인 행 슬라이싱
    (efficient row slicing)
  • 빠른 행렬 벡터 곱
    (fast matrix vector products)
  • 느린 열 슬라이싱
    (slow column slicing) 
    --> Compressed Sparse Column format 고려
  • 희소성 구조의 변화 시 연산비용 큼
    --> LIL, DOK 고려



이번 포스팅에서는 희소행렬에 대해 이들 중에서도 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가지 방법을 소개하겠습니다. 






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

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


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' 을 먼저 만들어보겠습니다. 



import numpy as np

from scipy.sparse import csr_matrix


arr = np.array([[0, 1, 0, 2], 

                [0, 3, 4, 5], 

                [0, 0, 0, 0], 

                [6, 0, 0, 7], 

                [0, 8, 0, 0]])


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() 메소드 안에 넣어주면 되니 제일 쉬운 방법입니다. 



# converting NumPy array into SciPy Compressed Sparse Row matrix

csr_mat = csr_matrix(arr)


csr_mat

[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'이 아닌 원소 값



print('-- Compressed Sparse Row matrix --')

print('indptr:', csr_mat.indptr)

print('indices:', csr_mat.indices)

print('data:', csr_mat.data)


-- 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) 방법보다는 좀 어려워보이네요.)



# converting NumPy array into SciPy Compressed Sparse Row matrix

indptr = np.array([0, 2, 5, 5, 7, 8]) # the location of the first element of the row.

indices = np.array([1, 3, 1, 2, 3, 0, 3, 1]) # column indices

data = np.array([1, 2, 3, 4, 5, 6, 7, 8])    # corresponding value


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

csr_mat2

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



print('-- Compressed Sparse Row matrix 2 --')

print('indptr:', csr_mat2.indptr)

print('indices:', csr_mat2.indices)

print('data:', csr_mat2.data)


-- 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) 방식보다는 직관적으로 이해하기가 더 쉽기는 합니다.)



# converting NumPy array into SciPy Compressed Sparse Row matrix

row = np.array([0, 0, 1, 1, 1, 3, 3, 4])

col = np.array([1, 3, 1, 2, 3, 0, 3, 1])

data = np.array([1, 2, 3, 4, 5, 6, 7, 8])


csr_mat3 = csr_matrix((data, (row, col)), shape=(5, 4))

csr_mat3

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

 

print('-- Compressed Sparse Row matrix 3 --')

print('indptr:', csr_mat3.indptr)

print('indices:', csr_mat3.indices)

print('data:', csr_mat3.data)


-- 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]





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

     (Transforming a SciPy compressed sparse row matrix into a NumPy matrix) 


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() 메소드



# converting sparse matrix to NumPy array

csr_mat.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)


csr_mat2.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)


csr_mat3.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)





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


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



csr_mat.todense()

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

 




  (3) 동일 위치에 중복된 원소값은 합산 (Duplicate entries are summed together.)


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


  5 + 3

 0

 0

 0

 2 + 4

 0

 0

 0

 0



# Duplicate entries are summed together. 

row = np.array([0, 1, 1, 0])

col = np.array([0, 1, 1, 0])

data = np.array([5, 2, 4, 3])

csr_matrix((data, (row, col)), shape=(3, 3)).toarray()


[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



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

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



Posted by R Friend Rfriend

댓글을 달아 주세요