Số hóa bởi trung tâm học liệu
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG CAO VĂN NGUYÊN
NGHIÊN CỨU MỘT SỐ KỸ THUẬT KHAI
PHÁ DỮ LIỆU KHÔNG GIAN SỬ DỤNG
CÂY QUYẾT ĐỊNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2013
Số hóa bởi trung tâm học liệu
ĐẠI HỌC THÁI NGUYÊN

Số hóa bởi trung tâm học liệu

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn chân thành nhất tới PGS. TS Đặng Văn Đức - người đã
hướng dẫn, chỉ bảo tận tình, cung cấp tài liệu và phương pháp luận nghiên cứu khoa
học để tôi hoàn thành bản luận văn này.
Tôi xin bày tỏ lòng cảm ơn sâu sắc tới thầy cô, bạn bè cùng khóa, cùng lớp đã
giúp đỡ tôi trong suốt những năm học qua.
Xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích, động viên và giúp
đỡ tôi trong mọi hoàn cảnh khó khăn.
Tôi xin cảm ơn các thầy cô trong trường Đại học Công nghệ thông tin và Truyền
thông, Đại học Thái Nguyên đã hết sức tạo điều kiện cho tôi trong quá trình học và
làm luận văn này.
Luận văn được hoàn thành trong thời gian hạn hẹp nên không thể tránh được
những thiếu sót. Tôi xin cảm ơn thầy cô, bạn bè, đồng nghiệp đã có những ý kiến đóng
góp chân thành cho nội dung của luận văn, để tôi có thể tiếp tục đi sâu tìm hiểu về lĩnh
vực này trong tương lai.

Thái Nguyên, 11/2013
Cao Văn Nguyên

ii

Số hóa bởi trung tâm học liệu

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của riêng cá nhân
tôi, không sao chép lại của ngƣời khác. Trong toàn bộ nội dung luận văn, những điều

1.2.2. Nhiệm vụ chính trong khai phá dữ liệu 9
1.2.3. Các phƣơng pháp khai phá dữ liệu 11
1.3. Cây quyết định 13
1.3.1. Khái niệm 13
1.3.2. Ƣu điểm và nhƣợc điểm của cây quyết định 14
1.3.3. Xây dựng cây quyết định 14
CHƢƠNG 2 KHAI PHÁ DỮ LIỆU KHÔNG GIAN SỬ DỤNG CÂY QUYẾT ĐỊNH 18
2.1. Phân lớp dữ liệu 18
2.2. Cây quyết định ứng dụng trong phân lớp dữ liệu 20
2.2.1. Thuật toán ID 3 21
2.2.2. Thuật toán C4.5 28
2.3. Xây dựng cây quyết định trong khai phá dữ liệu không gian 34
2.3.1. Tƣ tƣởng xây dựng thuật toán 34
2.3.2. Thuật toán cây quyết định không gian mở rộng từ ID3 36
2.3.3. Ví dụ xây dựng cây quyết định không gian 38
2.3.4. Tìm hiểu, đề xuất phân lớp dữ liệu không gian sử dụng cây quyết định 43
CHƢƠNG 3 CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM 55
3.1. Giới thiệu 55
3.2. Lựa chọn công nghệ 55
3.3. Dữ liệu thử nghiệm 56
iv

Số hóa bởi trung tâm học liệu

3.4. Thiết kế chƣơng trình 59
3.5. Cài đặt chƣơng trình 60
3.6. Đánh giá kết quả thử nghiệm 61
KẾT LUẬN 68
TÀI LIỆU THAM KHẢO 69
PHỤ LỤC 70


