Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG


LÊ VĂN SƠN

NGHIÊN CỨU TẬP MỤC THƯỜNG XUYÊN
VÀ LUẬT KẾT HỢP 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


2.2.1. Khai phá tập mục thƣờng xuyên 16
2.2.2. Mở rộng bài toán khai phá tập mục thƣờng xuyên 17
2.3. Khai phá luật kết hợp 18
2.4. Một số tính chất của tập mục thƣờng xuyên và luật kết hợp 20
2.4.1. Một số tính chất của tập mục thƣờng xuyên 20
2.4.2. Một số tính chất của luật kết hợp. 20
2.5. Một số hƣớng tiếp cận trong khai phá luật kết hợp 21

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

ii
CHƢƠNG 3: MỘT SỐ PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG LUẬT
KẾT HỢP 23
3.1. Mở đầu 23
3.2. Thuật toán APRIORI khai phá tập mục thƣờng xuyên 24
3.3. Khai phá tập mục thƣờng xuyên theo hƣớng tiếp cận không sinh ứng
cử. 30
3.3.1. Thuật toán tạo cây FP-tree [4] 31
3.3.2. Duyệt cây FP-tree để sinh các tập mục thƣờng xuyên. 40
3.4. Khai phá tập mục cổ phần cao 43
3.5. Thuật toán FSM 47
3.5.1. Cơ sở lý thuyết của thuật toán FSM 47
3.5.2 Thuật toán FSM 48
3.6. Thuật toán AFSM 52
3.6.1 Cơ sở lý thuyết của thuật toán AFSM 52
3.6.2 Thuật toán AFSM 55
Chƣơng 4: XÂY DỰNG ỨNG DỤNG KHAI PHÁ TẬP MỤC CỔ PHẦN CAO
- THỬ NGHIỆM TRÊN CSDL BÁN HÀNG 59
4.1. Đặt bài toán 59
4.2. Thiết kế modul chƣơng trình và giải thuật 59


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

iv
DANH MỤC CÁC BẢNG

Bảng 2.1: Biểu diễn ngang của cơ sở dữ liệu giao tác 15
Bảng 2.2: Biểu diễn dọc của cơ sử dữ liệu giao tác 15
Bảng 2.3: Ma trận giao tác của cơ sở dữ liệu bảng 2.1 16
Bảng 2.4: Các tập mục thƣờng xuyên của CSDL bảng 2.3 với minsup=50% 17
Bảng 2.5: Các luật kết hợp sinh ra từ tập mục thƣờng xuyên BCE 21
Bảng 3.1: Ký hiệu mô tả trong thuật toán Apriori 26

Hình 3.3: Cây FP-tree sau khi xét giao tác với TID = T02 37
Hình 3.4: Cây FP-tree sau khi xét giao tác với TID = T03 38
Hình 3.5: Cây FP-tree sau khi xét giao tác với TID = T04 38
Hình 3.6: Cây FP-tree sau khi xét giao tác với TID = T05 39
Hình 3.7: Cây FP-tree sau khi xét giao tác với TID = T06 39
Hình 3.8: Cây FP-tree sau khi xét giao tác với TID = T07 40
Hình 3.9: Cây FP-tree sau khi xét giao tác với TID = T08 40
Hình 3.10: Cây FP-tree sau khi xét giao tác với TID = T09 41
Hình 3.11: Cây FP-tree CSDL bảng 3.4 42
Hình 3.12: Không gian tìm kiếm tập mục cổ phần cao theo thuật toán AFSM 59
Hình 4.1: Cửa sổ giao diện chƣơng trình 61
Hình 4.2: Cửa sổ thực hiện nhập CSDL 62
Hình 4.3: Nhập ngƣỡng cổ phần minShare 63
Hình 4.4: Cửa sổ thể hiện các bƣớc tìm tập mục cổ phần cao 64
Hình 4.5: Cửa sổ hiển thị kết quả tìm tập mục cổ phần cao 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

