Tiểu luận Công nghệ tri thức Tramg 1/35
A – LÝ THUYẾT
I. TÌM HIỂU TỔNG QUAN VỀ DATA MINING
II. CÁC PHƯƠNG PHÁP MÁY HỌC ỨNG DỤNG TRONG DATA MINING
1. Tìm luật kết hợp (Mining Association Rules)
2. Phân lớp (Classification)
3. Gom nhóm (Clustering)
III. THUẬT TOÁN TÌM LUẬT KẾT HỢP ỨNG DỤNG TRONG DATA MINING
1. Giới thiệu – các định nghĩa liên quan
Các vấn đề về luật kết hợp
Support
Confidence
2. Tổng quan về các thuật toán tìm luật kết hợp
2.1 Thuật toán cơ sở
2.2 Các thuật toán tuần tự (Sequential)
Thuật toán AIS
Thuật toán SETM
Thuật toán Apriori
Thuật toán Apriori-TID
Thuật toán Apriori-Hybrid
Một số thuật toán khác:
 Off-line Candidate Determination (OCD)
 Partitioning
 Sampling
 Dynamic Itemset Counting (Brin1997a)
 CARMA (Continuous Association Rule Mining Algorithm)
2.2 Các thuật toán song song và phân tán
Các thuật toán song song dữ liệu (Data Parallelism)
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 2/35
 CD

được ý kiến góp ý và động viên của Thầy cũng như tất cả các Anh/Chị và các bạn để
tiểu luận được hoàn thiện hơn nữa.
Xin chân thành cảm ơn!

Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 4/35
A – LÝ THUYẾT
I. TÌM HIỂU TỔNG QUAN VỀ DATA MINING
1. Data Mining là gì?
Data Mining (khai phá dữ liệu) là việc sử dụng những công cụ phân tích dữ liệu phức
tạp để tìm ra những tri thức chưa được biết đến, những mô hình thích hợp, những mối
quan hệ trong những cơ sở dữ liệu lớn. Về bản chất, khai phá dữ liệu liên quan đến
việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính
quy (regularities) trong tập dữ liệu. Vì vậy, Data Mining không những tập hợp, quản lý
dữ liệu mà còn phân tích, tiên đoán dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức
trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ quá
trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là
một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất
ra các mẫu (pattern) (hay các mô hình) từ dữ liệu.
Data Mining có thể thao tác trên dữ liệu ở dạng định lượng, có cấu trúc hoặc đa
phương tiện. Những ứng dụng Data Mining có thể sử dụng các phương pháp khác
nhau để khảo sát dữ liệu như:
- Mô hình kết hợp: một sự kiện này được kết hợp với một sự kiện khác, ví dụ:
mua bút và mua giấy.
- Mô hình phân tích đường đi: một sự kiện này dẫn đến một sự kiện khác, ví dụ:
đứa trẻ ra đời dẫn đến việc mua tã lót.
- Mô hình phân lớp: xác định những mô hình mới.
- Mô hình gom nhóm: tìm kiếm và ghi lại thành nhóm những sự kiện chưa khám
phá trước đây, như vị trí địa lý, mức độ ưu tiên.

người già, giúp đỡ bộ tư pháp đưa ra những mô hình tội phạm và phân phối nguồn lực
thích hợp, trợ giúp tiên đoán sự thay đổi nhân khẩu và ước lượng tốt hơn về nhu cầu
ngân sách,
Gần đây, Data Mining được xem là công cụ quan trọng trong vấn đề an ninh quốc gia.
Một số người đề nghị rằng Data Mining nên được sử dụng như là phương tiện xác
định những hoạt động khủng bố như chuyển tiền và thông tin, và xác định định, đánh
dấu những người khủng bố qua hồ sơ du lịch, di cư. Hai ứng dụng Data Mining đầu
tiên gây được sự chú ý mạnh mẽ là dự án nhận biết thông tin khủng bố (Terrorism
Information Awareness-TIA) và hệ quan sát hành khách trước màn hình được máy
tính trợ giúp (Computer Assisted-Passenger Prescreening System II-CAPPS II). Cả 2
hệ thống này ra đời sau sự kiện 11-09-2001, ngày nước Mỹ bị bọn khủng bố tấn công,
nhằm đảm bảo an toàn cho các chuyến bay trước nguy cơ khủng bố. Hiện tại, dự án
TIA không được tiếp tục và CAPPS II được thay thế bởi hệ thống Chuyến bay an toàn
(Security Flight).
4. Một số vấn đề về Data Mining
a. Chất lượng dữ liệu
Chất lượng dữ liệu là một thách thức lớn đối với Data Mining. Chất lượng dữ liệu
được biết như là độ chính xác và toàn vẹn dữ liệu. Chất lượng dữ liệu cũng có thể bị
ảnh hưởng bởi cấu trúc và sự nhất quán của dữ liệu đang được phân tích.
Sự hiện diện của những bản ghi trùng nhau, sự thiếu dữ liệu chuẩn, dữ liệu được cập
nhật cùng một lúc và lỗi do con người có thể tác động đáng kể đến hiệu quả của những
kỹ thuật Data Mining, cụ thể là sự khác nhau tinh vi có thể tồn tại trên dữ liệu.
Để cải tiến chất lượng dữ liệu, đôi khi phải tinh chế dữ liệu như loại bỏ các bản ghi
trùng nhau, hình thức hóa các giá trị biểu diễn trong cơ sở dữ liệu (ví dụ: “no” được
thay thế thành 0 hay N ), tính toán những điểm dữ liệu bị thiếu, loại bỏ những trường
dữ liệu không cần thiết,
b. Tương tác giữa các thành phần
Đó là sự tương tác giữa các thành phần cơ sở dữ liệu và phần mềm Data Mining. Sự
tương tác ám chỉ khả năng của một hệ thống máy tính và/hoặc dữ liệu để làm việc với
những hệ thống khác, hoặc dữ liệu sử dụng những tiến trình hoặc tiêu chuẩn chung.

