MỤC LỤC
TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI MỎ DỮ LIỆU 3
1. Phát hiện tri thức và khai mỏ dữ liệu 3
2. Quá trình phát hiện tri thức từ cơ sở dữ liệu 4
3. Khai mỏ dữ liệu 7
LUẬT KẾT HỢP TRONG KHAI MỎ DỮ LIỆU 14
1. Khai phá luật kết hợp 14
2. Lý thuyết về luật kết hợp 14
2.1. Khái niệm 14
2.2 Một số tính chất: 15
TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 17
1. Thuật toán AIS 17
2. Thuật toán SETM 17
3. Thuật toán Apriori 18
3.1. Ý tưởng thuật toán Apriori 18
3.2. Thuật toán Apriori (Pseudo code) 19
4. Thuật toán AprioriTID: 22
4.1. Ý tưởng 22
4.2. Thuật toán AprioriTID (Pseudo code) 22
5. Thuật toán Apriori-Hybrid 24
6. Thuật toán FP-growth 24
KHAI THÁC LUẬT KẾT HỢP TRONG BÀI TOÁN KHÁM VÀ ĐIỀU TRỊ BỆNH
NGOẠI TRÚ TẠI PHÒNG KHÁM Y HỌC CỔ TRUYỀN BỆNH VIỆN BÀ RỊA TỈNH BÀ
RỊA – VŨNG TÀU 29
1. Cài đặt chương trình: 29
2. Về kỹ thuật: 29
3. Giao diện: 29
4. Cơ sở dữ liệu: 30
5. Giới thiệu source code của chương trình: 32
6. Hướng dẫn sử dụng: 33
KẾT LUẬN 35

“Necessity is the mother of invention”. - Plato
2
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
CHƯƠNG 1
TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI MỎ DỮ LIỆU
1. Phát hiện tri thức và khai mỏ dữ liệu
Trong thời đại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ liệu
ngày càng phát triển tạo điều kiện cho các đơn vị thu thập dữ liệu tốt hơn. Đặc
biệt trong lĩnh vực kinh doanh, các doanh nghiệp đã nhận thức được tầm quan
trọng của việc nắm bắt và xử lý thông tin, nhằm giúp các chủ doanh nghiệp
trong việc vạch ra các chiến lược kinh doanh kịp thời mang lại những lợi nhuận
to lớn cho doanh nghiệp của mình. Tất cả lí do đó khiến cho các cơ quan, đơn vị
và các doanh nghiệp đã tạo ra một lượng dữ liệu khổng lồ cỡ Gigabyte thậm chí
là Terabyte cho riêng mình.
Khi lưu trữ các dữ liệu khổng lồ như vậy thì chúng ta thấy rằng chắc chắn
chúng phải chứa những giá trị nhất định nào đó; Tuy nhiên, theo thống kê thì chỉ
có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được
phân tích, số còn lại họ không biết sẽ phải làm gì hoặc có thể làm gì với chúng
nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đó
quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Mặt khác, trong môi trường
cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ
giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính
cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có.
Với những lý do như vậy, các phương pháp quản trị và khai thác CSDL
truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một
khuynh hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai mỏ dữ liệu
(KDD - Knowledge Discovery and Data Mining).
Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và
các ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một
chương trình dưới một dạng nhất định. Chúng ta sử dụng các bit để đo lường các

- Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu
được.
- Trình diễn dữ liệu (Knowledge Presentation): Biểu diễn những tri thức khai
phá được cho người sử dụng.
5. Đưa kết quả vào
thực tiễn
4. Minh họa và đánh
giá tri thức
3. Khai thác dữ liệu–trích
ra các mẫu/mô hình
2. Thu thập và tiền xử
lý dữ liệu
1. Hiểu và xác định
vấn đề
Hình 1: Quá trình khám phá tri thức từ CSDL
4
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
Hình 1 mô tả 5 giai đoạn trong quá trình khám phá tri thức từ cơ sở dữ
liệu. Mặc dù có 5 giai đoạn như trên xong quá trình khám phá tri thức từ cơ sở
dữ liệu là một quá trình tương tác và lặp di lặp lại theo chu trình liên tục kiểu
xoáy trôn ốc, trong đó lần lặp sau hoàn chỉnh hơn lần lặp trước. Ngoài ra, giai
đoạn sau lại dựa trên kết quả thu được của giai đoạn trước theo kiểu thác nước.
Đây là một quá trình biện chứng mang tính chất khoa học của lĩnh vực
phát hiện tri thức và là phương pháp luận trong việc xây dựng các hệ thống phát
hiện tri thức.
2.1. Xác định vấn đề
Đây là một quá trình mang tính định tính với mục đích xác định được lĩnh
vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực tế, các
CSDL được chuyên môn hóa và phân chia theo các lĩnh vực khác nhau như sản
phẩm, kinh doanh, tài chính, quản lý,… Với mỗi tri thức phát hiện được có thể

Khóa luận môn học: Công nghệ tri thức và Ứng dụng
- Giới hạn vùng giá trị: là lỗi thường xảy ra đó là nằm ngoài vùng giới hạn
cho phép. Nghĩa là các thông tin chứa các giá trị không theo một quy tắc
nào đó, những lỗi này khá đặc biệt mà chúng ta rất khó phát hiện. Vì thế nó
ảnh hưởng không nhỏ đến việc đưa quá trình data mining vào bảng dữ liệu,
cho nên để sửa chữa các mâu thuẩn này nếu phần thông tin nào là không
biết thì nó có thể được thay thế bằng giá trị NULL và cứ như vậy chúng ta
tiến hành sửa chữa các mâu thuẫn trong các vùng dữ liệu khác.
c. Làm giàu dữ liệu: Việc thu thập dữ liệu đôi khi không đảm bảo tính đầy
đủ của dữ liệu, một số thông tin quan trọng có thể thiếu hoặc không đầy đủ. Do
đó quá trình làm giàu bao gồm việc tích hợp và chuyển đổi dữ liệu. Các dữ liệu
từ nhiều nguồn khác nhau được tích hợp thành một kho thống nhất. Các khuôn
dạng khác nhau của dữ liệu cũng được quy đổi, tính toán lại để đưa về một kiểu
thống nhất, tiện cho quá trình phân tích.
d. Mã hóa dữ liệu: Mã hóa là chuyển đổi kiểu dữ liệu về những dạng
thuận tiện cho việc tiến hành tìm luật kết hợp ở giai đoạn khám phá tiếp theo.
Chỉ có các thành phần thực thi trong thuật toán tìm luật kết hợp được mã hóa.
Tùy theo từng kiểu dữ liệu mà chúng ta có những cách mã hóa khác nhau, như:
Phân vùng; Chuyển đổi giá trị năm thanh số so với hiện tại, ví dụ:
hoten namsinh tuoi
AN HÙNG VINH 1960 52
AN THỊ CẨM LINH 1958 54
BẠCH NGỌC ON 1939 73
BÀNH THỊ HÒE ANH 1958 54
BÀNH THỊ LIỄU ANH 1948 64
BIỆN THỊ SĨ PHU 1974 38
BÙI CAO TÁC 1928 84
BÙI ĐÌNH NAM 1947 65
BÙI ĐỨC QUẾ 1945 67
BÙI ĐỨC QUY 1950 62

