ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HẠNH PHÚC ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG
KHAI THÁC CƠ SỞ DỮ LIỆU TÍCH HỢP
NGÀNH GIAO THÔNG VẬN TẢI

Ngành : CÔNG NGHỆ THÔNG TIN
Mã số : 1.01.10 LUẬN VĂN THẠC SĨ
Người hướng dẫn khoa học: T.S PHÙNG VĂN ỔN Hà Nội - 2006
LỜI CẢM ƠN
Tác giả xin chân thành cảm ơn các thầy giáo, cô giáo trong khoa Công
nghệ thông tin - Đại học Công nghệ, Đại học Quốc gia Hà nội, đã tận tâm
giảng dạy các kiến thức trong hai năm học qua cùng với sự cố gắng hết mực
của bản thân.
Đặc biệt tôi xin bày tỏ sự biết ơn sâu sắc đến thầy giáo Tiến sĩ Phùng
Văn Ổn, ngƣời đã tận tình hƣớng dẫn, động viên tôi thực hiện luận văn này.
Tác giả cũng xin chân thành cảm ơn Ban chủ nhiệm khoa Công nghệ
thông tin - Trƣờng đại học Hàng Hải, các bạn đồng nghiệp, các bạn trong lớp

3.8. Phân lớp (Classification) 16
3.9. Hồi quy (Regression) 17
3.10. Tổng hợp (Sumarization) 17
3.11. So sánh các nhiệm vụ phát hiện tri thức. 17
4. Phân lớp dữ liệu 20
4.1. Khái niệm về phân lớp 20
4.2. Ứng dụng của phân lớp 21
4.3. Các vấn đề nghiên cứu trong phân lớp 22
4.4. Các yêu cầu đối với bài toán phân lớp 23
5. Một số phƣơng pháp phân lớp 24
5.1. Phƣơng pháp phân hoạch 25
5.2. Phân lớp dựa trên cây quyết định [6] 25
5.3. Phƣơng pháp dựa vào mật độ 27
5.4. Phân lớp và mạng nơron nhân tạo 28
6. Đánh giá, nhận xét 30
CHƢƠNG 2 - ỨNG DỤNG LUẬT KẾT HỢP VÀO KHAI PHÁ DỮ LIỆU 31
1. Lý thuyết về luật kết hợp 31
1.1. Luật kết hợp 32

3
1.2. Một số tính chất của luật kết hợp [6] 35
1.3. Phân loại luật kết hợp 36
1.4. Đặc tả bài toán khai phá dữ liệu 39
2. Các đặc trƣng của luật kết hợp 40
2.1. Không gian tìm kiếm của luật 40
2.2. Độ hỗ trợ của luật 42
3. Một số giải thuật cơ bản khai phá các tập phổ biến 43
3.1. Giải thuật BFS (BFS – breadth first search) 44
3.2. Giải thuật DFS (Depth First Search) 53
3.3. Giải thuật DHP (Direct Hashing and Pruning) 54

confidence
Độ tin cậy
CSDL
Database
Cơ sở dữ liệu
DW
Data Warehouse
Kho dữ liệu
Item
item
Khoản mục
Itemset
itemset
Tập các khoản mục
K- itemset
K- itemset
Tập gồm K mục
KDD
Knowledge Discovery and Data
Mining
Kỹ thuật phát hiện tri thức và khai phá
dữ liệu
L
k
L
k

Tập các K - itemset phổ biến
Minconf
Minimum Confidence


DBSCAN
Density Based Spatial
Clustering of Application with
Noise
Thuật toán phân lớp dựa vào vị trí địa
phƣơng
DENCLUE
DENsity Based CLUstEring
Thuật toán phân lớp cơ bản (tổng quát)
TC

Tính chất
ADO
Activate X Data Object

DFS
Depth First Search
Tìm kiếm theo độ sâu
BFS
Breadth First Search
Tìm kiếm theo bề rộng
DHP
Direct Hashing and Pruning
Bảng băm trực tiếp và sự cắt tỉa
PHP
Perfect Hashing and Pruning
Bảng băm lý tƣởng và sự cắt tỉa
I/O
Input/Output

