Tiểu luận

Phân cụm tập kết quả
tìm kiếm web dựa vào
tập thô dung sai
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

1
1
1

thư mục và xác định tài liệu mình cần tìm.
Thế nhưng việc tìm kiếm thông tin theo những kiểu trên vẫn không hiệu
quả , chiếm nhiều thời gian vì:
-Khối lượng dữ liệu khổng lồ và tính động của các trang Web, nên máy truy
tìm chỉ có thể sắp xếp một phần các chỉ mục của Web.
-Người sử dụng đặt câu hỏi truy vấn quá ngắn, không thể hiện được hết ý
định của họ , do vậy mà tập kết quả tìm kiếm Web là chung chung.
Từ ảnh hưởng hai nhân tố trên tập kết quả tìm kiếm Web có thể từ hàng
nghìn đến hang triệu tài liệu, do đó tìm được đúng tài liệu mình cần là công việc
vô cùng khó khăn.
1

2

3

4

5

6

7

Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai
vấn .
Cấu trúc và phương thức hoạt động của máy truy tìm Web như sau:
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

3
3
31.1.1. Web Crawler
Web Crawler là một trong hai thành phần trực tiếp tương tác với internet,
nó còn được gọi là web spider hoặc robot. Công việc chính của Web Crawler là
phát hiện những nguồn tài nguyên mới trên Web. Nó giải quyết vấn đề này bằng
cách thực hiện tìm kiếm đệ quy theo các đường link từ tất cả các trang đã được
duyệt .
Trong khi khai phá các nguồn tài nguyên mới trên Internet, Web Crawler
còn có nhiệm vụ kiểm tra xem các trang có còn hợp lệ không và chúng ta đã được
cập nhật hay chưa. Mục
đích của công việc này là giúp cho máy truy tìm cập nhật
được tất cả tài liệu của Web(kể cả các tài liệu cũ và mới).
1.1.2. Document Index (lập chỉ mục tài liệu)

(document index), vừa lưu trữ bảng chỉ mục tài liệu gốc .Mục đích của việc lưu
trữ bảng chỉ mục các tài liệu gốc (tài liệu đầy đủ) là tạo ra các sippet và phục vụ
cho việc lưu trữ các phiên bản của tài liệu.
1.1.4. Document Ranking
Chắc chắn rằng trong môi trường www, thậm chí đối với cả những câu hỏi
truy vấn hoàn thiện và chính xác , thì tập kết quả trả tìm kiếm vẫn là hang ngàn
hoặc hàng triệu tài liệu. Do vậy , cần phải có công nghệ thực hiện sắp xếp tập kết
quả thu về theo mức độ liên quan và mức độ quan tâm. Và đây chính là công việc
của Document Ranking.
1.1.5. Query Processor(bộ xử lý truy vấn)
Vai trò của Query Processor là phố
i hợp với các bộ trên để thực hiện trả lời
câu hỏi truy vấn của người sử dụng. Cụ thể , trong quá trình thực hiện Query
Processor kết hợp các thành phần document index, document cache, document
ranking để tạo ra tập kết quả tìm kiếm liên quan đến câu hỏi truy vấn.
1.1.6. Presentation interface(giao diện trình bày)
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

5
5
5

Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

6
6
6
quả thu về từ câu hỏi truy vấn được sắp xếp theo mối liên quan đến câu hỏi truy
vấn - những tài liệu liên quan nhất được xếp đầu danh sách.

Tùa ®Ò
snippet
M« t ¶
url

Mặc dù vậy cách sắp xếp này vẫn còn nhiều nhược điểm :
-Vì Ranked list trình bày kết quả theo mối quan hệ với câu hỏi truy vấn .
Do vậy có nhiều hơn 24 kết quả tìm kiếm thì ranked list trở thành không thực tế
đối với việc duyệt kết quả.
-Phương thức ranked list yêu cầu khắt khe về thứ tự giữa các kết quả tìm
kiếm với giả thuyết rằng các snippet luôn có thể so sánh đượ
c với nhau .Tuy nhiên
với câu hỏi truy vấn chung chung, sẽ có những kết quả trả về mà nó chỉ chứa chủ

8
8
8
CHƯƠNG II

PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB DỰA
VÀO TẬP THÔ DUNG SAI

