GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn

Đầu tiên, chúng em xin chân thành cám ơn đã truyền đạt
hết sức nhiệt tình cho chúng em những kiến thức quý báu trong môn 
để chúng em hoàn thành đề tài này.
Em cũng xin gửi lời cám ơn chân thành đến các thầy cô trong trường Đại học
Công Nghệ Thông Tin đã tận tình giúp đỡ em trong thời gian học vừa qua.
Xin cảm ơn tất bạn bè đã và đang động viên, giúp đỡ chúng tôi trong quá trình học
tập và hoàn thành đề tài này.
 ! "#$ %&
'() *
+, /-

Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn

Trong cuộc sống chúng ta luôn luôn phải ra những quyết định, việc ra những
quyết định đúng đắn rất quan trọng cho mọi việc trong cuộc sống của chúng ta. Nếu
chúng ta có một quyết định sai lầm sẽ dẫn đến hậu quả (lớn hay nhỏ tùy tính chất sự
việc) cho chúng ta.
“Hệ hỗ trợ ra quyết định” bắt đầu xuất hiện từ năm 1970 và đã được phát triển
đến ngày nay. Nó đã có nhiều đóng góp và hỗ trợ tích cực cho công tác quản lý và ra
quyết định của các nhà quản lý và lãnh đạo cao cấp trong nhiều lĩnh vực khác nhau,
đặc biệt trong lĩnh vực kinh tế.
Trong bài báo cáo này, chúng em đề cập đến hệ hỗ trợ ra quyết định với thuật
toán quy nạp ID3 để xây dựng cây quyết định. Ứng dụng demo chúng em xây dựng ở
đây là chương trình hỗ trợ ra quyết định có nên chơi golf hay không dựa vào thời tiết
(nắng, mưa, độ ẩm, gió, ).
Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
 !"!#

Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn

$$
MỤC LỤC 4
CHƯƠNG 1: TỔNG QUAN HỆ HỖ TRỢ RA QUYẾT ĐỊNH 1
CHƯƠNG 3: GIẢI THUẬT QUY NẠP CÂY QUYẾT ĐỊNH ID3 16
CHƯƠNG 4: CHƯƠNG TRÌNH DEMO HỖ TRỢ RA QUYẾT ĐỊNH “CÓ NÊN ĐI ĐÁNH
GOLF HAY KHÔNG?” 27
TÀI LIỆU THAM KHẢO 39

BẢNG PHÂN CÔNG CÔNG VIỆC 40
Họ tên thành viên 40
Công việc 40
Huỳnh Thanh Việt 40
Tìm hiểu cơ sở lý thuyết 40
Võ Anh Tuấn 40
Xây dựng ứng dụng demo 40
Bảng 4: Bảng phân công công việc 40
Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
%$&"!'()'*
Hình 1: Định nghĩa hệ hỗ trợ ra quyết định
Hình 2: Năng lực hệ hỗ trợ ra quyết định
Hình 3: Mô hình hệ hỗ trợ ra quyết định
Hình 4: Sơ đ‹ cây quyết định
Hình 5: Một phần cây quyết định xây dựng được
Hình 6: Cây quyết định đã xây dựng xong
Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
Hình 7: Entropy(S)
Hinh 8: Class diagram
Hình 9: Giao diện chương trình
Hình 10: File DSS.exe
Hình 11: Giao diện chương trình
Hình 12: Màn hình Import Data
Hình 13: Giao diện chương trình sau khi Import Data
Hình 14: Màn hình khi đang xử lý dữ liệu
Hình 15: Màn hình hiển thị cây quyết định sau khi xử lý hoàn tất
Hình 16: Dữ liệu thử nghiệm 1
Hình 17: Kết quả thử nghiệm 1

