key: cord-0044837-9ey49pj5
authors: Coletti, Giulianella; Petturiti, Davide; Bouchon-Meunier, Bernadette
title: A Measurement Theory Characterization of a Class of Dissimilarity Measures for Fuzzy Description Profiles
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_20
sha: 838601fe4682ed06354519f12da7890df68333ac
doc_id: 44837
cord_uid: 9ey49pj5

We consider objects associated with a fuzzy set-based representation. By using a classic method of measurement theory, we characterize dissimilarity relations agreeing with a particular class of fuzzy dissimilarity measures. Dissimilarity measures in the considered class are those only depending on the attribute-wise distance of fuzzy description profiles. In particular, we analyze the subclass of weighted Manhattan dissimilarity measures.

Many situations in daily life or in science need to distinguish between several objects. Therefore, similarity and dissimilarity measures are important to evaluate a degree of resemblance between two or more objects. Many similarity/dissimilarity measures are available in the literature and the choice of one of them is done each time two images, cases, objects, situations, texts or data must be compared.

We are interested in measuring the similarity/dissimilarity of general objects characterized by a profile formed by a finite number of attributes or features. Then any object is identified by a vector which is binary (if the features can only belong or not to the object) or, as it has been more recently preferred, with elements in [0, 1] (if a partial degree of membership is accepted). In this setting, one can simply compare the vectors, rather than the objects themselves. For that,

The first and second authors are members of GNAMPA-INdAM. The second author was supported by University of Perugia, FRB 2019, project "Modelli per le decisioni economiche e finanziarie in condizioni di ambiguità ed imprecisione". many papers on this subject present in the literature (see for instance [5, 7, 10] ) discuss about the opportunity of considering as dissimilarity measure a (pseudo) distance function or a measure of comparison, as studied in [1] generalizing Tversky's contrast model [11] (for a general parametrised form, see [5] ). Usually the comparison is made for a particular environment and "a posteriori" (on the basis of the obtained results), focusing on one or more specific properties.

With the purpose to provide conscious reasons to use a particular similarity measure on the basis of the semantics behind this choice, in [2] [3] [4] we characterized two classes of similarity measures using the paradigm of measurement theory. These classes are very large and contain as particular cases almost all the known measures in the sense of Tversky's contrast model and its generalizations. The study starts from the concept of comparative similarity and provides the conditions related to the primitive idea of similarity which are accepted when choosing a measure of this class.

The aim of this paper is to make an equivalent study for dissimilarity measures which only depend on the distances between the degrees of membership of two objects, related to any feature. This class contains many distances (for instance, the Manhattan distance, the Minkowski distance, and the weighted Euclidean distance). The particular subclass of the weighted Manhattan distance (depending on a vector of parameters) is then considered and is completely characterized by the comparative dissimilarity agreeing with one element of such class.

Let H be a set of p attributes h k , (k ∈ I = {1, . . . , p}), each of which being present in an object with a degree of membership μ k (·) ∈ [0, 1].

Assume that the attributes in H are ordered increasingly according to indices in I. Let Y = [0, 1] p be the set of all fuzzy description profiles: objects are identified through vectors X = (x 1 , . . . , x p ) ∈ Y, where x i ∈ [0, 1] expresses the degree of membership of attribute i in the considered object. In other words, fuzzy description profiles in Y can be regarded as membership functions of fuzzy subsets of the ordered set H of p attributes. Let us stress that Y is endowed with the partial order relation ≤ defined component-wise.

Since the attributes can be expressed by a vague characterization, we can regard each of them as a fuzzy subset of a corresponding hidden variable. So each X ∈ Y is a projection of the Cartesian product of p possibly fuzzy subsets of p variables. For instance if the attributes h 1 and h 2 represent a person as "old" and "fat", every X = (x 1 , x 2 ) is a projection of the Cartesian product of the fuzzy sets "old" and "fat" of variables "age" and "weight", both taking values in R.

