Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
I H C QU C GIA THÀNH PH H CHÍ MINHĐẠ Ọ Ố Ố Ồ
TR NG I H C CÔNG NGH THÔNG TINƯỜ ĐẠ Ọ Ệ
BÀI TI U LU N MÔN: THU T TOÁN VÀ PH NG PHÁP GI I QUY T V NỂ Ậ Ậ ƯƠ Ả Ế Ấ
ĐỀ
BÀI TOÁN TÌM LU T K T H P D A TRÊN THU TẬ Ế Ợ Ự Ậ
TOÁN APRIORI
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 1
1.1.1.1.1.1.1.1
MSSV: CH1201051
H tên: Di p Thanh Nguyênọ ệ
L p: Cao h c khóa 7ớ ọ
GVHD: PGS.TS. V Thanh Nguyênũ
MSSV: CH1201051
H tên: Di p Thanh Nguyênọ ệ
L p: Cao h c khóa 7ớ ọ
GVHD: PGS.TS. V Thanh Nguyênũ
MSSV: CH1301118
H tên: Nguy n Ng c V ngọ ễ ọ ọ
L p: CH-K8ớ
GVHD: PGS.TS V n Nh nĐỗ ă ơ
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
Tp.HCM, Tháng 10/2014
LỜI NÓI ĐẦU
Khai phá dữ liệu (Data mining) là ngành khoa học đang ngày được quan tâm nghiên
cứu và phát triển do những ứng dụng thiết thực mà nó mang lại. Khai phá dữ liệu là phần
cốt lõi của phát hiện tri thức, trong khai phá dữ liệu phát hiện các luật là một trong những
nội dung cơ bản và phổ biến nhất. Các phương pháp phát hiện luật nhằm tìm ra sự phụ
thuộc giữa các tính chất của các đối tượng hay các thuộc tính trong cơ sở dữ liệu.
Qua môn học thuật toán và phương pháp giải quyết vấn đề, người viết đã được tìm
hiểu về thuật toán Apriori tìm luật kết hợp dựa theo ngưỡng minsup và minconf, trong đó GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 3
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
MỤC LỤC
LỜI NÓI ĐẦU 1
NHẬN XÉT CỦA GIẢNG VIÊN 2
MỤC LỤC 3
Ph n 1. C S LÝ THUY T KHAI PHÁ D LI Uầ Ơ Ở Ế Ữ Ệ 5
1.1 Khai phá d li uữ ệ 5
1.2 Khái ni m v lu t và lu t k t h pệ ề ậ ậ ế ợ 15
1.3 M t s tính ch t c a t p m c ph bi n và lu t k t h pộ ố ấ ủ ậ ụ ổ ế ậ ế ợ 17
Ph n 2. BÀI TOÁN TÌM LU T K T H P THEO GI I THU T APRIORIầ Ậ Ế Ợ Ả Ậ 20
2.1 Phát bi u bài toánể 20
2.2 B c 1: Mô hình hóa v n đướ ấ ề 20
2.3 B c 2: Thi t k thu t toán/ thu t gi iướ ế ế ậ ậ ả 21
2.4 B c 3: Ch ng minh tính đúng đ nướ ứ ắ 25
2.5 B c 4: Phân tích thu t toán/ thu t gi iướ ậ ậ ả 25
2.6 B c 5: Nghiên c u c i thi n và nâng cao hi u quướ ứ ả ệ ệ ả 26
Ph n 3. CH NG TRÌNH DEMOầ ƯƠ 27
3.1 Giao di n ch ng trìnhệ ươ 27
3.2 S d ng ch ng trìnhử ụ ươ 27
3.3 Xây d ng l p Aprioriự ớ 27
3.4 Xây d ng LargeItemSetự 28
KẾT LUẬN 30
TÀI LIỆU THAM KHẢO 31
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 4
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori

đầu. Giờ đây KPDL đã và đang trở thành một trong những hướng nghiên cứu chính của
lĩnh vực khoa học máy tính và công nghệ tri thức. Do đó có thể coi mục đích chính của
quá trình KPDL là một mô tả và dự đoán mà các mẫu KPDL phát hiện đều được nhằm vào
mục đích này.Để đạt được mục tiêu chính trên, nhiệm vụ cơ bản nhất của KPDL là:
1.1.2.1 Phân cụm, phân loại, phân nhóm, phân lớp
Nhiệm vụ là trả lời câu hỏi là một dữ liệu mới thu thập được sẽ thuộc về nhóm
nào? Quá trình này thường được thực hiện một cách tự động.
1.1.2.2 Khai phá luật kết hợp
Nhiệm vụ là phát hiện những mối quan hệ giống nhau về cấu trúc của các bản ghi
giao dịch. Luật kết hợp X=>Y có dạng tổng quát là : Nếu một giao dịch đã sở hữu các tính
chất X, thì đồng thời nó cũng sở hữu các tính chất Y, ở một mức độ nào đó. Khai phá luật
kết hợp được hiểu theo nghĩa: biết trước các tính chất X, thì sẽ biết được các tính chất Y là
những tính chất nào?
1.1.2.3 Lập mô hình dự báo
Bao gồm 2 nhiệm vụ hoặc là phân nhóm dữ liệu vào một hay nhiều lớp dữ liệu đã
xác định từ trước, hoặc là sử dụng các trường đã cho trong một cơ sở dữ liệu để dự báo sự
xuất hiện (hoặc không xuất hiện) của các trường khác.
1.1.2.4 Phân tích sự tiến hoá
Phân tích sự tiến hoá thực hiện việc mô tả và mô hình hoá các qui luật hay khuynh hướng
của những đối tượng mà ứng xử của chúng thay đổi theo thời gian. Phân tích sự tiến hoá
có thể bao gồm cả đặc trưng hoá, phân biệt, tìm luật kết hợp, phân lớp hay phân cụm dữ
liệu liên quan đến thời gian, phân tích dữ liệu theo chuỗi thời gian, sánh mẫu theo chu kì
và phân tích dữ liệu dựa trên tính tương tự.
1.1.2.5 Hồi quy
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 6
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị
thực.
1.1.2.6 Phân nhóm
Là việc mô tả chung để tìm ra các tập dữ liệu xác định hay các nhóm để mô tả dữ

Quá trình KPDL là công việc khảo sát thăm dò thông tin dữ liệu, trích chọn tri thức,
thu thập thông tin, thậm chí là duyệt và tìm kiếm dữ liệu. Tuy nhiên, các nhà thống kê thì
có quan điểm cho rằng KPDL là một quá trình phân tích và đánh giá để thăm dò, dự đoán
và ước lượng một lượng các thông tin dữ liệu với mục đích phát hiện ra các mẫu tin thích
hợp hoặc là các mối quan hệ thuộc tính giữa các yếu tố hay các biến cố và cuối cùng là
tích hợp các kết quả thu được bằng cách áp dụng các hệ số mẫu đã xác định cho các phần
dữ liệu mới phát hiện. Từ đó đưa ra các hoạt động liên quan đến kết quả thu được.
Quá trình khai phá dữ liệu được thể hiện qua mô hình sau:
Hình 1.1 Quá trình khai phá dữ liệu
 Xác định nhiệm vụ : Là việc xác định chính xác và rõ ràng vấn đề cần giải quyết.
 Xác định dữ liệu liên quan: Để xây dựng giải pháp
 Thu thập và tiền xử lý dữ liệu liên quan: Thành dạng sao cho thuật toán KPDL có
thể hiểu được.
 Chọn thuật toán KPDL: Cho phù hợp và thực hiện KPDL nhằm tìm được các mẫu
cần quan tâm và biểu diễn chúng dưới dạng có ý nghĩa.
 Mẫu : Là kết quả của quá trình KPDL, tức là hiểu và sử dụng tri thức đã tìm được
thông qua hành động.
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 8
Xác định
nhiệm vụ
Xác định
dữ liệu
liên quan
Thu thập và
tiền xử lý DL
Thống kê
Tóm tắt
Dữ liệu
trực tiếp
Giải thuật

trị thuộc tính nhiều chiều. Sau khi chọn mẫu ta thu được một tập con hay một nhóm dữ
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 9
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
liệu của tập các biến thuộc tính đầu vào sau khi đã loại bỏ đi các thuộc tính ít quan trọng,
thuộc tính thừa. Từ đó thu thập và kết hợp thành bộ véctơ thuộc tính mẫu.
1.1.6 Một số phương pháp khai phá
1.1.6.1 Phương pháp quy nạp
Có hai kỹ thuật chính để thực hiện công việc này đó là suy diễn và quy nạp. Suy
diễn: nhằm rút ra thông tin là kết quả lôgic của các thông tin trong CSDL dựa trên một dãy
các sự kiện chính để suy ra các tri thức mới từ các tri thức đã có. Kỹ thuật suy diễn để thu
được mẫu chi tiết thường sử dụng các luật suy diễn. Quy nạp: suy ra các thông tin được
sinh ra dựa trên CSDL hoặc các kho dữ liệu đã có. Phương pháp quy nạp là tự tìm kiếm,
tạo mô hình, mẫu và sinh ra tri thức cấp cao diễn tả các đối tượng trong CSDL, liên quan
trực tiếp đến các mẫu tìm được trong CSDL. Trong KPDL quy nạp được sử dụng để tạo
cây quyết định và luật.
1.1.6.2 Cây quyết định
Ở đây ta quan tâm đến cây quyết định quy nạp được dùng trong việc “học” tri thức
thông qua phân tích cây. Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân
các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gắn nhãn là tên các
thuộc tính, các cạnh được gắn các giá trị có thể của các thuộc tính, các lá miêu tả các lớp
khác nhau. Các đối tượng được phân theo lớp các đường đi trên cây, qua các cạnh tương
ứng với giá trị của thuộc tính.
1.1.6.3 Luật kết hợp
Là luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê.
Các luật có dạng: Nếu P thì Q; với P là mệnh đề đúng với một miền dữ liệu nào đó trong
kho dữ liệu và Q là mệnh đề sẽ dự đoán. Phương pháp này nhằm phát hiện ra các luật kết
hợp giữa các thành phần trong CSDL. Mẫu đầu ra của thuật toán KPDL là tập luật kết hợp
tìm được.
Cho một lược đồ R={A
1

lược kinh doanh và bán máy vi tính,máy in trong tương lai:
“Máy vi tính=>máy in ”{Độ hỗ trợ 20%, độ tin cậy 80%}
Với ví dụ này, có thể hiểu độ hỗ trợ 20% có nghĩa là 20% của tất cả các tác vụ đã
phân tích chỉ ra rằng người mua máy vi tính và mua máy in có tỷ lệ đã được mua là cùng
nhau. Còn độ tin cậy 80% có nghĩa là 80% người mua máy vi tính bao giờ cũng có tỷ lệ
lớn mua máy in.
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 11
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
Nhược điểm của phương pháp này là sự gia tăng nhanh chóng khối lượng tính toán
và các thông số. Tuy nhiên với sự phát triển nhanh chóng và mạnh mẽ của phần cứng thì
các vấn đề này cũng được khắc phục.
1.1.6.4 Phân lớp, phân loại dữ liệu
Cho phép ta sắp xếp các thực thể với một số thuộc tính giống nhau vào một lớp
chung. Công việc này giống việc phân loại nhưng có điểm khác biệt là chưa có sự định
nghĩa các lớp từ trước. Các phương pháp này rất có ích trong giai đoạn đầu của quá trình
nghiên cứu khi ta biết rất ít về đối tượng cần nghiên cứu, nó là tiền đề để tiến hành các
phương pháp khác về KDD.
Nhiệm vụ của phân lớp là tìm ra được một hàm để ghép một đối tượng dữ liệu vào
một lớp trong một số lớp nào đó. Ta thấy rằng rất khó để tách lớp một cách hoàn toàn bằng
một đường biên rạch ròi có dạng đường thẳng. Ngân hàng rất muốn sử dụng các miền đã
được phân lớp để có thể đi đến quyết định một cách tự động về việc liệu có tiếp tục cho
khách tiếp tục vay nữa hay không.
Có nhiều phương pháp phân lớp, phương pháp nổi tiếng nhất là phương pháp K lân
cận. Giả sử muốn chia các đối tượng ban đầu thành K lớp. Lựa chọn K trung tâm ngẫu
nhiên bất kỳ trong không gian các đối tượng. Sau đó tiến hành:
- Chia các dữ liệu thành K nhóm gần nhất với một trong các trung tâm. Khoảng
cách giữa các điểm với các trung tâm sẽ xác định chúng có thuộc K hay không.
- Xác định lại các trung tâm mới bằng cách tính lại giá trị trung bình của các biến
phụ thuộc, tất nhiên các trung tâm mới sẽ khác trung tâm cũ. Phương pháp K lân cận sẽ
làm việc tốt nếu bản chất của dữ liệu là có thể phân loại. Tuy nhiên nó khó áp dụng với

người cũng như các kỹ thuật máy tính khác không thể phát hiện được.
Một trong những ưu điểm phải kể đến của mạng neural là khả năng tạo ra các mô
hình dự đoán do có độ chính xác cao, có thể áp dụng được cho rất nhiều các loại bài toán
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 13
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
khác nhau đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân
nhóm, mô hình hoá, dự báo
Mẫu chiết xuất bằng mạng neural được thể hiện ở các nút đầu của mạng. Mạng
neural sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực
của các nút đầu ra và cập nhật các trọng số của nó.
Đặc điểm của mạng neural là không cần gia công dữ liệu nhiều trước khi bắt đầu
quá trình học như các kỹ thuật khác. Tuy nhiên để có thể sử dụng mạng neural có hiệu quả
cần phải xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng là gì?
- Mạng cần có bao nhiêu nút?
- Khi nào thì việc học dừng?
Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước
khi đưa vào mạng neural để mạng có thể hiểu được.
Mạng neural được đóng gói với những thông tin trợ giúp của các chuyên gia đáng
tin cậy và được các chuyên gia đảm bảo các mô hình này làm việc tốt. Sau khi học mạng
được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học
1.1.6.10Giải thuật di truyền
Đây là phương pháp không chỉ phục vụ KPDL mà còn phục vụ nhiều bài toán
khác, ví dụ như bài toán tối ưu hoặc lập lịch. Tư tưởng của thuật toán là áp dụng quy luật
của sự chọn lọc tự nhiên. Người ta mô phỏng tập hợp dữ liệu ban đầu bằng ký tự nhị phân
và gọi là những quần thể xuất phát, bằng các thao tác lai ghép, đột biến chúng ta biến đổi
quần thể gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác
định mức độ thích nghi của quần thể theo các giai đoạn. Quá trình tiến hoá làm cho các
quần thể thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho người ta lời
giải tối ưu toàn cục (khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn

Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
Mô tả một hệ luật dẫn: Các luật dẫn hoặc gọi là luật IF THEN là những mệnh đề có dạng
LHS=>RHS trong đó LHS xác định các điều kiện hoặc hoàn cảnh phải được thoả mãn cho
luật được áp dụng, RHS là những tác động phải xảy ra khi luật được áp dụng.
1.2.2 Định nghĩa luật kết hợp
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, 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à
φ
=
YX 
. Ở đâ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

Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong cơ sở dữ liệu T.
Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting rules).
Trong thực tế, hầu hết thời gian của quá trình khai thác luật kết hợp là thực hiện ở
pha 1.Nhưng khi có những mẫu rất dài (mẫu chứa nhiều mục) xuất hiện trong dữ liệu, việc
sinh ra toàn bộ các tập phổ biến ( FI ) hay các tập đóng (FCI ) là không thực tế. Hơn nữa,
có nhiều ứng dụng mà chỉ cần sinh tập phổ biến lớn nhất( MFI ) là đủ, như khám phá mẫu
tổ hợp trong các ứng dụng sinh học.
Có rất nhiều nghiên cứu về các phương pháp sinh tất cả các tập phổ biến và tập phổ
biến lớn nhất một cách có hiệu quả. Khi các mẫu phổ biến (frequent pattern) dài (có từ 15
đến 20 items ) thì tập FI ,thậm chí cả tập FCI trở nên rất lớn và hầu hết các phương pháp
truyền thống phải đếm quá nhiều tập mục mới có thể thực hiện được. Các thuật toán dựa
trên thuật toán Apriori - đếm tất cả 2
k
tập con của mỗi k- itemsets mà chúng quét qua, và
do đó không thích hợp với các itemsets dài được. Các phương pháp khác sử dụng “
lookaheads ” để giảm số lượng tập mục được đếm. Tuy nhiên, hầu hết các thuật toán này
đều sử dụng tìm kiếm theo chiều rộng, ví dụ: tìm tất cả các k – itemsets trước khi tính đến
các (k+1) – itemsets . Cách làm này làm hạn chế hiệu quả của lookaheads, vì các mẫu phổ
biến dài hơn mà hữu ích vẫn chưa được tìm ra.
1.3 Một số tính chất của tập mục phổ biến và luật kết hợp
1.3.1 Một số tính chất với tập mục phổ biến
Giả sử A và B là các tập mục phổ biến, các tính chất của tập mục phổ biến như sau:
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 17
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
 Tính chất 1 : Nếu A
⊆
B thì supp(A) ≥ supp(B).
Vì tất cả các tác vụ trong D hỗ trợ B thì cũng hỗ trợ A.
 Tính chất 2: Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến
(nếu A không phổ biến thì B cũng không phổ biến).

Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
Tuy nhiên, đảo lại: X → Y ∪ Z ⇒ X → Y ∧ X → Z
 Tính chất 3 : Các luật kết hợp không có tính chất bắc cầu.
Nếu X → Y và Y → Z chúng ta không thể suy ra X →Z.
Ví dụ: Giả sử T(X)⊂(T(Y)⊂(T(Z) tương ứng là tập các tác vụ chứa X,Y,Z và độ tin cậy
cực tiểu là minconf, conf(X→Y)=conf(Y→Z)=minconf
thế thì: conf(X→Z)=minconf
2
<minconf vì minconf<1, do đó luật X→Z không đủ độ
tin cậy.
Tính chất 4:
Nếu luật A→(L-A) không thỏa mãn độ tin cậy cực tiểu thì luật B→(L-B) cũng không
thỏa mãn, với các tập mục L,B,A và B⊆A⊆L.
Vì supp(B)≥(supp(A) (Theo tính chất 1 và định nghĩa độ tin cậy, chúng ta nhận
được:
conf
Ap
Lp
Bp
Lp
BLBconf min
)(sup
)(sup
)(sup
)(sup
))((
<≤=−→
Cũng như vậy: Nếu có luật (L-C)→C thì ta cũng có luật (L-D)→D, với D ⊆C và D≠∅.
Vì D ⊆ C nên (L-D) ⊇ (L-C), do đó supp(L-D) ≤ supp(L-C)
conf

3. Theo độ hỗ trợ minsupp và độ tin cậy minconf do ta đưa ra
+ Thu thập mẫu vấn đề và phân lớp
+ Mô tả mục tiêu hay kết luận của vấn đề: tìm được luật kết hợp từ mẫu dữ liệu
+ Mô tả các điều kiện hay ràng buộc: điều kiện không được nhỏ hơn độ hỗ trợ minsupp và
độ tin cậy minconf
2.2.2 Xây dựng mô hình
+ Mô hình cho DIK
Được mô hình hóa bằng table trong cơ sở dữ liệu. Trong đó
- Mặt hàng là các Items được lưu thành cột trong table
- Thuộc tính của mỗi cột là yes/no
+ Mô hình cho giả thiết
- Input: table, minsupp, minconf
- Output: luật kết hợp dạng a->b
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 20
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
2.3 Bước 2: Thiết kế thuật toán/ thuật giải
2.3.1 Phương pháp
Chọn lựa phương pháp giải quyết vấn đề dựa trên thuật giải Apriori.
2.3.2 Giới thiệu thuật giải Apriori
Apriori là thuật toán được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề
xuất lần đầu vào năm 1993. Bài toán được phát biểu: Tìm t có độ hỗ trợ s thỏa mãn s ≥ s
0
và độ tin cậy c ≥ c
0
(s
0
, c
0
là hai ngưỡng do người dùng xác định và s
0

Output: L- tập mục phổ biến trong D
Method:
1. L
1
=Large_1_ItemSets()
2.
for (k=2; L
k-1
≠ ∅; k++) do
3. begin
4. C
k
=apriori-gen(L
k-1
)
;
5. for (mỗi một giao dịch T
∈
D) do
6. begin
7. C
T
= subset(C
k
, T);
8. for (mỗi một ứng cử viên c
∈
C
T
) do

k-1
with L
k-1
;
2. Insert into C
k
3. select p.item
1
,p.item
2
, . . .p.item
k-1
, q.item
k-1
4. from L
k-1
as p, L
k-1
as q;
5.
where (p.item
1
= q.item
1
)∧ ∧(p.item
k-2
= q.item
k-2
)∧(p.item
k-1

Tính tập Large 1-item, ta có F1: {{a}, {b}, {m}, {t}}
Tập Items Số lần xuất hiện
{a}
3/7
{b}
5/7
{c} 1/7
{d}
1/7
{e}
1/7
{m}
3/7
{p}
1/7
{t}
3/7
{s}
1/7
{y}
2/7
Từ F1 trên ta có tập C2 gồm các cặp 2-item:
{{a, b}, {a, m}, {a,t}, {b,m}, {b,t}, {m,t}}
Tính tập Large 2-item, ta có F2: {{a,b}, {b,m}}
Tập Items Số lần xuất hiện
{a, b}
3/7
{a, m}
1/7
{a, t}

Tivi
Xe
máy
Máy ảnh Máy tính Xe hơi
x x
x x
x
x
x
x
Hãy tìm luật kết hợp cho Min Support = 50%, Min Confidence = 80%
Cho cơ sở dữ liệu chi tiết hóa đơn bán hàng trong 1 siêu thị như bảng sau:
Tính tập Large 1-item, ta có F1: {{ "Máy giặt "}, {"Tivi"}, {"Xe máy"}, {Máy tính}}
Tập Items Số lần xuất hiện
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Nguyễn Ngọc Vọng – CH1301118 24
Tiểu luận: Bài toán tìm luật kết hợp theo giải thuật Apriori
{Máy giặt} 6/9
{Tivi} 9/9
{Xe máy} 5/9
{Máy tính} 5/9
Từ F1 trên ta có tập C2 gồm các cặp 2-item:
{{Máy giặt, ti vi}, {Máy giặt, xe máy}, {Máy giặt, máy tính}, {Tivi, xe máy},
{Tivi, máy tính}, {Xe máy, máy tính}}
Tính tập Large 2-item, ta có F2: {{Máy giặt, ti vi}, {Tivi, xe máy}, {Tivi, máy tính}}
Tập Items Số lần xuất hiện
{Máy giặt, Tivi} 6/9
{Tivi, xe máy} 5/9
{Tivi, máy tính} 5/9
Từ F2 trên ta có tập C3 gồm các cặp 3-item:
{{Tivi, máy giặt, xe máy}, {Tivi, xe máy, máy tính}, {Tivi, máy giặt, máy tính},