Keywords: Classification ascendante hiérarchique orientée, Espaces ultramétriques, Règles d'association, Représentation graphique

‡ Les corrections portées -suite à une relecture attentive -sont peu nombreuses, mineures et de pure forme : des espaces blancs oubliés, des parenthèses oubliées, remplacement d'un terme qualificatif par un autre plus approprié, remplacements de crochets par des parenthèses, etc ...

Hiérachies binaires et

Espaces ultramétriques orientés. Résumé : Les hiérarchies binaires orientées ont été introduites pour fournir une représentation graphique orientée d'une famille de règles implicatives d'association. Une telle structure étend d'une façon très spécifique celle sous jacente aux arbres binaires hiérarchiques de classification. Nous proposons ici une formalisation précise de ce nouveau type de structure. Une hiérarchie binaire orientée est définie comme une famille de couples (ordonnés) de parties de l'ensemble à organiser remplissant des conditions spécifiques. Une nouvelle notion d'ultramétricité binaire orientée est construite. le résultat fondamental consiste en la mise en correspondance bijective entre une structure binaire ultramétrique orientée et une hiérarchie binaire orientée. De plus, un algorithme est proposé pour passer de la structure ultramétrique à celle graphique d'un arbre binaire orienté et valué.

Introduction

Given a finite set E of entities (objects or descriptive attributes) and a similarity s, or a dissimilarity d, on E, the common objective of a hierarchical clustering is to gather in small classes the most similar entities and to separate the most dissimilar ones in different large classes (e.g. [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Gordon | Classification[END_REF][START_REF] Lerman | Classification et analyse ordinale des données[END_REF]). In the vast majority of cases, the measures s and d are symmetrical. However, stimulated by applications in various area (e.g. co-citation analysis, social exchange, psychology) some authors have considered asymmetric measures (e.g. [START_REF] Loevinger | A systematic approach to the construction and evaluation of tests of ability[END_REF][START_REF] Gras | Contribution à l'étude expérimentale et à l'analyse de certaines acquisitions cognitives et de certains objectifs didactiques en mathématiques[END_REF][START_REF] Lerman | Élaboration et évaluation d'un indice d'implication pour des données binaires i et ii[END_REF][START_REF] Zielman | Models for asymmetric proximities[END_REF][START_REF] Takeuchi | Asymmetric agglomerative hierarchical clustering algorithms and their evaluation[END_REF]. Yadohisa [START_REF] Yadohisa | Formulation of asymmetric agglomerative hierarchical clustering and graphical representation of its results[END_REF][START_REF] Takeuchi | Asymmetric agglomerative hierarchical clustering algorithms and their evaluation[END_REF]) has proposed the concept of asymmetrical agglomerative hierarchical clustering to take into account the asymmetry of the relationships in a dendrogram representation.

A specific case of asymmetrical measures is notably found in data mining when considering association rules. Relative to two boolean attributes a and b, an association rule of the form a → b means that "when a is T RU E, then usually b is also T RU E". Association rules differ from logical rules by tolerating few counter-examples; they evaluate an implicative tendency. This notion commonly appears in real-life corpuses where we can observe few individuals for which a is T RU E and b is F ALSE without questioning the general trend to have b when we have a. From the seminal works of Agrawal and al. in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] 1993 and Manilla and al. in 1994 [START_REF] Klementtinen | Finding interesting rules from large sets of discovered association rules[END_REF], association rules have become one of the major concepts used in data mining. Many measures have been proposed to quantify the strenght of the rule implicative tendency (see [START_REF] Guillet | Quality measures in data mining[END_REF] for a recent state-ofthe-art [START_REF] Guillet | Quality measures in data mining[END_REF]). The vast majority of them are non symmetrical: if Imp measures the implication degree between entity conjunctions, Imp (a, b) = Imp (b, a).

Different clustering algorithms have been proposed for structuring the rule sets (e.g. Toivonen et al. [START_REF] Toivonen | Pruning and grouping discovered association rules[END_REF], Lent et al. [START_REF] Lent | Clustering association rules[END_REF]). Most of them build partitions. But, in order to preserve the intrinsical asymmetry of the measures and to discover relationships at different granularity levels, [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF] [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF] has proposed a hierarchical model called afterwards "directed hierarchy" by [START_REF] Gras | Discovering r-rules with a directed hierarchy[END_REF] [START_REF] Gras | Discovering r-rules with a directed hierarchy[END_REF]. Internal nodes of the binary directed hierarchy can be in a sense "rules of rules": e.g. (a → b) → (c → d) whose premisse (a → b) and conclusion (c → d) can be rules themselves (see figure 1). We refer to Gras et al. (2008) [START_REF] Gras | Statistical Implicative Analysis[END_REF] for applications of this model in data mining and didactics.

A first formalization of the concept of binary directed hierarchy has been proposed in a restricted context (where Imp is the implication intensity (Gras and al. 2008)). In this paper, following a work set about by [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF][START_REF] Lerman | Sur les différentes expressions formelles d'une hiérarchie binaire symétrique ou implicative[END_REF] [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF][START_REF] Lerman | Sur les différentes expressions formelles d'une hiérarchie binaire symétrique ou implicative[END_REF], we reexamine this structure in a deeper more accurate and more complete framework. We first define a binary directed hierarchy as a set of ordered pairs of subsets of E which satisfy specific conditions. Then, we propose a directed version of the ultrametricity and show that in a directed ultrametric space the triangles remain isosceles. In these conditions we establish a new bijection theorem between a binary directed hierarchy and a directed ultrametric structure. Due to the orientation, the bijection requires additionnal conditions not present in the classical case.

More precisely, in section 2, the notion of directed binary hierarchy is defined in terms of a set of directed forks. Some of its basic properties are given. Section 3 is devoted to the notion analysis of directed ultrametrics. By defining the strict directed ultrametricity, we obtain a characterization of this new notion in terms of directed isosceles triangles, for which the basis length is strictly lower RR n°6815 than the common length of the two other sides. The main result of this paper is developed in section 4 where we establish the correspondence between a directed binary hierarchy and an associated directed ultrametric space. This result can be viewed as an extension of those obtained in [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF] where a hierarchical classification and an ultrametric numerical or ordinal similarity structure are formally associated. Final remarks and comments are considered in the conclusion (section 5).

Let us end this introduction by mentioning that this paper consists of a development of a short summary given in [START_REF] Kuntz | Directed binary hierarchies and directed ultrametrics[END_REF].

Directed hierarchies

In this section we introduce the notion of complete binary directed hierarchy on a finite set E. The main result is given in Theorem 1. We show that this structure gives rise to a total order on E. X and Y designate the two components of the directed fork (X, Y ). X and Y are called the left and the right components of the fork. X ∪ Y defines the basis of the directed fork. Thus, the nature of a fork is binary.

