Luận án Khai phá luồng văn bản với kỹ thuật gom cụm

định các đợt nổi bật dài hơn dù cho tốc độ 
của luồng có thay đổi. Khung tổng thể của thuật toán Kleinberg được đề xuất dựa trên 
các phương pháp Markov được sử dụng trong việc mô hình hóa sự nổi bật trong lưu 
lượng truy cập mạng, và các mô hình Markov ẩn. 
 Việc sử dụng automaton tự động có các trạng thái tương ứng với cường độ cao 
cung cấp thêm một nguồn để phân tích bổ sung - các sự nổi bật liên quan đến chuyển 
đổi trạng thái tạo thành một cấu trúc lồng nhau tự nhiên, với một đợt nổi bật dài cường 
độ thấp có khả năng chứa một số đợt nổi bật cường độ cao hơn bên trong (đệ quy). Đối 
với một thư mục gồm các e-mail có liên quan, có thể phân rã theo trật tự thời gian, với 
các tập dài hạn phân rã thành những tập ngắn gọn hơn theo cấu trúc cây tự nhiên. Do 
đó, cây này có thể được xem như là một một cấu trúc tổ chức các tập con trên luồng 
thông điệp. Có thể xem thêm các lý thuyết toán học về automaton ở công trình [42]. 
 38 
Ý tưởng thuật toán Kleinberg trong việc phát hiện sự nổi bật 
 Thuật toán xác định các khoảng thời gian khi một sự kiện “mục tiêu” (target) 
thường xuyên xuất hiện một cách bất thường, hay còn gọi là “nổi bật”. Thuật toán có 
thể được sử dụng để phát hiện các sự nổi bật trong một chuỗi sự kiện liên tục. Có một 
tập hợp các sự kiện, bao gồm cả các sự kiện “mục tiêu” và không phải “mục tiêu” (non-
target), được quan sát tại mỗi thời điểm t. Nếu chúng ta xem xét ví dụ về các bài viết, 
thì các sự kiện “mục tiêu” có thể bao gồm các bài viết có một từ khóa “mục tiêu” được 
nhắm đến và các sự kiện không phải mục tiêu có thể bao gồm tất cả các bài viết khác 
không bao gồm từ khóa “mục tiêu” đó. 
 Cho: là tổng số sự kiện tại mỗi thời điểm; là tổng số sự kiện đích; Tỷ lệ các sự 
kiện mục tiêu tại mỗi thời điểm được tính theo công thức (2.22): 
 = ⁄ (2.22) 
 Để phát hiện sự nổi bật, các trạng thái khác nhau được giả định tương ứng với các 
xác suất khác nhau của các sự kiện “mục tiêu”. Một trạng thái có thể có xác suất mục 
tiêu cao, thấp hoặc trung bình. Nếu giả định rằng chỉ có hai trạng thái có thể xảy ra, thì 
chúng ta có thể coi trạng thái có xác suất thấp hơn là trạng thái cơ bản và trạng thái có 
xác suất cao hơn là trạng thái nổi bật. 
 Xác suất cơ sở 0 bằng tỷ lệ tổng thể của các sự kiện “mục tiêu” (theo công thức 
(2.23)). 
 0 = ⁄ (2.23) 
trong đó r là tổng các sự kiện mục tiêu và d là tổng các sự kiện tại mỗi thời điểm. 
 Xác suất trạng thái bùng nổ “bursty” p1 bằng xác suất cơ sở nhân với một số hằng 
số s có thể được chọn khác nhau (theo công thức (2.24)). Nếu s lớn, xác suất các sự kiện 
“mục tiêu” cần phải cao để đạt trạng thái bùng nổ “bursty”. 
 1 = 푆 ∗ 0 (2.24) 
 39 
 Hình 2.4: Tỉ lệ của các sự kiện mục tiêu 
 Hình 2.4 trình bày một ví dụ về tỷ lệ các sự kiện “mục tiêu”. Mục tiêu các sự kiện 
thường được mong đợi xảy ra với xác suất liên quan đến trạng thái của chúng. Tuy nhiên, 
tỷ lệ các sự kiện mục tiêu có thể cao hơn hoặc thấp hơn dự kiến do biến số nhiễu (noise) 
ngẫu nhiên. 
 Với tỷ lệ quan sát được của các sự kiện “mục tiêu”, thuật toán phát hiện Burst sẽ 
