1

đại học quốc gia hà nội
tr-ờng đại học công nghệ

trần thị lan h-ơng NGHIấN CU PHN LP T NG
VN BN BO CH TING VIT
V TI NGUYấN V MễI TRNG

luận văn thạc sĩ công nghệ thông tin
Ng-ời h-ớng dẫn khoa học: PGS.TS Đỗ Trung Tuấn

Hà nội - 2012 3
MỤC LỤC
Trang

Mục lục Danh mục các bảng Danh mục các hình MỞ ĐẦU
1

Chương 1: KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN VÀ THUẬT
TOÁN K LÁNG GIỀNG GẦN NHẤT
3

1.4.1.
Loại bỏ từ dừng
8
1.4.2.
Thu gọn đặc trưng biểu diễn
8
1.5.
Độ liên quan giữa các văn bản
13
1.6.
Phân lớp văn bản
14
1.7.
Thuật toán K láng giềng gần nhất (KNN)
17
1.8.
Kết chương
18

Chương 2: BÀI TOÁN PHÂN LỚP TỰ ĐỘNG VĂN BẢN BÁO CHÍ
TIẾNG VIỆT VỀ TÀI NGUYÊN VÀ MÔI TRƢỜNG
19

4
2.1.
Một số đặc điểm tiếng Việt
19
2.1.1.
Âm tiết
19

2.3.3.
Tài nguyên khoáng sản
26
2.3.4.
Tài nguyên biển
27
2.3.5.
Khí tượng thủy văn
28
2.3.6.
Môi trường
29
2.3.7.
Đo đạc và bản đồ
29
2.4.
Bài toán phân lớp tự động các văn bản báo chí tiếng Việt về
tài nguyên và môi trường
31
2.5.
Mô hình tiếp cận bài toán
31
2.5.1.
Tiền xử lý văn bản
31
2.5.2.
Lựa chọn đặc trưng theo chủ đề văn bản
34
2.5.3.
Xử lý tập mẫu

3.5.
Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản mẫu
42
3.6.
Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản phân lớp
43
3.7.
Chức năng quản lý từ điển, từ dừng
44
3.8.
Chức năng quản lý chủ đề
44
3.9.
Thiết kế cơ sở dữ liệu
45
3.10.
Kết chương
45

Chương 4: CÀI ĐẶT MÔ HÌNH VÀ KIỂM THỬ KẾT QUẢ
46
4.1.
Cài đặt chương trình
46
4.1.1.
Lựa chọn công nghệ và môi trường cài đặt
46
4.1.2.
Giao diện chương trình phân lớp văn bản báo chí tiếng Việt
về tài nguyên và môi trường
Trang
Bảng 1.1.
Các đại lượng TP
c
, TN
c,
FN
c
, FP
c

16
Bảng 3.1.
Bảng thiết kế cơ sở dữ liệu
34
Bảng 4.1.
Thông tin mô tả một số thông số của tập dữ liệu huấn luyện
50
Bảng 4.2.
Trích kết quả kiểm thử phân lớp văn bản báo chí tiếng
Việt về tài nguyên môi trường
54 7
DANH MỤC CÁC HÌNH
Việt về tài nguyên và môi trường
32
Hình 2.4.
Sơ đồ thuật toán tách từ
33
Hình 2.5.
Mô hình xử lý tập mẫu
35
Hình 3.1.
Sơ đồ phân rã chức năng chính của hệ thống phân lớp
văn bản
37
Hình 3.2.
Sơ đồ phân rã chức năng mức chi tiết của hệ thống phân
lớp văn bản
38
Hình 3.3.
Sơ đồ khung cảnh mức 0
39
Hình 3.4.
Sơ đồ khung cảnh mức 1 chức năng tiền xử lý
41
Hình 3.5.
Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản mẫu
42
Hình 3.6.
Sơ đồ khung cảnh mức 1 chức năng quản lý văn bản
phân lớp
43
Hình 3.7.a.

các thư viện điện tử, phân loại văn bản báo chí trên các trang tin điện tử,…
những hệ thống tốt, cho ra kết quả khả quan, giúp ích nhiều cho con người.
Đề tài "Nghiên cứu phân lớp tự động văn bản báo chí tiếng Việt về tài
nguyên và môi trường", học viên vận dụng những kiến thức về kỹ thuật khai
phá văn bản, kỹ thuật phân lớp văn bản nói riêng, và kiến thức về công nghệ
thông tin nói chung, xây dựng bộ phân lớp văn bản báo chí tiếng Việt về tài
nguyên và môi trường. Mong muốn ứng dụng hệ thống phân lớp này vào
phục vụ nghiên cứu khoa học và công tác quản lý, phân loại các tài liệu văn
bản các thông tin chuyên ngành về tài nguyên môi trường, bởi tài nguyên và
môi trường hiện nay đang là vấn đề nóng bỏng không những Việt Nam mà cả
thế giới đang rất quan tâm.
Nội dung và phạm vi đề tài: Trình bày khái niệm khai phá dữ liệu,
khai phá văn bản, một số kỹ thuật khai phá văn bản và phân lớp văn bản.
Nghiên cứu một số đặc điểm đặc trưng của ngôn ngữ tiếng Việt, phương pháp
tách từ tiếng Việt và loại bỏ từ dừng. Nghiên cứu các chủ đề về thông tin
chuyên ngành tài nguyên và môi trường. Nghiên cứu, sử dụng thuật toán K-
NN xây dựng bộ phân lớp văn bản báo chí tiếng việt về tài nguyên và môi
trường vào các chủ đề chuyên ngành.

10
Đầu vào của bộ phân lớp là văn bản báo chí tiếng Việt về tài nguyên
và môi trường ở dạng tệp tin.doc,.txt, phông chữ Unicode.
Đầu ra là kết quả phân lớp văn bản báo chí tiếng Việt vào một trong
các chủ đề thông tin chuyên ngành: Tài nguyên đất; tài nguyên nước; tài
nguyên khoáng sản; tài nguyên biển; khí tượng thuỷ văn; môi trường; đo đạc
và bản đồ.
Bố cục của luận văn bao gồm:
Chương 1: Khái quát về phân lớp văn bản và thuật toán KNN. Chương
này trình bày khái quát về khai phá văn bản, Phân lớp văn bản, thuật toán
KNN

1.2. KHÁI NIỆM CƠ BẢN TRONG KHAI PHÁ VĂN BẢN
1.2.1. Một số khái niệm sử dụng trong luận văn
- Từ khóa: là các từ xuất hiện trong một văn bản có nghĩa trong từ điển.
- Thuật ngữ: là các từ khóa có nghĩa liên quan đến một số lĩnh vực nào
đó. ví dụ: "máy tính", "công nghệ phần mềm", "tính toán song song". Các
thuật ngữ này thuộc về lĩnh vực "tin học".
- Từ dừng: Nhiều từ được dùng để biểu diễn cấu trúc câu, xuất hiện
thường xuyên trong các văn bản, nhưng hầu như không mang ý nghĩa về mặt

12
nội dung, chẳng hạn các giới từ, liên từ, … những từ đó được gọi là từ dừng.
Ví dụ: Có thể, nếu, vì vậy, sau khi, thì, một số, với lại, quả thật, hầu như, …
- Trọng số của từ là độ quan trọng hay hàm lượng thông tin mà từ đó
mang lại cho văn bản. Trọng số của từ là đại lượng dùng để đo sự khác biệt
giữa văn bản chứa nó với các văn bản khác.
1.2.2. Các phƣơng pháp đánh trọng số cho từ khóa
1.2.2.1. Phương pháp boolean
Giả sử có một tập gồm m văn bản D = {d
1,
d
2
, d
3
, d
m
}, T là một tập
từ vựng gồm n từ khóa T = {t
1,
t
2

, khi đó w
ij
được tính bởi một trong 3 công
thức sau:
w
ij
= f
ij
hoặc w
ij
= 1 + log(f
ij
)
hoặc w
ij
=
ij
f

Trong phương pháp này, trọng số w
ij
tỷ lệ thuận với số lần xuất hiện
của từ t
i
trong văn bản d
j
. Khi số lần xuất hiện từ khóa t
i
trong văn bản d
j

2/ Phương pháp dựa trên nghịch đảo tần số văn bản IDF: Trong phương
pháp này, giá trị w
ij
được tính theo công thức sau:
trong đó m là số lượng văn bản và h
i
là số văn bản mà từ khóa t
i
xuất hiện.
3/ Phương pháp TF × IDF: Phương pháp này là tổng hợp của hai
phương pháp TF và IDF, giá trị của ma trận trọng số được tính như sau:
Phương pháp này kết hợp được ưu điểm của cả 2 phương pháp trên.
Trọng số w
ij
được tính bằng tần số xuất hiện của từ khóa t
i
trong văn bản d
j
và
độ hiếm của từ khóa t
i
trong toàn bộ cơ sở dữ liệu.
1.3. MỘT SỐ PHƢƠNG PHÁP BIỂU DIỄN VĂN BẢN
1.3.1. Mô hình Boolean

log
)hlog()mlog(
h
m
1
i
nếu từ khóa t
i
xuất hiện trong tài liệu d
j
0 nếu ngược lại

w
ij
=
w
ij
=
[1+log(f
ij
)] log
i
h
m
nếu f
ij
≥1

0 nếu ngược lại
1
Xử lý các phép toán trên vector sẽ phụ thuộc vào độ lớn của ma trận
W
nm,
ở đây n là số lượng thuật ngữ hay số chiều của vector, và m là số lượng
văn bản có trong cơ sở dữ liệu. Trên thực tế, số lượng thuật ngữ và số văn bản
có thể lên đến vài chục nghìn. Khi đó số lượng phần tử trong ma trận W
nm
sẽ
lên đến con số trăm triệu và lưu trữ ma trận W
nm
sẽ tốn rất nhiều tài nguyên bộ
T
1
T
2
T
3
v
2
v
1
θ

2
=
(0, 0, 0, 3, 0, 4). Đối với vector thưa: d
0
=((1, 6), (2, 5)); d
1
= ((3, 4), (5, 3), (6,
1)); d
2
= ((4, 3), (6, 4)). Kiểu phần tử của vector thưa có thay đổi so với vector
chuẩn. Mỗi phần tử gồm hai giá trị là mã biểu diễn thuật ngữ và giá trị trọng
số tương ứng của thuật ngữ đó.
1.3.3. Mô hình xác suất
Mô hình xác suất là mô hình toán học làm việc với các biến ngẫu
nhiên và phân bố xác xuất của nó. Theo thuật ngữ toán học, một mô hình xác
suất có thể coi như một cặp (Y, P), trong đó Y là tập các quan sát (biến ngẫu
nhiên) và P là tập các phân bố xác suất trên Y. Khi đó, sử dụng suy diễn xác
suất sẽ cho ta kết luận về các phần tử của tập Y.
Văn bản trong mô hình xác suất được coi như một quan sát trong tập Y,
trong đó các từ trong văn bản được giả thiết là độc lập, không phụ thuộc vào vị
trí cũng như ngữ pháp của văn bản. Khi đó văn bản sẽ gồm các từ mà nó chứa
trong đó, chính vì vậy phương pháp này được gọi là biểu diễn túi - các - từ.
….
1
LSI 1
LSI

Hình 1.2: Biểu diễn văn bản theo túi - các - từ

16
1.3.4. Mô hình LSI
LSI đánh chỉ số ngữ nghĩa tiềm năng, là phương pháp được áp dụng
nhiều trong bài toán phân lớp. Ý tưởng chính của phương pháp này là, ánh xạ
mỗi văn bản vào một tập không gian ít chiều hơn, trong đó mỗi chiều được
gắn với một khái niệm. Như vậy bản chất của phương pháp này là chuyển từ
không gian các từ khóa sang không gian các khái niệm.
1.4. PHƢƠNG PHÁP LỰA CHỌN TỪ TRONG BIỂU DIỄN VĂN BẢN
1.4.1. Loại bỏ từ dừng
Trước hết có thể quan sát thấy rằng, trong một văn bản có nhiều từ chỉ
dùng để phục vụ cho biểu diễn cấu trúc câu, chứ không biểu đạt nội dung của
nó, chẳng hạn như các giới từ, từ nối,… Những từ xuất hiện nhiều trong văn
bản mà không có liên quan gì tới nội dung văn bản. Có thể loại bỏ những từ
như vậy, nó được xem như là những từ dừng.
1.4.2. Thu gọn đặc trƣng biểu diễn
Với các tài liệu văn bản, mỗi một từ khóa duy nhất sẽ biểu diễn một
chiều trong không gian biểu diễn. Do đó, kích thước của không gian biểu diễn
văn bản thường rất lớn, việc tính toán sẽ tốn nhiều thời gian.
Thêm nữa, một tài liệu văn bản khi được biểu diễn dưới dạng một
vector, thì số lượng các phần tử trong vector đó có giá trị 0 là rất lớn, điều này

nhỏ được đưa ra bởi Zipf năm 1949.
Gọi tổng số tần số xuất hiện của từ t trong tài liệu D là f
t
. Sau đó sắp
xếp tất cả các từ trong tập hợp theo chiều giảm dần của tần số xuất hiện f
t
, và
gọi thứ hạng của mỗi từ là r
t
.
Định luật Zipf được phát biểu dưới dạng công thức như sau:
r
t
. f
t
≈ K (với K là một hằng số). Hay r
t
. ≈ K/ f
t18
Phương pháp này được sử dụng phổ biến là lược bỏ những từ có tần
số xuất hiện thấp (từ 1 đến 3 lần) trong văn bản tùy theo từng ứng dụng cụ
thể, và loại bỏ những từ có tần số xuất hiện cao.
1.4.2.2. Thuật toán lựa chọn k đặc trưng tốt nhất [5]
Thuật toán lựa chọn đặc trưng cơ bản được mô tả ở hình 1.5 cho một
lớp c, tính toán một hàm tiện ích A (t, c) cho mỗi thuật ngữ trong tập từ vựng,
sau đó lựa chọn k thuật ngữ có giá trị A (t, c) là cao nhất. Tất cả các thuật ngữ
còn lại sẽ bị loại bỏ.
SELECT FEATURES (ID, c, k)
1. V EXTRACT VOCABULARY (ID)
(Trích rút tập từ vựng V từ tập văn bản)
2. L [] (Tập đặc trưng ban đầu gán là rỗng, L = ø)
3. for each t V (lấy mọi từ khóa t thuộc tập từ vựng V)
4. do A (t, c) COMPUTE FEATURE UTILITY (id, t, c) (Tính hàm
tiễn ích đặc trưng A(t, c) nhờ mỗi từ khóa t, mỗi chủ đề c, mỗi tập văn bản đã
đánh chỉ số id)
5. APPEND (L, A(t, c), t ) (đánh giá lựa chọn cho bộ (L, A(t, c), t ))
6. Return FEATURESWITHLARGESTVALUES (L, k) (trả về tập
đặc trưng L với k đặc trưng tốt nhất, có A(t, c) lớn nhất).
Hình 1.4. Thuật toán lựa chọn đặc trưng cơ bản
cho việc lựa chọn k đặc trưng tốt nhất

1.4.2.3. Thông tin tương hỗ [5]
Một phương pháp lựa chọn đặc trưng phổ biến để tính toán A (t, c) là
thông tin tương hỗ MI của thuật ngữ t với lớp c. MI đo mức độ thông tin (xuất
hiện/không xuất hiện) của thuật ngữ t góp phần làm cho quyết định quá trình
phân lớp đúng đắn trên lớp c.

20
Công thức của MI là:

NN
Log
N
NN
NN
Log
N
NN
NN
Log
N
NN
NN
Log
N
0 0
00
2
00
0 1
10
2
10
1 0
01
2
01
1 1
11
2

01
+ N
10
+ N
00
.
Để lựa chọn k các thuật ngữ: t
1
, …, t
k
cho bởi lớp nào đó, sử dụng
thuật toán lựa chọn đặc trưng trong hình 1.4, tính toán các hàm tiện ích cho tất
cả các thuật ngữ A (t, c) = I (U
t
, C
c
) và sau đó lựa chọn k thuật ngữ có các giá
trị lớn nhất.
1.4.2.4. Giải thuật Apriori [3]
Giải thuật này được sử dụng để lựa chọn đặc trưng (tập dữ liệu thường xuyên)
Thuật toán này sử dụng các k-itemset (tập thuật ngữ gồm k items) để
thăm dò (k+1)-itemset và qua đó khai thác được toàn bộ các tập thuật ngữ
thường xuyên (Fls) trong tập dữ liệu.
- Đầu tiên tính 1-itemsets, 2-itemsets và sau đó là 3-itemsets…

21
- Khi tính toán (k+1)-itemsets, chỉ xét những (k+1)-itemsets mà tất cả các
tập con có độ dài k đã được xác định là thường xuyên (đặc trưng) ở bước trước.
Mô tả giải thuật Apriori:
Biến C

L
k+1
= các ứng cử viên trong C
k+1
có GS > min_support
End
Return Tập các

L
k

1.5. ĐỘ LIÊN QUAN GIỮA CÁC VĂN BẢN
Độ liên quan giữa hai văn bản là một đại lượng đo mức độ giống nhau
về mặt nội dung giữa hai văn bản đó.
Phương pháp đánh giá độ liên quan theo tần xuất xuất hiện thuật ngữ,
không quan tâm đến thứ tự sắp xếp của các thuật ngữ trong văn bản mà chỉ
quan tâm đến số lần nó xuất hiện trong văn bản đó. Ví dụ: phương pháp sử
dụng hệ số consine, Độ tương tự giữa hai vector văn bản X = {x
1,
x
2, …,
x
m
} và
Y = { y
1,
y
2, …,
y
m

, j = 1…m, là là các tần số xuất hiện của các
từ khóa trong từng văn bản.
1.6. PHÂN LỚP VĂN BẢN
Phân lớp văn bản là một trong những bài toán cơ bản trong khai phá
dữ liệu văn bản [5].
- Bài toán phân lớp văn bản: là việc gán tên các chủ đề (tên lớp/nhãn
lớp) đã được xác định trước, vào các văn bản dựa trên nội dung của chúng.
- Phân lớp là công việc được sử dụng để hỗ trợ trong quá trình tìm
kiếm thông tin, chiết lọc thông tin, lọc văn bản hoặc tự động dẫn đường cho
các văn bản tới những chủ đề xác định trước. Hình 1.5. Mô tả bài toán phân lớp
- Để phân lớp văn bản tự động thường sử dụng các kỹ thuật học máy
có giám sát, dữ liệu văn bản đã được phân lớp bằng tay, được chia thành hai
phần: Tập huấn luyện hay tập mẫu và tập kiểm thử (kiểm tra), tập mẫu chiếm
2/3 dữ liệu, tập kiểm thử 1/3 dữ liệu còn lại. Đầu tiên hệ thống được huấn
luyện (học) thông qua tập mẫu, Sau đó đánh giá hiệu quả của hệ thống thông
qua các dữ liệu kiểm thử.
- Các hệ thống phân lớp có thể ứng dụng trong việc phân loại tài liệu
của các thư viện điện tử, phân loại văn bản báo chí trên các trang tin điện tử,…
những hệ thống tốt, cho ra kết quả rất khả quan, giúp ích nhiều cho con người.

23

Các công cụ
phân lớp Làm giảm số chiều
hoăc lựa chọn thuộc tính
Biểu diễn cuối
Hình 1.6. Lược đồ chung quá trình xây dựng bộ phân lớp văn bản

Biểu diễn ban đầu

24
- Sử dụng mô hình đã được xây dựng để phân lớp dữ liệu mới.
Đại lượng đánh giá hiệu suất phân lớp:
Việc đánh giá độ phân lớp dựa trên việc áp dụng mô hình đối với các
dữ liệu thuộc tập dữ liệu kiểm tra D
test
, sử dụng mô hình cho từng trường hợp
dữ liệu ở D
test
mà kết quả đầu ra là lớp c dự báo cho từng dữ liệu.
Hai độ đo được dùng phổ biến để đánh giá chất lượng của thuật toán
phân lớp là độ hồi tưởng p và độ chính xác . Ngoài ra, một số độ đo kết hợp
được xây dựng từ các độ đo này cũng được sử dụng, trong đó điển hình nhất
là độ đo f
1
(nhiều trường hợp bỏ qua trị số 1). Phần dưới đây trình bày các
tính toán chi tiết giá trị của các độ đo hồi tưởng và chính xác trong bài toán
phân lớp văn bản.
Xét trường hợp lực lượng của tập C các lớp trong bài toán lớn hơn hai,

Lớp c
Giá trị thực tế
Thuộc lớp c
Không thuộc lớp c
Giá trị qua
bộ phân lớp
Thuộc lớp c
TP
c

TN
c

Không thuộc lớp c
FP
c

FN
c

- FP
c
: (false positives): số lượng ví dụ dương được thuật toán phân lớp
gán cho giá trị sai là không thuộc lớp c.
- FN
c
: (false negatives): số lượng ví dụ âm được thuật toán phân lớp
gán cho giá trị sai là không thuộc lớp c.

25

c
p
K
1
1

Độ chính xác trung bình thô

M
=
k
c
c
K
1
1

Độ hồi tưởng trung bình mịn:
ρ
M
=
k
c
cc
k
c
c
FPTP
TP
1