ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
———————————— NGUYỄN DANH HÙNG NGHIÊN CỨU XÂY DỰNG HỆ THỐNG TỔNG HỢP,
PHÂN LOẠI THÔNG TIN TỰ ĐỘNG TRÊN WEB
Chuyên ngành: Khoa học máy tính
Mã số : 60.48.0101
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
1.2.1. Giới thiệu về khai phá Web 8
1.2.2. Khó khăn và thuận lợi 9
1.2.3. Quá trình khai phá Web 12
1.2.4. Các lĩnh vực của khai phá dữ liệu web 15
1.2.5. Các kiểu dữ liệu Web 16
1.3. Phân cụm tài liệu web 17
1.4. Phân lớp văn bản 19
1.4.1. Bài toán phân lớp văn bản 19
1.4.2. Dữ liệu văn bản 21
1.4.3. Biểu diễn văn bản 21
1.4.4. Một số vấn đề trong xử lý dữ liệu văn bản 23
1.5. Tổng kết chƣơng 1 29
CHƢƠNG 2: MÔ HÌNH HỆ THỐNG TỔNG HỢP, PHÂN LOẠI THÔNG TIN TỰ
ĐỘNG 30
2.1. Các phƣơng pháp tách từ tiếng Việt 30
2.1.1. Phƣơng pháp Maximum Matching: forward/backward 30
- ii -

2.1.2. Phƣơng pháp giải thuật học cải biến (Tranformation-based Learning) 31
2.1.3. Mô hình tách từ bằng WFST và mạng Neural 32
2.1.4. Phƣơng pháp quy hoạch động (Dynamic Programming) 34
2.1.5. Phƣơng pháp tách từ tiếng việt dựa trên thống kê từ Internet và thuật toán
di truyền IGATEC 35
2.2. Các phƣơng pháp phân loại văn bản 37
2.2.1. Phƣơng pháp phân lớp Bayes (Naïve Bayes) 37
2.2.2. Phƣơng pháp k-ngƣời láng giêng gần nhất (K-Nearest Neighbor) 39
2.2.3. Phƣơng pháp máy hỗ trợ vector (Support vector Machine) 40
2.2.4. Phƣơng pháp mạng nơron (Neural Network) 42
2.2.5. Phƣơng pháp Linear Least Square Fit 43
2.2.6. Phƣơng pháp Centroid-based vector 44

TÀI LIỆU THAM KHẢO 74 - iv -

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

