ĐẠ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 THU HOẠCH MÔN:
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
ĐỀ TÀI:
XÂY DỰNG ỨNG DỤNG CHO BÀI TOÁN PHÂN TÍCH HÀNH VI MUA
SẮM CỦA KHÁCH HÀNG TRONG CÁC SIÊU THỊ
Ging viên phụ trách: GS, TSKH. HOÀNG KIẾM
Học viên thực hiện: Lê Phước Vinh
TP. HỒ CHÍ MINH, THÁNG 10/2014
MỤC LỤC
MỤC LỤC 2
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT 3
Chương 1 – KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 4
Chương 2-KHAI THÁC TẬP PHỔ BIẾN & LUẬT KẾT HỢP 15
Chương 3- XÂY DỰNG ỨNG DỤNG CHO BÀI TOÁN PHÂN TÍCH HÀNH VI
MUA SẮM CỦA KHÁCH HÀNG TRONG CÁC SIÊU THỊ 33
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
STT Từ viết tắt Giải nghĩa
1 CSDL Cơ sở dữ liệu
2 I Tập các mục dữ liệu
3 Minsup Độ hỗ trợ tối thiểu
4 Minconf Độ tin cậy tối thiểu
5 KDD Knowledge Discovery in Database
6 TID Định danh của giao tác
7 T Giao tác
8 k-itemset Một itemset có k items
9 L
k
Tập phổ biến k-itemsets
10 C

có thể lĩnh hội được.
- Độ chính xác: Dù cho những mẫu khai phá thật sự có trong CSDL hay không
thì việc đo lường trị giá của chúng là bắt buộc phi có. Chúng ta sẽ chỉ sử dụng những
mẫu nào có độ chính xác càng cao thì hiệu qu công việc đạt được càng lớn, những
mẫu có độ chính xác chưa được xác định rõ ràng hoặc không cao thì không nên sử
dụng chúng.
4
- Tính hấp dẫn: Khám phá tri thức được coi là lý thú vì nó có thể vạch ra các xu
hướng một cách hoàn thiện. Đó là những điều mới lạ hay những quy trình tìm năng,
hữu ích ẩn chứa từ trong dữ liệu trước đó.
- Tính hiệu qu: thời gian chạy của thuật toán khám phá tri thức trên CSDL lớn
có thể dự tính và chấp nhận được. Dữ liệu là tập hợp những bộ thông tin chính xác và
quá trình khám phá tri thức được xem là sự lọc bỏ các dư thừa, được rút gọn tới mức
tối thiểu chỉ để lại các đặc trưng cơ bn cho dữ liệu. Tri thức được tìm thấy là các
thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ trong chúng. Các mối
quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học.
Nếu khám phá tri thức là toàn bộ quá trình chiết xuất tri thức từ các CSDL thì
KPDL là giai đoạn chủ yếu của quá trình đó. KPDL là một quá trình phát hiện các mẫu
mới, thường bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm kiếm các
mẫu từ tập dữ liệu theo mô hình đó. Sử dụng các kỹ thuật và các khái niệm của các
lĩnh vực đã được nghiên cứu từ trước như: học máy, nhận dạng, thống kê, hồi quy, xếp
loại, phân nhóm, các mô hình đồ thị, các mạng Bayes,… Hầu hết các CSDL đều chứa
rất nhiều các mẫu mới và có ích, tuy nhiên mẫu có giá trị với mục tiêu đặt ra phi là
những mẫu không tầm thường. Để các mẫu trở nên không tầm thường, hệ thống phi
làm nhiều hơn là chỉ mò mẫm thống kê vì kết qu của việc tính toán trực tiếp qua công
tác thống kê là đã có đối với người dùng. Một hệ thống tìm kiếm cần phi có kh năng
quyết định cần thực hiện tính toán nào và kết qu là có đáng quan tâm để tạo nên tri
thức trong ngữ cnh hiện tại hay không.
KPDL được sử dụng để tạo ra gi thuyết. Ví dụ như để xác định các yếu tố rủi ro
khi cho vay tín dụng, kỹ thuật KPDL phi phát hiện được những người có thu nhập

trình
khám
phá tri thức
6
Knowled
ge
Internet
,
Internet
,
Gatheri
ng
Selectio
n
Cleansing
Pre-
processing
Transform
ati
Data
Mining
Envalution
of
Data
Targe
t
Data
Cleansed
Preproccess
ed

