1. Data mining. Strojové ucenˇ í. Základní úlohy. Ucenˇ í s uciˇ ......DM jako proces:...

P. Pošík c© 2010 Aplikace umělé inteligence – 1 / 36

1. Data mining. Strojové učení. Základní úlohy.Učení s učitelem a bez učitele.

Petr Pošík

Katedra kybernetiky

ČVUT FEL

Obsah

Návaznosti

Data mining

Strojové učení

Flexibilita a složitostmodelu

Závěr


Návaznosti

Data mining

Strojové učení

Flexibilita a složitost modelu

Závěr

Návaznosti

NávaznostiCo bylo v ZUI?Co bude v AUI?

Data mining

Strojové učení


Závěr


Co bylo v ZUI?


✔ Prohledávání st. prostoru

✘ konstruktivní neinformované ainformované metody

✘ generativní metody, deterministické astochastické

✔ Splňování omezujících podmínek

✔ Evoluční algoritmy

✘ Reprezentace, fitness, křížení, mutace,selekce

✘ Aplikace

✔ Znalosti, reprezentace, výroková logika

✔ Predikátová logika, Prolog

✔ Neurčitost, pravděpodobnost, Bayesovskésítě

✔ Strojové učení, učení z příkladů

✘ Induktivní učení popisu konceptu vpredikátové logice

✔ Posilované učení

✔ Plánování

✘ Plánování jako prohledávání stavovéhoprostoru

✘ popis úloh v jazyce STRIPS

✘ partially ordered plans

✔ Neuronové sítě

✘ Typy NN, úlohy pro NN (s učitelem, bezučitele)

✘ Trénovací, validační, testovací

✘ Učení NN, error backpropagation

✔ Aplikace

Co bude v AUI?


Data mining

Strojové učení


Závěr


Předběžný plán přednášek:

1. Strojové učení, základní úlohy, učení s učitelem a bez učitele2. Lineární diskriminační funkce, perceptronový algoritmus, rozšíření báze3. Optimální rozdělující nadplocha, SVM4. Neuronové sítě, zpětné šíření chyby5. Učení bez učitele, hierarchické shlukování, k-means a EM algoritmus.6. Neuronové sítě - RBF, Kohonenova sít’, autoasociativní sít’7. Generativní metody prohledávání stavového prostoru, EA s reálnou reprezentací8. Alternativní přírodou inspirované techniky – ACO, PSO9. Základní techniky UI pro plánování

10. Úvod do multiagentních systémů a agentních technologií11. Plánování ve výrobě a v logistice (ukázky systému)12. Simulace, diagnostika a inteligentní robotika (ukázky systému)

Data mining

Návaznosti

Data miningDefiniceRozdílné pohledy nadataÚčel DMZdroje DMÚlohy pro DMCRISP-DM

Strojové učení


Závěr


Definice

Návaznosti


Strojové učení


Závěr


„Data mining je netriviální dobývání skrytých, předem neznámých apotenciálně užitečných informací z dat.“ Při jejich objevování se využívajíexpertní systémy, metody umělé inteligence a strojového učení,statistické, grafické a vizualizační techniky a prezentují se způsobemsrozumitelným lidem. [FSM92]

Český překlad

✔ Dolování dat✔ Vytěžování dat✔ Dobývání znalostí z databází (překlad KDD - knowledge discovery in databases)

Co má data mining společného s aplikacemi umělé inteligence?

✔ DM: obsáhlý proces zahrnující mnoho fází orientovaný na praktický přínos, na aplikace

✔ Metody umělé inteligence, strojového učení a rozpoznávání se uplatňují

✘ především ve fázi modelování, ale také✘ v několika dalších fázích procesu DM.

Rozdílné pohledy na data

Návaznosti


Strojové učení


Závěr


Exploratorní analýza dat

✔ Průzkum dat, první seznámení s daty, formulujeme hypotézy.

✔ Hojně se využívají grafické techniky.


Návaznosti


Strojové učení


Závěr





Konfirmatorní analýza dat