DANH MỤC CÁC BẢNG
Bảng 1.1: Topology vùng 6
Bảng 1.2: Topology nút 6
Bảng 1.3: Topology cung 6
Bảng 1.4: Dữ liệu tọa độ cung 7
Bảng 1.5: Mô tả dữ liệu đặc trƣng cấu trúc Spaghetti 7
Bảng 2.1: Dữ liệu thời tiết 24
Bảng 2.2: So sánh Gain của các thuộc tính tại nút gốc 24
Bảng 2.3: So sánh Gain trong nhánh "Quang cảnh" = "Nắng" 25
Bảng 2.4: So sánh Gain trong nhánh "Quang cảnh" = "Mƣa" 26
Bảng 2.5: Dữ liệu thời tiết xét thuộc tính độ ẩm dạng số 31
Bảng 2.6: Bảng tính Gain 32
Bảng 2.7: Dữ liệu thời tiết xét thuộc tính ngày 33
Bảng 2.8: Bảng quan hệ không gian 40
Bảng 2.9: Bảng quan hệ không gian và độ đo không gian 45
Bảng 2.10: Bảng quan hệ không gian đã lƣợc thuộc tính Object ID 48
Bảng 2.11: Bảng quan hệ không gian: khoảng cách đến sông gần nhất 49
Bảng 2.12: Bảng quan hệ không gian rút gọn (đầu vào thuật toán) 50
Bảng 3.1: Bảng dữ liệu đầu vào 62
Bảng 3.2: Tính Gain cho các thuộc tính dự đoán tại nút gốc 64
Bảng 3.3: Tính Gain các thuộc tính dự đoán nhánh BTScover="Low" 65
Bảng 3.4: Tính Gain các thuộc tính dự đoán nhánh Density="Medium" 66
Bảng 3.5: Tính Gain các thuộc tính dự đoán nhánh Density="Low" 66

Hình 2.16: Nhánh Dryland forest - thống kê Layer mật độ dân số 53
Hình 2.17: Nhánh Dryland forest - thống kê khoảng cách đến sông gần nhất 53
Hình 3.1: Bản đồ các trạm BTS trên địa bàn tỉnh Vĩnh Phúc 56
Hình 3.2: Khoảng cách đến BTS gần nhất 57
Hình 3.3: Bản đồ BTS và các điểm mục tiêu 58
Hình 3.4: Mô tả cấu trúc dữ liệu trạm BTS 59
Hình 3.5: Mô tả cấu trúc dữ liệu bệnh viện, trƣờng học, công sở 59
Hình 3.6: Mô tả cấu trúc dữ liệu vùng dân cƣ 60
Hình 3.7: Phần mềm ArcMap và ArcCatalog biên tập dữ liệu GIS 60
Hình 3.8: Mô tả kết quả chạy chƣơng trình 61
Hình 3.9: File dữ liệu Excel biểu diễn bảng dữ liệu đầu vào 62
Hình 3.10: Kết quả trên phần mềm Weka 63
Hình 3.11: Thống kê Tuple tại các nhánh BTScover 64
Hình 3.12: Thống kê Tuple tại nhánh BTScover="Low" và xét Density 65
Hình 3.13: Biểu diễn kết quả dƣới dạng cây quyết định 66

1

Số hóa bởi trung tâm học liệu

MỞ ĐẦU

1. Đặt vấn đề
Những tiến bộ trong công nghệ CSDL và kỹ thuật thu thập dữ liệu nhƣ đọc mã số
mã vạch, viễn thám, ghi nhận thông tin từ các vệ tinh,… đã tạo ra một lƣợng lớn thông
tin, dữ liệu. Việc dữ liệu tăng lên nhanh với quy mô lớn đòi hỏi phải đƣợc khai phá để
trích chọn ra các tri thức hữa ích phục vụ cho công tác chuyên môn. Chính điều này đã
dẫn đến sự ra đời của lĩnh vực khai phá dữ liệu hay khai phá tri thức trong các CSDL.
Khai phá tri thức trong các CSDL có thể đƣợc định nghĩa là khai phá tri thức đáng
quan tâm, tiềm ẩn và chƣa biết trƣớc trong các CSDL. Khai phá dữ liệu là sự kết hợp

