Tối ưu quá trình học cây quyết định cho bài toán phân lớp theo cách tiếp cận khoảng mờ lớn nhất

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Tối ưu quá trình học cây quyết định
cho bài toán phân lớp theo cách tiếp cận
khoảng mờ lớn nhất
Lê Văn Tường Lân1, Nguyễn Mậu Hân1, Nguyễn Công Hào2
1Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế
2Trung tâm Công nghệ Thông tin, Đại học Huế
E-mail: lvtlan@yahoo.com, nmhan2009@gmail.com, nchao@hueuni.edu.vn
Tác giả liên hệ: Lê Văn Tường Lân
Ngày nhận: 07/07/2017, ngày sửa chữa: 20/09/2017, ngày duyệt đăng: 09/10/2017
Tóm tắt: Hiện nay, khai phá dữ liệu rõ không thể giải quyết tất cả các yêu cầu đặt ra và bài toán phân lớp cây quyết
định mờ tất yếu đóng góp một vai trò quan trọng của bài toán khai phá dữ liệu mờ. Tuy vậy, việc học cây quyết định
dựa vào định lượng ngữ nghĩa theo điểm vẫn còn một số hạn chế như vẫn xuất hiện nhiều sai số trong quá trình xử lý,
cây kết quả thu được không thật sự linh hoạt. Bằng cách thức đối sánh theo khoảng mờ, cây thu được đã giảm thiểu sai
số và linh hoạt trong dự đoán tuy nhiên số nút trên cây tăng nhanh nên không đơn giản với người dùng và mất thời gian
duyệt cây khi dự đoán. Trong bài báo này, chúng tôi đề xuất khái niệm khoảng mờ lớn nhất để xây dựng phương pháp
học quy nạp cây quyết định mờ HAC4.5*, nhằm thu được cây quyết định mờ đạt được tối thiểu về số nút trên cây nhưng
có khả năng dự đoán cao.
Từ khóa: Khai phá dữ liệu, cây quyết định, cây quyết định mờ, khoảng mờ lớn nhất, HAC4.5*.
Title: Fuzzy Decision Tree Learning for Classification based on Maximum Fuzziness Intervals
Abstract: Nowadays, data mining based on precise logic cannot satisfy all requirements, so classification based on fuzzy decision
trees is important due to the fuzziness nature of data mining. However, decision tree learning based on the quantitative
methods of the hedge algebra still has some restrictions because of errors involved and the resulted tree not truly
flexible. Using fuzziness interval matching, the resulted tree has reduced the number of errors and increase flexibility
in prediction. However, the number of nodes in the resulted tree increases rapidly, causing difficulty to use and more
time to produce prediction results. In this paper, a concept of maximum fuzziness interval is proposed in order to build
an inductive learning method called “HAC4.5* fuzzy decision tree”, resulting a fuzzy decision tree with the minimum
number of nodes and highly accurate prediction.
Keywords: Data mining, decision tree, fuzzy decision tree, maximum fuzziness intervals, HAC4.5*.
I. ĐẶT VẤN ĐỀ
Thế giới thực thì vô hạn trong khi ngôn ngữ của chúng
ta lại hữu hạn, vì thế sẽ xuất hiện những cụm từ không
chính xác hoặc mơ hồ. Trong thế giới thực, các kho dữ liệu
nghiệp vụ được lưu trữ mờ là tất yếu, vì thế bài toán phân
lớp cây quyết định rõ không thể giải quyết tất cả các yêu
cầu đặt ra và bài toán phân lớp dữ liệu cây quyết định mờ
là vấn đề tất yếu của khai phá dữ liệu [1–12].
Cho một tập các mẫu dữ liệu V = U × Y , trong đó U =
{ui |i = 1, . . . , N} là tập dữ liệu, Y = {y1, . . . , yn} là tập
các nhãn của các lớp, ui ∈ D là dữ liệu thứ i với D =
A1× · · ·× Am là tích Đề-các của các miền của m thuộc tính
tương ứng, n là số lớp và N là số mẫu dữ liệu, để ý rằng
U ⊂ D. Mỗi dữ liệu ui ∈ U thuộc một lớp yi ∈ Y tương
ứng tạo thành từng cặp (ui, yi) ∈ V . Giải bài toán phân lớp
dựa trên mô hình cây quyết định chính là xây dựng một
cây quyết định để phân lớp, ký hiệu S, là một ánh xạ từ
tập dữ liệu vào tập nhãn:
S : D→ Y . (1)
Cây quyết định biểu diễn cho tri thức về bài toán, nó
không chỉ phản ánh đúng với tập dữ liệu mẫu mà còn phải
có khả năng dự đoán và cung cấp giúp cho người dùng
phán đoán, ra quyết định đối với đối tượng trong tương lai
mà nhãn lớp của nó chưa được xác định từ tập dữ liệu chưa
biết. Với bài toán phân lớp cây quyết định được nêu ở (1),
42
Tập V-2, Số 18 (38), 12/2017
nếu tồn tại một thuộc tính mờ Aj trong số các thuộc tính
của D thì ta nói (1) là bài toán phân lớp cây quyết định mờ.
Như vậy, mô hình cây quyết định S phải đạt các mục
tiêu như hiệu quả phân lớp cao, tức là sai số phân lớp cho
các dữ liệu ít nhất có thể, cây có ít nút nhưng có khả năng
dự đoán cao, không xảy ra tình trạng quá khớp. Mục tiêu
về hiệu quả phân lớp nhằm đáp ứng tính đúng đắn đối với
tập dữ liệu mẫu được cho của bài toán, còn mục tiêu sau
được đưa ra với mong muốn mô hình cây quyết định nhận
được phải đơn giản và dễ hiểu đối với người dùng.
Gọi fh(S) là hàm đánh giá tính hiệu quả của quá trình
phân lớp, fn(S) là hàm đánh giá tính đơn giản của cây và
dễ hiểu đối với người dùng, mục tiêu của bài toán là
fh(S) → max và fn(S) → min. (2)
Hai mục tiêu ở (2) khó có thể đạt được đồng thời. Khi
số nút của cây giảm đồng nghĩa với lượng tri thức về bài
toán giảm thì nguy cơ phân lớp sai tăng lên, nhưng khi có
quá nhiều nút cũng có thể gây ra sự quá khớp thông tin
trong quá trình phân lớp. Bên cạnh đó, sự phân chia tại
mỗi nút ảnh hưởng đến tính phổ quát hay cá thể tại nút đó.
Nếu sự phân chia tại một nút là nhỏ sẽ làm tăng tính phổ
quát và ngược lại nếu sự phân chia lớn sẽ làm tăng tính cá
thể của nút đó. Tính phổ quát của nút trên cây sẽ làm tăng
khả năng dự đoán nhưng nguy cơ gây sai số lớn, trong khi
tính cá thể giảm khả năng dự đoán nhưng lại tăng tính đúng
đắn nhưng nó cũng là nguyên nhân của tình trạng quá khớp
trên cây. Các phương pháp giải quyết bài toán mô hình cây
quyết định đều phải thỏa hiệp giữa các mục tiêu này để đạt
được kết quả cuối cùng.
Hiện có một số cách tiếp cận như sau. Trước hết là cách
tiếp cận giá trị ngôn ngữ cho tập mờ để xây dựng cây quyết
định mờ. Các tác giả trong [13–15] đã xác định các giá trị
ngôn ngữ cho tập dữ liệu mờ và xây dựng cây quyết định
ngôn ngữ (LDT: Linguistic Decision Tree) bằng cách sử
dụng tư tưởng của thuật toán ID3 của cây quyết định rõ
cho các nút ứng với các thuộc tính ngôn ngữ (LID3).
Tuy nhiên, cách làm này sẽ làm phát sinh cây đa phân, có
sự phân chia theo chiều ngang lớn tại các nút ngôn ngữ khi
tập giá trị ngôn ngữ của thuộc tính mờ lớn (Hình 1), nên
dễ dẫn đến tình trạng quá khớp. Thêm vào đó, tại nút này,
ta không thể sử dụng cách phân chia nhị phân của thuật
toán C4.5 vì không có thứ tự giữa các giá trị ngôn ngữ.
Hơn nữa, với các giá trị rõ trong miền thuộc tính mờ của
tập dữ liệu huấn luyện, một đoạn con các giá trị rõ sẽ được
ánh xạ bằng một giá trị ngôn ngữ nên có sự sai lệch lớn.
Cách tiếp cận mờ thứ hai là theo đại số gia tử (ĐSGT)
do N. C. Ho và W. Wechler khởi xướng từ 1990. Cách này
có nhiều ưu điểm vì theo cách tiếp cận này, mỗi giá trị
ngôn ngữ của một biến ngôn ngữ nằm trong một cấu trúc
đại số nên ta có thể đối sánh giữa các giá trị ngôn ngữ.
Nút phân
chia mờGiá trị 
ngôn ngữ 1 Giá trị ngôn ngữ k
... 
Hình 1: Điểm phân chia đa phân theo giá trị 
ngôn ngữ tại thuộc tính mờ Hình 1. Điểm phân chia đa phân theo giá trị ngôn ngữ tại thuộctính mờ.
Theo cách tiếp cận ĐSGT, chúng ta có thể thuần nhất
các trường mà dữ liệu của nó bao gồm cả dữ liệu rõ và
mờ. Các tác giả trong [16–20] đã chỉ ra phương pháp định
lượng ngữ nghĩa theo điểm nhằm thuần nhất dữ liệu về các
giá trị số hay giá trị ngôn ngữ và cách thức truy vấn dữ
liệu trên thuộc tính này. Từ đó, chúng ta có thể học phân
lớp trên tập mẫu thuần nhất đó.
Bài toán xây dựng cây quyết định mờ lúc này có thể sử
dụng các thuật toán xây dựng cây quyết định rõ như C4.5,
SLIQ, v.v. [7, 8, 10, 12]. Các nút phân chia nhị phân được
tính theo dựa theo điểm phân chia với các giá trị ngôn ngữ
đã có thứ tự và hoàn toàn xác định tương ứng với một giá
trị số trong ĐSGT đã xây dựng.
Tuy vậy, cách thuần nhất dựa trên phương pháp định
lượng ngữ nghĩa theo điểm này vẫn xuất hiện nhiều sai số
vì một đoạn con các giá trị rõ đã có sẽ được quy về một
điểm tức là một giá trị ngôn ngữ tương ứng, điều này cũng
làm xuất hiện các giá trị gần nhau có thể được phân hoạch
ở hai đoạn con khác nhau nên kết quả phân lớp khác nhau.
Bên cạnh đó, cây kết quả cũng khó đưa ra dự đoán trong
các trường hợp cần dự đoán mà tại đó có sự đan xen ở
điểm phân chia mờ, ví dụ ta cần dự đoán cho trường hợp
đoạn con [x1, x2], với x1 < x < x2 tại nút phân chia mờ ở
Hình 2.
Cách tiếp cận thứ ba là bằng cách thức đối sánh theo
khoảng mờ dựa trên ĐSGT, cây kết quả thu được đã giảm
thiểu sai số và linh hoạt nhờ chúng ta vẫn giữ nguyên miền
giá trị rõ trong khi vẫn đối sánh được với các giá trị mờ
trong tập mẫu cho quá trình huấn luyện [20], như Hình 3.
Tuy vậy, số nút trên cây kết quả có khả năng tăng cao nên
không đơn giản với người dùng và mất thời gian duyệt cây
khi dự đoán. Do vậy, hàm mục tiêu đã nêu ở (2) có thể
không đạt được.
Trong bài báo này, chúng tôi đề xuất một phương pháp
học cây quyết định mờ khi tập mẫu huấn luyện không thuần
nhất giá trị dựa trên khái niệm khoảng mờ lớn nhất, trong
khi giữ nguyên các ưu điểm của phương pháp đối sánh theo
khoảng mờ nhưng tối ưu về số nút trên cây kết quả, nhằm
thu được cây quyết định có đơn giản và hiệu quả.
43
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Hình 2: Điểm phân chia nhị phân theo giá trị ngôn ngữ hoặc giá trị số tại thuộc tính mờ, 
dựa trên phương pháp định lượng ngữ nghĩa theo điểm trong ĐSGT. 
Nút phân
chia mờ ≥ Giá trị số x tại 
điểm phân chia 
< Giá trị số x tại 
điểm phân chia 
Giá trị ngôn ngữ
tương ứng trong 
ĐSGT 
Giá trị ngôn ngữ 
tương ứng trong 
ĐSGT 
Hình 2. Điểm phân chia nhị phân theo giá trị ngôn ngữ hoặc giá trị số tại thuộc tính mờ, dựa trên phương pháp định lượng ngữ nghĩa
theo điểm trong ĐSGT.
Hình 3: Điểm phân chia theo khoảng mờ tại thuộc tính mờ, dựa trên phương pháp định 
lượng ngữ nghĩa theo khoảng mờ trong ĐSGT. 
Nút phân
chia mờ
Khoảng 
mờ [ai, aj]
Khoảng 
 mờ [ak, al]
