Đại học Vinh Tạp chí khoa học, tập XXXVI, số 4A-2007 57
XÂY DựNG CÂY QUYếT ĐịNH ĐA TRị DựA TRÊN TậP THÔ

Nguyễn Thị Minh Tâm
(a)Tóm tắt. Bài báo này giới thiệu một cách tiếp cận để xây dựng cây quyết định đa
trị có khả năng chịu lỗi dựa trên mô hình tập thô có độ chính xác thay đổi. Một khái
niệm mới về quan hệ tơng đơng với độ chính xác đợc đa ra trong lý thuyết tập
thô có độ chính xác thay đổi và đợc áp dụng để xây dựng cây quyết định đa trị.

I. GIớI THIệU
Hiện nay, các phơng pháp phân lớp đang đợc quan tâm nghiên cứu trong
nhiều lĩnh vực: khai phá dữ liệu, thống kê, học máy, Mục đích phân lớp là phân
loại các đối tợng dựa trên giá trị của các thuộc tính ban đầu và thuộc tính nhãn.
Trong bài báo này chúng tôi đa ra một trong những cách tiếp cận mới để lựa chọn
thuộc tính là xây dựng cây quyết định dựa trên lý thuyết tập thô.
Lý thuyết tập thô đợc Pawlak đề xuất, đã trở thành một công cụ toán học để
giải quyết với những thông tin mờ, không chắc chắn. Lý thuyết tập thô tổ hợp các
quan hệ không phân biệt (quan hệ tơng đơng) thành các tập xấp xỉ của các đối
tợng dựa trên tập xấp xỉ trên và xấp xỉ dới ([8]).
Một trong những vấn đề của lý thuyết tập thô là phân lớp, nhng các lớp
trong lý thuyết tập thô phải là chính xác và chắc chắn. Trong thực tế, hai điểm lân
cận có thể không giống nhau về cơ bản do thiếu các đặc trng dẫn đến việc phân lớp


58
Tơng tự ta định nghĩa:

A
(u,i) = {u U}: u IND(A)u & d(u) = i trong đó u U & i
A
(u)
( )
(
)
(
)
( )( )
( )


=
uj
A
A
A
A
iucard
iucard
iu





} là các
lớp tơng đơng của R, với mọi X U, các xấp xỉ trên và xấp xỉ dới với độ chính xác
đợc định nghĩa nh sau:

i) Tập xấp xỉ trên của X theo quan hệ R với độ chính xác

:{ }
( )







=






==
i
EX
R
XEXRUEXPOSXR

R
XEXRUEXNONNEGXR .
Tập
XR

là tập các phần tử của U đợc phân lớp là phần tử của X với xác
suất . Tri thức cho trớc đợc biểu diễn bằng các thuộc tính từ R; XR

là tập các
phần tử của U đợc phân lớp thuộc X hoặc -X với xác suất 1-, 01.
iii)
(
)
XRXRBN
R




= đợc gọi là miền biên của X có độ chính xác . Nó
bao gồm tất cả đối tợng không thể phân lớp rõ ràng thuộc vào tập X. Một tập đợc
gọi là thô nếu miền biên của nó khác rỗng, ngợc lại tập đó đợc gọi là tập chính xác.

Hình 1. Xấp xỉ trên và xấp xỉ dới của một tập
Tập hiện tại

Xấp xỉ trên

Xấp xỉ d


Định nghĩa 5. Nhân tố quan trọng của một thuộc tính C
j
trong C đợc định
nghĩa nh sau: importance-factor = 1 -
)(
)(
dCcard
CdCcard
j
+

+
.
Định nghĩa 6. Giả sử P, Q là 2 họ các quan hệ tơng đơng của tập đối
tợng U. Ký hiệu U/IND(P) = {X
1
, X
2
, , X
n
}; U/IND(Q) = {Y
1
, Y
2
, , Y
m
}
Đặt

)(/


=

,
thì {H
1
, H
2
, , H
m+1
} đợc gọi là suy rộng của P với độ chính xác

có quan hệ với Q,
đợc ký hiệu là GENQ

(P)
và có thể gọi {H
1
, H
2
, , H
m+1
} là một phép tách của tập
đối tợng U.
III. CÂY QUYếT ĐịNH ĐA TRị
3.1. Tập dữ liệu huấn luyện đa trị
Bảng 1 là ví dụ minh hoạ tập dữ liệu huấn luyện đa trị. Mỗi bản ghi của tập
dữ liệu có 4 thuộc tính thông thờng và một thuộc tính nhãn lớp. Thuộc tính maker,
performance, color là thuộc tính có giá trị phi số còn thuộc tính price là thuộc tính có
giá trị số. Thuộc tính nhãn lớp gồm 3 giá trị A, B, C. Sản phẩm p3 là một ví dụ về


good green A,B,C
p9 C $1250

good yellow, green A,B,C
p10 B $1140

good yellow, green A
p11 A $340

not good yellow, blue A,C
p12 C $1300

good yellow A,B
p13 B $1090

good blue C
p14 B $810

good green A
p15 B $520

not good yellow, blue, green C
Nguyễn Thị Minh Tâm CÂY QUYếT ĐịNH ĐA TRị DựA TRÊN TậP THÔ, tr. 57-64 60


3.3. Giải thuật cơ bản xây dựng cây quyết định đa trị
Các giải thuật xây dựng cây quyết định thờng tránh xây dựng những cây lớn
bởi vì chúng sẽ sinh ra nhiều luật, điều này sẽ không hiệu quả trong việc dự đoán
price

performanc
e

color

A,B,C

A,C

A

B,C

C



475~599

725~849

850~974

975~109
1100~1224

1225~1350

Hình 2.

Ví dụ về cây quyết định đa trị

Đại học Vinh Tạp chí khoa học, tập XXXVI, số 4A-2007 61
phân lớp. Vì vậy việc xây dựng cây quyết định nhỏ để đa ra các luật tốt nhất là vấn
đề có tầm quan trọng.
Giải thuật:
Input: Tập dữ liệu huấn luyện đa trị D.
Output: Cây quyết định đa trị T.
Begin
1. Khởi tạo cây T và đặt tất cả các bản ghi của T ở gốc.

A
(u)) then
begin Thay thế tập đối tợng tại N bằng cái chung của nó:
A
(u);
Thay đổi trạng thái của N là ready;
end
else
begin Tính P = CORE

(N, CCAS {d});
if P = | P = CCAS then
begin P = thuộc tính từ tập CCAS có importance factor cao
nhất;
Nguyễn Thị Minh Tâm CÂY QUYếT ĐịNH ĐA TRị DựA TRÊN TậP THÔ, tr. 57-64 62
end
Tính GEND

(P);
CCAS = CCAS \ P;
Thay thế nhãn của nút N bằng P và đánh dấu là ready;
Tạo m+1 nút mới N
1
, N

U/IND(C) = { {1}, {2, 4,18, 21, 22}, {3, 7, 9, 10, 14}, {5}, {6}, {8}, {11}, {12}, {13}, {15},
{16}, {17}, {19}, {20} }.
U/IND(D) = { {1, 2, 3, 4, 7, 9, 12, 14, 18, 20}, {5, 6, 8, 10, 11, 13, 15, 16, 17, 19, 21, 22}}
P = CORE

(N, CCAS {d}) = {C1,C4}
U/P = { {1, 12, 13}, {2, 4, 16, 18, 21, 22}, {3, 7, 9, 10, 14, 20}, {5, 19}, {6, 8,1 5}, {11, 17}}
Tính GEND

(P): H1 = {3, 7, 9, 10, 14, 20}; H2 = {5, 6, 8, 11, 15, 17, 19};
H3 = {1, 2, 4, 12, 13, 16, 18, 21, 22}
Bảng 2. Ví dụ về bảng quyết định
Các thuộc tính điều kiện
Thuộc tí
nh
quyết định

Tập đối
tợng U
C1 C2 C3 C4 Lớp (D)
1 high high high normal

H
2 high high high good H
3 low or less than zero low normal

good H
4 high high high good H
5 middle high high normal



Đại học Vinh Tạp chí khoa học, tập XXXVI, số 4A-2007 63
13 high low normal

normal

F
14 low or less than zero low normal

good H
15 low or less than zero middle

normal

normal

F
16 high middle

normal

good F
17 middle middle

high good F
18 high high high good H
19 middle high normal

thực hiện đối với các bảng quyết định nhất quán (bảng 1). Trên đây chúng tôi đã đa
ra một cách tiếp cận tập thô để xây dựng cây quyết định đa trị nhằm quản lý các hệ
thông tin đa trị và đa ra một giải thuật xây dựng cây quyết định dựa trên mô hình
tập thô có độ chính xác thay đổi có khả năng chịu lỗi. Cho dù tồn tại sự không nhất
quán trong bảng quyết định nhng giải thuật vẫn có thể đa ra kết quả khá vừa ý.
So với giải thuật ID3 [9] thì cây quyết định xây dựng dựa trên giải thuật RS_DTA có
cấu trúc đơn giản hơn và có các luật tốt hơn.

Tập đối tợng
U
C1: low or less than
zero
C4: good
{3,7,9,10,14,20}
C1: high

C4: good
{1,2,4,12,13,16,18,
21,22}
C1: low or less than zero

C4: normal
Hoặc C1:middle
{5,6,8,11,15,17,19}
H

F

C3: hig
h

Society of AI, SIGKBS-JSAI, ICS-IPSJ and IEICE-SIGAI on Active Mining,
Hanoi, Vietnam, 2004.
[4] H. T. Bao, Introduction To Knowledge Discovery And Data Mining,
http://www.ioit.ac.vn, 2000.
[5] Chang-Ling Hsu, Multi-valued and Multi-labeled Decision Tree Classifiers For
Data Mining, PhD Thesis in Information Management, China, 2004.
[6] Jin Mao Wei, Rough Set based approach to selection of node, Yangs Scientific
Research Institute, 2002.
[7] X. Liu, H. Huang, W. Xu, A Contribution to Decision Tree Construction Based on
Rough Set Theory, Springer-Verlag Berlin, 2004.
[8] Z. Pawlak, Rough Sets, Theoretical Aspects of Reasoning about Data. Dordrecht,
Kluwer, 1991.
[9] J. R. Quinlan, Induction of decision trees, In: Machine Learning, 1986.
[10] Sonajharia Minz, Rajni Jain, Rough Set based Decision Tree Model for
Classification, Springer-Verlag Berlin, 2003.
[11] W. Ziarko, Variable Precision Rough Set Model, Journal of computer and
System Sciences, 46, 1993, 3959.
[12] Y. Zhao, H. Zhang, Q. Pan, Classification Using the Variable Precision Rough
Set, Springer-Verlag Berlin, 2003
. SUMMARY

A Multivariate Decision Tree Construction Based on Rough Set

This paper presented an approach to construct multivariate decision tree,
which has the ability of fault tolerance, based on the variable precision rough sets
model. A new concept of generalization of one equivalence relation with precision
is introduced in the variable precision rough sets model and used for construction of