2. Mục tiêu của luận văn
- Nghiên cứu một số kỹ thuật phân lớp dữ liệu quan hệ dựa trên cây quyết định:
phƣơng pháp Hunt, thuật toán ID3, thuật toán C4.5.
- Nghiên cứu thuật toán cây quyết định ID3 mở rộng cho dữ liệu không gian. Học
viên đề xuất giải pháp khai phá dữ liệu không gian sử dụng cây quyết định ID3, so
sánh đánh giá giá kỹ thuật mới với thuật toán cây quyết định ID3 mở rộng cho dữ liệu
không gian.
- Nghiên cứu đề xuất dữ liệu thử nghiệm, giải pháp công nghệ cài đặt chƣơng
trình thử nghiệm.
3. Tóm tắt nội dung luận văn
Luận văn đƣợc tổ chức nhƣ sau:
Chƣơng 1: Chƣơng này là cơ sở lý thuyết, giới thiệu khái quát về dữ liệu không
gian, khai phá dữ liệu và cây quyết định.
Chƣơng 2: Trình bày những vấn đề cơ bản về phân lớp dữ liệu, giới thiệu thuật
toán ID3, C4.5 áp dụng cho dữ liệu quan hệ, giới thiệu thuật toán cây quyết định
không gian mở rộng từ ID3, đề xuất một giải pháp phân lớp dữ liệu không gian sử
dụng cây quyết định ID3.
Chƣơng 3: Mô tả bài toán thực tế, xây dựng dữ liệu thử nghiệm, thiết kế chƣơng
trình, cài đặt thuật toán và đánh giá kết quả thử nghiệm thuật toán phân lớp dữ liệu
không gian sử dụng cây quyết định ID3.
Kết luận tóm lƣợc lại những vấn đề đã trình bày và một số hƣớng phát triển
trong tƣơng lai.

3

Số hóa bởi trung tâm học liệu

CHƢƠNG I
TỔNG QUAN VỀ DỮ LIỆU KHÔNG GIAN VÀ KHAI PHÁ DỮ LIỆU


- Các phƣơng pháp mô hình hóa đối tƣợng địa lý (mô hình dữ liệu địa lý):
4

Số hóa bởi trung tâm học liệu

Mô hình dữ liệu địa lý là mô hình dữ liệu sử dụng trong hệ thống thông tin địa lý,
là sự hình dung thế giới giới thực đƣợc sử dụng trong GIS để tạo các bản đồ, trình diễn
các truy vấn giữa ngƣời và máy và thực hiện các phép xử lý, phân tích.
Có nhiều mô hình dữ liệu đƣợc sử dụng trong hệ thống thông tin địa lý,tuy nhiên,
phổ biến nhất trong biểu diễn thành phần không gian của thông tin địa lý là hai mô
hình dữ liệu cơ bản Vector và Raster.
+ Mô hình dữ liệu Vector: sử dụng các đƣờng hay điểm, đƣợc xác định tƣờng
minh bằng các tọa đọa x, y của chúng trên bản đồ.
Điểm: Dùng cho tất cả các đối tƣợng không gian đƣợc biểu diễn nhƣ một cặp tọa độ
(x, y). Ngoài giá trị tọa độ (x, y), điểm còn thể hiện kiểu điểm, màu, hình dạng và dữ liệu
thuộc tính đi kèm. Do đó, trên bản đồ điểm có thể đƣợc biểu hiện bằng ký hiệu hoặc văn
bản.
Hình 1.1: Đối tượng dữ liệu cơ bản Điểm, Đường, Vùng
Đƣờng: Dùng để biểu diễn tất cả các thực thể có dạng tuyến, đƣợc tạo nên từ hai
hoặc nhiều hơn cặp tọa độ (x, y). Ngoài tọa độ, đƣờng còn có thể bao hàm cả góc quay
tại đầu mút.
Vùng: là một đối tƣợng hình học hai chiều. Vùng có thể là một đa giác đơn giản
hay tập hợp của nhiều đa giác đơn giản. Do một vùng đƣợc cấu tạo từ nhiều đa giác
nên cấu trúc dữ liệu của đa giác phải ghi lại đƣợc sự thể thiện của các thành phần này
và các phần tử cấu tạo nên đa giác.
Hình 1.2: Biểu diễn đối tượng bằng mô hình dữ liệu Raster
+ Mô hình dữ liệu Raster: Sử dụng tập hợp các ô. Cấu trúc đơn giản nhất là mảng
gồm các ô của bản đồ. Mỗi ô trên bản đồ đƣợc biểu diễn bởi tổ hợp tọa độ (hàng, cột)
và một giá trị biểu diễn kiểu hoặc thuộc tính của ô đó trên các bản đồ. Trong cấu trúc
này, mỗi ô tƣơng ứng là một điểm. Khái niệm đƣờng là một dạng của các ô liền nhau


