Chuyên đề Nghiên cứu cây quyết định trong Khai phá dữ liệu

d cho phần lớn nhân viên nghỉ vào những ngày trời nắng và ẩm, hoặc những ngày mưa gió. Vì hầu như sẽ chẳng có ai chơi golf trong những ngày đó. Vào những hôm khác, khi nhiều người sẽ đến chơi golf, anh ta có thể thuê thêm nhân viên thời vụ để phụ giúp công việc. Lưu ý : ¡ Cây quyết định trên không có sự tham gia của thuộc tính “Nhiệt độ” trong thành phần cây, các thuộc tính như vậy được gọi chung là các thuộc tính dư thừa bởi vì các thuộc tính này không ảnh hưởng đến quá trình xây dựng mô hình của cây. ¡ Các thuộc tính tham gia vào quá trình phân lớp thông thường có các giá trị liên tục hay còn gọi là kiểu số (ordered or numeric values) hoặc kiểu rời rạc hay còn gọi là kiểu dữ liệu phân loại (unordered or category values). Ví dụ kiểu dữ liệu độ ẩm hay lương có thể biểu diễn bằng số thực là kiểu dữ liệu liên tục, kiểu dữ liệu giới tính là kiểu dữ liệu rời rạc (có thể rời rạc hóa thuộc tính giới tính một cách dễ dàng). Kết luận là cây quyết định giúp ta biến một biểu diễn dữ liệu phức tạp thành một cấu trúc đơn giản hơn rất nhiều. Ưu điểm cây quyết định: So với các phương pháp khai phá dữ liệu khác, cây quyết định là phương pháp có một số ưu điểm: Cây quyết định dễ hiểu. Người ta có thể hiểu mô hình cây quyết định sau khi được giải thích ngắn. Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thường đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị rỗng. Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thường chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số. Cây quyết định là một mô hình hộp trắng. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được. Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho ta có thể tin tưởng vào mô hình. Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong một thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định. CẤU TRÚC CỦA CÂY QUYẾT ĐỊNH: Cây quyết định là một cấu trúc được sử dụng để chia liên tiếp một tập các bản ghi lớn thành các tập con nhỏ hơn bằng cách áp dụng một chuỗi các luật đơn giản. Với mỗi phép chia liên tiếp, các tập con thu được trong tập kết quả sẽ ngày càng giống nhau. Nó có cấu trúc như sau : - Mỗi nút mang một thuộc tính (biến độc lập) - Mỗi nhánh tương ứng với một giá trị của thuộc tính - Mỗi nút lá là một lớp (biến phụ thuộc) Đối với cây quyết định, tại mỗi nút, một thuộc tính sẽ được chọn ra để phân tách tập mẫu thành những lớp khác nhau nhiều nhất có thể. Tiến hành lặp lại bước này đến khi kết thúc ta sẽ có được một tập các lớp đã được định nghĩa trước. Một trường hợp mới sẽ được phân loại dựa vào việc tìm một đường dẫn phù hợp tới nút lá. Ví dụ về cây quyết định : Bảng 1 : Dữ liệu thời tiết Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát TB Nhẹ Có Mưa Mát TB Mạnh Không Âm u Mát TB Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát TB Nhẹ Có Mưa Ấm áp TB Nhẹ Có Nắng Ấm áp TB Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng TB Nhẹ Có Mưa Ấm áp Cao Mạnh Không Âm u Cao Trung bình Nhẹ Mạnh Nắng Mưa Không Không Có Có Có Quang cảnh Độ ẩm Gió PHƯƠNG PHÁP XÂY DỰNG CÂY QUYẾT ĐỊNH: Việc tạo cây quyết định bao gồm 2 giai đoạn : Tạo cây và tỉa cây . Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính được chọn . Việc tỉa cây là xác định và xóa những nhánh mà có phần tử hỗn loạn hoặc những phần tử nằm ngoài (những phần tử không thể phân vào một lớp nào đó) . Có rất nhiều biến đổi khác nhau về nòng cốt của thuật toán cây quyết định, mặc dù vậy chúng vẫn tuân theo những bước cơ bản sau : - Cây được thiết lập từ trên xuống dưới và theo cách thức chia để trị. - Ở thời điểm bắt đầu, các mẫu huấn luyện nằm ở gốc của cây - Thuộc tính được phân loại (Rời rạc hóa các thuộc tính dạng phi số ) - Chọn một thuộc tính để phân chia thành các nhánh. Thuộc tính được chọn dựa trên độ đo thống kê hoặc độ đo heuristic. - Tiếp tục lặp lại việc xây dựng cây quyết định cho các nhánh. Điều kiện để dừng việc phân chia: + Tất cả các mẫu rơi vào một nút thuộc về cùng một lớp (nút lá) + Không còn thuộc tính nào có thể dùng để phân chia mẫu nữa + Không còn lại mẫu nào tại nút. XÂY DỰNG CÂY QUYẾT ĐỊNH: Chọn thuộc tính phân tách: Lúc khởi đầu, ta có trong tay một tập luyện chứa tập các bản ghi được phân loại trước – tức là giá trị của biến đích được xác định trong tất cả các trường hợp. Cây quyết định được xây dựng bằng cách phân tách các bản ghi tại mỗi nút dựa trên một thuộc tính đầu vào. Rõ ràng nhiệm vụ đầu tiên là phải chọn ra xem thuộc tính nào đưa ra được sự phân tách tốt nhất tại nút đó. Độ đo được sử dụng để đánh giá khả năng phân tách là độ tinh khiết. Chúng ta sẽ có những phương pháp xác định để tính toán độ tinh khiết một cách chi tiết, tuy nhiên chúng đều cố gắng đạt được hiệu quả như nhau. Một sự phân tách tốt nhất là sự phân tách làm tăng độ tinh khiết của tập bản ghi với số lượng lớn nhất. Một sự phân tách tốt cũng phải tạo ra các nút có kích cỡ tương tự nhau, hay chí ít cũng không tạo ra các nút có quá ít bản ghi. Dữ liệu gốc Phép phân tách kém Phép phân tách kém Phép phân tách tốt Thuật toán xây dựng cây quyết định hết sức thấu đáo. Chúng bắt đầu bằng việc chọn mỗi biến đầu vào chưa được chọn và đo mức độ tăng độ tinh khiết trong các kết quả ứng với mỗi biến. Sau đó một phép tách tốt nhất sẽ được sử dụng trong phép tách khởi đầu, để tạo hai hay nhiều nút con. Nếu không phép phân tách nào có khả năng (có thể do có quá ít bản ghi) hoặc do không có phép phân tách nào làm tăng độ tinh khiết thì thuật toán kết thúc và nút đó trở thành nút lá. Phép phân tách trên các biến đầu vào kiểu số: đối với sự phân tách nhị phân trên một biến đầu vào, mỗi giá trị mà biến đó chứa đều có thể trở thành giá trị dự tuyển. Phép phân tách nhị phân dựa trên biến đầu vào kiểu số có dạng X < N. Để cải thiện hiệu năng, một số thuật toán không kiểm tra hết toàn bộ các giá trị của biến mà chỉ kiểm tra trên tập mẫu giá trị của biến đó. Phép phân tách trên các biến đầu vào định tính : thuật toán đơn giản nhất trong việc phân tách trên một biến định tính là ứng với mỗi giá trị của biến đó, ta tạo một nhánh tương ứng với một lớp được phân loại. Phương pháp này được sử dụng thực sự trong một số phần mềm nhưng mang lại hiệu quả thấp. Một phương pháp phổ biến hơn đó là nhóm các lớp mà dự đoán cùng kết quả với nhau. Cụ thể, nếu hai lớp của biến đầu vào có phân phối đối với biến đích chỉ khác nhau trong một giới hạn cho phép thì hai lớp này có thể hợp nhất với nhau. Phép phân tách với sự có mặt của các giá trị bị thiếu: một trong những điểm hay nhất của cây quyết định là nó có khả năng xử lý các giá trị bị thiếu bằng cách coi giá trị rỗng (NULL) là một nhánh của nó. Phương pháp này được ưa thích hơn so với việc vứt các bản ghi có giá trị thiếu hoặc cố gắng gắn giá trị nào đó cho nó bởi vì nhiều khi các giá trị rỗng cũng có ý nghĩa riêng của nó. Mặc dù phép phân tách giá trị rỗng như là một lớp riêng rẽ khá có ý nghĩa nhưng người ta thường đề xuất một giải pháp khác. Trong khai phá dữ liêu, mỗi nút chứa vài luật phân tách có thể thực hiện tại nút đó, mỗi phép phân tách đó dựa vào các biến đầu vào khác nhau. Khi giá trị rỗng xuất hiên trong biến đầu vào của phép phân tách tốt nhất, ta sử dụng phép phân tách thay thế trên biến đầu vào có phép phân tách tốt thứ hai. Phép kiểm tra để chọn phép phân tách tốt nhất: - Độ lợi thông tin (Information gain) Information gain là đại lượng được sử dụng để chọn lựa thuộc tính với information gain lớn nhất. Cho P và N là hai lớp và S là một tập dữ liệu có p phần tử lớp P và n phần tử lớp N . Khối lượng thông tin cần thiết để quyết định một mẫu tùy ý có thuộc về lớp P hay N hay không là: Cho các tập {S1, S2 , …, Sv} là một phân hoạch trên tập S, khi sử dụng thuộc tính A. Cho mỗi Si chứa pi mẫu lớp P và ni mẫu lớp N Entropy, hay thông tin mong muốn cần thiết để phân lớp các đối tượng trong tất cả các cây con Si là: Thông tin có được bởi việc phân nhánh trên thuộc tính A là: Ví dụ: Với bảng dữ liệu về dự báo thời tiết ở trên: Lớp P: Chơi_tennis = “Có” Lớp N: Chơi_tennis = “Không” Thông tin cần thiết để phân lớp một mẫu được cho là: Xét thuộc tính ‘Quang cảnh’ ta có : ‘Quang cảnh’ = ‘Nắng’: Info ([2,3]) = entropy (2/5, 3/5) = – 2/5log2(2/5) – 3/5log2(3/5) = 0.971 ‘Quang cảnh’ = ‘Âm u’: Info ([4,0]) = entropy (1, 0) = – 1log2(1) – 0log2(0) = 0 Do không có log2(0) nên ta quy ước nó bằng 0 ‘Quang cảnh’ = ‘Mưa’: Info ([3,2]) = entropy (3/5, 2/5) = – 3/5log2(3/5) – 2/5log2(2/5) = 0.971 Entropy cho phép phân tách trên thuộc tính « Quang cảnh» : = (5/14) * 0.971 + (4/14) * 0 + (5/14) * 0.971 = 0.694 Do đó ta có: = 0.940 – 0.694= 0.246 Xét thuộc tính ‘Độ ẩm’ ta có : ‘Độ ẩm’ = ‘Cao’: Info ([3,4]) = entropy (3/7, 4/7) = – 3/7log2(3/7) – 4/7log2(4/7) = 0.985 ‘Độ ẩm’ = ‘Trung bình’: Info ([6,1]) = entropy (6/7, 1/7) = – 6/7log2(6/7) – 1/7log2(1/7) = 0.592 Entropy(Độ ẩm)= 7/14 Info(3,4) + 7/14 Info(6,1) = 7/14* 0.985 + 7/14* 0.592 = 0.789 Gian(Độ ẩm) = Info(9,5) – Entropy(Độ ẩm) = 0.940 – 0.798 = 0.151 Tương tự cho các thuộc tính còn lại ta có: Rõ ràng ban đầu ta sẽ chọn thuộc tính ‘Quang cảnh’  để phân tách. Sau đó làm tương tự ta sẽ được cây quyết định cuối cùng có dạng : Không Có Có Không Cao Mạnh Nhẹ Quang cảnh Độ ẩm Gió Nắng Mưa TB Có Âm u Cây quyết định cuối cùng BIẾN ĐỔI CÂY QUYẾT ĐỊNH THÀNH LUẬT: Biểu diễn tri thức dưới dạng luật IF-THEN . Mỗi luật tạo ra từ mỗi đường dẫn từ gốc đến lá. Mỗi cặp giá trị thuộc tính dọc theo đường dẫn tạo nên phép kết (phép AND – và) Các nút lá mang tên của lớp VÍ DỤ 1: Không Có Có Không Cao Mạnh Nhẹ Quang cảnh Độ ẩm Gió Nắng Mưa TB Có Âm u R1: If (Quang cảnh=Nắng) Ù (Độ ẩm=Cao) Then Chơi=Không R2: If (Quang cảnh=Nắng) Ù (Độ ẩm=Trung bình) Then Chơi=Có R3: If (Quang cảnh=Âm u) Then Chơi=Có R4: If (Quang cảnh=Mưa) Ù (Gió=Mạnh) Then Chơi=Không R5: If (Quang cảnh=Mưa) Ù (Gió=Nhẹ) Then Chơi=Có THUẬT TOÁN PHÂN LỚP HỌC CÂY QUYẾT ĐỊNH ID3: Giới thiệu: Giải thuật quy nạp cây ID3 (gọi tắt là ID3) là một giải thuật học đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree). Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data). Hay nói khác hơn, giải thuật có: Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó. Đầu ra: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai. Ví dụ, chúng ta hãy xét bài toán phân loại xem ta ‘có đi chơi tennis’ ứng với thời tiết nào đó không. Giải thuật ID3 sẽ học cây quyết định từ tập hợp các ví dụ sau: Tập dữ liệu này bao gồm 14 ví dụ. Mỗi ví dụ biểu diễn cho tình trạng thời tiết gồm các thuộc tính quang cảnh, nhiệt độ, độ ẩm và gió; và đều có một thuộc tính phân loại ‘chơi Tennis’ (có, không). ‘Không’ nghĩa là không đi chơi tennis ứng với thời tiết đó, ‘Có’ nghĩa là ngược lại. Giá trị phân loại ở đây chỉ có hai loại (có, không), hay còn ta nói phân loại của tập ví dụ của khái niệm này thành hai lớp (classes). Thuộc tính ‘Chơi tennis’ còn được gọi là thuộc tính đích (target attribute). Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính quang cảnh có ba giá trị (âm u, mưa, nắng), nhiệt độ có ba giá trị (nóng, mát, ấm áp), độ ẩm có hai giá trị (cao, TB) và gió có hai giá trị (mạnh, nhẹ). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài toán. Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis Nắng Nóng Cao Nhẹ Không Nắng Nóng Cao Mạnh Không Âm u Nóng Cao Nhẹ Có Mưa Ấm áp Cao Nhẹ Có Mưa Mát TB Nhẹ Có Mưa Mát TB Mạnh Không Âm u Mát TB Mạnh Có Nắng Ấm áp Cao Nhẹ Không Nắng Mát TB Nhẹ Có Mưa Ấm áp TB Nhẹ Có Nắng Ấm áp TB Mạnh Có Âm u Ấm áp Cao Mạnh Có Âm u Nóng TB Nhẹ Có Mưa Ấm áp Cao Mạnh Không Từ tập dữ liệu rèn luyện này, giải thuật ID3 sẽ học một cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập này, đồng thời hy vọng trong tương lai, nó cũng sẽ phân loại đúng các ví dụ không nằm trong tập này. Sau khi giải thuật đã quy nạp được cây quyết định, thì cây này sẽ được sử dụng để phân loại tất cả các ví dụ hay thể hiện (instance) trong tương lai. Và cây quyết định sẽ không thay đổi cho đến khi ta cho thực hiện lại giải thuật ID3 trên một tập dữ liệu rèn luyện khác. Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân loại đúng tất cả các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây quyết định khác nhau tùy thuộc vào thứ tự của các kiểm tra trên thuộc tính. Giải thuật ID3 xây dựng cây quyết định từ trên xuống ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên xuống. Lưu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng (partition) có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để phân vùng tập hợp các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy một cây con cho từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân vùng đều nằm trong cùng một lớp; lớp đó trở thành nút lá của cây. Vì thứ tự của các trắc nghiệm là rất quan trọng đối với việc xây dựng một cây QĐ đơn giản, ID3 phụ thuộc rất nhiều vào tiêu chuẩn chọn lựa trắc nghiệm để làm gốc của cây. * ID3 xây dựng cây quyết định theo giải thuật sau: Function induce_tree(tập_ví_dụ, tập_thuộc_tính) begin if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then return một nút lá được gán nhãn bởi lớp đó else if tập_thuộc_tính là rỗng then return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ else begin chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại; xóa P ra khỏi tập_thuộc_tính; với mỗi giá trị V của P begin tạo một nhánh của cây gán nhãn V; Đặt vào phân_vùngV các ví dụ trong tập_ví_dụ có giá trị V tại thuộc tính P; Gọi induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết quả vào nhánh V end end end ö Các khả năng có thể có của các phân vùng (partition): Trong quá trình xây dựng cây QĐ, phân vùng của một nhánh mới có thể có các dạng sau: Có các ví dụ thuộc các lớp khác nhau, chẳng hạn như có cả ví dụ âm và dương. Tất cả các ví dụ đều thuộc cùng một lớp, chẳng hạn như toàn âm hoặc toàn dương. Không còn ví dụ nào => giải thuật trả về mặc nhiên Không còn thuộc tính nào => nghĩa là dữ liệu bị nhiễu, khi đó giải thuật phải sử dụng một luật nào đó để xử lý, chẳng hạn như luật đa số (lớp nào có nhiều ví dụ hơn sẽ được dùng để gán nhãn cho nút lá trả về). Từ các nhận xét này, ta thấy rằng để có một cây QĐ đơn giản, hay một cây có chiều cao là thấp, ta nên chọn một thuộc tính sao cho tạo ra càng nhiều các phân vùng chỉ chứa các ví dụ thuộc cùng một lớp càng tốt. Một phân vùng chỉ có ví dụ thuộc cùng một lớp, ta nói phân vùng đó có tính thuần nhất. Vậy, để chọn thuộc tính kiểm tra có thể giảm thiểu chiều sâu của cây QĐ, ta cần một phép đo để đo tính thuần nhất của các phân vùng, và chọn thuộc tính kiểm tra tạo ra càng nhiều phân vùng thuần nhất càng tốt. ID3 sử dụng lý thuyết thông tin để thực hiện điều này. Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất? Entropy đo tính thuần nhất của tập ví dụ Khái niệm entropy của một tập S được định nghĩa trong Lý thuyết thông tin là số lượng mong đợi các bít cần thiết để mã hóa thông tin về lớp của một thành viên rút ra một cách ngẫu nhiên từ tập S. Trong trường hợp tối ưu, mã có độ dài ngắn nhất. Theo lý thuyết thông tin, mã có độ dài tối ưu là mã gán –log2p bits cho thông điệp có xác suất là p. Trong trường hợp S là tập ví dụ, thì thành viên của S là một ví dụ, mỗi ví dụ thuộc một lớp hay có một giá trị phân loại. Entropy có giá trị nằm trong khoảng [0..1], Entropy(S) = 0 ó tập ví dụ S chỉ toàn ví dụ thuộc cùng một loại, hay S là thuần nhất. Entropy(S) = 1 ó tập ví dụ S có các ví dụ thuộc các loại khác nhau với độ pha trộn là cao nhất. 0 < Entropy(S) < 1 ó tập ví dụ S có số lượng ví dụ thuộc các loại khác nhau là không bằng nhau. Để đơn giản ta xét trường hợp các ví dụ của S chỉ thuộc loại âm (-) hoặc dương (+). Cho trước: • Tập S là tập dữ liệu rèn luyện, trong đó thuộc tính phân loại có hai giá trị, giả sử là âm (-) và dương (+) • p+ là phần các ví dụ dương trong tập S. • p- là phần các ví dụ âm trong tập S. Khi đó, entropy đo độ pha trộn của tập S theo công thức sau: Entropy(S) = -p+log2p+ - p-log2p- Một cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả sử là có c giá trị phân loại thì công thức entropy tổng quát là: Entropy(S) = Lượng thông tin thu được đo mức độ giảm entropy mong đợi Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa một phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lượng thông tin thu được, nó đơn giản là lượng giảm entropy mong đợi gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Một cách chính xác hơn, Gain(S,A) của thuộc tính A, trên tập S, được định nghĩa như sau: Trong đó Values(A) là tập hợp có thể có các giá trị của thuộc tính A, và SV là tập con của S chứa các ví dụ có thuộc tính A mang giá trị v. Trở lại ví dụ ban đầu, nếu không sử dụng Entropy để xác định độ thuần nhất của ví dụ thì có thể xảy ra trường hợp cây quyết định có chiều cao lớn. Ta áp dụng phương thức tính Entropy để xác định chắc chắn thuộc tính nào được chọn trong quá trình tạo cây quyết định. Đầu tiên ta tính độ thuần nhất của tập dữ liệu: Entropy(S) = - (9/14) Log2 (9/14) - (5/14) Log2 (5/14) = 0.940 Từ đó ta tính tiếp Gain cho từng thuộc tính để suy ra thuộc tính nào được chọn làm nút gốc Quang cảnh Nắng Âm u Mưa [2+, 3-] [4+, 0-] [3+, 2-] Gain(S, Quang cảnh) = Entropy(S) – (5/14)Entropy(SNắng) – (4/14)Entropy(SÂm u) – (5/14) Entropy(SMưa) = 0.940 – (5/14)(5/14)(- (2/5)log2(2/5) – (3/5)log2(3/5)) - (4/14)(0) - (5/14)(- (3/5)log2(3/5) – (2/5)log2(2/5)) = 0.246 Nhiệt độ Nóng Ấm áp Mát [2+, 2-] [4+, 2-] [3+, 1-] Gain(S, Nhiệt độ) = Entropy(S) - (4/14)×Entropy(SNóng) - (6/14)×Entropy(SẤm áp) – (4/14)×Entropy(SMát) = 0.940 – (4/14)(1) - (6/14)(- (4/6)log2(4/6) – (2/6)log2(2/6)) - (4/14)(- (3/4)log2(3/4) – (1/4)log2(1/4)) = 0.029 Gió Mạnh Nhẹ [3+, 3-] [6+, 2-] Gain(S, Gió) = Entropy(S) - (6/14)×Entroy(SMạnh) - (8/14)×Entropy(SNhẹ) = 0.940 - (6/14)(1) - (8/14)(- (6/8)log2(6/8) – (2/8)log2(2/8)) = 0.048 Độ ẩm Cao TB [3+, 4-] [6+, 1-] Gain(S, Độ ẩm) = Entropy(S) – (7/14)×Entropy(SCao) – (7/14)×Entropy(STB) = 0.940 – (7/14)(- (3/7)log2(3/7) – (4/7)log2(4/7)) – (7/14)(- (6/7)log2(6/7) – (1/7)log2(1/7)) = 0.151 Ta thấy Gain(S, Quang cảnh) là lớn nhất à lấy thuộc tính quang cảnh làm nút gốc Quang cảnh Nắng Âm u Mưa Có - Không Có Có - Không Sau khi lập được cấp đầu tiên của cây quyết định ta lại xét nhánh Nắng Entropy(SNắng) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 Nóng Ấm áp Nhiệt độ Mát Nắng Quang cảnh [0+, 2-] [1+, 1-] [1+, 0-] Gain(SNắng, Nhiệt độ) = Entropy(SNắng) - (2/5)×Entropy(SNóng) - (2/5)×Entropy(SẤm áp) – (1/5)×Entropy(SMát) = 0.971 – (2/5)×0 - (2/5)×1 - (1/5)×0 = 0.571 Gió Mạnh Nắng Quang cảnh [1+, 1-] [1+, 2-] Nhẹ Gain(SNắng, Gió) = Entroy(SNắng) - (2/5)×Entropy(SNhẹ) - (3/5)×Entropy(SMạnh) = 0.971 - (2/5)×1 - (3/5)(- (1/3)log2(1/3) – (2/3)log2(2/3)) = 0.020 Độ ẩm TB Nắng Quang cảnh [0+, 3-] [2+, 0-] Cao Gain(SNắng, Độ ẩm) = Entropy(SNắng) – (3/5)×Entropy(SCao) – (2/5)×Entropy(STB) = 0.971 – (3/5)(0) – (2/5)(0) = 0.971 Như vậy thuộc tính độ ẩm có hiệu suất phân loại cao nhất trong nhánh Nắng à ta chọn thuộc tính Độ ẩm làm nút kế tiếp. Quang cảnh Cao Độ ẩm Có Mưa Âm u Nắng TB Không Có v Xét nhánh “Mưa”: Nhiệt độ Mát Mưa Quang cảnh [0+, 0-] [2+, 1-] [1+, 1-] Ấm áp Nóng Entropy(SMưa) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 Gain(SMưa, Nhiệt độ) = Entropy(SMưa) - (3/5)×Entropy(SẤm áp) - (2/5)×Entropy(SMát) = 0.971 - (3/5)(- (2/3)log2(2/3) – (1/3)log2(1/3)) - (2/5)(1) = 0.020 Gió Mạnh Mưa Quang cảnh [3+, 0-] [0+, 2-] Nhẹ Gain(SMưa, Gió) = Entropy(SMưa) - (3/5)×Entropy(SNhẹ) - (2/5)×Entropy(SMạnh) = 0.971 - (3/5)×0 - (2/5)×0 = 0.971 Như vậy thuộc tính gió có hiệu suất phân loại cao nhất trong nhánh Mưa à ta chọn thuộc tính Gió làm nút kế tiếp. Quang cảnh Cao Độ ẩm Có Mưa Âm u Nắng TB Không Có Gió Nhẹ Mạnh Có Không v Luật rút ra từ cây quyết định: Ÿ Luật 1: if (Quang cảnh = Nắng) and (Độ ẩm = cao) then Chơi tennis = Không Ÿ Luật 2: if (Quang cảnh = Nắng) and (Độ ẩm = Trung bình) then Chơi tennis= Có Ÿ Luật 3: if (Quang cảnh = Âm u) then Chơi tennis = Có Ÿ Luật 4: if (Quang cảnh = Mưa) and (Gió = Nhẹ) then Chơi tennis = Có Ÿ Luật 5: if (Quang cảnh = Mưa) and (Gió = Mạnh) then Chơi tennis = Không Tìm kiếm không gian giả thuyết trong ID3 Cũng như các phương pháp học quy nạp khác, ID3 cũng tìm kiếm trong một không gian các giả thuyết một giả thuyết phù hợp với tập dữ liệu rèn luyện. Không gian giả thuyết mà ID3 tìm kiếm là một tập hợp các cây quyết định có thể có. ID3 thực hiện một phép tìm kiếm từ đơn giản đến phức tạp, theo giải thuật leo-núi (hill climbing), bắt đầu từ cây rỗng, sau đó dần dần xem xét các giả thuyết phức tạp hơn mà có thể phân loại đúng các ví dụ rèn luyện. Hàm đánh giá được dùng để hướng dẫn tìm kiếm leo núi ở đây là phép đo lượng thông tin thu được. Từ cách nhìn ID3 như là một giải thuật tìm kiếm trong không gian các giả thuyết, ta có một số nhận xét như sau: Không gian giả thuyết các cây quyết định của ID3 là một không gian đầy đủ các cây quyết định trên các thuộc tính đã cho trong tập rèn luyện. Điều này có nghĩa là không gian mà ID3 tìm kiếm chắc chắn có chứa cây quyết định cần tìm. Trong khi tìm kiếm, ID3 chỉ duy trì một giả thuyết hiện tại. Vì vậy, giải thuật này không có khả năng biểu diễn được tất cả các cây quyết định khác nhau có khả năng phân loại đúng dữ liệu hiện có. Vì ID3 sử dụng tất cả các ví dụ ở mỗi bước để đưa ra các quyết định dựa trên thống kê, nên kết quả tìm kiếm của ID3 rất ít bị ảnh hưởng bởi một vài dữ liệu sai (hay dữ liệu nhiễu). Trong quá trình tìm kiếm, giải thuật ID3 có xu hướng chọn cây quyết định ngắn hơn là những cây quyết định dài. Đánh giá hiệu suất của cây quyết định: Một cây quyết định sinh ra bởi ID3 được đánh giá là tốt nếu như cây này có khả năng phân loại đúng được các trường hợp hay ví dụ sẽ gặp trong tương lai, hay cụ thể hơn là có khả năng phân loại đúng các ví dụ không nằm trong tập dữ liệu rèn luyện. Để đánh giá hiệu suất của một cây quyết định người ta thường sử dụng một tập ví dụ tách rời, tập này khác với tập dữ liệu rèn luyện, để đánh giá khả năng phân loại của cây trên các ví dụ của tập này. Tập dữ liệu này gọi là tập kiểm tra (validation set). Thông thường, tập dữ liệu sẵn có sẽ được chia thành hai tập: tập rèn luyện thường chiếm 2/3 số ví dụ và tập kiểm tra chiếm 1/3. Khi nào nên sử dụng ID3 Giải thuật ID3 là một giải thuật học đơn giản nhưng nó chỉ phù hợp với một lớp các bài toán hay vấn đề có thể biểu diễn bằng ký hiệu. Chính vì vậy, giải thuật này thuộc tiếp cận giải quyết vấn đề dựa trên ký hiệu (symbol – based approach). Tập dữ liệu rèn luyện ở đây bao gồm các ví dụ được mô tả bằng các cặp “Thuộc tính – giá trị”, như trong ví dụ ‘Chơi tennis’ trình bày trong suốt chương này, đó là ‘Gió – mạnh’, hay ‘Gió – nhẹ’,… và mỗi ví dụ đều có một thuộc tính phân loại, ví dụ như ‘chơi_tennis’, thuộc tính này phải có giá trị rời rạc, như có, không. Tuy nhiên, khác với một số giải thuật khác cũng thuộc tiếp cận này, ID3 sử dụng các ví dụ rèn luyện ở dạng xác suất nên nó có ưu điểm là ít bị ảnh hưởng bởi một vài dữ liệu nhiễu. Vì vậy, tập dữ liệu rèn luyện ở đây có thể chứa lỗi hoặc có thể thiếu một vài giá trị ở một số thuộc tính nào đó. Một giải pháp thường được áp dụng đối với các dữ liệu bị thiếu là sử dụng luật đa số, chương trình tiền xử lý dữ liệu sẽ điền vào các vị trí còn trống giá trị có tần số xuất hiện cao nhất của thuộc tính đó. VIII. THUẬT TOÁN PHÂN LỚP HỌC CÂY QUYẾT ĐỊNH C4.5 Giới thiệu: - Cây quyết định là phương pháp xấp xỉ hóa bằng hàm mục tiêu những giá trị rời rạc trong đó những hàm được học được thể hiện bằng cây quyết định . Học cây quyết định là một trong những phương pháp thực dụng và được sử dụng rộng rãi nhất cho phương pháp suy diễn qui nạp. - Giải thuật học cây quyết định được sử dụng thành công trong hệ chuyên gia trong việc nắm bắt kiến thức. Công việc chính sử dụng trong các hệ thống này là việc sử dụng phương pháp qui nạp cho những giá trị cho trước của những thuộc tính của một đối tượng chưa biết để xác định sự phân loại xấp xỉ theo những luật của cây quyết định. Cây quyết định sẽ phân loại các trường hợp bằng cách duyệt từ nút gốc đến những nút lá. Chúng ta sẽ bắt đầu từ nút gốc của cây quyết định, kiểm tra thuộc tính xác định bởi nút này sau đó chuyển xuống những nhánh của cây theo giá trị thuộc tính trong tập hợp cho trước. Quá trình này được lặp lại tại những cây con. - Giải thuật cây quyết định thích hợp cho những điều dưới đây: + Mỗi trường hợp được biểu diễn bởi cặp những giá trị thuộc tính. Ví dụ thuộc tính “nhiệt độ“ có những giá trị “nóng”, “mát”, “lạnh”. Chúng cũng đồng thời liên quan đến thuộc tính mở rộng , giá trị tiếp theo, dữ liệu được tính toán ( giá trị thuộc tính bằng số) trong dự án của chúng ta. + Hàm mục tiêu có giá trị đầu ra là những giá trị rời rạc. Nó dễ dàng liên hệ đến trường hợp mà được gán vào một quyết định đúng hoặc sai. Nó cũng có thể mở rộng hàm mục tiêu đến giá trị đầu ra là những giá trị thực. + Những dữ liệu đưa vào có thể chứa đựng nhiều lỗi điều này liên quan đến kĩ thuật giản lược những dữ liệu thừa. - Trong các thuật toán học cây quyết định thì ID3 và C4.5 là hai thuật toán phổ dụng nhất. - Những thiếu sót của giải thuật ID3: + Một thiếu sót quan trọng của ID3 là không gian phân chia hợp lệ tại một node là cạn kiệt . Một sự phân chia là sự phân hoạch của mỗi trường hợp của không gian mà kết quả đạt được từ việc thử nghiệm tại một node quyết định. ID3 và con cháu của nó cho phép sự kiểm tra tại tại một thuộc tính đơn và nhánh trong kết quả cho ra từ sự kiểm tra này. + Một thiếu sót nữa mà ID3 mắc phải là nó dựa vào rất nhiều vào số lượng của những tập hợp dữ liệu đưa vào. Quản lý sự tạp nhiễu của tập dữ liệu vào là vô cùng quan trọng khi chúng ta ứng dụng giải thuật học cây quyết định vào thế giới thực . Ví dụ như Khi có sự lẫn tạp trong tập dữ liệu đưa vào hoặc khi số lượng ví dụ đưa vào là quá nhỏ để tạo ra một ví dụ điển hình của hàm mục tiêu đúng, ID3 có thể dẫn đến việc tạo quyết định sai. + Trong thuật toán ID3, giá trị các thuộc tính là rời rạc, trong khi đó ở thế giới thực còn tồn tại các thuộc tính có giá trị liên tục (giá trị số). + Trong thuật toán ID3, nếu các thuộc tính có nhiều giá trị mà mỗi giá trị lại duy nhất, sẽ dẫn tới tạo cây phức tạp, không đưa ra được quyết định cho các trường hợp trong thực tế. - C4.5 là sự mở rộng của giải thuật ID3 trên một số khía cạnh sau: + Trong việc xây dựng cây quyết định, chúng có thể liên hệ với tập huấn luyện mà có những records với những giá trị thuộc tính không được biết đến bởi việc đánh giá việc thu thập thông tin hoặc là tỉ số thu thập thông tin , cho những thuộc tính bằng việc xem xét chỉ những record mà ở đó thuộc tính được định nghĩa. + Trong việc xây dựng cây quyết định, giải thuật C4.5 có thể giải quyết tốt đối với trường hợp giá trị của các thuộc tính là giá trị thực. + Trong việc xây dựng cây quyết đinh, C4.5 có thể giải quyết tốt đối với trường hợp thuộc tính có nhiều giá trị mà mỗi giá trị này lại duy nhất. Thuật toán xây dựng cây quyết định: Dữ liệu vào: Tập dữ liệu D, tập danh sách thuộc tính, tập nhãn lớp Dữ liệu ra: Mô hình cây quyết định Thuật toán: Tạocây(Tập dữ liệu E, tập danh sách thuộc tính F, tập nhãn lớp) 1 Nếu điều_kiện_dừng(E,F) = đúng 2 nútlá = CreateNode() 3 nútlá.nhãnlớp=Phânlớp(E) 4 return nútlá 5 Ngược lại 6 Nútgốc = CreateNode() 7 Nútgốc.điềukiệnkiểmtra = tìm_điểm_chia_tốt_nhất(E, F) 8 Đặt F = F \ {Nút chọn phân chia} 9 Đặt V = {v| v thoả điều kiện là phần phân chia xuất phát từ Nútgốc} 10 Lặp qua từng tập phân chia v V 11 Đặt Ev = {e | Nútgốc.điềukiệnkiểmtra(e) = v và e E} 12 Nútcon = Tạocây(Ev, F, tập nhãn lớp) 13 Dừng lặp 14 End if 15 Trả về nútgốc. Hàm chính Gọi hàm Tạocây (E, tập danh sách thuộc tính của E, tập nhãn lớp). Giải thích thuật toán: Đây là một thuật toán kiểu đệ qui tạo cây quyết định. + Tại hàm chính, gọi hàm đệ qui Tạocây() với ba tham số vào là tập dữ liệu E, tập danh sách thuộc tính của E và tập nhãn. Thuật toán làm việc bằng cách đệ qui chọn giá trị thuộc tính tốt nhất để chia, lưu ý là chọn giá trị của thuộc tính sao cho điều kiện chia tốt nhất (bước 7), tiếp tục tiến hành mở rộng nút con bằng cách gọi đệ qui cho đến khi điều kiện dừng (ở bước 1) được thỏa mãn. Dưới đây là phần giải thích chi tiết thuật toán: + Dòng đầu tiên sẽ kiểm tra điều kiện dừng, nếu được thỏa mãn nghĩa là đã đệ qui để tạo ra được đến nút lá. Điều kiện dừng chỉ xảy ra khi: ¡ Tất cả các dòng trong tập dữ liệu E thuộc về cùng một lớp duy nhất (1). ¡ Không có bất cứ dòng nào trong tập E, điều này có thể xảy ra khi tập con được tạo ở bước phân chia các tập con là rỗng (2). Trong trường hợp (1) chỉ việc tiến hành tạo nút lá bằng hàm createNode() và tiến hành gán nhãn cho nút lá này bằng cách gán nhãn duy nhất cho thuộc tính nhãn của nút vừa được tạo này. Trường hợp (2) sẽ trả về nút lá bằng rỗng và tiến hành gán nhãn cho nút cha là nhãn lớp xuất hiện nhiều nhất như sau: Nhãn lớp = max (tổng của từng giá trị nhãn lớp riêng biệt trong E). Hàm Phânlớp(E) thực hiện việc xác định nhãn cho một tập dữ liệu E, nó tự động xác định và trả về đúng giá trị nhãn cho cả hai trường hợp trên. + Dòng 3 và 4 xảy ra khi chỉ còn một thuộc tính trong nút cha (lưu ý nút cha là nút sau khi đã phân chia tạo ra tập dữ liệu D này). Nếu sau khi phân chia trên nút cha mà tập D không còn chứa thuộc tính để phân chia, trả về nút lá là giá trị nhãn xuất hiện nhiều nhất trong D. + Xét dòng 5, nếu thuật toán chưa thỏa mãn điều kiện để dừng, tiếp tục xét bằng cách tìm kiếm điểm chia tốt nhất. Để tìm điểm chia tốt nhất cần sử dụng một hàm đánh giá, kết quả của hàm này sẽ trả về thuộc tính được chọn tương ứng. Về các tiêu chuẩn đánh giá cũng như chọn điểm chia sẽ được giải thích rõ hơn trong các phần bên dưới. + Xét dòng 7 và 8, sau khi đã chọn được điểm chia tốt nhất, tiến hành phân chia tập D thành các tập con Di, cập nhật lại danh sách các thuộc tính. + Dòng 9 và 10: lặp qua danh sách các tập con Di và tiến hành gọi đệ qui hàm Tạocây() với tham số mới tương ứng. Độ đo sử dụng để xác định điểm chia tốt nhất: v Entropy: Đại lượng đo tính đồng nhất hay tính thuần nhất của các mẫu. Trong đó: Ÿ S là tập dữ liệu huấn luyện. Ÿ Ci là một nhãn lớp bất kỳ trong tập dữ liệu S. Ÿ Pi là xác suất của một bộ bất kỳ trên S thuộc về nhãn Ci. Giả sử phân chia các bộ trong S trên một thuộc tính A bất kỳ, để không mất tính tổng quát có thể xem như A có các giá trị phân biệt {a1, a2, …, av}. Nếu thuộc tính A được sử dụng để chia thành v tập con, những tập con này sẽ tương ứng với các nhánh con của nút hiện tại, độ đo thông tin có được sau khi phân lớp theo v tập con trên sẽ được tính như sau: Trong đó: là tổng số bộ dữ liệu được phân chia vào tập con thứ j. v Information gain: độ đo xác định ảnh hưởng của một thuộc tính trong mẫu đó trong việc phân lớp gọi là độ lợi thông tin. Độ lợi thông tin dựa trên phân nhánh bằng thuộc tính A: v SplitInformation: Thông tin tiềm ẩn được tạo ra bằng cách chia tập dữ liệu trong một số tập con nào đó. Splitinfomation(S,A) = - Trong đó Si là tập con của S chứa các ví dụ có thuộc tính A mang giá trị Vi. Để ý rằng Splitinfomation thực sự chính là Entropy của S với sự liên quan trên những giá trị của thuộc tính A. v GainRatio: Sự đánh giá thay đổi các giá trị của thuộc tính. Gain(S,A) GainRation(S,A) = SplitInformation(S,A) Tất cả các thuộc tính sẽ được tính toán độ đo tỷ lệ Gain, thuộc tính nào có độ đo tỷ lệ Gain lớn nhất sẽ được chọn làm thuộc tính phân chia. 4. Một số vấn đề với thuộc tính: v Thuộc tính liên tục: Thuật toán ID3 bị giới hạn bởi việc liên quan đến tập những giá trị rời rạc. Trong thuật toán C4.5 chúng ta sẽ mở rộng phạm vi hoạt của nó cho những thuộc tính có giá trị liên tục (giá trị số) để phù hợp với thế giới thực. Thuật toán C4.5 đưa ra định nghĩa những giá trị rời rạc mới để phân những giá trị liên tục thành những thuộc tính tượng trưng một lần nữa theo các quy tắc sau: Dựa trên một giá trị nếu muốn phân chia nhị phân. Dựa trên vài giá trị nếu muốn có nhiều nhánh. Với mỗi giá trị tính các mẫu thuộc một lớp theo dạng A v. Cách chọn giá trị v hiệu quả: + Sắp xếp các giá trị tăng dần. + Chọn giá trị trung bình của từng cặp giá trị của thuộc tính để phân chia và tính chỉ số gain. + Chọn giá trị phân chia có chỉ số gain cao nhất Ví dụ: Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis Nắng Nóng 85 Nhẹ Không Nắng Nóng 90 Mạnh Không Âm u Nóng 78 Nhẹ Có Mưa Ấm áp 96 Nhẹ Có Mưa Mát 80 Nhẹ Có Mưa Mát 70 Mạnh Không Âm u Mát 65 Mạnh Có Nắng Ấm áp 95 Nhẹ Không Nắng Mát 70 Nhẹ Có Mưa Ấm áp 80 Nhẹ Có Nắng Ấm áp 70 Mạnh Có Âm u Ấm áp 90 Mạnh Có Âm u Nóng 75 Nhẹ Có Mưa Ấm áp 80 Mạnh Không Ta có: Entropy(SĐộ ẩm) = - (9/14)log2(9/14) – (5/14)log2(5/14) = 0.940 EntropyĐộ ẩm =67.5(SĐộ ẩm) = (1/14)×Entropy(SĐộ ẩm≤67.5) + (13/14)×Entropy(SĐộ ẩm>67.5) = (1/14)(0) + (13/14)(-8/13log2(8/13) – 5/13log2(5/13)) = 0.893 Gain(SĐộ ẩm, Độ ẩm=67.5) = 0.940 – 0.893 = 0.047 Tính tương tự cho các giá trị còn lại ta có bảng sau: Độ ẩm 65 70 75 78 80 85 90 95 96 67.5 72.5 76.5 79 82.5 87.5 92.5 95.5 ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > Có 1 8 3 6 4 5 5 4 7 2 3 2 8 1 8 1 Không 0 5 1 4 1 4 1 4 2 3 7 2 4 1 5 0 Gain 0.047 0.646 0.045 0.090 0.102 0.025 0.010 0.047 Như vậy ta có giá trị để phân chia là 72.5 ≤72.5 >72.5 Độ ẩm v Thuộc tính nhiều giá trị: Thuộc tính ID3 bị giới hạn bởi việc liên quan đến những thuộc tính có nhiều giá trị, mà các giá trị này lại duy nhất. Khi đó, việc chia một tập dữ liệu thành thành quá nhiều các tập con dẫn đến số lượng các lớp tại mỗi nút giảm và do đó Entropy trên thuộc tính đó cũng giảm theo, nên sự thu thập thông tin (Gain) sẽ cao hơn các thuộc tính khác. Vì vậy thuộc tính này sẽ được lựa chọn thường xuyên để tách, dẫn đến độ phân nhánh lớn, cây sẽ rất lớn và phức tạp. Ví dụ: Ta thêm thuộc tính “Ngày” vào bảng dữ liệu thời tiết về chơi tennis. Ngày Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis D1 Nắng Nóng 85 Nhẹ Không D2 Nắng Nóng 90 Mạnh Không D3 Âm u Nóng 78 Nhẹ Có D4 Mưa Ấm áp 96 Nhẹ Có D5 Mưa Mát 80 Nhẹ Có D6 Mưa Mát 70 Mạnh Không D7 Âm u Mát 65 Mạnh Có D8 Nắng Ấm áp 95 Nhẹ Không D9 Nắng Mát 70 Nhẹ Có D10 Mưa Ấm áp 80 Nhẹ Có D11 Nắng Ấm áp 70 Mạnh Có D12 Âm u Ấm áp 90 Mạnh Có D13 Âm u Nóng 75 Nhẹ Có D14 Mưa Ấm áp 80 Mạnh Không EntropyNgày(S) = Entropy(SD1) + Entropy(SD2) + … + Entropy(SD14) Entropy(SD1) = Entropy(SD2) = … = Entropy(SD14) = 0 → EntropyNgày(S) = 0 Gain(S, Ngày) = Entropy(S) - EntropyNgày(S) = 0.940 Lúc này, thuộc tính ngày có độ đo thông tin cao nhất so với các thuộc tính khác trong tập dữ liệu. Nó sẽ được chọn làm thuộc tính phân tách. Kết quả phép tách trên thuộc tính “Ngày” Ngày Không Không Có Không D1 D2 D3 D14 Ø Điều gì sai với thuộc tính “Ngày” ? Thuộc tính “Ngày” có nhiều nhất những giá trị trong việc phân chia tập dữ liệu huấn luyện thành những tập nhỏ. Cũng chính vì điều này nó sẽ có thu thập thông tin rất cao liên quan đến tập dữ liệu huấn luyện. Tuy nhiên nó lại là một công cụ tiên đoán tồi của hàm mục tiêu trên những trường hợp vô hình. Ø Giải quyết vấn đề này như thế nào ? Lựa chọn thuộc tính để phân tách theo nguyên tắc: Tỉ lệ tăng thêm thông tin (GainRatio) cao. Có Entropy của thuộc tính lớn hơn Entropy trung bình của tất cả các thuộc tính. v Thuộc tính thiếu giá trị: Ø Nếu giá trị của thuộc tính A bị mất trên một số bộ dữ liệu, hướng giải quyết sẽ thế nào ? Giả sử rằng (x, C(x)) là một trong những tập huấn luyện trong S và giá trị A(x) là không được biết đến. Ø Giải pháp: Thay bằng giá trị xuất hiện nhiều nhất của thuộc tính A. Thay bằng giá trị xuất hiện nhiều nhất của thuộc tính A mà có cùng giá trị hàm mục tiêu. Tính lại các công thức dựa trên những giá trị đã có của thuộc tính A (loại các giá trị bị thiếu, nếu số lượng các giá trị bị thiếu không nhiều). Ví dụ: Ngày Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis D1 Nắng Nóng 85 Nhẹ Không D2 Nắng Nóng 90 Mạnh Không D3 Âm u Nóng 78 Nhẹ Có D4 Mưa Ấm áp 96 Nhẹ Có D5 Mưa Mát 80 Nhẹ Có D6 Mưa Mát 70 Mạnh Không D7 Âm u Mát 65 Mạnh Có D8 Nắng Ấm áp 95 Nhẹ Không D9 Nắng Mát 70 Nhẹ Có D10 Mưa Ấm áp 80 Nhẹ Có D11 Nắng Ấm áp 70 Mạnh Có D12 Âm u Ấm áp 90 Mạnh Có D13 Âm u Nóng 75 Nhẹ Có D14 Mưa Ấm áp 80 Mạnh Không D15 Mưa Mát 70 Không Gió: [9 nhẹ, 5 mạnh] → Giá trị của thuộc tính “Gió” ở bản ghi thứ 15 sẽ là: Nhẹ Gió: Nhẹ Mạnh Mạnh Nhẹ Mạnh Chơi Tennis: không Không Không Không Không → Giá trị của thuộc tính “Gió” ở bản ghi thứ 15 sẽ là: Mạnh 5. Ví dụ: Ngày Quang cảnh Nhiệt độ Độ ẩm Gió Chơi tennis D1 Nắng Nóng 85 Nhẹ Không D2 Nắng Nóng 90 Mạnh Không D3 Âm u Nóng 78 Nhẹ Có D4 Mưa Ấm áp 96 Nhẹ Có D5 Mưa Mát 80 Nhẹ Có D6 Mưa Mát 70 Mạnh Không D7 Âm u Mát 65 Mạnh Có D8 Nắng Ấm áp 95 Nhẹ Không D9 Nắng Mát 70 Nhẹ Có D10 Mưa Ấm áp 80 Nhẹ Có D11 Nắng Ấm áp 70 Mạnh Có D12 Âm u Ấm áp 90 Mạnh Có D13 Âm u Nóng 75 Nhẹ Có D14 Mưa Ấm áp 80 Mạnh Không Dữ liệu vào: + Tập dữ liệu thời tiết. + Tập danh sách thuộc tính: Ngày, Quang cảnh, Nhiệt độ, Độ ẩm, Gió. + Tập nhãn lớp: Có – Không. Dữ liệu ra: Mô hình cây quyết định chơi tennis. Tạo cây quyết định: Ä Lần tạo cây đầu tiên: Ø Tìm_điểm_chia_tốt_nhất(E, F): + E: Tập dữ liệu thời tiết. + F: Ngày, Quang cảnh, Nhiệt độ, Độ ẩm, Gió. S[9+, 3-] +: D3, D4, D5, D7, D9, D10, D11, D12, D13 - : D1, D2, D6, D8, D14 Entropy(S) = -(9/14)log2(9/14) – (5/14)log2(5/14) = 0.940 ¯Độ đo tỉ lệ gain cho thuộc tính “Quang cảnh”: Quang cảnh Nắng Âm u Mưa [2+, 3-] [4+, 0-] [3+, 2-] EntropyQuang cảnh(S)=(5/14)×Entropy(SNắng)+(4/14)×Entropy(SÂm u)+ (5/14)×Entropy(SMưa) = (5/14)(- (2/5)log2(2/5) – (3/5)log2(3/5)) + (4/14)(0) + (5/14)(- (3/5)log2(3/5) – (2/5)log2(2/5)) = 0.694 Gain(S, Quang cảnh) = Entropy(S) – EntopyQuang cảnh(S) = 0.940 – 0.694 = 0.246 SplitInfomation(S, Quang cảnh) = - (5/14)log2(5/14) - (4/14)log2(5/14) - (5/14)log2(5/14) = 1.577 GainRatio(S, Quang cảnh) = 0.246/1.577 = 0.156 ¯ Độ đo tỉ lệ gain cho thuộc tính “Gió”: Gió Mạnh Nhẹ [3+, 3-] [6+, 2-] EntropyGió(S) = (6/14)×Entroy(SMạnh) + (8/14)×Entropy(SNhẹ) = (6/14)(1) + (8/14)(- (6/8)log2(6/8) – (2/8)log2(2/8)) = 0.892 Gain(S, Gió) = Entropy(S) – EntropyGió(S) = 0.940 – 0.892 = 0.048 SplitInfomation(S, Gió) = -(6/14)log2(6/14) – (8/14)log2(8/14) = 0.985 GainRatio(S, Gió) = 0.048/0.985 = 0.049 ¯ Độ đo tỉ lệ gain cho thuộc tính “Độ ẩm”: Độ ẩm ≤ 72.5 72.5 [3+, 1-] [6+, 4-] EntropyĐộ ẩm(S) = (4/14)×Entropy(S72.5) = (4/14)(- (3/4)log2(3/4) – (1/4)log2(1/4)) + (10/14)(-(6/10)log2(6/10) – (4/10)log2(4/10)) = 0.925 Gain(S, Độ ẩm) = Entropy(S) - EntropyĐộ ẩm(S) = 0.940 – 0.925 = 0.015 SplitInfomation(S, Độ ẩm) = -(4/14)log2(4/14) – (10/14)log2(10/14) = 0.863 GainRatio(S, Độ ẩm) = 0.015/0.863 = 0.017 ¯ Độ đo tỉ lệ gain cho thuộc tính “Nhiệt độ”: Nhiệt độ Nóng Ấm áp Mát [2+, 2-] [4+, 2-] [3+, 1-] EntropyNhiệt độ(S) = (4/14)×Entropy(SNóng)+(6/14)×Entropy(SẤm áp)+(4/14)×Entropy(SMát) = (4/14)(1) + (6/14)(- (4/6)log2(4/6) – (2/6)log2(2/6)) + (4/14)(- (3/4)log2(3/4) – (1/4)log2(1/4)) = 0.911 Gain(S, Nhiệt độ) = Entropy(S) - EntropyNhiệt độ(S) = 0.940 – 0.911 = 0.029 SplitInfomation(S, Nhiệt độ) = - (4/14)log2(4/14) – (6/14)log2(6/14) – (4/14)log2(4/14) = 1.557 GainRatio(S, Nhiệt độ) = 0.028/1.557 = 0.019 ¯ Độ đo tỉ lệ gain cho thuộc tính “Ngày”: EntropyNgày(S) = (1/14)×Entropy(SD1) + … + (1/14)×Entropy(SD14) = 14×(1/14)×(0) = 0 Gain(S, Ngày) = Entropy(S) - EntropyNgày(S) = 0.940 – 0 = 0.940 SplitInfomation(S, Ngày) = 14×(- (1/14)log2(1/14)) = 3.807 GainRatio(S, Ngày) = 0.940/3.807 = 0.246 v Lựa chọn thuộc tính tốt nhất để phân chia: Entropy trung bình của các thuộc tính = (0.694 + 0.892 + 0.925 + 0.911 + 0)/5 = 0.684 Ta có: GainRatio(S, Quang cảnh) = 0.156 EntopyQuang cảnh(S) = 0.694 > 0.684 è Thuộc tính được chọn để phân chia: Quang cảnh Quang cảnh Nắng Âm u Mưa Có - Không Có Có - Không Ä Lần tạo cây thứ hai: ä Nhánh “Nắng”: ¯ Độ đo tỉ lệ gain cho thuộc tính “Nhiệt độ”: Nóng Ấm áp Nhiệt độ Mát Nắng Quang cảnh [0+, 2-] [1+, 1-] [1+, 0-] Entropy(SNắng) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 EntropyNhiệt độ(SNắng)=(2/5)×Entropy(SNóng) + (2/5)×Entropy(SẤm áp) + (1/5)×Entropy(SMát) = (2/5)×0 + (2/5)×1 + (1/5)×0 = 0.4 Gain(SNắng, Nhiệt độ) = 0.971 – 0.400 = 0.571 SplitInfomation(SNắng, Nhiệt độ) = - (2/5)log2(2/5) – (2/5)log2(2/5) – (1/5)log2(1/5) = 1.522 GainRatio(SNắng, Nhiệt độ) = 0.571/1.522 = 0.375 ¯ Độ đo tỉ lệ gain cho thuộc tính “Độ ẩm”: Chọn giá trị phân chia tốt nhất: Entropy(SĐộ ẩm) = - (2/5)log2(2/5) – (3/5)log2(3/5) = 0.971 Độ ẩm 70 85 90 95 77.5 87.5 92.5 ≤ > ≤ > ≤ > Có 2 0 2 0 2 0 Không 0 3 1 2 2 1 Gain 0.971 0.420 0.171 Độ ẩm > 77.5 Nắng Quang cảnh [2+, 0-] [0+, 3-] ≤ 77.5 EntropyĐộ ẩm(SNắng) = (2/5)×Entropy(S72.5) = (2/5)×0 + (3/5)×0 = 0 Gain(SNắng, Độ ẩm) = 0.971 – 0 = 0.971 SplitInfomation(SNắng, Độ ẩm) = - (2/5)log2(2/5) – (3/5)log2(3/5) = 0.971 GainRatio(SNắng, Độ ẩm) = 0.971/0.971 = 1 ¯ Độ đo tỉ lệ gain của thuộc tính “Gió”: Gió Mạnh Nắng Quang cảnh [1+, 1-] [1+, 2-] Nhẹ EntropyGió(SNắng) = (2/5)×Entropy(SNhẹ) + (3/5)×Entropy(SMạnh) = (2/5)×1 + (3/5)(- (1/3)log2(1/3) – (2/3)log2(2/3)) = 0.951 Gain(SNắng, Gió) = 0.971 – 0.951 = 0.020 SplitInfomation(SNắng, Gió) = - (2/5)log2(2/5) – (3/5)log2(3/5) = 0.971 GainRatio(SNắng, Gió) = 0.020/0.971 = 0.021 ¯ Độ đo tỉ lệ gain cho thuộc tính “Ngày”: Ngày Nắng Quang cảnh [0+, 1-] [0+, 1-] D1 D2 D8 D9 D11 [0+, 1-] [1+, 0-] [1+, 0-] EntropyNgày(SNắng) = (1/5)×Entropy(SD1) + (1/5)×Entropy(SD2) + (1/5)×Entropy(SD8) + (1/5)×Entropy(SD9) + (1/5)×Entropy(SD11) = 0 Gain(SNắng, Ngày) = 0.971 – 0 = 0.971 SplitInfomation(SNắng, Ngày) = 5×(-1/5×log2(1/5)) = 2.322 GainRatio(SNắng, Ngày) = 0.971/2.322 = 0.418 è Thuộc tính được chọn để phân chia: Độ ẩm Quang cảnh ≤ 77.5 Độ ẩm Có - Không Có Mưa Âm u Nắng > 77.5 Có Không ä Nhánh “Mưa”: ¯ Độ đo tỉ lệ gain cho thuộc tính “Nhiệt độ”: Nóng Ấm áp [1+, 1-] [2+, 1-] [0+, 0-] Quang cảnh Mưa Mát Nhiệt độ Entropy(SMưa) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 EntropyNhiệt độ(SMưa) = (3/5)×Entropy(SẤm áp) + (2/5)×Entropy(SMát) = (3/5)(- (2/3)log2(2/3) – (1/3)log2(1/3)) + (2/5)(1) = 0.951 Gain(SMưa, Nhiệt độ) = 0.971 – 0.951 = 0.020 SplitInfomation(SMưa, Nhiệt độ) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 GainRatio(SMưa, Nhiệt độ) = 0.020/0.971 = 0.021 ¯ Độ đo tỉ lệ gain cho thuộc tính “Gió”: Gió Mạnh Mưa Quang cảnh [3+, 0-] [0+, 2-] Nhẹ EntropyGió(SMưa) = (3/5)×Entropy(SNhẹ) + (2/5)×Entropy(SMạnh) = (3/5)×0 + (2/5)×0 = 0 Gain(SMưa, Gió) = 0.971 – 0 = 0.971 SplitInfomation(SMưa, Gió) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 GainRatio(SMưa, Gió) = 0.971/0.971 = 1 ¯ Độ đo tỉ lệ gain cho thuộc tính “Ngày”: Ngày Mưa Quang cảnh [1+, 0-] [1+, 0-] D4 D5 D6 D10 D14 [0+, 1-] [1+, 0-] [0+, 1-] EntropyNgày(SMưa) = (1/14)×Entropy(SD4) + (1/14)×Entropy(SD5) + (1/14)×Entropy(SD6) + (1/14)×Entropy(SD10) + (1/14)×Entropy(SD14) = 0 Gain(SMưa, Ngày) = 0.971 – 0 = 0.971 SplitInfomation(SMưa, Ngày) = 5×(-1/5×log2(1/5)) = 2.322 GainRatio(SMưa, Ngày) = 0.971/2.322 = 0.418 è Thuộc tính được chọn để phân chia: Gió Quang cảnh ≤ 77.5 Độ ẩm Có Mưa Âm u Nắng > 77.5 Có Không Gió Nhẹ Mạnh Có Không Luật rút ra từ cây quyết định: Ÿ Luật 1: if (Quang cảnh = Nắng) and (Độ ẩm ≤ 77.5) then Chơi tennis = Có Ÿ Luật 2: if (Quang cảnh = Nắng) and (Độ ẩm < 77.5) then Chơi tennis = Không Ÿ Luật 3: if (Quang cảnh = Âm u) then Chơi tennis = Có Ÿ Luật 4: if (Quang cảnh = Mưa) and (Gió = Nhẹ) then Chơi tennis = Có Ÿ Luật 5: if (Quang cảnh = Mưa) and (Gió = Mạnh) then Chơi tennis = Không ỨNG DỤNG CÂY QUYẾT ĐỊNH TRONG CƠ SỞ DỮ LIỆU THỰC TẾ: Tuổi Thu nhập Sinh viên Đánh giá độ tín nhiệm (trong tín dụng mua chịu) Mua máy tính Thanh niên Cao Không Trung bình Không Thanh niên Cao Không Tốt Không Trung niên Cao Không Trung bình Có Già Trung bình Không Trung bình Có Già Thấp Có Trung bình Có Già Thấp Có Tốt Không Trung niên Thấp Có Tốt Có Thanh niên Trung bình Không Trung bình Không Thanh niên Thấp Có Trung bình Có Già Trung bình Có Trung bình Có Thanh niên Trung bình Có Tốt Có Trung niên Trung bình Không Tốt Có Trung niên Cao Có Trung bình Có Già Trung bình không Tốt Không Entropy(S) = - (9/14) Log2 (9/14) - (5/14) Log2 (5/14) = 0.940 Tuổi Thanh niên Trung niên Già [2+, 3-] [4+, 0-] [3+, 2-] Gain(S, Tuổi) = Entropy(S) – (5/14)Entropy(SThanh niên) – (4/14)Entropy(STrung niên) – (5/14) Entropy(SGià) = 0.940 – (5/14)(5/14)(- (2/5)log2(2/5) – (3/5)log2(3/5)) - (4/14)(0) - (5/14)(- (3/5)log2(3/5) – (2/5)log2(2/5)) = 0.246 Thu nhập Cao Trung bình Thấp [2+, 2-] [4+, 2-] [3+, 1-] Gain(S, Thu nhập) = Entropy(S) - (4/14)×Entropy(SCao) - (6/14)×Entropy(STrung bình) – (4/14)×Entropy(SThấp) = 0.940 – (4/14)(1) - (6/14)(- (4/6)log2(4/6) – (2/6)log2(2/6)) - (4/14)(- (3/4)log2(3/4) – (1/4)log2(1/4)) = 0.029 Sinh viên Không Có [3+, 4-] [6+, 1-] Gain(S, Sinh viên) = Entropy(S) – (7/14)×Entropy(SKhông) – (7/14)×Entropy(SCó) = 0.940 – (7/14)(- (3/7)log2(3/7) – (4/7)log2(4/7)) – (7/14)(- (6/7)log2(6/7) – (1/7)log2(1/7)) = 0.151 Đánh giá độ tín nhiệm (trong tín dụng mua chịu) Tốt Trung bình [3+, 3-] [6+, 2-] Gain(S, Độ tín nhiệm) = Entropy(S) - (6/14)×Entroy(STốt) - (8/14)×Entropy(STrung bình) = 0.940 - (6/14)(1) - (8/14)(- (6/8)log2(6/8) – (2/8)log2(2/8)) = 0.048 Tuổi Ta thấy Gain(S, Tuổi) là lớn nhất à lấy thuộc tính “Tuổi” làm nút gốc. Già Trung niên Thanh niên Có - Không Có Có - Không v Xét nhánh “Thanh niên”: Entropy(SThanh niên) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 Cao Trung bình Thu nhập Thấp Thanh niên Tuổi [0+, 2-] [1+, 1-] [1+, 0-] Gain(SThanh niên, Thu nhập) = Entropy(SThanh niên) - (2/5)×Entropy(SCao) – (2/5)×Entropy(STrung bình) – (1/5)×Entropy(SThấp) = 0.971 – (2/5)×0 - (2/5)×1 - (1/5)×0 = 0.571 Sinh viên Có Thanh niên Tuổi [0+, 3-] [2+, 0-] Không Gain(SThanh niên, Sinh viên) = Entropy(SThanh niên) – (3/5)×Entropy(SKhông) – (2/5)×Entropy(SCó) = 0.971 – (3/5)(0) – (2/5)(0) = 0.971 Độ tin cậy Tốt Thanh niên Tuổi [1+, 1-] [1+, 2-] Trung bình Gain(SThanh niên, Độ tin cậy) = Entroy(SThanh niên) - (2/5)×Entropy(STrung bình) – (3/5)×Entropy(STốt) = 0.971 - (2/5)×1 - (3/5)(- (1/3)log2(1/3) – (2/3)log2(2/3)) = 0.020 Ta thấy Gain(SThanh niên, Sinh viên) là lớn nhất trong nhánh “Sinh viên” à lấy thuộc tính “Sinh viên” làm nút kế tiếp để phân chia. Sinh viên Trung niên Thanh niên Có Không Tuổi Không Có Già Có Có - Không v Xét nhánh “Già”: Entropy(SGià) = - (3/5)log2(3/5) – (2/5)log2(2/5) = 0.971 Thu nhập Thấp Già Tuổi [0+, 0-] [2+, 1-] [1+, 1-] Trung bình Cao Gain(SGià, Thu nhập) = Entropy(SGià) - (3/5)×Entropy(STrung bình) - (2/5)×Entropy(SThấp) = 0.971 - (3/5)(- (2/3)log2(2/3) – (1/3)log2(1/3)) - (2/5)(1) = 0.020 Độ tin cậy Trung bình Già Tuổi [3+, 0-] [0+, 2-] Tốt Gain(SGià, Độ tin cậy) = Entropy(SGià) - (3/5)×Entropy(STrung bình) - (2/5)×Entropy(STốt) = 0.971 - (3/5)×0 - (2/5)×0 = 0.971 Ta thấy Gain(SGià, Độ tin cậy) là lớn nhất trong nhánh “Già” à lấy thuộc tính “Độ tin cậy” làm nút kế tiếp để phân chia. Sinh viên Trung niên Thanh niên Tuổi Không Có Già Có Không Có Độ tin cậy Tốt Trung bình Có Không Ø Luật rút ra từ cây quyết định: § Luật 1: If (Tuổi = Thanh niên) and (Sinh viên = có) Then (mua máy tính = Có) § Luật 2: If (Tuổi = Thanh niên) and (Sinh viên = Không) Then (mua máy tính = Không) § Luật 3: If (Tuổi = Trung niên) Then (mua máy tính = Có) § Luật 4: If (Tuổi = Già) and (Độ tin cậy = Tốt) Then (Mua máy tính = Có) § Luật 5: If (Tuổi = Giá) and (Độ tin cậy = trung bình) Then (Mua máy tình = Không)