HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Trần Thu Hà
NGHIÊN CỨU LUẬT KẾT HỢP HIẾM VÀ KHUYẾN NGHỊ
ÁP DỤNG CHO BÀI TOÁN TIẾP THỊ Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.01.04
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013



Người hướng dẫn khoa học: Tiến sĩ Hà Hải Nam
Phản biện 1:
……………………………………………………………………………

Phản biện 2:
…………………………………………………………………………

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


Chương 1: Tổng quan về vấn đề phát hiện luật kết hợp.
Chương 2: Luật kết hợp hiếm.
Chương 3:Khuyến nghị áp dụng luật kết hợp hiếm cho bài toán tiếp thị.
Trong quá trình hình thành luận văn học viên đã được sự giúp đỡ tận tình của
thầy hướng dẫn TS. Hà Hải Nam, cùng sự giúp đỡ của các thầy cô giáo trong Học
viện Bưu chính viễn thông cùng các bạn bè đồng nghiệp. Học viên xin chân thành
cảm ơn và mong nhận được sự đóng góp tích cực để bản thân được tự hoàn thiện
mình hơn.
2 CHƯƠNG I: TỔNG QUAN VỀ VẤN ĐỀ PHÁT HIỆN LUẬT
KẾT HỢP.
Trước tiên, chương này sẽ giới thiệu tổng quan về phương pháp chung phát
hiện luật kết hợp. Tiếp theo là trình bày quá trình phát hiện luật kết hợp từ CSDL
tác vụ và vấn đề phát hiện luật kết hợp từ CSDL định lượng.
1.1 Luật kết hợp và các phương pháp chung phát hiện luật kết hợp.
1.1.1. Bài toán phát hiện luật kết hợp
Ngày nay việc phát hiện luật kết hợp đang trở thành một khuynh hướng quan
trọng trong khai phá dữ liệu. Luật kết hợp là luật ngầm định một số quan hệ kết hợp
giữa một tập các đối tượng, mà các đối tượng này có thể độc lập hoàn toàn với
nhau. Khái niệm luật kết hợp (Association Rule) và phát hiện luật kết hợp
(Association Rule Mining) được Rakesk Agrawal và các cộng sự đề xuất lần đầu
tiên vào năm 1993 nhằm phát hiện các mẫu có giá trị trong CSDL tác vụ
(Transaction Database) tại các siêu thị.
Mục đích của bài toán phát hiện luật kết hợp là tìm ra mối quan hệ giữa các
tập mục dữ liệu trong các CSDL lớn và các mối quan hệ này là có ích trong hỗ trợ

đưa ra trong quá trình phát hiện luật). Các thuật toán phát hiện luật kết hợp thường
chia quá trình giải bài toán này thành hai bước như sau:
(1) Bước 1: Tìm tất cả các tập phổ biến trong CSDL D.
(2) Bước 2: Với mỗi tập phổ biến I
1
tìm được ở bước 1 tất cả các luật
mạnh có dạng I
2


I
1
– I
2
, I
2


I
1

Trong đó, ở bước thứ 1 đây là giai đoạn khó khăn, phức tạp và tốn nhiều chi
phí. Bước 2 được giải quyết đơn giản hơn khi đã có các tập phổ biến và độ hỗ trợ
của chúng. Bài toán tìm tập phổ biến trong không gian các tập con của tập mục I có
độ phức tạp tính toán là O(2
I
).
2.1 Phát hiện luật kết hợp từ CSDL tác vụ.
Nghiên cứu phát hiện luật kết hợp trong CSDL tác vụ được khởi đầu từ phát
hiện luật kết hợp với một ngưỡng độ hỗ trợ, tới phát hiện luật kết hợp với độ hỗ trợ

phổ biến đã tìm được trong lần duyệt trước để sinh ra tập phổ biến tiềm năng, gọi là
tập ứng viên và tính độ hỗ trợ của tập ứng viên này khi duyệt qua dữ liệu, ở cuối
mỗi lần duyệt ta xác định được tập item nào là tập phổ biến thực sự trong các tập
ứng viên. Quá trình đó thực hiện cho tới khi không còn tập mục phổ biến nào mới
được tìm thấy nữa.
Bảng 11.1: Bảng kí hiệu sử dụng trong thuật toán Apriori
Ký hiệu
Ý nghĩa
k-itemset
Tập có k-mục dữ liệu
L
k

Tập chứa k= itemset phổ biến. Mỗi phần tử của tập này có hai trường:
i) itemset và ii) độ hỗ trợ của itemset đó
C
k
Tập chứa các k-itemset ứng viên( các tập phổ biến à tiềm năng). Mỗi
phần tử của tập này có hai trường: i) itemset và ii) độ hỗ trợ.
5 Đầu vào: CSDL D, độ hỗ trợ cực tiểu minSup
Kết quả: Tập các tập phổ biến

