ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Khoa Khoa Học Máy Tính
**********    **********
PHƯƠNG PHÁP
TÌM LUẬT KẾT HỢP
TRONG KHO DỮ LIỆU SIÊU THỊ
Bộ môn : Công nghệ tri thức & Ứng dụng
GVHD : GS-TSKH. Hoàng Văn Kiếm
Thực hiện : Lê Minh Trí (CH1101148)
Nguyễn Văn Sang (CH1101128)
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
Thành phố Hồ Chí Minh - Tháng 05 Năm 2012
BẢNG PHÂN CÔNG
 Lê Minh Trí:
o Chương I: Tổng quan
o Chương III: Khai phá dữ liệu
o Chương IV: Luật kết hợp
 Một số khái niệm cơ bản
 Thuật toán tìm luật kết hợp Apriori
 Nguyễn Văn Sang:
o Chương II: Tri thức
o Chương IV: Luật kết hợp
 Ưu điểm và khuyết điểm của thuật toán Apriori
 Cải tiến thuật toán
o Chương VI: Kết luận & Hướng phát triển đề tài
 Lê Minh Trí & Nguyễn Văn Sang:
o Lời nói đầu
o Chương V: Cài đặt chương trình thử nghiệm
o Source code
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 2

phát triển của công nghệ thông tin họ đã chọn cho mình cách lưu trữ dữ liệu trên máy
tính. Nhưng theo thời gian kho dữ liệu ấy cũng càng ngày càng tăng về lượng dữ liệu,
vượt quá khả năng diễn dịch và lĩnh hội của con người. Chúng ta bị tràn ngập trong
dữ liệu nhưng lại thiếu những tri thức mới và hữu ích. Việc tổ chức quản lý và sử
dụng những dữ liệu đó như thế nào trong tương lai lại là một bài toán nan giải của các
doanh nghiệp nói chung và trong lĩnh vực kinh doanh nói riêng. Theo đó một số các
kỹ thuật phân tích dữ liệu một cách thông minh và tự động đã được chọn nhằm tạo ra
các tri thức có giá trị tiềm ẩn trong kho dữ liệu. Khái niệm “Khai phá dữ liệu” hay
còn gọi là Data Mining được ra đời để hỗ trợ một số các công cụ kỹ thuật về phân
tích dự liệu đó.
Khai phá dữ liệu bao gồm rất nhiều những kỹ thuật phân tích dữ liệu bên trong
như: luật kết hợp, phân loại dữ liệu, gom nhóm dữ liệu, lập mô hình, dự báo…nhưng
tiềm ẩn quan trọng nhất vẫn là phương pháp tìm luật kết hợp để tạo ra các tri thức
hữu dụng. Ví dụ như chúng ta có thể dự đoán được những sản phẩm nào sẽ được mua
nhiều trong tương lai đối với hệ thống siêu thị hay dự đoán thị trường đối với lĩnh
vực kinh doanh chứng khoán…
Trong phạm vi bài tiểu luận này, nhóm chúng em sẽ trình bày một cách tổng quát
về cơ sở lý thuyết của phương pháp tìm luật kết hợp, ứng dụng thuật toán Apriori và
đồng thời áp dụng những lý thuyết đó để xây dựng nên một ứng dụng nhỏ để minh
họa cho phương pháp tìm luật kết hợp đó.
Xin gửi lời cảm ơn đến các anh/chị trong cùng khóa học đã nhiệt tình chia sẽ tài
liệu, những thông tin cần thiết trong suốt quá trình học. Và đặc biệt em cũng xin chân
thành cảm ơn thầy Hoàng Văn Kiếm, người đã tận tình truyền đạt cho chúng em
những kiến thức bổ ích về môn “Công nghệ tri thức và ứng dụng”. Từ đó giúp em có
thể nắm vững hơn về cơ sở lý thuyết, tạo điều kiện thuận lợi để nhóm chúng em hoàn
thành tốt bài tiểu luận này.
Thân mến,
Nhóm nghiên cứu
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 4
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm

cùng tìm hiểu về luật kết hợp trong Data Mining. Tuần lễ đầu tiên chính là giai đoạn
tìm hiểu về lý thuyết của thuật toán tìm luật kết hợp. Thời gian còn lại, từ những tư
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 5
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
liệu và tài liệu mà nhóm chúng em đã tìm hiểu được và bắt đầu kết hợp lại để tiến
hành xây dựng nên bài tiểu luận này.
Chương II>Tri thức:
1/ Khái niệm:
Là sự hiểu biết thông qua các quá trình nhận thức phức tạp như: quá trình tri
giác, quá trình học tập, tiếp thu, quá trình giao tiếp, quá trình tranh luận, quá trình
lý luận, hay kết hợp các quá trình này.
2/ Phân loại:
Tri thức có 2 dạng tồn tại chính là tri thức hiện và tri thức ẩn:
a) Tri thức hiện: là những tri thức được giải thích và mã hóa dưới dạng văn
bản, tài liệu, âm thanh, phim, ảnh,… thông qua ngôn ngữ có lời hoặc
không lời, nguyên tắc hệ thống, chương trình máy tính, chuẩn mực hay các
phương tiện khác. Đây là những tri thức đã được thể hiện ra ngoài và dễ
dàng chuyển giao, thường được tiếp nhận qua hệ thống giáo dục và đào tạo
chính quy.
b) Tri thức ẩn: là những tri thức thu được từ sự trải nghiệm thực tế, dạng tri
thức này thường ẩn trong mỗi cá nhân và rất khó “mã hóa” và chuyển giao,
thường bao gồm: niềm tin, giá trị, kinh nghiệm, bí quyết, kỹ năng VD:
Trong bóng đá, các cầu thủ chuyên nghiệp có khả năng cảm nhận bóng rất
tốt; trong một siêu thị điện máy bằng việc phân tích các giao dịch người ta
thấy rằng, có tới 60% độ tin cậy cho việc khách hàng khi mua máy tính thì
cũng mua phần mềm diệt virus. Đây là một dạng tri thức ẩn, nó nằm trong
mỗi cầu thủ Nó không thể “mã hóa” thành văn bản, không thể chuyển
giao, mà người ta chỉ có thể có bằng cách tự mình luyện tập.
3/ Các dạng biểu diễn tri thức thường gặp:
Là đưa ra những giải pháp mới để hoàn thành công việc hoặc làm cho công

a) Làm sạch dữ liệu (data cleaning): loại bỏ nhiễu hoặc các dữ liệu không thích
hợp.
b) Làm giàu dữ liệu (data enrichment): tích hợp dữ liệu từ các nguồn khác nhau
như: CSDL, Kho dữ liệu, file text
c) Chọn lọc dữ liệu (data selection): chọn những dữ liệu liên quan trực tiếp đến
nhiệm vụ sẽ được thu thập từ các nguồn dữ liệu ban đầu.
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 7
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
d) Chuyển đổi dữ liệu (data transformation): dữ liệu sẽ được chuyển đổi về
dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc
tập hợp.
e) Khai phá dữ liệu (data mining): là giai đoạn quan trọng nhất, trong đó các
phương pháp thông minh sẽ được áp dụng để trích xuất ra các mẫu dữ liệu.
f) Đánh giá mẫu (pattern evaluation): đánh giá sự hữu ích của các mẫu biểu
diễn tri thức dựa vào một số phép đo.
g) Biểu diễn dữ liệu (knowlegde presentation): sử dụng các kỹ thuật trình diễn
và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử
dụng.
Hình 1 – Quá trình phát hiện tri thức từ cơ sở dữ liệu
2/ Một số phương pháp khai phá dữ liệu:
a) Phương pháp qui nạp: Một cơ sở dữ liệu là một kho thông tin nhưng các
thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có
hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp.
 Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các
thông tin trong cơ sở dữ liệu. Phương pháp suy diễn dựa trên các sự kiện
chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất
được bằng cách sử dụng phương pháp này thường là các luật suy diễn.
 Phương pháp quy nạp: Phương pháp quy nạp suy ra các thông tin được sinh
ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 8

