Aggiunto template presentazione

[SusiTM.git] / clustering.tex

\chapter{Clustering}

\section{Introduzione}
Il \emph{clustering} consiste nella suddivisione di oggetti in gruppi, detti \emph{cluster}, tali da minimizzare la variabilità interna (\emph{intra-cluster}) e massimizzare invece la variabilità rispetto agli altri gruppi (\emph{inter-cluster}). Diventa quindi ragionevole aspettarsi che i documenti assegnati allo stesso \emph{cluster} siano simili secondo determinati criteri. 
Questa tecnica consente di rendere l'insieme di documenti a disposizione più comprensibile, offrendo all'utente una interfaccia più intuitiva. Inoltre il \emph{clustering} se adottato in applicazioni di ricerca comporta un miglioramento della \emph{recall}; infatti se un determinato documento \texttt{d} risponde ad una particolare \emph{query} è possibile ritornare anche tutti i documenti presenti nel \emph{cluster} che contiene \texttt{d} arricchendo così il risultato della ricerca.


\section{Tecniche disponibili}
Esistono due approcci principali per il \emph{clustering}: analisi gerarchica e analisi non gerarchica. Le due tecniche si distinguono fondamentalmente per le relazioni che si vanno a creare tra i \emph{clusters} individuati. 

\subsection{Analisi gerarchica}
Questo approccio consente di individuare una gerarchia tra i \emph{clusters} presenti, e quindi ogni classe fa parte di una classe più ampia, fino alla classe che contiene l'intero insieme di entità analizzate. Si distinguono due algoritmi principali:
\begin{itemize}
\item agglomerativo: inizialmente ogni elemento (documento) costituisce un \emph{cluster} a sè stante, e man mano si procede fondendo gli elementi più vicini, fino ad arrivare ad un unico \emph{cluster} che li contenga tutti. Per applicare questo algoritmo è necessario fissare a priori la misura di similarità tra i documenti da utilizzare per la fusione.
\item divisivo: rappresenta la situazione opposta rispetto alla precedente. Infatti in questo caso, inizialmente tutti gli elementi fanno parte di un unico grande \emph{cluster}, che viene suddiviso ad ogni iterazione in due, sulla base di un misura, fino a raggiungere un numero minimo di elementi sotto il quale il \emph{cluster} non viene ulteriormente suddiviso.  Per applicare questo algoritmo è indispensabile definire una funzione per stabilire il \emph{cluster} da sudduvidere ad ogni passo.
\end{itemize}
Gli algoritmi gerarchici non richiedono di stabilire a priori il numero di gruppi da individuare; dal punto di vista computazionale però sono piuttosto onerosi e quindi poco efficienti. Altro elemento a sfavore è il fatto che queste tecniche sono particolarmente influenzate da eventuali valori anomali (\emph{outliers}). Nelle figure successive vengono messi in evidenza i due differenti approcci, l'algoritmo gerarchico agglomerativo e l'algoritmo gerarchico scissorio.

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Aggr.png}
\caption{Algoritmo agglomerativo}
\label{agg}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Sciss.png}
\caption{Algoritmo scissorio}
\label{sciss}
\end{center}
\end{figure}

Nella figura \ref{dend} è messo in evidenza un dendogramma. Esso viene utilizzato per fornire una rappresentazione grafica del processo di raggruppamento delle istanze nella procedura gerarchica.


\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Cluster1.jpg}
\caption{Esempio di dendogramma}
\label{dend}
\end{center}
\end{figure}
\pagebreak
\subsection{Algoritmo di clustering gerarchico agglomerativo}
L'algoritmo inizia assegnando ogni oggetto ad un \emph{cluster} distinto e procedendo in modo iterativo unendo ogni volta le coppie di \emph{clusters} più simili secondo determinati criteri. La procedura termina quando tutti gli oggetti sono stati uniti in un unico \emph{cluster}.\\ \\
\textbf{\emph{Initialization}}\\ \\
Ogni oggetto viene assegnato ad un \emph{cluster} distinto.\\ \\
\textbf{\emph{Iteration}} \\ \\
Si individua la coppia di \emph{clusters} più simili e li si unisce in uno unico.\\ \\
\textbf{\emph{Stopping condition}}\\ \\
Quando ogni oggetto viene unito in un unico \emph{cluster}.

\subsection{Analisi non gerarchica}
Gli algoritmi non gerarchici si distinguono per la tipologia di classi che vengono individuate. Il numero di \emph{clusters} generati deve essere noto a priori, o altrimenti è necessario impostare l'analisi in modo da ottenere soluzioni che prevedano un numero variabile di \emph{clusters}. A seconda che un elemento possa appartenere o meno a più classi simultaneamente si distinguono due tecniche:
\begin{itemize}
\item partizioni: le classi sono mutuamente esclusive, e quindi è possibile classificare un'entità in una sola classe;
\item classi sovrapposte: un elemento può appartenere a più di una classe.
\end{itemize}
Questi algoritmi si rivelano più efficienti computazionalmente, ed inoltre non sono influenzati in modo sostanziale dagli \emph{outliers}. Ad ogni iterazione di fondono i \emph{clusters} più ''vicini'' e si spacca il \emph{cluster} più disomogeneo. 


