LỜI CẢM ƠN
Trước tiên em xin được gửi lời cảm ơn chân thành tới các thầy cô giáo trong
khoa Công nghệ thông tin - Trường đại học sư phạm Hà Nội đã tần tình giúp đỡ và
giảng dạy cho chúng em trong những năm học vừa qua.
Đặc biệt, em xin gửi lời cảm ơn chân thành nhất tới cô giáo - T.S Hồ Cẩm
Hà cùng các thầy cô giáo trong tổ bộ môn Hệ thống thông tin đã tận tình hướng
dẫn, giúp đỡ em hoàn thành đề tài nghiên cứu khoa học này.
Trong thời gian vừa qua mặc dù em đã cố gắng rất nhiều để hoàn thành tốt
đề tài nghiên cứu khoa học của mình. Song chắc chắn kết quả nghiên cứu sẽ không
tránh khỏi những thiếu sót, vì vậy em kính mong nhận được sự chỉ bảo và góp ý của
quý thầy cô và các bạn.
Em xin chân thành cám ơn!
Ký tên
H
ạ
nh
Nguyễn Thị Hạnh
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
MỤC LỤC
LỜI MỞ ĐẦU 3
Chương 1: Tổng quan về khai phá dữ liệu 4
1.1.Khám phá tri thức và khai phá dữ liệu là gì? 4
1.2.Quá trình phát hiện tri thức 5
1.2.1.Hình thành và định nghĩa bài toán 6
1.2.2.Thu thập và tiền xử lý dữ liệu 6
1.2.3.Khai phá dữ liệu và rút ra các tri thức 7
1.2.4.Phân tích và kiểm định kết quả 7
1.2.5.Sử dụng các tri thức phát hiện được 7
1.3.Quá trình khai phá dữ liệu 8
1.3.1.Gom dữ liệu (gatherin) 8
1.3.2.Trích lọc dữ liệu (selection) 8

2.2.3.Thuật toán C4.5 19
2.2.4.Thuật toán SLIQ[5] 23
2.2.5.Cắt tỉa cây quyết định 26
2.2.6.Đánh giá và kết luận về các thuật toán xây dựng cây quyết định 28
Chương 3: Xây dựng chương trình dêmo 30
3.1.Mô tả bài toán 30
3.2.Thu thập và tiền xử lý dữ liệu 30
3.3.Chương trình 31
Chương 4. KẾT LUẬN 31
4.1 Đánh Giá 31
4.1.1 Lý thuyết 31
4.1.2 Ứng dụng 31
4.2 Hướng Phát Triển 31
TÀI LIỆU THAM KHẢO 32
Tài liệu tiếng Việt 32
Tài liệu tiếng Anh 32
LỜI MỞ ĐẦU
Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng
dụng của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, thì lượng dữ
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
3
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
liệu được các cơ quan thu thập và lưu trữ ngày một nhiều lên. Người ta lưu trữ
những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên
theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến
10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm
gì với những dữ liệu này, nhưng họ vẫn tiếp tục thu thập và lưu trữ vì hy vọng
những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách nhanh
chóng để đưa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy, các
phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp

tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng các quy luật, ràng
buộc, qui tắc trong cơ sở dữ liệu.”. Còn các nhà thống kê thì xem " khai phá dữ liệu
như là một quá trình phân tích được thiết kế thăm dò một lượng cực lớn các dữ liệu
nhằm phát hiện ra các mẫu thích hợp và/ hoặc các mối quan hệ mang tính hệ thống
giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm được bằng cách áp dụng
các mẫu đã phát hiện được cho tập con mới của dữ liệu".
Nói tóm lại: khai phá dữ liệu là một bước trong quy trình phát hiện tri thức
gồm có các thụât toán khai thác dữ liệu chuyên dùng dưới một số quy định về hiệu
quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu [4].
1.2. Quá trình phát hiện tri thức
Quá trình khám phá tri thức được tiến hành qua 5 bước sau [5]:
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
5
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Hình 1.1. Quá trình khám phá tri thức
1.2.1. Hình thành và định nghĩa bài toán
Đây là bước tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này
sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các
phương pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản
chất của dữ liệu.
1.2.2.Thu thập và tiền xử lý dữ liệu
Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập
có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này
dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho
phù hợp với phương pháp khai phá dữ liệu được chọn lựa trong bước trên.
Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá tri
thức.
Các giải thuật tiền xử lý dữ liệu bao gồm :
1. Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được
thay thế bởi các giá trị thích hợp

