\documentclass[12pt]{report}   % list options between brackets
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{bm}
\usepackage{float}
\usepackage{graphicx} % list packages between braces
\graphicspath{ {images/} }
\usepackage{caption}
\usepackage{subcaption}
\usepackage{url}
\usepackage{todonotes}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage[T1]{fontenc}
\usepackage{libertine}
\usepackage[scaled=0.80]{beramono}
\usepackage{longtable}
\usepackage{hyperref}

% type user-defined commands here
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}

\setlength{\parindent}{0pt}
\setlength{\parskip}{0.1in}

\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

\begin{document}

\thispagestyle{empty}
\pagenumbering{roman}
\begin{center}

% TITLE
{\Huge Clustering and Topic Analysis \\ Final Report}

\vfill

\Large CS 5604 Information Storage and Retrieval

\vfill

Virginia Polytechnic Institute and State University \\
Fall 2017

\vfill

Submitted by \\
\vfill
\begin{table}[!htb]
\centering
\begin{tabular}{cc}
Ashish Baghudana   & Aman Ahuja      \\
Pavan Bellam &Rammohan Chintha   \\
Prathyush Sambaturu    & Ashish Malpani \\
Shruti Shetty   & Mo Yang
\end{tabular}
\end{table}
\vfill
December 15, 2017 \\
Blacksburg, Virginia 24061

\vfill
Instructor: Dr. Edward A. Fox

\end{center}

\pagebreak

\thispagestyle{empty}

\begin{abstract}
One of the key objectives of the CS-5604 course titled Information Storage and Retrieval is to build a pipeline for a state-of-the-art retrieval system for the Integrated Digital Event Archiving and Library (IDEAL) and Global Event and Trend Archive Research (GETAR) projects. The GETAR project, in collaboration with the Internet Archive, aims to develop an archive of webpages and tweets related to multiple events and trends that occur in the world, and develop a retrieval system to extract information from that archive.

Since it is practically impossible to manually look through all the documents in a large corpus, an important component of any retrieval system is a module that is able to group and summarize meaningful information. The Clustering and Topic Analysis (CTA) team aims to build this component for the GETAR project.

Our report examines the various techniques underlying clustering and topic analysis, discusses technology choices and implementation details, and, describes the results of the \textit{k}-means algorithm and latent Dirichlet allocation (LDA) on different collections of webpages and tweets. Subsequently, we provide a developer manual to help set up our framework, and finally, outline a user manual describing the fields that we populate in HBase.
% * <fox@vt.edu> 2017-12-17T23:33:10.313Z:
% 
% > .
% Add some details. How many events, how many webpage collections, how many tweet collections, how many clusters, how many topics, scalability findings, timings, approach to labeling, etc.
% 
% Add at top of Contents an entry for each of table of figures, table of tables
% 
% ^.
\end{abstract}

\tableofcontents
\pagebreak

\listoffigures
\pagebreak

\listoftables
\pagebreak

\pagenumbering{arabic}
\pagestyle{myheadings}

\chapter{Introduction}
The CS5604 course project aims to build a state-of-the-art information retrieval (IR) system in support of the Integrated Digital Event Archiving and Library (IDEAL) and Global Event and Trend Archive Research (GETAR) projects. The semester-long project is divided into several subareas undertaken by different teams. These are Classification (CLA), Collection Management Tweets (CMT), Collection Management Webpages (CMW), Clustering and Topic Analysis (CTA), Database and Indexing (SOLR), and Front-end and Visualization (FE). This report focuses on the results of the Clustering and Topic Analysis (CTA) team.

\section{Problem Statement}
Building a state-of-the-art information retrieval system involves several components. Each component is handled by a team. CMW and CMT crawl/collect from the Internet to fetch event related webpages and tweets, respectively. CLA refines the data processed by CMW and CMT to classify webpages and tweets with a specific event. Our team (CTA) takes classified data to learn cluster(s) and keywords/topics for each of the documents so that SOLR can index these documents using Lily. This will help FE fetch documents from the computer cluster when a user searches for something.

A naive solution to extract keywords would be to find the top-$n$ used words in the entire collection. There are two major problems with this approach. First, it assumes all documents in a collection talk about the same keywords. It would not allow users to search for different facets of an event -- such as, relief-related documents vs. destruction-related documents in the collection \textit{Hurricane Harvey}. Second, it is possible that a document may be about \textit{school shootings} without mentioning the words ``school'' or ``shooting''.

Clustering and topic modeling algorithms help identify semantically related words not just in a single document, but across similar documents. For instance, if ``gun'' occurred frequently with ``school'' and ``shooting'', a search for ``gun'' would yield results about \textit{school shootings}. These algorithms also help us identify recurring sub-themes within the collection. This is particularly important in documents about events as they often talk about different aspects of the event. As an example, these algorithms can identify different facets of the event \textit{Hurricane Irma}. Some articles talk about ``destruction'' and ``damage'', while others talk about ``weather'' and ``storm''.

Once we find the themes in the corpus, the documents will be indexed using the discovered topics and clusters to improve the quality of search and retrieval. The front-end team uses these topics to design a faceted search. These topics can also be used to validate the results of the clustering algorithms and vice-versa.

The approaches for clustering and topic modeling are discussed in the subsequent subsections.
More background information is described in Chapter 2.

\section{Clustering}
Clustering can be intuitively thought of as a process of placing similar objects close to each other and dissimilar objects away from each other. It is an example of an unsupervised form of learning where grouping into natural categories takes place when no class label is available. In clustering the goal is to reduce the distance between objects in the same cluster and have increasing distance between objects of different clusters \cite{Doe:2016:Online}.

Clustering can be used for finding latent groupings that will later be useful for categorization. It may help to gain insight into the nature of the data. In addition, it may also lead to discovery of distinct subclasses or similarities among patterns. Clustering can be classified into two categories based on the assignment of objects. 

\begin{enumerate}
\item \textbf{Hard clustering:} Each data point is assigned to only one of the given clusters.
\item \textbf{Soft Clustering:} Instead of putting each data point into a separate cluster, a probability or likelihood is assigned for a data point being in a cluster.
\end{enumerate}

Clustering algorithms can be grouped into different types of generating models. These are:

\begin{enumerate}

\item \textbf{Centroid Models:}
In these algorithms the similarity is derived from the closeness of the data point to the centroid of the clusters. These are iterative type algorithms, and the popular \textit{k}-means clustering algorithm falls under this category. It is described in Algorithm \ref{kmeans-algorithm}.

\begin{algorithm}[H]
\caption{The \textit{k}-means algorithm}\label{kmeans-algorithm}
\begin{algorithmic}[1]
\Procedure{KMeans}{$k, data$}
\State $centroids\gets $ randomly select $K$ points from $data$ as initial centroids
\While{centroids do not change}\Comment{This is the convergence criterion}
\For{$i\gets 1, k$}
\State $centroids[i]\gets$ Recompute centroid for cluster $i$
\EndFor
\EndWhile
\State \textbf{return} $centroids$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The closeness of data points in the cluster is represented by a distance measure. 
This could be based on the \textit{L1}-distance, \textit{L2}-distance, cosine similarity, correlation, or sum of squared errors.

\item \textbf{Distribution Models:}
In Distribution Models, the data points are related to each other based on their likelihood of belonging to the same probability distribution. Popular algorithms like Expectation-Maximization (EM) and Gaussian Mixture Model (GMM) fall under this category.

Initially we start with a fixed number of distributions and iteratively update to fit the data distribution such that the likelihood of the data given the distribution is maximized.

\item \textbf{Hierarchical Models:}
These models hierarchically aggregate or divide points into clusters based on their distance from each other. The two main components of hierarchical models are the distance function (distance between points) and the link function (distance between clusters). Based on the recursive approach, there are two types of hierarchical models. 
\begin{itemize}
    \item \textbf{Agglomerative Clustering Approach:} Start with all data points as individual clusters and aggregate them to form clusters.
    \item \textbf{Divisive Clustering Approach:} Start with all data points as a single cluster and partition the large cluster to form smaller clusters.
\end{itemize}
These models are very easy to interpret but lack scalability for handling big datasets.

\item \textbf{Density Models:}
These models search the data space for areas of varied density of data points in the data space. They isolate various different density regions and assign the data points within these regions in the same cluster. DBSCAN is a popular example of a density model.
\end{enumerate}

In this report, we focus on centroid and hierarchical clustering techniques, namely \textit{k}-means and Agglomerative Clustering using bag-of-words as feature vectors. For each cluster, we output the $n$-most frequent words in the cluster and set these as keywords for all documents in that cluster.

\section{Topic Analysis}

Topic analysis or topic modeling aims to find latent (\textit{hidden}) groups of words, called \textit{topics}, from a large corpus of text documents. The topics discovered by these techniques can be defined as groups (\textit{or themes}) of semantically similar words. Topic modeling uses statistical techniques to discover these topics, by using co-occurrence of words in the documents. Given a set of documents about ``computers'', ``basketball'', and ``economics'', sample words in each of the topics are given in Table \ref{table:wikipedia-lda-topics}.
% * <fox@vt.edu> 2017-12-18T00:40:13.720Z:
% 
% > Table
% Where did this example come from? If from a source, please cite it. If you ran this yourself, say more about what you did.  If it is not a real example, consider having one here from the data you have generated, which would be more interesting.
% 
% ^.

\begin{table}[htb]
\centering
\begin{tabular}{|l|l|l|}
\hline
\textbf{Topic 1} & \textbf{Topic 2} & \textbf{Topic 3} \\ \hline
computer & basketball & economic \\
game & team  & economy \\
ibm & league & government \\
program & team & investment \\
machine & coach & market  \\
design & player & trade  \\
software & nba & growth \\
memory & ncaa & policy \\ \hline
\end{tabular}
\caption{Sample topics from a collection of Wikipedia articles collected using a keyword search for ``computers'', ``basketball'', and ``economics''}
\label{table:wikipedia-lda-topics}
\end{table}

\begin{algorithm}[H]
\caption{Latent Dirichlet Allocation Algorithm}\label{lda-algorithm}
\begin{algorithmic}[1]
\Procedure{LDA}{$k$, $documents$, $iterations$}
\State Randomly initialize topic assignments \bm{$Z$}
\ForEach{iteration}
\ForEach{document}
\For{word $w \gets 1$, number of words in document}
\State $z \gets $ sampleTopic($w$) \Comment{Ignore current assignment when sampling}
\State Update topic assignments \bm{$Z$}
\EndFor
\EndFor
\EndFor
\State \textbf{return} topic assignments \bm{$Z$}
\EndProcedure
\end{algorithmic}
\end{algorithm}

Recent work in topic modeling is based on Latent Dirichlet Allocation (LDA) \cite{blei2002latent}. LDA is a probabilistic generative model that observes the word frequencies and co-occurrence in documents and infers the topic distribution based on sampling techniques. It models each document as a mixture over topics, and each topic as a mixture of words. Using this assumption, the algorithm aims to find the top ranked words for each topic. Since document-topic distribution and topic-word distribution are treated as latent variables, we use an approximation technique to tease out the probability distributions. Some of the techniques are Gibbs Sampling and Expectation Maximization (EM). The algorithm for LDA using Gibbs Sampling is given in Algorithm \ref{lda-algorithm}.

\chapter{Literature Survey}
\section{Clustering}
% Mo
Clustering algorithms can be classified into five groups - partitioning-based, hierarchy-based, density-based, grid-based, and model-based.

