Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
 PHẠM THỊ PHƢƠNG THẢO
SỬ DỤNG CÂY QUYẾT ĐỊNH TRONG
KHAI PHÁ DỮ LIỆU Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: GS.TS Vũ Đức Thi
Viện khoa học và công nghệ Việt nam, các Thày cô trong trƣờng đại học Công nghệ
Thông tin và Truyền thông, cùng các bạn bè đồng nghiệp. Đặc biệt là sự giúp đỡ
của GS.TS Vũ Đức Thi, ngƣời thầy trực tiếp hƣớng dẫn, đƣa ra ý trƣởng, định
hƣớng, đóng góp các ý kiến chuyên môn và tận tình giúp đỡ em trong suốt quá trình
nghiên cứu và thực hiện luận văn.
Qua đây cho phép em đƣợc bày tỏ lời cảm ơn tới tất cả các thầy cô giáo ở
Viện Công nghệ thông tin và trƣờng đại học Công nghệ Thông tin và Truyền thông,
đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ chúng em trong quá trình học
tập, nghiên cứu.
Cuối cùng, tôi xin cảm ơn đến gia đình, các bạn bè đồng nghiệp đã chia sẻ
động viên giúp đỡ tôi về chuyên môn cũng nhƣ về mọi mặt trong cuộc sống, đó là
nguồn động viên khích lệ giúp tôi có nghị lực hơn để hoàn thành khoá học.

Học viên Phạm Thị Phương Thảo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv
MỤC LỤC LỜI CAM ĐOAN ii
LỜI CẢM ƠN iii
MỤC LỤC iv
DANH MỤC CÁC BẢNG VÀ CÁC HÌNH TRONG LUẬN VĂN vi
LỜI MỞ ĐẦU 1

Chƣơng 3: 57
CÀI ĐẶT THỬ NGHIỆM 57
3.1. Thiết kế tổng thể 57
3.2. Chuẩn bị dữ liệu 58
3.3. Thiết kế chƣơng trình 66
3.4. Kết qủa thực nghiệm và đánh giá 67
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 68
TÀI LIỆU THAM KHẢO 69
PHỤ LỤC 70

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
vi
DANH MỤC CÁC BẢNG VÀ CÁC HÌNH
TRONG LUẬN VĂN

Danh mục các bảng

Bảng 2.1 Tập dữ liệu huấn luyện quyết định chơi tennis 18
Bảng 2.2 Bảng thống kê mức độ nguy hiểm khi lái xe và độ tuổi của lái xe 42
Bảng 2.3. Bảng thông tin phân bổ lớp của thuộc tính Tuổi 42
Bảng 2.4. Bảng thông tin phân bổ lớp của thuộc tính Loại xe 43
Bảng 2.5: Tìm ngƣỡng cho phép tách với thuộc tính Tuổi 45
Bảng 3.1. Bảng dữ liệu về những giấu hiệu của bệnh nhân nhiễm cúm H1N1 58
Bảng 3.2. Bảng tập dữ liệu con ứng với Cổ họng = Ho thƣờng 61
Bảng 3.3. Bảng tập dữ liệu con ứng với Cổ họng = Ho khan 63
Bảng phụ lục: Logarit cơ số hai của các số nguyên từ 1 đến 100 70

Danh mục các hình

Hình 1.1: Quá trình phát hiện tri thức 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
LỜI MỞ ĐẦU

