Đề tài Mô hình cây quyết định

 =  − ∑ || ||   =  − !"# $ %& ' (ắ)*+ − & %&  Â, − $ %&  -ư = 0.94 − $ %& × 0.971 − & %& × 0 − $ %& × 0.971 ≈ 0.246 Tư tượng đối với các thuộc tính Nhiệt độ, Độ ẩm, Gió ta có Gain tương ứng như sau: - Gain(S,ND)= 0.029 Decision Tree 20 - Gain(S,DA)= 0.151 - Gain(S,G)= 0.048 Chọn Quang cảnh làm thuộc tính phân lớp vì có Gain lớn nhất - Vẽ cây quyết định: Do Quang cảnh=Nắng và Quang cảnh=Mưa chưa xác định được thuộc tính phân lớp nên ta chia tập huấn liệu thành 2 bảng như hình trên và tiếp tục tìm thuộc tính phân lớp cho 2 bảng mẫu huấn luyện. Kết quả cuối cùng ta có cây quyết định sau: Quang Cảnh Có [D1, D2, D8, D9, D11] [D4, D5, D6, D10, D14][D3, D7, D12, D13] Nắng Âm u Mưa ??? ??? S Nắng [2+,3-] S Âm u [4+,0-] S Mưa [3+,2 Decision Tree 21 Từ cây quyết định trên tạo ra các luật: – R1: IF QC=Âm u THEN Chơi Tennis=Có. – R2: IF QC=Nắng AND Độ ẩm=TB THEN Chơi Tennis=Có. – R3: IF QC=Nắng AND Độ ẩm=Cao THEN Chơi Tennis=Không. – R4: IF QC=Mưa AND Gió=Nhẹ THEN Chơi Tennis=Có – R5: IF QC=Mưa AND Gió=Mạnh THEN Chơi Tennis=Không Nhận xét: Với việc tính toán giá trị Gain để lựa chọn thuộc tính tối ưu cho việc triển khai cây, thuật toán ID3 được xem là một cải tiến của thuật toán CLS. Tuy nhiên thuật toán ID3 còn các vấn đề chưa được giải quyết như sau: o Vấn đề overfitting (sẽ trình bày kỹ ở mục 4) o Độ đo Information Gain chưa thật sự tốt vì còn thiên về các thuộc tính có nhiều giá trị. o Xử lý các thuộc tính có kiểu giá trị liên tục (ví dụ như kiểu số thực) o Xử lý các bộ học thiếu giá thuộc tính (missing-value attributes) Quang Cảnh Có [D1, D2, D8, D9, D11] [D4, D5, D6, D10, D14][D3, D7, D12, D13] Nắng Âm u Mưa S Nắng [2+,3-] S Âm u [4+,0-] S Mưa [3+,2 Độ ẩm Có khôn CaoTB S TB [2+,0-] S cao[0+,3-] Gió Có Nhẹ S Nhẹ [3+,0-] Decision Tree 22 o Xử lý các thuộc tính có chi phí (cost) khác nhau Vấn đề này sẽ được giải quyết trong thuật toán C4.5 sau đây. 3.3 Thuật toán C4.5 Thuật toán C4.5 cũng được tác giả Quinlan phát triển và công bố vào năm 1996. Thuật toán này là một thuật toán được cải tiến từ thuật toán ID3 và giải quyết hầu hết các vấn đề mà ID3 chưa giải quyết như đã nêu trên. Nó thực hiện phân lớp tập mẫu dữ liệu theo chiến lược ưu tiên theo chiều sâu (Depth - First). Thuật toán xây dựng cây quyết định C4.5 Mô tả thuật toán dưới dạng giả mã như sau [2]: Function xay_dung_cay(T) { ; If <Kiểm tra các mẫu, nếu thuộc cùng một lớp hoặc có rất ít mẫu khác lớp>Then Else ; For Do ; <Tại nút N, thực hiện việc kiểm tra để chọn ra thuộc tính có giá trị Gain tốt nhất (lớn nhất). Gọi N.test là thuộc tính có Gain lớn nhất>; If Then <Tìm ngưỡng cho phép tách của N.test>; For Do ( T` được tách ra theo quy tắc: - Nếu N.test là thuộc tính liên tục tách theo ngưỡng ở bước 5 - Nếu N.test là thuộc tính phân loại rời rạc tách theo các giá trị của thuộc tính này. ) { If } Then ; Else <Gán nút con này là nút được trả về bằng cách gọi đệ qui lại đối với hàm xay_dung_cay(T'), với tập T'>; } ; ; } Decision Tree 23 3.4 Một số cài tiến của thuật toán C4.5 so với thuật toán ID3 3.4.1 Chọn độ đo Gain Ratio Thuật toán ID3 sử dụng độ đo Information Gain để tìm thuộc tính phân lớp tốt nhất nhưng xu hướng của Information Gain là ưu tiên chọn thuộc tính có nhiều giá trị làm thuộc tính phân lớp. Thật vậy, ta xét ví dụ với tập huấn luyện sau: Outlook Temp Humidity Windy Play A Hot High Weak No A Hot High Strong No B Hot High Weak Yes E Mild High Weak Yes A Cool Normal Weak Yes B Cool Normal Strong No E Cool Normal Strong Yes A Mild High Weak No D Cool Normal Weak Yes E Mild Normal Weak Yes A Mild Normal Strong Yes B Mild High Strong Yes C Hot Normal Weak Yes D Mild High Strong No Test bằng Tool WEKA ta được kết quả sau: Decision Tree 24 Rõ ràng Information Gain chọn thuộc tính có nhiều giá trị (Outlook) làm thuộc tính phân lớp. Kết quả cho cây quyết định phức tạp hơn, sinh ra nhiều luật hơn. Trong thuật toán C4.5, tác giả Quinlan đã giải quyết vấn đề này bằng cách sử dụng 1 độ đo khác là Gain Ratio, làm giảm ảnh hưởng của các thuộc tính có nhiều giá trị. 3.4.2 Xử lý các thuộc tính có kiểu giá trị liên tục Thuộc tính kiểu giá trị liên tục là Ngày Quang Cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis D1 Nắng 85 85 Nhẹ Không D2 Nắng 80 90 Mạnh Không D3 Âm u 83 78 Nhẹ Có D4 Mưa 70 96 Nhẹ Có D5 Mưa 68 80 Nhẹ Có D6 Mưa 65 70 Mạnh Không D7 Âm u 64 65 Mạnh Có D8 Nắng 72 95 Nhẹ Không D9 Nắng 69 70 Nhẹ Có Id3 Outlook = A | Humidity = High: No | Humidity = Normal: Yes Outlook = B | Temp = Hot: Yes | Temp = Mild: Yes | Temp = Cool: No Outlook = E: Yes Outlook = D | Temp = Hot: null | Temp = Mild: No | Temp = Cool: Yes Outlook = C: Yes C4.5 Humidity = High | Outlook = A: No (3.0) | Outlook = B: Yes (2.0) | Outlook = E: Yes (1.0) | Outlook = D: No (1.0) | Outlook = C: No (0.0) Humidity = Normal: Yes (7.0/1.0) Test bằng WEKA Decision Tree 25 D10 Mưa 75 80 Nhẹ Có D11 Nắng 75 70 Mạnh Có D12 Âm u 72 90 Mạnh Có D13 Âm u 81 75 Nhẹ Có D14 Mưa 71 80 Mạnh Không Trong thuật toán ID3 không phân biệt thuộc tính kiểu giá trị liên tục và thuộc tính kiểu giá trị rời rạc, mà chỉ xem thuộc tính kiểu giá trị liên tục như một thuộc tính có nhiều giá trị, và phạm phải khuyết điểm trên là ưu tiên chọn thuộc tính này làm thuộc tính phân lớp. Giả sử thuộc tính A có các giá trị v1 ,v2 ,…, vN, thuật toán C4.5 đã giải quyết vấn đề này như sau: - Trước tiên, sắp xếp các giá trị của thuộc tính A tăng dần ví dụ như từ v1 ,v2 ,…, vN - Chia giá trị của thuộc tính A thành N-1 “ngưỡng”, giá trị “ngưỡng”= 898:; < - Tính Information Gain ứng với N-1 “ngưỡng”. - Chọn “ngưỡng” có Information Gain cao nhất làm “ngưỡng” tốt nhất của A, Gain(S,A) là giá trị Gain cao nhất của “ngưỡng” chọn. Xét ví dụ với tập huấn luyện trên, tìm ngưỡng và Gain của thuộc tính Độ Ẩm. Decision Tree 26 Kết quả trên cho thấy ta có ngưỡng là Độ ẩm80 vì có Gain lớn nhất. Gain(S,Độ ẩm)=0.2361 Nhận xét: Việc tìm ngưỡng theo thuật toán C4.5 rất tốn thời gian để tính Gain cho N-1 ngưỡng. Sau có nhiều tác giả đã nghiên cứu để tìm cách tìm ngưỡng nhanh hơn như Fayyad(1991), Utgoff, Brodley, Murthy et al. 3.4.3 Làm việc với thuộc tính thiếu giá trị Thuật toán xây dựng dựa vào giả thuyết tất cả các mẫu dữ liệu có đủ các thuộc tính. Nhưng trong thực tế, xảy ra hiện tượng dữ liệu bị thiếu, tức là ở một số mẫu dữ liệu có những thuộc tính không được xác định, hoặc mâu thuẫn, hoặc không bình thường. Ta xem xét kỹ hơn với trường hợp dữ liệu bị thiếu. Đơn giản nhất là không Sắp xếp tăng dần 0.0477 0.0103 Information Gain 0.000 0.0150 0.0453 0.0903 0.1518 0.2361 0.1022 0.0251 0.0103 0.0477 Decision Tree 27 đưa các mẫu với các giá trị bị thiếu vào, nếu làm như vậy thì có thể dẫn đến tình trạng thiếu các mẫu học. Một số cách khác được đề xuất ở thuật toán C4.5 như sau: o Giả sử thuộc tính A là một ứng cử cho thuộc tính kiểm tra ở nút n o Xử lý thế nào với bộ X thiếu giá trị đối với thuộc tính A(tức là XA là không xác định)? o Gọi Sn là tập các mẫu học gắn với nút n có giá trị đối với thuộc tính A – Giải pháp 1: XA là giá trị phổ biến nhất đối với thuộc tính A trong số các bộ thuộc tập Sn – Giải pháp 2: XA là giá trị phổ biến nhất đối với thuộc tính A trong số các bộ Sn có cùng phân lớp với X – Giải pháp 3: • Tính xác suất pv đối với mỗi giá trị có thể V của thuộc tính A • Gán phần pv của bộ X đối với nhánh tương ứng của nút n. • Giá trị pv này được dùng tính Gain và hơn nữa để chia nhỏ nhánh tiếp theo của cây nếu có thuộc tính thứ 2 có lỗi(thiếu giá trị) Xét ví dụ sau: Ngày Quang Cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis D1 Nắng Nóng Cao Nhẹ Không D2 Nắng Nóng Cao Mạnh Không D3 Âm u Nóng Cao Nhẹ Có D4 Mưa Ấm áp Cao Nhẹ Có D5 Mưa Mát TB ??? Có D6 Mưa Mát TB Mạnh Không D7 Âm u Mát TB Mạnh Có D8 Nắng Ấm áp Cao Nhẹ Không D9 Nắng Mát TB Nhẹ Có D10 Mưa Ấm áp TB Nhẹ Có Decision Tree 28 D11 Nắng Ấm áp TB Mạnh Có D12 Âm u Ấm áp Cao Mạnh Có D13 Âm u Nóng TB Nhẹ Có D14 Mưa Ấm áp Cao Mạnh Không Tại mẫu huấn luyện D5 có thuộc tính không rõ giá trị là thuộc tính Gió, theo 3 giải pháp trên ta tìm giá trị cho thuộc tính ở mẫu này như sau: - Giải pháp 1: Xét trên toàn tập S có 13 mẫu, trong đó số mẫu có Gió = Mạnh là 6 và số mẫu có Gió = Nhẹ là 7. Vậy giá trị “Nhẹ” phổ biến hơn nên ta chọn “Nhẹ” điền vào giá trị thiếu ở mẫu D5. - Giải pháp 2: Chỉ xét trên lớp mà mẫu D5 thuộc, đó là lớp “Có”. Số mẫu thuộc lớp “Có” lúc này là 8, trong đó số mẫu có Gió = Mạnh là 3 và số mẫu có Gió = Nhẹ là 5. Vậy giá trị “Nhẹ” phổ biến hơn nên ta chọn “Nhẹ” điền vào giá trị thiếu ở mẫu D5. - Giải pháp 3: Gió có 2 giá trị là “Nhẹ” và “Mạnh”. Tính xác suất ứng với 2 giá trị này: • P(Gió=Nhẹ )=7/13 • P(Gió=Mạnh )=6/13 Xác suất của Gió=Nhẹ cao hơn nên ta chọn “Nhẹ” điền vào giá trị thiếu ở mẫu D5. 3.4.4 Xử lý các thuộc tính có giá trị chi phí Trong việc học để phân lớp các bệnh y tế, BloodTest có chi phí $150 trong khi TemperatureTest có chi phí $10, ta nên chọn thuộc tính nào để chi phí trị bệnh là thấp nhất! Theo xu hướng học cây quyết định: – Sử dụng càng nhiều các thuộc tính có chi phí thấp càng tốt. – Chỉ sử dụng các thuộc tính có chi phí cao khi cần thiết (để giúp đạt được các phân loại đáng tin cậy) Làm sao để học một cây quyết định với chi phí thấp? Vấn đề này đã được 2 tác giả Tan và Schimmer (1990) giải quyết bằng cách sử dụng các đánh giá khác của Information Gain cho việc xác định thuộc tính phân lớp theo công thức sau: < , = >= Decision Tree 29 Đến năm 1991, tác giả Nunez đưa ra một cách công thức khác: 2?@),A − 1 >= + 1 C 3.5 Thuật toán SPRINT [3] Ngày nay dữ liệu cần khai phá có thể có tới hàng triệu bản ghi và khoảng 10 đến 10000 thuộc tính. Hàng Tetabyte (100 M bản ghi * 2000 trường * 5 bytes) dữ liệu cần được khai phá. Những thuật toán ra đời trước không thể đáp ứng được nhu cầu đó. Trước tình hình đó, SPRINT là sự cải tiến của thuật toán SLIQ (Mehta, 1996) ra đời. Các thuật toán SLIQ và SPRINT đều có những cải tiến để tăng khả năng mở rộng của thuật toán như: • Khả năng xử lý tốt với những thuộc tính liên tục và thuộc tính rời rạc. • Cả hai thuật toán này đều sử dụng kỹ thuật sắp xếp trước một lần dữ liệu, và lưu trữ thường trú trên đĩa (disk – resident data) những dữ liệu quá lớn không thể chứa vừa trong bộ nhớ trong. Vì sắp xếp những dữ liệu lưu trữ trên đĩa là đắt, nên với cơ chế sắp xếp trước, dữ liệu phục vụ cho quá trình phát triển cây chỉ cần được sắp xếp một lần. Sau mỗi bước phân chia dữ liệu tại từng node, thứ tự của các bản ghi trong từng danh sách được duy trì, không cần phải sắp xếp lại như các thuật toán CART và C4.5. Từ đó làm giảm tài nguyên tính toán khi sử dụng giải pháp lưu trữ dữ liệu thường trú trên đĩa. • Cả 2 thuật toán sử dụng những cấu trúc dữ liệu giúp cho việc xây dựng cây quyết định dễ dàng hơn. Tuy nhiên cấu trúc dữ liệu lưu trữ của SLIQ và SPRINT khác nhau, dẫn đến những khả năng mở rộng, và song song hóa khác nhau giữa hai thuật toán này. Mã giả của thuật toán SPRINT như sau: SPRINT algorithm: Partition(Data S) { if (all points in S are of the same class) then return; for each attribute A do evaluate splits on attribute A; Use best split found to partition S into S1& S2 Partition(S1); Partition(S2); } Decision Tree 30 Initial call: Partition(Training Data) 3.5.1 SPRINT sử dụng độ đo Gini-index SPRINT là một trong những thuật toán sử dụng độ đo Gini-index để tìm thuộc tính tốt nhất làm thuộc tính phân lớp tại mỗi node trên cây. Chỉ số này đã được trình bày chi tiết ở mục 2.1.1.2 Ưu điểm của loại chỉ số này là các tính toán trên nó chỉ dựa vào thông tin về sự phân phối các giá trị lớp trong từng phần phân chia mà không tính toán trên các giá trị của thuộc tính đang xem xét. Để tìm được điểm phân chia cho mỗi node, cần quét từng danh sách thuộc tính của node đó và ước lượng các phân chia dựa trên mỗi thuộc tính gắn với node đó. Thuộc tính được chọn để phân chia là thuộc tính có chỉ số ginisplit(S) nhỏ nhất. Điểm cần nhấn mạnh ở đây là khác với Information Gain chỉ số này được tính mà không cần đọc nội dung dữ liệu, chỉ cần biểu đồ biểu diễn sự phân phối các bản ghi theo các giá trị phân lớp. Đó là tiền đề cho cơ chế lưu trữ dữ liệu thường trú trên đĩa. 3.5.2 Cấu trúc dữ liệu trong SPRINT Kỹ thuật phân chia dữ liệu thành các danh sách thuộc tính riêng biệt lần đầu tiên được SLIQ (Supervised Learning In Quest) đề xuất. Dữ liệu sử dụng trong SLIQ gồm: nhiều danh sách thuộc tính lưu trữ thường trú trên đĩa (mỗi thuộc tính tương ứng với một danh sách), và một danh sách đơn chứa giá trị của class lưu trữ thường trú trong bộ nhớ chính. Các danh sách này liên kết với nhau bởi giá trị của thuộc tính rid (chỉ số bản ghi được đánh thứ tự trong cơ sở dữ liệu) có trong mỗi danh sách. SLIQ phân chia dữ liệu thành hai loại cấu trúc: Decision Tree 31 Danh sách thuộc tính (Attribute List) thường trú trên đĩa. Danh sách này gồm trường thuộc tính và rid (a record identifier). Danh sách lớp (Class List) chứa các giá trị của thuộc tính phân lớp tương ứng với từng bản ghi trong cơ sở dữ liệu. Danh sách này gồm các trường rid, thuộc tính phân lớp và node (liên kết với node có giá trị tương ứng trên cây quyết định). Việc tạo ra trường con trỏ trỏ tới node tương ứng trên cây quyết định giúp cho quá trình phân chia dữ liệu chỉ cần thay đổi giá trị của trường con trỏ, mà không cần thực sự phân chia dữ liệu giữa các node. Danh sách lớp được lưu trữ thường trú trong bộ nhớ trong vì nó thường xuyên được truy cập, sửa đổi cả trong giai đoạn xây dựng cây, và cả trong giai đoạn cắt, tỉa cây. Kích thước của danh sách lớp tỉ lệ thuận với số lượng các bản ghi đầu vào. Khi danh sách lớp không vừa trong bộ nhớ, hiệu năng của SLIQ sẽ giảm. Đó là hạn chế của thuật toán SLIQ. Việc sử dụng cấu trúc dữ liệu thường trú trong bộ nhớ làm giới hạn tính mở rộng được của thuật toán SLIQ. SPRINT khắc phục được hạn chế của SLIQ bằng cách không sử dụng danh sách lớp cư trú trong bộ nhớ, SPRINT chỉ sử dụng một loại danh sách là danh sách thuộc tính có cấu trúc như sau: 3.5.3 Danh sách thuộc tính SPRINT tạo danh sách thuộc tính cho từng thuộc tính trong tập dữ liệu. Danh sách này bao gồm thuộc tính, nhãn lớp (Class label hay thuộc tính phân lớp), và chỉ số của bản ghi rid (được đánh từ tập dữ liệu ban đầu). Danh sách thuộc tính liên tục được sắp xếp thứ tự theo giá trị của thuộc tính đó ngay khi được tạo ra. Nếu toàn bộ dữ liệu không chứa đủ trong bộ nhớ thì tất cả các danh sách thuộc tính được lưu trữ trên đĩa. Decision Tree 32 Chính do đặc điểm lưu trữ này mà SPRINT đã loại bỏ mọi giới hạn về bộ nhớ, và có khả năng ứng dụng với những cơ sở dữ liệu thực tế với số lượng bản ghi có khi lên tới hàng tỉ. Các danh sách thuộc tính ban đầu tạo ra từ tập dữ liệu đào tạo được gắn với gốc của cây quyết định. Khi cây phát triển, các node được phân chia thành các node con mới thì các dánh sách thuộc tính thuộc về node đó cũng được phân chia tương ứng và gắn vào các node con. Khi danh sách bị phân chia thì thứ tự của các bản ghi trong danh sách đó được giữ nguyên, vì thế các danh sách con được tạo ra không bao giờ phải sắp xếp lại. Đó là một ưu điểm của SPRINT so với các thuật toán trước đó. • Biểu đồ (Histogram) SPRINT sử dụng biểu đồ để lập bảng thống kê sự phân phối lớp của các bản ghi trong mỗi danh sách thuộc tính, từ đó dùng vào việc ước lượng điểm phân chia cho danh sách đó. Thuộc tính liên tục và thuộc tính rời rạc có hai dạng biểu đồ khác nhau. - Biểu đồ của thuộc tính liên tục SPRINT sử dụng 2 biểu đồ: Cbelow và Cabove. Cbelow chứa sự phân phối của những bản ghi đã được xử lý, Cabove chứa sự phân phối của những bản ghi chưa được xử lý trong danh sách thuộc tính. Với thuộc tính liên tục, các giá trị kiểm tra là các giá trị nằm giữa mọi cặp 2 giá trị liền kề của thuộc tính đó. Để tìm điểm phân chia cho thuộc tính đó tại một node nhất định, biểu đồ được khởi tạo với Cbelow bằng 0 và Cabove là phân phối lớp của tất cả các bản ghi tại node đó. Hai biểu đồ trên được cập nhật lần lượt mỗi khi từng bản ghi được đọc. Mỗi khi con trỏ chạy gini-index được tính trên từng điểm phân chia nằm giữa giá trị vừa đọc và giá trị sắp đọc. Khi đọc hết danh sách thuộc tính (Cabove bằng 0 ở tất cả các cột) thì cũng là lúc tính được toàn bộ các gini-index của các điểm phân chia cần xem xét. Căn cứ vào kết quả đó có thể chọn ra gini-index thấp nhất và tương ứng là điểm phân chia của thuộc tính liên tục đang xem xét tại node đó. Việc tính gini-index hoàn toàn dựa vào biểu đồ. Nếu tìm ra điểm phân chia tốt nhất thì kết quả đó được lưu lại và biểu đồ vừa gắn danh sách thuộc tính đó được khởi tạo lại trước khi xử lý với thuộc tính tiếp theo. Decision Tree 33 - Biểu đồ của thuộc tính rời rạc Thuộc tính rời rạc cũng có một biểu đồ gắn với từng node. Tuy nhiển SPRINT chỉ sử dụng một biểu đồ là count matrix chứa sự phân phối lớp ứng với từng giá trị của thuộc tính được xem xét. Với thuộc tính rời rạc, quá trình tìm điểm phân chia tốt nhất cũng được tính toán dựa trên biểu đồ của danh sách thuộc tính đó. Trước tiên cần quét toàn bộ danh sách thuộc tính để thu được số lượng phân lớp ứng với từng giá trị của thuộc tính rời rạc, kết quả này được lưu trong biểu đồ count matrix. Sau đó, cần tìm tất cả các tập con có thể có từ các giá trị của thuộc tính đang xét, coi đó là điểm phân chia và tính gini-index tương ứng. Các thông tin cần cho việc tính toán chỉ số gini-index của bất cứ tập con nào đều có trong count matrix. Bộ nhớ cung cấp cho count matrix được thu hồi sau khi tìm ra được điểm phân chia tốt nhất của thuộc tính đó. Decision Tree 34 Các danh sách thuộc tính được xử lý cùng một lúc, do vậy thay vì đòi hỏi các danh sách thuộc tính trong bộ nhớ, với SPRINT bộ nhớ chỉ cần chứa tập các biểu đồ như trên trong quá trình phát triển cây. Ví dụ mô tả cách tính chỉ số Gini–index với mẫu huấn luyện như trên. Với Thuộc tính liên tục Age cần tính điểm phân chia trên lần lượt các so sánh sau Age<=17, Age<=20, Age<=23, Age<=32, Age<=43: • Gini(Age<=17) = 1- (12+02) = 0 • Gini(Age>17) = 1- ((3/5)2+(2/5)2) = 12/25 – GiniSPLIT (Age17)= (1/6) * 0 + (5/6) * (12/25) = 2/5 • G(Age<=20) = 1- (12+02) = 0 • G(Age>20) = 1- ((2/4)2+(2/4)2) = 1/2 – GiniSPLIT (Age20)= (2/6) * 0 + (4/6) * (1/2) = 1/3 • Gini(Age<=23) = 1- (12+02) = 0 • Gini(Age>23) = 1- ((1/3)2+(2/3)2) = 4/9 – GiniSPLIT (Age23)= (3/6) * 0 + (3/6) * (4/9) = 2/9 • Gini(Age<=32) = 1- ((3/4)2+(1/4)2) = 1/4 • Gini(Age>32) = 1- ((1/2)2+(1/2)2) = 1/2 – GiniSPLIT (Age32)= (4/6) * 1/4 + (2/6) * (1/2) = 1/3 • Gini(Age<=43) = 1- ((4/5)2+(1/5)2) = 8/25 • Gini(Age>43) = 1- ((0)2+(1)2) = 0 – GiniSPLIT (Age43)= (5/6) * 8/25 + (1/6) * 0= 4/15 So sánh các GiniSPLIT tìm được ứng với từng phân chia của các thuộc tính, GiniSPLIT ứng với Age <=23 có giá trị nhỏ nhất. Do vậy điểm phân chia là tại thuộc tính Age với giá trị ngưỡng phân chia = (23+32) / 2 = 27.5 và Gini(Age)=2/9. 3.5.4 Thực thi sự phân chia Decision Tree 35 Sau khi tìm ra thuộc tính phân chia tốt nhất của node dựa trên so sánh gini-index của các thuộc tính có trên node đó, cần thực thi sự phân chia bằng cách tạo ra các node con và phân chia danh sách thuộc tính của node cha cho các node con. Với thuộc tính được chọn (Age như trên hình vẽ) làm thuộc tính phân chia tại node đó, việc phân chia danh sách thuộc tính này về các node con khá đơn giản. Nếu đó là thuộc tính liên tục, chỉ cần cắt danh sách thuộc tính theo điểm phân chia thành 2 phần và gán cho 2 node con tương ứng. Nếu đó là thuộc tính rời rạc thì cần quét toàn bộ danh sách và áp dụng test đã xác định để chuyển các bản ghi về 2 danh sách mới ứng với 2 node con. Nhưng vấn đề không đơn giản như vậy với những thuộc tính còn lại tại node đó (Car Type chẳng hạn), không có test trên thuộc tính này, nên không thể áp dụng các kiểm tra trên giá trị của thuộc tính để phân chia các bản ghi. Lúc này cần dùng đến một trường đặc biệt trong các danh sách thuộc tính đó là rids. Đây chính là trường kết nối các bản ghi trong các danh sách thuộc tính. Cụ thể như sau: trong khi phân chia danh sách của thuộc tính phân chia (Age) cần chèn giá trị trường rids của mỗi bản ghi vào một bảng băm (hash table) để đánh đấu node con mà các bản ghi tương ứng (có cùng rids) trong các danh sách thuộc tính khác được phân chia tới. Cấu trúc của bảng băm như sau: Phân chia xong danh sách của thuộc tính phân chia thì cũng là lúc xây dựng xong bảng băm. Danh sách các thuộc tính còn lại được phân chia tới các node con theo thông tin trên bảng băm bằng cách đọc trường rids trên từng bản ghi và trường Child node tương ứng trên bảng băm. Decision Tree 36 Nếu bảng băm quá lớn so với bộ nhớ, quá trình phân chia được chia thành nhiều bước. Bảng băm được tách thành nhiều phần sao cho vừa với bộ nhớ, và các danh sách thuộc tính phân chia theo từng phần bảng băm. Quá trình lặp lại cho đến khi bảng băm nằm trong bộ nhớ. Decision Tree 37 4. Vấn đề Overfitting và các giải pháp giảm Overfitting (Hồ Sơn Lâm) 4.1 Quá khớp dữ liệu (Overfitting) Thế nào là “quá khớp” dữ liệu? Có thể hiểu đây là hiện tượng cây quyết định chứa một số đặc trưng riêng của tập dữ liệu đào tạo, nếu lấy chính tập traning data để test lại mô hình phân lớp thì độ chính xác sẽ rất cao, trong khi đối với những dữ liệu tương lai khác nếu sử dụng cây đó lại không đạt được độ chính xác như vậy. 4.1.1 Định nghĩa: Cho một không gian giả thuyết H, h Є H quá khớp với tập dữ liệu huấn luyện nếu tồn tại h’ Є H sao cho : - h có tỉ lệ lỗi thấp hơn h’ đối với tập dữ liệu huấn luyện. - nhưng h’ lại có tỉ lệ lỗi thấp hơn h đối với dữ liệu tổng quát. H1 Thống kê độ chính xác của cây quyết định Đây là một mô hình diễn tả quá trình quá khớp dữ liệu trong một ứng dụng điển hình của cây quyết định. Trong trường hợp này, cây quyết định này được xây dựng trên thuật toán ID3 về việc học chữa bệnh tiểu đường. Với đường chân trời Decision Tree 38 thể hiện tổng số node ứng viên trên cây quyết định và đường thẳng đứng thể hiện độ chính xác của trên trên tập dữ liệu huấn luyện và trên tập dữ liệu kiểm tra (không nằm trong tập dữ liệu huấn luyện). Nếu đưa tập huấn luyện vào thì cây cho kết quả thì độ chính xác tăng (với số lượng node tăng) theo một đường thẳng gần như tuyến tính, nhưng ngược lại độ chính xác của dữ liệu test lại bị giảm xuống theo số lượng node tăng dần. Như ta có thể thấy rằng nếu cây vượt quá 25 nodes ứng viên thì độ chính xác sẽ bị giảm dần trên dữ liệu test và tăng dần trên dữ liệu huấn luyện. Tại sao độ chính xác của cây quyết định lại giảm xuống khi kiểm tra dữ liệu test. 4.1.2 Nguyên nhân quá khớp dữ liệu Nguyên nhân chính là do dữ liệu test có những bộ dự liệu bị nhiễu (noise data) hay bị lỗi và số lượng dữ liệu đem đi huấn luyện quá ít hay dữ liệu huấn luyện chỉ nghiêng về một đặc trưng nào đó thôi chứ không bao quát toàn bộ trường hợp. Để diễn ta điều này ta đi vào một bộ dữ liệu nhiễu như sau: H2 Dữ liệu đem đi huấn luyện Decision Tree 39 H3 Cây quyết định từ bộ dữ liệu trên • Bộ dữ liệu nhiễu như sau: Outlook = Sunny, Temperature = Hot, Humidity = Normal, Wind = Strong,PlayTennis = No Bộ dữ liệu này sẽ không cho được kết quả dựa vào cây quyết định trên. Nếu như ta đêm bộ dữ liệu này vào tập huấn luyện và huấn luyện lại cây thì cây sẽ phức tạp, tăng độ chính xác của tập huấn luyện nhưng tập test thì giảm độ chính xác. 4.2 Phương pháp tránh quá khớp dữ liệu Decision Tree 40 Quá khớp dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định và những phương pháp học khác. Đặc biệt khi số lượng ví dụ trong tập dữ liệu đào tạo quá ít, hay có noise trong d ữ liệu. Có hai phương pháp tránh “quá khớp” dữ liệu trong cây quyết định: • Dừng phát triển cây sớm hơn bình thường, trước khi đạt tới điểm phân lớp hoàn hảo tập dữ liệu đào tạo. Với phương pháp này, một thách thức đặt ra là phải ước lượng chính xác thờ i điểm dừng phát triển cây. • Cho phép cây có th ể “quá khớp” dữ liệu, sau đó sẽ cắt, tỉa cây. Mặc dù phương pháp thứ nhất có vẻ trực tiếp hơn, nhưng với phương pháp thứ hai thì cây quyế t định được sinh ra được thực nghiệm chứng minh là thành công hơn trong thực tế . Hơn nữa việc cắt tỉa cây quyết định còn giúp tổng quát hóa, và cải thiện độ chính xác của mô hình phân lớp. Dù thực hiện phương pháp nào thì vấn đề mấu chốt ở đây là tiêu chuẩn nào được sử dụng để xác định kích thước hợp lý của cây cuối cùng. Như vậy kích thước chính xác của cây được tìm thấy bằng việc dừng sớm hay trễ là một câu hỏi được đặt ra cho nhiều nhà khoa học để xác định kích thước cuối cùng của cây. Và có các phương pháp như sau: • Tập dữ liệu được chia ra làm các phần riêng biệt, từ tập huấn luyện, tập đánh giá cây sau khi cắt tỉa bằng phương pháp hậu cắt tỉa • Áp dụng một kiểm tra thống kê (Chi-square test) để đánh giá xem việc mở rộng (hay cắt tỉa) một nút có giúp cải thiện hiệu năng đối với tập huấn luyện. • Dùng độ đo bằng cách mã hóa tập huấn luyện và cây quyết định , ngừng phát triển cây nếu chiều dài của chuỗi mã hóa là nhỏ nhất. Phương pháp đầu tiên được dùng phổ biến và sử dụng tập dữ liệu huấn luyện để tạo cây, tập đánh giá để đánh giá node cần cắt tỉa. Và ta tiếp tục đi vào phương pháp thứ nhất để giảm lỗi cắt quá khớp dữ liệu. 4.2.1 Cắt tỉa để giảm lỗi (Reduced error pruning) Như ta biết rằng phương pháp thứ nhất, người ta chia tập dữ liệu ra làm 3 phần do Quinlan đề xuất 1987 như sau: • Tập huấn luyện để tạo cây(training examples). • Tập đánh giá dùng cho việc cắt tỉa (validation examples). • Tập kiểm tra dùng để đánh giá độ chính xác trong tương lai (test examples). 1. Phương pháp cắt tỉa như sau: • Mỗi node trong cây quyết định là một ứng viên (không tính node lá). Decision Tree 41 • Node bị cắt đi nếu làm tăng độ chính xác của cây quyết định trên tập đánh giá. • Lặp cho tới khi độ chính xác của phần đánh giá giảm thì dừng. Sau đây là kết quả thống kê tính hiệu quả của việc cắt tỉa: H4 Độ chính xác của cây sau cắt tỉa Hiệu quả của việc cắt tỉa trên cây quyết định. Biểu đồ trên có đường cong trên và dưới giống như H3 thể hiện độ chính xác của tập huấn luyện và tập test. Thêm vào đó còn thể hiện hiệu quả độ chính xác của cây quyết định trên tập dữ liệu test sau khi cắt tỉa bằng thuật toán Reduced-error pruning. Sau khi cắt tỉa thì độ chính xác của tập test tăng lên theo số lượng node ứng viên nhưng khi đạt đến số lượng node tối đa thì độ chính xác của cây cắt tỉa giảm bằng với trước khi cắt tỉa (số lượng node nhiều nhất). Để thể hiện rõ điều này ta đi vào ví dụ cụ thể: Decision Tree 42 H5 Cây dùng để cắt tỉa [4] • Đánh giá tỉ lệ lỗi trên một nút theo PP C4.5: • f =S/N: tỉ lệ lỗi trên tập huấn luyện • S: số mẫu lỗi tại một node • N: tổng số mẫu tại node • z : độ lệch chuẩn (standard deviation) • Phân bổ Gaussian (Normal Distribution) Decision Tree 43 • Trung bình µ= 0 và phương sai δ2 =1 • c% : khoảng tin cậy của biến random X [–z ≤ X ≤ z] • Với phân bổ đối xứng: Xác xuất của một biến ngẫu nhiên bất kỳ [4] : Đánh giá việc cắt tỉa các node bằng cách dùng công thức đánh giá độ lỗi của một node cha so với độ lỗi trung bình ở một node con khi cho một bộ vào cây quyết định: Decision Tree 44 H6 Đánh giá độ lỗi tại một node[4] Kết quả cây được cắt tỉa như sau: Decision Tree 45 H7 Cây được cắt tỉa[4] Node cha bị cắt tỉa sẽ thay thế node con như sau: • Nâng cây: H8 Nâng cây[4] • Thay bằng node lá có tầng số xuất hiện nhiều nhất so với các node còn lại. Decision Tree 46 4.2.2 Luật hậu cắt tỉa (Rule Post-Pruning) 2. Phương pháp: • Phát triển cây quyết định hoàn toàn phù hợp với tập huấn luyện. • Chuyển biểu diễn cây quyết định học được thành một tập các luật tương ứng (tạo một luật cho mỗi đường đi từ nút gốc đến một nút lá) • Rút gọn mỗi luật bằng cách loại bỏ bất kỳ điều kiện nào giúp mang lại sự cải thiện về hiệu quả phân loại của luật đó. • Sắp xếp các luật đã rút gọn theo hiệu quả phân loại, và sử dụng thứ tự này cho việc phân loại các mẫu trong tương lai. 3. Ta có ví dụ cụ thể như sau: H10 Thí dụ hậu cắt tỉa Chuyển thành luật: 1.IF( Outlook=sunny ^ humidity=high) THEN (Play = No ) 2. IF(Outlook=sunny ^ humidity=normal ) THEN(Play= Yes) 3. IF( Outlook=overcast ) THEN (Play= Yes) 4. IF(Outlook=rain ^ wind=strong ) THEN(Play= No) 5. IF(Outlook=rain ^ wind=weak ) THEN (Play=Yes) Xét luật số 1: ta có thể chia ra thêm thành 2 luật mới: 1.IF( Outlook=sunny ^ humidity=high) THEN (Play = No ) 2.IF( Outlook=sunny) THEN (Play = No ) Decision Tree 47 3.IF( Humidity=high) THEN (Play = No ) Ta đánh giá độ chính xác từng luật nếu luật nào có độ chính xác cao trên tập đánh giá thì ta chọn và loại bỏ các luật còn lại. H11 Cách chọn luật mới từ luật ban đầu Ta chọn luật IF( Outlook=sunny) THEN (Play = No ) vì có độ chính xác cao hơn 2 luật còn lại. 4. Tại sao phải chuyển cây quyết định sang luật? • Phân biệt giữa những ngữ cảnh khác nhau ở những node của cây quyết định được dùng. • Loại bỏ đi điểm khác biệt giữa những thuộc tính kiểm tra xảy ra gần node gốc của cây và xảy ra gần node lá của cây. • Cải thiện tính dễ đọc. Decision Tree 48 5. Cây quyết định mở rộng (Bùi Tuấn Phụng) 5.1 Oblivious Decision Trees Cây quyết định oblivious là cây quyết định mà tất cả các nút tại cùng cấp thì cùng tính năng. Mặc dù có những hạn chế, song cây quyết định oblivious rất hiệu quả trong việc lựa chọn tính năng. [Almuallim và Deitterich (1994)] cũng như [Schlimmer (1993)] đã đề xuất một thủ tục lựa chọn tính năng trước đây bằng cách xây dựng cây quyết định oblivious, trong khi đó [Langley và Sage (1994)] đã đề nghị lựa chọn ngược cũng sử dụng cây quyết định oblivious. [Kohavi và Sommerfield (1998)] đã chỉ ra rằng cây quyết định oblivious có thể chuyển thành một bảng quyết định. Gần đây [Maimon và Last (2000)] đã đề nghị thuật toán mới IFN (Information Fuzzy Network) để xây dựng cây quyết định oblivious. 5. Vì sao phải xây dựng thuật toán IFN? • Ưu điểm: - Xây dựng IFN tương tự xây dựng cây quyết định. - IFN là một đồ thị có hướng chứ không phải là cây. - IFN sử dụng thông tin chung có điều kiện trong quá trình xây dựng cây, trong khi đó cây quyết định sử dụng số liệu Entropy hoặc Gini. - Chiều cao của IFN không thể vượt quá số lượng đầu vào. - Các mô hình IFN thường ổn định hơn, điều đó có nghĩa rằng những thay đổi nhỏ trong tập huấn luyện sẽ ảnh hưởng đến nó ít hơn trong các mô hình khác. • Nhược điểm: - Tuy nhiên độ chính xác của IFN thấp của cây quyết định. 6. Thuật toán: 6.1 Input: 6.1.1 Một danh sách các biến 6.1.2 Một danh sách tập huấn luyện 6.1.3 Một ý nghĩa thống kê tối thiểu được dùng để quyết định có phân chia nút đó hay không? (mặc định: 0.1%). 6.2 Tạo nút gốc và một lớp của biến mục tiêu. 6.3 Lặp lại cho đến khi sử dụng hết các thuộc tính hoặc không thể cải thiện hơn các thông tin chung điều kiện. 6.3.1 Tìm thuộc tính với thông tin chung có điều kiện lớn nhất. 6.3.2 Xác nhận sự tham gia của các thuộc tính có ý nghĩa thống kê bằng cách sử dụng các bộ kiểm tra tỷ lệ khả năng xảy ra. Decision Tree 49 6.3.3 Phân chia bất kỳ nút nào trong lớp trước đó mà tham gia vào các thuộc tính hiện tại với ý nghĩa thống kê. Nếu không, tạo một nút nối nút đó đến một trong các nút giá trị của biến mục tiêu dựa vào luật đa số. 6.4 Liệt kê danh sách các biến đã được sử dụng trong mạng lưới đó. Ví dụ: (Hình bên dưới) Trong hình này, mạng lưới bao gồm 2 lớp, đại diện cho 2 thuộc tính đầu vào (lớp 1 và lớp 2). - Thuộc tính đầu vào đầu tiên có 3 giá trị, được thể hiện bỡi các nút 1, 2, 3 trong lớp thứ 1. - Các nút 1 và 3 được phân chia bỡi thủ tục xây dựng mạng này. - Thuộc tính đầu vào thứ 2 có 4 nút là sự kết hợp của 2 giá trị trong thuộc tính đầu vào mà đã phân chia trong lớp đầu. - Lớp mục tiêu thể hiện thuộc tính mục tiêu với 3 giá trị. Dựa trên thuyết thông tin, thuận lợi chính của IFN là tính chặt chẽ. Trong cây quyết định thông thường, như CART, chiều cao của một cây quyết định có thể vượt quá số lượng các thuộc tính đầu vào. Nhưng trong IFN, chiều cao của một cây quyết định sẽ không bao giờ vượt quá số lượng thuộc tính đầu vào. [Pruning Irrelevant Features from Oblivious Decision Trees] Trong hình 6.2 minh họa cho một loại cây quyết định oblivious với 4 tính năng đầu vào: mức đường huyết (G), Tuổi (A), Huyết áp (H) và Mang thai (P), tính năng Đúng/Sai thể hiện rằng bệnh nhân đó có bị tiểu đường hay không. Mỗi lớp là một kết hợp duy nhất với tính năng đầu vào bằng cách thể hiện sự tương tác của tính năng đó Decision Tree 50 với các tính năng đầu vào của lớp trước. Các con số xuất hiện trong các nút cuối cùng chỉ ra số trường hợp phù hợp với đường đi này. Ví dụ: (Hình 6.2) Khảo sát một số bệnh nhân có mức đường huyết nhỏ hơn 107 và tuổi lớn hơn 50 thì kết quả nhận thấy rằng: cứ 10 người được chuẩn đoán xem có bị tiểu đường hay không thì 2 người không cần chuẩn đoán bệnh này. Trường hợp khác, khảo sát một số bệnh nhân có đường huyết lớn hơn hoặc bằng 107, tuổi nhỏ hơn hoặc bằng 30, có bị bệnh huyết áp và đang mang thai thì phải làm xét nghiệm tiểu đường. Tương tự cho các đường đi còn lại. Sự khác biệt chính trong cấu trúc của cây quyết định oblivious và cây quyết định thông thường là thứ tự hằng số của thuộc tính đầu vào tại mỗi nút cuối cùng của cây quyết định oblivious. Thuộc tính thứ hai là cần thiết cho việc giảm thiểu toàn bộ tập con của thuộc tính đầu vào (kết quả là giảm kích thước). Các dây cung mà kết nối các nút cuối cùng với các nút của lớp mục tiêu thì được gán nhãn với số lượng mẫu tin phù hợp với đường đi này. Một cây quyết định oblivious được xây dựng thường xuyên bằng thuật toán tham lam, cái mà cố gắng tối đa hóa các biện pháp thông tin lẫn nhau trong mỗi lớp. Tìm kiếm đệ qui các thuộc tính minh họa, sẽ dừng khi không có thuộc tính nào mà giải thích mục tiêu này với ý nghĩa thống kê. [5] 5.2 Fuzzy decision trees Decision Tree 51 Hầu hết các phương pháp cây quyết định trước đây sử dụng để trích lọc tri thức trong các vấn đề phân loại sự không chắc chắn, nhận thức mơ hồ và không rõ ràng liên quan đến tư duy và nhận thức của con người. Một phương pháp cây quyết định mờ đầu tiên, mà dựa trên việc giảm phân loại mơ hồ với dấu hiệu mờ được phát triển. Cây quyết định mờ thể hiện việc phân loại kiến thức tự nhiên hơn là cách thức tư duy của con người và mạnh mẽ hơn trong việc tiếp cận thông tin không chính xác, xung đột và thiếu thông tin. Trong cây quyết định cổ điển, một trường hợp có thể được kết hợp với chỉ một nhánh của cây. Cây quyết định mờ (FDT) có thể kết hợp đồng thời nhiều nhánh đến cùng một trường hợp. FDTs bảo tồn cấu trúc biểu tượng của cây và có thể hiểu được. Tuy nhiên, FDT có thể biểu diễn các khái niệm với các đặc trưng được phân chia bỡi giá trị thực đầu ra với việc thay đổi phân chia Janikow (1998) đã biểu diễn một khung hoàn chỉnh cho việc xây dựng cây mờ gồm một số hàm suy luận dựa trên việc giải quyết xung đột trong các hệ thống dựa theo luật và các phương pháp suy luận gần đúng hiệu quả. Olaru và Wehenkel (2003) đã hiện thực một cây quyết định mờ mới được gọi là cây quyết định mềm. Cách tiếp cận này vừa kết hợp việc phát triển cây và tỉa cây, để xác định cấu trúc của cây quyết định mềm, với việc trang bị lại và thích hợp hơn, để cải thiện khả năng khái quát của nó. Họ chỉ ra trong thực nghiệm rằng cây quyết định mềm chính xác hơn một cách đáng kể so với cây quyết định tiêu chuẩn. Hơn nữa, một mô hình nghiên cứu toàn cầu hợp lý cho thấy cây quyết định mềm có phương sai thấp hơn cây tiêu chuẩn như một nguyên nhân trực tiếp của tính chính xác việc cải tiến. Peng (2004) đã sử dụng FDT để cải thiện hiệu suất của phương pháp học tập quy nạp cổ điển trong quá trình sản xuất. Peng đã đề nghị sử dụng rời rạc mềm của các thuộc tính giá trị liên tục. Nó đã được chỉ ra rằng FDT có thể đối phó với nhiễu hoặc không chắc tồn tại trong các dữ liệu thu thập được của hệ thống công nghiệp. [5] 5.3 Decision Trees Inducers for Large Datasets Với sự tăng trưởng gần đây về số lượng dữ liệu được thu thập bởi các hệ thống thông tin, có một nhu cầu cho cây quyết định mà có thể xử lý những tập dữ liệu lớn. [Catlett (1991)] đã xem xét hai phương pháp cho cây quyết định tăng trưởng hiệu quả từ một cơ sở dữ liệu lớn bằng cách giảm các yêu cầu được tính toán phức tạp cho phương pháp quy nạp. Tuy nhiên, phương pháp Catlett yêu cầu rằng tất cả dữ liệu phải được đưa vào bộ nhớ chính trước khi được tính toán. Cụ thể, tập dữ liệu lớn nhất mà có thể được tính toán thì được giới hạn một kích thướt bộ nhớ. [Fifield (1992)] đề nghị một sự bổ sung tương đương của thuật toán ID3. Tuy nhiên, cũng giống như Catlett, nó giả định rằng tất Decision Tree 52 cả các tập dữ liệu có thể phù hợp với bộ nhớ chính. [Chan và Stolfo (1997)] đề nghị phân chia các tập dữ liệu thành các tập dữ liệu rời rạc để mỗi tập dữ liệu được tải một cách riêng biệt vào bộ nhớ và được sử dụng để tạo ra cây quyết định. Cây quyết định sau đó được kết hợp để tạo ra một phân loại duy nhất. Tuy nhiên, các kết quả thử nghiệm cho thấy rằng việc phân chia có thể làm giảm hiệu suất phân loại. Điều này có nghĩa là tính chính xác phân loại của cây quyết định kết hợp là không tốt như trên cây quyết định đơn được xây dựng trên toàn tập dữ liệu. Thuật toán SLIQ (Mehta, 1996) không bắt buộc phải tải toàn bộ tập dữ liệu vào bộ nhớ chính, thay vào đó nó sử dụng bộ nhớ thứ cấp (bộ nhớ đĩa). Nói cách khác, một trường hợp nào đó không nhất thiết phải cư trú trong bộ nhớ chính tại mọi thời điểm. SLIQ tạo ra một cây quyết định duy nhất từ toàn bộ tập dữ liệu. Tuy nhiên, phương pháp này cũng có một giới hạn đối với tập dữ liệu lớn nhất mà có thể đã được xử lý, bởi vì nó sử dụng cấu trúc dữ liệu mà phân chia kích thướt tập dữ liệu và cấu trúc dữ liệu này luôn luôn phải được cư trú trong bộ nhớ chính.Thuật toán SPRINT sử dụng cách tiếp cận tương tự (Shafer, 1996). Thuật toán này xây dựng các cây quyết định tương đối nhanh và khắc phục các hạn chế về bộ nhớ của cây quyết định quy nạp. SPRINT đánh dấu bất kỳ nhiễu nào được chia nhỏ dựa trên các bộ dữ liệu lớn. (Gehrke, 2000) đã giới thiệu RainForest; một khung đồng nhất cho các phân lớp cây quyết định mà có khả năng nhân rộng bất kỳ thuật toán cụ thể nào từ tài liệu này (gồm: C4.5, CART và CHAID). Hơn nữa để tổng quát, RainForest cải tiến SPRINT bằng một nhân tố của 3. Ngược lại với SPRINT, tuy nhiên, RainForest yêu cầu một số lượng nhỏ bộ nhớ chính, tương ứng với tập của các giá trị khác nhau trong một cột của mối quan hệ đầu vào. Tuy nhiên, yêu cầu này được coi là vừa phải và hợp lý.Cây quyết định kết luận cho các tập dữ liệu lớn có thể tìm thấy trong các tài liệu (Alsabti, 1998; Freitas và Lavington, 1998; Gehrke, 1999). [5] 5.4 Incremental Induction: Hầu hết các cây quyết định kết luận đều yêu cầu xây dựng lại cây từ những cái linh tinh ứng với dữ liệu mới mà đã có sẵn. một số nghiên cứu đã giải quyết được các vấn đề về cập nhật các cây quyết định tăng trưởng. (Utgoff, 1989b,1997) trình bày một số phương pháp để cập nhật cây quyết định tăng trưởng. Mở rộng của thuật toán CART là khả năng gây tăng trưởng được mô tả trong (Crawford, 2002). [5] Decision Tree 53 6. Demo (Phan Hoàn Vũ) 6.1 WEKA 6.1.1 Sơ lược về weka Weka là một bộ công cụ phần mềm mã nguồn mở rất nổi tiếng trong lĩnh vực khai thác dữ liệu và máy học được phát triển bởi Đại học Waikato ở New Zealand. Nó là tập hợp của rất nhiều các thuật toán máy học phục vụ mục đích khai thác dữ liệu. Các thuật toán có thể được chạy trực tiếp trên các bộ dữ liệu đưa vào hoặc gọi từ ứng dụng của người dùng (viết bằng Java). Weka bao gồm các công cụ để tiền xử lý dữ liệu, phân loại, hồi qui, gom nhóm, khai thác luật kết hợp và một giao diện đồ họa để biểu diễn các kết quả. Ngoài ra, Weka còn hỗ trợ các nhà nghiên cứu một môi trường thực nghiệm tiện dụng để phát triển các mô hình, thuật toán máy học mới. Giao diện đồ họa của Weka. 6.1.2 Các chức năng chính Weka cung cấp 4 môi trường chính để thao tác với các thuật toán máy học. Các môi trường này bao gồm: console, explorer, experimenter, knowledage flow. Trong đó Explorer là môi trường thể hiện đầy đủ các phương tiện để thao tác với dữ liệu và các thuật toán máy học được cung cấp bởi Weka. Các thành phần còn lại là tương tự như explorer. Do đó, trong khuôn khổ của phần này nhóm sẽ tập trung giới thiệu chi tiết Explorer và đi sơ lược chức năng các phần còn lại của Weka. Decision Tree 54 6.1.2.1 Explorer Cung cấp một giao diện người dùng tiện dụng cho việc thực thi các thuật toán máy học trên bộ dữ liệu người dùng đưa vào. Giao diện đồ họa của explorer Các thành phần chính của môi trường này bao gồm:  Preprocess: Chứa các công cụ tiền xử lý dữ liệu  Classify: Môi trường thực thi các thuật toán thuộc nhóm phân lớp dữ liệu  Cluster: Môi trường thực thi các thuật toán thuộc lớp gom nhóm dữ liệu  Associate: Môi trường thực thi các thuật toán khai thác các luật kết hợp  Select attributes: Cung cấp khả năng tìm và chọn những attributes có hiệu năng sử dụng cao nhất  Visualize: Cung cấp môi trường hiển thị các thống kê dữ liệu đầu vào của người dùng trên giao diện đồ họa 2D Các thành phần này tương ứng với các tab trong màn hình ứng dụng. Decision Tree 55 CHI TIẾT PREPROCESS: Giữ nhiệm vụ tiền xử lý dữ liệu cho các thuật toán máy học. Dữ liệu có thể được người dùng import từ nhiều nguồn khác nhau: ARFF file, URL hoặc database. Dữ liệu sau khi được load vào chương trình có thể được filter trước khi thực hiện các thuật toán. Weka cung cấp rất nhiều giải pháp filter dữ liệu, tùy nhu cầu khảo sát mà chọn các thuật toán thích hợp: discretization, normalization, resampling, attribute selection, transforming and combining attributes … Giao diện chính của chức năng Pre-processing CLASSIFIER Classifier cung cấp các mô hình để dự đoán các phân lớp dựa trên các thuật toán phân loại máy học cơ bản: Decision trees và lists, instance-based classifiers, support vector machines, multi-layer perceptrons, logistic regression, Bayes’ nets … Decision Tree 56 Giao diện chính của chức năng classify CLUSTER Cung cấp khả năng gom nhóm dữ liệu liên quan với nhau thành các nhóm riêng biệt dựa vào các thuật toán máy học cơ bản hiện nay: k-Means, EM, Cobweb, X-means, FarthestFirst. Giao diện chính của chức năng clustering Decision Tree 57 ASSOCIATE Chức năng này cho phép huấn luyện các luật kết hợp dựa trên việc chọn lựa các thuật toán máy học sẳn có: Apriori, FPGrowth … Các thuật toán khai thác dữ liệu này cần phải được cung cấp các giá trị như min_sup (độ support tối tiểu), min_conf (độ tin cậy tối tiểu) để hoạt động. Điều đáng lưu ý là các thuật toán này chỉ hoạt động với dữ liệu rời rạc. Do đó nếu dữ liệu vào là liên tục, chương trình sẽ không cho phép thực thi chức năng này. Giao diện chính của chức năng associate SELECT ATTRIBUTES Cung cấp khả năng rút trích, chọn lọc các thuộc tính “tốt” nhất (theo ý nghĩa có khả năng phân loại, dự đoán tốt nhất). Các phương pháp chọn lọc attribute bao gồm 2 phần:  Search method: best-first, forward selection, random, exhaustive, genetic algorithm, ranking  Evaluation method: correlation-based, wrapper, information gain, chi- squared … Decision Tree 58 Giao diện chính chức năng select attributes VISUALIZE Visialization là một module đóng vai trò rất quan trọng trong thực nghiệm, giúp đánh giá được độ khó của việc học. Visualization thể hiện được mối liên hệ giữa các giá trị của 1attribute (1D) hoặc 2 attributes (2D) Giao diện chính chức năng visualize Decision Tree 59 6.1.2.2 Experimenter Cung cấp môi trường thuận tiện cho việc tạo và thực thi các thí nghiệm liên quan đến các thuật toán máy học. Ví dụ, người dùng có thể tạo ra 1 thử nghiệm để tiến hành chạy các thuật toán khác nhau trên cùng 1 bộ dữ liệu đầu vào, sau đó kiểm tra, so sánh kết quả đạt được để chọn ra thuật toán có kết quả tốt nhất. Thao tác trong môi trường này hoàn toàn tương tự như thao tác trong môi trường Explorer đã trình bày ở trên. Giao diện chính của môi trường Experimenter 6.1.2.3 KnowledgeFlow Là một thành phần mở rộng và nâng cao của Explorer. KnowledgeFlow cung cấp một môi trường lý tưởng để xây dựng một chuỗi các hoạt động liên quan đến việc thực nghiệm một hay nhiều thuật toán máy học. Người sử dụng có thể chọn các thành phần từ toolbar như datasource, data loader, classifier, Decision Tree 60 cluster, … sau đó đặt chúng lên màn hình giao diện, và kết nối chúng lại với nhau tạo thành một flow thống nhất để phân tích và xử lý dữ liệu. Dưới đây là hình ảnh minh họa cho việc xây dựng một chuỗi thao tác học máy trong môi trường knowledage flow của weka. Giao diện chính của môi trường Knowledage-Flow 6.1.2.4 Simple CLI Cung cấp khả năng thực thi các thuật toán máy học bằng các thao tác dòng lệnh command line. Dòng lệnh cơ bản để thao tác với các thuật toán máy học là: java [ > file] có nhiệm vụ gọi thực thi java class với các tham số nếu có Decision Tree 61  break: dừng thread hiện hành. Dùng để dừng các thao tác không mong muốn trước đó  kill: dừng lại và xóa thread hiện hành. Xóa các thao tác đang thực thi trước đó  capabilities : cho phép xem description của các java class trong hệ thống weka  cls: xóa màn hình hiện tại  history: xem lại lịch sử các lần chạy chương trình  exit: thoát khỏi weka simple CLI  help : cung cấp cái nhìn tổng quát cho tất cả các dòng lệnh ở chế độ simple CLI Ví dụ: Chạy dòng lệnh sau: java weka.classifiers.trees.J48 -t test.arff > j48.txt Kết quả thực thi được xuất ra file j48.txt Giao diện chính của môi trường console Decision Tree 62 6.1.3 Demo sử dụng Weka Explorer Trong phần này sẽ trình bày cách sử dụng Weka để xây dựng cây quyết định C4.5 sử dụng dữ liệu play tennis. Dữ liệu được nhập từ file tennis.arff. Các bước thực hiện huấn luyện như sau: a. Nhập dữ liệu Nhấn Open file để import file dữ liệu b. Hiệu chỉnh dữ liệu Hiệu chỉnh dữ liệu để đáp ứng yêu cầu của bài toán Decision Tree 63 c. Chọn thuật toán huấn luyện Chú ý ở đây ta chọn J48 vì Weka implement một thuật toán dựa trên C4.5 gọi nó J48 để giải quyết một số vần đề implement của thuật toán C4.5 Decision Tree 64 d. Cấu hình training set Chọn bộ dữ liệu test thích hợp để test cây sau khi huấn luyện và tính độ lỗi, tỉa cây … e. Start training Nhấn Start để bắt đầu huấn luyện cây Decision Tree 65 f. Xem kết quả Kết quả được hiển thị ở khung Classifier Output. Sử dụng scrollbar để xem kết quả đầy đủ. Cây quyết định kết quả có thể được view ở dạng Cây 1 cách trực quan bằng cách thực hiện như hình vẽ trên. Cây quyết định sau khi chạy có dạng như sau: Decision Tree 66 6.2 Ứng dụng xây dựng 6.2.1 Ứng dụng xây dựng cây quyết định đơn giản 6.2.1.1 Mô tả ứng dụng  Ứng dụng xây dựng cây quyết định dựa trên thuật toán ID3 và C4.5.  Dữ liệu training và testing được import từ file ARFF (theo chuẩn của WEKA).  Kết quả huấn luyện xuất ra màn hình console. 6.2.1.2 Công cụ sử dụng:  Ngôn ngữ lập trình sử dụng: JAVA.  Công cụ lập trình: Eclipse  Framework sử dụng: apache common-lang (để xử lý các thao tác cơ bản trên String) 6.2.1.3 Kết quả thực hiện: Đối với thuật toán ID3 chương trình cho kết quả tương tự như các cây quyết định xây dựng bằng WEKA phiên bản 3.7.5. Tuy nhiên đối với thuật toán C4.5 chỉ xử lý được trên dữ liệu rời rạc. Và không thể so sánh với WEKA vì WEKA không implement thuật toán C4.5 một cách thuần túy. Dưới đây là một số màn hình console thể hiện kết quả huấn luyện: Decision Tree 67 Màn hình thể hiện kết quả huấn luyện cây dự đoán chơi tennis bằng thuật toán C4.5 Decision Tree 68 Màn hình thể hiện kết quả huấn luyện cây dự đoán chơi tennis bằng thuật toán ID3 6.2.2 Ứng dụng lọc thư rác 6.2.2.1 Mô tả ứng dụng  Ứng dụng là một hệ thống web/webservice cung cấp khả năng phân biệt email rác với email thông thường.  Hệ thống có thể dễ dàng tích hợp với các hệ thống mail server, hoặc outlook thông qua cơ chế webservice. 6.2.2.2 Công cụ sử dụng:  Ngôn ngữ lập trình sử dụng: JAVA. Decision Tree 69  Framework sử dụng: - Apache common-lang : dùng để xử lý các thao tác cơ bản trên String - Grails: web framework dùng để xây dựng web/web service framework. - Weka core: dùng để tiền xử lý dữ liệu huấn luyện và cây quyết định - ExtJS: javascript framework dùng để vẽ giao diện màn hình web  Dữ liệu huấn luyện được lấy từ website  Công cụ lập trình: Eclipse 6.2.2.3 Kết quả thực hiện: Kết quả thực hiện được demo ở dạng video được lưu trữ trên Mediafire server: Decision Tree 70 Tài liệu tham khảo [1] [2] Nguyễn Thị Hạnh, T.S Hồ Cẩm Hà, “Khai phá dữ liệu bằng cây quyết định”, 2008 [3] Nguyễn Thị Thùy Linh, “Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định”, 2005. [4] slide của Prof. Pier Luca Lanzi trong file DM2012-07-ClassificationTrees.pdf [5] Lior Rokach, Oded Maimon, “Decision Tree”, Data mining and knowlegde discovery handbook, 2010. [6] [7]