c3.pdf
(
71 KB
)
Pobierz
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
wiczenia 3
Klasyfikacja metod¡ k-NN (k-Nearest Neighbours)
1. Generujemy system decyzyjny testowy i treningowy za pomoc¡ programu
ds generatorTT.exe.
2. Otrzymany system testowy klasyfikujemy metod¡ 2-NN (w konceptach decy-
zyjnych) za pomoc¡ systemu treningowego stosuj¡c metryki,
a) Euklidesa (szczególny przypadek metryki Minkowskiego z pot¦g¡ 2)
b) Canberra
c) Czebyszewa
d) Manhattan
e) Bezwzgl¦dny współczynnik korelacji Pearsona
3. Tworzymy Confusion Matrix (na wzór RSESowej tabeli wyników klasyfikacji)
dla zbadanych metryk, zawieraj¡ce informacje o przeprowadzonej klasyfikacji.
4. Na koniec tworzymy ranking wyników, wypisuj¡c wyniki od metryki daj¡cej
najlepsze rezultaty do metryki najmniej skutecznej.
Preferowan¡ form¡ rozwi¡zania jest implementacja w dowolnym j¦zyku pro-
gramowania.
Podstawowa teoria do ¢wiczenia
•
Dla danego systemu testowy (
X,A,c
) i treningowego (
Y,A,c
), gdzie
X,Y
to od-
powiednio uniwersum obiektów testowych i treningowych,
A
= (
a
1
,a
2
,...,a
n
) jest
zbiorem atrybutów warunkowych,
c
2
D
=
{
c
1
,c
2
,...,c
m
}
jest atrybutem decyzyj-
nym.
Dla obiektów
x
2
X,y
2
Y
postaci,
x
=
a
1
(
x
)
a
2
(
x
)
...a
n
(
x
)
c
(
x
)
y
=
a
1
(
y
)
a
2
(
y
)
...a
n
(
y
)
c
(
y
)
zdefiniujmy podstawowe metryki,
Metryka Euklidesa
jest definiowana nast¦puj¡co,
q
d
(
x,y
) =
(
a
1
(
x
)
−
a
1
(
y
))
2
+ (
a
2
(
x
)
−
a
2
(
y
))
2
+
...
+ (
a
n
(
x
)
−
a
n
(
y
))
2
czyli zapisuj¡c ogólnie:
v
u
u
t
n
X
d
(
x,y
) =
(
a
i
(
x
)
−
a
i
(
y
))
2
i
=1
Metryka Canberra
jest postaci,
n
X
|
a
i
(
x
)
−
a
i
(
y
)
a
i
(
x
) +
a
i
(
y
)
|
Metryka Czebyszewa
okre±lana jest wzorem,
d
(
x,y
) =
i
=1
d
(
x,y
) =
max
(
|
a
i
(
x
)
−
a
i
(
y
)
|
)
,dlai
= 1
,
2
,...,n
Metryka Manhattan
przedstawia si¦ nast¦puj¡co,
n
X
d
(
x,y
) =
|
a
i
(
x
)
−
a
i
(
y
)
|
i
=1
Bezwzgl¦dny współczynnik korelacji Pearsona
mo»e by¢ u»ywany w poni»szy
sposób,
d
(
x,y
) = 1
−|
r
x,y
|
n
X
1
n
(
a
i
(
x
)
−
x
P
n
i
=1
(
a
i
(
x
)
−
x
)
2
)(
a
i
(
y
)
−
y
r
x,y
=
P
n
i
=1
(
a
i
(
y
)
−
y
)
2
)
q
1
n
q
1
n
i
=1
n
X
n
X
1
n
1
n
x
=
a
i
(
x
)
,y
=
a
i
(
y
)
i
=1
i
=1
Procedura algorytmu k-NN w konceptach decyzyjnych
•
Wczytujemy system testowy (
X,A,c
) i treningowy (
Y,A,c
), gdzie
X,Y
to od-
powiednio uniwersum obiektów testowych i treningowych,
A
= (
a
1
,a
2
,...,a
n
) jest
zbiorem atrybutów warunkowych,
c
2
D
=
{
c
1
,c
2
,...,c
m
}
jest atrybutem decyzyj-
nym.
•
Ustalamy metryk¦
d
liczenia odległo±ci mi¦dzy obiektami, oraz ilo±¢ najbli»szych
s¡siadów decyduj¡cych o klasyfikacji
k
,
•
Klasyfikujemy wszystkie obiekty testowe za pomoc¡ k najbli»szych obiektów, ka»-
dej z klas systemu treningowego, (decyzj¦ przekazuje klasa, której obiekty s¡ najbli-
»ej testowego w sensie metryki
d
),
•
Po zako«czeniu klasyfikacji, tworzymy Confusion Matrix, zawieraj¡c¡ informa-
cje o jako±ci klasyfikacji systemu testowego
X
:
Na wzór parametrów jako±ci klasyfikacji u»ywanych w ¢wiczeniu 2, do Confusion
Matrix wpisujemy warto±ci
Dla
8
c
2
D
acc
c
=
ilo
±¢
obiekt
ó
wpoprawniesklasyfikowanychwkoncepciedecyzyjnymc
ilo
±¢
obiekt
ó
wchwyconychwkoncepciec
cov
c
=
ilo
±¢
obiekt
ó
wchwyconychwkoncepciec
ilo
±¢
obiekt
ó
wkonceptuc
x
x
+
ilo
±¢
obiekt
ó
wzpozosta
ł
ychklasb
ł¦
dnietrafiaj
¡
cychdoklasyc
TPR
c
=
przyjmujemy, »e
x
=
ilo
±¢
obiekt
ó
wpoprawniesklasyfikowanychwkoncepciedecyzyjnymc
Ostatecznie wyliczamy warto±ci globalne, które umieszczamy pod Confusion Ma-
trix,
acc
global
=
ilo
±¢
obiekt
ó
wpoprawniesklasyfikowanychwca
ł
ymsystemieTST
ilo
±¢
obiekt
ó
wchwyconychwsystemieTST
cov
global
=
ilo
±¢
obiekt
ó
wchwyconychwca
ł
ymsystemieTST
ilo
±¢
obiekt
ó
wsystemuTST
Przykładowa klasyfikacja 2-NN
Wczytujemy sytem testowy postaci,
Tab
ela 1: System Testowy (
X,
A,c
)
a
1
a
2
a
3
a
4
c
x
1
2
4
2
1
4
x
2
1
2
1
1
2
x
3
9
7
10
7
4
x
4
4
4
10
10
2
oraz system treningowy
Tabel
a 2: System Treningowy (
Y
,A,c
)
a
1
a
2
a
3
a
4
c
y
1
1
3
1
1
2
y
2
10
3
2
1
2
y
3
2
3
1
1
2
y
4
10
9
7
1
4
y
5
3
5
2
2
4
y
6
2
3
1
1
4
Ustalmy
k
=2 i
d
jako metryk¦ Euklidesa
Metryka Euklidesa działa nast¦puj¡co, dla obiektów
x
=
a
1
(
x
)
a
2
(
x
)
...a
n
(
x
)
c
(
x
)
y
=
a
1
(
y
)
a
2
(
y
)
...a
n
(
y
)
c
(
y
)
q
d
(
x,y
) =
(
a
1
(
x
)
−
a
1
(
y
))
2
+ (
a
2
(
x
)
−
a
2
(
y
))
2
+
...
+ (
a
n
(
x
)
−
a
n
(
y
))
2
czyli zapisuj¡c ogólnie:
v
u
u
t
n
X
d
(
x,y
) =
(
a
i
(
x
)
−
a
i
(
y
))
2
i
=1
Przechodzimy do klasyfikacji obiektów testowych:
Dla
x
1
2 4 2 1 4
q
p
d
(
x
1
,y
1) =
(2
−
1)
2
+ (4
−
3)
2
+ (2
−
1)
2
+ (1
−
1)
2
=
3
d
(
x
1
,y
2) =
p
6
5
d
(
x
1
,y
3) =
p
2
p
d
(
x
1
,y
4) =
1
14
d
(
x
1
,y
5) =
p
3
d
(
x
1
,y
6) =
p
2
Dwóch najbli»szych s¡sia
dó
w o
bi
ektu testowego
x
1
w koncepcie 2 to
y
3
,y
1
Klasa 2 głosuje z moc¡
p
2 +
p
3
Najbli»szymi s¡siadami
x
1
w kl
as
ie decyzyjnej 4 s¡
y
6
,y
5
K
la
sa 4
g
łosuj
e
z m
oc
¡
p
2 +
p
3
p
p
p
2 +
p
3
St¡d obiekt
x
1
nie jest chwytany, nie jeste±my w stanie powiedzie¢, która klasa jest
bli»ej w sensie dwóch najbli»szych s¡siadów.
2 +
3 =
Dla
x
2
1 2 1 1 2
d
(
x
2
,y
1) = 1
d
(
x
2
,y
2) =
p
8
4
d
(
x
2
,y
3) =
p
2
d
(
x
2
,y
4) =
p
16
6
p
d
(
x
2
,y
5) =
1
5
p
d
(
x
2
,y
6) =
2
Klasa 2 głosuje z moc¡ 1
+
p
2
Klasa
4
gło
su
je z
mo
c¡
p
p
2 +
15
1 +
p
2
<
p
2 +
p
15
Obiekt
x
2
dostaje decyzj¦ 2, jest poprawnie sklasyfikowany.
Dla
x
3
9 7 10 7 4
p
d
(
x
3
,y
1) =
197
p
d
(
x
3
,y
2) =
117
d
(
x
3
,y
3) =
p
18
2
d
(
x
3
,y
4) =
p
50
d
(
x
3
,y
5) =
p
129
d
(
x
3
,y
6) =
p
182
p
p
Klasa 2 głosuje z moc¡
11
7 +
182
K
las
a 4
głosu
je z
mo
c¡
p
50 +
p
129
p
p
p
p
182
Obiekt
x
3
dostaje decyzj¦ 4, jest poprawnie sklasyfikowany.
50 +
129
<
117 +
Dla
x
4
4 4 10 10 2
p
d
(
x
4
,y
1) =
172
d
(
x
4
,y
2) =
p
182
d
(
x
4
,y
3) =
p
167
d
(
x
4
,y
4) =
p
151
d
(
x
4
,y
5) =
p
130
p
d
(
x
4
,y
6) =
167
p
p
Klasa 2 głosuje z moc¡
167
+
172
K
lasa
4 gł
osu
je z
moc
¡
p
1
30 +
p
151
p
p
p
p
172
Obiekt
x
4
dostaje decyzj¦ 4, jest bł¦dnie sklasyfikowany.
130 +
151
<
167 +
Podsumowuj¡c klasyfikacj¦:
Obiekt
x
1
nie jest chwytany
Obiekt
x
2
dostaje decyzj¦ 2, jest poprawnie sklasyfikowany
Obiekt
x
3
dostaje decyzj¦ 4, jest poprawnie sklasyfikowany
Obiekt
x
4
dostaje decyzj¦ 4, jest bł¦dnie sklasyfikowany.
Confusion Matrix jest postaci:
Tabela 3: Confusion Matrix
2
4
No.ofobj.AccuracyCoverage
2
1
1
2
0
.
5
1
.
0
4
0
1
2
1
.
0
0
.
5
TruePositiveRate
1
.
0
0
.
5
Dodatkowe pytanie
•
Jak powinna wygl¡da¢ obsługa bł¦dów metody k-NN, czyli jakie ograniczenia
wprowadzanych danych mo»emy napotka¢?
Plik z chomika:
monibach
Inne pliki z tego folderu:
KNN.exe
(22 KB)
ds_generatorTT.exe
(625 KB)
cw3nowy.xlsx
(43 KB)
c3.pdf
(71 KB)
Inne foldery tego chomika:
Ćw 1
Ćw 10
Ćw 2
Ćw 4
Ćw 5
Zgłoś jeśli
naruszono regulamin