Definition 1 A directed fork of E is an ordered pair (X, Y ) of non empty disjoint subsets of E such that X = E and Y = E. The top of the directed fork (X, Y ) is formally represented by (X → Y, X ∪ Y ). X Y, XUY) ( Y X

Definition 2 A binary directed hierarchy

-→ H (E) is a set of directed forks of E which satisfies the following property: for each unordered pair {(X, Y ) , (Z, T )} of distinct directed forks belonging to

-→ H (E), where card (X ∪ Y ) ≤ card (Z ∪ T ), we have either (X ∪ Y ) ∩ (Z ∪ T ) = ∅ or X ∪ Y ⊆ Z or X ∪ Y ⊆ T . INRIA (X ∪ Y ) ∩ (Z ∪ T ) = ∅
will be called exclusion between the two directed forks (X, Y ) and (Z, T ). On the other hand, X ∪ Y ⊆ Z (resp. X ∪ Y ⊆ T ) will be called a left inclusion (resp., a right inclusion) of the fork (X, Y ) into the fork (Z, T ).

Proposition 1 For each directed fork (X, Y ) ∈ -→ H (E), there is no other di- rected fork (Z, T ) ∈ -→ H (E) such that X ∪ Y = Z ∪ T . In particular, (Y, X) / ∈ -→ H (E).
P roof P roof P roof : Let us assume that there exist two directed forks (X, Y ) and (Z, T ) for which X ∪ Y = Z ∪ T . Then, we have clearly:

(X ∪ Y ) ∩ (Z ∪ T ) = ∅
As a consequence we have either

X ∪ Y ⊆ Z or X ∪ Y ⊆ T
Obviously, none of inclusions can hold. Because, they are equivalent to either

Z ∪ T ⊆ Z or Z ∪ T ⊆ T
respectively. But, according to the definition of a fork, Z and T are disjoint and non empty. Hence, the previous equation is not valid. On the other hand, since Y ∪ X = X ∪ Y then we can derive Y ∪ X / ∈ -→ H (E).

Corollary 1 A directed fork (X, Y ) for which X ∪ Y = E is unique.
This corresponds to a particular case of Proposition 1.

Proposition 2 For every element x of E (x ∈ E), there is at most one directed fork for which the singleton subset {x} is one of its components.

P roof P roof P roof : Suppose that there are two distinct directed forks having each {x} as one of its components. For each of them two cases have to be considered according to the position of {x} in the ordered subset pair defining the directed fork. In fact, it is sufficient to consider the unique case where {x} is the left component of both directed forks. The proof for the three other cases is strictly analogous. In these conditions, let us denote by ({x}, Y ) and ({x}, Z) the two distinct directed forks for which {x} is their common left component. Without loss of generality, let us suppose that card(Y ) ≤ card(Z). We have

({x} ∪ Y ) ∩ ({x} ∪ Z) = ∅
According to the above Definition 2, we have either

{x} ∪ Y ⊆ {x} or {x} ∪ Y ⊆ Z Since {x} ∩ Y = ∅, {x} ∩ Z = ∅ and Y = ∅ , Z = ∅ none of these inclusions can hold.
There is a natural strict partial order on -→ H (E) that we denote by ≺ H : for any pair of directed forks (X, Y ) and (Z, T ) belonging to -→ H (E), (X, Y ) ≺ H (Z, T ) if and only if the two following conditions are satisfied:

1. (X ∪ Y ) ∩ (Z ∪ T ) = ∅ 2. card(X ∪ Y ) < card(Z ∪ T )
According to Definition 2 one has necessarily :

X ∪ Y ⊂ Z or X ∪ Y ⊂ T Definition 3
A binary directed hierarchy is complete when 1. for any singleton x ∈ E, there is exactly one directed fork of -→ H (E) such that one component is {x};

2. there is a directed fork (X, Y ) in -→ H (E) such that X ∪ Y = E; 3. for any directed fork (X, Y ) in -→ H (E) such that X ∪ Y = E, there exists a directed fork (X ′ , Y ′ ) in -→ H (E) such that either X ′ = X ∪Y or Y ′ = X ∪Y .
Relative to the above item 2 and from Corollary 1, the directed fork such that X ∪ Y = E is necessarily unique. Now, relative to the above item 3 and from Definition 2, the directed fork (X ′ , Y ′ ) is necessarily unique. To see this point let us suppose without loss of generality that X ′ = X ∪ Y and assume that there exists another fork (X ′′ , Y ′′ ) such that we have either:

X ′′ = X ∪ Y or Y ′′ = X ∪ Y
Without loss of generality one may suppose that card(X ′′ ∪Y ′′ ) ≤ card(X ′′ ∪ Y ′′ ). In these conditions and from Definition 2, if X ′′ = X ∪ Y , then we have necessarily X ′′ ∪ Y ′′ ⊂ X ′ = X ∪ Y and this inclusion cannot hold ((X ′′ ∩ Y ′′ ) = ∅). On the other hand, if Y ′′ = X ∪Y , we have necessarily X ′′ ∪Y ′′ ⊂ Y ′ = X ∪Y and, for the same reason this inclusion cannot hold.

(X ′ , Y ′ ) will be called the mother of (X, Y ). Finally, according to the strict partial order ≺ H it is easy to establish that there cannot exist a directed fork (Z, T ) strictly between (X, Y ) and (X ′ , Y ′ ); that is to say such that:

(X, Y ) ≺ H (Z, T ) ≺ H (X ′ , Y ′ ) Proposition 3 Let -→
H (E) be a complete binary directed hierarchy. Given an unordered pair {x, y} from E ({x, y} ∈ P 2 (E)), there exists necessarily a directed fork in -→ H (E) such that one component contains x and the other one contains y.

INRIA

P roof P roof P roof : Let us consider x as one of the two elements of {x, y}. From Definition 3 there is exactly one directed fork of -→ H (E) such that one component is {x}. Initializing with this directed fork, consider the increasing sequence of forks such that each fork is the mother of the preceding one. In this sequence of directed forks consider the first one such that its top defines a basis including x and y. Since the basis of the final directed fork is E, this directed fork does necessarily exist. By construction, each of x and y belongs to one of the two components of the latter directed fork.

Proposition 4 If

-→ H (E) is a complete binary hierarchy of directed forks, and let (x, y) ∈ E × E. Assume that there exists a fork (X, Y ) for which (x, y) ∈ X × Y , then this fork is unique.

P roof P roof P roof : This result can be deduced directly from Definition 2. Assume that we have two different directed forks (X, Y ) and (Z, T ) such that (x, y) ∈ (X, Y ) and (x, y) ∈ (Z, T ). In these conditions we have:

(X ∪ Y ) ∩ (Z ∪ T ) = ∅
Without loss of generality one may suppose that card(X ∪Y ) ≤ card(Z ∪T ). Then, we necessarily have one of these two alternatives:

1. X ∪ Y ⊆ Z 2. X ∪ Y ⊆ T
and neither of them is possible. Indeed, the first (resp., second) contradiction is due to y / ∈ Z (resp., x / ∈ T ).

Theorem 1 Let -→ H (E) be a complete binary directed hierarchy on E. The binary relation R H on E defined by

∀ (x, y) ∈ E × E, x = y, xR H y ⇔ ∃! (X, Y ) ∈ -→ H (E) , (x, y) ∈ X × Y
defines a strict total order on E.

P roof P roof P roof :

1. Antisymmetry : Let us consider an arbitrary ordered pair (x, y) belonging to E × E. The conjunction xR H y and yR H x is contradictory. Indeed,

xR H y ⇔ ∃!(X, Y ) ∈ -→ H (E) such that (x, y) ∈ X × Y yR H x ⇔ ∃!(Y ′ , X ′ ) ∈ -→ H (E) such that (y, x) ∈ Y ′ × X ′ Clearly, RR n°6815 (X ∪ Y ) ∩ (Y ′ ∪ X ′ ) = ∅
According to Definition 2 we have at least, one of the following alternatives:

1. X ∪ Y ⊆ X ′ ; 2. X ∪ Y ⊆ Y ′ ; 3. X ′ ∪ Y ′ ⊆ X; 4. X ′ ∪ Y ′ ⊆ Y . Since x / ∈ Y , x / ∈ Y ′ , y /
∈ X and y / ∈ X ′ , any of the four previous alternatives is possible.

Transitivity:

Let us show that ∀(x, y, t) ∈ E 3 , xR H y and yR H t ⇒ xR H t From the definition of R H , there are two directed forks (X, Y ) and (Y ′ , T ) in -→ H (E) such that: (x, y) ∈ X × Y and (y, t) ∈ Y ′ × T. Since y ∈ Y ∩ Y ′ , (X ∪ Y ) ∩ (Y ′ ∪ T ) = ∅.
Consequently, from Definition 2, we have either

X ∪ Y ⊂ Y ′ or Y ′ ∪ T ⊂ Y.
In the first case (x, t) ∈ Y ′ × T and then xR H t. The same conclusion holds for the second case where (x, t) ∈ X × Y .

Total order :

This property is a direct consequence of the Propositions 3 and4

. Let (x, y) ∈ E × E with x = y. By Proposition 3, there exists (X, Y ) ∈ -→ H (E) such that either (x, y) ∈ X × Y or (y, x) ∈ X × Y . If (x, y) ∈ X × Y Then by Proposition 4 (X, Y ) is unique and so xR H y. Similarly, if (y, x) ∈ X × Y , Proposition 4 implies yR H x.
Since R H defines a total order on E, there exists a unique bijection {1, 2, ..., n} -→ E, i → x i , compatible with the total order (recall n = card(E)). Let us denote by I E the interval on E defined by the totally ordered sequence (x 1 , x 2 , ..., x i , ..., x n ).

Corollary 2 Let (X, Y ) be a given directed fork of the complete binary directed hierarchy -→ H (E). By considering the restriction of R H on X and Y , (X, Y ) determines an ordered pair of two consecutive subintervals of (x 1 , x 2 , ..., x i , ..., x n ).

INRIA

P roof P roof P roof : A recursion argument allows to establish this property that we can call interval split property.

Consider the top fork that we denote (X 1 , Y 1 ) whose basis is

X 1 ∪ Y 1 = E. By definition: ∀(x 1 , y 1 ) ∈ X 1 × Y 1 , x 1 R H y 1
By denoting I X1 and I Y1 the subintervals defined by the restrictions of R H on X 1 and Y 1 respectively, I X1 and I Y1 are necessarily two connex, disjoint and complementary intervals of

I E . I X1 (resp., I Y1 ) is a begining (resp., ending) subinterval of I E . If I X1 has the form (x 1 , x 2 , ..., x c ), then I Y1 has the form (x c+1 , x c+2 , ..., x n ). X 1 ∪ Y 1 = E and X 1 ∩ Y 1 = ∅.
Now, let us consider an arbitrary fork (X, Y ) belonging to -→ H (E). There exists a unique sequence of ordered forks:

(X 1 , Y 1 ), (X 2 , Y 2 ), ..., (X m , Y m ) beginning with the initial fork (X 1 , Y 1 ) and ending with the fork (X m , Y m ) = (X, Y ) such that (X j , Y j ) is the mother fork of (X j+1 , Y j+1 ), 1 ≤ j ≤ m -1.
Assume that the interval split property is established till (X m , Y m ) and consider the two forks associated with X m and Y m , respectively. Now, let us denote by (X ′ m+1 , X ′′ m+1 ) the fork whose basis is X m and by (Y ′ m+1 , Y ′′ m+1 ) that whose basis is Y m . By the same argument used for the fork (X 1 , Y 1 ) derived from E, the restrictions of R H on X ′ m+1 and X ′′ m+1 (resp., on Y ′ m+1 and Y ′′ m+1 ) determine two connex, disjoint and complementary intervals of I Xm (resp., I Ym ). In these conditions the recursion is established.

Directed ultrametrics

In this section we define the notion of a directed ultrametric space on a finite set E. This notion depends on a notion of dissimilarity on E compatible with a total order R on E. Under these conditions, for x, y, z ∈ E a directed triangle (x, y, z) is such that xRy and yRz. The main result showed in theorems 2 and 3 consists in establishing that for a directed ultrametric space every directed triangle is isosceles having its basis strictly smaller than its equal sides.

Definition 4 Let R be a total order on E. A directed dissimilarity d R compat- ible with R is a mapping E × E → R + = R + ∪ {∞},
where R + is the set of non negative numbers, of E × E on the positive real numbers R + which satisfies the four following conditions :

1. for any x ∈ E, d R (x, x) = 0; 2. for any (x, y) ∈ E × E, x = y, 0 < d R (x, y) < +∞ if xRy; 3. for any ((x, y), (z, t)) ∈ (E × E) × (E × E), x = y and z = t, d R (x, y) < d R (t, z) if xRy and zRt;
4. for any triple (x, y, z) ∈ E 3 x = y, x = z, y = z, such that xRy and yRz,

then d R (x, z) > min {d R (x, y) , d R (y, z)}.
Definition 5 Let us consider a total order R on E and a compatible directed dissimilarity d R . Then, d R is called a directed ultrametric if, for any triple (x, y, z) ∈ E 3 such that xRy and yRz, the three conditions are satisfied:

1. d R (x, y) ≤ M ax {d R (x, z) , d R (y, z)}; 2. d R (x, z) ≤ M ax {d R (x, y) , d R (y, z)}; 3. d R (y, z) ≤ M ax {d R (x, y) , d R (x, z)}.
Moreover, the directed ultrametric is strict if 1 or 3 is strict.

Definition 6 Let us consider a total order R on E. A triple (x, y, z) ∈ E 3 , x = y = z, forms a directed triangle if xRy and yRz.

In order to distinguish this specific and important case an R-compatible directed ultrametric will be denoted d uR .

Theorem 2 Let us consider a total order R on E and a compatible directed ultrametric d uR compatible with R. We have either:

d uR (x, y) < d uR (x, z) = d uR (y, z) or d uR (y, z) < d uR (x, y) = d uR (x, z)
Thus, each directed triangle from R is isosceles in the metric space (E, d uR ) with basis length strictly smaller than the length of the two equal sides; the basis being either xy or yz. P roof P roof P roof : Two cases have to be distinguished:

1. d uR (x, y) ≤ d uR (y, z) 2. d uR (y, z) ≤ d uR (x, y)
Let us consider the first case where d uR (x, y) ≤ d uR (y, z). According to the condition 4 of Definition 4, necessarily,

d uR (x, z) > d uR (x, y)
Then, 3 of Definition 5 gives:

d uR (y, z) ≤ d uR (x, z).
On the other hand, 2 of Definition 5 gives:

d uR (x, z) ≤ d uR (y, z).
Finally,

d uR (y, z) = d uR (x, z) > d uR (x, y).
The proof for the second case where d uR (y, z) ≤ d uR (x, y) is analogous to that for the first case. The condition 4 of Definition 4 entails:

INRIA d uR (x, z) > d uR (y, z)
Then, 1 of Definition 5 gives:

d uR (x, y) ≤ d uR (x, z).
On the other hand, 2 of Definition 5 gives:

d uR (x, z) ≤ d uR (x, y).
Finally,

d uR (x, y) = d uR (x, z) > d uR (y, z).
Now, let us notice that for the first case the inequality 1 of Definition 5 is strict, but 3 of Definition 5 is reduced to an equality. On the contrary, for the second case, the inequality 3 of Definition 5 is strict, but 1 of Definition 5 is reduced to an equality.

A reciprocal property of the above theorem can be stated as follows:

Theorem 3 If R is a total order on E and d R is a directed dissimilarity such that, each directed triangle (x, y, z) is isosceles having its basis length strictly smaller than the common length of the other sides, then, d R is strictly ultrametric.

The proof is obvious.

Directed binary hierarchy and directed ultrametricity

Now and of course, the objective consists in obtaining as in the classical case [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF] a "bijection theorem" between the new concepts of valuated binary directed hierarchy and strictly directed ultrametric distance. However, due to the order on E introduced by the orientation, the bijection theorem requires additional restrictive conditions.

Directed ultrametricity associated with a directed binary hierarchy

A family of directed ultrametric distances is associated with a directed hierarchy -→ H (E). Each member of this family is defined by a strictly monotone numerical valuation on -→ H (E) endowed with ≺ H . This valuation gives rise to the directed ultrametric distance.

Theorem 4 Let

-→ H (E) be a complete binary directed hierarchy on E. From -→ H (E) can be derived a directed dissimilarity d RH which satisfies the following property: ∀(x, y, z), x = y = z , for which xR H y and yR H z , exactly one of the two following conditions holds:

1. d RH (x, y) < d RH (x, z) = d RH (y, z) 2. d RH (y, z) < d RH (x, y) = d RH (x, z)
In particular, d RH is ultrametric and compatible with R H .

P roof P roof P roof : Let us begin by recalling an elementary property concerning the existence of a strictly monotone valuation of a strict partial order on a finite set. By denoting this set by F and by designating ≺ F the strict partial order on F , there exists an infinity of strictly monotone numerical valuations on F endowed with ≺ F .

In these conditions, a numerical positive function ν can be defined on -→ H (E) endowed with the strict partial order ≺ H , defined in Section 2:

ν : -→ H (E) → R + such that, ∀((X, Y ), (Z, T )) ∈ -→ H (E) × -→ H (E) , (X, Y ) ≺ H (Z, T ) ⇒ ν(X, Y ) < ν(Z, T )
Now, let us consider an ordered pair (x, y) ∈ E × E, x = y, such that xR H y. From the previous Propositions 3 and 4 there is exactly one directed fork (X, Y ) ∈ -→ H (E), such that (x, y) ∈ X × Y . In these conditions, we set d RH (x, y) = ν(X, Y ). Otherwise, according to Definition 4, d RH (x, x) = 0 for every x ∈ E and -for simplicity reasons -we can set d RH (y, x) = +∞ for every (x, y) ∈ E × E such that xR H y and x = y. Since R H is a total order on E, this defines the map d RH : E × E → R + uniquely.

Let us now consider a directed triangle (x, y, z) ∈ E 3 associated with R H . By definition we have xR H y and yR H z. Let us denote by (X, Y ) and (Y ′ , Z) the two unique directed forks such that (x, y) ∈ (X, Y ) and (y, z) ∈ (Y ′ , Z), respectively. As (X ∪ Y ) ∩ (Y ′ ∪ Z) = ∅ (this intersection contains at least the element y), two cases are possible:

1. X ∪ Y ⊂ Y ′ 2. Y ′ ∪ Z ⊂ Y
Indeed, Definition2 implies that we have one of the four possibilities: (a)

X ∪ Y ⊂ Y ′ , (b) X ∪ Y ⊂ Z, (c) Y ′ ∪ Z ⊂ X and (d) Y ′ ∪ Z ⊂ Y . Case (b) cannot occur since y ∈ Y and y / ∈ Z as Y ′ ∩ Z = ∅, similarly (c) cannot happen as y ∈ Y ′ and y / ∈ X.
In case 1, (X, Y ) ≺ RH (Y, Z), thus ν(X, Y ) < ν(Y ′ , Z), consequently:

INRIA d RH (x, y) < d RH (y, z) Besides, (x, z) ∈ Y ′ × Z and (y, z) ∈ Y ′ × Z, then d RH (x, z) = d RH (y, z) = ν(Y ′ , Z)
. Finally, we have:

d RH (x, y) < d RH (x, z) = d RH (y, z)
The second case is completely similar. In that case (Y ′ , Z) ≺ RH (X, Y ) then ν(Y ′ , Z) < ν(X, Y ), consequently:

d RH (y, z) < d RH (x, y) Besides, (x, y) ∈ X × Y and (x, z) ∈ X × Y , then d RH (x, y) = d RH (x, z) = ν(X, Y
). Finally, we have:

d RH (y, z) < d RH (x, y) = d RH (x, z).

Directed binary hierarchy associated with a directed ultrametric dissimilarity

Let (E, R) be a totally ordered set and let d uR : E × E → R + be a compatible directed strict ultrametric dissimilarity (see Definitions 4 and 5). In this paragraph we establish a constructive mapping associating with d uR a valuated directed hierarchy. The valuated directed binary hierarchy is built recursively: at each step a family of directed forks ordered by the inclusion relationship (left inclusion or right inclusion) (see Definition 2).

Definitions

Recall that the strict compatible direct ultrametricity is equivalent to the following isosceles property: for any directed triangle (x, y, z) ∈ E 3 associated with R, we have either d uR (x, y) < d uR (x, z) = d uR (y, z) or d uR (y, z) < d uR (x, y) = d uR (x, z) (see Theorems 2 and 3 in Section 3). Now, let us denote by (x 1 , x 2 , ..., x i , ..., x n ) the ordered sequence of the elements of E, according to the total and complete order R. Thus we have:

∀i, 1 ≤ i ≤ n -1, x i Rx i+1 Consider an interval (x i , x i+1 , ..., x m ) (m ≤ n)
of the above sequence and associate with x i , the sequence of its distances d uR with the subsequent elements in this interval, namely:

{d uR (x i , x j )|i ≤ j ≤ m}
From the compatibility of d uR with respect to the total order R and from its ultrametricity it follows:

∀i, 1 ≤ i ≤ n -1, if i ≤ j ≤ n -1, then d uR (x i , x j ) ≤ d uR (x i , x j+1 ).
More precisely (Condition 4 in Definition 4),

d uR (x i , x j+1 ) > min{d uR (x i , x j ), d uR (x j , x j+1 )}
Then (x i , x j+1 ) cannot be the basis of the directed isosceles triangle (x i , x j , x j+1 ). Therefore,

d uR (x i , x j ) ≤ d uR (x i , x j+1 )
and then, the preceding numerical sequence {d uR (x i , x j )|i ≤ j ≤ m} is no decreasing.

Among the distance values {d uR (x i , x j )|i ≤ j ≤ m} associated with the ordered set defining the sequence (x i , x i+1 , ..., x m ), we assume that there are in all k m i distinct values that we retain and denote them by increasing order:

η m i (0) < η m i (1) < η m i (2) < ... < η m i (h) < ... < η m i (k m i ) where η m i (0) = 0 and η m i (k m i )
is the biggest value. Under these conditions we have:

{x ∈ E|d uR (x i , x) ≤ η m i (0)} = {x i } {x ∈ E|d uR (x i , x) ≤ η m i (k m i )} = {x i , x i+1 , ..., x m }
Let us now consider the following increasing sequence of discrete ordered intervals which constitute circles centered at x i :

X m i (h) 0≤h≤k m i = X m i (0), X m i (1), ..., X m i (k m i )
where

X m i (h) = {x i ′ ∈ {x i , ..., x m }|d uR (x i , x i ′ ) ≤ η m i (h)} Notice that
the left bound of all these intervals is x i . The sequence of these intervals is increasing with respect to the inclusion relation. The first interval equals (x i ) and the last one equals (x i , x i+1 , ..., x m ), totally ordered by R. We call x i the attraction center of the above series of circles.

Definition 7

The series of directed forks {(X m i (h),

X m i (h + 1) -X m i (h))|0 ≤ h ≤ k m i -1}
defines the fork decomposition of the totally R-ordered sequence (x i , x i+1 , ..., x m ), endowed with the directed ultrametric dissimilarity d uR , with respect to the attraction center x i .

INRIA

Definition 8

The valuated fork decomposition of the totally-R ordered sequence (x i , x i+1 , ..., x m ), endowed with the directed ultrametric dissimilarity d uR , with respect to the attraction center x i is defined by the series of the valuated directed forks

{ (X m i (h), X m i (h + 1) -X m i (h)), η m i (h + 1) |0 ≤ h ≤ k m i -1},
where η m i (h + 1) is the common d uR dissimilarity of two elements belonging to X m i (h) and X m i (h + 1) -X m i (h)) respectively.

