MỤC LỤC
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 4
1. Giới thiệu về khai phá dữ liệu 4
2. Lịch sử phát triển khai phá dữ liệu 5
3. Tại sao dùng khai phá dữ liệu 6
4. Quá trình khám phá tri thức từ cơ sở dữ liệu 6
5. Khai phá dữ liệu (data mining) 7
6. Các kỹ thuật khai phá dữ liệu 8
6.1. Phân cụm dữ liệu: 9
6.2. Phương pháp hồi quy: 10
6.3. Khai phá luật kết hợp: 10
7. Các quy trình khai phá dữ liệu 12
8. Các hệ thống khai phá dữ liệu (data mining systems) 14
9. Ứng dụng của khai phá dữ liệu 16
KHAI PHÁ LUẬT KẾT HỢP 17
1. Tổng quan về khai phá luật kết hợp 17
1.1. Quá trình khai phá luật kết hợp 17
1.2. Các khái niệm cơ bản 17
1.3. Phân loại luật kết hợp 18
2. Biểu diễn luật luật kết hợp 19
3. Khám phá các luật kết hợp dựa trên ràng buộc 20
TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 21
1. Thuật toán AIS 21
2. Thuật toán SETM 21
3. Thuật toán Apriori 22
3.1. Ý tưởng thuật toán Apriori 22
3.2. Thuật toán Apriori (Pseudo code) 23
3.3. Đặc điểm của thuật toán Apriori 25
3.4. Các cải tiến thuật toán Apriori (Methods to Improve Apriori’s Efficiency) 25
4. Thuật toán FP-growth 26
4.1. Ý tưởng thuật toán 26

4.2. Giải thuật FP-growth 26
4.2.1. Xây dựng cây FP-tree 26
4.2.2. Khám phá frequent itemsets với FP-tree 27
4.3. Đặc điểm của FP-growth 28
KHAI PHÁ LUẬT KẾT HỢP TRONG BÀI TOÁN KHÁM VÀ ĐIỀU TRỊ BỆNH NHÂN
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 30
1. Cài đặt chương trình: 30
2. Về kỹ thuật: 30
3. Giao diện chương trình: 30
4. Cơ sở dữ liệu: 32
5. Giới thiệu source code của chương trình: 35
5.1. Code project Apriori: 35
5.2. Code project Data Access: Source code truy xuất CSDL bệnh viện Bà Bịa (benhvienbr)
42
6. Hướng dẫn sử dụng: 44
KẾT LUẬN 47
TÀI LIỆU THAM KHẢO 48
1
Khóa luận môn học: Khai phá dữ liệu
CÁC TỪ VIẾT TẮC
Ký hiệu Diễn giải
CSDL Cơ sở dữ liệu
KPDL Khai phá dữ liệu
KDD
Knowledge Discovery and Data Mining
CNTT
Công nghệ thông tin
DB Cơ sở dữ liệu giao tác
FP-Growth Frequent parttern tree

FP-tree Frequent pattern tree
IT-tree Itemset-Tidset tree
I Tập các mục dữ liệu
ICD Phân loại bệnh tật quốc tế (ICD-10)
YHCT Y học cổ truyền
Minsup Độ hỗ trợ tối thiểu
Minconf Độ tin cậy tối thiểu
TID Định danh của giao tác
TID_List Danh sách định danh của giao tác
T Giao tác
k-itemset Một itemset có k items
L
k
Tập phổ biến k-itemsets
C
k
Tập ứng viên k-itemsets
kC
Tập ứng viên k-itemsets mà tập giao tác có chứa
nó.
We are data rich, but information poor.
“Necessity is the mother of invention”. - Plato
Nguyễn Văn Quang - CH1101126
2
Khóa luận môn học: Khai phá dữ liệu
LỜI NÓI ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông
tin đã 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 nhanh chóng. Bên cạnh đó, việc tin học hóa 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 cần 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, y tế, giáo dục, quản lý , trong đó có nhiều cơ sở dữ liệu rất lớn cỡ
Gigabyte, thậm chí là Terabyte.
Ý nghĩa và vai trò khai phá dữ liệu: công nghệ hiện đại trong lĩnh vực
quản lý thông tin, hiện diện khắp nơi và có tính ẫn trong nhiều khía cạnh của đời
sống hằng ngày như: làm việc, mua sắm, tìm kiếm thông tin, Được áp dụng
trong nhiều ứng dụng thuộc nhiều lĩnh vực khác nhau. Hỗ trợ các nhà khoa học,
giáo dục học, kinh tế học, doanh nghiệp, khách hàng.
Ngày nay, khai phá dữ liệu đang được áp dụng một cách rộng rãi trong
nhiều lĩnh vực như: Trong kinh doanh (business); trong tài chính (finance) và
tiếp thị bán hàng (sales marketing); trong thương mại (commerce) và ngân hàng
(bank); trong bảo hiểm (insurance); trong khoa học (science) và y sinh học
(biomedicine); trong điều khiển (control) và viễn thông (telecommunication),
Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ
liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích
to lớn.
Trong nội dung bài tiểu luận này, tôi xin trình bày khái quát bài toán
“Tìm hiểu một số thuật toán tìm luật kết hợp. Ứng dụng thuật toán Apriori vào
chương trình tìm luật kết hợp tiềm ẫn trong CSDL khám và điều trị bệnh nhân
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” mà tôi đã tìm hiểu được. Vì thời gian có hạn nên trong khoá luận môn học
tôi chỉ trình bày chi tiết phần quan trọng nhất, cũng như khó nhất của tiến trình
Data Mining.
Tôi xin chân thành cảm ơn PGS. TS Đỗ Phúc, giảng viên môn học “Khai
phá dữ liệu”, Thầy đã tận tâm đã truyền đạt những kiến thức quý báu về khai
phá dữ liệu, một số ứng dụng, và cũng như những hướng nghiên cứu chính trên
thế giới hiện nay của nó. Tôi xin chân thành cảm ơn Bác sỹ chuyên khoa 1
Huỳnh Công Trứ phòng khám Đông y bệnh viện Bà Rịa đã hỗ trợ trong quá
trình thực nghiệm khai phá dữ liệu của phòng khám.Tôi xin chân thành cảm ơn

