Đại Học Công Nghệ Thông Tin
Đại Học Quốc Gia Thành Phố Hồ Chí Minh

TP. HCM 5/2012

Đề tài

Xây dựng cây quyết định
dùng thuật tốn sinh cây ID3

GVHD : GS.TSKH.Hồng Kiếm
Học viên: Trương Lê Hưng
MS: CH1101089
Lớp: Cao Học khóa 6
Mơn học: Cơng nghệ tri thức và ứng dụng


Môn học : Công nghệ tri thức và ứng dụng Trang 2


Lời cảm ơn
Lời đầu tiên em xin chân thành cảm ơn thầy Hoàng Kiếm đã truyền đạt cho em
những bài học thật bổ ích với những câu truyện đầy tính sáng tạo và lý thú.
Cảm ơn nhà trường đã tạo điều kiện cho em cùng các bạn trong lớp có thể học tập
và tiếp thu những kiến thức mới.
Em cũng chân thành cảm ơn các bạn trong lớp đã chia sẻ cho nhau những tài liệu
và hiểu biết về môn học để cùng hồn thành tốt mơn học này.
Trong thời gian vừa qua mặc dù em đã cố gắng rất nhiều để hồn thành tốt đề tài
của mình, song chắc chắn kết quả khơng tránh khỏi những thiếu sót. Em kính mong được
sự cảm thơng và tận tình chỉ bảo của thầy.
TP.Hồ Chí Minh Tháng 5/2012

Học viên thực hiện
Trương Lê Hưng
Lớp Cao Học khóa 6

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 3


Nhận xét
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Môn học : Công nghệ tri thức và ứng dụng Trang 4


Lời mở đầu
Trong nhiều năm qua, cùng với sự phát triển không ngừng của công nghệ
thông tin và ứng dụng trong nhiều lĩnh vực của đời sống và xã hội, thì lượng dữ
liệu được các cơ quan thu thập và lưu trữ ngày càng nhiều lên. Tuy nhiên phần lớn
dữ liệu thơng tin đó khơng được sử dụng hoặc khơng biết cách khai thác sử dụng.
Ngày nay công nghệ đã phát triển một khuynh hướng kỹ thuật mới đó là Kỹ
thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and
Data Mining). Các tri thức mà khai thác dữ liệu mang lại có thể hỗ trợ trong nhiều
hoạt động xã hội trong việc ra quyết định và trả lời những câu hỏi trước đây tốn
nhiều thời gian để xử lý.
Cây quyết định là một công cụ phổ biến và mạnh mẽ được sử dụng trong bài
toán phân loại. Ưu điểm lớn của cây quyết định là thể hiện được các luật. Các luật
này dễ dàng được diễn đạt để con người có thể hiểu được chúng, hiểu được kết
quả của quá trình khai thác dữ liệu.
Trong bài thu hoạch này em xin được áp dụng thuật toán ID3 để xây dưng cây
quyết định.

Nội dung bài thu hoạch bao gồm :
Phần 1 : Cây quyết định.
Phần 2 : Xây dựng cây quyết định bằng thuật toán ID3.
Phần 3 : Xây dựng chương trình Demo.
Phần 4 : Tổng kết.

Môn học : Công nghệ tri thức và ứng dụng Trang 5


Mục lục

Môn học : Công nghệ tri thức và ứng dụng Trang 6


Phần I . Cây quyết định
1.

Giới thiệu
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.
Trong lĩnh vực học máy (machine learning), cây quyết định là một kiểu mơ
hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự
vật, hiện tượng tới các kết luận về giá trị mục tiêu của sự vật, hiện tượng.
Cây quyết định có 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 nút 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.
Ví dụ: cây quyết định về việc chơi tennis

Môn học : Công nghệ tri thức và ứng dụng Trang 7


Hình 1.1: Cây quyết định về việc chơi tennis
2.

