Xem mẫu
- 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
nguon tai.lieu . vn