ban cố vấn học tập và ban quản trị Chương trình đào tạo thạc sĩ Công nghệ của
trường Đại Học Công nghệ Thông tin – Đại học Quốc Gia thành phố Hồ Chí
Minh đã tạo điều kiện về tài liệu học tập và tham khảo.
Nguyễn Văn Quang - CH1101126
3
Khóa luận môn học: Khai phá dữ liệu
CHƯƠNG 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1. Giới thiệu về khai phá dữ liệu
Sự phát triển nhanh chóng các ứng dụng công nghệ thông tin và Internet
vào nhiều lĩnh vực đời sống xã hội, quản lý kinh tế, y học, khoa học kỹ thuật,
đã tạo ra nhiều cơ sở dữ liệu khổng lồ, có thể đơn cử vài ví dụ tiêu biểu như
CSDL siêu thị Walmart (Mỹ) chứa hơn 20 triệu giao tác bán hàng; CSDL nhân
khẩu Tp. HCM với hơn 7,5 triệu nhân khẩu. Để khai phá hiệu quả nguồn thông
tin từ các CSDL lớn hỗ trợ tiến trình ra quyết định, bên cạnh các khai thác thông
tin truyền thống, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và
phần mềm mới hỗ trợ tiến trình khám phá, phân tích tổng hợp thông tin.
Theo đánh giá của IBM, các phương pháp khai phá thông tin truyền thống
chỉ thu được khoảng 80% thông tin từ CSDL, phần còn lại gồm các thông tin
mang tính khái quát, thông tin có tính quy luật vẫn còn tiềm ẩn trong dữ liệu.
Lượng thông tin này tuy nhỏ nhưng là thông tin cốt lõi và cần thiết cho tiến trình
ra quyết định.
Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong CSDL. Cụ
thể hơn, đó là tiến trình trích lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn,
chưa biết nhưng hữu ích từ CSDL lớn.
Khai phá dữ liệu là tiến trình khái quát các sự kiện rời rạc trong dữ liệu
thành các tri thức mang tính khái quát, tính quy luật hỗ trợ tích cực cho các tiến
trình ra quyết định.
Nguồn dữ liệu phục vụ cho khai phá dữ liệu có thể là các CSDL lớn hay
các kho dữ liệu có cấu trúc hoặc không có cấu trúc. KPDL chỉ thực sự phát huy

tác dụng trên các CSDL lớn, nơi mà nó có khả năng diễn dịch và trực giác của
con người cũng như các kỹ thuật truyền thống không thể thực hiện nỗi hoặc nếu
thực hiện được nhưng hiệu quả không cao.
Có thể chia khai phá dữ liệu thành hai dạng chính: khai phá dữ liệu
(KPDL) theo hướng kiểm tra và KPDL theo hướng khám phá. Trong khai phá
dữ liệu theo hướng kiểm tra, người dùng đề xuất giả thiết, hệ thống kiểm tra tính
đúng đắng của giả thiết; KPDL theo hướng kiểm tra bao gồm: truy vấn, báo cáo,
phân tích đa chiều, phân tích thống kê,… Ngược lại, KPDL theo hướng khám
phá sẽ tìm kiếm các tri thức tiềm ẩn trong CSDL bằng cách tiến hành xem xét tất
cả các giả thiết khả dĩ. Do không gian tìm kiếm lớn, nên rất nhiều các heuristic
đã được đề xuất nhằm nâng cao hiệu suất của các giải thuật tìm kiếm.
Ngày nay, khi công thu thập dữ liệu tự động và công nghệ lưu trữ dữ liệu
ngày càng hoàn thiện giúp con người tạo lập và quản lý một lượng dữ liệu
khổng lồ trong các CSDL, kho dữ liệu (data Warehouse) thì nhu cầu nắm bắt dữ
liệu, trích rút thông tin trở thành cấp thiết và có ý nghĩa. Mặt khác, với nhu cầu
ngày càng cao hơn, con người không bằng lòng với những dữ liệu đơn giản thu
được từ các kỹ thuật trước đây. Từ nhu cầu về những sự kiện rời rạc trong lĩnh
vực ứng dụng, nay phát sinh nhu cầu nắm bắt tri thức về các mối quan hệ giữa
Nguyễn Văn Quang - CH1101126
4
Khóa luận môn học: Khai phá dữ liệu
chúng, xa hơn nữa là phát hiện những quy luật trong lĩnh vực đó. KPDL ra đời
nhằm đáp ứng các nhu cầu cấp thiết đó.
2. Lịch sử phát triển khai phá dữ liệu
Chúng ta có thể điểm qua lịch sử phát triển của các kỹ thuật, công nghệ
lưu trữ và khai phá dữ liệu như sau:
- Những năm 1960: xuất hiện CSDL theo mô hình mạng là mô hình phân
cấp.
- Những năm 1970: thiết lập nền tảng lý thuyết cho CSDL quan hệ, và các
hệ quản trị CSDL quan hệ.

