i
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

ĐÀO THỊ THÚY QUỲNH

NGHIÊN CỨU PHƢƠNG PHÁP TÌM TẬP THƢỜNG XUYÊN SỬ DỤNG
CÂY TIỀN TỐ NÉN

THÁI NGUYÊN 2015


ii
LỜI CẢM ƠN
Luận văn này đƣợc hoàn thành với sự hƣớng dẫn tận tình của PGS.TS Ngô
Quốc Tạo – Viên Công nghệ thông tin - Viện Hàn Lâm Khoa học Việt Nam. Trƣớc
tiên tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới PGS.TS Ngô Quốc Tạo ngƣời
đã tận tình hƣớng dẫn, động viên giúp đỡ tôi trong suốt thời gian thực hiện luận
văn. Tôi cũng xin chân thành cảm ơn các thầy cô trong trƣờng Công Nghệ thông tin
và Truyền thông – Đại học Thái Nguyên, tạo điều kiện thuận lợi cho tôi hoàn thành
tốt khóa học.
Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học
CHK12A đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh
nghiệm học tập, công tác trong suốt khoá học.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, ngƣời thân, bạn bè đã
động viên, khuyến khích và hỗ trợ cần thiết để tôi hoàn thành luận văn này.
Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót,
kính mong đƣợc sự chỉ dẫn của các quý thầy cô và các bạn.
Thái Nguyên, ngày 16 tháng 05 năm 2015
Ngƣời viết

Đào Thị Thúy Quỳnh


iii
LỜI CAM ĐOAN

cảm ơn và các thông tin trích
dẫn trong luận văn đã đƣợc chỉ rõ nguồn gốc.
Thái Nguyên, ngày 16 tháng 05 năm 2015
Ngƣời cam đoan

Đào Thị Thúy Quỳnh


iv
BẢNG KÝ HIỆU CHỮ VIẾT TẮT

TT

Ký hiệu viết tắt

Giải thích

1

CNTT

Công nghệ thông tin

2


KPDL

Khai phá dữ liệu

3

CSDL

Cơ sở dữ liệu

4

KDD

5

ITL

Item - TransLink

6

CT-ITL

Compressed Tree - Item TransLink

7

CFP


Compressed FP - Tree

8

FP - Tree

Frequent pattern Tree

9

D = {T1, T2,…, Tn}.

Tập hợp n giao dịch

10

I= {i1, i2,…,im}

Tập hợp m phầntử trong CSDL

11

Minsup

Ngƣỡng độ hỗ trợ

12

Minconf


Ngƣỡng độ tin cậy tối thiểu

13

Conditional pattern - base

Cơ sở mẫu có điều kiện

14

Conditional FP-Tree

Cây FP có điều kiện

Khám phá tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Databases)


v
DANH MỤC CÁC BẢNG
Bảng 2.1. Biểu diễn cơ sở dữ liệu giao dịch ngang ..................................................18
Bảng 2.2. Biểu diễn cơ sở dữ liệu giao dịch dọc ......................................................19
Bảng 2.3. Biểu diễn cơ sở dữ liệu giao dịch ma trận ................................................19
Bảng 2.4. Một số hóa đơn bán hàng tại siêu thị ........................................................24
Bảng 3.1. Sắp xếp và ánh xạ khoản mục 1 đối tƣợng thƣờng xuyên ........................45


vi
DANH MỤC CÁC HÌNH

Hình 1.1. Quy trình khám phá tri thức từ cơ sở dữ liệu..............................................5
Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu.....................................................7
Hình 2.1: So sánh thời gian thực thi với số lƣợng giao dịch khác nhau ...................36
Hình 3.1. Cơ sở dữ liệu mẫu .....................................................................................38
Hình 3.2a. Cây tiền tố hoành chỉnh các đối tƣợng 1-4 .............................................39
Hình 3.2b. Cây giao dịch...........................................................................................39
Hình 3.3 Cấu trúc dữ liệu Item-TransLink (ITL)......................................................40
Hình 3.4a. Những cây con giống hệt nhau trong cây tiền tố .....................................41
Hình 3.4b. Cây tiền tố nén ........................................................................................41
Hình 3.5. Cây giao dịch nén ......................................................................................46
Hình 3.6. Cấu trúc Item - TransLink cải tiến ............................................................47
Hình 3.7.Khai phá đệ quy tập khoản mục thƣờng xuyên ..........................................48
Hình 3.8. Ví dụ minh họa xây dựng cây CFP-Tree ................................................53
Hình 3.9. Khai phá CFP-Tree ...................................................................................57
Hình 3.10. Biên dịch CFP_Tree trên VC6 ................................................................68
Hình 3.11. Sử dụng CFP-Tree qua tham số dòng lệnh .............................................69
Hình 3.12. Gọi CFP-Tree qua giao diện Window Form ...........................................70
Hình 3.13. Xem kết quả xử lý ...................................................................................71
Hình 3.14. Tổ chức các file để khai phá dữ liệu .......................................................71


vii
MỤC LỤC
LỜI CẢM ƠN……………………………………………………………………..…I
LỜI CAM
ĐOAN………………………………………………………………...…III
BẢNG KÝ HIỆU CHỮ VIẾT TẮT …………………………………………….....IV
DANH MỤC CÁC BẢNG………………………………………………………...IV
DANH MỤC CÁC HÌNH…………………………………………………………..V
MỞ ĐẦU .....................................................................................................................1