\subsection{Partition-based Clustering}
In partitioning-based clustering algorithms, data objects are divided into a number of partitions initially. 
Each partition represents a cluster. 
The partitioning is optimized for a pre-specified criterion function. 
The most typical partitioning-based clustering algorithm is the \textit{k}-means algorithm. 
\textit{k}-means clustering \cite{macqueen1967some} represents data as real-valued vectors in $d$-dimensional space $R^d$. 
Initially, data points are partitioned into $K$ clusters with $K$ center points. 
Then, the algorithm will iteratively update the center points to minimize the mean squared distance from each data point to its nearest center point. The major challenge in the \textit{k}-means algorithm is to determine the number of clusters $K$. This is explored later in this report.\\
\par Based on \textit{k}-means, fuzzy clustering such as fuzzy \textit{c}-means (FCM) \cite{bezdek1984fcm} has also been proposed. 
In FCM, data points are assigned to centers of clusters with a degree of belief. 
Therefore, each data point may belong to more than one cluster with different memberships. 
FCM follows the same principle of \textit{k}-means that iteratively searches the center point and updates memberships of each data object. 
But its goal is to minimize the objective function $J$ below.

\begin{equation}
J = \sum_{i=1}^{n}\sum_{k=1}^{c}\mu_{ik}^{m}|p_i-v_k|^2
\end{equation}

Here, $n$ is the number of data points, $c$ is the number of defined clusters, $\mu_{ik}$ is the likelihood data, $i$ belongs to cluster $k$, $m$ is a fuzziness factor and $|p_i-v_k|$ is the Euclidean distance between $i$-th object $p_i$ and $k$-th cluster center $v_k$.  


\subsection{Hierarchical Clustering}
In hierarchical clustering algorithms, data points are organized in a hierarchical manner depending on the medium of proximity \cite{fahad2014survey}. 
Each data point is a leaf node in the tree-like hierarchical structure. 
Hierarchy-based algorithms can either be bottom-up or top-down. 
Bottom-up methods start with one data point for each cluster and recursively merge other clusters. 
Top-down methods start with one cluster and recursively split into multiple clusters according to a certain metric. 
The major drawback of hierarchical based methods is that merge or split steps cannot be undone. 

BIRCH \cite{zhang1996birch} is an efficient hierarchy-based clustering algorithm. It builds up a clustering feature tree (CF tree) by scanning the dataset in an incremental and dynamic way. When a data point is encountered, the CF tree is traversed from root to leaf by choosing the closest node at each level. After the closest leaf cluster is identified, a test will be performed to check whether a current data point belongs to this leaf cluster. If not, a new leaf cluster will be created. Two major advantages of BIRCH are the ability to deal with large datasets and handle noise. However, it does not have good stability and may not work well when clusters are not spherical. 

Compared to BIRCH, CURE \cite{guha1998cure} is more robust in noise handling and can identify clusters with non-spherical shapes. CURE represents each cluster by a set of well-scattered points and shrinks them towards the center of the cluster by a specific function. With more than one representative point per cluster, CURE is able to adjust well to the geometry of clusters with sophisticated shapes which suppresses the noise effect. In addition, CURE also applies a combination of random sampling and partitioning to deal with large datasets.

\subsection{Density-based Clustering}
In density-based clustering algorithms, data objects are separated based on regions of density, connectivity, and boundary. A cluster is a connected, dense component with arbitrary shape. This feature provides a natural protection against outliers to filter out noise.  Two typical density-based clustering algorithms are density-based spatial clustering of applications with noise (DBSCAN) \cite{ester1996density} and density-based clustering (DENCLUE) \cite{hinneburg1998efficient}. 

In DBSCAN, a data object is assigned to a cluster when the density in its neighborhood is high enough. Clusters are created from a data object by absorbing all objects in its neighborhood. DENCLUE models cluster distributions based on the sum of influence functions of all data objects. An influence function describes the impact of a data object in its neighborhood. DENCLUE creates clusters according to density attractors which are the local maxima of the overall density function. DENCLUE is much faster than DBSCAN because it uses tree-based access structures.

\subsection{Grid-based Clustering}
In grid-based clustering algorithms, data objects are divided into grids. Then clustering is performed on the grids instead of the large dataset directly. A major advantage of grid-based methods is speed since the size of a grid is usually much smaller than the size of the dataset. However, it is not good at handling datasets with irregular distributions. Optimal Grid (OptiGrid) \cite{hinneburg1999optimal} is a grid-based clustering algorithm which aims at achieving optimal grid partitioning. OptiGrid constructs the best cutting hyperplanes through a set of selected projections. The cutting plane is chosen to have minimal point density. After grid construction, clusters can be found using a density function. Then, the algorithm is applied recursively on the clusters to achieve better clustering.

\subsection{Model-based Clustering}
Model-based clustering algorithms are designed to optimize the fit between a given dataset and a certain mathematical model. There are two types of model-based methods, statistical and neural network methods. 
Statistical methods use probability measures to determine clusters, while neural network methods utilize a set of weighted connections between input/output units to derive clusters. 
One example of statistical methods is the Expectation-Maximization (EM) algorithm \cite{dempster1977maximum}. 
As the name indicates, EM iteratively has two steps. 
In the expectation step, data objects are fractionally assigned to each cluster according to the posterior distribution of latent variables which is derived using current model parameters. In the maximization step, the fractional assignment is given by re-estimating model parameters with the maximum likelihood rule. However, the EM algorithm has a lot of mathematical requirements and it has a slow convergence rate. 

\section{Topic Analysis}

Topic modeling is used to represent a set of documents/text corpora by a distribution of hidden topics. Topics refer to unobserved data that are discovered using observed data - the words present in the documents. 
Thus, a distribution of related words makes up a topic. 
Topics help preserve the essential relationship amongst words in a document, thereby reducing the dimensionality of the documents to a bunch of topics.

\subsection{TF-IDF}
Different methodologies have been used in order to retrieve data from text corpora. The term frequency-inverse document frequency (tf-idf) method calculates the frequency of a word/term (tf) in a corpus and multiplies it by the inverse document frequency (idf) value to return a term-by-document matrix.

\subsection{Latent Semantic Indexing}
The Latent Semantic Indexing (LSI) method was later proposed to replace the \textit{tf-idf} matrix by a singular value decomposition (SVD). Following this, the probabilistic Latent Semantic Indexing (pLSI) model was proposed by Hoffman \cite{hofmann1999probabilistic}. It models a document as a mixture of topics based on the likelihood principle. There is no generative process for determining the document-topic distribution, which leads to problems while assigning probabilities to documents outside the training set. 

\subsection{Latent Dirichlet Allocation}
Latent Dirichlet allocation (LDA) \cite{blei2002latent} is an unsupervised machine learning technique, which assumes a hierarchical Bayesian dependency between the documents, topics, and words for topic modeling. It was first presented by David Blei, Andrew Ng, and Michael I. Jordan as a generative probabilistic model for collections of discrete data such as text corpora. It overcomes the limitations of the pLSI method.  Given a collection of documents, LDA assigns a distribution of words to every topic and also a distribution of topics to every document.

\begin{figure}[H]
\centering
\includegraphics[width=0.5\textwidth]{lda_plate_notation.png}
\caption{Plate notation for LDA (courtesy Wikipedia)}
\label{fig:lda-plate-notation}
\end{figure}

As explained in \cite{blei2002latent}, LDA assumes the following generative process:
\begin{itemize}
\item For each topic $k \in K$, draw topic distribution $\phi_k {\sim} Dirichlet (\beta)$
\item For each document $m$,
\begin{itemize}
\item Draw topic distribution $\theta {\sim} Dirichlet(\alpha)$
\item For each word $n$ in document $m$,
\begin{itemize}
\item Draw topic $z_{m,n} {\sim} Multinomial (\theta_m)$
\item Draw word $w_{m,n} {\sim} Multinomial (\phi_{z_{m,n}})$
\end{itemize}
\end{itemize}
\end{itemize}

The model is equivalently explained through a plate notation diagram (Figure \ref{fig:lda-plate-notation}). There are $M$ documents in the corpus. For simplicity, the diagram assumes $N$ words in each document. Each word $w$ has a topic $z$, which is generated from the document-topic distribution $\theta$. $\alpha$ and $\beta$ are the hyperparameters to the model (also known as Dirichlet priors).

\subsection{Twitter-LDA}
Twitter-LDA \cite{zhao2011empirical} is a variant of the standard LDA model which was developed for the purpose of modeling tweets. This model assumes that a tweet contains a single topic given the constraint on its length (140, expanded to 280, characters), and models background and topic-related words separately, to give a more realistic modeling of Twitter text. 
Topic modeling on tweets has also been studied in \cite{ahuja2016microblog} and \cite{mehrotra2013improving}.

\begin{figure}[H]
\centering
\includegraphics[width=0.5\textwidth]{twitter-lda.png}
\caption{Plate notation for Twitter-LDA \cite{zhao2011empirical}}
\label{fig:twitter-lda-plate-notation}
\end{figure}

