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

i

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

ii

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

iii

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

iv

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

v

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