Tài liệu Một số ứng dụng của hạt dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đinh Quang Thắng MỘT SỐ ỨNG DỤNG CỦA HẠT DỮ LIỆU LUẬN VĂN THẠC SĨ Hà Nội – 2005 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đinh Quang Thắng MỘT SỐ ỨNG DỤNG CỦA HẠT DỮ LIỆU Ngành : Chuyên ngành: Mã số: Công nghệ thông tin 1.01.1 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG CHÍ THÀNH Hà Nội - 2005 MỤC LỤC MỞ ĐẦU ..................................................................................................................... 4 CHƢƠNG 1: TỔNG QUAN VỀ TÍNH TOÁN HẠT ................................................... 7 1.1 Khái niệm về tính toán hạt ..................................................................................... 7 1.2 Tại sao chúng ta nghiên cứu tính toán hạt .............................................................. 8 1.3 Những vấn đề cơ bản của tính toán hạt ................................................................... 8 1.4 Một số mô hình tính toán hạt.................................................................................. 9 1.4.1 Các tập mờ ...................................................................................................... 9 1.4.2 Các tập thô .................................................................................................... 10 1.4.3. Một mô hình dựa trên lý thuyết tập hợp của tính toán hạt ............................. 11 1.4.3.1 Đại số luỹ thừa....................................................................................... 11 1.4.3.2 Đại số khoảng ........................................................................................ 11 1.4.3.3 Đại số tập khoảng .................................................................................. 12 1.5 Kết luận ............................................................................................................... 12 CHƢƠNG 2: BÀI TOÁN QUYẾT ĐỊNH VÀ PHƢƠNG PHÁP GIẢI QUYẾT DỰA VÀO HẠT DỮ LIỆU ................................................................................................ 13 2.1 Các cách kết hạt từ một tập .................................................................................. 13 2.1.1 Kết hạt bằng các quan hệ tƣơng đƣơng ......................................................... 13 2.1.2 Kết hạt bằng các quan hệ đồng dạng ............................................................. 14 2.2 Giới thiệu về các tập thô ...................................................................................... 15 2.2.1 Giới thiệu...................................................................................................... 15 2.2.2 Các định nghĩa về các tập thô ........................................................................ 16 2.2.2.1 Định nghĩa hƣớng phần tử ..................................................................... 16 2.2.2.2 Định nghĩa hƣớng hạt ............................................................................ 17 2.2.2.3 Định nghĩa hƣớng hệ thống con ............................................................. 17 2.2.2.4 Các hàm thuộc thô ................................................................................. 17 2.2.2.5 Một số tính chất của các xấp xỉ .............................................................. 20 2.2.2.6 Sự phân lớp thô...................................................................................... 20 2.3. Mô hình lý thuyết quyết định sử dụng tập thô ..................................................... 21 2.3.1 Khái quát về thủ tục quyết định Bayes .......................................................... 21 2.3.2 Mô hình lý thuyết quyết định sử dụng tập thô ............................................... 22 2.4 Kết luận ............................................................................................................... 28 -1- CHƢƠNG 3: KHAI PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU SỬ DỤNG CÁC TẬP THÔ .................................................................................................................. 30 3.1 Tổng quan về khai phá tri thức ............................................................................. 30 3.1.1 Giới thiệu...................................................................................................... 30 3.1.2 Khai phá tri thức và khai phá dữ liệu............................................................. 32 3.1.2.1 Quá trình KDD ...................................................................................... 33 3.1.2.2 Khai phá dữ liệu .................................................................................... 34 3.2 Các tập thô và khai phá tri thức trong cơ sở dữ liệu .............................................. 36 3.2.1 Làm sạch dữ liệu và tiền xử lý ...................................................................... 36 3.2.1.1 Rút gọn dữ liệu ...................................................................................... 36 3.2.1.2 Quản lý giá trị không đúng .................................................................... 37 3.2.1.3 Lựa chọn và trích chọn đặc trƣng ........................................................... 37 3.2.2 Khai phá dữ liệu ........................................................................................... 40 3.3 Khai phá luật kết hợp ........................................................................................... 40 3.3.1 Các luật kết hợp ............................................................................................ 41 3.3.2 Thuật giải tuần tự Apriori ............................................................................. 42 3.3.3 Các thuật giải song song và phân tán ............................................................ 43 3.3.3.1 Các kỹ thuật khai phá dữ liệu phân tán................................................... 43 3.3.3.1.1 Kỹ thuật sinh các tập ứng cử ........................................................... 43 3.3.3.1.2 Phép tỉa cục bộ các tập ứng cử ........................................................ 45 3.3.3.1.3 Phép tỉa toàn cục các tập ứng cử ..................................................... 48 3.3.3.1.4 Bầu kiểu kiểm phiếu ....................................................................... 50 3.3.3.2 Thuật giải 1: Phân tán tính toán ............................................................. 51 3.3.3.3 Thuật giải 2: Phân tán dữ liệu ................................................................ 52 3.3.3.4 Thuật giải 3: Phân tán ứng cử viên ......................................................... 55 3.3.3.5 Sinh các luật song song .......................................................................... 57 3.3.3.6 Thuật giải nhanh khai phá phân tán các luật kết hợp FDM ..................... 58 3.3.3.7 Sinh luật Apriori phân tán ...................................................................... 61 3.4 Kết luận ............................................................................................................... 64 CHƢƠNG 4: CHƢƠNG TRÌNH THỬ NGHIỆM ..................................................... 66 4.1 Thuật giải Apriori ………………………………………………………………...66 4.2 Cấu trúc dữ liệu T-tree ......................................................................................... 66 4.3 Giới thiệu chƣơng trình ........................................................................................ 67 4.4 Kết quả thử nghiệm .............................................................................................. 73 -2- 4.4 Kết luận ............................................................................................................... 74 KẾT LUẬN ............................................................................................................... 75 CÁC KẾT QUẢ ĐÃ ĐƢỢC BÁO CÁO TẠI CÁC HỘI THẢO QUỐC GIA ............ 76 TÀI LIỆU THAM KHẢO.......................................................................................... 77 -3- MỞ ĐẦU Trong những năm gần đây, tính toán hạt đã đƣợc áp dụng trong rất nhiều lĩnh vực nhƣ trí tuệ nhân tạo, phân tích khoảng, lƣợng tử hoá, lý thuyết tập thô, phân tích cụm, học máy, cơ sở dữ liệu và một số lĩnh vực khác. Cho đến nay, tính toán hạt đã có sự phát triển nhanh chóng và ngày càng có nhiều ngƣời tập trung nghiên cứu các ứng dụng của nó. Tính toán hạt là một thuật ngữ chỉ các lý thuyết, các phƣơng pháp, các kỹ thuật và các công cụ sử dụng các hạt (là các nhóm, các lớp, hoặc các cụm của một tập) để giải quyết các bài toán. Đề tài các hạt thông tin mờ đƣợc Zadeh đề xuất đầu tiên vào năm 1979 và đƣợc ông tiếp tục phát triển trong các bài báo công bố năm 1997. Đặc biệt, Zadeh đã trình bày một mô hình tổng quát của tính toán hạt dựa trên lý thuyết tập mờ. Các hạt đƣợc xây dựng và định nghĩa dựa trên các phép toán suy rộng. Mối quan hệ giữa các hạt đƣợc biểu diễn bằng đồ thị mờ hoặc các luật nếu-thì mờ. Mặc dù các công thức là khác với những nghiên cứu trong trí tuệ nhân tạo, nhƣng những ý tƣởng cơ bản của chúng là giống nhau. Zadeh xác định ba khái niệm cơ bản của tính toán hạt theo cách nhận thức của con ngƣời, cụ thể là phƣơng pháp kết hạt, phƣơng pháp tổ chức các hạt và phƣơng pháp lập luận với các hạt. Sau đó lý thuyết về tính toán với các hạt thông tin mờ đã đƣợc nghiên cứu bằng cách kết các hạt thông tin và lập luận với chúng. Sự cần thiết của việc kết hạt thông tin và tính dễ nhận đƣợc thông tin từ các hạt thông tin trong giải quyết bài toán là một trong các lý do thực tế cho tính phổ biến của tính toán hạt. Trong rất nhiều tình huống, khi một bài toán là không đầy đủ, không chắc chắn hoặc thông tin không rõ ràng sẽ rất khó để phân biệt các phần tử một cách riêng biệt và chỉ có thể nghiên cứu trên tập các phần tử đó. Trong một số trƣờng hợp khác, mặc dù chúng ta có thể nhận đƣợc những thông tin chi tiết, nhƣng chúng ta vẫn sử dụng các hạt để giảm chi phí một cách đáng kể. Điều này mở ra một định hƣớng của logic mờ: “Khai thác độ không chắc chắn và tính đúng bộ phận để có đƣợc khả năng dễ kiểm soát, tính mạnh mẽ, chi phí thấp và phù hợp với thực tế hơn”. Những nguyên tắc này hƣớng tới nhiều mô hình vật lý để giải quyết các bài toán thế giới thực: thay cho việc tìm kiếm những lời giải tối ƣu, ta có thể tìm kiếm những lời giải xấp xỉ tốt. Nhƣ vậy chỉ khi cần thiết chúng ta mới khảo sát bài toán tại một mức kết hạt mịn hơn với nhiều thông tin chi tiết hơn. Tính toán hạt cũng đƣợc nghiên cứu rộng rãi trong lý thuyết các tập thô. Nhƣ một nền tảng cụ thể của tính toán hạt, mô hình tập thô cho phép chúng ta định nghĩa một cách chính xác và phân tích nhiều khái niệm của tính toán hạt. Các kết quả nghiên cứu mang lại một cách hiểu thấu đáo hơn về tính toán hạt. -4- Luận văn tập trung vào nghiên cứu tính toán hạt dựa trên lý thuyết các tập thô. Cụ thể, luận văn có nội dung nhƣ sau sau: Chƣơng 1: Tổng quan về tính toán hạt: Trong chƣơng này, trình bày những thuật ngữ chung, các yếu tố và những vấn đề cơ bản của tính toán hạt và một số ứng dụng của chúng. Luận văn trình bày cách xây dựng, cách hiểu và cách biểu diễn các hạt cũng nhƣ các yếu tố cơ bản và các phép toán để tính loán và lập luận với các hạt. Phần cuối của chƣơng giới thiệu khái quát ba mô hình đang tồn tại của tính toán hạt: mô hình dựa trên các tập thông thƣờng, mô hình dựa trên lý thuyết các tập thô và mô hình dựa trên lý thuyết các tập mờ. Chƣơng 2: Bài toán quyết định và phƣơng pháp giải quyết dựa vào hạt dữ liệu: Luận văn giới thiệu một cách tổng quát hai cách kết hạt của một tập, các định nghĩa về các tập thô. Với các xấp xỉ tập thô, một tập tổng thể đƣợc phân thành ba vùng là POS, NEG và vùng biên BND. Bài toán quyết định là làm thể nào để xác định đƣợc ba vùng trên một cách hiệu quả. Một phƣơng pháp thƣờng hay đƣợc sử dụng để giải quyết bài toán quyết định trên là sử dụng thủ tục quyết định của Bayes. Luận văn trình bày tóm tắt thủ tục quyết định Bayes này và xây dựng một mô hình lý thuyết quyết định sử dụng các hạt dữ liệu dựa trên lý thuyết các tập thô. Chƣơng 3: Khai phá tri thức trong cơ sở dữ liệu sử dụng tập thô: Với các hạt là các xấp xỉ thô, luận văn nghiên cứu bài toán khai phá các luật kết hợp trong cơ sở dữ liệu quan hệ. Thuật giải tuần tự Apriori đƣợc trình bày. Sau đó, luận văn trình bày tới những ý tƣởng song song hoá của thuật giải này. Tốc độ của thuật giải sẽ tăng đáng kể khi thực hiện các thuật giải song song với dữ liệu đƣợc tổ chức trong môi trƣờng dữ liệu phân tán. Chƣơng 4: Chƣơng trình thử nghiệm: Luận văn trình bày một cấu trúc dữ liệu mới, cấu trúc dữ liệu T-tree. Cấu trúc này là phù hợp để cài đặt thuật giải Apriori vì nó cho phép tìm kiếm các tập mục nhanh và tiết kiệm không gian lƣu trữ dữ liệu. Thuật giải Apriori đƣợc cài đặt sử dụng cấu trúc dữ liệu này bằng ngôn ngữ lập trình Java. Luận văn đƣợc thực hiện dƣới sự hƣớng dẫn của PGS.TS Hoàng Chí Thành, Bộ môn Tin học, Khoa Toán-Cơ-Tin học trƣờng Đại học Khoa học Tự nhiên, Đại học Quốc Gia Hà Nội. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hƣớng dẫn và có ý kiến chỉ dẫn quí báu trong quá trình em làm luận văn. Em xin chân thành cảm ơn Thầy giáo, TS Hà Quang Thuỵ đã cho em nhiều ý kiến quí báu để em hoàn thiện luận văn hơn. Em xin cảm ơn các Thầy Cô giáo trong Bộ môn Tin học, các đồng nghiệp trong Khoa Toán-Cơ-Tin học, Trƣờng Đại học Khoa học Tự nhiên, các Thầy Cô giáo Khoa Công Nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc Gia Hà Nội đã tạo điều kiện giúp đỡ em trong quá trình hoàn thành luận văn. Cuối cùng xin bày tỏ lòng -5- cảm ơn tới những ngƣời thân trong gia đình, bạn bè đã động viên và giúp đỡ tôi hoàn thành luận văn này. -6- CHƢƠNG 1: TỔNG QUAN VỀ TÍNH TOÁN HẠT 1.1 Khái niệm về tính toán hạt Những ý tƣởng cơ bản về phƣơng pháp tính toán hạt đã đƣợc áp dụng trong một số lĩnh vực nhƣ phân tích khoảng, lƣợng tử hoá, lý thuyết các tập thô, phân tích cụm, học máy, cơ sở dữ liệu và một số lĩnh vực khác. Chủ đề về phƣơng pháp kết hạt thông tin mờ đầu tiên đƣợc trình bày bởi Zadeh vào năm 1979 [6]. Các ứng dụng của tính toán hạt đã đƣợc phát triển một cách nhanh chóng và nó đóng một vai trò quan trọng trong sự phát triển của logic mờ, lý thuyết các tập thô và các ứng dụng của chúng [6]. Những khái niệm và các thành phần cơ bản của tính toán hạt trên thực tế đã phát triển trong rất nhiều lĩnh vực, nhƣng đến nay chƣa có một định nghĩa tổng quát về tính toán hạt [3] [5] [6]. Tuy vậy, thông qua các phƣơng pháp giải một số bài toán trong thực tế, chúng ta vẫn có thể khái quát đƣợc các thành phần cơ bản của tính toán hạt [3, 7]. Do đó, chúng ta có thể nghiên cứu tính toán hạt dựa trên việc tập trung giải các bài toán sử dụng các tính chất chung của các hạt, các quan sát kết hạt, các tính chất của hạt và các hệ thống phân cấp của lớp các hạt. Khi đó, ta có thể coi tính toán hạt nhƣ là một nghiên cứu về lý thuyết tổng quát để giải quyết bài toán dựa trên các mức khác nhau về tính chất hạt [3, 6]. Những khái niệm dƣới đây của Zadeh có thể giúp chúng ta hiểu rõ hơn phạm vi ứng dụng và lập luận với các hạt: “Phƣơng pháp kết hạt của một đối tƣợng A hình thành một tập các hạt của A, với mỗi hạt là một cụm của các điểm (các đối tƣợng) đƣợc ghép lại với nhau theo quan hệ “không phân biệt đƣợc”, “quan hệ tƣơng tự”, “quan hệ xấp xỉ” hoặc “quan hệ có cùng chức năng”” [3], (Zadel 1997). “Lý thuyết về phƣơng pháp kết hạt thông tin mờ đƣợc xây dựng theo cách thức con ngƣời kết hạt thông tin và lập luận với chúng” [3] (Zadeh, 1997). “Lý thuyết về phƣơng pháp kết hạt thông tin mờ xây dựng trên bộ máy đang tồn tại của phƣơng pháp kết hạt thông tin mờ trong logic mờ nhƣng mang nó tới một mức cao hơn của tính tổng quát, thống nhất các nghiên cứu của nó và đề xuất các hƣớng nghiên cứu mới” [3] (Zadeh, 1997). “Tính toán hạt là một khái niệm của lý thuyết về phƣơng pháp kết hạt thông tin mờ, lý thuyết tập thô và tính toán khoảng và là một phần trong toán học tính toán với các hạt” [3] (Zadeh, 1997). Có thể thấy rằng ý tƣởng chung nhất của tính toán hạt là sử dụng các nhóm, các lớp hoặc cụm các phần tử đƣợc gọi là các hạt [3, 7]. Mặc dù đã có những ứng dụng cụ thể sử dụng tính toán hạt, vẫn khó có thể đƣa ra một định nghĩa chính xác. Chúng ta có thể -7- coi tính toán hạt là một thuật ngữ chỉ các lý thuyết, các phƣơng pháp, các kỹ thuật và các công cụ sử dụng các hạt trong quá trình giải bài toán. Dựa trên cách hiểu trực giác trên, chúng ta sẽ xem xét một số vấn đề cơ bản và một số giải pháp có thể của nó. 1.2 Tại sao chúng ta nghiên cứu tính toán hạt Có rất nhiều lý do để nghiên cứu tính toán hạt. Zadeh đã xác định ba vấn đề cơ bản của tính toán hạt: phƣơng pháp kết hạt, tổ chức các hạt và lập luận với các hạt. “Phƣơng pháp kết hạt bao gồm việc phân chia một tập tổng thể thành các phần, tổ chức các hạt bao gồm việc tích hợp các phần trong một tập tổng thể và lập luận với các hạt thực hiện việc sử dụng các mối quan hệ giữa các hạt để đi từ các điều kiện ban đầu tới các kết quả mong muốn” [3]. Trong việc giải quyết bài toán, sử dụng các hạt thông tin thƣờng đơn giản hơn sử dụng các thông tin chi tiết có lẽ là những lý do chính để phát triển tính toán hạt. Khi một bài toán có độ không chắc chắn, tính không đầy đủ hoặc thông tin không rõ ràng, có thể rất khó để phân biệt sự khác nhau giữa các phần tử và hƣớng chúng ta tới nghiên cứu các hạt. Một ví dụ điển hình là lý thuyết các tập thô [3, 7]. Tình trạng thiếu thông tin chỉ cho phép chúng ta xác định đƣợc các hạt thay cho việc xác định các phần tử cụ thể. Trong một số tình huống, mặc dù các thông tin chi tiết có thể có đƣợc, nhƣng sử dụng các hạt sẽ mang lại tính hiệu quả và các lời giải thiết thực hơn. Những nhân tố cơ bản của tính toán hạt cũng định hƣớng tới sự phát triển của logic mờ: “ Khai thác tính chấp nhận đƣợc với các dữ liệu có tính không chính xác, không chắc chắn và tính đúng bộ phận để nhận đƣợc tính dễ kiểm soát, tính mạnh mẽ, chi phí cho lời giải thấp và phù hợp với thực tế hơn”. Nhƣ vậy, thay cho việc tìm kiếm lời giải tối ƣu, ta có thể tìm kiếm các lời giải xấp xỉ tốt. Chỉ khi nào cần thiết hoặc khi có điều kiện thuận lợi ta mới nghiên cứu bài toán tại một mức kết hạt mịn hơn với nhiều thông tin chi tiết hơn. Tuy nhiên, có thể thấy rằng những nghiên cứu của tính toán hạt chỉ là bổ xung cho những nghiên cứu đòi hỏi tính chính xác cao và những phƣơng pháp tính toán không kết hạt. 1.3 Những vấn đề cơ bản của tính toán hạt Những vấn đề cơ bản của tính toán hạt có thể đƣợc nghiên cứu theo hai khía cạnh: phƣơng pháp xây dựng các hạt và phƣơng pháp tính toán với các hạt. Phƣơng pháp xây dựng các hạt nghiên cứu sự hình thành các công thức, các phép biểu diễn và các cách hiểu các hạt, phƣơng pháp tính toán với các hạt nghiên cứu các tiện ích sử dụng các hạt trong giải quyết bài toán [3] [4] [6]. -8- Cách hiểu các hạt trả lời cho câu hỏi tại sao hai đối tƣợng đƣợc đặt vào trong cùng một hạt. Tổng quát, các phần tử trong một hạt đƣợc nhóm lại với nhau theo các quan hệ không phân biệt đƣợc, quan hệ tƣơng tự hoặc quan hệ có cùng chức năng [1] [3] [6]. Hơn nữa, các hạt thông tin phụ thuộc vào các tri thức sẵn có. Trong việc xây dựng các hạt, cần thiết phải nghiên cứu các tiêu chuẩn để quyết định hai phần tử nào nên đƣợc đặt trong cùng một hạt dựa trên các thông tin có đƣợc. Nói cách khác, cần thiết phải xây dựng một cách hiểu ngữ nghĩa cho các quan hệ không phân biệt đƣợc, quan hệ đồng dạng hoặc quan hệ có cùng chức năng. Cũng cần thiết phải xây dựng các cấu trúc kết hạt của một tập tổng thể. Hình thành công thức và biểu diễn các hạt nghiên cứu các vấn đề thuộc thuật toán của phƣơng pháp xây dựng các hạt. Chúng trả lời cho câu hỏi đặt hai đối tƣợng vào trong cùng một hạt nhƣ thế nào. Các thuật giải cần đƣợc phát triển để xây dựng các hạt một cách hiệu quả [1] [3] [6]. Để tính toán với các hạt, chúng ta cần phải hiểu đƣợc mối liên hệ giữa các hạt nhƣ mối quan hệ gần gũi, mối quan hệ phụ thuộc, mối quan hệ kết hợp và định nghĩa và cách hiểu các phép toán trên các hạt. Hay chúng ta cần thiết kế một hệ phƣơng pháp và các công cụ cho tính toán hạt nhƣ các phép toán xấp xỉ, các lập luận và các suy luận với chúng [1] [3] [4] [5] [6]. 1.4 Một số mô hình tính toán hạt Để hiểu rõ hơn về tính toán hạt, luận văn trình bầy một số mô hình cụ thể của tính toán hạt. Đó là mô hình dựa trên lý thuyết tập mờ của Zadel, mô hình dựa trên lý thuyết tập thô và mô hình dựa trên lý thuyết tập hợp thông thƣờng. 1.4.1 Các tập mờ Một mô hình tính toán hạt tổng quát đƣợc trình bày bởi Zadeh [6] dựa trên lý thuyết các tập mờ. Các hạt đƣợc xây dựng từ khái niệm của các ràng buộc tổng quát. Mối quan hệ giữa các hạt đƣợc biểu diễn bằng đồ thị mờ hoặc đƣợc biểu diễn dƣới dạng các luật nếu-thì mờ [6]. Gọi X là một biến nhận giá trị trong một tập U. Một ràng buộc tổng quát trên các giá trị của X có thể đƣợc biểu diễn bởi X isr R, trong đó R là quan hệ ràng buộc, isr là một biến nối và R là một đại lƣợng rời rạc. Khi đó một hạt đƣợc định nghĩa bằng một tập mờ: G   X | X isr R . Tuỳ thuộc vào từng kiểu ràng buộc mà chúng ta có thể nhận đƣợc rất nhiều các lớp hạt khác nhau [6]. -9- Ta có thể gán các nhãn cho các hạt bằng các từ của ngôn ngữ tự nhiên. Điều này thiết lập một nền tảng cơ bản cho việc tính toán với các từ. Nhƣ một trong các thành phần cơ bản của logic mờ, tính toán với các từ sử dụng các luật nếu-thì mờ dƣới dạng: Nếu X isr1 A thì Y isr2 B trong đó R1 và R2 có thể biểu diễn các kiểu khác nhau của các ràng buộc, mặc dù chúng thƣờng có kiểu hay sử dụng là giống nhau. Một tập các luật nếu-thì mờ có thể đƣợc biểu diễn bằng một đồ thị mờ. Ta có thể sử các luật nếu-thì mờ hoặc các đồ thị mờ để tìm ra kết kết quả lập luận [6]. 1.4.2 Các tập thô Với các kết hạt của một tập tổng thể, chúng ta nghiên cứu các phần tử trong một hạt là một khối thay cho việc quan sát chúng dƣới dạng các hạt cụ thể [6]. Khi hệ thống chứa thông tin về các hạt chƣa đầy đủ, có nghĩa là chỉ có một số tập con của tập tổng thể đƣợc mô tả một cách chính xác, các tập con còn lại có các phần tử là không phấn biệt đƣợc. Lý thuyết các tập thô đƣợc sử dụng trong các trƣờng hợp xấp xỉ hạt thông tin [1]. Gọi E  U U là một quan hệ tƣơng đƣơng trên tập tổng thể U. Cặp apr  U , E  đƣợc gọi là một không gian xấp xỉ. Quan hệ tƣơng đƣơng E phân hoạch tập U thành các tập con không giao nhau. Mỗi lớp tƣơng đƣơng có thể đƣợc quan sát nhƣ một hạt chứa các phần tử không phân biệt đƣợc và nó cũng đƣợc coi nhƣ một hạt tƣơng đƣơng. Một biểu diễn ngữ nghĩa cụ thể của các quan hệ tƣơng đƣơng đƣợc cung cấp dựa trên các khái niệm của các bảng thông tin. Hai đối tƣợng là tƣơng đƣơng nếu chúng có các giá trị chính xác giống nhau trong một tập các thuộc tính. Do đó một hạt tƣơng đƣơng đƣợc mô tả bởi một ràng buộc tƣơng đƣơng [6]. Một tập X  U có thể không là hợp của một số lớp tƣơng đƣơng. Điều đó nói lên rằng ta không thể mô tả X một cách chính xác khi sử dụng các lớp tƣơng đƣơng của E. Trong trƣờng hợp này ta có thể mô tả X bằng một cặp các xấp xỉ trên và xấp xỉ dƣới: apr(X)=   x  x E  X E , apr(X)=   x  xE  X  E trong đó  xE   y | xEy là lớp tƣơng đƣơng chứa x. Xấp xỉ dƣới apr  X  là hợp của tất cả các hạt tƣơng đƣơng mà chúng là tập con của X. Xấp xỉ trên apr( X ) là hợp của tất cả các hạt tƣơng đƣơng mà chúng có giao với X khác rỗng. Dựa trên khái niệm xấp xỉ của các tập, ta có thể thiết lập các tác vụ khai phá và phân tích dữ liệu trong các bảng thông tin, chẳng hạn nhƣ thu gọn thuộc tính, phân tích tính phụ thuộc và học các luật quyết định [6]. - 10 - 1.4.3. Một mô hình dựa trên lý thuyết tập hợp của tính toán hạt Trong phần này, luận văn trình bày một hệ thống dựa trên lý thuyết tập hợp của tính toán hạt. Mỗi hạt biểu diễn một khái niệm cụ thể và mỗi phần tử của hạt là một bản thể của khái niệm đó. Các hạt có thể đƣợc xây dựng trên các bảng thông tin, nhƣ đƣợc trình bày trên lý thuyết tập thô [6]. Việc sử dụng các tập xác định (các hạt) có thể đƣợc biểu diễn tƣơng tự một họ các tập xác định (các hạt) sử dụng nhát cắt của nó. Các phép toán trên các hạt mờ do đó có thể đƣợc định nghĩa bằng các phép toán trên nhát cắt. 1.4.3.1 Đại số luỹ thừa Giả sử U là một tập hợp và o là một phép toán hai ngôi trên U. Ta định nghĩa một phép toán hai ngôi o+ trên các tập con của U nhƣ sau: X  Y   x  y | x  X , y  Y  với mọi X , Y  U . Tổng quát, ta có thể suy rộng bất kỳ phép toán f trên các phần tử của U thành một phép toán f+ trên các tập con của U, và gọi là phép toán luỹ thừa của f. Giả sử f : U n  U  n  1 là một phép toán n ngôi trên U. Phép toán luỹ thừa f  :  2U   2U đƣợc định nghĩa: n f  ( X 0 ,..., X n1 )   f ( x0 ,..., xn1 ) | xi  X i , i = 0,...,n-1 với mọi X 0 ,..., X n1  U . Với mỗi bộ (U , f1 ,..., f k ) của tập cơ sở U và các phép toán f1 ,..., f k , đại số luỹ thừa của chúng đƣợc cho bởi bộ (2U , f1 ,..., f k ) . Phép toán luỹ thừa f+ có thể có một số tính chất của f. Ví dụ với một phép toán hai ngôi f : U 2  U , nếu f là giao hoán và kết hợp thì f+ cũng tƣơng ứng là giao hoán và kết hợp. Nếu e là một phần tử đơn vị với một phép toán f, tập {e} là một phần tử đơn vị với f+. Nếu một phép toán f : U  U là một phép đối hợp, tức là f  f  x    f  x  , f+ cũng là một phép đối hợp. Nhƣng nhiều tính chất của f không còn đúng với f+. Ví dụ, nếu một phép toán hai ngôi f là luỹ đẳng, f  x, x   x , f+ không thể là luỹ đẳng. Nếu một phép toán hai ngôi g là phân phối trên f, g+ không là phân phối trên f+. 1.4.3.2 Đại số khoảng Một khoảng  a, a  với a  a là các số thực đƣợc định nghĩa bởi:    a, a   x | a  x  a .   Các khoảng đặc biệt có dạng [a, a] là tƣơng đƣơng với các số thực. - 11 - Ta có thể thực hiện các phép toán trên các khoảng bằng cách suy rộng các phép toán trên các số thực. Giả sử A   a, a  và B  b, b  là hai khoảng, ta có: A  B   x  y | x  A, y  B  a  b, a  b  . A  B  x  y | x  A, y  B  a  b, a  b  . A.B   x.y | x  A, y  B   min( ab,ab,ab,ab ),max( ab,ab,ab,ab ) . A / B   x / y | x  A, y  B   a, a) .  1 , 1  , 0  b, b  .  b b  Đại số khoảng cho ta một một nền tảng cơ bản cho lập luận khoảng với các giá trị là các số thực, nhƣ lập luận mờ khoảng, và lập luận với các xác xuất hạt [8]. Nó có thể đƣợc mở rộng một cách dễ dàng để nghiên cứu số học mờ với các số mờ [8]. 1.4.3.3 Đại số tập khoảng Giả sử U là một tập hợp và hai tập A1 , A2  2U , A1  A2 . A   A1 , A2    X  2U | A1  X  A2  đƣợc gọi là một tập khoảng đóng. Tập A1 đƣợc gọi là biên dƣới của tập khoảng, và tập A2 là biên trên. Các tập khoảng đặc biệt dạng [A,A] là tƣơng đƣơng với các tập thông thƣờng. Suy rộng các phép toán của lý thuyết tập hợp nhƣ phép giao, phép hợp và phần bù, chúng ta định nghĩa các phép toán của tập khoảng nhƣ sau: A  B   X  Y | X  A, Y  B   A1  B1 , A2  B2  A  B   X  Y | X  A, Y  B   A1  B1 , A2  B2  A \ B   X  Y | X  A, Y  B   A1  B2 , A2  B1  Phép toán phủ định tập khoảng  A1 , A2  của  A , A  đƣợc định U ,U  \  A , A  . Điều này tƣơng đƣơng với U  A ,U  A   ~ A ,~ A  . 1 2 2 1 1 2 2 nghĩa bởi 1 1.5 Kết luận Tính toán hạt có một tầm ảnh hƣởng lớn trong việc thiết kế và triển khai các hệ thống thông tin thông minh, và trong việc giải các bài toán trong thực tế. Các kết quả từ những nghiên cứu đang tồn tại chỉ ra sự phong phú và tính mềm dẻo của tính toán hạt. Những nghiên cứu đó cũng chỉ ra sự cần thiết phải nghiên cứu xa hơn, đặc biệt là khía cạnh ngữ nghĩa của tính toán hạt. - 12 - CHƢƠNG 2: BÀI TOÁN QUYẾT ĐỊNH VÀ PHƢƠNG PHÁP GIẢI QUYẾT DỰA VÀO HẠT DỮ LIỆU 2.1 Các cách kết hạt từ một tập Khái niệm về quan hệ “không phân biệt đƣợc” cung cấp một phƣơng pháp mô tả mối quan hệ giữa các phần tử trong một tập tổng thể. Trong lý thuyết các tập thô, quan hệ không phân biệt đƣợc đƣợc mô hình hoá bằng một quan hệ tƣơng đƣơng. Một quan sát kết hạt của tập tổng thể có thể nhận đƣợc từ các lớp tƣơng đƣơng. Bằng cách thay đổi quan hệ tƣơng đƣơng thành quan hệ chỉ có tính chất phản xạ, ta có thể nhận đƣợc các cách kết hạt khác nhau của một tập tổng thể. 2.1.1 Kết hạt bằng các quan hệ tƣơng đƣơng Giả sử E  U U là một quan hệ tƣơng đƣơng trên một tập hữu hạn khác rỗng U. E có tính phản xạ, đối xứng và bắc cầu. Quan hệ tƣơng đƣơng có thể đƣợc định nghĩa dựa trên các tri thức sẵn có. Ví dụ trong một bảng thông tin, các phần tử trong bảng đƣợc mô tả bằng một tập các thuộc tính. Hai phần tử đƣợc gọi là tƣơng đƣơng nếu chúng có cùng giá trị trên một số thuộc tính nào đó. Lớp tƣơng đƣơng:  xE   y U | yEx chứa tất cả các phần tử tƣơng đƣơng với x và gọi là lớp tƣơng đƣơng chứa x. Quan hệ E tạo ra một phân hoạch của tập U:   U / E   x E | x U . Do đó U/E là họ các tập con của tập tổng thể từng đôi một không giao nhau và   x xU E  U . Phân hoạch là một tập thƣơng và cung cấp một quan sát kết hạt của tập tổng thể qua quan hệ tƣơng đƣơng của các phần tử. Một cách trực giác, các tri thức có đƣợc chỉ cho phép chúng ta xử lý một lớp tƣơng đƣơng. Nói cách khác, thông qua quan sát kết hạt chúng ta nghiên cứu một lớp tƣơng đƣơng dƣới dạng khối thay vì nghiên cứu từng phần tử riêng lẻ trong lớp đó. Cặp apr = (U,E) đƣợc gọi là một không gian xấp xỉ. Mỗi lớp tƣơng đƣơng đƣợc gọi là một hạt cơ bản. Các hạt cơ bản, tập rỗng và hợp của các lớp tƣơng đƣơng đƣợc gọi là các hạt xác định trong trƣờng hợp chúng có thể đƣợc định nghĩa một cách chính xác qua các lớp tƣơng đƣơng của E. Ý nghĩa của các tập xác định sẽ đƣợc giải thích rõ hơn trong phần sau. Gọi Def(U/E) là tập của tất cả các hạt xác định. Def(U/E) đóng với các phép lấy phần bù, phép giao và phép hợp. - 13 - 2.1.2 Kết hạt bằng các quan hệ đồng dạng Giả sử R là một quan hệ hai ngôi trên tập tổng thể U biểu diễn tính đồng dạng của các phần tử trong U. Chúng ta giả thiết rằng R có tính chất phản xạ, tức là một phần tử e là đồng dạng với chính nó, nhƣng không nhất thiết phải có tính đối xứng và bắc cầu. Với hai phần tử x, y U , nếu xRy thì ta nói rằng x là đồng dạng với y. Quan hệ R có thể đƣợc biểu diễn thuận tiện hơn sử dụng tập các phân tử đồng dạng với x, hoặc lân cận gần nhƣ sau:  x R   y U | yRx . Tập (x)R chứa tất cả các phần tử đồng dạng với x. Chúng ta có x  ( x) R . Khi R là một quan hệ tƣơng đƣơng, (x)R là lớp tƣơng đƣơng chứa x. Họ của các lân cận gần: U / R   x  R | x U  là phủ của tập tổng thể, nghĩa là   x xU R  U . Với hai phần tử x, y U , (x)R và (y)R có thể khác nhau và có giao khác rỗng. Điều này dẫn tới một quan sát kết hạt khác của tập tổng thể. Theo quan hệ đồng dạng, một phần tử x đƣợc quan sát bởi một tập các phần tử đồng dạng với nó là (x)R. Chúng ta định nghĩa một quan hệ tƣơng đƣơng trên U nhƣ sau: x R y   x R   y R . Hai phần tử là tƣơng đƣơng nếu chúng có cùng lân cận. Nếu R là một quan hệ tƣơng đƣơng thì  R là R. Cặp apr=(U,R) đƣợc nghiên cứu là một không gian xấp xỉ tổng quát. Lân cận (x) R đƣợc gọi là một hạt cơ bản. Các hạt cơ bản, tập rỗng và hợp của các hạt cơ bản đƣợc gọi là các hạt xác định trong không gian apr = (U, R). Gọi Def(U / R) là tập tất cả các hạt xác định. Nó là đóng với phép hợp, và có thể không cần thiết là đóng với phép giao và phép lấy phần bù. Tập Def(U / R) chứa cả tập rỗng và tập U. Từ Def(U / R), ta định nghĩa: Def C (U / R)   AC | A  Def (U / R) , trong đó Ac là phần bù của A. Hệ thống mới Def C(U/R) chứa rỗng và U và đóng với phép giao. Hệ thống này còn đƣợc gọi là hệ thống đóng kín. Nếu quan hệ R là một quan hệ tƣơng đƣơng thì hai hệ thống là một. Trong trƣờng hợp tổng quát, hai hệ thống là không giống nhau. - 14 - 2.2 Giới thiệu về các tập thô 2.2.1 Giới thiệu Tập thô là một lý thuyết toán học mới nhằm giải quyết các bài toán có tính không chắc chắn. Lý thuyết này là độc lập với lý thuyết logic mờ, và nó là tổng quát của lý thuyết các tập thông thƣờng. Tập thô cũng là một mô hình cụ thể của tính toán hạt và đã đƣợc ứng dụng thành công trong rất nhiều lĩnh vực nhƣ học máy, khai phá dữ liệu, phân tích dữ liệu, các hệ chuyên gia và nhiều lĩnh vực khác. Trong lý thuyết tập thô, có một giả thiết cơ bản, đó là các đối tƣợng đƣợc định nghĩa, đƣợc biểu diễn hoặc thiết lập dựa trên một số hữu hạn các thuộc tính hoặc các tính chất. Từ những năm đầu của thập kỷ 1980, Pawlak đã hình thức hóa vấn đề này thành khái niệm hệ thông tin (bảng thông tin). Định nghĩa 2.1.( Hệ thông tin ) Hệ thông tin là cặp A = (U, A) trong đó U là một tập hữu hạn khác rỗng các đối tượng và A là một tập hữu hạn khác rỗng các thuộc tính, trong đó a : U  Va với mọi a  A. Tập Va được gọi là tập giá trị của a. Giả sử chúng ta có dữ liệu về 6 bệnh nhân nhƣ trong bảng 1 dƣới đây. Bệnh nhân (Patient) Đau đầu (Headac Đau cơ (Muscle-pain) Nhiệt độ (Temperature) Bị bệnh cúm (Flu) he) p1 không có cao có p2 Có không cao có p3 Có có rất cao có p4 không có bình thường không p5 Có không cao không p6 không có rất cao có Bảng 2.1: Dữ liệu về các bệnh nhân bị bệnh cúm. Ta nhận thấy các đối tƣợng khác nhau p1 và p4, lại có các giá trị trên các thuộc tính đau đầu và đau cơ giống nhau: đây là trƣờng hợp không phân biệt được các đối tƣợng nếu chỉ sử dụng thông tin từ các thuộc tính đau đầu và đau cơ. Tính không phân biệt đƣợc là một trong những yếu tố của sự mập mờ. Có thể nhận thấy tính mập mờ từ việc không phân biệt đƣợc: nếu chỉ xem xét các thuộc tính trên đây thì hai đối tƣợng p1 và p4 là hoàn toàn giống nhau, tuy nhiên khi quyết định bị bệnh cúm thì chỉ có bệnh nhân p1 bị mắc bệnh. - 15 - Khái niệm bảng quyết định. Trong nhiều ứng dụng, ngƣời ta đã biết nội dung, kết quả của việc phân lớp là các quyết định phân lớp. Tri thức (chỉ dẫn quyết định) phân lớp đƣợc thể hiện bằng một thuộc tính riêng biệt đƣợc gọi là thuộc tính quyết định trong hệ thông tin. Trong trƣờng hợp đó, hệ thông tin đƣợc gọi là bảng quyết định [1,5,9,10]. Định nghĩa 2.2. (Bảng quyết định ) Bảng quyết định là hệ thông tin có dạng A  (U , A {d}) , (hay A  (U , A,{d})) , với d  A là thuộc tính quyết định. Các thuộc tính thuộc A được gọi là thuộc tính điều kiện hay điều kiện. Thuộc tính quyết định có thể có nhiều hơn hai giá trị, tuy nhiên thông dụng là thuộc kiểu logic. Nhƣ vậy chúng ta không thể phân biệt đƣợc một số đối tƣợng đƣợc mô tả từ một tập thuộc tính. Nhƣng chúng ta lại có thể quan sát, đo hoặc định nghĩa một tập các đối tƣợng trong một khối tổng thể, không phân biệt đƣợc chúng dƣới dạng các đối tƣợng riêng lẻ, và trong tập luỹ thừa, chỉ một số tập con có thể đƣợc đo hoặc đƣợc định nghĩa. Do đó, tình trạng không chắc chắn xảy ra khi chúng ta muốn phân biệt cụ thể các đối tƣợng này. Một trong những ý tƣởng cơ bản là làm thế nào để chúng ta có thể biểu diễn các tập con không xác định thông qua các tập con xác định. Trả lời cho câu hỏi này ta có một giải pháp: một tập con không xác định đƣợc biểu diễn một cách xấp xỉ bằng hai tập con xác định, đƣợc gọi là các xấp xỉ trên và xấp xỉ dƣới. 2.2.2 Các định nghĩa về các tập thô Giả sử U là một tập hữu hạn và đƣợc gọi là tập tổng thể, E là một quan hệ tƣơng đƣơng trên U. Dƣới đây là một số ký hiệu đƣợc sử dụng trong luận văn.  U/E là phân hoạch sinh bởi quan hệ tƣơng đƣơng E.  [x]E biểu diễn lớp tƣơng đƣơng chứa x.  apr=(U, E) đƣợc gọi là một không gian xấp xỉ.  Def(U) là họ tất cả các tập con xác định trên U. 2.2.2.1 Định nghĩa hƣớng phần tử Định nghĩa 2.3. Với bất kỳ tập con X  U , các xấp xỉ trên và xấp xỉ dƣới đƣợc định nghĩa nhƣ sau: apr ( X )   x | y  U  xEy  y  X  apr ( X )   x | y  U  xEy  y  X  - 16 - Một phần tử x thuộc vào xấp xỉ dƣới nếu tất cả các phần tử tƣơng đƣơng với nó thuộc vào X. Một phần tử x thuộc vào xấp xỉ trên nếu ít nhất có một phần tử tƣơng đƣơng với nó thuộc vào X. Định nghĩa hƣớng phần tử có liên quan tới lý thuyết tập thô trong mô hình logic. Vấn đề này chúng ta sẽ xem xét trong phần tiếp theo. 2.2.2.2 Định nghĩa hƣớng hạt Khi quan sát x trong lớp tƣơng đƣơng chứa x, định nghĩa 2.3 có thể đƣợc viết lại nhƣ sau: Định nghĩa 2.4. Với bất kỳ tập con X  U , các xấp xỉ trên và xấp xỉ dƣới đƣợc định nghĩa nhƣ sau: apr ( X )    x E |  x E  X  apr ( X )    x E |  x E  X   Xấp xỉ dƣới là hợp của các lớp tƣơng đƣơng nằm trọn trong X. Xấp xỉ trên là hợp của các lớp tƣơng đƣơng có giao khác rỗng với X. Định nghĩa hƣớng hạt cung cấp một mô hình cho tính toán hạt. Trong một không gian xấp xỉ tổng quát apr = (U, R), các xấp xỉ tập thô hƣớng hạt có thể đƣợc định nghĩa nhƣ trên nhƣng lớp tƣơng đƣơng [x]E đƣợc thay bằng lân cận (x)R. 2.2.2.3 Định nghĩa hƣớng hệ thống con Định nghĩa 2.5. Với bất kỳ tập con X  U , các xấp xỉ trên và xấp xỉ dƣới đƣợc định nghĩa bởi: apr ( X )   Y | Y  Def (U )  Y  X  apr ( X )   Y | Y  Def (U )  X  Y  Xấp xỉ dƣới là tập xác định lớn nhất nằm trong X. Xấp xỉ trên là tập xác định nhỏ nhất chứa X. Định nghĩa này đƣợc sử dụng trong không gian tô pô, các hệ thống đóng và các hệ thống toán học khác cũng nhƣ các hàm tin cậy. 2.2.2.4 Các hàm thuộc thô Một định nghĩa tập thô khác đƣợc định nghĩa dựa trên các hàm thuộc thô. Kết quả này đƣợc thực hiện dựa trên khái niệm các hàm thuộc trong logic mờ. Định nghĩa 2.6. Với mỗi tập con A  U , hàm thuộc thô của nó đƣợc định nghĩa bởi: A ( X )   x  A  x E  P ( X |  x E ) , E - 17 - trong đó  là ký hiệu lực lƣợng của một tập. Giá trị thuộc thô  A ( x) có thể hiểu là xác suất có điều kiện để một phần tử bất kỳ thuộc vào A thì thuộc vào [x]E. Trên thực tế các xác suất có điều kiện đã đƣợc sử dụng trƣớc khi có sự phát triển của mô hình tập thô theo lý thuyết xác xuất. Các hàm thuộc thô có thể đƣợc hiểu nhƣ các hàm thuộc mờ. Khi áp dụng các hàm thuộc mờ trong lý thuyết tập thô chúng ta có: (1) U ( x)  1, (2)  ( x)  0, (3) y   x E   A ( x)   A ( y), (4) x  A   A ( x)  0, (5) x  A   A ( x)  1, (6)  A ( x)  1,   xE   A (7)  A ( x)  0,   xE   A   (8) A  B   A ( x)  B ( x) Tính chất (3) chỉ ra rằng các phần tử trong cùng lớp tƣơng đƣơng phải có cùng mức thuộc. Do đó các phần tử không phân biệt đƣợc phải có cùng giá trị thuộc. Tính chất (4) và (5) có thể đƣợc diễn đạt một cách tƣơng đƣơng nhƣ sau: (4)  A ( x)  0  x  A, (5)  A ( x)  1  x  A, Trong một không gian xấp xỉ tổng quát, apr = (U, R) đƣợc định nghĩa bằng một quan hệ phản xạ, với một tập con A của tập tổng thể, một hàm thuộc thô có thể đƣợc định nghĩa bằng cách thay [x]E bởi (x)E nhƣ sau:  A ( x)   x R  A .  x R Dựa trên tính chất phản xạ của quan hệ R, ta có thể kiểm tra các tính chất (1), (2), (4) và (8) vẫn đúng khi thay [x]E bằng (x)R. Với (3) ta có kết quả mạnh hơn: (3a)  y  ( x) R ,  A ( x)  1   A ( y)  0 . (3b)  y  ( x) R ,  A ( x)  0    A ( y)  1 . hoặc có thể viết (3a)  y  ( x) R ,  A ( y)  0    A ( x)  1 . (3b)  y  ( x) R ,  A ( y)  1   A ( x)  0 . Chúng có thể đƣợc hiểu một cách tƣơng tự đối với các quan hệ tƣơng đƣơng: (3c) x R y   A ( x)   A ( y) . - 18 -