Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Adatb´any´any´aszati m´odszerek ´ Illy´es Agota BME, Budapest
BME, Budapest, 2012.m´arcius 1.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Adatb´any´aszati (data mining) algoritmusokat az adatb´azisb´ol t˝ort´en˝o tud´asfelt´ar´as (knowledge discovery in databases) sor´an alkalmaznak. A tud´askinyer´es adatb´azisokb´ ol egy olyan folyamat, melynek sor´an ´erv´enyes, u ´jszer˝ u, lehet˝ oleg hasznos ´es v´egs˝o soron ´erthet˝o mint´akat fedez¨ unk fel az adatokban.
Klaszterez´es ´es k¨ ul¨ onc pontok keres´ese ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Megnevez´esek tiszt´az´asa
Regresszi´o vagy el˝ orejelz´es (predikci´ o) a v´altoz´ ot intervallum sk´al´an m´erj¨ uk
Oszt´alyoz´as vagy klasszifik´aci´ o (csoportba sorol´as) a v´altoz´ o diszkr´et ´ert´ekk´eszlet˝ u
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Adatb´anyaszatban alkalmazott el˝orejelz˝o ´es klasszifik´al´o m´odszerek
Legk¨ozelebbi szomsz´ed m´ odszerek Line´aris ´es logisztikus regresszi´ o Mesters´eges neur´alis h´al´ ozatok D¨ont´esi szab´alyok, sorozatok ´es f´ak Naiv Bayes klasszifik´aci´ o ´es Bayes h´al´ ozatok SVM Metaalgoritmusok (boosting, bagging, randomization, stb.)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
El˝orejelz˝o vagy klasszifik´al´o m´odszerek tulajdons´agai el˝orejelz´es teljes´ıtm´enye: milyen ´ert´ekes inform´aci´ot ad sz´amunkra a modell a nem megfigyelhet˝ o magyar´az´o v´altoz´or´ol gyorsas´ag: a modell el˝ o´all´ıt´as´anak ´es haszn´alat´anak id˝oig´enye robusztuss´ag: ´erz´ekeny-e a modell hi´anyz´ o, vagy outlier(beavatatlan) adatokra sk´al´azhat´os´ag: haszn´alhat´ o-e a modell nagyon nagy adathalmazokra is? ´ertelmezhet˝os´eg: kinyerthet¨ unk-e az emberek sz´am´ara ´ertelmezhet˝o tud´ast a modell bels˝ o szerkezet´eb˝ol? sk´ala-invariancia: a klaszterez´es lehetetlens´eg-elm´elet´et adapt´alva sk´ala-invari´ansnak h´ıvunk egy oszt´alyz´o elj´ar´ast, ha a m´odszer kimenete nem v´altozik, ha tetsz˝ oleges intervallum t´ıpus´ u magyar´az´o v´altoz´ o helyett annak α > 0-szoros´at vessz¨ uk. ´ Illy´ es Agota Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Az elj´ar´asok minimum k´et l´epcs˝ oben m˝ uk¨ odnek: tan´ıt´o adatb´azison fel´ep´ıtj¨ uk a modellt Alkalmazzuk a modellt u ´j adatokra, amelyen a magyar´azott v´altoz´o ´ert´eke nem ismert, de ismerni szeretn´enk
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Az oszt´alyoz´as ´es a regresszi´o feladata Az oszt´alyoz´as ´es regresszi´ o sor´an n-esekkel (tuple) fogunk foglalkozni, amelyeket objektumoknak vagy elemeknek h´ıvunk. Adott lesz objektumok sorozata (vagy zs´akja), amelyet tan´ıt´o mint´aknak, tan´ıt´o pontoknak, tan´ıt´ o halmazoknak (ugyanaz az objektum t¨obbsz¨or is szerepelhet most ezekben a halmazokban) nevez¨ unk. A tan´ıt´o pontok sz´ama m vagy |τ | jel¨ olj¨ uk ´es val´ oj´aban tan´ıt´asra a tan´ıt´o pontok egy r´esz´et haszn´aljuk, a t¨ obbi pont szerepe a tesztel´es. Az n-es j-edik elem´et j-edik attrib´ utumnak h´ıvjuk ´es egy attrib´ utumra n´evvel is hivatkozhatunk (pl. kor, magass´ag, sz´eless´eg attrib´ utumok), nem csak sorsz´ammal. Minden attrib´ utumnak saj´at ´ert´ekk´eszlete van. ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Oszt´ alyoz´ as ´ es regresszi´ o
Az oszt´alyoz´as ´es a regresszi´o feladata Az A attrib´ utumv´altoz´ on olyan v´altoz´ ot ´ert¨ unk, amely az A ´ert´ekk´eszlet´eb˝ol vehet fel ´ert´ekeket. ´ anos m´odon egy klasszifik´aci´ Altal´ o vagy el˝ orejelz˝ o m´odszer teljes´ıtm´eny´et v´arhat´o hasznoss´ag´aval m´erhetj¨ uk. Y-magyar´azand´o attrib´ utumv´altoz´ o X-magyar´az´o attrib´ utumv´altoz´ o(k) f az X ´ert´ekkeszletr˝ ol az Y ´ert´ekkeszletre k´epez C´elunk a E [U(Y , f (X ))] maximiz´al´asa, ahol U(y , yˆ ) jel¨oli az el˝orejelzett yˆ hasznoss´ag´at vagy E[L(Y , f (X ))] minimiz´al´asa, ahol L az U inverze, egy vesztes´eget m´er˝o f¨ uggv´eny, ezt v´arhat´ o oszt´alyoz´asi hib´anak nevezik ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Els˝o defin´ıci´o
Az A attrib´ utumhalmaz felett ´ertelmezett d¨ ont´esi szab´aly alatt olyan R : φ(A) → Y = y logikai implik´aci´ot ´ert¨ unk, amelyek felt´etelr´esz´eben attrib´ utumokra vonatkoz´o felt´etelek logikai kapcsolatai ´allnak, a k¨ ovetkezm´enyr´eszben pedig az oszt´alyattrib´ utumra vonatkoz´ o ´ıt´elet.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
P´elda: ˝ ERS ´ EKLET ´ ´ = nincs → IDO ˝ JAT ´ EKRA ´ HOM = magas AND SZEL alkamas P´elda val´osz´ın˝ us´egi d¨ont´esre: nem = f´erfi AND gyerek sz´ama = 0 AND aut´ o teljes´ıtm´eny > 150LE → kock´azatos = (80%,20%)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
a felt´etelr´eszben az AND, OR ´es neg´aci´ ot haszn´aljuk fel tetsz˝olegesen gyakorlatban csak olyan szab´alyokkal foglalkoznak, amelyben egy alapfelt´etel neg´aci´ oja, a felt´etelek ´es kapcsolatai szerepelnek a szab´alyok felt´etelr´esz´eben diszjunkt´ıv norm´al formul´ak ´allnak, ha az azonos k¨ ovetkezm´enyr´esszel rendelkez˝o szab´alyokb´ol egy szab´alyt k´esz´ıt¨ unk, u ´h. a felt´etelek vagy kapcsolat´at k´epezz¨ uk minden formula ´at´ırhat´ o diszjunkt´ıv norm´al formul´av´a a dupla neg´aci´o elimin´al´as´aval, a de Morgan ´es a disztributivit´as szab´aly alkalmaz´as´aval
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
M´asodik defin´ıci´o
Az R : φ(A) → Y = y szab´alyra illeszkedik a t objektum, ha a felt´etelr´esz attrib´ utumv´altoz´ oiba a t megfelel˝ o ´ert´ekeit helyettes´ıtj¨ uk, akkor igaz ´ert´eket kapunk. Ha a szab´aly k¨ovetkezm´enye is igaz, az objektumon ⇒ a szab´aly fenn´all vagy igaz az objektumon
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Harmadik defin´ıci´o
Az R : φ(A) → Y = y lefedi a T objektumhalmazt, ha minden objektum illeszkedik a szab´alyra. Adott τ tan´ıt´ohalmaz eset´en az R ´altal fedett tan´ıt´ opontok halmaz´at coverτ (R)-rel jel¨olj¨ uk. az R szab´aly helyesen fedi a T halmazt, ha R fedi T-t ´es a halmaz ¨osszes objektuma az y oszt´alyba tartozik a coverτ+ (R) az R ´altal helyesen fedett pontok halmaza a coverτ− (R) az R ´altal helytelen¨ ul fedett pontok halmaza
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Negyedik defin´ıci´o
Az R szab´aly relat´ıv fed´esi hib´aja megegyezik a rosszul oszt´alyozott pontok sz´am´anak a tan´ıt´ opontokhoz vett ar´any´aval, teh´at:
Er τ (R) =
´ Illy´ es Agota
coverτ− (R) coverτ (R)
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje
T´ıpusai: ´It´eletkalkulus-alap´ u d¨ ont´esi szab´alyok a felt´etelr´esz´eben predik´atumok logikai kapcsolata ´all (´ıt´eletkalkulus egy formul´aja, amelyben nem szerepelnek a → ´es ↔ m˝ uveleti jelek) -minden predik´atum egy attrib´ utumra vonatkozik -ha az attrib´ utum kateg´ oria t´ıpus´ u ⇒ A = a vagy a ∈ A alak´ u a felt´etel, ahol a-konstans A -A-az A ´ert´ekk´eszlet´enek egy r´eszhalmaza
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje
-sorrend vagy intervallum t´ıpus´ u attrib´ utum eset´en emellett A ≤ a 0 00 ´es a ≤ A ≤ a szab´alyokat is megenged¨ unk -az algoritmusok t¨obbs´ege csak olyan egyszer˝ u formul´akat tud el˝o´all´ıtani, amelyekben a predik´atumok ´es kapcsolatai ´allnak (pl. ´ ≤ 170 AND HAJSZ´IN = barna AND SZEMSZ´INE ∈ MAGASSAG {k´ek, z¨old} -a csak ´ıt´eletkalkulus alap´ u szab´alyokat tartalmaz´ o d¨ont´esi szab´alyokat/f´akat univariate (egyv´altoz´ os) d¨ ont´esi szab´alyoknak/f´aknak h´ıvjuk.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje Rel´aci´o-alap´ u d¨ont´esi szab´alyok -ha halmazelm´eleti szemmel n´ezz¨ uk a predik´atumokat, akkor az attrib´ utumokra vonatkoz´ o predik´atumot bin´aris rel´aci´onak nevezz¨ uk, amelynek egyik tagja egy v´altoz´ o, m´asik pedig egy konstans -a rel´aci´o alap´ u d¨ ont´esi szab´alyokban a m´asodik tag attrib´ utumv´altoz´o is lehet -itt pl a hajsz´ın = szemsz´ın vagy sz´eless´eg < magass´ag megengedett felt´etelek -a rel´aci´o-alap´ u szab´alyokat tartalmaz´ o d¨ ont´esi szab´alyokat/f´akat multivariate (t¨ obbv´altoz´ os) d¨ont´esi szab´alyoknak/f´aknak h´ıvjuk ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje
egyes esetekben a rel´aci´ os szab´aly helyettes´ıthet˝o sok egyv´altoz´os szab´alyp´arral P´elda: hajsz´ın = barna AND szemsz´ın = barna, hajsz´ın = k´ek AND szemsz´ın = k´ek, hajsz´ın = m´alyva AND szemsz´ın = m´alyva
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje
Indukt´ıv logikai programoz´as P´elda: ´ep´ıt˝oelemek egy kupaca legyen egy torony -a legfels˝o eleme a cs´ ucs, a marad´ek elemre pedig a marad´ek attrib´ utummal hivatkozunk -ha a sz´eless´eg < magass´ag, akkor ALAK = ´all´o ⇒ sz´eless´eg(´ep´ıt˝oelem) < magass´ag(´ep´ıt˝ oelem) → ´all´o(´ep´ıt˝oelem)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi szab´alyok kifejez˝oereje
-s˝ot tov´abb is bonyol´ıthatjuk a szab´alyt P´elda: sz´eless´eg(torony.cs´ ucs) < magass´ag(torony.cs´ ucs) AND ´all´o(torony.marad´ek) → ´all´ o(torony) -ez a rekurz´ıv kifejez´es, amely szerint egy torony akkor ´all´o, amikor a legfels˝o elem magass´aga nagyobb mint sz´eless´ege -a rekurzi´ot le kell z´arni: torony = u ¨res → ´all´ o(torony) -a rekurz´ıv szab´alyoknak nagyobb a kifejez˝ oerej¨ uk, mint a rel´aci´o-alap´ u d¨ont´esi szab´alyhalmazoknak -a rekurz´ıv szab´alyokat is tartalmaz´ o szab´alyhalmazt logikai programnak nevezz¨ uk, ezekkel tov´abbiakban nem foglalkozunk.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Szab´alyhalmazok ´es szab´alysorozatok
halmazok eset´en a szab´alyok f¨ uggetlenek egym´ast´ol a szab´alyhalmaz trivi´alis, ha tetsz˝ oleges objektum csak egy szab´alyra illeszkedik sorozat eset´eben egy u ´j objektum oszt´alyattrib´ utum´anak j´osl´as´an´al egyes´evel sorra vessz¨ uk a szab´alyokat eg´eszen addig, am´ıg olyat tal´alunk, amelyre illeszkedik az objektum ennek a szab´alynak a k¨ ovetkezm´enyr´esze adja meg az oszt´alyattrib´ utum ´ert´ek´et
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
egy szab´alyrendszer (halmaz vagy sorozat) teljes, ha tetsz˝oleges objektum illeszthet˝ o egy szab´alyra sorozatok eset´eben a teljess´eget ´altal´aban az utols´o, u ´n. alap´ertelmezett szab´aly biztos´ıtja, amely felt´etelr´esze u ¨res ⇒ minden objektum illeszkedik r´a a szab´alyok k¨oz¨otti sorrend (priorit´as) biztos´ıt´as´aval ker¨ ulj¨ uk el azt, hogy ha egy objektumra t¨ obb , k¨ ul¨ onb¨oz˝o k¨ovetkezm´enyr´esszel rendelkez˝ o szab´aly illeszkedik a priorit´as nem minden esetben kedvez˝ o! szab´alyhalmaz eset´eben minden szab´aly tud´asunk egy t¨ored´ek´et r¨ogz´ıti sorozatok eset´en egy szab´alyt nem emelhet¨ unk ki a k¨ornyezet´eb˝ol ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Szab´alyhalmazok ´es szab´alysorozatok
a szab´alyok sorozata ´at´ırhat´ o szab´alyok halmaz´aba u ´gy, hogy egyes´evel vessz¨ uk a szab´alyokat az els˝ ot˝ ol ´es a felt´etelr´eszhez hozz´af˝ozz¨ uk az el˝ otte ´all´ o szab´alyok felt´etelr´esz neg´altjainak kapcsolat´at
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi t´abl´azatok
minden oszlopa egy attrib´ utumnak felel meg, az utols´o oszlop viszont az oszt´alyattrib´ utumnak az A attrib´ utumhoz tartoz´ o oszlopban az A ´ert´ek´ere vonatkoz´o felt´etel szerepelhet, leggyakrabban A=a alakban (´ıt´eletkalkulus-alap´ u d¨ ont´esi szab´aly) a t´abl´azat egy sora egy d¨ ont´esi szab´alyt r¨ ogz´ıt ha az attrib´ utumok a sorban szerepl˝ o felt´eteleket kiel´eg´ıtik, akkor az oszt´alyattrib´ utum ´ert´eke megegyezik a sor utols´o elem´enek ´ert´ek´evel
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi t´abl´azat
id˝oj´ar´as napos napos bor´ us es˝os es˝os es˝os es˝os
h˝om´ers´eklet meleg meleg meleg enyhe hideg hideg hideg
p´aratartalom magas magas magas magas magas magas magas
´ Illy´ es Agota
sz´el nincs van nincs nincs nincs nincs nincs
j´at´ekid˝o nem nem nem igen igen igen igen
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
D¨ont´esi t´abl´azat egy d¨ont´esi t´abl´azat tulajdonk´eppen egy speci´alis d¨ont´esi szab´alyhalmaz, amelyre igaz, hogy a felt´etelr´eszben pontosan ugyanazok az attrib´ utumok szerepelnek k´erd´esek tiszt´az´asa: 1
az attrib´ utumok melyik r´eszhalmaz´at ´erdemes kiv´alasztani? ide´alis eset, ha minden r´eszhalmazt ki tudn´ank ´ert´ekelni ´es kiv´alasztani azt, amelyik a legkisebb hib´at(rosszul oszt´alyozott tan´ıt´ opontok sz´ama) adja a gyakorlatban az attrib´ utumok sz´ama nagy, ez´ert az ¨osszes r´eszhalmaz kipr´ ob´al´asa sok id˝ o
2
hogyan kezelj¨ uk a folytonos attrib´ utumkat? az el˝ oz˝ o p´eld´aban a h˝ om´ers´ekletet diszkretiz´altuk ide´alis az lenne, ha a folytonos attrib´ utumokat az algoritmus automatikusan tudn´a diszkretiz´alni ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
Az 1R algoritmus
-kiv´alaszt egy attrib´ utumot ´es az oszt´alyoz´asban kiz´ar´olag ezt haszn´alja -annyi szab´alyt ´all´ıt el˝ o, ah´any ´ert´eket felvesz a kiv´alasztott attrib´ utum a tan´ıt´ohalmazban -az A=a → Y=c szab´aly k¨ ovetkezm´enyr´essz´eben szerepl˝o c oszt´aly a legt¨obbsz¨or elofordul´ o oszt´aly az A attrib´ utum´aban a ´ert´eket felvev˝o tan´ıt´omint´ak k¨ oz¨ ul -nyilv´anval´o, hogy 1R egy´ertelm˝ u szab´alyhalmazt ´all´ıt el˝o
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
-minden attrib´ utum´ert´ekhez meg tudjuk hat´arozni a rosszul oszt´alyozott tan´ıt´opontok sz´am´at -oszt´alyoz´o attrib´ utumnak v´alasztjuk a legkevesebb rosszul oszt´alyozott tan´ıt´opontot ad´ o attrib´ utumot -hi´anyz´o attrib´ utumokat u ´gy kezel¨ unk, mintha lenne az attrib´ utumnak egy k¨ ul¨ onleges, a t¨ obbit˝ ol elt´er˝ o ´ert´eke -sorrend ´es intervallum t´ıpus´ u attrib´ utumn´al A≤ a, a’≤ A ≤ a” ´es a”’≤ A t´ıpus´ u szab´alyokat c´elszer˝ u el˝ o´all´ıtani -ehhez csoportos´ıtjuk az egym´ast k¨ ovet˝ o ´ert´ekeket , u ´h homog´en csoportok legyenek az oszt´aly´ert´ek szempontj´ab´ ol (vagyis diszkretiz´aljuk)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Defin´ıci´ ok Szab´ alyhalmazok ´ es szab´ alysorozatok D¨ ont´ esi t´ abl´ azatok Az 1R algoritmus
-az 1R m´odszer nem t´ ul bonyolult ´es egyes esetekben nagyon is pontos -van 0R oszt´alyz´o attrib´ utum is, amely nem haszn´al fel egyetlen attrib´ utumot sem -ebben az esetben az oszt´alyoz´ o egy felt´etel n´elk¨ uli szab´aly, amely ´ıt´eletr´esz´eben a leggyakoribb oszt´aly ´all
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi f´ak alap¨otlet: bonyolult ¨ osszef¨ ugg´esek egyszer˝ u d¨ont´esek sorozat´ara vezet vissza. a fa gy¨oker´eeb˝ol kiindulva haladunk lefele a csom´opontokon kereszt¨ ul ´es a csom´ opontokban feltett k´erd´esekre adott v´alaszoknak megfelel˝ oen addig l´epked¨ unk, am´ıg egy lev´elbe nem ´er¨ unk. a d¨ont´est a lev´el cimk´eje hat´arozza meg. a d¨ont´esi f´ak nagy el˝ onye, hogy automatikusan felismerik a l´enyegtelen v´altoz´ okat. Ha egy v´altoz´ or´ ol nem nyerhet˝o inform´aci´o az adott v´altoz´ or´ ol, akkor azt nem is tesztelik. az´ert el˝ony¨os ez a tulajdons´ag, mert ´ıgy a f´ak teljes´ıtm´enye zaj jelenl´et´eben sem romlik, a probl´emameg´ert´es¨ unket is nagyban seg´ıti, ha megtudjuk, hogy mely v´altoz´ok fontosak, ´es melyek nem. ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
a legfontosabb v´altoz´ okat a fa a gy¨ ok´er k¨ ozel´eben teszteli. M´asik el˝ony, hogy a d¨ ont´esi f´ak nagym´eret˝ u adathalmazokra is hat´ekonyan fel´ep´ıthet˝ ok. a d¨ont´esi f´ak egyik fontos tulajdons´aga, hogy egy csom´opontnak mennyi gyereke lehet. egy olyan fa, amely pontjainak kett˝ on´el t¨ obb gyermeke is lehet, mindig ´abr´azolhat´ o bin´aris f´aval. a legt¨obb algoritmus ez´ert csak bin´aris f´at tud el˝o´all´ıtani.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi fa hitelb´ır´alatra (Bodon Ferenc)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi f´ak ´es d¨ont´esi szab´alyok
a d¨ont´esi f´ak tulajdons´aga, hogy a gy¨ ok´erb˝ ol egy lev´elbe vezet˝o u ´t ment´en a felt´eteleket ¨ osszeolvasva k¨onnyen ´ertelmezhet˝o szab´alyokat kapunk a d¨ ont´es meghozatal´ara, illetve egy laikus sz´am´ara is ´erthet˝ o m´ odon azt is meg tudjuk magyar´azni, hogy a fa mi´ert pont az adott d¨ ont´est hozta. a d¨ont´esi f´akb´ol nyert d¨ ont´esi szab´alyhalmazok egy´ertelm˝ uek. Ez trivi´alis, hiszen tetsz˝ oleges objektumot a fa egy´ertelm˝ uen besorol valamelyik lev´elbe, a lev´elhez tartoz´ o szab´alyra az objektum illeszkedik, a t¨ obbi nem.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Vannak olyan d¨ont´esi feladatok, amikor a f´ak t´ ul bonyolult szab´alyokat ´all´ıtanak el˝ o, pl.: n´egy bin´aris magyar´az´ o attrib´ utum: A, B, C , D az oszt´alyattrib´ utum is bin´aris ´es Y -nal jel¨ olj¨ uk a d¨ont´esi szab´alysorozat 3 szab´alyb´ ol ´all: A = 1 AND B = 1 → Y = 1 C = 1 AND D = 1 → Y = 1 Y =0
Ekkor a szab´alysorozat teljes, hisz az utols´ o, felt´etel n´elk¨ uli szab´alyra minden objektum illeszkedik. A fenti p´eld´aban a fa az oszt´alyoz´as bonyolultabb le´ır´as´at adja, mint a szab´alysorozat.
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
a s´arga ´es k´ek r´eszf´ak izomorfak a r´eszfa ´altal adott oszt´alyoz´ast egyszer˝ uen tudjuk kezelni a d¨ont´esi szab´alysorozattal, de a r´eszf´ak ism´etelt felrajzol´asa nem elker¨ ulhet˝o d¨ ont´esi f´ak eset´eben. ez egy alapprobl´ema, neve ism´etl˝ od˝ o r´eszfa probl´ema (replicated subtree problem)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi fa el˝o´all´ıt´asa a f´at a tan´ıt´o adatb´azisb´ ol rekurz´ıvan ´all´ıtjuk el˝o kiindulunk a teljes adatb´azisb´ ol ´es egy olyan k´erd´est keres¨ unk, aminek seg´ıts´eg´evel a teljes tanul´ ohalmaz j´ ol sz´etv´aghat´o egy sz´etv´ag´as j´o, ha a magyar´azand´ o v´altoz´ o eloszl´asa a keletkezett r´eszekben kev´esb´e sz´ ort, kev´esb´e bizonytalan, mint a sz´etv´ag´as el˝ott egyes algoritmusban a keletkez˝ o r´eszek kb egyform´ak a r´eszekre rekurz´ıvan alkalmazzuk a fenti elj´ar´ast egy csom´opont lesz´armazottjaiban nem vizsg´aljuk t¨obb´e azt az attributumot, ami alapj´an sz´etosztjuk a mint´at
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Ism´etl˝od˝o r´eszfaprobl´ema
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
A rekurzi´ot megszak´ıtjuk, ha: nincs t¨obb attrib´ utum, ami alapj´an az elemeket tov´abboszthatn´ank a csom´oponthoz tartoz´ o oszt´aly ekkor az lesz, amelyikhez a legt¨obb tan´ıt´opont tartozik az adott m´elys´eg el´ert egy megadott korl´atot nincs olyan v´ag´as, amely jav´ıtani tudna az aktu´alis oszt´alyon Minden lev´elhez hozz´a kell rendeln¨ unk a magyar´azand´o v´altoz´o egy ´ert´ek´et, a d¨ont´est Ez ´altal´aban az u ´n. t¨obbs´egi szavaz´as elve alapj´an t¨ort´enik, az lesz a d¨ont´es, amely kateg´ ori´aban a legt¨ obb tan´ıt´ o minta tartozik
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
H´arom f˝o algoritmust eml´ıthet¨ unk meg a d¨ ont´esi f´ak el˝o´all´ıt´as´ara: Interative Dichotomizer 3 (ID 3) csal´ad, jelenlegi v´altozat C 5.0” Classification and Regression Trees (ART 5 ) Chi-squared Automatic Interaction Detection(CHAID)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
ID3 egyik legr´egibb ´es legismertebb algoritmus J. Ross Quinlan fejlesztette ki az algoritmust, ami d¨ont´esi f´akat hoz l´etre (”tanul meg”) a sz´am´ara megadott ”tanul´o” p´eld´ak alapj´an ezeket a f´akat a gy¨ ok´ert˝ ol a levelek fel´e haladva ´ep´ıti fel a val´os ´eletben j´o n´eh´any ilyen probl´em´aval tal´alkozhatunk, ezek valamilyen oszt´alyoz´asi funkci´ ot l´atnak el (pl. betegeket sorolnak kateg´ori´akba a t¨ uneteik alapj´an) alap¨otlet: kiv´alasztunk egy attrib´ utumot, amelynek az ´ert´ek´ere k´ıv´ancsiak vagyunk → ez lesz a c´elf¨ uggv´eny ezek ut´an feltessz¨ uk a k¨ ovetkez˝ o k´erd´est: melyik az a tov´abbi attrib´ utum, amely a legjobban ”meghat´arozza” a c´elf¨ uggv´eny kimeneti ´ert´ek´et a p´eld´ak alapj´an ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
ez lesz a fa gy¨okere ´es ezen attrib´ utumon lehets´eges ´ert´ekei lesznek az ´agak a k¨ovetkez˝o szinten ugyanez a k´erd´es, stb. a tesztattrib´ utum kiv´alaszt´asa az entr´ opia cs¨ okken´es´et alkalmazza ha Y egy l lehets´eges ´ert´eket pi (i = 1, ..., l) val´osz´ın˝ us´eggel felvev˝o val´osz´ın˝ us´egi v´altoz´ o, akkor Y Shanner-f´ e le entr´ opi´aj´an Pl a H(Y ) = H(p1 , . . . , pk ) = − j=1 pj log2 pj az entr´opia az inform´aci´ o-elm´elet k¨ ozponti fogalma
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Felt´etelek a csom´opontokban
az ID3 algoritmus kiv´alasztja a minim´alis felt´eteles entr´opi´aval rendelkez˝o attrib´ utumot ´es annyi gyerekcsom´ opont j¨on l´etre, amennyi ´ert´eket felvesz az attrib´ utum le´all´asi felt´etel: egy ´agat nem v´agunk tov´abb, ha nincs t¨obb vizsg´alhat´o, azaz a fa maxim´alis m´elys´ege = az attrib´ utumok sz´am´aval az ID3 algoritmus nem felt´etlen¨ ul bin´aris f´at ´all´ıt el˝o ha bin´aris fa el˝o´all´ıt´asa a c´el, akkor a magyar´az´o X attrib´ utum t´ıpus´at´ol f¨ ugg˝oen k´etf´ele felt´etelt szok´as l´etrehozni:
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
intervallum t´ıpus´ u attrib´ utumokn´al a c k´et szomsz´edos tan´ıt´o´ert´ek ´atlaga -kateg´oria t´ıpus´ u eset´eben X ⊆ K, ahol K az X ´ert´ekk´eszlet´enek egy r´eszhalmaza az els˝o esetben X felvett ´ert´ekeivel line´aris ar´anyos felt´eteles entr´opi´at kell sz´am´ıtani, a m´asodikban pedig a felvett ´ert´ekek sz´am´aval exponenci´alis sz´am´ ut (ugyanis egy n elem˝ u n halmaznak 2 darab r´eszhalmaza van) ha egy gy¨ok´erb˝ol lev´elig vezet˝ ou ´ton egy attrib´ utumot t¨obbsz¨or is vizsg´alunk (k¨ ul¨ onb¨ oz˝ o konstansokkal), akkor ebben az esetben kapunk j´ o bin´aris d¨ ont´esi f´at (a fa m´elys´ege az attrib´ utumok sz´am´an´al j´ oval nagyobb is lehet)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi f´ak nyes´ese -c´elja, hogy a fel´ep´ıtett f´a kicsit egyszer˝ us´ıts¨ uk -felt´etelezz¨ uk, hogy a fa megtanult olyan esetis´egeket is, amelyek csak a tan´ıt´ohalmazra jellemz˝ o -a nyes´est egy k¨ ul¨on¨os teszthalmazon szok´as elv´egezni -el˝onyes´es: egy intelligens STOP felt´etel -ut´onyes´es: nagy f´at n¨ oveszt¨ unk, majd elkezdj¨ uk azt zsugor´ıtani -a k´et legismertebb ut´ onyes´esi elj´ar´as: a r´eszfa helyettes´ıt´es(subtree replacement): egy bels˝o pontb´ol indul´o, minden u ´tj´aban lev´elig ´er˝ o f´at egyetlen lev´ellel helyettes´ıtj¨ uk a r´eszgr´af felh´ uz´asa(subtree raising)
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
D¨ont´esi f´ak ´abr´azol´asa -a d¨ont´esi f´ak el˝o´all´ıt´asa ut´an k´et fontos k´erd´es szokott megfogalmaz´odni: melyek azok a szab´alyok, amelyek sok tan´ıt´ opontra ´erv´enyesek? (mennyire jelent˝ os az adott lev´el?) a levelek mennyire j´ ol oszt´alyoznak? (mennyire j´o, mennyire igaz a lev´elhez tartoz´ o szab´aly?) -elterjedt m´odszer, hogy minden levelet egy k¨ orcikkely reprezent´al -a k¨orcikkely nagys´aga ar´anyos a lev´elhez tartoz´ o tan´ıt´opontokkal, a sz´ıne pedig a lev´elhez tartoz´ o szab´aly j´ os´ag´at adja meg pl. min´el s¨ot´etebb a sz´ın, ann´al rosszabb az oszt´alyoz´as ar´anya. -hanyag d¨ont´esi f´ak: amelyekben az azonos szinten elhelyezked˝o pontokban ugyanazt az attrib´ utumot vizsg´aljuk ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Bayesi h´al´ozatok Elvek, amire ´ep¨ ulnek a maximum likelihood a Bayes-t´etel A Bayes-t´etel szerint meghat´arozhat´ o a klasszifik´aci´os szab´aly: Jel¨olj¨ uk Yi -vel azt, amikor a klasszifik´aland´ o eset az i-edik oszt´alyba tartozik (Y = yi ) Az elemek megfigyelhet˝o tulajdons´agait az X vektor ´ırja le. Az egyszer˝ us´eg kedv´e´ert a t´eved´es k¨olts´ege legyen minden esetben azonos. Ekkor egy ismeretlen, X tulajdons´ag´ u p´eld´anyt abba az oszt´alyba (i) ´erdemes (optim´alis) sorolni, amelyikre P(Yi |X ) maxim´alis. A Bayes-szab´aly alapj´an: P(X |Yi )P(Yi ) ,Yi ) P(Yi |X ) = P(X P(X ) = P(X ) ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
P(Yi |X ) =
P(X ,Yi ) P(X )
=
P(X |Yi )P(Yi ) P(X )
Yi , amikor a klasszifik´aland´ o eset az i-edik oszt´alyba tartozik X vektor adja az elemek megfigyelhet˝ o tulajdons´agait a t´eved´es k¨olts´ege legyen minden esetben azonos (egyszer˝ us´eg) egy X tulajdons´ag´ u p´eld´anyt abba az oszt´alyba ´erdemes (optim´alis) sorolni, amelyire P(Yi |X ) maxim´alis P(X ) minden i-re konstans → elegend˝ o P(X |Yi )P(Yi )-t maximaliz´alni P(Yi )-t meg tudjuk hat´arozni csak a P(X |Yi )-t kell meghat´arozni
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Na´ıv Bayes h´al´ok a l(2k − 1) darab megbecs¨ ulend˝ o param´eter sz´ama l ∗ k-ra cs¨okken Legyen X,Y ´es Z h´arom val´ osz´ın˝ us´egi v´altoz´ o. Az X felt´etelesen f¨ uggetlen Y-t´ ol adott Z eset´en, ha P(X = xi |Y = yj , Z = zk ) = P(X = xi |Z = zk ) minden lehets´eges xi , yj , zk h´armasra a naiv Bayes-h´al´oban egy oszt´alyon bel¨ ul az attrib´ utumok felt´etelesen f¨ uggetlenek egym´ast´ ol ekkor P(X |Y ) val´ osz´ın˝ us´eg kifejezhet˝ o a P(Xj |Y ) val´osz´ın˝ us´egek szorzatak´ent: P(X1 , X2 |Yi ) = P(X1 |X2 , Yi )P(X2 |Yi ) = P(X1 |Yi )P(X2 |Yi ) magyar´az´o v´altoz´ o eset´ Qekn: P((X1 , X2 , . . . , Xk ) = (x1 , x2 , . . . , xk )|Yi ) = j=1 P(X1 |Yi )P(X2 |Yi ) ´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
Szakirodalom
[1] Bodon Ferenc. Adatb´ any´ aszati algoritmusok. BME, Feb. 2010 [2]http://www.cs.bme.hu/nagyadat/konyvek.html
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
Bevezet˝ o D¨ ont´ esi szab´ alyok D¨ ont´ esi f´ ak Bayesi h´ al´ ozatok
K¨ osz¨ on¨ om a figyelmet!
´ Illy´ es Agota
Adatb´ any´ any´ aszati m´ odszerek
