Luận văn Nâng cao hiệu quả phát hiện mã độc sử dụng các kỹ thuật học máy

LỜI CAM ĐOAN . i

LỜI CẢM ƠN.ii

DANH MỤC HÌNH. v

TÓM TẮT .vi

MỞ ĐẦU . 1

CHƯƠNG 1: TỔNG QUAN VỀ MÃ ĐỘC . 4

1.1. Giới thiệu về mã độc . 4

1.2. Phân loại mã độc . 4

1.2.1. Virus [5]. . 5

1.2.2. Worm [5]. 7

1.2.3. Ransomware. 8

1.2.4. Trojan . 10

1.2.5. Backdoor [6]. 10

1.2.6. Rootkits . 11

1.3. Mục đích phân tích mã độc . 12

1.4. Phương pháp phân tích mã độc. 12

1.5. Trích xuất đặc trưng và các loại đặc trưng. 14

1.5.1. Trích xuất đặc trưng. 14

1.5.2. Các loại đặc trưng . 15

CHƯƠNG 2: TỔNG QUAN VỀ HỌC MÁY . 17

2.1. Giới thiệu về học máy . 17

2.2. Phân loại các thuật toán học máy [2] . 19

2.3. Thuật toán One-class SVM. 20

2.3.1. Giới thiệu thuật toán One-class SVM . 20

2.3.2. Giới thiệu thuật toán SVM. 21

2.3.3. Thuật toán One-class SVM theo tác giả Schölkopf. 25