- Những năm 1980: hoàn thiện lý thuyết về CSDL quan hệ và các hệ quản
trị CSDL quan hệ, xuất hiện các hệ quản trị CSDL cao cấp (hướng đối tượng,
suy diễn, ) và hệ quản trị CSDL hướng ứng dụng trong lĩnh vực không gian,
khoa học, công nghiệp, nông nghiệp, địa lý,
- Những năm 1990-2000: phát triển khai phá dữ liệu và kho dữ liệu, CSDL
đa phương tiện, và CSDL Web.
Khai phá dữ liệu là một công đoạn trong tiến trình lớn hơn là khám phá tri
thức từ CSDL. KPDL mang tính trực giác, cho phép thu được những hiểu biết rõ
ràng và sâu sắc hơn, vượt xa kho dữ liệu, đồng thời giúp phát hiện những xu thế
phát triển từ những thông tin quá khứ, cũng như cho phép đề xuất các dự báo
mang tính thống kê, gom cụm và phân loại dữ liệu. Kho dữ liệu điễn hình trong
những doanh nghiệp cho phép người dùng hỏi và trả lời những câu hỏi như
“Doanh số bán ra là bao nhiêu theo khu vực, theo nhân viên bán hàng của quý
III năm 2012 ?”. Trong khi đó, KPDL cho phép người ra quyết định kinh doanh
và trả lời cho những câu hỏi như là “Ai là khách hàng chính yếu của công ty đối
với mặt hàng cụ thể” hoặc “Dòng sản phẩm nào sẽ bán trong khu vực này và ai
sẽ mua chúng, dựa vào việc bán những sản phẩm tương tự ở khu vực đó”. Vị trí
của KPDL được thể hiện qua sơ đồ (xem hình 1)
Nguyễn Văn Quang - CH1101126
5
Hình 1: Vị trí khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
3. Tại sao dùng khai phá dữ liệu
Khai phá dữ liệu là cần thiết đối với người dùng vì những lý do sau:
- Ngày càng có nhiều dữ liệu được lưu trữ trong các CSDL, kho dữ liệu và
hình thành một “mỏ vàng dữ liệu” chứa đầy các thông tin chiến lược mà hệ quản
trị CSDL thông thường không thể phát hiện và quản trị được chúng.
- CSDL phát triển rất nhanh cả về kích thước lẫn số lượng, không xét
những thông tin mang tính sự kiện được lưu trữ trong CSDL, những thông tin
này được suy diễn từ nó cũng hết sức thú vị. Tuy nhiên với các quan hệ có số

lượng khổng lồ các bản ghi (record) và có nhiều trường (feild), việc duyệt hàng
triệu bảng ghi hay hàng trăm trường tin để tìm ra các mẫu và các quy luật là một
thách thức và trở ngại thật sự đối với các nhà phân tích dữ liệu.
- Không phải người nào cũng là nhà thống kê hay nhà phân tích dữ liệu
chuyên nghiệp.
- Sử dụng các trường hợp tìm kiếm nhưng chưa xác lập rõ hoặc chưa mô tả
được các điều kiện tìm kiếm. Nếu người dùng biết họ đang tìm kiếm gì thì
dùngSQL, nhưng nếu người dùng chỉ có một ý tưởng không rõ ràng, hoặc một
cảm nhận nào đó thì họ nên dùng khai phá dữ liệu.
Khai phá dữ liệu là một công cụ hiệu quả trong các lĩnh vực:
- Sử dụng dữ liệu để xây dựng các mô hình dự báo:
o Khả năng dự báo tiềm ẩn trong dữ liệu.
o Gợi ý về các chiều và các nhóm dữ liệu có khả năng chứa các tri
thức hữu ích.
- Tóm tắc và báo cáo rõ ràng:
o Tự động tìm những phân đoạn trong dữ liệu.
o Tìm ra những phân đoạn mà nhà phân tích chưa biết hoặc có hiểu
biết chưa tường tận.
- Cung cấp cơ chế hỗ trợ ra quyết định:
o Dự báo.
o Mô hình hóa.
4. Quá trình khám phá tri thức từ cơ sở dữ liệu
Quá trình khám phá tri thức là một chuỗi lặp có thể chia thành các bước
như sau:
- Làm sạch dữ liệu (data cleaning): 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).
- Chọn lựa 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 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.
Nguyễn Văn Quang - CH1101126
6
Khóa luận môn học: Khai phá dữ liệu
- Chuyển đổi dữ liệu (data transformation): 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.
- Đánh giá mẫu (pattern evaluation): là 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): là 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. (xem hình 2)
5. Khai phá dữ liệu (data mining)
Khai phá dữ liệu là một quá trình trích xuất tri thức từ lượng lớn dữ liệu.
Một quá trình không dễ trích xuất thông tin ẩn, hữu ích, chưa được biết trước từ
dữ liệu.
Các thuật ngữ thường được dùng: knowledge discovery/mining in
data/databases (KDD), knowledge extraction, data/pattern analysis, data
archeology, data dredging, information harvesting, business intelligence.
Lượng lớn dữ liệu sẵn có để khai phá: bất kỳ loại dữ liệu được lưu trữ hay
tạm thời, có cấu trúc hay bán cấu trúc hay phi cấu trúc.
Dữ liệu được lưu trữ gồm: các tập tin truyền thống (flat files); các cơ sở
dữ liệu quan hệ (relational databases) hay quan hệ đối tượng (object relational
databases); các cơ sở dữ liệu giao tác (transactional databases) hay kho dữ liệu
(data warehouses); các cơ sở dữ liệu hướng ứng dụng như: cơ sở dữ liệu không
gian (spatial databases), cơ sở dữ liệu thời gian (temporal databases), cơ sở dữ
liệu không thời gian (spatio-temporal databases), cơ sở dữ liệu chuỗi thời gian

Nguyễn Văn Quang - CH1101126
7
Hình 2. Quá trình khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
(time series databases), cơ sở dữ liệu văn bản (text databases), cơ sở dữ liệu đa
phương tiện (multimedia databases); các kho thông tin: the World Wide Web.
Tri thức đạt được từ quá trình khai phá: mô tả lớp haykhái niệm; mẫu
thường xuyên, các mối quan hệ kết hợp hay tương quan; mô hình phân loại và
dự đoán; mô hình gom cụm; các phần tử biên.
Xu hướng hay mức độ thường xuyên của các đối tượng có hành vi thay
đổi theo thời gian.
Tri thức đạt được có thể có: tính mô tả hay dự đoán tùy thuộc vào quá
trình khai phá cụ thể; cấu trúc, bán cấu trúc, hoặc phi cấu trúc; có thể được hay
không được người dùng quan tâm cho ra kết quả các độ đo đánh giá tri thức đạt
được; có thể được dùng trong việc hỗ trợ ra quyết định, điều khiển quy trình,
quản lý thông tin, xử lý truy vấn,
Khai phá dữ liệu là một lĩnh vực liên ngành, nơi hội tụ của nhiều học
thuyết và công nghệ.
Khai phá dữ liệu và công nghệ cơ sở dữ liệu:
- Khả năng đóng góp của công nghệ cơ sở dữ liệu là: công nghệ cơ sở dữ
liệu cho việc quản lý dữ liệu được khai phá. Các hệ cơ sở dữ liệu có khả năng xử
lý hiệu quả lượng lớn dữ liệu với các cơ chế phân trang (paging) và hoán chuyển
(swapping) dữ liệu vào hay ra bộ nhớ chính. Các hệ cơ sở dữ liệu hiện đại có
khả năng xử lý nhiều loại dữ liệu phức tạp (spatial, temporal, spatiotemporal,
multimedia, text, Web, …). Các chức năng khác (xử lý đồng thời, bảo mật, hiệu
năng, tối ưu hóa, …) của các hệ cơ sở dữ liệu đã được phát triển tốt.
- Thực trạng đóng góp của công nghệ cơ sở dữ liệu là: các hệ quản trị cơ sở
dữ liệu (DBMS) hỗ trợ khai phá dữ liệu như: Oracle Data Mining (Oracle 9i,
10g, 11g, 11gR2), các công cụ khai phá dữ liệu của Microsoft (MS SQL Server
2000, 2005, 2008, 2012), Intelligent Miner (IBM). Các hệ cơ sở dữ liệu qui nạp