CHƢƠNG 1: TỔNG QUAN VỀ KHÁI PHÁ DỮ LIỆU ...........................................4
1.1. Giới thiệu tổng quan về khai phá dữ liệu. ............................................................4
1.2. Kiến trúc của hệ thống khai phá dữ liệu ..............................................................7
1.2.1.Một số khái niệm về khai phá dữ liệu ............................................................8
1.2.2. Nhiệm vụ chính của khai phá dữ liệu............................................................8
1.3. Một số phƣơng pháp khai phá dữ liệu................................................................10
1.3.1.Phƣơng pháp suy diễn / quy nạp ..................................................................10
1.3.2.Phƣơng pháp ứng dụng K-láng giềng gần ...................................................11
1.3.3.Phƣơng pháp sử dụng cây quyết định và luật ..............................................12
1.3.4.Phƣơng pháp phát hiện luật kết hợp .............................................................12
1.4. Những khó khăn trong khai phá dữ liệu.............................................................14
1.5. Một số ứng dụng khai phá dữ liệu .....................................................................17
CHƢƠNG 2: KHAI PHÁ TẬP THƢỜNG XUYÊN................................................18
2.1. Bài toán khai phá tập mục thƣờng xuyên ...........................................................18
2.1.1. Khái niệm Tập mục thƣờng xuyên ..............................................................18
2.1.2. Tập mục thƣờng xuyên và luật kết hợp .......................................................20
.....................................................................21
2.1.4. Một số tính chất của tập mục thƣờng xuyên ...............................................21
2.1.5. Hƣớng tiếp cận khai phá tập mục thƣờng xuyên ........................................21
2.2. Một số thuật toán khai phá tập mục thƣờng xuyên ............................................22


viii
2.2.1. Thuật toán Apriori .......................................................................................22
2.2.2. Thuật toán FP-Growth.................................................................................27
CHƢƠNG 3: THUẬT TOÁN KHAI PHÁ TẬP THƢỜNG XUYÊN SỬ DỤNG
CÂY TIỀN TỐ NÉN .................................................................................................38
3.1. Thuật toán khai phá tập thƣờng xuyên sử dụng cấu trúc dữ liệu và thuật toán
CT-ITL ......................................................................................................................38
3.1.1. Cấu trúc dữ liệu Item - TransLink...............................................................38

3.1.2.Cấu trúc dữ liệu và thuật toán CT-ITL.........................................................40
3.1.3. Thực hiện từng bƣớc thuật toán khai phá tập thƣờng xuyên sử dụng cấu
trúc CT-ITL ...........................................................................................................45
3.2. Thuật toán khai phá tập thƣờng xuyên sử dụng cây CFP – Tree .......................49
3.2.1. Cấu trúc cây CFP – Tree .............................................................................49
3.2.2. Thuật toán khai phá tập thƣờng xuyên trên cây CFP – Tree .....................54
3.3. Thực hiện từng bƣớc thuật toán .........................................................................59
3.4. Thực nghiệm ......................................................................................................68
3.4.1. Đặt vấn đề ...................................................................................................68
3.4.2. Cài đặt chƣơng trình khai phá tập thƣờng xuyên trên cây Compressed FP –
Tree (CFP) .............................................................................................................68
3.4.3. So sánh kết quả với các thuật toán khác: ....................................................72
KẾT LUẬN ...............................................................................................................73
TÀI LIỆU THAM KHẢO .........................................................................................74


1
MỞ ĐẦU
Ngày nay, cùng với sự phát triển của công nghệ thông tin (CNTT) là khả năng
thu thập và lƣu trữ thông tin của các hệ thống thông tin tăng một cách chóng mặt.
Bên cạnh đó, việc tin học hóa nhanh chóng trong nhiều lĩnh vực đời sống văn hóa
xã hội, quản lý kinh tế, khoa học kỹ thuật cũng nhƣ nhiều lĩnh vực khác đã tạo cho
chúng ta một lƣợng dữ liệu khổng lồ cần lƣu trữ.
Sự bùng nổ này dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công
cụ mới để tự động chuyển đổi lƣợng dữ liệu khổng lồ thành các tri thức có ích. Từ
đó, bên cạnh những phƣơng pháp khai thác thông tin truyền thống xuất hiện một
khuynh hƣớng kỹ thuật mới ra đời đó là Khai phá dữ liệu (Datamining) một lĩnh
vực quan trọng của ngành CNTT. Khai phá dữ liệu (KPDL) đang đƣợc áp dụng một
cách rộng rãi trong nhiều lĩnh vực đời sống nhƣ : marketing, tài chính – ngân hàng,
bảo hiểm, khoa học, y tế, an ninh, internet…Rất nhiều tổ chức và công ty lớn trên

thế giới đã áp dụng kỹ thuật KPDL vào các hoạt động sản xuất kinh doanh của mình
và thu đƣợc lợi ích to lớn.
Khai phá tập thƣờng xuyên đóng vai trò thiết yếu trong KPDL, nó là nền tảng
cho các nhiệm vụ KPDL khác nhƣ khai phá luật kết hợp, phân lớp, phân cụm dữ
liệu, tìm kiếm mối tƣơng quan, và các mối quan hệ trong cơ sở dữ liệu. Do vậy,
khai phá tập thƣờng xuyên đã trở thành nhiệm vụ quan trọng trong KPDL.Có rất
nhiều thuật toán đƣợc đề xuất với mục đích khai phá tập thƣờng xuyên nhanh và
chính xác. Tuy nhiên với cơ sở dữ liệu lớn rất cần một cấu trúc dữ liệu nhỏ gọn lƣu
trữ trên bộ nhớ và hiệu quả trong khai phá tập thƣờng xuyên.Từ những nhận định
trên và đƣợc sự gợi ý của giáo viên hƣớng dẫn, tôi quyết định chọn đề tài: “Nghiên
cứu phƣơng pháp tìm tập thƣờng xuyên sử dụng cây tiền tố nén”.
Nhiệm vụ chính của luận văn là nắm vững kiến thức tổng quan của lĩnh vực
KPDL, nghiên cứu một số thuật toán khai phá tập thƣờng xuyên, nghiên cứu thuật
toán khai phá tập thƣờng xuyên trên cây tiền tố nén lấy điển hình trên cấu trúc CFP
(Compressed FP-Tree) và cấu trúc CT-ITL (Compressed Tree - Item TransLink) sau
đó cài đặt chƣơng trình thử nghiệm, đánh giá, so sánh hiệu quả của thuật toán khai