\subsection{K-means}
L'algoritmo K-Means partiziona una collezione di vettori ${\{x_{1},x_{2}\ldots x_{n}\}}$ in un insime di \emph{clusters} ${\{C_{1},C_{2}\ldots C_{k}\}}$. L'algoritmo necessita di K semi per iniziare. Questi possono essere forniti dall'esterno o scelti a caso tra i vettori a disposizione. \\
La procedura è la seguente:\\ \\
\textbf{\emph{Initialization}}\\ \\
I K semi, forniti o selezionati a caso, costituiscono il cuore dei \emph{clusters}. Ogni vettore viene assegnato al \emph{cluster} più vicino.\\ \\
\textbf{\emph{Iteration}} \\ \\
I centroidi ${M_{i}}$ dei \emph{clusters} correnti sono calcolati:
\[
M_{i} = |C_{i}^{-1}| \sum_{x \in C_{i}} x
\]
Ogni vettore è riasseganto al cluster con il centroide più vicino.\\ \\
\textbf{\emph{Stopping condition}}
\begin{itemize}
\item Basate su una \emph{loss function}.
\item Si raggiunge il numero fissato di iterazioni.
\item Le partizioni dei vettori sono rimaste invariate.
\item Le posizioni dei centroidi sono immutate. 
\end{itemize}
L'algoritmo K-means mira a massimizzare la funzione di qualità del clustering Q definita come:

\[
Q(C_{1}, C_{2}, \ldots C_{k}) = \sum_{i=1}^k\sum_{x \in C_{i}} Sim(x-M_{i})
\]

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{kmeans.png}
\caption{Esempio K-means con k=2}
\label{kmeans}
\end{center}
\end{figure}
\pagebreak
K-means è un noto algoritmo data la sua semplicità ed efficienza. La complessità di ogni iterazione è di \emph{O}(\emph{kn}) confronti di similarità, e il numero di iterazioni necessarie è di solito piuttosto ridotto.\\
Uno dei maggiori problemi dell'algoritmo è la sua sensibilità alla scelta iniziale dei semi. Se infatti viene fatta una cattiva scelta dei semi, i \emph{clusters} generati sono molto spesso sub-ottimi. Per ovviare al problema possono essere adottate varie strategie, e una di queste potrebbe essere eseguire la procedura con diversi insiemi di semi scelti in modo casuale. Un'alternativa potrebbe essere inoltre quella di scegliere i semi iniziali utilizzando delle informazioni dipendenti dal dominio esterno. Il miglior numero di \emph{cluster}, nel caso in cui non sia noto, può essere calcoltato facendo eseguire l'algoritmo con differenti valori di $k$ e scegliendo poi il migliore in base al valore della funzione di qualità $Q$. 


\section{Misure di similarità}
Si distinguono due diverse tipologie di misure, all'interno di un \emph{cluster} e fra \emph{clusters} distinti.
\subsection{Distanze \emph{intra-cluster}}
Esistono tre principali tipologie di distanza tra elementi all'interno di un \emph{cluster}, che sono:
\begin{itemize}
\item Distanza euclidea tra due punti $p$ e $q$ in $n$ dimensioni.
\[
D_{Euclidea}(p,q) = \sum_{k=1}^{n} (p_{k}-q_{k})^{2}
\]
\item Distanza di Manhattan tra due punti $p$ e $q$ in $n$ dimensioni.
\[
D_{Manhattan}(p,q) = \sum_{k=1}^{n} |p_{k}-q_{k}|
\]
\item Distanza di Lagrange-Chebishev tra due punti $p$ $q$ in $n$ dimensioni.
\[
D_{LC}(p,q) = \max_{k} \{|p_{k}-q_{k}| \} \] con k ${\in \{1, 2, \ldots n\}}$.
\end{itemize}
\subsection{Distanze \emph{inter-cluster}}
Per quanto riguarda la misura della distanza tra i \emph{clusters} a disposizione, è possibile ricorrere ad uno dei metodi proposti di seguito. Dati due \emph{clusters} A e B, la loro distanza può essere definita con:
\begin{itemize}
\item Metodo del legame singolo
\[
D(A,B) = min \{ d(a,b): a \in{A}, b \in{B}\}
\]
\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Single.png}
\caption{Rappresentazione distanza basata sul legame singolo}
\label{single}
\end{center}
\end{figure}


\item Metodo del legame completo:
\[
D(A,B) = max \{ d(a,b): a \in{A}, b \in{B}\}
\]

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Complete.png}
\caption{Rappresentazione distanza basata sul legame completo}
\label{complete}
\end{center}
\end{figure}

\item Metodo della media di gruppo:
\[
D(A,B) = \frac{1}{|A||B|} \sum_{a \in{A}} \sum_{b \in{B}} d(a,b)
\]

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Average.png}
\caption{Rappresentazione distanza basata sulla media di gruppo}
\label{average}
\end{center}
\end{figure}

\item Metodo del centroide:
\[
D(A,B) = d(c_{A}, c_{B}) \] in cui $c_{i}$ sta ad indicare il centroide del \emph{cluster} $i$-esimo

\begin{figure}[h]
\begin{center}
\includegraphics[width=120mm]{Centroid.png}
\caption{Rappresentazione distanza basata sui centroidi}
\label{centroid}
\end{center}
\end{figure}

\end{itemize}