toán học và khả năng học. Các phương pháp là kết quả của việc nghiên cứu mô
hình học của hệ thống thần kinh con người.
Mạng Neuron có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính
xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện ra các xu hướng
quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát
hiện được. Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến
mạng Neuron. Tuy mạng Neuron có một số hạn chế gây khó khăn trong việc áp
dụng và phát triển nhưng nó cũng có những ưu điểm đáng kể.
d) Phương pháp tìm luật kết hợp:
Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu
trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm
được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp như sau: sự kết hợp giữa hai
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 9
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện
của B trong cùng bản ghi đó: A = > B.
Việc phát triển một thuật toán phải phát hiện luật này trong cơ sở dữ liệu lớn là
không khó. Tuy nhiên, vấn đề là ở chỗ có thể có rất nhiều luật kiểu này hoặc là ta chỉ
biết một tập nhỏ dữ liệu trong cơ sở dữ liệu lớn thoả mãn tiền đề của luật. Ví dụ chỉ
có số ít người mua sách tiếng anh mà mua thêm đĩa CD. Số lượng các luật kết hợp
trong một số cơ sở dữ liệu lớn gần như vô hạn. Do vậy thuật toán sẽ không thể phát
hiện hết các luật và không phân biệt được luật nào là thông tin thực sự có giá trị và
thú vị.
Vậy chúng ta đặt ra câu hỏi là luật kết hợp nào là thực sự có giá trị? Chẳng hạn ta
có luật: Âm nhạc, ngoại ngữ, thể thao = > CD, nghĩa là những người mua sách âm
nhạc, ngoại ngữ, thể thao thì cũng mua đĩa CD. Lúc đó ta quan tâm đến số lượng
trường hơp khách hàng thoả mãn luật này trong cơ sở dữ liệu hay độ hỗ trợ cho luật
này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có cả sách âm nhạc, ngoại ngữ,
thể thao và đĩa CD hay tất cả những người thích cả ba loại sách trên.
Tuy nhiên giá trị hỗ trợ là không đủ. Có thể có trường hợp ta có một nhóm tương đối

và độ tin cậy (C).
a) Độ hỗ trợ (Support): Độ hỗ trợ của một luật r = X
⇒
Y là tỉ số phần trăm
của số giao tác trong D có chứa X
∪
Y. Kí hiệu Supp(r).
Supp(r) thể hiện phạm vi ảnh hưởng của luật trên toàn bộ cơ sở dữ liệu.
Ngưỡng nhỏ nhất của độ hỗ trợ gọi là minsupp
Supp(r)=
)(
)(
DCard
YXCard ∪
(%) 0
≤
Supp(r)
≤
1
Với:
Card(X
∪
Y): tập các giao tác trên CSDL có chứa cả vế trái lẫn vế
phải.
Card(D): tập tất cả các dòng trên CSDL.
b)Độ tin cậy (Confidence): Độ tin cậy của một luật r = X
⇒
Y là tỉ số phần
trăm của số giao tác trong D chứa X
∪

nhỏ nhất (minconf) thì ta có luật kết hợp A ⇒ (L\A).
2/ Thuật toán tìm luật kết hợp Apriori:
a) Mô tả thuật toán:
Bước 1 : k:=1, tạo C1 = tập tất cả các itemsets có 1 phần tử từ tất cả các giao
tác.
Đọc cơ sở dữ liệu để tính độ hỗ trợ thỏa mãn (support >= minsup) trên C1 từ
đó rút ra được tập L1.
Bước 2 :
For (k = 2 ; Lk-1 khác rỗng ; k++)
{
• Tạo ra tập Ck, là tập các itemsets ứng viên có (k-1) phần tử, tạo
ra từ tập Lk-1.
• Duyệt qua tất cả các giao tác để tính số lần xuất hiện của các
itemsets trong Ck
• Tìm Lk, Lk là một tập con của Ck có chứa k phần tử với số đếm
>= minsup.
}
Bước 3 : Tạo tập LargeItemSet = L1 v L2 v v Lk
Bước 4 : Tạo các luật hợp từ tập LargeItemSet :
for each itemset l của LargeItemSet
for each s (tập con khác rỗng) của l
if confidence=count(l)/count(s) >= minconf then
xuất kết quả : s -> (l-s)
Minh họa thuật toán Apriori với minsup = 2, minconf = 50%
 Giải thích ký hiệu :
+TID : chỉ số định danh các giao tác của một itemset.
+ items : tập các mặt hàng
+ itemset : tập các mặt hàng ứng viên
+ sup : độ hỗ trợ tối thiểu
+ Ck tập các ứng viên với kích cỡ k được tạo ra bằng cách kết hợp Lk-1 với

