MỤC LỤC
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 4
1. Giới thiệu về khai phá dữ liệu 4
2. Lịch sử phát triển khai phá dữ liệu 5
3. Tại sao dùng khai phá dữ liệu 6
4. Quá trình khám phá tri thức từ cơ sở dữ liệu 6
5. Khai phá dữ liệu (data mining) 7
6. Các kỹ thuật khai phá dữ liệu 8
6.1. Phân cụm dữ liệu: 9
6.2. Phương pháp hồi quy: 10
6.3. Khai phá luật kết hợp: 10
7. Các quy trình khai phá dữ liệu 12
8. Các hệ thống khai phá dữ liệu (data mining systems) 14
9. Ứng dụng của khai phá dữ liệu 16
KHAI PHÁ LUẬT KẾT HỢP 17
1. Tổng quan về khai phá luật kết hợp 17
1.1. Quá trình khai phá luật kết hợp 17
1.2. Các khái niệm cơ bản 17
1.3. Phân loại luật kết hợp 18
2. Biểu diễn luật luật kết hợp 19
3. Khám phá các luật kết hợp dựa trên ràng buộc 20
TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 21
1. Thuật toán AIS 21
2. Thuật toán SETM 21
3. Thuật toán Apriori 22
3.1. Ý tưởng thuật toán Apriori 22
3.2. Thuật toán Apriori (Pseudo code) 23
3.3. Đặc điểm của thuật toán Apriori 25
3.4. Các cải tiến thuật toán Apriori (Methods to Improve Apriori’s Efficiency) 25
4. Thuật toán FP-growth 26
4.1. Ý tưởng thuật toán 26

FP-tree Frequent pattern tree
IT-tree Itemset-Tidset tree
I Tập các mục dữ liệu
ICD Phân loại bệnh tật quốc tế (ICD-10)
YHCT Y học cổ truyền
Minsup Độ hỗ trợ tối thiểu
Minconf Độ tin cậy tối thiểu
TID Định danh của giao tác
TID_List Danh sách định danh của giao tác
T Giao tác
k-itemset Một itemset có k items
L
k
Tập phổ biến k-itemsets
C
k
Tập ứng viên k-itemsets
kC
Tập ứng viên k-itemsets mà tập giao tác có chứa
nó.
We are data rich, but information poor.
“Necessity is the mother of invention”. - Plato
Nguyễn Văn Quang - CH1101126
2
Khóa luận môn học: Khai phá dữ liệu
LỜI NÓI ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông
tin đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin
tăng nhanh một cách nhanh chóng. Bên cạnh đó, việc tin học hóa một cách ồ ạt
và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực

ban cố vấn học tập và ban quản trị Chương trình đào tạo thạc sĩ Công nghệ của
trường Đại Học Công nghệ Thông tin – Đại học Quốc Gia thành phố Hồ Chí
Minh đã tạo điều kiện về tài liệu học tập và tham khảo.
Nguyễn Văn Quang - CH1101126
3
Khóa luận môn học: Khai phá dữ liệu
CHƯƠNG 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1. Giới thiệu về khai phá dữ liệu
Sự phát triển nhanh chóng 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, quản lý kinh tế, y học, khoa học kỹ thuật,
đã tạo ra nhiều cơ sở dữ liệu khổng lồ, có thể đơn cử vài ví dụ tiêu biểu như
CSDL siêu thị Walmart (Mỹ) chứa hơn 20 triệu giao tác bán hàng; CSDL nhân
khẩu Tp. HCM với hơn 7,5 triệu nhân khẩu. Để khai phá hiệu quả nguồn thông
tin từ các CSDL lớn hỗ trợ tiến trình ra quyết định, bên cạnh các khai thác thông
tin truyền thống, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và
phần mềm mới hỗ trợ tiến trình khám phá, phân tích tổng hợp thông tin.
Theo đánh giá của IBM, các phương pháp khai phá thông tin truyền thống
chỉ thu được khoảng 80% thông tin từ CSDL, phần còn lại gồm các thông tin
mang tính khái quát, thông tin có tính quy luật vẫn còn tiềm ẩn trong dữ liệu.
Lượng thông tin này tuy nhỏ nhưng là thông tin cốt lõi và cần thiết cho tiến trình
ra quyết định.
Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong CSDL. Cụ
thể hơn, đó là tiến trình trích lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn,
chưa biết nhưng hữu ích từ CSDL lớn.
Khai phá dữ liệu là tiến trình khái quát các sự kiện rời rạc trong dữ liệu
thành các tri thức mang tính khái quát, tính quy luật hỗ trợ tích cực cho các tiến
trình ra quyết định.
Nguồn dữ liệu phục vụ cho khai phá dữ liệu có thể là các CSDL lớn hay
các kho dữ liệu có cấu trúc hoặc không có cấu trúc. KPDL chỉ thực sự phát huy