Hình 18: Dữ liệu thử nghiệm 2
Hình 19: Kết quả thử nghiệm 2
Hình 20: Dữ liệu thử nghiệm 3
Hình 21: Kết quả thử nghiệm 3
Bảng 1: Các khái niệm cơ sở của các định nghĩa Hệ Hỗ Trợ Quyết Định
Bảng 2: Định nghĩa hệ hỗ trợ quyết định.
Bảng 3: Tập dữ liệu rèn luyện cho khái niệm “Có đi chơi golf không?”
Bảng 4: Bảng phân công công việc
Hệ hỗ trợ ra quyết định
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
+!,-.!/01232/456
,7 89:;<=<>?@AB-
Hệ hỗ trợ ra quyết định là phương pháp lấy tri thức đúng để cho ra quyết định
hợp lý vào đúng lúc và có mức phí hợp lý.
Đó là sự kết hợp giữa tri thức và việc tạo lập quyết định. (Knowledge –
Decision making).
Khái niệm hệ hỗ trợ ra quyết định được đề xuất bởi Michael S.Scott Morton
vào những năm 1970. Hệ hỗ trợ ra quyết định bao g‹m:
• Phần mềm máy tính.
• Chức năng hỗ trợ ra quyết định.
• Làm việc với bài toán có cấu trúc yếu.
• Hoạt động theo cách tương tác với người dùng.
• Được trang bị nhiều mô hình phân tích và mô hình dữ liệu.
0%12
Hệ hỗ trợ ra quyết định Page 1
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
 Các khái niệm cơ sở của các định nghĩa Hệ Hỗ Trợ Quyết Định:
CD 89:EFGH
Gorry & Scott-Morton (1971) Kiểu của bài toán, chức năng hệ thống
Little (1970) Chức năng hệ thống, đặc điểm giao tiếp

Alter (1980) Mục tiêu hệ thống, khuôn mẫu sử dụng
Moore & Chang (1980) Năng lực hệ thống, khuôn mẫu sử dụng
Bonezek et al (1989) Thành phần hệ thống
Keen (1980) Quá trình phát triển
34%1!5!--$6789!2:
Cơ sở của các định nghĩa về hệ hỗ trợ quyết định thay đổi từ nhận thức hệ hỗ
trợ quyết định làm gì (thí dụ, hỗ trợ ra quyết định trong các bài toán phi cấu trúc)
cho đến cách thức đạt được các mục tiêu của hệ hỗ trợ quyết định (các thành phần
yêu cầu, khuôn mẫu sử dụng, quá trình phát triển )
− Các giải thích:
• IJ (1970): hệ hỗ trợ quyết định là tập các thủ tục dựa vào các mô
hình để xử lý dữ liệu và phán xét nhằm trợ giúp các nhà ra quyết định.
• IJ< (1980): định nghĩa hệ hỗ trợ quyết định bằng cách tương phản với
các hệ xử lý dữ liệu điện tử theo 5 thứ nguyên như bảng sau:
KC?L ;<=>?@AB MNIOPQIANRS%TU
Cách dùng Tích cực Thụ động
Người dùng Quản lý Thư ký
Mục tiêu Hiệu dụng Hiệu quả
Thời gian Hiện tại, tương lai Quá khứ
Đặc trưng Linh hoạt Kiên định
3412
Hệ hỗ trợ ra quyết định Page 2
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
• VV<JWC (1980) cho rằng tính cấu trúc trong các định nghĩa
trước đây không thật sự có ý nghĩa vì rằng bài toán mô tả là có cấu trúc
hay phi cấu trúc chỉ tương ứng theo người ra quyết định/tình huống cụ
thể. Vì vậy, nên định nghĩa hệ hỗ trợ quyết định như là hệ thống hỗ trợ
các mô hình quyết định và phân tích dữ liệu tùy biến, được sử dụng ở các
khoảng thời gian bất kỳ, không hoạch định trước.
• &VJXJYJI (1980) cho rằng hệ hỗ trợ quyết định là một hệ máy tính