(inductive database) hỗ trợ khám phá tri thức. Chuẩn SQL/MM 6: Data Mining
của ISO/IEC 13249 - 6:2006 hỗ trợ khai phá dữ liệu. Đặc tả giao diện SQL cho
các ứng dụng và dịch vụ khai phá dữ liệu từ các cơ sở dữ liệu quan hệ.
6. Các kỹ thuật khai phá dữ liệu
- Kỹ thuật khai phá 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 trên 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 phá 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), (Hình 3)
Nguyễn Văn Quang - CH1101126
8
Khóa luận môn học: Khai phá dữ liệu
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
6.1. 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 (Hình 4).
a) Phân lớp dữ liệu:
Nguyễn Văn Quang - CH1101126
9
Hình 3. Các kỹ thuật khai phá dữ liệu
Hình 4. Phân cụm dữ liệu
Khóa luận môn học: Khai phá 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
mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm hai bước:

- Bước 1: Một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu
dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc
tính gọi là thuộc tính lớp. Các lớp dữ liệu này còn được gọi là lớp dữ liệu huấn
luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được
xác định trước khi xây dựng mô hình.
- Bước 2: Sử dụng mô hình để phân lớp dữ liệu. Trước hết, chúng ta phải
tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ
được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai.
(Hình 5)
6.2. Phương pháp hồi quy:
Phương pháp hồi quy khác với phân lớp dữ liệu ở chỗ: hồi quy dùng để
dự đoán về các giá trị liên tục còn phân lớp dữ liệu chỉ dùng để dự đoán về các
giá trị rời rạc.
Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có
giá trị thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, ví dụ
như: khả năng đánh giá tử vong của bệnh nhân khi biết các kết quả xét nghiệm;
chẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu
quảng cáo.
6.3. Khai phá luật kết hợp:
Phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị 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à luật kết
hợp tìm được. Chẳng hạn, phân tích cơ sở dữ liệu bán hàng nhận được thông tin
về những khách hàng mua máy tính có khuynh hướng mua phần mềm quản lý
tài chính trong cùng lần mua được miêu tả trong luật kết hợp sau: “Máy
tính=>Phần mềm quản lý tài chính” (Độ hỗ trợ: 2%, độ tin cậy: 60%)
Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật.
Nguyễn Văn Quang - CH1101126
10
Hình 5. Phân lớp dữ liệu
Khóa luận môn học: Khai phá dữ liệu

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 (min support)
- 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 (min confidence).
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, …
 Năm thành tố cơ bản để đặc tả một kỹ thuật khai phá dữ liệu:
- Dữ liệu cụ thể sẽ được khai phá (task-relevant data): phần dữ liệu từ các
dữ liệu nguồn được quan tâm. Tương ứng với các thuộc tính hay chiều dữ liệu
được quan tâm bao gồm: tên kho dữ liệu/cơ sở dữ liệu, các bảng dữ liệu hay các
khối dữ liệu, các điều kiện chọn dữ liệu, các thuộc tính hay chiều dữ liệu được
tâm, các tiêu chí gom nhóm dữ liệu.
- Loại tri thức sẽ đạt được (kind of knowledge): đặc trưng hóa dữ liệu, phân
biệt hóa dữ liệu, mô hình phân tích kết hợp hay tương quan, mô hình phân lớp,
mô hình dự đoán, mô hình gom cụm, mô hình phân tích phần tử biên, mô hình
phân tích tiến hóa.
- Tri thức nền (background knowledge): tương ứng với lĩnh vực cụ thể sẽ
được khai phá như hướng dẫn quá trình khám phá tri thức, hỗ trợ khai phá dữ
liệu ở nhiều mức trừu tượng khác nhau. Đánh giá các mẫu được tìm thấy, bao
gồm: các phân cấp ý niệm, niềm tin của người sử dụng về các mối quan hệ của
dữ liệu.
- Các độ đo (interestingness measures): thường đi kèm với các ngưỡng giá
trị (threshold); dẫn đường cho quá trình khai phá hoặc đánh giá các mẫu được
tìm thấy; tương ứng với loại tri thức sẽ đạt được và do đó, tương ứng với kỹ

thuật khai phá dữ liệu cụ thể sẽ được thực thi; kiểm tra tính đơn giản
(simplicity), tính chắc chắn (certainty), tính hữu dụng (utility), tính mới
(novelty).
- Các kỹ thuật biểu diễn tri thức/trực quan hóa mẫu (pattern visualization
and knowledge presentation): là xác định dạng các mẫu/tri thức được tìm thấy
để thể hiện đến người sử dụng, bao gồm: luật (rules), bảng (tables), báo cáo
(reports), biểu đồ (charts), đồ thị (graphs), cây (trees), và khối (cubes).
 Bốn thành phần cơ bản của một giải thuật khai phá dữ liệu:
- Cấu trúc mẫu hay cấu trúc mô hình (model or pattern structure): mô hình
là mô tả của tập dữ liệu, mang tính toàn cục ở mức cao. Mẫu là đặc điểm (đặc
trưng) của dữ liệu, mang tính cục bộ, chỉ cho một vài bản ghi hoặc đối tượng
Nguyễn Văn Quang - CH1101126
11
Khóa luận môn học: Khai phá dữ liệu
hay vài biến. Cấu trúc biểu diễn các dạng chức năng chung với các thông số
chưa được xác định trị. Cấu trúc mô hình là một tóm tắt toàn cục về dữ liệu.
Ví dụ: Y = aX + b là một cấu trúc mô hình và Y = 3X + 2 là một mô hình
cụ thể được định nghĩa dựa trên cấu trúc này.
Cấu trúc mẫu là những cấu trúc liên quan một phần tương đối nhỏ của dữ
liệu hay của không gian dữ liệu.
Ví dụ: p(Y>y1|X>x1) = p1 là một cấu trúc mẫu và p(Y>5|X>10) = 0.5 là
một mẫu được xác định dựa trên cấu trúc này.
- Hàm tỉ số (score function): hàm tỉ số là hàm xác định một cấu trúc mô
hình haymẫu đáp ứng tập dữ liệu đã cho tốt ở mức độ nào đó. Cho biết liệu một
mô hình có tốt hơn các mô hình khác hay không. Hàm tỉ số không nên phụ thuộc
nhiều vào tập dữ liệu, không nên chiếm nhiều thời gian tính toán. Một vài hàm tỉ
số thông dụng như: likelihood, sum of squared errors, misclassification rate,
- Phương pháp tìm kiếm và tối ưu hóa (optimization and search method):
Mục tiêu của phương pháp tìm kiếm và tối ưu hóa là xác định cấu trúc và giá trị
các thông số đáp ứng tốt nhất hàm tỉ số từ dữ liệu sẵn có.

+ Tìm kiếm các mẫu và mô hình: là không gian trạng thái, tập rời rạc các
trạng thái. Bài toán tìm kiếm được bắt đầu tại một node (trạng thái) cụ thể, di
chuyển qua không gian trạng thái để tìm thấy node tương ứng với trạng thái đáp
ứng tốt nhất hàm tỉ số.
+ Phương pháp tìm kiếm: chiến lược tham lam, có dùng heuristics, chiến
lược nhánh-cận.
+ Tối ưu hóa thông số.
- Chiến lược quản lý dữ liệu (data management strategy): dữ liệu được khai
phá ít hay toàn bộ được xử lý đồng thời trong bộ nhớ chính; hỗ trợ cách dữ liệu
được lưu trữ, đánh chỉ mục, và truy xuất. Giải thuật khai phá dữ liệu hiệu quả
(efficiency) và có tính co giãn (scalability) với dữ liệu được khai phá, và công
nghệ cơ sở dữ liệu.
7. Các quy trình khai phá dữ liệu
- Quy trình khai phá dữ liệu là một chuỗi lặp và tương tác gồm các bước
bắt đầu với dữ liệu thô (raw data) và kết thúc với tri thức (knowledge of interest)
đáp ứng được sự quan tâm của người sử dụng.
- Sự cần thiết của một quy trình khai phá dữ liệu là cách thức tiến hành
(hoạch định và quản lý) dự án khai phá dữ liệu có hệ thống; đảm bảo nỗ lực
dành cho một dự án khai phá dữ liệu được tối ưu hóa. Việc đánh giá và cập nhật
các mô hình trong dự án được diễn ra liên tục.
Các tiến trình khai phá dữ liệu:
Nguyễn Văn Quang - CH1101126
12
Khóa luận môn học: Khai phá dữ liệu
Nguyễn Văn Quang - CH1101126
13
Chọn các giải thuật KPDL
KPDL: Tìm kiếm tri thức
Đánh giá mẫu tìm được
Biểu diễn tri thức

Sử dụng các tri thức vừa khám phá
Nghiên cứu lĩnh vực
Tạo tập dữ liệu đầu vào
Tiền xử lý/làm sạch, mã hóa
Rút gọn/chiều
Chọn tác vụ khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
Tiến trình KDD tiêu biểu:
8. Các hệ thống khai phá dữ liệu (data mining systems)
Hệ thống khai phá dữ liệu được phát triển dựa trên khái niệm rộng của
khai phá dữ liệu. Đó là một quá trình khám phá tri thức được quan tâm từ lượng
lớn dữ liệu trong các cơ sở dữ liệu, kho dữ liệu, hay các kho thông tin khác.
Các thành phần chính như: Database, Data warehouse, World Wide Web,
và Information repositories. Thành phần này là các nguồn dữ liệu/thông tin sẽ
được khai phá. Trong những tình huống cụ thể, thành phần này là nguồn nhập
của các kỹ thuật tích hợp và làm sạch dữ liệu.
o Database hay data warehouse server: là thành phần chịu trách nhiệm
chuẩn bị dữ liệu thích hợp cho các yêu cầu khai phá dữ liệu.
o Nowledge base: là thành phần chứa tri thức miền, được dùng để hướng
dẫn quá trình tìm kiếm, đánh giá các mẫu kết quả được tìm thấy.
 Tri thức miền có thể là các phân cấp khái niệm, niềm tin của người sử
dụng, các ràng buộc hay các ngưỡng giá trị, siêu dữ liệu, …
o Data mining engine: là thành phần chứa các khối chức năng thực hiện các
tác vụ khai phá dữ liệu
o Pattern evaluation module: thành phần này làm việc với các độ đo (và các
ngưỡng giá trị) hỗ trợ tìm kiếm và đánh giá các mẫu sao cho các mẫu
được tìm thấy là những mẫu được quan tâm bởi người sử dụng.
 Thành phần này có thể được tích hợp vào thành phần Data mining engine.
Nguyễn Văn Quang - CH1101126
14