1
MỞ ĐẦU
Sự phát triển nhanh chóng của các ứng dụng Công nghệ thông tin và
Internet vào nhiều lĩnh vực đời sống xã hội nhƣ quản lý kinh tế, quản lý nhân
sự, khoa học kỹ thuật…đã mở ra nhiều cơ hội cho các tổ chức, doanh nghiệp
trong việc thu thập và xử lý thông tin. Hơn nữa các công nghệ lƣu trữ, phục
hồi dữ liệu phát triển một cách nhanh chóng, làm xuất hiện nhiều cơ sở dữ
liệu khổng lồ. Để khai thác có hiệu quả nguồn thông tin từ các cơ sở dữ liệu
khổng lồ trên, yêu cầu cấp thiết đặt ra là cần phải có những kỹ thuật, công cụ
để chuyển đổi kho dữ liệu khổng lồ thành những tri thức có ích. Từ đó các kỹ
thuật Khai phá dữ liệu trở thành một lĩnh vực đƣợc đặc biệt quan tâm trong

Kết luậ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Ề PHÁ DỮ LIỆU

1.1. Khai phá dữ liệu.
Trong kỷ nguyên bùng nổ công nghệ thông tin, các công nghệ lƣu trữ dữ
liệu ngày càng phát triển tạo điều kiện cho việc thu thập, lƣu trữ dữ liệu tốt
hơn. Đặc biệt trong lĩnh vực kinh doanh, các 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 các chủ doanh
nghiệp trong việc vạch ra các chiến lƣợc kinh doanh, kịp thời mang lại lợi
nhuận to lớn. Từ đó khiến các tổ chức, doanh nghiệp tạo ra một lƣợng dữ liệu

