HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN XUÂN KHUÊ

MỘT SỐ TÍNH CHẤT CỦA LUẬT KẾT HỢP
TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN NGANG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01.01

TÓM TẮT LUẬN VĂN THẠC SỸ


Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công
nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

1 MỞ ĐẦU
Hiện nay, lượng thông tin được lưu trữ trên các thiết bị điện tử không ngừng tăng lên.
Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Nói một cách hình ảnh là chúng ta
đang “ngập” trong dữ liệu nhưng lại “đói” tri thức. Câu hỏi đặt ra là liệu chúng ta có thể
khai thác được gì từ những “núi” dữ liệu ấy không?
Data Mining ra đời như một hướng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên.
Khá nhiều định nghĩa về Data Mining, tuy nhiên có thể tạm hiểu rằng Data Mining như 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 được
tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.
Khai phá dữ liệu bao hàm rất nhiều hướng tiếp cận. Các kỹ thuật chính được áp dụng
trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực cơ sở dữ liệu, machine learning, trí tuệ
nhân tạo, lý thuyết thông tin, xác suất thống kê, và tính toán hiệu năng cao. Các bài toán chủ
yếu trong khai phá dữ liệu là phân lớp/dự đoán (classification/prediction), phân cụm
(clustering), khai phá luật kết hợp (association rules mining), khai phá chuỗi (sequence

k
, tính chất t có thỏa mãn trong
các R
i
không?
Bố cục của luận văn gồm 3 chương:
Chương 1. Nghiên cứu tổng quan
- Nghiên cứu tổng quan về khai phá dữ liệu
- Giới thiệu chung về khai phá dữ liệu
- Quy trình và các kỹ thuật khai phá dữ liệu
- Các ứng dụng của khai phá dữ liệu
- Nghiên cứu về cơ sở dữ liệu phân tán
Chương 2. Khai phá luật kết hợp
- Các luật trong khai phá tri thức
- Khai phá luật kết hợp
- Một số dạng luật kết hợp
- Một số thuật toán khai phá luật kết hợp
Chương 3: Một số tính chất của luật kết hợp
- Giới thiệu
- Các định nghĩa
- Giới thiệu một số tính chất của luật kết hợp trong cơ sở dữ liệu phân tán ngang.

3 Chương 1 - NGHIÊN CỨU TỔNG QUAN
1.1. Tổng quan về khai phá dữ liệu

Phân nhóm dữ liệu [2, 3]
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ững đối
tượng vào trong những lớp tương đương. 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.
Hồi quy (Regression):
Là việc xét một hàm ánh xạ từ một tập dữ liệu thành một biến dự đoán có giá trị thực.
Nhiệm vụ hồi qui 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 rời rạc [3, 4].
Tổng hợp (summarization):
Là công việc liên quan đến các phương pháp tìm kiếm một mô tả cô đọng cho tập
con dữ liệu [2, 4]. Các kỹ thuật tổng hợp thường được áp dụng trong việc phân tích dữ liệu
có tính thăm dò và báo cáo tự động.
Phát hiện sự thay đổi và độ lệch (change and deviation dectection):
Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa
vào các giá trị chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung của
tập con dữ liệu và nội dung mong đợi. [2, 3].
1.1.4. Các bài toán thông dụng trong khai phá dữ liệu
Trong khai phá dữ liệu (KPDL), các bài toán có thể phân thành bốn loại chính [5]:
Phân lớp (Classification):
Là bài toán thông dụng nhất trong KPDL. Vớ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
5 (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
Cơ sở dữ liệu đa phương tiện
Số lượng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi, duyệt
web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang phát triển với tốc
độ rất cao, khai phá thông tin trên web (web mining) đã trở thành một lĩnh vực nghiên cứu
chính của khai phá dữ liệu, được các nhà nghiên cứu đặc biệt quan tâm.
1.1.6. Các ứng dụng của khai phá dữ liệu
- Phân tích dữ liệu và hỗ trợ ra quyết định (Analysis & decision 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à thông tin di
truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền.
- Nhận dạng.
- Tài chính và thị trường chứng khoán (Finance & stock market): Phân tích tình hình
tài chính và dự đoán giá cổ phiếu.
- Bảo hiểm (Insurance).
- Giáo dục (Education).
1.1.7. Khai phá dữ liệu và các lĩnh vực liên quan
Phát hiện tri thức và khai phá dữ liệu được coi là trung tâm của nhiều 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.
Đặ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

1.2.3. Tại sao phải phân tán CSDL?
Trong thực tế chúng ta luôn cần phân tán CSDL là vì:
- Chia để trị, chia CSDL thành các CSDL con để tiện giải quyết và quản trị
chúng.
- Do tầm hoạt động, tầm địa lý của CSDL rộng, lớn nên bắt buộc phải phân tán
CSDL theo các khu vực.
- Do yêu cầu bảo mật dữ liệu nên chúng ta phải phân tán dữ liệu thành các phần
con để dễ bảo vệ dữ liệu.
8 - Một lý do quan trọng bắt buộc chúng ta phải phân tán (phân rã) cơ sở dữ liệu
là để đảm bảo tính nhất quán, ổn định, không dư thừa dữ liệu mỗi khi thao tác
và truy xuất trên CSDL.
1.2.4. Phân rã dọc
Định nghĩa 1.3 Phân rã dọc
Phép phân rã dọc quan hệ R trên tập thuộc tính A = {A1, A2, , An} thành các quan
hệ R1, R2, , Rk tương ứng trên các tập thuộc tính U1, U2, , Uk là tách R thành k quan hệ
thỏa mãn các yêu cầu sau:
(i) A = U1

U2



Uk
(ii) R = R1*R2* *Rk. Trong đó * là phép nối tự nhiên

9 Chương 2 - KHAI PHÁ LUẬT KẾT HỢP
2.1. Luật kết hợp
2.1.1. Giới thiệu về luật kết hợp
 Khai phá luật kết hợp: Là tìm các mẫu phổ biến kết hợp nhân quả giữa các tập đối
tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác.
2.1.2. Các khái niệm cơ bản
- Gọi I = {I
1
, I
2,
, I
m
} là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là một mục.
- Gọi D là một cơ sở dữ liệu chứa n giao dịch, trong đó mỗi bản ghi Ti là một giao
dịch và chứa các tập mục, X  I:
Định nghĩa 2.1:
Độ hỗ trợ của X, ký hiệu support(X), là tỷ lệ phần trăm của các giao dịch hỗ trợ X
trên tổng các giao dịch trong D, nghĩa là:

| { / } |
( )
| |
T D X T
support X

support
Tong so giao dich


Định nghĩa 2.4:
10 Độ tin cậy (confidence) là tỷ lệ phần trăm giữa số lượng các giao dịch chứa cả X và
Y
( )
X Y

với số giao dịch có chứa X. Đơn vị tính %.
Tong so luong giao dich ho tro X Y
confidence
So luong giao dich ho tro X



Ý nghĩa của độ hỗ trợ và độ tin cậy:
 Độ hỗ trợ của luật biểu diễn "sức mạnh" của luật. Luật có ảnh hưởng như thế nào
trong toàn bộ hệ thống.
 Độ tin cậy biểu diễn mức độ "đúng" của quy tắc X

Y
Việc khai phá các luật kết hợp từ cơ sở dữ liệu chính là việc tìm tất cả các luật có độ
2.1.4. Tối ưu luật
2.2. Một số thuật toán khai phá luật kết hợp
2.2.1. Thuật toán khai phá luật kết hợp tuần tự
2.2.1.1. Thuật toán Apriori
Apriori là thuật toán khai phá luật kết hợp do RaKesh Agrawal, Tomasz Imielinski,
Anin Sawami đưa ra vào năm 1993, là nền tảng cho việc phát triển những thuật toán sau
này. Thuật toán sinh tập mục ứng cử từ những tập mục phổ biến ở bước trước, sử dụng kĩ
thuật “tỉa” để bỏ đi tập mục ứng cử không thỏa mãn ngưỡng hỗ trợ cho trước. Thuật toán
được trình bày chi tiết trong [7].
2.2.1.2. Thuật toán Apriori - TID
Tương tự thuật toán Apriori, thuật toán Apriori-TID cũng sử dụng tập phổ biến (k-1)
phần tử để tạo ra các tập mục ứng cử k phần tử trước khi bắt đầu mỗi giai đoạn.
Điểm khác nhau chủ yếu của thuật toán này so với thuật toán Apriori là: nó không sử
dụng cơ sở dữ liệu để tính độ hỗ trợ trong các giai đoạn k > 1. Thay vào đó nó sử dụng mã
khóa của các tập mục ứng cử đã sử dụng trong giai đoạn trước [7].
2.2.1.3. Thuật toán Apriori - Hybrid
Thuật toán này dựa vào ý tưởng “không cần thiết phải sử dụng cùng một thuật toán
cho tất cả các giai đoạn lên trên dữ liệu”. Như đã đề cập ở trên, thuật toán Apriori thực thi
hiệu quả ở các giai đoạn đầu, thuật toán Apriori-TID thực thi hiệu quả ở các giai đoạn sau.
Phương pháp của thuật toán Apriori-Hybrid là sử dụng thuật toán Apriori ở các giai đoạn
đầu và chuyển sang sử dụng thuật toán Apriori-TID ở các giai đoạn sau, được trình bày chi
tiết trong [7].
2.2.1.4. Thuật toán FP-Growth
Thuật toán được trình bày chi tiết trong [8].
Ý tưởng: Dùng đệ quy để gia tăng độ dài của mẫu phổ biến dựa trên cây FP-Tree và
các mẫu được phân hoạch.
Phương pháp thực hiện:
12

m-1
cho các bộ xử lý sao cho mỗi bộ xử
lý P
i
có thể sinh ra một C
p
i
(p > m) duy nhất độc lập với các bộ xử lý khác (C
p
i


C
p
j
= Ø,
i≠j).
13 Trong cùng một thời điểm, dữ liệu được phân chia lại sao cho một bộ xử lý có thể
sinh các tập mục ứng cử trong C
p
i
một cách độc lập với tất cả các bộ xử lý khác. Tùy vào
tính tối ưu của việc phân chia tập mục, một số phần cơ sở dữ liệu có thể có các bản sao trên
một số bộ xử lý.

biến toàn cục L, trong đó L
k
là tập phổ biến toàn cục k phần tử.
2.2.3.2. Thuật toán khai phá luật kết hợp phân tán DMAR
Thuật toán DMAR được trình bày chi tiết trong [10].
Thuật toán DMAR cho việc khai phá luật kết hợp phân tán sử dụng kỹ thuật meta-
learning. Đó là khai phá các tập phổ biến cục bộ mà chúng được sử dụng như là siêu tri thức
tại mọi điểm trong hệ thống phân tán và tạo ra các tập ứng cử phổ biến toàn cục từ những
siêu tri thức này, sau đó quét cơ sở dữ liệu giao dịch một lần để thu được các tập phổ biến
toàn cục. Thuật toán này có hiệu năng khai phá cao hơn và yêu cầu số lượng các giao tiếp
thông điệp ít hơn.
14 Chương 3 – MỘT SỐ TÍNH CHẤT CỦA LUẬT KẾT HỢP
3.1. Các khái niệm cơ bản của hệ khai thác dữ liệu
3.1.1. Hệ tin
Định nghĩa 3.1 Hệ tin
Hệ tin là bộ bốn thành phần S = (U, A, V, f). Trong đó:
- U = {o
1
, o
2
, o
m
}, m


Đôi khi để cho tiện ta có thể viết hệ tin S = (U, A). Với V, f coi như xác định.
Trong nhiều tài liệu các tác giả thường viết a(o) = v thay cho f(o, a) = v.
3.1.2. Hệ khai thác dữ liệu
Định nghĩa 3.1.
Hệ khai thác dữ liệu là hệ tin S = (O, I, V, f). Trong đó:
Tập O = {o
1
, o
2
, , o
m
} được gọi là tập các hóa đơn.
Tập I = {i
1
, i
2
, , i
n
} được gọi là tập các mục (ItemSet). Tập V = {0, 1}.
Giá trị f (o
j
, i
k
) =1 cho ta biết hóa đơn o
j
chứa mặt hàng i
k
và f (o
j
, i



} được gọi là các tập phổ biến
với ngưỡng

, gọi tắt là các tập phổ biến.
Đặt FS(

) là họ các tập X mà support (X)



. Hay
FS(

) = {X

I : support(X)



}.
3.1.3.2 Thuật toán tìm các tập phổ biến
Cho hệ khai thác dữ liệu S = (O, I, V, f).
Thuật toán Apriori tìm hết các tập phổ biến với ngưỡng minsupp FS(minsupp) = {X

I : support(X)

minsupp}.
Thuật toán

X
= k & X = Y

Z
trong đó Y, Z

F
k-1
& support(X)

minsupp}
Với k = 2, 3, Thuật toán sẽ dừng khi F
k
= rỗng
Tập tất cả các tập phổ biến FS(minsupp) = F
1


F
2




F
k-1

3.1.4. Luật kết hợp
3.1.4.1. Luật kết hợp
Cho hệ S = (O, I, V, f); X, Y

Y) =
support (X Y)
support (X)

.
3.1.4.3. Luật quan trọng
Cho hệ S = (O, I, V, f), minconf

(0,1], X, Y

I.
Định nghĩa 3.5.
Luật X

Y được goi là luật quan trọng (hay luật tin cậy) trong S với ngưỡng
minconf nếu CF
S
(X

Y)

minconf.
3.1.4.4. Thuật toán tìm luật quan trọng
Luật kết hợp tin cậy hay luật quan trọng: Một luật được xem là tin cậy nếu độ tin
cậy confidence của nó lớn hơn hoặc bằng một ngưỡng minconf ]1,0(

nào đó do người dùng
xác định. Ngưỡng minconf phản ánh mức độ xuất hiện của Y khi cho trước X.
Thuật toán tìm luật quan trọng
Input: S = (O, I, V, f) là hệ toàn cục; minsup, minconf

17 - Pha 1: Tìm tất cả các tập mục phổ biến từ cơ sở dữ liệu tức là tìm tất cả các tập
mục X thỏa mãn support(X) ≥ minsupp.
- Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha 1.
Nếu X là một tập mục phổ biến nhiều hơn 1 phần tử thì các luật kết hợp được sinh từ
X có dạng:
X’  X \ X’; trong đó:
X’ là tập con khác rỗng của X.
X\X’ là hiệu của hai tập hợp X và X’ và conf(X’  X\X’) ≥ minconf.
3.2. Một số tính chất của tập phổ biến trong hệ S = (O, I, V, f)
Tính chất 3.1:
Nếu A  B, A, B là các tập mục thì support(A) ≥ support(B)
Tính chất 3.2:
Một tập mục A không phải tập phổ biến với ngưỡng tối thiểu minsupp nghĩa là
support(A) < minsupp thì mọi tập cha B của A sẽ không phải là tập mục phổ biến.
Tính chất 3.3:
Nếu tập mục B là một tập mục phổ biến, nghĩa là support(B) ≥ minsupp thì mọi tập
con A của B đều là tập phổ biến.
Tính chất 3.4: (Không hợp luật kết hợp)
Nếu luật X

Z và Y

Z là luật quan trọng trong S thì không nhất thiết luật X
3.3. Một số tính chất của tập phổ biến và luật kết hợp trong hệ phân tán ngang
3.3.1. Hệ phân tán ngang
Giả sử ta có hệ khai thác dữ liệu S = (O, I, V, f). S được tách ngang thành m hệ thống
con S
1
, S
2
, …, S
m
. Với S
j
= (O
j
, I, V, f
j
) ; O =

O
j
; O
i
 O
j
=  với mọi i ≠ j và f
j
là co của

Hệ S = (O, I, V, f) ta sẽ gọi là hệ tập trung toàn cục.
Mỗi S
j
= (O
j
, I, V, f
j
) là một hệ con hay một trạm.
Thí dụ 3.3:
Xét S = (O, I, V, f) với O = {o
1
, o
2
, o
3
, o
4
, o
5
, o
6
, o
7
, o
8
}; I = {i
1
, i
2
, i

o
3
1 1 0 1 1 0
o
4
1 0 1 0 0 0
o
5
1 0 1 1 0 1
o
6
1 0 0 0 0 1
o
7
1 1 0 0 0 0
o
8
1 1 0 0 0 0

Ta có thể tách ngang S thành S
1
, S
2
, S
3
như sau:
S
1
= ({o
1

1
1 1 1 1 1 1
o
2
1 1 0 0 1 1

S
2
= ({o
3
, o
4
, o
5
}, I, V, f) = (O
2
, I, V, f) với f: O
2
×I  V
Bảng 3.12 – Bảng biểu diễn tập hóa đơn trạm S
2
i
1
i
2
i
3
i
4
i

1
i
2
i
3
i
4
i
5
i
6

o
6
1 0 0 0 0 1
o
7
1 1 0 0 0 0
o
8
1 1 0 0 0 0
3.3.2. Một số kết quả
Cho S = (O, I, V, f) là hệ tập trung toàn cục; |O| = M. Ta tách ngang S thành m trạm
S
j
= (O
j
, I, V, f); j = 1, 2, , m và mỗi trạm có số hóa đơn là |O
j
| =M


I ta luôn có bất đẳng thức:
sup
S
(X) <
1
sup (X)
m
Sj
j


Tính chất 3.11.
Cho hệ S = (O, I, V, f). Với mọi cặp X, Y

I ta luôn có bất đẳng thức:
CF
S
(X

Y) < Y) X (
1



m
j
Sj
CF
Tính chất 3.12.

3.3.3. Đánh giá.
Bộ dữ liệu kiểm thử là cơ sở dữ liệu ngân hàng với 11 thuộc tính và số lượng giao
dịch là 600.
Qua kiểm thử ta thấy phần lớn các luật xuất hiện trong hệ tập trung thì cũng xuất hiện
trên các trạm con tuy nhiên cũng có thể xảy trường hợp độ hỗ trợ và độ tin cậy không đảm
bảo đồng thời cùng xuất hiện trên một trạm S
j
nào đó.
21 KẾT LUẬN
Sau một thời gian tìm hiểu, nghiên cứu đến nay luận văn “MỘT SỐ TÍNH CHẤT CỦA
LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN NGANG” đã được hoàn thành. Về cơ
bản luận văn đáp ứng được các nội dung đã đăng ký trong đề cương. Cụ thể luận văn đã đạt
được một số kết quả chính sau:
 Tìm hiểu khái quát một số thuật toán khai phá luật kết hợp.
 Phát biểu bài toán hệ khai thác dữ liệu thực chất là một hệ tin.
 Đúc kết được các tính chất của các tập phổ biến trong hệ tập trung.
 Đề xuất và phát hiện, chứng minh một số các tính chất của tập phổ biến, luật kết
hợp trong cơ sở dữ liệu tập trung và phân tán ngang.
Do thời gian có hạn nên luận văn không thể tránh được các thiếu sót, các mặt còn hạn
chế chẳng hạn như:
 Chưa có kiểm thử các tính chất tìm được trên dữ liệu thực tế hoặc một cơ sở dữ
liệu lớn.
 Chưa có đề xuất cài đặt hoặc cải tiến các thuật toán khai phá luật kết hợp đã có
dựa trên các tính chất tìm được.