I. Tổng Quan Về Khám Phá Dữ Liệu Web Giới Thiệu Chung
Khám phá dữ liệu web (Web Data Mining) là quá trình khám phá tri thức từ lượng lớn dữ liệu web. Nó bao gồm việc trích xuất thông tin hữu ích và các mẫu từ các tài nguyên web. Khái niệm này khác với "Phát hiện tri thức" (KDD), trong đó khám phá dữ liệu chỉ là một bước. Quá trình KDD bao gồm làm sạch dữ liệu, tích hợp, lựa chọn, chuyển đổi, khai phá, đánh giá mẫu và biểu diễn tri thức. Các hướng tiếp cận chính bao gồm mô tả khái niệm, luật kết hợp, phân lớp, phân cụm và khai phá chuỗi. Ứng dụng của khám phá dữ liệu rất đa dạng, từ phân tích dữ liệu và hỗ trợ ra quyết định đến y học, khai thác văn bản, tin-sinh học, tài chính và bảo hiểm. Sự phát triển của Internet đã tạo ra nhu cầu lớn về khám phá thông tin từ dữ liệu web.
1.1. Định Nghĩa và Các Bước Trong Khám Phá Dữ Liệu
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.
1.2. Các Hướng Tiếp Cận và Kỹ Thuật 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), 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).
II. Thách Thức Khám Phá Dữ Liệu Web Vấn Đề và Giải Pháp
Dữ liệu web có nhiều đặc điểm phức tạp gây khó khăn cho việc khám phá. Web quá lớn để tổ chức thành một kho dữ liệu phục vụ khai phá. Độ phức tạp của trang web lớn hơn nhiều so với tài liệu truyền thống. Web là nguồn tài nguyên thông tin có độ thay đổi cao. Nó 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 nhỏ thông tin trên web thực sự hữu ích. Các thách thức này đòi hỏi các phương pháp và công cụ khai phá dữ liệu web phải linh hoạt và hiệu quả.
2.1. Đặc Điểm Của Dữ Liệu Web Gây Khó Khăn Cho Khai Phá
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.
2.2. Các Hướng Tiếp Cận Khai Phá Dữ Liệu Web Phổ Biến
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.
2.3. Ứng Dụng Phân Lớp và Tìm Kiếm 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.
III. Phương Pháp Phân Cụm Web Giải Pháp Tìm Kiếm Tối Ưu
Phân cụm web là một bài toán quan trọng trong khai phá web. Nó tự động sinh ra các "cụm" tài liệu dựa trên sự tương tự. Các lớp tài liệu ở đây là chưa biết trước. Người dùng có thể yêu cầu số lượng 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: phân cụm trên toàn bộ CSDL có sẵn và phân cụm trên tập tài liệu nhỏ do máy tìm kiếm trả về. Với 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.
3.1. Tổng Quan Về Bài Toán Phân Cụm 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.
3.2. Phân Loại Phân Cụm Tài Liệu Trực Tuyến và Ngoại Tuyến
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.
3.3. Yêu Cầu Về Tính Gia Tăng Của Thuật Toán Phân Cụm
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.
IV. Thuật Toán Phân Cụm Cây Hậu Tố Giải Pháp Tối Ưu
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 DT (DT-tree). Thuật toán STC (Suffix Tree Clustering) sử dụng cây hậu tố để biểu diễn dữ liệu văn bản và thực hiện phân cụm dựa trên cấu trúc cây này. Thuật toán DT-tree (Document Clustering Tree) xây dựng một cây phân cụm tài liệu để tổ chức và phân loại các tài liệu web. Cả hai thuật toán đều có khả năng xử lý dữ liệu một cách gia tăng, phù hợp với yêu cầu của việc phân cụm trực tuyến trên web.
4.1. Giới Thiệu Về Thuật Toán Phân Cụm Trang Web Có Tính Tăng
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.
4.2. Thuật Toán Phân Cụm Cây Hậu Tố STC
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.
4.3. Thuật Toán Cây Phân Cụm Tài Liệu DT Tree
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.
V. Ứng Dụng Thực Tiễn Phần Mềm Thử Nghiệm và Kết Quả
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. 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.
5.1. Thiết Kế Cơ Sở Dữ Liệu Cho Phần Mềm Thử Nghiệm
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ả.
5.2. Giao Diện Người Dùng và Chức Năng Của Phần Mềm
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ề.
5.3. Kết Quả Thử Nghiệm Phân Cụm Web Tiếng Việt
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.
VI. Kết Luận và Hướng Phát Triển Khám Phá Dữ Liệu Web
Luận văn đã đạt được 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. 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ế.
6.1. Tổng Kết Các Kết Quả Đạt Được Trong Luận Văn
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.
6.2. Hướng Nghiên Cứu Tiếp Theo Về Phân Cụm Web
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.
