Computing Degrees of Subsethood and Similarity for Interval-Valued Fuzzy Sets: Fast Algorithms-猫眼课题宝

计算区间值模糊集的子集度和相似度：快速算法

DOI：

发表时间：

2008

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

H. Nguyen;V. Kreinovich

集合等价性A⊆B和集合相等A=B是集合论的基本概念。对于传统的(明确的)集合，每个元素a要么属于集合A，要么不属于A，并且对于每两个集合A和B，或者A⊆B或者A 6⊆B，为了描述常识和专家推理，使用模糊集合是有利的，其中对于每个元素a，存在a属于该集合的度μA(A)∈[0，1]。对于模糊集A和B，定义隶属度d⊆(A，B)和相等程度(相似度)d=(A，B)是合理的。在实践中，往往很难给每个元素a分配一个确定的隶属度μA(A)；更现实的是，期望专家描述该度的可能值的区间[μA(A)，μA(A)]。由此得到的区间值模糊集可以看作是所有可能的模糊集μA(A)∈[μA(A)，μA(A)]的一类。因此，对于区间值模糊集A和B，将隶属度d⊆(A，B)定义为d⊆(A，B)对所有A∈A和B∈B的可能值的范围是合理的-类似地，我们可以定义相似度d=(A，B)。到目前为止，还没有已知的通用算法来计算这些范围。在本文中，我们描述了这样的通用算法。新提出的算法是相当快的：对于n元泛集合的模糊子集，这些算法在O(n·log(N))时间内计算范围。一、问题的提法取代和集合式是集合论的重要概念。在传统集合论中，基本概念中有集合相等和子集的概念：如果两个集合A和B包含完全相同的元素，则它们相等；如果集合A的每个元素也属于B，则集合A是集合B的子集。由于这一重要性，希望将这些概念推广到模糊集合。在模糊集合论中，谈论隶属程度和相等(相似)是合理的。在传统的集合论中，对于每两个集合A和B，要么A是B的子集，要么A不是B的子集。类似地，A和B要么相等，要么这两个集合不同。模糊逻辑背后的主要思想是，对于模糊的、不精确的概念，一切都是一个程度问题；例如，参见[3]、[9]。因此，对于两个模糊集A和B，定义隶属度和相似度是合理的。如何描述取代程度：主要思想。在模糊逻辑和模糊集合论中，没有集合之间的替代度或相等(相似)度的固有概念。相反，模糊逻辑和模糊集合论的标准描述是从并和交的概念开始的。描述两个集合的并集的最简单方法是取相应的隶属函数的最大值：μA∪B(X)=max(μA(X)，μB(X))。类似地，描述两个集合的交集的最简单方法是取相应的隶属函数中的最小值：μA∩B(X)=Min(μA(X)，μB(X))。因此，为了描述取代和平等(相似)的程度，用并集和相交来表达取代和设定平等的概念是合理的。这一表达式在集合论中是众所周知的：·一般而言，A∩B⊆A，且·A⊆B当且仅当A∩B=A。因此，对于清晰有限集，为了检查A是否为B的子集，我们可以考虑比率|A∩B||A|，其中|A|表示集合A中的元素的数目：·一般而言，该比率介于0和1之间，且·该比率等于1当且仅当A是B的子集时。比率越小，来自A的不属于交集A∩B的元素越多，并因此不是集合B的一部分。因此，对于清晰集合，该比率可被视为A是B的子集的程度的合理度量。类似的定义可用于定义两个模糊集合的隶属程度。具体地说，对于有限模糊集，我们可以使用基数概念的自然模糊扩展：|A|DEF=μA(X)。让我们来描述一下得到的公式。由于我们只考虑有限的模糊集，因此我们可以考虑有限的话语宇宙。在不失去一般性的情况下，我们可以用数字1、2、…来表示话语宇宙的元素。。。因此，对应于模糊集合A的隶属函数的值可以表示为A1，。。。、An.类似地，对应于模糊集合B的隶属函数的值可以由b1，.。。、BN。在这些符号中，·对应于交集A∩B的隶属函数具有值MIN(a1，b1)，.。。，Min(an，bn)，·模糊集A的基数|A|等于n∑i=1 ai，以及·交集A∩B的基数|A∩B|等于n∑

