ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA

NGUYỄN THANH HẢI

RÚT TRÍCH CÁC BÌNH LUẬN TRÊN MẠNG XÃ HỘI
VỀ MỘT SỐ NHÂN VẬT NỔI TIẾNG ĐỂ PHÂN TÍCH,
ĐÁNH GIÁ CẢM XÚC CỦA NGƯỜI DÙNG VỀ HỌ

Chuyên ngành: Khoa học máy tính
Mã số: 8480101

LUẬN VĂN THẠC SĨ KỸ THUẬT

Người hướng dẫn khoa học: TS. TRƯƠNG NGỌC CHÂU

Đà Nẵng - Năm 2018


LỜI CAM ĐOAN
Tôi xin cam đoan:
- Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng
dẫn của Ts. Trương Ngọc Châu.
- Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng, trung
thực về tên tác giả, tên công trình, thời gian và địa điểm công bố.
- Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được
ai công bố trong bất kỳ công trình nào khác.

Tác giả luận văn

Nguyễn Thanh Hải

MỤC LỤC
TRANG BÌA
LỜI CAM ĐOAN
MỤC LỤC
TRANG TOM TẮT LUẬN VĂN
DANH MỤC CAC TỪ VIẾT TẮT
DANH MỤC CÁC HÌNH
MỞ ĐẦU ..................................................................................................................... 1
1. Tính cấp thiết của đề tài, ý nghĩa thực tiễn: ......................................................... 1
2. Mục tiêu nghiên cứu: ............................................................................................ 2
3. Đối tượng và phạm vi nghiên cứu: ....................................................................... 2
4. Phương pháp nghiên cứu đề tài: ........................................................................... 2
5. Ý nghĩa khoa học và thực tiễn: ............................................................................. 3
6. Dự kiến kết quả đạt được. .................................................................................... 3
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU............................................ 5
1.1. Khai phá dữ liệu ................................................................................................ 5
1.1.1. Khái niệm .................................................................................................... 5
1.1.2. Các bước trong quá trình khai phá dữ liệu .................................................. 6
1.1.3. Các hướng tiếp cận và kỹ thuật áp dụng trong khai phá dữ liệu ................. 7
1.1.4. Ứng dụng của khai phá dữ liệu ................................................................... 8
1.2. Khai phá dữ liệu Web ........................................................................................ 9
1.2.1. Khai phá dữ liệu web .................................................................................. 9
1.2.2. Lợi ích của khai phá dữ liệu web ................................................................ 9
1.2.3. Khó khăn ................................................................................................... 10
1.2.4. Thuận lợi ................................................................................................... 12
1.2.5. Các kiểu dữ liệu web ................................................................................. 13
1.3. Các thách thức trong khai phá dữ liệu ............................................................. 13
1.3.1. Các vấn đề về Cơ sở dữ liệu...................................................................... 13

1.3.2. Một số vấn đề khác ................................................................................... 15
1.4. Các phương pháp tách từ hiện nay .................................................................. 16


1.4.1. Phương pháp Maximum Matching ........................................................... 16
1.4.2. Phương pháp giải thuật học cải biến (Transformation-based Learning TBL) .................................................................................................................... 17
1.4.3. Mô hình tách từ bằng WFST và mạng Neural .......................................... 17
1.4.4. Phương pháp Quy hoạch động : chỉ sử dụng tập ngữ liệu thô để lấy thông
tin về tần số thống kê của từ, làm tăng độ tin cậy cho việc tính toán. ................ 18
1.5. Các công trình khai phá và xử lý dữ liệu đã được phát triển .......................... 18
1.6. Kết luận Chương 1 .......................................................................................... 19
CHƯƠNG 2: PHƯƠNG PHÁP RÚT TRÍCH DỮ LIỆU TỪ MẠNG XÃ HỘI VÀ
PHÂN LỚP DỮ LIỆU ............................................................................................... 20
2.1. Giới thiệu bài toán ........................................................................................... 20
2.2. Mạng xã hội ..................................................................................................... 20
2.2.1. Giới thiệu................................................................................................... 20
2.2.2. Các mạng xã hội phổ biến hiện nay .......................................................... 21
2.2.3. Mạng xã hội Twitter .................................................................................. 23
2.3. Phương pháp rút trích dữ liệu từ mạng xã hội Twitter .................................... 26
2.3.1. Twitter REST API ..................................................................................... 26
2.3.2. Các phương thức của REST API v1.1 ..................................................... 26
2.4. Lựa chọn giải pháp phân lớp dữ liệu ............................................................... 31
2.4.1. Support Vector Machine (SVM) ............................................................... 31
2.4.2. Phương pháp K-Neaest Neighbor (KNN) ................................................. 32
2.4.3. Phân loại Naïve Bayse (NB) ..................................................................... 33
2.4.4. Centroid- based vector .............................................................................. 35
2.4.5. Linear Least Square Fit (LLSF) ................................................................ 35
2.5. Kết luận Chương 2 .......................................................................................... 36
CHƯƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ ..................................................... 38
3.1. Hướng tiếp cận thực nghiệm ........................................................................... 38

3.2. Tiến hành thực nghiệm .................................................................................... 39
3.2.1. Môi trường thực nghiệm ........................................................................... 39
3.2.2. Bài toán ..................................................................................................... 39
3.2.3. Cài đặt các thành phần cần thiết: .............................................................. 40


3.2.4. Tiến hành các bước thực nghiệm .............................................................. 40
3.3. Đánh giá kết quả. ............................................................................................. 51
3.4. Kết luận Chương 3 .......................................................................................... 51
KẾT LUẬN................................................................................................................ 52
DANH MỤC TÀI LIỆU THAM KHẢO .................................................................. 53
QU ẾT Đ NH GIAO ĐỀ TÀI LUẬN VĂN THẠC S (BẢN SAO).
BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC
PHẢN BIỆN