2
Loại bỏ các tập mục có độ hỗ trợ < Minsup, các tập mục còn lại của C
2
là tập các tập 2-
Itemset (L
2
) phổ biến. L
2
lại được sử dụng để sinh ra L
3
và cứ tiếp tục như vậy cho đến
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 13
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
khi tìm được tập mục k-Itemset

mà L
k
= ∅ (tức là không có tập mục phổ biến nào được
tìm thấy) thì dừng lại. Tập các tập mục phổ biến của CSDL là: ∪
k
i-1
= L
1
Để tăng hiệu quả của thuật toán trong quá trình sinh các tập mục ứng cử, ta sử
dụng tính chất của tập mục phổ biến để làm giảm số lượng tập các tập ứng cử, không
phải là tập phổ biến được sinh ra. Tính chất đó là: Tập các tập con khác rỗng của tập
mục phổ biến đều là tập mục phổ biến.
3/ Ưu điểm và khuyết điểm 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

do đó tập ứng viên Ck kích cỡ k có thể nhỏ hơn cơ sở dữ liệu. Nếu một giao tác
không chứa k – itemset ứng viên, khi đó nó sẽ được loại ra khỏi tập Ck. Với k có kích
cỡ lớn, mỗi tập mục có thể nhỏ hơn một giao tác. Giao tác có thể chỉ chứa một vài
ứng viên. Một tập mục bao gồm tất cả các k – itemset chứa trong giao tác. Tuy nhiên
thuật toán này có một điểm bất lợi là khi kích cỡ k nhỏ, mỗi tập mục có thể lớn hơn
số giao tác tương ứng.
Trình bày thuật toán AprioriTid:
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 14
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
Giải thích ký hiệu :
C^
k
: tập mục lưu trữ, mỗi thành viên của C^
k
có dạng <TID, { X
k

}, với X
k là
tập k-
itemset, thể hiện một giao tác t có mã là TID.

k
k
kk
t
^
kt
t
kt

=
++≠=
=
=
end
end
end
if
;
do candidates forall

begin do forall
;genapriori-
begin do For
1
1
φ
φ
Đánh giá tốc độ của thuật toán Apriori và AprioriTid
Để đánh giá về tốc độ của thuật toán Apriori và AprioriTid, chúng em lấy kết quả
từ một dự án Quest của trung tâm nghiên cứu IBM Almaden. Kết quả được thực hiện
trên tập dữ liệu đầu vào :
Kích thước trung bình của các giao tác là 10
Kích thước trung bình của tập phổ biến tối đại là 4
Số giao tác là 100.000
Độ hỗ trợ tối thiểu là 0.75%
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 15
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
Hình 3 – Sơ đồ so sánh Apriori và AprioriTid
Kết quả cho thấy ở giai đoạn đầu Apriori hiệu quả hơn AprioriTid về mặt thời

• diachi : địa chỉ
• email: email
Hóa đơn :
• maHD : mã hóa đơn
• maKH : mã khách hàng
• ngay : ngày hóa đơn
• tongTien : tổng tiền cho một hóa đơn
Chi tiết hóa đơn
id : mã chi tiết hóa đơn
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 17
KhachhangmaKH :
bigint
tenKH : nvarchar
cmnd : varchar
sdt : varchar
diachi : text
email: varchar
HoadonmaHD :
bigint
maKH : bigint
ngay : datetime
tongTien : numberic
ChitietHoadonid :
bigint
hdId : bigint
soluong: int
tongTien : numberic
Mathangid : bigint
chitietHDId :
bigint

minSup /= 100.0;
int itemsetNumber = 0;
// tạo hàm hỗ trợ cho việc tính sự suất hiện mặt hàng
getConfig(numItems, numTransactions, minSup);
List<ItemInfo> result = new List<ItemInfo>();
do
{
itemsetNumber++;
//Tạo các tập ứng viên
generateCandidates(itemsetNumber, numItems);
//hàm tính độ phổ biến của tập ứng viên
calculateFrequentItemsets(itemsetNumber, numItems, numTransactions,
minSup, transaFile, allItemsName, result);

} while (candidates.Count > 1);

