Đăng ký Đăng nhập
Trang chủ Khai phá luật kết hợp trên mô hình dữ liệu dạng khối...

Tài liệu Khai phá luật kết hợp trên mô hình dữ liệu dạng khối

.PDF
53
243
60

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ĐỖ THỊ LAN ANH KHAI PHÁ LUẬT KẾT HỢP TRÊN MÔ HÌNH DỮ LIỆU DẠNG KHỐI Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ MÁY TÍNH Người hướng dẫn khoa học: PGS.TS Trịnh Đình Thắng Hà Nội, 2013 1 LỜI CẢM ƠN Bằng sự kính trọng và lòng biết ơn sâu sắc, em xin chân thành cảm ơn PGS.TS Trịnh Đình Thắng, người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình làm luận vă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, phòng Sau đại học trường Đại học Sư phạm Hà Nội 2, các thầy cô đã trực tiếp giảng dạy các học phần trong khóa học đã tạo điều kiện thuận lợi cho em trong cả quá trình học tập và nghiên cứu tại trường. Xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp đã quan tâm, giúp đỡ em trong thời gian nghiên cứu và hoàn thành luận văn. Trong quá trình nghiên cứu, luận văn không tránh khỏi những thiếu sót. Rất mong nhận được sự góp ý của quý thầy cô và bạn bè đồng nghiệp quan tâm đến luận văn này. Hà Nội, tháng 10 năm 2013 Học viên Đỗ Thị Lan Anh 2 LỜI CAM ĐOAN Trong quá trình hoàn thành luận văn, tôi đã tìm hiểu, nghiên cứu, tổng hợp nhiều nguồn tài liệu khác nhau, dưới sự chỉ đạo, giúp đỡ của giáo viên hướng dẫn, kết quả của đề tài là sản phẩm lao động của cá nhân tôi. Các nguồn tài liệu sử dụng được trích dẫn rõ ràng, khoa học. Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên cứu nào. Tôi xin cam đoan những điều trên là hoàn toàn đúng. Hà Nội, tháng 10 năm 2013 Học viên Đỗ Thị Lan Anh 3 MỤC LỤC Trang Trang phụ bìa Lời cảm ơn ........................................................................................................ 1 Lời cam đoan ..................................................................................................... 2 Mục lục ............................................................................................................... 3 Danh mục các ký hiệu và chữ viết tắt ............................................................... 6 Danh mục các bảng ............................................................................................ 7 Danh mục các hình vẽ ....................................................................................... 8 MỞ ĐẦU ........................................................................................................... 9 N DUNG ...................................................................................................... 12 Chương 1. T NG U N KH PH D L U KH PH LU T K T H P ............................................................................................ 12 1.1. Khai phá dữ liệu ............................................................................... 12 1.1.1. Một số định ngh a về khai phá dữ liệu ..................................... 12 1.1.2. Các mô hình khai phá dữ liệu .................................................. 13 1.1.3. Các bài toán thông dụng trong khai phá dữ liệu ...................... 14 1.1.4. ng dụng của khai phá dữ liệu ................................................ 14 1.1.5. Một số khó khăn trong khai phá dữ liệu .................................. 15 1.2. Khai phá luật kết hợp ....................................................................... 17 1.2.1. Một số khái niệm ...................................................................... 17 1.2.2. Khai phá luật kết hợp ................................................................ 20 1.3. Kết luận chương 1 ............................................................................ 30 4 Chương 2. M H NH C SỞ D L U D NG KH ................................ 31 2.1. Khối, lược đồ khối ............................................................................ 32 2.2. Lát cắt ............................................................................................... 32 2.3. Khóa của khối ................................................................................... 33 2. . Đại số quan hệ trên khối ................................................................... 34 2. .1. Phép hợp ................................................................................... 34 2. .2. Phép giao .................................................................................. 34 2. . . Phép trừ ..................................................................................... 34 2. . . Tích Đề các................................................................................ 34 2. .5. Tích Đề các theo tập chỉ số ....................................................... 35 2. . . Phép chiếu ................................................................................. 35 2. . . Phép chọn .................................................................................. 36 2. . . Phép kết nối ............................................................................... 36 2. . . Phép chia ................................................................................... 37 2.5. Kết luận chương 2 ............................................................................. 37 Chương . KH D NG KH PH LU T K T H P TR N M H NH D L U .................................................................................................. 38 3.1. Một số khái niệm ............................................................................ 38 3.1.1. Khối giao tác ............................................................................. 38 .1.2. Luật kết hợp............................................................................... 38 3.2. Thuật toán khai phá luật kết hợp trên mô hình dữ liệu dạng khối . 40 3.2.1. Giới thiệu thuật toán khai phá luật kết hợp ............................... 40 5 .2.2. Thuật toán khai phá luật kết hợp trên từng lát cắt Dx ............... 42 .2. . Luật kết hợp trên khối r ............................................................. 48 .2. . Một số kết quả về luật kết hợp trên khối ................................... 48 . . Kết luận chương ........................................................................... 49 K T LU N ...................................................................................................... 50 T L U TH M KHẢO ............................................................................... 51 6 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT STT Ký hiệu/ Chữ viết tắt Viết đầy đủ Ý nghĩa 1 CSDL Cơ s dữ liệu Cơ s dữ liệu 2 đvdl Đơn vị dữ liệu Đơn vị dữ liệu 3 BFS Breadth First Search Duyệt theo chiều rộng 4 DFS Depth First Search Duyệt theo chiều sâu 7 DANH MỤC CÁC BẢNG Trang Bảng 1.1. Biểu di n ngang của cơ s dữ liệu giao tác .................................... 18 Bảng 1.2. Biểu di n dọc của cơ s dữ liệu giao tác ......................................... 18 Bảng 1.3. Tập giao tác minh họa thuật toán priori ....................................... 26 Bảng .1. Minh họa ma trận giao tác trên khối ................................................ 38 8 DANH MỤC CÁC H NH V Trang Hình 1.1. Khai phá tri thức trong cơ s dữ liệu .............................................. 12 Hình 1.2. Phân loại thuật toán khai phá luật kết hợp ....................................... 22 Hình 3.1. Khối giao tác nhị phân .................................................................... 39 9 MỞ ĐẦU 1. Lí do chọn đề tài Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng dụng của công nghệ thông tin trong nhiều l nh vực của đời sống xã hội, thì lượng dữ liệu được các cơ quan thu thập và lưu trữ ngày một nhiều lên. Người ta lưu trữ những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm gì với những dữ liệu này, nhưng họ vẫn tiếp tục thu thập và lưu trữ vì hy vọng những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách nhanh chóng để đưa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy, các phương pháp quản trị và khai thác cơ s dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là kỹ thuật khai phá dữ liệu. Khai phá dữ liệu là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu lớn. Có một số nhóm nghiên cứu đã đưa ra một số mô hình khai phá dữ liệu, trong đó khai phá dữ liệu sử dụng luật kết hợp là một mô hình cơ bản giúp tìm ra mối tương quan giữa những mục dữ liệu thường xuyên trong cơ s dữ liệu được lưu trữ trong kho dữ liệu. Bên cạnh đó, để có thể xây dựng được một hệ thống cơ s dữ liệu tốt, người ta thường sử dụng các mô hình dữ liệu thích hợp. Từ trước tới nay đã có một số loại mô hình được sử dụng trong các hệ thống cơ s dữ liệu như: mô hình thực thể - liên kết, mô hình mạng mô hình phân cấp, mô hình hướng đối tượng, mô hình dữ liệu datalog và mô hình quan hệ. Trong những năm gần đây, việc nghiên cứu nhằm m rộng mô hình dữ 10 liệu quan hệ đã được nhiều nhà khoa học quan tâm. Theo hướng nghiên cứu này một mô hình dữ liệu đã được đề xuất, đó là mô hình dữ liệu dạng khối. Mô hình dữ liệu này có thể được xem là một m rộng của mô hình dữ liệu quan hệ. Đã có một số công trình nghiên cứu về mô hình dữ liệu dạng khối này. Tuy nhiên việc khai phá dữ liệu trong mô hình dạng khối vẫn còn khá mới mẻ. Chính vì những lý do trên mà tôi đã chọn đề tài: “ Khai phá luật kết hợp trên mô hình dữ liệu dạng khối” 2. Mục đích nghiên cứu Trên cơ s nghiên cứu khai phá luật kết hợp theo thuật toán priori đề xuất thuật toán khai phá luật kết hợp trong mô hình dữ liệu dạng khối assoc_block. 3. Nhiệm vụ nghiên cứu 1. Tìm hiểu về khai phá dữ liệu. 2. Tìm hiểu về mô hình dữ liệu dạng khối. 3. Nghiên cứu thuật toán khai phá luật kết hợp trong mô hình cơ s dữ liệu dạng khối. 4. Đối tượng và phạm vi nghiên cứu Các vấn đề về khai phá luật kết hợp, thuật toán về khai phá luật kết hợp trên mô hình dữ liệu dạng khối. 5. Phương pháp nghiên cứu Trong quá trình triển khai đề tài, tôi sử dụng chủ yếu các phương pháp: Thu thập tài liệu, phân tích,suy luận, tổng hợp, đánh giá. 6. Những đóng góp mới của đề tài Các khái niệm về cơ s dữ liệu giao tác, độ h trợ, độ tin cậy, luật kết hợp và thuật toán khai phá luật kết hợp assoc_block trên mô hình dữ liệu dạng khối. 11 7. Cấu trúc của luận văn Luận văn gồm phần m đầu, phần kết luận và chương nội dung: Chương 1: Tổng quan về khai phá dữ liệu và khai phá luật kết hợp. Chương 2: Mô hình cơ s dữ liệu dạng khối. Chương : Khai phá luật kết hợp trong mô hình dữ liệu dạng khối. Sau cùng là Phụ lục và Tài liệu tham khảo. 12 CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ LUẬT KẾT HỢP 1.1 Khai phá dữ liệu 1.1.1. t ố định nghĩa khai phá dữ liệu Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong cơ s dữ liệu. uá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất, … . uá trình khai phá tri thức được Han và Kamber mô tả trong hình 1.1: Dữ liệu thực Mẫu ước lượng Cơ s tri thức Công cụ khai phá DL Kho dữ liệu Cơ s dữ liệu Kho dữ liệu Nơi chứa DL khác Hình 1.1 Khai phá tri thức trong cơ sở dữ liệu Có rất nhiều định ngh a khác nhau về khai phá dữ liệu đã được đưa ra: [2], [4] Định nghĩa của Ferruzza: “khai phá dữ liệu là tập hợp các phương pháp được dùng trong tiến trình khai phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu”. 13 Định nghĩa của Parsaye: “khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong cơ s dữ liệu (CSDL) lớn”. Định nghĩa của Fayyad: “khai phá dữ liệu là một quá trình không tầm thường nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu được”. Quá trình khai phá dữ liệu trải qua ba bước [2]: Bước 1: Lọc dữ liệu hay gọi là tiền xử lý. Khi dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Bước 2: Khai phá dữ liệu là công việc chính, sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu. Bước 3: Hậu xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật khác nhau cho các kết quả có thể khác nhau. Các kết quả được ước lượng b i những tiêu chí đánh giá nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. 1.1.2. Các mô hình khai phá dữ liệu Có hai mô hình khai phá dữ liệu [2],[4]:  Mô hình khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các k thuật này gồm có: phân cụm (clustering), tóm tắt (summarization), trực quan hóa (visualization), phân tích sự phát triển và độ lệch (evolution and deviation analysis), phát hiện luật kết hợp (association rules), ... 14  Mô hình khai phá dữ liệu suy di n: có nhiệm vụ đưa ra các dự đoán dựa vào các suy di n trên dữ liệu hiện thời. Các k thuật này gồm có: phân lớp (classification), hồi quy (regression), ... 1.1.3. Các bài toán thông dụng trong khai phá dữ liệu Trong khai phá dữ liệu, các bài toán có thể phân thành bốn loại chính [2]:  Phân lớp (Classification): Là bài toán thông dụng nhất trong khai phá dữ liệu. ới một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng để phân các dữ liệu mới vào một trong những lớp (còn gọi là loại) đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu Phân lớp.  Dự đoán (Prediction): ới mô hình học tương tự như bài toán Phân lớp, lớp bài toán Dự đoán sẽ học ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán. Bài toán tiêu biểu trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh.  Luật kết hợp (Association Rule): Các giải thuật tìm luật kết hợp tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị.  Phân cụm (Clustering): Các kỹ thuật Phân cụm sẽ nhóm các đối tượng dữ liệu có tính chất giống nhau vào cùng một nhóm. Có nhiều cách tiếp cận với những mục tiêu khác nhau trong Phân cụm. Các tài liệu [2, 4] giới thiệu khá đầy đủ và chi tiết về các cách tiếp cận trong Phân cụm. Các kỹ thuật trong bài toán này thường được vận dụng trong vấn đề phân hoạch dữ liệu tiếp thị hay khảo sát sơ bộ các dữ liệu. 1.1.4. Ứng dụng của khai phá dữ liệu 15 Khai phá dữ liệu được ứng dụng trong nhiều l nh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tùy theo bản chất của từng l nh vực, việc vận dụng khai phá dữ liệu có những cách tiếp cận khác nhau. Ngân hàng: Giúp cho việc xây dựng mô hình dự báo rủi ro tín dụng. Tìm kiếm tri thức, quy luật của thị trường chứng khoán và đầu tư bất động sản. Thương mại điện tử: Tìm hiểu, định hướng thúc đẩy, giao tiếp với khách hàng. Phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù hợp với nhiều loại khách hàng. Marketing: Phân tích nhu cầu khách hàng dựa trên mẫu dữ liệu mua bán hàng từ đó xác định chiến lược kinh doanh, quảng cáo, kế hoạch sản xuất, … Khai phá dữ liệu cũng được vận dụng hiệu quả để giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu từ ảnh vi n thám, cảnh báo hỏng hóc trong các hệ thống sản xuất, … Các kỹ thuật khai phá dữ liệu đã được áp dụng thành công trong việc dự đoán tái sử dụng điện năng cho các công ty cung cấp điện, lưu lượng vi n thông cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trường cho các công ty tài chính, …. Ngoài ra, khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như phân tích các kết quả phòng chống và điều trị một số loại bệnh, phân tích tác hại của ma tuý, phát hiện tội phạm hay tăng cường an ninh xã hội, .... iệc vận dụng thành công đã mang lại những hiệu quả thiết thực cho các hoạt động di n ra hàng ngày trong đời sống. 1.1.5. t ố khó khăn trong khai phá dữ liệu 16 - Cơ sở dữ liệu lớn: Các tập dữ liệu cần xử lý trong khai phá dữ liệu thường có kích thước cực kỳ lớn về cả số lượng các bản ghi và số lượng các thuộc tính. Trong thực tế, kích thước của các tập dữ liệu trong khai phá dữ liệu thường mức tera-byte (hàng ngàn giga-byte). ới kích thước như thế, thời gian xử lý thường cực kỳ dài. Mặc dù kích thước bộ nhớ trong của máy tính đã gia tăng đáng kể trong thời gian gần đây, việc gia tăng này cũng không thể đáp ứng kịp với việc tăng kích thước dữ liệu. ì vậy, việc vận dụng các kỹ thuật xác suất, lấy mẫu, đệm, song song, …vào các giải thuật để tạo ra các phiên bản phù hợp với yêu cầu của khai phá dữ liệu tr nên ngày càng quan trọng. - Dữ liệu thiếu và nhiễu: Mức độ nhi u cao trong dữ liệu điều này dẫn đến việc dự đoán thiếu chính xác. - Vấn đề “quá phù hợp” (Overfitting): Khi thuật toán khai phá tìm kiếm với các tham số tốt nhất cho một mô hình đặc biệt và một giới hạn của tập dữ liệu. Mô hình đó có thể “quá phù hợp” trên tập dữ liệu đó nhưng lại thi hành không chính xác trên tập dữ liệu kiểm tra. - Sự thay đổi của dữ liệu và tri thức: Dữ liệu là không t nh, dữ liệu thay đổi nhanh chóng có thể dẫn đến những tri thức đã khai phá trước đây tr nên không còn phù hợp thậm chí là vô giá trị. - Đánh giá các mẫu dữ liệu tìm được: Nhiều mẫu phát hiện không thực sự hữu ích với người sử dụng và thách thức với các hệ khai phá dữ liệu. - Làm việc với các dữ liệu quan hệ phức tạp: Do các hệ cơ s dữ liệu quan hệ được sử dụng rộng rãi nên vấn đề làm tốt với các hệ cơ s dữ liệu này là vấn đề cần quan tâm đối với các hệ khai phá dữ liệu. - Khai phá thông tin trong các hệ cơ sở dữ liệu hỗn hợp và hệ thống thông tin toàn cầu: ới sự ra đời của mạng máy tính, dữ liệu có 17 thể được thu thập từ nhiều nguồn khác nhau với định dạng khác nhau với số lượng rất lớn. iệc phát hiện tri thức từ các dạng dữ liệu h n hợp này là một thách thức đối với khai phá dữ liệu. 1.2. Khai phá luật kết hợp t ố khái niệm 1.2.1. 1.2.1.1. Cơ sở dữ liệu giao tác Định nghĩa 1.1 [2], [4], [5], [6] Cho I = {x1, x2, …, xn} là tập hợp các mục dữ liệu. M i x i gọi là một mục dữ liệu hay là một thuộc tính. Một tập con {x i1, xi2, …, xik}  được gọi là một giao tác trên . Đặt ti = {xi1, xi2, …, xik}, ti gọi là định danh của giao tác {xi1, xi2, …, xik}. Một tập hợp gồm m định danh giao tác T = {t 1, t2, …, tm}, với m bất kỳ được gọi là một cơ s dữ liệu giao tác trên . M i tập con X  với ||X|| = k được goi là tập k-mục dữ liệu hay k- thuộc tính của (trong trường hợp không quan tâm đến số mục dữ liệu của X, ta gọi tắt X là tập mục dữ liệu), m i tập con S  T gọi là tập định danh giao tác. 1.2.1.2. Biểu diễn cơ sở dữ liệu giao tác Có 2 cách biểu di n tập cơ s dữ liệu giáo tác: Biểu di n ngang và biểu di n dọc [2], [4].  Biểu di n ngang: Một cơ s dữ liệu là một danh sách các giao tác. M i giao tác có một định danh giao tác (tid) và một danh sách những mục dữ liệu trong giao tác đó. Ví dụ 1.1 Mục dữ liệu Giao tác t1 A, B, E t2 B, D t3 B, C 18 t4 A, B, D t5 A, C t6 B, C t7 A, C t8 A, B, C, E t9 A, B, C t10 A, B, E, G Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác  Biểu di n dọc: Một cơ s dữ liệu là một danh sách những mục dữ liệu, với m i mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu này. Mục dữ liệu Định danh giao tác A t1, t4, t5, t7, t8, t9, t10 B t1, t2, t3, t4, t6, t8, t9, t10 C t3, t5, t6, t7, t8, t9 D t2, t4 E t1, t8, t10 G t10 Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác Ma trận giao tác: Cho một cơ s dữ liệu giao tác T={ t1, t2, …, tm} trên I={x1, x2, …, xn}. Ma trận giao tác của T là ma trận M= (mpq)mxn với  1 khi iq  T p   mpq     0 khi iq T p   1.2.1.3. Khái niệm về luật kết hợp 19 Cho I = {I1, I2, …, q} là tập các đơn vị dữ liệu (đvdl). Ta quy ước m i giao tác làm phát sinh một tập con các đvdl của . Cho D là tập gồm m giao tác, m i giao tác T cho kết quả là tập con các đvdl T  I. í dụ, ta có tập đvdl tại một siêu thị: = {Bánh mì, bơ, sữa , trứng, bánh ngọt, đường, …}. Khách hàng mua bánh mì, bơ, sữa. Ta nói rằng, khách hàng đã đã phát sinh giao tác tA = {Bánh mì, bơ, sữa}. Giả sử, khảo sát tập giao tác D gồm m giao tác. ới m i tập đơn vị dữ liệu X  , xét số lượng p các giao tác trong D làm xuất hiện các đơn vị dữ liệu có trong X. Ký hiệu: v(X) là tần suất xuất hiện của tập đvdl X trong tập giao tác D. Ta có v( X )  p m Ký hiệu: |Z| là lực lượng của tập Z. Định nghĩa 1.2: Ta gọi luật kết hợp giữa hai tập đvdl X và Y (với X, Y là hai tập bất kỳ) là luật có dạng XY, trong đó X  I, Y  I và X  Y =  Định nghĩa1.3: Độ h trợ của luật X  Y, ký hiệu Supp(XY) hay Supp(X  Y) = v(XY), trong đó, XY là biểu di n hợp của hai tập đvdl X và Y. Định nghĩa 1.4: Ký hiệu Conf (X  Y)  Supp(XY) Supp(X) à gọi là độ tin cậy của luật X  Y Định nghĩa 1.5 : Cho trước các giá trị ngưỡng về độ h trợ tối thiểu Min_Supp = s0 và ngưỡng độ tin cậy tối thiểu Min_Conf = c0 với 0  s0, c0  1. Ta gọi tập X ( ) là tập thường xuyên trong tập giao tác D, nếu Supp(X)  s0. Ngược lại X được gọi là tập không thường xuyên. Nếu có Supp(X  Y)  s0 và Conf(X  Y)  c0. Ta nói rằng, có luật kết hợp X  Y trong D thỏa các ngưỡng cho trước.
- Xem thêm -

Tài liệu liên quan