TRANG TÓM TẮT TIẾNG ANH
RÚT TRÍCH CÁC BÌNH LUẬN TRÊN MẠNG XÃ HỘI
VỀ MỘT SỐ NHÂN VẬT NỔI TIẾNG ĐỂ PHÂN TÍCH, ĐÁNH GIÁ
CẢM XÚC CỦA NGƯỜI DÙNG VỀ HỌ

Học viên: Nguyễn Thanh Hải

Chuyên ngành: Khoa học máy tính

Mã số: 8480101 Khóa: 34.KMT.QB Trường Đại học Bách khoa - ĐHĐN
Tóm tắt Luận văn đã thu được một số kết quả nhất định và khái quát được những kiến
thức cơ bản về khai phá dữ liệu, khai phá dữ liệu trên nền WEB, đưa ra cái nhìn tổng quan về
mạng xã hội, các mạng xã hội phổ biến hiện nay đặc biệt là mạng xã hội Twitter, trình bày
phương pháp rút trích dữ liệu từ mạng xã hội Twitter và các giải pháp phân lớp dữ liệu. Viết

một ứng dụng Demo để lấy 200 tweet từ mạng xã hội Twitter với từ khóa là Tổng thống Mỹ
Donal Trump để phân tích, đánh giá cảm xúc của người đăng tweet hoặc của người dùng mạng
xã hội về một nhân vật cụ thể là Donal Trump. Nghiên cứu nâng cao hiệu quả, tính chính xác
của quá trình rút trích thông tin, đánh giá kết quả. Lấy thông tin từ đa người dùng của mạng xã
hội chứ không hạn chế một cá nhân cụ thể từ đó có thể đánh giá quan điểm của người dùng
mạng xã hội một cách chính xác hơn.
Từ khóa: Tổng thống Mỹ Donal Trump để phân tích, đánh giá cảm xúc của người đăng
tweet.
EXTRACTING COMMENTS ON SOCIAL MEDIA ABOUT A NUMBER OF
CELEBRITIES TO ANALYZE AND ASSESS USER FEELINGS ABOUT THEM
Abstract - The thesis has obtained some certain results and generalized the basic knowledge of
data mining, data mining on the WEB platform, giving an overview of social networks,
universal social networks The current variable, especially Twitter, presents data extraction
methods from Twitter and data classification solutions. Write a Demo application to get 200
tweets from the Twitter social network with the keyword US President Donal Trump to analyze
and assess the emotions of tweeters or social network users about a specific character, Donal
Trump. Research to improve efficiency, accuracy of information extraction process, evaluate
results. Get information from multi-users of social networks, not restricting a specific
individual from which to assess the views of social network users more accurately.
Key words: President Donal Trump to analyze and assess the emotions of tweeters


DANH MỤC CÁC TỪ VIẾT TẮT

KDD

Knowleadge Discovery in Database

CSDL


Cơ sở dữ liệu

KPDL

Khai phá dữ liệu

SVM

Support Vector Machine

NB

Naïve Bayse

KNN

K-nearest neighbors


DANH MỤC CÁC HÌNH
Hình 1.1: Các bước trong Datamining và KDD ...................................................... 6
Hình 1.2: Các bước trong khai phá dữ liệu ............................................................. 6
Hình 1.3: Phân loại dữ liệu web ............................................................................ 13
Hình 2.1: Siêu mặt phẳng h phân chia dữ liệu huấn huyện thành 2 lớp + và – với
khoảng cách biên lớn nhất. Các điểm gần h nhất là các vector hỗ trợ,
Support Vector (được khoanh tròn) .................................................. 31
Hình 3.1: Tạo app để truy xuất dữ liệu từ mạng xã hội Twitter............................ 41
Hình 3.2: Twitter App đã tạo xong........................................................................ 41
Hình 3.3: Các key cần thiết. .................................................................................. 42
Hình 3.4: Hiển thị chiều dài của các tweet theo thời gian..................................... 47

Hình 3.5: Hiển thị số lượt like và số lần retweet theo thời gian............................ 48
Hình 3.6: Hiển thị nguồn gốc của thiết bị dùng để đăng tweet ............................. 48


1

MỞ ĐẦU
1. Tính cấp thiết của đề tài, ý nghĩa thực tiễn:
Sự phát triển của khoa học công nghệ đã đem đến cho xã hội loài người
những thay đổi vượt bậc. Mỗi một đột phá trong lĩnh vực công nghệ lại tạo tiền
đề phát triển một loại hình truyền thông mới. Công nghệ mới đã dẫn đến những
phong cách và kiểu mẫu truyền thông mới. Trong khi Internet đang có một thời
đại phát triển bùng nổ, các hình thức truyền thông mới đang ngày càng thu hút
được đông đảo người xem. Những người dùng Internet - đặc biệt là giới trẻ, bắt
đầu tìm kiếm một nơi thỏa mãn mọi nhu cầu về thông tin, giải trí, kết nối… và
mạng xã hội ra đời, đáp ứng một cách gần như hoàn hảo những nhu cầu đó.
Hiện nay thế giới có hàng trăm mạng xã hội khác nhau như Facebook,
outube, Twitter, MySpace… Mỗi mạng xã hội có một sự thành công nhất định
dựa trên sự phù hợp với những yếu tố về địa lý, văn hóa… Twitter và
Facebook nổi tiếng nhất trong thị trường Bắc Mỹ và Tây Âu; Orkut và Hi5 tại
Nam Mỹ; Friendster tại Châu Á và các đảo quốc Thái Bình Dương.
Trong thời đại được gọi là “Thế giới phẳng”, không ai có thể phủ nhận lợi
ích từ mạng xã hội, đặc biệt là giới trẻ. Lượng thông tin chia sẻ thông qua mạng
xã hội là hết sức lớn và vô cùng phong phú, đa dạng dẫn đến số lượng người sử
dụng mạng xã hội ngày càng đông đảo. Vì vậy mà ảnh hưởng của mạng xã hội
đến việc truyền tải, tiếp nhận thông tin ngày càng lớn. Việc sở hữu 01 tài khoản
trên mạng xã hội ngày nay cũng đã trở thành thứ không thể thiếu với quá nhiều
người.
Sự bùng nổ, phát triển của công nghệ thông tin và mạng xã hội đã đem tới
cho người sử dụng một lượng dữ liệu khổng lồ nhưng thông tin mà chúng ta có,

