Một tiếp cận đánh giá độ trùng lặp văn bản sử dụng trong số mờ
Trùng lặp nội dung văn bản là vấn đề phổ biến từ các trang báo, trang tin đến
các tác phẩm. Việc phát hiện trùng lặp là rất cần thiết. Bản chất là kiểm tra sự tương tự
giữa các tài liệu. Tuy nhiên, đây là bài toán phức tạp và đang được quan tâm nghiên cứu.
Hiện nay, có nhiều phương pháp được nghiên cứu để giải quyết vấn đề này. Trong bài
báo này, chúng tôi đề xuất một cải tiến độ đo tương tự dựa trên logic mờ và ứng dụng
trong vấn đề phát hiện trùng lặp nội dung bài báo.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Bạn đang xem tài liệu "Một tiếp cận đánh giá độ trùng lặp văn bản sử dụng trong số mờ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Một tiếp cận đánh giá độ trùng lặp văn bản sử dụng trong số mờ
TP CH KHOA HC − S 8/2016 105 M T TI>P C=N NH GI TR/NG LMP VNN B5N S D8NG TR+NG S# M@ Đỗ Nam Tiến1(1), Khiếu Văn Bằng1, Nguyễn Tu Trung1, Trần Thành Trung2, Nguyễn Huy Đức3 1Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam 2Trường Đại học Sư phạm Hà nội 2 3Trường Cao đẳng Sư phạm Trung Ương Tóm tắt: Trùng lặp nội dung văn bản là vấn đề phổ biến từ các trang báo, trang tin đến các tác phẩm. Việc phát hiện trùng lặp là rất cần thiết. Bản chất là kiểm tra sự tương tự giữa các tài liệu. Tuy nhiên, đây là bài toán phức tạp và đang được quan tâm nghiên cứu. Hiện nay, có nhiều phương pháp được nghiên cứu để giải quyết vấn đề này. Trong bài báo này, chúng tôi đề xuất một cải tiến độ đo tương tự dựa trên logic mờ và ứng dụng trong vấn đề phát hiện trùng lặp nội dung bài báo. Từ khoá: Văn bản, phát hiện trùng lặp, độ tương tự. 1. ĐẶT VẤN ĐỀ Trùng lặp nội dung văn bản là hiện tượng phổ biến trong đời sống. Vì nhiều nguyên nhân, các văn bản thường bị sao chép, trích dẫn. Đây là lí do mà các văn bản có thể tìm được từ nhiều nguồn khác nhau như các trang báo điện tử. Vì những lí do khác nhau, nhiều khi chúng ta muốn tìm và phát hiện sự trùng lặp giữa các văn bản. Ví dụ liên quan đến vấn đề tác quyền, tác giả muốn kiểm tra xem nội dung tác phẩm của họ có bị sử dụng dụng lại một cách trái phép hay không. Vấn đề đạo nhạc, đạo bài hát, tác phẩm văn học... hiện đang khiến giới chuyên môn bức xúc. Đối với các hệ thống lưu trữ tài liệu, việc lưu các văn bản có độ trùng lặp cao chỉ gây lãng phí và tốn tài nguyên. Với các máy tìm kiếm, khi thu thập dữ liệu từ Internet, nếu đánh giá tốt độ trùng lặp của dữ liệu mới so với các tài liệu có trong kho dữ liệu sẽ tránh được việc tiếp tục tải thêm và lưu trữ một dữ liệu mới trùng lặp vào kho dữ liệu... Vì vậy, vấn đề phát hiện trùng lặp hiện đang được quan tâm. (1) Nhận bài ngày 11.8.2016; gửi phản biện và duyệt đăng ngày 15.9.2016 Liên hệ tác giả: Đỗ Nam Tiến; Email:tiendonam@gmail.com 106 TRNG I HC TH H NI Phát hiện trùng lặp là bài toán phức tạp vì các văn bản thường không bị sao chép toàn phần mà chỉ một phần có thể ít, có thể nhiều. Các phần bị sao chép có thể bị thay đổi và nằm ở vị trí khác nhau trong văn sao chép. Hiện tại, có nhiều kĩ thuật phát hiện trùng lặp khác nhau bao gồm: Shingling[1], I-Match[2], Phép chiếu ngẫu nhiên, SpotSigs, Sự tương tự giữa hai tài liệu... Có thể thấy vấn đề phát hiện trùng lặp thực chất là việc tính toán độ tương tự trong nội dung của văn bản cần so sánh với các văn bản có sẵn trong kho dữ liệu (Corpus). Độ tương tự của văn bản được xác định dựa trên các chỉ số như: • Độ tương tự về ngữ nghĩa của các văn bản: Từ khoá, TF - IDF; • Độ tương tự về câu văn, đoạn văn; • Độ tương tự về ngữ pháp của văn bản: Cú pháp câu, từ loại,... • Độ tương tự về các thẻ HTML của các trang web; Việc sử dụng một tiêu chí để đánh giá độ tương tự của các văn bản trong kho văn bản ngày càng trở nên thiếu hiệu quả do người dùng Internet và các công cụ sao chép nội dung ngày càng thông minh hơn. Do đó, ngày càng có nhiều nghiên cứu tập trung vào việc kết hợp các tiêu chí đánh giá độ tương tự với nhau để từ đó làm tăng độ chính xác của các công cụ đánh giá độ tương tự văn bản, phát hiện trùng lặp, máy tìm kiếm,... Trong [4], Muneer và cộng sự đã đề xuất thuật toán cho việc thiết lập các cụm trang web trùng lặp. Ngoài ra, Fresno và cộng sự đã đề xuất hàm trọng số FCC là hệ mờ cho việc gán các trọng số đặc trưng và sự kết hợp của chúng [5][3]. Hiện nay, trong nước cũng đã có một số công trình nghiên cứu về việc phát hiện nội dung trùng lặp trong kho văn bản tiếng Việt [9], [6], [8], các nghiên cứu cho thấy việc kết hợp các tiêu chí đánh giá nội dung văn bản để phát hiện sự trùng lặp trong kho văn bản tiếng Việt làm tăng độ chính xác trong việc đánh giá của các thuật toán. Tuy nhiên, các nghiên cứu cũng cho thấy vẫn cần phải nghiên cứu thêm để cải tiến, tối ưu hoá việc kết hợp các tiêu chí đánh giá để nâng cao độ chính xác của việc phát hiện trùng lặp. Bài báo này đề xuất cải tiến đánh giá độ tương tự giữa hai văn bản tiếng Việt.Các phần còn lại của bài báo này được trình bày như sau. Phần 2 trình bày hệ thống tra cứu văn bản nói chung và đô đo tương tự giữa hai văn bản. Phần 3 trình bày độ đo tương tự mới cải tiến từ độ đo đã có sử dụng logic mờ. Một số thử nghiệm được trình bày trong phần 4. Phần 5 là kết luận bài báo. 2. HỆ THỐNG TRA CỨU VĂN BẢN TRÙNG LẶP Trong [6] đưa ra một mô hình hệ thống tra cứu văn bản trùng lặp. Chương trình thực hiện kiểm tra một bài báo điện tử được thu thập về xem có giống/gần giống với các bài đã TP CH KHOA HC − S 8/2016 107 được thu thập trước đó hay không. Dữ liệu được lấy từ các bài báo điện tử được viết bằng Tiếng Việt. Hình 1. Mô hình thử nghiệm vấn đề phát hiện trùng lặp nội dung các bài báo [6]. Các bước thực hiện như sau: • Bước 1: Thu thập các bài báo điện tử • Bước 2: Lấy nội dung của các bài báo đã được thu thập và loại bỏ nhiễu. • Bước 3: Thực hiện shingling cho mỗi tài liệu. • Bước 4: Lấy dấu vân cho mỗi tài liệu. • Bước 5: So sánh và cho ra kết quả. 3. ĐỘ ĐO TƯƠNG TỰ Hình 2. Mô hình không gian vector cho văn bản [7]. Văn bản thường được biểu diễn dưới dạng vector dựa theo mô hình tần suất [7] mà tiêu biểu là các phương pháp dựa trên tần số (TF) và nghịch đảo tần số (IDF). Hình 2 là ví dụ trong trường hợp biểu diễn văn bản với số Token là 2. Về mặt tổng quát, sô Token rất nhiều, ví dụ: Tổng số âm tiết (nếu dùng đặc trưng âm tiết), Tổng số từ (nếu dùng đặc trưng từ). 108 TRNG I HC TH H NI Có một số độ đo được sử dụng như: độ tương tự cosine (cosine similarity), hệ số Jaccard (Jaccard coeficient), khoảng cách Euclide(Euclideandistance), hệ số tương quan Pearson (Pearson Correlation coeficient) [7]... Trong bài báo này, chúng tôi xem xét độ đo khoảng cách Euclide được biểu diễn theo công thức sau đây (1): 4. THUẬT TOÁN PHÂN CỤM DỮ LIỆU Khi cơ sở dữ liệu văn bản rất lớn, việc tra cứu trên toàn bộ kho văn bản khiến tốc độ thực thi rất chậm. Vì vậy, người ta có thể tiến hành cụm kho văn bản trước để tăng tốc độ tra cứu. Ngoài ra, kĩ thuật phân cụm còn được sử dụng để hỗ trợ phân lớp kho dữ liệu văn bản. Thuật toán KMeans [10] bao gồm 4 bước, được trình bày như sau: Đầu vào: n đối tượng xi với i = 1..n và số cụm c Đầu ra: Các cụm Cj (j = 1..c) sao cho hàm mục tiêu E sau đây đạt cực tiểu: (1) Các bước thuật toán như sau: Bước 1: Khởi tạo Chọn k đối tượng Cj (j=1..c) là tâm ban đầu của c cụm dữ liệu đầu vào (lựa chọn ngẫu nhiên hoặc theo kinh nghiệm). Bước 2: Gán tâm cụm theo khoảng cách Với mỗi đối tượng xi (i = 1..n), tính khoảng cách của nó tới mỗi tâm Cj với j = 1..c. Đối tượng thuộc về cụm CS mà khoảng cách từ tâm CS tương ứng đến đối tượng đó là nhỏ nhất. (2) Bước 3: Cập nhật tâm cụm Đối với mỗi j = 1c, cập nhật lại tâm cụm Cj bằng cách xác định trung bình cộng của các vector đối tượng dữ liệu đã được gán về cụm. (3) Bước 4: Lặp và kiểm tra điều kiện dừng Lặp lại các bước 2 và 3 cho đến khi các tâm cụm không thay đổi giữa hai lần lặp liên tiếp. TP CH KHOA HC − S 8/2016 109 Trong đó: • : khoảng cách từ x đến tâm Cj • : thành phần thứ k của tâm cụm Cj • : thành phần thứ k của đối tượng x 5. ĐỀ XUẤT ĐỘ ĐO TƯƠNG TỰ CẢI TIẾN Hiện tại, các độ đo tương tự đều đánh giá các đặc trưng có vai trò như nhau và chỉ dựa vào tần suất để phân biệt giá trị đặc trưng theo từng văn bản cụ thể. Nếu chỉ sử dụng đặc trưng rmức âm tiết – đơn vị đặc trưng không có nghĩa thì không sao. Tuy nhiên, nếu sử dụng đặc trưng mức từ, điều này là không hợp lí. Lí do là vì các từ thông thường sẽ được sử dụng nhiều hơn so với tên riêng, tên người, con số nên khả năng lặp lại cao hơn rất nhiều. Hay chữ viết tắt có khả năng lặp lại rất thấp trong các văn bản. Nói cách khác, xét về khả năng lặp lại thì các từ thông thường có ảnh hưởng lớn nhất còn các chữ viết tắt ảnh hưởng ít nhất. Như vậy, nếu chúng ta phân hạng đặc trưng theo các mức khác nhau thì có thể đánh giá độ tương tự văn bản chính xác hơn. Từ đây, nhóm tác giả đề xuất tập luật để xác định mức độ ảnh hưởng của các loại đặc trưng như sau: 1) Nếu đặc trưng là Từ thông thường thì ảnh hưởng rất lớn. 2) Nếu đặc trưng là Tên riêng thì ảnh hưởng lớn. 3) Nếu đặc trưng là Tên người hoặc tên thực thể thì ảnh hưởng trung bình. 4) Nếu đặc trưng là Phần trăm hoặc Số thì ảnh hưởng nhỏ. 5) Nếu đặc trưng là Chữ viết tắt thì ảnh hưởng rất nhỏ. Gọi là đặc trưng thứ i, hàm ảnh hưởng theo loại đặc trưng của đặc trưng là . Khi này, công thức đo độ tương tự (1) cải tiến trở thành (2): 6. THỰC NGHIỆM Độ đo tương tự văn bản được ứng dụng trong vấn đề tra cứu văn bản trùng lặp. Cụ thể, cơ sở dữ liệu nhóm tác giả sử dụng bao gồm danh sách trên 500 bài báo (tên, tóm tắt). Với bài báo mới, hệ thống thực hiện việc so sánh độ tương tự của phần tóm tắt với các bài báo trong cơ sở dữ liệu. Từ đây, hệ thống thực hiện việc phân cụm kho văn bản. Trong giai đoạn tra cứu, hệ thống đưa ra danh sách 5 bài báo có độ tương tự cao nhất từ các cụm. Hệ thống đưa ra hai cách thức tìm văn bản trùng lặp. Trường hợp 1, khi số lượng văn bản trong kho không quá nhiều, có thể duyệt toàn bộ văn bản và so sánh độ tương tự với văn 110 TRNG I HC TH H NI bản đầu vào. Trường hợp 2, số lượng văn bản trong kho quá lớn, giai đoạn tra cứu chia làm hai bước. Bước 1, hệ thống thực hiện so sánh độ tương tự của văn bản đầu vào với các cụm dữ liệu trong kho văn bản. Bước 2, từ các cụm gần nhất, hệ thống so sánh văn bản đầu vào với các văn bản thuộc cụm này. Trong thử nghiệm của chúng tôi, để rút trích được đặc trưng mức từ và phân biệt loại đặc trưng như trên, chúng tôi sử dụng công cụ phân tích đoạn văn "vn.hus.nlp.tokenizer" của nhóm nghiên cứu TS. Lê Hồng Phương. 6.1. Thử nghiệm đo độ tương tự hai văn bản Hình 3. So sánh hai văn bản khác nhau Hình 5. So sánh cùng một văn bản TP CH KHOA HC − S 8/2016 111 6.2. Đánh giá chất lượng phân cụm kho văn bản Để đánh giá chất lượng phân cụm, trong [11], các tác giả đã sử dụng chỉ số F(I) [13], tuân theo các tiêu chí về sự đồng nhất cụm [11] [12], để so sánh kết quả phân cụm của các thuật toán. Giá trị của F(I) càng nhỏ thì độ đồng nhất càng cao. Chỉ số này được tính như sau: (8) Bảng 1 và hình 6 thống kê chỉ số so sánh chất lượng phân cụm văn bản trong các trường hợp dùng và không dùng trọng số mờ trong các trường hợp 3, 5, 6 và 8 cụm. Bảng 1. So sánh độ đồng nhất cụm 3 5 6 8 Not Fuzzy 0.00303 0.00485 0.00521 0.0072 Fuzzy 0.0016 0.00266 0.00316 0.00415 Hình 6. So sánh độ đồng nhất cụm văn bản 6.3. Tra cứu văn bản tương tự a) Thử nghiệm 1 Bảng 1. Văn bản đầu vào thử nghiệm 1 Tên Tóm tắt Nghiên cứu hành vi xã hội, trí nhớ và học tập trên động vật thực nghiệm được tiêm thuốc gây bệnh tâm thần phân liệt Đánh giá hoạt động vận động, tương tác xã hội, trí nhớ không gian của chuột nhắt chủng Swiss trước và sau khi tiêm ketamine trường diễn với dải liều từ 10 - 35 mg/kg/ngày; Xây dựng mô hình gây bệnh TTPL thực nghiệm bằng liều ketamine phù hợp, sau đó điều trị bằng các thuốc chống loạn thần. Đánh giá sự biến đổi hành vi, trí nhớ và học tập của động vật trước và sau khi điều trị. 112 TRNG I HC TH H NI Bảng 2. Kết quả tìm kiếm với thử nghiệm 1 trong cở sở dữ liệu. Tên Độ tương tự Nghiên cứu hành vi xã hội, trí nhớ và học tập trên động vật thực nghiệm được tiêm thuốc gây bệnh tâm thần phân liệt 100% Nghiên cứu, ứng dụng hệ thống thông tin địa lí (GIS) và mô hình SWAT để dự báo lưu lượng dòng chảy và xói mòn đất tại tiểu lưu vực sông Ôn Lương - Hợp Thành. 71% Nghiên cứu ảnh hưởng của mật độ trồng đến năng suất và chất lượng giống sắn mới HL2004-28 tại trường Đại học Nông Lâm Thái Nguyên 71% Nghiên cứu vi sinh vật ứng dụng cho sản xuất biogas làm tăng hiệu suất trong điều kiện môi trường nước lợ và nước mặn 70% Phần mềm ôn luyện A 2 và IC 3 trực tuyến 70% b) Thử nghiệm 2 Bảng 3. Văn bản đầu vào thử nghiệm 2 Tên Tóm tắt Tác động của biến đổi khí hậu đến hạn hán khu vực Nam Trung Bộ Việt Nam, khả năng dự tính và giải pháp ứng phó Tổng quan về tình hình hạn hán và các nghiên cứu về hạn hán, dự tính hạn hán theo các kịch bản phát thải khí nhà kính; Thử nghiệm, lựa chọn chỉ số hạn khí tượng phù hợp, từ đó xác định mức độ biến đổi của hạn hán khu vực Nam Trung Bộ trong quá khứ, xu thế biến đổi trong tương lai theo các kịch bản phát thải khí nhà kính và đề xuất giải pháp ứng phó. Bảng 2. Kết quả tìm kiếm với thử nghiệm 2 trong cở sở dữ liệu Tên Độ tương tự Tác động của biến đổi khí hậu đến hạn hán khu vực Nam Trung Bộ Việt Nam, khả năng dự tính và giải pháp ứng phó 100% Phân tích đặc điểm địa hoá và thạch học của đá mẹ than và sét than trầm tích miocen khu vực phía bắc bể trầm tích sông Hồng 71% Nghiên cứu, ứng dụng hệ thống thông tin địa lí (GIS) và mô hình SWAT để dự báo lưu lượng dòng chảy và xói mòn đất tại tiểu lưu vực sông Ôn Lương - Hợp Thành. 70% Nghiên cứu vi sinh vật ứng dụng cho sản xuất biogas làm tăng hiệu suất trong điều kiện môi trường nước lợ và nước mặn 70% Xác lập cơ sở khoa học phục vụ quy hoạch bảo vệ môi trường huyện phú lộc tỉnh thừa thiên huế 70% TP CH KHOA HC − S 8/2016 113 c) Thử nghiệm 3 Bảng 4. Văn bản đầu vào thử nghiệm 3 Tên Tóm tắt Nâng cao năng lực tài chính của các ngân hàng thương mại cổ phần ở Việt Nam hiện nay Hệ thống hoá và hoàn thiện hơn những lí luận cơ bản về năng lực tài chính của NHTM như đưa ra quan điểm về tài chính, năng lực tài chính NHTM. Đặc biệt luận án đã chú trọng vào việc phân tích cơ sở để dẫn giải đưa đến nội dung trình bày về lí luận năng lực tài chính của NHTM; Phân tích rõ hơn cơ sở và ý nghĩa của các tiêu chí đánh giá năng lực tài chính NHTM, đồng thời cách tiếp cận khi phân tích các nhân tố ảnh hưởng cũng thể hiện tính logic và hệ thống với các giải pháp; Trên cơ sở nghiên cứu kinh nghiệm nâng cao năng lực tài chính của ngân hàng một số nước trên thế giới, chỉ ra căn nguyên chính dẫn đến những yếu kém về năng lực tài chính ngân hàng là tình trạng tăng trưởng tín dụng nóng và phát triển thiếu bền vững. Mặt khác, để nâng cao năng lực tài chính của các NHTM thì ngoài những nỗ lực của chính các NHTM còn rất cần nhưng hỗ trợ từ phía Ngân hàng Trung ương và Chính Phủ. Đây cũng chính là những bài học cần thiết trong việc nâng cao năng lực tài chính của các NHTMCP Việt Nam. Bảng 2. Kết quả tìm kiếm với thử nghiệm 1 trong cở sở dữ liệu Tên Độ tương tự Nâng cao năng lực tài chính của các ngân hàng thương mại cổ phần ở Việt Nam hiện nay 100% Hoàn thiện công tác lập và trình bày báo cáo tài chính hợp nhất trong các doanh nghiệp sản xuất thép thuộc Hiệp hội Thép Việt Nam 46% Quản trị rủi ro tài chính của doanh nghiệp Việt Nam 46% Phân tích đặc điểm địa hoá và thạch học của đá mẹ than và sét than trầm tích miocen khu vực phía bắc bể trầm tích sông Hồng 45% Một thuật toán phân cụm K-Means tăng cường cho phân đoạn ảnh đa phổ không giám sát 45% 7. KẾT LUẬN Trong bài báo này, chúng tôi đã đề xuất cải tiến độ đo tương tự giữa hai văn bản dựa trên luật mờ. Luật mờ được xây dựng để sinh ra trọng số ảnh hưởng theo loại đặc trưng. Kết quả cho thấy độ đo cải tiến áp dụng tốt cho việc so sánh văn bản tiếng Việt. Ngoài ra, chúng tôi áp dụng độ đo cải tiến trong việc tìm kiếm văn bản trùng lặp. Trong nghiên cứu tiếp theo, chúng tôi dự kiến phân tích nghiên cứu sâu hơn về vai trò, vị trí của đặc trưng trong câu để đưa ra mức độ ảnh hưởng theo ngữ cảnh cụ thể. 114 TRNG I HC TH H NI TÀI LIỆU THAM KHẢO 1. A.Z. Broder, S.C. Glassman, M.S. Manasse, G. Zweig (1997), "Syntactic Clustering of the Web", Computer Network. 2. E. Uyar (2009), Near-duplicate news detection using name entities. 3. M.A. Hearst (2006), "Clustering versus faceted categories for information exploration", In Communications of the ACM. 4. Muneer K., Syed Farook K (2014), "An Innovative Approach for Clustering of Web Pages Based on Transduction", International Journal of Advanced Research in Computer Science & Technology IJARCST, Vol. 2, Issue 3, pp. 241-244. 5. Xuemin Lin Chuan Xiao (2008), "Efficient similarity joins for near duplicate detection", In 17th International conference on World Wide Web. 6. Phạm Kim Hồng (2013), Phát hiện sự trùng lặp nội dung của các bài báo, Luận văn Thạc sĩ. 7. Lê Mạnh Hùng (2012), Tra cứu văn bản tiếng Việt dựa trên kĩ thuật phân cụm, Luận văn Thạc sĩ. 8. Dương Thăng Long, Báo cáo đề tài nghiên cứu: Nghiên cứu độ đo tương tự trong văn bản tiếng Việt và ứng dụng đánh giá việc sao chép bài điện tử. 9. Nguyễn Tuấn Anh (2009), Phát hiện trùng lặp văn bản và và xây dựng chỉ mục hiệu quả cho WebCrawler, Luận văn Thạc sĩ. 10. =KMeans.clustering. 11. Valliammal N., S.N.Geethalakshmi (2012), "Leaf Image Segmentation Based On the Combination of Wavelet Transform and K Means Clustering", International Journal of Advanced Research in Artificial Intelligence, Vol. 1, No.3. 12. R. H. Haralick, and L. G. Shapiro (1985), "Image segmentations techniques", Computer Vision Graphics Image Processing 29, pp.100-132. 13. J. Liu, and Y. H. Yang (1994), "Multiresolution color image segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.16, no.7, pp.689-700. AN APPROACH TO ASSESS DUPLICATION LEVEL OF TEXT USING FUZZY WEIGHT Abstract: Content duplication of text is a common issue of newspapers, news websites and publications. Duplication detecting is essential. Essence of this work is checking the similarity of documents. However, this is the complex problem and being interested in research. Presently, there are many researching methods to solve this problem. In this paper, we propose an improvement of similarity measure, which is based on fuzzy logic and applied it in duplication detecting of article content. Keywords: Text, duplication detecting, similarity measure
File đính kèm:
- mot_tiep_can_danh_gia_do_trung_lap_van_ban_su_dung_trong_so.pdf