1
TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN 1
CÂY QUYẾT ĐỊNH VÀ
ĐỘ ĐO

Người hướng dẫn: TS VÕ ĐÌNH BẢY
Người thực hiện: NGUYỄN KHÁNH PHƯƠNG
VÕ THỊ PHI PHỤNG
Lớp : 11050302
Khoá : 15
THÀNH PHỐ HỒ CHÍ MINH, NĂM 2014
TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN 1
CÂY QUYẾT ĐỊNH VÀ
ĐỘ ĐO

Người hướng dẫn: TS VÕ ĐÌNH BẢY
Người thực hiện: NGUYỄN KHÁNH PHƯƠNG
VÕ THỊ PHI PHỤNG
Lớp : 11050302
Khoá : 15
THÀNH PHỐ HỒ CHÍ MINH, NĂM 2014
3
LỜI CẢM ƠN
Trước tiên chúng em xin được gửi lời cảm ơn chân thành tới các thầy cô giáo
trong khoa Công nghệ thông tin - Trường đại học Tôn Đức Thắng đã tận tình giúp

đỡ và giảng dạy cho chúng em trong học kì này.
Đặc biệt, chúng em xin gửi lời cảm ơn chân thành nhất tới thầy T.s Võ Đình
Bảy đã tận tình hướng dẫn, giúp đỡ chúng em hoàn thành đề tài nghiên cứu khoa
học này.
Trong thời gian vừa qua mặc dù chúng em đã cố gắng rất nhiều để hoàn
thành tốt đề tài nghiên cứu khoa học của mình. Song chắc chắn kết quả nghiên cứu
sẽ không tránh khỏi những thiếu sót, vì vậy kính mong nhận được sự chỉ bảo và góp
ý của quý thầy cô.
Chúng em xin chân thành cám ơn!
Ký tên
Phương Phụng
Nguyễn Khánh Phương Võ Thị Phi Phụng
4
ĐỒ ÁN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của riêng tôi chúng tôi và được sự
hướng dẫn của TS Võ Đình Bảy. Các nội dung nghiên cứu, kết quả trong đề tài này
là trung thực và chưa công bố dưới bất kỳ hình thức nào trước đây. Những số liệu
trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác
giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong đồ án còn sử dụng một số nhận xét, đánh giá cũng như số
liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn
gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách
nhiệm về nội dung đồ án của mình. Trường đại học Tôn Đức Thắng không liên
quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực
hiện (nếu có).
TP. Hồ Chí Minh, ngày 29 tháng 05 năm 2014
Tác giả
(ký tên và ghi rõ họ tên)

Nguyễn Khánh Phương
5
Võ Thị Phi PhụngPHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
Phần xác nhận của GV hướng dẫn
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
_____________________
Tp. Hồ Chí Minh, ngày tháng 05 năm 2014
(kí và ghi họ tên)
Phần đánh giá của GV chấm bài
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
_____________________
Tp. Hồ Chí Minh, ngày tháng 05 năm 2014
(kí và ghi họ tên)
6
TÓM TẮT
Trong quá trình hoạt động, con người tạo ra nhiều dữ liệu nghiệp vụ. Các tập
dữ liệu được tích lũy có kích thước càng lớn, và có thể chưa nhiều thông tin ẩn dạng
những quy luật chưa được khám phá. Chính vì vậy một nhu cầu đặt ra là cần tìm

