khai phá dữ liệu bằng cây quyết định.
Information
MỤC LỤC
LỜI MỞ ĐẦU
Chương 1: Tổng quan về khai phá dữ liệu
1.1. Khám phá tri thức và khai phá dữ liệu là gì?
1.2. Quá trình phát hiện tri thức
1.2.1. Hình thành và định nghĩa bài toán
1.2.2. Thu thập và tiền xử lý dữ liệu
1.2.3. Khai phá dữ liệu và rút ra các tri thức
1.2.4. Phân tích và kiểm định kết quả
1.2.5. Sử dụng các tri thức phát hiện được
1.3. Quá trình khai phá dữ liệu
1.3.1. Gom dữ liệu (gatherin)
1.3.2. Trích lọc dữ liệu (selection)
1.3.3. Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing).
1.3.4. Chuyển đổi dữ liệu (transformation)
1.3.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery)
1.3.6. Đánh giá kết quả mẫu (evaluation of result )
1.4. Chức năng của khai phá dữ liệu
1.5. Các kỹ thuật khai phá dữ liệu
1.5.1. Phân lớp dữ liệu:
1.5.2. Phân cụm dữ liệu:
1.5.3. Khai phá luật kết hợp:
1.5.4. Hồi quy:
1.5.5. Giải thuật di truyền:
1.5.6. Mạng nơron:
1.5.7. Cây quyết định.
1.6. Các dạng dữ liệu có thể khai phá được
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

1.2.1.Hình thành và định nghĩa bài toán............................................................................7
1.2.2.Thu thập và tiền xử lý dữ liệu...................................................................................7
1.2.3.Khai phá dữ liệu và rút ra các tri thức......................................................................8
1.2.4.Phân tích và kiểm định kết quả ................................................................................8
1.2.5.Sử dụng các tri thức phát hiện được.........................................................................8
1.3.Quá trình khai phá dữ liệu................................................................................................9
1.3.1.Gom dữ liệu (gatherin)..............................................................................................9
1.3.2.Trích lọc dữ liệu (selection)......................................................................................9
1.3.3.Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing).......................................9
1.3.4.Chuyển đổi dữ liệu (transformation)......................................................................10
1.3.5.Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery) .......................10
1.3.6.Đánh giá kết quả mẫu (evaluation of result ).........................................................10
1.4.Chức năng của khai phá dữ liệu.....................................................................................10
1.5.Các kỹ thuật khai phá dữ liệu.........................................................................................11
1.5.1.Phân lớp dữ liệu: ....................................................................................................11
1.5.2.Phân cụm dữ liệu:....................................................................................................11
1.5.3.Khai phá luật kết hợp: ............................................................................................11
1.5.4.Hồi quy:...................................................................................................................12
1.5.5.Giải thuật di truyền:.................................................................................................12
1.5.6.Mạng nơron: ...........................................................................................................12
1.5.7.Cây quyết định........................................................................................................12
1.6.Các dạng dữ liệu có thể khai phá được..........................................................................13
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...........13
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.........................13
1.7.2.Ứng dụng của khai phá dữ liệu...............................................................................13
1.8.Các thách thức và hướng phát triển của phát hiện tri thức và khai phá dữ liệu............14
Chương 2: Khai phá dữ liệu bằng cây quyết định...................................................................15
2.1.Cây quyết định................................................................................................................15
2.1.1.Định nghĩa cây quyết định......................................................................................15
2.1.2.Ưu điểm của cây quyết định...................................................................................16

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 ứng được thực tế đã
làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và
khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining).
Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau trên thế giới, tại Việt Nam kỹ thuật này còn
tương đối mới mẻ tuy nhiên cũng đang được nghiên cứu và bắt đầu đưa vào một số
ứng dụng thực tế. Vì vậy, hiện nay ở nước ta vấn đề phát hiện tri thức và khai phá dữ
liệu đang thu hút được sự quan tâm của nhiều người và nhiều công ty phát triển ứng
dụng công nghệ thông tin. Trong phạm vi đề tài nghiên cứu khoa học này của em, em
sẽ trình bày những nội dung sau:
Chương 1: Tìm hiểu những kiến thức tổng quan về khám phá tri thức và khai
phá dữ liệu.
Chương 2: Nghiên cứu kỹ thuật khai phá dữ liệu bằng cây quyết định.
Chương 3: Xây dựng ứng dụng demo cho kỹ thuật khai phá dữ liệu bằng cây
quyết định
Chương 1: Tổng quan về khai phá dữ liệu
1.1. Khám phá tri thức và khai phá dữ liệu là gì?
5
Phát hiện tri thức (Knowledge Discovery ) trong các cơ sở dữ liệu là một qui
trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức,
mới, khả ích, và có thể hiểu được [4].
Còn khai thác dữ liệu (data mining) là một ngữ tương đối mới, nó ra đời vào
khoảng những năm cuối của của thập kỷ 1980. Có rất nhiều định nghĩa khác nhau về
khai phá dữ liệu. Giáo sư Tom Mitchell đã đưa ra định nghĩa của khai phá dữ liệu
như sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc
và cải thiện những quyết định trong tương lai.”. Với một cách tiếp cận ứng dụng hơn,
tiến sĩ Fayyad đã phát biểu: ”Khai phá dữ liệu thường được xem là việc khám phá tri

đi. Kỹ thuật này không được sử dụng cho các tác vụ có quan
tâm đến phân bố dữ liệu.
7
3. Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung
sẽ bị loại đi khỏi dữ liệu.
4. Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá.
5. Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị
rời rạc.
6. Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có.
7. Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt.
1.2.3.Khai phá dữ liệu và rút ra các tri thức
Đây là bước quan trọng nhất trong tiến trình khám phá tri thức. Kết quả
của bước này là trích ra được các mẫu và/hoặc các mô hình ẩn dưới các dữ liệu.
Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ
thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu được nảy
sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài
trường hợp trong cơ sở dữ liệu.
1.2.4. Phân tích và kiểm định kết quả
Bước thứ tư là hiểu các tri thức đã tìm được, đặc biệt là làm sáng tỏ các
mô tả và dự đoán. Trong bước này, kết quả tìm được sẽ được biến đổi sang
dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho người dùng.
1.2.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 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 thức

1.3.4. Chuyển đổi dữ liệu (transformation)
Trong giai đoạn này, dữ liệu có thể được tổ chức và sử dụng lại. Mục
đích của việc chuyển đổi dữ liệu là làm cho dữ liệu phù hợp hơn với mục đích
khai phá dữ liệu.
1.3.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery)
Đây là bước tư duy trong khai phá dữ liệu. Ở trong giai đoạn này 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ự.
1.3.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.
1.4. Chức năng của khai phá dữ liệu
Khai phá dữ liệu có hai chức năng cơ bản đó là: chức năng dự đoán và chức
năng mô tả.
10
1.5. Các kỹ thuật khai phá dữ liệu
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

1.5.6. Mạng nơron:
Đây là một trong những kỹ thuật khai phá dữ liệu được ứng dụng phổ
biến hiện nay. Kỹ thuật này phát triển dựa trên một nền tảng toán học vững
vàng, khả năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh
trung ương của con người.
Kết quả mà mạng nơron học được có khả năng tạo ra các mô hình dự
báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra
được các xu hướng phức tạp mà kỹ thuật thông thường khác khó có thể phát
hiện ra được. Tuy nhiên phương pháp mạng nơ ron rất phức tạp và quá trình
tiến hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều dữ
liệu, nhiều lần kiểm tra thử nghiệm.
1.5.7. Cây quyết định.
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
12
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