Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
Công trình được hoàn thành tại:
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Người hướng dẫn khoa học:
PGS.TS. Nguyễn Trọng Bình

THÁI NGUYÊN 2010

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2

Nguyên và thư viện Trường CĐCN – Thái Nguyên
1

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

LỜI CAM ĐOAN

Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng nội dung
đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội dung luận văn, các phần
trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm.

Tác giả luận văn Nguyễn Khải Hoài Anh

2

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

MỤC LỤC

3

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2.1.4. Các tiêu chuẩn để phân loại luật kết hợp……………………………………15
2.1.4.1. Kiểu của giá trị được quản lý trong luật…………………………… 15
2.1.4.2. Chiều của dữ liệu được đề cập trong luật……………………… 15
2.1.4.3. Mức trừu tượng được đề cập trong luật………………………… 15
2.2. Khai phá luật kết hợp boolean một chiều từ CSDL giao dịch………………… 16
2.2.1. Thuật toán Apriori: Tìm các frequent itemset sử dụng việc sinh ra các ứng
viên……………………………………………………………………….16
2.2.2. Sinh luật kết hợp từ các frequent temset [5, 8, 15]…………………… 19
2.2.3. Cải tiến hiệu quả thuật toán Apriori……………………………………… 19
2.2.3.1. Phương pháp dựa trên bảng băm…………………………… 20
2.2.3.2. Giảm số giao dịch……………………………………………………….20
2.2.3.3. Phân đoạn……………………………………………………………… 21
2.2.3.4. Lấy mẫu………………………………………………………………… 21
2.2.4. Khai phá các frequent itemset bằng cách không sinh ứng cử viên…… 21
2.3. Khai phá luật kết hợp đa thức từ CSDL giao dịch……………………………… 24
2.3.1. Luật kết hợp đa thức……………………………………………………… 24
2.3.2. Các phương pháp khai phá luật kết hợp đa mức……………………… 26
2.3.2.1. Đồng nhất độ hỗ trợ tối thiểu cho tất cả các mức………………… 26
2.3.2.2. Giảm dần độ hỗ trợ tối thiểu ở mức thấp hơn…………………….27
2.3.2.3. Độc lập theo từng mức………………………………………………….27
2.3.2.4. Lọc chéo mức bởi một itemset………………………………………… 27
2.4. Khai phá luật kết hợp đa chiều từ CSDL quan hệ và kho dữ liệu……………… 28
2.4.1. Luật kết hợp đa chiều……………………………………………………….28

3.5.1. Sinh dữ liệu tổng hợp………………………………………… 55
3.5.2. So sánh các thuật toán AIS, SETM, Apriori và AprioriTID……… 56
CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM…………… 63
“ MÔ PHỎNG THUẬT TOÁN APRIORI”
4.1. Phát biểu bài toán ………………………………………………………… 63
4.2. Phân tích bài toán ………………………………………………………… 63
4.3. Xây dựng dữ liệu…………………………………………………………….64
4.4. Cài đặt chƣơng trình thử nghiệm………………………………………… 64
4.5. Giao diện chính của chƣơng trình………………………………………….65
KẾT LUẬN VÀ ĐỀ NGHỊ………………………………………………… 67
TÀI LIỆU THAM KHẢO……………………………………………………….68 5

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT
Ký hiệuDiễn giảiC
k
k

L
k
Tập các k-itemset phổ biếnT
Giao dịch (transaction)X ⇒Y
Luật kết hợp (với X là tiền đề, Y là hệ quả)ConfĐộ tin cậy (Confidence)k-itemset
Tập mục gồm k mụcMin_conf
Ngưỡng tin cậy tối thiểuMin_sup
Ngưỡng hỗ trợ tối thiểu



Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

DANH MỤC CÁC BẢNG Trang
Bảng 2.1: Tóm tắt quá trình khai phá cây FP – Tree
24
Bảng 2.2: Dữ liệu giao dịch của cho nhánh AllElectronecs
25
Bảng 2.3: Phân chia dựa trên khoảng cách
32
Bảng 3.1: Các tham số của chương trính sinh dữ liệu tổng hợp
56
Bảng 3.2: Các tham số
56
Bảng 3.3: Thời gian thực hiện theo giây (s) của thuật toán SETM
57
Bảng 3.4: So sánh thời gain thực hiện của Apriori và DHP (T15.I4.D100)
61

