Luận án Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử

luyện là vấn đề đầu tiên phải quan tâm. Thông qua việc phân loại các thuộc tính 
rời rạc, luận án nhằm cung cấp sự lựa chọn xác đáng cho việc lựa chọn tập mẫu 
trong quá trình huấn luyện. 
 Trong tập mẫu huấn luyện có m thuộc tính, chiều cao tối đa của cây kết 
quả là m – 1, theo Định nghĩa 1.19, các thuộc tính rời rạc có lực lượng lớn hơn m 
rất có khả năng làm xuất hiện cây dàn trải theo chiều ngang tại nút đó vì có chiều 
rộng của nhánh lớn hơn chiều sâu của cây. Tuy vậy, sự phân nhánh của cây còn 
phụ thuộc vào lực lượng của thuộc tính huấn luyện Y tức là phụ thuộc vào giá trị 
|Y|, vì chúng ta cần phân chia đến các lớp thuần nhất theo mỗi giá trị của Y. Do 
vậy, khi xét tính dàn trải theo chiều ngang của cây, ta cần phải xét đến số lớp 
phân chia trên Y cùng với chiều cao của cây. Định nghĩa sau nhằm xác định 
ngưỡng có thể cho phép dàn trải đối với mỗi nút trên cây. 
Định nghĩa 2.1. Thuộc tính Ai D được gọi là thuộc tính có giá trị riêng biệt 
(gọi tắt là thuộc tính riêng biệt) nếu như nó là thuộc tính rời rạc và |Ai| > (m - 1) 
× |Y|. Tập các thuộc tính có giá trị riêng biệt trong D ký hiệu là D*. 
Mệnh đề 2.1. Trong cây quyết định, nếu có một nút được tạo là ứng với một 
thuộc tính riêng biệt trong quá trình huấn luyện thì đó là một cây dàn trải. 
 Chứng minh: thật vậy, mẫu D có m thuộc tính nên có chiều cao tối đa có 
thể của cây sau khi huấn luyện là m - 1. Do vậy, tính đúng của mệnh đề được suy 
ra từ Định nghĩa 2.1. 
 Như chúng ta đã biết, trong các kho dữ liệu nghiệp vụ, do cần phải lưu trữ 
thông tin phản ảnh thế giới thực nên nhiều thuộc tính được lưu trữ không có khả 
năng dự đoán mà chỉ có ý nghĩa lưu trữ nhằm mục đính diễn giải thông tin. Các 
định nhĩa sau nhằm để phân loại các thuộc tính có khả năng tham gia trong quá 
trình huấn luyện hay không. 
 40 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
Định nghĩa 2.2. Cho tập mẫu D. Thuộc tính 푖 D mà giữa các phần tử 푖푗 , 푖 
với j ≠ k là không sánh được thì ta gọi Ai là thuộc tính ghi nhớ trong tập mẫu. 
Tập các thuộc tính này trong D ký hiệu là DG. 
Mệnh đề 2.2. Cho tập mẫu D. Nếu thuộc tính Ai D là thuộc tính ghi nhớ thì ta 
loại Ai ra khỏi mẫu D mà không làm thay đổi cây quyết định thu được. 
 Chứng minh: hiển nhiên, bởi ta không thể so sánh giữa các phần tử 
 푖푗 với 푖 của Ai để tính hàm Gain(Ai, D) nên không tồn tại lợi ích thông tin của 
mỗi bộ trên Ai. Vì thế Ai không thể xuất hiện trên cây kết quả nên ta loại Ai ra 
khỏi D mà không làm thay đổi cây quyết định thu được. 
Mệnh đề 2.3. Nếu trong tập mẫu huấn luyện chứa thuộc tính Ai là khoá của tập 
D thì cây quyết định thu được là quá khớp tại nút Ai. 
 Chứng minh: thật vậy, với thuộc tính Ai có Dom( 푖) = { 푖1 , 푖2 ,  , 푖푛 }, 
