Scipy Sparse Matrix

Scipy Sparse Matrix, Dense Matrix

Sparse Matrix 의 경우 메모리를 적게 소비하기 위하여 생략하여 표기를 하는 경우가 많다. 

 

여러 기법이 있지만, 

 

그 중 3가지를 정리해본다. 

 

---

참고글

 

https://stackoverflow.com/questions/32743584/python-lil-matrix-vs-csr-matrix-in-extremely-large-sparse-matrices

Python: lil_matrix vs csr_matrix in extremely large sparse matrices

---

CSR (Compresses Sparse Row) : 

https://stackoverflow.com/questions/52299420/scipy-csr-matrix-understand-indptr

https://medium.com/@rlaskarb09/csr-matrix%EC%97%90%EC%84%9C-%ED%8A%B9%EC%A0%95-index%EC%9D%98-data-%EC%A0%91%EA%B7%BC-101ad6dc68f7

csr_matrix에서 특정 index의 data 접근

csr_matrix는 Scipy Library에서 제공하는 class로 sparse matrix를 저장하며 효율적인 연산을 지원한다.

csr_matrix의 경우 데이터를 data, indptr, indices로 관리한다.

위 이미지를 참고하여 아래 코드를 확인해보자. 

array([[1, 0, 2],
       [0, 0, 3],
       [4, 5, 6]])
       
indptr = np.array([0, 2, 3, 6])
indices = np.array([0, 2, 2, 0, 1, 2])
data = np.array([1, 2, 3, 4, 5, 6])
P = csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()


P.__dict__
{'_shape': (3, 3),
 'data': array([1, 2, 3, 4, 5, 6]),
 'indices': array([0, 2, 2, 0, 1, 2], dtype=int32),
 'indptr': array([0, 2, 3, 6], dtype=int32),
 'maxprint': 50}

data 에는 0 을 제외한 원소들을 작성한다. 

data 의 index 를 알 수 없으므로 indptr, indices 를 통해 위치를 표기한다. 

 

indicies 는 단순히 data의 원소를 row 기준으로 index 를 표기한 것이다. 

1 - 0, 2 - 2, 3 - 2, 4 - 0, 5 - 1, 6 - 2 가 그 예시이다. 

indptr 은 각 row 의 0이 아닌 원소의 시작 지점을 data 의 index 로 표기한 것이다. 

1 - 0(첫번째 줄 data의 0번째 원소), 3 - 2 (두번째 줄 data의 2번째 원소), 4 - 3 (세번째 줄 data의 3번째 원소),

6 - (4번째 줄 첫 index) 이건 마지막 row의 index 끝 지점을 어떠한 이유에서 알 필요가 있어서 표기하는 듯 하다. 정확한 이유는 아직 모르곘다. 

 

CSR Foramt의 장단점

 

CSR sparse matrices 는 산술 연산이 가능하다. (addition, subtraction, multiplication, division, matrix power)

장점

• 산술 연산이 효율적이다.  CSR + CSR, CSR * CSR, etc.
• row slicing이 효율적이다. 
• matrix vector products가 빠르다. (Ax=b)

단점

• CSC에 비하여 column slicing 이 느리다. 
• Sparsity Structure 로 바꾸는데 시간이 비교적 오래걸린다. (LIL or DOK 와 비교하여)

 

LIL (list of lists) :

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

scipy.sparse.lil_matrix — SciPy v1.9.0 Manual

희소 행렬을 점진적으로 구성하기 위한 구조, 최악의 경우 아이템 한개를 삽입하는 데 linear time이 걸릴 수 있다. 행렬을 효율적으로 구성하려면 아이템이 각 행(column)마다 인덱스별로 미리 정렬되어 있어야한다.

 

array([[1, 0, 2],
       [0, 0, 3],
       [4, 5, 6]])
       
K = P.tolil()

K.__dict__
{'_shape': (3, 3),
 'data': array([list([1, 2]), list([3]), list([4, 5, 6])], dtype=object),
 'dtype': dtype('int64'),
 'maxprint': 50,
 'rows': array([list([0, 2]), list([2]), list([0, 1, 2])], dtype=object)}

 

data 는 csr_matrix 와 다르게 각 row 별로 나눠서 표기한다.  [1,2], [3], [4,5,6]

rows 는 [0,2], [2], [0,1,2] 로 각 row 별 item의 index 를 표기한다. 

CSR 과는 달리 각 row 별로 나뉘다 보니 유연한 slicing 이 가능하다. 

 

 

LIL Foramt의 장단점

장점

• 유연한 slicing 지원 
• matrix sparse structure로 바꿀 때 효율적이다. 

단점

• CSR과 동일하게 산술 연산을 지원하나, CSR보다 속도가 느리다. 
• CSC 와 비교하여 column slicing이 느리다. 
• 비교적으로 CSR, CSC보다 matrix vector products 이 느리다. 

 

정리하자면, item을 추가할 때 LIL format 으로 바꾸는 듯 하다.  

 

 

DOK (Dictionary of Keys) :

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

scipy.sparse.dok_matrix — SciPy v1.9.0 Manual

희소 행렬을 점진적으로 구성하기 위한 구조

산술 연산인 덧셈, 뺄셈, 곱셈, 나눗셈 및 행렬 거듭제곱이 가능하다.

개별 아이템은 효율적인 액세스 O(1)가 가능하다. 복제는 허용되지 않는다. 생성 된 후 효율적인 coo_matrix로 변환될 수 있다.

 

C = K.todok()
C.__dict__

ans = []
for i in range(3):
  for j in range(3):
    ans.append(C[i,j])
print(ans)

[1, 0, 2, 0, 0, 3, 4, 5, 6]

 

sparse matrix의 DOK은 단순하게 dictionary 접근이다. 

 

이 외에도 여러 표기방법이 있다. 아래 공식 문서 참고 

 

https://rfriend.tistory.com/551

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

https://medium.com/@rlaskarb09/csr-matrix%EC%97%90%EC%84%9C-%ED%8A%B9%EC%A0%95-index%EC%9D%98-data-%EC%A0%91%EA%B7%BC-101ad6dc68f7

csr_matrix에서 특정 index의 data 접근