hiện đang áp dụng trong nhiều mặt của khoa học thống kê, ghi nhận mẫu, lý thuết
quyết định, máy học, mạng nơ-ron,…
Ba bước xử lý chính của phân lớp:
» Bước 1: xây dựng một mô hình sử dụng tập dữ liệu đã biết, được gọi là dữ
liệu tập huấn (Training data) hay các mẫu (Sample).
» Bước 2: đánh giá độ chính xác ước đoán của mô hình sử dụng dữ liệu thử
(test data).
» Bước 3: sử dụng mô hình để dự đoán dữ liệu chưa biết (nếu độ chính xác đã
được chấp nhận).
Chuẩn bị dữ liệu để phân lớp:
» Làm sạch dữ liệu: xóa nhiễu và các giá trị thất lạc.
» Kiểm tra không thích hợp: loại bỏ các thuộc tính dư thừa hoặc không thích
hợp.
» Chuyển đổi dữ liệu: dữ liệu được tổng quát hóa lên mức khái niệm cao hơn
hoặc được chuẩn hóa.
3. Gom nhóm (Clustering)
Gom nhóm là nhóm tập các đối tượng vào những nhóm tương đồng nhau,đích nhắm là
lớp có tính tương tự cao ở ngoài lớp và có tính tương tự thấp ở trong lớp. Ví dụ khám
phá các nhóm khách hàng khác biệt, phân loại gen theo chức năng tương tự nhau, nhận
diện nhóm người mua bảo hiểm xe ô-tô có tỉ lệ yêu cầu trung bình cao,
Gom nhóm khác phân lớp (Classification) ở chỗ nó không xác định trước các lớp và
cũng không đánh nhãn lớp cho tập mẫu tập huấn.
Phân lớp là phương pháp học theo mẫu, học có giáo viên còn gom nhóm là học theo sự
quan sát, không có giáo viên.
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 8/35
III. THUẬT TOÁN TÌM LUẬT KẾT HỢP ỨNG DỤNG TRONG DATA MINING
III.1. Giới thiệu – các định nghĩa liên quan
Cho là tập của các phần tử.
Một tập X = {i

support(X,D) := | cover(X,D) |
Hay nói cách khác, độ hỗ trợ của X là tỷ số các giao tác T hỗ trợ tập phần tử X trong
cơ sở dữ liệu D:
support(X) = |{T
∈
D | X
⊆
T}| / |D|.
Trong [Agrawal1993] [Cheung1996c], support(s) của một luật kết hợp là tỉ số (tính
theo phần trăm) của các bản ghi có chứa X ∪ Y trên tổng số bản ghi của CSDL.
Như vậy nếu ta nói, độ hỗ trợ của một luật là 5% thì có nghĩa là có 5% trên tổng số
bản ghi có chứa X ∪ Y.
Độ hỗ trợ của luật X
⇒
Y được định nghĩa như sau: support(X
⇒
Y) = support(X
∪
Y).
Tính phổ biến của tập X trong D là khả năng xuất hiện của X trong một giao tác T ∈ D:
frequency(X,D) := P(X) = support(X,D) / |D|
Một tập phần tử được gọi là phổ biến nếu độ hỗ trợ của nó không nhỏ hơn trị tuyệt đối
ngưỡng hỗ trợ tối thiểu (minimal support threshold) σ
abs
với 0 ≤ σ
abs
≤ |D|.
Khi làm việc với các tập phổ biến, thay vì sử dụng support của chúng ta dùng một khái
niệm liên quan là ngưỡng phổ biến tối thiểu (minimal frequency threshold) σ
rel

Tiên đề:
Cho CSDL giao tác D trên , X,Y
⊆
là hai itemset, khi đó:
X
⊆
Y
⇒
support(Y) ≤ support(X)
Chứng minh:
Điều này có được ngay từ cover(Y)
⊆
cover(X). (ĐPCM) 
III.2. Tổng quan về các thuật toán tìm luật kết hợp
1. Thuật toán cơ sở
Tìm các luật kết hợp từ một cơ sở dữ liệu bao gồm quá trình tìm tất cả các luật phù
hợp với ngưỡng support và confidence do người dùng ấn định. Vấn đề này có thể được
phân thành 2 vấn đề nhỏ hơn [Agrawal1994] như được trình bày trong thuật toán 1.
Thuật toán 1. Thuật toán cơ sở.
Input
I, D, s, α
Output
Các luật kết hợp thoả s và α
Thuật toán

Tìm mọi itemset xuất hiện có tần số lớn hơn hoặc
bằng support s do người dùng ấn định.

Phát sinh các luật thoả mãn độ tin cậy confidence α.
Bước thứ nhất của thuật toán sẽ tìm các mục dữ liệu thường xuyên xuất hiện trong cơ

T3 Bơ
T4 Bánh mì, Bơ
Bảng 2: minsupp cho các tập phần tử của bảng 1
Ghi chú: Large: phổ biến
Small: không phổ biến
Mục dữ liệu Support, s (%) Large/Small
Bánh mì 50 Large
Bơ 100 Large
Trứng 50 Large
Sữa 25 Small
Bánh mì, Bơ 50 Large
Bánh mì, Trứng 25 Small
Bánh mì, Sữa 0 Small
Bơ, Trứng 50 Large
Bơ, Sữa 25 Small
Sữa, Trứng 25 Small
Bánh mì, Bơ, Trứng 25 Small
Bánh mì, Bơ, Sữa 0 Small
Bánh mì, Trứng, Sữa 0 Small
Bơ, Trứng, Sữa 25 Small
Bánh mì, Bơ, Trứng, Sữa 0 Small
Bảng 3: các luật thoả minconf ≥ 60%
Luật Độ tin cậy (%) Chọn luật
Bánh mì
→
Bơ
100 Có
Bơ
→
Bánh mì

x) nếu tỷ lệ tần số xuất hiện của l với tần số cuất
hiện của x lớn hơn hoặc bằng ngưỡng tin cậy.
Ví dụ, giả sử ta cần xác định luật (Bánh mì
→
Bơ) có được chọn trong ví dụ 1. Ở đây,
l={Bánh mì, Bơ} và x={Bánh mì}, như vậy (l-x)={Bơ}. Khi đó support(Bánh mì, Bơ)
với support(Bánh mì) là 100%, lớn hơn ngưỡng tin cậy đã cho, vậy luật này được
chọn. Để làm rõ thêm ta xét luật thứ 3 (Bơ
→
Trứng), trong đó x = {Bơ} và (l-x) =
{Trứng}. Tỷ lệ support(Bơ, Trứng) và support(Bơ) là 50%, nhỏ hơn ngưỡng tin cậy tối
thiểu là 60%. Như vậy ta nói không đủ cơ sở để kết luận rằng luật (Bơ
→
Trứng) đạt
độ tin cậy 60%.
Quá trình tìm các luật kết hợp trong các cơ sở dữ liệu cực lớn là rất tốn kém và đạt
hiệu suất thấp. Vì vậy hầu hết các cải tiến sau này đều theo hướng tìm những thuật
toán hiệu quả hơn cho bước thứ nhất [Algrawal1994] [Cheung1996c]
[Klemettien1994]. Phần tiếp theo sẽ trình bày các thuật toán này.
2. Các thuật toán tuần tự (Sequential Algorithm)
Phần này sẽ trình bày một cách tổng quát về các thuật toán đã có để tìm luật kết hợp.
Hầu hết các thuật toán được dùng để nhận dạng các tập phổ biến được phân thành 2
lớp: tuần tự và song song. Trong hầu hết các trường hợp, các thuật toán này giả thiết
rằng các tập phần tử được nhận dạng và sắp xếp theo thứ tự đồ thị lexico
(lexicographic – đồ thị dựa trên tên của mục dữ liệu). Kiểu sắp xếp này cung cấp một
cách quản lý logic mà theo đó các tập phần tử có thể được phát sinh và thống kê. Đây
là hướng tiếp cận tiêu chuẩn với các thuật toán tuần tự. On the other hand, các thuật
toán song song tập trung vào phương pháp sao cho xử lý song song tác vụ khi tìm
kiếm các tập phổ biến. Sau đây chúng ta sẽ thảo luận về các thuật toán loại này.
2.1 Thuật toán AIS