✔ Máme hypotézy, data slouží jako prostředek pro jejich ověření.

✔ Využívají se statistické metody (ANOVA, regrese, χ-kvadrát testy, . . . )


Návaznosti


Strojové učení


Závěr





Konfirmatorní analýza dat

✔ Máme hypotézy, data slouží jako prostředek pro jejich ověření.

✔ Využívají se statistické metody (ANOVA, regrese, χ-kvadrát testy, . . . )

Data mining

✔ Máme data a chceme vytvořit modely, které fungují a jsou použitelné propredikce.1

✔ Využití metod umělé inteligence, strojového učení, . . .

1V obchodních a marketingových aplikacích bývá druhořadé, zda tyto modely popisují skutečné závislosti a děje.Při aplikaci metod strojového učení např. na biologické a medicinské aplikace je správnost modelu vyžadována mno-hem více.

Účel DM

Návaznosti


Strojové učení


Závěr


✔ DM je orientován na praktickou využitelnost výsledků, hlavně ve formě predikcí(exploratorní analýza dat naproti tomu slouží spíše k popisu dat, výzkumníky přiní napadají souvislosti, které stojí za ověření)

✔ Jde hlavně o vytvoření modelu, který přináší užitek, tj. modelu, jehož prognózybudou trefné, klasifikace použitelné (a zisky a úspory z něj plynoucí znatelné)

✔ Příklady otázek, na něž DM umí dát (přibližnou) odpověd’:

✘ Kolik člověkohodin bude třeba příští měsíc odpracovat na ARO?

✘ Kolik asi bude stát pozemek 20 km severně od Prahy?

✘ Odpoví konkrétní člověk z naší databáze na nabídku, kterou bychom muzaslali?

✘ Které produkty se prodávají společně? Které produkty si lidé kupují poté, co sikoupili jiné?

Zdroje DM

Návaznosti


Strojové učení


Závěr


Typy úloh řešených pomocí DM

Návaznosti


Strojové učení


Závěr


✔ Popis dat

✘ Vizualizace

✘ Sumarizace

✔ Hledání „nugetů“

✘ Dominantní struktury, asociační pravidla

✘ Segmentace, shluková analýza, popis rozdělení dat

✔ Predikce

✘ Klasifikace (predikce kategoriální proměnné)

✘ Regrese (predikce spojité proměnné)

✘ Časové řady (predikce závislé na čase)

DM jako proces: CRISP-DM

Návaznosti


Strojové učení


Závěr


Cross-Industry Standard Process for Data Mining

Strojové učení

Návaznosti

Data mining

Strojové učeníAI, ML, PRRozpoznáváníUčení jako indukcemodeluUčení s učitelem a bezučiteleDruhy úloh


Závěr


AI, ML, PR

Návaznosti

Data mining



Závěr


Umělá inteligence (Artificial Intelligence, AI) [McC04]: „Věda o sestavováníinteligentních strojů.“

✔ AI studuje: inteligentní chování, učení, adaptaci ve strojích a počítačích✔ AI zahrnuje: řízení, plánování a rozhodování, expertní systémy, rozpoznávání

ručně psaných znaků, přirozeného jazyka, mluvené řeči, obličejů, . . .

AI, ML, PR

Návaznosti

Data mining



Závěr





Strojové učení (Machine Learning, ML) studuje algoritmy umožňující strojům „učit se“.

✔ ML zahrnuje: syntaktické rozpoznávání, diagnostické systémy, bioinformatika,detekce zneužití kreditních karet, analýza akciového trhu, klasifikace DNAsekvencí, rozpoznávání ručně psaných znaků, přirozeného jazyka, mluvené řeči,obličejů, navigace robota, . . .

AI, ML, PR

Návaznosti

Data mining



Závěr





Strojové učení (Machine Learning, ML) studuje algoritmy umožňující strojům „učit se“.

✔ ML zahrnuje: syntaktické rozpoznávání, diagnostické systémy, bioinformatika,detekce zneužití kreditních karet, analýza akciového trhu, klasifikace DNAsekvencí, rozpoznávání ručně psaných znaků, přirozeného jazyka, mluvené řeči,obličejů, navigace robota, . . .

