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ữ

Ấn Âu.
Do đó, rất khó có thể áp dụng các kỹ thuật và
hướng tiếp cận đã được nghiên cứu và thử nghiệm
thành công trên các ngôn ngữ Ấn Âu cho tiếng Việt
nếu không xây dựng thành công giải pháp cho việc

tách từ trong văn bản tiếng Việt.
Vậy, vì sao việc xác định ranh giới từ trong tiếng
Việt lại có vai trò quan trọng trong việc phân loại văn
bản tiếng Việt?
Theo Yang và Xiu [18] và các kết quả khảo sát của
chúng tôi, hầu hết các phương pháp phân loại văn bản
tiếng Việt hiệu quả nhất hiện nay như: Support Vector
Machine [8], Linear Least Squares Fit [15], mạng nơ
ron [14, 1, 12] … đều cần thông tin xác suất hay thống
kê hay trọng số của từ. Sau khi khảo sát và đánh giá
các phương pháp này trong việc phân loại văn bản
tiếng Việt, chúng tôi nhận ra rằng việc tách từ là bước
đầu tiên hết sức quan trọng cần phải được giải quyết
Vậy, vì sao việc xác định ranh giới từ trong tiếng
Việt lại là bài toán khó? Đơn vị cơ bản trong tiếng
Việt là tiếng, không phải là từ. Trong [5] đã nêu ra
một số đặc tính chính của từ trong tiếng Việt như sau:
− Từ ở dạng nguyên thể, hình thức và ý nghĩa của từ
độc lập với cú pháp
− Từ được cấu trúc từ “tiếng”
− Từ bao gồm từ đơn (từ một tiếng) và từ phức (ntiếng, với n < 5), bao gồm từ láy và từ ghép.
Trong khi đó, định nghĩa về từ trong tiếng Anh như
sau: “Từ là một nhóm ký tự có nghĩa, được phân cách
bởi ký tự khoảng trăng trong câu” (Từ điển Webster).

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

dấu câu

Tổ hợp có nghĩa dựa
vào ngữ cảnh của các
tiếng

Khó khăn lớn nhất trong việc phân loại văn bản
tiếng Việt là gì? Gần đây, nhiều kết quả mới khả quan
trong việc phân loại văn bản tiếng Hoa và một số
ngôn ngữ Đông Nam Á khác đã được công bố. Tuy
nhiên, việc áp dụng các hướng tiếp cận dựa trên ngữ
liệu vào tiếng Việt khó có thể đạt được kết quả mong
muốn, thật chí không khả thi trên thực tế. Hiện tại,
chưa có lexicon chuẩn hay ngữ liệu huấn luyện tiếng
Việt được gán nhãn đủ lớn và có chất lượng phục vụ
việc này. Do đặc điểm của tiếng Việt nên việc xây
dựng bộ lexicon hay ngữ liệu này cần rất nhiều thời
gian, công sức và chi phí. Đây chính là vấn đề đáng lo
nhất trong bài toán phân loại văn bản tiếng Việt, xử lý
ngôn ngữ tự nhiên và tìm kiếm thông tin tiếng Việt.
Trong bài báo này, chúng tôi tập trung vào cách
tách từ trong văn bản tiếng Việt theo một cách khả thi
nào đó mà không dựa vào bất kỳ bộ lexicon hay ngữ
liệu huấn luyện được gán nhãn nào để phục vụ cho
việc phân loại văn bản tiếng Việt. Do có thể tồn tại
nhiều cách tách từ hợp lý khác nhau cho cùng một
câu, chúng tôi sử dụng giải thuật di truyền để tiến hóa
quần thể mà trong đó, mỗi cá thể là tương ứng với một
cách tách từ cho câu đang xét. Hàm đánh giá độ thích
nghi thể hiện thong tin thống kê rút trích trực tiếp từ

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

toán tách từ tiếng Việt như đã trình bày ở phần trên.
Dinh et al [6] đã xây dựng ngữ luyện huấn luyện riêng
(khoảng 10MB) dựa vào các tài nguyên, tin tức và
sách điện tử trên Internet. Dĩ nhiên là bộ ngữ liệu này
khá nhỏ và không toàn diện (tức là không đủ rộng,
bao gồm đủ các lĩnh vực, chủ đề khác nhau).
Trong hướng tiếp cận dựa vào từ điển, các phân


