Luận văn Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song

ĐẠI HỌC THÁI NGUYÊN

KHOA CÔNG NGHỆ THÔNG TIN

-----------------------------

LÊ THỊ VIỆT HOA

KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KHAI PHÁ

LUẬT KẾT HỢP SONG SONG

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số

: 60.48.01

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN

THÁI NGUYÊN 2008

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 CẢM ƠN

Xin chân thành cảm ơn Thầy giáo PGS.TS Đoàn Văn Ban đã tận tình

chỉ dạy và hướng dẫn tôi trong suốt thời gian học tập và làm luận văn.

Tôi cũng xin xin lời biết ơn chân thành đến quý Thầy giáo, cô giáo Viện

Công nghệ Thông đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý

báu trong suốt quá trình học tập tại Khoa.

Xin cảm ơn tất cả các anh chị em học viên Cao học khóa 5, cám ơn cán

bộ công chức, giảng viên – Khoa Công nghệ Thông tin - Đại học Thái Nguyên

đã tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập và làm luận văn.

Cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã giúp đỡ tôi

trong suốt thời gian học tập và hoàn thành luận văn này.

Thái Nguyên, tháng 9 năm 2008

Tác giả

Lê Thị Việt Hoa

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 đề tài khoa học “Khai phá dữ liệu và thuật toán khai

phá luật kết hợp song song” này là công trình nghiênứcu của bản thân tôi.

Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được

các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong

luận văn. Tôi xin chịu trách nhiệm về luận văn của mình.

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

Trang phụ bìa

Lời cám ơn

Lời cam đoan

Mục lục

Trang

Danh mục các kí hiệu, các chữ viết tắt

Danh mục các hình vẽ

Mở đầu

1

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1. Khái niệm

3

1.2. Kiến trúc của một hệ thống khai phá dữ liệu

1.3. Các giai đoạn của quá trình khai phá dữ liệu

1.4. Một số kỹ thuật khai phá dữ liệu

1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu

1.6. Các phương pháp chính trong khai phá dữ liệu

1.7. Các ứng dụng của khai phá dữ liệu

1.8. Khai phá dữ liệu và các lĩnh vực liên quan

1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu

1.10. Kết luận chương 1

3

4

6

10

11

13

14

15

16

17

18

21

22

24

30

Chương 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU

2.1. Mở đầu

2.2 Luật kết hợp

2.2.1 Các khái niệm cơ bản

2.2.2. Khai phá luật kết hợp

2.2.3. Cách tiếp cận khai phá luật kết hợp

2.3 Luật kết hợp cơ sở

2.3.1 Phát hiện các tập mục phổ biến

2.3.2 Sinh luật kết hợ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

2.4. Khai phá luật kết hợp với một số khái niệm mở rộng

2.4.1. Giới thiệu

32

43

49

2.4.2. Khai phá luật kết hợp trọng số

2.4.3 Khai phá luật kết hợp tổng quát

2.5. Kết luận chương 2

Chương 3: MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP

SONG SONG VÀ PHÂN TÍCH ĐÁNH GIÁ CÁC THUẬT TOÁN

50

3.1. Nguyên lý thiết kế thuật toán song song

3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song

3.2.1. Mô hình song song dữ liệu

50

51

52

54

58

60

65

71

73

74

75

77

3.2.2. Mô hình song song thao tác

3.3. Một số thuật toán khai phá luật kết hợp song song

3.3.1 Thuật toán Count Distribution (CD)

3.3.2. Thuật toán Data Distribution (DD)

3.3.3. Thuật toán Candidate Distribution

3.3.4. Thuật toán song song Fp-Growth

3.3.5 Thuật toán song song Eclat

3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán

3.4.1. Phân tích và đánh giá thuật toán song song

3.4.2. So sánh việc thực hiện các thuật toán

3.5. Kết luận chương 3

Kết luận

Tài liệu tham khảo

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 VIẾT TẮT

Ký hiệu

Diễn giải

Tập các k-itemset ứng viên

C_k

Tập các k-itemset ứng viên mà TID của giao dịch sinh ra

liên kết với tập mục ứng viên

Độ tin cậy (Confidence)

C_k

Conf

CFPT

D

FP-Tree điều kiện cơ sở (Fisst conditional FP-Tree)

Cơ sở dữ liệu giao dịch

D_i

Phần thứ i của cơ sở dữ liệu D

Mục

Item

Itemset

I

Tập mục

Tập các mục

KDD

Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery

in Database)

CSDL

Cơ sở dữ liệu (Database)

k-itemset Tập mục gồm k mục

L_k

Tập các k-itemset phổ biến

Truyền thông điệp

MPI

minconf

minsup

OLAP

OLTP

SC

Ngưỡng tin cậy tối thiểu

Ngưỡng hỗ trợ tối thiểu

Phân tích trực tuyến

Xử lý giao dịch trực tuyến

Số đếm hỗ trợ (support count)

Độ hỗ trợ (support)

sup

T

Giao dịch (transaction)

Tid

Định danh của giao dịch

Danh sách các định danh của giao dịch

Luật kết hợp (với X là tiền đề, Y là hệ quả)

Tid-List

X ⇒Y

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 HÌNH VẼ VÀ BẢNG

Trang

Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình

Hình 1.2. Các bước của quy trình khai phá dữ liệu

Hình 1.3: Cây quyết định

3

5

7

Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu

Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy

8

Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu

Hình 2.1. Sơ đồ tổng quan của thuật toán khai phá tập mục phổ biến

Hình 2.2: Ví dụ thuật toán Apriori

14

24

28

33

51

52

54

55

56

57

61

62

63

70

Bảng 2.1.a. Thông tin của một cửa hàng bán lẻ

Bảng 2.1.b. Tập giao dịch D của cửa hàng

Hình 3.1. Mô hình song song dữ liệu

Hình 3.2. Mô hình song song thao tác

Hình 3.3. Sơ đồ thuật toán Count Distribution

Hình 3.4. Phát hi ện các tập mục phổ biến bởi thuật toán song song CD

Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution

Hình 3.6: Sơ đồ luồng thuật toán Data Distribution

