In this example, we illustrate various unsupervised learning techniques (Clustering, PCA, SVD) using an example term-document matrix as the data.¶
In [1]:
import numpy as np
import pylab as pl
import pandas as pd
from sklearn.cluster import KMeans
In [2]:
Data = pd.read_csv("http://facweb.cs.depaul.edu/mobasher/classes/csc478/data/term-doc-mat.csv", header=None)
In [3]:
Data
Out[3]:
In [5]:
# Let's remove the column containing the terms
# TD will be out term x document matrix
TD = Data.iloc[:,1:]
TD
Out[5]:
In [6]:
# Reindex the columns to start from 0
TD.columns= range(15)
TD
Out[6]:
In [7]:
# The list of our index terms
terms = Data.iloc[:,0]
terms
Out[7]:
First, we want to do some document clustering. Since the data is in term-document format, we need to obtain the transpose of the TD matrix.¶
In [8]:
DT = TD.T
Now we have a document-term matrix:¶
In [9]:
DT
Out[9]:
In [12]:
numTerms=TD.shape[0]
NDocs = TD.shape[1]
Next, we will transform the data to TFxIDF weights (this is not necessary for clustering, but we will do it here for illustration purposes):¶
In [15]:
# Note: doc frequency (df) for a term t is the number of docs in which t appears divided by total number of docs
# first let's find the doc counts for each term
DF = pd.DataFrame([(TD!=0).sum(1)]).T
DF
Out[15]:
In [16]:
# Create a matrix with all entries = NDocs
NMatrix=np.ones(np.shape(TD), dtype=float)*NDocs
np.set_printoptions(precision=2,suppress=True,linewidth=120)
print(NMatrix)
In [17]:
# Convert each entry into IDF values
# IDF is the log of the inverse of document frequency
# Note that IDF is only a function of the term, so all columns will be identical.
IDF = np.log2(np.divide(NMatrix, np.array(DF)))
In [19]:
np.set_printoptions(precision=2,suppress=True)
print(IDF)
In [21]:
# Finally compute the TFxIDF values for each document-term entry
TD_tfidf = TD * IDF
In [22]:
pd.set_option("display.precision", 2)
TD_tfidf
Out[22]:
Now we are ready for clustering. We'll use the kMeans module of the MLA book from Ch. 10.¶
In [23]:
import kMeans
In [26]:
# First transpose to get the doc by term matrix and then call kMeans to cluster the docs
DT_tfidf = TD_tfidf.T
DT_tfidf = np.array(DT_tfidf)
centroids_tfidf, clusters_tfidf = kMeans.kMeans(DT_tfidf, 3, kMeans.distCosine, kMeans.randCent)
Let's take a look at the cluster centroids¶
In [31]:
pd.options.display.float_format='{:,.2f}'.format
centroids = pd.DataFrame(centroids_tfidf, columns=terms)
centroids
Out[31]:
Because the centroids are based on TFxIDF weights, they are not as descriptive as raw term frequencies or binary occurrence data. Let's redo the clustering with the original raw term frequencies.¶
In [32]:
DT = np.array(DT)
centroids, clusters = kMeans.kMeans(DT, 3, kMeans.distCosine, kMeans.randCent)
In [33]:
centroids = pd.DataFrame(centroids, columns=terms)
centroids
Out[33]:
The cluster centroids reveal some general patterns in the data as well as unique characterisitcs of each cluster. For example, it's clear that Cluster 0 is dominated by documents related to SQL databases while Cluster 1 contains documents primarily related to linear regresssion, etc.¶
In [35]:
# Let's look at cluster assigmens for each of the instances in the data.
print(clusters)
In [38]:
doc_clusters = pd.DataFrame(clusters, columns=["Cluster", "MinDistance**2"])
doc_clusters
Out[38]:
Next, let's use principal component analysis to reduce the dimensionality of the data:¶
In [39]:
from sklearn import decomposition
We'll perform PCA to obtain the top 5 components and then transform the DT matrix into the lower dimensional space of 5 components:¶
In [40]:
pca = decomposition.PCA(n_components=5)
DTtrans = pca.fit(DT).transform(DT)
In [42]:
np.set_printoptions(precision=2,suppress=True)
print(DTtrans)
In [43]:
print(pca.explained_variance_ratio_)
Looking at the above, it can be obsereved that the first 5 components capture (explain) 95% of the variance in the data.¶
Now, we can redo the clustering, but this time in the lower dimensional space:¶
In [44]:
centroids_pca, clusters_pca = kMeans.kMeans(DTtrans, 3, kMeans.distCosine, kMeans.randCent)
In [46]:
print(clusters_pca)
Next, let's actually derive the principal components manaually using linear algebra rather than relying on the PCA package from sklearn:¶
First step is to obtain the covariance matrix:¶
In [48]:
meanVals = np.mean(DT, axis=0)
meanRemoved = DT - meanVals #remove mean
covMat = np.cov(meanRemoved, rowvar=0)
np.set_printoptions(precision=2,suppress=True,linewidth=100)
print(covMat)
In [49]:
import numpy.linalg as la
eigVals,eigVects = la.eig(np.mat(covMat))
In [50]:
print(eigVals)
In [51]:
print(eigVects)
In [52]:
eigValInd = np.argsort(eigVals) #sort, sort goes smallest to largest
eigValInd = eigValInd[::-1] #reverse
sortedEigVals = eigVals[eigValInd]
print(sortedEigVals)
total = sum(sortedEigVals)
varPercentage = sortedEigVals/total*100
print(varPercentage)
We can plot the principal components based on the percentage of variance they capture:¶
In [53]:
import matplotlib.pyplot as plt
%matplotlib inline
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(range(1, 11), varPercentage[:10], marker='^')
plt.xlabel('Principal Component Number')
plt.ylabel('Percentage of Variance')
plt.show()
In [54]:
topNfeat = 5
topEigValInd = eigValInd[:topNfeat] #cut off unwanted dimensions
reducedEigVects = eigVects[:,topEigValInd] #reorganize eig vects largest to smallest
reducedDT = np.dot(meanRemoved, reducedEigVects) #transform data into new dimensions
print(reducedDT)
Next, let's look at an application of Singular Value Decomposition. This time, we'll foucs on the term-document matrix in order to find themes based on combinations of terms.¶
In [55]:
u, s, vt = np.linalg.svd(TD, full_matrices=False)
In [56]:
u = np.array([u[i]*(-1) for i in range(len(u))])
print(u)
In [57]:
vt = np.array([vt[i]*(-1) for i in range(len(vt))])
print(vt)
In [58]:
print(s)
In [59]:
print(np.diag(s))
In [60]:
# If we use all the dimensions of U.Sigma.Vt, we will get back to original matrix.
originalTD = np.dot(u, np.dot(np.diag(s), vt))
print(originalTD)
In [61]:
# But, the goal of SVD is to use a smaller number of dimensions each of which
# represent a latent variable capturing some cobminations of features associated
# with the data (e.g., general themes in the documents).
numDimensions = 3
u_ld = u[:, :numDimensions]
sigma = np.diag(s)[:numDimensions, :numDimensions]
vt_ld = vt[:numDimensions, :]
lowRankTD = np.dot(u_ld, np.dot(sigma, vt_ld))
In [62]:
# The U.Sigma.Vt in the lower dimensional space gives an approximation of the original materix
np.set_printoptions(precision=2,suppress=True,linewidth=120)
print(lowRankTD)
The VT matrix can be viewed as the new representation of documents in the lower dimensional space. Instead of row being terms (in the term by document matrix), now each row represents a latent "topic" or "theme" and so we have a topic by document matrix. You can think of each document (columns) being represented in term of the degree to which they reflect one of the topics.¶
In [64]:
print(vt_ld)
In information retrieval, a query is compared to documents using vector-space similarity between the query vector and document vectors. In the lower dim. space, this can be achieved by first mapping the query to lower dim. space, and then comparing it to docs in the lower dim. space.¶
In [65]:
queryVector = np.array([0,0,1,5,4,0,6,0,0,2])
lowDimQuery = np.dot(la.inv(sigma), np.dot(u_ld.T, queryVector))
print(lowDimQuery)
In [67]:
# Compute Cosine sim between the query and docs in the lower dimensional space
# first compute the normamlized versions of the query and the docs by dividing each vector by their norm
qNorm = lowDimQuery / la.norm(lowDimQuery)
docNorm = np.array([vt_ld[:,i]/la.norm(vt_ld[:,i]) for i in range(len(vt_ld[0]))])
print(docNorm)
In [68]:
# Cosine is now the dot product since the vectors are already normalized
sims = np.dot(qNorm, docNorm.T)
# return indices of the docs in decending order of similarity to the query
simInds = sims.argsort()[::-1]
for i in simInds:
print("Cosine similarity between Document %d and the query is: %.4f" %(i,sims[i]))
Now we can also cluster documents, but this time using only the low dimensional representation of the documents in terms of the latent topics.¶
In [69]:
centroids_svd, clusters_svd = kMeans.kMeans(vt_ld.T, 3, kMeans.distCosine, kMeans.randCent)
In [70]:
print(clusters_svd)
In [ ]: