zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kỹ Thuật - Công Nghệ

» Kiến trúc - Xây dựng

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Báo xấu

14
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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.vn 1. 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óm mà 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 đến cá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ác dụ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ẤT phá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ểm SVM,…) [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ủa hiệ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ác PTTH 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ểm vù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ững chọ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 cho K cụm. 1 https://github.com/maiing/DataTalk-Materials/tree/master/diem_thi_THPT_2018 133
Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 dĩ 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 dưới trung bình, cụm này đại điện cho các thí sinh học lực trung bình yếu, nên có thể không đáng nghi ngờ. Vì vậy, có thể bỏ qua khi xét. Cụm thứ ba: Có điểm Toán và Lý rất cao, nhưng điểm Hóa và Sinh rất thấp, cụm này Hình 1. Đồ thị thống kê điểm của 4 môn có vẻ đáng ngờ nhất vì các thi sinh thi khối A Sử dụng ngôn ngữ Python và một số thư (Toán, Lý, Hóa) thường có điểm thi 3 môn viện cần thiết cho phần thực nghiệm như : này không thể chênh lệch quá nhiều như vậy. numpy, pandas, scipy, sklearn. Phần biểu đồ Cụm này cần thiết phải xét đến. sử dụng các thư viện: matplotlib.pyplot và Cụm thứ tư: Các điểm quay quanh mức seaborn. trung bình, cụm này đại diện cho các thí sinh Áp dụng phương pháp phân cụm K-means có học lực trung bình khá nên cũng không cho tập dữ liệu D với số cụm K = 5 được lựa đáng ngờ. Vì vậy, có thể bỏ qua khi xét. chọn theo phương pháp Elbow như Hình 2. Cụm thứ năm: Có điểm thi các môn rất thấp, cụm này đại diện cho các thí sinh thuộc loại yếu kém, nên có thể không đáng nghi ngờ. Vì vậy, có thể bỏ qua khi xét. Để chọn ra các thí sinh có điểm nghi ngờ, thực hiện tính khoảng cách Euclid từ các điểm trong một cụm tới tâm mỗi cụm. Phần thực nghiệm sẽ tiến hành trong 2 trường hợp: Trường hợp 1: Xét điểm bất thường trên tất cả các cụm. Lựa chọn ra 5% các điểm có Hình 2. Đồ thị thăm dò số cụm k khoảng cách lớn nhất (khoảng 32 điểm) cho Sau khi dữ liệu được phân vào 5 cụm. tất cả các cụm. Thực hiện việc tính giá trị trung bình điểm các môn học của 5 cụm ta có kết quả sau: Bảng 1. Trung bình điểm thi mỗi cụm Cluster Math Physics Chemistry Biology 0 8.78235 9.02205 9.06617 3.00735 1 4.83743 3.89285 4.13054 4.51231 2 8.84 9.03 3.00 2.68 3 6.52715 5.92715 5.95364 4.97351 4 2.97419 2.62096 2.70737 3.44354 Hình 3. Các điểm bất thường (Toán - Lý) 134
Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 Hình 4. Các điểm bất thường (Toán - Hóa) Hình 8. Các điểm bất thường (Toán - Hóa) Hình 9. Các điểm bất thường (Toán - Sinh) Hình 5. Các điểm bất thường (Toán - Sinh) Hình 10. Các điểm bất thường (Hóa - Sinh) Các điểm bất thường được khoanh tròn trong các Hình 7 (Toán-Lý), Hình 8 (Toán-Hóa), Hình 6. Các điểm bất thường (Hóa - Sinh) Hình 9 (Toán-Sinh), Hình 10 (Hóa-Sinh). Như vậy, với phương pháp phân cụm Các điểm bất thường được khoanh tròn K-mean và khoảng cách Euclid có thể hỗ trợ trong các đồ thị Hình 3 (Toán-Lý), Hình 4 chúng ta trong việc chọn ra n điểm tình nghi (Toán-Hóa), Hình 5 (Toán-Sinh), Hình 6 (với số lượng điểm n chúng ta chọn trước). (Hóa-Sinh) Cần nhấn mạnh rằng phương pháp này chỉ Trường hợp 2: Chỉ xét riêng cụm thứ nhất giúp chúng ta khoanh vùng các đối tượng thí và cụm thứ ba dựa vào nhận xét về các cụm sinh có điểm tình nghi mà không thể khẳng theo Bảng 1 ở trên. Lấy ra khoảng 24 điểm ở định chắc chắn rằng tất cả trong số họ gian các cụm thứ nhất và thứ ba mà có khoảng lận, việc chấm bài thi cụ thể của các thí sinh cách tới tâm cụm là lớn nhất. khoanh vùng đó mới khẳng định chắn họ có gian lận hay không. 5. TÀI LIỆU THAM KHẢO [1] Charu C Aggarwal, 2017, “Outlier analysis”, Springer, Second Edition. [2] J. B. MacQueen, 1967, “Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability”, Berkeley, University of Hình 7. Các điểm bất thường (Toán - Lý) California Press. 135

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2431 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.