The generative process for Twitter-LDA is as follows:
\begin{itemize}
\item Draw word-category distribution $\pi {\sim} Bernoulli(\gamma)$
\item Draw background words distribution $\phi^B {\sim} Dirichlet (\beta)$
\item For each topic $k$, draw topic-word distribution $\phi^{'}_k {\sim} Dirichlet (\beta)$
\item For each user $u$, 
\begin{itemize}
\item Draw topic distribution $\theta_u {\sim} Dirichlet(\alpha)$
\item For each document $m_{u, t}$ by user $u$,
\begin{itemize}
\item Draw topic $z_{u, t} {\sim} Multinomial (\theta_u)$
\item For each word $w_{u, t, n}$
\begin{itemize}
\item Draw category $y_{u,t,n} {\sim} Binomial(\pi)$
\item Draw word $w_{u, t, n} {\sim} Multinomial(\phi^{'}_{z_{u,t}})$, if $y_{u,t,n} = 1$
\\ else $w_{u, t, n} {\sim} Multinomial(\phi^{B}$, if $y_{u,t,n} = 0)$
\end{itemize}
\end{itemize}
\end{itemize}
\end{itemize}

This model is equivalently explained by Figure \ref{fig:twitter-lda-plate-notation}. 
Each user $u$ has a topic-distribution $\theta_u$. 
Since every tweet is only 140 (expanded to 280) characters, there is only one topic $z$ for a tweet $t$. Each word in the tweet is drawn from a multinomial distribution.

\chapter{Requirements Gathering}
The system is aimed to support a helpful search experience for the users. 
Our team works on analyzing the topics from the clean text of tweets and webpages that have been already classified by CLA on the basis of different events. 
Since CMT and CMW already convert the text to lowercase, tokenize it, and remove stop words, we take in preprocessed text for our unsupervised learning algorithms. The text in these fields is \texttt{UTF-8} encoded. The tokenization technique, using NLTK \cite{nltk_tokenizer}, ``tokenizes a string to split off punctuation other than periods''.

The most relevant fields in the HBase schema for CTA are \texttt{clean-webpage:clean-tokens} and \texttt{clean-tweet\-:clean\-tokens}. To use custom tokenizing, one can also directly use \texttt{clean-webpage:\-clean-text-cta} and \texttt{clean-tweet:clean-text-cta}.

We find that the preprocessed text for webpages is less noisy and that the default NLTK implementation might work.
However, for tweets a more custom implementation such as NLTK's \texttt{TweetTokenizer} \cite{nltk:tweettokenizer} or a similar implementation called \texttt{tweetokenizer} \cite{jaredks_2013} might work better.

\section{Clustering}
For clustering, the tokenized text is converted to a bag-of-words model where we ignore the order of occurrence of words in a document. Each document is represented as a high-dimensional vector. 
We run the \textit{k}-means algorithm on this with different number of clusters $K$. 
To determine the best model (i.e., the best number of clusters), we plot the Calinski-Harabasz index for each model. The plot resembles an elbow plot and the best number of clusters is determined by the point at which the Calinski-Harabasz index drops off steeply. 
This is discussed in more detail in the evaluation section. 
The keywords for each cluster are the most frequently used \textit{n} words.

\section{Topic Analysis}
For topic modeling, the tokenized text is merely mapped to a high-dimensional vector space where each of the terms is encoded as a number. We run LDA on this vector space to determine the document-topic distribution and topic-word distribution. Using these two distributions, we find the keywords for each of the documents in the corpus. The quality of our results is evaluated using two quantitative measures -- perplexity and topic coherence.  
We favor models with low perplexity and high topic coherence. 
The two measures are described in the evaluation section. 
We also plan to do a qualitative study, where students in the class will be asked to determine if a set of words is coherent or not.
% * <fox@vt.edu> 2017-12-18T01:08:23.521Z:
% 
% > We also plan to do a qualitative study, where students in the class will be asked to determine if a set of words is coherent or not.
% Was this done? Why or why not? Did you figure out details of how it would work? Can it be done by another group, such as in the spring CS4624 class? Are there instructions for such?
% 
% ^.

\section{Outputs}
The results of the CTA team are the most probable clusters and topics for each document and a set of words representing a topic or a cluster. The topic analysis team maps the list of topics along with their probabilities to \texttt{topic:topic-list} and \texttt{topic:probability-list}, respectively. The clustering team populates the fields \texttt{cluster:cluster-list} and \texttt{cluster-probability}. To help the FE team, we also populate two fields -- \texttt{topic:topic-displaynames} and \texttt{cluster:cluster\-displaynames}. These correspond to the highest probability topic and cluster, respectively.

\chapter{Design and Deliverables }

\section{System Design}

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{pipeline.PNG}
\caption{Pipeline for text processing. The CTA team now begins the preprocessing pipeline at \textit{Step 3: Remove stop words and punctuation} as the text is already tokenized and lowercased.}
\label{fig1:pipeline}
\end{figure}
The CTA team uses tokenized text provided by the CMT and CMW teams, respectively. 
The incoming documents undergo pre-processing to normalize and filter out the redundant information. In general, each document is converted to lowercase and tokenized into blocks of text based on word boundaries (each called a token). 
A token is nothing but a sequence of characters which acts as a useful semantic entity for processing. 
For example : ``Harvey was a catastrophic flood disaster in southeast Texas'' will be split into \texttt{harvey}, \texttt{was}, \texttt{a}, \texttt{catastrophic}, \texttt{flood}, \texttt{disaster}, \texttt{in}, \texttt{southeast}, and \texttt{texas}. CMT and CMW have already uploaded, tokenized, and lowercased text to HBase, thereby, eliminating the first two steps in our pipeline.

The CTA team begins at Step 3, which involves removing stop words such as \texttt{the}, \texttt{is}, \texttt{a}, etc. They offer no analytic value to the text mining process. Punctuation marks are another component that has little or no importance to topic analysis and can be safely eliminated without any loss of information. For example: ``It's hard to believe, but it has already been a month since Hurricane Harvey made landfall in Texas.'' $\Rightarrow$ \textbf{\texttt{it}}, \textbf{\texttt{'s}}, \texttt{hard}, \textbf{\texttt{to}}, \texttt{believe}, \textbf{\texttt{,}}, \textbf{\texttt{but}}, \textbf{\texttt{it}}, \textbf{\texttt{has}}, \texttt{already}, \textbf{\texttt{been}}, \textbf{\texttt{a}}, \texttt{month}, \textbf{\texttt{since}}, \texttt{hurricane}, \texttt{harvey}, \texttt{made}, \texttt{landfall}, \textbf{\texttt{in}}, \texttt{texas}.

The emphasized strings are stop words and punctuation, which can be eliminated. In this example, we removed 55\% of the tokens which otherwise would have an impact on the overall runtime of the topic analysis system. Several documents in social media now contain hashtags (\#hashtag). These should not be removed as they offer key insights into the themes in the document. URLs can also be safely removed from documents for clustering and topic analysis. 
As a rule of thumb, we also eliminate all tokens with length less than  3. 

An optional step in the pipeline is stemming or lemmatization. 
Stemming reduces words to a base form using a simple algorithm. For example, ``forest'', ``forests'', and ``forested'' all contribute to a single word: ``forest''. 
This helps reduce the dimensionality of the vector space and eliminates words that just differ in tense or plurality.

Lemmatization is another technique to reduce words, to their root forms. Stemming employs a rule based system, whereas lemmatization takes into account the part-of-speech tag and linguistic analysis to normalize words. 
For example, ``am'', ``are'', and ``is'' will be lemmatized to ``be''.

Stemming or lemmatization can be helpful for webpages, however these techniques are not suitable for tweets. Tweets often ignore normal grammar rules, and may not comprise dictionary words. This makes stemming and lemmatization troublesome. Currently, we do not perform any stemming or lemmatization on any of the data.

The preprocessing step is trivially parallelizable for both webpages and tweets to increase the performance of our design.

\section{Technologies Used}
The topic modeling system uses Python extensively. Broadly, it has three main responsibilities:

\begin{enumerate}
\item \textbf{Database Access:} We use the Python library \texttt{happybase} to retrieve data from and put data into HBase. However, \texttt{happybase} is prone to failure when querying more than one million records. To overcome this difficulty, we use a shell (.sh) script when pulling data with over a million records. We also batch our queries whenever possible to reduce the load on the database server using \texttt{happybase}'s in-built \texttt{batch} method.
% * <fox@vt.edu> 2017-12-18T01:20:54.977Z:
% 
% > to
% Add cite
% 
% ^.
\item \textbf{Preprocessing and LDA:} Preprocessing generally includes removal of stop words and punctuation. We augment the stop word list using collection specific stop words. We achieve this using \texttt{nltk} and a custom preprocessing pipeline. The Python library \texttt{gensim} performs the heavy-lifting code of topic modeling. Since we do this on a single node of the cluster, we parallelize the algorithm by using all 20 cores of the node. This is done using the \texttt{LdaMulticore} class of \texttt{gensim}.
% * <fox@vt.edu> 2017-12-18T01:26:01.696Z:
% 
% > using collection specific stop words
% Be sure to identify what lists were used for which analyses. Explain in enough detail so this would be reproducible by others, and so others would know what to do with a new collection.
% 
% ^.
\item \textbf{Visualization:} \texttt{pyLDAvis} is a bring-your-own-topic-model package for visualizing inter-topic distances and the most relevant words for a topic. We incorporate this library to understand and evaluate the coherence of our topic models.
% * <fox@vt.edu> 2017-12-18T01:31:54.789Z:
% 
% > .
% Where is Fig. 7.2 cited?
% If obtained from another source, be sure to add a cite to that in the figure caption.
% 
% ^.
\end{enumerate}

\begin{figure}[H]
\includegraphics[width=\textwidth]{techstack-lda}
\caption{Latent Dirichlet Allocation uses a Python based system with three main capabilities -- access to HBase, preprocessing and LDA, and visualization.}
\label{techstack-lda}
\end{figure}

Alternate systems can be built using Scala, Spark, and MLLib (as used by the Fall 2016 team). However, we found Scala lacking in the rich preprocessing and visualization aspects that Python-based libraries excelled in. Additionally, we did not face scaling problems as \texttt{gensim} is written using \texttt{numpy} and \texttt{scipy}, both of which are wrappers for C libraries. This makes \texttt{gensim} adequately fast for large collections of data.
% * <fox@vt.edu> 2017-12-18T01:27:47.644Z:
%
% > Fall 2016 team
%
% ^.

We also used \texttt{PySpark} to create topic models. 
However, the \texttt{LDAModel} implementation of \texttt{PySpark} is incomplete and does not have methods for labeling documents by topics and evaluation. 
Therefore, we did not proceed with this approach.

Same technologies are used for database access and preprocessing in clustering as well. 
\textbf{Scala} and \textbf{Spark} are used for clustering the data into clusters. \textbf{matplotlib} and \textbf{Python} scripts are used for further evaluating and plotting the results.

\section{Timeline}

The major tasks for our team are highlighted in the table below. It is broadly divided into three phases -- Literature Survey, Baseline implementation and Scaling, and Experiments (Runs) and Evaluation.



\begin{longtable}{|p{3cm}p{6cm}p{3cm}p{2.5cm}|}
    \hline
    \textbf{Date} & \textbf{Task List} & \textbf{Team Member} & \textbf{Status} \\ \hline
    \multicolumn{4}{|l|}{Literature Survey} \\ \hline
    Sep 19, 2017  & Literature survey & Entire team & \textbf{Done} \\
    Sep 26, 2017  & Interim Report 1 & Entire team & \textbf{Done} \\ \hline
    \multicolumn{4}{|l|}{Baseline Implementation and Scaling} \\ \hline
    Oct 03, 2017  & Implement baseline LDA & Ashish B, Aman & \textbf{Done} \\
    Oct 05, 2017  & Data preprocessing for clustering & Mo, Prathyush & \textbf{Done} \\
    Oct 08, 2017  & Generate bag of words for tweet collection & Pavan, Ram & \textbf{Done} \\
    Oct 10, 2017  & Implement baseline Twitter-LDA & Ashish B, Aman & \textbf{Done} \\
    Oct 12, 2017  & Implement \textit{k}-means clustering & Pavan, Ram & \textbf{Done} \\
    Oct 13, 2017  & Evaluate LDA and Twitter-LDA on ``election'' data & Ashish B & \textbf{Done} \\
    Oct 15, 2017  & Intrepretation of results and visualization & Mo, Prathyush & \textbf{Done} \\
    Oct 15, 2017  & Find best number of clusters qualitatively & Ashish B, Shruti & \textbf{Done} \\
    Oct 18, 2017  & Interim Report 2 & Entire team & \textbf{Done}\\
    Oct 19, 2017  & Implement hierachial clustering & Pavan, Ram & \textbf{Done} \\
    Oct 21, 2017  & Implement quantitative measures: perplexity and topic coherence & Ashish B & \textbf{Done} \\
    Oct 21, 2017  & Performance comparison and selection of final value of K & Mo, Prathyush &  \textbf{Done} \\
    Oct 24, 2017  & Compare LDA with Twitter-LDA for results & Ashish B, Aman & \textbf{Done} \\
    Oct 31, 2017  & Package as single script to run LDA experiments and evaluations & Ashish B & \textbf{Done} \\ \hline
    \multicolumn{4}{|l|}{Experiments and Evaluation} \\ \hline
    Nov 04, 2017  & Run LDA on CMW collections - ``Solar Eclipse 2017'', ``Hurricane Irma'', ``Las Vegas Shooting'' & Ashish B & \textbf{Done} \\
    Nov 6, 2017  & Run clustering algorithm on CMW collections & Mo, Prathyush & \textbf{Done} \\
    Nov 08, 2017  & Interim Report 3 & Entire Team & \textbf{Done} \\
    Nov 14, 2017  & Integration with HBase to pull and write data seamlessly    & Shruti, Ashish M, Mo, Prathyush & \textbf{Done} \\
    Nov 21, 2017  & Thanksgiving break & & \\
    Nov 27, 2017  & Collate results between clustering and topic modeling & Ashish B, Pavan, Ram & \textbf{Done} \\
    Nov 30, 2017  & Qualitative evaluation of topics and clusters & Entire team & \textbf{Done} \\
    Dec 07, 2017  & Final Presentation & Entire team & \textbf{Done} \\
    Dec 12, 2017  & Final Report & Entire team & \textbf{Done} \\ 
    \hline
    \caption{Timeline of task list}
    \label{timeline-task-list}
\end{longtable}

\chapter{Implementation and Evaluation Techniques}
\section{Preprocessing}
Each document is preprocessed before being fed into the clustering and topic analysis algorithms. The pseudocode for our approach is described in Algorithm \ref{preprocessing-algorithm}.

\begin{algorithm}[H]
\caption{Preprocessing Algorithm}
\label{preprocessing-algorithm}
\begin{algorithmic}[1]
\Procedure{Preprocess}{$document$, $tokenizer$, $mappers$, $filters$}
\State $tokens \gets tokenize(document)$
\ForEach{mapper in mappers}
\State $tokens \gets map($$mapper.map$, $tokens)$
\EndFor
\ForEach{filter in filters}
\State $tokens \gets filter($$filters.filter$, $tokens)$
\EndFor
\State \textbf{return} \bm{$tokens$}
\EndProcedure
\end{algorithmic}
\end{algorithm}

We use Python's functional programming helper functions \texttt{map} and \texttt{filter} to make our interface simple. Examples of $mappers$ include \texttt{LowerCaseMapper}, which converts all tokens to lowercase, \texttt{WordNetLemmatizer}, which lemmatizes each token using Wordnet, and \texttt{PorterStemmer}, which stems words using Porter's algorithm.

\begin{figure}
\includegraphics[width=\textwidth]{preprocessing}
\caption{The three stages of our preprocessing pipeline -- tokenization, mapping, and filtering.}
\end{figure}

Examples of $filters$ include \texttt{StopWordFilter}, which removes stop words and \texttt{PunctuationFilter} which removes all punctuation from the tokens.

One of the most important aspects of preprocessing is  maintaining a list of words that are stop-words for a particular collection. 
For instance, webpages about Solar Eclipse 2017 mention words such as \texttt{solar}, \texttt{eclipse}, \texttt{tse}, etc. These words do not add any meaning to topic modeling or clustering results as they are present in almost all documents. We develop these lists for each collection based on multiple runs and experiments. A sample of these words is shown in Table \ref{table:collection-specific-stop-words}.
% * <fox@vt.edu> 2017-12-18T01:44:44.276Z:
% 
% > sample
% Be sure somewhere to give the name of the file used in each of the experiments.
% 
% ^.

\begin{table}
\centering
\begin{tabular}{c|c}
Solar Eclipse 2017 & Hurricane Irma \\ \hline
solar & hurricane \\
eclipse & irma \\
totality & national \\
tse & global \\
eclipse2017 & us \\
eclipses & sept \\
subnav & september \\
aug & csbn \\
august & reuters \\
account & florida \\
facebook & business \\
twitter & insider \\
published & guardian \\
username & subscribe \\
password & bloomberg \\
\end{tabular}
\caption{A sample of collection specific stop words for Solar Eclipse 2017 and Hurricane Irma}
\label{table:collection-specific-stop-words}
\end{table}

\section{Clustering}
\subsection{Implementation Details}

The implementation of the clustering algorithm is shown in Algorithm \ref{k-means}. 
The first step is to represent each document as a bag of words, which results in a corpus. 
The second step is to determine the number of clusters $K$ with the elbow method using the Calinski-Harabaz Index as a metric. 
A higher Calinski-Harabaz score relates to a model with better defined clusters. For $K$ clusters, the Calinski-Harabaz score $s$ is given as the ratio of the between-clusters dispersion mean and the within-cluster dispersion:
$$
s(k) = \frac{Tr(B_k)}{Tr(W_k)}\times\frac{(N-k)}{k-1} 
$$
$$
W_k = \sum_{q=1}^{k} \sum_{x\in C_q} (x-C_q)(x-C_q)^T
$$
$$
B_k = \sum_{q} n_q(c_q-c)(c_q-c)^T
$$
Here $N$ is the number of points in our data, $C_q$ is the set of points in cluster $q$, $c_q$ is the center of cluster $q$, $c$ is the center of $E$, and $n_q$ be the number of points in cluster $q$.

We run the \textit{k}-means and hierarchical clustering algorithm with an input of the corpus, iterations, and $K$ value (the number of clusters). The iteration is the maximum number of iterations before terminating the algorithm.

Note that as well as commonly known \textit{k}-means, we also implement Hierarchical Clustering. 
In Hierarchical Clustering, we do a divisive method where we split each cluster into sub-clusters in subsequent steps. 
Depending on the threshold we decide, we get a certain number of clusters. 
We can lower the threshold to get more clusters. Currently for hierarchical clustering, we set the threshold so that we have only four clusters generated. 
Further, we have to decide on the number of clusters at which to stop the divisive process.

\begin{algorithm}[H]
\caption{Run Clustering Algorithm}
\label{k-means}
\begin{algorithmic}[1]
\Procedure{RunCluster}{$documents$, $iterations$}
\State $corpus \gets return \; bag \; of \; words \; for \; each \; document$
\State \Comment{Convert all documents into their bag of words representation}
\State $K \gets Elbow(documents)$
\State $clusters\_kmean \gets KMeans(corpus, iterations, K)$
\State $clusters\_hier \gets Hierarchical(corpus, iterations)$
\State \textbf{return} \bm{$clusters\_kmeans, clusters\_hier$}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\textbf{Frequent Word Analysis: }
k-means just returns the clusters, but does not name them. We can name each cluster by looking at a handful of documents in the it, which can be tedious in a Big Data scenario. 
Therefore,
 (i) we determine the most frequent words in all documents within a cluster, and (ii) name the cluster based on a few very frequent words in the cluster. 
 Here, we use the assumption that "the frequent words in the cluster describe the information in the documents within  the cluster". The algorithm \ref{frequentwords} describes the first step, i.e., finding frequent words in each cluster. 
 Once we obtain the frequent words in a cluster, we use them to manually label the cluster with a suitable name related to these words. 
 
\begin{algorithm}[H]
\caption{Run Freqeunt Words Analysis Algorithm \\ Input: documents belonging to a single cluster, and a threshold value on the minimum frequency required for a word to be defined as "frequent" \\ Output: frequent words with frequency higher than the threshold}
\label{frequentwords}
\begin{algorithmic}[1]
\Procedure{FrequentWords}{$documents$, $threshold$}
\State $frequent\_words = \emptyset$
\State \Comment frequent\_words is a set of frequent words
\State $frequency\_map = \emptyset$ 
\State \Comment The frequency map has a key as a word and the value as its frequency in the cluster
\ForEach{document in documents}
	\ForEach{word in document}
    	\If{word in $frequency\_map$}
        	\State $increase \; word's \; frequency \; by \; 1 \; in \; frequency\_map$
        \Else
        	\State $add \; <word, 1> \; to \; frequency\_map$
        \EndIf
     \EndFor
\EndFor
\ForEach{word in frequency\_map}
	\If{$frequency\_map[word] \geq threshold$}
    	\State $add \; word \; to \; frequent\_words$
    \EndIf
\EndFor
\State \textbf{return} \bm{$frequent\_words$}
\EndProcedure
\end{algorithmic}
\end{algorithm}


\subsection{Evaluation}
\subsubsection*{Silhouette}
This is one of the methods to validate or understand the clustering obtained. 
In case of \textit{k}-means, we have $K$ clusters $C_1, C_2, ..., C_k$. 
Let $d_i$ be a document in cluster $C_i$, and let $a(d_i)$ represent the average dissimilarity of $d_i$ with all other documents in the same cluster. 
We also compute the average dissimilarity of $d_i$ to all documents in any cluster $C_j, i \neq j$. Let $b(d_i)$ represent the lowest of all these average dissimilarities. The silhouette of $d_i$ is \\
\begin{equation}
	s(d_i) = \frac{b(d_i)- a(d_i)}{max(b(d_i), a(d_j))}
\end{equation}
$s(d_i)$ has the range -1 to +1. If $s(d_i)$ is close to 1, then the document is said to be correctly clustered, whereas if $s(d_i)$ is close to -1, then the document is wrongly clustered. This could be easily seen from the definitions of $a(d_i)$ and $b(d_i)$.
\subsubsection*{Elbow}
This is used mainly in conjunction with the \textit{k}-means clustering to help in determining the optimal number of clusters. The method plots the sum of squared errors on the Y-axis and the number of clusters on the X-axis. The elbow of this plot points to the optimal number of clusters.


\section{Topic Analysis}
\subsection{Implementation Details}

\begin{algorithm}[H]
\caption{Building Vocabulary}
\label{vocabulary-algorithm}
\begin{algorithmic}[1]
\Procedure{BuildVocabulary}{$document$}
\State $id2word \gets dictionary()$
\State $word2id \gets dictionary()$
\State $counter \gets 0$
\ForEach{document in documents}
    \State $tokens \gets preprocess(document)$
    \ForEach{token in tokens}
        \If{token not in word2id}
            \State $id2word[counter] \gets token$
            \State $word2id[token] \gets counter$
            \State $counter \gets counter + 1$
        \EndIf
    \EndFor
\EndFor
\State \textbf{return} \bm{$(id2word, word2id)$}
\EndProcedure
\end{algorithmic}
\end{algorithm}

We use Python 2.7 as our language of choice for topic modeling. We use the package \texttt{gensim} to train all our topic models. We use the module \texttt{LdaMulticore} in \texttt{gensim} to use support of multicores to distribute our workload. We follow the Gibbs sampling derivations in \cite{ahuja2015topic} to understand and implement Gibbs sampling in LDA and Twitter-LDA.

The input to \texttt{LdaMulticore} is a stream of vectors or vector-space representations of each document. Since we want to scale our method as the number of documents, we opt to operate from disk rather than main memory. This helps us avoid loading all documents in memory and therefore scales easily.

The \texttt{BuildVocabulary} method helps us create a vector representation of each of the documents. 
It ensures that all terms get a unique ID.

\begin{algorithm}[H]
\caption{Run LDA using Gensim}
\label{gensim-lda}
\begin{algorithmic}[1]
\Procedure{RunLDA}{$documents$, $vocabulary$, $iterations$, $topics$, $hyperparameters$}
\State $corpus \gets doc2id(documents)$
\State \Comment{Convert all documents into their vector representation} 
\State $model \gets LdaMulticore(corpus, vocabulary, topics, iterations, hyperparamters)$
\State \textbf{return} \bm{$model$}
\EndProcedure
\end{algorithmic}
\end{algorithm}

The \texttt{RunLDA} method creates the topic model. Once trained, the model has details for the document-topic distribution and topic-word distribution.

For each topic, we extract the top 30 keywords and give them human-readable names. Subsequently, for each document, we extract the top 3 topics and their corresponding probabilities. These are put in HBase as probable \textit{facets} for a document. 
We also extract the most probable topic and populate that in \texttt{topic:topic-displaynames}. For quantitative evaluation, we calculate perplexity and topic coherence, which are described in the next section.

\subsection{Evaluation}
\subsubsection*{Quantitative}
One of the main evaluation techniques for topic modeling is perplexity. Informally, perplexity measures the cross entropy between the empirical distribution and the predicted distribution. Perplexity of a model for a test set of M documents is given by:

\[Perp(D_{test}) = \exp \Big\{ \frac{-\sum_{d=1}^{M} \log p(w_{d})}{\sum_{d=1}^{M}{N_d}} \Big\} \]

where $N_{d}$ is the number of words in the document and $p(w_d)$ is the probability of the word in the document.

According to the definition, a lower perplexity score indicates a better model.

\subsubsection*{Qualitative}
Evaluation of topic models quantitatively is fraught with several challenges. Often, human evaluation is necessary to determine the coherence of a topic. The authors in \cite{boydgraber2009} use a word intrusion task to detect the \textit{odd-one-out} of a set of words for a topic. If they are consistently able to find the out of place word, the topics are coherent. While we had initially planned to crowd-source our annotations from the class, we did not find enough time to complete this.

\chapter{Results}
Our experiments are performed on both the tweet and webpage data as shown in Table \ref{Table:Dataset}. 
% * <fox@vt.edu> 2017-12-18T01:58:53.674Z:
% 
% > Table
% When a column in a table has numbers of varying lengths, it is better to right justify the numbers.
% 
% ^.
For example, 56,376 tweets were collected through a keyword search for ``remember April 16''. 721 webpages and 2,667,720 webpages were collected using the keyword ``solar eclipse 2017''. 2741 and 913 webpages were collected for "Hurricane Irma" and "Vegas Shooting". A sample of the tweets is shown in Figure \ref{fig:tweet}.

\begin{table}[H]
\centering
\caption{Datasets description with category (tweet or document) and number of documents}
\label{Table:Dataset}
\begin{tabular}{|l|l|l|}
\hline
\textbf{Dataset Name} & \textbf{Type} & \textbf{No. of documents} \\ \hline
Remember April 16     & tweet         & 56376                     \\ \hline
Solar Eclipse 2017        & webpage       & 721                       \\ \hline
Solar Eclipse 2017        & tweet       & 2667720                       \\ \hline
Hurricane Irma        & webpage       & 2741                       \\ \hline
Vegas Shooting        & webpage       & 913                       \\ \hline
\end{tabular}
\end{table}

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{tweet}
\caption{Clean Tweet Data Sample}
\label{fig:tweet}
\end{figure}

\section{Remember April 16 Tweets}
\subsection{Clustering}
We use the Calinski Harabaz Index as the metric and apply the elbow method to find the optimal value of K in \textit{k}-means clustering. 
As illustrated in Figure \ref{fig:elbow} the Calinski Harabaz Index does not drop much after $K=4$. Therefore, the point $K=4$ indicates the optimal $K$ value.

\begin{figure}[H]
\centering
\includegraphics[width=0.8\textwidth]{selection_k}
\caption{Calinski Harabaz index vs. number of clusters for ``remember april 16'' Dataset}
\label{fig:elbow}
\end{figure}

However, after performing the experiments using various datasets we observed that the cluster distribution is skewed with one cluster representing the majority of data which are not correlated.
To reduce this, we can increase the the value of the number of clusters as per the datasets.
For the experiments conducted we generally used a value of K= 5 or 6.
If the results interpreted are not comprehensible we can also conduct an iterative clustering on the large cluster to derive more meaningful results.

A sample of the \textit{k}-means clustering result is in Figure \ref{fig:kmeans_result}. 
The number highlighted by a blue box is tweet ID while the number highlighted by a brown box is cluster index. 
For example, tweet 588503698176757762 belongs to cluster 0. Figure \ref{fig:kmeans_pie} presents the tweet distribution among different clusters. 
For experiments with webpage data, as will be shown later, we also apply cosine similarity analysis which calculates the similarity of intra- and inter-cluster documents to evaluate clustering results. 
However, we didn't perform cosine similarity analysis for tweet data because of the large data size and the exponential analysis time.
% * <fox@vt.edu> 2017-12-18T02:03:36.752Z:
% 
% > exponential
% Are you sure this is the complexity?
% 
% ^.

To understand the meaning of each cluster, we find the most frequently used words in the tweets belonging to each cluster. Using the frequent words we obtain the real world event or news that is frequently discussed in the set of tweets in the cluster. The frequent words and the corresponding event / news of each cluster are shown in Table \ref{kmeans_table}. 
For example, the frequent words in Cluster 0 are: \texttt{Remember}, \texttt{Sewol}, \texttt{door}, \texttt{missing}, and \texttt{April}. 
When we use these keywords to search in the Internet, we understand that these tweets are remembering the victims and sufferers of the \textit{Sewol Ferry Disaster} that happened on April 16, 2014. 
While Cluster 0 is fairly coherent, Cluster 3 lacks clarity. 
It is not always easy to ascertain the real word event from frequently used words in the cluster.

\begin{figure}[H]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=.6\textwidth]{kmeans_result}
  \caption{Sample of \textit{k}-means clustering output}
  \label{fig:kmeans_result}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=\textwidth]{kmeans_pie}
  \caption{Tweet distribution over clusters}
  \label{fig:kmeans_pie}