do Ai là khoá nên ta có 푖푗 ≠ 푖 , i ≠ k. Như thế, mẫu D được phân ra làm n 
phân hoạch, mà mỗi phân hoạch chỉ có 1 bộ nên  푖푗 Ai, hàm E(Ai, D) = 0. 
Hàm xác định lợi ích thông tin nhận được trên thuộc tính Ai ở Công thức 1.9 đạt 
giá trị cực đại, vì thế Ai được chọn làm điểm phân tách cây. Tại đây, cây được 
phân chia làm n nút, mỗi cạnh tương ứng được gán nhãn 푖푗 , đây là một cây dàn 
trải theo chiều ngang tại nút ứng với Ai. Do tính duy nhất của khoá nên không có 
giá trị trùng khớp khi so sánh tại nút này trong quá trình dự đoán. Vậy cây kết 
quả thu được là quá khớp tại nút Ai, theo Định nghĩa 1.19. 
 Với dữ liệu xét ở Bảng 2.1, các thuộc tính sau là không hiệu quả khi chọn 
nó trong các tập mẫu huấn luyện: 
 - Thuộc tính ID, PhiếuĐT là thuộc tính khoá. 
 - Thuộc tính HọVàTên là thuộc tính có giá trị riêng biệt. 
2.2.2. Ảnh hƣởng từ phụ thuộc hàm giữa các thuộc tính trong tập huấn 
luyện 
Mệnh đề 2.4. Cho mẫu D với thuộc tính quyết định Y. Nếu có phụ thuộc hàm Ai 
 Aj và ta đã chọn Ai làm nút phân tách trên cây thì mọi nút con của nó sẽ không 
 41 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
nhận Aj làm nút phân tách. 
 Chứng minh: thật vậy, giả sử |Ai| = k, khi chọn Ai làm nút phân tách trên 
cây thì tại nút này ta có k nhánh. Không mất tính tổng quát, các nhánh của cây 
lần lượt được gán các giá trị là 푖푗 , j = 1, , k. Do Ai Aj nên tại nhánh bất kỳ 
thì trên mẫu huấn luyện tương ứng D’, lúc này trên thuộc tính Aj sẽ có cùng 1 giá 
trị. Như thế Gain(Aj, D’) = 0 là nhỏ nhất nên Aj không thể chọn để làm nút phân 
tách cây. 
Mệnh đề 2.5. Trên mẫu D với thuộc tính quyết định Y, nếu có phụ thuộc hàm Ai 
 Aj thì lượng thông tin nhận được trên Ai không nhỏ hơn lượng thông tin nhận 
được trên Aj. 
 Chứng minh: thật vậy, giả sử thuộc tính quyết định Y có k giá trị. Do A1 
 A2 nên |A1| |A2|. Theo công thức (1.9), lượng thông tin nhận được trên thuộc 
tính Ai là Gain(Ai, D). Nên nếu |A1| = |A2| thì trên A1 hay A2 đều có k phân hoạch 
như nhau nên Gain(A1, D) = Gain(A2, D). Ngược lại nếu |A1| > |A2| tức tồn tại 
 1푖 , 1푗 A1, 1푖 1푗 mà trên tương ứng trên A2 thì 2푖 = 2푖 . Lúc này 2 phân 
hoạch trên A1 được gộp thành 1 phân hoạch trên A2 nên Entropy tương ứng trên 
A2 lớn hơn. Vậy Gain(A1, D) > Gain(A2, D). 
 Từ Mệnh đề 2.5, ta dễ dàng suy ra hệ quả nhằm giới hạn các thuộc tính 
trong tập huấn luyện như sau: 
Hệ quả 2.1. Nếu có phụ thuộc hàm A1 A2 mà A1 không phải là thuộc tính khóa 
của mẫu D thì thuộc tính A2 không được chọn làm nút phân tách cây. 
 Với dữ liệu được xét ở Bảng 2.1, thuộc tính PhụCấp là phụ thuộc hàm vào 
thuộc tính không khóa Lương nên không hiệu quả khi chọn trong các tập mẫu 
huấn luyện cây. 
 Như vậy, với các kho dữ liệu nghiệp vụ được lưu trữ bao gồm các thông tin 
