- Trang Chủ
- Kĩ thuật Viễn thông
- Về phương pháp rút gọn thuộc tính trong bảng quyết định với miền trị thuộc tính nhận giá trị số theo tiếp cận tập thô mờ
Xem mẫu
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
Về phƣơng pháp rút gọn thuộc tính trong bảng
quyết định với miền trị thuộc tính nhận giá trị
số theo tiếp cận tập thô mờ
Fuzzy Rough Set based Attribute Reduction in Numeric Domain
Decision Tables
Nguyễn Văn Thiện, Nguyễn Long Giang, Nguyễn Nhƣ Sơn
Abstract: Attributes reduction based on rough set tươ g ứ g 39.5 độ v 39.6 độ được rời rạ hó
is interesting research area. However, the attributes th h một gi t ị “Nhiệt độ cao”. T ê ảng quyết định
reduction algorithms based on rough set is done on mới, h i đối tượng x v y ó gi t ị bằ g h u t ê
the discrete domain decision tables (that is applied thuộ t h "Nhiệt độ cơ thể” v khô g ả t được
discretization methods). In recent years, some sự kh h u 0.1 độ t ê ảng quyết đị h đầu.
researchs on fuzzy rough set based directly attribute D đó, phươ g ph p ời rạ hó dữ liệu khô g ảo
reduction in numeric domain decision tables have t “ gữ ghĩ ” ủa dữ liệu gố v ó thể m giảm
been studied. This paper proposes fuzzy rough set độ h h x phâ ớp t ê dữ liệu gố . Để giải quyết
based directly attribute reduction method in numeric i t út gọn thuộ t h t ực tiếp t ê ảng
domain decision tables. The experiment results quyết đị h ó miền trị thuộ t h hậ gi t ị số, iê
showed that the fuzzy rough set method has better tục nhằm khắc phụ hượ điểm t ê , t g mấy ăm
classification accuracy than rough set theory. gầ đây ô g t ì h ghiê ứu đề xuất hướng tiếp
cận mới sử dụ g ý thuyết tập thô mờ
Keywords: rough set, fuzzy rough set, decision
table, fuzzy similarity relation, attribute reduction, Lý thuyết tập thô mờ (Fuzzy Rough Set) do D.
reduct. Du is v ộng sự [4, 5] đề xuất mở ra một hướng
ghiê ứu mới về út gọn thuộ t h t ê ảng
I. GIỚI THIỆU quyết định mờ v ảng quyết đị h ó miền trị
Rút gọn thuộ t h i t u t ọ g trong thuộ t h nhậ gi t ị số, iê tục. Lý thuyết tập thô
ước tiền xử ý số liệu với mụ tiêu ại bỏ mờ sự kết hợp củ ý thuyết tập thô [13] v ý thuyết
thuộ t h dư thừa nhằm â g t h hiệu quả của tập mờ [11] nhằm xấp xỉ tập mờ dự t ê một
thuật t kh i ph dữ liệu. Lý thuyết tập thô [13] quan hệ tươ g tự (simi ity e ti ) đượ x định
ô g ụ hiệu quả giải quyết i t út gọn thuộc t ê miề gi t ị thuộ t h. T g ý thuyết tập thô,
t h t g ảng quyết đị h v được cộ g đồ g ghiê h i đối tượ g tươ g đươ g t ê tập thuộ t h R,
cứu về tập thô thực hiệ âu y. Để thực hiệ h y độ tươ g tự 1, ếu gi t ị thuộ t h ủ hú g
phươ g ph p út gọn thuộ t h the tiếp cận tập thô, bằ g h u t ê tất cả thuộ t h t g R. Ngược
thuộ t h ó miền gi t ị số, iê tục cầ được rời lại, hú g khô g tươ g đươ g, h y độ tươ g tự 0.
rạ hó . Tuy hiê , phươ g ph p ời rạ hó dữ T g ý thuyết tập thô mờ, quan hệ tươ g tự thay thế
liệu khô g ả t được sự kh h u đầu giữa quan hệ tươ g đươ g hằm x đị h độ tươ g tự của
gi t ị thuộ t h. V dụ, với thuộ t h “Nhiệt độ h i đối tượ g. Độ tươ g tự một gi t ị nằm trong
cơ thể”, giả sử h i đối tượng x v y ó hiệt độ ơ thể khoảng [0, 1] cho thấy t h gầ h u, h y t h tươ g
- 40 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
tự, củ h i đối tượ g. C ghiê ứu iê u đến T g i y, hú g tôi đề xuất thuật t
út gọn thuộ t h the tiếp cận tập thô mờ tập trung heu isti út gọn thuộ t h t g ảng quyết đị h ó
v h i hướ g h h: hướng thứ nhất sử dụng tập miền trị thuộ t h nhậ gi t ị số sử dụ g độ phụ
thô mờ để giải quyết i t út gọn thuộ t h t ê thuộc mờ của thuộ t h t g tập thô mờ. Thuật t
ảng quyết định mờ (bảng quyết định với gi t ị đề xuất tìm một tập út gọn tốt nhất the tiêu huẩn
thuộ t h tập mờ) t ước khi thực hiệ thuật chất ượng phâ ớp (độ quan trọng của thuộ t h), d
t t h ọc hệ luật mờ với ô g ố điể hì h đó hiệu quả hơ ô g ố trong [1, 2, 3, 21, 22, 23,
[6, 7, 8, 15, 18, 19, 20, 24]; hướng thứ hai giải quyết 25]. Do sử dụ g độ phụ thuộc mờ củ thuộ t h
i t út gọn thuộ t h t ực tiếp t ê ảng ê thuật t đề xuất ó khối ượ g t h t hỏ hơ
quyết đị h ó miền trị thuộ t h nhậ gi t ị số, đây thuật t t g [8, 17] sử dụ g ô g thức entropy
hướ g ghiê ứu củ i y. Shannon mờ. Kết quả thử nghiệm t ê một số bộ số
The hướng tiếp cậ út gọn thuộ t h t ực tiếp liệu cho thấy, phươ g ph p đề xuất ó độ h h x
tê ảng quyết đị h ó miền trị thuộ t h nhận phâ ớp tốt hơ s với phươ g ph p sử dụ g độ phụ
gi t ị số, t ước hết một quan hệ tươ g tự đượ định thuộc của thuộ t h the tiếp cậ ý thuyết tập thô
ghĩ t ê miề gi t ị thuộ t h. Tiếp the , m truyền thố g. Hơ ữ , phươ g ph p đề xuất ó độ
trận quan hệ đượ xây dựng. Ma trận quan hệ cho h h x phâ ớp tốt hơ phươ g ph p dự t ê
phép x định gi t ị h m thuộc củ đối tượ g đối entropy Shannon mờ trong [8, 17]. Cấu t ú i
với mỗi lớp tươ g tự mờ. Từ đó, h m thuộc củ hư s u. Phầ 2 t ì h y một số kh i iệm ơ ản
tập xấp xỉ dưới mờ, xấp xỉ t ê mờ, miề dươ g mờ t g ý thuyết tập thô mờ. Phầ 3 t ì h y phươ g
đượ t h dự v t tử xấp xỉ t g ý thuyết ph p út gọn thuộ t h sử dụ g độ phụ thuộc mờ của
tập thô mờ [4, 5]. T ê ơ sở đó, phươ g ph p út thuộ t h the tiếp cận tập thô mờ. Phần 4 t ì h y
gọn thuộ t h đượ xây dựng dự t ê ền tảng mở kết quả thử nghiệm. Cuối ù g kết luậ v hướng
rộng phươ g ph p út gọn thuộ t h the tiếp cận ph t t iển tiếp theo
tập thô t uyền thố g. Đó g góp u t ọng về hướng
II. CÁC KHÁI NIỆM CƠ BẢN
ghiê ứu y phải kể đế ô g t ì h [1, 2, 3, 21,
22, 23, 25]. T g ô g t ì h y, t giả xây Phầ y t ì h y một số kh i iệm ơ ả t g
dựng ma trận phâ iệt mờ dự t ê m t ận quan hệ ý thuyết tập thô t uyề thố g ủ P w k [13] v ý
v đề xuất thuật t tìm tất cả tập út gọn bằng thuyết tập thô mờ d D. Du is v ộ g sự [4, 5]
h mở rộ g phươ g ph p út gọn thuộ t h dự t ê đề xuất.
ma trậ phâ iệt t g ý thuyết tập thô t uyền thống. Mô hì h tập thô t uyền thố g d P w k [13] đề
Tuy hiê , t giả hư ô g ố thuật t xuất dự t ê u hệ tươ g đươ g để xấp xỉ tập hợp.
heuristic tìm một tập út gọn tốt nhất dự t ê tiêu Xét ảng quyết định DS U , C D , Mỗi tập thuộc
chuẩn chất ượ g phâ ớp h y độ quan trọng của t h PC x định một quan hệ tươ g đươ g
thuộ t h. T g ô g t ì h [8, 17], t giả xây
dự g phươ g ph p út gọn thuộ t h dự t ê
IND P u, v U U a P, a u a v . Nếu
entropy Shannon. C t giả t g [8, 17] ũ g mi h u, v IND P thì u v v khô g phâ iệt được nhau
chứng bằng thực nghiệm rằ g, phươ g ph p út gọn bởi thuộ t h t g P. Ký hiệu lớp tươ g đươ g
thuộ t h the tiếp cận tập thô mờ ó độ h h x chứ đối tượng u u P , khi đó
phâ ớp tốt hơ phươ g ph p út gọn theo tiếp cậ ý
thuyết tập thô t uyền thống (sau khi rời rạ hó dữ u P v U u, v IND P . Với X U , tập
liệu) t ê một số bộ dữ liệu thử nghiệm.
CX u U u C X v CX u U u C X tươ g
- 41 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
ứng gọi C-xấp xỉ dưới, C-xấp xỉ trên của X. Ta gọi với x y R x, y , khi đó tập mờ xấp xỉ dưới
R
tập POSC ( D) CX C-miền dương của D. Dễ R F v tập mờ xấp xỉ t ê R F đượ viết ại hư
X U / D
thấy POSC ( D) tập đối tượng trong U đượ phâ sau:
lớp đú g v ớp của U / D sử dụng tập thuộ t h C.
Độ phụ thuộc của tập thuộ t h C v tập thuộ t h D
yU
R F x inf max 1 x y , F y
R
(3)
t g ý thuyết tập thô t uyền thố g, ký hiệu C D ,
yU
R F x sup min x y , F y
R
(4)
đượ đị h ghĩ hư s u:
Cặp R F , R F đượ gọi tập thô mờ. Dễ thấy
POSC D
k C D ằ g một tập hợp (tập õ) ất kỳ X U ó thể xem
U
một tập mờ, h m thuộ X y 1 với y X v
với S ự ượ g ủ tập S. Nếu k =1 thì D phụ thuộ
X y 0 với y X . Mô hì h tập thô mờ ó thể xem
h t v C. Nếu 0 k 1 , D phụ thuộ ộ phậ
việ sử dụ g u hệ tươ g tự để xấp xỉ tập mờ
v C. Tiếp the , hú g tôi t ì h y kh i iệm t ê
(h ặ tập õ) ằ g tập mờ xấp xỉ dưới v tập mờ xấp
t g ý thuyết tập thô mờ t g [4, 5].
xỉ t ê .
T g mô hì h tập thô mờ, một u hệ tươ g tự
Ch ả g uyết đị h ó miề t ị thuộ t h hậ
(similarity relation) đượ sử dụ g th y thế u hệ
gi t ị số DS U , C D với U u1,..., un ,
tươ g đươ g để xấp xỉ tập mờ. Cho U tập
đối tượ g, một u hệ R đượ đị h ghĩ t ê U đượ C c1,..., cm . Giả sử một u hệ tươ g tự R ất kỳ
gọi u hệ tươ g tự ếu R thỏ mã t h hất: x đị h t ê miề gi t ị ủ thuộ t h điều kiệ
t h phả xạ ( ef exive) R x, x 1 , t h đối xứ g c C . T ký hiệu ck u hệ R x đị h t ê thuộ
(symetric) R x, y R y, x v t h ắ ầu sup-min t h điều kiệ ck C, k 1..m . Khi đó, kh i iệm miề
(sup-min transitive) R x, z min R x, y , R y, z ) với dươ g POSC D t g ý thuyết tập thô t uyề thố g
mọi x, y, z U . Qu hệ tươ g tự R x đị h một phâ đượ mở ộ g th h kh i iệm miề dươ g mờ ủ
h ạ h mờ t ê U, ký hiệu U / R x R x U , trong tập thuộ t h D đối với tập thuộ t h C dự t ê u
hệ R, ký hiệu POSC D . POSC D một tập mờ
đó x R một ớp tươ g đươ g mờ tươ g ứ g với đối
m h m thuộ ủ đối tượ g x U đượ đị h ghĩ
tượ g x, h m thuộ đượ x đị h ởi ô g thứ
như s u [18].
x y R x, y R x, y với mọi y U .
POS x sup C X x
R
D (5)
Giả sử F một tập mờ v R một u hệ tươ g C
X U / D
tự x đị h t ê U, khi đó tập mờ xấp xỉ dưới R F v Dự t ê kh i iệm miề dươ g mờ, độ phụ thuộ
tập mờ xấp xỉ t ê R F ủ F tập mờ v h m ủ tập thuộ t h điều kiệ C v tập thuộ t h uyết
đị h D dự t ê u hệ R đượ đị h ghĩ the tiếp
thuộ ủ đối tượ g x U đượ x đị h hư s u:
ậ tập thô mờ hư s u [18].
R F x inf max 1 R x, y , F y (1)
yU POS D x xU POS D x
C D
R F x sup min R x, y , F y
C C (6)
(2) U U
yU
The hướ g tiếp ậ út gọ thuộ t h t ự tiếp
tê ả g uyết đị h thuộ t h số, m t ậ u
- 42 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
hệ x đị h t ê thuộ t h ck m t ậ vuô g ấp n giả t g [8] ũ g xây dự g thuật t heu isti tìm
đượ đị h ghĩ hư s u [21] một tập út gọ tốt hất dự t ê ượ g thô g ti tă g
thêm mờ. T g ả h i ô g t ì h [8, 17], t giả
M ck mijck
nn đều hứ g mi h ằ g thự ghiệm ằ g út gọ thuộ
t h the tiếp ậ thô mờ ó độ h h x phâ ớp tốt
với mijc ck ui , u j , i 1..n, j 1..n . Ở đây, ck ui , u j
k
hơ út gọ thuộ t h the tiếp ậ ý thuyết tập thô
gi t ị ủ u hệ giữ hai đối tượ g ui v u j . Khi t uyề thố g. Tuy hiê , hượ điểm ủ h i phươ g
đó, m t ậ u hệ mờ x đị h t ê tập thuộ t h ph p y đều sử dụ g ô g thứ e t py Sh
điều kiệ C đượ đị h ghĩ [21] để xây dự g đị h ghĩ tập út gọ , d đó thời
gi thự hiệ kém hiệu uả d phải t h t iểu
M C mijC
nn thứ g it. T g i y, hú g tôi sử dụ g độ
phụ thuộ mờ ủ thuộ t h th y h độ đ e t py
k 1.. m
với mijC min mijc min mijc , mijc ,..., mijc
k 1 2 m
Sh để đị h ghĩ tập út gọ v xây dự g thuật
t heu isti tìm một tập út gọ tốt hất. Vì độ phụ
Dễ thấy ằ g, với phầ tử mijC ủ m tậ M C thuộ mờ ủ thuộ t h khô g phải t h t iểu
t ó mijC C ui , u j , i 1..n, j 1..n , với thứ g it ê hiệu uả hơ phươ g ph p dự
t ê e t py Sh t g [8, 17]. Chú g tôi ũ g
C ui , u j C ui , u j ui u j . Từ m t ậ
C
M C hứ g mi h ằ g thự ghiệm ằ g phươ g ph p đề
h phép x đị h đượ ớp tươ g đươ g mờ xuất ó độ h h x phâ ớp hơ phươ g
m C
m C
ph p dự t ê e t py Sh t g [8, 17].
ui C ...
i1 i1 thuộ phâ h ạ h mờ
u1 un Tươ g tự phươ g ph p út gọ thuộ t h t g ý
U / C ui C ui U . Khi đó, h m thuộ ủ tập thuyết tập thô t uyề thố g, phươ g ph p đề xuất
mờ xấp xỉ dưới, tập mờ xấp xỉ t ê , miề dươ g mờ ó gồm ướ : đị h ghĩ tập út gọ dự t ê độ phụ
thể đượ t h dự v ô g thứ (3), (4), (5) tươ g thuộ mờ ủ thuộ t h, đị h ghĩ độ u t ọ g ủ
ứ g v từ đó t h đượ độ phụ thuộ ủ tập thuộ t h thuộ t h đặ t ư g h hất ượ g phâ ớp ủ
điều kiệ C v tập thuộ t h uyết đị h D the ô g thuộ t h v xây dự g thuật t heu isti tìm tập út
thứ (6). gọ tốt hất dự t ê tiêu huẩ độ u t ọ g ủ
thuộ t h.
III. RÚT GỌN THUỘC TÍNH TRONG BẢNG Định nghĩa 1. Cho bảng quyết định DS U ,C D ó
QUYẾT ĐỊNH VỚI MIỀN TRỊ THUỘC TÍNH
miề t ị thuộ t h hậ gi t ị số , một u hệ tươ g tự
NHẬN GIÁ TRỊ SỐ
R đượ x đị h t ê miề gi t ị ủ thuộ t h. Với
Như đã t ì h y ở phầ I, t ê ớp i t út gọ P C , nếu
thuộ t h t ự tiếp t ê ả g uyết đị h với miề t ị
1) P ( D) C ( D)
thuộ t h hậ gi t ị số the hướ g tiếp ậ heuristic
sử dụ g tập thô mờ, t g ô g t ì h [17], t giả 2) p P, P p ( D) C ( D)
đã đị h ghĩ tập út gọ dự t ê e t py Sh
mờ v xây dự g thuật t heu isti tìm một tập út thì P một tập út gọ ủ C dự t ê độ phụ thuộ
gọ tốt hất dự t ê e t py Sh mờ. T g mờ ủ thuộ t h.
ô g t ì h [8], t giả đị h ghĩ tập út gọ dư Từ Đị h ghĩ 1, dễ thấy ằ g tập út gọ dự t ê
t ê độ đ ượ g thô g ti tă g thêm mờ (fuzzy độ phụ thuộ mờ ủ thuộ t h tươ g đươ g với tập
information gain). Lượ g thô g ti tă g thêm mờ út gọ dự t ê miề dươ g mờ, tập út gọ dự t ê
đượ xây dự g dự t ê e t py Sh mờ. C t
- 43 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
miề dươ g mờ mở ộ g tập út gọ dự t ê miề Ví dụ 1. Xét ả g uyết đị h ó miề gi t ị thuộ
dươ g ủ P w k the tiếp ậ ý thuyết tập thô mờ. t h số DS U , C d h ở Bả g 1 với
Định nghĩa 2. Cho bảng quyết định DS U , C D ó U u1 , u2 , u3 , u4 , u5 , u6 , C c1 , c2 , c3 , c4 , c5 , c6 .
miề gi t ị thuộ t h số v u hệ tươ g tự R x đị h
Bảng 1. Bảng quyết định mô tả Ví dụ 1
t ê miề gi t ị thuộ t h. Với B C , độ u t ọ g
mờ ủ thuộ t h b C B đối với tập thuộ t h B c1 c2 c3 c4 c5 c6 d
đượ đị h ghĩ : u1 0.8 0.2 0.6 0.4 1 0 No
SIGB b Bb D B D (7) u2 0.8 0.2 0 0.6 0.2 0.8 Yes
u3 0.6 0.4 0.8 0.2 0.6 0.4 No
Độ u t ọ g ủ thuộ t h đặ t ư g h hất
u4 0 0.4 0.6 0.4 0 1 Yes
ượ g phâ ớp ủ thuộ t h điều kiệ v thuộ t h
uyết đị h v đượ sử dụ g m tiêu huẩ ự họ u5 0 0.6 0.6 0.4 0 1 Yes
thuộ t h h thuật t heu isti tìm tập út gọ s u u6 0 0.6 0 1 0 1 No
đây.
Giả sử t ê miề gi t ị ủ thuộ t h ck C , quan
Thuật toán F_RSAR (Fuzzy Rough Set based
Attribute Reduction). Thuật t heu isti tìm một tập hệ tươ g tự ck đượ đị h ghĩ hư s u [8]
út gọ sử dụ g độ phụ thuộ mờ ủ thuộ t h. ck ui ck u j ck ui ck u j
1 4 * , 0.25 (8)
Đầu vào: Bả g uyết đị h gi t ị thuộ t h số ck (ui , u j ) max(ck ) min(ck ) max(ck ) min(ck )
DS U , C D , một u hệ tươ g tự R đượ x 0, otherwise
đị h t ê miề gi t ị thuộ t h. Với max ck , min ck tươ g ứ g gi t ị ớ
Đầu ra: Một tập út gọ tốt hất P . hất v gi t ị hỏ hất ủ miề gi t ị thuộ t h ck
1. P ; Áp dụ g ướ ủ Thuật t F_RSAR tìm một
2. D 0 ; tập út gọ ủ ả g uyết đị h. T ướ hết, t h
thuộ t h điều kiệ M c1 ,
3. T h m t ậ u hệ M C ; m t ậ u hệ t ê
4. T h C D ;
M c2 , M c3 , M c4 , M c5 , M c6 . Từ đó, t h m
5. While P D C D do tậ M C :
6. Begin
1 0 0 0 0 0
For c C P t h 0 0
7.
1 0 0 0
SIGP c Pc D P D ; 0 0 1 0 0 0
M (C )
8. Chọ cm C P sao cho 0 0 0 1 0 0
0 0
SIGP cm Max SIGP c ;
0 0 0 1
cC P
0 0 0 0 0 1
9. P P cm ;
T ó U / d u1 , u3 , u6 , u2 , u4 , u5 . Xét
10. T h P D ;
X u1 , u3 , u6 , xấp xỉ mờ dưới C X tập mờ với
11. End;
12. Return P; h m thuộ ủ x U t h ởi
1 3 6
Cu ,u ,u x inf max 1 x y , u ,u ,u y
yU C 1 3 6
- 44 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
Từ m t ậ M C t ó đó thuật t dừ g v P c1, c4 một tập út gọ tốt
hất ủ ả g uyết đị h DS.
1 0 0 0 0 0
u1 C Thuật t F_RSAR tìm đượ một tập út gọ ủ
u1 u2 u3 u4 u5 u6
ả g uyết đị h dự t ê độ u t ọ g ủ thuộ t h
D đó C u ,u ,u u1 inf 1,1,1,1,1,1 1 , tươ g (đặ t ư g h hất ượ g phâ ớp ủ thuộ t h)
1 3 6
ê hiệu uả hơ thuật t tìm tất ả tập út
tự t ó Cu ,u ,u u2 0 , Cu ,u ,u u3 1 ,
1 3 6 1 3 6 gọ the hướ g tiếp ậ m t ậ phâ iệt t g
Cu ,u ,u u4 0 , Cu ,u ,u u5 0 ,
1 3 6
ô g t ì h [1, 2, 3, 21, 22, 23, 25]. Thuật t
1 3 6
F_RSAR sử dụ g độ phụ thuộ ủ thuộ t h để tìm
Cu ,u ,u u6 1 ,
1 3 6
Cu ,u ,u u1 0 ,
2 4 5
tập út gọ , d đó ó khối ượ g t h t hỏ hơ
thuật t the hướ g tiếp ậ e t py Sh t g
Cu ,u ,u u2 1 , Cu ,u ,u u3 0 ,
2 4 5 2 4 5 [8, 17]. Dễ thấy ằ g, tập út gọ thu đượ ủ Thuật
Cu ,u ,u u4 1 Cu ,u ,u u5 1 , t F_RSAR ả t miề dươ g mờ. Phầ tiếp
the , hú g tôi tiế h h thử ghiệm phươ g ph p đề
2 4 5 2 4 5
Cu ,u ,u u6 0 .
2 4 5
xuất t ê một số ộ dữ iệu thử ghiệm để m õ h i
vấ đề s u: 1) T h hiệu uả ủ hướ g tiếp ậ tập
Từ đó, h m thuộ ủ đối tượ g đối với miề
thô mờ s với hướ g tiếp ậ tập thô t uyề thố g về
dươ g mờ POSC d :
độ h h x phâ ớp s u khi út gọ thuộ t h; 2)
POS d u1 sup Cu ,u ,u u1 , Cu ,u ,u u1 1 ,
C 1 3 6 2 4 5
T h hiệu uả ủ thuật t đề xuất với thuật t
t g ô g t ì h [8] về độ h h x phâ ớp.
POS d u2 1 , POS d u3 1 , POS d u4 1 ,
C C C
VI. KẾT QUẢ THỰC NGHIỆM
POS d u5 1 , POS d u6 1 . Từ đó: Chú g tôi họ 8 ộ dữ iệu mẫu từ ấy từ kh dữ
C C
C d 1 iệu UCI [26] ó miề t ị thuộ t h hậ gi t ị số h
ở Bả g 2 để tiế h h thử ghiệm. Môi t ườ g thử
Áp dụ g ướ ủ Thuật t F_RSAR t ó ghiệm m y t h PC với ấu hì h Pe tium du e
c
1
d 0.167 , d 0 , c2
c 3
d 0.167 , 2.13 GHz CPU, 1GB ộ hớ RAM, sử dụ g hệ điều
h h Wi d ws 7.
c d 0.5 , d 0.467 , c5
c d 0.467 .
4 6
Bảng 2. Bộ số liệu thử nghiệm
Chọ thuộ t h c4 ó độ u tọ g ớ hất v TT Bộ dữ liệu Số thuộc tính Số đối
P c4 . Thự hiệ vò g ặp Whi e. Xét thuộ điều kiện tƣợng
1 Ecoli 7 336
t h c1 t ó: 2 Ionosphere 34 351
3 Wdbc 30 569
SIGc c1 c ,c d c d 1 0.5 0.5 . Tươ g tự 4 Wpbc 33 198
4 4 1 4
5 Wine 13 178
SIGc c2 0.5 , SIGc c3 0 , SIGc c5 0.5 , 6 Glass 9 214
4 4 4
SIGc c6 0.5 . Khô g mất t h tổ g u t, họ
7 Magic04 10 19020
4 8 Page-blocks 10 5473
thuộ t h c1 ó độ u tọ g ớ hất v
T ướ hết, hú g tôi tiế h h thử ghiệm hằm
P c1, c4 . Khi đó t ó c ,c
1 4
d 1 d , do C
đ h gi độ h h x phâ ớp t ê ộ số iệu
- 45 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
mẫu s u khi thự hiệ thuật t F_RSAR v thuật Bảng 3. Kết quả thử nghiệm rút gọn thuộc tính theo tiếp
t út gọ thuộ t h sử dụ g độ phụ thuộ ủ cận tập thô và tập thô mờ
thuộ t h t g ý thuyết tập thô t uyề thố g (gọi tắt Rút gọn thuộc tính Rút gọn thuộc tính theo
thuật t RSAR). Để tiế h h thử ghiệm, hú g theo tiếp cận tập thô tiếp cận tập thô mờ
(RSAR) (F_RSAR)
tôi thự hiệ ô g việ s u:
S R Độ Độ R Độ Độ
Bộ số U C
- C i đặt thuật t ời ạ hó dữ iệu ằ g phươ g T chính chính chính chính
liệu
ph p e u -width [12], thuật t RSAR, thuật t T xác xác xác xác
phân phân phân phân
F_RSAR sử dụ g u hệ tươ g tự t g [8], thuật
lớp lớp lớp lớp
t phâ ớp SVM [9], C4.5 [10] ằ g ô g ụ J v . SVM C4.5 SVM C4.5
- Thự hiệ thuật t ời ạ hó equal-width v 1 Ecoli 336 7 50.851 0.819 7 0.865 0.855
thuật t RSAR để tìm tập út gọ the tiếp ậ tập 2 Ionos 351 3 10.814 0.802 15 0.937 0.915
phere 4 0
thô. 3 Wdbc 569 3 80.795 0.784 19 0.980 0.975
- Thự hiệ thuật t F_RSAR để tìm tập út gọ 0
t ự tiếp từ ả g uyết đị h đầu the tiếp ậ tập 4 Wpbc 198 3 70.718 0.704 19 0.825 0.818
3
thô mờ sử dụ g u hệ tươ g tự ở ô g thứ (8) 5 Wine 178 1 40.814 0.802 10 0.955 0.920
trong ô g t ì h [8] 3
- T ê ả g uyết đị h thu đượ ủ h i h tiếp 6 Glass 214 9 50.815 0.795 7 0.891 0.882
7 Magic 190 1 40.745 0.715 6 0.782 0.765
ậ , họ 2/3 đối tượ g đầu tiê để m tập huấ uyệ 04 20 0
(t i i g), 1/3 đối tượ g ò ại m tập kiểm t (test). 8 Page- 547 1 50.758 0.725 7 0.865 0.855
Thự hiệ thuật t SVM, C4.5 t ê tập huấ uyệ blocks 3 0
v đ h gi độ h h x phâ ớp t ê tập kiểm t .
Từ đó, đ h gi độ h h x phâ ớp ủ h i h Từ Bả g 3 v Hì h 1 t thấy, tập út gọ ủ
tiếp ậ . F_RSAR hiều thuộ t h hơ RSAR. Độ h h x
Bả g 3 kết uả thử ghiệm t ê 8 ộ số iệu phâ ớp s u khi út gọ thuộ t h the tiếp ậ tập
đượ họ với U số đối tượ g, C số thuộ t h thô mờ (F_RSAR) hơ độ h h x phâ ớp the
tiếp ậ tập thô t uyề thố g (RSAR).
điều kiệ , R số thuộ t h ủ tập út gọ .
Tiếp the , hú g tôi tiế h h thử ghiệm để đ h
gi thuật t đề xuất (F_RSAR) với thuật t tìm
tập út gọ the tiếp ậ tập thô mờ sử dụ g ượ g
thô g ti tă g thêm (i f m ti g i ) dự t ê
e t py Sh , gọi thuật t
GAIN_RATIO_AS_FRS [8]. Để tiế h h thử
ghiệm, hú g tôi i đặt thuật t
GAIN_RATIO_AS_FRS trong [8] v thuật t
F_RSAR. Cả h i thuật t đều dù g u hệ tươ g tự
ở ô g thức (8) trong ô g t ì h [8]. Chạy 02 thuật
t t ê 8 ộ dữ iệu thử ghiệm. Kết uả thử ghiệm
h ở Bả g 4.
Hình 1. Độ chính xác phân lớp F_RSAR và RSAR
- 46 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
Bảng 4. Kết quả thử nghiệm thuật toán V. KẾT LUẬN
GAIN_RATIO_AS_FRS và thuật toán F_RSAR
Mô hì h tập thô mờ do D. Du is v ộng sự
Thuật toán Thuật toán F_RSAR [4, 5] đề xuất ô g ụ hiệu quả để giải quyết i
GAIN_RATIO_AS_FR
t út gọn thuộ t h t ực tiếp t ê ảng quyết
S
S R Độ Độ R Độ Độ
đị h ó miền trị thuộ t h nhậ gi t ị số. T g i
Bộ số C
T U chính chính chính chính y, hú g tôi đề xuất thuật t heu isti tìm một
liệu
T xác xác xác xác tập út gọn của bảng quyết đị h ó miền trị thuộ t h
phân phân phân phân
nhậ gi t ị số sử dụ g độ phụ thuộc mờ của thuộc
lớp lớp lớp lớp
SVM C4.5 SVM C4.5
t h the tiếp cận tập thô mờ.
1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855 Độ phụ thuộc mờ của thuộ t h đượ x định dựa
2 Ionosp 351 34 13 0.916 0.904 15 0.937 0.915
t ê m t ận quan hệ sinh bởi một quan hệ tươ g tự
here
3 Wdbc 569 30 17 0.925 0.917 19 0.980 0.975
x đị h t ê miề gi t ị thuộ t h. Thực nghiệm t ê
4 Wpbc 198 33 17 0.815 0.804 19 0.825 0.818 ộ số liệu UCI cho thấy, độ h h x phâ ớp
5 Wine 178 13 9 0.910 0.902 10 0.955 0.920 của tập dữ liệu sau khi thực hiệ phươ g ph p đề xuất
6 Glass 214 9 7 0.891 0.882 7 0.891 0.882
hơ độ h h x phâ ớp sau khi thực hiệ út
Magic 1902
7 10 6 0.782 0.765 6 0.782 0.765 gọn thuộ t h the tiếp cận tập thô truyền thống.
04 0
Page- Hơ ữ , phươ g ph p đề xuất ó độ h h x
8 5473 10 6 0.852 0.848 7 0.865 0.855
blocks phâ ớp hơ phươ g ph p tiếp cận dự t ê
e t py Sh t g ô g t ì h [8]. Mặt kh ,
phươ g ph p đề xuất khô g phải t h ô g thức
logarit củ e t py Sh ê thời gian thực hiện
hiệu quả hơ phươ g ph p t g [8].
Về đị h hướ g ghiê ứu tiếp theo, thứ nhất
tìm kiếm độ đ hiệu quả để giải quyết i t út
gọn thuộ t h the tiếp cận tập thô mờ nhằm â g
độ h h x phâ ớp, thứ h i tìm kiếm u hệ
tươ g tự kh hằm â g độ h h x phâ ớp
s u khi út gọn thuộ t h.
TÀI LIỆU THAM KHẢO
Hình 2. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS [1] CHEN, D.G., TSANG E.C.C. and ZHAO, S.Y, An
và F_RSAR approach of attributes reduction based on fuzzy TL
rough sets, IEEE International Conference on
Từ Bả g 4 v Hì h 2 t thấy, t ê ù g một u Systems, Man and Cybernetics, pp. 486-491, 2007.
hệ tươ g tự đượ sử dụ g, độ h h x phâ ớp s u [2] CHEN D.G, ZHAO S.Y., Local reduction of decision
khi thự hiệ thuật t đề xuất F_RSAR hơ độ system with fuzzy rough sets, Fuzzy Sets and Systems
h h x phâ ớp s u khi thự hiệ thuật t 161, pp. 1871-1883, 2010.
GAIN_RATIO_AS_FRS t g [8]. Bả g 4 ũ g h [3] CHEN D.G, LEI Z, SUYUN Z, QINGHUA H, and
thấy, tập út gọ ủ thuật t đề xuất F_RSAR ả PENGFEI Z, A Novel Algorithm for Finding Reducts
With Fuzzy Rough Sets, IEEE Transaction on Fuzzy
t miề dươ g mờ v hiều thuộ t h hơ s với
Systems, Vol. 20, No. 2, pp. 385 - 389 , 2012.
thuật t GAIN_RATIO_AS_FRS t g [8].
- 47 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
[4] DUBOIS D, PRADE H, Putting rough sets and fuzzy Knowledge-Based Systems 24 (2011), pp. 689–696,
sets together, Intelligent Decision Support, Kluwer 2011.
Academic Publishers,Dordrecht, 1992. [17] QINGHUA HU, DAREN YU, ZONGXIA XIE,
[5] DUBOIS D, PRADE H, Rough fuzzy sets and fuzzy Information-preserving hybrid data reduction based
rough sets, International Journal of General Systems, on fuzzy-rough techniques, Pattern Recognition Letters
17, pp. 191-209, 1990. 27, 2006, pp. 414-423.
[6] F. F. XU, D. Q. MIAO and L. WEI, An Approach for [18] R. JENSEN, Q. SHEN, Fuzzy-Rough Sets for
Fuzzy-Rough Sets Attributes Reduction via Mutual Descriptive Dimensionality Reduction, Proceedings of
Information, Fourth International Conference the 2002 IEEE International Conference on Fuzzy
on Fuzzy Systems and Knowledge Discovery, FSKD Systems ,FUZZ-IEEE'02, pp. 29-34, 2002.
2007, Volume 3, pp. 107 – 112, 2007. [19] R. JENSEN, Q. SHEN, Fuzzy–rough attribute
[7] F.F. XU, D.Q. MIAO and L. WEI, Fuzzy-rough reduction with application to web categorization,
attribute reduction via mutual information with an Fuzzy Sets and Systems, Volume 141, Issue 3, pp.
application to cancer classification, Computers and 469-485,2004.
Mathematics with Applications 57, pp. 1010 -1017, [20] RAJEN, B. BHATT, M. GOPAL., On fuzzy-rough sets
2009. approach to feature selection, Pattern Recognition
[8] J. DAI, QING X, Attribute selection based on Letters 26, pp. 965–975, 2005.
information gain ratio in fuzzy rough set theory with [21] TSANG G.C.Y., CHEN DEGANG., TSANG
application to tumor classification, Applied Soft E.C.C, LEE J.W.T and DANIEL S. YEUNGA, On
Computing 13, pp. 211–221, 2013. attributes reduction with fuzzy rough sets,
[9] J. NEUMANN, C. SCHNORR, G. STEILD, Proceedings of 2005 IEEE International Conference
Combined SVM-based feature selection and on Systems, Man and Cybernetics ,Volume 3, pp.
classification, Mach. Learn. 61 (2005), pp. 129-150. 2775 - 2780, 2005.
[10] J. QUINLAN, C4.5: Programs For Machine [22] TSANG E.C.C, DE GANG CHEN, The Fuzzy Rough
Learning, Morgan kaufmann, 1993. Set Approaches of Fuzzy Reasoning, Proceedings of
[11] L. A. ZADEH, Fuzzy sets, Information and Control, the Fifth International Conference on Machine
8:338-353, 1965. Learning and Cybernetics, Dalian, pp. 1642-1646,
2006.
[12] M.R. CHMIELEWSKI, J.W. GRZYMALABUSSE,
Global discretization of continuous attributes as [23] TSANG E.C.C, DEGANG CHEN. YEUNG D.S., XI
preprocessing for machine learning, Int. J. Approx. ZHAO WANG and JOHN W. T. LEE, Attributes
reasoning 15 (4), 1996, pp. 319–331. Reduction Using Fuzzy Rough Sets, IEEE Transactions
on Fuzzy Systems, Volume16, Issue 5 , pp. 1130 -
[13] PAWLAK Z., Rough sets, International Journal of
1141, 2008.
Computer and Information Sciences, 11(5): 341-356,
1982. [24] YI CHENG, Forward approximation and backward
approximation in fuzzy rough sets, Neurocomputing,
[14] PAWLAK Z., Rough sets: Theoretical Aspects of
Volume 148, pp. 340-353, 2015.
Reasoning About Data, Kluwer Aca-demic Publishers,
1991. [25] ZHAO MING, YAN ZHENGBO, ZHOU LIUKUN,
WANG HUIJIE and XU XIAOGANG, The Extraction
[15] Q. SHEN, R. JENSEN, Selecting informative features
Method of the Energy Consumption Characteristics
with fuzzy-rough sets and its application for complex
Based on Fuzzy Rough Set, Proceedings of Conference
systems monitoring, Pattern Recognition, Volume 37,
on Computational Intelligence and Bioinformatics
Issue 7, pp. 1351–1363, 2004.
(AASRI), pp. 142 – 149, 2012.
[16] QIANG HE, CONGXIN WU, DEGANG CHEN,
[26] The UCI machine learning repository,
SUYUN ZHAO, Fuzzy rough set based attribute
reduction for information systems with fuzzy decisions,
Ngày nhận bài: 29/02/2016
- 48 -
- Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-2, Số 16 (36), tháng 12/2016
SƠ LƢỢC VỀ TÁC GIẢ
NGUYỄN VĂN THIỆN NGUYỄN NHƢ SƠN
Si h ăm 1970 tại Phú Thọ. Si h ăm 1974 tại Nghệ A .
Tốt ghiệp ĐH B h kh H Nội Tốt ghiệp ĐH B h kh H
ăm 1996. Tốt ghiệp Thạ sỹ tại Nội ăm 1995, thạ sĩ CNTT tại
t ườ g ĐH Sư phạm H Nội ăm t ườ g ĐH B h kh H Nội
2000. ăm 2001. Nhậ ằ g tiế sỹ tại
Hiệ đ g ô g t tại : T ườ g ĐH Queensland - Aust i ăm
ĐH Cô g ghiệp H Nội. 2007, huyê g h Kh họ
m y t h.
Hướ g ghiê ứu: Hệ thố g thô g ti , Cơ sở dữ iệu,
Kh i ph dữ iệu. Hiệ ô g t tại: Việ CNTT, Việ H âm
KH&CN Việt N m.
Điệ th ại: 0902416668.
Hướ g ghiê ứu: Hệ thố g thô g ti , Cơ sở dữ iệu,
Email: nvthien1970@gmail.com
Kh i ph dữ iệu, T h t đ m mây.
NGUYỄN LONG GIANG Điệ th ại: 0987039966.
Email: nnson@ioit.ac.vn
Sinh ăm 1975 tại H Nội.
Tốt ghiệp ĐH B h kh H Nội
ăm 1997, thạ sĩ CNTT tại ĐH
Cô g ghệ, ĐH Quố gi H Nội
ăm 2003. Nhậ ằ g tiế sỹ tại
Việ CNTT, Việ H âm
KH&CN Việt N m ăm 2012.
Hiệ ô g t tại: Việ CNTT, Việ H âm
KH&CN Việt N m.
Hướ g ghiê ứu: Cơ sở dữ iệu, kh i ph dữ iệu v
họ m y.
Điệ th ại: 0904739189.
Email: nlgiang@ioit.ac.vn
- 49 -
nguon tai.lieu . vn