Bảng 1.1: Topology vùng
Topology vùng
Vùng
Cung
A
a1, a5, a3
B
a2, a5, 0, a6, 0, a7
C
a7
D
a6
E
vùng ngoài
Bảng Topology nút xác định mỗi nút thuộc những cung nào.
Bảng 1.2: Topology nút
Topology nút
Nút
Cung
N1
a1, a3, a4
N2
a1, a2, a5
N3
a2, a3, a5
N4
a4
N5
a6

a5
N3
N2
A
B
a6
N5
N5
B
B
a7
N6
N6
B
C
Từ 3 bảng này, có thể phân tích các quan hệ của các phần tử trong bản đồ.
Bảng thứ tƣ lƣu trữ tọa độ của các cung bằng cách lƣu trữ tọa độ của các nút và
đỉnh của cung, để từ đó vị trí của mỗi phần tử trên bản đồ đƣợc liên hệ với thế giới
thực. Cấu trúc Topology rất thích hợp với những toán tử phân tích không gian, nhất là
những bài toán kề và kết nối. Trong đó, cấu trúc Topology định rõ các liên kết.

7

Số hóa bởi trung tâm học liệu

Bảng 1.4: Dữ liệu tọa độ cung
Dữ liệu tọa độ cung

55, 15; 40, 15; 45, 27
55, 27
- Cấu trúc Spaghetti: về bản chất cấu trúc này, điểm và đƣờng đƣợc biểu diễn
đơn thuần là vị trí, hầu nhƣ không có mô tả rõ ràng cấu trúc Topology.
Trong cấu trúc dữ liệu Spaghetti, đơn vị cơ sở là các cặp tọa độ trên một không
gian địa lý xác định. Do đó, mỗi đối tƣợng điểm đƣợc xác định bằng một cặp tọa độ
(x, y); mỗi đối tƣợng đƣờng đƣợc biểu diễn bằng một chuỗi những cặp tọa độ (x
i
, y
i
);
mỗi đối tƣợng vùng đƣợc biểu diễn bằng một chuỗi những cặp toạ độ (x
j
, y
j
) với điểm
đầu và điểm cuối trùng nhau. Minh họa cho dữ liệu Spaghetti nhƣ hình vẽ sau:

Hình 1.4:Minh họa dữ liệu Spaghetti
Bảng mô tả đặc trƣng của cấu trúc Spaghetti
Bảng 1.5: Mô tả dữ liệu đặc trưng cấu trúc Spaghetti
Đặc trƣng
Vị trí
Điểm A
(x
A
, y
A
)
Điểm B