Subsethood A ⊆ B and set equality A = B are among the basic notions of set theory. For traditional (“crisp”) sets, every element a either belongs to a set A or it does not belong to A, and for every two sets A and B, either A ⊆ B or A 6⊆ B. To describe commonsense and expert reasoning, it is advantageous to use fuzzy sets in which for each element a, there is a degree μA(a) ∈ [0, 1] to which a belongs to this set. For fuzzy sets A and B, it is reasonable to define a degree of subsethood d⊆(A, B) and degree of equality (degree of similarity) d=(A, B). In practice, it is often difficult to assign a definite membership degree μA(a) to each element a; it is more realistic to expect that an expert describes an interval [μ A (a), μA(a)] of possible values of this degree. The resulting interval-valued fuzzy set can be viewed as a class of all possible fuzzy sets μA(a) ∈ [μ A (a), μA(a)]. For interval-valued fuzzy sets A and B, it is therefore reasonable to define the degree of subsethood d⊆(A,B) as the range of possible values of d⊆(A, B) for all A ∈ A and B ∈ B – and similarly, we can define the degree of similarity d=(A,B). So far, no general algorithms were known for computing these ranges. In this paper, we describe such general algorithms. The newly proposed algorithms are reasonably fast: for fuzzy subsets of an n-element universal set, these algorithms compute the ranges in time O(n · log(n)). I. FORMULATION OF THE PROBLEM Subsethood and set equality are important notions of set theory. In traditional set theory, among the basic notions are the notions of set equality and subsethood: • two sets A and B are equal if they contain exactly the same elements, and • a set A is a subset of the set B if every element of the set A also belongs to B. Because of this importance, it is desirable to generalize these notions to fuzzy sets. In fuzzy set theory, it is reasonable to talk about degrees of subsethood and equality (similarity). In traditional set theory, for every two sets A and B, either A is a subset of B, or A is not a subset of B. Similarly, either the two sets A and B are equal or these two sets are different. The main idea behind fuzzy logic is that for fuzzy, imprecise concepts, everything is a matter of degree; see, e.g., [3], [9]. Thus, for two fuzzy sets A and B, it is reasonable to define degree of subsethood and degree of similarity. How to describe degree of subsethood: main idea. In fuzzy logic and fuzzy set theory, there is no built-in notion of degree of subsethood or degree of equality (similarity) between the sets. Instead, the standard descriptions of fuzzy logic and fuzzy set theory start with the notions of union and intersection. The simplest way to describe the union of the two sets is to take the maximum of the corresponding membership functions: μA∪B(x) = max(μA(x), μB(x)). Similarly, the simplest way to describe the intersection of the two sets is to take the minimum of the corresponding membership functions: μA∩B(x) = min(μA(x), μB(x)). Thus, to describe the degrees of subsethood and equality (similarity), it is reasonable to express the notions of subsethood and set equality in terms of union and intersection. This expression is well known in set theory: it is known that • in general, A ∩B ⊆ A, and • A ⊆ B if and only if A ∩B = A. So, for crisp finite sets, to check whether A is a subset of B, we can consider the ratio |A ∩B| |A| , where |A| denotes the number of elements in a set A: • in general, this ratio is between 0 and 1, and • this ratio is equal to 1 if and only if A is a subset of B. The smaller the ratio, the more there are elements from A which are not part of the intersection A ∩ B, and thus, not part of the set B. Thus, for crisp sets, this ratio can be viewed as a reasonable measure of degree to which A is a subset of B. A similar definition can be used to define degree of subsethood of two fuzzy sets. Specifically, for finite fuzzy sets, we can use a natural fuzzy extension of the notion of cardinality: |A| def = μA(x). Let us describe the resulting formulas. Since we only consider finite fuzzy sets, we can therefore consider a finite universe of discourse. Without losing generality, we can denote the elements of the universe of discourse by their numbers 1, 2, . . . , n. The values of the membership function corresponding to the fuzzy set A can be therefore denoted by a1, . . . , an. Similarly, the values of the membership function corresponding to the fuzzy set B can be denoted by b1, . . . , bn. In these notations, • the membership function corresponding to the intersection A ∩B has the values min(a1, b1), . . . , min(an, bn), • the cardinality |A| of the fuzzy set A is equal to n ∑ i=1 ai, and • the cardinality |A∩B| of the intersection A∩B is equal to n ∑

Computing Degrees of Subsethood and Similarity for Interval-Valued Fuzzy Sets: Fast Algorithms

计算区间值模糊集的子集度和相似度：快速算法

文献摘要

被引文献

相似文献