ĐẠI HỌC THÁI
NGUYÊN
KHOA CÔNG NGHỆ THÔNG
TIN
-----------------------------
LÊ THỊ VIỆT
HOA
KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KHAI
PHÁ
LUẬT KẾT HỢP SONG
SONG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số :
60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN
THÁI NGUYÊN
2008
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
LỜI CẢM ƠN
Xin chân thành cảm ơn Thầy giáo PGS.TS Đoàn Văn Ban đã tận tình
chỉ dạy và hướng dẫn tôi trong suốt thời gian học tập và làm luận văn.
Tôi cũng xin xin lời biết ơn chân thành đến quý Thầy giáo, cô giáo Viện
Công nghệ Thông đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý
báu trong suốt quá trình học tập tại Khoa.
Xin cảm ơn tất cả các anh chị em học viên Cao học khóa 5, cám ơn cán
bộ công chức, giảng viên – Khoa Công nghệ Thông tin - Đại học Thái
Nguyên đã tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập và làm luận
văn.
Cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã giúp đỡ tôi

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
3
1.1.
Khái niệm
3
1.2.
Kiến trúc của một hệ thống khai phá dữ liệu
3
1.3.
Các giai đoạn của quá trình khai phá dữ liệu
4
1.4.
Một số kỹ thuật khai phá dữ liệu
6
1.5.
Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
10
1.6.
Các phương pháp chính trong khai phá dữ liệu
11
1.7.
Các ứng dụng của khai phá dữ liệu
13
1.8. Khai phá dữ liệu và các lĩnh vực liên quan
14
1.9.
Các thách thức trong phát hiện tri thức và khai phá dữ liệu
15
1.10.
Kết luận chương 1

49
Chương 3:
MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP
50
SONG SONG VÀ PHÂN TÍCH ĐÁNH GIÁ CÁC THUẬT TOÁN
3.1. Nguyên lý thiết kế thuật toán song song
50
3.2.
Hư
ớng
ti
ếp

cận

chính
t
rong
t
hiế
t
kế
t
huậ
t t
oán

kha
i
phá

71
3.4.2. So sánh việc thực hiện các thuật toán
73
3.5. Kết luận chương 3
74
Kết luận
75
Tài liệu tham khảo
77
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT
Ký hiệu Diễn
giải
C
k
Tập các k-itemset ứng viên
C
k
Tập các k-itemset ứng viên mà TID của giao dịch sinh ra
liên kết với tập mục ứng viên
Conf Độ tin cậy (Confidence)
CFPT FP-Tree điều kiện cơ sở (Fisst conditional FP-Tree)
D Cơ sở dữ liệu giao dịch
D
i
Phần thứ i của cơ sở dữ liệu D
Item Mục
Itemset Tập mục
I Tập các mục
KDD Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery

Bảng 2.1.a. Thông tin của một cửa hàng bán lẻ 33
Bảng 2.1.b. Tập giao dịch D của cửa hàng 33
Hình 3.1. Mô hình song song dữ liệu 51
Hình 3.2. Mô hình song song thao tác 52
Hình 3.3. Sơ đồ thuật toán Count Distribution
52
Hình 3.4. Phát hi ện các tập mục phổ biến bởi thuật toán song song
CD
54
Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution 55
Hình 3.6: Sơ đồ luồng thuật toán Data Distribution
56
Hình 3.7: Phát hi ện các tập mục phổ biến bởi thuật toán song song
DD
57
Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu 61
Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở 62
Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P
1
và P
2
63
Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc
70
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
MỞ ĐẦU
Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ
liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ

của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính
khác như thế nào. Bên cạnh đó, nhu cầu song
s
ong hóa và xử lý phân tán là rất
cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc
độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu
cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp.
Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc
tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn
nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
thước dữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung
lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán
song song hiệu quả cho luật kết hợp.
Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a
trên các bài báo khoa ọhc trong một số hội thảo quốc tế và các bài báo
chuyên ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một
số thuật toán khai phá luật kết hợp song song.
Nội dung luận văn được trình bày trong 3 chương và phần kết
luận
Chương 1: Tổng quan về
k
hai phá dữ liệu: Giới thiệu tổng quan về
quá trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của
một hệ thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá
dữ liệu.
Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng
quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp;
các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp;

từnhững
kho
d
ữ liệu
lớn.
Khai phá
d
ữ liệu
là
quátrình chính trong
khai
phá tri
th ức
từ
cởơdsữ
liệu.
Kiến trúc
của một
hệ thống khai
phá
dữ liệu
có
các
thành
[2]
phần
như
sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
Hình 1.1. Khám phá tri thức tron

ược
quan tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá
được. Cũng có thể Modul đánh giá mẫu được tích hợp vào Modul khai phá
dữ
liệu,
tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng.
 Giao diện đồ họa cho người dùng