\end{subfigure}
\caption{\textit{k}-means clustering results on ``remember April 16'' tweets.}
%\label{fig:test}
\end{figure}


\begin{table}[H]
\centering
\caption{Frequent words and events in each cluster for ``Remember April 16'' dataset}
\label{kmeans_table}
\resizebox{\textwidth}{!}{\begin{tabular}{|l|l|}
\hline
\multicolumn{2}{|c|}{\textbf{Cluster 0}}                                                                                           \\ \hline
\textbf{Frequent words} & April, 162014, Remember, \#Sewol, door, missing                                                          \\ \hline
\textbf{Event}          & Tweets remembering the Sinking of MV Sewol ferry on April 16, 2014                                   \\ \hline
\multicolumn{2}{|c|}{\textbf{Cluster 1}}                                                                                           \\ \hline
\textbf{Frequent words} & March, Selena, RIPSelena, Quintanilla                                                                    \\ \hline
\textbf{Event}          & Remembering the American singer Selena Quintanilla who died on March 31, 1995.                           \\ \hline
\multicolumn{2}{|c|}{\textbf{Cluster 2}}                                                                                           \\ \hline
\textbf{Frequent words} & Remember, 2007, April 16, Virginia, Students, Faculty, VT                                                \\ \hline
\textbf{Event}          & Remembering the victims and the suffering of the Virginia Tech Shooting that took place on April 16 2007 \\ \hline
\multicolumn{2}{|c|}{\textbf{Cluster 3}}                                                                                           \\ \hline
\textbf{Frequent words} & Remember, Jongin, pray, hyung-ksoo                                                                       \\ \hline
\textbf{Event}          & Too few tweets belonging to this cluster to infer exact event!                            \\ \hline
\multicolumn{2}{|c|}{\textbf{Cluster 4}}                                                                                           \\ \hline
\textbf{Frequent words} & world, voice, opportunity, elections                                                                       \\ \hline
\textbf{Event}          & Tweets celebrating WorldVoiceDay and some tweets belonging to Scottish elections.                            \\ \hline
\end{tabular}}
\end{table}



