# Dimensionality Reduction

## The Problem

There is an interesting tradeoff between model performance and a feature's dimensionality:


>*If the amount of available training data is fixed, then overfitting occurs if we keep adding dimensions. On the other hand, if we keep adding dimensions, the amount of **training data needs to grow exponentially fast to maintain the same coverage** and to avoid overfitting* ([Computer Vision for Dummies](http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/)).



### Multi-Collinearity

In many cases, there is a high degree of correlation between many of the features in a dataset. For instance, suppose that you


## Sparsity

- High dimensionality increases the sparsity of your features (**what NLP techniques have we used that illustrate this point?**)
- The density of the training samples decreases when dimensionality increases:
- **Distance measures (Euclidean, for instance) start losing their effectiveness**, because there isn't much difference between the max and min distances in higher dimensions.
- Many models that rely upon **assumptions of Gaussian distributions** (like OLS linear regression), Gaussian mixture models, Gaussian processes, etc. become less and less effective since their distributions become flatter and "fatter tailed".


What is the amount of data needed to maintain **20% coverage** of the feature space? For 1 dimension, it is **20% of the entire population's dataset**. For a dimensionality of $D$:

$$
X^{D} = .20
$$
$$
(X^{D})^{\frac{1}{D}} = .20^{\frac{1}{D}}
$$
$$
X = \sqrt[D]{.20}
$$
You can approximate this as 
```python
def coverage_requirement(requirement, D):
    return requirement ** (1 / D)

x = []
y = []
for d in range(1,20):
    y.append(coverage_requirement(0.10, d))
    x.append(d)
    
import matplotlib.pyplot as plt

plt.plot(x,y)
plt.xlabel("Number of Dimensions")
plt.ylabel("Appromximate % of Population Dataset")
plt.title("% of Dataset Needed to Maintain 10% Coverage of Feature Space")
plt.show()
```



```python
import pandas as pd
from sklearn.feature_extraction.text import CountVectorizer
reviews = pd.read_csv("mcdonalds-yelp-sentiment.csv", encoding='latin-1')
reviews = open("poor_amazon_toy_reviews.txt", encoding='latin-1')

#text = reviews["review"].values
text = reviews.readlines()

vectorizer = CountVectorizer(ngram_range=(3,3), min_df=0.01, max_df=0.75, max_features=200)
# tokenize and build vocab
vectorizer.fit(text)
vector = vectorizer.transform(text)
features = vector.toarray()
features_df = pd.DataFrame(features, columns=vectorizer.get_feature_names())

correlations = features_df.corr()
correlations_stacked = correlations.stack().reset_index()
#set column names
correlations_stacked.columns = ['Bi-Gram 1','Bi-Gram 2','Correlation']
correlations_stacked = correlations_stacked[correlations_stacked["Correlation"] < 1]
correlations_stacked = correlations_stacked.sort_values(by=['Correlation'], ascending=False)
correlations_stacked.head()
```


```python
# visualize the correlations (install seaborn first)!



```

# Principle Component Analysis

If you have an original matrix $Z$, you can decompose this matrix into two smaller matrices $X$ and $Q$. 

## Important Points:

- Multiplying a vector by a matrix typically changes the direction of the vector. For instance:
<figure>
  
    <figcaption><a href="https://lazyprogrammer.me/tutorial-principal-components-analysis-pca">Lazy Programmer- 
        Tutorial to PCA</a></figcaption>
</figure>

However, there are eigenvalues λ and eigenvectors $v$ such that

$$
\sum_{X}v = \lambda v
$$

Multiplying the eigenvectors $v$ with the eigenvalue $\lambda$ does not change the direction of the eigenvector.

Multiplying the eigenvector $v$ by the covariance matrix $\sum_{X}$ also does not change the direction of the eigenvector.

If our data $X$ is of shape $N \times D$, it turns out that we have $D$ eigenvalues and $D$ eigenvectors. This means we can arrange the eigenvalues $\lambda$ in decreasing order so that

$$
\lambda_3 > \lambda_2 > \lambda_5
$$

In this case, $\lambda_3$ is the largest eigenvalue, followed by $\lambda_2$, and then $\lambda_5$. Then, we can arrange 

We can also rearrange the eigenvectors the same: $v_3$ will be the first column, $v_2$ will be the second column, and $v_5$ will be the third column.

