Luận văn Nghiên cứu các thuật toán cải tiến trong khai thác dữ liệu

24 CHUONG 3-T~PPHO BIEN DONG 3.1.CO sa TOA.NHOC r171.r221 3.1.1.Ngii' tanh cuakhai that dii'li~u Ngucfmhcuakhaithacdfrli~ula bQbakhaini~mV =(0, I, R), trongd60 d~i di~nchot~phfruh~ cacgiaodich,I d~idi~nchomQtt~pcacdanhml,lC,vaR la quanh~nhiphancuacacgiaodichvacacdanhml,lCc6t6nt~itrongcO'saduli~u. Vi v~yR ~0 x I vam6ic~pth~hi~n(0,0ER duQ'cxemla th\lcth~lienquanden mQtgiaodich0E0 vamQtdanhml,lCi EI . 3.1.2.K~tnBi Galois Vaingucanhkhaithacdfrli~uV =(0, I, R), chungtac6haiphepanhx~nhusail: 3.1.2.1.Anh xt;ltum(Jttijpdanhm1jCsangm(Jt tijpgiaodjch .. t : P (I) --+P (0) X f-7 {oEOI\iXEX,(O,X)ER} trongd6P(I) la t~pt6 hQ'Pcacph~ntu cuat~pdanhml,lCIvai Ip(I)I=2III, va p(<9)lat6hQ'pcacph~ntucuat~pgiaodichvai Ip(0)1=21191. 25 T~pdanhill\lC T~pcacgiaodjch t x t(X) Hinh 3.1- Anh x~t fir t~pdaubIDI}Csangt~pgiaodich. 3.1.2.2.Anhxg titm(jttgpgiaodjchsangm(jttgpdanhmlfC.. i : p(O)-+P(I) X 14 {iEIIVxEX,(x,i)E'R} trongd6P(I) la t~pt6 hQ'pcacph~ntll cuat~pdanhml,1CIvai Ip(I)I=2III, va p(0) lat6hQ'pcacph~ntll cuat~pgiaodichvai Ip(0)1=2101. T~pcacgiaodich T~p danh ffil,1C x i (X) Hinh 3.2- Anh x~i fir t~pgiaodichsangt~pdaubIDI}C. 26 3.1.2.3.Nhffngtinhchdtcuacijpanhxgnay.. K@thQ'PhaianhX!;ltrentasec6duQ'chaiphepanhX!;lkhacv6inhungtinhch~thli vi seduQ'cSUd1,mgtrongdinhnghlat~pd6ng. Anh X!;lCit1<\S1,1'k@thQ'pclm hai anh X!;li, t theethu tl,1'nhu sail: Cit=iot: P(I)--+P(O)--+P(I) x I-H(X) ~ i(t(X)) C6thSduQ'cki hi~unhusail:Cil(x) =iot(X) =i(t(X)). T~pdanhm\lC T~pcacglaDdjch t Hinh 3.3- Anh x\l kep Cit. AnhX!;lCti1<\Sl,1'k@thQ'pcuahai anhX!;lt, i theethutl,1'nhusail: CII =toi: P( 0) --+P(I) --+P(0) X ~ i(X) ~ t(i(X)) CothSduQ'cki hi~unhusail:Cli(X) =t0i (X) =t(i (X) ) . T~pcacgiaodich 27 T~pdanhffi\lC t Biob 3.4- Aob x\I kep Crt. Nhii'ngtiOOch~tcoduQ'ctirhaiaOOXI;lkep: (1) I)<;;;;Iz~t(1)):;;;2t(1z) (2) I <;;;;Cit(1) (3) cit(Cit(1)) =cit (1) (4) I) <;;;;Iz ~ cit(1))<;;;;cit(1J (5) Cit(i(O))=i(O) (6) O<;;;;t(1)~I<;;;;i(O) 3.1.3.Djnh nghiatip dong (1') a) <;;;;°z~ i (0) );;2i (°z) (2') O<;;;;Cti(O) (3') Cti(Cti(O))=Cti(O) (4') a) <;;;;°z~Cti(O))<;;;;Cti(OZ) (5') Cti(t(1))=t(1) C~I la t~pdanhm\lCtrongngii'canhkhaithacdii'li~uV la t~pdongkhivachi khi Cit(C)=C. V~yt~pdong006nh~tchuat~pdanhm\lCI duQ'cxacdiOObilngaM XI;lCitchot~pI. Va ki hi~uCit(1) la t~pdongcuaI. TirdiOOnghiatrenchotacachxacdinhdQph6bi~ncoomQt~pdanhm\lCI b~tky thongquadQph6bi~ncuacact~pdongdffxacdinh.DQph6bi~ndochiOOlab~ng v&idQph6bi~ncuat~pdong006OO~tcochuat~pdanhm\lCI naybilngcongthuc: sup(1)=sup(Cit(1)) . 28 3.1.4.Blnh nghiadimt~pdong TagQiC hit~pcact~pdongtrongngil'canhkhaithacdil'li~uV v6'ik6tn6iGalois. C~p(C,s;)lamott~phQ'Pcothut\lvadllQ'Cxemlaclant~pdongdanhml,lCdllQ'Cki hi~uJLc'Va clant~pdongnayg6m2tiOOchAtsau: . T6ntc;timotthutlJ boph~giil'acacthanhph~ntrenclant~pdong,ch~nghc;tn OOllv6'ib~tkyt~pdongC)'C2EJLcthitacoC)s;C2khivachikhi C)£;C2. . T~pconS b~tky cuacact~pdongtrenclanJLcd8ucomotch~ntren(Join) vamotch~ndll6'i(Meet). Join(S) =Cit ( US; ] vaMeet(S)=ns; ~ES ~ES 3.2.BINH NGHiA TAp PHO BIEN BONG Mott~pdanhml,lCX lat~pph6bi6nvakh6ngt6ntc;ti~pchaX' sacchoX c X' va sup(X)=sup(X')thit~pdanhml,lCX dllQ'CgQilat~pph6bi6ndong. Vi dy: V6'icact~pph6bi6ntimdllQ'CtrongBang 2.11thit~pph6bi6n{a,d }va t~p{c,a,d }kh6ngphaila t~pph6bi6ndongvi t6ntc;timot~pph6bi6nIanhan {c,w, a,d }cocungdoph6bi6nla2.Bencc;tnhdod€ dangoo~ thAyt~p{c,w,a, d }chinhlat~pph6bi6ndongvi kh6ngcont~pnaGIanhancungdoph6bi6n. 3.3.cAe TINH CHAT CUATAp PHOBIEN BONGrt3 3.3.1.Tinh chAt1 aiasuX lamott~pdanhml,lCph6bi6nvatAtcacacgiaodichTranscochuat~p danhml,lCX d6ngthaimQigiaodichnaycfingchuat~pdaOOml,lCY :1=0 v6'iY n X =(2)vakh6ngt6ntc;ti~pV' tllangt\lOOllY v6'iY c Y' (conghiala,Y lat~p16'n nh~tcoth@co).Thitacoth@k6tlu~ la t~pX u Y lamott~pph6bi6ndongco sup(Xu Y) =ITransl;vaOOUngt~pph6bi6nchuaX makh6ngchua'Ythikh6ng th@lat~pph6bi6ndong. 29 Ch.mgminh: TacoX lat~pph6bi~nvaTranslatAtcacacgiaodjchcochuaX trongTDB : sup(X)=ITransl2::minSup. MQigiaodjchTransnayclingchuat~pdanhm\lCY : sup(Xu Y) =sup(X) =ITransI2::minSup. vat~pdanhm\lCY nayth6anhii'ngdi~uki~nsau: YnX=0 va;1Y' sacchoY c Y', Y' n X =0 vasup(Xu Y') =sup(Xu Y). R5rangtheedjnhnghlat~pph6bi~ndong(]tren,tad~dangk~tlu~ la : T~pdanhm\lCX kh6nglat~pph6bi~ndong. Vat~pph6bi~nX u Y lat~pph6bi~ndongv6isup(Xu Y) =ITransI(dpcm). Taxetm6tt~pph6bi~n(X u Z), v6i d6ph6bi~nJ3vaZ "#Y sexayra2 twang hqpsau: Truanghap1:n~usup(X)2::sup(Z)thisup(X)2::sup(Z)2::sup(Xu Z) =J3, mataclingcosup(Xu Y) =sup(X)=>sup(Xu Y u Z) =J3, vatak~tlu~nlat~pph6bi~n(X u Z) kh6nglat~pph6bi~n dongduQ'c(theodjnhnghla). Twanghap2 :n~usup(X)<sup(Z)thisup(Xu Z) =J3::;sup(X)< sup(Z), mataclingcosup(Xu Y) =sup(X)=>sup(Xu Y u Z) =J3, vatak~tlu~nlat~pph6bi~n(X u Z) kh6ngla~pph6bi~n dongduQ'c(theodjnhnghIa). Theok~tquatrenlanhungt~p h6bi~nchuaX makh6ngchuaY thikh6ngth~la t~ph6bi~ndong(dpcm). Vi d\l : 30 TrongBang 2.3tanh~nth§ynhfmggiaodichcochuat~pdanhm\lC{ c, a }thi clingchuat~pdanhm\lC{w }.V~ycoth~k~tlu~nlitt~p{c,w, a }litt~pdongvit clingnh~nth§ynhungffip{c,a,t }vit{c,a,d }khongth~litt~pdong. 3.3.2.Tinh chit 2 T~pdanhm\lCX litt~pph6bi~nvitt~pdanhm\lCY v6i Y c X vitsup(Y)=sup(X) thitacoth~kh~ngdinhlitnhfmgt~pph6bi~ndongcochuaY thich~ch~ sechua luonX hoticnhungt~pchichuaY khongchuaX thikhongth~litt~pph6bi~ndong. Ch.mgminh: Giasirco2t~pdanhm\lCX, (Y u Z) litt~pph6bi~nv6iY c X, Z ctX vitsup(Y)= sup(X),tadn phaixet2truanghQ'Psau: Truanghap1: n~usup(Y)2: sup(Z)thi sup(Y)2: sup(Z)2: sup(Yu Z) nhtmgsup(Y)=sup(X)choth§ysup(Xu Y u Z) =sup(Yu Z).V~y(Y u Z) khongth~litt~pph6bi~ndong. Truanghap2 : n~usup(Y)< sup(Z)thi sup(Yu Z):::; sup(Y)< sup(Z) nhtmgsup(Y)=sup(X)choth§ysup(Xu Y u Z) =sup(Yu Z).V~y(Y u Z) khongth~litt~pph6bi~ndong. TheochUngminhtrenthi t~p(Y u Z) khongth~lit t~pph6bi~ndongtrongca2 truanghQ'p(dpcm). Vi d1}: TrongBang 2.11,chungtanh~th§yt~p{c,w, a,t } litt~pph6bi~nv6i dQph6 bi~nlit3,vitt~pcon{a,t }clingcodQph6bi~nlit3.V~ynhfmgt~p{a,t }; {w,a, t }khongth~litt~pdong. 31 3.4.Ap DUNG TiNH CHAT TAP PH6 BIEN DONG TREN CAY FP- ~ 3.4.1.H~qua1( pbathi~nva lo~ibonbanhnhii'ngdaRbmyckhongcAn xet) N~ume>tdanhm1,lCph6bi~nd~uco xu~thi~ntrongnhi~uc~pfJist C1,lCbe>v6'iclIng de>ph6bi~nthi ta co thSlo;;tibe va kh6ngxetd~ndanhm1,lCnaytrongnhungc~p fJist C1,lCbe>tru6'cdo. Chtffigminh : Gia strta co danhm1,lCx xu~thi~nC1,lCbe>& c~pn cuat~pdanhm1,lCti~nt6 Xn co clIngde>ph6bi~nf3&dp m cuat~pdanhm1,lCti~nt6Xmv6'i0 ~m <nvaXmC Xn. V6'igiathi~tnaychungtacoduQ'ck~tqualasup(Xm)2:sup(Xn)2:f3. V~ytaco X'm=XmU x vaX' n=XnU x, guyraX'mC X' nvasup(X'm)=sup(X'n)=f3 TheoTinhchat2 cuat~pdongchoth~yX'mkh6ngthSla t~pdong,vi v~yta co thS lo;;tibevakh6ngxetd~ndanhm1,lCxtrongc~pm. 3.4.2.H~qua2( ki~mtra onbdongcuat~ppb&bi~n) Trangquatrinhphatsinht~pph6bi~ndong,chungtaphaidambaatinhdongcua t~p h6bi~nb~ngcachth1,1'chi~n2 phepkiSmtra: . Supersetchecking:t~pph6bi~nm6'inayco la t~pchav6'iclIngde>ph6bi~n cuacact~pph6bi~ndongdiltimtru6'cdokh6ng.N~ucothi~pph6bi~n nayduQ'cch~pnh~nvalo;;tibenhungt~p h6bi~ndongdiltimtru6'cdo. . Subsetchecking:t~pph6bi~nm6'inayco la t~pconv6'iclIngde>ph6bi~n cuacact~pph6bi~ndongdiltimtru6'cdokh6ng.N~ucothi t~pph6bi~n naykh6ngthSlat~pph6bi~ndong. 32 Vai chi@nIuQ'cduy~ttheechi~uSailvam6hinhchiad~tri clIngvai Tinhchdt1cua t?Pph6bi@ndongthich~cch~ Iakh6ngdn phepsupersetcheckingmavfu1dam baatinhdongcuat?Pph6bi@n. Chtfngminh: Giasutacot?Pph6bi@ndongXmdffduQ'cxacdinhtruac,vat?PXn Iat?Pph6bi@n dangxemxettinhdong. V?y tacoth~phMbi~uIa cosud\mgphepsupersetcheckingkhivachikhi cot6n t~itruanghQ'pXmc Xnvasup(Xm)=sup(Xn).Tu nh?nxetnaytacosup(Xn-Xm)= sup(Xm),conghlaIamQigiaodichcochuaXmd~ucochua(Xn-Xm). Nhungtrongquatrinhtimt?Pph6bi@ndongtacosud\mgTinhchdt1cuat?Pph6 bi@ndong,vi V?ych~cch~ Ia kh6ngt6nt~itruanghQ'PXmc Xnvasup(Xm)= sup(Xn).Chonentakh6ngc~nth\,l'chi~nphepki~mtrasuperset. 3.5.THUAT ToAN CLOSET+ rt31.rt91.rtl 3.5.1.Phepchi~uth1!cfir dumlen - D\,l'atrenthut\,l'cuafJist toanCI)C(CI)CbQ),b~td~ubkg danhml)CcodQ ph6bi@n h6nh~th6amill_supvak@thucb&ngdanhml)CcodQph6bi@n Iannh~t,I~nIuQ'tchQntungdanhml)Ch~tgi6ng. - TrenFP-treetoanCI)C(CI)CbQ),chungtab~td~uduy~ttungnuttunhii'ngnut chua danhml)Ch<;ltgi6ng ti@ndk Ien d@nnut g6c cua diy d6ngthai xay d\,l'ngfJist CI)CbQvaFP-treeCI)CbQcuadanhml)Ch<;ltgi6ngnay. - N@ufJist CI)CbQkh6ngcon danhml)Cnaothi quayIui mQtbuac va th\,l'c hi~nti@p. 3.5.2.Phepchi~uaofir trenxu&ng - D\,l'atrenthu t\,l'cuafJist toanCI)C,b~td~ubkg danhml)Cco ~Qph6bi~n Iannh~tvak@thucb&ngdanhml)CcodQph6bi@n h6nh~th6amill_sup, I~nIuQ'tchQntungdanhml)Ch<;ltgi6ngtrongfJist toanCI)C(CI)CbQ). 33 - TrenFP-treetoC:mC1.1C,chungtaduy~ttUngnutb~td~utunutchuadanhm1.1C h<;ltgi6ngxu6ngdk d~nnuthicuacayvaxayd1,1'I1gClist C1.1Cb6cuadanh m1.1Ch<;ltgi6ngnay.Ghinh~nvi tri cuanutcontn,rcti~pvai nhii'ngnutchua danhm1.1Ch<;ltgi6ngnaytrongClist C1.1Cb6. - N~ufJist C1.1Cb6khongcondanhm1.1Cnaothi quaylui m6tbuacva th\l'c hi~nti~p. 3.5.3.Ki~mtrasubsetb~ngdiy k~tqua MotacAutrucdayk~tqua: Sud1.1ngdu trucduli~ucayg6m2 c~pchim1.1Cd~lull tmt~pph6bi~nd6ng.C~p chim1.1Cthunh~td\l'atrentencuat~pdanhm1.1Ctheethut\l'cuaClist.C~pchim1.1C thuhaidin cutrend6ph6bi~ncuatungdanhm1.1Cc6thamgiavaot~pph6bi~n dongk~tqua. Ngochrakhib6sungt~pph6bi~nb&ngcachl~nIUQ1themnutvaotrongcay,n~u nutdiic6thil~ygiatri Iannh~thayvi tinhtichlUy. Cachtht'fcki~mtra tinhdongtrendayk~tqua: Giasut~pph6bi~ndangxetXnkhonglat~pd6ng:3t~pd6ngXmsacchoXnC Xmvasup(Xn)=sup(Xm)ho~ctac6th~n6i2t~pXnvaXmc6nhii'ngquailh~sau: . XnvaXmc6 clingd6ph6bi~n. . T~tcacacdanhm1.1CtrongXnd~un&mtrongt~pXm. . Cacph~ntu trongXnvaXmc6clingm6tthut\l'chungtrongfJist. D1.1'av onh~nxettrentaxayd1.1'nghamki~mtrasubsetnhusau: N{jidunghamCheckSubset-ResultTreeO DduVaG:Caykit quaRTreeluutrCi'tgpph6bidndong,vatgpph6bidnFl. Ddura:Kdtlugntgpph6bdnFl cola tgpph6bdndongkh6ng. Cacbu:acthlfchi?n: 34 Bmyc1: ChQnph~ntll cu6iclingtrongXnvaxacdinhvi tri xu~thi~ncuan6tren dp chi ml,lCthunh~t.Saud6 dl,l'avaobangchi ml,lCthuhaitimgiatri trlingvai sup(Xn). Bmyc2:N~uc6thixacdinhnuttrencayvaduy~tti~nd~nlennutg6cvaki@mtra xemt~tcacacph~ntll trongXnc6xu~thi~nh~trongc~utruccaymlyhay kh6ng? Bmyc3:N~ukh6ngh~t,k~tlu~ndaylat~pph6bi~nd6ngvataphaib6sungvao cay.NguQ'cl<;lithikh6nglat~p h6bi~nd6ng. 3.5.4.Ki~mtrasubsetbiingcityFP-tree N~ut6nttdanhml,lCc6thutl,l'nh6hanthutl,l'Iannh~trongt~pdanhml,lC dangchi~ud6ngthaixu~thi~ntrongmQigiaodichchuat~pdanhml,lCdangchi~u thik~tlu~nt~pdanhml,lCdangchi~ukh6ngth@lat~pph6bi~nd6ng. Dl,l'avaonh~nxettrentaxaydl,l'nghamki@mtrasubsetnhusau: Ni)idunghamCheckSubset_FP-treeO Dduvao:FP-treeloanqlc, va ttlPph6 bi€n FI. Ddura:K€t lu(jnt(jpph6 bi€n FI co la t(jpph6 bi€n dongthong . CacbtdlCthlfchifn: BtrO'c1: max=Thu tl,l'Ian nh~trongs6cacdanhml,lCtrongFI theofJist toanCl,lC. BtrO'c2:Duy~tl~nluQ'tcacgiaodichTj c6chuat~pph6bi~nFI naydl,l'atrenFP- treevaghinh~n hfu1gdanhml,lCc6xu~thi~ntrongb~tkygiaodichTj va c6thutl,l'nh6hanmaxtheofJist toanCl,lCclingvai itchliiyde>ph6bi~n. BtrO'c3:N~uc6danhml,lCnaoduQ'cxacdinh&buac2 c6de>ph6bi~nb~ngvaide> ph6bi~ncuat~pph6bi~nFI thi t~pFI kh6ngphaila t~pph6bi~nd6ng. NguQ'cl<;li,n~ukh6ngc6danhml,lCnaoc6dQph6bi~nitchlii~trongbuac 2 b~ngvaide>ph6bi~ncuat~pFI thik~tlu~nt~pFI lat~pph6bi~nd6ng. 35 3.5.5.Thuit toaD l)@t6iUtihoav6inhfi'nglOc;licO'sO'dfrli~ukhacnhau,thu~ttoanCLOSET+sechQn h,raphepchi~uth1,1'ctu du6itenn~ucO'sO'dfrli~ucoti l~nencaoho~cphepchi~u aotutrenxu6ngcoti l~nenth~pkhichuy@nquaFP-tree. N{jidunghamCLOSET+0 Ddu viw: C(Jsirdfrli~ucacgiao djch TDB vanglfO71gph6 bi~nminSup. Ddura: T(ipcac t(ipph6 bi~ndongFC! thoanglfO71gph6 bi~nminSup. Cac blfCrCth1!chi~n: B1fCYC1: Treeo=createFPtree(TDB,minSup). B1fCYC2: N~uTreeoco ti l~nencaothi si'rd\mgphepchi~uth1,1'ctu du6i tenva gQi thut\lCCheckSubset_ResultTreem6i l~nphatsinhmQtt~pph6bi~ndong d@ki@mtratinhdongcuak~tqua. BtrO'c3:N~uTreeocoti l~nenth~pthisi'rd\lngphepchi~uaotutrenxu6ngvagQi thut\lCCheckSubset_FP-treem6il~nphatsinhmQt~pph6bi~ndongd@ ki@mtratinhdongcuak~tqua. 3.6.vi DU Quatrinhtimt~pph6bi~ndongb&ngcachsi'rd\lngphepchi~uth1,1'ctutrenxu6ng tuO'ngt1,1'nhutrongthu~ttoanFP-growthapd\lngthemhaitinhch~tcuat~pdongva haih~quatrenFP-treev6iphepki@mtratrenciiyk~tquat~pph6bi~ndong.Vi v~y trongvi d\lnaykh6ngminhhQathu~ttoanCLOSET+v6i phepchi~uth1,1'ctu du6i tenmakhaosatv6iphepchi~uaotutrenxu6ngv6ingmJngminSup=1. Chi~DtreDtapdaDhfiDC(c : 6): 36 ---------------- ---,r--- ! ! ! , ! , I , , I I , I I I I : , I " ! ! / I , " I , '" IL ~ mnh 3.5- f_listeyeb(}ehi~utrent~pdaubmye{e}. K~tquat~pph6bi~ndongphatsinhduQ'cla : (c :6). Chi~utrentapdaubmue(ew: 5): ," /--1--, --- I I ,-- I I , I :I I I I I ,/ I " ! I " I 1,/ I \ ...r' , I " II ""- --'I ----- ------ mnh 3.6- f_listeyeb(}ehi~utrent~pdaubmye{ew}. K~tquat~pph6bi~ndongphatsinhduQ'clei: (cw:5). 37 Cbi~utrentapdaubmuc(cwa: 4): r-- I I I I I L j Hinb 3.7- Clist cycb{)cbi~utrent~pdaubmyc{cwa}. KStqua~pph6biSndongphatsinhduQ'cla : (cwa:4). Chi~utrentapdaubmuc(cwad: 2): ------ mnb 3.8- Clist cycb{)cbi~utrent~pdaubmyc{cwad}. 38 K~tquat~pph6bi~ndongphatsinhduQ'c18.: (cwad:2). Chi~utreo tap daub mue(ewadt : 1) : I J, I I I I I"""" moh 3.9- Clist eyeb{)ehi~utreot~pdaubmye{ewadt}. K~tquat~pph6bi~ndongph<itsinhduQ'c18.: (cwadt:1). Chi~utreotapdaubmue(ewat: 3) : I,,I I I I I"""----- moh 3.10- f_listeyeb{)ehi~utreot~pdaubmye{cwat}. 39 KStquat~pph6biSndongphatsinhduQ'cla : (cwat:3). Chi~uireDtapdaubmuc(cwd: 3) : ------ Hinh 3.11- Clist c\lcb{)chi~uireDt~pdaubm\lc{cwd}. KStquat~pph6biSndongphatsinhduQ'cIi : (cwd:3). Chi~uireDtapdaubmuc(cwdt: 1): 40 ,I,I I I I I""------ Hinh 3.12- f_listC\lCb{)chi~utrent~pdanhm\lc{cwdt}. Trongl~nchi~umlYkh6ngt~orat~pph6bi~ndong.Vi khi ki~ffitmtanh~nth~y t6nt~idanhffi\lC{a}thuocph~ntrensov&idanhffi\lC{t}vaxu~thi~ntrongffiQi giaodichchuat~pdanhffi\lC{cwdt}.D~nd~nk~tquala t~pph6bi~n(cwdt:1) kh6nglat~pph6bi~ndong. Chi~utrenHipdanhmuclcwt: 3) : TheaH? qua1 thit~pdanhffi\lCnaykh6ngdn xetvi danhffi\lCxu~thi~nhail~n: t~il~nchi~utrent~p{cw}vat~p{cwa}v&iclIngdoph6bi~nla3. Chi~utrenHipdanhmuclca : 4): TuO'ngt\J,theoH? qua1thit~pdanhffi\lCnaykh6ngc~ xetvi danhffi\lCxu~thi~n hail~n:t~il~nchi~utrent~p{c}vat~p{cw}v&iclIngdoph6bi~nla4. Chi~utren tap danh muc (cd: 4) : 41 --1 I I I I I I I I I J I, I I I I I I"'" ,,'"---" mnh 3.13- Clist cyc b{)chi~utren t~pdaub myc {cd}. K~tquat~pph6bi~ndongphatsinhduQ'clit: (cd:4). Chi~utren taDdaub muc (cdt : 2) : I I I I I I I" '" '" ,,'"---- mnh 3.14- Clist cycb{)chi~utrent~pdaubmyc{cdt}. 42 K~tquat~pph6bi~ndongphatsinhduQ'cla : (cdt:2). Chi~utrentapdaubmue(et: 4) : IIA1 ..IB... \ \, \ \ II I I I I I I' I'"""" Hinh 3.15- Clist eyeb(}ehi~utrent~pdaubmye{ct}. K~tquat~pph6bi~ndongphcitsinhduQ'cla : (ct:4). Chi~utrentapdaubmue(w : 5): TheoH? qua1 thit~pdanhml,lCmlykhongC§llxetvi danhml,lCxuAthi~nhaiIdn: t~ifJist toimCl,lCvaIdnchi~utrent~p{c}v&iclIngde>ph6bi~nla5. Chi~utrenHipdaubmue(a : 4): TheoH? qua1 thit~pdanhml,lCnaykhongcdnxetvi danhml,lCxuAthi~nhIDIdn: t~ifJist toanCl,lCval~nchi~utrent~p{c}v&iclIngde>ph6bi~nla4. Chi~utrentapdaubmue(d : 4): TheoH? qua1 thit~pdanhml,lCnaykhongcdnxetvi danhml,lCxuAthi~nhail~n: t~ifJist toanCl,lCval~nchi~utrent~p{c}v&iclIngde>ph6bi~nla4. I Chi~utrentapdaubmue(t : 4):I 43 TheoH? quit1 thit~pdanhm\lCll!iykh6ngc~nxetvi danhm\lCxu~thi~nhail~n: tph6bi~nla4. K~tQuadiDDhBbi~ndonS!thudIrO'ckhi thuchi(~nthuattminCLOSET+ : Bang 3.1- K~tquat~pphBbi~ndongthoangIro-ngminSup=1. 1 2 3 4 5 6 7 8 9 10 6 5 4 2 1 3 3 4 2 4 100.00% 83.33% 66.66% 33.33% 16.66% 50.00% 50.00% 66.66% 33.33% 66.66% c c,w C,W,a C,w,a,d C,w, a,d,t C,w, a,t c,w, d c,d c,d,t c,t K~tQuadiDDhBbi~ndonS!th~bien ireD dim: mnh 3.16- Dimt~pdongv6'iminSup=1 44 3.7. KET LuAN R5 rangv6'inhungthu~itto{mtlmtdpph6bi~ndong(ch~nghl:lnnhu:CLOSET+, CLOSET, CHARM, Pascal,A-ClosevaClose,...) conhi~uUtidi@msov6'inhung thudto{mtlmtdpph6bi~nnhusau: . Ph<itsinhluQ'ngtdpdanhm\,1Ck~tquaithannhi~ul~n. . B6 batnhi~ut6hQ'pkhongck thi~tkhi apd\,1ngcactinhch~tcuatdpph6 bi~ndong. . ValacO'So'choquatrinhsinhludthl:ltgi6ng(mQtkhaini~mm6'iv6'inhi~u lQ'ichduQ'ctrinhbaytrongChuang5).