IIIT Theory Reading Group: Seminar Saturdays

Fuzzy Set Theory

Traditional View

Uncertainity is undesirable in science and should be avoided by all possible means

Alternate or Modern View

uncertainity is unavoidable and posseses some utility

"No data processing system, whether artificial or living, can process more than $2 \times 10^{47}$ bits per second per gram of its mass." - Bremermann's Limit

Crisp Set

The characteristic function($\chi_{A}$) of a crisp set($A$) maps all members of the universal set($X$) to $\{0, 1\}$

Fundamental Properties of Crisp Set Operations

Involution

Commutaivity

Associativity

Distributivity

Idempotence

Absorption by $X$ and $\phi$

Identity

Law of Contradiction

Law of Excluded Middle

De Morgan's Laws

Boolean Lattice

• Elements of $P(X)$ can be partially ordered using set inclusion $\subseteq$

• This lattice is distributive and complemented

Partitions

A family of pairwise disjoin subsets of $A$ is called a parition on A if the union of these subsets yeilds the original set A.

All $A_i$ are called blocks of the partition.

$\pi_1(A)$ is a refinement of $\pi_2(A)$ iff

This refinement relation ($\leq$) forms a partial ordering over the set of all partitions of $A$ ($\prod(A)$)

The pair ($\langle \prod(A), \leq \rangle$) is called the partition lattice of $A$

Nested Family

Let $\mathcal{A} = \{A_1, ..., A_n\}$ be a family such that $A_i \subseteq A_j \forall i = 1, 2, ..., n-1$

• $\mathcal{A}$ is called a nested family
• $A_1$ is called the innermost set
• $A_n$ is called the outermost set

Supremum and Infimum

Let $R \subseteq \mathcal{R}$

• If $\exists r \; \forall x \in R \; x \leq r \rightarrow upper\_bound(R) = r$
• If $\exists s \; \forall x \in R \; x \geq s \rightarrow lower\_bound(R) = s$
• Upper bound $r$ is the supremum iff no other upperbound is less than $r = sup R$
• Lower bound $s$ is the infimum iff no other lowerbound is greater than $s = inf R$

Fuzzy Sets: Basic Types

The charracteristic function can be generalized such that values assigned can fall within a specified range(usually $[0, 1]$) indicating membership grades of the elements in the set in question.

The membership function of a fuzzy set $A$ can be denoted by $A$ itself or $\mu_A$. We use the former.

$X$ is always a crisp set

• Fuzzy sets allow us to describe vague concepts expressed in natural language. Although these are often dependent on concepts.

• Even for similar concepts, fuzzy sets may vary considerably while being similar in a few key features.

• Fuzzy sets usually represent linguistic concepts such as low, medium and high and are used to define states of variables called fuzzy variables

• [Paradox] Data based on fuzzy variables provide us with more accurate evidence about real world phenomena than data based on crisp variables

Example

Fuzzy set $A = \{x|x \text{ is a real numbers close to }2\}$

Example

Ordinary Fuzzy Sets

Given universal set $X$, an ordinary fuzzy set $A$ is defined by a membership funtion of the form

• also called type 1 and level 1 sets

Interval-valued Fuzzy Sets

If suppose you cannot pick between a definite real value to express the membership grade of an element, and you're only able to identify lower and upper bounds of the membership grade, we have two options

• Discard the uncertainity, pick the middle maybe to be the grade

• Accept the uncertainity and include it in the definition of the membership function

where

where $\xi([0, 1])$ denotes the family of all closed intervals of real numbers in $[0, 1]$

• They allow you to express uncertainity in choosing the membership function
• Computationally more demanding

Fuzzy sets of Type 2

Upon further generelization, intervals can also be fuzzy sets (ordinary)

Where

