ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

------------------------------

NGUYỄN DUY HÀM

PHÁT TRIỂN MỘT SỐ THUẬT TOÁN HIỆU QUẢ

KHAI THÁC TẬP MỤC TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG

CÓ SỰ PHÂN CẤP CÁC MỤC

LUẬN ÁN TIẾN SĨ TOÁN HỌC

Hà Nội - 2016

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

------------------------------

NGUYỄN DUY HÀM

PHÁT TRIỂN MỘT SỐ THUẬT TOÁN HIỆU QUẢ

KHAI THÁC TẬP MỤC TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG

CÓ SỰ PHÂN CẤP CÁC MỤC

Chuyên ngành: CƠ SỞ TOÁN CHO TIN HỌC Mã số: 62460110

LUẬN ÁN TIẾN SĨ TOÁN HỌC

NGƢỜI HƢỚNG DẪN KHOA HỌC:

1. TS. NGUYỄN THỊ HỒNG MINH

2. PGS.TS. VÕ ĐÌNH BẢY

XÁC NHẬN NCS ĐÃ CHỈNH SỬA THEO QUYẾT NGHỊ CỦA HỘI ĐỒNG ĐÁNH GIÁ LUẬN ÁN

Ngƣời hƣớng dẫn khoa học

TS. Nguyễn Thị Hồng Minh

Chủ tịch hội đồng đánh giá Luận án Tiến sĩ PGS.TS. Huỳnh Quyết Thắng

Hà Nội - 2016

LỜI CAM ĐOAN

Tôi xin cam đoan luận án này là công trình nghiên cứu do tác giả thực

hiện dƣới sự hƣớng dẫn của tập thể cán bộ hƣớng dẫn. Luận án có sử dụng

thông tin trích dẫn từ nhiều nguồn tham khảo khác nhau, các thông tin trích

dẫn đều đƣợc ghi rõ nguồn gốc. Các số liệu thực nghiệm, kết quả nghiên cứu

trình bày trong luận án là hoàn toàn trung thực, chƣa đƣợc công bố bởi tác giả

nào hay trong bất kì công trình nào khác.

Tác giả

i

Nguyễn Duy Hàm

Luận án Tiến sĩ này đƣợc thực hiện tại trƣờng Đại học Khoa học và Tự nhiên -

Đại học Quốc gia Hà Nội với sự hƣớng dẫn khoa học của TS. Nguyễn Thị Hồng

Minh, PGS.TS.Võ Đình Bảy và TS. Lê Quang Minh. Nghiên cứu sinh xin bày tỏ

lòng biết ơn sâu sắc tới thầy giáo, cô giáo hƣớng dẫn đã định hƣớng khoa học, tận

tâm giúp đỡ và chỉ bảo tỉ mỉ trong suốt quá trình nghiên cứu mới có thể hoàn thiện

bản luận án này. Nghiên cứu sinh luôn ghi nhớ công lao dạy dỗ, dìu dắt vào con

đƣờng khoa học của cố PGS.TS. Hoàng Chí Thành - ngƣời đã hƣớng dẫn Nghiên

cứu sinh ở giai đoạn đầu làm nghiên cứu khoa học. Nghiên cứu sinh xin chân thành

cảm ơn các nhà khoa học, tác giả các công trình nghiên cứu đã đƣợc trích dẫn trong

luận án vì đây là nguồn tài liệu quý báu để Nghiên cứu sinh phát triển và hoàn thiện

các công bố của mình.

Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu, lãnh đạo Khoa Toán -

Cơ - Tin học, các thầy cô, giảng viên Bộ môn Tin học - Trƣờng Đại học Khoa học Tự

nhiên - Đại học Quốc gia Hà Nội đã tạo những điều kiện thuận lợi nhất để Nghiên

cứu sinh hoàn thành chƣơng trình học tập và thực hiện hoàn tất luận án của mình.

Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu Trƣờng Đại học An

ninh nhân dân, tập thể giáo viên Bộ môn Toán - Tin học Trƣờng Đại học An ninh

nhân dân nơi Nghiên cứu sinh công tác và các bạn bè thân thiết đã luôn tạo điều

kiện, động viên, khuyến khích và hỗ trợ tối đa để Nghiên cứu sinh hoàn thành bản

luận án này.

Cuối cùng, con xin cảm ơn Bố Mẹ, đặc biệt là Mẹ - ngƣời đã luôn hy sinh tất

cả vì sự nghiệp học tập của các con, rất tiếc mẹ đã không đợi đƣợc đến ngày con

hoàn thành luận án. Xin cảm ơn gia đình, chị gái và các em đã luôn đồng hành,

động viên, chia sẻ giúp duy trì nhiệt huyết và nghị lực để đi đến hoàn thành bản

luận án này./

TP. Hồ Chí Minh, tháng năm 2016

ii

LỜI CẢM ƠN

MỤC LỤC

LỜI CAM ĐOAN ........................................................................................................... I LỜI CẢM ƠN ............................................................................................................... II MỤC LỤC .................................................................................................................... III DANH MỤC BẢNG ......................................................................................................V

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .................................................................. VII

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

MỞ ĐẦU ........................................................................................................................ 1 CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC ...................................... 7

1.1. Bài toán khai thác tập mục .................................................................................. 7 1.1.1. Một số khái niệm cơ bản ................................................................................. 8 1.1.2. Bài toán khai thác FI ...................................................................................... 15

1.2. Các phƣơng pháp khai thác FI ......................................................................... 15 1.2.1. Phƣơng pháp khai thác FI trên CSDL ngang ................................................ 15

1.2.2. Phƣơng pháp khai thác FI trên CSDL dọc dựa trên IT-tree .......................... 18

1.3. Một số phƣơng pháp khai thác FWI và FWUI trên CSDL số lƣợng ............ 21 1.3.1. Giới thiệu ....................................................................................................... 21

1.3.2. Khai thác FWI ............................................................................................... 21

1.3.3. Khai thác FWUI ............................................................................................. 24 1.3.4. Khai thác TRFIk ............................................................................................. 26 1.4. Khai thác FI trên CSDL có sự phân cấp các mục ........................................... 28 1.5. Tiếp cận bit-vector trong khai thác FI ............................................................. 31

1.6. Kết luận chƣơng ................................................................................................. 32

CHƢƠNG 2. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU

SỐ LƢỢNG ................................................................................................................. 35

2.1. Thuật toán khai thác tập FWI .......................................................................... 36 2.1.1. Giới thiệu ....................................................................................................... 36 2.1.2. Thuật toán tính giao của hai IWS .................................................................. 40

2.1.3. Thuật toán khai thác FWI .............................................................................. 42 2.1.4. Kết quả thực nghiệm ...................................................................................... 48

2.2. Thuật toán khai thác FWUI .............................................................................. 54 2.2.1. Cấu trúc Multi bit segment ............................................................................ 54 2.2.2. Thuật toán xác định giao MBiS ..................................................................... 55 2.2.3. Thuật toán khai thác FWUI dựa trên MBiS-tree ........................................... 56 2.2.4. Kết quả thực nghiệm ...................................................................................... 59

iii

2.3. Thuật toán khai thác TRFWUIk ....................................................................... 63 2.3.1. Một số khái niệm ........................................................................................... 63 2.3.2. Cấu trúc DTab ............................................................................................... 64

2.3.3. Cấu trúc TR-tree ............................................................................................ 65 2.3.4. Thuật toán khai thác TRFWUIk sử dụng cấu trúc dữ liệu DTab ................... 65 2.3.5. Thuật toán khai thác nhanh TRFWUIk dựa trên cấu trúc DHeap.................. 68 2.3.6. Kết quả thực nghiệm ...................................................................................... 70

2.4. Kết luận chƣơng ................................................................................................. 73

CHƢƠNG 3. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU

SỐ LƢỢNG CÓ SỰ PHÂN CẤP CÁC MỤC .......................................................... 75

3.1. Giới thiệu bài toán .............................................................................................. 76 3.2. Thuật toán khai thác FWUI trên HQDB ......................................................... 79 3.2.1. Thuật toán xác định weight cho các mục cha ................................................ 79

3.2.2. Thuật toán thêm mục cha vào CSDL ............................................................ 80

3.2.3. Thuật toán khai thác FWUI ........................................................................... 81

3.3. Một số cải tiến nâng cao hiệu quả khai thác FWUI trên HQDB ................... 84 3.3.1. Cấu trúc EDBV .............................................................................................. 84

3.3.2. Tính tidset nút cha từ tidset nút con .............................................................. 89

3.3.3. Kiểm tra mối quan hệ cha con đối với các mục trong tập mục ..................... 91

3.3.4. Thuật toán khai thác nhanh FWUI trên HQDB ............................................. 92

3.4. Kết quả thực nghiệm .......................................................................................... 93 3.4.1. CSDL thực nghiệm ........................................................................................ 93

3.4.2. Kết quả thực nghiệm ...................................................................................... 94

3.5. Kết luận chƣơng ............................................................................................... 100

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................................... 101 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN

ĐẾN LUẬN ÁN ......................................................................................................... 103

iv

DANH MỤC BẢNG

Bảng 1.1. Các giao dịch của nhị phân DB ............................................................. 8

Bảng 1.2. Các giao dịch của CSDL nhị phân có sự phân cấp mục DB.......... 9

Bảng 1.3.

ID của các mục của DB ....................................................................... 10

Bảng 1.4. Các giao dịch của DB bằng ID ............................................................ 10

Bảng 1.5. Giao dịch của CSDL số lƣợng BD .................................................. 12

Bảng 1.6.

Trọng số các mục của DB ................................................................... 12

Bảng 1.7. Các giao dịch của CSDL trọng số DB ................................................ 13

Bảng 1.8.

Trọng số của các mục của DB ............................................................. 13

Bảng 1.9. CSDL DB ............................................................................................ 15

Bảng 1.10. DB theo chiều dọc ............................................................................... 19

Bảng 1.11. Giá trị tw của CSDL DB trong ví dụ 1.4 ............................................. 23

Bảng 1.12.

twu các giao dịch của DB trong ví dụ 1.4 ........................................... 25

Bảng 1.13. DB trong Ví dụ 1.2 sau khi thêm mục cha .......................................... 30

Bảng 2.1. Bit-vector ............................................................................................ 36

Bảng 2.2. DBV của bit-vector trong ví dụ 2.1 .................................................... 36

Bảng 2.3.

IWS từ bit-vector trong ví dụ 2.1 ........................................................ 37

Bảng 2.4. Chỉ số các bit 1 của IWS(X) ................................................................ 39

Bảng 2.5. Mảng MAP .......................................................................................... 42

Bảng 2.6.

IWS của các mục ................................................................................ 46

Bảng 2.7. Mô tả CSDL thực nghiệm ................................................................... 49

Bảng 2.8. Bit-vector với 96 phần tử .................................................................... 54

Bảng 2.9. MBiS từ bit-vector ở Bảng 2.8 ............................................................ 55

Bảng 2.10. Bảng TRFWUIk ................................................................................... 64

Bảng 3.1. Giao dịch của HD ................................................................................ 76

Bảng 3.2.

Trọng số .............................................................................................. 76

Bảng 3.3.

Tên mặt hàng của các mục ................................................................. 77

v

Bảng 3.4. Giao dịch của HD ................................................................................ 82

Bảng 3.5.

Trọng số .............................................................................................. 82

Bảng 3.6.

twu của các giao dịch .......................................................................... 83

Bảng 3.7.

Tập 1-itemset phổ biến ........................................................................ 83

Bảng 3.8. Mảng MAP với 65.535 phần tử .......................................................... 86

Bảng 3.9.

Biểu diễn số nguyên K dƣới dạng bốn đoạn, mỗi đoạn là một word .... 86

Bảng 3.10. Mô tả CSDL ........................................................................................ 93

Bảng 3.11. Các mức trên cây phân cấp ................................................................. 93

Bảng 3.12. So sánh bộ nhớ và số lƣợng các mục ................................................. 94

Bảng 3.13. Thực nghiệm trên CSDL SALE-FACT-SYNC .................................. 95

Bảng 3.14. So sánh thời gian chạy trên CSDL SALE-FACT-1997 ...................... 99

vi

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1.1. Cây phân cấp Tr .................................................................................. 10

Hình 1.2. Cây phân cấp Tr biểu diễn theo ID ..................................................... 11

Hình 1.3.

Thuật toán Apriori trong khai thác tập mục phổ biến ......................... 16

Hình 1.4.

Thuật toán FP-Growth dựa trên cấu trúc FP-tree ................................ 17

Hình 1.5.

Thuật toán Eclat dựa trên cấu trúc IT-tree .......................................... 19

Hình 1.6. Cây IT tree với minsup = 0,5 của CSDL DB ...................................... 20

Hình 2.1.

Thuật toán xác định giao hai IWS ....................................................... 41

Hình 2.2.

Thuật toán tính ws của tập mục X ....................................................... 43

Hình 2.3.

Thuật toán xây dựng cây IWS-tree ..................................................... 45

Hình 2.4.

Thuật toán khai thác FWI dựa trên IWS-tree ...................................... 45

Hình 2.5.

IWS-tree với nút A(minws = 0,4) ........................................................ 46

Hình 2.6.

IWS-tree với nútA vàB(minws = 0,4) .................................................. 47

Hình 2.7.

IWS-tree với minws = 0,4 ................................................................... 48

Hình 2.8.

So sánh thời gian chạy với CSDL RETAIL........................................ 49

Hình 2.9.

So sánh thời gian chạy với CSDL BMS-POS. .................................... 49

Hình 2.10. So sánh thời gian chạy với CSDL SALE-FACT-1997. ...................... 50

Hình 2.11. So sánh thời gian chạy với CSDL SALE-FACT-1997+1998............. 50

Hình 2.12. So sánh thời gian chạy với CSDL SALE-FACT-SYNC. ................... 50

Hình 2.13. So sánh thời gian chạy với CSDL CONNECT. .................................. 50

Hình 2.14. So sánh thời gian chạy với CSDL ACCIDENTS. .............................. 51

Hình 2.15. So sánh bộ nhớ sử dụng với CSDL RETAIL. .................................... 51

Hình 2.16. So sánh bộ nhớ sử dụng với CSDL BMS-POS................................... 51

Hình 2.17. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997. .................... 51

Hình 2.18. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997+1998. ......... 52

vii

Hình 2.19. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-SYNC. ................. 52

Hình 2.20. So sánh bộ nhớ sử dụng với CSDL CONNECT. ................................ 52

Hình 2.21. So sánh bộ nhớ sử dụng với CSDL ACCIDENT. .............................. 52

Hình 2.22. Thuật toán xác định giao hai MBiS .................................................... 56

Hình 2.23. Thuật toán tính wus dựa trên MBiS .................................................... 57

Hình 2.24. Thuật toán khai thác FWUI dựa trên MBiS-tree ................................ 58

Hình 2.25. So sánh thời gian chạy trên CSDL RETAIL....................................... 59

Hình 2.26. So sánh thời gian chạy trên CSDL BMS-POS. ................................... 59

Hình 2.27. So sánh thời gian chạy trên CSDL SALE-FACT-1997. ..................... 60

Hình 2.28. So sánh thời gian chạy trên CSDL SALE-FACT-1997+1998............ 60

Hình 2.29. So sánh thời gian chạy trên CSDL SALE-FACT-SYNC. .................. 60

Hình 2.30. So sánh thời gian chạy trên CSDL CONNECT. ................................. 60

Hình 2.31. So sánh thời gian chạy trên CSDL ACCIDENTS. ............................. 61

Hình 2.32. So sánh bộ nhớ sử dụng trên CSDL RETAIL. ................................... 61

Hình 2.33. So sánh bộ nhớ sử dụng trên CSDL BMS-POS. ................................. 61

Hình 2.34. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997. ................... 61

Hình 2.35. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997+1998. ........ 62

Hình 2.36. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-SYNC. ................ 62

Hình 2.37. So sánh bộ nhớ sử dụng trên CSDL CONNECT. ............................... 62

Hình 2.38. So sánh bộ nhớ sử dụng trên CSDL ACCIDENT. ............................. 62

Hình 2.39. DTab với k = 5 .................................................................................... 65

Hình 2.40. Thuật toán tạo TR-tree sử dụng DTab ................................................ 67

Hình 2.41. Thuật toán lọc ra TRFWUIk ................................................................ 68

Hình 2.42. DHeap với k = 5 với CSDL trong ví dụ 1.4 ........................................ 69

Hình 2.43. Thuật toán tạo TR-tree sử dụng DHeap .............................................. 70

viii

Hình 2.44. Thuật toán lọc ra TRFWUIk ................................................................ 70

Hình 2.45. So sánh thời gian chạy trên CSDL MBS-POS .................................... 71

Hình 2.46. So sánh thời gian chạy trên CSDL RETAIL....................................... 71

Hình 2.47. So sánh thời gian chạy trên CSDL CONNECT .................................. 72

Hình 2.48. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 72

Hình 2.49. So sánh thời gian trên CSDL SALE-FACT-1997+1998 .................... 72

Hình 2.50. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 72

Hình 3.1.

Tập các cây phân cấp Tr ..................................................................... 77

Hình 3.2.

Thuật toán tính weight cho các mục cha ............................................. 80

Hình 3.3.

Thuật toán thêm mục cha vào CSDL .................................................. 80

Hình 3.4.

Thuật toán khai thác FWUI từ HQDB ................................................ 82

Hình 3.5. Cây HIT-tree với CSDL HD và minwus = 0,6 .................................... 84

Hình 3.6.

Sử dụng các phép AND và dịch bit để tách các đoạn hai byte ........... 87

Hình 3.7.

Thuật toán tính nhanh wus của các tập mục ...................................... 89

Hình 3.8.

Thuật toán xác định tidset các mục và tính twu của các giao dịch ..... 90

Hình 3.9.

Thuật toán khai thác nhanh FWUI trên HQDB .................................. 92

Hình 3.10. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 96

Hình 3.11. So sánh thời gian trên CSDLSALE-FACT-1997+1998 ..................... 96

Hình 3.12. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 97

Hình 3.13. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 98

Hình 3.14. So sánh thời gian trên CSDL SALE-FACT-1997+1998 .................... 98

Hình 3.15. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 98

ix

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

Stt Từ viết tắt

Thuật ngữ tiếng Anh

Thuật ngữ tiếng Việt

1. CSDL

Database

Cơ sở dữ liệu

2. DBV

Dynamic bit-vector

Bit động

3. EDBV

Extended dynamic bit-vector

Bit động mở rộng

4. EIWS

Extended interval word segment Các đoạn word mở rộng

5. FI

Frequent itemset

Tập mục phổ biến

6. FP-tree

Frequent Pattern-Tree

Cây FP

Tập mục phổ biến có

7. FWI

Frequent weighted itemset

trọng số

Tập mục phổ biến trọng

8. FWUI

Frequent weighted utility itemset

số hữu ích

Hierarchical quantitative

Cơ sở dữ liệu số lƣợng

9. HQDB

database

có sự phân cấp các mục

10.

IT-tree

Itemset tidset-tree

Cây IT-tree

11.

IWS

Interval words segment

Các đoạn word

12. MBiS

Multi bits segment

Các đoạn bit 1 liên tiếp

13. MByS

Multi bytes segment

Các đoạn byte

14. DTab

Dynamic table

Bảng động

K nhóm tập mục phổ biến

Top-rank-k frequent itemsets

15. TRFIk

có thứ hạng cao nhất

K nhóm tập mục phổ biến

Top-rank-k frequent weight

trọng số hữu ích có

16. TRFWUIk

utility itemsets

thứ hạng k cao nhất

17. DHeap

Dynamic heap

Heap động

18.

Item

Item

Mục

19.

Itemset

Set of items

Tập mục

20. LI

Large integer

Số nguyên lớn (tám byte)

x

MỞ ĐẦU

Sự phát triển mạnh mẽ của Công nghệ thông tin trong những năm gần

đây đã thúc đẩy sự phát triển chung của toàn xã hội. Với các ứng dụng của

Công nghệ thông tin, con ngƣời đã có những “trợ thủ” đắc lực hỗ trợ mình

trong cuộc sống cũng nhƣ trong công việc. Công nghệ thông tin ứng dụng

trong rất nhiều lĩnh vực đƣa đến sự tiện lợi và kết nối mọi ngƣời trên khắp

thế giới lại với nhau. Các ứng dụng nhƣ ngân hàng điện tử, thƣơng mại điện

tử, v.v… đã giúp cho con ngƣời tiết kiệm rất nhiều thời gian và công sức so

với thao tác thủ công trƣớc đây. Trong những ứng dụng đó, thông tin, dữ

liệu thƣờng xuyên đƣợc đƣa vào để các hệ thống thông tin lƣu trữ và xử lý.

Bên cạnh đó, một số lƣợng lớn các dữ liệu đƣợc cập nhật hàng ngày và tự

động lƣu trữ thông qua các hoạt động của con ngƣời khi tƣơng tác với các hệ

thống thông tin, mạng xã hội, v.v… làm cho dữ liệu càng ngày càng lớn và

phức tạp.

Ngoài việc phục vụ cho các hệ thống thông tin hoạt động theo chức năng

sẵn có thì một vấn đề đặt ra là làm sao có thể khai thác hiệu quả các loại dữ

liệu lƣu trữ trong hệ thống, tìm ra các tri thức quan trọng, các quy luật của dữ

liệu phục vụ cho việc đƣa ra các dự đoán, dự báo nhằm hỗ trợ ra quyết định

và các nhu cầu liên quan khác. Ví dụ nhƣ từ cơ sở dữ liệu (CSDL) của hệ

thống bán hàng trong siêu thị có thể tìm ra đƣợc quy luật (thói quen) mua

hàng của các khách hàng. Khách hàng thƣờng mua các mặt hàng nào cùng với

nhau? hay độ tuổi từ “A” đến “B” thƣờng ƣa thích mặt hàng nào?, v.v... Từ đó

để giúp cho việc triển khai các kế hoạch phát triển sản phẩm hiệu quả hơn của

các hệ thống bán hàng nhƣ trung tâm thƣơng mại, siêu thị, v.v…

Khai thác tập mục phổ biến trên CSDL nhị phân

Từ những yêu cầu thiết thực đó, lĩnh vực khai thác dữ liệu đã và đang

đƣợc phát triển mạnh trong thời gian gần đây. Một trong những bài toán quan

trọng trong khai thác dữ liệu đƣợc quan tâm nghiên cứu là khai thác tập mục

1

phổ biến (frequent itemsets - FI), từ FI có thể khai thác luật kết hợp, đƣa ra

những dự báo, dự đoán và tìm ra quy luật của dữ liệu nhằm phục vụ cho các

nhu cầu khác nhau của con ngƣời.

Thuật toán đầu tiên đƣợc biết tới trong khai thác FI là đƣợc đề xuất bởi

Agrawal và các đồng sự [2] năm 1993, sau đó chính Agrawal đề xuất thuật

toán Apriori [1] năm 1994. Tuy nhiên thuật toán này sớm bộc lộ hạn chế về

thời gian xử lý do đọc CSDL nhiều lần. Tiếp theo Han và các đồng sự đề xuất

thuật toán FP-Growth [19] và Grahne cùng các đồng sự đề xuất FP-Growth*

[18] dựa trên việc nén dữ liệu lên cây FP-tree (frequent pattern-tree) với chỉ hai

lần đọc CSDL, đây là thuật toán hiệu quả về bộ nhớ sử dụng, song lại tốn thời

gian cho duyệt cây FP-tree để khai thác các FI. Tiếp đến Zaki và các đồng sự

đề xuất thuật toán Eclat [49] dựa trên cấu trúc IT-tree (Itemset Tidset-tree) với

chỉ một lần đọc dữ liệu để chuyển CSDL ngang thành CSDL dọc với các mục

và tidset (set of transaction identifiers - tập các giao dịch) của chúng. Tuy

nhiên, Eclat có hạn chế là cần nhiều bộ nhớ để lƣu trữ tidset, do đó gián tiếp

ảnh hƣởng đến hiệu quả về mặt thời gian của thuật toán này. Tiếp theo Zaki và

các đồng sự [50] đề xuất cấu trúc diffset, với tƣ tƣởng sử dụng phần bù của

tidset, nhƣng cách làm này chỉ thực sự có hiệu quả trên CSDL dày. Tuy nhiên,

trong khi thực tế CSDL thƣa mới là loại CSDL phổ biến.

Một số phát triển gần đây với cấu trúc N-list [8, 9,10,11,12, 17, 26, 40]

là các nghiên cứu dựa trên tiếp cận lai ghép giữa FP-tree và định dạng dữ liệu

dọc nhằm giảm bộ nhớ giúp cải tiến thời gian khai thác và bộ nhớ sử dụng.

Tuy nhiên, các nghiên cứu này mới đề cập trên CSDL nhị phân, chƣa đƣợc

nghiên cứu áp dụng trên CSDL số lƣợng, do đặc thù của CSDL số lƣợng cần

tính trọng số các giao dịch của các tập mục để xác định độ hỗ trợ của các tập

mục, mà đây là một khó khăn của tiếp cận dựa trên FP-tree.

Khai thác tập mục phổ biến trên CSDL số lượng

Các chủ đề nghiên cứu trên CSDL số lƣợng nhƣ khai thác tập mục phổ

biến có trọng số (frequent weighted itemsets - FWI) [7, 22, 23, 32, 34, 37, 41,

2

42, 43, 44, 45, 46, 47, 48] hay khai thác tập mục phổ biến trọng số hữu ích

(frequent weighted utility itemsets - FWUI) [21, 39], hay tập mục hữu ích cao

- (hight utility itemsets - HUIs) [14, 24, 25, 29] đã đƣợc quan tâm nghiên cứu.

Rakumar và đồng sự [32] đề xuất bài toán khai thác luật kết hợp trọng số

và một framework để khai thác FWI. Sau đó Tao và đồng sự [34] đề xuất

thuật toán khai thác FWI dựa trên tiếp cận Apriori với hai độ đo trọng số giao

dịch (transaction weight - tw) và độ hỗ trợ trọng số (weight support - ws), tuy

nhiên nhƣ đã trình bày ở trên cách tiếp cận này rất tốn thời gian do quét

CSDL nhiều lần. Tiếp đến, Vo và các đồng sự [37] đề xuất cấu trúc WIT-tree

trong khai thác FWI và cấu trúc MWIT-tree [39] trong khai thác FWUI theo

tiếp cận Eclat [49] với chỉ một lần quét CSDL. Hạn chế của các phƣơng pháp

này là cần nhiều bộ nhớ lƣu trữ tidset của các tập mục bằng các danh sách,

làm tốn thời gian xác định giao tidset của các tập mục.

Một bài toán mới đƣợc đặt ra và phát triển gần đây trong khai thác FI là

khai thác k nhóm tập mục phổ biến có thứ hạng cao nhất (Top-rank-k frequent

itemset-TRFIk) [8, 11, 15, 26] Khai thác FI thông thƣờng không kiểm soát

đƣợc số lƣợng các tập mục phổ biến tìm thấy. Trong nhiều trƣờng hợp chỉ cần

quan tâm đến một số lƣợng nhất định các FI, hay số lƣợng các nhóm FI có độ

hỗ trợ lớn nhất. Khai thác TRFIk giải quyết đƣợc đòi hỏi này. Bài toán khai

thác TRFIk đã đƣợc Deng giới thiệu vào năm 2007 [8] với thuật toán FAE,

sau đó đƣợc Fang đề xuất thuật toán VTK [17] để giải quyết. Tiếp theo, Deng

[11] đề xuất thuật toán NTK dựa trên cây PPC-tree (Pre-order Post-order

Code tree) và cấu trúc N-list. Gần đây, Le và các đồng sự [26] đề xuất thuật

toán iNTK là một cải tiến của NTK. iNTK sử dụng cấu trúc N-list với khái

niệm subsume đƣợc giới thiệu trong [40]. Đây đƣợc xem là thuật toán hiệu

quả nhất cho đến hiện nay, mặc dù iNTK tốn thời gian cho việc tạo cây PPC-

tree. Tuy nhiên, các nghiên cứu trên mới chỉ đề cập đến CSDL nhị phân, còn

trên CSDL số lƣợng bài toán khai thác Top-rank-k vẫn chƣa đƣợc quan tâm

3

nghiên cứu.

Khai thác tập mục phổ biến trên CSDL có sự phân cấp các mục

Bên cạnh CSDL nhị phân và CSDL số lƣợng thì CSDL có sự phân cấp

các mục là loại CSDL có nhiều trong ứng dụng thực tế. CSDL có sự phân

cấp các mục là CSDL có thể hiện mối quan hệ khách quan giữa các mục

dƣới dạng cây phân cấp, các mục có mặt trong CSDL là các mục ở nút lá

của cây phân cấp. Năm 1995, Han và các đồng sự [20] lần đầu tiên đề cập

tới bài toán khai thác FI trên CSDL có sự phân cấp các mục. Tiếp theo, Liu

và các đồng sự [31] đề xuất bài toán khai thác FI với nhiều ngƣỡng hỗ trợ

trên CSDL có sự phân cấp các mục, theo đó, mỗi mục có một ngƣỡng hỗ trợ

riêng biệt. Từ đó đến nay đã có nhiều nghiên cứu liên quan đến bài toán này

[4, 5, 6, 28, 30, 35, 36]. Tuy nhiên các tiếp cận hiện nay đối với khai thác

trên CSDL có sự phân cấp các mục còn có nhiều hạn chế, trong đó đặc biệt

là tốn thời gian và bộ nhớ để thêm các mục cha trên cây phân cấp vào

CSDL. Ngoài ra các nghiên cứu hiện tại chƣa đề cập trên CSDL số lƣợng có

sự phân cấp các mục.

Động lực nghiên cứu của luận án

Bài toán khai thác FI trên một số loại CSDL nhƣ đã phân tích ở trên

mặc dù đã đƣợc quan tâm nghiên cứu nhiều, nhƣng cho đến hiện nay các

phƣơng pháp khai thác FI trên các loại CSDL số lƣợng còn hạn chế là tốn

bộ nhớ và thời gian xử lý chƣa đƣợc tối ƣu. Mặt khác, khai thác FI trên

CSDL số lƣợng có sự phân cấp các mục hiện nay chƣa đƣợc quan tâm

nghiên cứu, mặc dù đây là loại CSDL có nhiều trong các ứng dụng thực tế.

Đồng thời, CSDL số lƣợng có sự phân cấp các mục là sự kết hợp giữa

CSDL số lƣợng và CSDL có sự phân cấp các mục. Do đó, đề xuất thuật

toán khai thác hiệu quả FI trên CSDL số lƣợng có sự phân cấp các mục có

thể áp dụng để khai thác hiệu quả FI trên các CSDL số lƣợng và CSDL có

sự phân cấp các mục, giúp cải thiện thời gian và bộ nhớ trong khai thác FI

4

trên các hệ thống thông minh.

Trên cơ sở đó, Nghiên cứu sinh chọn đề tài “Phát triển một số thuật

toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lƣợng có sự phân

cấp các mục” làm đề tài nghiên cứu cho luận án tiến sĩ của mình.

Đối tƣợng nghiên cứu là CSDL số lƣợng và CSDL số lƣợng có sự phân cấp mục.

Phạm vi nghiên cứu của luận án là phát triển các thuật toán khai thác tập mục

phổ biến ứng dụng trên CSDL số lƣợng và CSDL số lƣợng có sự phân cấp mục

Đối tượng và phạm vi nghiên cứu của luận án

Mục tiêu của luận án như sau:

i) Đối với các thuật toán hiện có trên CSDL số lƣợng, luận án nghiên

cứu cách thức khai thác hiệu quả hơn bằng cách cải tiến theo hƣớng

tiếp cận bit - vector.

ii) Phát triển khái niệm CSDL số lƣợng có sự phân cấp mục và đề xuất

phƣơng pháp khai thác mẫu trên CSDL số lƣợng có sự phân cấp mục.

Luận án đạt được một số kết quả như sau:

1. Đề xuất một số cấu trúc dữ liệu mới, thuật toán mới để nâng cao hiệu

quả khai thác FWI và FWUI trên CSDL số lượng. Từ đó áp dụng cho khai

thác tập mục phổ biến trên CSDL số lượng có sự phân cấp các mục.

2. Đề xuất thuật toán hiệu quả để khai thác k nhóm tập mục phổ biến trọng

số hữu ích có thứ hạng cao nhất trên CSDL số lượng.

3. Đề xuất cấu trúc dữ liệu, thuật toán hiệu quả để khai thác FWUI trên

CSDL số lượng có sự phân cấp các mục.

Cấu trúc luận án bao gồm năm phần, ngoài phần mở đầu và phần kết

luận, nội dung luận án đƣợc trình bày trong ba chƣơng:

Chương 1: “Tổng quan về khai thác tập mục” trình bày các khái niệm

về khai thác FI các phƣơng pháp khai thác FI, FWI, FWUI và TRFIk. Phân

tích ƣu điểm và hạn chế của các phƣơng pháp này đồng thời đề xuất hƣớng

5

nghiên cứu của luận án.

Chương 2: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng”

trình bày một số cấu trúc dữ liệu mới để biểu diễn tidset của các tập mục, trên

cơ sở đó đề xuất các phƣơng pháp hiệu quả để khai thác nhanh FWI, FWUI

trên CSDL số lƣợng. Đồng thời, trong chƣơng này cũng đề xuất bài toán khai

thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất

(TRFWUIk) trên CSDL số lƣợng và thuật toán hiệu quả để giải quyết bài toán

này với hai cấu trúc DTab và DHeap.

Chương 3: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng

có sự phân cấp các mục” đề xuất thuật toán khai thác FWUI trên CSDL số

lƣợng có sự phân cấp các mục. Chƣơng này trình bày một mở rộng của cấu

trúc dữ liệu trong chƣơng 2 và một số đề xuất nhằm cải tiến thuật toán khai

6

thác hiệu quả FWUI trên CSDL số lƣợng có sự phân cấp các mục.

CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC

Chƣơng này trình bày các nghiên cứu liên quan đến khai thác tập mục

phổ biến trên các loại CSDL nhƣ CSDL nhị phân, CSDL số lƣợng, CSDL có

sự phân cấp các mục và khai thác k nhóm tập phổ biến có thứ hạng cao nhất

(Top-rank-k) từ các nhóm nghiên cứu trong nƣớc và quốc tế. Phần này cũng

trình bày các phân tích về ƣu điểm và hạn chế của các phƣơng pháp khai thác

tập mục phổ biến hiện có. Từ cơ sở đó luận án đề ra các thuật toán mới dựa

trên các cấu trúc dữ liệu phù hợp hơn cho các bài toán này trong chƣơng 2 và

3 của luận án.

1.1. Bài toán khai thác tập mục

Mục đích của việc khai thác tập mục là để xác định nhóm các mục (item)

có tần suất xuất hiện thỏa mãn một ngƣỡng nào đó của ngƣời sử dụng đƣa

vào. Trong đó, bài toán khai thác tập mục phổ biến là một bài toán con của

bài toán khai thác tập mục với việc khai thác các tập mục có tần suất xuất

hiện nhiều trong CSDL. Tần suất xuất hiện này thỏa mãn ngƣỡng do ngƣời sử

dụng đƣa vào (đƣợc gọi là ngƣỡng phổ biến). Từ các FI khai thác đƣợc có thể

sinh ra tập luật kết hợp nhằm khám phá mối quan hệ tiềm ẩn, hữu ích giữa các

mục trong CSDL, phục vụ các yêu cầu xuất phát từ đòi hỏi của thực tế của

ngƣời sử dụng. Có thể nói, từ khi đƣợc giới thiệu đến nay, đã có khá nhiều

công trình nghiên cứu liên quan nhằm mục đích giải quyết tốt bài toán này.

Hiện nay, bài toán khai thác tập mục đang đƣợc tiếp tục nghiên cứu để tìm ra

các giải pháp hiệu quả hơn.

Nội dung chƣơng 1 sẽ trình bày một số định nghĩa và khái niệm liên

quan đến bài toán khai thác tập mục trên một CSDL nhƣ CSDL nhị phân,

CSDL có sự phân cấp các mục, CSDL số lƣợng và một biến thể của CSDL số

lƣợng là CSDL trọng số. Đồng thời chƣơng 1 giới thiệu tổng quát một số tiếp

7

cận chính cho bài toán khai thác tập mục trên các loại CSDL đó.

1.1.1. Một số khái niệm cơ bản

Định nghĩa 1.1. CSDL nhị phân (binary database) là một bộ gồm hai

thành phần: T, I trong đó:

T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL

I = {i1, i2, ..., in} là tập gồm n mục trong CSDL

Với giao dịch thứ k (k = 1..m): ={ } trong đó 0

hoặc 1, với j =

Ví dụ 1.1: Cho CSDL DB với tập các mục I = {A, B, C, D, E} và tập các

giao dịch T đƣợc biểu diễn bởi Bảng 1.1 nhƣ sau:

Bảng 1.1. Các giao dịch của CSDL nhị phân DB

Mục A B C D E Giao dịch

1 1 0 1 1 t1

0 1 1 1 0 t2

1 1 0 1 1 t3

1 1 1 0 1 t4

1 1 1 1 1 t5

0 1 1 0 1 t6

Các mục xuất hiện trong một giao dịch của CSDL tƣơng ứng có giá trị 1,

ngƣợc lại có giá trị 0. Ví dụ giao dịch t1 = {1, 1, 0, 1, 1} có nghĩa các mục A,

B, D, E có trong giao dịch, mục C không có trong giao dịch.

CSDL nhị phân là CSDL biểu diễn sự xuất hiện hay không của các mục

trong các giao dịch. Trong nhiều trƣờng hợp, các mục trong CSDL có mối

quan hệ với nhau đƣợc thể hiện qua các cây phân cấp, ví dụ "computer" là

8

mức khái quát của "Desktop" và "Notebook", hay "Printer" là mức khái quát

của "Laser priter", "Ink-Jet printer", v.v… Những CSDL có thể hiện mối quan

hệ của các mục thông qua cây phân cấp nhƣ trên đƣợc gọi là CSDL nhị phân

có sự phân cấp các mục.

Định nghĩa 1.2. CSDL nhị phân có sự phân cấp các mục

(hierarchical database) là một bộ gồm ba thành phần: T, I, Tr, trong đó:

T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL

I = {i1, i2, ..., in} là tập gồm n mục trong CSDL

Với giao dịch thứ k (k = 1..m): ={ } trong đó 0

hoặc 1, với j = 1..n.

Tr là cây phân cấp thể hiện mối quan hệ của các mục trong CSDL.

Cho CSDL nhị phân có sự phân cấp mục DB với tập các mục I =

{Desktop, Dot-matrix printer, Ink-jet printer, Laser printer, Notebook,

Scanner}, các giao dịch T đƣợc biểu diễn nhƣ Bảng 1.2 và cây phân cấp thể

hiện quan hệ các mục nhƣ Hình 1.1.

Bảng 1.2. Các giao dịch của CSDL nhị phân có sự phân cấp mục DB

Giao dịch Mục

Notebook, Laser printer t1

Scanner, Dot-matrix printer t2

Dot-matrix printer, Ink-jet printer t3

Notebook, Dot-matrix printer, Laser printer t4

Scanner t5

9

Desktop t6

Printer

Computer

Scanner

Non – impact Dot – matrix

Desktop

Notebook

Laser

Ink – jet

Hình 1.1. Cây phân cấp Tr

Để đơn giản, ta gán các mục trên cây phân cấp Tr bằng các ID nhƣ Bảng 1.3:

Bảng 1.3. ID các mục của DB

ID mục Tên mục

Desktop A

Ink-jet Printer B

Laser Printer C

Notebook D

Scanner E

Dot-matrix Printer F

Non-impact G

Computer H

Printer K

Từ ID đƣợc định nghĩa trong Bảng 1.3, các giao dịch trong Bảng 1.2 và

cây phân cấp Tr đƣợc biểu diễn lại nhƣ trong Bảng 1.4 và Hình 1.2.

Bảng 1.4. Các giao dịch của DB bằng ID

Giao dịch mục

D, C t1

E, F t2

F, B t3

D, F, C t4

E t5

10

A t6

H

K

E

G

D

A

F

C

B

Hình 1.2. Cây phân cấp Tr biểu diễn theo ID

Tập J = {G, K, H} là tập các mục cha của cây phân cấp không xuất hiện

trong các giao dịch của DB. Tuy nhiên chúng có vai trò nhất định, thể hiện

mối quan hệ của các mục trong DB. Do đó, khi khai thác FI trên CSDL phân

cấp đòi hỏi phải khai thác cả tập các mục trên cây phân cấp bao gồm (I J).

CSDL nhị phân là CSDL thể hiện sự có mặt hay không của mục trong

các giao dịch của CSDL mà không quan tâm đến giá trị (trọng số, lợi ích, số

lƣợng, v.v…) của các mục trong các giao dịch. Trong nhiều ứng dụng thực tế

nhƣ CSDL bán hàng trong siêu thị, CSDL đơn thuốc, v.v… mỗi mục trên mỗi

đơn hàng thƣờng kèm theo số lƣợng và giá trị của chúng. Các CSDL dạng

này đƣợc gọi là CSDL số lƣợng.

Định nghĩa 1.3. CSDL số lượng (quantitative database) là một bộ ba

thành phần: T, I, W, trong đó:

T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL

I = {i1, i2, ..., in} là tập gồm n mục trong CSDL

W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong

tập I

Với giao dịch thứ k (k = 1..m): tk = { , , …, }, là số tự nhiên

chỉ số lƣợng của mục thứ j trong giao dịch, j = 1..n.

Ví dụ 1.2: Cho CSDL số lƣợng DB với tập các mục I = {A, B, C, D, E},

các giao dịch T đƣợc biểu diễn trong Bảng 1.5, trọng số các mục nhƣ trong

11

bảng 1.6.

Bảng 1.5. Giao dịch của CSDL số lƣợng BD

Giao dịch

A B C D E

1 1 0 4 1

0 1 3 0 1

2 1 0 3 2

3 1 1 0 1

1 2 2 1 3

0 1 1 1 0

Bảng 1.6. Trọng số các mục trong DB

Mục Trọng số

A 0,6

B 0,1

C 0,3

D 0,9

E 0,2

Theo Bảng 1.5, DB có sáu giao dịch {t1, t2, t3, t4, t5, t6}, ví dụ giao dịch

= {1, 1, 0, 4, 1} có nghĩa là trong giao dịch có một mục A, một mục B, bốn

mục D, một mục E, không có mục C.

Trong nhiều ứng dựng thực tế, CSDL số lƣợng có thể không quan tâm

đến số lƣợng của các mục trong mỗi giao dịch, mà chỉ quan tâm đến trọng số

của chúng. Ví dụ CSDL vi phạm giao thông, ngƣời ta chỉ quan tâm là ngƣời

vi phạm lỗi gì và mức tiền phạt tƣơng ứng cho từng lỗi ấy, hay CSDL khám

bệnh, ngƣời ta quan tâm đến bệnh nhân có những triệu chứng gì mức độ nặng

nhẹ (trọng số) của từng triệu chứng ấy, v.v… Các CSDL đó đƣợc gọi là

CSDL có trọng số hay CSDL trọng số - một biến thể của CSDL số lƣợng với

12

số lƣợng của các mục xuất hiện trong CSDL là 1.

Định nghĩa 1.4. CSDL trọng số (weighted database) là một bộ gồm ba

thành phần: T, I, W, trong đó:

T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL

I = {i1, i2,.., in} là tập gồm n mục trong CSDL

W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong

tập I

Ví dụ 1.3: Cho CSDL trọng số DB với tập mục I = {A, B, C, D, E}, các

giao dịch đƣợc biểu diễn trong Bảng 1.7, trọng số các mục đƣợc thể hiện

trong Bảng 1.8.

Bảng 1.7. Các giao dịch của CSDL trọng số DB

Mục

A, B, D, E

B, C, E

A, B, D, E

A, B, C, E

A, B, C, D, E

B, C, D Giao dịch

Bảng 1.8. Trọng số của các mục của DB

mục Trọng số

A 0,6

B 0,1

C 0,3

D 0,9

E 0,2

Định nghĩa 1.5. Tidset của tập mục X là tập hợp các giao dịch chứa X.

Nhƣ vậy:

13

tidset(X) = {t|t T  X  t}

Định nghĩa 1.6. Độ hỗ trợ của một tập mục (support) là tần suất xuất

hiện của tập mục đó trong CSDL và đƣợc xác định theo công thức sau:

support(X) =

Trong đó:

- k là số giao dịch chứa X

- m là số lƣợng giao dịch của CSDL

Ví dụ 1.4: Dựa vào CSDL Bảng 1.1, ta có support(AB) = =

66,67% (tập mục AB xuất hiện trong bốn giao dịch t1, t3, t4, t5).

Để khai thác FI, ngƣời ta đƣa vào một ngƣỡng, gọi là ngƣỡng phổ biến

(minsup), tập mục phổ biến theo ngƣỡng minsup là tập mục có độ hỗ trợ

(support) lớn hơn hay bằng ngƣỡng minsup. Nhƣ vậy tập các tập mục phổ

biến - FI đƣợc xác định nhƣ sau:

FI = {X|X I và support(X) minsup}

Định nghĩa 1.7. FI gồm k phần tử theo ngƣỡng minsup cho trƣớc gọi là

k-itemset.

Định nghĩa 1.8. Rank của một tập mục X thuộc CSDL DB, kí hiệu RX

là một số nguyên chỉ thứ tự tập mục X theo độ phổ biến từ cao xuống thấp của

tất cả các tập mục thuộc CSDL DB.

RX = |{Y I | support(Y) support(X)}|

Định nghĩa 1.9. Cho một giá trị nguyên k và CSDL DB, k nhóm tập

mục phổ biến có độ phổ biến cao nhất ( Top - rank - k frequent itemsets -

TRFIk) của CSDL DB là tập các tập mục có hạng nhỏ hơn hoặc bằng k đƣợc

xác định nhƣ sau:

14

TRFIk = {X|X I và Rx k}

1.1.2. Bài toán khai thác FI

Bài toán khai thác FI trên CSDL DB cho trƣớc là bài toán tìm tất cả các

tập mục của CSDL có tần số xuất hiện trong các giao dịch thỏa mãn ngƣỡng

minsup do ngƣời dùng xác định trƣớc. Tập các tập mục đƣợc khai thác theo

ngƣỡng minsup đƣợc gọi là FI của DB.

Ví dụ 1.5: Xét CSDL trong Bảng 1.1. gồm sáu giao dịch đƣợc mô tả lại

nhƣ Bảng 1.9:

Bảng 1.9. CSDL DB

Giao dịch Các mục trong các giao dịch

A, B, D, E t1

B, C, E t2

A, B, D, E t3

A, B, C, E t4

A, B, C, D, E t5

B, C, D t6

FI của DB với minsup = 0,5 nhƣ sau:

FI = {A, B, C, D, E, AB, AD, AE, BC, BD, BE, DE, ABD, ABE, BDE,

ABDE}

Bài toán khai thác FI là bài toán tìm tất cả các tập mục của CSDL có tấn

suất xuất hiện thõa mãn ngƣỡng minsup cho trƣớc.

1.2. Các phƣơng pháp khai thác FI

1.2.1. Phương pháp khai thác FI trên CSDL ngang

CSDL ngang đƣợc hiểu là CSDL giao dịch đƣợc mô tả nhƣ các định

nghĩa về các loại CSDL đã nêu ở trên (Định nghĩa 1.1, đến Định nghĩa 1.4).

Có hai phƣơng pháp chính khai thác FI trên CSDL ngang đó là Apriori và FP-

15

Growth.

1.2.1.1. Thuật toán Apriori

Thuật toán Apriori [1, 3] do Agrawal và các đồng sự đề xuất năm 1994.

Thuật toán này khai thác FI bằng cách quét CSDL nhiều lần. Ý tƣởng nhƣ

sau: Thuật toán quét CSDL lần thứ nhất để sinh ra tập1-itemset phổ biến, từ

tập 1-itemset phổ biến quét CSDL lần thứ hai để sinh ra tập 2-itemset phổ

biến, v.v… cho đến khi không tìm đƣợc bất kì tập phổ biến nào nữa thì dừng.

Thuật toán Apriori dựa trên tính chất đƣợc đặt tên là tính chất Apriori (còn

đƣợc gọi là tính chất bao đóng giảm) nhƣ sau:

Cho hai tập mục X và Y của CSDL DB:

Nếu X Y ⟹ support(X) support(Y)

Do đó:

Nếu support(X) minsup ⟹Y  X, support(Y) minsup

Nếu (Y) minsup ⟹X Y, support(X) minsup

Dựa vào tính chất trên, thuật toán Apriori [1] đƣợc mô tả nhƣ trong

Thuật toán 1.1: Apriori

Input: CSDL DB và một ngưỡng minsup

Output: Các FI của DB thỏa minsup

1. Quét CSDL để tính support của các 1 - itemset, so sánh support với

minsup để lọc ra FI gồm 1-itemset (L1) thỏa mãn minsup

2. Sử dụng Lk-1 để sinh ra ứng viên k-itemset. Sau đó quét CSDL để tính

support của các ứng viên và loại bỏ các k-itemset không phải là FI thu

được k-itemset phổ biến (Lk).

3. Lặp lại bước 2 cho đến khi không tạo ra ứng viên nào nữa. FI khai thác

được = L1 L2...

Hình 1.3:

16

Hình 1.3. Thuật toán Apriori trong khai thác FI

Ngày nay các CSDL thực tế có xu hƣớng tăng rất nhanh về dung lƣợng,

bởi vậy việc quét CSDL nhiều lần là không khả thi do rất tốn thời gian. Đồng

thời việc sinh ra tập các ứng viên ở mỗi bƣớc quét CSDL cần lƣợng bộ nhớ

lớn để lƣu trữ. Do đó thuật toán Apriori ít đƣợc quan tâm nghiên cứu và sử

dụng trong thời gian gần đây.

1.2.1.2. Thuật toán FP-Growth với cấu trúc FP-tree

Thuật toán FP-Growth [18] do Han và đồng sự đề xuất năm 2000 đã phần

nào giải quyết các hạn chế của Apriori về cả thời gian xử lý và bộ nhớ sử dụng.

Tiếp sau đó Grahne và đồng sự đề xuất FP-Growth* [19]. Đây là một tiếp cận

thú vị với việc sử dụng cấu trúc cây FP-tree (Frequent Partern-tree) để nén toàn

bộ CSDL với mỗi nút trên FP-tree là các mục của CSDL ban đầu. Đồng thời,

thuật toán FP-Growth chỉ cần hai lần quét CSDL, giảm đáng kể thời gian so

với thuật toán Apriori, đặc biệt là trong các trƣờng hợp CSDL lớn.

Bƣớc đầu tiên, thuật toán FP-Growth quét CSDL và sắp xếp lại trật tự

các mục theo thứ tự tần suất xuất hiện giảm dần trên mỗi giao dịch. Bƣớc thứ

2, FP-Growth quét CSDL và nén toàn bộ dữ liệu lên cây FP-tree. Bƣớc thứ 3,

duyệt FP-tree để khai thác các FI:

Thuật toán 1.2: FP-Growth

Input: CSDL DB và một ngưỡng minsup

Output: Các FI của DB thỏa minsup

1. Quét toàn bộ CSDL DB và tính độ hỗ trợ (support) của từng mục. Sau đó

xác định những mục có support lớn hơn minsup và sắp xếp giảm dần

theo support vào trong f_list.

2. Tạo cây FP-tree chỉ có một nút gốc được gán nhãn là “null” ký hiệu root.

a. Với mỗi giao dịch trong DB được thể hiện như sau: chọn và sắp xếp

những danh mục phổ biến theo thứ tự giảm dần trong f_list.

b. Chèn các mục lên cây FP-tree

3. Duyệt cây FP-tree để khai thác các FI thỏa mãn minsup

Thuật toán FP-Growth đƣợc mô tả nhƣ trong Hình 1.4

17

Hình 1.4. Thuật toán FP-Growth khai thác FI dựa trên cấu trúc FP-tree

Hạn chế của thuật toán này là quét CSDL đến hai lần và đặc biệt là tốn

thời gian trong duyệt cây FP-tree để xây dựng các FI.

1.2.2. Phương pháp khai thác FI trên CSDL dọc dựa trên IT-tree

Thuật toán Eclat [49] đƣợc đề xuất bởi Zaki sử dụng cấu trúc IT-tree

(Tidset Itemset-tree) để lƣu tidset của các tập mục trên mỗi nút và đƣa ra khái

niệm lớp tƣơng đƣơng để kết nối các tập mục trong cùng một lớp tƣơng

đƣơng để tạo ra tập mục mới. Thuật toán Eclat với chỉ một lần quét CSDL là

một tiếp cận hiện đại, tiết kiệm thời gian xử lý và có thể áp dụng khai thác FI

trên nhiều loại CSDL một cách hiệu quả. Trong đó, nhiều nghiên cứu đã mở

rộng và biến đổi cấu trúc IT-tree một cách phù hợp để áp dụng khai thác FI

trên nhiều loại CSDL khác nhƣ khai thác trên CSDL trọng số [37] CSDL số

lƣợng [39] và CSDL có sự phân cấp các mục [36] một cách hiệu quả hơn.

Tiếp cận Eclat sử dụng tính chất Apriori để cắt nhánh các tập mục không

thỏa ngƣỡng phổ biến. Do vậy các tập mục trên IT-tree là các FI thỏa mãn

ngƣỡng minsup.

Nhƣ vậy nếu tập mục X không thỏa mãn ngƣỡng minsup thì các tập mục

là phủ của X cũng không thỏa ngƣỡng minsup, do vậy ta không cần xét nhánh

do tập mục X tạo ra. Áp dụng tính chất bao đóng giảm trên cây IT-tree sẽ cắt

nhánh đƣợc tất cả các nhánh chắc chắn không chứa FI và các tập mục trên IT-

tree chính là FI cần khai thác.

1.2.2.1. Cấu trúc IT-tree

IT-tree có cấu trúc gồm nhiều mức, mỗi mức gồm nhiều lớp tƣơng

đƣơng. Mỗi lớp tƣơng đƣơng gồm các nút có cùng nút cha ở mức trên. Mỗi

nút gồm hai thành phần:

- Tập mục X

- Tidset của X

Mỗi lớp tƣơng đƣơng đƣợc tạo ra từ một mục cha ở mức trên kết hợp lần

lƣợt các nút phía sau nó trong cùng một lớp tƣơng đƣơng. Do vậy các nút

18

trong cùng một lớp tƣơng đƣơng có cùng số lƣợng phần tử chỉ khác nhau

phần tử cuối cùng. Một nút mới đƣợc chèn vào IT-tree nếu độ hỗ trợ

(support) của nó thỏa mãn ngƣỡng phổ biến (minsup) do đó các nút trên IT-

tree sau khi xây dựng xong chính là các FI cần khai thác.

Thuật toán 1.3: Eclat

Input: CSDL DB và một ngưỡng minsup

Output: Các FI của DB thỏa minsup

Method: Eclat

1. Quét toàn bộ CSDL DB để xác định tập giao dịch (tidset) của các mục.

Chọn các mục có support thỏa ngưỡng minsup (1-itemset).

2. Chèn 1-itemset vào mức 1 của IT-tree

3. Mỗi nút ở mức k - 1 kết hợp với các nút có cùng nút cha với nó tạo ra các

nút ở mức k nếu support của các nút này thỏa ngưỡng minsup.

4. Lặp lại bước 3 cho đến khi không thể tạo thêm nút mới trên IT-tree.

5. Duyệt cây IT-tree để lấy ra các FI (Tất cả các nút trên IT-tree là FI).

1.2.2.2. Thuật toán Eclat

Hình 1.5. Thuật toán Eclat dựa trên cấu trúc IT-tree

Ví dụ 1.6: Cho CSDL nhị phân DB trong ví dụ 1.1 và minsup = 0,5:

Bước 1: Quét CSDL chuyển sang CSDL theo chiều dọc nhƣ trong Bảng

1.10

Bảng 1.10. CSDL DB theo chiều dọc

Mục Tidset

A 1, 3, 4, 5

B 1, 2, 3, 4, 5, 6

C 2, 4, 5, 6

D 1, 3, 5, 6

E 1, 2, 3, 4, 5

19

Bước 2 và 3: IT-tree đƣợc xây dựng với ngƣỡng minsup = 0,5.

{}

D1,3,5,6 E1,2,3,4,5

B1,2,3,4,5,6 C2,4,5,6

A1,3,4,5

BC2,4,5,6 BD1,3,5,6

BE1,2,3,4,5

AD1,3,5 AE1,3,4,5

DE1,3,5

ABD1,3,5 ABE1,3,4,5

ADE1,3,5

BCE2,4,5 BDE1,3,5

ABDE1,3,5

AB1,3,4,5

Hình 1.6. Cây IT tree với minsup = 0,5 của CSDL DB

Đầu tiên, tập 1-itemset đƣợc đƣa vào mức đầu tiên của cây IT-tree. Sau

đó, các cặp nút trong cùng một lớp tƣơng đƣơng đƣợc kết nối với nhau để tạo

ra các tập mục mới ở mức tiếp theo nếu tập mục mới thỏa mãn ngƣỡng

minsup nhƣ trên Hình 1.4.

Bước 4: Các FI khai thác đƣợc: {A, B, C, D, E, AB, AD, AE, BC, BD,

BE, DE, ABD, ABE, ADE, BCE, BDE, ABDE}

Thuật toán Eclat với cấu trúc IT-tree là hƣớng tiếp cận tốt đƣợc biết đến

hiện nay với chỉ một lần quét CSDL. Tuy nhiên, phƣơng pháp này có nhƣợc

điểm lớn là tốn bộ nhớ sử dụng để lƣu tidset của các tập mục, do mỗi giao

dịch chứa tập mục cần một ô nhớ. Đồng thời bộ nhớ tạm cần thiết trong quá

trình tính toán trung gian cũng rất lớn. Các hạn chế này làm cho thời gian tính

toán của thuật toán Eclat chƣa đƣợc tối ƣu. Do đó, nghiên cứu đề xuất các

phƣơng pháp mới nhằm tối ƣu bộ nhớ để nâng cao hiệu quả khai thác FI trên

các loại CSDL theo hƣớng tiếp cận này có tính thực tế cao. Đây cũng chính là

20

một trong những mục tiêu nghiên cứu của luận án.

1.3. Một số phƣơng pháp khai thác FWI và FWUI trên CSDL số lƣợng

1.3.1. Giới thiệu

CSDL số lƣợng theo Định nghĩa 1.3 là CSDL đƣợc xuất hiện nhiều trong

thực tế, ví dụ CSDL giao dịch bán hàng trong các siêu thị, CSDL các đơn

thuốc, v.v… Trong đó các giao dịch có số lƣợng các mặt hàng cùng lợi nhuận

(lợi ích) của các mặt hàng đó. Do đó, bài toán khai thác FWI và FWUI từ

CSDL số lƣợng đƣợc nhiều ngƣời quan tâm nghiên cứu.

Một dạng rút gọn của CSDL số lƣợng là CSDL trọng số (Định nghĩa 1.4)

với các giao dịch nhị phân, tức là các mục xuất hiện trong giao dịch là 1, các

mục không xuất hiện là 0, mỗi mục có một trọng số xác định. CSDL trọng số

cũng là CSDL đƣợc sử dụng nhiều trong các ứng dụng thực tế. Với CSDL

trọng số, ngƣời ta không quan tâm đến số lƣợng mỗi mục trong các giao dịch,

mà quan tâm đến mục đó có xuất hiện hay không và trọng số của nó. Ví dụ

CSDL tai nạn giao thông, với mỗi vụ tai nạn giao thông ngƣời ta chỉ cần biết có

lỗi A, lỗi B và mức phạt của các lỗi ấy, hay CSDL bệnh nhân, mỗi ngƣời bệnh

có một số triệu chứng và các triệu chứng đó nặng hay nhẹ, ở mức độ nào, v.v…

Do đó, bên cạnh khai thác FWUI trên CSDL số lƣợng thì khai thác FWI trên

CSDL trọng số cũng đƣợc quan tâm khai thác từ nhiều nhóm nghiên cứu về

khai thác dữ liệu trên thế giới [7, 22, 23, 32, 34, 37, 42, 43, 44, 45, 46, 47, 48].

1.3.2. Khai thác FWI

1.3.2.1. Giới thiệu

Bài toán khai thác FWI đƣợc đề xuất lần đầu tiên bởi Ramkumar và

đồng sự [32], trong nghiên cứu này, các tác giả đã đƣa ra mô hình mô tả khái

niệm về luật kết hợp có trọng số, trong đó đề xuất thuật toán WIS để khai thác

FWI. Sau đó, việc nghiên cứu bài toán khai thác FWI đƣợc chia làm hai

hƣớng tiếp cận riêng biệt dựa theo các cách thức xác định độ đo hỗ trợ trọng

21

số (weight support - ws) khác nhau.

Hƣớng tiếp cận thứ nhất khởi đầu bởi Yun và đồng sự [45] sử dụng một

hàm trung bình để tính trọng số của tập mục, từ đó tính ws của tập mục bằng

tích của trọng số và độ hỗ trợ của tập mục đó. Do tính trọng số của tập mục

bằng hàm trung bình nên một tập mục có thể nhận giá trị trọng số lớn hơn khi

thêm vào một mục mới, điều này không đảm bảo tính chất bao đóng giảm. Để

giải quyết vấn đề, Yun & Leggett [46] đề xuất thuật toán WSPAN sử dụng mô

hình maximum-weighted-upper-bound, trong đó các mục đƣợc gán các giá trị

khác nhau trong phạm vi weight - range đƣợc định nghĩa trƣớc. Sau đó, Lan và

các đồng sự [21] (tƣơng tự [47, 48]) đề xuất tiếp mô hình sequence -maximum-

weight để rút gọn lại upper-bound của các ws nhằm giảm bớt số lƣợng ứng

viên trong quá trình khai thác. Cách tiếp cận theo hƣớng này xem xét song

song trọng số và độ hỗ trợ của tập mục trong quá trình khai thác. Thêm nữa,

theo cách tính ws của cách tiếp cận này, một tập mục xuất hiện trong giao dịch

ti cũng tƣơng đƣơng với xuất hiện trong giao dịch tj, điều này không phản ánh

đƣợc tầm quan trọng khác nhau của các giao dịch trong CSDL thực tế.

Hƣớng tiếp cận thứ hai đƣợc đề xuất lần đầu tiên bởi Tao và đồng sự

[34] dựa trên độ đo trọng số giao dịch (transaction weight - tw) đƣợc tính

bằng trung bình cộng các trọng số của các mục có trong giao dịch và giá trị

ws của một tập mục đƣợc xác định bằng tỉ số giữa tổng các tw của các giao

dịch có chứa tập mục đó và cho tổng tw của tất cả giao dịch. Theo cách tiếp

cận này thì giá trị ws của tập mục vừa phản ánh đƣợc mức độ xuất hiện của

tập mục trong các giao dịch, vừa thể hiện đƣợc mức độ quan trọng khác nhau

của các giao dịch. Một ƣu điểm nữa của cách tiếp cận này là thỏa mãn tính

chất bao đóng giảm một cách tự nhiên. Tuy nhiên, thuật toán do Tao và đồng

sự đề xuất dựa vào việc sinh ứng viên theo phƣơng pháp Apriori nên cần đọc

CSDL nhiều lần, dẫn đến tốn thời gian xử lý và cả bộ nhớ lƣu trữ. Tiếp theo,

Vo và các đồng sự [37] đề xuất cách thức lƣu trữ trọng số trên cây WIT-tree,

một mở rộng của cây IT-tree. Do chỉ cần quét CSDL một lần, cùng với áp

22

dụng chiến lƣợc Diffset để khai thác FWI trên cây WIT-tree, nên phƣơng

pháp này tỏ ra hiệu quả hơn phƣơng pháp theo hƣớng tiếp cận Apriori trƣớc

đó. Hạn chế của phƣơng pháp này là ở chỗ tốn bộ nhớ để lƣu trữ tidset, đó

cũng là nguyên nhân làm cho thời gian xử lý chƣa đƣợc tối ƣu.

Theo hƣớng tiếp cận thứ hai này, Tao [34] và các đồng sự đƣa ra công

thức tính các đại lƣợng trọng số giao dịch (transaction weight - tw) và độ hỗ

trợ trọng số (weight support - ws), trong đó tw của một giao dịch là trung bình

cộng của trọng số của các mục trong giao dịch đó, còn ws của một tập mục là

thƣơng của tổng tw của các giao dịch chƣa tập mục đó với tổng tw của CSDL.

Cách tính này đƣợc thể hiện qua hai định nghĩa 1.11 và 1.12 nhƣ sau:

Định nghĩa 1.10. Trọng số giao dịch của các giao dịch tw đƣợc xác

định nhƣ công thức 1.1:

∑ tw(tk) =

( )

(1.1)

Với:

– tw( ) là trọng số giao dịch của

– là trọng số của mục trong

– là số các mục có mặt trong

Từ CSDL trọng số DB trong ví dụ 1.3, ta có giá trị tw của các giao dịch

đƣợc tính nhƣ trong Bảng 1.11:

Bảng 1.11. Giá trị tw của CSDL DB trong ví dụ 1.4 Giao dịch Tw

= 0,45 t1 tw(t1) =

= 0,20 t2 tw(t2) =

= 0,45 t3 tw(t3) =

= 0,30 t4 tw(t4) =

= 0,42 t5 tw(t5) =

0,45+0,20+0,45+0,30+0,42+0,43

= 0,43 t6 tw(t6) =

23

= 2,25 Sum_tw

Định nghĩa 1.11. Độ hỗ trợ trọng số (ws) của tập mục X đƣợc tính

nhƣ công thức 1.2:

∑ (1.2)

Với, t(X) là tập các giao dịch chứa tập mục X và sum_tw = ∑

ws(BD) =

0,78.

Với tập mục BD trong DB ở ví dụ 1.3 đƣợc xác định nhƣ sau:

Tập mục X đƣợc gọi là phổ biến nếu và chỉ nếu ws(X) minws, với

minws đƣợc xác định bởi ngƣời sử dụng. Bài toán khai thác FWI trên CSDL

trọng số là bài toán tìm tất cả các tập mục X (X I) thỏa mãn ws(X) minws.

1.3.2.2. Một số nghiên cứu liên quan

Ramkumar và các đồng sự [32] đƣa ra bài toán khai thác FWI trên

CSDL trọng số. Sau đó, Tao và đồng sự [34] đề xuất mô hình giải quyết bài

toán này dựa trên hai đại lƣợng trọng số giao dịch (tw) và độ hỗ trợ trọng số

(ws) với công thức tính nhƣ trên trong định nghĩa 1.15 và định nghĩa 1.16.

Vo và các đồng sự [37] đề xuất cấu trúc WIT-tree là một mở rộng của

IT-tree [49]. Mỗi nút trên WIT-tree gồm ba thành phần ws, itemset, tidset.

Sự kết nối hai nút trong cùng một lớp tƣơng đƣơng ở mức k tạo ra nút mới ở

mức k+1, nếu ws của tập mục mới tạo thành này thỏa ngƣỡng minws, tập mục

ở nút mới chính là hợp từ hai tập mục của hai nút phía trên và tidset mới

chính là giao của hai tidset của hai nút đó. Sau khi xây dựng xong WIT-tree,

các tập mục trên cây chính là tất cả các FWI thỏa ngƣỡng khai thác minws.

Tuy nhiên các tiếp cận này chƣa đƣợc tối ƣu cả về thời gian lẫn bộ nhớ.

1.3.3. Khai thác FWUI

Bên cạnh khai thác FWI, bài toán khai thác FWUI cũng nhận đƣợc một

số quan tâm nghiên cứu [21, 39]. Việc khai thác FWUI liên quan đến việc xác

định trọng số hữu ích của các giao dịch twu (transaction weight utility) và độ

24

hỗ trợ trọng số hữu ích wus (weight utility support).

Khan và đồng sự [21] đã đƣa ra định nghĩa hai đại lƣợng là trọng số hữu

ích của giao dịch - transaction weight utility (twu) và độ hỗ trợ trọng số hữu

ích - weight utility support (wus) đƣợc biểu diễn lại nhƣ sau:

Định nghĩa 1.12. Trọng số hữu ích của các giao dịch twu đƣợc định

nghĩa nhƣ công thức 1.3:

∑

(1.3) twu( ) =

Với:

- twu( ) là trọng số hữu ích của ;

- là số lƣợng mục thứ i trong , i [1,…, n];

- là trọng số của mục i;