(
Graphical user interface)
Bộ
phận
này cho phép người dùng giao tiếp với hệ thống khai phá dữ liệu.
Thông qua giao diện này người dùng tương tác với hệ thống bằng cách đặc tả
một yêu cầu khai phá hay một nhiệm vụ, c ung cấp thông tin trợ giúp cho việc
tìm kiếm và thực hiện khai phá thăm dò trên các kết quả khai phá trung
gian. Ngoài ra bộ phận này còn cho phép người dùng xem các lược đồ CSDL,
lược đồ kho dữ liệu, các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng
khác nhau.
1.3. Các giai
đo
ạn của quá trình khai phá dữ liệu
Các thuật toán khai phá dữ liệu thường được mô tả như những chương
trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và
thống kê trước đây, bước đầu tiên là thuật toán thường nạp toàn bộ tệp (file) dữ
liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến
việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
chỉ bởi nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn khó có thể chiết
xuất dữ liệu ra các tệp đơn giản để phân tích.

Ví dụ, trong bài toán tìm quy luật mua hàng của khách hàng trong một
siêu thị, ta tìm xem khách hàng thường cùng mua những mặt hàng nào để sắp
xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể
có nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng,
nhà cung cấp, đơn giá hàng, người bán hàng… Các dữ liệu này cần cho quản lý
bán hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này
khỏi dữ liệu trước khi khai phá dữ liệu.
Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán
khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu.
Bước ba: Sau xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu
của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn
dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước
lượng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu,
chúng ta phải làm lại với kỹ thuật khác cho đến khi có
k
ết quả mong muốn.
1.4. Một số kỹ thuật khai phá dữ liệu
Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh
doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai
phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát
hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến
hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán
được những giá trị chưa biết hoặc những giá trị tương lai của các biến đáng quan
tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có
thể hiểu được.
Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu
bao gồm như sau:
Phân lớp dữ liệu [24]
Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000. Phân
lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những

những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết địnhcó
thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực.
Phân nhóm dữ liệu [13, 24]
Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu.
Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá
trình nhóm
nhữn
g đối tượng vào trong những lớp tương đương,
đ
ến những
đối tượng trong một nhóm là tương đương nhau, chúng phải khác với những
đối tượng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc
về lớp nào là phải xác định trước, trong khi phân nhóm không xác định
trước. Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự
giống nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi
những chức năng giống nhau. Thông thường những sự giống nhau về định
lượng như khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia
trong lĩnh vực của mình.
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
Nợ
nhóm 1
+
+ +
+ +
+
+ + +
+ +
+
+ + +

[13,
23]. 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ểm chẳng hạn như hồi qui tuyến tính. Tuy nhiên, phương pháp mô hình hóa
cũng được sử dụng [13, 24].
Nợ
+
0
0
+
0
+
+
0
+ +
0
0
đường hồi quy
tuyến tính
0
0 0
0
0
+ +
0 0
+
0
Thu nhập
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy

10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ
liệu thành các loại khác nhau.
Cơ sở dữ liệu quan hệ
Đến nay, hầu hết dữ liệu được lưu giữ dưới dạng cơ sở dữ liệu quan hệ.
Cơ sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tượng
mà chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu được
mô tả bởi một tập những thuộc tính và lưu trong những bảng. Khai phá dữ liệu
trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá
mẫu
. Ví dụ, trong cơ sở
dữ liệu của một ngân hàng, ta có thể tìm được những khách hàng có mức chi
tiêu cao, ta có thể phân loại những khách hàng này dựa vào quá trình chi tiêu
của họ. Cũng với việc phân tích những mục chi tiêu của khách hàng, chúng ta
có thể cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác.
Giả sử rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu
được phép, ngân hàng có thể cung cấp thông tin về khách hàng này cho
những cửa hàng thời trang.
Cơ sở dữ liệu giao tác
Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các
trường hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ
chức. Với tính phổ biến của máy tính và thương mại điện tử, ngày nay có rất
nhiều cơ sở dữ liệu giao tác. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập
trung vào khai phá luật kết hợp, tìm mối tương quan giữa những mục dữ liệu
của bản ghi giao dịch. Nghiên cứu sâu về cơ sở dữ liệu giao tác được mô tả chi
tiết ở phần sau.
Cơ sở dữ liệu không gian
Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu

chính: Khai phá cách dùng web (web usage mining), khai phá c ấu trúc web (web
structure mining) và khai phá
n
ội dung web (web content mining).
Khai phá cách dùng web tập trung vào việc khai phá thông tin của người
truy nhập web. Với những thông tin này người khai phá dữ liệu có thể cung cấp
những thông tin hữu ích cho người dùng và các nhà kinh doanh.
1.6. Các phương pháp chính trong khai phá d ữ liệu
 Phân lớp và dự đoán (Classification & Prediction)
