LỜI CẢM ƠN
Em xin chân thành cảm ơn thầy giáo, Phó giáo sư, Tiến sĩ
Phan T ng a, giám ă Đ đốc trung tâm máy tính trường Đại học
Bách Khoa Hà Nội; thầy giáo, Phó giáo sư, Tiến s Nguyĩ ễn Ngọc
Bình,, giám đốc trung tâm thư viện iđ ện tử trường Đại học
Bách Khoa Hà Nội ã tđ ận tình hướng dẫn và giúp đỡ, cung
cấp cho em những ý kiến óng góp, nhđ ận xét quý báu trong
quá trình thực hiện đồ án.
Em xin chân thành cảm ơn các thầy cô giáo trong khoa
Công nghệ thông tin c ng nhũ ư các thầy cô giảng dạy trong
trường Đại học Bách Khoa Hà Nội, những người ã truyđ ền thụ
cho em những kiến thức quí báu trong suốt thời gian học
tập và nghiên cứu tại trường, giúp em có được những iđ ều
kiện cần thiết để hoàn thành tốt đồ án này.
Sự quan tâm và giúp đỡ của Bố mẹ, cùng toàn thể gia
ình là mđ ột nguồn động viên rất lớn, tạo cho con sự yên
tâm về vật chất và tinh thần để con hoàn thành nhiệm vụ
của mình.
Cuối cùng xin cảm ơn sự quan tâm và óng góp ý kiđ ến
của tất cả các bạn.
Hà Nội ngày 15 tháng 05 năm 2004
Sinh viên
Hoàng Thị Minh Thu
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
DANH MỤC TỪ VIẾT TẮT
Số TT Từ viết tắt Giải nghĩa
1 CD Count Distribution
2 CSDL cơ sở dữ liệu
3 DB Database
4 DBMS Database Management System
5 DD Data Distribution

6 Count Distribution phân phối số đếm
7 Data Distribution phân phối dữ liệu
8 frequent itemset itemset có giá trị support không nhỏ hơn minsup
9
frequent itemset
maximal
Itemset frequent mà không có bất kỳ superset nào
của nó là frequent itemset
10 Interesting itemset itemset đáng quan tâm
11 Itemset tập các item
12 k-itemset itemset có k phần tử
13 k-subset một tập con của một giao dịch có chứa k item
14 large itemset itemset có giá trị support không nhỏ hơn minsup
15 long frequent itemset Itemset frequent dài
16 maximum frequent set Tập các frequent itemset tối đa
17 minconf confidence tối thiểu
18 minsup support tối thiểu
19
p’s conditional pattern
base
Cơ sở pattern điều kiện của p là các cơ sở sub-
pattern của p
20 set-enumeration-tree Cây đánh số thứ tự tập
21 subset tập các phần tử là tập con của một tập cho trước
22 superset tập cha
23 support(X)
phần trăm giao dịch trong CSDL có chứa itemset
X
24 transaction một giao dịch trong cơ sở dữ liệu
25 Transaction identifier Định danh duy nhất của một giao dịch

Hình 24: Một ví dụ của FP-Tree 53
Hình 25: Xây dựng FP-Tree từ m “FP-Tree |m” 55
Hình 26: Thuật toán FPGrowth 57
Hình 27: So sánh tốc độ thực hiện giữa FPGrowth và Apriori 58
Hình 28: ReduceScatter and AllGather Communication 63
Hình 29:Thuật toán FDM-LP 77
Hình 30: Mô hình chung hệ thống 79
Hình 31: Kiến trúc hệ thống ARMiner 80
Hình 32: Biểu đồ phân cấp chức năng 81
Hình 33: Định dạng tệp giao dịch 82
Hình 34: Tệp dữ liệu đầu ra 82
Hình 35: Các môđun dùng trong hệ thống 84
Hình 36: Sơ đồ lớp mô tả các chức năng 84
Hình 37: Định dạng tệp từ điển cải tiến 86
Hình 38: Giao diện chính của chương trình 87
Hoàng Thị Minh Thu, CNPM K44
4
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
DANH MỤC BẢNG
Bảng 1: Các thuộc tính 21
Bảng 2 : Ký hiệu 32
Bảng 3: Tập và Lk qua các giai đoạn 1, 2, 3 35
Bảng 4: Cơ sở dữ liệu giao dịch của ví dụ về FP-Tree 52
Bảng 5: Khai phá tất cả các pattern bởi tạo ra cơ sở (sub)-pattern điều kiện 55
Bảng 6: Bảng ký hiệu 71
Bảng 7: Large itemset cục bộ 71
Bảng 8: Large itemset toàn cục 72
Bảng 9: Số đếm support cục bộ 74
Bảng 10: Các tham số để sinh tập dữ liệu giả 85
Hoàng Thị Minh Thu, CNPM K44

