<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Lab 4
Ryan Rose
Scientific Computing
9/21/2016
Step1:  Loading Fifty Books
First, we load all fifty books from their text files.
Step2:  Cleaning up the Data
Next, we create a mapping of titles to their book's text along with removing the Project Gutenberg header and footer.
Step3:  Next, we iterate through all of the words, strip all characters that are not upper or lower-case letters. If the the resulting word is considered, non-empty, we throw it out. Else, we add the word in all lowercase stripped of all non-ASCII letters to our list of words for that book.
This is useful to determine word frequencies.
Step4:  Determining Frequencies
Now, we determine the frequencies for each word and putting them in a dictionary for each book.
Step5:  Top 20 Words
Now, let's determine the top 20 words across the whole corpus
Step6:  Creating the 20-dimensional vectors
Using the top 20 words above, let's determine the book vectors.
Step7:  Creating the Elbow Graph
Let's try each k and see what makes the sharpest elbow.
Step8:  We can see that the best k is 3 or 6.
Clustering
Let's cluster based on k = 3 and plot the clusters.
Step9:  Do the clusters make sense?
Yes. For instance, we can see that The Republic and The Iliad of Homer are in the same cluster. 
Performing PCA
Now, let's perform PCA and determine the most important elements and plot the clusters.
Step10:  We can see the data clusters well and the most important words are i and the based on them having the standard deviation. This is based on the concept of PCA.fracs aligning to the variance based on this documentation
Step11:  Now, let's do k-means based on the previously determined k.
Step12:  We can see that the new book is the black square above. In addition, it makes sense it fits into that cluster especially when we compare it to Jane Eyre.
Stop Words
Step13:  We can see that our k could be 3 or 7. Let's choose 7.
<ASSISTANT_TASK:>
Python Code:
## Imports!
%matplotlib inline
import os
import re
import string
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from matplotlib.mlab import PCA
from scipy.cluster.vq import kmeans, vq
Explanation: Lab 4
Ryan Rose
Scientific Computing
9/21/2016
End of explanation
os.chdir("/home/ryan/School/scientific_computing/labs/lab4/books")
filenames = os.listdir()
books = []
for name in filenames:
    with open(name) as f:
        books.append(f.read())
Explanation: Loading Fifty Books
First, we load all fifty books from their text files.
End of explanation
def get_title(text):
    pattern = "\*\*\*\s*START OF (THIS|THE) PROJECT GUTENBERG EBOOK ([A-Z,;' ]*)\*\*\*"
    m = re.search(pattern, text)
    if m:
        return m.group(2).strip()
    return None
def remove_gutenberg_info(text):
    pattern = "\*\*\*\s*START OF (THIS|THE) PROJECT GUTENBERG EBOOK ([A-Z,;' ]*)\*\*\*"
    start = re.search(pattern, text).end()
    pattern = "\*\*\*\s*END OF (THIS|THE) PROJECT GUTENBERG EBOOK ([A-Z,;' ]*)\*\*\*"
    end = re.search(pattern, text).start()
    return text[start:end]
cut_off_books = { get_title(book):remove_gutenberg_info(book) for book in books}
pd.DataFrame(cut_off_books, index=["Book's Text"]).T.head()
Explanation: Cleaning up the Data
Next, we create a mapping of titles to their book's text along with removing the Project Gutenberg header and footer.
End of explanation
def strip_word(word, alphabet):
    ret = ""
    for c in word:
        if c in alphabet:
            ret += c.lower()
    if len(ret) == 0:
        return None
    else:
        return ret
def get_words(book):
    alphabet = set(string.ascii_letters)
    b = book.split()
    words = []
    for word in b:
        w = strip_word(word, alphabet)
        if w:
            words.append(w)
    return words
cut_books = {name:get_words(book) for name, book in cut_off_books.items()}
Explanation: Next, we iterate through all of the words, strip all characters that are not upper or lower-case letters. If the the resulting word is considered, non-empty, we throw it out. Else, we add the word in all lowercase stripped of all non-ASCII letters to our list of words for that book.
This is useful to determine word frequencies.
End of explanation
def get_word_freq(words):
    word_counts = {}
    for word in words:
        if word in word_counts:
            word_counts[word] += 1
        else:
            word_counts[word] = 1
    return word_counts
book_freqs = {}
for name, words in cut_books.items():
    book_freqs[name] = get_word_freq(words)
Explanation: Determining Frequencies
Now, we determine the frequencies for each word and putting them in a dictionary for each book.
End of explanation
total_word_count = {}
for dicts in book_freqs.values():
    for word, count in dicts.items():
        if word in total_word_count:
            total_word_count[word] += count
        else:
            total_word_count[word] = count
a, b = zip(*total_word_count.items())
tuples = list(zip(b, a))
tuples.sort()
tuples.reverse()
tuples[:20]
_, top_20_words = zip(*tuples[:20])
top_20_words
Explanation: Top 20 Words
Now, let's determine the top 20 words across the whole corpus
End of explanation
def filter_frequencies(frequencies, words):
    d = {}
    for word, freq in frequencies.items():
        if word in words:
            d[word] = freq
    return d
labels = {}
for name, freqs in book_freqs.items():
    labels[name] = filter_frequencies(freqs, top_20_words)