pdf50 trang | Chia sẻ: honganh20 | Ngày: 16/03/2022 | Lượt xem: 124 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Luận văn Nâng cao hiệu quả phát hiện mã độc sử dụng các kỹ thuật học máy, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
4 đến bây giờ đã phát hiện hàng trăm biến thể của Jisut với các hành vi khác nhau hoặc các tin nhắn đòi tiền chuộc khác nhau nhưng tất cả dựa trên cùng một mẫu mã độc. Khi mã độc Jisut được kích hoạt thì nó sẽ tạo ra một màn hình hoạt động được hiện lên với đầy đủ màn hình với màu đen, nếu người dùng thay đổi giao diện hoặc tắt, khởi động lại thiết bị thì một thông báo sẽ được hiển thị lên hoặc một bài hát sẽ được thực thi.  WannaLocker: mã độc này là một loại khác của ransomware Wannacry, ban đầu nhắm đến người dùng Android ở Trung Quốc và mở rộng ra toàn thế giới. Mã độc này lây nhiễm các tệp tin (files) trên bộ lưu trữ của thiết bị và mã hóa các tệp tin bằng thuật toát mã hóa AES. Khi các tệp tin bị mã hóa, mã độc sẽ hiện lên một thông báo đòi tiền chuộc tương tự như WannaCry, nó cung cấp thông tin về dữ liệu đã được mã hóa và các khả năng đê phục hội chúng bằng ngôn ngữ tiếng trung. WannaLocker yêu cầu số tiền chuộc là 40 Renmibi Trung Quốc và cách liên lạc để thực hiện giao dịch chuyển tiền và khôi phục dữ liệu. 10 1.2.4. Trojan Trojan là một loại phần mềm giả mạo phổ biến, chúng thường ẩn náu trong chương trình phần mềm hữu ích để thực hiện các nhiệm vụ mong muốn và hợp pháp nhưng thực chất là thực hiện một số chức năng độc hại như xóa file, thu thập thông tin hệ thống và gửi cho máy chủ điều khiển, ăn cắp thông tin tài khoản người dùng ....Những chức năng mong muốn và hợp pháp chỉ là phần bề mặt giả tạo nhằm che dấu cho các thao táo độc hại. Không giống như virus, trojan không có chức năng tự sao chép nhưng lại có chức năng phá hoại tương tự virus. Một số dạng Trojans cơ bản như sau:  Remote Access Trojans: cho phép kẻ tấn công kiểm soát toàn bộ hệ thống từ xa  Data-Sending Trojans: Trojan gửi thông tin nhạy cảm của nạn nhân cho kẻ tấn công  Destructive Trojans: Trojan phá hủy hệ thống  Denied-of-Service – DoS Attack Trojan: Trojan phục vụ tấn công Ddos  HTTP, FTP Trojans: Trojan tự tạo thành HTTP hay FTP server để kẻ tấn công khai thác lỗi  Security Software Disable Trojan: Có tác dụng tắt tính năng bảo mật trong các máy tính nạn nhân 1.2.5. Backdoor [6] Backdoor (cửa hậu) là một loại phần mềm độc hại cung cấp cho kẻ tấn công quyền truy cập từ xa vào máy nạn nhân. Backdoor là loại phần mềm độc hại phổ biến nhất và chúng có đủ hình dạng, kích cỡ với khả năng khác nhau. Mã backdoor thường thực hiện đầy đủ các khả năng, vì vậy khi sử dụng backdoor kẻ tấn công thường không cần tải thêm các phần mềm độc hại khác hoặc mã chương trình. Backdoor thường cho phép kẻ tấn công kết nối đến máy tính từ xa với ít quyền hoặc không cần xác thực và đi kèm với một số chức năng phổ biến như khả năng thao tác các khóa registry, liệt kê các cửa sổ hiện thị, tạo thư mục, tìm kiếm tập tin, truy cập từ xa bằng tài khoản riêng, thực thi lệnh hệ thống....Một số loại backdoor như sau: 11  Reverse Shell: là một kết nối bắt nguồn từ một máy bị nhiễm và cung cắp quyền truy cập shell cho kẻ tấn công vào máy tính đó. Khi ở trong reverse shell, kẻ tấn công có thể thực thi các lệnh trên máy của nạn nhân ngay trên máy của kẻ tấn công.  RATs: công cụ quản trị từ xa (RAT) được sử dụng để quản lý các máy tính từ xa. RAT thường được sử dụng trong các cuộc tấn công có chủ đích với mục tiêu cụ thể, chẳng hạn như đánh cắp thông tin.  Botnet: là tập hợp các máy chủ bị xâm nhập, được gọi là zombie, được điểu khiển bởi máy chủ botnet. Mục tiêu của botnet là tạo ra một mạng lưới zombie lớn để botnet phát tán mềm mềm độc hại hoặc thực hiện tấn công từ chối dịch vụ (DDoS). 1.2.6. Rootkits Rootkit là một bộ công cụ phần mềm do kẻ xâm nhập đưa vào máy tính nạn nhân nhằm mục đích cho phép mình quay lại xâm nhập máy tính đó và dùng nó cho các mục đích xấu mà không bị phát hiện. Một số mục đích của kẻ xâm nhập khi sử dụng rootkit bao gồm:  Thu thập dữ liệu về các máy tính trong cùng mạng và thông tin của người dùng như mật khẩu, thông tin tài chính.  Tạo hoặc chuyển tiếp spam.  Gây lỗi hoặc sai trong hoạt động của máy tính. Rootkit được thiết kế tốt có khả năng che giấu hoặc xóa bỏ bất cứ dấu vết nào của việc nó truy cập vào máy tính, sự tồn tại và hoạt động của nó. Ví dụ, nó có thể sữa nhật ký (log) của hệ thống để hệ điều hành không ghi hoặc xóa bỏ tất cả các thông tin liên quan đến việc nó đăng nhập vào máy, thông tin các lần truy cập tiếp theo của kẻ xâm nhập, thông tin về các chương trình mà rootkit chạy. Rootkit không phải là virus do nó không tự nhân bản và không có cơ chế hoạt động tự chủ. Rootkit nằm hoàn toàn dưới quyền kiểm soát của kẻ tấn công. 12 1.3. Mục đích phân tích mã độc Khái niệm: phân tích phần mềm độc hại là quá trình xác định chức năng và mục đích của mẫu phần mềm độc hại đã cho là virus, worm, Trojan Horse .. hay biến thể của mã độc đã biết hoặc mã độc mới. Các mục đích của phân tích mã độc: có ba mục đích chính trong việc phân tích mã độc bao gồm phát hiện mã độc, phân tích sự tương tự giữa các phần mềm độc hại và phân loại các phần mềm độc hại. Chi tiết ba mục đích của phân tích mã độc như sau: [2]  Phát hiện mã độc nhằm mục đích phát hiện một tập tin có phải là mã độc hay không.  Phân tích sự tương tự giữa các phần mềm độc hại nhằm mục đích kiểm tra sự giống nhau, khác nhau giữa các phần mềm độc hại để phát hiện biến thể của mã độc đã biết hoặc lớp mã độc mới.  Phân loại phần mềm độc hại: cho phép phân loại phần mềm độc hại vào các nhóm phần mềm đọc hại khác nhau như nhóm virus, horm, rootkit... 1.4. Phương pháp phân tích mã độc Hiện tại có một số kỹ thuật được dùng để phân tích mã độc, gồm có phân tích tĩnh, phân tích động và phân tích lai, chi tiết các các kỹ thuật như sau: Phân tích tĩnh là phương pháp phân tích phần mềm mà không cần thực thi chúng. Các thông tin thu được có thể bao gồm các metadata của chương trình, định dạng, dung lượngcác chuỗi ký tự xuất hiên trong mã nguồn, các thư viện được thêm vào (import), các lời gọi hàm có thể được sử dụng, mã nguồn chương trình dưới dạng AssemblyƯu điểm của phương pháp này là có thể biết được tất cả các khả năng thực hiện có thể của chương trình, tuy nhiên đối với mã độc thì việc phân tích tĩnh thường gặp khó khăn do việc mã hóa (Encrypt), đóng gói (Packed), ngụy trang (Obfuscated). Một số kỹ thuật được sử dụng cho phân tích tĩnh bao gồm [8]:  Kỹ thuật phát hiện dựa trên chữ ký (signature based detection technique) còn gọi là khớp mẫu hoặc chuỗi hoặc mặt nạ hoặc kỹ thuật 13 dấu vân tay. Chữ ký là một chuỗi các bit được người viết phần mềm độc hại chèn vào chương trình ứng dụng được viết bởi những người phát triển mã độc và cho phép nhận ra một loại mã độc cụ thể. Để phát hiện phần mềm độc hại trong mã của chương trình, người rà soát mã độc hại sẽ tìm kiếm một số chữ ký đã được định nghĩa trước đó trong mã chương trình. Ví dụ, các từ khóa được tìm kiếm như địa chỉ IP, lời gọi chương trình.  Kỹ thuật phát hiện heuristic (heuristic detection technique) được biết như là kỹ thuật chủ động. Có nhiều sự tương đồng giữa kỹ thuật phân tích chữ ký số và kỹ thuật heuristic tuy nhiên có một sự khác nhau rõ ràng của kỹ thuật phân tích heuristic là việc thay cho tìm kiềm một chữ ký cụ thể trong đoạn mã chương trình thì người kiểm tra mã độc sẽ tìm những lệnh và chỉ thị mà không có trong chương trình. Thuận lợi chính của kỹ thuật này là có thể dễ dàng phát hiện ra các biến thể mới của mã độc mà chưa được phát hiện trước đây. Phân tích động là phương pháp theo dõi, phân tích hành vi thực hiện, các tương tác của phần mềm với môi trường thông qua việc thực thi các phần mềm đó. Khi phân tích động mã độc cũng đồng nghĩa với việc ta phải chạy mã độc đó, do vậy chúng ta cần có một môi trường an toàn để tránh các tác hại đối với hệ thống cũng như bên ngoài. Hộp cát (Sandbox) là một cơ chế bảo mật để chạy các chương trình không đáng tin cậy trong một môi trường an toàn mà không sợ làm hệ thống "thực". Ưu điểm của phương pháp phân tích này đó là có thể theo dõi các hành động thực sự được thực hiện bởi mã độc trong khi đối với phân tích tĩnh, khi gặp rẽ nhánh chúng ta không thể biết mã độc sẽ đi theo nhánh nào. Thách thức của phương pháp này là môi trường sandbox phải an toàn, tránh bị phát hiện đồng thời phải đáp ứng được các điều kiện để mã độc bộc lộ tối đa hành vi của mình. Có hai cách tiếp cận chính cho phương pháp phân tích động gồm có: 14  Phân tích sự khác biệt giữa các thời điểm được xác định: với phương pháp này, mẫu phần mềm độc hại đã được phân tích trong một khoảng thời gian nhất định, sau đó thay đổi cấu hình hệ thống và phân mềm độc hại sẽ được phân tích lại như ban đầu [7]  Quan sát hành vi thời gian chạy: theo cách tiếp cận này, phần mềm độc hại sẽ thực hiên các hành động độc hại được giám sát các hành vi bằng công cụ chuyên dụng [7]  Phân tích lai (hybrid): kỹ thuật phân tích này là sự kết hợp giữa phân tích tĩnh và phân tích động, thường tuân theo một quy trình đơn giản ban đầu kiểm tra bất kỳ chữ ký trong mã chương trình, nếu phát hiện bất kỳ chữ ký nào xuất hiện thì sẽ giám sát hành vi của mã này [8] 1.5. Trích xuất đặc trưng và các loại đặc trưng 1.5.1. Trích xuất đặc trưng Quá trình trích xuất đặc trưng được thực hiện bằng việc phân tích tĩnh hoặc phân tích động hoặc cả hai loại phân tích tĩnh và phân tích động. Cách tiếp cận dựa trên phân tích tĩnh được thực hiện bằng cách xem xét nội dung của các mẫu mã độc mà không cần chúng thực thi (không cần chạy chương trình), trong khi cách tiếp cận dựa trên phân tích động được thực hiện dựa trên các mẫu mã được được thực thi để kiểm tra các hành vi của nó. Mốt số kỹ thuật có thể được sử dụng cho phân tích động như: trình sữa lỗi (debugger) được sử dụng cho việc phân tích các lớp chỉ thị (instruction), các bộ mô phỏng (simulators) biểu diễn và hiện thị các hành vi tương tự như trong môi trường thật của mã độc, trong khi các bộ giả lập (emulators) nhân bản hành vi của một hệ thống với độ chính xác cao hơn nhưng yêu cầu nhiều tài nguyên hơn. Sandboxes là các hệ điều hành được ảo hóa cung cấp một môi trường đánh tin cậy và cô lập để kích hoạt các mã độc. Các dấu vết thực thi (excution traces) thường được sử dụng để trích xuất các đặc trưng khi sử dụng phân tích động. Ngoài ra, một số công cụ và kỹ thuật khác thường được sử dụng để trích xuất đặc như: các mã disassembly và biều đồ luồng dữ liệu (data-flow) 15 và điều khiển (control). Mã dịch ngược assembly là thành phần quan trọng cho việc trích xuất các byte tuần tự (Byte sequence và Opcode), trong khi biểu đồ luồng dữ liệu và điều khiển được sử dụng để trích xuất các lời gọi hệ thống (system calls) và API. 1.5.2. Các loại đặc trưng Có 8 loại đặc trưng điển hình bao gồm [2]:  Chuỗi byte (bytes sequence): phân tích các chuỗi byte cụ thể trong tệp tin nhị phân được sử dụng phổ biến trong phân tích tĩnh. Một số công trình sử dụng chuỗi các byte với kích thước cụ thể và đa số công trình khác sử dụng n-grams (n-grams là một chuỗi các byte).  Opcodes: opcodes xác định các hoạt động (operation) ở mức máy được thực thi bởi một file thực thi và có thể được trích xuất thông qua phân tích tĩnh bằng cách kiểm tra các mã assembly. Chuỗi tuần tự opcode là một trong những đặc trưng phổ biến được sử dụng, nó đếm số lần xuất hiện của opcode cụ thể trong assemby.  API và các lời gọi hệ thống (System calls): tương tự opcodes, API và các lời gọi hệ thống cho phép phân tích hành vi của mã độc nhưng ở mức cao. Chúng có thể được trích xuất bằng phân tích tĩnh hoặc phân tích động bằng cách phân tích mã assembly được dịch ngược hoặc một danh sách các lời gọi hệ thống. Một trong những cấu trúc dữ liệu phổ biến để biểu diễn hành vi PE và trích xuất cấu trúc chương trình là đồ thị luồng điều khiển (control flow graph).  Hoạt động mạng (Network activity): một số lượng lớn các thông tin chính có thể thu được bằng cách quan sát việc tương tác mã thực thi với mạng. Địa chỉ kết nối và lưu lượng được tạo ra có thể rất có giá trị như kết nối với một lệnh và trung tâm điều khiển. Một số đặc trưng được sử dụng như giao thức, cổng TCP/UDP, các yêu cầu HTTP, kết nối DNS....  File system: các hành động của file được thực thi bởi các mã độc là thành phần cơ bản khi thu thập chứng cứ về sự tương tác của mã độc với 16 môi trường, ví dụ loại file gì được thêm, sữa, xóa, thay đổi; file gì bị nhiễm mã độc và file chưa bị nhiễm mã độc.  Các thanh ghi CPU (CPU Registers): cách các thanh ghi trong CPU được sử dụng có thể có giá trị như thanh ghi ẩn nào được sử dụng và các giá trị gì được lưu trong các thanh ghi, đặc biệt là các cờ (Flasgs).  Các đặc điểm file PE (PE file characteristics): phân tích tĩnh một PE có thể mang lại tập hợp các thông tin có giá trị như các phần (sections), các nhập (imports), các ký hiệu (symbols),  Chuỗi ký tự (Strings): một PE có thể được kiểm tra bằng cách tìm kiếm các ký tự cụ thể như dấu hiệu tác giả, tên file, thông tin hệ thống. 17 CHƯƠNG 2: TỔNG QUAN VỀ HỌC MÁY 2.1. Giới thiệu về học máy Thời gian gần đây, trí tuệ nhân tạo (AI – Artificial Intelligence) và cụ thể hơn là học máy (Machine Learning) đang nổi lên như một bằng chứng của cách mạng công nghiệp lần thứ tư (lần 1 – động cơ hơi nước, lần 2 – năng lượng điện, lần 3 – công nghệ thông tin). Trí tuệ nhân tạo đang len lỏi vào mọi lĩnh vực trong đời sống của chúng ta như xẹ tự lái của Google và Tesla, hệ thống gợi ý sản phẩm của Amazon, hệ thống trợ lý ảo Siri của Apple, hệ thống gợi ý phim của Netfix....chỉ là một trong những ứng dụng AI/Machine Learning. Học máy là một tập con của trí tuệ nhân tạo. Theo định nghĩa của Wikipedia thì, học máy là một lĩnh vực nhỏ của khoa học máy tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải lập trình cụ thể. Ý tưởng cơ bản của mọi quy trình học máy là xây dựng mô hình dựa trên một số thuật toán để thực hiện một nhiệm vụ cụ thể như phân loại, phân lớp, hồi quy... Giai đoạn huấn luyện được thực hiện dựa trên dữ liệu đầu vào và mô hình được xây dựng để dự đoán đầu ra. Kết quả đầu ra phụ thuộc mục tiêu ban đầu và việc thực hiện. Chi tiết quy trình học máy gồm các bước như sau [13]: Hình 2.1: quy trình học máy 18 Quy trình học máy cơ bản được chia làm các giai đoạn sau:  Thu thập dữ liệu (gathering data): Quá trình thu thập dữ liệu phụ thuộc vào loại dự án mà chúng ta mong muốn xây dựng, ví dụ nếu chúng ta muốn xây dựng dự án học máy mà sử dụng dữ liệu thực để chúng ta có thể xây dựng một hệ thống IoT từ các dữ liệu cảm biến khác nhau. Dữ liệu chúng ta có thể thu thập từ các nguồn dữ liệu khác nhau như một tập tin, cơ sở dữ liệu, cảm biến ...  Tiền xử lý dữ liệu (data pre-processing): Tiền xử lý dữ liệu là một trong những giai đoạn quan trọng trong học máy, nó giúp xây dựng mô hình học máy chính xác. Tiền xử lý dữ liệu là một quá trình làm sạch dữ liệu thô, dữ liệu được thu thập từ nhiều nguồn trong thế giới thực và được chuyển thành một tập dữ liệu sạch. Dữ liệu thô ban đầu có một số đặc điểm như dữ liệu bị thiếu sót, không nhất quán, nhiễu vì vậy dữ liệu này phải được xử lý trước khi đưa vào học máy.  Xây dựng mô hình phù hợp cho loại dữ liệu (researching model): Mục tiêu chính của chúng ta là xây dựng mô hình thực hiện tốt nhất dựa trên một số thuật toán phân loại và phân lớp.  Huấn luyện và kiểm thử mô hình trên dữ liệu (training and testing model): để huấn luyện một mô hình, ban đầu chúng ta chia mô hình thành 03 giai đoạn bao gồm: dữ liệu huấn luyện (training data), dữ liệu xác nhận (validation data) và dữ liệu kiểm thử (testing data). Để huấn luyện bộ phân lớp ta sử dụng tập hợp dữ liệu huấn luyện (training data set), để tinh chỉnh các tham số ta sử dụng tập hợp xác nhận (validation set) và sau đó kiểm tra hiệu suất của bộ phân loại chưa biết sử dụng tập hợp dữ liệu kiểm thử (test data set). Một lưu ý quan trọng là trong quá trình huấn luyện bộ phân lớp là dữ liệu kiểm thử không được sử dụng để huấn luyện.  Đánh giá (evaluation): Đánh giá mô hình là một phần quan trọng trong quy trình phát triển mô hình, nó giúp tìm ra mô hình tốt nhất để đại diện 19 cho dữ liệu của chúng ta và mô hình được chọn sẽ hoạt động tốt như thế nào trong tương lai. 2.2. Phân loại các thuật toán học máy [2] Có hai cách phổ biến để phân loại các thuật toán học máy. Một là dựa vào phương thức học (learning style) và hai là dựa trên chức năng (function) của thuật toán. Theo phương phức học thì các thuật toán học máy được chia làm 04 loại gồm: học có giám sát (Supervise learning), học không giám sát (Unsupervised learning), học bán giám sát (Semi-supervised learning) và học tăng cường (Reinforcement Learning). Chi tiết các loại học máy theo phương thức học như sau:  Học có giám sát: Là thuật toán dự đoán đầu ra (outcome) của một dữ liệu mới (new input) dựa trên các cặp (input, output) đã biết từ trước. Các cặp dữ liệu này còn được gọi là “dữ liệu, nhãn”, tức (data, label). Học có giám sát là loại phổ biến nhất trong các thuật toán học máy. Bài toán học có giám sát còn được chia nhỏ thành hai loại chính như sau:  Phân loại (Classification): Một bài toán được gọi là phân loại nếu các nhãn của dữ liệu đầu vào (input data) được chia thành một số hữu hạn nhóm: Ví dụ bài toán xác định xem một email có phải spam hay không?  Hồi quy (Regression): Nếu nhãn (label) không được chia thành các loại mà là một giá trị thực cụ thể. Ví dụ, một căn nhà rộng x 𝒎𝟐`, có y phòng ngủ và cách trung tâm thành phố z km sẽ có giá là bao nhiêu?  Học không giám sát: trong bài toán này, chúng ta không biết được nhãn hay outcome mà chỉ có dữ liệu đầu vào. Thuật toán học không giám sát sẽ dựa vào cấu trúc của dữ liệu để thực hiện một công việc nào đó, ví dụ như phân nhóm (clustering) hoặc giảm số chiều của dữ liệu (dimension reduction) để thuận tiện trong việc lưu trữ và tính toán. Bài toán học không giám sát được tiếp tục chia nhỏ thành hai loại sau: 20  Phân nhóm (clustering): Một bài toán phân nhóm toàn bộ dữ liệu Y thành các nhóm nhỏ dựa trên sự liên quan giữa các dữ liệu trong mỗi nhóm. Ví dụ, phân nhóm khách hàng dựa vào hành vi mua hàng  Kết hợp (association): là bài toán khi chúng ta muốn khám phá ra một quy luật dựa trên nhiều dữ liệu cho trước. Ví dụ, những khách hàng nữ mua quần áo thường có xu hướng mua thêm son môi; những khách hàng mua bóng đá thường mua thêm bảo hộ ống quyển và tất.  Học bán giám sát (Semi-supervised learning): Các bài toán khi chúng ta có một lượng lớn dữ liệu Z nhưng chỉ một trong chúng được gán nhãn. Những bài toán thuộc nhóm này nằm giữa hai nhóm được nêu trên. Ví dụ, chỉ một phần các bức ảnh (ảnh về người, động vật, thực vật) được gán nhán và phần lớn các bức ảnh khác chưa được gán nhãn trên internet. Phân loại dựa trên chức năng: Cách phân loại thứ hai dựa trên chức năng của các thuật toán. Ví dụ các thuật toán hồi quy (Linear regression, Logistic Regression, Stepwise Regresstion), các thuật toán phân loại (SVM, kernel SVM, Linear Classifier), các thuật toán phân cụm (k-Means clustering, k-Medians, EM)... 2.3. Thuật toán One-class SVM. 2.3.1. Giới thiệu thuật toán One-class SVM Theo truyền thống nhiều vấn đề phân loại cố gắng giải quyết tình huống hai hoặc phân loại nhiều lớp và mục tiêu của ứng dụng học máy là phân biệt dữ liệu kiểm thử giữa một số lớp sử dụng dữ liệu huấn luyện. Nhưng điều gì sẽ xảy ra nếu bạn chỉ có dữ liệu của một lớp và mục tiêu là kiểm tra dữ liệu mới và tìm hiểu xem nó có giống hay không giống với dữ liệu huấn luyện. Một phương pháp cho nhiệm vụ này đã trở nên phổ biến là máy véc tơ hỗ trợ một lớp (One-class Support Vector Machine). Ví dụ hãy tưởng tượng một loại thiết lập của nhà máy với các máy sản xuất rất lớn dưới sự giám sát của một số hệ thống tiên tiến và nhiệm vụ của hệ thống giám sát 21 là xác định khi có sự cố xảy ra, chất lượng của các sản phẩm có dưới chuẩn chất lượng không, các máy có tạo ra rung động gì lạ không hoặc một cái gì đó làm nhiệt độ tăng lên không? Việc thu thập dữ liệu huấn luyện về các tình huống tương đối dễ dàng do nó chỉ là trạng thái hoạt động bình thường nhưng mật khác dữ liệu huấn luyện thu thập từ các trạng thái bị lỗi là khá tốn kém và đôi khi là không thể thực hiện được. Để đối phó với vấn dề này, các giải pháp phân loại một lớp (one-class) được giới thiệu bằng cách chỉ cung cấp dữ liệu huấn luyện bình thường và thuật toán tạo ra một mô hình cho dữ liệu này. Nếu dữ liệu được thu được quá khác nhau cùng với một số phép đo thì nó được gán nhãn ngoài lớp từ mô hình này. Trong phạm vi của nghiên cứu này chúng tôi sẽ trình bày 02 cách tiếp cận về thuật toán One-class SVM, một cách tiếp cận theo tác giả Schölkopf và một cách tiếp cận theo các tác giả Tax và Duin. Trước khi đi vào chi tiết thuật toán One-Class SVM, chúng ta tìm hiểu thuật toán máy véc tơ hỗ trợ (SVM – Support Vector Machine). 2.3.2. Giới thiệu thuật toán SVM. SVM (support vector machine) là một khái niệm trong thống kê và khoa học máy tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau để phân loại và phân tích hồi quy. SVM dạng chuẩn nhận dữ liệu đầu vào và phân loại chúng vào hai lớp khác nhau. Do đó SVM là một thuật toán phân loại nhị phân. Với một bộ các ví dụ huấn luyện thuộc hai thể loại cho trước, thuật toán huấn luyện SVM xây dựng một mô hình SVM để phân loại các ví dụ khác vào hai thể loại đó. Một mô hình SVM là một cách biểu diễn các điểm trong không gian và lựa chọn ranh giới giữa hai thể loại sao cho khoảng cách từ các ví dụ huấn luyện tới ranh giới là xa nhất có thể. Các ví dụ mới cũng được biểu diễn trong cùng một không gian và được thuật toán dự đoán thuộc một trong hai thể loại tùy vào ví dụ đó nằm ở phía nào của ranh giới. 22 SVM xây dựng một siêu phẳng hoặc một tập hợp các siêu phẳng trong một không gian nhiều chiều hoặc vô hạn chiều, có thể được sử dụng cho phân loại, hồi quy, hoặc các nhiệm vụ khác. Một cách trực giác, để phân loại tốt nhất thì các siêu phẳng nằm ở càng xa các điểm dữ liệu của tất cả các lớp (gọi là hàm lề) càng tốt, vì nói chung lề càng lớn thì sai số tổng quát hóa của thuật toán phân loại càng bé. Trong nhiều trường hợp, không thể phân chia các lớp dữ liệu một cách tuyến tính trong một không gian ban đầu được dùng để mô tả một vấn đề. Vì vậy, nhiều khi cần phải ánh xạ các điểm dữ liệu trong không gian ban đầu vào một không gian mới nhiều chiều hơn, để việc phân tách chúng trở nên dễ dàng hơn trong không gian mới. Để việc tính toán được hiệu quả, ánh xạ sử dụng trong thuật toán SVM chỉ đòi hỏi tích vô hướng của các vector dữ liệu trong không gian mới có thể được tính dễ dàng từ các tọa độ trong không gian cũ. Tích vô hướng này được xác định bằng một hàm hạt nhân K(x,y) phù hợp. [1] Một siêu phẳng trong không gian mới được định nghĩa là tập hợp các điểm có tích vô hướng với một vectơ cố định trong không gian đó là một hằng số. Vector xác định một siêu phẳng sử dụng trong SVM là một tổ hợp tuyến tính của các vector dữ liệu luyện tập trong không gian mới với các hệ số αi. Với siêu phẳng lựa chọn như trên, các điểm x trong không gian đặc trưng được ánh xạ vào một siêu mặt phẳng là các điểm thỏa mãn: Σi αi K(xi,x) = hằng số. Ghi chú rằng nếu K(x,y) nhận giá trị ngày càng nhỏ khi y xa dần khỏi x thì mỗi số hạng của tổng trên được dùng để đo độ tương tự giữa x với điểm xi tương ứng trong dữ liệu luyện tập. Như vậy, tác dụng của tổng trên chính là so sánh khoảng cách giữa điểm cần dự đoán với các điểm dữ liệu đã biết. Lưu ý là tập hợp các điểm x được ánh xạ vào một siêu phẳng có thể có độ phức tạp tùy ý trong không gian ban đầu, nên có thể phân tách các tập hợp thậm chí không lồi trong không gian ban đầu. Phân loại thống kê là một nhiệm vụ phổ biến trong học máy. Trong mô hình học có giám sát, thuật toán được cho trước một số điểm dữ liệu cùng với nhãn của chúng thuộc một trong hai lớp cho trước. Mục tiêu của thuật toán là 23 xác định xem một điểm dữ liệu mới sẽ được thuộc về lớp nào. Mỗi điểm dữ liệu được biểu diễn dưới dạng một vector p chiều và ta muốn biết liệu có thể chia tách hai lớp dữ liệu bằng một siêu phẳng p − 1 chiều, đây gọi là phân loại tuyến tính. Có nhiều siêu phẳng có thể phân loại được dữ liệu. Một lựa chọn hợp lý trong chúng là siêu phẳng có lề lớn nhất giữa hai lớp. 2.3.2.1. Xây dựng bài toán SVM Giả sử rằng các cặp dữ liệu của training set là (𝒙𝟏, 𝒚𝟏), (𝒙𝟐, 𝒚𝟐),.., (𝒙𝟑, 𝒚𝟑) với vector 𝒙𝒊 𝞊 𝑹𝒅 thể hiện đầu vào của một điểm dữ liệu và 𝒚𝒊là nhãn của điểm dữ liệu đó, d là số chiều của dữ liệu và N là số điểm dữ liệu. Giả sử rằng nhãn của mỗi điểm dữ liệu được xác định bởi 𝒚𝒊 = 1 (lớp 1) hoặc

Các file đính kèm theo tài liệu này:

  • pdfluan_van_nang_cao_hieu_qua_phat_hien_ma_doc_su_dung_cac_ky_t.pdf
Tài liệu liên quan