Hình 3.7: Phát hi ện các tập mục phổ biến bởi thuật toán song song DD

Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu

Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở

Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P₁và P₂

Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc

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Ở ĐẦU

Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều

hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ

liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ

liệu đã 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 kho dữ liệu khổng lồ khác.

Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học

chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có

những phương pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những

thông tin bổ ích. Những “ tri thức” chiết suất từ nguồn cơ sở dữ liệu trên sẽ là

nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc

trong việc ra quyết định sản xuất kinh doanh. T iến hành công việc như vậy

chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge

Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining)

cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri

thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả

năng tích hợp các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng

thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy

được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp

dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data

Warehouse) [19, 24].

Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ biến

là phát hiện các luật kết hợp. Phương pháp này nhằm tìm ra các tập thuộc tính

thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng

của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính

khác như thế nào. Bên cạnh đó, nhu cầu song song hóa và xử lý phân tán là rất

cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc

độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu

cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp.

Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc

tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn

nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích

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

thước dữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung

lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán

song song hiệu quả cho luật kết hợp.

Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a trên

các bài báo khoa ọhc trong một số hội thảo quốc tế và các bài báo chuyên

ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật

toán khai phá luật kết hợp song song.

Nội dung luận văn được trình bày trong 3 chương và phần kết luận

Chương 1: Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá

trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ

thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu.

Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng

quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp;

các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp;

khai phá luật kết hợp với một số khái niệm mở rộng.

Chương 3: Một số phương pháp khai phá luật kết hợp song song và phân

tích đánh giá các thuật toán song song .

Thái Nguyên 01 tháng 10 năm 2008

Tác giả

Lê Thị Việt Hoa

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

Chương 1

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1. Khái niệm

Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ

80, nó là quá trình tìm kiếm, khám phá d ưới nhiều góc độ khác nhau nhằm phát

hiện các mối liên hệ, quan hệ giữa các dữ liệu, đối tượng bên trong CSDL, kết

quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại bên trong

nhưng chúng nằm ẩn ở các CSDL [3]. Về bản chất nó là giai đoạn duy nhất rút

trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm ẩn có

trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn quan trọng

nhất trong quá trình phát hiện tri thức từ CSDL, các tri thức này hỗ trợ trong việc

ra quyết định, điều hành trong khoa học và kinh doanh.

Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong các CSDL,

cụ thể hơn, đó là tiến trình 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 thông tin hữu ích từ các CSDL lớn.

1.2. Kiến trúc của một hệ thống khai phá dữ liệu

Khai phá d ữ liệu là quá trình rút trích thông tin bổ ích từnhững kho dữ liệu lớn.

Khai phá d ữ liệu là quátrình chính trong khai phá tri th ức từ cởơdsữ liệu.

Kiến trúc của một hệ thống khai phá dữ liệu có các thành[2] phần như sau:

Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình

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

• CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các tập

CSDL, các khi dữ liệu, các trang tính hay các dạng khác của thông tin được lưu trữ.

Các kỹ thuật làm sách dữ liệu và tích hợp dữ liệu có thể được thực hiện.

• Máy chủ CSDL (Database or Warehouse Server): Máy chủ có trách

nhiệm lấy những dữ liệu thích hợp dựa trên những yêu cầu khám phá của người

dùng.

• Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để tìm kiếm

hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có thể

bao gồm một sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá

trị thuộc tính ở các mức trừu tượng khác nhau.

• Máy khai phá dữ liệu (Data mining engine): là một hệ thống khai phá

dữ liệu cần phải có một tập các Modul chức năng để thực hiện công việc, chẳng

hạn như kết hợp, phân lớp, phân cụm.

• Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tương tác với các

Modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng được quan

tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được.

Cũng có thể Modul đánh giá mẫu được tích hợp vào Modul khai phá dữ liệu,

tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng.

• Giao diện đồ họa cho 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 khai phá dữ liệu. Thông qua

giao diện này người dùng tương tác với hệ thống bằng cách đặc tả một yêu cầu

khai phá hay một nhiệm vụ, c ung cấp thông tin trợ giúp cho việc tìm kiếm và

thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. 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,

các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau.

1.3. Các giai đoạn của quá trình khai phá dữ liệu

Các thuật toán khai phá dữ liệu thường được mô tả như những chương

trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và

thống kê trước đây, bước đầu tiên là thuật toán thường nạp toàn bộ tệp (file) dữ

liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến

việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không

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

chỉ bởi nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn khó có thể chiết

xuất dữ liệu ra các tệp đơn giản để phân tích.

Thống kê tóm tắt

Xác

định

nhiệm

vụ

Thu thập

và tiền

xử lý dữ

liệu

Xác

định dữ

liệu liên

quan

Giải thuật

khai phá

dữ liệu

Mẫu

DL trực

tiếp

Hình 1.2. Các bước của quy trình khai phá dữ liệu

Quá trình xử lý khai phá dữ liệu bắt đầu bằng việc xác định chính xác vấn

đề cần giải quyết. Sau đó sẽ xác định dữ liệu liên quan dùng để xây dựng giải

pháp. Tiếp theo là thu thập dữ liệu có liên quan và xử lý chúng thành dạng sao

cho thuật toán khai phá dữ liệu có thể hiểu được.

Quá trình khai phá dữ liệu [2] trải qua ba bước:

Bước một: Lọc dữ liệu được thực hiện trong quá trình tiền xử lý. Công

việc đầu tiên là tích hợp và chỉnh sửa dữ liệu. Khi dữ liệu được thu thập từ nhiều

nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ

liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau

khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn.

Ví dụ, trong bài toán tìm quy luật mua hàng của khách hàng trong một

siêu thị, ta tìm xem khách hàng thường cùng mua những mặt hàng nào để sắp

xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể

có nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng,

nhà cung cấp, đơn giá hàng, người bán hàng… Các dữ liệu này cần cho quản lý

bán hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này

khỏi dữ liệu trước khi khai phá dữ liệu.

Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán

khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu.

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

Bước ba: Sau xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu

của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ

liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước lượng

bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta

phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn.

1.4. Một số kỹ thuật khai phá dữ liệu

Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh

doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai

phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát

hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến

hoặc các đối tượng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán

được những giá trị chưa biết hoặc những giá trị tương lai của các biến đáng quan

tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có

thể hiểu được.

Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu

bao gồm như sau:

Phân lớp dữ liệu [24]

Khái niệm phân lớp dữ liệu được Han và Kamber đưa ra năm 2000. Phân

lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tượng thành những

lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá

trị của dữ liệu sẽ xuất hiện trong tương lai.

Quá trình phân lớp dữ li ệu được thực hiện qua hai bước. Bước thứ nhất:

Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc

trưng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám

sát, học theo mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu

hoặc những khái niệm đã được xác định trước, dự đoán giá trị của những đối

tượng quan tâm.

6

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ột kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định.

Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ

thuật này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán.

Một ví dụ tiêu biểu về cây quyết định:

Tuổi

TID

30-35

Yes

>35

Giáo sư

Sinh viên

No

Yes

Hình 1.3: Cây quyết định

Yes

No

Trong hình 1.3 là một cây quyết định cho lớp mua laptop, chỉ ra một

khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà

đánh giá mua laptop là Yes hay No. Sau khi mô hình này được xây dựng, chúng

ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc

tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng

rộng rãi trong nhiều hoạt động của đời sống thực.

Phân nhóm dữ liệu [13, 24]

Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu.

Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá

trình nhóm nhữn g đối tượng vào trong những lớp tương đương, đến những đối

tượng trong một nhóm là tương đương nhau, chúng phải khác với những đối

tượng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về

lớp nào là phải xác định trước, trong khi phân nhóm không xác định trước.

Trong phân nhóm, những đối tượng được nhóm lại cùng nhau dựa vào sự giống

nhau của chúng. Sự giống nhau giữa những đối tượng được xác định bởi những

chức năng giống nhau. Thông thường những sự giống nhau về định lượng như

khoảng cách hoặc độ đo khác được xác định bởi những chuyên gia trong lĩnh

vực của mình.

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

Nợ

nhóm 2

nhóm 1

+

nhóm 3

Thu nhập

Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu

Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị

trường. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp

có thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận

lợi. Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách

hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau.

Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tương ứng cho việc

mua nhà, mua xe, … Trong trờưng hợp này ngân hàng có thể cung cấp những

dịch vụ tốt hơn, và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể

thu hồi được. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật

toán phân nhóm trong.

Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một

biến dự đoán có giá tịr thực. Nhiệm vụ hồi qui tương tự như phân lớp, điểm

khác nhau chính làở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc [13,

23]. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê

cổ điểm chẳng hạn như hồi qui tuyến tính. Tuy nhiên, phương pháp mô hình hóa

cũng được sử dụng [13, 24].

Nợ

đường hồi quy

tuyến tính

0

+

0

+

0

+

0

+

0

+

Thu nhập

Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy

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

Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát

quang hiện thời trong khi rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến

từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm

chuẩ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… hình 1.5 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, ở đây tổng

số nợ được điều chỉnh cho phù hợp giống như một hàm thu nhập tuyến tính.

Việc điều chỉnh này là không đáng kết bởi vì chỉ tồn tại một tương quan yếu

giữa hai biến.

Tổng hợp (summarization): Là công việc liên quan đến các phương pháp tìm

kiếm một mô tả cô đọng cho tập con dữ liệu [23, 24]. Các kỹ thuật tổng hợp

thường được áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự

động.

Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô hình mô

tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại ở hai mức:

 Mức cấu trúc của mô hình (thường dưới dạng đồ thị) xác định các biến phụ

thuộc cục bộ vào các biến khác;  Mức định lượng của mô hình xác định mức

độ phụ thuộc của các biến [13, 24]. Những phụ thuộc này thường được biểu thị

dưới dạng luật.

Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy [24].

Đó là đồ thị có hướng không có dạng chu trình, các nút biểu diễn thuộc tính và

trọng số chỉ liên kết phụ thuộc giữa các nút đó.

Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ

này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các

giá trị chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung

của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch thường dùng là

lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có

nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ

liệu trong hai tập con dữ liệu, tính cả trường hợp tập con của đối tượng này

thuộc tập con kia, nghĩa là xác định dữ liệu trong một nhóm con của đối tượng

có khác nhau đáng kể so với toàn bộ đối tượng [13, 24].

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.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu

Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ

liệu thành các loại khác nhau.

Cơ sở dữ liệu quan hệ

Đến nay, hầu hết dữ liệu được lưu giữ dưới dạng cơ sở dữ liệu quan hệ.

Cơ sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tượng

mà chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu được

mô tả bởi một tập những thuộc tính và lưu trong những bảng. Khai phá dữ liệu

trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ

liệu của một ngân hàng, ta có thể tìm được những khách hàng có mức chi tiêu

cao, ta có thể phân loại những khách hàng này dựa vào quá trình chi tiêu của họ.

Cũng với việc phân tích những mục chi tiêu của khách hàng, chúng ta có thể

cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử

rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu được phép,

ngân hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng

thời trang.

Cơ sở dữ liệu giao tác

Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các

trường hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ

chức. Với tính phổ biến của máy tính và thương mại điện tử, ngày nay có rất

nhiều cơ sở dữ liệu giao tác. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập

trung vào khai phá luật kết hợp, tìm mối tương quan giữa những mục dữ liệu

của bản ghi giao dịch. Nghiên cứu sâu về cơ sở dữ liệu giao tác được mô tả chi

tiết ở phần sau.

Cơ sở dữ liệu không gian

Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu

quan hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý.

Những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các

đặc trưng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có

dạng X ⇒ Y, với X, Y là tập hợp những vị từ không gian. Những thuật toá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

khai phá luật kết hợp không gian tương tự như khai phá luật kết hợp nhưng thêm

những vị từ về không gian.

Cơ sở dữ liệu có yếu tố thời gian

Giống như cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao

gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là

thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có

yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. Ví dụ, từ luật

kết hợp cơ bản {Bia} ⇒ {Thuốc lá}, với dữ liệu có yếu tố thời gian chúng ta có

thể có nhiều luật: Độ hỗ trợ của luật {Bia} ⇒ {Thuốc lá} là 20% từ 9 giờ đến

