Luận Văn Áp dụng kỹ thuật phân cụm dữ liệu trong phân cụm kết quả tìm kiếm

Áp dụng kỹ thuật phân cụm dữ liệu trong phân cụm kết quả tìm kiếm
Abstract
Phần này chúng tôi giới thiệu hướng tiếp cận trong việc sử dụng kỹ thuật phân cụm dữ liệu vào tìm kiếm và phân lại tài liệu Web, như xây dựng mô hình tìm kiếm, tiền xử lý, biểu diễn văn bản bằng mô hình vector và phân cụm tài liệu Web bằng thuật toán k-means.
I. Giới thiệu
Với sự gia tăng nhanh chóng số lượng trang và nội dung trên Web, sự cải tiến không ngừng của các Search engine cả về chức năng tìm kiếm và giao diện người dùng đã giúp cho người sử dụng dễ dàng hơn trong việc tìm kiếm thông tin từ nguồn dữ liệu Web. Mặc dù các search engine đã tạo danh sách theo thứ tự quan trọng của nó, nhưng người sử dụng thường vẫn phải duyệt qua hàng chục thậm chí hàng ngàn các trang Web để tìm kiếm thứ họ cần. Theo tâm lý người dùng, họ chỉ xem quan vài chục kết quả đầu tiên, thiếu kiên nhẫn và không đủ thời gian để xem duyệt qua tất cả kết quả đó. Nhằm giải quyết vấn đề này, ta có thể nhóm các trang Web này thành các nhóm theo các chủ đề, khi đó người sử dụng có thể bỏ qua các nhóm mà họ không quan tâm để tìm đến nhóm chủ đề quan tâm. Điều này sẽ giúp cho người dùng thực hiện truy vấn của họ một cách hiệu quả hơn. Tuy nhiên vấn đề phân cụm trang Web và chọn chủ đề thích hợp để nó có thể mô tả được nội dung của các trang là một vấn đề không đơn giản. Trong phần này, ta sẽ xem lại khía cạnh sử dụng kỹ thuật phân cụm để phân cụm tại liệu Web dựa trên kho dữ liệu đã được tìm kiếm và lưu trữ.
2. Hướng tiếp cận
Có nhiều phương pháp tìm kiếm khác nhau và nhiều cách xác định trọng số trang (chỉ số quan trọng của trang trong tập kết quả) như PageRank, HITS, Ta thấy rằng các phương pháp này chủ yếu dựa vào liên kết trang để xác định trọng số cho các trang đó.
Ta có thể tiếp cận theo một hướng khác đó là dựa vào nội dung của các tài liệu để xác định trọng số, nếu các tài liệu "gần nhau" về nội dung thì sẽ quan trọng tương đương và sẽ thuộc về cùng một nhóm, nhóm nào gần với câu truy vấn hơn sẽ quan trọng hơn.
Giả sử cho một tập S gồm các trang web, tìm ra các trang thỏa mãn câu hỏi truy vấn được tập tập R. Sử dụng thuật toán phân cụm dữ liệu để phân tập R thành k cụm (k xác định) sao cho các phần tử trong cụm là tương tự nhau nhất, các phần tử ở các cụm khác nhau thì phi tương tự với nhau.
Từ tập S-R, đưa các phần tử này vào một trong k cụm đã được thiết lập ở trên. Những phần tử nào tương tự với trọng tâm của cụm (theo một ngưỡng xác định nào đó) thì đưa vào cụm này, những phần tử không thỏa mãn xem như không phù hợp với truy vấn và loại bỏ nó khỏi tập kết quả.
Kế tiếp ta đánh trọng số cho các cụm và các trang trong tập kết quả như sau:
- Đối với các cụm, dựa vào trọng tâm của cụm để xác định trọng số. Trọng tâm nào tương tự với truy vấn hơn sẽ có trọng số lớn hơn.
- Xác định trọng số cho mỗi trang trong cụm. Trang nào gần trọng tâm hơn sẽ có trọng số lớn hơn.
Như vậy, theo cách tiếp cận này sẽ giải quyết được các vấn đề sau:
+ Kết quả tìm kiếm sẽ được phân thành các cụm chủ đề khác nhau, tùy vào yêu cầu cụ thể mà người dùng sẽ xác định chủ đề mà họ cần.
+ Quá trình tìm kiếm và xác định trọng số cho các trang chủ yếu tập trung vào nội dung của trang hơn là dựa vào các liên kết trang.
+ Giải quyết được vấn đề từ/cụm từ đồng nghĩa trong câu truy vấn của người dùng.
+ Có thể kết hợp phương pháp phân cụm trong lĩnh vực khai phá dữ liệu với các phương pháp tìm kiếm đã có.
Một số thuật toán phần cụm dữ liệu được sử dụng trong phân cụm văn bản như thuật toán phân cụm phân hoạch (k-means, PAM, CLARA), thuật toán phân cụm phân cấp (BIRCH, STC), . Trong thực tế phân cụm theo nội dung tài liệu Web, một tài liệu có thể thuộc vào nhiều nhóm chủ đề khác nhau, để giải quyết việc này ta có thể sử dụng thuật toán phân cụm theo cách tiếp cận mờ như
FCM, ξFCM,
3. Quá trình tìm kiếm và phần cụm tài liệu
Quá trình phân cụm kết quả tìm kiếm gồm các bước như sau [19]:
- Tìm kiếm các trang Web từ các Website thỏa mãn nội dung truy vấn.
- Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL tương ứng.
- Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang Web thành các cụm, sao cho các trang trong cụm “tương tự” về nội dung với nhau
hơn các trang ngoài cụm.
Đánh giá và biểu diễn tri thức
Áp dụng thuật toán phân cụm
Biểu diễn dữ liệu
Dữ liệu web
Tìm kiếm và Tiền xử lý trích rút dữ liệu
Các bước phần cụm kết quả tìm kiếm trên Web
3.1. Tìm kiếm dữ liệu trên Web
Nhiệm vụ chủ yếu của giai đoạn này là dựa vào tập từ khóa tìm kiếmđể tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt tài liệu, URL, tương ứng với các trang đó.
Nhằm nâng cao tốc độ xử lý, ta tiến hành tìm kiếm và lưu trữ các tài liệu này trong kho dữ liệu để sử dụng cho quá trình tìm kiếm lần sau (tương tự như các Search Engine Yahoo, Google, ). Mỗi phần tử gồm toàn văn tài liệu, tiêu đề, đoạn mô tả nội dung (snippets), URL,
3.2. Tiền xử lý dữ liệu
Quá trình làm sạch dữ liệu và chuyển dịch các tài liệu thành các dạng biểu diễn thích hợp dữ liệu.
Giai đoạn này bao gồm các công việc như sau: Chuẩn hóa văn bản, xóa bỏ các từ dừng, kết hợp các từ có cùng từ gốc, số hóa và biểu diễn văn bản,
3.2.1. Chuẩn hóa văn bản
Đây là giai đoạn chuyển văn bản thô về dạng văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuật tiện, chính xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả xử lý. Bao gồm:
+ Xóa các thẻ trong HTML và các loại thẻ khác để trích ra các từ/cụm từ.
+ Chuyển các ký tự hoa thành các ký tự thường.
+ Xóa bỏ các dấu câu, xoá các ký tự trắng dư thừa, .
3.2.2. Xóa bỏ các từ dừng
Trong văn bản có những từ mang ít thông tin trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất hiện với tần số lớn nhưng không quan trọng cho quá trình xử lý. Theo một số nghiên cứu gần đây [2] cho thấy việc loại bỏ các từ dùng có thể giảm bởi được khoảng 20-30% tổng số từ trong văn bản.
Có rất nhiều từ xuất hiện với tần số lớn nhưng nó không hữu ích cho quá trình KPDL. Ví dụ trong tiếng Anh các từ như a, an, the, of, and, to, on, by, . trong tiếng Việt như các từ “thì”, “mà”, “là”, “và”, “hoặc”, . Những từ xuất hiện với tần số quá lớn cũng sẽ được loại bỏ.