Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Bài thu hoạch môn học
Công nghệ tri thức
Ứng dụng thuật toán Apriori trong khai phá dữ
liệu sử dụng luật kết hợp
GVHD môn học: GS.TSKH. Hoàng Kiếm
Học viên thực hiện: Đặng Thị Thanh Châu
MSHV: CH1201005
Tp. HCM, Tháng 10/2014
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 1
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
MỤC LỤC
MỤC LỤC 2
LỜI GIỚI THIỆU 3
Chương 1: Tổng quan về Data Mining 4
1.1 Data Mining là gì: 4
1.2. Các phương pháp khai phá trong Data Mining: 5
1.2.1. Phân lớp và dự đoán (Classification & Prediction) 5
1.2.2. Hồi quy (Regression) 6
1.2.3. Time Series Analysis (Phân tích chuỗi thời gian) 6
1.2.4. Prediction (Dự đoán) 6
1.2.5. Clustering (Gom nhóm) 6
1.2.6. Summarization (Tổng quát hóa) 7
1.2.7. Luật kết hợp (Association Rules): 7
1.3. Các ứng dụng của Data Mining: 7
1.4. Kết luận: 8
Chương 2: Thuật toán Apriori trong khai phá dữ liệu luật kết hợp 9

tối ưu hóa cơ sở tri thức…
- Các hệ cơ sở tri thức (knowledge-based systems): tìm hiểu cấu trúc bên
trong của một hệ cơ sở tri thức, phân loại các hệ cơ sở tri thức, và một số hệ cơ
sở tri thức điển hình.
- Khai mỏ dữ liệu, khám phá tri thức (Data mining, knowledge discovery):
nghiên cứu về phương pháp, kỹ thuật để khai mỏ dữ liệu và khám phá tri thức.
……………
Do lĩnh vực nghiên cứu về Công nghệ tri thức rất rộng và sâu, nên bài tiểu
luận môn học của em chỉ đề cập nghiên cứu theo hướng khám phá Công nghệ tri
thức về Khai phá dữ liệu (Data Mining).
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 3
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Chương 1: Tổng quan về Data Mining
1.1 Data Mining là gì:
Data Mining (khai phá dữ liệu) là một khái niệm mô tả quá trình khám phá
các tri thức mới và các tri thức có ích ở dạng tiềm năng trong các nguồn dữ liệu
lớn, đã có.
Data Mining là một bước của tiến trình KDD (Knowledge discovery in
databases), nhằm:
- Rút trích thông tin hữu ích, chưa biết, tiềm ẩn trong khối dữ liệu lớn
- Phân tích dữ liệu bán tự động
- Giải thích dữ liệu trên các tập dữ liệu lớn
Một tiến trình KDD là một chuỗi lặp gồm các bước:
1) Data cleaning & intergration (làm sạch dữ liệu, tích hợp dữ liệu)
2) Selection & transformation (chọn lựa dữ liệu, biến đổi dữ liệu)
3) Data Mining (khai phá dữ liệu)
4) Evaluation & presentation (đánh giá kết quả mẫu, biểu diễn tri thức).
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

không nợ, từ đó giúp họ ra quyết định cho vay hay không cho vay.
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),…
1.2.2. Hồi quy (Regression)
Hồi quy là việc đưa một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự
đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác
nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự
báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng
hạn như hồi quy tuyến tính.
1.2.3. Time Series Analysis (Phân tích chuỗi thời gian)
Dựa trên việc phân tích chuỗi quan sát của một biến duy nhất theo biến số độc
lập là thời gian. Phương pháp dự báo theo chuỗi thời gian là một phương pháp
định lượng, sử dụng những dữ liệu quá khứ theo thời gian, dựa trên dữ liệu lịch
sử để phát hiện chiều hướng vận động của đối tượng phù hợp với một mô hình
bài toán nào đó và đồng thời sử dụng mô hình đó làm mô hình ước lượng. Tiếp
cận định lượng dựa trên giả định rằng giá trị tương lai của biến số dự báo sẽ phụ
thuộc vào xu thế vận động của đối tượng đó trong quá khứ.
1.2.4. Prediction (Dự đoán)
Với mô hình học tương tự như bài toán phân lớp, lớp bài toán dự đoán sẽ lọc
ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin
đang có để đưa ra một giá trị số học cho hàm cần dự đoán. Bài toán tiêu biểu
trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh.
1.2.5. Clustering (Gom nhóm)
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
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005