Rozpoznávání (Pattern Recognition, PR) je proces, na jehož vstupu jsou „surová“ dataa na výstupu je nějaká akce závislá na kategorii pozorovaných dat. Klasifikace datzaložená na apriorních znalostech nebo na statistických informacích extrahovaných z dat.

✔ PR zahrnuje: syntaktické rozpoznávání, detekce zneužití kreditních karet, analýzaakciového trhu, klasifikace DNA sekvencí, rozpoznávání ručně psaných znaků,přirozeného jazyka, mluvené řeči, obličejů, navigace robota, . . .

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:

✔ Statistické, příznakové — usuzování podle spojitých či diskrétních znakůměřených na objektu

✔ Strukturální — usuzování podle vztahů mezi jednotlivými prvky objektu(často: struktura objektu → odvozené příznaky → příznakové rozpoznávání)

Druhy veličin (pro příznakové rozpoznávání):

✔ Spojité vs. diskrétní

✔ Nezávislé (vstupy) vs. závislé (výstupy)

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:






Znak Škála Možné operace Příklady

Kval. Nominální

Ordinální

Kvant. Intervalová

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:







Kval. Nominální Popsat příslušnost

Ordinální

Kvant. Intervalová

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:







Kval. Nominální Popsat příslušnost Barva očí, národnost, pohlaví, místo narození

Ordinální

Kvant. Intervalová

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:








Ordinální Seřadit

Kvant. Intervalová

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:








Ordinální Seřadit Popis velikosti (S,M,L,XL,XXL), vzdělání (ZŠ, SŠ, VŠ)

Kvant. Intervalová

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:









Kvant. Intervalová Porovnat vzdálenosti

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:









Kvant. Intervalová Porovnat vzdálenosti Kalendářní datum, teplota, úhel, vzrůst zadlužení státu

Poměrová

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:










Poměrová Porovnat velikosti

Rozpoznávání

Návaznosti

Data mining



Závěr


Rozpoznávání:










Poměrová Porovnat velikosti Objem prodeje, průměr hřídele, hmotnost, pH

Učení jako indukce modelu

Návaznosti

Data mining



Závěr


Dvě fáze:

1. Učení modelu z příkladů (trénovací data)

✔ učícímu algoritmu jsou předkládány příklady (a protipříklady) konceptu,který se má naučit rozpoznávat

2. Vybavování modelu, rozpoznávání (testovací data)

✔ naučenému modelu jsou předkládány neznámé příklady k ohodnocení

(a) Model se učí. Trénovací data (dvo-jice x, y) jsou předkládány algoritmu učení,který tvoří strukturu modelu a ladí jeho pa-rametry.

(b) Model si vybavuje. Testovací data (ob-jekty x) „procházejí“ naučeným modelem,který poskytuje odhady hodnot závisléhoznaku y.

Předpoklad (běžný ve strojovém učení):

✔ trénovací a testovací data jsou nezávislá a pocházejí ze stejnéhopravděpodobnostního rozdělení (IID: Independent and Identically Distributed)

Učení s učitelem a bez učitele

Návaznosti

Data mining



Závěr


✔ Objekty jsou popsány vektorem příznaků x

✔ Učení bez učitele

✘ žádné další informace nejsou známy

✘ snaží se najít v datech přirozenou strukturu (a zakódovat ji v modelu)

✔ Učení s učitelem

✘ každý objekt má přiřazen i „štítek“ y (informaci od učitele)

✘ snaží se naučit relaci x → y (zakódovat ji v modelu)

Druhy úloh

Návaznosti

Data mining



Závěr


Klasifikace „štítek“ je kategoriální proměnná

Regrese „štítek“ je spojitá proměnná

Časové řady významným vstupem modelu (někdy i jediným) je čas

Shlukování „štítek“ není dán

Predikce

✔ je výrok o jisté události v budoucnosti (předpověd’, časové řady).

V ML se hojně používá i ve smyslu

