main.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Important note:
% Chapter heading images should have a 2:1 width:height ratio,
% e.g. 920px width and 460px height.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[11pt,fleqn]{book} % Default font size and left-justified equations
\usepackage{float}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{parcolumns}
\usepackage{listings}
\usepackage{bm}

%----------------------------------------------------------------------------------------

\input{structure}
\begin{document}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\begingroup
\thispagestyle{empty}
\begin{tikzpicture}[remember picture,overlay]
\node[inner sep=0pt] (background) at (current page.center) {\includegraphics[width=\paperwidth]{background}};
\draw (current page.center) node [fill=white,fill opacity=0.6,text opacity=1,inner sep=1cm]{\Huge\centering\bfseries\sffamily\parbox[c][][t]{\paperwidth}{\centering Machine Learning and Optimisation\\[15pt]
{\Large COMP24111 Course Notes}\\[20pt]
{\huge Jonathan Tang}}};
\end{tikzpicture}
\vfill
\endgroup

%----------------------------------------------------------------------------------------
%	COPYRIGHT PAGE
%----------------------------------------------------------------------------------------

\newpage
~\vfill
\thispagestyle{empty}

\noindent
\textbf{Contributions}\\
\noindent
Chapter 7: Katie Snell (github.com/katieisnell)\\

\ \\
\noindent Copyright \copyright\ 2017 Jonathan Tang\\

\noindent \textbf{jtang0506.github.io}

%----------------------------------------------------------------------------------------
%	TABLE OF CONTENTS
%----------------------------------------------------------------------------------------

%\usechapterimagefalse % If you don't want to include a chapter image, use this to toggle images off - it can be enabled later with \usechapterimagetrue

\chapterimage{chapter_head_1.pdf} % Table of contents heading image

\pagestyle{empty} % No headers
\tableofcontents % Print the table of contents itself
\cleardoublepage % Forces the first chapter to start on an odd page so it's on the right

\pagestyle{fancy} % Print headers again

%----------------------------------------------------------------------------------------
%	PART 1
%----------------------------------------------------------------------------------------

\part{Section I}

%----------------------------------------------------------------------------------------
%	Introduction to Machine Learning
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Introduction to Machine Learning}

\section{Supervised learning}\index{supervised learning}
In \textbf{supervised learning} problems, there is an input, $X$, an target output, $Y$, provided by a \textit{teacher} and the task is to learn the relationship between the input and the output. A training example in supervised learning is the pair ($x$, $y$) where $x$ is the input and $y$ is the target output. The labels provided with the training samples are know as the \textbf{ground truth}\index{ground truth}. We assume a model defined up to a set of parameters, $y = g(x \, \vert \, \theta)$ where $g(\cdot)$ is the model and $\theta$ are its parameters.
\subsection{Classification}
For a classification\index{supervised learning!classification} problem, the task of the classifier is to assign a class label to a given input. For example, a classification problem may be to decide whether an image contains a picture of a cat or a dog, or neither.

\subsection{Regression}
Suppose we want to predict the salary of a Computer Science graduate role. Inputs are the students attributes - that we believe affects a graduate's worth. The output is the predicted salary. Such problems where the output is a continuous number is known as a \textbf{regression}\index{Supervised learning!regression} problem.

\section{Unsupervised learning}\index{unsupervised learning}
Unlike in supervised learning, we do not have a supervisor and we only have input data. The task in \textbf{unsupervised learning} is to form a natural understanding of the hidden structure of unlabelled data. There is a structure to the input space such that certain patterns occur more often than others, and we want to see what generally happens and what does not.

\section{Reinforcement learning}\index{reinforcement learning}
In reinforcement learning, there is a \textit{teacher} who provides feedback on the action of an agent, in terms of reward and punishment.
%----------------------------------------------------------------------------------------
%	k-Nearest Neighbour
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{k-nearest Neighbour}\index{k-nearest Neighbour}
The \textbf{k-nearest Neighbour} estimation is one of the simplest machine learning algorithms, it is a \textbf{non-parametric method} (no parameter needs to be optimised) and requires \textbf{no explicit training}.

\section{k-nearest Neighbour Classification}\index{k-nearest Neighbour!classification}
The \textit{k}-nearest neighbour classifier assigns an instance to the class most heavily represented among its \textit{k} neighbours. It is based on the idea that the more similar the instances, the more likely it is that they belong to the same class. We measure how similar two data points are by using a reasonable similarity or distance measure.

\subsection{k-NN classification rule}
\begin{lstlisting}[mathescape]
let $x_{te}$ be the testing point
for each training data point $x_{tr}$
    measure distance($x_{te}$, $x_{tr}$)
end
sort distances
select $k$ nearest points
assign most common class to $x_{te}$
\end{lstlisting}

\noindent
In order to measure the distance $d(x_{te}, x_{tr})$ mentioned in the algorithm, we need to first decide on a distance measure. Euclidean distance and inner product are two measures we can used, that are defined below. An additional distance measure that we can use is cosine similarity, which is described in a later chapter.\\

\begin{exercise}
The hyper-parameter $k$ should be odd and co-prime to the number of classes in the data set, why?
\end{exercise}

\begin{definition}[Euclidean Distance]
Given two $d$-dimensional data points, $\mathbf{p}$ and $\mathbf{q}$, where $\mathbf{p}= \big[p_1, p_2, \cdots, p_d\big]$ and $\mathbf{q} = \big[q_1, q_2, \cdots, q_d\big]$, we define the \textbf{Euclidean distance}\index{similarity / distance measures!Euclidean distance} $d(\mathbf{p},\mathbf{q})$ as:
\begin{equation*}
	d(\mathbf{p},\mathbf{q}) \, = \, \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + \cdots + (p_d - q_d)^2} \, = \, \sqrt{\sum^d_{i=1}(p_i - q_i)^2}
\end{equation*}
In this case, the \textit{k}-nearest neighbours are the training points with the lowest Euclidean distances to the testing point.
\end{definition}

\begin{definition}[Inner Product]
Given two $d$-dimensional data points, $\mathbf{p}$ and $\mathbf{q}$, where $\mathbf{p}= \big[p_1, p_2, \cdots, p_d\big]$ and $\mathbf{q} = \big[q_1, q_2, \cdots, q_d\big]$, we define the \textbf{inner product}\index{similarity / distance measures!inner product} as:
\begin{equation*}
	s_{inner}(\mathbf{p},\mathbf{q}) \, = \, \sum^d_{i=1}p_iq_i
\end{equation*}
Since the inner product is a similarity measure, the \textit{k}-nearest neighbours are the training points possessing the highest similarity values to the testing point.
\end{definition}

\section{k-Nearest Neighbour Regression}\index{k-nearest Neighbour!regression}
For regression, we take a sample's $k$ nearest neighbours to estimate its target output, for example, through the weighted average of these neighbours target output. This is very similar to classification but you need to take into account the distance of this sample from its nearest neighbours.

\subsection*{Worked Example}
Since the $k$-NN classification algorithm is one of the simplest, you should be able to follow it from the lecture slides - hence a worked example has been omitted. It is also trivial to derive the algorithm for k-NN regression.

\section{Neighbour number $k$}
The neighbour number $k$ is called the \textbf{hyper-parameter}\index{hyper-parameter} and the processing of determining the best value of $k$ to use is called \textbf{hyper-parameter selection}\index{hyper-parameter selection} or model selection. If our choice of $k$ is too small, we may model noise and if our choice of $k$ is too large, neighbours will include too many samples from other classes.\\

\noindent
The number of training samples also plays a role, a small number of training samples will lead to insufficient information about the data set. However, a large number of training samples comes with a tradeoff in time and memory cost for calculating and sorting distances.

