Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CNTT
 
BÁO CÁO THỰC TẬP
Đề tài: “Tìm hiểu khai phá dữ liệu bằng cây quyết định”
GV hướng dẫn : NGUYỄN QUỲNH CHI
Tên Sinh Viên : NGUYỄN ĐỨC TÙNG
NGUYỄN CÔNG TOAN
ĐỒNG THỊ YẾN
Lớp : L10CQCN7-B
Nhóm SV Lớp: L10CQCN7-B
1
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
Lời mở đầu
Trong những năm gần đây, việc nắm bắt được thông tin được coi là chìa
khóa của kinh doanh. Ai thu thập, phân tích và hiểu được thông tin và hành động
được nhờ vào những thông tin đó là kẻ thắng cuộc trong thời đại thông tin này.
Chính vì vậy, việc tạo ra thông tin và mức tiêu thụ thông tin ngày nay ngày càng
gia tăng.
Cúng với chức năng khai thác có tính chất tác nghiệp, việc khai thác các cơ
sở dữ liệu (CSDL) phục vụ các yêu cầu trợ giúp quyết định ngày càng có ý nghĩa
quan trọng và là nhu cầu to lớn trong mọi lĩnh vực hoạt động kinh doanh, quản lý.
Dữ liệu được thu thập và lưu trữ ngày càng nhiều nhưng người ra quyết định trong
quản lý, kinh doanh lại cần những thông tin bổ ích, những “tri thức” rút ra từ nguồn
dữ liệu đó hơn là chính những dữ liệu đó cho việc ra quyết định của mình.
Các nhu cầu đó đã được biết đến từ lâu nhưng mới thực sự bùng nổ từ thập
niên 90 này. Do đó, những năm gần đây đã phát triển mạnh mẽ một loạt các lĩnh
vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin (data warehouse,
information warehouse), các hệ trợ giúp quyết định, các phương pháp phát hiện tri
thức và khai phá dữ liệu (data mining). Trong đó, khai phá dữ liệu và phát hiện tri

Nhiều hệ quản trị cơ sở dữ liệu mạnh với các công cụ phong phú và thuận tiện đã
giúp con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình cơ sở
dữ liệu quan hệ và ngôn ngữ vấn đáp chuẩn (SQL) đã có vai trò hết sức quan trọng
trong việc tổ chức và khai thác các cơ sở dữ liệu đó. Cho đến nay, không một tổ
chức kinh tế nào là không sử dụng các hệ quản trị cơ sở dữ liệu và các hệ công cụ
báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các cơ sở dữ liệu phục vụ cho hoạt động
tác nghiệp của mình.
1.2. Bước phát triển mới của việc tổ chức và khai thác các CSDL
Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin
cũng được chuyên môn hóa, phân chia theo các lỹnh vực ứng dụng như sản xuất,
tài chính, buôn bán thị trường v.v. Như vậy, bên cạnh chức năng khai thác dữ liệu
có tính chất tác nghiệp, sự thành công trong kinh doanh không còn là năng suất của
Nhóm SV Lớp: L10CQCN7-B
3
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
các hệ thống thông tin nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu cầu
trong thực tế, CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu đó.
Các quyết định cần phải có càng nhanh càng tốt và phải chính xác dựa trên những
dữ liệu sẵn có trong khi khối lượng dữ liệu cứ sau 20 tháng lại tăng gấp đôi làm ảnh
hưởng đến thời gian ra quyết định cũng như khả năng hiểu hết được nội dung dữ
liệu. Lúc này các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy không
có khả năng thực hiện công việc này. Để lấy được những thông tin có tính “tri
thức” trong khối dữ liệu khổng lồ này, người ta đã đi tìm những kỹ thuật có khả
năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành
một tập hợp các cơ sở dữ liệu ổn định, có chất lượng, chỉ được sử dụng riêng cho
một vài mục đích nào đó. Các kỹ thuật đó được gọi chung là kỹ thuật tạo kho dữ
liệu (data warehousing) và môi trường các dữ liệu có được gọi là các kho dữ liệu
(data warehouse).
Kho dữ liệu là một môi trường có cấu trúc các hệ thống thông tin, cung cấp
cho người dùng các thông tin khó có thể truy nhập hoặc biểu diễn trong các CSDL

