Phân loại văn bản tiếng Việt với giải thuật K-NN
MỞ ĐẦU
Trong những năm gần đây phân loại văn bản đã trở thành một kỹ thuật then
chốt để tổ chức thông tin trực tuyến. Nó có thể được sử dụng để tổ chức cơ sở
dữ liệu văn bản, lọc thư điện tử tìm kiếm thông tin liên quan đến Web, hoặc để
chỉ dẫn người dùng tìm kiếm thông tin qua các siêu văn bản hypertext). Mà ở
đó, việc phân loại văn bản bằng tay là không thể thực hiện được, hoặc thực hiện
với chi phí tốn kém nhất. Do đó, cùng với sự phát triển của thông tin trực tuyến,
một yêu cầu cấp thiết đặt ra là cần phải xây dựng hệ thống phân loại văn bản tự
động.
Cho đến nay, đã có nhiều đề xuất xây dựng bài toán phân loại văn bản tự
động như Neive Bayes, Bayes net, K- láng giêng gần nhất, cây quyết định, mạng
nơron, Support Vector Machines, Các phương pháp phân loại này, đạt được
những thành đáng kể đối vớ các văn bản tiếng anh, Pháp, Nhật, Trung Quốc đã
được ứng dụng thực tế như trong các tìm kiếm của Yahoo, Altavista, Google,
Trong đó, K- láng giềng gần nhất là một cách tiếp cận cho độ chính xác của
phân loại văn bản cao hơn hẳn các phương pháp phân loại khác.
Ơ Việt Nam, cũng đã có nhiều nghiên cứu về lĩnh vực xử lý văn bản tiếng
Việt, như đề tìa nghiên cứu về Máy dịch tự động Anh –Việt (EVTRan) của viện
nghiên cứu ứng dụng công nghệ, đề tài nhận dạng, xử lý tiếng Việt VnDoc của
viện công nghệ thông tin và nhiều luận văn tôt nghiệp cao học đại học khác.
Nhưng nghiên cứu về phân loại văn bản tiếng việt chưa nhiều và kết quả con hạn
chế. Bởi vậy, trong luận văn này em sẽ tập trung nghiên cứu bài toán phân loại
văn bản Tiếng Việt dựa trên cách tiếp cận K- láng giêng gần nhất.
Một vấn đề liên quan mật thiết đến tốc độ xử lý cũng như độ chính xác của
quá trình phân loại số chiều của vector biểu diễn văn bản. Nếu dùng các từ trong
từ điển làm đặc trưng để biểu diễn văn bản thì mỗi văn bản tiếng Việt được biểu
diễn bằng một vector có hơn 70 nghìn chiều (tương đương với số từ trong tư
điển tiếng Việt). 70 nghìn là con số quá lớn khi ta có đến hàng triệu văn bản cần
ĐỒ ÁN TÔT NGHIỆP
1

1.1. Khai phá dữ liệu văn bản (Text mining)
Văn bản là một trong những dạng dữ liệu phổ biến nhất, hiện nay, nó có
mặt ở khắp mọi nơi và chung ta thường xuyên bắt gặp hàng ngày. Do đó, các bài
toán xử lý văn bản đã được đặt ra từ khá lâu và cho đến nay vấn là một trong
những vấn đề hay trong khai phá dữ liệu văn bản (text), trong đó có những bài
toán đáng chú ý như tìm kiếm văn bản, phân loại văn bản, phân cụm văn bản,
hoặc dẫn đường văn bản,
Các văn bản được tập hợp trong cơ sơ dữ liệu văn bản có thể chia làm hai
loại:
- Dạng không có cấu trúc (unstructured): Những văn bản thông thường
mà chúng ta thường đọc hàng ngày được thể hiện dưới dạng ngôn ngữ tự nhiên
của con người và nó không có một cấu trúc định dạng nào.
- Dạng bán cấu trúc (semi- structured): Những văn bản được tổ chức
dưới dạng cấu trúc không chặt chẽ thành bản ghi mà dùng các ký hiệu đánh dấu
văn bản vẫn thể hiện được nội dung của văn bản, ví dụ như các dạng HTML,
email,
Trong luận văn này, em chỉ quan tâm xử lý dữ liệu văn bản ở dạng phi cấu
trúc (biểu diễn văn bản dưới dạng tập tin TXT), bài toán được giải quyết theo
hướng dữ liệu mở để tương lài có thể áp dụng với các mục đích sử dụng khác
nhau.
ĐỒ ÁN TÔT NGHIỆP
3
Phân loại văn bản tiếng Việt với giải thuật K-NN
Có nhiều cách phân lớp các lĩnh vực trong xử lý văn bản, Lewis đã chia
thành hai nhóm lĩnh vực chính là phân lớp văn bản (TextClàssifition) gồm các
công việc xác định văn bản hoặc một phần của văn bản vào một hay nhiều lớp
xác định trước và hiểu nghĩa văn bản (Text Understanding) bao gồm các công
việc phức tạp hơn để xử lý nội dung của văn bản như tóm tắt văn bản (Text
Summarization hoặc Abstraction), trích chọn thông tin (Text Extraction), Tuy
nhiên, việc phân làm hai lớp cũng không thật rõ ràng, trong các hệ phần mềm,

khác biệt giữa văn bản chứa nó với văn bản khác. Đại lượng này có thể xác định
bằng tay hay đánh giá số lần xuất hiện của cụm từ đó trong văn bản và số lần
xuất hiện của cụm từ đó trong các văn bản khác. Số lần xuất hiện của từ trong
văn bản càng nhiều thì độ quan trọng của nó trong văn bản càng lớn và ngược
lại.
1.2.1. Khai phá văn bản/dữ liệu
Một số bài toán của khai phá văn bản dữ liệu là:
- Phân loại văn bản (Text Categorization): cho một số lớp văn bản đã được
xác định trước, nhiệm vụ của phân loại văn bản là: gán các văn bản vào ( một
hay một số) lớp văn bản thích hợp dựa vào nội dung của văn bản.
- Lập nhóm của văn bản (Text Clustering): cho một số văn bản, nhiệm vụ
của lập nhóm văn bản là chia các văn bản này thành các nhóm thích hợp căn cứ
vào mặt tương tự về mặt nội dung giữa các văn bản.
- Tóm tắt văn bản (Text Summairzation): Tóm tắt, chắt lọc thông tin từ một
(hay nhiều) nguồn để đưa ra mô tả ngắn gọn, cô đọng thông tin từ nguồn tài liệu
đó.
- phát hiện xu hương nổi bật (Emerging Trend Detection): Phát hiện các
chủ đề sẽ được quan tâm và có ích trong tương lài.
- Trả lời câu hỏi: Đưa ra câu chả lời thích hợp cho câu hỏi (tìm tài liệu thích
hợp cho câu hỏi)
-
1.2.2. Ứng dụng các kết quả khai phá dữ liệu văn bản trong thực tế
Ứng dụng các kết quả khai phá dữ liệu văn bản là sử dụng cá kết quả khai
thác văn bản cho những mục đích cụ thể. Kết quả của quá trình khai phá dữ liệu
ĐỒ ÁN TÔT NGHIỆP
5
Phân loại văn bản tiếng Việt với giải thuật K-NN
văn bản có thể sử dụng cho việc trích lọc thông tin, tóm tắt thông tin, dịch tự
động văn bản, dự đoán các xu hướng trong tương lài, tim kiếm thông tin, phân
loại thông tin, Và các ứng dụng này lại được sử dụng như một công cụ hỗ trợ

thức từ tài liệu của hệ thống chuyên gia. nghĩa là, các luật phải được định nghĩa
bằng tay bởi các kỹ sư tri thức với sự giúp đỡ của chuyên gia trong lĩnh vực
được nêu trong tài liệu: nếu tập hợp của các loại được cập nhật, thì hai nhà
chuyên gia về lĩnh vực được nêu trong tài liệu: nếu tập hợp của các loại được
cập nhật, thì hai nhà chuyên nghiệp phải can thiệp lại và nếu phân loại được
chuyển hoàn toàn sau một phạm vi khác, một chuyên gia về lĩnh vực này phải
can thiệp vào công việc phải được bắt đầu từ tập tài liệu hỗn tạp ban đầu.
Đầu thế kỷ 90, cách tiếp cận học máy (Machine Learning) để phân loại
văn bản được coi là nổi tiếng và trở thành thống trị, ít nhất là trong cộng đồng
người nghiên cứu (Mitchell[1996]), Theo cách tiếp cận này, một quá trình xử lý
quy nạp chung (cũng được gọi là quá trình học) xây dựng tự động
một phần lớp cho một loại c
i
bằng quan sát các đặc trưng của tập hợp các
tài liệu đã được phân bằng tay vào c
i
hay
i
c
bởi chuyên gia về lĩnh vực này; từ
đó, quá trình qui nạp thu lươm các đặc trưng để phân loại một tài liệu mới
(không nhìn thấy) vào c
i
. Trong kỹ thuật học máy, bài toán phân lớp là hoạt
động học có giam sát, quá trình học được “giám sát” bởi tri thức của các phân
loại và của mẫu huấn luyện thuộc chúng.
Với phương pháp học máy, sự cố găng về phương diên công việc của kỹ sư
theo hướng không phải xây dựng một phân lớp tự động (học) từ một tập các tài
liệu đã được phân loại bằng tay. Trong các tiếp cận học máy, các tài liệu đã
được phân loại bằng tay. Trong các tiếp cận học máy, các tài liệu đã được phân

i
là kí hiệu của lớp thứ i. Hàm
Φ
: D
×
C
→
{T, F} với mọi < d
j
, c>
C×Ω∈
. Một tài liệu d
j
là mẫu dương của c
i
nếu
Φ
( d
j
, c
i
) = T, làu một mẫu âm nếu
Φ
( d
j
, c
i
) = F.
Với cách phân loại đưa ra, người ta mong muốn đánh giá được hiệu quả
của chúng. Bởi vậy, trước khi xây dựng phân loại của chúng. Bởi vậy, trước khi

i
) và so sánh giá trị này với quyết định
Φ
( d
j
, c
i
) của chuyên
gia. Hiệu quả của phân lớp dựa trên sự phù hợp giữa
Φ
( d
j
, c
i
) và
Φ
( d
j
, c
i
).
Số tài liệu trong tập luỵên và tập kiểm tra thường được chọn theo tỷ lệ
tương ứng là 70% và 30% Trong đó, Tr
∩
Te =
φ
, nếu điều kiện này bi vi
phạm thì kết quả đánh giá hiệu quả của mô hình mất đi yếu tố khách quan, khoa
học.
ĐỒ ÁN TÔT NGHIỆP

- Tách từ trong văn bản.
ĐỒ ÁN TÔT NGHIỆP
9
Phân loại văn bản tiếng Việt với giải thuật K-NN
- Biểu diễn văn bản
- Phương pháp học máy để phân loại văn bản
- Đánh giá hiệu quả của phương pháp học
1.3.2. Một Số phương pháp phân loại văn bản
Có nhiều phương pháp phân loại văn bản được đề xuất, sự khác nhau
cơ bản giữa các phương pháp này là ở thuật toán quy nạp. Nhiều thực nghiệm
cho thấy các phương pháp như: cây quyết định (decision tree), K- làng giềng
gần nhất (K- nearest neighbos), phương pháp sử dụng các vector hỗ trợ (Support
Vector Machines) là những phương pháp có hiệu quả phân loại cao ở Việt Nam
cũng như một số nghiên cứu sử dụng cây quyết định, k- láng giềng gần nhất để
phân loại văn bản tiếng Việt.
- Phương pháp cây quyết định: Ý tưởng của phương pháp này là xây
dựng một cây nhị phân quyết định gồm các nút và các cung trọng số liên kết
giữa các nút cụ thể: Các nút trong được gán nhãn bởi các từ, nhãn của các cung
tương ứng với trọng số của các từ trong tài liệu mẫu, nhãn của các lá tương ứng
với nhãn của các lớp. Cho một tài liệu d
j
, ta sẽ thực hiện so sánh các nhã của
cung xuất phát từ một nút trong (tương ứng với một từ nào đó) với trọng số của
từ trong d
j
, để quyết định nút trong nào sẽ được duyệt kế tiếp. Quá trình này
được lặp từ nút gốc của cây, cho tới khi nút được duyệt là một lá của cây. Kết
thúc quá trình này, nhãn của nút làn nhãn của lớp được gán cho văn bản.
- Phương pháp k- láng giềng gần nhất: Tư tưởng chính cảu phương
pháp này là tình độ phù hợp của văn bản đang xét với từng nhóm chủ đề dựa

