NGHIÊN CỨU TÍNH ỨNG DỤNG CỦA KHAI THÁC
LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU GIAO DỊCH
RESEARCH ON THE APPLICATION OF ASSOCIATION RULES IN
TRANSACTION DATABASE

TRƯƠNG NGỌC CHÂU – PHAN VĂN DŨNG
Trường Đại học Bách Khoa, Đại học Đà Nẵng

TÓM TẮT
Hiện tại, đã có một số ứng dụng kết quả của việc khai thác luật kết hợp trong cơ sở dữ liệu. Tuy nhiên,
chưa có nhiều nghiên cứu nói lên tính ứng dụng của nó, các nghiên cứu chỉ mang tính đơn thể, tự phát
và chưa có một giải pháp tổng quát nào vì phạm vi sử dụng kết quả của việc khai thác là rất đa dạng và
phong phú. Trong bài báo này, chúng tôi đề xuất một giải pháp tổng quát cho tính ứng dụng của việc
khai thác luật kết hợp trong cơ sở dữ liệu giao dịch.
ABSTRACT
Currently, there have been application results of the utilization of the association rules in database.
However, there have not been many studies on the practical applications because they are isolated and
fail to put forward the overall solutions due to the diverse application areas of the research results. In
this research, we propose a particular solution to utilize the association rules in transaction database.

1. Đặt vấn đề
Trong kỹ nguyên Internet, Intranets, Warehouses, đã mở ra nhiều cơ hội cho những
nhà 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ữ và
phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh
nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng.
Cơ sở dữ liệu trong các doanh nghiệp thì dữ liệu giao dịch đóng một vai trò rất quan
trọng cho việc hoạch định kế hoạch kinh doanh trên thương trường vào những năm tiếp theo.
Hiện tại, việc sử dụng các dữ liệu này tuy đã đạt được một số kết quả nhất định song vẫn còn
một số vấn đề tồn đọng như:
1. Dựa hoàn toàn vào dữ liệu, không sử dụng tri thức có sẳn về lĩnh vực, kết quả phân
tích khó có thể làm rõ được.

Transformati
Cleansing Preprocessing

Knowledge
Pattern
Discovery

Selection
Transformed
Data

Gathering

Internet,..
.

Target
Data

Cleansed
Preprocessed
Preparated

Data

Hình 1. Quá trình khai phá dữ liệu
Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý
thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất
nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,.v.v.
2.1 Gom dữ liệu (Gathering)

được quan tâm nhiều nhất hay còn gọi đó là Data Mining.
3. Luật kết hợp trong cơ sở dữ liệu – tính ứng dụng
3.1 Luật kết hợp trong cơ sở dữ liệu
Gọi I = {I1, I2,..., Im} 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, trong đó mỗi bản ghi T là một giao dịch và chứa các tập mục, T  I.
Định nghĩa 1: Một luật kết hợp là một quan hệ có dạng X  Y, trong đó X, Y  I là các tập
mục gọi là itemsets, và X  Y   . Ở đây, X được gọi là tiền đề, Y là mệnh đề kết quả.
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (s) và độ tin cậy (c).
Định nghĩa 2: Độ hỗ trợ (support) của luật kết hợp X  Y là tỷ lệ phần trăm các bản ghi
X  Y với tổng số các giao dịch có trong cơ sở dữ liệu.
Định nghĩa 3: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) là tỷ lệ của số
giao dịch có chứa X  Y với số giao dịch có chứa X. Đơn vị tính %.
Việc khai thác 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ó độ hỗ trợ
và độ tin cậy lớn hơn ngưỡng của độ hỗ trợ và độ tin cậy do người sử dụng xác định trước.
Các ngưỡng của độ hỗ trợ và độ tin cậy được ký hiệu là minsup và mincof.
Việc khai thác các luật kết hợp có thể được phân tích thành hai vấn đề sau đây:
1. Tìm tất cả các tập mục thường xuyên xảy ra mà có độ hỗ trợ lớn hơn hoặc bằng minsup.
2. Tạo ra các luật mong muốn sử dụng các tập mục lớn mà có độ tin cậy lớn hơn hoặc bằng
mincof. [1]
3.2 Tính ứng dụng
Luật kết hợp có ứng dụng trong nhiều lĩnh vực khác nhau của đời sống như: khoa học,
hoạt động kinh doanh, tiếp thị, thương mại, phân tích thị trường chứng khoán, tài chính và
đầu tư,... Ứng dụng luật kết hợp phải chỉ rõ các đặc điểm về: nguồn gốc, điều kiện áp dụng,
phạm vi ứng dụng, mục đích ứng dụng. Những đặc điểm này được thể hiện bằng mô hình sau:

Yêu cầu
sử dụng

Tham chiếu
tập luật R

4.1 Phát triển giải pháp hiệu quả trong khai thác luật kết hợp
a. Bài toán luật kết hợp
Cho một tập các giá trị I, một cơ sở dữ liệu giao dịch D, ngưỡng độ hỗ trợ tối thiểu
minsup, ngưỡng độ tin cậy mincof, tìm các luật kết hợp dạng X  Y trên D thoả mãn điều
kiện Support(X  Y) >= minsup và Confidence(X  Y) >= mincof.
b. Tiến trình khai thác luật kết hợp
 Xác định các tập mục lớn Việc xác định các tập mục lớn gồm có hai bước chính sau
đây:
- Xác định các tập ứng cử viên (Ck).
- Xác định các tập mục lớn (L) dựa vào tập ứng cử viên
Để xác định tập ứng cử viên, ta thực hiện các bước sau đây:
- Tìm các tập ứng cử viên một mục.
- Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu tiên, các
tập ứng cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng thứ k (k>1), các
tập ứng cử viên được xác định dựa vào các tập mục lớn đã xác định tại vòng k – 1, sử
dụng hàm Apriori-gen() [2,3,7]. Sau khi đã xác định được các tập ứng cử viên, thuật toán
quét từng giao dịch trong CSDL để tính độ hỗ trợ của các tập ứng cử viên. Quá trình xác
định các tập mục sẽ kết thúc khi không xác định được thêm tập mục lớn nào nữa.
Nội dung hàm Apriori-gen().
Hàm Apriori-gen() thực hiện hai bước [2]:
- Bước đầu tiên, Lk – 1 được kết nối với chính nó thu được Ck.
- Bước thứ hai, Apriori_gen() xoá tất cả các tập mục từ kết quả kết nối mà có một số tập
con (k – 1) không có trong Lk – 1. Sau đó nó trả về tập mục lớn kích thước k còn lại.
 Sinh các luật kết hợp từ tập mục lớn:
Việc phát hiện các tập mục lớn là rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi
tìm được tất cả các tập mục lớn (l  L), ta có thể dễ dàng sinh ra các luật kết hợp có thể
có bằng các bước như sau:
- Tìm tất cả các tập con không rỗng x, của tập mục lớn l  L.
- Với mỗi tập con x tìm được, ta xuất ra luật dạng x  (l - x) nếu tỷ lệ
Support(l)/Support(x)>= mincof ( %).

thuật “tỉa” các ứng cử viên không cần thiết.
Kỹ thuật này có tinh chất: Các mục trong tập ứng cử viên được sắp xếp theo thứ tự.
Nội dung kỹ thuật:
Forall itesets c  Ck do
Forall (k – 1)–subsets s of c do
If (s  Lk – 1) then
Delete c from Ck
Dựa vào đây, ta có thể tỉa được các tập ứng cử viên, từ đó có thể giới hạn miền tìm
kiếm của nó trên tất cả các tập mục.
4.2 Phát triển giải pháp hiệu quả tính ứng dụng
Trong phần 4.1, đã trình bày tiến trình khai phá luật kết hợp và giải pháp hiệu quả cho
việc tạo ra các luật kết hợp. Tuy đã giảm được một số lượng rất lớn các luật không mong
muốn, song một vấn đề nẩy sinh vẫn phải tiếp tục nghiên cứu nhằm tăng hiệu quả sử dụng kết
quả khai thác đó là:
1. Khi tồn tại tập luật dạng X  Y có độ tin cậy (ck) thì luôn tồn tại tập luật dạng Y  X có độ
tin cậy (ck+1). Như vậy, luật dạng Y  X thường không cần thiết vì người sử dụng đã ngầm
hiểu.
2. Cách thức vận dụng tập luật chưa rõ.[4,5,6]
Trong phạm vi nghiên cứu này, chúng tôi đưa ra một giải pháp mới để giải quyết hai
vấn đề nêu trên.


