Archyvas

Įrašai pažymėti ‘klasifikavimas’ žyma

Kvadratinis Gauso klasifikatorius

2011-12-06
Komentarų nėra

Klasifikavimo uždaviniui spręsti yra daugybė klasifikatorių, o mes palengva šį bei tą išmėginsim, pažiūrėsim kaip jie veikia ir kaip atrodo iš arčiau.

Šiandien mūsų taikinyje yra kvadratinis Gauso klasifikatorius. Teoriją apie klasifikatorių įkėliau atskirai, bet ji angliškai ir gana skurdi. Šis klasifikatorius leidžia rasti ribą tarp dvejų klasių, tačiau norint gero tikslumo, reikia pasiekti, kad požymiai turėtų normalinį pasiskirstymą. Naudojami duomenys yra čia, tik du požymiai ir dvi klasės. Programos kodas:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

clc;
close all;
 
% Užkraunami duomenys
load Apple.txt
data = Apple;
clear Apple;
 
% Braižomas grafikas
y = data(:,3) == 0;
d1 = data(y,1:2)';
d2 = data(~y,1:2)';
figure(1); clf; hold on
plot(d1(1,:), d1(2,:), 'r+');
plot(d2(1,:), d2(2,:), 'g+');
axis('equal');
 
% Parametrai
fromCol = 1; % nuo kurio stulpelio prasideda požymiai, imtinai
features = 2; % požymių kiekis
till = fromCol + features - 1; % paskutinis požymių stulpelis
classCol = 3; % stulpelis, kuriame yra klasės numeris
 
% Tikslumo skaičiavimas su "10-fold cross validation"
tic;
accuracy = mycrossvalidation('Gaussian', data, classCol, fromCol, features);
fprintf('Tikslumas = %3.2f, laikas = %3.2f s \n', accuracy, toc);
 