df = pd.DataFrame(labels).fillna(0)
df = (df / df.sum()).T
df.head()
Explanation: Creating the 20-dimensional vectors
Using the top 20 words above, let's determine the book vectors.
End of explanation
kvals = []
dists = []
for k in range(2, 11):
    centroids, distortion = kmeans(df, k)
    kvals.append(k)
    dists.append(distortion)
plt.plot(kvals, dists)
plt.show()
Explanation: Creating the Elbow Graph
Let's try each k and see what makes the sharpest elbow.
End of explanation
centroids, _ = kmeans(df, 3)
idx, _ = vq(df, centroids)
clusters = {}
for i, cluster in enumerate(idx):
    if cluster in clusters:
        clusters[cluster].append(df.iloc[i].name)
    else:
        clusters[cluster] = [df.iloc[i].name]
clusters
Explanation: We can see that the best k is 3 or 6.
Clustering
Let's cluster based on k = 3 and plot the clusters.
End of explanation
m = PCA(df)
fig, ax = plt.subplots()
for i in range(len(idx)):
    plt.plot(m.Y[idx==i, 0], m.Y[idx==i, 1], "o", alpha=.75)
for index, (x, y) in enumerate(zip(m.Y[:, 0], m.Y[:, 1])):
    plt.text(x, y, df.index[index])
    
fig.set_size_inches(36,40)
plt.show()
m.sigma.sort_values()[-2:]
Explanation: Do the clusters make sense?
Yes. For instance, we can see that The Republic and The Iliad of Homer are in the same cluster. 
Performing PCA
Now, let's perform PCA and determine the most important elements and plot the clusters.
End of explanation
with open("../pg45.txt") as f:
    anne = f.read()
get_title(anne)
anne_cut = remove_gutenberg_info(anne)
anne_words = get_words(anne_cut)
anne_freq = {get_title(anne):filter_frequencies(get_word_freq(anne_words), top_20_words)}
anne_frame = pd.DataFrame(anne_freq).fillna(0)
anne_frame = (anne_frame / anne_frame.sum()).T
anne_frame
Explanation: We can see the data clusters well and the most important words are i and the based on them having the standard deviation. This is based on the concept of PCA.fracs aligning to the variance based on this documentation: https://www.clear.rice.edu/comp130/12spring/pca/pca_docs.shtml. And, since PCA.sigma is the square root of the variance, the highest standard deviation should correspond to the highest value for the PCA.fracs. Then, i and the are the most important words  
New Book
So, we continue as before by loading Anne of Green Gables, parsing it, creating an array, and normalizing the book vector.
End of explanation
df_with_anne = df.append(anne_frame).sort_index()
centroids, _ = kmeans(df_with_anne, 3)
idx2, _ = vq(df_with_anne, centroids)
clusters = {}
for i, cluster in enumerate(idx2):
    if cluster in clusters:
        clusters[cluster].append(df_with_anne.iloc[i].name)
    else:
        clusters[cluster] = [df_with_anne.iloc[i].name]
clusters
coords = m.project(np.array(anne_frame).flatten())
fig, _ = plt.subplots()
plt.plot(coords[0], coords[1], "s", markeredgewidth=5)
for i in range(len(idx)):
    plt.plot(m.Y[idx==i, 0], m.Y[idx==i, 1], "o", alpha=.75)
for index, (x, y) in enumerate(zip(m.Y[:, 0], m.Y[:, 1])):
    plt.text(x, y, df.index[index])
    
fig.set_size_inches(36,40)
plt.show()
Explanation: Now, let's do k-means based on the previously determined k.
End of explanation
stop_words_text = open("../common-english-words.txt").read()
stop_words = stop_words_text.split(",")
stop_words[:5]
word_counts_without_stop = [t for t in tuples if t[1] not in stop_words]
word_counts_without_stop[:20]
_, top_20_without_stop = zip(*word_counts_without_stop[:20])
top_20_without_stop
no_stop_labels = {}
for name, freqs in book_freqs.items():
    no_stop_labels[name] = filter_frequencies(freqs, top_20_without_stop)
df_without_stop = pd.DataFrame(no_stop_labels).fillna(0)
df_without_stop = (df_without_stop / df_without_stop.sum()).T
df_without_stop.head()
kvals = []
dists = []
for k in range(2, 11):
    centroids, distortion = kmeans(df_without_stop, k)
    kvals.append(k)
    dists.append(distortion)
plt.plot(kvals, dists)
plt.show()
Explanation: We can see that the new book is the black square above. In addition, it makes sense it fits into that cluster especially when we compare it to Jane Eyre.
Stop Words
End of explanation
centroids, _ = kmeans(df_without_stop, 7)
idx3, _ = vq(df, centroids)
clusters = {}
for i, cluster in enumerate(idx3):
    if cluster in clusters:
        clusters[cluster].append(df_without_stop.iloc[i].name)
    else:
        clusters[cluster] = [df_without_stop.iloc[i].name]
clusters
m2 = PCA(df_without_stop)
fig, _ = plt.subplots()
for i in range(len(idx3)):
    plt.plot(m2.Y[idx3==i, 0], m2.Y[idx3==i, 1], "o", alpha=.75)
    
for index, (x, y) in enumerate(zip(m2.Y[:, 0], m2.Y[:, 1])):
    plt.text(x, y, df_without_stop.index[index])
    
fig.set_size_inches(36,40)
plt.show()
m2.sigma.sort_values()[-2:]
Explanation: We can see that our k could be 3 or 7. Let's choose 7.
End of explanation
<END_TASK>