cách trích rút từ tập dữ liệu đó các luật về phân lớp dữ liệu hay dự đoán những xu
hướng dữ liệu tương lai. Những quy tắc nghiệp vụ thông minh được tạo ra sẽ phục
vụ đắc lực cho các hoạt động thực tiễn, cũng như phục vụ đắc lực cho quá trình
nghiên cứu khoa học. Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng
mong muốn đó.
Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trước những
khao khát tri thức của con người. Trong những năm qua, phân lớp dữ liệu đã thu hút
sự quan tâm của các nhà nghiên cứu trong nhiều lĩnh vưc khác nhau. Công nghệ này
cũng ứng dụng trong nhiều lĩnh vực thực tế như: thương mại, nhà băng, maketing…
Nhiều kỹ thuật phân lớp đã được đề xuất như: Phân lớp cây quyết định
(Decision tree classification), phân lớp Bayesian (Bayesian classifier), phân tích
thống kê…Trong các kỹ thuật đó, cây quyết định được coi là công cụ mạnh, phổ
biến và đặc biệt. Do vậy cần xây dựng những thuật toán có độ chính xác cao, thực
thi nhanh đi kèm với khả năng mở rộng được để có thao tác với những tập dữ liệu
ngày càng lớn.
Đồ án này tập trung vào nguyên cứu vào cây quyết định và độ đo. Trước tiên
ta sẽ nói đến phân lớp dữ liệu rồi đi chuyên sâu vào khái niệm cây quyết định, ưu
nhược điểm của nó. Từ đó tập trung vào phân tích, đánh giá, so sánh các độ đo áp
dụng vào. Mỗi độ đo sẽ đi kèm với các thuật toán khác nhau và như vậy thì cách
biểu hiện cây quyết định của mỗi bài toán cũng sẽ khác đi. Ở đây chúng em tập
trung nguyên cứu bốn độ đo chính là Information Gain, Gain Ratio, độ đo V và
Gini.
Bài báo cáo này gồm các mục sau:
Chương I : KIẾN THỨC CHUNG
Chương II : TÌM HIỂU CÂY QUYẾT ĐỊNH VÀ ĐỘ ĐO
7
Chương III : PHÂN TÍCH THUẬT TOÁN
Chương IV : THỰC NGHIỆM
Chương V : TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN
8

MENU
9
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT
CÁC KÝ HIỆU
p+ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "yes"
p- tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no"
CÁC CHỮ VIẾT TẮT
MDL Minimum Description Length
10
DANH MỤC CÁC BẢNG BIỂU, HÌNH VẼ, ĐỒ THỊ
DANH MỤC HÌNH
Hình 2.1: Cây quyết định biểu diễn Độ Tuổi và Loại Xe thể hiện nguy cơ gây tai
nạn
Hình 3.1 : Mô hình các thuộc tính khi được chọn
Hình 3.2: Cây quyết định với thuật toán CLS
Hình 3.3: Cây quyết định với thuật toán ID3
Hình 3.4: Cây quyết định với thuật toán C4. 5
Hình 4.1: Giao diện của chương trình
Hình 4.2: Giao diện của chương trình khi bấm nút load
Hình 4.3: Giao diện khi load file .txt thành công
Hình 4.4: Giao diện khi chạy thuật toán ID3
Hình 4.5: Giao diện khi chạy thuật toán C4.5
Hình 4.6: Giao diện vẽ cây
Hình 4.7: Giao diện khi bấm nút reset
Hình 4.8: Giao diện khi bấm nút about
DANH MỤC BẢNG
Bảng 3.1: Dữ liệu huấn luyện trong tài liệu tham khảo [1]
11
CHƯƠNG 1 KIẾN THỨC CHUNG
1.1. Phân lớp dữ liệu

Là kĩ thuật dựa trên tập huấn luyện và những giá trị hay hay là nhãn của lớp
trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Phân
lớp cũng là tiên đoán loại lớp của nhãn. Bên cạnh kĩ thuật phân lớp có một hình
thức tương tự là kĩ thuật tiên đoán, kĩ thuật tiên đoán khác với phân lớp ở chỗ phân
lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô hình
những hàm đánh giá liên tục.
 Kĩ thuật phân lớp được tiến hành bao gồm 2 bước: Xây dựng mô hình và
sử dụng mô hình.
+ Xây dựng mô hình: là mô tả một tập những lớp được định nghĩa
trước trong đó: mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước
như là được xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ được sử dụng
trong việc sử dụng mô hình được gọi là tập huấn luyện. Mô hình được biểu diễn là
những luật phân lớp, cây quyết định và những công thức toán học.
+ Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích
phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến.
Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xác của mô
hình trong đó: nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp
của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại
đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện.
Phân lớp là một hình thức học được giám sát tức là: tập dữ liệu huấn luyện
(quan sát, thẩm định. . . ) đi đôi với những nhãn chỉ định lớp quan sát, những dữ
liệu mới được phân lớp dựa trên tập huấn luyện.
Ngược lại với hình thức học được giám sát là hình thức học không được
giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không được biết đến.
12
1.2 Các vấn đề liên quan đến phân lớp dữ liệu
1.2.1 Chuẩn bị dữ liệu cho việc phân lớp
Việc tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể
thiếu và có vai trò quan trọng quyết định tới sự áp dụng được hay không của mô
hình phân lớp. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu

quả và khả năng mở rộng được của mô hình phân lớp.
 Quá trình tiền xử lý dữ liệu gồm có các công việc sau:
+ Làm sạch dữ liệu:
Làm sạch dữ liệu liên quan đến việc xử lý với lỗi (noise) và giá trị thiếu
(missing value) trong tập dữ liệu ban đầu. Noise là các lỗi ngẫu nhiên hay các giá trị
không hợp lệ của các biến trong tập dữ liệu. Để xử lý với loại lỗi này có thể dùng kỹ
thuật làm trơn. Missing value là những ô không có giá trị của các thuộc tính. Giá trị
thiếu có thể do lỗi chủ quan trong quá trình nhập liệu, hoặc trong trường hợp cụ thể
giá trị của thuộc tính đó không có, hay không quan trọng. Kỹ thuật xử lý ở đây có
thể bằng cách thay giá trị thiếu đó bằng giá trị phổ biến nhất của thuộc tính đó hoặc
bằng giá trị có thể xảy ra nhất dựa trên thống kê. Mặc dù phần lớn thuật toán phân
lớp đều có cơ chế xử lý với những giá trị thiếu và lỗi trong tập dữ liệu, nhưng bước
tiền xử lý này có thể làm giảm sự hỗn độn rong quá trình xây dựng mô hình phân
lớp.
+ Phân tích liên quan(chọn đặc trưng)
Có rất nhiều thuộc tính trong tập dữ liệu có thể hoàn toàn không cần thiết
hay liên quan đến một bài toán phân lớp cụ thể. Ví dụ dữ liệu về ngày trong tuần
hoàn toàn không cần thiết đối với ứng dụng phân tích độ rủi ro của các khoảng tiền
cho vay của ngân hàng nên thuộc tính này là dư thừa. Phân tích sự cần thiết của dữ
liệu nhằm mục đích loại bỏ những thuộc tính không cần thiết, dư thừa khỏi quá
trình phân lớp vì thuộc tính đó sẽ làm chậm, phức tạp và gây ra sự hiểu sai trong
quá trình phân lớp dẫn tới mô hình phân lớp không đúng.
13
+ Biến đổi dữ liệu:
Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết
trong quá trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục.
Ví dụ: các giá trị số của thuộc tính thu nhập của khách hàng có thể được khái quat
hóa thành các dãy giá trị rời rạc: thấp, trung bình, cao. Tương tự với những thuộc
tính rời rạc như địa chỉ phố có thể được khái quát hóa lên thành thành phố. Việc
khái quát hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy các thao tác vào/ra liên

quan đến quá trình phân lớp sẽ giảm.
1.2.2 So sánh các mô hình phân lớp
Trong từng ứng dụng cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc
lựa chọn đó căn cứ vào sự so sánh các mô hình phân lớp khác nhau, dựa trên các
tiêu chuẩn sau:
o Độ chính xác dự đoán (predictive accuracy): Độ chính xác là khả năng
của mô hình để dự đoán chính xác nhãn lớp của dữ liệu mới hay dữ liệu
chưa biết.
o Tốc độ (Speed): Tốc độ là chi phí tính toán liên quan đến quá trình tạo ra
và sử dụng mô hình.
o Sức mạnh (Robustness): Sức mạnh là khả năng mô hình tạo ra những dự
đoán đúng từ những dữ liệu noise hay dữ liệu với những giá trị thiếu.
o Khả năng mở rộng (Scalability): là khả năng thực thi hiệu quả trên
lượng lớn dữ liệu của mô hình đã học.
o Tính hiểu được (Interpretability): Tính hiểu được là mức độ hiểu và hiểu
rõ những kết quả sinh ra bởi mô hình đã học.
14
o Tính đơn giản (Simplicity): Tính đơn giản liên quan đến kích thước của
cây quyết định hay độ cô đọng của các luật.
CHƯƠNG 2 TÌM HIỂU CÂY QUYẾT ĐỊNH VÀ ĐỘ ĐO
2.1 TÌM HIỂU CÂY QUYẾT ĐỊNH
2.1.1 Khái niệm
Trong lĩnh vực máy học, cây quyết định là một kiểu mô hình dự báo
(predictive model), nghĩa là ánh xạ từ các quan sát từ một sự vật/hiện tượng đến
các kết luận về giá trị mục tiêu của sự vật /hiện tượng đó. Intenal node (node trong)
tương ứng với một biến, đường nối giữa Internal node với node lá của nó thể hiện
giá trị cụ thể của biến đó. Mỗi node lá đại diện cho giá trị được dự đoán của
Internal node.
Cây quyết định là một đồ thị phát triển có cấu trúc dạng cây được mô tả
trong hình 1:

Age ≤ 27.5
Age
Age > 27.5
Car type
Risk = High
Car type {family,truck}
Car type {sport}
Risk = LowRisk = High
15
Hình 2.1: Cây quyết định biểu diễn Độ Tuổi và Loại Xe thể hiện nguy cơ gây tai
nạn
Trong đó:
* Root: là node trên cùng của cây
* Internal node: biểu diễn một kiểm tra trên một thuộc tính đơn ( )
* Nhánh: biểu diễn kết quả của kiễm tra tại Internal node ( )
* Node lá : biểu diễn sự phân phối lớp ( )
Cây quyết định có 2 loại:
• Cây hồi quy (Regression tree): ước lượng các hàm có giá trị là số thực
thay vì được sử dụng cho các nhiệm vụ phân loại (ví dụ: ước tính giá
một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện)
• Cây phân loại (Classification tree): nếu y là một biến phân loại như
kết quả một trận đấu (thắng hay thua).
Để phân lớp dữ liệu, giá trị các thuộc tính của mẫu được kiểm tra trên cây
quyết định. Mỗi mẫu tương ứng có một đường đi từ Root đế node lá và node lá biểu
diễn giá trị dự đoán phân lớp đó.
2.1.2 Ưu nhược điểm của Cây Quyết Định
2.1.2.1 Ưu điểm:
− Sinh ra các quy luật dễ hiểu: Chuyển đổi được sang tiếng anh hoặc
SQL.
− Thực thi trong lĩnh vực hướng theo quy luật.

− Dễ dàng tính toán trong khi phân lớp.
− Xử lý thuộc tính liên tục va rời rạc.
− Thể hiện rõ ràng những thuôc tính tốt nhất: phân chia dữ liệu từ gốc
2.1.2.2 Nhược điểm:
− Dễ xảy ra lỗi khi có quá nhiều lớp: vì chỉ thao tác với các lớp có giá
trị dạng nhị phân.
16
− Chi phí tính toán quá đắt để huấn luyện: do phải đi qua nhiều node để
đến node lá cuối cùng.
2.1.3 Quá trình xây dựng cây
Quá trình xây dựng cây quyết định được chia làm 3 giai đoạn cơ bản:
 Xây dựng cây:
• Đi từ Root đến các nhánh, phát triển quy nạp theo hình thức
chia để trị
• Chọn thuộc tính tốt nhất bằng một độ đo đã định trước.
• Phát triển cây bằng việc thêm nhánh tương ứng với từng giá trị
của thuộc tính đã chọn.
• Sắp xếp phân chia tập dữ liệu huấn luyện tới node con.
• Nếu các ví dụ được phân lớp rõ ràng thì dừng.
• Ngược lại: lặp lại cho từng node con từ bước 1 đến bước 4.
 Cắt tỉa cây: nhằm đơn giản hóa, khái quát hóa cây quyết định để tăng
độ chính xác.
 Đánh giá cây: dùng để đánh giá độ chính xác của cây kết quả. Tiêu
chí đánh giá là tổng số mẫu được phân lớp chính xác trên tổng số mẫu
được đưa vào.
2.1.4 Cắt tỉa cây quyết định
Qua tìm hiểu các thuật toán xây dựng cây quyết định ở trên, ta thấy việc
xây dựng cây bằng cách phát triển nhánh cây đầy đủ theo chiều sâu để phân lớp
hoàn toàn các mẫu huấn luyện; như thuật toán CLS và thuật toán ID3 đôi khi
gặp khó khăn trong các trường hợp dữ liệu bị nhiễu (Noisy Data) hoặc dữ liệu

bị thiếu (Missing Data) không đủ để đại diện cho một quy luật; tức là tạo ra các nút
có số mẫu rất nhỏ. Trong trường hợp này, nếu thuật toán vẫn cứ phát triển cây
thì ta sẽ dẫn đến một tình huống mà ta gọi là tình trạng "Over fitting" trong
cây quyết định.
Vẫn đề Over fitting là một khó khăn trong việc nghiên cứu và ứng
dụng cây quyết định. Để giải quyết tình trạng này người ta sử dụng phương pháp
cắt tỉa cây quyết định. Có hai phương pháp cắt tỉa cây quyết định.
17
2.1.4.1 Tiền cắt tỉa (Prepruning)
Chiến thuật tiến cắt tỉa nghĩa là sẽ dừng sớm việc phát triển cây trước khi nó
vươn đến điểm mà việc phân lớp các mẫu huấn luyện được hoàn thành. Nghĩa
là trong quá trình xây dựng cây, một nút có thể sẽ không được tách thêm
bước nữa nếu như kết quả của phép tách đó rơi vào một ngưỡng gần như chắc
chắn. Nút đó trở thành nút lá và được gán nhãn là nhãn của lớp phổ biến
nhất của tập các mẫu tại nút đó.
2.1.4.2 Hậu cắt tỉa (Postpruning)
Chiến thuật này ngược với chiến thuật tiền cắt tỉa. Nó cho phép phát
triển cây đầy đủ sau đó mới cắt tỉa. Nghĩa là xây dựng cây sau đó mới thực hiện cắt
bỏ các nhánh không hợp lý. Trong quá trình xây dựng cây theo chiến thuật hậu
cắt tỉa thì cho phép tình trạng Over fitting xảy ra. Nếu một nút mà các cây con của
nó bị cắt thì nó sẽ trở thành nút lá và nhãn của lá được gán là nhãn của
lớp phổ biến nhất của các con trước đó của nó.
Trong thực tế, phương pháp hậu cắt tỉa là một phương pháp khá thành
công cho việc tìm ra các giả thuyết chính xác cao. Chiến thuật hậu cắt tỉa
được tiến hành thông qua việc tính toán lỗi như sau:
Giả sử ta gọi: E(S) là lỗi tĩnh (Static error hay expected error) của một nút S;
BackUpError(S) là lỗi từ các nút con của S (Back Up Error); Error(S) là lỗi của
nút S. Các giá trị này được tính như sau:
Error(S) = Min(E(S), BackUpError(S))
E(S) = (N - n + 1) / (N + 2)

Trong đó: N là tổng số mẫu ở nút S
n là số mẫu của lớp phổ biến nhất trong S.
18
Trong trường hợp tổng quát, nếu thuộc tính lớp có K giá trị (K lớp) thì:
E(S) = (N-n+K-1) / (N+K)
BackUpError(S) =
I
Error(S
i
)
Trong đó: S
i
là nút con của S
P
i
là tỉ lệ số mẫu trong S
i
trên số mẫu S
Như vậy các nút lá sẽ có lỗi trong Error(S
i
) = E(S
i
) do nút lá không có nút
con dẫn đến không có lỗi BackUpError. Nếu BackUpError(S) E(S) thì chiến thuật
hậu cắt tỉa cây quyết định sẽ cắt tại nút S (tức là cắt bỏ các cây con của S).
Tóm lại, việc cắt tỉa cây nhằm: tối ưu hoá cây kết quả. Tối ưu về kích
cỡ cây và về độ chính xác của việc phân lớp bằng cách cắt bỏ các nhánh
không phù hợp (over fitted branches). Để thực hiện việc cắt tỉa cây thì có các
kỹ thuật cơ bản sau đây:
- Sử dụng tập hợp tách rời của mẫu học để đánh giá tính hữu dụng của việc

hậu cắt tỉa những nút trong cây. Sử dụng kỹ thuật cắt tỉa cây này có thuật toán
CART, gọi tắt là chi phí phức tạp (Cost - Complexity prunning).
- Áp dụng phương pháp thống kê để đánh giá và cắt bỏ các nhánh có độ
tin cậy kém hoặc mở rộng tiếp các nhánh có độ chính xác cao. Kỹ thuật cắt tỉa này
được gọi là cắt tỉa bi quan và thường được sử dụng để cắt tỉa các cây được xây dựng
theo thuật toán ID3 và C4. 5.
- Kỹ thuật mô tả độ dài tối thiểu - MDL (Minimum Description Length)
(với kỹ thuật này không cần kiểm tra các mẫu). Kỹ thuật này không cần thiết phải
kiểm tra các mẫu và nó thường được sử dụng trong các thuật toán SLIQ,
SPRINT.
19
2.2 TÌM HIỂU ĐỘ ĐO
 Entropy:
Phép tính dùng hỗ trợ các độ đo trong trường hợp các mẫu dữ liệu có hai
thuộc tính phân lớp "yes" (+), "no" (-).
Ký hiệu p+ là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là
"yes", và kí hiệu p- là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no"
trong tập S.
Trong trường hợp tổng quát:
Trong đó: P
i
là tỷ lệ các mẫu thuộc lớp I trên tập hợp S các mẫu kiểm tra.
Các trường hợp đặc biệt:
- Nếu tất cả các mẫu thành viên trong tập S đều thuộc cùng một lớp thì
Entropy(S) = 0
- Nếu trong tập S có số mẫu phân bố đều nhau vào các lớp thì
Entropy(S) =1
- Các trường hợp còn lại 0 < Entropy(S) <1
2.2.1 Informaion Gain (Gain)
Gain là đại lượng dùng để đo tính hiệu quả của một thuộc tính trong việc

phân lớp. Đại lượng này được tính thông qua hai giá trị Information và Entropy.
Cho tập dữ liệu S gồm có n thuộc tính Ai(i=1, 2…n) giá trị Information của
thuộc tính Ai ký hiệu là Information(Ai) được xác định bởi công thức.

Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S, A) và được tính theo
công thức sau:
20


Trong đó:
- S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tương ứng là
các giá trị của thuộc tính A.
- Sv bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.
- |Sv| là số phần tử của tập Sv.
- |S| là số phần tử của tập S.
2.2.2 Gain Ratio
Khái niệm độ lợi thông tin Gain có xu hướng ưu tiên các thuộc tính có số
lượng lớn các giá trị. Nếu thuộc tính D có giá trị riêng biệt cho mỗi bảng ghi (thuộc
tính Day ở bảng dữ liệu trên), thì Entropy(S, D) = 0, như vậy Gain(S, D) sẽ đạt giá
trị cực đại. Như vậy, trong một phân vùng như thế thì việc phân loại là vô ích.
Thuật toán xét tất cả các phép thử có thể để phân chia tập dữ liệu đã cho và
chọn ra một phép thử có giá trị GainRatio tốt nhất. GainRatio là một đại lượng để
đánh giá độ hiệu quả của thuộc tính dùng để thực hiện phép tách trong thuật toán để
phát triển cây quyết định.
GainRatio được tính dựa trên kết quả tính toán đại lượng Information Gain
theo công thức sau:
Trong đó S
i
là tập con của S chứa các ví dụ có thuộc tính A mang giá trị V
i

.
Để ý rằng Splitinfomation thực chất là Entropy của S với sự liện quan trên những
giá trị của thuộc tính A.
GainRatio là sự đánh giá thay đổi các giá trị của thuộc tính. Tất cả các thuộc
tính sẽ được tính toán độ đo tỉ lệ GainRatio. Thuộc tính nào có giá trị GainRatio
lớn nhất sẽ được chọn làm thuộc tính phân chia:
21
GainRatio =
2.2.3 Độ đo V
Độ đo V là độ đo dùng để xác định các mẫu ổn định trong các tập huấn luyện
trong bảng dữ liệu huấn luyện. Trong tập huấn luyện, xác định các giá trị cho trước
và tính lệ của cá giá trị đó.
Ví dụ: áp dụng cho bài toán “Có chơi tennis hay không ?” ở bảng 3.1: Dữ
liệu huấn luyện trong tài liệu tham khảo [1], ta có:
• Outlook(O)
Ta có:
V (O = Sunny) = (2/5, 3/5)
V (O = Overcast) = (4/4, 0/4)
V (O = Rainy) = (3/5, 2/5)
Ta có: V (O = Sunny) = (2/5, 3/5) là tỷ lệ mẫu Sunny có giá trị Yes và tỉ lệ
mẩu Sunny có giá trị No.
• Làm tương tự với Temp(T), Humidity(H), Wind(W) thì Outlook(O) có các
mẫu ổn định nhất nên chọn Outlook làm root.
 Tổng Quát:
Trong tập huấn luyện X (x), xác định các mẫu huấn luyện Y kí hiệu
V(x = Y). Tính tỉ lệ các giá trị “Yes” “ No” có được từ bảng dữ liệu huấn luyện. So
sánh tất cả các mẫu trong các tập huấn luyện có trong bảng dữ liệu huấn luyện:
- Nếu trong tập huấn luyện đó có nhiều mẫu ổn định hơn các mẫu khác (mẫu
tối giản nhỏ nhất) thì chọn mẫu đó là root.
- Tiếp tục khi phân nhánh, chọn tập có nhiều mẫu ổn định nhất đưa đưa vào

cây.
2.2.4 Gini
Chỉ số Gini (Gini index): Chỉ số Gini được sử dụng trong thuật toán
CART. Trái ngược với độ đo Gain, chỉ số Gini là độ đo về tính “không trong suốt”
của tập dữ liệu. Chỉ số Gini của một tập dữ liệu D được định nghĩa như sau:
22
Gini(D) = 1 –
i
)
2
Với m là tổng số nhãn lớp, pi là xác suất để một bộ bất kỳ trong D thuộc về
một nhãn Ci, được tính như sau:
p
i
=
Chỉ số Gini thường sẽ được tính toán dựa trên giả định một tập dữ liệu D
được phân chia nhị phân thành hai tập con. Đầu tiên xét trường hợp thuộc tính A
bất kỳ trong D có kiểu dữ liệu rời rạc, khi dùng phép chiếu sẽ thu được v = {a1, a2
…. . av} giá trị khác nhau. Để xác định điểm chia tốt nhất của A, kiểm tra tất cả
tập con có thể tạo được từ v giá trị phân biệt trên, mỗi tập con tạm gọi là SA là một
điều kiện kiểm tra nhị phân dạng A ∈ SA.
Như vậy với v giá trị khác nhau ta sẽ có 2v - 2 tập con, trong đó tập rỗng và
tập toàn phần v = {a
1
, a
2
…. . a
v
} sẽ không được xét đến. Tiến hành lặp qua tất cả
các tập con này, mỗi lần lặp sẽ phân chia tập giá trị v thành hai tập con v

1
và v
2
riêng biệt thoả điều kiện rời rạc toàn phần (hội v
1
và v
2
chính là tập v và phần giao
là tập rỗng). Với hai tập con v
1
và v
2
này tương ứng tập con D cũng được phân chia
thành hai tập con D
1
(các bộ có giá trị thuộc tính A ∈ v
1
) và D
2
(các bộ có giá trị
thuộc tính A ∈ v
2
) theo, Gini(D) sẽ được tính như sau:
Gini
A
(D) = Gini (D
1)
+ Gini (D
2)
Khác với độ đo Gain, người ta chọn chỉ số Gini nhỏ nhất với mong muốn

sau khi phân chia dữ liệu sẽ làm giảm tính không trong suốt của tập D nhiều nhất.
Đối với các giá trị liên tục có một lưu ý là đầu tiên phải sắp xếp các giá trị này, sau
đó tất cả các giá trị cũng sẽ được tính toán chỉ số Gini và cũng chọn ra giá trị nào có
thuộc tính Gini nhỏ nhất. Cũng giống như độ đo Gain, chỉ số Gini thông thường
cũng được tính cho điểm giữa của hai giá trị liên tục nằm liền kề nhau. Lúc này tập
D sẽ được chia làm hai tập D1 là các bộ dữ liệu thoả điều kiện giá trị thuộc tính A
nhỏ hơn hoặc bằng giá trị điểm giữa và D2 thoả điều kiện giá trị thuộc tính A lớn
23
hơn giá trị điểm giữa. Mục tiêu của chỉ số Gini là càng làm giảm tính không trong
suốt của dữ liệu càng nhiều càng tốt, giá trị giảm trừ này thể hiện qua công thức:
A
(D)
Lưu ý Gini(D) là một con số cố định, chính vì mục đích chọn điểm chia sao
cho Δgini(A) là lớn nhất nên bắt buộc chọn thuộc tính A sao cho GiniA(D) là nhỏ
nhất. Để tìm điểm chia tốt nhất, tiến hành lặp qua tất cả tập con (trừ tập rỗng và tập
toàn bộ) của từng thuộc tính.
CHƯƠNG 3 PHÂN TÍCH MỘT SỐ THUẬT TOÁN
3.1 Giới thiệu
Có rất nhiều thuật toán khác nhau để xây dựng cây quyết định: CLS, ID3,
C4. 5, SPRINT, … Trong báo cáo, chúng em chỉ nghiên cứu một số thật toán phổ
biến.
24
Ở đây, các thuật toán áp dụng cho bài toán “ Có Chơi Tennis” có tập huấn
luyện [1. 1] – theo tài liệu tham khảo [1]
Bài Toán: David là quản lý của một sân đánh tennis nổi tiếng. Anh ta đang
có rắc rối chuyện các thành viên đến hay không đến. Có ngày ai cũng muốn chơi
tennis nhưng số nhân viên của sân lại không đủ phục vụ. Có hôm, không hiểu vì lý
do gì mà chẳng ai đến chơi và sân lại thừa nhân viên.
Mục tiêu của David là tối ưu hóa số nhân viên phục vụ mỗi ngày bằng cách
dựa theo thông tin dự báo thời tiết để đoán xem khi nào người ta sẽ đến chơi tennis.

Để thực hiện điều đó, anh cần hiểu được tại sao khách hàng quyết định chơi và tìm
hiểu xem có cách giải thích nào cho việc đó hay không.
Vậy là trong hai tuần, anh ta thu thập thông tin về:
Quang cảnh (Outlook), Nhiệt độ(Temp), Độ Ẩm (Humidity), Gió(Wind).
Và tất nhiên là số người đến chơi tennis vào hôm đó. David thu được một bộ dữ liệu
gồm 14 dòng và 5 cột.
Day Outlook Temp Humidity Wind PhayTennis
D1 Sunny Hot Hight Weak No
D2 Sunny Hot Hight Strong No
D3 Overcast Hot Hight Weak Yes
D4 Rain Mild Hight Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild Hight Weak No
25
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild Hight Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild Hight Strong No
Bảng 3.1: Dữ liệu huấn luyện trong tài liệu tham khảo [1]
Cách đọc bảng 3.1 như sau: vào ngày D1 lúc này trời đang nắng, có nhiệt độ
cao, độ ẩm cao và gió mạnh thì sẽ không có khách chơi tennis. Các ngày từ
D2 tới D14 sẽ đọc tương tự như D1.
 Mô hình các thuộc tính được chọn trong bảng 3.1 trong hình 3.1:
Outlook Humidity
Yes
Yes

No
No
No
D[3,7,12,13]D[1,2,8,9,11]
Rainy
Sunny
Overcast
Yes
Yes
Yes
No
No
Normal
High
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

Yes
Yes
Yes
D[5,6,7,9,10,11,13]D[1,2,3,4,8,12,14]
D[4,5,6,10,14]