✔ aplikace naučeného modelu na nová data, nebo

✔ hodnoty poskytnuté modelem pro nová data.

Další často řešenou úlohou je analýza nákupního koše, která dala vzniknout asociačním asekvenčním pravidlům.

Flexibilita a složitost modelu

Návaznosti

Data mining

Strojové učení

Flexibilita a složitostmodeluExistuje dokonalýmodel?Základní otázkaPožadavky na model zhlediska MLTestovací dataChyba na trénovacích atestovacích datechShrnutí

Závěr


Existuje dokonalý model?

Návaznosti

Data mining

Strojové učení


Závěr


Dokonalý model,

✔ jehož struktura by umožňovala popsat jakýkoli koncept, jakoukoli relaci, ...,✔ neexistuje.

Je možné hledat správný model v prostoru všech možných myslitelných modelů?

✔ Velikost prostoru modelů roste exponenciálně, často je nekonečný — výpočetněneúnosné.

✔ Obrovské nároky na počet trénovacích dat.

Obvyklý přístup:

✔ Zvolíme omezenou třídu modelů (omezený prostor hypotéz).✔ V této třídě hledáme nejlepší model.✔ Tento model je ale už z principu zaujatý (inductive bias).

Co je nejlepší model? Dvě (obvykle protichůdná) kritéria:

✔ správnost (přesnost, minimální chyba) a✔ jednoduchost.

Jak je vyvážit???

Základní otázka

Návaznosti

Data mining

Strojové učení


Závěr


Co je dobrým ukazatelem „kvality“ modelu z hlediska DM?

✔ Při regresních úlohách se často aplikuje tzv. střední kvadratická chyba (mean squarederror):

MSE =1N

N

∑i=1

(yi − f (xi))2 , (1)

kde f je pro nás modelem, f (xi) je predikce modelu pro i. objekt x (zde reálnéčíslo).

✔ Je tato veličina (měřená na datech, která máme k dispozici — na trénovacíchdatech) dobrým ukazatelem kvality modelu?

Který model je lepší?

Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−1

−0.5

0

0.5

1

1.5

2

2.5

3f(x) = x

f(x) = x3−3x2+3x


Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−1

−0.5

0

0.5

1

1.5

2

2.5

3f(x) = x

f(x) = x3−3x2+3x

Z hlediska MSE jsou oba modely ekvivalentní!!! Je tedy jedno, který použijeme?


Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−1

−0.5

0

0.5

1

1.5

2

2.5

3f(x) = x

f(x) = x3−3x2+3x

Z hlediska MSE jsou oba modely ekvivalentní!!! Je tedy jedno, který použijeme?Lineární model je jednodušší!


Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−0.5

0

0.5

1

1.5

2

2.5f(x) = −0.09 + 0.99x

f(x) = 0.00 + (−0.31x) + (1.67x2) + (−0.51x3)


Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−0.5

0

0.5

1

1.5

2

2.5f(x) = −0.09 + 0.99x

f(x) = 0.00 + (−0.31x) + (1.67x2) + (−0.51x3)

Z hlediska MSE je kubický model lepší než lineární!!!


Návaznosti

Data mining

Strojové učení


Závěr


−0.5 0 0.5 1 1.5 2 2.5−0.5

0

0.5

1

1.5

2

2.5f(x) = −0.09 + 0.99x

f(x) = 0.00 + (−0.31x) + (1.67x2) + (−0.51x3)

Z hlediska MSE je kubický model lepší než lineární!!!Přesto může být lepší použít jednodušší lineární model.

Máme ovšem málo dat, těžko soudit.

Požadavky na model z hlediska ML

Návaznosti

Data mining

Strojové učení


Závěr


✔ Specifika procesu učení s ohledem na využití ML modelu, např. v DM:

✘ Model musí být užitečný při predikci

✘ Schopnost generalizace: model musí nalézt obecně platné závislosti v datech

✘ Nesmí být přeučený: nesmí se naučit na zdánlivé závislosti v datech nebo na šum

