Professional Documents
Culture Documents
Cy quyt nh
Bi:
Wiki Pedia
Trong l thuyt quyt nh (chng hn qun l ri ro), mt cy quyt nh (ting Anh:
decision tree) l mt th ca cc quyt nh v cc hu qu c th ca n (bao gm
ri ro v hao ph ti nguyn). Cy quyt nh c s dng xy dng mt k hoch
nhm t c mc tiu mong mun. Cc cy quyt nh c dng h tr qu trnh
ra quyt nh. Cy quyt nh l mt dng c bit ca cu trc cy.
Cy quyt nh
Cc kiu cy quyt nh
Cy quyt nh cn c hai tn khc:
Cy hi quy (Regression tree) c lng cc hm gi c gi tr l s thc thay v c
s dng cho cc nhim v phn loi. (v d: c tnh gi mt ngi nh hoc khong thi
gian mt bnh nhn nm vin)
Cy phn loi (Classification tree), nu y l mt bin phn loi nh: gii tnh (nam hay
n), kt qu ca mt trn u (thng hay thua).
V d thc hnh
Ta s dng mt v d gii thch v cy quyt nh:
David l qun l ca mt cu lc b nh golf ni ting. Anh ta ang c rc ri chuyn
cc thnh vin n hay khng n. C ngy ai cng mun chi golf nhng s nhn vin
cu lc b li khng phc v. C hm, khng hiu v l do g m chng ai n chi,
v cu lc b li tha nhn vin.
Mc tiu ca David l ti u ha s nhn vin phc v mi ngy bng cch da theo
thng tin d bo thi tit on xem khi no ngi ta s n chi golf. thc hin
iu , anh cn hiu c ti sao khch hng quyt nh chi v tm hiu xem c cch
gii thch no cho vic hay khng.
Vy l trong hai tun, anh ta thu thp thng tin v:
Tri (outlook) (nng (sunny), nhiu my (clouded) hoc ma (raining)). Nhit
(temperature) bng F. m (humidity). C gi mnh (windy) hay khng.
V tt nhin l s ngi n chi golf vo hm . David thu c mt b d liu gm
14 dng v 5 ct.
2/6
Cy quyt nh
3/6
Cy quyt nh
4/6
Cy quyt nh
Cc cng thc
Gini impurity
Dng trong thut ton CART (Classification and Regression Trees). N da vo vic
bnh phng cc xc sut thnh vin cho mi th loi ch trong nt. Gi tr ca n tin
n cc tiu (bng 0) khi mi trng hp trong nt ri vo mt th loi ch duy nht.
Gi s y nhn cc gi tr trong {1, 2, ..., m} v gi f(i,j) l tn xut ca gi tr j trong nt
i. Ngha l f(i,j) l t l cc bn ghi vi y=j c xp vo nhm i.
Entropy
Dng trong cc thut ton sinh cy ID3, C4.5 v C5.0. S o ny da trn khi nim
entropy trong l thuyt thng tin (information theory).
u im ca cy quyt nh
So vi cc phng php khai ph d liu khc, cy quyt nh l phng php c mt
s u im:
Cy quyt nh d hiu. Ngi ta c th hiu m hnh cy quyt nh sau khi
c gii thch ngn.
Vic chun b d liu cho mt cy quyt nh l c bn hoc khng cn thit.
Cc k thut khc thng i hi chun ha d liu, cn to cc bin ph
(dummy variable) v loi b cc gi tr rng.
Cy quyt nh c th x l c d liu c gi tr bng s v d liu c gi tr l
tn th loi. Cc k thut khc thng chuyn phn tch cc b d liu ch
gm mt loi bin. Chng hn, cc lut quan h ch c th dng cho cc bin
tn, trong khi mng n-ron ch c th dng cho cc bin c gi tr bng s.
5/6
Cy quyt nh
6/6