có thể xác định thời điểm hệ thống có thể ở trạng thái cơ bản hoặc trạng thái nổi bật. 
Điều này phụ thuộc vào: 
 Mức độ phù hợp giữa tỷ lệ quan sát được và xác suất mong đợi của mỗi 
 trạng thái. Hệ thống có nhiều khả năng mang một trạng thái hơn nếu tỷ lệ quan 
 sát được càng gần với xác suất mong đợi của trạng thái đó. Nó được ký hiệu là 
 sigma, được định nghĩa theo công thức (2.25): 
 푡 푡 푡− 푡 (2.25) 
 휎(푖, 푡, 푡) = − ln[( ) ( 푖 (1 − 푖) )] 
 푡
 Khó khăn khi chuyển đổi từ trạng thái trước sang trạng thái tiếp theo. Giữ 
 nguyên trạng thái cũ hoặc trở lại trạng thái thấp hơn không tốn kém gì, do đó chi 
 phí chuyển đổi, ký hiệu là 휏 = 0. Khi chuyển sang trạng thái cao hơn, phải 
 mất chi phí, do đó, chi phí chuyển đổi được định nghĩa theo công thức (2.26): 
 휏 = (푖푛푒 푡 − 푖 푒푣 ∗ 훾 ∗ ln(푛)) (2.26) 
 40 
 với n là số điểm thời gian; và gamma là độ khó trong việc chuyển đổi sang các 
 trạng thái cao hơn (các giá trị gamma cao hơn làm cho việc chuyển đổi sang trạng 
 thái bùng nổ hơn khó khăn hơn). 
 Tổng chi phí chuyển đổi từ trạng thái này sang trạng thái khác bằng tổng của hai 
 hàm (2.25) và (2.26). Với hàm chi phí, có thể tính được chuỗi trạng thái q tối ưu 
 để giảm thiểu tổng chi phí. Chuỗi trạng thái tối ưu này có thể được tìm thấy với 
 thuật toán Viterbi bằng cách thực hiện một số bước đơn giản sau đây. Đầu tiên, 
 thuật toán bắt đầu với việc tính toán chi phí ở mỗi trạng thái tại 푡 = 1 và chọn 
 trạng thái có chi phí tối thiểu. Sau đó, hệ thống sẽ tính toán chi phí chuyển đổi từ 
 trạng thái hiện tại ở 푡 = 1 sang từng trạng thái có thể có tại 푡 = 2, và lại chọn 
 trạng thái có chi phí tối thiểu. Các bước này được lặp lại cho tất cả các mốc thời 
 gian để cuối cùng có được một chuỗi trạng thái mà hàm chi phí là nhỏ nhất. Dựa 
 trên trình tự trạng thái, chúng ta biết khi nào hệ thống ở trạng thái tăng cao hoặc 
 trạng thái nổi bật. Thuật toán có thể được thực hiện cho các sự kiện “mục tiêu” 
 khác nhau để xây dựng khoảng thời gian về những sự kiện phổ biến theo thời 
 gian. 
 Công thức (2.27) có thể được sử dụng để ước tính cường độ (hoặc trọng số/chỉ 
 số độ quan trọng) của một sự nổi bật (bắt đầu tại thời điểm t1 và kết thúc tại thời 
 điểm t2 và được gán nhãn 푡1 − 푡2): 
 푤푒푖 ℎ푡 = 푠 푡2 (휎(0, , ) − 휎(1, , )) (2.27) 
 푡=푡1 푡 푡 푡 푡
 Công thức này cho thấy chi phí phù hợp giảm bao nhiêu khi nhận được trạng thái 
 nổi bật so với trạng thái cơ bản trong giai đoạn nổi bật. Chi phí phù hợp càng 
 giảm, trọng số càng lớn và sự nổi bật càng mạnh. 
2.2 Kết chương 
 Trong chương này, luận án trình bày các công trình nghiên cứu liên quan như 
