Fuzzy Classification

CLASSIFICATION
• There is structure in nature
• Examples:
• I. We see directly
• Natural sphericity of rain drops and bubbles
• Elegant beauty of crystals
• Solids with rectangular, pentagonal or hexagonal cross sections
• II. Some phenomena we cannot see directly
• The elliptical shape of the magnetic field around the Earth
• III. we can see only when certain atmospheric conditions exist
• Beautiful circular appearance of a rainbow
CLASIFICATION CONTD…
• IV. Some appeared to us only after the advent of extremely
powerful electron microscope

• The helical appearance of DNA

• The cylindrical shape of some bacteria

• V. Origin of some structures we still do not know

• geometry and colorful patterns of a butterfly’s wings

• VI. Many others have been discovered through increased

understanding of physics, chemistry, and biology.

• Q: why do these patterns exist in our physical world?

CLASSIFICATIONS CONTD…

• Just as there is structure in nature, we believe that there is an underlying

structure in most of the phenomena we wish to understand
• Examples :
• Image recognition/Pattern recognition
• molecular biology applications such as protein folding and 3D molecular
structure
• oil exploration, cancer detection

• FINDING THE STRUCTURE IN DATA IS THE ESSENCE OF CLASSIFICATION

CLASSIFICATION CONTD…
• By finding structure, we are classifying the data according to
• Similar patterns
• Similar attributes
• Similar features
• Similar characteristics
• The general area is known as classification
• Classification is also termed clustering

• The most important issue in classification is deciding what

criteria to classify against
CLASSIFICATION CONTD…

• For example, suppose we want to classify people

• In describing people we will look at their height, weight, gender, religion,
education, appearance, and so on
• Many of these features are numerical quantities such as height and weight
• Other features are simply linguistic descriptors
• We might want to classify people into three size categories: small, medium and
large
• We might need only two of the features describing people: height and weight
• The criterion may be a weighted combination of height and weight
CLASSIFICATION USING EQUIVALENCE
RELATIONS
• Let us consider a crisp equivalence relation R defined over a
universe U
• R decomposes U into disjoint equivalence classes
• We denote the set of equivalence classes of U with respect to
R by U/R (The quotient set of U with respect to R)
• For any x U we denote the equivalence class of x with
respect to R by [ x ] defined as { y : ( x, y )  R or xRy}
R
• Properties of equivalence classes are:
x  [ x ]R
[ x ]R  [ y ]R  [ x]R [ y ]R  

[ x]
xU
R U
AN EXAMPLE
• Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and R be the relation defined
as xRy iff x and y leave the same remainder when divided by 3.
The relation matrix R is given by

1 0 0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 1 0 0 

0 0 1 0 0 1 0 0 1 0
 
1 0 0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 1 0 0
 
0 0 1 0 0 1 0 0 1 0
1 0 0 1 0 0 1 0 0 1
 
0 1 0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0 1 0
 
1 0 0 1 0 0 1 0 0 1 
EXAMPLE CONTD…

• R is an equivalence relation
• The equivalence classes are given by
[1]R  [4]R  [7]R  [10]R  {1, 4, 7,10}

[2]R  [5]R  [8]R  {2, 5,8}

[3]R  [6]R  [9]R  {3, 6,9}

• The properties of equivalence classes are clearly satisfied

• U/R = {{1, 4, 7, 10}, {2, 5, 8}, {3, 6 ,9}}

SECOND EXAMPLE

• Let U = {x1 , x2 , x3 , x4 , x5. }

• We define R over U by the matrix 1 1 0 0 0
1 1 0 0 1
 
0 0 1 0 0
 
0 0 0 1 0

0 1 0 0 1

( x1 , x2 )  R,( x2 , x5 )  R

• R is not an equivalence relation

( x1 , x5 )  R
• but
SECOND EXAMPLE CONTD…

• But 1 1 0 0 1
1 1 0 0 1 

R  R  0 0 1 0 0
 
0 0 0 1 0
1 1 0 0 1 