$\mathcal{F}([0, 1]) =$ set of all ordinary fuzzy sets that can be defined within $[0,1$ - fuzzy power set of $[0, 1]$

• Have still greater expressive power, but are still more computationally demanding

Fyzzy Set of Type 3

When the membership grades assigned by type 2 fuzzy sets, are type 2 fuzzy sets themselves.

And so on...

L-Fuzzy Sets

Whem membership grades are represented by symbols of arbitriary set $L$ that is at least partially ordered

Usually L is a lattice and L-fuzzy sets capture all other fuzzy sets so far

Level 2 Fuzzy Sets

Fuzzy set defined within a universal set whose elements are ordinary fuzzy sets

• used when elements of $X$ cannot be specified precisely

Level 3 Fuzzy Sets

• Universal set consists of Level 2 Fuzzy Sets

and so on ...

Combinations

Type 2 + Level 2

and many more ...

FUZZY SETS: BASIC CONCEPTS

$\alpha$-Cuts and Strong $\alpha$-Cuts

Given fuzzy set $A$ defined on $X$ and any number $\alpha \in [0,1]$

Level Set of A

The set of all $\alpha \in [0,1]$ that represent distinct $\alpha$-cuts of a $A$

Total Ordering of $\alpha$s is inversely preserved by the set inclusion of the corresponding $\alpha$-cuts and strong $\alpha$-cuts

• both cuts form families of nested crisp sets

Support - $S(A)$ or $supp(A) = {}^{0+}A$

Core - $core(A) = {}^{1}A$

Height - $h(A) = \sup_{x \in X} A(x)$

Normal - If $h(A) = 1$, $A$ is normal

Subnormal - If $h(A) < 1$

Convexity

$\alpha$-cuts of a convex fuzzy set must be convex for all $\alpha \in (0, 1]$ in the classical sense

Theorm 1.1

A fuzzy set $A$ on $\mathcal{R}$ is convex iff

Cutworthy and Strong Cutworthy Property

Any property generelized from classical set theory into the domain of fuzzy set theory that is preserved in all $\alpha$-cuts for $\alpha \in (0, 1]$ in the classical sense is called a cutworthy property

If it is preserved in all strong $\alpha$-cuts for $\alpha \in [0, 1]$ then it is called strong cutworthy property)

Convexity is both cutworthy and strong cutworthy

Standard Fuzzy Set Operations

Standard Complement

• Equilibrium points - $x$ where $\overline{A}(x) = A(x)$

Standard Intersection and Union

Set Inclusion

Given $A, B \in \mathcal{F}(X)$

De Morgan Lattice

• A Fuzzy powerset can be viewed as a lattice with standard fuzzy intersection and union playing the roles of meet and join respectively.

• The lattice is distributed and complemented under the standard operations.

• It satisfies all Boolean lattice properties except the law of contradiction and the law of excluded middle

• $\langle \mathcal{F}(X), \subseteq \rangle$

Scalar Cardinality (or Sigma Count)

Degree of Subsethood

Alternate Representation

• only with finite support

Where $x_i \in {}^{0+}A$ and $a_i = A(x_i)$

When $X$ is countable $A = \sum_{i=1}^n a_i/x_i$ or $A = \sum_{i=1}^\infty a_i/x_i$

else when $X$ is an interval of real numbers $A = \int_x A(x)/x$

Interpret fuzzy set of $X$ with $n$ elements as an $n$-dimensional unit cube

• Whole cube represents $\mathcal{F}(X)$
• Vertices represent $\mathcal{P}(X)$

Distance between Fuzzy Sets $A$ and $B$ could be

Theorm 2.1

Let $A, B \in \mathcal{F}(X)$ and $\alpha, \beta \in [0,1]$, then

1. ${}^{\alpha+}A \subseteq {}^{\alpha}A$
2. $\alpha < \beta \Rightarrow {}^{\beta}A \subseteq {}^{\alpha}A$ and ${}^{\beta+}A \subseteq {}^{\alpha+}A$
3. ${}^{\alpha}(A \cap B) = {}^{\alpha}A \cap {}^{\alpha}B$ and ${}^{\alpha}(A \cup B) = {}^{\alpha}A \cup {}^{\alpha}B$
4. ${}^{\alpha+}(A \cap B) = {}^{\alpha+}A \cap {}^{\alpha+}B$ and ${}^{\alpha+}(A \cup B) = {}^{\alpha+}A \cup {}^{\alpha+}B$
5. x${}^{\alpha}(\overline{A}) = \overline{{}^{(1 - \alpha)+}A}$

• Properties 3 & 4 are cutworthy and strong cutworthy when applied to two sets or a finite number of sets because of the associativity of min and max

• Property 2 indicates that the $\alpha$ cuts and strong $\alpha$ cuts form a monotonically decreasing set sequence wrt $\alpha \Leftrightarrow$ nested family of sets