Khóa luận môn học: Khai phá dữ liệu
o User interface: thành phần hỗ trợ sự tương tác giữa người sử dụng và hệ
thống khai phá dữ liệu. Người sử dụng có thể chỉ định câu truy vấn hay
tác vụ khai phá dữ liệu, có thể được cung cấp thông tin hỗ trợ việc tìm
kiếm, thực hiện khai phá dữ liệu sâu hơn thông qua các kết quả khai phá
trung gian, cũng có thể xem các lược đồ cơ sở dữ liệu/kho dữ liệu, các cấu
trúc dữ liệu; đánh giá các mẫu khai phá được; trực quan hóa các mẫu này
ở các dạng khác nhau.
Những đặc điểm được dùng để khảo sát một hệ thống khai phá dữ liệu
bao gồm:
- Kiểu dữ liệu.
- Các vấn đề hệ thống.
- Nguồn dữ liệu.
- Các tác vụ và phương pháp luận khai phá dữ liệu.
- Vấn đề gắn kết với các hệ thống kho dữ liệu hay cơ sở dữ liệu.
- Khả năng co giãn dữ liệu.
- Các công cụ trực quan hóa.
- Ngôn ngữ truy vấn khai phá dữ liệu và giao diện đồ họa cho người dùng.
Một số hệ thống khai phá dữ liệu: Intelligent Miner (IBM), Microsoft data
mining tools (Microsoft SQL Server 2000/2005/2008/2012), Oracle Data
Mining (Oracle 9i/10g/11g/11gR2), Enterprise Miner (SAS Institute),
Nguyễn Văn Quang - CH1101126
15
Hình 6. Kiến trúc của một hệ thống khai phá dữ liệu
Khóa luận môn học: Khai phá dữ liệu
9. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu là một hướng tiếp cận mới đã 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ó. KPDL được ứng dụng rộng rãi trong rất nhiều lĩnh vực, sau đây là
một số ứng dụng điễn hình:

- Ngân hàng: xây dựng mô hình dự báo rủi ro tín dụng, tìm kiếm tri thức,
quy luật thị trường chứng khoán và đầu tư bất động sản.
- Thương mại điện tử: công cụ tìm hiểu, định hướng, thúc đẩy, giao tiếp với
khách hàng. Phân tích khách hàng duyệt web. Phân tích hành vi mua sắm trên
mạng và cho biết thông tin tiếp thị phù hợp với loại khách hàng trong một phân
khu thị trường nhất định.
- Công nghệ sinh học và dược phẩm: xây dựng công cụ KPDL trực quan
cho phép phát hiện sự hiện diện của dược chất, phân tích dữ liệu di truyền.
- Nhân sự: giúp nhà tuyển dụng chọn ứng viên thích hợp nhất theo nhu cầu
của công ty. Phát hiện giả mạo thẻ trong lĩnh vực viễn thông. Phát hiện thẻ tín
dụng giả trên mạng và công cụ hữu ích cho dịch vụ quản lý rủi ro trong thương
mại điện tử. pháp hiện xâm nhập trái phép.
- Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision
support).
- Text mining and Web mining,
- Trong bảo hiểm (insurance),
- Trong khoa học (science),
Nguyễn Văn Quang - CH1101126
16
Khóa luận môn học: Khai phá dữ liệu
CHƯƠNG 2
KHAI PHÁ LUẬT KẾT HỢP
1. Tổng quan về 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 cũng như quan trọng nhất
trong việc khai phá 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

Items trong trong các CSDL giao tác (transaction database) hoặc trong những
kho dữ liệu (data warehouse).
Hiện nay các công ty phải lưu một số lượng dữ liệu bán hàng khổng lồ.
Một bản ghi trong CSDL này chứa các thông tin về ngày mua, bán hàng, … Từ
CSDL bán hàng, chúng ta có thể tìm ra các mối quan hệ giữa các cặp thuộc tính
– giá trị thuộc tính. Một luật kết hợp tiêu biểu:
Ví dụ: “78% khách hàng mà mua sữa hộp Vinamilk thì mua trà Lipton.
Các công ty thành công thường tìm kiếm những luật như vậy để biết được
xu hướng của thị trường, từ đó đưa ra những chương trình và chiến lược nhập
hàng và bố trí các mặt hàng,….phù hợp.
1.1. Quá trình khai phá luật kết hợp
Ví dụ: Phân tích bán hàng trong siêu thị
1.2. Các khái niệm cơ bản
Phần tử (Item): là các phần tử, mẫu, đối tượng đang được quan tâm, như J
= {I1, I2, …, Im}: tập tất cả m phần tử có thể có trong tập dữ liệu.
Tập phần tử (Itemset): là tập hợp các items, một itemset có k items gọi là
k-itemset.
Giao dịch (Transaction): là lần thực hiện tương tác với hệ thống (ví dụ:
giao dịch “khách hàng mua hàng”). Liên hệ với một tập T gồm các phần tử được
giao dịch.
Nguyễn Văn Quang - CH1101126
17
Khóa luận môn học: Khai phá dữ liệu
Sự kết hợp (Association) và luật kết hợp (association rule): là sự kết hợp
các phần tử cùng xuất hiện với nhau trong một hay nhiều giao dịch.Thể hiện mối
liên hệ giữa các phần tử hay các tập phần tử.
Luật kết hợp: qui tắc kết hợp có điều kiện giữa các tập phần tử. Thể hiện
mối liên hệ (có điều kiện) giữa các tập phần tử. Ví dụ cho A và B là các tập phần
tử, luật kết hợp giữa A và B là A à B. B xuất hiện trong điều kiện A xuất hiện.
Hỗ trợ (Support): là độ đo đo tần số xuất hiện của các phần tử hay tập