LUẬT KẾT HỢP VÀO KHAI PHÁ DỮ LIỆU
Trình bày các bài toán trong khai phá dữ liệu, phát hiện luật kết hợp
Khái niệm về luật kết hợp và các phƣơng pháp khai phá luật kết hợp.
Khai phá luật kết hợp dựa trên sự phân chia không gian tìm kiếm.
CHƢƠNG III - ỨNG DỤNG, THỬ NGHIỆM KHAI PHÁ DỮ LIỆU
TÍCH HỢP NGÀNH GIAO THÔNG VẬN TẢI

6
Nội dung của chƣơng là áp dụng kỹ thuật khai phá dữ liệu vào bài toán
thống kê về tình hình gia tăng các loại ôtô trong cả nƣớcvà dự báo về tốc độ
gia tăng của các loại ôtô.
Cuối cùng là kết luận lại những kết quả đạt đƣợc của đề tài và hƣớng
phát triển trong tƣơng lai.

7
CHƢƠNG 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT
HIỆN TRI THỨC
1. Tổ chức và khai thác cơ sở dữ liệu truyền thống
Việc dùng các phƣơng tiện tin học để tổ chức và khai thác cơ sở dữ liệu
(CSDL) đã đƣợc phát triển từ những năm 60 của thế kỉ trƣớc. Từ đó cho đến
nay, rất nhiều CSDL đã đƣợc tổ chức, phát triển và khai thác ở mọi quy mô
và các lĩnh vực hoạt động của con ngƣời và xã hội. Theo nhƣ đánh giá cho
thấy, lƣợng thông tin trên thế giới cứ sau 20 tháng lại tăng lên gấp đôi. Kích
thƣớc và số lƣợng CSDL thậm trí còn tăng nhanh hơn. Năm 1989, tổng số
CSDL trên thế giới vào khoảng 5 triệu, hầu hết là CSDL cỡ nhỏ đƣợc phát
triển trên DBaseIII. Với sự phát triển của công nghệ điện tử, sự phát triển
mạnh mẽ của công nghệ phần cứng tạo ra các bộ nhớ có dung lƣợng lớn, bộ
xử lý có tốc độ cao cùng với sự phát triển của các hệ thống viễn thông, ngƣời
ta đã và đang xây dựng các hệ thống thông tin nhằm tự động hoá mọi hoạt
động của con ngƣời. Điều này đã tạo ra một dòng dữ liệu tăng lên không

dữ liệu (data warehouse).
Nhƣng chỉ có kho dữ liệu thôi chƣa đủ để có tri thức. Các kho dữ liệu
đƣợc sử dụng theo một số cách nhƣ:
Theo cách khai thác truyền thống: tức là kho dữ liệu đƣợc sử dụng để
khai thác các thông tin bằng các công cụ truy vấn và báo cáo.
Các kho dữ liệu đƣợc sử dụng để hỗ trợ cho phân tích trực tuyến
(OLAP- OnLine Analytical Processing). Việc phân tích trực tuyến có khả
năng phân tích dữ liệu, xác định xem giả thuyết đúng hay sai. Tuy nhiên,
phân tích trực tuyến lại không có khả năng đƣa ra các giả thuyết.
Công nghệ khai phá dữ liệu (data mining) ra đời đáp ứng những đòi hỏi
trong khoa học cũng nhƣ trong hoạt động thực tiễn. Đây chính là một ứng
dụng chính của kho dữ liệu.
2. Tổng quan về kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD -
Knowledge Discovery and Data Mining)
2.1. Phát hiện tri thức và khai phá dữ liệu là gì?
Nếu cho rằng các điện tử và các sóng điện tử chính là bản chất của công
nghệ điện tử truyền thống thì dữ liệu, thông tin và tri thức hiện đang là tiêu
điểm của một lĩnh vực mới trong nghiên cứu và ứng dụng về phát hiện tri
thức (Knowledge Discovery) và khai phá dữ liệu (Data Mining).
Thông thƣờng chúng ta coi dữ liệu nhƣ một dãy các bit, hoặc các số và
các ký hiệu, hoặc các “đối tƣợng” với một ý nghĩa nào đó khi đƣợc gửi cho
một chƣơng trình dƣới một dạng nhất định. Chúng ta sử dụng các bit để đo
lƣờng các thông tin và xem nó nhƣ là các dữ liệu đã đƣợc lọc bỏ các dƣ thừa,
đƣợc rút gọn tới mức tối thiểu để đặc trƣng một cách cơ bản cho dữ liệu.
Chúng ta có thể xem tri thức nhƣ là các thông tin tích hợp, bao gồm các sự
kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể đƣợc hiểu ra,

