i
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
PHẠM VĂN DƢƠNG
Nghiên cứu một số phƣơng pháp rút gọn
thuộc tính trên bảng quyết định không
đầy đủ và ứng dụng
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN
/>
ii
LỜI CẢM ƠN
Em xin chân thành cảm ơn và biết ơn sâu sắc đến GS.TS Vũ Đức Thi, Viện Công
nghệ thông tin – Đại học Quốc gia Hà Nội. Người đã tận tình hướng dẫn và giúp đỡ em
hoàn thành luận văn này.
Em xin chân thành cảm ơn các Thầy ở Viện Công nghệ thông tin đã dạy bảo, giúp
đỡ và truyền đạt kiến thức cho em trong suốt khóa học và quá trình em làm luận văn.
Em xin chân thành cảm ơn các Thầy, các Cô ở trường Đại học Công nghệ thông
tin và truyền thông Thái Nguyên đã tận tình dạy bảo, động viên, giúp đỡ và tạo điều kiện
1.3.4. Luật quyết định của bảng quyết định không đầy đủ và các độ đo cổ điển ....... 22
1.3.5. Các độ đo đánh giá hiệu năng tập luật và các tính chất .................................... 25
Số hóa bởi Trung tâm Học liệu - ĐHTN
/>
v
1.3.6. 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 ................................................................................................................... 27
Chƣơng 2. PHƢƠNG PHÁP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG
ĐẦY ĐỦ .................................................................................................................... 31
2.1. Mở đầu ........................................................................................................... 31
2.2. Entropy Liang mở rộng trong hệ thông tin không đầy đủ và các tính chất 31
2.2.1. Entropy Liang mở rộng của tập thuộc tính ....................................................... 32
2.2.2. Entropy Liang mở rộng có điều kiện ................................................................ 33
2.2.3. Một số tính chất của entropy Liang mở rộng .................................................... 34
............................................................................. 37
2.4. Thuật toán rút gọn thuộc tính ........................................................................ 42
Chƣơng 3: XÂY DỰNG CHƢƠNG TRÌNH THỰC NGHIỆM.................................... 45
3.1 Cấu trúc lớp chƣơng trình............................................................................... 45
3.2. Thiết kế phần mềm thực nghiệm .................................................................... 47
3.2.1. Yêu cầu hệ thống .............................................................................................. 47
3.2.2. Dữ liệu thử nghiệm ........................................................................................... 47
3.2.3. Chuẩn bị dữ liệu ................................................................................................ 47
3.2.4. Một số giao diện chương trình .......................................................................... 49
3.2.5. Kết quả thực nghiệm ......................................................................................... 51
................................................................................................................ 52
TÀI LIỆU THAM KHẢO........................................................................................... 53
Decision Table
Bảng quyết định đầy đủ
Complete Decision Table
Bảng quyết định không đầy đủ
Incomplete Decision Table
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
U , A,V , f
Diễn giải
Hệ thông tin, hệ thông tin đầy đủ
IIS
U , A,V , f
Hệ thông tin không đầy đủ
DS
U,C
Bảng quyết định, bảng quyết định đầy đủ
IDS
U,C
D, V , f
D, V , f
Bảng quyết định không đầy đủ
U
Số đối tượng
Lớp dung sai của đối tượng u trên quan hệ SIM B
U/B
U / SIM B
Phân hoạch của U sinh bởi tập thuộc tính B .
Phủ của U sinh bởi tập thuộc tính B .
COVER U
Họ tất cả các phủ của U.
B
(u )
Hàm quyết định suy rộng của đối tượng u đối với B .
BX
B xấp xỉ dưới của X
BX
BN B X
B xấp xỉ trên của X
B - miền biên của X
Tập lõi dựa trên entropy Liang có điều kiện
Số hóa bởi Trung tâm Học liệu - ĐHTN
/>
viii
MCORE C
Tập lõi dựa trên metric
E P
Entropy Liang của tập thuộc tính P
E (Q P)
Entropy Liang có điều kiện của Q khi đã biết P
IE P
Entropy Liang mở rộng của tập thuộc tính P trong hệ
thông tin không đầy đủ
Entropy Liang mở rộng có điều kiện của Q khi đã biết
P trong hệ thông tin không đầy đủ.
IE (Q P)
K P
Số hóa bởi Trung tâm Học liệu - ĐHTN
/>
x
DANH SÁCH HÌNH
Hình 1.1. Mối liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ ................. 20
Hình 3.1: Giao diện lớp MaxtrixDiscern............................................................................ 45
Hình 3.2: Giao diện lớp SqlExecute ................................................................................... 45
Hình 3.3: Giao diện lớp ImportData .................................................................................. 46
Hình 3.4: Giao diện lớp MainForm .................................................................................... 46
Hình 3.5. Dữ liệu adult-stretch gốc .................................................................................... 48
Hình 3.6. Dữ liệu adult-stretch sau khi chuyển đổi ............................................................ 49
Hình 3.7. Giao diện chọn tệp dữ liệu ................................................................................. 50
Hình 3.8. Kết quả thử nghiệm với bộ dữ liệu adult-stretch ................................................ 50
Hình 3.9. Lưu kết quả rút gọn thành dạng tệp .................................................................... 51
Số hóa bởi Trung tâm Học liệu - ĐHTN
/>
1
MỞ ĐẦU
Những năm trở lại đây, chúng ta đã chứng kiến sự phát triển mạnh
mẽ và sôi động của lĩnh vực nghiên cứu về rút gọn thuộc tính sử dụng lý
thuyết tập thô. Trong xu thế đó, nhiều nhóm nhà khoa học trên thế giới quan
tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định.
Các phương pháp chính là: Phương pháp dựa trên miền dương, phương
- Đây là phương pháp được nhiều nhà khoa học nghiên cứu và đã có
đóng góp trong thực tiễn.
- Có thể coi luận văn là một tài liệu tham khảo khá đầy đủ, rõ ràng về
các kiến thức cơ bản trong
bảng quyết định
không đầy đủ.
Bố cục của luận văn: Gồm phần mở đầu và 3 chương nội dung, phần
kết luận, danh mục tài liệu tham khảo và phụ lục.
Chƣơng 1: Trình bày các khái niệm cơ bản về bảng quyết định đầy
đủ, bảng quyết định không đầy đủ, mô hình tập thô truyền thống, mô hình
tập thô dung sai, trình bày một số phương pháp rút gọn thuộc tính trong
bảng quyết định đầy đủ.
Chƣơng 2: Trình bày phương pháp rút gọn trên
.
Chƣơng 3: Chương trình thực nghiệm trình bày các nội dung: Mô tả
dữ liệu, xây dựng chương trình, và kết quả thực nghiệm của thuật toán.
Cuối cùng, phần kết luận nêu những đóng góp của luận văn và hướng
phát triển của luận văn.
3
Chƣơng 1: NHỮNG KHÁI NIỆM CƠ BẢN VỀ CÁC PHƢƠNG PHÁP
RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH
1.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống.
1.1.1. Hệ thông tin đầy đủ
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
tượng, thì ta viết B u
B v nếu bi u
Xét hệ thông tin IS
bi v với mọi i 1,..., k .
U , A,V , f . 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
U / P U / Q ), khi và chỉ khi
u U, u
u Q.
P
2) Phân hoạch U / P mịn hơn phân hoạch U / Q (viết U / P U / Q ) khi
và chỉ khi u U , u
P
u Q.
Tính chất 1.1 [10] Xét hệ thông tin IS
U , A,V , f
và P, Q
A.
1) Nếu P Q thì U / Q U / P , mỗi lớp của U / P là một lớp hoặc hợp
của một số lớp thuộc U / Q .
2) Với mọi u U ta có u
P Q
B
X , BX
u U u
B
X
.
5
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
BNB X
BX : B-miền biên của X , U
BX
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ể
Rõ ràng POS B ( D ) là tập tất cả các đối tượng u sao cho với mọi v U
mà
u B
POS B ( D)
ta
v B
u U u
đều
u
B
D
có
u D
v D .
Nói
cách
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
Không
Ta có: U / {Đau đầu} =
u1 , u2 , u3 , u4 , u5 , u6 , u7 , u8
U / {Thân nhiệt} =
U / {Cảm cúm} =
u1 , u4 , u2 , u5 , u7 , u3 , u6 , u8
u1 , u4 , u5 , u8 , u2 , u3 , u6 , u7
U / {Đau đầu, Cảm cúm} =
u1 , u2 , u3 , u4 , u5 , u8 , u6 , u7
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 đó:
BX
u2 , u3 và BX
tập hợp BN B X
U/D
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
4) Tập X là B-không xác định hoàn toàn nếu BX
và BX U .
và BX U .
7
1.1.3. Bảng quyết định đầy đủ.
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 , f
với C D
Xét bảng quyết định DS
.
1.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
8
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.3. [11] (Tập lõi dựa trên miền dương) Cho bảng quyết
định DS
U,C
D,V , f . 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 ;
R.
R PRED C
Định nghĩa 1.5. Cho bảng quyết định DS
U,C
D, V , f
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.6. Cho bảng quyết định DS
nói rằng a là thuộc tính dư thừa của DS nếu a C
U,C
D, V , f
và a C . Ta
R.
u2
Có
Có
Có
Cao
Có
u3
Có
Có
Có
Rất cao
Có
u4
Có
Không
{Đ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}).
1.1.5. Ma trận phân biệt
Ma trận phân biệt do Andrzej Skowron và các cộng sự [4] đề 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
M
mi j
n n
D, V , f
với U
u1 , u2 ,..., un . Ma trận phân biệt của DS , 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
mi j
n n
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.8. [4, 6] (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, V , f , M
mi j
n n
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. Mỗi thuộc
tính a A xác định một ánh xạ: a : U
tính a A .
Va với Va là tập giá trị của thuộc
11
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 Nếu B
A là một tập con các thuộc tính thì ta ký hiệu bộ
b1 , b2 ,..., bk
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 .
Với hệ thông tin IS
U , A , nếu tồn tại u U và a
A sao cho a u
chứa giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy
phản xạ, đối xứng nhưng không có tính bắc cầu. SIM P là một quan hệ dung
sai (tolerance relation), hay quan hệ tương tự (similarity relation) trên U. Theo
[7], SIM P
a P SIM
a .
Gọi S P u là tập v U u, v
SIM P . S P u
là tập lớn nhất các đối
tượng không có khả năng phân biệt được với u trên tập thuộc tính P, còn gọi
là một lớp dung sai hay một hạt thông tin. Ký hiệu tập tất cả các lớp dung sai
sinh bởi quan hệ SIM(P) trên U là U / SIM P , khi đó các lớp dung sai trong
U / SIM P không phải là một phân hoạch của U mà hình thành một phủ của
U vì chúng có thể giao nhau và u U S P u
U sinh bởi các tập con thuộc tính P
U . Ký hiệu tập tất cả các phủ của
A là COVER U .
12
Trên COVER U ta định nghĩa một quan hệ thứ tự bộ phận COVER U ,
SA u SA u
u ,u U
SA u SA u
U, u U .
.
SQ u
phần tử nhỏ nhất gọi là phủ rời rạc
và phần tử lớn nhất gọi là phủ một khối
Tính chất 1.3. [7] Cho hệ thông tin không đầy đủ IIS
1) Nếu P Q
A thì SQ u
2) Nếu P Q
A thì U / SIM Q U / SIM P .
3) Nếu P, Q
A thì S P
Q
X SP u
X
SP u u U
13
Với các tập xấp xỉ nêu trên, ta gọi P-miền biên của X là tập
BNP X
PX
PX , và P-miền ngoài của X là tập U
PX .
Ví dụ 1.3. Bảng 1.3 biểu diễn thông tin về các xe hơi là hệ thông tin
không đầy đủ IIS
U, A
với U {u1 , u2 , u3 , u4 , u5 , u6 } , A {a1 , a2 , a3 , a4 } với a1
(Đơn giá), a2 (Km đã đi), a3 (Kích thước), a4 (Tốc độ tối đa).
Bảng 1.3. Bảng thông tin về các xe hơi
Tốc độ tối
đa
Cao
u4
Cao
*
Đầy đủ
Cao
u5
*
*
Đầy đủ
Cao
u6
Thấp
Cao
Đầy đủ
X
{u1 , u2 , u4 , u6 } ,
khi
đó
PX
u1 , u2
và
14
1.2.2. Mô hình tập thô dung sai
Trong phần này, tác giả tóm tắt một số khái niệm cơ bản về mô hình tập
thô dung sai do Marzena Kryszkiewicz [7] đề xuất và một số kết quả nghiên
cứu về mối liên hệ giữa các tập rút gọn của bảng quyết định không đầy đủ.
Với mỗi tập con thuộc tính P
A , ta định nghĩa một quan hệ nhị phân trên
U như sau:
SIM P
u, v
thuộc tính P, còn được gọi là một lớp dung sai hay một hạt thông tin. Rõ ràng
các lớp dung sai trong U / SIM P không phải là một phân hoạch của U mà
hình thành một phủ của U vì chúng có thể giao nhau, nghĩa là S P u
mọi u U và u U S P u
Với
B
A,
X
BX
u U SB u
BX
u U SB u
BNP X
PX
X
U.
U,
B-xấp
BX
X U/ d
Cho bảng quyết định không đầy đủ IDS
B
|
(u )
A
U, A
d
. Với B
A và u U ,
f d v v SB (u) được gọi là hàm quyết định suy rộng của IDS. Nếu
(u ) | 1 với mọi u U thì IDS là nhất quán, trái lại IDS là không nhất
15
quán. Theo định nghĩa miền dương, IDS nhất quán khi và chỉ khi
R , tồn tại u U sao cho
R'
u
A
u
thì R được gọi là một tập rút gọn của IDS dựa trên hàm quyết định suy rộng.
Zuqiang Meng và các cộng sự [14] đưa ra khái niệm về tập rút gọn dựa trên
miền dương.
Định nghĩa 1.11. [14] Cho bảng quyết định không đầy đủ
IDS
U, A
d . Nếu R
(1) POS R d
(2) R'
A thỏa mãn:
POS A d
R , POS R'
d
Copyright: Tài liệu đại học ©