\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{float}
\usepackage{amssymb,amsmath}
\usepackage[colorlinks,linkcolor=blue,urlcolor=blue,citecolor=black]{hyperref} % Create hyperlinks within the document
\usepackage{url}

\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\usepackage{caption}
\DeclareCaptionType{code}[Code Listing][List of Code Listings] 

\lstset{frame=tb,
  language=python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true
  tabsize=3
}



%homework
%\long\def\comment#1{}
%solution
\long\def\comment{}

\newcommand{\lit}[1]{\fbox{\texttt{#1}}}

\begin{document}

\title{{\bf CSXXX: NLP/Text Mining for Security}\\
       Homework Assignment \#5:\\
      Text Clustering  }

\author{}

\date{Out: Month date, Year\\
      Due: Month date, Year\\
      (xxxxx needs to be turned-in)}
\maketitle
For this part, you will implement a basic K-means clustering engine for finding
clusters in a collection of text documents. We will use the 20,000
newsgroup postings
\url{http://kdd.ics.uci.edu/databases/20newsgroups/20_newsgroups.tar.gz}. Treat
each posting (one posting per file) as a unique document.

For this assignment, we will treat the newsgroup directories as labels that are
unavailable to your clustering engine. That is, you will cluster the documents
based only on the contents of the documents, without knowledge of the newsgroup
each document actually belongs to. Your goal is straightforward: consume the
newsgroup postings, tokenize, and for some value of k find k clusters. You will
want to run the clustering repeatedly with different starting conditions to find
the "best" clustering.      

To evaluate the quality of your clustering, you should use purity. Recall that
purity is an external criterion requiring a ground truth "correct" assignment of
documents to classes. For the purpose of this homework we will treat the
newsgroup directories as the "correct" classes for each document, so you can
calculate the purity of your clustering versus this external criterion.        

Now for some details: when you tokenize your documents you should remove all of
the header materials (e.g., lines beginning with "Xref: ..." or "Path: ..." or
"NNTP-Posting-Host: ..."). Be careful to remove all of the header materials,
which you will see vary from message to message. For the remaining content, you
should lowercase everything. Consider as valid tokens all sequences of alphabet
characters [a-z] of length 4 or greater. You may additionally throw out any
valid token which occurs 1, 2, or 3 times across the space of all documents. For
weighting, you should use simple term frequency weights (no logs, just counts of
the frequency of a term within a document). Each document vector should be
length-normalized.         

For this problem, you should report the purity for k=2, k=5, k=10, k=20, and
k=40. At which k do you see the best purity? Why do you suppose this is the
case?    

You will find that there are many implementations of k-means available online.
You are welcome to study this code, but we expect you to write your own code to
solve this part and the following part.    
\end{document}