3.1.Các thuật toán nguyên thuỷ 30
3.1.1.AIS [3] 30
3.1.2. SETM [3] 31
3.2. Các thuật toán Apriori [4] 32
3.2.1.Thuật toán Apriori 32
3.2.2.Thuật toán AprioriTID: 34
3.2.3.Thuật toán AprioriHybrid 36
3.3.Thuật toán DHP (Direct Hashing and Pruning) [16] 37
3.4.Thuật toán DIC (Dynamic Counting Itemset) [6] 42
3.5.Thuật toán Pincer-Search [10] 45
3.6.Thuật toán khai phá các mẫu dài từ CSDL (Max-Miner) [14] 46
3.6.1.Max-Miner hình thức 47
3.6.2.Cách sắp thứ tự item 48
3.6.3.Yêu cầu về tính chính xác và hiệu quả 49
3.6.4.Giới hạn dưới của support 49
3.7.Thuật toán FPGrowth [9] 51
3.7.1.Thuật toán xây dựng FP - Tree 51
3.7.2.Khai phá các frequent pattern sử dụng FP-Tree 53
3.7.3.Đánh giá mô hình 57
3.8.Kết luận 58
Chương 4: KHAI PHÁ LUẬT KẾT HỢP SONG SONG TRÊN CƠ SỞ DỮ LIỆU PHÂN TÁN 60
4.1.Kiến trúc không chia sẻ bộ nhớ [5] , [11] 60
Hoàng Thị Minh Thu, CNPM K44
6
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
4.1.1.Thuật toán Count Distribution (Phân phối số đếm) 62
4.1.2.Thuật toán Data Distribution (Phân phối dữ liệu) 64
4.1.3. Thuật toán Candidate Distribution (Phân phối candidate) 65
4.1.4.Sinh luật song song 67
4.2.Kiểu kiến trúc chia sẻ bộ nhớ chung [8] 68