g‹m 3 thành phần tương tác với nhau: hệ thống ngôn ngữ (cơ chế để giao
tiếp giữa người dùng và các thành phần khác), hệ kiến thức (kho lưu
chứa các kiến thức của lĩnh vực đang xét dưới dạng dữ liệu hay thủ tục)
và hệ xử lý vấn đề (liên kết giữa 2 thành phần kia, chứa một hay nhiều
năng lực xử lý vấn đề tổng quát cần để ra quyết định).
• 8JJ (1980) áp dụng thuật ngữ hệ hỗ trợ quyết định cho các tình huống
ở đó hệ thống cuối cùng chỉ có thể được xây dựng bằng một quá trình
thích nghi về học tập và tiến hóa. Vì vậy, hệ hỗ trợ quyết định là sản
phẩm của quá trình phát triển ở đó người dùng hệ thống, người xây dựng
hệ thống và bản thân hệ thống có khả năng ảnh hưởng lên nhau gây ra
một tiến hóa và khuôn mẫu sử dụng.
Hệ hỗ trợ ra quyết định Page 3
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
Z7 [CI\EE];<=<>?@AB-
01;#</
• Hệ hỗ trợ quyết định cơ bản hỗ trợ các nhà ra quyết định trong các tình huống
nửa cấu trúc và phi cấu trúc bằng cách kết hợp phán xử của con người và xử lý
thông tin bằng máy tính. Các bài toán như vậy không thể/không thuận tiện giải
quyết được chỉ bằng các công cụ máy tính hóa hay các phương pháp định
lượng.
• Phù hợp cho các cấp quản lý khác nhau từ cao đến thấp.
• Phù hợp cho cá nhân lẫn nhóm. Các bài toán ít có tính cấu trúc thường liên đới
đến nhiều cá nhân ở các đơn vị chức năng hay mức tổ chức khác nhau cũng
như ở các tổ chức khác.
• Hỗ trợ cho các quyết định tuần tự, liên thuộc, được đưa ra một lần, vài lần hay
lặplại.
• Hỗ trợ cho các giai đoạn của quá trình ra quyết định: tìm hiểu, thiết kế, lựa
chọn và hiện thực.
• Phù hợp cho một số các phong cách và quá trình ra quyết định.
Hệ hỗ trợ ra quyết định Page 4

GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
^7 9E_`aE]:b;<=<>?@AB-
Một cách hình dung về các thành phần của một hệ hỗ trợ ra quyết định (DDS –
decision support system) và quan hệ giữa chúng là sử dụng các khái niệm đối thoại
(dialog), dữ liệu (data) và mô hình (model). Đối với những người thiết kế hệ thống
DDS cũng như những người sử dụng hệ thống, điều quan trọng là hiểu được các
thành phần này được thiết kế như thế nào. Người sử dụng cần phải biết có thể yêu
cầu cái gì ở DDS. Người thiết kế phải biết được DDS có thể cung cấp cái gì.
0=1>0
Các k— thuật mới có nhiều ảnh hưởng đến các thành phần đối thoại, dữ liệu, và
mô hình; ví dụ như giao diện đ‹ họa hay cơ sở dữ liệu quan hệ. Ngoài ra trí tuệ
nhân tạo cũng cung cấp các khả năng biểu di™n và sử dụng mô hình trong những
hình thức mới.
7 _`aAcVd-
Từ cách nhìn của người sử dụng, thành phần đối thoại là toàn bộ hệ thống.
Cách dùng hệ thống, hướng dẫn cách vận hành của hệ thống và thể hiện các trả lời
Hệ hỗ trợ ra quyết định Page 5
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
của hệ thống đều thông qua thành phần đối thoại. Bennett gọi các yếu tố này bằng
các khái niệm: cơ sở tri thức (knowledge base), ngôn ngữ hành động (action
language), và ngôn ngữ trình bày (representation language). Các yếu tố khác như
phần cứng và phần mềm, cách thức lưu trữ dữ liệu, các thuật toán được dùng
thường không được nhận thức bởi người dùng.
 ?@$AB1