đọan văn bản được đối sánh dựa vào từ điển. Việc xây
dựng từ điển các từ và ngữ tiếng Việt hoàn chỉnh là
không khả thi.
Hướng tiếp cận lai áp dụng nhiều cách khác nhau để
tận dụng ưu điểm của các giải pháp. Tóm lại, các
hướng tiếp cận để phân loại văn bản tiếng Việt dựa
vào từ chỉ khả thi khi chúng ta có bộ lexicon tốt
và/hay ngữ liệu huấn luyện đủ lớn và đáng tin cậy
Các hướng tiếp cận dựa trên ký tự (dựa trên
“tiếng” trong tiếng Việt): Có thể chia làm 2 nhóm
nhỏ: uni-gram và n-gram. Các phương pháp này tuy
đơn giản nhưng đã đem lại nhiều kết quả quan trọng
trong việc xử lý tiếng Hoa (Foo và Li, [7]). Gần đây
cũng có một số bài báo phân đọan văn bản tiếng Việt
theo hướng tiếp cận này. Le [9] đã xây dựng 10 MB
ngữ liệu thô và sử dụng quy hoạch động để tối ưu hóa
tổng xác suất của các phân đọan (các ngữ được phân
cách bởi các ký tự phân cách).
Trong bài báo gần đây của H. Nguyen et al [11],
thay vì sử dụng ngữ liệu thô, tác giả đã sử dụng thông
tin thống kê trực tiếp từ Internet và sử dụng giải thuật

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

tiếng Việt
Tiếng Việt
có
của
một

df
21.3 × 106
20.4 × 106
14.4 × 106

Do từ tiếng Việt gồm một (số) tiếng liên tiếp nhau,
ta cần độ đo thông kê mức độ liên kết giữa các tiếng.
Mutual information -MI là một khái niệm quan trọng
trong lý thuyết thông tin, được dùng trong xử lý ngôn
ngữ tự nhiên để thể hiện quan hệ giữa hai từ cụ thể x
và y (Church et al [3]):

Tuy nhiên, chúng tôi không chỉ xét các cặp tiếng mà
còn xét nhóm n tiếng (n-gram). Tương tự Chien et al
[3], chúng tôi mở rộng công thức tính MI của bigram
cho n-gram:

Với cw là chuỗi gồm n tiếng (cw = s1s2…sn), lw và
rw là hai chuỗi con dài nhất (n-1) của cw (lw =
s1s2…sn-1 và rw = s2s3…sn). Nếu giá trị MI(cw) lớn thì
lw và rw có khuynh hướng cùng xuất hiện chung
trong tài liệu trên Internet (tức là cw có khả năng cao
là từ ghép).
Ví dụ: xét chuỗi “đại học khoa học tự nhiên”, ta so

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:


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


0.27

Trong phần tiếp theo, chúng tôi sẽ giới thiệu hướng
tiếp cận bằng giải thuật di truyền để xác định MI tối
ưu toàn cục, tức là cách tách từ hợp lý nhất của câu.

lai, tỉ lệ biến dị và tỉ lệ tái sinh. Các cá thể ban đầu của
quần thể được phát sinh ngẫu nhiên. Tuy nhiên, chúng
tôi áp dụng một số ràng buộc nhằm tối ưu hóa các
chuỗi ngẫu nhiên được phát sinh ra. Dưới đây là thống
kê rút ra từ từ điển trực tuyến chưa 72994 từ và ngữ2
Bảng 4. Thống kê theo độ dài của từ trong từ điển

Độ dài của từ
1
2
3
4
≥5
Tổng cộng

IV. HƯỚNG TIẾP CẬN BẰNG GIẢI THUẬT DI
TRUYỀN ĐỂ TÁCH TỪ
Với mỗi câu, chúng ta sẽ xác định cách tách từ hợp
lý nhất. Tuy nhiên, không gian tìm kiếm sẽ rất lớn do
có nhiều cách tổ hợp các tiếng thành từ. Dựa vào
nguyên lý tiến hóa và di truyền, giải thuật di truyền
thích hợp cho việc xác định (xấp xỉ) các lời giải tối ưu
hóa toàn cục trong không gian tìm kiếm rất lớn thay vì
các lời giải tối ưu cục bộ (Michalewicz, [10]). Giải

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

5727
7040
2301
72994

Tỉ lệ %
12.2
67.1
7.9
9.7
3.1
100

Do hiện chưa có từ điển chuẩn dành cho xử lý ngôn
ngữ nên chúng tôi quyết định chọn thống kê dựa trên
một từ điển thông dụng. Dựa vào số liệu thống kê, ta
thấy rằng có trên 67% các từ trong từ điển có độ dài là
2 tiếng, khoảng 30% là từ đơn hay từ gồm 3-4 tiếng.
Các từ dài hơn chỉ chiếm khoảng 3% trong từ điển,
trong đó thường là các thành ngữ. Dựa vào nhận xét
này, chúng tôi đề ra một số điều kiện giới hạn cho
việc tạo và chọn các cá thể ngẫu nhiên ban đầu của
quần thể:
− Mỗi đoạn gồm tối đa 4 tiếng.
− Xác suất tạo ra đoạn gồm 2 tiếng cao hơn xác suất
tạo ra đoạn có độ dài khác 2
Ngoài ra, chúng tôi áp dụng dạng đơn giản của giải
thuật đối sánh Left Right Maximum (Tsai, [13]) để tạo
ra hai cá thể đặc biệt: cá thể “tiến” và cá thể “lùi”.
Như vậy, quần thể ban đầu sẽ có một số cá thể tối ưu

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




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