First steps of the hierarchical construction

As the hierarchical building process is recursive we here detail the two first steps.

The first step consists in repeating the fork decomposition of (x 1 , x 2 , ..., x n ) endowed with the total order R and the directed ultrametric d uR . In this case the attraction center is x 1 and the increasing sequence of the η values (d uR (x 1 , x i ) dissimilarities) can be denoted by

η 1 (0) < η 1 (1) < η 1 (2) < ... < η 1 (h) < ... < η 1 (k 1 )
Let us consider the increasing sequence -with respect to the inclusion relation -of the discrete intervals which constitute circles centered at x 1 :

{X 1 (h)|0 ≤ h ≤ k 1 } where X 1 (h) = {x i |d uR (x 1 , x i ) ≤ η 1 (h)}
The first interval contains the single element x 1 and the last one the set E. The set difference X 1 (h + 1) -X 1 (h) between two successive intervals is itself a discrete interval. It can also be interpreted as an annulus defined by the difference between the two circles X 1 (h+1) and X 1 (h) centered at x 1 and having the radii η 1 (h + 1) and η 1 (h), respectively. Each directed fork (X 1 (h), X 1 (h + 1) -X 1 (h)) is included in the next one (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), (left inclusion) and the basis of (X 1 (h),

X 1 (h + 1) -X 1 (h)) is the left component of (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), 1 ≤ h ≤ k 1 -2.
Hence, considering the partial order ≺ H associated with the fork inclusion, we have:

(X 1 (h), X 1 (h + 1) -X 1 (h)) ≺ H (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)) Proposition 5 ∀h ∈ [0, k 1 ] ∀(x, y) ∈ X 1 (h) 2 , ∀(z, t) ∈ X 1 (h + 1) -X 1 (h) 2 d uR (x, z) = d uR (x, t) = d uR (y, z) = d uR (y, t) = η 1 (h + 1), d uR (x, y) < η 1 (h + 1
) and d uR (z, t) < η 1 (h + 1).

P roof P roof P roof : By construction we have:

d uR (x, z) = d uR (x, t) = η 1 (h + 1).
Due to the strict isosceles triangle property, it follows:

d uR (z, t) < d uR (x, z) = d uR (x, t) = η 1 (h + 1).
On the other hand, since, by construction, d uR (x, y) ≤ η 1 (h) and d uR (x, z) = η 1 (h + 1), the strict isosceles triangle property gives:

d uR (x, y) < d uR (x, z) = d uR (y, z) = η 1 (h + 1).
Now, by considering the strict isosceles triangle (x, y, t), where we already have d uR (x, y) < η 1 (h+1) and d uR (x, t) = η 1 (h+1), we deduce that d uR (y, t) = η 1 (h + 1).

