1
MỤC LỤC

MỞ ĐẦU 4

CHƢƠNG 1. TỔNG QUAN 6
1.1. SƠ LƢỢC VỀ KHAI PHÁ TRI THỨC 6
1.1.1. Dữ liệu và tri thức 6
1.1.2. Khai phá tri thức 8
1.1.3. Các quá trình khai phá tri thức 9
1.2. KHAI PHÁ DỮ LIỆU 12
1.2.1. Khái niệm khai phá dữ liệu 12
1.2.2. Mục tiêu của khai phá dữ liệu 13
1.2.3. Chức năng của khai phá dữ liệu 13
1.2.4. Phương pháp khai phá dữ liệu 16
1.2.5. Các kỹ thuật khai phá dữ liệu 20
1.2.6. Các thách thức khi khai phá dữ liệu 25
1.2.7. Các yêu cầu khi khai phá dữ liệu 27
1.2.8. Đánh giá, kết luận 28

CHƢƠNG 2. CÁC KHÁI NIỆM CƠ BẢN 30
2.1. CÂY QUYẾT ĐỊNH 30
2.1.1. Khái niệm chung 30
2.1.2. Xây dựng cây quyết định 33
2.1.3. Cắt tỉa cây quyết định 34
2.1.4. Đánh giá cây quyết định 34
2.2. CƠ SỞ DỮ LIỆU QUAN HỆ 34
2.2.1. Quan hệ 34
2.2.2. Cơ sở dữ liệu quan hệ 35


KẾT LUẬN 68
TÀI LIỆU THAM KHẢO 70
3
DANH MỤC CÁC TỪ VIẾT TẮT
CSDL
Cơ sở dữ liệu
CNTT
Công nghệ thông tin
FDs
Phụ thuộc hàm
Functional Dependencies
AFDs
Phụ thuộc hàm xấp xỉ
Aproximate Functional Dependencies
CLS
Concept Learning System
ID3
Interative Dichotomizer
GA
Thuật toán di truyền
Genetic Algorithm
dụng cây quyết định nhằm phục vụ công tác nghiên cứu chuyên môn cũng như
mong muốn đưa các kỹ thuật khai phá dữ liệu sử dụng cây quyết định vào thực
tế nên tôi lựa chọn thực hiện luận văn tốt nghiệp sau đại học là “Một số phƣơng
pháp xây dựng cây quyết định trong khai phá dữ liệu”. Mục đích khi thực
hiện luận văn này là tổng hợp các kiến thức về kỹ thuật khai phá dữ liệu bằng
các kỹ thuật xây dựng cây quyết định dựa trên các thuật toán và phương pháp
xây dựng cây quyết định dựa trên phụ thuộc hàm của cơ sở dữ liệu quan hệ.
Nội dung chính của luận văn bao gồm 5 chương, trong đó: 5
Chƣơng 1. Tổng quan, chương này trình bày khái quát về các vấn đề về
khai phá dữ liệu, các thách thức gặp phải khi sử dụng các kỹ thuật khai phá dữ
liệu và các ứng dụng của khai phá dữ liệu và tình hình nghiên cứu về khai phá
dữ liệu nói chung và kỹ thuật khai phá dữ liệu sử dụng cây quyết định nói riêng
ở thế giới và nước ta.
Chƣơng 2. Các khái niệm cơ bản, bao gồm các khái niệm cơ bản về
khai phá dữ liệu, cây quyết định, các khái niệm trong cơ sở dữ liệu quan hệ.
Chƣơng 3. Một số phƣơng pháp xây dựng cây quyết định, chương này
là trọng tâm của luận văn đề cập đến phương pháp xây dựng cây quyết định dựa
trên các thuật toán khai phá dữ liệu bằng cây quyết định bao gồm các thuật toán
CLS, ID3, C4.5 và phương pháp xây dựng cây quyết định dựa trên phụ thuộc
hàm xấp xỉ trong cơ sở dữ liệu quan hệ.
Chƣơng 4. Ứng dụng thử nghiệm, chương này so sánh các kỹ thuật xây
dựng cây quyết định và đưa ra bài toán ứng dụng thử nghiệm để từ đó áp dụng
một phương pháp khai phá dữ liệu cho bài toán đã nêu ra, từ đó thiết kế các
modul cho triển khai bài toán.
Chƣơng 5. Đánh giá, kết luận, chương này đưa ra các đánh giá, kết luận
và các phân tích sau khi thực hiện luận văn.
Trong luận văn, các trích dẫn của các tác giả khác liên quan đến lĩnh vực

