text:
Provinces, Yukon score C- in flood disaster mitigation: report
By Ground Water Canada
Average scores of the 10 provinces and Yukon, according to a new University of Waterloo report. Intact Centre on Climate Adaptation
Waterloo, Ont. – The provinces and Yukon are not as prepared as they could be for floods, says a new report out of the Intact Centre on Climate Adaptation at the University of Waterloo.
The report, "Climate Change and the Preparedness of Canadian Provinces and Yukon to Limit Potential Flood Damage," surveyed 103 government representatives across 91 provincial and territorial ministries, departments and agencies between December 2015 and April 2016, the centre said in a news release. Assessments focused on the preparedness of provinces and Yukon to limit flood damage relative to current and future major rainfall events, across 12 categories of assessment, including flood-plain mapping, land-use planning, public health and safety, and emergency preparedness and response.
Using a scale from A (strong flood preparedness) to E (weak flood preparedness), the average score of the 10 provinces and Yukon is C-, suggesting there is considerable opportunity to limit future flood risk.
The report found the provinces and Yukon are doing relatively well in ensuring public health and safety by maintaining the capacity of hospitals and public health units to support the continuity of service delivery during floods. They also received high scores for emergency preparedness, as the provinces and Yukon work with local authorities and community leaders to identify and prepare for flood vulnerabilities.
Areas where the provinces and Yukon are not doing well include engagement with home and commercial property owners to identify and mitigate flood risks. Also, survey respondents often expressed frustration with municipalities that frequently override direction from the provinces to limit new development in flood-prone areas, thus putting homes and businesses at risk.
"The financial and social costs to Canadians will mount if preparedness to extreme weather events, and in particular flooding, continues to receive limited attention. Premiers are showing leadership on carbon pricing. Now, they need to build upon this commitment by embracing adaptation to address extreme weather and flooding with equal enthusiasm – this would be a strong position to lead with at COP 22 in Morocco," said Blair Feltmate, head of the Intact Centre and a professor in the School of Environment, Enterprise and Development at University of Waterloo, in the release.
Based on feedback from those surveyed, the report recommends the provinces and Yukon:
· create the position of chief adaptation officer (CAO), accountable to the premier, to identify areas of strength and weakness in reference to flood preparedness and actions to mitigate risk
· issue audited public reports that document the state of flood preparedness on a multi-year cycle, such as every five years
· rebuild infrastructure to meet new and future-projected flood risks where it is practically and actuarially cost effective to do so
· mandate the restriction of new development in flood-prone areas, or at a minimum, make development in such areas flood-resilient
Regarding the last recommendation, the report suggests that where development already exists in known flood-prone areas, the provinces and Yukon take action to limit potential flood damage and cautions that municipalities should not be able to override direction from the provinces or Yukon that restricts development in flood-prone areas or mandates flood-resilient design.
Federal government supports Ontario flood mitigation projects
Conserving wetlands could save Canadians millions in flood damage, report says
Ontario has leadership gap in flood-risk preparedness, study says
New Brunswick flood mitigation projects receive provincial, federal funding
flood preparedness
Intact Centre on Climate Adaptation
Solinst Canada Ltd.
Merrill Manufacturing Co.
Storm Lake, IA
Ancient water from N. Ontario mine self-sustaining, study suggests
Spinach plants engineered to detect explosives in ground water


text:
Privacy Policy for EmployAbility Service West Cork
At EmployAbility Service West Cork, accessible from empservice.org, one of our main priorities is the privacy of our visitors. This Privacy Policy document contains types of information that is collected and recorded by Employability Service West Cork and how we use it.
EmployAbility Service West Cork follows a standard procedure of using log files. These files log visitors when they visit websites. All hosting companies do this and a part of hosting services' analytics. The information collected by log files include internet protocol (IP) addresses, browser type, Internet Service Provider (ISP), date and time stamp, referring/exit pages, and possibly the number of clicks. These are not linked to any information that is personally identifiable. The purpose of the information is for analyzing trends, administering the site, tracking users' movement on the website, and gathering demographic information.
Like any other website, EmployAbility Service West Cork uses 'cookies'. These cookies are used to store information including visitors' preferences, and the pages on the website that the visitor accessed or visited. The information is used to optimize the users' experience by customizing our web page content based on visitors' browser type and/or other information.
Our Privacy Policy was created with the help of the Privacy Policy Generator and the Generate Privacy Policy Generator.
Third-party ad servers or ad networks uses technologies like cookies, JavaScript, or Web Beacons that are used in their respective advertisements and links that appear on Employability Service West Cork, which are sent directly to users' browser. They automatically receive your IP address when this occurs. These technologies are used to measure the effectiveness of their advertising campaigns and/or to personalize the advertising content that you see on websites that you visit.
Note that EmployAbility Service West Cork has no access to or control over these cookies that are used by third-party advertisers.
Employability Service West Cork's Privacy Policy does not apply to other advertisers or websites. Thus, we are advising you to consult the respective Privacy Policies of these third-party ad servers for more detailed information. It may include their practices and instructions about how to opt-out of certain options. You may find a complete list of these Privacy Policies and their links here: Privacy Policy Links.
EmployAbility Service West Cork does not knowingly collect any Personal Identifiable Information from children under the age of 13. If you think that your child provided this kind of information on our website, we strongly encourage you to contact us immediately and we will do our best efforts to promptly remove such information from our records.
This Privacy Policy applies only to our online activities and is valid for visitors to our website with regards to the information that they shared and/or collect in EmployAbility Service West Cork. This policy is not applicable to any information collected offline or via channels other than this website.
EmployAbility Services are funded by the Irish Government through the Department of Employment Affairs and Social Protection
Tá Seirbhísí Infhostaitheachta maoinithe ag Rialtas na hÉireann tríd an Roinn Gnóthaí Fostaíochta agus Coimirce Sóisialaí
Workstart West Cork Limited Trading as Employability Service West Cork CRO Number 382867 Patron: Lord David Puttnam
OnePage CRM sponsoring EmployAbility West Cork through the "Power of Action" Programme.
Site design by Marc Counsell
Microsoft Philanthropies is working to create a future where every person has the skills, knowledge, and opportunity to achieve more.
Martin Carey (Chair), Patrick Murphy, Gordon Teasdale, Dominic Cronin, Jill St. James-Hodnett, Gearoid O'Driscoll, Maria O'Donovan
© 2020 . Built using WordPress and the EmpowerWP Theme

redpajama_set_name: RedPajamaCommonCrawl


text:
\input{../../common/livre_begin.tex}%
\firstpassagedo{\input{space_metric_titre.tex}}
\input{../../common/livre_table_begin.tex}%
\firstpassagedo{\input{space_metric_chapter.tex}}