7

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
27
Hình 2.10: Lọc chéo mức bởi một itemset
28
Hình 2.11: Mạng cuboids tạo thành một data cube 3D
Hình 2.12: Lưới hai chiều do các luật kết hợp số lượng hai chiều với điều kiện buys
29
31
Hình3.1a:
Các bước thực hiện thuật toán SETM và min_sup_count = 2
38
Hìn 3.1b:
39
Hình 3.2: Các bước thực hiện của thuật toán AprioriTID
43
Hình 3.3: Thời gian xử lý mỗi bước quét của thuật toán Apriori và AprioriTID
44
Hình 3.4: Các bước thực hiện thuật toán DHP
49
Hình 3.5: Tìm L2 và D3
52
Hình 3.6a: Thời gian thực hiện với các tập dữ liệu T5.I2.D100K và T10.I2.D100K
57
Hình 3.6b: Thời gian thực hiện với các tập dữ liệu T10.I4.D100K và T20.I2.D100K
58
Hình 3.6c: Thời gian thực hiện với các tập dữ liệu T20.I4.D100K và T20.I6.D100K
58

8

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Khoa học, Xây dựng…
Với sự phát triển mạnh mẽ của công nghệ thông tin trong những năm gần
đây, hâu, hầu hết các tổ chức, cơ quan đã thu thập một lượng lớn các dữ liệu trong
cơ quan của họ. Các tổ chức này muốn chuyển những dữ liệu sẵn có của chính mình
thành các tri thức và các thông tin có ích cho chính họ.
Để làm được điều đó người ta đã sử dụng quá trình Phát hiện tri thức trong
cơ sở dữ liệu( Knowledge Discovery in Database-KDD). Nhiệm vụ của KDD là từ
dữ liệu sẵn có phải tìm ra những thông tin tiềm ẩn có giá trị mà trước đó chưa được
phát hiện cũng như tìm ra những xu hướng phát triển và các xu hướng tác động lên
chúng .Các kỹ thuật cho phép ta lấy được các tri thức từ cơ sở dữ liệu sẵn có đó
được gọi là kỹ thuật Khai phá dữ liệu( Data Mining).
Khai phá dữ liệu có thể xem như kết quả phát triển của công nghệ
thông tin, khai phá dữ liệu là một giai đoạn quan trọng của quá trình phát triển tri
thức.
Một trong những bài toán phổ biến của khai phá dữ liệu là khai phá luật kết
hợp. Khai phá luật kết hợp là tìm kiếm sự kết hợp đáng quan tâm hoặc quan hệ
tương quan giữa một tập lớn các khoản mục (item). Những luật kết hợp khai phá
được có thể giúp các tổ chức và các nhà quản lý đưa ra những quyết định kinh
doanh hiệu quả hơn.
Xuất phát từ những vấn đề đó em đã mạnh dạn lựa chọn đề tài luận văn:
“KHAI PHÁ DỮ LIỆU TRÊN CƠ SỞ PHƢƠNG PHÁP LUẬT KẾT HỢP VÀ
ỨNG DỤNG” là một việc làm không chỉ có ý nghĩa khoa học và còn mang đậm
tính thực tiễn.

