ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
________________
BÀI THU HOẠCH
CHUYÊN ĐỀ KHAI THÁC DỮ LIỆU VÀ KHO DỮ LIỆU
MÔ HÌNH CÂY QUYẾT ĐỊNH
THUẬT TOÁN C4.5
Giáo viên hướng dẫn:
PGS.TS. Đỗ Phúc
Học viên thực hiện:
Thái Hồng Quang
CH1101033
Lớp:
Thạc sỹ CNTT qua mạng khoá 06
Lời giới thiệu
Mô hình cây quyết định là một trong những phương pháp phổ biến và được áp dụng nhiều trong
thực tế cho các bài toán phân lớp và dự đoán. Chương này sẽ giới thiệu chung về mô hình cây
quyết định, một số độ đo phổ biến được áp dụng trong các thuật toán, thuật toán ID3, C4.5, và
một số vấn đề mở rộng của cây quyết định.
1. Giới thiệu
Mô hình học cây quyết định là phương pháp cho việc xấp xỉ các hàm mục tiêu có giá trị rời
rạc và được biểu diễn dưới dạng cây quyết định. Cây quyết định sau khi được học có thể biểu
diễn lại dưới dạng luật if-then để tăng khả năng dễ đọc. Đây là một trong những phương pháp
được sử dụng phổ biến nhất trong số các thuật toán học quy nạp, và nó đã được áp dụng khá
thành công trong ứng dụng y khoa và tài chính như chẩn đoán bệnh hay đánh giá rủi ro tín dụng.
1.1. Cây quyết định và một số ứng dụng
Cây quyết định là một phương pháp phân lớp thuộc nhóm học có giám sát (supervised
learning) như: dựa trên luật (rule-based), mạng Bayes (naïve Bayes), mạng nơron, SVM,…
Ứng dụng của cây quyết định dùng trong phân lớp dự đoán như:
 Dự báo thời tiết (dự báo trời nắng, mưa hay âm u,…) dựa trên một số yếu tố nhiệt
độ, sức gió, độ ẩm,…

xếp các thuộc tính trong cây có ảnh hưởng đến chất lượng kết quả không? Như vậy cần độ đo
giúp lựa chọn các thuộc tính thích hợp cho mỗi bước mà các độ đo này sẽ được giới thiệu ở phần
tiếp theo.
Dựa vào loại nhãn của thuộc tính quyết định C
k
có thể phân thành 2 dạng cây quyết định:
 Cây phân lớp (Classification tree): Nhãn của các C
k
là dữ liệu định danh
o Ví dụ: dự báo kết quả trận đấu “thắng” hay “thua”, kết quả học tập của học sinh là
“giỏi”, “khá” hay “trung bình”.
 Cây hồi quy (Regression tree): Nhãn của các C
k
là dữ liệu định lượng
(giá trị số).
o Ví dụ: ước tính giá một ngôi nhà hoặc khoảng thời gian điều trị bệnh.
Tương ứng với mỗi dạng sẽ có thuật toán phổ biến hiện nay: ID3, C4.5, CART
(Classification And Regression Tree).
 CART: giải quyết được bài toán cần sử dụng cây phân lớp và cây hồi quy
 ID3, C4.5: giải quyết được bài toán sử dụng cây phân lớp
Tùy vào mỗi thuật toán sẽ có các độ đo tương ứng để hỗ trợ việc đánh giá, lựa chọn thuộc
tính cho việc xây dựng cây ở mỗi bước.
2. Các độ đo
Như vậy để trả lời cho câu hỏi làm thế nào chọn được thuộc tính phân tách (splitting
attribute) cho mỗi bước khi thực hiện xây dựng cây quyết định? Các độ đo đã được đưa ra để giải
quyết vấn đề này.
Ak
Am
C1
C3

giá trị của thuộc tính quyết định.
Ví dụ 1: Tập dữ liệu S có 14 phần tử trong đó giá trị của thuộc tính quyết định Play
Tennis? là “Yes”, “No”. Vậy có thể phân thành 2 lớp theo thuộc tính quyết định C
1
: Yes và
C
2
: No. Áp dụng công thức tính được entropy của S như sau:

Entropy(S)=
Công thức tính entropy ở trên là công thức tổng quát đối với trường hợp S có m lớp. Trong
trường hợp S có 2 lớp công thức tính entropy (S) :
 Nếu (p
1
= 0 hay p
2
=0)  entropy = 0: S đồng nhất (mọi phần tử đều thuộc 1 lớp)
 Nếu p
1
= p
2
= 1/2  entropy = 1: số phần tử thuộc C
1
và C
2
bằng nhau
 Nếu p
i
 (0,1)  entropy  (0,1): số phần tử thuộc C
1

hỗn loạn). Do đó kết quả sẽ là chọn Gain (S,A
j
) của thuộc tính Aj nào có giá trị lớn nhất.
Ví dụ 2: Có tập dữ liệu Play Tennis như sau:
Xét thuộc tính Outlook: Outlook có 3 giá trị “Sunny”, “Overcast”, và “Rain”. Do đó
thuộc tính Outlook tạo ra 3 phân hoạch. Lần lượt tính Entropy cho mỗi phân hoạch theo công
thức tính Entropy phần 2.1 ta được:
j
Theo công thức tính Gain (S, Outlook):
phân tách.
Tương tự, lần lượt tính được Gain cho các thuộc tính khác:
Gain (S,Humidity)=0.151, Gain (S,Wind)=0.048, Gain (S,Temp)=0.029
Thuộc tính Outlook có Gain(S,Outlook) cao nhất nên chọn Outlook làm thuộc tính
Ví dụ 3: giả sử cũng tập dữ liệu Play Tennis như Ví dụ 2 nhưng có bổ sung
thêm một thuộc tính When (thời gian chơi Tennis) như sau:
Gain(S,When) = 0.940 – (4/14)*1 – (3/14)*0.918 – (3/14)*0.918 = 0.261
Nhận xét: bây giờ do thuộc tính When có Gain (S,When) cao nhất 0.261 (lớn hơn
Gain(S,Outlook)=0.246 đã tính ở Ví dụ 2), nên sẽ chọn thuộc tính When làm thuộc tính phân
tách thay vì là thuộc tính Outlook. Tuy nhiên, theo quan sát thì do thuộc tính When có nhiều giá
trị (5 giá trị) hơn thuộc tính Outlook (3 giá trị), trong đó có một phân hoạch là When=7pm chỉ có
1 phần tử, nên entropy của mỗi phân hoạch do thuộc tính When tạo ra thấp, từ đó dẫn đến Gain
(S, When) cao.
Như vậy với độ đo Information Gain có xu hướng “thiên vị” cho thuộc tính nhiều
giá trị (cây có nhiều nhánh). Điều này làm ảnh hưởng đến kết quả dự đoán. Do đó cần một độ đo
cải tiến hơn để giải quyết vấn đề này.
2.1.2. Gain Ratio
Độ đo Gain Ratio được đặt ra để giải quyết vấn đề một thuộc tính tạo ra rất nhiều
phân hoạch nhưng có thể mỗi phân hoạch chỉ gồm 1 phần tử. Độ đo này được sử dụng trong
thuật toán C4.5 và đã chuẩn hóa đươc Information Gain nhờ vào Split Information (thông tin
phân tách). [1] Công thức tính Split Information như sau:

làm giảm bớt kích thước tập luật và đơn giản hóa các luật mà độ chính xác so với nhánh tương
ứng cây quyết định là tương đương.
Tư tưởng phát triển cây quyết định của C4.5 là phương pháp HUNT đã nghiên cứu ở trên.
Chiến lược phát triển theo độ sâu (depth-first strategy) được áp dụng cho C4.5.
3.2. Các độ đo sử dụng trong C4.5
Phần lớn các hệ thống học máy đều cố gắng để tạo ra 1 cây càng nhỏ càng tốt, vì những
cây nhỏ hơn thì dễ hiểu hơn và dễ đạt được độ chính xác dự đoán cao hơn.
Do không thể đảm bảo được sự cực tiểu của cây quyết định, C4.5 dựa vào nghiên cứu tối
ưu hóa, và sự lựa chọn cách phân chia mà có độ đo lựa chọn thuộc tính đạt giá trị cực đại.
Hai độ đo được sử dụng trong C4.5 là information gain và gain ratio.
3.2.1. Information Gain
Trong đó: Value(A) là tập các giá trị của thuộc tính A, Sv là tập con của S mà A nhận giá trị v
Ví dụ mô tả cách tính information gain
Xét CSDL sau:
Xét
thuộ
c
tính
Outl
ook(
O)
X
tín
T
(T)