Tập giá trị ngôn 
ngữ tương ứng 
Akl trong ĐSGT 
Tập giá trị ngôn 
ngữ tương ứng 
Aij trong ĐSGT 
Hình 3. Điểm phân chia theo khoảng mờ tại thuộc tính mờ, dựa trên phương pháp định lượng ngữ nghĩa theo khoảng mờ trong ĐSGT.
II. KHOẢNG MỜ VÀ KHÁI NIỆM KHOẢNG MỜ
LỚN NHẤT
1. Khoảng mờ và đối sánh dựa trên khoảng mờ
Cho một ĐSGT X = (X,G,H, ≤), với G = {c+, c−}, trong
đó c+ và c− tương ứng là phần tử sinh dương và âm; X là
tập nền; H = H+ ∪ H− với H− = {h−p, h−p+1, . . . , h−1} và
H+ = h1, . . . , hq , h−1 > h−2 > · · · > h−p và h1 < · · · < hq .
Định nghĩa 1. Khoảng mờ của một phần tử x là một đoạn
con của [0, 1], có độ dài đúng bằng độ đo tính mờ f m(x),
ký hiệu là I(x), được xác định bằng cách quy nạp theo độ
dài của x như sau [17]:
i) Với độ dài x bằng 1 (l(x) = 1), tức là x ∈ {c+, c−},
I f m(c−) và I f m(c+) là các khoảng con và tạo thành một
phân hoạch của [0, 1], thỏa I f m(c−) ≤ I f m(c+). Tức là
với mọi u ∈ I f m(c−) và mọi v ∈ I f m(c+): u ≤ v. Điều
này hoàn toàn phù hợp với thứ tự ngữ nghĩa của c−
và c+.
Ký hiệu độ dài của I f m(x) là
I f m(x), ta có I f m(c−) =
I f m(c−) và
I f m(c+) = I f m(c+);
ii) Giả sử với mọi x ∈ X có độ dài bằng k (l(x) = k),
có khoảng mờ là I f m(x) và
I f m(x) = f m(x). Các
khoảng mờ của y = hi x, với mọi i ∈ [−p,−p +
1, . . . ,−1, 1, 2, . . . , q], lúc này l(y) = k + 1, là tập
{I f m(hi x)} thoả mãn một phân hoạch của I f m(x),I f m(hi x) = I f m(hi x) và có thứ tự tuyến tính tương
ứng với thứ tự của tập {h−px, h−p+1x, . . . , hq x}.
Khi l(x) = k, ta ký hiệu I(x) thay cho I f m(x), Xk =
{∀x ∈ X |l(x) = k} là tập các phần tử trong X có độ
dài đúng bằng k, Ik = {Ik(x)|x ∈ Xk} là tập tất cả các
khoảng mờ mức k.
Định nghĩa 2. Hai khoảng mờ được gọi là bằng nhau, ký
hiệu I(x) = I(y) khi chúng được xác định bởi cùng một giá
trị (x = y), tức là ta có IL(x) = IL(y) và IR(x) = IR(y).
Ngược lại ta gọi chúng là hai khoảng mờ khác nhau và ký
hiệu là I(x) , I(y). Trong đó, ký hiệu IL(x) và IR(x) là
điểm mút trái và phải của khoảng mờ I(x).
Định nghĩa 3. Cho 2 khoảng rõ khác nhau [a1, b1] và
[a2, b2] tương ứng với các khoảng mờ [Ia1, Ib1 ], [Ia2, Ib2 ] ⊆
[0, 1]. Ta nói khoảng [a1, b1] đứng trước [a2, b2] hay [a2, b2]
đứng sau [a1, b1], viết [a1, b1] < [a2, b2] hay [Ia1, Ib1 ] <
[Ia2, Ib2 ] nếu:
i) b2 > b1 tức Ib2 > Ib1 ,
ii) Nếu Ib2 = Ib1 tức b2 = b1 thì Ia2 > Ia1 tức a2 > a1,
và lúc này ta nói dãy [a1, b1], [a2, b2] là dãy có 2 khoảng
có quan hệ thứ tự trước sau.
Định lý 1. Cho k khoảng khác nhau từng đôi một [a1, b1],
[a2, b2],. . . , [ak, bk], ta luôn sắp xếp để được một dãy có k
khoảng với quan hệ thứ tự trước sau.
Thật vậy, với k khoảng khác nhau từng đôi một [a1, b1],
[a2, b2],. . . , [ak, bk], ta luôn tìm được khoảng trước nhất
của dãy là [ai, bi], với ai = min(a1, a2, . . . , an). Nếu có
nhiều khoảng [aj, bj], i = 1 . . . k mà aj = ai thì chọn ta
khoảng [ai, bi] là khoảng có bi bé nhất trong các giá trị bj .
Việc chọn bi luôn tìm được duy nhất vì các khoảng đã cho
khác nhau từng đôi một nên nếu ai = aj thì bi , bj (Định
nghĩa 2).
44
Tập V-2, Số 18 (38), 12/2017
Sau khi tìm được khoảng trước nhất của dãy là [ai, bi],
ta tiếp tục tìm khoảng thứ 2 và cứ thế tiếp tục. Sau k lần
tìm và sắp xếp ta có được dãy gồm k khoảng mà các phần
tử của dãy đã được sắp xếp theo quan hệ thứ tự trước sau.
2. Khoảng mờ lớn nhất và phương pháp tính khoảng
mờ lớn nhất
Trong ĐSGT, một hạng từ có thể mang ngữ nghĩa của
một hạng từ khác tức hạng từ được dùng để sinh ra nó.
Chẳng hạn “very old” mang ngữ nghĩa của “old”, “very
little old” cũng mang ngữ nghĩa của “old”. Vậy, hai hạng
từ “very old” và “very little old” đều có quan hệ kế thừa
ngữ nghĩa (hay quan hệ kế thừa) của “old”, ta gọi “very
old” và “very little old” có quan hệ kế thừa ngữ nghĩa.
Định nghĩa 4. Một ĐSGT X = (X,G,H, ≤), với mọi x, y ∈
X , được gọi là có quan hệ kế thừa ngữ nghĩa với nhau
và được ký hiệu ∼(x, y) nếu tồn tại z ∈ X sao cho x =
hin · · · hi1 z = hjm · · · hj1 z.
Mệnh đề 1. Với mọi x, y ∈ X xác định hai khoảng mờ mức
k và mức l lần lượt là Ik(x) và Il(y), chúng hoặc không
có quan hệ kế thừa, hoặc có quan hệ kế thừa với nhau nếu
tồn tại z ∈ X, |z | = v, v ≤ min(l, k), IL(z) ≤ IL(y), IR(z) ≥
IR(y), và IL(z) ≤ IL(x), IR(z) ≥ IR(x) hay Iv(z) ⊇ Ik(x)
và Iv(z) ⊇ Il(y), tức là x, y được sinh ra từ z.
Chứng minh. Mệnh đề này dễ dàng suy ra từ tính phân
hoạch các khoảng mờ.
Khi x và y có quan hệ kế thừa ngữ nghĩa, ta nói rằng
khoảng tính mờ Iv(z) bao hàm hai khoảng tính mờ Ik(x)
và Il(y), hay z bao hàm ngữ nghĩa của x và y và ta ký
hiệu z = ∼(x, y). Theo định nghĩa, rõ ràng hai hạng từ x, y
có quan hệ ngữ nghĩa nếu chúng có dạng x = hin · · · hi1 z,
y = hjm · · · hj1 z. Nếu hi1 = hj1 = h′1, hi2 = hj2 = h′2. . . thì ta
có z = h′1c hoặc z = h
′
1h
′
2c đều bao hàm ngữ nghĩa của x
và y. Tuy nhiên, thực tế sử dụng z thay thế cho cả x và y
có thể làm mất ngữ nghĩa của chúng và rõ ràng, trên thực
tế chúng ta cần phải xác định z sao cho ngữ nghĩa càng
gần với x, y càng tốt. 
Định nghĩa 5. Cho một ĐSGT X = (X,G,H, ≤), với x,
y, z ∈ X , z = ∼(x, y). Nếu ∃z1 ∈ X , z1 = ∼(x, y) và
len(z) ≥ len(z1) thì ta nói z có ngữ nghĩa gần với x, y
nhất, hay khoảng mờ z có độ dài lớn nhất và được ký hiệu
z = ∼max(x, y).
Định nghĩa 6. Cho một ĐSGT X = (X,G,H, ≤), với ∀x,
y ∈ X và ∼(x, y). Mức độ gần nhau của x và y theo quan
hệ kế thừa ngữ nghĩa, ký hiệu là sim(x, y), được định nghĩa
như sau:
sim(x ...  cũng dựa theo tỷ lệ
lợi ích thông tin của các ngưỡng trong tập D tại nút đó. Tỷ
lệ lợi ích thông tin của các ngưỡng đối với thuộc tính A là
thuộc tính số trong tập D tại nút đó.
Giả sử thuộc tính A là thuộc tính mờ đã phân hoạch theo
khoảng mờ và có k khoảng khác nhau đã được sắp xếp theo
thứ tự trước sau là: [Ia1, Ib1 ] < [Ia2, Ib2 ] < · · · < [Iak , Ibk ].
Ta có k ngưỡng được tính: ThHAi = [Iai , Ibi ], (với 1 ≤
i < k). Tại mỗi ngưỡng được chọn ThHAi , tập dữ liệu D
còn lại tại nút này được chia làm các tập
D1 = {∀ [Ia j , Ib j ]
 [Ia j , Ib j ] < ThHAi },
D2 = {∀ [Ia j , Ib j ]
 [Ia j , Ib j ] > ThHAi }.
Lúc này ta có
GainHA
(
D,ThHAi
)
= Entropy(D) − |D1 ||D| × Entropy(D1)
− |D2 ||D|× Entropy(D2),
SplitInfoHA
(
D,ThHAi
)
= − |D1 ||D| × log2
|D1 |
|D|
− |D2 ||D| × log2
|D2 |
|D| ,
GainRatioHA
(
D,ThHAi
)
=
GainHA
(
D,ThHAi
)
SplitInfoHA
(
D,ThHAi
) .
Trên cơ sở tính toán tỷ lệ lợi ích thông tin cho các ngưỡng,
ngưỡng nào có tỷ lệ lợi ích thông tin lớn nhất thì được chọn
để phân tách tập huấn luyện D.
2) Thuật toán đề xuất:
Trong mục này, chúng tôi đề xuất thuật toán, gọi là
HAC4.5*, chi tiết trong Thuật toán 2.
46
Tập V-2, Số 18 (38), 12/2017
Thuật toán 2: Thuật toán HAC4.5*
Input: Tập mẫu huấn luyện D.
Output: Cây quyết định mờ S.
Method:
for each (thuộc tính mờ X của D)
begin
Xây dựng ĐSGT Xk tương ứng thuộc tính mờ X;
Chuyển các giá trị số và giá trị ngôn ngữ của X về
các giá trị đoạn ⊆ [0, 1];
end
Khởi tạo tập các nút lá S; S = D;
for each (nút lá L thuộc S)
if (L thuần nhất) or (L.Tập thuộc tính là rỗng) then
L.Nhãn = Tên lớp
else
begin
if (L là thuộc tính mờ) then
begin
for each (khoảng mờ x của thuộc tính L)
for each (khoảng mờ y của thuộc tính L
mà y , x)
//Gọi thuật toán 1
Tìm và thay thế x bởi z = ∼max(x, y)
end
end if
X = Thuộc tính tương ứng có GainRatio hay
GainRatioHA lớn nhất;
L.Nhãn = Tên thuộc tính X;
if (L là thuộc tính mờ) then
begin
T = Ngưỡng có GainRatioHA lớn nhất;
Gán nhãn T của thuộc tính X cho cây S;
S1 = { Ixi
 Ixi ⊆ L, Ixi < T};