%----------------------------------------------------------------------------------------
%	Linear Classification and Regression
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Linear Classification and Regression}

\section{Linear Regression}
In \textbf{linear regression}\index{linear regression}, the model formulates the prediction function as $\hat{y} = f(x) = w_0 + w_1x$, indeed a straight line. You have come across this problem in high school before, drawing a \textit{line of best fit} for $(x, y)$ pairs so that you can estimate the output for some $x$. You probably would have been taught to draw the \textit{ideal} line by drawing a line that has equal number of points on each side of the line - in this chapter, we will look at how we optimise this linear regression model.\\

\noindent
We have a two parameters to optimise, namely $w_0$ (the \textbf{bias parameter}\index{bias parameter}) and $w_1$. To find their optimal setting, we can compute the prediction errors and the ideal settings for the parameters would minimise the prediction error.

\subsection{Sum-of-squares error function}
A commonly used error function is the \textbf{sum-of-squares}\index{sum-of-squares} error function:
$$O = (\hat{y_1} - y_1)^2 + (\hat{y_2} - y_2)^2 + \cdots + (\hat{y_n} - y_n)^2 = \sum^n_{i=1}(\hat{y_i} - y_i)^2 = \sum^n_{i=1}(w_1x_i + w_0 - y_i)^2$$
It follows that our optimisation problem is to minimise $O(w_1, w_0) = \frac{1}{2}\sum^n_{i = 1}(w_1x_i + w_0 - y_i)^2$

\begin{exercise}
	The $\frac{1}{2}$ is not a typo, why does the $\frac{1}{2}$ not change our optimisation problem?
\end{exercise}

$$\text{The optimal $w_1$ and $w_0$ satisfy:} \quad \frac{\delta O(w_1, w_0)}{\delta w_0} = 0 \quad \text{and} \quad \frac{\delta O(w_1, w_0)}{\delta w_1} = 0 $$

$$\text{We can write} \quad O(w_1, w_0) = \frac{1}{2} O_i(w_1, w_0) \quad \text{where} \quad O_i(w_1, w_0) = (w_1x_i + w_0 - y_i)^2$$

$$\text{It follows that} \quad \frac{\delta O_i(w_1, w_0)}{\delta w_0} = 2(w_1x_i + w_0 - y_i) \quad \text{and} \quad \frac{\delta O_i(w_1, w_0)}{\delta w_1} = 2(w_1x_i + w_0 - y_i)x_i$$

$$\frac{\delta O(w_1, w_0)}{\delta w_0} = \frac{1}{2}\sum_{i=1}^n\frac{\delta O_i(w_1, w_0)}{\delta w_0} = \sum^n_{i=1}(w_1x_i + w_0 - y_i) = w_1 \sum^n_{i=1} x_i + nw_0 - \sum^n_{i=1} y_i = 0$$

$$\frac{\delta O(w_1, w_0)}{\delta w_1} = \frac{1}{2}\sum_{i=1}^n\frac{\delta O_i(w_1, w_0)}{\delta w_1} = \sum^n_{i=1}(w_1x_i + w_0 - y_i)x_i = w_1 \sum^n_{i=1} x_i^2 + w_0 \sum^n_{i=1} x_i - \sum^n_{i=1} x_iy_i = 0$$

\noindent
Now from the two equations above, we have a pair of simultaneous equations with $w_1$ and $w_0$ as our unknowns. We can calculate all the summations as they are the $(x, y)$ values in our training samples and $n$ is simply the number of training examples. This model is known as the \textbf{linear least squares}\index{linear least squares} model.

\subsection*{Worked Example}
Consider the following data set, where we wish to produce a linear least squares model.
\begin{table}[h]
\centering
\begin{tabular}{l|lllll}
x & 4  & 7  & 11 & 10 & 14 \\ \hline
y & 62 & 58 & 51 & 58 & 44
\end{tabular}
\end{table}
$$ \sum^5_{i=1} x_i = 4 + 7 + 11 + 10 + 14 = 46 \quad \text{and} \quad \sum^n_{i=5} x_iy_i = 4 \cdot 62 + 7 \cdot 58 + 11 \cdot 51 + 10 \cdot 58 + 14 \cdot 44 = 2411$$
$$ \sum^n_{i=5} y_i = 62 + 58 + 51 + 58 + 44 = 273 \quad \text{and} \quad \sum^5_{i=1} x_i^2 = 4^2 + 7^2 + 11^2 + 10^2 + 14^2 = 482$$

\noindent
Now we have the pair of simultaneous equations:
$$46w_1 + 5w_0 - 273 = 0 \quad \text{and} \quad 482w_1 + 46w_0 - 2411 = 0$$

\noindent
It follows that $w_1 \approx -1.711$ and $w_0 \approx 70.34$ so we get $\hat{y} = -1.711x + 70.34$

\subsection{Regularised least squares}
\textbf{Overfitting}\index{overfitting} is the problem where an algorithm produced corresponds too closely to the training dataset (in particular, when it is small) so it may be unsuitable to fit additional data. Overfitting can also occur if the algorithm has modelled noise or random data among the training data. In the least squares model, we can add a \textbf{regularisation term}\index{regularisation term} to the error function in attempt to control overfitting. Our optimisation problem becomes:

$$O_\lambda (w_1, w_0) = \frac{1}{2}\sum^n_{i = 1}(w_1x_i + w_0 - y_i)^2 + \frac{\lambda}{2}(w_0^2 + w_1^2)$$

\subsection*{Hyperparameter $\lambda$}
Notice in the regularised least squares solution, we have a $\lambda$ in the regularisation term. This is a positive real-valued number, with $\lambda > 0$, set by the user. The purpose of $\lambda$ is to control the balance between the data dependent error function and the regularisation term and is called a hyper-parameter so it can be distinguished from those model parameters that need to be optimised, namely $w_1$ and $w_0$.

\section{Gradient descent}
Another way we can minimise the error function is by \textbf{gradient descent}\index{gradient descent}. The gradient of the error function indicates the direction in which the error \textit{ascends} the fastest, so we can simply move across the opposite direction, so the error descends the fastest. Say we have the error function $f(w)$ and an initial value of $\bm{w} = [w_0, w_1]$, then we can use $\bm{w}^{(t+1)} = \bm{w}^{(t)} - \eta f'(\bm{w}^{(t)})$ where $\eta > 0$ is the learning rate.

\subsection{Sequential (on-line) training}\index{sequential training}
In the gradient descent method described above, it would require processing of the entire training set and this can be computationally costly for large datasets. The idea of \textbf{sequential training} is to update model parameters after the presence of one training sample (or a small set of training samples). We will talk about a sequential training process called \textbf{stochastic gradient descent}.

\subsection*{Stochastic gradient descent (SGD)}\index{gradient descent!stochastic gradient descent}
\begin{definition}[Stochastic gradient descent]
	A way to estimate the gradient of the error function using a single training sample.
	$$\bm{w}^{(t+1)} = \bm{w}^{(t)} - \eta (\bm{w_1}^{(t)}x_n + \bm{w_0}^{(t)} - y_n)(x_n + 1)$$
\end{definition}

\begin{definition}[Mini-batch gradient descent (MBGD)]\index{gradient descent!mini-batch}
	A way to estimate the gradient of the error function using a small set of training samples.
	$$\bm{w}^{(t+1)} = \bm{w}^{(t)} - \eta \sum_{n \in I}(\bm{w_1}^{(t)}x_n + \bm{w_0}^{(t)} - y_n)(x_n + 1)$$
	where $I$ denotes a small set of training samples.
\end{definition}
%----------------------------------------------------------------------------------------
%	Logistic Regression
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Logistic Regression}