chứa rất nhều thông tin quan trọng. Khai phá dữ liệu (data mining) là một quá trình sử
dụng rất nhiều công cụ phân tích dữ liệu để phát hiện ra các mẫu và các mối quan hệ
trong dữ liệu để đưa ra được những dự đoán hiệu quả. Nhiệm vụ chính của data
mining là phát hiện ra các tri thức chưa được phát hiện hay còn ẩn chứa trong tập dữ
liệu lớn.
Những tiến bộ gần đây trong việc thu thập và lưu trữ dữ liệu đã được áp dụng
trong các công ty (kỹ thuật mã vạch), các cơ quan hành chính (dữ liệu điều tra) hay
các phòng thí nghiệm khoa học (CSDL phân tử trong hoá học hay sinh học) để lưu giữ
được một lượng lớn các dữ liệu liên quan đến hoạt động của các tổ chức này. Cùng
thời gian này, khả năng dùng nguồn năng lượng tính toán rẻ để trích rút tự động tri
thức có cấu trúc từ dữ liệu đã tập hợp được này một cách dễ dàng. Những hoạt động
như vậy đều được coi như khai phá dữ liệu. Khai phá dữ liệu bao gồm những lĩnh vực
như phân loại, chia nhóm, phân tích sự tương đồng, tóm tắt nội dung, khai phá luật kết
hợp và khai phá các mẫu tuần tự… Vấn đề khai phá luật kết hợp lần đầu tiên được đưa
ra giới thiệu vào năm 1993 nhưng đã nhanh chóng phát triển mạnh mẽ. Vậy lý do vì
sao ?
Hãy xem xét một CSDL lớn các mặt hàng, mỗi giao dịch bao gồm các mặt hàng
mua bán của khách hàng. Vấn đề khai phá luật kết hợp được áp dụng nhiều nhất trong
các quyết định kinh doanh, điển hình trong việc quản lý siêu thị như: mặt hàng gì cần
hạ giá, thiết kế phiếu mua hàng như thế nào hay sắp xếp các mặt hàng ra sao để có lợi
nhuận lớn nhất. Việc phân tích các dữ liệu trong quá khứ là cách tiếp cận thường được
sử dụng nhằm nâng cao chất lượng mua hàng. Tuy nhiên, gần đây chỉ những số liệu
tích luỹ theo định kỳ thời gian là được lưu lại trên máy tính. Sự tiến bộ trong kỹ thuật
mã vạch đã giúp lưu trữ các basket data - dữ liệu các mặt hàng mua bán trong mỗi
giao dịch một cách hiệu quả.
Luật kết hợp đã được sử dụng trong rất nhiều ứng dụng như: phân tích giao dịch
trong siêu thị, phân tích cách bố trí cách lưu trữ cũng như xu thế các mặt hàng, phân
tích số liệu tuyển sinh đại học, phân tích thói quen khách hàng, phân loại khách hàng
dựa vào mặt hàng mua bán, thiết kế catalog, phân tích sự xuất hiện của từ trong một
tài liệu văn bản, sự ghé thăm vào các trang WWW của người dùng, giao dịch chứng

Chương 4: Nghiên cứu các thuật toán kết hợp song song trên cơ sở dữ liệu phân
tán
Chương 5: Xây dựng giải pháp và thử nghiệm kết quả với các thuật toán khai phá
luật kết hợp đã cài đặt.
Kết luận: Nêu ra các nhận xét, kết quả đạt được và một số phương hướng phát
triển tiếp theo của đề tài.
Hoàng Thị Minh Thu, CNPM K44
9
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Phần đầu của chương sẽ đề cập tới các bước thực hiện của quá trình khai phá
dữ liệu và tổng quan các kỹ thuật khai phá. Phần sau sẽ đi sâu vào một số kỹ thuật
khai phá được sử dụng phổ biến hiện nay cũng như những vấn đề mà các kỹ thuật này
còn chưa giải quyết được.
Khi điện tử và sóng điện từ đã trở thành vấn đề cốt lõi của công nghệ điển tử cổ
điển thì ta thấy rằng dữ liệu, thông tin, tri thức đang là lĩnh vực tập trung nhiều nghiên
cứu và ứng dụng – phát hiện tri thức và khai phá dữ liệu (knowledge discovery and
data mining: KDD).
Nói chung, ta thường biết dữ liệu là một chuỗi các bit, số hay ký tự hoặc đối
tượng cần quan tâm. Ta sử dụng các bít để đánh giá thông tin. Tri thức được xem như
là thông tin tổ hợp, bao gồm các sự thật và mối liên quan giữa chúng, có thể thu nhận,
khám phá và học được. Nói cách khác, tri thức là dữ liệu ở mức cao của sự trừu tượng
và tổng quát hoá.
KDD là lĩnh vực phát triển nhanh chóng, kết hợp với hệ quản trị CSDL, các lĩnh
vực thống kê, học máy và các lĩnh vực liên quan khác. Phát hiện tri thức là một quá
trình chỉ ra được các mô hình/mẫu hiểu được có giá trị và đáng quan tâm. Data mining
là một bước trong quá trình phát hiện tri thức, bao gồm các thuật toán khai phá dữ liệu
cụ thể với hiệu năng tính toán chấp nhận được để tìm ra các mẫu hay mô hình của dữ
liệu.
Nói cách khác, mục đích của khai phá và phát hiện tri thức là tìm ra các mẫu hay

