BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

ĐỖ THỊ LAN ANH

KHAI PHÁ LUẬT KẾT HỢP
TRÊN MÔ HÌNH DỮ LIỆU DẠNG KHỐI

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH
Người hướng dẫn khoa học: PGS.TS Trịnh Đình Thắng

Hà Nội, 2013


1

LỜI CẢM ƠN
Bằng sự kính trọng và lòng biết ơn sâu sắc, em xin chân thành cảm ơn
PGS.TS Trịnh Đình Thắng, người đã tận tình hướng dẫn và giúp đỡ em
trong suốt quá trình làm luận văn.
Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ thông
tin, phòng Sau đại học trường Đại học Sư phạm Hà Nội 2, các thầy cô đã trực
tiếp giảng dạy các học phần trong khóa học đã tạo điều kiện thuận lợi cho em
trong cả quá trình học tập và nghiên cứu tại trường.
Xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp đã quan tâm, giúp
đỡ em trong thời gian nghiên cứu và hoàn thành luận văn.
Trong quá trình nghiên cứu, luận văn không tránh khỏi những thiếu sót.
Rất mong nhận được sự góp ý của quý thầy cô và bạn bè đồng nghiệp quan

Lời cảm ơn ........................................................................................................ 1
Lời cam đoan ..................................................................................................... 2
Mục lục ............................................................................................................... 3
Danh mục các ký hiệu và chữ viết tắt ............................................................... 6
Danh mục các bảng ............................................................................................ 7
Danh mục các hình vẽ ....................................................................................... 8
MỞ ĐẦU ........................................................................................................... 9
N

DUNG ...................................................................................................... 12

Chương 1. T NG

U N

KH

PH

D

L U

KH

PH

LU T K T H P ............................................................................................ 12
1.1. Khai phá dữ liệu ............................................................................... 12
1.1.1. Một số định ngh a về khai phá dữ liệu ..................................... 12

2. . . Phép chiếu ................................................................................. 35
2. . . Phép chọn .................................................................................. 36
2. . . Phép kết nối ............................................................................... 36
2. . . Phép chia ................................................................................... 37
2.5. Kết luận chương 2 ............................................................................. 37
Chương

. KH

D NG KH

PH

LU T K T H P TR N M

H NH D

L U

.................................................................................................. 38

3.1. Một số khái niệm ............................................................................ 38
3.1.1. Khối giao tác ............................................................................. 38
.1.2. Luật kết hợp............................................................................... 38
3.2. Thuật toán khai phá luật kết hợp trên mô hình dữ liệu dạng khối . 40
3.2.1. Giới thiệu thuật toán khai phá luật kết hợp ............................... 40


5



2

đvdl

Đơn vị dữ liệu

Đơn vị dữ liệu

3

BFS

Breadth First Search

Duyệt theo chiều rộng

4

DFS

Depth First Search

Duyệt theo chiều sâu


7

DANH MỤC CÁC BẢNG
Trang

truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một
khuynh hướng kỹ thuật mới đó là kỹ thuật khai phá dữ liệu. Khai phá dữ liệu
là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những
kho dữ liệu lớn. Có một số nhóm nghiên cứu đã đưa ra một số mô hình khai
phá dữ liệu, trong đó khai phá dữ liệu sử dụng luật kết hợp là một mô hình cơ
bản giúp tìm ra mối tương quan giữa những mục dữ liệu thường xuyên trong
cơ s dữ liệu được lưu trữ trong kho dữ liệu.
Bên cạnh đó, để có thể xây dựng được một hệ thống cơ s dữ liệu tốt,
người ta thường sử dụng các mô hình dữ liệu thích hợp.
Từ trước tới nay đã có một số loại mô hình được sử dụng trong các hệ
thống cơ s dữ liệu như: mô hình thực thể - liên kết, mô hình mạng mô hình
phân cấp, mô hình hướng đối tượng, mô hình dữ liệu datalog và mô hình quan
hệ. Trong những năm gần đây, việc nghiên cứu nhằm m rộng mô hình dữ


