Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

i

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TƢ KHAI PHÁ LUẬT KẾT HỢP
TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60. 48. 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. NGUYỄN HUY ĐỨC Thái nguyên, năm 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

i
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung trong Luận văn là đƣợc thực hiện
theo đúng đề cƣơng đã đƣợc hội đồng khoa học trƣờng Đại học Thái nguyên-
khoa Công nghệ thông tin phê duyệt, nội dung thực hiện trong đề cƣơng đã
đƣợc cán bộ hƣớng dẫn giao cho và kiểm soát. Nội dung luận văn, các phần
trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu
trách nhiệm.

hiện luận văn.
Tôi xin trân trọng cảm ơn TS. Nguyễn Huy Đức – Khoa Thông tin -
Máy tính, Trƣờng Cao đẳng Sƣ phạm Trung ƣơng, ngƣời thầy trực tiếp hƣớng
dẫn, đƣa ra ý tƣởng, định hƣớng, đóng góp các ý kiến chuyên môn và tận tình
giúp đỡ tôi trong suốt quá trình nghiên cứu và thực hiện luận văn thạc sĩ
ngành khoa học máy tính.
Tôi xin cảm ơn các bạn bè đồng nghiệp và gia đình đã giúp đỡ, đóng
góp ý kiến và động viên tôi trong suốt qua trình học, quá trình nghiên cứu và
hoàn thành luận văn . Tác giả Nguyễn Văn Tƣ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

iii
MỤC LỤC
Trang
Lời cam đoan……………………………………………………….…….………………i
Lời cảm ơn… …………………………………………….…………….……………….ii
Mục lục…………………… …………………………………….….…………… ……iii
DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT v

Chƣơng 3: KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ 47
3.1. Một số khái niệm về luật kết hợp có trọng số 47
3.2. Khai phá luật kết hợp trọng số không chuẩn hóa 49
3.3. Khai phá luật kết hợp trọng số chuẩn hóa 52

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

iv
3.3.1. Một số khái niệm về trọng số chuẩn hóa 52
3.3.2. Thuật toán khai phá luật kết hợp trọng số chuẩn hóa
(MINVAL(W)) 54
Kết luận chƣơng 3: 56
Chƣơng 4: THỰC NGHIỆM KHAI PHÁ LUẬT KẾT HỢP 57
4.1. Giới thiệu bài toán 57
4.2. Dữ liệu thực nghiệm 58
4.3. Xây dựng chƣơng trình 60
4.4. Thực nghiệm khai phá 61
4.5. Kết quả thực nghiệm 63
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 63
1. Những kết quả đã đạt đƣợc 63
2. Hƣớng phát triển của đề tài là: 64
TÀI LIỆU THAM KHẢO 65
PHỤ LỤC 67

T
Giao tác (transaction)C
k
k

Tập các ứng viên là tập mục có k mục dữ liệuL
k
Tập các tập mục thƣờng xuyên có k mục dữ liệuk-itemset
Tập mục gồm k mụcBFS
Breadth First Search
DFS
Depth First Search
FP-growth

Bảng 2.4: Ma trận giao tác của CSDL bảng 2.2 21
Bảng 2.5: Cơ sở dữ liệu DB 24
Bảng 2.6: Độ hỗ trợ của các mục 25
Bảng 2.7: Độ hỗ trợ của các tập mục 25
Bảng 2.8: Độ tin cậy của các luật 26
Bảng 2.9: CSDL giao tác minh hoạ cho thuật toán Apriori 31
Bảng 2.10: CSDL giao tác minh hoạ cho thuật toán FP- growth. 34
Bảng 3.1.a. Tập giao tác DB 48
Bảng 3.1.b. Thông tin của cửa hàng 48
Bảng 4.1: Dữ liệu đã trích chọn để khai phá 58
Bảng 4.2: Mã hóa các mặt hàng 59
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