Các kiểu cây quyết định
Cây quyết định cịn có hai tên khác:
Cây hồi quy (Regression tree) ước lượng các hàm giá 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 kết quả việc dự đốn là một biến
phân loại như: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay
thua).

3.

Các thuật toán cây quyết định
Một vài thuật toán xây dựng cây quyết định như:
a.

Thuật toán CLS
Thuật toán này được Hovland và Hint giới thiệu trong Concept learning

System (CLS) vào những năm 50 của thế kỷ 20. Sau đó gọi tắt là thuật toán
CLS. Thuật toán CLS được thiết kế theo chiến lược chia để trị từ trên xuống.

b.

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

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 8


tố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 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 quyết định từ trên- xuống (top -down)
c.

Thuật toán C4.5
Thuật toán C4.5 được phát triển và cơng bố bởi Quinlan vào năm 1996.

Thuật tốn C4.5 là một thuật toán được cải tiến từ thuật toán ID3 với việc cho
phép xử lý trên tập dữ liệu có các thuộc tính số (numeric atributes) và và làm
việc được với tập dữ liệu bị thiếu và bị nhiễu. Nó thực hiện phân lớp tập mẫu
dữ liệu theo chiến lược ưu tiên theo chiều sâu (Depth - First). Thuật tố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 tốn để phát triển
cây quyết định.
d.

Thuật toán SLIQ

Thuật toán SLIQ (Supervised Learning In Quest) được gọi là thuật toán

phân lớp leo thang nhanh. Thuật tốn này có thể áp dụng cho cả hai kiểu thuộc
liên tục và thuộc tính rời rạc.
Thuật tốn này có sử dụng kỹ thuật tiền xử lý phân loại (Pre sorting) trước
khi xây dựng cây, do đó giải quyết được vấn đề bộ nhớ cho thuật toán ID3.
Thuật tốn SLIQ có sử dụng giải thuật cắt tỉa cây hữu hiệu.
Thuật tốn SLIQ có thể phân lớp rất hiệu quả đối với các tập dữ liệu lớn và
không phụ thuộc vào số lượng lớp, số lượng thuộc tính và số lượng mẫu trong
tập dữ liệu.
e.

Đánh giá chung các thuật toán xây dựng cây quyết định
Các thuật toán xây dựng cây quyết định đều có những điểm mạnh và điểm

yếu riêng của nó.
- Thuật tốn CLS đây là một trong những thuật tốn ra đời sớm nhất. Nó
chỉ áp dụng cho các CSDL có các thuộc tính nhỏ, giá trị các thuộc tính dạng
phân loại hay rời rạc. Cịn đối với các CSDL lớn và có chứa các thuộc tính mà
giá trị của nó là liên tục thì CLS làm việc khơng hiệu quả.Thuật tốn có thể cho
Mơn học : Công nghệ tri thức và ứng dụng Trang 9


các kết quả khác nhau với cùng một tập dữ liệu đầu vào. Bởi vì, thuật tốn này
chưa có tiêu chí để lựa chọn thuộc tính trong q trình xây dựng cây. Nhưng
đây là thuật toán đơn giản, dễ cài đặt, phù hợp trong việc hình thành ý tưởng và
giải quyết những nhiệm vụ đơn giản.
- Thuật toán ID3: trong thuật toán ID3, Quinlan đã khắc phục được hạn chế
của thuật toán CLS (ID3 được xem là phiên bản cải tiến của CLS). Thuật tốn
này làm việc rất có hiệu quả, nó cho kết quả tối ưu hơn thuật tốn CLS . Khi áp

