LINK TẢI LUẬN VĂN MIỄN PHÍ CHO AE KET-NOI
MỤC LỤC
Giới thiệu (Đỗ Minh Tuấn)..................................................................................4
1.1 Mô hình cây quyết định ......................................................................................... 4
1.2 Chiến lược cơ bản để xây dựng cây quyết định .................................................... 5
1.3 Thuận lợi và hạn chế của mô hình cây quyết định ................................................ 6
Các tiêu chuẩn tạo cây quyết định (Đỗ Minh Tuấn) ...........................................8
2.1 Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria):......................................... 8
2.1.1 Impurity-based Criteria: .................................................................................. 8
2.1.2 Normalized impurity based criteria: ............................................................. 13
2.1.3 Binary criteria ................................................................................................ 13
2.2 Tiêu chuẩn tách đa chiều: .................................................................................... 14
2.3 Tiêu chuẩn dừng (Stopping Criteria):................................................................... 14
Một số thuật toán (Trần Thị Tuyết Vân) ...........................................................15
3.1 Thuật toán CLS ..................................................................................................... 15
3.2 Thuật toán ID3 ..................................................................................................... 18
3.3 Thuật toán C4.5....................................................................................................22
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.................................. 23
3.4.1 Chọn độ đo Gain Ratio .................................................................................. 23
3.4.2 Xử lý các thuộc tính có kiểu giá trị liên tục ................................................... 24
3.4.3 Làm việc với thuộc tính thiếu giá trị.............................................................. 26
3.4.4 Xử lý các thuộc tính có giá trị chi phí ............................................................ 28
3.5 Thuật toán SPRINT ............................................................................................... 29
3.5.1 SPRINT sử dụng độ đo Gini-index ................................................................. 30
3.5.2 Cấu trúc dữ liệu trong SPRINT....................................................................... 30
3.5.3 Danh sách thuộc tính .................................................................................... 31
3.5.4 Thực thi sự phân chia .................................................................................... 34
Vấn đề Overfitting và các giải pháp giảm Overfitting (Hồ Sơn Lâm)..............37
3.
4.
Decision Tree 2
5.
6.
4.1 Quá khớp dữ liệu (Overfitting) ............................................................................ 37
4.1.1 Định nghĩa: .................................................................................................... 37
4.1.2 Nguyên nhân quá khớp dữ liệu..................................................................... 38
4.2 Phương pháp tránh quá khớp dữ liệu ................................................................. 39
4.2.1 Cắt tỉa để giảm lỗi (Reduced error pruning) ................................................. 40
4.2.2 Luật hậu cắt tỉa (Rule Post-Pruning) ............................................................. 46
Cây quyết định mở rộng (Bùi Tuấn Phụng) ......................................................48
5.1 Oblivious Decision Trees ......................................... Error! Bookmark not defined.
5.2 Fuzzy decision trees ................................................ Error! Bookmark not defined.
5.3 Decision Trees Inducers for Large Datasets............ Error! Bookmark not defined.
5.4 Incremental Induction: ........................................... Error! Bookmark not defined.
Demo (Phan Hoàn Vũ) ......................................................................................53 Tài liệu tham khảo ......................................................................................................... 68
Decision Tree 3
1. Giới thiệu (Đỗ Minh Tuấn)
1.1 Mô hình cây quyết định
Cây quyết định (decision tree) là một trong những hình thức mô tả dữ liệu trực quan nhất, dễ hiểu nhất đối với người dùng. Cấu trúc của một cây quyết định bao gồm các nút và các nhánh. Nút dưới cùng được gọi là nút lá, trong mô hình phân lớp dữ liệu chính là các giá trị của các nhãn lớp (gọi tắt là nhãn). Các nút khác nút lá được gọi là các nút con, đây còn là các thuộc tính của tập dữ liệu, hiển nhiên các thuộc tính này phải khác thuộc tính phân lớp. Mỗi một nhánh của cây xuất phát từ một nút p nào đó ứng với một phép so sánh dựa trên miền giá trị của nút đó. Nút đầu tiên được gọi là nút gốc của cây. Xem xét một ví dụ về một cây quyết định như sau[1]:
Từ bảng dữ liệu trên, ta xây dựng được cây quyết định như sau:
Decision Tree 4
Cây quyết định của ví dụ trên có thể được giải thích như sau: các nút lá chứa các giá trị của thuộc tính phân lớp (thuộc tính “Play”). Các nút con tương ứng với các thuộc tính khác thuộc tính phân lớp; nút gốc cũng được xem như một nút con đặc biệt, ở đây chính là thuộc tính “Outlook”. Các nhánh của cây từ một nút bất kỳ tương đương một phép so sánh có thể là so sánh bằng, so sánh khác, lớn hơn nhỏ hơn... nhưng kết quả các phép so sánh này bắt buộc phải thể hiện một giá trị logic (Đúng hay Sai) dựa trên một giá trị nào đó của thuộc tính của nút. Lưu ý cây quyết định trên không có sự tham gia của thuộc tính “thu nhập” 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) hay 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 lương 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).
1.2 Chiến lược cơ bản để xây dựng cây quyết định
• Bắt đầu từ nút đơn biểu diễn tất cả các mẫu
• Nếu các mẫu thuộc về cùng một lớp, nút trở thành nút lá và được gán nhãn
bằng lớp đó
• Ngược lại, dùng độ đo thuộc tính để chọn thuộc tính sẽ phân tách tốt nhất các
mẫu vào các lớp
Decision Tree 5
• Một nhánh đƣợc tạo cho từng giá trị của thuộc tính được chọn và các mẫu đƣợc phân hoạch theo
• Dùng đệ quy cùng một quá trình để tạo cây quyết định
• Tiến trình kết thúc chỉ khi bất kỳ điều kiện nào sau đây là đúng
- Tất cả các mẫu cho một nút cho trƣớc đều thuộc về cùng một lớp.
- Không còn thuộc tính nào mà mẫu có thể dựa vào để phân hoạch xa
hơn.
- Không còn mẫu nào cho nhánh test_attribute = ai
Tuy nhiên, nếu không chọn được thuộc tính phân lớp hợp lý tại mỗi nút, ta sẽ tạo ca cây rất phức tạp, ví dụ như cây dưới đây:
Như vậy, vấn đề đặt ra là phải chọn được thuộc tính phân lớp tốt nhất. Phần tiếp theo sẽ giới thiệu các tiêu chuẩn, dựa vào các tiêu chuẩn này, ta sẽ chọn ra thuộc tính phân lớp tốt nhất tại mỗi nút.
1.3 Thuận lợi và hạn chế của mô hình cây quyết định
Một số thuận lợi sau đây của cây quyết định được xem như là một công cụ phân loại mà đã chỉ ra trong tài liệu này:
1. Câyquyếtđịnhtựgiảithíchvàkhiđượcgắnkếtlại,chúngcóthểdễdàngtựsinh
ra. Nói cách khác, nếu cây quyết định mà có số lượng nút lá vừa phải thì người Decision Tree 6
không chuyên cũng dễ dàng hiểu được nó. Hơn nữa, cây quyết định cũng có thể
chuyển sang tập luật. Vì vậy, cây quyết định được xem như là dễ hiểu.
2. Câyquyếtđịnhcóthểxửlýcảthuộctínhtênvàsốđầuvào.
3. Thểhiệncủacâyquyếtđịnhlàđủđadạngđểbiểudiễnchobấtkỳgiátrịrờirạc
nào.
4. Câyquyếtđịnhcókhảnăngxửlýcácbộdữliệumàcóthểgâyralỗi.
5. Câyquyếtđịnhcókhảnăngxửlýcácbộdữliệumàcógiátrịrỗng.
6. Cây quyết định được xem như là một phương pháp phi tham số. Điều này có
nghĩa là cây quyết định không có giả định về sự phân chia bộ nhớ và cấu trúc
phân lớp.
Bên cạnh đó, cây quyết định cũng có những bất lợi sau đây:
1. Hầuhếtcácthuậttoán(nhưID3hoặcC4.5)bắtbuộccácthuộctínhmụctiêuphải là các giá trị rời rạc.
2. Khicâyquyếtđịnhsửdụngphươngpháp“chiađểtrị”,chúngcóthểthựchiệntốt nếu tồn tại một số thuộc tính liên quan chặt chẽ với nhau, nhưng sẽ khó khăn nếu một số tương tác phức tạp xuất hiện. Một trong những nguyên nhân gây ra điều này là những sự phân lớp mà có mô tả rất mạch lạc về việc phân lớp cũng có thể gặp khó khăn trong việc biểu diễn bằng cây quyết định. Một minh họa đơn giản của hiện tượng này là vấn đề tái tạo cây quyết định (Pagallo và Huassler, 1990). Khi mà hầu hết các cây quyết định phân chia không gian thể hiện thành những khu vực loại trừ lẫn nhau để biểu diễn một khái niệm, trong một số trường hợp, cây nên chứa một vài cây con giống nhau trong thứ tự thể hiện của việc phân lớp. Ví dụ, nếu khái niệm sau mà thể hiện theo hàm nhị phân: y = (A1 ∩ A2) ∪ (A3 ∩ A4) thì cây quyết định đơn biến tối tiểu mà biểu diễn hàm này đã được biểu diễn trong phần 9.3. Lưu ý là cây có chứa 2 bản sao của cùng một cây con.
3. Các đặc tính liên quan của cây quyết định dẫn đến những khó khăn khác như là độ nhạy với tập huấn luyện, các thuộc tính không phù hợp, nhiễu. (Quinlan, 1993).
Decision Tree 7
2. Các tiêu chuẩn tạo cây quyết định (Đỗ Minh Tuấn)
Việc tìm các tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt. Cho một tập dữ liệu D, một tập các nhãn Ci (i>=1 và i<=m với m là số nhãn), định nghĩa các khái niệm sau:
Ci,D:làtấtcảcácbộdữliệucónhãnlớpCi trongD. |D|:làtổngsốbộdữliệucủatậpdữliệuD. |Ci,D|:làtổngsốbộdữliệucủatậpdữliệuDcónhãnlớpCi.[1]
2.1 Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria):
Nghĩa là tách chỉ dựa trên 1 thuộc tính. Xét theo cấu trúc của mẫu dữ liệu thì có 3 tiêu chuẩn
2.1.1 Impurity-basedCriteria:
Khi tất cả các mẫu dữ liệu thuộc về 1 phân lớp, ta gọi đó là Purity. Ngược lại, khi các mẫu dữ liệu tạo ra nhiều phân lớp thì đó gọi là Impurity. Xét theo tiêu chuẩn Impurity- based thì có các độ đo sau:
2.1.1.1 Information Gain
Các thuật toán cũ trước đây thường dùng độ đo Gain để xác định điểm chia. Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà toán học Claude Shannon, độ đo này xác định giá trị của nội dung mà các thông tin sở hữu trong một loạt các thông điệp. Giả sử tại nút hiện hành N, tập D là tập dữ liệu cần được xác định điểm chia, lặp qua tất cả các thuộc tính và chọn lựa thuộc tính nào có độ đo Gain lớn nhất làm ứng cử viên để phân chia. Công thức tính độ đo Gain như sau [1]:
Vớipi làxácsuấtcủamộtbộbấtkỳtrênDthuộcvềnhãnCi.
Có thể xem công thức Info(D) như một hàm tính giá trị trung bình trên lượng thông tin sử dụng nhằm xác định nhãn của một bộ bất kỳ trong tập D, Info(D) còn được gọi là độ đo sự hỗn loạn (entropy) của D. Giả sử phân chia các bộ trong D 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, a3, ....av}. Nếu thuộc tính A được sử dụng để chia thành v tập con,
Decision Tree 8
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 [1]:
Với |Dj| là tống số bộ dữ liệu được phân chia vào tập con thứ j.
Độ đo Gain được xác định là sự khác biệt giữa thông tin gốc (thông tin khi chưa phân lớp) và thông tin mới (thông tin sau khi đã phân lớp) và được tính theo công thức bên dưới như sau [1] :
Nói một cách khác, độ đo Gain cho biết được lượng thông tin thu được khi phân lớp, thuộc tính nào có độ đo Gain lớn nhất sẽ được chọn làm ứng cử viên để phân chia. Việc chọn thuộc tính theo tiêu chí độ đo Gain lớn nhất tương đương với việc muốn tìm được một phân hoạch sao cho việc phân lớp là tốt nhất hay nói cách khác lượng thông tin cần thiết để hoàn thành việc phân lớp (thể hiện qua giá trị InfoA(D)) là nhỏ nhất [1].
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
Giới thiệu (Đỗ Minh Tuấn)..................................................................................4
1.1 Mô hình cây quyết định ......................................................................................... 4
1.2 Chiến lược cơ bản để xây dựng cây quyết định .................................................... 5
1.3 Thuận lợi và hạn chế của mô hình cây quyết định ................................................ 6
Các tiêu chuẩn tạo cây quyết định (Đỗ Minh Tuấn) ...........................................8
2.1 Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria):......................................... 8
2.1.1 Impurity-based Criteria: .................................................................................. 8
2.1.2 Normalized impurity based criteria: ............................................................. 13
2.1.3 Binary criteria ................................................................................................ 13
2.2 Tiêu chuẩn tách đa chiều: .................................................................................... 14
2.3 Tiêu chuẩn dừng (Stopping Criteria):................................................................... 14
Một số thuật toán (Trần Thị Tuyết Vân) ...........................................................15
3.1 Thuật toán CLS ..................................................................................................... 15
3.2 Thuật toán ID3 ..................................................................................................... 18
3.3 Thuật toán C4.5....................................................................................................22
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.................................. 23
3.4.1 Chọn độ đo Gain Ratio .................................................................................. 23
3.4.2 Xử lý các thuộc tính có kiểu giá trị liên tục ................................................... 24
3.4.3 Làm việc với thuộc tính thiếu giá trị.............................................................. 26
3.4.4 Xử lý các thuộc tính có giá trị chi phí ............................................................ 28
3.5 Thuật toán SPRINT ............................................................................................... 29
3.5.1 SPRINT sử dụng độ đo Gini-index ................................................................. 30
3.5.2 Cấu trúc dữ liệu trong SPRINT....................................................................... 30
3.5.3 Danh sách thuộc tính .................................................................................... 31
3.5.4 Thực thi sự phân chia .................................................................................... 34
Vấn đề Overfitting và các giải pháp giảm Overfitting (Hồ Sơn Lâm)..............37
3.
4.
Decision Tree 2
5.
6.
4.1 Quá khớp dữ liệu (Overfitting) ............................................................................ 37
4.1.1 Định nghĩa: .................................................................................................... 37
4.1.2 Nguyên nhân quá khớp dữ liệu..................................................................... 38
4.2 Phương pháp tránh quá khớp dữ liệu ................................................................. 39
4.2.1 Cắt tỉa để giảm lỗi (Reduced error pruning) ................................................. 40
4.2.2 Luật hậu cắt tỉa (Rule Post-Pruning) ............................................................. 46
Cây quyết định mở rộng (Bùi Tuấn Phụng) ......................................................48
5.1 Oblivious Decision Trees ......................................... Error! Bookmark not defined.
5.2 Fuzzy decision trees ................................................ Error! Bookmark not defined.
5.3 Decision Trees Inducers for Large Datasets............ Error! Bookmark not defined.
5.4 Incremental Induction: ........................................... Error! Bookmark not defined.
Demo (Phan Hoàn Vũ) ......................................................................................53 Tài liệu tham khảo ......................................................................................................... 68
Decision Tree 3
1. Giới thiệu (Đỗ Minh Tuấn)
1.1 Mô hình cây quyết định
Cây quyết định (decision tree) là một trong những hình thức mô tả dữ liệu trực quan nhất, dễ hiểu nhất đối với người dùng. Cấu trúc của một cây quyết định bao gồm các nút và các nhánh. Nút dưới cùng được gọi là nút lá, trong mô hình phân lớp dữ liệu chính là các giá trị của các nhãn lớp (gọi tắt là nhãn). Các nút khác nút lá được gọi là các nút con, đây còn là các thuộc tính của tập dữ liệu, hiển nhiên các thuộc tính này phải khác thuộc tính phân lớp. Mỗi một nhánh của cây xuất phát từ một nút p nào đó ứng với một phép so sánh dựa trên miền giá trị của nút đó. Nút đầu tiên được gọi là nút gốc của cây. Xem xét một ví dụ về một cây quyết định như sau[1]:
Từ bảng dữ liệu trên, ta xây dựng được cây quyết định như sau:
Decision Tree 4
Cây quyết định của ví dụ trên có thể được giải thích như sau: các nút lá chứa các giá trị của thuộc tính phân lớp (thuộc tính “Play”). Các nút con tương ứng với các thuộc tính khác thuộc tính phân lớp; nút gốc cũng được xem như một nút con đặc biệt, ở đây chính là thuộc tính “Outlook”. Các nhánh của cây từ một nút bất kỳ tương đương một phép so sánh có thể là so sánh bằng, so sánh khác, lớn hơn nhỏ hơn... nhưng kết quả các phép so sánh này bắt buộc phải thể hiện một giá trị logic (Đúng hay Sai) dựa trên một giá trị nào đó của thuộc tính của nút. Lưu ý cây quyết định trên không có sự tham gia của thuộc tính “thu nhập” 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) hay 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 lương 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).
1.2 Chiến lược cơ bản để xây dựng cây quyết định
• Bắt đầu từ nút đơn biểu diễn tất cả các mẫu
• Nếu các mẫu thuộc về cùng một lớp, nút trở thành nút lá và được gán nhãn
bằng lớp đó
• Ngược lại, dùng độ đo thuộc tính để chọn thuộc tính sẽ phân tách tốt nhất các
mẫu vào các lớp
Decision Tree 5
• Một nhánh đƣợc tạo cho từng giá trị của thuộc tính được chọn và các mẫu đƣợc phân hoạch theo
• Dùng đệ quy cùng một quá trình để tạo cây quyết định
• Tiến trình kết thúc chỉ khi bất kỳ điều kiện nào sau đây là đúng
- Tất cả các mẫu cho một nút cho trƣớc đều thuộc về cùng một lớp.
- Không còn thuộc tính nào mà mẫu có thể dựa vào để phân hoạch xa
hơn.
- Không còn mẫu nào cho nhánh test_attribute = ai
Tuy nhiên, nếu không chọn được thuộc tính phân lớp hợp lý tại mỗi nút, ta sẽ tạo ca cây rất phức tạp, ví dụ như cây dưới đây:
Như vậy, vấn đề đặt ra là phải chọn được thuộc tính phân lớp tốt nhất. Phần tiếp theo sẽ giới thiệu các tiêu chuẩn, dựa vào các tiêu chuẩn này, ta sẽ chọn ra thuộc tính phân lớp tốt nhất tại mỗi nút.
1.3 Thuận lợi và hạn chế của mô hình cây quyết định
Một số thuận lợi sau đây của cây quyết định được xem như là một công cụ phân loại mà đã chỉ ra trong tài liệu này:
1. Câyquyếtđịnhtựgiảithíchvàkhiđượcgắnkếtlại,chúngcóthểdễdàngtựsinh
ra. Nói cách khác, nếu cây quyết định mà có số lượng nút lá vừa phải thì người Decision Tree 6
không chuyên cũng dễ dàng hiểu được nó. Hơn nữa, cây quyết định cũng có thể
chuyển sang tập luật. Vì vậy, cây quyết định được xem như là dễ hiểu.
2. Câyquyếtđịnhcóthểxửlýcảthuộctínhtênvàsốđầuvào.
3. Thểhiệncủacâyquyếtđịnhlàđủđadạngđểbiểudiễnchobấtkỳgiátrịrờirạc
nào.
4. Câyquyếtđịnhcókhảnăngxửlýcácbộdữliệumàcóthểgâyralỗi.
5. Câyquyếtđịnhcókhảnăngxửlýcácbộdữliệumàcógiátrịrỗng.
6. Cây quyết định được xem như là một phương pháp phi tham số. Điều này có
nghĩa là cây quyết định không có giả định về sự phân chia bộ nhớ và cấu trúc
phân lớp.
Bên cạnh đó, cây quyết định cũng có những bất lợi sau đây:
1. Hầuhếtcácthuậttoán(nhưID3hoặcC4.5)bắtbuộccácthuộctínhmụctiêuphải là các giá trị rời rạc.
2. Khicâyquyếtđịnhsửdụngphươngpháp“chiađểtrị”,chúngcóthểthựchiệntốt nếu tồn tại một số thuộc tính liên quan chặt chẽ với nhau, nhưng sẽ khó khăn nếu một số tương tác phức tạp xuất hiện. Một trong những nguyên nhân gây ra điều này là những sự phân lớp mà có mô tả rất mạch lạc về việc phân lớp cũng có thể gặp khó khăn trong việc biểu diễn bằng cây quyết định. Một minh họa đơn giản của hiện tượng này là vấn đề tái tạo cây quyết định (Pagallo và Huassler, 1990). Khi mà hầu hết các cây quyết định phân chia không gian thể hiện thành những khu vực loại trừ lẫn nhau để biểu diễn một khái niệm, trong một số trường hợp, cây nên chứa một vài cây con giống nhau trong thứ tự thể hiện của việc phân lớp. Ví dụ, nếu khái niệm sau mà thể hiện theo hàm nhị phân: y = (A1 ∩ A2) ∪ (A3 ∩ A4) thì cây quyết định đơn biến tối tiểu mà biểu diễn hàm này đã được biểu diễn trong phần 9.3. Lưu ý là cây có chứa 2 bản sao của cùng một cây con.
3. Các đặc tính liên quan của cây quyết định dẫn đến những khó khăn khác như là độ nhạy với tập huấn luyện, các thuộc tính không phù hợp, nhiễu. (Quinlan, 1993).
Decision Tree 7
2. Các tiêu chuẩn tạo cây quyết định (Đỗ Minh Tuấn)
Việc tìm các tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt. Cho một tập dữ liệu D, một tập các nhãn Ci (i>=1 và i<=m với m là số nhãn), định nghĩa các khái niệm sau:
Ci,D:làtấtcảcácbộdữliệucónhãnlớpCi trongD. |D|:làtổngsốbộdữliệucủatậpdữliệuD. |Ci,D|:làtổngsốbộdữliệucủatậpdữliệuDcónhãnlớpCi.[1]
2.1 Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria):
Nghĩa là tách chỉ dựa trên 1 thuộc tính. Xét theo cấu trúc của mẫu dữ liệu thì có 3 tiêu chuẩn
2.1.1 Impurity-basedCriteria:
Khi tất cả các mẫu dữ liệu thuộc về 1 phân lớp, ta gọi đó là Purity. Ngược lại, khi các mẫu dữ liệu tạo ra nhiều phân lớp thì đó gọi là Impurity. Xét theo tiêu chuẩn Impurity- based thì có các độ đo sau:
2.1.1.1 Information Gain
Các thuật toán cũ trước đây thường dùng độ đo Gain để xác định điểm chia. Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà toán học Claude Shannon, độ đo này xác định giá trị của nội dung mà các thông tin sở hữu trong một loạt các thông điệp. Giả sử tại nút hiện hành N, tập D là tập dữ liệu cần được xác định điểm chia, lặp qua tất cả các thuộc tính và chọn lựa thuộc tính nào có độ đo Gain lớn nhất làm ứng cử viên để phân chia. Công thức tính độ đo Gain như sau [1]:
Vớipi làxácsuấtcủamộtbộbấtkỳtrênDthuộcvềnhãnCi.
Có thể xem công thức Info(D) như một hàm tính giá trị trung bình trên lượng thông tin sử dụng nhằm xác định nhãn của một bộ bất kỳ trong tập D, Info(D) còn được gọi là độ đo sự hỗn loạn (entropy) của D. Giả sử phân chia các bộ trong D 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, a3, ....av}. Nếu thuộc tính A được sử dụng để chia thành v tập con,
Decision Tree 8
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 [1]:
Với |Dj| là tống số bộ dữ liệu được phân chia vào tập con thứ j.
Độ đo Gain được xác định là sự khác biệt giữa thông tin gốc (thông tin khi chưa phân lớp) và thông tin mới (thông tin sau khi đã phân lớp) và được tính theo công thức bên dưới như sau [1] :
Nói một cách khác, độ đo Gain cho biết được lượng thông tin thu được khi phân lớp, thuộc tính nào có độ đo Gain lớn nhất sẽ được chọn làm ứng cử viên để phân chia. Việc chọn thuộc tính theo tiêu chí độ đo Gain lớn nhất tương đương với việc muốn tìm được một phân hoạch sao cho việc phân lớp là tốt nhất hay nói cách khác lượng thông tin cần thiết để hoàn thành việc phân lớp (thể hiện qua giá trị InfoA(D)) là nhỏ nhất [1].
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links