České vysoké učení technické v České vysoké učení technické v PrazePraze
Fakulta Fakulta informinformačních technologiíačních technologií
Katedra teoretické informatikyKatedra teoretické informatiky
1
MI-ADM – Algoritmy data miningu (2010/2011)
Přednáška 2: Model, hodnocení modelu, metoda K nejbližších sousedů
Pavel Kordík, FIT, Czech Technical University in Prague
Kordik, Holena CTU Prague, FIT, MI-ADM 2
BusinessUnderstanding
Data Understanding
Data Preparation
Modeling Deployment Evaluation
FormatData
IntegrateData
ConstructData
CleanData
SelectData
DetermineBusiness
Objectives
ReviewProject
ProduceFinal
Report
Plan Monitering&
Maintenance
PlanDeployment
DetermineNext Steps
ReviewProcess
EvaluateResults
AssessModel
BuildModel
GenerateTest Design
SelectModelingTechnique
AssessSituation
ExploreData
DescribeData
CollectInitialData
DetermineData Mining
Goals
VerifyData
Quality
ProduceProject Plan
CRISP-DM: Phases and tasksMI-KDD MI-KDDMI-ROZ, MI-MVIMI-PDD
MI-ADM
MI-ADM
Nahrazuje bakalářský předmět BI-VZD Větší důraz na porozumění data miningu
jak z algoritmického, tak teoretického pohledu
Částečný překryv s MI-ROZ, ale podáno z jiné perspektivy
Je přípravou na předmět MI-MVI
MI-MVI – Metody výpočetní inteligence3
Computational Intelligence Methods
Artificial Neural Networks
Fuzzy Logic Evolutionary Computing
Machine Learning
4. Statistical MethodsBayesian, Monte Carlo etc
1. Divide and Conquer MethodsDecision trees, production rules…
2. Instance Based Learning Nearest neighbor, case based reasoning
5. Support Vector MachinesSVM, kernel methods, PCA, ICA
2. Back Propagation Learning
HYBRID METHODS
3. Reinforcement Learning4. Kohonen’s Self Organizing Maps
3. Hopfield’s Associative Memory
1. Adaptive Resonance Theory
7. Real Time Recurrent Learning
5. Pulsed Neural Networks
6. Radial Basis Functions
Metody výpočetní inteligence
5
Dnešní přednáška Model Metoda K- nejbližších
sousedů Plasticita modelu Hodnocení modelu Regularizace
Rozdělení modelů dle funkce
Predikční (predictive)
Popisné (descriptive)
Klasifikace Regrese, predikcebudoucí hodnoty
Shlukování a segmentace
Souhrny
Analýza vztahů a závislostí
Analýza časových řad
Modely v data miningu
Funkce MetodyKlasifikace Linear separation, Rule induction methods,
Decision trees, Neural networks, SVM, nearest neighbours, Case based reasoning
Regrese a predikce budoucí hodnoty
Linear, polynomial, logistic regression, Regression trees, Neural networks, nearest neighbours
Analýza časových řad Autoregression, Moving averages, Regression trees, neural networks, SVM
Analýza vztahů a závislostí
Association rules, Correlation analysis, Regression analysis, Bayesian networks, Inductive logic programming
Popis dat, souhrny Statistical techniques, OLAP
Shlukování a segmentace
K-nearest neighbour, Agglomerative clustering, Neural networks, Visualization methods
Přehled metod generujících modely
Klasifikace a regrese Klasifikační i regresní model:
y = f(x) Klasifikace: y je nominální (název třídy) Regrese: y je spojitá veličina (teplota,
výška)Klasifikační model
origin(America, Europe,
Japan)weightdispmpg
Regresní model
mpg300-800
weightdispcyl
Vytvoření a použití modelu
2 fáze Fáze učení, trénování
Model je vygenerován, upravuje se vnitřní struktura, parametry
Fáze použití, vybavování Model je použit, vypočítá se výstup, model to
neovlivní 9
Klasifikační model
origin(America, Europe,
Japan)weightdispmpg
1NN – nejbližší soused
Trénování – generování modelu Ulož trénovací data
Klasifikace – použití modelu Najdi nejbližšího souseda a klasifikuj stejnou třídou
http://www.theparticle.com/applets/ml/nearest_neighbor/
?
Metrika, Euklidovská vzdálenost
Je třeba nějak určit podobnost vzorů – jejich vzdálenost
Vzdálenost musí splňovat určité podmínky:1. d(x,y) > 0. 2. d(x,y) = 0 iff x = y.3. d(x,y) = d(y,x).4. d(x,y) < d(x,z) + d(z,y) (trojúhelníková nerovnost ).
Odmocňování není nezbytně nutné, když vzdálenosti porovnáváme
Euklidovská vzdálenost P a Q =
Dva body v n-rozměrném prostoru:
Manhattonská vzdálenost
Jak budeme počítat vzdálenost dvou cyklistů v Manhattonu?
nn qpqpqpQPM ..., 2211
Váha atributů
Problém – různé rozsahy vzdáleností Při určování euklidovské vzdálenosti mají atributy
různou váhu – např. p je 100x důležitější než q
0
3,5
2 350p
q
Normalizace atributů Problém vyřešíme přeškálováním (normalizací)
atributů:
Původní rozsahy se transformují do <0,1>
ii
iii vv
vva
minmax
min
)(
)(
i
iii vStDev
vAvgva
nebo
0
1
0 1p
qKde přesně je rozhodovací hranice tříd?
Voronoiův diagram
http://www.cs.cornell.edu/Info/People/chew/Delaunay.html
kNN – k nejbližších sousedů
Klasifikace Najdi k nejbližších sousedů a klasifikuj majoritní
třídou
Příklad 3NN klasifikace:
Jak zvolit optimální k?
?
Klasifikace
Generalizace
Lineární klasifikátor (separátor)
Nelineární klasifikátor
1NN
3NN
9NN
9NN, měkké rozhodnutí (poměr mezi počtem sousedů z různých tříd)
31NN – měkké rozhodnutí
x1
x2
Přeučení
x1
x2
Jak zjistit přeučení?
27
Rozdělit na trénovací a testovací data.
Model vygenerovat na datech trénovacích.
Chybu počítat na datech testovacích.mpg cyldisp hp wgt acc year Origin name 15 8 400 150 3761 9.5 70 US chevrolet_monte_carlo 14 8 455 225 3086 10 70 US buick_estate_wagon_(sw) 24 4 113 95 2372 15 70 JP toyota_corona_mark_ii 22 6 198 95 2833 15.5 70 US plymouth_duster 18 6 199 97 2774 15.5 70 US amc_hornet 21 6 200 85 2587 16 70 US ford_maverick 27 4 97 88 2130 14.5 70 JP datsun_pl510 26 4 97 46 1835 20.5 70 EU volkswagen_1131_deluxe_sedan 25 4 110 87 2672 17.5 70 EU peugeot_504 24 4 107 90 2430 14.5 70 EU audi_100_ls
TRAINTESTTRAINTRAINTESTTRAINTRAINTRAINTESTTEST
Učení a evaluace modeluTré
novací
Test
.Vstupy
Výstup
Učení,trénování modelu
Model
Predikce,použití modelu
Model
Výpočet chyby modelu
Odhady modelu
Chyba na testovacích datech
Chyba modelu Klasifikační model:
procento nesprávných předpovědí Regresní model:
součet absolutních hodnot odchylek součet čtverců odchylek
průměrný čtverec odchylky odmocnina průměrného čtverce odchylky
(RMSE)
( )i ii
err y f x 2
( )i ii
err y f x
21( )i i
i
err y f xN
21( )i i
i
RMSE y f xN
Rozhodovací hranice pro různá K Viz. demostrační interaktivní program
(autor Petr Pošík)
Načtení dat V dnešním cvičení budeme opět
používat databázi aut. Načtěte soubor auto-mpg.data-mod-
names.csv do objektu dataset a definujte jména jednotlivých atributů
auta = dataset('file', 'auto-mpg.data-mod-names.csv',...'ReadVarNames', false, 'ReadObsNames', false,... 'delimiter', ',', ...'VarNames', {'mpg', 'cyl', 'disp', ...
'hp', 'wgt', 'acc', 'year', 'org', 'name'});
Normalizace dat auta_norm = datasetfun( @minmax, auta(:,1:5), 'UniformOutput', false );
auta_norm = [auta_norm{:}]; auta = replacedata( auta, auta_norm, 1:5);
Rozdělení dat I
První polovinu datasetu použijeme pro trénování.
Druhou polovinu pro testování. Jak to udělat?
Rozdělení dat I První polovinu datasetu použijeme pro
trénování. Druhou polovinu pro testování. Jak to udělat?
auta_tren = auta(1:pocet_aut/2,:); auta_test =
auta(pocet_aut/2+1:pocet_aut,:);
Co může být problém při tomto způsobu dělení? Je trénovací a testovací množina reprezentativní podmnožinou?
Lépe: náhodné rozdělení dat
Vysvětlete:
function [tren, test] = rozdel_data(inData, hranice) vect = rand(1,length(inData));velikost_trenovaci_mnoziny = hranice;testIdx = find(vect > velikost_trenovaci_mnoziny);trenIdx = find(vect <= velikost_trenovaci_mnoziny);tren = inData(trenIdx,:);test = inData(testIdx,:);
end
Najdi k nejbližších sousedů Funkce pro výpočet nejbližšího souseda:[indexy_nejblizsich, vzdalenosti_k_nejblizsim] = knnsearch(testovaci mn, trenovaci mn, K)
Pro všechny testovací instance vrátí pole indexů nejbližších sousedů z trénovací množiny a pole vzdáleností k nim
Najděte v kódu funkce výpočet vzdálenosti
Najdi k nejbližších sousedů Pro 1NNif K==1 % Loop for each query point for k=1:N d=zeros(L,1); for t=1:M d=d+(R(:,t)-Q(k,t)).^2; end [D(k),idx(k)]=min(d); end
Trénovací množina
Testovací instance
Najdi k nejbližších sousedů kNN for k=1:N d=zeros(L,1); for t=1:M d=d+(R(:,t)-Q(k,t)).^2; end [s,t]=sort(d); idx(k,:)=t(1:K); D(k,:)=s(1:K); end
Trénovací množina
Testovací instance
Seřaď vzdálenostis – vzdálenosti,t - indexy
Klasifikuj do majoritní třídy Funkce pro klasifikaci z indexu nejbližších sousedů[oklasifikovana_testovaci_data] =
classify2(indexy_nejblizsich_sousedu, klasifikace_trenovacich_dat mn, pocet_trid)
trénovacítestovací
3NN
Klasifikuj do majoritní třídy Funkce pro klasifikaci z indexu nejbližších sousedů[oklasifikovana_testovaci_data] = classify2(indexy_nejblizsich_sousedu,
klasifikace_trenovacich_dat mn, pocet_trid)
function class = classify2(nearestIdxs, trainingClasses, numClasses)class = zeros(1,length(nearestIdxs));for i = 1:length(nearestIdxs)
classesCount = zeros(1,numClasses);for j = 1:numClasses
classesCount(j) = length(find(trainingClasses(i,:) == j));
end[cnt,finalClass] = max(classesCount);class(i) = finalClass;
endend
Klasifikuj do majoritní třídy Funkce pro klasifikaci z indexu nejbližších sousedů[oklasifikovana_testovaci_data] =
classify2(indexy_nejblizsich_sousedu, klasifikace_trenovacich_dat mn, pocet_trid)
trénovacítestovací
indexy_nejblizsich_sousedu
3NN
classesCount 1 23 0
class = oklasifikovana_testovaci_data
Křížová validace Umožňuje odhadnout testovací chybu a
potřebuje k tomu jen trénovací data Slouží k výběru (vhodné struktury a
parametrů) modelu
K-NN pro regresi Jak byste použili k-NN pro regresi (pro predikci
spojité veličiny)?
cyl disp wgt mpg
2 1800 2000 35
2 1900 2500 30
4 1800 1500 33
4 2400 2200 25
6 2000 2500 16
cyl disp wgt mpg
4 2000 2800 ????
K-NN regrese Demostrace
Varianty kNN Příspěvek souseda je vážen vzdáleností od
klasifikovaného vzoru
Klasifikace pomocí etalonů – vybrána vhodná podmnožina trénovací množiny
Experimenty na doma Postav 2NN klasifikátor původu aut
(origin) a sleduj shodu klasifikace s originálním atributem na všech datech
Porovnej chybu klasifikace na testovací množině pro 1NN a 10NN
Zjisti, které K je optimální pro model mpg z ostatních atributů pomocí metody KNN
Pro konkrétní auto najdi 3 jeho nejbližší sousedy
Diskuze k NN
Velmi populární metody a často i velmi úspěšné
Ale pomalejší vybavování Při klasifikaci musím projít celou trénovací množinu
Pozor na váhy atributů Řešením je normalizace dat
Důležité najít vhodné k Abychom minimalizovali chybu na testovacích datech
Použitelné i pro regresní problémy