Xếp một đối tượng vào một trong những lớp đa biết. Ví dụ : phân ớl
p vùng địa lý theo dữ liệu thời tiết. Đối với hướng tiếp cận này thường áp
dụng một số kỹ thuật như học máy (Machine learning), cây quyết định
(Decision
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên htt p ://www.lr c - tnu. ed u. v n
tree), mạng nơron nhân tạo (Neural network). Với hướng này, người ta còn gọi
là học có giám sát hạy học có thầy (Supervised learning).
 Phân cụm và phân đoạn (Clusterring and Segmentation)
Sắp xếp các đối tượng theo từng cụm (số lượng và tên của cụm chưa
được biết trước). Các đối tượng được gom cụm sao cho mức độ tương tự
g
iữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các
đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán phân cụm
còn được gọi là học không giám sát hạy học không thầy.
 Luật kết hợp (Association rules)
Luật kết hợp là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Mục tiêu
của phương pháp này là phát
hệi
n và đưa ra các mối liên hệ giữa các giá trị dữ
liệu trong cơ sở dữ liệu. Mẫu đầu của giải thuật khai phá dữ liệu là tập luật kết

quảng cáo, tiếp thị, quản lý hàng tồn kho và dự trữ hàng. Các luật kết hợp cũng
được sử dụng cho các ứng dụng khác như dự đoán lỗi, cho các mạng điện thoại
bằng việc xác định các sự kiện xuất hiện trước đó.
 Khai phá chuỗi theo thời gian (Sequential temporal patterns)
Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính
thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực
tài chính và thị trường chứng khoán bởi vì chúng có tính dự báo cao.
 Mô tả khái niệm và tổng hợp hóa (Summarization)
Liên quan
đế
n các phương pháp tìm kiếm một mô tả cho một tập con dữ
liệu. Các kỹ thuật toán tắt thường được áp dụng cho các phân tích dữ liệu tương
tác có tính thăm dò và tạo báo cáo tự động.
1.7. Các ứng dụng của khai phá
d
ữ
liệu
Khai phá dữ liệu tuy là một lĩnh vực mới nhưng đã thu hút được sự quan
tâm của rất nhiều nhà nghiên cứu, nhờ có nhiều những ứng dụng trong thực tiễn,
các ứng dụng điển hình, có thể liệt kê như sau:
- Phân tích dữ liệu và hỗ trợ ra quyết định (Analysis & decition support).
- Điều trị trong y học (Medical): mối liên hệ giữa triệu chứng, chuẩn đoán
và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật).
- Phân lớp văn bản, tóm tắt văn bản và phân lớp các trang Web (Text
mining & Web mining).
- Tin sinh học
(Bio
-informatics): Tìm
kiếm
, đối sánh các hệ gen và

ngành khoa học, nó liên quan đến rất nhiều ngành, nhiều lĩnh vực khác
nhau như tài chính, ngân hàng, thương mại, y tế, giáo dục, thống kê, máy móc,
trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song, thu nhận tri
thức trong các hệ chuyên gia, quan sát dữ liệu.
Lĩnh vực học máy và nhận dạng mẫu là giống nhau trong khai phá dữ liệu
nghiên cứu các lý thuyết và thuật toán của hệ thống trích ra các mẫu và mô hình
dữ liệu. Khai phá dữ liệu tập trung vào việc mở rộng các lý thuyết và thuật toán
cho các vấn đề về tìm ra các mẫu đặc biệt, đây được coi là những mẫu hữu ích
hoặc tri thức quan trọng tập dữ liệu lớn.
Đặ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…, kho dữ liệu và các công cụ xử lý trực tuyến (OLAP – online
analytical processing)
ật
p trung vào phân tích dữ liệu đa chiều, tốt hơn
SQL trong tính toán và phân tích thống kê đa chiều cũng liên quan chặt chẽ đến
khai phá dữ liệu.
Đặc trưng của hệ thống khai phá dữ liệu là nhờ vào các phương pháp
thuật toán và kỹ thuật từ những lĩnh vực khác nhau, nhằm mục đích cuối cùng là
trích ra tri thức từ dữ liệu trong CSDL khổng lồ.
1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu
Khai phá dữ liệu ngày càng đóng một vai trò quan trọng trong việc tìm ra
các tri thức thực sự có ích, hiệu quả tiềm ẩn trong các khối dữ liệu thông tin
khổng lồ vẫn hàng ngày đang được thu thập, lưu trữ để giúp các cá nhân và tổ
chức đưa ra được các quyết định chính xác và nhanh chóng. Tuy đã có rất nhiều
các giải pháp và phương pháp được ứng dụng trong khai phá dữ liệu nhưng trên
thực tế quá trình này vẫn gặp không ít khó khăn và thách thức như:
- Cơ sở dữ liệu lớn
- Số chiều các thuộc tính lớn
- Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát