Novel similarity measure for interval-valued data based on overlapping ratio

In computing the similarity of intervals, current similarity measures such as the commonly used Jaccard and Dice measures are at times not sensitive to changes in the width of intervals, producing equal similarities for substantially different pairs of intervals. To address this, we propose a new similarity measure that uses a bi-directional approach to determine interval similarity. For each direction, the overlapping ratio of the given interval in a pair with the other interval is used as a measure of uni-directional similarity. We show that the proposed measure satisfies all common properties of a similarity measure, while also being invariant in respect to multiplication of the interval endpoints and exhibiting linear growth in respect to linearly increasing overlap. Further, we compare the behavior of the proposed measure with the highly popular Jaccard and Dice similarity measures, highlighting that the proposed approach is more sensitive to changes in interval widths. Finally, we show that the proposed similarity is bounded by the Jaccard and the Dice similarity, thus providing a reliable alternative.


I. INTRODUCTION
Similarity measures are widely utilized in a range of applications including decision making, data aggregation, approximate reasoning, and machine learning. Measuring the similarity between two objects captures the degree to which they are alike. Similarities are commonly expressed as nonnegative real numbers, often between 0 (completely dissimilar) and 1 (identical) for simplicity. Similarity is typically assumed to be symmetrical; however, for certain stimuli, similarity may be better modeled by uni-directional or asymmetric functions [1]. Various similarity measures have been introduced in the literature to assess the likeness of data structures including numerals, intervals, and crisp and fuzzy sets. As individual similarity measures have their respective strengths and weaknesses, the selection of the most appropriate measure is widely considered to be application dependent.
Recently, interval-valued data and associated intervalsimilarity have gained much interest as they enable the efficient representation of imprecise and uncertain information [2]. Thus, intervals have been used in many applications, including the modeling of survey data [3], the clustering of symbolic data [4], and the capturing of natural language expressions [2].
For comparing intervals in terms of their similarity, the Jaccard [5] and Dice [6] similarity measures are the most commonly used. Both of these measures provide a symmetrical Pairs of intervals similarity which increases gradually from minimum similarity (0) to maximum similarity (1) in respect to increasing intersection between the intervals. Nevertheless, they are often subject to aliasing, i.e., they yield the same similarity for very different interval pairs. Fig. 1 shows an example of two interval pairs for which the Jaccard and the Dice similarity measures give the same similarity of 0.33 and 0.50 respectively-though intuitively, this is unexpected. Another way of viewing the example is that the measures, in effect, are sometimes not sensitive to (changes in) the relative width of the intervals, being instead driven by the size of their intersection and union. It is reasonable to consider that as the width of an interval varies, the similarity varies as well. Therefore, we propose a new similarity measure for pairs of intervals that focuses on the following similarity features: • sensitivity to changes in the width of the intervals; • sensitivity to the size of the intersection when one interval is a subset of another.
The proposed similarity measure uses the reciprocal overlapping ratios of the intervals to compute their asymmetric similarities which in turn are used to establish an overall symmetrical similarity, bounded by [0,1]. We compare the behavior of the new measure with the Jaccard and the Dice similarity measures using synthetic interval datasets. Along with the standard properties of similarity measures, we explore the properties of invariance and linearity for all three similarity measures. The paper is structured as follows. Section II briefly reviews the Jaccard and the Dice similarity measures. Section III introduces the proposed similarity measure based on the overlapping ratio of intervals and discusses its properties. We demonstrate the behavior of the proposed similarity measure in comparison to both Jaccard and Dice in Section IV. Lastly, Section V concludes the paper and provides suggestions for future work.

II. BACKGROUND
We now briefly review the concept of similarity measures as well as the specific similarity measures of Dice and Jaccard, the two commonly applied measures in the literature.

A. Similarity Measures
A similarity measure S(A, B) → [0, 1] is a real-valued function that determines the similarity between two objects A and B. Generally, the similarity between two objects is bounded by 0 and 1, where 0 means that both objects are completely different and 1 means that they are identical. The four common properties of a similarity measure for sets A, B and C are as follows [7]:

B. Jaccard Similarity Measure
The Jaccard similarity measure [5] is one of the most widely used similarity measures. It satisfies all of the above properties of a similarity measure [7]. Generally, the Jaccard similarity of two sets is defined as the ratio of the cardinality of their intersection and the cardinality of their union, Using the crisp set difference operation [8], (1) can be written as where A\B is the set of items that are in A but not in B and B\A is the set of items that are in B but not in A. Note that this alternative form of the Jaccard similarity measure at (2) is relevant for showing its relationship with the Dice and our proposed similarity measures, detailed in Section III. Beyond crisp sets, the Jaccard similarity measure is used to estimate the similarity for intervals or sets of intervals [9], [10]. A closed intervalĪ i is a set of real numbers characterized by two endpoints For comparing the intervals I i andĪ j , the Jaccard similarity measure is expressed as where |Ī i ∩Ī j | is the size of the intersection betweenĪ i and I j and |Ī i ∪Ī j | is the size of the entire interval segment(s) covering bothĪ i andĪ j . Hence, S J (Ī i ,Ī j ) = 1 whenĪ i andĪ j are completely overlapping and 0 when they are not overlapping at all. Similar to (2), we can rewrite (3) as where |Ī i \Ī j | is the size of the interval segment ofĪ i that is not overlapping withĪ j and |Ī j \Ī i | is the size of the interval segment ofĪ j that is not overlapping withĪ i . Along with crisp sets and intervals, many use the Jaccard similarity measure for assessing the similarity between type-1 sets [11]. A fuzzy set [12] is defined as a set where the set's elements have membership ranging between 0 and 1. Formally, a type-1 fuzzy set F in the universe of discourse X is written as [13] F is the membership grade of the element x in F . For two type-1 fuzzy sets F 1 and F 2 , the Jaccard similarity can be written as [14] S where µ F1 (x i ) and µ F2 (x i ) are the membership grades of x i in F 1 and F 2 respectively. Equation (6) yields a value of 1 when the fuzzy sets are identical and 0 when they are completely disjoint. Note that the Jaccard similarity measure has been extended for interval type-2 [15], [16] and general type-2 fuzzy sets [17]; though, this is not discussed here.

C. Dice Similarity Measure
The Dice similarity measure [6] is closely related to Jaccard and is also a popular similarity measure. It considers the ratio of the size of the intersection of two sets and the average of their cardinality/size. Like the Jaccard similarity, it produces outputs in [0, 1]. Specifically, for two crisp sets A and B, the Dice similarity is expressed as where |A| is the size of the set A. We can rewrite (7) by applying the crisp set difference operation [8] Note that the alternative expressions of Jaccard (2) and Dice (8) show clearly that the averaging operation in the denominator of (8) results in the Dice similarity always being equal (when sets are identical) to or larger than the Jaccard similarity. We expand on this in Section III.
In [9], [10], the Dice similarity is used along with the Jaccard similarity for interval-valued evidence. By following (4), the Dice similarity for two intervalsĪ i andĪ j can be expressed as While less frequently used for fuzzy sets than Jaccard, the Dice similarity measure was used in [18], [19] for trapezoidal fuzzy numbers in the context of solving multicriteria decisionmaking problems.
III. OVERLAPPING RATIO BASED SIMILARITY MEASURE In this section, we introduce a new similarity measure for intervals based on their overlapping ratio. The proposed measure estimates the overall similarity of a pair of intervals by considering the reciprocal similarity of each of the intervals within the pair. We first define the concept of the overlapping ratio for a pair of intervals and, later, present the new proposed similarity measure and discuss its essential properties.
A. Overlapping Ratio of Intervals Definition 1. The overlapping ratio (OR) of a given interval I i within an interval pair {Ī i ,Ī j } captures the ratio of the size of the intersection of the pair and the size of the given interval. The OR is defined as where |Ī i ∩Ī j | is the size of the intersection betweenĪ i and I j and |Ī i | is the size ofĪ i . Note that for any intervalĪ i with a size of 0, i.e., |Ī i | = 0, OR(Ī i ,Ī j ) is set to 0.
From (10), it is clear that the overlapping ratio for an interval in a pair will fall under one of the following cases:

B. Similarity Measure Based on the Overlapping Ratio
As noted, the motivation behind proposing a new similarity measure is to capture the potentially (very) different width of both intervals in the similarity calculation. Thus, the proposed overlapping ratio based similarity measure S OR , defined next, takes into consideration the reciprocal similarity of both intervals within a pair in order to estimate their overall similarity. Definition 2. The overlapping ratio based similarity measure S OR for a pair of intervals,Ī i andĪ j , is the t-norm of their reciprocal overlapping ratios, defined as where is a t-norm.
In this paper, we use the minimum t-norm for throughout. We will discuss the product t-norm in future work.
Similar to (4) and (9), we can rewrite (11) as where |Ī i \Ī j | is the size of the non-overlapping segment of the intervalĪ i with respect to the intervalĪ j and vice-versa for |Ī j \Ī i |.
Note that a distance measure D OR (Ī i ,Ī j ) can easily be derived from the S OR similarity measure (11) by taking its complement-i.e., 1 − S OR (Ī i ,Ī j ) -thus capturing the dissimilarity between both intervals. We discuss this distance measure in more detail, including proving that it is a metric, in future work.

C. Properties of the Proposed Similarity Measure
This section explores the properties of the proposed overlapping ratio similarity measure S OR (Ī i ,Ī j ).
AsĪ j ⊆Ī k , it follows that |Ī j | ≤ |Ī k |. Therefore, |Īi| |Īj | ≥ |Īi| Theorem 5. S OR (Ī i ,Ī j ) is bounded by the Jaccard and the Dice similarity measures when is the minimum t-norm. That is, Proof: For the interval pair {Ī i ,Ī j }, consider the formulations of the similarity measures at (4), (9), and (12). To prove this theorem, we consider four cases: Case 1: IfĪ i =Ī j , then all three measures yield a similarity of 1. That is, Case 3: IfĪ i ⊂Ī j (complete subset), then |Ī i ∩Ī j | = |Ī i |. With respect toĪ i , there is no non-overlap segment ofĪ j ; hence, |Ī i \Ī j | = 0. Inversely, there is a non-overlap segment ofĪ j in Ī i ; thus, |Ī j \Ī i | = 0. In this case, the three similarity measures can be simplified to which implies that Case 4: Considering the case w i ≤ w j , the three similarity measures can be rewritten as It is true that Note that for the case w j ≤ w i , the same procedure can be used to prove the above relation.

IV. DEMONSTRATION AND ANALYSIS
In this section, we demonstrate and analyze the behavior of the proposed S OR similarity measure by comparing its output to those of both Jaccard and Dice for a set of key synthetic examples. We specifically focus on exploring the following key aspects: • Aliasing, i.e., similarity measures producing the same output for different input intervals. • Behavior when one interval is a complete subset of another. Pairs of intervals  • Behavior for intervals of equal size and equal overlapping ratios. • Invariance to scaling/multiplication of interval endpoints. • Linearity in measure output in respect to linearly increasing interval overlap.
1) Experiment on aliasing: In Fig. 2, four different pairs of intervals {Ī i ,Ī j } are considered, where all pairs have an intersection of equal size. The similarity results for the pairs using the three similarity measures are shown in Table I. The S J and the S D measures give a similarity of 0.15 and 0.26 respectively for all pairs. Indeed, both measures provide identical similarities for pairs of intervals when the size of the union of their non-overlapping segments remains constant. On the contrary, the proposed S OR measure yields different similarity for all cases. Note, that as shown in Theorem 5 the results of the S OR measure are bounded by the similarity produced by the S J and S D measures. The reason that the S OR measure produces different results for each case is that it captures changes in the width of both input intervals which affects their reciprocal similarity and the overall similarity.
2) Experiment with interval pairs when one interval is a complete subset of the other: Five interval pairs are shown in Fig. 3, whereĪ j is a complete subset ofĪ i in all pairs and overlapping by 10%, 20%, 30%, 40%, and 50%, respectively ofĪ i . Table II presents the similarity for all pairs with all three measures. Note that for all pairs, the overlapping ratio ofĪ j is 1 while the overlapping ratio ofĪ i depends on the size ofĪ i andĪ j , i.e., |Īi∩Īj | |Īi| . Therefore, intuitively their mutual similarity can be at most |Īi∩Īj | |Īi| for each pair. The S J and the S OR measures perform accordingly while the S D measure exceeds this limit. Pairs of intervals  3) Experiment with interval pairs of equal size and equal overlapping ratio: In Fig. 4, five interval pairs are shown, where the intervals are of equal size and their intersection is varied to be 10%, 20%, 30%, 40%, and 50% of their size. Table III provides the results for all pairs using the three similarity measures. In all pairs, the overlapping ratio is equal, and it is intuitive to expect the similarity to be the extent of this overlapping ratio. In this case, the S D and the S OR measures satisfy the expectation whereas the S J measure yields lower similarity.
4) Experiment on invariance: Five pairs of intervals are shown in Fig. 5 where both endpoints of I i1 and I j1 are gradually multiplied by a factor, n = {2, 3, 4, 5} to produce new interval pairs. Yet, the overlapping ratio is maintained for individual intervals in all the pairs. Adapting the definition from [21], a similarity measure is invariant if its similarity output remains constant regardless of multiplying the endpoints of interval pairs by a factor. Table IV shows the similarity for all pairs using the three measures where n refers to the factor applied to the interval endpoints. The results shows that all three measures satisfy the invariance property for the given pairs of intervals.

5) Experiment on linearity:
Adapting the definition from [21], a similarity measure on intervals is linear if its similarity output varies linearly in respect to a linear change in the size of the intersection of the intervals. In Fig. 6(a), the intersection between two intervals of equal size is gradually increased in 10% steps. The corresponding similarity outputs for the pairs and all three measures are shown graphically in Fig. 6 Pairs of intervals  Pairs of intervals  while the S J measure exhibits convexity (differences rise with the increase of intersection).

V. CONCLUSION AND FUTURE WORK
In this paper, we have introduced a new similarity measure that considers the reciprocal similarity of a pair of intervals in computing their overall similarity. We have used the overlapping ratio of the intervals within the pair for capturing the asymmetric similarity. We have also demonstrated that the new measure satisfies essential properties of a similarity measure. Lastly, we have compared the behavior of the proposed measure with the two popular Jaccard and Dice similarity measures using synthetic datasets. The results have shown that the proposed similarity measure is more sensitive to the changes in the width of intervals, and further it is invariant and linear. We have also proved that the proposed similarity is bounded by the Jaccard and the Dice similarity.
In future, we will use the proposed similarity measure for capturing the mutual agreement of interval-valued evidence for aggregation. As each α-cut of a normal and convex fuzzy set is a closed interval [22], we aim to extend the proposed similarity measure for comparing fuzzy sets.

ACKNOWLEDGMENT
Shaily Kabir acknowledges the financial support of the Commonwealth Scholarship Commission in the UK.