cần thật sự rất ít. Các công cụ và kỹ thuật phân tích dữ liệu truyền thống cho việc
trích lọc thông tin hữu ích cho các quá trình nghiên cứu, khảo sát nắm bắt thông
tin, kinh doanh, … thì không hiệu quả cho một tập dữ liệu rất lớn và đa dạng về
mặt cấu trúc. Khai phá dữ liệu (data mining) là một lĩnh vực nghiên cứu quá trình
phân tích dữ liệu từ kho dữ liệu. Một trong các nội dung cơ bản nhất trong khai
phá dữ liệu và rất phổ biến là khai phá dữ liệu web. Kỹ thuật khai phá dữ liệu này
cho phép trích xuất tri thức từ cơ sở dữ liệu khổng lồ, phương pháp này cho phép
trích xuất ra nhiều thông tin hữu ích về các đối tượng cụ thể, các cá nhân nổi


2

tiếng như: các chính trị gia, ca sỹ,….
Việc nắm bắt được các thông tin hữu ích từ mạng xã hội, có những nhận
xét tích cực lẫn tiêu cực về các cá nhân là “người nổi tiếng” sẽ giúp các tổ chức
(chính phủ hoặc phi chính phủ), công ty quản lý (đối với ca sỹ, ..)……có thể
thăm dò đánh giá, phản ứng của dư luận về các cá nhân chịu sự quản lý của mình.
Trên cơ sở đó, tôi chọn đề tài “Rút trích các bình luận trên mạng xã hội
về một số nhân vật nổi tiếng để phân tích, đánh giá cảm xúc của người dùng
về họ” để làm luận văn tốt nghiệp.
Luận văn này sẽ minh họa cách làm thế nào để khai phá dữ liệu người dùng
trên mạng xã hội, làm thế nào để trích xuất các giá trị từ mạng xã hội. Nghiên cứu
này sẽ giải thích chi tiết về kịch bản, cách thức sử dụng API của mạng xã hội để
phân tích dữ liệu lớn.
2. Mục tiêu nghiên cứu:
Trên cơ sở lý thuyết về xử lý ngôn ngữ tự nhiên, phân tích từ vựng trong
đoạn văn bản, bước đầu xây dựng ứng dụng demo có thể phân tích ý kiến đánh
giá từ một đoạn văn bản.
Dữ liệu đầu vào của chương trình được khai thác từ các trang mạng xã hội
như Facebook, Twitter.

3. Đối tượng và phạm vi nghiên cứu:
- Đối tượng nghiên cứu: Người dùng có tài khoản và tương tác trên mạng
xã hội Twitter.
- Phạm vi nghiên cứu: Mạng xã hội Twitter, ngôn ngữ sử dụng là tiếng Anh
4. Phương pháp nghiên cứu đề tài:
- Tìm hiểu phương pháp khai thác dữ liệu từ mạng xã hội.
- Tìm hiểu các phương pháp phân lớp dữ liệu và phân loại văn bản: học
máy, SVM (support vector machine), KNN (K-Neaset Neighbor),....
- Tiến hành phân tích và xây dựng ứng dựng mô phỏng cho lý thuyết
nghiên cứu.
- Phân tích văn bản đã khai thác được từ mạng xã hội để xem văn bản đó
là mang ý nghĩa tích cực hay tiêu cực.


3

5. Ý nghĩa khoa học và thực tiễn:
- Ý nghĩa khoa học:
+ Đề xuất giải pháp thu thập dữ liệu người dùng thông qua API của mạng
xã hội.
+ Đề xuất kỹ thuật, đánh giá độ ổn định và khả năng phân tích dữ liệu
người dùng sử dụng mạng xã hội.
- Ý nghĩa thực tiễn:
+ Kết quả nghiên cứu sẽ giúp đánh giá sự quan tâm của người dùng về một
số nhân vật nổi tiếng mang tính tích cực hay tiêu cực.
+ Kết quả nghiên cứu sử dụng để khảo sát người dùng về một số nhân vật
nổi tiếng một cách khách quan hơn.
6. Dự kiến kết quả đạt được.
- Minh họa cách làm thế nào để khai phá dữ liệu người dùng trên mạng xã
hội, làm thế nào để trích xuất các giá trị từ mạng xã hội

- Xây dựng một ứng dụng demo có khả năng rút trích thông tin trên mạng
xã hội Twitter nhằm đánh giá phản ứng của người dùng.
7. Bố cục luận văn
Dựa trên những mục tiêu đã đề ra, ngoài các nội dung như mở đầu thì
luận văn sẽ được xây dựng với bố cục như sau:
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Chương này trình bày tổng quan về khai phá dữ liệu, các kỹ thuật khai phá
dữ liệu cũng như tính ứng dụng của nó trong các lĩnh vực đời sống, đặc biệt là dữ
liệu trên nền Web.
CHƯƠNG 2: CÁC PHƯƠNG PHÁP LẤY DỮ LIỆU TỪ MẠNG XÃ HỘI
Chương này trình bày tổng quan về các mạng xã hội phổ biến hiện nay, đặc
biệt là mạng xã hội Twitter. Tìm hiểu phương thức lấy dữ liệu từ mạng xã hội
Twitter bằng công cụ Twitter REST API. Sau đó, tìm hiểu các phương pháp phân
lớp dữ liệu như: SVM, NB, KNN, ...


4

CHƯƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ
Trên cơ sở tìm hiểu và phân tích các thuật toán liên quan, đặc biệt là thuật
toán NB, báo cáo khảo sát các phương pháp lấy dữ liệu và phân tích dữ liệu thu
được. Chương này xây dựng một ứng dụng demo được viết bằng ngôn ngữ lập
trình Python với bộ dữ liệu 200 tweet được lấy bằng Twitter Rest API.


5

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khai phá dữ liệu
1.1.1. Khái niệm

Khai phá dữ liệu (datamining) được định nghĩa như là một quá trình chắt
lọc hay khai phá tri thức từ một lượng lớn dữ liệu. Dataming được ví như công
việc "Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trước.
Thuật ngữ Datamining ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ
một số lượng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện được dùng cũng có
nghĩa tương tự với từ Datamining như Knowledge Mining (khai phá tri thức),
knowledge extraction (chắt lọc tri thức), data/patern analysis (phân tích dữ
liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging (nạo vét dữ liệu),...
Khai phá dữ liệu là một lĩnh vực mới được nghiên cứu, nhằm tự động khai
thác thông tin, tri thức mới hữu ích, tiềm ẩn từ những cơ sở dữ liệu lớn cho các
đơn vị, tổ chức, doanh nghiệp, .... từ đó thúc đẩy khả năng sản xuất, kinh doanh,
cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học cùng
với những ứng dụng thành công trong khai phá tri thức cho thấy khai phá dữ liệu
là một lĩnh vực phát triển bền vững và mang nhiều lợi ích hơn hẳn so với các
công cụ tìm kiếm phân tích dữ liệu truyền thống.
Khai phá dữ liệu là một bước chính quan trọng và mang tính quyết định
trong quá trình KDD (Knowleadge Discovery in Database) gồm 7 bước, cụ thể:
B1. Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu và
các dữ liệu không cần thiết.
B2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành
những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xử
lý (data cleaning & preprocessing).
B3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ
liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá
trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không đầy
đủ (incomplete data), .v.v.
B4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù
hợp cho quá trình xử lý.
B5. Khai phá dữ liệu(datamining): Là một trong các bước quan trọng nhất,



6

trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ
liệu.
B6. Ước lượng mẫu (knowledge evaluation): Quá trình đánh giá các kết
quả tìm được thông qua các độ đo nào đó.
B7. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng các
kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng.

Hình 1.1: Các bước trong Datamining và KDD
1.1.2. Các bước trong quá trình khai phá dữ liệu
Quá trình khai phá dữ liệu gồm các bước như sau:

Hình 1.2: Các bước trong khai phá dữ liệu


7

 Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.
 Xác định các dữ liệu liên quan dùng để xây dựng giải pháp giải quyết
nhiệm vụ bài toán.
 Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải
thuật khai phá dữ liệu có thể hiểu được.
 Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá
nhằm tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng với các ý
nghĩa đó. Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới
có thể đuợc đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá
trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri
thức (mối liên hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào).

Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo
độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu còn phải có khả năng sử dụng tiềm
tàng. Các mẫu này sau khi được xử lý và diển giải phải dẫn đến những hành động
có ích nào đó được đánh giá bằng một hàm lợi ích. Ví dụ như trong dữ liệu các
khoản vay, hàm lợi ích đánh giá khả năng tăng lợi nhuận từ các khoản
1.1.3. Các hướng tiếp cận và kỹ thuật áp dụng trong khai phá dữ liệu
Khai phá dữ liệu là một chuyên ngành rất rộng và có rất nhiềuhướng
nghiên cứu (bài toán) khác nhau. Tuy nhiên, chúng được tiếp cận theo các hướng
chính như sau:
- Phân lớp và dự đoán (Học có giám sát ): Phân lớp dữ liệu là việc xây
dựng một mô hình mà có thể phân cácđối tượng thành những lớp để dự đoán giá
trị bị mất tại một sốthuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất
hiệntrong tương lai.
- Phân cụm: Phân cụm dữ liệu là kỹ thuật khai phá dữ liệu tương tự như
phân lớp dữ liệu. Tuy nhiên, phân cụm dữ liệu là quá trình học không giám sát, là
quá trình nhóm những đối tượng vào các lớp tương ứng để sao cho các đối tượng
trong một nhóm là tương đương nhau, chúng khác so với các đối tượng của nhóm
khác.
- Luật kết hợp: Là quá trình khám phá các tập giá trị thuộc tính xuất hiện
phổ biến trong các đối tượng dữ liệu. Từ tập phổ biến có thể tạo ra các luật kết
hợp giữa các giá trị thuộc tính trong tập các đối tượng.


8

- Khai phá chuỗi theo thời gian:Phân tích chuỗi được sử dụng để tìm mẫu
trong tập rời rạc. Chuỗi được tạo thành từ tập các giá trị rời rạc. Phân tích chuỗi
theo thời gian và khai phá luật kết hợp là tương tự nhau nhưng có thêm tính thứ
tự và thời gian.
- Phân tích ngoại lệ: Phân tích ngoại lệ cũng là một dạng của phân cụm, nó

tập trung vào các trường hợp rất khác biệt so với các trường hợp khác. Đôi khi nó
thể hiện những lỗi trong dữ liệu hoặc thể hiện phần thú vị nhất trong dữ liệu đó.
- Hồi quy: Phương pháp hồi quy được sử dụng để đưa ra các dự báo dựa
trên các dữ liệu đang tồn tại bằng cách áp dụng các công thức. Một hàm sẽ được
học ra từ bộ dữ liệu hiện có bằng cách sử dụng các kỹ thuật hồi quy và tuyến tính
từ việc thống kê. Sau đó, dữ liệu mới sẽ căn cứ vào hàm này để đưa ra những dự
đoán.
1.1.4. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu đang được quan tâm và ứng dụng rộng rãi trong nhiều
lĩnh vực khoa học, kinh doanh,... đặc biệt trong các ngành có cơ sở dữ liệu lớn,
phức tạp, chứa đựng nhiều tri thức:
- Bảo hiểm: xác định loại khách hàng có rủi ro cao hay có gian lận bảo
hiểm, xác định khách hàng có thể thực hiện hết hợp đồng bảo hiểm hay đối
tượng, vùng nào có khả năng tham gia bảo hiểm,....
- Tài chính và thị trường chứng khoáng: phân tích tình hình tài chính, dự
báo giá, chỉ sổ của các loại cổ phiếu trong thị trường chứng khoáng, phát hiện các
giao dịch gian lận,...
- tế: một số thông tin về chuẩn đoán bệnh qua các triệu chứng, liên hệ
giữa các loại bệnh, dự đoán hiệu quả của một cuộc phẫu thuật,...
- Kinh doanh - Thương mại: xác định thói quen mua hàng của khách, dự
đoán chu kỳ kinh doanh của sản phẩm, dự đoán hiệu quả của một đợt quảng cáo,
tiếp thị,...
- Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định: dựa vào dữ liệu sẵn
có, phân tích dữ liệu để đưa ra những quyết định đúng lúc, có lợi nhất.
- Viễn thông: phát hiện gian lận trong cuộc gọi, xác định rủi ro trong việc
sử dụng đầu tư công nghệ mới, xu thế phát triển của khách hàng, các khu vực cần
phát triển, xác định sự khác nhau giữa các dịch vụ và sản phẩm với các đối thủ


9


cạnh tranh,...
Ngoài ra khai thác dữ liệu còn ứng dụng trong rất nhiều lĩnh vực khác nhau
của đời sống giúp đưa ra những giải pháp hiệu quả cho các vấn đề nan giải của
đời sống.
1.2. Khai phá dữ liệu Web
1.2.1. Khai phá dữ liệu web
Có nhiều khái niệm khác nhau về khai phá Web, nhưng có thể tổng quát
hóa như sau: Khai phá Web là việc sử dụng các kỹ thuật khai phá dữ liệu (KPDL)
để tự động hóa quá trình khám phá và trích rút những thông tin hữu ích từ các tài
liệu, các dịch vụ và cấu trúc Web. Hay nói cách khác khai phá Web là việc thăm
dò những thông tin quan trọng và những mẫu tiềm năng từ nội dung Web, từ
thông tin truy cập Web, từ liên kết trang và từ nguồn tài nguyên thương mại điện
tử bằng việc sử dụng các kỹ thuật KPDL, nó có thể giúp con người rút ra những
tri thức, cải tiến việc thiết kế các Web site và phát triển thương mại điện tử tốt
hơn. Lĩnh vực này đã thu hút được nhiều nhà khoa học quan tâm. Quá trình khai
phá Web có thể chia thành các công việc nhỏ như sau:
 Tìm kiếm nguồn tài nguyên: Thực hiện tìm kiếm và lấy các tài liệu Web
phục vụ cho việc khai phá.
 Lựa chọn và tiền xử lý dữ liệu: Lựa chọn và tiền xử lý tự động các loại
thông tin từ nguồn tài nguyên Web đã lấy về.
 Tổng hợp: Tự động khám phá các mẫu chung tại các Web site riêng lẽ cũng
như nhiều Website với nhau.
 Phân tích: Đánh giá, giải thích, biểu diễn các mẫu khai phá được.
1.2.2. Lợi ích của khai phá dữ liệu web
Với sự phát triển nhanh chóng của thông tin trên www, khai phá dữ liệu
Web đã từng bước trở nên quan trọng hơn trong lĩnh vực khai phá dữ liệu, người
ta luôn hy vọng lấy được những tri thức hữu ích thông qua việc tìm kiếm, phân
tích, tổng hợp, khai phá Web. Những tri thức hữu ích có thể giúp ta xây dựng nên
những Web site hiệu quả để có thể phục vụ cho con người tốt hơn, đặc biệt trong

lĩnh vực thương mại điện tử.
Khám phá và phân tích những thông tin hữu ích trên www bằng cách sử


10

dụng kỹ thuật khai phá dữ liệu đã trở thành một hướng quan trọng trong lĩnh vực
khám phá tri thức. Khai phá dữ liệu Web bao gồm khai phá cấu trúc Web, khai
phá nội dung Web và khai phá các mẫu truy cập Web.
Sự phức tạp trong nội dung của các trang Web khác với các tài liệu văn bản
truyền thống. Chúng không đồng nhất về cấu trúc, hơn nữa nguồn thông tin Web
thay đổi một cách nhanh chóng, không những về nội dung mà cả về cấu trúc
trang. Chẳng hạn như tin tức, thị trường chứng khoán, thông tin quảng cáo, trung
tâm dịch vụ mạng,... Tất cả thông tin được thay đổi trên Web theo từng giai đoạn.
Các liên kết trang và đường dẫn truy cập cũng luôn thay đổi. Khả năng gia tăng
liên tục về số lượng người dùng, sự quan tâm tới Web cũng khác nhau, động cơ
người dùng rất đa dạng và phong phú. Vậy làm thế nào để có thể tìm kiếm được
thông tin mà người dùng cần? Làm thế nào để có được những trang Web chất
lượng cao?...
Những vấn đề này sẽ được thực hiện hiệu quả hơn bằng cách nghiên cứu
các kỹ thuật KPDL áp dụng trong môi trường Web. Thứ nhất, ta sẽ quản lý các
Web site thật tốt; thứ hai, khai phá những nội dung mà người dùng quan tâm; thứ
ba, sẽ thực hiện phân tích các mẫu sử dụng Web. Dựa vào những vấn đề cơ bản
trên, ta có thể có những phương pháp hiệu quả cao để cung cấp những thông tin
hữu ích đối với người dùng Web và giúp người dùng sử dụng nguồn tài nguyên
Web một cách hiệu quả.
1.2.3. Khó khăn
World Wide Web là một hệ thống rất lớn phân bố rộng khắp, cung cấp
thông tin trên mọi lĩnh vực khoa học, xã hội, thương mại, văn hóa,... Web là một
nguồn tài nguyên giàu có cho Khai phá dữ liệu. Những quan sát sau đây cho thấy

Web đã đưa ra những thách thức lớn cho công nghệ Khai phá dữ liệu
 Web dường như quá lớn để tổ chức thành kho dữ liệu phục vụ
Dataming
Các CSDL truyền thống thì có kích thước không lớn lắm và thường được
lưu trữ ở một nơi, trong khi đó kích thước Web rất lớn, tới hàng terabytes và thay
đổi liên tục, không những thế còn phân tán trên rất nhiều máy tính khắp nơi trên
thế giới. Một vài nghiên cứu về kích thước của Web đã đưa ra các số liệu như
sau: Hiện nay trên Internet có khoảng hơn một tỷ các trang Web được cung cấp
cho người sử dụng., giả sử kích thước trung bình của mỗi trang là 5-10Kb thì tổng


11

kích thước của nó ít nhất là khoảng 10 terabyte. Còn tỷ lệ tăng của các trang Web
thì thật sự gây ấn tượng. Hai năm gần đây số các trang Web tăng gấp đôi và còng
tiếp tục tăng trong hai năm tới. Nhiều tổ chức và xã hội đặt hầu hết những thông
tin công cộng của họ lên Web. Như vậy việc xây dựng một kho dữ liệu
(datawarehouse) để lưu trữ, sao chép hay tích hợp các dữ liệu trên Web là gần
như không thể
 Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn
bản truyền thống khác
Các dữ liệu trong các CSDL truyền thống thì thường là loại dữ liệu đồng
nhất (về ngôn ngữ, định dạng,…), còn dữ liệu Web thì hoàn toàn không đồng
nhất. Ví dụ về ngôn ngữ dữ liệu Web bao gồm rất nhiều loại ngôn ngữ khác nhau
(Cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập trình), nhiều loại định dạng khác
nhau (Text, HTML, PDF, hình ảnh âm thanh,…), nhiều loại từ vựng khác nhau
(Địa chỉ Email, các liên kết (links), các mã nén (zipcode), số điện thoại). Nói cách
khác, trang Web thiếu một cấu trúc thống nhất. Chúng được coi như một thư viện
kỹ thuật số rộng lớn, tuy nhiên con số khổng lồ các tài liệu trong thư viện thì
không được sắp xếp tuân theo một tiêu chuẩn đặc biệt nào, không theo phạm trù,

tiêu đề, tác giả, số trang hay nội dung,... Điều này là một thử thách rất lớn cho
việc tìm kiếm thông tin cần thiết trong một thư viện như thế.
 Web là một nguồn tài nguyên thông tin có độ thay đổi cao
Web không chỉ có thay đổi về độ lớn mà thông tin trong chính các trang
Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu, hơn 500.000 trang
Web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10
ngày thì 50% các trang trong tên miền đó biến mất, nghĩa là địa chỉ URL của nó
không còn tồn tại nữa. Tin tức, thị trường chứng khoán, các công ty quản cáo và
trung tâm phục vụ Web thường xuyên cập nhật trang Web của họ. Thêm vào đó
sự kết nối thông tin và sự truy cập bản ghi cũng được cập nhật.
 Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng
Internet hiện nay nối với khoảng 50 triệu trạm làm việc, và cộng đồng
người dùng vẫn đang nhanh chóng lan rộng. Mỗi người dùng có một kiến thức,
mối quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng không có kiến thức
tốt về cấu trúc mạng thông tin, hoặc không có ý thức cho những tìm kiếm, rất dễ
bị "lạc" khi đang "mò mẫm" trong "bóng tối" của mạng hoặc sẽ chán khi tìm kiếm


12

mà chỉ nhận những mảng thông tin không mấy hữu ích.
 Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích
Theo thống kê, 99% của thông tin Web là vô ích với 99% người dùng Web.
Trong khi những phần Web không được quan tâm lại bị búi vào kết quả nhận
được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào để nhận
được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng? Như vậy
chúng ta có thể thấy các điểm khác nhau giữa việc tìm kiếm trong một CSDL
truyền thống với vviệc tìm kiếm trên Internet. Những thách thức trên đã đẩy
mạnh việc nghiên cứu khai phá và sử dụng tài nguyên trên Internet
1.2.4. Thuận lợi

Bên cạnh những thử thách trên, công việc khai phá Web cũng có những thuận lợi:
 Web bao gồm không chỉ có các trang mà còn có cả các hyperlink trỏ từ
trang này tới trang khác. Khi một tác giả tạo một hyperlink từ trang của ông ta tới
một trang A có nghĩa là A là trang có hữu ích với vấn đề đang bàn luận. Nếu
trang A càng nhiều Hyperlink từ trang khác trỏ đến chứng tỏ trang A quan trọng.
Vì vậy số lượng lớn các thông tin liên kết trang sẽ cung cấp một lượng thông tin
giàu có về mối liên quan, chất lượng, và cấu trúc của nội dung trang Web, và vì
thế là một nguồn tài nguyên lớn cho khai phá Web
 Một máy chủ Web thường đăng ký một bản ghi đầu vào (Weblog entry)
cho mọi lần truy cập trang Web. Nó bao gồm địa chỉ URL, địa chỉ IP, timestamp.
Dữ liệu Weblog cung cấp lượng thông tin giàu có về những trang Web động. Với
những thông tin về địa chỉ URL, địa chỉ IP,… một cách hiển thị đa chiều có thể
được cấu trúc nên dựa trên CSDL Weblog. Thực hiện phân tích OLAP đa chiều
có thể đưa ra N người dùng cao nhất, N trang Web truy cập nhiều nhất, và khoảng
thời gian nhiều người truy cập nhất, xu hướng truy cập Web


13

1.2.5. Các kiểu dữ liệu web
Ta có thể khái quát bằng sơ đồ sau:

Hình 1.3: Phân loại dữ liệu web
Các đối tượng của khai phá Web bao gồm: Server logs, Web pages, Web
hyperlink structures, dữ liệu thị trường trực tuyến và các thông tin khác.
 Web logs: Khi người dùng duyệt Web, dịch vụ sẽ phân ra 3 loại dữ liệu
đăng nhập: sever logs, error logs, và cookie logs. Thông qua việc phân tích các tài
liệu đăng nhập này ta có thể khám phá ra những thông tin truy cập.
 Web pages: Hầu hết các phương pháp KPDL Web được sử dụng trong
Web pages là theo chuẩn HTML.

 Web hyperlink structure: Các trang Web được liên kết với nhau bằng các
siêu liên kết, điều này rất quan trọng để khai phá thông tin. Do các siêu liên kết
Web là nguồn tài nguyên rất xác thực.
 Dữ liệu thị trường trực tuyến: Như lưu trữ thông tin thương mại điện tử
trong các site thương mại điện tử.
 Các thông tin khác: Chủ yếu bao gồm các đăng ký người dùng, nó có thể
giúp cho việc khai phá tốt hơn.
1.3. Các thách thức trong khai phá dữ liệu
1.3.1. Các vấn đề về Cơ sở dữ liệu
Đầu vào chủ yếu của một hệ thống khai thác tri thức là các dữ liệu thô
nhiều lúc không đầy đủ, lớn và bị nhiễu. Ngoài ra, chúng ta không biết cơ sở dữ


14

liệu có chứa các thông tin cần thiết cho việc khai thác hay không và làm thế nào
để giải quyết với sự dư thừa những thông tin không thích hợp này.
 Dữ liệu lớn: Cho đến nay, các cơ sở dữ liệu với hàng trăm trường và bảng,
hàng triệu bản ghi và với kích thước đến gigabytes đã là chuyện bình thường.
Hiện nay đã bắt đầu xuất hiện các cơ sở dữ liệu có kích thước tới terabytes. Các
phương pháp giải quyết hiện nay là đưa ra một ngưỡng cho cơ sở dữ liệu, lấu
mẫu, các phương pháp xấp xỉ, xử lý song song (Agrawal et al, Holsheimer et al).
 Kích thước lớn: không chỉ có số lượng bản ghi lớn mà số các trường trong
cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thước của bài toán trở nên lớn hơn. Một
tập dữ liệu có kích thước lớn sinh ra vấn đề làm tăng không gian tìm kiếm mô hình
suy diễn. Hơn nữa, nó cũng làm tăng khả năng một giải thuật khai phá dữ liệu có
thể tìm thấy các mẫu giả. Biện pháp khắc phục là làm giảm kích thước tác động
của bài toán và sử dụng các tri thức biết trước để xác định các biến không phù hợp.
 Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội dung
của chúng thay đổi liên tục. Dữ liệu có thể thay đổi theo thời gian và việc khai

phá dữ liệu cũng bị ảnh hưởng bởi thời điểm quan sát dữ liệu. Ví dụ trong cơ sở
dữ liệu về tình trạng bệnh nhân, một số giá trị dữ liệu là hằng số, một số khác lại
thay đổi liên tục theo thời gian (ví dụ cân nặng và chiều cao), một số khác lại thay
đổi tùy thuộc vào tình huống và chỉ có giá trị được quan sát mới nhất là đủ (ví dụ
nhịp đập của mạch). Vậy thay đổi dữ liệu nhanh chóng có thể làm cho các mẫu
khai thác được trước đó mất giá trị. Hơn nữa, các biến trong cơ sở dữ liệu của
ứng dụng đã cho cũng có thể bị thay đổi, bị xóa hoặc là tăng lên theo thời gian.
Vấn đề này được giải quyết bằng các giải pháp tăng trưởng để nâng cấp các mẫu
và coi những thay đổi như là cơ hội để khai thác bằng cách sử dụng nó để tìm
kiếm các mẫu bị thay đổi.
 Các trường không phù hợp: Một đặc điểm quan trọng khác là tính không
thích hợp của dữ liệu, nghĩa là mục dữ liệu trở thành không thích hợp với trọng
tâm hiện tại của việc khai thác. Một khía cạnh khác đôi khi cũng liên quan đến độ
phù hợp là tính ứng dụng của một thuộc tính đối với một tập con của cơ sở dữ
liệu. Ví dụ trường số tài khoản Nostro không áp dụng cho các tác nhân.
 Độ nhiễu và không chắc chắn: Đối với các thuộc tính đã thích hợp, độ
nghiêm trọng của lỗi phụ thuộc vào kiểu dữ liệu của các giá trị cho phép. Các giá
trị của các thuộc tính khác nhau có thể là các số thực, số nguyên, chuỗi và có thể


15

thuộc vào tập các giá trị định danh. Các giá trị định danh này có thể sắp xếp theo
thứ tự từng phần hoặc đầy đủ, thậm chí có thể có cấu trúc ngữ nghĩa. Mức độ
nhiễu cao trong dữ liệu dẫn đến các dự đoán thiếu chính xác
1.3.2. Một số vấn đề khác
 Quá phù hợp (Overfitting)
Khi một giải thuật tìm kiếm các tham số tốt nhất cho đó sử dụng một tập
dữ liệu hữu hạn, nó có thể sẽ bị tình trạng “quá độ” dữ liệu (nghĩa là tìm kiếm quá
mức cần thiết gây ra hiện tượng chỉ phù hợp với các dữ liệu đó mà không có khả

năng đáp ứng cho các dữ liệu lạ), làm cho mô hình hoạt động rất kém đối với các
dữ liệu thử. Các giải pháp khắc phục bao gồm đánh giá chéo (cross-validation),
thực hiện theo nguyên tắc nào đó hoặc sử dụng các biện pháp thống kê khác.
 Đánh giá tầm quan trọng thống kê
Vấn đề (liên quan đến overfitting) xảy ra khi một hệ thống tìm kiếm qua
nhiều mô hình. Ví dụ như nếu một hệ thống kiểm tra N mô hình ở mức độ quan
trọng 0,001 thì với dữ liệu ngẫu nhiên trung bình sẽ có N/1000 mô hình được
chấp nhận là quan trọng. Để xử lý vấn đề này, ta có thể sử dụng phương pháp
điều chỉnh thống kê trong kiểm tra như một hàm tìm kiếm, ví dụ như điều chỉnh
Bonferroni đối với các kiểm tra độc lập.
 Khả năng biểu đạt của mẫu
Trong rất nhiều ứng dụng, điều quan trọng là những điều khai thác được
phải cáng dễ hiểu với con người càng tốt. Vì vậy, các giải pháp thường bao gồm
việc diễn tả dưới dạng đồ họa, xây dựng cấu trúc luật với các đồ thị có hướng
(Gaines), biểu diễn bằng ngôn ngữ tự nhiên (Matheus et al.) và các kỹ thuật khác
nhằm biểu diễn tri thức và dữ liệu.
 Sự tương tác với người sử dụng và các tri thức sẵn có
Rất nhiều công cụ và phương pháp khai phá dữ liệu không thực sự tương
tác với người dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trước
đó. Việc sử dụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã có
nhiều biện pháp nhằm khắc phục vấn đề này như sử dụng cơ sở dữ liệu suy diễn
để phát hiện tri thức, những tri thức này sau đó được sử dụng để hướng dẫn cho
việc tìm kiếm khai phá dữ liệu hoặc sử dụng sự phân bố và xác suất dữ liệu trước
đó như một dạng mã hóa tri thức có sẵn.


16

1.4. Các phương pháp tách từ hiện nay
1.4.1. Phương pháp Maximum Matching

Phương pháp này còn được gọi là phương pháp khớp tối đa. Tư tưởng của
phương pháp này là duyệt một câu từ trái qua phải và chọn từ có nhiều tiếng nhất
mà có mặt trong từ điển, rồi cứ thế tiếp tục cho từ kế tiếp đến hết câu. Nôi dung
thuật toán này dựa trên thuật toán đã được ChihHao Tsai giới thiệu năm 1996.
Thuật toán có 2 dạng sau:
Dạng đơn giản: Giả sử có một chuỗi các tiếng trong câu là t1, t2, ..tN.
Thuật toán sẽ kiểm tra xem t1 có mặt trong từ điển hay không, sau đó kiểm tra
tiếp t1-t2 có trong từ điển hay không. Tiếp tục như vậy cho đến khi tìm được từ
có nhiều tiếng nhất có mặt trong từ điển, và đánh dấu từ đó. Sau đó tiếp tục quá
trình trên với tất các các tiếng còn lại trong câu và trong toàn bộ văn bản.
Dạng phức tạp: dạng này có thể tránh được một số nhập nhằng gặp phải
trong dạng đơn giản. Đầu tiên thuật toán kiểm tra xem t1 có mặt trong từ điển
không, sau đó kiểm tra tiếp t1-t2 có mặt trong từ điển không. Nếu t1-t2 đều có
mặt trong từ điển thì thuật toán thực hiện chiến thuật chọn 3-từ tốt nhất.
Tiêu chuẩn 3-từ tốt nhất được Chen & Liu (1992) đưa ra như sau:
 Độ dài trung bình của 3 từ là lớn nhất.
Ví dụ: với chuỗi “cơ quan tài chính” sẽ được phân đoạn đúng thành “cơ quan |
tài chính”, tránh được việc phân đoạn sai thành “cơ | quan tài | chính” vì cách
phân đúng phải có độ dài trung bình lớn nhất.
 Sự chênh lệch độ dài của 3 từ là ít nhất.
Ví dụ: với chuỗi “công nghiệp hóa chất phát triển” sẽ được phân đoạn đúng
thành “công nghiệp | hóa chất | phát triển” thay vì phân đoạn sai thành “công
nghiệp hóa | chất | phát triển”. Cả 2 cách phần đoạn này đều có độ dài trung bình
bằng nhau, nhưng cách phân đoạn đúng có sự chênh lệch độ dài 3 từ ít hơn.
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.



17

1.4.2. Phương pháp giải thuật học cải biến (Transformation-based Learning TBL)
Đây là cách tiếp cận dựa trên ngữ liệu đã đánh dấu. Theo cách tiếp cận này, để
huấn luyện cho máy tính biết cách nhận diện ranh giới từ đúng, ta có thể cho máy
“học” trên ngữ liệu hàng vạn câu đã được đánh dấu ranh giới 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 tập các câu mẫu và sau dó
máy sẽ tự rút ra quy 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 đã đưa 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 thật đầy đủ và phải
được huấn luyện lâu để có thể rút ra các luật đầy đủ.
1.4.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ố WFST
(Weighted finit-state Transducer) đã được áp dụng trong tách từ từ năm 1996. Ý
tưởng cơ bản là áp dụng WFST kết hợp với trọng số là xác suất xuất hiện của mỗi
từ trong ngữ liệu. Dùng WFST để duyệt qua câu cần xét. Cách duyệt có trọng số
lớn nhất sẽ là cách tách từ được chọn. 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 khi đã
tách từ (nếu có).
Chi tiết về 2 tầng này như sau:
 Tầng WFST gồm có 03 bước
Bước 1: Xây dựng từ điển trọng số: theo mô hình WFST, thao tách phân
đoạn từ đựoc 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ừ (POS : Part of speech) .
Mỗi cung của D có thể là :