Các giai đoạn của quá trình khám phá 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 các giai đoạn tiếp theo. Các bước của quá trình khám phá tri
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
7
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
thức có thể được lặp đi lặp lại một số lần, kết quả thu được có thể được lấy
trung bình trên tất cả các lần thực hiện.
1.3. Quá trình khai phá dữ liệu
Khai phá dữ liệu là hoạt động trọng tâm của quá trình khám phá tri thức . Thuật
ngữ khai phá dữ liệu còn được một số nhà khoa học gọi là phát hiện tri thức trong cơ sở dữ
liệu ( knowledge discovery in database _KDD) ( theo Fayyad Smyth and Piatestky-
Shapiro 1989). Quá trình này gồm có 6 bước [1]:
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
được chiết xuất ra. Nội dung của quá trình như sau:
1.3.1. Gom dữ liệu (gatherin)
Tập hợp dữ liệu là bước đầu tiên trong khai phá dữ liệu. Bước này lấy
dữ liệu từ trong một cơ sở dữ liệu, một kho dữ liệu, thậm chí dữ liệu từ những
nguồn cung ứng web.
1.3.2. Trích lọc dữ liệu (selection)
Ở giai đoạn này dữ liệu được lựa chọn và phân chia theo một
số tiêu chuẩn nào đó.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
8
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
1.3.3. Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing).
Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là
một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường

Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau nhằm thực hiện
hai chức năng mô tả và dự đoán.
- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả các tính chất hoặc
các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai
phá trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp
(Summarisation), trực quan hoá (Visualization), phân tích sự phát triển và
độ lệch (Evolution and deviation analyst),….
- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa
vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá
trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây
quyết định (Decision tree), thống kê (statictics), mạng nơron (neural
network), luật kết hợp,….
Một số kỹ thuật phổ biến thường được sử dụng để khai phá dữ liệu
hiện nay là :
1.5.1. Phân lớp dữ liệu:
Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ
liệu. Quá trình gồm hai bước: xây dựng mô hình, sử dụng mô hình để phân
lớp dữ liệu( mỗi mẫu 1 lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi
mà độ chính xác của mô hình chấp nhận được.
1.5.2. Phân cụm dữ liệu:
Mục tiêu của phân cụm dữ liệu là nhóm các đối tượng tương tự nhau
trong tập dữ liệu vào các cum, sao cho các đối tượng thuộc cùng một lớp là
tương đồng.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
10
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
1.5.3. Khai phá luật kết hợp:
Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ
giữa các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp
là tập luật kết hợp tìm được. Phương pháp khai phá luật kết hợp gồm có hai

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.
1.6. Các dạng dữ liệu có thể khai phá được
- CSDL quan hệ
- CSDL đa chiều
- CSDL giao dịch
- CSDL quan hệ - đối tượng
- CSDL không gian và thời gian
- CSDL đa phương tiện.
1.7. Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá
dữ liệu
1.7.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành và
lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục,
thống kê, máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song
song với tốc độ cao, thu thập cơ sở tri thức cho hệ chuyên gia,…
1.7.2. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh
vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các
ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo
hỏng hóc trong các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và
phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử
dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; Áp dụng cho
các vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh…
Một số ứng dụng cụ thể như sau :
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
12
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
- Khai phá dữ liệu được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.

Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
13
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Tạo ra tương tác người sử dụng tốt, giúp người sử dụng tham gia điều khiển quá
trình khai phá dữ liệu, định hướng hệ thống khai phá dữ liệu trong việc phát hiện
các mẫu đáng quan tâm. Tích hợp khai phá dữ liệu vào trong các hệ cơ sở dữ liệu.
Ứng dụng khai phá dữ liệu để khai phá dữ liệu web trực tuyến. Một vấn đề quan
trọng trong việc phát triển khám phá tri thức và khai phá dữ liệu đó là vấn đề an
toàn và bảo mật thông tin trong khai phá dữ liệu.
Chương 2: Khai phá dữ liệu bằng cây quyết định
2.1. Cây quyết định
2.1.1. Định nghĩa cây quyết định
Trong lĩnh vực học máy, 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 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 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ị dự đoán 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á đó. Kỹ thuật học máy dùng trong cây
quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn
gọn là cây quyết định. [3]
Ví dụ: Cây quyết định phân lớp mức lương
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
14
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Hình 2.1 Cây quyết định phân lớp mức lương
2.1.2. Ư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.

luật (IF …THEN…). Hai mô hình này là tương đương nhau.
Ví dụ từ cây 2.1 ta có thể rút ra được các luật sau.
IF (Age <= 35) AND (salary<=40) THEN class = bad
IF (Age<=35) AND (salary>40) THEN class = good
IF (Age>35) AND (salary <=50 ) THEN class = bad
IF (Age > 35) AND(salary>50) THEN class = good
2.2. Các thuật toán khai phá dữ liệu bằng cây quyết định
2.2.1. 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. Nó gồm các bước sau [6]:
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.
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á.
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á.
4. Trường hợp ngược lại các mẫu của tập huấn luyện thuộc cả hai lớp
"yes" và "no" thì:
+ Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ liệu
, X có các giá trị v
1
,v
2
, …v
n
.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT

toán ID3 được giới thiệu và trình bày trong mục Induction on decision trees,
machine learning năm 1986. ID3 được xem như là một cải tiến của CLS với
khả năng lựa 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) [5] .
Entropy [5]: dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của một
tập S được tính theo công thức (1)
+ -
2 2
Entropy(S)= - P log ( ) P log ( )P P
+ −
−
(2.1)
Trong trường hợp các mẫu dữ liệu có hai thuộc tính phân lớp "yes"
(+), "no" (-). Ký hiệu p
+
là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết
định là "yes", và p
-
là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no"
trong tập S.
Trường hợp tổng quát, đối với tập con S có n phân lớp thì ta có công
thức sau:
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
17
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
n
i 2
i=1
Entropy(S)= (- P log ( ))
i

