ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN MÔN KHAI PHÁ DỮ LIỆU
PHÂN TÍCH VÀ MÔ PHỎNG BÀI TOÁN
TÌM LUẬT KẾT HỢP THEO
THUẬT TOÁN APRIORI
Giảng viên hướng dẫn : PGS.TS. Đỗ Phúc
Sinh viên thực hiện :
Nguyễn Thị Thu Trang CH1101147
Lớp : CNTTQM K6
Khóa : 2012 - 2014
TP Hồ Chí Minh, tháng 11 năm 2012
1
MỤC LỤC
2
Nguyễn Thị Thu Trang CH1101147
I. Tổng quan về khai phá dữ liệu
1.1. Tại sao lại cần khai phá dữ liệu? (Data Mining)
Trong những năm gần đây, sự phát triển mạnh mẽ của Công nghệ thông tin
và ngành công nghiệp phần cứng đã 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 chóng mặt. Bên cạnh đó việc
tin học hoá 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 hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu
lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các hoạt động
sản xuất, kinh doanh, quản lí , trong đó có nhiều cơ sở dữ liệu cực lớn cỡ
Gigabyte, thậm chí là Terabyte.
Ngày nay lượng thông tin được lưu trữ trên các thiết bị điện tử (đĩa cứng,
CD-ROM, băng từ, .v.v.) không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra
với một tốc độ bùng nổ. Người ta ước đoán rằng lượng thông tin trên toàn cầu
tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡcủa các cơ
sở dữ liệu (cơ sở dữ liệu) cũng tăng lên một cách nhanh chóng. Nói một cách

Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để
tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập
hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong
tập dữ liệu đó.
Khai phá dữ liệu là một bước của quá trình khai thác tri thức (Knowledge
Discovery Process)[1], bao gồm:
- Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu và
các dữ liệu không cần thiết.
- Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành
những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch
và tiền xử lý (data cleaning & preprocessing).
- Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ
liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri
[4]
Nguyễn Thị Thu Trang CH1101147
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.
- Chuyển đổi dữ liệu: 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.
- Ước lượng mẫu (knowledge evaluation): 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): 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.
Quá trình khai thác tri thức không chỉ là một quá trình tuần tự từ bước đầu
tiên đến bước cuối cùng mà là một quá trình lặp và có quay trở lại các bước đã
qua.
1.3. Các chức năng chính của khai phá dữ liệu

data.
- Tổng hợp (Summarization): An additional descriptive task that involves
methods for finding a compact description for a set (or subset) of data.
- Mô hình ràng buộc (Dependency modeling): Finding a local model that
describes significant dependencies between variables or between the
values of a feature in a data set or in a part of a data set.
- Dò tìm biến đổi và độ lệch (Change and Deviation Dectection):
Discovering the most significant changes in the data set.
[6]
Nguyễn Thị Thu Trang CH1101147
1.5. Ứng dụng của khai phá dữ liệu
Data Mining tuy là một hướng tiếp cận mới nhưng 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ó. Chúng ta có thể liệt kê ra đây một số ứng dụng điển hình:
- Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision
support)
- Điều trị y học (medical treatment)
- Text mining & Web mining
- Thiên văn học
- Tin sinh học
- Bào chế thuốc
- Thương mại điện tử
- Phát hiện lừa đảo
- Quảng cáo
- Marketing
- Quản lý quan hệ khách hàng (CMR - Customer Relationship
Management)
- Chăm sóc sức khỏe
- Viễn thông
- Thể thao, giải trí