We'll end up with two matrices $V$ and $\Lambda$:
<figure>
  
    <figcaption><a href="https://lazyprogrammer.me/tutorial-principal-components-analysis-pca">Lazy Programmer- 
        Tutorial to PCA</a></figcaption>
</figure>


```python
# what is the shape of our features?
features.shape
```


```python
from sklearn.decomposition import PCA

pca = PCA(n_components=4)

Z = pca.fit_transform(features)

# what is the shape of Z?
Z.shape
```


```python
# what will happen if we take the correlation matrix and covariance matrix of our new reduced features?
import numpy as np
covariances = pd.DataFrame(np.cov(Z.transpose()))
plt.rcParams["figure.figsize"] = (5,5)
sns.heatmap(covariances)
```


```python
# train the model to reduce the dimensions down to 2
pca = PCA(n_components=2)
Z_two_dimensions = pca.fit_transform(features)
Z_two_dimensions
```


```python
import matplotlib.pyplot as plt

plt.scatter(Z_two_dimensions[:,0], Z_two_dimensions[:, 1])
reduced_features_df = pd.DataFrame(Z_two_dimensions, columns=["x1", "x2"])
reduced_features_df["text"] = text
```

# Singular Value Decomposition

Given an input matrix $A$, we want to try to represent it instead as three smaller matrices $U$, $\sum$, and $V$. Instead of **$n$ original terms**, we want to represent each document as **$r$ concepts** (other referred to as **latent dimensions**, or **latent factors**):
<figure>
  
    <figcaption><i>
        <a href="https://www.youtube.com/watch?v=P5mlg91as1c">Mining of Massive Datasets - Dimensionality Reduction: Singular Value Decomposition</a> by Leskovec, Rajaraman, and Ullman (Stanford University)</i></figcaption>
</figure>

Here, **$A$ is your matrix of word vectors** - you could use any of the word vectorization techniques we have learned so far, include one-hot encoding, word count, TF-IDF.

- $\sum$ will be a **diagonal matrix** with values that are positive and sorted in decreasing order. Its value indicate the **variance (information encoded on that new dimension)**- therefore, the higher the value, the stronger that dimension is in capturing data from A, the original features. For our purposes, we can think of the rank of this $\sum$ matrix as the number of desired dimensions. Instance, if we want to reduce $A$ from shape $1020 x 300$ to $1020 x 10$, we will want to reduce the rank of $\sum$ from 300 to 10.

- $U^T U = I$ and $V^T V = I$

## Measuring the Quality of the Reconstruction

