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ử
![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ử trang 1 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ử trang 1](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-1_V1LFgdWrrd.jpg)
Trang 1
![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ử trang 2 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ử trang 2](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-2_3X8DuOweyW.jpg)
Trang 2
![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ử trang 3 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ử trang 3](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-3_YnIp5vYFHc.jpg)
Trang 3
![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ử trang 4 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ử trang 4](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-4_BV9R2I05LY.jpg)
Trang 4
![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ử trang 5 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ử trang 5](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-5_BOvNPy0Rqw.jpg)
Trang 5
![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ử trang 6 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ử trang 6](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-6_HsXULC86sJ.jpg)
Trang 6
![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ử trang 7 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ử trang 7](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-7_E6HwJ3qwJ4.jpg)
Trang 7
![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ử trang 8 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ử trang 8](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-8_YA4XRD88hB.jpg)
Trang 8
![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ử trang 9 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ử trang 9](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-9_g7KOTf87Nv.jpg)
Trang 9
![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ử trang 10 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ử trang 10](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/227/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai-trang-10_LaqCUdBW6a.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "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ử", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
Tóm tắt nội dung tài liệu: 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ử
![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ử 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ử](https://s1.thuvienluanvan.org/d2fndtiye73ondva/thumb/2024/03/02/luan-an-phan-lop-du-lieu-bang-cay-quyet-dinh-mo-dua-tren-dai_ENy1Di060F.jpg)
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ờ.
File đính kèm:
luan_an_phan_lop_du_lieu_bang_cay_quyet_dinh_mo_dua_tren_dai.pdf
1. ThongtinMoiCuaLuanAn-TiengViet.pdf
2. ThongTinMoiCuaLuanAn-TiengAnh.pdf
3. TomTat LuanAn TiengViet.pdf
4. TomTat LuanAn TiengAnh.pdf
6. TrichYeuLuanAn-TiengViet.pdf
7. TrichYeuLuanAn-TiengAnh.pdf