13 giờ, là 50% trong thời gian 19 giờ tới 22 giờ. Rõ ràng rằng, những người bán

lẻ có thể xác định chiến lược để buôn bán tốt hơn.

Hầu hết nghiên cứu về lĩnh vực này ngày nay hình thành một hướng khai

phá dữ liệu mới gọi là khai phá mẫu lặp liên tục, khai phá tập mục dữ liệu

thường xuyên trong cơ sở dữ liệu thời gian.

Cơ sở dữ liệu đa phương tiện

Số lượng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi,

duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang phát

triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đ ã trở thành một lĩnh

vực nghiên cứu chính của khai phá dữ liệu, được các nhà nghiên cứu đặc biệt quan tâm.

Khai phá d ữ liệu web thông thường được chia thành ba phạm trù chính: Khai phá cách

dùng web (web usage mining), khai phá c ấu trúc web (web structure mining) và khai

phá n ội dung web (web content mining).

Khai phá cách dùng web tập trung vào việc khai phá thông tin của người

truy nhập web. Với những thông tin này người khai phá dữ liệu có thể cung cấp

những thông tin hữu ích cho người dùng và các nhà kinh doanh.

1.6. Các phương pháp chính trong khai phá d ữ liệu

• Phân lớp và dự đoán (Classification & Prediction)

Xếp một đối tượng vào một trong những lớp đa biết. Ví dụ : phân ớl p

vùng địa lý theo dữ liệu thời tiết. Đối với hướng tiếp cận này thường áp dụng

một số kỹ thuật như học máy (Machine learning), cây quyết định (Decision

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

tree), mạng nơron nhân tạo (Neural network). Với hướng này, người ta còn gọi

là học có giám sát hạy học có thầy (Supervised learning).

• Phân cụm và phân đoạn (Clusterring and Segmentation)

Sắp xếp các đối tượng theo từng cụm (số lượng và tên của cụm chưa

được biết trước). Các đối tượng được gom cụm sao cho mức độ tương tự giữa

các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối

tượng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán phân cụm còn

được gọi là học không giám sát hạy học không thầy.

• Luật kết hợp (Association rules)

Luật kết hợp là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Mục tiêu

của phương pháp này là phát hệi 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 của giải thuật khai phá dữ liệu là tập luật kết

hợp tìm được.

Ví dụ về luật kết hợp: Một cửa hàng bán văn phòng phẩm đăng thông tin

quảng cáo mỗi tuần trên một tờ báo địa phương. Khi một mặt hàng, chẳng hạn

như mực in đã được chỉ định bán giảm giá, người bán hàng xác định các mặt

hàng khác nào sẽ được mua cùng lúc với mực in. Họ thấy rằng giấy A4 và mực

in được khách hàng mua cùng chiếm 30% và kẹp giấy được mua kèm với mực

in là 40%. Dựa vào các mối quan hệ này, người bán hàng bày bán giấy A4 và

kẹp giấy gần với mặt hàng mực in khi bán giảm giá. Họ cũng quyết định không

đưa các mặt hàng này vào danh sách các mặt hàng giảm giá. Các hành động này

nhằm mục đích tăng thêm toàn bộ khối lượng hàng bán ra bởi việc bán các mặt

hàng mua mực in.

Có 2 luật kết hợp được đề cập ở ví dụ trên. Luật thứ nhất là: “30% khách

hàng mua mực in lẫn giấy A4 ”. Luật thứ hai là: “40% khách hàng khi mua mực

in thì cũng mua kẹ p giấy”. Các luậ t kết hợp này thường được sử dụng bởi các

cửa hàng bán lẻ để phân tích các giao dịch của cửa hàng. Đối với người quan lý

kinh doanh, các luậ t kết hợp được phát hiện có thể được dùng trong chiến dịch

12

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

quảng cáo, tiếp thị, quản lý hàng tồn kho và dự trữ hàng. Các luật kết hợp cũng

được sử dụng cho các ứng dụng khác như dự đoán lỗi, cho các mạng điện thoại

bằng việc xác định các sự kiện xuất hiện trước đó.

• Khai phá chuỗi theo thời gian (Sequential temporal patterns)

Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính

thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực

tài chính và thị trường chứng khoán bởi vì chúng có tính dự báo cao.

• Mô tả khái niệm và tổng hợp hóa (Summarization)

Liên quan đến các phương pháp tìm kiếm một mô tả cho một tập con dữ

liệu. Các kỹ thuật toán tắt thường được áp dụng cho các phân tích dữ liệu tương

tác có tính thăm dò và tạo báo cáo tự động.

1.7. Các ứng dụng của khai phá dữ liệu

Khai phá dữ liệu tuy là một lĩnh vực mới nhưng đã thu hút được sự quan

tâm của rất nhiều nhà nghiên cứu, nhờ có nhiều những ứng dụng trong thực tiễn,

các ứng dụng điển hình, có thể liệt kê như sau:

- Phân tích dữ liệu và hỗ trợ ra quyết định (Analysis & decition support).

- Điều trị trong y học (Medical): mối liên hệ giữa triệu chứng, chuẩn đoán

và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật).

- Phân lớp văn bản, tóm tắt văn bản và phân lớp các trang Web (Text

mining & Web mining).

- Tin sinh học (Bio-informatics): Tìm kiếm, đối sánh các hệ gen và thông

tin di truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền.

- Nhận dạng.

- Tài chính và thị trường chứng khoán (Finance & stock market): Phân

tích tình hình tài chính và dự đoán giá cổ phiếu.

- Bảo hiểm (Insurance).

- Giáo dục (Education).

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

1.8. Khai phá dữ liệu và các lĩnh vực liên quan

Thống kê

Máy móc, trí

tuệ nhân tạo

Cơ sở dữ liệu

Thương mại

Y tế

Tài chính,

ngân hàng

Khai phá dữ liệu

Thuật toán học

Các ngành

khoa học khác

Giáo dục

Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu

Phát hiện tri thức và khai phá dữ liệu được coi là trung tâm của nhiều

ngành khoa học, nó liên quan đến rất nhiều ngành, nhiều lĩnh vực khác nhau

như tài chính, ngân hàng, thương mại, y tế, giáo dục, thống kê, máy móc, trí tuệ

nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song, thu nhận tri thức

trong các hệ chuyên gia, quan sát dữ liệu.

Lĩnh vực học máy và nhận dạng mẫu là giống nhau trong khai phá dữ liệu

nghiên cứu các lý thuyết và thuật toán của hệ thống trích ra các mẫu và mô hình

dữ liệu. Khai phá dữ liệu tập trung vào việc mở rộng các lý thuyết và thuật toán

cho các vấn đề về tìm ra các mẫu đặc biệt, đây được coi là những mẫu hữu ích

hoặc tri thức quan trọng tập dữ liệu lớn.

Đặc biệt, phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực

thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện

các mẫu, luật…, kho dữ liệu và các công cụ xử lý trực tuyến (OLAP – online

analytical processing) ậtp trung vào phân tích dữ liệu đa chiều, tốt hơn SQL

trong tính toán và phân tích thống kê đa chiều cũng liên quan chặt chẽ đến khai

phá dữ liệu.

Đặc trưng của hệ thống khai phá dữ liệu là nhờ vào các phương pháp

thuật toán và kỹ thuật từ những lĩnh vực khác nhau, nhằm mục đích cuối cùng là

trích ra tri thức từ dữ liệu trong CSDL khổng lồ.

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

1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu

Khai phá dữ liệu ngày càng đóng một vai trò quan trọng trong việc tìm ra

các tri thức thực sự có ích, hiệu quả tiềm ẩn trong các khối dữ liệu thông tin

khổng lồ vẫn hàng ngày đang được thu thập, lưu trữ để giúp các cá nhân và tổ

chức đưa ra được các quyết định chính xác và nhanh chóng. Tuy đã có rất nhiều

các giải pháp và phương pháp được ứng dụng trong khai phá dữ liệu nhưng trên

thực tế quá trình này vẫn gặp không ít khó khăn và thách thức như:

- Cơ sở dữ liệu lớn

- Số chiều các thuộc tính lớn

- Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hệin

không còn phù hợp

- Dữ liệu bị thiếu hoặc bị nhiễu

- Quan hệ giữa các trường phức tạp

- Giao tiếp với người sử dụng và kết hợp với các tri thức đã có

- Tích hợp với các hệ thống khác

Cơ sở dữ liệu lớn có thể lớn về số lượng các bản ghi, lớn về số lượng các

thuộc tính trong CSDL. Số lượng các bản ghi trong CSDL lớn có khi dung

lượng tới hàng gigabyte, terabyte; số các thuộc tính trong CSDL có thể rất nhiều

và đa dạng. Để giải quyết vấn đề này, người ta thường đưa ra một ngưỡng nào

đó cho CSDL bằng các cách như chiết xuất mẫu, xấp xỉ hoặc xử lý song song.

Trong CSDL khi mà ốs các thuộc tính là rất lớn , cùng với số lượng lớn

các bản ghi sẽ dẫn đến kích thước độ phức tạp của bài toán tăng lên. Vì vậy,

không gian tìm kếim, không gian trạng thái gia tăng, n hiều mẫu hay mô hình

thừa, trùng lặp phát sinh nhiều luật thừa, đây được coi là vấn đề nan giải trong

quá trình khai phá dữ liệu. Nhằm giải quyết được những vấn đề trên , phải sử

dụng một số các tri thức đã biết trước để loại bỏ và trích lọc ra những dữ liệu

thích hợp với yêu cầu của bài toán.

15

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

Vấn đề dữ liệu bị thay đổi phụ thuộc theo thời gian, có nghĩa là dữ liệu bị

ảnh hưởng và phụ thuộc vào thời điểm quan sát, lấy mẫu, thời điểm khai phá.

Kết quả đạt được sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu,

như các mẫu được khai phá ở bước trước, có thể không còn giá trị hay vô nghĩa

đối với thời điểm sử dụng, hoặc có thể làm nhiễu hay phát sinh hiệu ứng phụ

làm sai ệl ch kết quả. Để khắc phục được vấn đề này cần phải chuẩn hóa, cải

tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi này là mục đích

của khai phá và tìm kiếm các mẫu bị thay đổi.

Thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị

trong các mềin thuộc tính đã làm ảnh hưởng rất lớn trong khai phá dữ liệu .

Trong quá trình khai phá dữ liệu, khi các hệ thống tương tác với nhau phụ thuộc

nhau mà thếiu vắng một vài giá trị nào đó , sẽ dẫn đến các mẫu không được

chính xác, bị thiếu, không đầy đủ. Để giải quyết cho vấn đề này, người ta coi sự

thiếu vắng của các dữ liệu này là giá trị ẩn, chưa biết và có thể được tiên đoán

bằng một số phương pháp nào đó.

Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần

được quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối liên

hệ phức tạp với nhau trong CSDL đòi hỏi khai phá dữ liệu phải có các giải pháp,

các kỹ thuật để có thể áp dụng được, nhận ra được các mối quan hệ này trong

quá trình khai phá dữ liệu.

1.10. Kết luận chương 1

Các tri thức tiềm ẩn trong các CSDL có ý nghĩa rất lớn trong nhiề u lĩnh

vực vì vậy việc phát hiện, rút trích tự động các tri thức ẩn từ các tập hợp dữ liệu

lớn thông qua các mẫu, mô hình dữ liệu càng đóng một vai trò hết sức quan

trọng, đặc biệt là trong bối cảnh hiện nay khi mà sự phát triển nhanh chóng của

các ứng dụng công nghệ thông tin ở nhiều ngành nghề trong đời sống xã hội ,

ngày càng ạto ra nhiều CSDL khổng lồ. Chương này trình bày tóm tắt các

phương pháp khai phá dữ liệu phổ biến, các thành phần chủ yếu của một giải

thuật khai phá dữ liệu và những thành tựu cũng như những thách thức trong khai

phá dữ liệu. Trong các phương pháp khai phá dữ liệu, khai phá các luật kết hợp

là một trong những lĩnh vực đang được quan tâm và nghiên cứu mạnh mẽ.