S1.Nút cha = L;
3. Đánh giá thuật toán
Như vậy, bằng việc tìm các khoảng mờ lớn nhất cho mọi
khoảng mờ trong tập huấn luyện và xác nhập chúng, thuật
toán HAC4.5* đã làm giảm thiểu số lượng khoảng mờ tham
gia trong quá trình học xây dựng cây nên làm giảm số nút
trên cây kết quả. Tuy vậy, do sự kết nhập các khoảng mờ
dựa trên độ đo về tính tương tự của các khoảng mờ đó đối
với thuộc tính huấn luyện nên nó không sai lệch đến kết
quả phân lớp cuối cùng.
Trong mỗi bước lặp của thuật toán, chúng ta đều phải
tính các khoảng mờ lớn nhất và thực hiện sát nhập các
khoảng mờ với chi phí là O(n2). Để ý rằng trong thuật
toán trên, chúng ta không thể chuyển việc tìm và sát nhập
các khoảng mờ lớn nhất ra khỏi vòng lặp. Do khi chúng
S1.Thuộc tính = L.Thuộc tính - X;
S2 = { Ixi
 Ixi ⊆ L, Ixi > T};
S2.Nút cha = L;
S2.Thuộc tính = L.Thuộc tính - X;
S = S + S1 + S2 − L; //Đánh dấu nút L đã
xét và bổ sung thêm các nút con của L ứng với
các tập S1 và S2
end
end if
else if (L là thuộc tính liên tục) then
begin
T = Ngưỡng có GainRatioHA lớn nhất;
S1 = { xi | xi ∈ L, xi ≤ T};
S1.Nút cha = L;
S1.Thuộc tính = L.Thuộc tính - X;
S2 = { xi | xi ∈ L, xi > T};
S2.Nút cha = L;
S2.Thuộc tính = L.Thuộc tính - X;
S = S + S1 + S2 − L; //Đánh dấu nút L đã xét và
bổ sung thêm 2 nút con của L ứng với tập S1 và S2
end
else //L là thuộc tính rời
begin
P = { xi | xi ∈ K, xi đơn nhất};
for each (xi ∈ P)
begin
Si = { xj
 xj ∈ L, xj = xi}
