Archyvas

December, 2011 archyvas

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 , ,