<jupyter_start><jupyter_text>Data loading and Conversion to Utility MatrixThe data is loaded into pandas dataframe and the relevant information is extracted to construct an MxN utility matrix in the form of a numpy matrix were M= No. of Users and N= No of movies.<jupyter_code>#reading the data into a pandas dataframe
links=pd.read_csv('links.csv')
ratings=pd.read_csv('ratings.csv')
movies=pd.read_csv('movies.csv')
tags=pd.read_csv('tags.csv')
links.head() 
links.shape # implies 9125 is the number of movies
ratings.head() # implies 100004 non zero values will be present in the matrix
ratings.shape
movies.head()
mov=movies['movieId'].tolist()
# dictionary idToIndex hashes movie id to a continuous index from 1 to 9125
idToIndex={}             
for i in xrange(len(mov)):
    idToIndex[mov[i]]=i           
len(idToIndex.keys())
N=movies.shape[0] #N=number of columns in MxN utility matrix
tags.head()
M=671
#Finally constructing the matrix iterating over rows of ratings data frame
A=np.zeros((M,N))
for index, row in ratings.iterrows():
    userid= int(row['userId'])
    movieid=int(row['movieId'])
    if idToIndex[movieid]<=9125:
        A[userid-1,idToIndex[movieid]]=row['rating']
    
np.count_nonzero(A)  #sanity check<jupyter_output><empty_output><jupyter_text>Function to compute eigen values and eigen vectorsFor calculating SVD, we need the eigenpairs of AAT and ATA. A generalised power iteration function is used here to do that. Power iteration actually just calulates the principal eigenvector, but we iteratively keep on reducting the matrix to find eigenvectors corresponding to largest k eigenvalues.<jupyter_code>A=np.matrix(A)
AAT=A*A.T
ATA=A.T*A
# This function computes the eigenvalues and eigenvectors using power iteration method
# Arguments:
#     M: Square Matrix
#     k: Number of eigenpairs we want to calculate
# Returns:
#     Val: list of k eigenvalues we want to calculate
#     Vec: list of corresponding eigenvectors as numpy column arrays
def getEigenPairs(M,k):
    x=np.random.randn((M.shape[0]))
    Val=[]
    Vec=[]
    x=x.reshape((M.shape[0],1)) 
    for i in xrange(k):
        #M=np.matrix(M)
        for run in xrange(1000):
            V=M*x                
            nor=norm(V)
            if nor!=0:
                
                x_new=V/nor
                x=x_new

        eVec=x
        y=x.reshape((1,M.shape[0]))
        y=np.matrix(y)
        x=x.reshape((M.shape[0],1))
        x=np.matrix(x)

        eVal=y*M*x
        
        eVal=np.asscalar(eVal)
        if eVal>0.1:
            
            Val.append(eVal)
            Vec.append(eVec)
        else:
            Val.append(0)
            Vec.append(eVec)
    
        M=M-eVal*x*y   
    return Val,Vec
def signU(A,u,v):
    x=A*v
    if x[0]/u[0]>0:
        return 1
    else:
        return -1
# Calculates Singular Value Decomposition of the matrix.
# Arguments:
#     AAT,ATA:
#         A*A(Transpose) and A(transpose)*A
#     k: Rank of SVD we want to compute/ no of singular values we want to consider
#         /No of latent dimensions we want to break our space into
def SVD(A,AAT,ATA,k):  
    
    #Fetch eigenvalues and eigenvectors for AAT and ATA
   
    L1,V1=getEigenPairs(AAT,k)
    L2,V2=getEigenPairs(ATA,k)
    
    print 'Eigenvectors and EigenValues calculated'
    
    print'proceeding...'
    
    
    for i in xrange(k):
            sgn=signU(A,V1[i],V2[i])
            V1[i]=sgn*V1[i]
        
    
    print 'stacking U and V matrices'
    #Create U Matrix:
    U=V1[0]
    for i in xrange(1,len(V1)):
        U=np.column_stack((U,V1[i]))
        
    
    
    #Create V matrix:
    V=V2[0]
    for i in xrange(1,len(V2)):
        V=np.column_stack((V,V2[i]))
        
        
        
        
    V=np.matrix(V)
    U=np.matrix(U)
    
    
    
    
    
    
    print 'constructing sigma matrix'    
    #construct the sigma matrix:

    sigma=np.zeros((k,k))
    sigma=np.matrix(sigma)
    for i in xrange(k):
        if L1[i]>0:
            sigma[i,i]=pow(L1[i],0.5)
        else:
            sigma[i,i]=0
            
        
    sigma=np.matrix(sigma)
    print 'done'
    return U, sigma, V