To the directed fork (X 1 (h), X 1 (h + 1) -X 1 (h)) is assigned the numerical value η 1 (h + 1) which represents the common value of d uR between two respective elements from X 1 (h) and X 1 (h + 1) -X 1 (h). This value is strictly smaller than the next one η 1 (h + 2), assigned to the directed fork (X

1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), 0 ≤ h ≤ k 1 -2.
The second step consists in repeating fork decomposition of the discrete interval X 1 (h 1 + 1) -X 1 (h 1 where h 1 is the smallest value of h for which the right component of (X

1 (h), X 1 (h + 1) -X 1 (h)), 1 ≤ h ≤ k 1 -1, contains more than one single element. The first element of X 1 (h 1 + 1) -X 1 (h 1 ) denoted by x i(2)
is the new attraction center. As in the first step, the numerical value assigned to each new directed fork is equal to the value d uR between any two elements belonging respectively to its left and right components, respectively. The new directed forks are ranked on the right, after the previous ones according to their occurence order.

Algorithmic construction

The general process consists in recursively repeating from left to right, the fork decomposition of the right component of the first encountered directed fork including more than one element and for which the fork decomposition has not yet been applied. The new attraction center is the left element of the right component. Each new directed fork is valuated according to the d uR dissimilarity between its two components. The process goes on while there remains a directed fork with a right component of cardinality greater than one and on which any fork decomposition has yet been applied.

All the new built directed forks are valuated respectively according to their occurence order and ranked on the right in order to obtain a global sequence of the already built forks.

Algorithm DH (Directed-Hierarchy)

Let us define a φ structure as an ordered pair (X, Y ), η whose second component η is a numerical value and whose first component (X, Y ) is itself an ordered pair of two consecutive and disjoint intervals of the sequence (x 1 , x 2 , ..., x n ). By denoting v-fork-decomposition the valuated fork decomposition function defined in the previous Definition 8, one can associate with the INRIA v-fork-decomposition (x i , x i+1 , ..., x m ) (1 ≤ i < m ≤ n) the following array variable:

var D i : array[1, k m i -1]
of φ Now, let us denote by C the array variable which will contain the successive valuated fork decompositions leading to the construction of the directed binary hierarchy. In the latter, there are exactly n -1 internal nodes. Consequently, there are exactly n -1 fork decompositions and the dimension of C is n -1. Thus, we have:

var C : array[1, n -1] of φ { C[j] = ((X[j], Y [j]), η[j]) or C[j] = empty } {Initialization} for j:= 1 to n -1 C[j]:=empty endfor place D 1 in C from the index 1
{Progression and stop rule}

for j:= 1 to n -2 Y [j] := second interval component of C[j] if card(Y [j]) > 1 D j := v -f ork -decomposition(Y [j]) place D j in C from its first empty cell endfor 4.2.

Illustration

Let us denote by E = {x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } the set on which a strict total order R and a compatible strict directed ultrametric dissimilarity are given. Assume that R is defined as follows: R :

x 1 < x 2 < x 3 < x 4 < x 5 < x 6
The compatible strict directed ultrametric dissimilarity is given by the following table. It is easy to check that every directed triangle (there are in all 20) is isosceles with a basis length strictly lower than the common length of both sides:

x 1 x 2 x 3 x 4 x 5
x 6 x 1 0 0.9 0.9 0.9 0.9 0.9 x 2 ∞ 0 0.6 0.7 0.7 0.7

x 3 ∞ ∞ 0 0.7 0.7 0.7 x 4 ∞ ∞ ∞ 0 0.3 0.3 x 5 ∞ ∞ ∞ ∞ 0 0.1 x 6 ∞ ∞ ∞ ∞ ∞ 0
Let us now make explicit the sequence of the different steps of the algorithmic construction AC. With each built directed fork will be associated its valuation ν. The ν value is equal to the common ultrametric dissimilarity between two elements belonging respectively to the two components of the concerned directed fork.

First step: Valuated fork decomposition of E, totally ordered, with respect to x 1 as an attraction center:

x i (1) = x 1 .
The increasing sequence of the η values (d uR dissimilarities) from x 1 becomes here (0., 0.9). The associated increasing sequence of dicrete ordered intervals is:

((x 1 ), (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ))
The first sequence of valuated directed forks is:

INRIA (({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9)
This sequence is reduced to one directed fork whose valuation is 0.9. Its second component includes more than one single element of E. The latter corresponds to the subinterval (x 2 , x 3 , x 4 , x 5 , x 6 ).

Second step: Valuated fork decomposition of (x 2 , x 3 , x 4 , x 5 , x 6 ) with respect to its first element x 2 as an attraction center:

x i (2) = x 2 .
The increasing sequence of the η values from x 1 is (0., 0.6, 0.7, 0.7, 0.7). The associated increasing sequence of dicrete ordered intervals is:

((x 2 ), (x 2 , x 3 ), (x 2 , x 3 , x 4 , x 5 , x 6 ))
This fork decomposition leads to the following sequence of directed forks: (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7)

The new global sequence of built valuated directed forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7)

In this sequence the first directed fork whose second component contains more than one single element and for which valuated fork decomposition has not been yet considered is the third one. This second component is defined by the interval (x 4 , x 5 , x 6 ). The valuated fork decomposition has to be applied on it.

Third step: Valuated fork decomposition of (x 4 , x 5 , x 6 ) with respect to its first element x 4 as an attraction center: x i (3) = x 4 . The increasing sequence of the η values is (0., 0.3). The associated increasing sequence of discrete intervals is:

((x 4 ), (x 4 , x 5 , x 6 ))

This Valuated fork decomposition leads to the following sequence of directed forks which contains only one element:

(({x 4 }, {x 5 , x 6 }), ν = 0.3)
The new global sequence of built valuated forks is: (({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7), (({x 4 }, {x 5 , x 6 }), ν = 0.3)

In this sequence the first directed fork whose second component contains more than one single element and for which Valuated fork decomposition has not been yet considered is the fourth one. This second component is defined by the interval (x 5 , x 6 ). The Valuated fork decomposition has to be applied on it.

Fourth step: Valuated fork decomposition of (x 5 , x 6 ) with respect to its first element x 4 as an attraction center: x i (3) = x 4 . The increasing sequence of the η values is (0., 0.1). The associated increasing sequence of discrete intervals is:

((x 5 ), (x 5 , x 6 ))
This Valuated fork decomposition leads to the following sequence of directed forks which contains only one element:

(({x 5 }, {x 6 }), ν = 0.1)
The new global sequence of built valuated directed forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7), (({x 4 }, {x 5 , x 6 }), ν = 0.3), (({x 5 }, {x 6 }), ν = 0.1)

In this sequence of directed forks there does no remain any directed fork whose right member contains more than one single element and for which Valuated fork decomposition has not been applied. Then, the algorithmic construction process is ended. P roof P roof P roof : From the recursive nature of the algorithm, it is sufficient to prove this proposition for the first two steps. Four cases can be considerered.

Case 1: (left inclusion between forks built at step 1 ). For the series of directed forks

{(X 1 (h) , X 1 (h + 1) -X 1 (h)) ; 0 ≤ h ≤ k 1 -1} ,
the basis of any directed fork constitutes the left component of the next one. Thus, the left inclusion relationship is verified.

Case 2: (left inclusion between forks built at step 2 ). Let us consider the decomposition of X 1 h 1 + 1 -X 1 h 1 considered in the second step of the algorithm, and let us denote by x i(2) , x i(2)+1 , ..., x i(2)+k2 the discrete interval which contains k 2 + 1elements. Then,

d uR x i(2) , x j ≤ d uR x i(2) , x j ′ , for i(2) < j < j ′ ≤ i(2) + k 2 .
Hence, by construction, the left inclusion is checked for all the new built directed forks on x i(2) , x i(2)+1 , ..., x i(2)+k2 with the attraction center x i(2) .

Case 3: (right inclusion between forks built at step 2 and forks built at step 1 ). The new built directed forks on x i(2) , x i(2)+1 , ..., x i(2)+k2 with the attraction center x i(2) respect the right inclusion with the forks obtained from the fork decomposition of (x 1 , x 2 , ..., x n ), with the attraction center obtained from the fork decomposition of (x 1 , x 2 , ..., x n ), with the attraction center x i(1) = x 1 .

Case 4: (exclusion between forks with a right component of cardinality one).

The directed forks built on X h 1 whose the right component is restricted to a single element are disjoint from the built forks whose basis is included in

X 1 h 1 + 1 -X 1 h 1 .
Lemma 2 . Let (x i , x j )be any ordered pair of E (x i Rx j ). In the directed fork set built by the algorithm DH, there exists a unique directed fork (X, Y )such that (x i , x j ) ∈ X × Y . P roof P roof P roof : As the initial fork decomposition starts on (x 1 , x 2 , ..., x n ) which contains {x i , x j }, there exists at least one directed fork buit by the algorithm DH which contains x i and x j . Let us denote by (X l (g) , X l (g + 1) -X l (g)) the smallest one : {x i , x j } ∈ X l (g + 1) and card (X l (g + 1)) is minimum among the set of directed forks built by the DH algorithm.

X l (g) can not contain a single element which is not x i . Indeed, in this case, {x i , x j } ⊂ X l (g + 1) -X l (g), which is in contradiction with the assumption : the fork decomposition of X l (g + 1) -X l (g) would lead to a directed fork whose basis contains x i and x j and whose cardinality is strictly smaller than card (X l (g + 1)).

X l (g) can not contain more than one single element such that {x i , x j } ⊂ X l (g). Otherwise, we would have card (X l (g)) < card (X l (g + 1)).

If X l (g) contains one single element which is x i , then necessarily x j belongs to X l (g + 1) -X l (g).

X l (g + 1) -X l (g) can not contain one single element which is not x j . Otherwise, we would have {x i , x j } ⊂ X l (g) and card (X l (g)) < card (X l (g + 1)).

X l (g + 1)-X l (g) can not contain more than one single element s.t. {x i , x j } ⊂ X l (g + 1)-X l (g). Otherwise, the fork decomposition of X l (g + 1)-X l (g)would lead to a directed fork whose basis contains x i and x j and whose cardinality is strictly smaller than card (X l (g + 1)).

Consequently, we necessarily have (x i , x j ) ∈ X l (g) × (X l (g + 1) -X l (g)) and d uR (x i , x j ) is the common value between any pairs of elements from respectively X l (g) and X l (g + 1).

Theorem 5 To a total order R on E and a compatible directed ultrametric dissimilarity d uR on E, the algorithmic construction DH associates a unique complete directed binary hierarchy valuated by d uR .

The proof is directly derived from the above Property 5 and Lemmas 1 and 2.

Conclusion and further work

Directed binary hierarchy is a new combinatorial structure devoted to data organization in case where a specific asymmetrical similarity measure is relevant. This structure has been characterized and studied in terms of a set of directed forks. A specific notion of directed ultrametric depending on a total order on the organized set, has been defined and studied with respect to several aspects. An important point concerns its characterization in terms of directed isosceles triangles. The main result obtained here consists of establishing the correspondence between these two previous structures. As mentioned in the introduction, this result is an extension of the "bijection theorem" obtained in the classical symmetrical case [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF]. However, for the latter, two versions can be distinguished: numerical [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF] and ordinal [START_REF] Lerman | Les bases de la classification automatique[END_REF]. For the first, the correspondence is established up to a strictly increasing function on the ultrametric distances. But, for the second version, the bijection associates two equally finite spaces, the represented set and the representation set. Ordinal directed ultrametric space can also be considered in this work. One other facet may consist in establishing a formal correspondence between the formalization of this new specific hierarchical structure and those considered in the literature. Thus, it is easy to establish that if in the metric space there does not exist equilateral triangle, INRIA then Condition 4 of Definition 4 is more general than Robinson condition [START_REF] Robinson | A model for chronological ordering of archeological deposits[END_REF] adapted to an asymmetrical dissimilarity. On the other hand, one can relate our formal presentation to the classification formalization in terms of a hypergraph (E, K) (see [START_REF] Brucker | Eléments de classification[END_REF]). In our case as in the ascendant hierarchical classification, E is a set of elements and represents the vertice set.The edge set K is defined by all subsets of E corresponding to the tops of the different forks. Due to the orientation specific results or specific formalization can be obtained in the case of directed hierarchies.

The objective is now to define a complete framework to build and analyse directed hierarchies for real-life applications. It requires aggregation criteria adapted to the directed forks, an efficient algorithm and indicators for interpretation aiding. A first attempt was proposed in [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF][START_REF] Gras | Significativité des niveaux d'une hiérarchie orientée en analyse statistique implicative[END_REF] in the context of rule mining. Besides, a mathematical and statistical analysis of different criterion types is provided in [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF]. However, the aggregation criterion and the indicators defined to study the directed hierarchy are strongly dependent on the implicative statistical analysis framework in which all these works have been developed (see [START_REF] Gras | An overview of the statistical implicative analysis (sia) development[END_REF]). We believe that the proposed algorithm is general enough to be easily adapted to any kind of dissimilarity.

Figure 1 :

 1 Figure 1: Tree associated with a binary directed hierarchy

Figure 2 :

 2 Figure 2: Directed fork X → Y does mean a directed junction from the subset X to the subset Y .X and Y designate the two components of the directed fork (X, Y ). X and Y are called the left and the right components of the fork. X ∪ Y defines the basis of the directed fork. Thus, the nature of a fork is binary.

Figure 3 : 4 . 2 . 5 PropertiesLemma 1

 34251 Figure 3: Directed tree associated with the built series of directed forks

RR n°6815

ACKNOWLEDGEMENT

We are indebted to Professor Benjamin Enriquez of the University Louis Pasteur of Strasbourg for his relevant remarks and suggestions which have improved the presentation of this article.


Lerman
email: lerman@irisa.fr

Pascale Kuntz
email: pascale.kuntz@polytech.univ-nantes.fr

Directed binary hierarchies and

Keywords: Directed ascendant hierarchical classification, Ultrametric spaces, Association rules, Graphical representation

Directed binary hierarchies have been introduced in order to give a graphical reduced representation of a family of association rules. This type of structure extends in a very specific way that underlying binary hierarchical classification. In this paper an accurate formalization of this new structure is studied. A binary directed hierarchy is defined as a set of ordered pairs of subsets of the initial individual set satisfying specific conditions. New notion of directed ultrametricity is studied. The main result consists of establishing a bijective correspondence between a directed ultrametric space and a directed binary hierarchy. Moreover, an algorithm is proposed in order to transform a directed ultrametric structure into a graphical representation associated with a directed binary hierarchy.

ISRAËL-CÉSAR LERMAN ET PASCALE KUNTZ

Hiérachies binaires et Espaces ultramétriques orientés.

Résumé : Les hiérarchies binaires orientées ont été introduites pour fournir une représentation graphique orientée d'une famille de règles implicatives d'association. Une telle structure étend d'une façon très spécifique celle sous jacente aux arbres binaires hiérarchiques de classification. Nous proposons ici une formalisation précise de ce nouveau type de structure. Une hiérarchie binaire orientée est définie comme une famille de couples (ordonnés) de parties de l'ensemble à organiser remplissant des conditions spécifiques. Une nouvelle notion d'ultramétricité binaire orientée est construite. le résultat fondamental consiste en la mise en correspondance bijective entre une structure binaire ultramétrique orientée et une hiérarchie binaire orientée. De plus, un algorithme est proposé pour passer de la structure ultramétrique à celle graphique d'un arbre binaire orienté et valué.

Mots clés : Classification ascendante hiérarchique orientée, Espaces ultramétriques, Règles d'association, Représentation graphique

Introduction

Given a finite set E of entities (objects or descriptive attributes) and a similarity s, or a dissimilarity d, on E, the common objective of a hierarchical clustering is to gather in small classes the most similar entities and to separate the most dissimilar ones in different large classes (e.g. [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Gordon | Classification[END_REF][START_REF] Lerman | Classification et analyse ordinale des données[END_REF]). In the vast majority of cases, the measures s and d are symmetrical. However, stimulated by applications in various area (e.g. co-citation analysis, social exchange, psychology) some authors have considered asymmetric measures (e.g. [START_REF] Loevinger | A systematic approach to the construction and evaluation of tests of ability[END_REF][START_REF] Gras | Contribution à l'étude expérimentale et à l'analyse de certaines acquisitions cognitives et de certains objectifs didactiques en mathématiques[END_REF][START_REF] Lerman | Élaboration et évaluation d'un indice d'implication pour des données binaires i et ii[END_REF][START_REF] Zielman | Models for asymmetric proximities[END_REF][START_REF] Takeuchi | Asymmetric agglomerative hierarchical clustering algorithms and their evaluation[END_REF]. Yadohisa [START_REF] Yadohisa | Formulation of asymmetric agglomerative hierarchical clustering and graphical representation of its results[END_REF][START_REF] Takeuchi | Asymmetric agglomerative hierarchical clustering algorithms and their evaluation[END_REF]) has proposed the concept of asymmetrical agglomerative hierarchical clustering to take into account the asymmetry of the relationships in a dendrogram representation.

A specific case of asymmetrical measures is notably found in data mining when considering association rules. Relative to two boolean attributes a and b, an association rule of the form a → b means that "when a is T RU E, then usually b is also T RU E". Association rules differ from logical rules by tolerating few counterexamples; they evaluate an implicative tendency. This notion commonly appears in real-life corpuses where we can observe few individuals for which a is T RU E and b is F ALSE without questioning the general trend to have b when we have a. From the seminal works of Agrawal and al. in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] 1993 and Manilla and al. in 1994 [START_REF] Klementtinen | Finding interesting rules from large sets of discovered association rules[END_REF], association rules have become one of the major concepts used in data mining. Many measures have been proposed to quantify the strenght of the rule implicative tendency (see [START_REF] Guillet | Quality measures in data mining[END_REF] for a recent state-of-the-art [START_REF] Guillet | Quality measures in data mining[END_REF]). The vast majority of them are non symmetrical: if Imp measures the implication degree between entity conjunctions, Imp (a, b) = Imp (b, a).

Different clustering algorithms have been proposed for structuring the rule sets (e.g. Toivonen et al. [START_REF] Toivonen | Pruning and grouping discovered association rules[END_REF], Lent et al. [START_REF] Lent | Clustering association rules[END_REF]). Most of them build partitions. But, in order to preserve the intrinsical asymmetry of the measures and to discover relationships at different granularity levels, [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF] [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF] has proposed a hierarchical model called afterwards "directed hierarchy" by [START_REF] Gras | Discovering r-rules with a directed hierarchy[END_REF] [START_REF] Gras | Discovering r-rules with a directed hierarchy[END_REF]. Internal nodes of the binary directed hierarchy can be in a sense "rules of rules": e.g. (a → b) → (c → d) whose premisse (a → b) and conclusion (c → d) can be rules themselves (see figure 1). We refer to Gras et al. (2008) [START_REF] Gras | Statistical Implicative Analysis[END_REF] for applications of this model in data mining and didactics.

A first formalization of the concept of binary directed hierarchy has been proposed in a restricted context (where Imp is the implication intensity (Gras and al. 2008)). In this paper, following a work set about by [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF][START_REF] Lerman | Sur les différentes expressions formelles d'une hiérarchie binaire symétrique ou implicative[END_REF] [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF][START_REF] Lerman | Sur les différentes expressions formelles d'une hiérarchie binaire symétrique ou implicative[END_REF], we reexamine this structure in a deeper more accurate and more complete framework. We first define a binary directed hierarchy as a set of ordered pairs of subsets of E which satisfy specific conditions. Then, we propose a directed version of the ultrametricity and show that in a directed ultrametric space the triangles remain isosceles. In these conditions we establish a new bijection theorem between a binary directed hierarchy and a directed ultrametric structure. Due to the orientation, the bijection requires additionnal conditions not present in the classical case. More precisely, in section 2, the notion of directed binary hierarchy is defined in terms of a set of directed forks. Some of its basic properties are given. Section 3 is devoted to the notion analysis of directed ultrametrics. By defining the strict directed ultrametricity, we obtain a characterization of this new notion in terms of directed isosceles triangles, for which the basis length is strictly lower than the common length of the two other sides. The main result of this paper is developed in section 4 where we establish the correspondence between a directed binary hierarchy and an associated directed ultrametric space. This result can be viewed as an extension of those obtained in [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF] where a hierarchical classification and an ultrametric numerical or ordinal similarity structure are formally associated. Final remarks and comments are considered in the conclusion (section 5).

PI n˚1922

Let us end this introduction by mentioning that this paper consists of a development of a short summary given in [START_REF] Kuntz | Directed binary hierarchies and directed ultrametrics[END_REF].

Directed hierarchies

In this section we introduce the notion of complete binary directed hierarchy on a finite set E. The main result is given in Theorem 1. We show that this structure gives rise to a total order on E.

Definition 1 A directed fork of E is an ordered pair (X, Y ) of non empty disjoint subsets of E such that X = E and Y = E. The top of the directed fork (X, Y ) is formally represented by (X → Y, X ∪ Y ). X Y, XUY) ( Y X Figure 2: Directed fork X → Y
does mean a directed junction from the subset X to the subset Y . X and Y designate the two components of the directed fork (X, Y ). X and Y are called the left and the right components of the fork. X ∪ Y defines the basis of the directed fork. Thus, the nature of a fork is binary.

Definition 2 A binary directed hierarchy -→ H (E) is a set of directed forks of E which satisfies the follow- ing property: for each unordered pair {(X, Y ) , (Z, T )} of distinct directed forks belonging to -→ H (E), where card (X ∪ Y ) ≤ card (Z ∪ T ), we have either (X ∪ Y ) ∩ (Z ∪ T ) = ∅ or X ∪ Y ⊆ Z or X ∪ Y ⊆ T .
(X ∪ Y ) ∩ (Z ∪ T ) = ∅ will be called exclusion between the two directed forks (X, Y ) and (Z, T ). On the other hand, X ∪ Y ⊆ Z (resp. X ∪ Y ⊆ T ) will be called a left inclusion (resp., a right inclusion) of the fork (X, Y ) into the fork (Z, T ).

Proposition 1 For each directed fork (X, Y ) ∈ -→ H (E), there is no other directed fork (Z, T ) ∈ -→ H (E) such that X ∪ Y = Z ∪ T . In particular, (Y, X) / ∈ -→ H (E).
P roof P roof P roof : Let us assume that there exist two directed forks (X, Y ) and (Z, T ) for which X ∪ Y = Z ∪ T . Then, we have clearly:

(X ∪ Y ) ∩ (Z ∪ T ) = ∅
As a consequence we have either

X ∪ Y ⊆ Z or X ∪ Y ⊆ T
Obviously, none of inclusions can hold. Because, they are equivalent to either

Z ∪ T ⊆ Z or Z ∪ T ⊆ T
respectively. But, according to the definition of a fork, Z and T are disjoint and non empty. Hence, the previous equation is not valid. On the other hand, since Y ∪ X = X ∪ Y then we can derive Y ∪ X / ∈ -→ H (E).

Corollary 1 A directed fork (X, Y ) for which X ∪ Y = E is unique.
This corresponds to a particular case of Proposition 1.

Irisa

Proposition 2 For every element x of E (x ∈ E), there is at most one directed fork for which the singleton subset {x} is one of its components.

P roof P roof P roof : Suppose that there are two distinct directed forks having each {x} as one of its components. For each of them two cases have to be considered according to the position of {x} in the ordered subset pair defining the directed fork. In fact, it is sufficient to consider the unique case where {x} is the left component of both directed forks. The proof for the three other cases is strictly analogous. In these conditions, let us denote by ({x}, Y ) and ({x}, Z) the two distinct directed forks for which {x} is their common left component. Without loss of generality, let us suppose that card(Y ) ≤ card(Z). We have

({x} ∪ Y ) ∩ ({x} ∪ Z) = ∅
According to the above Definition 2, we have either

{x} ∪ Y ⊆ {x} or {x} ∪ Y ⊆ Z Since {x} ∩ Y = ∅, {x} ∩ Z = ∅ and Y = ∅ , Z = ∅ none of these inclusions can hold.
There is a natural strict partial order on -→ H (E) that we denote by ≺ H : for any pair of directed forks (X, Y ) and (Z, T ) belonging to -→ H (E), (X, Y ) ≺ H (Z, T ) if and only if the two following conditions are satisfied:

1. (X ∪ Y ) ∩ (Z ∪ T ) = ∅ 2. card(X ∪ Y ) < card(Z ∪ T )
According to Definition 2 one has necessarily :

X ∪ Y ⊂ Z or X ∪ Y ⊂ T Definition 3
A binary directed hierarchy is complete when 1. for any singleton x ∈ E, there is exactly one directed fork of -→ H (E) such that one component is {x};

2. there is a directed fork (X, Y ) in -→ H (E) such that X ∪ Y = E; 3. for any directed fork (X, Y ) in -→ H (E) such that X ∪ Y = E, there exists a directed fork (X ′ , Y ′ ) in -→ H (E) such that either X ′ = X ∪ Y or Y ′ = X ∪ Y .
Relative to the above item 2 and from Corollary 1, the directed fork such that X ∪ Y = E is necessarily unique. Now, relative to the above item 3 and from Definition 2, the directed fork (X ′ , Y ′ ) is necessarily unique. To see this point let us suppose without loss of generality that X ′ = X ∪ Y and assume that there exists another fork (X ′′ , Y ′′ ) such that we have either:

X ′′ = X ∪ Y or Y ′′ = X ∪ Y
Without loss of generality one may suppose that card(X ′′ ∪ Y ′′ ) ≤ card(X ′′ ∪ Y ′′ ). In these conditions and from Definition 2, if

X ′′ = X ∪ Y , then we have necessarily X ′′ ∪ Y ′′ ⊂ X ′ = X ∪ Y and this inclusion cannot hold ((X ′′ ∩ Y ′′ ) = ∅). On the other hand, if Y ′′ = X ∪ Y , we have necessarily X ′′ ∪ Y ′′ ⊂ Y ′ = X ∪ Y
and, for the same reason this inclusion cannot hold.

(X ′ , Y ′ ) will be called the mother of (X, Y ). Finally, according to the strict partial order ≺ H it is easy to establish that there cannot exist a directed fork (Z, T ) strictly between (X, Y ) and (X ′ , Y ′ ); that is to say such that:

(X, Y ) ≺ H (Z, T ) ≺ H (X ′ , Y ′ ) PI n˚1922 Proposition 3 Let -→
H (E) be a complete binary directed hierarchy. Given an unordered pair {x, y} from E ({x, y} ∈ P 2 (E)), there exists necessarily a directed fork in -→ H (E) such that one component contains x and the other one contains y. P roof P roof P roof : Let us consider x as one of the two elements of {x, y}. From Definition 3 there is exactly one directed fork of -→ H (E) such that one component is {x}. Initializing with this directed fork, consider the increasing sequence of forks such that each fork is the mother of the preceding one. In this sequence of directed forks consider the first one such that its top defines a basis including x and y. Since the basis of the final directed fork is E, this directed fork does necessarily exist. By construction, each of x and y belongs to one of the two components of the latter directed fork.

Proposition 4 If

-→ H (E) is a complete binary hierarchy of directed forks, and let (x, y) ∈ E × E. Assume that there exists a fork (X, Y ) for which (x, y) ∈ X × Y , then this fork is unique.

P roof P roof P roof : This result can be deduced directly from Definition 2. Assume that we have two different directed forks (X, Y ) and (Z, T ) such that (x, y) ∈ (X, Y ) and (x, y) ∈ (Z, T ). In these conditions we have:

(X ∪ Y ) ∩ (Z ∪ T ) = ∅
Without loss of generality one may suppose that card(X ∪ Y ) ≤ card(Z ∪ T ). Then, we necessarily have one of these two alternatives:

1. X ∪ Y ⊆ Z 2. X ∪ Y ⊆ T
and neither of them is possible. Indeed, the first (resp., second) contradiction is due to y / ∈ Z (resp., x / ∈ T ).

Theorem 1 Let -→ H (E) be a complete binary directed hierarchy on E. The binary relation R H on E defined by

∀ (x, y) ∈ E × E, x = y, xR H y ⇔ ∃! (X, Y ) ∈ -→ H (E) , (x, y) ∈ X × Y
defines a strict total order on E.

P roof P roof P roof :

1. Antisymmetry : Let us consider an arbitrary ordered pair (x, y) belonging to E × E. The conjunction

xR H y and yR H x is contradictory. Indeed, xR H y ⇔ ∃!(X, Y ) ∈ -→ H (E) such that (x, y) ∈ X × Y yR H x ⇔ ∃!(Y ′ , X ′ ) ∈ -→ H (E) such that (y, x) ∈ Y ′ × X ′ Clearly, (X ∪ Y ) ∩ (Y ′ ∪ X ′ ) = ∅
According to Definition 2 we have at least, one of the following alternatives:

Irisa 1. X ∪ Y ⊆ X ′ ; 2. X ∪ Y ⊆ Y ′ ; 3. X ′ ∪ Y ′ ⊆ X; 4. X ′ ∪ Y ′ ⊆ Y . Since x / ∈ Y , x / ∈ Y ′ , y / ∈ X and y / ∈ X ′ ,
(x, y) ∈ X × Y and (y, t) ∈ Y ′ × T. Since y ∈ Y ∩ Y ′ , (X ∪ Y ) ∩ (Y ′ ∪ T ) = ∅.
Consequently, from Definition 2, we have either

X ∪ Y ⊂ Y ′ or Y ′ ∪ T ⊂ Y.
In the first case (x, t) ∈ Y ′ × T and then xR H t. The same conclusion holds for the second case where (x, t) ∈ X × Y .

Total order :

This property is a direct consequence of the Propositions 3 and 4. Let (x, y)

∈ E × E with x = y. By Propo- sition 3, there exists (X, Y ) ∈ -→ H (E) such that either (x, y) ∈ X × Y or (y, x) ∈ X × Y . If (x, y) ∈ X × Y Then by Proposition 4 (X, Y ) is unique and so xR H y. Similarly, if (y, x) ∈ X×Y , Proposition 4 implies yR H x.
Since R H defines a total order on E, there exists a unique bijection {1, 2, ..., n} -→ E, i → x i , compatible with the total order (recall n = card(E)). Let us denote by I E the interval on E defined by the totally ordered sequence (x 1 , x 2 , ..., x i , ..., x n ).

Corollary 2 Let (X, Y ) be a given directed fork of the complete binary directed hierarchy -→ H (E). By considering the restriction of R H on X and Y , (X, Y ) determines an ordered pair of two consecutive subintervals of (x 1 , x 2 , ..., x i , ..., x n ).

P roof P roof P roof : A recursion argument allows to establish this property that we can call interval split property.

Consider the top fork that we denote (X 1 , Y 1 ) whose basis is X 1 ∪ Y 1 = E. By definition:

∀(x 1 , y 1 ) ∈ X 1 × Y 1 , x 1 R H y 1
By denoting I X1 and I Y1 the subintervals defined by the restrictions of R H on X 1 and Y 1 respectively, I X1 and I Y1 are necessarily two connex, disjoint and complementary intervals of

I E . I X1 (resp., I Y1 ) is a begining (resp., ending) subinterval of I E . If I X1 has the form (x 1 , x 2 , ..., x c ), then I Y1 has the form (x c+1 , x c+2 , ..., x n ). X 1 ∪ Y 1 = E and X 1 ∩ Y 1 = ∅.
Now, let us consider an arbitrary fork (X, Y ) belonging to -→ H (E). There exists a unique sequence of ordered forks:

(X 1 , Y 1 ), (X 2 , Y 2 ), ..., (X m , Y m )
beginning with the initial fork (X 1 , Y 1 ) and ending with the fork

(X m , Y m ) = (X, Y ) such that (X j , Y j ) is the mother fork of (X j+1 , Y j+1 ), 1 ≤ j ≤ m -1.
Assume that the interval split property is established till (X m , Y m ) and consider the two forks associated with X m and Y m , respectively. Now, let us denote by (X ′ m+1 , X ′′ m+1 ) the fork whose basis is X m and by (Y ′ m+1 , Y ′′ m+1 ) that whose basis is Y m . By the same argument used for the fork (X 1 , Y 1 ) derived from E, the restrictions of R H on X ′ m+1 and X ′′ m+1 (resp., on Y ′ m+1 and Y ′′ m+1 ) determine two connex, disjoint and complementary intervals of I Xm (resp., I Ym ). In these conditions the recursion is established.

PI n˚1922 3 Directed ultrametrics

In this section we define the notion of a directed ultrametric space on a finite set E. This notion depends on a notion of dissimilarity on E compatible with a total order R on E. Under these conditions, for x, y, z ∈ E a directed triangle (x, y, z) is such that xRy and yRz. The main result showed in theorems 2 and 3 consists in establishing that for a directed ultrametric space every directed triangle is isosceles having its basis strictly smaller than its equal sides.

Definition 4 Let R be a total order on E. A directed dissimilarity d R compatible with R is a mapping E ×E → R + = R + ∪ {∞}, where R + is the set of non negative numbers, of E × E on the positive real numbers R + which satisfies the four following conditions :

1. for any x ∈ E, d R (x, x) = 0; 2. for any (x, y) ∈ E × E, x = y, 0 < d R (x, y) < +∞ if xRy; 3. for any ((x, y), (z, t)) ∈ (E × E) × (E × E), x = y and z = t, d R (x, y) < d R (t, z) if xRy and zRt; 4. for any triple (x, y, z) ∈ E 3 x = y, x = z, y = z, such that xRy and yRz, then d R (x, z) > min {d R (x, y) , d R (y, z)}.
Definition 5 Let us consider a total order R on E and a compatible directed dissimilarity d R . Then, d R is called a directed ultrametric if, for any triple (x, y, z) ∈ E 3 such that xRy and yRz, the three conditions are satisfied:

1. d R (x, y) ≤ M ax {d R (x, z) , d R (y, z)}; 2. d R (x, z) ≤ M ax {d R (x, y) , d R (y, z)}; 3. d R (y, z) ≤ M ax {d R (x, y) , d R (x, z)}.
Moreover, the directed ultrametric is strict if 1 or 3 is strict.

Definition 6 Let us consider a total order R on E. A triple (x, y, z) ∈ E 3 , x = y = z, forms a directed triangle if xRy and yRz.

In order to distinguish this specific and important case an R-compatible directed ultrametric will be denoted d uR .

Theorem 2 Let us consider a total order R on E and a compatible directed ultrametric d uR compatible with R. We have either:

d uR (x, y) < d uR (x, z) = d uR (y, z) or d uR (y, z) < d uR (x, y) = d uR (x, z)
Thus, each directed triangle from R is isosceles in the metric space (E, d uR ) with basis length strictly smaller than the length of the two equal sides; the basis being either xy or yz. P roof P roof P roof : Two cases have to be distinguished: On the other hand, 2 of Definition 5 gives:

d uR (x, z) ≤ d uR (y, z).
Finally,

d uR (y, z) = d uR (x, z) > d uR (x, y).
The proof for the second case where d uR (y, z) ≤ d uR (x, y) is analogous to that for the first case. The condition 4 of Definition 4 entails:

d uR (x, z) > d uR (y, z)
Then, 1 of Definition 5 gives:

d uR (x, y) ≤ d uR (x, z).
On the other hand, 2 of Definition 5 gives:

d uR (x, z) ≤ d uR (x, y).
Finally,

d uR (x, y) = d uR (x, z) > d uR (y, z).
Now, let us notice that for the first case the inequality 1 of Definition 5 is strict, but 3 of Definition 5 is reduced to an equality. On the contrary, for the second case, the inequality 3 of Definition 5 is strict, but 1 of Definition 5 is reduced to an equality.

A reciprocal property of the above theorem can be stated as follows:

Theorem 3 If R is a total order on E and d R is a directed dissimilarity such that, each directed triangle (x, y, z) is isosceles having its basis length strictly smaller than the common length of the other sides, then, d R is strictly ultrametric.

The proof is obvious.

Directed binary hierarchy and directed ultrametricity

Now and of course, the objective consists in obtaining as in the classical case [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF] a "bijection theorem" between the new concepts of valuated binary directed hierarchy and strictly directed ultrametric distance. However, due to the order on E introduced by the orientation, the bijection theorem requires additional restrictive conditions.

Directed ultrametricity associated with a directed binary hierarchy

A family of directed ultrametric distances is associated with a directed hierarchy -→ H (E). Each member of this family is defined by a strictly monotone numerical valuation on -→ H (E) endowed with ≺ H . This valuation gives rise to the directed ultrametric distance.

PI n˚1922

Theorem 4 Let -→ H (E) be a complete binary directed hierarchy on E. From -→ H (E) can be derived a directed dissimilarity d RH which satisfies the following property: ∀(x, y, z), x = y = z , for which xR H y and yR H z , exactly one of the two following conditions holds:

1. d RH (x, y) < d RH (x, z) = d RH (y, z) 2. d RH (y, z) < d RH (x, y) = d RH (x, z)
In particular, d RH is ultrametric and compatible with R H . P roof P roof P roof : Let us begin by recalling an elementary property concerning the existence of a strictly monotone valuation of a strict partial order on a finite set. By denoting this set by F and by designating ≺ F the strict partial order on F , there exists an infinity of strictly monotone numerical valuations on F endowed with ≺ F .

In these conditions, a numerical positive function ν can be defined on -→ H (E) endowed with the strict partial order ≺ H , defined in Section 2:

ν : -→ H (E) → R + such that, ∀((X, Y ), (Z, T )) ∈ -→ H (E) × -→ H (E) , (X, Y ) ≺ H (Z, T ) ⇒ ν(X, Y ) < ν(Z, T )
Now, let us consider an ordered pair (x, y) ∈ E × E, x = y, such that xR H y. From the previous Propositions 3 and 4 there is exactly one directed fork (X, Y ) ∈ -→ H (E), such that (x, y) ∈ X × Y . In these conditions, we set d RH (x, y) = ν(X, Y ). Otherwise, according to Definition 4, d RH (x, x) = 0 for every x ∈ E and -for simplicity reasons -we can set d RH (y, x) = +∞ for every (x, y) ∈ E × E such that xR H y and x = y. Since R H is a total order on E, this defines the map d RH : E × E → R + uniquely.

Let us now consider a directed triangle (x, y, z) ∈ E 3 associated with R H . By definition we have xR H y and yR H z. Let us denote by (X, Y ) and (Y ′ , Z) the two unique directed forks such that (x, y) ∈ (X, Y ) and (y, z) ∈ (Y ′ , Z), respectively. As (X ∪ Y ) ∩ (Y ′ ∪ Z) = ∅ (this intersection contains at least the element y), two cases are possible:

1. X ∪ Y ⊂ Y ′ 2. Y ′ ∪ Z ⊂ Y
Indeed, Definition2 implies that we have one of the four possibilities:

(a) X ∪ Y ⊂ Y ′ , (b) X ∪ Y ⊂ Z, (c) Y ′ ∪ Z ⊂ X and (d) Y ′ ∪ Z ⊂ Y . Case (b) cannot occur since y ∈ Y and y / ∈ Z as Y ′ ∩ Z = ∅, similarly (c) cannot happen as y ∈ Y ′ and y / ∈ X. In case 1, (X, Y ) ≺ RH (Y, Z), thus ν(X, Y ) < ν(Y ′ , Z), consequently: d RH (x, y) < d RH (y, z) Besides, (x, z) ∈ Y ′ × Z and (y, z) ∈ Y ′ × Z, then d RH (x, z) = d RH (y, z) = ν(Y ′ , Z)
. Finally, we have:

d RH (x, y) < d RH (x, z) = d RH (y, z)
The second case is completely similar. In that case (Y ′ , Z) ≺ RH (X, Y ) then ν(Y ′ , Z) < ν(X, Y ), consequently:

d RH (y, z) < d RH (x, y) Besides, (x, y) ∈ X × Y and (x, z) ∈ X × Y , then d RH (x, y) = d RH (x, z) = ν(X, Y
). Finally, we have:

d RH (y, z) < d RH (x, y) = d RH (x, z).
Irisa

Directed binary hierarchy associated with a directed ultrametric dissimilarity

Let (E, R) be a totally ordered set and let d uR : E × E → R + be a compatible directed strict ultrametric dissimilarity (see Definitions 4 and 5). In this paragraph we establish a constructive mapping associating with d uR a valuated directed hierarchy. The valuated directed binary hierarchy is built recursively: at each step a family of directed forks ordered by the inclusion relationship (left inclusion or right inclusion) (see Definition 2).

Definitions

Recall that the strict compatible direct ultrametricity is equivalent to the following isosceles property: for any directed triangle (x, y, z) ∈ E 3 associated with R, we have either d uR (x, y) < d uR (x, z) = d uR (y, z) or d uR (y, z) < d uR (x, y) = d uR (x, z) (see Theorems 2 and 3 in Section 3). Now, let us denote by (x 1 , x 2 , ..., x i , ..., x n ) the ordered sequence of the elements of E, according to the total and complete order R. Thus we have:

∀i, 1 ≤ i ≤ n -1, x i Rx i+1
Consider an interval

(x i , x i+1 , ..., x m ) (m ≤ n)
of the above sequence and associate with x i , the sequence of its distances d uR with the subsequent elements in this interval, namely:

{d uR (x i , x j )|i ≤ j ≤ m}
From the compatibility of d uR with respect to the total order R and from its ultrametricity it follows:

∀i, 1 ≤ i ≤ n -1, if i ≤ j ≤ n -1, then d uR (x i , x j ) ≤ d uR (x i , x j+1 ).
More precisely (Condition 4 in Definition 4), d uR (x i , x j+1 ) > min{d uR (x i , x j ), d uR (x j , x j+1 )} Then (x i , x j+1 ) cannot be the basis of the directed isosceles triangle (x i , x j , x j+1 ). Therefore,

d uR (x i , x j ) ≤ d uR (x i , x j+1 )
and then, the preceding numerical sequence {d uR (x i , x j )|i ≤ j ≤ m} is no decreasing.

Among the distance values {d uR (x i , x j )|i ≤ j ≤ m} associated with the ordered set defining the sequence (x i , x i+1 , ..., x m ), we assume that there are in all k m i distinct values that we retain and denote them by increasing order:

η m i (0) < η m i (1) < η m i (2) < ... < η m i (h) < ... < η m i (k m i ) where η m i (0) = 0 and η m i (k m i )
is the biggest value. Under these conditions we have:

{x ∈ E|d uR (x i , x) ≤ η m i (0)} = {x i } {x ∈ E|d uR (x i , x) ≤ η m i (k m i )} = {x i , x i+1 , ..., x m }
Let us now consider the following increasing sequence of discrete ordered intervals which constitute circles centered at x i :

X m i (h) 0≤h≤k m i = X m i (0), X m i (1), ..., X m i (k m i ) PI n˚1922
where

X m i (h) = {x i ′ ∈ {x i , ..., x m }|d uR (x i , x i ′ ) ≤ η m i (h)} Notice that
the left bound of all these intervals is x i . The sequence of these intervals is increasing with respect to the inclusion relation. The first interval equals (x i ) and the last one equals (x i , x i+1 , ..., x m ), totally ordered by R. We call x i the attraction center of the above series of circles.

Definition 7

The series of directed forks {(X m i (h),

X m i (h + 1) -X m i (h))|0 ≤ h ≤ k m i -1}
defines the fork decomposition of the totally R-ordered sequence (x i , x i+1 , ..., x m ), endowed with the directed ultrametric dissimilarity d uR , with respect to the attraction center x i .

Definition 8

The valuated fork decomposition of the totally-R ordered sequence (x i , x i+1 , ..., x m ), endowed with the directed ultrametric dissimilarity d uR , with respect to the attraction center x i is defined by the series of the valuated directed forks

{ (X m i (h), X m i (h + 1) -X m i (h)), η m i (h + 1) |0 ≤ h ≤ k m i -1},
where η m i (h + 1) is the common d uR dissimilarity of two elements belonging to X m i (h) and X m i (h + 1) -X m i (h)) respectively.

First steps of the hierarchical construction

As the hierarchical building process is recursive we here detail the two first steps.

The first step consists in repeating the fork decomposition of (x 1 , x 2 , ..., x n ) endowed with the total order R and the directed ultrametric d uR . In this case the attraction center is x 1 and the increasing sequence of the η values (d uR (x 1 , x i ) dissimilarities) can be denoted by

η 1 (0) < η 1 (1) < η 1 (2) < ... < η 1 (h) < ... < η 1 (k 1 )
Let us consider the increasing sequence -with respect to the inclusion relation -of the discrete intervals which constitute circles centered at x 1 :

{X 1 (h)|0 ≤ h ≤ k 1 } where X 1 (h) = {x i |d uR (x 1 , x i ) ≤ η 1 (h)}
The first interval contains the single element x 1 and the last one the set E. The set difference X 1 (h + 1) -X 1 (h) between two successive intervals is itself a discrete interval. It can also be interpreted as an annulus defined by the difference between the two circles X 1 (h + 1) and X 1 (h) centered at x 1 and having the radii η 1 (h + 1) and η 1 (h), respectively. Each directed fork (X 1 (h),

X 1 (h + 1) -X 1 (h)) is included in the next one (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), (left inclusion) and the basis of (X 1 (h), X 1 (h + 1) -X 1 (h)) is the left component of (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), 1 ≤ h ≤ k 1 -2.
Hence, considering the partial order ≺ H associated with the fork inclusion, we have:

(X 1 (h), X 1 (h + 1) -X 1 (h)) ≺ H (X 1 (h + 1), X 1 (h + 2) -X 1 (h + 1)) Proposition 5 ∀h ∈ [0, k 1 ] ∀(x, y) ∈ X 1 (h) 2 , ∀(z, t) ∈ X 1 (h + 1) -X 1 (h) 2 d uR (x, z) = d uR (x, t) = d uR (y, z) = d uR (y, t) = η 1 (h + 1), d uR (x, y) < η 1 (h + 1
) and d uR (z, t) < η 1 (h + 1).

P roof P roof P roof : By construction we have:

d uR (x, z) = d uR (x, t) = η 1 (h + 1).
Due to the strict isosceles triangle property, it follows:

d uR (z, t) < d uR (x, z) = d uR (x, t) = η 1 (h + 1).

Irisa

On the other hand, since, by construction, d uR (x, y) ≤ η 1 (h) and d uR (x, z) = η 1 (h + 1), the strict isosceles triangle property gives:

d uR (x, y) < d uR (x, z) = d uR (y, z) = η 1 (h + 1).
Now, by considering the strict isosceles triangle (x, y, t), where we already have d uR (x, y) < η 1 (h + 1) and d uR (x, t) = η 1 (h + 1), we deduce that d uR (y, t) = η 1 (h + 1).

To the directed fork (X 1 (h), X 1 (h + 1) -X 1 (h)) is assigned the numerical value η 1 (h + 1) which represents the common value of d uR between two respective elements from X 1 (h) and X 1 (h + 1) -X 1 (h). This value is strictly smaller than the next one η 1 (h + 2), assigned to the directed fork (X

1 (h + 1), X 1 (h + 2) -X 1 (h + 1)), 0 ≤ h ≤ k 1 -2.
The second step consists in repeating fork decomposition of the discrete interval X 1 (h 1 + 1) -X 1 (h 1 where h 1 is the smallest value of h for which the right component of (X 1 (h),

X 1 (h + 1) -X 1 (h)), 1 ≤ h ≤ k 1 -1, contains more than one single element. The first element of X 1 (h 1 + 1) -X 1 (h 1 ) denoted by x i(2)
is the new attraction center. As in the first step, the numerical value assigned to each new directed fork is equal to the value d uR between any two elements belonging respectively to its left and right components, respectively. The new directed forks are ranked on the right, after the previous ones according to their occurence order.

Algorithmic construction

The general process consists in recursively repeating from left to right, the fork decomposition of the right component of the first encountered directed fork including more than one element and for which the fork decomposition has not yet been applied. The new attraction center is the left element of the right component. Each new directed fork is valuated according to the d uR dissimilarity between its two components. The process goes on while there remains a directed fork with a right component of cardinality greater than one and on which any fork decomposition has yet been applied.

All the new built directed forks are valuated respectively according to their occurence order and ranked on the right in order to obtain a global sequence of the already built forks.

Algorithm DH (Directed-Hierarchy)

Let us define a φ structure as an ordered pair (X, Y ), η whose second component η is a numerical value and whose first component (X, Y ) is itself an ordered pair of two consecutive and disjoint intervals of the sequence (x 1 , x 2 , ..., x n ). By denoting v-fork-decomposition the valuated fork decomposition function defined in the previous Definition 8, one can associate with the v-fork-decomposition (x i , x i+1 , ..., x m ) (1 ≤ i < m ≤ n) the following array variable:

var D i : array[1, k m i -1] of φ Now, let
us denote by C the array variable which will contain the successive valuated fork decompositions leading to the construction of the directed binary hierarchy. In the latter, there are exactly n -1 internal nodes. Consequently, there are exactly n -1 fork decompositions and the dimension of C is n -1. Thus, we have:

var C : array[1, n -1] of φ { C[j] = ((X[j], Y [j]), η[j]) or C[j] = empty } PI n˚1922 {Initialization} for j:= 1 to n -1 C[j]:=empty endfor place D 1 in C from the index 1
{Progression and stop rule}

for j:= 1 to n -2 Y [j] := second interval component of C[j] if card(Y [j]) > 1 D j := v -f ork -decomposition(Y [j]) place D j in C from its first empty cell endfor 4.2.

Illustration

Let us denote by E = {x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } the set on which a strict total order R and a compatible strict directed ultrametric dissimilarity are given. Assume that R is defined as follows: R :

x 1 < x 2 < x 3 < x 4 < x 5 < x 6
The compatible strict directed ultrametric dissimilarity is given by the following table. It is easy to check that every directed triangle (there are in all 20) is isosceles with a basis length strictly lower than the common length of both sides:

x 1 x 2 x 3 x 4 x 5
x 6 x 1 0 0.9 0.9 0.9 0.9 0.9 x 2 ∞ 0 0.6 0.7 0.7 0.7

x 3 ∞ ∞ 0 0.7 0.7 0.7 x 4 ∞ ∞ ∞ 0 0.3 0.3 x 5 ∞ ∞ ∞ ∞ 0 0.1 x 6 ∞ ∞ ∞ ∞ ∞ 0
Let us now make explicit the sequence of the different steps of the algorithmic construction AC. With each built directed fork will be associated its valuation ν. The ν value is equal to the common ultrametric dissimilarity between two elements belonging respectively to the two components of the concerned directed fork.

First step: Valuated fork decomposition of E, totally ordered, with respect to x 1 as an attraction center:

x i (1) = x 1 .
The increasing sequence of the η values (d uR dissimilarities) from x 1 becomes here (0., 0.9). The associated increasing sequence of dicrete ordered intervals is:

((x 1 ), (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ))
The first sequence of valuated directed forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9)
This sequence is reduced to one directed fork whose valuation is 0.9. Its second component includes more than one single element of E. The latter corresponds to the subinterval (x 2 , x 3 , x 4 , x 5 , x 6 ).

Second step: Valuated fork decomposition of (x 2 , x 3 , x 4 , x 5 , x 6 ) with respect to its first element x 2 as an attraction center:

x i (2) = x 2 .
The increasing sequence of the η values from x 1 is (0., 0.6, 0.7, 0.7, 0.7). The associated increasing sequence of dicrete ordered intervals is:

Irisa ((x 2 ), (x 2 , x 3 ), (x 2 , x 3 , x 4 , x 5 , x 6 ))
This fork decomposition leads to the following sequence of directed forks: (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7)

The new global sequence of built valuated directed forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7)

In this sequence the first directed fork whose second component contains more than one single element and for which valuated fork decomposition has not been yet considered is the third one. This second component is defined by the interval (x 4 , x 5 , x 6 ). The valuated fork decomposition has to be applied on it.

Third step: Valuated fork decomposition of (x 4 , x 5 , x 6 ) with respect to its first element x 4 as an attraction center: x i (3) = x 4 . The increasing sequence of the η values is (0., 0.3). The associated increasing sequence of discrete intervals is:

((x 4 ), (x 4 , x 5 , x 6 ))
This Valuated fork decomposition leads to the following sequence of directed forks which contains only one element:

(({x 4 }, {x 5 , x 6 }), ν = 0.3)
The new global sequence of built valuated forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7), (({x 4 }, {x 5 , x 6 }), ν = 0.3) In this sequence the first directed fork whose second component contains more than one single element and for which Valuated fork decomposition has not been yet considered is the fourth one. This second component is defined by the interval (x 5 , x 6 ). The Valuated fork decomposition has to be applied on it.