Trong chương này, em đã trình bày tóm tắt các bước cần làm của một bài
toán phân loại văn bản. Nghiên cứu phương pháp KNN và so sánh no với một số
phương pháp phân loại văn bản khác. Cuối cùng là kết quả thực nghiệm của luận
văn, dùng phương pháp k- láng giềng gần nhất để phân loại văn bản tiếng Việt.
ĐỒ ÁN TÔT NGHIỆP
11
Phân loại văn bản tiếng Việt với giải thuật K-NN
CHƯƠNG II
TÁCH TỪ VÀ BIỂU DIỄN VĂN BẢN TIẾNG VIỆT
Để máy tính có thể tự động phân loại văn bản, thì các văn bản được trình
bày dưới dạng chuỗi ký tự cần phải biến đổi thành một mô tả thuận lợi cho thuật
toán huấn luyện và bài toán phân loại, nghĩa là văn bản được chuyển từ dạng
không có cấu trúc (hoặc bán cấu trúc) sang dạng có cấu trúc. Có rất nhiều cách
biểu diễn văn bản, nhưng dù theo cách này hay cách khác thì việc biểu diễn văn
bản đều dựa vào sự xuất hiện của từ trong văn bản. Do đó, công việc đầu tiền và
ảnh hưởng lớn đến quá trình phân loại là kết quả của việc tách từ trong văn bản.
Tiếng Việt có những đặc điểm riêng về cấu tạo của từ, cấu trúc ngữ pháp. Nên
việc tách từ trong văn bản tiếng Việt cũng đòi hỏi những phương pháp đặc
trưng. Trong chương này, em sẽ trình bày chi tiết các bước tiền xử lý chuẩn bị
cho việc phân loại văn bản tiếng Việt
o Một số phương pháp tách từ trong văn bản tiếng Việt.
o Cách trích chọn đặc trưng để biểu diễn văn bản.
o Một số phương pháp biểu diễn văn bản.
2.1. Một số phương pháp tách từ trong văn bản Tiếng Việt
2.1.1. Các đặc trưng của văn bản
- Nhiều chiều: Số lượng từ dùng để biểu diễn văn bản là rất lớn ( hơn
10000)
- Có tính phụ thuộc: Các từ, các câu trong văn bản hoàn toàn độc lập với
nhau, chúng có liên quan với nhau về mặt ngữ nghĩa. Để hiểu chinh xác ý nghĩa
diễn đạt của một từ nào đó trong văn bản ta cần phải xem xét nó trong một ngữ

trong tiếng Việt. Các định nghĩa về từ và tiếng của tiếng Việt. Các định nghĩa về
từ và tiếng của tiếng Việt trong phần này được trích dẫn từ bộ sách tiếng Việt
cấp 2, của nhà xuất bản Giáo Dục.
a) Tiếng
ĐỒ ÁN TÔT NGHIỆP
13
Phân loại văn bản tiếng Việt với giải thuật K-NN
Ngôn ngữ Việt Nam có một đơn vị đặc biệt gọi là tiếng. Mỗi tiếng trong
tiếng Việt được viết thành một chữ, ngược lại mỗi chữ đọc thành một tiếng, mỗi
chữ nằm giữa dấu phân cách trong câu. Tiếng được dùng để tạo thành từ, tiếng
có thể có nghĩa rõ ràng hoặc không có nghĩa rõ ràng. Ví dụ:
- Từ “ lạnh lẽo ” ( có nghĩa ): tiếng “lạnh” (có nghĩa), tiếng “lẽo” (nghĩa
không rõ).
- Từ “ bồ kết ” (có nghĩa): Tiếng “bồ” và tiếng “kết” (đều có nghĩa).
- Tiếng gồm có ba bộ phận hợp lại: âm đầu, vần và thanh. Ví dụ, tiếng
“đà” có âm đầu là “đ” vần “a” và thanh “huyền”. Hai bộ phân vần và thanh,
tiếng nào cũng phải có. Âm đầu thì có tiếng có, có tiếng không. ví dụ: tiếng “ở”
chỉ có vần “ơ” và thanh “hỏi”, không có âm đầu. Mỗi bộ phận của tiếng do một
âm hay kết hợp một số âm tạo thành. Bộ phận âm đầu do âm tạo thành. Âm đầu
là phụ âm.
- Bộ phận vần có thể do một hoặc 2, 3 âm tạo thành, nhưng bao giờ
cũng phải có một âm chính. Âm chính là nguyên âm. Âm cuối của vần cũng có
thể là phụ âm. Ví dụ, tiếng “nam” có âm đầu là n, âm cuối của vần là phụ âm m,
nguyên âm làm âm chính là a.
Tiếng Việt dùng chữ cái để ghi âm. Mỗi âm được ghi bằng 1 hoặc nhiều
chữ cái ghép lại. Trật tự bảng chữ cái trong Tiếng Việt: a, ă, â, b, c, d, đ, e, ê, g,
h, i, k, l, m, n, o, ô, ơ, p, q, r, s, t, u, ư, v, x, y.
b) Từ
Tồn tại nhiều định nghĩa khác nhau về từ trong tiếng Việt, Nhưng tất cả các
nghiên cứu ngôn ngữ đều đồng ý từ trong tiếng Việt có những đặc điểm sau

Tính từ
Là từ chỉ tính chất (của người, loại vật, đồ vật, cây cối, ) nhưng: mầu
sắc, hình thể, kích thước, dung lượng, phẩm chất,
Phụ từ
Là những hư từ chủ yếu đi kèm với động từ, tính từ để biểu diễn một số
quan hệ. Phần lớn phụ từ đứng trước động từ, tính từ. Xét về mặt ý nghĩa nào đó
mà thôi. Phụ từ biểu thị như quan hệ và những ý nghĩa thường gặp sau đây:
- Phụ từ (chỉ quan hệ ) thời gian
ĐỒ ÁN TÔT NGHIỆP
15
Phân loại văn bản tiếng Việt với giải thuật K-NN
- Phụ từ (chỉ) thể thức
- Phụ từ (chỉ ý) khẳng định, phủ định
- Phụ từ (chỉ ý) mức độ
Ví dụ: Mai nó mới đi
(phụ từ mới đi kèm với động từ đi chỉ ý khẳng định).
Phụ từ Không thể đảm nhiệm vài trò chính của cụm từ, chúng chuyên làm
thành tố trong cụng từ để bổ sung cho thành tố chính một ý nghĩa nào đó. Vì thế
chúng cũng được coi là các từ chứng làm bộc lộ bản chất ngữ pháp của các từ
làm thành tố chính. Đôi khi, nhờ các phụ từ mà ta xác định được từ loại của từ
mà chúng đi kèm. Chẳng hạn:
- Các phụ từ: đã, từng, vừa, mới, đang, sẽ, sắp, cho ta thấy từ đứng sau
được chúng phụ nghĩa thường là động từ.
- Các phụ từ chỉ mức độ: rất, hơi, cho ta thấy từ đứng sau được chúng
phụ nghĩa thường là tính từ hoặc động từ chỉ trạng thái tâm lí. Nhóm từ hãy,
chớ, đừng vốn là chứng tố của động từ, không xuất hiện được trước tính từ nói
chung. Tuy nhiên cũng có những trường hợp đặc biệt.
Ví dụ:
Có phải duyên nhau thì thắm lại
đừng xanh như lá, bạc như vôi

qua hệ về nhiều mặt giữa người nói – người nghe như hỏi, trả lời, sai khiến,
quan hệ, vài trò xã hội giữa họ với nhau. Trợ từ thường gặp là ư, ơ, à, a, ạ,
hử, hở, nhỉ, nhé, ghe, mà, lại, chứ lị, đi thôi, , chúng thường đứng ở cuối
câu. Tên gọi trợ từ còn được dùng chỉ những từ nhấn mạnh loại như cả, chỉ,
những. Ví dụ: Nó chỉ mua được hai vé.
Thán từ: là những từ biểu thị cảm xúc do sự việc hoặc đối với sự việc.
Thán từ thường gặp là: ôi, ơ, ái, á, ô hay, than ôi, trơi ơi, chúng thường
đứng ở đầu câu hoặc tách riêng thanh câu đặc biệt.
ĐỒ ÁN TÔT NGHIỆP
17
Phân loại văn bản tiếng Việt với giải thuật K-NN
2.1.2.2. Đặc điểm chính tả
a) Chính tả chưa thống nhất
Mặc dù chinh tả tiếng việt đã có một hệ thống quy tắc chuẩn mực, nhưng
vẫn có một số từ tôn tại nhiều cách viết khác nhau. Ngay cả bản thân một người
cũng có lúc viết thế này lúc viết thế khác Sự sai khác này là do các nguyên nhân
sau:
- Những từ đồng âm: y/i ( vật lý/ vật lí, tốc ký/tốc kí, bác sỹ/bác sĩ) d/gi
(dông bão/ giông bão).
- Phương ngữ: chính dáng/ chánh đáng, tru/ con trâu,
- Vị trí dấu trong một âm tiết: Khai hỏa/khai hỏa
- Cách viết hoa tùy tiện với danh từ riêng: tồn tại nhiều cách viết khác
nhau. Ví dụ: Bộ khoa học công nghệ và môi trường/Bộ khoa học công nghệ &
Môi trường, Việt Nam/Việt nam,
- Phiên âm tiếng nước ngoài: phiên âm là hình thức biến chữ ngoại quốc
thành chữ địa phương. Nhưng hiện nay tồn tại cả hai cách phiên âm hoặc không
phiên âm. Chẳng hạn, singapo/Xing- ga- po, America/ Hó Kỳ, Trung
Quốc/Trung Hoa,
- Dấu gạch nối: thường xuất hiện khi các từ đa âm nước ngoài du nhập
vào Việt Nam. Để chỉ rõ đây là một chữ không phải một cụm chữ, người ta dùng

tách từ trong nhóm ngôn ngữ trên.
Vào thời gian đầu và giữa thế kỷ 20, khi các nhà nghiên cứu Tiếng Việt
giới thiệu ngữ pháp phương Tây, một vài thay đổi trong mẫu viết tiếng Việt
được đề xuất, làm cho “nó hướng từ” hơn, sử dụng các nhãn hiệu khác cho biên
giới từ được rõ ràng hơn và ngôn ngữ giống với Châu Âu hơn. các thay đổi nay
gồm loại trừ khoảng trống giữa các tiếng và sử dụng dấu gạch nối, ví dụ “kỹ-
thuật” hay kỹ thuật thay cho “kỹ thuật” Sự cố gắng đó là không thanh công, có
thể do tính tự nhiên của ngôn ngữ tiếng Việt, hơn nữa sự nhận ra chính xác các
từ không phải lúc nào cũng qua trọng. Nhưng khó khăn và cũng là vấn đề đặt ra
với ngôn ngữ tiếng việt lá:
Sự nhập nhằng trong từ ghép
- Cho đến nay vẫn chưa có một từ điển tổng hợp, toàn diện.
ĐỒ ÁN TÔT NGHIỆP
19
Phân loại văn bản tiếng Việt với giải thuật K-NN
- Nhận ra các danh từ riêng và tên.
- Hình vị từ (morphemes) và từ láy.
Cho đến nay, đã có một số phương pháp tách từ Tiếng Việt được đánh giá
là hiệu quả.
2.1.3.1. Xây dựng các Ôtômát để đoán nhân các từ
Bài toán
Nhập vào một câu tiếng Việt bất kỳ, hãy tách câu đó thành những đơn vị
từ vựng (từ), hoặc chỉ ra những âm tiết nào không có trong từ điển (phát hiện
đơn vị từ vựng mới).
Với những phương pháp này, chúng ta cần tập dữ liệu gồm từ điển âm
tiết (khoảng 6700 âm tiết) và từ điển từ vựng tiếng Việt (khoảng 30. 000 từ).
Các từ điển được lưu dưới các tệp văn bản có định dạng mã TCVN hoặc
Unicode.
Các bước giải quyết
1) Xây dựng ôtômát âm tiết đoán nhận tất cả các âm tiết tiếng Việt

, , c
1−n
theo sơ đồ sau ( ô vuông chỉ rằng đó là trạng thái
kết thúc).
Ví dụ, với ba bộ âm tiết phương, pháp, trình ta sẽ có ôtômát âm tiết như sau
(hình bên):

Ôtômát từ vựng được xây dựng tương tự, với điểm khác nhau như sau:
Thay vi ghi trên mỗi cung chuyển một ký tự, ta ghi một số. Số này là số hiệu của
trạng thái (kết) của ôtômát âm tiết tại đó đoán nhận mỗi âm tiết của từ.
Với cách tổ chức này, ta làm giảm bớt kích thước của ôtômát từ vựng mà
không làm mất thông tin của nó, bởi vì mỗi âm tiết được xác định bằng một
trạng thái kết duy nhất trong ôtômát âm tiết. Ví dụ, với hai từ phương pháp và
phương trình, giả sử khi đưa lần lượt các âm tiết phương, pháp, trình qua ôtômát
âm tiết, ta đến được các trạng thái kết ghi số n
1
, n
2
, n
3
ĐỒ ÁN TÔT NGHIỆP
21
Phân loại văn bản tiếng Việt với giải thuật K-NN

Sau khi đã xây dựng xong hai ôtômát, ta ghi chúng vào hai tệp định kiểu
để dùng trong bước phân tách từ vựng. Đến lúc này, hai từ điển ban đầu không
còn cần thiết nữa, mọi dữ liệu của ta nằm trong hai tệp ghi hai ôtômát này. Nếu
mỗi ký tự (char) được ghi vào tệp với kích thước 2 byte (mã Unicode), mỗi số
nguyên (int) có kích thước 4 byte thì tệp lưu ôtômát âm tiết có kích thước 146
KB, tệp ôtômát từ vựng có kích thước 1MB.

0
đến đỉnh cuối v
1+n
. Trong
các phân tách câu đó, cách phân tách câu đúng đắn nhất ứng với đường đi qua ít
cung nhất trên đồ thị.
Trong trường hợp câu có sự nhập nhằng thì đồ thị sẽ có nhiều hơn một
đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối, ta liệt kê toàn bộ các đường đi
ngắn nhất trên đồ thị, từ đó đưa ra tất cả các phương án tách câu có thể và để
người dùng quyết định sẽ chọn phương án nào, tùy thuộc vào ngữ nghĩa hoặc
văn cảnh. Ví dụ, xét một cum câu “học sinh học”, ta có đồ thị sau:
ĐỒ ÁN TÔT NGHIỆP
22
Phõn loi vn bn ting Vit vi gii thut K-NN
Cụm n y có sự nhập nhằng, ta có hai kết quả phân tách là "học, sinh học"
và "học, sinh, học". Ta có thể chỉ ra rất nhiều cụm nhập nhằng trong tiếng Việt.
Trờng hợp trong câu có âm tiết không nằm trong từ điển thì rõ ràng ôtômát
âm tiết không đoạn nhận đợc âm tiết này. Kết quả là đồ thị xây dựng từ câu đó là
không liên thông. Dựa vào tính chất này, ta thấy rằng nếu đồ thị không liên
thụng thì dễ dàng phát hiện ra rằng đơn vị âm tiết không đoán nhận đợc không
nằm trong từ điển âm tiết, tức nó bị viết sai chính tả hoặc là đơn vị âm tiết mới.
ỏnh giỏ kt qu
Vi cỏch tip cn nh trờn, bi toỏn phõn tỏch t vng trong cõu ting
Vit v c bn ó c gi quyt, c bit l vn tỏch cỏc t hp t tng
ng vi mt n v t vng, thng l cỏc cm t c nh, ng c nh hoc
cỏc thnh ng trong ting Vit. Nu chỳng ta ch s dng mt danh sỏch t vng
thụng thng v tỡm kim trờn danh sỏch ny thỡ khụng th m bo thi gian
tỏch t vng i vi cõu cú chiu di ln.
Vi nhng cõu nhp vo cú s nhp nhng t vng, cú nhiu hn mt
cỏch phõn tỏch thỡ chng trỡnh lit kờ ton b cỏc phng ỏn tỏch t cú th v

tỏch cú xỏc sut sai ớt nht.
- Th hai l vn gii quyt tờn riờng, tờn vit tt v tờn cú ngun gc
nc ngoi cú mt trong cõu. Phng phỏp phõn tỏch ny cha nhn ra c cỏc
cum t dng Nguyn Vn A, i hc Khoa hc T nhiờn, hoc T. 8. 20.
20. 29, 1.000$, 0. 50%,
2.1.3.2. Phng phỏp tỏch t s dng mụ hỡnh markov n
Phng phỏp ny s dng mụ hỡnh n- gram c hun luyn khụng giỏm
sỏt bng thut toỏn baum- welch v s dng t in ting Vit thc hin phõn
on t trờn tp d liu ting vit cha c phõn on. Bi toỏn phõn on t
ting vit c qui v bi toỏn tỡm dóy trng thỏi hp lý nht khi cho mt dóy
N TễT NGHIP
24
Phân loại văn bản tiếng Việt với giải thuật K-NN
quan sát. Các thí nghiệm cho thấy rằng phương pháp này đạt được độ chính xác
cao hơn hoặc ít nhất là bằng các hệ phân đoạn từ tiếng Việt tự động tốt nhất hiện
nay, đặc biệt đối với các văn bản chuyên ngành. Hiện nay, kết quả này ứng dụng
vào chương trình kiểm lỗi chính tả và tìm kiếm mới tự động [5].
Mô hình tiếng Việt sử dụng HMM
Mô hình n- gram tiếng Anh chính là mô hình markov bậc n- 1.Dưới đây
chúng tôi sẽ trình bày mô hình n- gram tiếng Việt.
Mô hình n- gram tiếng Việt
Mô hình tiếng Việt cần được cần tham số hóa được hiện tượng nhập
nhằng ở đây. Cách thứ nhất, ta coi sự xuất hiện của một âm tiết được bổ xung
thêm một âm tiết phụ thuộc vào n- 1 âm tiết trước đó và tập âm tiết đặc biệt
dùng để phân biệt hai từ kề nhau. cách nhìn nhận này giống teahan và cộng sự
(2000) đã làm. Cách thứ hai, ta coi sự xuất hiện của một từ phụ thuộc vào n- 1 từ
trước đó và từ có thể là đơn hoặc ghép. sproat và cộng sự (1996) đã mô hình hóa
tiếng Trung Quốc bằng mô hình uni- gram kiểu này Đinh Điền và cộng sự
(2001) cũng đã áp dụng cách làm của sproat cho tiếng Việt. Tuy nhiên độ rộng
ngữ cảnh là không thì hẹp quá. Chúng ta xây dựng mô hinh n- gram vì các lý do