mục dữ liệu đều xuất hiện trong mỗi giao tác thì sẽ có 2
m
trường hợp cần xét. Như
vậy,trong trường hợp xấu nhất, độ phức tạp của thuật toán này là hàm mũ theo m.
2.2 Thuật toán SETM
Thuật toán SETM được đề xuất trong [Houtsma1995] và thích hợp cho SQL nhằm tính
toán các tập phổ biến [Srikant1996]. Trong thuật toán này, mỗi thành phần của tập phổ
biến,
L
k
, đều có khuôn dạng <TID, itemset> trong đó TID là định danh duy nhất của
giao tác. Tương tự, mỗi thành phần của tập các tập tổ hợp,
C
k
, cũng có dạng <TID,
itemset>.
Tương tự như AIS, SETM tiến hành duyệt nhiều lần trên cơ sở dữ liệu. Trong lần
duyệt đầu tiên, nó đến support của các mục dữ liệu riêng lẻ và xác định xem chúng có
thoả ngưỡng đã đặt hay không. Sau đó SETM sẽ phát sinh các tổ hợp bằng cách mở
rộng tập phổ biến của lần duyệt trước. Thêm vào đo, SETM sẽ ghi nhớ các TID của
các giao tác đang phát sinh cùng các tập tổ hợp. Trong quá trình phát sinh tổ hợp,
SETM lưu một bản sao của tập phổ biến cùng với TID quá trình phát sinh giao tác theo
dạng tuần tự (sequential manner). Sau này, các tổ hợp sẽ được lưu dưới dạng các tập
phần tử và các tập không thoả ngưỡng sẽ bị xoá bằng hàm kết hợp (aggregation
function). Nếu cơ sở dữ liệu được sắp xếp theo TID, tập phổ biến chứa trong một giao
tác ở bước kế tiếp sẽ được thu nhận bằng cách sắp xếp
L
k
theo TID. Theo cách này,
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy

tổ hợp để thống kê thoả ngưỡng hay không. Như đã trình bày, cả trong AIS và SETM,
các tập phần tử chung giữa tập phổ biến của lần duyệt trước và các phần tử của giao
tác được xác định. Các tập chung này được mở rộng với các phần tử riêng biệt trong
giao tác để tạo các tổ hợp. Tuy nhiên, các phần tử riêng biệt này có thể là không phổ
biến. Ta đã biết rằng sự kết hợp của tập phổ biến và tập không phổ biến có thể lại tạo
ra tập không phổ biến nên kỹ thuật này phát sinh quá nhiều tổ hợp có thể không thoả
ngưỡng. Thuật toán Apriori tạo các tổ hợp bằng cách kết nối các tập phổ biến của lần
duyệt trước và xoá các tập con không thoả trong lần duyệt trước mà không xét đến các
giao tác trong CSDL. Bằng cách chỉ xét đến tập phổ biến của lần duyệt trước, số lượng
tổ hợp giảm đi dáng kể.
2.4 Thuật toán Apriori-TID
Apriori quét dữ liệu đầu vào cho mỗi lần duyệt nhằm thống kê support nhưng việc
quét dữ liệu đầu vào này không cần thiết phải thực hiện ở tất cả các lần duyệt. Dựa vào
điều này, [Agrawal1994] đề xuất thuật toán khác gọi là Apriori-TID. Tương tự như
Apriori, Apriori sử dụng hàm tạo tổ hợp của Apriori để xác định tập tổ hợp phần tử
trước mỗi lần duyệt. Sự khác biệt chính so với Apriori là thuật toán này không dùng
CSDL để thống kê support sau lần duyệt đầu tiên. Đúng hơn là nó dùng một bảng mã
của tập tổ hợp các phần tử, ký hiệu là
C
k
, đã dùng trong lần duyệt trước. Như trong
SETM, mỗi phần tử trong
C
k
có dạng <TID, X
k
> với X
k
là khả năng hiện diện của tập
k phần tử trong giao tác có định danh TID. Tại lần duyệt đầu tiên,

lại được lưu theo cấu trúc tuần tự. Tại lần duyệt thứ k,
Apriori-TID cần có không gian bộ nhớ dành cho L
k-1
và C
k
trong quá trình tạo tổ hợp.
Không gian bộ nhớ là cần thiết cho C
k-1
, C
k
,
C
k
và
C
k -1
ở tại pha thống kê. Tại thời
điểm phát sinh tổ hợp, phân nửa bộ đệm được lấp đầy bằng các tổ hợp và điều này cho
phép các phần của C
k
và C
k-1
được lưu trong bộ nhớ suốt trong pha tính toán. Nếu bộ
nhớ không còn đủ để lưu trữ L
k
, thuật toán khuyến cáo nên sắp xếp L
k
ở thiết bị lưu trữ
ngoài.
Apriori-TID sử dụng

trong tất cả các lần duyệt trên dữ liệu. Như đã được đề cập trong [Agrawal1994],
Apriori đạt hiệu suất tốt hơn trong những lần duyệt đầu tiên, và Apriori-TID thực hiện
tốt hơn Apriori ở những lần duyệt sau. Dựa trên những thí nghiệm quan sát được, kỹ
thuật Apriori-Hybrid đã được phát triển nhằm sử dụng Apriori ở những lần duyệt khởi
động và chuyển sang Apriori-TID một khi cho rằng tập
C
k
ở cuối lần duyệt sẽ lấp vừa
bộ nhớ. Bởi vậy, sự tính toán
C
k
khi nào đạt được trạng thái trên là cần thiết. Mặt
khác, việc chuyển từ Apriori sang Apriori-TID cũng phải mất một lượng chí phí nhất
định. Hiệu năng của kỹ thuật này có thể đánh giá được bằng các thí nghiệm trên các
tập dữ liệu lớn. Thuật toán này là tốt hơn Apriori ngoại trừ trường hợp việc chuyển
trạng thái (từ thuật toán này sang thuật toán kia) xảy ra tại thời điểm cuối cùng của
mỗi lần duyệt [Srikant1996b].
2.6 Một số thuật toán khác
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 15/35
 Off-line Candidate Determination (OCD)