nghĩa và không có kh năng kết nối dữ liệu, ví dụ: điểm = -1. Giai đoạn này sẽ tiến
hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được
xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan
trọng vì dữ liệu này nếu không được “làm sạch” sẽ gây nên những kết qu sai lệch
nghiêm trọng.
1.2.4. Chuyển đổi dữ liệu (Transformation)
Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu được chuyển đổi hay được hợp
nhất về dạng thích hợp cho việc khai phá.
1.2.5. Khai phá dữ liệu (Data Mining)
7
Đây là một tiến trình cốt yếu. Ở giai đoạn này nhiều thuật toán khác nhau đã
được sử dụng một cách phù hợp để trích xuất thông tin có ích hoặc cá mẫu điển hình
trong dữ liệu.
1.2.6. Đánh giá kết quả mẫu (Evaluation of Result)
Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu
dữ liệu được chiết xuất, không phi bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi
nó còn bị sai lệch. Vì vậy, cần phi ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra
các tri thức cần thiết.
Từ quá trình khám phá tri thức trên chúng ta thấy được sự khác biệt giữa khám
phá tri thức và khai phá dữ liệu. Trong khi khám phá tri thức là nói đến quá trình tổng
thể phát hiện tri thức hữu ích từ dữ liệu. Còn KPDL chỉ là một bước trong quá trình
khám phá tri thức, các công việc chủ yếu là xác định được bài toán khai phá, tiến hành
lựa chọn phương pháp KPDL phù hợp với dữ liệu có được và tách ra các tri thức cần
thiết.
1.3 Các loại dữ liệu có thể khai phá
Các loại dữ liệu có thể được khai phá như sau:
• Cơ sở dữ liệu quan hệ (relational databases): là những CSDL được tổ chức
theo mô hình quan hệ. Hiện nay, các hệ qun trị CSDL đều hỗ trợ mô hình này như:
MS Access, MS SQL Server, Oracle, IBM DB2,
• Cơ sở dữ liệu đa chiều (multidimention structures, data warehouse, data

thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training
data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phi được xác định trước khi
xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát
(supervised learning) khác với phân nhóm dữ liệu là học không có giám sát
(unsupervised learning).
- Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phi tính độ
chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng
để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai.
Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây
quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng
Nơron (Neural networks), Gii thuật di truyền (Genetic algorithms), Mạng Bayesian
(Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets).
a) Cây quyết định (Decision Tree)
Các kỹ thuật phân lớp sử dụng cây quyết định để phân tách các dữ liệu cho đến
khi mỗi phần chứa đựng hầu hết các mẫu từ một lớp đặc trưng, kết qu của quá trình
sẽ cho ra một cây quyết định. Điểm phân tách trong cây quyết định là một nút (không
phi là nút lá) sẽ sử dụng một số điều kiện để quyết định dữ liệu sẽ được phân tách
như thế nào. Các nút cuối cùng trong cây quyết định chứa đựng các bộ mẫu giống
nhau. Lợi thế của cây quyết định là các thuật toán chạy khá nhanh, với kết qu khá tốt
9
và có thể gii thích được rõ ràng. Tuy nhiên, bất lợi mà các thuật toán của cây quyết
định có thể gặp phi đó là chúng có thể tìm ra các điểm tới hạn cục bộ, đưa ra các kết
qu không đúng.
b) K-láng giềng gần nhất (k-Nearest Neighbor)
Thuật toán này tìm ra các láng giềng gần nhất của mẫu thử nghiệm và quy về các
nhãn lớp của chúng dựa trên các nhãn đa số, điều đó có nghĩa là các mẫu được quy về
cùng lớp khi chúng là lân cận của nhau. Kỹ thuật này cho rằng vị trí trong không gian
đặc trưng hàm ý một quan hệ họ hàng gần gũi ở giữa các nhãn lớp.
Lợi thế của các thuật toán K-Láng giềng gần nhất là dễ thực thi, và kết qu mà nó
đem lại kh năng dễ dàng gii thích. Nhưng một điểm bất lợi là các thuật toán này đưa

