fuzzy_sets_fuzzy_logic_basic___Intro.ppt

Fuzzy sets
fuzz logic

1. Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Course Project Presentation
Mahdi Amiri
June 2003
Sharif University of Technology

2. Page 2 of 30 Fuzzy C-Means Clustering
Presentation OutlinePresentation Outline
Motivation and Goals
Fuzzy C-Means Clustering (FCM)
Possibilistic C-Means Clustering (PCM)
Fuzzy-Possibilistic C-Means (FPCM)
Comparison of FCM, PCM and FPCM
Conclusions and Future Works

3. Page 3 of 30 Fuzzy C-Means Clustering
Motivation and GoalsMotivation and Goals
Sample ApplicationsSample Applications
Image segmentation
–Medical imaging
•X-ray Computer Tomography (CT)
•Magnetic Resonance Imaging (MRI)
•Position Emission Tomography (PET)
Image and speech enhancement
Edge detection
Video shot change detection

4. Page 4 of 30 Fuzzy C-Means Clustering
Definition: Search for structure in data
Elements of Numerical Pattern Recognition
–Process Description
•Feature Nomination, Test Data, Design Data
–Feature Analysis
•Preprocessing, Extraction, Selection, …
–Cluster Analysis
•Labeling, Validity, …
–Classifier Design
•Classification, Estimation, Prediction, Control, …
We are here
Pattern RecognitionPattern Recognition
Motivation and GoalsMotivation and Goals

5. Page 5 of 30 Fuzzy C-Means Clustering
Fuzzy ClusteringFuzzy Clustering
Useful in Fuzzy Modeling
–Identification of the fuzzy rules needed to
describe a “black box” system, on the basis
of observed vectors of inputs and outputs
History
–FCM: Bezdek, 1981
–PCM: Krishnapuram - Keller, 1993
–FPCM: N. Pal - K. Pal - Bezdek, 1997
Motivation and GoalsMotivation and Goals
Prof. Bezdek

6. Page 6 of 30 Fuzzy C-Means Clustering
 
1 2
, , ,
n
X x x x
nis the number of data point inX
p
k
x pis the number of features in each vector
A c-partition of X, which is matrix Uc n
Set of vectors 
1 2
, , ,
p
c
 V v v v
i
vis called “cluster center”
Input, OutputInput, Output
Input: Unlabeled data set
Main Output
Common Additional Output
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

7. Page 7 of 30 Fuzzy C-Means Clustering
X
and U V
Rows of U
(Membership Functions)
188n
4c
2p
Sample IllustrationSample Illustration
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

8. Page 8 of 30 Fuzzy C-Means Clustering
2
( , )
1 1
min ( , )
c n
m
m ik ik
i k
J u D
 
 
 
 

U V
U V
(FCM), Objective Function(FCM), Objective Function
2
2
ik k i
D 
A
x vDistance
1m
Degree of
Fuzzification
1
1 ,
c
ik
i
u k

 Constraint
,
T
 
A A
x x x x Ax
A-norm
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Optimization of an “objective function” or
“performance index”

9. Page 9 of 30 Fuzzy C-Means Clustering
Zeroing the gradient of with respect to
Zeroing the gradient of with respect to
Minimizing Objective FunctionMinimizing Objective Function
1
2
1
1
, ,
mc
ik
ik
j jk
D
u ik
D



 
 
 
  
  
 
 
 

m
J
U
m
J
V
1
( )
t t
F
 
U V
1
( )
t t
G
 
V U
1 1
,
n n
m m
i ik k ik
k k
u u i
 
 
 
 
 
 v x


Note: It is the Center of Gravity
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

10. Page 10 of 30 Fuzzy C-Means Clustering
Initial Choices
–Number of clusters
–Maximum number of iterations (Typ.: 100)
–Weighting exponent (Fuzziness degree)
•m=1: crisp
•m=2: Typical
–Termination measure  1-norm
–Termination threshold (Typ. 0.01)
1c n 
T
m
0
1t t t
E

 V V