• This is an equivalence relation [ x1 ]  [ x2 ]  [ x5 ]  {x1 , x2 , x5 },

• The equivalence classes are[ x ]  {x }.
[ x3 ]  {x3 } 5 5
• and
FUZZY RELATIONS

• For all fuzzy equivalence relations their   cuts are equivalence relations
 1 0.8 0 0.1 0.2 
 0.8 1 0.4 0 0.9 
 
R   0 0.4 1 0 0 
 
 0.1 0 0 1 0.5 
0.2 0.9 0 0.5 1 
• The above relation is reflexive and symmetric but not transitive as
but  R ( x1 , x2 )  0.8,  R ( x2 , x5 )  0.9
 R ( x1 , x5 )  0.2  min{ R ( x1 , x2 ), R ( x2 , x5 )}
FUZZY RELATIONS CONTD…

• The composition of R with itself 4 times gives us the fuzzy equivalence relation

1 0.8 0.4 0.5 0.8

0.8 1 0.4 0.5 0.9 

R 4  0.4 0.4 1 0.4 0.4 
 
0.5 0.5 0.4 1 0.5
0.8 0.9 0.4 0.5 1 
FUZZY RELATIONS CONTD…

• Taking the different λ-cuts at different levels we get

1 0
1 0
 1 
 1  1
   
4
4
R1   1  R0.9  1 0
   
1  1 0 
 
 0 1  0 1 0 0 1 

•
FUZZY RELATIONS CONTD…

1 1 1 1 1 1 1
1 1  1
 1   1 1 1 
4
R0.8  1 0 4
R0.5  1 0
   
 1 0   1 1
1 1 0 0 1  1 1 0 1 1 

1 1 1 1 1
1 1 1 1 1

4
R0.4  1 1 1 1 1
 
1 1 1 1 1
1 1 1 1 1
FUZZY RELATIONS CONTD…

• Classification of five data points according to λ-cut level are

  cut level Classification

1 {x1},{ x2 },{x3},{ x4 },{ x5}
0.9 {x1},{x2 , x5},{ x3},{ x4 }
0.8 {x1 , x2 , x5 },{ x3 },{ x4 }
0.5 {x1 , x2 , x5 , x4 },{x3 }
0.4 {x1 , x2 , x3 , x5 , x4 }
CLUSTER ANALYSIS
• Clustering refers to identifying c subclasses, called clusters in a
data universe X
• comprising of n data samples
• partitioning X into the c clusters (2 ≤ c < n)
• c = 1 denotes rejection of the hypothesis that there are
clusters in the data
• c = n constitutes the trivial case where each sample is in a
“cluster” by itself
• Two important issues to consider in this regard are:
• How to measure the similarity between pairs of observations
• How to evaluate the partitions once they are formed
CLUSTER ANALYSIS CONTD…
• One of the simplest similarity measures is distance between
pairs of feature vectors in the feature space
• If one can determine a suitable distance measure and
compute the distance between all pairs of observations, then
one may expect that the distance between points in the same
cluster will be considerably less than the distance between
points in different clusters
• The clustering method described here defines “optimum”
partitions through a global criterion function that measures
the extent to which candidate partitions optimize a weighted
sum of squared errors between data points and cluster
centers in feature space
CLUSTER VALIDITY

• In many cases, the number c of clusters in the data is known

• In other cases, however, it may be reasonable to expect cluster substructure at
more than one value of c
• In this situation it is necessary to identify the value of c that gives the most
plausible number of clusters in the data for the analysis at hand
• This problem is known as cluster validity
• If the data used are labeled, there is a unique and absolute measure of cluster
validity: the c that is given
• For unlabeled data, no absolute measure of clustering validity exists
HARD C-MEANS ALGORITHM

• We define a sample set of n data samples that we wish to classify: X =

{x1 , x2 , x3 , . . . , xn }.
• Each data sample xi is defined by m features, that is,

xi  {xi1 , xi 2 , xi 3 , . . . , xim },