10

liệu quan hệ đã được nhiều nhà khoa học quan tâm. Theo hướng nghiên cứu
này một mô hình dữ liệu đã được đề xuất, đó là mô hình dữ liệu dạng khối.
Mô hình dữ liệu này có thể được xem là một m rộng của mô hình dữ liệu
quan hệ.
Đã có một số công trình nghiên cứu về mô hình dữ liệu dạng khối này.
Tuy nhiên việc khai phá dữ liệu trong mô hình dạng khối vẫn còn khá mới
mẻ. Chính vì những lý do trên mà tôi đã chọn đề tài: “ Khai phá luật kết hợp
trên mô hình dữ liệu dạng khối”
2. Mục đích nghiên cứu
Trên cơ s nghiên cứu khai phá luật kết hợp theo thuật toán

priori đề



CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
VÀ KHAI PHÁ LUẬT KẾT HỢP
1.1 Khai phá dữ liệu
1.1.1.

t ố định nghĩa

khai phá dữ liệu

Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức
trong cơ s dữ liệu.

uá 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, … .
uá trình khai phá tri thức được Han và Kamber mô tả trong hình 1.1:
Dữ liệu thực
Mẫu ước lượng
Cơ s tri thức
Công cụ khai phá DL
Kho dữ liệu

Cơ s dữ liệu

Kho dữ liệu

Nơi chứa DL khác

Hình 1.1 Khai phá tri thức trong cơ sở dữ liệu

chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các k thuật
này gồm có: phân cụm (clustering), tóm tắt (summarization), trực quan hóa
(visualization), phân tích sự phát triển và độ lệch (evolution and deviation
analysis), phát hiện luật kết hợp (association rules), ...


14

 Mô hình khai phá dữ liệu suy di n: có nhiệm vụ đưa ra các dự
đoán dựa vào các suy di n trên dữ liệu hiện thời. Các k thuật này gồm
có: phân lớp (classification), hồi quy (regression), ...
1.1.3. Các bài toán thông dụng trong khai phá dữ liệu
Trong khai phá dữ liệu, các bài toán có thể phân thành bốn loại chính
[2]:
 Phân lớp (Classification): Là bài toán thông dụng nhất trong
khai phá dữ liệu.

ới một tập các dữ liệu huấn luyện cho trước và sự huấn

luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại
(classifier) dùng để phân các dữ liệu mới vào một trong những lớp (còn gọi là
loại) đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu Phân
lớp.
 Dự đoán (Prediction):

ới mô hình học tương tự như bài toán

Phân lớp, lớp bài toán Dự đoán sẽ học ra các bộ dự đoán. Khi có dữ liệu mới
đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho
hàm cần dự đoán. Bài toán tiêu biểu trong nhóm này là dự đoán giá

ảnh vi n thám, cảnh báo hỏng hóc trong các hệ thống sản xuất, … Các kỹ
thuật khai phá dữ liệu đã được áp dụng thành công trong việc dự đoán tái sử
dụng điện năng cho các công ty cung cấp điện, lưu lượng vi n thông cho các
công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của
sản phẩm trên thị trường cho các công ty tài chính, ….
Ngoài ra, khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như
phân tích các kết quả phòng chống và điều trị một số loại bệnh, phân tích tác
hại của ma tuý, phát hiện tội phạm hay tăng cường an ninh xã hội, ....

iệc

vận dụng thành công đã mang lại những hiệu quả thiết thực cho các hoạt
động di n ra hàng ngày trong đời sống.
1.1.5.

t ố khó khăn trong khai phá dữ liệu


16

- Cơ sở dữ liệu lớn: Các tập dữ liệu cần xử lý trong khai phá dữ
liệu thường có kích thước cực kỳ lớn về cả số lượng các bản ghi và số lượng
các thuộc tính. Trong thực tế, kích thước của các tập dữ liệu trong khai phá dữ
liệu thường