return result;
}
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 18
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
// tạo hàm hỗ trợ cho việc tính sự suất hiện mặt hàng
private void getConfig(int numItems, int numTransactions, double minSup)
{

oneVal = new String[numItems];
for (int i = 0; i < oneVal.Length; i++)
{
oneVal[i] = "1";
}
}

}
}
else
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 19
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
{
for (int i = 0; i < candidates.Count; i++)
{
for (int j = i + 1; j < candidates.Count; j++)
{
str1 = "";
str2 = "";
st1 = new StringTokenizer(candidates[i]);
st2 = new StringTokenizer(candidates[j]);
for (int s = 0; s < n - 2; s++)
{
str1 = str1 + " " + st1.NextToken();
str2 = str2 + " " + st2.NextToken();
}
if (str2.Equals(str1))
tempCandidates.Add((str1 + " " + st1.NextToken() + " " +
st2.NextToken()).Trim());
}
}
}
//xóa các ứng viên cũ đi
candidates.Clear();
candidates = new List<String>(tempCandidates);
tempCandidates.Clear();
}

Console.Write(a+" ");
}

//kiểm tra ứng viên
for(int c=0; c < candidates.Count; c++)
{
match = false;
st = new StringTokenizer(candidates[c]);
while(st.HasMoreTokens())
{
match = (trans[Int32.Parse(st.NextToken())-1]);
if(!match)
break;
}
if(match)
count[c]++;
}
}
StringBuilder builder = new StringBuilder();
for(int i=0; i<candidates.Count; i++)
{
double doPB =(count[i] / (double)numTransactions);
if (doPB >= minSup)
{
frequentCandidates.Add(candidates[i]);
string[] candi = candidates[i].Split(' ');
builder.Clear();
for (int m = 0; m < candi.Length; m++) {
int key = int.Parse(candi[m]);
if (candi.Length == 1)

}
//xóa các ứng viên cũ đi
candidates.Clear();
candidates = new List<String>(frequentCandidates);
frequentCandidates.Clear();
return result;
}
c) Hướng dẫn sử dụng:
Để chạy được chương trình, máy tính cần phải có bộ .Net phiên bản từ 3.5 trở lên,
ngoài ra cần cài đặt chương trình đọc file Excel để nhập liệu nếu muốn kiểm tra nhiều
hơn dữ liệu cài đặt sẵn.
Vào thư mục “chuong_trinh/findAssociatedRules”,của chương trình, nhấp đúp
chuột vào file findAssociatedRules.exe, ta có giao diện chương trình như sau :
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 22
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
Hình 5 – Giao diện chương trình tìm luật kết hợp trong siêu thị.
Ở màn hình trên, phía bên trái, ta có thể nhập tham số, ví dụ nhập độ hỗ trợ tối
thiểu vào ô “Độ hỗ trợ”, sau đó nhấn vào nút “Tìm luật”, ta đươc kết quả như hình
bên dưới :
Hình 6 – Giao diện kết quả chương trình tìm luật kết hợp trong siêu thị.
Ngoài ra người dùng có thể nhập thêm dữ liệu để tính tìm luật, bằng cách nhập
liệu vào 2 file Excel được đính kèm trong thư mục
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 23
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
chuong_trinh/findAssociatedRules, đó là 2 file : Hoadon.xls và ChitietHD.xls.
Hình 7 – File excel cho hóa đơn
Hình 8 – File excel cho chi tiết hóa đơn
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 24
Công nghệ tri thức & Ứng dụng GVHD: GS-TSKH Hoàng Văn Kiếm
Chương V> Kết luận & Hướng phát triển đề tài:

thời tùy vào độ phức tạp của dữ liệu mà nên quyết định chọn hoặc kết hợp các thuật
toán cho phù hợp như: Aprioritid, AprioriHybrid… Từ đó giúp cho các nhà quản lý
trong các lĩnh vực khác như chứng khoán, bất động sản, y tế, siêu thị…có thể tự tin
áo dụng phương pháp này nhằm tìm ra những tri thức mới từ kho dữ liệu đã có để
phục vụ vì lợi ích của toàn doanh nghiệp.
HVTH: Lê Minh Trí – Nguyễn Văn Sang Trang 25