dụng thuật toán ID3 cho cùng một tập dữ liệu đầu vào và thử nhiều lần thì cho
cùng một kết quả. Bởi vì, thuộc tính ứng viên được lựa chọn ở mỗi bước trong
quá trình xây dựng cây được lựa chọn trước. Tuy nhiên thuật toán này cũng
chưa giải quyết được về vấn đề thuộc tính số, liên tục, số lượng các thuộc tính
cịn bị hạn chế và giải quyết hạn chế với vấn đề dữ liệu bị thiếu hoặc bị nhiễu.
- Thuật toán C4.5: Để tiếp tục khắc phục những nhược điểm của thuật toán
ID3, Quinlan đã đưa ra thuật toán C4.5(C4.5 là sự cải tiến cho thuật toán ID3
và cọi là phiên bản sau của ID3). Trong thuật toán này đã giải quyết được vấn
đề làm việc với thuộc tính số(liên tục), thuộc tính có nhiều giá trị, và vấn đề dữ
liệu bị thiếu hoặc bị nhiễu. Trong C4.5 thực hiện việc phân ngưỡng với thuộc
tính số bằng phép tách nhị phân đưa vào đại lượng GainRatio thay thế cho đại
lượng Gain của ID3. Để giải quyết được vấn đề thuộc tính có nhiều giá trị.
Ngồi ra C4.5 cịn có bước cắt tỉa nhánh khơng phù hợp. Tuy nhiên yếu điểm
của thuật toán này là làm việc khơng hiệu quả với những CSDL lơn vì chưa
giải quyết được vấn đề bộ nhớ.
- Thuật toán SLIQ phân lớp rất có hiệu quả đối với các tập dữ liệu lớn, nó
làm việc khơng phù thuộc vào số lượng các lớp, các thuộc tính và số lượng bản
ghi trong tập dữ liệu. SLIQ đã cải thiện được vấn đề về bộ nhớ vì có 3 pha tiền
xử lý phân loại, tại một thời điểm chỉ có 1 danh sách lớp thường trú trong bộ
nhớ. SLIQ có kỹ thuật cắt tỉa cây mô tả độ dài tối thiểu MDL, rất hữu hiệu. Nó
là thuật tốn phân lớp nhanh, chính xác, chi phí thấp. Tuy nhiên việc cài đặt
phức tạp, áp dụng cho các cơ sở dữ liệu lớn.

Môn học : Công nghệ tri thức và ứng dụng Trang 10


Mặc dù đã có nhiều cải tiến, nhiều thuật tốn xây dựng cây quyết định ra
đời, nhưng nói chung vấn cịn nhiều vấn đề khó khăn phức tạp và nhiều thách
thức trong khai phá dữ liệu bằng cây quyết định. Như vấn đề dữ liệu bị thiếu
giá trị đối với các thuộc tính trong CSDL. Vấn đề các CSDL rất lớn về số

lượng các thuộc tính và về số lượng các bản ghi, vấn đề về bộ nhớ…Những
vấn đề này luôn làm đau đầu những nhà khoa học. Trên thực tế các thuật toán
xây dựng cây quyết định vấn đang được cải tiến, nghiên cứu và phát triển.
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ác kỹ thuật khác thường địi hỏi
chuẩn hóa dữ liệu, cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị
rỗng.
- 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. Nếu có thể quan sát một tình
huống cho trước trong một mơ hình, thì có thể dễ dàng giải thích điều kiện đó
bằng logic Boolean. Mạng nơ-ron là một ví dụ về mơ hình hộp đen, do lời giải
thích cho kết quả q phức tạp để có thể hiểu được.
- 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ê.
- Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian
ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong
một thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa
trên phân tích của cây quyết định.

5.

Xây dựng một 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, …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:

a.
Giai đoạn thứ nhất xây dựng cây: Giai đoạn này phát triển bắt đầu từ
gốc cho đến mỗi nút lá, 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 .

Môn học : Công nghệ tri thức và ứng dụng Trang 11


b.

Giai đoạn thứ hai cắt tỉa cây: Giai đoạn này nhằm mục đích đơn giản