\section{Linear basis function model}\index{linear basis}
Suppose the estimated output variable is a linear combination of fixed nonlinear functions (known as basis functions) of the input. For example $\hat{y} = w_0 + w_1x + w_2x^2 + w_3x^3$ is a linear combination of $1, x, x^2$ and $x^3$ with coefficients $w_0, w_1, w_2, w_3$ respectively. The purpose of incorporating a \textbf{linear basis function model}\index{linear basis function model} is so that it is suitable for non-linear classification and regression.

$$\hat{y} = w_0 + w_1\phi_1(\bm{x}) + w_2\phi_2(\bm{x}) + \cdots + w_D\phi_D(\bm{x}) = \bm{w}^T\bm{\phi(x)}$$
$$\text{where} \quad \bm{w} = [w_0, w_1, \cdots, w_D]^T \quad \text{and} \quad \bm{\phi(x)} = [1, \phi_1(x), \phi_2(x), \cdots, \phi_D(x)]^T$$

\subsection{Polynomial regression}\index{linear basis!polynomial}
For a single input variable, if we take $\bm{\phi(x)} = [1, x, x^2, \cdots, x^D]^T$, our linear basis function model is
$$\hat{y} = w_0 + w_1x + w_2x^2 + \cdots + w_Dx^D$$
This is known as polynomial regression, and in the case $D = 1$, we get linear regression.

\begin{exercise}
	It is typical to set $\phi_0(x) = 1$, why is that?
\end{exercise}
%----------------------------------------------------------------------------------------
%	Support Vector Machine
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Support Vector Machine}

\section{Kernel trick}\index{kernel trick}

\section{Model Validation}\index{model validation}
\subsection{Holdout method}\index{model validation!holdout method}
With the \textbf{holdout method}, the whole dataset is split into two groups, a training set and a testing set. The model is trained using the training set and asked to predict output values for the data in the testing set, which it has never seen before. This evaluation can have a high variance as we may get an unfortunate split as it may depend heavily on which data points end up in the training set and which end up in the testing set. Another drawback is that we may only have a small dataset, so we may not afford to set aside a portion of the dataset for testing.

\subsection{Random subsampling}
In each split of \textbf{random subsampling}\index{random subsampling}, we select a fixed number of samples for testing and the remaining samples are used for training. For each data split, the classifier is training from scratch and its error rate is estimated with the testing examples.

\subsection{k-fold cross validation}\index{model validation!k-fold cross validation}
\textbf{k-fold cross validation} is one way to improve over the holdout method, the dataset is divided into $k$ partitions and the holdout method is performed $k$ times. Each time, one of the $k$ subsets is used as the testing set and the remaining $k - 1$ subsets are combined and used as the training set. We evaluate the error estimate as the average error across the $k$ trials. The advantage of this method is that it matters less how the dataset gets divided and all the examples in the dataset are eventually used for both training and testing, therefore the variance of the resulting estimate is reduced as $k$ is increased. However, the training has to be done $k$ times, which means this method gets expensive to compute as $k$ is increased.

\newpage
\subsection{Leave-one-out cross validation}\index{model validation!LOO cross validation}
\textbf{Leave-one-out cross validation} is the degenerate case for $k$-fold cross validation, with $k$ = $N$, the number of data points in the dataset. As before, the average error is computed and used to evaluate the model. The evaluation given by leave-one-out cross validation error is good, but it is very expensive to compute compared to other methods.

\subsection{Bootstrap}
With \textbf{bootstrap}\index{bootstrap}, on each iteration, you randomly select, with replacement, a fixed number of examples to use for training. The remaining examples that were not selected are used for testing - this means that the number of testing samples can change over repeats, as training samples are selected with replacement.

\subsection*{Model Selection (hyper-parameter selection)}
To select the best model, we run the algorithm with different hyper-parameters, which yields different models and use one of the above validation schemes to calculate an error estimate. It follows that the best model is the one that yields the lowest error estimate.

\section{Confusion matrix}\index{confusion matrix}
A confusion matrix is a table with two rows and two columns which allows further analysis rather than just the proportion of correct classifications. For example, if we had a dataset containing 98 examples from Class 1 and 2 examples from Class 2, there may be a classifier which classifies all the observations as Class 1, which yields a overall accuracy of 98\%. However, accuracy is not a reliable metric for this classifier as the classifier would have 100\% recognition rate for Class 1 but 0\% recognition rate for Class 2.\\

\begin{definition}[True Positives (TP)]\index{confusion matrix!true positive}
Both the predicted class and actual class is 'Yes'.
\end{definition}
\begin{definition}[True Negatives (TN)]\index{confusion matrix!true negative}
Both the predicted class and actual class is 'No'.
\end{definition}
\begin{definition}[False Positives (FP)]\index{confusion matrix!false positive}
The predicted class is 'Yes' and actual class is 'No'.
\end{definition}
\begin{definition}[False Negatives (FN)]\index{confusion matrix!false negative}
The predicted class is 'No' and actual class is 'Yes'.
\end{definition}

\subsection*{Worked Example}
Suppose that we predicted the presence of a disease that a patient and obtain the results below.
\begin{table}[h]
\centering
\begin{tabular}{c|c|cc}
\multicolumn{2}{c|}{\multirow{2}{*}{n = 165}} & \multicolumn{2}{c}{Predicted Class} \\ \cline{3-4}
\multicolumn{2}{c|}{} & No & Yes \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Actual\\ Class\end{tabular}} & No & 50 & 10 \\
 & Yes & 5 & 100
\end{tabular}
\end{table}

\begin{example}
	For the above example, \textbf{TP} = 100, \textbf{TN} = 50, \textbf{FP} = 10 and \textbf{FN} = 5.
\end{example}

\newpage
\noindent
Some questions we may want to ask about our predictions are:
\begin{enumerate}
	\item When the patient actually has the disease, how often did we predict this?
	\item When the patient does not have the disease, how often did we predict this?
	\item When we predict that a patient has a disease, how often are we correct?
\end{enumerate}

\noindent
\\First, we define some terms which directly relate to the questions above.\\

\begin{definition}[Sensitivity / Recall]\index{confusion matrix!sensitivity}\index{confusion matrix!recall}
The proportion of positives that are correctly classified.
\begin{equation*}
	\frac{\text{True Positives}}{\text{Number of Actual Positives}} = \frac{\text{TP}}{\text{TP+FN}}
\end{equation*}
\end{definition}

\begin{definition}[Specificity]\index{confusion matrix!specificity}
The proportion of negatives that are correctly classified.
\begin{equation*}
	\frac{\text{True Negatives}}{\text{Number of Actual Negatives}} = \frac{\text{TN}}{\text{TN+FP}}
\end{equation*}
\end{definition}

\begin{definition}[Precision]\index{confusion matrix!precision}
The proportion of predicted positives which were positive.
\begin{equation*}
	\frac{\text{True Positives}}{\text{Number of Predicted Positives}} = \frac{\text{TP}}{\text{TP+FP}}
\end{equation*}
\end{definition}

\begin{example}
	By definition, the answers to the above questions are sensitivity, specificity and precision respectively.
\end{example}

\begin{exercise}
Calculate the sensitivity, specificity and precision for the confusion matrix given above.
\end{exercise}

\begin{definition}[F1-score]\index{confusion matrix!F1-score}
The harmonic mean of precision and recall.
\begin{equation*}
	2 \cdot \frac{1}{\frac{1}{\text{recall}} + \frac{1}{\text{precision}}}
	= 2 \cdot \frac{\text{precision} \cdot \text{recall}}{\text{precision + recall}}
\end{equation*}
\end{definition}

%----------------------------------------------------------------------------------------
%	Deep Learning Models
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Deep Learning Models}

