Luận văn tốt nghiệp: Phát hiện luật bằng cách sử dụng siêu phằng tối ưu theo hướng tiếp cận thô ppt

Luận văn tốt nghiệp

Phát hiện luật bằng cách sử dụng siêu

phằng tối ưu theo hướng tiếp cận thô

TÓM TĂT KHOÁ LUẬN TỐT NGHIỆP

Cùng với sự phát triển của Công Nghệ Thông Tin ngày nay, khai phá tri thức

trong các cơ sở dư liệu lớn là một trong nhưng lĩnh vực được rất nhiều nhà nguyên cứu

và ứng dụng tin học đặc biệt quan tâm. Việc nguyên cứu những phương pháp có thể tự

động phát hiện những tri thức mới trong cơ sở dư liệu trên máy tính đã tỏ ra thực sự

hữu ích trong việc hỗ trợ quyết định cho con người.

Hiện nay, trên thế giới có rất nhiều thuật toán khai phá tri thức bằng cách phân

lớp và rời rạc dữ liệu như: Sử dụng cây quyết định, phương pháp thống kê, các mạng

nơ ron, thuật toán di truyền,...Trong một vài năm gần đây, lý thuyết tâp thô được nhiều

nhóm nguyên cứu hoạt động trong lĩnh vực tin học nói chung và khai phá tri thức nói

riêng nguyên cứu và áp dụng trong thực tế. Lý thuyết tập thô được xây dựng trên nền

tảng toán học vững chắc giúp cung cấp những công cụ hữu ích để giải quyết những bài

toán phân lớp dữ liệu và khai phá luật,...Với đặc tính có thể xử lý được những dữ liệu

mơ hồ, không chắc chắn tập thô tỏ ra rất hữu ích trong việc giải quyết những bài toán

thực tế. Từ những bảng dữ liệu lớn với dữ liệu dư thừa, không hoàn hảo, dữ liệu liên

tục, hay dữ liệu dưới dạng ký hiệu lý thuyết tập thô cho phép khai phá tri thức từ

những khối dữ liệu này nhằm phát hiện những luật tiềm ẩn từ khối dữ liệu này.

Trong khoá luân tốt nghiệp chúng tôi đã trình bày một số phương pháp rời rạc

hoá dữ liệu theo hướng tiếp cận tập thô. Và xây dựng chương trình thử nghiệm: phát

hiện luật bằng cách sử dụng siêu phẳng tối ưu theo hướng tiếp cân tập thô. Chương

trình được xây dựng để thử nghiệm trên bộ dữ liệu chứa thông tin về 768 bệnh nhân bị

bệnh tiểu đường cung cấp bởi tổ chức “National Institute of Diabetes and Digestive

and Kidney Diseases”. Từ đó xây dựng hệ thống các luật dựa trên cây quyết định dùng

để hỗ trợ việc khám bệnh của các bác sĩ.

MỤC LỤC

MỤC LỤC .......................................................................................................................2

PHẦN MỞ ĐẦU .............................................................................................................5

Chương 1 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC ...............................................8

1.1 . Khai phá tri thức....................................................................................................8

1.1.1. Định nghĩa khai phá tri thức.........................................................................8

1.1.2. Các giai đoạn của quá trình khai phá tri thức...............................................8

1.1.3. Khai phá dữ liệu..........................................................................................10

1.2 . Khai phá tri thức theo cách tiếp cận tập thô........................................................12

1.2.1. Một số khái niệm ........................................................................................12

1.2.1.1. Khái niệm hệ thông tin ..................................................................12

1.2.1.2. Khái niêm về bảng quyết định.......................................................13

1.2.1.3. Khái niệm quan hệ không phân biệt được trong hệ thông tin. ......15

1.2.1.4. Khái niệm tập các nhát cắt, nhát cắt trong bảng quyết định..........16

1.2.1.5. Tập thô trong không gian xấp xỉ. ..................................................17

1.2.2. Khai phá tri thức theo cách tiếp cận tập thô. ..............................................19

1.2.2.1. Sự rời rạc hoá dữ liệu theo cách tiếp cận tập thô. .........................19

1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô.............................................19

1.2.2.3. Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô. .......20

1.2.2.4. Khám phá mẫu trong hệ thông tin.................................................20

1.3 . Kết luận. ..............................................................................................................21

Chương 2 KHAI PHÁ LUẬT KẾT HỢP...................................................................22

2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu. ..........................................................22

2.1.1. Bài toán xuất phát.......................................................................................22

2.1.2. Mô hình hoá bài toán..................................................................................22

2.1.3. Thuật toán khai phá luật kết hợp. ...............................................................25

2.1.3.1. Tập phổ biến..................................................................................25

2.1.3.2. Khai phá luật dựa trên tập mục phổ biến.......................................25

2.1.4. Kết luận.......................................................................................................28

2.2 . Sinh cây quyết định từ hệ thông tin.....................................................................29

2.2.1. Thuật toán học cây quyết định....................................................................29

2.2.2. Một số phương pháp giải quyết vấn đề rời rạc hoá. ...................................35

2.2.2.1. Maximal Discernibility (MD) Heuristic........................................35

2.2.2.2. Sự rời rạc hoá định nghĩa bằng siêu phẳng. ..................................36

2.2.2.3. Những tính chất của phương thức MD..........................................39

2.2.2.4. Xây dựng cây quyết định không đối xứng. ...................................43

2.2.3. Kết luận.......................................................................................................50

Chương 3 CHƯƠNG TRÌNH THỬ NGHIỆM. .........................................................51

3.1 . Mô tả dữ liệu. ......................................................................................................51

3.2 . Xây dựng chương trình. ......................................................................................53

3.3 . Kết quả thử nghiệm. ............................................................................................57

3.4 . Nhận xét. .............................................................................................................61

KẾT LUẬN. ..................................................................................................................62

Tài liêu tham khảo:........................................................................................................63

CÁC KÝ HIỆU SỬ DỤNG TRONG LUẬN VĂN

Ký hiệu Mô tả

A Hệ thông tin hay bảng quyết định

A, B Tập các thuộc tính trong hệ thông tin

D Tập thuộc tính quyết định trong hệ thông tin

a Một thuộc tính điêu kiện trong hệ thông tin

Va Tập giá trị của thuộc tính điều kiện a

U Tập tất cả các đối tượng

∅ Tập rỗng

⊆ Bị chứa trong

∈ Thuộc (phần tử thuộc tập hơp)

≥ Lớn hơn hoặc bằng

≤ Nhỏ hơn hoặc bằng

≠ Khác

∪, ∩ phép lấy giao và hợp của tập hợp

PHẦN MỞ ĐẦU

Trong một vài năm gần đây, ngành công nghệ thông tin trên toàn thế giới đã

phát triển mạnh mẽ với một tốc độ rất nhanh. Song song với điều đó chúng ta cũng

phải đối mặt với một thách thức mới là sự bùng nổ về lượng thông tin. Tuy nhiên, một

thực tế diễn ra rất phổ biến là mặc dù có một lượng dữ liệu rất lớn nhưng thông tin mà

thực sự chúng ta có là rất ít, những hiểu biết thực sự của chúng ta về lượng dữ liệu mà

chúng ta có còn rất hạn chế.

Xuất phát từ thực tế đó mà trong một vài năm gần đây các nhà nguyên cứu và

ứng dụng tin học phải nguyên cứu, tìm kiếm những phương pháp mới để khai thác triệt

để nhưng thông tin có trong cơ sở dữ liệu. Từ cuối những năm của thập kỷ 1980 khái

niệm phát hiện tri thức trong cơ sở dữ liệu lần đầu tiên được nói đến, đây là quá trình

phát hiện tri thức tiềm ẩn, không biết trước và hữu ích trong các cơ sở dữ liệu lớn.

Khắc phục hạn chế của những mô hình cơ sở dữ liệu truyền thống chỉ với

những công cụ truy vấn dữ liệu không có khả năng tìm kiếm các thông tin mới, các

thông tin tiềm ẩn trong cơ sở dữ liệu. Khai phá tri thức trong cơ sở dữ liệu là một quá

trình có thể tìm ra những thông tin mới, những thông tin hữu ích, và tiềm ẩn trong cơ

sở dữ liệu. Quá trình phát hiện tri thức gồm nhiều giai đoạn, trong đó giai đoạn khai

phá dữ liệu là quan trọng nhất. Đây là giai đoạn chính tìm ra những thông tin mới

trong cơ sở dữ liệu. Quá trình phát hiện tri thức là sự tiếp thu, sử dụng và phát triển các

thành tựu của nhiều lĩnh vực nguyên cứu ứng dụng tin học trước đó như: lý thuyết

nhận dạng, hệ chuyên gia, trí tuệ nhân tạo, thống kê, v.v.

Từ đầu những năm 80 Z. Pawlak đã đề xuất ra lý thuyết tập thô với một cơ sở

toán học rất chắc chắn. Trong những năm gần đây, lý thuyết tập thô được nhiều nhóm

nguyên cứu hoạt động trong lĩnh vực tin học nói chung và khai phá tri thức trong cơ sở

dữ liệu nói riêng nguyên cứu và áp dụng trong thực tế [2,4,6,10,12]. Lý thuyết tập thô

ngày càng được áp dụng rộng rãi trong lĩnh vực phát hiện tri thức. Nó tỏ ra rất hữu ích

trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật và đặc biệt hữu ích

trong các bài toán phải xử lý các dữ liệu mơ hồ, không chắc chắn. Các mối quan hệ

giữa dữ liệu trong mô hình này được biểu diễn qua mối quan hệ “không phân biệt

được”, các tập dữ liệu là mơ hồ, không chắc chắn được biểu diễn thông qua tập xấp xỉ

trên và xấp xỉ dưới của nó. Nhờ vào những điều này mà dữ liệu có thể phân tích và xử

lý bằng những công cụ toán học.

Cụ thể trong lý thuyết tập thô dữ liệu được biểu diễn thông qua hệ thông tin

hay bảng quyết. Từ trong thực tế, với những bảng dữ liệu lớn với dữ liệu không hoàn

hảo, có dữ liệu dư thừa, dữ liệu liên tục hay biểu diễn dưới dạng các ký hiệu, lý thuyết

tập thô cho phép khai phá tri thức trong những cơ sở dữ liệu như thế này nhằm phát

hiện những tri thức tiềm ẩn từ những khối dữ liệu “thô” này. Tri thức tìm được được

thể hiện dưới dạng các luật, các mẫu. Sau khi tìm được những quy luật chung nhất để

biểu diễn dữ liệu, người ta có thể tính toán độ mạnh và độ phụ thuộc giữa các thuộc

tính trong hệ thông tin.