• Standard fuzzy complement is neither cutworthy or strong cutworthy

Maximum VS Supremum

If $X$ is a partially ordered set, and $S$ is a subset, then an element $s_0$ is the supremum of $S$ iff

• $s \leq s_0$ for all $s \in S$ and
• For all $t \in X$ such that for all $s \in S$ $s \leq t$ then $s_0 \leq t$

An element $m$ is the maximum of $S$ iff

• $s \leq m$ for all $s \in S$ and
• $m \in S$

• If $S$ has a maximum, then the maximum will be the supremum

• It is possible to have a supremum but not a maximum. Ex: set of all negative real numbers have no maximum but have a supremum($0$)

• If $S$ has a supremum $s$, then $s$ is also the mazimum iff $s \in S$

• If a particular set has both a supremum and a mazimum then they are the same

Theorm 2.2

Let $A_i \in \mathcal{F}(X)$ for all $i \in \mathcal{I}$, where $\mathcal{I}$ is an index set. Then,

$\bigcup_{i \in \mathcal{I}} {}^\alpha A_i \subseteq {}^\alpha \left ( \bigcup_{i \in \mathcal{I}} A_i \right )$ and $\bigcap_{i \in \mathcal{I}} {}^{\alpha} A_i = {}^{\alpha} \left ( \bigcap_{i \in \mathcal{I}} A_i \right )$

$\bigcup_{i \in \mathcal{I}} {}^{\alpha+} A_i = {}^{\alpha+} \left ( \bigcup_{i \in \mathcal{I}} A_i \right )$ and $\bigcap_{i \in \mathcal{I}} {}^{\alpha+} A_i \supseteq {}^{\alpha+} \left ( \bigcap_{i \in \mathcal{I}} A_i \right )$

Theorm 2.3.

Let $A, B \in \mathcal{F}(X)$. Then, for all $\alpha \in [0, 1]$

• $A \subseteq B \Leftrightarrow {}^{\alpha}A \subseteq {}^{\alpha}B$
• $A \subseteq B \Leftrightarrow {}^{\alpha+}A \subseteq {}^{\alpha+}B$
• $A = B \Leftrightarrow {}^{\alpha}A = {}^{\alpha}B$
• $A = B \Leftrightarrow {}^{\alpha+}A = {}^{\alpha+}B$

Fuzzy set inclusion are both cutworthy and strong cutworthy

Theorm 2.4

For any $A \in \mathcal{F}(X)$, the following properties hold

${}^{\alpha}A = \bigcup_{\beta < \alpha} {}^{\beta} A = \bigcup_{\beta < \alpha} {}^{\beta+} A$

${}^{\alpha}A = \bigcap_{\beta < \alpha} {}^{\beta} A = \bigcap_{\beta < \alpha} {}^{\beta+} A$

Representation of Fuzzy Sets

Therefore, a fuzzy set can be represented by both their $\alpha$-cuts and strong $\alpha$-cuts

This representation of $A$ in terms of special fuzzy sets ${}_\alpha A$ which are defined in terms of $\alpha$-cuts of $A$ is usually referred to as a decomposition of $A$

Operations On Fuzzy Sets

• Functions that qualify as fuzzy intersections and fuzzy unions are usually referred to in the literature as t-norms and t-conorms, respectively.

• Since the fuzzy complement, intersection, and union are not unique operations, contrary to their crisp counterparts, different functions may be appropriate to represent these operations
  in different contexts

Fuzzy Complements

Let $A$ be a fuzzy set. Let $cA$ denote the fuzzy complement of $A$ of type $c$.

• $cA(x)$ can represent not only the degree to which $x$ belongs to $cA$ but also the degree to which $x$ does not belong to $A$

Axiomatic Skeleton of Fuzzy Complements

To produce meaningful fuzzy complements, function $c$ must satisfy at least the following two axiomatic requirements

• $\texttt{Axiom c1. } c(0) = 1, c(1) = 0$

• $\texttt{Axiom c2. } \forall a, b \in [0, 1], if a \leq b, \; then \; c(a) \geq c(b)$

Additional requirements can be added

• $\texttt{Axiom c3. } c$ is a continuous function

• $\texttt{Axiom c2. } c$ is involutive, which means $\forall a \in [0,1] \; c(c(a)) = a$

