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

Download miễn phí Đồ án Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai



Mục lục
CHƯƠNG 1 5
VẤN ĐỀ TÌM KIẾM THÔNG TIN TRÊN WEB 5
1.1. Máy truy tìm Web 5
1.1.1. Web Crawler 6
1.1.2. Document Index (lập chỉ mục tài liệu) 6
1.1.3. Document Cache(lưu trữ tài liệu) 7
1.1.4. Document Ranking 7
1.1.5. Query Processor(bộ xử lý truy vấn) 7
1.1.6. Presentation interface(giao diện trình bày) 7
2.1. Trình bày kết quả tìm kiếm của máy truy tìm Web Google 8
CHƯƠNG II 10
PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB DỰA VÀO TẬP THÔ DUNG SAI 10
2.1. Khái niệm phân cụm 10
2.2. Phân cụm tập kết quả tìm kiếm Web 10
2.2.1. Khái niệm 10
2.2.2. Phép đo độ tương tự 11
2.2.3. Đặc điểm 12
2.2.4. Hiệu quả 13
2.2.5. Yêu cầu 13
2.3. Lý thuyết tập thô 14
2.3.1. Giới thiệu 14
2.3.2. Quan hệ không thể phân biệt 15
2.3.3. Hàm thuộc thô 16
2.3.4. Định nghĩa Hệ thông tin 16
2.3.5. Không gian xấp xỉ tổng quát (Generalized approximation spaces) 18
2.4. Mô hình tập thô dung sai (TRSM) 20
2.4.1. Không gian tolerance của các từ 20
2.4.2. Biểu diễn tài liệu 22
3. Phương pháp trọng số mở rộng đối với xấp xỉ trên 22
Chương III Giải thuật phân cụm tập kết quả tìm kiếm web 24
3.1. Giải thuật 24
3.1.1. Tiền xử lý snippet 24
3.1.2. Trích chọn những từ đặc trưng của mỗi snippet 26
3.1.3. Sinh lớp tolerance 28
3.1.4. Giải thuật phân cụm K-means 30
3.1.5. Tạo nhãn cho mỗi nhóm 33
3.2. Một số thuật toán phân cụm không giám sát 33
3.2.1. Phương pháp phân hoạch 33
3.2.2. Phương pháp phân cấp 34
 
 





Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.

Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn


Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:


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 hay multimedia.
Phân cụm tập kết quả tìm kiếm Web
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ụ đối với câu hỏi truy vấn “Clinton” thì kết quả được trình bày theo các chủ đề như:”Bill Clinton”, “Hillary Clinton”, “George Clinton”, v.v.
Theo cách trình bày này cả những người sử dụng không có kinh nghiệm trong việc đặt câu hỏi truy vấn cũng có thể dễ dàng xác định nhanh chóng và chính xác tài liệu quan tâm . Mặt khác, đối với những người sử dụng đặt câu hỏi chung chung với mục đích biết thêm những chủ đề con sẽ không phải mất nhiều thời gian .Thay vào đó , họ chỉ cần duyệt theo từng nhóm chủ đề.
Phép đo độ tương tự
Bản chất công việc phân cụm là nhóm những đối tượng tương tự với nhau vào cùng một nhóm . Vậy cần có phép đo để đo độ tương tự giữa các đối tượng.
Đối với các đối tượng là tài liệu thì người ta thường hay sử dụng phép đo hệ số góc cosin để đo độ tương tự giữa hai tài liệu (mỗi tài liệu được biểu diễn dưới dạng một vector). Công thức đo độ tương tự như sau:
Cosin(X,Y) =
Trong đó
-X (x1 ,x2 , ..,xt) và Y(y1 ,y2 ,..,yt) là vector biểu diễn hai tài liệu
-xi ,yi là trọng số thành phần thứ I của vector X,Y tương ứng .
Chú ý:
-Khi hệ số góc cosin =1 nghĩa là hai snippet đó hoàn toàn tương tự nhau(trùng nhau)
-Khi hệ số góc cosin =0 nghĩa là hai snippet đó không hoàn toàn tương tự nhau(trùng nhau)
-Các tài liệu có thể được biểu diễn dưới dạng vector, điểm trong không gian nhiều chiều.
Ví dụ: 2 tài liệu doc1 và doc2, sau khi trích chọn các thuộc tính đặc trưng của snippet
Trong doc1:từ computer xuất hiện 3 lần, và từ finace xuất hiện 1 lần
Trong doc2:từ computer xuất hiện 2 lần, và từ finace xuất hiện 4 lần
Biểu diễn dưới dạng vector, doc1 được biểu diễn (3i+1j) và doc2 được biểu diễn (2i+4j)
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
Đặc điểm
-Phân cụm tập kết quả có tính phụ thuộc vào câu hỏi truy vấn của người sử dụng do tạo ra các nhóm chủ đề không thể dự tính được mà hoàn toàn phụ thuộc
-Kết quả phân cụm là giao diện của máy truy tìm.
Hiệu quả
Việc phân các tài liệu thành từng nhóm cơ bản đã được chứng minh là có hiệu quả trong quá trình duyệt một tập lớn các tài liệu . Do đó việc phân cụm tập kết quả cũng có những ưu điểm sau:
-Việc tổ chức tập kết quả tìm kiếm thành các chủ đề tạo điều kiện thuận lợi khi duyệt tập lớn các kết quả tìm kiếm.
-Tên của các chủ đề giúp người sử dụng phát hiện được chủ đề chính và do đó có thể xác định nhanh chóng chủ đề mình quan tâm.
-Việc phân chia tập kết quả thành các chủ đề giúp người sử dụng có thể nghiên cứu thêm tài liệu liên quan đến các chủ đề khác mà họ thường bỏ qua khi duyệt danh sách kết quả tìm kiếm được trình bày theo cách truyền thống ranked list, vì những tài liệu này ở rất xa trang đầu.
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
Giải thụât cần tạo được các chủ đề có chất lượng cao thậm chí khi nó chỉ được thực hiện trên tập kết quả tìm kiếm web.
e.Tốc độ
Vì giải thuật được sử dụng trong hệ thống online, do vậy một yêu cầu về tốc độ xử lý phân cụm là vô cùng quan trọng để không làm chậm quá trình xử lý truy vấn .
f.Tăng tốc độ xử lý
Để tiết kiệm thời gian , giải thuật cần xử lý từng snippet ngay sau khi nhận được từ máy truy tìm .
Lý thuyết tập thô
Giới thiệu
Lý thuyết tập thô (rough set theory) được Zdzislaw Pawlak đề xuất vào đầu những năm 1980 và nó nhanh chóng được coi như là một công cụ toán học mới để xử lý những thông tin mơ hồ và không chắc chắn . Phương pháp này tỏ ra hết sức quan trọng đối với lĩnh vực Trí tuệ nhân tạo và các ngành khoa học khác liên quan đến nhận thức, đặc biệt là lĩnh vực học máy, thu nhận tri thức, phân tích quyết định, phát hiện /khám phá tri thức từ cơ sở dữ liệu , các hệ chuyên gia , các hệ hỗ trợ quyết định , lập luận dựa trên quy nạp và nhận dạng.
Triết lý của tập thô dựa trên giả sử rằng mọi đối tượng trong vũ trụ đều gắn một thông tin nào đó (như dữ liệu, tri thức). Ví dụ, nếu các đối tượng là các bệnh nhân bị một bệnh nhất định , các triệ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).
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 về khái niệm. Hiệu của xấp xỉ trên và xấp xỉ dưới tạo thành khoảng ranh giới của khái niệm không rõ ràng .
Các phép toán cơ bản của lý thuyết tập thô được sử dụng để phát hện các mẫu cơ sở trong dữ liệu . Do đó, với một ý nghĩa nhất định phương pháp luận tập thô cũng chính là học máy , phát hiện tri thức , suy diễn thống kê và suy diễn quy nạp.
Lý thuyết tập thô ở một mức độ nhất định giao với nhiều công cụ toán học khác được dung để xử lý tri thức không đầy đủ . Trong lý thuyết tập thô khái niệm không rõ ràng dựa trên các xấp xỉ và sự không phân biệt được.
Quan hệ không thể phân biệt
Để có thể định nghĩa được xấp xỉ trên và xấp xỉ dưới trước hết chúng ta cần tìm hiểu về quan hệ không thể phân biệt.
Định nghĩa: Quan hệ R(R Í UxU) được gọi là quan hệ không thể phân biệt khi nó là một quan hệ tương đương .
Hay nói cách khác, quan hệ không thể phân biệt R là một quan hệ tương đương và chia vũ trụ thành một họ các lớp tương đương . Họ này được gọi là sự phân loại và ký hiệu U\R. Các đối tượng trong cùng một lớp tương đương là không phân biệt được , ngược lại là phân biệt được đối với R. Với "xÎU , lớp tương đương của x trong quan hệ R được biểu diễn là [x]R
Trong không gian xấp xỉ A=(U,R) xấp xỉ dưới và xấp xỉ trên của tập X được định nghĩa tương ứng như sau:
LR(X) = {x Î U : [x]R Í X }
UR(X) = {x Î U : [x]R Ç X ¹ Æ }
Tập LR(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 UR(X) là tập các đối tượng của U mà theo quan hệ R thì ta chỉ có nói rằng chúng có thể là các đối tượng của X .
Sự thật là LR Í X Í do vậy tập BNR = UR - LR được gọi là vùng biên của xấp xỉ hay là vùng không chắc chắn . Rõ rang , BNR là tập các đối tượng mà theo quan hệ R ta không thể xác định được chúng có thuộc vào X hay không .
Kết hợp cặp (LR, UR) tạo thành xấp xỉ thô hay tập thô của khái niệm X.
Hàm thuộc thô
Ta cũng có thể định nghĩa các xấp xỉ thông qua khái niêm hàm thuộc thô. Cho hàm thuộc thô mX : X ® [0,1] của tập X Í U, tập thô được định nghĩa như sau:
Lm(X) = {x Î U : m(x, X) =1 }
Um(X) = {x Î U : m(x, X) >0 }
Trong đó
m(x, X) =
Đị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=
trong đó:
U={x1 ,x2, ,x n} là một tập không rỗng hữu hạn các đối tượng gọi là vũ trụ
A là một tập không rỗng hữu hạn các thuộc tính . Với mỗi thuộc tính a Î A thì có tương ứng một hàm giá trị fa : U ® Va với Va là tập giá trị của thuộc tính a.
Vậy rõ ràng rằng bất kỳ một tập hữu hạn các đối tượng , mỗi đối tượng được mô tả bởi một tập các thuộc tính có thể xem là một hệ thông tin . Ví dụ như, một nhóm người , với mỗi người được mô tả bởi giới tính,tuổi, nghề nghiệp .
Hình thức đơn giản của hệ thông tin chính là bảng thông tin , trong đó dòn...
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status