Khai phá tập mục thường xuyên lợi ích cao trong cơ sở dữ liệu

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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

VÀ TRUYỀN THÔNG

NGUYỄN AN KHÁNH

KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN

LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2012

THÁI NGUYÊN - 2012

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

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

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

VÀ TRUYỀN THÔNG

NGUYỄN AN KHÁNH

KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN

LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: GS. TS: Vũ Đức Thi

THÁI NGUYÊN - 2012

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

Lời đầu tiên cho tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc đến

GS. TS Vũ Đức Thi – Viện Công nghệ Thông tin, Viện Khoa học và Công

nghệ Việt Nam, ngƣời thầy đáng kính đã chỉ bảo và hƣớng dẫn tận tình cho tôi

trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này

Tôi xin chân thành cảm ơn sự dậy bảo, giúp đỡ, tạo điều kiện và khuyến

khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo Viện Công

nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam

Xin chân thành cảm ơn Ban Giám hiệu và thầy cô giáo Trƣờng Đại học

Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, nơi tôi học tập và

làm việc, xin đƣợc gửi lời cảm ơn chân thành và sâu sắc nhất đến các thầy cô.

Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, bạn bè và đồng nghiệp –

những ngƣời luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến

khích tôi trong cuộc sống và trong công việc.

Tôi xin chân thành cảm ơn!

Thái Nguyên, ngày 20 tháng 6 năm 2012

Tác giả

Nguyễn An Khá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

LỜI CAM ĐOAN

Tôi xin cam đoan Luận văn “ Khai phá tập mục thƣờng xuyên lợi ích cao

trong cơ sở dữ liệu “ đƣợc thực hiện theo đúng mục tiêu đề ra dƣới sự hƣớng dẫn

của GS. TS Vũ Đức Thi. Trong toàn bộ luận văn, những điều đƣợc trình bày là của

cá nhân hoặc là đƣợc tổng họp từ nhiều nguồn tài liệu. Tất cả các loại tài liệu đều có

xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp.

Thái Nguyên, ngày 20 tháng 6 năm 2012

Tác giả

Nguyễn An Khá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

DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT

Trong luận văn này, dùng thống nhất các ký hiệu và chữ viết tắt sau:

Các ký hiệu:

I = {i1,i2,…,in}: Tập n mục dữ liệu.

DB = {T1,T2,…,Tm}: Cơ sở dữ liệu có m giao tác.

db: cơ sở dữ liệu giao tác con của DB, db  DB.

ip: Mục dữ liệu thứ p.

Tq: Giao tác thứ q.

n: Số mục dữ liệu một cơ sở dữ liệu giao tác.

m: Số giao tác một cơ sở dữ liệu giao tác.

A, B, C,…: Tên các mục dữ liệu trong cơ sở dữ liệu giao tác ví dụ.

X, Y,…: Tập con của tập mục dữ liệu I, X, Y  I.

X = ABC thay cho X={A,B,C} trong các cơ sở dữ liệu giao tác ví dụ.

Nếu X  Y thì X gọi là tập con của tập Y, Y gọi là tập cha của tập X.

minsup: Ngƣỡng độ hỗ trợ tối thiểu.

minShare: Ngƣỡng cổ phần tối thiểu.

minutil: Giá trị lợi ích tối thiểu.

X: Số phần tử của tập hợp X.

Viết tắt:

CSDL: Cơ sở dữ liệu.

CNTT: Công nghệ Thông tin.

CNTT và TT: Công nghệ Thông tin và Truyền thông.

DL: Dữ liệ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

MỤC LỤC

MỞ ĐẦU.....................................................................................................................7

Chƣơng 1 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG..........9

1.1MỞ ĐẦU ...........................................................................................................9

1.2CÁC KHÁI NIỆM CƠ BẢN...........................................................................10

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

1.2.2 Tập mục thƣờng xuyên và luật kết hợp.......................................... 13

1.2.3 Bài toán khai phá luật kết hợp........................................................ 14

1.3 KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN.................................................15

1.3.1 Các cách tiếp cận khai phá tập mục thƣờng xuyên....................... 15

1.3.2 Thuật toán Apriori......................................................................... 16

1.3.3 Thuật toán FP-growth ................................................................... 21

1.4 MỞ RỘNG BÀI TOÁN KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN..........27

1.5 KẾT LUẬN CHƢƠNG 1 ...............................................................................28

Chƣơng 2 KHAI PHÁ TẬP MỤC LỢI ÍCH CAO......................................................30

2.1. GIỚI THIỆU..................................................................................................30

2.2 BÀI TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO......................................32

2.3 THUẬT TOÁN COUI-Mine1 ........................................................................35

2.3.1 Xây dựng cây TWUI-tree............................................................... 37

2.3.2 Khai phá cây TWUI-tree................................................................ 42

2.3.3 Đánh giá thuật toán COUI-Mine1.................................................. 51

2.3.3.1: Bƣớc xây dựng cây TWUI-tree: ............................................ 51

2.3.3.2: Bƣớc khai phá cây TWU-tree................................................ 52

2.3.4 Nhận xét thuật toán COUI-Mine1.................................................. 54

2.3.5 Khai phá tƣơng tác với cây TWUI-tree ......................................... 55

