ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ HỒNG HẠNH
NGHIÊN CỨU CÁC TẬP RÚT GỌN VÀ LUẬT TRONG BẢNG
QUYẾT ĐỊNH THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
Hà Nội - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ HỒNG HẠNH
NGHIÊN CỨU CÁC TẬP RÚT GỌN VÀ LUẬT TRONG BẢNG
QUYẾT ĐỊNH THEO TIẾP CẬN 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ố: 60.48.05
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
Người hướng dẫn: TS. Nguyễn Long Giang
Hà Nội - 2015
1
MỤC LỤC
MỤC LỤC ............................................................................................................................................................. 1
Danh mục các thuật ngữ ...................................................................................................................................... 3
Danh sách bảng ..................................................................................................................................................... 4
MỞ ĐẦU ............................................................................................................................................................... 5
Chương 1. TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ ........................................................................ 8
1.1. Hệ thông tin ..................................................................................................................... 8
1.2. Mô hình tập thô ............................................................................................................... 9
1.3. Bảng quyết định ............................................................................................................ 11
1.4. Tập rút gọn và tập lõi .................................................................................................... 12
1.5. Ma trận phân biệt và hàm phân biệt ............................................................................ 14
Chương 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG BẢNG
QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ .................................................................... 15
2.1.1. Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính ............................. 15
2.1.2. Luật quyết định và các độ đo đánh giá hiệu năng ............................................ 20
2.1.3. Lựa chọn, so sánh, đánh giá các phương pháp rút gọn thuộc tính ................... 23
2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định ....................................... 15
2.2. Xây dựng phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng khoảng
2.2.1. Độ đo khoảng cách .......................................................................................... 26
2.2.2. Xây dựng khoảng cách giữa hai tri thức và các tính chất ................................ 27
2.2.3. Phương pháp rút gọn thuộc tính sử dụng khoảng cách .................................... 31
2.2.4. Phân nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách ................. 36
cách 25
Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .................................................. 38
3.1. Bài toán .......................................................................................................................... 38
3.2.1. Thuật toán tìm tập rút gọn sử dụng entropy Liang .......................................... 39
3.2.2. Lựa chọn công cụ và cài đặt ............................................................................ 40
3.2. Phân tích, lựa chọn công cụ ......................................................................................... 38
3.3.1. Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng khoảng cách ............. 40
3.3. Một số kết quả thử nghiệm ........................................................................................... 40
2
3.3.2. Kết quả thử nghiệm về trích lọc luật theo tiếp cận tập thô .............................. 42
KẾT LUẬN ......................................................................................................................................................... 46
Tài liệu tham khảo .............................................................................................................................................. 47
Phụ lục ................................................................................................................................................................... 49
3
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
Bảng quyết định 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
Luật quyết định Decision Rule
Khoảng cách Distance
4
Danh sách bảng
Bảng 1.1. Bảng thông tin về bệnh cúm ............................................................................... 10
Bảng 1.2. Bảng quyết định về bệnh cúm ............................................................................. 13
Bảng 2.1. Các phương pháp rút gọn thuộc tính trong tài liệu [1] ...................................... 16
Bảng 2.2. Bảng quyết định về các xe hơi ............................................................................ 20
Bảng 2.1. Bảng quyết định minh họa thuật toán tìm tập rút gọn ........................................... 34
Bảng 3.1. Kết quả thực hiện Thuật toán ELBAR và Thuật toán DBAR .............................. 40
Bảng 3.2. Tập rút gọn của Thuật toán ELBAR và Thuật toán DBAR ................................. 41
Bảng 3.3. Kết quả thực hiện Thuật toán ELBAK và Thuật toán DBAK .............................. 42
trên các bộ số liệu lớn .......................................................................................................... 42
Bảng 3.7. Tập rút gọn tốt nhất của bộ số liệu Soybean-small ........................................... 44
Bảng 3.8. Các luật phân lớp trên bảng quyết định rút gọn sử dụng tập thô ....................... 44
5
MỞ ĐẦU
Lý thuyết tập thô - do Zdzislaw Pawlak [7] đề xuất vào những năm đầu thập
niên tám mươi của thế kỷ hai mươi - được xem là công cụ hữu hiệu để giải quyết
các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, không chắc chắn.
Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các bước của quá
trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý số liệu, khai phá dữ
liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và trích lọc luật quyết định
(luật phân lớp) là hai ứng dụng chính của lý thuyết tập thô trong khai phá dữ liệu.
Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn trích lọc luật thuộc giai
đoạn khai phá dữ liệu. 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 nhằm tìm tập con nhỏ nhất của tập thuộc tính điều kiện (tập rút gọn) mà bảo
toàn thông tin phân lớp của bảng quyết định. Dựa trên tập rút gọn thu được, việc
sinh luật và phân lớp đạt hiệu quả cao nhất.
Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính
trong bảng quyết định theo tiếp cận lý thuyết tập thô đã thu hút đông đảo cộng
đồng nghiên cứu về tập thô tham gia [1]. Có rất nhiều phương pháp rút gọn
thuộc tính khác nhau đã được đề xuất sử dụng các độ đo khác nhau. Các
phương pháp điển hình được tổng kết trong tài liệu [1] là: phương pháp dựa
trên miền dương, phương pháp dựa trên ma trận phân biệt, các phương pháp
sử dụng độ đo entropy trong lý thuyết thông tin, các phương pháp sử dụng độ
đo trong tính toán hạt, các phương pháp sử dụng độ đo khoảng cách…
Với mong muốn tổng hợp các kết quả nghiên cứu về các phương pháp
rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô, trên cơ sở đó
xây dựng phương pháp sử dụng một độ đo mới (độ đo khoảng cách), luận văn
đặt ra hai mục tiêu chính sau đây:
6
1) Tổng hợp các phương pháp rút gọn thuộc tính và trích lọc luật trong bảng
quyết định theo tiếp cận lý thuyết tập thô trong tài liệu [1, 2], bao gồm:
- Phân nhóm các phương pháp rút gọn thuộc tính và mối liên hệ giữa các
phương pháp dựa vào định nghĩa tập rút gọn.
- Trích lọc luật trong bảng quyết định, bao gồm: luật quyết định và các độ đo
đánh giá hiệu năng, sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn và
đánh giá các phương pháp dựa trên tiêu chuẩn chất lượng phân lớp (độ hỗ trợ) của
tập luật.
2) Xây dựng và thử nghiệm phương pháp rút gọn thuộc tính sử dụng độ đo
khoảng cách, bao gồm: đề xuất độ đo khoảng cách và xây dựng công thức tính
khoảng cách giữa hai tập thuộc tính; định nghĩa tập rút gọn và độ quan trọng của
thuộc tính dựa trên khoảng cách; xây dựng thuật toán heuristic tìm một tập rút gọn
tốt nhất sử dụng khoảng cách; phân nhóm và đánh giá phương pháp sử dụng khoảng
cách với các phương pháp đã có và thử nghiệm phương pháp trên các bộ số liệu
mẫu từ kho dữ liệu UCI [12].
Đố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 và trích lọc luật ở bước khai phá dữ liệu trong quá trình khai
phá dữ liệu và khám phá tri thức.
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ề 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 [12], so sánh và đánh giá kết quả thực nghiệm
so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên
cứu.
7
Bố cục của luận văn gồm phần mở đầu và ba chương nội dung, phần kết luận
và danh mục các tài liệu tham khảo.
Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô của Pawlak [8]
đượ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 công bố về các
phương pháp rút gọn thuộc tính và trích lọc luật, bao gồm phân nhóm các phương
pháp rút gọn thuộc tính, luật quyết định và các độ đo đánh giá hiệu năng, sự thay đổi
các độ đo đánh giá hiệu năng trên các tập rút gọn của các phương pháp, đánh giá các
phương pháp dựa vào chất lượng phân lớp (độ hỗ trợ) của tập luật. Thứ hai là xây
dựng phương pháp rút gọn thuộc tính sử dụng khoảng cách, bao gồm xây dựng
độ đo khoảng cách, định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa
trên khoảng cách, xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử
dụng khoảng cách; phân nhóm và đánh giá phương pháp sử dụng khoảng cách với
các phương pháp đã có.
Chương 3 trình bày kết quả thử nghiệm và đánh giá phương pháp sử dụng
khoảng cách trên các bộ số liệu mẫu từ kho dữ liệu UCI [12] nhằm sáng tỏ các
kết quả nghiên cứu về lý thuyết.
Cuối cùng, phần kết luận nêu những đóng góp của luận văn, hướng phát triển
tiếp theo.
8
Chương 1. TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ
Chương này trình bày các khái niệm cơ bản về lý thuyết tập thô do Pawlak [8]
đề xuất. Các khái niệm cơ bản này là kiến thức nền tảng để sử dụng cho các chương
sau của luận văn.
1.1. Hệ thông tin
Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm p
cột ứng với p thuộc tính và n hàng ứng với n đối tượng. Một cách hình thức, hệ
thông tin được định nghĩa như sau.
Định nghĩa 1.1. Hệ thông tin là trong đó U là tập hữu hạn, khác rỗng các
đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính.
Với mọi , ta ký hiệu giá trị thuộc tính a tại đối tượng u là
thay vì . Nếu là một tập con các thuộc tính thì ta 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 .
Xét hệ thông tin . Mỗi tập con các thuộc tính xác định một
quan hệ hai ngôi trên U, ký hiệu là , xác định bởi
.
là quan hệ P-không phân biệt được. Dễ thấy rằng 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 . Ký hiệu lớp tương đương trong phân hoạch
chứa đối tượng u là , khi đó .
9
1.2. Mô hình tập thô
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 , thế thì một
tập đối tượng X có thể biểu diễn thông qua các lớp tương đương này như thế nào?
Trong lý thuyết tập thô, để biểu diễn X thông qua các lớp tương đương của
(còn gọi là biểu diễn 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 đương của . Có hai cách xấp xỉ tập đối tượng X
thông qua tập 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à 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ó thể thuộc vào X dựa trên tập thuộc tính B. Từ
hai tập xấp xỉ nêu trên, ta định nghĩa các tập
: B-miền biên của X , : B-miền ngoài của X.
B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X,
còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các
lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể viết lại
,
Trong trường hợp thì X được gọi là tập chính xác (exact set),
ngược lại X được gọi là tập thô (rough set).
Với , ta gọi B-miền dương của D là tập được xác định như sau
10
là tập tất cả các đối tượng u sao cho với mọi
Rõ ràng mà
ta đều có . Nói cách khác, .
Ví dụ 1.1. 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.1.
Bảng 1.1. 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 đó:
11
và Như vậy, B-miền biên của X là tập
. Nếu đặt D = {Cảm cúm} thì hợp
; ,
.
Với các khái niệm của tập xấp xỉ đối với phân hoạch , các tập thô được
chia thành bốn lớp cơ bản:
1) Tập X là B-xác định thô nếu và .
2) Tập X là B-không xác định trong nếu và .
3) Tập X là B-không xác định ngoài nếu và .
4) Tập X là B-không xác định hoàn toàn nếu và .
1.3. Bảng quyết định
Một lớp đặc biệt của các hệ thông tin có vai trò quan trọng trong nhiều ứng
dụng là bảng quyết định. Bảng quyết định là một hệ thông tin DS với tập thuộc tính
A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt được gọi là tập
thuộc tính điều kiện và tập thuộc tính quyết định. Tức là với
.
Bảng quyết định được gọi là nhất quán nếu D phụ thuộc hàm vào C, tức là
với mọi kéo theo . Ngược lại thì gọi là không nhất
quán hay mâu thuẫn. Theo định nghĩa miền dương, 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.
12
1.4. 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 ba nhóm:
thuộc tính lõi (core attribute), thuộc tính rút gọn (reductive attribute) và thuộc tính
dư thừa (redundant attribute). Thuộc tính lõi là thuộc tính 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 lõi xuất hiện trong tất cả các tập rút
gọn của bảng quyết định. Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ
chúng không ảnh hưởng đến việc phân lớp tập dữ liệu, thuộc tính dư thừa không
xuất hiện trong bất kỳ tập rút gọn nào của bảng quyết định. Thuộc tính rút gọn là
thuộc tính xuất hiện trong một tập rút gọn nào đó của bảng quyết định. Chúng ta sẽ
đưa ra các định nghĩa chính xác trong phần tiếp theo.
Định nghĩa 1.2. [8] (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 (dispensable) 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 (indispensable). 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à . Khi đó, thuộc tính cần
thiết chính là thuộc tính lõi.
Theo Định nghĩa 1.2, thuộc tính không cần thiết là thuộc tính dư thừa hoặc
thuộc tính rút gọn.
Định nghĩa 1.3. [8] (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 đó .
13
Định nghĩa 1.4. 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 .
Định nghĩa 1.5. Cho bảng quyết định và . Ta nói rằng a là
thuộc tính dư thừa 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ó Có Bình thường Không u1
Có Có Có Cao Có u2
Có Có Có Rất cao Có u3
Có Có Không 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
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
lõi 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 vì không tham gia vào rút gọn nào
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}).
14
1.5. 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ự [3] đề 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.6. [3] (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 thu được bởi phương pháp sử dụng ma trận
phân biệt, gọi tắt là tập rút gọn 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 của C dựa trên ma trận phân biệt.
Định nghĩa 1.7. [3] (Tập lõi 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. Thuộc tính được
gọi là không cần thiết (dispensable) trong DS dựa trên ma trận phân biệt nếu
với mọi . Ngược lại, c được gọi là cần thiết
(indispensable). 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 ma trận phân biệt và được ký hiệu là . Theo [3],
.
15
Chương 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG
BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ
Chương này trình bày hai nội dung chính như sau:
1) Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và
trích lọc luật trong bảng quyết định trong tài liệu [1, 2], bao gồm: tổng hợp và phân
nhóm các phương pháp rút gọn thuộc tính dựa vào tập rút gọn; tổng hợp các kết quả
nghiên cứu về luật quyết định và các độ đo đánh giá hiệu năng; tổng hợp các kết
quả nghiên cứu về so sánh, đánh giá các phương pháp rút gọn thuộc tính.
2) Xây dựng phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao
gồm: xây dựng độ đo khoảng cách; định nghĩa tập rút gọn và độ quan trọng của
thuộc tính dựa trên khoảng cách; xây dựng thuật toán heuristic tìm tập rút gọn sử
dụng khoảng cách; phân nhóm, đánh giá phương pháp khoảng cách với các phương
pháp khác công bố.
2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định
2.1.1. Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính
Mục tiêu của rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô là
sử dụng công cụ tập thô để 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. Dựa vào tập rút gọn thu được, việc
sinh luật và phân lớp đạt hiệu quả cao nhất. Với một bảng quyết định cho trước, độ
phức tạp thời gian của thuật toán tìm tất cả các tập rút gọn là hàm mũ đối với số
thuộc tính điều kiện. Tuy nhiên, trong các bài toán thực tế không đòi hỏi tìm tất cả
các tập rút gọn mà chỉ cần tìm được một tập rút gọn tốt nhất theo một tiêu chuẩn
đánh giá đặt ra. Do đó, các phương pháp rút gọn thuộc tính sử dụng cận tập thô đều
thực hiện theo hướng tiếp cận heuristic. Các phương pháp này đều có các điểm
chung như sau:
- Đưa ra khái niệm tập rút gọn của phương pháp dựa trên một độ đo được
chọn. Các phương pháp khác nhau có độ đo khác nhau, điển hình là các độ đo trong
16
tính toán hạt (granunal computing), độ đo entropy, độ đo khoảng cách, sử dụng ma
trận…
- Đưa ra khái niệm độ 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 dựa trên độ đo được chọn.
- 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á độ quan trọng của thuộc tính (chất lượng phân lớp của thuộc tính).
Thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối
với các bài toán có dữ liệu lớn. 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). Ý tưởng chung của hướng tiếp cận từ
dưới lên (bottom-up) là xuất phát từ tập 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. Ý tưởng chung
của hướng tiếp cận từ trên xuống (top-down) xuất phát từ tập 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.
1) Các phương pháp rút gọn thuộc tính trong bảng quyết định
Theo tiếp cận tập thô, cho đến nay đã có rất nhiều phương pháp rút gọn thuộc
tính dựa trên các độ đo khác nhau được công bố. Trong tài liệu [1, 2], tác giả đã tổng
kết khá đầy đủ các phương pháp rút gọn thuộc tính trong bảng quyết định và các
tập rút gọn tương ứng.
Bảng 2.1. Các phương pháp rút gọn thuộc tính trong tài liệu [1, 2]
STT Phương pháp Tập rút gọn Ký hiệu tập
rút gọn
Phương pháp sử dụng miền Tập rút gọn dựa trên 1
dương. miền dương
Phương pháp sử dụng entropy Tập rút gọn dựa trên 2
17
Shannon entropy Shannon
Phương pháp sử dụng metric Tập rút gọn dựa trên 3
metric
Phương pháp sử dụng các Tập rút gọn dựa trên 4
phép toán trong đại số quan hệ đại số quan hệ
Phương pháp sử dụng ma trận Tập rút gọn dựa trên 5
phân biệt. ma trận phân biệt
Phương pháp sử dụng entropy Tập rút gọn dựa trên 6
Liang entropy Liang
Phương pháp sử dụng độ đo Tập rút gọn dựa trên 7
khác biệt của tri thức độ khác biệt của tri
thức.
2) Phân nhóm các phương pháp rút gọn thuộc tính
Như đã trình bày ở trên, mỗi phương pháp rút gọn thuộc tính đều đưa ra định
nghĩa về tập rút gọn và xây dựng thuật toán heuristic tìm tập rút gọn. Do đó, có thể
nói rằng tập rút gọn là kết quả của phương pháp rút gọn thuộc tính. Vì vậy, việc
phân nhóm các phương pháp rút gọn thuộc tính cũng dựa vào định nghĩa tập rút gọn
và được thực hiện theo nguyên tắc: các phương pháp có tập rút gọn như nhau được
phân thành một nhóm. Trong tài liệu [1, 2], các tác giả đã tổng kết và nghiên cứu
mối liên hệ giữa các định nghĩa tập rút gọn và kết quả phân nhóm các phương pháp
rút gọn thuộc tính như sau:
1) Nếu bảng quyết định nhất quán, các định nghĩa tập rút gọn , , ,
, , , là tương đương nhau.
2) Nếu bảng quyết định không nhất quán:
- Tập rút gọn dựa trên entropy Shannon ( ), tập rút gọn dựa trên metric ( ),
tập rút gọn dựa trên đại số quan hệ ( ) tương đương nhau.
18
- Tập rút gọn dựa trên ma trận phân biệt ( ), tập rút gọn dựa trên entropy
Liang ( ), tập rút gọn dựa trên độ khác biệt của tri thức ( ) tương đương nhau.
Mối quan hệ giữa các định nghĩa tập rút gọn được mô tả như sau:
- Tập rút gọn dựa trên miền dương ( ) là tập con của tập rút gọn dựa trên
entropy Shannon ( ), nghĩa là: nếu là một tập rút gọn dựa trên entropy
Shannon thì tồn tại với là một tập rút gọn dựa trên miền dương.
- Tập rút gọn dựa trên entropy Liang ( ) là tập con của tập rút gọn dựa trên
entropy Shannon ( ), nghĩa là: nếu là một tập rút gọn dựa trên entropy Liang
thì tồn tại với là một tập rút gọn dựa trên entropy Shannon.
Mối liên hệ giữa các tập rút gọn của bảng quyết định không nhất quán được
biểu diễn bằng sơ đồ sau:
Hình 2.1. Mối liên hệ giữa các định nghĩa tập rút gọn
Từ sơ đồ về mối liên hệ giữa các tập rút gọn, các tác giả trong [1, 2] đã thực
hiện phân nhóm các tập rút gọn và chỉ ra mối liên quan hệ giữa các tập rút gọn của
các nhóm. Cụ thể:
Các tập rút gọn trong bảng quyết định không nhất quán được chia thành bốn
nhóm:
Nhóm 1: Bao gồm tập rút gọn .
Nhóm 2: Bao gồm các tập rút gọn , ,
Nhóm 3: Bao gồm các tập rút gọn , ,
Mối liên hệ giữa các tập rút gọn trong các nhóm như sau:
19
Nếu là một tập rút gọn thuộc nhóm 3 thì tồn tại một tập rút gọn
thuộc nhóm 2 và một tập rút gọn thuộc nhóm 1 sao cho .
Dựa vào phân nhóm các tập rút gọn, các phương pháp rút gọn thuộc tính
trong bảng quyết định cũng được phân thành ba nhóm tương ứng.
Đế đánh giá tính hiệu quả của một phương pháp rút gọn thuộc tính, cộng
đồng nghiên cứu về tập thô sử dụng hai tiêu chuẩn: 1) độ phức tạp về thời gian
thực hiện thuật toán heuristic và 2) chất lượng phân lớp của tập rút gọn. Các công
bố về rút gọn thuộc tính đều tính toán độ phức tạp thời gian thuật toán tìm tập rút
gọn. Do đó, hoàn toàn có thể so sánh được tính hiệu quả của các phương pháp về
tiêu chuẩn thời gian. Vì vậy, luận văn tập trung nghiên cứu việc đánh giá các
phương pháp dựa trên tiêu chuẩn chất lượng phân lớp của tập rút gọn.
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ính xác, độ 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.
Phần tiếp theo, luận văn tổng kết các kết quả nghiên cứu liên quan đến luật
quyết định và các độ đo đánh giá hiệu năng trong bảng quyết định trong tài liệu [1,
2]. Luận văn cũng tổng hợp kết quả nghiên cứu về sự thay đổi các độ đo trên các
tập rút gọn của các nhóm phương pháp, từ đó trình bày kết quả so sánh, đánh giá
20
các phương pháp rút gọn thuộc tính dựa trên tiêu chuẩn chất lượng phân lớp của
tập rút gọn.
2.1.2. Luật quyết định và các độ đo đánh giá hiệu năng
1) Luật quyết định và các độ đo đánh giá hiệu năng
Cho bảng quyết định , giả sử và
. Với , và , 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 có dạng .
được Pawlak đề xuất [8].
Các độ đo đánh giá luật quyết định đơn
(1) Độ chắc chắn: ,
(2) Độ hỗ trợ: .
Ví dụ 2.1. Xét bảng quyết định mô tả về các ô tô cho ở Bảng 2.2
với , với (Đơn giá), (Km đã đi),
(Kích thước), (Tốc độ tối đa), D = {d}.
Bảng 2.2. Bảng quyết định về các xe hơi
Ô tô Đơn giá Km đã đi Kích thước Tốc độ tối đa d
Cao Thấp Đầy đủ Thấp Tốt u1
Thấp Thấp Đầy đủ Thấp Tốt u2
Thấp Thấp Gọn nhẹ Thấp Xấu u3
Cao Thấp Đầy đủ Cao Tốt u4
Cao Thấp Đầy đủ Cao Tuyệt hảo u5
21
Thấp Cao Đầy đủ Cao Tốt u6
, Ta có
,
. Vậy
Ta có với , , .
Các luật quyết định là:
(a1, Cao) (a2, Thấp) (a3, Đầy đủ) (a4, Thấp) (d, Tốt)
(a1, Thấp) (a2, Thấp) (a3, Đầy đủ) (a4, Thấp) (d, Tốt)
(a1, Thấp) (a2, Thấp) (a3, Gọn nhẹ) (a4, Thấp) (d, Xấu)
(a1, Cao) (a2, Thấp) (a3, Đầy đủ) (a4, Cao) (d, Tốt)
(a1, Cao) (a2, Thấp) (a3, Đầy đủ) (a4, Cao) (d, Tuyệt hảo)
(a1, Thấp) (a2, Cao) (a3, Đầy đủ) (a4, Cao) (d, Tốt)
Các độ đo của các luật quyết định đơn là:
22
Các độ đo này chỉ sử dụng để đánh giá các luật quyết định đơn, không phù
hợp cho việc đánh giá tập luật quyết định.
Giả sử là một phân hoạch của U theo D. Độ chính
xác của phân lớp F bởi C, ký hiệu là , được Pawlak [8] định nghĩa như sau
và độ nhất quán (hay độ phụ thuộc) được Pawlak [8] định nghĩa như sau
được dùng để đo độ chắc chắn của bảng
Trong một số trường hợp,
quyết định. Tuy nhiên, nhược điểm của độ đo này được Yuhua Qian và các cộng sự
chỉ ra trong [9]. Hơn nữa, độ nhất quán cũng không biểu diễn tốt tính nhất
quán của bảng quyết định vì chỉ xem xét các giá trị xấp xỉ dưới.
Nhằm khắc phục nhược điểm các độ đo cổ điển, trong tài liệu [1, 2] tác giả đã
đưa ra ba độ đo đánh giá hiệu năng tập luật quyết định: độ 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
Độ hỗ trợ của DS được định nghĩa
23
2) Kết quả nghiên cứu về sự thay đổi các độ đo đánh giá hiệu năng trên các tập
rút gọn.
Trong tài liệu [1, 2], tác giả đã nghiên cứu sự thay đổi độ chắc chắn , độ
nhất quán , độ hỗ trợ của bảng quyết định trên các tập rút gọn
, , của các nhóm phương pháp 1, phương pháp 2, phương pháp 3 tương
ứng.
1) Tập rút gọn (tập rút gọn của phương pháp miền dương) làm giảm độ độ
chắc chắn, giảm độ nhất quán và tăng độ hỗ trợ của tập luật đối với bảng quyết định
không nhất quán.
2) Tập rút gọn (tập rút gọn của các phương pháp sử dụng entropy Shannon,
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
metric) 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.
3) Tập rút gọn (tập rút gọn của các phương pháp sử dụng ma trận phân biệt,
phương pháp sử dụng độ khác biệt của tri thức, phương pháp sử dụng entropy
Liang) 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.
Hơn nữa, nếu thì độ hỗ trợ của tập luật dựa trên tập rút gọn lớn
hơn độ hỗ trợ của tập luật dựa trên tập rút gọn . Điều này có nghĩa là chất lượng
phân lớp của cao hơn , hay nhóm phương pháp 1 hiệu quả hơn nhóm phương
pháp 2 về chất lượng phân lớp. Điều này cho ta kết quả đánh giá các nhóm phương
pháp khác ở mục sau.
2.1.3. Lựa chọn, so sánh, đánh giá các phương pháp rút gọn thuộc tính
1) Lựa chọn nhóm phương pháp phù hợp
Mục tiêu rút gọn thuộc tính trong 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 khả năng phân lớp của bảng quyết định. Theo
24
tiếp cận độ đo, 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 mà bảo toàn độ chắc chắn của tập luật quyết định. Từ các kết quả đã
trình bày ở mục 2.1.2 tác giả rút ra kết luận.
1) Tập rút gọn , tập rút gọn , tập rút gọn đều bảo toàn độ chắc chắn
của tập luật đối với bảng quyết định không đầy đủ nhất quán. Do đó, tất cả các
phương pháp rút gọn thuộc tính đã trình bày ở bài báo này đều phù hợp với các
bảng quyết định nhất quán.
2) Tập rút gọn làm giảm độ chắc chắc của tập luật đối với bảng quyết định
không đầy đủ không nhất quán, do đó phương pháp miền dương thuộc Nhóm 1
không phù hợp với các bảng quyết định không nhất quán.
3) Tập rút gọn , tập rút gọn đều bảo toàn độ chắc chắn của tập luật đối
với bảng quyết định không nhất quán. Do đó, các phương pháp trong Nhóm 2,
Nhóm 3 đều phù hợp với các bảng quyết định không nhất quán
2) So sánh, đánh giá các phương pháp theo chất lượng phân lớp
Sau khi đưa ra khái niệm tập rút gọn, các phương pháp rút gọn thuộc tính đều
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 dựa trên tiêu chuẩn
độ quan trọng của thuộc tính, hay chất lượng phân lớp của thuộc tính. Với bảng
quyết định nhất quán, các tập rút gọn tốt nhất của bốn nhóm phương pháp là như
nhau nên chúng có chất lượng phân lớp như nhau. Với bảng quyết định không nhất
quán, tác giả đánh giá hai nhóm phương pháp phù hợp (Nhóm 2, Nhóm 3) dựa trên
tiêu chuẩn chất lượng phân lớp tập rút gọn của nhóm phương pháp.
Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc Nhóm 3
tìm được bởi thuật toán heuristic sử dụng entropy Liang, độ khác biệt của tri (
thức hay ma trận phân biệt). Theo kết quả nghiên cứu về mỗi liên hệ giữa các tập
rút gọn, tồn tại một tập rút gọn của nhóm 2 là sao cho ( tối thiểu
hơn ).
25
Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc Nhóm 2
tìm được bởi thuật toán heuristic sử dụng entropy Shannon, metric hay ma (
trận phân biệt). Ta có hai trường hợp.
- Nếu chính là ( ) thì , nghĩa là tối thiểu
hơn . Do đó, độ hỗ trợ của tập luật dựa trên cao hơn độ hỗ trợ của tập
luật dựa trên , hay có chất lượng phân lớp tốt hơn .
- Nếu khác thì có chất lượng phân lớp tốt hơn do có
chất lượng phân lớp tốt nhất. Mặt khác, do nên tốt hơn về chất
lượng phân lớp. Do đó, tốt hơn về chất lượng phân lớp.
Do đó, trong cả hai trường hợp có chất lượng phân lớp tốt hơn . Từ
đó kết luận các phương pháp thuộc Nhóm 2 hiệu quả hơn các phương pháp thuộc
Nhóm 3 theo tiêu chuẩn đánh giá chất lượng phân lớp của tập rút gọn.
2.2. Xây dựng phương pháp rút gọn thuộc tính trong bảng
quyết định sử dụng khoảng cách
Trong phần 2.1, luận văn đã tổng kết các kết quả nghiên cứu về các phương
pháp rút gọn thuộc tính và luật quyết định trong bảng quyết định, bao gồm: kết quả
về phân nhóm các phương pháp dựa vào tập rút gọn; kết quả về so sánh và đánh giá
các phương pháp dựa trên tiêu chuẩn chất lượng phân lớp của tập rút gọn. Trong
phần này, luận văn xây dựng phương pháp rút gọn thuộc tính sử dụng độ đo khoảng
cách, độ đo khoảng cách do luận văn đề xuất.
Kỹ thuật sử dụng khoảng cách đóng vai trò quan trọng trong khai phá dữ liệu
và học máy. Trong lý thuyết tập thô, khoảng cách cũng là một trong những độ đo
hiệu quả để giải quyết bài toán rút gọn thuộc tính. Các kết quả đáng chú ý về
hướng nghiên cứu này là:
- Các tác giả trong công trình [6] đã xây dựng một công thức tính metric
giữa hai phân hoạch (sinh bởi hai tập thuộc tính) sử dụng khoảng cách
Jaccard giữa hai tập hợp hữu hạn và đề xuất phương pháp rút gọn thuộc
26
tính sử dụng metric. Các tác giả cũng chứng minh phương pháp sử dụng
metric hiệu quả hơn các phương pháp sử dụng Entropy thông tin.
Tiếp tục hướng nghiên cứu về kỹ thuật sử dụng khoảng cách, trong phần này
luận văn xây dựng phương pháp rút gọn thuộc tính trong bảng quyết định dựa trên
một độ đo khoảng cách do luận văn đề xuất và phân nhóm phương pháp được xây
dựng vào các nhóm phương pháp đã có. Trên cơ sở đó, luận văn so sánh, đánh giá
phương pháp khoảng cách với các phương pháp đã công bố. Tương tự các phương
pháp khác, phương pháp sử dụng khoảng cách phân hoạch bao gồm các bước sau:
1) Định nghĩa một độ đo khoảng cách và xây dựng công thức tính khoảng
cách giữa hai tập thuộc tính trong bảng quyết định.
2) Định nghĩa tập rút gọn dựa trên khoảng cách.
3) Định nghĩa độ quan trọng của thuộc tính dựa trên khoảng cách.
4) Xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn
độ quan trọng của thuộc tính (hay chất lượng phân lớp của thuộc tính)
5) Phân nhóm và đánh giá phương pháp xây dựng.
2.2.1. Độ đo khoảng cách
Trong trường hợp tổng quát, một khoảng cách trên tập hợp U là một ánh xạ
thỏa mãn các điều kiện sau với mọi [4].
khi và chỉ khi
, .
.
.
Điều kiện được gọi là tiên đề bất đẳng thức tam giác. Bộ đôi
được gọi là một không gian khoảng cách.
27
Định lý 2.1. Cho U là tập hữu hạn các đối tượng và
là họ các tập con
của U. Với mọi
, biểu thức:
là một khoảng cách giữa tập X và tập Y.
Chứng minh. Hiển nhiên,
thỏa mãn điều kiện (P1) và (P2). Do
đó, ta cần chứng minh điều kiện (P3) (bất đẳng thức tam giác), nghĩa là với
mọi
ta có:
(3.1)
Giả sử
và
. Ta biểu diễn tập
bởi một véc tơ
với
nếu
và
trong trường hợp
N chiều
ngược lại.
Đặt
(tích trong của véc tơ
và
), khi đó
được biểu
diễn:
, ta có:
(3.2)
Dễ thấy
hoặc
thỏa mãn vì
phần tử thứ k của
và
là 0 và 1. Từ công thức 3.2 ta có:
(đpcm)
2.2.2. Xây dựng khoảng cách giữa hai tri thức và các tính chất
Từ khoảng cách giữa hai tập hợp hữu hạn được định nghĩa ở phần 2.1.1,
luận văn xây dựng khoảng cách giữa hai tri thức sinh bởi hai tập thuộc tính
trên bảng quyết định.
Cho bảng quyết định
, mỗi tập thuộc tính
,
được gọi là một tri thức (knowledge) của P trên U [1].
gồm
phần tử, mỗi phần tử là một khối trong phân hoạch
, còn
28
được gọi là một hạt tri thức (knowledge granule). Ký hiệu họ tất cả các tri
thức trên U là
.
Định lý 2.2. Ánh xạ
xác định bởi
là một khoảng cách giữa
và
.
Chứng minh
(P1) Áp dụng Định lý 2.1 với hai tập hợp
và
với
ta có
. Do đó,
.
khi
và
chỉ
khi
với mọi
, nghĩa là
.
(P2) Theo định nghĩa
với mọi
.
(P3) Theo định nghĩa ta có :
Từ (P1), (P2), (P3) kết luận
là một khoảng cách trên
.
Khoảng cách giữa hai tri thức
và
cũng được xem là khoảng
cách giữa hai tập thuộc tính P và Q trong bảng quyết định.
29
Mệnh đề 2.1.Cho bảng quyết định
và
, khi đó ta có:
1)
đạt giá trị nhỏ nhất là 0 khi và chỉ khi
2)
đạt giá trị lớn nhất là
khi và chỉ khi
,
hoặc
,
.
Chứng minh. Từ Định lý 2.2 ta có
đạt giá trị nhỏ nhất là
0 khi và chỉ khi
.
đạt giá trị lớn nhất khi
đạt giá trị lớn nhất là
và
đạt giá trị nhỏ nhất là 1,
nghĩa là
,
hoặc
,
. Giá trị lớn nhất là :
.
Mệnh đề 2.2. Cho bảng quyết định
và hai phân hoạch
,
. Khi đó ta có:
Chứng minh. Giả sử
với
và
, khi
đó
và
. Ta có
.
.
30
.
Do đó
Vì vậy ta có:
(đpcm)
Trong [5], Jiye Liang và các cộng sự đã đưa ra một định nghĩa mới về entropy,
chúng tôi gọi là entropy Liang.
và tập thuộc tính . Định nghĩa 2.1. [5] Cho bảng quyết định
Giả sử . Entropy Liang của P được định nghĩa bởi
với . Nếu đạt giá trị nhỏ nhất là 0, còn nếu thì
. Vì vậy ta có
với thì đạt giá trị lớn nhất là
.
Định nghĩa 2.2. [5] Cho bảng quyết định . Giả sử
. Entropy Liang có điều kiện của D khi đã
biết C được định nghĩa bởi
31
còn có thể được viết dưới dạng khác như sau
. với
.
Mệnh đề 2.3. Cho bảng quyết định
. Khi đó
với
là entropy Liang có điều kiện trong
[5].
Chứng minh. Giả sử
và
. Theo
định nghĩa entropy Liang trong [5] ta có:
(đpcm)
2.2.3. Phương pháp rút gọn thuộc tính sử dụng khoảng cách
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 khoảng cách, tác giả tiến hành các bước:
- Định nghĩa tập rút gọn dựa trên khoảng cách
- Định nghĩa độ quan trọng của thuộc tính sử dụng khoảng cách phân hoạch.
Độ 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.
- Xây dựng 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.
1) Tập rút gọn dựa trên khoảng cách
32
Định nghĩa 2.3. Cho bảng quyết định
, thuộc tính
gọi là
;
không cần thiết trong DS 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, ký hiệu là
.
Định nghĩa 2.4. Cho bảng quyết định
và tập thuộc tính
.
Nếu
1)
2)
thì R là một rút gọn của C dựa trên khoảng cách.
2) Độ quan trọng của thuộc tính dựa trên khoảng cách
Định nghĩa 2.5. Cho bảng quyết định
,
và
.
Độ quan trọng của thuộc tính
được định nghĩa bởi
với giả thiết
.
Theo [5],
nên
và
. Do đó,
được tính bởi lượng thay đổi khoảng cách
giữa B và
khi thêm thuộc tính b vào B và
càng lớn thì lượng
thay đổi khoảng cách càng lớn, hay thuộc tính b càng quan trọng và ngược lại.
Độ quan trọng của thuộc tính này là 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.
3) Thuật toán heuristic tìm tập rút gọn dựa trên khoảng cách phân hoạch
Để xây dựng thuật toán heuristic tìm tập rút gọn, 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 đề xuất một thuật toán heuristic tìm tập rút gọn tính toán lõi
33
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 R :=
CORE, 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 đề xuất sử dụng chiến lược Thêm - Xóa [10].
Thuật toán DBAR (Distance Based Attribute Reduction). Thuật toán
heuristic tìm một tập rút gọn tốt nhất sử dụng khoảng cách.
Đầu vào: Bảng quyết định
.
Đầu ra: Một tập rút gọn tốt nhất
.
//Tìm tập lõi
;
1.
;
2. For
then
3. If
//Tìm tập rút gọn dựa trên khoảng cách
;
4.
5. While
do
6. Begin
7.
For
tính
;
8.
Chọn
sao cho
;
9.
;
10. End;
//Loại bỏ các thuộc tính dư thừa trong R (nếu có)
11.
;
12. For each
13. Begin
14.
Tính
;
34
15.
If
then
;
16. End;
17. Return
;
Chứng minh tính đúng đắn của Thuật toán DBAR
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ừ 4 đến 10 thỏa mãn điều kiện bảo toàn khoảng cách
.
Với bước loại bỏ các thuộc tính dư thừa, câu lệnh từ 11 đến 16 đảm bảo tập R
là tối thiểu, nghĩa là .
Theo Định nghĩa 2.4, R là tập rút gọn dựa trên khoảng cách phân hoạch.
Độ phức tạp thời gian của Thuật toán DBAR
Xét bảng quyết định
(giả sử tập thuộc tính quyết định D
chỉ có một thuộc tính
), theo [11], độ phức tạp thời gian (gọi tắt là độ
phức tạp) để tính phân hoạch
là
, do đó độ phức tạp để tính
khoảng cách
là
,
độ phức tạp để tính tập lõi
từ câu lệnh số 1 đến câu lệnh số 3 là
, độ phức tạp để tính tập rút gọn từ câu
lệnh số 4 đến câu lệnh số 9 cũng là
. Vậy, độ phức tạp của
Thuật toán DBAR là
.
Ví dụ 2.2. Xét bảng quyết định
cho ở Bảng 2.3
Bảng 2.3. Bảng quyết định minh họa thuật toán tìm tập rút gọn
U
d
35
1
1
0
0
u1
1
1
1
0
u2
1
0
0
0
u3
1
0
1
0
u4
1
0
1
0
u5
0
0
1
1
u6
0
1
1
1
u7
,
Ta có
,
.
,
.
1) Thực hiện các câu lệnh từ dòng lệnh số 1 đến dòng lệnh số 3 của Thuật
toán DBAR để tìm tập lõi
, ta có:
;
1.
2.
3. Xét lần lượt các thuộc tính
. Ta có:
do đó
do đó
.
.
.
Do đó
Vì vậy
.
36
2) Thực hiện các câu lệnh từ dòng lệnh số 4 đến dòng lệnh số 11 của Thuật
toán DBAR để tìm tập rút gọn tốt nhất
, ta có:
Đặt
,
thực hiện vòng lặp While.
Do đó
Xét thuộc tính
. Theo tính toán ở phần 1):
, do đó:
Xét thuộc tính
. Theo tính toán ở phần 1):
, do đó:
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 ở phần 1):
. Dừng vòng lặp While.
Thực hiện vòng lặp For. Xét
và
Theo tính toán ở trên,
. Do đó
là một tập rút gọn tốt nhất của C dựa trên khoảng cách.
2.2.4. Phân nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách
Trước hết, luận văn trình bày định nghĩa tập rút gọn dựa trên entropy Liang
trong [5]. Dựa trên entropy Liang có điều kiện, các tác giả trong [5] định nghĩa tập
rút gọn của bảng quyết định.
37
Định nghĩa 2.6. [5] (Tập rút gọn Entropy Liang) Cho bảng quyết định
và tập thuộc tính . Nếu
. 1)
. 2)
thì R là một rút gọn của C dựa trên entropy Liang có điều kiện, gọi tắt là tập rút gọn
Entropy Liang.
Cho bảng quyết định và . Từ Mệnh đề 2.3 ta có
khi và chỉ khi . Theo
Định nghĩa 2.4 về tập rút gọn dựa trên khoảng cách và Định nghĩa 2.6 về tập rút gọn
dựa trên entropy Liang ta kết luận: Tập rút gọn dựa trên khoảng cách tương đương
với tập rút gọn dựa trên entropy Liang. Theo kết quả phân nhóm các phương pháp
rút gọn thuộc tính đã trình bày ở phần 2.1 ta kết luận: Phương pháp rút gọn sử dụng
khoảng cách thuộc Nhóm 3.
38
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à:
Đánh giá tính hiệu quả của thuật toán rút gọn thuộc tính sử dụng khoảng
cách (Thuật toán DBAR) với các thuật toán trong Nhóm 3 (gồm phương pháp
sử dụng entropy Liang, phương pháp sử dụng độ khác biệt của tri thức,
phương pháp sử dụng ma trận phân biệt). Luận văn chọn thuật toán rút gọn
thuộc tính sử dụng entropy Liang (của phương pháp rút gọn thuộc tính sử
dụng entropy Liang), gọi tắt là thuật toán ELBAR (Entropy Liang Based
Attribute Reduction) để so sánh với thuật toán DBAR vì phương pháp này
hiệu quả hơn các phương pháp khác trong Nhóm 3 [1].
Để thực hiện nhiệm vụ đặt ra, luận văn thực hiện các công việc sau:
- Cài đặt thuật toán DBAR và thuật toán rút gọn thuộc tính sử dụng
entropy Liang (thuật toán ELBAR)
- Thử nghiệm hai thuật toán trên các bộ số liệu lấy từ kho dữ liệu UCI
[12], so sánh thời gian thực hiện và kết quả thực hiện của hai thuật toán trên
các bộ số liệu thử nghiệm được chọn.
- Cài đặt và thực hiện thuật toán trích lọc luật RuleExtract trên tập rút gọn tìm
được của Thuật toán DBAR.
3.2. Phân tích, lựa chọn công cụ
Để thực hiện các công việc nêu trên, trước hết luận văn trình bày thuật
toán rút gọn thuộc tính sử dụng entropy Liang [5], gọi tắt là thuật toán
ELBAR (Entropy Liang Based Attribute Reduction)
39
3.2.1. Thuật toán tìm tập rút gọn sử dụng entropy Liang
Trong [5], J.Y. Liang và các cộng sự đưa ra khái niệm về tập rút gọn
dựa trên entropy mới, gọi là entropy Liang. Cho bảng quyết định
. Giả sử
. Entropy
Liang có điều kiện của D khi đã biết C được định nghĩa:
Nếu tập thuộc tính
thỏa mãn:
1)
.
2)
.
thì R được gọi là một tập rút gọn của DS dựa trên entropy Liang.
Thuật toán tìm tập rút gọn sử dụng entropy Liang, gọi tắt là thuật toán
NEBAR, được mô tả như sau:
Thuật toán ELBAR. Tìm tập rút gọn của bảng quyết định sử dụng entropy
Liang [5]. (Entropy Liang Based Attribute Reduction)
Đầu vào:
Bảng quyết định
.
Đầu ra:
Một tập rút gọn
.
1.
;
2. Tính
,
;
// Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất
do
3. While
4. Begin
5.
For each
tính
;
6.
Chọn
sao cho
;
7.
;
40
8. End;
// Loại bỏ các thuộc tính dư thừa trong R nếu có
9. For each
10.
If
then
;
11. Return
;
3.2.2. Lựa chọn công cụ và cài đặt
Luận văn sử dụng công cụ là ngôn ngữ lập trình C# trên môi trường hệ điều
hành Windows XP Professional để thực hiện cài đặt các thuật toán rút gọn thuộc tính
DBAR, ELBAR và thuật toán trích lọc luật quyết định RuleExtract.
3.3. Một số kết quả thử nghiệm
3.3.1. Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng khoảng cách
Sau khi cài đặt thuật toán rút gọn thuộc tính sử dụng khoảng cách (DBAR)
và thuật toán rút gọn thuộc tính sử dụng entropy Liang (ELBAR), tác giả tiến
hành thử nghiệm hai thuật toán này trên 6 bộ số liệu vừa và nhỏ lấy từ kho dữ
liệu UCI [12]. Môi trường thử nghiệm là máy tính LAPTOP với cấu hình Intel
Core i3 2.13 GHz CPU, 2GB bộ nhớ RAM, sử dụng hệ điều hành Windows 8.1.
Với mỗi bộ số liệu, giả sử
là số đối 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, 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 và Bảng
3.2 mô tả kết quả thực hiện của hai thuật toán.
Bảng 3.1. Kết quả thực hiện Thuật toán ELBAR và Thuật toán DBAR
Thuật toán Thuật toán
ELBAR DBAR STT Bộ số liệu
t t
155 19 4 1.296 4 0.89 1 Hepatitis.data
41
56 32 4 0.187 4 0.171 2 Lung-cancer.data
25 205 5 3 5 1.687 3 Automobile.data
38 798 9 179 9 86.921 4 Anneal.data
16 435 15 25.562 15 16.734 5 Congressional
Voting Records
690 15 7 29.703 7 15.687 6 Credit Approval
Bảng 3.2. Tập rút gọn của Thuật toán ELBAR và Thuật toán DBAR
STT Bộ số liệu Tập rút gọn của Tập rút gọn của
Thuật toán ELBAR Thuật toán DBAR
{1, 2, 4, 17} {1, 2, 4, 17} 1 Hepatitis.data
{3, 4, 9, 43} {3, 4, 9, 43} 2 Lung-cancer.data
{1, 13, 14, 20, 21} {1, 13, 14, 20, 21} 3 Automobile.data
{1, 3, 4, 5, 8, 9, 33, 34, {1, 3, 4, 5, 8, 9, 33, 34, 4 Anneal.data
35} 35}
{1, 2, 3, 4, 5, 7, 8, 9, 10, {1, 2, 3, 4, 5, 7, 8, 9, 10, 5 Congressional
11, 12, 13, 14, 15, 16} 11, 12, 13, 14, 15, 16} Voting Records
{1, 2, 3, 4, 5, 6, 8} {1, 2, 3, 4, 5, 6, 8} 6 Credit Approval
Kết quả thử nghiệm cho thấy
Trên 6 bộ số liệu được chọn, tập rút gọn thu được bởi Thuật toán DBAR
và Thuật toán ELBAR là như nhau. Kết quả này phù hợp với kết quả
nghiên cứu lý thuyết đã trình bày ở phần trên.
Thời gian thực hiện Thuật toán DBAR nhanh hơn Thuật toán ELBAR,
do đó Thuật toán DBAR hiệu quả hơn Thuật toán ELBAR.
Tiếp theo, tác giả tiến hành thử nghiệm Thuật toán DBAR và Thuật toán
ELBAR trên 5 bộ số liệu kích thước lớn. Kết quả thử nghiệm được mô tả ở
bảng sau:
42
Bảng 3.3. Kết quả thực hiện Thuật toán ELBAK và Thuật toán DBAK
trên các bộ số liệu lớn
Thuật toán Thuật toán ST ELBAR DBAR Bộ số liệu T STT t t
299285 11415 21 5206 21 40 1 Census-Income.data
48842 1270 9 675 9 14 2 Adult.data
1950 1000 92 2867 92 1247 3 Dorothea.data
00
4 1000000 11 8 8977 8 4376 Poker-hand-
testing.data
581012 54 17 14289 17 7256 5 CovType.data
Với các bộ số liệu có kích thước lớn, rõ ràng thời gian thực hiện Thuật
toán DBAR nhỏ hơn nhiều Thuật toán ELBAR, do đó bộ số liệu kích thước
càng lớn, Thuật toán DBAR càng hiệu quả.
3.3.2. Kết quả thử nghiệm về trích lọc luật theo tiếp cận tập thô
Cho bảng quyết định , giả sử và
. Với , và . Thuật toán RuleExtract hiển
và đỗ hỗ trợ
thị các luật quyết định dạng với độ chắc chắn
tương ứng.
Thuật toán RuleExtract
Input: Bảng quyết định DS = (U, CD, V, f).
và độ hỗ trợ
Output: Hiển thị danh sách các luật với độ chắc chắn .
1. Tính phân hoạch ;
43
2. For each
3. Begin
Tính ; 4.
For each 5.
Begin 6.
7. Sinh luật
;
8. Tính
;
9. Tính
, độ chắc chắn
, độ hỗ trợ
;
10. Hiển thị luật
11. End;
12. End;
13. Return.
Thuật toán RuleExtract sinh luật quyết định (luật phân lớp) sử dụng tập thô
được cài đặt bằng ngôn ngữ C#. Môi trường thử nghiệm là máy tính PC với cấu
hình Pentium dual core 2.13 GHz CPU, 1GB bộ nhớ RAM, sử dụng hệ điều hành
Windows XP Professional. Bộ số liệu thử nghiệm là Soybean-small.data lấy từ
kho dữ liệu UCI [12]. 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 DBAR 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.7
44
Bảng 3.4. Tập rút gọn tốt nhất của bộ số liệu Soybean-small
STT Bộ số liệu Tập thuộc Tập thuộc
tính ban đầu tính rút gọn
1 47 35 {c1,…,c35} {c4, c22} 1 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 tập thô 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
là độ chắc chắn và
là độ hỗ trợ của mỗi luật.
được mô tả trong Bảng 3.8, trong đó: tổng số luật phân lớp là 7, độ dài mỗi luật là 2,
Bảng 3.5. Các luật phân lớp trên bảng quyết định rút gọn sử dụng tập thô
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
45
Chú thích: Trên bảng Bảng 3.8, c4(1) nghĩa là thuộc tính c4 nhận giá trị 1 (c4
= 1). D1, D2, D3, D4 các là giá trị thuộc tính quyết định (tổng số 4 lớp quyết định).
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
DBAR, 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.
46
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. Nội dung nghiên cứu của
luận văn 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
xây dựng phương pháp dựa trên độ đo mới. Luận văn có hai kết quả chính:
(1) Tổng kết các kết quả đã công bố về hướng nghiên cứu rút gọn thuộc tính và
trích lọc luật trong bảng quyết định theo tiếp cận tập thô, bao gồm:
Phân nhóm các phương pháp rút gọn thuộc tính dựa vào tập rút gọn -
Luật quyết định và các độ đo đánh giá hiệu năng tập luật quyết định. -
Sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn, từ đó đánh -
giá các nhóm phương pháp dựa trên tiêu chuẩn chất lượng phân lớp của tập rút gọn (độ
hỗ trợ tập luật).
(2) Theo hướng tiếp cận khoảng cách, luận văn đề xuất một độ đo khoảng cách
và xây dựng phương pháp rút gọn thuộc tính sử dụng khoảng cách và thử nghiệm
phương pháp trên các bộ số liệu mẫu từ kho dữ liệu thử nghiệm UCI [13]. Phương
pháp sử dụng khoảng cách thuộc nhóm 3, do đó về tập rút gọn sẽ tương đương với các
phương pháp thuộc nhóm 3.
2) Hướng phát triển tiếp theo
Tiếp tục nghiên cứu các phương pháp gia tăng rút gọn thuộc tính trong bảng
quyết định trong trường hợp bổ sung và loại bỏ tập đối tượng, tập thuộc tính.
47
Tài liệu tham khảo
Tài liệu tiếng Việt
[1] Nguyễn Long Giang, “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, 2012.
[2] Nguyễn Long Giang, Phạm Hoàng Tuyên, Nghiên cứu sự thay đổi giá trị 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, Kỷ yếu Hội
thảo Quốc gia lần thứ XV “Một số vấn đề chọn lọc của Công nghệ thông tin
và truyền thông”, Hà Nội 11/2012, 2013, Tr. 295-301.
Tài liệu tiếng Anh
Andrzej Skowron and Rauszer C (1992), “The Discernibility Matrices and
[3]
Functions in Information Systems”, Interlligent Decision Support,
Handbook of Applications and Advances of the Rough Sets Theory, Kluwer,
Dordrecht, pp. 331-362.
[4]
Deza M. M. and Deza E., “Encyclopedia of Distances”, Springer, 2009.
[5]
Liang J.Y, Chin K.S., Dang C.Y. and Richard C.M.YAM, “New
method for measuring uncertainty and fuzziness in rough set theory”,
International Journal of General Systems 31, 2002, pp. 331-342.
[6]
Long Giang Nguyen, “Metric Based Attribute Reduction in Decision
Tables”, The 2012
International Workshop on Rough Sets
Applications (RSA’2012), FedCSIS Proceedings, IEEE, 2012, pp. 333-
338.
[7]
Pawlak Z. (1982), “Rough sets”, International Journal of Computer
and Information Sciences, 11(5): 341-356.
[8]
Pawlak Z., Rough sets: Theoretical Aspects of Reasoning About Data,
48
Kluwer Aca-demic Publishers, 1991.
Qian Y.H., Liang J.Y., Li D.Y., Zhang H.Y. and Dang C.Y. (2008),
[9]
“Measures for Evaluating The Decision Performace of a Decision Table in
Rough Set Theory”, Information Sciences, Vol.178, pp.181-202.
[10] Wang F., Liang J. Y, Qian Y. H., “Attribute reduction: A dimension
incremental strategy”, Knowledge-Based Systems, Volume 39, 2013,
pp. 95–108
[11] Z. Y. Xu, Z. P. Liu, B. R. Yang, W. Song., “A quick attribute
reduction algorithm with complexity of max(O(|C||U|), O(|C|2|U/C|))”,
Journal of Computer, Vol. 29, no. 3, pp. 391-398, 2006.
[12] The UCI machine learning repository,
49
Phụ lục
1. Một số giao diện của chương trình thử nghiệm
Hình 1. Giao diện chính chương trình
Hình 2. Chọn bộ dữ liệu từ kho dữ liệu UCI
50
Hình 3. Tính phân hoạch với bộ dữ liệu IRIS.DATA từ kho dữ liệu UCI
Hình 4. Tính phân hoạch U/D của bộ dữ liệu IRIS.DATA từ kho dữ liệu UCI
51
Hình 5. Tính phân hoạch U/C của bộ dữ liệu IRIS.DATA từ kho dữ liệu UCI
Hình 6. Thực nghiệm tính khoảng cách của bộ dữ liệu bằng thuật toán Entropy Liang
52
Kết quả khi chạy với bộ dữ liệu IRIS.DATA từ kho dữ liệu UCI:
Tập rút gọn: {C1,C2,C3} -
Tập dư thừa: {C4} -
Số thuộc tính sau rút gọn: 3 -
Thời gian tính toán: 0 giây 328 mili giây -
Hình 7. Thực nghiệm tính khoảng cách của bộ dữ liệu bằng thuật toán DBAR
Kết quả khi chạy với bộ dữ liệu IRIS.DATA từ kho dữ liệu UCI:
Tập rút gọn: {C1,C2,C3} -
Tập dư thừa: {C4} -
Số thuộc tính sau rút gọn: 3 -
Thời gian tính toán: 0 giây 62 mili giây -