#Sparse converting A, AAT and ATA into sparse csr matrices
sA=sparse.csr_matrix(A)
sAAT=sparse.csr_matrix(AAT)
sATA=sparse.csr_matrix(ATA)
#Tracking how the computation time increases with increase in k

timeTrajectory=[]
for i in xrange(10,40,5):
    start = time.time()

    u,s,v=SVD(AAT,ATA,i)


    end = time.time()
    print 'time required to compute SVD for with rank ' +str(i)+':'
    deltaT=(end - start)
    timeTrajectory.append(deltaT)
    print deltaT
    
    
for i in xrange(40,80,5):
    start = time.time()

    u,s,v=SVD(AAT,ATA,i)


    end = time.time()
    print 'time required to compute SVD for with rank ' +str(i)+':'
    deltaT=(end - start)
    timeTrajectory.append(deltaT)
    print deltaT
#plot of computation time in seconds versus the value of k. Clearly more time will be required for
#large k values
plt.plot([10,15,20,25,30,35,40,45,50], timeTrajectory, 'ro')
plt.axis([0, 100, 400, 2000])
plt.xlabel('rank')
plt.ylabel('time required in seconds for computation (secs)')
plt.show()<jupyter_output><empty_output><jupyter_text>CUR Decomposition<jupyter_code>#for C and R matrices of o


#pf for rows:
pfr=[]
for i in xrange(A.shape[0]):
    arr=A[i,:]
    p=np.linalg.norm(arr)
    pfr.append(p)
total=sum(pfr)
for i in xrange(len(pfr)):
    pfr[i]=pfr[i]/total
    
    
   
pfc=[]
for i in xrange(A.shape[1]):
    arr=A[:,i]
    p=np.linalg.norm(arr)
    pfc.append(p)  
total=sum(pfc)
for i in xrange(len(pfc)):
    pfc[i]=pfc[i]/total
sum(pfr)  #sanity check
sum(pfc)   #sanity check
def getU(W):
    WWT=W*W.T
    WTW=W.T*W
    u,s,v=SVD(W,WWT,WTW,W.shape[0])
    for i in xrange(s.shape[0]):
        if s[i,i]!=0:
            s[i,i]=1.0/s[i,i]
    s=np.power(s,2)
    return v*s*u.T
def getCUR(A,r):
    rowIndex=np.random.choice(A.shape[0],r,pfr)
    columnIndex=np.random.choice(A.shape[1],r,pfc)
    
    C=A[:,columnIndex[0]]
    columnIndex2=columnIndex[1:]
    for index in columnIndex2:
        C=np.column_stack((C,A[:,index]))
    
    R=A[rowIndex[0],:]
    rowIndex2=rowIndex[1:]
    for index in rowIndex2:
        R=np.vstack((R,A[index,:]))
        
    W=np.zeros((r,r))
    W=np.matrix(W)
    for i in xrange(W.shape[0]):
        for j in xrange(W.shape[1]):
            row=rowIndex[i]
            column=columnIndex[j]
            W[i,j]=A[row,column]
    W2=getU(W)        
    return C, W2, R
    

 
