Tóm tắt Luận án tiến sĩ Toán học: Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao

Mục đích của luận án nhằm nghiên cứu các thuật toán khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao. Xây dựng mô hình, điều kiện, cấu trúc dữ liệu nhằm giảm không gian tìm kiếm và dựa trên cơ sở đó để xây dựng các thuật toán khai phá tập phổ biến có trọng số và tập lợi ích cao.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận án tiến sĩ Toán học: Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao MỞĐẦU Khaipháluậtkếthợplàmộttrongnhữngkỹ thuậtquan trọngnhấttrongkhaiphádữ liệu.Mụcđíchchínhcủakhaipháluậtkếthợplàtìmramốiquanhệgiữacácphầntửkhácnhautrongcơsởdữliệu.Bàitoánkhaiphátậpluậtkếthợp gồmhaibàitoánconđólàkhaiphátậpphổbiếnvàsinhluậtkếthợp.Trongđó,bàitoánkhaiphátậpphổbiếnđãthuhút đượcnhiềunhànghiêncứutrongnướcvàthếgiớiquantâm.Nhưngkhaiphátậpphổbiếntruyềnthốngtrongthựctếvẫncònnhiềuhạnchế,khôngđápứngđượcnhucầucủangườisử dụngnhưđánhgiásự quantrọngcủatừngphầntửtrong từnggiaodịchhaytrongcơsởdữliệu .Đểkhắcphụcnhữnghạnchế củakhaiphátậpphổ biếntruyềnthống,nhiềunhànghiêncứuđãđềxuấtmôhìnhmởrộng trongđócótínhđếnmứcđộquantrọngkhácnhaucủacácphầntửtrongcơsởdữliệunhư:khaiphátậpphổbiếncótrọngsố WFI;khaiphátậplợiíchcaoHUI. Mộttrongnhữngtháchthứctrongkhaiphátậpphổbiếncótrọngsốvàtậplợiíchcaođólàtậpphổbiếncótrọngsố,tập lợiíchcaokhôngcótínhchấtđóngtínhchấtlàmgiảmsốlượng ứngviênđượcsinhravàkhônggiantìmkiếm.Hầuhếtcácthuậttoánkhaiphátậplợiíchcaođềusử dụngtínhchấtđóngcủalợiíchtrọngsố giaodịch–TWUdoLiuvàcộngsựcôngbốnăm2005.Tuynhiên,ngưỡngTWUvẫncònkhácaosovớilợiíchthựctếcủacáctậpphầntử,dođóvẫncònphátsinhmộtsốlượnglớncácứngviênkhôngcầnthiết, dođótiêutốnthờigianvàkhônggiantìmkiếm. Trêncơsở nhữngnghiêncứu,nhậnxétvàđánhgiáởtrên,nghiêncứusinh đã chọnđề tài“Nghiêncứupháttriểnmô hình,thuậttoánkhaiphátập phầntử cótrọngsố vàlợi íchcao”làmđềtàinghiêncứucholuậnántiếnsĩcủamình. Mụctiêunghiêncứu Nghiêncứucácthuậttoánkhaiphátậpphổ biến, tậpphổbiếncótrọngsốvàtậplợiíchcao. Xâydựngmôhình,điềukiện,cấutrúcdữ liệunhằm giảmkhônggiantìmkiếmvàdựatrêncơ sở đóđể xâydựngcácthuậttoánkhaiphátậpphổbiếncótrọngsốvàtậplợiíchcao.Chương1.TỔNGQUANVỀKHAIPHÁTẬPPHỔBIẾN1.1. Giớithiệuchung Khaiphátậpphổbiếnlàtìmracáctậpphầntửcósốlầnxuấthiệnlớnhơnmộtngưỡnghỗ trợ tốithiểu(minsupp). Tuynhiên,khaiphátậpphổ biếncónhữnghạnchế.Thứnhất,nóxử lýtấtcả cácphầntử cótầmquantrọngnhưnhau.Thứ hai,trongmộtgiaodịchmỗiphầntửch ỉcótrạngtháixuấthiệnhoặckhôngxuấthiện.Rõràngnhữnghạnchếnày làm cho bài toán khai phá tập phổ biến truyền thống khôngphùhợpvớicáccơsởdữliệuthựctế,vídụnhưtrong cơ sở dữliệucủasiêuthị,mỗimặthàngcótầmquantrọng haygiácảkhácnhau,sốlượngmuacácmặthàngtrongmỗi giaodịchcũngkhácnhau,…Vìvậy,môhìnhkhaiphátậpphổbiếnchỉ phản ánhmốitươngquangiữacácphầntử xuất hiệntrongcơsởdữliệu,nhưngkhôngphảnánhýnghĩacủatừngphầntửdữliệu.Đểkhắcphụcnhữngnhượcđiểmtrêncóhaimôhìnhđượcđưara:TậpphổbiếncótrọngsốWFIvàTậplợiíchcaoHUI.1.2. Tậpphổbiến Khaiphátậpphổbiếnlàquátrìnhtìmkiếmtậpcácphần tử cósố lầnxuấthiệncùngnhaulớnhơnmộtngưỡngchotrướctrongcơsởdữliệulớnđượcR.Agrawal,T.ImielinskivàA.Swamiđềxuấtnăm1993,xuấtpháttừnhucầubàitoánphântíchdữliệutrongcơsởdữliệugiaodịch,để pháthiệncácmốiquanhệ giữacáctậphànghóađãbántạisiêuthị.Việcxácđịnhnàykhôngphânbiệtsự khácnhaugiữacáchànghóamàchỉdựavàosựxuấthiệncủachúng. Mộtsốphươngphápkhaiphátậpphổbiến: Phươngphápdựatrênquanhệkếtnối Phươngphápsửdụngcấutrúccây Phươngpháptăngtrưởngđệquydựatrênhậutố Mộtsốphươngphápsongsong1.3. Tậpphổbiếncótrọngsố Năm1998,nhómcủaRamkumarđãđưaramôhìnhkhaiphá tậpphổ biếncó trọngsố (WeightFrequentItemsets– WFI).Trongđó,mỗiphầntửcómộttrọngsốkhácnhaunhư:lợiích,giácả,độ quantrọnghaysố lượng,…Mộttậpcácphầntử làphổ biếncótrọngsố khigiátrị cótrọngsố củachúnglớnhơnmộtngưỡngchotrước.Dựatrênmôhìnhnàyđãcónhiềuthuậttoánkhaiphátậpphổ biếncótrọngsốđượccôngbố. Mộtsốphươngphápkhaiphátậpphổbiếncótrọngsố: Thuậttoándựatrênkhoảngtrọngsố Thuậttoánsửdụngbảngbăm Thuậttoándựatrêntrọngsốphổbiếnxấpxỉ ThuậttoándựatrêncâyWIT1.4. Đềxuấtthuậttoánkhaiphámẫuphổbiến cótrọng sốtheochiềudọc Dựatrênnhững ưuđiểmcủathuậttoánVMDGkhaiphátậpphổ biến,đề xuấtthuậttoánkhaiphátậpphổ biếncó trọngsố vớitêngọiVMWFP(VerticalMiningofWeightedFrequentPatterns ...