HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN THỊ HUỆ

SẮP XẾP KẾT QUẢ CỦA MÁY TÌM KIẾM BẰNG
KỸ THUẬT PHÂN CỤM

Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2012

1 Người hướng dẫn khoa học: PGS.TS. TỪ MINH PHƯƠNG Phản biện 1: ……………………………………

Phản biện 2: ……………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn
thạc sĩ tại
Học viện Công nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

1

MỞ ĐẦU

giá, các phương pháp phân cụm phổ biến,
Chương 3. Thực nghiệm và đánh giá. Trinh bày
các bước tiến hành thực nghiệm trên tập dữ liệu lấy từ
máy tìm kiếm google, phân tích và xử lý sau đó đánh giá
kết quả trước và sau khi áp dụng kỹ thuật phân cụm.
Phần Kết luận Trình bày tổng hợp các kết quả mà
luận văn đã thực hiện được và phương hướng nghiên cứu
tiếp theo về các nội dung của luận văn.

3

CHƯƠNG I. TỔNG QUAN
1.1. Tổng quan về bài toán phân cụm kết quả tìm
kiếm
Ý tưởng được đưa ra là khi kết quả trả về của công
cụ tìm kiếm cần được phân ra theo chủ đề, giúp người
dùng định hướng, lựa chọn tài liệu phù hợp một cách
nhanh chóng và hiệu quả hơn.
Chẳng hạn, nếu chúng ta gửi truy vấn là “ô tô”
thông qua công cụ tìm kiếm nối tiếng như google [14] thì
sẽ nhận được khoảng 83 100 000 kết quả tìm kiếm (Số
liệu thống kê 27/9/2012).
Giống như nhiều truy vấn khác, truy vấn “ô tô”
cũng có nhiều đặc trưng khác nhau chẳng hạn như: mua
bán, đua xe, kỹ thuật lái xe, Mỗi kết quả mang một đặc
trưng nhất định và có thể các trang có cùng đặc trưng sẽ
nằm rải rác, xen kẽ trong một số lượng lớn các danh sách


tích hợp phân cụm đang được xây dựng và đem lại kết quả
rất khả quan.
1.2. Công cụ tìm kiếm thông thường
1.2.1. Giới thiệu
Công cụ tìm kiếm là một công cụ rất hữu ích giúp
người dùng sử dụng nguồn tài nguyên trên Internet một
cách hiệu quả nhất.
1.2.2. Quá trình tìm kiếm và kết quả tìm kiếm
1.2.2.1. Hệ thống thu thập dữ liệu
1.2.2.2. Hệ thống phân tích và lập chỉ mục dữ liệu
1.2.2.3. Hệ thống tìm kiếm
1.2.3. Một số công cụ tìm kiếm điển hình
1.2.3.1. Google:
1.2.3.2. Yahoo:
1.2.3.3. MSN:
1.2.4. Hiệu quả của các công cụ tìm kiếm

6

Đáp ứng các truy vấn rộng, mơ hồ, danh sách kết
quả nằm rải rác, pha trộn với một số trang không liên quan
đến truy vấn, Ngoài ra với khối lượng thông tin lớn trên
Internet thì danh sách kết quả trả về cũng lớn, có khi là
hàng tỷ kết quả với một câu truy vấn và điều này cũng hạn
chế khả năng lướt toàn bộ kết quả tìm kiếm của người sử
dụng.

- Công nhận kết quả
- Giải thích kết quả

8

2.1.3. Xây dựng mô hình phân cụm dữ liệu
2.1.3.1. Mô hình tài liệu
Hầu hết các thuật toán phân cụm đều yêu cầu tập
dữ liệu cần được phân cụm ở dạng một tập các véc tơ D =
{d1, d2, …, dn} trong đó véc tơ di, i= 1, 2 …, n đại diện
cho một đối tượng đơn lẻ trong tập dữ liệu và được gọi là
véc tơ đặc trưng (feature vector).
a, Mô hình dữ liệu tài liệu
b, Mô hình dữ liệu số
c, Mô hình phân cụm dữ liệu
d, Mô hình dữ liệu kết hợp
2.1.3.2. Độ đo về sự tương tự
Với 2 véc tơ đặc trưng x và y, cần phải tìm ra độ
tương tự (hoặc không tương tự) giữa chúng. Một lớp rất
hay sử dụng bởi các hàm khoảng cách được mô tả như
công thức (2.1) :

9




n
i
ii
yxyx
Công thức (2.3)
P = ∞ : Khoảng cách Tschebyshev xem công thức
(2.4)

10

iini
yxyx 
 , ,2,1
max

