Á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

Ngày nay, nhờ sự cải tiến không ngừng của các Search engine về cả chức năng tìm kiếm lẫn giao diện đã giúp cho người sử dụng dễ dàng hơn trong việc tìm kiếm thông tin trên web. Tuy nhiên, người sử dụng thường vẫn phải duyệt qua hàng trăm thậm chí hàng ngàn trang Web...
Nội dung trích xuất từ tài liệu:
Á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 ĐỀ Á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 The Application of data clustering technique in the result classification data searching Vũ Đức Thi1, Hoàng Văn Dũng2 Abstract Nowadays, searching information with big data is one of main s ubjects for data mining. In this paper we would like to introduce an approach to search and classify web documents by using data clustering technique, we solve the mathematical problem according to three main phases: search Web documents, data preprocessing, presenting data with vector models and cluster web documents. Từ khóa: data mining, phân cụm dữ liệu, phân cụm Web… 1. Giới thiệu Ngày nay, nhờ sự cải tiến không ngừng của các Search engine về cả c hức năng tìm kiếm lẫn giao diện đã giúp cho người sử dụng dễ dàng hơn trong việc tìm kiếm thông tin trên web. Tuy nhiên, người sử dụng thường vẫn phải duyệt qua hàng trăm thậm chí hàng ngàn trang Web mới có thể tìm kiếm được thứ mà họ cần. Theo tâm lý chung, người dùng chỉ xem qua vài chục kết quả đầu tiên, họ thiếu kiên nhẫn và không đủ thời gian để xem qua tất cả kết quả mà các search engine trả về. Nhằm giải quyết vấn đề này, ta có thể nhóm các kết quả tìm kiếm thành các nhóm theo từng chủ đề, khi đó người 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 công việc tìm kiếm một cách hiệu quả hơn. Tuy nhiên vấn đề phân cụm tài liệu 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 bài báo này, ta sẽ xem xét khía cạnh sử dụng kỹ thuật phân cụm để phân nhóm tài liệu Web dựa trên kho dữ liệu đã được tìm kiếm và lưu trữ. 1 Viện CNTT, Viện Khoa học - Công nghệ Việt Nam 2 Trường ĐH Quảng Bình 1 2. Hướng tiếp cận bằng kỹ thuật phân cụm Hiện nay, để xác định mức độ quan trọng của một trang web chúng ta có nhiều cách đánh giá như PageRank, HITS, …Tuy nhiên, các phương pháp đánh giá này chủ yếu đều dựa vào các liên kết để xác định trọng số cho các trang. Ta có thể tiếp cận cách đánh giá mức độ quan trọng 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ố cho trang, nếu các tài liệu tương tự về mặt nội dung thì sẽ có mức độ quan trọng tương đương và sẽ thuộc về cùng một nhóm. Giả sử S là tập các trang web đang xem xét, tìm trong tập S các trang chứa nội dung truy vấn ta được tập R. Sử dụng thuật toán phân cụm để 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 và 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, ta tìm cách đư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ụ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ả theo thuật toán sau: Đầu vào: tập dữ liệu D chứa các trang gồm k cụm và k trọng tâm Đầu ra: trọng số của các trang Phương pháp B1: Mỗi cụm dữ liệu thứ m và trọng tâm Cm ta gán cho nó một trọng số tsm. Với các trọng tâm Ci, Cj bất kỳ ta luôn có tsi>tsj nếu ti tương tự với truy vấn hơn tj. B2: Với mỗi trang p trong cụm m ta xác định trọng số trang là pw. Với mọi pi, pj bất kỳ ta luôn có pwi>pwj nếu pi gần trọng tâm hơn pj. Hình 1. Thuật toán đánh trọng số cụm và trang 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 theo các chủ đề khác nhau, tùy vào yêu cầu cụ thể người dùng sẽ xác định chủ đề mà họ cần để tìm kiếm. 2 + 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 truy vấn. + 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ó nhằm nâng cao chất lượng tìm kiếm. Hiện tại, có một số thuật toán phân cụm dữ liệu thường đượ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 vấn đề này ta có thể sử dụng thuật toán phân cụm theo cách tiếp cận mờ. 3. Quá trình tìm kiếm và phân cụm tài liệu Về cơ bản, quá trình phân cụm kết quả tìm kiếm sẽ diễn ra theo các bước chính được thể hiện như Hình 2 [14]: - 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. Tìm kiếm và Tiền xử lý Dữ liệu web trích rút dữ liệu Biểu diễn Biểu diễn Phân cụm và xác kết quả dữ liệu định trọng số trang Hình 2. Các bước phân cụm kết quả tìm kiếm trên Web 3 3.1. Tìm kiếm dữ liệu trên Web Nhiệ ...