trên, các kho dữ liệu được sử dụng theo ba cách chính:
- Theo cách khai thác truyền thống, kho dữ liệu được sử dụng để
khai thác các thông tin bằng các công cụ vấn đáp và báo cáo.
Tuy nhiên, nhờ có việc chiết xuất, tổng hợp và chuyển đổi từ
các dữ liệu thô sang dạng các dữ liệu chất lượng cao và có tính
ổn định, kho dữ liệu đã giúp cho việc nâng cao các kỹ thuật biểu
diễn thông tin truyền thống (hỏi đáp và báo cáo).
- Thứ hai là các kho dữ liệu được sử dụng để hỗ trợ cho phân tích trực
tuyến (OLAP). Trong khi ngôn ngữ vấn đáp chuẩn SQL và các công cụ làm
báo cáo truyền thống chỉ có thể mô tả những gì có trong CSDL thì phân tích
trực tuyến có khả năng phân tích dữ liệu, xác định xem giả thuyết đúng hay
sai. Tuy nhiên, phân tích trực tuyến lại không có khả năng đưa ra được các
giả thuyết.
Hơn nữa, do kích thước quá lớn và tính chất phức tạp của kho dữ liệu làm
cho nó rất khó có thể được sử dụng cho những mục đích như đưa ra các giả thuyết
từ các thông tin mà chương trình ứng dụng cung cấp (ví dụ như khó có thể đưa ra
được giả thuyết giải thích được hành vi của một nhóm khách hàng).
Trước đây, kỹ thuật học máy thường được sử dụng để tìm ra những giả
thuyết từ các thông tin dữ liệu thu thập được. Tuy nhiên, thực nghiệm cho thấy
chúng thể hiện khả năng rất kém khi áp dụng với các tập dữ liệu lớn trong kho dữ
liệu này. Phương pháp thống kê tuy ra đời đã lâu nhưng không có gì cải tiến để phù
hợp với sự phát triển của dữ liệu. Đây chính là lý do tại sao một khối lượng lớn dữ
Nhóm SV Lớp: L10CQCN7-B
5
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
liệu vẫn chưa được khai thác và thậm chí được lưu trữ chủ yếu trong các kho dữ
liệu không trực tuyến (off-line). Điều này tạo nên một lỗ hổng lớn trong việc hỗ trợ
phân tích và tìm hiểu dữ liệu, tạo ra khoảng cách giữa việc tạo ra dữ liệu và việc
khai thác các dữ liệu đó.Trong khi đó, càng ngày người ta càng nhận thấy rằng, nếu
được phân tích thông minh thì dữ liệu sẽ là một nguồn tài nguyên quý giá trong

xuyên xảy ra, các nhóm đối tượng trong cơ sở dữ liệu, v.v…
Tóm lại: Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in
Database – KDD) là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ
liệu với các tính năng như hợp thức mới, khả ích và có thể hiểu được.
1.3.1. Quá trình khám phá tri thức được tiến hành qua 5 bước sau :
Hình 1.1. Quá trình khám phá tri thức
Mặc dù có 5 giai đoạn như trên, xong quá trình phát hiện tri thức cơ sở dữ
liệu là một quá trình tương tác và lặp đi lặp lại theo kiểu hình xoắn chôn ốc, trong
đó lần lặp sau hoàn chỉnh hơn lần lặp trước. Ngoài ra giai đoạn sau lại dựa trên kết
quảthu được của giai đoạn trước theo kiểu thác nước. Đây là một quá trình
biện trứngmang tính chất học của quá trình phát hiện trí thức và là
phương pháp luận trongviện phát hiện tri thức. Các giai đoạn đó sẽ được trình
bày cụ thể như sau:
GĐ1: Hình thành và định nghĩa bài toán
Đây là bước tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này
sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các
phương pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản
chất của dữ liệu.
Nhóm SV Lớp: L10CQCN7-B
7
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
GĐ2: Thu thập và tiền xử lý dữ liệu
Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập
có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này
dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho
phù hợp với phương pháp khai phá dữ liệu được chọn lựa trong bước trên.
Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá tri
thức.
Các giải thuật tiền xử lý dữ liệu bao gồm :
1. Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được thay thế

nhau trong bối cảnh chung của hệ thống. Các kỹ thuật được sử dụng trong giai đoạn
trước có thể ảnh hưởng đến hiệu quả của các giải thuật được sử dụng trong các giai
đoạn tiếp theo. Các bước của quá trình khám phá tri thức có thể được lặp đi lặp lại
một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực
hiện.
Nhóm SV Lớp: L10CQCN7-B
9
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
CHƯƠNG 2: KHAI PHÁ DỮ LIỆU
2.1. Khai phá dữ liệu là gì?
Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong
CSDL. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự
báo trong kinh doanh, các hoạt động sản xuất, Khai phá dữ liệu làm giảm chi
phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương
pháp thống kê).
Khai thác dữ liệu (data mining) là một ngữ tương đối mới, nó ra đời vào
khoảng những năm cuối của của thập kỷ 1980. Có rất nhiều định nghĩa khác nhau
về khai phá dữ liệu. Giáo sư Tom Mitchell đã đưa ra định nghĩa của khai phá dữ
liệu như sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những
qui tắc và cải thiện những quyết định trong tương lai.”. Với một cách tiếp cận ứng
dụng hơn, tiến sĩ Fayyad đã phát biểu: ”Khai phá dữ liệu thường được xem là việc
khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông
tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng các quy luật, ràng
buộc, qui tắc trong cơ sở dữ liệu.”. Còn các nhà thống kê thì xem " khai phá dữ liệu
như là một quá trình phân tích được thiết kế thăm dò một lượng cực lớn các dữ liệu
nhằm phát hiện ra các mẫu thích hợp và/ hoặc các mối quan hệ mang tính hệ thống
giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm được bằng cách áp dụng
các mẫu đã phát hiện được cho tập con mới của dữ liệu".
Tóm lại: Khai phá dữ liệu là một bước trong quy trình phát hiện tri thức gồm
có các thuật toán khai phá dữ liệu chuyên dùng dưới một số quy định về hiệu quả

2.2.3.Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing).
Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một
bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải
Nhóm SV Lớp: L10CQCN7-B
12
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
trong khi gom dữ liệu là dữ liệu không đầy đủ hoặc không thống nhất, thiếu chặt
chẽ. Vì vậy dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối
dữ liệu. Ví dụ Sinh viên có tuổi=200. Giai đoạn thứ ba này nhằm xử lý các dữ liệu
như trên(dữ liệu vô nghĩa, dữ liệu không có khả năng kết nối). Những dữ liệu dạng
này thường được xem là thông tin dư thừa, không có giá trị. Bởi vậy đây là một quá
trình rất quan trọng. Nếu dữ liệu không được làm sạch- tiền xử lý - chuẩn bị trước
thì sẽ gây nên những kết quả sai lệch nghiêm trọng về sau.
Giai đoạn này có một số chức năng sau:
+ Điều hòa dữ liệu: giảm bớt tính không nhất quán dữ liệu lấy từ nhiều nguồn
khác nhau. Phương pháp thông thường là khử các trường hợp trùng lặp dữ
liệu và thống nhất các ký hiệu.
+ Xử lý các giá trị khuyết: Tính không đầy đủ của dữ liệu có thể gây ra hiện
tượng dữ liệu chứa các giá trị khuyết. Đây là hiện tượng khá phổ biến. Người
ta sử dụng nhiều phương pháp khác nhau để xử lý các giá trị khuyết.
+ Xử lý nhiễu và ngoại lệ: Thông thường nhiễu dữ liệu có thể là nhiễu ngẫu
nhiên hoặc các giá trị bất bình thường. Để làm sạch nhiễu, người ta có thể sử
dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát hiện ra các
ngoại lệ để xử lý.
2.2.4. Chuyển đổi dữ liệu (transformation)
Trong giai đoạn này, dữ liệu có thể được tổ chức và sử dụng lại. Mục đích
của việc chuyển đổi dữ liệu là làm cho dữ liệu phù hợp hơn với mục đích khai phá
dữ liệu.
2.2.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery)
Đây là bước tư duy trong khai phá dữ liệu. Ở trong giai đoạn này nhiều thuật

độ lệch (Evolution and deviation analyst),….
- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa
vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá
trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây
quyết định (Decision tree), thống kê (statictics), mạng nơron (neural
network), luật kết hợp,….
Một số kỹ thuật phổ biến thường được sử dụng để khai phá dữ liệu hiện nay
là :
2.4.1. Phân lớp dữ liệu
Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình gồm hai bước: xây dựng mô hình, sử dụng mô hình để phân lớp dữ
Nhóm SV Lớp: L10CQCN7-B
14
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
liệu( mỗi mẫu 1 lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi mà độ chính
xác của mô hình chấp nhận được.
2.4.2. Phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong
tập dữ liệu vào các cum, sao cho các đối tượng thuộc cùng một lớp là tương đồng.
2.4.3. Khai phá luật kết hợp
Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa
các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp là tập luật
kết hợp tìm được. Phương pháp khai phá luật kết hợp gồm có hai bước:
- Bước 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến được
xác định thông qua tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu.
- Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải
thoả mãn độ hỗ trợ và độ tin cậy cực tiểu.
2.4.4. Hồi quy
Phương pháp hồi quy tương tự như là phân lớp dữ liệu. Nhưng khác ở chỗ nó
dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá

- CSDL không gian và thời gian
- CSDL đa phương tiện.
2.6. Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá dữ
liệu
2.6.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành và
lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục, thống kê,
máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song song với tốc độ
cao, thu thập cơ sở tri thức cho hệ chuyên gia,…
2.6.2. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh
vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các ngành đòi
hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo hỏng hóc trong
các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và phát triển các hệ
thống quản lý và sản xuất trong thực tế như dự đoán tải sử dụng điện, mức độ tiêu
thụ sản phẩm, phân nhóm khách hàng; Áp dụng cho các vấn đề xã hội như phát
hiện tội phạm, tăng cường an ninh…
Một số ứng dụng cụ thể như sau :
- Khai phá dữ liệu được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.
Nhóm SV Lớp: L10CQCN7-B
16
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
- Trong sinh học: nó dùng để tìm kiếm , so sánh các hệ gen và thông tin di
chuyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di
chuyền
- Trong y học: khai phá dữ liệu giúp tìm ra mối liên hệ giữa các triệu
chứng, chuẩn đoán bệnh.
- Tài chính và thị trường chứng khoán: Khai phá dữ liệu để phân tích tình
hình tài chính, phân tích đầu tư, phân tích cổ phiếu
- Khai thác dữ liệu web.

bảo mật thông tin trong khai phá dữ liệu.
Nhóm SV Lớp: L10CQCN7-B
18
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
CHƯƠNG 3: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH
3.1. Cây quyết định
3.1.1. Định nghĩa
Cây quyết định (decision tree) 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. Mặt khác, cây quyết
định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng tri thức là các
luật If-Then.
Cây quyết định là cấu trúc biễu diễn dưới dạng cây. Trong đó, mỗi nút trong
(internal node) biễu diễn một thuộc tính, nhánh (branch) biễu diễn giá trị có thể có
của thuộc tính, mỗi lá (leaf node) biểu diễn các lớp quyết định và đỉnh trên cùng
của cây gọi là gốc (root). Cây quyết định có thể được dùng để phân lớp bằng cách
xuất phát từ gốc của cây và di chuyển theo các nhánh cho đến khi gặp nút lá. Trên
cơ sở phân lớp này chúng ta có thể chuyển đổi về các luật quyết định.
Cây quyết định được sử dụng để xây dựng một kế hoạch nhằm đạt được mục
đích mong muốn. Các cây quyết định được dùng để hỗ trợ quá trình ra quyết định.
Cây quyết định là một dạng đặc biệt của cấu trúc cây.
Tạo cây quyết định chính là quá trình phân tích cơ sở dữ liệu, phân lớp và
đưa ra dự đoán. Cây quyết định được tạo thành bằng cách lần lượt chia (đệ quy)
một tập dữ liệu thành các tập dữ liệu con, mỗi tập con được tạo thành chủ yếu từ
các phần tử của cùng một lớp. Lựa chọn thuộc tính để tạo nhánh thông qua Entropy
và Gain.
Ví dụ: Cây quyết định phân lớp mức lương
Nhóm SV Lớp: L10CQCN7-B
19
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
Hình 3.1 Cây quyết định phân lớp mức lương

20
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
3.1.4.Ưu điểm của cây quyết định
So với các phương pháp khai phá dữ liệu khác, cây quyết định có một số ưu
điểm sau
- Cây quyết định tương đối dể hiểu.
- Đòi hỏi mức tiền xử lý dữ liệu đơn giản.
- Có thể xử lý với cả các dữ liệu rời rạc và liên tục.
- Cây quyết định là một mô hình hộp trắng.
- Kết quả dự đoán bằng cây quyết định có thể thẩm định lại bằng cách kiểm
tra thống kê.
3.1.5.Vấn đề xây dựng cây quyết định
Có nhiều thuật toán khác nhau để xây dựng cây quyết định như: CLS, ID3,
C4.5, SLIQ, SPRINT, EC4.5, C5.0…Nhưng nói chung quá trình xây dựng cây
quyết định đều được chia ra làm 3 giai đoạn cơ bản:
- Xây dựng cây: Thực hiện chia một cách đệ quy tập mẫu dữ liệu huấn
luyện cho đến khi các mẫu ở mối nút lá thuộc cùng một lớp
- Cắt tỉa cây: Là việc làm dùng để tối ưu hoá cây. Cắt tỉa cây chính là việc
trộn một cây con vào trong một nút lá.
- Đá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 đưa
vào.
3.1.6.Rút ra các luật từ cây quyết định
Có thể chuyển đổi qua lại giữa mô hình cây quyết định và mô hình dạng luật
(IF …THEN…). Hai mô hình này là tương đương nhau.
Ví dụ từ cây 2.1 ta có thể rút ra được các luật sau.
IF (Age <= 35) AND (salary<=40) THEN class = bad
IF (Age<=35) AND (salary>40) THEN class = good
IF (Age>35) AND (salary <=50 ) THEN class = bad
IF (Age > 35) AND(salary>50) THEN class = good

,….,T
n
. chia theo
giá trị của X.
+ Tạo n nút con T
i
(i=1,2…n) với nút cha là nút T.
+ Tạo các nhánh nối từ nút T đến các nút T
i
(i=1,2…n) là các
thuộc tính của X.
• Thực hiện lặp cho các nút con T
i
(i =1,2 n) và quay lại bước 2.
Ta nhận thấy trong bước 4 của thuật toán, thuộc tính được chọn để triển khai
cây là tuỳ ý. Do vậy cùng với một tập mẫu dữ liệu huấn luyện nếu áp dụng thuật
toán CLS với thứ tự chọn thuộc tính triển khai cây khác nhau, sẽ cho ra các cây có
hình dạng khác nhau. Việc lựa chọn thuộc tính sẽ ảnh hưởng tới độ rộng, độ sâu, độ
phức tạp của cây. Vì vậy một câu hỏi đặt ra là thứ tự thuộc tính nào được chọn để
triển khai cây sẽ là tốt nhất. Vấn đề này sẽ được giải quyết trong thuật toán ID3
dưới đây.
3.2.2. Thuật toán ID3
Thuật toán ID3 được phát biểu bởi Quinlan (trường đại học Syney,
Australia) và được công bố vào cuối thập niên 70 của thế kỷ 20. Sau đó, thuật toán
ID3 được giới thiệu và trình bày trong mục Induction on decision trees, machine
learning năm 1986. ID3 được xem như là một cải tiến của CLS với khả năng lựa
Nhóm SV Lớp: L10CQCN7-B
22
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
chọn thuộc tính tốt nhất để tiếp tục triển khai cây tại mỗi bước. ID3 xây dựng cây

sau:
n
i 2
i=1
Entropy(S)= (- P log ( ))
i
P
∑

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
Nhóm SV Lớp: L10CQCN7-B
23
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
3.2.2.2. Information Gain
Gain là đại lượng dùng để đo tính hiệu quả của một thuộc tính được lựa chọn
cho 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 A
i
(i=1,2…n) giá trị Information
của thuộc tính A
i

bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.
 |S
v
| là số phần tử của tập S
v
.
 |S| là số phần tử của tập S.
Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi
bước triển khai cây, thuộc tính được chọn để triển khai là thuộc tính có giá trị
Gain lớn nhất.
3.2.2.3.Hàm xây dựng cây quyết định trong thuật toán ID3
Function induce_tree(tập_ví_dụ, tập_thuộc_tính)
begin
if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then
return một nút lá được gán nhãn bởi lớp đó
else if tập_thuộc_tính là rỗng then
return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong
tập_ví_dụ
else begin
chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại;
Nhóm SV Lớp: L10CQCN7-B
24
Báo cáo thực tập GVHD: Nguyễn Quỳnh Chi
xóa P ra khỏi tập_thuộc_tính;
với mỗi giá trị V của P
begin
tạo một nhánh của cây gán nhãn V;
Đặt vào phân_vùng
V
các ví dụ trong tập_ví_dụ có giá trị V

Dl4 Mưa Ấm áp Cao Mạnh Không
Bảng 2.1. Tập dữ liệu ví dụ cho chơi Tennis
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à chơi tennis ứng với thời tiết đó. Giá trị phân loại ở
Nhóm SV Lớp: L10CQCN7-B
25

Trích đoạn Thuật toán xây dựng cây quyết định

---