A popular metric used for measuring the quality of the reconstruction is the [Frobenius Norm](https://en.wikipedia.org/wiki/Matrix_norm#Frobenius_norm). When you explain your methodology for reducing dimensions, usually managers / stakeholders will want to some way to compare multiple dimensionality techniques' ability to quantify its ability to retain information but trim dimensions:

$$
\begin{equation}
||A_{old}-A_{new}||_{F} = \sqrt{\sum_{ij}{(A^{old}_{ij}- A^{new}_{ij}}})^2
\end{equation}
$$

## Heuristic Step for How Many Dimensions to Keep

1. Sum the $\sum$ matrix's diagonal values: 
$$
\begin{equation}
\sum_{i}^{m}\sigma_{i}
\end{equation}
$$

2. Define your threshold of "information" (variance) $\alpha$ to keep: usually 80% to 90%. 

3. Define your cutoff point $C$: $$
\begin{equation}
C = \sum_{i}^{m}\sigma_{i} \alpha
\end{equation}
$$

4. Beginning with your largest singular value, sum your singular values $\sigma_{i}$ until it is greater than C. Retain only those dimensions.

<figure>
  
    <figcaption><i>
        <a href="https://www.youtube.com/watch?v=P5mlg91as1c">Mining of Massive Datasets - Dimensionality Reduction: Singular Value Decomposition</a> by Leskovec, Rajaraman, and Ullman (Stanford University)</i></figcaption>
</figure>



```python
# create sample data

import numpy as np
import matplotlib.pyplot as plt
from scipy.linalg import svd
x = np.linspace(1,20, 20) # create the first dimension
x = np.concatenate((x,x))
y = x + np.random.normal(0,1, 40) # create the second dimension
z = x + np.random.normal(0,2, 40) # create the third dimension
a = x + np.random.normal(0,4, 40) # create the fourth dimension
plt.scatter(x,y) # plot just the first two dimensions
plt.show()
```


```python
# create matrix
A = np.stack([x,y,z,a]).T
```


```python
# perform SVD
D = 1
U, s, V = svd(A)
print(f"s is {s}\n")
print(f"U is {U}\n")
print(f"V is {V}")
```


```python
# Frobenius norm

s[D:] = 0
S = np.zeros((A.shape[0], A.shape[1]))
S[:A.shape[1], :A.shape[1]] = np.diag(s)
A_reconstructed = U.dot(S.dot(V))
np.sum((A_reconstructed - A) ** 2) ** (1/2) # Frobenius norm
# reconstruct matrix
U.dot(S)
```

# GLOVE

Global vectors for word presentation:
<figure>
  
    <figcaption><i>
        <a href="https://nlp.stanford.edu/pubs/glove.pdf">GloVe: Global Vectors for Word Representation</a></i></figcaption>
</figure>


```python
# import glove embeddings into a word2vec format that is consumable by Gensim
from gensim.scripts.glove2word2vec import glove2word2vec
glove_input_file = 'glove.6B.100d.txt'
word2vec_output_file = 'glove.6B.100d.txt.word2vec'
glove2word2vec(glove_input_file, word2vec_output_file)
```




    (400000, 100)




```python
from gensim.models import KeyedVectors
# load the Stanford GloVe model
filename = 'glove.6B.100d.txt.word2vec'
model = KeyedVectors.load_word2vec_format(filename, binary=False)
# calculate: (king - man) + woman = ?
result = model.most_similar(positive=['woman', 'king'], negative=['man'], topn=1)
print(result)
```

    [('queen', 0.7698541283607483)]



```python
words = ["woman", "king", "man", "queen", "puppy", "kitten", "cat", 
         "quarterback", "football", "stadium", "touchdown",
         "dog", "government", "tax", "federal", "judicial", "elections",
         "avocado", "tomato", "pear", "championship", "playoffs"]

vectors = [model.wv[word] for word in words]

import pandas as pd
vector_df = pd.DataFrame(vectors)
vector_df["word"] = words
vector_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
      <th>8</th>
      <th>9</th>
      <th>...</th>
      <th>91</th>
      <th>92</th>
      <th>93</th>
      <th>94</th>
      <th>95</th>
      <th>96</th>
      <th>97</th>
      <th>98</th>
      <th>99</th>
      <th>word</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.59368</td>
      <td>0.44825</td>
      <td>0.59320</td>
      <td>0.074134</td>
      <td>0.111410</td>
      <td>1.27930</td>
      <td>0.16656</td>
      <td>0.240700</td>
      <td>0.39045</td>
      <td>0.32766</td>
      <td>...</td>
      <td>-0.22008</td>
      <td>0.824010</td>
      <td>-0.092207</td>
      <td>-0.459410</td>
      <td>0.465710</td>
      <td>-0.56018</td>
      <td>-0.54648</td>
      <td>0.151620</td>
      <td>-0.30754</td>
      <td>woman</td>
    </tr>
    <tr>
      <th>1</th>
      <td>-0.32307</td>
      <td>-0.87616</td>
      <td>0.21977</td>
      <td>0.252680</td>
      <td>0.229760</td>
      <td>0.73880</td>
      <td>-0.37954</td>
      <td>-0.353070</td>
      <td>-0.84369</td>
      <td>-1.11130</td>
      <td>...</td>
      <td>-0.71320</td>
      <td>0.089623</td>
      <td>0.413940</td>
      <td>-1.336300</td>
      <td>-0.619150</td>
      <td>-0.33089</td>
      <td>-0.52881</td>
      <td>0.164830</td>
      <td>-0.98878</td>
      <td>king</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.37293</td>
      <td>0.38503</td>
      <td>0.71086</td>
      <td>-0.659110</td>
      <td>-0.001013</td>
      <td>0.92715</td>
      <td>0.27615</td>
      <td>-0.056203</td>
      <td>-0.24294</td>
      <td>0.24632</td>
      <td>...</td>
      <td>-0.37501</td>
      <td>0.457420</td>
      <td>0.045975</td>
      <td>-0.246750</td>
      <td>0.045656</td>
      <td>-0.38302</td>
      <td>-0.93711</td>
      <td>0.039138</td>
      <td>-0.53911</td>
      <td>man</td>
    </tr>
    <tr>
      <th>3</th>
      <td>-0.50045</td>
      <td>-0.70826</td>
      <td>0.55388</td>
      <td>0.673000</td>
      <td>0.224860</td>
      <td>0.60281</td>
      <td>-0.26194</td>
      <td>0.738720</td>
      <td>-0.65383</td>
      <td>-0.21606</td>
      <td>...</td>
      <td>-0.70584</td>
      <td>0.430120</td>
      <td>0.510510</td>
      <td>-0.803300</td>
      <td>-0.665720</td>
      <td>-0.63717</td>
      <td>-0.36032</td>
      <td>0.133470</td>
      <td>-0.56075</td>
      <td>queen</td>
    </tr>
    <tr>
      <th>4</th>
      <td>0.69548</td>
      <td>0.66222</td>
      <td>0.24528</td>
      <td>-1.130400</td>
      <td>-0.768530</td>
      <td>0.10149</td>
      <td>0.36038</td>
      <td>0.048728</td>
      <td>0.13055</td>
      <td>-0.16981</td>
      <td>...</td>
      <td>0.34369</td>
      <td>0.015695</td>
      <td>0.099343</td>
      <td>-0.004544</td>
      <td>-0.736170</td>
      <td>-0.10185</td>
      <td>0.43978</td>
      <td>-0.003745</td>
      <td>-0.48888</td>
      <td>puppy</td>
    </tr>
  </tbody>
</table>
<p>5 rows × 101 columns</p>
</div>




```python
%matplotlib inline
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
from sklearn.decomposition import TruncatedSVD
import matplotlib.pyplot as plt

dimension_model = PCA(n_components=2)
reduced_vectors = dimension_model.fit_transform(vectors)

for i, vector in enumerate(reduced_vectors):
    x = vector[0]
    y = vector[1]
    plt.plot(x,y, 'bo')
    plt.text(x * (1 + 0.01), y * (1 + 0.01) , words[i], fontsize=12)


```

# Clustering Text


```python
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=4)
cluster_assignments = kmeans.fit_predict(reduced_vectors)
for cluster_assignment, word in zip(cluster_assignments, words):
    print(f"{word} assigned to cluster {cluster_assignment}")