We perform Hierarchical Clustering on the same data. We note that for the same number of clusters, this gives a slightly different distribution of clusters as shown in Figure \ref{fig:hier_pie}. 
However, since the distribution of the clusters is almost similar in both types of clustering, we excluded hierarchical clustering from future experiments.
% * <fox@vt.edu> 2017-12-18T02:07:51.649Z:
% 
% > the distribution of the clusters is almost similar in both types of clustering
% Is there something like Table 6.2 for the hierarchical clustering that shows similar results? Using a pie chart to make a conclusion is not a very convincing argument.
% 
% ^.

\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth]{hier_pie}
\caption{Tweets distribution over clusters using hierarchical clustering algorithm.}
\label{fig:hier_pie}
\end{figure}

\subsection{Topic Analysis}
\subsubsection{LDA}
\begin{table}[htb]
\centering
\label{lda-topics-1}
\begin{tabular}{|p{3cm}|p{3cm}|p{3cm}|}
\hline
\textbf{Topic 1} & \textbf{Topic 2} & \textbf{Topic 3} \\ \hline
votes            & @louisemensch    & world            \\
monday           & schizophrenia    & opportunity      \\
elections        & laughing         & 16               \\
scottish         & trolled          & communicate       \\
council          & ruin             & \#worldvoiceday  \\ \hline
\end{tabular}

\begin{tabular}{|p{3cm}|p{3cm}|p{3cm}|}
\hline
\textbf{Topic 4} & \textbf{Topic 5} & \textbf{Topic 6} \\ \hline
sewol            & selena           & years            \\
thousands        & quintanilla-p    & never            \\
ferry            & erez             & tech             \\
stampede         & love             & students         \\
family           & la               & faculty          \\
people           & always           & \#neverforget    \\
died             & great            & virginia         \\ \hline
\end{tabular}
\caption{Top words for topics obtained through running LDA on the ``Remember April 16'' dataset. The results show only the best 6 topics. The remaining 4 topics were incoherent.}
\label{table:lda-topic-remember-april}
\end{table}

Running the LDA algorithm on the same dataset yielded slightly different results than clustering. We trained the model with $K=10$, $\alpha=0.1$, $\beta=0.01$, $iterations=500$. We obtained a list of top-30 words used for each topic and tried labelling them manually. The results are shown in Table \ref{table:lda-topic-remember-april}.
% * <fox@vt.edu> 2017-12-18T02:09:28.165Z:
% 
% > Running
% Where are times for the runs made?
% 
% ^.

\textbf{Topic 1}: \\
Words like \texttt{votes}, \texttt{monday}, \texttt{elections}, \texttt{scottish}, \texttt{council}, \texttt{registered}, etc. are closely associated with the theme ``Scottish Elections''. 

\textbf{Topic 2}: \\
\texttt{@louisemensch}, \texttt{schizophrenia}, \texttt{laughing}, \texttt{trolled}, and \texttt{ruin} talk about Louise Mensch -- a British journalist and former Conservative Member of Parliament.

\textbf{Topic 3}: \\
Monday, April 16 is observed as the world voice day and the words \texttt{world}, \texttt{opportunity}, \texttt{16}, \texttt{communicate}, \texttt{\#worldvoiceday}, and \texttt{basic} group tweets that are celebrating \#WorldVoiceDay.

\textbf{Topic 4}: \\
Words such as \texttt{sewol}, \texttt{thousands}, \texttt{ferry}, \texttt{stampede}, \texttt{family}, \texttt{people}, and \texttt{died} account for the sinking of MV Sewol off the coast of South Kore on April 16th, 2014.

\textbf{Topic 5}: \\
\texttt{Selena}, \texttt{quintanilla-p}, \texttt{erez}, \texttt{love}, \texttt{la}, \texttt{always}, and \texttt{great} refer to the American singer and songwriter Selena Quintanilla-Pérez who celebrated her birthday on April 16th.

\textbf{Topic 6}: \\
Words such as \texttt{years}, \texttt{never}, \texttt{tech}, \texttt{students}, \texttt{faculty}, \texttt{lives}, \texttt{lost}, \texttt{\#neverforget}, \texttt{va}, and \texttt{heroes} are about the Virginia Tech massacre that occurred on April 16, 2007.

While some of these topics are coherent, we also obtained a few other topics that we could not annotate. 
% * <fox@vt.edu> 2017-12-18T02:10:50.883Z:
% 
% > we could not annotate
% unclear
% 
% ^.
We ran the Twitter-LDA algorithm as well. These results are described in the next section.

\subsubsection{Twitter-LDA}

Twitter-LDA assumes that each user tweets about certain topics. 
It further assumes that each tweet is only about one topic, as compared to LDA that models each document as a mixture over topics. While Twitter-LDA gave many of the same topics, it also identified a few different topics. These are described in Table \ref{results_twitter_lda}. 

Two of those topics were about Coach Frank Beamer and a certain Maverick Gamer. This included words such as \texttt{changed}, \texttt{lives}, \texttt{coach}, \texttt{beamer}, \texttt{\#thanksfrank} and \texttt{maverickgamer}, \texttt{victims}, \texttt{still}, \texttt{vol}, \texttt{1}. However, neither of these topics were about real world events. Seeing these results, we decided to simplify our scripts and run only LDA instead of both LDA and Twitter-LDA.

\begin{table}[H]
\centering
\caption{Topics from Twitter-LDA that did not appear in LDA for the ``Remember April 16'' dataset}
\label{results_twitter_lda}
\begin{tabular}{|l|l|}
\hline
\textbf{Topic 1} & \textbf{Topic 2} \\ \hline
changed          & maverickgamer    \\
lives            & victims          \\
coach            & still            \\
beamer           & vol              \\
\#thanksfrank    & 1                \\ \hline
\end{tabular}
\end{table}



\section{Solar Eclipse 2017 Tweets}
\subsection{Clustering}
We run the clustering algorithm on ``Solar Eclipse 2017'' tweet data as well. The optimal number of clusters $K$ is found to be 6. The clustering distribution is shown in Figure \ref{fig:solar_web_tweet}. The clusters are named based on the frequent word analysis. The names of the clusters are presented in Table \ref{table:solar_web_tweet}.
% * <fox@vt.edu> 2017-12-18T02:22:54.124Z:
% 
% > Table
% Try to have the figure and table cites and order of appearance be sequential and close by.
% 
% ^.

\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth]{eclipsetweet}
\caption{Cluster distribution for ``Solar Eclipse 2017'' tweets}
\label{fig:solar_web_tweet}
\end{figure}

\begin{table}[H]
\centering
\caption{Cluster Naming based on frequent words for the ``Solar Eclipse 2017'' tweet data}
\label{table:solar_web_tweet}
\begin{tabular}{|l|l|}
\hline
\textbf{Cluster} & \textbf{Name} \\ \hline
\textbf{0} & DiamondRing \\ \hline
\textbf{1} & WatchEclipse \\ \hline
\textbf{2} & SafeEclipse \\ \hline
\textbf{3} & ExoPlanetMusic \\ \hline
\textbf{4} & MidFlightEclipse \\ \hline
\textbf{5} & NonEnglish \\ \hline
\end{tabular}
\end{table}


\subsection{Topic Analysis}
\begin{table}[H]
\centering
\begin{tabular}{|p{2cm}|p{2cm}|p{2cm}|p{2cm}|p{2cm}|p{2cm}|p{2cm}|}
\hline
\textbf{eclipse} & \textbf{safety} & \textbf{photos and pictures} & \textbf{experience} & \textbf{midflight} & \textbf{weather and forecast} & \textbf{exo} \\ \hline
eclipse & view & photos & truly & catch & cloud & exo \\
watch & don't & timelapse & breath\-taking & flight & path & totaleclipse \\
moon & look & pictures & remarkable & breath\-taking & shadow &  thepower\-ofexo \\
block & glass & photobomb & beautiful & mid & weather & planet \\
cover & eye & space & great & internation\-al & rain & message \\
totality & watch & lifetime & pretty & space & outside & verexo \\
circle & safely & live & happy & wow & forecast & que \\ \hline
\end{tabular}
\caption{Keywords for topics in the collection ``Solar Eclipse''}
\label{solar-eclipse-topics}
\end{table}

We obtained the best results with number of topics as 10. However, we were only able to extract 7 coherent topics from the model. The remaining 3 topics were repeats of other topics. These topics were about -- \textbf{describing the eclipse}, \textbf{safety}, \textbf{photos and pictures}, \textbf{experience}, \textbf{experiencing the eclipse midflight}, \textbf{weather and forecast}, and a music band called \textbf{exo}.

\section{Solar Eclipse 2017 Webpages}
\subsection{Clustering}
We run the clustering algorithm on webpage data corresponding to the event of ``Solar Eclipse 2017''. The optimal number of clusters $K$ is found to be 6 using the same method mentioned previously. The cluster distribution is shown in Figure \ref{fig:solar_web}. 
The cluster names based on frequent word analysis are presented in Table \ref{table:solar_table}.

\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth]{eclipseweb}
\caption{Cluster distribution for ``Solar Eclipse 2017'' webpages}
\label{fig:solar_web}
\end{figure}

To evaluate the result, cosine similarity analysis is performed. Cosine similarity is a metric to indicate the similarity of two documents. It is defined as 

\[sim(d_1,d_2)=\frac{\overrightarrow{V}(d_1)\cdot\overrightarrow{V}(d_2)}{|\overrightarrow{V}(d_1)||\overrightarrow{V}(d_2)|}\]

The intra- and inter-cluster cosine similarity are computed. 
The intra-cluster cosine similarity is the average cosine similarity of each pair of documents in one cluster. 
Inter-cluster cosine similarity is computed in a similar way but each pair contains documents from two different clusters. 
The result is shown in Table \ref{Table:cs_solar}. The intra-cluster cosine similarity is in red font while the inter-cluster cosine similarity is in blue font. 
On average, the intra-cluster cosine similarity is about three times that of inter-cluster similarity, indicating distinct clusters.


\begin{table}[H]
\centering
\caption{The cosine similarity analysis of ``Solar Eclipse 2017'' webpage data}
\label{Table:cs_solar}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
                   & \textbf{Cluster 0}              & \textbf{Cluster 1}              & \textbf{Cluster 2}              & \textbf{Cluster 3}              & \textbf{Cluster 4}              & \textbf{Cluster 5}              \\ \hline
\textbf{Cluster 0} & {\color[HTML]{FE0000} 0.235892} & {\color[HTML]{3166FF} 0.057602} & {\color[HTML]{3166FF} 0.095294} & {\color[HTML]{3166FF} 0.077461} & {\color[HTML]{3166FF} 0.067748} & {\color[HTML]{3166FF} 0.087039} \\ \hline
\textbf{Cluster 1} & {\color[HTML]{3166FF} 0.057602} & {\color[HTML]{FE0000} 0.579325} & {\color[HTML]{3166FF} 0.092020} & {\color[HTML]{3166FF} 0.083038} & {\color[HTML]{3166FF} 0.081589} & {\color[HTML]{3166FF} 0.076596} \\ \hline
\textbf{Cluster 2} & {\color[HTML]{3166FF} 0.095294} & {\color[HTML]{3166FF} 0.092020} & {\color[HTML]{FE0000} 0.146127} & {\color[HTML]{3166FF} 0.105437} & {\color[HTML]{3166FF} 0.095530} & {\color[HTML]{3166FF} 0.099726} \\ \hline
\textbf{Cluster 3} & {\color[HTML]{3166FF} 0.077461} & {\color[HTML]{3166FF} 0.0830}   & {\color[HTML]{3166FF} 0.1054}   & {\color[HTML]{FE0000} 0.1769}   & {\color[HTML]{3166FF} 0.0772}   & {\color[HTML]{3166FF} 0.0870}   \\ \hline
\textbf{Cluster 4} & {\color[HTML]{3166FF} 0.067748} & {\color[HTML]{3166FF} 0.0816}   & {\color[HTML]{3166FF} 0.0955}   & {\color[HTML]{3166FF} 0.0772}   & {\color[HTML]{FE0000} 0.1116}   & {\color[HTML]{3166FF} 0.0849}   \\ \hline
\textbf{Cluster 5} & {\color[HTML]{3166FF} 0.087039} & {\color[HTML]{3166FF} 0.0766}   & {\color[HTML]{3166FF} 0.0997}   & {\color[HTML]{3166FF} 0.0870}   & {\color[HTML]{3166FF} 0.0849}   & {\color[HTML]{FE0000} 0.7148}   \\ \hline
\end{tabular}
\end{table}


\begin{table}[H]
\centering
\caption{Cluster Naming based on frequent words for the ``Solar Eclipse 2017'' webpage data}
\label{table:solar_table}
\begin{tabular}{|l|l|}
\hline
\textbf{Cluster} & \textbf{Name} \\ \hline
\textbf{0} & EclipseChasers \\ \hline
\textbf{1} & AjcEclipseNews \\ \hline
\textbf{2} & EclipseScience \\ \hline
\textbf{3} & BusinessInsiderEclipseArticles \\ \hline
\textbf{4} & Eclipseville \\ \hline
\textbf{5} & MuseumEclipse \\ \hline
\end{tabular}
\end{table}

\subsection{Topic Analysis}
\begin{table}[htb]
\centering
\begin{tabular}{|p{3cm}|p{3cm}|p{3cm}|}
\hline
\textbf{Topic 1} & \textbf{Topic 2} & \textbf{Topic 3} \\ \hline
total & map & world \\
totality & atlanta & nasa \\
science & carolina & lunar \\
sun & washington & annular \\
sky & denver & earth  \\ \hline
\end{tabular}
\caption{Keywords for topics in the collection ``Solar Eclipse''}
\label{solar-eclipse-topics}
\end{table}

Using number of topics as 3, we ran our LDA code to obtain the following topics. The top words for each topic are highlighted in Table \ref{solar-eclipse-topics}.

\textbf{Topic 1}: \\
The words \texttt{total}, \texttt{totality}, \texttt{science}, \texttt{sun} and \texttt{sky} convey that these documents discuss the science behind solar eclipses.

\textbf{Topic 2}: \\
The words \texttt{map} \texttt{atlanta}, \texttt{carolina}, \texttt{washington} and \texttt{denver} seem to describe the locations in which the Solar Eclipse was observed.

\textbf{Topic 3}: \\
The words \texttt{world}, \texttt{nasa}, \texttt{lunar}, \texttt{annular} and \texttt{earth} are a little disjoint from each other. Unfortunately, this is one of the disadvantages of topic modeling. 
Words that do not relate with each other are sometimes force fit together within an artificial topic.
% * <fox@vt.edu> 2017-12-18T02:24:50.264Z:
% 
% > force fit
% When you give results for each collection, can you have a table for each list of topics and each list of clusters that indicate some confidence or quality assessment you have devised, so artificial results are not found in HBase?  Please discuss a workable methodology that yields good results for production operations.
% 
% ^.

\section{Hurricane Irma Webpages}
\subsection{Clustering}
The clustering distribution and cosine similarity analysis result for "Hurricane Irma" webpage data are shown in Figure \ref{fig:Irma_web} and Table \ref{Table:Irma_web}. The optimal number of clusters $K$ is found to be 6. 
The names of clusters obtained are presented in Table \ref{table:irma_web}.


\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth]{irma_pie}
\caption{Cluster distribution for ``Hurricane Irma'' webpages}
\label{fig:Irma_web}
\end{figure}

\begin{table}[H]
\centering
\caption{The cosine similarity analysis of ``Hurricane Irma'' webpage data}
\label{Table:Irma_web}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
                   & \textbf{Cluster 0}              & \textbf{Cluster 1}              & \textbf{Cluster 2}              & \textbf{Cluster 3}              & \textbf{Cluster 4}              & \textbf{Cluster 5}              \\ \hline