“Chúng ta đang ngập chìm trong dữ liệu mà vẫn đói tri thức” [1], điều đó cũng
báo trước việc ứng dụng công nghệ thông tin đang chuyển sang một thời kỳ mới
mà mục đích chủ yếu của công nghệ thông tin là giúp con người nhiều hơn trong 7
quá trình tìm kiếm, khai phá tri thức từ dữ liệu, biến đổi từ sự giàu có về thông
tin thành sự giàu có về tri thức.
Các khái niệm thông tin, dữ liệu và tri thức luôn có quan hệ chặt chẽ, mật
thiết với nhau và khó phân biệt được bằng các định nghĩa rõ ràng. Ta có thể hiểu
thông tin như là khái niệm chung nhất bao gồm mọi sự hiểu biết về các sự vật,
hiện tượng, quan hệ,… mà con người thu nhận được qua các giác quan, giao
tiếp, khảo sát, thực nghiệm, nghiên cứu, lý giải,… Dữ liệu có thể được mô tả bởi
các giá trị cho các sự kiện, hiện tượng cụ thể còn tri thức có thể được xem như là
những hiểu biết có mức độ khái quát, về các mối quan hệ có quy luật giữa các
thuộc tính của đối tượng, các sự vật, hiện tượng mà con người thu được sau khi
“chân lý hóa” bằng kinh nghiệm, phân tích dữ liệu hay qua nghiên cứu, lý giải,
suy luận. Hoạt động nhận thức của con người bao gồm việc tìm kiếm tri thức để
tăng cường sự hiểu biết về xã hội và cuộc sống, từ đó có thể tạo nên các kỹ
thuật, công nghệ và giải pháp nhằm cải thiện đời sống của mình. Dưới sự trợ
giúp của công nghệ thông tin, các phương pháp khai phá tri thức từ dữ liệu đã
được từng bước nghiên cứu và các công cụ, giải pháp nhằm tổ chức các kho
thông tin và dữ liệu có khả năng linh hoạt hơn trong việc trợ giúp quyết định
trên nền kiến trúc khách hàng, phục vụ thích hợp, với việc sử dụng các phương
pháp khai phá dữ liệu và phát hiện tri thức hiện đang được nghiên cứu rộng rãi
trên thế giới cũng như ở Việt Nam.
Từ nhiều thế kỷ qua, nếu như khoa học luôn hướng đến việc phát hiện các
tri thức có giá trị phổ biến dưới dạng các nguyên lý, quy luật, định lý,… thì ngày
nay chúng ta càng thấy rõ rằng ngay trong cuộc sống hàng ngày, trong việc quản
lý, kinh doanh,… cũng cần những tri thức có thể có ý nghĩa hẹp hơn, ít phổ biến

logic toán, trong các trò chơi giải trí trí tuệ cao, phiên dịch,… ngay từ thập niên
năm mươi tuy còn khá thô sơ nhưng cũng đủ để kích thích một chân trời mới
cho nhiều ngành khoa học và công nghệ tri thức cho các thập niên tiếp theo. Và
trong quá trình phát triển đó, con người có dịp tìm hiểu sâu hơn bản thân hoạt
động nhận thức của mình, hệ thống tri thức mà mình tích lũy được, đưa ra các
thuộc tính của tri thức và những đòi hỏi đối với tri thức trong hoạt động thực
tiễn của con người trong một môi trường ngày càng nhiều biến động đồng thời 9
cũng thúc đẩy việc nghiên cứu những phương pháp khoa học mới và giải pháp
công nghệ để biểu diễn, thu thập và tìm kiếm tri thức, xử lý tri thức, quản trị tri
thức nhằm đáp ứng các nhu cầu của con người trong quá trình vận động.
Quá trình phát triển của khai phá tri thức có thể chia theo một số bước
như sau [3]:
- Tri thức chắc chắn và các phương pháp suy luận logic tất định.
- Tri thức không chắc chắn và việc tìm quy luật cho “cái” không chắc chắn
- Tri thức không chắc chắn trong môi trường biến động
Chúng ta có thể tổng hợp khái niệm khai phá tri thức như sau [3]: Khai
phá tri thức (đôi khi còn gọi là khai phá dữ liệu hay khám phá tri thức), một cách
chung nhất là một quá trình phân tích dữ liệu từ nhiều nguồn dữ liệu khác nhau
và tổng hợp dữ liệu thành các tri thức.

