Tài liệu Sắp xếp kết quả của máy tính bằng kỹ thuật phân cụm

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN THỊ HUỆ SẮP XẾP KẾT QUẢ CỦA MÁY TÌM KIẾM BẰNG KỸ THUẬT PHÂN CỤM Chuyên ngành: Truyền dữ liệu và mạng máy tính Mã số: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012 1 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: PGS.TS. TỪ MINH PHƯƠNG Phản biện 1: …………………………………… Phản biện 2: …………………………………… Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Hiện nay, tìm kiếm thông tin trên Internet đã trở nên đơn giản hơn với sự phát triển cả về nội dung và hình thức của các công cụ tìm kiếm. Tuy nhiên, với sự phát triển nhanh chóng của mạng Internet hiện nay thì số lượng các trang Web là rất lớn. Vấn đề đặt ra là với câu truy vấn mà trả về hàng trăm, hàng nghìn thậm chí hàng tỷ kết quả thì liệu rằng người dùng có đủ kiên nhẫn và thời gian để lướt qua tất cả các kết quả đó hay không? Để tiến hành xử lý vấn đề này, các kỹ thuật phân cụm đã được sử dụng. Luận văn với đề tài: “Sắp xếp kết quả của máy tìm kiếm bằng kỹ thuật phân cụm” tập trung nghiên cứu về kỹ thuật phân cụm và áp dụng nó để sắp xếp kết quả tìm kiếm theo chủ đề. Luận văn được chia thành 3 chương với các nội dung chính như sau: Chương 1. Tổng quan. Trình bày khái quát về bài toán phân cụm kết quả tìm kiếm và giới thiệu đặc điểm, 2 chức năng, giao diện của một công cụ tìm kiếm điển hình hiện nay. Chương 2. Sắp xếp kết quả tìm kiếm bằng kỹ thuật phân cụm. Trình bày những nét cơ bản nhất về bài toán phân cụm dữ liệu nói chung và đặc biệt đi sâu vào bài toán phân cụm kết quả tìm kiếm theo chủ đề nói riêng, bao gồm: giới thiệu và mô tả bài toán, một số độ đo độ đánh giá, các phương pháp phân cụm phổ biến,... Chương 3. Thực nghiệm và đánh giá. Trinh bày các bước tiến hành thực nghiệm trên tập dữ liệu lấy từ máy tìm kiếm google, phân tích và xử lý sau đó đánh giá kết quả trước và sau khi áp dụng kỹ thuật phân cụm. Phần Kết luận Trình bày tổng hợp các kết quả mà luận văn đã thực hiện được và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. 3 CHƯƠNG I. TỔNG QUAN 1.1. Tổng quan về bài toán phân cụm kết quả tìm kiếm Ý tưởng được đưa ra là khi kết quả trả về của công cụ tìm kiếm cần được phân ra theo chủ đề, giúp người dùng định hướng, lựa chọn tài liệu phù hợp một cách nhanh chóng và hiệu quả hơn. Chẳng hạn, nếu chúng ta gửi truy vấn là “ô tô” thông qua công cụ tìm kiếm nối tiếng như google [14] thì sẽ nhận được khoảng 83 100 000 kết quả tìm kiếm (Số liệu thống kê 27/9/2012). Giống như nhiều truy vấn khác, truy vấn “ô tô” cũng có nhiều đặc trưng khác nhau chẳng hạn như: mua bán, đua xe, kỹ thuật lái xe, ... Mỗi kết quả mang một đặc trưng nhất định và có thể các trang có cùng đặc trưng sẽ nằm rải rác, xen kẽ trong một số lượng lớn các danh sách kết quả trả về. 4 Nhiệm vụ chúng ta cần giải quyết là những trang nào có nội dung đề cập đến mua bán xe ô tô ta gom vào một nhóm, làm tương tự với các nhóm đua xe, kỹ thuật lái xe, ... Khi đã xử lý được việc phân cụm này thì người sử dụng chỉ việc truy cập đến chủ đề cần tìm mà không cần quan tâm đến các chủ đề khác. Phương pháp phân cụm ở đây sẽ đưa về bài toán phân cụm xếp hạng các cụm từ quan trọng. Đưa ra câu truy vấn và lấy về một danh sách các tài liệu đã được xếp hạng từ công cụ tìm kiếm, đầu tiên là tách các tài liệu thành các cụm từ, sau đó xếp hạng các cụm từ này. Công trình đầu tiên dựa trên kỹ thuật phân cụm là Northern Light, vào cuối những năm 1990, nó chỉ được phân cụm dựa trên kết quả tìm kiếm được cho sẵn. Tính đến nay, phân cụm đã được tích hợp trong một số máy tìm kiếm tiếng Anh như Viv'isimo, carrot2 hay Clusty đạt độ chính xác khá cao, với tiếng Việt hiện tại chỉ có Việt Nam Search Engine là máy tìm kiếm có 5 tích hợp phân cụm đang được xây dựng và đem lại kết quả rất khả quan. 1.2. Công cụ tìm kiếm thông thường 1.2.1. Giới thiệu Công cụ tìm kiếm là một công cụ rất hữu ích giúp người dùng sử dụng nguồn tài nguyên trên Internet một cách hiệu quả nhất. 1.2.2. Quá trình tìm kiếm và kết quả tìm kiếm 1.2.2.1. Hệ thống thu thập dữ liệu 1.2.2.2. Hệ thống phân tích và lập chỉ mục dữ liệu 1.2.2.3. Hệ thống tìm kiếm 1.2.3. Một số công cụ tìm kiếm điển hình 1.2.3.1. Google: http://www.google.com/ 1.2.3.2. Yahoo: http://yahoo.com/ 1.2.3.3. MSN: http://www.msn.com/ 1.2.4. Hiệu quả của các công cụ tìm kiếm 6 Đáp ứng các truy vấn rộng, mơ hồ, danh sách kết quả nằm rải rác, pha trộn với một số trang không liên quan đến truy vấn,.... Ngoài ra với khối lượng thông tin lớn trên Internet thì danh sách kết quả trả về cũng lớn, có khi là hàng tỷ kết quả với một câu truy vấn và điều này cũng hạn chế khả năng lướt toàn bộ kết quả tìm kiếm của người sử dụng. 1.3. Kết luận chương 7 CHƯƠNG II. SẮP XẾP KẾT QUẢ TÌM KIẾM BẰNG KỸ THUẬT PHÂN CỤM 2.1. Kỹ thuật phân cụm 2.1.1. Giới thiệu phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, quá trình phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" với nhau. 2.1.2. Một số yêu cầu trong quá trình phân cụm - Chọn lựa đặc trưng - Chọn độ đo tương tự - Tiêu chuẩn phân cụm - Thuật toán phân cụm: - Công nhận kết quả - Giải thích kết quả 8 2.1.3. Xây dựng mô hình phân cụm dữ liệu 2.1.3.1. Mô hình tài liệu Hầu hết các thuật toán phân cụm đều yêu cầu tập dữ liệu cần được phân cụm ở dạng một tập các véc tơ D = {d1, d2, …, dn} trong đó véc tơ di, i= 1, 2 …, n đại diện cho một đối tượng đơn lẻ trong tập dữ liệu và được gọi là véc tơ đặc trưng (feature vector). a, Mô hình dữ liệu tài liệu b, Mô hình dữ liệu số c, Mô hình phân cụm dữ liệu d, Mô hình dữ liệu kết hợp 2.1.3.2. Độ đo về sự tương tự Với 2 véc tơ đặc trưng x và y, cần phải tìm ra độ tương tự (hoặc không tương tự) giữa chúng. Một lớp rất hay sử dụng bởi các hàm khoảng cách được mô tả như công thức (2.1) : 9 n x y  p  xi  yi p Công thức (2.1) i 1 Trong đó x,y Rn. Hàm khoảng cách này thực ra là mô tả một họ vô số các khoảng cách được đưa ra bởi p. Thông số này giả thiết là các giá trị lớn hơn hoặc bằng 1. Một vài giá trị chung của p và các hàm khoảng cách là: P = 1 : Khoảng cách Hammming xem công thức (2.2) n x  y   xi  y i Công thức (2.2) i 1 P = 2 : Khoảng cách Euclidean xem công thức (2.3) 2 n x y  x i  yi Công thức (2.3) i 1 P = ∞ : Khoảng cách Tschebyshev xem công thức (2.4) 10 x  y  max i 1, 2,..., n xi  yi Công thức (2.4) Một độ đo độ tương tự hay được dùng, đặc biệt là trong phân cụm tài liệu đó là độ đo liên quan cosine (cosine correlation), được định nghĩa như công thức (2.5): cos( x, y )  x. y x y Công thức (2.5) Trong đó . biểu thị việc nhân vector và ||.|| biểu thị cho độ dài của vector. Một độ đo hay được dùng khác đó là độ đo Jaccard (được sử dụng trong [26], [32]), được định nghĩa như công thức (2.6) :  d ( x, y )   n i 1 n min( xi , yi ) max( xi , yi ) i 1 Công thức (2.6) Trong trường hợp các vector đặc trưng nhị phân, có thể đơn giản hóa như công thức (2.7): 11 d ( x, y )  x y x y Công thức (2.7) 2.1.3.3. Mô hình phân cụm tài liệu Tùy theo vấn đề, chúng ta có thể có các phân cụm tách rời (disjoint) hoặc các phân cụm chồng chéo (overlapping). 2.1.4. Một số vấn đề trong xử lý dữ liệu văn bản 2.1.4.1. Loại bỏ từ dừng 2.1.4.2. Định luật Zipf 2.2. Phân cụm kết quả tìm kiếm 2.2.1. Mô tả bài toán Đưa ra danh sách được xếp hạng gốc của kết quả tìm kiếm R={r(di|q)}. Trong đó: + q là câu truy vấn hiện tại + di là một tài liệu (kết quả tìm kiếm) + r là một hàm tính độ liên quan giữa di và q 12 2.2.2. Mô tả thuật toán Phương pháp phân cụm dựa vào xếp hạng các cụm từ quan trọng [25] đã đưa bài toán phân cụm kết quả tìm kiếm sang bài toán xếp hạng các cụm từ quan trọng. 2.2.3. Mục tiêu của kỹ thuật phân cụm kết quả tìm kiếm Sắp xếp kết quả tìm kiếm theo chủ đề, giúp người sử dụng thuật tiện trong quá trình tìm kiếm thông tin từ các máy tìm kiếm. 2.2.4. Yêu cầu phân cụm kết quả tìm kiếm Bản chất dữ liệu cùng với việc sử dụng tương tác của cụm các kết quả đặt ra yêu cầu mới và thách thức đối với công nghệ phân cụm, như chi tiết trong danh sách sau đây. - Nhãn có ý nghĩa. - Tính toán hiệu quả. - Dữ liệu đầu vào Mô tả ngắn. 13 - Không biết số của các cụm. - Các chồng chéo cụm. - Giao diện người dùng đồ họa (GUI). 2.2.5. Các bước phân cụm kết quả tìm kiếm 2.2.5.1. Thu nhận kết quả tìm kiếm Cụ thể là dựa vào câu truy vấn để 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, URL,… tương ứng với các trang đó. 2.2.5.2. Tiền xử lý kết quả tìm kiếm a. Chuẩn hóa văn bản + Xóa các thẻ 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,... b. Xóa bỏ các từ dừng 14 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ý đều được loại bỏ. c. Kết hợp các từ có cùng gốc Hầu hết trong các ngôn ngữ đều có rất nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự nhau, do đó để giảm bởt số chiều trong biểu diễn văn bản, ta sẽ kết hợp các từ có cùng gốc thành một từ. d. Xây dựng từ điển Từ điển sẽ gồm một bảng các từ, chỉ số của nó trong từ điển và được sắp xếp theo thứ tự. e. Tách từ, số hóa văn bản và biểu diễn tài liệu Quá trình tách từ, vector hóa tài liệu là quá trình tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong từ điển. 2.2.5.3. Phân cụm kết quả tìm kiếm 2.3. Một số thuật toán phân cụm điển hình 15 2.3.1. Thuật Toán K-Means Các bước thực hiện B1. Chọn ngẫu nhiên K tâm cho K cụm. Mỗi cụm được đại diện bằng các tâm của cụm. B2. Tính khoảng cách giữa các đối tượng đến K tâm (thường dùng khoảng cách Euclidean) B3. Nhóm các đối tượng vào nhóm gần nhất B4. Xác định lại tâm mới cho các nhóm B5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng 2.3.2. Thuật toán Hierarchical Agglomeraltive Clustering Đoạn mã giả của thuật toán HAC [3]. 1. Đặt mỗi tài liệu d là một nhóm đơn {d} 2. Đặt G là tập tất cả các nhóm 3. while |G| > 1 do 16 4. Chọn Ґ, Δ Є G thông qua độ đo tính tương tự s(Ґ, Δ) 5. Loại bỏ Ґ, Δ khỏi G 6. Đặt Ф= Ґ Δ 7. Thêm Ф vào G 8. end while 2.3.3. Thuật toán Expectation Maximization Thuật toán Expectation Maximization ở bước lặp thứ t thực hiện các công việc sau: - Bước E: Tính toán để xác định giá trị của các biến chỉ thị dựa trên mô hình hiện tại và dữ liệu: - Bước M: Đánh giá xác suất 2.3.4. Thuật toán Suffix Tree Clustering STC có ba bước hợp lý: (1) văn bản "làm sạch", (2) xác định các cụm cơ sở bằng cách sử dụng một cây hậu tố, và (3) kết hợp các cụm cơ sở thành các cụm. 2.4. Kết luận chương 17 CHƯƠNG III. THỰC NGHIỆM VÀ ĐÁNH GIÁ 3.1. Tập dữ liệu Dữ liệu của thực nghiệm được lấy từ danh sách các kết quả trả về của máy tìm kiếm google. Thực hiện gán nhãn dữ liệu cho truy vấn với các từ khóa: “ô tô”. Trong chương trình này thực nghiệm với 50 kết quả đầu tiên, bao gồm tiêu đề, đoạn tóm tắt của tài liệu, URL và toàn bộ nội dung của mỗi kết quả tìm kiếm. Như vậy, tập dữ liệu vào của bài toán chứa nội dung là các từ xuất hiện trong từng trang. Còn dữ liệu ra là nhóm tập dữ liệu đó thành k cụm tùy ý. 3.2. Các công cụ thử nghiệm Công cụ chính được sử dụng để tiến hành phân cụm là phần mềm WEKA (Waikato Environment for Knowledge Analysis.). Để sử dụng được phần mềm Weka ta phải chuẩn bị dữ liệu vào dưới dạng file ARFF. 18 Một file ARFF cho dữ liệu oto trong bảng, file này đưa ra đặc trưng giá trị số. Dòng đầu tiên với một dấu % những ghi chú. Tiếp theo ghi chú ở đầu của file là tên của quan hệ (oto) và một khối định nghĩa các đặc trưng (mua_bán_ô_tô, tin_tức, ô_tô_nhập_khẩu, kỹ_thuật_lái_xe, thị_trường_ô_tô, người_đẹp_ô_tô, đồ_chơi, siêu_xe, giá_cả, đánh_giá). Các đặc trưng định danh được theo sau bởi một tập các giá trị mà chúng có thể xảy ra, và chúng được đặt trong dấu {}. Các giá trị có thể bao gồm các khoảng trống; Nếu vậy, chúng phải được đặt giữa hai dấu “”. Các giá trị số được kèm theo bởi từ khóa numeric. Tiếp theo các định nghĩa về đặc trưng là một dòng @data là ký hiệu cho bắt đầu các mẫu (instance) trong tập dữ liệu. Các instance được viết mỗi cái trên một dòng, với các giá trị cho mỗi đặc trưng theo thứ tự, cách nhau bởi dấu phẩy. Nếu một giá trị bị lỗi (missing) thì nó được thể hiện bằng một dấu hỏi chấm (không có giá trị missing nào trong dữ liệu này). Các mô tả đặc trưng trong file ARFF cho phép tập dữ liệu được kiểm tra xem có chắc rằng nó