Ngày nay các lĩnh vực khoa học kỹ thuật đang ngày một phát triển mạnh
mẽ. Đặc biệt là nghành khoa học máy tính rất phát triển, nó đƣợc ứng dụng rất
nhiều trong các lĩnh vực khác nhau của cuộc sống nhƣ: Giáo dục, Y tế, Kinh tế,
Khoa học, Xây dựng…
Với sự bùng nổ và phát triển của công nghệ thông tin trong những năm gần
đây, đã mang lại nhiều hiệu quả đối với khoa học cũng nhƣ các hoạt động thực tế,
sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho khả năng thu thập và lƣu
trữ thông tin của các hệ thống thông tin tăng nhanh một cách nhanh chóng, lƣợng
dữ liệu mà chúng ta lƣu trữ trở nên quá nhiều, gây lung túng cho việc lấy ra đƣợc
những thông tin hữu ích. Do vậy, cần có những kỹ thuật và công cụ mới để tự động
chuyển đổi lƣợng dữ liệu khổng lồ kia thành các tri thức hữu ích. Từ đó, các kỹ
thuật khai phá dữ liệu đã trở thành một trong những lĩnh vực mới nhƣng thu hút
đƣợc rất nhiều nhà khoa học quan tâm nghiên cứu nhờ vào những ứng dụng cao
trong thực tiễn cuộc sống. Với hàng loạt các công trình nghiên cứu, giải pháp đƣợc
thử nghiệm và ứng dụng thành công vào đời sống đã chứng minh khai phá dữ liệu là
lĩnh vực nghiên cứu có nền tảng lý thuyết vững chắc.
Một trong những phƣơng pháp khai phá dữ liệu có hiệu quả, đƣợc ứng dụng
nhiều và là vấn đề quan trọng đƣợc nhiều nhà khoa học nghiên cứu nhiều năm qua
là phƣơng pháp Cây quyết định.
Với những khả năng ứng dụng thiết thực vào đời sống xã hội của phƣơng
pháp này, với niềm say mê khám phá mọi lĩnh vực khoa học công nghệ mới có
nhiều triển vọng, tôi đã chọn hƣớng nghiên cứu về đề tài “Sử dụng cây quyết định

1.1. Tính cấp bách của việc khai phá dữ liệu.
Sự phát triển của công nghệ thông tin và việc ứng dụng của công nghệ thông
tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng đồng
nghĩa với lƣợng dữ liệu đƣợc thu thập, tích luỹ ngày càng nhiều lên. Ngƣời ta lƣu
trữ những dữ liệu này vì cho rằng trong đó ẩn chứa những giá trị nào đó. Tuy nhiên,
chỉ có một lƣợng nhỏ của những dữ liệu này là đƣợc phân tích, sử dụng một cách
hiệu quả. Số còn lại không biết phải làm gì nhƣng việc thu thập, lƣu trữ khá tốn kém
vẫn diễn ra thƣờng xuyên vì lo ngại rằng sẽ dung đến chúng trong một lúc nào đó.
Mặt khác, trong môi trƣờng cạnh tranh, ngày càng cần có những thông tin với tốc
độ nhanh để trợ giúp cho việc ra quyết định. Ngày càng có nhiều những câu hỏi
mang tính chất định tính cần phải trả lời dựa trên một khối lƣợng khổng lồ dữ liệu
đã có.
Nhƣ vậy, bên cạnh chức năng khai phá dữ liệu có tính chất tác nghiệp, sự
ứng dụng trong kinh doanh không còn là dữ liệu đơn thuần của các hệ thống nữa mà
cơ sở dữ liệu cần đem lại những “tri thức” hơn là chính dữ liệu đó.
Với những lý do nhƣ vậy, các phƣơng pháp quản trị, khai thác cơ sở dữ liệu
truyền thống, các ngôn ngữ hỏi ngày càng không đáp ứng yêu cầu đặt ra.
Để 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 dữ liệu 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 đƣợc sử dụng chỉ 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 gọi là các kho dữ liệu.
Tuy nhiên, việc sử dụng các cách khai thác dữ liệu theo khai thác truyền
thống mới chỉ dừng lại ở cách khai thác dữ liệu với các kỹ thuật cao để đƣa ra các

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
dữ liệu tinh và chính xác hơn chứ chƣa đƣa ra đƣợc dữ liệu mang tính „tri thức”.
Kho dữ liệu đƣợc sử dụng để hỗ trợ cho phân tích trực tuyến có khả năng phân tích