mô hình chủ đề, mô hình hỗn hợp dựa trên quy trình Dirichlet và một số nguyên 
lý liên quan, đồ thị hóa văn bản, kỹ thuật tìm đồ thị con phổ biến (thuật toán 
gSpan), thuật toán phát hiện sự nổi bật trên luồng dữ liệu văn bảnlàm cơ sở để 
xây dựng các thuật toán của luận án. 
 41 
 CHƯƠNG 3: GOM CỤM LUỒNG VĂN BẢN THEO NGỮ 
 NGHĨA DỰA TRÊN ĐỒ THỊ TỪ 
 Chương này trình bày phương pháp tiếp cận được đề xuất của luận án dựa trên mô 
hình hỗn hợp giúp tận dụng đánh giá mối quan hệ đồng hiện của từ bằng cách áp dụng 
phương pháp phân phối biểu đồ của từ phổ biến (GOW) trên các tài liệu trong một luồng 
văn bản nhất định, được gọi là GOW-Stream. GOW-Stream là một phương pháp gom 
cụm luồng văn bản đa thức theo quy trình Dirichlet (DPMM) có thể cải thiện đáng kể 
chất lượng của việc gom cụm các luồng văn bản ngắn với nội dung rời rạc. Phần đầu 
tiên của chương giới thiệu ngắn gọn cách tiếp cận rút trích đồ thị từ (GOW) phổ biến từ 
các tài liệu văn bản bằng cách áp dụng phép đồ thị hóa văn bản text2graph và kỹ thuật 
khai phá đồ thị con phổ biến (FSM). Nội dung tiếp theo trình bày một kỹ thuật suy luận 
chủ đề mới chủ yếu dựa trên mô hình MStream/MStreamF đã được công bố trước đó 
(năm 2018), các phân phối đa thức của tài liệu được biểu thị dưới dạng phân phối của 
các từ xuất hiện và đồ thị con phổ biến. Qua đó, cả từ độc lập và đồ thị con phổ biến 
trong mỗi tài liệu của một luồng văn bản đều được xem xét cẩn thận trong quá trình hình 
thành chủ đề. 
 Một phần của chương này được công bố trong bài báo “GOW-Stream: a novel 
approach of graph-of-words based mixture model for semantic-enhanced text stream 
clustering” và đã được chấp nhận đăng trong tạp chí “Intelligent Data Analysis” thuộc 
danh mục SCIE, Q3 năm 2020. 
3.1 Phương pháp 
 Phần này giới thiệu sơ nét các các phương pháp mà mô hình GOW-Stream sử dụng, 
so sánh với phương pháp truyền thống khác. 
3.1.1 Biểu diễn đặt trưng văn bản bằng phương pháp túi từ (BOW) 
Ví dụ về biểu diễn theo lối truyền thống. Giả sử cho tập văn bản ={ 1, 2, 3} gồm 
các văn bản: 
 1 = {푤1, 푤2, 푤3}, với 푤1 = , 푤2 = , 푤3 = 
 2 = {푤1, 푤2, 푤3, 푤4}, với 푤1 = , 푤2 = , 푤3 = , 푤4 = ; 
 3 = {푤1, 푤2, 푤3, 푤4, 푤5,, 푤6 }, với 푤1 = , 푤2 = , 푤3 = , 푤4 = , 푤5 =
 , 푤6 = ; 
 42 
 Phương pháp BOW truyền thống biểu diễn các văn bản như trong Bảng 3.1. 
 Bảng 3.1: Biểu diễn văn bản với BOW truyền thống 
 Văn Chiều dài văn bản Chiều dài văn bản sau khi Biểu diễn 
 a b c d 
 bản ban đầu loại bỏ từ trùng véc tơ 
 1 1 1 1 0 3 3 [1,1,1,0] 
 2 1 1 1 1 4 4 [1,1,1,1] 
 3 2 1 2 1 6 4 [2,1,2,1] 
 Bảng 3.1 mô tả khái quát cách biểu diễn văn bản với túi từ truyền thống đối với 3 