PickPick
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

11. Page 11 of 30 Fuzzy C-Means Clustering
Guess Initial Cluster Centers
Alternating Optimization (AO)
–
–REPEAT
–
–
–
–UNTIL ( or )
–
0 1,0 ,0
( , )
cp
c
 V v v
0t
1t t 
1
( )
t t
F
 
U V
1
( )
t t
G
 
V U
t T
1t t


 V V
( , ) ( , )
t t
U V U V
Guess, IterateGuess, Iterate
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

12. Page 12 of 30 Fuzzy C-Means Clustering
Sample Termination Measure PlotSample Termination Measure Plot
Final
Membership Degrees
Termination Measure Values
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
2.0m

13. Page 13 of 30 Fuzzy C-Means Clustering
0
U
1t t t
 U V U
1t t


 U U
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Process could be shifted one half cycle
–Initialization is done on
–Iterates become
–Termination criterion
The convergence theory is the same in either case
Initializing and terminating on V is advantageous
–Convenience
–Speed
–Storage
Implementation NotesImplementation Notes

14. Page 14 of 30 Fuzzy C-Means Clustering
Pros and ConsPros and Cons
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Advantages
–Unsupervised
–Always converges
Disadvantages
–Long computational time
–Sensitivity to the initial guess (speed, local minima)
–Sensitivity to noise
•One expects low (or even no) membership degree
for outliers (noisy points)

15. Page 15 of 30 Fuzzy C-Means Clustering
Optimal Number of ClustersOptimal Number of Clusters
2 2
( )
1 1
min ( ) ( )
c n
m
ik k i i
c
i k
Pc u
 
 
    
 
 x v v x
Sum of the
within fuzzy cluster fluctuations
(small value for optimal c)
Sum of the
between fuzzy cluster fluctuations
(big value for optimal c)
2
1 1
( )
c n
m
ik k i
i k
u
 
 x v
2
1 1
( )
c n
m
ik i
i k
u
 
 v x
1
1
n
k
kn

x x

Average of all feature vectors
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Performance Index

16. Page 16 of 30 Fuzzy C-Means Clustering
Optimal Cluster No. (Example)Optimal Cluster No. (Example)
Performance index for optimal clusters
(is minimum for c = 4)
c = 4
c = 2 c = 3
c = 5
Fuzzy C-Means ClusteringFuzzy C-Means Clustering

17. Page 17 of 30 Fuzzy C-Means Clustering
 is an outlier but has the same membership
degrees as
Outliers, Disadvantage of FCMOutliers, Disadvantage of FCM
6
x
6
x
12
x
1,6
0.5u
2,6
0.5u
1,12
0.5u
2,12
0.5u
1,6
0.5u
11X 12X
2,6
0.5u
FCM on FCM on
12
x
6
x
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering

18. Page 18 of 30 Fuzzy C-Means Clustering
(PCM), Objective Function(PCM), Objective Function
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
Objective function
Typicality or Possibility
–No constraint like
Cluster weights
2
( , )
1 1 1 1
min ( , ; ) (1 )
c n c n
m m
m ik ik i ik
i k i k
P t D t
   
 
   
 
  
T V
TVw w
1 2
( , , , )
T
c
w w ww 
i
w


ik
t
1
1 ,
c
ik
i
u k

 

19. Page 19 of 30 Fuzzy C-Means Clustering
Terms of Objective FunctionTerms of Objective Function
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
Unconstrained optimization of first term will
lead to the trivial solution
The second term acts as a penalty which tries to
bring typicality values towards 1.
2
1 1
c n
m
ik ik m
i k
t D J
 

1 1
(1 )
c n
m
i ik
i k
t
 
 w
0 , ,
ik
t ik 
First term
Second term

20. Page 20 of 30 Fuzzy C-Means Clustering
Minimizing Objective Function (OF)Minimizing Objective Function (OF)
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
Rows and columns of OF are independent
First order necessary conditions for
1
2
1
1
, ,
1
ik
m
ik
i
t i k
D

 
 
 
 
w
ik-th term of OF
Cluster centers (Same as FCM)
2
( , ) (1 )
ik m m
m ik ik i ik
P t D t  TV w
1 1
,
n n
m m
i ik k ik
k k
t t i
 
 
 
 
 
 v x
Typicality values

21. Page 21 of 30 Fuzzy C-Means Clustering
Alternating Optimization, AgainAlternating Optimization, Again
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
Similar to FCM-AO algorithm (Replace
equations of necessary conditions)
Terminal outputs of FCM-AO recommended as
a good way to initialize PCM-AO
–Cluster centers: Final cluster centers of FCM-AO
–Weights:
2
1
1
, 0
n
m
ik ik
k
i n
m
ik
k
u D
K K
u


 


w
Typ. K = 1
is proportional to the average
within cluster fluctuation

22. Page 22 of 30 Fuzzy C-Means Clustering
 is recognized as an outlier by PCM
Identify OutliersIdentify Outliers
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
6
x
12
x
1,12
0.5u
2,12
0.5u
1,6
0.5u
12X
2,6
0.5u
FCM on
12
x
1,12
0.07t
2,12
0.07t
1,6
0.63t
12X
2,6
0.63t
PCM on
6
x
12
x
2.0m
1 2
7.88w w 

23. Page 23 of 30 Fuzzy C-Means Clustering
Pros and ConsPros and Cons
Possibililstic C-Means ClusteringPossibililstic C-Means Clustering
Advantage
–Clustering noisy data samples
Disadvantage
–Very sensitive to good initialization
–Coincident clusters may result
•Because the columns and rows of the typicality
matrix are independent of each other
•Sometimes this could be advantageous (start with
a large value of c and get less distinct clusters)

24. Page 24 of 30 Fuzzy C-Means Clustering
IdeaIdea
 is a function of and all c centroids
 is a function of and alone
Both are important
–To classify a data point, cluster centroid has
to be closest to the data point  Membership
–For Estimating the centroids  Typicality
for alleviating the undesirable effect of
outliers
ik
u
ik
t
k
x
k
x
i
v
Fuzzy-Possibililstic C-MeansFuzzy-Possibililstic C-Means

25. Page 25 of 30 Fuzzy C-Means Clustering
(FPCM), OF and Constraints(FPCM), OF and Constraints
Fuzzy-Possibililstic C-MeansFuzzy-Possibililstic C-Means
Objective function
Constraints
–Membership
–Typicality
•Because of this constraint, typicality of a data point to a
cluster, will be normalized with respect to the distance of all
n data points from that cluster  next slide
2
,
( , , )
1 1
min ( , , ) ( )
c n
m
m ik ik ik
i k
J u t D


 
 
  
 

U T V
UTV
1
1 ,
c
ik
i
u k

 
1
1 ,
n
ik
k
t i

 

26. Page 26 of 30 Fuzzy C-Means Clustering
Minimizing OFMinimizing OF
Fuzzy-Possibililstic C-MeansFuzzy-Possibililstic C-Means
Membership values
–Same as FCM, but
resulted values may
be different
Typicality values
–Depends on all data
Cluster centers
1
2
1
1
, ,
mc
ik
ik
j jk
D
u i k
D



 
 
 
  
  
 
 
 

1 1
( ) ( ) ,
n n
m m m m
i ik ik k ik ik
k k
u t u t i
 
 
   
 
 
 v x
1
2
1
1
, ,
n
ik
ik
j ij
D
t ik
D




 
 
 
  
  
 
 
 

Typical
in the interval
[3,5]