mô tả về phân loại dữ liệu các thuộc tính và các phụ thuộc hàm của chúng, chúng 
ta có thể chọn được tập mẫu huấn luyện phù hợp thông qua thuật toán “chọn mẫu 
đặc trưng” cho quá trình huấn luyện cây như sau: 
 42 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
Thuật toán tìm tập huấn luyện đặc trƣng từ dữ liệu mẫu. 
Vào : Tập mẫu huấn luyện D được chọn từ dữ liệu mẫu; 
Ra : Tập mẫu huấn luyện đặc trưng D*; 
Mô tả thuật toán: 
Begin 
 For each i = 1 to m do 
 Begin 
 If (Ai {Khoá, Ghi nhớ}) then D = D - Ai ; 
 End; 
 i = 1; 
 While (i < m) do 
 Begin 
 j = i +1; 
 While (j ≤ m) do 
 Begin 
 If (Ai Aj and (Ai không phải thuộc tính khóa trong D)) 
 then D = D – Aj 
 Else 
 If (Aj Ai and (Aj không phải thuộc tính khóa trong D)) 
 then D = D – Ai; 
 j = j+1; 
 End; 
 i = i + 1; 
 End; 
End; 
 Tính đúng đắn của thuật toán được suy ra từ các mệnh đề ở trên. Với tập 
dữ liệu nghiệp vụ được chọn có m thuộc tính, do chúng ta phải duyệt qua 2 lần 
lồng nhau các thuộc tính hiện có nên thuật toán có độ phức tạp O(m2). 
 43 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
2.3. Phân lớp dữ liệu bằng cây quyết định dựa trên ngƣỡng miền trị 
thuộc tính 
2.3.1. Cơ sở của việc xác định ngƣỡng cho quá trình học phân lớp 
 Như chúng ta đã xét, các thuật toán học quy nạp cây quyết định đều dựa 
vào việc chọn thuộc tính có lượng thông tin tốt nhất để phân tách cây và sự phân 
chia tại mỗi nút phụ thuộc vào kiểu của thuộc tính là liên tục hay rời rạc. Tất cả 
các thuật toán đều cố định cách phân chia cho mọi thuộc tính rời rạc của tập 
huấn luyện theo nhị phân hoặc k-phân. 
 - Đối với cách chia k-phân, một điều dễ thấy là nếu thuộc tính A có lực 
lượng lớn sẽ làm cho số nút của cây tại một cấp tăng lên nhanh. Điều này làm 
tăng chiều rộng của cây nên cây sẽ dàn trải theo chiều ngang. Hơn nữa, cách chia 
này có khả năng dẫn đến lỗi khi dữ liệu không thể đoán nhận được lớp. Mặc dù 
vậy chia k-phân theo thuộc tính rời rạc có ưu điểm là độ phức tạp thấp, bởi vì 
sau khi phân thì thuộc tính đó không cần phải sử dụng lại nữa. 
 - Cách chia nhị phân theo giá trị tại điểm phân chia [48] [87] không làm 
tăng chiều rộng của cây, bởi cho dù k có lớn bao nhiêu cũng chỉ chia theo 2 nút, 
một nút là giá trị được chọn và một nút là tập còn lại. Tuy nhiên, điều này lại làm 
tăng nhanh chiều sâu của cây. Cách chia nhị phân theo tập hợp tại điểm phân 
chia [47] [52] luôn tách thuộc tính rời rạc làm 2 tập con nên và chi phí tính toán 
rất lớn và khó khăn trong việc duyệt cây kết quả cho quá trình dự đoán. 
 Từ những nhận định trên, ta nhận thấy cần phải xây dựng một thuật toán 
học với cách chia hỗn hợp nhị phân, k-phân theo từng thuộc tính nhằm có được 
cây với chiều rộng và chiều sâu hợp lý cho quá tình huấn luyện. 
2.3.2. Thuật toán MixC4.5 dựa trên ngƣỡng miền trị thuộc tính 
 Với tập mẫu huấn luyện D với m thuộc tính A1, A2,  Am có lực lượng 