1.1.3. Các quá trình khai phá tri thức
Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình
sau [4]:
Xác định vấn đề và không
gian dữ liệu để giải quyết
vấn đề.
Chuẩn bị dữ liệu

hệ thống dữ liệu đã được xây dựng và biến đổi. Tại đây, công việc phân tích và
đưa ra các quyết định lựa chọn khai thác dữ liệu, áp dụng các kỹ thuật xây dựng,
khai phá dữ liệu để trích chọn các mẫu, mô hình, các mối quan hệ ẩn trong dữ
liệu để từ đó khai phá tri thức cần thiết. Các lớp mô hình phổ biến của các
phương pháp khai phá dữ liệu là:
- Mô hình dự đoán bao gồm phân lớp (classification), hồi quy (regression)
và phân cụm (clustering)
- Mô hình phụ thuộc, chẳng hạn như các mô hình đồ thị hoặc ước lượng
mật độ 11
- Mô hình tóm lược như tìm ra các mối quan hệ giữa các trường, các mối
liên kết
- Mô hình kiểm tra sự thay đổi để phát hiện độ lệch trong dữ liệu và tri thức
Quy trình 4. Tổng hợp kết quả và đánh giá kết quả (Evaluation),
Mục đích của giai đoạn này là hiểu tri thức đã tìm được từ việc khai phá
dữ liệu đặc biệt là làm sáng tỏ và dự đoán chúng. Các kết quả khai phá sẽ được
tổng hợp dưới nhiều dạng khác nhau nhằm mục đích hỗ trợ ra quyết định. Nghĩa
là các thông tin hữu ích tìm được từ việc khai phá sẽ chuyển thành dữ liệu gần
gũi với người sử dụng hơn. Kinh nghiệm của các nhà khoa học cho thấy rằng
các mẫu hay các mô hình phát hiện từ việc khai phá dữ liệu không phải lúc nào
cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, mà quá trình khám
phá tri thức cần phải lặp đi lặp lại nhiều lần có sự điều chỉnh, bước sau dựa vào
kết quả của bước trước đó theo các tri thức khám phá được, lần sau hoàn chỉnh
hơn lần trước.
Các tri thức khám phá được sẽ được đánh giá theo những tiêu chí nhất
định. Để có thế đánh giá các luật được áp dụng trong qui trình khám phá tri
thức, người ta thường chia dữ liệu thành hai tập, huấn luyện trên tập thứ nhất và
kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này một số lần với các phần

trong cơ sở dữ liệu và đang bị dữ liệu (có khối lượng lớn) che khuất. Để trích rút
các mẫu, mô hình tiềm ẩn có tính “tri thức” ta phải tìm và áp dụng các phương
pháp, kỹ thuật khai phá sao cho các kỹ thuật và phương pháp này phải phù hợp
với tính chất, đặc trưng của dữ liệu và mục đích sử dụng. Tuy khai phá dữ liệu
chỉ là một bước trong quá trình khám phá tri thức từ dữ liệu nhưng nó lại là
bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình.
Tóm lại, có thể nói một cách khái quát, khai phá dữ liệu là một quá trình
tìm kiếm thông tin “tri thức” tiềm ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế,
có thể nói rằng hai thuật ngữ khám phá tri thức và khai phá dữ liệu là tương
đương nếu nói ở khía cạnh tổng quan, còn nếu xét ở một góc độ chi tiết thì Khai
phá dữ liệu là một giai đoạn có vai trò quan trọng trong quá trình khám phá tri
thức [5].
13
1.2.2. Mục tiêu của khai phá dữ liệu
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. Việc khai phá dữ liệu nhằm các
mục đích chính như sau:
- Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ
liệu lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu
hướng trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như:
các tổ chức, doanh nghiệp, nhà nghiên cứu,… nhằm đưa ra những quyết
định kịp thời, được định hướng trên những tri thức được khám phá mang
lại;
- Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá
trình xử lý dữ liệu để tìm ra tri thức.


Các chức năng của khai phá dữ liệu được thể hiện thông qua các bước
phân tích và xử lý dữ liệu bao gồm phân tích sự kết hợp và phân cụm, phân tích
và dự báo, Các phương pháp phân tích dùng để khai phá dữ liệu có thể được
xem xét dưới đây.

1.2.3.1 Phân tích luật kết hợp (Association Analysis)
Phân tích luật kết hợp là việc khám phá các luật kết hợp thể hiện các điều
kiện giá trị thuộc tính xảy ra thường xuyên cùng nhau trên tập dữ liệu đã cho.
Phân tích luật kết hợp thường sử dụng trong các lĩnh vực phân tích về thương
mại hay các giỏ hàng siêu thị (market basket) [5].

