ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
------------------------

NGUYỄN THỊ THOA
“PHÂN LỚP QUAN ĐIỂM KHÁCH HÀNG VÀ ỨNG DỤNG”

LUẬN VĂN THẠC SỸ

THÁI NGUYÊN – 2016


ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
-------------------------

NGUYỄN THỊ THOA
“PHÂN LỚP QUAN ĐIỂM KHÁCH HÀNG VÀ ỨNG DỤNG”

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ
CHUYÊN NGÀNH: 60.48.01.01

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS ĐOÀN VĂN BAN

THÁI NGUYÊN - 2016


MỤC LỤC
CHƯƠNG 1 – PHÂN LỚP DỮ LIỆU ........................................................................3
1.1 Giới thiệu về phân lớp dữ liệu..........................................................................3

1.2 Quá trình phân lớp dữ liệu ...............................................................................4
1.3 Các vấn đề liên quan đến phân lớp dữ liệu ......................................................8
1.3.1 Chuẩn bị dữ liệu cho việc phân lớp .............................................................8
1.3.2 So sánh các mô hình phân lớp .....................................................................9
1.3.3 Các phương pháp đánh giá độ chính xác của mô hình phân lớp ...............10
1.4 Kết luận chương 1 ..........................................................................................11
CHƯƠNG 2 – MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN..............12
2.1 Xử lý văn bản .................................................................................................12
2.1.1 Đặc điểm của từ trong tiếng việt................................................................12
2.1.2 Tách từ .......................................................................................................13
2.2 Biểu diễn văn bản ...........................................................................................18
2.2.1 Mô hình logic .............................................................................................18
2.2.2 Mô hình phân tích cú pháp ........................................................................19
2.2.3 Mô hình không gian vector ........................................................................20
2.2.4 Mô hình Boolean .......................................................................................22
2.2.5 Mô hình tần suất ........................................................................................23
2.3 Độ tương đồng................................................................................................25
2.3.1 Khái niệm độ tương đồng ..........................................................................25
2.3.2 Độ tương đồng ...........................................................................................26
2.3.3 Các phương pháp tính độ tương đồng .......................................................26
2.4 Các phương pháp phân loại văn bản ..............................................................29


2.4.1 Phương pháp pháp Naïve Bayes (NB) .......................................................29
2.4.2 Phương pháp Support Vector Machine (SVM) .........................................31
2.4.3 Phương pháp K-Nearest Neighbor (K-NN) ...............................................35
2.4.4 Phương pháp Linear Least Square Fit (LLSF) ..........................................37
2.4.5 Phương pháp Centroid – based vector .......................................................38
2.4.6 Kết luận ......................................................................................................38
2.5 Kết luận chương 2............................................................................................40

CHƯƠNG 3 – CHƯƠNG TRÌNH THỬ NGHIỆM .................................................41
3.1 Xây dựng mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website
dựa trên SVM ...........................................................................................41
3.1.1 Phát biểu bài toán .....................................................................................41
3.1.2 Mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website dựa
trên SVM .....................................................................................................41
3.2 Yêu cầu phần cứng và phần mềm ....................................................................44
3.2.1 Cấu hình máy thực nghiệm.......................................................................44
3.2.2 Công cụ và phần mềm sử dụng ................................................................44
3.3 Một số kết quả và đánh giá ..............................................................................45
3.3.1 Kết quả thử nghiệm ..................................................................................45
3.3.2 Đánh giá kết quả .......................................................................................56
3.4 Kết luận chương 3............................................................................................57
KẾT LUẬN VÀ ĐỀ NGHỊ .......................................................................................58


DANH MỤC HÌNH ẢNH
Hình 1.1 Quy trình phân loại văn bản [3] ........................................................ 4
Hình 1.2 Bước xây dựng mô hình phân lớp - Training..................................... 5
Hình 1.3 Ước lượng độ chính xác của mô hình ................................................ 6
Hình 1.4 Phân lớp dữ liệu mới .......................................................................... 7
Hình 1.5 Ước lượng độ chính xác của mô hình phân lớp bằng phương pháp
holdout............................................................................................................. 10
Hình 2.1 Biểu diễn vector văn bản trong không gian 2 chiều ........................ 21
Hình 2.2 Mô hình SVM [18]........................................................................... 32
Hình 2.3 Margin - khoảng cách của các điểm tới biên ................................... 32
Hình 2.4 Mô hình SVM trong không gian ...................................................... 33
Hình 2.5 Mô hình thuật toán K-NN ................................................................ 35
Hình 3.1 Sơ đồ xử lý dữ liệu ........................................................................... 41
Hình 3.2 Giao diện Weka ................................................................................ 45

Hình 3.3 Chuyển đổi dữ liệu sang .arff ........................................................... 50
Hình 3.4 vector hóa dữ liệu ............................................................................. 51
Hình 3.5 Giao diện huấn luyện ....................................................................... 55
Hình 3.6 Kết quả huấn luyện........................................................................... 55