tin có ích từ kho dữ liệu khổng lồ.
Khai phá dữ liệu được áp dụng trong các cơ sở dữ liệu quan hệ, giao dịch,
cơ sở dữ liệu không gian, cũng như các kho dữ liệu phi cấu trúc.
Như vậy, mục đích của khai mỏ dữ liệu là tìm ra các mẫu hoặc mô hình
đang tồn tại trong các CSDL nhưng vẫn còn tiềm ẫn bởi số lượng dữ liệu khổng
lồ.
3.2. Nhiệm vụ của khai mỏ dữ liệu
7
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
- 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:
Một dữ liệu mới thu thập 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.
- Khám phá luật kết hợp. Nhiệm vụ là phát hiện ra những mối quan hệ giống
nhau 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 đó. Khám phá luật kết hợp được hiểu
theo nghĩa: Biết trước các tính chất X, vậy các tính chất Y là những tính
chất nào?
- Lập mô hình dự báo: Phân nhóm dữ liệu vào một hay nhiều lớp dữ liệu đã
xác định trước hoặc 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 hợp khác.
- Phân tích đối tượng ngoài cuộc: Một cơ sở dữ liệu có thể có thể chứa các
đối tượng không tuân theo mô hình dữ liệu.
- Phân tích sự tiến hóa: Thực hiện việc mô tả và mô hình hóa các quy 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.
3.3. Triển khai việc khai mỏ dữ liệu
Nhóm các tác giả Cabena Et Al đề nghị triển khai quá trình khai mỏ dữ
liệu theo 5 bước:
- Bước 1: Xác định rõ mục tiêu thương mại cần khai phá.

thuật, khai mỏ dữ liệu là một quá trình tìm kiếm các mối tương quan giữa các
mẫu ẩn chứa trong hàng chục trường dữ liệu của một CSDL quan hệ cỡ lớn.
Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi
trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như:
- Thương mại, Thông tin sản xuất,
- Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, …
khoa học địa lý: dự báo động đất, … khoa học môi trường: biến đổi khí hậu
toàn cầu và nước biển dâng,
- Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet…
3.5. Các kỹ thuật khai phá dữ liệu
- Kỹ thuật khai mỏ 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 tring 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 mỏ 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)…
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
a) 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.
9
Hình 3: Phân cụm dữ liệu
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
b) Phân lớp 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

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
- 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.
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 …
3.6. Kiến trúc của hệ thống khai mỏ dữ liệu
Khai mỏ dữ liệu là một giai đoạn trong quá trình phát hiện tri thức từ số
lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu, kho dữ liệu hoặc các nơi lưu
trữ khác. Bước này có thể tương tác lẫn nhau giữa người sử dụng hoặc cơ sở tri
thức, những mẫu đáng quan tâm được đưa cho người dùng hoặc lưu trữ như là
tri thức mới trong cơ sở tri thức.(Hình 5)
11
Giao diện người dùng
Giao diện người dùng
Đánh giá mẫu
Đánh giá mẫu
Mô tả khai mỏ dữ liệu
Mô tả khai mỏ dữ liệu
CSDL hay kho dữ liệu phục vụ
CSDL hay kho dữ liệu phục vụ
Cơ sở tri thức
Cơ sở tri thức
Cơ sở dữ liệu

dạng sao cho thuật toán có thể hiểu được.
12
Xác định nhiệm vụ
Dữ liệu trực tiếp
Xác định dữ liệu
liên quan
Thu thập và tiền xử
lý dữ liệu
Thuật toán khai
mỏ dữ liệu
Mẫu
Hình 6: Mô tả quy trình khai mỏ dữ liệu
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
Sau đó chọn thuật toán khai mỏ dữ liệu thích hợp và thực hiện việc khai
mỏ dữ liệu để tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng (luật
kết hợp, cây quyết định …).
Với thuật toán và nhiệm vụ khai mỏ dữ liệu khác nhau thì dạng mẫu chiết
xuất được cũng rất đa dạng.
13
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
CHƯƠNG 2
LUẬT KẾT HỢP TRONG KHAI MỎ DỮ LIỆU
1. Khai phá luật kết hợp
Luật kết hợp được giới thiệu lần đầu tiên vào năm 1993. Luật kết hợp là
một trong những kỹ thuật được nghiên cứu tốt nhất vũng như quan trọng nhất
trong việc khai mỏ dữ liệu. Nó tìm ra những mối liên hệ giữa các trường mô tả
đối tượng trong CSDL và xây dựng thành các luật cụ thể. Luật kết hợp là tri
thức quan trọng nhất tiềm ẩn trong CSDL.
Mục đích của luật kết hợp là rút ra những mối liên quan, những tập mẫu
phổ biến, những cấu trúc kết hợp hay cấu trúc ngẫu nhiên giữ những tập hợp