- Những năm 1980: hoàn thiện lý thuyết về CSDL quan hệ và các hệ quản
trị CSDL quan hệ, xuất hiện các hệ quản trị CSDL cao cấp (hướng đối tượng,
suy diễn, ) và hệ quản trị CSDL hướng ứng dụng trong lĩnh vực không gian,
khoa học, công nghiệp, nông nghiệp, địa lý,
- Những năm 1990-2000: phát triển khai phá dữ liệu và kho dữ liệu, CSDL
đa phương tiện, và CSDL Web.
Khai phá dữ liệu là một công đoạn trong tiến trình lớn hơn là khám phá tri
thức từ CSDL. KPDL mang tính trực giác, cho phép thu được những hiểu biết rõ
ràng và sâu sắc hơn, vượt xa kho dữ liệu, đồng thời giúp phát hiện những xu thế
phát triển từ những thông tin quá khứ, cũng như cho phép đề xuất các dự báo
mang tính thống kê, gom cụm và phân loại dữ liệu. Kho dữ liệu điễn hình trong
những doanh nghiệp cho phép người dùng hỏi và trả lời những câu hỏi như
“Doanh số bán ra là bao nhiêu theo khu vực, theo nhân viên bán hàng của quý
III năm 2012 ?”. Trong khi đó, KPDL cho phép người ra quyết định kinh doanh
và trả lời cho những câu hỏi như là “Ai là khách hàng chính yếu của công ty đối
với mặt hàng cụ thể” hoặc “Dòng sản phẩm nào sẽ bán trong khu vực này và ai
sẽ mua chúng, dựa vào việc bán những sản phẩm tương tự ở khu vực đó”. Vị trí
của KPDL được thể hiện qua sơ đồ (xem hình 1)
Nguyễn Văn Quang - CH1101126
5
Hình 1: Vị trí khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
3. Tại sao dùng khai phá dữ liệu
Khai phá dữ liệu là cần thiết đối với người dùng vì những lý do sau:
- Ngày càng có nhiều dữ liệu được lưu trữ trong các CSDL, kho dữ liệu và
hình thành một “mỏ vàng dữ liệu” chứa đầy các thông tin chiến lược mà hệ quản
trị CSDL thông thường không thể phát hiện và quản trị được chúng.
- CSDL phát triển rất nhanh cả về kích thước lẫn số lượng, không xét
những thông tin mang tính sự kiện được lưu trữ trong CSDL, những thông tin
này được suy diễn từ nó cũng hết sức thú vị. Tuy nhiên với các quan hệ có số

và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá
trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không
đầy đủ (incomplete data), .v.v.
Nguyễn Văn Quang - CH1101126
6
Khóa luận môn học: Khai phá dữ liệu
- Chuyển đổi dữ liệu (data transformation): các dữ liệu được chuyển đổi
sang các dạng phù hợp cho quá trình xử lý.
- Khai phá dữ liệu (data mining): là một trong các bước quan trọng nhất,
trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ
liệu.
- Đánh giá mẫu (pattern evaluation): là quá trình đánh giá các kết quả tìm
được thông qua các độ đo nào đó.
- Biểu diễn tri thức (Knowledge presentation): là quá trình này sử dụng các
kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng. (xem hình 2)
5. Khai phá dữ liệu (data mining)
Khai phá dữ liệu là một quá trình trích xuất tri thức từ lượng lớn dữ liệu.
Một quá trình không dễ trích xuất thông tin ẩn, hữu ích, chưa được biết trước từ
dữ liệu.
Các thuật ngữ thường được dùng: knowledge discovery/mining in
data/databases (KDD), knowledge extraction, data/pattern analysis, data
archeology, data dredging, information harvesting, business intelligence.
Lượng lớn dữ liệu sẵn có để khai phá: bất kỳ loại dữ liệu được lưu trữ hay
tạm thời, có cấu trúc hay bán cấu trúc hay phi cấu trúc.
Dữ liệu được lưu trữ gồm: các tập tin truyền thống (flat files); các cơ sở
dữ liệu quan hệ (relational databases) hay quan hệ đối tượng (object relational
databases); các cơ sở dữ liệu giao tác (transactional databases) hay kho dữ liệu
(data warehouses); các cơ sở dữ liệu hướng ứng dụng như: cơ sở dữ liệu không
gian (spatial databases), cơ sở dữ liệu thời gian (temporal databases), cơ sở dữ
liệu không thời gian (spatio-temporal databases), cơ sở dữ liệu chuỗi thời gian

(inductive database) hỗ trợ khám phá tri thức. Chuẩn SQL/MM 6: Data Mining
của ISO/IEC 13249 - 6:2006 hỗ trợ khai phá dữ liệu. Đặc tả giao diện SQL cho
các ứng dụng và dịch vụ khai phá dữ liệu từ các cơ sở dữ liệu quan hệ.
6. Các kỹ thuật khai phá dữ liệu
- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc
các đặc tính chung của dữ liệu trên cơ sở dữ liệu hiện có. Các kỹ thuật này gồm
có: Gom nhóm (clustering), tóm tắt (summerization), trực quan hóa
visualiztation), phân tích sự phát triển và độ lệch (evolution and deviation
analyst), phân tích luật kết hợp (association rules),
- Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa
vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có: Phân lớp
(classification), hồi quy (regession), (Hình 3)
Nguyễn Văn Quang - CH1101126
8
Khóa luận môn học: Khai phá dữ liệu
Tuy nhiên, chỉ có một số phương pháp thông dụng nhất là: phân cụm dữ
liệu, phân lớp dữ liệu, phương pháp hồi quy và khai phá luật kết hợp
6.1. Phân cụm dữ liệu:
Mục tiêu chính của phương pháp phân cụ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 cụm sao cho các đối tượng thuộc cùng
một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không
tương đồng (Hình 4).
a) Phân lớp dữ liệu:
Nguyễn Văn Quang - CH1101126
9
Hình 3. Các kỹ thuật khai phá dữ liệu
Hình 4. Phân cụm dữ liệu
Khóa luận môn học: Khai phá dữ liệu
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các
mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm hai bước:

Chúng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ hỗ trợ 2%
có nghĩa là 2% của tất cả các vụ đang phân tích chỉ ra rằng máy tính và phần
mềm quản lý tài chính là đã được mua cùng nhau. Còn độ tin cậy 60% có nghĩa
là: 60% các khách hàng mua máy tính cũng mua phần mềm. Khai phá luật kết
hợp được thực hiện qua hai bước:
- Bước 1: Tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác
định qua tính hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu (min support)
- Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải
thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu (min confidence).
Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như
maketing có chủ đích, phân tích quyết định, quản lý kinh doanh, phân tích giá
thị trường, …
 Năm thành tố cơ bản để đặc tả một kỹ thuật khai phá dữ liệu:
- Dữ liệu cụ thể sẽ được khai phá (task-relevant data): phần dữ liệu từ các
dữ liệu nguồn được quan tâm. Tương ứng với các thuộc tính hay chiều dữ liệu
được quan tâm bao gồm: tên kho dữ liệu/cơ sở dữ liệu, các bảng dữ liệu hay các
khối dữ liệu, các điều kiện chọn dữ liệu, các thuộc tính hay chiều dữ liệu được
tâm, các tiêu chí gom nhóm dữ liệu.
- Loại tri thức sẽ đạt được (kind of knowledge): đặc trưng hóa dữ liệu, phân
biệt hóa dữ liệu, mô hình phân tích kết hợp hay tương quan, mô hình phân lớp,
mô hình dự đoán, mô hình gom cụm, mô hình phân tích phần tử biên, mô hình
phân tích tiến hóa.
- Tri thức nền (background knowledge): tương ứng với lĩnh vực cụ thể sẽ
được khai phá như hướng dẫn quá trình khám phá tri thức, hỗ trợ khai phá dữ
liệu ở nhiều mức trừu tượng khác nhau. Đánh giá các mẫu được tìm thấy, bao
gồm: các phân cấp ý niệm, niềm tin của người sử dụng về các mối quan hệ của
dữ liệu.
- Các độ đo (interestingness measures): thường đi kèm với các ngưỡng giá
trị (threshold); dẫn đường cho quá trình khai phá hoặc đánh giá các mẫu được
tìm thấy; tương ứng với loại tri thức sẽ đạt được và do đó, tương ứng với kỹ

+ Tìm kiếm các mẫu và mô hình: là không gian trạng thái, tập rời rạc các
trạng thái. Bài toán tìm kiếm được bắt đầu tại một node (trạng thái) cụ thể, di
chuyển qua không gian trạng thái để tìm thấy node tương ứng với trạng thái đáp
ứng tốt nhất hàm tỉ số.
+ Phương pháp tìm kiếm: chiến lược tham lam, có dùng heuristics, chiến
lược nhánh-cận.
+ Tối ưu hóa thông số.
- Chiến lược quản lý dữ liệu (data management strategy): dữ liệu được khai
phá ít hay toàn bộ được xử lý đồng thời trong bộ nhớ chính; hỗ trợ cách dữ liệu
được lưu trữ, đánh chỉ mục, và truy xuất. Giải thuật khai phá dữ liệu hiệu quả
(efficiency) và có tính co giãn (scalability) với dữ liệu được khai phá, và công
nghệ cơ sở dữ liệu.
7. Các quy trình khai phá dữ liệu
- Quy trình khai phá dữ liệu là một chuỗi lặp và tương tác gồm các bước
bắt đầu với dữ liệu thô (raw data) và kết thúc với tri thức (knowledge of interest)
đáp ứng được sự quan tâm của người sử dụng.
- Sự cần thiết của một quy trình khai phá dữ liệu là cách thức tiến hành
(hoạch định và quản lý) dự án khai phá dữ liệu có hệ thống; đảm bảo nỗ lực
dành cho một dự án khai phá dữ liệu được tối ưu hóa. Việc đánh giá và cập nhật
các mô hình trong dự án được diễn ra liên tục.
Các tiến trình khai phá dữ liệu:
Nguyễn Văn Quang - CH1101126
12
Khóa luận môn học: Khai phá dữ liệu
Nguyễn Văn Quang - CH1101126
13
Chọn các giải thuật KPDL
KPDL: Tìm kiếm tri thức
Đánh giá mẫu tìm được
Biểu diễn tri thức

Khóa luận môn học: Khai phá dữ liệu
o User interface: thành phần hỗ trợ sự tương tác giữa người sử dụng và hệ
thống khai phá dữ liệu. Người sử dụng có thể chỉ định câu truy vấn hay
tác vụ khai phá dữ liệu, có thể được cung cấp thông tin hỗ trợ việc tìm
kiếm, thực hiện khai phá dữ liệu sâu hơn thông qua các kết quả khai phá
trung gian, cũng có thể xem các lược đồ cơ sở dữ liệu/kho dữ liệu, các cấu
trúc dữ liệu; đánh giá các mẫu khai phá được; trực quan hóa các mẫu này
ở các dạng khác nhau.
Những đặc điểm được dùng để khảo sát một hệ thống khai phá dữ liệu
bao gồm:
- Kiểu dữ liệu.
- Các vấn đề hệ thống.
- Nguồn dữ liệu.
- Các tác vụ và phương pháp luận khai phá dữ liệu.
- Vấn đề gắn kết với các hệ thống kho dữ liệu hay cơ sở dữ liệu.
- Khả năng co giãn dữ liệu.
- Các công cụ trực quan hóa.
- Ngôn ngữ truy vấn khai phá dữ liệu và giao diện đồ họa cho người dùng.
Một số hệ thống khai phá dữ liệu: Intelligent Miner (IBM), Microsoft data
mining tools (Microsoft SQL Server 2000/2005/2008/2012), Oracle Data
Mining (Oracle 9i/10g/11g/11gR2), Enterprise Miner (SAS Institute),
Nguyễn Văn Quang - CH1101126
15
Hình 6. Kiến trúc của một hệ thống khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
9. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu là một hướng tiếp cận mới đã thu hút được rất nhiều sự
quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực
tiễn của nó. KPDL được ứng dụng rộng rãi trong rất nhiều lĩnh vực, sau đây là
một số ứng dụng điễn hình:

Items trong trong các CSDL giao tác (transaction database) hoặc trong những
kho dữ liệu (data warehouse).
Hiện nay các công ty phải lưu một số lượng dữ liệu bán hàng khổng lồ.
Một bản ghi trong CSDL này chứa các thông tin về ngày mua, bán hàng, … Từ
CSDL bán hàng, chúng ta có thể tìm ra các mối quan hệ giữa các cặp thuộc tính
– giá trị thuộc tính. Một luật kết hợp tiêu biểu:
Ví dụ: “78% khách hàng mà mua sữa hộp Vinamilk thì mua trà Lipton.
Các công ty thành công thường tìm kiếm những luật như vậy để biết được
xu hướng của thị trường, từ đó đưa ra những chương trình và chiến lược nhập
hàng và bố trí các mặt hàng,….phù hợp.
1.1. Quá trình khai phá luật kết hợp
Ví dụ: Phân tích bán hàng trong siêu thị
1.2. Các khái niệm cơ bản
Phần tử (Item): là các phần tử, mẫu, đối tượng đang được quan tâm, như J
= {I1, I2, …, Im}: tập tất cả m phần tử có thể có trong tập dữ liệu.
Tập phần tử (Itemset): là tập hợp các items, một itemset có k items gọi là
k-itemset.
Giao dịch (Transaction): là lần thực hiện tương tác với hệ thống (ví dụ:
giao dịch “khách hàng mua hàng”). Liên hệ với một tập T gồm các phần tử được
giao dịch.
Nguyễn Văn Quang - CH1101126
17
Khóa luận môn học: Khai phá dữ liệu
Sự kết hợp (Association) và luật kết hợp (association rule): là sự kết hợp
các phần tử cùng xuất hiện với nhau trong một hay nhiều giao dịch.Thể hiện mối
liên hệ giữa các phần tử hay các tập phần tử.
Luật kết hợp: qui tắc kết hợp có điều kiện giữa các tập phần tử. Thể hiện
mối liên hệ (có điều kiện) giữa các tập phần tử. Ví dụ cho A và B là các tập phần
tử, luật kết hợp giữa A và B là A à B. B xuất hiện trong điều kiện A xuất hiện.
Hỗ trợ (Support): là độ đo đo tần số xuất hiện của các phần tử hay tập

đến các phần tử/thuộc tính ở một mức trừu tượng. Ví dụ:
Age(X, “30 39”) à Buys(X, “computer”)
Age(X, “18 29”) à Buys(X, “camera”)
Nguyễn Văn Quang - CH1101126
18
Khóa luận môn học: Khai phá dữ liệu
Luật kết hợp đa mức (multilevel association rule): luật liên quan đến các
phần tử/thuộc tính ở các mức trừu tượng khác nhau. Ví dụ:
Age(X, “30 39”) à Buys(X, “laptop computer”)
Age(X, “30 39”) à Buys(X, “computer”)
Luật kết hợp (Association rule): luật kết hợp mạnh AàB đáp ứng yêu cầu
ngưỡng hỗ trợ tối tiểu và ngưỡng tin cây tối tiểu (minimum support threshold và
minimum confidence threshold).
Luật tương quan thống kê (Correlation rule): luật kết hợp mạnh A à B
đáp ứng yêu cầu về sự tương quan thống kê giữa A và B.
2. Biểu diễn luật luật kết hợp
Dạng luật: AàB [support, confidence]
Cho trước minimum support threshold (min_sup), minimum confidence
threshold (min_conf)
A và B là các itemsets
Frequent itemsets/subsequences/substructures Itemset/subsequence/
substructure X là frequent nếu support(X) >= min_sup. Trong đó: Itemsets: tập
các items, Subsequences: chuỗi tuần tự các events/items, Substructures: các tiểu
cấu trúc (graph, lattice, tree, sequence, set, …)
Closed frequent itemsets
Một itemset X closed trong J nếu không tồn tại tập cha thực sự Y nào
trong J có cùng support với X.
X ⊆ J, X closed iff ∀ Y ⊆ J và X ⊂ Y: support(Y) <> support (X).
X là closed frequent itemset trong J nếu X là frequent itemset và closed
trong J.

phá.
Khám phá luật (rules) hay tập phần tử phổ biến (frequent itemsets) thỏa
các ràng buộc, có hai cách tiếp cận:
- Cách tiếp cận trực tiếp: áp dụng các giải thuật truyền thống, kiểm tra các
ràng buộc cho từng kết quả đạt được. Nếu thỏa ràng buộc thì trả về kết
quả sau cùng.
- Cách tiếp cận dựa trên tính chất của các ràng buộc: phân tích toàn diện
các tính chất của các ràng buộc. Kiểm tra các ràng buộc càng sớm càng
tốt trong quá trình khám phá các tập phổ biến hay các luật (rules or
frequent itemsets). Không gian dữ liệu được thu hẹp càng sớm càng tốt.

Nguyễn Văn Quang - CH1101126
20
Khóa luận môn học: Khai phá dữ liệu
CHƯƠNG 3
TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP
1. Thuật toán AIS
Thuật toán do Agrwal đề nghị năm 1993. Thuật toán này chú trọng khai
phá luật kết hợp có dạng XàY, với Y là tập hợp chỉ bao gồm 1 tính chất (tập
hợp 1 phần tử). Thuật toán tìm cách xây dựng dần dần các tập ứng cử viên cho
“chức vụ” tập hợp xuất hiện σ – thường xuyên. Với cách đánh số thứ tự từ điển
cho từng tính chất, việc bổ sung phần tử cho tập ứng cử viên tránh được trùng
lặp, do vậy tiết kiệm tối đa thời gian tính toán.
Số lượng các tập ứng cử viên quá nhiều có thể gây ra hiện tượng tràn bộ
nhớ. Thuật toán đề nghị một phương án quản lý bộ nhớ hợp lý đề phòng trường
hợp này: không cho phép các ứng cử viên chiếm bộ nhớ, mà ghi thẳng chúng
vào đĩa ở chế đồ thường trực (disk-resident).
 Thuật toán AIS (Pseudo code)
Input: CSDL D, minsup
Output: các tập mục phổ biến

Sarawagi đã chỉ ra Thuật toán này không hiệu quả.
 Thuật toán SETM(Pseudo code)
Input: CSDL D, minsup
Output: Các tập mục phổ biến
1. L1 = {các tập mục phổ biến};
2. L1’={các tập mục phổ biến cùng các TID của nó được sắp xếp theo
TID};
3. for (k=2; Luật kết hợpk-1 ≠ ∅ ; k++ ) do begin
4. Ck = ∅;
5. forall các giao dịch t ∈ D do begin
6. Lt = (l ∈ L’k-1 | l.TID = t.TID); // các tập có (k - l) mục phổ biến trong
giao dịch t
7. forall các tập mục phổ biến lt ∈ Lt do begin
8. Ct = tăng lt thêm một mục có trong giao dịch t; //Các ứng cử viên có
trong t
9. C’k +={<t.TID, c>| c ∈ Ct};
10. end
11. end
12. Sort C’k theo các tập mục;
13. delete các mục c ∈ C’k có c.count<minsup đưa vào L’k ;
14. Lk ={<l.itemset, countof l in L’k > | l ∈ Lk'}; //kết hợp với bước 13
15. Sort L’k theo TID;
16. end
17. Trả lời = ∪k Lk ;
3. Thuật toán Apriori
3.1. Ý tưởng thuật toán Apriori
- Tìm tất cả frequent itemsets: k-itemset (itemsets gồm k items) được
dùng để tìm (k+1)- itemset.
Đầu tiên tìm 1-itemset (ký hiệu L1). L1 được dùng để tìm L2 (2-
itemsets). L2 được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có

{A1,A2} =>{A5}, {A1,A5} =>{A2}, {A2,A5} => {A1}
3.2. Thuật toán Apriori (Pseudo code)
- Input: CSDL D, minsup.
- Output: Tập các tập mục phổ biến.
Đầu tiên đếm số items và xác định L
1

Bước tiếp theo gồm 2 phần chính:
* C
k
tạo được bằng các kết L
k-1
với chính nó.
* Những tập kích thước (k-1) không phổ biến không thể là tập con của tập
phổ biến kích thước k.
1) L
1
= {large 1-itemsets};
2) for ( k = 2; L
k-1
≠ ∅; k++ ) do begin
3) C
k
= apriori-gen(L
k-1
); // Ứng viên mới
4) forall transactions t ∈ D do begin
5) C
t
= subset(C

1 A,C,D C1 {A} 2 L1 {A} 2
2 B,C,E 1st scan {B} 3 {B} 3
3 A,B,C,E {C} 3 {C} 3
4 B,E {D} 1 {E} 3
{E} 3
Itemsets Sup Itemsets Sup Itemsets
{A,C} 2 L2 {A,B} 1 C2 {A,B}
{B,C} 2 {A,C} 2 {A,C}
{B,E} 3 {A,E} 1 2nd scan {A,E}
{C,E} 2 {B,C} 2 {B,C}
{B,E} 3 {B,E}
{C,E} 2 {C,E}
Itemsets C3 Itemsets Sup L3 Itemsets Sup
{A,B,C} {A,B,C} 1 {B,C,E} 2
{A,B,E} 3th scan {A,B,E} 1
{A,C,E} {A,C,E} 1
{B,C,E} {B,C,E} 2
Ta có frequent itemsets I ={B,C,E}, với min_conf =80% ta có 2 luật kết hợp là
Nguyễn Văn Quang - CH1101126
24
Associaltion Rule Confidence
{B}=>{C,E} 67%
{C}=>{B,E} 67%
{E}=>{B,C} 67%
{B,C}=>{E} 100%
{B,E}=>{C} 67%
{C,E}=>{B} 100%
Khóa luận môn học: Khai phá dữ liệu
 Tạo Apriori Candidate :
Hàm apriori-gen nhận đối số L

1
, . . ., p.item
k-2
= q.item
k-2,
p.item
k-1
< q.item
k-1
; (điều kiện p.item
k-1
< q.item
k-1
để đảm bảo sẽ không có bộ trùng
được phát sinh).
- Bước kế tiếp xén bớt, chúng ta xoá tất cả các itemsets c∈C
k
. Sao cho
tập con của c không có trong L
k-1.

forall itemsets c ∈ C
k
do
forall (k-1)-subsets s of c do
if (s ∉ L
k-1
) then
delete c from C
k

3.4. Các cải tiến thuật toán Apriori (Methods to Improve Apriori’s Efficiency)
- Đếm dựa vào kỹ thuật bảng băm (hash-based itemset counting): Một
k-itemset ứng với hashing bucket count nhỏ hơn minimum support
threshold không là một frequent itemset.
- Giảm giao dịch (transaction reduction): Một giao dịch không chứa
frequent k-itemset nào thì không cần được kiểm tra ở các lần sau (cho
k+1-itemset).
- Phân hoạch (partitioning): Một itemset phải frequent trong ít nhất một
phân hoạch thì mới có thể frequent trong toàn bộ tập dữ liệu.
- Lấy mẫu (sampling): Khai phá chỉ tập con dữ liệu cho trước với một trị
support threshold nhỏ hơn và cần một phương pháp để xác định tính
toàn diện (completeness).
Nguyễn Văn Quang - CH1101126
25