2
phá tập thƣờng xuyên trên cây CFP với thuật toán Apriori và FP-Growth ( Những
thuật toán điển hình trong khai phá tập thƣờng xuyên).
Mục tiêu của luận văn:
- Nắm vững kiến thức tổng quan của lĩnh vực Khai phá dữ liệu.
- Nghiên cứu một số thuật toán khai phá tập thƣờng xuyên.
- Nghiên cứu thuật toán khai phá tập thƣờng xuyên sử dụng cấu trúc dữ liệu
và thuật toán CT-ITL.
- Nghiên cứu thuật toán khai phá tập thƣờng xuyên trên cây FP nén sử dụng
thuật toán CT-PRO và cài đặt chƣơng trình thực nghiệm đánh giá, so sánh hiệu quả
của thuật toán này với một số thuật toán khác trong khai phá tập thƣờng xuyên.
Phƣơng pháp nghiên cứu:

-

Kết hợp lý thuyết với đánh giá thực nghiệm

-

Sƣu tầm và tổng hợp các kết quả nghiên cứu về tập mục thƣờng xuyên, Khai

phá tập mục thƣờng xuyên từ nguồn sách và các bài báo khoa học, hội thảo chuyên
ngành trong nƣớc và ngoài nƣớc.
Một số kết quả nghiên cứu đạt đƣợc:
- Tổng kết kiến thức cơ bản về khai phá dữ liệu và khai phá tập thƣờng xuyên.
Trình bày hai thuật toán cơ bản trong khai phá tập thƣờng xuyên: thuật toán Apriori,
thuật toán tăng trƣởng mẫu FP-Growth.
- Trình bày chi tiết hai thuật toán khai phá tập thƣờng xuyên trên cây tiền tố
nén là cấu trúc cây FP nén và cấu trúc CT-ITL.
- Luận văn đã tiến hành cài đặt ba thuật toán Apriori, FP-Growth và thuật toán
CT-PRO sau đó đánh giá, so sánh tốc độ thực hiện của ba thuật toán này trên nhiều
CSDL lớn.
Ý nghĩa khoa học của đề tài:
- Làm rõ tầm quan trọng của khai phá tập thƣờng xuyên.
- Để có cái nhìn tổng quan, chi tiết về mỗi thuật toán và thảo luận về ý tƣởng
tối ƣu hóa của mỗi thuật toán.


3
Bố cục của luận văn:
Chƣơng 1: Tổng quan về khai phá dữ liệu
Giới thiệu tổng quan về khai phá dữ liệu, quá trình phát hiện tri thức từ cơ sở
dữ liệu, một số ứng dụng của khai phá dữ liệu và một số phƣơng pháp khai phá dữ

liệu.
Chƣơng 2: Khai phá tập thƣờng xuyên
Tổng quan khai phá tập thƣờng xuyên và luật kết hợp, trình bày một số thuật
toán khai phá tập thƣờng xuyên nhƣ: thuật toán Apriori, thuật toán FP- Growth.
Chƣơng 3: Khai phá tập thƣờng xuyên sử dụng cây tiền tố nén
Trình bàu cấu trúc dữ liệu ITL, cấu trúc dữ liệu và thuật toán khai phá tập
thƣờng xuyên CT-ITL.
Trình bày cấu trúc và thuật toán xây dựng cây CFP, thuật toán CT-PRO khai
phá tập thƣờng xuyên trên cây CFP.
Tiến hành cài đặt thuật toán CT-PRO sau đó đánh giá, so sánh tốc độ thực hiện
của nó với hai thuật toán Apriori và FP-Growth.


4
CHƢƠNG 1
TỔNG QUAN VỀ KHÁI PHÁ DỮ LIỆU
1.1. Giới thiệu tổng quan về khai phá dữ liệu.
Trong nhiều năm qua sự phát triển của công nghệ thông tin và việc ứng dụng
của công nghệ thông tin trong nhiều lĩnh vực đời sống, kinh tế xã hội đã tạo điều
kiện cho việc thu thập dữ liệu tốt hơn. Đặc biệt trong lĩnh vực kinh tế - xã hội,
doanh nghiệp đã nhận thức đƣợc tầm quan trọng của việc nắm bắt và xử lý thông
tin, nhằm giúp họ vạch ra chiến lƣợc kinh doanh kịp thời mang lại những lợi ích to
lớn. Chính vì những lí do trên họ đã tạo ra một lƣợng dữ liệu khổng lồ cần đƣợc lƣu
trữ và lƣợng dữ liệu ngày một tích lũy nhiều lên. Họ lƣu trữ các dữ liệu này vì cho
rằng trong nó ẩn chứa những giá trị nào đó.
Tuy nhiên theo thống kê thì chỉ có một lƣợng nhỏ (từ 5 – 10 %) của những dữ
liệu này là luôn đƣợc phân tích và số còn lại họ không biết phải làm gì và có thể làm
gì với chúng nhƣng họ vẫn tiếp tục thu thập với ý nghĩ rằng sau này có thể cần đến
nó mặc dù rất tốn kém. Một vấn đề đƣợc đặt ra là làm thế nào để tổ chức, khai thác
những khối lƣợng dữ liệu khổng lồ và đa dạng đó đƣợc? Giải pháp cho vấn đề này

