MỞ ĐẦU Ngày nay, Big Data – dữ liệu lớn hiện đã trở thành một thuật ngữ phổ biến và thịnh hành trong nhiều lĩnh vực công nghiệp và học thuật. Nó đƣợc sử dụng để mô tả một loạt các khái niệm từ khả năng công nghệ để lƣu trữ, tổng hợp và xử lý dữ liệu. Việc xử lý một lƣợng lớn dữ liệu đang trở thành một nhiệm vụ cần thiết trong một số lƣợng lớn các ứng dụng trong thế giới thực. Khi nói đến việc đối phó với bộ dữ liệu lớn, các tiêu chuẩn của các kỹ thuật khai thác dữ liệu thƣờng không giải quyết đƣợc khối lƣợng nhƣ vậy do đó các thuật toán trở nên kém hiệu quả.
KNN là một phƣơng pháp học có giám sát khai thác dữ liệu đơn giản đƣợc sử dụng rộng rãi nhất trong lĩnh vực học máy vì tính đơn giản nhƣng hiệu quả nổi tiếng rộng rãi trong khai thác dữ liệu. 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áy lƣời học, 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. 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 trong tập dữ liệu huấn luyện gần nó nhất (K-lân cận), không quan tâm đến việc có một vài điểm dữ liệu trong những điểm gần nhất này là nhiễu. Có một điều đáng lƣu ý là KNN phải nhớ tất cả các điểm dữ liệu huấn luyện, việc này không đƣợc lợi về cả bộ nhớ và thời gian tính toán đối với dữ liệu lớn.
Ứng dụng thực tế của mô hình này trong miền dữ liệu lớn là không khả thi do hạn chế về thời gian và bộ nhớ. Một số giải pháp thay thế phân tán đã đƣợc đề xuất để cho phép phƣơng pháp này xử lý dữ liệu quy mô lớn. Tuy nhiên, hiệu suất của chúng có thể đƣợc cải thiện hơn nữa với các thiết kế mới phù hợp với các công nghệ mới phát sinh. Ngoài ra, trong thời gian tác giả hoàn thành luận văn này, đại dịch COVID-19 vẫn đang diễn biến phức tạp, e 2 các nhà khoa học đã công bố các công trình nghiên cứu khai thác dữ liệu đã đƣợc phát triển trong đó có mô một số công trình có sử dụng mô hình KNN để đƣa ra các giải pháp nhằm dự báo và điều trị góp phần giúp thế giới ngăn chặn đại dịch.
Với tầm quan trọng của bài toán trong nghiên cứu cũng nhƣ ứng dụng, tôi chọn “Sử dụng thuật toán KNN kết hợp với bài toán điểm biên cho khai phá dữ liệu lớn trong Spark” làm đề tài nghiên cứu cho luận văn của mình. Luận văn đƣợc kiến trúc thành 03 chƣơng chính. Chƣơng 1 Tổng quan về khai phá dữ liệu và thuật toán KNN trong Spark. Chƣơng 2 Thuật toán KNN kết hợp với bài toán điểm biên trong Spark cho bài toán dữ liệu lớn.
Chƣơng 3 Cài đặt mô phỏng thực nghiệm. Cuối mỗi chƣơng đều có phần Tiểu kết để tổng kết lại nội dung của chƣơng. Ngoài các chƣơng chính đã nêu trên, luận văn kết thúc với phần Kết luận và hƣớng phát triển để tóm tắt những kết quả đạt đƣợc, những vấn đề còn tồn tại và dự kiến hƣớng phát triển tiếp theo của luận văn. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KNN TRONG SPARK Trong chƣơng đầu tiên này, do hạn chế về mục tiêu và phạm vi nghiên cứu của đề tài, nội dung chƣơng này luận văn không đi sâu mà chỉ giới thiệu một cách tổng quan về Khai phá dữ liệu (KPDL).
Đồng thời cũng trình bày tổng quan thuật toán KNN trong lĩnh vực khai phá dữ liệu nói chung và KPDL lớn nói riêng. Bên cạnh đó luận văn cũng giới thiệu về nền tảng Spark trong xử lý dữ liệu lớn làm cơ sở lý thuyết để tiếp tục đi sâu, phân tích và trình bày nội chính của luận văn ở các chƣơng tiếp theo. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Khai phá dữ liệu (KPDL) là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu).
Về bản chất, KPDL liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, KPDL là một bƣớc đặc biệt trong toàn bộ tiến trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) (hay các mô hình) từ dữ liệu. Trong những năm trở lại đây, lƣợng thông tin đã đƣợc chuyển sang dạng kỹ thuật số lƣu trữ trên các thiết bị điện tử, trên các phƣơng tiện truyền thông, mạng xã hội không ngừng tăng lên dẫn đến việc hình thành các kho dữ liệu khổng lồ.
Với việc tích lũy thông tin trong các kho này thách thức vẫn tồn tại là làm thế nào để trích xuất có ý nghĩa kiến thức từ nó. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Ngƣời ta ƣớc đoán rằng lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lƣợng cũng nhƣ e 4 kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Nói một cách hình ảnh là chúng ta đang ngập trong dữ liệu nhƣng lại “đói” tri thức.
Câu hỏi đặt ra là liệu chúng ta có thể khai thác đƣợc gì từ những “núi” dữ liệu tƣởng chừng nhƣ “bỏ đi” ấy không? Dữ liệu lớn gây ra một sự bùng nổ về sử dụng nhiều kỹ thuật khai phá dữ liệu hơn, một phần vì kích thƣớc thông tin lớn hơn rất nhiều và vì thông tin có xu hƣớng đa dạng và mở rộng hơn về chính bản chất và nội dung của nó. Data mining - khai phá dữ liệu là lĩnh vực đóng vai trò quan trọng trong việc phân tích và quản lý dữ liệu. Dựa vào đó chúng ta có thể đƣa ra những dự đoán cho kế hoạch tƣơng lai. Data Mining – khai phá dữ liệu ra đời nhƣ một hƣớng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên.
Khái niệm Khai phá dữ liệu là một tiến trình sử dụng các công cụ phân tích dữ liệu khác nhau để khám phá ra các mẫu dƣới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan hệ giữa các dữ kiện, đối tƣợng bên trong CSDL, kết quả của việc khai phá là xác định các mẫu hay các mô hình đang tồn tại bên trong, nhƣng chúng nằm ẩn khuất ở các CSDL. Để từ đó rút trích ra đƣợc các mẫu, các mô hình hay các thông tin và tri thức từ các CSDL [1]. Khai phá dữ liệu (datamining) đƣợc định nghĩa nhƣ là một quá trình chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Thuật ngữ Dataming ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lƣợng lớn các dữ liệu thô.
Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng tự với từ Datamining nhƣ Knowledge Mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/patern analysis (phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging (nạo vét dữ liệu). Khai phá dữ liệu (data mining) là quá trình tính toán để tìm ra các mẫu trong các bộ dữ liệu lớn liên quan đến các phƣơng pháp tại giao điểm của máy e 5 học, thống kê và các hệ thống cơ sở dữ liệu. Đây là một lĩnh vực liên ngành của khoa học máy tính.[2] Mục tiêu tổng thể của quá trình khai thác dữ liệu là trích xuất thông tin từ một bộ dữ liệu và chuyển nó thành một cấu trúc dễ hiểu để sử dụng tiếp. Ngoài bƣớc phân tích thô, nó còn liên quan tới cơ sở dữ liệu và các khía cạnh quản lý dữ liệu, xử lý dữ liệu trƣớc, suy xét mô hình và suy luận thống kê, các thƣớc đo thú vị, các cân nhắc phức tạp, xuất kết quả về các cấu trúc đƣợc phát hiện, hiện hình hóa và cập nhật trực tuyến.
Khai thác dữ liệu là bƣớc phân tích của quá trình "khám phá kiến thức trong cơ sở dữ liệu". Nói tóm lại, khai phá dữ liệu là một tập hợp các kỹ thuật đƣợc sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. Quá trình khai phá dữ liệu Quá trình khai phá dữ liệu là một quá trình phức tạp bao gồm kho dữ liệu chuyên sâu cũng nhƣ các công nghệ tính toán. Hơn nữa, KPDL không chỉ giới hạn trong việc trích xuất dữ liệu mà còn đƣợc sử dụng để chuyển đổi, làm sạch, tích hợp dữ liệu và phân tích mẫu.
Các giải thuật KPDL thƣờng đƣợc mô tả nhƣ những chƣơng trình hoạt động trực tiếp trên tệp dữ liệu. Với các phƣơng pháp học máy và thống kê trƣớc đây, thƣờng thì bƣớc đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng đƣợc. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích đƣợc.
Quá trình xử lý KPDL bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bƣớc tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành e 6 dạng sao cho giải thuật KPDL có thể hiểu đƣợc.