Đặc điểm của các mẫu là phải mới (ít nhất là đối với hệ thống đó). Độ mới có thể
được đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại
với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ
giữa các phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới
của mẫu được đánh giá bằng các hàm logic hoặc hàm đo độ mới, độ bất ngờ của mẫu.
Ngoài ra, mẫu phải có khả năng sử dụng tiềm tàng. Các mẫu này sau khi được xử lý
và diễn giải phải dẫn đến những hành động có ích nào đó được đánh giá bởi một hàm
lợi ích. Ví dụ như trong dữ liệu các khoản vay, hàm lợi ích đánh giá khả năng tăng lợi
nhuận từ các khoản vay. Mẫu khai thác được phải có giá trị đối với các dữ liệu mới
với độ chính xác nào đó.
Hình 1: Quá trình khai phá dữ liệu
Với các giải thuật và các nhiệm vụ của khai phá dữ liệu rất khác nhau, dạng của
các mẫu chiết xuất được cũng rất đa dạng. Theo cách đơn giản nhất, sự phân tích cho
ra kết quả chiết xuất là một báo cáo về một số loại (có thể bao gồm các phép đo mang
tính thống kê về độ phù hợp của mô hình, các dữ liệu lạ ). Trong thực tế đầu ra phức
tạp hơn nhiều. Mẫu chiết suất được có thể là một mô tả xu hướng, có thể dưới dạng
Hoàng Thị Minh Thu, CNPM K44
11
Xác định
nhiệm vụ
Xác định
dữ liệu
liên quan
Thu thập
và tiền xử
lý dữ liệu
Dữ liệu
trực tiếp
Thống kê
tóm tắt

phân loại) một mẫu dữ liệu vào một trong số các lớp đã xác định.
• Hồi quy (Regression) : Hồi quy là việc học 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.
• Phân nhóm (Clustering): Là việc mô tả chung để tìm ra các tập xác định,
các nhóm hay các loại để mô tả dữ liệu. Các nhóm có thể tách riêng nhau
hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc
nhóm này, vừa thuộc nhóm kia.
• Khai phá luật kết hợp (Association Rule): tìm ra các large itemset, các
mối liên quan, kết hợp và cấu trúc nhân quả trong tập các khoản mục hay
đối tượng trong CSDL giao dịch, CSDL quan hệ hay từ các kho lưu trữ
thông tin khác.
Hoàng Thị Minh Thu, CNPM K44
12
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
• Tóm tắt (Summarization) : Liên quan đến các phương pháp tìm kiếm
một mô tả tóm tắt cho một tập con dữ liệu.
• Mô hình hoá phụ thuộc (Dependency Modeling): Bao gồm việc tìm
kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình
phụ thuộc tồn tại dưới hai mức : mức cấu trúc của mô hình xác định
(thường ở dạng đồ hoạ) các biến nào là phụ thuộc cục bộ với nhau, mức
định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một
thước đo nào đó.
• Phát hiện sự thay đổi và lạc hướng (Change and Deviation Detection):
Tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các
giá trị chuẩn hoặc được đo trước đó.
Những nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin rất khác
nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật khai phá dữ
liệu khác nhau.
1.3. Khai phá dữ liệu mô tả
1.3.1. Phân nhóm