2.1. Khái niệm phân cụm
Phân cụm là nhóm các đối tượng lại thành các cụm sao cho thoả mãn :
-Các đối tượng trong mỗi cụm là giống nhau hoặc gần nhau được xác định
bằng độ tương tự . Hay nói cách khác, các đối tượng trong mỗi cụm là tương tự
nhau.
-Những đối tượng không cùng một cụm là không tương tự nhau.
Cần phân biệt giữa phân lớp với phân cụm:
Phân lớp còn được gọi học có giám sát . Là quá trình xếp m
ột đối tượng
vào trong những lớp đã biết trước . Ví dụ phân lớp các bệnh nhân theo dữ liệu hồ
sơ bệnh án .
Phân cụm còn được gọi học không giám sát .Là quá trình xếp các đối tưọng
theo từng cụm tự nhiên, tức là số lượng và tên cụm chưa được biết trước .
Yêu cầu về việc phân cụm xuất phát từ lĩnh vực thống kê, nó được áp dụng
cho dữ liệu số
. Tuy nhiên, trong lĩnh vực khoa học máy tính và khai phá dữ liệu
thì khái niệm này được mở rộng cho cả dữ liệu text hoặc multimedia.
2.2. Phân cụm tập kết quả tìm kiếm Web
2.2.1. Khái niệm
Phân cụm tập kết quả Web là tổ chức sắp xếp tập kết quả tìm kiếm thành
một số nhóm chủ đề riêng theo cách bố cục tổng thể đến chi tiết, giống như các
thư mục. Ví d

∑∑∑
∑
==
=
−+
t
i
t
i
iiii
t
i
ii
yxyx
yx
11
22
1

Trong đó
-X (x
1
,x
2
,

…..,x
t
) và Y(y
1 1
1
1
0
0
0
Biểu diễn dưới dạng một điểm trong không gian nhiều chiều, doc1 được
biểu diễn (3,1) và doc2 được biểu diễn (2,4). H×nh1: C¸c ®èi t-îng ®-îc biÓu diÔn d-íi d¹ng
vector H×nh2: C¸c ®èi t-îng ®-îc biÓu diÔn d-íi d¹ng ®iÓm
2.2.3.Đặc điểm
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai


Yêu cầu
a.Liên quan
Phân cụm phải tạo ra được các nhóm chủ đề khác biệt từ tập kết quả tìm
kiếm Web, những kết quả có liên quan với nhau được sắp xếp vào cùng 1 nhóm và
không liên quan thì ở nhóm khác.
b.Tính tổng thể
Nhãn của mỗi chủ đề phải ngắn gọn và chính xác.Như vậy mới giúp người
sử dụng xác định nhanh chóng chủ đề quan tâm và tránh phải duyệt rải rác trên
toàn tập kết quả.
c.Nạ
p chồng
Vì mỗi một tài liệu (snippet) có thể thuộc về nhiều chủ đề do vậy một tài
liệu có thuộc vào nhiều nhóm khác nhau.
d.Snippet tolerance
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

1
1
1
2

u chứng của bệnh nhân tạo thành thông tin về
bệnh nhân . Các đối tượng được đặc trưng bởi cùng thông tin thì không thể phân
biệt (indiscermible) được với nhau. Quan hệ tương đương là cơ sơ toán học của
lý thuyết tập thô
Một tập bất kỳ các đối tượng không thể phân biệt (các đối tượng tương tự)
được gọi là tập cơ bản (elementary) và tạo thành nguyên tử (atom hay granule) của
tri thức vũ tr
ụ. Hợp bất kỳ các tập cơ bản được gọi là tập rõ (crisp) hay tập chính
xác (precise), ngược lại là tập thô(rough) hay không chính xác(imprecise).
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

1
1
1
3
3
3
Trong lý thuyết tập thô , bất cứ một khái niệm không rõ ràng nào đều
được thay bằng một cặp khái niệm không chính xác gọi là xấp xỉ dưới và xấp
xỉ trên của khái niệm không rõ ràng. Xấp xỉ dưới bao gồm tất cả các đối tượng
chắc chắn thuộc về khái niệm và xấp xỉ trên gồm tất cả các đối tượng có thể thuộc

(X) = {x ∈ U : [x]
R
⊆ X }
U
R
(X) = {x ∈ U : [x]
R
∩ X ≠ ∅ }
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai

1
1
1
4
4
4
Tập L
R
(X) là tập các đối tượng trong U mà theo quan hệ R thì chắc chắn
chúng là các đối tượng của X
Tập U

μ
(X) = {x ∈ U : μ(x, X) =1 }
U
μ
(X) = {x ∈ U : μ(x, X) >0 }
Trong đó
μ(x, X) =
R
R
x
Ux
Xx
][
][
),(
∩
=
μ

2.3.4.

Định nghĩa Hệ thông tin
Trong thực tế các đối tượng thường là
Thông thường hệ thông tin được mô tả bởi một cặp I=<U, A>
trong đó:
U={x
1
,x
2
, …,x

Hình thức đơn giản của hệ thông tin chính là bảng thông tin , trong đó dòng
là thể hịên đối tượng và cột là thể hiện thuộc tính của đối tượng. Với mỗi đối
tượng x ∈U, việc nắm bắt thông tin về x thông qua tập thuộc tính B⊆A được gọi
là vector thông tin
inf
B
(x)= { (a, f
a
(x)) : a ∈ B }
Thông thường bảng thông tin được cho dưới dạng mở rộng , bằng cách thêm
vào cột chứa thuộc tính quyết định vào bảng thông tin được goi là bảng quyết định

Trích đoạn Phương phỏp phõn cấp

---