tương ứng của mỗi thuộc tính là |A1|, |A2|,  |Am|. Ta gọi k là ngưỡng giới hạn sự 
phân chia tại mỗi thuộc tính theo nhị phân, tức là nếu lực lượng của thuộc tính 
nhỏ hơn một giá trị được lựa chọn k cho trước thì sẽ phân theo k-phân, ngược lại 
phân theo nhị phân. 
 Do tính chất dàn trải của cây chỉ xảy ra trên thuộc tính rời rạc nên khi Ai 
không phải là thuộc tính riêng biệt (theo Định nghĩa 2.1) thì |Ai| < (m - 1) × |Y|. 
 44 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
Với thuộc tính Ai có |Ai| < (m - 1) × |Y| thì các nhánh của cây không lớn hơn 
chiều cao nên cây kết quả không dàn trải theo chiều ngang. Khi |Ai| ≥ (m - 1) × 
|Y|, ta có sự phân chia theo chiều ngang của nút tương ứng lớn hơn chiều rộng 
của cây. Tuy vậy, vì tính chất thuần nhất của sự phân lớp nên ta cần phân chia 
các nhánh của cây theo các giá trị riêng biệt của thuộc tính dự đoán Y. Do vậy, 
giá trị (m - 1) × |Y| sẽ được chọn để xác định ngưỡng phân chia. Khi |Ai| < (m - 
1) × |Y| thì ta sẽ phân chia theo k-phân như C4.5. Ngược lại thì |Ai| ≥ (m - 1) × 
|Y| nên có thể xảy ra tình trạng quá khớp tại nút này, vì vậy ta phân chia thuộc 
tính này theo nhị phân của SPRINT. 
 Với tập mẫu dữ liệu nghiệp vụ huấn luyện D có m thuộc tính, ta có thuật 
toán MixC4.5 xây dựng cây quyết định S như sau: 
Thuật toán MixC4.5 
Vào: mẫu huấn luyện D có n bộ, m thuộc tính dự đoán, thuộc tính quyết định Y. 
Ra: Cây quyết định S. 
Mô tả thuật toán: 
ChonMauDacTrung(D); //theo Mục 2.2.2 
Tính ngưỡng k cho các thuộc tính; 
Khởi tạo tập các nút lá S = D; 
For each (nút lá L thuộc S) do 
 If (L thuần nhất) or (L là rỗng) then 
 Gán nhãn cho nút tương ứng với giá trị thuần nhất của L; 
 Else 
 Begin 
 X = Thuộc tính tương ứng có GainRatio lớn nhất; 
 Gán nhãn cho nút tương ứng với tên thuộc tính X; 
 If (L là thuộc tính liên tục) then //Phân chia theo C4.5 
 Begin 
 Chọn ngưỡng T tương ứng có Gain lớn nhất trên X; 
 S1= {xi| xi Dom(L), xi ≤ T}; S2= {xi| xi Dom(L), xi > T}; 
 Tạo 2 nút con cho nút hiện tại tương ứng với hai tập S1 và S2; 
 45 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 Đánh dấu nút L đã xét; 
 End 
 Else //L là thuộc tính rời rạc 
 //phân chia k-phân theo C4.5 khi |L| không vượt qua ngưỡng k 
 If |L| < k then 
 Begin 
 P = {xi| xi K, xi đơn nhất}; 
 For each (xi P) do 
 Begin 
 Si = {xj| xj Dom(L), xj = xi}; 
 Tạo nút con thứ i cho nút hiện tại tương ứng với Si; 
 End; 
 End 
 Else 
 //phân chia nhị phân theo SPRINT tại giá trị tương ứng khi 
 //có |L| vượt ngưỡng k 
 Begin 
 Lập ma trận đếm cho các giá trị trong L; 
 T = Giá trị trong L có Gain lớn nhất; 
 S1= {xi| xi Dom(L), xi = T};S2= {xi| xi Dom(L), xi ≠ T}; 
 Tạo 2 nút con cho nút hiện tại ứng với hai tập S1 và S2; 
 End; 
 Đánh dấu nút L đã xét; 
 End; 
 End; 
 Với m là số thuộc tính, n là số thể hiện của tập huấn luyện. Tuần tự, chúng 