C,W,R=getCUR(A,100)
C.shape
R.shape
W.shape
norm(A-C*W*R)
timeTrajectoryCUR=[]
for i in xrange(20,200,20):
    start = time.time()

    c,u,r=getCUR(A,i)


    end = time.time()
    print 'time required to compute CUR for with rank ' +str(i)+':'
    deltaT=(end - start)
    timeTrajectoryCUR.append(deltaT)
    print deltaT
    
plt.plot([20,40,60,80,100,120,140,160,180], timeTrajectoryCUR, 'ro')
plt.axis([0,200 , 0, 0.5])
plt.xlabel('rank')
plt.ylabel('time required in seconds for computation (secs)')
plt.show()
memoryTrajectory=[]
memoryTrajectoryCUR=[]
reconsError=[]
reconsErrorCUR=[]

for i in xrange(10,50,10):
    
    c,u,r=getCUR(A,i)
    U,S,V=SVD(A,AAT,ATA,i)
    A_rec_svd=U*S*V.T
    A_rec_cur=c*u*r

    errSVD=norm(A-A_rec_svd)
    errCUR=norm(A-A_rec_cur)
    
    c=sparse.csr_matrix(c)
    u=sparse.csr_matrix(u)
    r=sparse.csr_matrix(r)
    
    memCUR=getsizeof(c)+getsizeof(u)+getsizeof(r)
    memSVD=getsizeof(U)+getsizeof(S)+getsizeof(V)
    
    memoryTrajectory.append(memSVD)
    memoryTrajectoryCUR.append(memCUR)
    
    reconsError.append(errSVD)
    reconsErrorCUR.append(errCUR)<jupyter_output>Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done
Eigenvectors and EigenValues calculated
proceeding...
stacking U and V matrices
constructing sigma matrix
done<jupyter_text>Comparison of SVD and CUR Memory:Since CUR can be represented by sparse matrices, it requires much less memory and remains almost constant with increase in rank. In SVD however, memory requirement explodes with increase in the value of k and is very large even at small values of k as U and V are dense matrices. Reconstruction error:Reconstruction error of SVD is less than that of CUR, but CUR performs reasonably well. Time Complexity:Time complexity of both CUR and SVD increases with increase in the value of k, however, the order of complexity of CUR is much less than that of SVD. For example, while SVD takes about 10 minutes to calculate a SVD with rank 10, CUR does it in fraction of second.<jupyter_code>memoryTrajectory  #memory trajectory of SVD
memoryTrajectoryCUR  #memory trajectory of CUR (Note the vast difference)
reconsError
reconsErrorCUR
plt.plot([10,20,30,40], reconsError, 'ro') #Red circles represent SVD
plt.plot([10,20,30,40], reconsErrorCUR, 'bs') #Blue squares represent CUR
plt.axis([0,50,500,2000])
plt.xlabel('rank')
plt.ylabel('reconstruction error')
plt.show()

plt.plot([10,20,30,40], memoryTrajectory, 'ro') 
plt.axis([5,50,200000,5000000])
plt.xlabel('rank')
plt.ylabel('space requirement of SVD')
plt.show()
plt.plot([10,20,30,40], memoryTrajectoryCUR, 'bs') 
plt.axis([5,50,50,300])
plt.xlabel('rank')
plt.ylabel('space requirement of CUR')
plt.show()<jupyter_output><empty_output><jupyter_text>Visualizing SVD for a small test matrix<jupyter_code>t=[[2,3,4,56],[2,3,7,6],[1,2,4,5],[1,2,4,5],[2,7,0,56],[55,45,66,9],[3,4,5,1]]
t=np.matrix(t)
x,y,z=SVD(t,t*t.T,t.T*t,4)
t_r=x*y*z.T
norm(t-t_r)
t_r<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12298209568535369, 'fraction_numerical': 0.02729674200176108, 'mean_word_length': 3.3021885521885523, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '208631', 'license': 'MIT', 'n_tokens_mistral': 3974, 'n_tokens_neox': 3707, 'n_words': 962, 'path': 'IRassignment2.ipynb', 'repo_name': 'prvjain007/Dimensionality-reduction-for-recommender-systems.', 'size': '10221'}