chính là việc xây dựng một kho dữ liệu (Data Warehouse) và phát triển một khuynh
hƣớng kỹ thuật mới đó là kỹ thuật phát triển tri thức và khai phá dữ liệu (KDD Knowledge Discovery and Data Mining)
Khai phá dữ liệu đƣợc dùng để mô tả quá trình phát hiện ra tri thức trong
CSDL. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo
trong kinh doanh, các hoạt động sản xuất, ... Khai phá dữ liệu làm giảm chi phí về
thời gian so với phƣơng pháp truyền thống trƣớc kia (nhƣ phƣơng pháp thống kê).
Khai phá tập thƣờng xuyên đóng vai trò thiết yếu trong khai phá dữ liệu. Tập
thƣờng xuyên là cơ sở quan trọng để chúng ta có đƣợc tri thức từ kho dữ liệu. Nhận
thấy tầm quan trọng của vấn đề này, trong luận văn tốt nghiệp của mình, tôi đã chọn
nghiên cứu đề tài về khai phá tập thƣờng xuyên sử dụng cây tiền tố nén.


5
Các bƣớc của quá trình phát hiện tri thức (KDD)
Quy trình phát hiện tri thức tuân theo những bƣớc sau:
Bƣớc thứ nhất:Hình thành và xác định bài toán. Bƣớc này 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.
Điều 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 dữ
liệu.
Hình thành và
Xác định bài toán

Thu thập và
Tiền xử lý dữ liệu

Khai phá dữ liệu
Rút ra các tri thức

Minh họa và

Đánh giá tri thức

Sử dụng các tri thức
phát hiện đƣợc
Hình 1.1. Quy trình khám phá tri thức từ cơ sở dữ liệu
Bƣớc thứ hai:Thu thập và tiền xử lý dữ liệu. Tiến hành 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ộ quy trình phát hiện tri
thức do dữ liệu đƣợc lấy từ nhiều nguồn gốc khác nhau, không đồng nhất có thể gây
ra nhầm lẫn. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và phục vụ
cho việc phân tích.


6
Bƣớc thứ ba:Khai phá dữ liệu rút ra tri thức.Giai đoạn khai phá dữ liệu đƣợc
bắt đầu sau khi dữ liệu đã đƣợc thu thập và tiền hành xử lý chính là trích ra các mẫu
hoặc/và các mô hình ẩn dƣới 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 khi 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 chất mô tả - đƣa ra những tính chất chung nhất của các dữ
liệu; các bài toán khai phá dự báo – bao gồm cả việc thực hiện các suy diễn trên dữ
liệu. 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ƣ:Minh họa và đánh giá tri thức. Các tri thức phát hiện từ cơ sở dữ
liệu cần đƣợc tổng hợp dƣới dạng các báo cáo phục vụ cho các mục đích hỗ trợ
quyết định khác nhau. Do nhiều phƣơng pháp khai phá có thể đƣợc áp dụng nên các
kết quả có mức độ tốt/xấu khác nhau. Việc đánh giá các kết quả thu đƣợc là cần
thiết, giúp tạo cơ sở cho những quyết định chiến lƣợc. Thông thƣờng chúng đƣợc
tổng hợp, so sánh bằng các biểu đồ và đƣợc kiểm nghiệm, tin học hóa. Công việc

này thƣờng là của các chuyên gia, các nhà phân tích và quyết định.
Bƣớc thứ năm:Sử dụng các tri thức phát hiện được. Các kết quả của quá trình
phát hiện tri thức có thể đƣợc đƣa vào ứng dụng trong những lĩnh vực khác nhau.
Do các kết quả có thể là các dự báo hoặc các mô tả nên chúng có thể đƣợc đƣa vào
các hệ thống hỗ trợ ra quyết định nhằm tự động hóa quá trình này.
Trên đây mô tả 5 giai đoạn trong quá trình khám phá tri thức từ cơ sở dữ liệu.
Mặc dù có 5 giai đoạn nhƣ trên xong quá trình khám phá tri thức từ cơ sở dữ liệu là
một quá trình tƣơng tác và lặp đi lặp lại theo chu trình liên tục kiểu xoáy trôn ốc,
trong đó lần lặp sau hoàn chỉnh hơn lần lặp trƣớc. Ngoài ra, giai đoạn sau lại dựa
trên kết quả thu đƣợc của giai đoạn trƣớc theo kiểu thác nƣớc. Đây là một quá trình
biện chứng mang tính chất khoa học của lĩnh vực phát hiện tri thức và là phƣơng
pháp luận trong việc xây dựng các hệ thống phát hiện tri thức.


7
1.2. Kiến trúc của hệ thống khai phá dữ liệu
Nhƣ đã trình bày ở trên khai phá dữ liệu là một giai đoạn trong quá trình phát
hiện tri thức từ số lƣợng lớn dữ liệu lƣu trữ trong các cơ sở dữ liệu, kho dữ liệu
hoặc các nơi lƣu trữ khác. Bƣớc này có thể tƣơng tác lẫn nhau giữa ngƣời sử dụng
hoặc cơ sở tri thức những mẫu đáng quan tâm đƣợc đƣa cho ngƣời dùng hoặc lƣu
trữ nhƣ là tri thức mới trong cơ sở tri thức.

Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu.
Kiến trúc của hệ thống khai phá dữ liệu có các thành phần nhƣ sau:
1. Cơ sở dữ liệu, kho dữ liệu: Đó là một hoặc tuyển tập các cơ sở dữ liệu, kho
dữ liệu... Các kỹ thuật làm sạch dữ liệu, tích hợp , lọc dữ liệu có thể thực hiện trên
dữ liệu.
2. Cơ sở dữ liệu hoặc kho dữ liệu phục vụ: là kết quả lấy dữ liệu có liên quan
trên cơ sở khai phá dữ liệu của ngƣời dùng.
3. Cơ sở tri thức: Đó là lĩnh vực tri thức đƣợc sử dụng để hƣớng dẫn việc tìm