KDD
Knowledge Discovery in Database
KPDL
Khai phá dữ liệu
IGATEC
Internet and Genetics Algorithm-based Text Categorization for
Documents in Vietnamese
kNN
K–Nearest Neighbor
LLSF
Linear Least Square Fit
NB
Naïve Bayes
NNet
Neural Network
LLSF
Linear Lest Square Fit
DF
Tần suất tài liệu (Document Frequency
TBL
Phƣơng pháp giải thuật học cải biến (Transformation – based Learning
IDF
Tần suất tài liệu ngƣợc (Inverse document frequency)

Hình 2.3. 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. 41
Hình 2.4. Kiến trúc mô đun (Modular Architecture) 43
Hình 2.5. Mô hình kiến trúc hệ thống thu thập tin 48
Hình 3.1. Giải thuật hoạt động phân hệ Crawler 66
Hình 3.2. Ví dụ sơ đồ cây DOM 67
Hình 3.2. Giải thuật hoạt động của phân hệ Extractor 69
Hình 3.3. Giao diện trang chủ 70
Hình 3.4. Quản lý kênh tinh 71
Hình 3.5. Quản lý cập nhập tin 71
Hình 3.6. Quản lý chuyên mục tin 72
Hình 3.7. Quản lý tin tức 72
- 1 -

MỞ ĐẦU
1. Lý do chọn đề tài
Trong những năm gần đây cùng với sự phát triển nhanh chóng của khoa
học kỹ thuật là sự bùng nổ về tri thức. Kho dữ liệu, nguồn tri thức của nhân loại
cũng trở nên đồ sộ, vô tận làm cho vấn đề khai thác các nguồn tri thức đó ngày
càng trở nên nóng bỏng và đặt ra thách thức lớn cho nền công nghệ thông tin thế
giới.
Cùng với những tiến bộ vƣợt bậc của công nghệ thông tin là sự phát triển
mạnh mẽ của mạng thông tin toàn cầu, nguồn dữ liệu Web trở thành kho dữ liệu
khổng lồ. Nhu cầu khai thác và xử lý thông tin phục vụ cho công tác quản lý,
hoạt động sản xuất, kinh doanh, học tập… đã trở nên cấp thiết trong xã hội hiện
đại. Do đó số lƣợng văn bản xuất hiện trên mạng Internet cũng tăng theo một tốc
độ chóng mặt. Với lƣợng thông tin đồ sộ nhƣ vậy, một yêu cầu lớn đặt ra là làm
sao tổ chức, tìm kiếm và có đƣợc thông tin nhanh chóng, hiệu quả nhất.
Để giải quyết vấn đề này, có một hƣớng giải quyết là nghiên cứu và áp
dụng kỹ thuật khai phá dữ liệu trong môi trƣờng Web. Vì vậy tôi chọn đề tài

mô hình hệ thống tổng hợp, phân loại tin tức.
Chƣơng 3: Trình bày giải pháp xây dựng thử nghiệm hệ thống tổng hợp,
phân loại thông tin việc làm tự động.
5. Phƣơng pháp nghiên cứu
Nghiên cứu lý thuyết:
- Tìm hiểu lý thuyết về khai phá dữ liệu và khai phá dữ liệu web.
- Tìm hiểu các thuật toán phâm cụm tài liệu.
- Tìm hiểu cơ chế hoạt động của các hệ thống tìm kiếm thu thập thông tin.
- 3 -

Nghiên cứu thực nghiệm:
- Dựa trên lý thuyết đã nghiên cứu, tiến hành xây dựng hệ thống thu thập và
phân loại thông tin từ các kênh tin đƣợc cấu hình trƣớc.
- Thử nghiệm trên máy đơn qua localhost có kết nối internet.
6. Ý nghĩa khoa học
Về mặt lý thuyết: Giới thiệu tổng quan, ứng dụng của khai phá dữ liệu web,
các thuật toán phân loại tài liệu và cơ chế của hệ thống thu thập tin.
Về mặt thực tiễn: Xây dựng hệ thống tổng hợp, phân loại thông tin tự động
trên web. Cho phép ngƣời dung cập nhật các thông tin mới nhất từ các website
khác, lƣu trữ, tìm kiếm thông tin theo các chuyên mục.
- 4 -

CHƢƠNG 1: KHAI PHÁ DỮ LIỆU
1.1. Khai phá dữ liệu
1.1.1. Giới thiệu khai phá dữ liệu
Khai phá dữ liệu (DM - Data Mining) là một khái niệm ra đời vào những năm
cuối của thập kỷ 1980. Cụm từ “khai phá dữ liệu” nó bao hàm một loạt các kỹ thuật
nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn.
Khám phá tri thức trong các cơ sở dữ liệu (Knowledge Discovery in Database -
KDD) là một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính

quá trình xử lý.
• Khai phá dữ liệu: Là một trong những bƣớc quan trọng nhất, trong đó sử dụng
những phƣơng pháp thông minh để lựa chọn ra những mẫu dữ liệu.
• Ƣớc lƣợng mẫu: Quá trình đánh giá kết quả thông qua một độ đo nào đó.
• Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan cho ngƣời dùng.

- 6 -

1.1.2. Quá trình khai phá dữ liệu
Quá trình khai phá dữ liệu có thể chia thành các giai đoạn nhƣ sau:

Hình 1.2. Quá trình khai phá dữ liệu [9]
Trích chọn dữ liệu: Đây là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá
từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định.
Tiền xử lý dữ liệu: Đây là bƣớc làm sạch dữ liệu (xử lý những dữ liệu không đầy
đủ, nhiễu, không nhất quán, ), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các
phƣơng pháp nén dữ liệu, sử dụng histograms, lấy mẫu, ), rời rạc hóa dữ liệu (rời rạc
hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng, ). Sau bƣớc này, dữ
liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hóa.
Biến đổi dữ liệu: Đây là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về
dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bƣớc sau.
Khai phá dữ liệu: Đây là bƣớc áp dụng những kỹ thuật phân tích (nhƣ các kỹ
thuật của học máy) nhằm để khai thác dữ liệu, trích chọn đƣợc những mẫu thông tin,
những mối liên hệ đặc biệt trong dữ liệu. Đây đƣợc xem là bƣớc quan trọng và tốn
nhiều thời gian nhất của toàn quá trình KDD.
Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu
đã đƣợc khám phá ở bƣớc trên đƣợc biến đổi và biểu diễn ở một dạng gần gũi với
ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật, Đồng thời bƣớc này cũng đánh giá
những tri thức khám phá đƣợc theo những tiêu chí nhất định.
- 7 -


- Trong sinh học: nó dùng để tìm kiếm, so sánh các hệ gen và thông tin di
chuyền, tìm mối liên hệ giữa các hệ gen và chẩn đoán một số bệnh di truyền.
- Trong y học: KPDL giúp tìm ra mối liên hệ giữa các triệu chứng lâm sàng, chẩn
đoán bệnh.
- Tài chính và thị trƣờng chứng khoán: KPDL để phân tích tình hình tài chính,
phân tích đầu tƣ, phân tích cổ phiếu.
- Khai phá dữ liệu web.
- Trong thông tin kỹ thuật: KPDL dùng để phân tích các sai hỏng, điều khiển và
lập lịch trình.
- Trong thông tin thƣơng mại: dùng để phân tích dữ liệu ngƣời dùng, phân tích
dữ liệu marketing, phân tích đầu tƣ, phát hiện các gian lận.
1.2. Khai phá Web
1.2.1. Giới thiệu về khai phá Web
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối
lƣợng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với sự thay đổi và
phát triển hàng ngày hàng giờ về nội dung cũng nhƣ số lƣợng của các trang Web trên
Internet thì vấn đề tìm kiếm thông tin đối với ngƣời sử dụng lại ngày càng khó khăn.
Có thể nói nhu cầu tìm kiếm thông tin trên môt cơ sở dữ liệu phi cấu trúc (bao gồm dữ
liệu văn bản) đã đƣợc phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy
với Internet, con ngƣời đã làm quen với các trang Web cùng với vô vàn các thông tin.
Trong những năm gần đây, Intrnet đã trở thành một trong những kênh về khoa học,
thông tin kinh tế, thƣơng mại và quảng cáo. Một trong những lý do cho sự phát triển
này là giá cả thấp cần tiêu tốn khi công khai một trang Web trên Internet. So sánh với
những dịch vụ khác nhƣ mua bản hay quảng cáo trên một tờ báo hay tạp chí, thì một
trang Web "đòi" chi phí rẻ hơn rất nhiều mà lại đƣợc cập nhật nhanh chóng hơn tới
hàng triệu ngƣời dùng khắp mọi nơi trên thế giới. Có thể nói không gian Web nhƣ là
cuốn từ điển Bách khoa toàn thƣ. Thông tin trên các trang Web đa dạng về mặt nội
dung cũng nhƣ hình thức. Có thể nói Internet nhƣ một xã hội ảo, nó bao gồm các
- 9 -


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 sự 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 một 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 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ế.
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
- 12 -

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.
2. 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.
1.2.3. Quá trình khai phá Web
Khai phá Web là việc sử dụng các kỹ thuật 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 [10].

Hình 1.3. Quá trình khai phá văn bản Web

- 13 -

Quá trình khai phá văn bản Web thƣờng trải qua một số bƣớc nhƣ sau:
- Lựa chọn dữ liệu: Về cơ bản, văn bản cục bộ đƣợc định dạng tích hợp thành

bao hàm của một số ít các từ đặc trƣng chính trong mô tả để thực hiện giảm bớt số
chiều.
- Khai phá văn bản: Sau khi tập hợp, lựa chọn và trích ra tập văn bản hình thành
nên các đặc trƣng cơ bản, nó sẽ là cơ sở để Khai phá dữ liệu. Từ đó ta có thể thực hiện
trích, phân loại, phân cụm, phân tích và dự đoán.
+ Trích rút văn bản: Việc trích rút văn bản để đƣa ra ý nghĩa chính có thể mô tả
tóm tắt tài liệu văn bản trong quá trình tổng hợp. Sau đó, ngƣời dùng có thể hiểu ý
nghĩa chính của văn bản nhƣng không cần thiết phải duyệt toàn bộ văn bản. Đây là
phƣơng pháp đặc biệt đƣợc sử dụng trong searching engine, thƣờng cần để đƣa ra văn
bản trích dẫn. Nhiều searching engines luôn đƣa ra những câu dự đoán trong quá trình
tìm kiếm và trả về kết quả, cách tốt nhất để thu đƣợc ý nghĩa chính của một văn bản
hoặc tập văn bản chủ yếu bằng việc sử dụng nhiều thuật toán khác nhau.
+ Phân lớp văn bản: Nhiều tài liệu đƣợc phân lớp tự động một cách nhanh chóng
và hiệu quả cao. Ngƣời ta thƣờng sử dụng phƣơng pháp phân lớp Navie Bayesian và
"K - láng giềng gần nhất" để khai phá thông tin văn bản. Trong phân lớp văn bản, đầu
tiên là phân loại tài liệu. Thứ hai, xác định đặc trƣng thông qua số lƣợng các đặc trƣng
của tập tài liệu huấn luyện. Cuối cùng, tính toán kiểm tra phân lớp tài liệu và độ tƣơng
tự của tài liệu phân lớp bằng thuật toán nào đó. Khi đó các tài liệu có độ tƣơng tự cao
với nhau thì nằm trong cùng một phân lớp. Độ tƣơng tự sẽ đƣợc đo bằng hàm đánh giá
xác định trƣớc. Nếu ít tài liệu tƣơng tự nhau thì đƣa nó về 0. Nếu nó không giống với
sự lựa chọn của phân lớp xác định trƣớc thì xem nhƣ không phù hợp.
+ Phân cụm văn bản: Chủ đề phân loại không cần xác định trƣớc nhƣng ta phải
phân loại các tài liệu vào nhiều cụm. Trong cùng một cụm thì độ tƣơng tự thấp hơn.
Phƣơng pháp sắp xếp liên kết và phƣơng pháp phân cấp thƣờng đƣợc sử dụng trong
văn bản phân cụm.
+ Phân tích và dự đoán xu hướng: Thông qua việc phân tích các tài liệu Web, ta
có thể nhận đƣợc quan hệ phân phối của các dữ liệu đặc biệt trong từng giai đoạn của
nó và có thể dự đoán đƣợc tƣơng lai phát triển.
- 15 -



* Khai phá sử dụng Web
Khai phá sử dụng web (web usage/log mining) là việc xử lý để lấy ra các thông
tin hữu ích trong các thông tin truy cập Web.
General Access Pattern tracking: phân tích các hồ sơ web để biết đƣợc các mẫu
và các xu hƣớng truy cập.
Cusomized Usage tracking: phân tích các xu hƣớng cá nhân. Mục đích là để
chuyên biệt hóa các web site cho các lớp đối tƣợng ngƣời dùng.
Có thể mô tả nội dung của khai phá dữ liệu web theo sơ đồ dƣới đây: Hình 1.4. Nội dung khai phá dữ liệu Web [1].
1.2.5. Các kiểu 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.
Cấu trúc Web
Khai phá Web
Sử dụng Web
Nội dung Web
Nội dung
trang web
Kết quả tìm

Liên kết tĩnh
Liên kết động
Dữ liệu Web
Dữ liệu nội dung
Dữ liệu cấu trúc
Dữ liệu sử dụng
Dữ liệu ngƣời
dùng định nghĩa
- 18 -

- Các kỹ thuật đƣợc sử dụng trong khai phá sử dụng Web:
+ Luật kết hợp: Để tìm ra những Web thƣờng đƣợc truy cập cùng nhau của ngƣời
dùng, những lựa chọn cùng nhau của khách hàng trong thƣơng mại điện tử.
+ Kỹ thuật phân cụm: Phân cụm ngƣời dùng dựa trên các mẫu duyệt để tìm ra sự
liên quan giữa ngƣời dùng Web và các hành vi của họ.
- Khai phá cấu trúc Web: WWW là hệ thống thông tin toàn cầu, bao gồm tất cả
các Website. Mỗi một trang có thể đƣợc liên kết đến nhiều trang. Các siêu liên kết thay
đổi chứa đựng ngữ nghĩa chủ đề của trang. Một siêu liên kết trỏ tới một trang Web
khác có thể đƣợc xem nhƣ là một chứng thực của trang Web đó. Do đó, nó rất có ích
trong việc sử dụng những thông tin ngữ nghĩa để lấy đƣợc thông tin quan trọng thông
qua hân tích liên kết giữa các trang Web.
Mục tiêu của khai phá cấu trúc Web là để phát hiện thông tin cấu trúc về Web.
Nếu nhƣ khai phá nội dung Web chủ yếu tập trung vào cấu trúc bên trong tài liệu thì
khai phá cấu trúc Web cố gắng để phát hiện cấu trúc liên kết của các siêu liên kết ở
mức trong của tài liệu. Dựa trên mô hình hình học của các siêu liên kết, khai phá cấu
trúc Web sẽ phân loại các trang Web, tạo ra thông tin nhƣ độ tƣơng tự và mối quan hệ
giữa các Website khác nhau. Nếu trang Web đƣợc liên kết trực tiếp với trang Web
khác thì ta sẽ muốn phát hiện ra mối quan hệ giữa các trang Web này.
- Quá trình tìm kiếm và phân cụm tài liệu: Về cơ bản, quá trình phân cụm kết quả
tìm kiếm sẽ diễn ra theo các bƣớc: