Hoel Le Capitaine

Carl Frélicot
email: cfrelico@univ-lr.fr

A Class-Selective Rejection Scheme based on Blockwise Similarity of Typicality Degrees

Overlapping classes and outliers can significantly decrease a classifier performance. We adress here the problem of giving a classifier the ability to reject some patterns either for ambiguity or for distance in order to improve its performance. Given a set of typicality degrees for a pattern to be classified, we use an operator based on triangular norms and a discrete Sugeno integral to quantify their blockwise similarities. We propose a new class-selective rejection scheme which uses this operator outputs. We present the resulting algorithm which allows to assign a pattern to zero, one or several classes, and show its efficiency on real data sets.

Introduction

The problem of aggregating collections of numerical or ordinal data to obtain a typical value is present in many decision systems. Aggregation operators are used to obtain an overall value for each alternative, which is exploited to establish a final decision. In the context of supervised pattern classification, such a decision consists in assigning objects (or patterns) to one class based on the aggregation of degrees related to the given classes (posterior probabilities, membership values, ...). It has been proved that the misclassification risk significantly be reduced by allowing a classifier to reject extraneous and/or ambiguous patterns [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF][START_REF] Dubuisson | A statistical decision rule with incomplete knowledge about classes[END_REF][START_REF] Ha | The optimum class-selective rejection rules[END_REF]. Thus, a classifier with reject options allows to assign a pattern to zero (distance rejection), one (exclusive classification) or several (ambiguity rejection) classes. Among the possible approaches, the fuzzy one has received more attention in the last few decades because of its ability to manage imprecise and/or incomplete data [START_REF] Grabisch | Pattern Recognition -From Classical to Modern Approaches, chapter Fuzzy pattern recognition by fuzzy integrals and fuzzy rules[END_REF]. In this framework, we propose a new classification scheme with reject options, based on an operator which aggregates class-degrees of typicality of a pattern to be classified.

Fuzzy Aggregation Operators

Let us recall basic definitions of fuzzy operators that will be used to combine the values of interest, i.e. the pattern class-degrees of typicality. Depending on properties, aggregation functions can be classified into several categories: conjunctive, disjunctive, compensatory, and so on. We restrict on conjunctive and disjunctive functions. By definition, the output of a conjunctive operator is lower or equal than the minimum value, whereas the output of a disjunctive operator is greater or equal than the maximum value. Beyond these operators, we choose to use the triangular norms because of their ability to generalize the logical AND and OR crisp operators to fuzzy sets, see [START_REF] Klement | Logical, Algebraic, Analytic, and Probabilistic Aspects of Triangular Norms[END_REF] for a survey. Briefly, a triangular norm (or t-norm) is a binary operation on the unit interval : [0, 1] 2 → [0, 1] which is commutative, associative, non decreasing and has 1 for neutral element. Thus, a t-norm is conjunctive and the minimum operator ∧ is the greatest tnorm. Alternatively, a trianglar conorm (or t-conorm) is the dual binary operation ⊥ : [0, 1] 2 → [0, 1] having the same properties except the latter: its neutral element is 0. Thus, a t-conorm ⊥ is disjunctive and the maximum operator ∨ is the lowest t-conorm. Typical examples of dual couples (t-norm, t-conorm) that will be used in the sequel are given in Table 1.

Table 1. Typical triangular norm couples

Standard a S b = min(a, b) a⊥ S b = max(a, b) Algebraic a A b = a b a⊥ A b = a + b -a b Hamacher a H b = ab γ+(1-γ)(a+b-ab) a⊥ H b = a+b+(γ-2)ab 1+(γ-1)ab
We will use another fuzzy aggregation operator, the Sugeno integral in its discrete form. It computes the mean value of a function with respect to a fuzzy mea-sure m, which is a non-additive measure of uncertainty, i.e. more general than a possibility one and therefore a probability one. The integral of a function µ is defined by

S m = n i=1 µ(x i ) ∧ m(A (i) ) (1)
where

A (i) = {x (i) , • • • , x (n) } with respect to a permu- tation so that µ(x (i) ) ≤ • • • ≤ µ(x (n)
). This integral is widely used in decision making, and in particular for pattern recognition [START_REF] Grabisch | Pattern Recognition -From Classical to Modern Approaches, chapter Fuzzy pattern recognition by fuzzy integrals and fuzzy rules[END_REF] because of its ability to model some kind of interaction between features describing a pattern x.

3. The Class-selective Rejection Scheme

Classifier design

Let Ω = {ω 1 , • • • , ω c } be a set of c classes and x an unknown pattern described by p features. Classifier design aims at defining rules that can associate x ∈ R p with one class of Ω. It generally consists of two steps L (labeling) and H (hardening):

• L : x → µ(x) = t (µ 1 (x), . . . , µ c (x)) ∈ L •c , de-
pending on the mathematical framework the classifier relies on, e.g.

L pc = [0, 1] c for degrees of typ- icality or L f c = {µ(x) ∈ L pc | c i=1 µ i (x) = 1}

for posterior probabilities and membership degrees.

There exists many ways to compute labels, but we do not address the labelling problem in this paper and we will use the typicality measure defined as:

µ i (x) = α α + d 2 (x, v i ) ( 2
)
where α is a user-defined parameter, d a distance, and v i a prototype of the class ω i obtained from a learning set of patterns. It has been shown through empirical studies [START_REF] Zimmerman | Quantifying vagueness in decision models[END_REF] that ( 2) is a good model for membership functions that model vague concepts or classes.

• H : µ(x) → h(x) = t (h 1 (x), . . . , h c (x)) ∈ L hc , where L hc = {h(x) ∈ L f c |h i (x) ∈ {0, 1}}.
We adress the hardening problem because this step, which often reduces to the class of maximum label selection, is in charge of the decision making.

Reject options and the proposed classselective scheme

As defined, H is an exclusive rule which is not efficient in practice because it supposed that: i) Ω is exhaustively defined (closed-world assumption), ii) classes do not ovelap (separability assumption).

Such untrue assumptions can lead to very undesired decisions. In many real applications, it is more convenient to with-hold making a decision than making a wrong assignment, e.g. in medical diagnosis where a false negative outcome can be much more costly than a false positive. Reject options have been proposed to overcome these difficulties and to reduce misclassification risk. The first one, called distance rejection [START_REF] Dubuisson | A statistical decision rule with incomplete knowledge about classes[END_REF], is dedicated to outlying patterns. If x is far from all the class prototypes, this option allows to assign it to no class. The second one, called ambiguity rejection, allows to assign inlying patterns to several or all classes [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF][START_REF] Ha | The optimum class-selective rejection rules[END_REF]. If x is close to two or more class prototypes, it is associated with the corresponding classes. Formally, including reject options consists in modifying H such that h(x) can take values in the set of vertices of the unit hypercube L c hc = {0, 1} c instead of the exclusive subset L hc ⊂ L c hc . Different strategies can be adopted to handle these options at hand, but they all lead to a three types decision system: distance rejection when h(x) = t (0, . . . , 0) = 0, exclusive classification when h(x) ∈ L hc , ambiguity rejection when h(x) ∈ L c hc \{L hc ∪ 0}. For any pattern x to be classified, given its label vector µ(x) from L by (2), sorted in descending order

µ 1 (x) ≥ µ 2 (x) ≥ • • • ≥ µ c (x)
, we propose a two-steps class-selective scheme for H as follows :

1) test for distance rejection :

h(x) = 0 if µ 1 (x) < s,
where s is a user-defined threshold

2) if x is not distance rejected, assign it to a (sub)set of selected classes of cardinality k ∈ {1, . . . , c} ; thus it is exclusively classified if k = 1 or ambiguity rejected between the selected classes if k > 1.

For the (sub)set of classes selection problem, we propose to use the Φ j,k measure introduced in [START_REF] Le Capitaine | Blockwise similarity in [0,1] via triangular norms and sugeno integrals -application to cluster validity[END_REF] for another purpose. Assuming µ to be a sorted c-tuple,

µ 1 ≥ µ 2 ≥ • • • ≥ µ c
, we defined an operator based on triangular norms and the Sugeno integral which quantifies the similarity of the block of values {µ j , • • • , µ k }:

Φ j,k (µ) =                              k ⊥ i= k+j 2 µi N λ (i,k) j ⊥ i= k+j 2 µi N λ (i,j) if k -j is even k ⊥ i= k+j+1 2 µi N λ (i,k) j ⊥ i= k+j-1 2 µi N λ (i,j) if k -j is odd (3)
where N λ (i, l) is a gaussian kernel defined by:

N λ (i, l) = exp -(i -l) 2 λ (4)
The resolution parameter λ controls the area of influence: when λ → 0, the kernel becomes a dirac centered in l, and when λ → ∞, the kernel becomes the constant value 1. Therefore, the contribution of the intermediate values µ j+1 , ..., µ k-1 to Φ j,k (µ) is small if λ is close to zero and increases with λ. This means that increasing λ will not make two consecutive µ i 's more similar but may increase the similarity of blocks of larger size.

Since a high value of Φ 1,k (µ(x)) reveals that the k highest labels have similar values, then x can be associated with the corresponding classes. We propose to use an iterative scheme in order to find k, leading to the following second part for the H-step:

2) for i varying from 1 to c, set h i (x) = 1 when Φ 1,i (µ(x)) ≥ t, where t is a user-defined threshold

Note that Φ 1,1 (µ(x)) is always greater than t, ∀t ∈ [0, 1], because Φ 1,1 (µ(x)) = µ1(x)
µ1(x) = 1 for any t-norm couple. This ensure that at least one class is selected, the one which corresponds to the maximum of typicality degree, i.e. the one selected by the optimum classification rule in the sense of Chow [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF]. In particular, if t is set to 1, there is no ambiguity rejection. The class-selective rejection scheme presented in Algorithm 1 can be compared to the rule proposed by Ha [START_REF] Ha | The optimum class-selective rejection rules[END_REF].

Algorithm 1: hardening step H : L pc → L c hc Data: a sorted vector µ of typicality degrees, a membership threshold s, an ambiguity threshold t Result: a vector h of class-selective assignements begin if µ 1 (x) < s then

h i (x) ← 0 ∀i = 1, c if c i=1 h i (x) > 0 then for i ← 1 to c do if Φ 1,i (µ(x)) ≥ t then h i (x) ← 1 else h i (x) ← 0 return h(x) end

Experiments and Results

To validate the efficiency of the proposed classselective scheme, we present some results obtained by a resubstitution procedure on well-known real datasets from the UCI Machine Learning Repository [START_REF] Blake | UCI repository of machine learning databases[END_REF] whose characteristics (number p of features, number c of classes, degree of overlap) are summarized in Table 2. The classification performance of some usual su- pervised classifiers with no reject options are given in Table 3 for comparison purpose : the Quadratic Bayes (QB) rule, the Nearest Neighbor (1-N N ) rule and the Maximum Classifier (M C) based on typicality degrees in the feature space computed by (2) with α = 1 and

d 2 (x, v i ) = t (x -v i )Σ -1 i (x -v i
) where the covariance matrix Σ i and the center v i of the class ω i are estimated from the (learning) dataset. The same labeling L is used in the remaining experiments. We compare the performance of the proposed scheme to two classselective rejection ones found in the literature. In [START_REF] Ha | The optimum class-selective rejection rules[END_REF], Ha has proposed to set the optimum cardinality of the set of selected classes by:

k HA = min{k ∈ {1, . . . , c}|µ k+1 (x) ≥ t} ( 5
)
where t is a user-defined ambiguity threshold whose role is similar to the one in our scheme. Since this selection can lead to unnatural classification areas, Horiuchi has proposed in [START_REF] Horiuchi | Class-selective rejection rule to minimize the maximum distance between selected classes[END_REF] to use:

k HO = min{k ∈ {1, . . . , c}|µ k (x) -µ k+1 (x) ≥ t} (6)
Since these two selection schemes do not allow distance rejection, we set s = 0 in the experiments so that re-sults can be compared. Note moreover that there are no outliers in the considered datasets.

The results obtained by a resubstitution procedure are given in Table 4 where HA and HO stand for the Ha and the Horiuchi schemes, Φ S , Φ A and Φ H stand for the proposed scheme using the different triangular norms of Table 1 (with γ = 0 for the Hamacher one). The ambiguity threshold t is (coarse) tuned so that the error rate is as much as possible equal for each rejection scheme. For the tested datasets, a very little influence of the resolution parameter λ setting was observed and we chose to report the results with λ = 10. As expected, rejecting patterns leads to decrease the error rate compared to classifiers with no reject option (Table 3). Whatever the triangular norms, the proposed class-selective rejection scheme outperforms the ones proposed by Ha and Horiuchi with respect to the correct classification rate. This efficiency is due to the fact that the ratio of membership degrees is more suited than a simple difference to ambiguity rejection: the same difference ε between two low values and two high values with Horiuchi's method will not be discriminated. On the other side, with Ha's method, the most reliable membership degree is not taken into account, which leads to unnatural decisions. We constructed the operator such that our method reap the benefits of both Ha's and Horiuchi's schemes.

Conclusion

In this paper, a new class-selective rejection scheme is proposed. It consits of two sequential step dealing with both reject options : distance rejection for outliers and ambiguity rejection for inliers. The latter option is based on an operator which aggregates the class-degrees of typicality of the pattern to be classified. This operator measures the blockwise similarity of sorted degrees by combining them with triangular norms and the Sugeno integral. Experimental results we obtained on well-known real datasets show that the proposed scheme achieves better recognition accuracy than other similar class-selective rules. Due to lack of place, we did not discuss the choice of the triangular norms, for which we have some theoritical results according to the nature of the degrees (in L pc , L f c ). We will adress this problem in a forthcoming paper. Future works will concern the definition of blockwise similarity of numbers through fuzzy residual implication. We think this could generalize the concept of ambiguity for pattern recognition problems.

Table 2 . Datasets used in the experiments.

 2

	data	p	c	overlap
	iris	4	3	slight overlap, 2 classes
	pima	8	2	medium overlap, 2 classes
	vowel	10 11 slight overlap, by pairs
	glass	9	6	strong overlap, up to 5 classes

Table 3 . Error (E) and Correct (C) rates of some usual classifiers with no reject options.

 3

	data	%	QB	1-NN	MC
	iris	E C	2 98	4.67 95.33	2 98
	pima	E 25.39 29.53 32.55 C 74.61 70.47 67.45
	vowel	E C 95.42 90.23 91.92 4.58 9.77 8.08
	glass	E 31.10 30.64 28.5 C 68.90 69.36 71.5

Table 4 . Reject (R), Error (E) and Correct (C) rates of rejection schemes.

 4 22.90 22.90 22.90 22.90 22.90 C 53.27 68.22 69.16 68.93 69.08

	data	%	HA	HO	ΦS	ΦA	ΦH
		R	0.67	1.33	0.67	0.67	0.67
	iris	E	2	1.33	1.33	1.33	1.33
		C 97.33 97.33	98	98	98
		R	5.60	4.30	3.52	4.30	4.04
	pima	E 30.47 30.21 30.59 30.08 30.24
		C 63.93 65.49 65.89 65.62 65.72
		R 15.15	9.49	8.89	8.79	8.79
	vowel	E	4.34	4.34	4.34	4.34	4.34
		C 80.51 86.16 86.77 86.87 86.87
		R 23.83	8.88	7.94	8.17	8.02
	glass	E


Hoel Le Capitaine
email: hoel.lecapitaine@univ-lr.fr

Carl Frélicot
email: carl.frelicot@univ-lr.fr

A family of cluster validity indexes based on a l-order fuzzy OR operator

Clustering is one of the most important task in pattern recognition. For most of partitional clustering algorithms, a partition that represents as much as possible the structure of the data is generated. In this paper, we adress the problem of finding the optimal number of clusters from data. This can be done by introducing an index which evaluates the validity of the generated fuzzy c-partition. We propose to use a criterion based on the fuzzy combination of membership values which quantifies the l-order overlap and the intercluster separation of a given pattern.

Introduction

The objective of fuzzy clustering is to partition the data set into c distinct clusters. The fuzzy c-means (FCM) algorithm proposed by Bezdek [START_REF] Bezdek | Pattern Recognition with fuzzy objective function algorithm[END_REF] and its variations [START_REF] Gustafson | Fuzzy clustering with fuzzy covariance matrix[END_REF] are probably the most commonly used fuzzy clustering methods. However, these algorithms require the user to set the number c of clusters although the user do not always know it. A fuzzy c-partition obtained by FCM has to be validated because its quality depends on this number. Many cluster validity indexes have been proposed that evaluate each fuzzy c-partition and determines the optimal number c of clusters allowing to obtain the optimal partition of the data.

Compactness and separation of clusters are often considered to validate a partition [START_REF] Bezdek | Some new indexes of cluster validity[END_REF][START_REF] Pal | On cluster validity for the fuzzy c-means model[END_REF][START_REF] Fukuyama | A new method for choosing the number of clusters for the fuzzy c-means method[END_REF]. In this paper, we propose a new family of indexes that combine an overlap measure and a separation measure both based on aggregation of membership values. Section 2 provides background information on basic fuzzy operators and the l-order fuzzy OR operator our work is based on. Next, in section 3, we briefly describe the FCM algorithm and recall some well-known cluster validity indexes we will use for comparison. The measures we propose to use and the definition of the new index are described in section 4. Experimental results on both synthetic and real data sets that show its efficiency and concluding remarks are given in section 5 and 6 respectively.

Mathematical Background

For the applications we have in mind, e.g. cluster validity, we are particulary interested in aggregation functions that map a collection u of c values in [0, 1] (i.e. a vector u = [u 1 , • • • , u c ] T ) to a value in [0, 1] . Among the frequently used aggregation operators, one can cite the classes of triangular norms (t-norms) and triangular conorms (t-conorms). They have been introduced to characterize the general multivalued logic AND and OR operations and are widely used in fuzzy logic and fuzzy set theory to implement conjunctive and disjunctive operator respectively. A triangular norm is a commutative, associative and monotone function having for neutral element 1. Alternatively, its dual operator, the triangular conorm, is a commutative, associative and monotone function ⊥ having for neutral element 0. Examples of triangular norms couples are given in Table 1 for two operands, see [START_REF] Klement | Logical, Algebraic, Analytic, and Probabilistic Aspects of Triangular Norms[END_REF] for a large survey. Note that various parameterized families have been introduced, e.g. the Hamacher family defined by