của nó là cần thu thập được các tri thức chuyên gia truyền thống.
f) Tập mờ và tập thô (Rough and Fuzzy Sets)
Lý thuyết về tập mờ và tập thô dựa trên một sơ sở toán học không chắc chắn. Đối
với các mô hình tập thô, một giới hạn trên và giới hạn dưới sẽ được xác định. Một tập
thô định nghĩa một lớp C là một xấp xỉ bởi hai tập. Tập cận dưới (lower) của C bao
gồm tất c các mẫu dữ liệu, mà dựa vào tri thức của các mẫu dữ liệu có thể quyết định
một mẫu bất kỳ thuộc phân lớp C một cách rõ ràng. Tập cận trên của C bao gồm tất c
các mẫu với giá trị của thuộc tính được mô t không thể thuộc vào phân lớp C. Mô
hình tập mờ không dốc về cực đại cục bộ bằng các thuật toán cây quyết định, và cũng
giống như mô hình tập thô, chúng dùng để đối phó với những điều không chắc chắn
tốt hơn bất kỳ một thuật toán nào khác.
1.4.2. Luật kết hợp (Association Rules)
Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơ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 CSDL. Mẫu đầu ra của gii thuật KPDL là tập luật kết hợp tìm được.
Tuy luật kết hợp là một dạng luật khá đơn gin nhưng lại mang rất nhiều ý nghĩa.
Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ ra quyết định. Tìm
kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp
là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu.
1.4.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns)
Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian.
Một luật mô t mẫu tuần tự có dạng tiêu biểu X ->Y phn ánh sự xuất hiện của biến cố
X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo cao.
1.4.4. Phân nhóm- đoạn (Clustering / Segmentation)
Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự nhau
trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối tượng trong
cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các
nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau
và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này,
nhưng cũng có thể vừa thuộc nhóm khác. Không giống như phân lớp dữ liệu, phân

phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật “nếu - thì” -
nếu tiền đề đúng thì kết luận đúng. Về nguyên tắc, c tiền đề và kết luận đều có thể là
sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề thường là nhóm các giá
trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa, hệ thống có thể phát hiện các
12
luật phân lớp trong đó tất c các luật cần phi có cùng một thuộc tính do người dung
chỉ ra trong kết luận.
Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy Bayes. Đó là
đồ thị có hướng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết
phụ thuộc giữa các nút đó.
1.4.8. Phát hiện sự biến đổi và độ lệch (Change and deviation detection)
Tập trung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết
trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu
thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian và
lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu thời gian.
Độ lệch theo nhóm là sự khác nhau của dữ liệu trong hai tập con dữ liệu, ở đây
xét c trường hợp tập con dữ liệu này thuộc tập con kia. Nghĩa xác định dữ liệu trong
một nhóm con của đối tượng có khác đáng kể so với toàn bộ đối tượng không? Theo
cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường sẽ được phát hiện.
1.5 Ứng dụng của khai phá dữ liệu
KPDL có nhiều ứng dụng trong thực tế, một số ứng dụng điển hình như: Bo
hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và dự báo giá
của các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn và giá, lãi suất, dữ
liệu thẻ tín dụng, phát hiện gian lận, …
Điều trị y học và chăm sóc y tế: một số thông tin về chẩn đoán bệnh lưu trong
các hệ thống qun lý bệnh viện. Phân tích mối liên hệ giữa triệu chứng bệnh, chẩn
đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc,…).
Sn xuất và chế biến: qui trình, phương pháp chế biến và xử lý xử cố Text
mining & Web mining: phân lớp văn bn và các trang web, tóm tắt văn bn,
Lĩnh vực khoa học: quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm

thời, chúng ta không cần biết khách hàng cụ thể là ai.
Nhà qun lý dùng những thông tin này đểđiều chỉnh việc nhập hàng về siêu thị,
hay đơn gin là để bố trí sắp xếp các mặt hàng gầnnhau, hoặc bán các mặt hàng đó
theo một gói hàng, giúp cho khách hàng đỡ mất công tìm kiếm.
Khai phá luật kết hợp được mô t như sự tương quan của các sự kiện, những sự
kiện xuấthiện thường xuyên một các đồng thời. Nhiệm vụ chính của khai phá luật kết
hợp là phát hiệnra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của
một cơ sở dữ liệu chotrước.
Bài toán khai phá luật kết hợp là bài toán rất quan trọng trong lĩnh vực khai phá
dữ liệu: Vạch ra các tính chất ẩn, quan trọng của tập dữ liệu.
2.2 Các khái niệm cơ bản
2.2.1 CSDL giao dịch (Transaction Database)
CSDL giao dịch D gồm các giao dịch T là tập các giao dịch t
1
, t
2
, …, t
n
.T = {t
1
, t
2
,
…, t
n
}. T gọi là cơ sở dữ liệu giao dịch (Transaction Database)
Mỗi giao dịch t
i
bao gồm tập các đối tượng I (gọi là itemset). I = {i
1

chi đánh răng, nước rửa chén Sunlight}.
2.2.2 Hạng mục (Ttem)
Hạng mục là mặt hàng trong giỏ hay một thuộc tính nào đó của đối tượng đang
xét trong CSDL (i
k
: k m, với m là số thuộc tính của đối tượng)
2.2.3 Tập các hạng mục (Itemset)
Tập các hạng mục I = {i
1
, i
2
, …, i
m
} là tập hợp các thuộc tính của đối tượng đang
xét trong CSDL.
Ví dụ: I = {Dầu gội, lăn ngăn mùi Rexona, sữa tắm, dầu x, kem đánh răng, bàn
chi đánh răng}.
2.2.4 Giao dịch (Transaction)
Là tập các hạng mục trong cùng một đơn vị tương tác, mỗi giaodịch được xử lý
một cách nhất quán mà không phụ thuộc vào cácgiao dịch khác.
2.2.5 Luật kết hợp(Association Rules)
 Gọi I = {i
1
, i
2
, …, i
m
}là tập các trường gọi là items.
 D là tập giao tác, ở đó mỗi giao tác T