hóa và khái qt hóa từ đó làm tăng độ chính xác của cây quyết định bằng cách
loại bỏ sự phụ thuộc vào mức độ lỗi (noise) của dữ liệu đào tạo mang tính chất
thống kê, hay những sự biến đổi mà có thể là đặc tính riêng biệt của dữ liệu
đào tạo. Giai đoạn này chỉ truy cập dữ liệu trên cây quyết định đã được phát
triển trong giai đoạn trước và quá trình thực nghiệm cho thấy giai đoạn này
không tốn nhiều tài nguyên tính tốn.
c.
Giai đoạn thứ ba đá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.
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 1.1 ta có thể rút ra được các luật sau.
IF (Outlook = SUNNY) AND (HUMINITY <= 70) THEN PLAY = YES
IF (Outlook = SUNNY) AND (HUMINITY > 70) THEN PLAY = NO

IF (Outlook = OVERCAST) THEN PLAY = YES
IF (Outlook = RAIN) AND (WINDY = TRUE) THEN PLAY = NO
IF (Outlook = RAIN) AND (WINDY = FALSE) THEN PLAY = YES

Môn học : Công nghệ tri thức và ứng dụng Trang 12


Phần II. Xây dựng cây quyết định bằng thuật toán ID3.
1.

Giới thiệu.
Giải thuật quy nạp cây 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).

•

Đầ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 tố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:

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 13


Tập dữ liệu này bao gồm 14 ví dụ tương ứng với 14 ngày. Mỗi ví dụ biểu
diễn cho tình trạng thời tiết của ngày hơm đó gồm các thuộc tính quang
cảnh(Outlook), nhiệt độ(Temperature), độ ẩm(Humidity) và gió(Wind) và đều
có một thuộc tính phân loại chơi Tennis(Playtennis) có hoặc khơng. ‘No’ nghĩa
là không đi chơi tennis ứng với thời tiết ngày hơm đó, ‘Yes’ nghĩa là ngược lại.
Giá trị phân loại ở đây chỉ có hai loại (Yes, No), hay cịn nói phân loại của tập
ví dụ của khái niệm này thành hai lớp (classes). Thuộc tính ‘Playtennis’ cịn
được gọi là thuộc tính đích (target attribute).
Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính Outlook có
ba giá trị (Rain, Overcast, Sunny), nhiệt độ có ba giá trị (nóng, mát, ấm áp), độ
ẩm có hai giá trị (cao, TB) và gió có hai giá trị (mạnh, nhẹ). Các giá trị này
chính là ký hiệu (symbol) dùng để biểu diễn bài toán.
Từ tập dữ liệu rèn luyện này, giải thuật ID3 sẽ học một cây quyết định có
khả năng phân loại đúng đắn các ví dụ trong tập này, đồng thời hy vọng trong
tương lai, nó cũng sẽ phân loại đúng các ví dụ khơng nằm trong tập này. Một
cây quyết định ví dụ mà giải thuật ID3 có thể quy nạp được là:

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 14



Các nút trong cây quyết định biểu diễn cho một sự kiểm tra trên một thuộc
tính nào đó, mỗi giá trị có thể có của thuộc tính đó tương ứng với một nhánh
của cây. Các nút lá thể hiện sự phân loại của các ví dụ thuộc nhánh đó, hay
chính là giá trị của thuộc tính phân loại.
Sau khi giải thuật đã quy nạp được cây quyết định, thì cây này sẽ được sử
dụng để phân loại tất cả các ví dụ hay thể hiện (instance) trong tương lai. Và
cây quyết định sẽ không thay đổi cho đến khi ta cho thực hiện lại giải thuật
ID3 trên một tập dữ liệu rèn luyện khác.
Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân
loại đúng tất cả các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây
quyết định khác nhau tùy thuộc vào thứ tự của các kiểm tra trên thuộc tính.
Vậy làm sao để học được cây quyết định có thể phân loại đúng tất cả các ví
dụ trong tập rèn luyện? Một cách tiếp cận đơn giản là học thuộc lịng tất cả các
ví dụ bằng cách xây dựng một cây mà có một lá cho mỗi ví dụ. Với cách tiếp
cận này thì có thể cây quyết định sẽ khơng phân loại đúng cho các ví dụ chưa
gặp trong tương lai. Vì phương pháp này cũng giống như hình thức ‘học vẹt’,

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 15