%----------------------------------------------------------------------------------------
%	PART 2
%----------------------------------------------------------------------------------------

\part{Section II}

%----------------------------------------------------------------------------------------
%	Generative Models and Naive Bayes
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Generative Models and Naive Bayes}

\section*{Introduction}
In machine learning, naive Bayes classifiers are a group of \textbf{probabilistic classifiers} which are based on using Bayes’ theorem assuming, naivly, that there is a \textbf{strong independence} between the features. Naive Bayes are probabilistic, meaning that they calculate the probability of each category for a given sample, and then output the category with the highest probability.\\

\noindent
Naive Bayes is popular method for determining the category of text, with word frequencies as the features. Some examples include: \\
\begin{enumerate}
	\item Determining what category an email belongs to, i.e. spam or legitimate, fashion or sports
	\item Digit recognition
	\item Face recognition
\end{enumerate}

\subsection*{Background}
There are three methodologies to design a model: \\
\begin{enumerate}
	\item Model a classification rule directly, for example k-NN, linear classifier, SVM, neural networks
	\item Model the probability of class memberships given input data, for example logistic regression, probabilistic neural networks
	\item Make a probabilistic model of data within each class, for example naive Bayes, model-based
	
\end{enumerate}
\ \\
\noindent
This brings up an important way of distinguishing these models based on what we want to achieve with the data we have been given; probabilistic models vs non-probabilistic models and discriminative models vs generative models.

\newpage
\noindent
The table shows us the difference between the learning models (classifiers) more clearly.

\begin{table}[h]
	\centering
	\begin{tabular}{|c|l|l|}
		\hline
		\multicolumn{1}{|l|}{}  & \multicolumn{1}{c|}{\textbf{Probabilistic}}                                                 & \multicolumn{1}{c|}{\textbf{Non-Probabilistic}}                                          \\ \hline
		\textbf{Discriminative} & \begin{tabular}[c]{@{}l@{}}$\bullet$ Logistic regression\\ $\bullet$ Probabilistic neural networks\end{tabular} & \begin{tabular}[c]{@{}l@{}}$\bullet$ k-NN\\ $\bullet$ Linear classifier\\ $\bullet$ SVM\\ $\bullet$ Neural networks\end{tabular} \\ \hline
		\textbf{Generative}     & \begin{tabular}[c]{@{}l@{}}$\bullet$ Naive Bayes\\ $\bullet$ Model-based (e.g. GMM)\end{tabular}                & N.A.                                                                                     \\ \hline
	\end{tabular}
\end{table}

\section{Probability basics}
\noindent
We will define some basic probability notation that will help us to understand how naive Bayes works. \\

\begin{definition}[Prior probability]\index{prior probability}
	The prior probabilities are the probabilities of an example from the training set belonging to each class:
	
	\begin{equation}
	P(c_i) = \frac{\textrm{number of examples that belong to class}~i}{\textrm{total number of examples}}
	\end{equation}
\end{definition}

\begin{definition}[Conditional Probability]\index{conditional probability}
	Conditional probability is the probability of $x_1$ happening if $x_2$ happens too. We use the notation $P(x_1 \, \vert \, x_2)$.
\end{definition}
\ \\ 
\noindent
These definitions of probabilities will now be clear with an example of using naive Bayes for discrete-valued features.

\section{Naive Bayes for discrete-valued features}\index{Naive Bayes!discrete}
\noindent
Suppose we want to build our classifier to say \textbf{whether a piece of text is about sports or not}. Our training set has 5 sentences: \\
\begin{itemize}
	\item “A great game” - Sports
	\item “The election was over” - Not sports
	\item “Very clean match” - Sports
	\item “A clean but forgettable game” - Sports
	\item “It was a close election” - Not sports
\end{itemize}
\ \\
\noindent
Lets say we want to classify “A very close game”.
As naive Bayes is a \textbf{probabilistic classifier}, we want to calculate the probability that the sentence “A very close game” is Sports and also the probability that it is Not sports. \\

\noindent
Once we have done this, we take the largest probability of the two which determines what category our sentence has been classified as (we want this to be Sports in this case). This is an application of the \textbf{``Maximum A Posterior’’}, or MAP, classification rule. \\

\begin{definition}[MAP Rule]\index{MAP Rule}
	The MAP rule determines that for an input $x$, find the largest probability from $L$ probabilities that are outputted by a discriminative probabilistic classifier  $P(c_1 \, \vert \, x), \cdots, P(c_L, \, \vert \, x)$. Then we assign $x$ to label $c^*$ if $P(c^* \, \vert \, x)$ is the largest.
\end{definition}
\ \\
In mathematical terms, we want $P(\text{Sports}\, | \,\text{a very close game}) > P(\text{Not sports}\, |\, \text{a very close game})$. \\

\noindent
Before we start, we need to decide what we shall use as features. In this case, we are comparing words so we will use \textbf{word frequencies}. This means our features will be the counts of each of the words. \\

\noindent
Now we look at the \textbf{Bayesian rule} (or Baye’s Theorem) which is useful when working with conditional probabilities because it provides a way to ``reverse’’ them. This is exactly what we want. \\

\begin{definition}[Bayesian Rule]\index{Bayesian rule}
	We define the Bayesian rule as follows:
	\begin{equation}
	P(c_i \, \vert \, \textbf{x}) = \frac{P(\textbf{x} \, \vert \, c_i) \cdot P(c_i)}{P(\textbf{x})},~i = 1,2,\cdots,L
	\end{equation}
\end{definition}
\ \\
\noindent
In our example, we want to work out $P(\text{Sports} \, \vert \, \text{a very close game})$, so using the Bayesian rule this gives us:
\begin{equation*}
P(\text{Sports} \, \vert \, \text{a very close game}) = \frac{P(\text{a very close game}\, \vert \, \text{Sports}) \cdot P(\text{Sports})} {P(\text{a very close game})}
\end{equation*}
\ \\
\noindent
Note that in our case, we just want to find out which category (Sports or Not sports) has a bigger probability, so we can ignore the divisor, as it is the same for both categories, and just compare:
\begin{equation*}
P(\text{a very close game}\, |\, \text{Sports}) \cdot P(\text{Sports}) \quad \text{and} \quad
P(\text{a very close game}\, |\, \text{Not sports}) \cdot P(\text{Not sports})
\end{equation*}
\noindent
We can calculate these probabilities easily. \\

\noindent 
Now we count how many times the sentence ``A very close game’’ appears in the Sports category in our training set, and divide it by the total which gives us $P(\text{a very close game} \, \vert \, \text{Sports})$. \\

\noindent
However, “A very close game” does not appear as a whole sentence in our training set so we will get a probability of 0. This means the model is not useful unless every sentence we want to classify appears in our training set, which defeats the point of using it. \\

\noindent
So to overcome this issue we make a strong \textbf{naive} assumption that every word in the sentence is \textbf{independent} of the others in the sentence. \\

\noindent
So this means now that ``A very close game’’ is the same as ``very game close a’’. We write this as: \\
$$P(\text{a very close game}) = P(\text{a}) \cdot P(\text{very}) \cdot P(\text{close}) \cdot P(\text{game})$$
\noindent
So now we can apply this to the conditional probability we were working with before as so: \\
$$P(\text{a very close game} \, \vert \, \text{Sports}) = P(\text{a $\vert$ Sports}) \cdot P(\text{very $\vert$ Sports}) \cdot P(\text{close $\vert$ Sports}) \cdot P(\text{game $\vert $ Sports})$$
\noindent
So now we can do some calculations. We first work out P(Sports) and P(Not sports), which is simply the prior probabilities.\\

