-1-
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH: MÁY HỌC VÀ ỨNG DỤNG
NỘI DUNG:
TÌM HIỂU VỀ GIẢI THUẬT
QUY NẠP CÂY QUYẾT ĐỊNH ID3
Ging viên phụ trách: PGS.TS. VŨ THANH NGUYÊN
Học viên thực hiện: Lê Phước Vinh
Mã học viên: CH1301116
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-2-
TP. HỒ CHÍ MINH, THÁNG 3/2014
LỜI MỞ ĐẦU
Lời đầu tiên em xin chân thành cm ơn Thầy PGS. TS. Vũ Thanh Nguyên
đã ging dạy tận tình và cung cấp cho em nhiều kiến thức rất hữu ích về môn
học Máy học và ứng dụng. Từ kiến thức sâu rộng của mình, bằng phương pháp
ging dạy tích cực Thầy đã truyền đạt cho em nhiều kiến thức vô cùng quý báu.
Mặc dù rất cố gắng, song bài viết chắc không tránh khỏi những hạn chế,
thiếu sót. Em rất mong được Thầy thông cm, góp ý, chỉnh sửa cho bài viết hoàn
chỉnh hơn.
Em xin chân thành cm ơn!
Học viên thực hiện

Lê Phước Vinh
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-3-
TỔNG QUAN VỀ BÀI THU HOẠCH

Khi được hỏi về những kỹ năng thông minh nào là cơ bn nhất đồng thời
khó tự động hóa nhất của con người ngoài các hoạt động sáng tạo nghệ thuật,

-4-
NỘI DUNG
I. TÌM HIỂU GIẢI THUẬT QUY NẠP CÂY QUYẾT ĐỊNH ID3
1. Giới thiệu
Gii thuật quy nạp cây quyết định 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 là một gii thuật
hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc qun
lý tính phức tạp, heuristic của nó dùng cho việc chọn lựa các khái niệm ứng
viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu.
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ìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-5-
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

Occam’s razor và một số lập luận khác đều cho rằng ‘gi thuyết có kh
năng nhất là gi thuyết đơn gin nhất thống nhất với tất c các quan sát’, ta nên
luôn luôn chấp nhận những câu tr lời đơn gin nhất đáp ứng một cách đúng đắn
dữ liệu của chúng ta. Trong trường hợp này là các gii thuật học cố gắng tạo ra
cây quyết định nhỏ nhất phân loại một cách đúng đắn tất c các ví dụ đã cho.
Trong phần kế tiếp, chúng ta sẽ đi vào gii thuật ID3, là một gii thuật quy nạp
cây quyết định đơn gin thỏa mãn các vấn đề vừa nêu.
2. 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 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 quyết định đơ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. Để đơn gin, phần này chỉ mô t gii thuật dùng để
xây dựng cây quyết định, với việc gi định một hàm chọn trắc nghiệm thích hợp.
Ví dụ, hãy xem xét cách xây dựng cây quyết định của ID3 trong hình sau
từ tập ví dụ rèn luyện trong bng 9.1.
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-7-
Bắt đầu với bng đầy đủ gồm 14 ví dụ rèn luyện, ID3 chọn thuộc tính
quang cnh để làm thuộc tính gốc sử dụng hàm chọn lựa thuộc tính mô t trong
phần kế tiếp. Trắc nghiệm này phân chia tập ví dụ như cho thấy trong hình 9.2
với phần tử của mỗi phân vùng được liệt kê bởi số thứ tự của chúng trong bng.
* 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)

dụ trong các phân vùng con của các nhánh cây này đều thuộc cùng một lớp, nên
gii thuật ID3 kết thúc và ta có được cây quyết định như hình 9.3.
Lưu ý, để phân loại một ví dụ, có khi cây quyết định không cần sử dụng
tất c các thuộc tính đã cho, mặc dù nó vẫn phân loại đúng tất c các ví dụ.
* 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:
1. 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 như phân vùng “Quang cnh = Nắng” của ví dụ trên => gii thuật phi
tiếp tục tách một lần nữa.
2. 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 như phân vùng “Quang cnh = Âm u” của ví dụ trên => gii thuật
tr về nút lá với nhãn là lớp đó.
3. Không còn ví dụ nào => gii thuật tr về mặc nhiên
4. 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 quyết định đơ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
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-9-
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 quyết định,
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.
3. Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất?
Quinlan (1983) là người đầu tiên đề xuất việc sử dụng lý thuyết thông tin
để tạo ra các cây quyết định và công trình của ông là cơ sở cho phần trình bày ở

Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-10-
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 (+).
Hình 9.4 minh họa sự phụ thuộc của giá trị entropy vào xác suất xuất hiện
của ví dụ 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:
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à:
b. 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.
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-11-
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.
4. Tìm kiếm không gian giả thuyết trong ID3:

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. Đây là tính chất thiên lệch quy
nạp của ID3.
5. Đá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.
6. Chuyển cây về các luật:
Thông thường, cây quyết định sẽ được chuyển về dạng các luật để thuận
tiện cho việc cài đặt và sử dụng. Ví dụ cây quyết định cho tập dữ liệu rèn luyện
trong bng 9.1 có thể được chuyển thành một số luật như sau:
If (Quang-cnh =nắng) (Độ ẩm = Cao) Then Chơi-Tennis = No ∧
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-13-
If (Quang-cnh =nắng) (Độ ẩm = TB) Then Chơi-Tennis = Yes ∧
If (Quang-cnh =Âm u) Then Chơi-Tennis = Yes
…
7. 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