mà cây không hề học được một khái quát nào của khái niệm cần học. Vậy, ta
nên học một cây quyết định như thế nào là tốt?
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.
2.


Entropy.
Khái niệm entropy của một tập S được định nghĩa trong Lý thuyết thông tin
là số lượng mong đợi các bít cần thiết để mã hóa thơng tin về lớp của một
thành viên rút ra một cách ngẫu nhiên từ tập S. Trong trường hợp tối ưu, mã có
độ dài ngắn nhất. Theo lý thuyết thơng tin, mã có độ dài tối ưu là mã gán –
log2p bits cho thơng điệp có xác suất là p.
Trong trường hợp S là tập ví dụ, thì thành viên của S là một ví dụ, mỗi ví
dụ thuộc một lớp hay có một giá trị phân loại.
• Entropy có giá trị nằm trong khoảng [0..1],
• Entropy(S) = 0  tập ví dụ S chỉ tồn ví dụ thuộc cùng một loại, hay S là

thuần nhất.
• Entropy(S) = 1  tập ví dụ S có các ví dụ thuộc các loại khác nhau với độ

pha trộn là cao nhất.
• 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 (+).

Môn học : Công nghệ tri thức và ứng dụng Trang 16


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:

Entropy(S) = -P+log2P+ - P-log2PMộ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à:
C

∑ − p log
Entropy(S) =

i=1

Môn học : Công nghệ tri thức và ứng dụng Trang 17

i

2

pi


3.

Information Gain
ID3 sử dụng Information gain để lựa chọn thuộc tính phân chia. Biện pháp
này được dựa trên cơng việc tiên phong của Claude Shannon về lý thuyết thông
tin, nhà nghiên cứu giá trị, nội dung thông tin thư. Chọn N làm đại diện hay giữ
bộ dữ liệu của phân vùng D. Các thuộc tính với độ lợi thơng tin cao nhất được
chọn là thuộc tính phân chia cho N. nút có độ lợi thơng tin nhỏ nhất cần được
phân loại các bộ dữ liệu trong phân vùng kết quả và phản ánh sự ngẫu nhiên là
ít nhất hoặc “khơng trong suốt ” trong những phân vùng này. Như một phương
pháp giảm thiểu số lượng dự kiến của các bộ test cần thiết để phân loại một
tuple và đảm bảo cây đơn giản được tìm thấy.

Những thơng tin dự kiến cần thiết để phân loại một tuple trong D được cho
bởi cơng thức:
Trong đó pi là khả năng mà một mẫu dữ liệu tùy ý trong D thuộc về lớp Ci
và được ước tính bởi | C i, D | / | D |. Hàm log cơ số 2 được sử dụng, bởi vì thơng
tin này đã được mã hóa theo bit. Info (D) là số trung bình của các thông tin cần
thiết để xác định các nhãn lớp của một tuple trong D. Lưu ý rằng, vào thời điểm
này, thơng đó là chỉ dựa vào tỷ lệ bộ dữ liệu của mỗi lớp. Info (D) cũng được
gọi là Entropy của D.
Bây giờ, giả sử đã phân vùng bộ dữ liệu trong D trên một số thuộc tính A có
giá trị riêng biệt, (a1, a2,.., av), như quan sát từ các dữ liệu đào tạo. Nếu A là có
giá trị rời rạc, những giá trị tương ứng trực tiếp cho v kết quả từ phép thử trên
A. Thuộc tính có thể được sử dụng để phân chia thành các phân vùng D thành v
hoặc tập con, (D1, D2,.., DV), nơi Dj chứa những bộ dữ liệu trong D có kết quả
aj của A. Những kết quả của các phân vùng sẽ tương ứng với các nhành xây
dựng từ nút N, ý tưởng là muốn phân vùng này để cho ra một phân loại chính
xác của bộ dữ liệu. Nghĩa là muốn cho mỗi phân vùng là tinh khiết. Tuy nhiên,

