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
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
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
Hiện nay, tìm kiếm thông tin trên Internet đã trở
nên đơn giản hơn với sự phát triển cả về nội dung và hình
thức của các công cụ tìm kiếm. Tuy nhiên, với sự phát
triển nhanh chóng của mạng Internet hiện nay thì số lượng
các trang Web là rất lớn. Vấn đề đặt ra là với câu truy vấn
mà trả về hàng trăm, hàng nghìn thậm chí hàng tỷ kết
quả thì liệu rằng người dùng có đủ kiên nhẫn và thời
gian để lướt qua tất cả các kết quả đó hay không?
Để tiến hành xử lý vấn đề này, các kỹ thuật phân
cụm đã được sử dụng. Luận văn với đề tài: “Sắp xếp kết
quả của máy tìm kiếm bằng kỹ thuật phân cụm” tập
trung nghiên cứu về kỹ thuật phân cụm và áp dụng nó để
sắp xếp kết quả tìm kiếm theo chủ đề.
Luận văn được chia thành 3 chương với các nội
dung chính như sau:
Chương 1. Tổng quan. Trình bày khái quát về bài
toán phân cụm kết quả tìm kiếm và giới thiệu đặc điểm,
2
chức năng, giao diện của một công cụ tìm kiếm điển hình
hiện nay.
Chương 2. Sắp xếp kết quả tìm kiếm bằng kỹ
thuật phân cụm. Trình bày những nét cơ bản nhất về bài
toán phân cụm dữ liệu nói chung và đặc biệt đi sâu vào bài
toán phân cụm kết quả tìm kiếm theo chủ đề nói riêng, bao
gồm: giới thiệu và mô tả bài toán, một số độ đo độ đánh
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
kết quả trả về.
4
Nhiệm vụ chúng ta cần giải quyết là những trang
nào có nội dung đề cập đến mua bán xe ô tô ta gom vào
một nhóm, làm tương tự với các nhóm đua xe, kỹ thuật lái
xe, ... Khi đã xử lý được việc phân cụm này thì người sử
dụng chỉ việc truy cập đến chủ đề cần tìm mà không cần
quan tâm đến các chủ đề khác.
Phương pháp phân cụm ở đây sẽ đưa về bài toán
phân cụm xếp hạng các cụm từ quan trọng. Đưa ra câu
truy vấn và lấy về một danh sách các tài liệu đã được xếp
hạng từ công cụ tìm kiếm, đầu tiên là tách các tài liệu
thành các cụm từ, sau đó xếp hạng các cụm từ này.
Công trình đầu tiên dựa trên kỹ thuật phân cụm là
Northern Light, vào cuối những năm 1990, nó chỉ được
phân cụm dựa trên kết quả tìm kiếm được cho sẵn.
Tính đến nay, phân cụm đã được tích hợp trong
một số máy tìm kiếm tiếng Anh như Viv'isimo, carrot2
hay Clusty đạt độ chính xác khá cao, với tiếng Việt hiện
tại chỉ có Việt Nam Search Engine là máy tìm kiếm có
5
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: http://www.google.com/
1.2.3.2. Yahoo: http://yahoo.com/
1.2.3.3. MSN: http://www.msn.com/
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.
1.3. Kết luận chương
7
CHƯƠNG II. SẮP XẾP KẾT QUẢ TÌM
KIẾM BẰNG KỸ THUẬT PHÂN CỤM
2.1. Kỹ thuật phân cụm
2.1.1. Giới thiệu phân cụm dữ liệu
Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ
liệu, quá trình phân cụm dữ liệu là quá trình phân chia một
tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các
phần tử trong một cụm "tương tự" với nhau và các phần tử
trong các cụm khác nhau sẽ "phi tương tự" với nhau.
2.1.2. Một số yêu cầu trong quá trình phân cụm
- Chọn lựa đặc trưng
- Chọn độ đo tương tự
- Tiêu chuẩn phân cụm
- Thuật toán phân cụm:
- 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
x y
p
xi yi
p
Công thức (2.1)
i 1
Trong đó x,y
Rn. Hàm khoảng cách này thực ra
là mô tả một họ vô số các khoảng cách được đưa ra bởi p.
Thông số này giả thiết là các giá trị lớn hơn hoặc bằng 1.
Một vài giá trị chung của p và các hàm khoảng cách là:
P = 1 : Khoảng cách Hammming xem công thức
(2.2)
n
x y xi y i
Công thức (2.2)
i 1
P = 2 : Khoảng cách Euclidean xem công thức (2.3)
2
n
x y
x
i
yi
Công thức (2.3)
i 1
P = ∞ : Khoảng cách Tschebyshev xem công thức
(2.4)
10
x y max i 1, 2,..., n xi yi
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):
cos( x, y )
x. y
x y
Công thức (2.5)
Trong đó . biểu thị việc nhân vector và ||.|| biểu thị
cho độ dài của vector. Một độ đo hay được dùng khác đó
là độ đo Jaccard (được sử dụng trong [26], [32]), được
định nghĩa như công thức (2.6) :
d ( x, y )
n
i 1
n
min( xi , yi )
max( xi , yi )
i 1
Công thức (2.6)
Trong trường hợp các vector đặc trưng nhị phân, có
thể đơn giản hóa như công thức (2.7):
11
d ( x, y )
x y
x y
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
12
2.2.2. Mô tả thuật toán
Phương pháp phân cụm dựa vào xếp hạng các cụm
từ quan trọng [25] đã đưa bài toán phân cụm kết quả tìm
kiếm sang bài toán xếp hạng các cụm từ quan trọng.
2.2.3. Mục tiêu của kỹ thuật phân cụm kết quả tìm
kiếm
Sắp xếp kết quả tìm kiếm theo chủ đề, giúp người
sử dụng thuật tiện trong quá trình tìm kiếm thông tin từ
các máy tìm kiếm.
2.2.4. Yêu cầu phân cụm kết quả tìm kiếm
Bản chất dữ liệu cùng với việc sử dụng tương tác
của cụm các kết quả đặt ra yêu cầu mới và thách thức đối
với công nghệ phân cụm, như chi tiết trong danh sách sau
đây.
- Nhãn có ý nghĩa.
- Tính toán hiệu quả.
- Dữ liệu đầu vào Mô tả ngắn.
13
- Không biết số của các cụm.
- Các chồng chéo cụm.
- Giao diện người dùng đồ họa (GUI).
2.2.5. Các bước phân cụm kết quả tìm kiếm
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ự.
e. Tách từ, số hóa văn bản và biểu diễn tài liệu
Quá trình tách từ, vector hóa tài liệu là quá trình
tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong
từ điển.
2.2.5.3. Phân cụm kết quả tìm kiếm
2.3. Một số thuật toán phân cụm điển hình
15
2.3.1. Thuật Toán K-Means
Các bước thực hiện
B1. Chọn ngẫu nhiên K tâm cho K cụm. Mỗi cụm
được đại diện bằng các tâm của cụm.
B2. Tính khoảng cách giữa các đối tượng đến K
tâm (thường dùng khoảng cách Euclidean)
B3. Nhóm các đối tượng vào nhóm gần nhất
B4. Xác định lại tâm mới cho các nhóm
B5. Thực hiện lại bước 2 cho đến khi không có
sự thay đổi nhóm nào của các đối tượng
2.3.2. Thuật toán Hierarchical Agglomeraltive
Clustering
Đoạn mã giả của thuật toán HAC [3].
1. Đặt mỗi tài liệu d là một nhóm đơn {d}
2. Đặt G là tập tất cả các nhóm
3. while |G| > 1 do
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
GIÁ
3.1. Tập dữ liệu
Dữ liệu của thực nghiệm được lấy từ danh sách các
kết quả trả về của máy tìm kiếm google. Thực hiện gán
nhãn dữ liệu cho truy vấn với các từ khóa: “ô tô”. Trong
chương trình này thực nghiệm với 50 kết quả đầu tiên, bao
gồm tiêu đề, đoạn tóm tắt của tài liệu, URL và toàn bộ nội
dung của mỗi kết quả tìm kiếm.
Như vậy, tập dữ liệu vào của bài toán chứa nội
dung là các từ xuất hiện trong từng trang. Còn dữ liệu ra là
nhóm tập dữ liệu đó thành k cụm tùy ý.
3.2. Các công cụ thử nghiệm
Công cụ chính được sử dụng để tiến hành phân
cụm là phần mềm WEKA (Waikato Environment for
Knowledge Analysis.).
Để sử dụng được phần mềm Weka ta phải chuẩn bị
dữ liệu vào dưới dạng file ARFF.
18
Một file ARFF cho dữ liệu oto trong bảng, file này
đưa ra đặc trưng giá trị số. Dòng đầu tiên với một dấu %
những ghi chú. Tiếp theo ghi chú ở đầu của file là tên của
quan hệ (oto) và một khối định nghĩa các đặc trưng
(mua_bán_ô_tô,
tin_tức,
ô_tô_nhập_khẩu,
kỹ_thuật_lái_xe,
thị_trường_ô_tô,
người_đẹp_ô_tô,
đồ_chơi,
siêu_xe, giá_cả, đánh_giá). Các đặc trưng định danh được
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ó
- Xem thêm -