Coming from a Matlab background, I found sparse matrices to be easy to use and well integrated into the language. However, when transitioning to python’s scientific computing ecosystem, I had a harder time using sparse matrices. This post is intended to help Matlab refugees and those interested in using sparse matricies in python (in particular, for clustering)

Requirements:

Requirements:

scikit-learn (2.10+)

**numpy (refer to scikit-learn version requirements)**

scipy (refer to scikit-learn version requirements)

scipy (refer to scikit-learn version requirements)

**Sparse Matrix Types:**

There are six types of sparse matrices implemented under scipy:

There are six types of sparse matrices implemented under scipy:

- bsr_matrix -- block sparse row matrix
- coo_matrix -- sparse matrix in coordinate format
- csc_matrix -- compressed sparse column matrix
- csr_matrix -- compressed sparse row matrix
- dia_matrix -- sparse matrix with diagonal storage
- dok_matrix -- dictionary of keys based sparse matrix
- lil_matrix -- row-based linked list sparse matrix

**(http://docs.scipy.org/doc/scipy/reference/sparse.html):**

**When to use which matrix:**

The following are scenarios when you would want to choose one sparse matrix type over the another:

csc_matrix, csr_matrix*Fast Arithmetic Operation*:csc_matrix*Fast Column Slicing (e.g., A[:, 1:2]):*csr_matrix*Fast Row Slicing (e.g., A[1:2, :])*csr_matrix, bsr_matrix, csc_matrix*Fast Matrix vector products:*lil_matrix, dok_matrix*Fast Changing of sparsity (e.g., adding entries to matrix):*coo_matrix*Fast conversion to other sparse formats:*coo_matrix*Constructing Large Sparse Matrices:*

**Clustering with scikit-learn:**

**With the release of scikit-learn 2.10, one of the useful new features is the support for sparse matrices with the k-means algorithm. The following is how you would use sparse matrices with k-means:**

**Full Matrix to Sparse Matrix**

**Example-1**

-----------------------------------------------------------------------------------------------

from numpy.random import random

from scipy.sparse import *

from sklearn.cluster import KMeans

**# create a 30x1000 dense matrix random matrix.**

D = random((30,1000))

**# keep entries with value < 0.10 (10% of entries in matrix will be non-zero)**

**# X is a "full" matrix that is intrinsically sparse.**

X = D*(D<0.10)

**# note: element wise mult**

**# convert D into a sparse matrix (type coo_matrix)**

**# note: we can initialize any type of sparse matrix.**

**# There is no particular motivation behind using**

**# coo_matrix for this example.**

S = coo_matrix(X)

labeler = KMeans(k=3)

**# convert coo to csr format**

**# note: Kmeans currently only works with CSR type sparse matrix**

labeler.fit(S.tocsr())

**# print cluster assignments for each row**

for (row, label) in enumerate(labeler.labels_):

print "row %d has label %d"%(row, label)

-----------------------------------------------------------------------------------------------

One of the issues with Example-1 is that we are constructing a sparse matrix from a full matrix. It will often be the case that we will not be able to fit a full (although intrinsically sparse) matrix in memory. For example, if the matrix X was a 100000x1000000000 full matrix, there could be some issues. One solution to this is to somehow extract out the non-zero entries of X and to use a smarter constructor for the sparse matrix.

**Sparse Matrix Construction**

In Example-2, we will assume that we have X's data stored on some file on disk. In particular, we will assume that X is stored in a csv file and that we are able to extract out the non-zero data efficiently.

**Example-2**

-------------------------------------------------

**import csv**

from scipy.sparse import *

from sklearn.cluster import KMeans

def extract_nonzero(fname):

"""

extracts nonzero entries from a csv file

input: fname (str) -- path to csv file

output: generator<(int, int, float)> -- generator

producing 3-tuple containing (row-index, column-index, data)

"""

for (rindex,row) in enumerate(csv.reader(open(fname))):

for (cindex, data) in enumerate(row):

if data!="0":

yield (rindex, cindex, float(data))

def get_dimensions(fname):

"""

determines the dimension of a csv file

input: fname (str) -- path to csv file

output: (nrows, ncols) -- tuple containing row x col data

"""

rowgen = (row for row in csv.reader(open(fname)))

# compute col size

colsize = len(rowgen.next())

# compute row size

rowsize = 1 + sum(1 for row in rowgen)

return (rowsize, colsize)

(rdim, cdim) = get_dimensions("X.csv")

# allocate a lil_matrix of size (rdim by cdim)

# note: lil_matrix is used since we be modifying

# the matrix a lot.

S = lil_matrix((rdim, cdim))

# add data to S

for (i,j,d) in extract_nonzero("X.csv"):

S[i,j] = d

# perform clustering

labeler = KMeans(k=3)

# convert lil to csr format

# note: Kmeans currently only works with CSR type sparse matrix

labeler.fit(S.tocsr())

# print cluster assignments for each row

for (row, label) in enumerate(labeler.labels_):

print "row %d has label %d"%(row, label)

from scipy.sparse import *

from sklearn.cluster import KMeans

def extract_nonzero(fname):

"""

extracts nonzero entries from a csv file

input: fname (str) -- path to csv file

output: generator<(int, int, float)> -- generator

producing 3-tuple containing (row-index, column-index, data)

"""

for (rindex,row) in enumerate(csv.reader(open(fname))):

for (cindex, data) in enumerate(row):

if data!="0":

yield (rindex, cindex, float(data))

def get_dimensions(fname):

"""

determines the dimension of a csv file

input: fname (str) -- path to csv file

output: (nrows, ncols) -- tuple containing row x col data

"""

rowgen = (row for row in csv.reader(open(fname)))

# compute col size

colsize = len(rowgen.next())

# compute row size

rowsize = 1 + sum(1 for row in rowgen)

return (rowsize, colsize)

**# obtain dimensions of data**(rdim, cdim) = get_dimensions("X.csv")

# allocate a lil_matrix of size (rdim by cdim)

# note: lil_matrix is used since we be modifying

# the matrix a lot.

S = lil_matrix((rdim, cdim))

# add data to S

for (i,j,d) in extract_nonzero("X.csv"):

S[i,j] = d

# perform clustering

labeler = KMeans(k=3)

# convert lil to csr format

# note: Kmeans currently only works with CSR type sparse matrix

labeler.fit(S.tocsr())

# print cluster assignments for each row

for (row, label) in enumerate(labeler.labels_):

print "row %d has label %d"%(row, label)

--------------------------------------------------

**What to do when Sparse Matrices aren't supported:**

When sparse matrices aren't supported, one solution is to convert the matrix to a full matrix. To do this, simply invoke the todense() method.

## No comments:

Post a Comment