\noindent
So in our example, $P(\text{Sports}) = 3/5$ and $P(\text{Not sports}) = 2/5$. \\

\noindent
Next we need to calculate each of the conditional probabilities of each word appearing in a class. So we start by calculating $P(\text{game} \vert \text{Sports})$ which is the number of times the word ``game’’ appears in Sports examples in the training set, which is 2, divided by the total number of words in the Sports examples, which is 11. Therefore, $P(\text{game} \vert \text{Sports}) = 2/11$. \\

\noindent
However, we have a problem when we work out the probability of $P(\text{close} \vert \text{Sports})$ as ``close’’ does not appear in any of our Sports examples. This means the probability is 0. This causes a \textbf{zero conditional probability problem} when we work out the probability of all the words combined as this 0 will make us end up with a zero probability.\\

\noindent
In order to overcome this, we apply Laplace smoothing. \\
\begin{definition}[Laplace smoothing]\index{Laplace smoothing}
	Laplace smoothing is the process of adding 1 to every count so we do not have any counts equalling zero.
\end{definition}

\noindent
We adjust our divisor to also add the number of possible words in the whole training set, in this example all possible words are ['a', 'great', 'very', 'over', 'it', 'but', 'game', 'election', 'clean', 'close', 'the', 'was', 'forgettable', 'match'], which is 14. \\

\noindent
After we apply smoothing, our probabilities are as follows:
\begin{table}[h]
	\centering
	\begin{tabular}{ccc}
		\textbf{Word} & \textbf{P(Word | Sports)} & \textbf{P(Word | Not sports)} \\
		a             & 2 + 1 / 11 + 14           & 1 + 1 / 9 + 14                \\
		very          & 1 + 1 / 11 + 14           & 0 + 1 / 9 + 14                \\
		close         & 0 + 1 / 11 + 14           & 1 + 1 / 9 + 14                \\
		game          & 2 + 1 / 11 + 14           & 0 + 1 / 9 + 14               
	\end{tabular}
\end{table}
\ \\
\noindent
The final step is to multiple all our non-zero probabilities and see whether Sports or Not sports are bigger, and do not forgot to multiple by the prior probability too. \\
\begin{equation*}
P(\text{a} \vert \text{Sports}) \cdot P(\text{very} \vert \text{Sports}) \cdot P(\text{close} \vert \text{Sports}) \cdot P(\text{game} \vert \text{Sports}) \cdot P(\text{Sports}) = 2.76 \cdot 10^{-5} = 0.0000276
\end{equation*}
\ \\
\noindent
Similarly we have $P(\text{a} \vert \text{Not sports}) = 0.572 \cdot 10^{-5} = 0.00000572$. \\

\noindent
So we have classified ``A very close game’’ to be in the Sports category using the naive Bayes classifier for discrete-valued features.\\

\newpage
\section{Naive Bayes for continuous-valued features}
When we want to model features which are continuous in nature, such as temperature, then our discrete method will not be appropriate. \\

\noindent
However, the prior probabilities can still be calculated in the same way as the example above. \\

\noindent
Instead, we \textbf{estimate} the \textbf{mean} and \textbf{variance} for each class and we can use this with the assumption that the attributes are subject to a \textbf{normal distribution} (or Gaussian). \\

\noindent
Now when we are in the test phase, we can calculate the conditional probabilities modelled with the Gaussian distribution using the equation in our original Bayesian rule above. \\
\begin{equation}
P(x_j | c_i) = \frac{1}{{\sigma_{ji} \sqrt {2\pi } }}e^{{{ - \left( {x_j - \mu_{ji} } \right)^2 } \mathord{\left/ {\vphantom {{ - \left( {x - \mu } \right)^2 } {2\sigma ^2 }}} \right. \kern-\nulldelimiterspace} {2\sigma_{ji} ^2 }}}
\end{equation}
\ \\
\noindent
Note that when $\sigma = 0$, we cannot use the equation but instead we realise that this means that there is \textbf{no spread of data} hence the attribute has only one value. Therefore, this means the probability of getting that attribute is 1. This means we only need to the equation when $\sigma > 0$.

%----------------------------------------------------------------------------------------
%	Clustering Analysis Basics
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Clustering Analysis Basics}

\section*{Introduction}
Clustering analysis is the process of finding similarities between data according to the characteristics underlying the data and grouping similar data objects into clusters. A \textbf{cluster}\index{cluster} is a group of data points which are similar to one another within the same group and dissimilar to the points in other groups. Clustering analysis is \textbf{unsupervised} as there are no predefined classes for a training data set. The main approach of clustering analysis is to maximise the intra-cluster similarity and minimise the inter-cluster similarity. Typically, clustering analysis is either used as a stand-alone tool to gain an insight into data distribution or used as a preprocessing step of other algorithms in intelligent systems.\\

\noindent
The two general tasks of clustering analysis are:
\begin{enumerate}
	\item Identifying the "natural" number of clusters present in a data set
	\item Properly grouping data points into "sensible" clusters
\end{enumerate}

\subsection*{Real Life Applications}
\begin{itemize}
	\item \textbf{Marketing} - companies can discover distinct groups in their customer bases and then use this knowledge to develop targeted marketing programs
	\item \textbf{Social network mining} - discovering communities of similar interests in a large group of people
	\item \textbf{Image segmentation} - dividing an image into distinct regions for object recognition
\end{itemize}

\section{Data Representation}\index{data representation}
\begin{multicols}{2}
\noindent
A data matrix is a $n \times p$ matrix which represents $n$ data points with $p$ dimensions. The data matrix has $two$ modes as rows and columns represent different entities.
\columnbreak
\begin{equation*}
	\begin{bmatrix}
		x_{11} & x_{12} & \cdots & x_{1p} \\
		x_{21} & x_{22} & \cdots & x_{2p} \\
		\vdots & \vdots & \vdots & \vdots \\
		x_{n1} & x_{n2} & \cdots & x_{np} \\
	\end{bmatrix}
\end{equation*}
\end{multicols}

\begin{multicols}{2}
\noindent
A distance / dissimilarity matrix is a $n \times n$ matrix which represents the distance between each data point. The distance matrix is a symmetric triangular matrix as $\mathbf{d}(x, y) = \mathbf{d}(y, x)$ where $x, y$ are two data points. The distance matrix has $one$ mode as the rows and column represent the distance for the same entity.
\columnbreak
\begin{equation*}
	\begin{bmatrix}
		0 & & & & \\
		d(x_2, x_1) & 0 & & & \\
		d(x_3, x_1) & d(x_3, x_2) & 0 & & \\
		\vdots & \vdots & \vdots & \ddots & \\
		d(x_n, x_1) & d(x_n, x_2) & d(x_n, x_3) & \cdots & 0\\
	\end{bmatrix}
\end{equation*}
\end{multicols}

\section{Distance Measures}\index{distance measures}
The \textbf{Minkowski distance} is a metric in a normed vector space which can be considered as the generalisation of both the Euclidean distance and the Manhattan distance. \\

\begin{definition}[Minkowski Distance]\index{distance measures!Minkowski distance}
The Minkowski distance of order $p$ between two points $\mathbf{x} = (x_1, x_2, \cdots, x_n)$ and $\mathbf{y} = (y_1, y_2, \cdots, y_n)$ is defined as:
\begin{equation*}
	d(\mathbf{p},\mathbf{q}) \, = \, \Bigg(\vert x_1 - y_1 \vert^p + \vert x_2 - y_2 \vert^p + \cdots + \vert x_n - y_n \vert^p \Bigg)^{\frac{1}{p}}, p > 0
\end{equation*}
\end{definition}