mức tera-byte (hàng ngàn giga-byte).

ới kích thước như thế,

thời gian xử lý thường cực kỳ dài. Mặc dù kích thước bộ nhớ trong của máy

iệc phát hiện tri thức từ các dạng dữ liệu h n hợp này là

một thách thức đối với khai phá dữ liệu.
1.2. Khai phá luật kết hợp
t ố khái niệm

1.2.1.

1.2.1.1. Cơ sở dữ liệu giao tác
Định nghĩa 1.1 [2], [4], [5], [6]
Cho I = {x1, x2, …, xn} là tập hợp các mục dữ liệu. M i x i gọi là một
mục dữ liệu hay là một thuộc tính. Một tập con {x i1, xi2, …, xik}  được gọi
là một giao tác trên . Đặt ti = {xi1, xi2, …, xik}, ti gọi là định danh của giao tác
{xi1, xi2, …, xik}. Một tập hợp gồm m định danh giao tác T = {t 1, t2, …, tm},
với m bất kỳ được gọi là một cơ s dữ liệu giao tác trên .
M i tập con X 

với ||X|| = k được goi là tập k-mục dữ liệu hay k-

thuộc tính của (trong trường hợp không quan tâm đến số mục dữ liệu của X,
ta gọi tắt X là tập mục dữ liệu), m i tập con S  T gọi là tập định danh giao
tác.
1.2.1.2. Biểu diễn cơ sở dữ liệu giao tác
Có 2 cách biểu di n tập cơ s dữ liệu giáo tác: Biểu di n ngang và biểu
di n dọc [2], [4].
 Biểu di n ngang: Một cơ s dữ liệu là một danh sách các giao
tác. M i giao tác có một định danh giao tác (tid) và một danh sách những mục
dữ liệu trong giao tác đó.
Ví dụ 1.1
Mục dữ liệu


A, C

t8

A, B, C, E

t9

A, B, C

t10

A, B, E, G

Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác
 Biểu di n dọc: Một cơ s dữ liệu là một danh sách những mục dữ
liệu, với m i mục dữ liệu có một danh sách tất cả các định danh của các giao
tác chứa mục dữ liệu này.
Mục dữ liệu

Định danh giao tác

A

t1, t4, t5, t7, t8, t9, t10

B

t1, t2, t3, t4, t6, t8, t9, t10



19

Cho I = {I1, I2, …, q} là tập các đơn vị dữ liệu (đvdl). Ta quy ước m i
giao tác làm phát sinh một tập con các đvdl của . Cho D là tập gồm m giao
tác, m i giao tác T cho kết quả là tập con các đvdl T  I.
í dụ, ta có tập đvdl tại một siêu thị:
= {Bánh mì, bơ, sữa , trứng, bánh ngọt, đường, …}. Khách hàng
mua bánh mì, bơ, sữa. Ta nói rằng, khách hàng

đã

đã phát sinh giao tác

tA = {Bánh mì, bơ, sữa}.
Giả sử, khảo sát tập giao tác D gồm m giao tác.

ới m i tập đơn vị dữ

liệu X  , xét số lượng p các giao tác trong D làm xuất hiện các đơn vị dữ
liệu có trong X.
Ký hiệu: v(X) là tần suất xuất hiện của tập đvdl X trong tập giao tác D.
Ta có v( X ) 

p
m