phần tử. Ngưỡng hỗ trợ tối thiểu (Minimum support threshold), giá trị support
nhỏ nhất được chỉ định bởi người dùng.
Độ tin cậy (Confidence): là độ đo đo tần số xuất hiện của một tập phần tử
trong điều kiện xuất hiện của một tập phần tử khác. Ngưỡng tin cậy tối thiểu
(Minimum confidence threshold), giá trị confidence nhỏ nhất được chỉ định bởi
người dùng.
Tập phần tử phổ biến (Frequent itemset): là tập phần tử có support thỏa
minimum support threshold. Ví dụ: cho A là một itemset, A là frequent itemset
iff support(A) >= minimum support threshold.
Luật kết hợp mạnh (Strong association rule) là luật kết hợp có support và
confidence thỏa minimum support threshold và minimum confidence threshold.
Ví dụ: cho luật kết hợp AàB giữa A và B, A và B là itemsets
AàB là strong association rule iff support(AàB) >= minimum support
threshold và confidence(AàB) >= minimum confidence threshold.
1.3. Phân loại luật kết hợp
Luật kết hợp luận lý (Boolean association rule): luật liên quan đến mối kết
hợp giữa sự có xuất hiện và không xuất hiện của các phần tử (ví dụ “có mua A"
hoặc “không có mua A")
Ví dụ:
mua=SQLServer, mua=DMBook ⇒ mua=DBMiner , có [support=2%,
confidence=60%]
mua(x, "SQLServer") ^ mua(x, "DMBook") à mua(x, "DBMiner"), có
[support=0.2%, confidence=60%]
Luật kết hợp đơn chiều (Single-dimensional association rule): luật chỉ liên
quan đến các phần tử/thuộc tính của một chiều dữ liệu.
Ví dụ: Buys(X, “computer”) à Buys(X, financial_management_software”)
Luật kết hợp đa chiều (multidimensional association rule): luật liên quan
đến các phần tử/thuộc tính của nhiều hơn một chiều.
Ví dụ: Age(X, “30 39”) à Buys(X, “computer”).
Luật kết hợp đơn mức (Single-level association rule): luật chỉ liên quan

đến các phần tử/thuộc tính ở một mức trừu tượng. Ví dụ:
Age(X, “30 39”) à Buys(X, “computer”)
Age(X, “18 29”) à Buys(X, “camera”)
Nguyễn Văn Quang - CH1101126
18
Khóa luận môn học: Khai phá dữ liệu
Luật kết hợp đa mức (multilevel association rule): luật liên quan đến các
phần tử/thuộc tính ở các mức trừu tượng khác nhau. Ví dụ:
Age(X, “30 39”) à Buys(X, “laptop computer”)
Age(X, “30 39”) à Buys(X, “computer”)
Luật kết hợp (Association rule): luật kết hợp mạnh AàB đáp ứng yêu cầu
ngưỡng hỗ trợ tối tiểu và ngưỡng tin cây tối tiểu (minimum support threshold và
minimum confidence threshold).
Luật tương quan thống kê (Correlation rule): luật kết hợp mạnh A à B
đáp ứng yêu cầu về sự tương quan thống kê giữa A và B.
2. Biểu diễn luật luật kết hợp
Dạng luật: AàB [support, confidence]
Cho trước minimum support threshold (min_sup), minimum confidence
threshold (min_conf)
A và B là các itemsets
Frequent itemsets/subsequences/substructures Itemset/subsequence/
substructure X là frequent nếu support(X) >= min_sup. Trong đó: Itemsets: tập
các items, Subsequences: chuỗi tuần tự các events/items, Substructures: các tiểu
cấu trúc (graph, lattice, tree, sequence, set, …)
Closed frequent itemsets
Một itemset X closed trong J nếu không tồn tại tập cha thực sự Y nào
trong J có cùng support với X.
X ⊆ J, X closed iff ∀ Y ⊆ J và X ⊂ Y: support(Y) <> support (X).
X là closed frequent itemset trong J nếu X là frequent itemset và closed
trong J.

Maximal frequent itemsets: một itemset X là maximal frequent itemset
trong J nếu không tồn tại tập cha thực sự Y nào trong J là một frequent itemset.
X ⊆ J, X là maximal frequent itemset iff ∀ Y ⊆ J và X ⊂ Y: Y không phải
là một frequent itemset.
Constrained frequent itemsets: frequent itemsets thỏa các ràng buộc do
người dùng định nghĩa.
Approximate frequent itemsets: frequent itemsets dẫn ra support (xấp xỉ)
cho các frequent itemsets sẽ được khai phá.
Top-k frequent itemsets: frequent itemsets có nhiều nhất k phần tử với k
do người dùng chỉ định.
Luật kết hợp luận lý (Boolean), đơn mức (single-level), đơn chiều (single-
dimensional) giữa các tập phần tử phổ biến: AàB [support, confidence]
A và B là các frequent itemsets ta có:
- Support(AàB) = Support(A U B) >= min_sup
- Confidence(AàB) = Support(A U B)/Support(A) = P(B|A) >= min_conf
Nguyễn Văn Quang - CH1101126
19
Khóa luận môn học: Khai phá dữ liệu
3. Khám phá các luật kết hợp dựa trên ràng buộc
Khám phá các luật kết hợp dựa trên ràng buộc là hướng dẫn quá trình khai
phá mẫu (patterns) và luật (rules). Giới hạn không gian tìm kiếm dữ liệu trong
quá trình khai phá, các dạng ràng buộc:
- Ràng buộc kiểu tri thức (knowledge type constraints): luật kết hợp hay
tương quan.
- Ràng buộc dữ liệu (data constraints): nhữn câu truy vấn SQL
- Ràng buộc mức hay chiều (level or dimension constraints): chiều (thuộc
tính) dữ liệu hay mức trừu tượng hay ý niệm.
- Ràng buộc liên quan đến độ đo (interestingness constraints): ngưỡng của
các độ đo.
- Ràng buộc liên quan đến luật (rule constraints): dạng luật sẽ được khám

phá.
Khám phá luật (rules) hay tập phần tử phổ biến (frequent itemsets) thỏa
các ràng buộc, có hai cách tiếp cận:
- Cách tiếp cận trực tiếp: áp dụng các giải thuật truyền thống, kiểm tra các
ràng buộc cho từng kết quả đạt được. Nếu thỏa ràng buộc thì trả về kết
quả sau cùng.
- Cách tiếp cận dựa trên tính chất của các ràng buộc: phân tích toàn diện
các tính chất của các ràng buộc. Kiểm tra các ràng buộc càng sớm càng
tốt trong quá trình khám phá các tập phổ biến hay các luật (rules or
frequent itemsets). Không gian dữ liệu được thu hẹp càng sớm càng tốt.

Nguyễn Văn Quang - CH1101126
20
Khóa luận môn học: Khai phá dữ liệu
CHƯƠNG 3
TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP
1. Thuật toán AIS
Thuật toán do Agrwal đề nghị năm 1993. Thuật toán này chú trọng khai
phá luật kết hợp có dạng XàY, với Y là tập hợp chỉ bao gồm 1 tính chất (tập
hợp 1 phần tử). Thuật toán tìm cách xây dựng dần dần các tập ứng cử viên cho
“chức vụ” tập hợp xuất hiện σ – thường xuyên. Với cách đánh số thứ tự từ điển
cho từng tính chất, việc bổ sung phần tử cho tập ứng cử viên tránh được trùng
lặp, do vậy tiết kiệm tối đa thời gian tính toán.
Số lượng các tập ứng cử viên quá nhiều có thể gây ra hiện tượng tràn bộ
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
giao dịch cùng với tập hợp ứng cử viên. Agrawal đã chỉ ra, Thuật toán này
Nguyễn Văn Quang - CH1101126
21
Khóa luận môn học: Khai phá dữ liệu
không những không có phương án quản lý bộ nhớ mà nó còn giả định nhét toàn
bộ tập hợp ứng cử viên của bước trước vào bộ nhớ để bước sau tiện bề sử dụng.

Sarawagi đã chỉ ra Thuật toán này không hiệu quả.
 Thuật toán SETM(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. L1’={các tập mục phổ biến cùng các TID của nó được sắp xếp theo
TID};
3. for (k=2; Luật kết hợpk-1 ≠ ∅ ; k++ ) do begin
4. Ck = ∅;
5. forall các giao dịch t ∈ D do begin
6. Lt = (l ∈ L’k-1 | l.TID = t.TID); // các tập có (k - l) mục phổ biến trong
giao dịch t
7. forall các tập mục phổ biến lt ∈ Lt do begin
8. Ct = tăng lt thêm một mục có trong giao dịch t; //Các ứng cử viên có
trong t
9. C’k +={<t.TID, c>| c ∈ Ct};
10. end
11. end
12. Sort C’k theo các tập mục;
13. delete các mục c ∈ C’k có c.count<minsup đưa vào L’k ;
14. Lk ={<l.itemset, countof l in L’k > | l ∈ Lk'}; //kết hợp với bước 13
15. Sort L’k theo TID;
16. end
17. Trả lời = ∪k Lk ;
3. Thuật toán Apriori
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
Nguyễn Văn Quang - CH1101126
22
Khóa luận môn học: Khai phá dữ liệu
- 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
độ tin cậy (Confidence) của nó > =min_conf
Chẳn hạn với I= {A1,A2,A5},các tập con của I: {A1}, {A2}, {A5}, A1,A2},
{A1,A5},{A2,A5}sẽ có các luật sau:
{A1} => {A2,A5}, {A2} =>{A1,A5},{A5} =>{A1,A2}

{A1,A2} =>{A5}, {A1,A5} =>{A2}, {A2,A5} => {A1}
3.2. Thuật toán Apriori (Pseudo code)
- Input: CSDL D, minsup.
- Output: Tập các tập mục phổ biến.
Đầu tiên đếm số items và xác định L
1

Bước tiếp theo gồm 2 phần chính:
* C
k
tạo được bằng các kết L
k-1
với chính nó.
* Những tập kích thước (k-1) không phổ biến không thể là tập con của tập
phổ biến kích thước k.
1) L
1
= {large 1-itemsets};
2) for ( k = 2; L
k-1
≠ ∅; k++ ) do begin
3) C
k
= apriori-gen(L
k-1
); // Ứng viên mới
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
Nguyễn Văn Quang - CH1101126
23
Khóa luận môn học: Khai phá dữ liệu
TDB Items Itemset Sup Itemsets Sup