hoặc đánh giá các mẫu kết quả thu đƣợc.


8
4. Mô tả khai phá dữ liệu: Bao gồm tập các modul chức năng để thực hiện các
nhiệm vụ mô tả đặc điểm , kết hợp, phân lớp, phân cụm dữ liệu...
5. Đánh giá mẫu: Thành phần này sử dụng các độ đo và tƣơng tác với modul
khai phá dữ liệu để tập chung vào tìm các mẫu quan tâm.
6. Giao diện ngƣời dùng: Đây là modul giữa ngƣời dùng và hệ thống khai phá
dữ liệu. Cho phép ngƣời dùng tƣơng tác với hệ thống trên cơ sở những truy vẫn hay
tác vụ, cung cấp thông tin cho việc tìm kiếm.
1.2.1. Một số khái niệm về khai phá dữ liệu
Khai phá dữ liệu đƣợc định nghĩa nhƣ một quá trình chắt lọc hay khai phá tri
thức từ một lƣợng lớn dữ liệu. Một ví dụ hay đƣợc sử dụng là việc khai thác vàng từ
đá và cát, khai phá dữ liệu đƣợc ví nhƣ công việc “Đãi cát tìm vàng” trong một tập
hợp lớn các dữ liệu cho trƣớc.
Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức để tìm ra các
mẫu và các mô hình trong dữ liệu. Mục đích của khám phá tri thức và khai phá dữ
liệu là tìm ra các mẫu hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhƣng
vẫn còn bị khuất bởi dữ liệu khổng lồ.
Sau đây là một số định nghĩa mang tính mô tả của nhiều tác giả về khai phá dữ liệu.
Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp đƣợc
dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và
các mẫu chƣa biết bên trong dữ liệu”
Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định,
trong đó chúng ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong CSDL lớn”
Định nghĩa của Fayyad: “Khai phá dữ liệu là một quá trình không tầm thƣờng
nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu đƣợc”.
1.2.2. Nhiệm vụ chính của khai phá dữ liệu
Điểm khác biệt giữa các kỹ thuật khai phá dữ liệu và các công cụ phục vụ tính

toán thống kê mà chúng ta đã biết là ở khối lƣợng cần tính toán. Một khi dữ liệu đã
trở nên khổng lồ thì những khâu nhƣ: thu thập dữ liệu, tiền xử lý và xử lý dữ liệu


9
đều đòi hỏi phải đƣợc tự động hóa. Tuy nhiên ở công đoạn cuối cùng, việc phân tích
kết quả sau khi đã khai phá dữ liệu vẫn luôn là công việc của con ngƣời.
Chúng ta thấy những nhiệu vụ cơ bản nhất của khái phá dữ liệu là:
-

Phân cụm, phân loại, phân nhóm, phân lớp: Nhiệm vụ là trả lời câu hỏi: Một

dữ liệu mới thu thập sẽ thuộc nhóm nào? Quá trình này thƣờng đƣợc thực hiện một
cách tự động.
-

Khai phá luật kết hợp: Nhiệm vụ là phát hiện ra những mối quan hệ giống

nhau của các bản ghi giao dịch. Luật kết hợp X->Y có dạng tổng quát là: Nếu một
giao dịch đã đƣợc sở hữu các tính chất X thì đồng thời nó cũng sở hữu các tính chất
Y, ở một mức độ nào đó. Khai phá luật kết hợp đƣợc hiểu theo nghĩa: Biết trƣớc
các tính chất X, vậy các tính chất Y là những tính chất nào?
-

Lập mô hình dự báo, bao gồm hai nhiệm vụ: Hoặc là phân nhóm dữ liệu vào

một hay nhiều nhóm dữ liệu đã xác định từ trƣớc hoặc sử dụng các trƣờng đã cho
trong một cơ sở dữ liệu để dự báo sựxuất hiện (hoặc không xuất hiện) của các
trƣờng hợp khác.
-


Phân tích đối tượng ngoài cuộc: Một cơsở dữ liệu có thể chứa các đối tƣợng

không tuân theo mô hình dữ liệu. Các đối tƣợng dữ liệu nhƣ vậy gọi là các đối
tƣợng ngoài cuộc. Hầu hết các phƣơng phápkhai phá dữ liệu đều coi các đối tƣợng
ngoài cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một sô ứng dụng , chẳng hạn
nhƣ phát hiện nhiễu thì sựkiện hiếm khi sảy ra lại đƣợc chú ý hơn những gì thƣờng
xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc đƣợc coi nhƣ là khai phá cácđối
tƣợng ngoài cuộc. Một số phƣơng pháp đƣợc ứng dụng để phát hiện đối tƣợng
ngoài cuộc: Sử dụng các hình thức kiểm tra mang tính thống kê trên cơ sở một phân
phối dữ liệu hay một mô hình xác xuất cho dữ liệu, dùng các độ đo khoảng cách mà
theo đó các đối tƣợng có một khoảng cách đáng kể đến cụm bất kì khác đƣợc coi
làđối tƣợng ngoài cuộc, dùng các phƣơng pháp dựa trên độ lệch để kiểm tra sự khác
nhau trong những đặc trƣng chính của các nhóm đốitƣợng.