9
có thể đƣợc phát hiện, hoặc có thể đƣợc học. Nói cách khác, tri thức có thể
đƣợc coi là dữ liệu có độ trừu tƣợng và tổ chức cao.

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.
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 và/hoặc 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?
Bƣớc thứ tƣ: 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. 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.
Tóm lại: KDD là một quá trình chiết xuất ra tri thức từ kho dữ liệu mà
trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
2.3. Các phƣơng pháp khai phá dữ liệu [7]
KDD bao gồm hai yếu tố quan trọng không thể thiếu đƣợc là Dự đoán
(Prediction) và Mô tả (Description)
Dự đoán: Đòi hỏi sử dụng một vài biến hoặc trƣờng để dự đoán thông tin
tiềm ẩn hoặc một giá trị tƣơng lai của một biến thuộc tính mà ta quan tâm đến.
Mô tả: Tập trung là nổi bật lên mô hình kết quả mà con ngƣời có thể
hiểu sâu về thông tin dữ liệu.
Với hai đích chính đã nêu ở trên, ngƣời ta thƣờng sử dụng các phƣơng
pháp sau cho khai phá dữ liệu:
- Phân lớp, phân loại (Classification): Là việc học một hàm ánh xạ từ
một mẫu dữ liệu vào một trong số các lớp đã đƣợc xác định trƣớc đó.
- Hồi qui (Regression): Là việc học một hàm ánh xạ từ một mẫu dữ liệu
thành một biến dự đoán có giá trị thực.

11
- 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.
- Tổng hợp (Summarization): Là công việc lên quan đến các phƣơng

12
2.4. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ
liệu [7]
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều
lĩnh vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán
song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ
liệu Đặc biệt Phát hiện tri thức và 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 mẫu, luật Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân
tích trực tuyến (OLAP) cũng liên quan rất chặt chẽ với Phát hiện tri thức và
khai phá dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng trong thực tế. Một số ứng dụng điển
hình nhƣ:
Bảo hiểm, tài chính và thị trƣờng chứng khoán: Phân tích tình hình tài
chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng khoán.
Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận,
Phân tích dữ liệu và hỗ trợ ra quyết định.
Điều trị y học và chăm sóc y tế: Một số thông tin về chuẩn đoán bệnh
lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu
chứng bệnh, chuẩn đoán và phƣơng pháp điều trị (chế độ dinh dƣỡng,
thuốc, )
Sản xuất và chế biến: Quy trình, phƣơng pháp chế biến và xử lý sự cố.
Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm
tắt văn bản,
Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học,
tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một
số bệnh di truyền,
Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát
lỗi, sự cố, chất lƣợng dịch vụ,
3. Các nhiệm vụ trong khai phá dữ liệu

Các hệ thống hƣớng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán
phát hiện tri thức trong CSDL chủ yếu phục vụ sự phân bổ dữ liệu trong trạng
thái hiện thời của CSDL;
Các hệ thống lai kết hợp các đặc tính của cả hệ thống hƣớng truy vấn và
hƣớng dữ liệu.
Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện
tri thức khác, là việc chọn các thuộc tính để tổng hợp một SQO cần phải tính
đến chi phí liên quan nhƣ dùng phƣơng pháp truy cập nào và sơ đồ chỉ số
trong hệ quản trị CSDL. Việc này là cần thiết để tiết kiệm thời gian xử lý

