Đánh giá mức độ giống nhau của văn bản tiếng việt

Nội dung tài liệu: Đánh giá mức độ giống nhau của văn bản tiếng việt

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG HỒ PHAN HIẾU ĐÁNH GIÁ MỨC ĐỘ GIỐNG NHAU CỦA VĂN BẢN TIẾNG VIỆT Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số : 62 48 01 01 TĨM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Đà Nẵng - 2019
2. Cơng trình được hồn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: 1. PGS.TS. Võ Trung Hùng 2. TS. Nguyễn Thị Ngọc Anh Phản biện 1: . Phản biện 2: . Phản biện 3: . Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Đại học Đà Nẵng Vào hồi giờ ngày tháng năm 2019 Cĩ thể tìm hiểu luận án tại: - Thư viện quốc gia Việt Nam. - Trung tâm Thơng tin - Học liệu & Truyền thơng, Đại học Đà Nẵng.
3. 1 MỞ ĐẦU 1. Đặt vấn đề Ngày nay, cùng với sự phát triển của Internet, hoạt động trao đổi, chia sẻ tài liệu diễn ra rất phổ biến. Các tài liệu như bài báo, sách, luận văn tốt nghiệp, báo cáo, được số hĩa và phổ biến trên mạng Internet ngày càng nhiều. Tuy nhiên, bên cạnh ưu điểm là cung cấp một nguồn tài liệu tham khảo phong phú thì tình trạng “sao chép” cũng đang trở thành một vấn nạn. Vấn đề đặt ra là làm thế nào để đánh giá được mức độ giống nhau của văn bản và chỉ ra được những nội dung sao chép trên một văn bản, đặc biệt đối với tiếng Việt. Để phát triển hệ thống phát hiện sao chép cần giải quyết các vấn đề chính như: 1) Xây dựng kho dữ liệu đủ lớn, cĩ độ bao phủ cao; 2) Cĩ phương pháp biểu diễn văn bản phù hợp và hiệu quả cho quá trình so sánh; 3) Các giải thuật để tính độ tương tự giữa các đơn vị văn bản và chỉ ra các nội dung sao chép; 4) Xử lý cho khối lượng văn bản cực lớn. Nhằm gĩp phần giải quyết các vấn đề trên, tơi đã chọn đề tài: “Đánh giá mức độ giống nhau của văn bản tiếng Việt” làm nội dung nghiên cứu cho luận án Tiến sĩ kỹ thuật của mình với mục tiêu phát hiện các nội dung sao chép trên một văn bản hiệu quả nhất cĩ thể. Ý tưởng nổi bật của luận án này là nghiên cứu, ứng dụng những thành tựu đã đạt được trong lĩnh vực sinh học, xử lý tín hiệu số vào lĩnh vực xử lý ngơn ngữ tự nhiên. Điểm chung của các lĩnh vực này là khối lượng dữ liệu cần xử lý rất lớn và mục đích là chỉ ra được sự giống nhau hoặc khác biệt giữa các đơn vị dữ liệu cần xử lý. Cụ thể, luận án đề xuất một hướng tiếp cận mới trong xử lý văn bản bằng cách áp dụng phương pháp biến đổi Wavelet rời rạc (DWT) và ứng
4. 2 dụng bộ lọc Haar để chuyển văn bản thành các chuỗi số DNA; tổ chức lưu trữ và đề xuất các giải thuật so sánh, tìm kiếm hiệu quả trong xử lý dữ liệu lớn để phát hiện và đánh giá được mức độ giống nhau trên các chuỗi DNA này. Đây là một hướng nghiên cứu mới, đầy tiềm năng để giải quyết bài tốn về xử lý văn bản và dữ liệu lớn. 2. Mục tiêu nghiên cứu Mục tiêu của luận án là tìm ra các giải pháp hiệu quả để biểu diễn, đánh giá mức độ giống nhau của các đơn vị văn bản và áp dụng cho việc phát hiện sao chép. Các mục tiêu cụ thể của luận án gồm: - Đề xuất được phương pháp hiệu quả trong biểu diễn văn bản để phục vụ tốt nhất cho quá trình phát hiện sao chép văn bản. - Đề xuất các giải thuật nhằm cải thiện tốc độ và độ chính xác để phát hiện sao chép khi xử lý dữ liệu lớn. - Xây dựng hệ thống phát hiện sao chép văn bản tiếng Việt và ứng dụng thử nghiệm tại ĐHĐN. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận án bao gồm các nội dung: - Các mơ hình, phương pháp biểu diễn văn bản. - Các phương pháp, thuật tốn tính độ tương tự văn bản. - Bài tốn phát hiện nội dung sao chép trên văn bản. - Các hệ thống phát hiện sao chép văn bản. Giới hạn phạm vi nghiên cứu trong luận án này gồm: - Tập trung vào phương pháp biểu diễn văn bản dựa trên mơ hình vector. Nghiên cứu một số mơ hình, phương pháp biểu diễn văn bản, chuyển văn bản thơ thành kho dữ liệu dựa trên mơ hình vector. - Nghiên cứu đề xuất các thuật tốn tính độ tương tự văn bản.
5. 3 Luận án chỉ tính tốn độ tương tự văn bản dựa trên các phương pháp liên quan đến chuỗi, mà khơng xét đến yếu tố ngữ nghĩa của văn bản. - Đề xuất giải pháp tính độ tương tự văn bản tiếng Việt và triển khai thử nghiệm tại ĐHĐN. 4. Phương pháp nghiên cứu - Phương pháp tài liệu: Nghiên cứu các tài liệu cĩ liên quan đến các nội dung nghiên cứu như: Khai phá văn bản, biểu diễn và lưu trữ văn bản; một số đặc trưng cơ bản của tiếng Việt; hệ thống phát hiện sao chép văn bản, độ tương tự văn bản, phát hiện sao chép tại PAN; DWT và bộ lọc Haar; tìm kiếm nhị phân, xử lý dữ liệu lớn. - Phương pháp thực nghiệm: Nghiên cứu đánh giá thực nghiệm các mơ hình, phương pháp so khớp văn bản trong phát hiện sao chép. Xây dựng các chương trình so khớp văn bản. So sánh, đánh giá kết quả các phương pháp đề xuất với một số phương pháp đã cĩ. Cuối cùng, phát triển hệ thống thực nghiệm tại ĐHĐN và đánh giá kết quả. 5. Nhiệm vụ nghiên cứu và kết quả đạt được Để đạt được mục tiêu đề ra, nhiệm vụ nghiên cứu tập trung vào các vấn đề chính sau đây: - Nghiên cứu, phân tích các phương pháp biểu diễn văn bản nĩi chung và mơ hình vector nĩi riêng, từ đĩ đề xuất các thuật tốn để so sánh, đánh giá và phát triển ứng dụng cụ thể. - Khảo sát các nguồn dữ liệu, tổng hợp tài liệu số, đề xuất giải pháp tổ chức lưu trữ, đánh chỉ mục, biểu diễn dữ liệu phù hợp. - Nghiên cứu bài tốn so sánh văn bản để phát hiện sao chép tại PAN, đề xuất giải pháp xử lý phát hiện sao chép văn bản hiệu quả. - Nghiên cứu lý thuyết về DWT và bộ lọc Haar trong xử lý tín hiệu số, đề xuất giải pháp để chuyển văn bản thành chuỗi số DNA.
6. 4 - Nghiên cứu đề xuất giải thuật xử lý thơng qua bộ lọc Haar, giải pháp tổ chức lưu trữ DNA phù hợp, đề xuất thuật tốn phát hiện sự giống nhau. - Nghiên cứu xây dựng bộ dữ liệu tiếng Việt thử nghiệm để phục vụ đánh giá. - Triển khai thực nghiệm và đánh giá kết quả. 6. Bố cục của luận án Trên cơ sở các nội dung nghiên cứu, để đạt mục tiêu đề ra và đảm bảo tính logic, ngồi phần mở đầu và phần kết luận, luận án được tổ chức thành các chương như sau: Chương 1: Tổng quan tình hình nghiên cứu. Chương này trình bày cơ sở lý thuyết, kết quả nghiên cứu tổng quan về các vấn đề nghiên cứu trong luận án. Trên cơ sở các phân tích, đánh giá sẽ định hướng, đề xuất và xác định các nội dung nghiên cứu được triển khai. Chương 2: So sánh văn bản dựa trên mơ hình vector. Chương này trình bày phương pháp tính trọng số các đặc trưng của văn bản biểu diễn trên mơ hình vector; thực nghiệm một số phương pháp so sánh văn bản dựa trên mơ hình vector. Trên cơ sở phân tích, đánh giá, luận án đề xuất thuật tốn thử nghiệm để đánh giá sự tương tự của văn bản tiếng Việt dựa trên mơ hình vector. Chương 3: Phát hiện sao chép văn bản dựa trên biến đổi Wavelet rời rạc. Chương này giới thiệu kết quả nghiên cứu, phân tích và đề xuất hướng tiếp cận mới để giải quyết bài tốn so sánh văn bản dựa trên DWT và sử dụng bộ lọc Haar. Nội dung trình bày tập trung vào phương pháp đề xuất dựa trên DWT và bộ lọc Haar để giải quyết bài tốn. Thực nghiệm, so sánh và đánh giá kết quả đạt được để chứng minh phương pháp đề xuất đạt hiệu quả cao.
7. 5 Chương 4: Phát triển hệ thống phát hiện sao chép văn bản tiếng Việt. Trình bày kết quả giải pháp xây dựng kho dữ liệu văn bản tiếng Việt và phát triển hệ thống phát hiện sao chép văn bản dựa trên các kết quả nghiên cứu đạt được về mơ hình vector và phương pháp DWT. Kết quả triển khai thử nghiệm tại ĐHĐN và một số nhận xét, đánh giá. 7. Đĩng gĩp chính của luận án Luận án đã gĩp phần giải quyết bài tốn đánh giá mức độ giống nhau của văn bản để phát hiện nội dung giống nhau của văn bản nhằm phát hiện sao chép. Những đĩng gĩp chính của luận án: - Đề xuất cải tiến mơ hình vector sử dụng độ đo Cosine để tính tốn độ tương tự văn bản dựa trên đơn vị từ và câu. - Đề xuất được cách tiếp cận mới để đánh giá mức độ giống nhau của văn bản gồm phương pháp biểu diễn văn bản thành các chuỗi số thực DNA và ứng dụng phương pháp DWT và bộ lọc Haar. - Đề xuất quy trình xử lý, xây dựng thuật tốn phát hiện sự giống nhau giữa các văn bản bằng cách tính tốn khoảng cách Euclid nhỏ nhất từ DNA cần đánh giá đến các DNA nguồn và so sánh với một mức ngưỡng thích hợp để đưa ra kết luận về sự giống nhau. - Đề xuất được các giải pháp, thuật tốn để xử lý dữ liệu lớn hiệu quả với việc mã hĩa dữ liệu văn bản sang dạng tín hiệu số thơng qua các chuỗi DNA được sắp xếp theo thứ tự tăng dần cho phép tìm kiếm nhị phân. - Xây dựng các bộ dữ liệu tiếng Việt để thực nghiệm, xây dựng hệ thống phát hiện sao chép văn bản và triển khai ứng dụng thử nghiệm tại ĐHĐN mang ý nghĩa thực tiễn cao.
8. 6 CHƯƠNG 1. TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU 1.1. Một số khái niệm sử dụng trong luận án Trình bày một số khái niệm liên quan sử dụng trong luận án như: Văn bản (Document/Text), độ tương tự (Similarity measures), độ tương tự văn bản (Text similarity), so khớp văn bản (Text alignment), đạo văn (Plagiarism), phát hiện sao chép (Copy detection), kho ngữ liệu (Corpus), các độ đo tính tốn hiệu năng (Precision, Recall, F-score). 1.2. Mơ hình biểu diễn văn bản Trong xử lý văn bản cĩ rất nhiều phương pháp cĩ cách tính tốn khác nhau, nhưng nhìn một cách tổng quan thì các phương pháp đĩ thường khơng tương tác trực tiếp trên tập dữ liệu thơ ban đầu, mà cần phải thực hiện tiền xử lý (như tách câu, tách từ, xử lý chữ viết hoa/chữ thường, loại bỏ từ dừng ) và chọn mơ hình biểu diễn văn bản phù hợp để xử lý, tính tốn gọi là mơ hình hĩa văn bản. Biểu diễn văn bản cĩ thể chia thành hai hướng tiếp cận chính, đĩ là: Hướng thống kê và hướng ngữ nghĩa. Trong tiếp cận theo hướng thống kê, các văn bản được biểu diễn theo một số tiêu chí phục vụ đo lường dựa trên thống kê, trong khi các phương pháp theo hướng ngữ nghĩa liên quan đến khái niệm và phân tích cú pháp. Luận án đã khảo sát và trình bày những nội dung cơ bản cũng như những nhận xét, đánh giá về các mơ hình biểu diễn văn bản như: Mơ hình Boolean, mơ hình khơng gian vector (VSM), mơ hình túi từ (bag of words), mơ hình chỉ mục ngữ nghĩa tiềm ẩn (LSI), dựa trên khái niệm mờ (fuzzy), mơ hình đồ thị, mơ hình n-gram, phương pháp chiếu ngẫu nhiên, mơ hình phân tích cú pháp, biểu diễn Tensor.
9. 7 1.3. Các phương pháp tính độ tương tự văn bản Qua khảo sát cĩ thể chia các nghiên cứu về phương pháp tính độ tương tự văn bản thành ba hướng tiếp cận chính theo phương pháp dựa trên chuỗi (String-Based) xác định sự giống nhau về mặt hình thức (từ, câu); phương pháp dựa trên tập dữ liệu (Corpus-Based) và dựa trên tri thức (Knowledge-Based) sẽ xác định sự giống nhau về mặt ngữ nghĩa của từ [39, 75]. Luận án trình bày một số thuật tốn điển hình để giải quyết bài tốn so khớp chuỗi như: Brute-Force, Nạve, Morris-Pratt, Knuth- Morris-Pratt (KMP), Boyer-Moore, Rabin-Karp, Horspool [27, 118, 133]. Những thuật tốn này tập trung vào vấn đề so sánh hai chuỗi ký tự bất kỳ và phát hiện sự giống nhau giữa chúng. Với một số trường hợp trong so khớp văn bản, việc đo độ tương tự giữa hai đoạn văn bản là việc sử dụng so khớp từ đơn giản. Vì vậy, luận án nghiên cứu các thuật tốn so khớp chuỗi để làm nền tảng cho việc tính tốn độ tương tự văn bản và so sánh hiệu quả của phương pháp đề xuất dựa trên độ phức tạp tính tốn. 1.4. So sánh văn bản và ứng dụng trong phát hiện sao chép Bài tốn so sánh văn bản thực chất là tính tốn được mức độ giống nhau hay độ tương tự của văn bản. Với mục đích nghiên cứu là đánh giá mức độ giống nhau của văn bản để ứng dụng trong phát hiện sao chép, luận án tập trung nghiên cứu theo hướng giải quyết bài tốn so sánh văn bản theo dạng so khớp chuỗi mà khơng đi sâu về mặt ngữ nghĩa cũng như khơng đề cập sâu về các hình thức sao chép như: dạng cấu trúc, ý tưởng, tự sao chép, trích dẫn khơng phù hợp Bài tốn phát hiện sao chép hầu hết là kiểu phát hiện các văn bản gần trùng lặp nên đây là một vấn đề khĩ và các dạng trùng lặp là
10. 8 vơ cùng đa dạng. Chính vì sự đa dạng trong việc sao chép văn bản mà khơng thể cĩ một giải thuật hay kỹ thuật nào đo được một cách chính xác sự giống nhau giữa các văn bản. Bài tốn này tuy khơng phải là mới, nhưng ở Việt Nam vẫn chưa cĩ những nghiên cứu và ứng dụng rõ ràng được cơng bố. Qua quá trình nghiên cứu, khảo sát và đánh giá, luận án tổng hợp các phương pháp, kỹ thuật so sánh văn bản và phát hiện sao chép cĩ thể được phân loại gồm: Các phương pháp dựa trên ký tự (Character-based methods), dựa trên tần suất (Frequency-based methods), dựa trên cấu trúc (Structural-based methods), dựa trên phân lớp và gom cụm (Classification and Cluster-based methods), dựa trên cú pháp (Syntax-based methods), phát hiện gần trùng lặp (Near Dupplicate Detection), dựa trên ngữ nghĩa (Semantic-based methods), dựa trên trích dẫn (Citation-based methods), kế thừa văn bản (Recognizing Textual Entailment). Phát hiện sao chép tại PAN Một mơ hình tổng quát cho quá trình xử lý để phát hiện sao chép đã được đề xuất trong các giải pháp cĩ hiệu quả cao tại PAN. Hình 1.4. Mơ hình xử lý tổng quát để phát hiện sao chép [124]
11. 9 Với một tài liệu nghi ngờ (Suspicious document), quá trình tìm kiếm để phát hiện sao chép sẽ thực hiện tìm kiếm, kiểm tra trên một tập dữ liệu rất lớn (Document collection). Quá trình thực hiện này gồm ba bước chính: - Bước 1: Lọc ra (Source retrieval) các tài liệu tiềm năng bị sao chép (Candidate documents): Chọn một nhĩm nhỏ các tài liệu ứng viên được xem là sao chép (Suspicious document) từ tập tài liệu lớn hay là kho dữ liệu (Document collection). Các tài liệu ứng viên là các tài liệu được xác định cĩ khả năng cao là nguồn của đạo văn liên quan đến tài liệu nghi ngờ. - Bước 2: So khớp văn bản (Text alignment): So sánh tài liệu nghi ngờ với từng tài liệu ứng viên và trích xuất các đoạn tương tự từ mỗi cặp tài liệu này. - Bước 3: Hậu xử lý (Knowledge-based post-processing): Xử lý, trình bày và so khớp từng đoạn sao chép (Suspicious passage) trên một giao diện phù hợp nhằm giúp cho người sử dụng cĩ thể xử lý các tác vụ về sau. Trên đây là các bước chính, tuy nhiên để hệ thống phát hiện sao chép văn bản cĩ thể sử dụng được trong thực tiễn thì phải cĩ giải pháp thích hợp cho việc tạo lập và duy trì chỉ mục của tất cả tài liệu trong tập tài liệu nguồn cũng như cĩ mơ hình tính tốn phù hợp để đáp ứng hiệu năng về độ chính xác và thời gian. Qua kết quả đạt được tại PAN, chúng ta thấy rằng việc phát hiện các văn bản giống nhau khĩ đạt kết quả tuyệt đối. Vì vậy, đây cũng chính là cơ sở để luận án tiếp tục nghiên cứu giải quyết bài tốn theo hướng chủ đề này.
12. 10 CHƯƠNG 2. SO SÁNH VĂN BẢN DỰA TRÊN MƠ HÌNH VECTOR 2.1. Phương pháp tính trọng số từ khĩa Phương pháp TF-IDF dựa trên mức độ quan trọng của mỗi từ trong tài liệu để thống kê. Phương pháp này thường được sử dụng nhiều nhất để tính trọng số các đặc trưng, giá trị của ma trận trọng số được tính theo các cơng thức sau: N tf(t,d) = t,d (2.1) Nd N idf(t,D) =1 + ln( ) (2.3) n TF-IDF(t,d,D) = tf(t,d) idf(t,D) (2.4) Theo phương pháp TF-IDF, trọng số từ là tích của tần suất từ (TF) và tần suất tài liệu nghịch đảo của từ đĩ (IDF). Trọng số được tính bằng tần suất xuất hiện của từ khĩa t trong văn bản d và độ hiếm của từ khĩa t trong tồn bộ tập văn bản. Như vậy, việc áp dụng mơ hình vector để biểu diễn văn bản thì mỗi văn bản được mơ hình hĩa thành một vector đặc trưng và khơng gian các đặc trưng của tất cả các văn bản đang xét sẽ bao gồm tất cả các từ. Ví dụ: Mơ hình hĩa 1.000 văn bản/tài liệu. Tách được 9.500 từ từ tập các văn bản này. Sau khi loại bỏ các từ dừng thì cịn lại 8.235 từ. Mơ tả cho việc mơ hình hĩa này bằng một ma trận 1.000 hàng (văn bản) và 8.235 cột (từ). Với mỗi ơ giao nhau của hàng và cột, tính một giá trị gọi là trọng số của hàng và cột tương ứng theo phương pháp TF-IDF như cơng thức 2.1, 2.3, 2.4.
13. 11 2.2. Một số phương pháp so sánh văn bản dựa trên mơ hình vector Để tính giá trị đặc trưng cho văn bản, luận án thực hiện bằng phương pháp TF-IDF. Trong luận án sử dụng các độ đo dựa vào thống kê tần suất xuất hiện của từ trong văn bản và xác định độ tương tự văn bản bằng cách: 1) Tính gĩc của những vector sử dụng độ đo Cosine và hệ số Jaccard; 2) Dựa trên tính khoảng cách giữa các điểm bằng độ đo khoảng cách Manhattan và Levenshtein. Các bước xử lý chính như sau: - Bước 1: Tiền xử lý (Tách từ đơn, loại bỏ từ dừng, tạo danh sách từ vựng ). - Bước 2: Xây dựng tập từ vựng chung T = {t1, t2 , tn} - Bước 3: Mơ hình hĩa văn bản thành vector: Dựa vào T ta tạo vector a và b với trọng số các từ của A và B lần lượt là ai, bj (bằng cách tính TF-IDF) - Bước 4: Áp dụng cơng thức tính độ tương tự theo các độ đo. - Bước 5: Hiển thị kết quả. Phương pháp cải tiến sử dụng độ đo Cosine Luận án đề xuất các thuật tốn tính tốn độ tương tự văn bản dựa trên mơ hình vector theo đơn vị từ và câu, cĩ xét đến yếu tố trật tự của từ để cĩ thể tăng độ chính xác về ý nghĩa của văn bản. So sánh hai phương pháp này dựa trên kết quả thực nghiệm trên bộ dữ liệu tiếng Việt từ các luận văn tốt nghiệp để chứng minh phương pháp đề xuất cĩ thể tính tốn độ tương tự của văn bản tiếng Việt và cĩ những nhận xét để làm tiền đề cho các nghiên cứu và đề xuất tiếp theo.
14. 12 Luận án áp dụng độ đo Cosine để tính độ tương tự giữa hai văn bản (văn bản truy vấn và văn bản nguồn), đĩ chính là gĩc giữa hai vector a và b, được tính theo cơng thức sau: n ab ab  ii Sim(a , b ) = i 1 (2.5) nn ab 22 abii ii 11 Thay đổi trật tự từ trong câu ảnh hưởng đến ý nghĩa của câu: Ta cĩ cơng thức tính độ tương tự của thứ tự từ giữa hai vector [1, 46]: m 2 r - r r - r  ia ib ab i 1 Sim (ab , ) 1 1 (2.11) R m rab + r 2  ria + r ib i 1 Trong đĩ: ra là vector thứ tự các từ trong văn bản a, rb là vector thứ tự các từ trong văn bản b, m là số từ chung trong hai văn bản, ria là thứ tự của từ i trong văn bản a, rib là thứ tự của từ i trong văn bản b. Độ tương tự nội dung đại diện cho sự giống nhau về mặt từ vựng, cịn độ tương tự về thứ tự các từ tương tự cung cấp thơng tin về mối quan hệ giữa các từ. Những từ xuất hiện trong câu hoặc đứng trước hoặc đứng sau các từ khác đều đĩng vai trị truyền đạt ý nghĩa của câu. Vì thế, độ đo giống nhau về tồn bộ văn bản là sự kết hợp giữa độ đo tương tự về mặt nội dung và thứ tự của từ trong văn bản. Luận án áp dụng cơng thức tính như sau: ab rab - r S(a , b )  Sim( a , b ) (1  )Sim ( a , b )  + (1  ) R ab (2.12) rab + r
15. 13 Qua nghiên cứu tính tốn độ tương tự văn bản dựa trên mơ hình vector với phương pháp đánh trọng số TF-IDF bằng cách sử dụng các độ đo Cosine, Jaccard, Manhattan, Levenshtein. Trong luận án đã cải tiến và đề xuất phương pháp so sánh văn bản dựa trên mơ hình vector sử dụng độ đo Cosine với đơn vị là từ và câu với việc tính tốn các trọng số từ và câu, dựa trên trật tự từ. 2.3. Đánh giá các phương pháp dựa trên mơ hình vector Luận án đã tạo ra các bộ dữ liệu để đánh giá các thuật tốn và xây dựng một ứng dụng với các chức năng như: Tiền xử lý văn bản, vector hĩa, so khớp, hiển thị kết quả và vẽ biểu đồ. Kết quả thực nghiệm cho thấy phương pháp dựa trên vector và các độ đo tương tự phổ biến như đã đề cập ở trên cĩ thể giải quyết được mục tiêu bài tốn là đánh giá độ tương tự các văn bản. Tuy nhiên, với phương pháp đề xuất này thì độ chính xác cũng chưa cao. Bên cạnh đĩ, phương pháp biểu diễn theo vector vẫn cịn hạn chế về số chiều biểu diễn cho tập văn bản sẽ rất lớn nên tốn khơng gian lưu trữ, độ phức tạp của thuật tốn khi so sánh tăng và làm giảm tốc độ tính tốn. Với những nội dung nghiên cứu đạt được ở Chương này, chúng tơi ứng dụng mơ hình biểu diễn vector một cách phù hợp nhất trong phạm vi nghiên cứu của luận án, đĩ là biểu diễn các DNA theo mơ hình vector và sử dụng độ đo khoảng cách Euclid giữa các vector để tính độ tương tự. Những nội dung liên quan được đề cập trong Chương 3.
16. 14 CHƯƠNG 3. PHÁT HIỆN SAO CHÉP VĂN BẢN DỰA TRÊN BIẾN ĐỔI WAVELET RỜI RẠC 3.1. Đặt vấn đề Luận án đề xuất ý tưởng để chuyển văn bản thành chuỗi tín hiệu số và xử lý, tính tốn, so khớp trên dữ liệu này. Để áp dụng trong việc đánh giá mức độ giống nhau của văn bản, những thách thức lớn đặt ra đĩ là: 1) Nghiên cứu để tìm cách chuyển đổi văn bản thành tín hiệu số và đảm bảo đầy đủ nội dung thơng tin của văn bản; 2) Nghiên cứu sử dụng các phương pháp xử lý tín hiệu số phù hợp để tính tốn; 3) Nghiên cứu áp dụng các độ đo để tính tốn, lọc ra các tín hiệu bất thường để phát hiện các tín hiệu giống nhau; 4) Liên kết và truy xuất lại nội dung để đánh giá được mức độ giống nhau của các văn bản. 3.2. Cơ sở lý thuyết về DWT và bộ lọc Haar Trình bày cơ sở lý thuyết về phép biến đổi Wavelet rời rạc (DWT), bộ lọc Haar và chuỗi số DNA. Việc nghiên cứu sử dụng bộ lọc Haar trong DWT để biến đổi tín hiệu chuỗi thời gian thực thành các chuỗi số DNA để tính tốn, xử lý và lọc tín hiệu là hướng tiếp cận mới để giải quyết bài tốn cĩ tính khả thi, giải quyết được bài tốn dữ liệu lớn và mang lại hiệu quả cao. 3.3. Đề xuất mơ hình hệ thống phát hiện sao chép Luận án đề xuất mơ hình tổng quan và thiết kế các khối cho hệ thống phát hiện sao chép văn bản. Trong giai đoạn tiền xử lý, văn bản thu thập sẽ được phân đoạn và lấy mẫu sao cho các mẫu cĩ độ dài bằng nhau. Sau đĩ, các phân đoạn này được lưu trữ như là dữ liệu thơ nhằm mục đích trích xuất các đoạn văn bản giống nhau (nếu cĩ). Trong giai đoạn xử lý chính, các văn bản sẽ được số hĩa và cho qua
17. 15 bộ lọc Haar để thu được dữ liệu cho bộ DNA nguồn. Trong khi đĩ, văn bản đánh giá được cho qua bộ mã hĩa để xử lý. Văn bản đánh giá thơ được tạo thành sau quá trình tiền xử lý sẽ được phân đoạn. Sau đĩ, từng phân đoạn trong văn bản đánh giá được mã hĩa thành một DNA nhằm mục đích phát hiện sự giống nhau (nếu cĩ) của phân đoạn đĩ với một phân đoạn khác thuộc bộ dữ liệu nguồn. Hình 3.6 mơ tả chi tiết quá trình xử lý để đánh giá văn bản kiểm tra so với tập văn bản nguồn (kho dữ liệu). Hình 3.6. Quá trình xử lý để đánh giá văn bản cần kiểm tra
18. 16 3.4. Đề xuất quy trình chuyển đổi dữ liệu Thuật tốn 3.1. Quy trình mã hĩa văn bản thành chuỗi tín hiệu số DNA Đầu vào: Văn bản Đầu ra: Chuỗi số DNA Xử lý: Mã hĩa văn bản thành chuỗi tín hiệu số 1 - Tiền xử lý (loại bỏ các dấu câu, ký tự đặc biệt, đánh chỉ mục và lưu trữ dưới dạng dữ liệu thơ ) 2 - Số hĩa nhằm chuyển dữ liệu thơ thành dạng chuỗi số 3 - Xử lý qua bộ lọc Haar để mã hĩa thành các DNA 3.5. Đề xuất phương pháp và giải thuật xử lý Trong phần này sẽ phân tích chi tiết nhiệm vụ của từng khối trong quá trình xử lý được thực hiện qua các giai đoạn như sau: Tiền xử lý sẽ loại bỏ các ký tự đặc biệt và chia văn bản thành các phân đoạn. Quá trình số hĩa sẽ chuyển đổi các từ trong từng phân đoạn thành một số thực đặc trưng trước khi đưa đến bộ lọc Haar để lấy mẫu cho việc tính tốn các DNA nhằm phục vụ cho việc so sánh mức độ giống nhau của văn bản kiểm tra và các văn bản trong kho dữ liệu. Giải thuật cho bộ lọc Haar Tín hiệu vào bộ lọc là các chuỗi số rời rạc gồm N = 2K số thực. Một phép biến đổi Haar rời rạc được thực hiện qua K bước lặp và tại lần lặp thứ k (hay mức thứ k), với k = 1,2 ,K; tín hiệu đầu ra của phép biến đổi được mơ tả như sau: (k ) ( k ) ( k ) ( k 1) x x x x (3.12) low high c (k) (k) trong đĩ, các hệ số xấp xỉ x và hệ số chi tiết x được cho bởi low high cơng thức lấy mẫu con như sau:
19. 17 (k) x  x(k-1)* f 2, (3.13) low a L ()k x  x(k 1)* f 2, (3.14) high a H với f = 1 1 và f =  1 1 lần lượt là đáp ứng bộ lọc thơng thấp và L H (k 1) (k 1) thơng cao; x và x tương ứng là các hệ số xấp xỉ của bước a c thứ (k-1) và tổng hợp các hệ số chi tiết của chuỗi tín hiệu thu được tại các bước trước đĩ. Tại điểm khởi tạo, x(0) và x(0) được cho như sau: a c (0) (0) xx= , (3.15) a x(0)= [], (3.16) c trong đĩ, x(0) là chuỗi tín hiệu ban đầu (vector x sau khi được số hĩa) (k) 1 Nk ( ) Kk và [] là vector rỗng. Các giá trị x a , với N ()k 2 , a a ()k 1 Nkc ( ) k Ki x và N ()k 2 , k = 1,2 ,K sẽ được cập nhật c c i 1 theo cơng thức sau: xx()()kk , (3.17) a low ()k ()k (k 1) x x x . (3.18) c high c K kk K i K Cĩ thể chứng minh NNN()()kk 2 2 2 , k = ac i 1 1,2 ,K. Qua đĩ, tín hiệu sau K bước lặp vẫn cĩ độ dài N như ban đầu. Thực chất, các phân đoạn văn bản khác nhau sau khi được số hĩa và qua bộ lọc Haar sẽ cho ra các chuỗi số mang thơng tin đặc trưng cĩ thể phân biệt được mức độ khác nhau giữa chúng. Do đĩ, các chuỗi tín hiệu sau bộ lọc được gọi là các DNA. Cuối cùng luận án phát triển một thuật tốn theo phân tích ở trên như sau:
20. 18 Thuật tốn 3.2. Xác định giá trị cho các chuỗi DNA Đầu vào: Tập chuỗi số thực. Đầu ra: Chuỗi số thứ K chính là DNA cần tính. Khởi tạo: Các vector xấp xỉ và hệ số được cho bởi CT (3.15), (3.16) 1 For k:= 1 K 2 - Tính chuỗi số thứ k theo CT (3.12), (3.13) và (3.14) 3 - Cập nhật giá trị cho vector xấp xỉ và hệ số theo CT (3.17), (3.18) 4 Endfor Tổ chức dữ liệu cho bộ DNA nguồn Sau khi thực hiện các bước ở quy trình số hĩa, chúng ta sẽ cĩ được một bộ DNA cho tập các văn bản thu thập được. Sau đĩ, sắp xếp bộ DNA theo giá trị đầu tiên của DNA tăng dần để hệ thống cĩ thể thực hiện việc tìm kiếm nhị phân nhằm xác định DNA giống với DNA của một mẫu thuộc phân đoạn nào đĩ trong văn bản đánh giá. Qua đĩ cĩ thể cải thiện được độ phức tạp của thuật tốn đánh giá văn bản. Sở dĩ cĩ thể dùng giá trị đầu tiên của DNA làm khĩa sắp xếp vì đĩ chính là giá trị xấp xỉ hay tổng của các giá trị thành phần sau K bước lặp. Vì vậy, tại vị trí này nếu giá trị của hai mẫu DNA giống nhau, hai mẫu văn bản tương ứng với hai DNA này sẽ giống nhau. 3.6. Đề xuất thuật tốn phát hiện sự giống nhau Mã hĩa dữ liệu và tính DNA của văn bản đánh giá: Sau khi tiền xử lý văn bản đánh giá, chúng ta cĩ thể dễ dàng thực hiện quy trình mã hĩa dữ liệu văn bản đánh giá như đã trình bày ở phần trên. So sánh và đưa ra quyết định Ở khối cuối cùng của hệ thống sẽ so sánh từng nhĩm DNA của các phân đoạn với các DNA của tập dữ liệu nguồn được lưu trữ sẵn. Đối với mỗi mẫu DNA trong nhĩm DNA đưa vào khâu so sánh, sẽ tìm kiếm nhị phân trong kho dữ liệu để xác định DNA nguồn nào cĩ
21. 19 giá trị đầu tiên giống với DNA đang xét nhất. Tiếp theo, khoảng cách Euclid giữa hai DNA được tính rất đơn giản theo cơng thức sau: 2 (3.19) d x, y x y 2 1 N trong đĩ, x và y 1 N lần lượt là vector DNA nguồn và vector DNA đang xét. Khoảng cách Euclid này sẽ được so sánh với một mức ngưỡng ε. Nếu d(x, y)< ε, hai DNA xem là giống nhau và vị trí tương ứng với DNA đang xét được đánh dấu lại để hệ thống đưa ra quyết định sau khi tổng hợp tất cả các mẫu DNA của phân đoạn. Thuật tốn 3.4. Phát hiện sự giống nhau Đầu vào: Văn bản cần đánh giá. Đầu ra: Đưa ra các phân đoạn chứa các từ giống với các phân đoạn nguồn (nếu cĩ). Khởi tạo: Độ dài chuỗi DNA (N) và mức ngưỡng (ε) để so sánh. 1 Tiền xử lý, phân đoạn và lưu trữ dữ liệu để xuất kết quả. 2 For mỗi phân đoạn, cần thực hiện: 3 Số hĩa phân đoạn. 4 Lấy mẫu và xác định nhĩm DNA phân đoạn theo Thuật tốn 3.2. 5 For mỗi DNA y nào đĩ trong nhĩm, cần thực hiện: 6 - Tìm kiếm nhị phân trên kho DNA nguồn để tìm ra một DNA x sao cho giá trị đầu của chuỗi DNA y đang xét gần nhất với giá trị đầu của DNA x. 7 - Tính khoảng cách Euclid d(x, y) theo cơng thức (3.19). 8 If d(x, y)< ε then 9 Đánh dấu DNA y đang xét. 10 Endif 11 Endfor // kết thúc vịng lặp for dịng 5 12 Tổng hợp các DNA y đã đánh dấu (nếu cĩ) để thu được chuỗi các từ giống nhau của phân đoạn đang xét so với phân đoạn nguồn. 13 Endfor // kết thúc vịng lặp for dịng 2
22. 20 3.7. Kết quả thử nghiệm phương pháp dựa trên DWT Để kiểm tra kết quả của giải thuật đề xuất, luận án sử dụng các phép đo trong PAN [100] để tính các giá trị prec và rec. Luận án thực hiện thử nghiệm trên bộ dữ liệu của PAN năm 20091, gồm 7.214 tài liệu nguồn và 7.214 tài liệu kiểm tra, với dung lượng hơn 2.6 GB, thực hiện mỗi lần đánh giá 100 văn bản nghi ngờ hồn tồn khác với văn bản sử dụng để tìm ngưỡng ε phù hợp thơng qua kết quả đạt được của prec và rec. Kết quả đạt được theo các thơng số sau: Hình 3.8. Giá trị prec và rec đạt được qua các mức ngưỡng khác nhau Với kết quả trên, chúng ta nhận thấy rằng thuật tốn đề xuất cho kết quả prec và rec rất cao và ổn định (trên 97% đến 99%, với ngưỡng ε từ 10-7 đến 10-12). Trong luận án cũng đã thực nghiệm trên bộ dữ liệu tiếng Việt tự tạo đạt tỉ lệ chính xác rất cao và do nguồn dữ liệu tiếng Việt ít nên việc tìm kiếm rất nhanh và kết quả đạt được rất chính xác với nhiều mức ngưỡng ε khác nhau. Qua quá trình huấn luyện sẽ dể dàng tinh chỉnh các mức ngưỡng ε để đạt kết quả tốt nhất. 1
23. 21 CHƯƠNG 4. PHÁT TRIỂN HỆ THỐNG PHÁT HIỆN SAO CHÉP VĂN BẢN TIẾNG VIỆT 4.1. Mơ tả hệ thống Nhằm mục đích xây dựng kho dữ liệu và phát hiện sao chép văn bản, luận án đề xuất xây dựng một hệ thống với quy trình thực hiện như sau: Hình 4.1. Quy trình phát hiện sao chép 4.2. Xây dựng kho dữ liệu văn bản tiếng Việt Luận án đã đề xuất giải pháp và xây dựng hệ thống kho dữ liệu giải quyết vấn đề thực tế của ĐHĐN và cĩ độ bao phủ cao. Kết quả thử nghiệm, bước đầu chúng tơi đã cập nhật vào kho dữ liệu hơn 2.000 tài liệu thuộc 6 lĩnh vực theo quy định của Bộ Khoa học và Cơng nghệ và phân theo các thể loại để phục vụ mục đích thử nghiệm cho hệ thống phát hiện sao chép. Dữ liệu này, chúng tơi sẽ tiếp tục cập nhật từ các nguồn dữ liệu của ĐHĐN để phục vụ cho việc kiểm tra sau này.
24. 22 4.3. Triển khai hệ thống phát hiện sao chép văn bản Với những nghiên cứu đạt được, chúng tơi tiến hành phát triển hệ thống phát hiện sao chép văn bản thử nghiệm được đặt tại địa chỉ: Luận án đã đề xuất thuật tốn đánh dấu nội dung văn bản sao chép trực tiếp trên tập tin tài liệu cần kiểm tra. Thuật tốn 4.1. Đánh dấu và tơ màu văn bản Đầu vào: Văn bản (tập tin .doc hay .docx). Đầu ra: Văn bản cĩ đánh dấu, tơ màu các câu nghi ngờ sao chép và tham chiếu đến tài liệu nguồn bị sao chép. Xử lý: 1 n = CountSent(D1) //Số lượng câu của tập tin cần kiểm tra D1 2 For i:= 1 n 3 m = length(W) //Số lượng câu trong kho dữ liệu 4 Extract Si //Tách câu thứ i trong D1 5 Encode Si //Mã hĩa câu thứ i trong D1 thành DNA 6 For j:= 1 m 7 Sj = DNAj //DNA của câu thứ j trong W 8 If So_khop(Si, Sj) trùng nhau (90%-100%): Chèn note, tơ màu đỏ 9 If So_khop(Si, Sj) trùng nhau (70%-89%): Chèn note, tơ màu xanh 10 If So_khop(Si, Sj) trùng nhau (50%-69%): Chèn note, tơ màu vàng 11 Endfor // kết thúc vịng lặp for dịng 6 12 Endfor // kết thúc vịng lặp for dịng 2 Hình 4.7. Đánh dấu nội dung giống nhau trên tài liệu cần kiểm tra
25. 23 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. Kết luận Luận án đã nghiên cứu khá tồn diện về cách đo độ tương tự của văn bản và ứng dụng nĩ vào phát hiện sao chép. Kết quả thực hiện cĩ thể tĩm tắt như sau: - Đã khảo sát, nghiên cứu, phân tích, đề xuất những nội dung liên quan đến so khớp văn bản dựa trên mơ hình vector, kết quả thực nghiệm chứng minh phương pháp dựa trên mơ hình vector và sử dụng độ đo Cosine là phương pháp thơng dụng cĩ thể giải quyết được bài tốn tính độ tương tự văn bản. - Đề xuất quy trình số hĩa văn bản bằng cách chuyển văn bản thành các chuỗi số thực DNA dựa trên phương pháp DWT và bộ lọc Haar. Đây là một cách tiếp cận hồn tồn mới để giải quyết bài tốn. - Đề xuất quy trình xử lý, xây dựng thuật tốn phát hiện sự giống nhau giữa các văn bản bằng cách tính tốn khoảng cách Euclid nhỏ nhất từ DNA cần đánh giá đến các DNA nguồn và so sánh với một mức ngưỡng thích hợp để đưa ra sự giống nhau giữa văn bản được kiểm tra với văn bản nguồn trong kho dữ liệu. Các kết quả thực nghiệm trên bộ dữ liệu chuẩn của PAN và bộ dữ liệu tiếng Việt thử nghiệm đã chứng minh thuật tốn được đề xuất trong luận án đã đem lại hiệu quả cao trong phát hiện sự giống nhau của văn bản. - Đã hướng đến xử lý dữ liệu lớn một cách hiệu quả với việc mã hố dữ liệu văn bản sang chuỗi DNA, tổ chức lưu trữ theo dạng vector được sắp xếp theo thứ tự tăng dần cho phép tìm kiếm nhị phân, vì đây là một trong những phương pháp tìm kiếm nhanh nhất khi làm việc với dữ liệu lớn. Hơn nữa, DWT cho độ phức tạp tính
26. 24 tốn chỉ là hàm tuyến tính trong mỗi lần lấy mẫu con nên giải pháp đề xuất sẽ càng hiệu quả trong quá trình xử lý dữ liệu lớn. - Thực nghiệm xây dựng kho dữ liệu và hệ thống phát hiện sao chép văn bản và triển khai ứng dụng thử nghiệm tại ĐHĐN. Mặc dù đã đạt được những kết quả khả quan nhưng luận án vẫn cịn một số hạn chế như: - Phương pháp dựa trên DWT và bộ lọc Haar tập trung vào độ chính xác và xử lý dữ liệu lớn nên chưa thể đánh giá về mặt ngữ nghĩa. Ngồi ra, phương pháp đề xuất này dựa trên đặc tính sắp xếp dữ liệu theo chuỗi thời gian thực, do đĩ trong trường hợp thay đổi thứ tự các từ trong tài liệu đáng ngờ thì hiệu quả sẽ thấp. - Luận án chưa giải quyết một số vấn đề liên quan trong sao chép như: ngữ nghĩa (liên quan đến cấu trúc của câu - từ, từ loại của từ, từ đồng nghĩa, phân tích cú pháp, gán nhãn từ loại, thứ tự từ trong câu, nhận dạng thực thế cĩ tên, khái niệm ), dịch từ ngơn ngữ này sang ngơn ngữ khác, trích dẫn, bản quyền tác giả, tự sao chép 2. Hướng phát triển - Tiếp tục nghiên cứu các phương pháp xử lý, tìm kiếm, so khớp DNA đạt hiệu quả cao hơn. - Tổ chức dữ liệu DNA theo mơ hình Tensor là một hướng đi đầy triển vọng cần tiếp tục nghiên cứu và thử nghiệm. - Phát triển hệ thống hồn chỉnh ứng dụng vào thực tiễn để gĩp phần nâng cao chất lượng đào tạo và nghiên cứu khoa học.
27. DANH MỤC CÁC CƠNG TRÌNH KHOA HỌC ĐÃ CƠNG BỐ 1. Hồ Phan Hiếu, Trần Thanh Liêm, Giải pháp hệ thống hĩa tên miền và nguồn tài liệu khoa học của Đại học Đà Nẵng. Tạp chí Khoa học và Cơng nghệ ĐHĐN, Số 12(97), 2015, (20-24). 2. Hung Vo Trung, Ngoc Anh Nguyen, Hieu Ho Phan, Thi Dung Dang, Comparison of the Documents Based On Vector Model: A Case Study of Vietnamese Documents. American Journal of Engineering Research (AJER), Vol 6(7), 2017, (251-256). 3. Hồ Phan Hiếu, Võ Trung Hùng, Nguyễn Thị Ngọc Anh, Một số phương pháp tính độ tương tự văn bản dựa trên mơ hình vector. Tạp chí Khoa học và Cơng nghệ ĐHĐN, Số 11(120), 2017, (112-117). 4. Hồ Phan Hiếu, Nguyễn Thị Ngọc Anh, Nguyễn Văn Hiếu, Đặng Thiên Bình, Võ Trung Hùng, Một cách tiếp cận mới để phát hiện sự giống nhau của văn bản dựa trên phép biến đổi Wavelet rời rạc. Kỷ yếu Hội nghị Khoa học Cơng nghệ Quốc gia lần thứ X (Fair’10), lĩnh vực Nghiên cứu cơ bản và ứng dụng CNTT, 2017, (479-487). 5. Phan Hieu Ho, Trung Hung Vo, Ngoc Anh Thi Nguyen, Data Warehouse Designing for Vietnamese Textual Document-based Plagiarism Detection System. IEEE International Conference on System Science and Engineering (ICSSE 2017), 2017, (254-258). (Indexed in Scopus) 6. Nguyen Thi Ngoc Anh, Ho Phan Hieu, Tran Anh Kiet, and Vo Trung Hung, Similarity Detection for Higher-Order Structure of DNA Sequences. Journal of Science and Technology: Issue on Information and Communications Technology, Vol. 3, No.2, 2017, (28-34). 7. Phan Hieu Ho, Ngoc Anh Thi Nguyen, Trung Hung Vo, DNA Sequences Representation Derived from Discrete Wavelet Transformation for Text Similarity Recognition. In Springer SCI Book, Modern Approaches for Intelligent Information and Database Systems, 2018, (75-85). (Indexed in Scopus) 8. Hồ Phan Hiếu, Nguyễn Thị Ngọc Anh, Võ Trung Hùng, Phương pháp mã hĩa văn bản thành chuỗi số DNA để đánh giá mức độ giống nhau của văn bản. Hội thảo KH Quốc gia CNTT và ứng dụng-CITA 2018, (223-229). 9. Phan Hieu Ho, Trung Hung Vo, Ngoc Anh Thi Nguyen, Ha Huy Cuong Nguyen, A Narrative Method for Evaluating Documents Similarity based on Unique Strings. International Journal of Recent Technology and Engineering (IJRTE), Vol 8, 2019, (473-479). (Indexed in Scopus)