1.6.3. MATLAB
MATLAB hay Matrix Laboratory là một ngôn ngữ lập trình tuyệt vời được
sử dụng rộng rãi trong một loạt các lĩnh vực như xử lý ảnh, xử lý tín hiệu, toán
học và phân tích thống kê, … . MATLAB được sử dụng rộng rãi để khai thác dữ
liệu bởi vì khả năng xử lý các giai đoạn khác nhau của khai thác dữ liệu. Nó được
trang bị với một số hộp công cụ mạnh mẽ như:
- MathWorks Neural Network Toolbox
- Fuzzy Clustering và Data Analysis Toolbox
- Association Rule Miner và Deduction Analysis Tool
- Cây quyết định (Decision Tree)
[10]
Nguyễn Thị Thu Trang CH1101147
1.6.4. DB2 Intelligent Miner
DB2 Intelligent Miner được giới thiệu trong các ngành công nghiệp kinh
doanh thông minh bởi IBM. Nó có thể được sử dụng trong các lĩnh vực kinh
doanh khác nhau để tìm những cái nhìn mới và thú vị trong số các dữ liệu giao
dịch có giá trị để đưa ra các quyết định kinh doanh lớn. Nó có thể được sử dụng
trong xác định các hành vi gian lận, phân khúc khách hàng hoặc để thực hiện
phân tích thị trường, có lợi trong việc giảm tỉ lệ hao mòn và thúc đẩy doanh số
bán hàng bằng cách bán hàng chéo hoặc tiếp thị hướng mục tiêu. Khả năng khai
thác cơ sở dữ liệu cho phép nó để có thể để tích hợp với những hệ thống hiện có
một cách dễ dàng.
[11]
Nguyễn Thị Thu Trang CH1101147
[12]
Nguyễn Thị Thu Trang CH1101147
II. Luật kết hợp (Association Rule)
2.1. Luật kết hợp trong khai phá dữ liệu (Association Rule in Data
Mining)
Nội dung cơ bản của luật kết hợp được tóm tắt như dưới đây.

kiện Y khi đã biết X như sau :
Trong đó: n(X) là số giao dịch chứa X
Để thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí : Minimum
Support (min_sup) và Minimum Confidence (min_conf).
Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng)
cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Rule).
Minimum support và Minimum confidence gọi là các giá trị ngưỡng
(threshold) và phải xác định trước khi sinh các luật kết hợp.
Một itemsets mà tần suất xuất hiện của nó >= min_sup goi là frequent
itemsets
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
[14]
Nguyễn Thị Thu Trang CH1101147
- 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.
2.2. Thuật toán Apriori
2.2.1. Thuật giải tạo ứng viên Apriori (Apriori Candidate Generation)
Thuật giải Apriori-Gen cần một tham số L
k-1
, tập hợp gồm (k-1) items. Nó
trả về một tập hợp cha của tập hợp gồm k items. Thuật giải thực hiện theo các
bước sau :
Đầu tiên, ở bước join chúng ta join L
k-1
với L

3
(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)
Thuật toánApriori
- 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
- 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
)
[16]
Nguyễn Thị Thu Trang CH1101147
- 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 độ tin cậy (Confidence) của nó > = min_conf

8. Vùng nhập dữ liệu điều kiện MinSupp, MinConf. Sau khi nhập đầy
đủ dữ liệu click button (Solve) để hiển thị lời giải
9.
10. Vùng hiển thị lời giải. Các bước giải bao gồm
- Tập thuộc tính Items trong database
- Các tập ứng viên và độ support của nó.
- Tập phổ biến theo bậc k
- Tập phổ biến tổng quát
- Tập phổ biến tối đại
- Các bước tìm luật kết hợp từ tập phổ biến tổng quát tìm được
11.
[21]
Nguyễn Thị Thu Trang CH1101147
12.
13. Ví dụ mẫu minh họa. Chọn một trong những ví dụ mẫu có sẵn rồi
click button (Open) để thể hiện ví dụ mẫu trên giao diện
14.
15.
[22]
Nguyễn Thị Thu Trang CH1101147
IV. Kết luận
16. Khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in
Databases) đang là một xu hướng quan trọng của nền Công nghệ thông tin thế
giới. Nó có khả năng ứng dụng vào rất nhiều lớp bài toán thực tế khác nhau.
Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining) giúp
người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các
nguồn dữ liệu khổng lồ khác.
17. Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những
hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về Công nghệ
thông tin trên thế giới. Trong những năm gần đây, rất nhiều các phương pháp và

[7]. http://en.wikipedia.org/wiki/Apriori_algorithm
[24]