Fourth step: Valuated fork decomposition of (x 5 , x 6 ) with respect to its first element x 4 as an attraction center: x i (3) = x 4 . The increasing sequence of the η values is (0., 0.1). The associated increasing sequence of discrete intervals is: ((x 5 ), (x 5 , x 6 ))

This Valuated fork decomposition leads to the following sequence of directed forks which contains only one element:

(({x 5 }, {x 6 }), ν = 0.1)
The new global sequence of built valuated directed forks is:

(({x 1 }, {x 2 , x 3 , x 4 , x 5 , x 6 }), ν = 0.9), (({x 2 }, {x 3 }), ν = 0.6), (({x 2 , x 3 }, {x 4 , x 5 , x 6 }), ν = 0.7), (({x 4 }, {x 5 , x 6 }), ν = 0.3), (({x 5 }, {x 6 }), ν = 0.1)
In this sequence of directed forks there does no remain any directed fork whose right member contains more than one single element and for which Valuated fork decomposition has not been applied. Then, the algorithmic construction process is ended. P roof P roof P roof : From the recursive nature of the algorithm, it is sufficient to prove this proposition for the first two steps. Four cases can be considerered.

PI n˚1922

Case 1: (left inclusion between forks built at step 1 ). For the series of directed forks

{(X 1 (h) , X 1 (h + 1) -X 1 (h)) ; 0 ≤ h ≤ k 1 -1} ,
the basis of any directed fork constitutes the left component of the next one. Thus, the left inclusion relationship is verified.