Môn học : Công nghệ tri thức và ứng dụng Trang 18


rất có thể những phân vùng sẽ khơng tinh khiết (ví dụ, nơi một phân vùng có thể
chứa một bộ sưu tập của bộ dữ liệu từ các lớp khác nhau chứ không phải từ một
lớp duy nhất). Làm thế nào để nhiều thông tin mà ta cần (sau khi phân vùng) để
đi đến một phân loại chính xác? Con số này được đo bằng:
Dj là tổng số bộ dữ liệu được phân chia và tập con thứ j
Info A(D) là thông tin mong đợi cần thiết để phân loại một tuple từ D dựa
trên các phân vùng của A. những thông tin nhỏ hơn vẫn yêu cầu.
Độ lợi thông tin (Informatin gain) được được định nghĩa là sự khác biệt
giữa những thông tin yêu cầu ban đầu (tức là, dựa trên tỷ lệ của các lớp) và yêu
cầu mới (thu được sau khi phân vùng trên A). Đó là Gain(A) = Info(D) − InfoA

(D).
Nói cách khác, Gain (A) cho chúng ta biết sẽ phân nhánh trên A như thế
nào. Điều này mong muốn sẽ giảm thông tin yêu cầu do biết giá trị của A. Một
thuộc tính với độ lợi thông tin cao nhất (Gain (A )), được chọn là thuộc tính chia
tách tại nút N. Điều này tương đương với cách nói rằng muốn phân vùng trên
thuộc tính A mà có thể làm cho việc phân loại “tốt nhất”, do đó số lượng thơng
tin vẫn cịn cần thiết để hoàn thành phân loại bộ dữ liệu là tối thiểu. (có nghĩa là
mức tối thiểu Info(D)).
Cơng thức tính Gain được mô tả cụ thể như sau:
-

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 .
n

Information(Ai ) = -∑ log 2 ( pi ) = Entropy(S)
i=1

-

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:
Gain( S , A) = Information(A) - Entropy(A)= Entropy(S)-

∑

v∉value(A)

Môn học : Công nghệ tri thức và ứng dụng Trang 19


Sv
S

Entropy(Sv )


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.
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.
4.

Giải thuật ID3

Giải thuật ID3 xây dựng cây quyết định được trình bày như sau:
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;
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ùngV các ví dụ trong tập_ví_dụ có giá trị
V tại thuộc tính P;
Gọi induce_tree(phân_vùngV, tập_thuộc_tính), gắn kết
quả vào nhánh V
end
end
end

5.

Ví dụ sử dụng giải thuật ID3

Mơn học : Công nghệ tri thức và ứng dụng Trang 20



Một người cho thuê sân tập tennis muốn biết thời tiết nào thì có người chơi
tennis, anh ta lập bảng theo dõi nhiều ngày được kết quả như sau:

Gọi S là tập huấn luyện, theo như bảng thống kê có 9 ngày chơi tennis và 5 ngày không
chơi. Vậy ta có S[9+,5-] => Entropy(S) =
= 0.94
Xét thuộc tính Outlook có các giá trị Sunny, Overcast, Rain ta có:
SSunny[2+,3-]
SOvercast[4+,0-]
SRain[3+,2-]
Vậy Gain(S,Outlook) = Entropy(S) – 5/14Entropy(SSunny) –
4/14Entropy(SOvercast) – 5/14Entropy(SRain) = 0.246
Xét thuộc tính Temperature có các giá trị Hot, Mild, Cool ta có:
SHot[2+,2-]
SMild[4+,2-]
SCool[3+,1-]