1.2.3.2. Phân cụm (Cluster Analysis)
Cách thức phân cụm dựa trên các đối tượng dữ liệu mà không cần tới
nhãn lớp đã biết. Các nhãn lớp không có mặt trong dữ liệu huấn luyện do chúng
không thể xác định trước được. Sự phân cụm được sử dụng để sinh ra các nhãn 15
một cách đơn điệu phục vụ cho khai phá. Các đối tượng được phân cụm dựa trên
nguyên tắc làm “tăng tối đa sự giống nhau của một lớp và làm giảm thiểu sự
khác nhau giữa các lớp” (maximizing the intraclass similarity and minimizing
the interclass similarity). Các cụm đối tượng hình thành sao cho các đối tượng
trong cùng một nhóm có sự giống nhau cao nhất còn các đối tượng khác nhau ở
các cụm khác thì không giống nhau. Mỗi cụm được hình thành có thể xem như
là một lớp các đối tượng, từ lớp các đối tượng thì các luật có thể được trích
chọn. Sự phân cụm cũng giúp cho các cách thức phân loại một cách dễ dàng và
các thông tin được thu thập thành một hệ thống có thứ bậc [5].

1.2.3.3. Phân lớp và dự đoán (Classification and Prediction)
Một trong các phương pháp phân tích dữ liệu dùng trong khai phá dữ liệu


Hình Quy trình phân lớp điển hình [9]

1.2.4. Phƣơng pháp khai phá dữ liệu
Hiện nay, có nhiều phương pháp khai phá dữ liệu được sử dụng phụ thuộc
vào cách tiếp cận như các phương pháp phân tích, tổng hợp dữ liệu lớn trên mô
hình thống kê, mạng neural, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức,…
Phương pháp khai phá dữ liệu so với một số phương pháp khai phá tri thức khác
có một số lợi thế là khai phá dữ liệu có thể sử dụng với các dữ liệu có nhiễu, dữ
liệu không đầy đủ hoặc dữ liệu biến đổi liên tục.
Trong phần này, trình bày một cách sơ lược về một số phương pháp khai
phá dữ liệu thông dụng đang được sử dụng, đó là: phương pháp khai phá dữ liệu
sử dụng phân cụm (data mining with Clustering), phương pháp khai phá dữ liệu
sử dụng luật kết hợp (data mining with Association Rules), phương pháp khái
phá dữ liệu sử dụng mạng neural (data mining with Neural Networks), phương
pháp khai phá dữ liệu sử dụng thuật giải di truyền (Genetic Algorithm-GA),
phương pháp khai phá dữ liệu sử dụng hệ chuyên gia, phương pháp khai phá dữ
liệu sử dụng thống kê. Các phương pháp này do không phải là trọng tâm của 17
luận văn nên chỉ được trình bày một cách sơ lược về ý tưởng chứ không đi sâu
vào chi tiết. Riêng phương pháp khai phá dữ liệu sử dụng cây quyết định (data
mining with Decision Tree) sẽ được trình bày chi tiết trong phần sau và đây
cũng là phần trọng tâm của luận văn.

1.2.4.1. Phương pháp hệ chuyên gia
Phương pháp này khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên
gia thường có chất lượng cao hơn nhiều so với các dữ liệu trong CSDL, và
chúng thường chỉ bao hàm được các trường hợp quan trọng. Hơn nữa các

Khai phá luật kết hợp được hình thành từ việc quan sát, thống kê mức độ
thường xuyên xảy ra đồng thời giữa các tập thuộc tính trong cơ sở dữ liệu 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 lớn.
Kết quả của kỹ thuật này là tập các luật kết hợp, chúng là một dạng biểu diễn tri
thức có thể được sử dụng cho các hoạt động khác

