Phát hiện các điểm bất thường dựa trên phân cụm K-Means

Bài viết Phát hiện các điểm bất thường dựa trên phân cụm K-Means áp dụng phương pháp phân cụm K-means và khoảng cách Euclid để phát hiện những điểm thi bất thường trong kì thi PTTH 2018 tại Hà Giang. Thực nghiệm cho thấy phương pháp này có thể hỗ trợ khoanh vùng ra các điểm thi bất thường với một tỉ lệ chọn trước.
Nội dung trích xuất từ tài liệu:
Phát hiện các điểm bất thường dựa trên phân cụm K-Means Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 PHÁT HIỆN CÁC ĐIỂM BẤT THƯỜNG DỰA TRÊN PHÂN CỤM K-MEANS Đinh Phú Hùng Trường Đại học Thủy lợi, email: hungdp@tlu.edu.vn1. GIỚI THIỆU CHUNG Bước 2: Tính khoảng cách Euclid giữa các điểm dữ liệu đến K tâm. Điểm bất thường trong dữ liệu là các điểm Bước 3: Nhóm các đối tượng vào nhómmà có giá trị khác đáng kể so với các điểm còn gần nhất dựa vào khoảng cách tính ở bước 2.lại. Việc phát hiện các điểm bất thường này Bước 4: Xác định lại tâm mới cho cácđóng vai trò quan trọng trong rất nhiều lĩnh nhóm.vực. Ví dụ, trong lĩnh vực ngân hàng, phát hiện Bước 5: Thực hiện lại bước 2 cho đếncác giao dịch bất thường, trong lĩnh vực giáo khi không có sự thay đổi nhóm nào của cácdục, phát hiện các điểm thi gian lận… đối tượng. Có rất nhiều các phương pháp tiếp cận đểgiải quyết vấn đề này. Ví dụ như các phương 3. GIẢI THUẬT XÁC ĐỊNH ĐIỂM BẤTpháp dựa trên mật độ (DBSCAN, LOF,…) THƯỜNG DỰA TRÊN PHÂN CỤM[1], các phương pháp dựa trên khoảng cách(K-NN, K-Means,…) [1], các phương pháp Đầu vào: Tập dữ liệu D, số cụm K.dựa trên mô hình tham số (GMM, One Class Đầu ra: Tập các điểm bất thường (n điểmSVM,…) [1]. Ngoài ra, cũng có một số hoặc m% cho trước).phương pháp khác như kiểm định thống kê Bước 1: Áp dụng giải thuật K-means để(Z-score) [1]. phân dữ liệu D đã cho vào K cụm tương ứng. Bài báo này sẽ áp dụng phương pháp phân Bước 2: Tính khoảng cách Euclid từ tất cảcụm K-means và khoảng cách Euclid để phát các điểm dữ liệu trong mỗi cụm đến tâm củahiện những điểm thi bất thường trong kì thi mỗi cụm tương ứng. Sau đó sắp xếp cácPTTH 2018 tại Hà Giang. Thực nghiệm cho khoảng cách đó theo thứ tự giảm dần.thấy phương pháp này có thể hỗ trợ khoanh Bước 3: Chọn ra n (hoặc m %) các điểmvùng ra các điểm thi bất thường với một tỉ lệ dữ liệu có khoảng cách lớn nhất làm nhữngchọn trước. điểm tình nghi.2. KIẾN THỨC NỀN TẢNG 4. KẾT QUẢ THỰC NGHIỆM 2.1. Giải thuật phân cụm K-Means Dữ liệu thực nghiệm là điểm thi PTTH Giải thuật này được đề xuất bởi năm 2018 tại Hà Giang1. Tuy nhiên, chỉ sửMacQueen[2], là một trong những phương dụng điểm thi của 4 môn bao gồm: Toán, Lý,pháp phân cụm cơ bản. Giải thuật này được Hóa và Sinh. Việc lựa chọn 4 môn thi trên làmô tả như sau: do các môn này đều thuộc ngành khoa học tự Đầu vào: nhiên, và quan trọng hơn những môn này - Tập các điểm dữ liệu, Số cụm K thuộc tổ hợp xét tuyển Đại học (Toán-Lý- Đầu ra: Hóa, hoặc Toán-Hóa-Sinh). Tập dữ liệu D - Các điểm được phân về các cụm gồm có: 630 thi sinh thi đủ cả 4 môn trên. Sở Bước 1: Khởi tạo ngẫu nhiên K tâm choK cụm. 1 https://github.com/maiing/DataTalk-Materials/tree/master/diem_thi_THPT_2018 133Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8dĩ chọn điểm thi tại Hà Giang làm thực Từ Bảng 1, ta có nhận xét sau về các cụm:nghiệm là vì việc thống kê điểm thi cho thấy Cụm thứ nhất: Các điểm Toán, Lý, vàsự bất thường (số lượng điểm thi từ 8 đến 10 Hóa rất cao, trong khi điểm Sinh rất thấp.tăng đột biến) theo Hình 1 (bao gồm: 1 biểu Những thí sinh thuộc cụm này có thể thi khốiđồ Histogram, 1 đồ thị mật độ theo điểm thi A (Toán, Lý, Hóa) và môn Sinh có thể chỉ làthực tế (đường màu xanh), và 1 biểu đồ phân môn xét tốt nghiệp nên việc thí sinh có thểphối chuẩn (đường màu đen). không đầu tư học môn này dẫn đến điểm thi thấp. Sự lệch đáng kể về điểm này không gây ra nhiều sự đáng ngờ nên cụm này có thể xét nếu cần. Cụm thứ hai: Tất cả điểm các môn đều ...