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

Nội dung text: 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

1. 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
2. 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 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 11
3. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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 22
4. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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 2 3 4 5 6 7 33
5. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai CHƢƠNG I VẤN ĐỀ TÌM KIẾM THÔNG TIN TRÊN WEB Như chúng ta đều biết www như là từ điển bách khoa toàn thư , là thư viện khổng lồ sẵn sàng phục vụ bất cứ ai quan tâm thông qua việc truy cập internet. Đối với chúng ta nó là một trong những nguồn tài nguyên thông tin có giá trị nhất, nếu không có nó thì mọi hoạt động hang ngày sẽ kém hiệu quả. Nhưng vấn đề đặt ra là chúng ta phải truy cập và sử dụng nguồn tài nguyên ấy nhhư thế nào để có hiệu quả nhất. Để tìm được đúng thông tin cần tìm trong nguồn tài nguyên khổng lồ là một thách thức lớn . Chính vì vậy mà hiện nay đã và đang có rất nhiều hướng nghiên cứu để giải quyết vấn đề này. 1.1. Máy truy tìm Web Một trong những thành công nhất trong nghiên cứu và giải quyết vấn đề trên là việc tạo ra được máy truy tìm Web. Máy này có nhiệm vụ giúp người sử dụng tìm tài liệu mình quan tâm. Các tài liệu chủ yếu có dạng HTML, PDF, PS, MS Word và MS PowerPoint. Giao diện máy truy tìm thân thiện và rất dễ sử dụng , người sử dụng chỉ cần đặt câu hỏi truy vấnvà ra lệnh tìm. Máy sẽ trả về tập kết quả tìm kiếm(được gọi là các sinppet) liên quan đến câu hỏi truy vấn đó. Snippet miêu tả ngắn gọn nội dung của tài liệu Web(trang Web), nó thường bao gồm tựa đề , địa chỉ web của tài liệu (được gọi là URL)và một đoạn text trình bày nội dung liên quan đến câu hỏi truy vấn . Cấu trúc và phƣơng thức hoạt động của máy truy tìm Web nhƣ sau: 44
6. 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. 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) Mục đích chính của việc lập chỉ mục tài liệu là hỗ trợ tìm kiếm. Tìm tài liệu có chứa những từ trong câu hỏi truy vấn? Để thực hiện công việc này thì đa số các máy truy tìm sử dụng biến dữ liệu có cấu trúc inverted index. Inverted index giống như danh sách chỉ mục ở phần cuối của cuốn sách – trong đó với mỗi một từ là một danh sách liên kết các tài liệu có từ đó xuất hiện. Biến này có khả năng giúp máy truy tìm xác định chính xác tài liệu có chứa các từ trong câu hỏi truy vấn. Với 55
7. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai bảng chỉ mục như vậy , máy truy tìm có thể thực hiện tìm kiếm theo nhóm từ hoặc tìm kiếm từ lân cận. 1.1.3. Document Cache(lƣu trữ tài liệu) Nhiều máy phục vụ tìm kiếm vừa lưu trữ bảng chỉ mục tài liệu theo từ (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) 66
8. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Kết quả tìm kiếm Web được đưa đến người sử dụng thông qua giao diện này. Do vậy presentation interface đóng vai trò vô cùng quan trọng, nó ảnh hưởng toàn bộ chất lượng của máy truy tìm. Bởi vì người sử dụng chỉ cần quan tâm kết quả nhận được thông qua giao diện mà không quan tâm máy hoạt động xử lý tìm kiếm web như thế nào. 2.1. Trình bày kết quả tìm kiếm của máy truy tìm Web Google Cách biểu diễn tập kết quả tìm kiếm đến người sử dụng đóng vai trò vô cùng quan trọng . Nó giúp người sử dụng xác định được tài lệu họ cần tìm. Giao diện trình bày kết quả tìm kiếm được đánh giá tốt nếu không để người sử dụng gặp ngay những tài liệu được cho là không liên quan đến vấn đề cần tìm ở ngay đầu danh sách kết quả tìm kiếm . Tuy nhiên , tiêu chuẩn này quá khắt khe vì - Hầu hết người sử dụng thường đặt câu hỏi ngắn và chung chung cho máy truy tìm - Trong khi đặt câu hỏi cho máy truy tìm ,người sử dụng không đặt được câu hỏi đúng như ý định , bởi vì: khi người sử dụng muốn tìm một thông tin trên Web , nghĩa là trong suy nghĩ của họ đã hình thành khái niệm về cái mình muốn tìm. Khái niệm này được chuyển thành tập từ.Tập từ này được sử dụng để đặt câu hỏi truy vấn . Thế nhưng tính chính xác của việc chuyển đổi giữa khái niệm và tập từ lại phụ thuộc vào nhiều yếu tố, chẳng hạn như kinh nghiệm tìm kiếm , kiến thức cơ bản liên quan đến khái niệm đó , hoặc sự thành thạo về ngôn ngữ. Do đó đã tạo nên sự không cân xứng giữa khái niệm và câu hỏi truy vấn. Vì thế máy truy tìm không thể biết được chủ đề người sử dụng thực sự quan tâm. Hiện nay các máy truy tìm vẫn chưa đáp ứng được tiêu chuẩn trên, vì sử dụng phương thức trình bày kết quả Ranked list . Theo phương thức này tập kết 77
9. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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. snippet Tùa ®Ò 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ủ đề con , do vậy việc so sánh giữa các kết quả không cân xứng . 88
10. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Lý do trên đã tạo động lực cho người ta nghiên cứu và xây dựng phương thức trình bày kết quả mới khắc phục tất cả những nhược điểm của phương thức cũ . Phân cụm tập kết quả tìm kiếm Web là một trong những phương thức mới đang được nhiều người quan tâm nghiên cứu 99
11. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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ụ đố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 1100
12. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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ủ đề. 2.2.2. 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 phải 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: t  xi yi Cosin(X,Y) = i 1 t t 2 2  xi  yi  xi yi i 1 i 1 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) 1111
13. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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 1122
14. 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ả 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. 2.2.4. 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 phương thức truyền thống ranked list, vì những tài liệu này ở rất xa trang đầu. 2.2.5. 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 1133
15. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Giải thụât cần phải 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 phải xử lý từng snippet ngay sau khi nhận được từ máy truy tìm . 2.3. Lý thuyết tập thô 2.3.1. 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). 1144
16. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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. 2.3.2. 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  } 1155
17. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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ô hoặc tập thô của khái niệm X. 2.3.3. 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ô X : X [0,1] của tập X  U, tập thô được định nghĩa như sau: L(X) = {x U : (x, X) =1 } U(X) = {x U : (x, X) >0 } Trong đó [x] U (x, X) = (x, X ) R [x] R 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= 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 . 1166
18. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 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 infB(x)= { (a, fa(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 1177
19. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Ví dụ : Gọi U là tập các bênh nhân , U=(p1,p2,p3,p4,p5,p6,p7,p8)các bệnh nhân được miêu tả thông qua các triệu chứng ốm . Bảng biểu diễn hệ thông tin sau Thuéc tÝnh ®iÒu kiÖn TT quyÕt BÖnh nh©n ®Þnh §au ®Çu Nhøc mái NhiÖt ®é C¶m p1 Cã Cã B×nh th•êng Kh«ng P2 Cã Cã Cao Cã P3 Cã Cã RÊt cao Cã P4 Kh«ng Cã B×nh th•êng Kh«ng P5 Kh«ng Kh«ng Cao Kh«ng P6 Kh«ng Cã RÊt cao Cã P7 Kh«ng Kh«ng Cao Cã P8 Kh«ng Cã RÊt cao Kh«ng R là một quan hệ tương đương , được định nghĩa thông qua đẳng thức của hai thuộc tính Đau đầu và Nhức mỏi. Ví dụ: xRy có nghĩa là f§au ®Çu(x) = f§au ®Çu(y)  fNhiÖt đo(x) = fNhiÖt ®é(y) Quan hệ tương đương này phân tập U thành các lớp {p1}, { p2}, { p3},{ p4}, { p5, p7}, { p6, p8}.Như vậy theo mối quan hệ R thì ta không thể phân biệt bệnh nhân p5 với p7 , bệnh nhân p6 với p8. Gọi khái niệm X là bệnh nhân bị cảm , như vậyX={ p2 ,p3 ,p6 ,p7}. Lúc này , xấp xỉ của X theo mối quan hệ R được xác định như sau 1188
20. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai LR(X) = { p2, p3} UR(X) = { p2, p3, p5, p6, p7, p8} XÊp xØ trªn XÊp xØ d•íi ThÕ giíi thùc Vïng kh«ng ch¾c ch¾n 2.3.5. Không gian xấp xỉ tổng quát (Generalized approximation spaces) Như trên đã trình bày, lý thuyết tập thô kinh điển là dựa trên quan hệ tương đương để chia vũ trụ thành các lớp rời nhau. Theo định nghĩa, quan hệ tương R  UxU phải thỏa các tính chất sau: Tính phản xạ: xRx, với bất kỳ x U Tính đối xứng: xRy yRx, với bất kỳ x,y U Tính bắc cầu: xRy  yRz xRz, với bất kỳ x,y,z U Tuy nhiên trong thực tế, đối với một vài ứng dụng thì yêu cầu của quan hệ tương được chỉ ra là quá khắt khe. Vì trong nhiều lĩnh vực có rất nhiều khái niệm là không rõ ràng và có thể chồng lên nhau. Ví dụ: Chúng ta xét một tập các tài liệu khoa học. Mỗi tài liệu được mô tả thông qua tập các từ khóa. Dễ dàng nhận thấy rằng mỗi tài liệu có thể có nhiều từ 1199
21. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai khóa và một từ khóa có thể xuất hiện trong nhiều tài liệu. Vì vậy khi phân chia vũ trụ các tài liệu thành các lớp thì các lớp này có thể chồng lên nhau (nghĩa là một tài liệu có thể cùng thuộc vào nhiều lớp khác nhau). Do vậy, để phù hợp với thực tế cần phải giảm yêu cầu của quan hệ tương đương R bằng cách loại bỏ tính bắc cầu, tạo nên quan hệ mới được gọi là quan hệ Tolerance. 2.3.5.1. Định nghĩa không gian xấp xỉ tổng quát Không gian xấp xỉ tổng quát là một bộ bốn A=(U, I, v, P) trong đó : U là một tập không rỗng hữu hạn các đối tượng, hay còn được gọi là một vũ trụ I: U P(U) là một hàm không chắc chắn, trong đó P(U) là tập tất cả các tập con của U Hàm I được gọi là hàm không chắc chắn nếu thỏa:  x I(x), x U  y I(x) x I(y), x,y U Vậy quan hệ xRy y I(x) là một quan hệ tolerance vì nó thỏa mãn điều kiện phản xạ, đối xứng và I(x) là lớp tolerance của x. Như vậy, nếu chúng ta xét các đối tượng x U theo R thì I(x) là tập các đối tượng tương tự với x.  : P(U) x P(U) [0,1] là hàm thuộc mờ. Hàm thuộc mờ v hầu như giống hàm thuộc (được định nghĩa ở phần 3), tuy nhiên nó được mở rộng trên P(U) x P(U) để đo mức thuộc của hai tập. Hàm : P(U) x P(U) [0,1] được gọi là hàm thuộc mờ nếu thỏa: Y  Z (X, Y) < (X, Z) với X, Y, Z  U, tính đơn điệu 2200
22. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Kết hợp hàm không chắc chắn I và hàm thuộc mờ v, hàm thuộc thô được định nghĩa như sau: Với x U, X  U, ta có hàm thuộc thô I, (x, X) = (I(x), X) 1. P: I(U) {0,1} là hàm cấu trúc Trong đó, I(U) = { I(x) : x U)} Hàm này dùng làm điều kiện ràng buộc toàn cục trên các tập I(x). Trong khi sinh các xấp xỉ, chỉ những tập X I(U) có P(X) = 1 mới được xem xét, nghĩa là chỉ xét những đối tượng trong U. 2.3.5.2. Xấp xỉ Trong không gian xấp xỉ A thì các xấp xỉ của tập X  U được định nghĩa như sau: LA(X) = {x U : P(I(X)) =1  (x, X) =1 } U A(X) = {x U : P(I(X)) =1  (x, X) >0 } 2.4. Mô hình tập thô dung sai (TRSM) Với khả năng giải quyết linh hoạt tính gần đúng và tính mờ, tập thô dung sai được đánh giá là một công cụ đầy hứa hẹn để xác định mối quan hệ giữa từ và tài liệu. Bất cứ vấn đề nào trong lĩnh vực thu thập thông tin, đặc biệt trong việc phân cụm tài liệu thì việc định nghĩa mối quan hệ tương tự giữa tài liệu – tài liệu, từ – từ, từ – tài liệu là không thể thiếu được. Vì bản chất của bài toán phân cụm là tìm những đối tượng tương tự nhóm lại thành một nhóm. 2.4.1. Không gian tolerance của các từ Gọi D là tập các tài liệu, D={d1, d2, ., dN } và T là tập các từ có trong D, T={t1, t1, , tM}. Thông qua mô hình không gian vectơ, mỗi tài liệu di được biểu diễn bởi một vectơ có trọng số [wi1, wi2, ., wiM], với wij là trọng số của từ j trong tài liệu 2211
23. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai di. Trong mô hình tập thô dung sai, không gian tolerance được định nghĩa dựa trên toàn bộ các từ trong D. U= T = {t1, t1, , tM} Mục đích đặt ra là căn cứ vào mối quan hệ giữa các từ để thực hiện phân lớp các tài liệu. Với mục đích này, quan hệ tolerance R được xác định thông qua số lần cùng xuất hiện của các từ trong tập tài liệu D. Sở dĩ ở đây chọn số lần cùng xuất hiện của các từ để định nghĩa quan hệ tolerance là vì: theo các tài liệu hiện nay người ta xác định rằng giữa hai từ có 2 loại quan hệ tương tự: Tƣơng tự ngữ nghĩa, hai từ tương tự ngữ nghĩa có thể thay thế cho nhau trong một ngữ cảnh riêng. Ví dụ, trong ngữ cảnh: “I read the book” từ book có thể được thay thế bởi từ magazine mà không làm thay đổi nghĩa của câu, và do vậy 2 từ này được gọi là tương tự ngữ nghĩa. Tƣơng tự theo ngữ đoạn, hai từ tương tự theo ngữ đoạn có nghĩa là chúng cùng xuất hiện với nhau trong một đoạn text. Ví dụ, hai từ cut và knife là tương tự trong ngữ đoạn vì chúng có đặc điểm là thường cùng xuất hiện với nhau trong cùng đoạn text. Như vậy, việc xác định quan hệ tương tự giữa hai từ theo loại 2 là đơn giản, phù hợp với yêu cầu về thời gian đối với giải thuật phân cụm (không chọn tương tự ngữ nghĩa vì phải mất thời gian học từ). Lớp tolerance của từ * Hàm không chắc chắn I với ngưỡng  được định nghĩa như sau: I(ti) = { tj | fD(ti,tj) >  }  {ti} trong đó, fD(ti, tj) là số snippet trong tập D có cả hai từ ti và tj cùng xuất hiện. Rõ ràng rằng hàm trên thỏa điều kiện: - Phản xạ: ti I(ti) - Đối xứng: tj I(ti) ti I(tj),  i, j T. 2222
24. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Vì vậy quan hệ tolerence I  T x T được định nghĩa như sau: ti I tj tj I(ti), trong đó I(ti) là lớp tolerance của từ ti Dễ dàng nhận thấy rằng một lớp tolerance là thể hiện một khái niệm thông qua các từ chứa trong nó. Để điều chỉnh mức độ quan hệ của các từ trong lớp tolerance thì ta có thể thay đổi tham số  ( được cho phụ thuộc vào số lượng tài liệu trong tập D) * Để đo mức độ thuộc của tập này vào tập khác, hàm thuộc mờ được định nghĩa như sau: X  Y  (X, Y) X Rõ ràng là hàm này thỏa mãn tính đơn điệu. * Hàm thuộc  với ti T, X  T được định nghĩa như sau: I (ti )  X (ti , X )  (I (ti ), X ) I (ti ) Giả sử rằng tập các từ trong T không thay đổi trong trình ứng dụng, tất cả các lớp tolerance của các từ được xem là các tập cấu trúc: P( I (ti ) ) = 1  ti T * Lúc này, xấp xỉ dưới và xấp xỉ trên của X  U với không gian các lớp tolerance R = (T, I,  ,P) được xác định tương ứng như sau: LR(X) = {ti T |  (I (ti ), X )=1 } UR(X) = { ti T | >0 } Nếu ta xem X như là một khái niệm được mô tả mờ bởi các từ chứa trong nó thì UR(X) là tập các khái niệm có một vài điểm chung so với X, trong khi đó LR(X) là khái niệm nhân của X. 2.4.2. Biểu diễn tài liệu 2233
25. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Trong mô hình không gian vector chuẩn, một tài liệu được xem là một cái túi chứa các từ. Theo mô hình này chỉ những từ xuất hiện trong tài liệu mới được gắn trọng số khác không. Còn với mô hình TRSM, không chỉ xét những từ xuất hiện trong tài liệu mà còn xét cả những từ có quan hệ tương tự với những từ xuất hiện trong tài liệu, thông qua lớp tolerance của các từ, nhằm mục đích nâng cao chất lượng thể hiện nét đặc trưng của tài liệu. Được thực hiện đơn giản thông qua xấp xỉ trên. Gọi di = {ti1, ti2, , tik } là tài liệu trong D và ti1, ti2, , tik T là các từ trong di, xấp xỉ trên của di được định nghĩa như sau: UR(di) = { ti T |  (I (ti ),di ) >0 } 2.5 Phƣơng pháp trọng số mở rộng đối với xấp xỉ trên Phương pháp trong số TF*IDF thường được sử dụng để gắn trọng số cho vector tài liệu. Phương pháp này được đánh giá là tốt, vậy để có thể sử dụng phương pháp này cho xấp xỉ trên của tài liệu thì cần phải mở rộng để biết được từ nào được xuất hiện trong xấp xỉ trên của tài liệu, nhưng không xuất hiện trong tài liệu. Phương pháp trọng số mở rộng đối với xấp xỉ trên, được định nghĩa như sau N (1 log( f (t )))*log if t d di j f (t ) j D j N log f D (t j ) wij min t d wik * if t j in U R (di ) \ d i k i N 1 log f D (t j ) 0 if t U (d ) \ d j R i i Trong đó, wị là trọng số của từ tj trong tài liệu di. Phương pháp này đảm bảo chắc rằng những từ xuất hiện trong xấp xỉ trên của tài liệu di nhưng không 2244
26. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai xuất hiện trong tài liệu di bao giờ cũng có trọng số nhỏ hơn trọng số của bất kỳ một từ nào trong tài liệu di. Sau đó chuẩn hóa chiều dài vector của tất cả các vector tài liệu bằng công thức sau: wij wij (w )2 t d ij k i 2255
27. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Chƣơng III Giải thuật phân cụm tập kết quả tìm kiếm web 3.1. Giải thuật Input : Tập D gồm N snippet d1, d2, ., dN Output : K nhóm chủ đề khác biệt Mô hình dữ liệu: * Áp dụng mô hình không gian vector để biểu diễn kết quả tìm kiếm snippet. Cụ thể: - Mỗi snippet được biểu diễn bởi một vector nhiều chiều. Mỗi một chiều là tương ứng với một từ trong snippet. - Giả sử trong tập N snippet có M từ riêng biệt nhau. Khi đó, một snippet được biểu diễn dưới dạng một vector như sau: . di= (wi1, wi2 , , wiM) , trong đó wij là trọng số của từ thứ j trong snippet di Vì mỗi một snippet trong D có một chiều dài riêng (có số lượng từ khác nhau). Do vậy để giải thuật phân cụm cho ra kết quả chính xác thì cần chuẩn hóa số chiều của vectơ tương ứng với mỗi snippet trong D. Như vây, với tập D sẽ tạo thành một ma trận document-terms. Giải thật phân cụm TRC gồm có 5 pha: 1. Tiền xử lý snippet 2. Trích chọn từ đặc trưng của mỗi snippet (những từ thể hiện nội dung chính của snippet) 3. Sinh các lớp tolerance 4. Phân cụm 2266
28. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 5. Tạo nhãn cho từng nhóm 3.1.1. Tiền xử lý snippet Đây là một pha vô cùng quan trọng, nó ảnh hưởng rất lớn đến quá trình thực hiện phân cụm. Nhiệm vụ của pha này là làm giảm số từ trong mỗi snippet, do vậy nó có tác dụng làm giảm độ phức tạp tính toán của các pha sau và làm nâng cao chất lượng pha 2 - trích chọn từ đặc trưng của snippet. Công việc của pha tiền xử lý snippet: a.Phân tích từ vựng Phân tích từ vựng chính là nhận dạng từ trong tài liệu. Kết quả công việc việc này là tạo ra tập từ khác biệt. Tuy nhiên trong quá trình phân tích từ cần phải chú ý một vài trường hợp đặc biệt, chẳng hạn như số, dấu ngoặc, dấu chấm câu và trường hợp chữ hoa chữ thường; để có cách ứng xử đặc biệt. Ví dụ về cách ứng xử đặc biệt, số thường bị loại ra trong khi phân tích vì một mình nó không mang lại một ý nghĩa nào cho tài liệu (ngoại trừ một vài trường hợp đặc biệt, ví dụ trong thu thập thông tin về lĩnh vực lịch sử). Dấu chấm câu, ví dụ như “.”, “!”, “?”, “-“, v.v cũng thường được loại ra mà không có ảnh hưởng gì đến nội dung của tài liệu. Tuy nhiên cần phải chú ý trong một vài trường hợp, chẳng hạn đối với những từ ghép nối (state-of- the-art) là không được phép bỏ dấu “-“, vì sẽ làm thay đổi nghĩa của từ. b. Loại bỏ stop-words Những từ mà xuất hiện quá nhiều trong các snippet của toàn tập kết quả, thường thì không giúp ích gì trong việc phân biệt nội dung của các tài liệu. Ví dụ, những từ “web”, “site”, “link”, “www”, v.v là xuất hiện hầu hết trong các snippet Những từ như vậy được gọi là stop-words. Ngoài ra, những từ như là “a”, “the” (mạo từ”, “in” (giới từ) , liên từ “but”, động từ phổ biến có dạng “to”, “be”, và một số trạng từ và tính từ đặc biệt cũng được xem là stop-words. 2277
29. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Vì đặc điểm của stop-words nên chúng được loại bỏ mà không ảnh hưởng đến các pha sau. c. Stemming Stemming là loại bỏ tiền tố và hậu tố của từ để biến đổi nó thành từ gốc. Vì trong thực tế một từ gốc có thể có nhiều hình thái biến đổi, chẳng hạn như động từ, danh từ, tính từ, trạng từ; và giữa chúng có mối quan hệ ngữ nghĩa. Ví dụ như những từ: “clusters”, “clustering”, “clustered” là có cùng mối quan hệ với từ “cluster”. Do vậy cần phải Stemming để làm giảm được số lượng từ mà vẫn không làm ảnh hưởng đến nội dung tài liệu. Tuy nhiên có một vấn đề không tốt xảy ra khi stemming, vì giải thuật stemming sử dụng một tập các quy tắc đơn giản để loại bỏ tiền tố/hậu tố. Do vậy nó có thể sinh ra các từ không chính xác. Ví dụ như “computing”, “computation” sau khi stemming sẽ còn là “comput” trong khi đó từ đứng phải là “compute’. 3.1.2. Trích chọn những từ đặc trƣng của mỗi snippet Dữ liệu đầu vào của pha này chính là dữ liệu đầu ra của pha tiền xử lý tài liệu. a. Việc trích chọn được thực hiện theo quy tắc sau: - Loại bỏ số và những từ ngắn hơn 2 ký tự - Loại bỏ những từ xuất hiện trong câu hỏi truy vấn, bởi vì chúng ta đang thực hiện trên tập kết quả tìm kiếm trả về từ câu hỏi truy vấn, do vậy mà những từ nó sẽ xuất hiện hầu hết trong tất cả các snippet - Loại bỏ những từ mà nó xuất hiện ít hơn ngưỡng cho phép (ví dụ ít hơn 2 snippet. 2288
30. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai b. Sau khi trích chọn được các từ đặc trưng, ta xây dựng ma trận tần số document- terms : TF=[tfi,j]NxM Trong đó, N là số snippet trong D M là số từ được trích chọn trong toàn tập D tfi,j là số lần xuất hiện của từ j trong snippet di Mỗi một dòng TF[i] trong ma trận TF là thể hiện đặc trưng của snippet di thông qua tần số xuất hiện của mỗi từ. c. Sau đó áp dụng phương pháp trọng số TF*IDF đối với ma trận TF để tạo ra ma trận trong số document-terms W = [wi,j]NxM wi,j = tfij * log(n/dfi) Trong đó wi,j là trọng số của từ j trong snippet di . Mỗi dòng W[i] trong ma trận W là thể hiện đặc trưng của snippet di thông qua trọng số của mỗi từ. Chú ý: Phải áp dụng phương pháp trọng số TF*IDF (term frequency – inverse document frequency) vì những từ xuất hiện nhiều lần (nhân tố TF) trong tài liệu là góp phần thể hiện nội dung của tài liệu nhiều hơn so với những từ chỉ xuất hiện một vài lần. Tuy nhiên, những từ mà xuất hiện thường xuyên trong toàn tập tài liệu D thì sẽ không có ý nghĩa nhiều trong việc phân biệt nội dung giữa những tài liệu, vì vậy nhân tố idf phải được sử dụng để làm giảm vai trò của từ thường xuyên xuất hiện trong toàn tập tài liệu D. Ví dụ: Cho tập D= {d1, d2, d3, d4, d5, d6) 2299
31. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Doc Title d1 Languege modeling approach to information retrieval: the importance of a query term d2 Title language model for information retrieval d3 Two-stage language models for information retrieval d4 Building a web theaurus from web link structure d5 Implicit link analysis for small web search d6 Query type classification for web document retrieval Bảng 1: Tập các snippet và những từ được trích chọn (từ được gạch chân) Information Web Query Retrieval Model Language Document/Term d1 1 0 1 1 0 1 d2 1 0 0 1 1 1 d3 1 0 0 1 1 1 d4 0 1 0 0 0 0 d5 0 1 0 0 0 0 d6 0 1 1 1 0 0 Bảng 2: Ma trận tần số xuất hiện document-terms Document/Term Information Web Query Retrieval Model Language d1 0.301 0 0.4771 0.1761 0 0.301 d2 0.301 0 0 0.1761 0.4771 0.301 d3 0.301 0 0 0.1761 0.4771 0.301 d4 0 0.6021 0 0 0 0 d5 0 0.301 0 0 0 0 d6 0 0.301 0.4771 0.1761 0 0 Bảng 3: Ma trận trọng số document-terms 3300
32. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 3.1.3. Sinh lớp tolerance Mỗi một từ trong tập D đều có thể có tập các từ tương tự theo quan hệ tolerance (quan hệ cùng xuất hiện trong các snippet lớn hơn một ngưỡng  cho trước). Vậy mỗi một từ trong D sẽ sinh ra một lớp tolerance. Do vậy cần phải thực hiện pha này trước để tối ưu việc tính toán, đảm bảo tính toán xấp xỉ trên của tập các từ trong D được nhanh chóng. Các bước thực hiện: Ma trận cùng tần số xuất hiện (term co-occurrence) có dạng sau: TC = [tcx,y] MxM trong đó, tcx,y là số lần cùng xuất hiện của hai từ x và y trong các snippet của tập D. Lúc này, quan hệ tolerance R giữa 2 từ được định nghĩa như sau: xRy tcx,y >  Vậy, độ phức tạp tính toán là O(NxM2) ( trong đó độ phức tính toán của bước 1 là O(NxM), độ phức tính toán của bước 2 và 3 là O(M2)) 3311
33. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Ví dụ: Bước 1: Dựa vào ma trận tần số xuất hiện TF để tính ma trận xuất hiện nhị phân OC. Tuy nhiên trong trường hợp này OC=TF Document/Term Information Web Query Retrieval Model Language d1 1 0 1 1 0 1 d2 1 0 0 1 1 1 d3 1 0 0 1 1 1 d4 0 1 0 0 0 0 d5 0 1 0 0 0 0 d6 0 1 1 1 0 0 Bước 2: Tính ma trận cùng tần số xuất hiện (term co-occurrence) COC Term Information Web Query Retrieval Model Language Information 3 0 1 3 2 3 Web 0 3 1 1 0 0 Query 1 1 2 2 0 1 Retrieval 3 1 2 4 2 3 Model 2 0 0 2 2 2 Language 3 0 1 3 2 3 Bước3:Tính ma trận nhị phân tolerance(term tolerance binary)TOL với  > 1 Term Information Web Query Retrieval Model Language Information 1 0 1 1 1 1 Web 0 1 1 1 0 0 Query 1 1 1 1 0 1 Retrieval 1 1 1 1 1 1 Model 1 0 0 1 1 1 Language 1 0 1 1 1 1 Từ ma trận TOL xác định lớp tolerance của các từ trong D 3322
34. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Term Lớp Tolerance Information Information, query, retrieval, model, language Web Web, query, retrieval Query Information, web, query, retrieval, language Retrieval Information, web, query, retrieval, model,language Model Information, retrieval, model,language Language Information, query, retrieval, model,language Giải thuật : Sinh các lớp Tolerance Input: TF – ma trận tần số xuất hiện của các từ trong snippet ,  - ngưỡng cùng xuất hiện. Output: TOL - ma trận nhị phân tolerance của các từ dùng để xác định lớp tolerance của các từ 1. Tính ma trận xuất hiện nhị phân OC dựa trên ma trận tần số xuất hiện document–term TF như sau: OC = [oci,j]NxM, trong đó 1 if tf i, j 0 oci, j 0 otherwise Mỗi cột trong OC là một vector bit biểu diễn những từ xuất hiện trong một snippet, nếu từ xuất trong snippet bit được thiết lập giá trị 1. 2. Lập ma trận từ cùng tần số xuất hiện (term co-occurrence) COC = [cocx,y]MxM như sau: x y cocx,y = card(OC AND OC ) trong đó, cocx,y là số lần từ x và y cùng xuất hiện trong các snippet của D 3. Lập ma trận nhị phân tolerance ( term tolerance binary) TOL = [tolx,y] theo công thức sau: 1 if cocx,y  tol x,y 0 otherwise 3333
35. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Mỗi một dòng trong ma trận TOL tạo nên một vector bit biểu diễn lớp tolerance của mỗi từ trong D. 3.1.4. Giải thuật phân cụm K-means Giải thuật được thực hiện để sinh ra K nhóm ( K được chọn phụ thuộc vào chiều dài (số lượng các snippet) của D) Giải thuật Input: D – tập N snippet, K- số nhóm,  - ngưỡng tương tự với Output: K nhóm các snippet từ tập D (có thể nạp chồng) với giá trị thuộc mờ 1. Khởi tạo đại diện của mỗi nhóm C1, C2 , ., CK bằng các chọn ngẫu nhiên K snippet từ tập D. K đại diện nhóm được ký hiệu lần lượt như sau: R1, R2, , RK 2. repeat 3. for each di D do 4. for each cluster Ck, k=1, ,K do 5. Tính mức độ tương tự giữa xấp xỉ trên của sniptet di với phần tử đại diện Rk : S(UR(di), Rk) ( sử dụng phép đo lường theo hệ số góc cosin) 6. if S(UR(di), Rk) >  then 7. gán di vào nhóm Ck , với mức độ tương tự bằng giá hàm thuộc vào nhóm: m(di, Ck) = S(UR(di), Rk) 8. end if 9. end for 10. end for 11. for each cluster Ck do 12. Xác định lại đại diện nhóm Rk ( determine_cluster_representatives(RK)) 3344
36. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai 13. end for 14. until không có sự thay đổi hoặc chỉ thay đổi rất it giá trị của hàm thuộc /* Vì do yêu cầu ràng buộc mức độ tương tự giữa các snippet phải lớn hơn ngưỡng , do vậy mà sau tất cả các vòng lặp trên vẫn tồn tại một số snippet không được gắn vào bất cứ nhóm nào. Lúc này có 2 giải pháp được đặt ra: + Tạo ra một nhóm đặc biệt “Other” và gắn tất các snippet chưa thuộc nhóm nào vào trong nhóm “Other” + Gắn những tài liệu đó vào những nhóm mà chúng có láng giềng gần nhất cũng ở trong nhóm đó. Trong bài này thì chọn giải pháp 2 */ 15. for each du chưa được phân lớp (chưa được gắn vào bất kỳ nhóm nào) do 16. Tìm láng giềng gần nhất của du ký hiệu NN(du) với mức độ tương tự khác không 17. Trong số những nhóm mà NN(du) thuộc về, chọn một nhóm Ck mà NN(du) có hàm thuộc là mạnh nhất 18. Gán du vào nhóm Ck và tính giá trị của hàm thuộc (tính mức độ phụ thuộc của du vào nhóm Ck) như sau: m(du, Ck) = m(NN(du),Ck) * S(UR(du),UR (NN(du))) 19. end for 20. if cần thiết ta có thể xác định lại phần tử đại diện của nhóm Rk đối với những nhóm có sự thay đổi. * Giải thuật xác định đại diện nhóm (determine_cluster_representatives(RK)) Đại diện nhóm Rk thể hiện nét đặc trưng tiêu biểu của nhóm k, do đó : - Mỗi snippet di trong nhóm Ck phải chứa ít nhất một từ trong Rk . 3355
37. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai - Những từ trong Rk phải xuất hiện trong hầu hết các snippet thuộc nhóm Ck . - Không phải từ nào trong Rk cũng cần phải xuất hiện trong mỗi snippet thuộc về nhóm Ck . Trọng số đối với mỗi từ tj trong Rk được tính như sau: w d C ij i k wij di Ck t j di  Giải thuật: 1. Rk=  2. for all di Ck and tj di do 3. if f f (t ) / C  do Ck j k 4. Rk = Rk  tj 5. end if 6. end for 7. if di Ck and di  Rk =  then 8. R = R  argmax R  arg max k k k t j diwij 9. end if trong đó f (t ) là số tài liệu trong nhóm C có chứa từ t . Ck j k j 3.1.5. Tạo nhãn cho mỗi nhóm Pha tạo nhãn cho từng nhóm chủ đề là công việc vô cùng quan trọng. Vì nhãn thể hiện đặc trưng chung của nhóm và do đó việc tạo ảnh hưởng đến chất lượng toàn bộ giải thuật phân cụm. 3366
38. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Giải thuật tạo nhãn thực hiện dựa trên phương pháp n_gram để trích chọn nhóm từ trong phần tử đại diện của mỗi nhóm. Nhóm từ này được chọn làm nhãn (tên chủ đề) của nhóm. Theo phương pháp n_gram để nhóm từ thể hiện được tính sinh động của nhóm thì phải được chọn theo những tiêu chuẩn sau: + Mức độ thường xuyên xuất hiện của nhóm từ trong toàn tập D + Mức độ thường xuyên xuất hiện của nhóm từ trong một nhóm + Chiều dài của nhóm (số từ hình thành nên nhóm từ) Do vậy, bằng quan sát trực quan phương pháp TD*IDF có thể thấy rằng những nhóm từ tương đối xuất hiện ít trong toàn tập D nhưng xuất hiện thường xuyên trong từng snippet của mỗi nhóm sẽ là ứng cử viên sáng giá cho việc chọn làm nhãn của nhóm. 3.2. Một số thuật toán phân cụm không giám sát 3.2.1. Phƣơng pháp phân hoạch Thuật toán K-means Thuật toán K-medoids Thuật toán K-Medoids được thực hiện bằng cách chọn đối tượng ở gần tâm cụm nhất làm đại diện cho cụm đó (medoid). Nhưng so với K-Means thì K-Medoids có độ phức tạp tính toán lớn hơn. Cả hai thuật toán trên đề có nhược điểm chung là số lượng cụm K được cung cấp bởi người dùng. 3.2.2. Phƣơng pháp phân cấp Phân cụm phân cấp được chia thành hai phương pháp là : top-down và bottom-up. 1 Phương pháp bottom-up: Phương pháp này được thiết kế theo chiến lược từ dưới lên (bottom-up). Phương pháp này bắt đầu với mỗi đối 3377
39. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó ghép những cụm này thành các cụm lớn hơn cho tới khi tất cả đối tượng đều nằm trong một cụm duy nhất hoặc cho tối khi gặp điều kiện dừng. 2 Phương pháp top-down: Phương pháp này được thiết kế theo chiến lược trên xuống (top-down), nó thực hiện ngược lại so với phương pháp bottom-up, tức là chia nhỏ cụm lớn thành các cụm nhỏ hơn cho tới khi mỗi đối tượng được chứa trong một cụm riêng lẻ hoặc gặp điều kiện dừng như: đạt đến số lượng các cụm cho phép, hoặc khoảng cách giữa hai cụm gần nhất đã lớn hơn khoảng cách ngưỡng. Thuật toán CURE CURE là thuật toán sử dụng chiến lược bottom-up của phương pháp phân cụm phân cấp. Khác với hai thuật toán phân cụm phân hoạch ở trên thuật toán CURE sử dụng nhiều đối tượng để biểu diễn cho một cụm thay vì sử dụng các trọng tâm hay đối tượng tâm. Các đối tượng đại diện của một cụm ban đầu được chọn rải rác đều ở các vị trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định nào đó. Khi hai cụm có cặp đối tượng đại diện gần nhất sẽ được trộn lại thành một cụm. Thuật toán BIRCH BIRCH là thuật toán phân cụm phân cấp sử dụng chiến lược Top-down. Tư tưởng của BIRCH là không lưu toàn bộ đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các tham số thống kê. Đối với mỗi cụm dữ liệu, BIRCH chỉ lưu bộ ba (N, LS, SS), trong đó N là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm, và SS là tổng bình phương của các giá trị thuộc tính của các đối tượng trong cụm. Bộ ba này được gọi là đặc trưng cụm (Cluster Feature- CF). Khi đó các cụm trong tập dữ liệu ban đầu sẽ được cho dưới dạng một cây CF. 3388
40. Phân cụm tập kết quả tìm kiếm web dựa vào tập thô dung sai Cây CF là một cây cân bằng nhằm lưu các đặc trưng của cụm. Một cây CF chứa các nút cha và lá, nút cha chứa các nút con, nút lá không có con. Nút cha lưu giữ tổng các đặc trưng cụm của các nút con của nó. Cây CF có hai đặc trưng cơ bản : -Yếu tố nhánh: nhằm xác định số lượng nút con tối đa trong một nút cha. - Ngưỡng: nhằm xác định khoảng cách tối đa giữa bất kỳ một cặp đối tượng trong nút lá của cây CF, khoảng cách này chính là đường kính của các cụm con được lưu lại ở nút lá. 3399
41. PPhh©©nn cccôômm tttËËpp kkÕÕÕttt qquu¶¶ ttt×××mm kkiiiÕÕÕmm wweeebb ddùùaa vvµµoo tttËËpp ttthh«« dduunngg sssaaiii CHƢƠNG IV: MỘT SỐ GIAO DIỆN KHI CHẠY CHƢƠNG TRÌNH 4.1 Giao diện chƣơng trình chính(menu) 4.2 Giao diện chƣơng trình phân cụm dữ liệu 4.2.1 Giao diện chƣơng trình của sinh mã 4400
42. PPhh©©nn cccôômm tttËËpp kkÕÕÕttt qquu¶¶ ttt×××mm kkiiiÕÕÕmm wweeebb ddùùaa vvµµoo tttËËpp ttthh«« dduunngg sssaaiii 4.2.2 Giao diện chƣơng trình của tìm kiếm cụm 4.2.3 Giao diện chƣơng trình của K-Means 4411
43. PPhh©©nn cccôômm tttËËpp kkÕÕÕttt qquu¶¶ ttt×××mm kkiiiÕÕÕmm wweeebb ddùùaa vvµµoo tttËËpp ttthh«« dduunngg sssaaiii 4.3 Giao diện chƣơng trình của thuật toán phân cụm K-means 4422
44. PPhh©©nn cccôômm tttËËpp kkÕÕÕttt qquu¶¶ ttt×××mm kkiiiÕÕÕmm wweeebb ddùùaa vvµµoo tttËËpp ttthh«« dduunngg sssaaiii TÀI LIỆU THAM KHẢO 1. Tolerance rough set approach to clustering web search result, Ngô Chi Lăng -2003 2. Unsupervised Word Discriimation by Clustering Similar Contexts,Amruta Purandare -2004 3. Valued Tolerance and Decision Rlues, Jerzy Stefanowski 4. From n_gramn to collocation an evaluation of xtract 4433