1.2.4.5. Phương pháp mạng neural
Kỹ thuật khai phá dữ liệu sử dụng mạng neural ngày càng phổ biến và
ứng dụng rộng rãi nhất là các ngành công nghiệp mở như nhận diện sổ sai tài
chính, chuẩn đoán bệnh trong y học, nhận dạng các khách hàng sử dụng dịch vụ
hoặc nhận dạng các thẻ giao dịch giả mạo,…[6]. Phương pháp này dựa trên nền
tảng toán học với khả năng huấn luyện được dựa theo mô hình thần kinh của con
người.
Khi cho một tập dữ liệu huấn luyện vào một hệ thống mạng, hệ thống
mạng sẽ tự huấn luyện, tự điều chỉnh qua từng lớp mạng và cho dữ liệu kết quả
đầu ra, các quá trình thực hiện có thể lặp đi lặp lại nhiều lần đến khi mạng học
theo tập dữ liệu thành công.
Huấn luyện dữ liệu bằng mạng neural sẽ cho ra các kết quả có ý nghĩa từ
cơ sở dữ liệu lớn ẩn chứa nhiều lỗi hoặc thiếu sót bên trong, tức là không phải 19
tốn thời gian gia công nhiều trước khi đưa vào cho mạng học, đây là một vấn đề
khó và phức tạp đối với các phương pháp khai thác khác.
Một mạng neural hoạt động tốt sẽ có khả năng tự “học” qua các lần huấn
luyện mà không cần sự can thiệp gì vào trong khi hệ thống đang làm việc, khả
năng tự điều chỉnh này là một điểm mạnh so với các phương pháp khác của
mạng nơron.
Các kết quả của mạng có khả năng tạo ra các mô hình dự báo với độ chính
xác cao và có khả năng phát hiện các xu hướng phức tạp mà con người cũng như

trực quan, dễ hiểu đối với người sử dụng. Tuy nhiên, nó đòi hỏi phải có một
không gian nhất định để mô tả tri thức trong giới hạn có thể hiểu được của con
người. Phương pháp này sẽ được trình bày chi tiết trong Chương 3. Một số
phương pháp xây dựng cây quyết định

1.2.5. Các kỹ thuật khai phá dữ liệu
Các kỹ thuật khai phá dữ liệu bao gồm các kỹ thuật chính như sau:
Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc
các đặc tính chung của dữ liệu trong CSDL hiện có. Các kỹ thuật này gồm có:
phân cụm (clustering), tóm tắt (summerization), trực quan hóa (visualiztion),
phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích
luật kết hợp (association rules)

1.2.5.1. Kỹ thuật khai phá dữ liệu dự đoán
Kỹ thuật này có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên
dữ liệu hiện thời. Các kỹ thuật này gồm có: phân lớp (classification), hồi quy
(regression)

1.2.5.2. Phân cụm dữ liệu
Mục tiêu chính của phương pháp 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 cụm sao cho các đối tượng thuộc cùng
một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không 21
tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy.
Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định
nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là
một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu
là học bằng ví dụ (learning by example). Trong phương pháp này bạn sẽ không

các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập
luật kết hợp tìm được.
Các luật kết hợp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu
của hình thành tri thức. Phương pháp 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 giải thuật khai phá
dữ liệu 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 phục.

1.2.5.5. Khai phá dữ liệu sử dụng mạng Neural
Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu
trúc toán học với khả năng học trên mô hình hệ thần kinh con người.
Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính
xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá
phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện
được.
Một trong ưu điểm phải kể đến của mạng Neural là khả năng tạo ra các
mô hình dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán
khác nhau, đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân
lớp, phân nhóm, mô hình hoá, dự báo…
Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những
nút đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các
hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số
của nó. 23
Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi
bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng

Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi
trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng
Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá 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.

1.2.5.7. Khai phá dữ liệu sử dụng cây quyết định
Phân lớp khai phá dữ liệu luật là một cách tiếp cận quan trọng trong qusa
trình khai phá dữ liệu, mục tiêu nhằm tạo ra một tập luật tương đối nhỏ có đọ
đúng đắn cao từ cơ sở dữ liệu lớn. Cây quyết định được cọi là phương pháp tiếp
cận truyền thống cho phép phân lớp luật [16]. Cây quyết định đưa ra cách tiếp
cận heuristic nhằm tìm kiếm các thuộc tính tốt nhất và dẫn đến kết quả cao nhất.
Tuy nhiên, cây quyết định có một số hạn chế khi triển khai lựa chọn thuộc tính
khi xây dựng cây. Các hạn chế của cây quyết định là các trường hợp phân rã và
tái tạo, vấn đề khi phân rã là khi cây quyết định cần phân chia dữ liệu nhiều lần
để có thể nhận biết được toàn bộ dữ liệu mẫu. Vấn đề khi tái tạo là một cây con
cần được xây dựng lại nhiều lần làm cho cây quyết định có độ sâu quá lớn và
khó hiểu.
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á.
Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân
chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây
quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một
cách tường tận. 25
Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó