i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TƢ KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái nguyên, năm 2011 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TƢ KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC TS NGUYỄN HUY ĐỨC Thái nguyên, năm 2011 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan toàn nội dung Luận văn đƣợc thực theo đề cƣơng đƣợc hội đồng khoa học trƣờng Đại học Thái nguyênkhoa Công nghệ thông tin phê duyệt, nội dung thực đề cƣơng đƣợc cán hƣớng dẫn giao cho kiểm soát Nội dung luận văn, phần trích lục tài liệu hồn tồn xác Nếu có sai sót tơi hoàn toàn chịu trách nhiệm Tác giả luận văn Nguyễn Văn Tư Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii LỜI CẢM ƠN Tôi xin chân thành cảm ơn thầy cô Trƣờng Đại học Công nghệ Thông tin Truyền thông – Đại học Thái Nguyên, Thầy cô Viện công nghệ thông tin – Viện Khoa học Công nghệ Việt Nam, anh chị lớp Cao học K8 - khóa 2009-2011 giúp đỡ tơi q trình nghiên cứu thực luận văn Tôi xin trân trọng cảm ơn TS Nguyễn Huy Đức – Khoa Thơng tin Máy tính, Trƣờng Cao đẳng Sƣ phạm Trung ƣơng, ngƣời thầy trực tiếp hƣớng dẫn, đƣa ý tƣởng, định hƣớng, đóng góp ý kiến chun mơn tận tình giúp đỡ tơi suốt q trình nghiên cứu thực luận văn thạc sĩ ngành khoa học máy tính Tôi xin cảm ơn bạn bè đồng nghiệp gia đình giúp đỡ, đóng góp ý kiến động viên tơi suốt qua trình học, q trình nghiên cứu hoàn thành luận văn Tác giả Nguyễn Văn Tƣ Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii MỤC LỤC Trang Lời cam đoan……………………………………………………….…….………………i Lời cảm ơn… …………………………………………….…………….……………….ii Mục lục…………………… …………………………………….….…………… ……iii DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT .v DANH MỤC CÁC BẢNG BIỂU vi DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ vii MỞ ĐẦU .1 Chƣơng 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU 1.1 Quá trình phát tri thức từ sở liệu 1.2 Kiến trúc hệ thống khai phá liệu 1.3 Quá trình khai phá liệu 1.4 Nhiệm vụ khai phá liệu 10 1.5 Các phƣơng pháp khai phá liệu 11 1.5.1 Phƣơng pháp luật kết hợp 12 1.5.2 Phƣơng pháp định 12 1.5.4 Các phƣơng pháp dựa mẫu 14 1.6 Các ứng dụng khai phá liệu 15 Kết luận chƣơng 1: 16 Chƣơng 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU 17 2.1 Bài toán mở đầu 17 2.2 Các khái niệm sở 18 2.2.1.Cơ sở liệu giao tác 19 2.2.2 Biểu diễn sở liệu giao tác 19 2.2.3 Tập mục thƣờng xuyên 21 2.2.4 Luật kết hợp 22 2.2.5 Độ hỗ trợ độ tin cậy luật kết hợp 22 2.3 Khai phá luật kết hợp 24 2.4 Các cách tiếp cận khai phá tập mục thƣờng xuyên 26 2.5 Các thuật toán điển hình khai phá tập mục thƣờng xuyên 27 2.5.1 Thuật toán Apriori 28 2.5.2.Thuật toán FP_growth 33 2.6 Thuật toán sinh luật kết hợp: 41 2.7 Một số mở rộng khai phá luật kết hợp sở liệu 44 Kết luận chƣơng 2: 46 Chƣơng 3: KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ 47 3.1 Một số khái niệm luật kết hợp có trọng số 47 3.2 Khai phá luật kết hợp trọng số khơng chuẩn hóa 49 3.3 Khai phá luật kết hợp trọng số chuẩn hóa 52 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv 3.3.1 Một số khái niệm trọng số chuẩn hóa 52 3.3.2 Thuật tốn khai phá luật kết hợp trọng số chuẩn hóa (MINVAL(W)) 54 Kết luận chƣơng 3: 56 Chƣơng 4: THỰC NGHIỆM KHAI PHÁ LUẬT KẾT HỢP 57 4.1 Giới thiệu toán 57 4.2 Dữ liệu thực nghiệm 58 4.3 Xây dựng chƣơng trình 60 4.4 Thực nghiệm khai phá 61 4.5 Kết thực nghiệm 63 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 63 Những kết đạt đƣợc 63 Hƣớng phát triển đề tài là: 64 TÀI LIỆU THAM KHẢO 65 PHỤ LỤC 67 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải KPDL Khai phá liệu CSDL Cơ sở liệu DB Cơ sở liệu giao tác TID Định danh giao tác I Tập mục liệu T Giao tác (transaction) Ck Tập ứng viên tập mục có k mục liệu Lk Tập tập mục thƣờng xuyên có k mục liệu k-itemset Tập mục gồm k mục BFS Breadth First Search DFS Depth First Search FP-growth Frequent-Pattern Growth FP-tree Frequent pattern tree Sup Độ hỗ trợ (support) Minsup Ngƣỡng hỗ trợ tối thiểu SC(X) Số lƣợng giao dịch chứa tập mục X SRC Kỹ thuật lấy mẫu ngẫu nhiên Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi DANH MỤC CÁC BẢNG BIỂU Bảng 2.1: Danh mục tập mục CSDL 19 Bảng 2.2: Biểu diễn ngang CSDL giao tác 20 Bảng 2.3: Biểu diễn dọc CSDL giao tác 20 Bảng 2.4: Ma trận giao tác CSDL bảng 2.2 21 Bảng 2.5: Cơ sở liệu DB 24 Bảng 2.6: Độ hỗ trợ mục 25 Bảng 2.7: Độ hỗ trợ tập mục 25 Bảng 2.8: Độ tin cậy luật 26 Bảng 2.9: CSDL giao tác minh hoạ cho thuật toán Apriori 31 Bảng 2.10: CSDL giao tác minh hoạ cho thuật toán FP- growth 34 Bảng 3.1.a Tập giao tác DB 48 Bảng 3.1.b Thông tin cửa hàng 48 Bảng 4.1: Dữ liệu trích chọn để khai phá 58 Bảng 4.2: Mã hóa mặt hàng 59 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1 Q trình khám phá tri thức Hình 1.2 Kiến trúc hệ thống khai phá liệu Hình 1.3: Quá trình khai phá liệu Hình 1.4: Mẫu kết với phƣơng pháp định 12 Hình 1.5: Phân cụm đối tƣợng k-Mean ( + tâm cụm) 13 Hình 2.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên 27 Hình 2.2: Cây FP-tree đƣợc xây dựng dần thêm giao tác t1, t2, t3 35 Hình 2.3: Cây FP-tree CSDL DB bảng 2.10 36 Hình 2.4: FP-tree phụ thuộc m 39 Hình 2.5 : Các FP-tree phụ thuộc am, cm cam 39 Hình 4.1: Dữ liệu mã hóa chuẩn bị cho khai phá 60 Hình 4.2: Giao diện chƣơng trình 61 Hình 4.3: Giao diện kết khai phá tập mục thƣờng xuyên 62 Hình 4.4: Giao diện kết khai phá luật kết hợp 62 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỞ ĐẦU Trong năm qua, việc nắm bắt, xử lý đƣợc thông tin đƣợc coi sở hoạt động đời sống xã hội, đặc biệt sản xuất, kinh doanh Những thơng tin tiềm ẩn mang tính dự đốn khối liệu lớn Mỗi cá nhân tổ chức thu thập hiểu đƣợc thông tin, hành động dựa thông tin đƣợc kết xuất từ thơng tin có đạt đƣợc thành cơng hoạt động Chính lý đó, việc tạo thông tin, tổ chức lƣu trữ khai phá ngày trở nên quan trọng gia tăng không ngừng Sự tăng trƣởng vƣợt bậc sở liệu (CSDL) sống nhƣ: thƣơng mại, quản lý khoa học …đã làm nảy sinh thúc đẩy phát triển kỹ thuật thu thập, lƣu trữ, phân tích khai phá liệu khơng phép tốn đơn giản thơng thƣờng nhƣ: phép đếm, thống kê mà đòi hỏi cách xử lý thơng minh hơn, hiệu Từ nhà quản lý có đƣợc thơng tin có ích để tác động lại trình sản xuất, kinh doanh tri thức Các kỹ thuật cho phép ta khai phá đƣợc tri thức hữu dụng từ CSDL (lớn) đƣợc gọi kỹ thuật khai phá liệu (DM – Data Mining) Khai phá luật kết hợp nội dung quan trọng khai phá liệu Một nội dung khai phá liệu thƣờng xuyên phát luật kết hợp kho sở liệu khổng lồ, nhằm tìm tập mục thƣờng xuyên thƣờng xuất đồng thời sở liệu rút luật ảnh hƣởng tập mục thƣờng xuyên dẫn đến xuất (hay tập) mục thƣờng xuyên khác nhƣ nào, khai phá luật kết hợp kho sở liệu có ý nghĩa quan trọng, có lợi ích to lớn việc tổng hợp cung cấp thông tin cần thiết nguồn sở liệu lớn Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 66 Itemset Mining Implementations (FIMI’03) in conjunction with IEEEICDM [11] Grahne G and Zhu J (2003), “Efficient using prefix-tree in mining frequent itemsets”, in Proc IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Melbourne, FL [12] Han J., Cheng H., Xin D., Yan X (2007), “Frequent pattern mining: current status and future directions” Data Min Knowl Disc, Vol 15, pp 55-86 Published online: 27 January 2007 Springer Science+Business Media, LLC 2007 [13] Han J., Pei J., and Yin Y (2000), “Mining frequent patterns without candidate generation”, In ACM SIGMOD Intl Conference on Management of Data, pp 1-12 [14] Kotsiantis S., Kanellopoulos D (2006), “Association Rules Mining: A Recent Overview”, GESTS International Transactions on Computer Science and Engineering, Vol 32, No 1, pp 71-82 [15] A.Tiwari, R.K Gupta and D.P Agrawal (2010) “A Survey on Frequent Pattern Mining: Current Status and Challenging Issues” Information Technology Journal, 9(7), 1278-1293 Asian Network for Scientific Infomation [16] Virendra Kumar Shrivastava, Dr Parveen Kumar, (2010), “FP-tree and COFI Based Approach for Mining of Multiple Level Association Rules in Large Databases” International Journal of Computer Science and Information Security, Vol No Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 67 PHỤ LỤC /* -File: AprioriSets.cpp -*/ #include #include #include #include using namespace std; #include "AprioriSets.h" AprioriSets::AprioriSets() { data=0; minsup=0; remap=0; relist=0; trie = new Item(0); verbose = false; countType = 1; } AprioriSets::~AprioriSets() { if(data) delete data; if(trie) { trie->deleteChildren(); delete trie; } if(remap) delete remap; if(relist) delete relist; } void AprioriSets::setData(char *fn, int type) { data = new Data(fn, type); } int AprioriSets::setOutputSets(char *fn) { setsout.open(fn); if(!setsout.is_open()) { cerr deleteChildren(); set::iterator tmp = runner++; items->erase(tmp); } } } return nodes; } int AprioriSets::countCandidates(int level) { int trans=0; // count all single items if(level==1) { Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 70 while(Transaction *t = data->getNext()) { trie->Increment(); int *iset = t->t, sl = t->length; set *items = trie->makeChildren(); for(int i=0; ifind(item); if(runner == items->end()) runner = (items>insert(item)).first; runner->Increment(); } trans++; delete t; } } else { while(Transaction *t = data->getNext()) { if(t->length >= level) { // Reorder transaction int i; vector list; for(i=0; ilength; i++) { set::iterator it = relist->find(Element(t->t[i])); if(it != relist->end()) list.push_back(it->id); } int size=list.size(); sort(list.begin(), list.end()); delete t; t = new Transaction(size); for(i=0; it[i] = list[i]; if(countType==1 || levelgetChildren(), 0, 1)) trans++; } else { if(processTransaction2(level, t, trie->getChildren(), 0, 1)) trans++; } delete t; } } } return trans; } int AprioriSets::processTransaction2(int level, Transaction *t, set *items, int spos, int depth) { if(items == 0) return 0; int used=0, max = t->length-level+depth; for(set::iterator it = items->begin(); sposend(); it++) { while(spost[spos] < it->getId()) spos++; if(spost[spos]==it->getId()) ) { if(depth==level) { Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 71 it->Increment(); used++; } else used += processTransaction2(level,t,it>getChildren(),spos+1,depth+1); } } return used; } int AprioriSets::processTransaction(int level, Transaction *t, set *items, int spos, int depth) { if(items == 0) return 0; int used=0, *iset = t->t, sl = t->length, loper = spos; set::iterator runner; spos = sl-(level-depth); while( spos >= loper) { runner = items->find(Item(iset[spos])); if(runner != items->end()) { if(depth == level) { runner->Increment(); used++; } else { if(depth==1 && level==2) runner->makeChildren(); used += processTransaction(level, t, runner->getChildren(), spos+1, depth+1); } } else if(depth==2 && level==2) { set *singles = trie->getChildren(); if(singles->find(Item(iset[spos])) != singles->end()) { runner = items->insert(Item(iset[spos])).first; runner->Increment(); used++; } } } return used; } int AprioriSets::pruneCandidates(int level) { int pruned; int *tmp = new int[level]; pruned = pruneCandidates(level,trie->getChildren(),1,tmp); delete [] tmp; return pruned; } int AprioriSets::pruneCandidates(int level, set *items, int depth, int *itemset) { if(items == 0) return 0; int left = 0; for(set::iterator runner = items->begin(); runner != items>end(); ) { itemset[depth-1] = runner->getId(); if(depth == level) { if(runner->getSupport() < minsup) { runner->deleteChildren(); Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 72 set::iterator tmp = runner++; items->erase(tmp); } else { if(setsout.is_open()) printSet(*runner, itemset, depth); left++; runner++; } } else { int now = pruneCandidates(level, runner->getChildren(), depth+1, itemset); if(now) { left += now; runner++; } else { runner->deleteChildren(); set::iterator tmp = runner++; items->erase(tmp); } } } return left; } void AprioriSets::printSet(const Item& item, int *itemset, int length) { set outset; for(int j=0; joldid >= minsup) { remap[i] = itE->id; relist->insert(Element(itE->id,i)); Item a(i); a.Increment(itE->oldid); src->insert(a); i++; } } } Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 73 /* -File: aprioritest.cpp -*/ #include "AprioriSets.h" #include #include int main(int argc, char *argv[]) { cout length) it->Increment(t->support); else trie->Increment(t->support); size = (t->length>size? t->length: size); delete t; } Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 78 if(verbose) cout getSupport()))/(float(runner->getSupport())*float(it>getSupport())); float conf = float(sup)/float(it->getSupport()); if(conf>=minconf) { for(i=0; i