Khi thiết kế thành phần đối thoại của một DDS, điều quan trọng là nhận ra ai là
người dùng của nó. Một DDS có thể chỉ có một người dùng, nhưng cũng có thể có
nhiều người dùng. Một số người dùng chỉ quan tâm đến khía cạnh hỗ trợ quyết
định có tính bề mặt của DDS, một số khác lại có thể dùng DDS một cách rất thành
thục. Đôi khi người ra quyết định dùng DDS một cách trực tiếp, nhưng đôi lúc họ
ra quyết định dựa trên một ban cố vấn và ban cố vấn lại sử dụng DDS. Như vậy

ban quyết định có thể được xem là phần mở rộng của DDS.
Thiết kế thành phần đối thoại của DDS phải cân bằng giữa tính d™ sử dụng và
tính mềm dšo (flexibility). Ví dụ cơ chế hỏi – đáp thì d™ sử dụng nhưng không
mềm dšo vì hệ thống chỉ bao g‹m các câu hỏi đã được lập trình s›n. Ngược lại
ngôn ngữ lệnh (command language) cung cấp cho người dùng nhiều chức năng
hơn, nhưng lại đœi hỏi người dùng phải am hiểu về các lệnh đó. Phần nhiều các
DDS sử dụng ngôn ngữ lệnh.
 678-CD5EF<@G@H7@I1
Cơ sở tri thức bao g‹m những gì người dùng biết về cách thức hệ thống vận
hành cũng như cách dùng hệ thống đó. Thường thì các tri thức xung quanh bài toán
cần được giải phải được cung cấp cho DDS, sau đó thì DDS mới có thể ra quyết
định. Một ngoại lệ là trường hợp DDS được dùng để huấn luyện người ra quyết
định. Lúc này DDS là một phương tiện giáo dục.
Người dùng có thể được huấn luyện sử dụng DDS theo nhiều cách khác nhau.
Có thể học sử dụng DDS theo cách một truyền một (one to one), nhưng khi có
nhiều người cần được huấn luyện thì phải sử dụng đến các lớp hay khóa học. Thêm
Hệ hỗ trợ ra quyết định Page 6
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
vào đó, có thể tìm kiếm sự trợ giúp từ một chuyên gia (con người) hay từ những
lệnh giúp đỡ đã được chuẩn bị kèm theo DDS.
DDS có thể d™ sử dụng hơn bằng cách công bố các tài liệu hướng dẫn
(manuals) trên mạng. Hệ thống trợ giúp cảm ngữ cảnh (context sénitive), được kích
hoạt khi người dùng nhấn một phím nào đó.
Tập tin lệnh cũng có thể được dùng. Tập tin lệnh chứa các lệnh cần được thực
thi trong một tập tin, và các lệnh này được thực hiện tuần tự khi tập tin lệnh được
thi hành. Một vài DDS cung cấp cơ chế lưu lại các lệnh: một chuỗi các lệnh đã
được thực thi bởi người dùng có thể được lưu lại trong một tập tin và được thực
hiện lại trong những lần sau bằng cách thực thi tập tin lệnh.
 ;>JKD-E<@I1
Có nhiều loại ngôn ngữ hành động khác nhau, hiểu theo nghĩa ngôn ngữ dùng

để điều hành DDS. Hỏi-đáp, dùng menu, hay ngôn ngữ lệnh đã được giải thích ở
trên. Ngoài ra cœn có một số “ngôn ngữ” khác như sau.
Một vài DDS sử dụng form để nhập/xuất dữ liệu. Người dùng điền dữ liệu đầu
vào (input) dùng form và nhận dữ liệu đầu ra (output) cũng trên form.
Giao diện đ‹ họa cung cấp một phương pháp tiếp cận khác. Các biểu tượng
(icon), ảnh được dùng để đại diện cho các đối tượng như tài liệu, tập tin…, người
dùng sử dụng con chuột để tác động lên các đối tượng đó (như di chuyển, chọn
menu…)
Giọng nói cũng là một loại ngôn ngữ hành động, và yêu cầu công nghệ nhận
dạng giọng nói (speech recognition). Với sự phát triển của công nghệ này, chúng ta
có thể trông đợi nhiều DDS sử dụng giọng nói làm ngôn ngữ hành động hơn.
Tóm lại, bàn phím không phải là sự lựa chọn duy nhất, có thể kể đến các lựa
chọn khác như chuột, các thiết bị trỏ dùng trực tiếp trên màn hình hay là micro.
 ;>J0H1