ta mất O(m × n) vì phải duyệt qua toàn bộ mẫu để xác định ngưỡng k cho m 
thuộc tính, là ngưỡng xác định sẽ chia tách theo nhị phân hay k-phân và tuần tự. 
Sau đó chúng ta mất chi phí O(m2 × n) để lựa chọn các thuộc tính đặc trưng cho 
tập mẫu huấn luyện nhằm tránh tình trạng quá khớp trên cây. 
 46 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 Trong quá trình huấn luyện, với thuộc tính liên tục MixC4.5 hoàn toàn 
trùng khớp với C4.5 và SPRINT. Đối với thuộc tính rời rạc, MixC4.5 được thiết 
kế dựa trên sự tổng hợp của C4.5 và SPRINT, khi lực lượng của thuộc tính đang 
xét chưa vượt ngưỡng k, do chúng ta sử dụng k-phân theo C4.5 nên độ phức tạp 
lúc này là O(m × n × log n). Ngược lại, khi vượt quá ngưỡng k, chúng ta phân 
chia nhị phân theo giá trị theo SPRINT nên độ phức tạp lúc này là O(m × n2 × 
log n). Vậy độ phức tạp của thuật toán MixC4.5 là O(m × n2 × log n). 
 Tính đúng và tính dừng của thuật toán được rút ra từ các thuật toán C4.5 
và SPRINT do MixC4.5 được kết hợp từ hai thuật toán này. 
2.3.3. Cài đặt thử nghiệm và đánh giá thuật toán MixC4.5 
 Chương trình thực nghiệm được cài đặt bằng ngôn ngữ Java Eclipse Mars 
Release 4.50 trên máy tính có cấu hình: Processor: Intel® Core™i5-2450 CPU 
@ 2.50GHz (4CPUs), ~ 2.50 GHz, RAM4GB, System type 64bit. 
 a. Với tập mẫu huấn luyện gồm 1500 bảng ghi và 500 bộ giá trị kiểm tra 
được lấy từ 2155 bộ dữ liệu từ các bảng Customers, Details, OrderDetails, 
Products của cơ sở dữ liệu Northwind, các thông số cụ thể như Bảng 2.2. Kết 
quả thực nghiệm đo được ở các Bảng 2.3 và Bảng 2.4. 
 Bảng 2.2. Thông số thuộc tính tập huấn luyện chọn từ cơ sở dữ liệu Northwind 
STT Tên trƣờng Lực lƣợng Kiểu thuộc tính Miền trị 
 1 Customers.CompanyName 91 Rời rạc 
 2 Customers.ContactName 91 Rời rạc 
 3 Customers.ContactTitle 12 Rời rạc 
 4 Customers.City 69 Rời rạc 
 5 Customers.Region 19 Rời rạc 
 6 Customers.Phone 91 Rời rạc 
 7 Products.ProductName 77 Rời rạc 
 8 Products.SupplierID 29 Rời rạc 
 9 Products.CategoryID 8 Rời rạc 
 47 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
10 Products.QuantityPerUnit 70 Rời rạc 
11 Products.UnitPrice 62 Liên tục [2.50, 265.0] 
12 Products.UnitsInStock 51 Liên tục [0, 125] 
13 Products.UnitsOnOrder 10 Liên tục [0, 100] 
14 Products.ReorderLevel 7 Liên tục [0, 30] 
15 Products.Discontinued 2 Logic 
16 Orders.CustomerID 89 Rời rạc 
17 Orders.EmployeeID 9 Liên tục [1, 9] 
18 Orders.OrderDate 480 Rời rạc 
19 Orders.RequiredDate 454 Rời rạc 
20 Orders.ShippedDate 388 Rời rạc 
21 Orders.Freight 79 Liên tục [0.02, 1007.6] 
22 Orders.ShipCity 70 Rời rạc 
23 Orders.ShipRegion 20 Rời rạc 
24 OrderDetails.ProductID 77 Liên tục [1, 77] 
25 OrderDetails.UnitPrice 116 Liên tục [2.0, 263.5] 
26 OrderDetails.Quantity 55 Liên tục [1, 130] 
27 OrderDetails.Discount 11 Liên tục [0.0, 0.25] 
 Bảng 2.3. Bảng so sánh kết quả huấn luyện của thuật toán MixC4.5 với 1000 
 mẫu trên cơ sở dữ liệu Northwind 
 Thuật toán Thời gian (s) Tổng số nút Độ chính xác (%) 
 C4.5 11.2 389 69.2 
 SLIQ 220.2 89 76.4 
 SPRINT 89.2 122 79.8 
 MixC4.5 73.3 130 78.2 
 48 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 Bảng 2.4. Bảng so sánh kết quả huấn luyện của thuật toán MixC4.5 với 1500 
 mẫu trên cơ sở dữ liệu Northwind 
 Thuật toán Thời gian (s) Tổng số nút Độ chính xác (%) 
 C4.5 20.4 552 76.4 
 SLIQ 523.3 162 82.4 
 SPRINT 184.0 171 83.2 
 MixC4.5 186.6 172 86.6 
 b. Với tập mẫu huấn luyện gồm 5000 bảng ghi và các bộ dữ liệu kiểm tra 