1
MỞ ĐẦU
Trong những năm qua, việc nắm bắt, xử lý đƣợc thông tin đƣợc coi là
cơ sở của mọi hoạt động của đời sống xã hội, đặc biệt là trong sản xuất, kinh
doanh. Những thông tin tiềm ẩn mang tính dự đoán trong các khối dữ liệu là
rất lớn. Mỗi cá nhân hoặc tổ chức nào thu thập và hiểu đƣợc thông tin, hành
động dựa trên các thông tin đƣợc kết xuất từ các thông tin đã có sẽ đạt đƣợc
thành công trong mọi hoạt động. Chính vì lý do đó, việc tạo ra thông tin, tổ
chức lƣu trữ và khai phá ngày càng trở nên quan trọng và gia tăng không
ngừng.
Sự tăng trƣởng vƣợt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống
nhƣ: thƣơng mại, quản lý và khoa học …đã làm nảy sinh và thúc đẩy sự phát
triển của kỹ thuật thu thập, lƣu trữ, phân tích và khai phá dữ liệu không chỉ
bằng các phép toán đơn giản thông thƣờng nhƣ: phép đếm, thống kê mà đòi
hỏi cách xử lý thông minh hơn, hiệu quả hơn. Từ đó các nhà quản lý có đƣợc
thông tin có ích để tác động lại quá trình sản xuất, kinh doanh của mình đó là
tri thức. Các kỹ thuật cho phép ta khai phá đƣợc tri thức hữu dụng từ CSDL
(lớn) đƣợc gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá
luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu.
Một trong những nội dung cơ bản nhất trong khai phá dữ liệu và rất
thƣờng xuyên là phát hiện các luật kết hợp trong kho cơ sở dữ liệu khổng lồ,
nhằm tìm ra các tập mục thƣờng xuyên thƣờng xuất hiện đồng thời trong cơ
sở dữ liệu và rút ra các luật về ảnh hƣởng của tập mục thƣờng xuyên dẫn đến
sự xuất hiện của một (hay một tập) mục thƣờng xuyên khác nhƣ thế nào, do
vậy khai phá luật kết hợp trong kho cơ sở dữ liệu có ý nghĩa rất quan trọng, có
lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin cần thiết trong
nguồn cơ sở dữ liệu lớn.



Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

3
Chƣơng 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU
1.1. Quá trình phát hiện tri thức từ cơ sở dữ liệu.
Trong thời đại ngày nay, với sự phát triển vƣợt bậc của công nghệ
thông tin, các hệ thống thông tin có thể lƣu trữ một khối lƣợng lớn dữ liệu về
hoạt động hàng ngày của chúng. Lƣợng dữ liệu đƣợc lƣu trữ dẫn đến một đòi
hỏi cấp bách phải có những kỹ thuật mới, những công cụ tự động mới trợ giúp
con ngƣời một cách thông minh trong việc chuyển đổi một lƣợng lớn dữ liệu
thành thông tin hữu ích.
Một số nhà khoa học xem khai phá dữ liệu nhƣ là một cách gọi khác
của một thuật ngữ cũng rất thông dụng là khám phá tri thức trong cơ sở dữ
liệu (Knowledge Discovery in Databases – KDD), vì cho rằng mục đích của
quá trình khám phá tri thức là thông tin và tri thức có ích, nhƣng đối tƣợng mà
chúng ta phải xử lý rất nhiều trong suốt quá trình khám phá tri thức lại chính
là dữ liệu. Một số nhà khoa học khác thì xem khai phá dữ liệu nhƣ là một
bƣớc chính trong quá trình khám phá tri thức.
Hiểu quá trình khám phá, phát hiện tri thức ở đây là gì? Thông thƣờng
chúng ta coi dữ liệu nhƣ là một dãy các bit, các số và các ký hiệu, hoặc các
“đối tƣợng” đƣợc gửi cho một chƣơng trình dƣới một định dạng nhất định nào
đó. Chúng ta sử dụng các bit để đo lƣờng thông tin, khi sử dụng xem nó nhƣ
là dữ liệu đã đƣợc lọc bỏ dƣ thừa, đƣợc rút gọn tới mức tối thiểu. Bít đƣợc
dùng làm đơn vị đặc trƣng 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 học, đƣợc hiểu, đƣợc phát hiện ra. Nói cách
khác, tri thức có thể coi là dữ liệu có độ trừu tƣợng và tổ chức cao.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình 1.1. Quá trình khám phá tri thức

Bƣớc 1: Trích chọn dữ liệu (data selection): là bƣớc trích chọn những
tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data
warehouses)
Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): là bƣớc làm sạch dữ
liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, v
v), rút gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy
mẫu, . v. .v ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng,
v. . v ). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời
rạc hoá.
Kho
dữ
liệu
Các mẫu
Dữ liệu đã

trên biểu diễn theo dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu,
luật,. v. v. Đồng thời bƣớc này cũng đánh giá những tri thức khai phá đƣợc
theo những tiêu chí nhất định.
Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời
dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc
cũng có thể đƣợc lƣu và sử dụng lại.
1.2. Kiến trúc của hệ thống khai phá dữ liệu
Khai phá dữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ
liệu. Khai phá dữ liệu là quá trình chính trong khai phá tri thức từ cơ sở dữ
liệu.
Kiến trúc của một hệ thống khai phá dữ liệu có các thành [3,8] phần
nhƣ sau:
* CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các
tập CSDL, các trang tính hay các dạng khác của thông tin đƣợc lƣu trữ. Các
kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

7

(Data mining engine)
Kho dữ liệu
Các lƣu trữ
thông tin khác
Làm sạch ; tích hợp dữ liệu; lọc
Máy khai phá dữ liệu
Đánh giá mẫu
Giao diện đồ họa cho ngƣời
dùng
Cơ sở dữ
liệu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

8
* Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tƣơng tác với
các Modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng
đƣợc quan tâm. Nó có thể dùng các ngƣỡng về độ quan tâm để lọc mẫu đã
khai 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ụ, cung 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. Quá trình khai phá dữ liệu

Hình 1.3: Quá trình khai phá dữ liệu

Công việc tiếp theo sử dụng các thuật toán khác nhau để khai phá các
kiến thức tiềm ẩn trong kho dữ liệu sau khi đã xử lý và đƣợc thống kê tóm tắt
cùng các dữ liệu trực tiếp. Kết quả của quá trình khai phá dữ liệu là đạt đƣợc
nhiệm vụ đặt ra. 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.

Giải thuật
khai phá DL

Xác định
nhiệm vụ

Xác định dữ
liệu liên quan

Thu thập và
tiền xử lý DL

Thống kê
tóm tắt

Dữ liệu

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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

11
hết các phƣơng pháp khai phá dữ liệu đều coi các đối tƣợng ngoài cuộc là
nhiễu và loại bỏ chúng. Sự phân tích dữ liệu ngoài cuộc đƣợc coi nhƣ là phai
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 suấ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 đối tƣợng.
Phân tí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
hay khuynh 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 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ự.
Trong quá trình phát triển nền Kinh tế - Xã hội hiện nay, rất nhiều lĩnh
vực đa ngành, nhiệm vụ khai phá dữ liệu phải làm là phát hiện ra những giả
thuyết mạnh trƣớc khi sử dụng những công cụ tính toán thống kê, đó là những
công việc luôn thu hút các lĩnh vực khoa học nhƣ trí tuệ nhân tạo, cơ sở dữ
liệu, hiển thị dữ liệu, marketing, toán học, tin sinh học, nhận dạng mẫu, tính
toán thống kê …

Hình 1.4: Mẫu kết quả với phƣơng pháp cây quyết định
1.5.3. Phƣơng pháp K-Mean
Phân cụm cũng là một trong những chủ đề đƣợc quan tâm nhiều trong
nghiên cứu KPDL. Có nhiều phƣơng pháp đƣợc sử dụng trong phân cụm,
Thu nhập > T

Cho vay

Nợ < n

Không cho vay

Không cho vay

Nợ > n

Thu thập < T

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