- s( là tổng các mục trong giao dịch

Bảng 1.12 là giá trị twu của các giao dịch của CSDL DB đƣợc cho trong

ví dụ 1.2

Tid

Twu

1,13

t1

6 9 4 2 7

0,4

t2

3 3 2 5

1,1

t3

6 2 9 3 2 2 8

0,6

t4

6 3 3 2 6

0,58

t5

6 2 3 2 9 2 3 9

0,43

t6

3 9 3

Sum_twu 1,13 + 0,4 + 1,1 + 0,6 + 0,58 + 0,43 =

4,24

25

Bảng 1.12. twu các giao dịch của DB trong ví dụ 1.2

Định nghĩa 1.13. Độ hỗ trợ trọng số hữu ích của các tập mục wus đƣợc

định nghĩa nhƣ công thức 1.4:

∑ wus(X) =

(1.4)

Với, T(X) là tập các giao dịch chứa tập mục X và sum_twu =

∑ .

Một tập mục X đƣợc gọi là phổ biến với ngƣỡng minwus (do ngƣời sử

dụng đƣa vào) nếu wus(X) minwus. Bài toán xác định tập mục phổ biến trên

CSDL số lƣợng là bài toán xác định tất cả các tập X sao cho X I và wus(X)

minwus.

Các tập mục phổ biến xác định theo minwus thỏa ngƣỡng tính chất bao

đóng giảm, điều này đã đƣợc chứng minh trong [40].

Khan và các đồng sự [21] đề xuất bài toán khai thác FWUI bằng việc đề

xuất hai độ đo trong khai thác FWUI là trọng số hữu ích của giao dịch - twu

và độ hỗ trợ trọng số hữu ích - wus, đồng thời đề xuất một “framework” trong

việc giải quyết bài toán khai thác FWUI dựa trên hai độ đo này.

Vo và các đồng sự đề xuất một cấu trúc dữ liệu có tên MWIT-tree [39] là

một mở rộng khác của IT-tree để khai thác FWUI với chỉ một lần quét dữ liệu

dựa trên tính chất bao đóng giảm của wus. Cấu trúc này gồm nhiều nút mỗi

nút gồm ba thành phần {X, t(X), wus(X)} trong đó X là tập mục, t(X) là

tidset(X) và wus(X) là độ hỗ trợ trọng số hữu ích của X. Tuy nhiên tiếp cận

này có hạn chế là bộ nhớ sử dụng lƣu trữ tidset của các tập mục còn rất lớn,

điều này ảnh hƣởng đến thời gian khai thác FWUI.

1.3.4. Khai thác TRFIk

Khai thác FI là bài toán trọng tâm trong khai thác dữ liệu đƣợc nhiều

nhóm nghiên cứu quan tâm. Tuy nhiên, trong nhiều trƣờng hợp khai thác FI

với ngƣỡng cho trƣớc không đáp ứng đƣợc các đòi hỏi thực tế. Ví dụ, với

26

ngƣỡng minsup đƣa vào thì số lƣợng các FI khai thác đƣợc quá nhiều hoặc

quá ít, nghĩa là ngƣời sử dụng không kiểm soát đƣợc số lƣợng các FI tìm thấy,

v.v… Trong những trƣờng hợp nhƣ vậy khai thác TRFIk sẽ giải quyết đƣợc

yêu cầu trên.

Fang và các đồng sự [17] đã đề xuất thuật toán VTK để khai thác TRFIk

trên CSDL nhị phân. Thuật toán VTK khai thác dữ liệu theo chiều dọc gồm

hai bƣớc. Đầu tiên VTK quét CSDL để chuyển dữ liệu sang chiều dọc và tính

support của các 1-itemset và đƣa chúng vào TRFI-Table theo thứ tự giảm dần

của support. Mỗi thành phần trên TRFI-Table gồm hai thành phần, một là

count (support của tập mục) hai là danh sách các tập mục có cùng support.

Bƣớc thứ 2, các l-itemset trong TRFI-Table đƣợc kết nối với nhau để tạo ra

các (l+1)-itemset, các tập mục mới đƣợc tạo thành sẽ đƣợc chèn vào TRFI-

Table nếu support của nó lớn hơn giá trị tại chỉ số k của TRFI-Table (phần tử

cuối của TRFI-Table). Thuật toán kết thúc khi không còn tập mục nào đƣợc

cập nhật vào TRFI-Table. VTK là một thuật toán khá hiệu quả song nó có

một số điểm yếu nhƣ:

- Bộ nhớ sử dụng lớn trong lƣu trữ tidset của các tập mục.

cặp với m là số lƣợng các tập

- Tốn nhiều thời gian thực hiện kết nối các l-itemset để tạo ra (l+1)-

itemset từ TRFI-Table, do phải xét

mục trong TRFI-Table.

Deng và các đồng sự [8,10] đã đề xuất thuật toán NTK dựa trên cấu trúc

N-list để tiết kiệm bộ nhớ, giảm thời gian tính toán trong khai thác TRFIk.

NTK tạo ra cây PPC-tree giống với cây FP-tree. Dựa trên PPC-tree sinh ra N-

list của các 1-itemset, từ đó khai thác TRFIk. NTK tuy đã cải thiện đƣợc bộ

nhớ lƣu trữ tidset của các tập mục, song vẫn tốn thời gian nhiều do quét

CSDL hai lần để tạo ra PPC-tree.

Le cùng các đồng sự [26] đƣa ra một cải tiến của NTK với thuật toán

27

iNTK dựa trên cấu trúc N-list giúp giảm thời gian trong tính giao các N-list

của các tập mục. Tuy nhiên cũng nhƣ NTK thuật toán iNTK vẫn phải quét

CSDL hai lần để tạo cây PPC-tree và tốn thời gian duyệt cây để tạo N-list của

1-itemset.

Hai thuật toán NTK và iNTK cải tiến đƣợc bộ nhớ nhƣng vẫn gặp phải

hạn chế thứ hai của VTK đã nêu ở trên.

1.4. Khai thác FI trên CSDL có sự phân cấp các mục

CSDL có sự phân cấp các mục theo Định nghĩa 1.2 là CSDL có nhiều

trong các ứng dụng thực tế, trong đó các mục trong CSDL có mối quan hệ

nhất định với nhau thông qua cây phân cấp, các mục tại nút lá là các mục

có mặt trong các giao dịch trong CSDL, các mục ở nút cha trên cây phân

cấp là các mục ở mức khái quát của các mục nút lá. Do đó, bài toán này đã

nhận đƣợc sự quan tâm từ nhiều nhóm nghiên cứu [4, 5, 6, 14, 15, 20, 28,

30, 35, 36].

Một số định nghĩa liên quan đến khai thác FI trên CSDL có sự phân cấp

các mục đƣợc trình bày trong [30]:

Một giao dịch trên CSDL có sự phân cấp các mục t = tid, X, X = (Y

Z) là tập các mục có trong giao dịch (Y) và các mục cha của Y trên cây phân

cấp (Z).

Định nghĩa 1.14. Tập X là FI thì support(X) minsup, đồng thời

trong X không tồn tại một cặp mục nào có quan hệ cha con, nhƣ vậy X là

phổ biến khi:

{  ( )

Có hai tiếp cận khai thác FI trên CSDL có sự phân cấp các mục, đó là

khai thác với một ngƣỡng phổ biến và khai thác với nhiều ngƣỡng phổ biến.

28

Các ngƣỡng phổ biến khác nhau đối với mỗi cấp trên cây phân cấp.

Khai thác với một ngưỡng phổ biến

Khai thác FI trên CSDL phân cấp sử dụng cùng một ngƣỡng phổ biến là

việc coi các mục cha trên cấp phân cấp và các mục con (là các mục trong

CSDL) có cùng một vai trò nhƣ nhau, đƣợc khai thác với cùng một ngƣỡng

phổ biến. Một số nghiên cứu theo tiếp cận này nhƣ [4, 5, 15, 20]. Tuy nhiên,

trong nhiều CSDL thực tế các mục tuy ít xuất hiện nhƣng lại quan trọng và

cần đƣợc quan tâm hơn các mục khác. Đồng thời các mục cha trên cây phân

cấp sẽ có tần suất xuất hiện nhiều hơn sau khi đƣợc thêm vào CSDL để khai

thác. Do đó, khi khai thác nhiều khả năng sẽ ít xuất hiện các mục con trong

các tập mục phổ biến tìm thấy. Do vậy cần đặt ra nhiều ngƣỡng phổ biến để

có thể lọc đƣợc các tập mục phổ biến đáp ứng đƣợc nhu cầu của ngƣời sử

dụng. Từ đó hình thành một tiếp cập khác rất tự nhiên là ngƣời ta sử dụng

nhiều ngƣỡng phổ biến để khai thác.

Khai thác với nhiều ngưỡng phổ biến

Khai thác tập mục phổ biến trên CSDL phân cấp mà mỗi mục đƣợc xác

định một ngƣỡng hỗ trợ khác nhau, điều này giúp cho việc khai thác các luật

kết hợp thú vị từ các mục ít xuất hiện trong CSDL nhƣng lại có tầm quan

trọng cao hơn các mục khác. Một số nghiên cứu theo hƣớng này [30, 35] đã

cho rằng việc khai thác tập mục phổ biến với nhiều ngƣỡng hỗ trợ là cần thiết

và cần đƣợc đầu tƣ nghiên cứu hơn nữa trên nhiều loại CSDL khác nhau.

Định nghĩa 1.15. ms(x) là độ hỗ trợ nhỏ nhất của mục x (I J), một

tập mục X = {x1, x2, …, xk} với xi (I J) và 1 i đƣợc gọi là phổ biến

nếu:

support(X) ms(xi)

Liu và các đồng sự [30] đề xuất bài toán khai thác tập mục phổ biến trên

CSDL có sự phân cấp các mục với nhiều ngƣỡng hỗ trợ theo tiếp cận Apriori.

29

Tiếp đến, Tseng và đồng sự [35] đƣa ra các công thức xác định các ngƣỡng

hỗ trợ tối thiểu đối với các mục, từ đó đƣa ra công thức tính ngƣỡng hỗ trợ

cho các tập mục. Sau đó sử dụng phƣơng pháp sinh ứng viên theo hƣớng tiếp

cận Apriori để khai thác FI. Phƣơng pháp này có đặc điểm ngƣời sử dụng tự

đƣa ra các ngƣỡng tối thiểu cho các mục theo quan điểm cá nhân để có thể

khai thác đƣợc các luật thú vị, tuy nhiên chính điều này cũng làm khó khăn

cho ngƣời sử dụng khi số lƣợng các mục cần quan tâm lớn. Đồng thời cách

tiếp cận Apriori tốn nhiều thời gian khai thác do quét CSDL nhiều lần.

Kế thừa các công thức từ [30], Vo và các đồng sự [36] sử dụng hƣớng

tiếp cận theo thuật toán Eclat [49] với việc đề xuất cấu trúc dữ liệu GIT-tree

là một mở rộng của IT-tree. Tuy nhiên, hạn chế của nghiên cứu này là việc

thêm các mục cha trên cây phân cấp vào các giao dịch của CSDL, thao tác

này làm tăng bộ nhớ lƣu trữ CSDL dẫn đến tăng thời gian khai thác do phải

phai thác trên CSDL lớn hơn.

Với CSDL phân cấp DB trong Ví dụ 1.2, sau khi thêm các mục cha vào

các giao dịch có chứa nút con, CSDL mới sẽ gồm các giao dịch nhƣ Bảng

1.13:

Bảng 1.13. DB trong Ví dụ 1.2 sau khi thêm mục cha

Giao dịch Mục

D, C, G, K, H t1

E, F, K t2

F, B, G, K t3

t4 D, F, C, G, K, H

E t5

A, H t6

Nhƣ vậy, DB bao gồm sáu giao dịch tổng cộng mƣời một mục nhƣ trong

Bảng 1.4, sau khi thêm các mục cha vào các giao dịch có chứa mục con ta có

30

CSDL DB mới gồm sáu giao dịch và hai mƣơi mốt mục nhƣ trong Bảng 1.13.

1.5. Tiếp cận bit-vector trong khai thác FI

Các thuật toán khai thác FI dựa trên IT-tree trên CSDL nhị phân hay các

mở rộng của IT-tree để khai thác trên các loại CSDL khác nhƣ: cấu trúc GIT-

tree khai thác FI trên CSDL nhị phân có sự phân cấp các mục, cấu trúc WIT-

tree dùng trong khai thác FWI trên CSDL trọng số, hay MWIT-tree dùng

trong khai thác FWUI trên CSDL số lƣợng, v.v… cho thấy hiệu quả cao về

mặt thời gian do chỉ cần duyệt dữ liệu một lần. Tuy nhiên nhƣ đã phân tích ở

trên, bộ nhớ sử dụng lƣu tidset của các tập mục là rất lớn.

Đã có một số nghiên cứu nhằm tối ƣu hóa bộ nhớ để nâng cao hiệu quả

của các phƣơng pháp dựa trên IT-tree. Một trong số đó là thuật toán dEclat

[50] do Zaki và đồng sự đề xuất với cấu trúc diffset thay vì tidset. Tuy nhiên

diffset chỉ có hiệu quả trên CSDL dày (là CSDL có nhiều mục trên mỗi giao

dịch). Trong khi thực tế CSDL thƣa lại rất phổ biến.

Một hƣớng hiệu quả là sử dụng phƣơng pháp bit-vector do tiết kiệm

đƣợc bộ nhớ lƣu trữ tidset (mỗi giao dịch chỉ cần một bit), đồng thời tận dụng

đƣợc tốc độ cao của các phép toán trên bit (bitwise).

Đầu tiên, Luoie & Liu [31] đề xuất sử dụng bit-vector trong biểu diễn

tidset của các tập mục và sau đó Dong & Han [13] (Song và các đồng sự [33])

cụ thể hóa bằng đề xuất cấu trúc BitTable, với việc sử dụng bit-vector bằng

mảng các byte để ghi nhận các giao dịch của tập mục. BitTable chỉ cần sử

dụng ( +1) byte cho mỗi tập mục để lƣu tidset (T là số lƣợng giao dịch trong

CSDL), đồng thời sử dụng phép toán AND trên bit để tính giao hai tidset

nhằm xác định tidset của tập mục mới từ hai tập mục đã có.

Tuy nhiên, với CSDL có số lƣợng các giao dịch lớn, thì việc biểu diễn

trên BitTable có thể chƣa hiệu quả bởi BitTable chứa nhiều byte có giá trị = 0,

(do BitTable của mỗi tập mục sử dụng lƣợng bộ nhớ bằng nhau là ( +1)

31

byte). Điều này làm cho phƣơng pháp sử dụng BitTable trong biểu diễn tidset

lãng phí bộ nhớ, đồng thời dẫn đến tốn thời gian trong xác định giao của hai

BitTable.

Tiếp đến, Vo và các đồng sự đề xuất cấu trúc DBV (Dynamic bit-vector)

[38] là một cải tiến của BitTable với việc loại bỏ các byte có giá trị bằng 0 ở

đầu và cuối trong biểu diễn tidset trên mảng byte.

Tuy nhiên DBV còn chứa nhiều byte có giá trị bằng 0 “ở giữa”, điều này

làm cho cấu trúc DBV chƣa thật sự tối ƣu về bộ nhớ, do đó tốn thời gian khi

tính toán trên các byte có giá trị bằng 0. Đặc biệt trên các CSDL thƣa, số

lƣợng các byte có giá trị bằng 0 rất lớn.

Ngoài ra, cấu trúc BitTable và DBV sử dụng mảng byte. Do đó, số lƣợng

các phần tử của mỗi DBV là khá lớn, nhất là trên các CSDL có số lƣợng giao

dịch nhiều. Nghiên cứu sử dụng các phần tử là các số nguyên lớn nhƣ bốn

byte hay tám byte sẽ tăng tốc tính toán trên DBV lên rất nhiều do hiện nay các

thế hệ máy tính hỗ trợ 64 bit là phổ biến. Tuy nhiên, khó khăn khi sử dụng

các số nguyên lớn là việc xác định tidset csủa các tập mục để tính các giá trị

twu, wus trong khai thác FWUI trên CSDL số lƣợng và tw, ws trong khai thác

FWI trên CSDL trọng số.

1.6. Kết luận chƣơng

Có thể nói, khai thác FI là một khâu rất quan trọng trong khai thác dữ

liệu, phục vụ cho việc khai thác luật kết hợp và các yêu cầu khác nhằm chỉ ra

mối quan hệ, quy luật giữa các mục trong CSDL. Vì vậy, bài toán này đã thu

hút đƣợc nhiều nhóm nghiên cứu trên thế giới quan tâm nghiên cứu. Từ thuật

toán Apriori với nhiều lần quét CSDL, đến thuật toán FP-Growth với chỉ hai

lần quét CSDL và duyệt cây FP-tree. Tiếp đến Zaki với tiếp cận theo dữ liệu

dọc đã đề xuất khai thác FI với chỉ một lần quét CSDL.

Bên cạnh CSDL nhị phân, khai thác tập mục phổ biến trên CSDL số

32

lƣợng cũng đã nhận đƣợc nhiều quan tâm từ các nhóm nghiên cứu về khai

thác dữ liệu trên thế giới. Trong đó, khai thác FWI với hai độ đo tw và ws trên

CSDL trọng số là một trƣờng hợp riêng của CSDL số lƣợng đƣợc quan tâm từ

rất sớm với việc áp dụng các thuật toán Apriori, FP-Growth hay Eclat. Cùng

với đó là khai thác FWUI với độ đo twu của các giao dịch và wus của các tập

mục đƣợc biết đến lần đầu tiên với nghiên cứu của Khan và đồng sự. Phƣơng

pháp khai thác FWI và FWUI từ CSDL số lƣợng tốt nhất đến hiện nay là

phƣơng pháp tiếp cận quét CSDL một lần sử dụng cấu trúc MWIT-tree [40].

Tuy nhiên, nhƣ đã phân tích ở trên, các cấu trúc dữ liệu hiện tại sử dụng trong

các thuật toán còn nhiều hạn chế. Do đó, cần phát triển các cấu trúc mới để

cải thiện về bộ nhớ và thời gian khai thác của các thuật toán hiện tại.

CSDL có sự phân cấp các mục là CSDL có mặt nhiều trong các ứng

dụng thực tế. Do đó, thời gian gần đây khai thác FI trên loại CSDL này đã

nhận đƣợc nhiều quan tâm nghiên cứu. Từ việc khai thác cùng một ngƣỡng hỗ

trợ, tiếp đến là khai thác trên nhiều ngƣỡng hỗ trợ, mỗi mục có một ngƣỡng

hỗ trợ riêng và qua đó xây dựng các công thức xác định độ hỗ trợ tối thiểu

cho các tập mục. Tuy nhiên, các nghiên cứu hiện tại còn có nhiều hạn chế,

thời gian và bộ nhớ sử dụng còn lớn, nhiều tồn tại cần đƣợc nghiên cứu khắc

phục để có thể khai thác hiệu quả hơn trên loại CSDL này. Một trong số đó là

việc thêm các mục nút cha trên các cây phân cấp vào các giao dịch có chứa

các mục con của nó trong CSDL là một hạn chế lớn, có thể sẽ gây ra sự bùng

nổ về dung lƣợng CSDL, nhất là trên các CSDL có nhiều cây phân cấp hay

các cây phân cấp có độ cao lớn. Đây là các điểm hạn chế cần đƣợc cải tiến để

giảm thời gian khai thác và dung lƣợng bộ nhớ sử dụng.

CSDL số lƣợng có sự phân cấp các mục là loại CSDL có sự khác biệt

nhiều so với các CSDL hiện có, đây là sự kết hợp giữa CSDL số lƣợng và

CSDL có sự phân cấp các mục. Do đó việc khai thác cần có các phƣơng pháp

riêng biệt, đặc thù. Tuy nhiên, hiện nay nghiên cứu khai thác tập mục trên

33

CSDL số lƣợng có sự phân cấp các mục chƣa đƣợc quan tâm. Do vậy, bài

toán khai thác tập mục trên CSDL số lƣợng có sự phân cấp các mục cần đƣợc

đặt ra nghiên cứu. Đề xuất thuật toán khai thác hiệu quả trên CSDL số lƣợng

có sự phân cấp các mục có thể đƣợc áp dụng vào khai thác hiệu quả trên

CSDL số lƣợng và CSDL có sự phân cấp, khắc phục những hạn chế hiện tại

của các thuật toán khai thác tập mục phổ biến trên hai loại CSDL này nhƣ đã

34

phân tích ở trên là các mục tiêu của luận án.

CHƢƠNG 2. KHAI THÁC TẬP MỤC PHỔ BIẾN

TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG

Tiếp cận bit-vector trong biểu diễn tidset của các tập mục là một hƣớng

phát triển hiệu quả, do tận dụng đƣợc tốc độ tính toán của các phép toán trên

bit, đồng thời tiết kiệm đƣợc bộ nhớ lƣu trữ tidset do mỗi giao dịch chỉ cần

đánh dấu bởi một bit. Do đó, trong nhiều nghiên cứu liên quan đến biểu diễn

chuỗi các phần tử có tính liên tục ngƣời ta thƣờng sử dụng phƣơng pháp bit-

vector. Đối với khai thác tập mục phổ biến ngƣời ta đã sửa dụng phƣơng

pháp bit-vector từ khá sớm, tuy nhiên việc sử dụng phƣơng pháp này khá

nguyên thủy [13, 31] hoặc chƣa đƣợc cải tiến triệt để nhƣ DBV [38] để có

thể loại bỏ các bộ nhớ thừa nhằm tối ƣu bộ nhớ cũng nhƣ tăng tốc độ tính

toán tốt hơn .

Trong chƣơng này, luận án trình bày một số cải tiến theo hƣớng tiếp cận

này với việc đề xuất hai cấu trúc dữ liệu IWS và MBiS sử dụng trong thuật

toán khai thác tập phổ biến. Cấu trúc IWS là một cải tiến của cấu trúc DBV

[38] bằng việc loại bỏ tất các các đoạn hai byte (word) liên tiếp có giá trị bằng

0 trên bit-vector giúp giảm bộ nhớ lƣu trữ tidset của các tập mục. Đồng thời

luận án đề xuất một mảng MAP khai báo trƣớc vị trí các bit 1 trong các số

nguyên hai byte để giúp tính nhanh độ phổ biến ws của các tập mục. Cấu trúc

MBiS [I] là một đề xuất khác theo hƣớng tiếp cận bit-vector, MBiS chỉ lƣu

các đoạn bit 1 liên tiếp trên bit-vector. Cấu trúc này cho phép việc xác định

nhanh hợp của các tập mục thông qua xác định giao của các MBiS của chúng,

do chỉ cần cập nhật lại các vị trí đầu đoạn và cuối đoạn mới bằng các phép

toán lấy MAX và MIN của hai đầu đoạn và cuối đoạn trƣớc đó.

Các phân tích về mặt lý thuyết và kết quả thực nghiệm cho thấy sự hiệu

quả của các cấu trúc mới này trong việc tiết kiệm bộ nhớ và giảm thời gian

35

khai thác trên các CSDL thƣa và CSDL trung bình.

Đồng thời, chƣơng 2 cũng trình bày về một đề xuất hiệu quả cho bài toán

khai thác hiệu quả FWUIk trên CSDL số lƣợng với hai cấu trúc DTab và

DHeap. Các kết quả thực nghiệm cho thấy các cấu trúc mới đề xuất này có

hiệu quả hơn các cấu trúc đã có.

2.1. Thuật toán khai thác tập FWI

Phần này luận án trình bày về cấu trúc Interval word segment - IWS là

một cải tiến của BDV, đã đƣợc công bố tại hội thảo quốc tế SMC 2015 [II],

sau đó đƣợc phát triển mở rộng, thử nghiệm trên nhiều bộ dữ liệu hơn và công

bố tại [V].

2.1.1. Giới thiệu

Định nghĩa 2.1. Interval word segment (IWS) của một tập mục X thuộc

CSDL DB là một cấu trúc gồm nhiều đoạn, trong đó mỗi đoạn là các word

(hai byte) liên tiếp khác 0 trên bit-vector biểu diễn tidset của tập mục X.

Mỗi đoạn gồm hai thành phần:

Start: Vị trí word đầu tiên của đoạn trên bit-vector.

Word list: Danh sách giá trị các word liên tiếp khác 0.

Ví dụ 2.1: Cho tập mục X của CSDL DB biểu diễn bởi một bit-vector

đƣợc cho dƣới dạng các byte nhƣ bảng 2.1

Chỉ số byte 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Giá trị

0 0 0 0 6 9 0 0 0 1 5 1 4 6 0 0 0 0 0 0 0 0 0 1 5 4 6 0 0 0 0 0

Bảng 2.1. Bit-vector

Bit-vector trong Bảng 2.1 (còn đƣợc gọi là BitTable) gồm 21 byte có giá

trị bằng 0, bit-vector trên đƣợc biểu diễn qua cấu trúc DBV [43] trong Bảng

2.2 nhƣ sau:

Chỉ số byte 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Giá trị

6 9 0 0 0 1 5 1 4 6 0 0 0 0 0 0 0 0 0 1 5 4 6

DBV

5(6, 9, 0, 0, 0, 1, 5, 1, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 4, 6)

36

Bảng 2.2. DBV của bit-vector trong ví dụ 2.1

DBV loại bỏ các byte có giá trị bằng 0 ở đầu và cuối của bit-vector, do

đó trong nhiều trƣờng hợp DBV tiết kiệm bộ nhớ khá tốt, nhờ vậy tăng tốc độ

tính toán trong khai thác FI. Tuy nhiên trong cấu trúc DBV vẫn còn tồn tại

các byte bằng 0, nhất là trên các CSDL thƣa thì số byte bằng 0 càng nhiều. Do

đó cấu trúc DBV vẫn chƣa tối ƣu đƣợc bộ nhớ.

Cấu trúc IWS đƣợc đề xuất trong [II, V] là một mở rộng của MByS, với

mỗi phần tử là một word (hai byte). IWS loại bỏ hoàn toàn các word có giá trị

bằng 0 khỏi DBV, bằng cách này đã giải quyết đƣợc hạn chế về lãng phí bộ

nhớ của DBV.

Bảng 2.3. IWS từ bit-vector trong ví dụ 2.1

Chỉ số word 3 5 6 7 12 13 14

Giá trị các byte 6 9 0 1 5 1 4 6 0 1 5 4 6 0

Giá trị các word 1545 1 1281 1030 1 1284 1536

{3(1545), 5(1, 1281, 1030), 12(1, 1284, 1536)}

IWS

IWS đƣợc biểu diễn nhƣ trong Bảng 2.3 có ba đoạn, đoạn thứ nhất từ

word có chỉ số là 3, giá trị là 1545. Đoạn thứ hai bắt đầu từ word chỉ số là 5

với ba phần tử là 1, 1281 và 1030, v.v… Nhƣ vậy, cấu trúc IWS đã loại bỏ

hoàn toàn các word bằng 0, chỉ lƣu giữ các đoạn word liên tiếp có giá trị

khác 0.

Mệnh đề 2.1. Đoạn Sx =  ( ) đƣợc gọi là đoạn con

của đoạn Sy =  ( ) nếu thỏa mãn ba điều kiện sau:

1.

2. 3. Chứng minh: Từ = , = , …, = , Sx

thay bằng Sx =  ( ) Sy. Do đó, Sx đƣợc gọi là

37

đoạn con của Sy.

Ví dụ 2.2: Sx = 6(1281, 1030) với sx = 6 là một đoạn con của Sy = 5(1,

1281, 1030) với sy =5. Bởi vì, với t = 1 ta có:

1.

2. 7 7 ⟹

3. = = 1281, = = 1030

Mệnh đề 2.2. chỉ nếu   IWS(X) nếu và

  là đoạn con của một đoạn thuộc IWS(X).

Ví dụ 2.3: Cho IWS(X) = {3(1545), 5(1, 1281, 1030), 12(1, 1284,

1536)}. Đoạn 6(1281, 1030) IWS(X) bởi vì 6(1281, 1030) là đoạn con

của đoạn 5(1, 1281, 1030) thuộc IWS(X) theo ví dụ 2.2.

Định nghĩa 2.2. Giao giữa hai đoạn Sx =   và Sy =

  là đoạn Sz, kí hiệu là Sz = Sx Sy,

Với:

sz = max(sx, sy)

Sz =  ( ), với: = & ; = & ; …; =

.

m = min(k+sx, l+sy)

Trong đó “&” là phép AND trên bit.

Ví dụ 2.4: Cho hai đoạn =5(1, 1281, 1030), k = 2 và = 6(3220,

8726, 3104), l = 2. Ta có:

= max(5, 6) = 6;

m = min((5+2), (6+2)) = 7;

⟹ = 6  với:

= & = 1281 & 3220 = 1024

= & = 1030 & 8726= 6

38

Do đó, giao của và là =6(1024, 6).

Định nghĩa 2.3. Giao của IWS(X) và IWS(Y) đƣợc định nghĩa là

IWS(X Y) = IWS(X) IWS(Y). IWS(X Y) chứa các đoạn, mỗi đoạn là giao

của các đoạn trên IWS(X) và IWS(Y) theo Định nghĩa 2.2.

Ví dụ 2.5:

IWS(X) = {3(1545), 5(1, 1281, 1030), 12(1, 1284, 1536)}

IWS(Y) = {6(3220, 8726, 3104), 10(1242, 8721, 6527,6)}

⟹ IWS(X Y) = {6(1024, 6), 12(1, 4)} 1281

Mệnh đề 2.1. Cho đoạn Si = si( , … ) IWS(X), l là chỉ số

bit 1 của (từ trái sang phải) với si sj ei. l đƣợc ánh xạ lên bit-vector

theo công thức 2.1:

(2.1) k = (sj - 1) 16 + l

Với, k chỉ số bit 1 trên bit-vector của bit có chỉ số l của asj.

Chứng minh: sj là chỉ số của trên word-vector. Nhƣ vậy có (sj - 1)

word trƣớc . Điều này có nghĩa là có [(sj - 1) 16] bit trƣớc trên bit-

vector (mỗi word có 16 bit). Do đó, bit có vị trí l trong word thứ sj đƣợc ánh

xạ lên bit-vector với vị trí k theo công thức:

k = (sj - 1) 16 + l.

Ví dụ 2.6: Cho IWS(X) = {3(1545)}, chỉ số các bit 1 của X đƣợc xác

định nhƣ trong Bảng 2.4:

Chỉ số bit 1 trên word

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Giá trị các bit

0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1

Giá trị word

1545

Chỉ số bit 1 trong word

{6,7,13,16}

Bảng 2.4. Chỉ số các bit 1 của IWS(X)

Ta thấy IWS(X) chỉ có một đoạn với một phần tử, do vậy start của

IWS(X) = 3, nên có (3 - 1) ×16 = 32 bit trƣớc IWS(X). Dựa trên công thức 2.1

39

và Bảng 2.4 ta có chỉ số các bit 1 của IWS(X) trên bit-vector lần lƣợt là:

32 + 6 = 38;

32 + 7 = 39;

32 + 13 = 45;

32 + 16 = 48;

Do đó, tidset(X) = {38, 39, 45, 48}

Định nghĩa 2.4. Cho tập mục X của CSDL DB, các chỉ số bit 1 trong

IWS(X) là các giao dịch trong CSDL DB, công thức 1.2 đƣợc định nghĩa lại

∑

nhƣ công thức 2.2:

(2.2) ws(X)

Với, Sum_tw = ∑ với m là số lƣợng các giao dịch trong

CSDL DB.

2.1.2. Thuật toán tính giao của hai IWS

Khai thác FWI với định dạng dữ liệu dọc theo tiếp cận Eclat [5] đòi hỏi

phải tính giao các tidset để xác định tập mục mới đƣợc tạo thành từ hai tập

mục cũ. Điều này đồng nghĩa với việc tính giao của hai IWS của hai tập mục

tƣơng ứng theo Định nghĩa 2.3.

Thuật toán 2.1: INTERSECTION_IWS

Input:

- IWS(X) gồmn1 đoạn, đoạn thứ I có start là IWS(X) [i].start

- IWS(Y) gồmm1đoạn, đoạn thứjcóstart là IWS(Y) [j].start

Output: Z = IWS(X) IWS(Y)

Method name: INTERSECTION_IWS()

40

Thuật toán xác định giao của hai IWS đƣợc trình bày nhƣ Hình 2.1

INTERSECTION_IWS (IWS(X), IWS(Y))

1

i = 1; j = 1; Z = ;

2

while (i n1 and j m1)

3

Đoạn i1 của IWS(X và đoạn j1 của IWS(Y là các đoạn giao đầu tiên

của IWS(X) và IWS(Y) tính từ đoạn i (IWS(X và đoạn j (IWS(Y))

4

S = ;

5

Start = max(IWS(X) [i1].start, IWS(Y) [j1].start);

6

End = min(IWS(X) [i1].end, IWS(Y) [j1].end);

7

for all k [Start, End] do

8

S = S IWS(X) [k] IWS(Y) [k]};

9

Loại bỏ các Word = 0 trong S và thêm S vào Z

10

if (End = IWS(X) [i1].end) then

11

i = i1 1;

12

j = j1;

13

if (End = IWS(Y) [i1].end) then

14

j = j1 1;

15

i = i1;

16

Return Z

Hình 2.1. Thuật toán xác định giao hai IWS

Đầu vào của thuật toán là IWS(X) và IWS(Y). Trong đó, IWS(X) có n1

đoạn. IWS(Y) có m1 đoạn. Đầu ra là Z là một IWS. Dòng 4, xác định đoạn giao

tiếp theo của IWS(X) và IWS(Y). Dòng 5 và 6, tính đầu và cuối đoạn giao kết

quả. Dòng 7 đến 9, tính S là đoạn giao kết quả. Dòng 10, loại các word có giá

trị bằng 0 khỏi S (có thể tạo ra nhiều đoạn mới). Dòng 10 đến dòng 15, xác

định đoạn giao tiếp theo trên IWS(X) và IWS(Y).

Dễ nhận thấy độ phức tạp thuật toán là O(n1 + m1), với n1 và m1 lần lƣợt

là số lƣợng các đoạn của IWS(X) và IWS(Y). Do đó, thời gian thực hiện thuật

41

toán INTERSECTION_IWS phụ thuộc vào số đoạn của mỗi IWS.

2.1.3. Thuật toán khai thác FWI

a. Cấu trúc IWS-tree

Từ cấu trúc IWS luận án đề xuất cấu trúc IWS-tree để khai thác FWI

theo dữ liệu dọc. Mỗi nút của IWS-tree gồm ba thành phần:

- X là một tập mục,

- IWS(X) là IWS của X,

- ws(X) là giá trị ws của X.

Các nút của IWS-tree ở mức thứ nhất là các 1-itemset, từ mức thứ hai,

các nút ở mức dƣới đƣợc tạo thành từ sự kết hợp của hai nút ở mức trên với

các điều kiện sau:

- Hai nút cùng số lƣợng phần tử và chỉ khác nhau phần tử cuối cùng.

- wus của tập mục tạo thành thỏa mãn ngƣỡng minwus do ngƣời sử

dụng đƣa vào.

b. Thuật toán tính nhanh wus dựa trên IWS

Khai thác FWI trên CSDL trọng số là phải xác định ws của các tập mục

theo công thức 2.2. Do đó cần xác định vị trí các bit 1 của IWS của các tập

mục, điều này đồng nghĩa với việc xác định tidset của các tập mục. Để giải

quyết hiệu quả vấn đề này, luận án đề xuất sử dụng một mảng MAP gồm

65.535 phần tử nhƣ trong Bảng 2.5. Phần tử thứ i của mảng MAP chứa một

danh sách các bit 1 trong biểu diễn nhị phân của i. Dựa trên mảng MAP ta có

thể tính đƣợc vị trí các bit 1 của IWS trên bit-vector.

Chỉ số mảng

2

…

65.534

65.535

1

Giá trị nhị phân 0000000000000001 0000000000000010 … 1111111111111110 1111111111111111

MAP

15

… 1, 2, …, 14, 15 1, 2, …, 15, 16

16

Bảng 2.5. Mảng MAP

Thuật toán tính ws của tập mục X đƣợc trình bày trong Hình 2.2. Bƣớc thứ

nhất tidset của các tập mục đƣợc xây dựng theo Mệnh đề 2.1 dựa trên công

42

thức 2.1 và mảng MAP. Bƣớc thứ 2 tính ws theo công thức 2.2.

Thuật toán 2.2: CALCULATION_WS

Input: IWS(X)

- Output: ws của tập mục X

- Method name: CALCULATION_WS()

CALCULATION_WS(IWS(X))

tidset(X) = ;

1

2

for all i IWS(X) do

3

for all j MAP [i] do

4

tidset(X) (si - 1) 16 j;

5

y = 0;

6

for all i tidset(X) do

7

y = y + tw( );

8

ws = y/sum_tw;

9

return ws

Hình 2.2. Thuật toán tính ws của tập mục X

Đầu vào của thuật toán là IWS của tập mục X, đầu ra là ws(X). Dòng 1

đến dòng 4, xây dựng tidset của X dựa trên công thức 2.1 và mảng MAP.

Dòng 5 đến dòng 8, tính ws(X) theo công thức 2.2. Cuối cùng, dòng 9 trả về

giá trị ws của X.

Với mảng MAP việc tính toán ws là khá đơn giản và tiết kiệm thời gian

tính toán. Vì chỉ cần O(1) để xác định vị trí một bit 1 trên bit-vector.

Do đó, độ phức tạp thuật toán là O(k) với k là số các giao dịch của tập

mục X.

c. Thuật toán

Luận án đề xuất thuật toán IWS-FWI [II, IV]khai thác FWI trên CSDL

trọng số dựa trên cấu trúc IWS-tree với lƣợng tiếp cận dữ liệu dọc. IWS-tree

43

đƣợc tạo ra nhƣ sau:

Trƣớc hết, mức thứ nhất của cây bao gồm các nút chứa các 1-itemset có

độ đo ws thỏa ngƣỡng minws. Tất cả các nút ở mức thứ nhất cùng thuộc một

lớp tƣơng đƣơng. Mỗi nút khi kết nối với lần lƣợt từng nút phía sau nó trong

cùng một lớp tƣơng đƣơng tạo ra các nút cùng một lớp tƣơng đƣơng ở mức

dƣới. Hai nút chứa hai tập mục X1X2…XkY1 và X1X2…XkY2 thuộc cùng một

lớp tƣơng đƣơng kết nối với nhau (các tập mục thuộc các nút trong cùng một

- Tạo ra nút mới X1X2…XkY1Y2

- ws(X1X2…XkY1Y2) minws

lớp tƣơng đƣơng có cùng độ dài và khác nhau phần tử cuối cùng):

Nhƣ vậy các k-itemset đƣợc tạo thành từ các (k-1)-itemset ở cùng một

lớp tƣơng đƣơng ở mức trên với điều kiện tập mục mới tạo thành thỏa mãn

ngƣỡng minws do ngƣời sử dụng đƣa vào. Do đó, các tập mục trên các nút

của IWS-tree chính là các FWI cần khai thác.

Thuật toán 2.3: CREATE_IWS-tree

Input: tậpP (tập 1-itemset) và minws;

Output: Tập P chứa tất cả FWI của CSDL DB với ngưỡng minws

Method name: CREATE_IWS_Tree()

CREATE_IWS_Tree(P)

1

IWS-tree = 

2

for all li P] do

3

[Pi] = ;

4

for all lj [P], (vớij i) do

5

X = li lj;

6

Y = INTERSECTION_IWS(IWS(li), IWS(lj));

7

ws_X= CALCULATION_WS(Y);//ws của tập mục X

8

if (ws_X minws) then

44

Thuật toán đệ quy tạo IWS-tree đƣợc trình bày nhƣ Hình 2.3.

9

[Pi] = [Pi] {(X, Y, ws_X};

10

IWS-tree = IWS-tree Pi;

11

CREATE_IWS_Tree( [Pi])

Hình 2.3. Thuật toán xây dựng IWS-tree

Đầu vào của thuật toán là lớp tƣơng đƣơng P (chứa các tập mục có cùng

độ dài chỉ khác nhau phần tử cuối và thỏa mãn minws). Dòng 1 đến dòng 4,

với mỗi tập mục li kết nối với tất cả các tập mục lj đứng phía sau li thuộc cùng

lớp tƣơng đƣơng P tạo ra X là tập mục mới. Dòng 6 tính Y = IWS(X) theo

thuật toán INTERSECTION_IWS trong Hình 2.1. Dòng 7, tính ws(Y) là ws

của tập mục X. Nếu ws(X) thỏa ngƣỡng minws thêm {X, Y, ws_X} vào Pi tại

dòng 9. Sau khi xây dựng xong lớp tƣơng đƣơng Pi, Pi đƣợc thêm vào IWS-

tree tại dòng 10. Cuối cùng gọi đệ quy với lớp tƣơng đƣơng mới Pi sau khi kết

nối li với tất cả các lj sau nó ở dòng 11.

Thuật toán IWS_FWI khai thác FWIs trên CSDL trọng số đƣợc trình bày

Thuật toán 2.4: IWS_FWIs

Input: CSDL DB và minws;

Output: IWS-tree chứa các FWI của DB theo ngưỡng minws

Method name: IWS_FWIs()

IWS_FWIs(minws)

P = ;

1

2

for all i I do

3

if (CALCULATION_WS(i) minws) then

4

P = P {i};

5

CREATE_IWS_TREE(P);

trong Hình 2.4

Hình 2.4. Thuật toán khai thác FWI dựa trên IWS-tree

Đầu vào thuật toán là CSDL trọng số D và minws. Dòng 1, P đƣợc gán

bằng . Từ dòng 2 đến dòng 4, P bằng tập 1-itemset thỏa mãn minws. Dòng

45

5, gọi hàm IWS-tree để tạo cây IWS-tree theo thuật toán 3 ở Hình 2.3.

Sau đây là một ví dụ khai thác FWI trên CSDL trọng số theo thuật toán

IWS_FWI.

Ví dụ 2.7: Khai thác FWI trên CSDL DB trong ví dụ 1.3 với minws =

0,4. IWS và ws của các mục đƣợc xác định nhƣ trong Bảng 2.6.

Bảng 2.6. IWS của các mục

mục Tidset BitTable IWS ws

0,72 1, 3, 4, 5 A {1(29)} 000111012

1,00 1, 2, 3, 4, 5, 6 B {1(63)} 001111112

0,60 2, 4, 5, 6 C {1(58)} 001110102

0,78 1, 3, 5, 6 D {1(53)} 001101012

0,81 E 1, 2, 3, 4, 5 {1(31} 000111112

Trong ví dụ này, mỗi IWS chỉ có một đoạn với một phần tử duy nhất.

Các giá trị ws của mục thỏa mãn minws. Do vậy, P = {A, B, C, D, E} và A, B,

C, D, E đƣợc thêm vào IWS-tree. Thuật toán đệ quy IWS_tree() đƣợc thực

hiện nhƣ sau:

[]

𝐴 }

𝐶 }

𝐵 }

𝐷 }

𝐸 }

𝐴𝐴𝐵 }

𝐴𝐸 }

𝐴𝐷 }

𝐴𝐷𝐸 }

𝐴𝐵𝐸 }

𝐴𝐵𝐶 }

𝐴𝐵𝐷 }

𝐴𝐵𝐷𝐸 }

 Với nút A:

46

Hình 2.5. IWS-tree với nút A (minws = 0,4)

Kết nối hai nút A và B. Ta có, IWS(A) IWS(B) = {1(29)}

{1(63)}, do đó IWS(AB) = {1(29)}. Dựa trên thuật toán 2.2, ta có ws(AB)

= ws(A) = 0,72 minws, nên AB đƣợc thêm vào IWS-tree.

Tiếp theo, kết nối A và C. IWS(A) IWS(C) = {1(29)} {1(58)}, nên

IWS(AC) = {1(24)}. Do ws(AC) = 0,32 minws, nên AC không đƣợc thêm

vào IWS-tree.

Tƣơng tự nhƣ trên, các tập mục {AD, AE, ABC, ABD, ABE, ABDE}

đƣợc thêm vào IWS-tree nhƣ trong Hình 2.5.

[]

𝐵 }

𝐴 }

𝐵𝐶 }

𝐵𝐸 }

𝐴𝐴𝐵 }

𝐴𝐸 }

𝐴𝐷 }

𝐵𝐷 }

𝐵𝐷𝐸 }

𝐴𝐵𝐷 }

𝐴𝐵𝐸 }

𝐴𝐷𝐸 }

𝐴𝐵𝐶 }

𝐴𝐵𝐷𝐸 }

 Với nút B:

Hình 2.6. IWS-tree với nút A và B (minws = 0,4)

Kết nối hai nút B và C. Ta có, IWS(B) IWS(C) = {1(63)}

{1(58)}, nên IWS(BC) = {1(29)}. Do ws(BC) = 0,72 minws, nên BC

đƣợc chèn vào IWS-tree.

Tiếp theo, kết nối B và D. Ta có, IWS(B) IWS(D) = {1(63)}

{1(53)}, nên IWS(BD) = {1(53)}. Do, ws(BD) = 0,78 minws, nên BD

đƣợc thêm vào IWS-tree.

Tƣơng tự, các tập mục {BE, BDE} đƣợc thêm vào IWS-tree nhƣ trong

Hình 2.6.

Sau khi xét tƣơng tự với các nút C, D và E còn lại, IWS-tree đầy đủ

47

đƣợc thể hiện nhƣ trong Hình 2.7.

Nhƣ vậy, với minws = 0,4 ta có tập các FWI theo: {A, B, C, D, E, AB,

𝐵 }

𝐴 }

𝐶 }

𝐷 }

𝐸 }

59

𝐴𝐴𝐵 }

𝐴𝐸 }

𝐵𝐶 }

𝐴𝐷 }

𝐵𝐷 }

𝐷𝐾 }

𝐵𝐸 }

𝐷𝐸 2 }

𝐶𝐸 }

𝐵𝐷𝐸 }

𝐴𝐵𝐶 }

𝐴𝐵𝐷 }

𝐴𝐷𝐸 }

𝐴𝐵𝐸 }

𝐴𝐵𝐷𝐸 }

AD, AE, BC, BD, BE, DE, ABD, ABE, ADE, BDE, ABDE}.

Hình 2.7. IWS-tree với minws = 0,4

2.1.4. Kết quả thực nghiệm

2.1.4.1. Môi trường thực nghiệm

Hệ thống thử nghiệm đƣợc cài đặt bằng C# 2014 trên Microsoft

Windows 8.1 Pro 64 bit, Net Framework 4.5,với CPU Intel® Haswell Core™

i5 - 1.4 GHz, Ram 4Gb. Hệ thống phần mềm đƣợc sử dụng: Visual Studio

2013 Ultimate.

2.1.4.2. CSDL thực nghiệm

CSDL thực nghiệm gồm BMS-POS, RETAIL, ACCIDENTS,

CONNECT, CHESS đƣợc lấy từ http: //fimi.cs.helsinki.fi/data/ và SALE-

FACT-1997, SALE-FACT-1997+1998, SALE-SYNC đƣợc lấy từ CSDL

FOODMART2000 của Microsoft SQL server, trong đó SALE-FACT-

1997+1998 đƣợc tổng hợp từ bản SALE-FACT-1997 và SALE-FACT-1998,

còn SALE-FACT-SYNC đƣợc kết hợp từ SALE-FACT-1997, SALE-FACT-

48

1998 và SALE-FACT-DEC_1998.

Các CSDL thử nghiệm đƣợc mô tả cụ thể trong Bảng 2.7 nhƣ sau:

Số lƣợng mục Số lƣợng giao dịch

Ghi chú

Stt CSDL

Bảng 2.7. Mô tả CSDL thực nghiệm

16.470 88.162 Thêm trọng số 1. RETAIL

2. BMS-POS 1.657 515.597 Thêm trọng số

3. SALE-FACT-1997 1.753 20.522

4. SALE-FACT-1997+1998 1.753 54.537

5. SALE-FACT-SYNC 1.753 58.308

6. CONNECT 468 340.183 Thêm trọng số

7. ACCIDENTS 130 67.557 Thêm trọng số

Các CSDL 1, 2, 6, 7 nguyên gốc đƣợc thêm vào một bảng mới với các

giá trị ngẫu nhiên trong khoảng từ 1 đến 10 làm giá trị trọng số của các mục.

Phần này trình bày biểu đồ thời gian thực thi và bộ nhớ sử dụng của ba

phƣơng pháp DBV, DIFFSET và IWS trên các CSDL thực nghiệm.

2.1.4.1. Kết quả thực nghiệm

150

139,571

100

DBV DIFFSET IWS

64,141

a. So sánh thời gian thực thi

) s ( e m

050

i t

27,69

000

001

001

000

000

000

000

minws(%)

300

232,209

200

DBV IWS DIFFSET

100

Hình 2.8. So sánh thời gian chạy với CSDL RETAIL.

) s ( e m

i t

125,091 61,511

0

0.6

0.5

0.4

0.3

0.2

0.1

minws(%)

49

Hình 2.9. So sánh thời gian chạy với CSDL BMS-POS.

400

309,301

300

200

DBV IWS DIFFSET

) s ( e m

i t

100

98,594 68,836

0

0.3

0.2

0.03

0.01

0.06

0.1 minws(%)

2501,68

DBV

IWS

Hình 2.10. So sánh thời gian chạy với CSDL SALE-FACT-1997.

) s ( e m

DIFFSET

i t

563,70

250,34

3000 2500 2000 1500 1000 500 0

0.3

0.2

0.1

0.06

0.03

0.01

minws(%)

3000

2748,776

2000

DBV IWS DIFFSET

1000

640,854

Hình 2.11. So sánh thời gian chạy với CSDL SALE-FACT-1997+1998.

) s ( e m

i t

322,957

0

0.3

0.2

0.1

0.06

0.03

0.01

minws(%)

60

48,812 41,935

40

DBV IWS DIFFSET

Hình 2.12. So sánh thời gian chạy với CSDLSALE-FACT-SYNC.

) s ( e m

20

i t

6,094

0

0.96

0.95

0.94

0.93

0.92

0.9

minws

50

Hình 2.13. So sánh thời gian chạy với CSDLCONNECT.

250

212,667

200

150

DBV IWS DIFFSET

) s ( e m

112,667

i t

100

50

30,742

0

0.9

0.8

0.7

0.6

0.5

minws

Hình 2.14. So sánh thời gian chạy với CSDL ACCIDENTS.

160,687

150

100

DBV IWS DIFFSET

50

48,479 24,002

b. So sánh bộ nhớ sử dụng 200

) b M ( y r o m e m

0

0.6

0.5

0.3

0.2

0.1

0.4 minws(%)

600

431.725

400

DBV IWS DIFFSET

200

213.67 103.038

Hình 2.15. So sánh bộ nhớ sử dụng với CSDL RETAIL.

) b M ( y r o m e m

0

0.6

0.5

0.3

0.2

0.1

0.4 minws(%)

800

DBV

600

IWS

622,14 542,7 509,81

400

DIFFSET

200

Hình 2.16. So sánh bộ nhớ sử dụng với CSDL BMS-POS.

) b M ( y r o m e m

0

0.03

0.02

0.1

0.06

0.03

0.01

minws(%)

51

Hình 2.17. So sánh bộ nhớ sử dụng với CSDLSALE-FACT-1997.

2000

DBV

1500

IWS

1477,976 1344,846 1284,567

1000

DIFFSET

500

0

) b M ( y r o m e m

0.3

0.2

0.1

0.06

0.03

0.01

minws(%)

2000

DBV

1500

IWS

1543,975 1482,239 1400,239

1000

DIFFSET

500

0

Hình 2.18. So sánh bộ nhớ sử dụng với CSDLSALE-FACT-1997+1998.

) b M ( y r o m e m

0.6

0.5

0.2

0.1

0.4

0.3 minws(%)

60

DBV

48,81 41,935

40

IWS

DIFFSET

20

6,094

0

Hình 2.19. So sánh bộ nhớ sử dụng với CSDLSALE-FACT-SYNC.

) b M ( y r o m e m

0.96

0.95

0.94

0.93

0.92

0.9

minws

150

112,667

100

78,172

DBV IWS DIFFSET

50

30,742

Hình 2.20. So sánh bộ nhớ sử dụng với CSDLCONNECT.

) b M ( y r o m e m

0

0.9

0.8

0.6

0.5

0.7 minws

52

Hình 2.21. So sánh bộ nhớ sử dụng với CSDL ACCIDENT.

Các kết quả thử nghiệm cho thấy hiệu quả của IWS trên các CSDL thƣa

(RETAIL, MBS-POS) và các CSDL trung bình (các CSDL SALE_FACT),

còn trên các CSDL dày (CONNECT, ACCIDENT) thì DIFFSET có hiệu quả

rõ rệt, do với các CSDL dày thì tidset của các tập mục lớn, nên diffset sẽ nhỏ

(do diffset lấy phần bù). Ví dụ, với CSDL RETAIL thì IWS là 27,69s còn

Diffset là 67,141s đối với độ phổ biến minws = 0,1%. Còn với dữ liệu

ACCIDENT thì MBiS là 112,667s còn Diffset là 30,742s đối với độ phổ biến

minws = 0,5.

Đối với các CSDL thƣa và trung bình, số lƣợng các mục xuất hiện trên

các giao dịch ít, do đó khi biểu diễn bằng phƣơng pháp bit-vector có loại bỏ

các đoạn 2 byte có giá trị bằng 0 sẽ tiết kiệm đƣợc nhiều bộ nhớ. Đồng thời

với việc chỉ cần ít bộ nhớ trong biểu diễn tidset bằng IWS thì việc tính toán

trên IWS cũng sẽ nhanh hơn, do các việc tính giao các IWS phụ thuộc vào số

đoạn word của chính nó. Nên thời gian khai thác khi sử dụng IWS là nhỏ so

với DBV hay DIFFSET trên CSDL thƣa. Tƣơng tự nhƣ thế IWS cũng có hiệu

quả tốt hơn đối với CSDL có mức độ trung bình.

Đối với CSDL dày, số lƣợng các mục xuất hiện trên giao dịch khá lớn

(dày đặc). Do đó khi biểu diễn tidset bằng phƣơng pháp bit-vector chỉ loại

đƣợc ít các đoạn hai byte bằng 0 liên tiếp, đồng thời qua quan sát chạy thực

nghiệm thấy rằng IWS có sự phân mảnh khá lớn, nghĩa là IWS có rất nhiều

đoạn. Nhƣ vậy, việc phải sử dụng khá nhiều bộ nhớ để lƣu trữ tidset và IWS

có nhiều đoạn đã làm cho các tính toán trên IWS tốn nhiều thời gian, điều này

làm cho IWS không có hiệu quả trên CSDL dày. Các kết quả thực nghiệm

trên 2 CSDL dày CONNECT và ACCIDENT cho thấy nhận định trên là

53

chính xác.

2.2. Thuật toán khai thác FWUI

Phần này trình bày về cấu trúc dữ liệu Multi bit segment và áp dụng vào

bài toán khai thác FWUI. Đây là một tiếp cận khác theo hƣớng loại bỏ hoàn

toàn các bit 0 trên bit-vector, lƣu giữ lại các đầu đoạn và cuối đoạn của các

đoạn bit 1 liên tục. Nội dung này đã đƣợc công bố tại công trình [I].

2.2.1. Cấu trúc Multi bit segment

Định nghĩa 2.5. Multi bit segment (MBiS) là một cấu trúc lƣu lại các

đoạn bit 1 liên tiếp từ bit-vector biểu diễn tidset của tập mục. Mỗi đoạn MBiS

gồm thành phần:

Start: Chỉ số bit 1 đầu đoạn

End: Chỉ số bit 1 cuối đoạn

Một ví dụ về MBiS nhƣ sau:

Chỉ số bit 1 2 … 15 16 17 … 35 36 37 … 58 59 60 … 80 81 82 … 96

Giá trị bit 0 0 0 0 1 1 … 1 0 0 … 0

1 1 … 1 0 0 … 0

Bảng 2.8. Bit-vector với 96 phần tử

Bảng 2.8 trình bày bit-vector gồm 96 phần tử (tƣơng ứng với 12 byte).

MBiS của bit-vector trên gồm hai đoạn tƣơng ứng nhƣ sau:

MBiS: [16,35], [59,80]

Cho MBiS(X) và MBiS(Y) là các MBiS củatập mục X và tập mục Y thuộc

CSDL DB. Ta có các định nghĩa sau:

Định nghĩa 2.6. MBiS của tập mục X bao gồm nhiều đoạn, mỗi đoạn là

các bit 1 liên tiếp trên bit-vector biểu diễn tidset của tập mục X:

MBiS(X) = { [ ], [ ], ..., [ ]},

Với ei si,i {1, 2,...,k} và i {2, 3, ...,k}.

Ví dụ 2.8: Trong Bảng 2.8, MBiS có hai đoạn là [16, 35] và [59, 80] nhƣ

54

trong Bảng 2.9.

Bảng 2.9. MBiS từ bit-vector ở Bảng 2.8

[16, 35] [59, 80]

Đoạn 1 Đoạn 2

Định nghĩa 2.7. Phần tử i đƣợc gọi là thuộc MBiS(X)(i MBiS(X)) nếu

và chỉ nếu tồn tại một đoạn [ , ] là một đoạn củaMBiS(X) sao cho i

.

Ví dụ 2.9: Với MBiS(X) = {[16, 35], [59, 80]}, ta nói rằng 30 thuộc

MBiS(X) bởi vì 16 30 35, mà [16, 35] là một đoạn thuộc MBiS(X).

Định nghĩa 2.8. Giao của MBiS(X) và MBiS(Y) đƣợc định nghĩa là

MBiS(X) MBiS(Y). Nếu i MBiS(X) MBiS(X), thìi MBiS(X) và i

MBiS(Y) và ngƣợc lại.

Ví dụ 2.10: Với MBiS(X) = { [5, 20], [35, 50]}và MBiS(Y) = {[15, 25],

[40, 60]}. MBiS(X) MBiS(Y) = { [15, 20], [40, 50]}.

Định nghĩa 2.9. Cho tập mục X của CSDL DB, các chỉ số bit 1 trong

MBiS(X) là các giao dịch trong CSDL DB, do đó công thức 1.4 đƣợc viết lại

∑

nhƣ sau:

(2.3) wus(X)

Với: Sum_twu = ∑ với m là số lƣợng các giao dịch trong

CSDL DB.

Thuật toán 2.5: INTERSECTION_MBiS

Input: MBiS(X) có n1 đoạn. Đoạn i có Starts = Si và End = Ei

MBiS(Y) có m1 đoạn Đoạn j có Starts = Sj và End = Ej

Output: Z = MBiS(X) MBiS(Y)

Method name: INTERSECTION_MBiS()

INTERSECTION_MBiS(MBiS(X), MBiS(Y))

1

Z =

55

2.2.2. Thuật toán xác định giao MBiS

2

while (i and j )

3

i1 IWS(X) và j1 IWS(Y là các đoạn giao đầu tiên của IWS(X) và

IWS(Y), tính từ đoạn i trên IWS(X và đoạn j trên IWS(Y);

4

Start = max(MBiS(X) [i1].start, MBiS(Y) [j1].start);

5

End = min(MBiS(X) [i1].end, MBiS(Y) [j1].end);

6

Z = Z [Start,End]};

7

if(End = MBiS(X) [i1].end)then

8

i = i1 1;// chuyển sang đoạn khác trênMBiS(X)

9

j = j1;

10

else

11

j = j1 1;// chuyển sang đoạn khác trênMBiS(Y)

12

i = i1;

13

return Z;//Z là kết quả củaMBiS(X) MBiS(Y)

Hình 2.22. Thuật toán xác định giao hai MBiS

Độ phức tạp của thuật toán INTERSECTION_MBiS trong hình 2.22 là

O(n + m), với n và m là số lƣợng đoạn tƣơng ứng của MBiS(X) và MByS(Y).

Để xác định giao của hai MBiS, ta chỉ cần xác định max và min của các đoạn

giao nhƣ dòng 5 và 6, đó chính là start và end của đoạn giao cần tìm. Do đó

tiết kiệm đƣợc thời gian trong xử lý.

2.2.3. Thuật toán khai thác FWUI dựa trên MBiS-tree

2.2.3.1. Cấu trúc MBiS-tree

Cấu trúc dữ liệu MBiS-tree đƣợc đề xuất trong [I] dùng để khai thác

FWUI. Mỗi nút trên MBiS-tree gồm ba thành phần X, MBiS(X) và wus(X),

trong đó:

- X là một tập mục,

- MBiS(X) là MBiS của X,

- wus(X) là giá trị wus của X.

Kết nối hai nút X và Y tạo ra nút mới X Y, với điều kiện X và Y có cùng

độ dài và cùng tiền tố |X|-1 phần tử. Đồng thời wus(X Y) minwus với

56

minwus do ngƣời sử dụng định nghĩa.

2.2.3.2. Thuật toán tính wus của tập mục

Để khai thác FWUI, cần phải xác định wus của các tập mục theo công

thức 2.3. Do đó cần phải xác định tidset của các tập mục dựa trên MBiS của

Thuật toán2.6: CALCULATION_WUS

Input: MBiS(X)

Output: wus của X

Method name: CALCULATION_WUS()

CALCULATION_WUS(MBiS(X))

for all i MBiS(X) do

1

for all j đoạn i của MBiS(X) do

2

3

s = s + twu( ;

4

return (s/Sum_twu);

các tập mục. Thuật toán đƣợc trình bày trong Hình 2.23.

Hình 2.23. Thuật toán tính wus dựa trên MBiS

Việc tính wus của tập mục dựa trên MBiS rất đơn giản, do cấu trúc

MBiS lƣu các đầu và cuối đoạn bit 1 liên tiếp trên bit-vector. Do đó chỉ cần

độ phức tạp O(1) để xác định các ID giao dịch. Nên độ phức tạp thuật toán

CALCULATION_WUS() là O(k) với k là số lƣợng các giao dịch chứa X. Nói

cách khác k chính là tổng số bit 1 trên bit-vector của tập mục X.

2.2.3.3. Thuật toán MBiS-FWUI

Lớp trên cùng (mức 0) của MBiS-tree đƣợc kí hiệu là []. Lớp thứ nhất

chứa các 1-itemset thỏa mãn minwus. Mức thứ k chứa các k-itemset thỏa mãn

minwus.

Mỗi mức của MBiS-tree chứa các lớp tƣơng đƣơng, mỗi lớp tƣơng

đƣơng đƣợc tạo thành từ một mục cha ở mức trên kết hợp lần lƣợt với các nút

cùng lớp tƣơng đƣơng của mục cha đó. Các nút trong cùng một lớp tƣơng

đƣơng chỉ khác nhau phần tử cuối cùng. Mức k chứa các k-itemset đƣợc tạo từ

57

sự kết hợp các cặp nút từ mức (k - 1) gồm các (k - 1)-itemset. Mỗi nút đƣợc

thêm vào MBiS-tree nếu giá trị wus của tập mục đó minwus. Do vậy,

MBiS-tree chứa tất cả các FWUI khai thác theo ngƣỡng minwus.

Quá trình xây dựng MBiS-tree theo mô tả trên đƣợc trình bày bằng thuật

Thuật toán 2.7: MBiS_FWUI

Input: CSDL BD vàminwus;

Output: MBiS-tree chứa tất cả FWUI thỏa mãn minwus của DB

Method name: MBiS_FWUI()

MBiS_FWUI()

1

[] = j I|wus_ j minwus;

2

MBiS-tree = ; P = ;

3

FWUI_MINE(P);

4

FWUI_mine( [P])

5

for all li P] do

6

[Pi] = ;

7

for all lj [P], (with j i) do

8

X = li lj;

9

Y =INTERSECTION_MBiS(MBiS(li), MBiS(lj));

10

wus_X = CALCULATION_WUS(Y);

11

if (wus_X minwus) then

12

[Pi] = [Pi] {(X, Y, wus_X)};

13

MBiS-tree = MBiS-tree [Pi];

14

FWUI_MINE( [Pi])

toán MBiS-FWUI.

Hình 2.24. Thuật toán khai thác FWUI dựa trên MBiS-tree

Đầu vào của thuật toán MBiS-FWUI là CSDL số lƣợng DB và minwus.

Trƣớc hết, CSDL đƣợc quét một lần để tính wus của các mục (dòng 2), các

mục thỏa mãn minwus đƣợc đƣa vào mức 0 của MBiS (dòng 3). Từ dòng 6

đến dòng 9, kết nối một nút với các nút sau đó (j > i) trong cùng một lớp

58

tƣơng đƣơng. Dòng 10 tính giao MBiS của tập mục mới tạo thành ở bƣớc 9

theo thuật toán 2.5. Dòng 11 tính wus theo thuật toán 2.6. Dòng 12, tập mục X

đƣợc kết nạp vào lớp Pi nếu thỏa mãn minwus. Dòng 13, lớp tƣơng đƣơng Pi

đƣợc kết nạp vào MBiS-tree. Cuối cùng, dòng 14 gọi đệ qui với lớp Pi.

2.2.4. Kết quả thực nghiệm

CSDL thực nghiệm và môi trƣờng thực nghiệm nhƣ trong mục 2.1.4. Số

lƣợng cho các mục xuất hiện trong các giao dịch đƣợc thêm bằng cách sinh

ngẫu nhiên trong khoảng từ 1 đến 10 đối với các CSDL: RETAIL, BMS-POS,

CONNECT, ACCIDENTS.

Sau đây là hình các kết quả thực nghiệm với cấu trúc MBiS đƣợc sử

dụng trong thuật toán MBiS_FWUI so sánh với các thuật toán khi cài đặt

bằng cấu trúc DBV và DIFFSET.

150

139,571

DBV

100

MBiS

64,141

DIFFSET

2.2.4.1. So sánh thời gian thực thi:

) s ( e m

50

29,648

i t

0

0.6

0.5

0.4

0.3

0.2

0.1

minwus(%)

250

232,209

DBV

200

MBiS

125,091

150

DIFFSET

85,102

Hình 2.25. So sánh thời gian chạy trên CSDL RETAIL.

) s ( e m

100

i t

50

0

0.6

0.5

0.4

0.3

0.2

0.1

minwus(%)

59

Hình 2.26. So sánh thời gian chạy trên CSDL BMS-POS.

400

DBV

309,301

300

MBiS

200

DIFFSET

) s ( e m

98,594 72,427

100

i t

0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

DBV

2501,68

MBiS

DIFFSET

Hình 2.27. So sánh thời gian chạy trên CSDL SALE-FACT-1997.

) s ( e m

i t

563,70 345,81

3000 2500 2000 1500 1000 500 0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

3000

2748,776

DBV

MBiS

2000

DIFFSET

Hình 2.28. So sánh thời gian chạy trên CSDL SALE-FACT-1997+1998.

) s ( e m

1000

i t

640,854 526,32

0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

60

DBV

55,202 41,935

MBiS

40

DIFFSET

Hình 2.29. So sánh thời gian chạy trên CSDL SALE-FACT-SYNC.

) s ( e m

20

i t

6,094

0

0.96

0.95

0.94

0.93

0.92

0.9

minwus(%)

60

Hình 2.30. So sánh thời gian chạy trên CSDL CONNECT.

250

DBV

212,667

200

MBiS

150

139,278

) s ( e m

DIFFSET

100

i t

50

30,742

0

0.9

0.8

0.6

0.5

0.7 minwus(%)

Hình 2.31. So sánh thời gian chạy trên CSDL ACCIDENTS.

200

DBV

160,687

150

MBiS

100

DIFFSET

50

2.2.4.1. So sánh bộ nhớ:

) b M ( y r o m e m

48,479 35,131

0

0.6

0.5

0.4

0.2

0.1

0.3 minwus(%)

DBV

431,725

MBiS

DIFFSET

213,67 144,981

Hình 2.32. So sánh bộ nhớ sử dụng trên CSDL RETAIL.

) b M ( y r o m e m

500 400 300 200 100 0

0.6

0.5

0.4

0.3

0.2

0.1

minwus(%)

800

DBV

600

720 622,14 542,7

MBiS

400

DIFFSET

200

Hình 2.33. So sánh bộ nhớ sử dụng trên CSDL BMS-POS.

) b M ( y r o m e m

0

0.03

0.02

0.1

0.06

0.03

0.01

minwus(%)

61

Hình 2.34. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997.

2000

DBV

1500

MBiS

1549,32 1477,976 1344,846

1000

DIFFSET

500

) b M ( y r o m e m

0

0.3

0.2

0.03

0.01

0.1

0.06 minwus(%)

2000

DBV

1500

1699,922 1543,975 1482,239

MBIS

1000

DIFFSET

500

Hình 2.35. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997+1998.

) b M ( y r o m e m

0

0.6

0.5

0.4

0.3

0.2

0.1

minwus(%)

50

DBV

46,579 41,935

40

MBiS

30

DIFFSET

20

10

Hình 2.36. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-SYNC.

) b M ( y r o m e m

6,094

0

0.96

0.95

0.92

0.9

0.94

0.93 minwus(%)

150

DBV

132,436

MBiS

100

78,172

DIFFSET

50

30,742

Hình 2.37. So sánh bộ nhớ sử dụng trên CSDL CONNECT.

) b M ( y r o m e m

0

0.9

0.8

0.7

0.6

0.5

minwus(%)

62

Hình 2.38. So sánh bộ nhớ sử dụng trên CSDL ACCIDENT.

Hình 2.25 đến 2.29 và Hình 2.32 đến 2.36 cho thấy rằng cấu trúc MBiS

hiệu quả hơn DBV và DIFFSET trên các CSDL thƣa. Ví dụ, trên CSDL

RETAIL với minws = 0,1%. Thời gian khai thác của MBiS, DIFFSET và

DBV lần lƣợt là 29,648s, 64,141s và 139,571s. Bộ nhớ sử dụng của IWS,

MBiS, DIFFSET và DBV lần lƣợt là 35,131MB, 48,479MB và 160,687MB.

Hình 2.30, 2.31, 2.37 và 2.38 cho thấy MBiS không tốt hơn DBV và

DIFFSET trên các CSDL dày. Do MBiS bị phân mảnh thành quá nhiều đoạn

bit 1, do đó việc xác định giao MBiS của các cặp tập mục sẽ tốn nhiều thời

gian do số lƣợng các đoạn bit 1 là rất lớn.

Đối với CSDL thƣa, số lƣợng các mục trên mỗi giao dịch ít, nên số đoạn

của MBiS là không nhiều, trong khi cấu trúc MBiS lại có lợi thế xác định

nhanh của giao của hai MBiS dó đó, MBiS có hiệu quả trên các dữ liệu thƣa

so với các cấu trúc đã có, kể cả tiếp cận Diffset. Đối với CSDL CSDL dày thì

ngƣợc lại, mỗi mục xuất hiện trong nhiều giao dịch, dó đó tidset của chúng

khi biểu diễn bằng MBiS sẽ có nhiều đoạn, điều này làm cho bộ nhớ có thể

tăng lên do cần thêm bộ nhớ để lƣu các đầu và cuối đoạn, ngoài ra với các

đoạn ít hơn bốn phần tử sẽ làm cho bộ nhớ cần nhiều hơn là cách biểu diễn

thông thƣờng. Do đó MBiS không hiệu quả hơn các phƣơng pháp khác trên

CSDL dày, các kết quả thực nghiệm trên hai CSDL CONNECT và

ACCIDENT thể hiện nhận định này.

2.3. Thuật toán khai thác TRFWUIk

Phần này trình bày kiến thức cơ sở về bài toán khai thác TRFWUIk trên

CSDL số lƣợng và đề xuất hai cấu trúc mới DTab và DHeap với hai thuật

toán tƣơng ứng DTab-TRFWUI và DHEAP_TRFWUI khai thác FWUIk.

Nội dung về cấu trúc DTab đã đƣợc công bố tại công trình [IV].

2.3.1. Một số khái niệm

Định nghĩa 2.10. (Rank của một tập mục) Cho một tập mục X ( I) của

63

CSDL số lƣợng DB. Rank của X là Rx đƣợc xác định nhƣ sau:

Rx = |{wus(Y)|wus(Y) wus(X), Y I}|.

Mệnh đề 2.1: Cho hai tập mục X và Y (X, Y I). Nếu wus(X) = wus(Y) thì

Rx = Ry.

Định nghĩa 2.11. TRFWUIk của CSDL số lƣợng BD là tập tất cả các

tập mục X mà X I và Rx k:

TRFWUIk = { X I| Rx k}

Ví dụ 2.11: Xét CSDL DB trong ví dụ 1.2, ta có TRFWUI3, TRFWUI4,

TRFWUI5 nhƣ trong Bảng 2.10.

Bảng 2.10. Bảng TRFWUIk

Số lượng K TRFWUIk

3 {1,0: B},{0,898: E, BE},{0,803: A, AB, ABE} 6

{1,0: B},{0,898: E, BE},{0,803: A, AB, ABE}, {0,764: D,

4 {1,0: B},{0,898: E, BE},{0,803: A, AB, ABE}, {0,764: D, BD} 8

BD},{0,662: AD, DE, ABD, ADE, BDE, ABDE}

14 5

Từ Bảng 2.10, với k = 3 ta có sáu FWUI và k = 5 có mƣời bốn FWUI

thỏa mãn. Trong đó E và BE có cùng nhóm do cùng độ đo wus. Tƣơng tự, A,

AB và ABE có cùng nhóm do có cùng wus = 0,803.

Mệnh đề 2.2: Tập mục X (X I) của một CSDL số lƣợng DB, nếu X

TRFWUIk thì các tập mục Y (Y I và X Y) TRFWUIk.

Nhƣ vậy, bài toán khai thác TRFWUIk từ CSDL số lƣợng là bài toán tìm

tất cả các tập mục X sao cho {X|X I, Rx k}

2.3.2. Cấu trúc DTab

DTab [45] là một danh sách liên kết hai chiều gồm k phần tử có giá trị

giảm dần. Nhƣ vậy phần tử thứ k là phần tử có giá trị nhỏ nhất gọi là min-

64

DTab. Ví dụ với k = 5 trong Bảng 2.10 ta có DTab nhƣ Hình 2.39:

1,0

0,898

0,803

0,764

0,662 NULL

Hình 2.39. DTab với k = 5

DTab trong Hình 2.40 có năm phần tử, phần tử thứ nhất có giá trị 1,0,

phần tử thứ hai có giá trị 0,898, v.v..., min-DTab = 0,662.

Với cấu trúc nhƣ trên, việc thêm một phần tử vào DTab để đảm bảo thứ

tự giảm dần có chi phí O(k). Đồng thời với nó là việc loại phần tử cuối cùng

ra khỏi DTab mất chi phí O(1).

2.3.3. Cấu trúc TR-tree

TR-tree là một cây gồm nhiều mức, mỗi mức gồm nhiều lớp tƣơng

đƣơng, mỗi lớp tƣơng đƣơng gồm nhiều nút, các nút trong cùng một lớp

tƣơng đƣơng có cùng nút cha ở mức trên, có số phần tử bằng nhau và chỉ khác

nhau phần tử cuối cùng.

Để tối ƣu bộ nhớ lƣu trữ tidset của các tập mục và tăng tốc độ tính toán

trong khai thác TRFWUIk, trong phần này tidset của các tập mục đƣợc biểu

diễn bởi cấu trúc IWS [II, V] đã đƣợc trình bày trong mục 2.1.

- Tập mục X

-

Mỗi nút gồm ba thành phần:

- wus của X

IWS của X

Kết hợp hai nút trong cùng một lớp tƣơng đƣơng tạo ra nút mới trên TR-

tree ở mức tiếp theo nếu wus của tập mục mới tạo thành min-DTab. Đồng

thời chèn wus(X) vào DTab và cập nhật lại min-DTab mới.

2.3.4. Thuật toán khai thác TRFWUIk sử dụng cấu trúc dữ liệu DTab

Thuật toán DTAB_TRFWUI dựa trên TR-tree gồm ba bƣớc nhƣ sau:

Bước 1: Quét CSDL tính wus của các mục, nếu số lƣợng mục có giá trị

wus khác nhau k thì chỉ lấy đúng k wus khác nhau lớn nhất. Các mục này

65

đƣợc đƣa vào lớp thứ nhất của TR-tree và là một lớp tƣơng đƣơng. Đồng thời

đƣa các giá trị wus của các mục này vào DTab theo thứ tự giảm dần. min-

DTab là giá trị nhỏ nhất wus trong DTab (DTab[k]).

Bước 2: Kết nối các cặp l-itemset (Xl và và Yl) trong các lớp tƣơng

đƣơng để tạo ra các (l+1)-itemset là {X, wus_X, IWS(X)} ở lớp tiếp theo nếu

wus_Xl và wus_Yl cùng min-DTab:

Nếu DTab chƣa đủ k phần tử thì bổ sung wus-X vào DTab

- Nếu trên DTab đã tồn tại một giá trị = wus_X thì thêm nút mới {X,

Ngƣợc lại, nếu wus_X min-DTab thì:

- Ngƣợc lại, loại phần tử thứ k trên DTab (DHaep) và chèn wus_X

wus_X, IWS(X)} vào TR-tree.

vào DTab sao cho đảm bảo tính giảm dần của DTab, đồng thời thêm

nút mới {X, wus_X, IWS(X)} vào TR-tree.

Bước 3: Lặp lại bƣớc 2 cho đến khi nào không có thêm tập mục nào

đƣợc tạo ra.

Kết thúc thuật toán, các tập mục trên TR-tree có wus min-DTab là các

TRFWUIk khai thác đƣợc.

Thuật toán 2.9: GEN_DTAB-TR-TREE

Input: CSDL DB và k;

Output: DTab, TR-tree

Method name: GEN_DTAB-TR-TREE()

GEN_DTAB-TR-TREE(DB, k)

1

d = 0;

2

[] =  j I, j là 1-itemset;

3

for all j [] do

4

if (d k) then

5

DTab wus_X;

6

Update min-DTab;

7

P = [];

66

Thuật toán đƣợc mô tả nhƣ Hình 2.40:

8

DTAB-TR-TREE( [P]);

9

for all li [P] do

10

[Pi] = ;

11

if (wus_li min-DTab) then

12

for all lj [P], với (j i) do

13

if (wus _lj min-DTab) then

14

X = lI lj;

15

IWS_X = INTERSECTION_IWS(IWS(li), IWS(lj));

16

Tính wus_X dựa trên IWS(X);

17

if (wus_X min-DTab) then

18

[Pi] = [Pj] {(X, wus_X, IWS_X};

19

if (wus_X>min-DTab) then

20

DTab wus_X;

21

Update min-DTab;

22

DTAB-TR-TREE( [Pi]);

Hình 2.40. Thuật toán tạo TR-tree sử dụng DTab

Dòng 3, tìm các 1-itemset và sắp xếp giảm dần theo wus. Dòng 4 đến

dòng 6, kết nạp các 1-itemset vào DTab. Dòng 15 sử dụng hai thuật toán

INTERSECTION_IWS(IWS(li), IWS(lj)) đƣợc trình bày trong [V] dùng để

tính giao hai IWS. Dòng 17 và 18, nếu wus min-DTab thì chèn nút mới

vào TR-tree. Dòng 19 đến dòng 21, nếu wus > min-DTab chèn wus vào

DTab và cập nhật lại giá trị min-DTab. Dòng 22 gọi đệ quy với lớp tƣơng

đƣơng mới Pi.

Nhƣ vậy chỉ các tập mục trong cùng một lớp tƣơng đƣơng có giá trị

wus min-DTab mới đƣợc xét kết nối với nhau để tạo ra các tập mục mới,

các tập mục mới này cũng phải có wus min-DTab mới đƣợc chèn vào TR-

tree, đồng thời min-DTab đƣợc cập nhật mới sau mỗi lần chèn một wus vào

67

DTab. Đây là điều kiện để cắt nhánh nhanh trên TR-tree.

Kết thúc thuật toán GEN_TR-Tree tạo ra cây TR-tree chứa các tập mục

đã đƣợc xét trong quá trình khai thác TRFWUIk, nhiều tập mục thuộcTR-tree

nhƣng không là TRFWUIk do các wus đƣợc cập nhật trên DTab đã loại các

tập mục này khỏi TRFWUIk. Thuật toán DTab-TRFWUI trong Hình 2.41 có

Thuật toán 2.10: DTAB_TRFWUI

Input: CSDL DB và ngưỡng k

Output: Z là TRFWUIk

Method name: DTAB_TRFWUI()

DTAB_TRFWUI(TR-tree,min-DTab)

GEN_DTAB-TR-TREE(DB, k)

1

Z = ;

2

for all X TR-tree do

3

if (X.wus min-DTab)then

4

Z {X.itemset, X.wus};

chức năng lọc các tập mục trên TR-tree là TRFWUIk

Hình 2.41. Thuật toán lọc ra TRFWUIk

Thuật toán DTAB_TRFWUI gọi hàm GEN_DTAB-TR-TREE() để tạo

TR-tree ở dòng 1, sau đó xét tất cả các nút thuộc TR-tree và lọc ra các tập

mục có wus không nhỏ hơn min-DTab-chính là TRFWUIk từ dòng 2 đến

dòng 5.

2.3.5. Thuật toán khai thác nhanh TRFWUIk dựa trên cấu trúc DHeap

2.3.5.1. Cấu trúc DHeap

Cấu trúc DTab dùng để cập nhật các giá trị wus thỏa mãn ngƣỡng min-

DTab của các tập mục trong quá trình khai thác TRFWUIk nhƣ đã trình bày ở

trên có chi phí O(k) để chèn một phần tử mới. Tuy nhiên, với những trƣờng

hợp giá trị k lớn thì chi phí cho việc chèn các giá trị mới vào DTab vẫn tốn

nhiều thời gian. Để giải quyết vấn đề này, luận án đề xuất cấu trúc Dynamic

68

Heap (DHeap) là hàng đợi ƣu tiên (Heap) nghĩa là các giá trị lớn hơn sẽ có

thứ tự ƣu tiên xử lý trƣớc (đống max). Thao tác cập nhật giá trị mới vào

DHeap mất chi phí O(log(k)). Nên thay thế DTab bằng DHeap sẽ giúp giảm

thời gian đáng kể trong khai thác TRFWUIk. Một ví dụ với DHeap đƣợc trình

bày trong hình 2.42.

Hình 2.42. DHeap với k = 5 với CSDL trong ví dụ 1.4

2.3.5.2. Thuật toán khai thác nhanh TRFWUIk dựa trên DHeap

Thuật toán DHEAP_TRFWUI khai thác nhanh TRFWUIk trên CSDL số

lƣợng dựa trên cấu trúc DHeap gồm bốn bƣớc nhƣ thuật toán

DTAB_TRFWUI. Chỉ thay cấu trúc DTab bằng cấu trúc DHeap trong quá

trình cập nhật các giá trị wus. Hình 2.44 là thuật toán tạo cây TR-tree kết hợp

Thuật toán 2.9: GEN_DHEAP-TR-TREE

Input: CSDL DB và k;

Output: DHeap, TR-tree

Method name: GEN_DHEAP-TR-TREE()

GEN_DHEAP-TR-TREE(DB, k)

1

d = 0;

2

[] =  j I|j là 1-itemset;

3

for all j [] do

4

if (d k) then

5

INSRERT_DHEAP(wus_j); // wus của mục j

6

DHEAP-TR-TREE( [P]);

7

P = [];

8

for all li [P] do

69

DHeap trong quá trình cắt nhánh các tập mục chắc chắn không thỏa mãn:

9

[Pi] = ;

10

if (wus_li min-Dheap) then

11

for all lj [P], (vớij i) do

12

if (wus_lj min-DTab) then

13

X = li lj;

14

IWS_X = INTERSECTION_IWS(IWS(li), IWS(lj));

15

Tính wus_X dựa trên IWS(X);

16

if (wus_X min-DHeap) then

17

[Pi] = [Pi] {(X, wus_X, IWS_X};

18

if (wus_X >min-DHeap) then

19

INSRERT_DHEAP(wus_X);

20

DHEAP-TR-TREE( [Pi]);

Hình 2.43. Thuật toán tạo TR-tree sử dụng DHeap

Thuật toán 2.10: DHEAP_TRFWUI

Input: CSDL DB và ngưỡng k

Output: Z là TRFWUIk

Method name: DHEAP_TRFWUI()

DHEAP_TRFWUI(TR-tree, min-DHeap)

GEN_DHEAP-TR-TREE(DB, k)

Z = ;

1

for all X TR-tree do

2

3

if (X.wus min-DHeap)then

4

Z {X.itemset, X.wus};

Thuật toán lọc TRFWUIk từ TR-tree nhƣ Hình 2.45

Hình 2.44. Thuật toán lọc ra TRFWUIk

2.3.6. Kết quả thực nghiệm

2.3.6.1. CSDL thực nghiệm

Phần này trình bày các kết quả thực nghiệm về thời gian thực thi của hai

phƣơng pháp đề xuất DHeap_TRFWUI và DTab_TRFWUI với phƣơng pháp

70

VTK. CSDL thực nghiệm đƣợc trình bày nhƣ trong Bảng 2.7

600

Dheap-TRFWUI

527,81

500

DTab-TRFWUI

400

300

VTK

2.3.6.2. Kết quả thực nghiệm

i

) s ( e m T

200

100

141,21 75,28

0

100

200

300

400

500

k

728,12

Dheap-TRFWUI

DTab-TRFWUI

Hình 2.45. So sánh thời gian chạy trên CSDL MBS-POS

i

VTK

) s ( e m T

211,66 107,4

800 700 600 500 400 300 200 100 0

100

200

400

500

300

k

DHeap-TRFWUI

578,62

DTab-TRFWUI

VTK

Hình 2.46. So sánh thời gian chạy trên CSD L RETAIL

i

) s ( e m T

164,22 68,2

700 600 500 400 300 200 100 0

100

200

300

400

500

k

71

Hình 2.47. So sánh thời gian chạy trên CSDL CONNECT

800

DHeap-TRFWUI

685,1

600

DTab-TRFWUI

400

269,2

VTK

i

) s ( e m T

200

97,61

0

100

200

400

500

300

k

800

732,06

600

400

279,02

DHeap-TRFWUI DTab-TRFWUI VTK

Hình 2.48. So sánh thời gian trên CSDL SALE-FACT-1997

i

) s ( e m T

200

104,2

0

100

200

400

500

300

k

800

739,15

DHeap-TRFWUI

600

DTab-TRFWUI

400

281,17

VTK

Hình 2.49. So sánh thời gian trên CSDL SALE-FACT-1997+1998

i

) s ( e m T

200

109,12

0

100

200

400

500

300

k

Hình 2.50. So sánh thời gian trên CSDL SALE-FACT-SYNC

Các kết quả thực nghiệm từ Hình 2.46 đến 2.51 cho thấy hiệu quả của

phƣơng pháp Dtab-TRFWUI và DHEAP_TRFWUI so với VTK trên các

CSDL thực nghiệm. Phƣơng pháp hiệu quả nhất là DHEAP_TRFWUI với

việc sử dụng cấu trúc DHeap. Ví dụ trên CSDL RETAIL với k = 500, VTK có

thời gian xử lý là 527,81s, DTab-TRFWUI là 141,21s, trong khi

DHEAP_TRFWUI là 107,4s. Thời gian chạy của VTK nhiều hơn 3,74 lần so

72

với DTab-FWUI và nhiều hơn DHEAP_TRFWUI 4,91 lần.

Kết quả thực nghiệm ở trên cho thấy việc sử dụng DHeap, DTab là hiệu

quả, không tốn thời gian lọc ra các tập mục cùng lớp để kết nối chúng lại do

trên cây TR-tree đã có sẵn các lớp. Đồng thời việc cập nhật các giá trị min-

DTab với chi phí O(1) trên DTab, DHeap và cắt nhánh nhanh trên TR-tree.

Ngoài ra, thao tác tìm và chèn một phần tử mới vào DHeap chỉ mất thời gian

O(nlogn).

2.4. Kết luận chƣơng

Chƣơng này tập trung trình bày các kết quả nghiên cứu khai thác nhanh

tập mục phổ biến trên CSDL số lƣợng với các cấu trúc mới đề xuất MBiS [I],

IWS [II, V] theo tiếp cận cải tiến cấu trúc dữ liệu lƣu tidset theo bit-vector.

Đồng thời đƣa ra bài toán khai thác Top-rank-k tập phổ trên CSDL số lƣợng

và đề xuất hai cấu trúc DTab [III], DHeap với hai thuật toán DTab-TRFWUI

[III] và DHEAP_TRFWUI để giải quyết hiệu quả bài toán này.

Các đề xuất về tối ƣu bit-vector với IWS bằng cách loại bỏ hoàn toàn các

word hai byte có giá trị bằng 0 trong biểu diễn bit-vector tidset của tập mục.

Nghĩa là IWS chỉ lƣu các word khác 0 liên tiếp trên bit-vector tidset của các

tập. Đồng thời đề xuất sử dụng mảng MAP lƣu trữ vị trí bit 1 đối với các số có

giá trị trong khoảng hai byte để tính nhanh ws (đối với khai thác FWI) và wus

(đối với khai thác FWUI). Các đề xuất này thật sự có hiệu quả nhất là đối với

các CSDL thƣa. Kết quả thực nghiệm trong mục 2.2.4.3 đã thể hiện rõ điều đó.

Bên cạnh đó, chƣơng 2 đề xuất cấu trúc MBiS, bằng cách chỉ lƣu các

đoạn bit 1 liên tiếp trên bit-vector của các tập mục. Với cấu trúc này việc xác

định giao MBiS của hai tập mục rất nhanh, do chỉ cần tính lại đầu và cuối mỗi

đoạn giao. Đồng thời, việc tính ws (đối với khai thác FWI) hay tính wus (đối

với khai thác FWUI). Các kết quả thực nghiệm trong mục 2.2.4.3 cho thấy

hiệu quả của MBiS so với DBV, tuy nhiên MBiS không hiệu quả hơn IWS,

do việc lƣu các đoạn bit 1 liên tiếp làm cho MBiS bị “phân mảnh” quá nhiều

73

dẫn tới việc xác định giao của các MBiS tốn nhiều thời gian.

Cuối cùng, chƣơng 2 đề xuất bài toán khai thác TRFWUIk trên CSDL số

lƣợng, đây là bài toán chƣa đƣợc đề cập trƣớc đây, mặc dù đã có nhiều công

bố liên quan đến bài toán này trên CSDL nhị phân. Cấu trúc DTab với khai

thác theo tiếp cận một lần quét CSDL đã cho thấy hiệu quả so với thuật toán

VTK. Tiếp theo luận án đề xuất cấu trúc DHeap dựa trên cấu trúc Heap, với

cấu trúc DHeap việc tìm vị trí chèn wus của tập mục mới là O(nlogn) giúp

giảm thời gian khai thác TRFWUIk. Các kết quả thực nghiệm trong mục

74

2.3.3.2 đã cho thấy hiệu quả của các đề xuất mới nói trên.

CHƢƠNG 3. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ

DỮ LIỆU SỐ LƢỢNG CÓ SỰ PHÂN CẤP CÁC MỤC

CSDL số lƣợng có sự phân cấp các mục là sự kết hợp giữa CSDL số

lƣợng và CSDL có sự phân cấp các mục. Do đó, về cơ bản khai thác tập mục

phổ biến trên CSDL số lƣợng có sự phân cấp các mục có thể đƣợc kế thừa từ

các phƣơng pháp khai thác tập mục phổ biến trên CSDL số lƣợng và CSDL

có sự phân cấp. Vì vậy, việc khó khăn và phức tạp của bài toán khai thác

FWUI trên CSDL số lƣợng có sự phân cấp cũng đƣợc kế thừa từ các bài toán

trên. Ngoài ra, đặc trƣng riêng của bài toán này là việc xác định trọng số của

các mục cha trên cây phân cấp nhƣ thế nào? Và xác định số lƣợng của từng

mục cha trong các giao dịch của CSDL ra sao? v.v... đã làm cho bài toán khai

thác tập mục phổ biến trên CSDL số lƣợng có sự phân cấp mục thêm sự phức

tạp và cần có những đề xuất tốt để giảm thiểu sự khó khăn đó.

CSDL số lƣợng có sự phân cấp các mục là CSDL xuất hiện nhiều trong

các ứng dụng thực tế, trong đó cây phân cấp đƣợc sử dụng nhƣ để phân loại

các nhóm mặt hàng, chủng loại hàng hóa. Các mục cha trên cây phân cấp là

mức khái quan cho mục con của nó. Tuy nhiên, cho đến hiện nay, bài toán

khai thác tập mục phổ biến trên loại CSDL này chƣa đƣợc quan tâm nghiên

cứu. Do vậy, phần nội dung chƣơng này luận án đề xuất bài toán khai thác

FWUI trên CSDL số lƣợng có sự phân cấp các mục trong mục 3.1 và đề xuất

một thuật toán MINE_FWUI dựa trên cấu trúc HIT-tree để khai thác FWUI

trong mục 3.2, các nội dung này đã đƣợc trình bày tại công bố [IV].

Tiếp theo, trong phần 3.3 luận án trình bày một số cải tiến nâng cao hiệu

quả khai thác FWUI trên CSDL số lƣợng có sự phân cấp các mục nhƣ:

(i) Đề xuất cấu trúc SDBV - là một mở rộng của DBV với việc sử dụng

phần tử là các số nguyên lớn (8 byte). Đề xuất này giúp làm giảm số

75

phép toán trong xác định giao giữa hai SDBV.

(ii) Đề xuất mệnh đề về việc xác định tidset mục nút cha dựa trên tidset

mục nút con. Với đề xuất này không phải tốn thời gian thêm các mục

nút cha vào CSDL và không làm tăng thêm bộ nhớ lƣu trữ.

(iii) Xác định nhanh mối quan hệ cha - con giữa các mục trên cây phân

cấp. Luận án đƣa ra mệnh đề về việc xác định mối quan hệ cha con

giữa các mục trong tập mục tạo thành bằng cách chỉ cần xác định

mối quan hệ của đúng một cặp mục trong tập mục đó.

Ngoài ra, các cấu trúc đã đề xuất trong chƣơng 2 nhƣ IWS, MBiS đều

đƣợc áp dụng vào để giải quyết hiệu quả hơn bài toán khai thác FWUI trên

CSDL số lƣợng có sự phân cấp các mục trong chƣơng này.

3.1. Giới thiệu bài toán

Định nghĩa 3.1. CSDL số lƣợng có sự phân cấp các mục -hierarchical

quantitative databases (HQDB) là một bộ gồm bốn thành phần: T, I, W, Tr

trong đó, T = {t1, t2, …, tm} là tập các giao dịch, I = {i1, i2, …, in} là tập các

mục, W = {w1, w2, …, wn} là tập các trọng số (lợi ích) tƣơng ứng của mỗi mục

trong tập các mục I và Tr là tập các cây phân cấp thể hiện mối quan hệ giữa

các mục. Mỗi giao dịch tk có dạng tk = { , , …, }, trong đó là số nguyên chỉ số lƣợng mục thứ i trong giao dịch tk, k = 1.. m.

Ví dụ 3.1: Cho HQBD HD = T, I, W, Tr với tập mục I = {A, B, C, D,

E}, các giao dịch T và trọng số W đƣợc trình bày trong Bảng 3.1 và Bảng 3.2,

các cây phân cấp Tr các mục nhƣ trong Hình 3.1.

Bảng 3.1. Giao dịch của HD Bảng 3.2. Trọng số

Giao dịch A B C D E F

Item

Weight

A

1 1 0 2 1 0

0,3

t1

B

0 1 3 0 1 0

0,2

t2

C

2 1 0 2 2 2

0,5

t3

D

3 1 1 0 1 0

0,6

t4

E

1 2 2 1 3 1

0,9

t5

F

0 1 1 1 0 1

0,1

t6

76

K

H

E

G

D

F

A

C

B

Và tập các cây phân cấp Tr nhƣ trong Hình 3.1

Hình 3.1. Tập các cây phân cấp Tr

Trong đó các kí hiệu A, B, C, D, E, F là đại diện cho tập các mặt hàng

theo Bảng 3.3 nhƣ sau:

Bảng 3.3. Tên mặt hàng của các mục

ID mục mục

A Desktop

B Ink-jet Printer

C Laser Printer

D Notebook

E Scanner

F Dot-matrix Printer

G Non-impact

H PC

K Printer

Theo Bảng 3.1 và Bảng 3.2, CSDL HD có sáu giao dịch {t1, t2, t3, t4, t5,

t6} và sáu mục {A, B, C, D, E, F}, trọng số của các mục tƣơng ứng là {0,3,

0,2, 0,5, 0,6, 0,9, 0,1}. Giao dịch t1 = {1, 1, 0, 2, 1, 0} có nghĩa là trong giao

dịch t1 có một mục A(Desktop), một mục B(Ink-jet Printer), hai mục

D(Notebook), một mục E(Scanner) và không có mục C với F nào.

Tập J = {G, K, H} là tập các mục cha của cây phân cấp không xuất hiện

trong các giao dịch của CSDL HD. Tuy nhiên chúng có vai trò nhất định, thể

hiện mối quan hệ của các mục trong CSDL HD. Do đó, khi khai thác FI trên

CSDL phân cấp đòi hỏi phải khai thác cả tập các mục trên cây phân cấp bao

77

gồm (I J).

HQDB có kế thừa hoàn toàn các định nghĩa, tính chất của CSDL số

lƣợng có sự phân cấp nhƣ đã trình bày trong chƣơng 1. Ngoài ra, khai thác

FWUI trên HQDB cần phải tính toán xác định trọng số của các mục cha, đồng

thời phải xác định số lƣợng các mục cha trong từng giao dịch dựa trên các

mục con của chúng trong mỗi giao dịch. Thông thƣờng có thể xác định các

đại lƣợng này thông qua các hàm MAX, MIN, SUM hay AVERAGE đối với

các giá trị số lƣợng và trọng số của các mục con của nó. Tuy nhiên, nếu sử

dụng công thức MIN hoặc AVERAGE thì số lƣợng và trọng số của mục cha

sẽ nhỏ hơn của mục con của nó trong nhiều trƣờng hợp. Điều này là không

thực tế, do mục cha là mức khái quát của mục con nên số lƣợng và trọng số

của nó không thể nhỏ hơn của mục con của nó. Do đó trong phạm vi luận án,

tác giả đề xuất sử dụng hai hàm là MAX và SUM trong xác định trọng số và

số lƣợng của các mục cha trên cây phân cấp trong mỗi giao dịch dựa trên

trọng số và số lƣợng của các mục con của nó trên cây phân cấp có sẵn trong

các giao dịch (là các mục ở nút lá).

Trong các CSDL thực tế, nếu trọng số hay số lƣợng của các mục cha nhƣ

là tổng trọng số hay số lƣợng của trọng số hay số lƣợng của các mục con (lợi

nhuận, giá trị, v.v…) thì sẽ sử dụng hàm SUM để xác định trọng số, số lƣợng

cho mục cha. Còn trong trƣờng hợp trọng số, số lƣợng của các mục cha nhƣ

đại diện cho trọng số và số lƣợng cho mục con (mức độ yêu thích, sự phản

hồi,…) thì sẽ sử dụng hàm MAX để xác định trọng số, số lƣợng của mục cha.

Trên cơ sở đó, luận án đề xuất hai định nghĩa sau:

Định nghĩa 3.2. Trọng số của mục cha trên cây phân cấp bằng hàm

Fun_weight của trọng số các mục con của nó ở nút lá nhƣ sau:

weight(A) Fun_weight(weight(A1); weight(A2 weight(Ak))

Trong đó A là mục cha trên cây phân cấp, A1, A2, ...,Ak là các nút lá của

78

A. Fun_weight có thể là hàm SUM hoặc MAX tùy vào CSDL thực tế.

Ví dụ 3.2: Với Fun_weight là hàm MAX: weight(K) =

MAX(weight(C), weight(B), weight(F)) = MAX(0,5; 0,2;0,1) = 0,5.

Định nghĩa 3.3. Số lƣợng của mục cha trên cây phân cấp ở trong giao

dịch nào đƣợc xác định bằng hàm Fun_quatity của số lƣợng các mục con của

quantity(A) tk = Fun_quantity(quantity(A1); quantity(A2 quantity(Ak))

nó ở trong giao dịch đó nhƣ sau:

Trong đó: A, A1, A2, ...,Ak tk và A1, A2, ..., Ak là con của A trên cây phân

cấp. Fun_quantity có thể là hàm MAX hoặc hàm SUM tùy thuộc vào CSDL

thực tế.

SUM(quantity(B); quantity(C); quantity(F))(do B, C, F t5) = SUM(2; 2; 1) = 5

Ví dụ 3.3: Với Fun_quantity là hàm SUM, ta có quantity(K) t5 =

Định nghĩa 3.4. Tập mục X I J) với I là tập các mục trong CSDL

(tập nút lá trên cây phân cấp) và J là tập các mục cha trên cây phân cấp đƣợc

gọi là phổ biến nếu wus(X) minwus, với minwus do ngƣời dùng xác định

trƣớc.

3.2. Thuật toán khai thác FWUI trên HQDB

Để khai thác FWUI trên HQDB bao gồm cả các mục cha trên cây phân

cấp, cần xác định weight cho các mục cha (theo Định nghĩa 3.2), đồng thời

cần xác định số lƣợng cho các mục cha (theo Định nghĩa 3.3) trong mỗi giao

dịch khi thêm các mục cha này vào trong các giao dịch [19].

3.2.1. Thuật toán xác định weight cho các mục cha

Thuật toán xác định weight cho các mục cha trên cây phân cấp theo Định

Thuật toán3.1: CALCULATION_WEGHTED

Input: R là gốc cây phân cấp Tr.

- Output: WA = {h, weght(h), h là các nút cha trên Tr}

79

nghĩa 3.2 đƣợc trình bày nhƣ sau:

- Method name: CALCULATION_WEGHTED()

CALCULATION_WEGHTED(R)

1

for all r children of R do

2

if (weight(r) = 0)then

3

CALCULATION_WEGHTED(r);

4

else

5

weight(R) = Fun_weight (weight(R), weight(r));

6

ChènR.weight vào WeightTable;

Hình 3.2. Thuật toán tính weight cho các mục cha

Thuật toán CALCULATION_WEGHTED trong Hình 3.2 là một thuật toán

đệ quy. Bắt đầu từ R là gốc của cây phân cấp. Duyệt hết toàn bộ cây để xác định

weight của các mục cha. Mỗi khi xác định đƣợc weight của một mục cha (line 6)

nó sẽ đƣợc chèn vào WeightTable (bảng WeightTable) chứa weight của tất cả

các mục trong CSDL).

3.2.2. Thuật toán thêm mục cha vào CSDL

Thuật toán thêm các mục cha vào CSDL đồng thời xác định weight cho

Thuật toán 3.2: ADD_PARENT

Input: CSDL HD và cây phân cấpTr.

- Output: CSDL HD (HD + các mục nút cha được chèn vào trong các giao dịch) - Method name: ADD_PARENT()

ADD_PARENT (R) for all t HD do for all i t do

if ( r Tr|r là cha của i) then

r.quantity = Fun_quantity (r.quantity, i.quantity);

1 2 3 4 5 6 7 8

if (r t) then

else

các mục cha trong các giao dịch đƣợc trình bày nhƣ Hình 3.3 sau đây:

t r; r.quantity = i.quantity; Hình 3.3. Thuật toán thêm mục cha vào CSDL

80

Thuật toán ADD_PARENT() quét lần lƣợt từng giao dịch trong CSDL,

với mỗi mục trong CSDL tìm các mục cha của nó trên cây cấp và thêm vào

CSDL nếu các mục cha này chƣa đƣợc thêm vào bởi một mục nào trong cùng

phân giao dịch. Dòng 1, quét từng dòng CSDL. Dòng 2, quét từng mục trên

mỗi giao dịch. Dòng 3, tìm các r là mục cha của i trên cây phân cấp Tr. Dòng

4 đến dòng 8, kiểm tra xem mục r đã đƣợc chèn vào CSDL trƣớc đó chƣa,

nếu đã chèn rồi thì xác định lại số lƣợng cho r theo Định nghĩa 3.3, còn nếu

chƣa chèn thì chèn r vào giao dịch t với quantity bằng quantity của mục i.

3.2.3. Thuật toán khai thác FWUI

3.2.3.1. Cấu trúc HIT-tree

Để khai thác FWUI trên HQDB theo Định nghĩa 3.4, luận án đề nghị sử

dụng cấu trúc HIT-tree. HIT-tree là một mở rộng của IT-tree [54]. HIT-tree

gồm nhiều mức, mỗi mức gồm nhiều lớp tƣơng đƣơng, mỗi lớp tƣơng đƣơng

bao gồm nhiều nút. Mỗi nút bao gồm ba thành phần: X, tidset(X), wus(X)

trong đó X là một tập mục, tidset(X) là tập các giao dịch chứa X và wus(X) là

độ hỗ trợ trọng số hữu ích của X đƣợc xác định theo công thức 1.4. Mỗi lớp

tƣơng đƣơng đƣợc tạo ra từ sự kết nối một mục cha ở lớp trên với lần lƣợt các

nút phía sau nó trong cùng lớp tƣơng đƣơng (để tránh trùng lặp), nút mới

đƣợc tạo thành khi và chỉ khi wus(X) của nút đó thỏa mãn ngƣỡng minwus.

Thuật toán 3.3: MINE_FWUIs

Input: HQDB HD, cây phân cấp Tr và ngưỡng minwus

Output: HIT-tree chứa các FWUI.

Method name: MINE_FWUIs()

MINE_FWUIs()

for all R TR do

1

CALCULATION_WEIGHTED(R);

2

ADD_PARENT();

3

81

3.2.3.2. Thuật toán khai thác FWUI

4

F = { i (I J), wus_i minwus};

5

HIT-tree ;

6

CREATE_HIT-tree(F)

7

P = ;

8

for all i F do

9

for j F (with j>i) do //j phía sau i

10

X = Fi Fj;

11

if ( x’ X, x” X: parent(x’) = x”)then

12

T = tidset(Fi) tidset(Fj) ;

13

if (wus_X minwus) then

14

P = P X, T, wus_X;

15

HIT-tree = HIT-tree X, T, wus_X;

16

CREATE_HIT-tree(P); // gọi đệ quy với lớp P

Hình 3.4. Thuật toán khai thác FWUI từ HQDB

Ví dụ 3.4: Thuật toán MINE_FWUIs trong Hình 3.4 với CSDL HD

trong ví dụ 3.1 và minwus = 0,6 nhƣ sau:

Dòng 2, thủ tục ADD_PARENT() cho kết quả nhƣ Bảng 3.4. Việc thêm

các mục cha, số lƣợng mục cha vào CSDL đƣợc thực hiện theo Định nghĩa 3.3,

việc thêm trọng số các mục cha theo Định nghĩa 3.2, ta có kết quả là Bảng 3.4

và 3.5. Đồng thời, twu của các giao dịch đƣợc tính nhƣ trong Bảng 3.6.

Bảng 3.5. Trọng số

Bảng 3.4. Giao dịchcủa HD

A B C D E F G H K

Item

Trọng số

1

1

0

2

1

1

2

1

A

0

0,3

0

1

3

0

1

3

0

3

B

0

0,2

2

1

0

2

2

1

2

2

C

2

0,5

3

1

1

0

1

1

3

1

D

0

0,6

1

2

2

1

3

2

1

2

E

1

0,9

0

1

1

1

0

1

1

1

F

1

0,1

ID t1 t2 t3 t4 t5 t6

G

0,5

H

0,6

K

0,5

82

Bảng 3.6. twu của các giao dịch

twu

ID

= 0,68

t1

3 2 2 6 9 5 2 6 5 7

= 1,12

t2

2 5 3 9 5 3 5 3 5

= 0,84

t3

3 2 2 6 2 9 2 2 5 6 2 5 2 8

= 0,76

t4

3 3 2 5 9 5 6 3 5 5

t5

= 0,84

3 2 2 5 2 6 9 3 5 2 6 5 2 9

= 0,43

t6

2 5 6 5 6 5 7

Sum_twu

= 4,67

Dòng 4, tập F (1-itemset phổ biến) gồm {A, B, C, D, E, G, H, K} nhƣ

Bảng 3.7:

mục

wus

Bảng 3.7. Tập 1-itemset phổ biến

F

= 0,65

A

A

68 84 76 84 4 76

= 1,0

B

B

68 2 84 76 84 43 4 76

= 0,67

C

C

= 0,6

D

D

2 76 84 43 4 76 68 84 84 43 4 76

= 0,91

E

E

= 0,45

F

68 2 84 76 84 4 76 84 84 43 4 76

= 1,0

G

G

68 2 84 76 84 43 4 76

= 0,76

H

H

68 84 76 84 43 4 76

= 1,0

K

K

68 2 84 76 84 43 4 76

83

Từ dòng 6 đến dòng 16 thủ tục đệ quy CREATE_HIT-tree() xây dựng

cây HIT-tree, sau khi xây dựng xong cây HIT-tree với ngƣỡng minwus, các

tập mục tại các nut trên cây HIT-tree là FWUI cần khai thác. Cây HIT-tree

với ngƣỡng minwus = 0,6 của CSDL HD nhƣ Hình 3.5.

Hình 3.5. Cây HIT-tree với CSDL HD và minwus = 0,6

Xét nút A trên cây HIT-tree:

A kết hợp với B: tidset(AB) = tidset(A) tidset(B) = {1, 3, 4, 5} {1, 2, 3,

4, 5, 6} = {1, 3, 4, 5}, wus(AB) = 0,68 >minwus⟹ kết nạp AB vào HIT-tree.

A kết hợp với C: tidset(AC) = tidset(A) tidset(C) = {1, 3, 4, 5} {2, 4,

5, 6} = {4, 5}, wus(AC) = 0,34 < minwus ⟹ không kết nạp AC vào HIT-tree.

Tƣơng tự kết nạp {AE, AG, AK} vào HIT-tree.

A kết hợp với H, không xét do H là cha của A trên cây phân cấp.

Tƣơng tự với các nút B, C, D, E, G, H, K ta có cây HIT-tree nhƣ Hình

3.5 có các nút là FWUI.

3.3. Một số cải tiến nâng cao hiệu quả khai thác FWUI trên HQDB

3.3.1. Cấu trúc EDBV

Thuật toán Eclat đƣợc Zaki và các đồng sự [49] đề xuất dựa trên IT-tree

có hiệu quả về mặt thời gian so với các phƣơng pháp khác. Tuy nhiên bộ nhớ

84

dùng để lƣu trữ tidset của các tập mục là rất lớn, đây chính là hạn chế của

phƣơng pháp này. Giải quyết đƣợc vấn đề bộ nhớ sẽ nâng cao hiệu quả về mặt

thời gian của tiếp cận này.

Zaki và các đồng sự [50] đề xuất sử dụng kĩ thuật diffset thay cho tidset.

Kĩ thuật diffset là một giải pháp hiệu quả nhằm rút gọn bộ nhớ so với tidset,

đồng thời giúp tính nhanh độ hỗ trợ trong bài toán khai thác FI. Tuy nhiên, do

đặc điểm diffset là lấy phần bù của tidset nên diffset không có hiệu quả trên

các CSDL thƣa.

Vo và các đồng sự [38] đề xuất DBV nhằm rút gọn bộ nhớ lƣu trữ tidset

bằng BitTable [13] và rút ngắn thời gian tính toán. Cách tiếp cận này khá hiệu

quả khi loại bỏ hoàn toàn các byte 0 ở đầu và cuối trên bit-vector và sử dụng

phép AND trên bit để tính giao tidset của hai tập mục. Đồng thời sử dụng một

mảng LOOKUP để định nghĩa trƣớc số lƣợng các bit 1 trong các byte, điều

này giúp tính nhanh độ hỗ trợ của các tập mục thông qua DBV. Từ đó DBV

đƣợc sử dụng với mảng mà mỗi phần tử là một byte. Đây là một hạn chế lớn

của DBV, do khi tính giao giữa hai DBV của các tập mục phải sử dụng nhiều

phép toán AND trên bit giữa các byte của hai DBV.

Cấu trúc MBiS đƣợc đề xuất và trình bày trong chƣơng 2 là cấu trúc

lƣu giữ các đoạn bit 1 liên tiếp nhau trên BitTable. MBiS có đặc điểm là xác

định giao giữa các tidset thông qua MBiS rất nhanh, do chỉ cần cập nhật lại

các đầu và cuối mỗi đoạn. Tuy nhiên, cấu trúc MBiS sẽ không có hiệu quả

nhiều trên các dữ liệu lớn do tính phân mảnh của tidset rất lớn dẫn đến

MBiS rất tốn bộ nhớ để lƣu trữ và tốn thời gian trong xác định giao do số

đoạn của mỗi MBiS lớn.

3.3.1.1. Xác định tidset của tập mục dựa trên EDBV

Luận án đề xuất cấu trúc EDBV (Extend DBV) và EIWS (Extend IWS)

bằng cách sử dụng các số nguyên lớn tám byte (Large Integer - LI) thay vì các

số nguyên một byte nhƣ DBV [38], MByS và hai byte nhƣ IWS Sử dụng các

85

LI giúp cho quá trình tính giao EDBV hay EIWS của hai tập mục nhanh hơn.

Do mỗi phép AND trên bit thực hiện trên các LI, mỗi LI có 64 bit đại diện

cho 64 giao dịch liên tiếp.

Tuy nhiên vấn đề đặt ra là làm thế nào để tính đƣợc wus của tập mục với EDBV và EIWS với các LI. Không đủ bộ nhớ định nghĩa trƣớc một mảng 264 phần tử để lƣu vị trí các bit 1 của các số trong khoảng từ 1 đến 264 nhƣ cách

làm trên MByS hay IWS.

Để tính nhanh tidset của tập mục phục vụ cho việc tính wus theo công thức 1.4, luận án định nghĩa trƣớc một mảng MAP gồm 216 (65536) phần tử

nhƣ đối với cấu trúc IWS. Trong đó, phần tử thứ i chứa một danh sách vị trí

các bit 1 của i tính từ trái qua phải đƣợc mô tả nhƣ Bảng 3.8:

Index

Bảng 3.8. Mảng MAP với 65.535 phần tử

Value 0000000000000001 0000000000000001 0000000000000010 …

111..110

111..111

MAP

Null

15

… 1, 2,.., 14, 15 1, 2,..,15, 16

16

0 2 … 65.534 65.535 1

Tiếp theo, sử dụng bốn phép AND trên bit với 65.535 kết hợp với ba

phép dịch phải bit để tách lần lƣợt các số nguyên hai byte (word) từ phải qua

trái. Mỗi lần AND với 65.535 ta đƣợc một word, ánh xạ word vào MAP ta

đƣợc danh sách vị trí các bit 1 trong word đó, từ đó ta xác định đƣợc ID giao

dịch của các tập mục.

Ví dụ 3.5: Cho K là một LI, K = 178.455.221.385.174.000, biểu diễn nhị

0000001001111010000000000001010000001110111110100001101111110000

phân của K bao gồm 64 bít nhƣ sau:

Cụ thể, số K đƣợc mô tả nhƣ trong Bảng 3.9

Binary 0000001001111010 0000000000010100 0000111011111010 0001101111110000

Index

634

3.834

7.126

20

MAP

7,10,11,12,13,15

5,6,7,9,10,11,12,13,15 4,5,7,8,9,10,11,12

12,14

Đoạn

1

3

4

2

86

Bảng 3.9. Biểu diễn số nguyên K dƣới dạng bốn đoạn, mỗi đoạn là một word

634

20 3.834 7.126

AND

65.535 = 7.126  MAP[7.126] = {4, 5, 7, 8, 9, 10, 11, 12}

634

20 3.834

Bƣớc 1 0

AND

65.535 = 3.834 MAP[3.834]={5, 6, 7, 9, 10, 11, 12, 13, 15}

0

634

20

Bƣớc 2 0

AND

65.535 =

20  MAP[20] = {12, 14}

0

0

634

Bƣớc 3 0

AND

65.535 =

634  MAP[634] = {7, 10, 11, 12, 13, 15}

Hình 3.6. Sử dụng các phép AND và dịch bit để tách các đoạn hai byte

Hình 3.6 mô tả ba lần dịch bit trên K để tách các word, sau đó ánh xạ vào

MAP để có vị trí các bit trong các word đã đƣợc định nghĩa trƣớc.

Mệnh đề 3.1. Chỉ số của bit 1 có vị trí thứ i trong đoạn thứ j của word

thứ k thuộc EDBV trên bit-vector là l đƣợc xác định theo công thức 3.1:

(3.1) l = (k-1) × 64 + (j-1)×16 + i

Trong đó:

- j là số hiệu đoạn word của block

- i là chỉ số một bit 1 trong đoạn thứ j của block thứ k

- k là chỉ số word của EDBV.

Chứng minh:

Dễ thấy trƣớc block thứ k có (k - 1) × 64 bit (do mỗi block tám byte có

64 bit). Tƣơng tự trƣớc đoạn thứ j có (j - 1) × 16 (mỗi đoạn hai byte có 16

bit). Do đó, chỉ số bit 1 thứ i của đoạn thứ j thuộc block k trên bit - vector

đƣợc xác định theo công thức:

87

Index_bit-vector(i) =(k - 1) × 64 +(j - 1)×16 + i

Ví dụ 3.6: Với số K trong ví dụ 3.5, ta có tập vị trí các bit 1 của K đƣợc

xác định nhƣ sau:

Word thứ 4: 7.126 có tập chỉ số {4, 5, 7, 8, 9, 10, 11, 12} {52, 53, 55,

56, 57, 58, 59, 60} do mỗi số đƣợc cộng thêm với (4 - 1) 16 = 48 theo công

thức 3.1.

Word thứ ba: 3.834 có tập chỉ số {5, 6, 7, 9, 10, 11, 12, 13, 15} {37,

38, 39, 41, 42, 43, 44, 45, 47}, do mỗi vị trí đƣợc cộng thêm (3 - 1) 16 = 32

theo công thức 3.1.

Word thứ hai: 20 có tập chỉ số {12, 14} {20, 22} do mỗi vị trí đƣợc

cộng thêm (2 - 1) 16 = 16 theo công thức 3.1.

Word thứ nhất: 634 có tập chỉ số {7, 10, 11, 12, 13, 15} tập này giữ

nguyên do đây là word số một nên (j - 1) = 0 với j = 1

Do đó, tập hợp các index bit 1 của K là {7, 10, 11, 12, 13, 15, 20, 22, 37,

38, 39, 41, 42, 43, 44, 45, 47, 52, 53, 55, 56, 57, 58, 59, 60}.

3.3.1.2. Thuật toán tính nhanh wus của tập mục dựa trên mảng MAP

Tính wus theo công thức 1.4 là thao tác thƣờng xuyên trong các bài toán

khai thác FWUI. Do đó, đòi hỏi phải xác định đƣợc tidset của các tập mục

tƣơng ứng. Dựa trên mảng MAP và Mệnh đề 3.1, luận án đề xuất thuật toán

xác định nhanh wus của tập mục dựa trên mảng MAP đƣợc trình bày nhƣ

Thuật toán 3.4: FAST_ CALCULATION_WUS

Input: EDBV(X)

Output: wus của tập mục X

Methode name: FAST_CALCULATION_WUS()

FAST_CALCULATION_WUS(EDBV(X))

for all i EDBV(X) do //xét các word trong EDBV(X)

1

k = EDBV(X) [i];// lấy word thứ i

2

t = 3 // dùng để xác định vị trí các đoạn trong k

3

while (k > 0)

4

88

trong hình 3.7.

m = k &65535;// lấy đoạn thứ t trong k

5

pos = i × 64 +(t×16);

6

7

for all j MAP [m] do// xét danh sách với chỉ số m

8

tidset(X)pos + j;// ánh xạ ra vị trí trên bit-vector

9

k = k >> 16;// k dịch phải 16 bít

10

t- - ;// chuyển sang đoạn tiếp theo trên k

11

y = 0;

12

for all i tidset(X) do

13

y + = twu [i];

14

wus = y/sum_twu;

15

return wus

Hình 3.7. Thuật toán tính nhanh wus của các tập mục

3.3.2. Tính tidset nút cha từ tidset nút con

Việc thêm các mục cha vào CSDL khi khai thác tập mục trên CSDL

phân cấp theo các phƣơng pháp trƣớc đây làm cho bộ nhớ tăng lên và tốn thời

gian quét và chèn dữ liệu. Trong phần này, luận án đề xuất giải pháp tính

tidset mục cha thông qua các mục con của nó trên cây phân cấp - là các mục

có trong CSDL gốc.

Mệnh đề 3.2. Tidset của mục cha trên cây phân cấp đƣợc xác định bằng

hợp tidset các mục con của nó ở nút lá.

Nhƣ vậy, tidset(X) = tidset(X1) tidset(X2) ... tidset(Xk).

Trong đó X1, X2,..., Xk là các mục con ở nút lá của mục X.

Ví dụ 3.7: Xét CSDL HD, do H là cha của A và D trên cây phân cấp nên

tidset(H) = tidset(A) tidset(D) = {1, 3, 4, 5} {1, 3, 5, 6} = {1, 3, 4, 5, 6}

Chứng minh: Các mục cha thuộc các giao dịch có chứa mục con của nó

ở nút lá, do đó tidset của mục cha sẽ chính là hợp tidset của tất cả tidset các

89

mục con của nó ở nút lá.

Thuật toán xác định tidset mục cha dựa vào tidset mục con của nó đồng

Thuật toán 3.5: CREAT_TIDSET

Input: HQDB HD, minsup

Output: tập L chứa các 1-itemset

- Method name: CREAT_TIDSET()

CREAT_TIDSET(Tr)

for all t T do

1

twu [t] = 0;

2

L = ;

3

for all i t do

4

5

tidset(i) t;// cập nhật tidset cho mục i

6

twu [t] = twu [t] + quantity [i] weight [i];

7

for all h parent(i) of Tr do

8

tidset(h) t; //cập nhật tidset cho mục cha của i

9

weight(h) = Fun_weight(weight(h), weight(i));

10

quantity (h) = Fun_quantity(quantity(h), quantity(i);

11

L h;

12

for all l L do

13

twu [t] = twu [t] + quantity(l) weight(l);

thời tính twu của các giao dịch đƣợc trình bày nhƣ trong Hình 3.8.

Hình 3.8. Thuật toán xác định tidset các mục và tính twu của các giao dịch

Thuật toán CREAT_TIDSET() thực hiện nhƣ sau:

Dòng 2, quét lần lƣợt từng giao dịch, dòng 3, 4 gán các giá trị ban đầu

twu của giao dịch t = 0, L = là tập các mục cha có nút con trong giao dịch t.

Dòng 5 xét từng mục trong giao dịch t. Dòng 6, xây dựng tidset của mục i.

Dòng 7 tính twu của giao dịch t đối với mục i (là các mục có sẵn trong

CSDL). Dòng 8, xét các mục cha của mục i. Dòng 9 xây dựng tidset cho mục

cha của h, dòng 10 và 11 xác định weight và quantity cho mục h theo các

90

Định nghĩa 3.2 và 3.3. Dòng 12, kết nạp h vào L-tập các mục cha đƣợc thêm

vào giao dịch t. Dòng 13 và 14, tính twu [t] với các mục cha có nút con trong

giao dịch t.

Nhƣ vậy, thuật toán CREAT_TIDSET() chỉ cần một lần quét CSDL đã

xây dựng xong tidset của tất các các mục, đồng thời tính twu của các giao

dịch mà không cần phải thêm các mục cha vào CSDL nhƣ thuật toán

MINE_FWUIs trong Hình 3.4. Bằng việc xác định tidset mục cha thông qua

các mục con trong các giao dịch đã bỏ đƣợc công đoạn tiêu tốn nhiều thời

gian là quét và thêm các mục cha vào CSDL.

3.3.3. Kiểm tra mối quan hệ cha con đối với các mục trong tập mục

Dòng số 11 trong thuật toán MINE_FWUIs ở Hình 3.4 có chức năng

kiểm tra mối quan hệ cha con của các cặp hai mục trong X - là mục mới tạo

thành từ Fi và Fj, cũng giống nhƣ Vo và các đồng sự [37] đã xét hết tất cả các

cặp phần tử trong X với nhau (có tất cả 2 cặp với m là số lƣợng

mục của tập mục X). Trong phần này luận án đề xuất phƣơng pháp kiểm tra

nhanh tính cha con của các mục trong tập mục đƣợc tạo thành trên HIT-tree

dựa vào Mệnh đề 3.2 nhƣ sau:

Mệnh đề 3.3. Cho Fi = X1X2...XkY1 và Fj = X1X2…XkY2 là hai tập mục

thuộc hai nút bất kì trong cùng một lớp tƣơng đƣơng trên HIT-tree, tập mục X

= Fi Fj = X1X2…XkY1Y2. Ta nói rằng trong X không tồn tại hai cặp mục nào

có quan hệ cha con khi và chỉ khi Y1 và Y2 không có quan hệ cha con với nhau.

Chứng minh: Thật vậy, Fi = X1X2...XkY1, Fj = X1X2...XkY2 và X =

X1X2...XkY1Y2. Do Fi và Fj thuộc các nút trên HIT-tree nên không tồn tại cặp

mục nào có quan hệ cha con trong Fi và Fj Y1 và Y2 không có mối quan hệ

cha con với các mục trong tập {X1X2...Xk}. Đồng thời tập mục X1X2...Xk thuộc

mục cha của Fi và Fj trên HIT-tree, do đó X1X2…Xk không tồn tại mối quan hệ

cha con giữa các mục. Do đó, các mục trong X không có mối quan hệ cha con

khi và chỉ khi cặp {Y1, Y2} không có mối quan hệ cha con với nhau trên cây

91

phân cấp Tr.

3.3.4. Thuật toán khai thác nhanh FWUI trên HQDB

Dựa trên các cải tiến đã trình bày ở trên, thuật toán khai thác nhanh

FWUI từ HQDB có tên FAST_MINE_FWUIs đƣợc đề xuất trong phần này.

Trong đó module ADD_PARENT() đƣợc sử dụng trong thuật toán

MINE_FWUIs không còn đƣợc sử dụng trong thuật toán này. Đồng thời cấu

trúc EDBV với các phần tử là các LI và việc kiểm tra nhanh mối quan hệ giữa

Thuật toán3.6: FAST_MINE_FWUIs

Input: HQDBHD và độ đo minwus

Output: HIT-tree chứa tất cả các FWUI

Method name: FAST_MINE_FWUIs()

FAST_MINE_FWUIs()

CREATE_TIDSET(Tr)

1

2

F = { i (I J), wus_i minwus}; //tâp 1-itemset thỏa mãn minwus

3

HIT-tree ;

CREATE_HIT-TREE(F);

4

CREATE_HIT-TREE(F)

5

P = ; // khởi tạo một lớp mới

6

for all i F do

7

for j F (vớij>i)do //duyệt các j sau i

8

if (Y1 parent(Y2) and Y1 parent(Y2)) then

9

X = Fi Fj;

10

T = EDBV(Fi) EDBV(Fj); //T là EDBV của X

11

wus_X = FAST_CALCULATION_WUS(X);

12

if (wus_X minwus)then

13

P = P X, T, wus_X;

14

HIT-tree = HIT-tree X, T, wus_X;

15

CREATE_HIT-TREE(P)

các mục trong tập mục đƣợc thiết lập.

92

Hình 3.9. Thuật toán khai thác nhanh FWUI trên HQDB

Thuật toán FAST_MINE_FWUIs() trong Hình 3.9 sử dụng thủ tục

CREATE_TIDSET() với một lần quét CSDL để xây dựng tidset của các mục

bao gồm cả các mục thuộc mục cha trên cây phân theo Mệnh đề 3.2. Bên

cạnh đó, thuật toán này tính twu của tất cả các giao dịch. Dòng 10 của thuật

toán MINE_FWUIs() kiểm tra toàn bộ các cặp mục trong tập mục X đƣợc thay

bằng dòng 8 trong FAST_MINE_FWUIs() với việc kiểm tra đúng một cặp (Y1,

Y2), trong đóY1, Y2 lần lƣợt là các phần tử cuối cùng của Fi và Fj theo Mệnh đề

3.3. Dòng 12 trong MINE_FWUIs() đƣợc thay thế bằng dòng 10 trong

FAST_MINE_FWUIs() với việc sử dụng cấu trúc EDBV thay cho cấu trúc

DBV.

3.4. Kết quả thực nghiệm

3.4.1. CSDL thực nghiệm

CSDL thực nghiệm bao gồm ba CSDL SALE-FACT-1997, SALE-

FACT-1997+1998 và SALE-FACT-SYNC đƣợc cho trong bảng 2.7. Đây là

các HQDB rút ra từ CSDL Foodmart2000 của SQL2000. Bảng 3.10 mô tả về

các CSDL:

Bảng 3.10. Mô tả CSDL thực nghiệm

Tên CSDL Số lƣợng giao dịch

SALE-FACT-1997 20.522

SALE-FACT-1997+1998 54.537

SALE-FACT-SYNC 58.308

Các CSDL có chung cây phân cấp gồm sáu cấp đƣợc trình bày cụ thể

trong Bảng 3.11

Bảng 3.11. Các mức trên cây phân cấp

Mức Tên các mức Số lƣợng nút

1 Product_family 3

2 Product_department 24

93

3 Product_category 48

4 Product_subcategory 56

5 Product_class 110

6 Product 1560

Theo Bảng 3.11 các CSDL thực nghiệm có ba cây phân cấp (mức một có

ba nút). Độ cao của cây phân cấp là sáu (có sáu cấp).

3.4.2. Kết quả thực nghiệm

3.4.2.1. So sánh bộ nhớ

Bảng 3.12. So sánh bộ nhớ và số lƣợng các mục

CSDL

So sánh

MINE_FWUIs FAST_MINE_FWUIs

Số lƣợng mục

Bộ nhớ

Số lƣợng mục

275.539 86.837 SALE-FACT-1997 13,52 MB 4,65 MB

Bộ nhớ

783.639 251.395 SALE-FACT-

Số lƣợng mục

1997+1998 38,16 MB 13,46 MB

840.079 269.720 SALE-FACT-SYNC Bộ nhớ 40,92 MB 14,44 MB

Bảng 3.12 thể hiện việc thêm và không thêm các mục thuộc mục cha trên

cây phân cấp giữa hai thuật toán MINE_FWUIs và FAST_MINE_FWUIs. Số

lƣợng mục và dung lƣợng bộ nhớ tăng lên đáng kể sau khi thêm các mục cha

trên cây phân cấp vào CSDL.

Ví dụ với CSDL SALE-FACT-1997, số lƣợng mục ban đầu là 86.837,

sau khi thêm các mục cha là 275.539, nhƣ vậy việc thêm mục cha trên cây

phân cấp làm số lƣợng mục tăng 317%. Tƣơng tự nhƣ vậy, dung lƣợng dữ

liệu là 4,65 MB, sau khi thêm mục cha là 13,52 MB, nhƣ vậy dung lƣợng dữ

liệu tăng 290%.

3.4.2.2. Thực nghiệm với hàm MAX và SUM

Khi sử dụng hàm MAX hoặc SUM để xác định trọng số và số lƣợng của

các mục nút cha sẽ có bốn trƣờng hợp có thể xảy ra gồm: (max, max), (max,

sum), (sum, sum), (sum, max). Trong đó cặp (max, max) nghĩa là sử dụng

94

hàm MAX trong xác định trọng số và số lƣợng, tƣơng tự cho các cặp còn lại.

Trong mục này, luận án thống kê số lƣợng và tỉ lệ G-FWUI (Generalized

FWUI: là các FWUI chứa ít nhất một mục cha trên cây phân cấp) trên CSDL

SALE-FACT-SYNC với 02 ngƣỡng minwus khá nhỏ là 0,001% và 0,003%.

Đồng thời, so sánh số lƣợng và tỉ lệ G-FWUI khai thác đƣợc khi sử dụng cặp

hàm (max, max) và (sum, sum) khi xác định trọng số của các mục cha và số

lƣợng của các mục cha trong từng giao dịch.

minwus = 0,001%

minwus = 0,003%

G-FWUI

G-FWUI

Số

cấp

(max, max)

(sum, sum)

(max, max)

(sum, sum)

%

Số lƣợng %

Số lƣợng %

Số lƣợng %

Số lƣợng

0

1559

102

3 65,57% 4.528 73,99%

5.993

62,3%

818

87,53%

1.719

4 92,84% 21.783 95,48% 34.476 90,50% 4.128 97,52%

6.821

5 98,49% 103.292 99,16% 185.371 97,88% 1.906 99,43% 30.612

6 98,97% 151.435 99,43% 274.248 98,58% 26.580 99,62% 45.827

Bảng 3.13. Thực nghiệm trên CSDL SALE-FACT-SYNC

Số liệu thực nghiệm từ bảng 3.13 với CSDL SALE-FACT-SYNC cho

thấy cây có độ cao càng lớn thì số lƣợng các FWUI khai thác đƣợc càng lớn,

điều này là hợp lý do càng có nhiều mục cha đƣợc thêm vào CSDL hơn.

Tƣơng tự nhƣ thế, số lƣợng G-FWUI cũng đƣợc khai thác nhiều hơn.

So sánh tỉ lệ và số lƣợng G-FWUI khai thác đƣợc khi sử dụng cặp hàm

(sum, sum) và (max, max) cũng có sự khác biệt đáng kể, trong đó số lƣợng

khi sử dụng cặp hàm (sum, sum) lớn hơn khá nhiều so với cặp hàm (max,

max) trong cùng một ngƣỡng phổ biến wus. Ví dụ với wus = 0,003% và cây

phân cấp có sáu cấp, số lƣợng G-FWUI khi sử dụng cặp hàm (max, max) là

26.580, khi sử dụng cặp hàm (sum, sum) là 45.827. Do khi sử dụng cặp hàm

95

(sum, sum) sẽ tạo ra các mục cha có số lƣợng và trọng số lớn hơn khi sử dụng

cặp hàm (max, max), nên các mục nút cha sẽ tạo ra nhiều G-FWUI hơn khi

kết hợp với các mục trong CSDL có trọng số và số lƣợng nhỏ. Đây là lý do

mà sử dụng cặp hàm (sum, sum) sẽ tạo ra nhiều G-FWUI nhất so với các cặp

hàm còn lại.

Tùy theo CSDL thực tế nhƣ thế nào mà việc xác định trọng số hay số

lƣợng của các mục nút cha sẽ sử dụng cặp hàm nào trong bốn cặp trên cho

phù hợp.

3.4.2.3. So sánh thời gian

Kết quả thực nghiệm trên ba CSDL cho trong Bảng 3.10 với thuật toán

MINE_FWUIs khi sử dụng các cấu trúc DBV, MBiS, EDBV và EIWS đƣợc

DBV

308,02

MBiS

234,82

EDBV

chỉ ra trong các hình 3.10-3.12:

) s ( e m

174,82 156,32

EIWS

i t

350 300 250 200 150 100 050 000

000

000

000

000

000

000 minwus (%)

2634,16 2228,732

Hình 3.10. So sánh thời gian trên CSDL SALE-FACT-1997

) s ( e m

DBV MBiS SDBV EIWS

i t

1028,981 899,458

3000 2500 2000 1500 1000 500 0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

96

Hình 3.11. So sánh thời gian trên CSDLSALE-FACT-1997+1998

3000

DBV

2757,776

2500

MBiS

2109,512

2000

EDBV

1500

) s ( e m

1292,55

i t

EIWS

1000

910,23

500

0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

Hình 3.12. So sánh thời gian trên CSDL SALE-FACT-SYNC

Hình 3.10-3.12 so sánh thời gian chạy của bốn cấu trúc DBV, MBiS,

EDBV và EIWS với thuật toán MIN_FWUIs. Kết quả thực nghiệm chỉ ra

rằng thuật toán MINE_FWUIs hiệu quả nhất khi sử dụng cấu trúc EIWS. Ví

dụ, CSDL SALE-FACT-1997, với ngƣỡng minwus = 0,01%, thời gian chạy

với DBV, MBiS, EDBV và EIWS lần lƣợt là 308,02s, 234,82s, 174,82s và

156,32s. Nhƣ vậy EIWS nhanh hơn EDBV, MBiS vàDBV lần lƣợt là 1,12;

1,34 và 1,76 lần.

Cũng nhƣ các kết quả thực nghiệm trong chƣơng 2, các cấu trúc IWS và

MBiS có hiệu quả trên CSDL thƣờng và CSDL thƣa. Do đó đối với khai thác

tập mục phổ biến trên CSDL số lƣợng có sự phân cấp mục cũng có kết quả

tƣơng tự. Ngoài ra, ta có thể thấy thời gian khai thác FWUI trên CSDL số

lƣợng có sự phân cấp lớn hơn so với trên CSDL số lƣợng thông thƣờng (cùng

so sánh trên các CSDL SALE-FACT) do việc thêm các mục nút cha trên cây

phân cấp vào CSDL và phải xác định trọng số, số lƣợng cho các mục này.

Đồng thời trong quá trình khai thác luôn phải kiểm tra mối quan hệ cha con

giữa các mục trong tập mục mới tạo thành. Mặt khác, sau khi thêm các mục

nút cha vào CSDL, CSDL mới tạo thành cũng lớn hơn CSDL gốc do đó cũng

cần nhiều thời gian hơn để khai thác trên CSDL mới so với CSDL gốc.

Kết quả thực nghiệm với thuật toán FAST_MINE_FWUIs và

97

MINE_FWUIs đƣợc trình bày qua các Hình 3.13-3.15:

200

MINE_FWUIs- EIWS

156,321

150

FAST_MINE_FWUIs-EIWS

100

) s ( e m

50

i t

45,563

0

0.3

0.2

0.03

0.01

0.1

0.06 minwus(%)

1000

MINE_FWUIs-EIWS

393,452

800

FAST_MINE_FWUIs-EIWS

600

400

899,458

Hình 3.13. So sánh thời gian trên CSDL SALE-FACT-1997

) s ( e m

i t

200

0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

1500

MINE_FWUIs - EIWS

495,872

1000

FAST_MINE_FWUIs -EIWS

Hình 3.14. So sánh thời gian trên CSDL SALE-FACT-1997+1998

) s ( e m

1021,441

i t

500

0

0.3

0.2

0.1

0.06

0.03

0.01

minwus(%)

Hình 3.15. So sánh thời gian trên CSDL SALE-FACT-SYNC

Hình 3.13-3.15 chỉ ra sự hiệu quả của thuật toán FAST_MINE_FWUIs

so với MINE_FWUIs khi cùng sử dụng cấu trúc EIWS. Điều này thể hiện các

ƣu điểm của việc không chèn thêm mục cha vào CSDL và xác định nhanh

mối quan hệ cha con của tập mục tạo thành từ hai tập mục trong cùng một lớp

tƣơng đƣơng trên HIT-tree. Cụ thể ta có kết quả đối với CSDL SALE-FACT-

98

1997 nhƣ trong Bảng 3.14 sau đây:

Bảng 3.14. So sánh thời gian chạy trên CSDL SALE-FACT-1997

MINE_FWUIs FAST_MINE_FWUIs Thuật toán

DBV MBiS EDBV EIWS EDBV EIWS minwus

0,3% 18,41 16,68 11,68 6,21 4,68 2,33

0,2% 45,59 33,53 21,53 12,38 11,53 6,43

0,1% 57,26 42,03 26,03 19,32 17,03 10,12

0,06% 71,82 60,92 30,923 28,41 24,92 14,24

0,03% 121,46 90,76 52,76 45,46 30,76 18,54

0,01% 308,02 234,82 174,13 156,32 90,65 45,56

Từ bảng 3.14, với minwus = 0,01% thuật toán FAST_MINE_FWUIs với

cấu trúc EDBV có thời gian chạy là 90,65s nhanh hơn thuật toán

MINE_FWUIs (174,13s) là 1,93 lần. Điều này cho thấy tính hiệu quả của việc

không thêm mục cha vào CSDL và việc xác định nhanh mối quan hệ cha con

của các mục trong tập mục tạo thành từ hai tập mục trong cùng một lớp tƣơng

đƣơng của HIT-tree.

Bên cạnh đó, cấu trúc EIWS cho thấy hiệu quả khá tốt so với các phƣơng

pháp khác. Ví dụ với minwus = 0,01%, thuật toán FAST_MINE_FWUIs với

cấu trúc EDBV có thời gian chạy là 90,65s, với cấu trúc EIWS có thời gian

chạy là 45,56s. Nhƣ vậy sử dụng cấu trúc EIWS nhanh hơn 49,8% so với cấu

trúc EDBV.

Các kết quả thực nghiệm về mặt thời gian trên đã cho thấy thuật toán

FAST_MINE_FWUIs nhanh hơn hẳn thuật toán MINE_FWUIs trong khai

thác tập mục phổ biến trên CSDL số lƣợng có sự phân cấp mục. Điều này

chứng tỏ các cải tiến đã trình bày trong phần 3.3 của chƣơng 3 này là có hiệu

99

quả rõ rệt.

3.5. Kết luận chƣơng

Chƣơng này của luận án đề xuất hai cấu trúc EDBV và EIWS với các

phần tử là các LI, đây là các mở rộng của DBV và IWS. Đồng thời đề xuất sử

dụng mảng MAP định nghĩa trƣớc vị trí các bit 1 của các số nguyên hai byte

và sử dụng các phép dịch và AND bit để “cắt” các word (hai byte) từ các LI

để ánh xạ vào mảng MAP để tính tidset của các tập mục giúp tính nhanh wus

của chúng. Các kết quả thực nghiệm từ Hình 3.10-3.12 đã cho thấy hiệu quả

của EIWS và EDBV đối với các cấu trúc trƣớc đó trên ba CSDL thực nghiệm

lấy từ bản Foodmart2000 của SQL2000.

Bên cạnh đó, chƣơng này đề xuất hai mệnh đề nhằm tối ƣu bộ nhớ và tiết

kiệm thời gian khai thác FWUI trên HQDB. Thứ nhất, Mệnh đề 3.2 đƣa ra

cách xác định tidset mục cha thông qua tidset của các mục con ở nút lá trên

cây phân cấp. Bằng mệnh đề này, việc khai thác trên HQDB không tốn thời

gian thêm mục cha vào các giao dịch của HQDB nhƣ các phƣơng pháp trƣớc

đây và đồng thời không tốn bộ nhớ để lƣu trữ các mục cha này trong CSDL,

điều này thật sự có hiệu quả, nhất là trên các CSDL có nhiều cây phân cấp và

độ sâu của các cây phân cấp là lớn. Thứ hai, Mệnh đề 3.3 chứng minh việc

xác định trong tập mục mới tạo thành từ hai tập mục cùng lớp tƣơng đƣơng

trên HIT - tree bằng cách kiểm tra mối quan hệ của đúng một cặp mục cuối

của tập mục mới. Trong khi các phƣơng pháp trƣớc đây kiểm tra 2 (m - 1)

cặp với m là số lƣợng mục của tập mục cần kiểm tra. Kết quả thực nghiệm từ

Hình 3.13 - 3.15 cho thấy hiệu quả khi áp dụng hai mệnh đề đề xuất trong

100

chƣơng này.

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN

Các kết quả đạt được

Luận án đã khảo sát các nghiên cứu đã có về khai thác tập mục phổ biến

trên CSDL, đặc biệt là khai thác FWI và FWUI trên CSDL số lƣợng và khai

thác FI trên CSDL có sự phân cấp các mục. Trên cơ sở đó, luận án đề xuất

cấu trúc MBiS [I], cấu trúc IWS [II] cấu trúc DTab [IV] để khai thác hiệu quả

tập mục phổ biến trên CSDL số lƣợng. Tiếp đến, luận án đề xuất bài toán khai

thác tập mục phổ biến trên CSDL số lƣợng có sự phân cấp các mục. Luận án

đề xuất một số cải tiến nhƣ tính tidset của mục cha dựa trên tidset các mục

con, cấu trúc EDBV, EIWS là các mở rộng của các cấu trúc DBV và IWS áp

dụng trong khai thác hiệu quả tập mục trên CSDL số lƣợng có sự phân cấp

các mục. Các kết quả nghiên cứu nêu trên đã đƣợc công bố trên các tạp chí và

hội thảo trong nƣớc và quốc tế uy tín.

Đối với khai thác tập mục trên CSDL số lƣợng, các cấu trúc dữ liệu đƣợc

đề xuất trong luận án là IWS và MBiS là các cấu trúc mới theo hƣớng tiếp cận

bit-vector, cải tiến hiệu quả rõ rệt so với các cấu trúc đã có nhƣ BitTable hay

DBV về bộ nhớ sử dụng cũng nhƣ thời gian xử lý. Bên cạnh đó, đối với cấu

trúc IWS, luận án đề xuất sử dụng một mảng MAP định nghĩa trƣớc vị trí bit

1 trong các phần tử của cấu trúc để tính nhanh wus (đối với khai thác FWUI)

và ws (đối với khai thác FWI) trên CSDL số lƣợng. Đồng thời luận án đề xuất

cấu trúc DTab và DHeap đối với khai thác Top-rank-k tập mục phổ biến trên

CSDL số lƣợng. Hiệu quả của các cấu trúc này đƣợc minh họa cụ thể qua các

kết quả thực nghiệm trong chƣơng 2.

Đối với khai thác tập mục trên CSDL số lƣợng có sự phân cấp các mục,

hai cấu trúc EDBV và EIWS là mở rộng của các cấu trúc DBV và IWS tƣơng

ứng, bằng cách sử dụng các phần tử là các LI. Luận án đƣa ra giải pháp sử

dụng các phép dịch bit và AND bit để vẫn sử dụng đƣợc mảng MAP nhƣ đối

101

với cấu trúc IWS giúp tính nhanh wus (đối với khai thác FWUI) và ws (đối

với khai thác FWI). Bên cạnh đó, luận án đề xuất một số mệnh đề nhằm xác

định tidset của các mục cha thông qua tidset của mục con trên cây phân cấp

và xác định nhanh mối quan hệ cha con của các mục trong một tập mục để

giảm bộ nhớ lƣu trữ CSDL và tăng tốc tính toán cho bài toán khai thác FWUI

trên HQDB. Các kết quả thực nghiệm trong chƣơng 3 đã cho thấy sự hiệu quả

của các đề xuất đối với bài toán này.

Hướng phát triển

Luận án đã nghiên cứu các phƣơng pháp khai thác tập mục phổ biến trên

CSDL số lƣợng và CSDL số lƣợng có sự phân cấp các mục. Luận án đề xuất

một số thuật toán với các cấu trúc dữ liệu mới hiệu quả hơn các phƣơng pháp

khai thác tập phổ biến đã có. Tuy nhiên, các bài toán trên CSDL số lƣợng có

sự phân cấp các cần đƣợc mở rộng và nghiên cứu tiếp nhƣ:

1. Giải quyết bài toán khai thác tập mục phổ biến đóng, tập phổ biến tối đại

đối với HQDB.

2. Nghiên cứu các hƣớng tiếp cận hiệu quả hơn trong khai thác tập mục phổ

biến trên HQDB dày.

3. Mở rộng bài toán khai thác FWUI trên HQBD lớn, khi đó cần sử dụng các

hệ thống tính toán hiệu năng cao để giải quyết bài toán với các mô hình

song song hóa thuật toán một cách hợp lý.

4. Giải quyết bài toán khai thác tập mục phổ biến với CSDL số lƣợng có

nhiều tham số (trọng số, thời gian, giá trị, mức độ yêu thích, v.v…) của

102

các mục.

DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ

LIÊN QUAN ĐẾN LUẬN ÁN

[I] Nguyen Duy Ham, Vo Dinh Bay, Nguyen Thi Hong Minh, Tzung Pei

Hong (2015), “MBiS: an efficient method for mining frequent weighted

utility itemsets from QDB”, Journal of Computer Science and Cybernetics,

31(1), pp.17–30.

[II] Nguyen Duy Ham, Bay Vo, Nguyen Thi Hong Minh, Tzung Pei Hong

(2015), “An improved algorithm for mining frequent weighted itemsets”,

in Proc. of the International conf on IEEE System, Man, Cybernetics,

Hong Kong, pp. 2579–2584.

[III] Nguyễn Duy Hàm, Võ Đình Bảy, Nguyễn Thị Hồng Minh (2015), “Thuật

toán hiệu quả khai thác tập phổ biến từ cơ sở dữ liệu số lƣợng có sự phân

cấp mục”, Hội nghị khoa học quốc gia lần thứ 8:“Nghiên cứu cơ bản và

ứng dụng CNTT”, Viện CNTT – Đại học Quốc gia Hà Nội, tr. 679-686.

[IV] Nguyễn Duy Hàm, Võ Đình Bảy, Nguyễn Thị Hồng Minh (2015),

“Thuật toán hiệu quả khai thác Top – rank – k tập phổ biến trọng số hữu

ích”, Hội thảo quốc gia lần thứ 18: “Một số vấn đề chọn lọc về CNTT và

TT”, tr. 312–317.

[V] Nguyen Duy Ham, Bay Vo, Nguyen Thi Hong Minh, Witold Pedrycz (2016), “An Efficient Algorithm for Mining Frequent Weighted Itemsets

using Interval Word Segments”, Applied Intelligence, pp.1 -13.

103

[1] Agrawal, R., & Srikant, R. (1994). Fast algorithms for minings association rules.

Proc. of the 20th International Conf on Very Large Data Bases, pp. 487-499.

[2] Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules

between sets of items in large databases. Proc. of the 1993 ACM SIGMOD

International conference on Management of data, 22(2), 207-216.

[3] Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., & Verkamo, I. A. (1996).

Fast discovery of association rules. Proc.of Conf on Advances in Knowldege

Discovery and Data Mining, pp. 307-328.

[4] Ali, Z. S., & Rathore, Y. (2014.). A effective and efficient algorithm for cross

level frequent pattern mining. Proc. of Conf on Advances in Engineering and

Technology Research, pp. 1-6.

[5] Baralis, E., Cagliero, L., Cerquitelli, T., & Garza, P. (2012). Generalized

association rule mining with constraints. Information Science (Elsevier

Science Inc), 194, pp. 68-84.

[6] Baralis, E., Cagliero, L., Cerquitelli, T., D’Elia, V., & Garza, P. (2014).

Expressive generalized itemsets. Information Sciences, 278, pp. 327-343.

[7] Cai, C. H., Fu, A. C., Cheng, C. H., & Kwong, W. W. (1998). Mining

association rules with weighted items. Proc. of Conf on IEEE Intelligence

Database Engineering and Applications Symposium, pp. 68-77.

[8] Deng, H. Z., & Fang, G. (2007). Mining top-rank-k-frequent patterns. Proc. of

Conf on Machine Learning and Cybernetics, pp. 1763-1768.

[9]

Deng, H.-Z. (2012). A new algorithm for fast mining frequent itemsets using

N-list. Science china information science, 55(9), pp. 2008-2030.

[10] Deng, H.-Z., & Long, S. (2014). Fast mining frequent itemsets using

Nodesets. Expert Systems with Applications, 41(10), pp. 4505-4512.

[11] Deng, Z.-H. (2014). Fast mining top-rank-k - frequent patterns by using Node-

list. Expert Systems with Applications, pp. 1763-1768.

104

TÀI LIỆU THAM KHẢO

[12] Deng, Z.-H., & Lv, S.-L. (2015). PrePost+: An efficient N-Lists-based

Algorithm for Mining Frequent Itemsets via Children-Parent Equivalence

Pruning. Expert Systems with Applications, 42(13), pp. 5424-5432.

[13] Dong, J., & Han, M. (2007). BitTable-FI An efficient mining frequent itemsets

algorithm. Knowledge-Based Systems, 20(4), pp. 329-335.

[14] Elena, B., Luca, C., Tania, C., & Paolo, G. (2012). Generalized association rule

mining with constraints. Information Science (Elsevier Science Inc), 194, 68-84.

[15] Elena, B., Luca, C., Tania, C., Vincenzo, D., & Paolo, G. (2014). Expressive

generalized itemsets. Information Sciences, 278, 327-343.

[16] Erwin, A., Gopalan, R. P., & Achuthan, R. N. (2007). CTU-Mine: An efficient

hight utility itemset mining algorithm using the pattern growth approach.

Computer and Informaition Technology, CIT, pp. 71-76.

[17] Fang, G., & Deng, Z.-H. (2008). VTK: Vertical mining of top-rank-k frequent

pattern. Proc. of the Conf on Fifth International Fuzzy Systems and

Knowdelge Discovery 2008, pp. 620 - 624.

[18] Grahne, G., & Zhu, J. (2005). Fast algorithms for frequent itemset mining

using FP-trees. Proc. of Conf on IEEE Transactions on Knowledge anh Data

Mining and Data Engineering, 17(10), pp. 1347-1362.

[19] Han , J., Pei , J., & Yin, Y. (2000). Mining frequent patterns without candidate

generation. Proc. of conf on ACM SIGMOD Management of Data, pp. 1-12.

[20] Han, J., & Fu, F. (1995). Discovery of multiple-level association rules from

large databases. Proc. of 21th conf on Very Largr Databases, (pp. 420-431).

Zurich, pp. 420-431.

[21] Khan, M. S., Muyeba, M., & Coenen, F. (2008). A weighted utility framework

for mining association rules. Proc. of conf on IEEE European Modeling

Symposium, pp. 87-92.

[22] Lan, C. G., Hong, P. T., & Lee, Y. H. (2014). An efficient approach for

finding weighted sequential patterns from sequence databases. Applied

Intelligence, 41(2), pp. 439-452.

105

[23] Lan, C. G., Hong, P. T., Lee, Y. H., Wang, L. S., & Tsai, W. C. (2013).

Enhancing the efficiency in mining weighted frequent itemsets. Proc. of IEEE

Internationnal conf on System, Man, Cybernetics (SMC), pp. 1104-1108.

[24] Lan, G. C., Hong, P. T., & Tseng, V. S. (2011). Discovery of hight utility

itemsets from on-shelf time periods of products. Expert Systems with

Applications, 38(6), pp. 5851-5857.

[25] Le, B., Cao, T. A., Nguyen, H., & Vo, B. (2009). A novel algorithm for

mining hight utility itemsets. Proc. of the Conf on 1st Asian Inteleigent

Information and Databases systems, pp. 13-16.

[26] Le, B., Vo, B., Le, Q., & Le, T. (2015). Enhancing the mining top-rank-k

frequent patterns. Proc. of IEEE internationnal conf on System, Man,

Cybernetics (SMC), pp. 2008-2012

[27] Le, T., & Vo, B. (2015). An N-list-based algorithm for mining frequent closed

patterns. Expert Systems with Applications, 42(19), pp. 6648-6657.

[28] Lee, Y. C., Hong, P. T., & Chen C, H. (2010). Mining Generalized

Association Rules with Quantitative Data under Multiple Support Constraints,

Computational Collective Intelligence. Technologies and Applications Lecture

Notes in Computer Science, 6422, pp. 224-231.

[29] Lin, W. C., Lan, C. G., & Hong, P. T. (2015). Mining hight utility itemsets for

transaction deletion in a dynamic databases. Intelligence Databases Analys,

pp. 43-55.

[30] Liu, B., Hsu, W., & Ma, Y. (1999). Mining association rules with multiple

mining supports. Proc. of International Conf on Knowdelge Discovery and

Data Mining, pp. 337-341.

[31] Louie, E., & Lin, T. (2000). Finding Association Rules Using Fast Bit

Computation: Machine-Oriented Modeling. Foundations of intelligent system

International Symposium, ISMIS , pp. 497-505.

[32] Ramkumar, G. D., Ranka, S., & Tsur, S. (1998). Weighted Association Rules:

Model and Algorithm. Proc. of conference on Knowledge Discovery and Data

Mining - KDD, pp. 1-13.

106

[33] Song, W., Yang, B., & Xu, Z. (2008). Index-BitTableFI: An improve

algorithm for mining frequent itemsets. Knowledge - Based System, 21(6), pp.

507-513.

[34] Tao, F., Murtagh, F., & Farid, M. (2003). Weighted Association Rules mining

using weighted support and signifocance framework. Proc. of conference on

ACM SIGKDD, pp. 661-666.

[35] Tseng, M. C., & Lin, W. Y. (2007). Efficient mining of generalized

association rules with non-uniform minimum support. Data & Knowledge

Engineering, 66(1), pp. 41-64.

[36] Vo, B., & Le, B. (2009). Fast Algorithm for Mining Generalized Association

Rules. International Journal of Database and Application, 2(3), pp. 1-12.

[37] Vo, B., Coenen, F., & Le, B. (2013). A new method for mining Frequent

Weighted Itemsets base on WIT-trees. Expert systems with Applications,

40(4), pp. 1256-1264.

[38] Vo, B., Hong, P. T., & Le, B. (2012). DBV-Miner: A Dynamic Bit - Vector

approach for fast mining frequent close itemsets. Expert Systems with

Applications, 39(8), pp. 7196-7206.

[39] Vo, B., Le, B., & Jason, J. J. (2012). A Tree-based Approach for Mining

Frequent Weighted Utility Itemsets. Computational Collective Intelligence

Tecnologies and Applications, 7653, pp. 114-123.

[40] Vo, B., Le, T., Coenen, F., & Hong, P. T. (2016). Mining frequent itemsets

using the N-list and subsume concepts. International Journal of Machine

Learning and Cybernetics, 7(2), pp 253-265

[41] Vo, B., Nguyen, Y., & Nguyen, D. (2013). Mining frequent weighted closed

itemsets. Proc. of Conf on Advanced Computational Methods for Knowledge

Engineering, pp. 379-390.

[42] Wang, W., Yang, J., & Yu, P. (2000). Efficient mining of weighted

association rules (WAR). Proc. of the conference on ACM SIGKDD

Knowledge Discovery and Data Mining, pp. 270-274.

107

[43] Yang, J. K., Hong, P. T., Lan, C. G., & Chen, M. Y. (2014). A two phase

approach

for mining weighted partial periodic pattern. Engineering

Applications of Artificial Intelligence, 30(4), pp. 225-234.

[44] Yun, U., & Eunchul, Y. (2014). An efficient approach for mining weighted

approximate closed

frequent patterns considering noise constraints.

International Journal of Uncertainty Fuzziness and Knowledge-Based Systems

22(6), pp. 879-912.

[45] Yun, U., & Leggett, J. J. (2005). WFIM: Weighted Frequent Itemset Mining

with a weight range and a minimum weight. In: Proceedings of SIAM

International Conference on Data Mining, pp. 636-640.

[46] Yun, U., & Leggett, J. J. (2006). WSpan: Weighted Sequential pattern mining

in large sequence databases. Pro. of IEEE International Conference on

Intelligent Systems, pp. 512-517.

[47] Yun, U., & Pyun, G. (2015). Efficient mining of robust closed weighted

sequential patterns without information loss. International Journal on

Artificial Intelligence Tools, 24(1), pp. 1-28.

[48] Yun, U., Lee, G., & Ryu, H. K. (2014). Mining maximal frequent patterns by

considering weight conditions over data streams. Knowl.-Based Syst. 55, pp.

49-65.

[49] Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE

transactions on Knowledge and Data Engineering, 12(3), pp. 372-390.

[50] Zaki, M. J., & Gouda, K. (2003). Fast vertical mining using Diffset. Proc. of

the ninth ACM SIGKDD International conf on Knowledge Discovery and

Data Mining, pp. 327-335.

108