k
L
k
Hàm Apriori – Gen sinh ra các ứng cử viên:
Procedure apriori-gen(L
k-1
)
insert into C
k
//bước kết nối
select p.item
1
, p.item
2
,…,p.item
k-1
, q.item
k-1

from L
k-1
p, L
k-1
q
where p.item
1
= q.item
1
,…,p.item
k-2Với những CSDL quá dầy( mọi giao dịch đều có số lượng lớn các mặt hàng)
thì số lượng tập phổ biến đóng cũng rất lớn và phương pháp chỉ tìm các tập phổ
biến cực đại được đề xuất để khác phục tình huống này.
Tập phổ biến X là cực đại nếu không có tập phổ biến khác chứa nó. Như vậy
không gian tập phổ biến cực đại là nhỏ hơn không gian tập phổ biến đóng. Từ các
tập phổ biến cực đại cho phép sinh ra được tất cả các tập phổ biến nhưng có hạn chế
là không ghi được độ hỗ trợ của chúng. Một số thuật toán tìm tập phổ biến cực đại
điển hình là Max – Miner, MAFIA, GENMAX…
1.2.2. Phát hiện luật kết hợp với độ hỗ trợ khác nhau.
1.2.2.1. Phát hiện luật kết hợp có ràng buộc mục dữ liệu
Phát hiện luật kết hợp trong CSDL sinh ra rất nhiều luật trong khi người sử
dụng lại chỉ quan tâm đến một phần trong các luật được phát hiện, như là chỉ quan
tâm đến các luật có chứa một mục dữ liệu cụ thể, vì vậy, các nghiên cứu phát hiện
luật kết hợp theo ràng buộc mục dữ liệu ra đời.
1.2.2.2. Phát hiện luật kết hợp với độ hỗ trợ nhiều mức
Thực tiễn cho thấy, với cùng một CSDL, có thể có nhiều tập mục có tần suất xuất
hiện rất cao nhưng có nhiều tập mục khác lại có tần suất xuất hiện rất thấp và việc
sử dụng một ngưỡng độ hỗ trợ (tương ứng với giả thiết tần suất xuất hiện của các
mục là như nhau) là không hợp lý. Hướng tiếp cận phát hiện luật kết hợp với độ hỗ
trợ nhiều mức được đưa ra nhằm khắc phục điều bất hợp lý này, theo đó, người
dùng có thể đưa ra ngưỡng độ hỗ trợ cực tiểu khác nhau cho từng mục dữ liệu. Bằng
việc đặt độ hỗ trợ cực tiểu thấp cho các mục dữ liệu tần số thấp cho phép người sử
dụng sẽ tìm được các luật kết hợp đa dạng hơn.
1.2.2.3. Phát hiện luật kết hợp có trọng số
Một khái niệm mang tính thực tế là các tập mục không đơn thuần chỉ được
xét là “có” hay “không” trong khi tính độ hỗ trợ mà mỗi tập mục được kèm theo

a
và l
b
thỏa mãn điều kiện l
a
< l
b
. Các
tác giả đưa ra ngưỡng độ hỗ trợ mà theo đó sẽ giảm dần theo chiều dài của tập mục
dữ liệu. Một tập mục được coi là phổ biến nếu thỏa mãn ràng buộc độ hỗ trợ giảm
dần theo độ dài của nó. Trái với cách tiếp cận truyền thống, tập mục được coi là phổ
biến ngay cả khi tập con của nó là không phổ biến. Như vậy tính chất đóng về độ hỗ
trợ theo thuật toán Apriori đã không còn đúng. Để khắc phục vấn đề này, các tác giả
đã phát triển tính chất giá trị nhỏ nhất ( SVE – smallest valid extension). Cách tiếp
cận này đề cao các tập mục nhỏ, tuy nhiên tập mục dài có thể rất hữu ích, ngay cả
khi chúng ít phổ biến hơn. Thuật toán tìm ra các tập dài mà không cần phải sinh một
số lượng lớn các tập ngắn tránh được sự bùng nổ số lượng lớn các tập mục nhỏ.
1.2.2.5. Phát hiện luật kết hợp không sử dụng độ hỗ trợ cực tiểu.
8 Quá trình phát hiện luật kết hợp được chia thành hai giai đoạn, giai đoạn thứ
nhất là tìm ra các tập phổ biến có độ hỗ trợ lớn hơn hoặc bằng một giá trị chung nào
đó(gọi là độ hỗ trợ cực tiểu, ký hiệu là minSup), còn giai đoạn hai là tìm các luật kết
hợp từ các tập tìm được ở giai đoạn thứ nhất và có độ tin cậy lớn hơn hoặc bằng
một giá trị chung khác(gọi là độ tin cậy cực tiểu, ký hiệu minConf). Trong đó, giai
đoạn tìm các tập phổ biến là phức tạp và tốn nhiều chi phí nhất.