theo dữ liệu trong hồ sơ bệnh án. Hƣớng tiếp cận này thƣờng sử dụng các kỹ
thuật nhƣ học máy (Machine learning), cây quyết định (Decision tree), mạng
nơ ron nhân tạo (Neural network) Với phƣơng pháp này còn đƣợc gọi là học
có giám sát.
- Luật kết hợp (Association rules): 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 hiệ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.
Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin
– sinh học, tài chính, thị trƣờng chứng khoán
- Khai phá chuỗi theo thời gian (Sequential temporal patterns): 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.
- 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 dữ liệu tự nhiên (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ự giữ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

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

5
đố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 (Unsupervised learning).
- Mô tả khái niệm và tổng hợp hóa (Concept description and
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 tóm 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.3. Các cơ sở dữ liệu có thể khai phá
KPDL đƣợc ứng dụng rộng rãi nên có rất nhiều dạng dữ liệu khác nhau
có thể khai phá [7]. Sau đây là một số dữ liệu điển hình:

thông tin địa lý. Những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối
quan hệ giữa các đặc trƣng trong cơ sở dữ liệu không gian. Dạng của luật kết
hợp không gian có dạng X

Y, với X, Y là tập hợp những vị từ không gian.
Những thuật toán khai phá luật kết hợp không gian tƣơng tự nhƣ khai phá luật
kết hợp nhƣng thêm những vị từ về không gian.
- CSDL có yếu tố thời gian (Time – series databases): Giống nhƣ cơ sở
dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao gồm hai phần: Phần
thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin về thời gian
xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có yếu tố thời gian có
nhiều thông tin hơn những luật kết hợp cơ bản.
- CSDL đa phương tiện (Multimedia databases): CSDL đƣợc tích hợp
gồm nhiều dạng khác nhau nhƣ: âm thanh, hình ảnh, văn bản.
1.4. Quá trình khai phá dữ liệu.
- Trích chọn dữ liệu: 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.
- Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu (xử lý với dữ liệu không
đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán ), rút gọn dữ liệu (sử dụng
hàm nhóm và tính tổng, các phƣơng pháp nén dữ liệu, sử dụng histogram, lấy
mẫu, ), rời rạc hoá dữ liệu (rời rạc hoá dựa vào histogram, dựa vào entropy,

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

7
dựa vào phân khoảng, ). 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á.
- Biến đổi dữ liệu: Là bƣớc chuẩn hoá và làm mềm dữ liệu để đƣa dữ
liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá tiếp theo.
- Thuật toán khai phá dữ liệu: Lựa chọn các thuật toán khai phá dữ liệu

Tri thức
Đánh giá, giải
thích

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

8
- Điều trị trong y học (Medical treatment): Mối liên hệ giữa triệu chứng,
chuẩn đoán và phƣơng pháp điều trị.
- Phân lớp, tóm tắt văn bản và phân lớp các trang Web (Text ming &
Web mining)
- Tin - sinh (Bio - Informatics): Tìm kiếm, đối sánh các hệ gene và thông
tin di truyền, mối liên hệ giữa một số hệ gene 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.6. Khai phá dữ liệu và các lĩnh vực có liên quan
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, 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 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

- 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 hiện
không còn phù hợp
- Dữ liệu bị thiếu hoặc bị nhiễu

Khai phá dữ liệu
Thống kê

Cơ sở dữ liệu

Máy móc, trí tuệ
nhân tạo

Tài chính,
ngân hàng

Thuật toán

Các ngành
khoa học khác

Giáo dục
Thƣơng mại

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



11
ta coi sự thiếu vắng của các dữ liệu này là giá trị ẩn, chƣa biết và có thể đƣợc
tiên đoán bằng một số phƣơng pháp nào đó.
Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần
đƣợc quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối
liên hệ phức tạp với nhau trong CSDL đòi hỏi khai phá dữ liệu phải có các
giải pháp, các kỹ thuật để có thể áp dụng đƣợc, nhận ra đƣợc các mối quan hệ
này trong quá trình khai phá dữ liệu.

(transaction) T là một tập con của I, T I. Cơ sở dữ liệu giao tác là một tập
các giao tác DB = {T
1
, T
2
, , T
m
}. Mỗi giao tác đƣợc gán một định danh TID.
Một tập mục con X  I, gồm k mục phân biệt đƣợc gọi là một k – tập mục.
Giao tác T gọi là chứa tập mục X nếu XT.
- Biểu diễn cơ sở dữ liệu giao tác: Thƣờng đƣợc biểu diễn ở dạng biểu
diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác.

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

13
+ Biểu diễn ngang: 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 TID và một danh sách các mục dữ liệu trong giao
tác đó.
Ví dụ:
TID
Transaction
T01
{A, C, D}
T02
{B, C, E}
T03
{A, B, C, E}
T04
{B, E}

2
, , i
n
} đƣợc biểu diễn bởi ma trận nhị phân
M = (m
pq
)
mxn
ở đó:
1 khi i
q
 T
p

0 khi i
q
 T
p
m
pq
=

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

14
Ví dụ: Cơ sở dữ liệu bảng 2.1 biểu diễn ở dạng ma trận giao tác là:
TID
A
B
C

- Độ hỗ trợ (Support) của tập mục X trong CSDL giao tác DB đƣợc ký
hiệu sup(X): Là tỷ lệ phần trăm số giao tác trong CSDL có chứa X trên tổng
số các giao tác trong DB:
%100*
||
|}|{|
)sup(
DB
tXDBt
X



Ta có 0 ≤ sup(X) ≤ 1 với mọi tập mục X  I
Ví dụ: Bảng CSDL 2.3, cho tập mục X = ABC, ta có
- Số giao tác chứa tập mục X ={A,B,C} là 1
- Số giao tác trong CSDL là 4
Vậy
%25%100*
4
1
)sup( X

2.1.3. Tập mục thường xuyên (Frequent intemset)
Tập mục X đƣợc gọi là tập mục thƣờng xuyên với độ hỗ trợ minsup. Với
minsup là giá trị cho trƣớc đƣợc xác định bởi ngƣời sử dụng. Nếu độ hỗ trợ
của nó lớn hơn hoặc bằng minsup tức là: s(X) ≥ minsup
Bảng liệt kê các tập mục thƣờng xuyên (frequent-itemset) trong CSDL
bảng 2.3 với giá trị minsup = 50%


)sup()sup( YXYX 

Vậy độ hỗ trợ của luật kết hợp
YX 
chính là xác suất
)( YXP 
của
sự xuất hiện đồng thời X và Y trong một giao tác.
Ta có
1)sup(0  YX

- Độ tin cậy (Confidence) của luật kết hợp
YX 
, ký hiệu
conf(
YX 
), là tỷ lệ phần trăm giữa số giao tác chứa
YX 
và số giao tác
chứa X trong cơ sở dữ liệu DB.

)sup(
)sup(
)(
X
YX
YXconf




Các luật thoả mãn cả hai ngƣỡng độ hỗ trợ tối thiểu (minsup) và độ tin
cậy tối thiểu (minconf), tức thoả mãn
supmin)sup( YX
và
confYXconf min)( 
đƣợc gọi là luật kết hợp mạnh.

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

16
2.2. Khai phá tập mục thƣờng xuyên và mở rộng
2.2.1. Khai phá tập mục thường xuyên
Các nghiên cứu về khai phá tập mục thƣờng xuyên tập trung vào tìm các
thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có.
Bài toán khai phá tập mục thƣờng xuyên có thể chia thành hai bài toán nhỏ:
Tìm các tập mục ứng viên và các tập mục thƣờng xuyên.
Tập các ứng viên là tập mục mà có thể hy vọng nó là tập thƣờng xuyên.
Tập mục thƣờng xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng
ngƣỡng hỗ trợ tối thiểu cho trƣớc.
Có nhiều thuật toán tìm tập mục thƣờng xuyên, ta có thể phân chúng
theo hai tiêu chí sau:
- Phƣơng pháp duyệt qua không gian tìm kiếm.
- Phƣơng pháp xác định độ hỗ trợ của tập mục.
Phƣơng pháp duyệt qua không gian tìm kiếm đƣợc phân làm hai cách:
Duyệt theo chiều rộng (Breadth First Search-BFS) và duyệt theo chiều sâu
(Depth First Search – DFS).
Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ
của tất cả các tập mục ứng viên có (k-1) mục trƣớc khi tính độ hỗ trợ của các
tập mục ứng viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k
phải kiểm tra độ hỗ trợ của tất Hình 2.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên
2.2.2. Mở rộng bài toán khai phá tập mục thường xuyên
Bài toán khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng
trong thực tế nhƣng nó cũng có hạn chế, không đáp ứng đầy đủ yêu cầu của
ngƣời sử dụng. Ràng buộc về độ hỗ trợ của tập mục thƣờng xuyên chủ yếu
mang ngữ nghĩa thống kê, không thể hiện đƣợc vai trò khác nhau của các
thuộc tính cũng nhƣ đặc tính dữ liệu của chúng trong CSDL.
Nhằm khắc phục hạn chế của bài toán khai phá tập mục thƣờng xuyên,
đã có nhiều nghiên cứu mở rộng bài toán theo nhiều hƣớng khác nhau. Hƣớng
nghiên cứu mở rộng bài toán có nhiều ứng dụng thực tiễn là quan tâm đến cấu
trúc dữ liệu và mức độ quan trọng khác nhau của các mục dữ liệu, các thuộc
tính trong CSDL.
Sau đây là một số nghiên cứu mở rộng bài toán khai phá tập mục thƣờng
xuyên trong thời gian qua:
- Các kiểu thuộc tính khác nhau trong CSDL nhƣ nhị phân, đa phân,
định lƣợng, khi đó rút ra luật kết hợp gọi là luật kết hợp định lƣợng. Để tìm
BFS
DFS
Đếm
Giao
Đếm
Giao
AIS
Apriori
Dic
Partition

tập thƣờng xuyên, luật kết hợp đƣợc sinh từ X có dạng
YX
c

, với YX,
Y≠và YX= và c là độ tin cậy của luật thoả mãn c≥minconf
Với mỗi tập mục thƣờng xuyên X tìm thấy từ CSDL giao tác ta có thể dễ
dàng sinh các luật kết hợp theo nguyên tắc sau:
Với Y  X và Y ≠  thì luật đƣợc sinh ra có dạng nhƣ sau:

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

19
X – Y  Y (trong đó X – Y là hiệu của hai tập hợp)
Độ tin cậy của luật đƣợc tính nhƣ sau:
c(X-YY) =
)(
)(
YXs
Xs


Trong đó : s(X) là độ hỗ trợ của tập mục thƣờng xuyên
s(X-Y) là độ hỗ trợ của tập mục X-Y
Có thể coi tỉ số
)(
)(
YXs
Xs


EBC 
%67

Không
CBE  
%100

Có
BCE 
%67

Không

Bảng 2.5: Các luật kết hợp sinh ra từ tập mục thƣờng xuyên BCE

Trích đoạn Thuật toán tạo cây FP-tree [4] Cơ sở lý thuyết của thuật toán AFSM Đánh giá kết quả và hƣớng phát triển của chƣơng trình

---