Hướng tiếp cận mới trong việc tách từ để phân
loại văn bản tiếng Việt sử dụng giải thuật di
truyền và thống kê trên Internet
A Novel Approach in Word Segmentation to Classify
Vietnamese Documents Using GA and Internet-Based Statistics
Nguyễn Thanh Hùng

Abstract: Vietnamese segmentation approach for text
categorization. Instead of using annotated training corpus
or lexicon which is still lack in Vietnamese, we uses
statistic information extracted directly from a commercial
search engine and genetic algorithm to find most
reasonable ways of segmentation. The extracted
information includes document frequency and n-gram
mutual information. Our experiment results obtained on
segmentation and categorization online news abstracts
show that our approach is very promising. It achieves near
80% human judgment on segmentation and over 90%
micro-averaging F1 in categorization. The processing time
is less than one second per document when statistic
information was cached.

I. GIỚI THIỆU
Tách từ là một khó khăn chính trong việc phân loại
văn bản đối với các ngôn ngữ châu Á như tiếng Hoa,
tiếng Nhật, tiếng Hàn và cả tiếng Việt. Mặc dù được
viết bằng các ký tự La tinh mở rộng, tiếng Việt cũng
có những đặc tính chung với các ngôn ngữ
phonographic Đông Nam Á khác như khó xác định
ranh giới giữa các từ và có các điểm khác biệt về
phonetic, văn phạm và ngữ nghĩa so với các ngôn ngữ

Dưới đây là một số điểm khác biệt chính giữa tiếng
Việt và tiếng Anh. Những đặc điểm này làm cho việc
tách từ tiếng Việt trở nên khó khăn hơn.


Bảng 1. Các điểm khác biệt chính giữa tiếng Việt và tiếng
Anh
Đặc điểm
Đơn vị cơ
bản
Tiền tố/Hậu
tố
Từ loại
Ranh giới từ

Tiếng Việt
Tiếng

Tiếng Anh
Từ

Không có

Có

Not Unanimous

Được định nghĩa
rõ
Khoảng trắng hoặc

Internet sử dụng các search engine thương mại. Thông
tin rút trích bao gồm tần số của tài liệu và thông tin
tương quan n-gram.
Nội dung bài viết được tổ chức như sau: sau phần
giới thiệu, chúng tôi sẽ trình bày về tình hình nghiên
cứu việc tách từ tiếng Hoa và tiếng Việt. Phần 3 trình
bày ý tưởng chính của việc thống kê dựa trên Internet.
Trong phần tiếp theo, chúng tôi trình bày chi tiết

hướng tiếp cận giải thuật di truyền. Phần 5 trình bày
kết quả thử nghiệm và thảo luận. Cuối cùng là phần
kết luận và hướng phát triển.
II. TÌNH HÌNH NGHIÊN CỨU
Dưới đây là kết quả khảo sát của Foo và Li [7] về
tách từ trong văn bản tiếng Hoa và thống kê của
chúng tôi về việc tách từ tiếng Việt (Hình 1).

Hình 1. Các hướng tiếp cận cơ bản trong việc phân đọan
văn bản tiếng Hoa và các hướng tiếp cận hiện nay trong
việc phân đọan văn bản tiếng Việt.

Các hướng tiếp cận dựa trên “từ”: được chia
thành 3 nhóm: dựa vào thống kê, dựa vào từ điển và
nhóm lai, nhằm tách từ trọn vẹn trong câu. Các giải
pháp theo hướng tiếp cận dựa vào thống kê cần phải
dựa vào thong tin thống kê như term, từ hay tần số ký
tự, hay xác suất cùng xuất hiện trong một tập dữ liệu
cơ sở. Do đó, tính hiệu quả của các giải pháp loại này
chủ yếu dựa vào ngữ liệu huấn luyện cụ thể được sử
dụng. Đáng tiếc đây lại là vấn đề khó khăn đối với bài

di truyền để tìm ra những cách phân đọan văn bản tối
ưu nhất của cùng một văn bản. Mặc dù bài báo chỉ
mới trình bày những kết quả thử nghiệm bước đầu,
chúng tôi tin vào khả năng phát triển và tính khả thi
của hướng tiếp cận mới này. Trong bài viết này,
chúng tôi sẽ mở rộng ý tưởng này, bổ sung một số
thay đổi quan trọng và đánh giá các kết quả thử
nghiệm.
III. NGUYÊN
INTERNET

LÝ

THỐNG KÊ DỰA VÀO

Chúng tôi đồng ý với H. Nguyen et al [11] rằng
thống qua các search engine thương mại, chúng ta có
thể rút trích những thông tin thống kê hữu ích từ
Internet. Đó là tần số tài liệu (document frequency –
df), số lượng các tài liệu đã được lập chỉ mục có chứa
từ cần xét. Ta chuẩn hóa giá trị df bằng cách chia cho
một hằng số MAX (là số lượng các tài liệu tiếng Việt
đã được lập chỉ mục) để xấp xỉ xác suất xuất hiện của
một từ trên Internet.

Trên thực tế, chúng ta khó có thể biết được chính
xác số lượng các tài liệu tiếng Việt đã được lập chỉ
mục, do đó, thông qua thực nghiệm1 giá trị df của các
từ thông dụng, chúng tôi chọn giá trị MAX là 109.
Bảng 2. Tần số tài liệu của một số từ thông dụng trong

sánh khả năng chuỗi “khoa học tự nhiên” hay “học
khoa học tự” là từ ghép. Ta thấy rằng “khoa học tự
nhiên” có giá trị MI lớn hơn hẳn MI của “học khoa
học tự” (không có ý nghĩa).
Bảng 3. Ví dụ về MI của n-gram
Chuỗi

1

wf

MI

Chúng tôi thử nghiệm bằng Google: http://www.google.com


khoa học tự nhiên
khoa học tự
học tự nhiên
học khoa học tự
học khoa học

39200
41800
39900
14900
28600

0.92


thuật di truyền sẽ tiến hóa một quần thể qua nhiều thế
hệ nhằm tối ưu hóa toàn cục thông quá quá trình chọn
lọc, lai, biến dị và tái sinh. Chất lượng của mỗi cá thể
trong quần thể được xác định bằng hàm thích nghi và
qua mỗi thế hệ, chúng ta sẽ chọn lại N cá thể tốt nhất
sau khi thực hiện quá trình lai, biến dị và tái sinh.
Giải thuật di truyền áp dụng cho bài toán tách từ
tiếng Việt được tóm tắt như sau:
Mục tiêu: Xét văn bản t gồm n tiếng t=s1s2…sn.
Mục tiêu của quá trình GA là xác định những cách
tách hợp lý nhất văn bản t thành m đọan t=w1w2…wm
với wk=si…sj (1 ≤ k≤ m, 1≤ i, j≤ n) có thể là từ đơn
hay từ phức.
Cách biểu diễn: Quần thể (pop) là tập hợp các cá
thể (id) được biểu diễn bằng xâu nhị phân. Mỗi bit
tương ứng với một tiếng. Vậy, một từ sẽ gồm các bit
giống nhau liên tiếp.
Ví dụ:
học sinh học sinh học
0 0 1 0 0
học sinh # học # sinh học
w1
w2
w3
Khởi tạo quần thể: Ở bước này, ta khởi gán các
tham số như số lượng thế hệ, kích thước quần thể, tỉ lệ

Tần số
8933
48995

hóa cục bộ.
Phép lai: Chúng tôi áp dụng thao tác lai 1-điểm
chuẩn trên hai xâu bit. Với cặp cá thể id1 id2, hai cá
thể con được tạo ra bằng cách lấy phần đầu của id1
nối vào phần sau của id2 và ngược lại. Tuy nhiên,
nếu cá thể con vi phạm các điều kiện giới hạn về kích
thước (mỗi đoạn wk có kích thước tối đa là 4), ta sẽ
chuẩn hóa cá thể này bằng cách đảo các bit gây ra vi
phạm ở cuối đoạn này.
Phép biến dị: Thay vì dùng phép biến dị đảo bit
2

http://dict.vietfun.com


ngẫu nhiên, chúng tôi chỉ đảo các bit ở biên của mỗi
phân đoạn. Tương tự phép lai, ta sẽ chuẩn hóa các cá
thể để thỏa điều kiện giới hạn kích thước của phân
đoạn.
Tái sinh: Sau khi thực hiện phép lai và biến dị, ta
chọn lại một số cá thể ở thế hệ trước (theo tỉ lệ đã
chọn) đưa vào quần thể mới.
Phép chọn: Ở mỗi thế hệ, chúng ta chỉ chọn giữ lại
N cá thể tốt nhất. Hàm thích nghi của mỗi cá thể id
được xác định như sau:

tóm tắt của nhiều trang báo điện tử3 nhằm tạo ra sự
toàn diện cho dữ liệu thử nghiệm (tin tức đa dạng về
chủ đề và phong cách). Để thử nghiệm việc phân loại
văn bản, chúng tôi chia các tóm tắt bài báo theo các

đánh giá,
− Thử nghiệm phân loại văn bản dựa trên cách tách từ
được chúng tôi đề nghị.
Chúng tôi xây dựng ngữ liệu để thực hiện thử
nghiệm. Do hướng tiếp cận của chúng tôi sử dụng
thống kê dựa trên Internet, chúng tôi đã thu thập phần

− Phép chọn N = 100 cá thể tốt nhất
1. Thử nghiệm tách từ
Trong thử nghiệm này, chúng tôi đã nhờ một giáo
sư ngôn ngữ học và một học viên cao học Tin học
cùng hợp tác để đánh giá (một cách độc lập) độ chính
xác của việc tách từ trong các tóm tắt bản tin điện tử.
Người tham gia sẽ trả lời hai câu hỏi sau đối với kết
quả tách từ:
− Hoàn toàn đồng ý với kết quả tách từ hay không?
(câu hỏi này dùng để đánh giá kết quả tách từ là hoàn
hảo)
− Theo kết quả của việc tách từ, người đọc hiểu đúng
ý nghĩa của văn bản hay không? (câu hỏi này dùng để
đánh giá kết quả tách từ là chấp nhận được)
Để phục vụ bài toán phân loại văn bản, chúng ta
không cần tách từ một cách hoàn hảo mà chỉ cần kết
quả tách từ là chấp nhận được, tức là các từ quan
trọng phải được tách chính xác, còn các từ ít quan
trọng có thể tách không hoàn toàn chính xác. Bảng 5
thể hiện đánh giá của người tham gia thử nghiệm đối
với kết quả tách từ:
Bảng 5. Đánh giá kết quả của việc tách từ


hai người tham gia thử nghiệm. Chúng tôi tin rằng
điều này là do hệ thống từ loại (part of speech) trong
tiếng Việt không được định nghĩa rõ ràng, dẫn đến sự
không thống nhất ý kiến đánh giá.
Tuy nhiên, điều đáng mừng là tỉ lệ tách từ chấp
nhận được khá cao. Gần 80% kết quả tách từ không
làm người đọc hiểu sai nghĩa của câu. Đây chính là
điều mà chúng ta mong đợi. Cần lưu ý là để phục vụ
bài toán phân loại văn bản, chúng ta chỉ cần tách từ ở
mức độ chấp nhận được mà không cần phải đòi hỏi
đến mức độ hoàn hảo. Như vậy, không cần dùng ngữ
liệu huấn luyện, hướng tiếp cận được chúng tôi đề
nghị đã đạt được kết quả tách từ khả quan.
2. Thử nghiệm việc phân loại văn bản
Ngữ liệu thử nghiệm là tập gồm nhiều tài liệu,
D={d1, d2,…,dn}, trong đó, mỗi tài liệu được gán nhãn
chủ đề duy nhất từ tập hợp các chủ đề C={c1,
c2,…,cm}. Mỗi chủ đề sẽ có một danh sách các từ khóa
đại diện K={k1, k2,…,ku}. Với mỗi tài liệu d, chúng ta
áp dụng một số bước tiền xử lý để tăng tốc độ xử lý.
Trước tiên, chúng ta tách d thành nhiều nhóm tiếng
dựa vào dấu câu và số lượng. Thứ hai, sử dụng danh
sách stop word, chúng ta loại bỏ các các từ thường ít
có ý nghĩa. Cuối cùng, d được biểu diễn là d =g1g2…gr
với gi là một nhóm tiếng sau khi đã tiền xử lý.
Với một chuỗi đã phân đoạn t=w1w2…wm, ta tính
điểm liên quan với một chủ đề c như sau:

Với p(k | w) là xác suất có điều kiện của từ khóa k
nếu biết từ w. Theo công thức trên, mức độ support

Thể thao
Micro-avg

Phương pháp
đề nghị
87.2
90.5
82.9
88.5
85.7
96.4
99.5
90.1

IGATEC
83.9
91.4
78.0
87.4
83.6
96.0
100.0
88.6

Kết quả thực nghiệm cho thấy hướng tiếp cận của
chúng tôi có phần tốt hơn IGATEC. Bên cạnh đó, việc
sử dụng các bước tiền xử lý nêu trên giúp giảm đáng
kể số lượng thế hệ của quá trình tiến hóa. Trong thử
nghiệm, số lượng thế hệ trung bình trong phương
pháp của chúng tôi vào khoảng 52.3, trong khi

lexicon chuẩn. Ngoài ra, chúng tôi tin rằng hướng tiếp
cận trong việc tách từ của mình có thể được áp dụng
hiệu quả trong nhiều bài toán khác liên quan đến tiếng
Việt hoặc các ngôn ngữ tương tự, như xử lý ngôn ngữ
tự nhiên hay truy tìm thông tin.
Chúng tôi sẽ tiếp tục nghiên cứu, khảo sát nhằm tối
ưu các tham số của giải thuật di truyền. Chúng tôi sẽ
xây dựng chiến lược xác định giá trị các tham số một
cách tự động nhằm tăng tốc độ xử lý của giải thuật.
Ngoài ra, hiện tại, chúng tôi chỉ sử dụng tần số thô
của tài liệu từ search engine. Trong bài báo của
4

Pentium IV, 1.50GHz, 250 MB RDRAM

Cilibrasi và Vitanyi [4] đã giới thiệu nhiều độ đo
khoảng cách mới và phương pháp để rút trích ý nghĩa
của từ và ngữ từ Internet sử dụng số lượng trang trên
Google. Những kết quả này có thể được áp dụng để
nâng cao hiệu quả của phương pháp được đề nghị.
Mục tiêu lâu dài của chúng tôi là áp dụng và đánh
giá các phương pháp phân loại văn bản hiệu quả và
được nghiên cứu sâu để tìm ra phương pháp hiệu quả
và phù hợp nhất cho việc phân loại văn bản tiếng Việt.
TÀI LIỆU THAM KHẢO.
[1] L. D. Baker, A. K. Mccallum, Distributional
clustering of words for text categorization, Proceedings of
the 21st Annual International Conference on Research and
Development in Information Retrieval (SIGIR’98), 1998,
pp96-103.



[10] Z. Michalewicz, Genetic algorithms + data structures
= evolution programs, 3rd edition, Springer-Verlag
London, UK, 1996.

retrieval. 17th Annual International Conference on
Research and Development in Information Retrieval
(SIGIR’94), 1994, pp13-22

[11] H. Nguyen, H. Nguyen, T. Vu, N. Tran, K. Hoang,
Internet and Genetics Algorithm-based Text Categorization
for Documents in Vietnamese, Research, Innovation and
Vision of the Future, the 3rd International Conference in
Computer Science, (RIVF 2005), Can Tho, Vietnam, 2005.

[16] Yiming Yang, An evaluation of Statistical Approaches
to Text Categorization. Journal of Information Retrieval,
Vol 1, No. 1/2, 1999, pp 67—88.

[12] S. Shankar, G. Karypis, Weight adjustment schemes
for a centroid-based classifier, Text Mining Workshop on
Knowledge Discovery in Data (KDD’00), 2000.
[13] Chih-Hao Tsai, MMSEG: A Word Identification
System for Mandarin Chinese Text Based on Two Variants
of the Maximum Matching Algorithm. Web publication at
http://technology.chtsai.org/mmseg/, 2000.
[14] E. Wiener, J.O. Pedersen, A.S. Weigend, A neural
network approach to topic spotting. Proceedings of the
Fourth Annual Symposium on Document Analysis and