i

Supp(X Y) =
Khi chúng ta nói rằng độ hỗ trợ của một luật là 50%, có nghĩa là có 50% tổng số
bn ghi chứa XY. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật.
Trong một số trường hợp, chúng ta chỉ quan tâm đến những luật có độ hỗ trợ cao.
Nhưng cũng có trường hợp, mặc dù độ hỗ trợ của luật thấp, ta vẫn quan tâm.
2.2.7 Tập phổ biến
Tập phổ biến là tập các hạng mục có độ hỗ trợtho mãn độ hỗ trợ tối thiểu
(minsupp - là một giá trị do người dùngxác định trước). Nếu tập mục X có Supp(X)
Minsupp thì ta nóiX là một tập các mục phổ biến
17
Tập phổ biến tối đại (Max-Pattern): Là tập phổ biến và không tồn tại tập nào
baonó là phổ biến (Bayardo – SIGMOD’98).
Ví dụ: Cho CSDL giao dịch D như bng 2.1.
 Với Minsupp = 50%.
 Tập phổ biến tương ứng với ngưỡng minsupp = 50% là: {{dầu gội, dầu x},
{dầu gội, sữa tắm}, {dầu x, sữa tắm}, {kem đánh răng, bàn chi đánh răng}, {dầu
gội, dầu x, sữa tắm}}.
 Tập phổ biến tối đại: {{dầu gội, dầu x, sữa tắm}, {kem đánh răng, bàn chi
đánh răng}}.
Tập phổ biến đóng (Closed Pattern): Là tập phổ biến và không tồn tại tập nào
baonó có cùng độ phổ biến như nó (Pasquier, ICDT’99).
 Tập phổ biến đóng: {{dầu gội, dầu x, sữa tắm}, {kem đánh răng, bàn chi
đánh răng}}.
2.2.8 Độ tin cậy (confidence)
2.1.8.1 Định nghĩa 2.3
Độ tin cậy của một luật kết hợp X Y là tỷ lệ giữa số các bn ghi trong D chứa
X Y với số bn ghi trong D có chứa tập hợp X. Ký hiệu độ tin cậy của một luật là
Conf(R). Ta có 0 conf(R) 1.
Nhận xét: Độ hỗ trợ và độ tin cậy có xác suất sau:
Supp(X Y) = P(X Y).

Nếu mục B là mục phổ biến trên D, nghĩa là sup(B) minsup thì mọi tập con A
của B là tập phổ biến trên D vì sup(A) sup(B) > minsup.
2.3.2 Các tính chất của luật kết hợp (4 tính chất)
2.3.2.1 Tính chất 1 (không hợp các luật kết hợp)
Nếu có X Z và Y Z trong D thì không nhất thiết X Y Z là đúng.
19
Xét trường hợp X Z = và các tác vụ trong D hỗ trợ Z nếu và chỉ nếu chúng hỗ
trợ mỗi X hoặc Y, khi đó luật X Y Z có độ hỗ trợ 0%.
Tương tự : X Y X Z X Y Z.
2.3.2.2 Tính chất 2 (Không tách luật)
Nếu X Y Z thì X Z và Y Z chưa chắc xy ra.
Ví dụ: Trường hợp Z có mặt trong một giao tác chỉ khi c X và Y cũng có mặt,
tức là sup(X Y)= sup(Z), nếu độ hỗ trợ của X và Y đủ lớn hơn sup(X Y), tức là
sup(X) > sup(X Y) và sup(Y) > sup(X Y) thì hai luật riêng biệt sẽ không đủ độ tin
cậy.
Tuy nhiên đo lại: X Y Z X Y X Z.
2.3.2.3 Tính chất 3 (Các luật kết hợp không có tính 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(X), T(Y), T(Z) tương ứng là các giao
dịch chứa X,Y,Z, và độ tin cậy cực tiểu minconf
conf(X Y) = conf(Y Z)=minconf thế thì:
conf(X Y) =minconf2 < minconf vì minconf< 1, do đó luật X Z không đủ độ
tin cậy.
2.3.2.4 Tính chất 4
Nếu A (L - A) không tho mãn độ tin cậy cực tiểu thì luật
B (L -B) cũng không tho mãn, với các tập mục L,A,B và B A L
20
Vì supp(B) sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta nhận
được:
Cũng như vậy: Nếu có (L- C) C thì ta cũng có luật (L – D) D, với D C và

R4: sữa tắm dầu gội
100%
R5: dầu x sữa tắm
100%
R6: sữa tắm dầu x
100%
R7: kem đánh răng bàn chi đánh răng
100%
R8: bàn chi đánh răng kem đánh răng
100%
R9: dầu gội dầu x,sữa tắm
100%
R10: dầu x dầu gội,sữa tắm
100%
R11: sữa tắm dầu gội,dầu x
100%
R12: dầu gội,dầu x sữa tắm
100%
R13: dầu gội, sữa tắm dầu x
100%
R14: dầu x,sữa tắm dầu gội
Bảng 2.3 Luật kết hợp thỏa minconf = 100%
2.5 Các thuật toán khai phá dữ liệu bằng luật kết hợp
2.5.1 Thuật toán Apriori
2.5.1.1 Ý tưởng thuật toán Apriori
Thuật toán khai thác các tập phổ biến bằng cách thực hiện nhiều lần duyệt
CSDL. Duyệt lần thứ nhất để tính độ phổ biến của các 1-itemset và xác định các item
phổ biến từ chúng, nghĩa là độ phổ biến thỏa ngưỡng phổ biến tối thiểu. Trong các lần
duyệt sau, thuật toán sẽ kết hợp các itemset phổ biến đã tìm được trong lần duyệt trước
để tìm các tập ứng viên. Sau đó, tính độ phổ biến thực sự của các tập ứng viên này

các tập hợp – thường xuyên có 2 phần tử. Ký hiệu tập hợp này là L
2
.
Bước 3: Với chú ý đã nêu (về tính chất tăng dần của các tập hợp – thường
xuyên), ta tiến hành tìm các ứng cử viên có 3 phần tử (lấy từ L
1
). Gọi nó là tập C
3
. Lưu
ý là nếu {A, B, C} muốn là “ứng cử viên” thì các tập 2 phần tử {A, B},{B,C},{C, A}
đều phi là – thường xuyên, tức là chúng đều là phần tử của tập L
2
. Ta đi kiểm tra
trong tập C
3
và lọc ra được tập các tập hợp – thường xuyên có 3 phần tử. Tập hợp
này được ký hiệu là L
3
.
23
Bước 4: Tiến hành tìm các ứng cử viên có n phần tử. Gọi tập của chúng là tập C
n
và từ đây, lọc ra L
n
là tập tập các tập hợp – thường xuyên có n phẩn tử.
2.5.1.3 Mã giả thuật toán Apriori
Đoạn mã gi sau đây trình bày thuật toán Apriori: L
1
chứa các 1-itemset thỏa
minSupCount(dòng 1), từ dòng 2 đến dòng 6 là quá trình lặp đi lặp lại của việc sinh

k
.count++
7) L
k
= {c
k
C
k
| c
k
.count minSupCout}
8) F
I
= U
k
L
k
Apriori_gen(L
k-1
)
9) C
k
=
24
10)for each�
1
L
k-1
do
11)for each�

k
16)return C
k
Has_infrequent_subset(c, L
k-1
)
17)foreach (k -1)-itenset s c do
18)if s L
k-1
then
19)return True
20)return False
2.5.1.4 Thách thức của thuật toán Apriori
Thuật toán kinh điển Apriori tìm tập mục phổ biến thực hiện tốt bởi rút gọn kích
thước các tập ứng cử nhờ kỹ thuật tỉa. Tuy nhiên, trong tình huống mà số các giao tác
nhiều, hoặc với độ hỗ trợ cực tiểu thấp, các thuật toán Apriori gặp phi 2 vấn đề làm
nh hưởng tới tốc độ :
 Vấn đề khi số lượng các tập ứng cử cực lớn. Ví dụ: nếu có 10
4
tập phổ biến 1-
itemset thì thuật toán Apriori sẽ phi tạo ra 10
7
các ứng cử 2– itemset; để khám phá
được một số mẫu phổ biến kích thước 100, chẳng hạn tập {a
1
,a
2
, ,a
100
} thì nó cần tạo