Khóa luận Nghiên cứu kỹ thuật khai phá dữ liệu và ứng dụng trong hệ thống bán sách trực tuyến

họa bước làm đối với mục chọn m) : Bảng 5: Kết quả FP-tree Mục chọn Cơ sở mẫu có điều kiện FP-tree có điều kiện p {(fcam: 2), (cb: 1)} {(c:3)} | p m {(fca: 2), (fcab: 1)} {f:3, c:3, a:3} | m b {(fca: 1), (f: 1), (c: 1)} Empty a {(fc: 3)} {f:3, c:3} | a c {(f: 3)} {f:3} | c f Empty Empty f:4 p:2 c:3 a:3 m:2 c:1 b:1 p:1 f:1 b:1 b:1 r m:1 r f:3 c:3 a:3 FP-tree có điều kiện của m: COUNT ITEM NODE POINTER CHILD POINTERS PARENT POINTER Khai phá FP-tree có điều kiện Hình 13: Khai phá FP-tree có điều kiện Bước 3: Khai phá đệ quy FP-tree có điều kiện r a:3 c:3 f:3 FP-tree có điều kiện của m r c:3 f:3 Cơ sở mẫu có điều kiện của “am”: (fc: 3) FP-tree có điều kiện của am r f:3 Cơ sở mẫu có điều kiện của “cm”: (f: 3) FP-tree có điều kiện của cm r f:3 Cơ sở mẫu có điều kiện của “cam”: (f: 3) FP-tree có điều kiện của cam Hình 14: Khai phá FP-tree có điều kiện Sau khi có được các FP-tree có điều kiện của từng nút, ta có thể sinh ra các mẫu thường xuyên có chứa mục chọn mà nút đó đại diện. Giả sử FP-tree có một đường dẫn đơn P. Tập tất cả mẫu thường xuyên của T có thể được sinh ra bằng cách liệt kê tất cả các tổ hợp của các đường dẫn con của P. r a:3 c:3 f:3 FP-tree có điều kiện của m Tất cả các mẫu thường xuyên có chứa m: m, fm, cm, am, fcm, fam, cam fcam Hình 15: Khai phá FP-tree có điều kiện Kết luận: sự phát triển của các mẫu thường xuyên (FP) có tốc độ tăng lớn hơn trong thuật toán Apriori bởi vì thứ nhất, nó không cần sinh ra tập các mục chọn dự tuyển cũng như kiểm tra tập dự tuyển. Thứ hai là do nó sử dụng FP-tree là cấu trúc dữ liệu có tính cô đọng cao. Thứ ba, nó ngăn ngừa tới mức tối đa các hoạt động liên quan đến việc quét toàn bộ cơ sở dữ liệu một cách lặp đi lặp lại. Cuối cùng, do các hoạt động cơ bản của nó chủ yếu liên quan đến việc đếm và xây dựng các FP-tree. Dưới đây là biểu đồ đánh giá sự so sánh của các mẫu thường xuyên đối với tập dữ liệu thực 50000 58350 66650 75000 Hình 16: Biểu đồ đánh giá sự so sánh của các mẫu thường xuyên với tập dữ liệu thực Thuật toán kết hợp Microsoft Thuật toán kết hợp Microsoft (do Microsoft đưa ra) cũng thuộc về họ các thuật toán tìm luật kết hợp theo thuật toán Apriori tức là việc tìm các luật kết hợp sẽ gồm hai pha chính là tìm tập các mục chọn thường xuyên sau đó dùng tập các mục chọn thường xuyên để sinh ra các luật kết hợp. Vì vậy thuật toán kết hợp Microsoft cũng có các tính chất của luật kết hợp theo thuật toán Apriori. Ngoài ra nó còn có một khái niệm quan trọng khác liên quan trực tiếp đến việc sử dụng thuật toán kết hợp Microsoft. Độ quan trọng (I) Độ quan trọng của một tập các mục chọn được định nghĩa như sau: I ({A, B}) = P (A, B) / (P (A) * P(B)) Nếu I = 1, thì A và B là hai mục chọn độc lập. Tức là việc mua sản phẩm A và việc mua sản phẩm B là hai sự kiện độc lập. Nếu I < 1, thì A và B có mối liên quan với nhau một cách tiêu cực. Tức là khi khách hàng mua sản phẩm A, thì không có khả năng anh ta sẽ mua sản phẩm B. Nếu I >1 thì A và B có mối liên quan với nhau một cách tích cực. Tức là khi khách hàng mua sản phẩm A, thì có khả năng anh ta sẽ mua sản phẩm B. Độ quan trọng của một luật được định nghĩa như sau: I (A => B) = log(p(B | A) / p(B | not A)) Nếu I = 0, thì không có mối liên quan nào giữa A và B. Nếu I > 0, thì khi A xuất hiện xác suất xuất hiện của B tăng lên. Nếu I < 0, thì khi A xuất hiện xác suất xuất hiện của B giảm xuống Remove empty entries Determine candidate itemsets which are containted in transaction TID Build a new storage set The storage set is initialized with the database Take only those with support over minsup Find the support of all the candidates Generate new k-itemsets candidates Count item occurrences Algorithm AprioriTid Trong thuật toán kết hợp Microsoft sử dụng khái niệm xác suất (Probability) thay cho độ tin cậy (Confidence). Ngoài ra nó còn có một danh sách các tham số: Minimum_Support: là một tham số giới hạn. Nó xác định tần suất tối thiểu cho tập các mục chọn, nếu tập các mục chọn có tần suất lớn hơn hoặc bằng Minimum_Support thì tập đó là thường xuyên. Minimum_Support có miền giá trị từ 0 đến 1, giá trị mặc định của nó là 0.03 Nếu Minimum_Support được thiết lập với giá trị lớn hơn 1 lúc đó ta hiểu Minimum_Support chính là số lần xuất hiện của tập các mục chọn. Maximum_Support: là một tham số giới hạn. Nó xác định tần suất tối đa cho tập các mục chọn thường xuyên. Maximum _Support có miền giá trị từ 0 đến 1, giá trị mặc định của nó là 0.03. Nếu Maximum _Support được thiết lập với giá trị lớn hơn 1 lúc đó ta hiểu Maximum _Support chính là số lần xuất hiện của tập các mục chọn. Minimum_Probability: là một tham số giới hạn. Nó xác định xác suất tối thiểu cho một luật kết hợp. Miền giá trị của nó từ 0 đến 1, giá trị mặc định của nó là 0.04. Minimum_Importance: là một tham số giới hạn cho các luật kết hợp. Các luật với độ quan trọng nhỏ hơn Minimu_Importance sẽ bị loại. Maximum_Itemset_Size: xác định kích thước tối đa của tập các mục chọn. Giá trị mặc định của nó là 0, tức là không có giới hạn về kích thước của tập các mục chọn. Minimum_Itemset_Size: xác định kích thước tối thiểu của tập các mục chọn. Giá trị mặc định của nó là 0. Maximum_Itemset_Count: xác định số lượng tối đa của tập các mục chọn. Nếu không được xác định giá trị, thuật toán sẽ sinh ra tất cả tập các mục chọn dựa vào tham số Minimum_Support. Optimized_Prediction_Count: được sử dụng để số lượng các mục chọn đề nghị cho việc dự báo được yêu cầu bởi các truy vấn. Giá trị mặc định của nó là 2. Cây quyết định Giới thiệu Cây quyết định là một phương pháp rất mạnh và phổ biến cho cả hai nhiệm vụ của khai phá dữ liệu là phân loại và dự báo. Sự hấp dẫn đối với các phương pháp dựa vào cây quyết định là các cây quyết định miêu tả các luật. Các luật này có thể sẵn sàng biểu diễn ở dạng tiếng Anh, do đó có con người chúng ta có thể hiểu được chúng. Các luật này cũng có thể được miêu tả bằng ngôn ngữ truy xuất cơ sở dữ liệu như SQL để nhận được danh mục cụ thể trong một danh mục cụ thể. Cây quyết định cũng hữu ích trong việc khảo sát dữ liệu và mô hình hóa dữ liệu để đạt được sự hiểu biết sâu sắc về mối quan hệ giữa một số lượng lớn các biến đầu vào dự tuyển và một biến đích. 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ột nút trong dùng để kiểm tra trên một thuộc tính. Một nhánh dùng để miêu tả một kết quả của phép kiểm tra trên thuộc tính. Một nút lá miêu tả nhãn của lớp hay sự phân phối của lớp đó. Đố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 6 : Dữ liệu thời tiết Outlook Temperature Humidity Windy Play? sunny hot high false No sunny hot high true No overcast hot high false Yes rain mild high false Yes rain cool normal false Yes rain cool normal true No overcast cool normal true Yes sunny mild high false No sunny cool normal false Yes rain mild normal false Yes sunny mild normal true Yes overcast mild high true Yes overcast hot normal false Yes rain mild high true No overcast high normal false true sunny rain No No Yes Yes Yes Outlook Humidity Windy Hình 17: Ví dụ về cây quyết định  Phương pháp xây dựng cây quyết định 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 : Bước 1 : Xây dựng cây quyết định từ trên xuống dưới. Chúng ta bắt đầu xây dựng cây quyết định với tập mẫu tại nút gốc sau đó tiến hành phân tách các mẫu này một cách để quy bằng cách chọn một thuộc tính tại một thời điểm Bước 2 : Chọn lọc cây quyết định từ dưới lên trên. Loại bỏ các cây con hay các nhánh, từ dưới lên trên để tăng sự chính xác trong cách đánh giá với các mẫu mới. 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 Hình 18: Ví dụ về phép phân tách 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á. Từ đặc điểm của phép phân tách ta thấy rằng, tiêu chuẩn để chọn một phép phân tách phù hợp phụ thuộc vào kiểu của biến đích, mà không phục thuộc vào kiểu của biến đầu vào. Với các biến đích định tính (là biến mà giá trị của chúng không khác nhau bởi số lượng hay mức độ, ví dụ giới tính: nam, nữ), thì các phép kiểm tra như Gini, lượng thông tin thu được (Information Gain) và Chi-square là phù hợp nhất, còn đối với các biến kiểu số, phép kiểm tra như F-test là phù hợp nhất. 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. Đo tính hiệu quả của cây quyết định Tính hiệu quả của cây quyết định được xác định bằng việc áp dụng nó vào một tập kiểm tra – là một tập các bản ghi chưa được sử dụng để xây dựng cây quyết định – và theo dõi tỉ lệ phần trăm sự phân loại chính xác. Điều này cung cấp tỉ lệ lỗi phân loại của cây quyết định một cách tổng quan, nhưng cũng thật quan trọng để xác định chất lượng của từng nhánh trong cây quyết định. Mỗi đường dẫn từ đầu đến cuối của cây, miêu tả một luật và luật này có thể tốt hơn luật kia. Tại mỗi nút, có thể là nút lá hay nút nhánh, chúng ta có thể tiến hành đo : Số lượng các bản ghi là thành viên của nút đó. Tỉ lệ bản ghi của mỗi lớp. Những bản ghi đó được phân loại thế nào nếu đây là nút lá. Tỉ lệ phần trăm của các bản ghi được phân loại đúng. Sự khác nhau trong sự phân phối giữa tập luyện và tập kiểm tra. Tỉ lệ phần trăm của các bản ghi được phân loại đúng là chỉ số được quan tâm nhiều nhất. Thật ngạc nhiên, sau khi đo đạc chỉ số này, người ta phát hiện một số nút ở mức cao có tỉ lệ phân tách đúng cao hơn các nút ở mức độ thấp hơn. Điều này đòi hỏi, sau khi xây dựng được cây quyết định chúng ta phải tiến hành bước chọn lọc để loại bỏ những nút có thể dẫn đển kết quả này. Phép kiểm tra để chọn phép phân tách tốt nhất Có rất nhiều các độ đo hữu dụng cho việc đánh giá khả năng của các phép phân tách. Cộng đồng các nhà khoa học theo phương pháp học máy đưa ra các thuật toán làm tăng độ tinh khiết từ kết quả của một phép phân tách, trong khi đó các thuật toán đưa ra bởi công đồng các nhà khoa học theo phương pháp xác suất thống kê lại tập trung vào ý nghĩa thống kê của sự phân phối khác nhau giữa các nút con. Các tiêu chuẩn phân loại khác nhau thường thu được cây quyết định cuối cùng khác nhau, nhưng đều giống nhau về mặt thi hành. Độ tinh khiết Tiêu chuẩn phân loại là làm tăng độ tinh khiết của tập kết quả từ phép phân loại đó. Độ tinh khiết có giá trị trong khoảng từ 0 ( khi không có hai mục chọn nào ở trong cùng một lớp) đến 1 (khi tất cả các mục chọn ở trong cùng một lớp). Một vài phương pháp sử dụng để đánh giá phép phân tách của cây quyết định gán điểm số thấp nhất cho nút tinh khiết ; một số độ đo khác lại gán điểm số cao nhất cho nút tinh khiết. Hình 19: Phép phân loại nhị phân trên một biến định tính làm tăng độ tinh khiết Phương pháp đo độ tinh khiết cho việc đánh giá các phép phân tách đối với các biến đích định tính bao gồm: Gini, Entropy (cũng được gọi là lượng thông tin thu được), tỉ lệ thông tin thu được và phép kiểm tra Chi-square. Khi các biến đích dạng số, hai phương pháp hay dùng là: giảm bớt sự dao động và phép kiểm tra F. Chú ý việc lựa chọn phương pháp đo độ tinh khiết phụ thuộc vào biến đích có kiểu định tính hay kiểu số. Kiểu của biến đầu vào không ảnh hưởng tới lựa chọn này, do đó toàn bộ cây quyết định được xây dựng với một phương pháp duy nhất Phương pháp Gini Một trong những tiêu chuẩn phân tách nổi tiếng có tên là Gini (đặt theo tên nhà xác suất và kinh tế học người Ý Corrado Gini). Phương pháp này, được sử dụng bởi các nhà sinh học và sinh thái học trong việc nghiên cứu tính đa dạng của dân số, để đưa ra xác suất mà hai mục chọn một cách ngẫu nhiêu từ tập dân số giống nhau ở trong cùng một lớp. Đối với tập dân số tinh khiết, xác suất này là 1. Độ đo Gini của tập dữ liệu T với các mẫu thuộc n lớp được tính theo công thức : Gini (T) = ∑ Pi2 n i =1 Trong đó, Pi là tỉ lệ của các lớp do phép = N 1 + N 2 ginisplit (T ) gini(T1) N gini(T2) N Sau khi phân tách T thành hai tập con là T1 và T2 với các kích cỡ lần lượt là N1 và N2, độ đo Gini của phép phân tách được định nghĩa : Giảm Entropy hay lượng thông tin tăng thêm Phương pháp dùng lượng thông tin tăng thêm sử dụng một ý tưởng rất thông minh trong việc định nghĩa độ tinh khiết. Nếu một nút lá hoàn toàn tinh khiết, thì các lớp ở nút đó có thể được miêu tả dễ dàng – chúng cùng rơi cùng vào một lớp giống nhau. Nói một cách khác, nếu một nút lá càng không trong sáng, thì việc miêu tả chúng phức tạp hơn. Lý thuyết thông tin là một bộ phận của khoa học máy tính, đã nghĩ ra một độ do cho tình huống này đó là entropy. Trong lý thuyết thông tin, entropy là một độ đo của việc làm thế nào phá vỡ tổ chức của một hệ thống. Chúng ta có thể hiểu đơn giản, entropy là số bit cần để miêu tả một tình huống cụ thể nào đó hay kết quả, phụ thuộc vào kích cỡ của tập kết quả thu được. Entropy có thể được nghĩ như là số lượng các câu hỏi có/không để xác định các trạng thái của hệ thống. Nếu số trạng thái có thể của hệ thống là 16 thì ta cần Log2 (16), hay 4 bít thông tin để miêu tả hệ thống. Thông tin thêm vào, sẽ làm giảm số lượng câu hỏi có/không dùng để xác định trạng thái của hệ thống, vì vậy lượng thông tin tăng thêm có thể nghĩ như là sự giảm entropy Công thức tình entropy có dạng : Entropy (p1, p2, …, pn) = – p1log2p1 – p2log2p2 – … – pnlog2pn Giả sử phép phân tách trên một thuộc tính tại một nút có tập kết quả gồm n lớp C1, C2, …, Cn với các kích cỡ là N1, N2,… Nn. Công thức tính Entropy của phép phân tích này có dạng : Entropysplit = (N1/N)EntropyC1 + (N2/N)EntropyC2 + … (Nn/N)EntropyCn Sau đây là ví dụ đối với thuộc tính «Outlook» trong ví dụ về dự báo thời tiết ở trên : ‘Outlook’ = ‘Sunny’: Info ([2,3]) = entropy (2/5, 3/5) = – 2/5log2(2/5) – 3/5log2(3/5) = 0.971 bít ‘Outlook’ = ‘Overcast’: Info ([4,0]) = entropy (1, 0) = – 1log2(1) – 0log2(0) = 0 bít Do không có log2(0) nên ta quy ước nó bằng 0 ‘Outlook’ = ‘Rainy’: Info ([3,2]) = entropy (3/5, 2/5) = – 3/5log2(3/5) – 2/5log2(2/5) = 0.971 bít Entropy cho phép phân tách trên thuộc tính « Outlook« : Info ([3,2], [4, 0], [2, 3] ) = (5/14) * 0.971 + (4/14) * 0 + (5/14) * 0.971 = 0.693 bít. Lượng thông tin tăng thêm tại một nút được xác định bằng biểu thức : (Thông tin trước khi phân tách) – ( Thông tin sau khi phân tách) Lượng thông tin tăng thêm cho các thuộc tính trong cơ sở dữ liệu thời tiết ở trên : Rõ ràng ban đầu ta sẽ chọn thuộc tính ‘Outlook’  để 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 : Hình 20: Cây quyết định cuối cùng Phương pháp phân tách dựa trên entropy có thể gặp vấn đề khi kết hợp với phương pháp phân tách dựa trên biến đầu vào định tính bằng cách tạo một nhánh riêng rẽ cho mỗi giá trị. Vấn đề ở đây là, việc chia một tập dữ liệu 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 cũng giảm theo Cơ sở dữ liệu với trường ID : Bảng 6 : Dữ liệu thời tiết với trường ID ID Code Outlook Temperature Humidity Windy Play? A sunny hot high false No B sunny hot high true No C overcast hot high false Yes D rain mild high false Yes E rain cool normal false Yes F rain cool normal true No G overcast cool normal true Yes H sunny mild high false No I sunny cool normal false Yes J rain mild normal false Yes K sunny mild normal true Yes L overcast mild high true Yes M overcast hot normal false Yes N rain mild high true No Lúc đó phép phân tách trên thuộc tính ID có dạng như hình vẽ ở dưới. Và Entropy của phép phân tách này = 0 (bởi vì mỗi nút lá đều tinh khiết, vì chỉ chứa một mẫu duy nhất) Hình 21: Kết quả phép phân tách trên thuộc tính ID Lúc này độ đo lượng thông tin tăng thêm không phù hợp nữa buộc người ta phải đưa ra một độ đo khác hợp lý hơn để thay thế đó là tỉ lệ tăng thêm thông tin. Tỉ lệ tăng thêm thông tin có giá trị lớn khi dữ liệu được trải đều nhau, có giá trị nhỏ khi dữ liệu thuộc về một nhánh. Thông tin bản chất (Intrinsic information) là entropy của sự phân phối của một trương hợp vào một nhánh: Tỉ lệ thông tin tăng thêm được tính theo biểu thức: Ví dụ: Thông tin bản chất cho trường ID code : Tỉ lệ thông tin thu được : Chọn lọc cây quyết định Chọn lọc là quá trính loại bỏ các nhánh và các lá để làm tăng khả năng thực thi dự báo của cây quyết định. Kết quả của quá trình chọn lọc là một tập cây con của cây quyết định đang phát triển. Điều này nghe có vẻ lạ lùng vì tập con của cây quyết định lại có khả năng dự báo hơn chính cây quyết định đang phát triển. Điều này có thể lý giải như sau, cây quyết định đang phát triển được luyện trên một tập dữ liệu xác định, tập dữ liệu này có thể chứa một số mẫu dị thường do những dữ liệu tạp nhiễu gây ra. Mặc dầu cây quyết định tìm các mẫu chung tại các nút lớn, nhưng nó lại tìm ra các mẫu xác định đối với tập luyện trong các nút nhỏ hơn. Điều dẫn đến tình trạng, tính tổng quan của kết quả tìm được sẽ bị cản trở vì dữ liệu mới không cư xử giống như tập luyện cho tất cả các biến, và điều này nên tránh bằng bất cứ giá nào. Phương pháp luận chọn lọc cây quyết định Chọn lọc có thể được tiếp cận hai phương pháp khác nhau : Chọn lọc trước : Cây quyết định có thể được chọn lọc trong pha xây dựng. Dừng việc phát triển một nhánh nếu thông tin trở nên không đáng tin cậy. Chọn lọc sau : Tiến hành phát triển cây quyết định một cách đầy đủ sau đó tiến hành loại bỏ đi các nhánh hoặc các nút lá không đáng tin cậy. Thực tế đã chứng minh, phương pháp chọ lọc sau có tính ưu việt hơn phương pháp chọn lọc trước, vì vậy sau đây, chúng ta sẽ trình bày hai thuật toán theo phương pháp chọn lọc sau : CART và C5. Thuật toán chọn lọc CART Cây phân loại và hồi quy – CART là một trong những thuật toán cây quyết định nổi tiếng đầu tiên được đưa ra vào năm 1984. Thuật toán CART phát triển cây nhị phân và tiếp tục phân tách cho đến khi vẫn tìm thấy phép phân tách làm tăng độ tinh khiết của tập kết quả. Trong hình dưới đây, ta vẫn thấy có rất nhiều cây con đơn giản hơn, mỗi cây con đó là miêu tả sự cân bằng giữa hai yếu tố: độ phức tạp của mô hình và tỉ lệ phân tách sai đối với tập luyện. Thuật toán CART xác định một tập các cây con đó như là mô hình dự tuyển. Những cây dự tuyển này được áp dụng đối với tập dữ liệu phê chuẩn và cây với tỉ lệ phân chia sai trên tập dữ liệu nhỏ nhất sẽ được chọn là mô hình cuối cùng. Hình 22: Ví dụ về tập cây con đơn giản trong một cây hoàn chỉnh Tạo các cây dự tuyển : Thuật toán nhận ra các cây con thông qua một tiến trình chọn lọc được lặp đi lặp lại. Mục tiêu là tiến hành loại bỏ những nhánh mà cung cấp sức mạnh dự báo ít nhất trên mỗi lá. Để xác định những nút lá này có độ hữu ích ít nhất, CART dựa vào một khái niệm gọi là tỷ lệ điều chỉnh lỗi ( adjusted error rate). Hệ số điều chỉnh lỗi dũng để xác định các nhánh « yếu«  (là những nhánh mà có tỉ lệ phân tách lỗi không đủ nhỏ) và đánh dấu chúng để tiến hành loại bỏ. Công thức xác định tỉ lệ điều chỉnh lỗi được xác định bằng : Tỉ lệ điều chỉnh lỗi (T) = Tỉ lệ lỗi (T) + α * Số lượng nút lá (T) Trong đó: α là hệ số điều chỉnh được tăng lên từng bước để tạo những cây con mới. Khi α = 0, tỉ lệ điều chỉnh lỗi bằng tỉ lệ lỗi. Để bắt đầu tìm cây con đầu tiên, tỉ lệ điều chỉnh lỗi cho tất cả các cây con có chứa nút gốc được đánh giá theo α được tăng theo từng bước. Khi tỉ lệ điều chỉnh lỗi của một cây con nhỏ hơn hoặc bằng tỉ lệ điều chỉnh lỗi của cây đầy đủ, ta tìm được cây dự tuyển đầu tiên α1. Tất cả các nhánh không thuộc α1 bị loại bỏ và tiến trình bắt đầu lại từ đầu. Cây α1 được chọn lọc để tạo thành cây α2 và tiến trình sẽ ngừng khi cây được chọn lọc cho kết quả chỉ chứa nút gốc. Mỗi cây con trong tập kết quả là một dự tuyển cho mô hình cuối cùng. Chú ý: tất cả các dự tuyển đều chứa nút gốc và cây dự tuyển lớn nhất là cây đầy đủ. Chọn cây con dự tuyển tốt nhất.  Nhiệm vụ tiếp theo là chọn ra trong tập các cây dự tuyển một cây con mà làm việc với dữ liệu mới một cách tốt nhất. Tập dữ liệu được dùng với mục đích này gọi là tập phê chuẩn (validation set). Mỗi cây con trong tập dự tuyển được sử dụng để phân loại các bản ghi trong tập phê chuẩn. Cây con nào thực hiện nhiệm vụ này với tỉ lệ lỗi thấp nhất là cây chiến thắng (được chọn). Cây chiến thắng được chọn lọc một cách thích đáng để loại bỏ những ảnh hưởng của việc luyện mô hình một cách quá mức nhưng vẫn giữ được những thông tin cần thiết. Sử dụng tập dữ liệu kiểm tra (test set) để đánh giá cây quyết định cuối cùng. Cây con chiến thắng được chọn dựa vào tỉ lệ lỗi của nó khi áp dụng vào việc phân loại các bản ghi trong tập phê chuẩn. Nhưng trong khi chúng ta hi vọng cây con được chọn sẽ tiếp tục là cây con có tốc độ thực thi tốt nhất khi áp dụng đối với tập dữ liệu khác, thì chính tỉ lệ lỗi mà khiến nó được chọn sẽ cường điệu hóa tính hiệu quả của chúng. Để kiểm tra thực thi của cây con được chọn, nó được áp dụng vào một tập dữ liệu thứ ba chưa được phân loại. Tập dữ liệu này không giao với cả tập dữ liệu luyện và tập dữ liệu phê chuẩn. Tập dữ liệu thứ ba này được gọi là tập kiểm tra. Tỉ lệ lỗi thu được trên tập kiểm tra dùng để dự đoán sự thực thi mong muốn của các luật phân loại áp dụng cho tập dữ liệu chưa được phân loại. Thuật toán chọn lọc C5 C5 là phiên bản gần đây nhất của thuật toán cây quyết định do nhà nghiên cứu người Úc J.Ross Quinlan đưa ra và cải tiến trong nhiều năm. Phiên bản sớm hơn – ID3 được đưa ra vào năm 1986 có ảnh hưởng rất lớn trong lĩnh vực học máy. Và các biến thể của nó đã được dùng rất nhiều trong một số sản phẩm mang tính thương mại v