Tìm hiểu kỹ thuật nhận dạng văn bản trong lớp ngôn ngữ La tinh

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

------------------

CHỬ ĐỨC THÀNH

TÌM HIỂU KỸ THUẬT NHẬN DẠNG VĂN BẢN

TRONG LỚP NGÔN NGỮ LA TINH

LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH

THÁI NGUYÊN, NĂM 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

------------------

CHỬ ĐỨC THÀNH

TÌM HIỂU KỸ THUẬT NHẬN DẠNG VĂN BẢN

TRONG LỚP NGÔN NGỮ LA TINH

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH

NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. ĐẶNG THỊ THU HIỀN

THÁI NGUYÊN, NĂM 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

LỜI CẢM ƠN

Tôi xin chân thành cảm ơn các Thầy giáo, Cô giáo trong khoa Công nghệ

thông tin và các cán bộ, nhân viên phòng Đào tạo Sau đại học, Trƣờng Đại học

Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã luôn nhiệt tình

giúp đỡ và tạo điều kiện tốt nhất cho tôi trong suốt quá trình học tập tại trƣờng.

Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học

CK12H - Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái

Nguyên đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm

học tập, công tác trong suốt khoá học.

Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Đặng Thị Thu Hiền đã tận

tình giúp đỡ tôi hình thành và hoàn chỉnh luận văn.

Mặc dù đã có nhiều cố gắng, song do sự hạn hẹp về thời gian, điều kiện nghiên

cứu và trình độ, luận văn không tránh khỏi những khiếm khuyết. Tôi chân thành

mong nhận đƣợc sự đóng góp ý kiến của các Thầy giáo, Cô giáo và đồng nghiệp.

Một lần nữa tôi xin cảm ơn!

Thái Nguyên, tháng 08 năm 2015

Ngƣời thực hiện luận văn

Chử Đức Thành

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

MỤC LỤC

MỞ ĐẦU ....................................................................................................................4

CHƢƠNG I TỔNG QUAN VỀ NHẬN DẠNG ......................................................3

1.1. Tổng quan về nhận dạng..................................................................................3

1.1.1. Không gian biểu diễn đối tƣợng, không gian diễn dịch ...........................3

1.1.2. Mô hình và bản chất của quá trình nhận dạng..........................................4

1.2. Nhận dạng dựa trên phân hoạch không gian....................................................7

1.2.1. Phân hoạch không gian.............................................................................7

1.2.2. Hàm phân lớp hay hàm ra quyết định ......................................................7

1.2.3. Nhận dạng thống kê..................................................................................8

1.2.4. Một số thuật toán nhận dạng tiêu biểu trong tự học ...............................10

1.3. Nhận dạng theo cấu trúc ................................................................................12

1.3.1. Biểu diễn định tính .................................................................................12

1.3.2. Phƣơng pháp ra quyết định dựa vào cấu trúc .........................................13

1.4. Nhận dạng bằng mạng nơron.........................................................................14

1.4.1. Bộ não và Nơron sinh học ......................................................................15

1.4.2. Mô hình mạng nơron ..............................................................................17

CHƢƠNG II KỸ THUẬT NHẬN DẠNG BẰNG THỐNG KÊ .........................20

2.1. Bài toán ..........................................................................................................20

2.2. Nhận dạng có giám sát...................................................................................21

2.3. Nhận dạng không có giám sát........................................................................25

2.3.1. Đặt bài toán.............................................................................................25

2.3.2. Giải bài toán trƣờng hợp cho trƣớc số k.................................................25

2.3.3. Trƣờng hợp số k chƣa cho biết trƣớc .....................................................28

2.4. Mô hình xích Markov ....................................................................................30

2.5. Đặc trƣng của ngôn ngữ tự nhiên ..................................................................32

2.5.1. Tần số đơn tƣơng đối của ngôn ngữ Tiếng Anh, Tiếng Pháp, Tiếng

Đức. ..................................................................................................................33

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

2.5.2. Tần số bộ đôi móc xích của Tiếng Anh, Tiếng Pháp, Tiếng Đức ..........34

CHƢƠNG III THỰC NGHIỆM............................................................................38

3.1. Bài toán nhận dạng văn bản La Tinh .............................................................38

3.2. Thuật toán sử dụng tần số đơn ......................................................................38

3.2.1.Xây dựng cơ sở dữ liệu để máy học ........................................................38

3.2.2.Phân biệt trực tiếp....................................................................................42

3.2.3. Một số ví dụ............................................................................................44

3.3. Thuật toán dựa trên xich Markov cấp 1 hữu hạn trạng thái...........................46

3.3.1. Xây dựng cơ sở dữ liệu để máy học .......................................................46

3.3.2. Nhận biết trực tiếp ..................................................................................57

3.3.3. Một số ví dụ............................................................................................59

3.4.Chƣơng trình Demo ........................................................................................72

3.4.1 Giao diện chính của chƣơng trình ...........................................................73

3.4.2 Xây dựng các mẫu thử.............................................................................74

3.4.3. Thực thi chƣơng trình với thuật toán sử dụng tần số đơn ......................75

3.4.4. Thực thi chƣơng trình với thuật toán dựa trên xích Markov cấp 1 hữu

hạn trạng thái ....................................................................................................76

3.4.5. So sánh giữa 2 thuật toán........................................................................78

KẾT LUẬN..............................................................................................................80

TÀI LIỆU THAM KHẢO ......................................................................................81

PHỤ LỤC.................................................................................................................82

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DANH MỤC CÁC HÌNH

Hình 1.1. Sơ đồ tổng quát một hệ nhận dạng..............................................................7

Hình 1.2. Cấu tạo nơron sinh học..............................................................................15

Hình 1.3 Mô hình nơron nhân tạo.............................................................................17

Hình 3.1. Sơ đồ khối của thuật toán sử dụng tần số đơn ..........................................43

Hình 3.2. Sơ đồ khối của thuật toán dựa trên xich Markov cấp 1 hữu hạn trang thái....58

Hình 3.3.Giao diện của chƣơng trình........................................................................73

Hình 3.4 Thực hiện lấy dữ liệu đầu vào....................................................................74

Hình 3.5 Màn hình thực thi thuật toán sử dụng tần số đơn.......................................75

Hình 3.6 Kết quả hiển thị dang file.txt của thuật toán sử dụng tần số đơn...............76

Hình 3.7 Màn hình thực thi thuật toán dựa trên xích Markov cấp 1 hữu hạn trạng

thái.............................................................................................................................77

Hình 3.8 Kết quả hiển thị dang file.txt của thuật toán dựa trên xích Markov cấp 1

hữu hạn trạng thái......................................................................................................77

Hình 3.9 Sơ đồ biểu diễn độ chính xác của hai thuật toán........................................78

Hình 3.10 Kết quả của thuật toán sử dụng tần số đơn ..............................................78

Hình 3.11 Kết quả của thuật toán dựa trên xích Markov cấp 1 hữu hạn trạng thái .79

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DANH MỤC CÁC BẢNG

Bảng 2.1 Tần số đơn tƣơng đối của ngôn ngữ Anh, Pháp, Đức .............................33

Bảng 2.2 Bảng tần số bộ đôi móc xích của Tiếng Anh.............................................35

Bảng 2.3 Bảng tần số bộ đôi móc xích của Tiếng Pháp............................................36

Bảng 2.4 Bảng tần số bộ đôi móc xích của Tiếng Đức.............................................37

Bảng 3.1 Ƣớc lƣợng hợp lí cực đại đặc trƣng các ngôn ngữ Anh, Pháp , Đức, Dãy

ngẫu nhiên .................................................................................................................39

Bảng 3.2 Ƣớc lƣợng hợp lí cực đại đặc trƣng các ngôn ngữ Anh, Pháp , Đức, Dãy

ngẫu nhiên .................................................................................................................40

Bảng 3.3 Ƣớc lƣợng hợp lí cực đại đặc trƣng các ngôn ngữ Anh, Pháp , Đức, .......41

Bảng 3.4 Ƣớc lƣợng hợp lí cực đại đặc trƣng các ngôn ngữ Anh, Pháp , Đức, .......42

Bảng 3.5. Ƣớc lƣợng bộ đôi móc xích tiếng Đức ....................................................48

Bảng 3.6. Ƣớc lƣợng bộ đôi móc xích tiếng Pháp ...................................................49

Bảng 3.7. Ƣớc lƣợng bộ đôi móc sích tiếng Anh ....................................................50

Bảng 3.8. Ƣớc lƣợng ma trận các xác suất chuyển trạng thái P của mô hình Markov

ứng với các ngôn ngữ tự nhiên tiếng Đức.................................................................53

Bảng 3.9.Ƣớc lƣợng ma trận các xác suất chuyển trạng thái P của mô hình Markov

ứng với các ngôn ngữ tự nhiên tiếng Pháp................................................................54

Bảng 3.10. Ƣớc lƣợng ma trận các xác suất chuyển trạng thái P của mô hình

Markov ứng với các ngôn ngữ tự nhiên tiếng Anh ...................................................55

Bảng 3.11.Ƣớc lƣợng ma trận các xác suất chuyển trạng thái P của mô hình Markov

ứng với các ngôn ngữ tự nhiên tiếng dãy ngẫu nhiên ...............................................56

1

MỞ ĐẦU

Nhận dạng là một lý thuyết toán học có nhiều ứng dụng trong thực tiễn, nhƣ

nhận dạng tiếng nói, nhận dạng hình ảnh, nhận dạng chữ ký, phân loại ngôn ngữ ,

xây dựng tiêu chuẩn bản rõ ứng dụng trong phân tích các bản mã v.v..Trên thế giới

cũng nhƣ trong nƣớc đã có nhiều nhà nghiên cứu vấn đề này và đã có những phần

mềm áp dụng cho nhiều lĩnh vực khác nhau: phần mềm nhận dạng tiếng việt, phần

mềm nhận dạng vân tay, phần mềm kiểm soát E-mail trên hệ thống Internet…

Nhận dạng chữ là bài toán rất hữu ích, quen thuộc đƣợc ứng dụng nhiều trong

thực tế đặc biệt là trong lĩnh vực nhận dạng và phân loại văn bản vì thế đã thu hút

nhiều tác giả quan tâm nghiên cứu bằng các phƣơng pháp nhận dạng khác nhau:

logic mờ, giải thuật di truyền, mô hình xác suất thống kê, mô hình mạng nơ ron. Đã

có rất nhiều công trình nghiên cứu thực hiện việc nhận dạng, phân loại văn bản La

Tinh đã đạt tỷ lệ chính xác cao, tuy nhiên các ứng dụng đó cũng chƣa thể đáp ứng

hoàn toàn nhu cầu của ngƣời sử dụng vậy nên ngày nay ngƣời ta vẫn tiếp tục nghiên

cứu những phƣơng pháp nhận dạng tốt hơn hƣớng đến dùng cho các thiết bị di

động, và các bài toán thời gian thực. Sau khi tìm hiểu về sự tiến bộ của công nghệ

nhận dạng chữ La Tinh cũng nhƣ các tính năng cơ bản của các phần mềm nhận

dạng chữ, đƣợc sự tƣ vấn của giáo viên hƣớng dẫn, tôi đã lựa chọn đƣợc một hƣớng

nghiên cứu thiết thực với đề tài: "Tìm hiểu kỹ thuật nhận dạng văn bản trong lớp

ngôn ngữ La Tinh".

Trong khuôn khổ của luận văn, tôi tập trung nghiên cứu, giải quyết bài toán

nhận dạng ngôn ngữ tự nhiên dựa vào phân hoạch không gian (nhận dạng theo

thống kê toán học), trong đó một lớp ngôn ngữ tiêu biểu đƣợc nghiên cứu đó là

ngôn ngữ La Tinh.

Việc nghiên cứu này là quan trọng và cần thiết, kết quả của nghiên cứu có khả

năng mở rộng ứng dụng trong việc xây dựng chƣơng trình kiểm soát E-mail đặc biệt

là chƣơng trình phân tích bản mã tự động, đây là những vấn đề rất cần thiết trong an

ninh quốc phòng. Đó chính là ý nghĩa thực tiễn của đề tài.

 Nội dung của luận văn và các vấn đề cần giải quyết

1. Nghiên cứu quá trình Markov hữu hạn trạng thái.

2. Nghiên cứu và xây dựng mô hình Markov ứng với các ngôn ngữ tự nhiên nhƣ :

Tiếng Anh, Tiếng Pháp, Tiếng Đức.

2

3. Giải bài toán phân lớp các đối tƣợng cho trƣờng hợp số lớp đã biết trƣớc và số

lớp chƣa biết.

4. Nghiên cứu xây dựng các ƣớc lƣợng tham số của xích Markov

5. Ứng dụng bài toán kiểm định giả thiết thống kê (testing of statistic hypothesis)

để giải quyết bài toán nhận dạng ngôn ngữ.

6. Lập trình thử nghiệm.

 Phƣơng pháp nghiên cứu

Phƣơng pháp cơ bản là nghiên cứu ứng dụng các phƣơng pháp toán học, nhận dạng

và xử lý ngôn ngữ, nghiên cứu khảo sát lý thuyết và xây dựng các thuật toán, lập

trình kiểm thử thuật toán và đánh giá. Cụ thể:

- Tìm hiểu và cập nhật các kiến thức và phƣơng pháp cơ bản về nhận dạng ngôn

ngữ tự nhiên, trí tuệ nhân tạo, khảo sát lý thuyết các mô hình, công cụ toán học,

thiết kế và xây dựng thuật toán, kỹ thuật tổ chức dữ liệu và ngôn ngữ lập trình.

- Tìm đọc các bài báo, các công trình nghiên cứu khoa học liên quan đến chủ đề

nghiên cứu trong nƣớc và trên thế giới. Cụ thể là các tài liệu kỹ thuật thống kê toán

học các quá trình Markov; các quy luật ngôn ngữ nhƣ là một quá trình ngẫu nhiên

dừng, không hậu quả; các kỹ thuật nhận dạng ngôn ngữ tự nhiên. Hình thành đƣợc

tổng quan tƣơng đối đầy đủ về tình hình nghiên cứu liên quan đến chủ đề hiện nay

trên thế giới.

- Lập trình cài đặt một số kỹ thuật nhận dạng ngôn ngữ La Tinh và đánh giá kết

quả.

 Cấu trúc luận văn đƣợc chia thành 3 chƣơng:

Chƣơng 1: " Tổng quan về nhận dạng ", trình bày tổng quan các hƣớng nghiên

cứu hiện nay về nhận dạng.

Chƣơng 2: " Kỹ thuật nhận dạng bằng thống kê ", trình bày các ứng dụng kỹ

thuật thống kê Toán học để nhận dạng các ngôn ngữ tự nhiên và tìm hiểu

đặc trƣng của một số ngôn ngữ tự nhiên tiêu biểu.

Chƣơng 3: " Thực Nghiệm ", trình bày thuật toán nhận dạng văn bản La Tinh và

đƣa ra kết quả với một số mẫu ngôn ngữ điển hình.