Tƣ
In
0.048
InfoGain(W) = 0.029

GainRatio(S, H) = 0.151/1.56 = 0.097
GainRatio(S, W) = 0.048/1 = 0.048
GainRatio(S, T) = 0.029/0.985 = 0.029
Suy ra: Chọn Outlook vì có Gain Ratio lớn nhất
3.3. Đặc điểm của C4.5
4.3.1. C4.5 có cơ chế riêng trong xử lý những giá trị thiếu
Một cải tiến hơn so với ID3 là C4.5 có cơ chế riêng để xử lý những dữ liệu thiếu:
VD: Gọi So là tập các mẫu có giá trị của thuộc tính Outlook bị thiếu.Khi đó độ đo
information gain của Outlook sẽ giảm vì chúng ta không học được gì từ các mẫu trong So
14
Tương ứng split information cũng thay đổi
Nhờ sự thay đổi này làm giảm giá trị của các
mẫu liên quan tới thuộc tính có tỷ lệ giá trị cao.
Ở ví dụ trên nếu Outlook được chọn, C4.5 không tạo một nhánh riêng trên cây quyết định cho So.
Thay vào đó, thuật toán có cơ chế phân chia các mẫu trong So về các tập con Si là tập con mà
có giá trị thuộc tính outlook xác định theo trong số |Si| / |S – So|.
3.3.2. Tránh “Quá vừa” dữ liệu
“Quá vừa” dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định và những
phương pháp học khác. Quá vừa dữ liệu là hiện tượng: nếu không có các case xung đột (là những
case mà giá trị cho mọi thuộc tính là giống nhau nhưng giá trị của lớp lại khác nhau) thì cây
quyết định sẽ phân lớp chính xác toàn bộ các case trong tập dữ liệu đào tạo. Đôi khi dữ liệu đào
tạo lại chứa những đặc tính cụ thể, nên khi áp dụng cây quyết định đó cho những tập dữ liệu khác
thì độ chính xác không còn cao như trước.
Có một số phương pháp tránh “quá vừa” dữ liệu trong cây quyết định:
+ Dừng phát triển cây sớm hơn bình thường, trước khi đạt tới điểm phân lớp hoàn hảo tập
dữ liệu đào tạo. Với phương pháp này, một thách thức đặt ra là phải ước lượng chính xác thời
điểm dừng phát triển cây.
+ Cho phép cây có thể “quá vừa” dữ liệu, sau đó sẽ cắt, tỉa cây Mặc dù phương pháp thứ
nhất có vẻ trực quan hơn, nhưng với phương pháp thứ hai thì cây quyết định được sinh ra được
thử nghiệm chứng minh là thành công hơn trong thực tế, vì nó cho phép các tương tác tiềm

ợng, đánh giá:
Tập luật được đem ước lượng lại trên toàn bộ tập training, nhằm mục đích xác định xem
liệu có luật nào làm giảm độ chính xác của sự phân lớp. Nếu có, luật đó bị loại bỏ và quá trình
ước lượng được lặp cho đến khi không thể cải tiến thêm.
4.4. Nhận xét về C4.5
• C4.5 có cơ chế sinh cây quyết định hiệu quả và chặt chẽ bằng việc sử dụng độ đo lựa
chọn thuộc tính tốt nhất là gain-ratio.
• Các cơ chế xử lý với giá trị lỗi, thiếu và chống “quá vừa” dữ liệu của C4.5 cùng với
cơ chế cắt tỉa cây.
Thêm vào đó, mô hình phân lớp C4.5 còn có phần chuyển đổi từ cây quyết định sang luật
dạng if-then, làm tăng độ chính xác và tính dễ hiểu của kết quả phân lớp. Đây là tiện ích rất có ý
nghĩa đối với người sử dụng.
4. Các vấn đề trong việc học cây quyết định
4.1. Tránh Overfitting dữ liệu
Trong một số trường hợp giải thuật chỉ mô tả sự phát triển của cây chỉ đủ sâu để phân loại
hoàn toàn những dữ liệu đào tạo. Trong thực tế, ta thường gặp một số khó khăn như dữ liệu bị
nhiễu, lỗi hoặc khi số lượng dữ liệu là quá ít. Trong hai trường hợp nêu trên, giải thuật ID3 có
thể tạo ra trường hợp quá khớp (overfitting).
Nhóm tác giả phát biểu rằng một giả thuyết quá khớp với dữ liệu đào tạo nếu một số những
giả thuyết mà thích hợp với dữ liệu đào tạo nhưng thiếu chính xác trên toàn bộ sự phân bố của
trường hợp. Chương này sẽ giới thiệu các kỹ thuật thường được sử dụng nhất.
Định nghĩa:
Cho một không giả thuyết H , một giả thuyết h thuộc H được gọi là quá khớp trên dữ liệu
đào tạo nếu tồn tại một vài giả thuyết h‟ thuộc H mà h có ít lỗi hơn h‟ trên dữ liệu đào tạo,
nhưng
h‟
có ít lỗi hơn h trên toàn bộ sự phân bố.
Hình ảnh dưới đây minh họa các tác động của thao tác quá khớp trong một ứng dụng điển
hình của việc học một cây quyết định. Trong ví dụ này, thuật toán ID3 được áp dụng trong tin
học y tế.