\textbf{Cluster 0} & {\color[HTML]{FE0000} 0.511192} & {\color[HTML]{3166FF} 0.037326} & {\color[HTML]{3166FF} 0.052042} & {\color[HTML]{3166FF} 0.030241} & {\color[HTML]{3166FF} 0.046346} & {\color[HTML]{3166FF} 0.041547} \\ \hline
\textbf{Cluster 1} & {\color[HTML]{3166FF} 0.037326} & {\color[HTML]{FE0000} 0.274652} & {\color[HTML]{3166FF} 0.120389} & {\color[HTML]{3166FF} 0.060207} & {\color[HTML]{3166FF} 0.081885} & {\color[HTML]{3166FF} 0.086328} \\ \hline
\textbf{Cluster 2} & {\color[HTML]{3166FF} 0.052042} & {\color[HTML]{3166FF} 0.120389} & {\color[HTML]{FE0000} 0.369712} & {\color[HTML]{3166FF} 0.088786} & {\color[HTML]{3166FF} 0.144062} & {\color[HTML]{3166FF} 0.128138} \\ \hline
\textbf{Cluster 3} & {\color[HTML]{3166FF} 0.030241} & {\color[HTML]{3166FF} 0.060207} & {\color[HTML]{3166FF} 0.088786} & {\color[HTML]{FE0000} 0.081079} & {\color[HTML]{3166FF} 0.067102} & {\color[HTML]{3166FF} 0.071955} \\ \hline
\textbf{Cluster 4} & {\color[HTML]{3166FF} 0.046346} & {\color[HTML]{3166FF} 0.081885} & {\color[HTML]{3166FF} 0.144062} & {\color[HTML]{3166FF} 0.067102} & {\color[HTML]{FE0000} 0.907489} & {\color[HTML]{3166FF} 0.119770} \\ \hline
\textbf{Cluster 5} & {\color[HTML]{3166FF} 0.041547} & {\color[HTML]{3166FF} 0.086328} & {\color[HTML]{3166FF} 0.128138} & {\color[HTML]{3166FF} 0.071955} & {\color[HTML]{3166FF} 0.119770} & {\color[HTML]{FE0000} 0.118860} \\ \hline
\end{tabular}
\end{table}


\begin{table}[H]
\centering
\caption{Cluster naming based on frequent words for the ``Hurricane Irma'' web data}
\label{table:irma_web}
\begin{tabular}{|l|l|}
\hline
\textbf{Cluster} & \textbf{Name} \\ \hline
\textbf{0} & HeavyDotComIrmaUpdates \\ \hline
\textbf{1} & GlobalNewsIrmaUpdates \\ \hline
\textbf{2} & ExpressCoUkIrmaUpdates \\ \hline
\textbf{3} & FloridaIrmaUpdates \\ \hline
\textbf{4} & PicturesIrma \\ \hline
\textbf{5} & IrmasPathAndDevastation \\ \hline
\end{tabular}
\end{table}


\subsection{Topic Analysis}
\begin{figure}[H]
\includegraphics[width=\textwidth]{solar-eclipse-hurricane-irma-perplexity-coherence}
\caption{Plots showing number of topics vs. log perplexity and number of topics vs. topic coherence for the collections Solar Eclipse webpages and Hurricane Irma webpages. We attempt to choose the best number of topics based on these two plots.}
\end{figure}

We were able to obtain 5 topics on the Hurricane Irma dataset. These broadly corresponded to \textbf{damage and destruction}, \textbf{carribbean islands}, \textbf{weather and winds}, \textbf{florida}, and \textbf{president trump}.

\begin{table}[htb]
\centering
\begin{tabular}{|p{3cm}|p{3cm}|p{3cm}|p{3cm}|p{3cm}|}
\hline
\textbf{damage} & \textbf{carribbean islands} & \textbf{weather winds} & \textbf{florida} & \textbf{trump} \\ \hline
damage & carribbean & weather & florida & trump \\
destruction & coast & winds & miami & president \\
surge & islands & mph & orlando & us \\
water & puerto & tropical & coast & home \\
flood & rico & forecast & state & help \\ \hline
\end{tabular}
\caption{Keywords for topics in the collection ``Solar Eclipse''}
\label{solar-eclipse-topics}
\end{table}


\section{Vegas Shooting Webpages}
\subsection{Clustering}
The clustering distribution and cosine similarity analysis result for "Vegas Shooting" webpage data are shown in Figure \ref{fig:vegas_web} and Table \ref{Table:vegas_web}. 
The optimal number of clusters $K$ is found to be 6. 
The names of clusters obtained are presented in Table \ref{table:vegas_web}.
% * <fox@vt.edu> 2017-12-18T02:29:29.535Z:
% 
% > .
% Please add more discussion of the results for these later collections, and a summary of your findings and their implications.
% 
% ^.

\begin{figure}[H]
\centering
\includegraphics[width=0.6\textwidth]{vegas_pie}
\caption{Cluster distribution for ``Vegas Shooting'' webpages}
\label{fig:vegas_web}
\end{figure}

\begin{table}[H]
\centering
\caption{The cosine similarity analysis of ``Vegas Shooting'' webpage data}
\label{Table:vegas_web}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
                   & \textbf{Cluster 0}              & \textbf{Cluster 1}              & \textbf{Cluster 2}              & \textbf{Cluster 3}              & \textbf{Cluster 4}              & \textbf{Cluster 5}              \\ \hline
\textbf{Cluster 0} & {\color[HTML]{FE0000} 0.356642} & {\color[HTML]{3166FF} 0.115300} & {\color[HTML]{3166FF} 0.130751} & {\color[HTML]{3166FF} 0.042092} & {\color[HTML]{3166FF} 0.031763} & {\color[HTML]{3166FF} 0.028054} \\ \hline
\textbf{Cluster 1} & {\color[HTML]{3166FF} 0.115300} & {\color[HTML]{FE0000} 0.174116} & {\color[HTML]{3166FF} 0.138287} & {\color[HTML]{3166FF} 0.143103} & {\color[HTML]{3166FF} 0.109531} & {\color[HTML]{3166FF} 0.107970} \\ \hline
\textbf{Cluster 2} & {\color[HTML]{3166FF} 0.130751} & {\color[HTML]{3166FF} 0.138287} & {\color[HTML]{FE0000} 0.353778} & {\color[HTML]{3166FF} 0.154930} & {\color[HTML]{3166FF} 0.119397} & {\color[HTML]{3166FF} 0.113233} \\ \hline
\textbf{Cluster 3} & {\color[HTML]{3166FF} 0.042092} & {\color[HTML]{3166FF} 0.143103} & {\color[HTML]{3166FF} 0.154930} & {\color[HTML]{FE0000} 0.517013} & {\color[HTML]{3166FF} 0.036331} & {\color[HTML]{3166FF} 0.032462} \\ \hline
\textbf{Cluster 4} & {\color[HTML]{3166FF} 0.031763} & {\color[HTML]{3166FF} 0.109531} & {\color[HTML]{3166FF} 0.119397} & {\color[HTML]{3166FF} 0.036331} & {\color[HTML]{FE0000} 0.412272} & {\color[HTML]{3166FF} 0.024849} \\ \hline
\textbf{Cluster 5} & {\color[HTML]{3166FF} 0.028054} & {\color[HTML]{3166FF} 0.107970} & {\color[HTML]{3166FF} 0.113233} & {\color[HTML]{3166FF} 0.032462} & {\color[HTML]{3166FF} 0.024849} & {\color[HTML]{FE0000} 0.271590} \\ \hline
\end{tabular}
\end{table}


\begin{table}[H]
\centering
\caption{Cluster naming based on frequent words for the ``Vegas Shooting'' webpage data}
\label{table:vegas_web}
\begin{tabular}{|l|l|}
\hline
\textbf{Cluster} & \textbf{Name} \\ \hline
\textbf{ 0} & ReviewJournalLasVegas \\ \hline
\textbf{ 1} & MandalayBayShooting \\ \hline
\textbf{ 2} & LasVegasShootingTheGuardian \\ \hline
\textbf{ 3} & DowntownShooting \\ \hline
\textbf{ 4} & RealEstateLasVegas \\ \hline
\textbf{ 5} & LocalNewsAndEntertainmentLasVegas \\ \hline
\end{tabular}
\end{table}


\chapter{User Manual}

\section{HBase schema}

The results of clustering and topic modeling on webpages and tweets will be stored in an HBase table. The output received from the CTA team will be useful to the SOLR and FE team for faceted search. In the HBase table we will use column families to store our data. Topic and cluster are the two column families in the table that our team is concerned with. As illustrated in Table \ref{hbase_schema_topic}, column family topic will consist of columns \texttt{topic-list}, \texttt{probability-list}, and \texttt{keyword-list}. The \texttt{topic-list} will contain a list of topic labels received after topic modeling on our set of webpages and tweets. The \texttt{probability-list} will contain a list of topic probabilities with respect to the topics present in the topic list. The \texttt{keyword-list} will contain the top 5 list of words that occur in the top 2 topics of the topic lists.

Similarly, the ``cluster'' column family consists of columns \texttt{cluster-list}, \texttt{display-clusternames} and \texttt{cluster-probability}. Here, \texttt{cluster-list} and \texttt{display-clusternames} contains the name of each cluster. 
Note that \texttt{display-clusternames} is for the FE team to use as a facet in their interface. 
\texttt{cluster-probability} will denote the probability the document is in that cluster. Note that in this case, we use hard clustering, so the probability will always be 1. An example of clustering results for "Solar Eclipse 2017" tweets stored in HBase is shown in Table \ref{hbase_schema_cluster}. \\

\begin{table}[H]
\centering
\caption{HBase Schema: Fields for Topic Analysis}
\label{hbase_schema_topic}
\begin{tabular}{c|c|c|c|}
\cline{2-4}
column family    & \multicolumn{3}{c|}{\textbf{topic}}                                                \\ \cline{2-4} 
column name & \textbf{topic-list} & \textbf{probability-list} & \textbf{display-clusternames} \\ \cline{2-4} 
               & photos pictures, midflight, eclipse    & 0.53,0.26,0.12                            & photos pictures                  \\ \cline{2-4} 
               & exo, eclipse, experience    & 0.78,0.14,0.04                            & exo                   \\ \cline{2-4} 
               & midflight, eclipse, experience    & 0.40,0.27,0.15                            & midflight                \\ \cline{2-4} 
\end{tabular}
\end{table}

\begin{table}[H]
\centering
\caption{HBase Schema: Fields for Clustering}
\label{hbase_schema_cluster}
\begin{tabular}{c|c|c|c|}
\cline{2-4}
column family    & \multicolumn{3}{c|}{\textbf{cluster}}                                                \\ \cline{2-4} 
column name & \textbf{cluster-list} & \textbf{cluster-probability} & \textbf{display-clusternames} \\ \cline{2-4} 
               & WatchEclipse    & 1                            & WatchEclipse                  \\ \cline{2-4} 
               & DiamondRing    & 1                            & DiamondRing                   \\ \cline{2-4} 
               & ExoPlanetMusic    & 1                            & ExoPlanetMusic                \\ \cline{2-4} 
\end{tabular}
\end{table}

The schema also contains a field \texttt{keywords}, which is currently present only in the column-family \texttt{webpages}. The CTA team proposes the same field be present for tweets as well to index tweets by their topics and clusters.
% * <fox@vt.edu> 2017-12-18T02:33:10.464Z:
% 
% > The CTA team proposes the same field be present for tweets
% What was done? Has this been resolved? What happens in SOLR and FE with regard to tweets and webpages in this regard?
% 
% ^.

\section{Topic Analysis}
\subsection{Help File}
The entire process of training a topic model can be done through a single Python script \texttt{lda.py}. To view the help section to run the code, use the following command:
\begin{center}
\texttt{python lda.py -h}
\end{center}
The following parameters need to be used while running the code:
\begin{itemize}
\item \texttt{COLLECTION\_NAME}: The name of the data collection on which the LDA code will run.
\item \texttt{FILE}: Location of the file containing the dataset.
\item \texttt{TOPICS}: Number of topics \textit{k} to be given to the LDA model as input. To run multiple instances of the model with different number of topics in each instance, use the following format $k_1$, $k_2$, $k_3$.
\end{itemize}