Kỹ thuật này được đề xuất trong [Mannila1994] dựa trên ý tưởng là các mẫu không
phổ biến thường rất tốt để tìm các tập phổ biến. Kỹ thuật OCD sử dụng kết quả phân
tích tổ hợp các thông tin nhận được từ lần duyệt trước nhằm loại ra các tập không cần
thiết. Nếu một tập Y
⊆
l là không phổ biến, có ít nhất (1-s) giao tác phải được duyệt
với s là ngưỡng support. Bởi vậy khi s đủ nhỏ, gần như toàn bộ quan hệ đưa vào được
đọc. Rõ ràng là đối với các CSDL rất lớn, điều này rất quan trọng để có thể tiến hành
duyệt CSDL ít hơn.

L
3
thì X gồm có






3
2
hay 3 tập
từ L
2
. Tương tự, mỗi mục của L
4
gồm 4 tập của L
3
và cứ thế tiếp tục.
Ví dụ, với L
2
={Táo, Chuối}, {Chuối, Cải bắp}, {Táo, Cải bắp}, {Táo, Trứng}, {Chuối,
Trứng}, {Táo, Kem}, {Cải bắp, Sirô}} ta kết luận rằng {Táo, Chuối, Cải bắp} và {Táo,
Chuối, Trứng} chỉ có thể là các thành phần thuộc L
3
. Bởi vì chúng là các tập có kích
thước 3 của tất cả các tập con có kích thước 2 trong L
2
. L
4

= {Y
∪
Y’ với Y, Y’
∈
L
k
và |Y
∪
Y’|=k+1} (2)
Như vậy C
k+1

∈
C’
k+1
và C
k+1
có thể được tính bằng cách kiểm tra mỗi một tập trong
C’
k+1
mà các điều kiện định nghĩa C
k+1
thoả mãn.
Hướng đi thứ hai là xây dựng hợp của các tập từ L
k
và L
1
như trong (3)
C’’
k+1

với e>1 trực tiếp từ L
k

Độ phức tạp thời gian tính C
k+1
từ C’
k+1
là O(k|L
k
|
3
). Nói cách khác, thời gian tính C
k+1
từ C’’
k+1
là tuyến tính theo kích thước của cơ sở dữ liệu (n) và hàm mũ theo kích thước
của tập phổ biến lớn nhất. Bởi vậy thuật toán có thể rất chậm với giá trị n rất lớn. Tập
phổ biến có thể được tính xấp xỉ bằng cách phân tích các mẫu nhỏ hơn của một CSDL
lớn [Lee1998; Mannila1994]. Lý thuyết phân tích này đã được [Mannila1994] trình
bày và chứng tỏ rằng các mẫu nhỏ này rất tốt để tìm các tập phổ biến. Theo
[Mannila1994], thậm chí khi ấn định giá trị thấp cho support, một cơ sở dữ liệu mẫu
gồm 3000 dòng vẫn có thể tìm xấp xỉ rất tốt các tập thỏ ngưỡng.
Hiệu suất của thuật toán này đã được đánh giá trong [Mannila1994] bằng cách sử dụng
hai tập dữ liệu. Tập dữ liệu thứ nhất gồm dữ liệu về 4734 sinh viên, tập thứ hai là cơ
sở dữ liệu quản lý lỗi hệ thống của công ty với 30 000 bản ghi. Thực nghiệm đã chỉ ra
rằng thời gian thực hiện OCD chuẩn hơn 10%-20% so với AIS. Điểm tiện lợi mà OCD
mang lại là khả năng ấn định ngưỡng support thấp [Mannila1994]. Các tổ hợp được
phát sinh trong AIS là cao hơn đáng kể so với OCD. AIS có thể tạo ra các tổ hợp trùng
lặp trong khi duyệt, còn OCD phát sinh bất kỳ tổ hợp nào cũng chỉ một lần và kiểm tra
nếu các tập con của nó là phổ biến hay không trước khi đánh giá trong cơ sở dữ liệu.

1
và D
2

để tìm các Local
Large Itemset.
T1 = Bánh mỳ, Bơ, Trứng.
T2 = Bơ, Trứng, Sữa.
T3 = Bơ.
T4 = Bánh mỳ, Bơ.
L
1
={{Bánh mỳ}.{Bơ},{Trứng}.{Bánh mỳ, Bơ},
{Bánh mỳ, Trứng},{Bơ, Trứng},{Bánh mỳ, Bơ,
Trứng}, {Sữa},{Bơ, Sữa}, {Trứng, Sữa},{Bơ,
Trứng, Sữa}}
L
2
={{Bơ}, {Bánh mỳ}, {Bơ}, {Bánh mỳ, Bơ}}
C ={{Bánh mỳ}.{Bơ},{Trứng}.
{Bánh mỳ, Bơ},
{Bánh mỳ, Trứng},{Bơ, Trứng},
{Bánh mỳ, Bơ, Trứng}, {Sữa},{Bơ,
Sữa}, {Trứng, Sữa},{Bơ, Trứng,
Sữa}}
L ={{Bánh mỳ}, {Bơ},{Trứng},
{Bánh mỳ, Bơ},{Bơ, Trứng}}
Duyệt D để thống
kê support
Hình 1: Tìm các tập phổ biến dùng thuật toán PARTITION