kết hợp, phương pháp chung phát hiện luật kết hợp và vấn đề phát hiện luật kết hợp
từ CSDL tác vụ, phát hiện luật kết hợp từ CSDL định lượng. Từ phần nghiên cứu
tổng quan này đã giúp cho học viên có kiến thức và căn cứ cơ sở để lựa chọn và
thực hiện hướng nghiên cứu của mình.
10 CHƯƠNG II: LUẬT KẾT HỢP HIẾM
Chương 2 giới thiệu chung về luật kết hợp hiếm, trọng tâm là luật kết hợp
hiếm Sporadic tuyệt đối và không tuyệt đối. Một số thuật toán phát hiện tập hiếm
được trình bày trong chương này là tiền đề cho các cài đặt thử nghiệm ở chương 3.
Tiếp theo,chương 2 cũng đưa ra thảo luận ngắn gọn về khuynh hướng nghiên cứu
luật kết hợp hiếm.
2.1. Giới thiệu chung về luật kết hợp hiếm.
Luật kết hợp hiếm hàm ý chỉ các luật kết hợp không xảy ra thường xuyên
trong các CSDL. Mặc dù ít khi xảy ra, nhưng trong nhiều trường hợp chúng lại là
các luật rất có giá trị.
Luật kết hợp hiếm được ứng dụng ở nhiều các lĩnh vực khác nhau. Các luật
hiếm sẽ giúp cho việc học phát âm từ, xác định ảnh hưởng của các hoạt động trong
việc học trực tuyến đến kết quả đánh giá cuối cùng của sinh viên, xác định được các
bệnh hiếm gặp trong y khoa, dự báo việc hỏng thiết bị truyền thông, phát hiện dấu
hiệu tràn dầu trên hình ảnh vệ tinh, hay giúp xác định các mặt hàng tuy ít xảy ra
trong các giao dịch mua bán nhưng lại có giá trị lớn hoặc mang lại lợi nhuận cao
trong kinh tế. Phát hiện luật kết hợp hiếm là một phần của bài toán phát hiện luật
kết hợp và hiện đang nhận được nhiều sự quan tâm của các nhà nghiên cứu.
2.2. Phát hiện luật kết hợp hiếm.
Phần này sẽ nghiên cứu và giới thiệu vấn đề phát hiện luật hiếm từ CSDL

kết hợp hiếm. Họ chia luật Sporadic thành hai loại là: luật Sporadic tuyệt đối và luật
Sporadic không tuyệt đối.
Luật Sporadic tuyệt đối X

Y với độ hỗ trợ cực tiểu minSup và độ tin cậy cực
tiểu minConf là các luật kết hợp thỏa mãn:
(2.1)
Độ hỗ trợ của luật Sporadic tuyệt đối nhỏ hơn maxSup(tính hiếm) và mọi
mục dữ liệu trong tập X

Y đều có độ hỗ trợ nhỏ hơn maxSup(tính hiếm ”tuyệt
đối”).
2.2.3. Khuynh hướng nghiên cứu về luật hiếm
Quá trình sinh ra tất cả các luật hiếm hữu ích vẫn là một vẫn đề khó, nó bị
giới hạn bởi tính chất tự nhiên của dữ liệu.
Các luật hiếm là sự kết hợp của:
(1) các mục dữ liệu hiếm;
12 (2) các mục dữ liệu hiếm và các mục dữ liệu phổ biến;
(3) các mục dữ liệu phổ biến, có độ hỗ trợ cao
Khi xét riêng từng mục dữ liệu, nhưng khi kết hợp lại tạo thành các tập mục có độ
hỗ trợ nhỏ. Vì thế không thể dùng các kỹ thuật phát hiện tập phổ biến thông thường
để phát hiện các luật kết hợp hiếm. Độ hỗ trợ thấp của các tập mục gây trở ngại lớn
cho quá trình phát hiện luật hiếm. Trong [ 1], tác giả đã chỉ ra rằng: Phát hiện luật
kết hợp hiếm yêu cầu kỹ thuật tiền xử lý khác so với phát hiện luật phổ biến. Mặc