```

    woman assigned to cluster 1
    king assigned to cluster 1
    man assigned to cluster 1
    queen assigned to cluster 1
    puppy assigned to cluster 3
    kitten assigned to cluster 3
    cat assigned to cluster 3
    quarterback assigned to cluster 2
    football assigned to cluster 2
    stadium assigned to cluster 2
    touchdown assigned to cluster 2
    dog assigned to cluster 3
    government assigned to cluster 0
    tax assigned to cluster 0
    federal assigned to cluster 0
    judicial assigned to cluster 0
    elections assigned to cluster 0
    avocado assigned to cluster 3
    tomato assigned to cluster 3
    pear assigned to cluster 3
    championship assigned to cluster 2
    playoffs assigned to cluster 2



```python
color_map = {
    0: "r",
    1: "b",
    2: "g",
    3: "y"
}

plt.rcParams["figure.figsize"] = (10,10)

for i, vector in enumerate(reduced_vectors):
    x = vector[0]
    y = vector[1]
    plt.plot(x,y, 'bo', c=color_map[cluster_assignments[i]])
    plt.text(x * (1 + 0.01), y * (1 + 0.01) , words[i], fontsize=12)
```


```python

```

876c7829188860c828fba5935942ac6c5e011171
ipynb
Jupyter Notebook
week7/Dimensionality Reduction and Clustering.ipynb
ychennay/dso-599-text-analytics-nlp
e02e136d24e5a704e2ad69c599e89f9173072968
MIT
2019-03-06T02:34:41.000Z
2021-12-28T23:06:57.000Z
week7/Dimensionality Reduction and Clustering.ipynb
ychennay/dso-599-text-analytics-nlp
e02e136d24e5a704e2ad69c599e89f9173072968
MIT
week7/Dimensionality Reduction and Clustering.ipynb
ychennay/dso-599-text-analytics-nlp
e02e136d24e5a704e2ad69c599e89f9173072968
MIT
2019-03-06T02:25:01.000Z
2021-04-09T14:02:09.000Z
Qwen/Qwen-72B
1. YES
2. YES