LỜI CẢM ƠN Em xin chân thành cảm ơn thầy giáo, Phó giáo sư, Tiến sĩ Phan T ng a, giám ă Đ đốc trung tâm máy tính trường Đại học Bách Khoa Hà Nội; thầy giáo, Phó giáo sư, Tiến s Nguyĩ ễn Ngọc Bình,, giám đốc trung tâm thư viện iđ ện tử trường Đại học Bách Khoa Hà Nội ã tđ ận tình hướng dẫn và giúp đỡ, cung cấp cho em những ý kiến óng góp, nhđ ận xét quý báu trong quá trình thực hiện đồ án. Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ thông tin c ng nhũ ư các thầy cô giảng dạy trong trường Đại học Bách Khoa Hà Nội, những người ã truyđ ền thụ cho em những kiến thức quí báu trong suốt thời gian học tập và nghiên cứu tại trường, giúp em có được những iđ ều kiện cần thiết để hoàn thành tốt đồ án này. Sự quan tâm và giúp đỡ của Bố mẹ, cùng toàn thể gia ình là mđ ột nguồn động viên rất lớn, tạo cho con sự yên tâm về vật chất và tinh thần để con hoàn thành nhiệm vụ của mình. Cuối cùng xin cảm ơn sự quan tâm và óng góp ý kiđ ến của tất cả các bạn. Hà Nội ngày 15 tháng 05 năm 2004 Sinh viên Hoàng Thị Minh Thu Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng DANH MỤC TỪ VIẾT TẮT Số TT Từ viết tắt Giải nghĩa 1 CD Count Distribution 2 CSDL cơ sở dữ liệu 3 DB Database 4 DBMS Database Management System 5 DD Data Distribution 6 DHP Direct Hashing and Puning 7 DIC Dynamic Itemset Counting 8 FDM Fast Distributed Mining of Association rules 9 FP-Tree Frequent Pattern Tree 10 KDD Knowledge Discovery from Data 11 K-NN K- Nearest Neighbor 12 MFCS maximum frequent candidate set 13 MFS maximum frequent set 14 SET set-enumeration-tree 15 SETM Set-Oriented Mining for Association Rules. 16 SP2 Scallable POWER parallel System 17 TID Transaction identifier Hoàng Thị Minh Thu, CNPM K44 2 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng DANH MỤC CÁC THUẬT NGỮ Số TT Thuật ngữ Giải nghĩa 1 basket data dữ liệu các mặt hàng mua bán trong giao dịch 2 Candidate Distribution Phân phối candidate 3 candidate group nhóm candidate được sử dụng trong thuật toán MaxMiner 4 candidate itemset Một itemset trong tập C k được dùng để sinh ra các large itemset 5 confidence tỷ số support(X ∪ Y) / support(X) phản ánh khả năng giao dịch hỗ trợ X thì cũng hỗ trợ Y 6 Count Distribution phân phối số đếm 7 Data Distribution phân phối dữ liệu 8 frequent itemset itemset có giá trị support không nhỏ hơn minsup 9 frequent itemset maximal Itemset frequent mà không có bất kỳ superset nào của nó là frequent itemset 10 Interesting itemset itemset đáng quan tâm 11 Itemset tập các item 12 k-itemset itemset có k phần tử 13 k-subset một tập con của một giao dịch có chứa k item 14 large itemset itemset có giá trị support không nhỏ hơn minsup 15 long frequent itemset Itemset frequent dài 16 maximum frequent set Tập các frequent itemset tối đa 17 minconf confidence tối thiểu 18 minsup support tối thiểu 19 p’s conditional pattern base Cơ sở pattern điều kiện của p là các cơ sở sub- pattern của p 20 set-enumeration-tree Cây đánh số thứ tự tập 21 subset tập các phần tử là tập con của một tập cho trước 22 superset tập cha 23 support(X) phần trăm giao dịch trong CSDL có chứa itemset X 24 transaction một giao dịch trong cơ sở dữ liệu 25 Transaction identifier Định danh duy nhất của một giao dịch 26 trie một cấu trúc dữ liệu dạng hash tree mà mỗi node gắn trên nó có chứa các thông tin bổ sung. Hoàng Thị Minh Thu, CNPM K44 3 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng DANH MỤC HÌNH VẼ Hình 1: Quá trình khai phá dữ liệu 11 Hình 2 : Cây quyết định với Temperature làm node gốc 17 Hình 3: Cây quyết định với Outlook làm node gốc 17 Hình 4: Các dạng biểu diễn khác nhau của I = {a,b,c,d,e} 24 Hình 5: Thủ tục sinh luật đơn giản 27 Hình 6: Thủ tục sinh luật nhanh 28 Hình 7: Thuật toán AIS 30 Hình 8: Thuật toán SETM 31 Hình 9: Thuật toán Apriori 32 Hình 10: Hàm sinh tập candidate của thuật toán Aprirori 33 Hình 11: Thuật toán AprioriTID 34 Hình 12: Chương trình chính của thuật toán DHP 38 Hình 13: Các thủ tục của thuật toán DHP 39 Hình 14: Ví dụ về bảng băm và phép sinh C2 40 Hình 15: Cắt tỉa đối với L2 41 Hình 16: Thuật toán DIC 44 Hình 17: Thủ tục tăng số đếm cho giao dịch 45 Hình 18: Thuật toán Pincer- Search 46 Hình 19: SET đầy đủ trên bốn item 47 Hình 20: Thuật toán Max-Miner 48 Hình 21: Minh hoạ kết quả giảm support từ việc mở rộng itemset I và Is với i 50 Hình 22: Sinh subset và tính toán với giới hạn dưới 51 Hình 23: Thuật toán sinh FP-Tree 52 Hình 24: Một ví dụ của FP-Tree 53 Hình 25: Xây dựng FP-Tree từ m “FP-Tree |m” 55 Hình 26: Thuật toán FPGrowth 57 Hình 27: So sánh tốc độ thực hiện giữa FPGrowth và Apriori 58 Hình 28: ReduceScatter and AllGather Communication 63 Hình 29:Thuật toán FDM-LP 77 Hình 30: Mô hình chung hệ thống 79 Hình 31: Kiến trúc hệ thống ARMiner 80 Hình 32: Biểu đồ phân cấp chức năng 81 Hình 33: Định dạng tệp giao dịch 82 Hình 34: Tệp dữ liệu đầu ra 82 Hình 35: Các môđun dùng trong hệ thống 84 Hình 36: Sơ đồ lớp mô tả các chức năng 84 Hình 37: Định dạng tệp từ điển cải tiến 86 Hình 38: Giao diện chính của chương trình 87 Hoàng Thị Minh Thu, CNPM K44 4 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng DANH MỤC BẢNG Bảng 1: Các thuộc tính 21 Bảng 2 : Ký hiệu 32 Bảng 3: Tập và Lk qua các giai đoạn 1, 2, 3 35 Bảng 4: Cơ sở dữ liệu giao dịch của ví dụ về FP-Tree 52 Bảng 5: Khai phá tất cả các pattern bởi tạo ra cơ sở (sub)-pattern điều kiện 55 Bảng 6: Bảng ký hiệu 71 Bảng 7: Large itemset cục bộ 71 Bảng 8: Large itemset toàn cục 72 Bảng 9: Số đếm support cục bộ 74 Bảng 10: Các tham số để sinh tập dữ liệu giả 85 Hoàng Thị Minh Thu, CNPM K44 5 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng MỤC LỤC LỜI CẢM ƠN 1 DANH MỤC TỪ VIẾT TẮT 2 DANH MỤC CÁC THUẬT NGỮ 3 DANH MỤC HÌNH VẼ 4 DANH MỤC BẢNG 5 MỤC LỤC 6 LỜI MỞ ĐẦU 8 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 10 1.1.Các bước của quá trình khai phá dữ liệu: 10 1.2.Nhiệm vụ chính của khai phá dữ liệu 12 1.3. Khai phá dữ liệu mô tả 13 1.3.1.Phân nhóm 13 1.4. Khai phá dữ liệu dự đoán 14 1.4.1.Bài toán phân loại 14 1.4.2.Cây quyết định 15 1.4.3.K – Láng giềng (K – Nearest Neighbor) [17] 19 1.5. Tại sao khai phá luật kết hợp lại quan trọng 20 Chương 2: KHAI PHÁ LUẬT KẾT HỢP 23 2.1.Các định nghĩa cơ bản: 23 2.1.1. Itemset: 23 2.1.2. Cơ sở dữ liệu [1], [15] 23 2.1.3. Support 24 2.1.4.Luật kết hợp: 25 2.2.Giới thiệu bài toán 26 1.2.1.Bài toán 1: Khai phá các large itemset: 26 1.2.2.Bài toán 2: Sinh luật từ các large itemset: 27 Chương 3: CÁC THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP 29 3.1.Các thuật toán nguyên thuỷ 30 3.1.1.AIS [3] 30 3.1.2. SETM [3] 31 3.2. Các thuật toán Apriori [4] 32 3.2.1.Thuật toán Apriori 32 3.2.2.Thuật toán AprioriTID: 34 3.2.3.Thuật toán AprioriHybrid 36 3.3.Thuật toán DHP (Direct Hashing and Pruning) [16] 37 3.4.Thuật toán DIC (Dynamic Counting Itemset) [6] 42 3.5.Thuật toán Pincer-Search [10] 45 3.6.Thuật toán khai phá các mẫu dài từ CSDL (Max-Miner) [14] 46 3.6.1.Max-Miner hình thức 47 3.6.2.Cách sắp thứ tự item 48 3.6.3.Yêu cầu về tính chính xác và hiệu quả 49 3.6.4.Giới hạn dưới của support 49 3.7.Thuật toán FPGrowth [9] 51 3.7.1.Thuật toán xây dựng FP - Tree 51 3.7.2.Khai phá các frequent pattern sử dụng FP-Tree 53 3.7.3.Đánh giá mô hình 57 3.8.Kết luận 58 Chương 4: KHAI PHÁ LUẬT KẾT HỢP SONG SONG TRÊN CƠ SỞ DỮ LIỆU PHÂN TÁN 60 4.1.Kiến trúc không chia sẻ bộ nhớ [5] , [11] 60 Hoàng Thị Minh Thu, CNPM K44 6 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng 4.1.1.Thuật toán Count Distribution (Phân phối số đếm) 62 4.1.2.Thuật toán Data Distribution (Phân phối dữ liệu) 64 4.1.3. Thuật toán Candidate Distribution (Phân phối candidate) 65 4.1.4.Sinh luật song song 67 4.2.Kiểu kiến trúc chia sẻ bộ nhớ chung [8] 68 4.2.1.Các kỹ thuật khai phá dữ liệu phân tán 69 4.2.2.Thuật toán khai phá luật kết hợp phân tán 76 Chương 5: XÂY DỰNG GIẢI PHÁP VÀ THỬ NGHIỆM KẾT QUẢ 79 Tổng quan về hệ thống 79 5.1.1.Mô tả hệ thống 79 5.1.2.Kiến trúc hệ thống 80 5.1.3.Mô tả chức năng 80 5.1.4.Cấu trúc dữ liệu 81 Giải pháp, cài đặt 82 5.2.1.Môi trường, công cụ, ngôn ngữ sử dụng 82 5.2.2.Lựa chọn thuật toán 83 5.2.3.Thiết kế môđun 84 5.2.4.Sinh tập dữ liệu giả 85 5.2.5.Cải tiến 85 Kết quả thử nghiệm và đánh giá 87 5.3.1.Giao diện chương trình: 87 5.3.2.Cơ sở dữ liệu thử 89 5.3.3.Đánh giá kết quả 90 Thông tin rút ra từ dữ liệu thử 91 5.4.1.Teldata 92 5.4.2.Bảo Việt: 92 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 95 TÀI LIỆU THAM KHẢO 96 CHỈ MỤC TỪ 98 Hoàng Thị Minh Thu, CNPM K44 7 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng LỜI MỞ ĐẦU Ngày nay, cơ sở dữ liệu có kích thước lên tới Terabyte — hơn 1,000,000,000,000 byte dữ liệu. Bên trong khối lượng dữ liệu lớn như vậy còn ẩn chứa rất nhều thông tin quan trọng. Khai phá dữ liệu (data mining) là một quá trình sử dụng rất nhiều công cụ phân tích dữ liệu để phát hiện ra các mẫu và các mối quan hệ trong dữ liệu để đưa ra được những dự đoán hiệu quả. Nhiệm vụ chính của data mining là phát hiện ra các tri thức chưa được phát hiện hay còn ẩn chứa trong tập dữ liệu lớn. Những tiến bộ gần đây trong việc thu thập và lưu trữ dữ liệu đã được áp dụng trong các công ty (kỹ thuật mã vạch), các cơ quan hành chính (dữ liệu điều tra) hay các phòng thí nghiệm khoa học (CSDL phân tử trong hoá học hay sinh học) để lưu giữ được một lượng lớn các dữ liệu liên quan đến hoạt động của các tổ chức này. Cùng thời gian này, khả năng dùng nguồn năng lượng tính toán rẻ để trích rút tự động tri thức có cấu trúc từ dữ liệu đã tập hợp được này một cách dễ dàng. Những hoạt động như vậy đều được coi như khai phá dữ liệu. Khai phá dữ liệu bao gồm những lĩnh vực như phân loại, chia nhóm, phân tích sự tương đồng, tóm tắt nội dung, khai phá luật kết hợp và khai phá các mẫu tuần tự… Vấn đề khai phá luật kết hợp lần đầu tiên được đưa ra giới thiệu vào năm 1993 nhưng đã nhanh chóng phát triển mạnh mẽ. Vậy lý do vì sao ? Hãy xem xét một CSDL lớn các mặt hàng, mỗi giao dịch bao gồm các mặt hàng mua bán của khách hàng. Vấn đề khai phá luật kết hợp được áp dụng nhiều nhất trong các quyết định kinh doanh, điển hình trong việc quản lý siêu thị như: mặt hàng gì cần hạ giá, thiết kế phiếu mua hàng như thế nào hay sắp xếp các mặt hàng ra sao để có lợi nhuận lớn nhất. Việc phân tích các dữ liệu trong quá khứ là cách tiếp cận thường được sử dụng nhằm nâng cao chất lượng mua hàng. Tuy nhiên, gần đây chỉ những số liệu tích luỹ theo định kỳ thời gian là được lưu lại trên máy tính. Sự tiến bộ trong kỹ thuật mã vạch đã giúp lưu trữ các basket data - dữ liệu các mặt hàng mua bán trong mỗi giao dịch một cách hiệu quả. Luật kết hợp đã được sử dụng trong rất nhiều ứng dụng như: phân tích giao dịch trong siêu thị, phân tích cách bố trí cách lưu trữ cũng như xu thế các mặt hàng, phân tích số liệu tuyển sinh đại học, phân tích thói quen khách hàng, phân loại khách hàng dựa vào mặt hàng mua bán, thiết kế catalog, phân tích sự xuất hiện của từ trong một tài liệu văn bản, sự ghé thăm vào các trang WWW của người dùng, giao dịch chứng khoán… Sự hấp dẫn của việc phân tích tình hình thị trường bắt nguồn từ tính rõ ràng và tính thiết thực của các kết quả được rút ra từ các luật kết hợp. Phân tích tình hình thị Hoàng Thị Minh Thu, CNPM K44 8 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng trường biểu diễn cách thức các sản phẩm và các dịch vụ liên quan với nhau, chúng có xu hướng lập nhóm với nhau như thế nào. Một luật có dạng “Nếu khách hàng mua bột giặt OMO thì khách hàng đó sẵn sàng trả tiền mua nước xả Comfor” là hoàn toàn rõ ràng. Hiện nay, khai phá luật kết hợp ngày càng được ứng dụng rộng rãi trong thực tế và đã được đưa vào nghiên cứu trong lĩnh vực y tế và sinh tin học. Như các siêu thị có thể áp dụng bài toán này để có quy cách trưng bày sản phẩm hợp lý. Viện Khoa học công nghệ, viện công nghệ thông tin JAIST của Nhật đã ứng dụng luật kết hợp để nghiên cứu và chẩn đoán triệu chứng của bệnh nhân đau dạ dày rất hiệu quả. Các nhà kinh tế có thể dự đoán được xu thế kinh tế, tâm lý khách hàng…. Và gần đây, Carlos Ordonez [12] , năm 2000 đã nghiên cứu về việc khai phá luật kết hợp có ràng buộc để dự đoán bệnh đau tim ở người. Chính vì những ý nghĩa thiết thực đó của bài toán khai phá luật kết hợp, em đã quyết định chọn đề tài tốt nghiệp của mình là “Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng”. Đồ án này sẽ tập trung vào tìm hiểu và nghiên cứu về các thuật toán khai phá luật kết hợp. Nội dung chính của đồ án được trình bày trong 5 chương : Chương 1: Tìm hiểu tổng quan chung về các kỹ thuật khai phá dữ liệu. Đi sâu vào các bài toán cụ thể như cây quyết định, K-láng giềng, Chương 2: Nghiên cứu các vấn đề lý thuyết liên quan đến việc khai phá luật kết hợp. Chương 3: Các thuật toán khai phá luật kết hợp nhanh được xem xét và đánh giá so sánh với nhau. Chương 4: Nghiên cứu các thuật toán kết hợp song song trên cơ sở dữ liệu phân tán Chương 5: Xây dựng giải pháp và thử nghiệm kết quả với các thuật toán khai phá luật kết hợp đã cài đặt. Kết luận: Nêu ra các nhận xét, kết quả đạt được và một số phương hướng phát triển tiếp theo của đề tài. Hoàng Thị Minh Thu, CNPM K44 9 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Phần đầu của chương sẽ đề cập tới các bước thực hiện của quá trình khai phá dữ liệu và tổng quan các kỹ thuật khai phá. Phần sau sẽ đi sâu vào một số kỹ thuật khai phá được sử dụng phổ biến hiện nay cũng như những vấn đề mà các kỹ thuật này còn chưa giải quyết được. Khi điện tử và sóng điện từ đã trở thành vấn đề cốt lõi của công nghệ điển tử cổ điển thì ta thấy rằng dữ liệu, thông tin, tri thức đang là lĩnh vực tập trung nhiều nghiên cứu và ứng dụng – phát hiện tri thức và khai phá dữ liệu (knowledge discovery and data mining: KDD). Nói chung, ta thường biết dữ liệu là một chuỗi các bit, số hay ký tự hoặc đối tượng cần quan tâm. Ta sử dụng các bít để đánh giá thông tin. Tri thức được xem như là thông tin tổ hợp, bao gồm các sự thật và mối liên quan giữa chúng, có thể thu nhận, khám phá và học được. Nói cách khác, tri thức là dữ liệu ở mức cao của sự trừu tượng và tổng quát hoá. KDD là lĩnh vực phát triển nhanh chóng, kết hợp với hệ quản trị CSDL, các lĩnh vực thống kê, học máy và các lĩnh vực liên quan khác. Phát hiện tri thức là một quá trình chỉ ra được các mô hình/mẫu hiểu được có giá trị và đáng quan tâm. Data mining là một bước trong quá trình phát hiện tri thức, bao gồm các thuật toán khai phá dữ liệu cụ thể với hiệu năng tính toán chấp nhận được để tìm ra các mẫu hay mô hình của dữ liệu. Nói cách khác, mục đích của khai phá và phát hiện tri thức là tìm ra các mẫu hay mô hình đáng quan tâm có trong CSDL nhưng đang ẩn dấu trong một lượng lớn dữ liệu. 1.1. Các bước của quá trình khai phá dữ liệu: Các giải thuật khai phá dữ liệu thường được miêu tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp máy học và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết suất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình xử lý khai phá dữ liệu bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho các giải thuật khai phá dữ liệu có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải nhiều vướng mắc Hoàng Thị Minh Thu, CNPM K44 10 [...]... sinh luật nhanh Do bài toán 2 thực hiện khá đơn giản, nên hiệu quả của bài toán khai phá luật kết hợp phụ thuộc rất nhiều vào sự thực hiện của bài toán 1 Trong chương 3, ta sẽ đi sâu nghiên cứu các thuật toán khai phá luật kết hợp khác nhau Đa phần các thuật toán tập trung vào việc nâng cao tốc độ thực hiện của bài toán khai phá large itemset Mỗi thuật toán này đều có những xử lý và các cách cải tiến thuật. .. Hình 7: Thuật toán AIS Hoàng Thị Minh Thu, CNPM K44 30 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng 3.1.2 SETM [3] Thuật toán SETM được xuất phát từ nhu cầu muốn sử dụng SQL để tính toán các large itemset Giống như AIS, thuật toán SETM cũng sinh ra các candidate ngay sau khi đọc các giao dịch từ CSDL Nhằm sử dụng được toán tử kết nối chuẩn join của SQL đối với việc sinh các candidate,... candidate itemset và là thuật toán khai phá luật kết hợp nguyên thuỷ nhất Sau đó, họ thuật toán Apriori [4] được đưa ra, đã chỉ rõ bài toán cụ thể của khai phá luật kết hợp Thuật toán Apriori đã trở thành thuật toán khuôn mẫu của bài toán khai phá luật kết hợp Apriori giới thiệu một cấu trúc lưu trữ các candidate itemset là hashtree nhằm lưu trữ chỉ số của một danh sách các đối tượng itemset để công việc xử... toán khai phá luật kết hợp nhanh và ứng dụng Chương 3: CÁC THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP Do việc sinh luật kết hợp có ý nghĩa rất lớn trong thực tiễn, hiện nay ngày càng có nhiều thuật toán khai phá luật kết hợp khác nhau Các thuật toán luôn luôn được cải tiến để nâng cao hiệu quả thực hiện về cấu trúc lưu trữ, tốc độ thực hiện, dung lượng lưu trữ và tránh hiện tượng thắt cổ chai bộ nhớ AIS và SETM... large itemset và đưa chúng vào giai đoạn duyệt tiếp theo Quá trình này sẽ được tiếp tục cho đến khi không xác định được thêm bất kỳ large itemset mới nào Hoàng Thị Minh Thu, CNPM K44 26 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng Các thuật toán AIS, SETM và các thuật toán họ Apriori đều nhằm giải quyết bài toán khai phá large itemset này 1.2.2 Bài toán 2: Sinh luật từ các large itemset:... nhóm kia • Khai phá luật kết hợp (Association Rule): tìm ra các large itemset, các mối liên quan, kết hợp và cấu trúc nhân quả trong tập các khoản mục hay đối tượng trong CSDL giao dịch, CSDL quan hệ hay từ các kho lưu trữ thông tin khác Hoàng Thị Minh Thu, CNPM K44 12 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng • Tóm tắt (Summarization) : Liên quan đến các phương pháp tìm kiếm... khoảng cách giữa các thuộc tính dữ liệu và tính toán nó Trong khi điều này là rất đơn giản với dữ Hoàng Thị Minh Thu, CNPM K44 19 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng liệu số, biến phân loại cần phải được xử lý đặc biệt hơn Như khoảng cách giữa màu xanh và màu đỏ là gì? Phải có cách để tính tổng khoảng cách giữa các thuộc tính Mỗi khi tính toán khoảng cách giữa các trường hợp, ... sát Một trong các ứng dụng của bài toán này là khi ngân hàng muốn phát triển một cơ chế tự động có thể quyết định được rằng một ứng dụng sử dụng thẻ tín dụng có được chấp nhận hay không dựa trên các bản ghi dữ liệu của các khách hàng đã có Hoàng Thị Minh Thu, CNPM K44 14 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng Hay một ứng dụng khác là: Một bệnh viện muốn chẩn đoán một bệnh nhân... tránh được chi phí cao do các lần duyệt CSDL, tránh chi phí tốn kém trong việc sinh một lượng lớn tập các candidate Với việc phân nhỏ bài toán khai phá thành tập các công việc nhỏ hơn nhằm khai phá các pattern đã dược giới hạn trong cơ sở pattern điều kiện, không gian tìm kiếm của thuật toán được giảm xuống nhanh chóng Hoàng Thị Minh Thu, CNPM K44 29 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh. .. cholesterol Các luật 5, 6, 7 được xác nhận có tỷ lệ rủi ro mắc bệnh tim cao với độ chính xác cao Về cơ bản nếu một bệnh nhân cao tuổi, hàm lượng cholesterol cao và có phát hiện perfusion thì hầu như chắc chắn rằng người đó có tình trạng tim mạch rất nguy hiểm… Hoàng Thị Minh Thu, CNPM K44 22 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng Chương 2: KHAI PHÁ LUẬT KẾT HỢP Bài toán khai phá luật . luật kết hợp, em đã quyết định chọn đề tài tốt nghiệp của mình là Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng . Đồ án này sẽ tập trung vào tìm hiểu và nghiên cứu về các. từ các luật kết hợp. Phân tích tình hình thị Hoàng Thị Minh Thu, CNPM K44 8 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng trường biểu diễn cách thức các sản phẩm và các dịch. K44 6 Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng 4.1.1 .Thuật toán Count Distribution (Phân phối số đếm) 62 4.1.2 .Thuật toán Data Distribution (Phân phối dữ liệu) 64 4.1.3. Thuật