Ký hiệu: |Z| là lực lượng của tập Z.
Định nghĩa 1.2: Ta gọi luật kết hợp giữa hai tập đvdl X và Y (với X, Y là hai

1.2.2. Khai phá luật kết hợp
1.2.2.1. Bài toán khai phá luật kết hợp
Phát biểu bài toán:
Đầu vào: - Cho một tập mục dữ liệu I = { I1, I2, …, n}
- Cho một cơ s dữ liệu giao dịch D (m giao dịch)
-

Độ h trợ tối thiểu Min_Supp và độ tin cậy tối thiểu Min_Conf

Đầu ra: - Tập các luật kết hợp R: X  Y sao cho Supp(X  Y) 
Min_Supp và Conf (X  Y)  Min_Conf.
Giải quyết bài toán: Bài toán khai phá luật kết hợp trên một cơ s dữ liệu
được chia thành hai bài toán nhỏ:
 Bài toán thứ nhất là tìm tất cả các tập mục dữ liệu có độ h trợ
thỏa mãn ngưỡng tối thiểu cho trước, gọi là tập các tập mục dữ liệu thường
xuyên.
 Bài toán thứ hai là tìm ra những luật kết hợp từ những tập mục
dữ liệu thường xuyên thỏa độ tin cậy tối thiểu cho trước.
Bài toán thứ hai được giải quyết như sau: Giả sử ta có tập các mục dữ
liệu thường xuyên X, những luật kết hợp theo ngưỡng tin cậy tối thiểu c0 trên
tập mục dữ liệu thường xuyên này được phát sinh ra bằng cách: Y  X, ta
kiểm tra độ tin cậy của luật X\Y  Y có thỏa ngưỡng tin cậy tối thiểu cho
trước hay không.
Bài toán thứ hai là đơn giản, hầu hết các nghiên cứu về luật kết hợp tập
trung

bài toán thứ nhất.

1.2.2.2. Cách tiếp cận khai phá luật kết hợp


ới cơ s dữ liệu có n mục dữ liệu, ={x1, x2, …, xn}, thì không gian
tìm kiếm là tập tất cả các tập con của , đây là bài toán NP khó, nếu không có
phương pháp duyệt thích hợp thì bài toán không giải được khi n đủ lớn.
Phương pháp xác định độ h trợ của tập mục dữ liệu X  được phân
làm hai cách: Cách thứ nhất là đếm số giao tác trong cơ s dữ liệu chứa X.
Cách thứ hai là tính phần giao của các tập định danh giao tác chứa X.


22


23

Ta có thể phân loại các thuật toán như sau:

Đếm

BFS

Giao
Đếm

AIS
APRIORI
DIC
PARTITION
FP-GROWTH

DFS
Giao


phần tiếp theo của luận văn, trong đó thuật toán ứng với bài toán thứ hai là
tương đối đơn giản. ì vậy, trong các thuật toán được phát triển

chương này

sẽ tập trung giải quyết cho bài toán thứ nhất.
1.2.2.4. Nhận xét về bài toán khai phá luật kết hợp
Bài toán tìm tất cả các tập thường xuyên đối với một cơ s dữ liệu là
bài toán có độ phức tạp là hàm mũ. Nếu thực hiện “vét cạn” thì với các tập
thường xuyên, ta có không gian tìm kiếm gồm 2 q phần tử (với q =  là số
phần tử của tập đơn vị dữ liệu ). Tương tự nếu ‘vét cạn’ đối với tập luật kết
hợp, thì không gian tìm kiếm gồm

q

phần tử. Như vậy, với các CSDL lớn thì

số phần tử q của tập có thể hàng trăm hoặc hàng nghìn và số giao tác m có
thể là hàng triệu hoặc hơn, thì chi phí về thời gian thực hiện của thuật toán là
không khả thi.
Để giải quyết vấn đề này, cần phải xây dựng thuật toán tìm kiếm các
tập thường xuyên cũng như các luật kết hợp sao cho có thể thực hiện được
trên máy tính với những tập dữ liệu tương đối lớn. Thuật toán

priori đã tìm

cách thu gọn đáng kể không gian tìm kiếm các tập thường xuyên và là thuật
toán căn bản trong việc tìm ra các luật kết hợp. Ý tư ng của thuật toán này
dựa trên các mệnh đề ban đầu sau đây.