Xây dựng hệ thống phát hiện những xu hướng nổi lên trên mạng xã hội sử dụng tiếng việt

GIỚI THIỆU

Lý do chọn đề tài

Trong những năm gần đây, mạng xã hội đã phát triển mạnh mẽ tại Việt Nam và trên toàn thế giới Theo thống kê, số người tham gia mạng xã hội tại Việt Nam đã tăng từ gần 30 triệu vào tháng 10 năm 2012 lên gần 40 triệu vào tháng 1 năm 2014 Mạng xã hội không chỉ là nơi để giao lưu, giải trí và kết nối bạn bè, mà còn là kênh quan trọng để cung cấp và chia sẻ thông tin giữa người dùng và các doanh nghiệp muốn quảng bá sản phẩm.

Sự phát triển nhanh chóng của mạng xã hội đã dẫn đến sự gia tăng đáng kể về khối lượng dữ liệu trực tuyến, với thông tin chia sẻ ngày càng phong phú Những nguồn thông tin này không chỉ hữu ích mà còn được cập nhật liên tục, tạo ra cơ hội khai thác thông tin quý giá Tuy nhiên, thách thức đặt ra là làm thế nào để xử lý và phân tích dữ liệu từ mạng xã hội, giúp người dùng nhận diện được các chủ đề thảo luận phổ biến.

Xác định các chủ đề phổ biến trong mạng xã hội giúp phát hiện xu hướng nổi bật, từ đó hiểu rõ hơn về mối quan tâm của xã hội Một hệ thống phát hiện xu hướng sử dụng tiếng Việt là cần thiết, hỗ trợ các công ty xây dựng chiến lược quảng cáo hiệu quả và nắm bắt nhanh chóng xu hướng người dùng.

1.2 Mục tiêu của đề tài Đưa ra những cơ sở lý thuyết và hướng tiếp cận mới từ đó hình thành nên phương pháp xây dựng một hệ thống phát hiện những xu hướng nổi lên trên mạng xã hội

Tiến hành thu thập dữ liệu từ một mạng xã hội thực tế và lưu trữ vào cơ sở dữ liệu sử dụng ySql, tạo đầu vào cho hệ thống phát hiện xu hướng nổi lên Hệ thống này sẽ được xây dựng bằng ngôn ngữ Java, với kết quả đầu ra được lưu trữ trong cơ sở dữ liệu.

Phân đoạn dữ liệu theo thời gian giúp chia nhỏ dữ liệu thu thập thành các khoảng thời gian cụ thể Qua việc phân tích các phân đoạn này, hệ thống có thể nhận diện và xác định thời điểm xuất hiện của các xu hướng nổi bật.

Tiến hành tiền xử lý dữ liệu và tìm từ khóa quan trọng trong từng phân đoạn

Kết hợp hai phương pháp gom cụm k-means và HAC (Hierarchical Agglomerative Clustering) giúp nhóm các từ khóa quan trọng một cách hiệu quả Đầu tiên, phương pháp k-means được áp dụng để phân loại các từ khóa, sau đó sử dụng HAC trên từng cụm kết quả của k-means Việc này không chỉ giảm thiểu độ phức tạp tính toán mà còn tận dụng độ chính xác cao của HAC, mặc dù phương pháp này có tốc độ tính toán chậm do độ phức tạp tăng theo cấp số mũ với số lượng phần tử.

Hệ thống thu thập thông tin từ mạng xã hội trong khoảng thời gian từ ngày 24/3/2015 đến 31/3/2015, sau đó chia dữ liệu thành các phân đoạn 6 ngày, với độ phủ chồng lấp 5 ngày.

Bảng 1.3.1: Ví dụ minh họa phân đoạn dữ liệu

Thời gian Nội dung tài liệu

2015-03-24 - 2015-03-29 máy bay Airbus A320 chở 148 người rơi tại Pháp

Pháp đã công bố lời cuối cùng từ chiếc Airbus A320 trước khi xảy ra tai nạn, trong khi đó, 16 học sinh người Đức lẽ ra đã có thể thoát khỏi thảm kịch này Cùng lúc, vụ sập giàn giáo tại công trình Formosa đã khiến 12 người thiệt mạng, để lại nỗi đau xót khi gia đình và bạn bè đón nhận thi thể các nạn nhân.

, trải lòng của người thoát chết vụ sập giàn giáo Formosa

2015-03-25 - 2015-03-30 Airbus A320 rơi : 16 học sinh Đức lẽ ra đã thoát nạn

, sập giàn giáo công trình Formosa , 12 người tử vong , rớt nước mắt đón thi thể nạn nhân vụ sập giàn giáo Formosa

2015-03-26 - 2015-03-31 sập giàn giáo công trình Formosa , 12 người tử vong

, rớt nước mắt đón thi thể nạn nhân vụ sập giàn giáo Formosa

, U23 VN - U23 aCau : 2 bàn thắng sớm

, U23 Malaysia - U23 VN : ngỡ ngàng Công Phượng , U23 VN chính thức vào VCK U23 Châu Á

, HLV Miura: U23 VN không thua 10 bàn là thành công

, HLV iura bị sa thải?

, lý do HLV iura sợ báo chí viết nhiều về Công Phượng

Sau khi thực hiện tiền xử lý văn bản, như sẽ được trình bày trong Chương 3, chúng tôi áp dụng phương pháp tính trọng số tf*idf để rút trích các từ khóa quan trọng trong từng phân đoạn Số lượng từ khóa được xác định dựa trên ngưỡng chặn của giá trị tf*idf, và giá trị này có thể được điều chỉnh khi chạy hệ thống trên các tập dữ liệu khác nhau Dưới đây là bảng thể hiện các từ khóa quan trọng của tập dữ liệu.

Bảng 1.3.1: Ví dụ minh họa kết quả tìm từ khóa quan trọng

2015-03-24 - 2015-03-29 cơ phó, sập, giàn giáo, người, A320, Formosa, rơi,

Pháp, máy bay, Airbus 2015-03-25 - 2015-03-30 sập, giàn giáo, Formosa,

2015-03-26 - 2015-03-31 sập, giàn giáo, Formosa, VN, Miura, U23

Sau khi xác định các từ khóa quan trọng trong từng phân đoạn thời gian, bước tiếp theo là tạo tập dữ liệu đầu vào cho quá trình gom cụm bằng k-means Mỗi từ khóa sẽ được biểu diễn dưới dạng một cấu trúc dữ liệu gọi là DataPoint, bao gồm hai thuộc tính chính: tên từ khóa và vector sức mạnh liên kết (link-strength) Vector này thể hiện mức độ liên kết giữa các từ khóa trong danh sách đã được rút trích trước đó Do đó, dữ liệu đầu vào cho bước gom cụm là một vector các DataPoint, mỗi DataPoint đại diện cho một từ khóa trong tập hợp các từ khóa như cơ phó, sập, giàn giáo, người, A320, Formosa, rơi, Pháp, máy bay, Airbus, VN, iura, U23.

Nếu tại bước gom cụm k-means chúng ta chọn hệ số k = 2, khi đó dữ liệu sẽ được chia thành 2 cụm với mỗi cụm chứa một vector các DataPoint:

Cụm 1: vector DataPoint [cơ phó, sập, giàn giáo, người, A320, Formosa, rơi, Pháp, máy bay, Airbus]

Cụm 2: vector DataPoint [VN, Miura, U23]

Sử dụng các cụm kết quả tại bước gom cụm k-means áp dụng thuật toán HAC hệ thống thu được 3 cụm chủ đề như sau:

Cụm 1: vector DataPoint [cơ phó, A320, rơi, Pháp, máy bay, Airbus]

Cụm 2: vector DataPoint [sập, giàn giáo, người, Formosa]

1.4 Cấu trúc của luận văn

Trong chương này chúng tôi đã giới thiệu tổng quan về đề tài Phần còn lại của luận văn sẽ được tổ chức như sau:

Chương 2: Trình bày các nghiên cứu liên quan, giới thiệu phương pháp và hướng tiếp cận của đề tài

Chương 3: Trình bày cơ sở lý thuyết được sử dụng để xây dựng hệ thống phát hiện xu hướng nổi lên trên mạng xã hội

Chương 4: Trình bày chi tiết về hệ thống phát hiện xu hướng nổi lên trên mạng xã hội

Chương 5: Trình bày kết quả thực nghiệm và đưa ra đánh giá về hệ thống

Chương 6: Đưa ra kết luận.

Giới thiệu đề tài

Thu thập dữ liệu từ mạng xã hội thực tế và lưu trữ vào cơ sở dữ liệu sử dụng ySql là bước đầu tiên trong việc phát triển hệ thống phát hiện xu hướng nổi lên Hệ thống này sẽ được xây dựng hoàn toàn bằng ngôn ngữ Java, và các kết quả đầu ra sẽ được lưu trữ lại trong cơ sở dữ liệu để phục vụ cho các phân tích sau này.

Phân đoạn dữ liệu theo thời gian giúp chia nhỏ dữ liệu thu thập thành nhiều phần, từ đó xác định được các xu hướng nổi bật Hệ thống có khả năng nhận diện thời gian mà những xu hướng này xuất hiện, giúp người dùng hiểu rõ hơn về sự phát triển của dữ liệu theo thời gian.

Tiến hành tiền xử lý dữ liệu và tìm từ khóa quan trọng trong từng phân đoạn

Kết hợp hai phương pháp gom cụm k-means và HAC (Hierarchical Agglomerative Clustering) nhằm gom nhóm các từ khóa quan trọng Đầu tiên, k-means được sử dụng để nhóm các từ khóa, sau đó áp dụng HAC trên từng cụm kết quả từ k-means Sự kết hợp này giúp giảm độ phức tạp tính toán trong quá trình gom cụm Mặc dù HAC có độ chính xác cao, nhưng tốc độ tính toán chậm do độ phức tạp tăng theo cấp số mũ với số lượng phần tử, vì vậy việc sử dụng k-means ở bước đầu tiên giúp giảm số lượng cụm cần xử lý.

Hệ thống thu thập thông tin từ mạng xã hội trong khoảng thời gian từ ngày 24/3/2015 đến 31/3/2015, sau đó chia dữ liệu thành các phân đoạn 6 ngày, với độ phủ chồng lên nhau là 5 ngày.

Bảng 1.3.1: Ví dụ minh họa phân đoạn dữ liệu

2015-03-24 - 2015-03-29 máy bay Airbus A320 chở 148 người rơi tại Pháp

Pháp đã công bố lời cuối cùng từ chiếc Airbus A320 trước khi gặp nạn, trong khi 16 học sinh người Đức lẽ ra đã có thể thoát khỏi thảm kịch Đồng thời, vụ sập giàn giáo tại công trình Formosa đã khiến 12 người thiệt mạng, gây xúc động mạnh mẽ khi thân nhân đón nhận thi thể các nạn nhân.

2015-03-25 - 2015-03-30 Airbus A320 rơi : 16 học sinh Đức lẽ ra đã thoát nạn

, sập giàn giáo công trình Formosa , 12 người tử vong , rớt nước mắt đón thi thể nạn nhân vụ sập giàn giáo Formosa

2015-03-26 - 2015-03-31 sập giàn giáo công trình Formosa , 12 người tử vong

, rớt nước mắt đón thi thể nạn nhân vụ sập giàn giáo Formosa

, U23 VN - U23 aCau : 2 bàn thắng sớm

, U23 Malaysia - U23 VN : ngỡ ngàng Công Phượng , U23 VN chính thức vào VCK U23 Châu Á

, HLV Miura: U23 VN không thua 10 bàn là thành công

, HLV iura bị sa thải?

, lý do HLV iura sợ báo chí viết nhiều về Công Phượng

Sau khi hoàn tất quá trình tiền xử lý văn bản, chúng tôi sẽ áp dụng phương pháp tính trọng số tf*idf để rút trích các từ khóa quan trọng trong từng phân đoạn Số lượng từ khóa được xác định dựa trên ngưỡng chặn của giá trị tf*idf, và giá trị này có thể được điều chỉnh khi hệ thống hoạt động trên các tập dữ liệu khác nhau Dưới đây là bảng thể hiện các từ khóa quan trọng của tập dữ liệu đã phân tích.

Bảng 1.3.1: Ví dụ minh họa kết quả tìm từ khóa quan trọng

2015-03-24 - 2015-03-29 cơ phó, sập, giàn giáo, người, A320, Formosa, rơi,

Pháp, máy bay, Airbus 2015-03-25 - 2015-03-30 sập, giàn giáo, Formosa,

2015-03-26 - 2015-03-31 sập, giàn giáo, Formosa, VN, Miura, U23

Sau khi xác định các từ khóa quan trọng cho từng phân đoạn thời gian, bước tiếp theo là tạo tập dữ liệu đầu vào cho quá trình gom cụm bằng k-means Mỗi từ khóa sẽ được biểu diễn dưới dạng một cấu trúc dữ liệu gọi là DataPoint, bao gồm hai thành phần chính: tên từ khóa và vector sức mạnh liên kết (link-strength) Vector này thể hiện mức độ liên kết của từ khóa với các từ khóa khác trong tập hợp đã được rút trích Do đó, dữ liệu đầu vào cho bước gom cụm sẽ là một vector các DataPoint, với mỗi DataPoint đại diện cho một từ khóa trong danh sách như [cơ phó, sập, giàn giáo, người, A320, Formosa, rơi, Pháp, máy bay, Airbus, VN, iura, U23].

Nếu tại bước gom cụm k-means chúng ta chọn hệ số k = 2, khi đó dữ liệu sẽ được chia thành 2 cụm với mỗi cụm chứa một vector các DataPoint:

Cụm 1: vector DataPoint [cơ phó, sập, giàn giáo, người, A320, Formosa, rơi, Pháp, máy bay, Airbus]

Sử dụng các cụm kết quả tại bước gom cụm k-means áp dụng thuật toán HAC hệ thống thu được 3 cụm chủ đề như sau:

Cụm 1: vector DataPoint [cơ phó, A320, rơi, Pháp, máy bay, Airbus]

Cụm 2: vector DataPoint [sập, giàn giáo, người, Formosa]

Cụm 3: vector DataPoint [VN, Miura, U23].

Cấu trúc của luận văn

Trong chương này chúng tôi đã giới thiệu tổng quan về đề tài Phần còn lại của luận văn sẽ được tổ chức như sau:

Chương 2: Trình bày các nghiên cứu liên quan, giới thiệu phương pháp và hướng tiếp cận của đề tài

Chương 3: Trình bày cơ sở lý thuyết được sử dụng để xây dựng hệ thống phát hiện xu hướng nổi lên trên mạng xã hội

Chương 4: Trình bày chi tiết về hệ thống phát hiện xu hướng nổi lên trên mạng xã hội

Chương 5: Trình bày kết quả thực nghiệm và đưa ra đánh giá về hệ thống

Chương 6: Đưa ra kết luận.

CÁC NGHIÊN CỨU LIÊN QUAN

Giới thiệu

Sự phát triển mạnh mẽ của truyền thông xã hội đã trở thành một phần quan trọng trong cuộc sống hiện đại, giúp các doanh nghiệp quảng bá thương hiệu và sản phẩm, đồng thời xây dựng mạng lưới khách hàng hiệu quả Bên cạnh đó, cá nhân cũng tận dụng mạng xã hội để xây dựng danh tiếng, chia sẻ cảm xúc và kết nối với bạn bè.

Sự phát triển bùng nổ của dữ liệu trực tuyến và thông tin trên mạng xã hội đã tạo ra khối lượng thông tin khổng lồ, khó kiểm soát và sàng lọc Điều này đã thúc đẩy mạnh mẽ các nghiên cứu liên quan đến khai phá dữ liệu trong các mạng xã hội.

Khám phá khả năng mở rộng của các chủ đề nổi bật trong dòng văn bản thông qua việc phân tích các ngưỡng quan trọng của Erich Schubert, Michael Weiler và Hans-Peter Kriegel.

- Hệ thống phát hiện xu hướng của các chủ đề dựa trên dòng dữ liệu của các tài khoản Twitter nhất định của: Duc T Nguyen và Jai E Jung [3]

The trending topic on Twitter has been identified by researchers James Benhardus and Jugal Kalita, along with Yavuz Selim Yilmaz, Muhammed Fatih Bulut, Cuneyt Gurcan Akcora, Murat Ali Bayir, and Murat Demirbas Additionally, insights have been provided by Mario Cataldi, Luigi Di Caro, and Claudio Schifanella.

Khai thác dữ liệu từ các miền web xã hội, bao gồm cả blog và email, là một lĩnh vực nghiên cứu quan trọng do Matthew A Russell thực hiện.

Phương pháp phát hiện xu hướng trên mạng xã hội được nghiên cứu bởi Ceren Budak, Divyakant Agrawal và Amr El Abbadi, giới thiệu hai định nghĩa mới về xu hướng có cấu trúc: xu hướng có liên kết và không liên kết Cách tiếp cận này cho phép đánh giá cao các chủ đề thảo luận sôi nổi trong các cụm nút mạng liên kết chặt chẽ, đồng thời cũng nhận diện những chủ đề được bàn luận nhiều nhưng chỉ có ít nút mạng bên ngoài liên kết với chúng.

- Phương pháp phát hiện xu hướng nổi lên bằng “dictionary learning” của: Shiva Prasad Kasiviswanathan, Prem Melville, Arindam Banerjee và Vikas Sindhwani [8].

Các phương pháp phát hiện xu hướng

Có hai loại kỹ thuật chính để phát hiện xu hướng: phương pháp bán tự động và tự động Những phương pháp này được sử dụng để phân tích xu hướng từ nhiều lĩnh vực khác nhau, bao gồm dữ liệu văn bản, dữ liệu đa truyền thông và các công bố khoa học.

2.2.1 Phương pháp bán tự động ( semi-automatic )

Phương pháp bán tự động là cách tiếp cận dựa trên thông tin thống kê và sự can thiệp của con người để xác định xu hướng Để hỗ trợ việc phát hiện xu hướng, một giao diện người dùng được thiết kế nhằm trình bày các thông tin thống kê một cách có tổ chức và dễ hiểu.

Hệ thống phân tích thời cơ công nghệ (Technology Opportunities Analysis

Hệ thống TOAS cung cấp thông tin đo lường tài liệu, bao gồm số lượng từ, số trích dẫn, ngày xuất bản và thông tin về nhà xuất bản Nó thu thập dữ liệu từ các truy vấn của người dùng trên các lĩnh vực nghiên cứu khác nhau.

Trong hệ thống Envision, người dùng có thể khám phá thư viện kỹ thuật số đa phương tiện dưới dạng biểu diễn đồ họa để nhận diện các xu hướng Envision tích hợp các công bố khoa học từ lĩnh vực khoa học máy tính dưới nhiều định dạng khác nhau như văn bản, video và hiệu ứng.

Envision hỗ trợ người dùng tìm kiếm theo đoạn trích dẫn hoặc nội dung đầy đủ, với kết quả được hiển thị dưới dạng đồ họa ma trận biểu tượng màu Từ đó, người dùng có thể quan sát các mối quan hệ động giữa các công bố, giúp xác định những chủ đề nổi bật và xu hướng trong các lĩnh vực nghiên cứu.

CIMEL (Constructive, Collaborative Inquiry-based Multimedia E-learning)

CI EL là một hệ thống cộng tác giúp xác định các xu hướng nổi bật từ vùng người dùng chọn Hệ thống thu thập thông tin từ các hội nghị và workshop liên quan, sau đó tạo ra các thông tin thống kê Để xác định các xu hướng nổi lên, sự can thiệp của con người là cần thiết trong quá trình phân tích dữ liệu.

2.2.2 Phương pháp tự động ( automatic )

Phương pháp tự động (automatic) sử dụng kỹ thuật khai phá dữ liệu thông minh (intelligent data mining) để phát hiện xu hướng một cách tự động, bao gồm hai thành phần chính: khai phá tài liệu và khai phá thời gian Khai phá tài liệu tập trung vào việc xác định xu hướng dựa trên nội dung tài liệu, trong khi khai phá thời gian chú trọng đến thông tin thời gian, chẳng hạn như ngày đăng tải, để nhận diện các xu hướng.

Trong khai phá tài liệu, thông tin về các xu hướng được trích xuất từ nội dung của tài liệu Các tài liệu này được phân loại thành các cụm thông qua kỹ thuật gom cụm Tiếp theo, thông tin trong mỗi cụm sẽ được phân tích để nhận diện các xu hướng.

Hệ thống HDDI áp dụng phương pháp khai phá tài liệu để phát hiện xu hướng từ dữ liệu văn bản bằng cách sử dụng kỹ thuật lựa chọn điểm đặc trưng để rút trích từ khóa quan trọng Sau khi rút trích, hệ thống tính toán độ tương tự của tài liệu và gom nhóm các tài liệu phù hợp Thông tin về số lượng cụm, tần suất và sự kết hợp các điểm đặc trưng chính được sử dụng để xác định xu hướng Ngoài ra, HDDI còn đề xuất một kỹ thuật dựa trên mạng neural để phát hiện xu hướng nổi bật.

Các đoạn trích dẫn trong các công bố khoa học rất hữu ích cho việc phát hiện xu hướng nghiên cứu Bài báo [16] đề xuất một kỹ thuật dựa trên các đoạn trích dẫn để phát hiện xu hướng trong CiteSeer, sử dụng cơ sở dữ liệu trích dẫn Kỹ thuật này gom cụm tài liệu dựa trên thông tin kết hợp và mỗi cụm được coi là một xu hướng Thông tin thời gian của tài liệu, như ngày công bố, được sử dụng để cung cấp thông tin thống kê cho từng xu hướng Mặc dù kỹ thuật hỗ trợ tìm xu hướng dựa trên từ khóa của người dùng, nhưng nó không xem xét thông tin thời gian trong quá trình gom cụm Do đó, việc xác định xu hướng hiện tại trong lĩnh vực nghiên cứu trở nên khó khăn.

Trong khai phá thời gian, thông tin về các xu hướng được rút ra từ dữ liệu thời gian của tài liệu Tài liệu trong cơ sở dữ liệu văn bản được phân nhóm theo ngày công bố, từ đó giúp phát hiện xu hướng thông qua các mẫu tuần tự của các tài liệu liên quan theo thời gian.

Khai thác thông tin thời gian từ tập dữ liệu văn bản được đánh nhãn, phương pháp thống kê được sử dụng để rút trích các điểm đặc trưng quan trọng liên quan đến từng thời kỳ Các điểm đặc trưng này sau đó được nhóm thành các chủ đề, giúp TimeMines xác định chính xác các chủ đề hoặc sự kiện quan trọng trong các khoảng thời gian nhất định Thông tin thống kê về các sự kiện trong mỗi thời kỳ cũng được cung cấp.

ThemeRiver là một công cụ khai phá thông tin thời gian từ tập dữ liệu văn bản lớn để xác định các chủ đề Nó phân loại tài liệu theo ngày công bố, mỗi nhóm tài liệu được biểu thị bằng một tập từ khóa tương ứng với chủ đề Nhờ đó, ThemeRiver xác định được các chủ đề cho từng thời kỳ Tiếp theo, nó tính toán mức độ tương tự giữa các chủ đề trong các thời kỳ khác nhau và kết hợp chúng thành một dòng chảy Giao diện đồ họa của ThemeRiver cho phép người dùng quan sát sự thay đổi của các chủ đề theo thời gian một cách trực quan.

Trong dự án TDT, một hệ thống "Event Tracking" đã được phát triển để thu thập dữ liệu văn bản từ các mẩu chuyện tin tức được sắp xếp theo thời gian Hệ thống rút trích các từ khóa quan trọng từ mỗi mẩu chuyện và so sánh chúng với những mẩu chuyện trong quá khứ Nếu mẩu chuyện hiện tại không giống với các mẩu chuyện trước đó, hệ thống sẽ ghi nhận một sự kiện mới, coi đây là một xu hướng mới được phát hiện tại thời điểm đó.

2.2.3 Phương pháp phân tích cụm dựa trên ngữ cảnh

Các tác giả trong bài báo [20] đã giới thiệu phương pháp phát hiện xu hướng nghiên cứu dựa trên phân tích cụm theo ngữ cảnh (Context-based Cluster Analysis - CCA) Phương pháp này cho phép tự động phát hiện các xu hướng nghiên cứu từ cơ sở dữ liệu trích dẫn CCA bao gồm hai quá trình chính: phát sinh quan hệ và ngữ cảnh xuyên suốt các cụm.

CƠ SỞ LÝ THUYẾT

Tiền xử lý văn bản

Bước này rất quan trọng vì nó giúp giảm số lượng từ trong văn bản, từ đó giảm kích thước dữ liệu và tăng độ chính xác trong việc tìm kiếm các từ khóa quan trọng khi tính toán tf*idf.

Tiền xử lý văn bản sẽ tiến hành các bước sau:

Để tách từ ghép trong văn bản, tôi sử dụng công cụ vnTokenizer, dựa trên phương pháp so khớp tối đa với bảng âm tiết và từ điển tiếng Việt Mục tiêu của việc này là giảm số lượng từ mà không làm ảnh hưởng đến nội dung tài liệu Dưới đây là quy trình thực hiện tách từ theo phương pháp so khớp tối đa.

Quy trình tách từ của vnTokenizer bắt đầu với đầu vào là một câu hoặc một đoạn văn bản, và đầu ra sẽ là một chuỗi các đơn vị từ đã được tách rời.

 Loại bỏ từ dừng (Stop-words):

Từ dừng (Stop-words) là những từ xuất hiện quá nhiều trong văn bản và thường không giúp phân biệt nội dung tài liệu, như "và", "do", "rồi", "những" Việc loại bỏ các từ dừng này không ảnh hưởng đến việc biểu diễn văn bản sau này.

Vector trọng số tf-idf

Phương pháp vector trọng số tf-idf (tần suất từ - tần suất ngược tài liệu) được hiểu rõ hơn qua mô hình không gian vector, trong đó thông tin văn bản được biểu diễn dưới dạng vector Mỗi thành phần của vector tương ứng với một từ khóa trong tập văn bản gốc và được gán giá trị dựa trên mật độ xuất hiện của từ khóa đó trong văn bản.

Hình 3.2.1: Các vector văn bản được biểu diễn trong không gian 2 chiều

Giả sử chúng ta có một văn bản được biểu diễn dưới dạng vector V(v1, v2, v3, , vn), trong đó vi là số lần xuất hiện của từ khóa i trong văn bản Dưới đây là ba văn bản để xem xét.

 Văn bản 1 (VB1): Tôi thích bóng đá và tenis

 Văn bản 2 (VB2): Tôi chơi guitar

 Văn bản 3 (VB3): Bóng đá và bóng đá văn bản 1 văn bản 2 văn bản 3

Sau khi qua bước tiền xử lý văn bản ta biểu diễn chúng dưới dạng vector như sau:

Bảng 3.2.1: Biểu diễn các vector văn bản

Từ thích bóng đá tenis chơi guitar

Trong các cơ sở dữ liệu văn bản, mô hình vector là phương pháp phổ biến nhất để biểu diễn văn bản, cho phép xác định mối quan hệ giữa các trang văn bản thông qua các phép toán trên vector Phương pháp trọng số tf-idf là một trong những kỹ thuật nổi bật nhất trong mô hình không gian vector, giúp xác định giá trị của các cụm từ trong vector đặc trưng một cách hiệu quả.

Tf-idf là tích của hai số liệu thống kê tần suất xuất hiện và nghịch đảo tần suất xuất hiện

 Tf (tần suất xuất hiện) được tính theo công thức:

( ) ( ) : là tần suất xuất hiện từ t trong văn bản d

( ) : là số lần xuất hiện từ t trong văn bản d

( ) : số lần xuất hiện nhiều nhất của một từ bất kỳ trong văn bản d

 Idf (nghịch đảo tần suất xuất hiện) được tính theo công thức:

( ) : là nghịch đảo tần suất xuất hiện từ t

N: là tổng số văn bản trong tập tài liệu D

( ) : số lượng tài liệu chứa từ t

Các từ có giá trị TF-IDF cao là những từ xuất hiện thường xuyên trong văn bản cụ thể nhưng lại ít xuất hiện trong các văn bản khác Điều này giúp loại bỏ các từ phổ biến và giữ lại những từ có giá trị cao, từ đó nâng cao chất lượng nội dung.

Thuật toán k-means

Gom cụm dữ liệu, hay còn gọi là phân cụm, là phương pháp nhóm các ứng viên thành các cụm trong học máy mà không cần giám sát Phương pháp này được ứng dụng rộng rãi trong nhiều lĩnh vực như khai phá dữ liệu, học máy và xử lý ảnh.

K-Means là thuật toán được sử dụng phổ biến trong trong hướng tiếp cận phân cụm phân hoạch (Partitional clustering) Ý tưởng chính của phương pháp phân cụm phân hoạch là phân một tập dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu một phần tử dữ liệu

Thuật toán k-means có độ phức tạp thấp O(tkn), trong đó t là số lần lặp, k là số cụm và n là số đối tượng cần gom cụm Được giới thiệu lần đầu bởi J.B MacQueen vào năm 1967, thuật toán này có nhiều biến thể khác nhau Đầu vào của k-means là một tập hợp n mẫu và một số nguyên k, với mục tiêu phân chia n đối tượng thành k cụm sao cho sự tương đồng giữa các mẫu trong cùng một cụm cao hơn so với các đối tượng thuộc cụm khác.

Thuật toán này bắt đầu bằng việc chọn ngẫu nhiên k mẫu, mỗi mẫu được coi là tâm của một cụm Các mẫu còn lại sẽ được gán vào một trong k cụm sao cho tổng khoảng cách từ mẫu đến tâm cụm là nhỏ nhất Sau đó, tâm của các cụm sẽ được tính lại và quá trình này sẽ lặp lại cho đến khi hàm tiêu chuẩn hội tụ Hàm tiêu chuẩn thường được sử dụng là hàm tiêu chuẩn bình phương sai.

Thuật toán k-means được mô tả cụ thể như sau:

Hình 3.3.1: Lưu đồ mô tả thuật toán K-means

 Bước 1: Chọn ngẫu nhiên k mẫu vào k cụm Coi tâm của cụm là chính là mẫu có trong cụm

 Bước 2: Tính khoảng cách giữa các mẫu còn lại đến k tâm

 Bước 3: Gán các mẫu vào cụm sao cho khoảng cách từ mẫu đến tâm cụm là nhỏ nhất

Khi không có mẫu nào duy chuyển khỏi cụm

Tính khoảng cách từ mẫu đến tâm cụm

Gom cụm dựa trên khoảng cách

 Bước 4:Nếu các cụm không có sự thay đổi nào sau khi thực hiện bước 3 thì chuyển sang bước 5, ngược lại thì quay lại bước 2

 Bước 5: thuật toán kết thúc.

Thuật toán HAC

HAC (Hierarchical Agglomerative Clustering) là một thuật toán phân cụm không giám sát, cho phép người dùng không cần xác định trước số lượng cụm, nhưng yêu cầu phải có điều kiện dừng Thuật toán này chủ yếu sử dụng hai phương pháp chính để thực hiện quá trình phân cụm.

Phương pháp kết hợp cụm từ dưới lên (Agglomerative Approach) bắt đầu bằng cách coi mỗi đối tượng là một nhóm riêng biệt Sau đó, nhóm hai đối tượng gần nhất lại với nhau để tạo thành một cụm Quá trình này tiếp tục lặp lại cho đến khi tất cả các đối tượng được gộp thành một cụm cuối cùng hoặc đạt được điều kiện đã được xác định trước.

Phương pháp phân chia cụm từ trên xuống (Divisive Approach) là một kỹ thuật phân tích dữ liệu ngược lại với phương pháp gộp cụm (Agglomerative Approach) Ban đầu, tất cả các đối tượng được xem là thuộc về cùng một cụm, sau đó tiến hành chia thành hai nhóm con dựa trên khoảng cách lớn nhất giữa các đối tượng Quá trình này tiếp tục cho đến khi mỗi nhóm chỉ còn lại một đối tượng duy nhất.

Chúng tôi áp dụng phương pháp gom nhóm từ khóa quan trọng bằng thuật toán k-means để xác định các chủ đề Để thực hiện điều này, chúng tôi chọn phương pháp cụm từ dưới lên, sử dụng thuật toán HAC để phân tích và tổ chức dữ liệu một cách hiệu quả.

Hình 3.4.1: Lưu đồ mô tả thuật toán HAC

Giả sử có N phần tử và ma trận khoảng cách N*N

 Bước 1: Bắt đầu cho mỗi phần tử vào phân vùng của nó Nếu có N phần tử thì có N phân vùng khởi tạo

 Bước 2: Tìm cặp phân vùng có khoảng cách nhỏ nhất và hợp lại thành một phân vùng Lúc này số phân vùng đã giảm đi một

 Bước 3: Tính khoảng cách giữa phân vùng mới với các phân vùng cũ còn lại

Để hoàn thành bước 4 trong thuật toán HAC, chúng ta cần lặp lại các bước 2 và 3 cho đến khi chỉ còn lại một phân vùng hoặc đạt được điều kiện dừng cụ thể Để tính khoảng cách giữa các cặp phân vùng, cần tìm hiểu một số phương pháp phổ biến được sử dụng trong thuật toán này.

Giả sử có hai cụm dữ liệu K và L được ký hiệu lần lượt là C K và C L Trong đó, x i và x j là các phần tử thuộc cụm C K và C L, và d(x i , x j ) đại diện cho khoảng cách giữa hai phần tử này.

- Single Linkage: Khoảng cách ngắn nhất giữa 2 phần tử của mỗi cụm

Số phân vùng =1 hoặc thỏa điều kiện

Gọp hai phân vùng có khoảng cách nhỏ nhất

Cập nhật lại ma trận khoảng cách Khởi tạo phân vùng

Với phương pháp này khoảng cách giữa 2 cụm là D KL được tính bằng khoảng cách ngắn nhất min d(x i , x j ) của x i và x j

- Complete linkage: Khoảng cách lớn nhất giữa 2 phần tử của mỗi cụm

Với phương pháp này khoảng cách giữa 2 cụm là D KL được tính bằng khoảng cách lớn nhất max d(x i , x j ) của x i và x j

- Average Linkage: Trung bình khoảng cách của tất cả các cặp phần tử của hai cụm

Với phương pháp này khoảng cách giữa 2 cụm là D KL được tính bằng trung bình cộng khoảng cách của tất cả các cặp x i và x j trong 2 cụm C K và C L

- Centroid linkage: Khoảng cách giữa hai phần tử trung tâm của mỗi cụm

Với phương pháp này khoảng cách giữa 2 cụm là D KL được tính bằng khoảng cách giữa 2 phần tử trung tâm (Centroid) của mỗi cụm C K và C L

Xét một ví dụ sau: Gom nhóm các từ khóa quan trọng sử dụng single linkage:

Bảng 3.4.1: Ma trận khoảng cách khi khởi tạo

HLV Miura cầu thủ U23 Việt Nam

Khoảng cách giữa từ khóa "HLV" và "Miura" là 0.00, cho thấy chúng gần gũi nhất Khi nhóm hai từ khóa này lại, ta có "HLV/Miura" Từ đây, ta tính toán khoảng cách của "HLV/Miura" đến các từ khóa khác, tạo thành ma trận khoảng cách.

Bảng 3.4.2: Ma trận khoảng cách sau khi gom cụm ”HLV” và ”Miura”

HLV/Miura cầu thủ U23 Việt Nam

U23 và Việt Nam có khoảng cách gần nhất là 0.42, vì vậy hai từ khóa này được gộp nhóm lại Ma trận khoảng cách đã được cập nhật để phản ánh sự liên kết này.

Bảng 3.4.2: Ma trận khoảng cách sau khi gom cụm ”U23” và ”Việt Nam”

HLV/Miura cầu thủ U23/ Việt Nam

- Lặp lại quá trình gom nhóm ta gọp cụm ”U23/Việt Nam” và ”cầu thủ” do khoảng cách giữa chúng bằng 0.43 là nhỏ nhất cập nhật ma trận khoảng cách:

Bảng 3.4.2: Ma trận khoảng cách sau khi gom cụm ”U23/Việt Nam ” và ”cầu thủ”

HLV/Miura U23/ Việt Nam/cầu thủ

Cuối cùng ta gọp hai cụm còn lại uá trình trên được thể hiện qua cây dendrogram bên dưới:

Hình 3.4.3: Cây dendrogram biểu diễn quá trình gom cụm HAC

HLV Miura cầu thủ U23 Việt Nam

Phương pháp tính khoảng cách khi gom cụm

3.6.1 Giới thiệu về link-strength và correlation Đối với dữ liệu hệ thống làm việc là dữ liệu text do đó khi tiến hành gom cụm các từ khóa quan trọng để xác định chủ đề chúng ta không thể áp dụng giá trị khoảng cách toán học (euclidean distance) để tính toán giá trị khoảng cách giữa các từ khóa để hình thành nên cụm chủ đề Trong ngữ cảnh là mạng xã hội, một số từ khóa quan trọng thường được người dùng nhắc đến thường xuyên sẽ đi cùng với nhau, chính sự xuất hiện cùng nhau của những từ khóa này mà chúng ta có thể dự đoán được những chủ đề mà người dùng trong mạng xã hội bàn luận đến trong một khoảng thời gian nào đó Tức là nếu hai từ khóa A và B liên quan đến nhau thì khi nhắc đến

Chúng tôi đã kết hợp hai kỹ thuật, sức mạnh liên kết và hệ số tương quan, để phân tích và suy ra cách tính khoảng cách giữa các từ khóa quan trọng trong các interval trong quá trình gom cụm.

Sức mạnh liên kết (link-strength) giữa hai đối tượng A và B được định nghĩa bởi công thức:

X là tổng số lần xuất hiện đồng thời của hai từ khóa A và B, trong khi Y là tổng số lần xuất hiện riêng lẻ của A, riêng lẻ của B và cả hai cùng xuất hiện Trong hệ thống phát hiện xu hướng trên mạng xã hội, X thể hiện tổng số khoảng thời gian mà cả hai từ khóa A và B xuất hiện đồng thời.

Y đại diện cho tổng số interval mà các interval này có thể chứa A, B, hoặc cả A và B Trong hệ thống phát hiện xu hướng, kết quả tính toán link-strength được thể hiện dưới dạng ma trận N*N, trong đó mỗi hàng là một vector thể hiện độ liên kết giữa một từ khóa và các từ khóa khác Những vector này sẽ được sử dụng để tính toán độ tương quan giữa các từ khóa trong quá trình gom cụm.

Trong lý thuyết xác suất và thống kê, hệ số tương quan đo lường độ mạnh của mối tương quan tuyến tính giữa hai biến số ngẫu nhiên Trong hệ thống phát hiện xu hướng của chúng tôi, hệ số tương quan giữa hai từ khóa trong mỗi khoảng thời gian thể hiện giá trị khoảng cách giữa chúng khi tiến hành gom cụm Hệ số tương quan lớn cho thấy khoảng cách giữa hai từ khóa nhỏ, cho thấy khả năng chúng thuộc về cùng một cụm cao hơn Công thức tính hệ số tương quan được áp dụng để xác định mối liên hệ này.

√[ (∑ ) (∑ ) ][ (∑ ) (∑ ) ] Trong đó X, Y lần lượt là các vector biểu diễn độ liên kết giữa các từ khóa, N là số chiều của vector X hoặc Y

3.6.2 Kết hợp link-strength và correlation để tính khoảng cách

Bài viết dưới đây trình bày các bước kết hợp giữa sức mạnh liên kết (link-strength) và tương quan (correlation) để tính toán khoảng cách khi gom cụm Giả sử chúng ta có 6 khoảng thời gian (interval) và các từ khóa xu hướng (trend words) trong mỗi khoảng thời gian như được mô tả bên dưới.

Bảng 3.5.2.1: Ví dụ về các trend word trong interval

 Tính Link-strength ta được ma trận kết quả như bên dưới

Bảng 3.5.2.2: Ma trận tính link-strength

Từ ma trận kết quả link-strength ta được các vector như sau:

Tương tự cho việc tính các hệ số tương quan còn lại

Khi hệ số tương quan giữa X và Y càng lớn, khoảng cách giữa chúng càng nhỏ Hệ thống chỉ xem xét hệ số tương quan tuyến tính dương, vì vậy giá trị của hệ số tương quan nằm trong khoảng [0,1] Từ đó, có thể suy ra công thức tính khoảng cách giữa X và Y.

Thông thường, độ nghịch đảo được sử dụng để tính đại lượng nghịch vì nó không phụ thuộc vào giá trị lớn nhất và giúp giảm khoảng cách tuyệt đối tương đối lớn, có thể ảnh hưởng đến kết quả tính toán Để thu nhỏ khoảng cách, người ta thường áp dụng giá trị log Trong các ứng dụng thực tế, khoảng cách thường được tính dựa vào độ tương quan thông qua một công thức nhất định.

The distance can be calculated using the formula Distance = log(1/Correlation) In the given example, by selecting the coefficient k = 2 for the k-means algorithm and choosing the centroids A and D, we can identify two distinct clusters: {A, B, C} and {D}.

Trong chương này, chúng tôi phân tích các cơ sở lý thuyết cho hệ thống phát hiện xu hướng, sử dụng phương pháp vector trọng số tf-idf để biểu diễn dữ liệu văn bản từ mạng xã hội Chúng tôi giới thiệu hai phương pháp gom cụm là k-means và HAC, cùng với các phương pháp tính khoảng cách giữa các cụm Cuối cùng, hai kỹ thuật sức mạnh liên kết và hệ số tương quan được trình bày để tính giá trị khoảng cách trong quá trình gom cụm.

Ô HÌNH PHÁT HIỆN XU HƯỚNG ĐƯỢC ĐỀ XUẤT

Kiến trúc của hệ thống

Hệ thống bao gồm các thành phần chính được thể hiện qua mô hình do giáo viên hướng dẫn đề xuất, mà tôi đã nắm vững và phát triển thêm.

Hình 4.1.1: Mô hình hệ thống phát hiện xu hướng nổi trên mạng xã hội

Lưu trữ dữ liệu đầu vào của hệ thống và các giá trị sau khi tính toán là rất quan trọng Sơ đồ quan hệ dưới đây mô tả cấu trúc của cơ sở dữ liệu một cách rõ ràng và dễ hiểu.

Hình 4.1.2: Sơ đồ cơ sở dữ liệu quan hệ của hệ thống

Bảng entries: lưu trữ dữ liệu đầu vào của hệ thống là các bài viết được người dùng đăng

Bảng intervals lưu trữ các phân đoạn thời gian được tính toán từ các entries, trong khi bảng intervals_entries xác định các bài viết có trong từng interval Class DB đảm nhận việc quản lý các entries trong ô column.

*PK id title content posttime ôPKằ

+ UQ_entries_id() interv als ôcolumnằ

+ UQ_intervals_id() + PK_intervals() interv als_entries ôcolumnằ

+ UQ_intervals_entries_id() w ord ôcolumnằ

*PK id word intervalsid ôPKằ

+ UQ_word_id() tfidf_threshold ôcolumnằ

*PK id threshold intervalsid ôPKằ

+ UQ_tfidf_threshold_id() v ectorspace ôcolumnằ

*PK id name weight check_delete intervalsid ôPKằ

+ UQ_vectorspace_id() linkstrength ôcolumnằ

*PK id linkstrength vectorspaceid ôPKằ

Bảng tfidf_threshold lưu trữ các giá trị tf-idf đã tính toán cho từng khoảng thời gian, cho phép điều chỉnh ngưỡng tf-idf theo nhu cầu.

Bảng word: lưu trữ các từ được cắt ra sau quá trình xử lý tf-idf

Bảng vectorspace: lưu trữ các từ và trọng số của nó sau quá trình xử lý tf-idf

Bảng linkstrength: lưu trữ các giá trị trong ma trận linkstrength của vectorspace

4.1.2 Phân đoạn dữ liệu theo thời gian

Hệ thống sẽ phân đoạn dữ liệu mạng xã hội thành nhiều khoảng thời gian, với mỗi khoảng có độ lớn là 7 ngày, có thể điều chỉnh trong quá trình thực nghiệm Tuy nhiên, việc phân đoạn này có thể dẫn đến việc bỏ sót các từ khóa quan trọng, nếu chúng bị chia cắt giữa các khoảng thời gian Ví dụ, nếu một từ khóa xuất hiện ở hai khoảng liên tiếp, nó có thể không được nhận diện đầy đủ.

Trong một nghiên cứu về dữ liệu mạng xã hội trong 8 ngày, từ khóa “A” đã xuất hiện liên tiếp trong 3 ngày, cụ thể là vào ngày 4, ngày 5 và ngày 6 Hệ thống phân đoạn dữ liệu thành 2 phần, mỗi phần kéo dài 4 ngày Theo quy định, nếu một từ xuất hiện hơn 2 lần trong một phân đoạn, nó sẽ được coi là từ khóa quan trọng (trend word).

Bảng 4.1.1: Phân đoạn dữ liệu trên mạng xã hội

Để xác định trend word “A” hiệu quả, cần phân đoạn mạng xã hội theo thời gian với cách tiếp cận có sự chồng chéo Trong ví dụ, nếu phân đoạn là 4 ngày và mỗi phân đoạn bắt đầu chồng lên nhau 1 ngày, hệ thống sẽ tạo ra các phân đoạn như [1→4], [2→5], [3→6], [4→7] Nhờ vào cách phân đoạn này, từ khóa “A” xuất hiện 3 lần trong phân đoạn [4→7], giúp hệ thống nhận diện “A” là một trend word trong khoảng thời gian từ ngày 4 đến ngày 7.

4.1.3 Tiền xử lý văn bản và Tìm từ khóa quan trọng

Các chức năng tiền xử lý văn bản và tìm từ khóa quan trọng được mô tả trong sơ đồ sau:

Hình 4.1.3: Sơ đồ sơ đồ mô tả chức năng của similarity module và scoring module

Khi người dùng nhấp vào nút tìm kiếm từ khóa quan trọng trên màn hình phân đoạn dữ liệu theo thời gian, hệ thống sẽ kích hoạt controller SelectKeyWordController Controller này sẽ sử dụng VectorProcessingService để xử lý dữ liệu, bắt đầu bằng việc tách các từ trong phân đoạn, lấy từ ghép, loại bỏ stop words và lưu trữ vào cơ sở dữ liệu Tiếp theo, hệ thống sẽ tính trọng số tf-idf cho từng từ trong các khoảng thời gian và gửi kết quả trở lại controller Cuối cùng, controller sẽ gọi trang KeyWord để hiển thị kết quả trên màn hình.

Dựa trên các từ khóa quan trọng đã được xác định, hệ thống tiến hành nhóm các từ khóa liên quan để tối ưu hóa nội dung Sơ đồ dưới đây minh họa sự tương tác của hệ thống trong quá trình gom cụm từ khóa.

Hình 4.1.4: Sơ đồ sơ đồ mô tả chức năng của Trend detection

Khi người dùng nhấn vào nút gom cụm dữ liệu từ màn hình với các từ khóa quan trọng, hệ thống sẽ gọi controller ClusteringController, từ đó kích hoạt KmeanClustering để xử lý dữ liệu Sau khi tạo không gian vector và thêm vào cơ sở dữ liệu, hệ thống tính toán linkstrength Tiếp theo, thuật toán k-means được áp dụng để gom nhóm và kết quả được gửi về cho controller Controller sẽ sử dụng kết quả từ k-means để tạo ma trận khoảng cách trong HacClustering và thực hiện gom nhóm bằng thuật toán HAC Cuối cùng, kết quả được hiển thị trên màn hình Clustering.

Dưới đây sẽ trình bày giải thuật kết hợp thuật toán k-means và HAC:

Input: Danh sách các từ khóa quan trọng L p = {p 1 ,…, pn} với p i là một từ khóa

Output: danh sách cụm HAC Lhac_cluster với mỗi hac_cluster chứa một danh sách các từ khóa

5: L k-means_cluster ← result of k-means algorithm on Lp

6: for each k-means_cluster c i {c 1 ,…, c n } in L k-means_cluster do

7: L i_hac_cluster ← Apply HAC algorithm on ci

8: Merge L i_hac_cluster to Lhac_cluster

Kết quả của hệ thống k-means phụ thuộc vào việc lựa chọn hệ số k và tâm cụm phù hợp Hiện tại, chưa có giải pháp khoa học nào được công nhận để xác định hệ số k hiệu quả Thông thường, người ta áp dụng các phương pháp khác nhau để chọn hệ số k phù hợp với từng hệ thống cụ thể.

Chúng tôi thử nghiệm hệ thống với các giá trị khác nhau của k để xác định giá trị tối ưu cho kết quả phân cụm tốt nhất Phương pháp này được áp dụng trong hệ thống phát hiện xu hướng trên mạng xã hội của chúng tôi để chọn hệ số k phù hợp.

Để tối ưu hóa quá trình phân cụm dữ liệu, việc tham khảo ý kiến từ các chuyên gia trong lĩnh vực liên quan là rất quan trọng Họ thường có cái nhìn sâu sắc và có thể đề xuất giá trị phù hợp cho hệ số k, giúp cải thiện chất lượng phân tích và kết quả cuối cùng.

THỰC NGHIỆM

Kết quả thí nghiệm

5.1.1 Cách xây dựng tập dữ liệu thí nghiệm

Dữ liệu được thu thập từ cộng đồng tin tức 24h trên Facebook, với các tập dữ liệu nhỏ hơn có độ lớn 1 tháng Chúng tôi xác định thủ công các chủ đề phổ biến trong từng tập dữ liệu để đánh giá độ chính xác của hệ thống Sau đó, hệ thống được chạy trên từng tập dữ liệu và kết quả các chủ đề phát hiện được so sánh với các chủ đề đã xác định trước Đồng thời, chúng tôi cũng so sánh kết quả của hai phương pháp khác nhau Để đánh giá tốc độ, chúng tôi tiến hành chạy độc lập và đo tốc độ của hai phương pháp này.

- Phương pháp 1: Chỉ chạy độc lập phương pháp gom cụm HAC cho bước gom nhóm các chủ đề

- Phương pháp 2: Kết hợp hai phương pháp gom cụm k-means và HAC cho bước gom nhóm các chủ đề

Sau khi chạy hệ thống trên 4 tập dữ liệu thí nghiệm, chúng tôi tổng hợp được các kết quả như sau:

Bảng 5.1.2.1 So sánh kết quả về thời gian chạy giữa hai phương pháp gom cụm Độ lớn HAC - Kmeans HAC

214 từ 2 mili giây 10 mili giây

Tập Dữ liệu 1: Đầu vào: 214 từ và độ rộng về thời gian là 1 tháng

Bảng 5.1.2.1 So sánh về kết quả chạy giữa hai phương pháp gom cụm với tập dữ liệu 1

[U23 - VN - HLV - Miura - công phượng]

[Pháp - Airbus - A320 - rơi - máy bay - đâm - cơ phó]

[nạn nhân - Formosa - tử vong - sập - giàn giáo]

[chị ve chai - giấy tờ - bà - triệu - Yên -

[Yên - giấy tờ - bà - chị ve chai - triệu - Ngọt]

[xúc động - qua đời - vợ - người - duy nhân]

[duy nhân - xúc động - vợ - qua đời]

[Nepal - VN - động đất] [người - VN - Nepal - động đất]

[thiếu nữ - sàm sỡ - công viên nước] [sàm sỡ - công viên nước - thiếu nữ]

[scandal - MC - nguy kịch] [nguy kịch - MC]

[hé lộ - gây án - người ở - nghi phạm - khai - 10 - lên tiếng - ai - thảm sát - ngôi nhà - gia đình - bình phước - nghệ an - hung thủ - người chết]

[hung thủ - nghệ an - thảm sát - bình phước- gây án - người ở - người - hé lộ

- nghi phạm – khai - ai- 10 - lên tiếng - ngôi nhà - gia đình]

[lịch sử - cơn - lũ - quảng ninh - nhấn chìm]

[quảng ninh - cơn - lũ - lịch sử]

[ánh viên - giành - Singapore - kình ngư - HCV]

[giành - HCV- ánh viên - kình ngư - Singapore -]

[dài - 2.000 - phim - bá đạo - tập - cô dâu]

[phim - cô dâu - 2.000- dài - bá đạo - tập]

[U23 - indonesia - sea games - trực tiếp

[sea games - trực tiếp - U23 - việt nam - indonesia]

[tức tưởi - bạn trai - chết - mạng - tung

[nữ sinh - chết - tức tưởi - bạn trai - mạng - tung - 15 - sex]

[ ỹ - hợp pháp hóa - hôn nhân - đồng giới - chính thức - cộng đồng - LGBT]

[ ỹ - hợp pháp hóa - hôn nhân - đồng giới - chính thức - cộng đồng - LGBT] [đầu - trọc - thái lan - tuấn hưng - cạo - mr đàm - tin nhắn - quang lê]

[thái lan - tuấn hưng - đầu - trọc - cạo - mr đàm - tin nhắn - quang lê]

Đánh giá

Dựa trên kết quả thu thập từ việc chạy hệ thống trên các bộ dữ liệu thí nghiệm, chúng tôi đã tiến hành đánh giá hệ thống theo hai tiêu chí chính: độ chính xác và tốc độ.

 Về độ chính xác của hệ thống

Vậy nếu đánh giá tổng thể trên toàn bộ các tập thí nghiêm kết quả chạy giữa hai phương pháp gom cụm giống nhau trong khoảng 90 -95%

So sánh tốc độ giữa hai phương pháp phân cụm, phương pháp 1 sử dụng thuật toán gom cụm HAC và phương pháp 2 kết hợp k-means với HAC, cho thấy rằng phương pháp 2 nhanh gấp khoảng 2.2 lần so với phương pháp 1.

Đánh giá về độ chính xác và tốc độ của hệ thống chỉ mang tính chất tương đối, vì độ chính xác phụ thuộc vào các giá trị khởi tạo đầu vào như hệ số k trong thuật toán k-means và điều kiện dừng của thuật toán HAC Thuật toán k-means có độ phức tạp thấp là O(t*k*n), với t và k nhỏ so với n, trong khi thuật toán HAC có độ phức tạp lớn hơn, O(n^3) Do đó, khi tập dữ liệu lớn hơn, tức giá trị n tăng, sự tối ưu về tốc độ của phương pháp kết hợp sẽ trở nên rõ ràng hơn.

Tiêu đề	Xây Dựng Hệ Thống Phát Hiện Những Xu Hướng Nổi Lên Trên Mạng Xã Hội Sử Dụng Tiếng Việt
Tác giả	Trịnh Công Minh Quân
Người hướng dẫn	PGS. TS Quản Thành Thơ
Trường học	Trường Đại Học Công Nghệ TP. HCM
Chuyên ngành	Công Nghệ Thông Tin
Thể loại	luận văn thạc sĩ
Năm xuất bản	2015
Thành phố	TP. HỒ CHÍ MINH

Định dạng
Số trang	53
Dung lượng	1 MB