Phát hiện ngoại lệ với Anomaly Detection

ANOMALY DETECTION

Motivation

Quy trình kiểm tra chất lượng của một nhà máy sản xuất động cơ xe máy đo đạc các số liệu về độ rung của động cơ, nhiệt lượng tỏa ra, công sinh ra … Làm thế nào ta có thể dựa vào các số liệu này để đưa ra các cảnh báo về động cơ nào có vấn đề cần phải kiểm tra lại chất lượng, động cơ nào đảm bảo có thể xuất ra thị trường? Thuật toán Anomaly Detection có thể được ứng dụng trong hoàn cảnh này để phát hiện ra các instance bất thường, ngoại lệ.
image

Tổng quan về thuật toán

Với tập dữ liệu train ban đầu {x(1), x(2), x(3),…, x(m)}bao gồm m ví dụ bình thường (normal instances).Chúng ta đi xây dựng một hàm đánh giá P(x) và xác định một giá trị ngưỡng e:

Nếu P(x) < e : x được coi như instance bất thường

Nếu P(x) ≥ e : x được coi như normal instance

Phân phối chuẩn Gaussian

Để hiểu rõ hơn về các bước của thuật toán, chúng ta đi tìm hiểu về phân phối chuẩn Gaussian trước nhé.

Phân phối chuẩn hay phân phối Gaussian là một phân phối đóng vai trò cực kỳ quan trọng trong lý thuyết xác suất. Với phân phối có giá trị trung bình μ và độ lệch chuẩn σ. Hàm mật độ xác suất có công thức:
image
Đồ thị biểu diễn hàm mật độ xác suất có dạng hình chuông, đạt cực đại tại giá trị trung bình μ.
image
Giả sử một biến ngẫu nhiên X có phân phối chuẩn. Với một chuỗi giá trị quan sát được {x(1), x(2), x(3),…, x(m)}, ta có thể ước lượng các tham số μ, σ bằng công thức sau:
image
image
Ví dụ xét biến ngẫu nhiên X: cân nặng trong một quần thể gà có phân phối chuẩn
Chọn ngẫu nhiên 5 cá thể ta được các cân nặng lần lượt là 1.2, 2.6, 2.3, 1.9, 3.1
Ta tính được các giá trị:
image

Chi tiết thuật toán

Nhắc lại, ta có tập m ví dụ bình thường{x(1), x(2), x(3),…, x(m)}. Mỗi ví dụ x(i) được biểu diễn bởi tập các thuộc tính (x(i)1,x(i)2,x(i)3,…,x(i)n).

Ta dựa trên giả định mỗi thuộc tính biểu diễn ví dụ có phân phối chuẩn, khi đó ta đi xác định các tham số giá trị trung bình và độ lệch chuẩn cho từng thuộc tính j theo công thức:
image
Khi đó với một ví dụ mới x cần kiểm tra, ta tính được giá trị P(x) theo công thức sau:
image
Và như đã nói ở trên, nếu P(x) < e (e là giá trị ngưỡng) thì x được coi như instance bất thường, ngược lại x là ví dụ bình thường

Một số ứng dụng của thuật toán anomaly detection

  • Phát hiện giao dịch gian lận:
    Có thể gọi x(i) là tập các feature biểu diễn các activites của người dùng (số lầm click chuột, số lần gửi request tới server, thời gian giữa các request…) Từ đó hệ thống có thể phát hiện người dùng có các hành động bất thường và đưa ra cảnh báo với người quản trị hệ thống

  • Kiểm tra chất lượng trong dây chuyền sản xuất

  • Giám sát các máy tính trong trung tâm dữ liệu
    Các thuộc tính như bộ nhớ sử dụng, số lần truy cập nhớ, CPU load, network traffic có thể được sử dụng trong hoàn cảnh này.

Việc lựa chọn thuộc tính biểu diễn ví dụ phụ thuộc vào kinh nghiệm của các chuyên gia tư vấn trên cơ sở hiểu biết về những đặc điểm nào có khả năng cho ta nhận ra các ví dụ bất thường. Đôi khi ta sẽ cần phải xây dựng thêm các thuộc tính dẫn xuất như nhân, chia 2 thuộc tính để tạo ra thuộc tính mới có khả năng phân loại tốt hơn.

Lựa chọn thuộc tính biểu diễn

Một chú ý khi lựa chọn thuộc tính biểu diễn là cần phải quan sát phân phối của giá trị thuộc tính có dạng giống phân phối chuẩn (dạng hình chuông). Lý do như đã nói ở trên, thuật toán Anomaly Detection dựa trên giả định là các thuộc tính có phân phối chuẩn, khi đó thì công thức tính hàm mật độ xác suất f(x, μ, σ) ở trên mới đúng.
image
Trong trường hợp giá trị thuộc tính không có dạng phân phối đúng chuẩn, chúng ta có thể áp dụng các biến đổi, chẳng hạn như dùng hàm log để đưa về dạng phân phối hình chuông. Dưới đây là minh họa gợi ý giúp bạn một số cách biến đổi chuỗi ban đầu về dạng phân phối chuẩn.

Khi nào dùng Anomaly Detection

Nếu ai có hiểu biết một chút về các thuật toán machine learning thì sẽ biết một thuật toán cũng cho phép phát hiện ví dụ bất thường đó chính là Logistic Regression. Thuật toán này cho phép gán nhãn một ví dụ, nhãn 0 tương ứng với ví dụ bình thường, nhãn 1 tương ứng với ví dụ bất thường với ý tưởng dùng phương pháp Gradient Descent để tối thiểu hàm Cost Function gần giống như Linear Regression mà đã có nhiều bài viết nói về nó trên stories. Vậy với cùng khả năng cho phép nhận biết 2 nhãn lớp, khi nào ta sẽ dùng Anomaly Detection, khi nào ta sẽ dùng Logistic Regression?

Dựa vào tập dữ liệu train mà bạn đang có, bạn có thể quyết định chọn thuật toán nào hợp lý:

  • Nếu tập dữ liệu của bạn là lệch, số lượng ví dụ bất thường là nhỏ hoặc không có, mà phần đông là ví dụ bình thường, thì hãy lựa chọn Anomaly Detection vì nội dung thuật toán dựa trên việc train trong một tập đông các ví dụ thường để phát hiện ra quy luật phân bố của chúng.

  • Nếu tập dữ liệu của bạn có số lượng ví dụ normal và anomaly instance đều lớn, lúc này lựa chọn Logistic Regression là hợp lý vì thuật toán này cần một lượng lớn ví dụ của cả 2 nhãn thì việc phát hiện decision boundary càng chính xác.

Ngoài ra, nếu bạn gặp phải trường hợp mà có rất nhiều “types” of anomalies, và nó là rất khó để cho thuật toán có thể học từ các ví dụ train để rút ra vậy thì những ví dụ ngoại lệ “trông” sẽ như thế nào, hơn nữa rất có thể các ví dụ ngoại lệ khác trong tương lai không hề giống (rất khác) với các anomalous instances hiện có trong tập train. Lúc này Anomaly Dectection phát huy hiệu quả hơn Logistic Regression. Ngược lại, nếu các ví dụ tương lai dường như sẽ tương tự như các ví dụ ta đã có trong tập train, vậy thì có thể lựa chọn Logistic Regression.

Trên đây là những kiến thức cơ bản về thuật toán cho phép phát hiện ngoại lệ bất thường, thuật toán Anomaly Detection. Như có thể thấy, đây là một thuật toán không khó và dựa trên kiến thức về xác suất thống kê, rất rõ ràng và dễ hiểu. Mong rằng nó có thể giúp bạn trong một vài tình huống mà bạn gặp phải trong công việc của mình
Để học thêm nhiều thuật toán machine learning nền tảng, bạn có thể tham khảo khóa học Machine Learning của Andrew trên Coursera, review tại đây