DANH MỤC BẢNG BIỂU
Bảng 2.1 Biểu diễn văn bản trong mô hình Logic .......................................... 18
Bảng 2.2 Biểu diễn văn bản mô hình Vector .................................................. 21
Bảng 2.3 Biểu diễn văn bản mô hình Boolean................................................ 22
Bảng 3.1 kết quả huấn luyện và kiểm thử ....................................................... 56


6

MỞ ĐẦU
I.

ĐẶT VẤN ĐỀ
Hầu hết các doanh nghiệp đều luôn muốn quan tâm đến ý kiến, phản hồi của khách

hàng về sản phẩm, dịch vụ của họ như thế nào. Các đánh giá của khách hàng một mặt giúp
cho những người dùng khác định hướng trong việc chọn lựa sản phẩm, mặt khác giúp cho
các doanh nghiệp định hướng cải tiến chất lượng. Số lượng đánh giá về một sản phẩm mà
chúng ta nhận được ngày càng tăng và có thể đến từ nhiều nguồn khác nhau (web bán
hàng, diễn đàn, blog, mạng xã hội ...). Vì vậy, để có thể tổng hợp ý kiến phản hồi của
khách hàng về chất lượng, thì phải tự động hóa được công việc thu thập và phân tích đánh
giá.
Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trước những khao
khát tri thức của con người. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan
tâm các nhà nghiên cứu trong nhiều lĩnh vực khác nhau như học máy (machine learning),

hệ chuyên gia (expert system), thống kê (statistics) ... Công nghệ này cũng ứng dụng trong
nhiều lĩnh vực thực tế như: thương mại, nhà băng, maketing, nghiên cứu thị trường, bảo
hiểm, y tế, giáo
dục ...
Phân lớp văn bản là bài toán cơ bản trong khai phá quan điểm. Các hệ thống phân
lớp văn bản là các hệ thống phải có khả năng xác định, khai phá ra nội dung thông tin. Có
thể coi phân lớp quan điểm là bài toán phân lớp văn bản theo hai lớp tích cực và tiêu cực.
Do đó tôi chọn đề tài “Đánh giá sản phẩm trên các website thương mại điện tử
dựa trên nhận xét của người dùng trên internet” đề tài nghiên cứu một số kỹ thuật phân
lớp văn bản như K-means, Naïve Bayes, Maximum entropy và SVM để sử dụng trong
phương pháp học máy phân lớp quan điểm khách hàng.


II.

ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU
 Đối tượng nghiên cứu:
Các kỹ thuật phân lớp văn bản và ứng dụng để phân lớp quan điểm khách
hàng đưa vào các website TMĐT bán hàng trực tuyến với số lượng truy cập và giao
dịch lớn.
 Phạm vi nghiên cứu
Nghiên cứu các tài liệu bài viết trong và ngoài nước về kỹ thuật phân lớp dữ
liệu để xây dựng phát triển bài toán “Phân lớp quan điểm khách hàng và ứng dụng”
hiệu quả trong công việc phân tích, khai thác các nguồn ý kiến khách hàng.

III.

HƯỚNG NGHIÊN CỨU CỦA ĐỀ TÀI
-


Đề tài sẽ kết hợp phương pháp nghiên cứu lý thuyết với kết quả thực nghiệm.

- Phân tích các tài liệu và thông tin liên quan.
- Mô phỏng và thử nghiệm.
IV.

PHƯƠNG PHÁP NGHIÊN CỨU
Nghiên cứu lý thuyết dựa trên các tài liệu về phân lớp dữ liệu, các thuật toán,

phương pháp phân lớp … của các tác giả trong và ngoài nước. Thực nghiệm dựa trên các
website TMĐT để xây dựng, đánh giá phương pháp.


CHƯƠNG 1 – PHÂN LỚP DỮ LIỆU
1.1 Giới thiệu về phân lớp dữ liệu
Bài toán phân lớp quan điểm
Là quá trình phân lớp một đối tượng dữ liệu vào một hay nhiều lớp cho trước nhờ
một mô hình phân lớp mà mô hình này được xây dựng dựa trên một tập hợp các đối tượng
dữ liệu đã được gán nhãn từ trước gọi là tập dữ liệu học (tập huấn luyện). Quá trình phân
lớp còn được gọi là quá trình gán nhãn cho các đối tượng dữ liệu [5][3].
Như vậy, nhiệm vụ của bài toán phân lớp dữ liệu là cần xây dựng mô hình (bộ)
phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc
lớp nào.
Có nhiều bài toán phân lớp dữ liệu, như phân lớp nhị phân, phân lớp đa lớp, phân
lớp đa trị,….
Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vào một trong hai
lớp khác nhau dựa vào việc dữ liệu đó có hay không một số đặc tính theo quy định của bộ
phân lớp.
Phân lớp đa lớp là quá trình phân lớp với số lượng lớp lớn hơn hai. Như vậy, tập
hợp dữ liệu trong miền xem xét được phân chia thành nhiều lớp chứ không đơn thuần chỉ