Mơn học : Công nghệ tri thức và ứng dụng Trang 21


Vậy Gain(S, Temperature) = Entropy(S) – 4/14Entropy(SHot) –
6/14Entropy(SMild) – 4/14Entropy(SCool) = 0.246
Xét thuộc tính Wind có các giá trị Weak, Strong ta có:
SWeak[6+,2-]
SStrong[3+,3-]
Vậy Gain(S,Wind) = Entropy(S) – 8/14Entropy(SWeak) – 6/14Entropy(SStrong)
= 0.048
Xét thuộc tính Huminity có các giá trị High, Normal ta có:
SHigh[3+,4-]
SNormal[6+,1-]

Vậy Gain(S, Huminity) = Entropy(S) – 7/14Entropy(SHigh) –
7/14Entropy(SNormal) = 0.151
Như vậy ở bước đầu tiên ta có:
Gain(S, Outlook) = 0.246
Gain (S, Humidity) = 0.151
Gain (S, Wind) = 0.048
Gain (S, Temperature) = 0.029
Như vậy Outlook là thuộc tính phân loại tốt nhất tại bước này nên ta chọn
Outlook là nút gốc của cây.
Outlook có các giá trị Sunny, Overcast, Rain. Vì giá trị Overcast là [4+,0-]
nên suy ra kết quả phân loại ở nhánh Overcast là Yes. Ta có hình bên dưới:

Môn học : Công nghệ tri thức và ứng dụng Trang 22


T lần lượt xét giá trị Sunny và Rain.
Thực hiện tương tự các bước tính Gain tại giá trị Sunny ta có:
Gain (Ssunny, Humidity) = 0.97- (3/5)0.0 – (2/5)0.0 = 0.97
Gain (Ssunny, Wind) = 0.97 – (2/5)1.0 –(3/5)0.918 = 0.019
Gain (Ssunny, Temperature) = 0.97-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.57
Vậy thuộc tính Humidity có giá trị phân loại tốt nhất ở bước này. Humidity
thuộc Ssunny có 2 giá trị High[0+,3-] và Normal[2+,0-] nên kết quả phân loại tại
giá trị High là No và Normal là Yes.
Ta có sơ đồ cây như sau:

Mơn học : Cơng nghệ tri thức và ứng dụng Trang 23


Tiếp tục xét SRain ta có:
Gain (Srain, Humidity) = 0.97- (2/5)1.0 – (3/5)0.91 = 0.02

Gain (Srain, Wind) = 0.97– (3/5)0.0 –(2/5)0.0 = 0.97
Gain (Srain, Temperature) = 0.97-(3/5)0.91-(2/5)1.0=0.02
Như vậy thuộc tính Wind có giá trị phân loại tốt nhất ở bước này. Wind
thuộc Srain có hai giá trị Weak[3+,0-] và Strong[0+,2-] như vậy kết quả phân loại
tại giá trị Weak là Yes và Strong là No.
Kết quả cuối cùng cho ra cây quyết định như sau:

Môn học : Công nghệ tri thức và ứng dụng Trang 24


6.

Đánh giá hiệu suất 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.
Các bước đánh giá hiệu suất cây quyết định:
• Thu thập một tập hợp lớn các ví dụ.
• Chia thành tập rèn luyện và tập kiểm tra.
• Sử dụng giải thuật và tập rèn luyện để xây dựng giả thuyết H(cây quyết
định).
• Đo phần trăm tập kiểm tra được phân loại đúng bởi H.
• Lặp lại bước 1 đến 4 cho các kích cỡ tập kiểm tra khác nhau được chọn
một cách nhẫu nhiên.


7.

Các vấn đề trong ID3
Một thiếu sót quan trọng của ID3 là không gian phân chia hợp lệ tại một
node là cạn kiệt. Một sự phân chia là sự phân hoạch của mỗi trường hợp của

Môn học : Công nghệ tri thức và ứng dụng Trang 25