văn bản đã cho là 1, 2, 3 với chiều dài sau khi loại bỏ từ trùng lần lượt là 3,4,4. Như 
vậy, kích thước của ma trận các véc tơ biểu diễn tập văn bản sẽ là 3x4 và từng véc tơ có 
giá trị tương ứng như cột “Biểu diễn véc tơ” trong Bảng 3.1. 
Ví dụ về sử dụng TF-IDF để biểu diễn. Với TF-IDF, các văn bản đã cho được biểu 
diễn như trong Bảng 3.2. 
 Bảng 3.2: Biểu diễn văn bản với BOW và TF-IDF 
 Chiều dài Chiều dài Biểu diễn véc tơ 
 Văn TF- TF- TF- TF- văn bản văn bản sau 
 bản IDF(a) IDF(b) IDF(c) IDF(d) khi loại bỏ từ 
 trùng 
 1 0 0 0 0 3 3 [0,0,0,0] 
 2 0 0 0 0,04 4 4 [0;0;0;0,04] 
 3 0 0 0 0,03 6 4 [0;0;0;0,03] 
 Bảng 3.2 trình bày ví dụ về phương pháp biểu diễn văn bản với túi từ truyền thống 
đối với 3 văn bản đã cho là 1, 2, 3 có sử dụng thêm kỹ thuật TF-IDF để tính tần số 
xuất hiện của các từ tương ứng trong văn bản. Sau đó, véc tơ biểu diễn văn bản sẽ có giá 
trị là các tần số từ được tính bằng kỹ thuật TF-IDF. 
 43 
3.1.2 Biểu diễn văn bản bằng đồ thị từ (GOW) 
 Kỹ thuật đồ thị hóa văn bản Text2graph. Biểu diễn tài liệu văn bản dựa trên 
GOW là một cách tiếp cận NLP nổi tiếng nhằm mục đích biểu diễn tài liệu văn bản d 
thành cấu trúc dựa trên đồ thị, được ký hiệu là: Gd = (Vd, Ed) với tập hợp các nút (Vd) 
và các cạnh (Ed) đại diện cho tập hợp các từ phân biệt, như W = {w1, w2  w|W|}, được 
xuất hiện trong tài liệu d và quan hệ đồng xuất hiện tương ứng giữa các từ này. Các quan 
hệ đồng xuất hiện giữa các từ có thể được rút trích linh hoạt dựa vào một cửa sổ trượt 
được xác định trước. Đây còn được gọi là kỹ thuật đồ thị hóa văn bản text2graph, phương 
pháp thống kê để biểu diễn các mối quan hệ đồng xuất hiện giữa các từ trong văn bản 
mà không cần cân nhắc về ý nghĩa ngữ nghĩa giữa các từ. Các đồ thị dạng văn bản sau 
khi biến đổi có thể có hướng hoặc vô hướng. Cách triển khai đơn giản nhất của biểu 
diễn GOW cho tài liệu văn bản là sử dụng đồ thị vô hướng để biểu diễn quan hệ đồng 
xuất hiện giữa các từ (minh họa trong Hình 3.1) được áp dụng trong mô hình đề xuất 
GOW-Stream. Trong trường hợp cần xem xét thứ tự xuất hiện của các từ trong tài liệu, 
các đồ thị được xây dựng nên là đồ thị có hướng. Để triển khai nâng cao phương pháp 
tiếp cận text2graph, có thể cân nhắc để tính đến tần suất xuất hiện đồng thời của hai từ 
và gán nhãn bằng chú thích từng phần của từ cho các đồ thị văn bản đã xây dựng. Trong 
nghiên cứu này, luận án sử dụng đồ thị vô hướng và phương pháp biểu diễn mối quan 
hệ đồng xuất hiện của từng cặp từ trong văn bản làm nền tảng để biểu diễn văn bản. 
 lazy big brown
 jumped
 [JJ]
 dog [JJ] [JJ]
 amod amod
 over fox the
 amod fox
 lazy [DT] det
 [NN]
 det
 the brown case
 dog jumped over
 big nsubj
 [NN] [VBD] [IN]
 Hình 3.1: Hình ảnh minh Ah.ọ a Simplecấu trúc đ ồgraph thị hóa -vănof b-ảwordsn (text2graph) với đồ thị Bvô. Complex graph-of-words 
 (GOWs) structure (GOWs) structure 
 hướng 
 Hình 3.1 minh họa cho việc biểu diễn bằng đồ thị văn bản có nội dung là “The 
lazy dog jumped over the big brown fox”. Sau khi loại bỏ từ trùng (“the”) thì văn bản 
 44 