14
truy vấn. Một thuật toán phát hiện tri thức trong CSDL loại này đòi hỏi phải
xem xét tối ƣu chi phí.
3.2. Phát hiện sự phụ thuộc CSDL (Database Dependencies)
Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong
CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này
thƣờng đƣợc thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn.
Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu
này. Sự phụ thuộc CSDL đƣợc sử dụng trong thiết kế và duy trì một CSDL.
Phƣơng pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu
nhiệm vụ của Khai phá dữ liệu.
3.3. Phát hiện sự sai lệch (Deviation)
Nhiệm vụ này nhằm phát hiện sự sai lệch đáng kể giữa nội dung của tập
con dữ liệu thực và nội dung mong đợi. Hai mô hình sai lệch hay dùng là mô
hình sai lệch theo thời gian và sai lệch nhóm. Sai lệch theo thời gian là sự
thay đổi có ý nghĩa của dữ liệu theo thời gian. Sai lệch theo nhóm là sự khác
nhau không chờ đợi giữa dữ liệu trong hai tập con dữ liệu, ở đây tính đến cả
trƣờng hợp tập con này thuộc trong tập con kia, nghĩa là xác định dữ liệu
trong một nhóm con của đối tƣợng có khác đáng kể so với toàn bộ đối tƣợng
không. Theo cách này, các sai sót dữ liệu hay sự sai lệch so với giá trị thông

Trên thực tế, tiên đề thƣờng là nhóm các giá trị thuộc tính và kết luận chỉ là
một giá trị tuộc tính. Lƣu ý là những luật này không phải hoàn toàn giống với
sự phụ thuộc CSDL đƣợc nêu ở phần II.2. Hơn nữa, hệ thống có thể phát
hiện các luật với phần kết luận nhiều thuộc tính. Điều này khác với luật phân
lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do ngƣời dùng chỉ
ra trong kết luận.
Quan hệ phụ thuộc cũng có thể biểu diễn dƣới dạng Bayes. Đó là một
đồ thị có hƣớng, không chu trình. Các nút biểu diễn các thuộc tính và trọng
số của cung biểu diễn độ mạnh của sự phụ thuộc giữa các nút đó.
3.6. Mô hình hoá nhân quả (Causation Modeling)
Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong
thuộc tính. Các luật nhân quả cũng là các luật “nếu - thì” giống các luật phụ
thuộc, nhƣng mạnh hơn. Luật phụ thuộc đơn giản chỉ ra một mối tƣơng hỗ
giữa tiên đề và kết luận của luật mà không có ý nghĩa nhân quả trong quan hệ
này. Do đó, cả tiên đề và kết luận có thể quan hệ dƣới sự ảnh hƣởng của một
biến thứ ba, tức là một thuộc tính hoặc có ở trong tiên đề hoặc có ở trong kết
luận. Luật nhân quả không chỉ chỉ ra mối tƣơng quan giữa tiên đề và kết luận
mà còn cho biết tiên đề thực sự tạo ra kết luận và mối quan hệ giữa hai thành
phần này là trực tiếp. Tập các mối quan hệ nhân quả có thể đƣợc biểu diến
bằng đồ thị nhân quả.

16
Thuật toán phát hiện các luật nhân quả CAUDISCO áp dụng các phép
kiểm tra sự độc lập thống kê của từng cặp thuộc tính. Sau đó, đối với các
thuộc tính phụ thuộc lẫn nhau, thuật toán sẽ xác định mối quan hệ có là xác
thực, tiềm năng hay chỉ là một liên kết giả tạo, không phụ thuộc vào tập các
điều kiện thoả mãn bởi quan hệ nhân quả.
Các quan hệ nhân quả cần phụ thuộc vào thời gian theo nghĩa là nguyên
nhân trƣớc kết quả (kết luận). Nguyên nhân và kết quả đều có ít nhất một sự
kiện thời gian đi kèm và thời gian của kết quả phải đi sau thời gian của

