Khóa luận Sử dụng phương pháp xếp hạng trong bài toán phân cụm tiếng việt

2 2 c c c d d d μ μ μ μ η γ γ − − − − − Δ = Σ Tồn tại nhiều quy tắc cập nhật khác có thể được sử dụng. Gán “mềm” không làm mất đi liên kết chặt trong việc tạo nên phân bố các tài liệu cho một cụm đơn đạt được một cách tỉ mỉ[6]. b. Thuật toán STC (Suffix Tree Clustering) Theo [11][13] STC là thuật toán phân cụm dựa vào việc nhận dạng các cụm từ thường xuyên xuất hiện trong một nhóm văn bản. Trong hoàn cảnh của chúng ta, một cụm từ là một chuỗi có trình tự của một hoặc nhiều hơn một từ. Chúng ta định nghĩa 12 một base cluster (cụm cơ sở) là một tập hợp các văn bản cùng chia sẻ một cụm từ nào đó. Thuật toán gồm ba bước: (1) “làm sạch” tài liệu (document “learning”), (2) xác định các cụm cơ sở (base clusters) sử dụng cây hậu tố, (3) trộn các cụm cơ sở tạo thành các cụm. (1)Trong bước làm sạch tài liệu, xóa tất cả các hậu tố và tiền tố của các từ nếu có, đưa toàn bộ số nhiều về số ít, loại bỏ các ký tự không phải là một từ (như các thẻ HTML, hệ thống dấu chấm câu), các từ trong tài liệu được giữ nguyên vị trí. (2) Xác định các cụm cơ sở: Theo định nghĩa trong [13] thì cây hậu tố T là một cây có hướng có gốc, biểu diễn một chuỗi s bất kỳ có chiều dài m với đúng m nút lá. Mỗi cạnh trên cây hậu tố đều được gán nhãn bằng một chuỗi con khác rỗng của chuỗi s. Các nhãn của hai cạnh bất kỳ xuất phát từ một nút chung phải bắt đầu bằng các ký tự khác nhau. Đối với nút lá của cây hậu tố, việc kết các nhãn của các nút nằm trên con đường đi từ gốc đến nút lá đó sẽ tạo thành một hậu tố của chuỗi s. Như tên của nó, cây hậu tố sẽ biểu diễn các chuỗi hậu tố của 1 từ hoặc một cụm từ. Chuỗi hậu tố là tập hợp các đơn vị từ hoặc chữ cái cạnh nhau đi sau từ hoặc cụm từ. Đơn vị từ ở đây có thể là chữ cái nếu xây dựng cây hậu tố cho từ, và là từ nếu xây dựng cây hậu tố cho 1 cụm Lấy ví dụ: Từ misisippi có các hậu tố là T1 = mississippi T2 = ississippi T3 = ssissippi T4 = sissippi T5 = issippi T6 = ssippi T7 = sippi T8 = ippi T9 = ppi T10 = pi 13 T11 = i Ta có thể sắp xếp lại từ tự dãy hậu tố trên như sau: T11 = i T8 = ippi T5 = issippi T2 = ississippi T1 = mississippi T10 = pi T9 = ppi T7 = sippi T4 = sissippi T6 = ssippi T3 = ssissippi Việc xây dựng như trên giúp ta xây dựng một cây với đặc điểm là: • Không có 2 nút nào cùng là con của một nút có nhãn cạnh như nhau. • Và có thể đưa ra tất cả các tập con với các đơn vị từ liên tiếp có đơn vị cuối là đơn vị cuối của từ, cụm từ được đưa vào phân tích. • Có một nút gốc sinh ra cây • Mỗi nút trong có ít nhất 2 nút con • Các nhãn được đặt phải có liên kết với nhau. • Với mỗi hậu tố của s, tồn tại một nút có nhãn là s. Cây hậu tố được tổ chức thành cây gồm nhiều nút. Mỗi nút sẽ lưu trữ tất cả các thông tin về các cụm từ ( tần số xuất hiện trong tập văn bản, tần số xuất hiện trong từng văn bản) trong khi quan hệ giữa chúng lại nói lên sự tồn tại của các cụm từ Trong phân cụm, người ta sử dụng cây hậu tố mở rộng để phân tích các câu: [11] Cây hậu tố mở rộng là cây hậu tố nhằm kết tất cả các hậu tố của các câu trong văn bản. 14 Tức là ta phân tích văn bản bằng cây hậu tố, mỗi câu được coi là một hậu tố, mỗi hậu tố của câu cũng là một hậu tố. Mỗi nút có thể là 1 tử, hoặc là 1 cụm từ đi liền. Sau đó xét tất cả các cụm được coi là hậu tố và xét quan hệ của chúng với nhau để nhóm lại thành một cây. Ví dụ một cây hậu tố với tập hợp các string là 3 câu: “cat ate cheese”, "mouse ate cheese too" , "cat ate mouse too". Phân tích với cây hậu tố với mỗi đơn vị là một từ. Ở trong văn bản gồm 3 câu này sẽ có các cụm từ được đưa ra lần lượt như sau: 1. cat [2]( 1 3) 2. cat ate [2]( 1 3) 3. cat ate cheese [1]( 3) 4. cat ate mouse [1]( 1) 5. cat ate mouse too [1]( 1) 6. ate [3]( 1 2 3) (ate xuất hiện 3 lần trong cả 3 câu) 7. ate cheese [2]( 2 3) 8. ate cheese too [1]( 2) 9. ate mouse [1]( 1) 10. ate mouse too [1]( 1) 11. cheese [2]( 2 3) 12. cheese too [1]( 2) 13. mouse [2]( 1 2) 14.mouse ate cheese [1]( 2) 15.mouse ate cheese too [1]( 2) 16. mouse too [1]( 1) 17. too [2]( 1 2] 15 và cây hậu tố chúng ta xây dựng được sẽ là tree1>|---cat ate cheese |---ate cheese |---cheese Tree2>|---mouse ate cheese too |---ate cheese too |--- cheese too |--- too Tree3>|---cat ate mouse too |---ate mouse too |--- mouse too |---too Coi mỗi hậu tố là một vector. Ta so sánh độ tương đồng giữa các vetor và dùng các thuật toán gom cụm để gom các câu trong văn bản lại và tổng hợp đưa ra vector đặc trưng cho câu. Cây cuối cùng được đưa ra là Tree􀃆|---cat ate|---cheese | |----mouse | |---ate|---cheese|---too | | |--- $ | |---mouse too | |---mouse|---too | |---ate cheese too |---cheese|---too | |---$ |---too 16 Hình 2: Cây hậu tố mở rộng Trong đó Node(a, b): a= hậu tố thuộc câu b= số thứ tự của lần xuất hiện chúng ta gán nhãn cho tất cả các nút trong của cây. Mỗi nhãn này tương đương với một từ hoặc một cụm từ nhận được từ các cạnh liền nhau từ gốc đến nhãn đó. Sau đó đánh giá các nút này. Node Cụm từ Văn bản a Cat ate 1, 3 b Ate 1, 2, 3 c Cheese 1, 3 d Mouse 2, 3 e Too 2, 3 F Ate cheese 1, 2 Bảng 2: Các tài liệu chứa cụm từ ở các node Và bằng cách này, cụm cơ sở được đưa ra dựa vào số văn bản mà cụm từ này xuất hiện và số từ trong cụm. Công thức: S(B) = |B| * f 17 Trong đó: |B| là số văn bản trong cụm cơ sở B |P| số lượng từ hợp pháp trong cụm P (have non zero score) zero score words: stopwords, quá ít(40%) hàm f không xác định với các cụm từ có độ dài bằng 1, là một hàm tuyến tính với những cụm từ có độ dài từ 2 đến 6 và sẽ không đổi với những cụm từ dài hơn 6. (3)Một vấn đề đặt ra là các văn bản có thể chứa nhiều cụm từ giống nhau. Vì thế với cách phân cụm cơ sở như trên thì việc 2 cụm cơ sở có chia sẻ chung một số văn bản có xác suất khá lớn. Để tránh việc trùng lấp này chúng ta trộn những cụm có chứa số văn bản dùng chung lại thành một cụm. Giả sử Bm and Bn là 2 cụm phân biệt. Gọi |Bm∩Bn| là tập hợp các văn bản thuộc cả 2 cụm trên. Chúng ta định nghĩa độ tương tự giữa 2 cụm là 1 nếu: |Bm∩Bn|/|Bm| >0.5 và |Bm∩Bn|/|Bn| > 0.5. Và là 0 trong trường hợp còn lại Hình 3: Kết quả sau khi trộn các tài liệu Xét trong ví dụ trên. Các thông số được thể hiện như hình trên. Mỗi nút là một cụm và mỗi cạnh nối với nhau thể hiện rằng độ tương tự giữa 2 cụm là lớn hơn 1 tức là các cụm có tồn tại một cạnh nối có thể hợp lại với nhau thành một cụm. như vậy sơ đồ trên thể hiện duy nhất một cụm. 18 Xét trong trường hợp của ví dụ này. Ta thấy b (ate) là một stopword, nút b sẽ được đánh giá là 0. Như vậy các cạnh nối từ b cũng bị bỏ đi và chúng ta có 3 cụm được đưa ra là “mouse too” “cat ate” “ate cheese” 1.3. Đánh giá các thuật toán phân cụm Như đã được giới thiệu, thuật toán AHC thường chậm khi áp dụng cho các tập tài liệu lớn. Các thuật toán khác theo hướng này như Single-link và Group-average có thời gian thực hiện là O(n2), đồng thời thời gian kết nối hoàn toàn (complete-link) là O(n3). Các thuật toán theo hướng này là quá chậm so với yêu cầu của bài toán phân cụm Web. Một điểm đáng chú ý nữa đối với các thuật toán HAC là điều kiện dừng. Đã có rất nhiều đề xuất về điều kiện dừng được đưa ra nhưng chủ yếu là dựa trên việc điều kiện dừng đã được xác định trước (chẳng hạn, dừng khi chỉ còn 5 cụm). Điều kiện dừng đối với các thuật toán này (HAC) là cực kỳ quan trọng. Nếu như thuật toán trộn các cụm “tốt” với nhau có thể tạo ra kết quả không theo mong muốn của người dùng. Trên Web, với kết quả trả về theo truy vấn là vô cùng đa dạng (về số lượng, độ lớn, kiểu và sự phù hợp của các tài liệu) thì điều kiện dừng không tốt sẽ làm cho kết quả trở nên nghèo nàn [6]. Thuật toán k-means thuộc vào lớp các thuật toán phân cụm thời gian tuyến tính và là những lựa chọn tốt nhất để đáp ứng yêu cầu về tốc độ của bài toán phân cụm online. Thời gian thực hiện của các thuật toán này là O(nk) trong đó k là số các cụm mong muốn [6]. Thêm một ưu điểm của thuật toán K-means so với HAC là việc đáp ứng các yêu cầu của bài toán phân cụm Web là nó có thể tạo ra các cụm có sự giao thoa. Điểm yếu chính của thuật toán này là nó chạy hiệu quả nhất chỉ khi các cụm mong muốn là các miền hình cầu đối với độ đo tương tự được dùng. Không có lý do gì để tin rằng các tài liệu sẽ thuộc vào các miền cầu. Vì vậy thuật toán có thể làm mất đi các thông tin có giá trị. Các thuật toán như HAC hay K-means đều không là các thuật toán gia tăng. Một số thuật toán gia tăng đã được phát triển như thuật toán phân cụm cây hậu tố (Suffix Tree Clustering - STC), với thời gian thực hiện O(n) trong đó n là kích thước của tập tài liệu[6]. 19 Chương 2. Phân cụm văn bản tiếng Việt 2.1. Đặc trưng của tiếng Việt và tách từ trong tiếng việt Có thể nói, khai phá web là giao thoa của khai phá dữ liệu, xử lý ngôn ngữ tự nhiên và Word-Wide-Web. Vì vậy để có thể làm việc được với các tài liệu web tiếng Việt cần phải tìm hiểu về các đặc trưng của tiếng Việt và việc tách từ tiếng Việt. 2.1.1. Đặc trưng của tiếng Việt Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp. Dưới đây trình bày một số đặc điểm của tiếng Việt theo các tác giả ở Trung tâm ngôn ngữ học Việt Nam đã trình bày Error! Reference source not found.. a. Đặc điểm ngữ âm Tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng", về mặt ngữ âm, mỗi tiếng là một âm tiết. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình, tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hoà về ngữ âm, đến nhạc điệu của câu văn. b. Đặc điểm từ vựng: Mỗi tiếng nói chung là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị có nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng..., chủ yếu nhờ phương thức ghép và phương thức láy. Việc tạo ra các đơn vị từ vựng ở phương thức ghép luôn chịu sự chi phối của quy luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát... Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ các ngôn ngữ khác để tạo ra các từ, ngữ mới, ví dụ như tiếp thị, karaoke, thư điện tử (e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thông tin, siêu liên kết văn bản, truy cập ngẫu nhiên, v.v. 20 Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn như chôm chỉa, chỏng chơ, đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v. Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, có thể có nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát huy cao độ trong các phong cách chức năng ngôn ngữ, đặc biệt là trong phong cách ngôn ngữ nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc biệt là công nghệ thông tin, thì tiềm năng đó còn được phát huy mạnh mẽ hơn. c. Đặc điểm ngữ pháp Từ của tiếng Việt không biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong tiếng Việt khi nói “Anh ta lại đến” là khác với “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp của từ mà "củ cải" khác với "cải củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em”, “anh vì em”. Hư từ cùng với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng có nội dung thông báo cơ bản như nhau nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây: - Ông ấy không hút thuốc. - Thuốc, ông ấy không hút. - Thuốc, ông ấy cũng không hút. Ngoài trật tự từ và hư từ, tiếng Việt còn sử dụng phương thức ngữ điệu. Ngữ điệu giữ vai trò trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng 21 dấu câu. Sự khác nhau trong nội dung thông báo được nhận biệt khi so sánh hai câu sau: - Đêm hôm qua, cầu gãy. - Đêm hôm, qua cầu gãy. Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta có thể hình dung được phần nào bản sắc và tiềm năng của tiếng Việt 2.1.2. Tách từ tiếng Việt Các tác giả [6][12]rút ra một số đặc điểm của từ tiếng Việt như sau: - là đơn vị có ranh giới trùng với hình vị và âm tiết - không có sự biến đổi hình thái trong quá trình sử dụng - là đơn vị có sẵn, được tái hiện trong khi nói - có tính định hình hoàn chỉnh - Có thể chia từ tiếng việt thành hai loại: từ đơn và từ phức Chính từ những đặc điểm này mà tách từ là một khó khăn chính trong việc xử lý các văn bản tiếng Việt. Mặc dù được viết bằng các ký tự La tinh mở rộng, tiếng Việt cũng có những đặc tính chung với các ngôn ngữ Đông Nam Á khác như khó xác định ranh giới giữa các từ và có các điểm khác biệt về phonetic, văn phạm và ngữ nghĩa so với tiếng Anh. Do đó, rất khó có thể áp dụng các kỹ thuật và hướng tiếp cận đã được nghiên cứu và thử nghiệm thành công trên tiếng Anh cho tiếng Việt nếu không xây dựng thành công giải pháp cho việc tách từ trong văn bản tiếng Việt. Dưới đây là một số điểm khác biệt chính giữa tiếng Việt và tiếng Anh được trình bày trong [12]. Đặc điểm Tiếng việt Tiếng Anh Đơn vị cơ bản Tiếng Từ Tiền tố/Hậu tố Không có Có Từ loại Not unanimous Được định nghĩa rõ Ranh giới từ Tổ hợp có nghĩa dựa vào ngữ cảnh của các tiếng Khoảng trắng hoặc dấu câu Bảng 3: So sánh một số đặc điểm của tiếng Việt và tiếng Anh 22 Những đặc điểm này làm cho việc tách từ tiếng việt trở nên khó khăn hơn. Dưới đây là kết quả khảo sát về tách từ trong văn bản tiếng hoa và thống kê về tách từ tiếng Việt được công bố hiện tại [12]. Hình 4: Thống kê về tách từ tiếng Hoa và tiếng Việt [12] Các hướng tiếp cận dựa trên “từ”: được chia thành 3 nhóm: dựa vào thống kê, dựa vào từ điển và nhóm lai, nhằm tách từ trọng vẹn trong câu. Các giải pháp dựa theo hướng tiếp cận vào thống kê cần phải dựa vào thông tin thống kê như term, từ hay tần số ký tự. hay xác suất cùng xuất hiện trong một tập dữ liệu cơ sở. Do đó, tính hiệu quả của các giải pháp này chủ yếu dựa vào dữ liệu huấn luyện cụ thể được sử dụng. Trong hướng tiếp cận dựa vào từ điển, các đoạn văn bản được đối sánh dựa vào từ điển. Việc xây dựng từ điển các từ và ngữ pháp tiếng việt hoàn chỉnh là không khả thi. Hướng tiếp cận lai áp dụng nhiều cách khác nhau để tận dụng ưu điểm của các giải pháp. Các hướng tiếp cận để phân loại văn bản tiếng việt dựa vào từ chỉ khả thi khi có một bộ từ vựng tốt. 23 Hướng tiếp cận dựa trên ký tự: có thể chia làm hai nhóm uni-gram và n-gram. Các phương pháp này tuy đơn giản nhưng đã đem lại kết quả khả thi. 2.2. Một số nghiên cứu về phân cụm tiếng Việt Cho đến nay đã có khá nhiều các công trình nghiên cứu về phân cụm trong tiếng Việt và đều đạt được những kết quả khả quan. Dưới đây, khóa luận sẽ trình bày ba nghiên cứu về phân cụm trong tiếng Việt là phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc [2], đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt [1], gom cụm đồ thị và ứng dụng vào việc trích rút nội dung chính của khối thông điệp trên diễn đàn thảo luận[3]. 2.2.1. Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc Nghiên cứu về phân cụm từ tiếng Việt là khá mới mẻ đối với bài toán tiếng Việt[2]. Bài toán phân cụm từ tiếng việt được phát biểu như sau: gọi X là câu đầu vào tiếng Việt bao gồm một dãy các từ tố ký hiệu X=(X1, X2,…, Xn). Cần xác định Y=(Y1,Y2,…, Yn) là một dãy các nhãn cụm từ (cụm danh từ, cụm động từ). Bài toán được qui về học đoán nhận dãy (có thể được thực hiện qua việc sử dụng các mô hình học máy ….). Qui trình học được thực hiện bằng cách gán nhãn câu mới ( không thuộc tập huấn luyện). Để thực hiện việc gán nhãn cụm cho câu tiếng việt, tác giả sử dụng hai mô hình học khá thông dụng bao gồm: Conditional Random Fields (CRFs) và Online Learing. Cả hai phương pháp đối với bài toán này đều dựa trên giả thuyêt các từ tố trong câu X=(X1, X2,…, Xn) tuân theo quan hệ của chuỗi Markov. Hoạt động của hệ thống góp nhóm từ tiếng việt được thể hiện ở hình dưới [2]: 24 Hình 5: Hệ thống phân cụm từ tiếng Việt theo phương pháp học máy cầu trúc Trong thực nghiệm, tác giả sử dụng dữ liệu huấn luyện từ VTB (VietTree Bank) cho bài toán phân cụm sử dụng mô hình CRFs và mô hình học Online Learning. Số lượng dữ liệu không nhiều (260 câu được gán nhãn) nhưng kết quả thực nghiệm rất khả quan. 2.2.2. Đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt Nhóm tác giả nghiên cứu về các phương pháp đánh giá chất lượng phân cụm và áp dụng đánh giá chất lượng kết quả phân cụm của máy tìm kiếm VNSEN. VNSEN là máy tìm kiếm dựa trên mã nguồn mở có tích hợp phân cụm do nhóm tác giả phát triển. Có nhiều phương pháp phân cụm khác nhau như k-mean, STC, HAC có thể áp dụng vào phân cụm các trang Web trả về của máy tìm kiếm. Và việc đánh giá thường dựa vào chất lượng kết quả phân cụm. Để người dùng có thể tìm được tài liệu mong muốn một cách nhanh chóng thì cần phải gán nhãn các cụm tốt. Tồn tại một số phương pháp đánh giá như sau [1]: - Đánh giá phân cụm dựa vào kinh nghiệm của người dùng: nhãn cụm cần ngắn gọn súc tích và không trùng lặp quá nhiều, số lượng cụm tạo ra vừa đủ để người dùng không bị quá tải bởi các chủ đề quá cụ thể, nhãn cụm cần tránh chứa các từ truy vấn. Thuật toán phân cụm phải đủ nhanh để có thể phân cụm với lượng thời gian phù hợp. Xử lý ngôn ngữ cũng rất quan trọng để tránh các từ gần nghĩa, đồng nghĩa. 25 - Các tiêu chí đánh giá độ kết dính và cô lập của các cụm: độ cô đọng súc tích là độ dính kết hoặc đơn nhất của mỗi cặp đối tượng trong từng cụm riêng rẽ. Độ cô lập đo sự tách biệt giữa hai cụm. Trong [1], Nguyễn Thi Thu Chung và cộng sự giới thiệu 4 tiêu chuẩn đánh giá chất lượng cho phân cụm để bảo đảm tính kết dính và độc lập là: giảm tối thiểu tổng khoảng cách (tổng khoảng cách giữa trọng tâm các cụm với trọng tâm toàn cục và tổng khoảng cách giữa đối tượng với trọng tâm của cụm chứa đối tượng), phân cụm sao cho độ tách biệt giữa các cụm là lớn nhất, vị trí cụm của đối tượng và số lượng đối tượng có vị trí cụm đúng. - Phương pháp đánh giá dựa vào tập dữ liệu mẫu: chọn một chuẩn cơ sở để so sánh khả năng phân cụm của bộ phân cụm: độ đo chất lượng phân cụm, đo chất lượng của một hệ thống phân cụm bởi các mức. Một số độ đo được sử dụng là MNI (normalized mutual information), độ hồi tưởng, độ chính xác, F, Purity (chỉ ra độ tinh khiết, rõ ràng của cụm i). Từ các phương pháp trên tác giả đã tiến hành đánh giá chất lượng phân cụm của máy tìm kiếm VNSEN dựa trên cây phân cấp chủ đề và so sánh với kết quả phân cụm của máy tìm kiếm vivisimo[1]. - Dựa vào cây phân cấp chủ đề: cây phân cấp chủ đề là một cấu trúc thư mục Web lớn nhất được xây dựng. Tác giả tiến hành thu thập tài liệu trên wikipedia tiếng Việt và tạo cây phân cấp thô ban đầu. Sau đó lọc ra các chủ đề chưa có tài liệu, các tài liệu chưa có nội dung hoặc chưa được dịch. Thực hiện tách các thẻ html. Hiện tại, đã xây dựng được cây phân cấp với 10 gốc chủ đề và 500 chủ đề các cấp. Thử nghiệm và thông qua hai độ đo là F và Purity cho thấy modul phân cụm có chất lượng tốt. - So sánh kết quả phân cụm với máy tìm kiếm vivisimo: lựa chọn các truy vấn tiếng Việt mang nghĩa tổng quát để phân cụm được rõ ràng. Tác giả lấy kết quả trả về của google và tiến hành phân cụm với VNSEN. Sau đó so sánh kết quả phân cụm của VNSEN và vivisimo. Nguyễn Thi Thu Chung và cộng sự [1] đã trình bày các phương pháp đánh giá chất lượng phân cụm và xây dựng cây phân cấp chủ đề dựa trên wikipedia tiếng Việt để phục vụ đánh giá. Qua đó đánh giá chất lượng phân cụm của VNSEN và đưa ra kết quả khả quan. 26 2.2.3. Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của khối thông điệp trên diễn đàn thảo luận Trong các hệ thống trực tuyến, diễn đàn thảo luận là phương tiện hữu hiệu để trao đổi và khối lượng thông tin trên diễn đàn là rất lớn. Để người quản lý có thể nắm bắt các nội dung chính của thông tin trao đổi trên diễn đàn trong một giai đoạn, cần xây dựng một hệ thống gom cụm các thông điệp, hỗ trợ trích rút nội dung chính trong khối thông điệp [3]. Đỗ Phúc và cộng sự trình bày cách sử dụng mạng Kohonen để gom cụm các đồ thị đặc trưng văn bản và rút trích các ý chính từ khối văn bản hỗ trợ tạo trích lược thông tin chính trong khối văn bản. Mạng Kohonen có thể gom cụm dữ liệu mà không cần định trước số cụm. Các bước thực hiện của phương pháp này như sau [3]: - Biều diễn văn bản bằng đồ thị: trích rút các từ phổ biến trong văn bản, tính các thành phần có ý nghĩa dựa trên tần suất xuất hiện đồng thời của hai từ trong một câu, đoạn văn bản. Nếu tần suất xuất hiện đồng thời của hai từ lớn hơn một ngưỡng cho trước thì sẽ xuất hiện một cung nối hai từ này. Ở đây, các từ tiếng Việt cũng được tách đúng các từ đơn và từ ghép nhằm tạo chính xác các đỉnh trong đồ thị. - Dữ liệu nhập vào mạng Kohonen là tập các đồ thị đặc trưng văn bản. Sau khi huấn luyện, các đồ thị nhập sẽ được gom vào các nút trên lớp ra của mạng Kohonen. (Kết quả huấn luyện mạng Kohonen sẽ tạo trên lớp ra Kohonen các cụm dữ liệu ứng với nhóm các nút gần nhau trên lớp ra Kohonen. Các mẫu học sẽ thuộc về cụm có khoảng cách gần nhất từ nó đến nowrron trong cụm. Các cụm có vị trí gần nhau trên mạng Kohonen sẽ chứa các đối tượng có mức độ tương tự cao). Qua thử nghiệm cho thấy hệ thống gom cụm văn bản biểu diễn bằng đồ thị có độ chính xác cao hơn so với gom cụm văn bản được biểu diễn bằng vector [3]. Trên đây là một số những nghiên cứu về phân cụm văn bản trong tiếng Việt. Các nghiên cứu đều cho những kết quả rất khả quan. Ở chương sau, khóa luận sẽ trình bày phương pháp phân cụm văn bản dựa theo việc xếp hạng các cụm từ quan trọng [10]. Tiếp đó là phần thực nghiệm với việc áp dụng kỹ __________thuật phân cụm này đối với các văn bản tiếng Việt là kết quả trả về của máy tìm kiếm Google 27 Chương 3. Phân cụm văn bản sử dụng phương pháp xếp hạng cụm từ quan trọng 3.1. Khái quát bài toán Với sự phát triển nhanh chóng của công nghệ thông tin thì các tài nguyên trên internet cũng ngày càng phong phú và đa dạng. Việc tìm kiếm thông tin trên internet là rất quan trọng và cần thiết đối với người sử dụng. Và việc tổ chức các kết quả tìm kiếm thành các cụm làm cho người sử dụng dễ dàng hơn trong việc duyệt các kết quả tìm kiếm. Theo [10] thì các kỹ thuật phân cụm truyền thống không phù hợp với phân cụm kết quả tìm kiếm bởi chúng tạo ra các tên cụm “khó đọc”. Vì vậy, phương pháp phân cụm ở đây sẽ đưa bài toán phân cụm về bài toán xếp hạng các cụm từ quan trọng. Đưa ra truy vấn và lấy về một danh sách các tài liệu đã được xếp hạng từ máy tìm kiếm, đầu tiên là tách các tài liệu thành các cụm từ, sau đó xếp hạng các cụm từ này. Các cụm từ cũng chính là tên các cụm ban đầu (candidate cluster). Việc xếp hạng các cụm từ dựa vào một mẫu hồi qui được học từ tập dữ liệu huấn luyện. Các tài liệu sẽ được gắn với các cụm từ quan trọng tạo thành các cụm với tên cụm chính là tên của cụm từ. 3.1.1. Nhu cầu về phân cụm các kết quả tìm kiếm Tài nguyên trên internet rất phong phú và đa dạng, có thể nói, người sử dụng có thể tìm kiếm thông tin về mọi lĩnh vực trên internet. Các máy tìm kiếm là công cụ tìm kiếm hỗ trợ rất tốt cho người sử dụng. Tuy nhiên, với các máy tìm kiếm khá phổ biến như Google [14], Yahoo [16], MSN [17] thì khi nhận một truy vấn từ người dùng, các máy tìm kiếm này thường trả về một danh sách dài các kết quả tìm kiếm. Các kết quả được xếp hạng theo sự phù hợp với truy vấn của người dùng dựa vào một số yếu tố như các từ khóa trong tài liệu, mức tương tự với truy vấn, dựa theo link liên kêt,… Tuy nhiên, danh sách kết quả trả về thường rất lớn. Thêm vào đó, đối với các truy vấn “nhập nhằng”, có nhiều chủ đề liên quan thì người dùng rất khó khăn và tốn nhiều thời gian xem xét các tiêu đề và đoạn tóm lược của tài liệu để tìm ra kết quả mong muốn. Ví dụ với truy vấn “việt nam” trên máy tìm kiếm google. Số kết quả trả về là rất lớn, vào khoảng 78 000 000. 28 Hì