\noindent
The value of $p$ in the Minkowski Distance would be selected depending on the application. The \textbf{Manhattan} and \textbf{Euclidean} distances are simply Minkowski distances of order 1 and 2 respectively.\\

\begin{definition}[Manhattan Distance]\index{distance measures!Manhattan distance}
\begin{equation*}
	d(\mathbf{p},\mathbf{q}) \, = \, \vert x_1 - y_1 \vert + \vert x_2 - y_2 \vert + \cdots + \vert x_n - y_n \vert
\end{equation*}
This is also known as the city block distance, the reason becomes clear in the examples below.
\end{definition}

\begin{definition}[Euclidean Distance]\index{distance measures!Euclidean distance}
\begin{equation*}
	d(\mathbf{p},\mathbf{q}) \, = \, \sqrt{\vert x_1 - y_1 \vert^2 + \vert x_2 - y_2 \vert^2 + \cdots + \vert x_n - y_n \vert^2}
\end{equation*}
This is the distance that you are already familiar with, in $n$ dimensions.
\end{definition}

\begin{exercise}
When is the Manhattan distance between $x$ and $y$ equal to the Euclidean distance between $x$ and $y$, where $x$ and $y$ are data points of two dimensions?
\end{exercise}

\begin{definition}[Cosine measure]\index{distance measures!Cosine measure}
For $\mathbf{x} = (x_1, x_2, \cdots, x_n)$ and $\mathbf{y} = (y_1, y_2, \cdots, y_n)$
\begin{equation*}
	\cos(\mathbf{x}, \mathbf{y}) = \frac{x_1y_1 + \cdots + x_ny_n}{\sqrt{x_1^2 + \cdots + x_n^2} \; \sqrt{y_1^2 + \cdots + y_n^2}} \quad \text{and} \quad d(\mathbf{x}, \mathbf{y}) = 1 - \cos(\mathbf{x}, \mathbf{y})
\end{equation*}
Note that $-1 \leq \cos(\mathbf{x}, \mathbf{y}) \leq 1$ and $0 \leq d(\mathbf{x}, \mathbf{y}) \leq 2$
\end{definition}

\newpage

\subsection*{Worked Example}
Suppose we have some documents that we want to compare to see how similar texts are, without taking into account the order of the words. For this example, we will consider:\\

\begin{enumerate}[label=(\alph*)]
	\item Labeeba loves me more than Hani loves me
	\item Hani loves Labeeba more than Labeeba loves Hani
	\item Labeeba likes Hani more than Hani likes Labeeba
\end{enumerate}

\ \\ \noindent
First, we make a list of all the words that appear across all texts.
\begin{center}
	[Hani, Labeeba, likes, loves, me, more, than]
\end{center}

\noindent
Next, we construct a vector for each document, with the frequency of each word.
\begin{center}
	\textbf{a} = [1, 1, 0, 2, 2, 1, 1]\\
	\textbf{b} = [2, 2, 0, 2, 0, 1, 1]\\
	\textbf{c} = [2, 2, 2, 0, 0, 1, 1]\\
\end{center}

\noindent
Now we can compute the \textbf{cosine measures}: cos(\textbf{a}, \textbf{b}), cos(\textbf{a}, \textbf{c}) and cos(\textbf{b}, \textbf{c}).

\begin{equation*}
	\cos(\mathbf{a}, \mathbf{b}) = \frac{(1)(1) + (1)(2) + (0)(0) + (2)(2) + (2)(0) + (1)(1) + (1)(1)}{\sqrt{1^2 + 1^2 + 0^2 + 2^2 + 2^2 + 1^2 + 1^2} \, \sqrt{2^2 + 2^2 + 0^2 + 2^2 + 0^2 + 1^2 + 1^2}} \approx 0.694
\end{equation*}

\noindent
By similar calculations, we find that $\cos(\mathbf{a}, \mathbf{c}) \approx 0.463$ and $\cos(\mathbf{b}, \mathbf{c}) \approx 0.714$. This tells us that sentences \textbf{b} and \textbf{c} are the most similar pair out the above texts, as they have the highest cosine measure. This is also the reason $d(\mathbf{x}, \mathbf{y})$ is defined as $1 - \cos(\mathbf{x}, \mathbf{y})$ since a larger cosine measure would be converted into a smaller distance.

\section{Distance for binary features}\index{binary features!distance}
For binary features, their values can be converted to 1 or 0, then we calculate the contingency table.\index{binary features!contingency table}

\begin{table}[h]
\centering
\begin{tabular}{cccc}
\multicolumn{2}{c}{\multirow{2}{*}{}}       & \multicolumn{2}{c}{y} \\
\multicolumn{2}{c}{}                        & 1         & 0         \\ \cline{2-4}
\multirow{2}{*}{x} & \multicolumn{1}{c|}{1} & a         & b         \\
                   & \multicolumn{1}{c|}{0} & c         & d
\end{tabular}
\end{table}

\subsection*{Symmetric binary features}\index{binary features!symmetric}
Binary features are \textbf{symmetric} if both of their states equally valuable and carry the same weight; i.e. no
preference on which outcome should be coded as 1 or 0 , e.g. gender.

\begin{center}
	$$d(\mathbf{x}, \mathbf{y}) = \frac{b + c}{a + b + c + d}$$
\end{center}


\subsection*{Asymmetric binary features}\index{binary features!asymmetric}
Binary features are \textbf{asymmetric} if the outcomes of the states not equally important, e.g. the positive and negative
outcomes of a disease test; the rarest one is set to 1 and the other is 0. Since the number of negative matches are considered unimportant, they are omitted from the calculations.

\begin{center}
	$$d(\mathbf{x}, \mathbf{y}) = \frac{b + c}{a + b + c}$$
\end{center}

\section{Distance for nominal features}\index{nominal features!distance}
Nominal features are those that can take more than two states, for example {\textit{small, medium, large}}. There are two methods to handle variables with nominal features; simple mis-matching and converting them into binary variables.

\subsection*{Simple mis-matching}\index{nominal features!simple mismatching}
$$d(\mathbf{x}, \mathbf{y}) = \frac{\text{number of mis-matching features between \textbf{x} and \textbf{y}}}{\text{total number of features}}$$

\subsection*{Converting them into binary variables}\index{nominal features!converting into binary}
We create new binary features for all of its nominal states, for example if our size feature takes three possible nominal states \textit{{small, medium, large}} then this feature will be expanded into three binary features. \textit{{small, medium, large}} = {100, 010, 001}, then we can use the distance measures for binary features.

\subsection*{Worked Example}
Consider the example below where we have two toys, $T_1$ and $T_2$, whose features are size, colour and price range.
\begin{table}[h]
\centering
\begin{tabular}{c|c|c|c|}
\cline{2-4}
                         & Size & Colour & Price Range \\ \hline
\multicolumn{1}{|c|}{$T_1$} & 010  & 100    & 01       \\ \hline
\multicolumn{1}{|c|}{$T_2$} & 100  & 001    & 01      \\ \hline
\end{tabular}
\end{table}

\subsubsection*{Simple mis-matching}
Only the price range takes the same value for the features between $T_1$ and $T_2$ hence
$$d(\mathbf{T_1}, \mathbf{T_2}) = \frac{2}{3} \approx 0.66$$

\subsubsection*{Converting them into binary values}
Size: [Small, Medium, Large] = [100, 010, 000]\\
Colour: [Green, Red, Yellow] = [100, 010, 000]\\
Price: [Cheap, Expensive] = [10, 01]\\

\noindent
Now we do $T_1$ \textbf{XOR} $T_2$ = 01010001 \textbf{XOR} 10000101 = 11010100. Now from here we can get the distance by dividing the number of 1 bits in $T_1$ \textbf{XOR} $T_2$ by the total number of bits in $T_1$.
$$d(\mathbf{T_1}, \mathbf{T_2}) = \frac{4}{8} = 0.5$$