trong kết luận”.
3.9. Hồi quy (Regression)
Về khái niệm, nhiệm vụ hồi quy tƣơng tự nhƣ phân lớp. Điểm khác
nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải rời rạc.
Việc dự báo các giá trị số thƣờng đƣợc làm bởi các phƣơng pháp thống kê cổ
điển, chẳng hạn nhƣ hồi quy tuyến tính. Tuy nhiên, các phƣơng pháp mô
hình hoá cũng đƣợc sử dụng, chẳng hạn nhƣ cây quyết định, trong đó nút lá là
mô hình tuyến tính phát sinh tập các lớp giả (pseudo - class) có giá trị thuộc
tính đích tƣơng tự nhau, sau đó sử dụng phƣơng pháp quy nạp để thay thế các
lớp trong luật quy nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các bộ dữ
liệu theo luật.
3.10. Tổng hợp (Sumarization)
Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trƣng cho một lớp.
Mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả
(hoặc hầu hết) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.
Các mô tả đặc trƣng thể hiện dƣới dạng luật có dạng sau: ”nếu một bộ dữ
liệu thuộc về một lớp đã chỉ ra trong tiên đề, thì bộ dữ liệu đó có tất cả các
thuộc tính đã nêu trong kết luận”. Cần lƣu ý là các luật này có những đặc
trƣng khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho một lớp chỉ
sản sinh khi các bộ dữ liệu đã thuộc về lớp đó.
3.11. So sánh các nhiệm vụ phát hiện tri thức.
Điểm giống và khác giữa các nhiệm vụ phát hiện tri thức đƣợc tóm tắt
trong bảng sau:
Nhiệm vụ
Kiểu phát hiện
Mục đích
Kiểu dự báo
SQO
Hƣớng hệ quản tri CSDL
Tối ƣu truy vấn

Dự báo
Có học
Hồi quy
Mục đích chung
Dự báo
Có học
Tổng hợp
Mục đích chung
Dự báo
Có học
Bảng 1: So sánh các nhiệm vụ phát hiện tri thức
Trong bảng này, cột đầu tiên chỉ ra nhiệm vụ phát hiện tri thức. Cột thứ
hai chỉ ra kiểu tri thức đƣợc phát hiện. Các kiểu có thể là hƣớng hệ quản trị
CSDL (nhƣ các luật SQO) hoặc phụ thuộc CSDL hoặc là mục đích chung (tức
là các nhiệm vụ phát hiện bổ trợ khác). Tri thức hƣớng hệ quản trị CSDL
thƣờng dùng trong thiết kế và giao dịch của một CSDL. Tuy nhiên, tri thức
hƣớng hệ quản trị CSDL cũng có thể dùng cho việc kiểm tra các luật tối ƣu
truy vấn ngữ nghĩa để cải thiện việc tìm hiểu ứng dụng. Trong khi tri thức
theo kiểu mục đích chung có thể đƣợc sử dụng theo các mục đích khác nhau
tuỳ thuộc vào nhu cầu của ngƣời dùng theo nghĩa mờ và nó có thể sử dụng
hiệu quả trong hệ quản trị CSDL. Tuy vậy, điểm khác biệt quan trọng là tri
thức hƣớng hệ quản trị CSDL yêu cầu độ chính xác cao hơn so với tri thức
theo mục đích chung. Cột thứ ba trong bảng chỉ ra mục đích của việc phát
hiện tri thức. Cột này xuất phát từ cột hai. Mục đích chính của các tri thức
hƣớng hệ quản trị CSDL là khá cụ thể: Tối ƣu truy vấn (trong trƣờng hợp
SQO) và thiết kế, duy trì CSDL (trong trƣờng hợp sự phụ thuộc CSDL). Các
tri thức theo kiểu mục đích chung thƣờng đƣợc dùng co một sự kết hợp các
mục đích dự báo, mô tả và xác định trội. Dự báo liên quan đến xác định giá trị
của các tri thức trên cơ sở xác định giá trị của các thuộc tính khác. Kỹ thuật
đặc trƣng là phân lớp và hồi quy. Tuy nhiên, dự báo cũng dựa trên quan hệ