We denote by X ⊂ Y the set of crisp description profiles, i.e., X = {0, 1} p , and for any X ∈ Y, we consider the support s X = {i : x i > 0}, so, in particular, 0 is the fuzzy description profile with s X = ∅. More generally, if ε ∈ [0, 1], then ε denotes the element of Y whose components are all equal to ε.

the value x i − δ, and by x η i the value x i + η, and consider the elements of Y:

which is referred to as the complement of X.

Let us now consider a comparative dissimilarity that is a binary relation on Y 2 , with the following meaning: for all X, Y, X , Y ∈ Y, (X, Y ) (X , Y ) means that X is no more dissimilar to Y than X is dissimilar to Y .

The relations ∼ and ≺ are then induced by in the usual way:

If is assumed to be complete, then ∼ and ≺ are the symmetric and the asymmetric parts of , respectively.

Let be a comparative dissimilarity and D :

As is well-known, if is complete, the above conditions can be summarized as follows:

Given a comparative dissimilarity relation on Y 2 , in the following we propose a set of axioms that reveal to be necessary and sufficient for to have a dissimilarity measure representation inside a suitable class of dissimilarity measures.

is a weak order on Y 2 (i.e., it is a complete and transitive binary relation on Y 2 ).

We note that the completeness of relation can be removed and required only in some specific cases: we assume it for simplicity.

The next axiom requires the comparative degree of dissimilarity to be independent of the common increment of presence/absence of the features in the objects of a pair. In fact, what is discriminant is the difference between the membership degrees of each feature.

(FD1) For all X, Y ∈ Y, for all k ∈ I, for all ε ≤ min(x k , y k ), it holds:

The next example shows a situation of three pairs that the axioms (FD0) and (FD1) require to be equivalent. Example 1. Let us consider a comparative dissimilarity among apartments in New York, described by the following attributes:

a = it is small; -b = it is centrally located; -c = it has a modern kitchen; -d = it has a panoramic view; -e = it is near a metro station.

Given the fuzzy description profiles below, axioms (FD0) and (FD1) require that one must retain (X,

The next axiom is a local strong form of symmetry.

Y k = (y 1 , . . . , x k , . . . , y p ), it holds:

Example 2. Refer to the features in Example 1 and consider the fuzzy description profiles below.

As the following proposition shows, for a transitive complete relation, local symmetry implies symmetry. We note that the transitivity is necessary and that the converse does not hold. Proof. The proof trivially follows by applying at most p times (FD2) and (FD0).

The next proposition shows that under axioms (FD0) and (FD1), all pairs of identical fuzzy description profiles are equivalent.

Let be a comparative dissimilarity on Y 2 . If satisfies axioms (FD0) and (FD1) , then for every X ∈ Y one has: (1, 1) ∼ (X, X) ∼ (0, 0).

Proof. For every X ∈ Y, in particular X = 1, apply p times axiom (FD1) taking ε = x k and then use (FD0).

The following axiom is a boundary condition. It provides a natural left limitation: "the elements of each pair (X, Y ) are at least dissimilar to each other as an element of the pair is from itself". On the other hand, for the right limitation it is not enough to refer to any pair (X, X c ) formed by a profile and its complement, but it is required that the profile X is crisp, or equivalently that the supports of X and X c are disjoint.

The following is a monotonicity axiom.

(FD4) For all X, Y ∈ Y, for all k ∈ I, such that x k ≤ y k , for all 0 < ε ≤ x k and 0 < η ≤ 1 − y k , it holds:

. The following Theorem 1 shows that the introduced axioms are necessarily satisfied by any comparative dissimilarity agreeing with a dissimilarity measure, taking into account the distances of the degree of membership of each feature in the compared fuzzy description profiles. The same axioms become necessary and sufficient together with the following structural axiom (Q), known as Debreu's condition [6] , which assures the representability of a weak order by a real function.

We need to precise that we adopt as fuzzy inclusion the classic concept introduced by Zadeh [12] , as follows: if X, Y are fuzzy sets of a set C = {z 1 , . . . , z n }, then

In particular, in our case, we have that X ⊆ Y if and only if every component of X is smaller than or equal to the same component of Y , i.e. every attribute is no more present in X than it is in Y . So, X ⊆ Y can be written as X ≤ Y , where the inequality is component-wise.

[0, 1] representing in the sense of Definition 1 and a function ϕ : Y → R such that:

Proof. We first prove that Let us consider now the implication (ii) =⇒ (i). Every binary relation representable by a real function satisfies axiom (FD0) and (Q) [8] . We must prove that satisfies axioms (FD1)-(FD4): taking into account representability of by Φ we deduce that condition c) in (ii) implies (FD1) and (FD2) whereas condition a) implies (FD3). To prove axiom (FD4) it is sufficient to consider that Φ assigns 1 to all and only the elements of the equivalence class of (1, 0), i.e. only to the pairs (X, X c ) with X ∈ X . Similarly, Φ assigns 0 to all and only the elements of the equivalence class of (0, 0), i.e. to the pairs (X, X) for every X ∈ Y.

Condition (ii) of Theorem 1 identifies a too wide and therefore too general class of functions. In the following we will study the relations representable by the elements of a particular subclass of functions Φ that is the class of the weighted Manhattan distances.

The next axiom will represent "the constraint accepted" to obtain that the function representing our comparative dissimilarity belongs to this particular subclass. . . . , n, for all λ 1 , . . . , λ n > 0 it holds:

The above axiom has an easy interpretation. First of all it requires to evaluate as equally dissimilar every pairs (X, Y ) and (|X − Y |, 0). Moreover, it asserts that if you have n pairs (X i , Y i ) of fuzzy profiles and you judge the elements of each of them no more dissimilar than those of other n pairs (X i , Y i ), with at least a strict comparison, combining in a positive linear combination the first and the second you cannot obtain two vectors Z and Z such that the fuzzy

In the next example we provide a comparative dissimilarity assessment which violates the above rationality principle. H a b c d e X 1 1/2 1 1/4 3/4 1/10 Y 1 1/2 2/3 1/4 1/2 1/10 X 2 1 1 1/6 1/2 1/2 Y 2 1/2 1 1/6 1/2 1/2 X 3 2/3 2/3 1/3 0 1/4 Y 3 1/6 1 1/3 0 1/4 X 4 1/8 1 1/2 1/2 0 Y 4 1/8 1 1/3 1/4 0 X 5 1 1/8 0 0 1 Y 5 1/2 1/8 0 1/4 1 X 6 0 1/2 1/3 0 0 Y 6 0 1/6 1/3 0 2/3 X 7 1/4 1/6 1/6 1 1/3 Y 7 1/4 1/6 0 1 1 X 8 0 1/3 1/4 3/4 0 Y 8 1/2 0 1/4 1/2 0 Suppose now to assign the following reasonable relation:

It is easy to prove that the relation violates axiom (R). By trivial computations, taking all λ i 's equal to 1, one obtains

The next theorem shows that, for a complete , condition (R) implies all the axioms from (FD0) to (FD4). Nevertheless, since condition (R) deals with finite sets of pairs, condition (Q) is not guaranteed to hold, so (R) does not assure representability of on the whole Y 2 .

Proof. To prove transitivity suppose that we have (X,

contradicting (R). The proof of the other cases is similar.

To prove (FD1) and (FD2) it is sufficient to note that

To prove condition b) let us consider that for all and only X ∈ X one has |X − X c | = 1 ≥ |X − Y |. Similar considerations prove (FD4).

In the following we consider nontrivial relations , i.e., we assume that there exist (X, Y ), (X , Y ) with (X, Y ) ≺ (X , Y ).

