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

Luận vă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

11

Mục lục

CHƢƠNG 1 ....................................................................................................................... 4

VẤN ĐỀ TÌM KIẾM THÔNG TIN TRÊN WEB.......................................................... 4

1.1. Máy truy tìm Web............................................................................................. 4

1.1.1. Web Crawler ............................................................................................. 5

1.1.2. Document Index (lập chỉ mục tài liệu).................................................... 5

1.1.3. Document Cache(lƣu trữ tài liệu)............................................................ 6

1.1.4. Document Ranking ................................................................................... 6

1.1.5. Query Processor(bộ xử lý truy vấn)........................................................ 6

1.1.6. Presentation interface(giao diện trình bày)............................................ 6

2.1. Trình bày kết quả tìm kiếm của máy truy tìm Web Google......................... 7

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) ... 19

2.4. Mô hình tập thô dung sai (TRSM) ................................................................ 21

2.4.1. Không gian tolerance của các từ............................................................ 21

2.4.2. Biểu diễn tài liệu...................................................................................... 23

3. Phƣơng pháp trọng số mở rộng đối với xấp xỉ trên......................................... 24

Chƣơng III Giải thuật phân cụm tập kết quả tìm kiếm web.................................... 26

3.1. Giải thuật......................................................................................................... 26

3.1.1. Tiền xử lý snippet........................................................................................ 27

3.1.2. Trích chọn những từ đặc trƣng của mỗi snippet ..................................... 28

3.1.3. Sinh lớp tolerance ....................................................................................... 31

3.1.4. Giải thuật phân cụm K-means................................................................... 34

3.1.5. Tạo nhãn cho mỗi nhóm............................................................................. 36

3.2. Một số thuật toán phân cụm không giám sát ............................................... 37

3.2.1. Phƣơng pháp phân hoạch ...................................................................... 37

3.2.2. Phƣơng pháp phân cấp........................................................................... 37

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

22

LỜI CẢM ƠN

Sau thời gian làm đồ án, lời đầu tiên em xin cảm ơn thầy giáo huớng dẫn

Th.s Nguyễn Trọng Thể đã tận tình hướng dẫn, chỉ bảo và tạo mọi điều kiện

thuận lợi để em hoàn thành tốt đồ án tốt nghiệp được giao.

Em xin chân thành cảm ơn các thầy cô giáo trong khoa công nghệ thông

tin trường Đại học dân lập Hải Phòng đã giảng dạy và cung cấp tất cả các kiến

thức chuyên môn cần thiết và quý giá nhất. Ngoài ra chúng em còn được rèn

luyện một tinh thần học tập và sáng tạo. Đây chính là tính cách hết sức cần

thiết để có thể thành công khi bắt tay vào công việc trong tương lai.

Cuối cùng em xin gửi lời cảm ơn tới tất cả người thân, bạn bè đã giúp đỡ,

động viên và đóng góp nhiều ý kiến quý báu cho em trong quá trình làm báo

cao tốt nghiệp này.

Em xin trân trọng cảm ơn!

Hải Phòng, tháng 8 năm 2007

Sinh viên

Nguyễn Thị Việt Ánh

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

33

LỜI MỞ ĐẦU

Ngày nay với sự bùng nổ thông tin , Word Wide Web(www) trở thành

nguồn tài nguyên khổng lồ và quý giá. Nó cung cấp cho chúng ta thông tin về mọi

lĩnh vực đời sống xã hội, khoa học v.v… Tuy nhiên đi đôi với sự thuận lợi ấy có

một vấn đề được đặt ra là chúng ta làm thế nào để truy cập và khai phá được

nguồn tài nguyên ấy hiệu quả nhất.

Từ vấn đề trên người ta đã nghiên cứu và tạo ra Máy truy tìm web(Web

search engine). Máy này có khả năng tìm kiếm thông tin linh hoạt , nhanh chóng

và rất dễ sử dụng . Người sử dụng chỉ cần đặt câu hỏi truy vấn về vấn đề cần quan

tâm là có được tập kết quả liên quan đến câu hỏi truy vấn đó.Hiện nay Google1

,

Altavista2

, HotBot3

, Lycos4

, AllTheWeb5

là những máy truy tìm hiệu quả và đang

được sử dụng rộng rãi .

Ngoài ra, người ta cũng đã tạo ra các thư mục Web , chẳng hạn như Yahoo6

,Open Directory Project7

. Theo kiểu này thì các tài liệu Web được sắp xếp thành

các thư có phân cấp, người sử dụng có thể tìm thông tin bắng cách duyệt các cây

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 http://www.google.com

2 http://www.altavista.com

3 http://www.hotbot.com

4 http://www.lycos.com

5 http://www.alltheweb.com

6 http://www.yahoo.com

7 http://www.dmoz.org