a. Tỉa tập luật dạng Y  X
Việc tỉa các tập luật dạng Y  X nhằm mục đích bỏ đi các luật không có giá tri hoặc
người sử dụng đã biết trước luật đó, đồng thời rút gọn được các tập luật. Kỹ thuật tỉa này sử
dụng độ tin cậy của tập luật tìm thấy.
Kết quả khai thác sinh ra tập luật thường được lưu trữ vào một cơ sở dữ liệu nào đó như
Access, Excel, Paradox, v.v. Kỹ thuật tỉa nhằm loại bỏ các tập luật có độ tin cậy ck+1 < ck.
Nội dung kỹ thuật:
Forall rulsets r  Ri do

sử dụng luật nhằm giảm thời gian tìm kiếm và tăng khả năng thi hành luật. Việc xác định tính
chất luật có tính quyết định hình thành kết hợp tập mục trong mỗi giao dịch. Vì thế, khai thác
luật kết hợp được ứng dụng rất thành công trong cơ sở dữ liệu giao dịch.
Một giải pháp mô phỏng việc tinh lọc, xem xét đặc điểm luật phục vụ cho ứng dụng
được nghiên cứu và phản ảnh trong hình 4.


Trong vòng lặp đầu tiên (k=n),
tập luật được xác định tính chất là tập
luật thứ n trong R (toàn bộ tập luật).
Nội dung xác định tập luật gồm: “tiền
đề”, “kết luận”, “độ tin cậy”, “độ hỗ
trợ”. Tiếp theo kiểm tra tính chất luật
này. Nếu luật kiểm tra thoả mãn
chuẩn đề ra thì ghi nhận đặc tính sử
dụng cho nó, ngược lại xoá luật ri ra
khỏi R, lưu kết quả và thực hiện vòng
lặp tiếp theo. Giải pháp kết thúc khi
đã kiểm tra xong toàn bộ tập luật R.
(k=0).
Ghi nhận tính chất ứng dụng là
một bước rất quan trọng quyết định
tối ưu tính ứng dụng. Vì thế, trong
bước này sẽ được xây dựng các
“Chuẩn” đánh giá nghiêm ngặt.
Chuẩn này dựa trên những nguyên
tắc riêng, nhất định của phạm vi ứng
dụng luật. Các hàm chuẩn này sẽ
được tiến hành cài đặt và thử nghiệm
trong môi trường cơ sở dữ liệu giao

luật đã được xác nhận đặc tính sẽ có tính ứng dụng linh hoạt, chủ động hơn khi ứng dụng.
Như vậy, tính ứng dụng của khai thác luật kết hợp trong cơ sở dữ liệu giao dịch đề cập
đến phạm vi ứng dụng luật kết hợp trên các giao dịch là rất quan trọng. Khai thác mối quan hệ
giữa các mục trong phiên giao dịch sẽ là hữu ích khi chúng ta tiến hành khai thác một cách có
thứ tự, có mục đích rõ ràng. Giải pháp này góp phần chỉ rõ hơn những thông tin có trong các
phiên giao dich để từ đó giúp cho lãnh đạo có kế hoạch hoạt động, sản xuất kinh doanh trong
các năm tiếp theo. Tính ứng dụng của khai thác luật kết hợp trong cơ sở dữ liệu giao dịch giải
quyết tốt cách thức thi hành, ứng dụng thông tin quan trọng trên các phiên giao dịch. Dựa vào
tính ứng dụng này có thể có giải pháp tốt đối với nền kinh tế thị trường hiện tại cũng như
trong tương lai.
5. Ví dụ minh hoạ khai thác - Ứng dụng luật
Thực tế, hệ thống thu ngân tại Siêu Thị Đà Nẵng đã sử dụng công nghệ mã vạch để
thanh toán cho khách hàng. Dữ liệu giao dịch mỗi khách hàng được lưu trữ trong phần mềm
cơ sở dữ liệu của máy tính đặt tại các quầy thu ngân. Hiện nay dữ liệu này đã trở nên rất nhiều
qua các phiên giao dịch, việc sử dụng DataMining để khai phá các dữ liệu hiện có là một việc
rất cần thiết cho hoạt động kinh doanh trong Siêu Thị.
Như vậy, nhiệm vụ của khai thác dữ liệu là phải tìm được mối liên hệ giữa các mặt
hàng trong giao dịch đó. Mối quan hệ này có dạng X => Y, đây chính là các tri thức chiết xuất
được trong khi khai thác với độ hỗ trợ cho trước (minsupt), độ tin cậy cho trước (minconf).