✔ Základní metodou pro omezení přeučení je ověření modelu na nezávislých, tzv.testovacích datech

Testovací data

Návaznosti

Data mining

Strojové učení


Závěr


X ∼ U(0, 10)

Y ∼ (X − 3)2 + N(0, 62)

0 2 4 6 8 10−20

−10

0

10

20

30

40

50

60

Trenovaci MSE: 131.87Testovaci MSE: 426.96

Polynom 0−teho stupne

Testovací data

Návaznosti

Data mining

Strojové učení


Závěr


X ∼ U(0, 10)

Y ∼ (X − 3)2 + N(0, 62)

0 2 4 6 8 10−20

−10

0

10

20

30

40

50

60



Chyba na trénovacích a testovacích datech

Návaznosti

Data mining

Strojové učení


Závěr


0 1 2 3 4 5 610

1

102

103

Slozitost modelu

MS

E

Trenovaci MSETestovaci MSE

✔ Chyba na trénovacích datech se snižuje se vzrůstající flexibilitou modelu

✔ Chyba na testovacích datech je pro určitou flexibilitu modelu minimální

Shrnutí

Návaznosti

Data mining

Strojové učení


Závěr


✔ Dva extrémy flexibility modelu

1. Málo flexibilní model (jednoduchý model)

✘ Model je silně vychýlen, zaujat (biased)

✘ Model je stabilní (vzhledem ke změně trénovací množiny)

2. Moc flexibilní model (složitý model)

✘ Velice přesný model (trénovacích dat)

✘ Model je velice citlivý (na změnu trénovací množiny)

✔ Model, který je „nejblíž skutečnosti“, se nachází někde mezi nimi

✔ Chybu, kterou model bude dělat na nových neznámých datech (pocházejících zestejného zdroje), lze odhadnout chybou na testovacích datech

✔ Chybu na testovacích datech lze využít i pro volbu vhodné struktury modelu

Závěr

Návaznosti

Data mining

Strojové učení


ZávěrShrnutíReference


Shrnutí

Návaznosti

Data mining

Strojové učení




✔ DM (či KDD) se dá chápat jako mnohastupňový proces tvorby modelů strojovéhoučení a jejich nasazování do praxe.

✔ Umělá inteligence se zabývá tvorbou umělých entit s inteligentním chováním.

✔ Strojové učení je podobor umělé inteligence, který studuje algoritmy umožňujícístrojům učit se.

✔ Rozpoznávání je podoblast strojového učení, kde se studují modely umožňujícírozeznat určitou situaci nebo jev a zareagovat na ni.

✔ Mezi hlavní úlohy řešené v rámci strojového učení patří klasifikace, regrese,shlukování a odhad pravděpodobnostního rozdělení.

✔ Základní metodou pro zajištění kvality naučeného modelu je ověření jeho funkcena nových, tzv. testovacích datech.

Reference

Návaznosti

Data mining

Strojové učení




[FSM92] W. J. Frawley, Piatetsky G. Shapiro, and C. J. Matheus. Knowledge discoveryin databases - an overview. AI Magazine, 13:57–70, 1992.

[McC04] John McCarthy. What is Artificial Intelligence.http://www-formal.stanford.edu/jmc/whatisai/whatisai.html, 2004.


Data miningDefiniceRozdílné pohledy na dataÚcel DMZdroje DMTypy úloh rešených pomocí DMDM jako proces: CRISP-DM

Strojové uceníAI, ML, PRRozpoznáváníUcení jako indukce modeluUcení s ucitelem a bez uciteleDruhy úloh

Flexibilita a složitost modeluExistuje dokonalý model?Základní otázkaKterý model je lepší?Který model je lepší?Požadavky na model z hlediska MLTestovací dataTestovací dataTestovací dataTestovací dataTestovací dataTestovací dataTestovací dataChyba na trénovacích a testovacích datechShrnutí

ZáverShrnutíReference

Date post:	20-Oct-2020
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

1. Data mining. Strojové ucenˇ í. Základní úlohy. Ucenˇ í s uciˇ ......DM jako proces:...

Documents