16

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

2.1. Mở đầu

Khai phá dữ liệu là quá trình phát hiện ra các thômg tin có giá trị tiềm ẩn

trong CSDL và được xem như là một công đoạn trong quá trình khai thác tri

thức. Chức năng của khai phá dữ liệu bao gồm phân lớp, phân cụm, dự đoán và

phân tích kết hợp. Ứng dụng khai phá kết hợp là một trong những ứng dụng

quan trọng của khai phá dữ liệu. Luật kết hợp được giới thiệu đầu tiên vào năm

1993 [19], được sử dụng để xác định các mối quan hệ giữa các tập thuộc tính

trong CSDL. Việc xác định các quan hệ này không được dựa vào các đặc tính

dữ liệu vốn có của chúng (như các phụ thuộc hàm), mà nên dựa vào sự xuất hiện

cùng lúc của các thuộc tính dữ liệu.

Ví dụ 1.1

Trong một hiệu sách lưu lại các phiếu mua sách, người ta phát hiện ra

rằng: Trong số những người mua quyển "Các khái niệm và kỹ thuật khai phá dữ

liệu" thì có 40% số người đó mua thêm quyển " Hệ quảntrị cơ sở dữ liệu", và

25% mua thêm quyển "Kho dữ liệu".

Trong ví dụ trên, tìm được hai luật kết hợp:

- Có 40% số người mua quyển " Các khái niệm và kỹ thuật khai phá dữ

liệu" thì đồng thời mua quyển "Hệ quản trị cơ sở dữ liệu".

- Có 25% số người mua quyển " Các khái niệm và kỹ thuật khai phá dữ

liệu" thì đồng thời mua quyển "Kho dữ liệu".

Với những quy tắc được khám phá trên, ta có thể sắp xếp các quyển sách

có liên quan với nhau ở v ị trí gần nhau để giúp cho người mua sách thuận tiện

hơn. Những quy tắc đó cũng giúp cho nhà sách có chiến lược kinh doanh tốt

hơn.

Luật kết hợp được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau như:

Kinh doanh, sản xuất, giao thông, viễn thông, giáo dục, quản lý thị trường, …

17

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

Luật kết hợp cho biết phạm vi mà trong đó, sự xuất hiện của tập các thuộc

tính A nào đó trong các bản ghi của CSDL D sẽ kéo theo sự xuất hiện của tập

các thuộc tính khác B, cũng trong những bản ghi đó, có dạng A ⇒ B. Mỗi luật

kết hợp được đặc trưng bởi một cặp tỷ lệ đó, là độ hỗ trợ và độ tin cậy. Thông

tin mà luậ t kết hợp mang lại là rất to lớn và hỗ trợ đáng kể cho quá trình ra

quyết định trong kinh doanh cũng như trong nghiên cứu khoa học.

2.2 Luật kết hợp

2.2.1 Các khái niệm cơ bản [18, 22]

Đặt: I = {i₁,…,i_n}: tập n mục (Item, còn gọi là thuộc tính) phân biệt.

D: CSDL giao dịch

Mỗi giao dịch (Transaction - còn gọi là bản ghi - record) T ∈ D được

định nghĩa như một tập con các mục trong I (T ⊆ I) và có một định danh duy

nhất có dạng <TID, i₁,…, i_k>.

Một giao dịch T ∈ D hỗ trợ cho tập mục X, X ⊆ I nếu nó chứa tất cả các

mục của X, nghĩa là X ⊆ T, trong một số trường hợp người ta dùng ký hiệu

T(X) để chỉ tập các giao dịch hỗ trợ cho X. Ký hiệu sup(X) (support(X) hoặc

s(X)) là tỷ lệ phần trăm của các giao dịch hỗ trợ X trên tổng các giao dịch có

trong D, nghĩa là:

{

T ∈ D | X ⊆ T

}

sup(X) = P_r(X) =

(2.1)

| D |

Ta có 0 ≤ sup(X) ≤ 1 với mọi tập mục X.

Định nghĩa 2.1: Cho một tập X ⊆ I và một ngưỡng hỗ trợ tối thiểu

(minimum support) minisup∈ (0,1] (được xác định bởi người sử dụng). Một tập

mục X được gọi là một tập mục phổ biến (Frequent Itemset hoặc Large Iteset)

với độ hỗ trợ tối thiểu minsup nếu và chỉ nếu sup(X) ≥ minsup.

Một tập mục phổ biến được sử dụng như là một tập đáng quan tâm trong

các thuật toán, ngược lại, những tập mục không phải tập mục phổ biến là những

tập không đáng quan tâm. Trong các trình bày sau này, ta sử dụng những cụm từ

18

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

khác như ‘‘X có độ hỗ trợ tối thiểu ’’ , ‘‘X không có độ hỗ trợ tối thiểu ’’ cũng

chỉ để nói lên X thỏa mãn hay không thỏa mãn sup(X) ≥ minsup.

Một tập mục X được gọi là k-itemset nếu lực lượng của X bằng k (tức

làX= k).

Một số tính chất liên quan đến tập mục phổ biến:

Tính chất 2.1: Nếu A ⊆ B, A, B là các tập mục thì sup(A) ≥ sup(B) vì tất

cả các giao dịch của D hỗ trợ B thì cũng hỗ trợ cho A.

Tính chất 2.2: Một tập mục B không có độ hỗ tối thiểu trên D nghĩa là

sup(B) < minsup thì mọi tập cha A của B sẽ không phải là tập mục phổ biến vì

sup(A) ≤ sup(B) < minsup.

Tính chất 2.3: Nếu tập mục B là một tập mục phổ biến trên D, nghĩa là

sup(B) ≥ minsup thì mọi tập con A của B đều là tập phổ biến trên D vì

sup(A) ≥ sup(B) > minsup.

Định nghĩa 2.2: Một luật kết hợp là một quan hệ có dạng X ⇒Y, trong

đó X, Y ⊂ I là tập các mục còn gọi là itemset, và X ∩Y = φ . Ở đây, X được gọi

là tiền đề, Y là hệ quả của luật.

Hai thông số quan trọng của luật kết hợp là độ hỗ trợ và độ tin cậy.

Định nghĩa 2.3: Độ hỗ trợ (support) của luận kết hợp X ⇒ Y là tỷ lệ phần

trăm giữa các giao dịch chứa X ∪ Y và tổng số các giao dịch trong CSDL.

{

T ∈ D | X ∪Y ⊆ T

}

sup(X ⇒ Y) = P_r(X ∪ Y ) =

(2.2)

| D |

Bởi vậy, ta nói độ hỗ trợ của luật bằng 5% nghĩa là có 5% tổng số giao

dịch có chứa X ∪ Y. Độ hỗ trợ mang ý nghĩa thống kê của luật kết hợp. Trong

khi, một độ hỗ trợ cao cho luật kết hợp thường được mong muốn nhất, tuy nhiên

điều đó không phải luôn luôn đúng. Ví dụ, nếu ta sử dụng luật kết hợp để dự

đoán thất bại các nút chuyển mạch trong mạng điện thoại dựa vào tập sự kiện

nào đó xuất hiện trước một thất bại, mặc dù hai sự kiện này không thường xuyên

xuất hiện, các luật kết hợp chỉ ra quan hệ này vẫn có tầm quan trọng đáng kể.

19

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

Định nghĩa 2.4: Đối với một số giao dịch được đưa ra, độ tin cậy

(confidence) của luật kết hợp X ⇒ Y là tỷ lệ phần trăm giữa số giao dịch có

chứa X ∪ Y và số giao dịch chứa X.

p(Y ⊆ T ∧ X ⊆ T) sup(X ∪Y)

conf (X ⇒ Y) = p (Y ⊆ I X ⊆ I) =

(2.3)

=

p(X ⊆ T)

sup(X )

Vì vậy, nếu ta nói rằng một luật có độ tin cậy conf = 85% có nghĩa là 85%

các giao dịch hỗ trợ cho X thì cũng hỗ trợ cho Y. Độ ti n cậy của luật cho biết

mức độ tương quan trong tập dữ liệu (dataset) giữa hai tập mục X và Y và là

tiêu chuẩn đánh giá độ tin cậy của một luật.

Việc khai thác các luật kết hợp từ cơ sở dữ liệu D chính là việc tìm tất cả các luật

có độ hỗ trợ và độ tin cậy lớn hơnngưỡng hỗ trợ (độ hỗ trợ tối thiểu) và ngưỡng tin cậy

(độ tin cậy tối thiểu) do ngư ời sử dụng xác định trước. Ngưỡng hỗ trợ và ngưỡng tin cậy

lần lượt được ký hiệu là minsup và mincof. Chú ý r ằng, nếu luật X⇒ Y th ỏa mãn trên D

thì c ả X và Y đềulà các t ập mục phổ biến trên D.

Một số tính chất liên quan đến luật kết hợp

Tính chất 2.4: Nếu X ⇒ Z và Y ⇒ Z là thỏa mãn trên D thì không nhất

thiết X ∪ Y ⇒ Z là đúng.

Xét trư ờng hợp X∩Y = ∅ và các giao d ịch trong D có hỗ trợ cho Z nếu và chỉ

nếu chúng chỉ chứa X hoặc Y, khi đó conf(X ∪ Y ⇒ Z) = 0. Tương t ự, ta c ũng có: Nếu

X ⇒ Y và Z ⇒ Z thỏa mãn trên D thì cũng không thể suy ra X⇒ Y ∪ Z.

Tính chất 2.5: Nếu luật X ∪ Y ⇒ Z thỏa mãn trên D thì không nhất thiết

X ⇒ Z và Y ⇒ Z thỏa mãn trên D.

Chẳng hạn, khi Z có mặt trong giao dịch chỉ khi cả X và Y đều có mặt

trong giao dịch đó, nghĩa là sup(X ∪ Y) =sup(Z). Nếu sup(X) ≥ sup(X ∪ Y) và

sup(Y) ≥ sup(X ∪ Y) thì 2 luật trên sẽ không có độ tin cậy yêu cầu.

Tuy nhiên, nếu X ⇒ Y ∪ Z thỏa mãn trên D thì suy ra được X ⇒ Y và

X ⇒ Z cũng thỏa mãn trên D.

Tính chất 2.6: Nếu X ⇒ Y và Y ⇒ Z thỏa mãn trên D thì không thể

khẳng định X ⇒ Z cũng thỏa mãn trên D.

20

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

Giả sử T(X) ⊆ T(Y) ⊆ T(Z) và conf(X ⇒ Y) = conf(Y ⇒ Z) = minconf.

Khi đó, ta có conf(X ⇒ Z) = minconf²< minconf vì minconf< 1, nghĩa là luật

X ⇒ Z không có độ tin cậy tối thiểu.

Tính chất 2.7: Nếu luật X ⇒ (L - X) không có độ tin cậy tối thiểu thì

không có luật nào trong các luật Y ⇒ (L – Y) có độ tin cậy tối thiểu, trong đó

Y ⊆ X ; X,Y ⊂ L.

Thật vậy, theo tính chất 2.1, vì Y ⊆ X nên sup(Y) ≥ sup(X) và theo định

nghĩa độ tin cậy, ta có:

sup port(L) sup port(L)

confidence(Y ⇒ (L – Y)) =

≤

< minconf

sup port(Y) sup port(X )

Nếu luật (L – X) ⇒ X thỏa mãn trên D thì các luật (L – Y) ⇒ Y với

Y ⊆ X và Y ≠ ∅ cũng thỏa mãn trên D.

2.2.2. Khai phá luật kết hợp

Trong m ục này sẽ giới thiệu chi tiết bài toán khai phá luật kết hợp (Association

Rule Mining). Nh ững kết quả khác nhau trong khai phá luật kết hợp sẽ được trình bày

chi ti ết cùng với những thuật toán và những ví dụ kinh điển.

Bài toán khai phá luật kết hợp trên một cơ sở dữ liệu được chia thành hai

bài toán nhỏ. Bài toán thứ nhất là tìm tất cả các tập mục dữ liệu có độ hỗ trợ

thỏa ngưỡng tối thiểu cho trước, gọi là tập các tập mục dữ liệu thường xuyên.