nhau của việc học nhiễu, lỗi, tình trạng quá khớp có thể làm giảm tính chính xác của cây quyết
định từ 10-25%.
Có một vài cách tiếp cận nhằm tránh trường hợp quá khớp trong việc học cây quyết định.
Ở đây có thể được phân thành hai lớp:
 Phương pháp tiếp cận bằng cách ngừng phát triển cây trước khi nó đạt đến điểm cây
quyết định hoàn toàn phân loại dữ liệu huấn luyện.
 Phương pháp tiếp cận cho phép tiếp tục phát triển cây quyết định – vẫn để tình trạng quá
khớp xảy ra, sau đó tỉa lại cây.
Mặc dù cách tiếp cận của phương pháp đầu tiên có vẻ thực tế hơn, tuy nhiên trong thực tế
phương pháp thứ hai đạt kết quả thành công hơn. Nguyên nhân là do trong phương pháp đầu tiên
khó khăn là phải ước tính một cách chính xác khi nào ngừng phát triển cây; kích thước cuối cùng
của cây là kích thước nào? Sử dụng tiêu chí nào để xác định kích thước cuối cùng này? Phương
pháp tiếp cận bao gồm:
 Sử dụng một bộ dữ liệu kiểm tra riêng biệt, khác biệt so với tập dữ liệu huấn luyện để
đánh giá hiệu quả của việc cắt tỉa nút từ cây.
 Sử dụng tất cả tập dữ liệu có sẵn để đào tạo, nhưng áp dụng một bài thống kê kiểm tra
nhằm ước tính khả năng mở rộng. Ví dụ: phép thử nghiệm chi-square
 Sử dụng một biện pháp rõ ràng để mã hóa các ví dụ huấn luyện và các cây quyết định,
ngăn chặn sự tăng trưởng của cây này nhằm làm giảm kích thước tối thiểu của cây mã
hóa. Cách tiếp cận này, dựa trên nguyên lý mô tả chiều dài tối thiểu (Minimum
18
Description Length principle) được đề cập đến trong Quinlan và Rivest (1989) và Mehta
cùng các cộng sự (1995).
Cách đầu tiên của các phương pháp tiếp cận trên được sử dụng phổ biến nhất. Nhóm tác
giả thảo luận về hai biến thể chính của cách tiếp cận này. Trong phương pháp này, các dữ liệu có
sẵn được chia thành hai bộ: một tập hợp dữ liệu để đào tạo – được sử dụng để hình thành các giả
thuyết học, và một tập hợp dữ liệu riêng biệt để kiểm tra, được sử dụng để đánh giá tính chính
xác của giả thuyết này trên dữ liệu tiếp theo, và để đánh giá tác động của việc cắt tỉa.
Động lực của thao tác trên như sau: Mặc dù người học có thể bị nhầm lẫn bởi những lỗi
ngẫu nhiên và quy luật này trùng hợp ngẫu nhiên trong tập huấn luyện. Vì vậy, tập hợp xác nhận