Công thức (2.4)
Một độ đo độ tương tự hay được dùng, đặc biệt là
trong phân cụm tài liệu đó là độ đo liên quan cosine
(cosine correlation), được định nghĩa như công thức
(2.5):
yx
yx
yx
.
),cos( 

11

yx
yx
yxd


),(

Công thức (2.7)
2.1.3.3. Mô hình phân cụm tài liệu
Tùy theo vấn đề, chúng ta có thể có các phân cụm
tách rời (disjoint) hoặc các phân cụm chồng chéo
(overlapping).
2.1.4. Một số vấn đề trong xử lý dữ liệu văn bản
2.1.4.1. Loại bỏ từ dừng
2.1.4.2. Định luật Zipf
2.2. Phân cụm kết quả tìm kiếm
2.2.1. Mô tả bài toán
Đưa ra danh sách được xếp hạng gốc của kết quả
tìm kiếm R={r(di|q)}. Trong đó:
+ q là câu truy vấn hiện tại
+ di là một tài liệu (kết quả tìm kiếm)
+ r là một hàm tính độ liên quan giữa di và q

2.2.5.1. Thu nhận kết quả tìm kiếm
Cụ thể là dựa vào câu truy vấn để tìm kiếm và trả
về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt,
URL,… tương ứng với các trang đó.
2.2.5.2. Tiền xử lý kết quả tìm kiếm
a. Chuẩn hóa văn bản
+ Xóa các thẻ HTML và các loại thẻ khác để trích
ra các từ/cụm từ.
+ Chuyển các ký tự hoa thành các ký tự thường.
+ Xóa bỏ các dấu câu, xoá các ký tự trắng dư
thừa,
b. Xóa bỏ các từ dừng

14

Trong văn bản có những từ mang ít thông tin trong
quá trình xử lý, những từ có tần số xuất hiện thấp, những
từ xuất hiện với tần số lớn nhưng không quan trọng cho
quá trình xử lý đều được loại bỏ.
c. Kết hợp các từ có cùng gốc
Hầu hết trong các ngôn ngữ đều có rất nhiều các từ
có chung nguồn gốc với nhau, chúng mang ý nghĩa tương
tự nhau, do đó để giảm bởt số chiều trong biểu diễn văn
bản, ta sẽ kết hợp các từ có cùng gốc thành một từ.
d. Xây dựng từ điển
Từ điển sẽ gồm một bảng các từ, chỉ số của nó
trong từ điển và được sắp xếp theo thứ tự.
16

4. Chọn Ґ, Δ Є G thông qua độ đo tính
tương tự s(Ґ, Δ)
5. Loại bỏ Ґ, Δ khỏi G
6. Đặt Ф= Ґ  Δ
7. Thêm Ф vào G
8. end while
2.3.3. Thuật toán
Expectation Maximization

Thuật toán Expectation Maximization ở bước lặp
thứ t thực hiện các công việc sau:
- Bước E: Tính toán để xác định giá trị của các
biến chỉ thị dựa trên mô hình hiện tại và dữ liệu:
- Bước M: Đánh giá xác suất
2.3.4. Thuật toán Suffix Tree Clustering
STC có ba bước hợp lý: (1) văn bản "làm sạch", (2)
xác định các cụm cơ sở bằng cách sử dụng một cây hậu tố,
và (3) kết hợp các cụm cơ sở thành các cụm.
2.4. Kết luận chương

17

CHƯƠNG III. THỰC NGHIỆM VÀ ĐÁNH

theo sau bởi một tập các giá trị mà chúng có thể xảy ra, và
chúng được đặt trong dấu {}. Các giá trị có thể bao gồm
các khoảng trống; Nếu vậy, chúng phải được đặt giữa hai
dấu “”. Các giá trị số được kèm theo bởi từ khóa numeric.
Tiếp theo các định nghĩa về đặc trưng là một dòng
@data là ký hiệu cho bắt đầu các mẫu (instance) trong tập
dữ liệu. Các instance được viết mỗi cái trên một dòng, với
các giá trị cho mỗi đặc trưng theo thứ tự, cách nhau bởi
dấu phẩy. Nếu một giá trị bị lỗi (missing) thì nó được thể
hiện bằng một dấu hỏi chấm (không có giá trị missing nào
trong dữ liệu này). Các mô tả đặc trưng trong file ARFF
cho phép tập dữ liệu được kiểm tra xem có chắc rằng nó

19

chứa các giá trị hợp lệ hay không. Và các chương trình
đọc file ARFF sẽ làm việc kiểm tra này một cách tự động.
Ngoài ra, chúng tôi sử dụng thêm các công cụ:
- Detagger để
chuyển đổi file định dạng HTML về định
dạng plaintext

- Stopwords.java để loại bỏ các từ dừng
- LovinsStemmerWrapper.java và
PorterStemmerWrapper.java để rút gọn các từ về dạng
nguyên gốc
- PruneByFrequency.java để loại bỏ các từ có tần số

 Thực hiện vector hóa các file văn bản với
mỗi thành phần của vector tương ứng một từ khóa trong
wordlist và được gán giá trị là một số nguyên dương

21

tương ứng với tần suất xuất hiện của từ khóa đó trong
trang Web .
Dựa vào mô hình không gian vecto, ta có 50 kết
quả tìm kiếm đã được xử lý là: doc 1, doc 2, … ,doc 50.
- Các từ được tách ra mà có nghĩa sẽ đặt là w1, w2,
…, wn
- Căn cứ số từ xuất hiện trong các docs, chúng ta sử
dụng mô hình túi của từ (bag – of – words) để biểu diễn
 Tổ chức các vector thành file search.arff
theo định dạng của phần mềm WEKA.
Bước 3. Phân cụm kết quả tìm kiếm
Dữ liệu dùng để phân cụm trong thực nghiệm này
là nội dung đã được chuẩn hóa của 50 kết quả tìm kiếm
với truy vấn là từ khóa “ô tô”, trong đó gồm có 10 đặc
trưng là các từ, cụm từ xuất hiện trong các kết quả tìm
kiếm được lựa chọn trong nội dung tìm kiếm và giá trị của
mỗi đặc trưng chính là tần suất xuất hiện của từ. Lưu ý


10%
20%
30%
40%
50%
60%
70%
Cụm 0 Cụm 1 Cụm 2
Số cụm lựa chon
Phần trăm kết quả
EM
HierarchicalClusterer
SimpleKMeans

Hình 3.14. Biểu đồ so sánh số liệu giữa các thuật
3.5. Kết luận chương
.