Let be a nontrivial complete comparative dissimilarity relation on a finite F ⊂ Y 2 . Then, the following statements are equivalent:

Proof. Since F is finite, the binary relation amounts to a finite number of comparisons. Consider the sets

with s = cardS and w = cardW, and fix two enumerations 

Indeed, if we have a weight vector α satisfying (ii), then setting β = α T we get a solution of the above system. On the converse, if β is a solution of the above system, then defining α k = β k p i=1 βi , we get a weight vector α satisfying (ii).

By the Motzkin theorem of the alternative [9] , the solvability of the above system is equivalent to the non-solvability of the following system

with unknowns μ ∈ R 1×s and ν ∈ R 1×w . In particular, the first inequality reduces to

thus the non-solvability of the above system is equivalent to condition (R).

We note that, in the hypotheses of previous theorem, if (X, Y ), (X , Y ) ∈ F and it holds |X − Y | < |X − Y | then it must be (X, Y ) ≺ (X , Y ). In particular, if (0, 0), (1, 0) ∈ F, then it must be (0, 0) ≺ (1, 0).

Consider now the case where is a nontrivial complete relation on Y 2 . In this case, axiom (R) is not sufficient to assure representability of by a dissimilarity measure D α on the whole Y 2 . Indeed, axiom (R) guarantees representability only on every finite subset Y 2 , by virtue of Theorem 3. This implies that the parameter α characterizing D α depends on the particular finite subset F. To remedy this problem it is necessary to introduce a further axiom which requires that in each equivalence class (|X − Y |, 0) there must be one pair (ε, 0).

For all (X, Y ) ∈ Y 2 there exists ε ∈ [0, 1], such that (X, Y ) ∼ (ε, 0). 

In this paper we characterize comparative dissimilarities on fuzzy description profiles, representable by elements of a class of dissimilarity measures only depending on the attribute-wise distance. This very large class contains all L p distances and, in particular, the weighted Manhattan distances. Then, we characterize comparative dissimilarities representable by the latter subclass. Our aim for future research is to provide a characterization of comparative dissimilarities representable by other distinguished subclasses.

Towards general measures of comparison of objects

Fuzzy similarity measures and measurement theory

A study of similarity measures through the paradigm of measurement theory: the classic case

A study of similarity measures through the paradigm of measurement theory: the fuzzy case. Soft Computing (under revision)

On the transitivity of a parametric family of cardinality-based similarity measures

Representation of Preference Ordering by a Numerical Function

In: Image Registration. Advances in Computer Vision and Pattern Recognition

Foundations of Measurement

Nonlinear Programming

Comparison of distance and dissimilarity measures for clustering data with mix attribute types

Features of similarity

Fuzzy sets

Proof. The implication (ii) =⇒ (i) is easily proven, therefore we only prove (i) =⇒ (ii).For every finite F ⊂ Y 2 such that the restriction of to F is nontrivial, Theorem 3 implies the existence of a weight vector α F = (α F 1 , . . . , α F p ) with α F k ≥ 0 and p k=1 α F k = 1, such that the corresponding D α F represents the restriction of to F. Notice that, by Remark 1 every finite subset of Y 2 containing (0, 0) and (1, 0) meets nontriviality, as it must be (0, 0) ≺ (1, 0).. In particular, denoting by E k the element of Y whose k-th component is 1 and the others are 0, we have that there exists

Moreover, for all k = 1, . . . , p, we haveHence, there exists a weight vector α = (α 1 , . . . , α p ) with α k ≥ 0 andand such weight vector is unique. Indeed, suppose there exists α = (α 1 , . . . , α p ) with α k ≥ 0 and p k=1 α k = 1, such that D α represents on the whole Y 2 and α = α. For k = 1, . . . , p, it holds that (E k , 0) ∼ (α k , 0) ⇐⇒ D α (E k , 0) = α k = α k = D α (α k , 0), reaching in this way a contradiction.