2.4 THUẬT TOÁN COUI-Mine2 ........................................................................57

2.4.1 Xây dựng cây UP-tree.................................................................... 57

2.4.2 Khai phá cây UP-tree ..................................................................... 59

2.4.3 Ví dụ áp dụng minh họa................................................................. 61

2.4.3.1 Xây dựng cây UP-tree............................................................. 62

2.4.3.2 Khai phá cây UP-tree .............................................................. 64

2.4.4 Nhận xét thuật toán COUI-Mine2.................................................. 68

2.5 THUẬT TOÁN COUI-Mine3 ........................................................................70

2.5.1 Cơ sở của thuật toán....................................................................... 70

2.5.2 Xây dựng và khai phá mảng giao tác............................................. 71

2.5.2.1 Xây dựng mảng giao tác ......................................................... 71

2.5.2.2 Khai phá mảng giao tác :......................................................... 75

2.5.3 Nhận xét thuật toán COUI-Mine3.................................................. 78

2.6 KẾT LUẬN CHƢƠNG 2 ...............................................................................80

Chƣơng 3 THỰC NGHIỆM THUẬT TOÁN KHAI PHÁ TẬP MỤC LỢI ÍCH CAO ..81

PHẦN KẾT LUẬN .....................................................................................................85

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

7

MỞ ĐẦU

Ngày nay, cùng với sự phát triển không ngừng của ngành công nghệ thông tin

và truyền thông vào nhiều lĩnh vực đời sống văn hóa xã hội, quản lý kinh tế, khoa

học kỹ thuật, … đã tạo ra nhiều cơ sở dữ liệu khổng lồ. Để khai thác hiệu quả nguồn

thông tin dữ liệu lớn, hỗ chợ tiến trình ra quyết định, bên cạnh các phƣơng pháp

khai thác thông tin truyền thống một khuynh hƣớng kỹ thuật mới ra đời đó là Kỹ

thuật Khai phá dữ liệu và khám phá tri thức (KDD – Knownledge Discovery and

DataMining) là một lĩnh vực quan trọng của nghành Công nghệ thông tin. Đây là

lĩnh vực đã thu hút đƣợc đông đảo các nhà khoa học trên thế giới và trong nƣớc

tham gia nghiên cứu. Khai phá tập mục thƣờng xuyên là bài toán có vai trò quan

trọng trong nhiều nhiệm vụ khai phá dữ liệu.

Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong thực

tế bên cạnh đó còn có những hạn chế, không đáp ứng đƣợc nhu cầu của ngƣời sử

dụng.

Để đáp ứng yêu cầu thực tiễn, một số hƣớng mở rộng của bài toán đã đƣợc

quan tâm nghiên cứu, theo hƣớng này, từ các bài toán khai phá tập mục thƣờng

xuyên ban đầu các nhà nghiên cứu đã đề xuất các mô hình mở rộng, một trong số đó

có mô hình Khai phá tập mục lợi ích cao, đánh giá lợi ích mà tập mục dữ liệu mang

lại trong cơ sở dữ liệu.

Khai phá tập mục lợi ích cao là thực sự là một lĩnh vực đang thu hút nhiều nhà

nghiên cứu tham gia.

Trong luận văn này, tôi trình bày ba thuật toán khai phá tập mục lợi ích cao

dựa trên cấu trúc cây đơn giản và cách khai phá không đệ quy (Thuật toán COUI￾Mine1, COUI-Mine2, COUI-Mine 3). Các thuật toán đề xuất sử dụng cấu trúc cây

FP-tree đƣợc Han, Wang và Yin giới thiệu năm 2000 trong cách khai phá cây FP￾tree không đệ quy bởi cấu trúc cây COFI-tree do Mohammad El-Hajj và Osmar R.

Zaiane đề xuất năm 2003. Hai thuật toán đầu sử dụng cấu trúc cây FP-tree để xây

dựng cây chứa thông tin của các giao tác, sau đó khai phá cây này để tìm ra các tậ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

8

mục lợi ích cao. Thuật toán thứ 3 chuyển đổi dữ liệu thành mạng ma trận để lƣu ở

bộ nhớ ngoài, sau khi đã chuyển đổi sang dạng biểu diễn mới, có thể khai phá các

ngƣỡng lợi ích khác nhau. Thuật toán thứ ba này có thể khai phá đƣợc các tập dữ

liệu lớn vì hầu nhƣ toàn bộ dữ liệu đặt tại bộ nhớ ngoài, chỉ đƣa vào bộ nhớ trong

một phần nhỏ dữ liệu để khai phá. Ba thuật toán đề xuất thực hiện khai phá hiệu quả

vì các lí do: 1) Số lần duyệt cơ sở dữ liệu ít, 2) Không sinh ra khối lƣợng khổng lồ

các tập ứng viên, giảm chi phí thanh toán và 3) sử dụng tiết kiệm bộ nhớ.

Với thời gian và kiến thức còn hạn chế, luận văn này không tránh khỏi

những thiếu sót, rất mong đƣợc sự quan tâm định hƣớng của thầy cô giáo sự góp ý

của các bạn đồng nghiệp để báo cáo hoàn thiện hơn.

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