công cụ khai phá dữ liệu có thể dự đoán những xu hƣớng trong tƣơng lai do đó cho
phép các tổ chức, doanh nghiệp ra quyết định kịp thời đƣợc định hƣớng bởi tri thức
mà công nghệ khai phá dữ liệu đem lại. Sự phân tích dữ liệu một cách tự động và
mang tính dự báo của khai phá dữ liệu khiến nó có ƣu thế hơn hẳn so với sự phân
tích thông thƣờng dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết
định truyền thống trƣớc đây. Công cụ khai phá dữ liệu cũng có thể trả lời các câu
hỏi trong lĩnh vực kinh doanh mà trƣớc đây đƣợc xem là tốn nhiều thời gian để xử
lý.
Với tất cả các ƣu thế trên, khai phá dữ liệu đã chứng tỏ đƣợc tính hữu dụng
của nó trong mỗi môi trƣờng kinh tế, xã hội đầy tính cạnh tranh ngày nay. Giờ đây
khai phá dữ liệu đã và đang trở thành một trong những hƣớng nghiên cứu chính của
lĩnh vực khoa học máy tính và công nghệ tri thức. Phạm vi ứng dụng ban đầu của
khai phá dữ liệu chỉ là trong lĩnh vực thƣơng mại và tài chính. Nhƣng ngày nay,
khai phá dữ liệu đã đƣợc ứng dụng rộng rãi trong các lĩnh vực khác nhau nhƣ: Tin
sinh học, điều trị y học, viễn thông, giáo dục, trí tuệ nhân tạo, cơ sở dữ liệu, thuật
toán học, thu thập tri thức cho các hệ chuyên gia. Đặc biệt, khai phá dữ liệu rất gần
gũi với lĩnh vực thống kê, sử dụng các phƣơng pháp thống kê để mô hình dữ liệu và
phát hiện các luật…
Qua những nội dung đã trình bày ở trên, chúng ta có thể hiểu một cách sơ
lƣợc rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang
tính dự báo trong các cơ sở dữ liệu lớn. Khai phá dữ liệu là cốt lõi của quá trình
khám phá tri thức. Khai phá dữ liệu là nhằm tìm ra những mẫu mới, mẫu có tính
chất không tầm thƣờng, những thông tin tiềm ẩn mang tính dự động chƣa đƣợc biết
đến và có khả năng mang lại ích lợi.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
1.3. Quá trình phát hiện tri thức.
Quá trình phát hiện tri thức đƣợc tiến hành qua 5 bƣớc sau:


Khai phá dữ liệu
Rút ra các tri thức
Phân tích và kiểm định
kết quả
Sử dụng các tri thức
phát hiện đƣợc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
Bước 5: Sử dụng các tri thức phát hiện được
Trong bƣớc này, các tri thức khám phá đƣợc sẽ đƣợc củng cố, kết hợp lại
thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức
đó. Các mô hình rút ra đƣợc đƣa vào những hệ thống thông tin thực tế dƣới dạng
các môdun hỗ trợ việc đƣa ra quyết định.
Các giai đoạn của quá trình phát hiện tri thức có mối quan hệ chặt chẽ với
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 những
giai đoạn tiếp theo. Các bƣớc của quá trình phát hiện 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ả những lần
thực hiện.
1.4. Quá trình khai phá dữ liệu.
Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỹ
1980. Nó là quá trình khám phá thông tin ẩn đƣợc tìm thấy trong các cơ sở dữ liệu
và có thể xem nhƣ là một bƣớc trong quá trình khám phá tri thức. Data Mining là
giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri
thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
Quá trình khai phá dữ liệu đƣợc thực hiện qua 6 giai đoạn nhƣ Hình 1.2

Hình 1.2. Quá trình khai phá dữ liệu
Quá trình khai phá dữ liệu bắt đầu với kho dữ liệu thô và kết thúc với tri thức

nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Thuật
toán thƣờng dùng để trích mẫu dữ liệu là thuật toán phân loại dữ liệu, kết hợp dữ
liệu, thuật toán mô hình hoá dữ liệu tuần tự…

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
Giai đoạn 6. Đánh giá kết quả mẫu (evaluation of result )
Đây là giai đoạn cuối cùng trong quá trình khai phá dữ liệu, ở giai đoạn này
các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải mẫu
dữ liệu nào cũng hữu ích, đôi khi nó còn bị sai lệch. Vì vậy cần phải đƣa ra những
tiêu chuẩn đánh giá độ ƣu tiên cho các mẫu dữ liệu để rút ra đƣợc những tri thức
cần thiết.
Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5
là giai đoạn đƣợc quan tâm nhiều nhất hay còn gọi đó là Data Mining. Các bƣớc
trên có thể 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.
1.5. Các dạng dữ liệu có thể khai phá.
Khai phá dữ liệu đƣợc ứng dụng rộng rãi nên có rất nhiều kiểu dữ liệu khác
nhau đƣợc chấp nhận để khai phá, sau đây là một số loại điển hình:
Cơ sở dữ liệu quan hệ (relational databases): là các cơ sở dữ liệu tác nghiệp
đƣợc tổ chức theo mô hình dữ liệu quan hệ. Hầu hết các hệ quản trị cơ sở dữ liệu
đều hỗ trợ dạng cơ sở dữ liệu này.
Cơ sở dữ liệu đa chiều (multimensional structures, data warehouses, data
mart): là các kho dữ liệu đƣợc tập hợp, chọn lọc từ nhiều nguồn dữ liệu khác nhau.
Dạng dữ liệu này mang tính lịch sử (tức có tính thời gian) và chủ yếu phục vụ cho
quá trình phân tích cũng nhƣ là khai phá tri thức nhằm hỗ trợ cho việc ra quyết định.
Cơ sở dữ liệu dạng giao dịch (transactional databases): là dạng cơ sở dữ
liệu tác nghiệp nhƣng các bản ghi thƣờng là các giao dịch. Dạng dự liệu này thƣờng
phổ biến trong lĩnh vực thƣơng mại và ngân hàng.
Cơ sở dữ liệu quan hệ - hướng đối tượng (object – Relational Databases): là