Case 2: (left inclusion between forks built at step 2 ). Let us consider the decomposition of X 1 h 1 + 1 -X 1 h 1 considered in the second step of the algorithm, and let us denote by x i(2) , x i(2)+1 , ..., x i(2)+k2 the discrete interval which contains k 2 + 1elements. Then,

d uR x i(2) , x j ≤ d uR x i(2) , x j ′ , for i(2) < j < j ′ ≤ i(2) + k 2 .
Hence, by construction, the left inclusion is checked for all the new built directed forks on x i(2) , x i(2)+1 , ..., x i(2)+k2 with the attraction center x i(2) .

Case 3: (right inclusion between forks built at step 2 and forks built at step 1 ). The new built directed forks on x i(2) , x i(2)+1 , ..., x i(2)+k2 with the attraction center x i(2) respect the right inclusion with the forks obtained from the fork decomposition of (x 1 , x 2 , ..., x n ), with the attraction center obtained from the fork decomposition of (x 1 , x 2 , ..., x n ), with the attraction center x i(1) = x 1 .

Case 4: (exclusion between forks with a right component of cardinality one). The directed forks built on X h 1 whose the right component is restricted to a single element are disjoint from the built forks whose basis is

Irisa included in X 1 h 1 + 1 -X 1 h 1 .
Lemma 2 . Let (x i , x j )be any ordered pair of E (x i Rx j ). In the directed fork set built by the algorithm DH, there exists a unique directed fork (X, Y )such that (x i , x j ) ∈ X × Y .

