% Lines starting with % are comments

% We tell that we write an article, [...] are options.
\documentclass[a4paper, 10pt]{article}

% We use some packages that provide useful commands
\usepackage[utf8]{inputenc}        % We tell latex that our .tex file is utf8 encoded
\usepackage[margin=3cm]{geometry}  % We set all margins to 3cm
\usepackage{graphicx}              % We will use the \includegraphics command to draw figures from files.
\usepackage{color}                 % We will set up custom colors
\usepackage{bbold}                 % We use a font for printing the real set (with double bars).

% This package (with all the options) sets smart hyper links in our document.
\usepackage[colorlinks=true, linkcolor=blue, anchorcolor=blue,
citecolor=blue, filecolor=blue, menucolor=blue, urlcolor=blue]{hyperref}

% These two packages enable the definition and rendering of algorithms.
\usepackage{algorithm}
\usepackage{algorithmic}
% This sets some customization of algorithm rendering. 
\floatname{algorithm}{Algorithm}
\definecolor{algocoul}{rgb}{0,0,0.75}
\definecolor{algocom}{rgb}{.75,.25,0}
\renewcommand{\algorithmiccomment}[1]{{\small \textcolor{algocom}{// #1}}}

% This sets the bibliography style
\usepackage{apalike}
\bibliographystyle{apalike}

% This sets the heading (title, author, ...)
\title{The online k-mean algorithm}
\author{Michel Choupauvert}
\date{\today}

% Now, until \end{document}, this describe our document/
\begin{document}

\maketitle        % We start with a title
\tableofcontents  % and then the table of contents.

\section{How does it work ?} % This is section 1.

This algorithm has been described in \cite{macqueen67}.            % \cite{xxx} cites a bibliographical reference. xxx is the reference key in the .bib file, @TYPE_OF_DOCUMENT{key,...
Let us recall it here step by step, in algorithm~\ref{algo:kmeans} % \ref{xxx} references something where \label{xxx} has been written.

% This describes our algorithm
\begin{algorithm}
\caption{$k$-means online\label{algo:kmeans}} % The use of \label{algo:kmeans} tells which number the previous \ref{algo:kmeans} expression is, i.e. the number of that algorithm.
\begin{algorithmic}[1]
\STATE Sample $W = \{w_1, \cdots w_k\}$ according to some sampling process (e.g a crow in $\mathbb{R}^2$ from a~$0.75$ to a~$0.99$ radius).
\WHILE {\TRUE}
\STATE Sample $\xi$ according to the sampling process.
\STATE Determine $w^\star = \displaystyle \mathop{\mathrm{argmin}}_{w \in W} \left\| w - \xi \right\|$. \COMMENT{Competition.}
\STATE \label{line:learn} Update $ w^\star \leftarrow  w^\star + \alpha(\xi - w^\star)$ \COMMENT{learning, $\alpha \in ]0,1]$, (e.g $\alpha = 0.01$).}
\ENDWHILE
\end{algorithmic}
\end{algorithm}

As illustrated in figure~\ref{fig:learning}, learning (i.e. line~\ref{line:learn} of algorithm~\ref{algo:kmeans}) consists in linearily adapting the best matching prototype.

% This is how we define floating figures (latex decides where they are placed).
% Note that the label definition is inside the caption.
\begin{figure}
  \centerline{\includegraphics[width=.8\textwidth]{fig-learn.pdf}}
  \caption{Learning consists of moving the prototype toward the sample. In our experiments, $\alpha = 0.01$ is used.\label{fig:learning}}
\end{figure}

Let us consider a simulated ramdom process from which samples are tossed. We use the one depicted in figure~\ref{fig:simulation}.
\begin{figure}
  \centerline{\includegraphics[width=.8\textwidth]{fig-simu.pdf}}
  \caption{Our simulation consists in randomly sampling points in a crown of radius $R=0.99$, with a hole of radius $r=0.75$. \label{fig:simulation}}
\end{figure}

We expect from k-means that the $k$ prototypes are ``equally'' placed in the sample distribution. Figure~\ref{fig:experiment} shows an experiment of the algorithm.

\begin{figure}
  \centerline{\includegraphics[width=.8\textwidth]{kmeans.pdf}}
  \caption{The k-means is obtained from $10000$ samples, after $20000$ iterations. On the figure, $k=5$ prototypes are used, displayed in orange. Crown dimensions are $R=0.99, r=0.75$.\label{fig:experiment}}
\end{figure}

Here, all the prototype share the distortion. The distortion of a prototype is defined by equation~\ref{eq:disto}.

\begin{equation}
  \mathrm{disto}(w) = \frac 1{\left|S_w \right|} \sum_{\xi \in S_w} \left\| \xi - w \right\| \mbox{ where } S_w = \left\{ \xi \in \mbox{dataset} \; \middle| \; \mathop{\mathrm{argmin}}_{w'\in W}  \left\| \xi - w' \right\| = w\right\}
  \label{eq:disto}
\end{equation}

Table~\ref{tab:disto} shows the distortion values.

% A table is a figure... but the caption starts with TAB rather than FIG.
% Inside our floating table, we have an equation. Inside the equation,
% we define an array.
\begin{table}
  \begin{equation}
    \begin{array}{|c|c|r|} % Tree columns where elements are centered, centered and right aligned, with bars on the left and right side, as well as inbetween.
      \hline % This draw an horizontal line
      \mbox{\bf Prototype} & \mbox{\bf Distortion} & \mbox{\bf Nb Samples} \\
      \hline
      \hline

      % data line #1, it is fake.
      (x,y) & 3.14 & 18 \\
      \hline
      
      % data line #2, it is fake.
      (a,b) & \sqrt 2 & 20 \\
      \hline

      
  \end{array}\nonumber
  \end{equation}
  \caption{Distortion values, see equation~\ref{eq:disto}. \label{tab:disto}}
\end{table}

\section{Conclusion}

It is very nice, even if a real k-mean algorithm, also known as LBG \cite{lbg}, is a better choice in real situations.


\bibliography{biblio}

\end{document}