chủ đề khác nhau: xã hội, thế giới, thương mại, khoa
học, văn hóa, sức khỏe và thể thao. Cuối cùng, chúng
tôi thu thập 0,5MB ngữ liệu thử nghiệm gồm 700 tóm
tắt, 41219 tiếng, 100 tài liệu trong mỗi chủ đề.
Trong các thử nghiệm, chúng tôi chọn các tham số
của giải thuật di truyền như sau:
− Số lượng thế hệ tối đa = 100
− Số lượng cá thể trong quần thể = 100
− Tỉ lệ lai = 0.8
− Tỉ lệ biến dị = 0.1
− Tỉ lệ tái sinh = 0.1

với id=w1w2…wm là một cá thể trong quần thể pop
= {id1, …, idN}
Hội tụ: Quá trình tiến hóa nhằm cải thiện độ thích
nghi của các cá thể trong quần thể, tức là cải thiện
chất lượng của việc tách từ. Do đó, chúng ta sẽ dừng
quá trình tiến hóa nếu độ thích nghi của thế hệ sau
không cao hơn thế hệ trước, hoặc số lượng thế hệ đạt
ngưỡng cho trước.
V. KẾT QUẢ THỬ NGHIỆM VÀ THẢO LUẬN
Việc đánh giá độ chính xác của giải thuật tách từ
tiếng Việt là điều rất phức tạp, đặc biệt là không có
ngữ liệu kiểm chứng đã được tách từ thủ công. Bên
cạnh đó, như chúng tôi đã trình bày ở phần trên, tách
từ chỉ là bước đầu tiên của phân loại văn bản, sau đó
còn có nhiều bước xử lý khác trước khi có thể đánh
giá về kết quả phân loại văn bản. Do đó, chúng tôi
thực hiện hai thử nghiệm:
− Thử nghiệm việc tách từ, kết quả sẽ do con người

đá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ừ


,
,
,
3


Người đánh giá

Hoàn hảo

Giáo sư ngôn ngữ học

368
52.57%
431
61.57%

Học viên Cao học Tin
học

Chấp nhận
được
538
76.86%
554
79.14%

Chúng ta có thể biết trước là tỉ lệ tách từ hoàn hảo
không cao, ngoài ra, có sự chênh lệch đáng kể giữa
việc đánh giá tính hoàn hảo của kết quả tách từ giữa

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

càng cao thì khả năng văn bản thuộc về chủ đề đó
càng cao. Chúng tôi tổng quát hóa mức độ support của
một tài liệu đã được tiền xử lý d đối với một chủ đề c
như sau:

Trong thí nghiệm này, chúng tôi sẽ phân loại ngữ
liệu thử nghiệm theo 7 chủ đề phổ biến trên tờ báo
tiếng Việt gồm: xã hội, thế giới, kinh tế, khoa học, văn
hóa, sức khỏe và thể thao. Việc xác định danh sách
các từ khóa của mỗi chủ đề không phải là mục tiêu
của bài báo này và sẽ được nghiên cứu sâu trong các
công trình sau này. Do đó, trong thí nghiệm này,
chúng tôi chọn một từ khóa – chính là tên của chủ đề cho mỗi chủ đề.
Trong thí nghiệm của chúng tôi giả sử rằng mỗi tài
liệu chỉ thuộc về duy nhất một trong số bảy chủ đề đã
chọn. Chúng ta sử dụng độ đo F1 và micro-averaging
F1 (Yang [16]) để lượng giá hiệu quả. Bảng 6 thể hiện
kết quả trên ngữ liệu thử nghiệm của chúng tôi đối với
tất cả các chủ đề và giá trị microaveraging. Chúng tôi
so sánh kết quả của mình với phương pháp IGATEC
của H. Nguyen [11].
Bảng 6. Giá trị F1 và micro-averaging F1 của phương pháp
được đề nghị so với IGATEC
Chủ đề
Xã hội
Thế giới
Kinh tế
Khoa học
Văn hóa
Sức khỏe

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