\section{Clustering methodologies}\index{clustering methodologies}
\begin{itemize}
	\item \textbf{Partitioning}: construct various partitions and then evaluate them by some criterion, e.g. minimising the sum of squares distance cost
	\item \textbf{Hierarchical}: create a hierarchical decomposition of the set of data using some criterion
	\item \textbf{Density-based}: based on connectivity and density functions
	\item Model-based: a generative model is hypothesised for each of the clusters and tries to find the best fir of that model to each other
	\item \textbf{Spectral clustering}: convert data set into a weighted graph then cut the graphs into sub-graphs corresponding to clusters via spectral analysis
	\item \textbf{Clustering ensemble}: combine multiple clustering results
\end{itemize}

%----------------------------------------------------------------------------------------
%	k-means Clustering
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{k-means Clustering}

\section*{Introduction}
The k-means algorithm is the simplest partitioning method for clustering analysis and is widely used in data mining algorithms. It is a \textbf{heuristic method} and is based on each clustering being represented by the centre of the cluster and the algorithm will converge to stable centroids\index{centroid} of clusters. The goal of this algorithm is find a partition of $k$ clusters to optimise the chosen partition criterion - the global optimum is achieved by exhaustively searching all partitions.

\section{Partitioning clustering approach}\index{partitioning clustering}
A partitioning clustering approach is done by iteratively partitioning the training data set to learn a partition of the given data space to product several non-empty clusters, where the number of clusters is usually given in advance. In principle, an optimal partition is achieved by minimising the sum of the squared distance to its "representative object" in each cluster.

\begin{exercise}
Why do we have to used the squared distance?
\end{exercise}

\section{k-means algorithm}
Before we can use the k-means algorithm, we must decide the cluster number \textit{k} and an appropriate distance measure that will be used. We initialise the algorithm by selecting \textit{k} distinct seed points, randomly.\\

\begin{enumerate}
	\item assign each object to the cluster of the nearest point
	\item compute new seed points as the centroids of the clusters of the current partition
\end{enumerate}

\ \\ \noindent
The two steps are repeated until it converges (membership in each cluster no longer changes). At this point, we have \textit{k} centroids which partition the whole data space into \textit{k} mutually exclusive subspaces to form a partition.\\

\begin{figure}[h]
	\centering
  	\includegraphics[width=50mm, scale=0.7]{Pictures/voronoi}
  	\caption{Voronoi Diagram}
\end{figure}

\noindent
The figure above shows how a data space can be partitioned, where each black dot represents a centroid of a cluster. Notice that the distance used above is Euclidean distance.

\section{Issues}

\begin{itemize}
	\item This algorithm has computational complexity of \textit{O}(tKn), where \textit{n} is the number of data points, \textit{K} is the number of clusters and \textit{t} is the number of iterations. Normally, \textit{K}, \textit{t} << \textit{n}.
	\item It is sensitive to initialisation, which may result to unwanted solutions
	\item Is unable to handle noisy data and outliers, which results in an inaccurate partition
	\item Requires prior knowledge of the cluster number
	\item Incapable of handling clusters of non-convex shape
	\item Inapplicable to categorical data, since the mean is not defined
	\item How do we evaluate the k-mean performance?
\end{itemize}

\subsection*{Example}
The k-Means algorithm is very simple, so an example has be omitted. An example may be added in the future, if I have spare time - but for now, just check the lecture slides.

%----------------------------------------------------------------------------------------
%	Hierarchical and Ensemble Clustering
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Hierarchical and Ensemble Clustering}

\section{Hierarchical clustering approach}
Hierarchical clustering approach\index{hierarchical clustering} is done by sequentially partitioning the data set to construct nested partitions layer by layer, via grouping objects into a tree of clusters. We use a generalised distance matrix as the clustering criteria and we do not need to know the number of clusters in advance.

\subsection*{Approaches to hierarchical clustering}\index{hierarchical clustering!approaches}
There are two main approaches to hierarchical clustering: \textbf{agglomerative clustering}\index{hierarchical clustering!agglomerative} (bottom-up) and \textbf{divisive clustering}\index{hierarchical clustering!divisive} (top-down). In agglomerative clustering, each data point is initially its own atomic cluster and we merge clusters into larger and larger clusters. Divisive clustering, as the name suggests, is where all data points belong to a single cluster initially, then the cluster is divided into smaller and smaller clusters.

\section{Cluster distance measures}\index{cluster distance measures}
\
\begin{definition}[Single link]\index{cluster distance measures!single link}
	The \textbf{smallest} distance between an element in one cluster and an element in another, i.e. $d(C_i, C_j) = \text{min}\{d(x_{ip}, x_{jq})\}$
\end{definition}

\begin{definition}[Complete link]\index{cluster distance measures!complete link}
	The \textbf{largest} distance between an element in one cluster and an element in another, i.e. $d(C_i, C_j) = \text{max}\{d(x_{ip}, x_{jq})\}$
\end{definition}

\begin{definition}[Average]\index{cluster distance measures!average}
	The \textbf{average} distance between elements in one cluster and elements in the other, i.e. $d(C_i, C_j) = \text{avg}\{d(x_{ip}, x_{jq})\}$
\end{definition}