10

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Trong thời đại ngày nay, với sự phát triển vượt bật của công nghệ thông tin,
các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng
ngày của chúng. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu (KPDL)
và máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa
biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt động của
hệ thống thông tin ban đầu.
1.1. Khai phá dữ liệu
1.1.1. Khái niệm về khám phá tri thức và khai phá dữ liệu
KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ
liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không
tường minh (ẩn), chưa được biết đến và có tiềm năng mang lại lợi ích. Có một số
nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Database - KDD). Ở đây chúng ta có thể coi KPDL là cốt
lõi của quá trình phát hiện tri thức. Quá trình phát hiện tri thức gồm các bước [3, 8, 16]:
- Làm sạch dữ liệu (Data cleaning): Các thủ tục làm sạch dữ liệu được sử
dụng để lấp kín những giá trị còn thiếu, loại bỏ nhiễu, nhận dạng các phần tử ngoài
cuộc và hiệu chỉnh những dữ liệu không đồng nhất.
- Tích hợp dữ liệu (Data intergation): Nó tổ hợp các dữ liệu từ nhiều nguồn
khác nhau thành một kho dữ liệu không đồng nhất.
- Lựa chọn dữ liệu (Data selection): Những dữ liệu thích hợp với nhiệm vụ
phân tích được trích rút từ cơ sở dữ liệu (CSDL)
- Chuyển đồi dữ liệu (Data transformation): Nó chuyển đổi hay hợp nhất
dữ liệu về dạng thích hợp cho việc khai phá. Việc chuyển đổi dữ liệu có thể gồm
các bước:
+ Loại bỏ nhiễu khỏi dữ liệu.
+ Kết tập các dữ liệu.

4

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

trữ trong một cơ sở tri thức.