còn lại 8 từ tương ứng với 8 đỉnh của đồ thị. Các cặp từ đứng gần nhau (trong văn bản 
d trước khi loại bỏ từ trùng) sẽ được biểu diễn bằng các cung nối (có tổng cộng 8 cung): 
the-lazy, lazy-dog, dog-jumped, jumped-over, over-the, the-big, big-brown, brown-fox. 
 Đồ thị con phổ biến là đặc trưng cho tài liệu. Tiếp theo, với một tập hợp các đồ 
thị dạng văn bản đã xây dựng = {G1, G2,  G|D|) từ một kho văn bản nhất định (D), 
với V và E là tập hợp các từ xuất hiện đặc biệt W là các nút của đồ thị và các quan hệ 
đồng xuất hiện tương ứng của chúng. Sau đó, luận án áp dụng các kỹ thuật khai phá đồ 
thị con phổ biến, chẳng hạn như: gSpan, FFSM, vv... để rút trích ra tập hợp các đồ thị 
 ′ ′ ′
con phổ biến, được ký hiệu là: F = {G1, G2  G|F|}, trong đó mỗi đồ thị con phổ biến: 
 ′ ′ ′ ′ ′
Gf = (Vf, Ef), với Vf ∈ V và Ef ∈ E, được dùng để biểu diễn đặc trưng phân biệt cho các 
 ′
tài liệu đã cho có chứa đồ thị con Gf. Khác với việc sử dụng các từ phổ biến làm các đặc 
trưng phân biệt để biểu diễn văn bản, hay còn gọi là biểu diễn theo túi từ (BOW), việc 
sử dụng các đồ thị con phổ biến để biểu diễn văn bản mang tính ngữ nghĩa hơn do khả 
năng nắm bắt các mối quan hệ đồng xuất hiện của các cặp từ (n-gram với n=1) được áp 
dụng vào mô hình đề xuất. 
 Biểu diễn tài liệu kết hợp BOW và GOW. Kết hợp với biểu diễn dựa trên BOW 
cổ điển, một tài liệu d bây giờ được phân rã thành bộ giá trị sau (như thể hiện trong công 
thức (3.1)): 
 ⟨Wd: Nd|퐅퐝⟩ (3.1) 
Với: 
 Wd là tập hợp các từ duy nhất xuất hiện trong tài liệu 
 w
 Nd là tần số của chúng được biểu diễn dưới dạng vectơ Nd, trong đó Nd là tần số 
 w
 xuất hiện của (w) cụ thể trong tài liệu đã cho d hay Nd = ∑w∈d Nd . 
 Fd là tập các đồ thị con phổ biến của tài liệu d. 
 Đối với mỗi tập đồ thị con phổ biến Fd trong tài liệu , mỗi đồ thị con phổ biến chỉ 
xuất hiện một lần, do đó không cần tính tần suất xuất hiện của đồ thị con phổ biến trong 
mỗi tài liệu (vì luôn là 1). Thuật toán 3.1 do luận án đề xuất minh họa các bước để rút 
trích đồ thị con phổ biến từ một kho ngữ liệu văn bản thô nhất định với thuật toán gSpan 
[92] để khai phá đồ thị con văn bản phổ biến. Tóm lại, ý tưởng quan trọng đằng sau 
gSpan là thay vì liệt kê tất cả các đồ thị con và kiểm tra tính đẳng cấu trong toàn bộ bộ 
sưu tập, trước tiên nó xây dựng cho mỗi đồ thị một thứ tự từ vựng của tất cả các cạnh 
bằng cách sử dụng tìm kiếm Depth First Search (DFS) và gán cho nó một mã DFS tối 
thiểu duy nhất. Dựa trên tất cả các mã DFS này, cây tìm kiếm phân cấp được xây dựng 
 45 
ở cấp bộ sưu tập. Bằng cách sắp xếp trước việc duyệt cây này, gSpan phát hiện ra tất cả 
các đồ thị con phổ biến thỏa ngưỡng min support σ yêu cầu. 
 Thuật toán 3.1: Rút trích các đồ thị con phổ biến từ tập tài liệu đã cho (D) 
Input: 
 Tập tài liệu D 
 Cửa sổ trượt s=1//chỉ xét từng cặp từ 
 Ngưỡng support nhỏ nhất 휎=0,2//(20%). 
Output: Tập các đồ thị con phổ biến của tập tài liệu D, ký hiệu: FD 
1: Function ExtractGOWs(D, σ) 
2: Initialize: GD = {} #Khởi tạo tập các GOW của tập tài liệu , ký hiệu 
3: For document d in D: 
4: Initialize: Gd = Text2Graph(d)#Khởi tạo từng đồ thị từ 
5: Update: GD. append(Gd)#Cập nhật vào tập đồ thị từ 
6: End for 
7: Initialize: FD = gSpanAlgorithm(GD, σ) #Tìm tập đồ thị con phổ biến 퐹 
8: Return FD 
9: End function 
10: Function Text2Graph(d): 
11: Initialize: G #cấu trúc đồ thị của tài liệu 
12: Initialize: Wd = {}, WSeqd = {}#Danh sách từ, ds từ theo thứ tự của tài liệu 
13: For word w in tokenize(d): 
14: If w not in Wd: Wd.append(w)#Tạo ds từ không trùng 
15: Update: WSeqd.append(w) #Tạo ds từ theo thứ tự 
16: End for 
17: Update: G. nodes. create(Wd) #Tạo tập các nút từ tập từ không trùng đã có 
18: For word w in WSeqd: 
19: For i in range(0, s): 
 Update: G. edges. create([w], [Seq [w − i])#Tạo cạnh với từ phía 
20: d
 trước 
 Update: G. edges. create([w], [Seq [w + i]) #Tạo cạnh với từ phía 
21: d
 sau 
22: End for 
23: End for 
24: Return G 
 46 
 25: End function 
 26 Function gSpanAlgorithm (GD, σ): 
 27: Initialize: FD = {} #lưu các đồ thị con phổ biến của tập tài liệu 
 28: For Gd in GD: 
 29: For c in children(Gd): #Duyệt tất cả các đồ thị con của Gd 
 If support(c, G ) 휎: Update: F . append(c)#Cập nhật đồ thị con phổ 
 30: D D
 biến tương ứng vào tập đồ thị con phổ biến 퐹 
 31: End for 
 32: End for 
 33 Return FD 
 34 End function 
 Như vậy, Thuật toán 3.1 tìm đồ thị con phổ biến của tập tài liệu là ExtractGOWs 
có thể tóm tắt thành các bước như sau: 
 (1)- Với mỗi tài liệu trong tập tài liệu , hệ thống khởi tạo GOW của tài liệu 
là (dòng 2) và cập nhật vào danh sách GOW của tập tài liệu sử dụng hàm 
Text2Graph(d) (dòng 4 và 5). 
 (2)- Hệ thống tìm tập đồ thị con phổ biến 퐹 tương ứng với tập tài liệu bao gồm 
các tập đồ thị con phổ biến 퐹 của từng tài liệu sao cho 퐹 chỉ chứa các đồ thị con phổ 
biến có tần số xuất hiện lớn hơn ngưỡng phổ biến tối thiểu minsupp σ sử dụng thuật 
toán gSpan, thuật toán tìm đồ thị con phổ biến của tài liệu (dòng 7). 
 Hàm Text2Graph(d) có thể tóm tắt thành các bước sau: 
 (1)- Hệ thống khởi tạo cấu trúc đồ thị G của tài liệu (dòng 11) 
 (2)-Hệ thống khởi tạo danh sách sách từ 푊 không trùng và từ theo thứ tự 
푊푆푒푞 của tài liệu (dòng 12) 
 (3)- Với mỗi từ trong danh sách từ 푊 của tài liệu , hệ thống tạo đỉnh cho đồ thị 
Gd sau đó dựa vào danh sách từ theo thứ tự 푊푆푒푞 của tài liệu , hệ thống tạo cạnh cho 
đồ thị Gd (dòng 18 - 23) 
 * Đỉnh đồ thị chỉ có một từ duy nhất nên tham số trượt s (trong n-gram) được thiết 
lập là 1. 
 Có thể tóm tắt các bước của hàm gSpanAlgorithm như sau: 
 47 
 (1)- Hệ thống khởi tạo cấu trúc FD để lưu các tập đồ thị con phổ biến của tập tài 
liệu D (dòng 27). 
 (2)- Với mỗi tập đồ thị từ Gd của tài liệu thuộc về tập đồ thị từ GD của tập tài liệu 
D, hệ thống duyệt tất cả đồ thị con của Gd và thêm các đồ thị con thỏa min support α 
vào tập FD tương ứng (dòng 28-32). 
 Ví dụ về biểu diễn văn bản bằng đồ thị và tìm đồ thị con phổ biến. Phần sau 
đây trình bày ví dụ về biểu diễn văn bản bằng GOW. 
 Giả sử cho tập văn bản ={ 1, 2, 3} gồm các văn bản 
 1 = {푤1, 푤2, 푤3}, với 푤1 = , 푤2 = , 푤3 = 
 2 = {푤1, 푤2, 푤3, 푤4}, với 푤1 = , 푤2 = , 푤3 = , 푤4 = ; 
 3 = {푤1, 푤2, 푤3, 푤4, 푤5,, 푤6 }, với 푤1 = , 푤2 = , 푤3 = , 푤4 = , 푤5 =
 , 푤6 = ; 
 Ta có thể biểu diễn cho tập bằng đồ thị từ và được tập đồ thị từ tương ứng =
 1 2 3
{ , , }, với: 
 1
 = 푊( 1); 
 2
 = 푊( 2); 
 3
 = 푊( 3); 
 Tập đồ thị từ có thể được minh họa bằng các hình vẽ như sau: 
 a 
 a a 
 d 
 b b d b 
 c 
 c c 
 1 2 3
 Hình 3.2: Biểu diễn đồ thị từ của tập tài liệu 
 48 
 1 2 3
 Vậy ta tìm ra được tập = { , , } 
 Giả sử ta dùng thuật toán gSpan để tìm đồ thị con phổ biến với ngưỡng min support 
= 50%, ta được các đồ thị con phổ biến trên toàn tập D gồm: 
 a 
 a 
 d 
 b b 
 c c 
 1 2
 Hình 3.3: Tập đồ thị con phổ biến chung của tập tài liệu 
 1 2
 Như vậy, tập các đồ thị con phổ biến là 퐹 = { , } và: 
 1 1
 1 có 1 đồ thị con phổ biến là , ta có tập đồ thị con phổ biến của 1 là =
 1
{ } 
 1 2
 2 có 2 đồ thị con phổ biến là và , ta có tập đồ thị con phổ biến của 2 là 
 2 1 2
 = { , } 
 1 2
 3 có 2 đồ thị con phổ biến là và , ta có tập đồ thị con phổ biến của 3 là 
 3 1 2
 = { , } 
 Và ta có tập đồ thị con phổ biến cuối cùng như sau: 
 1 2 3 1 2 3
 퐹 = { , , } hay gọi tắt FD = { , , } 
 Vậy, sử dụng đồ thị con phổ biến để biểu diễn các văn bản như trong Bảng 3.3. 
 Bảng 3.3: Biểu diễn văn bản với GOW 
 Văn bản 풇푮 풇푮 Số đồ thị con phổ biến Biểu diễn véc tơ 
 1 1 0 1 [1,0] 
 2 1 1 2 [1,1] 
 3 1 1 2 [1,1] 
 49 
 Bảng 3.3 trình bày ví dụ về cách biểu diễn văn bản sử dụng đồ thị từ đối với 3 văn 
bản được cho là 1, 2, 3. Đầu tiên, các văn bản được đồ thị hóa. Tiếp theo, hệ thống 
tìm tập đồ thị con phổ biến với thuật toán gSpanAlgorithm theo ngưỡng min support 
 1 2
được thiết lập là 50% được tập đồ thị con phổ biến là 퐹 = { , }. Dựa vào kết quả 
này, véc tơ biểu diễn của các văn bản sẽ có số chiều là 2 vì tập đồ thị con phổ biến có 2 
đồ thị con phổ biến và các véc tơ này được biểu diễn giá trị tương ứng như trong Bảng 
3.3, cột “Biểu diễn véc tơ”. 
 Khi kết hợp giữa BOW và GOW trong mô hình luận án đề xuất GOW-Stream, các 
văn bản được biểu diễn như Bảng 3.4. 
 Bảng 3.4: Biểu diễn văn bản kết hợp BOW và GOW 
 Chiều Biểu diễn véc tơ 
 Văn bản BOW GOW dài văn 
 bản 
 1 0 0 0 0 1 0 3 [0,0,0,0,1,0] 
 2 0 0 0 0,04 1 1 4 [0;0;0;0,04;1;1] 
 3 0 0 0 0,03