p =
∑
(2.3)
- 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:
v
v
v value(A)
S
( , ) Information(A) - Entropy(A)= Entropy(S)- Entropy(S )
S
Gain S A
∉
=
∑
(2.4)
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.
 S
v
bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.
 |S
v
| là số phần tử của tập S
v
.
 |S| là số phần tử của tập S.
Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi
bước triển khai cây, thuộc tính được chọn để triển khai là thuộc tính có giá trị

triển khai cây, thuật toán ID3 được xem là một cải tiến của thuật toán CLS.
Tuy nhiên thuật toán ID3 không có khả năng xử lý đối với những dữ liệu có
chứa thuộc tính số - thuộc tính liên tục (numeric attribute) và khó khăn trong
việc xử lý các dữ liệu thiếu (missing data)và dữ liệu nhiễu (noisy data). Vấn
đề này sẽ được giải quyết trong thuật toán C4.5 sau đây.
2.2.3. 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 toá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 toá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 toán để phát triển cây quyết
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
19
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
định. GainRatio được tính dựa trên kết quả tính toán đại lượng
Information Gain theo công thức sau:
( , )
( , )
(X,T)
Gain X T
GainRation X T
SplitInfo
=
(2.5)
Với:
i i

4. <Tại nút N, thực hiện việc kiểm tra để chọn ra thuộc tính có giá trị
Gain tốt nhất (lớn nhất). Gọi N.test là thuộc tính có Gain lớn nhất>;
5. If <Nếu N.test là thuộc tính liên tục> Then <Tìm ngưỡng cho phép
tách của N.test>;
6. For <Với mỗi tập con T` được tách ra từ tập T> Do
( T` được tách ra theo quy tắc:
- Nếu N.test là thuộc tính liên tục tách theo ngưỡng ở bước 5
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
20
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
- Nếu N.test là thuộc tính phân loại rời rạc tách theo các giá
trị của thuộc tính này.
)
7. { If <Kiểm tra, nếu T' rỗng>} Then
<Gán nút con này của nút N là nút lá>;
Else
8. <Gán nút con này là nút được trả về bằng cách gọi đệ qui lại đối
với hàm xay_dung_cay(T'), với tập T'>;
}
9. <Tính toán các lỗi của nút N>;
<Trả về nút N>;
}
Một số công thức được sử dụng
n
i
x i
i=1
T
Info (T)=- *Info(T )
T

T
 
 ÷
 