o Phần 4: Các nút lệnh của chương trình.
Có 4 nút lệnh với các chức năng như sau:
 Nạp dữ liệu vào: Nạp dữ liệu vào chương trình.
 Chạy giải thuật: Chạy gii thuật ID3.
 Khởi động lại chương trình: Khởi động, chạy lại chương trình.
 Thông tin: Thông tin về chương trình.
2. Hướng dẫn sử dụng demo:
Yêu cầu:
Hệ thống có cài .Net Framework 4.0
Các bước chạy chương trình:
- Đầu tiên, nạp dữ liệu vào chương trình bằng nút Nạp dữ liệu vào
Dữ liệu được đưa lên bng Dữ liệu vào (hình minh họa).
- Sau đó, nhấn nút Chạy giải thuật để chạy.
Các bước gii sẽ được hiện ra ở phần 2 (Chi tiết các bước của gii thuật).
Cây được vẽ ra ở phần 3 (Cây minh họa gii thuật).
Giao diện chương trình:
3. Một số module chính trong chương trình demo
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-15-
Chương trình demo sử dụng ngôn ngữ C#. NET 2010
 Chương trình gồm những hàm chính sau:
Hàm tính Entropy:
• Công thức:
Entropy (S) = - p
+
log
2
p
+
- p

double result;
int CountPositives = 0;
int[] CountPositivesA = new int[A.Value.Count];
int[] CountNegativeA = new int[A.Value.Count];
int Col = Attributes.IndexOf(A);
for (int i = 0; i < A.Value.Count; i++)
{
CountPositivesA[i] = 0;
CountNegativeA[i] = 0;
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-16-
}
for (int i = 0; i < Examples.Count; i++)
{
int j = A.Value.IndexOf(Examples[i][Col].ToString());
if (Examples[i][Examples[0].Count - 1]=="yes")
{
CountPositives++;
CountPositivesA[j]++;
}
else
{
CountNegativeA[j]++;
}
}
result = GetEntropy(CountPositives, Examples.Count - CountPositives);
for (int i = 0; i < A.Value.Count; i++)
{
double RateValue = (double)(CountPositivesA[i] +
CountNegativeA[i]) / Examples.Count;

Hàm thực hiện giải thuật ID3:
• Gii thuật:
ID3_algorithm(Training_Set, Class_Labels, Attributes)
Tạo nút Root của cây quyết định
If tất c các ví dụ của Training_Set thuộc cùng lớp c
Return Cây quyết định có nút Root được gắn với (có nhãn) lớp c
If Tập thuộc tính Attributes là rỗng
Return Cây quyết định có nút Root được gắn với nhãn lớp ≡
Majority_Class_Label(Training Set)
A ← Thuộc tính trong tập Attributes có kh năng phân loại “tốt
nhất” đối với Training_Set
Thuộc tính kiểm tra cho nút Root ← A
For each Giá trị có thể v của thuộc tính A
Bổ sung một nhánh cây mới dưới nút Root, tương ứng với trường
hợp: “Giá trị của A là v”
Xác định Training_Set
v
= {ví dụ x | x ⊆ Training_Set, x
A
=v}
If (Training_Set
v
là rỗng) Then
Tạo một nút lá với nhãn lớp ≡ Majority_Class_Label(Training_Set)
Gắn nút lá này vào nhánh cây mới vừa tạo
Else Gắn vào nhánh cây mới vừa tạo một cây con sinh ra bởi
ID3_algorithm(Training_Set
v
, Class_Labels, {Attributes \ A})
Return Root

}
if (Examplesvi.Count==0)
{
return new TreeNode(new
Attribute(GetMostCommonValue(Examplesvi)));
}
else
{
Attribute.Remove(BestAttribute);
Root.AddNode(ID3(Examplesvi, Attribute,BestAttribute.Value[i]));
}
}
return Root;
}
TÀI LIỆU THAM KHẢO
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-19-
[1] PGS. TS. Vũ Thanh Nguyên. (2013). Bài dạy trong các buổi học.
[2] Geogre F. Luger – Artificial Intelligence, Structures and Strategies for
Complex Problem Solving– Addison – Wesley Publishing Company, Inc – 2002
(trang 349 – 381, 417 – 438, 469 – 480)
[3] Tom M. Mitchell – Machine Learning – McGraw Hill, Inc (trang 52 – 65)
[4] Wikipedia – Bách khoa toàn thư mở - Học máy:
http://en.wikipedia.org/wiki/Machine_learning
[5] Ender ÖZCAN, Murat ERENTÜRK – A Brief Review Of Memetic
Algorithms For Solving TSP:
http://physics.yeditepe.edu.tr/merenturk/tainn04.ppt
Tìm hiểu về giải thuật quy nạp cây quyết định ID3_Lê Phước Vinh_CH1301116
-20-
MỤC LỤC