In addition to these, the user can also pass the following optional arguments while running the code:
\begin{itemize}
\item \texttt{ALPHA}: The value of the hyperparameter $\alpha$ in the LDA model. If this flag is not specified, the default value of 0.1 will be used.
\item \texttt{BETA}: The value of the hyperparameter $\beta$ in the LDA model. If this flag is not specified, the default value of 0.01 will be used.
\item \texttt{ITER}: The number of Gibbs sampling iterations for the LDA model. The default value of 800 will be used if this is not specified.
\item \texttt{PREPROCESS}: Preprocessing options for the dataset if any fine-tuning is required.
\item \texttt{TOKENIZER}: The tokenizer to use -- valid options are \texttt{CommaTokenizer}, \texttt{SemicolonTokenizer}, \texttt{SpaceTokenizer}, and \texttt{WordTokenizer}.
\item \texttt{MAPPERS}: The mappers to use for each of the tokens -- valid options are \texttt{WordnetLemmatizer}, \texttt{PorterStemmer}, and \texttt{LowercaseMapper}.
\item \texttt{FILTERS}: The filters to use for each of the tokens -- valid options are \texttt{ASCIIFilter}, \texttt{Stopword\-Filter}, \texttt{LengthFilter} and \texttt{CollectionFilter}.
\item \texttt{FILTER\_WORDS}: The file path to specific words to filter out for a collection.
\end{itemize}

The output of this script includes several files, mainly -- document-topics, topics-keywords, and visualization.

\subsection{Computational Complexity}
We benchmarked our method on time taken, the results of which are shown in Figure \ref{computational-complexity}. The time taken to preprocess the text, create a model, and run evaluations takes about one hour for approximately 2.5 million tweets. 
While we did not implement LDA using Spark, this is better than the Spark implementation from Fall 2016, which was averaging about 3 hours for a fewer number of tweets. However, this is only a preliminary comparison as the datasets used might differ in composition.

\begin{figure}[H]
\includegraphics[width=\textwidth]{computational-complexity}
\caption{Computational complexity of running LDA for different  collections. The results were benchmarked on a single node server with 20 cores.}
\label{computational-complexity}
\end{figure}

\section{Clustering}
\subsection{Running Clustering Algorithm}

The user can use the Spark framework for clustering and can tune the algorithm by modifying parameters such as the number of clusters and iterations. 

First, a build.sbt has to be created with the following configuration to run the sbt package.

\begin{center}

\texttt{import sbt.Artifact} \\
\texttt{name := "Kmeans"} \\
\texttt{scalaVersion := "2.10.4"} \\
\texttt{libraryDependencies ++= Seq("org.apache.spark" \%\% "spark-core" \%\ "1.5.0","org.apache.spark" \%\% "spark-mllib" \%\ "1.5.0")} \\

\end{center}

Use the following command to generate a \texttt{jar} file to run on Apache Spark
\begin{center}
\texttt{sbt package}
\end{center}

To run \textit{k}-means, run the following command.
\begin{center}
\texttt{spark-submit <created jar file> -k <input file>}
\end{center}

For large datasets, if there is any performance related issue, the driver memory and executor memory can be increased by modifying the command as follows.

\begin{center}
\texttt{spark-submit  --driver-memory 16g --executor-memory 16g <jar> -k <input file>}
\end{center}

\subsection{Analysis}
We plot the cluster distribution using the Python script in the {\tt analysis/distribution\_analysis/} directory with the following command. The {\tt <input file>} should be in the format of {\tt "(document\_ID, cluster\_ID)"}

\begin{center}
\texttt{python clustering\_analysis.py <input file>}
\end{center}


The inter- and intra-cluster cosine similarity analysis is performed using the Python script in the {\tt "analysis/similarity\_analysis/"} directory with following command. The {\tt <input file>} should be in the format of {\tt "clean\_document,cluster\_ID"}.


\begin{center}
\texttt{python cos\_sim\_inter.py <input file>} \\
\texttt{python cos\_sim\_intra.py <input file>}
\end{center}

\chapter{Developer Manual}
\section{Clustering}
This section is useful for users to continue further development on the project. The implementation of clustering requires the following tools:

\begin{enumerate}
\item Python 2.7.0
\item Apache Spark 1.5.0
\item Scala >=2.10.4
\item SBT 1.0.1
\item Java 1.6.0\_31
\item Pyspark >=1.5.2
\item Sklearn >=0.16.0
\item Scipy >=0.14.1
\end{enumerate}

A reference manual for Scala and Spark can be found at 
% * <fox@vt.edu> 2017-12-18T02:41:50.488Z:
% 
% > at
% Looks like something is missing.
% 
% ^.
A complete reference manual for Scala and Spark 1.5.0, including the guidelines for installation, can be found at \cite{scala} and \cite{spark}, respectively.

The value of $K$ was chosen based on the Calinski Harabaz index and after examining the results. 
Developers can employ a different metric based on the input dataset to arrive at a value for $K$. 
This can be directly modified in both the Python and Scala implementations.

\section{Topic Analysis}
Topic Analysis for both documents and tweets is written in Python 2.7.14. 
The requirements for the code are:

\begin{enumerate}
\item Python 2.7.14
\item Gensim 3.1.0
\item nltk 3.2.5
\item numpy 1.13.3
\item tabulate 0.8.1
\item happybase 1.1.0
\end{enumerate}

LDA can also be done using Apache Spark using the \texttt{mllib} library. This is still under development since this implementation uses Variational Inference rather than Collapsed Gibbs Sampling for inference. This leads to different (and often poor) results as compared to Gibbs Sampling.

We use \texttt{virtualenv} to encapsulate our environment for replicability. We strongly suggest that other developers also use \texttt{virtualenv} for each of their projects to manage versions of libraries.

We also use the library \texttt{happybase} to access the HBase database dynamically. This allows us to fetch and put rows into the database directly from our code.

\section{HBase interaction}
\subsection{Clustering}
To read data from HBase, run the script {\tt HBase\_interaction/hbase\_read\_cluster.py} with the following command. Please modify table name and corresponding column list in the Python code accordingly. 
An output CSV file will be generated storing the data.

\begin{center}
\texttt{python hbase\_read\_cluster.py}
\end{center}

To write data to HBase, run the script {\tt HBase\_interaction/hbase\_write\_cluster.py} with the following command. 
The {\tt <input file>} should be a CSV file in the format {\tt "document\_ID, cluster\_name, cluster\_probability"}. 
This will fill in the HBase field "cluster-name" and "cluster-probability" with {\tt "document\_ID"} as row name. 

\begin{center}
\texttt{python hbase\_write\_cluster.py <input file>}
\end{center}


\section{File Inventory}
% * <fox@vt.edu> 2017-12-18T02:45:52.376Z:
% 
% > Inventory
% What about data files? Directories?
% Can you add a figure to show workflows?
% 
% ^.
\begin{longtable}{|l|l|}
    \hline
	\textbf{Directory} & \textbf{Description} \\
    \hline
    Clustering/kmeans/src/main/scala/kmeans.scala & Code for Clustering \\
    Clustering/kmeans/src/main/scala/Preprocess.scala & Does Preprocessing for Clustering \\
    Clustering/kmeans/src/main/scala/cluster.scala & Supporting File for Clustering \\
    Clustering/analysis/clustering\_analysis.py & Clustering Results Visualization \\
    Clustering/analysis/cos\_sim\_inter.py & Inter-Cluster Similarity Calculation \\
    Clustering/analysis/cos\_sim\_intra.py & Intra-Cluster Similarity Calculation \\
    Clustering/HBase\_interaction/hbase\_read\_cluster.py & Code for Reading data from HBase \\
    Clustering/HBase\_interaction/hbase\_write\_cluster.py & Code for writing Clustering Results to HBase \\ 
    Topic\_Analysis/tokenizers.py & Different tokenizers for the data \\
    Topic\_Analysis/mappers.py & Mapping tokens to a different form \\
    Topic\_Analysis/filter.py & Filtering out specific tokens \\
    Topic\_Analysis/pipeline.py & Preprocessing pipeline \\
    Topic\_Analysis/hbase.py & HBase interaction \\
    Topic\_Analysis/lda.py & Source code for LDA  \\
    Topic\_Analysis/utils.py & Miscellaneous functions \\
    Topic\_Analysis/readers.py & Read dataset from file \\
    \hline
    \caption{File Inventory}
    \label{timeline-task-list}
\end{longtable}

\chapter{Future Work and Enhancements}
\section{Clustering}
In clustering, we only used the hard clustering algorithms, but in the future we would like to use some soft clustering algorithms. 
This might help to understand the community structure of the documents in cases where a document could be part of more than one cluster. 
We did perform hierarchical clustering on some tweets and documents, but would like to compare and contrast these results with those of \textit{k}-means. 
In future, we would also like to improvise the frequent word analysis on the resultant clusters to include techniques from Community Detection.  
% * <fox@vt.edu> 2017-12-18T02:47:42.133Z:
% 
% > Community Detection
% Add a cite
% 
% ^.

\section{Topic Analysis}
Topic analysis focused on two models -- LDA and Twitter LDA. Twitter-LDA assumes that each user has a distribution of topics. Since the data collected is event-driven and not user-driven, we realized that Twitter-LDA is not a good model since the data violated some of the assumptions in the Twitter-LDA model. 
In the LDA model, however, we noticed some room for improvement in our process:

\begin{enumerate}
\item \textbf{Automatic elimination of collection specific words}: While we currently maintain lists of collection specific words to discard in the preprocessing step, it would indeed be better to do this automatically by understanding the word distribution in a collection.
\item \textbf{Crowd sourcing annotations for topic names}: In the current approach, we follow either automatic or manual naming of clusters. Automatic naming is fraught with challenges as naming is dependent on the order of words and does not capture adequate semantic meaning. Manual naming can get equally difficult when we have several collections and topics. Moreover, neither approach helps us understand how coherent a topic really is. Therefore, we feel that topic naming is an ideal candidate for crowd-sourcing.
\item \textbf{Joint model for tweets and webpages}: Modeling tweets and webpages separately has its advantages -- however, a joint model may be better able to capture the latent themes in the combined collection. We found that the topics in tweets were generally different from those in webpages. This makes correlation between the two collections difficult and may be alleviated by using a joint model.
% * <fox@vt.edu> 2017-12-18T02:49:47.425Z:
% 
% > We found that the topics in tweets were generally different from those in webpages
% Where is this shown? Please refer to a table or other place this is illustrated.
% 
% ^.
\end{enumerate}

\pagebreak

\addcontentsline{toc}{chapter}{Acknowledgements}
\section*{Acknowledgments}
This work was a part of the Global Event and Trend Archive Research (GETAR) and Integrated Digital Event Archiving and Library (IDEAL) projects, supported by the National Science
Foundation grants IIS-1619028 and IIS-1319578, respectively. We would also like to thank Dr. Edward A. Fox (Instructor), and Liuqing Li (GTA) from the course CS 5604 at Virginia Tech, for their support towards the completion of this work.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% If you are using BibTeX, uncomment the following:
\addcontentsline{toc}{chapter}{Bibliography}
\bibliographystyle{plain}
\bibliography{bibliography.bib}

% Otherwise, uncomment the following:
% \chapter*{Bibliography}

% \appendix

% In LaTeX, each appendix is a "chapter"
% \chapter{Program Source}

\end{document}