\newpage
\section{Agglomerative clustering}
\subsection*{Algorithm}
\begin{enumerate}
	\item Select a cluster distance measure to use
	\item Convert all object features into a distance matrix
	\item Set each object as an atomic cluster (N objects means N clusters at start)
	\item Repeat until number of clusters is one (or known \# of clusters)
	\begin{itemize}
		\item Merge two closest clusters
		\item Update distance matrix
	\end{itemize}
\end{enumerate}

\subsection*{Example}
Again, very simple algorithm - so an example has been omitted as the lecture example is sufficient.\\

\begin{definition}[Lifetime]\index{lifetime}
	The distance between that a cluster is created and that it disappears (merges with other clusters during clustering).
\end{definition}

\begin{definition}[k-cluster lifetime]\index{k-cluster lifetime}
	The distance from that $K$ clusters emerge to that $K$ clusters vanish (due to the reduction to $K-1$ clusters).
\end{definition}

\section*{Relevant Issues}
\begin{itemize}
	\item How do we determine the number of clusters?
	\begin{itemize}
		\item If the number of clusters is known, then we have a termination condition
		\item We can use the \textbf{K-cluster lifetime} as a range of threshold values on the dendrogram that leads to the identification of $K$ clusters
		\item Heuristic method: cut the dendrogram tree with maximum life time to find a "proper" $K$
		\end{itemize}
	\item Major weakness of agglomerative clustering methods
	\begin{itemize}
		\item Can never undo what was done previously...
		\item Sensitive to cluster distance measures, noise and outliers
		\item Efficiency of $O(n^2\log n)$, where $n$ is the number of total objects
	\end{itemize}
\end{itemize}

\section{Ensemble Clustering}\index{ensemble clustering}
\textbf{Ensemble clustering} is concerned with the issues that may affect a single clustering algorithm, for example, sensitivity to initialisation, noise, outliers, distance metrics and it may be hard to choose a single algorithm which can handle all types of cluster shapes and sizes. The purpose of ensemble clustering is to utilise the results obtained by multiple clustering analyses for robustness.

\subsection*{Algorithm summary}
\begin{enumerate}
	\item Perform clustering analysis by using either different clustering algorithms or running a single clustering algorithm of different conditions, \textbf{leading to multiple partitions}
	\item Convert clustering results on different partitions into \textbf{binary distance measure}
	\item Evidence accumulation: form a \textbf{collective distance matrix} based on all the distance matrices
	\item Apply a hierarchical clustering algorithm (with a proper cluster distance measure) to collective distance matrix and \textbf{use the maximum $k$-cluster lifetime to decide}
\end{enumerate}

%----------------------------------------------------------------------------------------
%	Cluster Validation
%----------------------------------------------------------------------------------------

\chapterimage{chapter_head_2.pdf}

\chapter{Cluster Validation}
\section*{Introduction}
Cluster validation refers to the procedures that evaluate the results of clustering in a \textit{quantitive} and \textit{objective} fashion. In cluster validation, we need to compare clustering algorithms, solve the problem of determining the number of clusters, avoid finding patterns in noise and finding the "best" clusters from the data.\\

\noindent
We have two types of criteria, internal and external. An \textbf{internal criteria}\index{internal index} (index) is used to validate without external information and can be applied to find the "proper" number of clusters in a data set. An \textbf{external criteria}\index{external index} (index) may be applied to evaluate the performance of a clustering algorithm against data sets where the ground truth is available, by comparing how similar the partition generated by the clustering algorithm is to the ground truth.

\section{Internal Index}
The internal index we will focus on is the \textbf{F-ratio index}, which is a variance based internal index.

\subsection*{Variance-based methods}
In \textbf{variance-based methods}\index{variance-based methods}, the goal is to minimise the intra-cluster variance and to maximise the inter-cluster variance. Assume an algorithm leads to a partition of $K$ clusters where cluster $i$ has $n_i$ data points, $c_i$ is its centroid and $d(\cdot,\cdot)$ is a chosen distance measure.

$$ \text{Intra-cluster variance = } SSW(K) = \sum^K_{i=1}\sum^{n_i}_{j=1}d^2(\mathbf{x}_{ij}, \mathbf{c}_i)$$
$$ \text{Inter-cluster variance = } SSB(K) = \sum^K_{i=1}n_i \cdot d^2(\mathbf{c}_i, \mathbf{c})$$
$$ \text{where \textbf{c} is the global centroid of the whole data set} $$

\subsection{F-ratio index}
The \textbf{F-ratio index}\index{F-ratio index} is a measure of the inter-cluster variance against the intra-cluster variance. We calculate the F-ratio index for a partition of $K$ clusters as follows.
$$ F(K) = \frac{K \cdot SSW(K)}{SSB(K)} = \frac{K \cdot \sum^K_{i=1}\sum^{n_i}_{j=1}d^2(\mathbf{x}_{ij}, \mathbf{c}_i)}{\sum^K_{i=1}n_i \cdot d^2(\mathbf{c}_i, \mathbf{c})}$$

\noindent
It is ideal to have a low F-ratio index, so we run clustering algorithms for a range of values of $K$ (the number of clusters) and calculate a F-ratio index for each value of $K$ and each algorithm, then select the algorithm and value of $K$ which yields the lowest F-ratio index.

\section{External Index}
The external index we will focus on is the Rand Index, 1971.

\subsection{Issues with external indexes}
\begin{itemize}
	\item \textbf{cluster-ID permutation}: the cluster IDs in a partition from clustering have been assigned arbitrarily due to unsupervised learning
	\item \textbf{inconsistence in cluster numbers}: the number off clusters from algorithm may be different from the number of classes (in ground truth)
	\item \textbf{point-pair correspondence}: how do we find all possible correspondences between the ground truth and a partition?
\end{itemize}

\subsection{Rand Index}
The idea behind \textbf{Rand Index}\index{rand index} is to consider all pairs in the data set by looking into both \textit{agreement} and \textit{disagreement} against the ground truth.

\begin{table}[h]
\centering
\begin{tabular}{c|c|c|}
\cline{2-3}
\textbf{X/Y} & \begin{tabular}[c]{@{}c@{}}Pairs in the\\ same class\end{tabular} & \begin{tabular}[c]{@{}c@{}}Pairs in\\ different classes\end{tabular} \\ \hline
\multicolumn{1}{|c|}{\begin{tabular}[c]{@{}c@{}}Pairs in the\\ same cluster\end{tabular}} & $a$ & $b$ \\ \hline
\multicolumn{1}{|c|}{\begin{tabular}[c]{@{}c@{}}Pairs in \\ different clusters\end{tabular}} & $c$ & $d$ \\ \hline
\end{tabular}
\end{table}

\begin{definition}[Rand Index]\index{rand index}
Let \textbf{X} be the partition from clustering and \textbf{Y} be the ground truth. The Rand Index is defined as
\begin{equation*}
	\text{RI}(\mathbf{X},\mathbf{Y}) = \frac{a + d}{a + b + c + d}
\end{equation*}
\end{definition}

\noindent
To calculate $a, b, c, d$, we can use a contingency table as follows. $k$ denotes the number of clusters in \textbf{X}, $l$ denotes the number of classes in \textbf{Y} and each $n_{ij}$ denotes the number of points in both cluster $i$ and class $j$.

\begin{table}[h]
\centering
\begin{tabular}{llll|l}
$n_{11}$ & $n_{12}$ & $\cdots$ & $n_{1l}$ & $n_{1.}$ \\
$n_{21}$ & $n_{22}$ & $\cdots$ & $n_{2l}$ & $n_{2.}$ \\
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$ \\
$n_{k1}$ & $n_{k2}$ & $\cdots$ & $n_{kl}$ & $n_{k.}$ \\ \hline
$n_{.1}$ & $n_{.2}$ & $\cdots$ & $n_{.l}$ & $N$
\end{tabular}
\end{table}

\begin{multicols}{2}
$$ a = \frac{1}{2}\sum^{k}_{i=1}\sum^{l}_{j=1}n_{ij}(n_{ij} - 1) $$
$$ b = \frac{1}{2}(\sum^{l}_{j=1}n_{.j} - \sum^{k}_{i=1}\sum^{l}_{j=1}n_{ij}^2)$$

$$ c = \frac{1}{2}(\sum^{k}_{i=1}n_{i.} - \sum^{k}_{i=1}\sum^{l}_{j=1}n_{ij}^2)$$
$$ d = \frac{1}{2}(N^2 + \sum^{k}_{i=1}\sum^{l}_{j=1}n_{ij}^2 - (\sum^{k}_{i=1}n_{i.} + \sum^{l}_{j=1}n_{.j}))$$
\end{multicols}

\section{Weighted Clustering Ensemble}
\subsection*{Motivation}
The problem with the \textbf{clustering ensemble} algorithm is that it does not distinguish between \textit{non-trivial} and \textit{trivial} partitions so all partitions in clustering ensemble are treated \textbf{equally important}. This algorithm is also sensitive to the cluster distance used in the hierarchical clustering for reaching a consensus.

\subsection*{Solution}
With \textbf{weighted clustering ensemble}\index{weighted clustering ensemble}, multiple internal and external validity indexes reflecting various aspects are applied to different partitions obtained by initial clustering analysis. \textbf{Internal indexes} are used directly to measure the importance of a partition, quantitatively and objectively. \textbf{External indexes} are used indirectly to measure the importance of a partition via comparing with other partitions used in clustering ensemble for another round of \textit{evidence accumulation}.\\

\noindent
The values of these indexes are used as weights to highlight the non-trivial evidence and to diminish the trivial evidence simultaneously. Thus, the weighted clustering ensemble yield better yet robust performance in clustering analysis.

%----------------------------------------------------------------------------------------
%	INDEX
%----------------------------------------------------------------------------------------

\cleardoublepage
\phantomsection
\setlength{\columnsep}{0.75cm}
\addcontentsline{toc}{chapter}{\textcolor{ocre}{Index}}
\printindex

%----------------------------------------------------------------------------------------

\end{document}