[FONT=Times New Roman]Mở đầu

Hơn một thập niên trở lại đây, khai phá dữ liệu (KPDL) đã trở thành một trong

những hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri

thức. Hàng loạt nghiên cứu, đề xuất ra đời đã được thử nghiệm và ứng dụng thành

công vào đời sống cùng với hơn mười năm lịch sử cho thấy rằng KPDL là một

lĩnh vực nghiên cứu ổn định, có một nền tảng lý thuyết vững chắc chứ không phải

được xem là “sớm nở tối tàn” như một số ít nhà tin học nghi ngờ tại thủa ban đầu

của lĩnh vực này.

KPDL bao hàm rất nhiều hướng tiếp cận. Các kỹ thuật chính được áp dụng

trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực cơ sở dữ liệu (CSDL),

machine learning, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, và tính

toán hiệu năng cao. Các bài toán chủ yếu trong KPDL là phân lớp/dự đoán

(classification/prediction), phân cụm (clustering), khai phá luật kết hợp

(association rules mining), khai phá chuỗi (sequence mining), v.v. Lĩnh vực này

cũng là điểm hội tụ và giao thoa của rất nhiều lĩnh vực khác. KPDL đã và đang

được ứng dụng thành công vào thương mại, tài chính & thị trường chứng khoán,

sinh học, y học, giáo dục, viễn thông, .v.v.

Ý thức được đây là một lĩnh vực nghiên cứu có nhiều triển vọng, tôi đã chọn

hướng nghiên cứu Khai phá song song luật kết hợp mờ cho đề tài luận văn của

mình. Luận văn được xây dựng dựa trên nền các nghiên cứu đã có trong lĩnh vực

khai phá luật kết hợp kể từ năm 1993, đồng thời tôi cũng mạnh dạn trình bày một

vài đề xuất của riêng mình mà hai trong số những đề xuất đó là “nêu lên mối liên

hệ giữa luật kết hợp mờ và lý thuyết tập mờ” và “thuật toán song song khai phá

luật kết hợp mờ”.

Luận văn được tổ chức thành 5 chương như sau:

• Chương I trình bày tổng quan về KPDL như định nghĩa thế nào là KPDL

và khám phá tri thức từ cơ sở dữ liệu, các bước chính trong quá trình khám

phá tri thức. Chương này cũng đề cập đến các kỹ thuật và hướng tiếp cận

chính trong KPDL và phân loại các hệ thống khai phá theo nhiều tiêu chí

khác nhau. Phần cuối của chương này phác họa những ứng dụng chính của - 2 -

lĩnh vực này và những hướng nghiên cứu đang và sẽ được chú trọng trong

thời gian tới.

• Chương II trình bày về bài toán “khai phá luật kết hợp”. Để đi vào những

nghiên cứu cụ thể ở hai chương sau, chương này cung cấp những hiểu biết

cần thiết về bài toán khai phá luật kết hợp. Phần cuối chương sẽ là tổng

hợp những đề xuất chính trong hơn 10 năm lịch sử tồn tại và phát triển của

bài toán này.

• Chương III trình bày về “khai phá luật kết hợp mờ”. Phần đầu của chương

phát biểu lại bài toán khai phá luật kết hợp với thuộc tính số và thuộc tính

hạng mục cùng các phương pháp rời rạc hóa dữ liệu cho bài toán này.

Dạng luật kết hợp này cùng với các phương pháp rời rạc hóa đi kèm có

một vài hạn chế như ngữ nghĩa của luật hay vấn đề “điểm biên gãy”. Luật

kết hợp mờ được đề xuất như một hướng khắc phục các nhược điểm của

bài toán trên. Bên cạnh sự tổng hợp về các nghiên cứu trước đó về dạng

luật này, luận văn cũng nêu lên mối liên hệ giữa luật kết hợp và lý thuyết

tập mờ và giải quyết câu hỏi “tại sao lại chọn phép tích đại số và phép lấy

min cho toán tử T-norm”. Phần cuối của chương này là một đề xuất về

cách chuyển đổi luật kết hợp mờ về dạng luật kết hợp mờ với thuộc tính số

dựa vào ngưỡng wf

tương ứng với các tập mờ f của từng thuộc tính mờ.

• Chương IV tập trung vào bài toán ”khai phá song song luật kết hợp”. Phần

đầu của chương này, luận văn tóm tắt lại các thuật toán đã được đề xuất và

thử nghiệm thành công. Các thuật toán này giống nhau ở một điểm là phải

đồng bộ hóa dù nhiều hay ít trong suốt quá trình tính toán và đây chính là

nhược điểm cần khắc phục. Nắm bắt được tính chất của luật kết hợp mờ,

luận văn đã đề xuất một thuật toán mới theo đó các bộ xử lý (BXL) trong

hệ thống song song hạn chế được tối đa quá trình trao đổi dữ liệu và đồng

bộ hóa. Thuật toán khai phá song song luật kết hợp mờ này được xem là

gần lý tưởng bởi ngoài việc tránh được nhược điểm truyền thông, nó còn

đạt được sự cân bằng tải giữa các BXL nhờ một chiến thuật chia tập thuộc

tính ứng cử viên phù hợp.

• Chương V tổng kết luận văn bằng việc nêu lại những công việc đã thực

hiện và kết quả đạt được của luận văn này. Ngoài ra, chương này cũng đề-

cập những vấn đề chưa được giải quyết hoặc giải quyết thấu đáo trong toàn

luận văn cũng như công việc và hướng nghiên cứu trong tương lai.

Mục lục

Mở đầu .................................................. .................................................. ........... 1

Mục lục .................................................. .................................................. .......... 4

Danh sách hình vẽ .................................................. ........................................... 6

Danh sách bảng biểu .................................................. ........................................ 7

Bảng từ viết tắt .................................................. ................................................ 8

Chương I. Tổng quan về Khai phá dữ liệu .................................................. ...... 9

1.1 Khai phá dữ liệu .................................................. .................................... 9

1.1.1 Tại sao lại Khai phá dữ liệu? .................................................. ......... 9

1.1.2 Định nghĩa Khai phá dữ liệu .................................................. ........ 10

1.1.3. Các bước chính trong Khám phá tri thức (KDD) .......................... 11

1.2 Các hướng tiếp cận và các kỹ thuật áp dụng trong Khai phá dữ liệu .... 12

1.2.1 Các hướng tiếp cận và các kỹ thuật chính trong Khai phá dữ liệu 12

1.2.2 Các dạng dữ liệu có thể khai phá .................................................. . 13

1.3 Ứng dụng của Khai phá dữ liệu .................................................. .......... 14

1.3.1 Ứng dụng của Khai phá dữ liệu .................................................. ... 14

1.3.2 Phân loại các hệ Khai phá dữ liệu .................................................. 14

1.4 Những vấn đề được chú trọng trong Khai phá dữ liệu .......................... 15

Chương II. Luật kết hợp .................................................. ................................ 17

2.1 Tại sao lại luật kết hợp? .................................................. ...................... 17

2.2 Phát biểu bài toán khai phá luật kết hợp ............................................... 18

2.3 Những hướng tiếp cận chính trong khai phá luật kết hợp ..................... 20

Chương III. Khai phá luật kết hợp mờ .................................................. .......... 23

3.1 Luật kết hợp có thuộc tính số .................................................. .............. 23- 5 -

3.1.1 Luật kết hợp có thuộc tính số .................................................. ....... 23

3.1.2 Các phương pháp rời rạc hóa .................................................. ....... 24

3.2 Luật kết hợp mờ .................................................. .................................. 27

3.2.1 Rời rạc hóa thuộc tính dựa vào tập mờ .......................................... 27

3.2.2 Luật kết hợp mờ (fuzzy association rules) ..................................... 29

3.2.3 Thuật toán khai phá luật kết hợp mờ .............................................. 33

3.2.4 Chuyển luật kết hợp mờ về luật kết hợp với thuộc tính số ............ 38

3.2.5 Thử nghiệm và kết luận .................................................. ................ 38

Chương IV. Khai phá song song luật kết hợp mờ ........................................... 39

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

4.1.1 Thuật toán phân phối độ hỗ trợ .................................................. .... 40

4.1.2 Thuật toán phân phối dữ liệu .................................................. ........ 41

4.1.3 Thuật toán phân phối tập ứng cử viên ............................................ 43

4.1.3 Thuật toán sinh luật song song .................................................. ..... 46

4.1.4 Một số thuật toán khác .................................................. ................. 47

4.2 Thuật toán song song cho luật kết hợp mờ ........................................... 47

4.2.1 Hướng tiếp cận .................................................. ............................. 47

4.2.2 Thuật toán song song cho luật kết hợp mờ .................................... 51

4.3 Thử nghiệm và kết luận .................................................. ....................... 52

Chương V. Kết luận .................................................. ...................................... 53

Những vấn đề đã được giải quyết trong luận văn này ................................. 53

Công việc nghiên cứu trong tương lai .................................................. ....... 54

Tài liệu tham khảo .................................................. ......................................... 56