<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Sparse Matrices
Step1:  Creating a sparse matrix
There are many applications in which we deal with matrices that are mostly zeros. For example, a matrix representing social networks is very sparse - there are 7 billion people, but most people are only connected to a few hundred or thousand others directly. Storing such a social network as a sparse rather than dense matrix  will offer orders of magnitude reductions in memory requirements and corresponding speed-ups in computation.
Coordinate format
The simplest sparse  matrix format is built from the coordinates and values of the non-zero entries.
From dense matrix
Step2:  From coordinates
Note that the (values, (rows, cols)) argument is a single tuple.
Step3:  Convert back to dense matrix
Step4:  Compressed Sparse Row and Column formats
When we have 2 or more repeated entries in the rows or cols, we can remove the redundancy by indicating the  location of the  first occurrence of a value and its increment instead of the full coordinates. These are known as CSR or CSC formats.
Step5:  Casting from COO format
Because the coordinate format is more intuitive, it is often more convenient to first create a COO matrix then cast to CSR or CSC form.
Step6:  COO summation convention
When entries are repeated in a COO matrix, they are summed. This provides a quick way to construct confusion matrices for evaluation of multi-class  classification algorithms.
Step7:  Application
Step8:  Creating an $n$ by $n$ confusion matrix
For classifications with a large number of classes (e.g. image segmentation),  the savings are even more dramatic.
Step9:  Application
Step10:  Construct the sparse adjacency matrix
Step11:  Construct the transition matrix
Step12:  Modify the transition matrix with a damping factor
The PageRank algorithm assumes that every node can be reached from every other node. To guard against case where a node has out-degree 0, we allow every node a small random chance of transitioning to any other node using a damping factor $d$. Then we solve  the linear system  to find the pagerank score $r$.
$$
r = (I - dM)^{-1}\frac{1-d}{N}\mathbb{1}
$$
or equivalently in the $Ax = b$ format
$$
(I - dM)r = \frac{1-d}{N}\mathbb{1}
$$
Step13:  Visualize the airport connections graph and label the top and bottom 5 airports by pagerank
<ASSISTANT_TASK:>
Python Code:
%matplotlib inline
import numpy as np
import pandas as pd
from scipy import sparse
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_context('notebook', font_scale=1.5)
Explanation: Sparse Matrices
End of explanation
A = np.random.poisson(0.2, (5,15)) * np.random.randint(0, 10, (5, 15))
A
rows, cols = np.nonzero(A)
vals = A[rows, cols]
vals
rows
cols
X1 = sparse.coo_matrix(A)
X1
print(X1)
Explanation: Creating a sparse matrix
There are many applications in which we deal with matrices that are mostly zeros. For example, a matrix representing social networks is very sparse - there are 7 billion people, but most people are only connected to a few hundred or thousand others directly. Storing such a social network as a sparse rather than dense matrix  will offer orders of magnitude reductions in memory requirements and corresponding speed-ups in computation.
Coordinate format
The simplest sparse  matrix format is built from the coordinates and values of the non-zero entries.
From dense matrix
End of explanation
X2 = sparse.coo_matrix((vals, (rows, cols)))
X2
print(X2)
Explanation: From coordinates
Note that the (values, (rows, cols)) argument is a single tuple.
End of explanation
X2.todense()
Explanation: Convert back to dense matrix
End of explanation
np.vstack([rows, cols])
indptr = np.r_[np.searchsorted(rows, np.unique(rows)), len(rows)]
indptr
X3 = sparse.csr_matrix((vals, cols, indptr))
X3
X3.todense()
Explanation: Compressed Sparse Row and Column formats
When we have 2 or more repeated entries in the rows or cols, we can remove the redundancy by indicating the  location of the  first occurrence of a value and its increment instead of the full coordinates. These are known as CSR or CSC formats.
End of explanation
X4 = X2.tocsr()
X4
Explanation: Casting from COO format
Because the coordinate format is more intuitive, it is often more convenient to first create a COO matrix then cast to CSR or CSC form.
End of explanation
rows = np.r_[np.zeros(4), np.ones(4)]
cols = np.repeat([0,1], 4)
vals = np.arange(8)
rows
cols
vals
X5 = sparse.csr_matrix((vals, (rows, cols)))
print(X5)
Explanation: COO summation convention
When entries are repeated in a COO matrix, they are summed. This provides a quick way to construct confusion matrices for evaluation of multi-class  classification algorithms.
End of explanation
obs = np.random.randint(0, 2, 100)
pred = np.random.randint(0, 2, 100)
vals = np.ones(100).astype('int')
pred
vals.shape, obs.shape , pred.shape
X6 = sparse.coo_matrix((vals, (pred, obs)))
X6.todense()
Explanation: Application: Confusion matrix
Creating a 2 by 2 confusion matrix
End of explanation
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
iris = datasets.load_iris()
knn = KNeighborsClassifier()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, 
                                                    test_size=0.5, random_state=42)
