Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô
1
ĐẠ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
TÓM TẮT LUẬN VĂN THẠC SĨ
CÔNG NGHỆ THÔNG TIN
Hà Nội - 2014
2
MỤC LỤC
MỤC LỤC
MỞ ĐẦU
Chương 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ
1.1. Hệ thông tin
1.2. Bảng quyết định
1.3. Quan hệ không phân biệt được
1.4. Các tập xấp xỉ
1.5. Tập rút gọn và tập lõi
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
2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định
2.2. Phương pháp rút gọn thuộc tính sử dụng entropy Shannon
2.2.1. Entropy Shannon trên bảng quyết định
2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon
2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon
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
2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định
2.3.1. 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
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
Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ
3.1. Bài toán
3
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
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
3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế
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
3.4.2. Thực hiện thuật toán sinh luật quyết định
KẾT LUẬN
TÀI LIỆU THAM KHẢO
4
MỞ ĐẦU
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ó.
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.
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ô”.
Đố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ề 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
5
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.
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.
1.2. 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à DS U , C D,V , f với C D .
1.3. Quan hệ không phân biệt được
Xét hệ thông tin IS U , A,V , f , P A , quan hệ không
phân biệt được trên U theo P, ký hiệu là IND P , được định nghĩa
như sau:
IND P u, v U U a P, u a v a .
Khi đó 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
6
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 .
1.4. Các tập xấp xỉ
Cho hệ thông tin IS U , A,V , f
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 .
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 đương của phân hoạch 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ần 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ó khả năng được phân loại
vào X dựa vào tập thuộc tính B.
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.
7
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.
2.2. Phương pháp rút gọn thuộc tính sử dụng entropy Shannon
2.2.1. Entropy Shannon trên bảng quyết định
Định nghĩa 2.2. ([25]) Cho bảng quyết định DS U , C D,V , f .
Giả sử U / C {C1, C2 ,...., Cm }, U / D {D1 , D2 ,..., Dn } . Entropy
Shannon có điều kiện của D khi đã biết C được định nghĩa bởi
m
H D C
i 1
Ci
U
n
j 1
Ci D j
Ci
log 2
Ci D j
Ci
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 DS U ,C D ,V , f ,
thuộc tính a C đượ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 H D C H D C a ; 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 DS được gọi
là tập lõi dựa trên entropy Shannon có điều kiện và ký hiệu là
HCORE C .
8
Ví dụ 2.1. Xét bảng quyết định DS U , C D,V , f
với
U u1 , u2 , u3 , u4 , u5 , u6 , C a1 , a2 , a3 và D d cho ở Bảng
2.1.
Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1
U
a1
a2
a3
d
u1
0
1
1
0
u2
0
1
1
1
u3
0
1
0
0
u4
0
1
0
1
u5
1
0
0
1
u6
1
0
1
1
Rõ ràng DS không nhất quán vì u1 C u2 C nhưng
u1 d u2 d . Ta có
U / C u1 , u2 , u3 , u4 , u5 , u6 ,U / D u1 , u3 , u2 , u4 , u5 , u6
U / C a3 U / a1 , a2 u1 , u2 , u3 , u4 , u5 , u6
1 1
1
1
1
4 2
H D | C 2. log 2 2. log 2 *2
6 2
2
2
2
6 3
9
1 2
2
2 2 1 2
2
H D | C a3 H D | a1 , a2 4* *log 2 4* log 2 2* *log 2
6 4
4
4 4 6 2
2
2
3
2
H D C a3 H D a1 , a2 H D C nên a3 là dư
3
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 DS U , C D, V , f
và tập thuộc tính R C . Nếu
1) H D R H D C
2) r R, H ( D R r ) H ( D C )
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 HRED C là họ tất cả các tập rút gọn Entropy
Shannon. Theo [21], HCORE C
R.
RHRED C
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
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 DS U , C D,V , f .
Output:
Method:
Tập lõi HCORE C .
10
HCORE C ;
1.
2. Tính H ( D | C ) ;
3. For each a C
4.
Begin
5.
Tính H D | C a ;
6.
If H D | C a H D | C then
HCORE C : HCORE C a;
7.
End;
8. Return HCORE C ;
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 U / C , độ phức tạp là
O C U . Do đó, độ phức tạp để tính H ( D | C ) là O C U . 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
2
thứ 7 là O C U
2
và độ phức tạp của Thuật toán 2.1 là
O C U .
Thuật toán 2.2. Tính phân hoạch U / R a khi biết U / R
Input: Phân hoạch U / R R1, R2 ,..., Rk .
Output:
Method:
1.
TMP ;
Phân hoạch U / R a
11
2. For each Ri U / R do
3.
Begin
4.
Tính phân hoạch Ri / a ;
5.
TMP TMP Ri / a ;
6.
End;
7. Return (TMP);
Sử dụng thuật toán trong [14] để tính phân hoạch Ri / a với
độ phức tạp O Ri
thì độ phức tạp của Thuật toán 2.2 là
k
O R O U .
i 1
i
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
R HCORE C , 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,
R C, a C R
Output:
1.
Một tập rút gọn R.
Tìm tập lõi HCORE C theo Thuật toán 2.1;
V,
f),
12
2.
R HCORE C ;
// Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất
3.
4.
Begin
For each a C R
5.
6.
Begin
Tính H D | R a
7.
8.
While H D R H D C do
Tính
SIGR a H D R H D R a ;
9.
End
10.
am C R
Chọn
sao
cho
SIGR am Max SIGR a ;
aC R
11.
R R am ;
12.
Tính H D R
13.
End;
R* R HCORE C ;
14. For each a R *
15.
16.
17.
Begin
Tính H D | R a
If H D R a H D C then R R a ;
13
18.
End
19. Return R ;
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 H D R H D C .
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à
r R, H ( D R r) H ( D C ) .
Theo Định nghĩa 2.2, R là tập rút gọn dựa trên entropy
Shannon.
Độ 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)
| Ri a D j | | Ri a D j |
1 n | Ri D j | | Ri D j |
log2
| Ri a |
log 2
| Ri |
| Ri |
| Ri |
| Ri a |
| Ri a |
i 1 | U i | j 1
m
SIGR a
để tính SIGR a , ta chỉ cần tính phân hoạch U / R a và phân
hoạch U / R đã được tính ở bước trước. Từ Thuật toán 2.1, độ phức
tạp thời gian để tính U / R a khi biết U / R là O U
nên độ
phức tạp thời gian để tính tất cả các SIGR a là
C C 1 ... 1 * U C * C 1 / 2 * U O C
2
Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất
. Vòng lặp For
là C C 1 ... 1 C * C 1 / 2 O C
2
tại dòng
U
14
lệnh 17 thực hiện R* lần, mỗi lần ta phải tính H D | R với độ phức tạp
thời gian O R U . Do đó, độ phức tạp thời gian của dòng lệnh 17 là
O R* R U . Vì vậy, độ phức tạp thời gian của thuật toán là
2
O C U .
Ví dụ 2.4. Xét bảng quyết định DS U , C D,V , f
2.2.
Từ
Ví
dụ
2.2.
cho ở Ví dụ
ta
U / C u1 , u2 , u3 , u4 , u5 , u6 , u7 ,U / D u1 , u3 , u2 , u4 , u5 , u6 , u7
có
U / C a3 U / a1 , a2 u1 , u2 , u3 , u4 , u5 , u6 , u7
1 2
H D | C 8. log 2
7 4
2 4
4 7
R HCORE C a3 , U / a3 u1 , u2 , u7 , u3 , u4 , u5 , u6
1
1
2
3 2
H D | a3 3log 2 2log 2 2 3log 2 3 log 2 3
7
3
3
4 7
Do đó H D | a3 H D | C thực hiện vòng lặp While.
Xét thuộc tính a1 C a3 . Theo tính toán ở Ví dụ 2.2:
H D | a1 , a3 H D | C
4
7
SIGa3 a1 H D | a3 H D | a1 , a3
,
2
4 2
3 log2 3 1 log2 3
7
7 7
Xét thuộc tính a2 C a3 . Tính toán tương tự ta được:
SIGa3 a2 SIGa3 a1
2
1 log 2 3 .
7
15
Do a1 và a2 có độ quan trọng như nhau nên chọn bất kỳ a1
hoặc a2 , giả sử chọn a1 , khi đó và R a1 , a3 và theo tính toán ở
Ví dụ 2.2: H D | a1 , a3 H D | C
.Thực hiện vòng lặp For. Xét R* R HCORE (C ) a1 và
R a1 a3 Theo tính toán ở trên, H D | a3 H D | C . Do đó
thuật toán kết thúc và R a1 , a3 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
2.3.1. Luật quyết định
Cho
bảng
quyết
định
DS U ,C D ,
giả
sử
U / C {X1 , X 2 ,..., X m} và U / D {Y1, Y2 ,..., Yn} là các phân hoạch được
sinh bởi C, D. Với X i U / C , Y j U / D và X i Yj , ký hiệu
des X i và des Y j lần lượt là các mô tả của các lớp tương đương X i
và Y j trong bảng quyết định DS.
Một luật quyết định đơn có dạng Zij : des X i des Y j .
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
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
U / C {X1 , X 2 ,..., X m}
và
định
DS U ,C D ,
U / D {Y1, Y2 ,..., Yn } . Với
giả
sử
X i U / C ,
Y j U / D và X i Yj . Thuật toán RuleExtract hiển thị các luật
16
với độ
s Z X Y
quyết định dạng Zij : des X i des Y j
Zij X i Yj / X i và đỗ hỗ trợ
ij
i
chắc chắn
/ U tương
j
ứng.
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ợ s .
1. Tính phân hoạch U / C ;
2. For each X i U / C
3. Begin
4.
Tính X i / D ;
5.
For each Y j X i / D
6.
Begin
7.
Sinh luật Zij : des X i des Y j
8.
Tính Zij Y j / X i ;
9.
Tính s Zij Y j / U ;
10.
Hiển thị luật Z ij , độ chắc chắn Zij , độ hỗ
trợ s Zij ;
11.
End;
12. End;
13. Return.
17
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.
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
Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC
STT Bộ số liệu
U
C
R
t
Tập rút
gọn
1
Lungcancer.data
32
56
4
0.78
{3, 4, 9,
43}
2
Zoo.data
101
17
1
0.505
{1}
3
Liver-disorders
(bupa.data)
345
6
3
0.677
{1, 2, 5}
4
Soybean
Large.data
307
35
4
3.115
{1, 2, 8,
11}
5
Flag.data
194
29
1
0.682
{1}
6
Credit
Approval
690
15
7
29.703
{1, 2, 3,
4, 5, 6,
–
18
8}
7
Anneal.data
798
38
7
49.336
{3, 5, 8,
12, 33,
34, 35}
8
Abalone.data
4177
8
3
256.12
{2, 5, 6}
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
Thử nghiệm Thuật toán RuleExtract sinh luật quyết định (luật
phân lớp) với bộ số liệu Soybean - small.data.
Bảng 3.4. Các luật phân lớp trên bảng quyết định rút gọn
Các luật trên bảng quyết
định rút gọn
s
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
STT
3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế
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ó
19
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, 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
3.4.2. Thực hiện thuật toán sinh luật quyết định
20
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à làm phong phú thêm các phương pháp rút gọn
thuộc tính sử dụng entropy.
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.
- Xem thêm -