Kết quả của việc xây dựng mô hình là một bản mô tả các mẫu và mối quan hệ dữ liệu
có thể hỗ trợ cho việc dự đoán. Để tránh khó hiểu trong các khía cạnh khác nhau của
khai phá dữ liệu, cần đưa ra cấu trúc công việc cần thực hiện cho quá trình dự đoán
• Mục tiêu công việc
• Kiểu dự đoán
• Kiểu mô hình
• Thuật toán
Mức cao nhất cần quan tâm là công việc nhằm mục đích gì. Như tìm kiếm các
mẫu trong dữ liệu kinh doanh để dự đoán đối tượng khách hàng sẽ thu được lợi nhiều
nhất. Quyết định kiểu dự đoán phù hợp nhất: phân loại hay hồi quy. Kiểu mô hình:
mạng noron cho bài toán hồi quy hay một cây quyết đinh cho bài toán phân lớp. Có
các mô hình như suy diễn logic, phân tích rời rạc số hay mô hình tuyến tính. Có nhiều
thuật toán đã được công bố hiện nay, với cây quyết định ta có CART, C5.0 Quest hay
CHAID.
Mô hình dự đoán [17] được xây dựng hay huấn luyện sử dụng dữ liệu, trong đó
giá trị các biến tương ứng là đã biết. Kiểu huấn luyện này đôi khi được gọi là học có
giám sát.
1.4.1. Bài toán phân loại
Trong bài toán phân loại [13], mỗi đối tượng là được miêu tả bởi một tập các giá
trị thuộc tính và mỗi đối tượng sẽ thuộc về một lớp được xác định trước. Mục đích
của bài toán phân loại là thu được một tập các luật chỉ ra lớp mà đối tượng thuộc vào,
dựa trên một tập các mẫu huấn luyện. Do đó, phân loại dữ liệu được gọi là học có
giám sát. Một trong các ứng dụng của bài toán này là khi ngân hàng muốn phát triển
một cơ chế tự động có thể quyết định được rằng một ứng dụng sử dụng thẻ tín dụng có
được chấp nhận hay không dựa trên các bản ghi dữ liệu của các khách hàng đã có.
Hoàng Thị Minh Thu, CNPM K44
14
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
Hay một ứng dụng khác là: Một bệnh viện muốn chẩn đoán một bệnh nhân có
thuộc về một nhóm có nguy cơ rủi ro cao hay không dựa trên tiền sử bệnh của bệnh

Đại học,
CĐ
Trung bình Trẻ Không Nữ Cao
Trung học Thấp Trung niên Không Nam Thấp
Đại học,
CĐ
Trung bình Trung niên Nữ Cao
Trung học
Trung bình Trẻ Không Nam Thấp
1.4.2. Cây quyết định
Cây quyết định [17] là một biểu đồ phát triển có cấu trúc cây với tập các thuộc
tính cho trước, cần xác dịnh được giá trị của thuộc tính cuối cùng cần rút ra. Cây quyết
định có thể dễ dàng chuyển đổi sang dạng luật với cấu trúc if then.
Cấu trúc cây quyết định có dạng:
• Mỗi node trong ký hiệu cho một bộ dữ liệu thử cho một thuộc tính
• Mỗi nhánh đặc trưng cho một đợt dữ liệu thử
• Các node lá đại diện cho các lớp hoặc là phân phối lớp.
• Node trên đỉnh của cây là node gốc.
Quá trình dựng cây gồm hai bước:
Hoàng Thị Minh Thu, CNPM K44
15
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
• Dựng cây: Phân đoạn dữ liệu cho trước hồi quy dựa trên các thuộc tính
được lựa chọn. Tai thời điểm bắt đầu, mọi đối tượng huấn luyện được đặt
tại node gốc.
• Tỉa cây: chỉ ra và loại bỏ những nhánh chịu nhiễu hoặc ngoài lề.
Ứng dụng: chia lớp một đối tượng. Kiểm thử các giá trị thuộc tính một lần nữa
trên cây quyết định.
Thuật toán dựng cây: tại mỗi node của cây tiến hành như sau:
1. Chọn ra thuộc tính tối ưu nhất căn cứ trên các đánh giá cho trước

Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng

Hình 2 : Cây quyết định với Temperature làm node gốc
Nhưng nếu chọn Outlook làm node gốc, cây thu được sẽ đơn giản hơn nhiều
Hình 3: Cây quyết định với Outlook làm node gốc
Vậy, chọn node gốc như nào thì tốt nhất?
Cách chọn lựa thuộc tính tốt nhất: sử dụng lý thuyết của độ đo thông tin Gain
và Entropy.
Entropy:đặc trưng cho mức độ pha tạp (hay đồng nhất) của một tập hợp các đối
tượng mẫu. Gọi S là tập hợp các đối tượng âm và dương , P
⊕
là phần các giá trị dương
trong S, P
Θ