Hệ hỗ trợ ra quyết định Page 7
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
Ngày trước, máy in là một ngu‹n xuất dữ liệu. Khả năng đ‹ họa của màn hình
cung cấp nhiều cách thể hiện mới. Màn hình có thể thể hiện các hình ảnh, đ‹ thị.
Ngoài ra âm thanh cũng được xem xét như một khả năng mới.
 !5-LD7<@I)M-EN-1
Tổ hợp các kiểu thực hiện các thành phần con như cơ sở tri thức, ngôn ngữ
hành động và ngôn ngữ trình bày, ta được nhiều kiểu thành phần hội thoại khác
nhau. Một số DDS thiên về bàn phím và buộc người dùng phải nhớ các tổ hợp
phím để thực thi các lệnh. Một số DDS trực quan hơn thì cho phép người dùng
dùng chuột để tác động lên các đại diện của các đối tượng cần thao tác.
e7 _`aPQI-
DDS không dùng các dạng dữ liệu thô thu được trong các quá trình giao dịch
của các tổ chức. Dữ liệu thường phải được tóm tắt, cô đọng trước khi được sử dụng
bởi DDS. Lý tưởng nhất là công việc này cũng được tự động bằng máy tính.
Nhưng đôi lúc cũng được thực hiện bằng tay khi không tốn quá nhiều công sức hay

công việc đœi hỏi việc xử lý tinh tế của con người. Thông thường cần phải dùng
một hệ quản trị cơ sở dữ liệu (DBMS).
Các dữ liệu nội (internal data) cũng được cần đến. Ví dụ như loại dữ liệu liên
quan đến các lĩnh vực của k— sư hay của nhà quản lý. Các dữ liệu này thường
không thể có được qua các quá trình xử lý dữ liệu thông thường được. Chúng phải
được thu thập, nhập liệu, lưu trữ và cập nhật thông qua các phương pháp và tiến
trình đặc biệt. Loại dữ liệu này cũng cần dùng đến hệ quản trị cơ sở dữ liệu
(DBMS).
Các dữ liệu ngoại (external data): như thông tin thương mại, tài chính của một
nền kinh tế, các số liệu công nghiệp cũng đœi hỏi nhiều nỗ lực đặc biệt để có được.
Nhưng khác với dữ liệu nội, dữ liệu ngoại có thể mua được từ các công ty, tổ chức.
Loại dữ liệu này được rút trích từ các cơ sở dữ liệu thương mại…
E7 _`a:fg-
 !<EN-$>01
Hệ hỗ trợ ra quyết định Page 8
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
Có nhiều loại mô hình khác nhau được phân chia dựa trên mục đích sử dụng,
cách xử lý với tính tình cờ (randomness), tính tổng quát của ứng dụng…
Mục đích của mô hình là tối ưu hóa hay để mô tả. Một mô hình dùng để tối ưu
hóa là một mô hình trong đó một đại lượng nào đó cần phải được cực tiểu hóa hay
cực đại hóa. Ví dụ như cực đại hóa lợi nhuận hay cực tiểu hóa chi phí. Nói chung
loại mô hình dùng để mô tả cho người dùng một hình dung đúng về thực tế, cœn
theo nghĩa hžp nó mô tả về cách vận hành của hệ thống và không thực hiện một
phép tối ưu nào.
Nói về tính tình cờ, hầu hết các hệ thống đều mang tính xác suất, nghĩa là hành
vi của hệ thống không thể được đoán trước một cách chính xác, các dữ liệu nhập
vào đều mang tính xác suất thống kê và các dữ liệu xuất ra cũng vậy. Tuy vậy, đa
số các mô hình toán học đều là mô hình tất định (determintistic). Các mô hình tiền
định thường d™ xây dựng hơn, ít tốn kém về thời gian và tiền bạc hơn.
Về tính tổng quát, có mô hình có thể chỉ được dùng với một hệ thống (custom-

build model), nhưng cũng có những mô hình được xây dựng chung cho nhiều hệ
thống khác nhau (ready-build model). Nói chung, custom-build model cung cấp
một cái nhìn k— hơn về một hệ thống cụ thể, tuy nhiên thường tốn kém hơn để xây
dựng vì phải làm từ những việc nhỏ nhất.
 !<()$>01