người mua bánh mì thì có 40 người cùng mua sữa hay bơ.
Trong khi khai phá dữ liệu tập trung vào việc chiết suất các thông tin có tính
dự đoán về khách hàng và kinh doanh từ các cơ sở dữ liệu, nghiên cứu tiếp thị
truyền thống tập trung vào việc xác định các yếu tố ảnh hưởng đến quyết định mua
sắm của các hộ gia đình và tổ chức. Dữ liệu liên quan được thu thập, thông thường
thông qua dữ liệu kinh doanh, các khảo sát và nhóm nghiên cứu tập trung. Các nhà
nghiên cứu tiếp thị truyền thống xác định một cơ hội, thu thập thông tin cần thiết
sau đó hình thành một chiến lược kinh doanh phù hợp.
3.2. Khuyến nghị áp dụng khai phá dữ liệu với luật kết hợp hiếm cho
bài toán tiếp thị.
Các quyết định tiếp thị, như là khuyến mãi, các kênh phân phối và phương
tiện quảng cáo, dựa trên các phương pháp tiếp cận phân đoạn truyền thông dẫn đến
tỷ lệ đáp ứng kém và giá thành cao. Khách hàng ngày nay có các thị hiếu và sở
14 thích khó có thể nhóm thành các nhóm đồng nhất để phát triển các chiến lược tiếp
thị theo nhóm. Trong thực tế, mỗi khách hàng muốn được phục vụ theo nhu cầu cá
nhân và duy nhất.
Việc ứng dụng luật kết hợp hiếm được khuyến nghị áp dụng trong ba phạm
vi chính của tiếp thị dựa trên tri thức đó là: 1) Xây dựng hồ sơ cá nhân khách hàng;
2) Phân tích biến động và 3) Phân tích xu hướng.
3.1.1. Xây dựng hồ sơ cá nhân khách hàng
Một trong những tri thức hữu ích về khách hàng là hồ sơ, nó có thể được sử
dụng để đưa ra một số quyết định tiếp thị quan trọng. Một hồ sơ cá nhân khách hàng
là một mô hình khách hàng, dựa trên đó các chuyên gia tiếp thị quyết định các chiến
lược và chiến thuật tiếp thị đúng đắn để đáp ứng các yêu cầu của khách hàng. Hình


Khách hàng

CSDL
khách
hàng
CSDL
giao dịch
CSDL
sản
phẩm
Sản phẩm phổ
biến
Đặc tính
Hình 23.1: Hệ thống xây dựng hồ sơ cá nhân khách hàng
15 biến độn rất khó có thể được phát hiện kịp thời để có các hành động phù hợp. Các
công cụ khai phá dữ liệu cung cấp các phương tiện mạnh như là mạng nơ ron nhân
tạo để phát hiện và phân loại các biến động đó. Ví dụ một mua sắm với lượng tiền
lớn hơn thông thường có thể là một bất thường liên quan đến gian lận hoặc là một
mua sắm thật do sự thay đổi từ phía khách hàng.
3.1.3. Phân tích xu hướng
Các xu hướng là các mẫu không thay đổi trong một giai đoạn thời gian. Các
xu hướng có thể là các xu hướng ngắn hạn như là sự tăng tức thời và sự giảm chậm
của sản lượng kinh doanh do một chiến dịch kinh doanh. Hoặc các xu hướng có thể

khách hàng có nghề nghiệp văn phòng không mua các sản phẩm khuyến mãi.
Luật 3: (ProductPrice >= 300.000, ProductType =2, CareerType=2) =>
Month = 1) với conf = 0.8
Luật 4: (ProductPrice >= 300.000, ProductType = 2, CareerType=2) =>
Month = 2) với conf = 0.76
Luật 3 và 4 được suy diễn như sau: Vào tháng 1 và tháng 2 các khách hàng
có nghề nghiệp lao động phổ thông mua đồ chơi trẻ em có giá trị lớn hơn 300.000
VND.
Tuy thử nghiệm được tiến hành chỉ đưa ra một số luật hiếm khá đơn giản,
thử nghiệm cũng minh chứng được khả năng áp dụng khai phá luật hiếm trong các
ứng dụng tiếp thị sản phẩm dịch vụ.
Kết luận chương:
Trong chương thứ 3, luận văn đã trình bày kết quả ứng dụng khai phá dữ liệu
với luật kết hợp hiếm cho bài toán tiếp thị. Việc ứng dụng luật kết hợp hiếm được
khuyến nghị áp dụng vào ba phạm vi chính của tiếp thị dựa trên tri thức là: Xây
dựng hồ sơ khách hàng, phân tích biến động và phân tích xu hướng. Thử nghiệm
được áp dụng với CSDL của một của hàng bán đồ trẻ em cũng đã mang lại kết quả
hữu ích mà bài toán tiếp thị cần quan tâm. Đưa ra được một số luật cần thiết áp
dụng cho tiếp thị.

17