13
phƣơng pháp k-Mean đƣợc coi là các kỹ thuật cơ bản của phân cụm. Với
phƣơng pháp này sẽ chia tập có n đối tƣợng thành k cụm sao cho các đối
tƣợng trong cùng một cụm thì giống nhau, các đối tƣợng khác cụm thì khác
nhau.
Đầu tiên chọn k đối tƣợng ngẫu nhiên, mỗi đối tƣợng đại diện cho tâm
của cụm (cluster mean or center). Dựa vào khoảng cách giữa tâm cụm với
mỗi đối tƣợng còn lại, gán mỗi đối tƣợng vào một cụm mà nó giống nhau
nhất. Sau đó, tính tâm mới của mỗi cụm. Quá trình đƣợc lặp lại cho đến khi
hàm tiêu chuẩn hội tụ (criterion function converges). Chẳng hạn sử dụng hàm











































Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

14
1.5.4. Các phƣơng pháp dựa trên mẫu
Phƣơng pháp này sử dụng khai phá chuỗi theo thời gian (Sequential
temporal patterns). Xét về mặt kỹ thuật thì 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. Một luật mô tả mẫu
tuần tự có dạng tiêu biểu X -> Y phản ánh sự xuất hiện của biến cố X sẽ dẫn
đến việc xuất hiện kế tiếp biến cố Y. 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 số lưu ý khi thực hiện các phương pháp khai phá dữ liệu:
Khi thực hiện các phƣơng pháp có những khó khăn phát sinh trong khai
phá dữ liệu, đó là vì dữ liệu trong thực tế thƣờng rất lớn, động và nhiễu, làm
thế nào để giải quyết sự dƣ thừa thông tin không thích hợp khi khai phá dữ
liệu.
- Khai phá với dữ liệu lớn: giả sử cơ sở dữ liệu với hàng trăm trƣờng,
hàng triệu bản ghi với kích thƣớc rất lớn, có thể lên đến GB. Phƣơng pháp
giải quyết nên chọn là đƣa ra lấy mẫu, lấy một ngƣỡng cho cơ sở dữ liệu nhƣ

dữ liệu là quá trình phân tích cơ sở dữ liệu nhằm phát hiện ra các thông tin
mới và giá trị, thƣờng thể hiện dƣới dạng các mối quan hệ chƣa biết đến giữa
các mục dữ liệu. Nhờ phân tích các dữ liệu mà các doanh nghiệp có khả năng
dự báo trƣớc một số hành vi ứng xử của khách hàng. Công nghệ thông tin
phát triển đồng nghĩa với việc phát triển các phần mềm ứng dụng. Phần mềm
khai phá dữ liệu là một công cụ phân tích dùng để phân tích dữ liệu. Nó cho
phép ngƣời sử dụng phân tích dữ liệu theo nhiều góc nhìn khác nhau, phân
loại dữ liệu theo những quan điểm riêng biệt và tổng kết các mối quan hệ đã
đƣợc bóc tách.
Hiện nay, kỹ thuật khai phá dữ liệu đang đƣợc áp dụng một cách rộng
rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau nhƣ:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

16
- Thƣơng mại: Phân tích dữ liệu bán hàng và thi trƣờng, phân tích đầu
tƣ, quyết định cho vay, phát hiện gian lận, …
- Thông tin sản xuất: Đ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, …
- Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen,
…khoa học địa lý: dự báo động đất, …
- Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet…
Những gì thu đƣợc từ khai phá dữ liệu thật đáng giá. Điều đó đƣợc
chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét
nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trƣờng hợp xét nghiệm
không hợp lý, tiết kiệm đƣợc nhiều kinh phí mỗi năm; Trong dịch vụ viễn
thông đã phát hiện ra những nhóm ngƣời thƣờng xuyên gọi cho nhau bằng
mobile và thu lợi hàng triệu USD; IBM Suft-Aid đã áp dụng khai phá dữ liệu
vào phân tích các lần đăng nhập Web vào các trang liên quan đến thị trƣờng
để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua