The Higher Education and Research forge

Home My Page Projects Code Snippets Project Openings Complex Surface Machining Optimization
Summary Activity SCM

SCM Repository

authorMahfoud Herraz <mahfoud@debian>
Tue, 26 May 2020 14:13:35 +0000 (16:13 +0200)
committerMahfoud Herraz <mahfoud@debian>
Tue, 26 May 2020 14:13:35 +0000 (16:13 +0200)
Publis/JIM2020/v1.0/main.tex

index 13639e0..aa098ab 100644 (file)
@@ -90,7 +90,7 @@ In this section we present some unsupervised algorithms that will be used later
 
 \hl{TODO: justifier pourquoi cela... représentatifs d'une vaste éventail d'algo de clustering ?}
 
-\subsubsection{K-Means algorithm}
+\subsubsection{K-means algorithm}
 The K-means algorithm \ref{alg:Kmeans} is one of the most classical unsupervised classification algorithms. The theoretical framework of the algorithm, as well as its proof of convergence are presented in \cite{duda_pattern_2012}, which also suggests a way to choose an initial point (K-Means++), which consists in taking a random center among the points the second center is then chosen with a law of probability (the most probable point being the one that has a greater distance from the first center) and so on. A parallelizable version of the algorithm is proposed (K-Means$||$).
 
 \begin{algorithm}
@@ -625,16 +625,21 @@ A similar equation can be found for the covariance of two variables: Let $(x_i)_
 Hence, the covariance $\mbox{Cov}_{n-1}$ of variables $(x_i)_{1\leq i\leq n-1}$ et $(y_i)_{1\leq i\leq n-1}$ is written:
 \begin{equation}
  \begin{split}
-  \mbox{Cov}_{n-1}&=\frac{1}{n-1}\sum_{i=1}^{n-1}{x_iy_i} - \mbox{E}_{x,n-1}\mbox{E}_{y,n-1}=\frac{n}{n-1}\sum_{i=1}^{n}{\frac{x_iy_i}{n}} - \frac{x_ny_n}{n-1} - \mbox{E}_{x,n-1}\mbox{E}_{y,n-1} \\
-   &=\frac{n}{n-1}\left(\mbox{Cov}_n+\mbox{E}_{x,n}\mbox{E}_{y,n}\right)-\frac{x_ny_n}{n-1} - \left(\frac{n}{n-1}\mbox{E}_{x,n} - \frac{x_n}{n-1}\right)\left(\frac{n}{n-1}\mbox{E}_{y,n} - \frac{x_n}{n-1}\right)
+  \mbox{Cov}_{n-1}&=\frac{1}{n-1}\sum_{i=1}^{n-1}{x_iy_i} - \mbox{E}_{x,n-1}\mbox{E}_{y,n-1}\\
+  & =\frac{n}{n-1}\sum_{i=1}^{n}{\frac{x_iy_i}{n}} - \frac{x_ny_n}{n-1} - \mbox{E}_{x,n-1}\mbox{E}_{y,n-1} \\
+  & =\frac{n}{n-1}\left(\mbox{Cov}_n+\mbox{E}_{x,n}\mbox{E}_{y,n}\right)-\frac{x_ny_n}{n-1} \\
+  &- \left(\frac{n}{n-1}\mbox{E}_{x,n} - \frac{x_n}{n-1}\right)\left(\frac{n}{n-1}\mbox{E}_{y,n} - \frac{x_n}{n-1}\right)
  \end{split}
  \label{removecov}
 \end{equation}
 
 Using scalar equations \ref{removemean}, \ref{removevar} and \ref{removecov}, we can find a matrix equation to update the covariance matrix in the case of vectors samples. Let $p\in\mathbb{N}^*$ be the dimension of vectors, $n\geq2$ their number and $(\mathbf{X}_i)_{1\leq i\leq n}\in\left(\mathbb{R}^p\right)^n$ a sample of vectors of $\mathbb{R}^p$. $\mathbf{E}_n$ denotes the mean vector of the sample while $\Sigma_n$ denotes its covariance matrix. Thus, the covariance matrix of the reduced sample $\left(\mathbf{X}_i\right)_{1\leq i\leq n-1}$ is written:
 \begin{equation}
- \Sigma_{n-1}=\frac{n}{n-1}\left(\Sigma_n+\mathbf{E}_n\mathbf{E}_n^T\right)-\frac{\mathbf{X}_n\mathbf{X}_n^T}{n-1}-\left(\frac{n}{n-1}\mathbf{E}_n-\frac{\mathbf{X}_n}{n-1}\right)\left(\frac{n}{n-1}\mathbf{E}_n-\frac{\mathbf{X}_n}{n-1}\right)^T
- \label{removecovar}
+\begin{split}
+ \Sigma_{n-1}&=\frac{n}{n-1}\left(\Sigma_n+\mathbf{E}_n\mathbf{E}_n^T\right)-\frac{\mathbf{X}_n\mathbf{X}_n^T}{n-1} \\
+ &-\left(\frac{n}{n-1}\mathbf{E}_n-\frac{\mathbf{X}_n}{n-1}\right)\left(\frac{n}{n-1}\mathbf{E}_n-\frac{\mathbf{X}_n}{n-1}\right)^T
+\end{split}
+\label{removecovar}
 \end{equation}
 
 Equation \ref{removecovar} enables to update the covariance matrix $\Sigma_{n-1}$ of a zone containing initially $n$ meshes of feature-vectors $\left(\mathbf{X}_i\right)_{1\leq i\leq n}$ (and covariance matrix $\Sigma_n$), after removing the $n$-th mesh which feature-vector is $\mathbf{X}_n$.