B GIO DC V O TO TRNG I HC CễNG NGH TP HCM - Vế MINH QUN KHAI THC LUT KT HP TI THIU S DNG DN TP ểNG LUN VN THC S Chuyờn ngnh: Cụng ngh Thụng tin Mó s ngnh: 60480201 TP H CH MINH, thỏng 04 nm 2015 B GIO DC V O TO TRNG I HC CễNG NGH TP HCM - Vế MINH QUN KHAI THC LUT KT HP TI THIU S DNG DN TP ểNG LUN VN THC S Chuyờn ngnh: Cụng ngh Thụng tin Mó s ngnh: 60480201 CN B HNG DN KHOA HC: PGS TS Lấ HOI BC TP H CH MINH, thỏng 04 nm 2015 CễNG TRèNH C HON THNH TI TRNG I HC CễNG NGH TP HCM Cỏn b hng dn khoa hc : PGS TS Lờ Hoi Bc Lun Thc s c bo v ti Trng i hc Cụng ngh TP HCM ngy11 thỏng 04 nm 2015 Thnh phn Hi ng ỏnh giỏ Lun Thc s gm: TT H v tờn PGS.TS Lờ Trng Vnh GS.TSKH Hong Vn Kim TS Vừ ỡnh By PGS.TS Phỳc TS Nguyn Vn Mựi Chc danh Hi ng Ch tch Phn bin Phn bin y viờn y viờn, Th ký Xỏc nhn c a Ch tch Hi ng ỏnh giỏ Lun sau Lun ó c sa cha (nu cú) Ch tch Hi ng ỏnh giỏ LV PGS TS Lờ Trng Vnh TRNG H CễNG NGH TP HCM PHềNG QLKH TSH CNG HềA X HI CH NGHA VIT NAM c lp T Hnh phỳc TP HCM, ngy 18 thỏng 03 nm 2015 NHIM V LUN VN THC S H tờn hc viờn: Vế MINH QUN Gii tớnh: Nam Ngy, thỏng, nm sinh: 02/10/1980 Ni sinh: Phỳ Quc Kiờn Giang Chuyờn ngnh: Cụng ngh Thụng tin MSHV: 1341860017 I- Tờn ti : KHAI THC LUT KT HP TI THIU S DNG DN TP ểNG II- Nhim v v ni dung : - Tp trung tỡm hiu, ỏnh giỏ v xut hng tip cn hiu qu thut toỏn khai thỏc lut kt hp cross-level s dng dn úng - Kho sỏt phng phỏp khai thỏc lut kt hp cross -level s dng dn úng hin cú - nh hng xut hng tip cn mi khai thỏc lut kt hp cross-level dựng dn ú ng III- Ngy giao nhim v:18/08/2014 IV- Ngy hon thnh nhim v: 14/03/2015 V- Cỏn b hng dn: PGS.TS Lấ HOI BC CN B HNG DN PGS.TS Lấ HOI BC KHOA QUN Lí CHUYấN NGNH i LI CAM OAN Tụi xin cam oan õy l cụng trỡnh nghiờn cu ca riờng tụi Cỏc s liu, kt qu nờu Lun l trung thc v cha tng c cụng b bt k cụng trỡnh no khỏc Tụi xin cam oan rng mi s giỳp cho vic thc hin Lun ny ó c cm n v cỏc thụng tin trớch dn Lun ó c ch rừ ngun gc Hc viờn thc hin Lun Vừ Minh Quõn ii LI CM N Trong sut quỏ trỡnh hc v hon thnh lun ny, tụi ó nhn c s hng dn, giỳp quý bỏu ca quý thy cụ, gia ỡnh, bn bố v ng nghip Vi lũng kớnh trng v bit n sõu sc tụi xin c by t li cm n chõn thnh ti: Khoa Cụng Ngh Thụng Tin, Phũng Qun lý Khoa hc - o to sau i hc trng i Hc Cụng Ngh Thnh Ph H Chớ Minh ó to mi iu kin thun li giỳp tụi quỏ trỡnh hc v hon thnh lun ny Thy hng dn Phú Giỏo s - Tin s Lờ Hoi Bc, thy ó truyn t nhng kin thc rt b ớch cho tụi quỏ trỡnh hc tp, ó ht lũng to iu kin cng nh giỳp tụi quỏ trỡnh hon thnh lun ny Anh Lng Hu Phỳc, ó ht lũng giỳp , hng dn cho tụi quỏ trỡnh thc hin lun ny Ton th quý thy cụ ó nhit tỡnh gin g dy v truyn t nhng kin thc b ớch cho tụi sut khúa hc va qua Cui cựng xin cm n n tt c nhng ngi thõn gia ỡnh, bn bố v ng nghip ó giỳp tụi sut quỏ trỡnh hc v thc hin lun ny Vừ Minh Quõn iii MC LC M U Chng TNG QUAN Chng C S Lí THUYT 2.1 Khai thỏc ph bin 2.1.1 Mt s nh ngha 2.1.2 Thut toỏn khai thỏc ph bin Apriori 2.2 Khai thỏc ph bin úng 11 2.2.1 Mt s nh ngha 11 2.2.2 Thut toỏn khai thỏc ph bin úng (CHARM) [3 1] 12 2.3 Dn ph bin úng 15 2.3.1 nh ngha 15 2.3.2 Mt s thut toỏn khai thỏc dn ph bin úng 15 2.3.2.1 Thut toỏn CHARM-L [31] 15 2.3.2.2 Thut toỏn xõy dng dn úng [2] 17 2.4 Tp sinh ti tiu (minimal Generator mG) [30] 19 2.5 Khai thỏc lut kt hp ti thiu khụng d tha t dn úng 20 2.5.1 Mt s nh ngha 20 2.5.2 Thut toỏn khai thỏc MNAR t dn úng [26] 20 Chng THUT TON MMCAR 22 3.1 GII THIU 22 3.1.1 Tớnh toỏn ph bin ca item 22 3.1.2 Xõy dng dn úng mc xỏc nh 23 3.1.3 Cỏc lut kt hp ti thiu khụng d tha cross -level 23 3.1.3.1 Dn ng c viờn 25 3.1.3.2 Tớnh toỏn mG, TidList v h tr ti thiu 32 3.1.3.3 Sinh cỏc lut kt hp cross-level t dn úng 33 3.2 Mễ T THUT TON MMCAR 33 iv 3.3 XUT HNG TIP CN MI 45 Chng THC NGHIM V NH GI 50 4.1 Mễ T CHIN LC V D LIU THC NGHIM 50 4.2 SO SNH, NH GI KT QU THC NGHIM 53 KT LUN V HNG PHT TRIN 58 TI LIU THAM KHO 59 PH LC v DANH MC CC K HIU, T VIT TT T Ting Anh Gii thớch CCL Cross-level Closed-Itemset Lattices Dn úng cross-level CFCI Cross-level Frequent Closed Itemsets Tp ph bin úng cross-level CSDL Database(s) C s d liu DFS Depth First Search Tỡm theo chiu sõu FI Frequent Itemset(s) Tp ph bin FCI Frequent Closed Itemsets Tp ph bin úng FCI-List Frequent Closed Itemsets List Danh sỏch ph bin úng FIL Frequent Itemsets Lattice Dn ph bin FCIL Frequent Itemsets Lattice Dn ph bin úng Item Mc Itemset Tp mc MFIL Modification of Frequent Itemset Dn ph bin thay i Lattice MMCAR Minimal Non-redundent Multilevel Lut khụng d tha ti thiu a and Cross-level Assocication Rules MNAR cp v cross-level Minimal Non-redundent Assocication Lut khụng d tha ti thiu Rule(s) mFI Multilevel Frequent Itemsets Tp ph bin a cp mFCI Multilevel Frequent Closed Itemsets Tp ph bin úng a cp mG(MG) Minimal Generator Tp sinh ti tiu minSup Minimum Support h tr ti thiu minConf Minimum Confidence tin cy ti thiu Subset Tp Superset Siờu Tid(TID) Transaction identifier Danh nh cỏc giao dch TidList Transaction identifier List Danh sỏch cỏc danh nh giao dch Support ph bin ỉ Tp rng vi Thuc Tn ti Phộp giao Cha hon ton Khụng cha Ln hn hoc bng Tng ng Khụng thuc Khụng tn ti Phộp hp Cha Khỏc Nh hn hoc bng Vi mi 52 Bng 4.4 Kt qu thc nghim trờn b d liu Retail Bng Kt qu thc nghim trờn b d liu Pumsb Trong ú, Phng phỏp l thut toỏn MMCAR, Phng phỏp l phng phỏp xut Mi dũng bng l kt qu trung bỡnh cng ca ln thi hnh chng trỡnh ng vi mi b mó húa, tng ng vi cỏc o minSup v minConfó c s dng thc nghim thut toỏn MMCAR 53 4.2 SO SNH, NH GI KT QU THC NGHIM Hỡnh 4.1 4.4so sỏnh thi gian xõy dng dn ca Phng phỏp t cỏc b d liu Mushroom, Chess, Pumsb v Retail, ng vi s thay i v s nhúm v minSup Hỡnh 4.1 Thi gian xõy dng dn t b d liu Mushroom vi cỏc giỏ tr khỏc ca minSup v s nhúm Hỡnh 4.2 Thi gian xõy dng dn t b d liu Chess vi cỏc giỏ tr khỏc ca minSup v s nhúm 54 Hỡnh 4.3 Thi gian xõy dng dn t b d liu Pumsb vi cỏc giỏ tr khỏc ca minSup v s nhúm Hỡnh 4.4 Thi gian xõy dng dn t b d liu Retail vi cỏc giỏ tr khỏc ca minSup v s nhúm 55 Hỡnh 4.5 Lng b nh cn thit xõy dng dn t b d liu Mushroom vi cỏc giỏ tr khỏc ca minSup v s nhúm Hỡnh 4.6 Lng b nh cn thit xõy dng dn t b d liu Chess vi cỏc giỏ tr khỏc ca minSup v s nhúm 56 Hỡnh 4.7 Lng b nh cn thit xõy dng dn t b d liu Pumsb vi cỏc giỏ tr khỏc ca minSup v s nhúm Hỡnh 4.8 Lng b nh cn thit xõy dng dn t b d liu Retail vi cỏc giỏ tr khỏc ca minSup v s nhúm Hỡnh 4.5 4.8 so sỏnh lng b nh cn thit xõy dng dn ca Phng phỏp t cỏc b d liu Mushroom, Chess, Pumsb v Retail, ng vi s thay i v s nhúm v minSup 57 Cỏc kt qu trờn cho thy s thay i ca s nhúm v minSup s nh hng n: i) Thi gian xõy dng dn ii) Lng b nh cn thit dng dn V hu ht cỏc trng hp, phng phỏp xut cú kt qu v chi phớ tt hn so vi phng phỏp so sỏnh (thut toỏn MMCAR) c v thi gian v b nh, v kt qu v s lut kt hp a cp v cross -level khai thỏc c l tng ng T ú cho thy, phng phỏp xut hiu qu hn so vi thut toỏn MMCAR Mt khỏc, cng phng phỏp xut ó b qua c vic xõy dng dn -item v khụng cn phi duyt DFS sinh cỏc úng ng viờn vỡ ó s dng trc tip cỏc úng sinh lm cỏc ng v iờn giao 58 KT LUN V HNG PHT TRIN Kt qu t c ca lun Lun ó trung tỡm hiu k thut khai thỏc cỏc lut kt hp a cp v cross-level s dng dn úng, da trờn vic khai thỏc hiu qu cỏc hnh vi ca dn Qua ú, lun xut mt hng tip cn mi hiu qu hn da vo k thut ó tỡm hiu Phng phỏp xut hiu qu hn vỡ khụng phi tn khụng gian lu tr cỏc dn ng viờn, vỡ dn ph bin úng cross -level c to t cỏc ph bin úng cross-level bng thut toỏn xõy dng dn ph bin úng hiu qu Ngoi ra, phng phỏp xut khụng tn thi gian duyt dn theo DFS sinh cỏc úng ng viờn Phng phỏp xut ó c thc nghim trờn cỏc CSDL thc vi s mc phõn cp l v ó khai thỏc thnh cụng cỏc lut kt hp ti thiu a cp v cross level, ch vi s ớt lut nhng cung cp rt nhiu thụng tin Cỏc lut kt hp khai thỏc c phng phỏp xut cng cú nh hng ln cỏc lnh vc ng dng thc t y thỏch thc nh: mỏy hc, sinh hc, trớ tu nhõn to, thng kờ , Hng nghiờn cu tip theo Cỏc hng nghiờn cu tng lai s trung khai thỏc lut kt hp ti thiu a cp v cross -level trờn CSDL ln , ngoi ra, s m rng s mc phõn cp cao hn Bờn cnh ú cng tip tc nghiờn cu ỏp dng vo CSDL thc t thy c úng gúp ca ti vo thc tin Mc dự bn thõn ó c gng trung nghiờn cu v tham kho cỏc ti liu, bi bỏo, khoa hc v ngoi nc, nhng trỡnh cũn n hiu hn ch nờn khụng th trỏnh nhng thiu sút Rt mong nhn c s úng gúp ca cỏc quý thy cụ v cỏc nh khoa hc lun c hon thin hn 59 TI LIU THAM KHO Ting Vit [1] Lờ Hoi Bc & Vừ ỡnh By Khai thỏc lut thit yu nht t ph bin úng Science & Technology Development, Vol 11, No.01 2008, 40-50 [2] Lờ Hoi Bc & Vừ ỡnh By ng dng dn úng khai thỏc lut thit yu nht Tp Phỏt trin KH&CN, 12, s 11-2009, 49-56 [3] Lờ Hoi Bc & Vừ ỡnh By Thut toỏn tỡm nhanh Minimal Generator ca ph bin úng Tp Phỏt trin KH&CN, 10, s 12-2007, 11-19 [4] Vừ ỡnh By (2011) Nõng cao hiu qu ca cỏc thut toỏn khai thỏc lut kt hp d trờn dn Lun Tin s, Khoa Hc Mỏy Tớnh, HKHTN Ting Anh [5] Agrawal, R., & Srikant, R (1994) Fast algorithms for mining association rules in large databases In VLDB (pp 487499) [6] Agrawal, R., & Srikant, R (1995) Mining sequential patterns In ICDE (pp 314) [7] Agrawal, R., Imielinski, T., & Swami, A.N (1993) Mining association rules between sets of items in large databases In SIGMOD conference (pp 207216) [8] Ahmed, C F., Tanbeer, S K., Jeong, B.-S., Lee, Y.-K., & Choi, H.-J (2012) Single-pass incremental and interactive mining for weighted frequent patterns Expert Systems with Applications, 39(9), 79767994 [9] Alramouni, S.,& Lee, J Y (2005) Mining multiple-level association rules from a transactional database using fp-tree In DMIN (pp 97103) [10] Bastide, Y., Pasquier, N., Taouil, R., Stumme, G., & Lakhal, L (2000) Mining minimal non-redundant association rules using frequent closed itemsets In Computational logic (pp 972986) [11] Brin, S., Motwani, R., & Silverstein, C (1997) Beyond market baskets: Generalizing association rules to correlations In SIGMOD conferencepp (265 276) 60 [12] Han, J., & Fu, Y (1995) Discovery of multiple-level association rules from large databases In VLDB (pp 420431) [13] Han, J., Pei, J., & Yin, Y (2000) Mining frequent patterns without candidate generation In SIGMOD conference (pp 112) [14] Han, J., & Fu, Y (1999) Mining multiple-level association rules in large databases IEEE Transactions on Knowledge and Data Engineering, 11(5), 798 804 [15] Jia, L., Yao, J., & Pei, R (2003) Mining association rules with frequent closed itemsets lattice In KES (pp 469475) [16] ki Leung, C W., fai Chan, S C., & Chung, F.-L (2008) An empirical study of a cross-level association rule mining approach to cold-start recommendations Knowledge Based Systems, 21(7), 515529 [17] Loglisci, C., & Malerba, D (2009) Mining multiple level non-redundant association rules through two-fold pruning of redundancies In MLDM (pp 251 265) [18] Pei, J., Han, J., & Mao, R (2000) Closet: An efficient algorithm for mining frequent closed itemsets In ACM SIGMOD workshop on research issues in data mining and knowledge discovery(pp 2130) [19] Shrivastava, V K., Kumar, P., & Pardasani, K R Fp-tree and cofi based approach for mining of multiple level association rules in large databases arXiv:1003.1821 [20] Srikant, R., & Agrawal, R (1995) Mining generalized association rules In VLDB(pp 407419) [21] Srikant, R., & Agrawal, R (1996) Mining sequential patterns: Generalizations and performance improvements In EDBT (pp 317) [22] Tahrima, H., Chowdhury, F A., Md Samiullah., Sayma, A & Byeong-Soo, J (2014) An efficient approach for mining cross-level closed itemsets and minimal association rules using closed itemset lattices Expert Systems with Applications 41 (2014) 29142938 [23] Thakur, R., Jain, R., & Pardasani, K (2006) Mining level-crossing association 61 rules from large databases Journal of Computer Science, 2(1), 7681 [24] Vo, B., & Le, B (2009) Mining traditional association rules using frequent itemsets lattice In 39th international conference on computers and industrial engineering (pp 14011406) [25] Vo, B., & Le, B (2009) Fast algorithm for mining minimal generators of frequent closed itemsets and their applications In 39th international conference on computers and industrial engineering (pp 14071411) [26] Vo, B., & Le, B (2011) A frequent closed itemsets lattice-based approach for mining minimal non-redundant association rules arXiv:1108.5253 [27] Vo, B., & Le, B (2011) Mining minimal non-redundant association rules using frequent itemsets lattice IJISTA, 10(1), 92106 [28] Wan, Y., Liang, Y., & Ding, L -Y (2008) Mining multiple association rules with dynamic concept hierarchy In Seventh international conference on machine learning and cybernetics (pp 287292) [29] Wu, T., Chen, Y., & Han, J (2007) Association mining in large databases: A reexamination of its measures In PKDD (pp 621628) [30] Zaki, M J (2004) Mining non-redundant association rules Data Mining and Knowledge Discovery, 9(3), 223248 [31] Zaki, M J., & Hsiao, C.-J (2005) Efficient algorithms for mining closed itemsets and their lattice structure IEEE Transactions on Knowledge and Data Engineering, 17(4), 4624 PH LC B Qua dn vi , ,, , ,, vi dn , s to cựng dn , , cp dn s sinh mt dn kt qu d tha ,, , , ,, v dn , , ,, , Tuy nhiờn, vic xem xột c hai Chng minh Dn dn , ,, , , ,, cha cỏc item ca cỏc mc a 1,a2,,ak-1,ak Tng t, cỏc , v , ,, cha cỏc item tng ng vi cỏc mc , a1,a2,,ak-1,ak+1 v a2,a3,,ak,ak+1 Nu xột qua hai dn , ,, hoc dn , , ,, , ,, , vi dn , chỳng ta s to mt dn cha cỏc item t cỏc , mc a1,a2,,ak-1,ak,ak+1 Trong thc t, õy l dn , ,, , Do ú, c hai , cp l tng ng v s to cỏc dn d tha nu xột qua cựng mt thi im B Khi duyt mt cỏc nỳtT ca dn , ,, giao nú vi dn , khỏc, nỳt u tiờn c xột th t duyt t heo chiu sõu (Depth First Search DFS) s c thc hin u tiờn, nú s m bo l ph bin úng ln nht c khai thỏc u tiờn Chng minh T cỏc thuc tớnh ca dn, rừ rng l, dn CFCI= Vi mi nỳtT={CFCIT,TIDT,MGT}t CTt , ,, , , ,, ,, , , cú nỳt gc TR cha cha mt cỏc nỳt , , ú iCT[i]={CFCICT[i],TIDCT[i],MGCT[i]}, iCFCICT[i] CFCIT , v TIDCT[i] TIDT Do ú, cỏc nỳt mc lỏ Tleaf ca dn , ,, , cha CFCI ln nht v cỏc nỳt ca mc trờn tng ng cha CFCI nh hn Vỡ vy, cỏc nỳt sõu nht vi itemset di nht s c khỏm phỏ u tiờn trỡnh t duyt DFS B Khi giao hai nỳt T1={ T2={ , , }t , ,, , , , } t , ,, , v to tt c cỏc subset cú th ca s bao ph tt c CFCI cú th c to bng cỏch giao cỏc nỳt ng viờn ca T1 v T2, vi mi Chng minh: l on itemset xung t ca Xột, T2={ ={ }, , , (CFCIcon) vi T1={ }t , ,, (CFCImat) , , } t , Rừ rng ={ l , ,, v , All_subset(CFCI) (CFCIdis) Cho T1 v T2, thỡ Hn na, k=1 thỡ } v = = u Xột k=n>1, subset v ca CFCImat cho T1 v T2 ó c tớnh toỏn theo phng phỏp xõy dng CFCI, vi cỏc bc k=1,2, ,n-1, cỏc subset cú chiu di khỏc ca CFCImat ó c tớnh toỏn Do ú, vic tớnh toỏn li cỏc subset ca CFCImat s cho kt qu d tha v cú th trỏnh c mt cỏch an ton bng cỏch to cỏc subset ln nht, ú chớnh l CFCImat Mt ln na, vic tớnh toỏn tt c cỏc subset cú th cho CFCIdisT1 v CFCIdisT2 l khụng cn thit Do cỏc tớnh cht ca dn, rừ rng l bt k subset, khỏc vi v , s khụng kt thỳc CFCI Vỡ t cỏc subset khỏc s to cỏc subset thc t ca CFCI kt qu vi h tr nh nhau, iu ny trỏi vi tớnh cht ca ph bin úng Do ú, trỏnh c vic tớnh toỏn subset ca Cỏc subset ca on itemset item cng cú th trỏnh c Vỡ s xung t gia cỏc v DESC(subset( s c gii Kt qu l, giao hai nỳt T1={ , }t ú: , ,, CFCIS = {CFCImat Vi CFCImat= cỏch g }\ DESC( , , , ,, , } t , ,, , , , ,., }, (1) , = { }, )} }t , ,, v s cho S=T1ìT2={CFCIS,TIDS,MGS}, , B Cho hai nỳt bt k T1={ , b , bao = cỏc itemset ó gii quyt xung t ca T1 v T2= {{ , T2={ bng Do ú, ch cn tớnh cỏc subset ca l tớnh CFCI ca nỳt kt qu ca dn , quyt )) i t n )), vi DESC(subset( gm tt c cỏc subset cú th ca T2={ l tt nht v , , , } t , ,, , v , nu on itemset gp ca T1 l CFCIP hoc nu on itemset gp ca T2 l CFCIQ, thỡ itemset kt qu s khụng l CFCI, vi P v Q l cỏc nỳt cha tng ng ca T1 v T2 Chng minh: Cho hai dn bt k T1={ t , , ,, } t , v , , ,, , T2={ Q={CFCIQ,TIDQ,MGQ} t , , ,, ,, , vi mnỳt v ,, ,, , vi nnỳt, nu , cú nỳt cha l P={CFCIP,TIDP,MGP} , , }t , cú nỳt cha l v on itemset gp ca T1 l , CFCIP hoc on itemset gp ca T2 l l CFCI Bi vỡ, theo nh ngha dn, TIDP v , CFCIQ, thỡ itemset kt qu s khụng CFCIP v CFCIQ, cựng vi TIDQ Giao hai nỳt T1 v T2 xõy dng CFCI ngha l giao , m ũi hi sinh subset ca v 3, rừ rng l ch cn subset ca Hn na, t b v l , vi cha nh mt on lừi Vỡ vy, bt k nỳt cha dn cú itemset vi lc lng nh hn lc lng ca itemset nú, nhiờn, vi ph bin ln hn hoc bng ph bin ca itemset ca nú Do ú Nu CFCIP hoc CFCIQ, thỡ nờn hoón xõy dng CFCI hoc CFCI xõy dng s mõu thun vi nh ngha ca ph bin úng v cỏc nỳt gi s c to B Cho hai nỳt bt k T1={ T2={ , T1 CFCImat , , = T2 , }t , ,, , , T2={ T1 vi k2 { hoc T1 hai nỳt }t T1={ , ,, , , ,, }= , v v } t , Nu , hoc { , , ,, , v , itemset gii quyt xung t ca T1 l v itemset gii quyt xung t ca T2 l T2 itemset trựng khp cho c hai nỳt l tng ng l , , }=, thỡ nỳt kt qu S , , ,, v itemset gii quyt xung t ca T2 l T2 giao , , , itemset gii quyt xung t ca T1 l Chng minh: Khi } t , ,., , , on v itemset riờng bit cho T1 v T2 Vi k1, thỡ CFCImat=, nhng vi k2, nu CFCImat= thỡ t b 1, cỏc nỳt phi thuc v dn , v khụng thuc dn kt qu , ,, ú, {T1 V {T1 , , , } l cỏc itemset ca mc }= s cho kt qu nỳt cha cỏc ph bin t cỏc mc a2,a3, ,ak+1 ch khụng phi l cỏc nỳt ca dn {T2 , {T1 , }= , ú nỳt kt qu S bng , cỏch giao , }t T1={ , Chng minh Theo b 4, i cha ith ca T1, v j , ,, , , , , thỡ TIDS = v cỏc nỳt s , Tid ca cỏc item , v , , tỡm v , tng ng l , bi vỡ bi vỡ trng , i din cho danh sỏch cỏc Theo cụng thc (2), CFCIS = B Cho nỳt kt qu bt k S={CFCIS,TIDS,MGS} t , ,, v hoc v , v vỡ vy TIDS = bng ,, s l úng c lp, v cú th thuc vo bt k nỳt khỏc ca Do ú, ,, , , CFCIQ[j], vi Q[j]={CFCIQ[j],TIDQ[j],MGQ[j]} l cha jth Tuy nhiờn, da vo tớnh cht ca dn, thỡ hp ú, Ngoi ra, , CFCIP[i], vi P[i]={CFCIP[i],TIDP[i],MGP[i]} l Rừ rng l v T2={ ,, } t , ca T2 Xột danh sỏch Tid ca cỏc item c ,, B Cho nỳt kt qu bt k S={CFCIS,TIDS,MGS} t T2={ dn , } l cỏc itemset ca mc ak+1 Kt qu l, cha ph bin ca cỏc mc a2,a3, ,ak c Do cỏch giao , }t Chng minh T1={ , ,, , , } t , , thỡ: , , , , = , , ,, ,, , , , cú v T nh ngha, cỏc mG l cỏc subset khụng rng nh nht ca ph bin úng vi TidList ging nh l ph bin úng ca chớnh nú [25] Nu = , thỡ TIDS = = v hoc = TIDS Do ú, MGS s l subset khụng rng nh nht ca cỏc item ca , tng ng vi cỏc hoc = hoc Tuy nhiờn, nỳt T1 thuc v dn cú mc cao hn nỳt T2 Do ú, trỡ cỏc tớnh cht dn ca vic tớnh toỏn MG, suy MGS = Nu , thỡ TIDS = s l subset khụng rng nh nht ca cỏc item ca MGS = v TIDS = Do ú, MGS , tng ng vi , suy tng t nh (2) nu , thỡ TIDS = v TIDS Do ú, MGS s l subset khụng rng nh nht ca cỏc item t c , tng ng t s pha trn ca cỏc v , suy ra, MGS = v TIDS v ... (superset )tối thiểu – tập con(subset) tối đại Các luật kết hợp khai thác thời gian ngắn khai thác hành vi dàn Các tác giả [22] đưa phương pháp khai thác luật kết hợp thông qua khai thác hành vi dàn tập. .. sử dụng dàn tập đóng - Khảo sát phương pháp khai thác luật kết hợp cross -level sử dụng dàn tập đóng có - Định hướng đề xuất hướng tiếp cận khai thác luật kết hợp cross-level dùng dàn tập ng III-... : KHAI THÁC LUẬT KẾT HỢP TỐI THIỂU SỬ DỤNG DÀN TẬP ĐÓNG II- Nhiệm vụ nội dung : - Tập trung tìm hiểu, đánh giá đề xuất hướng tiếp cận hiệu thuật toán khai thác luật kết hợp cross-level sử dụng