là phần các giá trị âm trong S.
Entropy(S) = - P
⊕
log
2
P
⊕
- P
Θ

log
2
P
Θ


p
i
Với 14 đối tượng trong ví dụ Play-tennis, có 9 đối tượng dương và 5 đối tượng âm (ký
hiệu là [9+, 5-]).
Entropy([9+, 5-]) = - (9/14)log
2
(9/14) – (5/14)log
2
(5/14)
= 0.940
Lưu ý, Entropy bằng 0 nếu mọi phần tử của S đều thuộc vào cùng một lớp. Entropy
bằng 1 nếu S có số đối tượng dương và âm bằng nhau.
Information Gain:
Information Gain của một thuộc tính A trong tập S, ký hiệu là Gain(S,A) được định
nghĩa như sau:
Gain(S, A) = Entropy(S) =
∑
∈ )(
||
||
AValuev
v
S
S
Entropy(S
v
)
trong đó, Value(A) là tập các giá trị có thể của thuộc tính A; S
v
là một tập con của S

18
[3+,4-]
E = 0.985
[6+,1-]
E = 0.592
high normal
humidity
[6+,2-]
E = 0.811
[3+,3-]
E = 1.00
weak strong
wind
Gain(S, Humidity) = 0.940 – (7/14)0.985 – (7/14)0.592
= 0.151
Gain(S, Wind) = 0.940 – (8/14)0.811 – (6/14)1.00
= 0.048
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
{D1,D2, …, D14} [9+,5-]
S
sunny
= {D1, D2, D3, D9, D11}
Gain(Ssunny, Humidity) = 0.970 - (3/5)0.0 - (2/5)0.0 = 0.970
Gain(Ssunny, Temperature) = 0.970 - (2/5)0.0 - (2/5)1.0 - (1/5)0.0 = 0.570
Gain(Ssunny, Wind) = 0.970 - (2/5)1.0 - (3/5)0.918 = 0.019
Ta chọn thuộc tính Humidity để dựng tiếp. Cứ tiếp tục như vậy đến khi đạt điều kiện
dừng. Cây quyết định được tăng trưởng theo các bước lặp để phân tách dữ liệu thành
các nhóm rời rạc nhau, mục tiêu là cực đại sự sai khác nhau giữa mỗi nhóm.
Điều kiện dừng:
1. Mọi thuộc tính đều đã có mặt trên cây.

{D4, D5, D6, D10, D14}
[3+,2-]
??
Yes
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
liệu số, biến phân loại cần phải được xử lý đặc biệt hơn. Như khoảng cách giữa màu
xanh và màu đỏ là gì? Phải có cách để tính tổng khoảng cách giữa các thuộc tính. Mỗi
khi tính toán khoảng cách giữa các trường hợp, phải chọn ra một tập các trường hợp
khác đã được phân lớp làm cơ sở cho quá trình phân loại trường hợp mới, quyết định
độ rộng của vùng lân cận so sánh và cách đếm láng giềng (có thể cung cấp nhiều
trọng số cho láng giềng gần hơn cho các láng giếng xa hơn). K-NN đưa một khối
lượng công việc lớn vào máy tính vì thời gian tính toán tăng theo hệ số tổng các điểm.
Trong khi xử lý nhanh hơn với cây quyết định hay mạng nơron đối với một trường
hợp mới, k-NN yêu cầu phép tính toán mới cho mỗi trường hợp mới. Để tăng tốc độ
cho k-NN, tất cả dữ liệu thường xuyên truy cập được lưu trong bộ nhớ. Mô hình k-NN
dễ hiểu khi chỉ có vài biến dự đoán, và cũng rất hữu ích khi tính toán với dữ liệu
không chuẩn hoá như văn bản. Chỉ có một yêu cầu đối với một kiểu dữ liệu là phải tồn
tại một ma trận thích hợp.
1.5. Tại sao khai phá luật kết hợp lại quan trọng
Hãy xét một ứng dụng trong việc khai phá dữ liệu y tế liên quan tới căn bệnh tim
[12] . Giả sử ta có một bảng mô tả các thuộc tính như sau và tập các mẫu thông tin liên
quan của bệnh nhân. Mục tiêu là phải chỉ ra được mối liên quan giữa độ đo perfusion
và mức độ rủi ro với mức độ mắc bệnh tim.
Đã có rất nhiều kỹ thuật khai phá dữ liệu được sử dụng, nhưng ta hãy xét xem tại
sao những kỹ thuật này lại không thể giải quyết hiệu quả bài toán đặt ra. Cây quyết
định đưa ra tập luật để phân loại các bản ghi từ một tập dữ liệu đã được tối thiểu hoá
các lỗi phân loại. Mục đích của việc sử dụng cây quyết định là chỉ ra lớp mà các bản
ghi thuộc vào. Trong trường hợp này, có thể phân loại bệnh nhân là khoẻ hay có bệnh.
Tuy nhiên, các bệnh nhân sẽ không thể được phân vào các lớp một cách dễ dàng bởi
có nhiều cấp độ khác nhau của “có bệnh”. Có thể sẽ có rất nhiều lớp được áp dụng để

15 Sex C R Giới tính
16 HTA C R Hyper-tension
17 Diab C R Diabetes
18 HYPLD C R Hyperlipidemia
19 FHCAD C R Fam. Hist. of
disease
20 Smoke C R Thói quen hút thuốc
21 Claudi C R Claudication
22 Pangio C R Previous angina
23 Pstroke C R Prior stroke
24 PcarSu
r
C R Prior carotid surgery
25 Chol N R Hàm lượng
Cholesterol
Với kỹ thuật khai phá luật kết hợp có ràng buộc ta có thể thu được tập các luật
rất có ý nghĩa liên quan tới cả việc xác định có bệnh hay không có bệnh và mức độ ra
sao.
Dự đoán không có bệnh:
1. [Sex = F]
⇒
([0.0 <=LCX < 50.0 ]), s =0.229, c = 0.728
2. [Smoke = n]
⇒
([not(70.0 <=RCA < 100.1)]), s = 0.290, c = 0.714
3. [0.0 <= CHO: < 200.0]
⇒
[not(70.0 <= LAD <100.1)], s = 0.078, c = 0.708
4. [0.0 <= Age < 40.0][Smoke = n]
⇒

2. [60.0 <= Age < 100.0][0.2 <= AP < 1.1][Smoke = y]
⇒
[not(0.0 <=LAD < 50.0)], s
= 0.107, c = 0.833
3. [0.2 <= LA < 1.1][Sex = M]and[250.0 <= CHOL < 500.1]
⇒
[not(0.0 <= LCX <
50.0)], s =0.014, c = 0.750
4. [60.0 <= Age <100.0][0.2 <= IL < 1.1][250.0 <= CHOL < 500.1]
⇒
[not(0.0 <=
RCA < 50.0)], s = 0.017, c = 0.917
5. [60.0 <= Age < 100.0][0.2 <= IS < 1.0][250.0 <= CHOL < 500.1]
⇒
[not(0.0
<=RCA < 50.0)], s = 0.015, c = 1.000
6. [60.0 <=Age < 100.0][0.2 <= SA < 1.0][FHCAD = y]
⇒
[not(0.0 <=LAD < 50.0)],
s = 0.015, c = 1.000
7. [0.2 <= SA < 1.0]and[PANGIO = y]
⇒
[not(0.0 <=LAD < 50.0)], s = 0.023, c =
0.938
8. [60.0 <= Age <100.0][0.2 <= AP < 1.1][Sex = F]
⇒
[not(0.0 <=LAD < 50.0)], s =
0.049, c = 0.941
9. [60.0 <= Age < 100.0][0.2 <= SA < 1.0][Claudi = y]
⇒

ứng là s và c cho trước, liệt kê tất cả luật từ CSDL D có giá trị support và confidence
tương ứng lớn hơn s và c. Ví dụ, nếu D là CSDL kinh doanh, s = 40% và c = 90%, bài
toán sẽ được phát biểu thành (1) liệt kê tất cả các luật chỉ ra rằng sự có mặt của một
khoản mục này sẽ kéo theo sự có mặt của các khoản mục khác. (2) Chỉ xét những luật
có chiếm hơn 40% bản ghi mà có mức độ tin cậy vượt quá 90%.
2.1. Các định nghĩa cơ bản:
2.1.1. Itemset:
Gọi I là tập các item phân biệt nhau, I = { I
1
, I
2
, I
m
} với Ii là các item (khoản
mục). Không mất tính tổng quát, ta giả sử rằng bất kỳ tập con (subset) nào của I đều
có thể được biểu diễn dưới dạng chuỗi tuần tự các item sắp theo trật tự tên các item.
Ví dụ {a,c} và {c,a} biểu diễn cùng là tập con của {a,b,c} nhưng chỉ có một chuỗi
tuần tự duy nhất là ac.
Định nghĩa 1: Một Itemset X là một tập các item trong I, Itemset X được gọi là k-
itemset nếu chứa k item có trong I.
2.1.2. Cơ sở dữ liệu [1], [15]
CSDL D được xét như một bảng quan hệ Booolean (Hình 4.a) và có thể được tổ
chức vật lý theo chiều ngang (Hình 4.b) hoặc chiều dọc ( Hình 4.c). Tổ chức theo
chiều ngang gồm tập các cặp (TID, T) với TID là định danh duy nhất của giao dịch và
T là một giao dịch trong D – là một tập các item sao cho T ⊆ I. Tổ chức theo chiều
dọc gồm tập các cặp (a, list) với a là một item và list là một danh sách sắp thứ tự các
số nối tiếp.
Hoàng Thị Minh Thu, CNPM K44
23
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng

abcde↓↓↓↓↓112
1132432435535
4664 5 5 6
(c)
(b)
(a)
Nghiên cứu các thuật toán khai phá luật kết hợp nhanh và ứng dụng
Định nghĩa 5: Một frequent itemset là tối đa (maximal) nếu nó không có bất kỳ
superset nào là frequent itemset.
Định nghĩa 6: Tập các frequent itemset tối đa được gọi là maximum frequent itemset
(viết tắt là MFS).
Ví dụ 1-1 : Cho D được định nghĩa như Hình 4. Cho ngưỡng minsup = 0.5, ta tìm được
các frequent itemset với hệ số support như sau:
sup(b) = |{1, 2, 3, 4, 5, 6}| / 6 = 100%
sup(e) = sup(be) = |{1, 2, 3, 4, 5}| / 6 = 83%
sup(a) = sup(ab) = sup(ae) = sup(abe) = |{1, 3, 4, 5}| / 6 = 67%
sup(c) = sup(bc) = |{2, 4, 5, 6}| / 6 = 67%
sup(d) = sup(bd) = |{21, 3, 5, 6}| / 6 =67%
sup(ad)= sup(de) =sup(abd) = sup(bde) = sup(abde) = |{1, 3, 5}| / 6 = 50%
sup(ce) = sup(bce) = |{2, 4, 5}| / 6 = 50%
2.1.4. Luật kết hợp:
Định nghĩa 7: Gọi X và Y là hai itemset mà X⊂ I, Y⊂ I và X∩Y=φ, một luật kết
hợp sẽ có dạng X ⇒ Y trong đó X được gọi là tiền đề và Y được gọi là hệ quả của
luật. Lưu ý rằng mỗi luật X ⇒ Y đều gắn với một confidence conf,
conf =
)(sup
)(sup
X
YX ∪
.