Sélection du plan de coupe

Une fois sélectionnés le multi-ensemble à découper et l'axe de coupe $A$, nous devons définir la position du plan de coupe le long de l'axe $A$. La stratégie la plus simple est encore une fois proposée par Heckbert [Hec82]. Celui-ci propose de couper par un plan médian, c'est à dire un plan tel que $\vert C_1\vert = \vert C_2\vert$ où $C_1$ et $C_2$ sont les deux multi-ensembles issus de la découpe de .

Cette stratégie peut être grandement améliorée en tenant compte de l'erreur de la partition. En effet, soient $m$ et $M$ les deux extrémités de le long de l'axe $A$ (voir Figure 6.7 et définition 7) et $t$ un réel de l'intervalle $[m,M]$. Le plan orthogonal à $A$ et de position $t$ sur l'axe $A$ découpe en deux multi-ensembles t et $(C-C_t,f)$. L'erreur associée à cette partition est égale à :

$$E_t(C) = \ERROR(C_t) + \ERROR(C-C_t)$$ (6.10)

clustersLe multi-ensemble sélectionné est découpé orthogonalement à l'axe de coupe $A$ positionné à la coordonnée $t$ sur l'axe $A$.

Wu [Wu92] a donné une autre formulation de l'erreur de la partition :

$$E_t(C) = \sum_{v\in C} f(v)\,\Vert v\Vert^2 - \left( \frac{\Vert ... ...rt^2}{M_0(C_t)} + \frac{\Vert M_1(C)-M_1(C_t)\Vert^2}{M_0(C)-M_0(C_t)} \right).$$ (6.11)

Cette nouvelle formulation est plus efficace puisqu'elle ne fait apparaître que le multi-ensemble $C_t$ que nous allons faire évoluer jusqu'à trouver la valeur $t_{opt}$ minimisant $E_t(C)$. Elle présente toutefois quelques inconvénients. Tout d'abord elle impose de manipuler des grands nombres tels que les moments d'ordre un au carré. Du point de vue pratique, la présence de grands nombres oblige à stocker les variables sur des entiers ou réels longs qui ralentissent l'algorithme. De plus, cette formule se prête peu à des manipulations et peut donc difficilement être optimisée.

Wan et al. ont simplifié l'équation 6.12 en minimisant non pas l'erreur de la partition mais la somme des variances $var_A(C_t)$ et $var_A(C-C_t)$. Intuitivement, cette simplification revient à approximer le multi-ensemble par sa projection sur l'axe $A$ (voir définition 7). Afin de limiter la perte d'information liée à cette simplification, Wan et al. définissent $A$ comme l'axe principal de . On peut montrer que la recherche de la valeur $t_{opt}$ peut à ce moment là ce limiter à l'intervalle $[\frac{\mu+m}{2},\frac{\mu+M}{2}]$. Cette approche permet donc de limiter l'intervalle de recherche mais ne permet pas d'obtenir la position du plan minimisant l'erreur de la partition.

Le calcul de la valeur $t_{opt}$ par les méthodes de Wu ou de Wan et al. nécessite le calcul des moments $\Mze(C_t)$ et $\Mun(C_t)$ pour $t$ appartenant à l'intervalle $[m,M]$. Ces moments peuvent être calculés rapidement grâce à la propriété suivante. Supposons que le multi-ensemble défini par $C =[a_1,a_2[\times[b_1,b_2[\times[c_1,c_2[$ doit être découpé perpendiculairement au premier axe de coordonnée. Pour tout $t$ nous avons alors : $C_t = [a_1,t[\times[b_1,b_2[\times[c_1,c_2[$. Si nous définissons :

$$D_t = \{t\}\times[b_1,b_2[\times[c_1,c_2[$$

$C_t$ peut se définir comme l'union des $D_t$. Le multi-ensemble étant discret, l'intervalle $[a_1,a_2]$ est égal à $\{a_1,a_1+1,\dots,a_2\}$ et les moments peuvent être calculés incrémentalement par les formules suivantes :

$$\forall i \in \{0,1,2\} \left \{ \begin{array}{l} M_{i}(C_{a+1})=... ...all t \in ]a+1,b[, M_{i}(C_{t+1})=M_{i}(C_t)+M_{i}(D_t). \\ \end{array} \right.$$ (6.12)

Les moments du multi-ensemble $(C_{t_{opt}},f)$ peuvent donc être calculés incrémentalement à l'aide des équations 6.13. Les moments du multi-ensemble $(C-C_{t_{opt}},f)$ se déduisent des moments de $(C_{t_{opt}},f)$ par la proposition 1 sur l'additivité des moments. Une fois les moments des deux multi-ensembles calculés, on peut calculer leurs moyennes, leurs variances et leurs erreurs quadratiques grâce à la définitions 3 et à l'équation 5.1. Les moments, moyennes et erreurs quadratiques de chacun des multi-ensemble sont ensuite stockés dans les feuilles de l'arbre de découpe correspondant aux multi-ensembles.

Tableau 6.1: Ce tableau résume les principales heuristiques employées par les algorithmes de quantification basés sur une division récursive du multi-ensemble de départ.

		1	2	3	4
Choix du multi-ensemble	Erreur quadratique		$\star$	$\star$	$\star$
	Cardinal	$\star$
Choix d'un ensemble d'axes	Axes de coordonnées	$\star$			$\star$
	Axe principal		$\star$	$\star$
Choix de l'axe	Plus grande longueur	$\star$
	Plus grande variance		$\star$	$\star$	$\star$
Choix du plan	Plan médian	$\star$
	Minimisation de la variance		$\star$
	Minimisation de l'erreur			$\star$	$\star$

(1)	:	Méthode de Heckbert
(2)	:	Méthode de Wan and Wong
(3)	:	Méthode de Wu
(4)	:	Méthode de Braquelaire et Brun.