Trang 7
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Do đó, Data Mining có nhiều ứng dụng trong thực tế, như:
- Tài chính và thị trường chứng khoán (Finance & stock market): Phân tích
tình hình tài chính và dự đoán giá cổ phiếu.
- Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định
- Điều trị y học và chăm sóc y tế: một số thông tin về chuẩ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 các triệu
chứng bệnh, chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc,
thời gian )
- Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.
- Text mining và 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 kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một
số bệnh di truyền,
- Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi,
sự cố, chất lượng dịch vụ,
1.4. Kết luận:
Khám phá tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh
vực. Tuy đã có rất nhiều các giải pháp và phương pháp được ứng dụng trong
khai phá dữ liệu nhưng trên thực tế quá trình này vẫn gặp không ít khó khăn và
thách thức như:
- Cơ sở dữ liệu lớn
- Số chiều các thuộc tính lớn
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 8
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp

chứa X∪Y so với số giao tác trong D chứa X, khi đó ta có :
Conf(X=>Y) = c %= Card(X∪Y)/Card(X)%
Tâp các hạng mục dữ liệu gọi là ItemSet có độ support lớn hơn hay bằng giá
trị ngưỡng nhỏ nhất (gọi là minsupp) được gọi là Large ItemSet. Các ItemSet
còn lại được gọi là các Small ItemSet.
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 9
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Với mỗi một Large ItemSet - L, và A là một tập con khác rỗng của L, nếu tỉ
lệ % giữa support(L) so với support(A) >= độ tin cậy nhỏ nhất (gọi là minconf)
thì ta có luật kết hợp A => (L\A).
Luật kết hợp X→Y được coi là một tri thức (mẫu có giá trị)
nếu xảy ra đồng thời supp(X→Y) ≥ minsup và conf(X→Y) ≥
minconf. Trong đó minsup và minconf là hai giá trị ngưỡng
cho trước. Một tập mục X có độ hỗ trợ vượt qua ngưỡng
minsup được gọi là tập phổ biến.
Minh họa: Cho CSDL sau
Một số loại luật kết hợp:
- Binary association rules (luật kết hợp nhị phân): Apple => Banana
- Quantitative association rules (luật kết hợp định lượng):
weight in [70kg – 90kg] => height in [170cm – 190cm]
- Fuzzy association rules (Luật kết hợp mờ):
weight in HEAVY => height in TALL
Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary
association rules
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 10
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp

2
,…, t
m
}.
Ngưỡng tối thiểu minsup > 0.
Output: Tập hợp tất cả các tập phổ biến.
mincount = minsup * |D|;
F
1
= { các tập phổ biến có độ dài 1};
for(k=1; F
k
!= ∅; k++)
{
C
k+1
= Apriori_gen(F
k
);
for each t in D
{
C
t
= { c ∈ C
k+1
| c ⊆ t};
for c ∈ C
t

c.count++;

∪ F
2
∪ … ∪ F
k
Để sinh các luật kết hợp thì đối với mỗi tập phổ biến I ∈ F, ta xác định các tập
mục không rỗng là con của I. Với mỗi tập mục con s không rỗng của I ta sẽ thu
được một luật kết hợp s→(I-s) nếu độ tin cậy thỏa mãn:
conf(s→(I-s)) = supp(I)/supp(I-s) ≥ minconf
(minconf là ngưỡng tin cậy cho trước)
Minh họa 1: Giả sử ta có CSDL giao dịch như sau :
Thuật toán Apriori khai phá luật kết hợp được mô tả qua các bước sau
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 12
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Ta có frequent itemsets I ={B,C,E}, với min_conf =80% ta có 2 luật kết hợp
là: {B,C} => {E} và {C,E} => {B}
Minh họa 2: Giả sử ta có CSDL giao dịch bán hàng gồm 5 giao dịch như
sau:
Thuật toán Apriori tìm các luật kết hợp trong giao dịch bán hàng trên như sau:
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 13
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Kết quả ta có các luật kết hợp sau (với min_sup= 40%, min_conf=70%)
R1: Beer => Diaper (support =60%, confidence = 75%)
R2: Diaper =>Beer (support =60%,confidence = 75%)
R3: Milk =>Beer (support =40%, confidence = 100%)
R4: Baby Powder => Diaper (support =40%,confidence = 100%)
Từ kết quả các luật được sinh ra bởi giao dịch bán hàng trên, ta thấy rằng có

Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Chương 3: Ứng dụng Khai phá luật kết hợp với Microsoft
Association Rule
3.1. Mô tả công cụ và CSDL dùng để khai phá luật kết hợp:
Khai phá luật kết hợp (Association Rule Discovery) là kỹ thuật rất quan trọng
trong lĩnh vực khai phá dữ liệu. Mục đích của việc khai phá luật kết hợp là tìm
ra các mối quan hệ, sự kết hợp hay mối tương quan giữa các đối tượng trong
khối lượng lớn dữ liệu
Công cụ sử dụng khai phá dữ liệu bằng luật kết hợp:
Công cụ xây dựng mô hình khai phá dữ liệu Business Intelligence
Development Studio (BIDS) của Microsoft SQL Server 2008 R2 Enterprise.
BIDS là công cụ cho phép tổ chức quản lý và khai thác kho dữ liệu (Xử lý
phân tích trực tuyến) cũng như xây dựng các mô hình khai phá dữ liệu rất dễ sử
dụng và hiệu quả của Microsoft
BIDS cho phép triển khai các mô hình khai phá dữ liệu sau:
- Micorosft Decision Tree (Cây quyết định)
- Microsoft Clustering (Phân cụm)
- Micorosoft Naive Bayes(Phân lớp với Bayes Rules)
- Micorosoft Time Series (Chuỗi thời gian)
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 16
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
- Micorosoft Association Rule (Luật kết hợp)
- Micorsoft Sequence Clustering (Phân tích chuỗi)
- Microsoft Neural Network (Mạng Neural)
- Micorsoft Linear Regression(Hồi qui tuyến tính)
- Micorsoft Logistics Regression(Hồi qui logistics)
Mô tả dữ liệu sử dụng trong mô hình:
Cơ sở dữ liệu minh họa AdventureWorks lấy bối cảnh trên dữ liệu của 1 công

3.2 Qui trình xây dựng mô hình khai phá dữ liệu với BIDS như sau:
Tạo mới 1 project (Analysis Services Project)
Tạo một Data Source
Tạo một Data Source View
Tạo một Mining Model structure.
Tạo các Mining Models.
Khai thác Mining Models.
Kiểm tra độ chính xác của Mining Models.
Sử dụng Mining Models để dự đoán.
3.2.1 Tạo mới 1 project (Analysis Services Project)
Khởi động SQL Server Business Intelligence Development Studio tạo 1 project mới có tên
“DataMing”
3.2.2 Tạo Data Source kết nối đến CSDL AdventureWorksDW
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 19
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
3.2.3 Tạo một Data Source View:
Trong Data Source View chọn dữ liệu lấy từ View là vAssocSeqOrders và
vAssocSeqLineItems
3.2.4 Tạo một Mining Model structure.
Trong cửa sổ Solution Explorer, bấm phải chuột trên mục Mining
Structures chọn New Mining Structure. Sau đó chọn mô hình khai phá dữ liệu
là Microsoft Association Rules.
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 20
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Bấm Next và chọn Data Source View đã tạo là AdventureWorksDW. Bấm
Next và chọn Case là vAssocSeqOrders và Nested là vAssocSeqLineItems.

Probability: Cho biết xác suất xảy ra của luật.
Importance: Đo lường tính hữu dụng của luật, giá trị này càng cao thì luật
kết hợp càng tốt.
Rules: Phần này thể hiện các luật kết hợp dạng x==>Y
Các luật này cho biết sự kết hợp giữa các items trong cở sở dữ liệu giao
dịch. Chẳng hạn luật kết hợp thứ 3 cho bạn biết rằng nếu một khách hàng nào đó
mua các sản phẩm là xe đạp model ML Road Tire và Sport-100 thì người đó
luôn mua Road Tire Tube với xác suất 100%.
- Dependency Net (Mạng phụ thuộc):
Sử dụng Dependency Net cho phép bạn hiểu được sự tác động của các
items khác nhau trong Model. Mỗi Node trong Dependency Net thể hiện một
Item, bằng cách chọn một item bạn sẽ thấy được các items khác được xác định
bởi Item đã chọn (hoặc dùng để xác định Item đã chọn) trong model.
Bạn có thể kéo thanh trượt (Slile) bên phải để xem các mức độ kết hợp
(mạnh hay yếu) giữ các Items trong model.
Học viên thực hiện : - Đặng Thị Thanh Châu CH1201005

Trang 23
Ứng dụng thuật toán Apriori trong khai phá dữ liệu sử dụng luật kết hợp
Trong Dependency Net, nếu chọn Node Mountain bottle Cage ta sẽ thấy
rằng Item Mountain bottle Cage có thể được dự đoán bởi 2 items khác đó
là Water bottle và Mountain-200 hoặc Mountain bottle Cage được dùng để
dự đoán 2 Items water bottle và Mountain-200 (Dấu mũi tên 2 chiều, xem hình
dưới).
Điều này có nghĩa là những sản phẩm này có khả năng được mua cùng
nhau. Nếu khách hàng nào đó mua xe đạp thì có khả năng họ mua kẹp để bình
đựng nước và bình đựng nước.
Các thông tin này có thể giúp cho bộ phận bán hàng đặt các sản phẩm có
khả năng mua cùng nhau cạnh nhau để giúp cho khách hàng khỏi mất công tìm
kiếm cũng như xây dựng các chiến lược marketing hiệu quả.