CHƯƠNG 1: CƠ SỞ LÝ LUẬN 1. Tổng quan về thuật toán K-NN 1.1 Khái niệm thuật toán K-NN: “Hãy cho tôi biết bạn của bạn là ai, tôi sẽ cho bạn biết bạn là người như thế nào.” Danh ngôn dân gian. Đó là một câu danh ngôn phổ biến, để dự đoán một người ta dựa vào bạn bè, người thân xung quanh họ, tương tự thuật toán K-NN cũng có ý tưởng như vậy, từ đó ta có thể phát biểu về thuật toán K-NN như sau: Thuật toán K-NN (K-Nearest Neighbors nghĩa là K-hàng xóm gần nhất) [2] [3] [4] [5] là một trong những thuật toán học có giám sát [6] [7] căn bản nhất, đơn giản nhất, trực quan nhất dùng để phân loại dữ liệu, thuật toán này dùng để phân loại một đối tượng dựa vào các đối tượng hoặc lớp trong tập tham chiếu xung quanh, đối tượng sẽ được phân loại cùng với đối tượng hoặc lớp có nhiều nét tương đồng nhất. Thuật toán này không cần học hỏi từ dữ liệu cũ.2 Lịch sử ra đời thuật toán K-NN: K-NN là một phương pháp đơn giản nên từ rất sớm đã được đề cập đến, người đầu tiên là nhà khoa học Ibn al-Haytham (965-1040) [9].
Trong lĩnh vực quang học và nhận thức, K-NN được nhắc đến trong cuốn sách của ông - Lý thuyết nhận thức thị giác của Alhacen, dưới những nguyên tắc: “Các cá thể của một loài nào đó sẽ giống hệt nhau, các cá thể khác nhau theo các đặc điểm riêng biệt có thể nhận biết bằng mắt”. Quan điểm này giống như là hỗn hợp của K-NN và quy tắc trung bình gần nhất, khi xác định các dạng phổ quát. Tuy nhiên đây chỉ là nguyên tắc, đến thế kỉ XIV, những nguyên lý cơ bản của K- NN được Ockham đưa ra “chọn giả thuyết với ít giả thuyết nhất”. Có thể hiểu đây là luật SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 4 Khóa luận tốt nghiệp GVHD : TS.
Nguyễn Đình Hoa Cương của K-NN cho các thuộc tính định danh, tuy nhiên Ockham nhấn mạnh đây chỉ là các xây dựng trên ý tưởng chứ không phải xây dựng trên các dạng quan sát [9]. Mãi đến một thời gian rất lâu sau này, thuật toán K-NN lần đầu tiền được đề xuất và công bố rõ ràng, đầy đủ vào năm 1951 bởi Fix và Hodges [8] [9], đây là thuật toán lâu đời và đơn giản của thuật toán mô hình phân loại. Từ nhu cầu xác định một ẩn số mà không biết hoặc khó xác định các tham số của nó, phương pháp này được xây dựng lên để xử lý vấn đề này. Đến năm 1962 thì được Sebestyen gọi là Thuật toán gần gũi [9].
Năm 1965 thì được gọi là Phân loại khoảng cách tối thiểu bởi Cover và Hart [9]. Tuy nhiên chính xác và phổ biến vẫn là của Fix và Hodges.3 Nội dung thuật toán K-NN: Thuật toán K-NN dùng để phân loại một đối tượng dựa vào độ tương tự với K đối tượng xung quanh trong một tập tham chiếu. K là số nguyên dương được chọn trước khi tính toán. Với thuật toán này ta có 5 bước để thực hiện [4]: Bước 1 : Xác định giá trị tham số K (số láng giềng gần nhất).
Bước 2 : Tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong không gian xung quanh (thường sử dụng khoảng Euclid, Manhettan). Bước 3 : 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 tượng chính. Bước 4 : Lấy tất cả các lớp của K láng giềng gần nhất đã xác định. Bước 5 : Dựa vào các lớp của láng giềng gần nhất để xác định lớp cho đối tượng chính.
SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 5 Khóa luận tốt nghiệp GVHD : TS. Nguyễn Đình Hoa Cương Hình 1: Lưu đồ thuật toán của thuật toán K-NN 1.1 Ưu điểm của phương pháp K-NN: Thuật toán K-NN được sử dụng rộng rãi vì có nhiều ưu điểm như [2] [6]: Rất đơn giản, dễ học và thực hiện còn gọi là học lười vì khi thực hiện thì không cần xây dựng các mô hình trên tập tham chiếu, nghĩa là không cần gom các văn bản giống nhau thành một nhóm để tính toán, có thể để ngẫu nhiên như vậy để thực hiện. Có thể làm việc trên nhiều loại dữ liệu khác nhau như dữ liệu số, văn bản, đối tượng cụ thể, đồ vật. Giải quyết tốt các vấn đề phân loại, hồi quy, gộp nhóm với tỷ lệ chính xác cao mà lại đơn giản để thực hiện.
Ứng dụng thành công trong rất nhiều lĩnh vực như phân loại thông tin, phân loại số liệu, phân loại văn bản, từ ngữ, phân loại đối tượng trừu tượng. SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 6 Khóa luận tốt nghiệp GVHD : TS. Nguyễn Đình Hoa Cương 1.2 Nhược điểm của phương pháp K-NN: Tuy nhiên thuật toán K-NN vẫn có một số nhược điểm như [2] [10]: Chỉ có thể phân loại thông tin chứ không có khả năng phân tích để tìm ra thông tin có giá trị. Chỉ có thể áp dụng trong lĩnh vực phân loại.
Vì phải tính khoảng cách đến tất cả đối tượng, rồi xác định độ tương tự nên với một dữ liệu lớn thì sẽ rất mất thời gian để phân tích. Dễ bị ảnh hưởng bởi “nhiễu”, là các đối tượng ở gần đối tượng cần phân loại nhưng chỉ là một lớp nhỏ, nên khi xét trong một tham chiếu K ít đối tượng thì rất dễ ảnh hưởng đến độ chính xác của kết quả.4 Ví dụ đơn giản về K-NN: Hình 2 : Mô tả phương pháp K-NN ( Wikipedia 2007 ) Hãy xác định đối tượng hình tròn sẽ thuộc lớp với hình vuông hay là thuộc lớp với hình tam giác ? Xét vòng tròn nhỏ nét liền ở trong, tức là ta lấy K = 3, thì ta thấy có 2 hình tam giác đứng gần hình tròn hơn so với chỉ 1 hình vuông, nên hình tròn sẽ được phân loại thuộc lớp với hình tam giác. Nhưng nếu ta lấy mẫu K = 5 thì sao ? Tức là xét vòng tròn nét đứt ở ngoài, ta thấy có 3 hình vuông đứng gần với hình tròn hơn so với có 2 hình tam giác nên hình tròn sẽ được phân loại thuộc lớp với hình vuông. SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 7 Khóa luận tốt nghiệp GVHD : TS.
Nguyễn Đình Hoa Cương Ở đây ta thấy có sự khác nhau nếu ta lấy K đối tượng khác nhau, vì chỉ có ít đối tượng để xét đến, nên theo nhược điểm của K-NN có thể gọi các hình tam giác này là nhiễu, gây ảnh hưởng đến kết quả cuối cùng. Tuy nhiên, các đối tượng ở đây đã được xem như là cùng 1 định dạng tương tự nhau và khoảng cách giữa các đối tượng đã được tính toán và sắp xếp, nhưng trong đề tài này thì sẽ rắc rối hơn, ta phải tính toán nhiều việc. Sau đây là giới thiệu về các công việc phải làm để có thể giải quyết thuật toán K-NN trong tư vấn thông tin. Công thức tính TF-IDF: 2.1 Khái niệm: TF-IDF [11] [12] là từ viết tắt của thuật ngữ Term Frequency – Inverse Document Frequency nghĩa là trọng số của một từ trong một văn bản mà văn bản đó lại thuộc một tập tham chiếu nhiều văn bản khác, trọng số này thể hiện độ quan trọng của từ đó trong văn bản thuộc một tập các văn bản.
Phương pháp này thường được sử dụng trong phân tích từ vựng vì luôn có các từ được sử dụng nhiều hơn các từ khác là các từ thông dụng, nhưng không có nhiều ý nghĩa và quan trọng, Zipf’s law đã phát biểu về vến đề này [13]. Biểu đồ 1 : Sơ đồ minh họa phát biểu của Zipf’s law (viblo 2016). Phát biểu này đúng với mọi ngôn ngữ nên ta cần cân bằng mức độ quan trọng của các từ trong ngôn ngữ. Nên phương pháp TF-IDF đã được đề xuất.
SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 8 Khóa luận tốt nghiệp GVHD : TS. Nguyễn Đình Hoa Cương Đây là 1 trong những kỹ thuật để xử lý ngôn ngữ tự nhiên căn bản và thường được áp dụng vào nhiều thuật toán khác như K-NN để phân tích dữ liệu văn bản, tóm tắt văn bản, tìm kiếm thông tin. TF-IDF là kết hợp gồm 2 phần TF và IDF, ta sẽ tiếp tục tìm hiểu về 2 phần này.2 TF: TF [11] [12] là viết tắt của Term Frequency nghĩa là tần số xuất hiện của một từ trong một văn bản, mỗi văn bản thì có số kí tự hay chiều dài khác nhau, một từ có thể xuất hiện ít hoặc nhiều hơn tùy vào văn bản, nên để tính tần số xuất hiện thì ta lấy số lần từ đó xuất hiện và chia cho tổng số từ trong văn bản. Ta có công thức tính TF: , , , ∶ (1) Trong đó : f (t,d) là Tần số xuất hiện của từ t trong văn bản d.
Kết quả tính được sẽ nằm trong khoảng 0 đến 1. Giá trị TF càng lớn thì chứng tỏ văn bản d phụ thuộc rất nhiều vào từ t.3 IDF: Còn IDF [11] [12] là viết tắt của từ Inverse Document Frequency nghĩa là tần số nghịch của 1 từ trong tập văn bản xét đến hay còn gọi là độ quan trọng của từ đó trong văn bản. Nhưng có nhiều từ rất phổ biến mà lại không quan trọng trong văn bản như “và”, “thì”, “sẽ”, “nếu”, “nhưng”. là các từ phổ biến như Zipf’s law đã nói, nếu chỉ với công thức TF thì các từ này sẽ có tần số xuất hiện rất cao, còn những từ quan trọng thì lại rất ít, mà các từ quan trọng chính trong văn bản lại mạng giá trị cao hơn, nhiều thông tin hơn so với các từ phổ biến, để hạn chế nhược điểm này thì ta cần loại bỏ để tăng tính chính xác, từ đó ta có công thức IDF.
SV: Ngô Minh Nhật – K47 Tin Học Kinh Tế 9 Khóa luận tốt nghiệp GVHD : TS. Nguyễn Đình Hoa Cương | | , | ∶ | (2) Trong đó: | D | là tổng số văn bản trong tập hợp D. | { d D : t d } | là số văn bản có chứa từ t. Log e là để giảm đi độ quan trọng của các từ phổ biến mà không có giá trị hoặc giá trị rất thấp trong IDF như đã nói ở trên.
Vì với các từ mà xuất hiện trong càng nhiều văn bản thì thương số D/d càng bé, nên chỉ xuất hiện trong 1 văn bản thì giá trị IDF này là lớn nhất.