gồm 500 và 1000 mẫu được lấy từ 8000 bộ dữ liệu của cơ sở dữ liệu Mushroom, 
các thông số cụ thể như Bảng 2.5. Kết quả thực nghiệm của quá trình huấn luyện 
và kiểm tra được trình bày ở Bảng 2.6. 
 Bảng 2.5. Thông số thuộc tính tập huấn luyện từ cơ sở dữ liệu Mushroom 
 STT Tên trƣờng Lực lƣợng Kiểu thuộc tính Miền trị 
 1 Bruises 2 Rời rạc 
 2 Capshape 6 Rời rạc 
 3 CapSurface 4 Rời rạc 
 4 CapColor 10 Rời rạc 
 5 Bruises 2 Rời rạc 
 6 Odor 9 Rời rạc 
 7 GillAttachment 2 Rời rạc 
 8 GillSpacing 2 Rời rạc 
 9 GillSize 2 Rời rạc 
 10 GillColor 12 Rời rạc 
 11 StalkShape 2 Rời rạc 
 12 StalkRoot 5 Rời rạc 
 13 StalkSurfaceAboveRing 4 Rời rạc 
 14 StalkSurfaceBelowRing 4 Rời rạc 
 49 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 15 StalkColorAboveRing 9 Logic 
 16 StalkColorBelowRing 9 Rời rạc 
 17 VeilType 9 Rời rạc 
 18 VeilColor 4 Rời rạc 
 19 RingNumber 3 Rời rạc 
 20 RingType 5 Rời rạc 
 21 SporePrintColor 9 Rời rạc 
 22 Population 62 Mờ Rõ: [1, 50] 
 23 Habitat 126 Mờ Rõ: [20, 90] 
 24 Classes 2 Logic 
 Bảng 2.6. Bảng so sánh kết quả của thuật toán MixC4.5 với 5000 mẫu huấn 
 luyện trên cơ sở dữ liệu có chứa thuộc tính mờ Mushroom 
 Thời gian Độ chính xác (%) Độ chính xác (%) 
 Thuật toán 
 huấn luyện (s) 500 mẫu kiểm tra 1000 mẫu kiểm tra 
 C4.5 18.9 54.8 51.2 
 SLIQ 152.3 51.8 52.2 
 SPRINT 60.1 54.2 54.6 
 MixC4.5 50.2 54.8 54.6 
 c. Từ kết quả thu được, chúng ta có các nhận xét, đánh giá như sau: 
  Thời gian huấn luyện: Thuật toán C4.5 luôn thực hiện k-phân tại các 
thuộc tính rời rạc và loại bỏ các thuộc tính của tập huấn luyện ở mỗi bước phân 
chia, nên C4.5 luôn đạt tốc độ thực hiện nhanh nhất. Thời gian xử lý của SLIQ là 
lớn nhất do phải thực hiện các phép tính Gini trên mỗi giá trị rời rạc của thuộc 
tính rời rạc. Do cách phân chia của MixC4.5 trộn lẫn giữa C4.5 và SPRINT và 
C4.5 nhanh hơn SPRINT nên thời gian huấn luyện của MixC4.5 khá tương đồng 
tốt với SPRINT, thể hiện ở Hình 2.3. 
 50 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 600
 500
 400
 300
 200
 Thời giánThời huấn luyện (s)
 100
 0
 1000 mẫu (Northwind) 1500 mẫu (Northwind) 5000 mẫu (Mushroom)
 C45 SLIQ SPRINT MixC4.5 
 Hình 2.3. So sánh thời gian huấn luyện của MixC4.5 với các thuật toán khác. 
  Kích thƣớc cây kết quả: SLIQ do thực hiện cách chia nhị phân theo 