Thông thường các mô hình được phân thành các lớp sau:
• Mô hình chiến lược: được dùng cho công việc quản lý ở tầm cao, dùng
để hỗ trợ xác định mục đích của tổ chức, các tài nguyên cần có để thực
thi các mục đích này.
• Mô hình chiến thuật: được dùng quản lý ở mức trung cấp, để giúp cất
phát và sử dụng tài nguyên của tổ chức.
• Mô hình hoạt động: dùng để ra những quyết định ngắn hạn (hàng ngày,
hàng tuần).
 !,OPQRS),(-$>01
Hệ hỗ trợ ra quyết định Page 9
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
• Khó khăn trong việc tìm dữ liệu nhập cho mô hình.
• Khó khăn trong việc sử dụng dữ liệu xuất ra từ mô hình.
• Khó khăn trong việc cập nhật hóa mô hình.
• Sự thiếu tin cậy đối với mô hình của người dùng.
• Ÿt có sự hợp nhất, tích hợp giữa các mô hình.
• Sự tương tác yếu (nghèo nàn) giữa mô hình và người dùng.
• Người dùng khó mà tạo mô hình của riêng họ.
• Các mô hình thường ít đưa ra giải thích về dữ liệu xuất (output).
 )M-EN-1
• Các khái niệm thành phần dữ liệu, thành phần đối thoại và thành phần
mô hình cung cấp một phương pháp hữu hiệu để hiểu các thành phần của
một DDS và các tương tác giữa chúng với nhau.
• Thành phần dữ liệu cung cấp dữ liệu để xây dựng, kiểm tra và “bảo
dưỡng” mô hình. Kết xuất của mô hình lại được lưu trong cơ sở dữ liệu

nên có thể làm dữ liệu nhập cho các mô hình khác, do đó có thể tích hợp
nhiều mô hình lại với nhau.
• Thành phần đối thoại không chỉ giúp cho người dùng sử dụng tốt mô
hình, sử dụng một DDS có hiệu quả để ra quyết định mà cœn giúp người
dùng xây dựng mô hình của riêng họ, cho những nhu cầu của riêng họ.
Hệ hỗ trợ ra quyết định Page 10
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
+!Z-h4/456
Trong lý thuyết quyết định (chẳng hạn quản lí rủi ro), một cây quyết định
(tiếng Anh: decision tree) là một đ‹ thị của các quyết định và các hậu quả có thể
của nó (bao g‹m rủi ro và hao phí tài nguyên). Cây quyết định được sử dụng để
xây dựng một kế hoạch nhằm đạt được mục tiêu 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.
,7 89:-
Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng để
phân lớp các đối tượng dựa vào dãy các luật (series of rules). Các thuộc tính của
đối tượng (ngoại trừ thuộc tính phân lớp – Category attribute) có thể thuộc các kiểu
dữ liệu khác nhau (Binary, Nominal, ordinal, quantitative values) trong khi đó
thuộc tính phân lớp phải có kiểu dữ liệu là Binary hoặc Ordinal.
Tóm lại, cho dữ liệu về các đối tượng g‹m các thuộc tính cùng với lớp
(classes) của nó, cây quyết định sẽ sinh ra các luật để dự đoán lớp của các đối
tượng chưa biết (unseen data)
Cây quyết định là một flow-chart giống cấu trúc cây, nút bên trong biểu thị
một kiểm tra trên một thuộc tính, nhánh biểu di™n đầu ra của kiểm tra , nút lá biểu
di™n nhãn lớp hoặc sự phân bố của lớp.
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 y 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).
Việc tạo cây quyết định bao g‹m 2 giai đoạn: Tạo cây và tỉa cây .
Hệ hỗ trợ ra quyết định Page 11
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
• Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau
đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính được
chọn.
• Việc tỉa cây là xát định và xóa những nhánh mà có phần tử hỗn loạn hoặc
những phần tử nằm ngoài (những phần tử không thể phân vào một lớp nào
đó).
 Việc sử dụng cây quyết định như sau: Kiểm tra những giá trị thuộc tính của