• In a geometric sense, each is a point in m-dimensional feature space, and the

universe of the data sample Xxiis a point set with n elements in the sample space
HARD C-MEANS ALGORITHM CONTD…

• Bezdek (1981) suggested using an objective function approach for clustering the
data into hyper spherical clusters

• The objective function is developed so as to do two things simultaneously:

• First, minimize the Euclidean distance between each data point in a cluster and
its cluster center (a calculated point)

• Second, maximize the Euclidean distance between cluster centers

HARD C-MEANS ALGORITHM CONTD…

• HCM is used to classify data in a crisp sense

• By this we mean that each data point will be assigned to one, and only one, data
cluster
• In this sense these clusters are also called partitions – that is, partitions of the
data
• Define a family of sets { i = 1, 2, . . . , c} as a hard c-partition of X, where the
following set-theoretic forms
Ai , apply to the partition:
• (i) c (ii) (iii)
Ai  X Ai  Aj   , i  j   Ai  X
i 1
EQUIVALENT CONDITIONS USING
CHARACTERISTIC FUNCTIONS
• For all k,
• (i)  c  ( x )  1
i 1 Ai k

• (ii)
 Ai ( xk )   Aj ( xk )  0

• (iii) n
0    Ai ( xk )  n
k 1

• Equations (i) and (ii) explain that any sample can only and
definitely belong to one of the c classes. xk
• Equation (iii) implies that no class is empty and no class is a
whole set X (i.e., the universe).
PARTITION SPACE

• For simplicity in notation, our membership assignment of the jth data point in the
ith cluster, or class, is defined to be
 ij   Ai ( x j )
• Now define a matrix U comprising elements  (i = 1, 2, . . . , c; j = 1, 2, . . . , n);
hence, U is a matrix with c rows and n columns. ij
• Then, we define a hard c-partition space for X as the following matrix set:

c n
M c  {U |  ij  {0,1},   ik  1, 0   ik  n}
i 1 k 1
CARDINALITY OF THE SOLUTION SPACE

 c c c i n 
M  (1 / c!)     ( 1) .i 
 i 1  i 
C

• When n = 5 and c = 2 then  M C  15
• An interesting question now arises:
• Of all the possible c-partitions for n data samples, how can we
select the most reasonable c-partition for the partition space
Mc
• The answer to this question is provided by the objective
function (or classification criteria) to be used to classify or
cluster the data
OBJECTIVE FUNCTION FOR HCM

• It is known as a within-class sum of squared errors approach using a Euclidean

norm to characterize distance
• This is denoted J(U, v), where U is the partition matrix, and the parameter v is a
vector of cluster centers
n c
J (U , v)    ik .(dik ) 2
k 1 i 1
• Here is the Euclidean distance measure (in m-dimensional feature space, )
between
dik the data sample and Rm
th
• cluster center k xk as follows
, which is given i th
ci
1/ 2
 m
2
dik  d ( xk  vi )    ( xkj  vij ) 
 j 1 
THE CLUSTER CENTRES

• Since each data sample requires m coordinates to describe its location in R m -

space, each cluster center also requires m coordinates to describe its location in
this same space

• Therefore, the th cluster center is a vector of length m,

i
, where the th coordinate is given by
vi  {vi1 , vi 2 ,...vim } j vij
n

 ik .xkj
vij  k 1
n

 k 1
ik
PROBLEMS IN FINDING THE OPTIMAL SOLUTION

• Finding the optimum partition matrix, U∗, is exceedingly difficult for practical
problems because Mc becomes very large for even modest-sized problems
• Example:
• For the case where n = 25 and c = 10, the cardinality approaches an extremely
large number, that is,
M c  1018
• ALETRNATE APPROACH:
• Fortunately, very useful and effective alternative search algorithms have been
devised (Bezdek, 1981)
DESCRIPTION OF THE ALGORITHM

• One such search algorithm is known as iterative optimization

• This method is like many other iterative methods in that we

start with an initial guess at the U matrix

• From this assumed matrix (input values for the number of

classes) and iteration tolerance (the accuracy we demand in
the solution), we calculate the centers of the clusters (classes)
DESCRIPTION OF THE ALGORITHM CONTD…

• From these cluster or class centers, we recalculate the membership values that
each data point has in the cluster

• We compare these values with the assumed values and continue this process
until the changes from cycle to cycle are within our prescribed tolerance level
THE HARD C-MEANS ALGORITHM
• STEP 1: Fix c (2 ≤ c < n) and initialize the U matrix U (0)  M c
• STEP 2:For r = 0, 1, 2, . . . . do
• Calculate the c center vectors vi( r ), i =1, 2,…with U ( r )
• STEP 3: Calculate the updated characteristic functions (for all i,
k) using the formula
1, if dik( r )  min{d (jkr ) }, for all j  1, 2,...c
 ik( r 1) 
0, otherwise

• STEP 4: If U ( r 1)  U ( r )   (the pre-assigned value then STOP

• Else r = r+1 and go to STEP 2 (The . norm here is the
Euclidean norm)
ILLUSTRATIVE EXAMPLE

• In a chemical engineering process involving an automobile’s

catalytic converter (which converts carbon monoxide to carbon
dioxide), we have a relationship between the conversion
efficiency of the catalytic converter and the inverse of the
temperature of the catalyst

• Points of high conversion efficiency and high temperature are

indicators of a nonpolluting system (class c1)
ILLUSTRATIVE EXAMPLE CONTD…

• Points of low conversion efficiency and low temperature are indicative of a

polluting system(class c2)

• Suppose we measure the conversion efficiency and temperature (T ) of four

different catalytic converters and attempt to characterize them as polluting or
nonpolluting
THE DATA TABLE

• The measurement results in

Convertors Conversion efficiency Temperature

x1 1 3
x2 1.5 3.2
x3 1.3 2.8
x4 3 1

1  2  1 4  2 0 4 1
MC    (1) (1)    (1) (2)   [2  16]  7
2!  1   2  2
EXECUTION OF THE HCM ALGORITHM

• Let the initial guess of the U matrix be

1 0 0 0 
U (0)   
0 1 1 1 
• In this case m = 2 and c = 2
• Therefore,
• where vi  {vi1 , vi 2 },i  1, 2
• for c = 1 (which is class 1), v1  {v11 , v12 }
• for c = 2 (which is class 2), v  {v , v }
2 21 22
EXECUTION OF THE HCM ALGORITHM CONTD…

• Using the expression for for c = 1, andvij j = 1 and 2, respectively

11.x1 j  12 .x2 j  13 .x3 j  14 .x4 j x1 j

v1 j  
11  12  13  14 1
• So, the centre
v11  1 and v12  3 v1  (1,3).
 21.x1 j   22 .x2 j   23 .x3 j   24 .x4 j x2 j  x3 j  x4 j
v2 j  
• So,
 21   22  .23Hence
  24 3
v21  1.93 and v22  2.33 v2  (1.93, 2.33).
NEXT STEP

• Now, we compute the distances of the sample vectors

• x1 , x2 , x3 , x4from the two centres v and v using the formula
1 2
1/ 2
m 2
dik    ( xkj  vij ) 
 j 1 
• For cluster 1, the 4 distances are
• For cluster 2, the 4 distances are d11  0.0, d12  0.54, d13  0.36, d14  2.83

• d 21 functions
Next we find the updated characteristic 1.14, d22  0.97,
ford23all
 0.78,
i andd24 k1.70
• For i= 1, we compare with min{ }
d1k d1k , d 2 k
NEXT STEP CONTD…

• Taking k = 1, 2, 3, 4, we get
d11  0.00, min( d11 , d 21 )  0.00  d11. So, 11  1
d12  0.54, min(d12 , d 22 )  0.54  d12 . So, 12  1
d13  0.36, min( d13 , d 23 )  0.36  d13 . So, 13  1
d14  2.83, min(d14 , d 24 )  1.70  d14 . So, 14  0

• Similarly, we get d 21  0, d 22  0, d 23  0 and d24  1. So,

(1) 1 1 1 0
U 
0 0 0 1

• As U (0)  U (1) the procedure is to be repeated.
NEXT STEP
11.x11  12 .x21  13 .x31  14 .x41
v11 
• For c = 1, 11  12  13  14
1.(1)  1(1.5)  1(1.3)  0.(3)
 3.8
• 111 0 =  1.26
3
11.x12  12 .x22  13 .x32  14 .x42
v12 
11  12  13  14

• =3
• So, v1  (v11 , v12 )  (1.26, 3).
NEXT STEP CONTD…

• For c = 2, we get  21.x11   22 .x21   23 .x31   24 .x41

v21  3
 21   22   23   24
 21.x12   22 .x22   23 .x32   24 .x42
v22  1
 21   22   23   24

v2  (3,1).
• So,
• Again we find the distances of the sample points from these new centres.
THE NEW DISTANCES

d11  (1  1.26)2  (3  3) 2  0.26

• Similarly, d12  0.31, d13  0.20 and d14  2.65

• Also, d 21  2.83, d 22  2.66, d 23  2.47 and d 24  0.0

• Now min{d11 , d 21}  0.26  d11 .So, 11  1

min{d12 , d 22 }  0.31  d12 .So, 12  1
min{d13 , d 23 }  0.20  d13 .So, 13  1
min{d14 , d 24 }  0.00  d14 .So, 14  0
THE NEW MATRIX

• Similarly,  21  0,  22  0,  23  0,  24  1.

(2) 1 1 1 0
• Hence U 
0 0 0 1 

• As U (2)  U (1) the process ends.

• The two clusters are {x1 , x2 , x3 } and {x4 }.

FUZZY C-MEANS

• To develop these methods in classification, we define a family of fuzzy sets { Ai, i =

1, 2, . . . , c} as a fuzzy c-partition on a universe of data points X

• As fuzzy sets allow for degrees of membership, we can extend the crisp
classification idea into a fuzzy classification notion

• Then, we can assign membership to the various data points in each fuzzy set
(fuzzy class, fuzzy cluster).

• Hence, a single point can have partial membership in more than one class
FUZZY C-MEANS CONTD…
• We denote the membership value of the k th data point in the
i th class by ik   Ai ( xk )  [0,1]
• The restriction (as with crisp classification) that the sum of all
membership values for a single data point in all of the classes
has to be unity c
• For k = 1, 2, …n  ik  1
i 1

• As before in crisp classification, there can be no empty classes

and there can be no class that contains all the data points
n
0   ik  n
k 1
RESTRICTIONS ON MEMBERSHIP FUNCTIONS
CONTD…
• As each data point can have partial membership in more than one class, the
clusters are no more disjoint, that is
min{ik ,  jk }  0( may be)

• The other two

c conditions however remains true, that is
 ik  1, k  1, 2,...n
i 1

• and n
0   ik  n
k 1
RESTRICTIONS ON MEMBERSHIP FUNCTIONS
CONTD…
• In the crisp case, when c = 2, the classification problem reduced to that of the
excluded middle axioms for crisp classification
• Since we now allow partial membership, the case of c = 2 does not follow the
restrictions of the excluded middle axioms, that is, for two classes Ai and Ak

Ai  Ak  
  Ai  X
• We can now define a family of fuzzy partition matrices M fC , for the classification
involving c classes and n data points
FUZZY PARTITION SPACE

c n
M fC  {U | ik  [0,1];  ik  1;0   ik  n}
i 1 k 1

• AnyU  M fCis a fuzzy c-partition, and it follows from the overlapping character of
the classes and the infinite number of membership values possible for describing
class membership that the cardinality of M fC is also infinity, that is
.
M f  
C
FUZZY C-MEANS ALGORITHM
• STEP 1: Fix c ( 2  c  n ) and select a value m’
Initialize the partition matrixU (0)
For r = 0, 1, 2,…. Do
(r )
• STEP 2: Calculate the ‘c’ centresvi , i  1, 2,...c using the formula
n
( ikm ' .xkj )
vij  k 1
n

 ik
 m'

k 1 th
• STEP 3:Update the partition matrix for ther U (r )
step to
U ( r 1) = (ik( r 1) ), where
FUZZY C-MEANS ALGORITHM CONTD…

• Taking I k  {i | 2  c  n; d ik( r )  0}

2/( m ' 1) 1

 c  d (r)  
ik( r 1)     ik( r )   , if I k   ,
 j 1  d jk  
 
 0, where i  I 'k  {1, 2,...c}  I k

U ( r 1)  U ( r )   L
• STEP 4: If STOP
• Else go to STEP 2.
ILLUSTRATIVE EXAMPLE
• We consider the same chemical engineering example
• Here we have n = 4, c = 2
• Let us take the weighing factor m’=2 and  L= 0.01
• We start with the in initial partition as
(0) 1 1 1 0    1k ' s 
U     ' s 
 0 0 0 1  2k 
• We compute the initial centres using the formula
n

 ( ik ) 2 . xkj
vij  k 1
n

 (
k 1
ik )2
ILLUSTRATIVE EXAMPLE CONTD…
v1 j  ( x1 j  x2 j  x3 j ) / 3
• For c = 1, . So,
v11  (1  1.5  1.3) / 3  1.26
v12  (3  3.2  2.8) / 3  3

v2 j  ( x4 j ) / 1
• For c = 2, . So,
v21  3
v22  1

• Hence the initial centres are

(1.26, 3) and (3, 1)
ILLUSTARTIVE EXAMPLE CONTD…

• Next we find the distances of the items from the 2 centres

d11  0.26, d12  0.31, d13  0.20 and d14  2.65
d 21  2.82, d 22  2.66, d 23  2.47 and d 24  0

• Next we compute the new membership values using the formula

2 1
 c  d ( r 1)  
ik( r 1)     ik( r 1)  
 j 1  d jk  
 
ILLUSTRATIVE EXAMPLE CONTD…

11(1)  0.991, 12(1)  0.986, 13(1)  0.993, 14(1)  0.0

21(1)  0.009,  22(1)  0.014,  23(1)  0.007,  24(1)  1.0
• So, (1)  0.991 0.986 0.998 0
U 
0.009 0.014 0.007 1 

U (1)  U (0)  max{| ik(1)  ik(0) |}  0.14   L  0.01

i ,k

• We proceed for one more iteration

ILLUSTRATIVE EXAMPLE CONTD…
(0.98).x1 j  (0.97).x2 j  (0.99).x3 j
• We have v1 j 
0.98  0.97  0.99

• So, (0.98).(1)  (0.97).(1.5)  (0.99).(1.3)

v11   1.26
0.98  0.97  0.99

• And (0.98).(3)  (0.97).(3.2)  (0.99).(2.8)

v12   3.0
0.98  0.97  0.99

v1(1)  (1.26, 3)
• So,
ILLUSTRATIVE EXAMPLE CONTD…

• Again (0.009) 2 .x1 j  (0.014)2 .x2 j  (0.007)2 .x3 j  (1)2 .x4 j

v2 j 
(0.009) 2  (0.014)2  (0.007)2  (1)2

• So, v21  3.0 and v22  1.0

v2(1)  (3.0,1.0)
• Hence,
So, the centres are identical with those in the previous step
Hence there will be no change in the other computations, that is in the d-values
and the membership values. (2)
U  U (1)
So, we will get
ILLUSTARTIVE EXAMPLE CONTD…
max{| ik(2)  ik(1) |}  0   L  0.01
• Hence the condition i ,k is satisfied
• The final partition is
C1  {(1,3), (1.3, 2.8), (1.5,3.2)} and C2  {(3,1)}

• Here, it is to note that the data elements are given by their membership values