đề xuất, liên quan đến phân vùng dữ liệu có sẵn nhiều lần khác nhau bằng nhiều cách, sau đó tính
trung bình các kết quả. Đánh giá dựa trên kinh nghiệm của cây thay thế phương pháp cắt tỉa
được báo cáo bởi Mingers (1989b) và Malerba cùng các cộng sự (1995).
4.1.2. Luật POST-PRUNING
Trong thực tiễn, một phương pháp thành công cho việc tìm kiếm những giả thuyết với sự
chính xác cao là một kỹ thuật mà chúng ta sẽ gọi là luật cắt tỉa (post-pruning). Một dạng khác
của phương pháp cắt tỉa được sử dụng trong C4.5 là một dạng phát triển của giải thuật ID3. Luật
toán cắt tỉa (post-pruning) gồm những bước sau đây:
 Xây dựng cây quyết định từ tập dữ liệu huấn luyện - cho phép tình trạng quá khớp xảy ra.
 Chuyển đổi cây đã học thành một tập luật tương đương. Mỗi luật là một đường đi từ nút
gốc đến nút lá của cây quyết định.
 Thu gọn mỗi luật bằng cách loại bỏ bất kỳ điều kiện tiên quyết mà kết quả được cải thiện
độ chính xác.
 Phân loại các quy tắc cắt tỉa và sắp xếp chúng theo độ chính xác ước tính của chúng, và
xem xét chúng trong trình tự khi phân loại các trường hợp tiếp theo.
Để minh họa, xem xét lại cây quyết định sau:
20
Trong khi rút gọn luật, mỗi lá tương ứng với một luật và được tạo ra bằng cách đi từ nút
gốc đến nút lá của cây. Mỗi lần kiểm tra thuộc tính dọc theo đường dẫn từ gốc đến lá sẽ trở thành
một quy tắc tiền đề (điều kiện tiên quyết) và phân loại tại các nút lá trở thành hệ quả
(postcondition).
IF (Outlook = Sunny) A (Humidity = High)
THEN PlayTennis = No
Tiếp theo, mỗi quy tắc như vậy được tỉa bằng cách loại bỏ bất kỳ tiền đề, điều kiện tiên
quyết, mà khi loại bỏ kết quả không tồi tệ hơn ước tính chính xác của nó. Luật cắt tỉa được chọn
tùy theo điều kiện nào của các bước cắt tỉa cải tiến hơn so với các điều kiện khác. Việc cắt tỉa sẽ
không được thực hiện nếu nó làm giảm tính chính xác của quy tắc ước tính. Ví dụ luật cắt tỉa sẽ
xem xét việc loại bỏ tiền đề (Outlook=Sunny) and (Humidity=High) trong luật đã được tạo ra.
Như đã nói ở trên, một trong những phương pháp để ước tính độ chính xác là sử dụng một
xác nhận ví dụ phân chia tập huấn luyện. Một phương pháp khác, được sử dụng trong thuật toán

trong cây quyết định. Điều này có thể đạt tới bằng việc hạn chế tối đa những thuộc tính giá trị rời
rạc mới mà phân chia giá trị liên tục thành tập hợp của những giá trị rời rạc theo các khoảng.
Cụ thể với một giá trị thuộc tính A là giá trị liên tục, giải thuật có thể linh động tạo ra một
thuộc tính logic Ac mang giá trị true nếu A < c và false nếu ngược lại.
Vấn đề còn lại là lựa chọn giá trị tốt nhất cho ngưỡng c như thế nào.
Ví dụ, giả sử ta xét các thuộc tính giá trị liên tục Temperature. Giả sử trong một ví dụ liên
kết huấn luyện với một nút cụ thể trong một cây quyết định có giá trị Temperature và thuộc tính
PlayTennis.
Những ngưỡng ứng cử viên có thể được đánh giá bằng cách tính toán được thông qua các
thông tin có liên quan với nhau. Trong ví dụ trên, có hai ngưỡng ứng cử viên, tương ứng với giá
trị của nhiệt độ mà tại đó giá trị thay đổi PlayTennis là (48 + 60)/2 và (80 + 90)/2. Khi đó, giá trị
Information gain có thể được tính toán lại cho mỗi ứng cử viên thuộc tính, Temperature
>54
và Temperature
>85
. Vì Information gain (Temperature
>54
) > Information gain
(Temperature
>85
) nên giá trị Temperature
>54
được chọn. Giá trị thuộc tính này tự động tạo ra
có thể so sánh được với các thuộc tính ứng cử viên khác có sẵn cho việc phát triển cây quyết
định.
Fayyad và Irani (1993) thảo luận về một phần mở rộng để tiếp cận theo cách này chia tách
các thuộc tính liên tục vào nhiều khoảng hơn là chỉ hai khoảng dựa trên một ngưỡng duy nhất.
Utgoff và Brodley (1991) và Murthy cùng cộng sự (1994) thảo luận về cách tiếp cận xác định
các tính năng bằng cách kết hợp tuyến tính một số thuộc tính có giá trị liên tục.
4.2.1. Các