\newcommand{\initialisation}[0]{initialisation : \\}
\newcommand{\step}[0]{body : \newline}
\newcommand{\terminaison}[0]{termination : \\}
\newcommand{\for}[2]{for $#1$ to $#2$ do}
\newcommand{\forend}[0]{end for \\}
\newcommand{\while}[1]{while $\pa { #1 }$ do\\}
\newcommand{\whilenotl}[1]{while $\pa { #1 }$ do}
\newcommand{\whileend}[0]{end while}

\newenvironment{algopar}{}{}
\newcommand{\ind}[0]{\null \quad}

\label{space_metric_introduction}

\sloppy

Chercher des mots identiques ou similaires dans un dictionnaire est un problème classique et peut être défini pour tout espace métrique. \indexfr{dictionnaire}\indexfr{lexique}\indexfr{plus proches voisins}\indexfrr{distance}{édition} Soit $\pa{E,d}$ un espace métrique quelconque et $D \subset E$ un ensemble fini quelconque, $x \in E$ est un élément de $E$ et $s \in \R_+$ un réel positif. L'objectif est de trouver le sous-ensemble $D'\pa{x,s} \subset D$ des voisins les plus proches de $x$ tels que~:

    $$
    D'\pa{x,s} = \acc{  y \in D \sac d\pa{x,y} \infegal s}
    $$

Afin de déterminer les voisins de $x$, une méthode simple consiste à estimer toutes les distances entre $x$ et les éléments de $D$. Le coût de cette méthode est proportionnel au nombre d'éléments de $D$ et à la complexité du calcul de la distance. On distingue généralement deux directions afin d'améliorer la rapidité des algorithmes de recherche~:

    \begin{enumerate}
    \item L'optimisation du calcul de la distance.
    \item L'optimisation de la recherche des voisins.
    \end{enumerate}

Les méthodes présentées dans ce chapitre concerne la seconde direction, plus générale que la première.

%-------------------------------------------------------------------------------------------------------------
\section{Classification ascendante hiérarchique}
%-------------------------------------------------------------------------------------------------------------

Cette méthode reprend celle décrite dans l'article \citeindex{Dupré2003}.

\subsection{Arbre de partitionnement}
\label{section_partitionning_tree}
\indexfr{partitionnement}\indexfrr{arbre}{partitionnement}

L'objectif de cette partie est de construire un arbre de partitionnement qui sera utilisé ensuite afin d'améliorer la recherche des plus proches voisins au paragraphe~\ref{section_optimisation_distance}.

			\begin{xdefinition}{rayon et centre d'un ensemble discret}
			\indexfr{centre}\indexfr{rayon}
			\label{definition_center_radius}%
			Soit $D = \vecteur{y_1}{y_N} \subset E$ un ensemble fini de $E$, le centre $C\pa{D}$ de $D$
			est défini par~:
			    $$
			    C\pa{D} \in \underset {x \in D} {\arg \min} \cro{  \underset{y \in D} {\max} \; d\pa{x,y}}
			    $$
			où $d\pa{x,y}$ est la distance entre les éléments $x$ et $y$. On définit aussi le rayon $R\pa{D}$
			de $D$ par~:
			    $$
			    R\pa{D} = \underset{x \in D} {\max} \; d\pa{C\pa{D},y}
			    $$
			\end{xdefinition}

\begin{xremark}{cas particulier}
Si $A,B \subset D$ et $A \subset B$, cela n'implique pas que $R\pa{A} \infegal R\pa{B}$ comme le montre la
figure~\ref{figure_partition_inclusion} où $$R\pa{A} = d\pa{x,y} > d\pa{x,z} = R\pa{B}$$.
\end{xremark}

		\begin{figure}[ht]
    \[
    \unitlength 1mm
    \fbox{
    \filefig{../space_metric/fig_ray}
    }
    \]
    \caption{Exemple où ajouter un élément à un sous-ensemble aboutit à une réduction du rayon.}
    \label{figure_partition_inclusion}
		\end{figure}

		\begin{xproperty}{rayon d'un couple d'éléments}\label{property_001}%
		Soit $\pa{x,y} \in E^2$ deux éléments de $E$, alors $R\acc{x,y} = d\pa{x,y}$.\\
		\end{xproperty}

L'algorithme~\ref{algorithm_AHC}\footnote{
Autre formulation~:

			\begin{xalgorithm}{Arbre de partionnement}
			\label{algorithm_AHC_prime}%
			Soit $D= \vecteur{y_1}{y_N}$ un ensemble fini de $\pa{E,d}$. Soit $N\pa{n_1,n_2,C,R}$ un n\oe ud
			lié à ses deux précédesseurs $n_1,n_2$ et qui définit une partie dont le centre est $C$ et le rayon $R$.
			$L$ représente un ensemble de n\oe uds. Si $x$ est un n\oe ud, $P\pa{x}$ désigne la partie réunion
			de tous les centres des ancêtres de $x$.

			\begin{xalgostep}{initialisation}
			    Pour t$ y \in D$, on ajoute le n\oe ud$N\pa{ \emptyset,\emptyset,y,0}$ à $L$.
			\end{xalgostep}

			\begin{xalgostep}{recherche de la meilleure réunion}\label{space_metric_step_cah_cah_2}
			    Soit $\pa{x,y} \in \underset{ x,y \in L, \, x \neq y }
			    																{\arg \min} \; R\pa{ P\pa{x} \cup P\pa{y} }$.
			    Le n\oe ud \\
			    									$	z =		 N\pa{	x,y,
			    													C\pa{ P\pa{x} \cup P\pa{y} } ,
			    													R\pa{ P\pa{x} \cup P\pa{y} } }$ est créé et
			    $L \longleftarrow L \cup {z} - \acc{x,y}$
			\end{xalgostep}

			\begin{xalgostep}{terminaison}
					Si $L$ contient plus d'un n\oe ud, retour à l'étape~\ref{space_metric_step_cah_cah_2}.
			\end{xalgostep}
			\end{xalgorithm}
} est basé sur une classification ascendante hiérarchique (voir \citeindex{Saporta1990}, \citeindex{Reinert1979}),\indexfr{CAH} il construit une hiérarchie de partitions décrite par un graphe. \indexfr{n\oe ud}

			\begin{xalgorithm}{classification ascendante hiérarchique}\label{algorithm_AHC}%
			Soit $D= \vecteur{y_1}{y_N}$ un sous-ensemble fini de $\pa{E,d}$. On note $P_n$
			une partie contenant les éléments $P_n = \acc{p_{n,1} \; , ... , \; p_{n, \cro{card\pa{D}-n+1}}}$.
			L'algorithme a pour but de construire la suite de partitions $\pa{P_n}_{n \supegal 1}$ comme suit~:

			\begin{xalgostep}{initialisation}
			    $n = 1$ et $P_1$ est la partition où chaque élément de $D$ est un élément de $P_1$
			\end{xalgostep}

			\begin{xalgostep}{récurrence}\label{space_cah_algo_step}
			    \begin{xfor}{n}{1}{N-1}
			        soit $\pa{i^*_n,j^*_n} \in \underset{ i \neq j }{\arg \min} \; R\pa{p_{ni} \cup p_{nj} }$, alors
			        $P_{n+1} = \acc{ \pa{p_{nk}}_{k \neq i^*_n,j^*_n}, p_{ni^*} \cup p_{nj^*} }$
			    \end{xfor}
			\end{xalgostep}

			\end{xalgorithm}

La suite $\pa{P_n}_{1 \infegal n \infegal N}$ définit un graphe d'inclusion illustré par la
figure~\ref{figure_partition_inclusion_graph}) pour cinq éléments.\\

\begin{xremark}{plusieurs minima}
L'étape~\ref{space_cah_algo_step} impose de choisir un élément dans un ensemble de minima. Lorsque celui-ci contient plus d'un élément, une règle simple consiste à choisir le plus petit regroupement de deux parties parmi celles de rayon minimum. Cette règle a peu d'influence lorsque la construction de l'arbre s'effectue dans un espace continu. En revanche, pour un espace de mot muni d'une distance d'édition comme celle de Levenstein (voir~\citeindex{Levenstein1966}), ce cas se produit fréquemment puisque la distance est à valeurs entières. Cette règle accroît sensiblement les performances.
\end{xremark}

Chaque n\oe ud du graphe obtenu avec l'algorithme~\ref{algorithm_AHC} satisfait les conditions suivantes~:

\begin{enumerate}
\item Il n'a aucun prédécesseur\indexfr{prédécesseur} et la partie désignée par ce n\oe ud est un
        singleton\indexfr{singleton} dont le rayon est nul. \indexfr{rayon}
\item Il a deux prédécesseurs et la partie pointée par ce n\oe ud contient plus d'un élément, son rayon est strictement positif si au moins deux éléments sont différents.
\item Il n'a aucun successeur\indexfr{successeur} et la partie que le n\oe ud désigne est le sous-ensemble $D$.
\end{enumerate}

		\begin{figure}[ht]
    \[\frame{
    \filefig{../space_metric/fig_cah}
    }\]
    \caption{Graphe d'inclusion, la première partition contient une partie par élément de $D$ (les
                feuilles)\indexfr{feuille}, la seconde partition regroupe ensemble les plus
                proches éléments,
                la troisième partition regroupe ensemble les couples d'éléments les plus proches,
                la quatrième partition
                construit la partition de rayon minimum, le choix est entre
                $\acc{x_1,x_2,x_3}$, $\acc{x_1,x_4,x_5}$, $\acc{x_2,x_3,x_4,x_5}$, la cinquième partition est
                l'ensemble $D$ complet.}
    \label{figure_partition_inclusion_graph}
		\end{figure}

			\begin{xproperty}{nombre de n\oe uds}\label{property_node}
			L'arbre construit par l'algorithme~\ref{algorithm_AHC} contient exactement $2N-1 = 2 * card\pa{D}-1$
			n\oe uds.
			\end{xproperty}

\begin{xdemo}{propriété}{\ref{property_node}}
L'arbre construit par l'algorithme~\ref{algorithm_AHC} contient $N$ n\oe uds sans prédécesseur,
\indexfr{prédécesseur} soit un n\oe ud par mot de $D$. A chaque itération, un n\oe ud est créé pour
assembler deux parties entre elles. $N-1$ itérations sont nécessaires pour passer de $N$ parties à une seule. Donc, le nombre de n\oe ud de l'arbre est~:
    $$
    N + \pa{N-1} = 2N-1
    $$
\end{xdemo}

Le théorème~\ref{theorem_hierarchy} montre que l'arbre construit par l'algorithme~\ref{algorithm_AHC} peut être
considéré comme une hiérarchie pour un certain indice défini par le théorème.

			\begin{xtheorem}{hiérarchie}\label{theorem_hierarchy}
			\indexfr{hiérarchie}
			Soit $\pa{P_n}_{1 \infegal n \infegal N}$ la suite construite par l'algorithme~\ref{algorithm_AHC}.
			Soit $i\pa{P_n}$ défini par~:
			    $$
			    i\pa{P_n} = \underset{p \in P_n} {\max} \, R\pa{p}
			    $$
			Alors, la suite $\pa{i\pa{P_n}}_{1 \infegal n \infegal N}$ est croissante.
			\indexfrr{suite}{croissante}
			\end{xtheorem}

\begin{xdemo}{théorème}{\ref{theorem_hierarchy}}

Afin que la démonstration soit plus claire, les partitions notées~:
    $$
    \pa{P_{ni}}_{  \begin{subarray}{l} 1 \infegal n \infegal N \\ 1 \infegal i \infegal N-n+1 \end{subarray}  }%
    \text{ avec } \forall \pa{n,i}, \; P_{ni} \neq \emptyset
    $$
sont maintenant notées~:
    $$
    \pa{P_{ni}}_{\begin{subarray}{l} 1 \infegal n \infegal N \\ 1 \infegal i \infegal N \end{subarray}} %
    \text{ avec } \forall n, \; card \acc{ i | P_{ni} = \emptyset } = N-n+1
    $$

Donc~:
    \begin{eqnarray*}
    P_1 = \vecteur{P_1^1}{P_1^N}        &=&     \vecteur{\acc{y_1}}{\acc{y_N}} \text{ et }
    P_k                     =     \vecteur{P_k^1}{P_k^N}
    \end{eqnarray*}

Selon l'algorithme~\ref{algorithm_AHC}, $\exists \pa{a_{k+1},b_{k+1}} \in \intervalle{1}{N}^2$ tel que $a_{k+1}                 <         b_{k+1}$ et~:
		$$
    \begin{array}{l}
    P_{k+1}^{a_{k+1}}       =         P_{k}^{a_{k+1}} \cup P_{k}^{b_{k+1}} \; , \quad
    P_{k+1}^{b_{k+1}}       =         \emptyset  \; , \quad
    P_k^{a_{k+1}}           \neq      \emptyset  \; , \quad
    P_k^{b_{k+1}}           \neq      \emptyset \\
    \text{ et } \forall i \notin \acc{a_{k+1},b_{k+1}}, \, P_{k+1}^{i} = P_k^i
    \end{array}
    $$

Soit $R_k^i = R \pa{P_k^i}$ et $C_k^i = C \pa{P^k_i}$. On impose aussi que si $P^k_i = \emptyset$ alors $R_k^i = 0$. Si l'assertion (\ref{equation_1}) est vraie alors le théorème~\ref{theorem_hierarchy} le sera aussi~:
    \begin{eqnarray}
    \forall k \in \intervalle{1}{N-1}, \, \forall i \in \intervalle{1}{N}, \, R_{k+1}^{a_{k+1}} \supegal R_{k}^i
    \label{equation_1}
    \end{eqnarray}

Cette démonstratin s'effectue par récurrence. L'assertion (\ref{equation_1}) est vraie de manière évidente pour $k=2$ puisque~:

    $$
    \forall i \in \intervalle{1}{N}, \, R_{1}^i = 0
    $$

Donc, on suppose (\ref{equation_1}) est pour tout $k < N$, on cherche à montrer que (\ref{equation_1}) est aussi vraie pour $k+1$.

\itemdemo
\quad
\para{$1^\circ$ cas : $\acc{a_k,b_k} \bigcap \acc{a_{k+1},b_{k+1}} = \emptyset$}

On a :

    $$
    \acc{a_k,b_k} \bigcap \acc{a_{k+1},b_{k+1}} = \emptyset \Longrightarrow P_{k+1}^{a_{k}} = P_{k}^{a_{k}}
    $$

Donc :

    \begin{eqnarray}
    \forall i \in \intervalle{1}{N}, \, &&
    						 i \notin \acc{a_k,b_k} \Longrightarrow R_k^{a_k} \supegal R_{k-1}^{i} = R_{k}^{i}
    						  \label{equation_2}
    \end{eqnarray}

Mais l'algorithme~\ref{theorem_hierarchy} implique que~:

    \begin{eqnarray*}
    \acc{a_k,b_k} &\in& \underset{  \begin{subarray}{c} i < j \\ P_{k-1}^i \neq \emptyset \\ P_{k-1}^j \neq
    \emptyset\end{subarray} }
            {\arg \min} \, R\pa{P_{k-1}^i \bigcup P_{k-1}^j} \text{ et }
    \acc{a_{k+1},b_{k+1}} \in \underset{  \begin{subarray}{c} i < j \\ P_{k}^i \neq \emptyset \\ P_{k}^j \neq
    \emptyset\end{subarray} }
            {\arg \min} \, R\pa{P_{k}^i \bigcup P_{k}^j}
    \end{eqnarray*}

Par conséquent, $\acc{a_k,b_k} \bigcap \acc{a_{k+1},b_{k+1}} = \emptyset$ implique que~:

    \begin{eqnarray*}
    \acc{a_{k+1},b_{k+1}} \in \underset{  \begin{subarray}{c} i < j \\ i \neq a_k, j\neq b_k\\
        P_{k}^i \neq \emptyset \\ P_{k}^j \neq \emptyset\end{subarray} }
        {\arg \min} \, R\pa{P_{k}^i \bigcup P_{k}^j}
    &\Longrightarrow& \acc{a_{k+1},b_{k+1}} \in \underset{  \begin{subarray}{c} i < j \\ i \neq a_k, j\neq b_k\\
        P_{k-1}^i \neq \emptyset \\ P_{k-1}^j \neq \emptyset\end{subarray} }
        {\arg \min} \, R\pa{P_{k-1}^i \bigcup P_{k-1}^j}\\
    &\Longrightarrow& R\pa{P_k^{a_{k-1}} \bigcup P_k^{b_{k-1}}}   \infegal R\pa{P_k^{a_{k+1}} \bigcup P_k^{b_{k+1}}} \\
    &\Longrightarrow& R\pa{ P_k^{a_{k}} }   \infegal R\pa{ P_{k+1}^{a_{k+1}} }
    \end{eqnarray*}

D'où~:
    \begin{eqnarray}
    \forall i \in \intervalle{1}{N}, \, R_{k+1}^{a_k} \supegal R_{k}^{i} \label{equation_reca_1}
    \end{eqnarray}

\itemdemo
\quad
\para{$2^\circ$ cas : $\acc{a_k,b_k} \bigcap \acc{a_{k+1},b_{k+1}} \neq \emptyset$}

Si $\acc{a_k,b_k} \bigcap \acc{a_{k+1},b_{k+1}} \neq \emptyset$, alors $a_{k+1} = a_k$ or $b_{k+1} = a_k$. Pour ces deux cas, la preuve est la même donc on suppose que $a_{k+1} = a_k$, alors :
    $$
    \forall i \in \intervalle{1}{N}, \, R_k^{a_k} \supegal R_{k}^{i} \quad \text{ (voir (\ref{equation_2}))}
    $$

Comme $a_{k+1} = a_k$, il suffit de prouver que~:
    $$
    R_{k+1}^{a_{k}} \supegal R_{k}^{a_{k}}
    $$

Mais :

    \begin{eqnarray*}
    P_{k+1}^{a_{k+1}}   &=&     P_{k}^{a_{k+1}} \bigcup P_{k}^{b_{k+1}}
                        =     P_{k-1}^{a_{k}} \bigcup P_{k-1}^{b_{k}} \bigcup P_{k}^{b_{k+1}}
    \end{eqnarray*}

Deux cas sont possibles~:

\begin{enumerate}
\item si $C_{k+1}^{a_k} \in P_{k}^{a_{k}}$, alors :
    \begin{eqnarray}
    R_k^{a_k}   &=&         \underset{y \in P_{k}^{a_{k}}}{\max} \, d\pa{C_{k}^{a_k},y} %\nonumber\\
                \infegal  \underset{y \in P_{k}^{a_{k}}}{\max} \, d\pa{C_{k+1}^{a_k},y}
                \infegal  \underset{y \in P_{k+1}^{a_{k}}}{\max} \, d\pa{C_{k+1}^{a_k},y} %\nonumber\\
                \infegal  R_{k+1}^{a_k} \label{equation_reca_2}
    \end{eqnarray}
\item si $C_{k+1}^{a_k} \in P_{k}^{b_{k+1}}$, alors l'algorithm~\ref{algorithm_AHC} implique que~:
    \begin{eqnarray}
    R_{k+1}^{a_k}   &=&         \max \Bigg\{
    														\underset{y \in P_{k}^{a_{k}}}{\max} \, d\pa{C_{k+1}^{a_k},y} , %\nonumber\\
                    %&& \quad \quad \quad \quad
                                \underset{y \in P_{k}^{b_{k+1}}}{\max} \, d\pa{C_{k+1}^{a_k},y}
                                \Bigg \}\nonumber\\
                    &\supegal&  \max \acc{  \underset{y \in P_{k}^{a_{k}}}{\max} \,
                    											d\pa{C_{k+1}^{a_k},y} , R_k^{b_{k+1}} }\nonumber\\
                    &\supegal&  \max \Bigg\{  \underset{y \in P_{k-1}^{a_{k}}}{\max} \,
                    											d\pa{C_{k+1}^{a_k},y} ,
                                            \underset{y \in P_{k-1}^{b_{k}}}{\max} \, d\pa{C_{k+1}^{a_k},y} ,
                                            R_k^{b_{k+1}} \Bigg\}\nonumber\\
                    &\supegal&  \max \acc{  R_k^{a_{k}}  , R_k^{b_{k}} , R_k^{b_{k+1}} }\nonumber\\
                    &\supegal&  R_k^{a_{k}}  \label{equation_reca_3}
    \end{eqnarray}
\end{enumerate}

En conclusion, la récurrence est démontrée par les inégalités (\ref{equation_reca_1}), (\ref{equation_reca_2}),
(\ref{equation_reca_3}). Par conséquent, la suite d'indices $\pa{i\pa{P_n}}_{1 \infegal n \infegal N}$ est croissante.

\end{xdemo}

			\begin{xcorollary}{majoration du rayon}\label{corollary_AHC}%
			Soit $D$ un sous-ensemble fini de $E$ et $A$ l'arbre obtenu grâce à l'algorithme~\ref{algorithm_AHC},
			soit $n$ un n\oe ud quelconque de cet arbre, alors~:\indexfr{successeur}
			    \begin{eqnarray}
			    \textnormal{le successeur } s\pa{n} \text { de } n\; { existe}
			    \Longrightarrow R\pa{n} \infegal R\pa{s\pa{n}}
			    \end{eqnarray}
			\end{xcorollary}

Finalement, si $p_1$ et $p_2$ sont deux partitions de l'arbre de partitionnement, et $p_1 \subset p_2$, alors
$R\pa{p_1} \infegal R\pa{p_2}$. Cette conclusion n'était pas évidente d'après le cas particulier de la figure~\ref{figure_partition_inclusion}.

L'objectif de cet algorithme est de grouper ensemble les éléments ou les parties les plus proches à chaque itération. La conséquence attendue est que le voisinage d'un mot soit concentré dans une branche de l'arbre. Néanmoins, le principal inconvénient de cet algorithme est son coût. Si on suppose que le coût de la distance est approchée par une constante $c$ et que l'ensemble à hiérarchiser contient $n$~éléments, le coût de l'algorithme est en $O\pa{c\,n^5}$. Ce coût peut être réduit en factorisant les calculs d'une itération à l'autre puisque la liste $L$ conserve $n-k-1$ n\oe uds inchangés. Cette remarque permet de ne calculer le centre et le rayon que pour les parties nouvellement créées. De la même manière, il est possible de conserver pour chaque n\oe ud, le meilleur voisin qui, à l'itération suivante, peut être resté le même ou être la partie qui vient d'être réunie. Finalement, il est possible de faire descendre le coût de l'algorithme à $O\pa{c \, n^3}$.

Toutefois, pour des ensembles de plusieurs milliers d'éléments, l'algorithme~\ref{algorithm_AHC} demeure très long. Une optimisation consiste à adapter l'algorithme des centres mobiles\seeannex{emission_continue_centre_mobile}{centres mobiles}. L'algorithme s'inspire de l'algorithme~\ref{algo_centre_mobile} en remplaçant toutefois la notion de barycentre d'une partie par son centre (définition~\ref{definition_center_radius}) et l'inertie d'une partie par son rayon.

\subsection{Ajouter un élément au graphe}
\label{section_alternative}

L'algorithme~\ref{algorithm_AHC} ne permet d'insérer de nouveaux n\oe uds une fois que celui-ci est construit, inconvénient auquel remédie l'algorithme~\ref{algorithm_insertion}. Ce dernier ajoute des n\oe uds au graphe de partitionnement et pourrait être également utilisé pour construire l'arbre entier en insérant un à un tous les éléments de $D$ mais cette méthode est moins efficace.

		\begin{xalgorithm}{insertion d'un n\oe ud}\label{algorithm_insertion}

		Soit $D$ un sous-ensemble fini de $E$ et $A$ un arbre binaire, soit $n$ un n\oe quelconque de $A$, alors~:
		    \begin{enumerate}
		    \item $n$ définit une partie notée $P\pa{n}$ dont le rayon est $R\pa{n}$ et
		    				dont le centre est $C\pa{n}$.
		    \item $n$ n'a pas de prédécesseur\indexfr{prédécesseur} si $P\pa{n}$ est
		    				un singleton ou deux predecessors
		            sinon. Dans ce second cas, $P\pa{n}$ est la réunion des parties de deux prédécesseurs~:
		             $Pr\pa{n} = \acc{ p_1\pa{n} , p_2\pa{n}}$
		    \item $n$ n'a pas de successeur\indexfr{successeur} et il définit la partiet $D$
		    						ou un successeur noté $Su\pa{n} = s\pa{n}$
		    \end{enumerate}

		Le seul n\oe ud sans successeur est appelé \emph{racine}.\indexfr{racine} et noté $r$.
		Soit $m$ un élément et $x$
		le n\oe ud associé, alors $P\pa{x} = \acc{m}$, $C\pa{x} = m$, $R\pa{x} = 0$, et $x$ n'a
		pour le moment aucun succeseur
		et aucun prédécesseur. $N$ définit un ensemble de n\oe ud, le n\oe ud $x$ est inséré dans l'arbre $A$
		selon les règles suivantes~:

		\begin{xalgostep}{intialisation}
		    $N \longleftarrow \acc{r}$
		\end{xalgostep}

		%\possiblecut

		\begin{xalgostep}{insertion}
		    \begin{xwhile}{non fin}

		        \begin{xif}{$
		                    \begin{array}{l} d\pa{m,C\pa{n}} > R\pa{n}
		                    \hspace{10cm}
		                    \refstepcounter{equation}(\theequation)
		                    \label{amelioration_insertion_1}
		                    \end{array}
		                    $}

		            \begin{enumerate}
		            \item soit $ n\in \arg \min \acc{ d\pa{m,C\pa{n'}} \;|\; n' \in N}$, le n\oe ud $y$ est créé
		            \item le successeur de $y$ devient : $s\pa{y} \longleftarrow s\pa{n}$
		            \item le prédécesseur de $y$ devient : $p_1\pa{y} \longleftarrow x$
		            									and $p_2\pa{y} \longleftarrow n$
		            \item si le successeur de $n$ existe alors :
		                $$
		                \exists i \in \acc{1,2} \text{ tel que } p_i\pa{s\pa{n}} = n \text{ et }
		                					p_i\pa{s\pa{n}} \longleftarrow  p_i\pa{s\pa{n}} = y
		                $$
		            \item le successeur de $n$ devient : $s\pa{n} \longleftarrow y$
		            \item le successeur de $x$ devient : $s\pa{x} \longleftarrow y$
		            \item si $r = n$, alors $r \longleftarrow y$
		            \item le centre et le rayon sont reestimés pour toutes les parties définies par
		                    les éléments $\pa{n_1,...}$ de la suite the serie :
		                            $$
		                            n_0 = n \textnormal{ et pour } k \supegal 0, \;
		                                                n_{k+1} = \left\{
		                                                            \begin{array}{l}
		                                                            s\pa{n_k} \textnormal{ si } r \neq n_k \\
		                                                            r \textnormal{ sinon }
		                                                            \end{array}
		                                                            \right.
		                            $$
		            \item fin
		            \end{enumerate}

		        \xelse
		            $$
		            \begin{array}{lr}
		            \exists n \in N \text{ tel que } d\pa{m,C\pa{n}} \infegal R\pa{n} &
		                                        \hspace{6.5cm}\refstepcounter{equation}(\theequation)
		                                         \label{amelioration_insertion_2} \\
		            \text{et } N \longleftarrow \acc{N - \acc{n} } \cup \acc{p_1\pa{n},p_2\pa{n}} &
		            \end{array}
		            $$
		        \end{xif}
		    \end{xwhile}
		\end{xalgostep}
		\end{xalgorithm}

\begin{xremark}{hiérarchie}
Il n'est pas démontré que l'arbre obtenu après une ou plusieurs applications de l'algorithme~\ref{algorithm_insertion} vérifie le corollaire~\ref{corollary_AHC}. \indexfr{hiérarchie}
\end{xremark}

		\begin{figure}[ht]
    \[
    \begin{tabular}{|c|c|}
        \hline
        \filefig{../space_metric/fig_try1}
        &
        \filefig{../space_metric/fig_try2}
        \\
        \hline
        insertion de $x,y,z$ &   insertion de $y,z,x$ \\
        \hline
    \end{tabular}
    \]
    \caption{Graphe d'inclusion pour deux ordres différents d'inclusion, le second est bien sûr meilleur.}
    \label{partition_inclusion_graphe_ordre_insertion}
		\end{figure}

\begin{xremark}{ordre d'insertion}
L'arbre final dépend de l'ordre d'insertion des éléments comme le montre la \indexfrr{ordre}{insertion}
figure~\ref{partition_inclusion_graphe_ordre_insertion}. L'algorithme~\ref{algorithm_insertion} peut être amélioré et devenir l'algorithme~$\ref{algorithm_insertion}^*$ en remplaçant les lignes (\ref{amelioration_insertion_1}) et (\ref{amelioration_insertion_2}) par les suivantes, respectivement (\ref{amelioration_insertion_1_p}) et (\ref{amelioration_insertion_2_p})~:

    \begin{eqnarray}
    \text{si }      && \forall n \in N, \; d\pa{m,ArgC\pa{n}} > R\pa{n} \label{amelioration_insertion_1_p} \\
    \text{sinon }   && \exists n \in N \text{ tel que } d\pa{m,ArgC\pa{n}} \infegal R\pa{n}
    \label{amelioration_insertion_2_p}
    \end{eqnarray}

où~:

    \begin{eqnarray*}
    ArgC\pa{n}            &=&     \underset{x \in P\pa{n}} {\arg \min}
    															\cro{  \underset{y \in P\pa{n}} {\max} \; d\pa{x,y}} \text{ et }
    d\pa{m,ArgC\pa{n}}    =     \underset{y \in ArgC\pa{n}} {\min } d\pa{m,y}
    \end{eqnarray*}

On ne considère pas seulement un centre mais l'ensemble des centres possibles, à égale distance de l'élément à insérer. Comme la distance de Levenstein\indexfr{Levenstein} est à valeurs entières, cet ensemble est rarement réduit à un singleton comme le montrera le paragraphe~\ref{section_test}. Cette version de l'algorithme~\ref{algorithm_insertion} est notée~$\ref{algorithm_insertion}^*$. La construction de l'arbre de partitionnement est effectuée par la répétition de l'algorithme~\ref{algorithm_insertion} ou~$\ref{algorithm_insertion}^*$ tant qu'il reste des éléments à classer.

\end{xremark}

\subsection{Optimisation de la recherche des plus proches voisins}
\label{section_optimisation_distance}

Cette optimisation de la recherche utilise un des arbres construits par l'algorithme~\ref{algorithm_AHC} ou la répétition de l'algorithme~\ref{algorithm_insertion} ou~\ref{algorithm_insertion}$^*$. Chaque n\oe ud définit une partie décrite par un centre et un rayon. Le problème à résoudre consiste ici à trouver pour un élément $m$ la liste $B\pa{s}$ des voisins inclus dans le sous-ensemble $D\vecteur{y_1}{y_N}$ vérifiant~:

            $$
            B\pa{s} = \acc{ x \in D \sachant d\pa{x,m} \infegal s }
            $$

Soit $P \subset E$ une partie dont le centre est $C\pa{P}$ et le rayon $R\pa{P}$, l'optimisation est basée sur les deux remarques suivantes~:

    \begin{eqnarray}
    d\pa{m,C\pa{P}} > s + R\pa{P} 				&\Longrightarrow&
    																			\forall w \in P, \; d\pa{m,w} > s
    												\Longrightarrow	B\pa{s} \cap P = \emptyset					\label{equation_un} 	\\
    d\pa{m,C\pa{P}} + R\pa{P} \infegal s 	&\Longrightarrow&
    																			\forall w \in P, \; d\pa{m,w} \infegal s
    																		\Longrightarrow	B\pa{s} \subset  P \label{equation_deux}
    \end{eqnarray}

		\begin{xalgorithm}{recherche rapide}\label{algorithm_optimisation}%
		Soit $r$ la racine de l'arbre $A$ obtenu par un des algorithmes~\ref{algorithm_AHC},
		\ref{algorithm_insertion_all},
		$\ref{algorithm_insertion}^*$. $N$ est un ensemble de n\oe uds. Soit $s \in \R_+$, $B\pa{s}$ est
		l'ensemble cherché, il est défini par $B\pa{s} = \acc{ x \in D \sachant d\pa{x,m} \infegal s }$.

		\begin{xalgostep}{initialisation}
		    $N \longleftarrow r$ \\
		    $B\pa{s} \longleftarrow \emptyset$
		\end{xalgostep}

		\begin{xalgostep}{suite}\label{space_algo_step_B}
		    \begin{xwhile}{$N \neq \emptyset$}
		        Soit $n \in N$ et $p$ la partie définie par $n$, $n$ est retiré de $N$ :
		        							$N \longleftarrow N \backslash n$
		        et~: \\
		        \begin{xif}{$d\pa{m, C\pa{p}} + R\pa{p}\infegal s $}
		            $B\pa{s} \longleftarrow B\pa{s} \bigcup p$

						\xelseif{$ d\pa{m, C\pa{p}} > s + R\pa{p} $}
								ne rien faire
		        \xelse
		            \begin{xif}{$p = \acc{ w \in D}$}
				            \begin{xif}{$d\pa{m, w} \infegal s$}
				                $B\pa{s} \longleftarrow B\pa{s} \bigcup \acc{w}$
				            \end{xif}
		            \xelse
		                $N \longleftarrow N \bigcup \acc{p_1\pa{n},p_2\pa{n}}$\\
		                où $\acc{p_1\pa{n},p_1\pa{n}}$ sont les deux prédécesseurs de $n$
		            \end{xif}
		        \end{xif}
		    \end{xwhile}
		\end{xalgostep}

		La liste $B\pa{s}$ contient tous les voisins de $m$ sans aucune approximation.
		\end{xalgorithm}

\begin{xremark}{mémorisation des distances}
Durant l'étape~\ref{space_algo_step_B} de l'algorithme~\ref{algorithm_optimisation}, il est nécessaire de calculer les distance entre l'élément $m$ et le centre de certaines parties. Ces centres appartiennent au sous-ensemble $D$ et plusieurs parties peuvent avoir le même centre si elles sont incluses les unes dans les autres. Si le calcul de la distance $d$ est coûteux, il est intéressant de conserver en mémoire les résultats du calcul des distances de $m$ aux centres visités. Cette mémorisation\indexfr{mémorisation} implique qu'il ne peut y avoir plus de $N$ calculs de distance si $N$ est le nombre d'éléments de $D$.
\end{xremark}

\subsection{Critère d'efficacité}
\label{section_criterion}

Quelque soit la méthode choisie pour construire l'arbre de partitionnement, l'algorithme~\ref{algorithm_optimisation} mène à la solution exacte. D'un autre côté, on peut se demander s'il existe des arbres meilleurs que d'autres lors de la recherche des plus proches voisins et s'il existe un arbre optimal. La première idée est de considérer que plus les parties définies par l'arbre sont petites, plus la recherche sera rapide. Selon cette idée, le critère (\ref{critere_optimalite}) essaye d'évaluer la pertinence\indexfr{pertinence}\indexfr{efficacité} d'un arbre $A$ construit à partir du sous-ensemble fini $D$~:

    \begin{eqnarray}
    Cr_1\pa{A}                            &=&  \left\{   \begin{array}{l}
                                                0 \text{ si } R\pa{D} = 0 \text{ ou }
                                                				card\pa{D} \infegal 1 \\ \\  \textnormal{sinon }
                                                \dfrac{\summyone{n \in A} R\pa{n}}{\pa{card\pa{D}-1} * R\pa{D}}
                                                \end{array}%
                                                \right.
                                                \label{critere_optimalite} \\
        \text{où }&& \nonumber\\
        card\pa{D}                      &&      \text{est le nombre d'éléments de } D           \nonumber   \\
        R\pa{D}                         &&      \text{est le rayon de } D                       \nonumber   \\
        n                               &&      \text{est un n\oe ud de } A                     \nonumber   \\
        R\pa{n}                         &&      \text{est le centre de la partie définie par } n    \nonumber
    \end{eqnarray}

Si l'arbre $A$ choisi est construit par l'algorithme~\ref{algorithm_AHC}, le corollaire~\ref{corollary_AHC} permet d'affirmer que si $n$ est un n\oe ud de $A$, alors $R\pa{n} \infegal R\pa{D}$. De plus, l'arbre contient au plus $card\pa{D}-1$ n\oe uds dont le rayon est strictement positif~:

    $$
    card  \acc{n \in A \; | \; R \pa{n} > 0} \infegal card\pa{D}-1
    $$

Par conséquent, l'arbre $A$ construit par l'algorithme~\ref{algorithm_AHC} satisfait~:

    \begin{eqnarray}
    R\pa{D} \infegal    \summyone{n \in A} R\pa{n} \infegal \pa{card\pa{D}-1} * R\pa{D}
    				 \label{inegalite_critere}
    \end{eqnarray}

L'inégalité (\ref{inegalite_critere}) explique l'expression du critère (\ref{critere_optimalite}) puisque~:
    \begin{eqnarray}
    R\pa{D} > 0 \Longrightarrow \dfrac{1}{card\pa{D}-1} \infegal    Cr_1\pa{A} \infegal 1  &&
             \label{inegalite_critere2}
    \end{eqnarray}

\begin{xremark}{limites}
Les deux limites de l'inégalité (\ref{inegalite_critere2}) sont atteintes pour un sous-ensemble $D$ ne contenant que deux éléments distincts. Pour un ensemble contenant plus de trois éléments, la propriété suivante répond partiellement à la question.
\end{xremark}

		\begin{xproperty}{limites} \label{property_bornes_atteintes}%
		Soit $\pa{E,d}$ un espace métrique quelconque,\indexfrr{espace}{métrique} soit $D \neq
		\emptyset$ un sous-ensemble fini de $E$, soit $A_D$ l'arbre construit par
		l'algorithme~\ref{algorithm_AHC}, alors les trois 		propositions suivantes sont vraies~:

		\begin{description}
		\item[(1) ] $\forall n > 1,$ il existe $D_1 \subset E$ tel que~:
		    $$
		    \left\{
		    \begin{array}{rcl}
		    card\pa{D_1} &=& n \\
		    Cr_1\pa{A_{D_1}} &=& \dfrac{1}{n-1}
		    \end{array}
		    \right.
		    $$
		\item[(2) ] $\forall n > 1,$ il existe $D_2 \subset E$ tel que~:
		    $$
		    \left\{
		    \begin{array}{l}
		    card\pa{D_2} = n \\ %\\
		    \forall \pa{x,y} \in D_2^2, \; x \neq y \Longrightarrow d\pa{x,y} = R\pa{D_2}
		    \end{array}
		    \right.
		    $$
		    alors $Cr_1\pa{A_{D_2}} = 1$. \newline
		\item[(3) ] si $E$ est un espace vectoriel de dimension infinie, alors, $\forall n > 1,$
									il existe $D_3 \subset E$ tel que~:
		    $$
		    \left\{
		    \begin{array}{rcl}
		    card\pa{D_3} &=& n \\
		    Cr_1\pa{A_{D_3}} &=& 1
		    \end{array}
		    \right.
		    $$
		\end{description}
		\end{xproperty}

\begin{xdemo}{propriété}{\ref{property_bornes_atteintes}}

Pour prouver \textbf{(1)}, il faut considérer l'ensemble $D_1 = \vecteur{x_1}{x_n}$ défini par~:

    $$
    \left\{
    \begin{array}{l}
    x_1 \neq x_2 \\
    \forall i \supegal 3, \, x_i = x_2
    \end{array}
    \right.
    $$

De manière évidente~: $Cr_1\pa{A_{D_1}} = \frac{1}{n-1}$.

Prouver \textbf{(2)} est aussi évident parce que si un tel ensemble $D_2$ existe, pour une partie $P$ quelconque de $D$, $R\pa{P} = R\pa{D_2} = Cr_1\pa{A}$.

Pour prouver \textbf{(3)}, on n'utilise \textbf{(2)} puisqu'un tel ensemble $D_2$ existe dans un espace vectoriel de dimension infinie. C'est précisément le cas de l'espace des mots.

\end{xdemo}

%-------------------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------------------
\comment{

Pour prendre en compte la pertinence de la réunion de deux parties, un second critère est défini~:

			\begin{eqnarray}
			Cr_2\pa{A}      &=&     \left\{\begin{array}{l}
      				                0 \text{ si } R\pa{D} = 0 \text{ ou } card\pa{D} \infegal 1 \\
                              \dfrac{ \summyone{n \in A} \biggcro{ 2 R\pa{n} - d\pa{n} }}
                              			{\pa{card\pa{D}-1} * R\pa{D}} \text{ sinon}
															\end{array}%
                              \right.
                              \label{critere_optimalite_2} \\
    		\text{où }&& \nonumber\\
    		p_i\pa{n}            &&      \text{est un des deux prédécesseurs du n\oe ud } n \\
    		\text{et }d\pa{n}    &=&     d\pa{C\pa{p_1\pa{n}}, C\pa{p_2\pa{n}}}  \nonumber\\
				\end{eqnarray}

De manière évidente, ce critère vérifie (\ref{inegalite_critere3})~:

    \begin{eqnarray}
    R\pa{D} > 0 \Longrightarrow 0 \infegal    Cr_2\pa{A} \infegal 2  && \label{inegalite_critere3}
    \end{eqnarray}

Ce second critère ne sera pas évoqué par la suite car il corrobore les déductions obtenus avec le premier critère.

}
%-------------------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------------------------------------

\subsection{Résultats expérimentaux}
\label{section_test}

La première expérience consiste à chercher les voisins dans un ensemble de points tirés aléatoirement dans le carré $\cro{0,1} \times \cro{0,1}$ (figure~\ref{space_metric_rnd_01_01}). L'expérience consiste d'abord à tirer $N$ points aléatoires dans ce carré. Pour différentes valeurs de seuil~$s$, $N$~points sont de nouveau tirés aléatoirement pour lesquels le voisinage $V_s\pa{x}=\acc{y \sac d\pa{x,y} \infegal s}$ est calculé selon les deux algorithmes~\ref{algorithm_AHC} et~$\ref{algorithm_insertion}^*$. Si $X$ est une variable aléatoire de l'espace métrique~$E$ -~les éléments de $E$ sont équiprobables~-, l'objectif est d'estimer le nombre moyen de calculs de distance $r_s\pa{N}$ effectués pour déterminer les voisins d'un élément~:

		    \begin{eqnarray}
		    r_s\pa{N} = \dfrac{1}{N} \; \esp{ \text{nombre de distances calculées pour $V_s\pa{X}$}}
		    \label{gain_mot}
		    \end{eqnarray}

				\begin{figure}[ht]
				$$
				\begin{array}{|c|}\hline
    		\includegraphics[height=3cm, width=3cm]{\filext{../space_metric/image/rnd}} \\ \hline
    		\end{array}
    		$$
    		\caption{Tirage aléatoire de points dans le carré $\cro{0,1} \times \cro{0,1}$.}
    		\label{space_metric_rnd_01_01}
    		\end{figure}

L'algorithme~\ref{algorithm_AHC} est de loin le meilleur et ce quelle que soit la valeur du seuil $s$ choisi. Cette supériorité est également traduite par la valeur de $Cr_1$ obtenu pour chacun des arbres (voir table~\ref{space_metric_rnd_gain}).

				\begin{table}[ht]
				\[
				\begin{tabular}{|c|c|c|c|c|c|} \hline
				seuil &   $\frac{\esp{\card{V_s\pa{X}}}}{N}$ &
								$\begin{subarray}{c} r_s\pa{N=2000} \\
								algorithme~\ref{algorithm_insertion}^* \end{subarray}$ 	&
								$\begin{subarray}{c} r_s\pa{N=2000} \\
								algorithme~\ref{algorithm_AHC} \end{subarray}$ 							&
								$\begin{subarray}{c} r_s\pa{N=5000} \\
								algorithme~\ref{algorithm_AHC} \end{subarray}$ 							&
								$\begin{subarray}{c} r_s\pa{N=10000} \\
								algorithme~\ref{algorithm_AHC} \end{subarray}$ 		\\ \hline
				0,001		&		0 \,\%   &  	6,4 \,\%   &  	1,2 \,\%  & 0,6  \,\% &  0,3 \,\% \\ %\hline
				0,01		&		0 \,\%   &  	6,8 \,\%   &  	1,4 \,\%  & 0,7  \,\% &  0,4 \,\% \\ %\hline
				0,1			&		2 \,\%   &  	11,8 \,\%  &  	4,1 \,\%  & 2,7  \,\% &  1,9 \,\% \\ %\hline
				0,2			&		10 \,\%  &  	17,2 \,\%  &  	6,8 \,\%  & 4,5  \,\% &  3,2 \,\% \\ %\hline
				0,3			&		21 \,\%  &  	21,7 \,\%  &  	8,7 \,\%  & 5,7  \,\% &  4,0 \,\% \\ %\hline
				0,4			&		34 \,\%  &  	25,1 \,\%  &  	9,6 \,\%  & 6,3  \,\% &  4,5 \,\% \\ %\hline
				0,5			&		48 \,\%  &  	26,9 \,\%  &  	10,0 \,\% & 6,5  \,\% &  4,6 \,\% \\ %\hline
				0,6			&		62 \,\%  &  	27,9 \,\%  &  	9,4 \,\%  & 6,1  \,\% &  4,4 \,\% \\ %\hline
				0,7			&		74 \,\%  &  	27,0 \,\%  &  	8,3 \,\%  & 5,4  \,\% &  3,9 \,\% \\ %\hline
				0,8			&		85 \,\%  &  	24,0 \,\%  &  	6,7 \,\%  & 4,3  \,\% &  3,1 \,\% \\ %\hline
				0,9			&		92 \,\%  &  	19,2 \,\%  &  	4,6 \,\%  & 3,0  \,\% &  2,1 \,\% \\ %\hline
				1				&		98 \,\%  &  	10,9 \,\%  &  	2,3 \,\%  & 1,4  \,\% &  1,0 \,\% \\ %\hline
				2				&		100 \,\% &  	0,1 \,\%   &  	0,1 \,\%  & 0,0  \,\% &  0,0 \,\% \\ \hline
				$Cr_1$	&   -     	 &   0,135			 &   0,039	 		& 0,023  		&  0,017   \\ \hline
						\begin{minipage}[c]{3cm}
						temps de calcul (arbre)
						\end{minipage}
								&  - &   $\sim$ 2 sec 					 & $\sim $30 sec& $\sim $2 min  &  $\sim $10 min   \\ \hline
				\end{tabular}
				\]
				\caption{	Gain apporté lors de la recherche du voisinage pour différentes valeurs de seuil.
									Le premier test utilise un nuage de 2000 points tirés
									aléatoirement dans l'ensemble $\cro{0,1}^2$, le second en utilise 5000,
									le dernier 10000. A seuil fixe,
									la part du voisinage observé décroît lorsque $N$ diminue. Dans les trois cas,
									lorsque le seuil est fixé, les rapports tailles de
									voisinages sur nombre d'éléments sont sensiblement égales quel que soit $N$.
									On s'aperçoit que le critère $Cr_1$ décroît également lorsque $N$ augmente.
									Les temps de calcul sont estimées avec un processeur Intel Pentium~III à 1~GHz et
									désignent le temps nécessaire à la construction de l'arbre.}
				\indexfr{Intel}
				\indexfr{Pentium}
				\indexfr{temps de calcul}
				\label{space_metric_rnd_gain}
				\end{table}

Une expérience similaire est effectuée dans un espace de mots et pour mesurer l'amélioration obtenu par l'optimisation décrite au paragraphe~\ref{section_optimisation_distance}, le test suivant est réalisé~:

		\begin{itemize}
    \item Un dictionnaire $D$ de 2178 prénoms\indexfr{prénom} est utilisé, son rayon est 10.
    \item Le test consiste en l'obtention du voisinage $V_s\pa{m}$ de n'importe quel mot $m$ du dictionnaire.
    \item La distance utilisée est cette de Levenstein (\citeindex{Levenstein1966},
        	\citeindex{Wagner1974}).\indexfr{Levenstein}
		\end{itemize}

Sans optimisation, pour un mot donné $m$, toutes les distances de $m$ avec les autres mots doivent être calculées. En utilisant l'optimisation proposée, il n'est pas nécessaire de les calculer toutes. Les résultats sont illustrés par le tableau~\ref{metric_test_optimisation}.

		\begin{table}[ht]
    %\newline
    $$
    \begin{tabular}{|c|c|cc|} \hline
    \textnormal{seuil} &    $\frac{\esp{\card{V_s\pa{X}}}}{N}$ &
    						$\begin{subarray}{c} r_s\pa{N=2178} \\ algorithme~\ref{algorithm_AHC} \end{subarray}$ &
                $\begin{subarray}{c} r_s\pa{N=2178} \\
                algorithme~\ref{algorithm_insertion}^* \end{subarray}$
                \\ \hline
								1				&	0,1 \,\%		&	17,3 \,\%	& 34,1	 \,\% \\
								2				&	0,3 \,\%		&	30,2 \,\%	& 46,9	 \,\% \\
								3				&	1,5 \,\%		&	45,7 \,\%	& 60,4	 \,\% \\
								4				&	7,0 \,\%		&	63,1 \,\%	& 73,3	 \,\% \\
								5				&	21,8 \,\%		&	76,3 \,\%	& 83,0	 \,\% \\
								6				&	45,2 \,\%		&	79,8 \,\%	& 86,0	 \,\% \\
								7				&	68,2 \,\%		&	74,0 \,\%	& 81,2	 \,\% \\
								8				&	82,8 \,\%		&	59,6 \,\%	& 71,1	 \,\% \\
								9				&	90,9 \,\%		&	45,2 \,\%	& 58,0	 \,\% \\
								10			&	95,5 \,\%		&	30,7 \,\%	& 43,5	 \,\% \\
								11			&	96,7 \,\%		&	21,0 \,\%	& 28,8	 \,\% \\
								12			&	98,5 \,\%		&	12,5 \,\%	& 18,3	 \,\% \\
								13			&	99,3 \,\%		&	7,7 \,\%	& 11,0	 \,\% \\
								14			&	99,4 \,\%		&	4,9 \,\%	& 7,3	 \,\% \\
								15			&	99,5 \,\%		&	3,0 \,\%	& 4,2	 \,\% \\
								16			&	99,5 \,\%		&	2,2 \,\%	& 2,7	 \,\% \\
								17			&	99,6 \,\%		&	1,5 \,\%	& 2,0	 \,\% \\
								18			&	99,8 \,\%		&	0,9 \,\%	& 1,5	 \,\% \\
								19			&	99,7 \,\%		&	0,9 \,\%	& 1,3	 \,\% \\
								20			&	99,9 \,\%		&	0,6 \,\%	& 1,2	 \,\% \\ \hline
                $Cr_1$ 	&  -					& 0,153  	&  0,221 \\ \hline
                		\begin{minipage}[c]{3cm}
                		temps de calcul (arbre)
                		\end{minipage}
                				& - 	& $\sim$5 min &  $\sim$1 h\\ \hline
    \end{tabular}
    $$
    \caption{	Amélioration moyenne mesurée par (\ref{gain_mot}), comparaison des
    					 algorithmes~\ref{algorithm_AHC},
    	 				$\ref{algorithm_insertion}^*$. Le centre du dictionnaire est
            	MARIE-LOUISE et son rayon est 17. Dans le pire des cas, $s=6$,
            	20\% des calculs de distances sont évités.
            	Les temps de calcul correspondand à la construction de l'arbre
            	sont estimés avec un processeur Intel Pentium 1~GHz.}
				\indexfr{Intel}
				\indexfr{Pentium}
				\indexfr{temps de calcul}
    \label{metric_test_optimisation}
		\end{table}

\begin{xremark}{ordre d'insertion}
L'ordre d'insertion des mots dans l'arbre affecte les résultats. En ce qui concerne les \indexfrr{ordre}{insertion}
algorithmes~\ref{algorithm_insertion} et~$\ref{algorithm_insertion}^*$, les mots ont été insérés par ordres croissant et décroissant de taille, les différences sont rendues par le tableau~\ref{test_optimisation_taille_2}.
\end{xremark}

		\begin{table}[ht]
   	%\newline
    $$
    \fbox{$
    \begin{array}{ccccc}
    \text{seuil} &  \begin{subarray}{c} r \textnormal{ moyen} \\ algorithme~\ref{algorithm_insertion}^* \\
                    \textnormal{longueurs décroissantes} \end{subarray} &
                    \begin{subarray}{c} r \textnormal{ moyen} \\ algorithme~\ref{algorithm_insertion}^* \\
                    \textnormal{longueurs croissantes} \end{subarray}
                    \\
    1            & 82,0 \,\% &    75,2 \,\%     \\
    2            & 65,8 \,\% &    60,6 \,\%     \\
    3            & 45,6 \,\% &    42,8 \,\%     \\
    4            & 26,7 \,\% &    25,5 \,\%     \\
    5            & 12,8 \,\% &    12,2 \,\%
    \end{array}
    $}
    $$
    \caption{Amélioration moyenne mesurée par (\ref{gain_mot}), comparaison des ordres d'insertion}
    \label{test_optimisation_taille_2}
		\end{table}

		\begin{table}[ht]
    %\newline
    $$
    \begin{tabular}{|c|cc|} \hline
    \textnormal{seuil} &    $\frac{\esp{\card{V_s\pa{X}}}}{N}$ &
    						$\begin{subarray}{c} r_s\pa{N=4987} \\ algorithme~\ref{algorithm_AHC} \end{subarray}$
                \\ \hline
								1		&	0,0	 		\,\%	&	5,7	 	\,\%	 \\
								2		&	0,0	 		\,\%	&	10,4	\,\%	 \\
								3		&	0,0	 		\,\%	&	17,1	\,\%	 \\
								4		&	0,1	 		\,\%	&	26,4	\,\%	 \\
								5		&	0,4	 		\,\%	&	42,2	\,\%	 \\
								6		&	2,0	 		\,\%	&	61,6	\,\%	 \\
								7		&	9,0	 		\,\%	&	82,1	\,\%	 \\
								8		&	34,1	 	\,\%	&	94,7	\,\%	 \\
								9		&	77,4	 	\,\%	&	91,3	\,\%	 \\
								10	&	97,7	 	\,\%	&	73,1	\,\%	 \\
								11	&	99,4	 	\,\%	&	48,4	\,\%	 \\
								12	&	99,9	 	\,\%	&	31,0	\,\%	 \\
								13	&	100,0	 	\,\%	&	20,1	\,\%	 \\
								14	&	100,0	 	\,\%	&	11,1	\,\%	 \\
								15	&	100,0	 	\,\%	&	6,0	 	\,\%	 \\
								16	&	100,0	 	\,\%	&	3,0	 	\,\%	 \\
								17	&	100,0	 	\,\%	&	1,3	 	\,\%	 \\
								18	&	100,0	 	\,\%	&	0,0	 	\,\%	 \\ \hline
                $Cr_1$ 	&  -					& 0,210  			  \\ \hline
                temps de calcul & - 	& $\sim$3 h   \\ \hline
                \end{tabular}
    $$
    \caption{	Amélioration moyenne mesurée par (\ref{gain_mot}), le test est effectué
    					sur un dictionnaire de 4987 mots anglais de centre "POSITIVELY" de rayon 13.
    					L'optimisation est plus pertinente dans ce cas où le dictionnaire
    					contient plus du double de mots que celui utilisé
    					pour le test~\ref{metric_test_optimisation}.
    					}
    \label{metric_test_optimisation_dicos}
		\end{table}

%-------------------------------------------------------------------------------------------------------------------
\section{Voisinage dans un espace vectoriel}
%-------------------------------------------------------------------------------------------------------------------

Lorsque l'espace métrique est aussi vectoriel, la recherche des plus proches voisins est facilité car il est possible d'utiliser les coordonnées des éléments comme dans l'algorithme \emph{Branch and Bound}. Ces coordonnées permettent également d'obtenir des résultats théorique plus avancés en ce qui concerne le coût de cette recherche (voir \citeindex{Arya1994}.

\subsection{B+ tree}
\indexfr{B+ tree}

Ce premier algorithme s'applique dans le cas réel afin d'ordonner des nombres dans un arbre de sorte que chaque n\oe ud ait un père et pas plus de $n$ fils (voir figure~\ref{space_metric_btree}).

				\begin{figure}[ht]
				$$\begin{array}{|c|}\hline
    		\includegraphics[height=5cm, width=7cm]{\filext{../space_metric/image/btree}} \\ \hline
    		\end{array}$$
    		\caption{Illustration d'un B+ tree.}
    		\label{space_metric_btree}
    		\end{figure}

		\begin{xdefinition}{B+ tree}
		Soit $B_n$ un B+ tree, soit $N$ un n\oe ud de $B_n$, il contient un vecteur $V\pa{N} = \vecteur{x_1}{x_t}$
		avec $0 \infegal t \infegal n$ et $x_1 < ... < x_t$. Ce n\oe ud contient aussi exactement $t-1$ n\oe uds fils
		notés $\vecteur{N_1}{N_{t-1}}$. On désigne par $D\pa{N_t}$ l'ensemble des descendants du n\oe ud $N_t$ et
		$G\pa{N_t} = \acc{ V\pa{M} \sac M \in D\pa{N_t}}$. Le n\oe ud $N$ vérifie~:
					\begin{eqnarray*}
					&& \forall x \in G\pa{N_t}, \; x_{t} \infegal x < x_{t+1} \\
					&& \text{avec par convention } x_0 = -\infty \text{ et } x_{t+1} = + \infty
					\end{eqnarray*}
		\end{xdefinition}

\indexfr{quicksort}
\indexfrr{tri}{quicksort}

Cet arbre permet de trier une liste de nombres, c'est une généralisation du tri "quicksort" pour lequel $n=2$. Comme pour le tri quicksort, l'arbre est construit à partir d'une série d'insertions et de cet ordre dépend la rapidité du tri. L'espérance du coût (moyenne sur tous les permutations possibles de $k$ éléments), le coût de l'algorithme est en $O\pa{k \log_n k}$.

\subsection{R-tree ou Rectangular Tree}
\indexfr{R-tree}

L'arbre R-tree est l'adaptation du mécanisme du B+ tree au cas multidimensionnel (voir \citeindex{Guttman1984}). La construction de cet arbre peut se faire de manière globale -~construction de l'arbre sachant l'ensemble de points à classer~- ou de manière progressive -~insertion des points dans l'arbre les uns à la suite des autres~-. Ces arbres sont comparables à l'arbre de partitionnement construit par l'algorithme~\ref{algorithm_AHC} à ceci près que la forme des ensembles est constituée de rectangles et non plus de cercles. L'appartenance d'un point à un rectangle dépend dorénavant des comparaisons entre coordonnées tandis que l'appartenance d'un point à un cercle nécessite le calcul d'une distance, ce qui est plus lent. Toutefois, ces méthodes sont resteintes à des espaces vectoriels.

				\begin{figure}[ht]
				$$\begin{array}{|c|c|}\hline
    		\includegraphics[height=6cm, width=6cm]{\filext{../space_metric/image/rtree1}} &
    		\includegraphics[height=5cm, width=11cm]{\filext{../space_metric/image/rtree2}} \\ \hline
    		\end{array}$$
    		\caption{	Illustration d'un R-tree en deux dimensions,
    							figure extraite de \citeindexfig{Sellis1987}, la première image montre des rectangles
    							pointillés englobant d'autres rectangles en trait plein. Chaque style de trait correspond
    							à un niveau dans le graphe de la seconde image.
    							}
    		\label{space_metric_rtree}
    		\end{figure}

\indexfrr{boîte}{englobante}
\indexfrr{boîte}{objet}
\indexfrr{boîte}{fenêtre}

Il n'existe pas une seule manière de construire un R-tree, les n\oe uds de ces arbres suivent toujours la contrainte des B+~Tree qui est d'avoir un père et au plus $n$ fils. Les R-Tree ont la même structure que les B+~Tree ôtée de leurs contraintes d'ordonnancement des fils. De plus, ces arbres organisent spatialement des rectangles ou boîtes en plusieurs dimensions comme le suggère la figure~\ref{space_metric_rtree}. Les boîtes à organiser seront nommés les objets, ces objets sont ensuite regroupés dans des boîtes englobantes. Un n\oe ud $n$ d'un R-tree est donc soit une feuille, auquel cas la boîte qu'il désigne est un objet, dans ce cas, il n'a aucun fils, soit le n\oe ud désigne une boîte englobante $B\pa{n}$. On désigne par $\mathcal{B}$ l'ensemble des boîtes d'un espace vectoriel quelconque et $v\pa{b}$ désigne son volume. Pour un n\oe ud $n$ non feuille, $A\pa{n}$ désigne l'ensemble des descendants de ce n\oe ud. $B\pa{n}$ est défini par~:

			$$
			B\pa{n} = \arg \min \acc{ v\pa{b} \sac b \in \mathcal{B} \text{ et }
										\forall n' \in A\pa{n'}, \; B\pa{n'} \subset B\pa{n} }
			$$

La recherche dans un R-tree consiste à trouver toutes les objets ayant une intersection avec une autre boîte ou fenêtre $W$, soit l'ensemble $L$~:

		$$
		L = \acc{ B\pa{n} \sac B\pa{n} \text{ est un objet et } B\pa{n} \cap W \neq \emptyset }
		$$

Cet ensemble est construit grâce à l'algorithme suivant~:

		\begin{xalgorithm}{recherche dans un R-tree}  \label{space_metric_algo_r_tree_search}
		Les notations sont celles utilisées dans ce paragraphe. On désigne par $r$ le n\oe ud racine d'un R-tree.
		Soit $n$ un n\oe ud, on désigne par $F\pa{n}$ l'ensemble des fils de ce n\oe ud.

		\begin{xalgostep}{initialisation}
		$L \longleftarrow 0$ \\
		$N \longleftarrow \acc{r}$
		\end{xalgostep}

		\begin{xalgostep}{itération}
		\begin{xwhile}{$N \neq \emptyset$}
			\begin{xforeach}{n}{N}
				\begin{xif}{$W \cap B\pa{n} \neq \emptyset$}
				  $N \longleftarrow N \cup F\pa{n}$ \\
					\begin{xif}{$B\pa{n}$ est un objet}
							$L \longleftarrow B\pa{n}$
					\end{xif}
				\end{xif}
			\end{xforeach}
		\end{xwhile}
		\end{xalgostep}

		$L$ est l'ensemble cherché.

		\end{xalgorithm}

Il reste à construire le R-tree, opération effectuée par la répétition successive de l'algorithme~\ref{space_metric_algo_r_tree_insert} permettant d'insérer un objet dans un R-tree.

		\begin{xalgorithm}{insertion d'un objet dans un R-tree} \label{space_metric_algo_r_tree_insert}
		Les notations utilisées sont les mêmes que celles de l'algorithme~\ref{space_metric_algo_r_tree_search}.
		On cherche à insérer l'object $E$ désigné par son n\oe ud feuille $e$. On suppose que l'arbre contient au
		moins un n\oe ud, sa racine $r$. On désigne également par $p\pa{n}$ le père du n\oe ud $n$. Chaque n\oe ud
		ne peut contenir plus de $s$ fils. On désigne par
		$v^*\pa{G} = \min \acc{ P \sac P \in \mathcal{B} \text{ et }
				\unionone{g \in G} B\pa{g}  \subset P }$.

		\begin{xalgostep}{sélection du n\oe ud d'insertion}
		$n^* \longleftarrow r$ \\
		\begin{xwhile}{$n^*$ n'est pas un n\oe ud feuille}
		    On choisit le fils $f$ de $n^*$ qui minimise l'accroissement $v_f - v\pa{B\pa{f}}$
		    du volume avec $v_f$ défini par~:
				\begin{eqnarray}
				v_f = \min \acc{ v\pa{P} \sac P \in \mathcal{B} \text{ et } B\pa{f} \cup B\pa{e}  \subset P }
				\label{space_metric_r_tree_b_n_update}
				\end{eqnarray}
				$n^* \longleftarrow f$
		\end{xwhile}
		\end{xalgostep}

		\begin{xalgostep}{ajout du n\oe ud}
		Si $p\pa{n^*}$ a moins de $s$ fils, alors le n\oe ud $e$ devient le fils de $p\pa{n^*}$ et $B\pa{p\pa{n^*}}$ est
		mis à jour d'après l'expression (\ref{space_metric_r_tree_b_n_update}). L'insertion est terminée.
		Dans le cas contraire, on sépare découpe le n\oe ud $p\pa{n^*}$ en deux grâce à l'étape suivante.
		\end{xalgostep}

		%\possiblecut

		\begin{xalgostep}{découpage des n\oe uds} \label{space_metric_insertion_decoupage_r_tree}
		L'objectif est de diviser le groupe $G$ composé de $s+1$ n\oe uds en deux groupes $G_1$ et $G_1$.
		Tout d'abord, on cherche
		le couple $\pa{n_1,n_2}$ qui minimise le critère $$ d = v^*\pa{\acc{n_1,n_2}} - v\pa{B\pa{n_1}} - v\pa{B\pa{n_2}}$$ Alors~:
		$G_1 \longleftarrow n_1$, $G_2 \longleftarrow n_2$ et $G \longleftarrow G - G_1 \cup G_2$ \\
		\begin{xwhile}{$G \neq \emptyset$}
				On choisit un n\oe ud $n \in G$, on détermine $i^*$ tel que $v\pa{\acc{n} \cup G_i} - v\pa{G_i}$ soit minimal. \\
				$G \longleftarrow G - \acc{n}$ \\
				$G_{i^*} \longleftarrow G_{i^*} \cup \acc{n}$
		\end{xwhile}
		\end{xalgostep}

		\end{xalgorithm}

\indexfr{R$^*$ tree}
\indexfr{R$^*$ tree}
\indexfr{R+ Tree}
Si la recherche est identique quel que soit l'arbre construit, chaque variante de la construction de l'arbre tente de minimiser les intersections des boîtes et leur couverture. Plus précisément, l'étape~\ref{space_metric_insertion_decoupage_r_tree} qui permet de découper les n\oe uds est conçue de manière à obtenir des boîtes englobantes de volume minimale et/ou d'intersection minimale avec d'autres boîtes englobantes. L'algorithme R+~Tree (voir \citeindex{Sellis1987}) essaye de minimiser les intersections entre boîtes et les objets à organiser sont supposés n'avoir aucune intersection commune. La variante R$^*$~Tree (voir \citeindex{Beckmann1990}) effectue un compromis entre l'intersection et la couverture des boîtes englobantes. L'algorithme X-Tree (voir \citeindex{Berchtold1996}) conserve l'historique de la construction de l'arbre ce qui lui permet de mieux éviter les intersections communes entre boîtes.

\subsection{Branch and Bound}
\indexfr{Branch and Bound}
\indexfr{hiérarchie}
\indexfrr{décomposition}{hiérarchique}
\indexfr{espace vectoriel}

Les algorithmes regroupés sous cette terminaison \emph{Branch and Bound} englobe la plupart des méthodes présentées dans ce document, elles désignent tout algorithme de recherche nécessitant une première étape permettant de construire une décomposition hiérarchique de l'ensemble des exemples ou exemples d'apprentissage, cet ensemble étant inclus dans un espace vectoriel. La première version de cette famille algorithme a été développée dans \citeindex{Fukunaga1975}.

\indexfrr{loi}{normale}

La méthode présentée dans \citeindex{D'Haes2003} utilise une analyse en composantes principales afin de construire une hiérarchique adaptée à un nuage de points obéissant à une loi normale multidimensionnelle (voir figure~\ref{space_metric_dheas_1}).

				\begin{figure}[ht]
				$$\begin{array}{|c|}\hline
    		\includegraphics[height=6cm, width=12cm]{\filext{../space_metric/image/dhaes}} \\ \hline
    		\end{array}$$
    		\caption{ Figure extraite de \citeindexfig{D'Haes2003} représentant l'arbre de décomposition
    							de deux nuages de points obéissant à des loi normales, uniforme dans le premier cas,
    							avec deux variables corrélées dans le second cas.}
    		\label{space_metric_dheas_1}
    		\end{figure}

\indexfr{ACP}
\indexfr{médiane}
\indexfr{analyse en composantes principales}

La méthode proposée dans cet article effectue une analyse en composantes principales afin de repérer l'axe principal du nuage qui correspond au vecteur propre $\vec{V}$ associé à la plus grande des valeurs propres de la matrice $X'X$ où chaque ligne de la matrice $X$ est un élément du nuage de points $\vecteur{\vec{x_1}}{\vec{x_n}}$. On détermine la médiane $m$ de l'ensemble $\acc{ < \vec{V}, \vec{x_i}  >  \sac 1 \infegal i \infegal n}$. Le nuage de points est alors divisée en deux sous-nuages de cardinaux égaux selon que le produit scalaire $< \vec{V}, \vec{x_i} >$ est inférieur ou supérieur à $m$. Chaque sous-nuage est à nouveau divisé selon le même processus incluant une analyse en composantes principales et la recherche de la médiane. L'algorithme s'arrête lorsque les sous-ensembles sont réduits à un seul élément.

\subsection{Méthodes approchées}
\indexfrr{kPPV}{méthode approchée}

Toutes les méthodes proposées jusqu'à présent permettent de déterminer le voisinage exact d'un élément inclus dans un ensemble d'exemples, les différences concernant l'organisation de cet ensemble afin d'optimiser la recherche. L'autre direction de recherche concerne la recherche du voisinage notamment par des méthodes approchées, plus rapide, mais ne retournant pas le voisinage exact. Ces méthodes ne seront pas plus développées ici, l'article \citeindex{Arya1994} propose une étude théorique de ce problème. L'article \citeindex{Ramasubramanian2000} compare plusieurs méthodes de recherche du voisinage.

%-------------------------------------------------------------------------------------------------------------
\section{Autres alternatives}
%-------------------------------------------------------------------------------------------------------------

Il existe de nombreuses alternatives en ce qui concerne la recherche des plus proches voisins dans un espace métrique quelconque, passées en revue dans les articles \citeindex{Bustos2001}, \citeindex{Chavez1999}, \citeindex{Navarro2001}, certaines utilisant plus particulièrement les arbres comme \citeindex{Ulhmann1991} ou \citeindex{Yianilos1993}. Lorsque cette recherche s'applique aux mots ou aux séquences, l'optimisation de la distance est envisagée (voir \citeindex{Apostolico1985} ou \citeindex{Madhvanath2001}). L'algorithme qui suit est une de ces alternatives préférée aux autres en raison de sa simplicité. Il ne nécessite pas la construction d'un arbre et son coût est aisément calculable.

\subsection{LAESA}

\label{space_metric_laesa_laesa}
\indexfr{LAESA}\indexfr{pivot}

Cet algorithme permet de chercher les plus proches voisins dans un ensemble inclus dans un espace métrique quelconque. Il s'appuie encore sur l'inégalité triangulaire appliquée de manière semblable à (\ref{equation_un}). Le voisinage d'un point $x$ doit être cherché dans un ensemble $E$. L'algorithme LAESA (Linear Approximating Eliminating Search Algorithm, voir \citeindex{Rico-Juan2003}) consiste à éviter un trop grand nombre de calculs de distances en se servant de distances déjà calculées entre les éléments de $E$ et un sous-ensemble $B$ inclus dans $E$ contenant des "pivots".

La sélection des pivots demeure un problème ouvert. Ceux-ci pourrait être les n\oe uds d'un coupe de l'arbre construit par l'algorithme~\ref{algorithm_AHC}. Il existe d'autres possibilités comme l'algorithme~\ref{space_metric_algo_laesa_prime} plus simple et nettement moins coûteux -~les deux algorithmes n'ont pas été comparés en terme de performances en classification.

			\begin{xalgorithm}{LAESA}
			\label{space_metric_algo_laesa}

			Soit $E = \ensemble{y_1}{y_N}$ un ensemble de points, $B = \ensemble{p_1}{p_P} \subset E$
			un ensemble de pivots inclus dans $E$. On cherche à déterminer le voisinage $V\pa{x}$ de $x$
			inclus dans $E$ vérifiant~:

						$$
						\forall y \in V\pa{x}, \; d\pa{x,y} \infegal \rho
						$$

			On suppose que la matrice $M = \pa{m_{ij}}_ { \begin{subarray} 1 \infegal i \infegal P \\
			1 \infegal j \infegal N \end{subarray} }$ a été calculée préalablement comme suit~:

						$$
						\forall \pa{i,j}, m_{ij} = d\pa{p_i, y_j}
						$$

			\begin{xalgostep}{initialisation}
				$\begin{array}{ll}
				\forall y \in E, & g\pa{y} \longleftarrow 0 \\
				\forall y \in E, & h\pa{y} \longleftarrow 1
				\end{array}$
			\end{xalgostep}

			\begin{xalgostep}{choix d'un pivot et mise à jour de la fonction $g$} \label{classif_laesa_step_b}
				$B' \longleftarrow B \cap \acc{ y \in E \sac h\pa{y} = 0}$ \\
				\begin{xif}{$B' \neq \emptyset$}
					Soit $i$ tel que $p_i$ soit un élément de $B'$ tiré au hasard tel que~: \\
									$$p_i \in \arg \min \acc{ g\pa{y} \sac y \in B'}$$
					$\begin{array}{lll}
					\alpha 		&\longleftarrow& d\pa{p_i,x} \\
					h\pa{p_i} &\longleftarrow& 1
					\end{array}$ \\
					$\begin{array}{rl}
					\forall y_j \in E \text{ tel que } h\pa{y_j} = 0, \; g\pa{y_j} \longleftarrow &
											\max \acc {	g\pa{y_j} , \abs{ \alpha - m_{ij} }  } \\ = &
											\max \acc {	g\pa{y_j} , \abs{ d\pa{x,p_i} - d\pa{p_i, y_j} }  }
					\end{array}$
				\xelse
					Choisir un élément $s$ de $E$ tel que $h\pa{s} = 0$. \\
					$\begin{array}{lll}
					\alpha 		&\longleftarrow& d\pa{s,x} \\
					h\pa{s}   &\longleftarrow& 1
					\end{array}$ \\
					$\begin{array}{rl}
					\forall y   \in E \text{ tel que } h\pa{y} = 0, \; g\pa{y} \longleftarrow & d\pa{x,y}
					\end{array}$

				\end{xif}

			\end{xalgostep}

			\possiblecut

			\begin{xalgostep}{élimination}
				$\begin{array}{rl}
				\forall y_j \in E \text{ tel que } h\pa{y_j} = 0, \text{ si } g\pa{y_j} > \rho \text{ alors }
				h\pa{y_j} = 1
				\end{array}$
			\end{xalgostep}

			\begin{xalgostep}{terminaison}
				$A \longleftarrow \acc{ y \in E \sac h\pa{y} = 0 }$ \\
				\begin{xif}{$A \neq \emptyset$}
				Retour à l'étape~\ref{classif_laesa_step_b}.
				\xelse
				Fin, l'ensemble cherché correspond à $\acc{y \in E \sac g\pa{y}} \infegal \rho$.
				\end{xif}
			\end{xalgostep}

			\end{xalgorithm}

La sélection des pivots est assurée par un autre algorithme décrit dans l'article~\citeindex{Moreno2003}.

			\begin{xalgorithm}{LAESA : sélection des pivots}
			\label{space_metric_algo_laesa_pivtos_sel}
			\indexfrr{pivot}{sélection}

			Soit $E = \ensemble{y_1}{y_N}$ un ensemble de points, on cherche à déterminer
			l'ensemble $B = \ensemble{p_1}{p_P} \subset E$ utilisé par l'algorithme~\ref{space_metric_algo_laesa}.

			\begin{xalgostep}{initialisation}
				$B \longleftarrow y \in E$ choisi arbitrairement.
			\end{xalgostep}

			\begin{xalgostep}{calcul de la fonction $g$} \label{space_metric_laesa_pivots_sel_b}
					\begin{xforeach}{y}{E - B}
						$g\pa{y} \longleftarrow 0$ \\
						\begin{xforeach}{p}{B}
						$g\pa{y} \longleftarrow g\pa{y} + d\pa{y,p}$
						\end{xforeach}
					\end{xforeach}
			\end{xalgostep}

			\begin{xalgostep}{mise à jour de $B$}
					Trouver $p^* \in \arg \max \acc { g\pa{p} \sac p \in E - B}$\\
					$B \longleftarrow B \cup \acc{ p^*}$ \\
					Si $\card{B} < P$, retour à l'étape~\ref{space_metric_laesa_pivots_sel_b} sinon fin.
			\end{xalgostep}

			\end{xalgorithm}

Cet article~\citeindex{Moreno2003} améliore également l'algorithme~\ref{space_metric_algo_laesa} par le suivant~:

			\begin{xalgorithm}{LAESA'}
			\label{space_metric_algo_laesa_prime}
			\indexfr{LAESA'}

			Soit $E = \ensemble{y_1}{y_N}$ un ensemble de points, $B = \ensemble{p_1}{p_P} \subset E$
			un ensemble de pivots inclus dans $E$. On cherche à déterminer le voisinage $V\pa{x}$ de $x$
			inclus dans $E$ vérifiant~:

						$$
						\forall y \in V\pa{x}, \; d\pa{x,y} \infegal \rho
						$$

			On suppose que la matrice $M = \pa{m_{ij}}_ { \begin{subarray} 1 \infegal i \infegal P \\
			1 \infegal j \infegal N \end{subarray} }$ a été calculée préalablement comme suit~:

						$$
						\forall \pa{i,j}, \; m_{ij} = d\pa{p_i, y_j}
						$$

			\begin{xalgostep}{initialisation}
				$\forall i \in \ensemble{1}{P}, \; d_i \longleftarrow d\pa{x,p_i}$
			\end{xalgostep}

			\begin{xalgostep}{fonction $g$} \label{classif_laesa_prime_step_b}
				$\forall j \in \ensemble{1}{N}, \;  g\pa{y_j} \longleftarrow \underset{  i \in \ensemble{1}{P} }{\min}  \abs{ m_{ij} - d_i} $
			\end{xalgostep}

			\begin{xalgostep}{tri}
				Tri l'ensemble $g\pa{y_i}$ par ordre croissant $\longrightarrow g\pa{y_{\sigma\pa{j}}}$. \\
				\begin{xfor}{j}{1}{N}
				   \begin{xif}{$g\pa{y_{\sigma\pa{j}}} \infegal \rho$}
				   $g\pa{y_{\sigma\pa{j}}} = d\pa{x,y_{\sigma\pa{j}}}$
				   \end{xif}
				\end{xfor}

				Fin, l'ensemble cherché correspond à $\acc{y \in E \sac g\pa{y}} \infegal \rho$.
			\end{xalgostep}

\end{xalgorithm}

\indexfr{TLAESA}

Il existe d'autres versions de l'algorithme LAESA comme TLAESA (Tree - LAESA) (voir \citeindex{Mic\'o1996}). Cet algorithme associe un arbre à l'algorithme LAESA et fait le lien entre les algorithmes~\ref{algorithm_AHC} et~\ref{space_metric_algo_laesa}.

\subsection{Résultats théoriques}

\indexfr{mesure}\indexfr{densité}
L'article~\citeindex{Farag\'o1993} démontre également qu'il existe une majoration du nombre moyen de calcul de distances pour peu que la mesure de l'espace contenant l'ensemble $E$ et l'élément $x$ soit connue et que l'ensemble $B = \ensemble{p_1}{p_P}$ des pivots vérifie~:

			\begin{eqnarray}
			\exists \pa{\alpha,\beta} \in \R^+_* \text{ tels que } && \nonumber\\
			\forall \pa{x,y} \in E^2, \; \forall i\, && \alpha \, d\pa{x,y} \supegal
							\abs{d\pa{x,p_i} - d\pa{p_i,y}} \label{space_metric_cond_1} \\
			\forall \pa{x,y} \in E^2, && \underset{i}{\max} \; \abs{d\pa{x,p_i} - d\pa{p_i,y}} \supegal
							\beta \, d\pa{x,y} \label{space_metric_cond_1}
			\end{eqnarray}

L'algorithme développé dans~\citeindex{Farag\'o1993} permet de trouver le point de plus proche d'un élément $x$ dans un ensemble $E = \ensemble{x_1}{x_N}$ selon l'algorithme suivant~:

			\begin{xalgorithm}{plus proche voisin d'après [Farag\'o1993]}\label{space_metric_algo_farago}
			Soit $E = \ensemble{x_1}{x_N}$ et $B = \ensemble{p_1}{p_P} \subset E \subset X$. Soit $x \in X$
			un élément quelconque.
			On suppose que les valeurs $m_{ij} = d\pa{x_i, p_j}$ ont été préalablement calculées.

			\begin{xalgostep}{initialisation}
			On calcule préalablement les coefficients $\gamma\pa{x_i}$~:
			  				$$
								\forall i \in \ensemble{1}{N}, \; \gamma\pa{x_i} \longleftarrow \underset{j
														\in \ensemble{1}{P} } {\max} \;
											\abs{ m_{ij} - d\pa{x,p_j} }
								$$
			\end{xalgostep}

			\begin{xalgostep}{élaguage}
			On définit $t_0 \longleftarrow \underset{i} {\min} \; \gamma\pa{x_i}$. \\
			Puis on construit l'ensemble $F\pa{x} = \acc{ x_i \in E \sac \gamma\pa{x_i} }\infegal
						 \frac{\alpha}{\beta} \, t_0$.
			\end{xalgostep}

			\begin{xalgostep}{plus proche voisin}
			Le plus proche $x^*$ voisin est défini par~: $x^* \in \arg \min \acc{ d\pa{x,y} \sac y \in F\pa{x}}$.
			\end{xalgostep}

			\end{xalgorithm}

			\begin{xtheorem}{[Farag\'o1993]$^1$}
																\label{space_metric_farago_1}
			Les notations sont celles de l'algorithme~\ref{space_metric_algo_farago}.
			L'algorithme~\ref{space_metric_algo_farago} retourne le plus proche voisin $x^*$ de $x$ inclus dans $E$.
			Autrement dit, $\forall x \in X, \; x^* \in F\pa{x}$.
			\end{xtheorem}

\begin{xremark}{mesure de dissimilarité}
L'algorithme~\ref{space_metric_algo_farago} est en fait valable pour une distance mais aussi pour une mesure de dissimilarité. Contrairement à une distance, une mesure de dissimalité ne vérifie pas l'inégalité triangulaire.
\indexfrr{mesure}{dissimilarité}\indexfr{dissimilarité}
\indexfr{inégalité triangulaire}
\end{xremark}

			\begin{xtheorem}{[Farag\'o1993]$^2$}
																\label{space_metric_farago_2}
			Les notations sont celles de l'algorithme~\ref{space_metric_algo_farago}. On définit une mesure
			sur l'ensemble $X$, $B\pa{x,r}$ désigne la boule de centre $x$ et de rayon $r$, $Z \in X$ une variable
			aléatoire, de plus~:
						$$
						p\pa{x,r} = P_X \pa{B\pa{x,r}} = \pr{  Z \in B\pa{x,r}}
						$$

			On suppose qu'il existe $d > 0$ et une fonction $f : X \longrightarrow \R$ tels que~:
						$$
						\underset { r \rightarrow 0 } { \lim } \; \frac{ p\pa{x,r} } { r^d } = f\pa{x} > 0
						$$
		  La convergence doit être uniforme et presque sûre.
		  On note également $F_N$ le nombre de calculs de dissimilarité effectués par
		  l'algorithme~\ref{space_metric_algo_farago} où $N$ est le nombre d'élément de $E$,
		  $P$ désigne toujours le nombre de pivots, alors~:

		  			$$
		  			\underset{ n \rightarrow \infty } { \lim \sup } \;
		  							\esp{F_N} \infegal k + \pa{\frac{\alpha}{\beta}}^{2d}
		  			$$

			\end{xtheorem}

\subsection{Suppression des voisins inutiles}
\label{space_metric_suppression_voisins_inutile}
\indexfr{voisins inutiles}
\indexfr{plus proches voisins}
\indexfr{classification}
\indexfr{capacité d'attraction}

L'article \citeindex{Wu2002} propose une idée intéressante qui consiste à supprimer les voisins inutiles. Cette méthode s'applique dans le cas d'une classification à l'aide de plus proches voisins. A un élément à classer, cette méthode attribue la classe du point le plus proche, il faut donc a priori calculer les distances du point en question à tous ceux déjà classés. Certains points de cet ensemble ont une forte "capacité d'attraction"~: ils sont le centre d'une région dans laquelle seuls des points de la même classe figurent. Plus concrètement, soient un point $y$ à classer et une base de points classés noté $\vecteur{x_1}{x_N}$ de classe $\vecteur{c\pa{x_1}}{c\pa{x_N}}$, on suppose que $x_i$ et $x_j$ sont deux points, enfin, on définit~:

		\begin{eqnarray}
		y^*					 = \arg \min \acc{ d\pa{x_k, y} \sac 1 \infegal k \infegal n }
		\end{eqnarray}

On suppose également que $x_i$ est un point de forte capacité et que~:

		\begin{eqnarray}
		\forall y, \; y^* = x_i \Longrightarrow \exists l \text{ tel que }
										x_l = \arg \min \acc{ d\pa{x_k, y} \sac k \neq i } \text{ et } c\pa{x_l} = c\pa{x_i}
		\end{eqnarray}

Autrement dit, $x_i$ est un point attracteur si quel que soit le point $y$ proche de $x_i$, il sera toujours possible de trouver un voisin de $x_i$ proche et $y$ et appartenant à la même classe. Dans ce cas, il ne sert à rien de calculer la distance de $x_i$ à $y$, le point $x_i$ peut alors être éliminé de la base des points classés. Il reste maintenant à traiter la base de points classés de manière à en garder le moins possible. De cette façon, l'ensemble des points classés ne gardera que des points situés près des frontières entre classes.

L'article \citeindex{Wu2002} définit le rayon d'un point~:

		\begin{eqnarray}
		r\pa{x}  = \max\acc { 0, \max \acc{ d\pa{x, y} \sac c\pa{x} = c\pa{y} } }
		\end{eqnarray}

L'algorithme de suppression des points attracteurs est le suivant~:

			\begin{xalgorithm}{suppression des points attracteurs}
			Soit $\Gamma$ un seuil positif, les notations sont celles utilisées dans les paragraphes qui précèdent,
			on note également $\Omega$ l'ensemble des points classés.

			\begin{xalgostep}{calcul des rayons}\label{space_metric_attracteur_step_a}
			Pour chaque $x \in \Omega$, on calcule $r\pa{x}$, et on désigne par $x^*$ le point qui vérifie~:
			$r\pa{x^*} = \underset{x \in \Omega} {\max} \; { r\pa{x} }$
			\end{xalgostep}

			\begin{xalgostep}{suppression}
			Si $r\pa{x^*} \supegal \Gamma$, alors le point $x^*$ est supprimé de l'ensemble $\Omega$, et retour
			à l'étape~\ref{space_metric_attracteur_step_a}. Dans le cas contraire, l'algorithme s'arrête.
			\end{xalgostep}

			\end{xalgorithm}

\begin{xremark}{méthode approchée}
Le fait de supprimer les points dont le rayon attracteur est supérieur à un certain seuil peut entraîner une modification de la classification si ce seuil est trop petit.
\end{xremark}

\indexfr{LVQ}\indexfrr{prototype}{LVQ}
Cette méthode poursuit le même objectif que celui des méthodes LVQ\seeannex{clas_super_principe_lvq}{LVQ} ou Learning Vector Quantization qui permettent de réduire un ensemble de points utilisés dans une classification de plus proches voisins à un ensemble de prototypes.

\subsection{Lien vers la classification}

Déterminer le voisinage d'un point est un passage obligé lorsqu'on applique une classification à l'aide de plus proches voisins puisque chaque élément est classé à partir des classes de ses voisins\seeannex{clas_super_kppv_simple}{classification k-PPV}. Toutefois, les résultats obtenus par cette méthode dépendent fortement de la distance utilisée. Sans a priori sur celle-ci, c'est souvent une distance euclidienne qui est choisie.

Dans le cas des espaces vectoriels, il est possible d'utiliser une distance pondérant différemment chaque dimension et d'estimer cette pondération à partir d'un échantillon représentatif du problème de classification à résoudre. Deux méthodes sont présentées aux chapitre~\ref{classification_graphem_carac_dist} et~\ref{classification_distance_voisinage}.

\newpage

\firstpassagedo{
	\begin{thebibliography}{99}
	\input{space_metric_biblio.tex}
	\end{thebibliography}
}

\input{../../common/livre_table_end.tex}%
\input{../../common/livre_end.tex}%

redpajama_set_name: RedPajamaGithub


During the summer, it's common to let your dog out in the garden. After all, they love the fresh air and bathing in the hot sun. And it can be fun for all the family when your pooch joins you in the backyard. However, you need to be so careful to ensure your pet is safe when in the yard. After all, you don't want to find they have made a grand escape from the garden, or have an injury. Therefore, here are some ways to keep your pooch safe in the yard.
It's easy to leave things like rakes and lawn mowers out in your garden. After all, we aren't so great at putting things away straight away! However, you need to be so careful if you are going to let your pooch out when these kind of items are just sitting around. After all, they might end up hurting their paw or getting caught if they sniff around that area. And then you will end up making a trip to the vet. Therefore, it's so important for the safety of your pet to ensure any hazardous items are put away in a shed after you have finished using them. That way, they can go outside and play without getting hurt in the yard.
You want your pet to be able to play out in the yard without you worrying about them getting out. After all, it can be a horrendous time if your pet does go missing. And moreover, you don't want anyone getting in your yard and taking your pooch. Therefore, you should make sure there is a solid wooden fence in your garden which can ensure your pet can't go further afield. And it can be useful if you have a pool or a pond you don't want them to get close to! You can find wood fences on https://www.beitzellfence.com/ that might look great in the garden. And if you do notice any missing panels over time, make sure they are quickly fixed to keep your pet safe in the backyard.
It's common for your garden to have a wealth of pests during the warmer months. In fact, you might have to deal with bugs like wasps and fleas in your yard. And these can both prove an issue to your pets. For one thing, they might get stung which will leave them in pain. And if they get fleas, they could end up infested. Of course, there is a risk of big pests like moles and rats too in your yard. And these can harm your pooch too if they get too close. Therefore, to keep your pet safe in your yard, you need to make sure you get rid of any pests in the garden. You can get sprays to keep garden pests away, or contact an exterminator. Then you can safely let your pet out without worrying about a pest infestation!
And make sure you only have animal-friendly plants in your yard. Otherwise, you could have one poorly pooch to deal with! Look on http://www.1stinflowers.com/ for a list of plants you need to avoid!


text:
Q: Vmware EULA - Essentials and vSphere Standard same site Can a company run a vSphere Essentials cluster and maintain a vSphere Standard cluster at the same time and still be in license compliance in the VMware EULA?
No requirement for all hosts to be managed by one vCenter server.

A: Sure. Why not?
If you pay for them and aren't managing via the same Virtual Center, there's no problem.

redpajama_set_name: RedPajamaStackExchange


text:
Iulică Ruican (* 29. srpna 1971, Cujmir, Rumunsko) je bývalý rumunský veslař. Na olympijských hrách 1992 v Barceloně získal zlatou medaili na čtyřce s kormidelníkem a stříbrnou na osmě. Je též trojnásobným mistrem světa.

Na olympijských hrách 1996 byl vlajkonošem rumunské výpravy a obsadil s osmiveslicí sedmé místo.

Závodil za armádní klub CSA Steaua București a po ukončení aktivní kariéry působil jako viceprezident klubu.

Jeho manželka Anca Tănaseová je také olympijskou vítězkou ve veslování.

Reference

Externí odkazy

 Profil na worldrowing.com

Narození v roce 1971
Rumunští veslaři
Rumunští olympijští vítězové
Rumunští stříbrní olympijští medailisté
Olympijští vítězové ve veslování
Stříbrní olympijští medailisté ve veslování
Žijící lidé
Muži
Narození 29. srpna
Mistři světa ve veslování

redpajama_set_name: RedPajamaWikipedia


First Christian Church is located at the corner of East Fifth Street and Florence in Claremore, Oklahoma.
Our congregation celebrates worship on Sunday at 10:45am & 6:30 PM. Please visit the worship page for more information.
Ours is a unified worship with elements of both contemporary and traditional style worship. We always welcome new experiences!
If you have any other questions, please call the church (918.341.1199) and talk to a staff member. We want to welcome you and provide a welcoming, relaxed place to worship.


The Audeze EL-8 Closed-Back are mangetic planar headphones using Audeze's unique Fluxor magnets to achieve incredible frequency response ranging between 10Hz to 50kHz into a 30 Ohm load.
The Audeze EL-8 Closed-Back provides incredible performance with transient response impossible to achieve with conventional dynamic headphones. Its closed back design makes it idea for performers (vocalists, instrumentalists) and recording engineers who need sound isolation.
Magnetic planar headphones use multiple magnetic strips located behind a very thin diaphragm to provide a much faster response. The diaphragm features a specifically designed circuit etched to it evenly distributing the magnetic force across the diaphragm. This "Uniforce" technology greatly minimises distortion.
The diaphragm is made of polymer developed by NASA for use on the Space Station. This polymer is extremely light, flexible and resistant. The EL-8 also includes Audeze's Fazor waveguides that focus the sounds coming through the magnet, and minimises phase and additional distortion.
Magnetic planar headphones using Audeze's unique Fluxor magnets to achieve incredible frequency response ranging between 10Hz to 50kHz into a 30 Ohm load.


English fiction -- 19th century -- Scottish authors.
Publication Edinburgh : printed for Archibald Constable and Co. ; London : Hurst, Robinson, and Co., 1824.
Vol. 1: 310 p. ; vol. 2: 325,  p. ; vol. 3: 323,  p.
The author of "Waverley" is Sir Walter Scott.
"Edinburgh: printed by James Ballantyne and Co."--t.p. verso.


10 When they saw the star, they were overjoyed. 11 On coming to the house, they saw the child with his mother Mary, and they bowed down and worshiped him. Then they opened their treasures and presented him with gifts of gold, frankincense and myrrh.12 And having been warned in a dream not to go back to Herod, they returned to their country by another route.
12 When your days are over and you rest with your ancestors, I will raise up your offspring to succeed you, your own flesh and blood,and I will establish his kingdom.
13 He is the one who will build a housefor my Name, and I will establish the throne of his kingdom forever.


text:
Fifth Third Foundation funds $1.2 Million 'Innovation Meets Main Street' program for Black women-owned entrepreneurs
by Marshall A. Latimore September 11, 2020
On Friday, Fifth Third announced a new $1.2 million grant program called "Innovation meets Main Street: Boosting Black Women-Owned Businesses," a partnership between AEO and LISC powered by Fifth Third Bank.
The program is made possible by grants from the Fifth Third Foundation to Local Initiatives Support Corporation (LISC) and the Association of Enterprise Opportunity's (AEO) MainStreet RISE program. The funds are part of the $8.75 million Fifth Third pledged to support small businesses and the community during the COVID-19 pandemic.
"Our vision for this program was to bring together proven organizations who could help black- and other minority-owned women entrepreneurs through the COVID-19 pandemic and beyond," said Byna Elliott, Fifth Third's senior vice president and chief enterprise responsibility officer. "Not only do these businesses need grants to help weather the health and economic crisis, but they also need technical assistance like marketing and digital capabilities as well as venture capital investments. This program is specially designed to help women business owners address their most pressing needs to ensure their sustainability now and in the future."
Join the Family. Be in the Know. Sign up for weekly newsletters and get the best of The Atlanta Voice in your inbox.
This Innovation meets Main Street program is powered entirely by Fifth Third. LISC received $1 million from the Fifth Third Foundation, $630,000 of which was designated for grant funding to small businesses and $250,000 for an investment in the Fearless Fund, a venture capital firm that invests in women of color-led businesses seeking financing. The remaining funds will support the delivery of technical assistance.
"People of color, especially Black women, have been left out of venture capital investments and corporate funding for small businesses for far too long," said Arian Simone, general partner, co-founder, and investor for the Fearless Fund. "Systemic change cannot survive without economic empowerment in Black entrepreneurs from the top down. We are delighted to have Fifth Third's support of the Fearless Fund to help us change the narrative."
Additionally, AEO received $200,000 from the Foundation to provide business owners access to MainStreet RISE, a suite of critical tech-enabled tools and resources to keep businesses existing and selling during and after the pandemic. The tools include Saverlife, FanBank, GoDaddy, Bench, MicroMentor, and more. The funding also will enable AEO to design the Small Business Resource Navigator, an online interactive tool that directs small businesses to local resources.
Altogether, the program will provide targeted services—grants, technical assistance, or capital infusions—to 35 black- or other minority-owned women entrepreneurs in Atlanta, Charlotte, Cincinnati, Detroit, Louisville, Nashville, and Orlando. A total of 245 women entrepreneurs will be assisted with grants and investments, and more will receive technical assistance.
"The Fifth Third Foundation is providing vital capital to help sustain Black and minority women-owned small businesses, especially in communities that have been historically underserved," said Maurice A. Jones, the president and CEO of LISC, a national community development nonprofit that invests in affordable housing, economic development, health, and jobs. "Through our partnership, we are focused on offering immediate support to these entrepreneurs who don't otherwise have ready access to relief funds, as well as creating longer-term pathways to recovery, which will be critical in the months to come."
Applications, via an online portal, will open at the commencement of the "State of Black Women-Owned Businesses" webinar on Sept. 16 at 1 p.m. EST. The webinar features:
Byna Elliott, Fifth Third Bank senior vice president and chief enterprise sustainability officer
Connie E. Evans, president and CEO of the Association of Enterprise Opportunity
Steve Hall, senior director of economic development of Local Initiatives Support Corporation
Arian Simone, co-founder of Fearless Fund
Kimberly Blackwell, chief executive officer of PMM.
Registrations must be made in advance of the date at the following link: https://zoom.us/webinar/register/WN_LQHGoZu_S-CbR-zwA6YkVQ.
The application period will close seven days later, on Sept. 23. All eligible applicants will be scored and ranked for selection. Applicants will be notified of acceptance and/or denial via email. Eligibility requirements include, but are not limited, to:
Legal, for-profit business located in one of the seven markets.
Businesses must be currently operating, not closed.
Demonstrated record of operating before COVID-19 and was closed due to a local pandemic-related mandate, and in operation for over one year (business launched prior to May 1, 2019).
Location within al ow- and moderate-income census tract.
Annual business revenues of less than $1 million.
The National Bureau on Economic Research (NBER) presented a working paper that found that the medium firm/business with expenses over $10,000 per month has only enough cash on hand to last for two weeks. (Photo: Shutterstock)
JPMorgan Chase Expands Commitment to Atlanta with $3.2 million for Entrepreneurs of Color
In "Money"
Lowe's to give $55 million in grants to small businesses during COVID-19
In "News"
Facebook provides $40M in grants to Black-Owned Businesses, additional commitments to support the Black community


Here are some pictures of the wall coat rack ikea. Now, we want to try to share these some pictures for your interest, select one or more of these brilliant imageries. We like them, maybe you were too. Perhaps the following data that we have add as well you need. She took ikea bed base off her hung wall bathroom genius, Wood panels ikea sultan lade slatted bed base perfect many things never imagine all which include hanging wall kristina steinmetz coat rack here one intended.
We hope you can make similar like them. We added information from each image that we get, including set of size and resolution. You can click the picture to see the large or full size image. If you like and want to share please click like/share button, so other people can visit here too. Right here, you can see one of our wall coat rack ikea gallery, there are many picture that you can surf, do not miss them.
Who ever said that skilled inside designers are a should, modern stone houses has most likely yet to come across the Interior Designer program. Experimenting with designs has by no means been this easy as Interior Designer permits customers to play with their concepts by way of the use of 3D fashions, superior design tools, in addition to digital tours. Use your creativity to decorating concepts to magnificence the celebration. An added deal with is the photograph importing possibility which permits users to use precise photographs as artwork work and cling them on the partitions of their rooms. Never has it been this easy to arrange cabinets, doors, windows, and partitions all to the proper tuning of 1's instinctive design prowess. There are additionally a variety of pre-made style templates which come complete with window styles, flooring, cabinets, doorways, and are all in full shade. There are also guide and automated dimension instruments that additionally come in helpful when placing interior wall finishes or room dimensions.
This is where Virtual Architect's digital tours and 3D models are available in useful. The problem with blueprints and miniature models is that though they supply a good illustration of how the new residence will appear like, it is still not the same as really strolling inside the home. This fashion, customers are usually not solely aware of how their new properties will look like, but extra importantly, have a really feel of how it will ultimately turn out to be. This brilliantly designed piece of software program allows customers to pick from thousands of different supplies, flooring, wall coverings, colours, and styles - nearly everything and anything to make their homes as close to their dream as doable. For those who want they may give their dream houses the texture and the look they've always wished then Chief Architect Interior Designer has obtained to be the reply to their prayers. To make your own home look enticing in the Christmas night, put the lighting in a decorative method and enjoy the celebration providing a grand occasion amongst your pals, household, and neighbors.
Christmas is also for the time of celebration and marry making. During Christmas people get holidays and that is why it's real time to make get-together with buddies and family. This is the time when your kids await that thrilling second when they will get gifts from Santa Clause. The original cause I did not get a wooden shed was due to the worth. Outdoor garden shed designs for automobiles need to have robust foundation. There are 1000's of various sample plans that can function inspirations for individuals who might have hit a inventive highway block. Those who are looking for a spark of inspiration can choose from the hundreds of accessible pattern plans that can really present great design concepts. Users are not only able to design their new homes, but they're also given the facility to design their very own virtual tours. With a strong design or blue print, you possibly can construct a durable shed that will final a lifetime.
Users can select from the multitude of different furnishings out there which include sofas, tables, chairs, beds, and a lot more. Take your time and don't rush by the venture as a result of this can cause errors and create more problems. Start your Christmas shopping before the schedule time and people who want to avoid wasting money also needs to begin making dwelling made Christmas decoration before the due time. However, the soul attraction of all of the Christmas decoration items is the Christmas tree. A loads of lighting Christmas decoration is obtainable in the market. Common backyard shed designs have domes and windows to enhance the air quality and lighting. With Interior Designer, customers have the facility to create ground plans of the best stage. You'll have shelves put in or purchase storage containers to raised set up gadgets to be saved. What's even higher is that these furnishings can simply be modified, might or not it's their fabric, coloration, or size. Drawers and bins where you'll be able to keep small hand tools, gloves and different small gadgets are also commonly found in backyard sheds.
Below are 6 top images from 20 best pictures collection of wall coat rack ikea photo in high resolution. Click the image for larger image size and more details.