Các tri thức chiết xuất được sẽ giúp cho hoạt động kinh doanh trong Siêu Thị được tốt hơn từ
đó có thể hoạch định kế hoạch sản xuất kinh doanh trong những năm tiếp theo. Bảng 1 trình
bày cơ sở dữ liệu các giao dịch tại quầy thu ngân của Siêu Thị.
Bảng 1. Cơ sở dữ liệu giao dịch

Sau khi đã xác định được các tập mục lớn và độ hỗ trợ, ta tiến hành sinh các luật kết
hợp bằng cách sử dụng thủ tục sinh các tập con của tập mục lớn. Các luật kết hợp thu được
trong trường hợp này bao gồm các luật dạng Y  X như đã đề cập ở trên. Bảng 2 mô tả nội
dung toàn bộ tập luật khai thác được trong cơ sở dữ liệu giao dịch với minsup =10% và

Như vậy, tính ứng dụng của khai thác luật kết hợp trong cơ sở dữ liệu giao dịch đã giải
quyết được hai vấn đề tồn đọng đã nêu ở phần trên. Kết quả của khai thác sẽ được lưu trữ
trong các cơ sở dữ liệu tri thức để phục vụ cho mục đích xây dựng các hệ chuyên gia về sau
này.
6. Kết luận
Nội dung nghiên cứu trong đề tài, các tác giả đã đưa ra một giải pháp từ việc thu gom
dữ liệu trên các phiên giao dịch, trên thương trường,... rồi tiến hành khai thác xử lý chúng để
chiết xuất ra các tri thức cần thiết. Các tri thức cần thiết này lại được tối ưu hoá và đem vào sử
dụng một cách hiệu quả trên các phiên giao dịch trong những lần tiếp theo. Đề tài đã đi sâu
vào tính ứng dụng, đưa ra cách thức xử lý thi hành các tri thức được chiết xuất một cách hiệu
quả. Nghiên cứu này đã đưa ra một cách nhìn tổng quan về quy trình khai phá dữ liệu từ các
nguồn dữ liệu khác nhau đến việc ứng dụng các tri thức đã chiết xuất vào thực tế cuộc sống.
Một ví dụ minh hoạ ứng dụng đã làm rõ cách nhìn này.
Nghiên cứu thiên về tính ứng dụng trong cơ sở dữ liệu giao dịch, song việc nghiên cứu
sẽ được tiếp tục phát triển trên các cơ sở dữ liệu khác nhằm mục đích tìm ra một quy luật ứng
dụng cho các tri thức đã chiết xuất.
TÀI LIỆU THAM KHẢO
/>Rekesh Arawal, Ramakrishnan Srikant*; Fast Algorithms for Mining Association, IBM Almadem
Research Center 650 Harry Road, San Jose, CA 95120.
Rekesh Agrawal, Tomasz Imielinski, and Arun N.Swami; Mining Association Rules Between Sets
of Items in Large Databases, Proceedings of the 1993 ACM SIGMOD International Conference
on Management of Data, pp. 207-216, Washington, D.C., May 1993.
Ming-Syan Chen, Jiawei*, Philip S. Yu; Data Mining: An Overview from Database Perspective;
Elect. Eng. Department National Taiwan Univ. IBM T.J. Watson Res. Ctr. P.O.Box 704
Yorktown, NY 10598, U.S.A.
Anthony K.H. Tung1, Hongjun Lu2, Jiawei Han1, Ling Feng3; Breaking the Barrier of
Transactions: Mining Tnter-Transaction Association Rules; 1Simon Fraser University,
BritishvColumbia, Canada {khtung, han}@cs.sfu.ca; 2The Honh Kong University of Science an
Technology, Hong Kong, China, ; 3The Hong Kong Polytectnic University, Hong
Kong, China.