, y
B
), (x
A
, y
A
)
Vùng b
(x
A
, y
A
), (x
b1
, y
b1
), (x
b2
, y
b2
), (x
b3
, y
b3
) , (x
B
, y
B
), (x
A


Hình 1.5: Các bước của quá trình khai phá dữ liệu
9

Số hóa bởi trung tâm học liệu

- Bƣớc thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu lĩnh
vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành.
Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức hữu ích và cho phép chọn các
phƣơng pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ
liệu.
- Bƣớc thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn đƣợc
gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu
(làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bƣớc này thƣờng
chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Do dữ liệu đƣợc
lấy từ nhiều nguồn khác nhau, không đồng nhất, có thể gây ra các nhầm lẫn. Sau bƣớc
này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và rời rạc hoá.
- Bƣớc thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là khai phá dữ liệu, hay nói
cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dƣới các dữ liệu. Giai đoạn này
rất quan trọng, bao gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích của
khai phá dữ liệu, dùng phƣơng pháp khai phá nào? Thông thƣờng, các bài toán khai
phá dữ liệu bao gồm: các bài toán mang tính mô tả - đƣa ra tính chất chung nhất của
dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa trên dữ liệu
hiện có. Tùy theo bài toán xác định đƣợc mà ta lựa chọn các phƣơng pháp khai phá dữ
liệu cho phù hợp.
- Bƣớc thứ tƣ: Là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. 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.
- Bƣớc thứ năm: Sử dụng các tri thức phát hiện đƣợc. Là hiểu tri thức đã tìm
đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán.

- Phân nhóm (clustering)
Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các
nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa
thuộc nhóm này lại vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ
phân nhóm nhƣ phát hiện tập các khách hàng có phản ứng giống nhau trong CSDL
tiếp thị; xác định các quang phổ từ các phƣơng pháp đo tia hồng ngoại, … Liên quan
chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm mật độ xác suất đa
biến/ các trƣờng trong CSDL.
- Tổng hợp (summarization)
Là công việc liên quan đến các phƣơng pháp tìm kiếm một mô tả tập con dữ liệu.
Kỹ thuật tổng hợp thƣờng áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo
cáo tự động.
Nhiệm vụ chính là sản sinh ra các mô tả đặc trƣng cho một lớp. Mô tả loại này là
một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một
lớp. Các mô tả đặc trƣng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã
chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Lƣu ý rằng
luật dạng này có các khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho lớp
chỉ sản sinh khi các mục đã thuộc về lớp đó.
- Mô hình hoá sự phụ thuộc (dependency modeling)
Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo
11

Số hóa bởi trung tâm học liệu

hai mức:
+ Mức cấu trúc của mô hình mô tả (thƣờng dƣới dạng đồ thị). Trong đó, các biến
phụ thuộc bộ phận vào các biến khác.
+ Mức định lƣợng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này
thƣờng đƣợc biểu thị dƣới dạng theo luật “nếu - thì” (nếu tiền đề là đúng thì kết luận
đúng).

12

Số hóa bởi trung tâm học liệu

+ Phƣơng pháp tìm kiếm: Phƣơng pháp này bao gồm hai thành phần: Tìm kiếm
tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các
tham số để tối ƣu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát đƣợc
và với một mô tả mô hình đã định. Tìm kiếm mô hình xảy ra giống nhƣ một vòng lặp
qua phƣơng pháp tìm kiếm tham số: Mô tả mô hình bị thay đổi tạo nên một họ các mô
hình. Với mỗi một mô tả mô hình, phƣơng pháp tìm kiếm tham số đƣợc áp dụng để
đánh giá chất lƣợng mô hình.
- Phƣơng pháp suy diễn/quy nạp:
Một CSDL là một kho thông tin nhƣng các thông tin quan trọng hơn cũng có thể
đƣợc suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy
diễn và quy nạp.
Phƣơng pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin
trong CSDL. Ví dụ nhƣ toán tử liên kết áp dụng cho bảng quan hệ, bảng đầu chứa
thông tin về các nhân viên và phòng ban, bảng thứ hai chứa các thông tin về các phòng
ban và các trƣởng phòng. Nhƣ vậy sẽ suy ra đƣợc mối quan hệ giữa các nhân viên và
các trƣởng phòng. 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 xuấ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: Phƣơng pháp quy nạp suy ra các thông tin đƣợc sinh ra từ
CSDL. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu
với các tri thức đã biết trƣớc. Các thông tin mà phƣơng pháp này đem lại là các thông
tin hay các tri thức cấp cao diễn tả về các đối tƣợng trong CSDL. Phƣơng pháp này
liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp
đƣợc sử dụng trong cây quyết định và tạo luật.
- Phƣơng pháp K-láng giềng gần:
Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là có ích

phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B
trong cùng bản ghi đó: A → B.
1.3. Cây quyết định
1.3.1. Khái niệm
Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây, nhƣ mô tả tronghình 1.6:
Hình 1.6: Cây quyết định
Trong cây quyết định:
- Gốc: là nút trên cùng của cây.
- Nút trong: biểu diễn một kiểm tra trên một thuộc tính đơn.
- Nhánh: biểu diễn các kết quả của kiểm tra trên nút trong.
14

Số hóa bởi trung tâm học liệu

- Nút lá: biểu diễn lớp hay sự phân phối lớp.
Để phân lớp mẫu dữ liệu chƣa biết, giá trị các thuộc tính của mẫu đƣợc đƣavào
kiểm tra trên cây quyết định. Mỗi mẫu tƣơng ứng có một đƣờng đi từ gốc đến lá và lá
biểu diễn dự đoán giá trị phân lớp mẫu đó.
1.3.2. Ưu điểm và nhược điểm của cây quyết định
- Cây quyết định có 5 ƣu điểm chính sau:
+ Khả năng sinh ra các quy tắc hiểu đƣợc:Cây quyết định có khả năng sinh ra các
quy tắc có thể chuyển đổi đƣợc sang các câu lệnh SQL.
+ Khả năng thực thi trong những lĩnh vực hƣớng quy tắc: Quy tắc quy nạp nói
chung và câyquyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh vực thực sự là
các quy tắc.
+ Dễ dàng tính toán trong khi phân lớp: Thực tế, các thuật toán sử dụng để tạo ra
cây quyết định thƣờng tạo ra những cây với số phân nhánh thấp và các kiểm tra đơn
giản tại từng node. Những kiểm tra điển hình là: so sánh số, xem xét phần tử của một
tập hợp và các phép nối đơn giản. Khi thực thi trên máy tính, những kiểm tra này
chuyển thành các toán hàm logic và số nguyên là những toán hạng thực thi nhanh và

Do vậy, ở đây chúng ta chỉ tập trung vào nghiên cứu giai đoạn phát triển cây
quyết định. Dƣới đây là khung công việc của giai đoạn này:
Bƣớc 1) Chọn thuộc tính “tốt” nhất bằng một độ đo đã định trƣớc.
Bƣớc 2) Phát triển cây bằng việc thêm các nhánh tƣơng ứng với từng giá trị của
thuộc tính đã chọn.
Bƣớc 3) Sắp xếp, phân chia tập dữ liệu đào tạo tới node con.
Bƣớc 4) Nếu các ví dụ đƣợc phân lớp rõ ràng thì dừng.
Ngƣợc lại: lặp lại bƣớc 1 tới bƣớc 4 cho từng node con.
Thuật toán xây dựng cây quyết định:
- Tƣ tƣởng chung: Phần lớn các thuật toán phân lớp dữ liệu dựa trên cây quyết
định có mã giả nhƣ sau:
Make Tree (Training Data T)
{
Partition(T)
}
Partition(Data S)
{
if (tất cả các điểm trong tập S thuộc cùng một lớp) then
return
for each attribute A do
Tính toán các giá trị phục vụ phân lớp trên thuộc A;
use giá trị phân lớp tốt nhất tìm được để phân vùng tập S thành S
1
, S
2
, , S
k

Partition(S
1

quyết định ứng với T là một lá tƣơng ứng với lớp C
j

Trƣờng hợp 2: T chứa các trƣờng hợp thuộc về nhiều lớp khác nhau trong tập C.
Cần phải lựa chọn một thuộc tính để chia phân lớp T. Việc lựa chọn thuộc tính trên cơ
sở tính toán dựa trên lý thuyết thông tin. Sau khi tìm đƣợc thuộc tính phân chia T, tập T
đƣợc chia thành cácnhánh con (lớp), mỗi lớp là tập hợp các bản ghi đƣợc phân chia trên
cơ sở thuộc tính phân chia và giá trị phân chia (Gọi mỗi lớp con đó là tập con T
1
, T
2
, …,
T
n
). Cây quyết định ứng với T bao gồm: một nút biểu diễn thuộc tính phân lớp đƣợc
chọn, mỗi nhánh tƣơng ứng với phép kiểm tra giá trị thuộc tính và giá trị phân chia
thuộc tính, các cây con hình thành từ các tập con T
i
. Cách thức xây dựng cây con
T
i
tƣơng tự đƣợc xây dựng cây T bằng cácháp dụng đệ quy.
Trƣờng hợp 3: T không chứa case nào. Cây quyết định ứng với T là một lá,
nhƣng lớp gắn với lá đó phải đƣợc xác định từ những thông tin khác ngoài T. Ví dụ
C4.5 chọn giá trị phân lớp là lớp phổ biến nhất tại cha của node này.
- Tình hình nghiên cứu các thuật toán hiện nay:
Các thuật toán phân lớp dữ liệu dựa trên cây quyết định đều có tƣ tƣởng chủ đạo
là phƣơng pháp Hunt đã trình bày ở trên. Luôn có 2 câu hỏi lớn cần phải đƣợc trả lời
trong các thuật toán phân lớp dữ liệu dựa trên cây quyết định là:
1. Làm cách nào để xác định đƣợc thuộc tính tốt nhất để phát triển tại mỗi nút?