Chương 1: Giới thiệu đề tài. Chương 2: Trình bày cơ sở lý thuyết về bài toán phân loại tin tức giả mạo. Chương 3: Trình bày phương pháp giải quyết bài toán theo các phương pháp trên. Chương 4: Thực nghiệm, đánh giá nhận xét kết quả bài toán, so sánh kết quả với các nghiên cứu tương đương.
Chương 5: Kết luận và hướng phát triển. 13 CHƯƠNG 2: CƠ SỞ LÝ THUYET 1. Đồ thị và đồ thị tri thức: 1. Dinh nghĩa đồ thị: Một đồ thị được định nghĩa là một cấu trúc rời rạc gồm tập hợp các đỉnh và các cạnh nối giữa các đỉnh đó.
Ta có thé mô tả đồ thị theo công thức (1.1) Khi đó, đồ thị G có tập các đỉnh là V, tập các cạnh là E, ta có thé hiểu E là tập hợp các cặp (u,v) với u và v là hai đỉnh thuộc V. Một đồ thị G bất kỳ có thê được phân loại theo tính chất của tập cạnh như sau: e G được định nghĩa là đồ thị đơn nêu như giữa hai đỉnh (u,v) của V có nhiều nhất một cạnh trong E nối từ đỉnh u tới đỉnh v. e G được định nghĩa là đồ thị đa nếu như giữa hai đỉnh (u,v) của V có thé có nhiều hơn một cạnh nối trong E nối từ đỉnh u tới đỉnh v. e G được định nghĩa là đồ thị vô hướng (undirected graph) nếu như các cạnh trong E là không có hướng, nghĩa là cạnh (u,v) là cạnh hai chiều.
e G được gọi là đồ thị có hướng (directed graph) nếu như các cạnh trong E là có định hướng, nghĩa là có tồn tại một cạnh bất kỳ nối từ đỉnh u tới đỉnh v nhưng chưa chắc tồn tại cạnh nối từ đỉnh v tới đỉnh u. Trên đồ thị có hướng, các cạnh sẽ được gọi là các cung. Đồ thị vô hướng cũng có thé coi là đồ thị có hướng trong trường hợp ta coi cạnh (u,v) bat kỳ tương ứng với hai cung (u > v) và (v > 1ì. Đơn đồ thị Đa đồ thị Hình 2.
Mô tả các loại đồ thị 14 1. Một số khái niệm trên đồ thị: 1. Cạnh liên thuộc, đỉnh kề, bậc và khuyên: Đối với đồ thị vô hướng G = (W, E), ta xét cạnh e = (u,v) € E. Ta nói rang hai đỉnh u và đỉnh v kề nhau (adjacent), và cạnh e này liên thuộc (incident) với hai đỉnh u và đỉnh v.
Với một đỉnh u thuộc đồ thị, định nghĩa bậc (degree), ký hiệu deg(u) là số cạnh liên thuộc với u. Trên đơn đồ thị, số cạnh liên thuộc với u cũng chính là số đỉnh kề VỚI U. Ta có các định lý về đồ thị như sau: “ Dinh lý 1 Giả sử G = (V,E) là đồ thị vô hướng với M cạnh khi đó tổng tat cả các bậc đỉnh trong V sẽ bằng 2M.2) Chứng minh: Khi lấy tổng tat cả các bậc đỉnh, tức là mỗi cạnh e = (u, 0) bất kỳ sẽ được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra điều phải chứng minh.
Hệ quả: Trên đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. Đối với đồ thị có hướng G = (V,E), xét một cung e = (u 0) € E. Khi đó ta nói đỉnh u nối tới đỉnh v và đỉnh v nối từ đỉnh u. Đỉnh u được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e.
Với mỗi đỉnh u trong đồ thị có hướng, định nghĩa: Bán bậc ra (out-degree) của đỉnh u, ký hiệu deg +( +) là số cung đi ra khỏi nó. Ban bậc vao (in-degree) của đỉnh u, ký hiệu deg —( +) là số cung đi vào nó. ®% Định lý 2 Gia sử G = (V,E) là đồ thị có hướng với M cung, khi đó tong tat cả các bán bậc ra băng tông tât cả các bán bậc vào và băng M: 3»ey deg*(v) = Xvey deg" (v) = M (13) 15 Chứng minh: Khi lay tổng tat cả các bán bậc ra hoặc bán bậc vào, mỗi cung u > v bất kỳ sẽ được tính đúng một lần trong đeg?() và cũng được tính đúng một lần trong đeg” (ø). Từ đó ta suy ra điều phải chứng minh.
Ngoài ra, trên đồ thị có hướng hoặc vô hướng, trong một số trường hợp có thê có những cạnh nối một đỉnh với chính nó. Cạnh này được gọi là khuyên của đồ thị, và trong trường hợp này, thì các cạnh nối hai đỉnh phân biệt sẽ được gọi là các liên kết dé tránh nhằm lẫn. Đường đi và chu trình: Một đường đi P độ dài k từ đỉnh vp tới đỉnh v, là tập đỉnh {v9, V4, 0, ., 2} sao cho (;_¡,1¿) € E,Vi: 1 <i < k. Khi đó ta nói đường đi này bao gồm các đỉnh {Uạ,1,9ạ,.,(0y—+,0„)}; và Vo đến được 1„ thông qua đường di P.
Đường đi được gọi là đường đi đơn giản (simple path) nếu tat cả các đỉnh trên đường đi đó đều phân biệt. Đường đi được gọi là đường đi đơn nếu như không có cạnh nào trên đường đi đó đi qua hơn một lần. Một đường di con (subpath) P“ của P là một đoạn liên tục các đỉnh và cạnh dọc theo đường di P. Một đường đi P được gọi là chu trình (circuit) nếu như vp = œ„.
Chu trình P gọi là chu trình đơn giản (simple circuit) nếu như {14, v2, ., Vg} đôi một khác nhau. Chu trình mà trong đó không có cạnh nào đi qua hơn một lần được gọi là chu trình đơn. Tính liên thông của đồ thị: Đối với đồ thị vô hướng G = (W,E) thì G được gọi là liên thông nếu như với mọi cặp đỉnh phân biệt (u,v), ta đều có đỉnh u đến được đỉnh v và ngược lại. Đối với đồ thị có hướng G = (V,E) thi: e G được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt (u, 0), ta có đỉnh u đến được đỉnh v và đỉnh v cũng đến được đỉnh u.
16 e G được gọi là liên thông yêu (weakly connected) nếu như đồ thị vô hướng nền của nó là liên thông. e G được gọi là liên thông một phan (unilaterally connected) nếu như với mọi cặp đỉnh phân biệt (u, v), có ít nhất một đỉnh đến được đỉnh còn lại. Dinh nghĩa về đồ thị tương tự: Đồ thị tương tự (similarity graph) là đồ thị vô hướng biểu diễn mối quan hệ tương đồng giữa các phần tử trong một tập hợp. Trong ngữ cảnh của xử lý ngôn ngữ tự nhiên, đồ thị tương tự thường được sử dụng dé mô tả mối quan hệ ngữ nghĩa hoặc tương tự giữa các từ hoặc văn bản.
Đặc điểm chính của đồ thị tương tự: e Đinh: Mỗi đỉnh trong đồ thị đại diện cho một phần tử trong tập hợp, thường là một từ, cụm từ hoặc một đối tượng. e _ Cạnh: Các cạnh giữa các đỉnh thể hiện mức độ tương đồng hoặc mối quan hệ giữa chúng. Càng gần nhau, mức độ tương tự cảng cao. e Trọng số cạnh: Mỗi cạnh có thé được gán một trọng số dé biểu thị độ mạnh của mỗi quan hệ tương tự giữa các đỉnh.
Dinh nghĩa về đồ thị tri thức (Knowledge Graph - KG): Đồ thị tri thức là cách biểu diễn tri thức thực tiễn dưới dạng đồ thị. Một đồ thị tri thức được tạo thành từ ba thành phần chính: đỉnh, cạnh và nhãn. Bat kỳ đối tượng, địa điểm hoặc người nào cũng có thể là một đỉnh. Một cạnh xác định mối quan hệ giữa các đỉnh.
17 Thuộc loại hình ® Có giám đốc '— Thanh lập vào oe Thành viên của Be Thuộc tổ chức Có địa chỉ Có đội ngũ nhân sự = cm Hình 2. Minh họa đồ thị tri thức Trung tâm của đồ thị tri thức là một mô hình tri thức, là một tập hợp các mô tả liên kết với nhau về các khái niệm, thực thé, mối quan hệ và sự kiện trong đó: e Các mô tả có ngữ nghĩa chính thức cho phép cả người và máy tính xử lý chúng một cách hiệu quả và rõ ràng. e Các mô tả đóng góp cho nhau, tạo thành một mạng lưới, trong đó mỗi thực thê đại diện cho một phần mô tả của các thực thê liên quan đến nó. e Di liệu đa dạng được kết nối và mô tả bằng siêu dữ liệu ngữ nghĩa theo mô hình tri thức.
Đồ thị tri thức kết hợp các đặc điểm của một số mô hình quản lý đữ liệu: e Cơ sở dữ liệu tri thức vi dit liệu có thé được trích xuất thông qua các truy van có cấu trúc đồ thị, chúng có thể được phân tích như bat ky cau trúc dữ liệu mang nao khac. ¢ Cơ sở tri thức vì chúng mang ngữ nghĩa chính thức, có thé được sử dụng dé giải thích dữ liệu và suy ra các sự kiện mới. Cách thức hoạt động của đồ thị tri thức: Đồ thị tri thức hoạt động bằng cách hiền thị các mối quan hệ giữa mỗi câu lệnh trong đó, các câu lệnh được gọi là “thực thể”. Khi ta đặt các thực thể trong mối quan hệ với nhau, ta có thé cung cấp thông tin này cho tat cả các loại máy sẽ ngay lập tức tạo ra ý nghĩa.
Đây là một ưu điểm lớn của đồ thị tri thức trong việc biểu diễn mối quan hệ giữa các “thực thể” trong một câu. Đồ thị tri thức thường được tạo thành từ các tập dữ liệu từ nhiều nguồn khác nhau, thường khác nhau về cấu trúc. Các lược đồ, danh tính và ngữ cảnh phối hợp với nhau dé cung cấp cấu trúc cho dit liệu da dang. Các lược đồ cung cấp khung cho đồ thị tri thức, các danh tính phân loại các nút bên dưới một cách thích hợp và ngữ cảnh xác định cài đặt mà tri thức đó tồn tại.
Các thành phan này giúp phân biệt các từ nhiều nghĩa. Điều này cho phép các sản phẩm, có thé kể đến như thuật toán công cụ tìm kiếm của Google, xác định sự khác biệt giữa Apple, Android. Đồ thị tri thức được hỗ trợ bởi các thuật toán học máy, sử dụng quá trình xử lý ngôn ngữ tự nhiên để xây dựng một đồ thị trực quan hóa toàn diện về các nút, cạnh và nhãn, quá trình này được gọi là làm giàu ngữ nghĩa. Khi dữ liệu được nhập vào, cho phép đồ thị tri thức xác định các đối tượng riêng lẻ và hiểu được mối quan hệ giữa các đối tượng khác nhau.
Sau khi đồ thị tri thức hoàn thành, nó cho phép các hệ thong tim kiếm và trả lời câu hỏi truy xuất và sử dụng lại các câu trả lời toàn diện cho các truy vấn đã biết trước.