10
-Phântích sự tiến hóa:Phân tích sự tiến hóa thực hiện việc mô tả vàmô hình hóa
các quy luật haykhuynh hƣớng của những đối tƣợng mà ứng xử của chúng thay đổi
theo thời gian. Phân tích sự tiến hóa có thể bao gồm các đặc trƣng hóa, phân biệt,
tìm luật kết hợp, phân lớp hay phân cụm dữ liệu liên quan đến thời gian, phân tích
dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kì và phân tích dữ liệu dựa trên
tính tƣơng tự.
1.3. Một số phƣơng pháp khai phá dữ liệu
Khai phá dữ liệu là lĩnh vực mà con ngƣời luôn tìm cách đạt đƣợc mục đích sử
dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu,
trong đó phƣơng pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo
dạng xác định. Có thể kể ra đây một vài phƣơng pháp nhƣ: sử dụng công cụ truy
vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị
trung bình, phát hiện luật kết hợp, … Các phƣơng pháp trên có thể đƣợc phỏng theo

và đƣợc tích hợp vào các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều
năm nghiên cứu. Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phƣơng
pháp này cũng đối diện với thách thức về mặt hiệu quả và quy mô.
1.3.1.Phƣơng pháp suy diễn / quy nạp
Một cơ sở dữ liệu 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 cơ sở dữ liệu. 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.


11
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ừ cơ sở dữ liệu. 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 cơ sở dữ
liệu. 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.
1.3.2.Phƣơng pháp ứng dụng 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à
rất có ích đối với việc phân tích dữ liệu. Việc dùng các miêu tả này, nội dung của
vùng lân cận đƣợc xác định, trong đó các bản ghi gần nhau trong không gian đƣợc
xem xét thuộc về lân cận (hàng xóm – láng giềng) của nhau. Khái niệm này đƣợc
dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần, trong đó K là số láng
giềng đƣợc sử dụng. Phƣơng pháp này rất hiệu quả nhƣng lại đơn giản. Ý tƣởng

thuật toán học K-láng giềng gần là “thực hiện nhƣ các láng giềng gần của bạn đã
làm”.
Ví dụ: Để dự đoán hoạt động của cá thể xác định, K-láng giềng tốt nhất của cá thể
đƣợc xem xét, và trung bình các hoạt động của các láng giềng gần đƣa ra đƣợc dự
đoán về hoạt động của cá thể đó.
Kỹ thuật K-láng giềng gần là một phƣơng pháp tìm kiếm đơn giản. Tuy nhiên,
nó có một số mặt hạn chế giới là hạn phạm vi ứng dụng của nó. Đó là thuật toán này
có độ phức tạp tính toán là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu.Vấn đề
chính liên quan đến thuộc tính của bản ghi. Một bản ghi gồm hiều thuộc tính độc
lập, nó bằng một điểm trong không gian tìm kiếm có số chiều lớn. Trong các không
gian có số chiều lớn, giữa hai điểm bất kỳ hầu nhƣ có cùng khoảng cách. Vì thế mà
kỹ thuật K-láng giềng không cho ta thêm một thông tin có ích nào, khi tất cả các cặp
điểm đều là các láng giềng. Cuối cùng, phƣơng pháp K-láng giềng không đƣa ra lý
thuyết để hiểu cấu trúc dữ liệu. Hạn chế đó có thể đƣợc khắc phục bằng kỹ thuậtcây
quyết định.


12
1.3.3.Phƣơng pháp sử dụng cây quyết định và luật
Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của quá trình xây dựng
mô hình sẽ cho ra một cây quyết định. Cây này đƣợc sử dụng trong quá trình phân
lớp các đối tƣợng dữ liệu chƣa biết hoặc đánh giá độ chính xác của mô hình. Tƣơng
ứng với hai giai đoạn trong quá trình phân lớp là quá trình xây dựng và sử dụng cây
quyết định.
Quá trình xây dựng cây quyết định bắt đầu từ một nút đơn biểu diễn tất cả các
mẫu dữ liệu. Sau đó, các mẫu sẽ đƣợc phân chia một cách đệ quy dựa vào việc lựa
chọn các thuộc tính. Nếu các mẫu có cùng một lớp thì nút sẽ trở thành lá, ngƣợc lại
ta sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm cơ sở để phân
chia các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa chọn, ta tạo ra các
nhánh tƣơng ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình trên

cho tới khi tạo ra đƣợc cây quyết định, tất cả các nút triển khai thành lá và đƣợc gán
nhãn.
Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau đƣợc thỏa mãn:
-

Tất cả các mẫu thuộc cùng một nút.

-

Không còn một thuộc tính nào để lựa chọn.

-

Nhánh không chứa mẫu nào.

Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng
nhiều bộ nhớ. Lƣợng bộ nhớ sử dụng tỷ lệ thuận với kích thƣớc của mẫu dữ liệu
huấn luyện. Một chƣơng trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài
song lại có nhƣợc điểm về tốc độ thực thi. Do vậy, vấn đề tỉa bớt cây quyết định trở
nên quan trọng. Các nút lá không ổn định trong cây quyết định sẽ đƣợc tỉa bớt.Kỹ
thuật tỉa trƣớc là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa.
1.3.4.Phƣơng pháp phát hiện luật kết hợp
Phƣơng pháp này 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 luật kết
hợp tìm đƣợc. Ta có thể lấy một ví dụ đơn giản về luật kết hợp nhƣ sau: sự kết hợp


13
giữa hai thành 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.

Cho một lƣợc đồ R={A , …, A } các thuộc tính với miền giá trị {0,1}, và một
1

p

quan hệ r trên R. Một luật kết hợp trên r đƣợc mô tả dƣới dạng X=>B với X
B

R và

R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật nhƣ sau: nếu một

bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc tính B
cũng là 1 trong cùng bản ghi đó. Ví dụ nhƣ ta có tập cơ sở dữ liệu về các mặt hàng
bán trong siêu thị, các dòng tƣơng ứng với các ngày bán hàng, các cột tƣơng ứng
với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mì) xác định rằng bánh mì đã bán
ngày hôm đó cũng kéo theo sự xuất hiện giá trị 1 tại ô (20/10, bơ).
Cho W