tập hợp nên số nút của nó luôn nhỏ nhất và C4.5 luôn phân chia k-phân nên số 
nút luôn lớn nhất. Thuật toán MixC4.5 tương đồng kém với SPRINT do số lượng 
nút của thuật toán SPRINT ít hơn C4.5, Hình 2.4. 
 600
 500
 Số lƣợng Sốnút 400 1000 mẫu 
 (Northwind)
 300
 1500 mẫu 
 200 (Northwind)
 100
 0
 C45 SLIQ SPRINT MixC4.5 
 Hình 2.4. So sánh số nút trên cây kết quả của MixC4.5 với các thuật toán khác. 
 51 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
 100%
 90%
 80%
 Tỷ lệ đúng (%) đúng lệ Tỷ 70%
 60%
 50%
 40%
 30%
 20%
 10%
 0%
 500/1000 mẫu 500/1500 mẫu 500/5000 mẫu 1000/5000 mẫu 
 (Northwind) (Northwind) (Mushroom) (Mushroom)
 C45 SLIQ SPRINT MixC4.5 
 Hình 2.5. So sánh tỷ lệ đúng trên kết quả của MixC4.5 với các thuật toán khác. 
  Hiệu quả dự đoán: Thuật toán MixC4.5 cải tiến từ sự kết hợp các 
thuật toán C4.5 và SPRINT nên cho cây kết quả có khả năng dự đoán khả quan 
hơn các thuật toán kinh điển. Trong tất cả các trường hợp dự đoán trên cả dữ liệu 
rõ và dữ liệu có chứa giá trị mờ, MixC4.5 luôn cho kết quả dự đoán phù hợp hơn 
C4.5, SLIQ và SPRINT do chúng ta đã hạn chế được tình huống “quá khớp” trên 
cây kết quả. 
 Tuy nhiên, đối sánh giữa các tập huấn luyện không có thuộc tính mờ 
(Northwind) và các tập huấn luyện có chứa thuộc tính mờ (Mushroom) thì khả 
năng dự đoán của MixC4.5 còn có sự chênh lệch lớn, khả năng dự đoán khi dữ 
liệu có chứa giá trị mờ chưa cao. Trong tất cả các trường hợp, các thuật toán 
kinh điển và thuật toán đề xuất MixC4.5 đều cho kết quả dự đoán đúng có tỷ lệ 
nhỏ hơn 60%, Hình 2.5. Điều này hoàn toàn hợp lý vì trong quá trình học các 
thuật toán đang xét không thể xử lý nên chọn giải pháp bỏ qua các giá trị mờ, vì 
thế kết quả dự đoán có sai số lớn. 
 52 
 Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử 
2.4. Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đối sánh điểm mờ 
2.4.1. Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định mờ 
 Như chúng ta đã biết, bài toán phân lớp mờ đã và đang được nhiều tác giả 
nghiên cứu và ứng dụng, các phương pháp được biết đến như lập luận xấp xỉ mờ 
[5], hệ nơ-ron mờ [9], [12], [23], luật kết hợp mờ [8], [22], cây quyết định mờ 
[16], [17], [45], Các phương pháp này sử dụng các phép toán truyền thống 
trên tập mờ để lập luận cho kết quả đầu ra. Mô hình thể hiện cho quá trình phân 
lớp mờ này bao gồm 2 giai đoạn, thể hiện như ở Hình 2.6. 
 - Giai đoạn 1: xác định hệ mờ bao gồm việc lựa chọn các biến vào, các 
tham số mờ, phân hoạch các khoảng mờ của các biến vào, lập luận đầu ra cho hệ 
mờ.