Đối tƣợng và phạm vi nghiên cứu
Đối tƣợng nghiên cứu
- Nghiên cứu các tài liệu về bài toán phân loại văn bản đã công bố ở trong và ngoài nước;
- Nghiên cứu tài liệu về đặc trƣng các loại văn bản tiếng việt xây dựng hệ thống phân loại
- Nghiên cứu thuật toán K-means để ứng dụng trong bài toán phân loại văn bản
- Nghiên cứu xây dựng cơ sở dữ liệu phân loại văn bản
- Nghiên cứu ngôn ngữ lập trình C# và cài đặt cho bài toán phân loại văn bản
- So sánh, đánh giá hiệu quả của các thuật toán.
Phạm vi nghiên cứu
Bài toán phân loại văn bản có thể được thực hiện bằng nhiều thuật toán khác nhau như Nạve Bayes, K-NN (K-Nearest-Neighbor), Cây quyết định, Mạng Neuron nhân tạo và SVM (Support Vector Machine) Mỗi phương pháp này đều mang lại kết quả khả quan cho việc phân loại văn bản.
Trong luận văn này, tôi nghiên cứu thuật toán K-means để so sánh với các thuật toán phân loại khác Mục tiêu là xây dựng phần mềm ứng dụng bằng ngôn ngữ lập trình C# cho bài toán phân loại văn bản.
Mục đích, nhiệm vụ nghiên cứu
Luận văn tập trung vào 3 mục tiêu chính sau:
Nắm vững kiến thức về phương pháp học máy là rất quan trọng, đặc biệt là hiểu rõ cơ chế hoạt động của thuật toán phân loại văn bản Điều này giúp áp dụng hiệu quả vào các bài toán cụ thể trong thực tiễn.
(2) Nghiên cứu bài toán phân loại văn bản bằng các thuật toán k- means
(3) Nghiên cứu ngôn ngữ lập trình C# để cài đặt hệ thống phân loại văn bản và đánh giá hiệu quả của các thuật toán K-means.
Nội dung nghiên cứu
- Nghiên cứu tổng quan về các hệ thống phân loại văn bản đã đƣợc công bố
- Nghiên cứu các thuật toán tiền xử lý để nâng cao chất lƣợng văn bản cần xử lý
- Nghiên cứu các phương pháp để tìm đặc trưng tách từ tiếng việt
- Nghiên cứu thuật toán k-means để phân loại văn bản
- Nghiên cứu ngôn ngữ lập trình C# để cài hệ thống phân loại.
Đóng góp của luận văn
Thuật toán K-means, mặc dù có một số hạn chế, vẫn giữ vai trò quan trọng trong lĩnh vực học máy và là cơ sở cho nhiều thuật toán phức tạp khác Luận văn này tập trung chủ yếu vào ứng dụng của K-means trong phân loại văn bản.
Đặt vấn đề
Văn bản là phương tiện ghi chép và truyền đạt thông tin bằng ngôn ngữ hoặc ký hiệu, với hình thức và nội dung đa dạng tùy thuộc vào lĩnh vực văn hóa xã hội Chúng đóng vai trò quan trọng trong hoạt động quản lý, giúp ghi lại và truyền đạt các quyết định cũng như thông tin cần thiết trong quá trình quản lý.
Phân loại văn bản đóng vai trò quan trọng trong việc hỗ trợ người soạn thảo chọn lựa văn bản phù hợp với mục đích sử dụng Mỗi loại văn bản có nội dung, hình thức và chức năng riêng biệt, do đó việc hiểu rõ sự khác biệt này giúp nâng cao hiệu quả trong việc tạo lập và sử dụng văn bản.
Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, việc số hóa giấy tờ và văn bản đã trở thành xu hướng phổ biến, với tài liệu được lưu trữ trên máy tính và truyền tải qua Internet Tài liệu số mang lại nhiều ưu điểm như lưu trữ gọn nhẹ, thời gian bảo quản lâu dài và khả năng chỉnh sửa dễ dàng Sự gia tăng nhanh chóng của văn bản số, đặc biệt trên mạng toàn cầu, đã dẫn đến nhu cầu tìm kiếm văn bản tăng cao Do đó, việc phân loại văn bản tự động trở nên cần thiết hơn bao giờ hết.
Phân loại văn bản tự động là cần thiết để tìm kiếm thông tin một cách nhanh chóng và hiệu quả, thay vì phải lục lọi trong ổ đĩa lưu trữ Với khối lượng thông tin ngày càng gia tăng, việc tự động hóa quá trình phân loại giúp tiết kiệm thời gian và công sức Do đó, nghiên cứu các phương pháp phân loại văn bản trở thành một nhu cầu cấp thiết trong thời đại hiện nay.
Các phương pháp phân loại văn bản
Phân loại văn bản tự động đã được nghiên cứu rộng rãi và đạt nhiều kết quả tích cực Các phương pháp phổ biến hiện nay bao gồm Support Vector Machine (SVM), k-Nearest Neighbor (k-NN), và Linear Least Squares Fit.
Neural networks (Wiener et al., 1995), Nạve Bayes (Baker and Mccallum, 2000), and centroid-based methods (Shankar and Karypis, 1998) are all techniques that rely on statistical probability or the weighted information of words within a text.
Mỗi phương pháp phân loại văn bản có cách tính toán riêng, nhưng nhìn chung, tất cả đều phải trải qua một số bước cơ bản giống nhau.
Làm sạch dữ liệu là bước quan trọng trước khi tiến hành xử lý tập dữ liệu, bao gồm các vấn đề liên quan đến xử lý ngôn ngữ tự nhiên như loại bỏ khoảng trắng và kiểm tra chính tả.
Tách từ, hay còn gọi là words segmentation, là một bước cực kỳ quan trọng, đặc biệt là trong việc xử lý ngôn ngữ Tiếng Việt Trong phần tiếp theo, tôi sẽ trình bày chi tiết về quy trình này.
Feature Extraction là quá trình xác định và lựa chọn các đặc điểm nổi bật từ tập dữ liệu ban đầu Mục tiêu của bước này là tìm ra những đặc trưng tiêu biểu có tính đại diện cho dữ liệu, nhằm sử dụng làm đầu vào cho thuật toán phân lớp.
Training là quá trình sử dụng thuật toán học máy để xác định mô hình tốt nhất, giúp phân tích thông tin về sự xuất hiện của từ trong văn bản, như tần số và số văn bản chứa từ Qua đó, văn bản được chuyển đổi thành dạng vector Tùy thuộc vào phương pháp áp dụng, chúng ta sẽ sử dụng các công thức và phương thức tính toán khác nhau để thực hiện phân loại.
Trong lĩnh vực phân loại văn bản, việc áp dụng cho tiếng Anh đã đạt được nhiều thành tựu, trong khi đó, nghiên cứu về phân loại văn bản tiếng Việt vẫn còn nhiều hạn chế Một trong những nguyên nhân chính là khó khăn trong việc xử lý văn bản để xác định tần suất xuất hiện của từ Bước tách từ đóng vai trò quan trọng nhất trong quy trình phân loại, vì nếu sai ở bước này, việc phân loại sẽ không thể thành công Trong phần tiếp theo, chúng tôi sẽ trình bày về tách từ tiếng Việt và những đặc điểm đặc trưng của nó.
Ứng dụng của bài toán phân loại văn bản và các nghiên cứu liên quan
Từ trong tiếng Anh được định nghĩa là nhóm ký tự có nghĩa, dễ dàng tách biệt bởi khoảng trắng Ngược lại, trong tiếng Việt, việc xác định ranh giới từ phức tạp hơn nhiều, vì nó phụ thuộc vào ngữ cảnh câu Ví dụ, từ "clock" trong tiếng Anh tương ứng với "đồng hồ" trong tiếng Việt, nhưng có những từ đồng âm như "mĩ lệ" và "Mỹ Lệ", hay từ bao nhau như "giầy" và "giầy thể thao" Việc xác định ranh giới từ càng trở nên khó khăn nếu không nắm rõ ngữ nghĩa trong ngữ cảnh, như từ "nhà" và "nước" đều có ý nghĩa độc lập khi đứng riêng lẻ.
Giải quyết bài toán tách từ là bước quan trọng để phát triển các nghiên cứu liên quan đến xử lý ngôn ngữ tự nhiên, như phân loại văn bản, dịch tự động, kiểm tra lỗi chính tả và ngữ pháp Những ứng dụng này không chỉ thiết thực mà còn đáp ứng nhu cầu của cuộc sống con người, trở thành mục tiêu mà chúng ta đang hướng tới.
Một số nước châu như Trung Quốc, Nhật Bản, Hàn Quốc, Việt
Nam sử dụng ngôn ngữ có hình thái và cú pháp tương tự, cho phép áp dụng và cải tiến các phương pháp tách từ từ các nước khác, đặc biệt là Trung Quốc, vào việc tách từ tiếng Việt.
Theo Đinh Điền (2004), các phương pháp tách từ từ tiếng Hoa đã được áp dụng cho tiếng Việt bao gồm Maximum Matching (LRMM), giải thuật học cải biến TBL, mạng chuyển dịch trạng thái hữu hạn có trọng số (WFST) và giải thuật dựa trên nén Để đạt hiệu quả cao, điều kiện quan trọng là cần có một hệ thống từ điển và ngữ liệu đánh dấu đầy đủ, chính xác, vì từ điển hoặc ngữ liệu không hoàn chỉnh sẽ làm giảm hiệu suất của thuật toán.
Việc tạo ra một từ điển hoàn chỉnh là điều khó khăn trong bối cảnh ngôn ngữ luôn phát triển và thay đổi Tiếng Anh hiện đang là ngôn ngữ phổ biến nhất trong giao dịch toàn cầu, do đó việc xây dựng một tập ngữ liệu tiếng Anh đáp ứng tiêu chí không quá phức tạp Ngược lại, Việt Nam chỉ mới có Internet trong khoảng một thập kỷ qua, dẫn đến số lượng trang web tiếng Việt còn hạn chế Đến nay, vẫn chưa có tập ngữ liệu huấn luyện chuẩn nào được công bố cho việc tách từ và phân loại trang web tiếng Việt.
Gần đây, phương pháp tách từ mới mang tên Internet and Genetics Algorithm-based Text Categorization (IGATEC) do H Nguyen et al (2005) giới thiệu đã thu hút sự chú ý nhờ ưu điểm không cần sử dụng tập ngữ liệu hay từ điển để thu thập thông tin thống kê hay trọng số của từ Sự sáng tạo của thuật toán này nằm ở việc kết hợp thuật toán di truyền với việc trích xuất thông tin từ Internet thông qua các công cụ tìm kiếm như Google, thay vì dựa vào tập ngữ liệu như các phương pháp trước đây.
Giới thiệu thuật toán K-means
Thuật toán K-means nhằm mục đích phân cụm dữ liệu đầu vào thành số lượng nhóm xác định, xác định trọng tâm cho mỗi nhóm và phân loại các điểm dữ liệu vào các nhóm tương ứng, với giả định rằng mỗi điểm dữ liệu chỉ thuộc về một nhóm duy nhất.
Trong bài toán phân cụm K-means, giả sử chúng ta có N điểm dữ liệu trong tập huấn luyện được biểu diễn dưới dạng X [x₁, x₂, , xN] thuộc R^dxN, với K là số cụm được xác định trước và K < N Nhiệm vụ của chúng ta là tìm các trọng tâm m₁, m₂, , mK thuộc R^dx1 và gán nhãn cho mỗi điểm dữ liệu Mỗi cụm sẽ được đại diện bởi một nhãn, thường là một số tự nhiên từ 1 đến K Điều quan trọng là các điểm dữ liệu ban đầu không có nhãn cụ thể, và mục tiêu của chúng ta là xác định nhãn sao cho các điểm có cùng nhãn gần nhau, hình thành các cụm rõ ràng.
Với mỗi điểm dữ liệu x i , ta cần tìm nhãn y i = k của nó, ở đây k∈
Một kỹ thuật phổ biến để biểu diễn nhãn trong học máy là one-hot coding Mỗi nhãn k được chuyển đổi thành một vector hàng xk trong không gian R^y, với tất cả các phần tử của vector y i bằng 0, ngoại trừ phần tử tại vị trí thứ k bằng 1 Cụ thể, y ij = 0 với mọi j khác k, và y ik = 1 Khi các vector y i được chồng lên nhau, ta thu được một ma trận nhãn Y thuộc R^(N x K) Trong đó, y ij đại diện cho phần tử tại hàng thứ i và cột thứ j của ma trận Y, cũng như phần tử thứ j của vector y i Ví dụ, nếu một điểm dữ liệu có nhãn vector là 1,0,0,…,0, nó thuộc về cụm thứ nhất, trong khi nhãn 0,1,0,…,0 cho thấy nó thuộc về cụm thứ hai Ràng buộc của yi có thể được diễn đạt bằng các công thức toán học.
2.1.2 Hàm mất mát và bài toán tối ƣu
Trong phân cụm, trọng tâm mk ∈ R d đại diện cho mỗi cụm, và việc thay thế tất cả các điểm thuộc cụm này bằng mk dẫn đến sai số cho điểm dữ liệu x i, được tính bằng (xi - mk) Mục tiêu của chúng ta là giảm sai số này, tức là làm cho x i gần với mk Một cách đơn giản để đo khoảng cách giữa hai điểm là sử dụng khoảng cách Euclid bình phương, được biểu diễn là (xi - mk)² Hơn nữa, vì x i thuộc cụm k, ta có yik = 1 và yij = 0 với mọi j ≠ k Do đó, biểu thức khoảng cách Euclid có thể được viết lại một cách hiệu quả.
Nhƣ vậy, sai số trung bình cho toàn bộ dữ liệu sẽ là:
Ma trận M = [m1; m2; , mK] ∈ R dxK được tạo thành từ K trọng tâm trong bài toán phân cụm K-means Hàm mất mát L(Y,M) phải tuân thủ ràng buộc được nêu trong (2.1) Tóm lại, mục tiêu của bài toán là tối ưu hóa hàm mất mát này.
2.1.3 Thuật toán tối ƣu hàm mất mát
Bài toán (2.4) là một bài toán tối ưu khó khăn do có các điều kiện ràng buộc và thuộc loại mix-integer programming, khiến việc tìm nghiệm tối ưu toàn cục trở nên thách thức Mặc dù vậy, vẫn có những phương pháp cho phép tìm nghiệm gần đúng trong một số trường hợp Một kỹ thuật đơn giản và phổ biến để giải bài toán này là xen kẽ giữa việc giải Y và M trong khi giữ các biến còn lại cố định, cho đến khi hàm mất mát hội tụ Chúng ta sẽ lần lượt giải quyết hai bài toán này.
Sau khi xác định các trọng tâm, bước tiếp theo là tìm các nhãn vector để tối thiểu hóa hàm mất mát Điều này có nghĩa là chúng ta cần phân cụm cho từng điểm dữ liệu Khi các trọng tâm đã được cố định, việc tìm nhãn vector cho toàn bộ dữ liệu có thể được chia thành bài toán tìm nhãn vector cho từng điểm dữ liệu riêng lẻ.
Vì chỉ có một phần tử của nhãn vector yj bằng 1 nên bài toán (2.5) chính là bài toán đi tìm trọng tâm gần điểm xi nhất: j = argminj
Vì 2 j 2 i m x chính là bình phương khoảng cách Euclid từ điểm xi tới trọng tâm mj, ta có thể kết luận rằng mỗi điểm xi thuộc vào cụm có trọng tâm gần nó nhất Từ đó ta có thể suy ra nhãn vector của từng điểm dữ liệu
Khi đã xác định được cụm cho từng điểm dữ liệu, bước tiếp theo là tìm trọng số cho mỗi cụm sao cho hàm mất mát đạt giá trị tối thiểu Sau khi nhãn vector cho từng điểm được xác định, bài toán tìm trọng tâm cho mỗi cụm trở nên đơn giản hơn.
Để tìm nghiệm cho bài toán tối ưu, ta áp dụng phương pháp giải phương trình đạo hàm bằng không Hàm cần tối ưu là một hàm liên tục và có đạo hàm xác định tại mọi điểm \( m_j \) Đặt \( l(m_j) \) là hàm trong dấu argmin trong (2.6), nhiệm vụ của chúng ta là giải phương trình này.
Nếu để ý một chút, chúng ta sẽ thấy rằng mẫu số chính là phép đếm
Số lượng các điểm dữ liệu trong cụm j được ký hiệu là n j, trong khi tử số là tổng các điểm dữ liệu trong cụm này Do đó, m j có thể được hiểu là giá trị trung bình cộng của các điểm trong cụm j.
Bài toán phân cụm K-means cũng xuất phát từ đây
2.1.4 Ƣu điểm thuật toán k-means
- Độ phức tạp: O(K.N.l) với l: số lần lặp
- Có khả năng mở rộng, có thể dễ dàng sửa đổi với những dữ liệu mới
- Bảo đảm hội tụ sau một số bước lặp hữu hạn
- Luôn có K cụm dữ liệu
- Luôn có ít nhất một điểm dữ liệu trong một cụm dữ liệu
- Các cụm không phân cấp và không bị chồng chéo dữ liệu lên nhau
- Mọi thành viên của một cụm là gần với chính cụm đó hơn bất cứ một cụm nào khác.
Phân loại văn bản bằng thuật toán k-means
Để phân loại văn bản theo các chủ đề như giáo dục, thể thao, y tế và khoa học, thuật toán K-means là một công cụ hữu ích Quy trình phân loại văn bản bằng K-means bao gồm các bước cụ thể mà người dùng cần thực hiện để đạt được kết quả chính xác và hiệu quả.
Bước 1 Thu thập các văn bản: Bước này ta cần tập hợp các văn bản mà ta cần phân loại theo chủ đề
Bước 2 trong xử lý ngôn ngữ tự nhiên là tách từ, một bước quan trọng nhất Việc tách từ trong tiếng Việt phức tạp hơn so với tiếng Anh do sự xuất hiện của các từ ghép.
Tách từ là một bước quan trọng trong tiền xử lý dữ liệu cho các bài toán xử lý ngôn ngữ tự nhiên Trong luận văn này, tôi giả định rằng việc tách từ đã được thực hiện chính xác nhờ vào phần mềm VnTokenizer.
Bước 3 trong quy trình chuẩn hóa dữ liệu là loại bỏ các từ và ký hiệu không cần thiết, không ảnh hưởng đến việc phân loại văn bản Điều này bao gồm việc loại bỏ các ký hiệu đặc biệt, dấu câu và khoảng trống để tối ưu hóa chất lượng dữ liệu.
Bước 4: Xây dựng từ điển từ vựng Trong quá trình phân loại văn bản, chúng ta cần tạo ra một danh sách các từ đã sử dụng trong các đoạn văn bản đó Điều này sẽ giúp mã hóa văn bản thành các con số tương ứng với thứ tự của các từ trong từ điển.
Bước 5 trong quá trình xử lý văn bản là tạo vector thuộc tính bằng phương pháp Bag of Words Phương pháp này cho phép chúng ta biểu diễn văn bản dưới dạng tập hợp các từ kèm theo tần suất xuất hiện của từng từ trong văn bản Ví dụ, nếu có hai văn bản đơn giản, chúng ta có thể áp dụng phương pháp này để phân tích nội dung của chúng.
(1) John likes to watch movies Mary likes movies too và
(2) John also likes to watch football games
Dựa trên hai văn bản này, ta có danh sách các từ đƣợc sử dụng, đƣợc gọi là từ điển với 10 từ nhƣ sau:
["John", "likes", "to", "watch", "movies", "also", "football", "games",
Với mỗi văn bản, ta sẽ tạo ra một vector đặc trƣng có số chiều bằng
10, mỗi phần tử đại diện cho số từ tương ứng xuất hiện trong văn bản đó Với hai văn bản trên, ta sẽ có hai vector đặc trƣng là:
Văn bản (1) có 1 từ “John”, 2 từ “likes”, 0 từ “also”, 0 từ
“football”,… nên ta thu được vector tương ứng như trên
Có một vài điều cần lưu ý trong BoW [1]:
Trong các ứng dụng thực tế, từ điển có thể chứa hàng trăm nghìn đến cả triệu từ, dẫn đến việc vector đặc trưng sẽ rất dài Một câu đơn giản hay một tiểu thuyết dài hàng nghìn trang đều có thể được biểu diễn bằng các vector với số chiều lên tới 100 nghìn hoặc 1 triệu.
Nhiều từ trong từ điển không xuất hiện trong văn bản, dẫn đến việc các vector đặc trưng thường chứa nhiều phần tử bằng 0 Những vector này được gọi là vector thưa.
Bước 6 Áp dụng thuật toán K-means để phân loại văn bản
Sau khi vector hóa các văn bản, chúng ta sẽ sử dụng thuật toán K-means để phân cụm chúng Để so sánh sự tương đồng giữa hai văn bản, cần tính toán độ tương đồng của hai vector, ví dụ bằng cách sử dụng phương pháp tính cosin góc Khi hai vector đồng hướng, cosin của góc giữa chúng sẽ bằng 1 Trong một tập hợp văn bản (ngữ liệu — corpus), có nhiều từ không quan trọng như "a", "the", "and" xuất hiện với tần suất cao, trong khi các từ quan trọng liên quan đến chủ đề của văn bản thường chỉ xuất hiện nhiều trong văn bản đó và ít xuất hiện ở các văn bản khác.
Chúng ta sử dụng các chỉ số:
- Document Frequency của từ t: Là số văn bản có chứa từ t Ký hiệu là df_t
- Collection Frequency của từ t: là tần số xuất hiện của từ trong toàn bộ ngữ liệu Ký hiệu là cf_t
Các từ không quan trọng thường có df và cf lớn, trong khi các từ quan trọng lại có df nhỏ hơn nhưng cf lớn hơn nhiều so với df Điều này xảy ra vì các từ quan trọng xuất hiện ít trong toàn bộ văn bản (hiếm gặp toàn cầu) nhưng lại có tần suất cao trong một văn bản cụ thể (phổ biến cục bộ).
2.2.2 Ví dụ về dùng thuật toán K-means trong phân loại văn bản
Tôi xin trình bày một ví dụ nhỏ về việc dùng thuật toán k-means trong phân loại văn bản nhƣ sau:
Giả sử ta có 10 tài liệu cần phân nhóm Và có 5 từ và tần suất xuất hiện các từ đƣợc cho ở bảng sau
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Giả sử ta cần phân văn bản thành 3 nhóm Ta phải chọn 3 điểm trung tâm cho 3 nhóm Giả sử đó là D2, D5, D7 đƣợc chọn làm 3 điểm chính khởi đầu
Sau đó ta cần tính khoảng cách Euclidean từ 3 điểm chính D2, D5, D7 đến các tài liệu khác Ta ký hiệu 5 từ có trong từ điển nhƣ sau:
Bảng 2.2 Giả sử ta tính khoảng cách Euclidean giữa 2 tài liệu D1 và D2
Ta sẽ tính đƣợc khoảng cách từ các tài liệu đến 3 tài liệu đƣợc chọn làm điểm chính và có kết quả nhƣ bảng sau:
Từ 10 tài liệu ta chuyển thành 3 nhóm nhƣ sau:
Ta sẽ xác định lại điểm trung tâm cho 3 nhóm Giá trị của điểm trung tâm là trung bình cộng giá trị của các điểm trong nhóm
Giá trị điểm trung tâm của nhóm 1:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Giá trị điểm trung tâm của nhóm 2:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Bảng 2.5 Giá trị điểm trung tâm của nhóm 3:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Sau khi xác định được giá trị của 3 điểm trung tâm mới, chúng ta tiến hành tính khoảng cách giữa 10 tài liệu và 3 điểm trung tâm này Quá trình này sẽ tiếp tục lặp lại cho đến khi không còn tài liệu nào thay đổi nhóm nữa.
Ta tính lại khoảng cách các tài liệu đến 3 điểm trung tâm mới
Ta đƣợc 3 nhóm mới nhƣ sau:
Ta thấy có sự thay đổi nhóm của tài liệu D3; từ nhóm 3 chuyển sang nhóm 1
Tiếp tục tính giá trị cho điểm trung tâm cho 3 nhóm mới
Giá trị điểm trung tâm của nhóm C1:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Bảng 2.8 Giá trị điểm trung tâm của nhóm C2:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Bảng 2.9 Giá trị điểm trung tâm của nhóm C3:
Tài liệu Trực tuyến Du lịch Sách Chuyến bay Hà nội
Ta tính lại khoảng cách các tài liệu đến 3 điểm trung tâm mới:
Ta đƣợc 3 nhóm đƣợc phân theo 3 điểm trung tâm mới:
Có thể thấy ba nhóm trên không có sự thay đổi về thành viên, nên ta có thể dừng việc lặp cho việc chia 10 tài liệu thành 3 nhóm.
26 THỬ NGHIỆM VÀ Đ NH GI KẾT QUẢ PHÂN LOẠI VĂN BẢN VỚI
Tóm tắt thuật toán
Input: X = xi| i = 1, 2, …, N},và số lƣợng cluster cần tìm K
Output: các trọng tâm M, và các cụm tách rời tương ứng sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu
Hình 3.1: Sơ đồ khối của chương trình
Sử dụng thuật toán K-means để phân lớp văn bản
Để áp dụng thuật toán K-means vào phân lớp văn bản, trước tiên cần thực hiện quá trình vector hóa văn bản Mỗi văn bản sẽ được biểu diễn dưới dạng vector, giúp cho việc phân loại trở nên hiệu quả hơn.
K/C giữa trọng tâm đến đối tƣợng
Gom nhóm các đối tƣợng theo cụm
Begin bản sử dụng mô hình vector không gian Sau khi có tập các vector thì ta có thể áp dụng thuật toán K-means để tách văn bản
3.2.1 Thực hiện việc tách từ
Sau khi hoàn thành việc đánh số các văn bản từ 1 đến 50, tôi sử dụng phần mềm VnTokenizer để tách từ trong từng câu Dưới đây là một số kết quả tách từ được minh họa trong các hình ảnh sau.
Hình 3.2: Tách từ bằng phần mềm VnTokenizer
Sau khi tách từ, dữ liệu có thể vẫn chứa những từ không cần thiết cho việc phân loại văn bản Chúng ta có thể loại bỏ các ký hiệu đặc biệt, dấu câu, khoảng trống và con số để cải thiện chất lượng dữ liệu.
Giả sử dữ liệu sau khi tách ta đƣợc nhƣ sau:
Vào lúc 8h30 sáng ngày 5/6, giá vàng miếng trong nước được Tập Đoàn Vàng bạc đá quý Doji niêm yết ở mức 36,58 triệu đồng (mua vào) và 36,67 triệu đồng (bán ra), giảm 10 ngàn đồng ở chiều mua vào so với cuối giờ chiều phiên liền trước Công ty vàng bạc đá quý Sài Gòn niêm yết giá vàng SJC ở mức 36,54 triệu đồng.
Bây giờ, chúng ta chỉ giữ lại các phần có chứa từ WORD, NAME và CAPITAL, trong khi loại bỏ các loại khác Kết quả tách từ sau khi chuẩn hóa sẽ được trình bày như sau:
Vào sáng nay, giá vàng miếng trong nước được Tập Đoàn Vàng bạc đá quý Doji niêm yết ở mức triệu đồng mỗi lượng (mua vào) và triệu đồng mỗi lượng (bán ra), giảm ngàn đồng ở chiều mua vào so với cuối giờ chiều phiên liền trước Công ty vàng bạc đá quý cũng niêm yết giá vàng ở mức triệu đồng mỗi lượng.
Từ các từ đã tách ở bước trên, ta sẽ xây dựng được từ điển chứa các từ khác nhau, tạo nên các văn bản đó
Với đoạn văn bản đƣợc tách ở trên ta sẽ có từ điển bao gồm các từ sau:
Sáng nay, giá vàng miếng trong nước được Tập Đoàn Vàng bạc đá quý Doji niêm yết ở mức triệu đồng/lượng (mua vào) và triệu đồng/lượng (bán ra), giảm ngàn đồng ở chiều mua vào so với cuối giờ chiều phiên liền trước Công ty vàng bạc đá quý cũng niêm yết giá vàng ở mức triệu đồng/lượng.
Từ các từ đã tách ở bước trên, ta sẽ xây dựng được từ điển cho các từ khác nhau, tạo nên các văn bản đó
Vào lúc sáng, giá vàng miếng được niêm yết ở mức triệu đồng một lượng bởi Tập Đoàn Vàng bạc đá quý Doji.
Giá vàng niêm yết của công ty vàng bạc đá quý đã giảm xuống còn triệu đồng/lượng ở chiều mua vào, giảm ngàn đồng so với cuối giờ chiều phiên trước.
3.2.4 Mô hình vector không gian
Mô hình vector không gian, hay còn gọi là mô hình vector hạn, là một đại diện đại số cho các tài liệu văn bản, thường được gọi là vector định danh Mô hình này chủ yếu được áp dụng trong các lĩnh vực lọc thông tin, thu hồi thông tin, lập chỉ mục và xếp hạng Sử dụng đầu tiên của mô hình này là trong hệ thống truy hồi thông tin SMART.
Mỗi một kích thước thường tương ứng với một thuật ngữ riêng biệt
Khi một từ không xuất hiện trong tài liệu, giá trị của nó trong vector sẽ là 0 Trong số nhiều phương pháp tính trọng số, tf-idf được coi là tối ưu nhất, thường áp dụng cho từ đơn, từ khóa hoặc cụm từ dài Nếu các điều kiện được lựa chọn, số chiều của vector sẽ tương ứng với số từ trong từ vựng, tức là số lượng từ riêng biệt xuất hiện trong ngữ liệu Vector này có thể được sử dụng để so sánh các tài liệu với các truy vấn.
Quá trình lựa chọn vector trọng tâm ban đầu là rất quan trọng; việc xác định trọng tâm cho từng nhóm phân biệt sẽ mang lại hiệu quả tối ưu, nhưng thực tế lại khó khăn Trong chương trình, tôi đã thực hiện khởi tạo ngẫu nhiên trọng tâm ban đầu cùng với số nhóm được xác định trước.
3.2.5 Xác định trọng số (tọa độ) của hạn (term) trong văn bản
Trong mô hình vector không gian cổ điển, trọng lượng cụ thể của các vectơ tài liệu văn bản được xác định bởi sự kết hợp giữa các biến số địa phương và toàn cục Mô hình này còn được gọi là nghịch đảo tần số của hạn tần số tài liệu Vector trọng lượng cho tài liệu d được biểu diễn dưới dạng một vectơ.
Khi đó ta có thể xác định tọa độ wt,d theo công thức dưới đây:
Tần số xuất hiện của hạn t trong tài liệu d được ký hiệu là tft,d, trong khi nghịch đảo tần số tài liệu được biểu thị bằng IDF Tổng số tài liệu trong tập được ký hiệu là |D|, và số tài liệu chứa hạn t là một yếu tố quan trọng trong việc phân tích dữ liệu.
3.2.6 Xác định các hạn (term) trong văn bản
Việc xác định các hạn trong văn bản thực chất là xác định các từ trong văn bản, nhưng tách từ trong tiếng Việt là một bài toán khó Đầu tiên, các từ tối nghĩa như giới từ và mạo từ như "thì", "là", "mà", "và", "rằng", "sẽ" sẽ được loại bỏ, được gọi là stopwords Trong khi đó, việc tách từ trong tiếng Anh dễ dàng hơn do hầu hết các từ là từ đơn, có thể áp dụng phương pháp tách bằng khoảng trắng và ký tự đặc biệt Ngược lại, tiếng Việt chủ yếu là từ ghép, do đó việc tách từ đơn sẽ làm giảm độ chính xác trong việc gom nhóm.
Ví dụ: “họa sĩ”, “ca sĩ”, “thi sĩ”, “bác sĩ”,… thì việc tách thành từ đơn có thể làm cho việc gom nhóm không hiệu quả
Xây dựng chương trình bằng C#
Code của chương trình được viết bằng Visual Studio 2013
Khai báo lớp DocumentVector trên vectơ không gian (vectơ hạn) public class DocumentVector
{ public string Content { get; set; } public float[] VectorSpace { get; set; }
Bước tiếp theo ta định nghĩa lớp DocumentCollection để chứa các tài liệu đã đƣợc gom nhóm class DocumentCollection
{ public List DocumentList { get; set; }
Để xác định tần số nghịch đảo của hạn tần số TF-IDF, ta sử dụng công thức: TF-IDF t,d = TF t,d * IDF t, trong đó t đại diện cho thuật ngữ trong tài liệu d Việc tính toán trọng số TF-IDF cho mỗi thuật ngữ t trong tài liệu d là rất quan trọng để đánh giá mức độ quan trọng của thuật ngữ đó.
//Tinh trong so TF-IDF cho moi tu xuat hien o tai lieu d private static float FindTFIDF(string document, string term)
{ float tf = FindTermFrequency(document, term); float idf = FindInverseDocumentFrequency(term); return tf * idf;
} private static float FindTermFrequency(string document, string term)
{ int count = r.Split(document).Where(s => s.ToUpper() = term.ToUpper()).Count();
//Xac dinh ty le xuat hien cua mot tu t trong tai lieu d return (float)((float)count / (float)(r.Split(document).Count()));
} private static float FindInverseDocumentFrequency(string term)
//Khong tim duoc tu co trong tai lieu int count = documentCollection.ToArray().Where(s => r.Split( s.ToUpper()).ToArray().Contains(term.ToUpper())).Count(); return (float)Math.Log((float)documentCollection.Count() /
Chúng ta sẽ tìm kiếm sự tương đồng giữa các tài liệu bằng cách sử dụng phương thức FindCosineSimilarity Phương thức này được định nghĩa như sau: public static float FindCosineSimilarity(float[] vecA, float[] vecB).
{ var dotProduct = DotProduct(vecA, vecB); var magnitudeOfA = Magnitude(vecA); var magnitudeOfB = Magnitude(vecB); float result = dotProduct / (magnitudeOfA * magnitudeOfB);
//tra ve 0 trong truong hop mau so la 0 if (float.IsNaN(result)) return 0; else return (float)result;
} để chuẩn bị ta phân cụm cho văn bản ta định nghĩa thêm lớp entroid public class Centroid
{ public List GroupedDocument { get; set; }
} chuẩn bị cụm tài liệu public static List PrepareDocumentCluster(int k,
List documentCollection,ref int _counter)
//Khoi tao k ban dau va lay ngau nhien 1 diem lam trong tam
List centroidCollection = new List();
HashSet uniqRand = new HashSet();
GenerateRandomNumber(ref uniqRand,k,documentCollection.Count); foreach(int pos in uniqRand)
{ c = new Centroid(); c.GroupedDocument = new List(); c.GroupedDocument.Add(documentCollection[pos]); centroidCollection.Add(c);
InitializeClusterCentroid(out resultSet, centroidCollection.Count); do
{ prevClusterCenter = centroidCollection; foreach (DocumentVector obj in documentCollection)
{ int index = FindClosestClusterCenter(centroidCollection, obj); resultSet[index].GroupedDocument.Add(obj);
InitializeClusterCentroid(out centroidCollection, centroidCollection.Count()); centroidCollection = CalculateMeanPoints(resultSet); stoppingCriteria = CheckStoppingCriteria(prevClusterCenter, centroidCollection); if (!stoppingCriteria)
//Khoi tao ket qua cho lan lap tiep theo
InitializeClusterCentroid(out resultSet, centroidCollection.Count); }
Xây dựng trọng tâm cho cụm tại đây ta khởi tạo trọng tâm cho lần lặp tiếp theo private static void InitializeClusterCentroid(out List centroid,int count)
Centroid c; centroid = new List(); for (int i = 0; i < count; i++)
{ c = new Centroid(); c.GroupedDocument = new List(); centroid.Add(c);
Tìm trọng tâm cho cụm gần nhất rivate static int FindClosestClusterCenter(List clusterCenter,DocumentVector obj)
{ float[] similarityMeasure = new float[clusterCenter.Count()]; for (int i = 0; i < clusterCenter.Count(); i++)
{ similarityMeasure[i] SimilarityMatrics.FindCosineSimilarity( clusterCenter[i].GroupedDocument[0].VectorSpace, obj.VectorSpace);
} int index = 0; float maxValue = similarityMeasure[0]; for (int i = 0; i < similarityMeasure.Count(); i++)
//neu tai lieu co diem tuong dong thi gan vao 1 cum cung trong tam
//sao cho chi muc thap nhat de vong lap khong bi lap lai if (similarityMeasure[i] >maxValue)
Determine the new centroid location of the cluster After each iteration, the text is assigned to its nearest cluster centroid, and the average value of each centroid is recalculated to establish the new position of the centroid.
{ float total = 0; foreach (DocumentVector vSpace in
_clusterCenter[i].GroupedDocument[0].VectorSpace[j] total / _clusterCenter[i].GroupedDocument.Count(); }
Hình 3.3: Giao diện chính của chương trình
- Chạy tập tin TextClustering.exe
- Khai báo các tham số cần thiết cho hệ thống nhƣ:
+ Nhập số phân nhóm ban đầu vào ô số cụm K
+ Chép hay nhập văn bản cần phân loại vào textbox bên dưới
- Nhấn vào nút thêm để ghi nhận
- Nhấn nút xóa để xóa các thông số vừa ghi nhận
- Nhấn nút làm lại để khai báo lại từ đầu
Sau khi hoàn tất việc thiết lập các thông số cần thiết, chúng ta tiến hành phân loại văn bản bằng cách nhấn nút phân loại Tiếp tục nhấn nút này cho đến khi kết quả bên tay phải không còn thay đổi, điều này cho thấy chúng ta đã đạt được kết quả tối ưu nhất cho quá trình phân loại.
Hình 3.4: Khai báo các tham số hệ thống
Hình 3.5: Kết quả sau khi phân loại
Giao diện chương trình
Phân loại văn bản là một bài toán quan trọng trong xử lý ngôn ngữ tự nhiên, với nhiều ứng dụng thực tiễn, thu hút sự chú ý của các nhà nghiên cứu Tuy nhiên, nghiên cứu về vấn đề này vẫn gặp nhiều thách thức do sự phức tạp của ngôn ngữ tự nhiên.
Trong luận văn tốt nghiệp, tôi đã nghiên cứu thuật toán phân cụm K-means và xác định 6 bước cần thực hiện để phân loại văn bản Tôi cũng đã thu thập dữ liệu văn bản và tiến hành thử nghiệm với dữ liệu thực tế.
Tiếp tục nghiên cứu các thuật toán phân cụm khác nhằm áp dụng vào bài toán phân loại văn bản, chúng ta sẽ tiến hành phân tích và so sánh kết quả của các thuật toán này.
Do thời gian và kiến thức hạn chế, nội dung nghiên cứu chưa được sâu sắc và còn nhiều thiếu sót Kính mong quý thầy cô, thầy hướng dẫn cùng các bạn đóng góp ý kiến để hoàn thiện hơn.