pred = knn.fit(X_train, y_train).predict(X_test)
X7 = sparse.coo_matrix((np.ones(len(pred)).astype('int'), (pred, y_test)))
pd.DataFrame(X7.todense(), index=iris.target_names, columns=iris.target_names)
Explanation: Creating an $n$ by $n$ confusion matrix
For classifications with a large number of classes (e.g. image segmentation),  the savings are even more dramatic.
End of explanation
data = pd.read_csv('data/airports.csv', usecols=[0,1])
data.shape
data.head()
lookup = pd.read_csv('data/names.csv', index_col=0)
lookup.shape
lookup.head()
import networkx as nx
Explanation: Application: PageRank
SciPy provides efficient routines for solving large sparse systems as for dense matrices. We will illustrate by calculating the page rank  for airports using data from the Bureau of Transportation Statisitcs.
End of explanation
g = nx.from_pandas_dataframe(data, source='ORIGIN_AIRPORT_ID', target='DEST_AIRPORT_ID')
airports = np.array(g.nodes())
adj_matrix = nx.to_scipy_sparse_matrix(g)
Explanation: Construct the sparse adjacency matrix
End of explanation
out_degrees = np.ravel(adj_matrix.sum(axis=1))
diag_matrix = sparse.diags(1 / out_degrees).tocsr()
M = (diag_matrix @ adj_matrix).T
Explanation: Construct the transition matrix
End of explanation
n = len(airports) 
d = 0.85 
I = sparse.eye(n, format='csc')
A = I - d * M
b = (1-d) / n * np.ones(n) # so the sum of all page ranks is 1
A.todense()
from scipy.sparse.linalg import spsolve
r =  spsolve(A, b)
r.sum()
idx = np.argsort(r)
top10 = idx[-10:][::-1]
bot10 = idx[:10]
df = lookup.loc[airports[top10]]
df['degree'] = out_degrees[top10]
df['pagerank']= r[top10]
df
df = lookup.loc[airports[bot10]]
df['degree'] = out_degrees[bot10]
df['pagerank']= r[bot10]
df
Explanation: Modify the transition matrix with a damping factor
The PageRank algorithm assumes that every node can be reached from every other node. To guard against case where a node has out-degree 0, we allow every node a small random chance of transitioning to any other node using a damping factor $d$. Then we solve  the linear system  to find the pagerank score $r$.
$$
r = (I - dM)^{-1}\frac{1-d}{N}\mathbb{1}
$$
or equivalently in the $Ax = b$ format
$$
(I - dM)r = \frac{1-d}{N}\mathbb{1}
$$
End of explanation
import warnings
labels = {airports[i]: lookup.loc[airports[i]].str.split(':').str[0].values[0] 
          for i in np.r_[top10[:5], bot10[:5]]}
with warnings.catch_warnings():
    warnings.simplefilter('ignore')
    nx.draw(g, pos=nx.spring_layout(g), labels=labels, 
            node_color='blue', font_color='red', alpha=0.5,
            node_size=np.clip(5000*r, 1, 5000*r), width=0.1)
Explanation: Visualize the airport connections graph and label the top and bottom 5 airports by pagerank
End of explanation
<END_TASK>