Theorem 3.1. Let a function $c : [0, 1] \rightarrow [0, 1]$ satisfy Axioms c2 and c4. Then, $c$ also satisfies Axioms cl and c3, Moreover, $c$ must be a bijective function.

Examples

• c1 - c2: Thresholding Type

Examples

• c1 - c3: Continuous

Examples

• c1 - c4 Sugeno class

Where $\lambda \in (-1, \infin)$

Fuzzy Intersections

where

Axiomatic Skeleton for Fuzzy Intersection

• $\texttt{Axiom il. } i(a, 1) = a$

• $\texttt{Axiom i2. } b \leq d \implies i (a, b) \leq i (a, d)$

• $\texttt{Axiom i3. } i (a, b) = i (b, a)$

• $\texttt{Axiom i4. } i (a, i (b, d)) = i (i (a, b), d)$

Additional Requirements

• $\texttt{Axiom i5. }i$ is a continuous function
• $\texttt{Axiom i6. }i (a, a) \leq a$
• $\texttt{Axiom i7. }a_1 < a_2$ and $b_1 < b_2 \implies i(a_1, b_1) < i(a_2, b_2)$

Theorem 3.9 The standard fuzzy intersection is the only idempotent t-norm.

Examples

• Standard Intersection: $i(a, b) = min(a,b)$
• Algebraic Product: $i(a, b) = ab$
• Bounded Difference: $i(a, b) = max(0, a+b-1)$
• Drastic Intersection:

$i_{min}(a, b) \leq max(0, a + b - 1) \leq ab \leq min(a, b)$

$i_{min} (a, b) \leq i (a, b) \leq min (a, b)$

Fuzzy Unions

where

Axiomatic Skeleton for Fuzzy Unions

• $\texttt{Axiom u1. } i(a, 0) = a$

• $\texttt{Axiom u2. } b \leq d \implies u (a, b) \leq u (a, d)$

• $\texttt{Axiom u3. } u (a, b) = u (b, a)$

• $\texttt{Axiom u4. } u (a, u (b, d)) = u (u (a, b), d)$

Additional Requirements

• $\texttt{Axiom u5. }u$ is a continuous function
• $\texttt{Axiom u6. }u (a, a) \geq a$
• $\texttt{Axiom u7. }a_1 < a_2$ and $b_1 < b_2 \implies u(a_1, b_1) < u(a_2, b_2)$

Theorem 3.14 The standard fuzzy union is the only idempotent t-conorm.

Examples

• Standard Union: $u(a, b) = max(a,b)$
• Algebraic sum: $u(a, b) = a + b - ab$
• Bounded Sum: $u(a, b) = min(1, a+b)$
• Drastic Union:

$max(a, b) \leq u(a, b) < i_{max}(a, b)$

Fuzzy Arithmatic

Fuzzy Number

To qualify as a fuzzy number, a fuzzy set $A$ on $R$ must possess at least the following
three properties:

• $A$ must be a normal fuzzy set
• $^{\alpha}A$ must be a closed interval $\forall \alpha \in (0, 1]$
• the support of $A$ should be bounded

Linguistic Variables

Liguistic variables are represented by a quintuple - $(\nu, T, X, g, m)$ where

• $\nu$ is the name of the variable
• $T$ is the set of linguistic terms forming $\nu$\s base class
• $X$ - Universe of Discourse
• $g$ is a syntactic rule for generating terms
• $m(t)$ defines fuzzy set $\forall t \in T$

Applications: Cluster Analysis

• The utility of fuzzy set theory in pattern recognition and cluster analysis was already recognized in the mid-1960s, and the literature dealing with fuzzy pattern recognition and fuzzy clustering is now quite extensive.

• This is not surprising, since most categories we
  commonly encounter and employ have vague boundaries.

Three Fundamental Problems

• Sensing Data - Representation of input data obtained by measurements on objects yet to be detected

• Feature Extraction - Extraction of characteristic features

• discrimination function - determination of decision rules

Clustering

Given a finite set of data, $X$, the problem of clustering in $X$ is to find several cluster centers that can properly characterize relevant classes of $X$.

In classical cluster analysis, these classes are required to form a partition of $X$ such that

• the degree of association is strong for data within blocks of the partition and
• weak for data in different blocks

Fuzzy c-Means Clustering Method

Let $X = \{x_1, ... x_2\}$ be the set of real data.