Tài liệu ứng dụng thuật toán k láng giềng gần nhất trong phân loại văn bản tin tức theo chủ đề

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA LÊ QUANG HÒA ỨNG DỤNG THUẬT TOÁN K LÁNG GIỀNG GẦN NHẤT TRONG PHÂN LOẠI VĂN BẢN TIN TỨC THEO CHỦ ĐỀ Chuyên ngành: Khoa học máy tính Mã số: 8480101 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA Người hướng dẫn khoa học: TS. Ninh Khánh Duy Phản biện 1 : TS. Lê Thị Mỹ Hạnh Phản biện 2 : TS. Đậu Mạnh Hoàn Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ kỹ thuật họp tại Trường Đại học Bách khoa vào ngày 05 tháng 01 năm 2019 Có thể tìm hiểu luận văn tại: - Trung tâm Học liệu và Truyền thông Trường Đại học Bách khoa, Đại học Đà Nẵng - Thư viện Khoa Công nghệ thông tin, Trường Đại học Bách khoa, Đại học Đà Nẵng 1 MỞ ĐẦU 1. Lý do chọn đề tài Như ta đã biết, thời đại hiện nay là thời đại internet, là thời đại của sự bùng nổ thông tin, khi mà tất cả mọi người trên thế giới đều sống trên một thế giới phẳng, đặc biệt là hiện nay khi đang diễn ra cuộc cách mạng công nghiệp 4.0 thì lượng thông tin ngày càng nhiều, việc phân loại chúng trở nên khó khăn. Ở bất kỳ một tổ chức nào, với bất kỳ một mô hình hay quy mô nào cũng đều có những nhu cầu về lưu trữ và khai thác thông tin. Đã có nhiều hệ thống phân loại tin tức trên thế giới cũng như ở Việt Nam đã đáp ứng được phần nào đó nhu cầu phân loại tin tức để ra quyết định. Việc phân loại tin tức đã đem lại thành tựu nhất định, cụ thể: - Xác định được xu thế của cộng đồng mạng khi mà cộng đồng này chiếm ngày càng đông trong xã hội. Qua đó xác định được xu thế về mặt ngắn hạn của xã hội, hỗ trợ cho người sử dụng ra các quyết định phù hợp. - Việc phân loại tin tức cũng được ứng dụng trên các website thương mại nhằm nắm bắt được xu thế tiêu dùng của người sử dụng. Một trong những thuật toán để ứng dụng công việc phân loại dữ liệu của các website tin tức tiếng Việt đó là thuật toán k-láng giềng gần nhất; thuật toán này có ưu điểm: Độ phức tạp của quá trình huấn luyện bằng 0 hay nói đúng hơn là không tốn chi phí.Việc dự đoán kết quả của dữ liệu mới rất đơn giản, không cần giả sử gì về phân phối của các lớp. Tuy nhiên, thuật toán này cũng có nhược điểm là nhạy cảm với nhiễu khi k nhỏ. Vì thuật toán k- láng giềng gần nhất này 2 mọi tính toán đều nằm ở giai đoạn kiểm thử( Test) cho nên việc tính toán khoảng cách đến từng điểm dữ liệu trong tập huấn luyện tốn nhiều thời gian, đặc biệt đối với cơ sở dữ liệu lớn và có nhiều điểm dữ liệu. Để việc áp dụng thuật toán k- láng giềng gần nhất trong việc ứng dụng phân loại tin tức giảm được chi phí về mặt thời gian và độ phức tạp cần phải tăng tốc và khăc phục nhược điểm cho thuật toán này. Đề tài nghiên cứu này nhằm vận dụng thuật toán k- láng giềng gần nhất theo cách tối ưu nhất dựa trên các cơ sở lý thuyết. 2. Mục đích và ý nghĩa đề tài - Nghiên cứu và đề xuất các phương pháp phân loại văn bản theo chủ đề dựa trên thuật toán k- láng giềng. - Tích hợp các giải pháp vào một hệ thống phân loại văn bản theo chủ đề và đánh giá hiệu quả. - Đóng góp về mặt phương pháp luận và thực nghiệm vào lĩnh vực phân loại văn bản, một nhánh nghiên cứu của xử lý ngôn ngữ tự nhiên. - Cải tiến chất lượng hệ thống phân loại văn bản hiện có để nâng cao quản lý xu thế của tin tức. 3. Mục tiêu và nhiệm vụ - Mục tiêu chính của đề tài là Ứng dụng thuật toán k-láng giềng gần nhất vào hệ thống xử lý thông tin để phân loại thông tin theo chủ đề. - Nghiên cứu và cải thiện thuật toán k- láng giềng trong hệ thống phân loại tin tức. 3 Để đạt được những mục tiêu trên thì nhiệm vụ đặt ra của đề tài là: - Thu thập dữ liệu mẫu từ các trang Web tiếng Việt. - Nghiên cứu các phương pháp biểu diễn văn bản dưới dạng vec-tơ để đưa vào áp dụng thuật toán k-láng giềng gần nhất. - Phát biểu, phân tích và cài đặt giải thuật cho bài toán trong hệ thống phân loại tin tức. - Đánh giá so sánh kết quả phân loại với các thuật khác như Naïve Bayes và Support Vector Machine. 4. Đối tượng và phạm vi nghiên cứu Trong khuôn khổ của luận văn thạc sĩ thuộc loại ứng dụng với thời gian thực hiện là 06 tháng, tôi giới hạn nghiên cứu các vấn đề sau: - Xây dựng phương pháp biểu diễn văn bản dưới dạng vec-tơ và áp dụng thuật toán k-láng giềng phục vụ cho hệ thống phân loại tin tức. - Đánh giá giải pháp đề xuất trên cơ sở tích hợp vào hệ thống phân loại tin tức. 5. Phương pháp nghiên cứu Phương pháp lý thuyết - Tiến hành thu thập và nghiên cứu các tài liệu có liên quan đến đề tài. - So sánh, đánh giá các phương pháp phân loại tin tức. Phương pháp thực nghiệm - Nghiên cứu và khai thác các công cụ phần mềm hỗ trợ. 4 - Nghiên cứu đề xuất giải pháp tối ưu trong việc biểu diễn và phân loại văn bản. - Kiểm tra, thử nghiệm, nhận xét và đánh giá kết quả. 6. Kết luận - Xây dựng được một hệ thống phân loại văn bản tin tức tiếng Việt. - Thiết lập được quy trình phân loại văn bản chặt chẽ, thông suốt, theo đúng chủ đề, thuận tiện cho việc tìm kiếm, tra cứu , theo dõi khi cần thiết. 7. Bố cục của luận văn ● CHƯƠNG 1: TỔNG QUAN BÀI TOÁN PHÂN LOẠI VĂN BẢN + Khái niệm phân lớp văn bản. + Mô hình phân lớp văn bản dùng tiếp cận học máy + Thu thập dữ liệu + Tiền xử lý văn bản + Biểu diễn văn bản trong không gian vec-tơ bằng B W và T IDF ● CHƯƠNG 2: THUẬT T ÁN K- LÁNG GIỀNG GẦN NHẤT (KNN) + Khai phá dữ liệu + Thuật toán k láng giềng gần nhất ● CHƯƠNG 3: TRIÊN KHAI VÀ ĐÁNH GIÁ HÊ THỐNG ● KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ● TÀI LIỆU THAM KHẢ 5 CHƯƠNG 1: TỔNG QUAN BÀI TOÁN PHÂN LOẠI VĂN BẢN 1.1. Khái niệm phân lớp văn bản 1.1.1. Khái niệm Phân lớp văn bản(Text classification) là quá trình gán nhãn(tên lớp / nhãn lớp) các văn bản ngôn ngữ tự nhiên một cách tự động vào một hoặc nhiều lớp cho truớc. Phân lớp văn bản là bài toán cơ bản trong khai phá dữ liệu văn bản. Bài toán phân lớp văn bản là việc gán tên các chủ đề (tên lớp/nhãn lớp) đã được xác định trước, vào các văn bản dựa trên nội dung của chúng. Phân lớp văn bản là công việc được sử dụng để hỗ trợ trong quá trình tìm kiếm thông tin, chiết lọc thông tin, lọc văn bản hoặc tự động dẫn đường cho các văn bản tới những chủ đề xác định trước. Phân lớp văn bản có thể thực hiện thủ công hoặc tự động sử dụng các kỹ thuật học máy có giám sát. Các hệ thống phân lớp có thể ứng dụng trong việc phân loại tài liệu của các thư viện điện tử, phân loại văn bản báo chí trên các trang tin điện tử… những hệ thống tốt, cho ra kết quả khả quan, giúp ích nhiều cho con người. Hình 1.1. Bài toán phân lớp văn bản theo chủ đề. 6 1.1.2. Phân loại bài toán phân lớp văn bản - Phân lớp văn bản nhị phân / đa lớp: Bài toán phân lớp văn bản được gọi là nhị phân nếu số lớp là 2, gọi là đa lớp nếu số lớp lớn hơn 2. -Phân lớp văn bản đơn nhãn / đa nhãn: Bài toán phân lớp văn bản được gọi là đơn nhãn nếu mỗi tài liệu được gán vào chính xác một lớp. Bài toán phân lớp văn bản được gọi là đa nhãn nếu một tài liệu có thể được gán nhiều hơn một nhãn. 1.2. Mô hình phân lớp văn bản dùng tiếp cận học máy Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán tên các chủ đề (tên lớp / nhãn lớp) đã được xác định cho trước vào các văn bản text dựa trên nội dung của nó.Để phân loại văn bản, người ta sử dụng phương pháp học máy có giám sát. Tập dữ liệu được chia ra làm hai tập là tập huấn luyện và tập kiểm tra, trước hết phải xây dựng mô hình thông qua các mẫu học bằng các tập huấn luyện, sau đó kiểm tra sự chính xác bằng tập dữ liệu kiểm tra. Hình 1.2. Sơ đồ khung một hệ thống phân lớp văn bản dùng Học máy. 7 1.3. Thu thập liệu Để đảm bảo tính đa dạng của các nguồn dữ liệu, tôi thu thập các bài viết từ 10 trang web điện tử phổ biến nhất của Việt Nam (dựa trên http://alexa.com) như zing.vn, kenh14, tuoitre.vn,…. Mỗi trang được chia thành 20 chủ đề chính. Các chủ đề bao gồm: Tin tức, Thế giới, Văn hóa - Văn học, Cuộc sống, Y tế, Khoa học - Công nghệ, Kinh tế, Thể thao, Du lịch, Âm nhạc, Phim, Luật, Tự động - Moto, Thời trang, Trẻ sống, Giáo dục, Nói chuyện, Quảng cáo, Khám phá, Sao. 1.3.1. Trình thu thập thông tin web Hình 1.3. Kiến trúc của trình thu thập dữ liệu web. 1.3.2. Thống kê dữ liệu 8 Hình 1.4 Số bài báo được thu thập theo chủ đề. 1.4. Tiền xử lý văn bản 1.4.1. Làm sạch 1.4.2. Tách từ 1.4.3. Chuẩn hóa từ 1.4.4. Loại bỏ StopWords 1.5. Biểu diễn văn bản ưới dạng vector 1.5.1.Túi từ (Bag-of-words) Khái niệm: là cách biểu diễn đơn giản được sử dụng trong xử lý ngôn ngữ tự nhiên và truy xuất thông tin. Mô hình BOW là một biểu diễn đơn giản được sử dụng trong xử lý ngôn ngữ tự nhiên và truy xuất thông tin. Trong mô hình này, một tài liệu văn bản được biểu diễn như thể nó là túi của các từ của nó, bỏ qua ngữ pháp và thứ tự từ nhưng chỉ giữ tần số của mỗi từ trong tài liệu. Nội dung: ý tưởng chính của BOW là: chạy từ đầu đến cuối văn bản, gặp từ nào thì tăng số lần đếm của từ từ đó trong danh sách từ đã lưu trước.Mô hình bag-of-words thường được sử dụng trong các 9 phương pháp phân loại tài liệu, nơi sự xuất hiện của mỗi từ được sử dụng như một tính năng để đào tạo một trình phân loại. Hình 1.5 Mô hình Bag-of-words. 1.5.2. Term Frequency – Inverse Document Frequency (TF-IDF) Khái niệm:tf-idf hoặc TF-IDF, viết tắt của Term Frequency – Inverse Doccument Frequencylà một con số thu được qua thống kê thể hiện mức độ quan trọng của từ này trong một văn bản, mà bản thân văn bản đang xét nằm trong một tập hợp các văn bản. Giá trị tfidf tăng tương ứng với số lần một từ xuất hiện trong tài liệu, nhưng thường được bù đắp bằng tần số của từ trong kho văn bản, giúp điều chỉnh thực tế là một số từ xuất hiện thường xuyên hơn nói chung[1][7]. Nội dung: Giá trị TF-IDF của từ t đối với văn bản d trong tập văn bản D là: (1.1) Với: - df (d, t): là số lượng văn bản trong tập D có chứa từ t. 10 Những từ có giá trị TF-IDF cao là những từ xuất hiện nhiều trong văn bản này, và xuất hiện ít trong các văn bản khác. Việc này giúp lọc ra những từ phổ biến và giữ lại những từ có giá trị cao (từ khoá của văn bản đó). 11 CHƯƠNG 2: THUẬT TOÁN K LÁNG GIỀNG GẦN NHẤT 2.1. Khai phá d liệu Dưới đây là một số thuật toán phổ biến được dùng trong khai phá dữ liệu: Cây quyết định: Decision tree Láng giềng gần nhất: Nearest Neighbor Mạng Neural: Neural Network Luật quy nạp : Rule Induction Thuật toán K-Means: K-Means 2.2. Thuật toán K láng giềng gần nhất 2.2.1.Giới thiệu chung KNN là một trong những thuật toán học có giám sát đơn giản nhất mà hiệu quả trong một vài trường hợp trong học máy. Khi huấn luyện, thuật toán này không học một điều gì từ dữ liệu huấn luyện (đây cũng là lý do thuật toán này được xếp vào loại lazy learning), mọi tính toán được thực hiện khi nó cần dự đoán kết quả của dữ liệu mới. KNN có thể áp dụng được vào cả hai loại của bài toán học có giám sát là phân lớp và hồi quy. KNN còn được gọi là một thuật toán instance-based hay memory-based learning. Một cách ngắn gọn, KNN là thuật toán đi tìm đầu ra của một điểm dữ liệu mới bằng cách chỉ dựa trên thông tin của K điểm dữ liệu gần nhất trong tập huấn luyện. 2.2.2. Nội dung thuật toán Mô tả thuật toán: • Xác định giá trị tham số K (số láng giềng gần nhất). 12 • Tính khoảng cách giữa điểm truy vấn phân lớp với tất cả các đối tượng trong tập dữ liệu huấn luyện. • Sắp xếp khoảng cách theo thứ tự tăng dần và xác định K láng giềng gần nhất với điểm truy vấn phân lớp. • Lấy tất cả các lớp của K láng giềng gần nhất đã xác định. • Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho điểm truy vấn phân lớp, lớp của điểm truy vấn phân lớp được định nghĩa là lớp chiếm đa số trong K láng giềng gần nhất. Việc tính khoảng cách giữa các đối tượng cần phân lớp với tất cả các đối tượng trong tập dữ liệu huấn luyện được thường được sử dụng với công thức tính khoảng cách Euclidean. Cho 2 điểm P1(x1,y1) và P2(x2,y2) thì khoảng cách Euclidean distance sẽ được tính theo công thức: √ (2.1) 2.2.3. Đánh trọng số cho các điểm lân cận Trong kỹ thuật major voting bên trên, mỗi trong bảy điểm gần nhất được coi là có vai trò như nhau và giá trị lá phiếu của mỗi điểm này là như nhau. Như thế có thể không công bằng, vì những điểm gần hơn cần có trọng số cao hơn. Vì vậy, ta sẽ đánh trọng số khác nhau cho mỗi trong bảy điểm gần nhất này. Cách đánh trọng số phải thoải mãn điều kiện là một điểm càng gần điểm kiểm thử phải được đánh trọng số càng cao. Cách đơn giản nhất là lấy nghịch đảo của khoảng cách này. Trong trường hợp dữ liệu kiểm thử trùng với một điểm dữ liệu trong tập dữ liệu huấn luyện, tức khoảng cách bằng 0, ta lấy luôn đầu ra của điểm dữ liệu huấn luyện. 13 Scikit-learn giúp chúng ta đơn giản hóa việc này bằng cách gán thuộc tính weights = ’ distance’. (Giá trị mặc định của weights là ’uniform’, tương ứng với việc coi tất cả các điểm lân cận có giá trị như nhau như ở trên). 2.2.4. Ưu điểm của KNN - Độ phức tạp tính toán của quá trình huấn luyện là bằng 0. - Việc dự đoán kết quả của dữ liệu mới rất đơn giản (sau khi đã xác định được các điểm lân cận). - Không cần giả sử về phân phối của các lớp. 2.2.5. Nhược điểm của KNN - KNN rất nhạy cảm với nhiễu khi K nhỏ. - Như đã nói, KNN là một thuật toán mà mọi tính toán đều nằm ở khâu kiểm thử, trong đó việc tính khoảng cách tới từng điểm dữ liệu trong tập huấn luyện tốn rất nhiều thời gian, đặc biệt là với các cơ sở dữ liệu có số chiều lớn và có nhiều điểm dữ liệu. Với K càng lớn thì độ phức tạp cũng sẽ tăng lên. Ngoài ra, việc lưu toàn bộ dữ liệu trong bộ nhớ cũng ảnh hưởng tới hiệu năng của KNN. 2.2.6. Các tham số quan trọng của thuật toán KNN Dựa vào các phần trước, tôi thấy có các tham số quan trọng đối với thuật toán KNN: - Giá trị K: K càng lớn thì thuật toán càng ít nhạy cảm với nhiễu, nhưng nếu K lớn quá một ngưỡng nào đó thì độ chính xác của thuật toán có thể giảm vì K láng giềng này có thể thuộc về nhiều lớp khác nhau, dẫn đến độ tin cậy của việc phân lớp giảm. - Hàm khoảng cách: để tính khoảng cách giữa điểm cần phân loại và điểm trong tập dữ liệu huấn luyện. Có nhiều hàm khoảng cách và 14 tôi chọn hàm khoảng cách Euclidean vì sự đơn giản và phổ biến của nó. - Cách đánh trọng số các điểm lân cận: có nhiều cách đánh trọng số cho các điểm lân cận nhưng tôi chọn phương pháp đồng nhất (uniform) vì tính đơn giản. Ngoài các tham số trên của thuật toán KNN thì độ chính xác của thuật toán còn phụ thuộc vào số chiều của vec tơ đặc trưng biểu diễn mỗi điểm dữ liệu ( trong trường hợp này là một văn bản). 15 CHƯƠNG 3: TRIỂN KHAI VÀ ĐÁNH GIÁ HỆ THỐNG 3.1. Môi trường triển khai thử nghiệm 3.2. Mô tả d liệu Dưới đây là bảng thống kê số lượng văn bản theo 06 chủ đề được dùng trong thực nghiệm: Chủ đề TT Số lượng văn bản 1 Tin tức 450 2 Sức khỏe 450 3 Khoa học – Công nghệ 450 4 Thể thao 450 5 Giải trí 450 6 Giáo dục 450 Bảng 3.1 Số lượng văn bản theo chủ đề được dùng trong thực nghiệm 3.3. Sơ đồ phân lớp văn bản dùng KNN Hình 3.1. Sơ đồ phân lớp văn bản dùng KNN. 16 Trong thuật toán KNN đặc biệt ở chỗ nó không có giai đoạn huấn luyện mô hình. Tập văn N văn bản đã gán nhãn được vec tơ hóa dùng T -IDF thành N vec tơ (i=1...N). Tương tự Văn bản cần phân lớp cũng được vec tơ hóa thành vec tơ khoảng cách từ vec tơ . Sau đó thuật toán KNN tính N đến vec tơ (i=1...N), và chọn ra K (trong số N) văn bản có khoảng cách nhỏ nhất. Cuối cùng, chủ đề của văn bản cần phân loại là chủ đề chiếm đa số trong tập K văn bản. 3.4. Cấu hình tham số phân loại văn bản bằng KNN - Cấu hình cố định: + Cách tính trọng số: đồng nhất. + Tính khoảng cách: dùng khoảng cách euclidean. - Cấu hình thay đổi để so sánh hiệu suất hoạt động của hệ thống: + Số láng giềng được xét (k) có các giá trị: 2, 4, 6, 10, 12, 20, 30, 40. + Số chiều vec tơ đặc trưng biểu diễn văn bản: 500, 1000, 2000, 3000, 4000. 3.5. Kết quả thực nghiệm 3.5.1 Đánh giá thuật toán KNN Bảng 3.2 cho thấy hiệu suất hoạt động của thuật toán phân loại bằng KNN. Nó thể hiện độ chính xác khi thay đổi K và số các đặc trưng được trích xuất. Hệ thống có độ chính xác tốt nhất khi K = 12 và số chiều vec tơ đặc trưng là 4000 với tỷ lệ là 86,45%. Theo dõi kết quả ta có thể thấy với khi số chiều vec tơ đặc trưng càng tăng thì độ chính xác phân lớp càng tăng. Khi K lớn hơn hoặc bằng 2 và số 17 chiều vec tơ đặc trưng lớn hơn hoặc bằng 1000 thì tăng dần đều độ chính xác. Nếu K tăng từ 10 và số chiều vec tơ đặc trưng tăng từ 3000 thì độ chính xác tăng chậm lại, có cả giảm nhưng không đáng kể. Bảng 3.2. Độ chính xác nhận dạng theo số chiều của vectơ đặc trưng và K thay đổi (Đơn vị tính: %) Số chiều của vec tơ đặc trưng 500 1000 2000 3000 4000 K 2 77.60 80.05 80.47 80.69 81.08 4 81.17 82.82 83.09 84.10 84.48 6 82.09 83.97 84.91 85.18 85.65 10 82.69 84.53 85.49 86.36 86.27 12 82.85 85.07 85.83 86.43 86.45 20 83.09 85.29 86.12 86.18 86.14 30 83.07 85.60 86.23 86.32 86.43 40 83.34 85.67 85.89 86.10 86.27 18 3.5.2 So sánh với thuật toán phân loại Naive Bayes Naive Bayes cũng là thuật toán phân loại nhưng nó khác với KNN ở chỗ là Naive Bayes gồm hai giai đoạn là huấn luyện mô hình và kiểm thử mô hình, còn KNN thì không huấn luyện mô hình mà chỉ kiểm thử mô hình. Tôi đã huấn luyện Naive Bayes dùng 4500 văn bản và kiểm chứng dùng 450 văn bản, số chiều của vec tơ đặc trưng lần lượt là 500, 1000, 2000, 3000, 4000 và thu được kết quả như bảng 3.3. Bảng 3.3. Độ chính xác của Naive Bayes theo số chiều của vec tơ đặc trưng. (Đơn vị tính: %) Số chiều N 500 1000 2000 3000 4000 Độ chính xác của 80.99 83.85 85.09 85.85 86.00 Naive Bayes Bảng 3.3 cho ta thấy độ chính xác của thuật toán Naive Bayes tăng khi số chiều của vec tơ đặc trưng tăng. Khi so sánh với kết quả của bảng 3.2 thì ta có thể thấy độ chính xác cao nhất của thuật toán Naive Bayes là 86.00% và độ chính xác cao nhất của thuật toán KNN là 86.45% khi chạy cùng dữ liệu kiểm thử, dù thuật toán Naive Bayes phức tạp hơn nhưng độ chính xác khi thực nghiệm vẫn không bằng độ chính xác của thuật toán đơn giản hơn là KNN, đây chính là lý do mà tôi chọn thuật toán KNN trong bài toán phân loại văn bản.