CƠ SỞ LÝ THUYẾT
Tổng quan
2.1.1 Định nghĩa phân loại văn bản
Phân loại văn bản là một trong nhiêu lĩnh vực được chú ý nhất và đã được nghiên cứu trong những năm gần đây
Phân loại văn bản là quá trình gán văn bản vào các lớp đã xác định trước Việc phân loại có thể thực hiện thủ công bằng cách đọc nội dung và gán loại, nhưng phương pháp này tốn nhiều thời gian và công sức, đặc biệt trong hệ thống quản lý tập văn bản lớn Do đó, cần áp dụng các phương pháp phân loại tự động Các phương pháp học máy trong trí tuệ nhân tạo như Cây quyết định, Nạve Bayes và K láng giềng gần nhất được sử dụng để thực hiện phân loại tự động hiệu quả.
Phân loại văn bản tự động đóng vai trò quan trọng trong các hệ thống tìm kiếm văn bản, giúp gán chỉ số lớp cho các văn bản trong miền tìm kiếm từ một tập con đã phân loại Người dùng có thể xác định chủ đề hoặc loại văn bản mong muốn, từ đó hệ thống cung cấp kết quả tìm kiếm phù hợp với yêu cầu của họ.
Phân loại văn bản là một ứng dụng quan trọng trong lĩnh vực hiểu văn bản, giúp lọc ra các đoạn văn hoặc thông tin cần thiết mà vẫn giữ nguyên tính phức tạp của ngôn ngữ tự nhiên.
Phân loại văn bản được ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm lọc e-mail, định hướng mail, lọc thư rác, giám sát tin tức và tự động chỉ mục các bài báo khoa học.
Các phương pháp rút trích thông tin cổ điển xem mỗi văn bản như một tập hợp các từ khóa, được gọi là tập term Mỗi phần tử trong tập term là một từ, có ngữ nghĩa quan trọng trong việc hình thành nội dung văn bản Do đó, tập term được sử dụng để tạo chỉ mục và tóm tắt nội dung của văn bản.
Trong một tập hợp các thuật ngữ của một văn bản, không phải tất cả các từ đều có tầm quan trọng giống nhau Một số từ có thể mang ý nghĩa chính yếu, trong khi những từ khác chỉ đóng vai trò phụ trợ Việc nhận diện và phân loại các từ này là rất cần thiết để tối ưu hóa nội dung và nâng cao hiệu quả truyền tải thông điệp.
Trong quá trình phân tích nội dung văn bản, việc xác định trọng số cho từng từ trong tập term là rất quan trọng Nếu một từ A xuất hiện quá nhiều trong một tập hợp lớn văn bản, như một trăm ngàn văn bản, chúng ta có thể kết luận rằng từ A không có giá trị thông tin cao và sẽ không được chú ý Do đó, từ A sẽ bị loại khỏi tập term, giúp chúng ta xây dựng một tập hợp từ ngữ phù hợp hơn để mô tả nội dung ngữ nghĩa của các văn bản Mỗi từ trong tập term được gán một trọng số Wij ≥ 0 trong văn bản dj, với Wij > 0 nếu từ xuất hiện trong văn bản Nhờ vào việc xác định trọng số này, mỗi văn bản dj có thể được biểu diễn dưới dạng vector, giúp tối ưu hóa việc phân tích và hiểu nội dung của nó.
Các đặc trưng của văn bản khi biểu diễn dưới dạng vector:
Số nhiều không gian đặc trưng thường lớn
Các đặc trưng độc lập nhau
Các đặc trưng rời rạc trong vector đặc trưng có thể chứa nhiều thành phần giá trị 0, do một số đặc trưng không xuất hiện trong văn bản Phương pháp sử dụng giá trị nhị phân 0, 1 để biểu diễn sự xuất hiện của đặc trưng có thể hạn chế khả năng phân loại, vì một đặc trưng có thể không có trong văn bản nhưng vẫn có từ khóa khác mang ý nghĩa tương tự Do đó, một giải pháp thay thế là sử dụng giá trị số thực thay vì nhị phân, nhằm giảm bớt tính rời rạc trong vector văn bản.
Mô hình biểu diễn văn bản
Có nhiều cách biểu diễn văn bản, luận văn trình bày một số phương pháp biểu diễn văn bản phổ biến
Theo mô hình này, các từ có nghĩa trong văn bản được đánh chỉ số để quản lý nội dung Mỗi văn bản được liệt kê theo vị trí xuất hiện của các từ có nghĩa, giúp xác định thông tin chính Những từ này mang lại cái nhìn tổng quan về chủ đề của văn bản, cho phép người đọc nhanh chóng hiểu nội dung cần biểu diễn.
Chúng ta sẽ tiến hành lập chỉ mục cho các văn bản dựa trên danh sách từ khóa đã đề cập Mỗi từ khóa sẽ được đánh số theo thứ tự xuất hiện và lưu trữ chỉ số cùng với mã văn bản chứa nó Phương pháp này được các công cụ tìm kiếm ưa chuộng.
Ví dụ: Có 2 văn bản với mã tương ứng là VB1, VB2:
VB1 là: “Đại hội chi bộ thành công”
VB2 là: “Chi bộ hoàn thành nhiệm vụ”
Khi đó, ta có cách biểu diễn như sau:
Bảng 2.1: Biểu diễn văn bản trong mô hình Logic
Từ mục Mã VB_Vị trí xuất hiện Đại VB1(1)
Vụ VB2(6) Ưu điểm, nhược điểm của mô hình logic:
Việc tìm kiếm thông tin trở nên nhanh chóng và đơn giản khi hệ thống duyệt bảng Index để xác định chỉ số tương ứng với từ khóa, chẳng hạn như "computer" Nếu bảng Index được sắp xếp theo thứ tự chữ cái, quá trình tìm kiếm sẽ diễn ra hiệu quả với độ phức tạp là nlog2 n , trong đó n là số từ trong bảng Index Chỉ số index sẽ cung cấp thông tin về các tài liệu chứa từ khóa tìm kiếm Do đó, nếu tìm kiếm liên quan đến k từ, tổng số phép toán cần thực hiện sẽ là k*n* log2 n.
Phương pháp tìm kiếm này yêu cầu người dùng có kinh nghiệm và chuyên môn, vì câu hỏi được đưa ra dưới dạng Logic (Boolean) nên kết quả nhận được sẽ có giá trị Chỉ những tài liệu thỏa mãn tất cả các điều kiện được nhập mới được trả lại Do đó, để tìm kiếm tài liệu theo nội dung, người dùng cần phải biết rõ về tài liệu mình cần tìm.
Việc Index các tài liệu rất phức tạp và làm tốn nhiều thời gian, đồng thời cũng tốn không gian để lưu trữ các bảng Index
Các tài liệu được tìm thấy không được tổ chức theo độ chính xác, và bảng chỉ mục không linh hoạt Khi có sự thay đổi về từ vựng như thêm, sửa, hoặc xóa, chỉ số Index cũng cần phải điều chỉnh tương ứng.
2.2.2 Mô hình phân tích cú pháp
Trong mô hình này, mỗi văn bản cần được phân tích cú pháp để trích xuất thông tin chi tiết về chủ đề Tiếp theo, các chủ đề của từng văn bản sẽ được tiến hành lập chỉ mục (Index).
9 bản Cách Index trên chủ đề cũng giống như Index trên văn bản nhưng chỉ Index trên các từ xuất hiện trong chủ đề
Các văn bản được tổ chức theo các chủ đề cụ thể, giúp người dùng dễ dàng tìm kiếm thông tin khi cần Các câu hỏi tìm kiếm sẽ dựa vào những chủ đề này để đảm bảo tính chính xác và hiệu quả trong việc truy xuất dữ liệu.
Một số ưu điểm, nhược điểm của phương pháp này:
Phương pháp tìm kiếm này rất hiệu quả và dễ thực hiện, nhờ vào khả năng tìm kiếm nhanh chóng và chính xác Đối với các ngôn ngữ có ngữ pháp đơn giản, việc phân tích có thể đạt được độ chính xác cao và đáng tin cậy.
Chất lượng của hệ thống phụ thuộc hoàn toàn vào độ chính xác của hệ thống phân tích cú pháp và khả năng nhận diện nội dung tài liệu Việc xây dựng hệ thống này rất phức tạp, phụ thuộc vào đặc điểm riêng của từng ngôn ngữ, và hiện tại, hầu hết các hệ thống vẫn chưa đạt được độ chính xác cao.
2.2.3 Mô hình không gian vector
Cách phổ biến nhất để biểu diễn văn bản là sử dụng mô hình không gian vector (Vector Space Model), một phương pháp đơn giản nhưng hiệu quả.
Theo mô hình này, mỗi văn bản được chuyển đổi thành một vector, trong đó mỗi thành phần đại diện cho một từ khóa riêng lẻ từ tập văn bản gốc Mỗi từ khóa sẽ được gán một giá trị phản ánh mật độ xuất hiện của nó trong văn bản.
Trong không gian hai chiều, một văn bản có thể được biểu diễn dưới dạng vector V = (v1, v2, , vn), trong đó vi đại diện cho số lần xuất hiện của từ khóa thứ i Ví dụ, khi phân tích hai văn bản khác nhau, chúng ta có thể so sánh sự xuất hiện của các từ khóa để hiểu rõ hơn về nội dung và ý nghĩa của chúng.
VB1: Đại hội chi bộ
VB2: Đại hội đã thành công
Sau khi qua bước tiền xử lý văn bản, ta biểu diễn như sau:
Bảng 2.2: Biểu diễn văn bản mô hình Vector
Từ Vector_VB1 Vector_VB2 Đại 1 1
Mô hình vector là phương pháp phổ biến nhất để biểu diễn văn bản trong các cơ sở dữ liệu văn bản hiện nay Mối quan hệ giữa các văn bản được xác định thông qua việc tính toán trên các vector biểu diễn, mang lại hiệu quả cao trong việc xử lý và phân tích dữ liệu.
Mô hình Boolean là một biểu diễn vector với hàm f, cho ra giá trị rời rạc chỉ với hai trạng thái: đúng (true) và sai (false), tương ứng với 0 và 1 Hàm f sẽ trả về giá trị đúng khi từ khóa ti xuất hiện trong văn bản.
Mô hình Boolean được xác định như sau:
Trong một cơ sở dữ liệu với m văn bản D = {d1, d2, , dm}, mỗi văn bản được biểu diễn dưới dạng vector của n từ khóa T = {t1, t2, , tn} Ma trận trọng số W = {Wij} thể hiện giá trị trọng số của từ khóa ti trong văn bản dj.
Trở lại với 2 văn bản trên, áp dụng mô hình Boolean ta có biểu diễn như sau:
Bảng 2.3: Biểu diễn văn bản mô hình Boolean
Từ Vector_VB1 Vector_VB2 Đại 1 1
Các phương pháp phân loại văn bản
2.3.1 Phương pháp Nạve Bayes (NB)
Phương pháp Naive Bayes (NB) là một kỹ thuật phân loại dựa trên xác suất, được ứng dụng rộng rãi trong máy học, với lịch sử phát triển từ năm 1961 khi Maron lần đầu tiên áp dụng trong phân loại NB đã trở nên phổ biến trong nhiều lĩnh vực như công cụ tìm kiếm và bộ lọc mail Ý tưởng chính của phương pháp này là sử dụng xác suất có điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của văn bản cần phân loại Một điểm quan trọng là giả định rằng sự xuất hiện của các từ trong văn bản là độc lập với nhau, điều này giúp NB không cần xem xét sự phụ thuộc giữa các từ và không kết hợp chúng để đưa ra phán đoán chủ đề.
NB chạy nhanh hơn các phương pháp khác với độ phức tạp theo hàm số mũ
Công thức tính xác suất Pr(Cj,d′) nhằm xác định khả năng văn bản d′ thuộc lớp Cj Theo luật Bayes, văn bản d′ sẽ được phân loại vào lớp Cj có xác suất Pr(Cj, d′) cao nhất Công thức này được đề xuất bởi Joachims vào năm
Pr Pr / Pr Pr / argmax argmax
- (TF,d’) là số lần xuất hiện của từ wj trong văn bản d′
- |d′| là số lượng các từ trong văn bản d′
- wj là một từ trong không gian đặc trưng F với số chiều là |F|
- Pr(Cj) được tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp tương ứng trong tập dữ liệu huấn luyện:
- Pr( wj|Cj) được tính sử dụng phép ước lượng Laplace (do Napnik trình bày năm 1982)
Ngoài Naive Bayes cơ bản, còn có các phương pháp khác như ML Naive Bayes, MAP Naive Bayes, Expected Naive Bayes và Bayesian Naive Bayes (Jason, 2001) Naive Bayes là một công cụ hiệu quả trong một số tình huống, nhưng kết quả có thể kém nếu dữ liệu huấn luyện nghèo nàn và các tham số dự đoán có chất lượng kém Thuật toán này phù hợp cho phân loại văn bản nhiều chủ đề với ưu điểm là cài đặt đơn giản, tốc độ nhanh và dễ dàng cập nhật dữ liệu huấn luyện mới Tuy nhiên, Naive Bayes cần giả định tính độc lập giữa các từ và một ngưỡng tối ưu để đạt kết quả khả quan Để cải thiện hiệu năng, có thể áp dụng các phương pháp như multiclass-boosting và ECOC (Berger).
1999 và Ghani mô tả lại năm 2000) có thể được dùng kết hợp
2.3.2 Phương pháp K-Nearest Neighbor (k-NN) Đây là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên thống kê đã được nghiên cứu trong nhận dạng mẫu hơn bốn thập kỷ qua (theo tài liệu của Dasarathy năm 1991) kNN được đánh giá là một trong những phương pháp tốt nhất (áp dụng trên tập
Phương pháp phân loại văn bản được giới thiệu từ những năm 1990, như Marsand (1992), Yang (1994) và Iwayama (1995), sử dụng tập dữ liệu Reuters phiên bản 21450 Khi phân loại một văn bản mới, thuật toán tính toán khoảng cách (như khoảng cách Euclide và Cosine) giữa văn bản này và tất cả văn bản trong tập huấn luyện để xác định k văn bản gần nhất (k "láng giềng") Trọng số của một chủ đề được tính bằng tổng khoảng cách của các văn bản trong k láng giềng có cùng chủ đề, trong khi chủ đề không xuất hiện sẽ có trọng số bằng 0 Cuối cùng, các chủ đề được sắp xếp theo trọng số giảm dần và những chủ đề có trọng số cao nhất sẽ được chọn làm chủ đề cho văn bản cần phân loại.
Khi đó trọng số của chủ đề cj đối với văn bản x
không thuộc về chủ đề c y j , 1: văn bản d i
: độ giống nhau giữa văn bản cần phân loại x và văn bản d i
Có thể sử dụng độ đo cosine để tính sim x d ( , i )
Ngưỡng phân loại bj của chủ đề cj được xác định tự động thông qua một tập văn bản hợp lệ từ dữ liệu huấn luyện Để tìm ra tham số k tối ưu cho việc phân loại, thuật toán cần được thử nghiệm với nhiều giá trị k khác nhau; giá trị k lớn hơn sẽ giúp thuật toán trở nên ổn định hơn và giảm thiểu sai sót.
17 sót càng thấp [20] Giá trị tốt nhất được sử dụng tương ứng trên hai bộ dữ liệu Reuter và Oshumed là k = 45
2.3.3 Phương pháp Support vector Machine (SVM)
SVM, hay Máy Vector Hỗ trợ, là một phương pháp phân lớp dựa trên lý thuyết học thống kê, được giới thiệu bởi Vapnik vào năm 1995 Bài viết này sẽ tập trung vào bài toán phân lớp nhị phân trước, sau đó sẽ mở rộng sang bài toán phân loại nhiều lớp.
Trong bài toán phân lớp, mục tiêu là tìm một đường thẳng phân chia các điểm dữ liệu, sao cho tất cả các điểm đỏ nằm bên trái và các điểm xanh nằm bên phải Phương pháp này được gọi là phân lớp tuyến tính (linear classification).
Hình 2.2 Phân lớp tuyến tính (Tham khảo http://www.statsoft.com/Textbook/Support-Vector-Machines)
Hàm tuyến tính phân biệt hai lớp như sau:
Trong đó: wR m là vector trọng số hay vector chuẩn của siêu phẳng phân cách, T là kí hiệu chuyển vị b R là độ lệch
là véc tơ đặc trưng, làm hàm ánh xạ từ không gian đầu vào sang không gian đặc trưng
Tập dữ liệu đầu vào gồm N mẫu input vector {x1, x2, ,xN}, với các giá trị nhãn tương ứng là {t1,…,tN} trong đó t n 1,1
Trong bài viết này, cần lưu ý rằng các thuật ngữ như điểm dữ liệu và mẫu đều được hiểu là vector đầu vào xi Trong không gian hai chiều, đường phân cách là một đường thẳng, trong khi trong không gian đa chiều, nó được gọi là siêu phẳng.
Giả sử rằng tập dữ liệu có thể được phân tách tuyến tính hoàn toàn trong không gian đặc trưng, sẽ tồn tại các tham số w và b sao cho y(x_n) > 0 đối với các điểm có nhãn t_n = +1 và y(x_n) < 0 đối với các điểm có nhãn t_n = -1 Điều này dẫn đến việc t * y(x_n) > 0 cho mọi điểm dữ liệu trong quá trình huấn luyện.
SVM giải quyết vấn đề phân loại bằng cách sử dụng khái niệm lề (margin), định nghĩa là khoảng cách nhỏ nhất từ đường phân cách đến các điểm dữ liệu, đặc biệt là những điểm gần nhất.
Hình 2.3 Minh họa lề trong thuật toán SVM
Trong SVM, đường phân lớp tối ưu là đường có khoảng cách margin lớn nhất, nghĩa là giữa các đường phân cách khác nhau, ta chọn ra đường có khoảng cách margin lớn nhất để đạt được hiệu quả phân loại tốt nhất.
Hình 2.4 Phân lớp SVM bằng cách sử dụng lề
Ta có công thức tính khoảng cách từ điểm dữ liệu đến mặt phân cách như sau:
Hình 2.5 Minh họa khoảng cách từ điểm dữ liệu đến mặt phân cách
Do ta đang xét trong trường hợp các điểm dữ liệu đều được phân lớp đúng nên
0 n n t y x cho mọi n Vì thế khoảng cách từ điểm xn đến mặt phân cách được viết lại như sau:
Lề là khoảng cách vuông góc từ điểm dữ liệu gần nhất \( x_n \) trong tập dữ liệu, và mục tiêu của chúng ta là tối ưu hóa giá trị của \( w \) và \( b \) để cực đại hóa khoảng cách này Vấn đề cần giải quyết có thể được diễn đạt thông qua công thức sau:
Chúng ta có thể đưa nhân tử 1 w ra ngoài vì w không phụ thuộc vào n Việc giải quyết vấn đề này trực tiếp sẽ phức tạp, vì vậy ta sẽ chuyển đổi nó thành một vấn đề tương đương dễ giải quyết hơn Cụ thể, ta sẽ biến đổi w thành w và b thành b cho mọi điểm dữ liệu, từ đó khoảng cách lề trở thành 1, mà không làm thay đổi bản chất của vấn đề.
Từ bây giờ, các điểm dữ liệu sẽ thỏa ràng buộc:
Vấn đề tối ưu yêu cầu ta cực đại w 1 được chuyển thành cực tiểu w 2 , ta viết lại công thức:
2 w , arg min 1 w (6) b 2 Việc nhõn hệ số ẵ sẽ giỳp thuận lợi cho lấy đạo hàm về sau
Lý thuyết Nhân tử Lagrange:
Vấn đề cực đại hàm f(x) thỏa điều kiện g x 0 sẽ được viết lại dưới dạng tối ưu của hàm Lagrange như sau:
Trong đó x và λ phải thỏa điều kiện Karush-Kuhn-Tucker (KKT) như sau:
Nếu là cực tiểu hàm f(x) thì hàm Lagrange sẽ là
L x f x g x Để giải quyết bài toán trên, ta viết lại theo hàm Lagrange như sau:
Trong đó a a a 1 , 2 , , a N T là nhân tử Lagrange
Lưu ý dấu (–) trong hàm Lagrange, bởi vì ta cực tiểu theo biến w và b, và là cực đại theo biến a
Lấy đạo hàm L(w,b,a) theo w và b ta có:
Loại bỏ w và b ra khỏi L(w,b,a) bằng cách thế (8), (9) vào Điều này sẽ dẫn ta đến vấn đề tối ưu:
Ở đây hàm nhân (kernel function) được định nghĩa là k x x n , m x n T x m
Để phân lớp một điểm dữ liệu mới bằng mô hình đã được huấn luyện, ta sẽ tính dấu của y(x) theo công thức (1), sử dụng giá trị w từ công thức (8) Vấn đề này sẽ được thảo luận kỹ hơn trong phần kỹ thuật giải quyết thỏa mãn các điều kiện (10), (11), (12) sau.
Thỏa các điều kiện KKT sau:
Khai thác đồ thị
Trong phần này, chúng tôi sẽ giới thiệu các khái niệm và định nghĩa quan trọng liên quan đến lý thuyết đồ thị, nhằm hỗ trợ cho bài toán phân loại văn bản dựa trên mô hình đồ thị Bên cạnh đó, chúng tôi cũng sẽ đề cập đến các phương pháp khai phá đồ thị con phổ biến trong các phần tiếp theo.
Cho một nhãn node bằng chữ cái (alphabet) L V và một nhãn cạnh bằng chữ cái L E đồ thị G (có hướng) được định nghĩa bằng bộ gồm 4 thành phần G V E , , , v , trong đó:
V: biểu diễn một tập hữu hạn các node
E V V biểu diễn một tập các cạnh
biểu diễn một hàm ghi nhãn node
biểu diễn một hàm ghi nhãn cạnh
Tập V có thể được coi là một tập các định danh nút và thường được chọn bằng V =
Trong đồ thị, tập hợp các nút được ký hiệu là V, trong khi tập các cạnh E thể hiện cấu trúc kết nối giữa các nút Một nút u ∈ V được kết nối với một nút v ∈ V thông qua một cạnh (u, v) nếu (u, v) thuộc E Hàm ghi nhãn cho phép tích hợp thông tin về các nút và các cạnh bằng cách gán thuộc tính từ L V và L E cho các nút và cạnh tương ứng Đồ thị được định nghĩa có thể bao gồm nhiều trường hợp đặc biệt, trong đó đồ thị vô hướng được xác định bởi điều kiện rằng cho mỗi cạnh (u, v) thuộc E, cần có (v, u) cũng thuộc E.
Trong trường hợp đồ thị không thuộc tính, bảng chữ cái nhãn được xác định bởi L với V và E là tập hợp rỗng Do đó, mỗi node và mỗi cạnh trong đồ thị sẽ được gán nhãn null, tức là nhãn rỗng Đồ thị rỗng được định nghĩa là G = (∅, ∅, μ, ν, ε).
2.4.1.2 Đồ thị được gán nhãn Đồ thị được gán nhãn: là một đồ thị được biểu diễn bởi G V E L L , , V , E , v , e , trong đó:
V: tập hợp của các đỉnh đồ thị
E V V : tập hợp các cạnh của đồ thị
L V : các nhãn đỉnh tương ứng
L E : các nhãn cạnh tương ứng v :V L V
: hàm ánh xạ một đỉnh với nhãn của nó e : E L E
: hàm ánh xạ một cạnh với nhãn của nó
Trong lý thuyết đồ thị, một thuật ngữ cơ bản là "đường đi", được định nghĩa là một chuỗi các đỉnh sắp xếp theo thứ tự, trong đó mỗi cặp đỉnh liền kề được kết nối bởi một cạnh.
Chiều dài của đường đi: là số cạnh bên trong đường đi đó
Chu trình: là một đường đi bắt đầu và kết thúc ở cùng một đỉnh
Khuyên: là một cạnh được kết nối một đỉnh và chính nó
Cạnh bội là tình huống có hai hoặc nhiều cạnh nối giữa hai đỉnh trong đồ thị Đồ thị không chu trình là loại đồ thị không chứa bất kỳ chu trình nào Đồ thị đầy đủ có đặc điểm là có cạnh nối giữa mọi cặp đỉnh Đồ thị có hướng được xác định bởi thứ tự của các đỉnh, trong khi đồ thị vô hướng thì không quan tâm đến thứ tự này.
Cho trước hai đồ thị G 1 V E L 1 , 1 , V 1 , L E 1 , v 1 , e 1 và G 2 V E L 2 , 2 , V 2 , L E 2 , v 2 , e 2
G 1 là một đồ thị con của G 2 nếu G 1 thỏa mãn các điều kiện sau:
G 2 cũng được gọi là siêu đồ thị của G 1 Ngoài ra, G 1 được gọi là đồ thị con cảm sinh của G 2 nếu G 1 thỏa mãn thêm điều kiện dưới đây:
Đồ thị con cảm sinh được định nghĩa là một đồ thị con G1 của G2, trong đó mọi cặp đỉnh xuất hiện đồng thời trong cả hai đồ thị đều phải có các cạnh kết nối giữa chúng cũng xuất hiện đồng thời Nói cách khác, đồ thị con cảm sinh là một đồ thị con có các ràng buộc nhất định.
2.4.2.1 Giới thiệu về phân lớp đồ thị
Biểu diễn dữ liệu bằng đồ thị là phương pháp hiệu quả cho các loại dữ liệu có cấu trúc như trình tự sinh học, hợp chất hóa học, protein, RNA, mạng xã hội và các tài liệu bán cấu trúc như HTML, XML Khai phá dữ liệu đồ thị đã trở thành một chủ đề quan trọng trong lĩnh vực này.
Trong thời gian gần đây, nhiều nghiên cứu đã được thực hiện để phát triển các phương pháp mới xử lý dữ liệu đồ thị, phản ánh nhu cầu thực tiễn trong các lĩnh vực như tin sinh học, tin hóa học, thị giác máy tính và phân tích mạng xã hội Điển hình là NCBI PubChem, nơi lưu trữ hàng triệu hợp chất hóa học được biểu diễn dưới dạng đồ thị phân tử.
Phân lớp sử dụng đồ thị gồm có hai bài toán:
- Phân lớp đồ thị: gán nhãn cho toàn bộ một đồ thị Được thực hiện giữa các đồ thị trong một tập hợp các đồ thị
- Phân lớp đỉnh đồ thị: gán nhãn cho các đỉnh bên trong một đồ thị Được thực hiện với một đồ thị đơn có kích thước lớn
Bài toán phân lớp đồ thị lần đầu được nghiên cứu bởi [15] với thuật toán SUBDUECL, đạt kết quả hứa hẹn bằng cách sử dụng tìm kiếm tham lam để phân biệt các lớp đồ thị Nhiều thuật toán và cách tiếp cận mới đã được phát triển, trong đó [11] áp dụng hệ thống FSG để khai thác đồ thị con phổ biến và sử dụng SVM để phân loại các véc tơ đặc trưng [12] giới thiệu thuật toán DT-CLGBI, sử dụng cây quyết định cho việc phân lớp đồ thị, với mỗi nút đại diện cho một đồ thị con Cuối cùng, [16] đề xuất một phương pháp dựa trên SVM để phân lớp đồ thị thông qua việc phát triển các nhân đồ thị.
2.4.2.2 Một số kỹ thuật phân lớp đồ thị a SUBDUE
Thuật toán Subdue, được đề xuất bởi Agrawal và Srikant, là một phương pháp quan trọng trong phân lớp đồ thị Thuật toán này sử dụng tư tưởng tham lam và tìm kiếm heuristic để xác định các đồ thị con xuất hiện trong mẫu dương nhưng không có trong mẫu âm Không gian tìm kiếm của Subdue bao gồm tất cả các đồ thị con liên thông từ các đồ thị được gán nhãn trong mẫu dương.
Subdue thực hiện việc tìm kiếm bằng cách bắt đầu từ các đồ thị con, bao gồm tất cả các đỉnh có nhãn đơn nhất Quá trình này mở rộng các đồ thị con thông qua việc thêm một đỉnh và một cạnh.
Có 32 cách hoặc nhiều hơn để tạo ra các đồ thị con ứng cử dựa trên đồ thị đầu vào Subdue giữ lại các đồ thị con này và áp dụng tính đẳng cấu đồ thị để xác định các cấu trúc con ứng cử Các cấu trúc này được đánh giá dựa trên độ chính xác trong phân lớp và khái niệm độ dài mô tả cực tiểu.
Độ dài của tia tìm kiếm ảnh hưởng đến số lượng cấu trúc con có thể được mở rộng sau này Quy trình này lặp đi lặp lại cho đến khi tất cả các cấu trúc đã được xem xét hoặc độ phức tạp tính toán vượt quá ngưỡng mà người dùng quy định Khi kết thúc quy trình, các mẫu dương từ cấu trúc tốt nhất sẽ bị loại bỏ Tiến trình tìm kiếm và loại bỏ các mẫu dương sẽ tiếp tục cho đến khi tất cả các mẫu dương được khám phá.
Mô hình Subdue sử dụng danh sách quyết định, trong đó mỗi thành viên là một đồ thị liên thông, để phân loại các mẫu chưa biết Việc kiểm tra tính đẳng cấu của đồ thị con cho phép dự đoán: nếu một đồ thị trong danh sách xuất hiện trong mẫu, nó sẽ được dự đoán là dương; ngược lại, nếu tất cả đồ thị trong danh sách đều vắng mặt, mẫu sẽ được dự đoán là âm Bên cạnh đó, việc khai phá đồ thị con phổ biến kết hợp với SVM cũng mang lại hiệu quả cao trong quá trình phân loại.
Tiếp cận được giới thiệu bởi T Asai và cộng sự cho việc phân lớp đồ thị bao gồm hai công việc chính: khai phá đồ thị con phổ biến và phân lớp SVM.
Kết luận
Trong chương 2, chúng tôi đã giới thiệu các kiến thức cơ bản về phân loại văn bản và các phương pháp phổ biến được áp dụng Tất cả các thuật toán phân loại này đều yêu cầu văn bản được biểu diễn dưới dạng vector.
Các thuật toán như KNN và NB yêu cầu ước lượng tham số và ngưỡng tối ưu để phân loại văn bản hiệu quả Để đảm bảo độ chính xác, cần có một tập dữ liệu huấn luyện chuẩn và đủ lớn cho quá trình học Tuy nhiên, các thuật toán này không hỗ trợ tính năng tăng cường, dẫn đến việc phải phân loại lại toàn bộ tập văn bản khi có thêm dữ liệu mới.
Bài viết này giới thiệu kiến thức nền tảng về phân loại văn bản dựa trên mô hình đồ thị, bao gồm các khái niệm cơ bản như đồ thị được gán nhãn, tính chất của đồ thị và đồ thị con Chúng tôi cũng đề cập đến một số thuật toán tiêu biểu cho bài toán phân lớp đồ thị, trong đó có các thuật toán nổi tiếng như gSpan, FSG, gFSG và GASTON Qua phân tích và đánh giá độ phức tạp cũng như phạm vi áp dụng, chúng tôi nhận thấy gSpan là lựa chọn phù hợp cho phân loại văn bản Luận văn này xây dựng mô hình phân loại văn bản dựa trên thuật toán gSpan kết hợp với bộ phân lớp SVM nhằm giải quyết bài toán phân loại văn bản hiệu quả.