Č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