(PL)
∪
PL. Phủ định biên của tập các phần tử PL
là tập tối thiểu của tập các phần tử không chứa trong PL nhưng mọi tập con của chúng
lại thuộc PL. Hàm phủ định biên là sự tổng quát hoá của hàm apriori_gen trong
Apriori. Khi mọi tập phần tử trong PL có cùng kích thước, BD
¯
(PL)
=Apriori_gen(PL). Sự khác biệt ở đây là phủ định biên có thể được áp dụng cho các
tập phần tử có kích thước khác nhau, trong khi hàm apriori_gen () chỉ áp dụng khi kích
thước tập phần tử là một.
Sau khi các tổ hợp được phát sinh, toàn bộ CSDL được quét một lần để xác định số
lượng các tổ hợp. Nếu tất cả các tập phổ biến đều nằm trong PL, nghĩa là không có tập
phần tử nào trong BD
¯
(PL) trở thành phổ biến, thì mọi tập phổ biến đã được tìm thấy
và thuật toán dừng. Điều này được đảm bảo bởi vì BD
¯
(PL)
∪
PL thực tế chứa mọi tổ
hợp các tập phần tử của Apriori nếu PL bao hàm tất cả tập các phần tử L, nghĩa là L
⊆
PL.
 Dynamic Itemset Counting (Brin1997a)
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 18/35
DIC sẽ phát sinh và thống kê các tập phần tử trước, như vậy số lần duyệt CSDL sẽ
giảm xuống. DIC xem CSDL là các khoảng phân biệt (interval) của các giao tác, và
các interval này được duyệt lần lượt. Khi duyệt interval đầu tiên, các tập có 1 phần tử

hay không. Trong mô hình Data Parallelism, mỗi nút (note) đếm cùng một số lượng
tập tổ hợp; trong mô hình Task Parallelism, một tập tổ hợp được phân chia và phân bố
xử lý chéo, và mỗi nút sẽ đếm một tập khác nhau của các tổ hợp. Về lý thuyết, CSDL
có thể được phân chia theo mô hình hay không nhưng để đạt được hiệu quả hơn trong
thao tác I/O, trong thực tiễn người ta thường giả thiết rằng CSDL bị phân chia và phân
bố xử lý chéo.
Trong mô hình Data Parallelism, các tổ hợp bị trùng lặp trên mọi bộ xử lý và CSDL
được phân bổ xử lý chéo. Mỗi quá trình xử lý chịu trách nhiệm tính số hỗ trợ cục bộ
(local support count) của mọi tổ hợp, đây là các support count của phần chia tương
ứng. Tiếp đó mọi quá trình xử lý tính số hỗ trợ toàn cục (global support count) của các
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 19/35
tổ hợp (là tổng các support count của các tổ hợp trên toàn CSDL) bằng cách trao đổi
các local support count. Rồi sau đó, các tập phổ biến được tính toán bởi mỗi bộ xử lý
một cách độc lập. Mô hình Data Parallelism sử dụng dữ liệu trong bảng 1 được cung
cấp trong [hình 2]: bốn giao tác được phân phối qua ba bộ xử lý với bộ thứ ba có hai
giao tác T3 và T4, bộ 1 có T1 và bộ 2 có T2. Ba tổ hợp trong lần duyệt thứ hai bị lặp
lại trên mỗi bộ xử lý. Các local support count có được sau khi duyệt các CSDL cục bộ.
Trong mô hình Task Parallelism, tập tổ hợp được phân chia và phân bố xử lý chéo như
trong CSDL. Mỗi bộ xử lý chịu trách nhiệm giữ các global support count của chỉ một
tập con của các tổ hợp. Hướng tiếp cận này yêu cầu phải có hai vòng giao tiếp tại mỗi
lần lặp: vòng thứ nhất, mỗi bộ xử lý gửi phần chia dữ liệu của nó cho các bộ xử lý
khác; ở vòng thứ hai, mỗi bộ xử lý phát các tập phổ biến được tìm thấy đến mọi bộ xử
lý khác để tính toán các tổ hợp cho lần lặp kế tiếp. Với dữ liệu trong bảng 1, mô hình
này được diễn tả như sau: bốn giao tác vẫn được phân chia như mô hình Data
Paralleism. Ba tập tôe hợp được phân bố xử lý chéo với mỗi bộ xử lý sẽ có một tổ hợp.
Sau khi quét CSDL cục bộ và các phân khu CSDL xuất phát từ các bộ xử lý khác,
global count của mỗi tổ hợp được tìm thấy.
3.1 Các thuật toán song song dữ liệu (Data Parallelism)
Các thuật toán xét đến là CD [Agrawal1996], PDM [Park1995], DMA [Cheung1996]

D
2
C
2
Count
Bánh mỳ, Bơ1Bánh mỳ,
Trứng0Bơ, Trứng0
T3
T4
Processor 3
D
3
C
2
Count
Global Redution
Hình 2: Mô hình Data Parallelism
Tiểu luận Công nghệ tri thức Tramg 20/35
 Bước 2: mỗi bộ xử lý trao đổi các local support count của mọi tổ hợp để lấy
được global support count của tất cả các tổ hợp.
 Bước 3: tập phổ biến L
k
được nhận dạng và các tổ hợp kích thước (k+1)
phần tử được tạo bằng cách áp dụng thủ tục Apriori_gen() với L
k
trên mỗi bộ xử
lý một cách độc lập.
CD sẽ lặp lại bước 1 đến 3 cho đến khi không tìm thấy thêm tổ hợp nào nữa.
 PDM [Park1995a]