1 A,C,D C1 {A} 2 L1 {A} 2
2 B,C,E 1st scan {B} 3 {B} 3
3 A,B,C,E {C} 3 {C} 3
4 B,E {D} 1 {E} 3
{E} 3
Itemsets Sup Itemsets Sup Itemsets
{A,C} 2 L2 {A,B} 1 C2 {A,B}
{B,C} 2 {A,C} 2 {A,C}
{B,E} 3 {A,E} 1 2nd scan {A,E}
{C,E} 2 {B,C} 2 {B,C}
{B,E} 3 {B,E}
{C,E} 2 {C,E}
Itemsets C3 Itemsets Sup L3 Itemsets Sup
{A,B,C} {A,B,C} 1 {B,C,E} 2
{A,B,E} 3th scan {A,B,E} 1
{A,C,E} {A,C,E} 1
{B,C,E} {B,C,E} 2
Ta có frequent itemsets I ={B,C,E}, với min_conf =80% ta có 2 luật kết hợp là
Nguyễn Văn Quang - CH1101126
24
Associaltion Rule Confidence
{B}=>{C,E} 67%
{C}=>{B,E} 67%
{E}=>{B,C} 67%
{B,C}=>{E} 100%
{B,E}=>{C} 67%
{C,E}=>{B} 100%
Khóa luận môn học: Khai phá dữ liệu
 Tạo Apriori Candidate :
Hàm apriori-gen nhận đối số L

k-1
là tất cả các tập (k-1)_itemset.
Hàm này trả về các tập k _itemset.
apriori-gen(L
k-1
)
- Đầu tiên ở bước kết ta kết L
k-1
với L
k-1
:
insert into C
k
select p.item
1
, 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).
- Bước kế tiếp xén bớt, chúng ta xoá tất cả các itemsets c∈C
k
. Sao cho
tập con của c không có trong L
k-1.

forall itemsets c ∈ C
k
do
forall (k-1)-subsets s of c do
if (s ∉ L
k-1
) then
delete c from C
k

;
Ví du: cho tập L
3=
{{1, 2, 3},{1, 2, 4}, {1, 3, 4}, {1,3, 5}, {2, 3, 4}}.
- Sau khi kết ta có, C
4
sẽ là {1, 2, 3,4}, {1, 3, 4, 5}.
- Bước tiếp theo xén bớt sẽ xoá itemset {1, 3, 4, 5} bở vì itemset {1, 4,
5}∉ L3 và {3, 4, 5}∉ L3.
- Sau cùng ta có C
4
chỉ chứa {1,2,3,4}.
3.3. Đặc điểm của thuật toán Apriori
Tạo ra nhiều tập dự tuyển:
- 10
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

3.4. 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).
Nguyễn Văn Quang - CH1101126
25