Phân tách cụm danh từ cơ sở tiếng việt sử dụng mô hình crfs

TRƯỜNG …………………. KHOA……………………….

----------

Báo cáo tốt nghiệp

Đề tài:

PHÂN TÁCH CỤM DANH TỪ CƠ SỞ TRIẾNG ViỆT SỬ DỤNG MÔ HÌNH CRFs

Có thể bạn quan tâm!

LỜI CAM ĐOAN

Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.

Học viên

Nguyễn Thanh Huyền

LỜI CẢM ƠN

Trong suốt thời gian học tập, hoàn thành luận văn tôi đã được các Thầy, Cô truyền đạt cho các kiến thức cũng như phương pháp nghiên cứu khoa học rất hữu ích và được gia đình, cơ quan, đồng nghiệp và bạn bè quan tâm, động viên rất nhiều.

Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, người Thầy đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình thực hiện luận văn này.

Cũng qua đây, tôi xin gửi lời cảm ơn đến ban giám hiệu trường Trung cấp kinh tế Hà Nội, nơi tôi đangcông tác đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình làm luận văn tốt nghiệp.

Cuối cùng, tôi xin cảm ơn bố mẹ, anh, chị, chồng, con và các bạn bè, đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn.

Hà Nội, ngày 12 tháng 06 năm 2011

Nguyễn Thanh Huyền

MỤC LỤC

LỜI CAM ĐOAN i

LỜI CẢM ƠN iii

MỤC LỤC iv

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

DANH MỤC CÁC BẢNG vii

DANH MỤC CÁC HÌNH viii

MỞ ĐẦU 1

Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LÝ THUYẾT TẬP THÔ 3

1.1. Giới thiệu về khai phá dữ liệu 3

1.1.1 Khám phá tri thức 3

1.1.2. Khai phá dữ liệu 4

1.2. Ứng dụng của khai phá dữ liệu 5

1.3. Một số phương pháp khai phá dữ liệu thông dụng 6

1.3.1. Phân lớp (Classification) 6

1.3.2. Phân cụm (Clustering) 8

1.3.3. Luật kết hợp (Association Rules) 9

1.4. Lý thuyết tập thô 9

1.4.1. Hệ thông tin 10

1.4.2. Bảng quyết định 10

1.4.3. Quan hệ không phân biệt được 12

1.4.4. Xấp xỉ tập hợp 12

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

Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNH 15

2.1. Tổng quan về cây quyết định 15

2.1.1. Định nghĩa 15

2.1.2. Thiết kế cây quyết định 16

2.1.3. Phương pháp tổng quát xây dựng cây quyết định 18

2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu 19

2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy 20

2.2.1. Tiêu chí chọn thuộc tính phân lớp 20

2.2.2. Thuật toán ID3 21

2.2.3. Ví dụ về thuật toán ID3 23

2.3. Thuật toán xây dựng cây quyết định dựa vào độ phụ thuộc của thuộc tính 28

2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô 28

2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô 28

2.3.3. Tiêu chí chọn thuộc tính để phân lớp 28

2.3.4. Thuật toán xây dựng cây quyết định ADTDA 29

2.3.5. Ví dụ 30

2.4. Thuật toán xây dựng cây quyết định dựa vào Entropy và độ phụ thuộc của thuộc tính 33

2.4.1. Tiêu chí chọn thuộc tính để phân lớp 33

2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] ) 34

2.4.3. Ví dụ 35

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

Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ 40

3.1. Giới thiệu bài toán 40

3.2. Giới thiệu về cơ sở dữ liệu 40

3.3. Cài đặt ứng dụng 41

3.4. Kết quả và đánh giá thuật toán 42

3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data 42

3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data 44

3.4.3. Đánh giá thuật toán 44

3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu 45

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

KẾT LUẬN 47

TÀI LIỆU THAM KHẢO 49

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

CÁC KÝ HIỆU:

S = (U, A) Hệ thông tin

Va Tập các giá trị của thuộc tính a

IND(B) Quan hệ tương đương của tập thuộc tính B [ui]p Lớp tương đương chứa đối tượng ui

U/B Phân hoạch của U sinh ra bởi quan hệ IND(B)

DT=(U,CD) Bảng quyết định

B( X )

POSC (d )

B-Xấp xỉ dưới của X B-xấp xỉ trên của X

Miền C-khẳng định của d

|DT| Tổng số các đối tượng trong DT

|U| Lực lượng của tập U

[U]d Phân hoạch của U sinh ra bởi quan hệ IND(d)

CÁC CHỮ VIẾT TẮT:

ADTDA Algorithm for Buiding Decision Tree Based on Dependency of Attributes

FID3 Fixed Iterative Dichotomiser 3 ID3 Iterative Dichotomiser 3

IG Information Gain

DANH MỤC CÁC BẢNG

Bảng 1. Hệ thông tin đơn giản 10

Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk} 11

Bảng 3. Dữ liệu huấn luyện 23

Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data 41

Bảng 5. Độ chính xác của các thuật toán 45

DANH MỤC CÁC HÌNH

Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình 7

Hình 2. Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình 8

Hình 3. Quá trình phân lớp dữ liệu –Phân lớp dữ liệu mới 8

Hình 4. Xấp xỉ tập đối tượng trong Bảng 2 bởi các thuộc tính điều kiện Age và LEMS 14

Hình 5. Mô tả chung về cây quyết định 15

Hình 6. Ví dụ về Cây quyết định 16

Hình 7. Mô hình phân lớp các mẫu mới 19

Hình 8. Cây sau khi chọn thuộc tính Humidity (ID3) 25

Hình 9. Cây sau khi chọn thuộc tính Outlook (ID3) 26

Hình 10. Cây kết quả (ID3) 27

Hình 11. Cây sau khi chọn thuộc tính Humidity (ADTDA) 31

Hình 12. Cây sau khi chọn thuộc tính Outlook (ADTDA) 32

Hình 13. Cây kết quả (ADTDA) 33

Hình 14. Cây quyết định sau khi chọn thuộc tính Humidity (FID3) 36

Hình 15. Cây quyết định sau khi chọn thuộc tính Windy (FID3) 38

Hình 16. Cây kết quả (FID3) 39

Hình 17. Dạng cây quyết định ID3 42

Hình 18. Dạng cây quyết định ADTDA 42

Hình 19. Dạng cây quyết định FID3 43

Hình 20. Một số luật của cây quyết định ID3 44

Hình 21. Một số luật của cây quyết định ADTDA 44

Hình 22. Một số luật của cây quyết định FID3 44

Hình 23. Giao diện ứng dụng 46