P roof P roof P roof : As the initial fork decomposition starts on (x 1 , x 2 , ..., x n ) which contains {x i , x j }, there exists at least one directed fork buit by the algorithm DH which contains x i and x j . Let us denote by (X l (g) , X l (g + 1) -X l (g)) the smallest one : {x i , x j } ∈ X l (g + 1) and card (X l (g + 1)) is minimum among the set of directed forks built by the DH algorithm.

X l (g) can not contain a single element which is not x i . Indeed, in this case, {x i , x j } ⊂ X l (g + 1) -X l (g), which is in contradiction with the assumption : the fork decomposition of X l (g + 1) -X l (g) would lead to a directed fork whose basis contains x i and x j and whose cardinality is strictly smaller than card (X l (g + 1)).

X l (g) can not contain more than one single element such that {x i , x j } ⊂ X l (g). Otherwise, we would have card (X l (g)) < card (X l (g + 1)).

If X l (g) contains one single element which is x i , then necessarily x j belongs to X l (g + 1) -X l (g).

X l (g + 1) -X l (g) can not contain one single element which is not x j . Otherwise, we would have {x i , x j } ⊂ X l (g) and card (X l (g)) < card (X l (g + 1)).

X l (g + 1) -X l (g) can not contain more than one single element s.t. {x i , x j } ⊂ X l (g + 1) -X l (g). Otherwise, the fork decomposition of X l (g + 1) -X l (g)would lead to a directed fork whose basis contains x i and x j and whose cardinality is strictly smaller than card (X l (g + 1)).