hoàn toàn đúng với mục tiêu dự báo nhƣng có thể nói nó liên quan đến việc
phát hiện không có học.
Nhiệm vụ phân lớp và hồi quy liên quan đến dự báo nhiều - một trong đó
giá trị của nhiều thuộc tính có thể đƣợc sử dụng để dự báo giá trị của một
thuộc tính do ngƣời dùng xác định trƣớc. Đối với nhiệm vụ tổng hợp, từ lớp
của một bộ dữ liệu, chúng ta có thể dự báo giá trị (hoặc khoảng giá trị, giá trị
trung bình, ) của các thuộc tính khác. Tri thức đƣợc phát hiện phải bao gồm
quan hệ đó. Do vậy, tính tự chủ của hệ thống chỉ ở chỗ xác định các thuộc
liên quan đến giá trị thuộc tính đích và có hạn chế hơn so với các nhiệm vụ
không học. Tuy nhiên, các nhiệm vụ không học có thể chuyển thành có học.
Các đặc tính khác của phát hiện tri thức nhƣ tính thông minh và tính hữu
dụng không bao gồm trong bảng trên bởi vì chúng mang tính chủ quanvà thay
đổi lớn trong mỗi nhiệm vụ của từng kĩnh vực cụ thể.
Phát hiện tri thức hƣớng CSDL (SQO và sự phụ thuộc CSDL) có độ
chính xác cao. Đây là điểm khác biệt quan trọng so với các đòi hỏi của các
nhiệm vụ phát hiện tri thức khác. Nhiệm vụ phát hiện sự sai lệch liên quan

20
đến phát hiện tri thức với mức ý nghĩa do ngƣời dùng xác định. Nhiệm vụ
phát hiện liên kết cũng nhƣ thế với ngƣỡng tin cậy (ngƣỡng confidence) và
tần suất tƣơng đối (ngƣỡng hỗ trợ - support). Nhiệm vụ tổng hợp liên quan
đến phát hiện tri thức có tính phổ biến cao tức là luật đƣợc phát hiện phải bao
hàm một số dữ liệu (mà các nhiệm vụ khác nhƣ phân lớp không đòi hỏi nhƣ
vậy).
Các nhiệm vụ nhƣ phát hiện sự phụ thuộc, nhân quả, phân lớp và hồi quy
chủ yếu liên quan đến phát hiện tri thức có độ chính xác cao.
4. Phân lớp dữ liệu
4.1. Khái niệm về phân lớp
Phân lớp (classification) là quá trình nhóm một tập các đối tƣợng vật lý
hoặc trừu tƣợng thành các nhóm hay các đối tƣợng tƣơng tự nhau. Một lớp

liệu huấn luyện để tránh vấn đề Over-fitting có thể xảy ra.
4.2. Ứng dụng của phân lớp
Việc phân lớp đã đƣợc sử dụng rộng rãi trong các ứng dụng của nhiều
lĩnh vực, bao gồm nhận dạng mẫu, phân tích dữ liệu, phân tích thị trƣờng,
Bằng cách phân lớp, chúng ta có thể thấy các vùng đầy đặc hoặc thƣa thớt do
vậy phát hiện đƣợc sự phân bố các mẫu và có thể thấy đƣợc sự tƣơng quan
giữa những thuộc tính dữ liệu. Trong kinh doanh, phân lớp có thể giúp nhà
nghiên cứu thị trƣờng phát hiện đƣợc các nhóm khách hàng khác nhau và đặc
tính của từng nhóm khách hàng dựa vào dữ liệu mua bán. Trong sinh học,
phân lớp đƣợc dùng để chia nhóm các loài động và thực vật, phân loại gen có
Xây dựng mô hình
Sử dụng mô hình để dự
báo
Dữ liệu huấn
luyện
Bộ phân loại
(mô hình)
Dữ liệu
kiểm tra
Dữ liệu
chƣa biết

22
chức năng tƣơng tự nhau và có những thông tin chi tiết hơn về cấu trúc của
các vùng dân cƣ. Phân lớp cũng giúp cho việc nhận dạng các mẫu đất giống
nhau dựa trên cơ sở dữ liệu quan sát trái đất, phân chia các nhóm nhà trong
thành phố theo các tiêu chí nhƣ giá trị, vị trí địa lý của ngôi nhà. Phân lớp
còn đƣợc sử dụng để phân chia các nhóm tài liệu Web dựa vào nội dung
thông tin.
Với vai trò là chức năng trong khai phá dữ liệu, phân tích phân lớp có

Phân lớp luôn là vấn đề nghiên cứu với nhiều thách thức bởi các ứng
dụng của nó thƣờng đòi hỏi rất nhiều các yêu cầu đặc biệt. Sau đây là các yêu
cầu chính đối với phân lớp trong khai phá dữ liệu:
+ Tính tuyến tính (scalability): nhiều thuật toán làm việc tốt trên tập dữ
liệu nhỏ có ít hơn 200 đối tƣợng dữ liệu, tuy nhiên các CSDL lớn có thể có
hàng triệu đối tƣợng. Phân lớp tập các dữ liệu lớn có thể dẫn đến kết quả
không mong muốn nhƣ có thời gian thực hiện quá lâu hoặc dữ liệu đầu ra
không phù hợp. Do vậy các thuật toán cần có tính tuyến tính.
+ Khả năng làm việc với nhiều loại dữ liệu khác nhau: nhiều thuật toán
đƣợc xây dựng chỉ thực hiện với dữ liệu số. Tuy nhiên, các ứng dụng có thể
yêu cầu phân lớp với nhiều dạng dữ liệu khác nhau nhƣ là nhị phân, dữ liệu
phân loại, dữ liệu thứ tự hoặc dữ liệu hỗn hợp theo nhiều kiểu.
+ Khả năng phát hiện các lớp với hình dạng bất kỳ: nhiều thuật toán xác
định lớp chỉ dựa vào độ đo khoảng cách Euclidean hoặc Manhattan. Các
thuật toán dựa vào độ đo này có xu hƣớng tìm các lớp có hình cầu và có sự
tƣơng tự nhau về kích thƣớc và mật độ. Tuy nhiên, một lớp lại có thể có hình
dạng bất kỳ. Do vậy, việc phát hiện các thuật toán có khả năng phát hiện các
lớp với hình dạng bất kỳ là rất quan trọng.
+ Tối thiểu các tham số đầu vào: nhiều thuật toán phân lớp yêu cầu
ngƣời sử dụng nhập vào một số các tham số nhất định để thực hiện việc phân
lớp (ví dụ nhƣ số lớp mong muốn). Các tham số thƣờng rất khó xác định, đặc
biệt với các tập dữ liệu có các đối tƣợng nhiều chiều. Điều này không chỉ gây
khó khăn cho ngƣời sử dụng mà còn cho ra chất lƣợng các lớp khác nhau.
+ Khả năng làm việc với các dữ liệu nhiễu: Hầu hết các dữ liệu thực đề
có dữ liệu không đầy đủ, không biết rõ hoặc dữ liệu lỗi. Một số thuật toán
nhạy cảm với các dữ liệu nhƣ vậy và có thể dẫn đến phân lớp có chất lƣợng
kém.
+ Không phụ thuộc vào thứ tự của các bản ghi đầu vào: Một số thuật
toán phân lớp là rất nhạy cảm với thứ tự dữ liệu đầu vào. Cùng một tập dữ
liệu, khi biểu diễn với thứ tự khác nhau đối với các thuật toán có thể tạo ra