PDM (Parallel Data Mining) là một sửa đổi của thuật toán CD sử dụng kỹ thuật băm

Processor 2
D
2
C
2
2
Count
Bơ, Trứng
2
T3
T4
Processor 3
D
3
C
2
3
Count
Itemset broadcast
Database broadcast
Hình 3: Mô hình Task Parallelism
Tiểu luận Công nghệ tri thức Tramg 21/35
phần chia vừa phổ biến trên toàn bộ CSDL) của một tập phần tử rồi sau đó tạo các tổ
hợp từ các tập phần tử heavy trên.
Ví dụ, giả sử A và B là hai mục dữ liệu heavy trên bộ xử lý 1 và 2 tách biệt nhau.
Nghĩa là, A phổ biến cục bộ và toàn cục chỉ trên bộ xử lý 1, B phổ biến trên bộ xử lý
2. DMA sẽ không tạo AB như một tổ hợp 2 phần tử trong khi thuật toán Apriori sẽ tạo
AB như các local count trên mỗi bộ xử lý. Để giao tiếp, thay vì phân phát các local
count của mọi tổ hợp như trong thuật toán CD, DMA chỉ gửi các local count đến một
vị trí, vì vậy sẽ làm giảm lượng giao tiếp từ O(p

 IDD (Intelligent Data Distribution)
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 22/35
IDD là một thuật toán cải tiến từ DD [Han1997]: phân chia các tổ hợp xử lý chéo dựa
trên phần tử đầu tiên của các tổ hợp đó. Điều này có nghĩa là các tổ hợp có cùng phần
tử đầu tiên sẽ được phân chia vào cùng một phân vùng. Bởi vậy mỗi một bộ xử lý chỉ
cần kiểm tra các tập con có phần tử đầu tiên tương ứng đúng với chúng. Điều này làm
giảm thiểu sự dư thừa tính toán trong DD: thay vì mỗi bộ xử lý cần phải kiểm tra tất cả
các tập con của mỗi giao tác thì chỉ cần tiến hành kiểm tra như trên.
Để sự phân tán của các tổ hợp cân bằng, thuật toán sử dụng kỹ thuật nén nhị phân
(bin-packing technique) nhằm phân phối các tổ hợp. Đầu tiên, IDD tính số tổ hợp bắt
đầu bằng một phần tử đặc biệt, sau đó sử dụng thuật toán nén nhị phân để chỉ định các
phần tử cho các vùng tổ hợp sao cho số lượng các tổ hợp là như nhau.
Thuật toán này cũng sử dụng kiến trúc vòng để làm giảm tràn giao tiếp, tức là nó dùng
giao tiếp điểm-điểm không đồng bộ giữa các phần tử cạnh nhau trong vòng thay cho
việc loan truyền giữa các phần tử.
 HPA (Hash-based Parallel mining of Association rules)
HPA sử dụng kỹ thuật băm để phân phối các tổ hợp vào các bộ xử lý khác nhau
[Shintani1996], nghĩa là mỗi bộ xử lý sử dụng cùng một hàm băm (hash function) để
tính toán các tổ hợp được phân bố trên nó. Trong quá trình thống kê, thuật toán di
chuyển tập con các phần tử của các giao tác (thay cho việc phải dịch chuyển các phân
vùng dữ liệu) đến bộ xử lý đích của chúng bằng cùng kỹ thuật băm. Vì vậy, thay vì
phải đến n bộ xử lý, một tập mục dữ liệu của một giao tác chỉ đến một bộ xử lý mà
thôi.
HPA được cải tiến hơn nữa bằng cách dùng kỹ thuật skew handling [Shintani1996].
Đây là kỹ thuật sao lại một vài tổ hợp nếu có đủ bộ nhớ trên mỗi bộ xử lý, vì vậy tải
trọng làm việc của mỗi bộ xử lý được cân bằng hơn.
 PAR (Parallel Association Rules)
PAR (Zaki1997] gồm có tập các thuật toán sử dụng việc phân chia và thống kê tổ hợp
khác nhau. Tất cả đều giả sử rằng CSDL phân chia dọc (liệt kê tid cho mỗi phần tử -

toán phân chia tổ hợp, nên thuật toán này là một kiểu lai giữa hai mô hình trên.
 SH
Trong SH [Harada1998], các tổ hợp không được phát sinh từ các tập phổ biến trước
đó, điều này dường như khác với thuật toán tuần tự Apriori.
Thay vì các tổ hợp được tạo độc lập bởi mỗi bộ xử lý trong suốt quá trình duyệt phân
vùng CSDL, tại bước lặp k, mỗi bộ xử lý phát sinh và thống kê các tập k phần tử từ
các giao tác có trong phân vùng dữ liệu của chúng. Chỉ mọi tập k phần tử của các tập
con (k-1) phần tử mà phổ biến toàn cục là được phát sinh. Tại điểm cuối mỗi bước lặp,
mọi bộ xử lý trao đổi các tập k phần tử và các local count của chúng, nhận global
count của tất cả các tập k phần tử.Tập k phần tử phổ biến được xác định và ảnh
(bitmap) của các tập phổ biến cũng được lập trên mỗi bộ xử lý.
Trong trường hợp việc thống kê không được thực hiện cân bằng, các giao tác được
chuyển từ các bộ xử lý quá tải sang các bộ xử lý khác rảnh hơn. Trường hợp không đủ
bộ nhớ, các tập k phần tử hiện tại sẽ được lưu trữ và đợi trên đĩa, và các tổ hợp k phần
tử mới được phát sinh và thống kê cho đến hết phân vùng CSDL. Tại thời điểm cuối
của mỗi bước lặp, các local count của mọi tập k phần tử được kết hợp và trao đổi với
các bộ xử lý khác để nhận được các global count.
SH có vẻ như dựa trên thuật toán khác với Apriori nhưng lại rất tương đồng với thuật
toán này. Đầu tiên, nó cũng lặp lại như trong Apriori, nghĩa là chỉ tại điểm cuối của
bước lặp thì sự gia tăng các tổ hợp mới (có kích thước mới) mới được phát sinh. Điểm
khác so với Apriori là SH tạo các tổ hợp trong quá trình lặp còn Apriori tạo tại điểm
cuối bước lặp. Điểm thứ hai nữa là các tổ hợp được phát sinh bởi SH cũng chính xác
như trong Apriori nếu CSDL là phân tán đều, chỉ khi CSDL là vô cùng lệch thì việc
phát sinh các tổ hợp mới dẫn đến sự khác biệt.
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 24/35
Ví dụ, nếu A và B không bao giờ xuất hiện cùng nhau (A và B có thể vẫn là phổ biến)
trên phần chia dữ liệu i, nghĩa là thống kê của nó bằng 0, SH sẽ không phát sinh AB
như một tổ hợp ở bước thứ hai trên bộ xử lý i. Nhưng nếu AB xuất hiện cùng nhau
một lần, AB sẽ được phát sinh như một tổ hợp bởi thuật toán SH. Vì thế ta có thể xếp

dựa trên mô hình này đều không làm việc (ngoại trừ SH) hoặc hiệu suất của chúng sẽ
giảm xuống. Riêng SH cố gắng giải quyết hiện tượng này bằng cách chuyển các tổ hợp
xuống đĩa. Một vấn đề có thể xáy ra thêm đối với SH là có quá nhiều tổ hợp cần phải
ghi lên đĩa, như vậy tổng số các local count trong mọi quá trình trên dẫn đến cần nhiều
thao tác I/O. Thêm nữa, SH có thể xảy ra trường hợp tràn tính toán khi phát sinh tổ
hợp trong khi đang thực hiện trực tuyến. Ví như khi thuật toán cần kiểm tra mọi tập
con (k-1) của tập k phần tử trong mỗi giao tác là phổ biến hay không bằng cách tìm
kiếm ảnh của các tập phần tử phổ biến (k-1); trong khi Apriori chỉ cần kiểm tra tập các
phần tử là kết nối của hai tập L
k+1
.
Mô hình Task Parallelism ban đầu được đề xuất nhằm tăng khả năng sử dụng bộ nhớ
chính của máy tính song song. Nó phân chia và phân tán các tổ hợp giữa các bộ xử lý
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy
Tiểu luận Công nghệ tri thức Tramg 25/35
trong mỗi vòng lặp vì thế nó dùng bộ nhớ chính của mọi bộ xử lý và có thể không xảy
ra trường hợp thiếu bộ nhớ với số lượng bộ xử lý ngày càng tăng. Bởi vậy lớp thuật
toán này được dùng để tìm các luật kết hợp với ngưỡng minsupp rất thấp. Tuy nhiên,
Task Parallelism yêu cầu di chuyển các phân vùng dữ liệu để trao đổi.
Thông thường, CSDL được dùng tìm luật là rất lớn, vì vậy việc di chuyển dữ liệu sẽ
làm xảy ra lỗi tràn giao tiếp rất khủng khiếp. Như vậy lớp thuật toán này gặp vấn đề
đối với các CSDL rất lớn. Trong thuật toán cơ bản của mô hình này, độ phức tạp di
chuyển dữ liệu là O(p
2
) với p là số lượng bộ xử lý. Thuật toán IDD dùng kiến trúc
vòng và các giao tiếp diễn ra đồng thời trên các phầhn tử kề nhau vì vậy độ phức tạp
chỉ còn O(p). HPA dùng kỹ thuật băm để di chuyển trực tiếp các phân vùng dữ liệu, vì
vậy nó chỉ di chuyển các giao tác (chính xác là các tập con của các giao tác) đến bộ xử
lý đích thích hợp. Tương tự như các tổ hợp được phân bổ bởi hàm băm, các tập con
của các giao tác cũng được lưu trữ bởi cùng một hàm băm, vì vậy độ phức tạp chỉ là

1
nhận được trong quá trình duyệt CSDL lần đầu tiên. Tương tự, mọi tập phổ biến
trong L
2
cũng được nhận dạng trong lần duyệt thứ hai, và cứ thế tiếp tục. Mọi thuật
Thái Thị Bích Thủy – Nguyễn Thị Kim Ngân – Nguyễn Thị Diễm Thúy

Trích đoạn nhỏ Apriori-

---