là hai lớp như trong bài toán phân lớp nhị phân. Về bản chất, bài toán phân lớp nhị phân là
trường hợp riêng của bài toán phân lớp đa
lớp.
Trong phân lớp đa trị, mỗi đối tượng dữ liệu trong tập huấn luyện cũng như các đối
tượng mới sau khi được phân lớp có thể thuộc vào từ hai lớp trở lên. Ví dụ như trang web
về việc bùng phát bệnh cúm gia cầm, thủy cầm tại một số tính phía Bắc vừa thuộc về lĩnh
vực y tế liên quan đến lây bệnh sang người nhưng cũng thuộc về lĩnh vực kinh tế liên quan
đến ngành chăn nuôi…


Trong những trường hợp như vậy, việc sắp xếp một tài liệu vào nhiều hơn một lớp là phù
hợp với yêu cầu thực tế.
1.2 Quá trình phân lớp dữ liệu
Huấn luyện

Kiểm tra

Nhãn
Tệp đầu vào

Tập dữ liệu
Học

Tệp trích rút

máy

Tệp trích rút

Phân lớp


Kết quả

Hình 1.1 Quy trình phân loại văn bản [3]
Quá trình phân lớp dữ liệu thường gồm hai bước: xây dựng mô hình (tạo bộ phân
lớp) và sử dụng mô hình đó để phân lớp dữ liệu.
Bước 1 Bước xây dựng mô hình phân lớp (Training)
Một mô hình sẽ được xây dựng dựa trên việc phân tích các đối tượng dữ liệu đã
được gán nhãn từ trước. Tập các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện
(training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định bởi con người
trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát
(supervised learning). Trong bước này, chúng ta còn phải tính độ chính xác của mô hình,
mà cần phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính xác là chấp
nhận được (tức là cao), mô hình sẽ được sử dụng để xác định nhãn lớp cho các dữ liệu khác
mới trong tương lai. Trong việc test mô hình, sử dụng các độ đo để đánh giá chất


lượng của tập phân lớp, đó là độ hồi tưởng, độ chính xác, độ đo F1 ... Nội dung chi tiết về
các độ đo này được trình bày trong mục.
Tồn tại nhiều phương pháp phân lớp dữ liệu để giải quyết bài toán phân lớp tùy
thuộc vào cách thức xây dựng mô hình phân lớp như phương pháp Bayes, phương pháp
cây quyết định, phương pháp k-người láng giềng gần nhất, phương pháp máy hỗ trợ vector
.... Các phương pháp phân lớp khác nhau chủ yếu về mô hình phân lớp. Mô hình phân lớp
còn được gọi là thuật toán phân
lớp.

Thuật
toán
phân lớp
Dữ liệu huấn luyện


Tuổi
20
18
40
50
35
30
30
40

Xe
Combi
Sports
Sports
Family
Minivan
Combi
Family
Combi

Giàu
Cao
Cao
Cao
thấp
thấp
cao
thấp
thấp


Phân lớp

Nếu tuổi < 31
hoặc Xe = sport
thì Giàu = cao

Hình 1.2 Bước xây dựng mô hình phân lớp - Training
Bước 2 Phân lớp (classification)
Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu mới.
Trước tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra được ước
lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác đó. Kỹ thuật này sử
dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp. Các mẫu này được chọn
ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu đào tạo. Độ chính xác của mô hình
trên tập dữ liệu kiểm tra


đã đưa là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp
đúng (so với thực tế). Nếu độ chính xác của mô hình được ước lượng dựa trên tập dữ liệu
đào tạo thì kết quả thu được là rất khả quan vì mô hình luôn có xu hướng “quá vừa” dữ
liệu. Quá vừa dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá
trình xây dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm
riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập
dữ liệu đào tạo. Nếu độ chính xác của mô hình là chấp nhận được, thì mô hình được sử
dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà giá trị của thuộc tính
phân
lớp là chưa biết.

Phân lớp
Dữ liệu huấn luyện


Tuổi

Xe

Giàu

27

Sports

Cao

34

Family

thấp

66

Family

Cao

44

Sports

Cao


Già
u
Cao
thấp
thấp
cao

Hình 1.3 Ước lượng độ chính xác của mô hình


Phân lớp

Dữ liệu
mới

Tuổi
Giàu
27

Xe
Sports

34

Minivan

55
34


Family
Sports

Già
u
Cao
thấp
thấp
cao

Hình 1.4 Phân lớp dữ liệu mới
Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định tới sự
thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp dữ liệu là tìm ra
được một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao và có khả năng mở
rộng được. Trong đó khả năng mở rộng được của thuật toán được đặc biệt trú trọng và phát
triển.
Có thể liệt kê ra đây các kỹ thuật phân lớp đã được sử dụng trong những
năm qua:
 Phân lớp cây quyết định (Decision tree classification)
 Bộ phân lớp Bayesian (Bayesian classifier)


Mô hình phân lớp K-hàng xóm gần nhất (K-nearest neighbor classifier)

 Mạng nơron
 Phân tích thống kê
 Các thuật toán di truyền
 Phương pháp tập thô (Rough set Approach)



1.3 Các vấn đề liên quan đến phân lớp dữ liệu
1.3.1 Chuẩn bị dữ liệu cho việc phân lớp
Việc tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể thiếu và có
vai trò quan trọng quyết định tới sự áp dụng được hay không của mô hình phân lớp. Quá
trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu quả và khả năng mở rộng
được của mô hình phân lớp.
Quá trình tiền xử lý dữ liệu gồm có các công việc sau:
i. Làm sạch dữ liệu
Làm sạch dữ liệu liên quan đến việc xử lý với lỗi (noise) và giá trị thiếu (missing
value) trong tập dữ liệu ban đầu. Noise là các lỗi ngẫu nhiên hay các giá trị không hợp lệ
của các biến trong tập dữ liệu. Để xử lý với loại lỗi này có thể dùng kỹ thuật làm trơn.
Missing value là những ô không có giá trị của các thuộc tính. Giá trị thiếu có thể do lỗi chủ
quan trong quá trình nhập liệu, hoặc trong trường hợp cụ thể giá trị của thuộc tính đó
không có, hay không quan trọng. Kỹ thuật xử lý ở đây có thể bằng cách thay giá trị thiếu
bằng giá trị phổ biến nhất của thuộc tính đó hoặc bằng giá trị có thể xảy ra nhất dựa trên
thống kê. Mặc dù phần lớn thuật toán phân lớp đều có cơ chế xử lý với những giá trị thiếu
và lỗi trong tập dữ liệu, nhưng bước tiền xử lý này có thể làm giảm sự hỗn độn trong quá
trình học (xây dựng mô hình phân lớp).
ii. Phân tích sự cần thiết của dữ liệu
Có rất nhiều thuộc tính trong tập dữ liệu có thể hoàn toàn không cần thiết hay liên
quan đến một bài toán phân lớp cụ thể. Ví dụ dữ liệu về ngày trong tuần hoàn toàn không
cần thiết đối với ứng dụng phân tích độ rủi ro của các khoản tiền cho vay của ngân hàng,
nên thuộc tính này là dư thừa. Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ
những thuộc tính không cần thiết, dư thừa khỏi quá trình học vì những thuộc tính đó sẽ
làm chậm, phức tạp và


gây ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng
được.
iii. Chuyển đổi dữ liệu

Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết trong quá
trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục (continuous
attribute hay numeric attribute). Ví dụ các giá trị số của thuộc tính thu nhập của khách
hàng có thể được khái quát hóa thành các dãy giá trị rời rạc: thấp, trung bình, cao. Tương
tự với những thuộc tính rời rạc (categorical attribute) như địa chỉ phố có thể được khái quát
hóa lên thành thành phố. Việc khái quát hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy
các thao tác vào/ ra liên quan đến quá trình học sẽ giảm.
1.3.2 So sánh các mô hình phân lớp
Trong từng ứng dụng cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc lựa chọn
đó căn cứ vào sự so sánh các mô hình phân lớp với nhau, dựa trên các tiêu chuẩn sau:
1/ Độ chính xác dự đoán (predictive accuracy)
Độ chính xác là khả năng của mô hình để dự đoán chính xác nhãn lớp của dữ liệu
mới hay dữ liệu chưa biết.
2/ Tốc độ (speed)
Tốc độ là những chi phí tính toán liên quan đến quá trình tạo ra và sử
dụng mô hình.
3/ Sức mạnh (robustness)
Sức mạnh là khả năng mô hình tạo ta những dự đoán đúng từ những dữ
liệu noise hay dữ liệu với những giá trị thiếu.
4/ Khả năng mở rộng (scalability)
Khả năng mở rộng là khả năng thực thi hiệu quả trên lượng lớn dữ liệu của mô hình
đã học.


5/ Tính hiểu được (interpretability)
Tính hiểu được là mức độ hiểu và hiểu rõ những kết quả sinh ra bởi mô
hình đã học.
6/ Tính đơn giản (simplicity)
Tính đơn giản liên quan đến kích thước của cây quyết định hay độ cô
đọng của các luật.

1.3.3 Các phương pháp đánh giá độ chính xác của mô hình phân lớp
Ước lượng độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán
được độ chính xác của các kết quả phân lớp những dữ liệu tương lai. Độ chính xác còn
giúp so sánh các mô hình phân lớp khác nhau. Khóa luận này đề cập đến hai phương pháp
đánh giá phổ biến là holdout và k-fold kiểm tra chéo. Cả hai kỹ thuật này đều dựa trên các
phân hoạch ngẫu nhiên tập dữ liệu ban đầu.
Trong phương pháp holdout, dữ liệu dưa ra được phân chia ngẫu nhiên thành hai
phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thường 2/3
dữ liệu cấp cho tập dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm tra.

Tệp huấn
luyện

Mô hình
phân lớp

Độ chính xác
phân loại

Dữ liệu

Tệp kiểm tra
Hình 1.5 Ước lượng độ chính xác của mô hình phân lớp bằng phương
pháp holdout


Trong phương pháp k-fold xác nhận chéo tập dữ liệu ban đầu được chia ngẫu nhiên
thành k tập con (fold) có kích thước xấp xỉ nhau S1, S2, …, Sk. Quá trình học và test được
thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ
liệu đào tạo. Có nghĩa là, đâu tiên việc dạy được thực hiện trên các tập S2, S3, …, sau đó

test trên tập S1; tiếp tục quá trình dạy được thực hiện trên tập S1, S3, S4, …, sau đó test
trên tập S2; và cứ thế tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia
cho tổng số mẫu của tập dữ liệu ban đầu.
1.4 Kết luận chương 1
Trong chương I đã trình bày về bài toán phân lớp quan điểm, mô hình phân lớp dữ
liệu và quá trình phân lớp dữ liệu. Đồng thời cũng đưa ra các vấn đề trong phân lớp dữ liệu
như chuẩn bị dữ liệu trước khi phân lớp, giới thiệu một số tiêu chí so sánh và đánh giá độ
chính xác của các thuật toán phân lớp dữ liệu.


CHƯƠNG 2 – MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN
2.1 Xử lý văn bản
2.1.1 Đặc điểm của từ trong tiếng việt
Tiếng Việt là ngôn ngữ đơn lập [3][11]. Đặc điểm này bao quát tiếng Việt cả về
mặt ngữ âm, ngữ nghĩa, ngữ pháp. Khác với các ngôn ngữ châu Âu, mỗi từ là một nhóm
các ký tự có nghĩa được cách nhau bởi một khoảng trắng. Còn tiếng Việt, và các ngôn ngữ
đơn lập khác, thì khoảng trắng không phải là căn cứ để nhận diện từ.
Tiếng:
 Trong tiếng Việt trước hết cần chú ý đến đơn vị xưa nay vẫn quan gọi là tiếng.
Về mặt ngữ nghĩa, ngữ âm, ngữ pháp, đều có giá trị quan trọng.
 Sử dụng tiếng để tạo từ có hai trường hợp:
 Trường hợp một tiếng: đây là trường hợp một tiếng được dùng làm một từ,
gọi là từ đơn. Tuy nhiên không phải tiếng nào cũng tạo thành một từ.
 Trường hợp hai tiếng trở lên: đây là trường hợp hai hay nhiều tiếng kết hợp
với nhau, cả khối kết hợp với nhau gắn bó tương đối chặt chẽ, mới có tư
cách ngữ pháp là một từ. Đây là trường hợp từ ghép
hay từ phức.
Từ:
Có rất nhiều quan niệm về từ trong tiếng Việt, từ nhiều quan niệm về từ tiếng Việt
khác nhau đó chúng ta có thể thấy đặc trưng cơ bản của "từ" là sự hoàn chỉnh về mặt nội

dung, từ là đơn vị nhỏ nhất để đặt câu.
Người ta dùng "từ" kết hợp thành câu chứ không phải dùng "tiếng", do đó quá trình
tách câu thành các "từ" cho kết quả tốt hơn là tách câu bằng “tiếng”.


2.1.2 Tách từ
2.1.2.1 Phương pháp Maximum Matching: Forward / Backward
Phương pháp so khớp tối đa (MM-Maximum Matching) hay còn gọi là LRMM Left Right Maximum Matching. Ở phương pháp này, chúng ta sẽ duyệt một ngữ hoặc câu
từ trái sang phải và chọn từ có nhiều âm tiết nhất có mặt trong từ điển và cứ thực hiện lặp
lại như vậy cho đến hết câu.
Dạng đơn giản của phương pháp dùng để giải quyết nhập nhằng từ đơn. Giả sử
chúng ta có một chuỗi ký tự C1, C2, …, Cn. Chúng ta sẽ áp dụng phương pháp từ đầu
chuỗi. Đầu tiên kiểm tra xem C1 có phải là từ hay không, sau đó kiểm tra xem C1C2 có
phải là từ hay không. Tiếp tục thực hiện như thế cho đến khi tìm được từ dài nhất .
Dạng phức tạp: Quy tắc của dạng này là phân đoạn từ. Thông thường người ta chọn
phân đoạn ba từ có chiều dài tối đa. Thuật toán bắt đầu từ dạng đơn giản, cụ thể là nếu phát
hiện ra những cách tách từ gây nhập nhằng, như ở ví dụ trên, giả sử C1 là từ và C1C2 cũng
là một từ, khi đó chúng ta kiểm tra ký tự kế tiếp trong chuỗi C1, C2, ..., Cn để tìm tất cả
các đoạn ba từ có bắt đầu với C1 hoặc C1C2.
Ví dụ : Giả sử chúng ta có được các đoạn sau:
- C1 C2 C3 C4
- C1C2 C3C4 C5
- C1C2 C3C4

C5 C6

Khi đó chuỗi dài nhất sẽ là chuỗi thứ ba. Do đó từ đầu tiên của chuỗi thứ ba (C1C2)
sẽ được chọn. Thực hiện các bước cho đến khi được chuỗi từ hoàn chỉnh.
Nhận xét :
Phương pháp này thực hiện tách từ đơn giản, nhanh và chỉ cần dựa vào từ điển để

thực hiện. Tuy nhiên, khuyết điểm của phương pháp này cũng chính


là từ điển, nghĩa là độ chính xác khi thực hiện tách từ phụ thuộc hoàn toàn vào
tính đủ, tính chính xác của từ điển.
2.1.2.2 Phương pháp Transformation – based Learning (TBL)
Phương pháp này tiếp cận dựa trên tập ngữ liệu đã đánh dấu. Theo cách tiếp cận
này để cho máy tính có thể nhận biết ranh giới giữa các từ để có thể tách từ chính xác,
chúng ta sẽ cho máy học các câu mẫu trong tập ngữ liệu đã được đánh dấu ranh giới giữa
các từ đúng. Chúng ta thấy phương pháp rất đơn giản, vì chỉ cần cho máy học các tập câu
mẫu và sau đó máy sẽ tự rút ra qui luật của ngôn ngữ và để từ đó sẽ áp dụng chính xác khi
có những câu đúng theo luật mà máy đã rút ra. Và để tách từ được hoàn toàn chính xác
trong mọi trường hợp thì đòi hỏi phải có một tập ngữ liệu tiếng Việt thật đầy đủ và phải
được huấn luyện lâu để có thể rút ra các luật đầy đủ.
2.1.2.3 Mô hình tách từ bằng WFST và mạng Neural
Mô hình mạng chuyển dịch trạng thái hữu hạn có trọng số Weighted Finit State
Transducer (WFST) đã được áp dụng trong tách từ từ năm 1996 [13]. Ý tưởng cơ bản là áp
dụng WFST với trọng số là xác suất xuất hiện của mỗi từ trong kho ngữ liệu. Dùng WFST
để duyệt qua các câu cần xét, khi đó từ có trọng số lớn nhất là từ được chọn để tách.
Phương pháp này cũng đã được sử dụng trong công trình đã được công bố của tác giả Đình
Điền năm 2001, tác giả đã sử dụng WFST kèm với mạng Neural để khử nhập nhằng khi
tách từ, trong công trình tác giả đã xây dựng hệ thống tách từ gồm tầng WFST để tách từ
và xử lý các vấn đề liên quan đến một số đặc thù riêng của ngôn ngữ tiếng Việt như từ láy,
tên riêng, ... và tầng mạng Neural dùng để khử nhập nhằng về ngữ nghĩa sau khi đã tách từ
(nếu có).
Chi tiết về hai tầng này như sau:
a. Tầng WFST gồm có 3 bước


Bước 1: Xây dựng từ điển trọng số: theo mô hình WFST, thao tác phân

đoạn từ được xem như là một sự chuyển dịch trạng thái có xác suất.
Chúng ta miêu tả từ điển D là một đồ thị biến đổi trạng thái hữu hạn có trọng số.
Giả sử:
 H là tập các từ chính tả tiếng Việt (còn gọi là “tiếng”)
- P là từ loại của từ .


Mỗi cung của D có thể là:
- Từ một phần tử của H tới một hần tử của H
-

Các nhãn trong D biểu diễn một chi phí được ước lượng theo công thức:
Cost = -log(f/N)

Trong đó: f là tần số của từ, N là kích thước tập mẫu.
Bước 2: Xây dựng các khả năng phân đoạn từ: Để giảm sự bùng nổ tổ hợp khi sinh
ra dãy các từ có thể từ một dãy các tiếng trong câu, tác giả đã đề xuất phương pháp kết hợp
dùng thêm từ điển để hạn chế sinh ra các bùng nổ tổ hợp, cụ thể là nếu phát hiện thấy một
cách phân đoạn từ nào đó không phù hợp (không có trong từ điển, không có phải là tứ láy,
không phải là danh từ riêng,…) thì tác giả loại bỏ các nhánh xuất phát từ cách phân đoạn
đoạn đó.
Bước 3: Lựa chọn khả năng phân đoạn từ tối ưu: Sau khi có được danh sách các
cách phân đoạn từ có thể có của câu, tác giả đã chọn trường hợp phân đoạn từ có trọng số
bé nhất.
b. Tầng mạng Neural
Mô hình được sử dụng để khử nhập nhằng khi tách từ bằng cách kết hợp so sánh
với từ điển.
Nhận xét: Mô hình này đạt được độ chính xác trên 97% theo như công bố trong
công trình của tác giả, bằng việc sử dụng thêm mạng Neural kết hợp với từ điển để khử
các nhập nhằng có thể có khi tách ra các được nhiều từ từ



một câu và khi đó tầng mạng Neural sẽ loại bỏ đi các từ không phù hợp bằng cách kết hợp
với từ điển. Bên cạnh đó, cũng tương tự như phương pháp TBL điểm quan trọng của mô
hình này cần tập ngữ liệu học đầy đủ.
2.1.2.4 Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải di
truyền
Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải di
truyền – IGATEC (Internet and Genetics Algorithm based Text Categorization for
Documents in Vietnamese) do H. Nguyễn đề xuất năm 2005 như một hướng tiếp cận mới
trong tách từ với mục đích phân loại văn bản mà không cần dùng đến một từ điển hay tập
ngữ liệu học nào. Trong hướng tiếp cận này, tác giả kết hợp giữa thuật toán di truyền với
dữ liệu thống kê được lấy từ Internet.
2.1.2.5 Loại bỏ từ dừng
Từ dừng (stop-words) dùng để chỉ các từ mà xuất hiện quá nhiều trong các câu văn
bản của toàn tập kết quả, thường thì không giúp ích gì trong việc phân biệt nội dung của
các tài liệu văn bản. Ví dụ, những từ “và”, “hoặc”, “cũng”, “là”, “mỗi”, “bởi”, …
2.1.2.6 Đặc trưng văn bản
Các phương pháp rút trích thông tin [6][11][16] cổ điển thì coi mỗi một văn bản
như là tập các từ khóa và gọi tập các từ khóa này là tập các term. Một phần tử trong tập
term thì đơn giản là một từ, mà ngữ nghĩa của từ này giúp tạo thành nên nội dung của văn
bản. Vì vậy, tập term được sử dụng để tạo các chỉ mục và tóm lược nội dung của văn bản.
Giả sử cho một tập term của một văn bản nào đó, chúng ta có thể nhận thấy rằng
không phải tất cả các từ trong tập term này đều có mức độ quan trọng như nhau trong việc
mô tả nội dung văn bản. Ví dụ, bây giờ chúng ta xét một tập gồm một trăm ngàn văn bản,
giả sử có một từ A nào đó xuất hiện trong một


trăm ngàn văn bản này thì chúng ta có thể khẳng định rằng từ A này không quan trọng và
chúng ta sẽ không quan tâm đến nó, bởi vì chắc chắn là nó sẽ không cho chúng ta biết được

về nội dung của các văn bản này. Vì vậy từ A sẽ bị loại ra khỏi tập các term, khi chúng ta
xây dựng tập term cho văn bản để miêu tả nội dung ngữ nghĩa của các văn bản này. Kết
quả này có được thông qua thao tác xác định trọng số cho mỗi một từ trong tập term của
một văn bản.
Đặt ki là từ thứ i trong tập term, dj là văn bản j, và wij >= 0 là trọng số của từ ki
trong văn bản dj. Giá trị của trọng số này thì rất là quan trọng trong việc miêu tả nội dung
của văn bản.
Đặt t là số luợng các từ trong tập term của hệ thống. K = {k1, k2, k3, …, kt} là tập
tất cả các từ trong tập term, trong đó ki là từ thứ i trong tập term. Trọng số wij > 0 là
trọng số của từ ki trong văn bản dj. Với mỗi một từ, nếu nó không xuất hiện trong văn bản
thì wij = 0. Do đó, văn bản dj thì được biểu diễn bằng vector dj, trong đó vector dj =
{wj1,wj2,wj3, ….,wjt }.
Các đặc trưng của văn bản khi biểu diễn dưới dạng vector:
- Số nhiều không gian đặc trưng thường lớn .
- Các đặc trưng độc lập nhau.
- Các đặc trưng rời rạc: vector đặc trưng di có thể có nhiều thành phần mang giá trị
0 do có nhiều đặc trưng không xuất hiện trong văn bản di (nếu chúng ta tiếp cận theo cách
sử dụng giá trị nhị phân 1, 0 để biểu diễn cho việc có xuất hiện hay không một đặc trưng
nào đó trong văn bản đang được biểu diễn thành vector), tuy nhiên nếu đơn thuần cách tiếp
cận sử dụng giá trị nhị phân 0, 1 này thì kết quả phân loại phần nào hạn chế là do có thể
đặc trưng đó không có trong văn bản đang xét nhưng trong văn bản đang xét lại có từ khóa
khác với từ đặc trưng nhưng có ngữ nghĩa giống với từ đặc trưng này, do đó một cách tiếp
cận khác là không sử dụng số nhị phân 0, 1 mà sử dụng giá trị số thực để phần nào giảm
bớt sự rời rạc trong vector văn bản.


2.2 Biểu diễn văn bản
Có nhiều cách biểu diễn văn bản [1], luận văn trình bày các phương pháp
biểu diễn văn bản phổ biến.
2.2.1 Mô hình logic

Theo mô hình này, các từ có nghĩa trong văn bản sẽ được đánh chỉ số và nội dung
văn bản được quản lý theo các chỉ số Index đó. Mỗi văn bản được đánh chỉ số theo quy tắc
liệt kê các từ có nghĩa trong các văn bản với vị trí xuất hiện của nó trong văn bản. Từ có
nghĩa là từ mang thông tin chính về các văn bản lưu trữ, khi nhìn vào nó, người ta có thể
biết chủ đề của văn bản cần biễu
diễn.
Tiến hành Index các văn bản đưa vào theo danh sách các từ khóa nói trên. Với mỗi
từ khóa người ta sẽ đánh số thứ tự vị trí xuất hiện của nó và lưu lại chỉ số đó cùng với mã
văn bản chứa nó. Cách biểu diễn này cũng được các máy tìm kiếm ưa dùng.
Ví dụ, có 2 văn bản với mã tương ứng là VB1, VB2:
- VB1 là: “Ngân hàng cổ phần thương mại”.
- VB2 là: “Công ty thương mại hàng hóa” Khi
đó, ta có cách biểu diễn như sau:
Bảng 2.1: Biểu diễn văn bản trong mô hình Logic
Từ mục

Mã VB_Vị trí XH

Ngân

VB1(1)

Hàng

VB1(2),VB2(5)

Cổ

VB1(3)


Phần

VB1(4)

Thương

VB1(5),VB2(3)


Mại

VB1(6)VB2(4)

Công

VB2(1)

Một số ưu điểm, nhược điểm
- Ưu điểm
Việc tìm kiếm trở nên nhanh và đơn giản. Thật vậy, giả sử cần tìm kiếm từ
“computer”. Hệ thống sẽ duyệt trên bảng Index để trỏ đến chỉ số Index tương ứng nếu từ
“computer” tồn tại trên hệ thống. Việc tìm kiếm này khá nhanh và đơn giản khi trước đó ta
đã sắp xếp bảng Index theo vẫn chữ cái. Phép tìm kiếm
trên có độ phức tạp cấp (

2

), với n là số từ trong bảng Index. Tương ứng

với chỉ số index trên sẽ cho ta biết các tài liệu chứa từ khóa tìm kiếm. Như vậy,

việc tìm kiếm liên quan đến k từ thì các phép toán cần thực hiện là k*n*log2n
(n là số từ trong bảng Index).
- Nhược điểm
Đòi hỏi người sử dụng phải có kinh nghiệm và chuyên môn trong lĩnh vực tìm
kiếm vì câu hỏi đưa vào dưới dạng Logic nên kết quả cũng có giá trị Logic (Boolean). Một
số tài liệu sẽ được trả lại khi thỏa mãn mọi điều kiện đưa vào. Như vậy muốn tìm được tài
liệu theo nội dung thì phải biết đích xác về tài
liệu.
Việc Index các tài liệu rất phức tạp và làm tốn nhiều thời gian, đồng thời
cũng tốn không gian để lưu trữ các bảng Index.
Các tài liệu tìm được không được sắp xếp theo độ chính xác của chúng. Các bảng
Index không linh hoạt vì khi các từ vựng thay đổi (thêm, sửa, xóa,
…) dẫn tới chỉ số Index cũng phải thay đổi theo.
2.2.2 Mô hình phân tích cú pháp


Trong mô hình này, mỗi văn bản đều phải được phân tích cú pháp và trả lại thông
tin chi tiết về chủ đề của văn bản đó. Sau đó, người ta tiến hành Index các chủ đề của từng
văn bản. Cách Index trên chủ đề cũng giống như Index trên văn bản nhưng chỉ Index trên
các từ xuất hiện trong chủ đề.
Các văn bản được quản lý thông qua các chủ đề này để có thể tìm kiếm
được khi có yêu cầu, câu hỏi tìm kiếm sẽ dựa trên các chủ đề trên.
Một số ưu điểm, nhược điểm của phương pháp này
- Ưu điểm
Tìm kiếm theo phương pháp này khá hiệu quả và đơn giản, do tìm kiếm nhanh và
chính xác.
Đối với những ngôn ngữ đơn giản về mặt ngữ pháp thì việc phân tích trên có thể
đạt được mức độ chính xác cao và chấp nhận được.
- Nhược điểm
Chất lượng của hệ thống theo phương pháp này hoàn toàn phụ thược vào chất lượng

của hệ thống phân tích cú pháp và đóan nhận nội dung tài liệu. Trên thực tế, việc xây dựng
hệ thống này rất phức tạp, phụ thuộc vào đặc điểm của từng ngôn ngữ và đa số chưa đạt
đến độ chính xác cao.
2.2.3 Mô hình không gian vector
Cách biểu diễn văn bản thông dụng nhất là thông qua vector biểu diễn theo mô hình
không gian vector (Vector Space Model). Đây là một cách biểu diễn tương đối đơn giản và
hiệu quả.