kiểm tra trong phòng thí nghiệm, nó có thể là kiểm tra thử máu trên một tập những bệnh nhân
cho phép. Trong trường hợp như vậy chúng ta thông thường phải ước đoán những giá trị thiếu
dựa trên những trường hợp mà thuộc tính này có một giá trị đã biết.
Xét một trường hợp mà trong đó Gain(S,A) được tính toán tại nút n trong cây quyết định
để xác định khi nào thuộc tính A là thuộc tính tốt nhất để kiểm tra nút quyết định này. Giả sử
rằng (x,c(x)) là một trong những tập dữ liệu đào tạo trong S và giá trị A(x) là không được biết
đến. Một trong những chiến thuật liên quan đến thao tác thiếu giá trị thuộc tính là gán cho nó giá
trị chiếm hầu hết trong tập dữ liệu huấn luyện tại nút n. Một thủ tục thứ hai phức tạp hơn là gán
một kết quả có thể xảy ra cho mỗi một giá trị của A hơn là đơn giản gán một giá trị chung cho
A(x). Khả năng có thể nhận được bằng cách quan sát tần số của những giá trị khác nhau cho A
trong số những ví dụ tại nút n.
Ví dụ: Giả sử thuộc tính A là một ứng cử cho thuộc tính kiểm tra ở nút n. Ta sẽ phải xử lý
như thế nào với ví dụ x không có (thiếu) giá trị đối với thuộc tính A (tức là: x
A
là không
xác định)?
 Gọi S
n
là tập các ví dụ học gắn với nút n có giá trị đối với thuộc tính A
 Giải pháp 1: x
A
là giá trị phổ biến nhất đối với thuộc tính A trong số các ví dụ thuộc tập
S
n
 Giải pháp 2: x
A
là giá trị phổ biến nhất đối với thuộc tính A trong số các ví dụ thuộc tập
S
n
có cùng phân lớp với x

Khi đó, cần sử dụng những cách đánh giá khác InformationGain nhằm xác định các thuộc
tính kiểm tra
(w
*0,1+
là hằng số xác định
mức độ quan trọng giữa chi phía
và Information Gain)
Gai
n
(S
,
A)
Cost(

A)
Ga

in(
S

,

A)
(Cost(

A)1)
24
2
w


log
5
14
2
14 14
2
14 14
2
14
= 1.577
GainRatio(S,When)= Gain(S,When)/SplitInfo(S,When)=0.261/2.217= 0.118
GainRatio(S,Outlook)= Gain(S,Outlook)/SplitInfo(S,Outlook)=0.246/1.577= 0.156
Ta thấy thuộc tính Outlook có Gain Ratio lớn hơn do đó chọn Outlook làm thuộc
tính phân tách
Gain Ratio cũng gặp một số vấn đề do có phần mẫu số SplitInfo:
 SplitInfo có thể bằng 0 hay rất thấp (khi |S
A
|  |S|). Khi đó Gain Ratio sẽ không xác
định được hoặc rất lớn.
Cách giải quyết:
 Tính Gain cho từng thuộc tính và lấy giá trị Gain trung bình (Gain_Average)
 Sau đó chỉ áp dụng Gain Ratio trên những thuộc tính có Gain > Gain_Average
5.2.2. Gini Index
Độ đo Gini Index được sử dụng trong thuật toán CART (Classification And Regression
Tree). Thuật toán CART được sử dụng trong bài toán xây dựng cây phân lớp và cây hồi quy.[2]
Độ đo Gini có đặc điểm là khi xây dựng cây sẽ tạo ra sự phân tách nhị phân cho mỗi thuộc
tính A
j
(phân hoạch thuộc A
j