u 1 H u 2 = u1 u2 γ+(1-γ) (u1+u2-u1 u2) and u 1 ⊥ H u 2 = u1+u2-u1 u2-(1-γ) u1 u2 1-(1-γ) u1 u2
where γ ∈ [0, +∞[. The dual couple is generally associated with a fuzzy negation defined as N (u 1 ) = 1 -u 1 and mentionned as the triple ( , ⊥, N ).

u1 S u2 = min(u1, u2) u1⊥Su2 = max(u1, u2) Algebraic u1 Au2 = u1 u2 u1⊥Au2 = u1 + u2 -u1 u2 Lukasiewicz u1 Lu2 = max(u1 + u2 -1, 0) u1⊥Lu2 = min(u1 + u2, 1)
Assume that the values u i (i = 1, • • • , c) to be aggregated represent the degree to which an object x satisfies each group description, i.e. its similarity to the prototypes describing each group. Using this knowledge contained in u, clustering consists in selecting the most appropriate group that the objects will be assigned to. The maximum operator is commonly used in this situation, but we may be interested in the lower values, which interact with the greatest value. In particular, if an object satisfies more than one group description, such an exclusive partitioning is not efficient. A fundamental issue becomes the determination of the overall degree of exclusive belongingness to a group or cluster. In [START_REF] Mascarilla | A k-order fuzzy or operator for pattern classification with k-order ambiguity rejection[END_REF], the authors define the l-order fuzzy OR operator. This operator evaluates degrees of satisfaction at a given order by combination of triangular norms. Let P be the powerset of C = {1, 2, ..., c} and P l = {A ∈ P : |A| = l} where |A| denotes the cardinality of subset A, then the fOR-l is defined by:

l ⊥ i=1,••• ,c u i = A∈P l-1 ⊥ j∈C\A u j (1)
It must be viewed as some kind of generalization of the notion of "l th highest" value, with l in C. In particular, with standard triangular norms, l ⊥(u) is ex-actly the "l th highest" element of u. For instance, let us take C = {1, 2, 3}, l = 2 and use standard triangular norms. We have P 1 = {{1}, {2}, {3}} and

2 ⊥ i=1,••• ,3 u i = min(max(u 2 , u 3 ) max(u 1 , u 3 ) max(u 1 , u 2 )) so that if u 2 < u 1 < u 3 , 2 ⊥ i=1,••• ,3 u i = u 1 .
This operator satisfies nice mathematical properties such as monotony, symmetry, see [START_REF] Mascarilla | A k-order fuzzy or operator for pattern classification with k-order ambiguity rejection[END_REF] for proofs and details.

3 Cluster Validity for Fuzzy Clustering

Fuzzy c-means algorithm

Clustering is an instance of unsupervised classification which aims at finding a structure of groups in set of n p-dimensional patterns X = {x 1 , ..., x n }. In this framework, the label vectors u k = u(x k ) do not exist and clustering algorithms can be used to obtain them from X. For instance, the fuzzy c-means (FCM) algorithm partitions X into c > 1 clusters by minimizing the following objective function [START_REF] Bezdek | Pattern Recognition with fuzzy objective function algorithm[END_REF]:

J m (U, V ) = n k=1 c i=1 u m ik ||x k -v i || 2 (2)
where u ik is the membership degree of x k to the i th cluster represented by its centroid

v i ∈ R p . Centroids are gathered into a (c × p) matrix V = [v 1 , ..., v c ].
Degrees u ik are subject to c i=1 u ik = 1 for all x k in X and to 0

< n k=1 u ik < n (∀i = 1, • • • , c).
In addition, they are elements of the fuzzy c-partition matrix U (c × n). The so-called fuzzifier m > 1 is a weighting exponent which makes the resulting partition more or less fuzzy [START_REF] Pal | On cluster validity for the fuzzy c-means model[END_REF]. The higher m is, the softer the clusters' boundaries are. Minimization of ( 2) is obtained by iteratively updating (U, V ) as follows:

u ik = 1 c j=1 ||x k -v i || ||x k -v j || 2/(m-1) (3)
v i = n k=1 u m ik x k n k=1 u m ik (4)
The usual euclidian norm ||.|| induces hyperspherical clusters, hence FCM can only detect clusters with the same shape and orientation.

Classical indexes

Validating the provided clustering of X consists in assessing whether the resulting partition reflects the data structure or not. Since c is a user-defined parameter of clustering algorithms such as FCM, most of works on cluster validity focus on the number of clusters problem. Many validity indexes have been proposed for fuzzy clustering (refer to [START_REF] Bezdek | Some new indexes of cluster validity[END_REF][START_REF] Kim | On cluster validity index for estimating the optimal number of fuzzy clusters[END_REF][START_REF] Wu | A cluster validity index for fuzzy clustering[END_REF][START_REF] Wang | On fuzzy cluster validity indices[END_REF][START_REF] Zarandi | A new cluster validity index for fuzzy clustering based on similarity measure[END_REF] for comparative studies). They can be classified in two main categories. The first one is composed of indexes that only use membership degrees (U ). Let us cite the Partition Coefficient [START_REF] Bezdek | Pattern Recognition with fuzzy objective function algorithm[END_REF], taking values in [ 1 c , 1]:

P C(c) = 1 n n k=1 c i=1 u 2 ik ( 5
)
or the Partition Entropy [START_REF] Bezdek | Cluster validity with fuzzy sets[END_REF], taking values in [0, log(c)]:

P E(c) = - 1 n n k=1 c i=1 u ik log(u ik ) (6)
Both P C to be maximized and P E to be minimized are monotonic with c, as well as their bounds. Normalized versions have been proposed to reduce this monotonic tendency, e.g. in [START_REF] Dave | Validating fuzzy partitions obtained through c-shells clustering[END_REF]. We will use these normalized versions in the experiments:

N P C(c) = cP C(c)-1 c-1
and N P E(c) = nP E(c) n-c . The second category consists of indexes that use membership degrees but also some information about the geometrical structure of the data (U, V, X), e.g. the Xie-Beni index [START_REF] Pal | On cluster validity for the fuzzy c-means model[END_REF][START_REF] Xie | A validity measure for fuzzy clustering[END_REF]:

XB(c) = J m (U, V ) /n min i,j=1,••• ,c;j =i ||v i -v j || 2 (7)
or the Fukuyama-Sugeno index [START_REF] Fukuyama | A new method for choosing the number of clusters for the fuzzy c-means method[END_REF]:

F S(c) = J m (U, V ) - n k=1 c i=1 u m ik ||v i -v|| 2 (8)
where v is the mean of centroids. Both XB and F S combine the FCM objective function (2) which measures the degree of compactness of the clusters and an additional term which measures the degree of their separation. Combination indicates that both indexes are to be minimized. The more compact and separated the clusters are, the more optimal c is.

The Proposed Index

Let U = [u 1 , ..., u c ] be a fuzzy c-partition provided by a fuzzy clustering algorithm, e.g. FCM. An overlap measure between l fuzzy clusters for each point x k in X described by its membership degrees can be obtained by Eq. [START_REF] Bensaid | Validity-guided (re)clustering with applications to image segmentation[END_REF]. By successively computing l ⊥(u k ) for different values of c, we get a combination of l-order overlap measure for x k . The most satisfied order is obtained by the disjunction of these measures, and we define the overall overlap measure as:

O(u k , c) = 1 ⊥ l=2,c   l ⊥ i=1,••• ,c u ik   (9)
In [START_REF] Bezdek | Some new indexes of cluster validity[END_REF], Bezdek and Pal show that intercluster separation plays a more important role in cluster validity than cluster diameters. We propose to introduce such a measure by quantifying the separation of each point x k with 1 ⊥(u k ) which is the overlap measure between 1 fuzzy cluster, i.e. its separation from the other fuzzy clusters, since u k sum up to one. Note that if standard triangular norms ar used, 1 ⊥(u k ) is the maximum coordinate of u k . Finally, we define the family of l-order Fuzzy OR Indexes as:

lF ORI(c, , ⊥) = 1 n n k=1 O(u k , c) 1 ⊥ i=1,••• ,c u ik (10)
Given U , the less overlaping and separated clusters are, the lower the value of lF ORI is expected to be and minimizing Eq. ( 10) will give the optimal number c of clusters. If U is hard, i.e. u ik ∈ {0, 1}, then one value equals 1 while the others are 0, say u 1k = 1 and u 2k = • • • = u ck = 0. Since 0 is the absorbing element of , it is easy to verify that O(u k , c) = 0 for all u k , whatever ( , ⊥), therefore lF ORI(c, , ⊥) = 0:

1 ⊥ l=2,c   l ⊥ i=1,••• ,c u ik   =   2 ⊥ i=1,••• ,c (1, 0, • • • , 0)   1 ⊥ • • • 1 ⊥ c ⊥ i=1,••• ,c (1, 0, • • • , 0) (11) = 1 ⊥(0,••• , 0 c-1 times ) = 0. ( 12
)
and

1 ⊥(1,0,••• , 0) = 1, since 1 is the absorbing element of ⊥.
On the other hand, if U is totally fuzzy, i.e. u ik = 1 c (∀i = 1, • • • , c), the resulting lF ORI value depends on the couple ( , ⊥) because Eq. ( 9) only reduces to

1 ⊥ l=2,c   l ⊥ i=1,••• ,c u ik   =   2 ⊥ i=1,••• ,c 1 c , • • • , 1 c   1 ⊥ • • • 1 ⊥ c ⊥ i=1,••• ,c 1 c , • • • , 1 c (13)
in the general case. If standard t-norms are used, we have:

1 ⊥ l=2,c   l ⊥ i=1,••• ,c u ik   = 1 ⊥     1 c , • • • , 1 c c-1 times     (14) = 1 c (15)
which is the value of 1 ⊥(u k ) for all u k , therefore lF ORI(c, S , ⊥ S ) = 1 for all c. Unfortunately, it is not possible to give a simple value for lF ORI for other couples ( , ⊥), but an upper bound can be found. Due to lack of space, the proof is postponed to a forthcoming long paper, as well as properties that could help the user to choose the couple ( , ⊥).

Experiments

Behavior according to clusters' separability

First, we generated a serie of 10 data sets, each composed of 800 points drawn from a mixture of c = 4 bivariate normal distributions. The covariance matrix of each component is the same

Σ i = I (∀i = 1, • • • , c
) and the mean vectors are:

µ 1 = α 1 1 , µ 2 = α 1 -1 , µ 3 = α -1 -1 and µ 4 = α -1 1

Robustness to outliers

In order to compare the proposed index to the classical ones, we generated a data set D 1 containing n = 200 points consisting of 50 points each drawn from a mixture of c = 4 bivariate normal distributions, see Figure 2-left. FCM was used with m = 2 for c varying from c min = 2 to c max = 10. A second artificial data set D 2 was generated. It is similar to D 1 except that 100 points drawn from a uniform distribution were added, as shown in Figure 2-right. These additional points act as noise and can make the FCM algorithm partitioning the data set into three clusters because the less separated groups in the right-lower area tend to become only one cluster. Values of the tested validity indexes on D 1 and D 2 are given in Table 2 and Table 3 respectively, where optimal values are bold faced and acceptable ones are italicized. Even if the classical indexes are known to be efficient, most of them fail in giving the right number of clusters on D 1 and with even stronger reason in presence of noise (D 2 ), whereas lF ORI always gives the right number c = 4 whatever the couple ( , ⊥) for both data sets. Moreover, multiple runs of FCM with random initializations on data set D 2 showed us that the proposed index gives more stable results compared to the others, thus demonstrating a significantly higher robustness to noisy data.

Sensitivity to the fuzzifier m

The FCM objective function depends on the fuzzy exponent m, see Eq. ( 2). Since the resulting fuzzy c-partition U is sensitive to this parameter, a cluster validity index can also be analysed with respect to m. In [START_REF] Bezdek | Some new indexes of cluster validity[END_REF], Pal and Bezdek have shown that FCM provides best results for m lying in [1.5, 2.5]. We compare the different indexes in this range on data sets D 1 and D 2 . Again, c is varying from c min = 2 to c max = 10. The selected number of clusters are reported in Table 4. As it can be seen, the proposed index lF ORI is less sensitive to m whatever the couple ( , ⊥) for both data sets.

Benchmark data sets

We finally compare the different indexes on benchmark data sets:

-Iris [5], composed of three classes of 50 flowers each described by 4 physical attibutes. Two classes have a substantial overlap in the feature space and the optimal number of clusters to be found is debatable: 2 or 3, see [START_REF] Bezdek | Some new indexes of cluster validity[END_REF]. -Wine [START_REF] Blake | Uci repository of machine learning databases[END_REF], which consists of 13 chemical attributes for n = 178 italian wines, divided into three classes. Classes are well separable, so the indexes found in the literature generally give the right number of clusters. -Wisconsin Breast Cancer [START_REF] Blake | Uci repository of machine learning databases[END_REF], composed of n = 699 malignant/benign cells described by 9 features computed from digitized images. -The artificial data set X30 introduced in [START_REF] Bezdek | Some new indexes of cluster validity[END_REF], consisting in n = 30 observations in R 2 , for which three clusters are expected. -The bidimensional artificial data set Bensaid Table 5 summarizes the results obtained on these data sets. The c column gives the expected number of clusters and the other columns show the optimal number of clusters obtained using the validity indexes. The proposed index always finds the optimal number of clusters whatever the couple ( , ⊥) while some others do not.

Conclusion

A new family of cluster validity indexes for fuzzy partitions has been proposed. These indexes combine a new measure of overlap of clusters and a separation measure. The novelty of the approach is that, for each data point to be clustered, the relative importance of each membership degree and the relationship of the degrees are taken into account through a combination of triangular norms ( , ⊥). Results obtained on artificial and benchmark data sets have shown that the proposed family of indexes is most of time more efficient than well-known ones, less sensitive to the fuzzifier exponent and particularly robust in noisy environments.

Further results about properties of the proposed indexes based on the mathematical properties of the agregation operators involved as well as guidelines to choose a member ( , ⊥) of the family appropriated to specific situations will come soon.

  , for increasing values of α = 1, 2, . . . , 10. This successively moves the clusters in opposite directions, creating less overlap as the clusters become more and more separated. The first and last data sets are shown in Figure 1-left. Each data set was then clustered using FCM with c = 4, providing a fuzzy partition matrix U α . Corresponding values of lF ORI for the different basic norms are plotted in Figure 1-right as a function of α. As expected, the proposed validity index decreases towards 0 as α increases whatever the couple ( , ⊥).

Fig. 1 .

 1 Fig. 1. α-separated data sets -α = 1 and 10 (left) and values of lF ORI(c = 4) as a function of α for various t-norms (right).

Fig. 2 .

 2 Fig. 2. Centroids of optimal clusters for data sets D1 (left) and D2 (right).

[ 1 ]

 1 characterized by 3 classes of very different cardinalities(6, 3 and 40).-The original Starfield[START_REF] Xie | A validity measure for fuzzy clustering[END_REF], which contains the position and light intensity of n = 51 bright stars near Solaris. The expected number of clusters is 8 or 9, depending on the papers.

Table 1 .

 1 Basic t-norms and t-conorms couples Standard

Table 2 .

 2 Validity indexes on data set D1.

	c N P C N P E XB	F S ×10 -3 ( , ⊥)S ( , ⊥)A-( , ⊥)H lF ORI
	2 0.57 0.52 0.13 -1.57	0.17	0.14	0.15
	3 0.70 0.56 0.07 -3.39	0.12	0.12	0.14
	4 0.74 0.59 0.08 -0.74	0.07	0.07	0.12
	5 0.67 0.80 0.31 -4.25	0.12	0.11	0.17
	6 0.61 1.00 0.45 -2.98	0.18	0.13	0.18
	7 0.56 1.15 0.37 -1.53	0.19	0.10	0.20
	8 0.530 1.27 0.30 -1.60	0.23	0.09	0.19
	9 0.532 1.37 0.31 -2.43	0.29	0.10	0.19
	10 0.50 1.47 0.28 -0.15	0.28	0.11	0.17

Table 3 .

 3 Validity indexes on data set D2 .

	c N P C N P E XB	F S ×10 -3 ( , ⊥)S-( , ⊥)A-( , ⊥)H lF ORI
	2 0.49 0.58 0.23 -0.85	0.25	0.17	0.19
	3 0.60 0.71 0.11 -2.33	0.23	0.11	0.20
	4 0.59 0.87 0.13 -0.75	0.17	0.09	0.15
	5 0.55 1.08 0.24 -5.21	0.18	0.13	0.21
	6 0.50 1.26 0.35 -0.06	0.21	0.14	0.22
	7 0.50 1.36 0.36 -0.12	0.21	0.17	0.22
	8 0.46 1.50 0.44 -2.41	0.26	0.16	0.21
	9 0.45 1.61 0.46 -2.61	0.30	0.16	0.19
	10 0.44 1.70 0.36 -1.81	0.30	0.15	0.18

Table 5 .

 5 Selected number of clusters in benchmark data sets.

	Data set c	N P C N P E XB F S	lF ORI ( , ⊥)S ( , ⊥)A ( , ⊥)H
	Iris 2 or 3	2	2	2 3	2	2	2
	Wine	3	3	2	3 5	3	3	3
	Breast	2	2	2	2 3	2	2	2
	X30	3	3	2	3 7	3	3	3
	Bensaid	3	3	2	3 7	3	3	3
	Starfield 8 or 9	2	2	6 7	8	8	8


Hoel Le Capitaine
email: hoel.lecapitaine@univ-lr.fr

Carl Frélicot
email: carl.frelicot@univ-lr.fr

Towards a unified logical framework of fuzzy implications to compare fuzzy sets

Keywords: aggregation operators, distance, fuzzy implication, inclusion, similarity

In fuzzy set theory, comparison of fuzzy sets plays an important role. Among the several ways to compare fuzzy sets, we address the logical theoretic approach using fuzzy implications. We propose a general framework allowing to generate many measures of comparison: inclusion, similarity and distance, and study their properties. Since the literature on the use fuzzy implications for defining such measures is abundant, we also attempt to relate this work to existing research.

Introduction

In fuzzy set theory, inclusion (or subsethood) and similarity measures between fuzzy sets are basic concepts. Among the different approaches to compare fuzzy sets, one finds three categories. The first one is based on measuring a distance between two real functions and do not refer to a specific interpretation, e.g. the Minkowski r-distances. The second category involves set-theoretic operations for fuzzy sets (fuzzy intersection, union, cardinality) [START_REF] Tversky | Features of similarity[END_REF][START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF]. This paper addresses the third category which relies on logical theory, mainly approached by using fuzzy implications. Following the early paper by Bandler and Kohout [START_REF] Bandler | Fuzzy power sets and fuzzy implication operators[END_REF] introducing the use of implications to measure inclusion of fuzzy sets, many authors have proposed new measures satisfying some specific axioms [START_REF] Young | Fuzzy subsethood[END_REF][START_REF] Fan | Subsethood measure: new definitions[END_REF][START_REF] Burillo | Inclusion grade and fuzzy implication operators[END_REF]. This paper will be organized as follows. We first recall some basic definitions and theorems on aggregation operators, triangular norms and fuzzy implications that will be used in the sequel in section 2. Next, in section 3 we propose a general framework of comparison measures of fuzzy sets (i.e. inclusion, similarity and distance) based on logical considerations, i.e. using fuzzy implications. A general description of the overall aggregation method is also provided, characterizing each measure belonging to this category. In section 4, we present the existing approaches that could be linked to this general formulation. We finally conclude and mention some application domains we have in mind in section 5.

Preliminaries and notations

Aggregating numbers plays an important role in decisionmaking systems. Values to be aggregated are generally defined on a finite real interval or on ordinal scales. In this paper, we assume with no loss of generality that they come from the unit interval. If not, a simple transformation can be found to make this assumption true. Given n numbers, an aggregation operator is a mapping A : [0, 1] n → [0, 1], satisfying bound-ary conditions

A(0, • • • , 0) = 0 and A(1, • • • , 1) = 1.
(

) 1
and monotonocity

∀n ∈ N, x 1 ≤ y 1 , • • • , x n ≤ y n implies A(x 1 , • • • , x n ) ≤ A(y 1 , • • • , y n ). (2)
Adding properties like idempotency, continuity, associativity lead to others definitions. In the literature, one finds many aggregation operators, e.g.: triangular norms (t-norms for short), OWA (Ordered Weighted Averaging) operators, γ-operators, or fuzzy integrals. They belong to several categories, depending on the way the values are aggregated: conjunctives, disjunctives, compensatory, and weighted operators. Briefly, an aggregation operator is said to be conjunctive if its output value is lower than the minimum of the input values, compensatory if the output value lies between the minimum and the maximum input value, and disjunctive if its output is greater than the maximum value of the inputs, refer to [START_REF] Calvo | Aggregation Operators: New Trends and Applications[END_REF] for a large survey on aggregation operators.

Theorem 1.

If A is a strictly monotonic compensatory aggregation operator, then

A(x 1 , . . . , x n ) = 1 ⇔ x 1 = • • • = x n = 1 (3)
and

A(x 1 , . . . , x n ) = 0 ⇔ x 1 = • • • = x n = 0 (4)
Proof.

(3) (⇐) obvious with Eq. ( 1). (⇒) by contraposition. We show that ∃i such that

x i < 1 implies A(x 1 , • • • , x n ) < 1. If x i < 1 for some i, then, since x j ≤ 1 for all j, by strict monotonicity of A, we get A(x 1 , • • • , x n ) < A(1, • • • , 1) = 1
, which ends the contraposition.

(4) (⇐) obvious with Eq. ( 1). (⇒) by contraposition. We show that ∃i such that

x i > 0 implies A(x 1 , • • • , x n ) > 0.
If x i > 0 for some i, then, since x j ≥ 0 for all j, by strict monotonicity of A, we get

A(x 1 , • • • , x n ) > A(0, • • • , 0) = 0, which ends the contraposition.
Example 1. The family of mean operators are strictly monotonic compensatory aggregation operators.

Remark 1. From Theorem 1, we immediately see that a disjunctive aggregation operator cannot be strictly monotonic. ∀j x j ≤ 1, and ∃i,

x i < 1, ∃k, x k = 1. If A is strictly monotonic, A(x 1 , • • • , x n ) < A(1, • • • , 1) = 1. Since A is disjunctive, i.e. A(x 1 , • • • , x n ) ≥ max(x 1 , • • • , x n ), we have 1 = max(x 1 , • • • , x n ) ≤ A(x 1 , • • • , x n ) < 1, which is a contradiction.
A t-norm is an increasing, associative and commutative mapping : [0, 1] 2 → [0, 1] satisfying the boundary condition (x, 1) = x for all x ∈ [0, 1]. The most popular continuous t-norms are:

• Standard: S (x, y) = min(x, y) • Algebraic (Product): A (x, y) = x y • Łukasiewicz: L (x, y) = max(x + y -1, 0)
Alternatively, the dual operators with respect to a strict negation are called triangular conorms (t-conorms for short). A t-conorm is an increasing, associative and commutative mapping ⊥ : [0, 1] 2 → [0, 1] satisfying the boundary condition ⊥(x, 0) = x for all x ∈ [0, 1]. The most popular continuous t-conorms are:

• Standard: ⊥ S (x, y) = max(x, y) • Algebraic (Product): ⊥ A (x, y) = x + y -x y • Łukasiewicz: ⊥ L (x, y) = min(x + y, 1)
Various parametrical families have been introduced, e.g. the Hamacher family defined by: given γ ∈ [0, +∞[,

• x H y = x y γ+(1-γ) (x+y-x y) • x ⊥ H y = x+y-x y-(1-γ) x y 1-(1-γ) x y .
Such families result in an infinite number of t-norm couples, including non parametrical ones e.g. the Algebraic couple for γ = 1. A general problem in fuzzy logic is to handle conditional statements if x, then y where x and y are fuzzy predicates. A widely used method consists in managing them by mappings I : [0, 1] × [0, 1] → [0, 1] such that the truth value of I depends on the initial propositions x and y. We generally speak about an implication function if I is non-increasing in the first variable, non-decreasing in the second variable and I(0, 0) = I(1, 1) = 1, and I(1, 0) = 0, see [START_REF] Mas | A survey on fuzzy implication functions[END_REF] for a survey on fuzzy implication functions and [START_REF] Whalen | Parameterized r-implications[END_REF] for a large overview on the use of parametrical implications in fuzzy inference systems. The four most usual implications are:

1. S-implications, defined by:

I ⊥ (x, y) = ⊥(x c , y) (5)
where (.) c is the usual complementation x c = 1-x. This implication is an immediate generalization of the usual boolean implication x → y ≡ x c ∨ y.

R-(for Residual

) implications, defined by:

I (x, y) = sup t {t ∈ [0, 1]| (x, t) ≤ y}. (6)
Note that if is a left-continuous t-norm, the supremum operation can be substituted by the maximum one.

3. QL-(for Quantum mechanic Logic) implications, defined by:

I QL (x, y) = ⊥(x c , (x, y)). (7)
4. D-implications, defined by:

I D (x, y) = ⊥( (x c , y c ), y) (8)
which are the contraposition of QL-implications with respect to the complementation.

In the sequel, we will denote by:

• X = {x 1 , • • • , x n } the (supposed finite) universe of dis- course,
• C(X) and F(X) the sets of all crisps and fuzzy sets in X, respectively,

• f A (x), ∀x ∈ X, the membership function of a fuzzy set A over X,

• [ 1 2 ] the constant fuzzy set defined by [ 1 2 ](x) = 1 2 for any x ∈ X.

General framework

There are several ways to compare fuzzy values or fuzzy quantities. The first one is based on a broad class of measures of equality based on a distance measure which is specified for membership functions of fuzzy sets. This approach takes its roots from studies on how to measure the distance between two real functions and do not refer to any specific interpretation. The general form of a Minkowski r-metric is usually taken and leads to well known distance functions (Hamming, Euclidean, Chebyshev):

d r (A, B) = x∈X |f A (x) -f B (x)| r 1/r (9)
A second way to compare fuzzy values comes from some basic set-theoretic considerations where union, intersection and complementation are defined for fuzzy sets. Cardinal and possibility based measures belong to this category. In this paper, we will focus our attention on the third way: the logical framework. We present the design a unified logical framework to compare fuzzy sets, which includes usual measures depending the aggregation operators we use. The use of parametrical t-norms and t-conorms to define the implications will enable to obtain parametrical measures of comparison, where the parameters can be set according to user needs.

Inclusion measures

An inclusion measure is a relation between two fuzzy sets which indicates to which extent one fuzzy set is contained in another one. Since its original definition by A ⊂ B iff f A (x) ≤ f B (x), for all x in X, which was crisp assessment, Bandler and Kohout enlarged this point of view by giving a degree of subsetness [START_REF] Bandler | Fuzzy power sets and fuzzy implication operators[END_REF], more in the spirit of the fuzzy theory. Inclusion measures are generally defined by a set of axioms [START_REF] Young | Fuzzy subsethood[END_REF] and by using fuzzy implication operators [START_REF] Bandler | Fuzzy power sets and fuzzy implication operators[END_REF][START_REF] Zhang | Hybrid monotonic inclusion measure and its use in measuring similarity and distance between fuzzy sets[END_REF].

Definition 1. A mapping I : F(X)×F(X) → [0, 1] is called an inclusion (or subsethood) measure if it satisfies (P1) I(A, B) = 1 iff A ⊆ B , ∀A, B ∈ F(X). (P2) if [ 1 2 ] ⊆ A, then I(A, A c ) = 0 iff A = X. (P3) ∀A, B, C ∈ F(X), if A ⊆ B ⊆ C, then I(C, A) ≤ I(B, A), and if A ⊆ B, I(C, A) ≤ I(C, B).
Note that if a measure I satisfies only the two last properties, it is called a weak inclusion measure.

Theorem 2. Let I be a residual implication function. Given X and arbitrary A, B ∈ F(X), let

I(A, B) = n A i=1 I (f A (x i ), f B (x i )) (10)
for all x i in X, where A is a conjunctive or a strictly monotonic compensatory aggregation operator satisfying Eqs.( 1) and ( 2). Then I is an inclusion measure.

Proof.

(P1) (⇐) if A ⊆ B, then f A (x i ) ≤ f B (x i ) for all x i ∈ X. Since if x ≤ y then I (x, y) = 1, we have I (f A (x i ), f B (x i )) = 1 for all x i ∈ X, which gives I(A, B) = 1 by boundary condition on A. (⇒) two cases are considered -if A is disjunctive, then we obviously have f A (x i ) ≤ f B (x i
) for all x i ∈ X, since the minimum value of all implications on X is 1 -if A is a strictly monotonic compensatory aggregation operator, then by using Theorem 1, we have

I (f A (x i ), f B (x i )) = 1 for all x i ∈ X, giving A ⊆ B by the confinement principle: x ≤ y iff I(x, y) = 1. (P2) (⇐) if A = X, then I (f X (x i ), ∅(x i )) = 0 for all x i ∈ X.
By boundary condition on A, it follows that

I(A, A c ) = 0. (⇒) if I(A, A c ) = 0, then I (f A (x i ), 1 -f A (x i )) = 0 for all x i ∈ X by Theorem 1. Assuming that A = X, then ∃i, x i such that 1 2 ≤ f A (x i ) < 1, i.e. 0 < 1 -f A (x i ) ≤ 1 2
. By non-increasingness in the first variable of I , we have

I (f A (x i ), 1 -f A (x i )) ≥ I (1, 1 -f A (x i )) = 1 -f A (x i ) = 0, since I satisfies the border principle: I(1, x) = x, ∀x ∈ [0, 1]. This is a contradiction with I (f A (x i ), 1 -f A (x i )) = 0, so that A = X. (P3) if A ⊆ B ⊆ C, f A (x i ) ≤ f B (x i ) ≤ f C (x i ), for all x i ∈ X.
By non-increasingness in the first variable and non-decreasingness in the second variable, it follows that

I (f C (x i ), f A (x i ) ≤ I (f B (x i ), f A (x i )) and I (f C (x i ), f A (x i )) ≤ I (f C (x i ), f B (x i )) for all i.
By monotonicity of A, we have I(C, A) ≤ I(B, A) and I(C, A) ≤ I(C, B), which concludes the proof.

A necessary condition to define a strong inclusion measure I is that the implication I holds the confinement principle and the border principle. It is easy to show that the four usual implications I , I ⊥ , I QL and I D satisfy the latter, but only I satisfies the former. Therefore S, QL and D-implications define weak inclusion measures while R-implications define strong inclusion measures provided the operator A is not disjunctive, see Remark 1.

Similarity and distance measures

Definition 2. A mapping S :

F(X)×F(X) → [0, 1] is called a similarity measure if it satisfies (P1) S(A, B) = S(B, A), ∀A, B ∈ F(X). (P2) S(A, A) = 1, ∀A ∈ F(X). (P3) S(D, D c ) = 0, ∀D ∈ C(X). (P4) ∀A, B, C ∈ F(X), if A ⊆ B ⊆ C, then S(A, C) ≤ S(A, B) ∧ S(B, C) or, equivalently ∀A, B, C, D ∈ F(X), if A ⊆ B ⊆ C ⊆ D, then S(A, D) ≤ S(B, C)
However, the symmetry property (P1) is still subject to experimental investigation: if S(x, y) is the answer to the question how is x similar to y?, then, when making comparisons, subjects focus more on the feature x than on y. This corresponds to the notion of saliency [START_REF] Tversky | Features of similarity[END_REF] of x and y: if y is more salient than x, then x is more similar to y than vice versa, which is experimentally confirmed. Accordingly to [START_REF] Hirota | Matching fuzzy quantities[END_REF], for a certain element of the universe of discourse X, a degree of equality of two fuzzy elements x and y can be defined by using implications as follows:

(x ≡ y) = 1 2 (x → y) ∧ (y → x) + (x c → y c ) ∧ (y c → x c ) (11)
where ∧ stands for minimum, → is an R-implication. Then applying Eq. ( 6) with x ≥ y, gives

(x ≡ y) = 1 2 (x → y) + (y c → x c ) ( 12
)
since 1 is the neutral element of t-norms. Furthermore, due to the opposition law: I(x, y) = I(y c , x c ), we obtain

(x ≡ y) = (x → y) (13)
A convenient way to define a similarity measure is to quantify to which extent two fuzzy membership degrees are similar, so that it is closely related to the problem of matching fuzzy quantities, or fuzzy sets similarity. So we propose to use fuzzy implication functions as similarity measures by the following theorem:

Theorem 3. Let I be a residual implication function. For arbitrary A, B ∈ F(X), let

S(A, B) = n A i=1 I f (1) (x i ), f (2) (x i ) (14)
for all x i in X, where f (.) is a permutation of f A and f B such that f (1)

(x i ) = (f A ∪f B )(x i ), f (2) (x i ) = (f A ∩f B )(x i ),
and A an aggregation operator satisfying Eqs. ( 1) and (2). Then S is a similarity measure.

Proof.

(P1) we have I (x, x) = 1, for any x ∈ [0, 1]. By boundary conditions on A, see Eq. ( 1), we obtain S(A, A) = 1.

(P2) by commutativity of union and intersection of fuzzy sets, we have

S(A, B) = n A i=1 I ((f A ∪ f B )(x i ), (f A ∩ f B )(x i )) = n A i=1 I ((f B ∪ f A )(x i ), (f B ∩ f A )(x i )) = S(B, A) (
(P4) since A ⊆ B ⊆ C ⊆ D, we have for all x i ∈ X f D (x i ) ≥ f C (x i ) (15) f B (x i ) ≥ f A (x i ) (16)
By non-increasingness in the first variable and nondecreasingness in the second variable of I , we obtain for all

x i ∈ X I (f D (x i ), f A (x i )) ≤ I (f C (x i ), f A (x i ))
by Eq. ( 15)

I (f C (x i ), f A (x i )) ≤ I (f C (x i ), f B (x i ))
by Eq. ( 16)

Last, monotonicity of A, see Eq. ( 2), gives S(A, D) ≤ S(B, C) which concludes the proof.

In contrast to inclusion measures, no restriction is imposed to the A operator, it can be freely chosen provided Eqs.( 1) and (2) are satisfied. On another hand, here again, the confinement principle is necessary to obtain property (P1) of similarity measures. Since S(A, B) is reflexive and symmetrical, i.e. S(A, A) = 1 and S(A, B) = S(B, A) hold for any A, B ∈ F(X), S is a proximity relation on F(X). andS(A, B) a similarity measure defined by Eq. ( 14), then the mapping

Definition 3. A mapping D : F(X)×F(X) → [0, 1] is called a distance measure if D has the following properties (P1) D(A, B) = D(B, A), ∀A, B ∈ F(X). (P2) D(A, A) = 0, ∀A ∈ F(X). (P3) D(D, D c ) = 1, ∀D ∈ C(X). (P4) ∀A, B, C ∈ F(X), if A ⊆ B ⊆ C, then D(A, B) ≤ D(A, C) and D(B, C) ≤ D(A, C) Proposition 1. For arbitrary A, B ∈ F(X),
D : F(X) × F(X) → [0, 1] defined by D(A, B) = S c (A, B)
is a distance measure between A and B.

Examples

Some examples of inclusion and similarity measures of the literature, and the new Hamacher inclusion and similarity measures, all obtained through the proposed general logical framework are given in Table 1. Moreover, this table shows how it is easy to check wether an inclusion measure is strong (non disjunctive A and I ) or weak (non disjunctive A), see Definition 1, as well as the proper definition of a similarity measure (any A and I ), see Theorem 3.

For illustration purpose, Fig. 1 shows some examples of fuzzy similarity measures as well as the influence of the parameter γ for Hamacher residual implications, which are defined by:

I Hγ (x, y) = 1 if y ≥ x y(γ+x-γx) y(γ+x-γx)+x-y if y ≤ x ( 17
)
where γ ∈ [0, +∞[. The different plots show the similarity value of a given fuzzy set A = {0.4/x 1 , 0.3/x 2 } to all the possible two-dimensional fuzzy sets B for various I . As one could expect, the closer to x 1 or x 2 the higher the similarity.

One can also note that different I lead to different shapes for isosurfaces of the similarity.

Related works

Let us relate, as far as possible, the proposed framework to some works issued from the abundant literature on the use of fuzzy implications for defining inclusion measures. In their seminal paper [START_REF] Bandler | Fuzzy power sets and fuzzy implication operators[END_REF], Bandler and Kohout propose to use implication functions in order to quantify the inclusion of each element in another, and then aggregate these individual measures by a conjunctive operator: the minimum. Some years later, Hirota and Pedrycz propose to use implications for matching fuzzy quantities [START_REF] Hirota | Matching fuzzy quantities[END_REF]. They aggregate the different implication truth values over X by a Choquet integral, computing the fuzzy measure with the help of a family of fuzzy sets taken as fuzzy prototypes. They also propose an entropy measure based on this matching measure, which gives an impression concerning the uncertainty of matching. In [START_REF] Kosko | Neural networks and fuzzy systems[END_REF], Kosko criticizes the original definition of fuzzy set containment: B contains A if and only if f A (x) ≤ f B (x) for all x in X by Zadeh, pointing out that if this inequality holds for all but just a few x, we can still consider A to be a subset of B to some degree. So he proposes a second definition based on fuzzy intersection of two fuzzy sets which can be seen as the conditional probability P (B|A) under certain circumstances. Furthermore, he defines the fuzziness of a fuzzy set A as the inclusion measure of A ∪ A c in A ∩ A c , which satisfies the axioms of fuzzy entropy of De Luca and Termini [START_REF] De | A definition of a nonprobabilistic entropy in the setting of fuzzy sets theory[END_REF]. Inclusion and similarity measures from a general set-theoretic point of view, coming from the proposition of Tversky [START_REF] Tversky | Features of similarity[END_REF], are described by Bouchon-Meunier et al. in [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF]. The authors introduce a general framework for similitude, satisfiability and inclusion measures, also study the aggregation of measures of comparison, but take only two examples for the aggregation operator A: a t-norm and the OWA operator. In this paper, we propose a study of the properties of A in its more general meaning. The same remark applies to the work by Young [START_REF] Young | Fuzzy subsethood[END_REF] proposing an axiomatization of inclusion measures and their connection to implication operators since she restricts herself to both the minimum and the arithmetical mean for A. Furthermore, this work do not give necessary conditions on implications for the definition of strong or weak inclusion measure whereas our's does (Definition 1). Wang [START_REF] Wang | New similarity measures on fuzzy sets and on elements[END_REF] presents two similarity measures which can be viewed as particular cases of the framework we propose. He enlarges his definition to the similarity of fuzzy elements belonging to various fuzzy sets. Again, the framework we propose allows to obtain a similarity between fuzzy elements since we compute implications for each element. Starting from Kosko and Young observations, Botana [START_REF] Botana | Deriving fuzzy subsethood measures from violations of the implication between elements[END_REF] presents a set of new measures derived

(min(1, 1 -f A (x) + f B (x)
)) as defined in [START_REF] Sinha | Fuzzification of set inclusion : theory and applications[END_REF] min

I L I(A, B) = 1 n x∈X min(1, 1 -f A (x) + f B (x)) arithmetical mean I L I(A, B) = 1 n x∈X max(1 -f A (x), f B (x)) arithmetical mean I ⊥ S I(A, B) = 1 n x∈X 1 -f A (x) + f A (x) f B (x)
as defined in [START_REF] Young | Fuzzy subsethood[END_REF] arithmetical mean

I ⊥ A I(A, B) = 1 n x∈X f B (x)(γ + f A (x) -γf A (x)) f B (x)(γ + f A (x) -γf A (x)) + f A (x) -f B (x) arithmetical mean I Hγ Similarity Measure S Aggregation Operator A Implication I S(A, B) = 1 n x∈X min(f A (x), f B (x)) max(f A (x), f B (x))
as defined in [START_REF] Wang | New similarity measures on fuzzy sets and on elements[END_REF] arithmetical mean

I A S(A, B) = 1 n x∈X 1 -|f A (x) -f B (x)
| as defined in [START_REF] Wang | New similarity measures on fuzzy sets and on elements[END_REF] arithmetical mean

I L S(A, B) = max x∈X min(f A (x), f B (x)) max I S S(A, B) = 1 -max x∈X |f A (x) -f B (x)| min I L S(A, B) = 1 n x∈X f (2) (x)(γ + f (1) (x) -γf (1) (x)) f (2) (x)(γ + f (1) (x) -γf (1) (x)) + f (1) (x) -f (2) (x)
arithmetical mean I Hγ from fuzzy implications. He studies whether the introduced inclusion measures satisfy Young's axioms [START_REF] Young | Fuzzy subsethood[END_REF] and/or those in [START_REF] Sinha | Fuzzification of set inclusion : theory and applications[END_REF] when using Wu, Goguen, modified Goguen, Gödel and Standard strict implications. He also gives the formulation of the corresponding entropy in the sense of [START_REF] De | A definition of a nonprobabilistic entropy in the setting of fuzzy sets theory[END_REF][START_REF] Kosko | Neural networks and fuzzy systems[END_REF]. Another approach to aggregation operators is proposed in [START_REF] Fonck | An application of aggregation procedures to the definition of measures of similarity between fuzzy sets[END_REF] consisting in combining implication truth values through respectively disjunctive and conjunctive functions for an optimistic and pessimistic aggregation. Fan et al. discuss the links between inclusion, entropy and fuzzy implications, and propose some new axioms for these measures [START_REF] Fan | Subsethood measure: new definitions[END_REF]. Burillo et al. present a family of implication operators derived from the Łukasiewicz implication in order to define a family of inclusion grade operators [START_REF] Burillo | Inclusion grade and fuzzy implication operators[END_REF] using the minimum operator for A.

In [START_REF] Kehagias | L-fuzzy valued inclusion measure, l-fuzzy similarity and l-fuzzy distance[END_REF], Kehagias and Konstantinidou introduce L-fuzzy valued inclusion, similarity and distance measures, i.e. mappings I, S, D : F(X) × F(X) → [0, 1] n , but restrict the output to crisp values. As pointed out by the authors, the vector output can lead to a difficult interpretation of the result. Furthermore, as vectors are partially ordered they are even harder to compare, they require a new measure to compare outputs. The framework we propose can provide a vector output since an implication on each element of X is computed. By contrast to [START_REF] Kehagias | L-fuzzy valued inclusion measure, l-fuzzy similarity and l-fuzzy distance[END_REF], it would be a fuzzy L-fuzzy valued measure. More recently [START_REF] Papadopoulos | Optimization method for the selection of the appropriate fuzzy implication[END_REF][START_REF] Balopoulos | Distance and similarity measures for fuzzy operators[END_REF], a distance between fuzzy operators, fuzzy implication functions in particular, is proposed. It leads to normalized tensor-norms which allow to define a similarity of fuzzy sets, and present an heuristic to choose the most suitable implication function to a fuzzy inference system. Zhang and Zhang propose an hybrid inclusion measure in [START_REF] Zhang | Hybrid monotonic inclusion measure and its use in measuring similarity and distance between fuzzy sets[END_REF] and use it to define similarity and distance measures of fuzzy sets. They restrict themselves to the weighted mean for A, so it can be viewed as a special case of the work we propose, but contrarily to Young the involved implications satisfy the confinement and the border principle. Let us finally mention the work by Fono et al. [START_REF] Fono | Fuzzy implication operators for difference operations for fuzzy sets and cardinality-based measures of comparison[END_REF] where as many difference operations as many implications are used to define measures of comparison of fuzzy sets in the set-theoretic framework, but we remind that such measures are out of the scope of this paper.

Conclusion and perspectives

In this paper, we propose a unified logical framework to compare fuzzy sets as well as fuzzy elements. Within this framework, new measures of inclusion, similarity and distance can be easily derived. These measures depend on any fuzzy implication I, provided it satisfies the necessary conditions we give (the border and the confinement principles) and any aggregation operator A (for similarity and distance) or any conjunctive and strictly monotonic compensatory aggregation operator A (for inclusion). Choosing specific (A, I) enables to retrieve most of the measures of the literature. We hope that results of this work would be of great help to set comparison functions in many fields: fuzzy mathematical morphology [START_REF] Burillo | Inclusion grade and fuzzy implication operators[END_REF], cluster validity [START_REF] Fan | Subsethood measure: new definitions[END_REF], as well as other domains e.g. image retrieval or feature selection.

  P3) by definition, I(1, 0) = 0. By boundary conditions on A, see Eq. (1), we obtain S(D, D c ) = 0.

Figure 1 :

 1 Figure 1: Examples of similarity measures of A = {0.4/x 1 , 0.3/x 2 } and all fuzzy sets F(X), n = 2 where high and low values correspond to red and blue colors respectively. First row: A is the arithmetical mean, and we use I S , I A and I L , respectively from left to right. Second row: A is the arithmetical mean and we used the Hamacher implication I Hγ , where γ = 0, 2, 5 from left to right.

Table 1 :

 1 Inclusion and similarity measures of the literature, and the new Hamacher inclusion and similarity measures, all obtained through the proposed general logical framework.

	Inclusion Measure I


Hoel Le Capitaine
email: hoel.lecapitaine@univ-lr.fr

Carl Frélicot
email: carl.frelicot@univ-lr.fr

Classification with reject options in a logical framework: a fuzzy residual implication approach

Keywords: Ambiguity measures, Dombi and Hamacher implications, fuzzy r-implications, pattern classification, reject options

In many classification problems, overlapping classes and outliers can significantly decrease a classifier performance. In this paper, we introduce the possibility of a given classifier to reject patterns either for ambiguity or for distance. From a set of typicality degrees for a pattern to be classified, we propose to use fuzzy implications to quantify the similarity of the degrees. A class-selective scheme based on this new family is presented, and experimental results showing the efficiency of the proposed algorithm are given.

Introduction

Usual classification of objects, or patterns, consists in assigning incoming samples to one class belonging to a set of known ones. Since classes may overlap in the feature space and all of them do not appear during the learning step of most real classification problems, some samples may have to be not classified but rejected. In practice, two situations can lead to rejection, either the incoming sample could belong to unknown class(es) (distance rejection) or it should be assigned to several classes (ambiguity rejection) [START_REF] Dubuisson | A statistical decision rule with incomplete knowledge about classes[END_REF]. In this paper, we focus our attention on this latter situation. Initially introduced by Chow [START_REF] Chow | On optimum error and reject tradeoff[END_REF], it consists in rejecting the most unreliable patterns that have a low posterior probability, or more generally a low membership degree value, to its closest class. Such a reject classification rule is optimal if posterior probabilities are estimated without error, unfortunately this is not the case in practice. We investigate some new measures that aim at quantifying to what extent such a pattern is ambiguous from its membership degrees, or more generally from its multi-class classifier soft outputs, using fuzzy implications. These measures assess the relationships between membership values with various combination of triangular norm operators (t-norms for short, see [START_REF] Klement | Logical, Algebraic, Analytic, and Probabilistic Aspects of Triangular Norms[END_REF] for an overview). The remainder of this paper is organized as follows. In section 2, we start by presenting distance-based class models that we will use in the sequel, and then discuss about standard approaches to pattern rejection. Next, we give a brief recall on some basic definitions of triangular norms and fuzzy residual implications, as well as some new parametrical implications (section 3). Section 4 is devoted to the proposal of using implications as ambiguity measures. In section 5, an experimental evaluation and comparisons to well known class-selective pattern recognition schemes are provided. We finally conclude and give some perspectives in section 6.

2 Classification with reject options

Classification

Let x be a pattern described by a p (real) features and let

Ω = {ω 1 , • • • , ω c } be a set of classes of cardinality c.
The objective of classification is to assign any pattern x ∈ R p to one of the c classes of Ω. It generally consists of two steps L (labeling) and H (hardening):

• L : x → u(x) = t (u 1 (x), . . . , u c (x)) ∈ L •c • H : u(x) → h(x) = t (h 1 (x), . . . , h c (x)) ∈ L hc .
where L hc = {h(x) ∈ L f c : h i (x) ∈ {0, 1}} and L •c depends on the mathematical framework the classifier relies on, e.g.

L pc = [0, 1] c for degrees of typicality or L f c = {u(x) ∈ L pc : c i=1 u i (x) = 1}
for posterior probabilities and membership degrees. Posterior probabilities can be obtained either from (known) class-conditional densities whose parameters are estimated using a learning set X of patterns, i.e. patterns for which the assignment is known, or from class-density estimates using the classes of their neighbors in X. However, for high dimensional feature spaces, many patterns are required to perform good class-density estimates (curse of dimensionality). When the learning set is small, distances to prototypes of each class are used, e.g.

d 2 (x, v i ) = (x -v i ) t Σ -1 i (x -v i ) (1)
where v i and Σ i are the mean vector and covariance matrix of the class ω i estimated from X. In order to have a common scaling, label values are often obtained in the unit interval, e.g.

u i (x) = α i α i + d 2 (x, v i ) (2)
where α i are user-defined parameters. We focus on the H-step because it is in charge of the classification. This step often reduces to the class of maximum label value selection, resulting in an exclusive classification rule which is not efficient in practice because it supposes that Ω is exhaustively defined (closed-world assumption) and classes do not overlap (separability assumption). Such untrue assumptions can lead to very undesired decisions. In many real applications, it is more convenient to with-hold making a decision than making a wrong assignment, e.g. in medical diagnosis where a false negative outcome can be much more costly than a false positive. Reject options have been proposed to overcome these difficulties and to reduce misclassification risk. The first one, called distance rejection [START_REF] Dubuisson | A statistical decision rule with incomplete knowledge about classes[END_REF], is dedicated to outlying patterns. If x is far from all the class prototypes, this option allows to assign it to no class. The second one, called ambiguity rejection, allows to assign inlying patterns to several or all classes [START_REF] Chow | On optimum error and reject tradeoff[END_REF][START_REF] Ha | The optimum class-selective rejection rule[END_REF]. If x is close to two or more class prototypes, it is associated with the corresponding classes. Including reject options leads to partition the feature space into as many regions as subsets of classes, i.e. at most 2 c ones, to which a pattern can be assigned. Formally, it consists in modifying H such that h(x) can take values in the set of vertices of the unit hypercube L c hc = {0, 1} c instead of the exclusive subset L hc ⊂ L c hc . Different strategies can be adopted to handle these options at hand, but they all lead to a three types decision system: distance rejection when h(x) = t (0, . . . , 0) = 0, exclusive classification when h(x) ∈ L hc , ambiguity rejection when h(x) ∈ L c hc \{L hc ∪ 0}. The resulting classification rule is then a matter of selecting the appropriate number of classes varying from zero (distance rejection) to c (total ambiguity rejection).

Usual reject schemes

Since the work by Chow [START_REF] Chow | On optimum error and reject tradeoff[END_REF], many rejection schemes have been proposed. In its general form, a class-selective procedure defined by

n (x, t) = min k∈[1,c] {k : A k (x) ≤ t} (3)
where A k is a given ambiguity measure on membership degrees, n (x, t) is the number of selected classes for the pattern x to be classified, and t is a user-defined threshold which can be class dependent (e.g. t k ). This threshold can be set conditionally to cost functions relative to error, reject and correct classification rates. Propositions from the literature mainly consist in new definitions of ambiguity measures A k . For Chow, A k was one minus the maximum value of the membership degrees. In the paper by Ha [START_REF] Ha | The optimum class-selective rejection rule[END_REF], the second highest value was tested to decide wether one or several classes are selected. Since this scheme is leading to unnatural decisions, Horiuchi [START_REF] Horiuchi | Class-selective rejection rule to minimize the maximum distance between selected classes[END_REF] proposed a new measure defined by the difference of the membership degrees which is actually a disambiguity measure. In [START_REF] Frélicot | A multi-step predictor of membership function as an ambiguity reject solver in pattern recognition[END_REF], Frélicot proposed to use the ratio of membership degrees. As usual, we use the convention that if A k (x) > t for all k, then we set n (x, t) = c. Table 1 summarizes the existing ambiguity measures used for pattern rejection, where the membership degrees are assumed to be sorted in decreasing order for writing convenience, i.e.

u 1 (x) ≥ • • • ≥ u c (x).
Table 1: Existing ambiguity measures related to Eq. ( 3). Scheme Ambiguity Measure A k (x) Chow [START_REF] Chow | On optimum error and reject tradeoff[END_REF] 1 -u 1 (x)

Ha [4] u k+1 (x) Horiuchi [5] 1 -(u k (x) -u k+1 (x)) Frélicot [6] u k+1 (x)/u k (x)
3 Fuzzy residual implications

Basic definitions

Let us recall basic definitions of fuzzy operators that will be used to combine the values of interest, i.e. the pattern classdegrees of typicality. Depending on properties, aggregation functions can be classified into several categories: conjunctive, disjunctive, compensatory, and so on. We restrict on conjunctive and disjunctive functions. By definition, the output of a conjunctive operator is lower or equal than the minimum value, whereas the output of a disjunctive operator is greater or equal than the maximum value. Beyond these operators, we choose to use the triangular norms because of their ability to generalize the logical AND and OR crisp operators to fuzzy sets, see [START_REF] Klement | Logical, Algebraic, Analytic, and Probabilistic Aspects of Triangular Norms[END_REF] for a survey. Briefly, a triangular norm (or t-norm) is a binary operation on the unit interval

: [0, 1] 2 → [0, 1]
which is commutative, associative, non decreasing and has 1 for neutral element. Thus, a t-norm is conjunctive and the minimum operator ∧ is the greatest t-norm. Alternatively, a triangular conorm (or t-conorm) is the dual binary operation

⊥ : [0, 1] 2 → [0, 1]
having the same properties except that its neutral element is 0. Thus, a t-conorm ⊥ is disjunctive and the maximum operator ∨ is the lowest t-conorm. Typical examples of dual couples (t-norm, t-conorm) that will be used in the sequel are given in Table 2.

Table 2: Examples of dual couples, including parametrical ones.

Standard

a S b = min(a, b) a⊥Sb = max(a, b) Algebraic a Ab = a b a⊥Ab = a + b -a b Łukasiewicz a Lb = max(a + b -1, 0) a⊥Lb = min(a + b, 1) Hamacher a Hγ b = a b γ+(1-γ) (a+b-a b) a⊥H γ b = a+b+(γ-2) a b 1+(γ-1) a b Dombi a Dγ b = 1 + 1-a a γ + 1-b b γ 1/γ -1 a⊥D γ b = 1 -1 + a 1-a γ + b 1-b γ 1/γ -1
A fuzzy residual implication, denoted R-implication (or →) is defined by:

I(a, b) = sup t {t ∈ [0, 1] : (a, t) ≤ b} (4)
Note that if is a left-continuous t-norm, the supremum operation can be substituted by maximum. If we use additive generating functions, i.e. a strictly decreasing function f : [0, 1] → [0, +∞] with f (1) = 0, and admitting an inverse (or pseudo-inverse) function f -1 , Eq. ( 4) can be written as

I(a, b) = max(f -1 (f (b) -f (a)), 0) (5)
because f is strictly monotonic. We generally speak about an implication function if I is non-increasing in the first variable, non-decreasing in the second variable and I(0, 0) = I(1, 1) = 1, and I(1, 0) = 0, see [START_REF] Mas | A survey on fuzzy implication functions[END_REF] for a large survey on fuzzy implication functions. Within theses implications, the well-known Gödel and Goguen ones are respectively given by

I(a, b) = 1 if b ≥ a b if b < a (6)
and

I(a, b) = 1 if b ≥ a b a if b ≤ a (7)
which are obtained with the minimum and algebraic (or product) triangular norms, respectively. In the sequel, we will assume for writing convenience that the fuzzy values are sorted in decreasing order, e.g. a ≥ b.

Parametrical implications

Proposition 1. Let ( Hγ ), γ ∈ [0, +∞[, be the family of Hamacher t-norms. The residual Hamacher implication is given by

I Hγ (a, b) = 1 if b ≥ a b (γ+a-γa) b (γ+a-γa)+a-b if b ≤ a (8)
Proof. By definition of R-implications (4), we can write

I Hγ (a, b) = sup t {t ∈ [0, 1] : Hγ (a, t) ≤ b}.
We also have

I Hγ (a, b) = max t {t ∈ [0, 1] : Hγ (a, t) ≤ b} because Hγ is a left-continuous t-norm. Then, solving a t γ + (1 -γ) (a + t -a t) ≤ b (9)
gives

t ≤ b (γ + a -γa) b (γ + a -γa) + a -b . (10)
Since a ≥ b, it is easy to show that the right part of Eq. ( 10) is in [0, 1], hence we obtain Eq.( 8).

Proposition 2. Let ( Dγ ), γ ∈]0, +∞[, be the family of Dombi t-norms. The residual Dombi implication is given by

ID γ (a, b) =      1 if b ≥ a 1 + 1-b b γ -1-a a γ 1/γ -1 if b < a (11)
Proof. I Dγ (a, b) = sup t {t ∈ [0, 1] : Hγ (a, t) ≤ b} by (4). Since Dγ is a left-continuous t-norm, we can write

I Dγ (a, b) = max t {t ∈ [0, 1] : Dγ (a, t) ≤ b}. Then, solving 1 + 1 -a a γ + 1 -t t γ 1/γ -1 ≤ b (12)
gives

t ≤ 1 + 1 -b b γ - 1 -a a γ 1/γ -1 . (13)
Since, a ≥ b, it is easy to show that

1-b b γ -1-a a γ 1/γ
≥ 0, hence the right part of Eq. ( 13) is in [0, 1] and ( 11) is obtained.

Note that R-implications are mostly used in fuzzy inference systems, see [START_REF] Th | Parameterized r-implications[END_REF] for a large overview on the use of parametrical R-implications in fuzzy rule based systems.

4 Some parametrical measures of ambiguity

In this section, the concept of similarity measure and its relationship with ambiguity measures are described. Then we propose to use fuzzy parametrical implications as new families of ambiguity measures to be used for pattern classification with reject options. The resulting class-selection algorithm (H-step) is presented and we finally discuss the choice of the parameter for parametrical implications with the help of numerical examples.

Proposition and properties

A similarity measure S generally satisfies the following properties:

(P1) S(a, b) = S(b, a), (symmetry)
(P2) S(a, a) ≥ S(a, b), (minimality)
(P3) S(a, b) = 1 ⇔ a = b, (identity)
However, the symmetry property (P1) is still subject to experimental investigation: if S(a, b) is the answer to the question how is a similar to b?, then, when making comparisons, subjects focus more on the feature a than on b. This corresponds to the notion of saliency of a and b [START_REF] Tversky | Features of similarity[END_REF]: if b is more salient than a, then a is more similar to b than vice versa, which is experimentally confirmed. Property (P2) is also open because it can be violated experimentally, see [START_REF] Tversky | Features of similarity[END_REF] for details. There are several ways to deal with the comparison of fuzzy values, or fuzzy quantities. The first one is based on a broad class of measures of equality based on a distance measure which is specified for membership functions of fuzzy sets. This approach takes its roots from studies on how to measure the distance between two real functions and do not refer to any specific interpretation. The general form of a Minkowski r-metric is usually taken and leads to well known distance functions (Hamming, Euclidean, Chebyshev). A second way to compare fuzzy values comes from some basic set-theoretic considerations where union, intersection and complement are defined for fuzzy sets. Cardinal and possibility based measures belong to this category. In this paper, we focus on the third way to deal with fuzzy values comparison: the logical framework. Accordingly to [START_REF] Hirota | Matching fuzzy quantities[END_REF], for a certain universe of discourse D, the degree of equality of two fuzzy elements a and b can be defined by implications as follows:

(a ≡ b) = 1 2 (a → b) ∧ (b → a) + (ā → b) ∧ ( b → ā) ( 14
)
where ∧ stands for minimum, → is an implication and ā is the strict negation ā = 1 -a. Since 1 is the neutral element of t-norms, applying Eq. ( 4) with a ≥ b gives

(a ≡ b) = 1 2 (a → b) + ( b → ā) . (15)
A convenient way to define an ambiguity measure is to quantify to which extent two fuzzy membership degrees are similar, so that it is closely related to the problem of matching fuzzy quantities, or fuzzy sets similarity. So we propose to use fuzzy R-implications as generalized ambiguity measures.

Given a set of c truth values assumed to be sorted in decreasing order, i.e. u 1 (x) ≥ • • • ≥ u c (x), with no loss of generality, let us have two predicates (x is ω i ), with the truth value u i (x), and (x is ω k ), with the truth value u k (x). The truth value of the implication if the pattern x is ω i , then the pattern x is also ω j , ∀j varying from i + 1 to k is an ambiguity measure given by I(u i (x), u k (x)). By convention, we assume that the assignment of x to ω i is more probable than the assignment of x to ω k when using this implication because u i (x) ≥ u k (x) and obviously we have I(u i (x), u i+1 (x)) ≥ I(u i (x), u k>i+1 (x)).

Proposition 3. Given t ∈ [0, 1], the optimum cardinality of the generalized class-selective rejection rule is given by

n (x, t) = min k∈[1,c] k : I u k (x), u k+1 (x) ≤ t (16) with u 1 (x) ≥ • • • ≥ u c (x)
, and the convention u c+1 (x) = 0.

Since I(a, 0) = 0 if a = 0, c classes will be selected if none were previously selected.

Property 1. If we use the Standard triangular norm min, we obtain the Ha class-selective rejection scheme [START_REF] Ha | The optimum class-selective rejection rule[END_REF].

Property 2. If we use the Łukasiewicz triangular norm, we obtain the Horiuchi class-selective rejection scheme [START_REF] Horiuchi | Class-selective rejection rule to minimize the maximum distance between selected classes[END_REF].

Property 3. If we use the Algebraic triangular norm, we obtain the Frélicot class-selective rejection scheme [START_REF] Frélicot | A multi-step predictor of membership function as an ambiguity reject solver in pattern recognition[END_REF].

Proofs are straightforward and will be given in a longer forthcoming paper. Note that modifying Eq.( 16) such as

n (x, t) = min k∈[0,c] k : I u k (x), u k+1 (x) ≤ t (17)
with the convention u 0 (x) = 1 allows to select none of the classes, i.e. to proceed to distance rejection, since I(1, a) = a whatever the triangular norm. The resulting generalized pattern classification rule with reject options (H-step) is presented in Algorithm 1. It can be used to compare various schemes, depending on the choice of the triangular norm.

Algorithm 1: H-step classification algorithm. Data: a vector of soft class-labels u(x) ∈ L pc and a reject threshold t Result: a vector of class-selective assignments h(x) ∈ L c hc begin set h(x) to 0 find n (x, t) -Eq.( 16) or Eq.( 17) foreach j = 1 : n (x, t) in decreasing order of u j (x) s do set h j (x) = 1 end end

Discussion and examples

One of the main difficulties when using t-norms is to choose the dual couple and if needed to set the parameter value. Let us study how the choice of γ for Hamacher and Dombi implications modifies the resulting implication strength.

• Hamacher: increasing the value of γ will make two fuzzy values more similar because

I Hγ (a, b) = ab/(a -b + ab) if γ = 0 while lim γ→+∞ I Hγ (a, b) = 1 whatever (a, b) ∈ [0, 1] 2 .
Indeed, I Hγ is non-decreasing with γ since

∂I Hγ ∂γ = (b -ab)(a -b) (b(γ + a -γa) + a -b) 2 ≥ 0.
The influence of γ is much more significant for low values of a and b than for high ones because b(γ + aγa) appears to be of order b a (respectively b (γ + a)) for high (respectively low) values of a and b. It follows that if γ 1 >> γ 2 , we have γ1 γ1+ε >> γ2 γ2+ε , so that large values of γ associated to low values of (a, b) will result in a high value of I Hγ , see Table 3 for examples. Thus, decreasing γ for the Dombi family has the same impact as increasing γ for the Hamacher family, so that we expect the opposite tendency, see Table 4 for examples. The appropriate tuning of γ can be achieved using a gradient procedure, as in [START_REF] Rutkowski | Flexible neuro-fuzzy systems[END_REF]. happen, here x low ≈ 0.8 and x up ≈ 1.9. Then, the corresponding u 1 (x low ) and u 2 (x up ) ordinate values can be used to set the classification threshold t. Then, referring to measures of ambiguity in the middle -and bottom -plots, the behaviour of the different schemes can be analyzed. In such a situation, Chow's and Horiuchi's (Łukasiewicz implication) schemes would lead to reject too many points in low density areas, while other schemes do not show these drawbacks. On the other hand, Ha's scheme (standard implication) would not allow to reject simultaneously highly ambiguous and outlying patterns, whereas schemes based on algebraic or parametrical implications do (provided an appropriate value for the parameter), so a better classification performance can be expected. One can also see in the bottom-plot that tuning the parameter allows to reject patterns for ambiguity as well as for distance (a higher value of γ for the Hamacher family and a lower value for the Dombi family) as pointed out in the discussion.

Experimental results

In this section, we report experiments carried out on both artificial and real benchmark datasets for which it is beneficial to introduce the ambiguity reject option because the classes overlap in the feature space. The proposed class-selective rejection scheme is compared to the usual rejection schemes presented in section 2. For additional comparison, results obtained using the two very recent classification rules proposed by Tax and Duin [START_REF] Tax | Growing a multi-class classifier with a reject option[END_REF] called Outlier-norm and Target-norm are given, the former being especially designed for distance rejection. Note we did not detailed these (not usual) rules here because they do not rely on an ambiguity measure, therefore they cannot be derived using fuzzy R-implications, by contrast to the previous ones. In all cases, the L-step was performed using Eqs.(1-2) with α i = 1 (∀i = 1, c).

The datasets

Two synthetic datasets are used: D which contains 2000 points drawn from two normal seven-dimensional distributions of 1000 points each with means v 1 = t (1 0 • • • 0) and v 2 = t (-1 0 • • • 0), and equal covariance matrices Σ 1 = Σ 2 = I, and DH which consists of two overlapping gaussian classes with different covariance matrices according to the Highleyman distribution, each composed of 800 observations in R 2 , see [START_REF] Highleyman | Linear decision functions, with application to pattern recognition[END_REF]. Real datasets are taken from the UCI Machine Learning Repository [START_REF] Blake | Uci repository of machine learning databases[END_REF]. The characteristics (number n of patterns, number p of features, number c of classes, degree of overlap) are reported in Table 5.

Results

Table 6 shows the classification performance of the different rejection schemes obtained by a 10-fold cross-validation procedure on the different datasets. In all cases, the threshold t was set to reject 10% of the data, so that 90% is the best achievable correct classification rate performance, then the error rate is (90correct)%. The best results are indicated in bold. Note that there are no outliers in the datasets, so that a part of the rejected points are considered as outliers whereas they belong to classes. It appears from these results that parametrical implications generally outperform usual rejection schemes as well as non usual ones (Outlier-norm, Target-norm), e.g. I Hγ=2 and I Dγ=0.5 . As expected in the previous section, these schemes enable to reject both ambiguous and outlying patterns. Furthermore, the tradeoff to be found between a scheme which

Conclusion and perspectives

In this paper, a generalized class-selective rejection scheme based on a logical approach to pattern assignation is presented allowing to either reject only ambiguous patterns or ambiguous and outlying patterns. For this purpose, we propose to design a family of ambiguity measures based on fuzzy residual implication functions, which indicate to which extent a pattern should be assigned to n classes depending on its membership degrees from the truth value of the implication. These measures assess the relationships between membership values with various combination of triangular norm operators, including parametrical families. It is shown that the proposed scheme generalizes well-known ones of the literature on pattern classification with reject options. It appears from experiments on both synthetic and real datasets that using, as the basis for residual implication computation, triangular norms greater than the Łukasiewicz triangular norm and lower than the standard one, gives better classification performance. Furthermore, measures taking in consideration several membership degrees, so that interactions between classes are taken into account, also give better results.

A future work will consist in defining new class-selective rejection schemes based on other parametrical triangular families (Sklar, Frank, Yager and so on) and compare their classification performance. We also think that, depending on the context of the pattern recognition problem, other implications functions than the residual implication ones would be suitable. We plan to make an extensive study on the behavior of S-implications which are an immediate generalization of the usual boolean implication, QL-implications coming from quantum mechanic logic, and D-implications which are the contraposition with respect to a negation of QL-implications, see [START_REF] Mas | A survey on fuzzy implication functions[END_REF] for definitions.

Table 3 : 2 10 II

 3210 Hamacher implications examples for a = 0.9, b = 0.8, c = 0.1 and d = 0.05. γ 0 Hγ (a, b) 0.87 0.89 0.93 I Hγ (a, c) 0.10 0.12 0.19 I Hγ (c, d) 0.09 0.65 0.90 • Dombi: decreasing the value of γ will make two fuzzy values more similar because lim γ→+∞ I Dγ (a, b) = b while lim γ→0 Dγ (a, b) = 1 whatever (a, b) ∈ [0, 1] 2 . Analogously to Hamacher family, I Dγ is non-increasing with γ since ∂I Dγ ∂γ ≤ 0.

Table 4 :.5 2 10 I

 410 Dombi implications examples for a = 0.9, b = 0.8, c = 0.1 and d = 0.05. γ 0Dγ (a, b) 0.97 0.81 0.80 I Dγ (a, c) 0.12 0.10 0.10 I Dγ (c, d) 0.35 0.06 0.05 The simple graphical example shown in Fig.1 illustrates how the different implications behave. The top-plot shows a onedimensional dataset composed of two classes ( and ×) described by a distance-based model (Eqs.(1-2)) with α i = 1 (∀i = 1, c). In the middle, implication truth values for the standard, algebraic, and Łukasiewicz triangular norms, corresponding to Ha, Frélicot and Horiuchi class-selective schemes respectively, as well as Chow's scheme are shown. Truth values when using parametrical implications are shown in the bottom-plot. Observing the data points in the top-plot allows to obtain the bounds of intervals of x values where the classes do not overlap, therefore for which no misclassification should

1 I 2 I 5 I

 125 Hγ , γ = 0I Hγ , γ = Dγ , γ = 0.Dγ , γ = 2Parametrical Ambiguity Measures

Figure 1 :

 1 Figure 1: Original outputs using Eqs.(1-2) for two classes with normal distributions (top), implication truth values with usual triangular norms (middle) and implication truth values with Hamacher and Dombi families (bottom).

Table 5 :

 5 The datasets and their characteristics.

	Dataset	n	p	c	Overlap
	D	2000	7	2	slight
	DH	1600	2	2	very slight
	Ionosphere	351	34 2 very strong
	Forest	495411 10 2	moderate
	Vowel	528	10 11 very slight
	Digits	10992 16 10 very slight
	Thyroid	215	5	3	very slight
	Pima	768	9	2	strong
	Statlog	6435	36 6	slight
	Glass	214	9	6	moderate


Designing relational schema from an object model using model transformations Antoine Wiedemann 1 awiede01@univ-lr.fr SIDO, L3i, Université de La Rochelle

1 Introduction: Problem statement

The domain model [12,8] hereafter referred to as DM is a central model during information systems development. It serves to visualize real-world concepts as opposed to software objects. We want to help the database designer to derive from the DM a relational structure eventually made available to potentially multiple applications.

But there is no direct mapping between concepts of object and relational models, and as shown in table 1, there is a so-called object-relational impedance mismatch [4]. For example the internal identication of objects is very dierent from the identication of tuples. A relational tuple is identied by the value of a subset of its attributes (table columns). Each of the subsets is a key, and is dened by a unique constraint. There may be more than one key in a table. Integrity constraints (unique -including primary key-, referential and check constraints)

are an important part of every quality relational schema, as they prevent storing in its tables data that would be inconsistent with the domain model.

UML concepts Relational concepts

Class

Our proposal

We propose an automated relational database design method starting from a DM. This DM is assumed correct and we do not consider its validation. We provide specic annotations enabling the designer to express identication constraints (IC) on DM objects. An object IC may be composed of attributes and/or roles. Each IC is bound to become a unique constraint in the relational schema.

We help the designer during the DM annotation phase, by computing sets of allowed IC components. From the annotated DM we derive a relational model with integrity constraints. We believe that the targeted relational model avoids redundancy although classical normalization theory [6] doesn't apply, since it does not take null values into account. Classical normalization imposes classes merging in case of 1-1 association. To respect the designer vocabulary more closely, we sometimes step back from these principles. The relational model produced by our process can be viewed as a multi-purpose model from which relational artefacts (UML 2.0) can be derived (SQL, physical schema . . . ). CREATE Using the QVT approach, we build transformations that take a whole model as input. This makes the input model refactoring costly, since even a small change on it forces to recompute everything from the start. Perhaps we should split our transformations into smaller ones.

Implementation using MDE

Another challenge we face is the denition of a mechanism suited to practically add annotations to our DM. At the time of writing we do not have a fully integrated CASE tool that would take care of the translation of graphical symbols (stereotypes) into metaclasses instances. To support the formal proof that our relational schema avoids redundancy, we also try to generate on the y traceability links between input and output models.

Contribution

The whole process tends to ensure the quality of the resulting schema with the same purpose as classical normalization [6], i.e. minimizing redundancy, which is very dierent from ORM techniques. We decide to retain -within the database schema -the meaningful names from the domain terminology, especially by avoiding some inopportune table fusions or creations. We provide support to the designer through control and supervision during the annotation process on DM and SMDs, enabling further automation of the design process. Contrary to E/R-like methods, we handle 0..1 multiplicities in the DM and accept NULL constraints in the relational model.

With respect to MDE implementation, we extend UML by dening appropriate specializations of some of its metaclasses. Therefore we take benet of the stereotypes extension mechanism, adopt their standard notation and make the various user-annotation steps fully UML-compliant. As outlined in Section 2.2, our work raises various questions about MDA integration. Beyond the simple MDA transformation pattern of a single model into another, we also have to master more complex model processing, such as model and inter-model annotation and also model composition. We expect to bring new contributions by coping with these challenges.

References

Fig. 1 .

 1 Fig. 1. Sample DM

⇔

  Fig. 5. Sample state machine diagram of the Training class and additional designer annotations

Table Association

 Association

	CASE tools enable relational model generation from an UML diagram, but the
	quality of the result is not satisfactory [11]: missing unique constraints, no way
	to use role to express constraints. Besides relational database design, some pat-
	terns consider the mapping between object and relational concepts [1]. Some are
	implemented in various Object Relational Mapping (ORM) tools that provide
	a persistence layer to applications objects and hide the underlying database ar-
	chitecture (Hibernate, JDO, ActiveRecord 1 , . . . ). Constraints checking is then
	mainly left to the applications while the RDBMS capabilities are under-used. So
	mapping Java objects to relational tables and automatically generating queries
	is not the problem we try to solve. We do not provide an ORM persistence layer
	that would hide the RDBMS and we do not automatically generate queries [13].
	Generalization	Foreign Key (referential constraint)
	Attribute	Column
	Role
	Constraint	Key (unique constraint)
	[0..1] multiplicity	no not null constraint
	Table 1. The object relational impedence mismatch
	Previous approaches use E/R diagrams [5] as a design language to produce a
	relational schema or SQL code. However, they do not handle [0..1] multiplicities
	and do not generate SQL code with NULL values. Moreover today the UML is
	widely accepted and used so we try to keep the database designer work in the
	same formalism. Many patterns are dened in the literature to map UML to
	relational concepts, but the transformation is not automated [18, 7]. Dierent

TABLE Training

 Training

				(
		ID_TRAI NUMBER NOT NULL, topic VARCHAR(30) NOT NULL,
		start	DATE	NOT NULL, end	DATE	NOT NULL,
		trainee NUMBER NOT NULL,
		CONSTRAINT PK_TRAI PRIMARY_KEY (ID_TRAI ),
		CONSTRAINT K1_TRAI UNIQUE (trainee,start) );
		ALTER TABLE Training
		ADD CONSTRAINT FK_STUD FOREIGN_KEY (Trainee )
		REFERENCES Student.ID_STUD ;
			Fig. 4. SQL of the output relational model
	2.2	Problems encountered so far