BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC QUY NHƠN NGUYỄN THỊ LÝ PHƢƠNG 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 Chuyên ngành: Khoa học máy tính Mã số: 8480101 Ngƣời hƣớng dẫn: TS. Hồ Văn Lâm LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu của tôi, không sao chép ở bất kỳ công trình khoa học nào trƣớc đây. Các kết quả nêu trong luận văn có nguồn gốc rõ ràng và đƣợc trích dẫn đầy đủ. Luận văn đƣợc hoàn thành trong thời gian tôi làm Học viên Cao học tại Khoa Công nghệ Thông tin, Trƣờng Đại học Quy Nhơn. Tôi xin chịu hoàn toàn trách nhiệm về luận văn này. Quy Nhơn, ngày tháng năm 2021 Học viên Nguyễn Thị Lý Phƣơng LỜI CẢM ƠN Tôi xin chân thành cảm ơn các thầy cô giáo trong Khoa Công nghệ thông tin Trƣờng Đại học Quy Nhơn đã truyền đạt kiến thức bổ ích, đồng thời xin cảm ơn Phòng Đào Tạo Sau đại học Trƣờng Đại học Quy Nhơn đã tạo mọi điều kiện thuận lợi trong quá trình học tập và thực hiện luận văn tốt nghiệp. Tôi cũng xin gửi lời biết ơn chân thành đến TS. Hồ Văn Lâm, ngƣời đã tận tình hƣớng dẫn và góp ý cho tôi trong suốt quá trình nghiên cứu, cho tôi nhiều lời động viên cũng nhƣ những hƣớng dẫn quý báu để tôi có thể thực hiện tốt đƣợc đề tài này. Trong quá trình thực hiện đề tài, không thể không kể đến sự giúp đỡ, đóng góp ý kiến và những lời động viên từ phía gia đình, ngƣời thân, đồng nghiệp và bạn bè xung quanh, điều này thật sự là động lực lớn giúp tôi hoàn thành tốt đề tài nghiên cứu của mình. Xin chân thành cảm ơn! Học viên Nguyễn Thị Lý Phƣơng MỤC LỤC LỜI CAM ĐOAN LỜI CẢM ƠN DANH MỤC CÁC CHỮ VIẾT TẮT DANH MỤC HÌNH ẢNH MỞ ĐẦU .......................................................................................................... 1 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KNN TRONG SPARK ..............................................................................................3 1.1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU........................................................3 1.1.1. Khái niệm ..................................................................................................4 1.1.2. Quá trình khai phá dữ liệu .........................................................................5 1.1.3. Các bƣớc trong quá trình khai phá dữ liệu ................................................7 1.1.4. Khái quát về các kỹ thuật KPDL ..............................................................8 1.1.5. Ứng dụng của KPDL ...............................................................................10 1.1.6. Những thách thức trong nghiên cứu và ứng dụng của KPDL.................12 1.2. THUẬT TOÁN KNN TRONG KHAI PHÁ DỮ LIỆU ................................13 1.2.1. Giới thiệu chung về KNN .......................................................................13 1.2.2. Cơ sở toán học của thuật toán KNN cho bài toán phân lớp ....................14 1.2.3. Thuật toán KNN cho bài toán phân lớp ..................................................15 1.2.4. Ứng dụng của KNN ................................................................................15 1.2.5. Thách thức và ƣu điểm của KNN ...........................................................16 1.3. TỔNG QUAN VỀ SPARK ..............................................................................16 1.3.1. Giới thiệu về Apache Spark ....................................................................17 1.3.2. Thành phần cơ bản của Spark .................................................................18 1.3.3. Những điểm nổi bật của Spark và mục tiêu sử dụng ..............................19 1.4. TIỂU KẾT CHƢƠNG 1 ..................................................................................20 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 ...........................................21 2.1. GIỚI THIỆU CHUNG VÀ PHÁT BIỂU BÀI TOÁN ..................................21 2.1.1. Giới thiệu.................................................................................................21 2.1.2. Phát biểu bài toán ....................................................................................22 2.2. THUẬN TOÁN KNN VÀ BÀI TOÁN ĐIỂM BIÊN CHO DỮ LIỆU LỚN ..........................................................................................................................23 2.2.1. Ý tƣởng của KNN ...................................................................................24 2.2.2. Thuật toán phân lớp KNN .......................................................................24 2.2.3. Điểm biên bà ứng dụng trong xử lý dữ liệu lớn ......................................25 2.3. THUẬT TOÁN KNN KẾT HỢP BÀI TOÁN ĐIỂM BIÊN CHO DỮ LIỆU LỚN ..........................................................................................................................30 2.3.1. Thuật toán KNN cho dữ liệu lớn .............................................................30 2.3.2. Kết hợp KNN và bài toán điểm biên cho dữ liệu lớn .............................31 2.3.3. Ý tƣởng kết hợp KNN và bài toán điểm biên cho dữ liệu lớn ................31 2.3.4. Phƣơng pháp kết hợp KNN và bài toán điểm biên cho dữ liệu lớn ........32 2.3.5. Thuật toán kết hợp KNN và bài toán điểm biên cho dữ liệu lớn ............33 2.4. TRIỂN KHAI THUẬT TOÁN KNN KẾT HỢP BÀI TOÁN ĐIỂM BIÊN CHO DỮ LIỆU LỚN TRONG SPARK ................................................................36 2.4.1. Giới thiệu.................................................................................................37 2.4.2. Tổng quan về KNN Tham gia bằng MapReduce dựa trên Hadoop ........38 2.4.3. Triển khai KNN kết hợp với bài toán điểm biên dựa trên Spark ............39 2.5. TIỂU KẾT CHƢƠNG 2 ..................................................................................41 CHƢƠNG 3. CÀI ĐẶT MÔ PHỎNG THỰC NGHIỆM ...................................42 3.1. MÔI TRƢỜNG VÀ CÔNG CỤ ......................................................................42 3.1.1. Phát biểu bài toàn ....................................................................................42 3.1.2. Môi trƣờng và ngôn ngữ lập trình ...........................................................42 3.1.3. Công cụ và thƣ viện ................................................................................43 3.1.4. Bộ dữ liệu ................................................................................................43 3.2. CÀI ĐẶT MÔ PHỎNG ...................................................................................43 3.2.1. Cài đặt .....................................................................................................43 3.2.2. Các tham số và kết quả đạt đƣợc ............................................................45 3.2.3. So sánh và đánh giá kết quả đạt đƣợc .....................................................46 KẾT LUẬN ..............................................................................................................48 TÀI LIỆU THAM KHẢO ......................................................................................49 DANH MỤC CÁC CHỮ VIẾT TẮT Chữ viết tắt Tên đầy đủ Nghĩa tiếng Việt KPDL Data minining Khái phá dữ liệu KDD Knowledge Discovery in Phát hiện tri thức trong cơ sở Database dữ liệu CSDL Database Cơ sở dữ liệu KNN K-nearest neighbors K-Hàng xóm gần nhất RDD Resilient Distributed Cấu trúc dữ liệu cơ bản của Datasets Spark PCA Principal Component Thuật toán phân tích thành Analysis phần DANH MỤC HÌNH ẢNH Hình 1.1. Quá trình KPDL ........................................................................................6 Hình 1.2. Các bƣớc trong KPDL ..............................................................................7 Hình 1.3. Một ví dụ về cách tính khoảng cách d giữa hai điểm dữ liệu trong không gian hai chiều...............................................................................14 Hình 1.4. Các mốc thời gian phát triển của Spark ................................................17 Hình 1.5. Các thành phần cơ bản của Spark ..........................................................18 Hình 2.1. Ví dụ về điểm ranh giới là các điểm dữ liệu nằm ở lề của (hoặc cụm) dữ liệu đƣợc phân phối dày đặc. ..................................................26 Hình 2.2. Không thể vẽ một đƣờng thẳng để phân tách các lớp trong không gian đặc trƣng này một cách hoàn hảo. Ba dòng có thể đƣợc vẽ, nhƣng mỗi dòng dẫn đến một số phân loại sai. ....................................27 Hình 2.3. Quyết định ranh giới theo 1-NN cho các điểm dữ liệu của các lớp khác biệt với nhau...................................................................................28 Hình 2.4. Các vùng lân cận gần nhất cho tập dữ liệu huấn luyện gồm hai lớp, trong đó các mẫu huấn luyện của một lớp đƣợc hiển thị với dấu „*‟ màu đỏ, các vùng của lớp kia đƣợc hiển thị bằng „◦‟ màu xanh lam. ..........................................................................................................28 Hình 2.5. Ranh giới quyết định và các vùng quyết định cho bộ phân 1-NN cho hai lớp. ..............................................................................................29 Hình 2.6. Các vùng lân cận gần nhất cho tập dữ liệu huấn luyện gồm ba lớp .....29 Hình 2.7. Ranh giới quyết định và các vùng quyết định cho bộ phân loại hàng xóm 1-NN cho ba lớp....................................................................30 Hình 2.8. Tính không hiệu quả của thƣớc đo khoảng cách đến trung tâm của cụm nhƣ một tiêu chí duy nhất để chọn cụm thích hợp .......................31 Hình 2.9. Ảnh hƣởng của mật độ cụm đến hiệu suất của thuật toán KNN. .........33 Hình 2.10. KNN kết hợp với bài toán điểm biên bằng Spark ...............................41 1 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, 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. 3 CHƢƠNG 1. 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. 1.1. 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ƣ 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. 1.1.1. 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 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 đó. 1.1.2. 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 6 dạng sao cho giải thuật KPDL có thể hiểu đƣợc. Về lý thuyết thì có vẻ rất đơn giản nhƣng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vƣớng mắc nhƣ: các dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết xuất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi),… Bƣớc tiếp theo là chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn tƣơng ứng với các ý nghĩa đó (thƣờng đƣợc biểu diễn dƣới dạng các luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy,…) Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới có thể đuợc đo tƣơng ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trƣớc đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ giữa phƣơng pháp tìm mới và phƣơng pháp cũ nhƣ thế nào). Thƣờng thì độ mới của mẫu đƣợc đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu còn phải có khả năng sử dụng tiềm tàng. Các mẫu này sau khi đƣợc xử lý và diễn giải phải dẫn đến những hành động có ích nào đó đƣợc đánh giá bằng một hàm lợi ích. Mẫu khai thác đƣợc phải có giá trị đối với các dữ liệu mới với độ chính xác nào đó. Hình 1.1. Quá trình KPDL 7 1.1.3. Các bƣớc trong quá trình khai phá dữ liệu Về cơ bản các bƣớc quan trọng khi KPDL bao gồm: Bước 1: Làm sạch dữ liệu – Trong bƣớc này, dữ liệu đƣợc làm sạch sao cho không có tạp âm hay bất thƣờng trong dữ liệu. Bước 2: Tích hợp dữ liệu – Trong quá trình tích hợp dữ liệu, nhiều nguồn dữ liệu sẽ kết hợp lại thành một. Bước 3: Lựa chọn dữ liệu – Trong bƣớc này, dữ liệu đƣợc trích xuất từ cơ sở dữ liệu. Bước 4: Chuyển đổi dữ liệu – Trong bƣớc này, dữ liệu sẽ đƣợc chuyển đổi để thực hiện phân tích tóm tắt cũng nhƣ các hoạt động tổng hợp. Bước 5: Khai phá dữ liệu – Trong bƣớc này, chúng tôi trích xuất dữ liệu hữu ích từ nhóm dữ liệu hiện có. Bước 6: Đánh giá mẫu – Chúng tôi phân tích một số mẫu có trong dữ liệu. Bước 7: Trình bày thông tin – Trong bƣớc cuối cùng, thông tin sẽ đƣợc thể hiện dƣới dạng cây, bảng, biểu đồ và ma trận. Hình 1.2. Các bƣớc trong KPDL 8 1.1.4. Khái quát về các kỹ thuật KPDL Kỹ thuật KPDL thực chất là phƣơng pháp không hoàn toàn mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã đƣợc nghiên cứu từ trƣớc nhƣ máy học, nhận dạng, thống kê (hồi quy, xếp loại, phân cụm), các mô hình đồ thị, các mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia, v.v… Tuy nhiên, với sự kết hợp tài tình của KPDL, kỹ thuật này có ƣu thế hơn hẳn các phƣơng pháp trƣớc đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học. Một số kỹ thuật cốt lõi, đƣợc sử dụng trong khai phá dữ liệu, mô tả kiểu hoạt động khai phá và hoạt động phục hồi dữ liệu. 1.1.4.1. Khai thác tập phổ biến và luật kết hợp Đây là tiến trình khám phá các tập giá trị thuộc tính xuất hiện phổ biến trong các đối tƣợng dữ liệu. Từ tập phổ biến có thể tạo ra các luật kết hợp giữa các giá trị thuộc tính nhằm phản ánh khả năng xuất hiện đồng thời các giá trị thuộc tính trong tập các đối tƣợng. Một luật kết hợp X → Y phản ánh sự xuất hiện của tập X dẫn đến sự xuất hiện đồng thời của tập Y. Chẳng hạn phân tích CSDL bán hàng nhận đƣợc thông tin về những khách hàng mua máy tính có khuynh hƣớng mua phần mềm quản lý nhân sự trong cùng lần mua đƣợc miêu tả bằng luật kết hợp. Luật kết hợp giúp các nhà hoạch định hiểu rõ xu thế bán hàng, tâm lý khách hàng, ... từ đó đƣa ra chiến lƣợc bố trí mặt hàng, kinh doanh, tiếp thị,... 1.1.4.2. Phân lớp dữ liệu Phân lớp (Classification): Là tiến trình khám phá các luật phân loại hay đặc trƣng cho các tập dữ liệu đã đƣợc xếp lớp. Tập dữ liệu học bao gồm tập đối tƣợng đã đƣợc xác định lớp sẽ đƣợc dùng để tạo mô hình phân lớp dựa trên đặc trƣng của đối tƣợng trong tập dữ liệu học. Các luật phân lớp đƣợc sử dụng để xây dựng các bộ phân lớp dữ liệu. Phân lớp dữ liệu có vai trò quan 9 trọng trong tiến trình dự báo các khuynh hƣớng quy luật phát triển. Áp dụng vào tiến trình phân lớp dữ liệu khách hàng trong CSDL có thể xây dựng các luật phân lớp khách hàng [3]. Một số kỹ thuật thƣờng đƣợc sử dụng trong phân lớp: Cây quyết định (Decision tree): Cấu trúc dạng hình cây là biểu thị cho các quyết định. Các quyết định này sinh ra các quy tắc để phân lớp và dự đoán (dự báo) tập dữ liệu mới chƣa đƣợc phân lớp. Tri thức đƣợc rút ra trong kỹ thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản, trực quan, dễ hiểu đối với ngƣời sử dụng. Tuy vậy, nó cũng đòi hỏi một không gian nhất định để mô tả tri thức trong phạm vi mà con ngƣời có thể hiểu đƣợc [4]. Mạng Nơron (Neural Network): Đây là một trong những kỹ thuật đƣợc ứng dụng rất phổ biến hiện nay vì kỹ thuật này bắt chƣớc khả năng tìm kiếm mẫu của bộ não con ngƣời. Việc huấn luyện theo phƣơng pháp này đƣợc bắt đầu bằng việc cho vào một tập dữ liệu (gọi là tập dữ liệu huấn luyện) mạng sẽ tự động điều chỉnh (học) qua từng lớp trong mạng và cho ra kết quả, quá trình huấn luyện đƣợc lặp đi lặp lại nhiều lần. Sau khi mạng học thành công thì nó đƣợc xem là một chuyên gia trong lĩnh vực đó [4]. Phân cụm: Phân cụm hay gom cụm (clustering): Là tiến trình nhận diện các cụm tiềm ẩn trong tập các đối tƣợng chƣa đƣợc xếp lớp. Tiến trình phân cụm dựa trên mức độ tƣơng tự giữa các đối tƣợng. Các đối tƣợng đƣợc gom cụm sao cho mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là cực đại và mức độ tƣơng tự giữa các đối tƣợng nằm trong các cụm khác nhau là cực tiểu. Các cụm đƣợc đặc trƣng bằng các tính chất chung của tất cả các đối tƣợng trong cụm. Do vậy, khảo sát các cụm sẽ giúp khái quát, tổng kết nhanh chóng nội dung của khối dữ liệu lớn [5]. Một số kỹ thuật dùng trong gom cụm: phƣơng pháp phân cấp và thuật giải k-means. Trong phƣơng pháp phân cấp gồm hai giai đoạn: ở giai đoạn gộp mỗi 10 đối tƣợng thuộc về một lớp, dƣới một ngƣỡng nào đó chúng đƣợc gom lại và tiếp tục nhƣ vậy cho đến khi tất cả các đối tƣợng thuộc về cùng một cụm; còn ở giai đoạn tách sẽ tiến hành ngƣợc lại so với giai đoạn gộp. Trong phƣơng pháp này, để đƣa ra đƣợc ngƣỡng ngƣời ta dựa vào liên kết đơn (khoảng cách gần nhất) và liên kết đôi (khoảng cách xa nhất) giữa hai cụm [4]. Trong thuật giai k-means: khi tiến hành gom cụm ta cần phải biết trƣớc số cụm. Với mỗi cụm nhƣ vậy ta chọn phần tử trọng tâm, tiếp đến tính khoảng cách từ mỗi đối tƣợng đến phần tử trọng tâm ở tất cả các cụm và gán nó vào cụm có khoảng cách nhỏ nhất. Quá trình này tiếp tục nhƣ vậy cho đến khi các cụm không còn biến đổi hoặc thoả điều kiện đặt ra. 1.1.4.3. Các mẫu tuần tự Thƣờng đƣợc sử dụng trên các dữ liệu dài hạn, các mẫu tuần tự là một phƣơng pháp có ích để nhận biết các xu hƣớng hay các sự xuất hiện thƣờng xuyên của các sự kiện tƣơng tự 1.1.4.4. Các tổ hợp Trong thực tế, thật hiếm khi sẽ sử dụng một kỹ thuật trong số những kỹ thuật riêng biệt này. Việc phân loại và phân cụm là những kỹ thuật giống nhau. Nhờ sử dụng việc phân cụm để nhận ra các thông tin lân cận gần nhất, có thể tiếp tục tinh chỉnh việc phân loại của mình. Thông thƣờng, sử dụng các cây quyết định để giúp xây dựng và nhận ra các loại mà có thể theo dõi chúng trong một thời gian dài để nhận biết các trình tự và các mẫu. 1.1.4.5. Xử lý (bộ nhớ) dài hạn Trong tất cả các phƣơng pháp cốt lõi, thƣờng có lý do để ghi lại thông tin và tìm hiểu từ thông tin. Trong một số kỹ thuật, việc này hoàn toàn rõ ràng. 1.1.5. Ứng dụng của KPDL Mặc dù còn rất nhiều vấn đề mà KPDL cần phải tiếp tục nghiên cứu để giải quyết nhƣng tiềm năng của nó đã đƣợc khẳng định bằng sự ra đời của rất 11 nhiều ứng dụng. Các ứng dụng của KPDL trong khoa học cũng đƣợc phát triển. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá dữ liệu với các ứng dụng nhƣ Intelligence Miner, … Ta có thể đƣa ra một số ứng dụng trong các lĩnh vực nhƣ: Ngân hàng: Xây dựng mô hình dự báo rủi ro tín dụng; tìm kiếm tri thức, quy luật của thị trƣờng chứng khoán và đầu tƣ bất động sản,… Thương mại điện tử: Công cụ tìm hiểu, định hƣớng, thúc đẩy, giao tiếp với khách hàng; phân tích khách hàng duyệt web; Phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù hợp với loại khách hàng. Thiên văn học: Hệ thống SKICAT do JPL/Caltech phát triển đƣợc sử dụng cho các nhà thiên văn để tự động xác định các vì sao và các dải thiên hà trong một bản khảo sát lớn để có thể phân tích và phân loại (Fayyad, Djorgovski, & Weir). Sinh học phân tử: Hệ thống tìm kiếm các mẫu trong cấu trúc phân tử (Conklin, Fortier, và Glasgow 1993) và trong các dữ liệu gen (Holder, Cook, và Djoko 1994). Mô hình hóa những thay đổi thời tiết: các mẫu không thời gian nhƣ lốc, gió xoáy đƣợc tự động tìm thấy trong các tập lớn dữ liệu mô phỏng và quan sát đƣợc (Stolorz et al. 1994). Tại thời điểm viết thực hiện luận văn này, tổng số ca nhiễm coronavirus mới đƣợc xác nhận trên toàn cầu (COVID-19) đã vƣợt quá 23,8 triệu (Worldometer, 2020). Vì vi rút vẫn đang tàn phá hầu hết các nơi trên thế giới, thảm họa sức khỏe cộng đồng toàn cầu chƣa từng có này cũng có tác động to lớn đến sức khỏe tâm thần của con ngƣời (Rajkumar, 2020; Tandon, 2020a; Vindegaard và Benros, 2020). Trong khi các nhà nghiên cứu tâm lý học trên 12 toàn cầu đang áp dụng nhiều cách tiếp cận và kỹ thuật nghiên cứu khác nhau để chống lại đại dịch. Các nhà khoa học đã giới thiệu một kỹ thuật mới nổi trong các nghiên cứu và sử dụng các kỹ thuật KPDL để đƣa ra các đánh giá, phán đoán giúp phòng tránh và góp phần ngăn chặn đại dịch COVID-19. 1.1.6. Những thách thức trong nghiên cứu và ứng dụng của KPDL Khối lƣợng dữ liệu lớn và từ nhiều nguồn khác nhau: CSDL, internet, các loại thiết bị thu nhận tính hiệu, các loại thiết bị nhận dạng, các loại thiết bị lƣu trữ nhƣ băng từ, CD, ... Số mẫu tin và số các thuộc tính quá lớn làm cho độ phức tạp và thời gian giải quyết bài toán tăng lên rất nhanh. Mô hình hay tri thức phát hiện đƣợc bị thay đổi theo thời gian tức là mô hình hay tri thức đó phụ thuộc vào thời điểm quan sát, lấy mẫu, thời điểm khai phá, kết quả đạt đƣợc sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu. Dữ liệu bị ảnh hƣởng, bị nhiễu bởi tác động của môi trƣờng bên ngoài, hay bộ dữ liệu không hoàn chỉnh làm cho dữ liệu không phản ánh trung thực, chính xác của các quy luật, tri thức mà ta tìm đƣợc. Các thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị trong các miền thuộc tính sẽ ảnh hƣởng rất lớn đến việc khai phá dữ liệu. Chẳng hạn nhƣ khi khai phá dữ liệu, các hệ thống tƣơng tác với nhau, phụ thuộc nhau, chỉ cần thiếu một vài giá trị nào đó sẽ dẫn đến các mẫu thuẫn, không chính xác, không đầy đủ. Từ những vấn đề đặt ra ở trên nên tốc độ xử lý cần quan tâm trƣớc nhất. Có hai phƣơng hƣớng để giải quyết vấn đề này là nâng cao năng lực của phần cứng và cải tiến phần mềm. Tuy nhiên khi cải thiện năng lực của máy tính thì dữ liệu cung tăng không ngừng, thậm chí còn tăng nhanh hơn gấp nhiều lần. Do vây việc nghiên cứu đề xuất các thuật toán hiệu quả có khả năng làm việc trên khối lƣợng dữ liệu lớn, và có độ phức tạp tính toán thấp là một hƣớng nghiên cứu đầy tiềm năng. Từ nhu cầu thực tế trên, gần đây đã