Đăng ký Đăng nhập
Trang chủ Một số phương pháp khai phá dữ liệu sinh luật kết hợp...

Tài liệu Một số phương pháp khai phá dữ liệu sinh luật kết hợp

.PDF
83
169
83

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN VĨNH HOÀNG MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU SINH LUẬT KẾT HỢP LUẬN VĂN THẠC SĨ Hà Nội - 2007 1 Mục lục Lời cảm ơn ..................................................................................................................... 6 MỞ ĐẦU ........................................................................................................................ 7 1. Chương 1: Tổng quan về khai phá dữ liệu (KPDL) .............................................. 9 1.1. Khái niệm....................................................................................................................... 9 1.2. Các hướng tiếp cận chính trong KPDL .................................................................... 10 1.3. Một số phương pháp KPDL phổ biến ....................................................................... 10 1.3.1. Phương pháp suy diễn và quy nạp ..................................................................... 10 1.3.2. Cây quyết định và luật ........................................................................................ 10 1.3.3. Phát hiện các luật kết hợp .................................................................................. 11 1.3.4. Phân nhóm và phân đoạn ................................................................................... 11 1.3.5. Mạng Neural ........................................................................................................ 12 1.3.6. Giải thuật di truyền ............................................................................................. 12 1.4. Lựa chọn các kỹ thuật khai phá ................................................................................ 13 1.5. Các dạng CSDL thường được sử dụng để KPDL .................................................... 14 1.6. Một số ứng dụng của KPDL ...................................................................................... 14 2. Chương 2: Một số vấn đề cơ bản về Luật kết hợp ............................................... 16 2.1. Định nghĩa luật kết hợp .............................................................................................. 16 2.1.1. Ví dụ về luật kết hợp ........................................................................................... 16 2.1.2. Các định nghĩa và tính chất ................................................................................ 16 2.1.2.1. Các định nghĩa cơ bản ..................................................................................... 16 2.1.2.2. Một số tính chất của tập mục phổ biến ............................................................. 19 2.1.2.3. Một số tính chất của luật kết hợp ..................................................................... 19 2.2. Các loại luật kết hợp và hướng tiếp cận ................................................................... 20 2.2.1. Luật kết hợp nhị phân ........................................................................................ 20 2.2.2. Luật kết hợp định lượng ..................................................................................... 20 2.2.2.1. Giới thiệu ........................................................................................................ 20 2.2.2.2. Khai phá luật kết hợp định lượng ..................................................................... 20 2.2.3. Luật kết hợp đơn chiều ....................................................................................... 22 2.2.4. Luật kết hợp đa chiều ......................................................................................... 22 2.2.5. Luật kết hợp đa mức ........................................................................................... 22 2.2.5.1. Giới thiệu ........................................................................................................ 22 2.2.5.2. Khai phá luật kết hợp đa mức .......................................................................... 24 2.2.6. Luật kết hợp với thuộc tính có trọng số ............................................................ 27 2.2.7. Luật kết hợp mờ .................................................................................................. 27 2.2.8. Luật kết hợp đóng ............................................................................................... 27 Một số phương pháp khai phá dữ liệu sinh luật kết hợp 2 3. Chương 3: Một số phương pháp KPDL sinh luật kết hợp .................................. 29 3.1. Thuật toán Apriori...................................................................................................... 29 3.1.1. Giới thiệu .............................................................................................................. 29 3.1.2. Thuật toán ............................................................................................................ 33 3.1.3. Nâng cao hiệu quả của thuật toán Apriori........................................................ 35 3.1.3.1. Sử dụng kỹ thuật băm ...................................................................................... 35 3.1.3.2. Rút gọn số giao dịch sau mỗi lần quét CSDL ................................................... 37 3.1.3.3. Phân hoạch (Partitioning) ................................................................................ 37 3.1.3.4. Lấy mẫu (Sampling) ........................................................................................ 38 3.1.4. Sinh luật kết hợp từ tập mục phổ biến .............................................................. 39 3.1.4.1. Thuật toán đơn giản sinh luật kết hợp từ tập mục phổ biến............................... 39 3.1.4.2. Thuật toán nhanh hơn sinh luật kết hợp từ tập mục phổ biến ............................ 40 3.2. Thuật toán FP-Growth ............................................................................................... 42 3.2.1. Giới thiệu .............................................................................................................. 42 3.2.2. Thuật toán ............................................................................................................ 47 3.2.3. Tổng kết ................................................................................................................ 49 3.3. Thuật toán Charm ...................................................................................................... 50 3.3.1. Giới thiệu .............................................................................................................. 50 3.3.1.1. Một số khái niệm ............................................................................................. 50 3.3.1.2. Toán tử đóng và tập đóng ................................................................................ 52 3.3.1.3. Cây tìm kiếm “tập mục – tập định danh” và Lớp tương đương ......................... 53 3.3.2. Thuật toán ............................................................................................................ 56 3.3.3. Sinh luật kết hợp từ tập mục đóng phổ biến .................................................... 59 3.3.4. Tổng kết ................................................................................................................ 60 3.4. Thuật toán Closet ........................................................................................................ 63 3.4.1. Giới thiệu .............................................................................................................. 63 3.4.2. Thuật toán ............................................................................................................ 67 3.4.3. Tổng kết ................................................................................................................ 68 4. Chương 4: Xây dựng ứng dụng minh hoạ ............................................................ 70 4.1. Giới thiệu ..................................................................................................................... 70 4.2. Phân tích và Thiết kế hệ thống .................................................................................. 71 4.3. Cài đặt và Đánh giá .................................................................................................... 79 KẾT LUẬN .................................................................................................................. 80 Danh sách tài liệu tham khảo tiếng Việt ..................................................................... 82 Danh sách tài liệu tham khảo tiếng Anh ..................................................................... 82 Danh sách WebSites tham khảo ................................................................................... 83 Phụ lục (Mã nguồn chương trình) ............................................................................... 83 Một số phương pháp khai phá dữ liệu sinh luật kết hợp 5 Ký hiệu và Từ viết tắt Stt 1 2 3 4 5 Ký hiệu viết tắt CSDL HQTCSDL KPDL KDD đpcm Nghĩa tiếng Việt Cơ sở dữ liệu Hệ quản trị cơ sở dữ liệu Khai phá dữ liệu Khai phá tri thức Điều phải chứng minh Một số phương pháp khai phá dữ liệu sinh luật kết hợp Nghĩa tiếng Anh Database Database Management System Data Mining Knowledge Discovery in Database 3 Danh sách các bảng trong luận văn Bảng 2.1: Ví dụ một CSDL giao dịch. .............................................................................17 Bảng 2.2: Ví dụ về các tập mục phổ biến. ........................................................................17 Bảng 2.3: Các luật kết hợp được sinh từ tập mục phổ biến ACW.....................................19 Bảng 2.4: Dữ liệu điều tra dân số.....................................................................................21 Bảng 2.5: Danh sách thuộc tính sau khi rời rạc hoá. ........................................................22 Bảng 2.6: Ví dụ CSDL giao dịch bán hàng. .....................................................................23 Bảng 3.1: Ký hiệu mô tả trong thuật toán Apriori. ...........................................................30 Bảng 3.2: Cơ sở dữ liệu minh hoạ thuật toán Apriori. ......................................................31 Bảng 3.3: Thuật toán Apriori. ..........................................................................................34 Bảng 3.4: Thủ tục Apriori_Gen. ......................................................................................34 Bảng 3.5: Thủ tục Has_Infrequent_Subset. ......................................................................35 Bảng 3.6: Thủ tục tính tích luỹ độ hỗ trợ của các ứng cử là tập con của giao dịch t. ........37 Bảng 3.7: Thuật toán đơn giản sinh luật kết hợp từ tập mục phổ biến. .............................40 Bảng 3.8: Thủ tục GenRules. ...........................................................................................40 Bảng 3.9: Thuật toán nhanh hơn sinh luật kết hợp từ tập mục phổ biến. ..........................40 Bảng 3.10: Thủ tục Ap_GenRules. ..................................................................................41 Bảng 3.11: Cơ sở dữ liệu minh hoạ thuật toán FP-Growth. ..............................................43 Bảng 3.12: Mô tả cây FP-tree. .........................................................................................43 Bảng 3.13: Kết quả khai phá dữ liệu bởi thuật toán FP-Growth. ......................................46 Bảng 3.14: Thủ tục thêm 1 tập mục vào FP-tree. .............................................................47 Bảng 3.15: Thủ tục tạo cây FP-tree T từ CSDL D. ...........................................................47 Bảng 3.16: Thủ tục tạo CSDL phụ thuộc mẫu từ cây T. ...................................................48 Bảng 3.17: Thủ tục FP_Growth. ......................................................................................48 Bảng 3.18: Cơ sở dữ liệu minh hoạ thuật toán Charm. .....................................................51 Bảng 3.19: Mô tả cây IT-tree. ..........................................................................................54 Bảng 3.20: Thuật toán Charm. .........................................................................................56 Bảng 3.21: Thủ tục Charm_Extend. .................................................................................57 Bảng 3.22: Thủ tục Charm_Property. ..............................................................................57 Bảng 3.23: Thủ tục Subsumption_Check. ........................................................................58 Bảng 3.24: Thủ tục GenAllClosedRules. .........................................................................60 Bảng 3.25: Cơ sở dữ liệu minh hoạ thuật toán Closet. .....................................................63 Bảng 3.26: Thủ tục ClosetMining. ...................................................................................67 Bảng 3.27: Thủ tục Closet. ..............................................................................................67 Bảng 4.1: Cấu trúc file dữ liệu RawDataFile. ..................................................................70 Bảng 4.2: Cấu trúc file dữ liệu StandardData. ..................................................................72 Bảng 4.3: Cấu trúc file ItemMap. ....................................................................................73 Một số phương pháp khai phá dữ liệu sinh luật kết hợp 4 Bảng 4.4: Cấu trúc file DirectData. ..................................................................................73 Bảng 4.5: Cấu trúc file DirectItemsets. ............................................................................73 Bảng 4.6: Cấu trúc file StandardItemsets. ........................................................................73 Bảng 4.7: Cấu trúc file DirectRules. ................................................................................74 Bảng 4.8: Cấu trúc file StandardRules. ............................................................................74 Bảng 4.9: Cấu trúc file ActualRules. ...............................................................................74 Bảng 4.10: Cấu trúc file CompareInfo. ............................................................................75 Danh sách các hình vẽ trong luận văn Hình 1.1: Các bước trong quá trình KDD. ........................................................................ 9 Hình 2.1: Sự phân cấp mức độ trừu tượng của dữ liệu. ....................................................23 Hình 2.2: Khai phá luật kết hợp đa mức với minsup giống nhau tại các mức. ..................24 Hình 2.3: Khai phá luật kết hợp đa mức với minsup giảm dần. ........................................25 Hình 2.4: Khai phá luật kết hợp đa mức với minsup giảm dần kết hợp lọc.......................25 Hình 2.5: Khai phá luật kết hợp đa mức với minsup giảm dần kết hợp lọc k-mục. ...........26 Hình 3.1: Minh hoạ thuật toán Apriori. ............................................................................32 Hình 3.2: Minh hoạ cây băm (Hash tree). ........................................................................36 Hình 3.3: Sơ đồ khai phá bằng phân hoạch dữ liệu. .........................................................38 Hình 3.4: Minh hoạ xây dựng cây FP-tree. ......................................................................45 Hình 3.5: So sánh FP-Growth và Apriori. ........................................................................49 Hình 3.6: Cây IT-tree (Itemset-Tidset Search Tree). ........................................................54 Hình 3.7: Minh hoạ thuật toán Charm. .............................................................................58 Hình 3.8: So sánh Charm với Apriori, Close, Pascal, Mafia và Closet. ............................61 Hình 3.9: Minh hoạ thuật toán Closet. .............................................................................64 Hình 3.10: So sánh Closet với A-Close và Charm. ..........................................................68 Hình 4.1: Mô hình quan hệ CSDL đơn hàng thực tế. .......................................................70 Hình 4.2: Sơ đồ luồng dữ liệu trường hợp dùng thuật toán cụ thể. ...................................71 Hình 4.3: Sơ đồ luồng dữ liệu trường hợp so sánh các thuật toán.....................................72 Hình 4.4: Màn hình nhập liệu dạng Text. .........................................................................76 Hình 4.5: Màn hình nhập liệu dạng Grid (Visual). ...........................................................76 Hình 4.6: Màn hình tiến trình thực hiện khai phá dữ liệu. ................................................77 Hình 4.7: Màn hình tiến trình so sánh các giải thuật. .......................................................77 Hình 4.8: Màn hình kết quả khai phá dữ liệu dạng Text. ..................................................78 Hình 4.9: Màn hình kết quả khai phá dữ liệu dạng Grid (Visual). ....................................78 Một số phương pháp khai phá dữ liệu sinh luật kết hợp 7 MỞ ĐẦU Ngày nay với một Hệ quản trị cơ sở dữ liệu (HQTCSDL) mạnh, các doanh nghiệp có thể dễ dàng tổ chức, lưu trữ hàng triệu hồ sơ khách hàng, hợp đồng, số liệu kinh doanh, công văn, chứng từ, tài liệu, ... cũng như khai thác chúng một cách có hiệu quả. Có thể nói rằng với ngôn ngữ truy vấn SQL, các HQTCSDL ngày nay có thể đáp ứng được khoảng 80% nhu cầu khai thác thông tin của con người. Tuy nhiên, chỉ có một chuyên viên phân tích thị trường đầy kinh nghiệm mới có thể đưa ra được những kết luận đại loại như: “Khách hàng ở độ tuổi 18-22 khi mua hoa và quà lưu niệm thường mua thêm thiệp” hay “Khi giá dầu thô tăng đột biến thì chỉ số chứng khoán giảm”. Vấn đề đặt ra là liệu máy tính có thể tự phát hiện ra được các kết luận như thế sau khi phân tích một khối lượng lớn dữ liệu hay không?. Câu trả lời là hoàn toàn có thể. Trong một vài thập niên gần đây, Khai phá dữ liệu (KPDL) đã trở thành một trong những hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri thức. Trong quá trình phát triển đó với hàng loạt nghiên cứu, đề xuất được thử nghiệm và ứng dụng thành công vào đời sống, đã chứng tỏ rằng KPDL là một lĩnh vực nghiên cứu ổn định, có nền tảng lý thuyết vững chắc. KPDL bao hàm rất nhiều hướng tiếp cận. Các kỹ thuật chính được áp dụng trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực cơ sở dữ liệu (CSDL), máy học (Machine Learning), trí tuệ nhân tạo (AI – Artificial Intelligence), lý thuyết thông tin, xác xuất thống kê và tính toán hiệu năng cao (High performance computing). Các bài toàn chủ yếu trong KPDL là khai phá luật kết hợp (Association rules mining), phân lớp/dự đoán (Classification/Prediction), phân cụm (Clustering), khai phá chuỗi (Sequence mining), …. Lĩnh vực này là điểm hội tụ và giao thoa của nhiều lĩnh vực khác nhau. KPDL đã và đang được ứng dụng thành công trong thương mại, tài chính & thị trường chứng khoán, sinh học, y học, giáo dục, viễn thông, …. Khai phá luật kết hợp là một nội dung quan trọng trong KPDL được đề xuất lần đầu tiên năm 1993 thậm chí có chuyên gia đã khẳng định Phát hiện luật kết hợp là mục tiêu cơ bản của lĩnh vực khai phá dữ liệu [002]. Vì đây là một lĩnh vực nghiên cứu có nhiều triển vọng, nên tôi đã chọn Một số phương pháp khai phá dữ liệu sinh luật kết hợp làm đề tài cho luận văn của mình. Luận văn được xây dựng dựa trên nền của một số nghiên cứu chính yếu trong lĩnh vực khai phá luật kết hợp trong những năm gần đây. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 8 Luận văn được tổ chức thành 4 chương: Chương 1: Tổng quan về Khai phá dữ liệu Trình bày những nét khái quát nhất về KPDL, các hướng tiếp cận, phương pháp và các ứng dụng. Chương 2: Một số vấn đề cơ bản về Luật kết hợp Trình bày các vấn đề chung, cơ bản nhất về Luật kết hợp, các hướng tiếp cận và các vấn đề liên quan. Chương 3: Một số phương pháp khai phá dữ liệu sinh luật kết hợp Trình bày các phương pháp, giải thuật cơ bản khai phá luật kết hợp từ dữ liệu như Apriori, FP-Growth, Charm và Closet. Chương 4: Xây dựng ứng dụng minh hoạ Triển khai các giải thuật khai phá luật kết hợp trình bày trong Chương 3 và áp dụng vào CSDL đơn hàng thực tế và so sánh chúng với nhau. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 9 1. Chương 1: Tổng quan về khai phá dữ liệu (KPDL) 1.1. Khái niệm KPDL (Data Mining) là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng trong CDSL nhất định. Trong đó tri thức được ngầm hiểu là các thông tin mang tính chất quy luật và hữu ích đối với người sử dụng. KPDL là bước quan trọng nhất trong quá trình Khai phá tri thức (KDD – Knowledge Discovery in Database) - gồm 5 bước như sau [006]: + Thu thập dữ liệu (Data colection): là bước thu thập, trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (Databases, Data marts, Data warehouses, Data repositories) ban đầu theo một số tiêu chí nhất định. + Tiền xử lý dữ liệu (Data preprocessing): là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, …), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, …), rời rạc hoá dữ liệu (rời rạc hoá dựa vào histograms, entropy, phân khoảng, …). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa. + Biến đổi dữ liệu (Data Transformation): đây là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau. + KPDL (Data mining): đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của máy học) nhằm để khai phá dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng nhất và tốn nhiều thời gian nhất của toàn quá trình KDD. + Đánh giá và biểu diễn tri thức (Knowledge presentation and evaluation): chuyển hoặc biểu diễn những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên về một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, …. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Dữ liệu thô Tri thức Trích chọn DL Tiền xử lý DL Biến đổi DL Đánh giá và Biểu diễn TT Khai phá DL Hình 1.1: Các bước trong quá trình KDD. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 10 1.2. Các hướng tiếp cận chính trong KPDL Các hướng tiếp cận trong KPDL có thể được phân chia theo chức năng hay lớp các bài toán khác nhau, dưới đây là một số hướng tiếp cận chính: + Phân lớp và Dự đoán (Classification and Prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp các bệnh nhân theo dữ liệu trong hồ sơ bệnh án. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định (Decision tree), mạng nơron nhân tạo (Neural network), …. Phân lớp và dự đoán còn được gọi là học có giám sát (Supervised learning). + Khai phá luật kết hợp (Association rules mining): khai phá các tri thức dạng luật kết hợp. Ví dụ: “60% nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm đậu phộng”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trường chứng khoán, … + Phân tích chuỗi theo thời gian (Sequential/Temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Phương pháp này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. + Phân cụm (Clustering/Segmentation): xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không giám sát (Unsupervised learning). + Mô tả khái niệm (Concept description and summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. 1.3. Một số phương pháp KPDL phổ biến 1.3.1. Phương pháp suy diễn và quy nạp + Phương pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong CSDL dựa trên các quan hệ trong dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết suất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. + Phương pháp quy nạp: Các thông tin được suy ra từ CSDL bằng cách nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết trước. 1.3.2. Cây quyết định và luật + Cây quyết định: Cây quyết định là một phương pháp mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút trong của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá miêu tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của các thuộc tính của đối tượng tới lá. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 11 + Tạo luật: Các luật được tạo ra nhằm suy diễn cho một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng nếu P thì Q, trong đó P là mệnh đề đúng với một phần dữ liệu trong CSDL và Q là mệnh đề dự đoán. Ví dụ: Ta có mẫu phát hiện được bằng phương pháp tạo luật “Nếu mỗi năm cứ tăng vốn lưu động thêm 20% và vốn cố định tăng 10% thì lợi nhuận trước thuế tăng 25%”. Cây quyết định là phương pháp dùng trong các bài toán phân loại dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Cây quyết định và luật có ưu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là miêu tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về độ chính xác của mô hình. 1.3.3. Phát hiện các luật kết hợp Các luật kết hợp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu của hình thành tri thức. Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Một đầu ra của giải thuật khai phá dữ liệu là tập các luật kết hợp tìm được. Cho một lược đồ R = {A1, A2, …, Ap} với các thuộc tính có miền giá trị {0, 1} và một quan hệ r trên R. Cho W  R, đặt s(W, r) là tần số xuất hiện của W trong r được tính bằng tỉ lệ của các hàng trong r có giá trị 1 tại mỗi cột. Ta định nghĩa một luật kết hợp trên quan hệ r: X => B với X  R và B  R\X với độ hỗ trợ (tần số xuất hiện) và độ tin cậy: - Độ hỗ trợ  = s(X{B}, r). - Độ tin cậy  = s(X{B}, r) / s(X, r). Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X => B sao cho tần số xuất hiện của luật không nhỏ hơn ngưỡng min cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng min cho trước. Những ngưỡng này thường do người dùng hoặc các chuyên gia trong lĩnh vực xác định. Giải thuật tìm các luật kết hợp được bắt đầu bằng việc tìm tất cả các tập mục thường xuyên xuất hiện (FIS - Frequent ItemSet), đây là các tập mục mà tần số xuất hiện lớn hơn min. Sau đó các luật kết hợp sẽ được khai phá từ các tập mục phổ biến này dựa trên min. Chúng ta sẽ đi sâu nghiên cứu về Luật kết hợp trong Chương 2 và Chương 3. 1.3.4. Phân nhóm và phân đoạn Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá các thuộc tính của các thành phần như là hàm của các tham số của các thành phần. Kỹ thuật này được gọi là kỹ thuật phân hoạch tối ưu. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 12 Một trong những ứng dụng của kỹ thuật phân nhóm theo độ giống nhau là cơ sở dữ liệu khách hàng để phân nhóm khách hàng theo các tham số và các nhóm thuế tối ưu có được khi thiết lập biểu thuế bảo hiểm. Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu chứa dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu. Khi các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan trọng. 1.3.5. Mạng Neural Mạng neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng neural có thể đưa ra các kết luận từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Một trong những ưu điểm phải kể đến của mạng neural là khả năng tạo ra các mô hình dự đoán do có độ chính xác cao, có thể áp dụng được cho nhiều các bài toán khác nhau đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo,…. Mẫu chiết xuất bằng mạng neural được thể hiện ở các nút đầu của mạng. Mạng neural có thể sử dụng các hàm số bất kỳ chứ không chỉ đơn giản là sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng neural là không cần gia công dữ liệu nhiều trước khi bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên để có thể sử dụng mạng neural có hiệu quả cần xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng (kiến trúc) là gì ? - Mạng cần bao nhiêu tầng và bao nhiêu nút ? - Khi nào thì việc học dừng ? Mạng neural được đóng góp với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ đảm bảo các mô hình này làm việc tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. 1.3.6. Giải thuật di truyền Đây là phương pháp không chỉ phục vụ phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Ví dụ bài toán tối ưu hoá hoặc lập lịch. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập hợp dữ liệu ban đầu bằng ký tự nhị phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến chúng ta biến đổi quần thể gene ban đầu và loại bỏ đi một số gene làm cho số lượng gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích Một số phương pháp khai phá dữ liệu sinh luật kết hợp 13 nghi của quần thể theo các giai đoạn. Quá trình tiến hoá làm cho các quần thể thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho ta lời giải tối ưu toàn cục (Khác với phương pháp mạng neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng thì giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn là các giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ. Giải thuật di truyền là một thuật giải tối ưu hoá, nó được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng neural. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối ưu hoá là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. 1.4. Lựa chọn các kỹ thuật khai phá Các giải thuật khai phá dữ liệu tự động mới chỉ ở giai đoạn phát triển ban đầu. Hiện nay người ta vẫn chưa đưa ra được một tiêu chuẩn nào trong việc quyết định sử dụng phương pháp nào vào trong trường hợp nào thì hiệu quả. Hầu hết các kỹ thuật về khai phá dữ liệu đều là mới trong các lĩnh vực. Hơn nữa lại có rất nhiều kỹ thuật được sử dụng cho nhiều bài toán khác nhau. Vì vậy câu hỏi dùng kỹ thuật nào để khai phá không phải là đơn giản. Mỗi phương pháp đều có những điểm mạnh và điểm yếu riêng của nó, nhưng đa số các điểm yếu đều có thể khắc phục được. Vậy phải làm như thế nào để áp dụng kỹ thuật một cách đơn giản nhất, dễ sử dụng, để không cảm thấy sự phức tạp vốn có của kỹ thuật đó và vấn đề là tất cả các mẫu tìm được đều đáng quan tâm ? Đây chính là vấn đề quan tâm đối với một hệ thống khai phá dữ liệu. Hệ thống khai phá có thể sinh ra hàng nghìn mà thậm chí có thể hàng triệu mẫu hoặc luật, do vậy với câu hỏi trên thì câu trả lời là: Chỉ có một phần nhỏ trong các mẫu hay các luật là đáng quan tâm và hữu ích với người sử dụng. Có một vài câu hỏi thường đặt ra đối với một hệ thống khai phá dữ liệu là: + (1) Cái gì tạo ra các mẫu quan tâm ? + (2) Hệ thống khai phá có thể sinh ra được tất cả các mẫu quan tâm không ? + (3) Hệ thống khai phá có thể chỉ sinh các mẫu quan tâm không ? Đối với câu hỏi 1: Mẫu là đáng quan tâm nếu nó dễ hiểu đối với con người, hợp lệ hoặc dữ liệu được kiểm tra với độ chắc chắn nào đó, có khả năng (tiềm năng) hữu ích, và cuối cùng là càng mới lạ càng tốt. Có vài độ đo cho các mẫu quan tâm dựa trên cấu trúc của mẫu đã khai phá và thống kê chúng. Chẳng hạn độ đo của luật kết hợp dạng X => Y là độ hỗ trợ và độ tin cậy của luật và cụ thể ta định nghĩa độ hỗ trợ là xác suất P(XY) và độ tin cậy là xác suất có điều kiện P(X|Y). Một số phương pháp khai phá dữ liệu sinh luật kết hợp 14 Đối với câu hỏi thứ 2: Có thể tạo ra được tất cả các mẫu đáng quan tâm không ? Vấn đề này liên quan đến tính hoàn thiện của thuật toán khai phá. Nó thường không thực hiện được và không có khả năng đối với cả hệ thống khai phá dữ liệu để sinh ra tất cả các mẫu có thể có, có thể tồn tại. Thay cho điều đó người ta tập trung vào mục tiêu tìm kiếm. Khai phá luật kết hợp là một ví dụ, ở đó người ta sử dụng các độ đo có thể đảm bảo khai phá trọn vẹn, có nghĩa là với ngưỡng độ hỗ trợ và độ tin cậy nhỏ nhất xác định trước thì có thể tìm được. Đối với câu hỏi thứ 3: Hệ thống khai phá có thể chỉ sinh ra các mẫu cần quan tâm không ? Đây chính là vấn đề tối ưu trong khai phá dữ liệu. Vấn đề này còn là thách thức rất lớn đối với các nhà khoa học trong lĩnh vực khai phá dữ liệu. 1.5. Các dạng CSDL thường được sử dụng để KPDL Do KPDL được ứng dụng rộng rãi nên có rất nhiều dạng dữ liệu khác nhau được chấp nhận trong KPDL [105]. Sau đây là một số dữ liệu điển hình: + CSDL quan hệ (Relational databases): là CSDL tác nghiệp được tổ chức theo mô hình quan hệ. Hầu hết các hệ quản trị CSDL hiện nay đều hỗ trợ dạng CSDL này như SQL Server, Oracle, DB2, MySQL, MS Access, …. + CSDL giao dịch (Transaction databases): đây cũng là một dạng CSDL tác nghiệp, nhưng các bản ghi thường là các giao dịch. Dạng dữ liệu này phổ biến trong lĩnh vực thương mại và tài chính ngân hàng. + CSDL đa chiều (Multidimentional structures, Data warehouses, Data mart): là các kho dữ liệu được tập hợp, chọn lọc từ nhiều nguồn khác nhau. Dạng dữ liệu này có mang tính lịch sử (mang tính thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng như khai phá tri thức nhằm hỗ trợ quá trình ra quyết định. + CSDL hướng đối tượng (Object-oriented databases): dạng CSDL là tập các đối tượng, các đối tượng này có quan hệ và có thể tương tác với nhau. + Dữ liệu không gian và thời gian (Spatial, Temporal, and Time-series data): là dạng dữ liệu có tích hợp thuộc tính về không gian (ví dụ: dữ liệu bản đồ) hoặc thời gian (ví dụ: dữ liệu về thị trường chứng khoán). + CSDL đa phương tiện (Multimedia databases): dữ liệu được tích hợp gồm nhiều dạng khác nhau: âm thanh, hình ảnh, văn bản,… 1.6. Một số ứng dụng của KPDL KPDL là một lĩnh vực mới, nó thu hút được nhiều nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số hướng nghiên cứu và ứng dụng điển hình của nó hiện nay: + Phân tích dữ liệu và hỗ trợ quyết định (data analysis & decision support). Một số phương pháp khai phá dữ liệu sinh luật kết hợp 15 + Điều trị trong y học (medical treatment): mối liên hệ giữa triệu chứng, chuẩn đoán và phương pháp điều trị. + Text ming & Web mining: phân lớp, tóm tắt văn bản và phân lớp các trang WEB. + Tin – sinh (Bio-informatics): tìm kiếm, đối sánh các hệ gene và thông tin di truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền,… + Tài chính và thị trường chứng khoán (finance & stock market): phân tích tình hình tài chính và dự báo giá của các cổ phiếu trong thị trường chứng khoán. + Bảo hiểm (insurance), Giáo dục (education), …. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 16 2. Chương 2: Một số vấn đề cơ bản về Luật kết hợp Khai phá dữ liệu sinh luật kết hợp là một hướng tiếp cận quan trọng trong KPDL nói chung (thậm chí có những chuyên gia đánh giá là hướng tiếp cận quan trọng nhất), nó được ra đời và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên nó được các tác giả R. Agrawal, T. Imielinski và A. Swami đề xuất năm 1993, sau đó ngày càng được nhóm tác giả và các nhà khoa học khác nghiên cứu phát triển và hoàn thiện. 2.1. Định nghĩa luật kết hợp 2.1.1. Ví dụ về luật kết hợp Ví dụ 1: “Tại siêu thị 10% giao dịch là khách hàng mua bia và lạc. Cũng để ý thấy nếu một người mua bia thì chắc đến 70% rằng người đó sẽ mua thêm lạc.” Ví dụ 2: “Tại quầy lưu niệm 12% giao dịch là khách hàng nam giới mua quà lưu niệm và hoa để tặng bạn gái anh ta. Người bán hàng chắc đến 90% rằng nếu khách hàng là nam giới mua quà lưu niệm mua cả hoa thì người được tặng là bạn gái anh ta.” Ở đây vế trái (tiền đề - antecedent) của luật là “mua bia”, “nam giới, mua quà lưu niệm và hoa”, còn “mua lạc” và “tặng bạn gái” là vế phải (mệnh đề kết luận consequent) của luật. Các số 10%, 12% được gọi là độ hỗ trợ của luật (Support – số phần trăm các giao dịch chứa cả về phải và vế trái của luật). Các số 70%, 90% được gọi là độ tin cậy của luật (Confidence – số phần trăm giao dịch thoả mãn vế trái thì cũng thoả mãn vế phải). Chúng ta thấy rằng tri thức đem lại bởi những luật kết hợp ở dạng trên có sự khác biệt cơ bản so với thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường. Đó thường là những tri thức, những mối liên hệ chưa được biết trước và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không chỉ đơn giản là kết quả của các phép nhóm, tính tổng hay sắp xếp mà là kết quả của quá trình tính toán phức tạp và tốn nhiều thời gian. Tuy luật kết hợp là dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại rất đáng kể và hỗ trợ không nhỏ trong quá trình ra quyết định. Tìm kiếm được những luật kết hợp quý hiếm và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực KPDL và đây chính là động lực không nhỏ thúc đẩy việc tập trung nghiên cứu của nhiều nhà tin học. 2.1.2. Các định nghĩa và tính chất 2.1.2.1. Các định nghĩa cơ bản Cho tập các mục I = {i1, i2, …, in} và tập các giao dịch T = {t1, t2, …, tm}. Trong đó Một số phương pháp khai phá dữ liệu sinh luật kết hợp 17 + ij (j = 1..n) là một mục (item) hay một thuộc tính (property). + tk (k = 1..m) là một giao dịch (transaction) hay một bản ghi (record) được định danh bởi TID (Transaction Identifier). Cho δ là một quan hệ nhị phân trên I và T (δ: IxT => {0, 1}) sao cho nếu mục i xuất hiện trong giao dịch t thì ta viết δ(i, t). Về ý nghĩa, một CSDL là một tập các giao dịch, mỗi giao dịch t là một tập mục: t  2I (với 2I là tập các tập con của I). Ví dụ: CSDL (dạng giao dịch) I = {A, B, C, D, T, W}, T = {1, 2, 3, 4, 5, 6} với thông tin về giao dịch cho ở bảng sau: TID Danh sách các mục 1 A 2 C C T D W 3 A C 4 A C D 5 A C D T C D T 6 W T W W W Bảng 2.1: Ví dụ một CSDL giao dịch. + Độ hỗ trợ (Support): Cho tập mục (Itemset) X: X  I. Ta định nghĩa Độ hỗ trợ của tập mục X trong CSDL D như sau: sup(X )  | {t  D : X  t} | *100% |D| Tuy nhiên khi xét trên 1 CSDL D cụ thể ta có thể bỏ qua |D| vì nó cố định và lúc này có thể coi sup(X) = |{tD: Xt}|. + Tập mục phổ biến (FIS: Frequent ItemSet): Tập mục X được gọi là tập mục phổ biến với độ hỗ trợ minsup (minsup là giá trị cho trước được xác định bởi người sử dụng) nếu độ hỗ trợ của nó lớn hơn hoặc bằng minsup: s(X) minsup. Bảng sau đây liệt kê các FIS trong CSDL cho ở trên với giá trị minsup = 50% Các tập mục phổ biến C Tần suất Độ hỗ trợ 6 100% W, CW 5 83% A, D, T, AC, AW, CD, CT, ACW 4 67% AT, DW, TW, ACT, ATW, CDW, CTW, ACTW 3 50% Bảng 2.2: Ví dụ về các tập mục phổ biến. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 18 + Luật kết hợp (Association Rule): Luật kết hợp có dạng: r: X => Y (s, c), với X, Y là các tập mục thoả mãn điều kiện XY = Ø, X là tiền đề, Y là kết quả của luật, s là độ hỗ trợ (Support), c là độ tin cậy (Confidence) của luật trong đó: + s(r) = s(X => Y) = s(X  Y). + c(r) = c(X => Y) = s(X  Y) / s(X). + Luật kết hợp mạnh (Strong association rule): Luật kết hợp r được gọi là luật kết hợp mạnh khi và chỉ khi nó thoả cả 2 điều kiện (minsup và minconf được cho trước): + s(r) = s(X  Y)  minsup. + c(r) = s(X  Y) / s(X)  minconf. + Bài toán khai phá dữ luật kết hợp (ở dạng đơn giải nhất): Cho một CSDL D, độ hỗ trợ tối thiểu minsup, độ tin cậy tối thiểu minconf. Hãy tìm kiếm tất cả các luật kết hợp r dạng X => Y (s, c) thoả mãn cả 2 điều kiện: + s(r) = s(X  Y)  minsup. + c(r) = s(X  Y) / s(X)  minconf. Hầu hết các thuật toán được đề xuất để khai phá luật kết hợp thường chia bài toán thành 2 pha: + Pha 1: Tìm tất cả các tập mục phổ biến từ CSDL tức là tìm tất cả các tập mục X thoả mãn s(X)  minsup. Đây là pha tốn khá nhiều thời gian của CPU và thời gian vào ra ổ đĩa. + Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha 1. Pha này tương đối đơn giản và tốn ít thời gian hơn so với pha trên. Nếu X là một tập mục phổ biến thì luật kết hợp được sinh từ X có dạng r: X\Y => Y, với Y  X, Y  Ø và c(r)  minconf. Ví dụ: Xét tập mục ACW trong Bảng 2.2 có độ hỗ trợ s = 67% và với minconf = 70% thì ta có thể sinh các luật kết hợp sau đây: Luật kết hợp % A 100    CW Thoả mãn minconf  70% Có % C 67 AW   % W 80 AC   % AC 100   W % AW 100   C Không Có Có Có Một số phương pháp khai phá dữ liệu sinh luật kết hợp 19 Bảng 2.3: Các luật kết hợp được sinh từ tập mục phổ biến ACW. 2.1.2.2. Một số tính chất của tập mục phổ biến + Tính chất 1: Độ hỗ trợ của tập con. Cho X, Y là các tập mục và X  Y thì sup(X)  sup(Y). + Tính chất 2: Một tập chứa tập không phổ biến thì nó cũng không phổ biến. Cụ thể: Nếu X  Y và sup(X) < minsup thì sup(Y) < minsup. + Tính chất 3: Mọi tập con của một tập phổ biến cũng là tập phổ biến. Cụ thể: Nếu X  Y và sup(Y) > minsup thì sup(X) > minsup. 2.1.2.3. Một số tính chất của luật kết hợp + Tính chất 1: Không hợp các luật kết hợp. Giả sử có hai luật kết hợp mạnh X => Z và Y => Z thì X  Y => Z chưa chắc đã là luật kết hợp mạnh. Tương tự nếu có X => Y và X => Z thì X => Y  Z chưa chắc mạnh. Thật vậy xét: I = {x, y, z}, T = {xz, yz, xy, xyz}, minsup = 50%, minconf = 60%. Dễ thấy x => z (50%, 67%), y => z (50%, 67%), x => y (50%, 67%) là mạnh. Còn xy => z (25%, 50%) và x => yz (25%, 33%) không mạnh. + Tính chất 2: Không tách luật kết hợp. Giả sử có luật kết hợp mạnh X  Y => Z thì X => Z và Y => Z chưa chắc đã là luật kết hợp mạnh. Thật vậy xét: I = {x, y, z, t}, T = {xt, yt, xyz}, minsup = 30%, minconf = 60%. Dễ thấy xy => z (33%, 100%) là mạnh. Còn x => z (33%, 50%) và y => z (33%, 50%) không mạnh. Tuy nhiên nếu có luật kết hợp mạnh X => Y  Z thì X => Y và X => Z chắc chắn là luật kết hợp mạnh. Thật vậy ta chỉ cần chứng minh X => Y là luật kết hợp mạnh <=> sup(X  Y)  minsup và sup(X  Y) / sup(X)  minconf. (*) Xuất phát từ giả thiết: X => Y  Z là luật kết hợp mạnh nên sup(X  Y  Z)  minsup và sup(X  Y  Z) / sup(X)  minconf mà hiển nhiên sup(X  Y)  sup(X  Y  Z) nên (*) đã được chứng minh. Tương tự X => Z cũng là luật kết hợp mạnh. + Tính chất 3: Các luật kết hợp không có tính chất bắc cầu. Giả sử có các luật kết hợp mạnh X => Y và Y => Z thì X => Z chưa chắc đã là luật kết hợp mạnh. Một số phương pháp khai phá dữ liệu sinh luật kết hợp 20 Thật vậy xét: I = {x, y, z}, T = {xy, yz}, minsup = 30%, minconf = 60%. Dễ thấy x => y (50%, 100%) và y => z (50%, 100%) đều mạnh. Còn x => z (0%, 0%) không mạnh. + Tính chất 4: Nếu luật A => (L \ A) không thoả mãn độ tin cậy cực tiểu (minconf) thì luật B => (L \ B) cũng không thoả mãn, trong đó B  A  L, B  Ø. Thật vậy conf(B => (L \ B)) = sup(L) / sup(B)  sup(L) / sup(A) < minconf. Tương tự: Nếu luật (L \ C) => C là luật kết hợp mạnh thì luật (L \ D) => D cũng mạnh, trong đó D  C  L, D  Ø. Thật vậy conf((L \ D) => D) = sup(L) / sup(L \ D)  sup(L) / sup(L \ C)  minconf. Và hiển nhiên theo giả thiết sup(L)  minsup nên (L \ D) => D là mạnh. Các tính chất này của luật kết hợp sẽ được sử dụng trong các thuật toán về sau. 2.2. Các loại luật kết hợp và hướng tiếp cận 2.2.1. Luật kết hợp nhị phân // Binary association rule or Boolean association rule. Đối với các luật kết hợp này, các mục chỉ được quan tâm là có xuất hiện hay không xuất hiện trong giao dịch chứ không quan tâm đến mức độ xuất hiện. Ví dụ: “Mua bia => Mua lạc”, “Mua quà, Mua hoa => Tặng bạn gái”, .... Đây là dạng luật kết hợp đơn giản nhất và điều đặc biệt là chúng ta có thể chuyển các dạng luật khác về dạng luật này nhờ phương pháp rời rạc hoá. Các thuật toán tiêu biểu thực hiện khai phá luật kết hợp nhị phân là Apriori và FP-Growth. Chúng ta sẽ đi sâu nghiên cứu trong phần tiếp sau. 2.2.2. Luật kết hợp định lượng // Quantitative assosiation rule. 2.2.2.1. Giới thiệu Đối với loại này, ta không chỉ quan tâm tới sự có mặt hay không của các mục trong giao dịch mà còn quan tâm tới định lượng của từng mục trong luật. Ví dụ: “Mua bia 2-5 chai => Mua lạc 5-10 gói”, “Tuổi 20-30, Mua quà $5-$10, Mua hoa $3-$8 => Tặng bạn gái thân”, .... 2.2.2.2. Khai phá luật kết hợp định lượng Để phát hiện ra luật kết hợp định lượng ta phải thực hiện các bước sau: + Tiền xử lý: Thực hiện rời rạc hoá chuyển đổi các thuộc tính số và thuộc tính phân loại thành các thuộc tính nhị phân để có thể sử dụng được các thuật toán khai phá luật kết hợp nhị phân. Điểm quan trọng của bước này là phải xác định các khoảng thuộc tính số Một số phương pháp khai phá dữ liệu sinh luật kết hợp
- Xem thêm -

Tài liệu liên quan