IGATEC sử dụng khoảng 500 thế hệ. Chính nhờ điều
này, cùng với việc sử dụng thông tin MI có thể được
tính nhanh chóng, giúp cho việc phân loại văn bản
của chúng tôi có tốc độ khá nhanh (khoảng 0.5 giây
cho mỗi tài liệu trên máy tính cá nhân4 với thông tin
thống kê đã được lưu trữ sẵn).
Đây chỉ là những thử nghiệm ban đầu để kiểm
chúng hướng tiếp cận của chúng tôi. Hiện chúng tôi
đang tiếp tục thử nghiệm việc phân loại văn bản với
ngữ liệu phức tạp và đa dạng hơn .
VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Trong bài báo này, chúng tôi đề nghị việc sử dụng
thông tin MI với hàm lượng thông tin lớn nhưng có
chi phí tính toán thấp và một số bước tiền xử lý hiệu
quả phục vụ việc phân loại văn bản tiếng Việt. Điểm
mới của hướng tiếp cận này là thay vì phải sử dụng
ngữ liệu huấn luyện đã được gán nhãn hay lexicon –
vốn chưa có sẵn cho tiếng Việt, chúng tôi đã sử dụng
thông tin thống kê rút trích trực tiếp từ search engine
và dùng giải thuật di truyền để xác định những cách
tách từ hợp lý nhất đối với văn bản tiếng Việt cho
trước. Các kết quả thực nghiệm cho thấy hướng tiếp
cận của chúng tôi đạt được những kết quả khả quan
trong việc tách từ và phân loại văn bản tiếng Việt với
độ đo micro-averaging F1 (Yang, [16]) đạt trên 90%.
Phương pháp này hứa hẹn tiềm năng lớn cho việc xử
lý các văn bản của các ngôn ngữ tương tự tiếng Việt –
vốn còn chưa có các ngữ liệu được gán nhãn hay

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.

[2] Lee-Feng Chien, T. I. Huang, M. C. Chen., PAT-TreeBased Keyword Extraction for Chinese Information
Retrieval, Proceedings of 1997 ACM SIGIR Conference,
Philadelphia, USA, 1997, pp50-58.
[3] K. Church, P. Hanks, W. Gale, and D. Hindle, Using
Statistics in Lexical Analysis, in U. Zernik Lexical
Acquisition: Using On-line Resources to Build a Lexicon,
Lawrence Erlbaum Associates, 1991.
[4] Rudi Cilibrasi, Paul Vitanyi, Automatic meaning
discovery of Google. A search for meaning, New Scientist,
Duncan Graham-Rowe, 29 January 2005, p.21.
[5] Dinh Dien, Từ tiếng Việt,
University, HCMC, Vietnam, 2000.

Vietnam National

[6] Dinh Dien, Hoang Kiem, Nguyen Van Toan,
Vietnamese Word Segmentation, The Sixth Natural
Language Processing Pacific Rim Symposium, Tokyo,
Japan 2001, pp749-756.
[7] Foo S., Li H, Chinese Word Segmentation and Its
Effect on Information Retrieval, Information Processing &
Management: An International Journal, 40(1), 2004,
pp161-190.
[8] T. Joachims, Text Categorization with Support Vector
Machines: Learning with Many Relevant Features,
European Conferences on Machine Learning (ECML’98),
1998.
[9] Le An Ha, A method for word segmentation in
Vietnamese, Proceedings of Corpus Linguistics 2003,
Lancaster, UK, 2003.



[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
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

Information Retrieval (SDAIR’95).
[15] Yiming Yang, Expert network: Effective and efficient
learning from human decisions in text categorization and

SƠ LƯỢC TÁC GIẢ
NGUYỄN THANH HÙNG
Sinh ngày 04/04/1964 tại Thanh Hoá
Tốt nghiệp Đại học Sư phạm Toán-Lý tại Liên xô
(cũ) năm 1987. Tốt nghiệp Cao học Tin học tại Đại
học Khoa học Tự nhiên TP. HCM năm 1997. Hiện là
Nghiên cứu sinh tại Đại học KHTN TP. HCM
Hiện đang giảng dạy tại Trường PT Năng KhiếuĐHQG TP. Hồ Chí Minh.
Lĩnh vực nghiên cứu: Lý thuyết thuật toán, Các bài
toán tối ưu, Thuật giải di truyền (GA)
Email :

[17] Yiming Yang, C.G. Chute, An example-based
mapping method for text categorization and retrieval,
ACM Transaction on Information System (TOIS’94), 1994,
pp 252-277.
[18] Yiming Yang, Xin Liu, A re-examination for text
categorization methods. Proceedings of ACM SIGIR
Conference on Research and Development in Information
Retrieval (SIGIR’99), 1999.
Ngày nhận bài: 23/01/2006