Classification
Technique that associates samples to
classes previously known.
 May be Crisp or Fuzzy
 Supervised

Classification
 MLP  trained
Adriano Joaquim de O Cruz ©2002
NCE/UFRJ
[email protected]

Non supervised
 K-NN e fuzzy K-NN  not trained
*@2001 Adriano Cruz
*NCE e IM - UFRJ
K-NN and Fuzzy K-NN

Classification Methods

Classes identified by patterns

Classifies by the k nearest neighbours

Previous knowledge about the problem
classes

It is not restricted to a specific distribution of
the samples
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification
Classification 3
Crisp K-NN
Classification 2
Crisp K-NN





Crisp K-NN
Supervised clustering method (Classification
method).
Classes are defined before hand.
Classes are characterized by sets of elements.
The number of elements may differ among
classes.
The main idea is to associate the sample to the
class containing more neighbours.
Class 1
*NCE e IM - UFRJ
Classification 5
Crisp K-NN
Class 3
w5
w9
w14
w8
Class 4
w11
w 12
s
w7
w6
Class 5
3 nearest neighbours, and sample s is closest to
pattern w6 on class 5.
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 6
Crisp K-NN
Consider W={w
={w1, w2, ..., wt} a set of t labelled
data.
 Each object w is defined by l characteristics
i
wi=(w
=(wi1, wi2, ..., wil).

Input of y unclassified elements.
k the number of closest neighbours of y.
 E the set of k nearest neighbours (NN).


*@2001 Adriano Cruz
w4
w13
w10

*@2001 Adriano Cruz
Class 2
w2 w3
w1
*NCE e IM - UFRJ
Classification 7
 Let
t be the number of elements that identify
the classes.
 Let c be the number of classes.
 Let W be the set that contain the t elements
 Each cluster is represented by a subset of
elements from W.
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 8
Crisp K-NN algorithm
Crisp K-NN algorithm cont.
set set k
{Calculating the NN}
for t
for i = 1 to
= 1 to Calculate distance from y to xi
if if i<=k then add then add xi to E
else else if if xi is closer to y than any previous NN
then delete the farthest neighbour then delete the farthest neighbour and include xi in the set E
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 9
Determine the majority class represented in the set E and include y in this class.
if there is a draw, if there is a draw, then calculate the sum of distances from then calculate the sum of distances from y to all neighbours in each class in the draw
if the sums are different
if the sums are different
then add then add xi to class with smallest sum
else add else add xi to class where last minimum was found
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 10
Fuzzy K-NN
Classification
Fuzzy K-NN
The basis of the algorithm is to assign
membership as a function of the object’s
distance from its K-nearest neighbours and
the memberships in the possible classes.
 J. Keller, M. Gray, J. Givens. A Fuzzy KNearest Neighbor Algorithm. IEEE
Transactions on Systems, Man and
Cybernectics, vol smc-15, no 4, July August
1985

*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 12
Fuzzy K-NN
Fuzzy K-NN
Classe 2
Classe 1
w2
w4
w 13
w1
w10
w11
Classe 4
*@2001 Adriano Cruz
w8
w7
w12
w14
Consider W={w
={w1, w2, ..., wt} a set of t labelled data.

Each object wi is defined by l characteristics wi=(w
=(wi1,
wi2, ..., wil).

Input of y unclassified elements.
k the number of closest neighbours of y.
E the set of k nearest neighbours (NN).
i(y) is the membership of y in the class i
ij is the membership in the ith
ith class of the jth vector
of the labelled set (labelled wj in class i) .



w6

Classe 5
*NCE e IM - UFRJ
Classification 13
Fuzzy K-NN

*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 14
Fuzzy K-NN algorithm
 Let
t be the number of elements that identify
the classes.
 Let c be the number of classes.
 Let W be the set that contain the t elements
 Each cluster is represented by a subset of
elements from W .
*@2001 Adriano Cruz

w5
w9
w3
Classe 3
*NCE e IM - UFRJ
Classification 15
set set k
{Calculating the NN}
for t
for i = 1 to
= 1 to Calculate distance from y to xi
if if i<=k then add then add xi to E
else else if if xi is closer to y than any previous NN
then delete the farthest neighbour then delete the farthest neighbour and include xi in the set E
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 16
Computing  ij(y) Fuzzy K-NN algorithm
Calculate  i(y) using

for c // number of classes
for i = 1 to
= 1 to k
∑ μij
μi ( y )=
j=1
k
∑
j=1
*@2001 Adriano Cruz
(
(
1
∥y −x j∥2/( m−1 )
1
∥y−x j∥2/( m−1)
*NCE e IM - UFRJ

)


)
Classification 17
 ij(y) can be assigned class membership in
several ways.
They can be given complete membership in their
known class and non membership in all other.
Assign membership based on distance from their
class mean.
Assign membership based on the distance from
labelled samples of their own class and those
from other classes.
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 18
ICC-KNN System
Classification
ICC-KNN System

Non-Parametric Statistical Pattern
Recognition System

Associates FCM, fuzzy KNN and ICC

Evaluates data disposed on several class
formats
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 20
ICC-KNN System


ICC-KNN First Module
Divided in two modules
First module (training)

 chooses the best patterns to use with K-NN
 chooses the best fuzzy constant and best
number of neighbours (K)

 Finds structure on data sample
 Divided into two phases

• FCM – Applied to each class using many numbers
of categories
• ICC – Finds the best number of categories to
represent each class
 uses fuzzy k-nn to classify
*NCE e IM - UFRJ
Classification 21
ICC-KNN First Phase

 Patterns for K-NN which are the centres of the
chosen run of FCM
 Number of centres which are all the centres of
the number of categories resulting after
applying ICC to all FCM runs
*NCE e IM - UFRJ
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 22
ICC-KNN Second Phase
Results of applying FCM and ICC
*@2001 Adriano Cruz
First phase of training
 Finds the best patterns for fuzzy K-NN
Second module (classification)
*@2001 Adriano Cruz
Classification Module
Classification 23

Second phase of training

Evaluates the best fuzzy constant and the
best number of neighbours so to achieve
best performance on the K-NN
 tests several m and k values
 finds m and k for the maximum rate of crisp hits
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 24
ICC-KNN

ICC-KNN block diagram
Pattern Recognition Module
 Distributes each data to its class

Classification Module
Uses the chosen patterns, m and k to
classify data
Pattern
Recognition
Module
U1cmin
Class 1
FCM
ICC
w1
U1cmáx
W, Uw
UScmin
Class s
FCM
ICC
Fuzzy
K-NN
m k
Fuzzy
K-NN
W Uw
ws
UScmáx
Not
classified Data
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 25
*@2001 Adriano Cruz
ICC-KNN
*NCE e IM - UFRJ
Classification 26
ICC-KNN algorithm

Let R={
R={r1,r2,...,rn} be the set of samples.

Classification Module

Each sample ri belongs to one of s known classes.

First phase of training


Let Uic be the inclusion matrix for the class i with c
categories.
Let Vic be the centre matrix for the class i with c
categories.
Let wi be equal to the best Vic of each class

Step 1. Set m
Step 2. Set cmin and cmáx
Step 3. For each s known class
Generate the set Rs with the points from R belonging to the class s
For each category c in the interval [ cmin , cmáx]
cmáx]
Run FCM for c and the set Rs generating Usc and Vsc
Calculate ICC for Rs e Usc
End
Define the patterns ws of class s as the matrix Vsc that
maximizes ICC



Let W be the set of sets of centres wi
*@2001 Adriano Cruz
*NCE e IM - UFRJ


Classification 27
Step 4. Generate the set W = {w1, ..., ws}
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 28
ICC-KNN algorithm

Second phase of Training

Step 5. Set mmin e mmáx
Step 6. Set kmin e kmáx
For each m from [mmin , mmáx]
For each k from [kmin , kmáx]
Run fuzzy K-NN for the patterns from the set W
generating Umk
Calculate the number of crisp hits for Umk



ICC-KNN algorithm

Pattern Recognition Module

Step 9. Apply fuzzy K-NN using patterns form the set W and the chosen
parameters m and k to the data to be classified.
Step 7. Choose m and k that yields the best crips hit figures
Step 8. if there is a draw
If the k’s are different
Choose the smaller k
else
Choose the smaller m
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 29
ICC-KNN results
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 30
ICC-NN results
 2000
samples, 4 classes, 500 samples
in each class
 Classes
1 and 4 – concave classes
 Classes
2 and 3 – convex classes,
elliptic format
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 31
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 32
ICC-KNN results
ICC-KNN results
First phase of training
Second phase of Training

FCM applied to each class

Running fuzzy K-NN
 Training data 80%  400 samples from each
class
 c = 3..7 and m = 1,25





ICC applied to results
Patterns from first phase
Random patterns
k = 3 a 7 neighbours
m = {1,1; 1,25; 1,5; 2}
 Classes 1 and 4  4 categories
 Classes 2 and 3  3 categories
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 33
ICC-KNN results
*NCE e IM - UFRJ
*@2001 Adriano Cruz
Classification 34
ICC-KNN results
Dados de Treinamento
Classes
Conclusão:K-NN é mais estável em relação ao valor de m para os padrões da PFT
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 35





Padrões da PFT
Padrões Aleatórios
1
2
3
4
1
2
3
4
1
388
10
0
2
213
66
0
121
2
14
379
0
7
19
380
0
1
3
0
0
376
24
3
0
324
73
4
0
1
2
397
4
46
1
349
Training data
Lines  classes
Columns  classification
m = 1,5 e k = 3  96,25%
m = 1,1 e k = 3  79,13% (random patterns)
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 36
ICC-KNN results
ICC-KNN x Others

Dados de Testes
Classes
Padrões da PFT
Padrões Aleatórios

1
2
3
4
1
2
3
4
1
97
2
0
1
53
27
0
20
2
4
93
0
3
4
96
0
0
3
0
0
90
10
0
0
82
18
4
0
0
1
99
0
15
0
85
FCM, FKCN, GG e GK
Fase de Treinamento (FTr)
 Dados de treinamento
 c = 4 e m = {1,1; 1,25; 1,5; 2}
 Associar as categorias às classes
• Critério do somatório dos graus de inclusão




o Cálculo do somatório dos graus de inclusão dos pontos de
cada classe em cada categoria
o Uma classe pode ser representada por mais de uma
categoria
Test data
Lines  classes
Columns  classification
Pad. PFT – 94,75% Pad. Aleat – 79%
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 37
ICC-KNN x Others

Fase de Teste
ICC-KNN
Classe representada por mais de 1 categoria
 Grau de inclusão = soma dos graus de inclusão dos
pontos nas categorias que representam a classe
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 38
ICC-KNN x Others
 Dados de Teste
 Inicialização dos métodos com os centros da FTr
 Calcula o grau de inclusão dos pontos em cada
categoria

*NCE e IM - UFRJ
*@2001 Adriano Cruz
Classification 39
FCM
FKCN
GG
GK
66%
66%
69%
84%
95,75%
83%
70,75%
70,75%
69%
89,5%
36,5s
23,11s
2,91s
2,59s
22,66s
18,14s
94,75%
N
T




KNN A.
79%
R
GK para m = 2  84%
FCM e FKCN  66% para m = 1,1 e m = 1,25
GG-FCM  69% para m = 1,1 e 1,25
GG Aleatório  57,75% para m = 1,1 e 25% para m =
1,5
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 40
GK
GK
GK
Classes
1
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 41
2
3
4
1
77
6
0
17
2
6
94
0
0
3
0
0
97
3
4
0
0
32
68
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 42
KNN+Fuzzy C-Means algorithm
Classification



KNN+Fuzzy Cmeans System

The idea is an two-layer clustering algorithm
First an unsupervised tracking of cluster centres is
made using K-NN rules
The second layer involves one iteration of the
fuzzy c-means to compute the membership
degrees and the new fuzzy centres.
Ref. N. Zahit et all, Fuzzy Sets and Systems 120
(2001) 239-247
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 44
First Layer (K-NN)
KNN-1FCMA settings

Let X={x
={x1,…,xn} be a set of n unlabelled objects.

Let X={x
={x1,…,xn} be a set of n unlabelled objects.

c is the number of clusters.
The first layer consists of partitioning X into c cells
using the fist part of K-NN.
Each cell i is (1<=i
(1<=i<=c
<=c) represented as Ei (yi, K-NN
of yi, Gi)

Fix c the number of clusters.
Choose m>1 (nebulisation factor).
Set k = Integer(n
Integer(n/c –1).
Let I={1,2,…,
n} be the set of all indexes of X.
I={1,2,…,n






Gi is the center of cell Ei and defined as
Gi =
*@2001 Adriano Cruz
∑
x k ∈Ei
xk / k + 1
*NCE e IM - UFRJ
Classification 45
KNN-1FCMA algorithm step 1
Calculate Calculate G0
for c
for i = 1 to
= 1 to Search in I for the index of the farthest object yi from Gi­1
For j = 1 to n
Calculate distance from yi to xj
if j <= k
then add then add xj to Ei
else else if if xi is closer to y than any previous NN
then delete the farthest neighbour then delete the farthest neighbour and include x in the set Ei Classification 47
*NCE e iIM - UFRJ
*@2001 Adriano Cruz
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 46
KNN-1FCMA algorithm cont.
Include yi in the set Ei .
Calculate Gi.
Delete yi index and the K­NN indexes of yi from I.
if if I  
then for each remaining object then for each remaining object x determine the minimum distance to any centre Gi of Ei.
classify x to the nearest centre.
update all centres.
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 48
KNN-1FCMA algorithm step2

Compute the matrix U according to c
μik =

Results KNN-1FCMA
2 −1
m−1
(∑ ( ) )
l=1
d ik
d lk
Calculate all fuzzy centres using
n
∑ ( μie )m⋅x ej
v ij=
e=1
n
∑ ( μ ie )m
e =1
*@2001 Adriano Cruz
*NCE e IM - UFRJ
Classification 49
Data
Elem
c
FCMA
KNN-1FCMA
FCMA
S1
20
2
0
0
11
S2
60
3
1
0
8
S3
80
4
2
0
10
S4
120
6
13
13
19
IRIS23
150
2
14
13
10
IRIS
100
3
16
17
12
*@2001 Adriano Cruz
Misclassification
rate
Number of
Iterations avg
*NCE e IM - UFRJ
Classification 50