ĐẠ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. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định....................................... 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.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 25
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
Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .................................................. 38
3.1. Bài toán .......................................................................................................................... 38
3.2. Phân tích, lựa chọn công cụ ......................................................................................... 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.3. Một số kết quả thử nghiệm........................................................................................... 40
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
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à IS U , A 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 u U , a A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a u
thay vì f u, a . Nếu B b1 , b2 ,..., bk A là một tập con các thuộc tính thì ta ký
hiệu bộ các giá trị bi u bởi B u . Như vậy, nếu u và v là hai đối tượng, thì ta viết
B u B v nếu bi u bi v với mọi i 1,..., k .
Xét hệ thông tin IS U , A . Mỗi tập con các thuộc tính P A xác định một
quan hệ hai ngôi trên U, ký hiệu là IND P , xác định bởi
IND P u, v U U a P, a u a v .
IND P là quan hệ P-không phân biệt được. Dễ thấy rằng IND P là một quan hệ
tương đương trên U. Nếu u, v IND P 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 IND P xác định một phân hoạch trên
U, ký hiệu là U / IND P hay U / P . Ký hiệu lớp tương đương trong phân hoạch
U / P chứa đối tượng u là u P , khi đó u P v U u, v IND P .
9
1.2. Mô hình tập thô
Cho hệ thông tin IS U , A và tập đối tượng X U . Với một tập thuộc tính
B A cho trước, chúng ta có các lớp tương đương của phân hoạch U / B , 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
U / B (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 U / B . 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à BX và BX , được xác định như sau:
BX u U u B X , BX u U u B X .
Tập BX 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
BX 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
BN B X BX BX : B-miền biên của X , U BX : 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
BX
Y U / B Y X ,
BX
Y U / B Y X .
Trong trường hợp BN B X 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 B, D A , ta gọi B-miền dương của D là tập được xác định như sau
BX
POS B ( D)
X U / D
10
Rõ ràng POSB ( D) là tập tất cả các đối tượng u sao cho với mọi v U mà
u B v B ta đều có u D v D . Nói cách khác, POSB ( D) u U u B u D .
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
u1
Có
Bình thường
Không
u2
Có
Cao
Có
u3
Có
Rất cao
Có
u4
Không
Bình thường
Không
u5
Không
Cao
Không
u6
Không
Rất cao
Có
u7
Không
Cao
Có
u8
Không
Rất cao
Không
Ta có: U / {Đau đầu} =
u , u , u ,u , u , u , u , u
U / {Thân nhiệt} =
U / {Cảm cúm} =
1
2
3
4
5
6
7
8
u , u ,u , u , u ,u , u , u
1
4
2
5
7
3
6
8
u , u , u , u ,u , u , u , u
1
4
U / {Đau đầu, Cảm cúm} =
5
8
2
3
6
7
u ,u , u ,u , u , u ,u , u
1
2
3
4
5
8
6
7
Như vậy, các bệnh nhân u2 , u3 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à:
u1 , u2 , u3 , u4 , u5 , u7 , u6 , u8 .
Đặt X {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u7 . Khi đó:
11
BX u2 , u3 và BX u2 , u3 , u5 , u6 , u7 , u8 . Như vậy, B-miền biên của X là tập
hợp BN B X u5 , u6 , u7 , u8 . Nếu đặt D = {Cảm cúm} thì
U / D X1 u1, u4 , u5 , u8 ; X 2 u2 , u3 , u6 , u7 , BX1 u1 , u4 ; BX 2 u2 , u3 ,
BX u1 , u2 , u3 , u4 .
POSB ( D)
X U / D
Với các khái niệm của tập xấp xỉ đối với phân hoạch U / B , 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 BX và BX U .
2) Tập X là B-không xác định trong nếu BX và BX U .
3) Tập X là B-không xác định ngoài nếu BX và BX U .
4) Tập X là B-không xác định hoàn toàn nếu BX và BX U .
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à DS U , C D với
C D .
Bảng quyết định DS đượ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 u, v U , C u C v kéo theo D u D v . 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 POSC D U . Trong trường hợp bảng không nhất quán thì POSC D chính là
tập con cực đại của U sao cho phụ thuộc hàm C D đú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
DS U , C D . Thuộc tính c C được gọi là không cần thiết (dispensable) trong
DS dựa trên miền dương nếu POSC D POS(C c) D ; 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à PCORE C . 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
DS U ,C D và tập thuộc tính R C . Nếu
1) POSR ( D) POSC ( D)
2) r R, POSRr ( D) POSC ( D)
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
PRED C là họ tất cả các tập rút gọn Pawlak của C. Khi đó PCORE C
R.
RPRED C
13
Định nghĩa 1.4. Cho bảng quyết định DS U , C D và a C . 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 R PRED C sao cho a R .
Định nghĩa 1.5. Cho bảng quyết định DS U , C D và a C . Ta nói rằng a là
thuộc tính dư thừa của DS nếu a C
R.
RPRED C
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
u1
Có
Có
Có
Bình thường
Không
u2
Có
Có
Có
Cao
Có
u3
Có
Có
Có
Rất cao
Có
u4
Có
Không
Có
Bình thường
Không
u5
Có
Không
Không
Cao
Không
u6
Có
Không
Có
Rất cao
Có
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 DS U , C D
với U u1 , u2 ,..., un . Ma trận phân biệt của DS , ký hiệu M mi j nn , 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
c C c(ui ) c(u j )
mi j
if
D(ui ) D(u j ),
if
D(ui ) D(u j ) .
Đị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
DS U , C D , M mi j
nn
là ma trận phân biệt của DS và tập thuộc tính R C .
Nếu
1) R mi j với mọi mi j
2) Với mọi r R , R r 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 SRED C 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
DS U , C D , M mi j
nn
là ma trận phân biệt của DS. Thuộc tính c C đượ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
C c m
ij
với mọi mi j . 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à SCORE C . Theo
SCORE C
R.
RSRED C
[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
1
Tập rút gọn dựa trên
dương.
2
Phương pháp sử dụng miền
miền dương
Phương pháp sử dụng entropy
Tập rút gọn dựa trên
RP
RH
17
Shannon
3
entropy Shannon
Phương pháp sử dụng metric
Tập rút gọn dựa trên
RM
metric
4
Phương pháp sử dụng ma trận
Tập rút gọn dựa trên
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
Liang
entropy Liang
Phương pháp sử dụng độ đo
Tập rút gọn dựa trên
khác biệt của tri thức
7
đại số quan hệ
phân biệt.
6
Tập rút gọn dựa trên
phép toán trong đại số quan hệ
5
Phương pháp sử dụng các
độ khác biệt của tri
RF
RS
RE
RK
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 RP , RH , RM ,
RF , RS , RE , RK 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 ( RH ), tập rút gọn dựa trên metric ( RM ),
tập rút gọn dựa trên đại số quan hệ ( RF ) tương đương nhau.
18
- Tập rút gọn dựa trên ma trận phân biệt ( RS ), tập rút gọn dựa trên entropy
Liang ( RE ), tập rút gọn dựa trên độ khác biệt của tri thức ( RK ) 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 ( RP ) là tập con của tập rút gọn dựa trên
entropy Shannon ( RH ), nghĩa là: nếu RH là một tập rút gọn dựa trên entropy
Shannon thì tồn tại RP RH với RP 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 ( RE ) là tập con của tập rút gọn dựa trên
entropy Shannon ( RH ), nghĩa là: nếu RE là một tập rút gọn dựa trên entropy Liang
thì tồn tại RH RE với RH 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:
RP
RH RM RF
RS RE RK
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 RP .
Nhóm 2: Bao gồm các tập rút gọn RH , RM , RF
Nhóm 3: Bao gồm các tập rút gọn RS , RE , RK
Mối liên hệ giữa các tập rút gọn trong các nhóm như sau:
- Xem thêm -