Bài toán thứ hai là tìm ra những luật kết hợp từ những tập mục dữ liệu thường

xuyên thỏa độ tin cậy tối thiểu cho trước.

Bài toán thứ hai được giải quyết như sau: Giả sử ta có tập các mục dữ liệu

thường xuyên L_k, với L_k=

{

x_i, x_i,..., x_i

, những luật kết hợp theo ngưỡng tin

}

1

2

k

cậy tối thiểu C₀với những mục dữ liệu thường xuyên này được phát sinh ra

bằng cách:

{

x_i,x_i,...,x_i

}

→

{

x_i

Luật thứ nhất:

^}, kiểm tra độ tin cậy của luật này có

1

2

k−1

k

thỏa ngưỡng tin cậy tối thiểu cho trước hay không.

{

x_i,x_i,...,x_i,x_i

}

→

{

x_i

Luật thứ hai:

^}, kiểm tra độ tin cậy của luật này có

1

2

k−2

k

k−1

thỏa ngưỡng tin cậy tối thiểu cho trước hay không.

21

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

{

x_i,x_i,...,x_i

}

→

{

x_i,x_i

Luật thứ k+1:

^}, kiểm tra độ tin cậy của luật này có

1

2

k−2

k−1

k

thỏa ngưỡng tin cậy tối thiểu cho trước hay không.

Tổng quát: ∀X ⊂ L_k, ta kiểm tra độ tin cậy của luật X → L_k\ X có thỏa

ngưỡng tin cậy tối thiểu cho trước hay không.

Bài toán th ứ hai là đơn giản, hầu hết nghiên cứu về luật kết hợp tập trung ở bài

toán th ứ nhất. Sau đây chúng ta tập trung giải quyết bài toán thứ nhất.

2.2.3. Cách tiếp cận khai phá luật kết hợp

Khai phá luật kết hợp là một lĩnh vực nghiên cứu được nhiều người quan

tâm và có nhiều kết quả đã được công bố. Ở đây chỉ giới thiệu một số cách tiếp

cận kinh điển và cơ bản, làm cơ sở để phát triển các thuật toán mới.

Bài toán thứ nhất có thể chia nhỏ hơn nữa thành hai bài toán: Tìm các tập

mục dữ liệu ứng viên và tìm các tập mục dữ liệu thường xuyên. Tập mục dữ liệu

ứng viên là những tập mục dữ liệu, mà ta phải tính độ hỗ trợ để xem nó có phải

là tập mục dữ liệu thường xuyên hay không. Tập mục dữ liệu thường xuyên là

những tập mục dữ liệu có độ hỗ trợ lớn hơn hay bằng ngưỡng tối thiểu cho

trước. Phát triển thuật toán khai phá luật kết hợp, là làm giảm độ phức tạp tính

toán của thuật toán để cải thiện tốc độ xử lý.

Ta có thể phân loại các thuật toán tìm tập thường xuyên theo hai tiêu chí:



Phương pháp duyệt qua không gian tìm kiếm

Phương pháp xác định độ hỗ trợ của tập mục dữ liệu.

Với phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách:

Duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu

(Depth First Search – DFS).

Duyệt theo chiều rộng là duyệt qua dữ liệu nguyên bản, để tính độ hỗ trợ

của tất cả các tập ứng viên có k-1, mục dữ liệu trước khi tính độ hỗ trợ của các

tập ứng viên có k mục dữ liệu. Một cơ sở dữ liệu có n mục dữ liệu, trong lần lặp

thứ k để tìm những tập k-mục dữ liệu ứng viên, phải kiểm tra tất cả

n!

C^k_n=

tập k-mục dữ liệu.

k!(n − k)!

22

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

Duyệt theo chiều sâu, là duyệt qua cơ sở dữ liệu đã được chuyển thành

cấu trúc cây, quá trình duyệt được gọi đệ quy theo chiều sâu của cây.

Với cơ sở dữ liệu có n mục dữ liệu, I = {x₁, x₂, …, x_n}, thì không gian tìm

kiếm là tập tất cả các tập con của I, đây là bài toán NP khó, nếu không có

phương pháp duyệt thích hợp thì bài toán không giải được khi n đủ lớn.

Phương pháp xác định độ hỗ trợ của tập mục dữ liệu X ⊆ I được phân làm

hai cách: Cách thứ nhất: Đếm số giao tác trong cơ sở dữ liệu chứa X. Cách thứ

hai: Tính phần giao của các tập định danh giao tác chứa X.

Phát biểu bài toán phát hiện luật kết hợp

Cho một tập các mục I, một cơ sở dữ liệu giao dịch D, ngưỡng hỗ trợ

minsup, ngưỡng tin cậy minconf. Tìm tất cả các luật kết hợp X ⇒Y trên CSDL

D sao cho: sup(X ⇒ Y) ≥ minsup và conf(X ⇒ Y) ≥ minconf. Bài toán khai thác

luật kết hợp có thể được chia ra làm 2 bài toán con được phát biểu trong thuật

toán sau:

Nội dung thuật toán

Vào: I, D, minsup, minconf

R: Các luận kết hợp thỏa mãn minsup và minconf

Phương thức:

(1) Tìm tất cả các tập mục phổ biến từ CSDL D tức là tìm tất cả các tập

mục có độ hỗ trợ lớn hơn hoặc bằng minsup.

(2) Sinh ra các luật từ các tập mục phổ biến (large itemsets) sao cho độ

tin cậy của luật lớn hơn hoặc bằng minconf.

Bước 1: Tìm các tập mục phổ biến như được mô tả trong hình 2.1.

Bước 2: Sinh các luật kết hợp từ tập mục phổ biến tìm được ở bước 1.

Tùy theo ngữ cảnh các thuộc tính dữ liệu, cũng như phương pháp sử dụng

trong các thuật toán; người ta có thể phân bài toán khai phá luật kết hợp ra nhiều

nhóm khác nhau. Chẳng hạn, nếu giá trị của các thuộc tính có kiểu boolean thì

ta gọi là khai phá luật kết hợp Boolean (Mining Boolean Association Rules) …

2.3 Luật kết hợp cơ sở

23

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