'Compressed Sparse Row(CSR) 형태(format) 자료구조의 장점과 단점'에 해당되는 글 1건

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

행렬의 값이 대부분 '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



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

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



728x90
반응형
Posted by Rfriend
,