sup(X)=
{T∈|X⊆T}
14
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
D
Độ hỗ trợ tối thiểu minsup là một giá trị cho trước bởi người sử dụng. Nếu
tập mục X có sup(X) ≥ minsup thì ta nói X là một tập các mục phổ biến. Một tập
phổ biến được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược
lại, những tập không phải tập phổ biến là những tập không đáng quan tâm. Các
phần sau sẽ sử dụng những cụm từ khác như “X có độ hỗ trợ tối thiểu”, hay “X
không có độ hỗ trợ tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa
mãn support(X) ≥ minsup.
→Một khoản mục X được gọi là k-itemset nếu lực lượng của X bằng k,
tức là |X|=k.
Một luật kết hợp có dạng R: X => Y, trong đó X, Y là tập các mục, X, Y
⊆ I và X ∩Y = ∅. X được gọi là tiên đề và Y được gọi là hệ quả của luật.
Luật X => Y tồn tại một độ tin cậy c . Độ tin cậy c được định nghĩa là khả
năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Ta có công thức tính độ tin cậy c
như sau:
conf(X =>Y)= p(Y ⊆ I | X ⊆ I ) =
p(Y⊆T∧X⊆T
)
=
sup(X∪Y)
p(X ⊆T)
sup(X)
Tuy nhiên, không phải bất cứ luật kết hợp nào có mặt trong tập các luật có
thể được sinh ra cũng đều có ý nghĩa trên thực tế. Mà các luật đều phải thoả mãn
một ngưỡng hỗ trợ và tin cậy cụ thể. Do vậy, cho một tập các giao dịch D, bài
toán phát hiện luật kết hợp là sinh ra tất cả các luật kết hợp mà có độ tin cậy

Các tập con của tập phổ biến cũng là tập phổ biến
Nếu mục B là mục phổ biến trên D, nghĩa là support(B) ≥ minsup thì mọi
tập con A của B là tập phổ biến trên D vì support(A) ≥ support(B) > minsup.
2.2.2 Tính chất của luật kết hợp: có 4 tính chất
- 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
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
- 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ả hai 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
- 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
- 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
Vì supp(B) ≥ sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta
nhận được:
conf(B →(L-B))=
sup(L)

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
1. L1 = { các tập mục phổ biến};
2. for (k=2; Luật kết hợpk-1 ≠ ∅ ; k++ ) do begin
3. Ck = ∅;
4. forall các giao dịch t ∈ D do begin
5. Lt = Subset(Lk-1,t); // các tập mục phổ biến thuộc Lk-1 chứa trong giao
dịch t
6. forall các tập mục phổ biến lt ∈ Lt B do begin
7. Ct = tăng thêm một mục có trong giao dịch t;
8. forall các ứng cử viên c ∈ Ct do
9. if (c ∈ Ck) then
add tăng biến đếm của c thêm 1 cho mục tương ứng của Ck
else add c và Ck và tăng biến đếm tương ứng thêm 1;
10. End
11. Lk = { c ∈ Ck | c.count ≥ minsup}
12. End
13. Trả lời = ∪k Lk ;
Thuật toán được áp dụng tỏ ra thành công cho cơ sở dữ liệu của các công
ty bán lẻ hàng hóa và đã tìm ra các luật kết hợp đề cập đến mối quan hệ giữa
hành vi ứng xử mua hàng của khách hàng với 63 gian hàng của công ty, sau khi
nghiên cứu 46.873 giao dịch mua hàng.
2. Thuật toán SETM
Thuật toán do Houtsma đề nghị năm 1995. Thuật toán này cũng sử dụng
kỹ thuật bổ sung dần dần từng phần tử (từ tập hợp 1 phần tử) nhằm tìm kiếm các
tập hợp ứng cử viên. Một cải tiến đáng kể là Thuật toán đề nghị lưu lại cả ID của

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ó
k-itemset được tìm thấy.
- Từ frequent itemsets sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa
mãn 2 tham số min_sup và min_conf)
Các bước thực hiện thuật toán:
- Bước 1. Duyệt (Scan) toàn bộ transaction database để có được support
S của 1-itemset, so sánh S với min_sup, để có được 1-itemset (L
1
)
- Bước 2. Sử dụng L
k-1
nối (join) L
k-1
để sinh ra candidate k-itemset. Loại
bỏ các itemsets không phải là frequent itemsets thu được k-itemset
18
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
- Bước 3. Scan transaction database để có được support của mỗi candidate
k-itemset, so sánh S với min_sup để thu được frequent k –itemset (L
k
)
- Bước 4. Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không
tìm thấy frequent itemsets)
- Bước 5. Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng
của I
- Bước 6. Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu

4) forall transactions t ∈ D do begin
5) C
t
= subset(C
k
, t); // Ứng viên chứa trong t
6) forall candidates c ∈ C
t
do
7) c.count++;
8) end
9) L
k
= {c ∈ C
k
| c.count≥ minsup}
10) end
11) Answer = ∪
k
L
k
;
Ví dụ: Giả sử ta có có sở dữ liệu giao dịch (Transaction Database -TDB) với
min_sup=50%, min_conf =80% như sau:
Database TDB
TID items
1 A,C,D
2 B,C,E
3 A,B,C,E
4 B,E

, 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-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).

4
frequent 1-itemsets sẽ tạo ra nhiều hơn 10
7
(≈10
4
(10
4
-1)/2) 2-
itemsets dự tuyển.
- Một k-itemset cần ít nhất 2
k
-1 itemsets dự tuyển trước đó.
Kiểm tra tập dữ liệu nhiều lần:
- Chi phí lớn khi kích thước các itemsets tăng lên dần.
- Nếu k-itemsets được khám phá thì cần kiểm tra tập dữ liệu k+1 lần
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).
- Đếm itemset động (dynamic itemset counting): Chỉ thêm các itemsets
dự tuyển khi tất cả các tập con của chúng được dự đoán là frequent.
21

k-1
≠ ∅; k++ ) do begin
4) C
k
= apriori-gen(L
k-1
); // Ứng viên mới
5)
kC
= ∅;
6) forall entries t ∈ C
k-1
do begin
7) // Xác đònh candidate itemsets trong C
k
chứa trong giao tác nhận dạng
với t.TID
C
t
= {c ∈ C
k
| (c-c[k]) ∈ t:set-of-itemsets} and (c - c[k_1]) ∈ t.set-of-
itemsets};
8) forall candidates c ∈ C
t
do
9) c.count++;
10) if (C
t
≠ ∅ ) then

1C
và tạo ra
2C
. Với giao tác 100 ta có
1C
={{A} {C}
{D}}. C
t
tại dòng thứ 7 tương ứng mục t này là {{A C}}, vì {A C} là thành viên
của C
2
và cả ({AC}-{A}) và ({AC}-{C} là thành viên của t.set-of-itemsets.
- Gọi hàm apriori_gen với đối số L
2
cho C
3
-
2C
,
3C
được tạo ra từ
2C
và C
3.

- Gọi hàm apriori-gen với đối số L
2
cho C
3.
Lưu ý rằng

ii) extension.
23
Database
TIDItems100
200
300
400A C D
B C E
A B C E
B E
TIDSet-of-Itemsets100
200
300
400{{A},{C},{D}}
{{B},{C},{E}}
{{A},{B},{C},{E}}
{{B},{E}}
L
1
ItemsetSupport{A}
{B}
{C}
{E}2
3
3
3
C
2
ItemsetSupport{A
B}