Si .Nút cha = L;
Si .Thuộc tính = L.Thuộc tính - X;
S = S + Si; //Đánh dấu nút L đã xét và bổ
sung tất cả các nút con của L ứng với tập Si
end
S = S − L;
end
end
ta tìm được một thuộc tính phù hợp để tạo cây thì tại các
điểm phân chia này, tập mẫu huấn luyện tương ứng trên
mỗi nhánh của cây thay đổi nên các khoảng mờ của thuộc
tính mờ thay đổi.
Với m là số thuộc tính, n là số thể hiện của tập huấn
luyện, độ phức tạp của C4.5 là O(m × n × log n); Với
HAC4.5*, trước tiên ta mất O(n2) cho mỗi một thuộc tính
mờ để tính các phân hoạch đoạn mờ. Sau đó, độ phức
tạp của thuật toán tại mỗi bước lặp theo thuộc tính mi là
O(n × log n) nếu mi không phải là thuộc tính mờ và là
O(n × n × log n) nếu là thuộc tính mờ do phải mất thêm
O(n) để tìm ngưỡng cho các khoảng mờ đối với thuộc tính
này và O(n2) để tìm khoảng mờ lớn nhất cho mỗi khoảng
mờ trong tập huấn luyện. Tuy vậy, việc tìm khoảng mờ lớn
nhất và xác định ngưỡng cho các khoảng mờ là tuần tự nên
47
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
độ phứt tạp của HAC4.5* là O(m × n3 × log n).
Tính đúng và tính dừng của thuật toán được rút ra từ
tính đúng của C4.5 và cách thức đối sánh giữa các giá trị
khoảng mờ.
IV. THỰC NGHIỆM VÀ SO SÁNH
Chương trình thực nghiệm được cài đặt bằng ngôn ngữ
Java (Eclipse Mars Release (4.5.0) trên máy tính có cấu
hình: Intel® CoreTMi5-2450, 4 CPU với mỗi CPU có tốc
độc xử lý là 2, 5 GHz, RAM có 4 GB, hệ thống 64 bit, cho
đồng thời cả ba thuật toán: C4.5, HAC4.5 và HAC4.5* trên
đồng thời hai bộ dữ liệu là Adult và Bank.
1. Kết quả trên dữ liệu dự đoán thu nhập Adult
Bộ dữ liệu Adult có hơn 40.000 mẫu tin gồm 14 thuộc
tính bao gồm dữ liệu rời rạc, liên tục, logic và mờ, trong
đó có 2 thuộc tính Age (Tuổi) và HoursPerWeek (Số giờ
làm việc) chứa cả dữ liệu rõ và mờ. Chúng tôi tách riêng
biệt 20.000 mẫu tin cho tập huấn luyện và dùng 20.000
mẫu còn lại để chọn ngẫu nhiên 5.000 mẫu dùng cho việc
kiểm tra. Kết quả cụ thể như Bảng I và Bảng II.
Bảng I
ĐỐI SÁNH HUẤN LUYỆN TRÊN DỮ LIỆU ADULT
Thuật toán Thời gian huấn luyện (s) Tổng số nút trên cây
C4.5 479,8 682
HAC4.5 1863,7 1873
HAC4.5* 2610,8 1624
Bảng II
TỶ LỆ KIỂM TRA TRÊN DỮ LIỆU ADULT
Thuật toán
Số mẫu kiểm tra
1000 2000 3000 4000 5000
C4.5 84,5% 85,7% 85,9% 86,2% 85,7%
HAC4.5 92,3% 91,5% 93,0% 95,0% 96,1%
HAC4.5* 92,8% 91,6% 93,2% 95,1% 96,3%
Bảng III
ĐỐI SÁNH HUẤN LUYỆN TRÊN DỮ LIỆU BANK
Thuật toán Thời gian huấn luyện (s) Tổng số nút trên cây
C4.5 2243 562
HAC4.5 4587,2 1061
HAC4.5* 6610,5 892
2. Kết quả trên dữ liệu dự đoán thu nhập trên dữ
liệu Bank
Bộ dữ liệu Bank có hơn 45.000 mẫu tin gồm 17 thuộc
tính bao gồm dữ liệu rời rạc, liên tục, logic và mờ, trong đó
thuộc tính Age (Tuổi) chứa cả dữ liệu rõ và mờ. Chúng tôi
tách riêng biệt 30.000 mẫu tin cho tập huấn luyện và dùng
15.000 mẫu còn lại để chọn ngẫu nhiên 5.000 mẫu dùng
cho việc kiểm tra. Kết quả được thể hiện trong Bảng III và
Bảng IV.
Bảng IV
TỶ LỆ KIỂM TRA TRÊN DỮ LIỆU BANK
Thuật toán
Số mẫu kiểm tra
1000 2000 3000 4000 5000
C4.5 61,3% 58,1% 58,3% 61,2% 64,7%
HAC4.5 76,6% 72,6% 72,9% 76,5% 80,9%
HAC4.5* 85,2% 83,5% 83,2% 82,1% 81,1%
2000
2500
3000
Thời gian (s)
0
500
1000
1500
C4.5 HAC4.5 HAC4.5*
Hình 4. Đối sánh thời gian huấn luyện và số nút của cây kết quả
trên dữ liệu Adult.
90.0%
92.0%
94.0%
96.0%
98.0%
oá
n 
đú
ng
78.0%
80.0%
82.0%
84.0%
86.0%
88.0%
1000 2000 3000 4000 5000
Tỷ
 lệ 
dự
 đo
Số lượng mẫu
C4.5
HAC4.5
HAC4.5*
Hình 5. Đối sánh tỷ lệ kiểm tra từ 1.000 đến 5.000 trên mẫu trên
dữ liệu Bank.
48
Tập V-2, Số 18 (38), 12/2017
5000
6000
7000
Thời gian (s)
0
1000
2000
3000
4000
C4.5 HAC4.5 HAC4.5*
Hình 6. Đối sánh thời gian huấn luyện và số nút của cây kết quả
trên dữ liệu Bank.
50.0%
60.0%
70.0%
80.0%
90.0%
oá
n 
đú
ng
0.0%
10.0%
20.0%
30.0%
40.0%
1000 2000 3000 4000 5000
Tỷ
 lệ 
dự
 đo
Số lượng mẫu
C4.5
HAC4.5
HAC4.5*
Hình 7. Đối sánh tỷ lệ kiểm tra từ 1.000 đến 5.000 trên mẫu trên
dữ liệu Bank.
3. Đánh giá kết quả thực nghiệm
Việc đồng thời cài đặt cả ba thuật toán C4.5, HAC4.5
và HAC4.5*, kết quả đánh giá trên cùng các bộ dữ liệu
là Adult và Bank đã cho phép chúng ta có các đánh giá
sau. Về chi phí huấn luyện, kết quả ở Hình 4 và Hình 6
cho chúng ta thấy rằng, thuật toán C4.5 luôn cho thời gian
nhanh nhất trong tất cả các bộ mẫu kể cả trong quá trình
huấn luyện hay kiểm tra, vì nó bỏ qua các giá trị mờ trong
tập mẫu nên không mất thời gian xử lý. HAC4.5 phải trải
qua quá trình xây dựng các ĐSGT cho các trường mờ và
chi phí để chuyển đổi các giá trị về đoạn [0, 1] ban đầu và
tại mỗi bước cần thêm thời gian để chọn đoạn phân chia
nên tốn nhiều thời gian hơn nhiều so với C4.5. HAC4.5*
vì mỗi bước lặp cần thêm thời gian để tìm các khoảng mờ
lớn nhất cho miền trị mờ của thuộc tính mờ tương ứng nên
HAC4.5* chậm nhất so với các thuật toán khác.
Về dự đoán, kết quả ở Hình 5 và Hình 7 cho chúng ta
thấy rằng, trước hết C4.5 bỏ qua các giá trị mờ trong tập
mẫu, chỉ quan tâm các giá trị rõ nên cây kết quả thu được
khá giản đơn vì ít nút. Tuy nhiên, do việc bỏ qua các giá trị
mờ nên làm mất dữ liệu tại các trường mờ, vì thế kết quả
dự đoán không cao. Thứ đến, HAC4.5 xây dựng một ĐSGT
tại các trường mờ và dùng nó để thuần nhất tập mẫu nên
chúng ta đã xử lý được các giá trị mờ mà vẫn giữ nguyên
các giá trị rõ nên không làm xuất hiện thêm sai số trong
quá trình phân hoạch,vì thế kết quả trong các quá trình dự
đoán tốt hơn nhiều so với C4.5. Tuy vậy, so với C4.5 thì
cây kết quả thu được không giản đơn vì có nhiều nút. Cuối
cùng, HAC4.5* cho kết quả tốt nhất vì trong quá trình huấn
luyện cây, chúng ta đã tìm được các điểm phân hoạch tốt
nhất tại các thuộc tính mờ nên ít cây kết quả thu được có
sai số ít hơn. Hơn nữa, việc tìm các khoảng mờ lớn nhất
và kết nhập các giá trị mờ trên thuộc tính mờ đã làm cho
lực lượng của các thuộc tính mờ tương ứng giảm, vì thế số
nút trên cây thu được cũng giảm nên cây kết quả thu được
là tốt nhất.
V. KẾT LUẬN
Bài toán phân lớp cây quyết định mờ đóng vai trò quan
trọng trong quá trình khai phá dữ liệu. Tuy vậy, việc phân
lớp bằng cây quyết định mờ dựa trên lý thuyết tập mờ luôn
gặp phải những hạn chế do xuất phát từ bản thân nội tại
của lý thuyết tập mờ. ĐSGT với lợi thế của mình đã trở
thành một công cụ thật sự hữu ích để giải quyết bài toán
phân lớp cây quyết định.
Bằng việc nhận ra các hạn chế của phương pháp định
lượng ngữ nghĩa theo điểm của việc sử dụng ĐSGT trong
quá trình huấn luyện, cách thức đối sánh theo khoảng mờ
là một giải pháp nhằm giảm thiểu sai số cho việc học cây
quyết định mờ. Bằng việc đưa ra khái niệm khoảng mờ lớn
nhất, bài báo đã đề xuất một phương pháp học quy nạp cây
quyết định mờ HAC4.5*, nhằm thu được cây quyết định
mờ đơn giản và hiệu quả cho bài toán phân lớp mờ.
TÀI LIỆU THAM KHẢO
[1] A. Bikas, E. Voumvoulakis, and N. Hatziargyriou, “Neuro-
fuzzy decision trees for dynamic security control of power
systems,” in 15th International Conference on Intelligent
System Applications to Power Systems (ISAP’09). IEEE,
2009, pp. 1–6.
[2] G. G. Anuradha, “Fuzzy decision tree construction in crisp
scenario through fuzzified trapezoidal membership func-
tion,” Internetworking Indonesia, vol. 7, no. 2, pp. 21–28,
2015.
[3] B. Chandra and P. P. Varghese, “Fuzzy SLIQ decision
tree algorithm,” IEEE Transactions on Systems, Man, and
Cybernetics, Part B (Cybernetics), vol. 38, no. 5, pp. 1294–
1301, 2008.
[4] H. Ishibuchi and T. Nakashima, “Effect of rule weights in
fuzzy rule-based classification systems,” IEEE Transactions
on Fuzzy Systems, vol. 9, no. 4, pp. 506–515, 2001.
[5] K. K. R. C and V. Babu, “A survey on issues of decision tree
and non-decision tree algorithms,” International Journal of
Artificial Intelligence and Applications for Smart Devices,
vol. 4, no. 1, pp. 9–32, 2016.
49
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
[6] S. Moustakidis, G. Mallinis, N. Koutsias, J. B. Theocharis,
and V. Petridis, “SVM-based fuzzy decision trees for clas-
sification of high spatial resolution remote sensing images,”
IEEE Transactions on Geoscience and Remote Sensing,
vol. 50, no. 1, pp. 149–169, 2012.
[7] M. Mehta, R. Agrawal, and J. Rissanen, “SLIQ: A fast
scalable classifier for data mining,” Advances in Database
Technology-EDBT’96, pp. 18–32, 1996.
[8] J. Shafer, R. Agrawal, and M. Mehta, “SPRINT: A Fast
Scalable Classifier for Data Mining,” IBM Almaden Reseach
Center, 1996.
[9] P. Fatima, D. Parveen, and M. Sathik, “Fuzzy decision tree
based effective imine indexing,” International Journal of
Computer Technology and Electronics Engineering, vol. 1,
2011.
[10] J. R. Quinlan, “Simplifying decision trees,” International
Journal of Man-Machine Studies, vol. 27, no. 3, pp. 221–
234, 1987.
[11] R. H. Tajiri, E. Z. Marques, B. B. Zarpelão, and
L. de Souza Mendes, “A new approach for fuzzy classifi-
cation in relational databases,” in International Conference
on Database and Expert Systems Applications. Springer,
2011, pp. 511–518.
[12] S. Ruggieri, “Efficient C4.5,” 2000.
[13] Z. Qin and Y. Tang, “Linguistic decision trees for classifica-
tion,” in Uncertainty Modeling for Data Mining. Springer,
2014, pp. 77–119.
[14] J. Zhang and V. Honavar, “Learning decision tree classifiers
from attribute value taxonomies and partially specified data,”
in Proceedings of the International Conference on Machine
Learning, Washington DC, 2003.
[15] M. Zeinalkhani and M. Eftekhari, “Comparing different
stopping criteria for fuzzy decision tree induction through
IDFID3,” Iranian Journal of Fuzzy Systems, vol. 11, no. 1,
pp. 27–48, 2014.
[16] N. C. Ho and N. Van Long, “Fuzziness measure on complete
hedge algebras and quantifying semantics of terms in linear
hedge algebras,” Fuzzy Sets and Systems, vol. 158, no. 4, pp.
452–471, 2007.
[17] N. C. Ho and H. V. Nam, “An algebraic approach to linguistic
hedges in Zadeh’s fuzzy logic,” Fuzzy Sets and Systems, vol.
129, no. 2, pp. 229–254, 2002.
[18] N. C. Ho and W. Wechler, “Hedge algebras: an algebraic
approach to structure of sets of linguistic truth values,” Fuzzy
Sets and Systems, vol. 35, no. 3, pp. 281–293, 1990.
[19] ——, “Extended hedge algebras and their application to
fuzzy logic,” Fuzzy Sets and Systems, vol. 52, no. 3, pp.
259–281, 1992.
[20] L. V. T. Lân, N. M. Hân, and N. C. Hào, “An algorithm
to building a fuzzy decision tree for data classification
problem based on the fuzziness intervals matching,” Journal
of Computer Science and Cybernetics, vol. 32, no. 4, pp.
367–380, 2017.
Lê Văn Tường Lân sinh năm 1974 tại
thành phố Huế. Ông nhận bằng Thạc sĩ,
chuyên ngành Công nghệ Thông tin tại
Trường Đại học Bách khoa Hà Nội, năm
2002. Hiện nay, ông đang là giảng viên
và là nghiên cứu sinh tại Khoa Công nghệ
Thông tin, Trường Đại học Khoa học, Đại
học Huế, chuyên ngành Khoa học Máy tính.
Lĩnh vực nghiên cứu của ông là khai phá dữ liệu và công nghệ
phần mềm.
Nguyễn Mậu Hân sinh năm 1957 tại Thừa
Thiên Huế. Ông nhận bằng Tiến sĩ tại
Viện Công nghệ Thông tin Hà Nội và được
phong hàm Phó Giáo sư năm 2013. Hiện
nay, ông là giảng viên tại Khoa Công nghệ
Thông tin, Trường Đại học Khoa học, Đại
học Huế. Lĩnh vực nghiên cứu của ông là
xử lý song song và phân tán, tính toán lưới
và điện toán đám mây.
Nguyễn Công Hào sinh năm 1976 tại Thừa
Thiên Huế. Ông nhận bằng Tiến sĩ tại Viện
Công nghệ Thông tin Hà Nội, năm 2008.
Hiện nay, ông là Giám đốc Trung tâm Công
nghệ Thông tin, Đại học Huế. Lĩnh vực
nghiên cứu của ông là cơ sở dữ liệu mờ, các
phương pháp tính toán mềm và các phương
pháp lập luận xấp xỉ.
50