1.7. Một số lĩnh vực ứng dụng của khai phá dữ liệu.
Khai phá dữ liệu là một lĩnh vực mới phát triển nhƣng thu hút đƣợc nhiều nhà
nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Nó đƣợc vận dụng trong
nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú đƣợc lƣu trữ
trong các hệ thống thông tin. Tuỳ theo bản chất của từng lĩnh vực, việc vận dụng
khai phá dữ liệu có những cách tiếp cận khác nhau.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Một số lĩnh vực ứng dụng điển hình:
 Khai phá dữ liệu đƣợc sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.
 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.
 Trong sinh học: nó dùng để tìm kiếm, so sánh các hệ gen và thông tin di truyề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 truyền.
 Trong thông tin kỹ thuật: khai phá dữ liệu dùng để phân tích các sai hỏng, điều
khiển và lập lịch trình.
 Trong thông tin thƣơng mại: dùng để phân tích dữ liệu ngƣời dùng, phân tích dữ
liệu marketing, phân tích đầu tƣ, phát hiện các gian lận.
 Tài chính và thị trƣờng chứng khoán: khai phá dữ liệu dùng để 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. 1.8. Lựa chọn các kỹ thuật khai phá.
Các giải thuật khai phá dữ liệu tự động mới chỉ ở giai đoạn phát triển ban
đầu. Hiện nay chúng ta vẫn chƣa có đƣợc một tiêu chuẩn thống nhất về việc sử
dụng phƣơng pháp nào vào trong trƣờng hợp nào thì hiệu quả cao nhất.
Hầu hết các kỹ thuật về khai phá dữ liệu đều là mới trong các lĩnh vực. Hơn
nữa lại có rất nhiều kỹ thuật đƣợc sử dụng cho nhiều bài toán khác nhau. Vì vậy câu

đối tƣợng dữ liệu thành một số lớp nhất định. Các nút của cây đƣợc gán nhãn là tên
các thuộc tính, các cạnh đƣợc gán các giá trị có thể của các thuộc tính, các lá miêu
tả các lớp khác nhau. Các đối tƣợng đƣợc phân lớp theo các đƣờng đi trên cây, qua
các cạnh tƣơng ứng với giá trị của các thuộc tính của đối tƣợng tới lá.
Các luật đƣợc tạo ra nhằm suy diễn cho một số mẫu dữ liệu có ý nghĩa về
mặt thống kê. Các luật có dạng “Nếu P thì Q”, trong đó P là mệnh đề đúng với một
phần dữ liệu trong cơ sở dữ liệu và Q là mệnh đề dự đoán.
Cây quyết định là phƣơng pháp dùng trong các bài toán phân loại dữ liệu
theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Cây quyết
định và luật có ƣu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu
đối với ngƣời sử dụng. Tuy nhiên, giới hạn của nó là miêu tả cây và luật chỉ có thể
biểu diễn đƣợc một số dạng chức năng và vì vậy giới hạn cả về độ chính xác của mô
hình.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
1.9.2. Phương pháp suy diễn và quy nạp.
Phƣơng pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm
trong cơ sở dữ liệu dựa trên các quan hệ trong dữ liệu. Phƣơng pháp suy diễn dựa
trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết
suất đƣợc bằng cách sử dụng phƣơng pháp này thƣờng là các luật suy diễn.
Phƣơng pháp quy nạp: Các thông tin đƣợc suy ra từ cơ sở dữ liệu bằng cách
nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết
trrƣớc.
1.9.3. Luật kết hợp.
Mục tiêu của phƣơng pháp này nhằm phát hiện ra các luật kết hợp giữa các
thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của thuật giải phát hiện luật kết
hợp là tập các luật kết hợp tìm đƣợc. Nhƣợc điểm cơ bản của phƣơng pháp này là
sự gia tăng nhanh chóng khối lƣợng tính toán và các thông số. Tuy nhiên với sự
phát triển nhanh chóng và mạnh mẽ của phần cứng thì vấn đề này cũng đƣợc khắc

thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hóa
trong sinh học.
Giải thuật di truyền là một giải thuật tối ƣu hóa, nó đƣợc sử dụng rất rộng rãi
trong việc tối ƣu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng
neural. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối ƣu hóa là
cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Chƣơng 2:
KỸ THUẬT KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT
ĐỊNH

2.1. Giới thiệu kỹ thuật khai phá dữ liệu sử dụng cây quyết định.
Kỹ thuật khai phá dữ liệu sử dụng cây quyết định là kỹ thuật đƣợc trình bày
trọng tâm trong luận văn này.
Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân
lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá trị của đối
tƣợng dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo. Tri thức đƣợc rút ra trong kỹ
thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản, trực quan, dễ hiểu
đối với ngƣời sử dụng.
Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tƣợng
dữ liệu thành một số lớp nhất định. Các nút của cây đƣợc gán nhãn là tên của các
thuộc tính, các cạnh đƣợc gán các giá trị có thể của các thuộc tính, các lá mô tả các
lớp khác nhau. Các đối tƣợng đƣợc phân lớp theo các đƣờng đi trên cây, qua các
cạnh tƣơng ứng với giá trị của thuộc tính của đối tƣợng tới lá.
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:
- Cây quyết định tƣơng đối dễ hiểu. Ngƣời ta có thể hiểu đƣợc mô hình của cây
quyết định chỉ cần sau khi đƣợc giải thích ngắn gọn.

 Các đỉnh lá (các đỉnh không khai triển đƣợc) biểu thị các lớp hoặc các phân
bổ lớp.
 Đỉnh trên cùng trong một cây đƣợc gọi là gốc.
Việc sinh cây quyết định được chia làm hai giai đoạn:
 Xây dựng cây
- Tại thời điểm khởi đầu, tất cả các case dữ liệu học đều nằm tại gốc.
- Các case dữ liệu đƣợc phân chia đệ quy trên cơ sở các thuộc tính đƣợc chọn.
 Rút gọn cây:
Phát hiện và bỏ đi các nhánh chứa các điểm dị thƣờng và nhiễu trong dữ liệu.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
2.2. Thuật toán sử dụng cho việc xây dựng cây quyết định
Trong khai phá dữ liệu bằng cây quyết định thì xây dựng cây là vấn đề mấu
chốt và quan trọng nhất. Các thuật toán xây dựng cây quyết định đã đƣợc các nhà
khoa học phát triển, công bố và cải tiến qua thời gian.
Dƣới đây là một số thuật toán xây dựng cây quyết định:
2.2.1. Thuật toán CLS
Xây dựng cây quyết định lần đầu tiên đƣợc Hoveland và Hunt giới thiệu
trong Concept Learning System -CLS vào cuối 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 và gồm những bƣớc sau:

Bƣớc 1. Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện.
Bƣớc 2. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị
"yes" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "yes" và dừng lại.
T lúc này là nút lá.
Bƣớc 3. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị “no”
(hay thuộc cùng một lớp), thì gán nhãn cho nút T là “no” và dừng lại. T lúc
này là nút lá.

18
Ngày
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi Tennis
D1
Nắng
Nóng
Cao
Nhẹ
Không
D2
Nắng
Nóng
Cao
Mạnh
Không
D3
Âm u
Nóng
Cao
Nhẹ
Có
D4
Mƣa
Ấm áp
Cao
Nhẹ

Có
D10
Mƣa
Ấm áp
TB
Nhẹ
Có
D11
Nắng
Ấm áp
TB
Mạnh
Có
D12
Âm u
Ấm áp
Cao
Mạnh
Có
D13
Âm u
Nóng
TB
Nhẹ
Có
D14
Mƣa
Ấm áp
Cao
Mạnh