% Piešiamas klasifikatoriaus diskriminantinės funkcijos kontūras
cols = fromCol + features - 1; % stulpelių kiekis duomenyse
k = data(:, classCol) == 0;
c1 = data(k, fromCol : cols)'; % apmokymo duomenų pirma klasė
c2 = data(~k, fromCol : cols)'; % apmokymo duomenų antra klasė
d = -2 : .05 : 2;
[X, Y] = meshgrid(d, d);
xx = 1;
yy = 1;
Z = zeros(size(X));
for x = d
    for y = d
        Z(yy, xx) = quadratic_gaussian_classifier([x y]', c1, c2);
        yy = yy + 1;
    end;
    xx = xx + 1;
    yy = 1;
end;
contour(X, Y, Z, [0,0], 'k');

Naudojama „10-fold cross validation“ validacija, kuri leidžia patikrinti klasifikatoriaus efektyvumą su skirtingomis duomenų imtimis:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function [accuracy] = mycrossvalidation(type, data, classCol, fromCol, features)
el = size(data, 1); % kiek duomenų yra iš viso
p = 90; % kiek duomenų skirti apmokymui procentais
q = int16(size(data, 1) * p / 100); % kiek duomenų skirti apmokymui
 
total = 0; % bus skaičiuojami teisingi atpažinimai
step = el - q;
for w = 1 : step : el % 10-fold cross validation
    % paskaičiuojami nuo (from) iki (till) intervalas testavimui
    from = w;
    till = w + el - q - 1;
    if till > el
        till = el;
    end;
    % atrenkama apmokymo ir testavimo dalis
    testing = data(from : till, :);
    training = data;
    training(from : till, :) = [];
    % tikrinamas konkretus klasifikatorius, šiuo atveju turime tik vieną
    if strcmp(type, 'Gaussian') == 1
        [count, accuracy] = mygaussian(training, testing, classCol, fromCol, features);
    end;
    total = total + count; % sumuojamas teisingai atpažintas duomenų kiekis
end;  
 
accuracy = total * 100 / el;

Skaičiuojamos tikimybės, kuriai klasei priklauso konkretūs atvejai iš testavimo duomenų imties:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function [count, accuracy] = mygaussian(training, testing, classCol, fromCol, features)
cols = fromCol + features - 1; % stulpelių kiekis duomenyse
 
k = training(:, classCol) == 0;
c1 = training(k, fromCol : cols)'; % apmokymo duomenų pirma klasė
c2 = training(~k, fromCol : cols)'; % apmokymo duomenų antra klasė
 
count = 0;
el = size(testing, 1);
for z = 1 : el % tikrinam su visais testavimo duomenimis
    x = testing(z, fromCol : cols)';
    class = quadratic_gaussian_classifier(x, c1, c2);
    if class == testing(z, classCol) % ar apskaičiuota klasė atitinka tikrą
        count = count + 1;
    end;
end;
 
accuracy = count * 100 / el;

Ir galiausiai kvadratinio Gauso klasifikatoriaus realizacija pagal 2.20 formulę:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function [class] = quadratic_gaussian_classifier(x, c1, c2)
covM1 = cov(c1');
covM2 = cov(c2');
invM1 = inv(covM1);
invM2 = inv(covM2);
piko1 = mean(c1, 2);
piko2 = mean(c2, 2);
pc1 = size(c1, 2);
pc2 = size(c2, 2);
A = 0.5 * (invM1 - invM2); % 2.21 formulė
beta = invM2 * piko2 - invM1 * piko1; % 2.22 formulė
gama = (piko1' * invM1 * piko1 - piko2' * invM2 * piko2) * 0.5 ...
    + log(det(covM1) / det(covM2)) - log(pc1 / pc2); % 2.23 formulė
res = x' * A * x + beta' * x + gama; % 2.20 formulė
if res < 0
    class = 0;
elseif res > 0
    class = 1;
else
    class = -1; % neapsisprendęs
end;

Skaičiavimų rezultatas:

Selec All Code:
1

Tikslumas = 97.68, laikas = 1.14 s

Diskriminantinės funkcijos kontūras parodytas paveikslėlyje, taškų braižymui paimta nedaug, todėl kreivė laužyta, tačiau tai yra parabolė:

97,68 % tikslumas yra gana aukštas. Šį klasifikatorių bandžiau su duomenimis, kurie turi 30 požymių ir gavau 95,96 % tikslumą, o atmetus mažiau reikšmingus požymius ir palikus jų tik 8 bei kai kuriuos iš jų normalizavus, pavyko pasiekti 97,01 % tikslumą. Vadinasi klasifikatorius yra gana tikslus, greitas ir patogus. Tačiau jis tinka tik gana paprastiems uždaviniams.

Tyrinėjimai , ,

k artimiausių kaimynų metodas KNN

2011-10-30
Komentarų nėra

KNN (k nearest neighbors) metodas klasifikuoja tikrindamas kokioms klasėms priklauso artimiausi K kaimynai ir priskiria tai klasei, kuriai priklauso daugelis K kaimynų. Įėjimo vektorius gali turėti bet kokį požymių kiekį, pvz.: 1, 2, 10 ir daugiau. Euklido atstumą naudosime skaičiuojant atstumą tarp kaimynų, kurį lengva paskaičiuoti net ir daug dimensijų turinčiai erdvei. Išbandysime pasirašyti savo KNN funkciją bei palyginti rezultatą su Matlab knnclassify funkcija naudojant dvejų dimensijų duomenų aibę. Abejų klasių duomenys (0 – raudona, 1 – žalia) parodyti žemiau:

Eksperimentas labai paprastas. Užkrausime duomenis, kurie turi du požymius, o pačių duomenų yra kiek daugiau nei tūkstantis. Apmokymui imsime dešimt procentų duomenų atsitiktine tvarka, o tikslumą tikrinsime su likusiais.

Programa:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

clc;
close all;
 
load apple.txt
data = apple;
% duomenys išmaišomi atsitiktine tvarka, nes kas kartą norime
% naudoti vis kitą imti apmokymui, o likutį testavimui
data = data(randperm(size(data, 1)), :);
clear apple;
 
% atvaizduojam abi klases
figure(1); clf; hold on
l = data(:, 3) == 0;
d1 = data(l, 1 : 2)';
d2 = data(~l, 1 : 2)';
plot(d1(1, :), d1(2, :), 'r+');
plot(d2(1, :), d2(2, :), 'g+');
axis('equal');
 
p = 10; % kiek duomenų skirti apmokymui procentais
features = 2; % požymių kiekis
k = 3; % kiek kaimynų naudoti klasifikuojant
q = int16(size(data, 1) * p / 100); % kiek duomenų skirti apmokymui
training = data(1 : q, 1 : features); % apmokymo duomenys
plot(training(:, 1), training(:, 2), 'b.'); % pažymėti, kurie duomenys dalyvauja apmokyme
group = data(1 : q, features + 1); % apmokymo duomenų klasės
total = size(data, 1); % duomenų kiekis
correct1 = 0;
correct2 = 0;
for i = q + 1 : total % testuoti tik su tais duomenimis, kurie nenaudojami apmokymui
    g = data(i, features + 1);
    sample = data(i, 1 : features);
    c = knnclassify(sample, training, group, k);
    if c == g
        correct1 = correct1 + 1;
    else
        fprintf('Klaida: %d \n', i);
    end;
    c = myknnclassify(sample, training, group, k);
    if c == g
        correct2 = correct2 + 1;
    else
        fprintf('Klaida: %d \n', i);
    end;
    fprintf('Total iterations: %d, done: %d\n', total - q, i - q);
end;
fprintf('knnclassify rezultatas: %4.2f %%\n', 100 * correct1 / (total - q));
fprintf('myknnclassify rezultatas: %4.2f %%\n', 100 * correct2 / (total - q));

KNN funkcija:

Selec All Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function [class] = myknnclassify(sample, training, group, k)
A = zeros(1, 2); % matrica artimiausiems kaimynams saugoti
n = size(training, 1); % iš viso kaimynų kiekis
for i = 1 : n % kiekvienam kaimynui atliekami skaičiavimai
    d = euclidean_distance(training(i, :), sample); % randamas Euklido atstumas
    s = size(A, 1);
    if s < k % jeigu artimiausių kaimynų atrinkta mažiau nei K, tai papildom
        A(s + 1, 1 : 2) = [group(i) d];
    elseif A(k, 2) > d % jeigu artimiausių kaimynų atrinkta K, tolimiausią keičiam artimesniu
        A(k, 1 : 2) = [group(i) d];
    end;
    A = sortrows(A, 2); % išrūšiuojam pagal atstumą
end;
m = max(group) + 1; % klasių kiekis
B = zeros(1, m);
for i = 1 : k % randam po kiek artimiausių kaimynų priklauso kiekvienai klasei
    B(A(i, 1) + 1) = B(A(i, 1) + 1) + 1;
end;
[maxC, maxI] = max(B); % klasės indeksas, kurioje daugiausiai artimiausių kaimynų
[minC, minI] = min(B); % klasės indeksas, kurioje mažiausiai artimiausių kaimynų
if maxC > minC % laimėtoja klasė, kuri turi daugiausia artimiausių kaimynų
    class = maxI - 1;
else % jeigu visos klasės turi vienodą kaimynų kiekį (gali būti ir kitokie kriterijai)
    class = -1; % atmetimo (reject) klasė
end;

Euklido atstumas:

Selec All Code:
1
2
3
4
5
6
7

function [d] = euclidean_distance(x, y)
n = size(x, 2);
d = 0;
for i = 1 : n
    d = d + (x(i) - y(i)) ^ 2;
end;
d = d ^ 0.5;

Abejų funkcijų rezultatai yra gana panašūs. Kadangi duomenų klasės nepersidengia ir yra gana toli viena nuo kitos, tai pakanka vos kelių procentų apmokymo duomenų, kad visus likusius duomenis abi funkcijos klasifikuotų šimto procentų tikslumu. Žemiau esančiame paveiksliuke matosi mėlynai pažymėti taškai, kurie buvo naudojami apmokymui ir yra atrinkti atsitiktine tvarka (vos 10 procentų nuo visų duomenų). Kiekvieną kartą užkrovus duomenis, parenkama vis kita 10 procentų duomenų imtis apmokymui, taip mes galime matyti kaip funkcijų tikslumas priklauso nuo skirtingų duomenų aibių, tačiau išlaikant norimą jos dydį:

myknnclassify funkcija yra dešimt kartų lėtesnė nei Matlab standartinė funkcija knnclassify ir kiek testavau, mažiau tiksli. Be to, aprašytoje gali būti (ir tikriausiai yra) klaidų, nes ji nėra pilnai ištestuota kaip Matlab funkcija. Todėl Matlab funkcija yra gerokai pranašesnė, kuri be to dar turi ir įvairių papildomų parametrų.

Tyrinėjimai , , , ,