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.
- 23 - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB 2. 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. 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]. - 24 - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. 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ư 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 - 25 - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
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”.
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.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 - 26 - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. 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.
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. 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: - 27 - LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
E j = − ∑ pij log( pij ) , trong đó việc tính tổng được thực hiện với tất cả các i 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 m ⎛Nj ⎞ phân cụm: E P = ∑ ⎜⎜ × E j ⎟⎟ , trong đó Nj là kích cỡ của phân cụm j và N là j =1 ⎝ N ⎠ 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à: N ij P = precision(i, j ) = Ni N ij R = recall (i, j ) = Nj 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.