ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ KIM OANH KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH NHỜ LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ KIM OANH KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH NHỜ LÝ THUYẾT TẬP THÔ
Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS. VŨ ĐỨC THI Hà Nội - 2014
1
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành nhất tới GS.TS Vũ Đức Thi, Viện Công nghệ thông tin – Đại học Quốc gia Hà Nội đã tận tình hướng dẫn, định hướng, đóng góp những ý kiến quý báu cho tôi trong quá trình thực hiện luận văn.
Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giảng dạy và truyền thụ cho tôi những kiến thức quý báu trong suốt quá trình học tập tại trường. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn này.
Hà Nội, ngày tháng 6 năm 2014
Học viên
Hoàng Thị Kim Oanh
2
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày tháng 6 năm 2014
Học viên
Hoàng Thị Kim Oanh
3
MỤC LỤC
LỜI CẢM ƠN ............................................................................................................................................................ 1
LỜI CAM ĐOAN..................................................................................................................................................... 2
MỤC LỤC ................................................................................................................................................................... 3
DANH MỤC CÁC THUẬT NGỮ .................................................................................................................... 5
DANH MỤC CÁC KÝ HIỆU, CÁC 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
Chƣơng 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ .................................................... 12
1.1. Hệ thông tin ........................................................................................................................... 12
1.2. Bảng quyết định .................................................................................................................... 13
1.3. Quan hệ không phân biệt được ............................................................................................ 14
1.4. Các tập xấp xỉ ........................................................................................................................ 16
1.5. Tập rút gọn và tập lõi ............................................................................................................ 18
1.6. Ma trận phân biệt và hàm phân biệt .................................................................................... 20
Chƣơng 2. PHƢƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG
QUYẾT ĐỊNH ........................................................................................................................................................ 21
2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định ...................................................... 21
2.2. Phương pháp rút gọn thuộc tính dựa trên entropy Shannon ............................................. 25
2.2.1. Entropy Shannon trên bảng quyết định .................................................................. 25
2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon ........................................ 26
2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon .................................. 27
2.2.4. Độ quan trọng của thuộc tính dựa trên entropy Shannon ....................................... 27
2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon .......... 28
2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định ................................................ 34
2.3.1. Luật quyết định ....................................................................................................... 34
2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn .................. 35
2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định ............. 38
Chƣơng 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ...................................................................... 40
3.1. Bài toán .................................................................................................................................. 40
3.2. Một số kết quả thử nghiệm .................................................................................................. 40
4
3.2.1. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon ........ 40
3.2.2. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn .............. 42
3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế .......................................................... 44
3.4. Một số giao diện chương trình ............................................................................................. 45
3.4.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC ........................................... 45
3.4.2. Thực hiện thuật toán sinh luật quyết định .............................................................. 45
KẾT LUẬN .............................................................................................................................................................. 48
TÀI LIỆU THAM KHẢO ................................................................................................................................. 49
5
DANH MỤC CÁC THUẬT NGỮ
Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh
Tập thô Rough Set
Hệ thông tin Information System
Hệ thông tin đầy đủ Complete Information System
Bảng quyết định Decision Table
Bảng quyết định đầy đủ Complete Decision Table
Quan hệ không phân biệt được Indiscernibility Relation
Xấp xỉ dưới Lower Approximation
Xấp xỉ trên Upper Approximation
Rút gọn thuộc tính Attribute Reduction
Tập rút gọn Reduct
Tập lõi Core
Ma trận phân biệt Indiscernibility Matrix
Hàm phân biệt Indiscernibility Function
Luật quyết định Decision Rule
6
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu, từ viết tắt Diễn giải
Hệ thông tin, hệ thông tin đầy đủ
Bảng quyết định, bảng quyết định đầy đủ
Số đối tượng
Số thuộc tính điều kiện trong bảng quyết định
Số thuộc tính trong hệ thông tin
Giá trị của đối tượng tại thuộc tính
Quan hệ không phân biệt
Lớp tương đương chứa của quan hệ
Phân hoạch của sinh bởi tập thuộc tính .
Hàm quyết định suy rộng của đối tượng đối với .
miền dương của
Họ tất cả các tập rút gọn Pawlak
Họ tất cả các tập rút gọn Entropy Shannon
Tập lõi dựa trên miền dương
Tập lõi dựa trên entropy Shannon có điều kiện
Entropy Shannon của tập thuộc tính P
Entropy Shannon có điều kiện của Q khi đã biết P
7
DANH MỤC CÁC BẢNG
Bảng 1.1. Ví dụ về hệ thông tin ............................................................................................... 13
Bảng 1.2. Ví dụ một bảng quyết định ...................................................................................... 14
Bảng 1.3. Bảng thông tin về bệnh cúm ................................................................................... 17
Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1 ....................................................................... 26
Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.2 ....................................................................... 29
Bảng 2.3. Bảng quyết định về bệnh cúm ................................................................................. 36
Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC ............................................................ 41
Bảng 3.2. Kết quả thực hiện Thuật toán CEBARKCC ............................................................ 42
Bảng 3.3. Tập rút gọn tốt nhất của bộ số liệu Soybean - small.data ....................................... 43
Bảng 3.4. Các luật phân lớp trên bảng quyết định rút gọn ....................................................... 43
8
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Mô tả về tập xấp xỉ và miền .................................................................................... 16
Hình 3.1. Giao diện thực hiện thuật toán rút gọn thuộc tính ................................................... 45
Hình 3.2. Giao diện tìm tập rút gọn với bộ số liệu Soybean – small.data ............................... 46
Hình 3.3. Tập rút gọn thu được với bộ số liệu Soybean – small.data ...................................... 46
9
MỞ ĐẦU
Ngày nay với sự bùng nổ của công nghệ thông tin và mạng Internet, lượng dữ liệu đang ngày càng tăng lên một cách nhanh chóng khiến chúng ta rơi vào tình trạng “ngập lụt thông tin". Chính vì vậy, các chuyên gia cho rằng, hiện nay chúng ta đang sống trong một xã hội “rất giàu về thông tin nhưng nghèo về tri thức”. Trước tình hình đó đòi hỏi phải phát triển các phương pháp khai phá, phát hiện ra những thông tin, tri thức có ích bị che giấu trong các “núi” dữ liệu phục vụ cho các nhà quản lý, các chuyên gia, từ đó thúc đầy khả năng sản xuất, kinh doanh của các tổ chức, doanh nghiệp. Do đó, khai phá dữ liệu (Data Mining) ra đời nhằm đáp ứng nhu cầu này.
Lý thuyết tập thô do nhà logic học Balan Zdzislak Pawlak [17] đề xuất vào đầu những năm 80 được xem như là một cách tiếp cận mới để phát hiện tri thức và tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu. Nó rất hữu ích trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật, … chứa dữ liệu mơ hồ không chắc chắn. Các mối quan hệ trong mô hình này được biểu diễn qua quan hệ không phân biệt được, còn các dữ liệu được biểu diễn thông qua tập xấp xỉ trên và xấp xỉ dưới của nó.
Dữ liệu trong lý thuyết tập thô được biểu diễn thông qua hệ thông tin hay bảng quyết định. Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định.
Hiện nay các cơ sở dữ liệu (CSDL) cần khai phá thường có kích thước rất lớn, chẳng hạn như CSDL tin sinh học, CSDL đa phương tiện, … Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó khăn trong việc khai phá, thậm chí còn làm cho nhiệm vụ khai phá trở nên bất khả thi. Vấn đề đặt ra là phải tìm cách rút gọn số thuộc tính mà không làm mất những thông tin cần thiết phục vụ nhiệm vụ khai phá.
Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin phân lớp của bảng quyết định.
10
Mười năm trở lại đây, nhiều nhóm nhà khoa học trên thế giới quan tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng lý thuyết tập thô. Các phương pháp chính là: phương pháp dựa trên miền dương, phương pháp sử dụng các phép toán trong đại số quan hệ, phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng entropy thông tin, …. Tại Việt Nam, luận án tiến sĩ của tác giả Hoàng Thị Lan Giao [1] đã đề xuất các thuật toán heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán, bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán sử dụng ma trận phân biệt. Luận án tiến sĩ của tác giả Nguyễn Đức Thuần [2] đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô. Luận án tiến sĩ của tác giả Nguyễn Long Giang [3] đã đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ và không đầy đủ sử dụng metric.
Với những lý do trên, tập thô đã chứng tỏ là một trong những lý thuyết rất hiệu quả trong lĩnh vực khai phá dữ liệu. Vì vậy tôi đã chọn đề tài “Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô”. Trong luận văn này, tôi nghiên cứu hai vấn đề chính sau:
Tìm hiểu về lý thuyết tập thô: hệ thông tin, bảng quyết định, các tập xấp xỉ,
tập lõi và tập rút gọn.
Tìm hiểu các phương pháp rút gọn thuộc tính, từ đó lựa chọn phương pháp rút gọn thuộc tính sử dụng Entropy Shannon trong bảng quyết định và phương pháp sinh luật quyết định trên tập rút gọn thu được. Sau đó thử nghiệm thuật toán heuristic tìm tập rút gọn trên bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi trên các bộ số liệu mẫu từ kho dữ liệu UCI
Đối tượng nghiên cứu của luận văn là các bảng quyết định với kích thước
trung bình và kích thước lớn.
Phạm vi nghiên cứu của luận văn tập trung vào bài toán rút gọn thuộc
tính ở bước tiền xử lý số liệu trong quá trình khai phá dữ liệu.
Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các mệnh đề được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về
11
nghiên cứu thực nghiệm: luận văn thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI
Bố cục luận văn gồm 3 chương:
Chương 1: Trình bày các khái niệm cơ bản của lý thuyết tập thô được sử
dụng trong chương 2 và chương 3.
Chương 2: Trình bày hai nội dung chính: thứ nhất là tổng kết các phương pháp rút gọn thuộc tính đã công bố, từ đó lựa chọn phương pháp rút gọn thuộc tính dựa trên entropy Shannon. Thứ hai là nghiên cứu phương pháp sinh luật quyết định, các độ đo đánh giá hiệu năng tập luật quyết định, từ đó lựa chọn và đánh giá các phương pháp rút gọn thuộc tính.
Chương 3: Thử nghiệm thuật toán heuristic tìm tập rút gọn trên bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi trên các bộ số liệu mẫu từ kho dữ liệu UCI và thuật toán sinh luật trên bảng quyết định.
12
Chƣơng 1.
KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ
Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak (1926-2006) đề xuất vào năm 1982 đã được ứng dụng ngày càng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết tập thô được phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng… Đặc biệt lý thuyết này thích hợp với các bài toán phân tích trên khối lượng dữ liệu lớn, chứa đựng thông tin mơ hồ, không chắc chắn.
Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ trên và xấp xỉ dưới của một tập. Tập con được tạo ra bởi xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Mỗi tập con xác định thông qua xấp xỉ dưới và xấp xỉ trên được gọi là tập thô.
1.1. Hệ thông tin
Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thường, thông tin thường được biểu diễn dưới dạng các bảng dữ liệu, trong đó mỗi dòng biểu diễn thông tin ứng với một đối tượng, mỗi cột biểu diễn một thuộc tính có thể đo được của đối tượng. Từ đầu những năm 80, Z. Pawlak đã đưa ra một khái niệm mới là hệ thông tin dựa trên khái niệm bảng truyền thống. Có thể định nghĩa hệ thông tin một cách hình thức như sau.
Định nghĩa 1.1. Hệ thông tin là một bộ , trong đó:
U là tập hữu hạn, khác rỗng các đối tượng (tập vũ trụ);
A là tập hữu hạn, khác rỗng các thuộc tính;
với là tập giá trị của thuộc tính ;
là hàm thông tin, với mọi và hàm f cho giá trị .
Với mọi , ta ký hiệu giá trị của đối tượng u tại thuộc tính a là
thay vì . Nếu là một tập con các thuộc tính thì ta
13
ký hiệu bộ các giá trị
bởi . Như vậy, nếu u và v là hai đối tượng, thì ta
viết nếu với mọi .
Ví dụ 1.1. Bảng 1.1 dưới đây biểu diễn về một hệ thông tin của 10 đối tượng với 5 thuộc tính
Bảng 1.1. Ví dụ về hệ thông tin
Ta có một hệ thông tin .
, A = {To, Ly, Ho, Nv, Av}
, , ,
,
1.2. Bảng quyết định
Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết định, ta xét một trường hợp đặc biệt của hệ thông tin được gọi là bảng quyết định.
Bảng quyết định là một dạng đặc biệt của hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con tách biệt nhau: tập các thuộc tính điều kiện C và tập các thuộc tính quyết định D. Bảng quyết định, được ký hiệu là
với .
14
Bảng quyết định được gọi là nhất quán khi và chỉ khi phụ thuộc hàm
CD nghiệm đúng, nghĩa là với mọi kéo theo .
Ngược lại là không nhất quán. Dễ thấy bảng quyết định là nhất quán khi và
chỉ khi . Trong trường hợp bảng không nhất quán thì chính
là tập con cực đại của U sao cho phụ thuộc hàm đúng.
Ví dụ 1.2: Mô tả một bảng quyết định, với các thuộc tính điều kiện lấy ở
Bảng 1.1 và thêm vào thuộc tính quyết định “Tc”
Bảng 1.2. Ví dụ một bảng quyết định
1.3. Quan hệ không phân biệt đƣợc
Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ và xử lý các dữ liệu không phân biệt được. Trong một hệ thông tin theo định nghĩa 1.1 thì cũng có thể có những đối tượng không phân biệt được. Trước tiên ta nhắc lại định nghĩa quan hệ tương đương như sau:
trên U là
Định nghĩa 1.2 Một quan hệ hai ngôi (quan hệ nhị phân) một quan hệ tương đương khi nó thỏa mãn 3 tính chất:
- Phản xạ: Mọi đối tượng đều quan hệ với chính nó
- Đối xứng: Nếu xRy thì yRx
- Bắc cầu: Nếu xRy và yRz thì xRz
15
đương. Lớp tương đương của phần tử tượng y mà xRy.
Quan hệ tương đương R sẽ chia tập các đối tượng U thành các lớp tương , ký hiệu là [x]R, chứa tất cả các đối
Xét hệ thông tin , , quan hệ không phân biệt được trên
U theo P, ký hiệu là , được định nghĩa như sau:
.
Khi đó là một quan hệ tương đương trên U. Nếu thì
hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương
đương xác định một phân hoạch trên U, ký hiệu là hay .
Lớp tương đương trong phân hoạch chứa đối tượng u ký hiệu là :
.
Định nghĩa 1.3. ([18]) Cho hệ thông tin và . Ta nói:
1) Phân hoạch và phân hoạch là như nhau (viết ),
khi và chỉ khi .
2) Phân hoạch mịn hơn phân hoạch (viết ) khi và
chỉ khi .
Tính chất 1.1. ([18]) Xét hệ thông tin và .
1) Nếu thì , mỗi lớp của là một lớp hoặc hợp của
một số lớp thuộc .
2) Với mọi ta có .
Ví dụ 1.3. Xét hệ thông tin cho ở Bảng 1.1, phân hoạch của tập U sinh bởi quan hệ tương đương IND(P):
- Với P={To} ta có IND(P)={{X1, X2, X7, X8}, {X5, X6, X9, X10}, {X3}, X4}}. Lúc này ta nói X1 và X2 là không phân biệt được.
16
1.4. Các tập xấp xỉ
Cho hệ thông tin và tập đối tượng . Với một tập
thuộc tính cho trước, chúng ta có các lớp tương đương của phân hoạch
.
Trong lý thuyết tập thô truyền thống, để biểu diễn tập đối tượng X bằng tri thức có sẵn B, người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương . Có hai cách xấp xỉ tập đối tượng X thông qua tập đương của phân hoạch thuộc tính B , được gọi là B-xấp xỉ dưới và B-xấp xỉ trên của X, ký hiệu lần lượt
là và , được xác định như sau:
Tập bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập
bao gồm các phần tử của U có khả năng được phân loại vào X dựa vào tập
thuộc tính B. Từ hai tập xấp xỉ nêu trên, người ta định nghĩa các tập
: B-miền biên của X , : B-miền ngoài của X.
Dễ thấy B-miền biên của X là tập chứa các đối tượng có thể thuộc X, còn B-miền ngoài (NEGB(X)) của X chứa các đối tượng chắc chắn không thuộc X
Trong trường hợp , X được gọi là tập rõ, ngược lại X được gọi là
tập thô.
Hình 1.1. Mô tả về tập xấp xỉ và miền
17
Ví dụ 1.4. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân cho ở Bảng 1.3.
Bảng 1.3. Bảng thông tin về bệnh cúm
U Đau đầu Thân nhiệt Cảm cúm
Bình thường Không Có u1
Có Cao Có u2
Có Rất cao Có u3
Không Bình thường Không u4
Không Cao Không u5
Không Rất cao Có u6
Không Cao Có u7
Không Rất cao Không u8
Ta có: {Đau đầu} =
{Thân nhiệt} =
{Cảm cúm} =
{Đau đầu, Cảm cúm} =
Như vậy, các bệnh nhân không phân biệt được về đau đầu và cảm
cúm, nhưng phân biệt được về thân nhiệt.
Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là:
.
Đặt (Cảm cúm) = Có} = . Khi đó:
và
Như vậy, B-miền biên của X là tập hợp .
18
1.5. Tập rút gọn và tập lõi
Trong bảng quyết định, các thuộc tính điều kiện được phân thành thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu. Thuộc tính không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết được phân thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính dư thừa thực sự là những thuộc tính dư thừa mà việc loại bỏ tất cả các thuộc tính như vậy không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là thuộc tính lõi.
Định nghĩa 1.3. ([17]) (Tập lõi dựa trên miền dương) Cho bảng quyết định
. Thuộc tính được gọi là không cần thiết (dư thừa)
trong DS dựa trên miền dương nếu ; Ngược lại, c được
gọi là cần thiết. Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi
dựa trên miền dương và được ký hiệu là . Lúc đó, thuộc tính cần
thiết còn được gọi là thuộc tính lõi.
Định nghĩa 1.4. ([17]) (Tập rút gọn dựa trên miền dương) Cho bảng quyết định
và tập thuộc tính . Nếu
1)
2)
thì R là một tập rút gọn của C dựa trên miền dương.
Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu
là họ tất cả các tập rút gọn Pawlak của C. Khi đó
.
Định nghĩa 1.5. ([17]) Cho bảng quyết định và . Ta nói
rằng a là thuộc tính rút gọn của DS nếu tồn tại một tập rút gọn sao
cho .
19
Định nghĩa 1.6. ([17])Cho bảng quyết định
. Ta nói và
rằng a là thuộc tính dư thừa thực sự của DS nếu .
Ví dụ 1.2. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.2.
Bảng 1.2. Bảng quyết định về bệnh cúm
U Mệt mỏi Đau đầu Đau cơ Thân nhiệt Cảm cúm
Có Có Bình thường Không U1 Có
Có Có Cao Có U2 Có
Có Có Rất cao Có U3 Có
Không Có Bình thường Không U4 Có
Không Không Cao Không U5 Có
Không Có Rất cao Có U6 Có
Bảng này có tập thuộc tính điều kiện C = {Mệt mỏi, Đau đầu, Đau cơ,
Thân nhiệt} và thuộc tính quyết định là D = {Cảm cúm}
Bảng này có hai tập rút gọn là R1 = {Đau cơ, Thân nhiệt} và R2 = {Đau đầu, Thân nhiệt}. Như vậy tập lõi là PCORE(C) = {Thân nhiệt} và Thân nhiệt là thuộc tính cần thiết duy nhất. Các thuộc tính không cần thiết bao gồm:
Thuộc tính Mệt mỏi là thuộc tính dư thừa thực sự vì không tham gia vào tập rút
gọn R1 và R2
Hai thuộc tính Đau đầu và Đau cơ là hai thuộc tính rút gọn vì đều có mặt trong một tập rút gọn. Hai thuộc tính này đều không cần thiết theo nghĩa là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính này mà vẫn chuẩn đoán đúng bệnh. Tức là
POS{Đau cơ, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm})
POS{Đau đầu, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}).
20
1.6. Ma trận phân biệt và hàm phân biệt
Ma trận phân biệt do Andrzej Skowron và các cộng sự trong [5] đề xuất là công cụ sử dụng để tìm tập rút của bảng quyết định. Xét bảng quyết định
với . Ma trận phân biệt của , ký hiệu
, là một ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các
thuộc tính được xác định như sau
Định nghĩa 1.7. ([5, 7]): (Tập rút gọn dựa trên ma trận phân biệt) Cho bảng
quyết định , là ma trận phân biệt của DS và tập
thuộc tính . Nếu
1) với mọi
2) Với mọi , không thỏa mãn 1)
thì R được gọi là một tập rút gọn của C dựa trên ma trận phân biệt. Ký hiệu
là họ tất cả các tập rút gọn dựa trên ma trận phân biệt.
Định nghĩa 1.8. ([5, 7]): (Tập lõi dựa trên ma trận phân biệt) Cho bảng quyết
, là ma trận phân biệt của DS. Thuộc tính định
được gọi là không cần thiết (dư thừa) trong DS dựa trên ma trận phân biệt
với mọi . Ngược lại, c được gọi là cần thiết. Tập nếu
tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên ma trận
phân biệt và được ký hiệu là . Theo [7], .
21
Chƣơng 2.
PHƢƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT
TRÊN BẢNG QUYẾT ĐỊNH
Chương này trình bày phương pháp rút gọn thuộc tính trên bảng quyết định sử dụng entropy Shannon trong mô hình tập thô truyền thống. Trên cơ sở đó, phần tiếp theo sẽ trình bày phương pháp sinh luật quyết định từ tập rút gọn tìm được trong mô hình tập thô truyền thống.
2.1. Phƣơng pháp rút gọn thuộc tính trên bảng quyết định
Rút gọn thuộc tính trên bảng quyết định là tìm tập con nhỏ nhất của tập thuộc tính điều kiện mà bảo toàn thông tin phân lớp của bảng quyết định để việc sinh luật và phân lớp đạt hiệu quả cao nhất. Với mục tiêu đó, có rất nhiều các phương pháp rút gọn thuộc tính khác nhau đã được đề xuất dựa trên các tiêu chuẩn khác nhau nhưng đều thực hiện các công việc sau:
1) Đưa ra khái niệm tập rút gọn của phương pháp.
2) Đưa ra khái niệm độ quan trọng của thuộc tính. Ý nghĩa độ quan trọng thuộc tính của tất cả các phương pháp đều giống nhau, đều đặc trưng cho khả năng đóng góp của thuộc tính vào việc phân lớp tập đối tượng. Thuộc tính có độ quan trọng càng lớn thì khả năng đóng góp vào việc phân lớp đối tượng càng nhiều và ngược lại.
3) Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá là độ quan trọng của thuộc tính (chất lượng phân lớp của thuộc tính). Các thuật toán heuristic này thường được xây dựng theo hai hướng tiếp cận khác nhau: hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Dựa vào nhận xét tập lõi xuất hiện trong mọi tập rút gọn nên các thuật toán xây dựng theo hướng tiếp cận bottom-up được chia thành hai nhóm: các thuật toán có tính toán lõi và các thuật toán không tính toán lõi. Ý tưởng chung của các thuật toán có tính toán lõi là xuất phát từ tập lõi, bổ sung dần dần các thuộc tính có độ quan trọng lớn nhất vào tập lõi cho đến khi thu được tập rút gọn. Các thuật toán không tính toán lõi xuất phát từ tập rỗng và bổ sung dần các thuộc tính có độ quan trọng lớn nhất cho cho đến khi thu được tập rút gọn. Các thuật toán được xây dựng theo hướng tiếp cận top - down xuất phát từ tập
22
thuộc tính điều kiện ban đầu, loại bỏ dần các thuộc tính có độ quan trọng nhỏ nhất cho đến khi thu được tập rút gọn. Cả hai hướng tiếp cận này đều đòi hỏi phải sắp xếp danh sách các thuộc tính theo thứ tự giảm dần hoặc tăng dần của độ quan trọng tại mỗi bước lặp.
Cho đến nay có rất nhiều các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo tiếp cận lý thuyết tập thô truyền thống, các phương pháp điển hình được trình bày trong công trình số [1], bao gồm:
1) Phương pháp rút gọn thuộc tính dựa trên miền dương
2) Phương pháp rút gọn thuộc tính sử dụng các phép toán trong đại số
quan hệ
3) Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt
4) Phương pháp rút gọn thuộc tính sử dụng các độ đo trong tính toán hạt
5) Phương pháp rút gọn thuộc tính sử dụng entropy thông tin
Phương pháp rút gọn thuộc tính dựa trên miền dương
Kể từ khi Pawlak [17] đưa ra định nghĩa tập rút gọn dựa trên miền dương,
một số công trình nghiên cứu đã xây dựng thuật toán tính miền dương ,
từ đó xây dựng thuật toán tìm tập rút gọn dựa trên miền dương: Nguyen Sinh Hoa và Nguyen Hung Sơn [16] sử dụng phương pháp sắp xếp nhanh (Quick- sort) để sắp xếp các đối tượng theo giá trị thuộc tính, xây dựng thuật toán tính miền dương; Xu Zhangyan và các cộng sự [28] sử dụng phương pháp sắp xếp theo cơ số (Radix-sort) để xây dựng thuật toán tính miền dương.
Phương pháp rút gọn thuộc tính sử dụng các phép toán trong đại số quan hệ
Trong [8], Hu Xiaohua và các cộng sự đưa ra khái niệm tập lõi và tập rút gọn dựa trên các phép toán trong đại số quan hệ, từ đó xây dựng thuật toán tìm tập lõi và tập rút gọn của bảng quyết định. Trong [1], tác giả Hoàng Thị Lan Giao đã phân tích nhược điểm của khái niệm tập lõi trong [8] và đề xuất khái niệm mới về tập lõi, tập rút gọn của bảng quyết định nhất quán.
Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt
Trong [5], Skowron đưa ra khái niệm ma trận phân biệt, hàm phân biệt và sử dụng chúng để tìm tập rút gọn của bảng quyết định. Dựa trên ma trận phân biệt của Skowron, Hu Xiaohua và Nick Cercone [7] đề xuất thuật toán tìm tập rút gọn, tập
23
lõi của bảng quyết định. Trong [27], Xu Zhangyan và các cộng sự đề xuất thuật toán tìm tập rút gọn trong bảng quyết định dựa trên ma trận phân biệt đơn giản hóa.
Phương pháp rút gọn thuộc tính sử dụng các độ đo trong tính toán hạt
Kể từ khi Zadeh [30] giới thiệu mô hình tính toán hạt, nhiều nhà nghiên cứu đã sử dụng mô hình này để giải quyết bài toán rút gọn thuộc tính trong hệ thông tin. Trong [10,11, 31], các tác giả đã đề xuất các thuật toán heuristic tìm tập rút gọn sử dụng độ đo phép kết hạt bởi thuộc tính làm tiêu chuẩn đánh giá độ quan trọng của thuộc tính. Các thuật toán này được chứng minh là hiệu quả và có thể áp dụng trong các bảng dữ liệu lớn.
Phương pháp rút gọn thuộc tính sử dụng entropy thông tin
Entropy thông tin do Shannon giới thiệu lần đầu vào năm 1948 (gọi tắt là entropy Shannon) là một đại lượng toán học dùng để đo độ không chắc chắc của một đại lượng ngẫu nhiên. Trong những năm gần đây, entropy Shannon là một trong những công cụ hiệu quả để giải quyết bài toán rút gọn thuộc tính trong hệ thông tin.
Nhóm nghiên cứu đầu tiên đề xuất thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon có điều kiện là Miao Duoqian và các cộng sự [15], trong đó các tác giả sử dụng entropy tương hỗ để đánh giá độ quan trọng của thuộc tính và xây dựng thuật toán heuristic tìm tập rút gọn của bảng quyết định MIBARK.
Những đóng góp đáng chú ý tiếp theo trong nghiên cứu phương pháp tìm tập rút gọn sử dụng entropy Shannon phải kể đến các công trình của Wang Guo Yin và các cộng sự [20, 21, 22, 23, 24]. Trong các công trình này, các tác giả đã đưa ra khái niệm tập rút gọn và tập lõi của bảng quyết định dựa trên entropy Shannon có điều kiện và đề xuất hai thuật toán heuristic tìm tập rút gọn của bảng quyết định: thuật toán CEBARKCC và thuật toán CEBARKNC [23]. CEBARKCC là thuật toán heuristic tính toán lõi còn CEBARKNC là thuật toán heuristic không tính toán lõi. Trong cả hai thuật toán, độ quan trọng của thuộc tính đều được xây dựng trực tiếp từ công thức tính entropy có điều kiện. Trong [20], các tác giả đã phân tích nhược điểm của định nghĩa độ quan trọng của thuộc tính trong [23] và đề xuất định nghĩa độ quan trọng mới, từ đó xây dựng thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon có điều kiện.
24
Về cơ bản, mỗi phương pháp rút gọn thuộc tính đều thực hiện các công việc sau: Đưa ra khái niệm tập rút gọn của phương pháp, khái niệm độ quan trọng của thuộc tính (đặc trưng cho khả năng đóng góp của thuộc tính vào việc phân lớp tập đối tượng), xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá là số lượng thuộc tính của tập rút gọn và độ phức tạp của thuật toán heuristic tìm tập rút gọn. Tập rút gọn của phương pháp càng ít thuộc tính thì độ hỗ trợ của tập luật dựa trên tập rút gọn đó càng cao và phương pháp đó càng hiệu quả. Độ phức tạp thuật toán heuristic của phương pháp càng nhỏ thì phương pháp đó càng hiệu quả. Do đó, hoàn toàn có thể đánh giá được tính hiệu quả của các phương pháp về tiêu chuẩn thời gian.
Việc đánh giá chất lượng phân lớp của tập rút gọn dựa vào số lượng thuộc tính của tập rút gọn và chất lượng phân lớp của từng thuộc tính. Về mặt định tính, tập rút gọn có số thuộc tính càng ít thì chất lượng phân lớp càng cao. Tuy nhiên, điều này chưa hẳn đã chính xác vì chất lượng phân lớp của từng thuộc tính khác nhau. Tóm lại, ta cần phải sử dụng độ đo mang tính định lượng để đánh giá chất lượng phân lớp của tập rút gọn. Trong lý thuyết tập thô, các nhà nghiên cứu sử dụng ba độ đo để đánh giá tính đúng đắn và tính hiệu quả của một phương pháp rút gọn thuộc tính: độ chắc chắn (certainty measure), độ nhất quán (consistency measure) và độ hỗ trợ (support measure). Cụ thể là: tập rút gọn của phương pháp rút gọn thuộc tính phải bảo toàn độ chắc chắn, độ nhất quán của tập luật quyết định. Độ hỗ trợ sử dụng để đánh giá chất lượng phân lớp của tập rút gọn. Độ hỗ trợ của tập luật quyết định dựa trên tập rút gọn càng cao thì chất lượng phân lớp của tập rút gọn đó càng cao.
Với bảng quyết định nhất quán, tập rút gọn của tất cả các phương pháp là như nhau. Do đó, để đánh giá các phương pháp rút gọn thuộc tính, ta chỉ cần sử dụng tiêu chuẩn độ phức tạp của thuật toán heuristic tìm tập rút gọn, độ phức tạp của thuật toán càng nhỏ thì phương pháp đó càng hiệu quả. Ngoài ra, có thể sử dụng thêm tiêu chuẩn là dung lượng bộ nhớ mà thuật toán sử dụng.
Với bảng quyết định không nhất quán, việc đánh giá các phương pháp rút gọn thuộc tính dựa trên hai tiêu chuẩn: số lượng thuộc tính tập rút gọn của phương pháp và độ phức tạp thuật toán tìm tập rút gọn.
Trong [3] Nguyễn Long Giang và các cộng sự đã phân tích và chỉ ra rằng: Theo tiêu chuẩn đánh giá số lượng thuộc tính của tập rút gọn, nhóm phương
25
pháp Entropy Shannon hiệu quả hơn cả. Do đó tác giả luận văn xin chọn nhóm phương pháp entropy Shannon để tìm hiểu và nghiên cứu.
2.2. Phƣơng pháp rút gọn thuộc tính dựa trên entropy Shannon
Giống như các phương pháp rút gọn thuộc tính khác, để xây dựng phương pháp heuristic rút gọn thuộc tính sử dụng entropy Shannon, cần tiến hành nghiên cứu các bước:
- Định nghĩa tập rút gọn dựa trên entropy Shannon
- Định nghĩa độ quan trọng của thuộc tính sử dụng entropy Shannon. Độ quan trọng của thuộc tính đặc trưng cho chất lượng phân lớp của thuộc tính và là tiêu chuẩn lựa chọn thuộc tính trong các bước của thuật toán heuristic tìm một tập rút gọn có chất lượng phân lớp tốt nhất.
Mô tả thuật toán heuristic tìm một tập rút gọn có chất lượng phân
lớp tốt nhất.
Đánh giá tập rút gọn tìm được và độ phức tạp của thuật toán.
2.2.1. Entropy Shannon trên bảng quyết định
Định nghĩa 2.1. ([25]) Cho bảng quyết định và tập thuộc
. Giả sử . Entropy Shannon của P được định nghĩa tính
bởi
(2.1)
với |X| biểu diễn lực lượng của tập X. Nếu thì đạt giá trị nhỏ nhất
là 0, còn nếu với thì đạt giá trị lớn nhất là
. Do đó .
Định nghĩa 2.2. ([25]) Cho bảng quyết định . Giả sử
. Entropy Shannon có điều kiện của
D khi đã biết được định nghĩa bởi
(2.2)
với quy ước 0. .
26
Nếu bảng quyết định DS nhất quán thì dễ dàng suy ra , trái lại
.
Mệnh đề 2.1. ([21]) Cho bảng quyết định . Nếu
. Dấu đẳng thức xảy ra nếu thì
, mà , thì với
mọi .
Mệnh đề 2.1 nói lên tính phản đơn điệu của entropy Shannon có điều kiện, nghĩa là tập thuộc tính điều kiện Q càng nhỏ (phân hoạch sinh bởi Q càng
thô) thì càng lớn và ngược lại.
2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon
Định nghĩa 2.3. ([21]) Cho bảng quyết định , thuộc tính
được gọi là không cần thiết (dư thừa) trong DS dựa trên entropy Shannon có điều
kiện nếu ; Ngược lại, a gọi là cần thiết. Tập tất cả các thuộc
tính cần thiết trong được gọi là tập lõi dựa trên entropy Shannon có điều kiện
và ký hiệu là .
Ví dụ 2.1. Xét bảng quyết định với ,
và cho ở Bảng 2.1.
Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1
U d
0 1 1 0
0 1 1 1
0 1 0 0
0 1 0 1
1 0 0 1
1 0 1 1
27
Rõ ràng DS không nhất quán vì nhưng . Ta có
nên là dư thừa trong DS dựa trên entropy
Shannon có điều kiện
2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon
Định nghĩa 2.4. ([21]) Cho bảng quyết định và tập thuộc
tính . Nếu
1)
2)
thì R là một tập rút gọn của C dựa trên entropy Shannon có điều kiện, gọi tắt là tập rút gọn Entropy Shannon.
Ký hiệu là họ tất cả các tập rút gọn Entropy Shannon. Theo [21],
.
2.2.4. Độ quan trọng của thuộc tính dựa trên entropy Shannon
Định nghĩa 2.5. ([21]) Cho bảng quyết định và tập thuộc
. Độ quan trọng của thuộc tính đối với R được định tính ,
nghĩa bởi
Theo Mệnh đề 2.1 ta có: nên . Do đó, ,
càng lớn thì lượng thay đổi entropy càng lớn, hay thuộc tính a càng
28
quan trọng và ngược lại. Độ quan trọng của thuộc tính a đặc trưng cho khả năng phân lớp của thuộc tính a vào các lớp quyết định, hay chất lượng phân lớp của thuộc tính a, và được sử dụng làm tiêu chuẩn lựa chọn thuộc tính trong thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ.
2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon
Để mô tả thuật toán heuristic tìm tập rút gọn sử dụng entropy Shannon, ta có thể sử dụng hai hướng tiếp cận: hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Phần này mô tả một thuật toán heuristic tìm tập rút gọn có tính toán lõi theo hướng tiếp cận bottom-up. Ý tưởng của thuật toán là xuất phát từ tập lõi HCORE(C), lần lượt bổ sung vào tập lõi các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn.
Thuật toán tìm tập lõi
Thuật toán 2.1. Thuật toán tìm tập lõi sử dụng entropy Shannon
Input: Bảng quyết định .
Output: Tập lõi .
Method:
; 1.
2. Tính ;
3. For each
Begin 4.
5. Tính ;
6. If then
7. End;
8. Return ;
29
Phân tích độ phức tạp Thuật toán 2.1
Sử dụng thuật toán trong [14] để tính , độ phức tạp là . Do
đó, độ phức tạp để tính là . Vì vậy, độ phức tạp của vòng lặp
For từ dòng lệnh thứ 3 đến dòng lệnh thứ 7 là và độ phức tạp của
Thuật toán 2.1 là .
Ví dụ 2.2. Xét bảng quyết định cho ở Bảng 2.2
Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.2
U d
0 1 1 0
0 1 1 1
0 1 0 0
0 1 0 1
0 1 0 1
1 0 0 1
1 0 1 1 u7
Ta có , , .
, .
Thực hiện các bước Thuật toán 2.1 tìm tập lõi:
; 1.
2.
3. Xét lần lượt các thuộc tính . Ta có:
- do đó
30
hay a3 không phải là
thuộc tính dư thừa
- do đó
hay a2 là thuộc tính dư thừa
- do đó
hay a1 là thuộc tính dư thừa.
Vì vậy .
Thuật toán tính phân hoạch
Xét bảng quyết định . Với giả sử
. Theo Định nghĩa 2.2, entropy
Shannon có điều kiện của D khi đã biết là
Để tính phân hoạch khi biết phân hoạch ta sử dụng thuật
toán sau:
Thuật toán 2.2. Tính phân hoạch khi biết
Input: Phân hoạch .
Output: Phân hoạch
Method:
1. ;
2. For each do
3. Begin
4. Tính phân hoạch ;
5. ;
6. End;
31
7. Return (TMP);
Sử dụng thuật toán trong [14] để tính phân hoạch với độ phức tạp
thì độ phức tạp của Thuật toán 2.2 là .
Ví dụ 2.3. Xét bảng quyết định cho ở Ví dụ 2.2. Giả sử
và phân hoạch , áp dụng Thuật
toán 2.2 tính phân hoạch (với ) ta có:
1. ;
2. Xét , tính và .Xét
, tính và .
Vậy .
Thuật toán heuristic tìm tập rút gọn tốt nhất
Luận văn đã chọn thuật toán CEBARKCC [23] (Conditional Entropy Based Algorithm for Reduction of Knowledge with Computing Core) là thuật toán heuristic tìm tập rút gọn tốt nhất trong bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi để tìm hiểu, nghiên cứu.
Ý tưởng của thuật toán là xuất phát từ tập lõi , lần lượt bổ
sung vào tập R các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn.
Thuật toán 2.3. CEBARKCC:
Input: Bảng quyết định DS = (U, CD, V, f),
Output: Một tập rút gọn R.
1. Tìm tập lõi theo Thuật toán 2.1;
// Tìm tậprút gọn Entropy Shannon
2. ;
// Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất
3. While do
32
Begin 4.
For each 5.
6. Begin
7. Tính
; 8. Tính
9. End
Chọn sao cho ; 10.
11. ;
12. Tính
13. End;
//Loại bỏ các thuộc tính dư thừa trong R nếu có.
14. ;
15. For each
16. Begin
17. Tính
18. If then ;
19. End
20. Return ;
Chứng minh tính đúng đắn của Thuật toán 2.3
Với bước thêm dần vào R các thuộc tính có độ quan trọng lớn nhất, tập thuộc tính R thu được từ câu lệnh từ 3 đến 13 thỏa mãn điều kiện bảo toàn
entropy Shannon .
Với bước loại bỏ các thuộc tính dư thừa, câu lệnh từ 14 đến 19 đảm bảo
tập R là tối thiểu, nghĩa là .
Theo Định nghĩa 2.2, R là tập rút gọn dựa trên entropy Shannon.
33
Độ phức tạp thời gian của Thuật toán 2.3
Xét vòng lặp While từ dòng lệnh số 3 đến dòng lệnh số 13, theo công thức
(2.2)
để tính , ta chỉ cần tính phân hoạch và phân hoạch đã
được tính ở bước trước. Từ Thuật toán 2.1, độ phức tạp thời gian để tính
khi biết là nên độ phức tạp thời gian để tính tất cả các
là
Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất là
. Vòng lặp For tại dòng lệnh 17 thực hiện lần,
mỗi lần ta phải tính với độ phức tạp thời gian . Do đó, độ phức tạp
thời gian của dòng lệnh 17 là . Vì vậy, độ phức tạp thời gian của thuật
toán là .
Ví dụ 2.4. Xét bảng quyết định cho ở Ví dụ 2.2. Từ Ví dụ
2.2. ta có:
,
Do đó thực hiện vòng lặp While.
Xét thuộc tính . Theo tính toán ở Ví dụ 2.2:
, do đó:
34
Xét thuộc tính . Tính toán tương tự ta được:
.
Do và có độ quan trọng như nhau nên chọn bất kỳ hoặc , giả sử
chọn , khi đó và và theo tính toán ở Ví dụ 2.2:
.Thực hiện vòng lặp For. Xét và
Theo tính toán ở trên, . Do đó thuật toán kết thúc và
là một tập rút gọn tốt nhất của C dựa trên entropy Shannon.
2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định
Rút trích và đánh giá hiệu năng tập luật quyết định từ bảng quyết định là bước tiếp theo của rút gọn thuộc tính trong quá trình khai phá dữ liệu sử dụng lý thuyết tập thô. Yuhua Qian và các cộng sự [19] đã đề xuất ba độ đo mới nhằm khắc phục các nhược điểm của các độ đo cổ điển, đó là độ chắc chắn, độ nhất quán và độ hỗ trợ để đánh giá hiệu năng tập luật quyết định của bảng quyết định (gọi tắt là các độ đo đánh giá hiệu năng tập luật quyết định).
trên các Trong phần này, chỉ xem xét bảng quyết định
. phân hoạch và , do đó DS được biểu diễn vắn tắt là
2.3.1. Luật quyết định
và Cho bảng quyết định , giả sử
và là các phân hoạch được sinh bởi C, D. Với ,
, ký hiệu và lần lượt là các mô tả của các lớp tương đương
và trong bảng quyết định DS.
Một luật quyết định đơn có dạng .
Các độ đo cổ điển đánh giá luật quyết định đơn được đề xuất trong [19].
(1) Độ chắc chắn: ,
(2) Độ hỗ trợ: .
35
(3) Độ nhất quán:
Các độ đo này chỉ sử dụng để đánh giá cho các luật quyết định đơn, không
phù hợp cho việc đánh giá hiệu năng tập luật quyết định.
2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn
Để đánh giá hiệu năng tập luật quyết định, khắc phục nhược điểm các độ đo cổ điển, Yuhua Qian và cộng sự [19] đã đề xuất ba độ đo: độ chắc chắn (certainty measure), độ nhất quán (consistency measure) và độ hỗ trợ (support measure).
Cho bảng quyết định và
với .
Độ chắc chắn của DS được định nghĩa
.
Độ nhất quán của DS được định nghĩa
với
là số luật quyết định sinh bởi lớp tương đương
.
Độ hỗ trợ của DS được định nghĩa
Ví dụ 2.4: Xét bảng quyết định mô tả về bệnh cúm cho ở Bảng
2.4 với , với (Mệt mỏi), (Đau đầu),
(Đau cơ), (Thân nhiệt).
36
Bảng 2.3. Bảng quyết định về bệnh cúm
U Mệt mỏi Đau đầu Đau cơ Thân nhiệt Cảm cúm
Có Có Bình thường Không Có U1
Có Có Cao Có Có U2
Có Có Rất cao Có Có U3
Có Không Có Bình thường Không U4
Có Không Không Cao Không U5
Có Không Có Rất cao Có U6
Ta có các phân hoạch:
Các luật quyết định trên tập thuộc tính C là:
Z11: (a1, Có) (a2, Có) (a3, Có) (a4, Bình thường) → (D, Không)
Z41: (a1, Có) (a2, Không) (a3, Có) (a4, Bình thường) → (D, Không)
Z51: (a1, Có) (a2, Không) (a3, Không) (a4, Cao) → (D, Không)
Z22: (a1, Có) (a2, Có) (a3, Có) (a4, Cao) → (D, Có)
Z32: (a1, Có) (a2, Có) (a3, Có) (a4, Rất cao) → (D, Có)
Z62: (a1, Có) (a2, Không) (a3, Có) (a4, Rất cao) → (D, Có)
Các độ đo của các luật quyết định đơn là:
,
37
Độ chắc chắn của bảng quyết định DS là:
Độ nhất quán của bảng quyết định DS là:
Độ hỗ trợ của bảng quyết định DS là:
Bảng quyết định DS đã cho có 2 tập rút gọn là
Xét tập rút gọn ta có . Không mất
tính tổng quát, ta có bảng quyết định tương ứng với tập rút gọn R là
Từ tập rút gọn này ta có các luật quyết định là:
(a3, Có) (a4, Bình thường) → (D, Không)
(a3, Không) (a4, Cao) → (D, Không)
(a3, Có) (a4, Cao) → (D, Có)
(a3, Có) (a4, Rất cao) → (D, Có)
Các độ đo của các luật quyết định đơn là:
,
Độ chắc chắn của bảng quyết định DS’ là:
38
Độ nhất quán
của bảng quyết định DS’ là:
Độ hỗ trợ của bảng quyết định DS’ là:
Nhận xét:
,
,
- Trên tập rút gọn R thì số luật quyết định được giảm bớt từ 6 luật xuống còn 4 luật, mỗi luật từ 4 thuộc tính vế trái xuống còn 2 thuộc tính.
- Tập rút gọn R làm tăng độ hỗ trợ của tập luật.
Như vậy, có thể kết luận rẳng tập rút gọn Entropy Shannon bảo toàn độ
chắc chắn, bảo toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định.
2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định
Cho bảng quyết định , giả sử và
. Với , và . Thuật toán RuleExtract hiển
thị các luật quyết định dạng với độ chắc chắn
và đỗ hỗ trợ tương ứng.
Thuật toán sau đây thực hiện sinh các luật quyết định và hiển thị độ đo của
các luật dựa vào định nghĩa luật quyết định trong lý thuyết tập thô.
39
Thuật toán RuleExtract
Input: Bảng quyết định DS = (U, CD, V, f).
Output: Hiển thị danh sách các luật với độ chắc chắn và độ hỗ trợ .
1. Tính phân hoạch ;
2. For each
3. Begin
Tính ; 4.
For each 5.
Begin 6.
7. Sinh luật
8. Tính ;
9. Tính ;
10. Hiển thị luật , độ chắc chắn , độ hỗ trợ ;
11. End;
12. End;
13. Return.
40
Chƣơng 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ
3.1. Bài toán
Cho trước các bảng quyết định với kích thước trung bình và kích thước lớn,
nhiệm vụ của phần thử nghiệm và đánh giá đặt ra là:
1) Cài đặt và thử nghiệm, đánh giá thuật toán rút gọn thuộc tính sử dụng
entropy Shannon
2) Cài đặt và thử nghiệm thuật toán sinh luật quyết định RuleExtract trên
tập rút gọn tìm được của thuật toán sử dụng entropy Shannon.
Nhiệm vụ này bao gồm các bước sau:
Bước 1: Cài đặt thuật toán rút gọn thuộc tính sử dụng entropy Shannon (Thuật toán CEBARKCC) bằng ngôn ngữ C# trên môi trường hệ điều hành Windows 7 Home Premium.
Bước 2: Chạy thử nghiệm thuật toán CEBARKCC trên bộ số liệu lấy từ
kho dữ liệu UCI.
Bước 3: Cài đặt và thực hiện thuật toán sinh luật RuleExtract trên tập rút gọn tìm được của Thuật toán CEBARKCC bằng ngôn ngữ C# trên môi trường hệ điều hành Windows 7 Home Premium.
3.2. Một số kết quả thử nghiệm
3.2.1. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon
Sau khi cài đặt, tôi tiến hành chạy thử nghiệm thuật toán CEBARKCC với 8 bộ số liệu vừa và nhỏ lấy từ kho dữ liệu UCI ([32]). Môi trường thử nghiệm là máy tính Laptop với cấu hình Intel core2 duo 2.1 GHz CPU, 3GB bộ nhớ RAM, sử dụng là số đối hệ điều hành Windows 7 Home Premium. Với mỗi bộ số liệu, giả sử
tượng, là số thuộc tính điều kiện, là số thuộc tính của tập rút gọn thu
được; t là thời gian thực hiện thuật toán (đơn vị là giây s). Các thuộc tính điều
kiện được đánh số thứ tự từ 1 đến . Bảng 3.1 mô tả kết quả thực hiện của thuật
toán.
41
Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC
STT Bộ số liệu Tập rút gọn t
4 32 56 0.78 {3, 4, 9, 43} 1 Lung-cancer.data
1 101 17 0.505 {1} 2 Zoo.data
3 3 345 6 0.677 {1, 2, 5} Liver-disorders (bupa.data)
4 4 307 35 3.115 {1, 2, 8, 11} Soybean – Large.data
1 194 29 0.682 {1} 5 Flag.data
7 690 15 29.703 6 Credit Approval {1, 2, 3, 4, 5, 6, 8}
7 798 38 49.336 7 Anneal.data {3, 5, 8, 12, 33, 34, 35}
3 4177 8 256.12 {2, 5, 6} 8 Abalone.data
Kết quả thử nghiệm trên 8 bộ số liệu vừa và nhỏ cho thấy:
Trên 8 bộ số liệu được chọn, bộ số liệu nào có kích thước càng nhỏ thì thời gian thực hiện càng nhanh, ngược lại, bộ số liệu nào có kích thước càng lớn thì thời gian thực hiện càng chậm.
Tiếp theo, tác giả tiến hành thử nghiệm Thuật toán CEBARKCC trên 5 bộ số liệu kích thước lớn. 5 bộ số liệu được chọn để thử nghiệm có miền giá trị của các thuộc tính là các giá trị nguyên dương, hoặc các giá trị rời rạc (đã qua bước tiền xử lý dữ liệu) được lấy từ kho dữ liệu UCI ([32]). Kết quả thử nghiệm được mô tả ở bảng 3.2 sau:
42
Bảng 3.2. Kết quả thực hiện Thuật toán CEBARKCC
STT Bộ số liệu t
40 21 11415 1 Census-Income.data 299285
48842 14 9 1270 2 Adult.data
1950 100000 92 2867 3 Dorothea.data
4 1000000 11 8 8977 Poker-hand- testing.data
581012 54 17 14289 5 CovType.data
Với các bộ số liệu có kích thước càng lớn, rõ ràng thời gian thực hiện Thuật toán CEBARKCC càng chậm, do đó Thuật toán CEBARKCC chưa thật sự hiệu quả với các bộ số liệu có kích thước lớn.
3.2.2. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn
Để tiến hành thử nghiệm, Thuật toán RuleExtract được cài đặt bằng ngôn ngữ C#. Môi trường thử nghiệm là máy tính Laptop với cấu hình Intel core2 duo 2.1 GHz CPU, 3GB bộ nhớ RAM, sử dụng hệ điều hành Windows 7 Home Premium. Bộ số liệu thử nghiệm là Soybean - small.data lấy từ kho dữ liệu UCI ([32]). Soybean - small.data là bộ số liệu đã rời rạc hóa với miền giá trị các thuộc tính là các số nguyên dương.
1) Thử nghiệm Thuật toán CEBARKCC tìm một tập rút gọn tốt nhất. Với
bộ số liệu thử nghiệm, giả sử là số đối tượng, là số thuộc tính điều kiện,
là độ chắc chắn của bảng quyết định với tập thuộc tính ban đầu,
là độ chắc chắn của bảng quyết định với tập thuộc tính rút gọn, các thuộc tính điều kiện được đặt tên theo thứ tự từ c1, c2,…,cn. Kết quả thử nghiệm được mô tả trong Bảng 3.3
43
Bảng 3.3. Tập rút gọn tốt nhất của bộ số liệu Soybean - small.data
STT Bộ số liệu
Tập thuộc tính rút gọn
Tập thuộc tính ban đầu
1 47 35 {c1,…,c35} 1 {c4, c22} 1 -
Soybean small.data
2) Thử nghiệm Thuật toán RuleExtract sinh luật quyết định (luật phân lớp) sử dụng mô hình tập thô truyền thống với bộ số liệu Soybean - small.data. Trên bảng quyết định ban đầu với 35 thuộc tính điều kiện {c1,…,c35}, kết quả thử nghiệm thu được 47 luật phân lớp, độ dài mỗi luật là 35(được tính bằng tổng số thuộc tính điều kiện tham gia vào vế trái của luật). Trên bảng quyết định rút gọn với 2 thuộc tính điều kiện {c4, c22}, kết quả thử nghiệm được mô tả trong Bảng 3.4, trong
đó: tổng số luật phân lớp là 7, độ dài mỗi luật là 2, là độ chắc chắn và là độ hỗ
trợ của mỗi luật.
Bảng 3.4. Các luật phân lớp trên bảng quyết định rút gọn
STT Các luật trên bảng quyết định rút gọn
1 c4(1) and c22(1) ==> D1 1 0.12766
2 c4(1) and c22(0) ==> D1 1 0.08511
3 c4(2) and c22(3) ==> D2 1 0.12766
4 c4(1) and c22(3) ==> D2 1 0.08511
5 c4(0) and c22(1) ==> D3 1 0.21277
6 c4(1) and c22(2) ==> D4 1 0.21277
7 c4(0) and c22(2) ==> D4 1 0.14894
Chú thích: Trên bảng Bảng 3.4, c4(1) nghĩa là thuộc tính c4 nhận giá trị 1 (c4 = 1). D1, D2, D3, D4 là các giá trị thuộc tính quyết định (tổng số 4 lớp quyết định).
44
Kết quả thử nghiệm cho thấy, trên tập rút gọn tốt nhất thu được bởi Thuật toán CEBARKCC, số lượng các luật từ 47 giảm xuống còn 7, độ dài các luật từ 35 giảm xuống còn 2. Độ chắc chắn của tập luật không thay đổi (bằng 1). Kết quả này khẳng định ý nghĩa của việc rút gọn thuộc tính trong bước tiền xử lý dữ liệu
3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế
Trong thực tế, việc sử dụng các phương pháp rút gọn thuộc tính trong các bảng quyết định có ý nghĩa rất quan trọng. Nó loại bỏ được các thuộc tính dư thừa (những thuộc tính không có ý nghĩa trong việc sinh ra các luật quyết định). Trong phần này, xin được giới thiệu một vài bài toán ứng dụng các phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ, đồng thời sinh các luật quyết định.
Trước hết xin nêu ra một số bài toán ứng dụng khi sử dụng các thuật toán
rút gọn đã trình bày trên những bộ dữ liệu chuẩn thuộc bộ dữ liệu UCI..
Thông thường trong một bảng quyết định thì số thuộc tính trong bảng có thể vẫn còn là thuộc tính dư thừa, việc loại bỏ các thuộc tính dư thừa đó ra khỏi bảng quyết định là rất cần thiết, nó giúp việc sinh luật quyết định trở nên hiệu quả và tiết kiệm thời gian.
Trong bộ dữ liệu Lung-Cancer của bộ dữ liệu UCI thì số thuộc tính ban đầu khi chưa thực hiện thuật toán rút gọn là 56. Sau khi thực hiện thuật toán rút gọn đã trình bày thì số thuộc tính quyết định chỉ còn lại 4. Như vậy, thay bằng việc để dự đoán bệnh nhân nào có khả năng mắc ung thư phổi cao, Bác sĩ sẽ phải xét tất cả 56 thuộc tính mà trong đó có tới 52 thuộc tính dư thừa, trong khi chỉ cần dựa vào 4 thuộc tính trong bảng quyết định, Bác sĩ vẫn có thể có kết luận như trên.
Một ví dụ khác, khi áp dụng thuật toán tìm tập rút gọn với bộ dữ liệu viêm gan Hepatitis.data trong kho dữ liệu UCI để sinh luật quyết định phục vụ cho các bác sĩ chuyên ngành chuẩn đoán bệnh viêm gan cho bệnh nhân. Ban đầu, bộ dữ liệu Hepatitis.data gồm 19 thuộc tính điều kiện, tương ứng với 19 triệu chứng thu thập được từ bệnh nhân có biểu hiện viêm gan, bao gồm: Tuổi,
Giới tính, STEROID, Dùng thuốc kháng Virus, Mệt mỏi, Khó ở, Chán ăn, Gan sƣng to, Sơ gan, Viêm lá lách, Huyết thanh, Tĩnh mạch, Sắc tố da,
45
ALK PHOSPHATE, SGOT, ALBUMIN, PROTIME, Tiền sử mắc bệnh hay chƣa. Sau khi thực hiện thuật toán rút gọn thuộc tính thu được một tập rút gọn gồm 03 thuộc tính là: Giới tính, Sắc tố da, ALK PHOSPHATE. Điều đó có nghĩa là 16 thuộc tính còn lại là dư thừa. Thay vì sinh luật từ tập 19 thuộc tính ban đầu, chúng tôi chỉ thực hiện việc sinh luật trên tập rút gọn gồm 03 thuộc tính để chuẩn đoán bệnh viêm gan…
3.4. Một số giao diện chƣơng trình
3.4.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC
Kết quả thực hiện thuật toán CEBARKCC tìm một tập rút gọn tốt nhất sử
dụng entropy Shannon với bộ dữ liệu hepatitis.data như sau:
Hình 3.1. Giao diện thực hiện thuật toán rút gọn thuộc tính
3.4.2. Thực hiện thuật toán sinh luật quyết định
Kết quả thực hiện thuật toán sinh luật quyết định RuleExtract dựa trên tập rút gọn thu được từ thuật toán rút gọn thuộc tính với bộ dữ liệu Soybean - small.data như sau:
46
Bước 1: Tìm tập rút gọn của bảng quyết định với bộ số hình 3.2
Hình 3.2. Giao diện tìm tập rút gọn với bộ số liệu Soybean – small.data
Bước 2: Click chuột vào nút “Xem tập rút gọn” thu được kết quả như hình 3.3
Hình 3.3. Tập rút gọn thu được với bộ số liệu Soybean – small.data
Bước 3: Click chuột vào nút “Sinh luật quyết định”, thu được tập luật quyết định (luật phân lớp)
47
Hình 3.4. Tập luật quyết định thu được trên bộ số liệu Soybean - small
48
KẾT LUẬN
1) Những kết quả chính của luận văn
Luận văn tập trung vào hướng nghiên cứu lý thuyết với nội dung nghiên cứu bao gồm hai phần: phần nghiên cứu tổng hợp các kết quả đã công bố và phần chương trình mô phỏng thuật toán. Luận văn đạt được hai kết quả chính sau:
(1) Trên cơ sở tổng kết các kết quả đã công bố mới nhất về hướng nghiên cứu rút gọn thuộc tính trong bảng quyết định, bao gồm nhóm các phương pháp rút gọn thuộc tính, luận văn nghiên cứu phương pháp rút gọn thuộc tính sử dụng entropy Shannon
(2) Cài đặt và thử nghiệm phương pháp rút gọn thuộc tính sử dụng entropy Shannon và phương pháp sinh luật quyết định trên các bộ số liệu thử nghiệm từ kho dữ liệu UCI.
Phương pháp sử dụng entropy Shannon không hiệu quả hơn phương pháp sử dụng khoảng cách entropy Liang ([13]), tuy nhiên ý nghĩa của phần này là tài liệu học tập cho những người mới tiếp cận với khai phá dữ liệu sử dụng lý thuyết tập thô, đặc biệt là phương pháp rút gọn thuộc tính trên bảng quyết định sử dụng entropy Shannon.
2) Hƣớng phát triển tiếp theo
Tác giả luận văn sẽ tiếp tục nghiên cứu các phương pháp rút gọn thuộc tính
trên bảng quyết định không đầy đủ sử dụng các độ đo khoảng cách.
49
TÀI LIỆU THAM KHẢO
Tài liệu tiếng Việt
[1] Hoàng Thị Lan Giao (2007), “Khía cạnh đại số và lôgic phát hiện luật theo
tiếp cận tập thô”, Luận án Tiến sĩ Toán học, Viện Công Nghệ Thông Tin.
[2] Nguyễn Đức Thuần (2010), “Phủ tập thô và độ đo đánh giá hiệu năng tập luật
quyết định”, Luận án Tiến sĩ Toán học, Viện Công Nghệ Thông Tin.
[3] Nguyễn Long Giang (2012), “Nghiên cứu một số phương pháp khai phá dữ
liệu theo tiếp cận lý thuyết tập thô”, Luận án Tiến sĩ Toán học, Viện Công
Nghệ Thông Tin.
[4] Nguyễn Long Giang, Vũ Đức Thi (2011), “Một phương pháp rút gọn thuộc
tính trong bảng quyết định dựa trên Entropy cải tiến”, Tạp chí Tin học và Điều khiển học, T.27, S.2, tr. 166-175.
Tài liệu tiếng Anh
[5] Andrzej Skowron and Rauszer C (1992), “The Discernibility Matrices and
Functions
in Information Systems”, Interlligent Decision Support,
Handbook of Applications and Advances of the Rough Sets Theory, Kluwer, Dordrecht, pp. 331-362.
[6] Ge H., Li L.S and Yang C.J. (2009), “Improvement to Quick Attribution
Reduction Algorithm”, Journal of Computers, Vol.30, No.2, pp. 308-312.
[7] Hu X.H. and Cercone N. (1995), “Learning in relational databases: a rough set
approach”, International Journal of computational intelligence, pp. 323-338.
[8] Hu X.H., Lin T.Y. and Han J.C. (2004), “A new rough sets model based on
database systems”, Fundamenta Informaticae, 59(1), pp. 135-152 .
[9] Kryszkiewicz M. (1998), “Rough set approach to incomplete information
systems”, Information Science, Vol. 112, pp. 39-49.
[10] Li J.H. and Shi K.Q. (2006), “A algorithm for attribute reduction based on
knowledge granularity”, Computer Applications, Vol. 26, No. 6, pp. 76-77.
[11] Li X.H. and Shi K.Q. (2006), “A knowledge granulation-based algorithm for
50
attribute reduction under incomplete information systems”, Computer
Science, Vol. 33, pp. 169-171.
[12] Liu Y., Xiong R. and Chu J. (2009), “Quick Attribute Reduction Algorithm
with Hash”, Chinese Journal of Computers, Vol.32, No.8, pp. 1493-1499.
[13]
Liang J.Y., Shi Z.Z., Li D.Y. and Wierman M.J. (2006), “The information entropy, rough entropy and knowledge granulation in incomplete information
system”, International Journal of General Systems 35 (6), pp. 641-654.
[14] Lv Y.J. and Li J.H. (2007), “A Quick Algorithmfor Reduction of Attribute in
Information Systems”, The First International Symposium on Data, Privacy,
and E-Commerce (ISDPE 2007), pp. 98-100.
[15] Miao D.Q. and Hu G.R. (1999), “A heuristic algorithm for knowledge
reduction”, Computer Research and Development, Vol. 36, No. 6, pp. 681-684.
[16] Nguyen S. Hoa, Nguyen H. Son (1996), "Some Efficient Alogrithms for
Rough Set Methods", Proceedings of the sixth International Conference on
Information Processing Management of Uncertainty in Knowledge Based
Systems, pp. 1451 - 1456.
[17] Pawlak Z. (1991), Rough sets: Theoretical Aspects of Reasoning About
Data, Kluwer Aca-demic Publishers.
[18] Pawlak Z. (1998), “Rough set theory and its applications in data analysis”,
Cybernetics and systems 29, pp. 661-688.
[19] Qian Y.H., Liang J.Y., Li D.Y., Zhang H.Y. and Dang C.Y. (2008),
“Measures of Evaluating The Decision Performace of a Decision Table in
Rough Set Theory”, Information Sciences, Vol.178, pp.181-202.
[20] Wang C.R. and OU F.F. (2008), “An Attribute Reduction Algorithm in Rough Set Theory Based on Information Entropy”, 2008 International Symposium on Computational Intelligence and Design, IEEE ISCID, pp. 3-6.
[21] Wang G.Y. (2001), “Algebra view and information view of rough sets theory”, In: Dasarathy BV,editor. Data mining and knowledge discovery: Theory, tools, and technology III, Proceedings of SPIE, pp. 200-207.
[22] Wang G.Y. (2003), “Rough reduction in algebra view and information view”,
51
