Luận văn Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM LUẬN VĂN THẠC SỸ Hà Nội – 2007 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM Ngành: Công nghệ thông tin. Mã số: 1.01.10 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HÀ QUANG THỤY Hà Nội - 2007 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 1 - Những lời đầu tiên Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo, tiến sỹ Hà Quang Thụy - người đã tận tình hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời xin cảm ơn tất cả những người thân yêu trong gia đình tôi cùng toàn thể bạn bè, những người đã luôn giúp đỡ và động viên tôi mỗi khi vấp phải những khó khăn, bế tắc. Cuối cùng, xin chân thành cảm ơn đồng nghiệp của tôi tại Trung tâm CNTT, NHNo&PTNT VN những người đã đem đến cho tôi những lời khuyên vô cùng bổ ích để giúp tháo gỡ những khó khăn, vướng mắc trong quá trình làm luận văn. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 2 - LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 01 tháng 11 năm 2007 Nguyễn Thị Thu Hằng Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 3 - MỤC LỤC DANH MỤC CHỮ VIẾT TẮT ........................................................................................ 5 DANH MỤC HÌNH VẼ, BẢNG BIỂU ............................................................................ 6 MỞ ĐẦU .......................................................................................................................... 7 CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB ................................... 9 1.1. Khai phá dữ liệu Web ....................................................................................... 9 1.1.1. Giới thiệu về Khai phá dữ liệu .................................................................. 9 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin ........................................... 11 1.1.3. Đặc điểm của dữ liệu Web ...................................................................... 12 1.1.4. Các hướng tiếp cận khai phá dữ liệu Web .............................................. 13 1.1.5. Nhu cầu Phân cụm tài liệu Web .............................................................. 14 1.2. Mô hình tìm kiếm thông tin ............................................................................ 15 1.2.1. Giới thiệu ................................................................................................ 15 1.2.2. Quy trình tìm kiếm thông tin trong hệ thống .......................................... 15 1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm ........................................... 18 1.3. Kết luận chương 1 ........................................................................................... 19 CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB ................................................... 20 2.1. Một số nội dung cơ bản về thuật toán phân cụm tài liệu ................................ 20 2.2. Tiêu chuẩn đánh giá thuật toán phân cụm ...................................................... 22 2.3. Các đặc tính của các thuật toán phân cụm web .............................................. 24 2.3.1. Mô hình dữ liệu ....................................................................................... 24 2.3.2. Độ đo về sự tương tự .............................................................................. 27 2.3.3. Mô hình phân cụm .................................................................................. 29 2.4. Một số kỹ thuật Phân cụm Web điển hình ...................................................... 30 2.4.1. Phân cụm theo thứ bậc ............................................................................ 30 2.4.2. Phân cụm bằng cách phân mảnh ............................................................. 33 2.5. Các yêu cầu đối với các thuật toán phân cụm Web ........................................ 35 2.5.1. Tách các thông tin đặc trưng ................................................................... 35 2.5.2. Phân cụm chồng lặp ................................................................................ 36 2.5.3. Hiệu suất ................................................................................................. 36 2.5.4. Khả năng khử nhiễu ................................................................................ 36 2.5.5. Tính tăng ................................................................................................. 37 2.5.6. Việc biểu diễn kết quả ............................................................................ 37 2.6. Bài toán tách từ tự động tiếng Việt ................................................................. 37 2.6.1. Một số khó khăn trong phân cụm trang Web tiếng Việt ......................... 37 2.6.2. Tiếng và Từ trong tiếng Việt .................................................................. 39 2.6.3. Phương pháp tách từ tự động tiếng Việt fnTBL ..................................... 39 2.6.4. Phương pháp Longest Matching ............................................................. 43 2.6.5. Kết hợp giữa fnTBL và Longest Matching ............................................. 44 2.7. Kết luận chương 2 ........................................................................................... 44 CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT TOÁN CÂY PHÂN CỤM TÀI LIỆU ........................................................................................ 45 3.1. Giới thiệu về thuật toán phân cụm trang Web có tính tăng ............................ 45 3.2. Thuật toán phân cụm cây hậu tố ..................................................................... 46 3.2.1. Mô tả ....................................................................................................... 46 3.2.2. Thuật toán STC ....................................................................................... 47 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 4 - 3.3. Thuật toán phân cụm sử dụng cây phân cụm tài liệu ...................................... 51 3.3.1. Giới thiệu ................................................................................................ 51 3.3.2. Trích chọn đặc trưng và phân cụm tài liệu ............................................. 51 3.3.3. Cây phân cụm tài liệu –DC Tree ............................................................ 55 3.4. Kết luận chương 3 ........................................................................................... 60 CHƯƠNG 4 - PHẦN MỀM THỬ NGHIỆM VÀ KẾT QUẢ THỰC NGHIỆM ...... 61 4.1. Giới thiệu ........................................................................................................ 61 4.2. Thiết kế cơ sở dữ liệu ..................................................................................... 62 4.3. Chương trình thử nghiệm ................................................................................ 65 4.4. Kết quả thực nghiệm ....................................................................................... 66 4.5. Kết luận chương 4 ........................................................................................... 69 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 5 - DANH MỤC CHỮ VIẾT TẮT AHC: Phân cụm tích tụ theo thứ bậc (Agglomerative Hierarchical Clustering) CSDL: Cơ sở dữ liệu DF: tần suất xuất hiện tài liệu (Document Frequency) DC-tree: Cây phân cụm tài liệu (Document Clustering Tree) fnTBL: Học dựa trên sự biến đổi (Fast Transformation-based learning) FCM: Fuzzy C-means FCMdd: Fuzzy C-Medoids IR: Mô hình tìm kiếm thông tin (Information Retrieval) IDF: tần suất nghịch đảo tài liệu (inverse document frequency) KDD: Khai phá tri thức (Knowledge Discovery in Databases) STC: Phân cụm cây hậu tố (Suffix tree clustering) TF: tần suất xuất hiện (term frequency) UPGMA: (Unweighter Pair-Group Method using Arithmetic averages) Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 6 - DANH MỤC HÌNH VẼ, BẢNG BIỂU Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 7 - MỞ ĐẦU World Wide Web là một kho thông tin khổng lồ với tiềm năng được coi là không có giới hạn. Khai phá Web là vấn đề nghiên cứu thời sự trong thời gian gần đây, đã thu hút nhiều nhóm nhà khoa học trên thế giới tiến hành nghiên cứu, đề xuất các mô hình, phương pháp mới nhằm tạo ra các công cụ hiệu quả hỗ trợ người dùng trong việc tổng hợp thông tin và tìm kiếm tri thức từ tập hợp các trang Web khổng lồ trên Internet. Phân cụm tài liệu Web là một bài toán điển hình trong khai phá Web, nhằm phân hoạch tập văn bản thành các tập con có tính chất chung, trong đó bài toán phân cụm các trang Web là kết quả trả về từ máy tìm kiếm là rất hữu dụng [4-6, 8-15, 18, 19, 22, 24]. Như đã biết, tập hợp các trang Web đáp ứng một câu hỏi trả về từ máy tìm kiếm nói chung là rất lớn, vì vậy, thuật toán phân cụm văn bản ở đây cần có được một tính chất rất quan trọng là tính "tăng" theo nghĩa thuật toán phân cụm không phải thực hiện chỉ trên toàn bộ tập dữ liệu mà có thể được thực hiện theo cách từ bộ phận dữ liệu tới toàn bộ dữ liệu [4, 6, 11, 14, 15, 24]. Điều đó cho phép thuật toán tiến hành ngay trong giai đoạn máy tìm kiếm đưa các trang web kết quả về. Luận văn tập trung khảo sát các phương pháp phân cụm trong Web có tính chất tăng và thực hiện một số thử nghiệm tích hợp các kết quả nghiên cứu nói trên vào một phần mềm tải trang Web theo dạng máy tìm kiếm. Đồng thời, luận văn triển khai một số bước đầu tiên trong việc áp dụng phân cụm cho các trang Web tiếng Việt. Luận văn xây dựng một phần mềm thử nghiệm và tiến hành các thử nghiệm phân cụm Web tiếng Việt. Ngoài Phần Mở đầu, Phần Kết luận và các Phụ lục, nội dung luận văn được chia thành 4 chương chính: Chương 1 – Khái quát về khai phá dữ liệu Web. Chương này giới thiệu những nội dung cơ bản nhất, cung cấp một cái nhìn khái quát về Khai phá dữ liệu Web. Đồng thời, luận văn cũng mô tả sơ bộ một hệ thống thông tin tìm kiếm và nhu cầu phân cụm áp dụng cho hệ thống này. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 8 - Chương 2 – Thuật toán phân cụm Web. Chương này trình bày một cách khái quát về các thuật toán phân cụm Web, những đặc trưng và yêu cầu đối với các thuật toán phân cụm Web. Những yêu cầu và độ đo áp dụng cho các thuật toán phân cụm Web cũng được trình bày trong chương này. Một số kiến thức cơ bản về tiếng Việt cũng được giới thiệu ở đây. Chương 3 – Thuật toán phân cụm cây hậu tố và thuật toán cây phân cụm tài liệu. Chương này đi sâu vào phân tích các thuật toán phân cụm Web có tính chất tăng. Luận văn tập trung vào hai thuật toán phân cụm Web có tính “tăng” là thuật toán STC và thuật toán phân cụm có sử dụng cấu trúc cây DC (DC-tree). Chương 4 – Phần mềm thử nghiệm và kết quả thực nghiệm. Chương này trình bày kết quả thực nghiệm phân cụm Web theo phần mềm thử nghiệm trên cơ sở thuật toán phân cụm DC-tree. Chương trình cài đặt thử nghiệm được viết trên ngôn ngữ lập trình C# trên nền tảng .Net Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ liệu. Phần mềm đã hoạt động, cho kết quả phân cụm, tuy nhiên, do thời gian hạn chế nên luận văn chưa tiến hành đánh giá kết quả phân cụm một cách chính thống. Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. Luận văn đã đạt một số kết quả khả quan bước đầu trong việc nghiên cứu và triển khai các thuật toán phân cụm Web có tính chất tăng, tuy nhiên, luận văn không tránh khỏi những sai sót. Rất mong được sự đóng góp ý kiến, nhận xét để tác giả có thể hoàn thiện được kết quả nghiên cứu. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 9 - CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB 1.1. Khai phá dữ liệu Web 1.1.1. Giới thiệu về Khai phá dữ liệu Khái niệm Khai phá dữ liệu (Data Mining) Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu. Thuật ngữ Data Mining ám chỉ việc tìm một tập nhỏ có giá trị từ một lượng lớn các dữ liệu thô. Có sự phân biệt giữa khái niệm "Khai phá dữ liệu" với khái niệm "Phát hiện tri thức" (Knowledge Discovery in Databases - KDD) mà theo đó, khai phá dữ liệu chỉ là một bước trong quá trình KDD. Quá trình KDD gồm một số bước sau: • Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết • Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại • Lựa chọn dữ liệu: Các dữ liệu có liên quan đến quá trình phân tích được lựa chọn từ cơ sở dữ liệu • Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý • Khai phá dữ liệu: Là một trong những bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để lựa chọn ra những mẫu dữ liệu. • Ước lượng mẫu: Quá trình đánh giá kết quả thông qua một độ đo nào đó • Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan cho người dùng. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 10 - Hình 1. Các bước trong KDD Các hướng tiếp cận và các kỹ thuật trong khai phá dữ liệu Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau: • Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. • Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản. Ví dụ: “50% những người mua máy tính thì cũng mua máy in”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v. • Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Người ta còn gọi phân lớp là học có giám sát (học có thầy). • Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Người ta còn gọi phân cụm là học không giám sát (học không thầy). • Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 11 - Ứng dụng của khai phá dữ liệu Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được sự quan tâm của rất nhiều nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể liệt kê ra đây một số ứng dụng điển hình [7,16]: • Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support) • Điều trị y học (medical treatment) • Text mining & Web mining • Tin-sinh (bio-informatics) • Tài chính và thị trường chứng khoán (finance & stock market) • Bảo hiểm (insurance) • Nhận dạng (pattern recognition) • .v.v. 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng như số lượng của các trang Web trên Internet thì vấn đề tìm kiếm thông tin đối với người sử dụng lại ngày càng khó khăn. Có thể nói nhu cầu tìm kiếm thông tin trên môt cơ sở dữ liệu phi cấu trúc (bao gồm dữ liệu văn bản) đã được phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy với Internet, con người đã làm quen với các trang Web cùng với vô vàn các thông tin. Trong những năm gần đây, Intrnet đã trở thành một trong những kênh về khoa học, thông tin kinh tế, thương mại và quảng cáo. Một trong những lý do cho sự phát triển này là giá cả thấp cần tiêu tốn khi công khai một trang Web trên Internet. So sánh với những dịch vụ khác như mua bản hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web "đòi" chi phí rẻ hơn rất nhiều mà lại được cập nhật nhanh chóng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thể nói không gian Web như là cuốn từ điển Bách khoa toàn thư. Thông tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Có thể nói Internet như một xã hội ảo, nó bao gồm các Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 12 - thông tin về mọi mặt của đời sống kinh tế, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh,... Tuy nhiên cùng với sự đa dạng và số lượng lớn thông tin như vậy đã nảy sinh vấn đề quá tải thông tin. Người ta không thể tìm tự kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung giống với yêu cầu của người tìm kiếm. Các tiện ích này quản lý dữ liệu trang Web như các đối tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy, đó là Yahoo, Google, Alvista, ... Mặt khác, giả sử chúng ta có các trang Web về các vấn đề Tin học, Thể thao, Kinh tể-Xã hội và Xây dựng...Căn cứ vào nội dung của các tài liệu mà khách hàng xem hoặc download về, sau khi phân lớp các yêu cầu như thế của khách hàng, chúng ta sẽ biết được khách hàng hay tập trung vào nội dung gì trên trang Web của chúng ta, mà từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm. Ngược lai, về phía khách hàng, sau khi được phục vụ phù hợp yêu cầu, khách hàng sẽ hướng sự quan tâm tới hệ thống của chúng ta hơn. Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài toán thời sự và cần được phát triển nghiên cứu. Như vậy, chúng ta có thể hiểu rằng khai phá Web như là việc trích chọn ra các thành phần được quan tâm hay được đánh giá là có ích cùng các thông tin tiềm năng từ các tài nguyên hoặc các hoạt động liên quan tới World-Wide Web [25, 26]. Một cách trực quan có thể quan niệm khai phá Web là sự kết hợp giữa Khai phá dữ liệu, Xử lý ngôn ngữ tự nhiên và Công nghệ Web: Khai phá web = Khai phá dữ liệu + Xử lý ngôn ngữ tự nhiên + World Wide Web. 1.1.3. Đặc điểm của dữ liệu Web * Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ Khai phá dữ liệu. * Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản truyền thống khác. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 13 - * Web là một nguồn tài nguyên thông tin có độ thay đổi cao * Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng * Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích 1.1.4. Các hướng tiếp cận khai phá dữ liệu Web Như đã phân tích về đặc điểm và nội dung các siêu văn bản ở trên, từ đó khai phá dữ liệu Web cũng sẽ tập trung vào các thành phần có trong trang Web. Đó chính là: 1. Khai phá nội dung trang Web (Web Content mining) Khai phá nội dung trang Web gồm hai phần: a. Web Page Content Nghĩa là sẽ sử dụng chỉ các từ trong văn bản mà không tính đến các liên kết giữa các văn bản. Đây chính là khai phá dữ liệu Text (Textmining) b. Search Result Tìm kiếm theo kết quả. Trong các máy tìm kiếm, sau khi đã tìm ra những trang Web thoả mãn yêu cầu người dùng, còn một công việc không kém phần quan trọng, đó là phải sắp xếp kết quả theo thứ tự dộ gần nhau với nội dung cần tìm kiếm. Đây cũng chính là khai phá nội dung trang Web. 2. Web Structure Mining Khai phá dựa trên các siêu liên kết giữa các văn bản có liên quan. 3. Web Usage Mining a. General Access Partern Tracking: Phân tích các Web log để khám phá ra các mẫu truy cập của người dùng trong trang Web. b. Customize Usage Tracking: Phân tích các mẫu truy cập của người dùng tại mỗi thời điểm để biết xu hướng truy cập trang Web của từng đối tượng người dùng tại mỗi thời điểm khác nhau Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 14 - Luận văn này tập trung chủ yếu vào nội dung “khai phá phá nội dung trang Web” và định hướng vào phân cụm tập trang web là kết quả tìm kiếm của các máy tìm kiếm. 1.1.5. Nhu cầu phân cụm tài liệu Web Một trong những bài toán quan trọng trong lĩnh vực khai phá Web là bài toán phân cụm Web. Phân cụm Web - nói một cách khái quát - là việc tự động sinh ra các "cụm" (lớp) tài liệu dựa vào sự tương tự của các tài liệu. Các lớp tài liệu ở đây là chưa biết trước, người dùng có thể chỉ yêu cầu số lượng các lớp cần phân loại, hệ thống sẽ đưa ra các tài liệu theo từng tập hợp, từng cụm, mỗi tập hợp chứa các tài liệu tương tự nhau. Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các tài liệu được lấy từ Web. Có hai tình huống phân cụm tài liệu. Tình huống thứ nhất là việc phân cụm trên toàn bộ một CSDL có sẵn gồm rất nhiều tài liệu Web. Thuật toán phân cụm cần tiến hành việc phân cụm toàn bộ tập dữ liệu thuộc CSDL đó. Tình huống này thường được gọi là phân cụm không trực tuyến (off- line). Tình huống thứ hai thường được áp dụng trên một tập tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về theo một truy vấn của người dùng. Trong trường hợp này, giải pháp phân cụm được tiến hành kiểu phân cụm trực tuyến (on-line) theo nghĩa việc phân cụm tiến hành theo từng bộ phận các tài liệu nhận được. Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân cụm ngay khi chưa có đủ tài liệu và phân cụm tiếp theo không cần phải tiến hành với dữ liệu đã được phân cụm trước đó. Do tập tài liệu trên Web là vô cùng lớn cho nên cách phân cụm trực tuyến là thích hợp hơn và phải đòi hỏi tính "gia tăng" của thuật toán phân cụm. Quá trình xử lý truy vấn và kết quả phân hạng được phản hồi từ các máy tìm kiếm phụ thuộc vào việc tính toán độ tương tự giữa truy vấn và các tài liệu. Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhưng nó thường quá ngắn và dễ xảy ra sự nhập nhằng. Như đã biết, trung bình các truy vấn trên Web chỉ gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn, truy vấn star dẫn đến sự nhập nhằng rất cao, các tài liệu lấy được liên quan đến astronomy, plants, animals, popular media and sports figures… Độ tương tự giữa các tài liệu của một truy từ đơn như vậy là có sự khác nhau rất lớn. Vì lẽ đó, Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 15 - nếu máy tìm kiếm phân cụm các kết quả theo từng chủ đề thì người dùng có thể nhanh chóng hiểu kết quả truy vấn hoặc tìm vào một chủ đề xác định. 1.2. Mô hình tìm kiếm thông tin 1.2.1. Giới thiệu Với sự phát triển nhanh chóng của công nghệ tin học, khối lượng thông tin lưu trữ trên máy tính ngày càng nhiều, vì vậy cần có các hệ thống tìm kiếm thông tin (IR: Information Retrieval) cho phép người dùng tìm kiếm một cách chính xác và nhanh nhất các thông tin mà họ cần trên kho dữ liệu khổng lồ này, trong đó, Internet chính là một kho dữ liệu như thế. Mục tiêu của hệ thống tìm kiếm là cung cấp công cụ để trả về cho người dùng các tài liệu trong kho dữ liệu có liên quan tới câu truy vấn [3,23,25,26]. Đó là nhu cầu chung của hầu hết các ngôn ngữ và tiếng Việt của chúng ta cũng phải là một ngoại lệ. Khác với các ngôn ngữ khác, tiếng Việt có nhiều đặc điểm riêng biệt và rất khó xử lý bằng máy tính, nên các đề tài liên quan đến các hệ thống tìm kiếm tiếng Việt còn rất ít. Mà nhu cầu tìm kiếm tài liệu trên kho tàng kiến thức của người Việt là rất lớn. 1.2.2. Quy trình tìm kiếm thông tin trong hệ thống Quy trình của một hệ thống tìm kiếm thông tin như sau [3,23,26]: • Người dùng muốn xem những tài liệu liên quan tới một chủ đề nào đó. • Người dùng cung cấp một mô tả về chủ đề đó dưới dạng câu truy vấn • Từ câu truy vấn này hệ thống sẽ lọc ra những cụm từ chỉ mục • Những cụm từ chỉ mục này sẽ được so khớp với những cụm từ chỉ mục của các tài liệu đã được xử lý trước đó. • Những tài liệu nào có mức độ liên quan cao nhất sẽ được trả về cho người sử dụng. Mục đích của hệ thống tìm kiếm thông tin là tìm kiếm và hiển thị cho người dùng một tập các thông tin thoả mãn nhu cầu của họ. Chúng ta định nghĩa Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 16 - chính xác cho thông tin cần thiết là “câu truy vấn” (query), và các thông tin được chọn là “tài liệu” (documents). Mỗi cách tiếp cận trong IR bao gồm hai thành phần chính (1) các kỹ thuật để biểu diễn thông tin (câu truy vấn, tài liệu), và (2) phương pháp so sánh các cách biểu diễn này. Mục đích là để tự động quy trình kiểm tra các tài liệu bằng cách tính toán độ tương quan giữa các câu truy vấn và tài liệu. Quy trình này được đánh giá là thành công khi nó trả về các kết quả giống với các kết quả được con người tạo ra khi so sánh câu truy vấn với các tài liệu. Có một vấn đề thường xảy ra đối với hệ thống tìm kiếm là những từ mà người dùng đưa ra trong câu truy vấn thường khác xa những từ trong tập tài liệu chứa thông tin mà họ tìm kiếm. Trường hợp như thế gọi là “paraphrase problem” (vấn đề về diễn giải). Để giải quyết vấn đề này, hệ thống đã tạo ra các hàm biểu diễn xử lý các câu truy vấn và các tài liệu một cách khác nhau để đạt tới một độ tương thích nào đó. Hình 2. Mô hình hệ thống tìm kiếm thông tin Gọi miền xác định của hàm biểu diễn câu truy vấn q là Q, tập hợp các câu truy vấn có thể có; và miền giá trị của nó là R, không gian thống nhất biểu diễn Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 17 - thông tin. Gọi miền xác định của hàm biểu diễn tài liệu d là D, tập hợp các tài liệu; và miền giá trị của nó là R2. Miền xác định của hàm so sánh c là R × R và miền giá trị của nó là [0,1] là tập các số thực từ 0 đến 1. Trong một hệ thống tìm kiếm lí tưởng: c(q(query),d(doc)) = j(query,doc), ∀ query ∈ Q, ∀ doc ∈ D, khi j: Q × D → [0,1] biểu diễn việc xử lý của người dùng giữa các mối quan hệ của 2 thông tin, được tính dựa trên một tiêu chuẩn nào đó(ví dụ: sự giống nhau về nội dung hay sự giống nhau về kiểu,...). Hình 2 minh hoạ mối quan hệ này. Có hai kiểu hệ thống tìm kiếm: tìm kiếm dựa trên so khớp chính xác và dựa trên sắp xếp. Mô hình trên đây có thể mô tả cả hai cách tiếp cận như thế. Trong hệ thống tìm kiếm dựa trên so khớp chính xác, miền giá trị của c được giới hạn hai lựa chọn là 0 và 1, và nó được chuyển sang nhị phân để quyết định liệu 1 tài liệu có thoả biểu thức bool được xác định bởi câu truy vấn hay không? Các hệ IR dựa trên sự so khớp chính xác thường cung cấp các tài liệu không sắp xếp thoả mãn câu truy vấn của người sử dụng, hầu hết các hệ thống tìm kiếm hiện nay đều dùng cách này. Cách hoạt động chi tiết của hệ thống sẽ được mô tả ở phần sau. Đối với hệ thống IR dựa trên sắp xếp, thì các tài liệu sẽ được sắp xếp theo thứ tự giảm dần về mức độ liên quan. Có 3 loại hệ thống tìm kiếm dựa trên sắp xếp: “ranked Boolean”, “probabilistic” và “similarity base”. Trong 3 cách này thì miền giá trị của c là [0, 1], tuy nhiên chúng khác nhau ở cách tính “giá trị trạng thái tìm kiếm” (“retrieval status value”): • Trong hệ thống dựa trên “ranked Boolean” giá trị này là mức độ mà thông tin thoả mãn biểu thức Bool được chỉ ra bởi các thông tin còn lại. • Trong hệ thống dựa trên “probabilistic”, khái niệm này hơi khác một chút, giá trị này là xác suất mà thông tin có liên quan đến một câu truy vấn. Rất nhiều hệ thống tìm kiếm dựa trên xác suất được thiết kế để chấp nhận câu truy vấn được diễn tả bằng ngôn ngữ tự nhiên hơn là một biểu thức bool. • Trong hệ thống tìm kiếm dựa trên sự giống nhau, giá trị trạng thái tìm kiếm được tính bằng cách tính mức độ giống nhau của nội dung thông tin. Trong các hệ thống tìm kiếm dựa trên sự so khớp chính xác, việc đánh giá hệ thống chủ yếu dựa trên việc đánh giá mức độ liên quan. Giả sử j là giá trị nhị Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 18 - phân và được cho trước. Nói cách khác, ta giả sử rằng các tài liệu hoặc có hoặc không có liên quan đến câu truy vấn, và độ liên quan giữa tài liệu và câu truy vấn do con người xác định là chính xác. Theo giả định này, tính hiệu quả của các hệ thống tìm kiếm dựa trên so khớp chính xác được đánh giá dựa trên hai đại lượng thống kê là “độ chính xác” ( precision) và “độ hồi tưởng” (recall). Độ chính xác là tỷ lệ các tài liệu được chọn, các tài liệu thực sự có liên quan đến các thông tin mà người dùng cần, độ hồi tưởng là tỉ lệ tài liệu có liên quan được sắp xếp chính xác theo độ liên quan bởi hệ thống tìm kiếm. Nói cách khác, độ chính xác bằng 1 trừ đi tỷ lệ cảnh báo sai, trong khi đó độ hồi tưởng đo mức độ hoàn chỉnh của việc tìm kiếm. Về hai độ đo đánh giá này cũng sẽ được đề cập chi tiết trong phần tiêu chuẩn đánh giá phân cụm cho thuật toán phân cụm ở phía sau. Việc đánh giá tính hiệu quả của hệ thống tìm kiếm dựa trên sắp xếp là phức tạp hơn. Một cách tính độ hiệu quả phổ biến cho các hệ thống này “độ chính xác trung bình”. Nó được tính bằng cách chọn 1 tập lớn hơn các tài liệu ở đầu danh sách có giá trị hồi tưởng giữa 0 và 1. Phương pháp thường được sử dụng là phương pháp tính dựa trên 5,7,11 điểm theo độ hồi tưởng. Độ chính xác sau đó sẽ tính cho từng tập một. Quy trình sẽ được lặp lại cho từng câu truy vấn, và tương ứng với mỗi độ chính xác trung bình sẽ cho một độ hồi tưởng. Mỗi giá trị trung bình của những số này sau đó sẽ được tính toán và ghi nhận như một đặc trưng của hệ thống. Độ chính xác trung bình càng lớn thì càng tốt, và việc so sánh chỉ thực sự có ý nghĩa khi chúng ta sử dụng cùng một tập tài liệu và câu truy vấn. Tuy nhiên độ chính xác trung bình cũng làm giảm đi mức độ thay đổi của các câu truy vấn có các đặc tính khác nhau (ví dụ như số lượng tài liệu có liên quan khác nhau). Hơn thế nữa, các tài liệu có liên quan thường tập trung ở đầu danh sách sắp xếp nên thông thường độ chính xác sẽ giảm mỗi khi tập tài liệu được mở rộng để tăng độ hồi tưởng. 1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm Như vậy, với việc phân tích nhu cầu phân cụm đối với các tài liệu Web, khi ta xây dựng một hệ thống tìm kiếm thì đồng thời ta cũng sẽ tiến hành tích hợp module phân cụm vào hệ thống này. Việc phân cụm văn bản như một phương thức tổ chức các dữ liệu trả lại khác giúp người sử dụng thay vì phải xem xét chọn lọc danh sách dài các văn bản theo thứ tự để tìm kiếm các văn bản liên Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 19 - quan thì chỉ cần xem xét trong các lĩnh vực mà người sử dụng quan tâm mà thôi. Như vậy hệ thống tìm kiếm sẽ trở nên hữu dụng hơn cho người sử dụng. 1.3. Kết luận chương 1 Sự phát triển của Internet dẫn đến nhu cầu tìm kiếm, khai thác, tổ chức, truy cập và duy trì thông tin đối với người sử dụng thường xuyên hơn. Những người sử dụng các máy tìm kiếm Web thường bị bắt buộc xem xét chọn lọc thông qua một danh sách thứ tự dài của các mẩu thông tin văn bản được trả trở lại bởi các máy tìm kiếm. Yêu cầu phân cụm tài liệu, cụ thể hơn là tài liệu Web trở thành bài toán cho các nhà khoa học nghiên cứu và giải quyết. Sau đây chúng ta sẽ nghiên cứu tiếp các vấn đề liên quan tới bài toán phân cụm nêu trên. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 20 - CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB 2.1. Khái quát về các thuật toán phân cụm tài liệu Như đã trình bày ở chương 1, phân cụm tài liệu đã và đang được nghiên cứu như là một cách cải tiến hiệu năng cho cách máy tìm kiếm bằng cách phân cụm trước toàn bộ tập hợp. M. Steinbach và các đồng tác giả [4] đã cung cấp một số nội dung khái quát về các thuật toán phân cụm tài liệu. Theo các tác giả [4], rất nhiều thuật toán phân loại tài liệu đã xuất hiện trong các tài liệu. Các thuật toán Agglomerative Hierarchical Clustering (AHC – Phân cụm tích tụ có thứ bậc) được sử dụng thường xuyên nhất. Những thuật toán này thường là chậm khi được áp dụng với một tập lớn các tài liệu. Các phương thức liên kết đơn (Single-link) và trung bình nhóm (group-average) thường có độ phức tạp thời gian khoảng O(n2) trong khi liên kết đầy đủ thường mất khoảng O(n3). Có nhiều điều kiện kết thúc cho các thuật toán AHC được đưa ra, nhưng chúng thường là được dựa trên các các quyết định cứng. Những thuật toán này rất nhạy cảm với các điều kiện dừng – khi thuật toán trộn lỗi nhiều phân cụm tốt, kết quả có thể là vô nghĩa đối với người dùng. Trong lĩnh vực phân cụm web những kết quả của các câu truy vấn có thể là cực kỳ nhiều (theo số lượng, độ dài, kiểu và độ quan hệ với tài liệu), việc nhạy cảm với các điều kiện dừng rất dễ dẫn đến các kết quả nghèo nàn. Một thuộc tính nữa của phân cụm Web đó là chúng ta thường xuyên nhận được nhiều phần ko cần thiết. Đó là một kiểu nhiễu có thể gây giảm độ ảnh hưởng của các tiêu chí ngừng thường được sử dụng hiện nay. Các thuật toán phân cụm có thời gian tuyến tính là các ứng cử viên cho yêu cầu về tốc độ đối với các phân cụm online [11]. Những thuật toán này bao gồm thuật toán K-Means có độ phức tạp thời gian là O(nkT), trong đó k là số lượng của các phân cụm và T là số lượng chu trình lặp và phương thức Single Pass – O(nK) với K là số lượng phân cụm đã được tạo ra. Một điểm mạnh của K-Means đó là không giống với các thuật toán AHC, nó có thể hoạt động trên các phân cụm chồng chéo. Bất lợi chính của nó đó là nó được coi như là hiệu quả nhất khi các phân cụm đã được tạo ra gần như Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 21 - làm tròn xấp xỉ trên đơn vị đo đạc được sử dụng. Điều này có nghĩa là không có lý do để tin rằng những tài liệu đó nên được phân loại vào các phân cụm xấp xỉ. Phương thức Single Pass cũng gặp phải vấn đề này cũng như gặp phải sự phụ thuộc thứ tự và có xu hướng đưa ra các phân cụm lớn. Theo [4,11], đây là một thuật toán phân cụm tăng nổi tiếng nhất. Buckshot và Fractionation là 2 thuật toán phân cụm nhanh, thời tuyến tính do Cutting phát triển năm 1992 [4]. Factionation là một sự xấp xỉ với AHC với việc tìm kiếm cho hai phân cụm gần nhau nhất không được thực hiện một cách tổng thể thay vào đó là thực hiện một cách cục bộ hoặc trong các vùng giới hạn. Thuật toán này hiển nhiên sẽ vấp phải cùng nhược điểm với AHC – các điều kiện dừng độc đoán và hiệu năng thấp khi có nhiều phần không liên quan. Buckshot là một giải thuận K-Means với việc các phân cụm trung tâm được tạo ra bởi việc áp dụng phân cụm AHC với một tập mẫu các tài liệu. Việc sử dụng tập mẫu là có rủi ro khi có thể có người có hứng thú với các phân cụm nhỏ mà có thể không có trong các mẫu. Tuy nhiên, tuy là các thuật toán nhanh song chúng không phải là thuật toán phân cụm tăng. Tất cả các thuật toán được nói ở trên coi một tài liệu là một tập các từ và không phải một tập các từ có thứ tự, do đó có mất đi các thông tin quan trọng. Các cụm từ đã được sử dụng từ lâu để cung cấp các chỉ mục từ trong các hệ thống IR. Việc sử dụng các phân tử từ vựng và các cụm từ có cú pháp đã được đưa ra để làm tăng khả năng dự đoán mà không cần đến việc phân tích lại tài liệu. Các cụm từ được sinh ra bởi các phương thức thống kê đơn giản đã và đang được sử dụng một cách thành công. Nhưng những phương pháp trên chưa được áp dụng rộng rãi trong việc phân cụm tài liệu. Ngoài ra, thuật toán sử dụng DC-tree [24] (Document Clustering Tree: cây phân cụm tài liệu) có thể phân cụm các tài liệu mà không cần tập huấn luyện. Với DC-tree, một đối tượng dữ liệu đưa vào không bắt buộc phải chèn vào mức(vị trí) thấp khi không tồn tạo một nút con tương tự cho đối tượng dữ liệu. Điều này ngăn cản một vài dữ liệu không tương tự từ việc đặt cùng nhau. Kết quả là thuật toán phân cụm dựa trên cấu trúc DC-tree là ổn định với yêu cầu đưa thêm tài liệu và dễ chấp nhận các tài liệu “nhiễu”. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 22 - Trên Web, có một vài nỗ lực để kiểm soát số lượng lớn tài liệu được trả lại bởi các máy tìm kiếm. Nhiều máy tìm kiếm cung cấp các tính năng tìm kiếm chọn lọc. Ví dụ, AltaVista gợi ý các từ nên được thêm hoặc loại bỏ khỏi câu truy vấn. Những từ này được tổ chức theo nhóm, nhưng các nhóm này không đại diện cho các phân cụm của tài liệu. Máy tìm kiếm Northern Light (www.nlsearch.com) cung cấp “Custom Search Folders” (Các thư mục tìm kiếm quen thuộc), các thư mục này được đặt tên bằng một từ hoặc một từ kép và bao gồm tất cả các tài liệu có chứa cái tên đó. Northern Light không tiết lộ cách thức sử dụng để tạo ra các thư mục đó cũng như chi phí của nó. Trong chương 3, luận văn đi sâu nghiên cứu hai thuật toán phân cụm có tính tăng thích hợp cho việc phân cụm trang Web và hơn nữa là dễ dàng áp dụng cho phân cụm Tiếng Việt- thuật toán phân cụm câu hậu tố (STC) và thuật toán phân cụm sử dụng DC-Tree. 2.2. Tiêu chuẩn đánh giá thuật toán phân cụm Các kết quả của bất cứ một thuật toán phân cụm nào cũng nên được đánh giá sử dụng một thước đo chất lượng thông tin để chỉ ra “độ tốt” của các phân cụm kết quả. Việc đánh giá phụ thuộc vào tri thức nào ta ưu tiên trong việc phân loại đối tượng dữ liệu (Ví dụ, chúng ta đã gán nhãn các dữ liệu hoặc không có sự phân loại dữ liệu). Nếu dữ liệu chưa được phân loại trước đó, chúng ta cần phải sử dụng các tiêu chuẩn chất lượng bên trong để cho phép so sánh giữa các tập phân cụm mà không phải tham khảo các tri thức bên ngoài. Nói theo cách khác, nếu dữ liệu đã được gán nhãn, chúng ta sử dụng việc phân loại này để so sánh kết quả phân cụm với các phân loại gốc; độ đo này được biết đến như một độ đo chất lượng ngoài. Chúng ta sẽ xem qua hai tiêu chuẩn chất lượng ngoài là Entropy và F-measure) và một tiêu chuẩn chất lượng trong là Overall Similarity. Entropy Một độ đo chất lượng ngoài đó là entropy, nó cung cấp một độ đo về “độ tốt” cho các phân cụm được lấy ra hoặc cho các phân cụm tại một cấp độ của một phân cụm theo thứ bậc. Entropy cho chúng ta biết sự đồng nhất của một phân cụm. Một phân cụm càng đồng nhất thì entropy của nó càng giảm và ngược lại. Entropy của một phân cụm mà chỉ chứa một đối tượng (cân bằng hoàn hảo) là 0. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 23 - Coi P là một kết quả phân chia của một thuật toán phân cụm bao gồm m phân cụm. Với tất cả phân cụm j trong P, chúng ta cần tính toán pij , với pij là khả năng một thành viên của phân cụm j thuộc vào lớp i. Entropy của mỗi phân cụm j được tính toán sử dụng công thức chuẩn: )log( ij i ijj ppE ∑−= , trong đó việc tính tổng được thực hiện với tất cả các lớp. Tổng entropy của một tập các phân cụm được tính toán như là tổng cộng entropy của mỗi phân cụm được tính toán dựa theo kích cỡ của mỗi phân cụm: ∑ = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ×= m j j j P EN N E 1 , trong đó Nj là kích cỡ của phân cụm j và N là tổng số lượng đối tượng dữ liệu. Như đã nói ở trên, chúng ta cần phải tạo ra các phân cụm với các entropy càng nhỏ càng tốt và entropy là một thước đo về độ đồng nhất (tương tự) của các đối tượng dữ liệu trong phân cụm. F-measure Độ đo chất lượng ngoài thứ hai là độ đo F (F-measure), một độ đo gộp ý tưởng về sự chính xác và khả năng nhớ lại từ thông tin thu về. Sự chính xác và khả năng nhớ lại của một phân cụm j đối với lớp i được định nghĩa là: i ij N N jiprecisionP == ),( j ij N N jirecallR == ),( trong đó Nij là số lượng thành viên của lớp I trong phân cụm j, Nj là số lượng thành viên của phân cụm j và Ni là số lượng thành viên của lớp i. Độ đo F của một lớp i được định nghĩa là: RP PRiF += 2)( Trong các mối liên hệ với lớp i, chúng ta tìm ra giá trị độ đo F lớn nhất trong các phân cụm j đối với nó và giá trị này là điểm của lớp i. Giá trị độ đo F của kết quả phân cụm P là trung bình trọng số của các độ đo F với mỗi lớp i. ( )( ) ∑ ∑ ×= i i P i iFi F Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 24 - Trong đó |i| là số lượng đối tượng trọng lớp i. Giá trị độ đo F càng cao thì việc phân cụm càng tốt vì độ chính xác càng lớn của việc gắn kết các lớp gốc. Overall Similarity Một độ đo chất lượng trong rất hay được sử dụng là độ đo tương tự toàn diện (Overall Similarity) và được sử dụng khi không có bất cứ thông tin nào từ bên ngoài như các lớp đã gán nhãn. Độ đo này phân cụm đo sự kết nối của các phân phân cụm bằng việc sử dụng trọng số tương tự của phân cụm trong ∑ ∈∈ 2 ),( 1 Sy Sx yxsim S , trong đó S là phân cụm được xem xét, và sim(x,y) là độ tương tự giữa 2 đối tượng x và y. 2.3. Các đặc tính của các thuật toán phân cụm web Trước khi chúng ta phân tích và so sánh các thuật toán khác nhau, chúng ta cần phải định nghĩa một số thuộc tính của các thuật toán và tìm ra các vùng vấn đề của các thuộc tính này. Phân tích về các phương pháp phân cụm tài liệu Web sẽ được giới thiệu ở ngày sau phần này. 2.3.1. Mô hình dữ 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ơ X = {x1, x2, …, xn} trong đó véc tơ xi, i= 1, …, 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). Việc tách lọc các đặc trưng cần thiết thông qua véc tơ đặc trưng phụ thuộc nhiều vào từng lĩnh vực. Số chiều của véc tơ đặc trưng là nhân tố chủ chốt trong thời gian chạy của thuật toán cũng như độ lớn của nó. Tuy nhiên, một vài lĩnh vực mặc định phải chấp nhận số chiều lớn. Tồn tại một vài phương pháp làm giảm các vấn đề liên quan đến cỡ, như việc phân tích nguồn gốc thành phần. Phương pháp Krishnapuram [8] đã có thể làm giảm véc tơ đặc trưng 500 chiều thành véc tơ 10 chiều; tuy nhiên độ chính xác của nó chưa được kiểm chứng. Từ bây giờ ta tập trung vào việc biểu diễn dữ liệu tài liệu và làm thế nào để bóc tách các đặc trưng chính xác. a, Mô hình dữ liệu tài liệu Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 25 - Hầu hết các phương thức phân cụm tài liệu sử dụng mô hình không gian véc tơ (Vector Space) để biểu diễn các đối tượng tài liệu. Mỗi tài liệu được biểu diễn bằng một véc tơ d, trong không gian véc tơ, d = {tf1, tf2, …, tfn} trong đó tfi (i=1,…,n) là tần suất xuất hiện (term frequency – TF) của từ ti trong tài liệu. Để biểu diễn tất cả các tài liệu với cùng 1 tập từ, chúng ta cần tách tất cả các từ tìm được trên tổng các tài liệu và sử dụng chúng như véc tơ đặc trưng của chúng ta. Thỉnh thoảng, một vài phương pháp được sử dụng đã gộp tần suất xuất hiện từ và tần suất nghịch đảo tài liệu (inverse document frequency TF-IDF). Tần suất xuất hiện tài liệu dfi là số lượng tài liệu trong tập N tài liệu mà từ ti xuất hiện. Một thành phần tấn suất nghịch đảo tài liệu (idf) được định nghĩa là log(N/dfi). Trọng số của từ ti trong tài liệu được định nghĩ là wi= tfi × log(N/dfi) [24]. Để cỡ của véc tơ đặc trưng là chấp nhận được, chỉ n từ có trọng số lớn nhất trong tất cả các tài liệu được sử dụng như là n đặc trưng. Wong và Fu [24] đã chỉ ra rằng họ có thể làm giảm số lượng từ đại diện bằng việc chỉ chọn những từ mà mức độ hồi tưởng (coverage) đủ trong tập dữ liệu. Một vài thuật toán [9,24] lặp lại việc sử dụng các tần suất xuất hiện từ (hoặc trọng số từ) bằng việc sử dụng véc tơ đặc trưng nhị phân, trong đó mỗi trọng số từ là 1 hoặc 0, phụ thuộc vào từ đó có trong tài liệu hay không. Wong và Fu [24] phản đối rằng tần suất xuất hiện từ trung bình trong tài liệu web là nhỏ hơn 2 (dựa theo các thí nghiệm, thống kê), vì nó không chỉ ra độ quan trọng thực sự của từ, do đó một sự phối với trọng số nhị phân sẽ là thích hợp hơn với vùng vấn đề này. Trước khi nói về tách đặc trưng, tập tài liệu sẽ được làm sạch bằng cách loại bỏ các từ dừng (stop-word: các từ có tần suất xuất hiện nhiều nhưng không có ý nghĩa như: và, với, …) và áp dụng một thuật toán làm đầy để chuyển đổi các mẫu từ khác nhau thành một mẫu chuẩn tương đương. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 26 - Một ví dụ về các stop-word Một mô hình khác về vấn đề biểu diễn tài liệu được gọi là N-gram. Mô hình N-gram giả sử rằng tài liệu là một chuỗi các ký tự, và sử dụng một cửa sổ trượt với kích cỡ n ký tự để quét và tách tất cả các chuỗi n ký tự liên tiếp trong tài liệu. N-gram là có thể chấp nhận được với các lỗi phát âm nhỏ bởi vì sự rườm rà trong các kết quả trả về của nó. Mô hình này cũng xử lý được các vấn đề nhỏ về phụ thuộc ngôn ngữ khi được sử dụng với thuật toán làm đầy. Vấn đề tương tự trong phương pháp tiếp cận này được dựa trên số lượng n-gram giữa hai tài liệu. Cuối cùng, một mô hình mới được giới thiệu bởi Zamir và Etzioni [5] là một phương pháp tiếp cận về cụm từ. Mô hình này tìm kiếm các cụm hậu tố giữa các tài liệu và xây dựng một cây hậu tố trong đó mỗi nút biểu diễn một phần của cụm từ (một nút hậu tố) và gắn với nó là các tài liệu chứa cụm từ hậu tố này. Phương pháp tiếp cận này rõ ràng là nắm được các thông tin quan hệ giữa các từ, rất có giá trị trong việc tìm kiếm độ tương tự giữa các tài liệu. b, Mô hình dữ liệu số Một mô hình trong sáng hơn về dữ liệu đó là mô hình số. Dựa trên ngữ cảnh vấn đề là có nhiều đặc trưng được tách, trong đó mỗi đặc trưng được biểu diễn như là một khoảng các giữa các số. Véc tơ đặc trưng luôn luôn ở trong một Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 27 - cỡ chấp nhận được, và nó phụ thuộc vào vấn đề đang được phân tích. Các khoảng cách đặc trưng thường được bình thường hóa vì thế mỗi đặc trưng có tác dụng như nhau khi tính toán độ đo khoảng cách. Độ tương tự trong trường hợp này là minh bạch vì việc tính toán khoảng cách giữa 2 véc tơ là rất đơn giản [17]. c, Mô hình phân loại dữ liệu Mô hình này thường được tìm thấy trong các vấn đề về phân cụm cơ sở dữ liệu. Thường thì các thuộc tính của bảng cơ sở dữ liệu là được phân loại và có một vài thuộc tính là kiểu số. Các phương pháp tiếp cận về phân cụm dựa trên thống kê được dùng để làm việc với kiểu dữ liệu này. Thuật toán ITERATE có thể coi là một ví dụ về việc làm việc với dữ liệu phân loại trên các dữ liệu thống kê [18]. Thuật toán K-modes cũng có thể coi là một ví dụ tốt [19]. d, Mô hình dữ liệu kết hợp Dựa vào các vùng vấn đề, thỉnh thoảng các đối tượng biểu diễn dữ liệu đặc trưng không có cùng kiểu. Một sự kết hợp giữa các kiểu dữ liệu số, phân loại, không gian hoặc text có thể được sử dụng. Trong trường hợp này, vấn đề quan trọng là nghĩ ra một phương pháp có thể nắm giữ tất cả các thông tin một cách hiệu quả. Một quy trình chuyển đổi nên được áp dụng để chuyển đổi từ một kiểu dữ liệu này thành một kiểu dữ liệu khác. Thỉnh thoảng một kiểu dữ liệu không thể áp dụng vào được, lúc đó thuật toán phải được chỉnh sửa để làm việc với các kiểu dữ liệu khác [18]. 2.3.2. Độ đo về sự tương tự Nhân tố chính trong thành công của bất kỳ một thuật toán phân cụm nào đó chính là độ đo về sự tương tự của nó. Để có thể nhóm các đối tượng dữ liệu, một ma trận xấp xỉ đã được sử dụng để tìm kiếm những đối tượng (hoặc phân cụm) tương tự nhau. Có một số lượng lớn các ma trận tương tượng đã được đề cập đến trong các tài liệu, ở đây, chúng ta chỉ xem qua một số ma trận thông thường nhất. Việc tính toán độ (không) tương tự giữa 2 đối tượng được thực hiện thông qua các hàm tính khoảng cách (distance), thỉnh thoảng cũng có thể sử Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 28 - dụng các hàm tính về độ không tương tự (dissimilarity). 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 được sử dụng của các hàm khoảng cách đó là “gia đình các khoảng cách Minkowski” [7], được mô tả như phía dưới: p n i p ii yxyx ∑ = −=− 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 Hamming ∑ = −=− n i ii yxyx 1 p = 2: Khoảng cách Euclidean ∑ = −=− n i ii yxyx 1 2 p = ∞: Khoảng cách Tschebyshev =− yx maxi=1,2,...,n ii yx − 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 sử dụng trong [4], [15], và [13]), được định nghĩa là: yx yxyx .),cos( = 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 [8], [9]), được định nghĩa là: ),max( ),min( ),( 1 1 i n i i i n i i yx yx yxd ∑ ∑ = == trong trường hợp các vector đặc trưng nhị phân, có thể đơn giản hóa thành: yx yx yxd ∪ ∩=),( Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 29 - Cần phải chú ý rằng từ “khoảng cách” không có gì nhập nhằng với “tương tự”. Những từ này là trái nghĩa với nhau, cho chúng ta biết độ tương tự giữa 2 đối tượng. Độ tương tự giảm khi khoảng cách tăng. Thêm một điểm cần chú ý khác đó là nhiều thuật toán sử dụng hàm khoảng cách (hoặc tương tự) để tính toán sự tương tự giữa 2 phân cụm, một phân cụm và một đối tượng, hai đối tượng. Việc tính toán khoảng cách giữa 2 phân cụm (hoặc các phân cụm và các đối tượng) yêu cầu một vector đặc trưng đại diện cho phân cụm. Thường thì các thuật toán phân cụm thường sử dụng một ma trận tương tự (similarity matrix). Một ma trận tương tự cỡ N × N ghi nhận các khoảng cách (hoặc độ tương tự) giữa từng cặp đối tượng. Hiển nhiên ma trận tương tự là một ma trận đối xứng do đó chúng ta chỉ cần lưu phần trên bên phải hoặc phần dưới bên trái của nó. 2.3.3. Mô hình phân cụm Bất cứ thuật toán phân cụm nào cũng thừa nhận một cấu trúc phân cụm nào đó. Đôi khi cấu trúc phân cụm không thực sự rõ ràng tùy theo nhu cầu của bản thân thuật toán phân cụm. Ví dụ, thuật toán k-means sử dụng các phân cụm hình cầu (hoặc các phân cụm lồi). Đó là vì theo cách k-means tìm kiếm phân cụm trung tâm và cập nhật các đối tượng thành viên. Nếu như không cẩn thận, chúng ta có thể kết thúc việc phân cụm với các phân cụm kéo dài (elongated cluster), trong đó kết quả là có ít phân cụm lớn và có nhiều phân cụm rất nhỏ. Wong và Fu [16] đã đưa ra một giải pháp để giữ kích cỡ phân cụm trong một khoảng nào đó, nhưng việc giữ kích cỡ phân cụm trong một khoảng nào đó không phải bao giờ cũng đáng thực hiện. Một mô hình động để tìm kiếm các phân cụm không thích hợp với cấu trúc của chúng đó là CHAMELEON, được đưa ra bơi Karypis [13]. 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). Trong ngữ cảnh phân cụm tài liệu thường mong muốn có các phân cụm chồng chéo bởi vì tài liệu có xu hướng có nhiều hơn một chủ đề (ví dụ một tài liệu có thể chứa thông tin về đua ô tô và các công ty ô tô). Một ví dụ khác về việc tạo ra các phân cụm chồng chéo là hệ thống cây hậu tố (STC) được đưa ra bởi Zamir và Etzionin [5]. Một cách khác để tạo ra các phân cụm chồng chéo đó là phân cụm mờ trong đó các đối tượng có thể Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 30 - thuộc vào các phân cụm khác nhau dựa vào các cấp độ khác nhau của tư cách thành viên [8]. 2.4. Một số kỹ thuật Phân cụm Web điển hình Kỹ thuật phân cụm được chia thành 2 nhóm chính: Phân cụm theo thứ bậc và phân cụm bằng cách phân mảnh. 2.4.1. Phân cụm theo thứ bậc Các kỹ thuật phân cụm theo thứ bậc đưa ra một chuỗi các phần chia lồng vào nhau với một phân cụm gốc ở trên cùng và các phân cụm đơn của các đối tượng đơn lẻ ở phía dưới. Các phân cụm ở cấp độ trên chứa các phân cụm phía dưới chúng theo thứ bậc. Kết quả của thuật toán phân cụm theo thứ bậc có thể xem như một cây, được gọi là một dendogram (Hình 3). Hình 3: Một ví dụ dendogram của phân cụm sử dụng phân cụm có thứ bậc Tùy thuộc vào định hướng của việc xây dựng thứ tự, chúng ta có thể chỉ ra các phương thức của phân cụm theo thứ bậc: tích tụ (Agglomerative) hay chia xẻ (Divisive). Phương thức tích tụ được sử dụng trong hầu hết các phân cụm theo thứ bậc. a, Phân cụm tích tụ theo thứ bậc (AHC) Phương thức này bắt đầu với tập các đối tượng là các phân cụm đơn lẻ, tiếp đó, tại mỗi bước kết nối 2 phân cụm giống giau nhất với nhau. Quá trình này Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 31 - được lặp lại cho đến khi số lượng phân cụm còn lại đạt đến một ngưỡng cho phép hoặc là nếu cần phải hoàn thành toàn bộ thứ bậc thì quá trình này sẽ tiếp tục cho đến khi chỉ còn 1 phân cụm. Phân cụm tích tụ làm việc theo mô hình tham ăn (greedy), trong đó cặp nhóm tài liệu được chọn cho việc tích tụ là cặp mà được coi là giống nhau nhất theo một số tiêu chuẩn nào đó. Phương thức này tương đối đơn giản nhưng cần phải định nghĩa rõ việc tính khoảng cách giữa 2 phân cụm. Có 3 phương thức hay được dùng nhất để tính toán khoảng cách này được liệt kê ở phía dưới. • Phương thức kết nối đơn (Single Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách ngắn nhất (minimal) giữa các thành phần nằm trong các phân cụm tương ứng. Phương thức này còn được gọi là phương pháp phân cụm “láng giềng gần nhất” (“nearest neighbour). yxST y Tx −=− ∈∈Smin • Phương thức kết nối toàn bộ (Complete Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách lớn nhất (maximal) giữa các thành phần thuộc vào các phân cụm tương ứng. Phương thức này còn được gọi là phương pháp phân cụm “láng giềng xa nhất” (“furthest neighbour”). yxST y Tx −=− ∈∈Smax • Phương thức kết nối trung bình (Average Linkage Method): Độ tương tự giữa 2 phân cụm S và T được tính toán dựa trên khoảng cách trung bình (average) giữa các thành phần của các phân cụm tương ứng. Phương thức này xét tất cả các cặp khoảng cách các đối tượng trong các 2 phân cụm. Phương thức này còn được gọi là UPGMA (Unweighter Pair-Group Method using Arithmetic averages ) TS yx ST y Tx . S ∑ ∈∈ −=− Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 32 - Karypis [13] đã phản đối các phương thức trên vì cho rằng chúng sử dụng một mô hình tĩnh của các liên kết và gần gũi của dữ liệu, và đã đưa ra một mô hình động để tránh được những vấn đề trên. Hệ thống đó được gọi là CHAMELEON, chỉ gộp 2 phân cụm nếu sự liên kết và gần gũi của các phân cụm là có quan hệ mật thiết với sự liên kết và gần gũi bên trong các phân cụm. Các kỹ thuật chất đống thường sử dụng thời gian cỡ Ω(n2) vì đặc trưng của nó là xem xét tất cả các cặp phân cụm có thể. Hệ thống Phân tán/Tập hợp (Scatter/Gather) được giới thiệu trong cuốn Cutting [15], đã sử dụng một nhóm tích tụ trung bình để tìm kiếm các phân cụm hạt nhân (seed) để sử dụng cho thuật toán chia phân cụm. Tuy nhiên, để tránh thời gian chạy bình phương, họ chỉ sử dụng nó với một ví dụ nhỏ của các tài liệu để phân cụm. Ngoài ra, phương thức trung bình nhóm đã được giới thiệu trong Steinbach [4] được coi là tốt hơn hầu hết các phương thức đo độ tương tự khác do tính ổn định của nó. b, Phương pháp phân cụm chia xẻ cấp bậc Những phương thức này làm việc từ trên xuống dưới, bắt đầu với việc coi toàn bộ các tập dữ liệu là một phân cụm và tại mỗi bước lại phân chia một phân cụm cho đến khi chỉ còn những phân cụm đơn của các đối tượng riêng lẻ còn lại. Chúng thường khác nhau bởi 2 điểm: (1) phân cụm nào được phân chia kế tiếp và (2) làm thể nào để phân chia. Thường thì một tìm kiếm toàn diện được thực hiện để tìm ra phân cụm để phân tách dựa trên một vài tiêu chuẩn khác nhau. Một cách đơn giản hơn có thể được sử dụng đó là chọn phân cụm lớn nhất để chia tách, phân cụm có độ tương tự trung bình ít nhất hoặc sử dụng một tiêu chuẩn dựa trên cả kích cỡ và độ tương tự trung bình. Trong Steinbach [4] đã làm một thí nghiệm dựa trên những chiến thuật này và phát hiện ra rằng sự khác nhau giữa chúng là rất nhỏ, do đó họ đã sắp xếp lại bằng việc chia nhỏ phân cụm lớn nhất còn lại. Chi nhỏ một phân cụm cần đưa ra quyết định xem những đối tượng nào được đưa vào phân cụm con. Một phương pháp được dùng để tìm 2 phân cụm con sử dụng k-means trả lại kết quả là một kỹ thuật lai ghép được gọi là kỹ thuật chia cắt k-means (bisecting k-means) [4]. Cũng có một cách khác dựa trên thống kê được sử dụng bằng thuật toán ITERATE [18], tuy nhiên, không cần thiết phải Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 33 - chia một phân cụm thành 2 phân cụm con, chúng ta có thể chia nó thành nhiều phân cụm con, tùy theo kết cấu của các đối tượng. 2.4.2. Phân cụm bằng cách phân mảnh Lớp thuật toán phân cụm này làm việc bằng cách nhận ra các phân cụm tiềm năng cùng một lúc trong khi lặp lại việc cập nhật các phân cụm để làm tối ưu một vài chức năng. Lớp các thuật toán nổi tiếng của nó là thuật toán K-means và các biến thể của nó. K-means bắt đầu bằng việc chọn lựa ngẫu nhiên k phân cụm hạt nhân, sau đó đưa các đối tượng vào phân cụm có ý nghĩa gần nó nhất. Thuật toán lặp lại việc tính toán ý nghĩa của các phân cụm và cấp độ thành viên của các đối tượng mới. Quá trình xử lý tiếp tục cho đến một số lần lặp nhất định hoặc khi không còn sự thay đổi nào được phát hiện trong ý nghĩa của các phân cụm [17]. Các thuật toán K-means có kích cỡ O(nkT) trong đó T là số lượng vòng lặp. Dù sao, một nhược điểm chính của K-means là nó giả định một cấu trúc phân cụm cầu và không thể được áp dụng với các miền dữ liệu mà các cấu trúc phân cụm không phải là hình cầu. Một biến thể của K-means cho phép sự chồng lặp của các phân cụm đó là C-means mờ (FCM: Fuzzy C-means). Thay vì có các quan hệ thành viên kiểu nhị phân giữa các đối tượng và các phân cụm tiêu biểu, FCM cho phép các cấp độ khác nhau của cấp độ thành viên [17]. Krishnapuram [8] đã đưa ra một phiên bản đã chỉnh sửa của FCM được coi là Fuzzy C-Medoids (FCMdd) trong đó các ý nghĩa được thay bằng các ngữ cảnh. Thuật toán này tương đối nhanh và có cỡ là O(n2) và có cường độ hoạt động nhanh hơn FCM. Do sự lựa chọn ngẫu nhiên của các phân cụm hạt nhân những thuật toán này, chúng đối lập với phân cụm có thứ bậc. Do đó kết quả của các lần chạy của thuật toán là không thực sự ổn định. Một vài phương pháp đã được cải tiến bằng cách tìm ra các phân cụm hạt nhân ban đầu “tốt” sau đó mới sử dụng các thuật toán này. Có một ví dụ rất hay trong hệ thống Phân chia/Thu thập [15]. Có một cách tiếp cận gộp cả việc phân cụm phân mảnh và phân cụm lai ghép đó là thuật toán chia cách K-means (Bisecting K-means) đã nói ở phần trước. Thuật toán này là một thuật toán phân chia trong đó việc phân chia phân cụm sử dụng K-means để tìm kiếm 2 phân cụm con. Trong Steinbach đã chỉ ra Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 34 - rằng hiệu suất của thuật toán Bisecting K-means là tuyệt vời so với K-means bình thường cũng như UPGMA [4] Cần phải chú ý rằng một đặc trưng quan trọng của các thuật toán có thứ bậc là hầu hết đều có cập nhật theo tính tăng và các đối tượng mới có thể được đưa vào các phân cụm liên quan rất dễ dàng bằng việc lần theo một đường dẫn nào đó tới vị trí thích hợp. STC [5] và DC- tree [24] là hai ví dụ về các thuật toán này. Nói theo cách khác các thuật toán phân chia đồng loạt thường yêu cầu việc cập nhật đồng loạt về ý nghĩa của các phân cụm và thậm chí là các đối tượng thành viên. Việc cập nhật có tính tăng là rất cần thiết với các ứng dụng hoạt động on-line. Một phương pháp nhằm thi hành thuật toán phân cụm là phân hoạch tập tài liệu vào k tập con hoặc các cụm D1, …, Dk để làm cực tiểu khoảng cách bên trong cụm ∑ ∑ ∈i Ddd ddi ),( 2, 121 δ hoặc làm cực đại sự tương tự bên trong cụm ∑∑ ∈i Ddd ddi ),( 2, 121 ρ . Nếu một biểu diễn bên trong của các tài liệu là có giá trị thì biểu diễn này cũng được dùng để xác định một biểu diễn của các cụm liên quan đến cùng mô hình. Chẳng hạn, nếu các tài liệu được biểu diễn sử dụng mô hình không gian vector, một cụm của các tài liệu có thể được biểu diễn bởi trọng tâm (trung bình) của các tài liệu vector. Khi một biểu diễn cụm là có giá trị, một mục tiêu có thể phân hoạch D thành D1, …,Dk để cực tiểu hóa ),( ii Dd Ddi G∑ ∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi G∑ ∑ ∈ ρ trong đó Di là biểu diễn vector của cụm i. Có thể xem xét tới việc gán tài liệu d cho cụm i như việc đặt một giá trị Boolean zd,i là 1. Điều này có thể phát sinh ra việc phân cụm mềm tại đó zd,i là một số thực từ 0 đến 1. Trong bối cảnh như vậy, ta có thể muốn tìm zd,i để cực tiểu hóa ),( ii Dd Ddi G∑∑ ∈ δ hoặc cực đại hóa ),( ii Dd Ddi G∑ ∑ ∈ ρ . Việc phân hoạch có thể thực hiện theo hai cách. Bắt đầu với mỗi tài liệu trong một nhóm của nó và kết hợp các nhóm tài liệu lại với nhau cho đến khi số các phân hoạch là phù hợp; cách này gọi là phân cụm bottom-up. Cách khác là có Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 35 - thể khai báo số các phân hoạch mong muốn và gán các tài liệu vào các phân hoạch; cách này gọi là phân cụm top-down. Có thể xem xét một kỹ thuật phân cụm bottom-up dựa vào quá trình lặp lại việc trộn các nhóm của các tài liệu tương tự nhau cho đến khi đạt được số cụm mong muốn, và một kỹ thuật top-down sẽ làm mịn dần bằng cách gắn các tài liệu vào các cụm được thiết đặt trước. Kỹ thuật bottom-up thường chậm hơn, nhưng có thể được sử dụng trên một tập nhỏ các mẫu để khởi tạo các cụm ban đầu trước khi thuật toán top-down tiến hành 2.5. Các yêu cầu đối với các thuật toán phân cụm Web Trong các thảo luận trước đó về các thuật toán phân cụm việc cần phải nhận ra các yêu cầu cho các thuật toán phân cụm tài liệu là cần thiết, việc này sẽ giúp chúng ta thiết kế ra các giải pháp hiệu quả và thiết thực hơn hướng tới các yêu cầu này. Tiếp đây là một danh sách của các yêu cầu này. 2.5.1. Tách các thông tin đặc trưng Vấn đề cốt lõi của bất cứ vấn đề phân cụm nào nằm hầu hết ở việc lựa chọn các tập đại diện của các đặc trưng của mô hình dữ liệu. Tập các đặc trưng được tách ra cần phải có đủ thông tin để nó có thể biểu diễn dữ liệu thực sự đang được phân tích. Ngược lại, dù thuật toán tốt đến mấy, nó sẽ vô dụng nếu như sử dụng những đặc trưng không chứa thông tin. Hơn nữa, việc làm giảm số lượng đặc trưng là rất quan trọng vì số chiều của không gian đặc trưng luôn có tác động đến hiệu suất của thuật toán. Một so sánh được hoàn thành bởi Yang và Pedersen [20] về hiệu quả của các phương pháp tách đặc trưng trong việc chia loại văn bản đã chỉ ra rằng phương pháp ngưỡng tần suất xuất hiện tài liệu (DF) cho những kết quả tốt hơn các phương thức khác và cũng cần ít các xử lý tính toán hơn. Hơn nữa, như đã đề cập ở trên, Wong và Fu [24] đã chỉ ra rằng họ có thể làm giảm số lượng từ đại diện bằng việc chỉ chọn các từ có ý nghĩa trong tập tài liệu. Mô hình tài liệu cũng thực sự rất quan trọng. Hầu hều các mô hình hay được sử dụng đều dựa trên các từ khác nhau được tách lọc từ tập tất cả các tài liệu và tính toán tần suất xuất hiện của từ cũng như tần suất xuất hiện của tài liệu như đã nói ở phần trước. Một mô hình tài liệu khác là mô hình dựa trên cụm từ, Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 36 - như mô hình được Zamir và Eztioni [5] đưa ra trong đó chúng tìm kiếm các cụm từ hậu tố có cùng điểm chung trong tài liệu sử dụng cấu trúc cây hậu tố. 2.5.2. Phân cụm chồng lặp Với tập dữ liệu bất kỳ, đặc biệt là trong lĩnh vực web, sẽ có xu hướng chứa một hoặc nhiều chủ đề. Khi phân cụm tài liệu, việc đưa những tài liệu vào các phân cụm liên quan với nó là cần thiết, điều này có nghĩa là vài tài liệu có thể thuộc vào nhiều hơn một phân cụm. Một mô hình phân cụm chồng lặp cho phép việc phân cụm tài liệu với nhiều chủ đề này. Có rất ít thuật toán cho phép phân cụm chồng lặp trong đó có phân cụm mờ [8] và cây hậu tố [5]. Trong vài trường hợp nếu việc mỗi tài liệu bắt buộc phải thuộc một phân cụm, một thuật toán không chồng lặp sẽ được sử dụng hoặc một tập của các phân cụm độc lập có thể được tạo ra bởi phân cụm mờ sau khi làm rõ các mối liên hệ giữa các phân cụm. 2.5.3. Hiệu suất Trong lĩnh vực web, mỗi một câu lệnh tìm kiếm có thể trả về hàng trăm và thỉnh thoảng là hàng nghìn trang web. Việc phân cụm các kết quả này trong một thời gian chấp nhận được là rất cần thiết. Cần phải chú ý rằng một vài hệ thống đã giới thiệu chỉ phân cụm trên các đoạn tin được trả lại trên hầu hết các máy tìm kiếm chứ không phải toàn bộ trang web [5]. Đây là một chiến thuật hợp lý trong việc phân cụm kết quả tìm kiếm nhanh nhưng nó không chấp nhận được với phân cụm tài liệu vì các đoạn tin không cung cấp đầy đủ thông tin về nội dung thực sự của những tài liệu này. Một thuật toán phân cụm online nên có khả năng hoàn thành trong thời gian tuyến tính nếu có thể. Một thuật toán offline thường hướng tới việc đưa ra các phân cụm có chất lượng cao hơn. 2.5.4. Khả năng khử nhiễu Một vấn đề có thể xảy ra với nhiều thuật toán phân cụm đó là sự xuất hiện của nhiễu và các dữ liệu thừa. Một thuật toán phân cụm tốt phải có khả năng giải quyết những kiểu nhiễu này và đưa ra các phân cụm có chất lượng cao và không bị ảnh hưởng bởi nhiễu. Trong phân cụm có thứ bậc, ví dụ các tính toán khoảng cách láng giềng gần nhất và láng giềng xa nhất, rất nhạy cảm với các dữ Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 37 - liệu thừa do đó không nên được sử dụng nếu có thể. Phương thức trung bình kết nối là thích hợp nhất với dữ liệu bị nhiễu. 2.5.5. Tính tăng Một đặc trưng rất đáng quan tâm trong các lĩnh vực như web đó là khả năng cập nhật phân cụm có tính tăng. Những tài liệu mới cần phải được đưa vào các phân cụm tương ứng mà không phải phân cụm lại toàn bộ tập tài liệu. Những tài liệu đã được chỉnh sửa nên được xử lý lại và đưa đến các phân cụm tương ứng nếu có thể. Thật đáng để nhớ rằng tính tăng càng hiệu quả thì hiệu suất cũng được cải thiện. 2.5.6. Việc biểu diễn kết quả Một thuật toán phân cụm là tốt nếu nó có khả năng biểu diễn một sự mô tả của các phân cụm mà nó đưa ra ngắn gọn và chính xác với người sử dụng. Các tổng kết của phân cụm nên có đủ tiêu biểu về nội dung tương ứng để người sử dụng có thể đưa ra quyết định nhanh xem phân cụm nào mà họ cảm thấy quan tâm. 2.6. Bài toán tách từ tự động tiếng Việt Đối với tiếng Anh, ta tách từ dựa vào khoảng trắng. Tuy nhiên đối với tiếng Việt, công việc này tương đối khó khăn. Cấu trúc tiếng Việt rất phức tạp, không chỉ đơn thuần dựa vào khoảng trắng để tách từ. Hiện nay có rất nhiều công cụ để tách từ tiếng Việt, mỗi phương pháp có ưu, khuyết điểm riêng và tất nhiên, chưa thể coi rằng là phương pháp tách từ nào là tốt nhất. Phần này trình bày một vài phương pháp tách từ tiếng Việt. Nhưng trước đó chúng ta sẽ xem xét một số khó khăn trong phân cụm trang Web tiếng Việt. 2.6.1. Một số khó khăn trong phân cụm trang Web tiếng Việt Hiện nay, chúng ta đã quen thuộc với rất nhiều công cụ hỗ trợ việc tìm kiếm thông tin như Google, Yahoo Search, AltaVista, ... Tuy nhiên, đây là công cụ của người nước ngoài nên chúng chỉ giải quyết tốt đối với các yêu cầu của họ. Chúng ta cũng có một số công cụ hỗ trợ tìm kiếm thông tin tiếng Việt như: Vinaseek, Netnam, ... Các công cụ này cũng tách từ chủ yếu dựa vào khoảng Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 38 - trắng nên việc tìm kiếm cũng chưa được cải thiện. Nhìn chung, để xây dựng một hệ thống tìm kiếm thông tin Tiếng Việt, chúng ta gặp khó khăn trong việc tách từ Tiếng Việt và xác định bảng mã tiếng Việt. Đồng thời đó cũng chính là khó khăn trong việc phân cụm các tài liệu bằng tiếng Việt vì bước đầu tiên của phân cụm cũng chính là tách từ tiếng Việt [1]. Vấn đề bảng mã Tiếng Việt Không như tiếng Anh, tiếng Việt có rất nhiều bảng mã đòi hỏi phải xử lý. Một số công cụ tìm kiếm tiếng Việt hỗ trợ bảng mã rất tốt như Vinaseek, hỗ trợ mọi bảng mã (VNI, TCVN3, ViQR, ...) Khó khăn trong tách từ Tiếng Việt Có thể nói tách từ là giai đoạn khó khăn nhất khi xây dựng một hệ tìm kiếm thông tin Tiếng Việt và phân cụm tài liệu Tiếng việt. Đối với tiếng Anh, việc xác định từ chỉ đơn giản dựa vào khoảng trắng để tách từ. Ví dụ, câu “I am a student” sẽ được tách thành 4 từ: I, am, a, student. Tuy nhiên, đối với Tiếng Việt, tách dựa vào khoảng trắng chỉ thu được các tiếng. Từ có thể được ghép từ một hay nhiều tiếng. Từ phải có ý nghĩa hoàn chỉnh và có cấu tạo ổn định. Câu “Tôi là một sinh viên” được tách thành 4 từ: Tôi, là, một, sinh viên. Trong đó, từ “sinh viên” được hình thành từ hai tiếng “sinh” và “viên”. Hiện nay có rất nhiều phương pháp được sử dụng để tách từ Tiếng Vịêt. Tuy nhiên, với sự phức tạp của ngữ pháp Tiếng Việt nên chưa có phương pháp nào đạt được chính xác 100%. Và việc lựa chọn phương pháp nào là tốt nhất cũng đang là vấn đề tranh cãi. Các khó khăn khác Tiếng Việt có các từ đồng nghĩa nhưng khác âm. Các công cụ hiện nay không hỗ trợ việc xác định các từ đồng nghĩa. Vì vậy, kết qủa trả về sẽ không đầy đủ. Ngược lại, có những từ đồng âm khác nghĩa. Các hệ thống sẽ trả về các tài liệu có chứa các từ đã được tách trong câu hỏi mà không cần xác định chúng có thực sự liên quan hay không. Vì vậy, kết quả trả về sẽ không chính xác. Một số từ xuất hiện rất nhiều nhưng không có ý nghĩa trong tài liệu. Các từ như: và, với, nhưng, ... có tần số xuất hiện rất lớn trong bất cứ văn bản nào. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 39 - Nếu tìm cách trả về các tài liệu có chứa những từ này sẽ thu được kết quả vô ích, không cần thiết. Do đó, chúng ta cần tìm cách loại bỏ các từ này trước khi tìm kiếm. 2.6.2. Tiếng và Từ trong tiếng Việt Về mặt ngữ âm, tiếng là âm tiết. Âm tiết bao gồm những đơn vị ở bậc thấp hơn gọi là âm vị. Mỗi âm vị được ghi bằng một ký tự gọi là chữ. Về mặt ngữ nghĩa, tiếng là đơn vị nhỏ nhất có nghĩa, nhưng cũng có một số tiếng không có nghĩa. Về giá trị ngữ pháp, tiếng là đơn vị cấu tạo từ. Sử dụng tiếng để tạo thành từ, ta có hai trường hợp sau: - Từ một tiếng: gọi là từ đơn. Trường hợp này một từ chỉ có một tiếng. Ví dụ như: ông, bà, cha, mẹ, ... - Từ hai tiếng trở lên: gọi là từ phức. Trường hợp này một từ có thể có hai hay nhiều tiếng trở lên. Ví dụ như: xã hội, an ninh, hợp tác xã, ... Từ là đơn vị nhỏ nhất để tạo thành câu. Trong đặt câu chúng ta dùng từ chứ không dùng tiếng. 2.6.3. Phương pháp tách từ tự động tiếng Việt fnTBL Ý tưởng chính của phương pháp học dựa trên sự biến đổi (TBL) là để giải quyết một vấn đề nào đó ta sẽ áp dụng các phép biến đổi, tại mỗi bước, phép biến đổi nào cho kết quả tốt nhất sẽ được chọn và được áp dụng lại với vấn đề đã đưa ra. Thuật toán kết thúc khi không còn phép biến đổi nào được chọn. Hệ thống fnTBL (Fast Transformation-based learning) gồm hai tập tin chính [1]: - Tập tin dữ liệu học (Training): Tập tin dữ liệu học được làm thủ công, đòi hỏi độ chính xác. Mỗi mẫu (template) được đặt trên một dòng riêng biệt. Ví dụ: tập dữ liệu học cho việc xác định từ loại của một văn bản có thể được định dạng như sau: Công ty danhtu ISA danhturieng bị dongtu Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 40 - kiểm tra. dongtu Trong ví dụ này mỗi mẫu gồm hai phần: phần đầu tiên là từ, phần thứ hai là từ loại tương ứng. - Tập tin chứa các mẫu luật (rule template): Mỗi luật được đặt trên một dòng, hệ thống fnTBL sẽ dựa vào các mẫu luật để áp dụng vào tập dữ liệu học. Ví dụ: chunk_ -2 chunk_-1 => chunk Áp dụng đối với việc xác định từ loại, với chunk_-2 = động từ, chunk_-1 = số từ, chunk = danh từ thì luật trên có ý nghĩa như sau: nếu hai từ trước đó là động từ và số từ thì chuyển từ loại hiện hành thành danh từ. Áp dụng để tách từ Tiếng Việt: Ta có thể áp dụng phương pháp fnTBL để tách từ Tiếng Việt, chỉ cần thay đổi một số định dạng cho phù hợp. - Xây dựng tập tin dữ liệu học: Tập tin dữ liệu cho việc tách từ Tiếng Việt có dạng như sau: Vì B sao B công B ty I ISA B bị B đặt B vào B tình B trạng I ... Các ký tự B, I gọi là các chunk có ý nghĩa như sau: Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 41 - Tiếng có chunk = B nghĩa là tiếng đó bắt đầu một từ (begin) Tiếng có chunk = I nghĩa là tiếng đó nằm trong một từ (inside). - Xây dựng tập tin chứa các mẫu luật: Sau khi tìm hiểu về từ trong Tiếng Việt, ta xây dựng được 3 luật áp dụng cho tách từ tiếng Việt như sau: chunk_0 word_0 => chunk chunk_0 word_-1 word_0 => chunk chunk_0 word_0 word_1 => chunk a, Quá trình học: (1) Từ tập dữ liệu học xây dựng từ điển các từ (2) Khởi tạo các từ (3) Rút ra tập luật Ở bước (1) từ tập dữ liệu học đã có sẵn, sử dụng phương pháp thống kê → ta sẽ có từ điển các tiếng (Lexicon). Các tiếng có thể xuất hiện trong các từ với các chunk khác nhau, ta sẽ ghi nhận lại số lần xuất hiện của mỗi tiếng với các chunk tương ứng. Ví dụ, đối với từ “công ty” thì tiếng “công” có chunk = B nhưng trong từ “của công” thì tiếng công có chunk=I. Ở bước (2) từ tập dữ liệu học, tạo ra tập dữ liệu học không có chunk bằng cách xoá hết các chunk tương ứng. Tập dữ liệu mới này sẽ được sử dụng để khởi tạo lại các chunk thông dụng nhất dựa vào từ điển. Ở bước (3) so sánh tập dữ liệu học với tập dữ liệu đang xét, dựa vào các mẫu luật đã cho, ta sẽ rút ra được các luật ứng viên, ứng với mỗi luật ứng viên ta lại áp dụng vào tập dữ liệu đang xét và tính điểm cho nó (dựa vào số lỗi phát sinh khi so sánh với tập dữ liệu học là tập dữ liệu chuẩn). Chọn luật có điểm cao nhất và lớn hơn một ngưỡng cho trước để đưa vào danh sách luật được chọn. Kết quả ta sẽ được một tập các luật được chọn. Các luật có dạng như sau: SCORE: 414 RULE: chunk_0=B word_0=tế => chunk=I SCORE: 312 RULE: chunk_0=B word_-1=của word_0=công => chunk=I SCORE: 250 RULE: chunk_0=B word_0=hoá => chunk=I Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 42 - SCORE: 231 RULE: chunk_0=B word_0=động => chunk=I SCORE: 205 RULE: chunk_0=B word_0=nghiệp => chunk=I SCORE: 175 RULE: chunk_0=B word_-1=phát word_0=triển => chunk=I SCORE: 133 RULE: chunk_0=B word_-1=xã word_0=hội => chunk=I SCORE: 109 RULE: chunk_0=B word_-1=đầu word_0=tư => chunk=I SCORE: 100 RULE: chunk_0=B word_0 = thể => chunk=I Ở dòng 2 ta có luật: nếu từ hiện hành là “công” (word_0=công) và từ trước đó là “của” (word_-1=của) và chunk của từ hiện hành là B (chunk_0=B) thì chuyển chunk của từ hiện hành là I, nghĩa là “của công” phải là một từ. Toàn bộ quá trình học được mô tả như sau: Hình 4. Quá trình học Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 43 - b, Xác định từ cho tài liệu mới (1) Tài liệu mới đưa vào phải có địng dạng giống như tập tin dữ liệu học, nghĩa là mỗi tiếng trên một dòng. (2) Dựa vào từ điển, gán chunk thông dụng nhất cho các tiếng trong tài liệu mới. (3) Áp dụng các luật có được từ giai đoạn học vào tài liệu đang xét ta sẽ tách được các từ hoàn chỉnh. Giai đoạn xác định từ cho tài liệu mới được mô tả như sau: Hình 5. Giai đoạn xác định từ cho tài liệu mới 2.6.4. Phương pháp Longest Matching Phương pháp Longest Matching tách từ dựa vào từ điển có sẵn [1]. Theo phương pháp này, để tách từ tiếng Việt ta đi từ trái qua phải và chọn từ có nhiều âm tiết nhất mà có mặt trong từ điển, rồi cứ tiếp tục cho từ kế Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 44 - tiếp cho đến hết câu. Với cách này, ta dễ dàng tách được chính xác các ngữ/câu như: “hợp tác|mua bán”, “thành lập|nước|Việt Nam|dân chủ|cộng hoà”... Tuy nhiên, phương pháp này sẽ tách từ sai trong trường hợp như: “học sinh học sinh học” được tách thành “học sinh|học sinh|học”, “một ông quan tài giỏi” được tách thành “một|ông|quan tài|giỏi” , “trước bàn là một ly nước” được tách thành “trước|bàn là|một|ly|nước”,... 2.6.5. Kết hợp giữa fnTBL và Longest Matching Chúng ta có thể kết hợp giữa hai phương pháp fnTBL và Longest Matching để có được kết quả tách từ tốt nhất. Đầu tiên ta sẽ tách từ bằng Longest Matching, đầu ra của phương pháp này sẽ là đầu vào của phương pháp fnTBL học luật. 2.7. Kết luận chương 2 Trong chương này, các nội dung liên quan tới phân cụm tài liệu Web đã được trình bày một cách khái quát nhất giúp có một cái nhìn tổng quan để bắt tay vào thực hiện giải quyết bài toán. Đồng thời hướng giải quyết khó khăn khi phân cụm tài liệu Web tiếng Việt cũng đã được trình bày. Trên cơ sở đó, luận văn nghiên cứu tập trung vào các thuật toán phân cụm Web có tính tăng điển hình. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 45 - CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT TOÁN CÂY PHÂN CỤM TÀI LIỆU 3.1. Giới thiệu về thuật toán phân cụm trang Web có tính tăng Chúng ta đang quan tâm giải quyết bài toán phân cụm tài liệu cho các trang Web. Theo truyền thống, nhiệm vụ phân lớp tài liệu được tiến hành thủ công. Để gán một tài liệu với một lớp thích hợp, người thực hiện đầu tiên sẽ phân tích các nội dung của tài liệu. Bởi vậy một số lượng lớn nỗ lực của con người sẽ bị yêu cầu. Đã có một vài công việc nghiên cứu hướng dẫn việc phân cụm tự động văn bản text. Một hướng đi là phân lớp văn bản text bằng cách sử dụng các kỹ thuật học máy. Tuy nhiên, các thuật toán này dựa trên một bộ ví dụ huấn luyện đúng và sai cho học các lớp văn bản. Chất lượng của kết quả các lớp muốn cao thì phải phụ thuộc vào các ví dụ huấn luyện phù hợp. Có rất nhiều thuật ngữ và các lớp trên World Wide Web (hoặc chỉ là Web), và rất nhiều thuật ngữ và khái niệm được tạo ra hằng ngày. Thật là không thể để có các chuyên gia trong lĩnh vực này để định nghĩa các ví dụ huấn luyện để học một người phân loại cho từng lớp theo cách như trên. Để tiến hành xử lý phân lớp tài liệu tự động, các kỹ thuật phân cụm đã được sử dụng. Sự thu hút của phân tích phân cụm là ở việc nó có thể tìm thấy các cụm trực tiếp từ dữ liệu đưa vào mà không cần nhờ vào bất cứ thông tin nào đã được xác định trước, chẳng hạn như các ví dụ huấn luyện cung cấp bởi các chuyên gia trong lĩnh vực. Trong chương này, luận văn xin trình bày một số các thuật toán phân cụm thích hợp cho việc phân cụm trang Web bởi các đặc tính tăng của chúng, cụ thể đó là thuật toán phân cụm cây hậu tố (STC) và thuật toán sử dụng cây phân cụm tài liệu (DC-Tree). Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 46 - 3.2. Thuật toán phân cụm cây hậu tố 3.2.1. Mô tả Cây hậu tố (hay còn gọi là cây PAT hoặc gần đây có thể được gọi là cây vị trí) là một cấu trúc dữ liệu biểu diễn các hậu tố của xâu ký tự nhất định cho phép thực hiện một cách đặc biệt nhanh chóng nhất nhiều phép toán quan trọng trên xâu. Cây hậu tố cho một xâu ký tự S là một cây có cạnh và nhãn là các xâu, thí dụ hậu tố eAHC của S phù hợp chỉ có một con đường từ gốc của cây tới một lá. Do đó chỉ có một cây cơ số cho các hậu tố của S. Việc xây dựng một cây cho xâu ký tự S mất thời gian và không gian tuyến tính với độ dài của S. Mỗi một lần xây dựng, một vài thao tác có thể được thực hiện nhanh chóng, ví dụ như việc xác định vị trí một xâu con trong S, xác định vị trí của một xâu con nếu cho phép một số chắc chắn các lỗi, xác định vị trí các xâu tương ứng cho một mẫu công thức thông thường,... Các cây hậu tố cũng cung cấp một trong các giải pháp có thời gian tuyến tính cho vấn đề tìm xâu con thông thường. Tuy nhiên việc tăng tốc độ sẽ dẫn tới tăng chi phí không gian bộ nhớ do phải lưu trữ thêm cây hậu tố của một xâu hơn so việc lưu trữ xâu đó. Hình 6. Cây hậu tố cho xâu BANANA Cây hậu tố cho xâu BANANA được thêm $ vào cuối. Có sáu con đường từ gốc tới một lá (được chỉ ở trên như các hộp) tương ứng với 6 hậu tố A$, NA$, Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 47 - ANA$, NANA$, ANANA$ và BANANA$. Các chữ số trong các hộp chỉ ra vị trí bắt đầu của hậu tố tương ứng. Hậu tố được liên kết bởi mũi tên kéo theo 3.2.2. Thuật toán STC Thuật toán phân cụm cây hậu tố Suffix Tree Clustering (STC) [5] là một thuật toán phân cụm thời gian tuyến tính dựa trên việc nhận dạng các cụm từ chung của các văn bản. Một cụm từ trong ngữ cảnh này là một chuỗi thứ tự của một hoặc nhiều từ. Chúng ta định nghĩa một cụm cơ bản (base cluster) là một tập các văn bản có chia sẻ một cụm từ chung. STC có 3 bước thực hiện logic: (1) “Làm sạch” văn bản, (2) định nghĩa các cụm cơ bản sử dụng một cây hậu tố, và (3) kết hợp các cụm cơ bản vào các cụm. Bước 1: Tiền xử lý (Pro-Precessing). Trong bước này, các chuỗi của đoạn văn bản biểu diễn mỗi tài liệu được chuyển đổi sử dụng các thuật toán chặt (Chẳng hạn như loại bỏ đi các tiền tố, hậu tố, chuyển từ số nhiều thành số ít). Phân ra thành từng câu (xác định các dấu chấm câu, các thẻ HTML). Bỏ qua các từ tố không phải là từ (chẳng hạn như kiểu số, các thẻ HTML và các dấu câu). Các chuỗi tài liệu nguyên gốc được giữ lại, cùng với các con trỏ tại vị trí bắt đầu của mỗi từ trong chuỗi chuyển đổi đến vị trí của nó trong chuỗi gốc. Việc có các con trỏ nhằm giúp hiển thị được đoạn văn bản gốc từ các nhóm từ khóa đã chuyển đổi. Bước 2: Xác định các cụm cơ sở. Việc xác định các cụm cơ sở có thể được xem xét như việc tạo một chỉ số của các nhóm từ cho tập tài liệu. Điều này được thực hiện hiệu quả thông qua việc sử dụng cấu trúc dữ liệu gọi là cây hậu tố. Cấu trúc dữ liệu này có thể được xây dựng trong thời gian tuyến tính với kích cỡ của tập tài liệu, và có thể được xây dựng tăng thêm cho các tài liệu đang được đọc vào. Một cây hậu tố của một chuỗi S là một cây thu gọn chứa đựng tất cả các hậu tố của S. Thuật toán coi các tài liệu như các chuỗi của các từ, không phải của các ký tự vì vậy các hậu tố chứa đựng một hoặc nhiều từ. Mô tả cụ thể về cây hậu tố như sau: 1. Một cây hậu tố là cây có gốc và được định hướng. 2. Mỗi node trong có tối thiểu 2 con. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 48 - 3. Mỗi cạnh được gắn nhãn là một chuỗi con của S và chuỗi đó khác rỗng. Nhãn của một node được xác định thông qua chuỗi nối tiếp của các nhãn được gắn cho các cạnh từ gốc tới node đó. 4. Không có hai cạnh từ một node được gắn nhãn bắt đầu với từ giống nhau. 5. Với mỗi hậu tố s của S, tồn tại một suffix-node có nhãn là s. Cây hậu tố của một tập các chuỗi là một cây thu gọn chứa đựng tất cả các hậu tố của tất cả các chuỗi trong tập tài liệu. Mỗi suffix-node được đánh dấu để chỉ ra chuỗi mà nó thuộc về. Nhãn của suffix-node chính là một hậu tố của chuỗi đó. Để phân cụm ta sẽ xây dựng cây hậu tố của tất cả các câu của tất cả các tài liệu trong tập tài liệu. Chẳng hạn có thể xây dựng cây hậu tố cho tập các chuỗi là {“cat ate cheese”, “mouse ate cheese too”, “cat ate mouse too”}. - Các node của cây hậu tố được vẽ bằng hình tròn - Mỗi suffix-node có một hoặc nhiều hộp gắn vào nó để chỉ ra chuỗi mà nó thuộc về. - Mỗi hộp có 2 số (số thứ nhất chỉ ra chuỗi mà hậu tố thuộc về, số thứ hai chỉ ra hậu tố nào của chuỗi gắn nhãn cho suffix-node) Hình 7: Cây hậu tố của các chuỗi “cat ate cheese”, “mouse ate cheese too”, “cat ate mouse too”. Một số node đặc biệt a → f. Mỗi một node này biểu diễn cho một nhóm tài liệu và một nhóm từ chung được thiết đặt cho tất cả tài liệu. Nhãn của node biểu diễn nhóm từ chung. Tập các tài liệu gắn nhãn suffix-node là kế thừa của các node tạo bởi nhóm tài liệu. Do đó, mỗi node biểu diễn một cụm cơ sở (base Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 49 - cluster). Ngoài ra, tất cả các cụm cơ sở có thể (chứa 2 hoặc nhiều tài liệu) xuất hiện như các node trong cây hậu tố. Bảng sau liệt kê các node a-> f trong hình 1 và các cụm cơ sở tương ứng. Bảng 1: Sáu node từ hình 14 và các cụm cơ sở tương ứng. Node Phrase Documents a cat ate 1,3 b ate 1,2,3 c cheese 1,2 d mouse 2,3 e too 2,3 f ate cheese 1,2 Mỗi cụm cơ sở được gán một điểm số là một hàm của số lượng các tài liệu cụm đó chứa đựng, và các từ hình thành nên nhóm từ của nó. Điểm số s(B) của cụm cơ sở B với nhóm từ P là: s(B) = |B| . f(|P|) (*) Trong đó: |B| là số lượng của các tài liệu trong cụm cơ sở B, |P| là số lượng các từ có trong nhóm từ P mà có điểm số khác 0. Việc xét đến điểm số của nhóm từ P theo nghĩa như sau: Thuật toán cài đặt một danh sách stoplist bao gồm các từ đặc trưng trên internet dùng để xác định các từ khác. ( Ví dụ “previous”, “java”, “frames”, “mail”). Các từ xuất hiện trong danh sách stoplist đó hay các từ xuất hiện quá ít trong một nhóm từ (3 hoặc ít hơn) hay quá nhiều (hơn 40% của tập tài liệu) sẽ được gán điểm số 0 cho nhóm từ. Hàm f trong công thức (*) thực hiện trên các nhóm từ đơn, nó là tuyến tính cho các nhóm từ có độ dài từ 2 đến 6 và là hằng số với các nhóm có độ dài lớn hơn. Bước 3: Kết nối các cụm cơ sở Các tài liệu có thể chia sẻ nhiều hơn một nhóm từ. Kết quả là, tập hợp tài liệu của các cụm cơ sở khác nhau có thể trùng lặp và thậm chí là có thể là giống nhau. Để tránh việc có nhiều các cụm gần giống nhau. Tại bước thứ 3 này của thuật toán việc trộn các cụm cơ sở với một sự trùng lặp cao trong tập tài liệu của chúng (chú ý là các nhóm từ chung không xem xét trong bước này) Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 50 - Thuật toán đưa ra một độ đo tính tương tự giữa các cụm dựa trên việc trùng lặp của tập tài liệu của chúng. Giả sử có hai cụm cơ sở Bm và Bn với kích cỡ là |Bm| và |Bn| tương ứng. Và | Bm ∩ Bn| thể hiện số tài liệu chung của cả hai cụm, độ tương tự giữa Bm và Bn là 1 nếu: +) | Bm ∩ Bn| / |Bm| > 0.5 và +) | Bm ∩ Bn| / |Bn| > 0.5 Ngược lại, độ tương tự là 0. Hãy xem minh họa tiếp theo của ví dụ trong Hình 7. Ở đây mỗi node là các cụm cơ sở. Hai node được nối với nhau khi độ tương tự là 1. Một cụm được xác định là các thành phần được ghép nối trong đồ thị cụm cơ sở. Mỗi một cụm sẽ bao gồm tập của tất cả các tài liệu của các cụm cơ sở trong nó. Hình 7: Đồ thị các cụm cơ sở của ví dụ trong Hình 6 và bảng 1. Trong ví dụ này có một thành phần kết nối, do đó có 1 cụm. Nếu giả sử rằng từ ‘ate’ có trong danh sách stoplist, thì cụm cơ sở b sẻ bị loại ra bởi vì nó có chỉ số của nhóm từ là 0. Và do đó sẽ có 3 thành phần kết nối trong đồ thị, thể hiện 3 cụm. Chúng ta thấy rằng thời gian của việc tiền xử lý các tài liệu tại bước 1 của thuật toán STC hiển nhiên là tuyến tính với kích thước tập tài liệu. Thời gian của việc thêm các tài liệu vào cây hậu tố cũng tuyến tính với kích thước tập tài liệu theo thuật toán Ukkonen cũng như số lượng các node có thể bị ảnh hưởng bởi việc chèn này. Do vậy thời gian tổng cộng của STC tuyến tính với kích thước tập tài liệu. Hay thời gian thực hiện của thuật toán STC là O(n) trong đó n là kích thước của tập tài liệu. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 51 - 3.3. Thuật toán phân cụm sử dụng cây phân cụm tài liệu 3.3.1. Giới thiệu Trong thuật toán phân cụm sử dụng cây phân cụm tài liệu, một tài liệu thông thường được biểu diễn bởi một vector đặc trưng. Một cách đặc tính, từng đặc trưng tương ứng với một từ khoá hoặc cụm từ xuất hiện trong tập tài liệu. Mỗi entry của vector lưu một trọng số cho đặc trưng tương ứng của tài liệu. Sau khi trích chọn các vector đặc trưng của các tài liệu, chúng ta có thể áp dụng thuật toán phân cụm trên tập các vector như trong phân cụm dữ liệu kích thước lớn thông thường. Các lớp tài liệu kết quả thu được cũng với các đặc trưng tiêu biểu (ví dụ các từ khoá hoặc cụm từ khóa với đủ hỗ trợ tài liệu (document support) cho cụm) do đó trình bày cho người sử dụng. Trong luận văn này, tôi xin giới thiệu một cấu trúc cây gọi là DC-tree (Document Clustering Tree: Cây phân cụm tài liệu) có thể phân cụm các tài liệu mà không cần tập huấn luyện [24]. Với DC-tree, một đối tượng dữ liệu đưa vào không bắt buộc phải chèn vào mức (vị trí) thấp khi không tồn tạo một nút con tương tự cho đối tượng dữ liệu. Điều này ngăn cản một vài dữ liệu không tương tự từ việc đặt cùng nhau. Kết quả là thuật toán phân cụm dựa trên cấu trúc DC- tree là ổn định với yêu cầu đưa thêm tài liệu và dễ chấp nhận các tài liệu “nhiễu”. Phương thức này có thể hữu ích trong một số cách: (1) Cho việc tiền xử lý trong việc phân lớp trang Web để người sử dụng có thể chọn lớp thích hợp trước khi tìm kiếm, việc này giúp ích việc tìm kiếm trở nên có trọng tâm hơn và hiệu quả hơn. (2) Cho việc phân lớp trực tuyến online, để khi số lượng lớn các kết qủa trả lại từ một tìm kiếm, Kỹ thuật này có thể phân lớp các kết quả và cung cấp tốt hơn hướng dẫn cho người sử dụng trong các tìm kiếm trong tương lai. (3) Cho việc phân lớp trang Web có tính tăng sau khi cập nhật trên kho dữ liệu. 3.3.2. Trích chọn đặc trưng và phân cụm tài liệu Nhiệm vụ đầu tiên là nhận biết một phương pháp trích chọn đặc trưng tốt thích hợp cho môi trường Web. Trong phần này, luận văn trình bày một phương Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 52 - pháp trích chọn đặc trưng. Ngoài ra, tài liệu và sự biểu diễn phân cụm tài liệu cũng sẽ được mô tả. Cuối cùng, phương pháp ước lượng chất lượng phân cụm cũng sẽ được trình bày. a, Trích chọn đặc trưng tài liệu Phương pháp trích chọn đặc trưng cho thuật toán phân cụm tài liệu Web được đưa ra không phụ thuộc vào tần xuất xuất hiện từ. Phương pháp này cân bằng các yếu tố khác nhau để đạt được sự kết hợp tốt nhất giữa độ hồi tưởng và số các đặc trưng sử dụng cho biểu diễn tài liệu. Trong vấn đề của chúng ta phạm vi phân cụm mục tiêu để giúp đỡ trong việc lấy thông tin trong việc tìm kiếm bằng cách thu hẹp phạm vi tìm kiếm. Trong một viễn cảnh, người sư dụng có thể không muốn quá nhiều phân cụm trong kết quả. Đồng thời, các cụm quá lớn hoặc quá nhỏ là không được mong muốn. Các cụm quá lớn không thể giúp thu hẹp phạm vi tìm kiếm. Các cụm qúa nhỏ có thể làm tăng tổng số các cụm,và nó có thể thậm chí gây nên trạng thái “nhiễu”. Tham số k được sử dụng để thiết lập một số xấp xỉ trên cỡ của cụm. Do đó số các phân cụm là xấp xỉ N/k, trong đó N là tổng số các tài liệu. Phương pháp được đề xuất bao gồm các bước sau: 1. Lấy ngẫu nhiên một tập con của các tài liệu với cỡ m từ tập sao lục. 2. Trích tập các từ có xuất hiện ít nhất một lần trong các tài liệu. Xoá các từ kết thúc và kết nối các từ vào cùng một gốc bằng cách sử dụng kỹ thuật lấp đầy. 3. Đếm tần xuất tài liệu của các từ đã được trích trong bước 2. 4. Đặt lower=k và upper=k 5. Lấy tất cả các từ với tần xuất tài liệu trong giá trị từ lower và upper. 6. Kiểm tra nếu coverage ( độ hồi tưởng) của các từ là lớn hơn ngưỡng định nghĩa trước. Nếu vậy, dừng. Nếu không, đặt lower=lower-1 và upper=upper+1, và quay lại bước 5. Để trích chọn các đặc trưng tiêu biểu từ các tài liệu, chúng ta lựa chọn ngẫu nhiên một tập các tài liệu mẫu cho bước trích chọn đặc trưng trong bước 1. Một vài thử nghiệm [24] chỉ ra rằng phương pháp trích chọn đặc trưng này có thể trích ra một tập các đặc trưng tốt cho phân cụm tài liệu Web. Một danh sách các Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 53 - từ kết thúc thường được sử dụng để xoá các từ ít có ý nghĩa. Kỹ thuật lấp đầy thường được sử dụng để kết nối các từ này trong dạng tương tự. Bởi vì các vector đặc trưng ngắn nhất dẫn tới thời gian phân cụm ngắn hơn, bước 4 và 6 cố gắng để làm nhỏ nhất số các đặc trưng và thu được độ hồi tưởng hợp lý cho các đặc trưng. Thừa nhận người sử dụng muốn cụm kết quả bao gồm khoảng k tài liệu.Trong trường hợp lý tưởng, một đặc trưng cho một cụm sẽ xuất hiện chỉ trong cụm và do đó tần xuất tài liệu của của đặc trưng là k. Bởi vậy, đầu tiên chúng ta chọn các đặc trưng với tần xuất tài liệu là bằng k, bằng cách thiết lập lower và upper bằng k trong bước 4. Khoảng giá trị {lower, upper} là tăng lên một cách lặp lại trong bước 6 để bảo đảm đủ bảo phủ cho tập đặc trưng kết quả. Chúng ta thấy rằng N/k chỉ là một hướng dẫn phỏng đoán, số lượng thực tế các phân cụm của kết quả phân cụm có thể không giống như N/k. Phương pháp cũng sử dụng một ngưỡng hồi tưởng để đảm bảo rằng các đặc trưng được chọn có đủ độ hồi tưởng. Với các thử nghiệm ([24]), chúng ta thấy rằng 0.8 là giá trị ngưỡng hồi tưởng khá tốt. b, Biểu diễn tài liệu Trong thuật toán của chúng ta, một tài liệu (Di) được biểu diễn theo dạng sau: Di=(Wi,IDi), trong đó IDi là sự nhận dạng tài liệu có thể được sử dụng để lấy tài liệu (Di), và Wi là vector đặc trưng của tài liệu: Wi=(wi1,wi2,...,win). Do đó n là số các đặc trưng đã được trích chọn, và wij là trọng số của đặc trưng thứ j, trong đó j Є {1,2,..,n}. Trong thuật toán của chúng ta, sự sắp xếp trọng số nhị phân được sử dụng. Đó là, wij =1 nếu Di bao gồm đặc trưng thứ j, ngược lại, wij =0. Như đã đề cập tại phần trích chọn đặc trưng phía trên, một trang Web điển hình không bao gồm nhiều từ mà tần xuất xuất hiện của một từ không biểu thị sự quan trọng trong thực tế của từ này. Bởi vậy, lược đồ trọng số nhị phân là thích hợp nhất cho phạm vi vấn đề của chúng ta. c, Phân cụm tài liệu (DC) Một giá trị phân cụm tài liệu (DC- Document Cluster) là một bộ ba thông tin mà chúng ta duy trì bởi một tập các tài liệu trong cùng một cụm: (1) số các tài liệu (2) tập các nhận dạng tài liệu Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 54 - (3) vector đặc trưng của phân cụm Định nghĩa1: (DC) Cho N tài liệu trong một phân cụm: {D1,D2,...DN}, giá trị DC của một nút được định nghĩa như một bộ ba: DC = (N,ID,W), trong đó N là số lượng các tài liệu trong cụm, ID là tập các nhận dạng tài liệu của các tài liệu trong cụm, ví dụ ID={ID1,ID2,...IDN}, và W là vector đặc trưng của cụm tài liệu, ví dụ W=(w1,w2,...,wn), trong đó wj=∑ = N i ijw 1 , và n là số các đặc trưng đã được trích chọn. Bộ ba này không chỉ ra tổng hợp tần suất tài liệu trong cụm, nhưng có thể sử dụng để đánh giá sự giống nhau giữa hai cụm. Bổ đề sau cung cấp một cách linh hoạt kết nối hai cụm thành một và cho ra giá trị DC cho cụm kết hợp. Bổ đề [24] (Phép cộng) Cho DC1 = (N1,ID1,W1) and DC2= (N2,ID2,W2) là bộ giá trị DC của hai cụm tài liệu tách rời, trong đó tách rời có nghĩa là một tài liệu không thuộc về nhiều hơn một cụm tại cùng một thời điểm. Khi đó bộ giá trị DC mới, DCnew, của cụm được hình thành bằng cách kết hợp hai cụm tách biệt là: DCnew = (N1+N2, ID1 ∪ ID1, W1+W2), trong đó W1+W2= (w11+w21,w12+w22,...,w1n+w2n), và n là số các đặc trưng đã được trích chọn. d, Các kỹ thuật đánh giá Để đánh giá chất lượng của kết quả việc phân cụm, chúng ta chọn kỹ thuật đánh giá F-Measure (độ đo lường F) [23]. Chi tiết của phương pháp đánh giá được mô tả như sau: Cho từng topic được gán nhãn bằng tay T trong tập tài liệu, giả sử rằng một phân cụm X tương ứng với topic đó được hình thành. N1= số các tài liệu của topic T trong phân cụm X N2=số các tài liệu trong phân cụm X N3= tổng số các tài liệu của topic T P=Precision(X,T)=N1/N2 R=Recall(X,T)=N1/N3 F-measure cho topic T được địng nghĩa như sau: Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 55 - F(T)= RP PR + 2 Với đánh giá cao với một topic T, chúng ta quan tâm phân cụm với độ đo F-measure cao nhất để phân cụm C cho T, và độ đo F-measure đó trở thành điểm số cho topic T. Độ đo overall F-measure[22] cho cây kết quả phân cụm là giá trị trung bình của F-measure cho từng topic T: Overall_F_Measure= ∑ ∑ ∈ ∈ × MT MT T TFT ))(( trong đó M là tập các topic, |T| là số các tài liệu của topic T, và F(T) là F-Measure cho topic T. 3.3.3. Cây phân cụm tài liệu –DC Tree Trong phần này xin giới thiệu một thuật toán phân cụm tài liệu Web bằng phương tiện là cây phân cụm tài liệu (Document Cluster -DC-tree). Trong DC- tree, mỗi nút có thể được quan tâm như một phân cụm tài liệu. Cấu trúc cây được sử dụng để hướng dẫn cách đưa đối tượng tài liệu vào một phân cụm tài liệu (DC) thích hợp tại các nút lá. Nó là tương tự với B+-tree [2] trong đó các bản ghi chỉ số tại các nút lá bao gồm các con trỏ trỏ tới các đối tượng dữ liệu, nhưng nó không là cây có chiều cao cân bằng. Cấu trúc này được thiết kế bởi vì việc gán một tài liệu vào một phân cụm chỉ yêu cầu duyệt qua một số lượng nhỏ các nút. Một DC-tree là một cây với 4 tham số: hệ số nhánh (B), hai ngưỡng tương tự (S1 và S2, trong đó 0 ≤ S1 , S2 ≤ 1) và số nhỏ nhất con của một nút (M). Một nút không phải là lá của toàn bộ các chỉ mục của B có dạng (DCi, Childi), trong đó i=1, 2,..., B, “Childi” là một con trỏ tới nút con thứ i hoặc một tài liệu, và DCi là giá trị DC của phân cụm con tiêu biểu cho nút con thứ i hoặc một tài liệu của nó. Vì thế, một nút không phải là lá mô tả một cụm cấu tạo nên tất cả các cụm con được mô tả bởi chỉ mục của nó. Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. - 56 - Một nút lá DC của toàn bộ chỉ mục B là một chỉ mục có dạng (DCi, Doci), trong đó i Є {1, 2, ..., B}, “Doci” là một con trỏ tới một tài liệu hoặc một tập tài liệu, và DCi là chỉ mục DC của cụm con tương ứng. Gọi tập tài liệu dưới một con trỏ là một nút lá tài liệu ( document leaf node), để phân biệt với nó trong nút lá cây (tree leaf node) hoặc DC leaf node (xem hình 8). Một nút lá DC cũng mô tả một cụm cấu tạo nên tất cả các cụm con được mô tả bởi các chỉ mục DC của nó. Cây DC cho phép một chỉ mục đưa tài liệu vào, để chèn vào một nút lá tài liệu mới tại các mức khác nhau của cây. Vì thế, Cây DC không phải là một cây có chiều cao cân bằng. Hình 8 biểu diễn một ví dụ cây DC với chiều cao là 2, B=3, M=2. Chú ý rằng cây là không cân bằng. Trong việc xây dựng cây, hai ngưỡng được sử dụng: Hình 8. Ví dụ của một cây DC Ngưỡng S1: Để ngăn chặn kết quả phân cụm tài liệu kém chất lượng (ví dụ: Các tài liệu trong các lớp khác nhau được đưa vào cùng 1 cây con hoặc phân cụm) được gây ra bởi thứ tự chèn tài liệu, S1 được sử dụng để quyết định tài liệu đến E có thể được chuyển tới cấp độ tiếp theo hay không trong quá trình chèn tài liệu. Nếu tồn tại một tài liệu con của nút hiện tại mà độ tương tự giữa tài liệu này và tài liệu sắp được đưa vào lớn hơn S1, tài liệu mới sẽ được chuyển đến nút con tương ứng. Ngược lại, tài liệu mới sẽ được thêm vào