5

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.1.2. Kiến trúc của một hệ thống khai phá dữ liệu
Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần
như hình 1.2 [3, 8]
- CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data
warehouse, ): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang tính
hay các dạng lưu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ
liệu có thể được thể hiện trên những dữ liệu này.
- Máy chủ CSDL hay máy chủ kho dữ liệu ( Database or warehouse server):
Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên các yêu cầu khai
phá của người dùng.
phá được dùng.
- Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận này
cho phép người dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này còn cho
phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu (hay các cấu trúc dữ
liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau.
1.1.3. Các loại dữ liệu đƣợc khai phá
KPDL phải có thể được áp dụng vào một loại lưu trữ thông tin bất kì [8]. Các
loại dữ liệu đó có thể là CSDL quan hệ, CSDL giao dịch, kho dữ liệu, các hệ CSDL
nâng cao, các tập tin phẳng ( flat file) và Web. Các hệ CSDL nâng cao gồm CSDL
hướng đối tượng, CSDL quan hệ đối tượng, CSDL hướng ứng dụng cụ thể như:
CSDL chuỗi thời gian ( time-series), CSDL văn bản và CSDL đa phương tiện.
1.1.4. Chức năng khai phá dữ liệu
KPDL có hai chức năng chính: mô tả (description) và dự đoán (prediction)
[3,8]
Công việc KPDL mô tả sẽ mô tả các tính chất hoặc đặc tính chung của dữ liệu
trong CSDL, nghĩa là phân tích và mô tả một tập mẫu đã biết (a set of known
sample) trong khả năng nhận thức của con người nhằm giúp họ hiểu rõ hơn, sâu hơn
về dữ liệu.
Còn công việc KPDL dự đoán sẽ thực hiện việc suy luận dựa trên dữ liệu hiện
hành để cho ra các dự báo, nghĩa là phân tích tập dữ liệu huấn luyện và tạo ra một
hoặc vài mô hình cho phép dự đoán các mẫu mới chưa biết (unseen new examples).

7

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.2. Một số phƣơng pháp khai phá dữ liệu thông dụng


Thu nhập < T

Thu nhập > T

Nợ < n

Nợ > n

Hình 1.3: Mẫu kết quả với phương pháp cây quyết định 8

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.2.3. Phƣơng pháp k-Mean
Phân cụm cũng là một trong những chủ đề được quan tâm nhiều trong nghiên
cứu KPDL. Có nhiều phương pháp được sử dụng trong phân cụm, phương pháp k-
Mean được coi là các kỹ thuật cơ bản của phân cụm [8].
Với phương pháp này sẽ chia tập có n đối tượng thành k cụm sao cho các đối
tượng trong cùng một cụm thì giống nhau, các đối tượng khác cụm thì khác nhau.
Đầu tiên chọn k đối tượng ngẫu nhiên, mỗi đối tượng đại diện cho tâm của
cụm (cluster mean or center). Dựa vào khoảng cách giữa tâm cụm với mỗi đối
tượng còn lại, gán mỗi đối tượng vào một cụm mà nó giống nhau nhất. Sau đó, tính
tâm mới của mỗi cụm. Quá trình được lặp lại cho đến khi hàm tiêu chuẩn hội tụ
(criterion function converges). Chẳng hạn sử dụng hàm tiêu chuẩn:




























+











9

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1.3. Một số ứng dụng của khai phá dữ liệu
1.3.1. Phân tích dữ liệu gen và sinh học y học
KPDL đã trở thành một công cụ mạnh và đóng góp thiết thực vào việc phân
tích gen theo các cách sau [8]:
Nghiên cứu tương tự và so sánh các chuỗi gen: Một trong những nghiên cứu
quan trọng trong phân tích gen là nghiên cứu tương tự và so sánh các chuỗi gen.
Các chuỗi gen được cô lập từ các mô bệnh và khoẻ có thể được so sánh với nhau để
nhận dạng những khác biệt giữa hai lớp gen.
Phân tích kết hợp: Nhận dạng các chuỗi gen cùng xảy ra, phân tích kết hợp
có thể được sử dụng giúp chúng ta xác định các loại gen thường kết hợp với nhau để
gây nên bệnh.
Phân tích hướng đi: Liên kết các gen ở các giai đoạn khác nhau của quá trình
phát triển bệnh, nếu một chuỗi hoạt động của các gen ở những giai đoạn khác nhau
của bệnh được xác định, thì có thể giúp chúng ta chế tạo ra các dược phẩm can thiệp
vào từng giai đoạn của bệnh. Do đó, có thể đạt được cách điều trị bệnh hiệu quả

dữ liệu khổng lồ đã và đang được thu thập ngày càng tăng, đặc biệt với sự gia tăng
về sự tiện lợi, lợi ích và tính phổ biến của việc kinh doanh trên Web, thương mại
điện tử. Dữ liệu bán lẻ cung cấp một kho dữ liệu phong phú cho việc khai phá dữ
liệu.
KPDL bán lẻ có thể giúp chúng ta xác định được hành vi mua hàng của
khách hàng, phát hiện những mẫu mua hàng của người dùng, những khuynh
hướng mua hàng [8].
Thiết kế các chiến dịch kinh doanh: Giữ khách hàng - Phân tích lòng trung
thành của khách hàng: Lòng trung thành của khách hàng và khuynh hướng mua
hàng có thể được phân tích một cách hệ thống.
1.3.4. Công nghiệp viễn thông
Công nghiệp viễn thông đã phát triển nhanh từ các dịch vụ điện thoại cục bộ
và điện thoại đường dài cho đến các dịch vụ truyền thông khác như voice, fax,
image, e-mail, truyền dữ liệu Web, các giao lộ dữ liệu khác. Tích hợp viễn thông,
mạng máy tính, internet, các phương tiện truyền thông khác đã và đang được thực
hiện. Điều này tạo ra một yêu cầu lớn về KPDL để giúp hiểu thêm việc kinh doanh,
xác định các mẫu viễn thông, chặn đứng các hoạt động lừa dối nhằm tạo điều kiện
sử dụng các tài nguyên tốt hơn và nâng cao được chất lượng dịch vụ [8].
Phân tích nhu cầu: Dữ liệu viễn thông là các dữ liệu đa chiều đích thực, với
các chiều như: giờ gọi, thời gian gọi, vị trí người gọi, vị trí người được gọi,

11

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

kiểu cuộc gọi. Phân tích đa chiều đối với các dữ liệu kiểu này có thể giúp xác định
nhu cầu và hành vi của các nhóm người dùng, từng vùng…Từ đó cung cấp

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

phá phân tích trực tuyến nên được tích hợp vào trong một khung hợp nhất. Điều
này sẽ đảm bảo tính tiện ích dữ liệu, linh động, uyển chuyển và thực thi cao của
KPDL
Khai phá Web: Ngày nay, với một lượng khổng lồ thông tin trên Web vai
trò quan trọng của Web đối với xã hội, việc khai phá nội dung Web sẽ trở thành bài
toán quan trọng và đáng quan tâm trong vấn đề khai phá dữ liệu.
An toàn và bảo mật thông tin trong KPDL: Với sự tăng nhanh của việc sử
dụng các công cụ KPDL, mạng máy tính, mạng viễn thông, một vấn đề quan trọng
đang đối mặt với KPDL là an toàn và bảo mật thông tin. Cho nên các phương pháp
được phát triển sau này phải đảm bảo được vấn đề này, mà vẫn tạo điều kiện thuận
lợi cho việc truy cập và khai phá thông tin hoàn hảo.

13

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

CHƢƠNG 2
KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU LỚN
Hiện tại, đã có một số ứng dụng kết quả của việc khai thác luật kết hợp trong

Độ tin cậy của luật A => B là:
Confidence (A => B) = P (B/A) =
)(sup
)(
Aport
BASupport 
(2)
Các luật kết hợp thoả mãn ngưỡng hỗ trợ tối thiểu (min_sup) và ngưỡng tin
cậy tối thiểu (min_conf) được gọi là luật mạnh. Quy ước, giá trị độ hỗ trợ và độ tin
cậy được thể hiện ở dạng % (từ 0% đến 100%) thay vì dưới dạng thập phân (0
đến 1.0)
Itemset là tập hợp các item, k - itemset là một itemset có k item.

14

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Tần số xuất hiện của một itemset là số giao dịch chứa itemset đó, thường được
viết: frequency, support count hoặc count of itemset.
Một itemset thoả độ hỗ trợ tối thiểu (minimum support) nếu tần số xuất hiện
của nó lớn hơn hoặc bằng min _sup x D . Số giao dịch cần thiết để một itemset
thoả độ hỗ trợ tối thiểu gọi minimum support count (min_sup_count). Một itemset
thoả độ hỗ trợ tối thiểu gọi là frequent itemset (hoặc large itemset) ngược lại gọi là
infrequent itemset (hoặc smal itemset). Một tập frequent k -itemset ký hiệu là L
k.
2.1.2. Cách khai phá luật kết hợp
Bài toán khai phá luận kết hợp được tách thành hai bài toán con [5,8]:

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2.1.4. Các tiêu chuẩn để phân loại luật kết hợp
Để phân loại các luận kết hợp chúng ta có thể dựa trên các tiêu chuẩn sau [8].
2.1.4.1. Kiểu của giá trị đƣợc quản lý trong luật
- Nếu luật quan tâm đến việc kết hợp về sự hiện diện của các item, thì nó là
luận kết hợp Boolean. Chẳng hạn, luật.
Computer => financial_management _software (3)
- Nếu luật mô tả sự kết hợp hợp giữa các item số luợng (quatitative) thì nó là
luật kết hợp số lượng. Với những luật này, các giá trị số lượng đối với item hoặc
thuộc tính (attribute) được rời rạc hoá thành các khoảng (interval).
Ví dụ:
age(X, "30….39") income (X, 42K….48K") => busy (X, high resolution TV) (4)
Trong đó: X là khách hàng. Các thuộc tính số lượng age, income đã
được rời rạc hoá.
2.1.4.2. Chiều của dữ liệu đƣợc đề cập trong luật
Nếu những item và attribute trong luật kết hợp là chỉ một chiều, thì nó là luật
kết hợp một chiều. Chẳng hạn luật (3) có thể viết lại như sau:
buys (X, Computer) => busy (X, financial_management_ software) (5)
Luật (5) là luật một chiều, vì nó chỉ đề cập đến một chiều kà buys. Nếu luật
liên quan đến hơn một chiều, thì nó là luật kết hợp đa chiều. Chẳng hạn, luật (4) là
lụât kết hợp đa chiều.
2.1.4.3. Mức trừu tƣợng đƣợc đề cập trong luật
Một số phương pháp cho phép chúng ta khai phá luật kết hợp ở các mức trừu
tượng khác nhau. Chẳng hạn, giả sử rằng tập những luật kết hợp được khai phá là
các luật sau:
age (X, "30…39") => buys (X, "laptop computer") (6)