R, đặt s(W,r) là tần số xuất hiện của W trong r đƣợc tính bằng tỷ lệ

của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật
X=>B trong r đƣợc định nghĩa là s(X
cậy của luật là s(X

{B}, r) còn gọi là độ hỗ trợ của luật, độ tin

{B}, r)/s(X, r). Ở đây X có thể gồm nhiều thuộc tính, B là giá

trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn

trƣớc khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm có
kích thƣớc tăng theo hàm mũ của số lƣợng các thuộc tính ở đầu vào. Do vậy cần
phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm các luật kết hợp.
Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X=>B
sao cho tần số của luật không nhỏ hơn ngƣỡng σ cho trƣớc và độ tin cậy của luật
không nhỏ hơn ngƣỡng θ cho trƣớc. Từ một cơ sở dữ liệu ta có thể tìm đƣợc hàng
nghìn và thậm chí hàng trăm nghìn các luật kết hợp.
Ta gọi một tập con X

R là thƣờng xuyên trong r nếu thỏa mãn điều kiện s(X,

r)≥σ. Nếu biết tất cả các tập thƣờng xuyên trong r thì việc tìm kiếm các luật rất dễ
dàng. Vì vậy, giải thuật tìm kiếm các luật kết hợp trƣớc tiên đi tìm tất cả các tập
thƣờng xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách ghép dần các tập
thuộc tính dựa trên mức độ thƣờng xuyên.


14
Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất thích
hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giới hạn cơ bản của
phƣơng pháp này là ở chỗ các quan hệ cần phải thƣa theo nghĩa không có tập
thƣờng xuyên nào chứa nhiều hơn 15 thuộc tính. Giải thuật tìm kiếm các luật kết
hợp tạo ra số luật ít nhất phải bằng với số các tập thƣờng xuyên và nếu nhƣ một tập
K

thƣờng xuyên có kích thƣớc K thì phải có ít nhất là 2 tập thƣờng xuyên. Thông tin
về các tập thƣờng xuyên đƣợc sử dụng để ƣớc lƣợng độ tin cậy của các tập luật kết
hợp.
1.4. Những khó khăn trong khai phá dữ liệu
Việc nghiên cứu và sử dụng những ứng dụng trong khai phá dữ liệu gặp nhiều

khó khăn nhƣng không phải không giải quyết đƣợc mà chúng cần đƣợc tìm hiểu để
đƣợc phát triển tốt hơn. Ta có thể liẹt kê một số khó khăn nhƣ sau:
-

Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trƣờng và bảng , hàng

triệu bản ghi với kích thƣớc rất lớn, có thể lên đến GB. Các phƣơng pháp giải quyết
hiện nay là đƣa ra một ngƣỡng cho cơ sở dữ liệu ,lấy mẫu, các phƣơng pháp tính
xấp xỉ, xử lý song song.
-

Kích thước lớn: Không chỉ có số lƣợng bản ghi mà số các trƣờng trong cơ sở

dữ liệu cũng nhiều. Vì vậy mà kích thƣớc của bài toán trở nên lớn làm tăng không
gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng một thuật toán khai phá dữ liệu
có thể tìm thấy các mẫu giả. Biện pháp khắc phục là làm giảmkích thƣớc tác động
của bài toán và sử dụng các tri thức biết trƣớc để xác định các biến không phù hợp.
-

Dữ liệu động: Đặc điểm cơ bản của các dữ liệu là nội dung của chúng thay

đổi liên tục. Chẳng hạn nhƣ các biến trong cơ sở dữ liệu của ứng dụng đã cho chúng
có thể bị thay đổi, bị xóa , hoặc là tăng lên theo thời gian. Dữ liệu có thể thay đổi
theo thời gian và việc khai phá dữ liệu bị ảnh hƣởng bởi thời điểm quan sát dữ liệu,
do đó có thể làm cho mẫu khai thác đƣợc trƣớc đó mất giá trị. Vấn đề này đƣợc giải
quyết bằng giải pháp tăng trƣởng để nâng cấp các mẫu và coi những thay đổi nhƣ là
cơ hội để khai thác bằng cách sử dụng nó để tìm kiếm các mẫu bị thay đổi.


15

-

Các trường dữ liệu không phù hợp : Một đặc điểm quan trọng khác làtính

không thích hợp của dữ liệu – nghĩa là mục dữ liệu trở thành không thích hợp với
trọng tâm hiện tại của việc khai thác. Bên cạnh đó tính ứng dụng của một thuộc tính
đối với một tập con của cơ sở dữ liệu cũng là một vấn đề đôikhi cũng liên quan đến
độ phù hợp.
-

Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu

phù hợp có thể ảnh hƣởng đến việc khai phá dữ liệu. Trong hệ thống tƣơng tác, sự
thiếu vắng dữ liệu quan trọng có thể dẫn tới yêu cầu cho giá trị của nó hoặc kiểm tra
để xác định giá trị của nó. Hoặc cũng có thể sự vắng mặt của dữ liệu đƣợc coi nhƣ
một điểu kiện, thuộc tính bị mất có thể đƣợc xem nhƣ một giá trị trung gian và giá
trị không biết.
-

Các trường dữ liệu bị thiếu: Một quan sát không đầy đủcơ sở dữ liệu có thể