∑
(2.9)
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
21
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
( )
( )
Info(X)
Gain X
GainRatio X
Split
=
(2.10)
Giá trị SplitInfo là đại lượng đánh giá thông tin tiềm năng thu thập
được khi phân chia tập T thành n tập hợp con.
GainRatio là tiêu chuẩn để đánh giá việc lựa chọn thuộc tính phân
loại.
2. Làm việc với dữ liệu bị thiếu
Thuật toán vừa xây dựng dựa vào giả thuyết tất cả các mẫu dữ liệu có
đủ các thuộc tính. Nhưng trong thực tế, xẩy ra hiện tượng dữ liệu bị thiếu,
tức là ở một số mẫu dữ liệu có những thuộc tính không được xác
định,hoặc mâu thuẫn, hoặc không bình thường. Ta xem xét kỹ hơn với
trường hợp dữ liệu bị thiếu. Đơn giản nhất là không đưa các mẫu với các
giá trị bị thiếu vào, nếu làm như vậy thì có thể dẫn đến tình trạng thiếu
các mẫu học. Giả sử T là một tập hợp gồm các mẫu cần được phân loại,
X là phép kiểm tra theo thuộc tính L, U là số lượng các giá trị bị thiếu của

mẫu với giá trị trên thuộc tính L đã xác định. Khi đó tiêu chuẩn (2.8) được
viết lại bằng công thức (2.13) như sau:
x
| |
( ) (Info(T)-Info ( ))
| |
T U
Gain X T
T
−
=
(2.13)
Tương tự thay đổi tiêu chuẩn (2.13). Nếu phép kiểm tra có N giá trị đầu
vào thì tiêu chuẩn (2.13) được tính như trong trường hợp chia N tập hợp ban
đầu thành (N+1) tập hợp con.
Giả sử phép thử X có các giá trị O
1
,O
2
,….O
n
được lựa chọn theo tiểu
chuẩn (2.13), ta cần xử lý như thế nào với các dữ liệu bị thiếu. Giả sử mẫu từ
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
22
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
tập hợp T với đầu ra là Oi có liên quan đến tập hợp Ti thì khả năng mẫu đó
thuộc tập hợp Ti là 1.
Giả sử mỗi mẫu trong T
i

Tóm lại giải pháp này được phát biểu như sau: xác suất xuất hiện của
các giá trị bị thiếu tỷ lệ thuận với xác suất xuất hiện của các giá trị không
thiếu.
Qua tìm hiểu trên ta thấy thuật toán C4.5 là cải tiến của thuật toán ID3
2.2.4. Thuật toán SLIQ[5]
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 toá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 toá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 toán SLIQ có sử dụng giải thuật cắt tỉa cây hữu hiệu.
Thuật toá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.
Xây dựng cây quyết định theo thuật toán này chia ra làm 2 giai đoạn:
1. Giai đoạn tạo cây
 Vào: tập dữ liệu học T
 Ra: cây được phân loại trên tập T
Hàm
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
23
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
MakeTree(TrainningData T)
{partition (T) ;}
2. Giai đoạn phân chia tập dữ liệu S
Thủ tục phân loại tập S có giả mã như sau:
Function partition (Data S)
{
If <tất cả các giá trị của tập S đều thuộc cùng một lớp>
Then <kết thúc>

( ) ( ) ( )
split
T T
gini T gini T gini T
T T
= +
(2.15)
Sau khi tính toán chỉ số gini cho các nút, thuộc tính nào có chỉ số gini
nhỏ nhất sẽ được chọn để thực hiện tiếp việc triển khai cây.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
24
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Kỹ thuật tiền xử lý phân loại(Pre_sorting Technique)
Kỹ thuật này tạo ra một lược đồ, lược đồ này được tạo ra bằng cách
sắp xếp dữ liệu tạo ra tại mỗi nút. Ứng với mỗi thuộc tính có một danh sách
riêng tạo ra bởi tập giá trị của thuộc tính và định danh các mẫu dữ liệu. Mỗi
danh sách riêng gọi là danh sách lớp (class list). Các danh sách riêng sẽ tạo ra
tương ứng nhãn của cây gắn với các mẫu học.
Thuật toán SLIQ yêu cầu tại một thời điểm có một danh sách lớp và
chỉ một danh sách thuộc tính được lưu trữ trong bộ nhớ của máy tính, các
danh sách còn lại lưu trên đĩa.
Đánh giá sự phân chia:
Thuật toán đánh giá phân chia:
EvaluateSplits()
{
For <Với mỗi thuộc tính A> do
{ <Duyệt danh sách các giá trị của thuộc tính A>;
For <với mỗi giá trị v trong danh sách thuộc tính > do
<Tìm một mục tương ứng trong danh sách lớp, sau đó hãy tìm
lớp tương ứng với nút lá 1>;