Consequently, we necessarily have (x i , x j ) ∈ X l (g) × (X l (g + 1) -X l (g)) and d uR (x i , x j ) is the common value between any pairs of elements from respectively X l (g) and X l (g + 1).

Theorem 5 To a total order R on E and a compatible directed ultrametric dissimilarity d uR on E, the algorithmic construction DH associates a unique complete directed binary hierarchy valuated by d uR .

The proof is directly derived from the above Property 5 and Lemmas 1 and 2.

Conclusion and further work

Directed binary hierarchy is a new combinatorial structure devoted to data organization in case where a specific asymmetrical similarity measure is relevant. This structure has been characterized and studied in terms of a set of directed forks. A specific notion of directed ultrametric depending on a total order on the organized set, has been defined and studied with respect to several aspects. An important point concerns its characterization in terms of directed isosceles triangles. The main result obtained here consists of establishing the correspondence between these two previous structures. As mentioned in the introduction, this result is an extension of the "bijection theorem" obtained in the classical symmetrical case [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF][START_REF] Lerman | Les bases de la classification automatique[END_REF]. However, for the latter, two versions can be distinguished: numerical [START_REF] Benz Écri | L'Analyse des Donnés[END_REF][START_REF] Johnson | Hierarchical clustering schemes[END_REF] and ordinal [START_REF] Lerman | Les bases de la classification automatique[END_REF]. For the first, the correspondence is established up to a strictly increasing function on the ultrametric distances. But, for the second version, the bijection associates two equally finite spaces, the represented set and the representation set. Ordinal directed ultrametric space can also be considered in this work. One other facet may consist in establishing a formal correspondence between the formalization of this new specific hierarchical structure and those considered in the literature. Thus, it is easy to establish that if in the metric space there does not exist equilateral triangle, then Condition 4 of Definition 4 is more general than Robinson condition [START_REF] Robinson | A model for chronological ordering of archeological deposits[END_REF] adapted to an asymmetrical dissimilarity. On the other hand, one can relate our formal presentation to the classification formalization in terms of a hypergraph (E, K) (see [START_REF] Brucker | Eléments de classification[END_REF]). In our case as in the ascendant hierarchical classification, E is a set of elements and represents the vertice set.The edge set K is defined by all subsets of E corresponding to the tops of the different forks. Due to the orientation specific results or specific formalization can be obtained in the case of directed hierarchies.

PI n˚1922

  A T O I R E S P U B L I C A T I O N I N T E R N E N o I R I S A CAMPUS UNIVERSITAIRE DE BEAULIEU -35042 RENNES CEDEX -FRANCE ISSN 1166-8687 1922 DIRECTED BINARY HIERARCHIES AND DIRECTED ULTRAMETRICS.

Figure 1 :

 1 Figure 1: Tree associated with a binary directed hierarchy

1 .

 1 d uR (x, y) ≤ d uR (y, z) 2. d uR (y, z) ≤ d uR (x, y) Let us consider the first case where d uR (x, y) ≤ d uR (y, z). According to the condition 4 of Definition 4, necessarily, d uR (x, z) > d uR (x, y) Then, 3 of Definition 5 gives: Irisa d uR (y, z) ≤ d uR (x, z).

Figure 3 :Lemma 1

 31 Figure 3: Directed tree associated with the built series of directed forks

  any of the four previous alternatives is possible.

2. Transitivity: Let us show that ∀(x, y, t) ∈ E 3 , xR H y and yR H t ⇒ xR H t From the definition of R H , there are two directed forks (X, Y ) and (Y ′ , T ) in -→ H (E) such that:

Lerman Kuntz

The objective is now to define a complete framework to build and analyse directed hierarchies for real-life applications. It requires aggregation criteria adapted to the directed forks, an efficient algorithm and indicators for interpretation aiding. A first attempt was proposed in [START_REF] Gras | L'implicationstatistique -Nouvelle méthode exploratoire de données[END_REF][START_REF] Gras | Significativité des niveaux d'une hiérarchie orientée en analyse statistique implicative[END_REF] in the context of rule mining. Besides, a mathematical and statistical analysis of different criterion types is provided in [START_REF] Lerman | Analyse logique, combinatoire et statistique de la construction d'une hiérarchie binaire implicative; niveaux et noeuds significatifs[END_REF]. However, the aggregation criterion and the indicators defined to study the directed hierarchy are strongly dependent on the implicative statistical analysis framework in which all these works have been developed (see [START_REF] Gras | An overview of the statistical implicative analysis (sia) development[END_REF]). We believe that the proposed algorithm is general enough to be easily adapted to any kind of dissimilarity.

ACKNOWLEDGEMENT

We are indebted to Professor Benjamin Enriquez of the University Louis Pasteur of Strasbourg for his relevant remarks and suggestions which have improved the presentation of this article.