mẫu đối với cây quyết định .
Trong lĩnh vực phân lớp, 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. Mỗi một nút trong
(internal node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể
hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến
mục tiêu, cho trước các giá trị của các biến được biểu di™n bởi đường đi từ nút gốc
tới nút lá đó.
Phân lớp bằng cây quyết định cũng là một phương pháp thông dụng trong khai
phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại
diện cho các phân loại cœn cành đại diện cho các kết hợp của các thuộc tính dẫn tới
phân loại đó. Một cây quyết định có thể được phân lớp bằng cách chia tập hợp
ngu‹n thành các tập con dựa theo một kiểm tra giá trị thuộc tính . Quá trình này
được lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành
khi không thể tiếp tục thực hiện việc chia tách được nữa, hay khi một phân loại đơn
có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu
nhiên (random forest) sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân
loại.

Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán
các xác suất có điều kiện.
Hệ hỗ trợ ra quyết định Page 12
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
Cây quyết định có thể được mô tả như là sự kết hợp của các k— thuật toán học
và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho
trước.
Dữ liệu được cho dưới dạng các bản ghi có dạng:
1 2 3
( , ) ( , , , , , )
5
A  A A A A =
Biến phụ thuộc (dependant variable) y là biến mà chúng ta cần tìm hiểu, phân
loại hay tổng quát hóa.
1 2 3
, , A A A
là các biến sẽ giúp ta thực hiện công việc đó.
Z7 9E_`aEi?>?@AB-
Cây quyết định bao g‹m bốn thành phần: nhánh, nút quyết định, nút biến cố và
kết quả.
• Nhánh là một biến cố hay chiến lược nối hai nút hay một nút và kết quả.
• Nút quyết định là một điểm trên cây được biểu di™n bằng hình vuông và
từ đó sẽ phát xuất nhiều nhánh. Mỗi nhánh từ nút quyết định là một
chiến lược khả dĩ sẽ được người ra quyết định xem xét.
• Nút biến cố là một điểm trên cây quyết định được biểu di™n bằng hình
trœn và từ đó cũng sẽ phát xuất nhiều nhánh, mỗi nhánh là một biến cố
có thể xảy ra.
• Kết quả là một chuỗi chiến lược và biến cố tạo thành một con đường
duy nhất trên cây quyết định từ điểm đầu cho đến điểm cuối.
Hệ hỗ trợ ra quyết định Page 13

GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
0&16TU
Hình trên là một cây quyết định tiêu biểu. Nút đầu tiên của cây sẽ bắt đầu bằng
quyết định thứ nhất, một sự chọn lựa giữa chiến lược 1 hay chiến lược 2 sẽ xảy ra.
Theo sau sự chọn chiến lược là một biến cố ngẫu nhiên: biến cố 1 hoặc biến cố 2.
Lúc này người ra quyết định sẽ đứng giữa một trong bốn nút quyết định và phải
thực hiện quyết định thứ 2 giữa chiến lược 3 và chiến lược 4. Theo sau quyết định
này là một biến cố ngẫu nhiên thứ 2: biến cố 3 và biến cố 4. Tùy theo con đường đã
chọn, một trong 16 kết quả sẽ được xem là kết cuộc (từ CP1 đến CP16). Ví dụ: con
đường g‹m chiến lược 1, biến cố 2, chiến lược 3, biến cố 4 sẽ dẫn đến kết quả CP6.
Quyết định tối ưu cho loại bài toán này là chọn một bộ chiến lược duy nhất cho
giá trị kỳ vọng tốt nhất ứng với nút đầu tiên. Lời giải này giả định có thể ấn định
Hệ hỗ trợ ra quyết định Page 14
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
giá trị kỳ vọng ở từng nút biến cố và người ra quyết định sẽ thực hiện một quyết
định phức tạp dựa trên nhiều biến cố ngẫu nhiên.
^7 +Aj:E]Ei?>?@AB
So với các phương pháp khai phá dữ liệu khác, cây quyết định là phương pháp
có một số ưu điểm:
• Cây quyết định d™ hiểu. Người ta có thể hiểu mô hình cây quyết định
sau khi được giải thích ngắn.
• Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần
thiết. 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ây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có
giá trị là tên thể loại. Các k— thuật khác thường chuyên để phân tích các
bộ dữ liệu chỉ g‹m một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể
dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các
biến có giá trị bằng số.
• 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ả quá phức tạp để có thể hiểu được.
• Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này
làm cho ta có thể tin tưởng vào mô hình.
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.
Hệ hỗ trợ ra quyết định Page 15
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
+!^-!"/4kTh4/456%^
,7 !l-
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 5!--$ (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ó:
am_V- 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ó.
a<- 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 golf không ứ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:
C_? /CEn Ab bo: !p F!VIqr
1 Nắng Nóng Cao Nhž Không
2 Nắng Nóng Cao Mạnh Không
3 Âm u Nóng Cao Nhž Có
4 Mưa Ấm áp Cao Nhž Có
Hệ hỗ trợ ra quyết định Page 16
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
5 Mưa Mát TB Nhž Có
6 Mưa Mát TB Mạnh Không
7 Âm u Mát TB Mạnh Có
8 Nắng Ấm áp Cao Nhž Không
9 Nắng Mát TB Nhž Có
10 Mưa Ấm áp TB Nhž Có
11 Nắng Ấm áp TB Mạnh Có
12 Âm u Ấm áp Cao Mạnh Có
13 Âm u Nóng TB Nhž Có
14 Mưa Ấm áp Cao Mạnh Không
34=1V)GJ<-W<E5!--$XY-6-E<Z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 golf (có, không). ‘Không’ nghĩa là không đi chơi golf ứ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 hai <() (classes).
Thuộc tính ‘Chơi golf’ 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 quang cảnh có
ba giá trị (âm u, mưa, nắng), 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à 5]
- (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.
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.
Hệ hỗ trợ ra quyết định Page 17
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
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à 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. 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.

Z7 !ns%^Mi?P\CEi?>?@ABt<LMcC
ID3 xây dựng cây quyết định (cây QĐ) 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
Hệ hỗ trợ ra quyết định Page 18
GVHD: PGS.TS Đỗ Phúc HVTH: Huỳnh Thanh Việt – Võ Anh Tuấn
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
QĐ đơ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 QĐ,
với việc giả định một hàm chọn trắc nghiệm thích hợp. Phần kế tiếp sẽ trình
bày heuristic chọn lựa của ID3.
Ví dụ, hãy xem xét cách xây dựng cây QĐ của ID3 trong hình sau từ tập ví dụ
rèn luyện trong bảng ở trên
0^1K)UAUG/Q
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.
 ID3 xây dựng cây quyết định theo giải thuật sau:
_-E-G@`@@DV)`,a`GbV)`K`aI
H@-
-Z$+-,aGbEV)`,a`GbPc$Ed$K<()@
@$K<!Q!eH8-<()Y
@<7@-ZV)`K`a<@
Hệ hỗ trợ ra quyết định Page 19