làm cho dữ liệu có giá trị bị xem nhƣ có lỗi. Việc quan co sở dữ liệu phải phát hiện
đƣợc toàn bộ các thuộc tính có thể dùng để thuật toán khai phá dữ liệu có thểáp
dụng để giải quyết bài toán. Giảsử ta có các thuộc tính để phân biệt các tình huống
đáng quan tâm. Nếu chúng không làm đƣợc điều đó thì có nghĩa là đã có lỗi trong
dữ liệu. Đây cũng là vấn đề thƣờng xảy ratrong cơ sở dữ liệu kinh doanh. Các thuộc
tính quan trọng có thể sẽ bị thiếu dữ liệu không đƣợc chuẩn bị.
-

Quá phù hợp: Khi một thuật toán tìm kiếm tham số tốt nhất cho một mô hình


nào đó sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng quá độ dữ liệu
(nghĩa là tìm kiếm quá mức cần thiết gây ra hiện tƣợng chỉ phù hợp với dữ liệu đó
mà không có khả năng đáp ứng cho các dữ liệu lạ), làm cho mô hình hoạt động rất
kém với các dữ liệu thử .Các giải pháp khắc phục nhƣ đánh giá chéo, thực hiện theo
nguyên tắc nào đó hoặc sử dụng các biện pháp thống kê khác.
-

Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng điều quan trọng là

nhữngđiều khai thác đƣợc phải càng dễ hiểu với con ngƣời càng tốt. Vì vậy các giải
pháp thƣờng bao gồm việc diễn tả dƣới dạng đồ họa , xây dựng cấu trúc luật với các
đồ thị có hƣớng biểu diễn bằng ngôn ngữ tự nhiên và kĩ thuật khác nhằm biểu diễn
các tri thức và dữ liệu.


16
-

Sự tương tác với người sử dụng các tri thức có sẵn: Rất nhiều công cụ và

phƣơng pháp khai phá dữ liệu không thực sự tƣơng tác với ngƣời dùng và không dễ
dàng kết hợp cùng các tri thức đã biết trƣớc đó. Việc sử dụng tri thức miền là rất
quan trọng trong khai phá dữ liệu. Đã có nhiều biện pháp nhằm khắc phục vấn đề
này nhƣ sử dụng cơ sở dữ liệu suy diễn để phát hiện tri thức , những tri thức này sau
đó đƣợc sử dụng để hƣớng dẫn cho viêc tìm kiếm khai phá dữ liệu hoặc sử dụng sự
phân bố xác xuất dữ liệu trƣớc đó nhƣ một dạng mã hóa tri thức có sẵn.
-

Độ nhiễu và không chắc chắn: Đối với các thuộc tính đã thích hợp, độ


nghiêm trọng của lỗi phụ thuộc vào kiểu dữ liệu của các giá trị cho phép. Các giá trị
của các thuộc tính khác nhau có thể là các số thực, số nguyên, chuỗi và có thể thuộc
vào tập các giá trị định danh. Các giá trị định danh này có thể sắp xếp theo thứ tự
từng thành phần hoặc đầy đủ, thậm chí có thể có cấu trúc ngữ nghĩa.
Một yếu tố khác của độ không chắc chắn chính là tính kế thừa hoặc độ chính xác
của dữ liệu cần có, nói cách khác là độ nhiễu của dữ liệu. Dựa trên việc tính toán
trên các phép đo và phân tích có ƣu tiên, mô hinhd thống kê mô tả tính ngẫu nhiên
đƣợc tạo ra và đƣợc sử dụng để định nghĩa độ mong muốn và độ dung sai của dữ
liệu. Thƣờng thì các mô hình thống kê đƣợc áp dụng theo cách đặc biệt để xác định
một cách chủ quan các thuộc tính để đạt đƣợc các thống kê và đánh giá khả năng
chấp nhận của giá trị thuộc tính. Đặc biệt là những dữ liệu kiểu số, sự đúng đắn của
dữ liệu có thể là một yếu tố trong việc khai phá
-

Mối quan hệ phức tạp giữa các trƣờng: Các thuộc tính hoặc các giá trị có cấu

trúc phân cấp, các mối quan hệ giữa các thuộc tính và các phƣơng tiện phức tạp để
diễn tả tri thức về nội dung của cơ sở dữ liệu yêu cầu các thuật toán phải có khả
năng sử dụng một cách hiệu quả thông tin này. Ban đầu, kỹ thuật khai phá dữ liệu
chỉ đƣợc phát triển cho các bản ghi có giá trị thuộc tính đơn giản. Tuy nhiên, ngày
nay ngƣời ta đang tìm cách phát triển các kỹ thuật nhằm rút ra mỗi quan hệ giữa các
biến này.


17
1.5.Một số ứng dụng khai phá dữ liệu
Với mỗi phƣơng thức riêng biệt, rất nhiều ứng dụng thành công sử dụng
KPDL trong cuộc sống thực, sau đây là một số lĩnh vực mà áp dụng thành công kỹ
thuật KPDL:

- 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, ...
- Đ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, ...
- Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.
- Viễn thông: Phát hiện gian lận trong cuộc gọi, xác định những hồ sơ khách
hàng trung thành, xác định các nhân tố ảnh hƣởng đến hành vi khách hàng liên quan
đến các kiểu gọi điện thoại, xác định rủi ro trong việc sử dụng đầu từ các công nghệ
mới, xác định những sự khác nhau giữa các dịch vụ và sản phẩm giữa các đối thủ
cạnh tranh.
- Tài chính, ngân hàng: phân khúc khách hàng và lợi nhuận, chấm điểm tín
dụng và phê duyệt, quảng bá và bán sảnphẩm, phát hiện ra những giao dịch gian
lận, quyết định cho vay.
- Ngoài ra KPDL còn đƣợc ứng dụng trong sản xuất nhƣ điều khiển và lập kế
hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm, … Trong thông tin khoa học
nhƣ dự báo thời tiết, cơ sở dữ liệu sinh học: ngân hàng gen, … khoa học địa lý: dự
báo động đất, …