Khám Phá Dữ Liệu Web: Phương Pháp Tìm Kiếm Hiệu Quả

Khám phá dữ liệu (Data Mining) được định nghĩa là quá trình 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 "Khám phá dữ liệu" với khái niệm "Phát hiện tri thức" (KDD), trong đó, khám 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, Tích hợp dữ liệu, Lựa chọn dữ liệu, Chuyển đổi dữ liệu, Khai phá dữ liệu, Ước lượng mẫu, Biểu diễn tri thức.

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), Luật kết hợp (association rules), Phân lớp và dự đoán (classification & prediction), Phân cụm (clustering), Khai phá chuỗi (sequential/temporal patterns). Các hướng tiếp cận này thường sử dụng các kỹ thuật của machine learning như cây quyết định. Phân lớp còn được gọi là học có giám sát (học có thầy), trong khi phân cụm là học không giám sát (học không thầy).

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

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. Khai phá nội dung trang Web (Web content mining) gồm hai phần: Web Page Content và Search Result. 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. Web Usage Mining: 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.

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 hay các hoạt động liên quan tới World-Wide Web. 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.

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.

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 (offline). 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 (online) 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.

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.

Thuật toán phân cụm cây hậu tố (Suffix Tree Clustering - STC) là một phương pháp phân cụm văn bản sử dụng cấu trúc cây hậu tố để biểu diễn dữ liệu. Cây hậu tố cho phép tìm kiếm nhanh chóng các cụm từ chung giữa các tài liệu, từ đó xác định các cụm tài liệu có liên quan.

Thuật toán cây phân cụm tài liệu (Document Clustering Tree - DT-Tree) xây dựng một cây phân cấp để tổ chức các tài liệu. Mỗi nút trên cây đại diện cho một cụm tài liệu, và các nút con đại diện cho các cụm con. Thuật toán này cho phép phân cụm tài liệu một cách hiệu quả và có thể được sử dụng để duyệt và tìm kiếm tài liệu.

Phần mềm thử nghiệm được xây dựng với cơ sở dữ liệu được thiết kế để lưu trữ thông tin về các trang web, bao gồm nội dung, liên kết và các thuộc tính khác. Cơ sở dữ liệu này đóng vai trò quan trọng trong việc hỗ trợ các thuật toán phân cụm và đánh giá kết quả.

Phần mềm cung cấp giao diện người dùng thân thiện, cho phép người dùng thực hiện các thao tác như tải trang web, phân cụm dữ liệu và xem kết quả. Các chức năng chính bao gồm cập nhật từ điển, lấy dữ liệu từ Internet và phân cụm dữ liệu đã lấy về.

Phần mềm đã 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. Các thử nghiệm ban đầu cho thấy tiềm năng của các thuật toán phân cụm trong việc tổ chức và tìm kiếm thông tin trên web tiếng Việt.

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

Các hướng nghiên cứu tiếp theo có thể tập trung vào việc cải thiện hiệu suất của các thuật toán phân cụm, đánh giá kết quả phân cụm một cách chính xác hơn và áp dụng các thuật toán này vào các ứng dụng thực tế. Ngoài ra, việc nghiên cứu các phương pháp kết hợp các thuật toán phân cụm khác nhau cũng là một hướng đi tiềm năng.