27. Page 27 of 30 Fuzzy C-Means Clustering
FPCM on X-12FPCM on X-12
Fuzzy-Possibililstic C-MeansFuzzy-Possibililstic C-Means
6
x
12
x
1,12
0.5u
2,12
0.5u
1,6
0.5u
2,6
0.5u
U values 1,12
0.002t
2,12
0.002t
1,6
0.023t
2,6
0.023t
T values
6
x
12
x
2.0m 2.0 0.00001Initial parameters

28. Page 28 of 30 Fuzzy C-Means Clustering
IRIS Data SamplesIRIS Data Samples
Iris plants database
–4-dimensional data set containing
50 samples each of three types
of IRIS flowers
–n = 150, p = 4, c = 3
–Features
•Sepal length, sepal width,
petal length, petal width
–Classes
•Setosa, Versicolor, Virginica
Iris
setosa
Iris
versicolor
Iris
virginica
Petal
Comparison of FCM, PCM and FPCMComparison of FCM, PCM and FPCM

29. Page 29 of 30 Fuzzy C-Means Clustering
IRIS Data ClusteringIRIS Data Clustering
Comparison of FCM, PCM and FPCMComparison of FCM, PCM and FPCM
Initial parameters: [PalPB97]
Resubstitution errors based on the hardened Us and Ts
m Iter-
FCM
Iter-
PCM
Iter-
FPCM
Err-
FCM
Err-
PCM
Err-U-
FPCM
Err-T-
FPCM
1.5 1.5 26 (24)57, 8026 (13)17 (17)100, 1017 (17)19 (17)
2.0 2.0 28 (26)39, 8028 (12)16 (16)100, 1016 (16)15 (16)
1.5 3.0 26 (24)57, 5726 (13)17 (17)100, 1017 (17)16 (17)
3.0 3.0 29 (25)31, 4029 (13)15 (15)100, 1115 (15)15 (14)
5.0 2.0 37 (31)49, 3044 (16)15 (15)150, 2015 (15)12 (14)
2.0 5.0 28 (26)39, 5728 (12)16 (16)100, 916 (16)16 (16)
5.0 5.0 37 (31)49, 3037 (15)15 (15)150, 2015 (15)12 (15)

My Implementation [PalPB97] Tuned weightsAuto weights

30. Page 30 of 30 Fuzzy C-Means Clustering
Err-T-FPCM <= Err-U-FPCM <= Err-FCM
–Could be considered true in general
Mismatch
–Number of iterations required for FPCM in general
is not half of that for FCM as mentioned at
[PalPB97]; Is there any mistake in my
implementation?
Comparison of algorithms using other “noisy”
data sets
Conclusions and Future WorksConclusions and Future Works

31. Thank You
1.http://ce.sharif.edu/~m_amiri/
2. http://yashil.20m.com/
FIND OUT MORE AT...
Fuzzy C-Means ClusteringFuzzy C-Means Clustering
Course Project Presentation

32. Page 32 of 30 Fuzzy C-Means Clustering
[Bez81] J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function
Algorithms, Plenum, NY, 1981.
[BezKKP99] James C. Bezdek, James Keller, Raghu Krishnapuram and Nikhil
R. Pal, Fuzzy Models and Algorithms for Pattern Recognition and
Image Processing, Kluwer Academic Publishers, TA 1650.F89,
1999.
[KriK93] R. Krishnapuram and J. M. Keller, “A possibilistic approach to
clustering,” IEEE Transactions on Fuzzy Systems, Vol. 1, No. 2, pp.
98-110, May 1993.
[PalPB97] N. R. Pal, K. Pal and J. C. Bezdek, “A mixed c-means clustering
model,” Proceedings of the Sixth IEEE International Conference on
Fuzzy Systems, Vol. 1, pp. 11-21, Jul. 1997.
[YanRP94] Jun Yan, Michael Ryan and James Power, Using fuzzy logic
Towards intelligent systems, Prentice Hall, 1994.
ReferencesReferences

33. Page 33 of 30 Fuzzy C-Means Clustering
…
Part Title
…
…
…
…
Part TitlePart Title