ItemsetSuppo
rt{B C E}2
TIDSet-of-Itemsets200
300{{B C E}}
{{B C E}}
L
3
ItemsetSupport{
B C E}2
Khóa luận môn học: Công nghệ tri thức và Ứng dụng
- Trường generators của tập candidate itemset c
k
lưu ID của hai tập large
(k-1)-itemset mà hai tập này kết lại để phát sinh c
k.
- Trường extensions của tập itemset c
k
lưu những ID của tất cả các tập
(k+1)- cadidate được phát sinh từ c
k
.
Do đó khi một candidates c
k
được phát sinh bằng các kết l
1
k-1
và l
2
k-1
, ta lưu

T
k
, trường generators chứa các ID của hai tập itemset mà phát sinh ra c
k
. Nếu
những tập itemset này thuộc mẫu tin t.set-of-itemsets, thì ta có thể kết luận rằng
c
k
thuộc giao tác t.ID, và thêm c
k
vào C
t
.
5. Thuật toán Apriori-Hybrid
Thuật toán Apriori-Hybrid được coi như kết hợp giữa Thuật toán Apriori
và thuật toán Apriori-TID.
Trong thuật toán Apriori-Hybrid, được sử dụng khi tổ chức lặp và chuyển
sang Apriori-TID khi đã chắc chắn rằng tập
kC
đã vào bộ nhớ chính.
Thuật toán Apriori-Hybrid được coi là tốt hơn so với Apriori và
AprioriTID.
Nhờ có nhận xét tinh tế là thuật toán Apriori chạy khá nhanh ở những
bước đầu tiên, còn thuật toán Apriori-TID chạy nhanh ở những bước sau,
Agrawal đề nghị phương án lai ghép: không nhất thiết phải chạy tất cả các bước
cùng một thuật toán giống nhau. Những bước đầu tiên, ông cho chạy thuật toán
Apriori, sau đó khi tập các ứng cử viên khá lớn, sắp chứa đầy trong bộ nhớ tính
toán, mới dùng thuật toán Apriori-TID.
6. Thuật toán FP-growth
6.1. Ý tưởng thuật toán

- Mỗi node trên một nhánh tương ứng một item của giao dịch.
+ Các item của một giao dịch được sắp theo giảm dần.
+ Mỗi node kết hợp với support count của item tương ứng.
- Các giao dịch có chung items tạo thành các nhánh có prefix chung.
Thuật toán FP_Tree
Input: cơ sở dữ liệu và ngưỡng độ hỗ trợ minsup
Output: Cây mẫu thường xuyên FP_Tree
Method:
- Bước 1: Duyệt qua cơ sở dữ liệu để đếm số lần xuất hiện của các mục
trong giao tác và xác định mục thường xuyên và độ hỗ trợ của chúng, sắp xếp
các mục thường xuyên giảm dần theo độ hỗ trợ, ta được danh sách các mục
được sắp xếp L.
- Bước 2: Xây dựng FP_Tree. Đầu tiên tạo nút gốc, sau đó với mỗi giao
tác t chọn và sắp xếp các mục thường xuyên theo thứ tự trong danh sách L, thực
hiện thêm vào cây FP_Tree bằng cách gọi hàm insert_tree(p|T), thay đổi trường
count cho phù hợp.
6.2.2. Khám phá frequent itemsets với FP-tree
a) Tạo conditional pattern base cho mỗi node của FP- Tree
- Tích luỹ các prefix paths with frequency của node đó
b) Tạo conditional FP-tree từ mỗi conditional pattern base
-Tích lũy frequency cho mỗi item trong mỗi base
- Xây dựng conditional FP-tree cho frequent items của base đó
c) Khám phá conditional FP-tree và phát triển frequent itemsets một cách
đệ qui
- Nếu conditional FP-tree có một path đơn thì liệt kê tất cả các itemsets.
25